先進先出調度演算法

㈠ 進程調度演算法的國內外研究現狀有哪些

調度演算法是指：根據系統的資源分配策略所規定的資源分配演算法。常見的進程調度演算法有：

1.先來先去服務

2.時間片輪轉法

3.多級反饋隊列演算法

4.最短進程優先

5.最短剩餘時間優先

6.最高響應比優先

7.多級反饋隊列調度演算法

一、先來先去服務

先來先去服務調度演算法是一種最簡單的調度演算法，也稱為先進先出或嚴格排隊方案。當每個進程就緒後，它加入就緒隊列。當前正運行的進程停止執行，選擇在就緒隊列中存在時間最長的進程運行。該演算法既可以用於作業調度，也可以用於進程調度。先來先去服務比較適合於常作業（進程），而不利於段作業（進程）。

二、時間片輪轉法

輪轉法是基於適中的搶占策略的，以一個周期性間隔產生時鍾中斷，當中斷發生後，當前正在運行的進程被置於就緒隊列中，然後基於先來先去服務策略選擇下一個就緒作業的運行。這種技術也稱為時間片，因為每個進程再被搶占之前都給定一片時間。

三、最短進程優先

最短進程優先是一個非搶占策略，他的原則是下一次選擇預計處理時間最短的進程，因此短進程將會越過長作業，跳至隊列頭。該演算法即可用於作業調度，也可用於進程調度。但是他對長作業不利，不能保證緊迫性作業（進程）被及時處理，作業的長短只是被估算出來的。

四、最短剩餘時間優先

最短剩餘時間是針對最短進程優先增加了搶占機制的版本。在這種情況下，進程調度總是選擇預期剩餘時間最短的進程。當一個進程加入到就緒隊列時，他可能比當前運行的進程具有更短的剩餘時間，因此只要新進程就緒，調度程序就能可能搶占當前正在運行的進程。像最短進程優先一樣，調度程序正在執行選擇函數是必須有關於處理時間的估計，並且存在長進程飢餓的危險。

㈡ FIFO調度演算法和LRU演算法

FIFO：先進先出調度演算法
LRU：最近最久未使用調度演算法

兩者都是緩存調度演算法，經常用作內存的頁面置換演算法。

打一個比方，幫助你理解。

你有很多的書，比如說10000本。
由於你的書實在太多了，你只能放在地下室裡面。
你看書的時候不會在地下室看書，而是在書房看書。
每次，你想看書都必須跑到地下室去找出來你想看的書，
然後抱回來放到書桌上，之後才開始看。
還有就是，有一些書你會反復的看，今天看了也許過幾天又要看。
總之，你自己是不知道你哪天會需要看哪本書的。
你的老師每天下課的時候會給你布置一個書單，讓你晚上回去去看哪本書。
（假設你老師讓你看的書在你的地下室裡面都有）

跑地下室當然是非常麻煩的，所以你希望你的經常看的那些書最好放在書桌上。
但是你的書房的書桌同時只能擺放10本書（這個是假設的啊）。
那麼，問題來了。
到底把哪些說留在書桌上最好呢？
這里說的最好，就是說你盡量少的跑地下室去找書。

為了解決這個問題，人們發明了很多的演算法。
其中，比較常見的就是上面這兩種：FIFO演算法和LRU演算法。

FIFO演算法
很簡單，我把書桌上的10本書按照放置時間先後堆放成一堆。
這里的放置時間，就是說這本書在我的書桌上放了幾天了。
每次要看書的時候，我先在書桌上找，找到就直接可以讀了。
讀完之後放回原來的位置就可以，不打亂順序。
如果書桌上面沒有我要讀的書，就去地下室找。
找來之後，我就把書桌上放的時間最長的那本（也就是
書堆裡面最下面的那本書）放回地下室。
然後把我今天需要看的這本書放在書堆的最上面。

LRU演算法
也不難，我把書桌上的10本書按照閱讀時間先後堆放成一堆。
這里的閱讀時間，就是說我最近一次讀這本書是幾天之前。
每次要看書的時候，我先在書桌上找，找到就直接可以讀了。
讀完之後放在書堆的最上面。
如果書桌上面沒有我要讀的書，就去地下室找。
找來之後，我就把書桌上最久沒有閱讀的那本
（也就是書堆裡面最下面的那本書）放回地下室。
然後把我今天需要看的這本書放在書堆的最上面。

上面這個比方，相信你可以看明白吧。
這里的地下室對應內存，書桌對應緩存，書對應頁面。

