【文章內(nèi)容簡介】 中仍然可能會因為內(nèi)存塊太少而頻繁缺頁，或者因為內(nèi)存塊太多而浪費空間。可變內(nèi)存分配，局部置換策略：采用該策略時，為每個進程分配一定數(shù)目的物理塊后，若某個進程發(fā)生缺頁，則只能將自己的某個內(nèi)存頁換出。如果進程在運行時頻繁發(fā)生缺頁中斷，則系統(tǒng)需為該進程分配若干附加的物理塊，直至其缺頁率減少到適當(dāng)程度為止；反之，若一個進程的缺頁率特別低，則可以適當(dāng)減少分配給它的物理塊，但不應(yīng)引起其缺頁率的明顯增加。因此，可變分配局部置換策略可以獲得較高的內(nèi)存空間利用率，同時又能保證每個進程有較低的缺頁率。、FIFO、LFU、LRU、CLOCK及改進CLOCK等置換算法的基本思想，若假設(shè)系統(tǒng)采用固定分配局部替換的頁面調(diào)入策略，并假設(shè)某進程在創(chuàng)建時，分配到了3個頁面框。試針對如下的該進程相關(guān)頁面引用順序；7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1分別計算采用OPT、FIFO和LRU三種算法時的缺頁率。幾種算法的基本思想：最佳算法(optimal, OPT)n 選擇未來最長時間不使用頁進行置換(最理想算法)；先進先出算法(FIFO)l 選擇最先進入駐留集的頁面進行置換；最不常用算法(Least Frequently Used, LFU)178。 選擇到至今訪問次數(shù)最少的頁進行置換，要設(shè)置一個頁面訪問計數(shù)器。最近最久未使用算法(Least Recently Used, LRU)216。 選擇內(nèi)存中至今最久未使用頁面進行置換；是局部性原理的合理近似，性能接近最佳，但硬件開銷較大。時鐘算法(clock)v 也稱最近未用算法(Not Recently Used,NRU)，是LRU和FIFO的折衷。每頁框有個使用位(use bit,ub)，若該頁被訪問ub=1。所有駐留頁面組織為類似時鐘的環(huán)形緩沖池，置換時采用一個類時鐘指針，從當(dāng)前指針位置開始順時針搜索檢查ub=0的頁框，選擇首個遇到的ub=0的頁框進行置換。改進的時鐘算法（結(jié)合訪問位A和修改位M）252。 第一輪候選對象：A=0∧M=0，失敗進入下一輪252。 第二輪候選對象：A=0∧M≠0， ，失敗進入下一輪252。 第三輪，先將所有目標駐留頁面框的A復(fù)位，再從滿足A=0∧M≠0的候選頁面框中，進行一輪選擇。70120304230321201701FIFO缺頁率15/20777001230422230001270011230423330111270122304230001222701LRU缺頁率12/20777012230422033120170012030423032120170120304230321201701OPT缺頁率9/20777222222222222227770000004440000000000111333333331111111第4章 進程的同步與通信（共享變量是否一定互斥使用）1. 了解多進程環(huán)境下資源的概念、分類和特性。概念：Any entity or any abstract machine ponent ,if it satisfies following charactics:(滿足以下三個特征的任何實體或抽象的計算機元件：)(1) a process must request it from OS （進程需要從操作系統(tǒng)申請它）(2)the process must block its exeution until the entity is allocated to it （資源未分配給進程時，進程處于阻塞狀態(tài)）(3)the coexisting process will pete for resources if they need resources （當(dāng)互斥的進程需要資源時，進程之間處于競爭關(guān)系）分類：分類一：（1）可分配，用完要歸還（可歸還）（2）無需分配的抽象資源分類二：（1）可同時共享資源 （2）臨界資源特性：有限性：2. 什么是臨界區(qū)？請說明臨界區(qū)的代碼模式、同步原則。若不同進程訪問相同臨界資源R1，它們訪問臨界資源R1的代碼一定相同嗎？它們控制進入訪問臨界資源R1代碼區(qū)的同步代碼一定相同嗎？臨界區(qū)定義：每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section）（臨界資源是一次僅允許一個進程使用的共享資源）或定義為： a segment of code ,that write a shard device（write a shared device，是寫入操作，非讀寫操作）, which cannot be wxcuted while the other process are in the respond segment of code that acess to the same resources 代碼模式: // 進入臨界區(qū) 　　EnterCriticalSection(amp。g_cs)。 　　// 對共享資源進行寫入(不是讀寫，)操作 // 離開臨界區(qū)2. 什么是臨界區(qū)？每個進程中訪問臨界資源的那段代碼稱為臨界區(qū)（Critical Section）（臨界資源是一次僅允許一個進程使用的共享資源）請說明臨界區(qū)的代碼模式、同步原則。 // 臨界區(qū)結(jié)構(gòu)對象 　　 CRITICAL_SECTION g_cs。 　 // 共享資源 　　 char g_cArray[10]。 　 　UINT ThreadProc10(LPVOID pParam) 　　 { // 進入臨界區(qū) 　　 EnterCriticalSection(amp。g_cs)。 // 對共享資源進行寫入操作 　 　for (int i = 0。 i 10。 i++) 　　 { 　　 g_cArray[i] = a。 　　 Sleep(1)。 　　 } 　　// 離開臨界區(qū) 　 　LeaveCriticalSection(amp。g_cs)。 　 　return 0。 　　 } 　 　UINT ThreadProc11(LPVOID pParam) 　　 { 　　// 進入臨界區(qū) 　　 EnterCriticalSection(amp。g_cs)。 　　// 對共享資源進行寫入操作 　 　 for (int i = 0。 i 10。 i++) 　　 { 　 　g_cArray[10 i 1] = b。 　 　Sleep(1)。 　 　} // 離開臨界區(qū) 　 　LeaveCriticalSection(amp。g_cs)。 　　 return 0。 　　 } 　 　…… 　 　void CSample08View::OnCriticalSection() 　 　{ 　　// 初始化臨界區(qū) 　　 InitializeCriticalSection(amp。g_cs)。 　　// 啟動線程 　　 AfxBeginThread(ThreadProc10, NULL)。 　　 AfxBeginThread(ThreadProc11, NULL)。 　　// 等待計算完畢 　　 Sleep(300)。 　　// 報告計算結(jié)果 　　 CString sResult = CString(g_cArray)。 　 　AfxMessageBox(sResult)。 　 　}進程進入臨界區(qū)的調(diào)度原則是： 　　如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入。 　　任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其它所有試圖進入臨界區(qū)的進程必須等待。 　　進入臨界區(qū)的進程要在有限時間內(nèi)退出，以便其它進程能及時進入自己的臨界區(qū)。 　　如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進程出現(xiàn)“忙等”現(xiàn)象若不同進程訪問相同臨界資源R1，它們訪問臨界資源R1的代碼一定相同嗎？不一定，例如相同的循環(huán)，可以采用i++或者使用i它們控制進入訪問臨界資源R1代碼區(qū)的同步代碼一定相同嗎？一定相同同步原則：忙碌等待（必須）：對已有進程進入臨界區(qū)時，其他試圖進入臨界區(qū)的進程立即進入臨界區(qū)?？臻e則入（必須）：當(dāng)沒有進程處于臨界區(qū)時，可以允許一個請求進入臨界區(qū)的進程立即進入臨界區(qū)。有限等待（錦上添花）：對要求訪問臨界資源的進程，應(yīng)保證能在有限時間內(nèi)進入臨界區(qū)。讓權(quán)等待（錦上添花）：當(dāng)進程不能進入臨界區(qū)時，應(yīng)釋放處理機。3. 請寫出利用1）禁止中斷結(jié)合共享標志變量；2）多個共享標志變量；3）硬件指令TS；4）硬件指令SWAP 等四種技術(shù)方案，實現(xiàn)臨界區(qū)同步的算法，并分別舉一例說明它們的應(yīng)用方法。這些算法都是基于平等競爭的同步實現(xiàn)算法，它們能實現(xiàn)“有限等待”和“讓權(quán)等待”這兩條原則嗎？1）禁止中斷結(jié)合共享標志變量：Enter(lock){Disable interrupt()。While(lock ){Enable interrupt()Disable interrupt ()}Lock=true。Enable interrupt()}Exit (lock){Disable interrupt()。Lock=false。Enable interrupt()。}}2）多個共享標志變量：Boolean flag[N]While(1){Flag[i]=true。Turn=j。While(flag[j]==trueamp。amp。 turn==j){null。}CRFlag{i}=false。……………}3）硬件指令TS:TS 功能描述：Boolean TS（boolean *lock）{Boolean old。old=*lock。*lock=true。Return old。}應(yīng)用（算法描述）：Lock=false。While (TS(amp。lock))。CRLock=false。進程的其他代碼；4）硬件指令SWAP功能描述：Swap(Boolean *a, boolean *b){Boolean temp。Temp=*a。*a=*b。*b=temp。}應(yīng)用（算法描述）Pi/Pj(線程)：有全局變量lock Pi : 有局部變量key例子：P1：While(1){key=true。While(key==true)Swap(amp。lock,amp。key)CRLock=false。}用上面所列出的算法語句，沒有辦法實現(xiàn)【有限等待】和【讓權(quán)等待】，但通過改進的方式和引入新的算法或許可以利用這四種方法實現(xiàn)【有限等待】和【讓權(quán)等待】4. 理解信號量的概念、定義和分類；理解具有睡眠等待機制的信號量實現(xiàn)算法。信號量定義：*是一種最最經(jīng)典，能有效解決進程同步的軟件方法，也是現(xiàn)代OS中最具基本的同步機制。*是一種抽象的OS內(nèi)核數(shù)據(jù)類型（見作業(yè)本）分類：（1）二元信號量：value 0,1 （互斥）（2）一般信號量：value 非負具有睡眠等待機制的信號量實現(xiàn)算法：typedef struct { //信號量定義 int value。 LIST_ENTRY queue。} semaphore。void P (semaphore s) //wait (semaphore s) // P操作定義{ 。 if ( 0) { 構(gòu)造一個包含