cpu的調度演算法

1. cpu調度演算法決定了進程執行的順序.若有n個進程需要調度，有多少種可能的調度順

前兩天做操作系統作業的時候學習了一下幾種進程調度演算法，在思考和討論後，有了一些自己的想法，現在就寫出來，跟大家討論下。，或者說只有有限的CPU資源，當系統中有多個進程處於就緒狀態，要競爭CPU資源時，操作系統就要負責完成如何分配資源的任務。在操作系統中，由調度程序來完成這一選擇分配的工作，調度程序所使用的演算法即是調度演算法。調度演算法需要考慮的指標主要有盡量保證CPU資源分配的公平性；按照一定策略強制執行演算法調度；平衡整個計算機系統，盡量保持各個部分都處於忙碌狀態。而根據系統各自不同的特點和要求，調度演算法又有一些側重點和目標不同，因此，演算法按照系統差異主要分為三大類：批處理系統中的調度演算法，代表調度演算法有：先來先服務、最短作業優先、最短剩餘時間優先。互動式系統中的調度演算法，代表調度演算法有：輪轉調度、優先順序調度、多級隊列、最短進程優先、保證調度、彩票調度、公平分享調度。實時系統中的調度演算法，代表調度演算法有：速率單調調度、最早最終時限優先調度。下面就上述提到的調度演算法中挑出幾個進行重點分析：保證調度保證調度是指利用演算法向用戶做出明確的性能保證，然後盡力按照此保證實現CPU的資源分配。利用這種演算法，就是定一個進程佔用CPU的時間的標准，然後按照這個標准去比較實際佔用CPU的時間，調度進程每次使離此標准最遠的進程得到資源，不斷滿足離所保證的標准最遠的進程，從而平衡資源分配滿足這個標準的要求。保證調度演算法的優點是：能很好的保證進程公平的CPU份額，當系統的特點是：進程的優先順序沒有太大懸殊，所制定的保證標准差異不大，各個進程對CPU的要求較為接近時，比如說系統要求n個進程中的每個進程都只佔用1/n的CPU資源，利用保證調度可以很容易的實現穩定的CPU分配要求。但缺點是，這種情況太過理想，當系統的各個進程對CPU要求的緊急程度不同，所制定的保證較為復雜的時候，這個演算法實現起來比較困難。彩票調度彩票調度這種演算法的大意是指向進程提供各種系統資源如CPU資源的彩票，當系統需要做出調度決策時，隨機抽出一張彩票，由此彩票的擁有者獲得資源。在彩票調度系統中，如果有一個新的進程出現並得到一些彩票，那麼在下一次的抽獎中，該進程會有同它持有彩票數量成正比例的機會贏得獎勵。進程持有的彩票數量越多，則被抽中的可能性就越大。調度程序可以通過控制進程的彩票持有數量來進行調度。彩票調度有很多優點：首先，它很靈活，系統增加分給某個進程的彩票數量，就會大大增加它佔用資源的可能性，可以說，彩票調度的反應是迅速的，而快速響應需求正是互動式系統的一個重要要求。其次，彩票調度演算法中，進程可以交換彩票，這個特點可以更好的保證系統的平衡性，使其各個部分都盡可能的處於忙碌狀態。而且利用彩票調度還可以解決許多別的演算法很難解決的問題，例如可以根據特定的需要大致成比例的劃分CPU的使用。速率單調調度速率單調調度演算法是一種可適用於可搶占的周期性進程的經典靜態實時調度演算法。當實時系統中的進程滿足：每個周期性進程必須在其周期內完成，且進程之間沒有相互依賴的關系，每個進程在一次突發中需要相同的CPU時間量，非周期的進程都沒有最終時限四個條件時，並且為了建模方便，我們假設進程搶占即刻發生沒有系統開銷，可以考慮利用速率單調演算法。速率單調調度演算法是將進程的速率（按照進程周期所算出的每秒響應的次數）賦為優先順序，則保證了優先順序與進程速率成線性關系，這即是我們所說的速率單調。調度程序每次運行優先順序最高的，只要優先順序較高的程序需要運行，則立即搶占優先順序低的進程，而優先順序較低的進程必須等所有優先順序高於它的進程結束後才能運行。速率單調調度演算法可以保證系統中最關鍵的任務總是得到調度，但是缺點是其作為一種靜態演算法，靈活性不夠好，當進程數變多，系統調度變得復雜時，可能不能較好的保證進程在周期內運行。最早最終時限優先調度最早最終時限優先調度演算法是一個動態演算法，不要求進程是周期性的，只要一個進程需要CPU時間，它就宣布它的到來時間和最終時限。調度程序維持一個可運行的進程列表，按最終時限排序，每次調度一個最終時限最早的進程得到CPU 。當新進程就緒時，系統檢查其最終時限是否在當前運行的進程結束之前，如果是，則搶占當前進程。由於是動態演算法，最早最終優先調度的優點就是靈活，當進程數不超過負載時，資源分配更優，但也同樣由於它的動態屬性，進程的優先順序都是在不斷變化中的，所以也沒有哪個進程是一定可以保證滿足調度的，當進程數超過負載時，資源分配合理度會急速下降，所以不太穩定。

2. cpu調度的基本方式

我們知道，程序需要獲得CPU的資源才能被調度和執行，那麼當一個進程由於某種原因放棄CPU然後進入阻塞狀態，下一個獲得CPU資源去被調度執行的進程會是誰呢？下圖中，進程1因為阻塞放棄CPU資源，此時，進程2剛IO操作結束，可以獲得CPU資源去被調度，進程3的時間片輪轉結束，也同樣可以獲得CPU資源去被調度，那麼，此時的操作系統應該安排哪個進程去獲得CPU資源呢？這就涉及到我們操作系統的CPU調度策略了。

