【正文】 不能繼續(xù)執(zhí)行時才釋放處理機。（2）短作業(yè)（進程）優(yōu)先調(diào)度算法可以分別用于作業(yè)調(diào)度和進程調(diào)度，短作業(yè)優(yōu)先（SJF）調(diào)度算法，是從后備對列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先（SPF）調(diào)度算法，是從就緒隊列中選出一估計運行時間最短的進程，將處理機分配給它。（3）時間片輪轉(zhuǎn)調(diào)度算法在時間片輪轉(zhuǎn)調(diào)度算法中，系統(tǒng)將所有就緒進程按到達時間的先后次序排成一個隊列，進程調(diào)度程序總是選擇隊列中的第一個進程執(zhí)行，并規(guī)定執(zhí)行一定時間，該時間稱為時間片。當該進程用完這一時間片時，系統(tǒng)將它送至就緒隊列隊尾，再把處理機分配給下一個就緒進程。這樣，處于就緒隊列中的進程，就可以依次輪流地獲得一個時間片的處理時間，然后回到隊列尾部，如此不斷循環(huán)，直至完成為止。（4）優(yōu)先級調(diào)度算法優(yōu)先級調(diào)度算法是一種常用的進程調(diào)度算法，其基本思想是把處理機分配給優(yōu)先級最高的進程，該算法的核心問題是如何確定進程的優(yōu)先級。進程的優(yōu)先級用于表示進程的重要性及運行的優(yōu)先性。進程優(yōu)先級通常分為兩種：靜態(tài)優(yōu)先級和動態(tài)優(yōu)先級。靜態(tài)優(yōu)先級是在創(chuàng)建進程時確定的，確定之后在整個進程運行期間不再改變。動態(tài)優(yōu)先級是指在創(chuàng)建進程時，根據(jù)進程的特點及相關(guān)情況確定—個優(yōu)先級，在進程運行過程中再根據(jù)情況的變化調(diào)整優(yōu)先級。基于優(yōu)先級的調(diào)度算法還可按調(diào)度方式不同分為非剝奪優(yōu)先級調(diào)度算法和可剝奪優(yōu)先級調(diào)度算法。非剝奪優(yōu)先級調(diào)度算法的實現(xiàn)思想是系統(tǒng)一旦將處理機分配給就緒隊列中優(yōu)先級最高的進程后，該進程便一直運行下去，直到由于其自身的原因(任務(wù)完成或等待事件)主動讓出處理機時，才將處理機分配給另一個更高優(yōu)先級的進程。可剝奪優(yōu)先級調(diào)度算法的實現(xiàn)思想是將處理機分配給優(yōu)先級最高的進程，使之運行。在進程運行過程中，一旦出現(xiàn)了另一個優(yōu)先級更高的進程時，進程調(diào)度程序就停止原運行進程，而將處理機分配給新出現(xiàn)的高優(yōu)先級進程。（5）高響應(yīng)比優(yōu)先調(diào)度算法此算法是先來先服務(wù)算法和短作業(yè)優(yōu)先算法的折衷，為每個作業(yè)引入一個動態(tài)優(yōu)先權(quán)（響應(yīng)比），使作業(yè)的優(yōu)先級隨著等待時間的增加而提高，響應(yīng)比的計算公式為：響應(yīng)比=（等待時間+要求服務(wù)時間）/要求服務(wù)時間（4）多級反饋隊列調(diào)度算法多級反饋隊列調(diào)度算法可以滿足各種類型進程的需要，是目前公認的一種較好的調(diào)度算法，實現(xiàn)思想如下：第一，設(shè)置多個就緒隊列，并為每個隊列賦予不同的優(yōu)先級。第1個隊列優(yōu)先級最高，第2個隊列次之，其余隊列的優(yōu)先級逐個降低。每個隊列中進程執(zhí)行的時間片大小也各不相同，進程所在隊列的優(yōu)先級越高，其相應(yīng)的時間片就越短。通常，第i+1個隊列的時間片是第i個隊列時間片的兩倍。第二，當一個新進程進入系統(tǒng)時，首先將它放入第一個隊列的末尾，按先來先服務(wù)的原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如能在此時間片內(nèi)完成，便可準備撤離系統(tǒng)；如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第二個隊列末尾，再同樣地按照先來先服務(wù)原則等待調(diào)度執(zhí)行；如果它在第二個隊列個運行一個時間片后仍未完成，再以同樣方法轉(zhuǎn)入第3個隊列。如此下去，最后一個隊列中使用時間片輪轉(zhuǎn)調(diào)度算法。第三，僅當?shù)谝粋€隊列空閑時，調(diào)度程序才調(diào)度第二個隊列中的進程運行；僅當?shù)?至(i1)個隊列均為空時，才會調(diào)度第i個隊列中的進程運行。當處理機正在為第i個隊列中的某進程服務(wù)時，若又有新進程進入優(yōu)先級較高的隊列中，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在執(zhí)行的進程放回第i個隊列末尾，重新將處理機分配給新進程。(三)進程同步1．進程同步的基本概念進程同步的主要任務(wù)：使并發(fā)執(zhí)行的諸進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。（1）進程間的兩種制約關(guān)系①間接相互制約關(guān)系。源于資源共享，同處于一個系統(tǒng)中的進程，必然共享某種系統(tǒng)資源，如共享CPU、共享I/O設(shè)備等，如兩個進程A和B，若系統(tǒng)已將惟一的打印機分配給B，此時如果A進程提出打印請求時，則進程A只能阻塞；一旦B將打印機釋放，才能使A進程由阻塞改為就緒狀態(tài)。此時進程同步的主要任務(wù)是保證諸進程能互斥地訪問臨界資源，為此，系統(tǒng)中的資源應(yīng)不允許用戶進程直接使用，而應(yīng)有系統(tǒng)統(tǒng)一分配。②直接相互制約關(guān)系。源于進程合作，此時進程同步的主要任務(wù)是保證相互合作的諸進程在執(zhí)行次序上的協(xié)調(diào)，不會出現(xiàn)與時間有關(guān)的差錯。（2）臨界資源和臨界區(qū)在計算機中有許多資源一次只能允許一個進程使用，我們把一次僅允許一個進程使用的資源稱為臨界資源。如打印機和一些共享變量。進程中訪問臨界資源的那段代碼稱為臨界區(qū)。（3）同步機制應(yīng)遵循的準則①空閑讓進。當沒有進程處于臨界區(qū)時，可以允許一個請求進入臨界區(qū)的進程立即進入自己的臨界區(qū)。②忙則等待。當已有進程進入自己的臨界區(qū)時，意味著相應(yīng)的臨界資源正被訪問，因而所有其他試圖進入臨界區(qū)的進程必須等待，以保證諸進程互斥地訪問臨界資源。③有限等待。對要求訪問臨界資源的進程，應(yīng)保證該進程能在有效時間內(nèi)進入自己的臨界區(qū)，以免陷入“死等”狀態(tài)。④讓權(quán)等待。當進程不能進入自己的臨界區(qū)時，應(yīng)立即釋放處理機，以免進程陷入“忙等”。2．實現(xiàn)臨界區(qū)互斥的基本方法臨界區(qū)互斥的實現(xiàn)既可以用軟件的方法，也可以用硬件的方法。下面對這兩種方法進行介紹。（1）軟件方法用軟件方法解決互斥和同步問題較復雜，為了說明將介紹的正確算法中某些變量設(shè)置的必要性，首先給出兩個不正確算法。1）不正確算法1兩個進程(P0，P1)共享一個公用變量turn，turn=i時進程Pi可進入臨界區(qū)。進程Pi的結(jié)構(gòu)如下：（turn初值為0或1無關(guān)緊要。i和j分別為0或1，i＝1—j。repeat while turn＜＞i do skip。 臨界區(qū)； turn：=j。 其他代碼；until false。該算法滿足互斥性要求，但它要求執(zhí)行臨界區(qū)的進程必須嚴格地交替進行，若turn=0且P1希望進入臨界區(qū)，盡管P0已用完并退出臨界區(qū)，該算法也不能讓P1進入其臨界區(qū)運行。2）不正確算法2不正確算法1的問題在于，它只記住了哪個進程允許進入它的臨界區(qū)，但沒有記錄每個進程的狀態(tài)。為了避免這種情況，可以用下面的數(shù)組來代替變量turn: var flag: array[0..1] of boolean。該數(shù)組的每個元素的初值均為false。若且flag[i]為turn，則表示進程Pi正在其臨界區(qū)執(zhí)行。進程Pi的一般結(jié)構(gòu)為： repeat while flag[j] do skip； flag[i]:＝true； 臨界區(qū)； flag[i]:＝false； 剩余區(qū)； untll false。這里，首先查看是否有另一進程在其臨界區(qū)中，若有則等待；否則置本進程的flag為true，并進入臨界區(qū)。當離開臨界區(qū)時，又置其flag為false，以允許另一進程進入其臨界區(qū)。然而該算法并未保證一次只有一個進程在其臨界區(qū)內(nèi)執(zhí)行。例如考慮以下執(zhí)行序列：T0：P0進入while語句并發(fā)現(xiàn)flag[1]＝false；T1：P1進入while語句并發(fā)現(xiàn)flag[0]＝false；T2：P1置flag[1]為true并進入臨界區(qū)；T3：P0置flag[0]為true并進入臨界區(qū)進入。于是，P0與P1都進入了臨界區(qū)，從而違反了互斥的要求。3）正確算法（只針對雙進程)該算法將上述兩種不正確算法中的有利思想結(jié)合在一起。進程間共享兩個共用變量： var flag：array[0..1] of boolean；turn：0..1；最初flag[0]＝flag[1]＝false，turn的初值是無關(guān)緊要的。進程Pi的一般結(jié)構(gòu)為： repeat flag[i]:=true。turn:=j。； while(flag[j] and turn=j) do skip。 臨界區(qū)； flag[i]:= false。 剩余區(qū)； until false；(2)硬件方法解決互斥問題：1）中斷屏蔽方法當一個進程正在使用處理器執(zhí)行它的臨界區(qū)代碼時，要防止其他進程再進入其臨界區(qū)訪問的最簡單方法是禁止一切中斷發(fā)生，或稱之為屏蔽中斷、關(guān)中斷。因為CPU只在發(fā)生中斷時引起進程切換，屏蔽中斷就能保證當前運行進程將臨界區(qū)代碼順利地執(zhí)行完，從而保證了互斥的正確實現(xiàn)，然后再開中斷。下面是用中斷屏蔽方法實現(xiàn)互斥的典型模式：…關(guān)中斷；臨界區(qū)；開中斷；…并關(guān)中斷方法來實現(xiàn)過程間互斥，既簡單又有效。但它存在一些不足，如該法限制了處理器交替執(zhí)行程序的能力，其執(zhí)行的效率將會明顯降低；對于核心來說，當它在執(zhí)行更新變量或列表的幾條指令期間將中斷關(guān)掉是很方便的，但將關(guān)中斷的權(quán)力交給用戶進程則很不明智，若—個進程關(guān)中斷之后不再開中斷，則系統(tǒng)可能會因此終止。2）硬件指令方法許多計算機中都提供了專門的硬件指令，完成對一個字或字節(jié)中的內(nèi)容進行檢查和修改，或交換兩個字或字節(jié)的內(nèi)容的功能。用一條指令來完成對共享變量的檢查和修改兩個功能，這樣中斷不可能發(fā)生，所以不會影響共享變量數(shù)據(jù)的完整性。實現(xiàn)這種功能的硬件指令有兩種：①TS(Testandset)指令。該指令的功能是讀出指定標志后把該標志設(shè)置為真。boolean TS(boolean *lock){boolean old；old=*lock；*lock=true；return old。}為了實現(xiàn)多個進程對臨界資源的互斥訪問，可以為每個臨界資源設(shè)置一個共享的布爾變量lock，表示資源的兩種狀態(tài)：true表示正被占用，false表示空閑，初值為false。在進程訪問臨界資源之前，利用TS檢查和修改標志lock；若有進程在臨界區(qū)，則重復檢查，直到其他進程退出。利用TS指令實現(xiàn)進程互斥的算法可描述為： While TS(＆lock)； 進程的臨界區(qū)代碼CS； Lock=false； 進程的其他代碼；②swap指令。該指令的功能是交換兩個字或字節(jié)的內(nèi)容，描述如下： Swap(boolean *a，boolean *b) { Boolean temp； temp＝*a； a=*b； *b=temp；}利用swap指令實現(xiàn)進程互斥時，應(yīng)為每個臨界資源設(shè)置一個共享布爾變量lock，初值為false；在每個進程中再設(shè)置一個局部布爾變量key，用于與lock交換傳息。在進入臨界區(qū)之前利用swap指令交換lock與key的內(nèi)容，然后檢查key的狀態(tài)；若有進程在臨界區(qū)時，重復交換和檢查過程，直到其他進程退出。利用swap指令實現(xiàn)進程互斥的算法描述為：key＝true；while (key!＝false) swap(＆lock，amp。key)；進程的臨界區(qū)代碼CS；lock＝false；進程的其他代碼；3．信號量荷蘭學者Dijkstral965年提出的信號量機制是一種卓有成效的進程同步工具。在長期且廣泛的應(yīng)用中，信號量機制又得到了很大的發(fā)展，它從整型信號量經(jīng)記錄型信號量，進而發(fā)展為“信號量集”機制。（1）整型信號量機制整型信號是—個整型量，除初始化外，僅能通過兩個標準的原子操作wait(s)和signal(s)來訪問。這兩個操作很長時間以來一直被分別稱為P、V操作。Wait和signal操作可描述為：Wait(s)：while (s≤0) noop。 s。 signal(s)： s++；整型信號量的主要問題是，只要s≤0，wait操作就會不斷地測試，因而沒有做到“讓權(quán)等待”。（2）記錄型信號量機制在記錄型信號量中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進程鏈表L．用于鏈接上述的所有等待進程。typedef struct { int value； 1ist of proces s *L；}semaphore；相應(yīng)的wait和signal操作可描述為：void wait(static semaphore s){ ； if (＜0) block()；}void signal(static semaphore s){ ++； if (＜=0) wakeup()；}在記錄型信號量機制中，因而又稱為資源信號量，每次的wait操作意味著進程請求一個單位的資源，；＜0時，表示資源己分配完畢，因而進程調(diào)用block原語，進行自我阻塞?？梢?，該機制遵循了讓權(quán)等待準則。每次signal操作，表示執(zhí)行進程釋放一個單位資源．++操作表示資源數(shù)目加1。＜=0，則表示在該信號鏈表中仍有等待該資源的進程被阻塞，故還應(yīng)調(diào)用wakeup喚醒進程。，則此時的信號量轉(zhuǎn)化為互斥信號量。(3)信號量的應(yīng)用1）利用信號量實現(xiàn)互斥為使多個進程能互斥地訪問某個臨界資源，只需為該資源設(shè)置—個互斥信號量mutex，并將其初值設(shè)置為1，然后將訪問該資源的臨界區(qū)置于wait(mutex)和signal(mutex)之間。下面的算法描述了如何利用信號量實現(xiàn)進程P1和P2的互斥，信號量mutex的初值為1。P1進程 P2進程… …wait(mutex)； wait(mutex)；critical section； critical section；signal(mutex)； signal(mutex)； … …2）利用信號量實現(xiàn)前趨關(guān)系若干進程為了完成一個共同任務(wù)而并發(fā)執(zhí)行。然而，這些并發(fā)進程之間根據(jù)邏輯