操作系統淘汰算法

操作系統淘汰算法

　　操作系統中的內存淘汰算法主要有三種。下面由學習啦小編為大家整理了操作系統淘汰算法的相關知識，希望對大家有幫助!

　　操作系統淘汰算法詳解

　　操作系統淘汰算法1，LRU(Least Recently Used，最少最近使用算法)

　　計時法:給頁表中的每一頁增加一個域，專門用來存放計時標志，用來記錄該頁面自上次被訪問以來所經歷的時間。頁面每被訪問一次，計時清0。要裝入新頁時，從內存的頁面中選出時間最長的一頁，調出，同時把各頁的計時標志全部清0，重新開始計時。 計時法可以稍作改變，成為計數法：頁面被訪問，計數標志清0，其余所有內存頁面計數器加1;要裝入新頁時，選出計數最大的一頁調出，同時所有計數器清0。

　　鏈表法:操作系統為每個進程維護一條鏈表，鏈表的每個結點記錄一張頁面的地址。調用一次頁面，則把該頁面的結點從鏈中取出，放到鏈尾;要裝入新頁，則把鏈頭的頁面調出，同時生成調入頁面的結點，放到鏈尾。鏈表法可看作簡單計時/計數法的改良，維護一個鏈表，自然要比維護所有頁面標志要簡單和輕松?？墒牵@并沒有在數量級上改變算法的時間復雜度，每調用一個頁面，都要在鏈表中搜尋對應結點并放至鏈尾的工作量并不算小。

　　操作系統淘汰算法2，FIFO(先進先出算法)

　　顧名思義，最先被置換進內存的頁面最先出來，公正公平，大家都別搶，但是不一定合理，能者要多勞啊。

　　最先進去的頁面，比如一些初始化性質的頁面，通常在整個程序運行期間都是需要，被置換出去非常不合理。

　　操作系統淘汰算法3，NRU(Not Recently Used，最近未使用算法，又稱CLK算法)

　　a. 給每一幀關聯一個附加位，稱為使用位

　　b. 當某一頁首次裝入主存時，該幀的使用位設置為1

　　c. 當該頁隨后再被訪問到時，它的使用位也被置為1

　　d. 對于頁替換算法，用于替換的候選幀集合看做一個循環緩沖區，并且有一個指針與之相關聯

　　e. 當某一頁被替換時，該指針被設置成指向緩沖區中的下一幀

　　f. 當需要替換一頁時，操作系統掃描緩沖區，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，操作系統就將該位重新置為0

　　g. 如果在這個過程開始時，緩沖區中所有幀的使用位均為0，則選擇遇到的第一個幀替換

　　h. 如果所有幀的使用位均為1,則指針在緩沖區中完整地循環一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