操作系統fifo演算法

⑴ 操作系統中在FIFO演算法中，缺頁中斷率是什麼怎麼計算

FIFO是先進先出演算法，當CPU需要訪問的頁不在內存中時產生了缺頁中斷，缺頁中斷是一段程序就是把外存中的頁調入內存，還需要把內存中原有的頁放回到外存。缺頁中斷率就是一個進程執行過程中缺頁的次數除以需訪問頁的總次數得到缺頁中斷率，這個值越小越好。

⑵ 操作系統先進先出演算法（FIFO）和先來先服務演算法（FCFS）有啥本質區別嗎 為什麼感覺一樣

這兩個是確實一樣的，但是有時候會說FCFS演算法常常用FIFO隊列來實現。

⑶ 操作系統題LRU，FIFO演算法怎麼做

其實這種題目是非常簡單的：

頁號：2,3,2,1,4,5,2,4,5,1,3,2,5,2
O: 1 3 4 1 共有4次中斷
F: 2 3 1 4 5 2 1 共有7次中斷
C: 3 2 1 2 4 5 1 共有7次中斷
L: 3 1 2 4 5 1 共有6次中斷

⑷ FIFO和LRU小結

 一:FIFO演算法

     1.0,FIFO (First in First out) 先進先出(核心原則:最先進來的,最先淘汰); 其實在操作系統的設計理念中很多地方都是利用到了先進先出的思想就是因為這個原則簡單切符合人們的慣性思維,具備公平性實現起來也簡單,直接使用數據結構中的隊列即可實現

     1.1,在FIFO 中應該支持這些操作: 一,get(key),如果Cache中存在該key,則返回對應的value值,否則返回 -1; 二,set(key,value),如果Cache中存在該key,則重置value值,如果不存在則將該key插入到Cache中,若Cache已滿則淘汰最先進入Cache的數據

     1.2,那麼利用什麼數據結構來實現呢?有這一種思路, 利用一個雙向鏈表保存數據,當來了新數據之後便添加到鏈表末尾,如果Cache存滿數據,則把鏈表頭部數據刪除,然後把次年數據添加到鏈表末尾,在訪問數據的時候,如果在Cache中存在該數據的話,則返回對應的value值,否則返回 -1,如果想提高訪問效率,可以利用hashmap來保存每個key在鏈表中的位置(參考下面拓展)

     二:LRU演算法

     1.0,LRU (Least recently used) 最近最久未使用調度,其核心思想是"如果數據最近被訪問過,那麼將來被訪問的幾率也更高"; 最常見的實現是使用一個鏈表保存緩存數據,詳細演算法實現如下:

       1,新數據插入到鏈表頭部

       2,每當緩存命中(即緩存數據被訪問),則將數據移到鏈表頭部;

       3,當鏈表滿的時候,將鏈表尾部的數據丟棄

     1.1,LRU的優缺點 1.命中率,當存在熱點數據時,LRU的效率很好,但偶發性的,周期性的批量操作會導致LRU命中率急劇下降,緩存污染情況比較嚴重 2,實現相對簡單 3,命中時需要遍歷鏈表,找到命中的數據塊索引,然後需要將數據移到頭部

     2.0,LRU-K K代表最近使用的次數,因此LRU也可以認為是LRU-1,它主要是為了解決LRU演算法"緩存污染"的問題,其核心思想是將"最近使用過1次"的判斷標准擴展為"最近使用過K次"; 相比LRU要多維護一個隊列,用於記錄所有緩存數據被訪問的歷史,只有當數據的訪問次數達到K次的時候,才將數據放入緩存.當需要淘汰數據時,LRU-k會淘汰第K次訪問時間距離當前時間最大的數據.詳細實現如下:

     2.1,一,數據第一次被訪問,加入到訪問歷史列表; 二,如果數據在訪問歷史列表裡後達到K次訪問,則按照一定(FIFO, LRU)淘汰; 三,當訪問歷史隊列中的數據訪問次數達到k次後,將數據l索引從歷史隊列刪除,將數據移到緩存隊列中,並緩存此數據,緩存隊列重新按照時間排序; 四,緩存數據隊列中被再次訪問後,重新排序; 五,需要淘汰數據時,淘汰緩存隊列中排在末尾的數據(即:淘汰倒數第K次訪問離現在最久的數據)

     2.2,LRU-K具有LRU的優點,同時能夠避免LRU的缺點,實際應用中LRU-2是綜合各種因素後最優的選擇,LRU-3或者更大的K值命中率會高,但適應性差,需要大量的數據訪問才能將歷史記錄緩存或者清除掉

     2.3優缺,LRU-K降低了"緩存污染"帶來的問題,命中率比LRU要高,但LRU-K隊列是一個優先順序隊列,演算法復雜度和代價相對LRU較高,並且LRU需要記錄那些被訪問過,但是沒有達到K次也就是還沒有放入緩存的對象,因此b內存消耗會比LRU要多,當然如果數據量很大的時候,內存消耗會比較可觀

     3.0,Two queues (2Q) 演算法類似於LRU-2,不同點在於2Q將LRU-2演算法中的訪問歷史隊列(歷史隊列,還沒有緩存數據)改為一個FIFO緩存隊列,即: 2Q演算法有兩個緩存隊列,一個是FIFO隊列,一個是LRU隊列.

     3.1,當數據第一次訪問時,2Q演算法會將數據緩存在FIFO隊列裡面,當數據第二次被訪問時,則將數據從FIFO隊列移到LRU隊列裡面,兩個隊列各自按照自己的方法淘汰數據; 一,新訪問的數據插入到FIFO隊列, 二,如果數據在FIFO隊列中一直沒有被再次訪問,則最終按照FOFO規則淘汰, 三,如果數據在FIFO隊列中被再次訪問,則將數據移到LRU隊列頭部, 四,如果數據在LRU隊列再次被訪問,則將數據移到LRU隊列頭部, 五,LRU隊列淘汰末尾的數據

     3.2,可能會感覺FIFO隊列比LRU隊列短,但並不代表這是演算法的要求,實際應用中兩者比例沒有硬性要求

     3.3,2Q演算法命中率高於LRU,切需要兩個隊列,但兩個隊列本身都比較簡單,代價是FIFO和LRU代價之和; 2Q演算法和LRU-2演算法命中率類似,內存消耗也比較接近,但對於最後的緩存數據來說,2Q減少一次從原始儲存讀取數據或者計算數據的操作

     4.0,Multi Queue (MQ) 演算法根據訪問頻率將數據劃分為多個隊列,不同的隊列具有不同的訪問優先順序,其核心思想是:優先緩存訪問次數多的數據

     4.1,MQ演算法將緩存劃分為多個LRU隊列,每個隊列對應不同的訪問優先順序,訪問優先順序是根據訪問次數計算出來的,詳情: 一,新插入的數據放入Q0; 二,每個隊列按照LRU管理數據; 三,當數據訪問次數達到一定次數需要提升優先順序時將數據從當前隊列刪除,加入到高一級的隊列頭部; 四,為了防止高優先順序數據永遠不被淘汰,每個隊列淘汰數據時,將數據從緩存中刪除,將數據加入Q-history頭部; 五,需要淘汰數據時,從最低一級隊列開始按照LRU淘汰,每個隊列淘汰數據時,將數據從緩存中刪除,將數據索引加入Q-history頭部; 六,如果數據在Q-history中被重新訪問,則重新計算其優先順序,移到目標隊列的頭部; 七,Q-history按照LRU淘汰數據的索引

     4.2,MQ降低了"緩存污染"帶來的問題,命中率比LRU高,但MQ需要維護多個隊列,切需要維護每個數據的訪問時間,復雜度比較高,並且MQ需要記錄每個數據的訪問時間,需要定時掃碼所有隊列,代價也比較高

     4.3,雖然MQ的隊列看起來數量比較多,但由於所有隊列之和受限於緩存容量的大小,因此這里多個隊列長度之和和一個LRU隊列是一樣的,因此隊列掃碼性能接近

     小結: 命中率  LRU-2 > MQ(2) > 2Q > LRU ; 復雜度 LRU-2 > MQ(2) > 2Q >LRU ; 代價 LRU-2 > MQ(2) > 2Q > LRU ; 需要注意的是,命中率並不是越高越好,實際中應該根據業務需求和對數據的訪問情況進行分析選擇,LRU雖然看起來命中率低一些,切存在"緩存污染"的問題,但其簡單切代價小,實際中反而應用更多

     拓展:基於 雙鏈表的 LRU 實現: 一,傳統意義的LRU演算法是每一個Cache對象設置一個定時器,每次Cache命中則給定時器 +1,而Cache用完需要淘汰舊內容,放置新內容時就查看所有的計時器,並將使用的內容替換掉; 其弊端很明顯,如果Cache的數量少,問題不大,但如果Cache的空間過大,達到10W或者100W以上,一旦需要淘汰,則需要遍歷所有計時器,其性能與資源消耗巨大,效率也就非常的慢了; 二,雙鏈表原理,將Cache的所有位置都用雙鏈表連接起來,當一個位置被命中之後,就將通過調整鏈表的指向,將該位置調整到鏈表頭的位置,新加入Cache直接加到鏈表頭中,這樣在多次進行Cache操作後,最近被命中的就會被向鏈表頭方向移動,而沒有命中的則向鏈表後部移動,鏈表尾則表示最近最少命中的Cache,當需要替換內容時我們只需要淘汰鏈表最後的部分即可!

