****** 九 ******、軟設筆記【作業系統】-處理機管理（一）-死鎖

一、作業系統定義

操作

系統是直接控制和管理計算機硬體、軟體資源、合理地對各類作用進行排程，以友善使用者使用的程式集合。

四、作業系統分類

*批處理作業系統

*分時作業系統

*實時作業系統

*網絡作業系統

*分布式作業系統

五、作業系統的功能

*處理機管理功能

*存儲器管理功能

*裝置管理功能

*檔案管理功能

*使用者接口

OS定義：OS是直接控制和管理計算機硬體、軟體資源，合理地對各類作業進行排程，以友善使用者使用的程式集合

處理機管理（程序管理）

一、程序的定義

程序：程式關于某個資料集合的一次執行過程。

1.程序的特征（與程式比較）

(1)結構特征

程序控制塊（PCB） + 程式 + 資料 = 程序實體

(2)動态性--最基本特征

程序：經程實體的一次執行過程，有生命周期。

程式：程式是一組有序指令的集合，是靜态的概念。

2.程序的三種基本狀态

（1）就緒狀态（ready）

程序已獲得除CPU之外的所有必需的資源，一旦得到CPU控制權，立即可以運作。

（2）運作狀态（Runing）

程序已獲得運作所必需的資源，它正在處理機上執行。

（3）阻塞狀态（Blocked）

正在執行的程序由于發送某事件而暫時無法執行時，便放棄處理機而處于暫停狀态，稱該程序處于阻塞狀态或等待狀态。

3.程序的五種狀态

引入挂起狀态後，增加了挂起狀态（靜止狀态）到非挂起狀态（活動狀态）的轉換，或者相反

二、程序互斥與同步

1.程序間兩種形式的制約關系

(1)間接互相制約關系 --- 源于資源共享

(2)直接互相制約關系 --- 源于程序合作

2.臨界資源

*臨界資源（Critical Resource）：把一段時間内隻允許一個程序通路的資源稱為臨界資源或獨占資源

*臨界區（Critical Section）：每個程序中通路臨界資源的那段代碼稱為臨界區

三、信号量機制

*信号量是OS提供的管理公有資源的有效手段。

*信号量是一個整數，當信号量大于等于零時，代表可供并發程序使用的資源數量，當信号量小于零時，表示處于阻塞态程序的個數。

Wait操作：

*申請資源，減量操作，S.value := S.value - 1

*當S.value < 0時，表示資源配置設定完了，進行自我阻塞。

Signal操作：

*釋放資源，增量操作，S.value := S.value + 1

*當S.value <= 0，喚醒S.L連結清單中的等待程序。  

四、信号量的應用

1.利用信号量實作程序互斥（模式）

為使多個程序互斥的通路某臨界資源，必須為該資源設定一互斥信号量mutex，并設其初始值為1，然後将各程序通路資源的臨界區cs置于wait（mutex）和signal（mutex）之間即可。

2.利用信号量實作前驅關系（模式）

設有兩個并發執行的程序P1和P2，P1中有語句S1，P2中有語句S2，希望在S1執行後在執行S2.

使程序P1和P2共享一個公用信号量S，并賦予其初值為0. 

3.利用記錄型信号量實作同步（模式）

P1，P2兩個程序因合作完成一項任務而公用一個變量x。

程序P2将處理結果送入x；程序P1将x的結果列印。

五、程序排程

也稱短程排程（Short-Term Scheduling），用來決定就緒隊列中的哪個程序應獲得處理機，然後再由分派程式把處理機配置設定給該程序。

為最基本的一種排程，三種類型OS中都必須有程序排程。

程序排程可采用下述兩種排程方式：

*非搶占方式（Non-preemptive Mode）

一旦把處理機配置設定給某程序後，便讓該程序一直執行，直至該程序完成或發生某事件而被阻塞時，才把處理機配置設定給其他程序，決不允許程序搶占已經配置設定出去的處理機。

*搶占方式(Preemptive Mode)

允許排程程式根據某種原則，去暫停某個正在執行的程序，将處理機重新配置設定給另一程序。

搶占的原則：

*時間片原則：個程序按時間片運作，一個時間片用完時，停止該程序執行重新進行排程。

*短作業（程序）優先原則：短作業（程序）可以搶占長作業（程序）的處理機。

*優先權原則：優先權高的搶占優先權低的進的處理機。

六、排程算法

1.先來先服務

是一種最簡單的排程算法，既可以用于作業排程，也可用于程序排程。

程序排程采用FCFS算法時，每次排程都從就緒隊列中選擇一個最先進入該隊列的程序，為之配置設定處理機，使之運作。

*FCFS算法比較有利于長作業（程序），而不利于短作業（程序）。

2.短作業（程序）優先排程算法

對短作業或短程序優先排程的算法。可以分别用于作業排程和程序排程。

*短作業優先（SJF）的排程算法：從後備隊列中選擇一個或若幹個估計運作時間最短的作業，将它們調入記憶體運作。

*短程序優先（SPF）排程算法，是從就緒隊列中選出一估計運作時間最短的程序，将處理機配置設定給它，使它立即執行。

SJF排程算法的優缺點：

優點：有效的降低作業的平均等待時間，提高系統吞吐量。

缺點：對長作業不利。

*該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業（程序）會被及時處理。

*由于作業(程序)的長短隻是根據估計執行時間定的，主觀因素較大，不一定能真正做到短作業優先。

3.高優先權優先排程算法

為了照顧緊迫性作業，使之在進入系統後便獲得優先處理，引入了最高優先權優先（FPF）排程算法。

此算法常用于批處理系統中，作為作業排程算法，也作為多種作業系統中的程序排程算法，還可用于實時系統中。

(1)優先權的類型

對于最高優先權優先排程算法，關鍵在于：使用靜态優先權、動态優先權；如何确定程序的優先權。

*靜态優先權：在建立程序時确定的，在程序的整個運作期間保持不變，利用某一範圍的整數來表示（0~7），又稱為優先數。

*動态優先權：在建立程序時所賦予的優先權可以随程序的推進或随其等待時間的增加而改變。

（2）高響應比優先排程算法

在批處理系統中，短作業優先算法是一種比較好的算法，器主要不足是長作業的運作得不到保證。我們為每個作業引入動态優先權，并使左作業的優先級随着等待時間的增加而以速率a提高，則可解決問題，見下式：

優先權 = （等待時間 + 要求服務時間）/要求服務時間

由于等待時間與服務時間之和就是系統的響應時間，故上式又可以表示為：Rp = 響應時間/要求服務時間

由上式可以看出：

*如作業等待時間相同，則要求服務的時間越短優先權越高，是以該算法利于短作業。

*當要求服務的時間相同，作業優先權的高低決定于其等待時間的長短，是以是先來先服務。

*對于長作業，作業的優先級可以随等待時間的增加而提高，當其等待時間足夠長也可獲得處理機。

4.時間片輪轉排程算法

是一種最古老，最簡單，最公平且使用最廣的算法。每個程序配置設定一個時間段，稱作它的事件片，即該程序允許運作的時間。

*如果在時間片結束時，程序還沒有運作結束，則cpu将被剝奪并配置設定給另一個程序，該程序到就緒隊列尾重新排隊。

*如果程序在時間片内阻塞或結束，則CPU當即進行切換。