OS-03中斷與處理機調(diào)度

操作系統(tǒng)原理金海溶blue1879@163.com辦公室：JK329第3章處理器調(diào)度處理器調(diào)度的類型調(diào)度算法Linux進程調(diào)度Windows2000/xp線程調(diào)度中斷中斷：在進程運行過程中出現(xiàn)某種緊急情況，必須中止當前正在運行的程序，轉(zhuǎn)去處理其它事件，處理完畢后恢復原來程序的運行。中斷系統(tǒng)：中斷裝置+中斷處理程序中斷分類：內(nèi)中斷和外中斷；硬中斷和軟中斷；可屏蔽中斷和不可屏蔽中斷；強迫性中斷和自愿性中斷P49-59：選擇性自學第3章處理器調(diào)度操作系統(tǒng)必須為多個進程可能有競爭的請求分配計算機資源。對處理器而言，可分配的資源是在處理器上的執(zhí)行時間，分配途徑是調(diào)度處理器調(diào)度：指采用合理的策略和方法在多個可運行實體間分配CPU資源。處理器調(diào)度算法：按照什么原則和方法分配處理器資源處理機調(diào)度必須設(shè)計成可以滿足多個目標，例如公平、任何進程都不會餓死、有效地使用處理器時間和低開銷等調(diào)度算法設(shè)計指標面向用戶準則所關(guān)心的性能指標周轉(zhuǎn)時間

T

:指一個進程從提交到完成之間的時間間隔，包括實際執(zhí)行時間加上等待時間（等待+就緒）。帶權(quán)的周轉(zhuǎn)時間W：周轉(zhuǎn)時間與執(zhí)行時間的比值響應時間從提交一個請求到開始處理的時間間隔。最后期限當可以指定進程完成的最后期限時，調(diào)度原則將服從于其他目標，使得距最后期限最近平均周轉(zhuǎn)時間：p61平均帶權(quán)周轉(zhuǎn)時間：p61面向系統(tǒng)準則所關(guān)心的性能指標吞吐量單位時間內(nèi)完成的任務數(shù)。調(diào)度策略將試圖使得每個時間單位完成的進程數(shù)目最大。處理器使用率處理器忙的時間百分比。盡量是CPU處于繁忙狀態(tài)。公平進程應該被平等對待，沒有一個進程會被餓死強制優(yōu)先級當進程被指定了優(yōu)先級，調(diào)度策略會先選擇高優(yōu)先級的進程平衡資源保持系統(tǒng)中所有資源忙。這個準則也可用于中程調(diào)度和長程調(diào)度調(diào)度算法設(shè)計指標處理器調(diào)度的類型（級別）多道程序的關(guān)鍵是調(diào)度。典型的調(diào)度類型有：長程調(diào)度(作業(yè)調(diào)度,高級調(diào)度）決定加入到待執(zhí)行的進程池中中程調(diào)度（交換調(diào)度,中級調(diào)度）將進程調(diào)入內(nèi)存,或者將進程交換到硬盤短程調(diào)度（進程調(diào)度，低級調(diào)度）決定哪一個就緒進程將被處理器執(zhí)行線程調(diào)度：決定哪一個線程被處理器執(zhí)行就緒/掛起新建就緒運行退出阻塞短程調(diào)度阻塞/掛起中程調(diào)度長程調(diào)度長程調(diào)度中程調(diào)度下一次允許哪一個進程進入的決策可以基于簡單的先來先服務原則，或者也可以基于管理系統(tǒng)性能的工具使用的原則包括優(yōu)先級、期待執(zhí)行時間和I/O需求同樣，可以根據(jù)請求哪個I/O資源和試圖平衡I/O使用的目的進行決策長程調(diào)度中程調(diào)度的目標有2個：解決內(nèi)存資源緊張的矛盾減小并發(fā)度以降低系統(tǒng)開銷

中程調(diào)度算法將結(jié)合存儲管理來設(shè)計。中程調(diào)度從執(zhí)行的頻率看長程調(diào)度程序的執(zhí)行頻率相對低些，并且僅僅是粗略地決定是否接受新進程以及接受哪一個為進行交換決策，中程調(diào)度程序執(zhí)行得略微頻繁一些短程調(diào)度程序，即分派程序執(zhí)行得最頻繁，并且精確地決定下一次執(zhí)行哪一個進程短程調(diào)度根據(jù)已占有處理機的進程是否可被剝奪這一原則，調(diào)度方式（策略）可分為：非剝奪方式：一旦某個就緒進程分得處理機之后，只要不是其自身的原因被阻塞(如要求I/O操作)而不能繼續(xù)運行時，就一直運行下去，直至運行結(jié)束缺點：緊急進程無法立即運行，實時性差；短進程周轉(zhuǎn)時間長，公平性差。進程調(diào)度方式剝奪方式：當一個正在運行的進程沒有運行完時，系統(tǒng)采取某種手段強行剝奪已分配給該進程的處理器資源。而被剝奪的進程重新回到就緒隊列中等待在剝奪方式下，可以通過剝奪處理器所有權(quán)的方式，暫停當前進程的運行，已滿足更緊急進程的處理要求。進程調(diào)度方式進程調(diào)度方式有三個進程p1，p2，p3到達時間為：0，3，4，優(yōu)先級依次增高，運行所需的時間分別為20，4，2，假設(shè)現(xiàn)按優(yōu)先級策略調(diào)度執(zhí)行，并且不采用時間片原則，請分別求出非剝奪方式和剝奪方式下各個進程的周轉(zhuǎn)時間。P1（20）P3(2)P2(4)周轉(zhuǎn)時間：p1＝20；p2＝23；p3＝18P1（17）P3(2)P2(1)P1(3)P2(3)周轉(zhuǎn)時間：p1＝26；p2＝6；p3＝2當時間片為5時，采用優(yōu)先級策略，問非剝奪和剝奪方式下，求各進程的周轉(zhuǎn)時間和響應時間先來先服務(FCFS——FirstComeFirstService)按照進程就緒的先后順序來調(diào)度進程，到達的越早，其優(yōu)先級越高獲得處理機的進程，在未遇到其他情況時一直運行下去——采用的是非剝奪方式FCFS算法具有公平的特點，不會發(fā)生餓死。但短進程的等待時間長，平均周轉(zhuǎn)時間長調(diào)度算法p61最短進程SPN（短進程優(yōu)先調(diào)度算法）減少FCFS固有的對長進程的偏愛的另一種方法是最短進程(SPN)策略，這是一種非剝奪的策略，其原則是下一次選擇所需處理時間最短的進程，因此，短進程將會越過長進程，得到優(yōu)先運行SPN策略的難點在于需要知道或至少需要估計每個進程所需要的處理時間長進程可能被“餓死”調(diào)度算法最短剩余時間優(yōu)先調(diào)度算法(SRTN)對SPN增加剝奪機制。當一個時鐘中斷周期到后，調(diào)度程序總是選擇預期剩余時間最短的進程當一個新進程加入就緒隊列時，它可能比當前運行的進程具有更短的剩余時間，因此，調(diào)度程序?qū)儕Z當前程序，將處理器分配給新進程。和SPN一樣，調(diào)度程序必須有關(guān)于處理時間的估計，并且存在長進程被餓死的危險調(diào)度算法最高響應比優(yōu)先調(diào)度算法（HRRN）響應比：R=(w+s)/s=1+w/s

