【正文】 個頁面中，哪一個頁面是未來最長時間內不再被訪問的，因而該算法是無法實現(xiàn)的，便可以利用此算法來評價其它算法。 先進先出(FIFO)頁面置換算法 這是最早出現(xiàn)的置換算法。該算法總是淘汰最先進入內存的頁面，即選擇在內存中駐留時間最久的頁面予以淘汰。該算法實現(xiàn)簡單只需把一個進程已調入內存的頁面，按先后次序鏈接成一個隊列，并設置一個指針，稱為替換指針，使它總是指向最老的頁面。最近最久未使用置換算法 （1）LRU(Least Recently Used)置換算法的描述FIFO置換算法性能之所以較差，是因為它所依據(jù)的條件是各個頁面調入內存的時間，而頁面調入的先后并不能反映頁面的使用情況。最近最久未使用（LRU）置換算法，是根據(jù)頁面調入內存后的使用情況進行決策的。由于無法預測各頁面將來的使用情況，只能利用“最近的過去”作為“最近的將來”的近似，因此，LRU置換算法是選擇最近最久未使用的頁面予以淘汰。該算法賦予每個頁面一個訪問字段，用來記錄一個頁面自上次被訪問以來所經(jīng)歷的時間t,，當須淘汰一個頁面時，選擇現(xiàn)有頁面中其t值最大的，即最近最久未使用的頁面予以淘汰。 （2）LRU置換算法的硬件支持 　 LRU置換算法雖然是一種比較好的算法，但要求系統(tǒng)有較多的支持硬件。為了了解一個進程在內存中的各個頁面各有多少時間未被進程訪問，以及如何快速地知道哪一頁是最近最久未使用的頁面，須有以下兩類硬件之一的支持： a）寄存器 為了記錄某個進程在內存中各頁的使用情況，須為每個在內存中的頁面配置一個移位寄存器，可表示為 R=Rn1Rn2Rn3……R2R1R0 當進程訪問某物理塊時，要將相應寄存器的Rn1位置成1。此時，定時信號將每隔一定時間(例如100ms)將寄存器右移一位。如果我們把n位寄存器的數(shù)看作是一個整數(shù)，那么具有最小數(shù)值的寄存器所對應的頁面，就是最近最久未使用的頁面。如圖1示出了某進程在內存中具有8個頁面，為每個內存頁面配置一個8位寄存器時的LRU訪問情況。這里，把8個內存頁面的序號分別定為1――＝8。由圖可以看出，第7個內存頁面的R值最小，當發(fā)生缺頁時首先將它置換出去。 R7 R6 R5 R4 R3 R2 R1 R0 1 0 1 0 1 0 0 1 0 2 1 0 1 0 1 1 0 0 3 0 0 0 0 0 1 0 0 4 0 1 1 0 1 0 1 1 5 1 1 0 1 0 1 1 0 6 0 0 1 0 1 0 1 1 7 0 0 0 0 0 1 1 1 8 0 1 1 0 1 1 0 1 b)棧 可利用一個特殊的棧來保存當前使用的各個頁面的頁面號。每當進程訪問某頁面時，便將頁面的頁面號從棧中移出，將它壓入棧頂。因此，棧頂始終是最新被訪問頁面的編號民，而棧底則是最近最久未使用的頁面的頁面號。四、程序清單參考實驗步驟如下：// 現(xiàn)定義數(shù)據(jù)結構和全局變量。include include define M 4 define N 17 define Myprintf printf(|++++++++++++++++|\n) /*表格控制*/ typedef struct page { int num。 /*記錄頁面號*/ int time。 /*記錄調入內存時間*/ }Page。 /* 頁面邏輯結構，結構為方便算法實現(xiàn)設計*/ Page b[M]。 /*內存單元數(shù)*/ int c[M][N]。 /*暫保存內存當前的狀態(tài)：緩沖區(qū)*/ int queue[100]。 /*記錄調入隊列*/ int K。 /*調入隊列計數(shù)變量*/ //初始化內存單元、緩沖區(qū) void Init(Page *b,int c[M][N]) { int i,j。 for(i=0。iN。i++) { b[i].num=1。 b[i].time=Ni1。 } for(i=0。iM。i++) for(j=0。jN。j++) c[i][j]=1。 } //取得在內存中停留最久的頁面,默認狀態(tài)下為最早調入的頁面 int GetMax(Page *b) { int i。 int max=1。 int tag=0。 for(i=0。iM。i++) { if(b[i].timemax) { max=b[i].time。 tag=i。 } } return tag。 } //判斷頁面是否已在內存中int Equation(int fold,Page *b) { int i。 for(i=0。iM。i++) if (fold==b[i].num) return i。 return 1。 }//LRU算法void Lru(int fold,Page *b) { int i。 int val。 val=Equation(fold,b)。 if (val=0) { b[val].time=0。 for(i=0。iM。i++) if (i!=val) b[i].time++。 } else { queue[++K]=fold。/*記錄調入頁面*/ val=GetMax(b)。 b[val].num=fold。 b[val].time=0。 for(i=0。iM。i++) if (i!=val) b[i].time++。 } }//FIFO與OPT的算法描述省略。//主程序 void main() { int a[N]={1,0,1,0,2,4,1,0,0,8,7,5,4,3,2,3,4}。 int i,j。 start: K=1。 Init(b, c)。 for(i=0。iN。i++) { Lru(a[i],b)。 c[0][i]=a[i]。 /*記錄當前的內存單元中的頁面*/ for(j=0。jM。j++) c[j][i]=b[j].num。 } /*結果輸出*/ printf(內存狀態(tài)為：\n)。 Myprintf。 for(j=0。jN。j++) printf(|%2d ,a[j])。 printf(|\n)。 Myprintf。 for(i=0。iM。i++) { for(j=0。jN。j++) if(c[i][j]==1) printf(|%2c ,32)。 else printf(|%2d ,c[i][j])。 printf(|\n)。 } Myprintf。 printf(\n調入隊列為:)。 for(i=0。iK+1。i++) printf(%3d,queue[i])。 printf(\n缺頁次數(shù)為：%6d\n缺頁率：%,K+1,(float)(K+1)/N)。 printf(\nAre you continuing!\ty?)。 if(getche()==39。y39。) goto start。 }六、思考題 （1）補充完成FIFO與OPT的算法。（2）為什么在實際的系統(tǒng)中不用LRU置換算法，而用它的近似算法？（3）OPT算法為什么難以實現(xiàn)？實驗八 SCAN 磁盤調度模擬實現(xiàn)實驗學時：2實驗類型：設計實驗要求：（必修、選修）一、實驗目的1) 理解磁盤調度相關理論；2) 掌握多種磁盤調度算法；3) 徹底掌握 SCAN 磁盤調度算法。二、實驗內容本實驗主要針對操作系統(tǒng)中磁盤調度相關理論進行實驗。要求實驗者設計一個程序，該程序模擬操作系統(tǒng)的磁盤調度，調度采用 SCAN 算法。1) 設計磁盤調度請求隊列（請求數(shù)≥10）；2) 設定單位尋道時間；3) 可動態(tài)修改磁盤請求時間和磁道；4) 實現(xiàn) SCAN 磁盤調度算法；5) 實現(xiàn)動態(tài)調度并輸出調度序列。三、實驗原理或算法1) 磁盤調度磁盤可供多個進程共享，當有多個進程要求訪問磁盤時，應采用一種調度算法，以使進程對磁盤的平均訪問時間最小，由于在訪問磁盤的時間中，主要是尋道時間，因此磁盤調度的目標就是使磁盤的平均尋道時間最短。2) SCAN 算法該算法優(yōu)先考慮磁頭當前的移動方向。如果磁頭自里向外運動，則下一個要訪問的磁道為當前磁道之外且距離最近的磁道，直到無更外的磁道時，磁頭又改為從外向里運動。四、實驗要求1） 編寫程序完成實驗內容；2） 在實驗報告中畫出 SCAN 調度函數(shù)流程圖；3） 撰寫實驗報告。五、測試要求1） 進行 3 次以上的調度測試；2） 修改 3 次以上開始磁道數(shù)據(jù)。六、思考題1) SCAN 算法有哪些優(yōu)缺點？2) SCAN 與 CSCAN 有什么異同？實驗九 UNIX基本操作實驗學時：2實驗類型：驗證實驗要求：必修一、實驗目的掌握 UNIX （LINUX）系統(tǒng)的基本使用方法：系統(tǒng)啟動、注銷、關閉和關機；帳號管理；文件系統(tǒng)的日常管理；文件系統(tǒng)的權限控制。 二、實驗內容⑴系統(tǒng)啟動和關閉⑵帳號管理⑶文件系統(tǒng)的日常管理⑷文件系統(tǒng)的權限控制實驗步驟⑴系統(tǒng)啟動和關閉① 使用自己的賬戶登錄UNIX系統(tǒng)，查看系統(tǒng)提示符確定自己使用的shell程序類型別?！蜷_機后，系統(tǒng)自檢啟動后提示login： （輸入：root ↙）password： （輸入：用戶口令 ↙ ，root用戶為redhat ）◎ 查看/etc/passwd文件可以獲得用戶使用的shell grep $LOGNAME /etc/passwd ↙可能的顯示為： user001:*:200:50::/usr/user001:/bin/sh請思考上述命令怎樣得到了當前使用的shell類型的？使用下面的命令也可以查看當前shell： echo $SHELL② 注銷和關機命令?！?用戶注銷使用：$exit ↙或 $ctrl+D ↙或 $logout ↙◎ 超級用戶關機使用：shutdown ↙該命令將結束所有的進程，當執(zhí)行此命令后系統(tǒng)提示“ Safe to Power off or Press Any Key to Reboot ”時可以關閉電源或按任一鍵重啟系統(tǒng)?！騢altsys（halt），reboot只能由超級用戶在單用戶模式下使用。⑵帳號管理① 添加用戶，刪除用戶，修改個人口令后重新進行登錄；◎ 添加用戶的shell命令： useradd user08 ↙（Linux系統(tǒng)中可以為 adduser）上述命令采用默認屬性， UNIX 也可以使用選項來指定創(chuàng)建帳戶的屬性： c ment 用戶說明 d directory 指定用戶主目錄 m 若用戶的起始目錄不存在則創(chuàng)建 g group 指定用戶所屬組 s shell 指定用戶使用的shell u uid 為用戶分配標識◎ 修改口令對linux系統(tǒng)而言，用adduser增加的用戶應該隨即用passwd命令來修改口令。 passwd user08 ↙new password:( 輸入口令，屏幕不回顯) ↙new password （ again ） :( 再次輸入口令) ↙◎ 刪除用戶的shell命令userdel命令用來刪除已經(jīng)存在的用戶及相關的文檔，其命令格式如下： userdel 〔選項〕用戶名userdel命令的常用選項：r將用戶目錄下的文檔一并刪除。在其他位置上的文檔也將一一找出并刪除。Userdel不允許移除正在線上的用戶帳號，因此，如果想刪除這類用戶帳號，必須先殺掉用戶在系統(tǒng)上運行的程序才能進行帳號刪除。② 組的添加、刪除管理；◎ 組信息保存在 /etc/group 文件中，文件記錄格式為：userg1::21:user01,user02,user08其中： userg1 為組名，組ID號為21，組成員有 user01,user02,user08 。◎ 添加用戶組可以直接編輯 /etc/group 文件來創(chuàng)建一個新組。③ 用who命令查看當前登錄在系統(tǒng)中的用戶列表、用戶總數(shù)、系統(tǒng)啟動時間等信息；who H ↙④ 查看當前用戶的標識符及當前進程的狀態(tài)；ps –lf | pg ↙觀察上述命令的輸出。⑤ 用cal命令查看自己的生日是星期幾。如： cal 9 1983 ↙根據(jù)顯示可以得到答案。⑶文件系統(tǒng)的日常管理① 文件的顯示、復制、移動和刪除；◎ cat /etc/passwd ↙◎ catfilea ↙◎ cat filea ↙◎ more /etc/filea ↙◎ pg /etc/filea ↙◎ cp filea fileb ↙◎ mv filea /fileb ↙◎ rm /fileb ↙② 目錄的建立、刪除、顯示