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