w表示等待時間；s表示執(zhí)行所需時間最高響應比也是對最短進程法的一種改進，當當前進程完成或被阻塞時，選擇響應比最大的進程先執(zhí)行，是一種非剝奪的策略。響應比R，代表了進程的年齡，算法在保證短進程優(yōu)先的同時又兼顧了長進程——折中調(diào)度算法最高響應比優(yōu)先調(diào)度算法（HRRN）R=(w+s)/s=1+w/s當一系列進程同時進入系統(tǒng)時，由于短作業(yè)s值小，R值就大，因此短作業(yè)得到了優(yōu)先執(zhí)行。但隨著長作業(yè)等待的時間(w)增長，R值不斷增大，到達一定的等待時間，長進程最終將憑借年齡的增長戰(zhàn)勝短進程，從而獲得處理器?？梢?，在HRRN算法中，長作業(yè)不會被餓死調(diào)度算法優(yōu)先級調(diào)度算法：按進程的優(yōu)先級調(diào)度，選擇就緒隊列中優(yōu)先級最高的進程到處理機上運行。優(yōu)先數(shù)確定方式：靜態(tài)優(yōu)先級：每個進程創(chuàng)建時被賦予一個優(yōu)先數(shù)，該優(yōu)先數(shù)在進程整個生命周期都是固定不變的。動態(tài)優(yōu)先級：每個進程被創(chuàng)建時被賦予一個優(yōu)先數(shù)，該優(yōu)先數(shù)在進程的生命周期內(nèi)是可以動態(tài)變化的調(diào)度算法大多數(shù)動態(tài)優(yōu)先級設(shè)計方案把交互式和I/O頻繁的進程移到優(yōu)先級隊列的頂端，而讓計算量大的進程移到較低的優(yōu)先級上對與優(yōu)先級相同的進程，按先來先服務或輪轉(zhuǎn)法則分配處理機對于一給定時間周期，一個正在運行的進程，每請求一次I/O操作后其優(yōu)先級就自動加1，直接反映出I/O請求的頻率，從而使I/O設(shè)備具有很高的利用率調(diào)度算法優(yōu)先級調(diào)度算法分類：非搶占的優(yōu)先級調(diào)度法：一旦一個高優(yōu)先級的進程占有了處理器，就一直運行下去，直到因等待某事被阻塞或執(zhí)行結(jié)束，才選擇就緒隊列中優(yōu)先級最高的進程來執(zhí)行?？蓳屨嫉膬?yōu)先級調(diào)度法：任何時刻都按照高優(yōu)先級進程在處理器上運行的原則進行進程調(diào)度。當一高優(yōu)先級進程運行時，若有一更高優(yōu)先級進程到達就緒隊列，則當前運行進程立刻將處理器讓給更高優(yōu)先級的進程（即使未處理完，也無遇到阻塞情況）調(diào)度算法

