【正文】 （２）基于優(yōu)先級(jí)的調(diào)度算法 （３）分時(shí)和優(yōu)先級(jí)相結(jié)合的算法 （ 4）最短作業(yè)優(yōu)先算法（ SJF） 容易實(shí)現(xiàn)，但效率不高。 作業(yè)調(diào)度算法 （１）先來(lái)先服務(wù)（ FCFS） 按作業(yè)進(jìn)入后備緩沖存儲(chǔ)器的先后選取作業(yè)。 ? 為選中的作業(yè)建立相應(yīng)的進(jìn)程。 作業(yè)狀態(tài)及轉(zhuǎn)換圖 作業(yè)控制塊和后備作業(yè)隊(duì)列 指向下一個(gè)JCB指針 ??????? 外設(shè)申請(qǐng) 長(zhǎng)度 位置 時(shí)間估計(jì) 優(yōu)先數(shù) 現(xiàn)在狀態(tài) 作業(yè)名 JCB1 JCB2 ??????? 后備作業(yè)隊(duì)列 作業(yè)控制塊JCB 作業(yè)調(diào)度 作業(yè)調(diào)度的主要功能 ? 按某種調(diào)度算法，從 JCB隊(duì)列中選取作業(yè)進(jìn)入內(nèi)存。 執(zhí)行狀態(tài)： 由作業(yè)調(diào)度程序?qū)⒑髠渥鳂I(yè)隊(duì)列中若干作業(yè)選中，并分配一定的系統(tǒng)資源，建立相應(yīng)的進(jìn)程，進(jìn)入執(zhí)行狀態(tài)。 外 存 內(nèi) 存 提交 收 容 執(zhí) 行 完 成 輸入 作業(yè)調(diào)度 作業(yè)調(diào)度 運(yùn)行 就緒 阻塞 事件發(fā)生 提交狀態(tài) ：用戶向計(jì)算機(jī)提交作業(yè)。 脫機(jī)用戶接口： 批處理用戶 （用 作業(yè)控制語(yǔ)言 提交用戶的命令） 。 第 83 頁(yè) /89 程序一級(jí)的接口 ? 系統(tǒng)調(diào)用 系統(tǒng)調(diào)用命令按其功能分為 5類 （ 1） 進(jìn)程管理和控制 （ 2）外設(shè)管理和控制 （ 3）磁盤(pán)管理和輸入 /輸出 （ 4）文件管理 （ 5）存儲(chǔ)申請(qǐng)和釋放 系統(tǒng)調(diào)用即是用戶在程序中調(diào)用操作系統(tǒng)提供的各種服務(wù)功能。 ? GUI是系統(tǒng)原始的圖形輸出庫(kù)，它用于在屏幕上輸出像素、在打印機(jī)上輸出硬拷貝以及繪制 Windows用戶界面。 第 82 頁(yè) /89 Windows用戶接口 ? 現(xiàn)行的 Windows界面是基于 GUI的用戶接口，已經(jīng)成為一種開(kāi)放化系統(tǒng)的用戶接口。 UNIX系統(tǒng)可同時(shí)接納多個(gè)計(jì)算機(jī)系統(tǒng)的多個(gè)用戶， Shell是根據(jù)用戶輸入的命令，找到相應(yīng)模塊中的程序，為它建立進(jìn)程并執(zhí)行。 Shell即可方便的編程操作，又可以聯(lián)機(jī)作為交互命令使用。 死 鎖 的解除： 1)終止死鎖進(jìn)程； 2)按一定順序中止進(jìn)程直至釋放到有足夠的資源來(lái)完成剩下的進(jìn)程為止； 3)從被鎖住進(jìn)程中強(qiáng)迫剝奪資源以解除死鎖。 一經(jīng)發(fā)現(xiàn)死鎖，必須立即解除。系統(tǒng)有 3個(gè)進(jìn)程，分別用編號(hào) 1~3表示。 在圖中 ， 有兩個(gè)環(huán)： P1 P2 P3R1 R3R4R2第 74 頁(yè) /89 圖 57 資源分配圖 (含環(huán)路 ) P1 P2 P3R1 R3R4R2P1→R1→P2→R3→P3→R2→P1 P2→R3→P3→R2→P2 P P P3均處于死鎖狀態(tài)。 ? 可以證明 ， 如果資源分配圖中沒(méi)有環(huán)路 ， 則系統(tǒng)中沒(méi)有死鎖；如果圖中存在環(huán)路 ，則系統(tǒng)中可能存在死鎖 。這樣的圖就是所謂的 “ 資源分配圖 ”。 R1 R2 P1 P2 用方框代表資源，圓圈代表進(jìn)程。一旦檢測(cè)到死鎖，就按記錄的文件進(jìn)行回退，讓損失減到最小。假定現(xiàn)有 3個(gè)進(jìn)程 A~C，有 5個(gè)同類型資源 r~v。 表示進(jìn)程申請(qǐng)任何類資源數(shù)不能超過(guò)聲明的最大資源需求數(shù) 第 68 頁(yè) /89 匯總向量 R總的資源、 A已分配資源、 V剩余資源 R A V PPT63狀態(tài)下安全判斷，安全序列？ SEE 教材 P144例題 注意 F向量 第 69 頁(yè) /89 總的資源 R、已分配資源 A、剩余資源 V 圖示為安全狀態(tài)，安全序列（ D， A， E， B， C） R A V 第 70 頁(yè) /89 . . . 系統(tǒng)中有 A~G共 7個(gè)進(jìn)程， 6個(gè)同類資源 r~w，當(dāng)前的資源所屬關(guān)系如下： ?死鎖的檢測(cè) 與 恢復(fù) 1. 利用資源分配圖檢測(cè)死鎖 r A s C D F w u G t B E v . A得到資源 r，需要資源 s； . B不占有資源，需要資源 t； . C不占有資源，需要資源 s； D得到資源 u和 s，需要資源 t； . E得到資源 t，需要資源 v； F得到資源 w，需要資源 s； G得到資源 v，需要資源 u。 表示所有資源要么已被分配 、 要么尚可分配 ? Cki ≤R j 對(duì) i=1,..,m,k=1,..,n。因此，接受資源分 配后導(dǎo)致的新?tīng)顟B(tài) 是安全的；如果仍 存在“能執(zhí)行完”標(biāo) 志為 0的進(jìn)程，則 說(shuō)明這一請(qǐng)求所導(dǎo) 致的狀態(tài)是不安全 的，應(yīng)暫時(shí)拒絕該請(qǐng)求。 檢查所有進(jìn)程的 “能執(zhí)行完” 標(biāo)志。 進(jìn)程 磁帶機(jī) 繪圖儀 打印機(jī) CDROM A 3 0 1 1 B 0 1 0 0 C 1 1 1 0 D 1 1 0 1 E 0 0 0 0 進(jìn)程 磁帶機(jī) 繪圖儀 打印機(jī) CDROM A 1 1 0 0 B 0 1 1 2 C 3 1 0 0 D 0 0 1 0 E 2 1 1 0 已分配資源表 還需資源表 R[ 6 3 4 2 ] (資源總數(shù) ) A[ 5 3 2 2 ] (已分配數(shù) ) V[ 1 0 2 0 ] (剩余數(shù) ) . 假定接受一個(gè)進(jìn)程提出的資源請(qǐng)求，修改向量 A和 V。 多種資源銀行家算法的執(zhí)行步驟 系統(tǒng)設(shè)兩張表：“ 分配資源表 ”，記錄已分配給各進(jìn)程的資源數(shù)；“ 還需資源表 ” ，記錄各進(jìn)程還需要的資源數(shù)。 檢查還需資源表中是否有一個(gè)進(jìn)程的行向量小于或等于向量 V。 系統(tǒng)擁有某類資源 10個(gè) 進(jìn)程 已有資源數(shù) 還要申請(qǐng)資源數(shù) P 4 4 Q 2 2 R 2 7 a、單項(xiàng)資源的銀行家算法 第 63 頁(yè) /89 如果存在這種進(jìn)程，那么假定它已獲得需要的所有資源，并完成工作，把它的“能執(zhí)行完”標(biāo)志設(shè)置成 1。若是 ， 則不滿足該請(qǐng)求；否則便滿足 ? 檢查狀態(tài)是否安全的方法：是看它是否有足夠的資源滿足一個(gè)距最大需求最近的客戶 ， 如此反復(fù)下去 。 單種資源銀行家算法的基本思想 單種資源銀行家算法： 將所有進(jìn)程的 “能執(zhí)行完”標(biāo)志清 0 假定接受該請(qǐng)求 , 把資源分配給進(jìn)程 將系統(tǒng)當(dāng)前所有剩余資源 與”能執(zhí)行完”標(biāo)志為 0的進(jìn) 程還需資源數(shù)比較 ,找出一 個(gè)能滿足其所有需求的進(jìn)程 找到了嗎？ 將該進(jìn)程的”能執(zhí)行完” 標(biāo)志置為 1,系統(tǒng)收回它 所要求的全部資源數(shù) Y N 檢查所有進(jìn)程的 “能執(zhí)行完”標(biāo)志 還有” 能執(zhí)行完 ” 標(biāo)志為 0的進(jìn)程嗎？ 這一請(qǐng)求不安 全 ,暫時(shí)不予接受 Y N 這一請(qǐng)求是安 全的 ,可以分配 . .. . . 在“能執(zhí)行完”標(biāo)志為 0 的進(jìn)程中重復(fù)以上兩步，直 到找不到資源還需數(shù)小于系統(tǒng)剩余資源數(shù)的進(jìn)程時(shí)為止。如果找不到，那么系統(tǒng)就有可能死鎖，因 為任何進(jìn)程都無(wú)法運(yùn)行結(jié)束。 在這一假設(shè)下，檢查每個(gè)進(jìn)程對(duì)資源的還需要數(shù)。于是把它的“能執(zhí)行完”標(biāo)志置為 1。 第 59 頁(yè) /89 如果所有進(jìn)程的“能執(zhí)行完”均為 1，表示接受這次請(qǐng)求是安全的；否則暫時(shí)不能接受進(jìn)程的這次資源請(qǐng)求。 銀行家算法的思想 : （假定 在 單類資源的分配 上實(shí)行這一算法）。只有當(dāng)探測(cè)結(jié)果不會(huì)導(dǎo)致死鎖，才真正接收進(jìn)程提出的這一請(qǐng)求。即系統(tǒng)處于安全狀態(tài)一定可以避免死鎖，而系統(tǒng)處于不安全狀態(tài)則僅僅有可能進(jìn)入死鎖狀態(tài)。 第 56 頁(yè) /89 注意： ?（ 1）系統(tǒng)在某一時(shí)刻的安全序列可能不唯一，但這不影響對(duì)系統(tǒng)安全性的判斷。則稱此時(shí)系統(tǒng)的狀態(tài)為 安全狀態(tài) ，稱這樣的一個(gè)進(jìn)程序列 P1,P2,…,Pn 為 安全序列 。 ? 常用的避免死鎖的算法是 “ 銀行家算法 ” ，系統(tǒng)采用此法給進(jìn)程分配資源時(shí)，需先判斷 “ 如果分配，系統(tǒng)狀態(tài)是否安全 ” ，這很像銀行家 放貸前的思考過(guò)程 。當(dāng)然，若不按照安全序列分配資源，安全狀態(tài)可能變?yōu)椴话踩珷顟B(tài)。 如果 P3 請(qǐng)求 1 臺(tái) , 狀態(tài)發(fā)生變化 . 已分配 5 2 2 可用 3 還需 5 2 7 找不到一個(gè)安全序列 . 狀態(tài)不安全 . 請(qǐng)求不能滿足。 第 53 頁(yè) /89 例：三個(gè)進(jìn)程 P1,P2,和 P3,所需要磁帶機(jī)分別為 10， 4，9臺(tái)，系統(tǒng)中共 12臺(tái)。進(jìn)程申請(qǐng)使用資源時(shí)，必須嚴(yán)格按照編號(hào)的升序進(jìn)行。 采用虛擬技術(shù)，使 非共享設(shè)備變成共享設(shè)備 ，以避免死鎖。 破壞循環(huán)等待。 破壞對(duì)資源采用動(dòng)態(tài)的部分分配原則（每個(gè)進(jìn)程必須提出它所需要的全部資源，只有完全滿足時(shí)，才能啟動(dòng)）。 破壞“資源的不可剝奪性”（申請(qǐng)不到資源時(shí)，釋放原先已占有的，進(jìn)入等待，以后再一起申請(qǐng)）。 解決死鎖的辦法 *死鎖的預(yù)防 ? 破壞產(chǎn)生死鎖的 4個(gè)必要條件中的任何一