計算機硬件—調度與死鎖

進程調度原因及調度切換時機,進程調度方式與實現及各種調度算法的個人總結:

1.一般調度概念 1)什麼是調度 就是選出待分派的作業或進程。 操作系統管理了系統的有限資源,當有多個進程(或作業)發出請求要使用這些資源時,因為資源的有限性,必須按照一定的原則選擇進程(或作業)來佔用資源。這就是調度。

2)調度目的 1.控制資源使用者的數量 2.選取資源使用者 3.許可哪些使用者佔用資源 4.讓使用者直接佔用資源。

二、調度類型 1、高級調度(長程調度)。 即作業調度,選取輸入井中的作業,生成根進程。目的是控制使用系統資源的進程數。

2、中級調度(中程調度)。 指選取進程佔用內存或有資格佔用內存,又稱進程滾入滾出,中級調度將在存儲管理章節中介紹,有頁式調度、段式調度、段頁式調度等。

3、低級調度(短程調度) 指選取進程佔用處理機,又稱進程調度。 4、I/O調度 選取進程佔用I/O設備。

三、調度和狀態轉換 在許多系統中,調度被分為三種:長程、中程和短程。 1)調度和進程狀態轉換

 

從狀態轉換的觀點: 1、長程調度(作業調度)就是將一個或一批作業從後備狀態變為運行狀態。一個作業一旦被高級調度選中,便可獲得所需要的基本內存和設備資源,並被裝入內存,此後就以進程形式參与併發執行,與其它進程競爭CPU。

從狀態轉換的觀點: 2、中程調度就是將進程從活動態變為靜止的掛起態,或者將進程從掛起態變為就緒或阻塞態。 3、短程調度就是將某個進程從就緒態變為(在CPU上運行的)執行態。

2)調度的層次(調度作用的嵌套關係)

 

 

 

3)三級調度示意圖 調度從根本上講,是要使隊列延遲的時間最小,並優化系統的執行效率

 

 

 

 

 

 

 

4.1.2作業調度的功能

①記錄系統中各個作業的情況。 ②按照某種調度算法從後備作業隊列中挑選作業,即決定接納多少個作業進入內存和挑選哪些作業進入內存。

③為選中的作業分配內存和外設等資源。 ④為選中的作業建立相應的進程,並把該進程放入就緒隊列中。 ⑤作業結束後進行善後處理工作。如輸出必要的信息,收回該作業所佔用的全部資源,撤消與該作業相關的全部進程和該作業的JCB 。

 

4.1.3進程調度的功能與調度時機 一、進程調度的功能 (1)保存現場(2)挑選進程(3)恢復現場

 

 

 

二、進程調度的時機 一般在下列事件發生后要執行進程調度。 (1)創建進程。 當進程創建時,要決定是運行父進程還是子進程。 (2)進程終止。 (3)等待事件。 (4)中斷髮生。 (5)運行到時。

4.1.4進程調度的基本方式 1)非剝奪調度(非搶佔) 只有當處理機上的進程主動放棄處理機時,才重新調度。 2)剝奪調度(搶佔) 當進程運行時可以被系統以某種原則為由剝奪其處理機。

例:只有一部電話機,小李正在通電話,此時小張有急事也要打電話,此時小張的調度方式有兩種: 一種是非搶佔,即等待小李打完電話,自己再打電話。 另一種是搶佔,不等小李通完電話,搶過話筒就撥打電話。

3)進程調度在核心態進行。 CPU狀態有兩種,目態和管態。 管態——也稱核心態或系統態,系統程序在CPU上運行的狀態。 目態——用戶程序在CPU上運行的狀態。

 

 

 

4.2 調度算法 4.2.1 常用的調度算法

1. FCFS 誰先到就緒隊列就將處理機分給誰。 2. 短作業優先 取一個下次所需運行時間最短的作業(該算法能使平均等待時間最短)。

3. 優先級調度 選優先級最高的進程佔用處理機(優先級可動態改變)。 4.輪轉調度法 以先來後到的次序+ 時間片輪轉。

5.多隊列調度法 按屬性將就緒進程分類,不同類進程可有不同的調度算法。 6.多級反饋隊列調度法 設置多條就緒隊列,進程被調度執行后,在被剝奪或放棄處理機后而在就緒時,可以改變其就緒隊列(見下圖)。

 

 

又一個多級反饋隊列調度算法的例子:使用優先權實現調度。做法如下:

(1)以優先級設置多隊列。 (2)各隊列的調度算法採用FCFS+時間片輪轉. (3)進程優先級升降原則是:等待過久升,輸入/輸出完成時升,運行完一個完整時間片降……

(4)進程最初進入就緒隊列以用戶初置優先級為參數。 (5)開始調度時,先從最高優先權的就緒隊列(RQ0)開始選取一個進程,如果RQ0空,則檢查RQ1,如此下去。見下圖示:

 

 

4.2.2 調度策略的討論

一、調度性能評價準則 1、CPU利用率。 2、吞吐率。即每單位時間所完成的作業數目。 3、周轉時間。即從作業提交直至完成這一作業的時間間隔。

4、等待時間。即作業在就緒隊列中等待所花的時間。 5、響應時間。即從作業提交到首次產生回答信息之間的時間。

二、主要的調度算法 下面以表所示的進程集作為範例討論不同的調度策略。 到達時間:進程或作業提交時間。 服務時間:進程要求服務的時間,或完成作業所需的時間。

 

一、FCFS調度策略(或先進先出)

 

 

 

 

 

 

 

FCFS策略更適合於長進程。例:

 

 

注:周轉時間=完成時間—到達時間 tq/ts :帶權周轉時間=周轉時間/服務時間

(1)進程C的等待標準化時間是不能容忍的。它位於系統的總時間是它所需服務時間的100倍。無論何時,一個長進程到后,一個短進程就會出現較長的等待。 (2)進程D的標準化等待時間尚可容忍,小於2.0。進程D的輪轉時間差不多是C的兩倍。

總結: FCFS(First Come First Served)即先來先服務,故它的本質是非搶佔的。它簡單易行,但調度性能較差,有可能使短的、重要的或緊迫的作業等進程長期等待,其實現過程容易,可採用FIFO隊列管理。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

台北網頁設計公司這麼多,該如何挑選?? 網頁設計報價省錢懶人包"嚨底家"

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※想知道購買電動車哪裡補助最多?台中電動車補助資訊懶人包彙整

南投搬家費用,距離,噸數怎麼算?達人教你簡易估價知識!