㈢ 頁面調度先進先出演算法（FIFO） 用C語言描述 歡迎高手前來挑戰

c語言實現的頁面調度演算法,用三種演算法實現調度1.先進先出2.OPT3.LRU 2.頁面序列從指定的文本文件（TXT文件）中取出3.輸出：第一行：每次淘汰的頁面號 第二行：顯示缺頁的總次數(上機已經運行通過!!)-pages scheling algorithm, a three-Scheling Algorithm 1. FIFO 2.OPT3.LRU 2. Pages from the designated sequence of text files (TXT) out of three. Output : the first line : each of the pages out of the second line : show na the total number of pages (on the plane had run through! !)

㈣ linux進程調度的三種策略是什麼

linux內核的三種主要調度策略：
1，SCHED_OTHER 分時調度策略，
2，SCHED_FIFO實時調度策略，先到先服務
3，SCHED_RR實時調度策略，時間片輪轉

實時進程將得到優先調用，實時進程根據實時優先順序決定調度權值。分時進程則通過nice和counter值決定權值，nice越小，counter越大，被調度的概率越大，也就是曾經使用了cpu最少的進程將會得到優先調度。

SHCED_RR和SCHED_FIFO的不同：
當採用SHCED_RR策略的進程的時間片用完，系統將重新分配時間片，並置於就緒隊列尾。放在隊列尾保證了所有具有相同優先順序的RR任務的調度公平。
SCHED_FIFO一旦佔用cpu則一直運行。一直運行直到有更高優先順序任務到達或自己放棄。
如果有相同優先順序的實時進程（根據優先順序計算的調度權值是一樣的）已經准備好，FIFO時必須等待該進程主動放棄後才可以運行這個優先順序相同的任務。而RR可以讓每個任務都執行一段時間。

相同點：
RR和FIFO都只用於實時任務。
創建時優先順序大於0(1-99)。
按照可搶占優先順序調度演算法進行。
就緒態的實時任務立即搶占非實時任務。

所有任務都採用linux分時調度策略時：
1，創建任務指定採用分時調度策略，並指定優先順序nice值(-20~19)。
2，將根據每個任務的nice值確定在cpu上的執行時間(counter)。
3，如果沒有等待資源，則將該任務加入到就緒隊列中。
4，調度程序遍歷就緒隊列中的任務，通過對每個任務動態優先順序的計算權值(counter+20-nice)結果，選擇計算結果最大的一個去運行，當這個時間片用完後(counter減至0)或者主動放棄cpu時，該任務將被放在就緒隊列末尾(時間片用完)或等待隊列(因等待資源而放棄cpu)中。
5，此時調度程序重復上面計算過程，轉到第4步。
6，當調度程序發現所有就緒任務計算所得的權值都為不大於0時，重復第2步。

所有任務都採用FIFO時：
1，創建進程時指定採用FIFO，並設置實時優先順序rt_priority(1-99)。
2，如果沒有等待資源，則將該任務加入到就緒隊列中。
3，調度程序遍歷就緒隊列，根據實時優先順序計算調度權值(1000+rt_priority),選擇權值最高的任務使用cpu，該FIFO任務將一直佔有cpu直到有優先順序更高的任務就緒(即使優先順序相同也不行)或者主動放棄(等待資源)。
4，調度程序發現有優先順序更高的任務到達(高優先順序任務可能被中斷或定時器任務喚醒，再或被當前運行的任務喚醒，等等)，則調度程序立即在當前任務堆棧中保存當前cpu寄存器的所有數據，重新從高優先順序任務的堆棧中載入寄存器數據到cpu，此時高優先順序的任務開始運行。重復第3步。
5，如果當前任務因等待資源而主動放棄cpu使用權，則該任務將從就緒隊列中刪除，加入等待隊列，此時重復第3步。

所有任務都採用RR調度策略時：
1，創建任務時指定調度參數為RR，並設置任務的實時優先順序和nice值(nice值將會轉換為該任務的時間片的長度)。
2，如果沒有等待資源，則將該任務加入到就緒隊列中。
3，調度程序遍歷就緒隊列，根據實時優先順序計算調度權值(1000+rt_priority),選擇權值最高的任務使用cpu。
4，如果就緒隊列中的RR任務時間片為0，則會根據nice值設置該任務的時間片，同時將該任務放入就緒隊列的末尾。重復步驟3。
5，當前任務由於等待資源而主動退出cpu，則其加入等待隊列中。重復步驟3。