如果錯誤或者建議,歡迎下方留言,謝謝!

⑸ 什麼是FIFO

FIFO是First Input First Output的縮寫，先入先出隊列，這是一種傳統的按序執行方法，先進入的指令先完成並引退，跟著才執行第二條指令。

是一種先進先出的數據緩存器，它與普通存儲器的區別是沒有外部讀寫地址線，這樣使用起來非常簡單。

但缺點就是只能順序寫入數據，順序讀出數據，其數據地址由內部讀寫指針自動加1完成，不能像普通存儲器那樣可以由地址線決定讀取或寫入某個指定的地址。

⑹ 如何用java實現fifo頁面置換演算法

[fifo.rar] - 操作系統中內存頁面的先進先出的替換演算法fifo
[先進先出頁面演算法程序.rar] - 分別實現最佳置換演算法(optimal)、先進先出(fifo)頁面置換演算法和最近最久未使用（LRU）置換演算法，並給出各演算法缺頁次數和缺頁率。
[0022.rar] - 模擬分頁式虛擬存儲管理中硬體的地址轉換和缺頁中斷，以及選擇頁面調度演算法處理缺頁中斷
[Change.rar] - 用java實現操作系統的頁面置換 其中包括 最佳置換演算法(Optimal)、先進先出演算法（First-in, First-out） 、最近最久不用的頁面置換演算法（LeastRecently Used Replacement）三種演算法的實現
[M_Management.rar] - 操作系統中內存管理頁面置換演算法的模擬程序，採用的是LRU置換演算法
[detail_of_44b0x_TCPIP.rar] - TCPIP 程序包載入到44b0x 的ADS1.2工程文件的說明書。說名了載入過程的細節和如何處理演示程序和代碼。演示代碼已經上傳，大家可以搜索
[.rar] - java操作系統頁面置換演算法： （1）進先出的演算法（fifo） （2）最近最少使用的演算法（LRU） （3）最佳淘汰演算法(OPT) （4）最少訪問頁面演算法(LFU) （註：由本人改成改進型Clock演算法） （5）最近最不經常使用演算法(NUR)

