實驗一  進程同步和互斥

實驗一

進程同步和互斥（建議4學時）一、實驗目的1．掌握臨界資源、臨界區(qū)概念及并發(fā)進程互斥、同步訪問原理。2．學會使用高級語言進行多線程編程的方法。3．掌握利用VC或Java語言線程庫實現(xiàn)線程的互斥、條件競爭，并編碼實現(xiàn)P、V操作，利用P、V操作實現(xiàn)兩個并發(fā)線程對有界臨界區(qū)的同步訪問。4．通過該實驗，學生可在源代碼級完成進程同步互斥方案的分析、功能設計、編程實現(xiàn)，控制進程間的同步、互斥關系。二、實驗要求1．知識基礎：學生應在完成進程和線程及調度等章節(jié)的學習后進行。2．開發(fā)環(huán)境與工具：硬件平臺——個人計算機。軟件平臺-Windows操作系統(tǒng)，vc語言或Java語言開發(fā)環(huán)境。3．運用高級語言VC或Java語言線程庫及多線程編程技術進行設計實現(xiàn)。三、實驗內容1．實現(xiàn)臨界資源、臨界區(qū)、進程或線程的定義與創(chuàng)建。2．利用兩個并發(fā)運行的進程，實現(xiàn)互斥算法和有界緩沖區(qū)同步算法。四、實驗方案指導該實驗方案由以下幾個關鍵設計項目組成：1．并發(fā)訪問出錯。即設計一個共享資源，創(chuàng)建兩個并發(fā)線程，二者并發(fā)訪問該共享資

源。當沒有采用同步算法設計時，線程所要完成的某些操作會丟失。2．互斥鎖。并發(fā)線程使用線程庫提供的互斥鎖，對共享資源進行訪問。3．軟件方法。設計并編程實現(xiàn)計數(shù)信號量、P操作函數(shù)、V操作函數(shù)，并發(fā)線程通過調用P，V操作函數(shù)實現(xiàn)線程的互斥。4．同步訪問多緩沖區(qū)。利用上面的軟件方法完成P，V操作，可實現(xiàn)兩個線程對多緩沖區(qū)的同步訪問。五、實驗方案實現(xiàn)范例以下是對該項目中包含的部分設計功能的實現(xiàn)方法、實現(xiàn)過程、技術手段的描述，供師生參考。1．模擬線程并發(fā)運行。假設我們使用POSIX線程庫，而POSIX并沒有真正提供線程間的并發(fā)運行需求。我們設計的系統(tǒng)應支持符合RR調度策略的并發(fā)線程，每個線程運行一段時間后自動掛起，另一

個線程開始運行。這樣一個進程內所有線程以不確定的速度并發(fā)執(zhí)行。2．模擬一個競爭條件——全局變量。創(chuàng)建兩個線程tl和t2，父線程主函數(shù)main()定義兩個全局變量accntl和accnt2，每個變

量表示一個銀行賬戶，初始化為0。每個線程模擬一個銀行事務：將一定數(shù)額的資金從一個

賬戶轉到另一個賬戶。每個線程讀入一個隨機值，代表資金數(shù)額，在一個賬戶上做減法，在

另一個賬戶上做加法，用兩個變量記錄兩個賬戶的收支情況。良性情況下收支應平衡，即兩

個全局變量之和應為0。下面是每個線程的代碼：counter=0;do{tmp1=accnt1;tmp2=accnt2;r=random();accnt1=tmp1r;accnt2=tmp2-r;counter;}while(accnt1accnt2==0);printf(”%d”,counter);=====================================================================兩個線程運行的代碼相同，只要各自代碼不被交叉執(zhí)行，兩個收支余額之和就應一直為

如果線程被交叉執(zhí)行，某個線程可能會讀入一個舊的accntl值和一個新的accnt2值，或

反，這樣會導致某個值的丟失。當這種情況出現(xiàn)時，線程停止運行，并把出現(xiàn)情況的位置

