【正文】 帶機(jī)。設(shè)在時(shí) 刻 T0進(jìn)程 P P2和 P3分別已經(jīng)獲得 5臺(tái)、 2臺(tái)和 2臺(tái)磁帶機(jī)。 進(jìn)程 最大需求 已分配 可用 P1 10 5 3 P2 4 2 P3 9 2 死鎖 死鎖的檢測(cè)與恢復(fù) 發(fā)現(xiàn)死鎖的原理： 考查某一時(shí)刻系統(tǒng)狀態(tài) 是否合理 檢測(cè)死鎖算法的基本思想 死鎖檢測(cè)的時(shí)機(jī)： 1) 每次分配后； 2)定期檢查 排除死鎖的實(shí)用方法： 1)把陷于死鎖的全部進(jìn)程一律撤消； 2)逐個(gè)作廢死鎖進(jìn)程至死鎖不再存在； 3)逐個(gè)強(qiáng)迫搶占資源至死鎖不再存在 死鎖 處理機(jī)的多級(jí)調(diào)度 1）確定數(shù)據(jù)結(jié)構(gòu) 2）制訂調(diào)度策略（調(diào)度原則） 3）給出調(diào)度算法 4）具體的實(shí)施處理機(jī)分派 處理機(jī)調(diào)度分類：作業(yè)調(diào)度和進(jìn)程調(diào)度 3. 多任務(wù)操作系統(tǒng)中的處理機(jī)調(diào)度 處理機(jī)調(diào)度 進(jìn)程調(diào)度 進(jìn)程調(diào)度（也稱 CPU調(diào)度） :按照某種調(diào)度 算法從就緒隊(duì)列中選取進(jìn)程分配 CPU 衡量各種調(diào)度算法性能優(yōu)劣的指標(biāo) : 1） CPU利用率 —— 主要目標(biāo) CPU利用率 =CPU利用的時(shí)間 /開(kāi)機(jī)運(yùn)行的總時(shí)間 2）等待時(shí)間 3）響應(yīng)時(shí)間 4） I/O設(shè)備的利用率 5）“時(shí)空”代價(jià) 處理機(jī)調(diào)度 進(jìn)程調(diào)度 進(jìn)程調(diào)度方式： 剝奪調(diào)度和非剝奪調(diào)度 下面介紹幾種常見(jiàn)的進(jìn)程調(diào)度方法 （ First e first service, FCFS） 2. 輪轉(zhuǎn)法（ RR， Round Robin） 將 CPU的處理時(shí)間分成固定大小的時(shí)間片 ，進(jìn)程時(shí)間片內(nèi)輪轉(zhuǎn)執(zhí)行 關(guān)鍵問(wèn)題： 如何確定時(shí)間片的大小 時(shí)間片 q = RT/Nmax 處理機(jī)調(diào)度 將考慮下面 3個(gè)進(jìn)程，它們按 1， 2， 3的順序處于就緒隊(duì) 列中： 進(jìn)程 下一個(gè) CPU周期 P1 24 P2 3 P3 3 處理機(jī)調(diào)度 圖 316 執(zhí)行過(guò)程 1 圖 317 執(zhí)行過(guò)程 2 FCFS調(diào)度算法 其他調(diào)度算法 2. 輪轉(zhuǎn)法 設(shè)有如下 4個(gè)就緒進(jìn)程： 進(jìn)程 下一個(gè) CPU周期 P1 6 P2 3 P3 1 P4 7 則如圖 318所示 處理機(jī)調(diào)度 ATT 0 1 2 3 4 5 6 7 q 圖 318 平均周轉(zhuǎn)時(shí)間 ATT與時(shí)間片q之間的關(guān)系 進(jìn)程調(diào)度 3. 多級(jí)反饋輪轉(zhuǎn)法 思想： 不同級(jí)別的就緒隊(duì)列分配給不同時(shí) 間片，優(yōu)先級(jí)高的為第一級(jí)隊(duì)列，時(shí)間片最 小，隨著隊(duì)列級(jí)別降低，時(shí)間片加大 例如 考慮由 3個(gè)隊(duì)列組成的多級(jí)隊(duì)列調(diào)度。 3個(gè)隊(duì)列的編號(hào)分別為 0, 1, 2，如圖 319 處理機(jī)調(diào)度 進(jìn)程調(diào)度 4. 優(yōu)先數(shù)法（ Priority） 思想： 按進(jìn)程的優(yōu)先級(jí)確定調(diào)度優(yōu)先權(quán) 優(yōu)先級(jí)確定方法： （ 1）靜態(tài)法：可按進(jìn)程類型、資源的要 求、用戶要求指定 （ 2）動(dòng)態(tài)法：原則是合理地分配 CPU時(shí)間、 緊急的程序優(yōu)先 處理機(jī)調(diào)度 實(shí)例解釋： 假設(shè)就緒狀態(tài)有 4個(gè)進(jìn)程，每個(gè)進(jìn)程所需運(yùn)行 時(shí)間如下所示。 進(jìn)程 所需運(yùn)行時(shí)間 1 6 2 3 3 1 4 7 進(jìn)程到達(dá)次序?yàn)?1， 2， 3， 4。試分別按先來(lái)先服務(wù)調(diào) 度算法、短進(jìn)程優(yōu)先調(diào)度算法和時(shí)間片輪轉(zhuǎn)法 (時(shí)間片 分 1， 3， 5， 6) 給出進(jìn)程調(diào)度順序，并計(jì)算平均等待時(shí) 處理機(jī)調(diào)度 解： （ 1）先來(lái)先服務(wù)調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋? T=1／ 4 (0+6+9+10)= （ 2）短進(jìn)程優(yōu)先調(diào)度算法進(jìn)程調(diào)度順序?yàn)椋? 平均等待時(shí)間： T=1／ 4 (4+1+0+10)= （ 3）時(shí)間片輪轉(zhuǎn)法 處理機(jī)調(diào)度 解： 時(shí)間片為 1 T=1/4 ((0+3+2+2+1+1)+(1+3+2)+2+(3+2+2+1+1+1) =1／ 4 (9+6+2+10)= 時(shí)間片為 3，進(jìn)程調(diào)度順序如下： T=1／ 4 ((0+7)+3+6+(7+3)) =1／ 4 (7+3+6+10)= 處理機(jī)調(diào)度 解： 時(shí)間片為 5，進(jìn)程調(diào)度順序如下： T=1／ 4 ((0+9)+5+8+(9+1)) =1／ 4 (9+5+8+10)=8 時(shí)間片為 6，相當(dāng)于先來(lái)先服務(wù)調(diào)度算法。其進(jìn)程調(diào)度順序和平均等待時(shí)間與先來(lái)先服務(wù)調(diào)度算法相同。 總結(jié)： 短進(jìn)程優(yōu)先調(diào)度算法使進(jìn)程平均等待時(shí)間最小。 對(duì)于時(shí)間片輪轉(zhuǎn)法，進(jìn)程平均等待時(shí)間與時(shí)間片的大小 有關(guān)。 處理機(jī)調(diào)度 Windows XP 的進(jìn)程 XP的進(jìn)程對(duì)象 XP的進(jìn)程 TDB （任務(wù)數(shù)據(jù)庫(kù)） Windows XP的進(jìn)程和線程管理 圖 320 Windows XP的進(jìn)程對(duì)象 進(jìn)程 進(jìn)程 ID 安全描述符 基本優(yōu)先級(jí) 默認(rèn)處理器集合 定額限制 執(zhí)行時(shí)間 I/O計(jì)數(shù)器 VM操作計(jì)數(shù)器 異常 /調(diào)試端口 退出狀態(tài) 創(chuàng)建進(jìn)程 打開(kāi)進(jìn)程 查詢進(jìn)程信息 設(shè)置進(jìn)程信息 當(dāng)前進(jìn)程 終止進(jìn)程 對(duì)象類型 對(duì)象體屬性 服務(wù) 圖 321 Windows XP的進(jìn)程 TDB 私有堆棧 鏈接指針 狀態(tài)標(biāo)志 （ 事件計(jì)數(shù) ）優(yōu)先級(jí) …… 屬 性 名 稱 屬 性 含 義 進(jìn)程 ID 進(jìn)程的惟一標(biāo)識(shí) 安全描述符 描述誰(shuí)創(chuàng)建對(duì)象 、 誰(shuí)可以訪問(wèn) /使用對(duì)象或禁止誰(shuí)訪問(wèn)對(duì)象 基本優(yōu)先級(jí) 進(jìn)程中線程的基本優(yōu)先級(jí) 默認(rèn)處理器集合 可以運(yùn)行的進(jìn)程中線程的默認(rèn)處理器集合 定額限制 頁(yè)式存儲(chǔ)器及頁(yè)式文件空間 ， 進(jìn)程可使用的處理器最大時(shí)間 執(zhí)行時(shí)間 進(jìn)程中的所有線程已經(jīng)執(zhí)行的時(shí)間總量 I/O計(jì)數(shù)器 記載進(jìn)程中線程已執(zhí)行的 I/O操作數(shù)量 、 類型的變量 VM操作計(jì)數(shù)器 記載進(jìn)程中線程已執(zhí)行的虛擬存儲(chǔ)操作數(shù)量 、類型的變量 異常 /調(diào)試端口 進(jìn)程中的線程異常時(shí) ， 用于進(jìn)程管理器發(fā)送消息的通信信道 退出狀態(tài) 進(jìn)程終止的原因 表 32 Windows XP進(jìn)程對(duì)象的屬性 Windows XP 的線程 XP的線程 對(duì)象 線程對(duì)象如圖 322所 示 線程對(duì)象的屬性見(jiàn)表 33。 Windows XP的進(jìn)程和線程管理 線程 線程 ID 動(dòng)態(tài)優(yōu)先級(jí) 基本優(yōu)先級(jí) 線程處理器集合 線程執(zhí)行 警告狀態(tài) 掛起計(jì)數(shù)器 假冒標(biāo)志 終止端口 線程退出狀態(tài) 創(chuàng)建線程 打開(kāi)線程 查詢線程信息 當(dāng)前線程 終止線程 獲取上下文 設(shè)置上下文 掛起 恢復(fù) 警告線程 測(cè)試線程警告 寄存器終止端口 對(duì)象類型 對(duì)象屬性 服務(wù) 圖 322Windows XP線程對(duì)象 屬 性 名 稱 屬 性 含 義 線程 ID 當(dāng)線程調(diào)用一個(gè)服務(wù)程序時(shí) ， 標(biāo)識(shí)該線程的惟一值 線程上下文 定義線程執(zhí)行狀態(tài)的一組寄存器值和其他易失的數(shù)據(jù) 動(dòng)態(tài)優(yōu)先級(jí) 任何給定時(shí)刻 ， 線程執(zhí)行優(yōu)先級(jí) 基本優(yōu)先級(jí) 線程動(dòng)態(tài)優(yōu)先級(jí)的下限 線程處理器集合 可以運(yùn)行的線程的處理器集合 線程執(zhí)行時(shí)間 線程在用戶模式和內(nèi)核模式下執(zhí)行的時(shí)間總量 警告狀態(tài) 表示線程是否將執(zhí)行一個(gè)異步過(guò)程調(diào)用的標(biāo)志 掛起計(jì)數(shù)器 記載線程被掛起的次數(shù) （ 但未恢復(fù) ） 假冒標(biāo)志 允許線程代表另一進(jìn)程執(zhí)行的臨時(shí)訪問(wèn)標(biāo)志 （ 供子系統(tǒng)使用 ） 線程退出狀態(tài) 線程終止的原因 表 33 Windows XP線程對(duì)象的屬性 XP的線程狀態(tài) 等待完成 等待完成 換出的內(nèi)核堆棧 換入的內(nèi)核堆棧 搶先或 時(shí)間片完 等待對(duì)象句柄 完成 描述表切換 選擇執(zhí)行 創(chuàng)建并初始化 初始化 備用 就緒 運(yùn)行 轉(zhuǎn)換 終止 等待 圖 323 Windows XP線程狀態(tài)轉(zhuǎn)換 Windows XP的線程 XP的線程控制 CreateThread、 ExitThread、SuspendThread、 ResumeThread XP的線程調(diào)度 Windows XP的調(diào)度對(duì)象是線程 Windows XP采用嚴(yán)格的搶先式動(dòng)態(tài)優(yōu)先級(jí)調(diào) 度，根據(jù)優(yōu)先級(jí)和分配時(shí)間配額（ quantum）進(jìn) 行調(diào)度 Windows XP的進(jìn)程和線程管理 XP的線程調(diào)度 Windows XP的進(jìn)程和線程管理 表 34 Windows 32中與線程調(diào)度相關(guān)的 API函數(shù)及功能說(shuō)明 與線程調(diào)度有關(guān)的 API函數(shù) 函數(shù)功能說(shuō)明 Suspend/ResumeThread 掛起 /激活一個(gè)正在運(yùn)行 /暫停的線程 Get/SetPriorityClass 讀 /設(shè)置一個(gè)線程的基本優(yōu)先級(jí)類型 Get/SetThreadPriority 讀 /設(shè)置一個(gè)線程的相對(duì)優(yōu)先級(jí) Get/SetProcessPriorityBoost 讀 /設(shè)置當(dāng)前進(jìn)程的默認(rèn)優(yōu)先級(jí)提升控制 Get/SetThreadPriorityBoost 讀 /設(shè)置暫時(shí)提升線程優(yōu)先級(jí)狀態(tài)：在可調(diào)范圍內(nèi) Get/SetProcessAffinityMask 讀 /設(shè)置一個(gè)進(jìn)程的默認(rèn)處理器集合 SetThreadAffinityMask 設(shè)置線程的默認(rèn)處理器集合 SetThreadIdealProcessor 設(shè)置線程的首選處理器 ， 但不限制線程在該處理器 SwitchToThread 當(dāng)前線程放棄一個(gè)或多個(gè)時(shí)間配額的運(yùn)行 Sleep 使當(dāng)前線程等待一個(gè)指定的時(shí)間段 SleepEx 使當(dāng)前線程進(jìn)入等待狀態(tài) Windows XP的進(jìn)程互斥和同步 、互斥對(duì)象與臨界區(qū)對(duì)象 Windows XP中用于互鎖變量訪問(wèn)的 API函數(shù)：InterlockedExchange、InterlockedExchangePointer、InterlockedCompareExchange、InterlockedCompareExchangePointer、InterlockedExchangeAdd、InterlockedDecrement、InterlockedIncrement。 Windows XP的進(jìn)程和線程管理 Windows XP的進(jìn)程互斥和同步 、互斥對(duì)象與臨界區(qū)對(duì)象 Windows XP中與互斥對(duì)象有關(guān)的 API函數(shù)： Crea