系統中既有分時調度，又有時間片輪轉調度和先進先出調度：
1，RR調度和FIFO調度的進程屬於實時進程，以分時調度的進程是非實時進程。
2，當實時進程准備就緒後，如果當前cpu正在運行非實時進程，則實時進程立即搶占非實時進程。
3，RR進程和FIFO進程都採用實時優先順序做為調度的權值標准，RR是FIFO的一個延伸。FIFO時，如果兩個進程的優先順序一樣，則這兩個優先順序一樣的進程具體執行哪一個是由其在隊列中的未知決定的，這樣導致一些不公正性(優先順序是一樣的，為什麼要讓你一直運行?),如果將兩個優先順序一樣的任務的調度策略都設為RR,則保證了這兩個任務可以循環執行，保證了公平。

Ingo Molnar-實時補丁
為了能並入主流內核，Ingo Molnar的實時補丁也採用了非常靈活的策略，它支持四種搶占模式：
1．No Forced Preemption (Server)，這種模式等同於沒有使能搶占選項的標准內核，主要適用於科學計算等伺服器環境。
2．Voluntary Kernel Preemption (Desktop)，這種模式使能了自願搶占，但仍然失效搶占內核選項，它通過增加搶占點縮減了搶占延遲，因此適用於一些需要較好的響應性的環境，如桌面環境，當然這種好的響應性是以犧牲一些吞吐率為代價的。
3．Preemptible Kernel (Low-Latency Desktop)，這種模式既包含了自願搶占，又使能了可搶占內核選項，因此有很好的響應延遲，實際上在一定程度上已經達到了軟實時性。它主要適用於桌面和一些嵌入式系統，但是吞吐率比模式2更低。
4．Complete Preemption (Real-Time)，這種模式使能了所有實時功能，因此完全能夠滿足軟實時需求，它適用於延遲要求為100微秒或稍低的實時系統。
實現實時是以犧牲系統的吞吐率為代價的，因此實時性越好，系統吞吐率就越低。

㈤ 虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎

虛擬存儲器採用的頁面調度演算法是「先進先出」（FIFO）演算法嗎。常見的替換演算法有4種。

①隨機演算法：用軟體或硬體隨機數產生器確定替換的頁面。

②先進先出：先調入主存的頁面先替換。

③近期最少使用演算法（LRU，Least Recently Used）：替換最長時間不用的頁面。

④最優演算法：替換最長時間以後才使用的頁面。這是理想化的演算法，只能作為衡量其他各種演算法優劣的標准。

虛擬存儲器的效率是系統性能評價的重要內容，它與主存容量、頁面大小、命中率，程序局部性和替換演算法等因素有關。

(5)先進先出調度演算法擴展閱讀

虛擬存儲器地址變換基本上有3種形虛擬存儲器工作過程式：全聯想變換、直接變換和組聯想變換。任何邏輯空間頁面能夠變換到物理空間任何頁面位置的方式稱為全聯想變換。每個邏輯空間頁面只能變換到物理空間一個特定頁面的方式稱為直接變換。

組聯想變換是指各組之間是直接變換，而組內各頁間則是全聯想變換。替換規則用來確定替換主存中哪一部分，以便騰空部分主存，存放來自輔存要調入的那部分內容。

在段式虛擬存儲系統中，虛擬地址由段號和段內地址組成，虛擬地址到實存地址的變換通過段表來實現。每個程序設置一個段表，段表的每一個表項對應一個段，每個表項至少包括三個欄位：有效位(指明該段是否已經調入主存)、段起址(該段在實存中的首地址)和段長(記錄該段的實際長度)。

㈥ 操作系統先進先出(FIFO)和先來先服務(FCFS)有什麼區別

1.先來先服務調度演算法（FCFS）:就是按照各個作業進入系統的自然次序來調度作業。這種調度演算法的優點是實現簡單，公平。其缺點是沒有考慮到系統中各種資源的綜合使用情況，往往使短作業的用戶不滿意，因為短作業等待處理的時間可能比實際運行時間長得多。

2.先進先出演算法(FIFO)：按照進程進入就緒隊列的先後次序來選擇。即每當進入進程調度，總是把就緒隊列的隊首進程投入運行。

㈦ 頁面淘汰演算法

LRU（2個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺頁中斷18次

LRU（4個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺頁中斷次數10次

FIFO（2個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺頁中斷次數18次

