【正文】 　3秒，P3　 3秒如果進(jìn)程以PPP3 的順序到達(dá)，并且以FCFS 規(guī)則服務(wù)，我們將獲得如下的甘特圖：　　　　　　　　　P1P2P30 　　　　　　　　　　　 24 　　　27 　　　　 30P1 的等待時間是0 毫秒，進(jìn)程P2 是24 毫秒，P3 是27 毫秒。這樣，平均時間是(0 + 24 + 27)/3 = 17毫秒。優(yōu)點(diǎn)：它簡單易行缺點(diǎn)：調(diào)度性能較差，有可能使短的進(jìn)程長期等待長的進(jìn)程（護(hù)送效應(yīng)）。它有利于偏重CPU的進(jìn)程，不利于偏重I/O的進(jìn)程。（2）短作業(yè)優(yōu)先調(diào)度算法（SJF）—— 搶占式的／非搶占式的。當(dāng)CPU 有效時，它將被賦給下一個CPU burst 最小的進(jìn)程。例如：進(jìn)程 Burst 時間　　P1　 6秒；P2 　　8秒；P3　 7秒；P4 　3秒　用SJF 調(diào)度，我們將依照如下的甘特圖來調(diào)度這些進(jìn)程：P4P1P3P20 　3　　　　　　9　　　　　16　　　　　　 　24P1 的等待時間是3 毫秒，P2 是16 毫秒，P3 是9 毫秒，P4 是0 毫秒。因而，平均等待時間是(3 + 16 + 9 +0)/4 =7 毫秒。如果使用FCFS 調(diào)度策略，那么平均等待時間是（0+6+14+21）/4＝ 毫秒。新進(jìn)程的下一個CPU burst 可能會比當(dāng)前執(zhí)行進(jìn)程的剩余量短。在搶占式SJF 算法中，新進(jìn)程搶占當(dāng)前的進(jìn)程；而非搶占式SJF 算法允許當(dāng)前運(yùn)行的進(jìn)程結(jié)束其CPU burst．例如：Process 　　Arrival Time　　　　 Burst Time　　　　P1　　　　 0 　　　　　　　　　　8　　　　P2 　　　　1 　　　　　　　　　　4　　　　P3 　　　　2 　　　　　　　　　　9　　　　P4 　　　　3 　　　　　　　　　　5按照搶占式SJF 調(diào)度會產(chǎn)生如下的結(jié)果：P1P2P4P1P30　 1 　　5 　 　10 　　 17 　　　　　26P2 在時間1 到達(dá)。進(jìn)程P1 的剩余時間大于進(jìn)程P2的時間需求（4 毫秒），所以進(jìn)程P1 被搶占，P2 被調(diào)度。這個例子的平均等待時間是((10 1) + (1 1) + (17 2) + (5 3))/4 = 26/4 = 毫秒（被調(diào)度時間減去到達(dá)的時間）。而采用非搶占式SJF 調(diào)度的平均等待時間為（（00）+（81）+（123）＋（172））/ 4 ＝ 毫秒（p1,p2,p4,p3）. 優(yōu)點(diǎn)：可證明SJF 調(diào)度算法是最佳的算法，因?yàn)樗鼮橹付ǖ倪M(jìn)程組給出了最小的平均等待時間。對短作業(yè)或短進(jìn)程最為有利。缺點(diǎn)：對長作業(yè)不利，特別是在搶占方式下，可能會使長作業(yè)無限延遲。而且實(shí)際上無法預(yù)測下一CPU瞬時段的長度。（3）優(yōu)先級調(diào)度算法 —— 搶占式的／非搶占式的為每個進(jìn)程賦予一個優(yōu)先權(quán)，把CPU 分配給擁有最高優(yōu)先權(quán)的進(jìn)程。缺點(diǎn)：優(yōu)先調(diào)度算法可能導(dǎo)致一些低優(yōu)先權(quán)進(jìn)程無限的等待CPU（即無限阻塞）解決一個方法是老化（aging））是指逐漸地提高在系統(tǒng)中長時間等待的進(jìn)程的優(yōu)先權(quán)。（4）輪轉(zhuǎn)調(diào)度算法（RR）—— 搶占式的ＣＰＵ分配給每一個進(jìn)程一段時間，到時間輪轉(zhuǎn)到下一個進(jìn)程。若需要CPU 的時間 分配的時間量——自己釋放CPU，等待下一次輪轉(zhuǎn)；若需要CPU的時間 分配的時間量——進(jìn)程一結(jié)束就釋放CPU，讓給下一個進(jìn)程使用。（5）多級隊列調(diào)度算法就緒隊列劃分為多個獨(dú)立的隊列。每個隊列有自己的調(diào)度算法。進(jìn)程不會在隊列間移動。在隊列間進(jìn)行調(diào)度，這種調(diào)度通常實(shí)現(xiàn)為權(quán)限固定的搶占式調(diào)度或采用時間片機(jī)制。（6）多級反饋隊列調(diào)度算法 —— 搶占式的它綜合考慮了多種因素，根據(jù)進(jìn)程運(yùn)行情況的反饋信息動態(tài)改變進(jìn)程的優(yōu)先級，按優(yōu)先級別組織設(shè)置了規(guī)定CPU時間片的各就緒隊列；對同一隊列中的各就緒進(jìn)程按FCFS或RR算法調(diào)度。優(yōu)點(diǎn)：這種策略不必事先知道各種進(jìn)程所需的執(zhí)行時間，而且還可以滿足各種類型進(jìn)程的需要。如果一個CPU 占用了太多的CPU 時間，它將被移動到優(yōu)先權(quán)更低的隊列（lowerpriority queue）。這種策略把I/O 繁忙型進(jìn)程和交互式進(jìn)程放置到優(yōu)先權(quán)更高的隊列（higherpriority queue）?！　　☆愃频?，一個在低優(yōu)先權(quán)隊列中等待太久的進(jìn)程可能會被移動到一個更高優(yōu)先權(quán)的隊列。這種老化形式避免了饑餓的發(fā)生。例如：進(jìn)入就緒隊列的進(jìn)程被放到隊列0。隊列0 中的進(jìn)程被指定一個8 毫秒的時間量。如果它不能在這個時間內(nèi)完成，將被移動到隊列1 的隊尾。如果隊列0 是空的，那么隊列1 頭部的進(jìn)程被指定一個16 毫秒的時間量。如果它不能完成，將被搶占并被放入隊列2。隊列2 中的進(jìn)程只有當(dāng)隊列0 和1 為空時以FCFS原則運(yùn)行。調(diào)度準(zhǔn)則（1）CPU利用率（越大越好）?。?）吞吐量（越大越好）（3）周轉(zhuǎn)時間：從進(jìn)程提交到進(jìn)程完成的時間間隔（越小越好）（4）反應(yīng)時間：從進(jìn)程提交請求到首次產(chǎn)生響應(yīng)的時間（越小越好）（5）等待時間：在就緒隊列中等待的時間（越小越好）第7章 進(jìn)程同步進(jìn)程為什么需要同步和互斥（1）進(jìn)程的同步：一個進(jìn)程運(yùn)行到某一點(diǎn)時要求另一伙伴進(jìn)程為它提供消息，在未獲得消息之前，該進(jìn)程處于等待狀態(tài)，獲得消息后被喚醒進(jìn)入就緒態(tài)。（2）進(jìn)程的互斥：由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競爭使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥。信號量的含義信號量表示資源，初始化值非負(fù)。是用于解決進(jìn)程間同步與互斥的通信量。信號量ｓ= 0時，ｓ表示可用資源的數(shù)量。執(zhí)行一次wait（P）操作意味著請求分配一個單位資源，因此ｓ的值減1；當(dāng)ｓ 0時，表示已經(jīng)沒有可用資源。請求者必須等待別的進(jìn)程釋放該資源，它才能運(yùn)行。而執(zhí)行一個signal（V）操作意味著釋放一個單位資源，因此ｓ加1。若ｓ= 0，表示某些進(jìn)程正在等待資源。因此要喚醒一個等待狀態(tài)的進(jìn)程，使之運(yùn)行下去。臨界資源： 系統(tǒng)中某些資源一次只允許一個進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。臨界區(qū)（互斥區(qū)）：在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)。信號量和自懸鎖的區(qū)別（1）自懸鎖：當(dāng)一個進(jìn)程處于臨界區(qū)時，其它進(jìn)程持續(xù)循環(huán)等待。繁忙等待浪費(fèi)了CPU 周期，本來其它進(jìn)程可以有效利用這些時間。在多處理機(jī)系統(tǒng)中非常有用。自旋鎖的優(yōu)點(diǎn)是：當(dāng)期望短時間持有鎖時，自旋鎖很有用。（小王一直等著別人出來，自己不去睡覺）（2）信號量：為了克服對繁忙等待的需求，我們修改wait 和signal 信號量操作的定義。當(dāng)一個進(jìn)程執(zhí)行wait 操作且信號量不為正時，它必須等待。然而，進(jìn)程可以阻塞自身，而不是繁忙等待。block 操作將一個進(jìn)程置入與該信號量關(guān)聯(lián)的等待隊列中并將進(jìn)程狀態(tài)設(shè)為等待。（小王可以去睡覺，等別人喚醒）經(jīng)典的同步互斥問題（1）生產(chǎn)者消費(fèi)者問題① 一個生產(chǎn)者，多個消費(fèi)者，公用一個緩沖區(qū)。定義兩個同步信號量Empty——表示緩沖區(qū)空否　　　初始值為1（根據(jù)緩沖區(qū)個數(shù)來設(shè)置）Full——表示緩沖區(qū)滿否　　　　初始值為0生產(chǎn)者進(jìn)程While(True ){生產(chǎn)一個產(chǎn)品；　　P(empty)。 // empty1　產(chǎn)品送往buffer。 　V(full)。 // 喚醒消費(fèi)者，full+1} 消費(fèi)者進(jìn)程While(True ){ 　P(full)。 // 看是否有