Counter的值）打印出來。3．模擬一個競爭條件——共享文件。主線程創(chuàng)建兩個共享文件fl和f2，每個文件包含一個當前銀行賬戶。線程使用隨機數(shù)對文件進行讀／寫，方式同上。注意：文件在讀／寫過程中不要加互斥訪問鎖，以免不會出現(xiàn)交叉訪問的情況。4．測試出現(xiàn)一個競爭條件的時間。我們的編程環(huán)境中，一般無法支持線程的RR調度，必須編程實現(xiàn)兩個線程間在兩個賦值語句之間插入以下代碼：在指定區(qū)間（比如0到1）生成一個隨機數(shù)，小于一個極限值（如0.1），調用線程自動掛起函數(shù)jield()，自動放棄CPU，另一運行，于是導致一個數(shù)據更新的丟失。5．互斥鎖。POSIX線程庫提供一個二值信號量，稱為MUTEX，它可以加鎖或解鎖。如果已被另一個線程加上鎖的MUTEX加鎖，就會引發(fā)該線程被阻塞，MUTEX解鎖時喚醒它。使用這些原語，很容易實現(xiàn)互斥進入CS（臨界區(qū)）。進入CS區(qū)時加鎖，離開CS區(qū)時解鎖。系統(tǒng)負責阻塞或喚醒線程。6．用軟件方法實現(xiàn)互斥訪問臨界區(qū)。用標準編程語言設置變量的值，用線程“忙等待”實現(xiàn)互斥訪問CS。設計兩線分代碼如下：=====================================================================intcl=0,c2=0,will_wait;p1:

while(l){cl=l;will_wait=l;while(c2&&(will_wait==1));

/*忙等待*/csl;cl=0;programl;}p2:

