二次機會置換演算法

㈠ OPT頁面置換演算法最優性證明。

1常見的置換演算法

1．最佳置換演算法（OPT）（理想置換演算法）：所選擇的被淘汰頁面將是以後永不使用的，或者是在最長時間內不再被訪問的頁面，這樣可以保證獲得最低的缺頁率。2．先進先出置換殲燃談演算法（FIFO）：優先淘汰最早進入的頁面，亦即在內存中駐留時間最久的頁面。3．最近最久未使用（LRU）演算法：選擇最近氏碰最長時間未訪問過的頁面予以淘汰。4．Clock置換演算法（LRU演算法的近似實現）：給每一幀關聯一個附加位，稱為使用位。5．最少使用（LFU）置換演算法6．工作集演算法7 . 工作集時鍾演算法8. 老化演算法（非常類似LRU的有效演算法）9. NRU(最近未使用）演算法10. 第二次機會演算法2操作系統頁面置換演算法代碼#include <stdio.h>^[1]#include <stdlib.h>#include <unistd.h> #define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /*指令流長*/#define total_vp 32 /*虛頁長*/#define clear_period 50 /*清段弊零周期*/typedef struct{ /*頁面結構*/int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp]; /*頁面結構數組*/struct pfc_struct{ /*頁面控制結構*/int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];void initialize(int);void FIFO(int);void LRU(int);void NUR(int);int main(){int S,i;srand((int)getpid());S=(int)rand()%390;for(i=0;i<total_instruction;i+=1) /*產生指令隊列*/{a[i]=S; /*任選一指令訪問點*/a[i+1]=a[i]+1; /*順序執行一條指令*/a[i+2]=(int)rand()%390; /*執行前地址指令m』*/a[i+3]=a[i+2]+1; /*執行後地址指令*/S=(int)rand()%390;}for(i=0;i<total_instruction;i++) /*將指令序列變換成頁地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) /*用戶內存工作區從4個頁面到32個頁面*/{printf("%2d page frames",i);FIFO(i);LRU(i);NUR(i);printf(" ");}return 0;}void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*//*用戶進程的內存頁面數*/{int i;pfc_type *p, *t;initialize(total_pf); /*初始化相關頁面控制用數據結構*/busypf_head=busypf_tail=NUL; /*忙頁面隊列頭，對列尾鏈接*/for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*頁面失效*/{diseffect+=1; /*失效次數*/if(freepf_head==NUL) /*無空閑頁面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID; /*釋放忙頁面隊列中的第一個頁面*/freepf_head=busypf_head;freepf_head->next=NUL;busypf_head=p;}p=freepf_head->next; /*按方式調新頁面入內存頁面*/freepf_head->next=NUL;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NUL)busypf_head=busypf_tail=freepf_head;else{busypf_tail->next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}printf("FIFO:%6.4F",1-(float)diseffect/320);}void LRU(int total_pf){int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*頁面失效*/{diseffect++;if(freepf_head==NUL) /*無空閑頁面*/{min=32767;for(j=0;j<total_vp;j++)if(min>pl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;}elsepl[page[i]].time=present_time;present_time++;}printf("LRU:%6.4f",1-(float)diseffect/320);}void NUR(int total_pf){int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*頁面失效*/{diseffect++;if(freepf_head==NUL) /*無空閑頁面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f",1-(float)diseffect/320);}void initialize(int total_pf) /*初始化相關數據結構*//*用戶進程的內存頁面數*/{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID; /*置頁面控制結構中的頁號，頁面為空*/pl[i].counter=0;pl[i].time=-1; /*頁面控制結構中的訪問次數為0，時間為-1*/}for(i=1;i<total_pf;i++){pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之間的連接*/}pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0]; /*頁面隊列的頭指針為pfc[0]*/}/*說明：本程序在linux的gcc下和c-free下編譯運行通過*/【http://wenku..com/link?url=o_】
不知道能不能打開-是復制的 但也辛苦半天 忘採納~

㈡ 頁面置換演算法的常見的置換演算法

最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。理由是：最早調入內存的頁，其不再被使用的可能性比剛調入內存的可能性大。建立一個FIFO隊列，收容所有在內存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內存時，就把它插在隊尾上。
這種演算法只是在按線性順序訪問地址空間 時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。
FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。
FIFO演算法和OPT演算法之間的主要差別是，FIFO演算法利用頁面進入內存後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間里最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。
LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間里最久未被使用的頁面。
LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。LRU演算法需要實際硬體的支持。其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法：
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位，並給CPU增加一個邏輯時鍾或計數器。每次存儲訪問，該時鍾都加1。每當訪問一個頁面時，時鍾寄存器的內容就被復制到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要 維護這個頁表中的時間，還要考慮到時鍾值溢出的問題。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。
因實現LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似演算法。
一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。
4）Clock置換演算法（LRU演算法的近似實現）
5）最少使用（LFU）置換演算法
在採用最少使用置換演算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪 問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。
LFU置換演算法的頁面訪問圖與LRU置換演算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。
6）工作集演算法
7）工作集時鍾演算法
8）老化演算法（非常類似LRU的有效演算法）
9）NRU(最近未使用）演算法
10）第二次機會演算法
第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是 0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。
第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

㈢ 12、存儲模型2（操作系統筆記）

我們將虛擬存儲技術吵尺和頁式存儲管理方案結合起來得到了虛擬頁式存儲管理系統。具體有兩種方式，一是請求調頁，二是預先調頁。以 cpu 時間和磁碟換缺碰旁取昂貴內存空間，這是操作系統中的資源轉換技術。

通常，頁表項是硬體設計的。

為什麼要鎖定頁面？

又稱頁面淘汰演算法。最佳演算法-->先進先出-->第二次機會-->時鍾演算法-->最近未使用-->最近最少使用-->最不經常使用-->老化演算法-->工作集-->工作集時鍾

在先進先出演算法的基礎上進行該機而來的，此演算法按照先進先出演算法選擇某一頁面，檢查其訪問位 R ，如果為 0 ，則置換該頁；如果為 1 ，則給第二次機會，並將訪問位置零，並將其從鏈頭取下放到鏈尾。

在第二次機會演算法中當給某個頁面第二伏橡次機會的時候，將其訪問位置零，然後將其掛到鏈尾，這都是需要開銷的，於是我們改進為時鍾演算法。

選擇最後一次訪問時間距離當前時間最長的一頁並置換，即置換未使用時間最長的一頁。

即 Not frequently Used ，選擇訪問次數最少的頁面置換

例子：

要求：
計算應用 FIFO、LRU、OPT 演算法時的缺頁次數

應用 FIFO、LRU 頁面置換演算法

應用OPT頁面置換演算法

例子：系統給某進程分配 m 個頁框，初始為空頁面訪問順序為
1 2 3 4 1 2 5 1 2 3 4 5 ，採用 FIFO 演算法，計算當 m=3 和 m=4 時的缺頁中斷次數。
結論： m=3 時，缺頁中斷九次； m=4 時，缺頁中斷十次。注意： FIFO 頁面置換演算法會產生異常現象（ Belady 現象），即：當分配給進程的物理頁面數增加時，缺頁次數反而增加。

缺頁越多，系統的性能越差，這稱為顛簸（抖動）：虛存中，頁面在內存與磁碟之間頻繁調度，使得調度頁面所需的時間比進程實際運行的時間還多，這樣導致系統效率急劇下降，這種現象稱為顛簸或抖動。

例子：
分配了一個頁框，頁面大小為 128 個整數，矩陣 A(128 x 128) 按行存放。

如果能為進程提供與活躍頁面數相等的物理頁面數，則可減少缺頁中斷次數，這是由 Denning 提出的。

㈣ 經驗交流：科目二考試兩次機會怎麼用

1、考試時有兩次灶寬機會，要求每次機會五個項目都要合格，如果有一項不合格，則五個項目都要重考。

2、如果第一次機會考試不合格，接著就進行第二次考試，考試流程跟第一次相同，而且是同一輛車、同一條考道，第二次補考和第一次考試一樣，上車准備時一定要調好座椅、後視鏡、系好安全帶後才能驗證指紋。

把握好第二次考試機會

一、找到第一次失敗的原因，及時調整

剛上場就納大掛科，不洞辯豎少小夥伴都很是受挫。想要第二次考試過關，必須要找到失敗的原因，及時調整對策。科二考試中如果是倒庫時壓線了，就要想想是不是點看晚了；如果是因為坡道起步熄火了，第二次考試的時候就要小心點了，抬離合的過程中不能著急，一定要等離合器到了半聯動點再松開。

二、調整好心態

科二第一次掛了，很多學員一下子就慌了，導致第二次考試更加緊張，更容易出錯了。其實，第一次掛科是很普遍的現象，不適應考試車輛、考試緊張等都會導致第一次發揮失常。所以，第一次考試就當是熟悉考場了，適應下考試車輛，這樣第二次過關的幾率就更大了。

㈤ 2次機會，第1次70%拿到紅球，第2次55%拿到紅球。總的來說拿到多少機率拿到紅球 怎麼算

如果是兩次都必須拿到紅球，那麼概率轎碼是70%x55%=38.5%

如果是兩次其中任何一次拿到紅球都可以，那麼概率是1-（1-70%）x（1-55%）=86.5%

除掉兩次都沒有拿到紅球這斗帆滲種情況，當然就至少拿到一次了。
第一次沒拿到1-70%，第二次沒拿到1-55%，兩次都沒有拿空脊到（1-70%）x（1-55%）=13.5%
1-13.5%=86.5%

㈥ 求一段C語言代碼，實現近似LRU頁置換，運用二次機會演算法。

二次機會演算法我有。
但是我不明白你說的內存幀數是什麼意思。是內存物理塊的意思嗎？
錯誤頁數又是什麼意思呢？

㈦ 對於問題小孩這門課所學所識有什麼啟發

我做了這么多年幼師，一直在想幼兒園的小孩是否全部都是天真快樂呢？是否全部都能友好相處呢？這些問題一直縈繞在我的心中，直到我讀了《幼兒園里的「問題小孩」》,我這個疑惑的雲朵才被撥開。

對於《幼兒園里的「問題小孩」》此鄭這一本書的總體評價，我認為這是一本基於作者理論學養於實踐經驗的原創之作，站在一個幼師的角度，我認為要以身作則，去在現實中發現書中存在的「問前扒老題」小孩，學會更多的專業知識去輔導孩子的心理，引導他們積極向上，懂得生活的美好。

在書中，論述圍繞幼兒園課程的課程價值，分析了幼兒園教學內容有別於其他階段的特質，從課程與教學的視角，澄清了長期以來幼兒園教育設計中諸多群體性、無意識的錯誤做法。語言淺白通俗又不失學理思考，雖脫胎於日常的授課講義，又從讀者的閱讀心理出發設計了靈動的閱讀結構，為職前、職後的幼兒園教師提供了有價值的學習與指導。

書中描述的一個很典型的現象就是幼兒的「隱蔽性」說謊，是指幼兒在特定環境下因為某種原因而隱蔽地說謊，這對剛處在萌芽階段的幼兒有很不利的影響。由於幼兒「心靈的純潔」，他們在真實的偽裝下說謊時，往往會顯得很不自然，對他們心靈的摧殘也是顯而易見的，因此，教導幼兒學會真誠，多和幼兒熟悉，多聽他們的心事，也是我讀完這本書的一個很大的感悟。

書中描述的幼兒園中存在的問題小孩主要有下面這八個問題：磨蹭、倔強、叛逆、暴力、吹牛、撒謊、孤僻，這些都是一個人成長中起阻礙的消極慧升面，書中主要描寫了從行為規范、心理健康、培養個性、解決叛逆等問題入手，以幼兒園和家長的雙角度去更好地描述這本書的主題思想，帶給普世大眾對幼兒園教育中的解決。其中，書中展現的「榜樣模範」也是讓我記憶尤深的，一個好的集體需要好的帶領人，在幼兒中建立榜樣模範，可以讓幼兒培養良好的習慣，汲取優秀的品質從而培養真誠善良的性格，良好的學習升高習慣，有益於幼兒集體的發展。

總之，幼兒園里的孩子作為稚嫩的花朵，必然需要社會上人們的關懷，作為幼兒園老師和家長，我們要學會用愛去鼓勵孩子，去呵護每一個嬌嫩的花朵，使他們尋回自信和堅強，讓他們能以更好的姿態去迎接生活中的困難，去呵護每一個幼兒園孩子，培養他們優良的品格，成為國家未來的中流砥柱.

㈧ lru演算法是什麼

lru演算法是一種常用的頁面置換演算法，選擇最近最久未使用的頁面予以淘汰。

該演算法賦予每個頁面一個訪問欄位，用來記錄一個頁面自上次被訪問以來所經歷的時間 t，當須淘汰一個頁面時，選擇現有頁面中其 t 值最大的，即最近最少使用的頁面予以淘汰。

特點：

LRU 置換演算法雖然是一種比較好的演算法，但要求系統有較多的支持硬體。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有兩類硬體之一的支持：寄存器或棧。

在進程運行過程中，若其所要訪問的頁面不在內存而需把它們調入內存，但內存已無空閑空間時，為了保證該進程能正常運行，系統必須從內存中調出一頁程序或數據送磁碟的對換區中。

㈨ 現代操作系統的作品目錄

前言
1 引言 1
1．1 什麼是操作系統? 3
1．1．1 所有延長機器的作業系統 4
1．1．2 作為一個資源管理器的作業系統 6
1．2 操作系統的歷史 7
1．2．1 第一代（1945年至1955年）真空管 7
1．2．2第二代（1955年至1965年）晶體管和批處理系統 8
1．2．3 第三代（1965年至1980年）的集成電路 10
1．2 4 第四代（1980年至今）個人電腦 15
1．3計算機硬體檢查 19
l．3．1處理器 19
1．3．2內存 23
1．3．3 磁碟 26
1．3．4 膠帶 27
1．3．5 I/O設備 27 (I/O即輸入輸出)
1．3．6匯流排 30
1 3．7啟動計算機 33
1．4 操作系統動物園 33
1．4．1大型機操作系統 34
1．4．2 伺服器操作系統34
1．4．3多處理器的操作系統 34
1．4．4個人電腦操作系統 35
1．4．5掌上電腦操作系統 35
1．4．6 嵌入式操作系統． 35
1．4．7 感測器節點的操作系統 36
1．4．8 實時操作系統 36
1．4．9 智能卡操作系統 37
1．5操作系統的概念 37
1．5．1 流程 38
1．5．2 地址空間 40
1．5．3文件 40
1．5．4輸入/輸出 43
1．5．5保護 44
1．5．6 殼牌 44
1．5．7系統發育個體發育重演 46
1．6 系統調用 49
1．6．1 流程管理系統調用 52
1．6．2文件管理系統調用 56
1．6．3 目錄管理系統調用 57
1．6．4雜項系統調用 58
1．6．5 在Windows的Win32 API 59
1．7 操作系統結構 62
1．7．1單片系統 62
1．7．2分層系統 63
1．7．3微內核 64
1．7．4 客戶 - 伺服器模型 67
1．7．5 虛擬機 67
1．7．6 出的內核 71
1．8 根據C的WORLD 72
1．8．1 C語言 72
1．8．2頭文件 73
1．8．3大的編程項目 74
1．8．4運行時模型75
1．9操作系統上的研究 76
1．10 本書的其餘部分的概要 77
1．11 公制單位 78
1．12 概要 79
2進程和線程
2．1工序83
2．1．1 過程模型 84
2．1．2 進程創建 86
2．1．3 進程終止 88
2．1．4 流程層次結構 89
2．1．5 進程國家 90
2．1．6實施流程 91
2．1．7多多建模的建模 93
2．2 螺紋 95
2．2．1線程使用情況 95
2．2．2古典的線程模型 100
2．2．3POSIX線程 104
2．2．4在用戶空間中實現的線程 106
2．2．5在內核中實現的線程 109
2．2．6混合實現 110
2．2．7調度激活 111
2．2．8 彈出式線程 112
2．2．9 使單線程代碼中使用多線程技術 114
2．3 進程間通信 117
2．3．1靜態條件 117
2．3．2關鍵區域 119
2．3．3忙等待的互斥 120
2．3．4 睡眠和喚醒 125
2．3．5 信號燈 128
2．3．6互斥 130
2．3．7顯示器 134
2．3．8消息傳遞 140
2．3．9 壁壘 144
2．4 調度 145
2．4．1調度 145
2．4．2 批處理系統的調度 152
2．4．3 調度互動系統 154
2．4．4 調度實時系統 160
2．4．5政策與機制 161
2．4．6 線程調度 162
2．5經典的IPC問題 163
2．5．1 哲學家就餐問題 164
2．5．2讀者和作者的問題 167
2．6 進程和線程的研究 168
2．7概要169
習題95第3章 存儲管理993.1 無存儲器抽象993.2 一種存儲器抽象：地址空間1013.2.1 地址空間的概念1013.2.2 交換技術1033.2.3 空閑內存管理1043.3 虛擬內存1063.3.1 分頁1073.3.2 頁表1083.3.3 加速分頁過程1093.3.4 針對大內存的頁表1113.4 頁面置換演算法1133.4.1 最優頁面置換演算法1143.4.2 最近未使用頁面置換演算法1143.4.3 先進先出頁面置換演算法1153.4.4 第二次機會頁面置換演算法1153.4.5 時鍾頁面置換演算法1163.4.6 最近最少使用頁面置換演算法1163.4.7 用軟體模擬lru 1173.4.8 工作集頁面置換演算法1183.4.9 工作集時鍾頁面置換演算法1203.4.10 頁面置換演算法小結1213.5 分頁系統中的設計問題1213.5.1 局部分配策略與全局分配策略1213.5.2 負載控制1233.5.3 頁面大小1233.5.4 分離的指令空間和數據空間1243.5.5 共享頁面1243.5.6 共享庫1253.5.7 內存映射文件1263.5.8 清除策略1273.5.9 虛擬內存介面1273.6 有關實現的問題1283.6.1 與分頁有關的工作1283.6.2 缺頁中斷處理1283.6.3 指令備份1293.6.4 鎖定內存中的頁面1293.6.5 後備存儲1293.6.6 策略和機制的分離1303.7 分段1313.7.1 純分段的實現1333.7.2 分段和分頁結合：multics 1343.7.3 分段和分頁結合：intel pentium 1353.8 有關存儲管理的研究1383.9 小結138習題139第4章 文件系統1434.1 文件1444.1.1 文件命名1444.1.2 文件結構1454.1.3 文件類型1454.1.4 文件存取1474.1.5 文件屬性1474.1.6 文件操作1484.1.7 使用文件系統調用的一個示常式序1484.2 目錄1504.2.1 一級目錄系統1504.2.2 層次目錄系統1504.2.3 路徑名1504.2.4 目錄操作1524.3 文件系統的實現1534.3.1 文件系統布局1534.3.2 文件的實現1534.3.3 目錄的實現1564.3.4 共享文件1584.3.5 日誌結構文件系統1594.3.6 日誌文件系統1604.3.7 虛擬文件系統1614.4 文件系統管理和優化1634.4.1 磁碟空間管理1634.4.2 文件系統備份1674.4.3 文件系統的一致性1704.4.4 文件系統性能1724.4.5 磁碟碎片整理1744.5 文件系統實例1754.5.1 cd-rom文件系統1754.5.2 ms-dos文件系統1784.5.3 unix v7文件系統1794.6 有關文件系統的研究1814.7 小結181習題182第5章 輸入/輸出1845.1 i/o硬體原理1845.1.1 i/o設備1845.1.2 設備控制器1855.1.3 內存映射i/o 1855.1.4 直接存儲器存取1875.1.5 重溫中斷1895.2 i/o軟體原理1915.2.1 i/o軟體的目標1915.2.2 程序控制i/o 1925.2.3 中斷驅動i/o 1935.2.4 使用dma的i/o1945.3 i/o軟體層次1945.3.1 中斷處理程序1945.3.2 設備驅動程序1955.3.3 與設備無關的i/o軟體1975.3.4 用戶空間的i/o軟體2005.4 盤2015.4.1 盤的硬體2015.4.2 磁碟格式化2115.4.3 磁碟臂調度演算法2125.4.4 錯誤處理2145.4.5 穩定存儲器2165.5 時鍾2185.5.1 時鍾硬體2185.5.2 時鍾軟體2195.5.3 軟定時器2205.6 用戶界面：鍵盤、滑鼠和監視器2215.6.1 輸入軟體2215.6.2 輸出軟體2245.7 瘦客戶機2335.8 電源管理2355.8.1 硬體問題2355.8.2 操作系統問題2365.8.3 應用程序問題2395.9 有關輸入/輸出的研究2395.10 小結240習題241第6章 死鎖2446.1 資源2446.1.1 可搶占資源和不可搶占資源2446.1.2 資源獲取2456.2 死鎖概述2466.2.1 資源死鎖的條件2466.2.2 死鎖建模2466.3 鴕鳥演算法2486.4 死鎖檢測和死鎖恢復2486.4.1 每種類型一個資源的死鎖檢測2496.4.2 每種類型多個資源的死鎖檢測2506.4.3 從死鎖中恢復2516.5 死鎖避免2526.5.1 資源軌跡圖2526.5.2 安全狀態和不安全狀態2536.5.3 單個資源的銀行家演算法2546.5.4 多個資源的銀行家演算法2546.6 死鎖預防2556.6.1 破壞互斥條件2556.6.2 破壞佔有和等待條件2566.6.3 破壞不可搶占條件2566.6.4 破壞環路等待條件2566.7 其他問題2576.7.1 兩階段加鎖2576.7.2 通信死鎖2576.7.3 活鎖2586.7.4 飢餓2596.8 有關死鎖的研究2596.9 小結259習題260第7章 多媒體操作系統2637.1 多媒體簡介2637.2 多媒體文件..2667.2.1 視頻編碼2667.2.2 音頻編碼2687.3 視頻壓縮2697.3.1 jpeg標准2697.3.2 mpeg標准2717.4 音頻壓縮2727.5 多媒體進程調度2747.5.1 調度同質進程2757.5.2 一般實時調度2757.5.3 速率單調調度2767.5.4 最早最終時限優先調度2777.6 多媒體文件系統范型2787.6.1 vcr控制功能2797.6.2 近似視頻點播2797.6.3 具有vcr功能的近似視頻點播2817.7 文件存放2827.7.1 在單個磁碟上存放文件2827.7.2 兩個替代的文件組織策略2827.7.3 近似視頻點播的文件存放2847.7.4 在單個磁碟上存放多個文件2857.7.5 在多個磁碟上存放文件2877.8 高速緩存2887.8.1 塊高速緩存2887.8.2 文件高速緩存2897.9 多媒體磁碟調度2907.9.1 靜態磁碟調度2907.9.2 動態磁碟調度2917.10 有關多媒體的研究2927.11 小結292習題293第8章 多處理機系統2958.1 多處理機2968.1.1 多處理機硬體2968.1.2 多處理機操作系統類型3018.1.3 多處理機同步3038.1.4 多處理機調度3068.2 多計算機3098.2.1 多計算機硬體3098.2.2 低層通信軟體3128.2.3 用戶層通信軟體3138.2.4 遠程過程調用3148.2.5 分布式共享存儲器3168.2.6 多計算機調度3198.2.7 負載平衡3198.3 虛擬化3218.3.1 虛擬化的條件3228.3.2 i型管理程序3228.3.3 ii型管理程序3238.3.4 准虛擬化3248.3.5 內存的虛擬化3258.3.6 i/o設備的虛擬化3268.3.7 虛擬工具3278.3.8 多核處理機上的虛擬機3278.3.9 授權問題3278.4 分布式系統3278.4.1 網路硬體3298.4.2 網路服務和協議3318.4.3 基於文檔的中間件3338.4.4 基於文件系統的中間件3348.4.5 基於對象的中間件3378.4.6 基於協作的中間件3388.4.7 網格3418.5 有關多處理機系統的研究3418.6 小結342習題343第9章 安全3469.1 環境安全3479.1.1 威脅3479.1.2 入侵者3479.1.3 數據意外遺失3489.2 密碼學原理3489.2.1 私鑰加密技術3499.2.2 公鑰加密技術3499.2.3 單向函數3509.2.4 數字簽名3509.2.5 可信平台模塊3519.3 保護機制3529.3.1 保護域3529.3.2 訪問控制列表3539.3.3 權能3549.3.4 可信系統3569.3.5 可信計算基3579.3.6 安全系統的形式化模型3589.3.7 多級安全3589.3.8 隱蔽信道3609.4 認證3629.4.1 使用口令認證3639.4.2 使用實際物體的認證方式3679.4.3 使用生物識別的驗證方式3699.5 內部攻擊3709.5.1 邏輯炸彈3709.5.2 後門陷阱3709.5.3 登錄欺騙3719.6 利用代碼漏洞3719.6.1 緩沖區溢出攻擊3729.6.2 格式化字元串攻擊3739.6.3 返回libc攻擊3749.6.4 整數溢出攻擊3759.6.5 代碼注入攻擊3769.6.6 許可權提升攻擊3769.7 惡意軟體3779.7.1 特洛伊木馬3789.7.2 病毒3799.7.3 蠕蟲3859.7.4 間諜軟體3869.7.5 rootkit 3889.8 防禦3909.8.1 防火牆3919.8.2 反病毒和抑制反病毒技術3929.8.3 代碼簽名3959.8.4 囚禁3969.8.5 基於模型的入侵檢測3979.8.6 封裝移動代碼3989.8.7 java安全性4009.9 有關安全性研究4019.10 小結401習題402第10章 實例研究1：linux 40510.1 unix與linux的歷史40510.1.1 unics 40510.1.2 pdp-11 unix 40610.1.3 可移植的unix 40610.1.4 berkeley unix 40710.1.5 標准unix 40710.1.6 minix 40810.1.7 linux 40910.2 linux概述41010.2.1 linux的設計目標41010.2.2 到linux的介面41110.2.3 shell 41210.2.4 linux應用程序41310.2.5 內核結構41410.3 linux中的進程41610.3.1 基本概念41610.3.2 linux中進程管理相關的系統調用41810.3.3 linux中進程與線程的實現42010.3.4 linux中的調度42410.3.5 啟動linux系統42610.4 linux中的內存管理42710.4.1 基本概念42710.4.2 linux中的內存管理系統調用42910.4.3 linux中內存管理的實現43010.4.4 linux中的分頁43410.5 linux中的i/o系統43510.5.1 基本概念43510.5.2 網路43610.5.3 linux的輸入/輸出系統調用43710.5.4 輸入/輸出在linux中的實現43710.5.5 linux中的模塊43910.6 linux文件系統44010.6.1 基本概念44010.6.2 linux的文件系統調用44210.6.3 linux文件系統的實現44410.6.4 nfs：網路文件系統44910.7 linux的安全性45310.7.1 基本概念45310.7.2 linux中安全相關的系統調用45410.7.3 linux中的安全實現45510.8 小結455習題456第11章 實例研究2：windows vista 45911.1 windows vista的歷史45911.1.1 20世紀80年代：ms-dos 45911.1.2 20世紀90年代：基於ms-dos的windows 46011.1.3 21世紀：基於nt的windows 46011.1.4 windows vista 46211.2 windows vista編程46211.2.1 內部nt應用編程介面46311.2.2 win32應用編程介面46511.2.3 windows注冊表46711.3 系統結構46811.3.1 操作系統結構46911.3.2 啟動windows vista 47611.3.3 對象管理器的實現47711.3.4 子系統、dll和用戶態服務48311.4 windows vista中的進程和線程48411.4.1 基本概念48411.4.2 作業、進程、線程和纖程管理api調用48711.4.3 進程和線程的實現49011.5 內存管理49411.5.1 基本概念49411.5.2 內存管理系統調用49611.5.3 存儲管理的實現49711.6 windows vista的高速緩存50211.7 windows vista的輸入/輸出50411.7.1 基本概念50411.7.2 輸入/輸出api調用50411.7.3 i/o實現50611.8 windows nt文件系統50911.8.1 基本概念51011.8.2 ntfs文件系統的實現51011.9 windows vista中的安全51611.9.1 基本概念51611.9.2 安全相關的api調用51811.9.3 安全性的實現51811.10 小結519習題520第12章 實例研究3：symbian操作系統52212.1 symbian操作系統的歷史52212.1.1 symbian操作系統的起源：psion和epoc 52212.1.2 symbian操作系統版本6 52312.1.3 symbian操作系統版本7 52312.1.4 今天的symbian操作系統52312.2 symbian操作系統概述52312.2.1 面向對象52412.2.2 微內核設計52412.2.3 symbian操作系統納核52512.2.4 客戶機/伺服器資源訪問52512.2.5 較大型操作系統的特點52512.2.6 通信與多媒體2.3 symbian操作系統中的進程和線程2.3.1 線程和納線程2.3.2 進程52712.3.3 活動對象52712.3.4 進程間通信52712.4 內存管理52812.4.1 沒有虛擬內存的系統52812.4.2 symbian操作系統的定址方式52912.5 輸入和輸出53012.5.1 設備驅動53012.5.2 內核擴展53012.5.3 直接存儲器訪問53112.5.4 特殊情況：存儲介質53112.5.5 阻塞i/o 53112.5.6 可移動存儲器53112.6 存儲系統53212.6.1 移動設備文件系統53212.6.2 symbian操作系統文件系統53212.6.3 文件系統安全和保護53212.7 symbian操作系統的安全53312.8 symbian操作系統中的通信53412.8.1 基本基礎結構53412.8.2 更仔細地觀察基礎結構53512.9 小結536習題536第13章 操作系統設計53713.1 設計問題的本質53713.1.1 目標53713.1.2 設計操作系統為什麼困難53813.2 介面設計53913.2.1 指導原則53913.2.2 范型54013.2.3 系統調用介面54213.3 實現54313.3.1 系統結構54313.3.2 機制與策略54513.3.3 正交性54613.3.4 命名54613.3.5 綁定的時機54713.3.6 靜態與動態結構54713.3.7 自頂向下與自底向上的實現54813.3.8 實用技術54913.4 性能55213.4.1 操作系統為什麼運行緩慢55213.4.2 什麼應該優化55213.4.3 空間-時間的權衡55313.4.4 高速緩存55413.4.5 線索55513.4.6 利用局部性55513.4.7 優化常見的情況55513.5 項目管理55613.5.1 人月神話55613.5.2 團隊結構55613.5.3 經驗的作用55813.5.4 沒有銀彈55813.6 操作系統設計的趨勢55813.6.1 虛擬化55913.6.2 多核晶元55913.6.3 大型地址空間操作系統55913.6.4 聯網55913.6.5 並行系統與分布式系統56013.6.6 多媒體56013.6.7 電池供電的計算機56013.6.8 嵌入式系統56013.6.9 感測節點56113.7 小結561習題561第14章 閱讀材料及參考文獻56314.1 進行深入閱讀的建議56314.1.1 簡介及概要56314.1.2 進程和線程56314.1.3 存儲管理56414.1.4 輸入/輸出56414.1.5 文件系統56414.1.6 死鎖56414.1.7 多媒體操作系統56414.1.8 多處理機系統56514.1.9 安全56514.1.10 linux 56614.1.11 windows vista 56714.1.12 symbian操作系統56714.1.13 設計原則56714.2 按字母順序排序的參考文獻...568

㈩ 頁面置換演算法

在瞎啟虛程序的執行過程中，當所訪問的信息不在內存時，會由操作系統負責將所需信息從外存調入內存，然後再繼續執行程序，如果在調入內存時，發現內存空間不夠，會由操作系統負責將內存中暫時用不到的信息換出到外存,由於頻繁的進行IO操作會影響計算機性能，所以我們需要使用合適的演算法來進行頁面的置換。這里介紹幾種常見的頁面置換演算法：

每次選擇淘汰的頁面將是以後永不使用，或者在最長時間不再被訪問的頁面，這樣可以保證最低的缺頁率。但是實際上進程執行的過程才能知道接下來會訪問到的是哪個頁面，操作系統無法預知，因此最佳置換演算法是一種 理想化 演算法，無法實現。

每次旁純選擇淘汰的頁面是最早進入內存的頁面，這種演算法雖然實現簡單，但是該演算法與進程實際運行時的規律不適應，因為先進入的頁面也有可能最經常被訪問，因此該演算法性能磨燃很差。

每次淘汰的頁面是最近最久未被使用的頁面，需要有額外的內存空間來記錄該頁面自上次被訪問以來所經過的時間，但是性能很好。

該演算法是一種性能和開銷較均衡的演算法，又稱最近未使用演算法（NRU）。每個頁面需要額外添加兩個標志位：訪問位（0代表最近沒有被訪問，1代表最近被訪問）、修改位（0代表最近沒有被修改，1代表最近被修改過）。如果淘汰的頁面最近是被修改過，那麼淘汰該頁面前會進行寫入外存的IO操作，使性能變差，所以在其他條件都相同的情況下，應優先淘汰沒有修改過的頁面。

演算法規則：將所有可能被置換的頁面排成一個循環隊列 （訪問位， 修改位）

第一輪：從當前位置開始掃描到第一個（0，0）的頁用於替換。

第二輪：若第一輪掃描失敗，則重新掃描，查找第一個（0，1）的頁面用於替換，同時將掃描過的頁面的訪問位設為0。例如（1，0）變成（0，0）

第三輪：若第二輪掃描失敗，則重新掃描，查找第一個（0，0）的頁面用於替換。

第四輪：若第三輪掃描識別，則重新掃描，查找第一個（0，1）的頁面用於替換。本次掃描必定會有一個頁面被選中。