最高優(yōu)先數(shù)算法可搶占CPUProcess

Arrivaltime

Priority

BursttimeP1008P2215P3437P4023P5572GanttChart

0

3

4

5

7

131725P1P4P2P2P3P3P5最高優(yōu)先數(shù)算法0

3

4

5

7

131725P1P4P2P2P3P3P5輪轉(zhuǎn)調(diào)度(簡單輪轉(zhuǎn)法RR)系統(tǒng)把所有就緒進程按先后次序排隊，處理機總是優(yōu)先分配給就緒隊列中的第一個就緒進程，并分配它一個固定的時間片(如50毫秒)當該運行進程用完規(guī)定的時間片時，被迫釋放處理機給下一個處于就緒隊列中的第一個進程,自己回到就緒隊列的尾部，并等待下次調(diào)度當某個正在運行的進程的時間片尚未用完，但進程需要I/O時，該進程被送到相應阻塞隊列，等I/O完成重新返回到就緒隊列尾部，等待調(diào)度。調(diào)度算法簡單輪轉(zhuǎn)法RR處理器就緒隊列阻塞隊列分派釋放超時等待事件事件發(fā)生輪轉(zhuǎn)調(diào)度簡單輪轉(zhuǎn)法是以就緒隊列中的所有進程均以相同的速度往前推進為其特征。其時間片的長短，影響著進程的進展速度當就緒進程很多時，如果時間片很長，就會影響一些需要“緊急”運行的作業(yè)。同樣這對短作業(yè)和要求I/O操作多的作業(yè)顯然是不利的因而，在簡單輪轉(zhuǎn)法的基礎(chǔ)上又提出了分級輪轉(zhuǎn)法調(diào)度算法分級輪轉(zhuǎn)法將一個就緒隊列根據(jù)進程的優(yōu)先級不同，劃分二個或二個以上的就緒隊列，并賦給每個隊列不同的優(yōu)先級，甚至可以分配不同的時間片一般情況下，調(diào)度算法把相同的時間片分配給優(yōu)先級高的就緒隊列中的隊首進程只有當優(yōu)先級高的就緒隊列中的所有進程全部運行完畢或等待I/O操作而沒有進程運行時，才把處理機分配給低優(yōu)先級就緒隊列中的進程調(diào)度算法高優(yōu)先級就緒隊列低優(yōu)先級就緒隊列處理器分級輪轉(zhuǎn)調(diào)度分派超時等待事件阻塞隊列釋放超時事件發(fā)生高優(yōu)先級隊列空調(diào)度算法分級輪轉(zhuǎn)法為了公平性，低優(yōu)先級就緒隊列的進程如果獲得調(diào)度，將得到比高優(yōu)先級就緒隊列進程更多的時間片，加以彌補這樣能大大降低長作業(yè)的交換頻率，減少系統(tǒng)在交換作業(yè)時的時間消耗，又給了短作業(yè)較高的優(yōu)先級反饋FB（多級反饋隊列調(diào)度算法）分級輪轉(zhuǎn)調(diào)度和動態(tài)優(yōu)先級算法的結(jié)合，采用剝奪策略劃分多個就緒隊列，優(yōu)先級逐步降低。新建進程進入優(yōu)先級最高的隊列中，每當進程規(guī)定的時間片用完，被剝奪時，就送往低一級的就緒隊列。進程調(diào)度時總是先執(zhí)行高優(yōu)先級隊列中的進程。高優(yōu)先級隊列為空后，才轉(zhuǎn)去處理低一級優(yōu)先級隊列中的進程。同一優(yōu)先級隊列（除最低）的進程，按FIFO機制調(diào)度。最低優(yōu)先級隊列，按時間片輪轉(zhuǎn)調(diào)度算法執(zhí)行調(diào)度算法允許進入CPURQ0RQ1RQ2RQn釋放CPU釋放CPU釋放CPU釋放反饋調(diào)度不同優(yōu)先級的就緒隊列可以給予相同的時間片，也可以不同。調(diào)度算法反饋FB在反饋調(diào)度算法中，長進程也存在餓死的現(xiàn)象當比運行進程更高優(yōu)先級隊列到來一個新進程時，則應該處理高優(yōu)先級隊列的進程。有兩種方案：搶占方式：即當高優(yōu)先級進程到來時，立即搶占處理進程的處理器，被搶占進程回到原來就緒隊列的末尾。（沒有特殊說明時，認為是搶占方式）非搶占方式：當前進程用完規(guī)定的時間片后，再調(diào)度高優(yōu)先級的進程。調(diào)度算法反饋FB對于被阻塞的進程，當阻塞取消后的處理方法：進入低一級的就緒隊列回到原就緒隊列放入高一級的就緒隊列中進入最高級的就緒隊列時間片的長短由如下四個因素決定：系統(tǒng)的響應時間當進程數(shù)目一定時，時間片的長短直接影響系統(tǒng)的響應時間就緒隊列中進程的數(shù)目當系統(tǒng)對響應時間要求一定時，就緒隊列中進程數(shù)少則時間片長，反之亦然進程狀態(tài)轉(zhuǎn)換

