




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
1、調度與死鎖調度與死鎖內容提要內容提要 調度的類型及其功能 調度的性能評價 常用的調度算法 死鎖調度的含義調度的含義 調度就是選出待分派的作業或進程 處置機調度的主要目的是為了分配處置機調度的類型調度的類型 高級調度:作業調度 中級調度:存儲對換 低級調度:進程調度進程的調度方式進程的調度方式 非搶占方式 搶占方式進程調度的時機進程調度的時機 現行進程完成或錯誤終止 現行進程提出I/O懇求,等待I/O完成時 在進程通訊中,執行中的進程執行了某種原語操作,如P操作、阻塞原語時,都能夠引起進程調度 在分時系統,按照時間片輪轉,分給進程的時間片用完時 優先級調度時,有更高優先級進程變為就緒時進程調度的
2、主要功能進程調度的主要功能 保管讓權進程的現場 擇優選出一個就緒進程 為選中進程恢復現場,令其投入運轉作業調度和進程調度的區別作業調度和進程調度的區別 作業調度是宏觀調度,進程調度是微觀調度 作業調度為進程的活動做預備,進程調度使進程真正活動起來 作業調度執行次數較少,進程調度活動頻繁 作業調度可以不設,進程調度必不可少僅有進程調度的調度隊列模型僅有進程調度的調度隊列模型就就 緒緒 隊隊 列列阻阻 塞塞 隊隊 列列CPU事件出現事件出現交互用戶交互用戶時間片完時間片完進程進程調度調度等待等待事件事件進程完成進程完成常用的調度性能評價規范常用的調度性能評價規范 CPU的利用率 系統吞吐量 周轉時
3、間 呼應時間 就緒隊列等待時間周轉時間周轉時間 周轉時間是指從作業提交給系統開場,到作業完成為止的時間 通常把周轉時間作為評價批處置系統性能、選擇作業調度方式與算法的準那么平均周轉時間與平均帶權周轉時間平均周轉時間與平均帶權周轉時間 平均周轉時間可描畫為: 通常把周轉時間作為評價批處置系統性能、選擇作業調度方式與算法的準那么常用調度算法常用調度算法 對于不同的系統和系統目的,通常采用不同的調度算法。目前存在很多調度算法,有的適用于作業調度,有的適用于進程調度,有的兩者都適用。先來先效力調度算法先來先效力調度算法 先來先效力FCFS算法的思想很簡單:每次調度是從作業后備隊列中選擇一個或多個最先進
4、入該隊列的作業,將它們調入內存,為它們分配資源,創建進程,然后放入就緒隊列。FCFSFCFS算法表示圖算法表示圖作業作業T作業作業1作業作業2作業作業3012242730表示作業到達時間表示作業到達時間表示作業執行過程表示作業執行過程FCFSFCFS算法性能分析算法性能分析作業作業 到達時間到達時間 運轉時間運轉時間 開場時間開場時間 完成時間完成時間 周轉時間周轉時間 帶權周轉時間帶權周轉時間平均周轉時間平均周轉時間 T=26 平均帶權周轉時間平均帶權周轉時間 W=6.331 0 24 0 24 24 12 1 3 24 27 26 8.673 2 3 27 30 28 9.33FCFS的特
5、征的特征 較利于長作業或進程 有利于占用CPU時間多的作業 容易實現,但效率較低短作業進程優先調度算法短作業進程優先調度算法 短作業(SJF)調度算法是從后備隊列中選擇一個或假設干個估計運轉時間最短的作業,將它們調入內存運轉 短進程(SPF)調度算法是從就緒隊列中選出一估計運轉時間最短的進程,將處置機分配給它,使它立刻執行SJ(P)FSJ(P)F調度算法的缺陷調度算法的缺陷 對長作業非常不利 完全未思索作業的緊迫程度 由于作業進程的長短,只是根據用戶估計的時間而定,致使算法不一定能真正做到短作業優先調度時間片輪轉調度算法時間片輪轉調度算法 系統使每個進程依次按時間片輪番執行。在通常的輪轉法中,
6、系統將一切就緒進程按先來先效力原那么,排成一個隊列。每次調度時,把CPU分配給隊首進程,并對其執行一個時間片。時間片的大小從幾ms到幾百ms。 時間片用完時,停頓該進程的執行,并將其送入就緒隊列的末尾。影響時間片長短的要素影響時間片長短的要素 系統的呼應時間 就緒隊列進程的數目 進程的轉換時間 CPU運轉指令速度優先權調度算法優先權調度算法 為照顧到緊迫型作業進入到系統后就能獲得優先處置,引入最高優先權調度算法。當該算法用于作業調度時,系統將從后備隊列中選擇假設干優先權最高的作業調入內存;當算法用于進程調度時,把處置機分配給就緒隊列中優先權最高的進程。算法分類算法分類 非搶占式優先權算法 搶占
7、式優先權算法優先權的類型優先權的類型 靜態優先權。確定根據為:進程類型、進程對資源的需求、用戶要求 動態優先權多級隊列調度多級隊列調度 多級隊列調度是根據作業的性質或類型不同,將就緒隊列分成假設干個子隊列,每個作業固定屬于某個隊列。每個隊列采用一種算法,不同隊列可采用不同的調度算法。多級反響隊列調度算法多級反響隊列調度算法 多級反響隊列調度算法不用事先了解各進程所需的執行時間,而且還可滿足各種類型進程的需求,是目前公認的比較好的進程調度算法。多級反響隊列中就緒隊列種類多級反響隊列中就緒隊列種類 剛剛被創建的進程等待進程調度 曾經被調度執行過,但還沒有執行完,等待下一次調度 正在執行的進程還未用
8、完時間片,因懇求I/O,等待I/O完成被迫放棄CPU,當等待緣由解除后,進入就緒隊列等待運轉多級反響隊列調度的實施過程多級反響隊列調度的實施過程 系統設置多個就緒隊列,進程在其生命期內能夠在多個隊列中存在 各個隊列賦予不同的優先級。第一個隊列的優先級最高,其他各隊列的優先權逐個降低 各個隊列中進程執行的時間片大小也各不一樣,在優先權越高的隊列中,每個進程的執行時間片就越小多級反響隊列調度的實施過程多級反響隊列調度的實施過程 新進程進入內存后,排在最高優先級隊列的末尾,按FCFS原那么等待調度。該進程執行時,假設它在一個時間片終了時髦未完成,調度程序便將該進程轉入下一個較低優先級隊列的隊尾 當一
9、個出息程從第一隊列依次降到第n隊列后,在第n隊列中便采取按時間片輪轉的方式運轉多級反響隊列調度的實施過程多級反響隊列調度的實施過程 調度時,總是先調度優先級高的隊列。僅當該隊列空時,才調度次高優先級隊列,以此類推,第n個隊列進程被調度時,必需是前n-1個隊列為空 假設處置機正在第i個隊列中為某進程效力時,又有新進程進入優先權較高的隊列,那么此時新進程將搶占正在運轉進程的處置機,由調度程序把正在運轉的進程放回到第i個隊列的末尾,把處置機分配給新到的進程多級反響隊列調度算法表示圖多級反響隊列調度算法表示圖就緒隊列就緒隊列1就緒隊列就緒隊列2就緒隊列就緒隊列3就緒隊列就緒隊列4至至CPU至至CPU至
10、至CPU至至CPUS1S2S3死鎖死鎖 在多道程序系統中,雖可經過進程的并發執行改善系統的資源利用率和提高處置才干,但也能夠引發一種危險死鎖。 死鎖(dead lock),是指多個進程因競爭資源而呵斥的一種僵局。假設無外力作用,這些進程將永遠不能向前推進。產生死鎖的緣由產生死鎖的緣由 競爭資源 進程推進順序非法資源分配圖資源分配圖 代表進程 代表資源 代表進程懇求資源 代表資源已分配給進程資源分配死鎖舉例資源分配死鎖舉例P1P2R1R2進程推進不當引發死鎖舉例進程推進不當引發死鎖舉例例如:兩個進程P1,P2 共享兩個系統資源R1和R2合法順序為:P1: Request(R1); P1: Req
11、uest(R2);P1: Release(R1); P1: Release(R2);P2: Request(R2); P2: Request(R1);P2: Release(R2); P2: Release(R1);非法順序為:P1: Request(R1); P2: Request(R2);P1: Request(R2); P2: Request(R1);產生死鎖的緣由產生死鎖的緣由 互斥條件 懇求和堅持條件 不剝奪條件 環路等待條件處置死鎖的根本方法處置死鎖的根本方法 預防死鎖 防止死鎖 檢測死鎖 解除死鎖預防死鎖的方法預防死鎖的方法 因產生死鎖須四個必要條件。假設能破壞其中的一個或幾個條
12、件,那么死鎖不發生。摒棄懇求和堅持條件摒棄懇求和堅持條件 系統要求一切進程一次性地懇求整個運轉過程中所需的全部資源。只需有一種資源要求不能滿足,也讓該進程等待 該方法的優點是簡單,容易實現,而且平安 缺陷是資源浪費嚴重,進程執行被延遲摒棄不剝奪條件摒棄不剝奪條件 系統要求一個曾經堅持了某些資源的進程,當它提出新的資源要求而不被滿足時,必需釋放它曾經堅持的一切資源,待以后再重新懇求 這種方法實現起來比較復雜,且要付出很大代價摒棄環路等待條件摒棄環路等待條件 系統將一切資源按類型排成線性隊列,并賦予不同的序號。一切進程懇求資源時必需嚴厲按資源序號遞增的順序提出。 這種處理方法使資源利用率和系統吞吐
13、量有明顯改善。 但對資源給予固定序號,將限制系統資源的擴展和程序編寫的自在。防止死鎖的方法防止死鎖的方法 該方法把系統的形狀分為平安形狀和不平安形狀。只需能使系統處于平安形狀,就可以防止死鎖的發生。平安形狀平安形狀 所謂平安形狀,系統能按某種順序如(P1, P2, , Pn),稱為平安序列,來為每個進程分配其所需資源,直至最大需求,使每個進程都可順利完成 假設系統不存在這樣一個平安序列,那么稱系統處于不平安形狀 防止死鎖的本質在于:如何使系統不進入不平安形狀銀行家算法銀行家算法 最有代表性的防止死鎖的算法,是Dijkstra提出的銀行家算法。該算法因用于銀行系統現金貸款的發放而得名。系統中必需
14、設置假設干數據構造。銀行家算法中的數據構造銀行家算法中的數據構造 可利用資源向量Available 最大需求數組Max 分配矩陣Allocation 需求矩陣Need 上述三個矩陣間存在下述關系: Needi,j=Maxi,j Allocationi,j銀行家算法的步驟銀行家算法的步驟設Requesti是進程Pi的懇求向量。(1)假設RequestiNeedi,那么轉向步驟(2);否那么報錯(2)假設RequestiAvailable,轉向步驟(3);否那么Pi等待(3)系統試探把資源分配給進程Pi,并修正下面的數值: Availablei=Availablei-Requesti Alloca
15、tioni=Allocationi+Requesti Needi=Needi-Requesti(4)執行平安性算法平安性算法的步驟平安性算法的步驟(1)設置兩個向量:任務向量Work和完成向量Finish(2)從進程集合中找到一個滿足以下條件的進程Pi: 1. Finishi=False 2.NeediWorki 假設能找到,執行步驟(3);否那么執行步驟(4) 平安性算法的步驟平安性算法的步驟(3)當進程Pi順利完成,并釋放資源,可執行: Worki=Worki+Allocationi Finishi=true go to step (2)(4)假設一切的Finishi=true,那么表示系
16、統處于平安形狀;否那么就是不平安形狀銀行家算法舉例銀行家算法舉例 假定系統中有五個進程P0, P1, P2, P3, P4和三類資源A,B,C,各類資源的數目分別是10、5、7。T0T0時辰的資源分配時辰的資源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P4 7 5 33 2 29 0 22 2 24 3 30 1 02 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 2銀行家算法舉例銀行家算法舉例l 利用平安性算法,T0時辰存在一個平安序列P1,P3,P4,P2,P0,故
17、系統是平安的。l P1懇求資源,懇求向量為Request1,0,2,那么資源分配如以下圖資源分配資源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 1 03 0 23 0 22 1 10 0 27 4 30 2 06 0 00 1 14 3 12 3 0銀行家算法舉例銀行家算法舉例l P4懇求資源,懇求向量為Request3,3,0,系統按銀行家算法進展檢查,可用資源不能滿足懇求資源, P4等待。l P0懇求資源,懇求向量為Request0,2,0 ,那么資源分配如以下圖資源分配資源分配MaxA B CAllocationA B CNeedA B CAvailableA B CP0 P1 P2 P3 P47 5 33 2 29 0 22 2 24 3 30 3 03 0 23 0 22 1 10 0 27 2 30 2 06 0 00 1 14 3 12 1 0銀行家算法舉例銀行家算法舉例l P4懇求系統按銀行家算法進展檢查,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 兒科病房心理護理指南
- 護理答辯匯報全攻略
- 企業數據資產化及數據資產入表白皮書
- 學前教育自我定位
- 健康鼻子的故事
- 【福州】2025年福建省閩江師范高等專科學校公開招聘緊缺急需高層次人才24名筆試歷年典型考題及考點剖析附帶答案詳解
- 【大連】2025年遼寧大連醫科大學附屬第二醫院招聘高層次人才163人筆試歷年典型考題及考點剖析附帶答案詳解
- 書包小學生課件圖片
- 攀枝花光伏逆變器項目可行性研究報告
- 敬仰英烈主題班會課件
- 五育并舉-立德樹人始于行潤品育心成于思
- 安全策略優化
- ANSYS Fluent:湍流模型理論與應用.Tex.header
- 《批判性思維原理和方法》全套教學課件
- 《道德經》的智慧啟示智慧樹知到期末考試答案章節答案2024年中國海洋大學
- 老公出軌保證書范文
- 【正版授權】 ISO 7887:1994 EN Water quality - Examination and determination of colour
- 獨家供應商協議
- 學術交流英語(學術寫作)智慧樹知到期末考試答案2024年
- 《建筑施工模板安全技術規范》JGJ162-2024解析
- 中年危機人生規劃
評論
0/150
提交評論