根據生活中的例子，我們很容易想到以下兩種策略CPU調度的直觀想法：1.FIFO誰先進入，先調度誰，這是一種非常簡單有效的方法，就好比我們去飯堂打飯，誰先到就給誰先打飯。但是這種策略會遇到一個問題：如果遇到一個很小的任務，但是它是最後進入的，那麼必須得前面一大堆任務結束完後才能執行這個小小的任務，這樣就感覺很不劃算呀！因為我只是簡簡單單的一個小任務，但是從打開這個任務到結束這個任務要很久。這顯然不符合我們的需求，因而我們會想到第2種策略，就是先調度小任務，後調度大任務。2.Priority很簡單，就是任務短的優先執行，但是此時又有問題了，任務雖然短，但是它的執行時間不一定短，就好比在一個銀行業務中，客戶填寫一個表，這是一個非常短的任務吧——就單單填個表，但是這個表很長很長，那麼這個短任務它的執行時間就很長了，我們怎麼知道這個短的任務將來會執行多長的時間呢？所以，這樣的策略還是依然有問題。那麼，面對諸多的場景，如何設計調度演算法呢？首先，我們要明白我們的演算法應該讓什麼更好呢？面對客戶：銀行調度演算法的設計目標應該是用戶滿意；而面對進程：CPU調度的目標應該是進程滿意。那怎麼才能讓進程滿意呢？那就是時間了。進程希望盡早地結束任務，這就是周轉時間(從任務到達到任務結束)要短，而且希望用戶的操作能夠盡快地被響應，這就是響應時間(從操作發生到響應)要短。而且系統內耗時間要少，吞吐量(任務的完成量)要大，系統需要把更多的時間用在任務的執行上，而不能老是去做無關緊要的事情，例如：頻繁切換任務，切換棧，分配資源等事情。同時，系統還要去合理地調配任務。那麼，CPU的調度策略如何做到合理呢？首先得明白系統中有以下的幾種矛盾。1.吞吐量和響應時間之間有矛盾響應時間小=>切換次數多=>系統內耗大=>吞吐量小由於需要較短的響應時間，那麼就得頻繁地切換任務，這樣系統的很多時間都花在切換任務上面了，系統的內耗大了，吞吐量就小了。2.前台任務和後台任務的關注點不同前台任務關注響應時間，後台任務關注周轉時間。前台任務例如我們的word文檔，我們打一個字，需要立馬顯示在文檔中，這就是word文檔這個任務關注的是響應時間；而後台任務中，例如我們的javac編譯java代碼，它的周轉時間要小，即該任務從進入到結束所花的時間要小，即編譯完成的時間要小。http://3.IO約束型任務和CPU約束型任務各有各的特點IO約束型任務就是使用CPU的時間較少，進行IO操作的時間較長，CPU約束型的任務就是使用CPU的時間較長。因此，要做到合理，需要折中、綜合考慮以上的幾種矛盾。由此，產生了一些CPU的調度演算法，在下一節我們將重點講述這些CPU調度演算法。

關注小鯨融創，一起深度學習金融科技！

編輯於 2019-12-11 · 著作權歸作者所有
贊同 1
評論
展開全部

3. 進程調度的方式有哪兩種試列舉至少4種進程調度演算法。

進程調度的方式有非剝奪方式和剝奪方式。
非剝奪方式：
分派程序一旦把處理機分配給某進程後便讓它一直運行下去，直到進程完成或發生某事件而阻塞時，才把處理機分配給另一個進程。
剝奪方式：
當一個進程正在運行時，系統可以基於某種原則，剝奪已分配給它的處理機，將之分配給其它進程。剝奪原則有：優先權原則、短進程優先原則、時間片原則。
進程調度演算法：
1、先進先出演算法（FIFO）：
演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。
舉例：有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間，對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。
2、最短CPU運行期優先調度演算法(SCBF--Shortest CPU Burst First)：
該演算法從就緒隊列中選出下一個「CPU執行期最短」的進程，為之分配處理機。
舉例：在就緒隊列中有四個進程P1、P2、P3和P4，它們的下一個執行進程調度期分別是16、12、4和3個單位時間，P1、P2、P3和P4的周轉時間分別為35、19、7、3，平均周轉時間為16。該演算法雖可獲得較好的調度性能，但難以准確地知道下一個CPU執行期，而只能根據每一個進程的執行歷史來預測。
3、時間片輪轉法：
前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。
4、多級反饋隊列：
多級隊列方法：將系統中所有進程分成若干類，每類為一級。多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權。

4. 操作系統-cpu調度演算法設計

對等動態優先權演算法，進程調度過程掌握情況；考查學生的寫演算法和編程能力等；考查學生的分析問題和解決問題的能力；實驗報告的撰寫能力等。 設計思路： （1）先對就緒隊列，阻塞隊列，cpu的進行初始化。 （2）進行進程調度的選擇。 1）cpu，就緒...

5. 多核CPU操作系統採用的是什麼任務調度演算法

目前多數多核CPU操作系統採用的是基於全局隊列的任務調度演算法

處理器設計的首要問題是選擇程序執行模型。程序執行模型的適用性決定多核處理器能否以最低的代價提供最高的性能。程序執行模型是編譯器設計人員與系統實現人員之間的介面。編譯器設計人員決定如何將一種高級語言程序按一種程序執行模型轉換成一種目標機器語言程序; 系統實現人員則決定該程序執行模型在具體目標機器上的有效實現。當目標機器是多核體系結構時，產生的問題是: 多核體系結構如何支持重要的程序執行模型？是否有其他的程序執行模型更適於多核的體系結構？這些程序執行模型能多大程度上滿足應用的需要並為用戶所接受？