FIFO（4個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺頁中斷次數：14次

㈧ hrn演算法調度順序是怎樣確定的

FIFO：即先進先出演算法，就是先進去的頁在位置不夠時先淘汰。所以具體如下：
主存開始為空
訪問1，1不在主存中，產生缺頁中斷，添加，主存里現在是：1
訪問2，2不在主存中，產生缺頁中斷，添加，主存里現在是：1,2
以此類推，
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
訪問4，4不在主存中，缺頁中斷，主存滿了，最早的1淘汰，主存里現在是：2,3,6,4
然後3,6,4,7（缺頁中斷，2淘汰）
然後3，3在主存中，不產生中斷
然後6,4,7,2（缺頁中斷，3淘汰）
4,7,2,1（缺頁中斷，6淘汰）
4在主存中，不中斷
7在主存中，不中斷
7,2,1,5（缺頁中斷，4淘汰）
2,1,5,6（缺頁中斷，7淘汰）
5在主存中，不中斷
2在主存中，不中斷
1在主存中，不中斷
整個FIFO過程就是這樣。

LRU是最近最久未使用的先淘汰，具體如下：
1（缺頁中斷）
1,2（缺頁中斷）
1,2,3（缺頁中斷）
1,2,3,6（缺頁中斷）
2,3,6,4（缺頁中斷，1最久沒用過，淘汰）
3,6,4,7（缺頁中斷，2最久沒用過，淘汰）
3在主存中，不中斷，3最近使用過，主存中順序調整為6,4,7,3
4,7,3,2（缺頁中斷，6最久沒用過，淘汰）
7,3,2,1（缺頁中斷，4最久沒用過，淘汰）
3,2,1,4（缺頁中斷，7最久沒用過，淘汰）
2,1,4,7（缺頁中斷，3最久沒用過，淘汰）
1,4,7,5（缺頁中斷，2最久沒用過，淘汰）
4,7,5,6（缺頁中斷，1最久沒用過，淘汰）
5在主存中，調整順序為4,7,6,5
7,6,5,2（缺頁中斷，4最久沒用過，淘汰）
6,5,2,1（缺頁中斷，7最久沒用過，淘汰）
整個LRU過程就是這樣。

全手打求採納謝謝~！如有問題請追問~

㈨ 最佳頁面淘汰演算法是怎樣計算的

<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%

㈩ 什麼是進程調度常用的進程調度演算法有哪些試比較他們之間的性能。 什麼是進程調度

進程調度，用戶進程數進程調度一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。無論是在批處理系統還是分時系統中，用戶進程數 進程調度 一般都多於處理機數、這將導致它們互相爭奪處理機。另外，系統進程也同樣需要使用處理機。這就要求進程調度程序按一定的策略，動態地把處理機分配給處於就緒隊列中的某一個進程，以使之執行。 進程調度的的分級 高級、中級和低級調度作業從提交開始直到完成，往往要經歷下述三級調度： 高級調度：(High-Level Scheling)又稱為作業調度，它決定把後備作業調入內存運行； 低級調度：(Low-Level Scheling)又稱為進程調度，它決定把就緒隊列的某進程獲得CPU； 中級調度：(Intermediate-Level Scheling)又稱為在虛擬存儲器中引入，在內、外存對換區進行進程對換。先進先出演算法 進程調度 演算法總是把處理機分配給最先進入就緒隊列的進程，一個進程一旦分得處理機，便一直執行下去，直到該進程完成或阻塞時，才釋放處理機。 例如，有三個進程P1、P2和P3先後進入就緒隊列，它們的執行期分別是21、6和3個單位時間， 執行情況如下圖： 對於P1、P2、P3的周轉時間為21、27、30，平均周轉時間為26。 可見，FIFO演算法服務質量不佳，容易引起作業用戶不滿，常作為一種輔助調度演算法。 最短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執行期，而只能根據每一個進程的執行歷史來預測。 輪轉法 前幾種演算法主要用於批處理系統中，不能作為分時系統中的主調度演算法，在分時系統中，都採用時間片輪轉法。 簡單輪轉法：系統將所有就緒進程按FIFO規則排隊，按一定的時間間隔把處理機分配給隊列中的進程。這樣，就緒隊列中所有進程均可獲得一個時間片的處理機而運行。 多級隊列方法：將系統中所有進程分成若干類，每類為一級。 多級反饋隊列 多級反饋隊列方式是在系統中設置多個就緒隊列，並賦予各隊列以不同的優先權