⑺ 操作系統題：頁面置換演算法 OPT FIFO LRU

fifo就是先進先出，可以想像成隊列
lru是最久未使用，當需要替換頁面的時候，向前面看，最久沒使用的那個被替換
opt是替換頁面的時候，優先替換後面最遲出現的。
不懂再問。。

⑻ 操作系統頁面置換演算法：第二次機會演算法是什麼

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

⑼ 操作系統 頁式管理中的置換演算法 怎麼看缺頁

去年學過，現在記憶殘缺，盡量回答
FIFO演算法是先入先出演算法吧，首先是有三個頁面，所以一列只有三行
再者，根據先入先出的規則，後面讀取的串替代內存中進來時間最久的串，若當前讀取的串內存中已經有了，則內存中的頁面不變
缺頁就是沒有重復的頁面，即沒有重復的頁面共有10頁，就缺頁10次
LRU LFU就是看訪問串前面或者後面會不會有使用到，具體哪個我忘了，把FIFO看明白了你就曉得了
FIFO：
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0
空0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1
空空1 1 1 1 0 0 0 3 3 3 3 3 2 2 2
你的打錯了吧
PS:我上面說缺頁10頁是隨便舉的例子，題目中的缺頁數是12，缺頁不是很好計算的么，就是沒有內容重復的內存頁，數一下就知道了，還不知道就留言我吧

⑽ 操作系統原理與應用之 頁面調度演算法問題

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過程就是這樣。

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