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