(即進程由就緒態(tài)到運行，或反之)的時間開銷計算機本身的處理能力

執(zhí)行速度和可運行作業(yè)的道數(shù)調(diào)度算法調(diào)度算法例題現(xiàn)有5各進程，到達就緒隊列的時間和所需的服務時間如下表所示求：⑴FCFS,⑵RR(q=1、4),⑶SPN,⑷SRTN,⑸HRRN,⑹FB(q=1、2i)進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE先來先服務(FCFS)調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE循環(huán)(RR)q=1調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE循環(huán)(RR)q=4調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE最短進程(SPN)調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE最短剩余時間(SPTN)調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE最高響應比(HRRN)調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE反饋(隊列有2個）q=1調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82012345678910111213141516171819ABCDE反饋（采用剝奪方式）q=2i調(diào)度算法例題進程到達時間服務時間A03B26C44D65E82各種調(diào)度算法各有其特點，但分級輪轉(zhuǎn)法和反饋法較為理想除了從就緒進程中選取一合理的進程投入運行外，進程調(diào)度程序還必須給該進程分配運行時間片為了保證終端用戶提供服務請求之后，能及時得到響應，一般規(guī)定的時間片在幾十毫秒到幾百毫秒之間不等調(diào)度算法可以有針對性地確定時間片的長短，讓運行時間長的進程在不太頻繁的時間間隔里獲得較大的時間片讓經(jīng)常相互制約的進程有更多的機會獲得處理機，但每次獲得的時間片應較短系統(tǒng)優(yōu)先考慮那些短的、相互制約的進程，而要求時間片長的進程雖然不經(jīng)常運行，但其運行周期較長，能減少處理機分配所造成的開銷進程調(diào)度算法有許多種，在具體實施中，是將幾種算法結(jié)合起來使用，這樣效率更高選擇調(diào)度策略因等待I/O而堵塞運行高優(yōu)先級就緒低優(yōu)先級就緒首先選擇其次選擇超過時間片請求I/OI/O完成調(diào)度時的進程狀態(tài)變遷圖分析其使用的調(diào)度策略與調(diào)度算法分析這一調(diào)度策略的設(shè)計出發(fā)點調(diào)度算法分析：將就緒進程分成高和低優(yōu)先級兩個隊列。如果進程運行中超過了規(guī)定的時間片就進入低優(yōu)先級隊列，而I/O操作完成的進程，即由阻塞狀態(tài)進入高優(yōu)先級就緒隊列調(diào)度算法是:首先從高優(yōu)先就緒隊列中選擇一個進程來運行，如果在高優(yōu)先級就緒隊列中沒有進程，則從低優(yōu)先級就緒隊列中選擇一個進程運行調(diào)度時的進程狀態(tài)圖此算法對于要求I/O量大的就緒進程有利

(高優(yōu)先級)，而對于那些計算量大的就緒進程不利

(未計算完畢就進入低優(yōu)先級就緒隊列)由于外部設(shè)備的運行速度大大低于主機的運行速度，所以為了保持I/O通道和設(shè)備處于忙碌狀態(tài)，受I/O限制的進程優(yōu)先于受CPU限制的進程運行。只有當所有的受I/O限制的進程全部被阻塞，才選取某個受CPU限制的低優(yōu)先級就緒進程在處理機上運行對交互式用戶來說，這個策略提供了良好的響應，也保持了I/O和中央處理機之間的高度并行調(diào)度時的進程狀態(tài)圖§4傳統(tǒng)的UNIX調(diào)度傳統(tǒng)的UNIX調(diào)度的基本目標是分時交互環(huán)境調(diào)度算法設(shè)計成為交互用戶提供好的響應時間，同時保證低優(yōu)先級的后臺作業(yè)不會餓死。是分時調(diào)度算法的代表傳統(tǒng)的UNIX調(diào)度程序在每個優(yōu)先級隊列中采用使用循環(huán)法的多級反饋。該系統(tǒng)使用1秒剝奪，也就是說，如果一個正在運行的進程在1秒內(nèi)沒有阻塞或完成，它將被剝奪。優(yōu)先級基于進程類型和執(zhí)行歷史§4傳統(tǒng)的UNIX調(diào)度每秒都重新計算每個進程的優(yōu)先級，并進行一次新的調(diào)度決策基本優(yōu)先級的目的是把所有的進程劃分成固定的優(yōu)先級。這些區(qū)用于優(yōu)化訪問塊設(shè)備(如磁盤)和允許操作系統(tǒng)迅速響應系統(tǒng)調(diào)用按優(yōu)先級的順序，這些區(qū)如下交換程序塊I/O設(shè)備控制文件操作字符I/O設(shè)備控制用戶進程§4多處理器調(diào)度當系統(tǒng)包含多個處理器時，在設(shè)計調(diào)度功能時就會產(chǎn)生一些新問題多處理器系統(tǒng)可以劃分為以下幾類松耦合、分布式多處理器、集群：由一組相對自治的系統(tǒng)組成，每個處理器有自己的主存和I/O通道專門功能的處理器：例如I/O處理器。在這種情況下，有一個通用的主處理器，專用處理器受主處理器的控制，并給主處理器提供服務緊耦合多處理器：由一組共享同一個主存并在操作系統(tǒng)完全控制下的處理器組成關(guān)注最后一類系統(tǒng)，特別是與調(diào)度有關(guān)的問題粒度刻畫多處理器的一種比較好的方法，是考慮系統(tǒng)中進程之間的同步粒度，或者說同步頻率可以根據(jù)粒度區(qū)分5類并行度獨立：多個無關(guān)進程非常粗：在網(wǎng)絡(luò)節(jié)點上進行分布處理，以形成一個計算環(huán)境粗：在多道程序環(huán)境中并發(fā)進程的多處理中等：在一個應用程序中的并行處理或多任務處理(線程)細：指令流中固有的并行§4多處理器調(diào)度獨立并行度進程間沒有顯式的同步。每個進程都代表各自獨立的應用或作業(yè)。這類并行度的一個典型應用是分時系統(tǒng)。每個用戶都執(zhí)行一個特定的應用，如字處理或使用電子表格。多處理器和多道程序單處理器一樣提供相同的服務。由于有多個處理器可用，因而用戶的平均響應時間非常短有可能達到這樣的性能：每個用戶都如同在使用個人計算機或工作站。如果任何一個文件或信息被共享，則單個系統(tǒng)必須連接在一個有網(wǎng)絡(luò)支持的分布式系統(tǒng)中在許多實例中，多處理器共享系統(tǒng)比分布式系統(tǒng)的成本效益更合算，它允許節(jié)約使用磁盤和其他外圍設(shè)備粒度粗粒度和非常粗粒度的并行度是指進程之間在一個非常粗的級別上存在著同步。這種情況可以簡單地處理成一組運行在多道程序單處理器上的并發(fā)進程，在多處理器上對用戶軟件進行很少的改動或者不進行改動就可以提供支持一般來說，使用多處理器體系結(jié)構(gòu)，對所有需要通信或同步的并發(fā)進程集合都有好處。當進程間存在非常頻繁的交互時，分布式系統(tǒng)可以提供好的支持。但是，當交互更加頻繁時，分布式系統(tǒng)中的網(wǎng)絡(luò)通信開銷會抵消一部分潛在的加速，在這種情況下，多處理器組織能提供最有效的支持粒度中等粒度的并行度應用程序可以作為進程中的一組線程被有效地實現(xiàn)。在這種情況下，可以由程序員顯式地指定應用程序潛在的并行性。典型地，在應用程序的線程之間，需要更高程度的合作與交互，從而導致中等粒度級的同步盡管多處理器和多道程序單處理器都支持獨立、非常粗和粗粒度的并行度，并對調(diào)度功能產(chǎn)生少許影響或沒有影響，但是在處理線程調(diào)度時，我們?nèi)匀恍枰匦路治稣{(diào)度。由于應用程序中各個線程間的交互是如此地頻繁，關(guān)于線程調(diào)度的決策可能會影響整個應用的性能粒度細粒度的并行度代表著比線程中的并行更加復雜的使用。盡管在高度并行的應用中已經(jīng)完成了大量的工作，迄今為止，這仍然是一個特殊的、被分割的領(lǐng)域粒度多處理器中的調(diào)度涉及到以下三個相關(guān)問題把進程分配到處理器在單個處理器上使用多道程序一個進程的實際分派在討論這三個問題時，必須記住所采用的方法通常取決于應用程序的粒度等級和可用的處理器的數(shù)目設(shè)計問題把進程分配到處理器假設(shè)多處理器結(jié)構(gòu)中各個處理器在訪問主存和I/O設(shè)備時沒有特別優(yōu)勢，那么最簡單的調(diào)度方法是把處理器看作是一個資源池，并按照要求把進程分配到相應的處理器。帶來的問題是：分配應該是靜態(tài)的還是動態(tài)的設(shè)計問題靜態(tài)：一個進程從被激活到完成，被永久地分配到一個處理器，則需要為每個處理器維護一個專門的短程隊列。其優(yōu)點是調(diào)度的開銷比較小，因為所有進程關(guān)于處理器的分配只進行一次靜態(tài)分配的缺點是某個處理器可能空閑，這時它的隊列為空，而另一個處理器卻積壓了許多工作設(shè)計問題設(shè)計問題動態(tài)：為防止靜態(tài)分配浪費CPU資源的情況，需要使用一個公共隊列。所有進程都進入一個全局隊列，然后調(diào)度到任何一個可用的處理器中。這樣，在一個進程的生命周期中，它可以在不同的時間在不同的處理器上執(zhí)行把進程分配到處理器——處理器結(jié)構(gòu)主從式結(jié)構(gòu)：操作系統(tǒng)的主要核心功能總是在某個特定的處理器上運行，其他處理器可能僅用于執(zhí)行用戶程序主處理器負責調(diào)度作業(yè)。當一個進程被激活時，如果從處理器需要服務(例如一次I/O調(diào)用)，它必須給主處理器發(fā)送一個請求，然后等待服務的執(zhí)行這種方法簡單，由于處理器擁有對所有存儲器和I/O資源的控制，因而可以簡化沖突解決方案缺點是:主處理器的失敗導致整個系統(tǒng)失敗;主處理器可能成為性能瓶頸設(shè)計問題把進程分配到處理器——處理器結(jié)構(gòu)對等式結(jié)構(gòu)：操作系統(tǒng)可以在任何一個處理器中執(zhí)行。每個處理器從可用進程池中進行自調(diào)度。這種方法增加了操作系統(tǒng)的復雜性，必須確保兩個處理器不會選擇同一個進程，進程也不會從隊列中丟失也可以提供一個處理器子集專門用于內(nèi)核處理，或者是基于優(yōu)先級和執(zhí)行歷史來管理內(nèi)核進程和其他進程之間的差別等設(shè)計問題在單個處理器上使用多道程序傳統(tǒng)的多處理器處理是粗粒度或獨立同步粒度，顯然單個處理器能夠在許多進程間切換，以達到較高的使用率和更好的性能。但是，對于運行在有許多處理器的多處理器系統(tǒng)中的中等粒度(線程)應用程序，當多個處理器可用時，要求每個處理器盡可能地忙就不再那么重要了。相反，我們更加關(guān)注如何能為應用提供最好的平均性能。設(shè)計問題進程分派選擇哪一個進程運行？在多道程序單處理器上，與簡單的先來先服務策略相比較，使用優(yōu)先級或者基于過去的使用歷史的高級調(diào)度算法可以提高性能當考慮多處理器時，這些復雜性是不必要的，不然可能反而達不到預期的目標，對于多處理器，相對比較簡單的方法會更有效，而且開銷也比較低。設(shè)計問題在大多數(shù)傳統(tǒng)的多處理器系統(tǒng)中，進程并不是被指定到一個專門的處理器。不是所有處理器只有一個隊列而是有多條基于優(yōu)先級的隊列，并且都送進相同的處理器池中。在任何情況下，我們都可以把系統(tǒng)看作是多服務器排隊結(jié)構(gòu)對各種情況進行分析，對于多處理器，調(diào)度原則的選擇沒有在單處理器中顯得重要。因此，在多處理器系統(tǒng)中使用簡單的FCFS(先來先服務)原則或者在靜態(tài)化先級方案中使用FCFS就足夠了多處理器進程調(diào)度CPU就緒隊列n釋放CPU釋放CPU釋放CPU釋放多處理器調(diào)度就緒隊列3就緒隊列2就緒隊列1分派CPU池在單處理器中，線程可以用作輔助構(gòu)造程序，并在處理過程中重疊執(zhí)行I/O。由于在進行線程切換時的性能損失遠遠小于進程切換的開銷，因此可以用很少的代價實現(xiàn)這些優(yōu)點在多處理器系統(tǒng)中，線程的全部能力得到了更好的展現(xiàn)，線程可以用于開發(fā)應用程序中真正的并行性。如果一個應用程序的各個線程同時在各個獨立的處理器中執(zhí)行，其性能就會得到顯著的提高。線程調(diào)度在多處理器線程調(diào)度和處理器分配的各種方案中，比較突出的方法是：負載分配：進程不是分配到一個特定的處理器，而是維護一個就緒進程的全局隊列，每個處理器只要空閑就從隊列中選擇一個線程，負載平衡是基于一種比較永久的分配方案配工作的成組調(diào)度：一組相關(guān)的線程基于一對一的原則，同時調(diào)度到一組處理器上運行專用處理器分配：這種方法與負載分配的方法相反，它通過把線程指定到處理器來定義隱式的調(diào)度。在程序執(zhí)行過程中，每個程序被分配給一組處理器，處理器的數(shù)目與程序線程的數(shù)目相等。當程序終止時，處理器返回到總的處理器池中，可供分配給另一個程序動態(tài)調(diào)度：在執(zhí)行期間，進程中線程的數(shù)目可以改變線程調(diào)度Windows2000調(diào)度Windows2000的設(shè)計目標是在高度交互的環(huán)境中或者作為服務器盡可能地響應單個用戶的需求Windows2000實現(xiàn)了剝奪式調(diào)度程序，它具有靈活的優(yōu)先級系統(tǒng)，在每一級上都包括了循環(huán)調(diào)度方法，在某些級上，優(yōu)先級可以基于它們當前的線程活動而動態(tài)變化Windows2000中的優(yōu)先級被組織成兩段(兩類)：實時和可變。每一段包括16種優(yōu)先級。需要立即關(guān)注的線程在實時類中，它包括諸如通信之類的功能和實時任務Windows2000使用一種優(yōu)先級驅(qū)動的剝奪式調(diào)度程序，具有實時優(yōu)先級的線程優(yōu)先于其他線程在單處理器中，當一個線程就緒時，如果它的優(yōu)先級高于當前正在執(zhí)行的線程，那么低優(yōu)先級的線程被剝奪，具有更高優(yōu)先級的進程占用處理器進程和線程優(yōu)先級兩類優(yōu)先級的處理方式有一定的不同在實時優(yōu)先級類中，所有線程具有固定的優(yōu)先級，并且它們的優(yōu)先級永遠不會改變，某一給定優(yōu)先級的所有活動線程在一個循環(huán)隊列中在可變優(yōu)先級類中，一個線程的優(yōu)先級在開始時是最初指定的值，但在它的生命周期中可能會發(fā)生變化，上升或者下降。因此，在每個優(yōu)先級上都有一個FIFO隊列，一個進程可能在可變優(yōu)先級類中從一個隊列遷移到另一個隊列。但是，優(yōu)先級為15的線程不能升到16級，也就是說不能升到實時類的任何級中進程和線程優(yōu)先級最低(0)最高(15)最低(16)最高(31)實時優(yōu)先級類可變優(yōu)先級類WindowsNT線程調(diào)度優(yōu)先級當Windows2000運行在一個處理器上時，優(yōu)先級最高的線程總是活躍的，除非它正在等待一個事件如果有多個線程具有最高的優(yōu)先級，則處理器在這一級的所有線程間被循環(huán)共享在一個具有N個處理器的多處理器系統(tǒng)中，(N-1)個最高優(yōu)先級的線程總是活躍的，在(N-1)個處理器上獨占運行。剩下的低優(yōu)先級線程共享剩下的一個處理器多處理器調(diào)度3.4實時調(diào)度(real-timescheduling)實時任務：具有明確時間約束的計算任務。Eg.某時刻前必須開始處理某時刻前必須處理完畢實時調(diào)度：合理安排就緒實時任務的執(zhí)行次序，滿足每個實時任務時間約束條件的調(diào)度。實時任務分類硬實時vs.軟實時

硬實時(hardreal-time):必須滿足任務截止期要求.軟實時(softreal-time):期望滿足截止期要求.周期性vs.隨機性

周期性:每隔固定時間發(fā)生一次隨機性:由隨機事件觸發(fā)，其發(fā)生時刻不確定術(shù)語解釋Readytime:就緒時間Startingdeadline:開始截止期Processingtime:處理時間Completiondeadline:完成截止期Occurringfrequency:發(fā)生頻率周期性實時事務周期性實時事務:令Ci為任務Pi處理時間，Ti為任務Pi的發(fā)生周期，則任務P1,…,Pm可調(diào)度的必要條件為：

周期性實時事務例：T1=100,T2=200,T3=500(ms)C1=50,C2=30,C3=100(ms)C1/T1+C2/T2+C3/T3=0.5+0.15+0.2=0.85<1滿足可調(diào)度的必要條件周期性實時事務進程就緒時間處理時間完成截止期發(fā)生周期A0102020B025505010/20+25/50=1,可調(diào)度(不考慮開銷)例子ProcessArrivaltimeExecutiontimecompletiondeadlineA(1)A(2)A(3)A(4)A(5)…...B(1)B(2)020406080…...0501010101010……252520406080100…...501003.4.1最早截止期調(diào)度EDF（EarliestDeadlineFirst)優(yōu)先選擇截止期最早的實時任務可搶先可以證明：對EDF來說，可調(diào)度充分條件是：在不可調(diào)度的條件下，可使錯過截止期任務最小化例子:EarliestDeadlineFirst0102030405060708090100TimeA2A2dlA3A3dlA4A4dlB1A1A1dlB1dlB2B2dlA5A5dlA1B1A2B1A3B2A5B2A4A1A2B1A3A4A5B23.4.2速率單調(diào)調(diào)度RMS（RateMonotonicScheduling）提出于1973年面向周期性實時事務，非剝奪式優(yōu)先調(diào)度發(fā)生周期最短（頻度最高）的實時任務可調(diào)度條件：RMS的上限值RMSvs.EDFRMS可調(diào)度條件強于EDFRMS調(diào)度較EDF實現(xiàn)簡單RMS例子：進程ＴiCiA10020B15040C350100可調(diào)度，具體調(diào)度結(jié)果：A1B1C1A2B2A3A4B3C202060160180220240300320360460例題精選假定要在一臺處理機上執(zhí)行右表作

