【文章內(nèi)容簡介】 已送緩沖區(qū)的信號 讀緩沖區(qū)數(shù)據(jù) 并計算 向 A進程發(fā)信號緩沖區(qū)數(shù)據(jù)已取走 兩進程并發(fā)執(zhí)行過程 57 同步機制 實現(xiàn)進程同步與互斥的機制稱為同步機制 ? 空閑讓進 ：無進程處于臨界區(qū)內(nèi)，可讓一申請進入臨界區(qū)的進程進入，以有效利用臨界資源 ? 忙則等待 ：若已有進程進入臨界區(qū)時，其余試圖進入臨界區(qū)的進程必須等待，以保證它們互斥的進入臨界區(qū) ? 有限等待 ：對要求進入臨界區(qū)的進程，應(yīng)在有限時間內(nèi)使之進入，以免陷入“死等” ? 讓權(quán)等待 ：等待進入臨界區(qū)的進程，它必須立即釋放處理機，以免進程“忙等” 58 P、 V操作 (一種典型的同步機制 ) ? P－等待 V－發(fā)信號 S－信號量 （共享資源使用情況） P操作 P(S): while(S=0) S=S1。 V操作 V(S): S=S＋ 1 59 進程 A … P（ mutex）； 進入 A臨界區(qū)； V（ mutex）； … 進程 B … P（ mutex）； 進入 B臨界區(qū)； V（ mutex）； … 利用 P、 V操作實現(xiàn)進程的互斥模型 ?Ｐ－申請獲取資源；Ｖ－釋放資源； ?在進入臨界區(qū)時，執(zhí)行Ｐ操作，獲取對臨界資源的控制權(quán)； ?離開時，執(zhí)行Ｖ操作，釋放對臨界資源的控制權(quán)。 60 利用 P、 V操作實現(xiàn)進程的同步例子 計算進程（ CP） … 計算結(jié)果放入緩沖區(qū)； V（ S1）； P（ S2）； … 打印進程（ IOP） … P（ S1）； 從緩沖區(qū)取結(jié)果打??； V（ S2）； … 緩沖區(qū) 計算進程 打印進程 S1 S2 61 生產(chǎn)者－消費者問題 ? 生產(chǎn)者 －釋放某一資源的進程 ? 消費者 －使用同類資源的進程 制約關(guān)系 ： 緩沖區(qū)至少有一個單元為空， 生產(chǎn)者進程才能放入“產(chǎn)品”； 緩沖區(qū)中至少有一個單元是滿 的，消費者進程才能取出“產(chǎn)品”； 各消費者進程與各生產(chǎn)者進程 只能互斥的使用臨界資源緩沖區(qū)。 消費者進程 生產(chǎn)者進程 in out 62 生產(chǎn)者－消費者進程的模型 生產(chǎn)者進程 生產(chǎn)一個產(chǎn)品； P（ empty）； P（ mutex）； 將產(chǎn)品放入 in指向的緩沖區(qū)； in=(in+1) mod n。 V（ mutex）； V（ full）； … 消費者進程 P（ full）； P（ mutex）； 從 out指向的緩沖區(qū)取產(chǎn)品； out=(out+1) mod n。 V（ mutex）； V（ empty）； … 檢查是否有空緩沖區(qū) 申請進入臨界區(qū) 進程退出臨界區(qū)，即釋放臨界資源 滿緩沖區(qū)數(shù)量＋ 1 63 生產(chǎn)者－消費者進程的模型 生產(chǎn)者進程 生產(chǎn)一個產(chǎn)品； P（ empty）； P（ mutex）； 將產(chǎn)品放入 in指向的緩沖區(qū)； in=(in+1) mod n。 V（ mutex）； V（ full）； … 消費者進程 P（ full）； P（ mutex）； 從 out指向的緩沖區(qū)取產(chǎn)品； out=(out+1) mod n。 V（ mutex）； V（ empty）； … 檢查緩沖區(qū)是否有信息 申請進入臨界區(qū) 進程退出臨界區(qū)，即釋放臨界資源 空緩沖區(qū)數(shù)量＋ 1 64 生產(chǎn)者－消費者進程的模型 生產(chǎn)者進程 生產(chǎn)一個產(chǎn)品； P（ empty）； P（ mutex）； 將產(chǎn)品放入 in指向的緩沖區(qū)； in=(in+1) mod n。 V（ mutex）； V（ full）； … 消費者進程 P（ full）； P（ mutex）； 從 out指向的緩沖區(qū)取產(chǎn)品； out=(out+1) mod n。 V（ mutex）； V（ empty）； … 注意： 該進程中， P操作的次序不允許顛倒，否則可能死鎖。 65 五、進程通信 (1)基于共享數(shù)據(jù)結(jié)構(gòu)或共享內(nèi)存進行通信 (2)利用消息進行通信 (3)利用共享文件進行通信 發(fā)送進程 接收進程信箱信箱頭 發(fā)送進程 接收進程 共享文件66 六、 死鎖 ? 死鎖：在多個進程并發(fā)執(zhí)行并共享系統(tǒng)軟硬件資源的情況下，各進程彼此互相等待對方所擁有且又不釋放的資源，導(dǎo)致永遠等待下去。 ? 死鎖產(chǎn)生的原因： １）爭奪資源而引起的死鎖 打印機 Ｒ １ 磁帶機 Ｒ ２ Ｐ １ Ｐ ２ 已分配 申 請 已分配 申 請 67 ２）進程推進順序不當而引起的死鎖 S1 S3 Ｐ １ Ｐ ２ S2 Ｐ 3 死鎖： P1： …Request(S3)。Relese(S1)。… P2： …Request(S1)。Relese(S2)?！? P3： …Request(S2)。Relese(S3)。… 不會死鎖： P1： …Relese(S1)。Request(S3)。 … P2： …Relese(S2)。Request(S1)。 … P3： …Relese(S3)。Request(S2)。 … 68 ? 產(chǎn)生死鎖的必要條件 １）互斥條件 進程互斥使用資源，任一時刻一個資源只為一個進程獨占。 2）請求和保持條件 進程每次申請它所需要的一部分新資源的同時，繼續(xù)占用它已分配到的資源。 3）不剝奪條件 進程所獲得的資源在未使用完畢前，不能被其他進程強行剝奪。 ４）環(huán)路條件 存在一個循環(huán)等待鏈，鏈中每一個進程都在等待它的前一個進程所持有的資源。 69 ? 死鎖的預(yù)防（有效，使資源利用率低） 通過設(shè)置某些限制條件，以破壞產(chǎn)生死鎖的四個必要條件中的一個或幾個，來防止發(fā)生死鎖。 互斥條件是資源固有屬性，不能避免。 摒棄請求和保持條件 全分配，全釋放 缺點： 1）延遲進程運行 2）資源嚴重浪費 摒棄 “ 不剝奪 ” 條件 一個已保持了某些資源的進程，若新的資源要求不能立即得到滿足，它必須釋放已保持的所有資源。 缺點：實施復(fù)雜，增加系統(tǒng)開銷，且進程前段工作可能失效。 摒棄 “ 環(huán)路 ” 條件 有序資源分配法：為資源編號，申請時需按編號進行。 缺點： 1）新增資源不便，（原序號已排定） 2）用戶不自由 3）資源與進程使用順序不同造成浪費 處理死鎖的基本方法 70 ? 避免死鎖 不需要預(yù)先采取各種限制措施，去破壞產(chǎn)生死鎖的必要條件，而是在資源的動態(tài)分配過程中，使用某種方法去防止系統(tǒng)進入不安全狀態(tài)，從而避免了死鎖的發(fā)生。 系統(tǒng)對各種資源的分配提供一種算法，當進程申請資源時，采用相應(yīng)算法計算，以確定這一申請是否會造成死鎖。 最著名的避免死鎖的 算法 — 銀行家算法 。 ? 死鎖的檢測與解除 檢測到死鎖再清除 １）撤銷進程法 ２）資源剝奪法 71 作業(yè)管理 進程 是計算機系統(tǒng)中的 基本工作單位 ，而 作業(yè)是用戶請求系統(tǒng)服務(wù)的 最大單位 。 一、概念 一個作業(yè)就是用戶請求計算機系統(tǒng)執(zhí)行的一次獨立的上機任務(wù)，是能共享公共資源區(qū)域的 一組 有關(guān) 進程 。 組成： 控制命令序列 、 程序集 和 數(shù)據(jù)集 一個作業(yè)又可分為若干順序處理的 作業(yè)步 。 72 作業(yè)控制塊（ JCB） JCB是作業(yè)在系統(tǒng)中存在的唯一標志。與作業(yè)間是一一對應(yīng)的關(guān)系。是記錄類型的 數(shù)據(jù)結(jié)構(gòu) ，用于記錄作業(yè)的有關(guān)信息 。 作業(yè)狀態(tài) 提交（進入）、后備、運行、完成 提交 后備 完成 執(zhí)行 就緒 等待 運行 進程調(diào)度 作業(yè)建立 作業(yè)調(diào)度 終止作業(yè) 73 二、作業(yè)控制 用戶與操作系統(tǒng)的接口 1）命令接口。（普通用戶） 2）系統(tǒng)調(diào)用。（編程人員） 控制方式 1）聯(lián)機方式。 命令驅(qū)動（ MS－ DOS） 菜單驅(qū)動 窗口驅(qū)動（ Windows） 2）脫機方式。 通常用于批處理系統(tǒng) 74 作業(yè)調(diào)度 進程調(diào)度稱為處理機的 低級調(diào)度 ，作業(yè)調(diào)度稱為處理機的 高級調(diào)度 。 1）功能 按某種調(diào)度算法，從作業(yè)的后備隊列中挑選一批合理搭配的作業(yè)進入內(nèi)存，實現(xiàn)作業(yè)從后備狀態(tài)轉(zhuǎn)變?yōu)檫\行狀態(tài)。同時為選中的作業(yè)分配內(nèi)存和外設(shè)資源、并為其建立有關(guān)的進程。 2）調(diào)度算法 先來先服務(wù) 最高優(yōu)先級 最短作業(yè)優(yōu)先 最高響應(yīng)比優(yōu)先 資源搭配法 75 存儲管理 目的 ： 盡可能方便用戶和提高主存儲器的效率。 存儲管理應(yīng)當解決幾個問題 ： ? 一是 存儲空間的分配和回收 ； ? 二是 地址映射 ，就是把程序使用的地址映射成內(nèi)存空間地址； ? 三是 內(nèi)存的保護 ，就是系統(tǒng)必須保證內(nèi)存中的進程不會相互干擾，影響整個系統(tǒng)的穩(wěn)定性、可靠性。 76 重要術(shù)語 ?邏輯空間 和 物理空間 ： 邏輯空間是程序設(shè)計人員的編程空間，物理空間是指內(nèi)存空間，是由物理存儲單元組成 ?重定位 和 地址映射 ： 在設(shè)計程序時，程序設(shè)計人員使用的是邏輯地址空間，在程序調(diào)入內(nèi)存實際執(zhí)行時，操作系統(tǒng)再將邏輯地址空間轉(zhuǎn)換成內(nèi)存的物理地址空間，稱為 地址映射 。由操作系統(tǒng)自動完成，對用戶是透明的。 重定位 ：一是當某程序裝入內(nèi)存運行時，根據(jù)其所獲得的空間位置，將程序的邏輯地址映射成相應(yīng)的物理地址；二是在程序的執(zhí)行過程中，如果系統(tǒng)移動了其在內(nèi)存的位置，需要將程序的邏輯地址重新映射成新的物理地址 77 覆蓋 (Overlay):P107 ? 目的 ：為了能在小的內(nèi)存空間中運行大的作業(yè) ? 原理 ：一個程序的幾個代碼段或數(shù)據(jù)段，按照時間先后來占用公共的內(nèi)存空間。 1）將程序的必要部分（常用功能）的代碼和數(shù)據(jù)常駐內(nèi)存； 2）可選部分（不常用功能）在其他程序模塊中實現(xiàn)，平時存放在外存中，在需要用到時才裝入到內(nèi)存； 3）不存在調(diào)用關(guān)系的模塊不必同時裝入到內(nèi)存，從而可以相互覆蓋。 ? 缺點 ：編程時必須劃分程序模塊和確定程序模塊之間的覆蓋關(guān)系，增加編程復(fù)雜度。從外存裝入覆蓋文件，以時間延長來換取空間節(jié)省。 ? 實現(xiàn) ：函數(shù)庫（操作系統(tǒng)對覆蓋不得知），或操作系統(tǒng)支持 78 交換技術(shù) （對換， Swapping） 目的 ：內(nèi)外存之間交換程序和數(shù)據(jù)。緩解內(nèi)存不足的矛盾。 多個程序并發(fā)執(zhí)行，可以將暫時不能執(zhí)行的程序送到外存中，從而獲得空閑內(nèi)存空間來裝入新程序，或讀入保存在外存中而目前到達就緒狀態(tài)的程序。 原理 ：暫停執(zhí)行內(nèi)存中的進程，將整個進程的地址空間保存到外存的交換區(qū)中（換出 swap out），而將外存中由阻塞變?yōu)榫途w的進程的地址空間讀入到內(nèi)存中，并將該進程送到就緒隊列（換入 swap in）。 優(yōu)點 ：增加并發(fā)運行的程序數(shù)目，并且給用戶提供適當?shù)捻憫?yīng)時間；編寫程序時不影響程序結(jié)構(gòu) 缺點 ：對換入和換出的控制增加處理機開銷；程序整個地址空間都進行傳送，沒有考慮執(zhí)行過程中地址訪問的統(tǒng)計特性。 考慮的問題 ： ? 程序換入時的重定位； ? 減少交換中傳送的信息量，特別是對大程序。 79 虛擬存儲 ：虛擬存儲器，就是把內(nèi)外存連起來統(tǒng)一使用 . 常規(guī)存儲管理的問題： 用戶編程的地址空間不能超過實際的內(nèi)存空間，故無法運行很大的應(yīng)用程序； 產(chǎn)生存儲碎片，內(nèi)存空間利用率低。 虛擬存儲的 基本思想 ： 用大容量的外存對內(nèi)存進行邏輯擴充，為用戶提供一個比有限的實際內(nèi)存空間大的多的虛擬內(nèi)存空間。以便有效的支持多道程序系統(tǒng)中大型作業(yè)的需要，增強系統(tǒng)的處理能力。 80 存儲管理方式 ? 1）分區(qū)管理 ： 把內(nèi)存空間靜態(tài)地或動態(tài)地分割成若干大小不等的區(qū)域，每個作業(yè)分配 一片連續(xù)的存儲空間 ，程序一次整體裝入到系統(tǒng)內(nèi)存中。常見的有：固定式、可變式、動態(tài)重定位和多重分區(qū)幾種。 ? 固定式分區(qū) ：有 n個分區(qū)，則可同時最多裝入 n個作業(yè) /任務(wù)。 — 分區(qū)大?。合嗟?，不相等（不相等利用率更高） — 簡單，有碎片（內(nèi)零頭 :分配給用戶而未被利用的空間） （外零頭：存儲空間中小