while(l){c2=1;will_wait=2;while(cl&&(will_wait==2);

/*忙等待*/cs2;c2=0;program2;}=====================================================================該軟件方法使用三個變量cl，c2，will_wait，解決兩個線程的同步問題。兩個線程分別將c1和c2設置為1，表示自己試圖進入臨界區(qū)，并將will_wait分別設置為1和2，以消除任何競爭條件。通過“忙等待”循環(huán)實現(xiàn)線程的阻塞。當線程退出CS區(qū)時，分別將變量c1和c2設置為0。我們可以比較互斥鎖和軟件方法這兩種解決方法的效率?？梢酝ㄟ^重復相同的循環(huán)次數(shù)，測量各自的執(zhí)行時間，盡量減少可能的外部干擾，重復測試幾次，并計算平均值。#include"iostream"usingnamespacestd;#include"windows.h"DWORDWINAPIThreadProc1(LPVOIDlpParameter);DWORDWINAPIThreadProc2(LPVOIDlpParameter);HANDLEhMutex;intcounter=0,accnt1=0,accnt2=0,tmp1,tmp2,r;voidmain(){printf("開始服務:\n");HANDLEhandle1=CreateThread(NULL,0,ThreadProc1,NULL,0,NULL);HANDLEhandle2=CreateThread(NULL,0,ThreadProc2,NULL,0,NULL);CloseHandle(handle1);CloseHandle(handle2);hMutex=CreateMutex(NULL,FALSE,NULL);/*控制主進程運行時間*/Sleep(5000);printf("服務結束\n");//getchar();//VS2008}DWORDWINAPIThreadProc1(LPVOIDlpParameter){

while(accnt1accnt2==0){WaitForSingleObject(hMutex,INFINITE);tmp1=accnt1;tmp2=accnt2;r=rand();accnt1=tmp1r;accnt2=tmp2-r;counter;printf("賬戶A完成轉賬--%d\n",counter);Sleep(100);ReleaseMutex(hMutex);}

//printf("第%d次轉賬發(fā)生錯誤",counter);return0;}DWORDWINAPIThreadProc2(LPVOIDlpParameter){

while(accnt1accnt2==0){WaitForSingleObject(hMutex,INFINITE);tmp1=accnt1;tmp2=accnt2;r=rand();accnt1=tmp1r;accnt2=tmp2-r;counter;printf("賬戶B完成轉賬--%d\n",counter);Sleep(100);ReleaseMutex(hMutex);}//printf("第%d次轉賬發(fā)生錯誤",counter);return0;}實驗二

進程及其資源管理（建議4學時）一、實驗目的1．理解資源共享與互斥特性，以及操作系統(tǒng)管理資源的基本方法。2．學會使用高級語言進行多線程編程的方法。3．掌握利用VC或Java線程庫實現(xiàn)一個管理器，用來實現(xiàn)操作系統(tǒng)對進程及其資源的管理功能。4．通過該實驗，學生可在源代碼級完成進程及其資源管理方案的分析、功能設計、編程實現(xiàn)，控制進程間的同步、互斥關系。二、實驗要求1．知識基礎：學生應在完成對進程和線程、調度、死鎖等章節(jié)的學習后進行。2．開發(fā)環(huán)境與工具：硬件平臺——個人計算機。軟件平臺——Windows操作系統(tǒng)，根據需要，任選安裝VC語言、java語言或C語言開發(fā)環(huán)境。三、實驗內容1．開發(fā)一個函數(shù)，建立進程控制塊和資源控制塊結構，并實現(xiàn)相關數(shù)據結構的初始化。2．開發(fā)一系列操作，由進程調用這些操作，達到控制進程申請或釋放各種資源的目的。四、實驗方案指導

該實驗方案由以下幾個關鍵設計項目組成：1．進程數(shù)據結構表示。2．資源數(shù)據結構表示。3．進程對資源的操作。4．調度程序。5．用戶功能shell界面。五、實驗方案實現(xiàn)范例以下是對該項目中包含的設計功能的實現(xiàn)方法、實現(xiàn)過程、技術手段的描述，供師生參考。

1．進程數(shù)據結構表示。使用結構類型設計實現(xiàn)進程PCB表，它包含以下成員：①進程ID——進程的唯一標識，

供其他進程引用該進程；②內存——是一個指針鏈表，它在創(chuàng)建進程時已申請完畢，可用鏈表實現(xiàn)；③其他資源——表示除去內存之外的所有資源；④進程狀態(tài)——包括兩個數(shù)據類型，一個是狀態(tài)碼，另一個是狀態(tài)隊列鏈表指針；⑤生成樹——包括兩個數(shù)據類型，本進程的父進程和本進程的子進程；⑥優(yōu)先級——供進程調度程序使用，用來確定下一個運行進程，可以設定為靜態(tài)整數(shù)。2．資源數(shù)據結構。每個資源都用一個稱為資源控制塊的數(shù)據結構表示。使用結構類型設計實現(xiàn)資源控制塊RCB。資源控制塊包括以下字段成員：①RID-資源的唯一標識，由進程引用；②資源狀態(tài)——空閑／已分配；③等待隊列——是被本資源阻塞的進程鏈表，本資源正被其他所有資源都設定為靜態(tài)數(shù)據，系統(tǒng)啟動時初始化。3．進程管理及進程對資源的操作。進程操作及進程狀態(tài)轉換歸納如下：①進程創(chuàng)建——（無）→就緒；②申請行→阻塞；③資源釋放——阻塞→就緒；④刪除進程——（任何狀態(tài)）→（無）；——就緒→運行或運行→就緒。具體實現(xiàn)步驟如下：(1)根據上述數(shù)據結構，用高級語言設計相應函數(shù)，分別實現(xiàn)創(chuàng)建進程、刪除進程、掛起進程、喚醒進程等功能。(2)設計一個函數(shù)，實現(xiàn)調度程序，在每個進程操作執(zhí)行完畢后，自動調用執(zhí)行。(3）實現(xiàn)兩個資源操作：申請資源和釋放資源。相關參考算法如下：=====================================================================request(RID)

/*申請資源算法*/{

r=get_RCB(RID);

/*獲取資源控制塊首地址*/if(r->status==’free’){

/*資源可用*/r->status=’allocated’;

/*分配給調用進程，*/insert(self->other_resources,r);}

/*插入一個RCB指針指向進程資源鏈表；*/else{

/*資源不可用*/self->status.type=’blocked’;

/*記錄阻塞*/self->status.list=r;

/*指向所請求資源的RCB*/.

remove(RL,self);

/*將進程從就緒隊列中刪除*/insert(r->waiting_list,self);}

/*插入資源等待隊列*/scheduler();

/*調度程序運行選擇下一個運行進程*/release(RID)

/*釋放資源算法*/{

r=get_RCB(RID);

/*獲取資源控制塊首地址*/remove(self->other_resource,r);

/*從進程資源鏈表中刪除該資源*/if(waiting_list==NULL)

r->status=’free’;

/*等待隊列為空，置資源狀態(tài)為空閑*/else{

/*等待隊列不為空*/remove(r->waiting_list,q);

/*從等待隊列中移出一個進程q*/q->status.type=’ready’;

/*將進程q的狀態(tài)設為就緒*/q->status.list=RL;

/*進程q的狀態(tài)指針指向就緒隊列*/insert(RL,q);}

/*進程q插入就緒隊列*/scheduler();

/*調度程序運行選擇下一個運行進程*/=====================================================================4．調度程序。調度策略采用固定優(yōu)先級和可剝奪優(yōu)先級調度算法。即調度程序必須維護n個不同優(yōu)先

級的就緒隊列，各就緒隊列可為空，也可包含多個進程。0級進程優(yōu)先級最低，n-l級進程優(yōu)先級最高。創(chuàng)建進程時就賦予了固定的優(yōu)先級，并在進程的生存期內保持不變。當新進程創(chuàng)建或阻塞進程被喚醒時，它就被插入同級的就緒隊列中。調度程序按“先來先服務”和優(yōu)先級“從高到低”的方式處理就緒隊列。即從最高優(yōu)先

級的非空就緒隊列的隊首選擇一個進程進入運行態(tài)。這樣的調度策略很容易導致"饑餓"，進

程出現(xiàn)。因為對進程q來說，只有當優(yōu)先級高于自己的所有進程都運行完畢，或都進入阻塞

狀態(tài)時，它才能得到運行權。為了簡化調度程序，我們假定系統(tǒng)中至少有一個進程處于就緒態(tài)。為確保這一點，設計

一個特殊進程init，該進程在系統(tǒng)初始化時自動創(chuàng)建，并賦予最低優(yōu)先級0級。init進程有兩個作用：充當閑逛進程，該進程運行時不申請任何資源，以免被阻塞；作為第一個被創(chuàng)建的進程，它沒有父進程，可創(chuàng)建比自己優(yōu)先級高的其他進程。所以init進程是進程生成樹的根進程。采用優(yōu)先級策略的調度程序的常見結構知下所示：=====================================================================scheduler(){

找出最高優(yōu)先級進程p；If(self->priority<p->priority)||self->status.type!=’running’||self=nil)preempt(p,self);

/*調度進程p，替換當前進程self*/}=====================================================================每當任一進程的操作執(zhí)行完畢，必須執(zhí)行進程調度程序，它是當前運行進程的一部分。

進程調用該函數(shù)，后者決定該進程是繼續(xù)執(zhí)行還是被其他進程剝奪運行權。作出判斷的依據

是：是否存在高優(yōu)先級進程p，如果存在，p將剝奪self的運行權。當前進程的運行權被剝奪的情況有以下兩種：①當前進程剛剛完成release(操作，由此被喚醒進程的優(yōu)先級可能高于當前進程。②當前進程剛剛完成create()操作，新創(chuàng)建進程的優(yōu)先級可能高于當前進程。在以下兩種情況下，新挑選的進程必須剝奪當前進程的運行權：①當前進程剛剛完成reques()操作，并且申請的資源timeout則當前進程的狀態(tài)就改為“阻塞”；或者由于分時運行進程的需要，調度程序被一個timeout操作調用運行。在timeout操作中當前進程的狀態(tài)改為“就緒”。在上述情況中，當前進程的狀態(tài)都不是“運行”。所以當前進程必須停止運行，此時就緒隊列中最高優(yōu)先級的進程p得到執(zhí)行。②當進程剛剛完成destroy操作，進程自己刪除自身，它的PCB表不再存在。此時調度程序被執(zhí)行，從就緒隊列中選出最高優(yōu)先級的進程p，并令其執(zhí)行。剝奪操作包括以下工作：將選中的最高優(yōu)先級進程p的狀態(tài)改為“運行"。如果當前進

程依然存在且沒CPU，則將其狀態(tài)改為“就緒”，以便隨后能得到執(zhí)行。最后，進行上下文

切換，保留當前CPU的各個寄存器值，放入PCB表。裝入中選進程p的寄存器值。本實現(xiàn)方案沒有對實際的CPU進行訪問來保存或恢復寄存器的值，因此上下文切換的任務只是將正在運行進程的名字顯示在終端屏幕上。從這一點可以認為，用戶終端屏幕開始扮演當前運行進程功能的角色。5．用戶shell界面。為RCB試和演示管理器的CPU能，本方案設計開發(fā)一個shell界面，它可以重復接受終端輸入的命令，喚醒管理器執(zhí)行相應的功能，并在屏幕上顯示結果。使用上述系統(tǒng)，終端就能展示當前進程。只要輸入一個命令，就中斷當前進程序的執(zhí)行，shell界面調用進程資源管理器中的函數(shù)F，并傳遞終端輸入的參數(shù)。該函數(shù)執(zhí)行后將改變PCB、RCB及其他數(shù)據結構中的信息。當調度程序執(zhí)行時，決定下一個要運行的進程，并改變其狀態(tài)值。保存當前進程的CPU各寄存器值（虛擬CPU），然后恢復中選進程的值。調度程序將系統(tǒng)狀態(tài)信息顯示在屏幕上，提示下一步操作。特別地，它始終提示正在運行的進程是什么，即終端和鍵盤正在為哪個進程服務。另外，函數(shù)F也可能返回一個錯誤碼，shell也將它顯示在屏幕上。shell命令的語法格式規(guī)定如下：命令名

參數(shù)例如，執(zhí)行命令行“crA1”時將調用對應的管理器函數(shù)create(A，1)，即創(chuàng)建一個名為A、優(yōu)先級為1的進程。同理，命令“rqR”將調用函數(shù)request(R)執(zhí)行。以下顯示說明shell界面的交互內容（假定進程A的優(yōu)先級為1，并且正在運行）。由“*”開始的行視為shell的輸崮結果。提示符“>”后面是提示用戶輸入的命令?！?processAisrunning>crB2*processBisrunning>crC1*processBisrunning>reqR1*processBisblocked;processAisrunning……6．進程及資源管理器的升級版?？蓪ι鲜龌拘瓦M程功能資源管理器進行功能擴展，使管理器能夠處理時鐘到時中斷和I/O處理完成中斷。(1)相對時鐘到時中斷。假設系統(tǒng)提供一個硬件時鐘。周期性產生一個時鐘到時中斷。引發(fā)調用函數(shù)timeout()的執(zhí)行。(2)110處理完成中斷。使用名為IO的資源表示所有的I/O設備。該資源的RCB由以下兩部分組成：IOWaiting_list(3)擴展shell。顯示當前運行進程，并添加一個系統(tǒng)調用request_100。終端也能表示硬件，用戶能夠模擬兩種類型的中斷：時鐘到時、I/O完成處理。為了實現(xiàn)以上功能，必須添加新的shell命令，調用以下三個系統(tǒng)調用：request_IO()，IO_competion，timeout()。實驗三

存儲管理（建議4學時）一、實驗目的1．掌握內存管理的基本功能和分區(qū)法內存分配的基本原理。2．學會Linux操作系統(tǒng)下使用c語言函數(shù)和系統(tǒng)調用進行編程的方法。3．利用c語言設計實現(xiàn)分區(qū)法內存分配算法。4．驗證無虛存的存儲管理機制。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程、調度、存儲管理。2．安裝Linux操作系統(tǒng)，使用c語言編程，調用相關系統(tǒng)調用進行設計實現(xiàn)。三、實驗內容1．創(chuàng)建空閑存儲管理表和模擬內存。2．設計并實現(xiàn)一個內存分配程序，分配策略可以分別采用最先適應算法、最佳適應算法和最壞適應算法等，并評價不同分配算法的優(yōu)劣。3．提供一個用戶界面，利用它用戶可輸入不同的分配策略。4．進程向內存管理程序發(fā)出申請、釋放指定數(shù)量的內存請求，內存管理程序調用對應函數(shù)，響應請求。四、實驗方案指導該實驗方案由以下幾個關鍵設計項目組成。1．設計實現(xiàn)一個空閑分區(qū)表。2．設計實現(xiàn)模擬內存。

考慮實現(xiàn)的便利，本方案不訪問真正的內存。定義一個字符數(shù)組charmm[mem_size]或使用Linux系統(tǒng)調用mm=malloc(mem_size)，用來模擬內存。利用指針對模擬內存進行訪問。

3．設計一組管理物理內存空間的函數(shù)。用戶接口由以下三個函數(shù)組成：void*mm_request(intn)申請n個字節(jié)的內存空間。如申請成功，則返回所分配空間的首地址；如不能滿足申請，則返回空值。voidmm_release(void*p)釋放先前申請的內存。如果釋放的內存與空閑區(qū)相鄰，則合并為一個大空閑區(qū)；如果與空閑區(qū)不相鄰，則成為一個單獨的空閑區(qū)。void*mm_init(intmem_size)內存初始化。返回mm指針指向的空閑區(qū)。4．設計實現(xiàn)不同策略的內存分配程序。對于采用不同分配策略的內存管理程序，從以下兩個方面進行調度程序性能的比對：內存利用率以及找到一個合適的分配空間所需查找的步驟。設置一個模擬實驗。分別構建一個隨機生成的請求與釋放隊列。釋放隊列中的操作總是得到滿足，隊列總為空；請求隊列的操作能否被滿足，取決于空閑區(qū)能否滿足申請的空間大小。若不能滿足，則該操作在隊列中等待相應釋放操作喚醒。請求隊列采用FIFO管理，以避免饑餓現(xiàn)象的發(fā)生。內存管理程序應對內存初始化，隨機設定內存空間的占有、空閑情況，隨機設定申請和釋放的操作隊列。調用釋放操作開始運行，調用申請操作，如能滿足，則分配空間，否則等待釋放操作喚醒。下面給出一個模擬內存管理的程序框架（偽碼形式）。可對性能數(shù)據指標進行統(tǒng)計。=====================================================================for(i=0;i<sim_step;i){

/*設定模擬程序執(zhí)行次數(shù)*/do{

/*循環(huán)調用請求操作，直到請求不成功*/getsizenofnextrequest;

/*設定請求空間大小*/mm_request(n);

/*調用請求操作*/}while(requestsuccessful);

/*請求成功，循環(huán)繼續(xù)*/recordmemoryutilization;

/*統(tǒng)計內存使用率*/selectblockptoberelease;

/*釋放某空間p*/release(p);

/*調用釋放操作*/｝=====================================================================以上程序由主循環(huán)控制固定次數(shù)的模擬步驟。每次循環(huán)，程序完成如下處理步驟：內循環(huán)盡可能多地滿足內存請求，請求內存大小值隨機生成。一旦請求失敗，掛起內存管理程序，直至釋放操作被執(zhí)行。此時進行系統(tǒng)內存利用率的統(tǒng)計、計算，隨機挑選一個內存分配空間完成釋放操作。本次主循環(huán)執(zhí)行完畢，開始下一次循環(huán)。需要在程序中完成以下設計：確定請求分配空間大小，統(tǒng)計性能數(shù)據，選擇一個內存區(qū)釋放。實驗四

頁面置換算法(建議4學時）一、實驗目的1．掌握內存管理基本功能和請求分頁式管理的基本原理以及頁面置換算法。2．學會在Linux操作系統(tǒng)下使用C函數(shù)和系統(tǒng)調用的編程方法。3．掌握利用C語言設計實現(xiàn)不同置換策略的頁面置換算法。4．驗證虛存存儲管理機制及其性能。對于生成的引用串，計算、比對不同頁面置換算法的缺頁率。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程、調度、存儲管理。2．安裝Linux操作系統(tǒng)，使用C語言編程，利用相關系統(tǒng)調用實現(xiàn)設計。三、實驗內容1．創(chuàng)建空閑存儲管理表、模擬內存、頁表等。2．提供一個用戶界面，用戶利用它可輸入不同的頁面置換策略和其他附加參數(shù)。3．運行置換程序，輸出缺頁率結果。四、實驗方案指導熟悉頁面置換算法及其實現(xiàn)，了解計算機系統(tǒng)性能評價方法，編制頁面置換算法的模擬程序。方案設計重點提示如下。1．假定系統(tǒng)有固定數(shù)目的內存塊F，物理塊號依次為O～F-l。進程的大小為P頁，其邏輯頁號依次為O～P-l。隨機生成一個引用串RS，即從O～P-l組成的整數(shù)序列。定義一個整型數(shù)組intM[F]表示所有物理塊，如果M[i]=n，表示邏輯頁n存放在物理塊i中。2．生成引用串。用隨機數(shù)方法產生頁面走向，頁面走向長度為L。3．根據頁面走向，分別采用FIFO和LRU算法進行頁面置換，設計一個函數(shù)自動統(tǒng)計缺頁率。4．假定可用內存塊和頁表長度（進程的頁面數(shù)）分別為m和k。初始時，進程的頁面都不在內存。5.參考其他設計項目，將不同置換算法設計實現(xiàn)為函數(shù)，能在界面上方便調用執(zhí)行。實驗五進程調度（建議4學時）一、實驗目的1．掌握進程調度程序的功能和調度程序采用的調度算法。2．學會在Linux操作系統(tǒng)下使用C函數(shù)和系統(tǒng)調用的編程方法。3．掌握利用C語言設計實現(xiàn)不同調度策略的進程調度算法。4．驗證不同進程調度算法對性能的影響。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程、調度。2．安裝Linux操作系統(tǒng)，使用C語言編程，利用相關系統(tǒng)調用完成設計實現(xiàn)。三、實驗內容1．定義、初始化進程數(shù)據結構及其就緒隊列。2．提供一個用戶界面，用戶利用它可輸入不同的分配策略及相關參數(shù)。3．設計實現(xiàn)調度程序，調用下面的功能函數(shù)。4．設計函數(shù)，實現(xiàn)計算平均周轉時間，實現(xiàn)不同調度算法。四、實驗方案指導關鍵設計內容如下，供參考。1．用C語言的結構類型及其鏈表，完成PCB表數(shù)據結構設計，并動態(tài)生成一組進程組成的就緒隊列鏈表。每個進程都由PCB記錄運行時間，優(yōu)先級、到達系統(tǒng)時間等數(shù)據。也可根據需要，自行添加不同調度算法需要的數(shù)據。2．設計實現(xiàn)不同調度算法的函數(shù)，如先來先服務法、短作業(yè)優(yōu)先法、優(yōu)先級法等。設計一個函數(shù)，計算出這組進程的平均周轉時間。3.設計總控函數(shù)，實現(xiàn)進程調度程序。根據用戶界面的輸入，調用相應的調度算法，實現(xiàn)進程調度，計算調度性能指標。實驗六銀行家算法（建議4學時）一、實驗目的1．理解死鎖概念、銀行家算法及安全性檢測算法。2．學會在Linux操作系統(tǒng)下‘使用C語言函數(shù)和指針進行編程的方法。3．掌握利用C語言設計實現(xiàn)銀行家算法的基本過程。4.驗證銀行家算法對于避免死鎖的作用。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程的調度。死鎖。2．安裝Linux操作系統(tǒng)，使用C語言編程完成設計實現(xiàn)。三、實驗內容1.定義并初始化進程及其資源數(shù)據結構。2．提供一個用戶界面，用戶利用它可動態(tài)輸入進程和資源種類等相關參數(shù)3．設計實現(xiàn)安全狀態(tài)檢測和銀行家死鎖避免算法的功能函數(shù)。四、實驗方案指導以如下幾組初始數(shù)據為例，設計相應程序，判斷下列狀態(tài)是否安全。1.3個進程共享12個同類資源狀態(tài)a下：allocation=(1,4,5)，max=(4,4,8)。判斷系統(tǒng)是否安全。狀態(tài)b下：allocation=(1,4,6),max=(4,6,8)。判斷系統(tǒng)是否安全。2.

5個進程共享多類資源狀態(tài)c下：判斷系統(tǒng)是否安全？若安全，給出安全序列。若進程2請求（0，4，2，0），可否立即分配？分配矩陣

最大需求矩陣

可用資源矩陣0

0

1

2

0

0

1

2

1

5

2

01

0

0

0

1

7

5

01

3

5

4

2

3

5

60

6

3

2

0

6

5

20

0

1

4

0

6

5

6實現(xiàn)方案的主要作是如何輸入，如何初始數(shù)據，如何調用對應功能函數(shù)，如何輸出結果。下面給出一個實現(xiàn)方案，供參考。1．開發(fā)一個交互程序，首先從文件中讀入系統(tǒng)描述信息，包括進程的數(shù)目、資源的種類和數(shù)量、每個進程的最大資源請求。程序自動根據文件內容創(chuàng)建一個當前系統(tǒng)描述例如，每類資源的數(shù)目用…維數(shù)組R[m]描述，m為資源的種類。每個R[j]記錄資源Rj的數(shù)量。進程的最大需求矩陣用P[n][m]表示，P[il[j]記錄進程Pi對資源Rj的最人需求。分配矩陣和請求矩陣可使用二維數(shù)組表示。2.用戶輸入一個請求，格式類似：resquest(i,j,k),或release(i,j,k),在這里，i表示進程Pi,j表示資源Rj，k是申請/釋放的數(shù)量。對每一個請求，系統(tǒng)回應是滿足要求還是拒絕分配。3.設定一個申請和釋放序列，無任何檢測和避免死鎖的算法，分配會導致死鎖。4.設定一個申請和釋放序列，按照安全性算法進行設計，回應系統(tǒng)是否安全。然后實現(xiàn)銀行家算法，確保沒有死鎖的分配。實驗七

磁盤調度算法（建議4學時）一、實驗目的1．理解文件讀/寫基本原理和磁盤調度算法的作用。2．學會在Linux操作系統(tǒng)下使用C語言函數(shù)和指針進行編程的方法。3．利用C語言設計實現(xiàn)不同磁盤調度算法，如FIFO，SSTF,SCAN等算法。4．驗證不同磁盤調度算法對性能的影響。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程、調度、存儲管理、I/O管理。2．安裝Linux操作系統(tǒng)，使用C語言編程完成設計實現(xiàn)。三、實驗內容1．設計一個函數(shù)，其功能是動態(tài)創(chuàng)建I/O請求隊列及其相關參數(shù)，如磁道號等。2．提供一個用戶界面，用戶可輸入不同的分配策略以相關參數(shù)。3．設計相應程序計算平均移臂距離。四、實驗方案指導實現(xiàn)本實驗的關鍵內容如下，供參考。1．實現(xiàn)電梯算法。2．實現(xiàn)FIFO,SSTF算法。3．寫一個驅動程序，測試不同的算法。設置多次循環(huán)，每次循環(huán)中，驅動程序隨機調用函數(shù)request(n)和release()。如果執(zhí)行request(n),系統(tǒng)會將n轉換成1~T之間的一個隨機值，T是磁盤的磁道數(shù)。對每種算法，計算平均移臂距離。實驗八

設備處理程序設計（建議4學時）一、實驗目的1.理解設備處理程序的一般設計過程，加深對緩沖和中斷概念的理解。2.學會在Linux操作系統(tǒng)下使用C語言編程與有關進程的系統(tǒng)調用方法。3.掌握利用C語言設計實現(xiàn)鍵盤緩沖區(qū)的讀/寫操作的方法。4.驗證鍵盤緩沖區(qū)和中斷處理程序是否同步。二、實驗要求1．學生應完成如下章節(jié)的學習：進程和線程