業(yè)，且假定這些作業(yè)同時到達的次

序是1,2,3,4,5，(數(shù)字越小優(yōu)先級

越高）。(1)給出Gantt圖說明分別使用FCFS、RR(時間片=1)、SPN以及非搶占優(yōu)先調(diào)度算法時這些作業(yè)的執(zhí)行情況。(2)針對上述每一算法，給出每個作業(yè)周轉(zhuǎn)時間；(3)就上述每一算法，求出每個作業(yè)相應的等待時間；(4)對所有作業(yè)而言，具有最小平均等待時間和最小周轉(zhuǎn)時間的調(diào)度算法各是哪一個？作業(yè)執(zhí)行時間優(yōu)先級1103211323414552(1)給出Gantt圖說明分別

使用FCFS、RR(時間片=1)、

SPN以及非搶占優(yōu)先調(diào)度算法

時這些作業(yè)的執(zhí)行情況。

1(10)2(1)3(2)4(1)5(5)FCFS/RR123451351515151（5）2(1)4(1)3(2)5(5)1(10)SPN/Priority2(1)5(5)1(10)3(2)4(1)例題精選作業(yè)執(zhí)行時間優(yōu)先級1103211323414552例題精選(2)針對上述每一算法，

給出每個作業(yè)的周轉(zhuǎn)時間。作業(yè)執(zhí)行時間優(yōu)先級1103211323414552作業(yè)FCF