實(shí)驗(yàn)一  進(jìn)程同步和互斥

實(shí)驗(yàn)一

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

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

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

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

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

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

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

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

反，這樣會(huì)導(dǎo)致某個(gè)值的丟失。當(dāng)這種情況出現(xiàn)時(shí)，線程停止運(yùn)行，并把出現(xiàn)情況的位置

Counter的值）打印出來。3．模擬一個(gè)競(jìng)爭(zhēng)條件——共享文件。主線程創(chuàng)建兩個(gè)共享文件fl和f2，每個(gè)文件包含一個(gè)當(dāng)前銀行賬戶。線程使用隨機(jī)數(shù)對(duì)文件進(jìn)行讀／寫，方式同上。注意：文件在讀／寫過程中不要加互斥訪問鎖，以免不會(huì)出現(xiàn)交叉訪問的情況。4．測(cè)試出現(xiàn)一個(gè)競(jìng)爭(zhēng)條件的時(shí)間。我們的編程環(huán)境中，一般無法支持線程的RR調(diào)度，必須編程實(shí)現(xiàn)兩個(gè)線程間在兩個(gè)賦值語句之間插入以下代碼：在指定區(qū)間（比如0到1）生成一個(gè)隨機(jī)數(shù)，小于一個(gè)極限值（如0.1），調(diào)用線程自動(dòng)掛起函數(shù)jield()，自動(dòng)放棄CPU，另一運(yùn)行，于是導(dǎo)致一個(gè)數(shù)據(jù)更新的丟失。5．互斥鎖。POSIX線程庫(kù)提供一個(gè)二值信號(hào)量，稱為MUTEX，它可以加鎖或解鎖。如果已被另一個(gè)線程加上鎖的MUTEX加鎖，就會(huì)引發(fā)該線程被阻塞，MUTEX解鎖時(shí)喚醒它。使用這些原語，很容易實(shí)現(xiàn)互斥進(jìn)入CS（臨界區(qū)）。進(jìn)入CS區(qū)時(shí)加鎖，離開CS區(qū)時(shí)解鎖。系統(tǒng)負(fù)責(zé)阻塞或喚醒線程。6．用軟件方法實(shí)現(xiàn)互斥訪問臨界區(qū)。用標(biāo)準(zhǔn)編程語言設(shè)置變量的值，用線程“忙等待”實(shí)現(xiàn)互斥訪問CS。設(shè)計(jì)兩線分代碼如下：=====================================================================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;}=====================================================================該軟件方法使用三個(gè)變量cl，c2，will_wait，解決兩個(gè)線程的同步問題。兩個(gè)線程分別將c1和c2設(shè)置為1，表示自己試圖進(jìn)入臨界區(qū)，并將will_wait分別設(shè)置為1和2，以消除任何競(jìng)爭(zhēng)條件。通過“忙等待”循環(huán)實(shí)現(xiàn)線程的阻塞。當(dāng)線程退出CS區(qū)時(shí)，分別將變量c1和c2設(shè)置為0。我們可以比較互斥鎖和軟件方法這兩種解決方法的效率。可以通過重復(fù)相同的循環(huán)次數(shù)，測(cè)量各自的執(zhí)行時(shí)間，盡量減少可能的外部干擾，重復(fù)測(cè)試幾次，并計(jì)算平均值。#include"iostream"usingnamespacestd;#include"windows.h"DWORDWINAPIThreadProc1(LPVOIDlpParameter);DWORDWINAPIThreadProc2(LPVOIDlpParameter);HANDLEhMutex;intcounter=0,accnt1=0,accnt2=0,tmp1,tmp2,r;voidmain(){printf("開始服務(wù):\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);/*控制主進(jìn)程運(yùn)行時(shí)間*/Sleep(5000);printf("服務(wù)結(jié)束\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完成轉(zhuǎn)賬--%d\n",counter);Sleep(100);ReleaseMutex(hMutex);}

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

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

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

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

1．進(jìn)程數(shù)據(jù)結(jié)構(gòu)表示。使用結(jié)構(gòu)類型設(shè)計(jì)實(shí)現(xiàn)進(jìn)程PCB表，它包含以下成員：①進(jìn)程ID——進(jìn)程的唯一標(biāo)識(shí)，

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

/*申請(qǐng)資源算法*/{

r=get_RCB(RID);

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

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

/*分配給調(diào)用進(jìn)程，*/insert(self->other_resources,r);}

/*插入一個(gè)RCB指針指向進(jìn)程資源鏈表；*/else{

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

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

/*指向所請(qǐng)求資源的RCB*/.

remove(RL,self);

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

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

/*調(diào)度程序運(yùn)行選擇下一個(gè)運(yùn)行進(jìn)程*/release(RID)

/*釋放資源算法*/{

r=get_RCB(RID);

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

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

r->status=’free’;

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

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

/*從等待隊(duì)列中移出一個(gè)進(jìn)程q*/q->status.type=’ready’;

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

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

/*進(jìn)程q插入就緒隊(duì)列*/scheduler();

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

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

級(jí)的非空就緒隊(duì)列的隊(duì)首選擇一個(gè)進(jìn)程進(jìn)入運(yùn)行態(tài)。這樣的調(diào)度策略很容易導(dǎo)致"饑餓"，進(jìn)

程出現(xiàn)。因?yàn)閷?duì)進(jìn)程q來說，只有當(dāng)優(yōu)先級(jí)高于自己的所有進(jìn)程都運(yùn)行完畢，或都進(jìn)入阻塞

狀態(tài)時(shí)，它才能得到運(yùn)行權(quán)。為了簡(jiǎn)化調(diào)度程序，我們假定系統(tǒng)中至少有一個(gè)進(jìn)程處于就緒態(tài)。為確保這一點(diǎn)，設(shè)計(jì)

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

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

/*調(diào)度進(jìn)程p，替換當(dāng)前進(jìn)程self*/}=====================================================================每當(dāng)任一進(jìn)程的操作執(zhí)行完畢，必須執(zhí)行進(jìn)程調(diào)度程序，它是當(dāng)前運(yùn)行進(jìn)程的一部分。

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

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

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

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

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

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

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

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

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

/*循環(huán)調(diào)用請(qǐng)求操作，直到請(qǐng)求不成功*/getsizenofnextrequest;

/*設(shè)定請(qǐng)求空間大小*/mm_request(n);

/*調(diào)用請(qǐng)求操作*/}while(requestsuccessful);

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

/*統(tǒng)計(jì)內(nèi)存使用率*/selectblockptoberelease;

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

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

頁(yè)面置換算法(建議4學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?．掌握內(nèi)存管理基本功能和請(qǐng)求分頁(yè)式管理的基本原理以及頁(yè)面置換算法。2．學(xué)會(huì)在Linux操作系統(tǒng)下使用C函數(shù)和系統(tǒng)調(diào)用的編程方法。3．掌握利用C語言設(shè)計(jì)實(shí)現(xiàn)不同置換策略的頁(yè)面置換算法。4．驗(yàn)證虛存存儲(chǔ)管理機(jī)制及其性能。對(duì)于生成的引用串，計(jì)算、比對(duì)不同頁(yè)面置換算法的缺頁(yè)率。二、實(shí)驗(yàn)要求1．學(xué)生應(yīng)完成如下章節(jié)的學(xué)習(xí)：進(jìn)程和線程、調(diào)度、存儲(chǔ)管理。2．安裝Linux操作系統(tǒng)，使用C語言編程，利用相關(guān)系統(tǒng)調(diào)用實(shí)現(xiàn)設(shè)計(jì)。三、實(shí)驗(yàn)內(nèi)容1．創(chuàng)建空閑存儲(chǔ)管理表、模擬內(nèi)存、頁(yè)表等。2．提供一個(gè)用戶界面，用戶利用它可輸入不同的頁(yè)面置換策略和其他附加參數(shù)。3．運(yùn)行置換程序，輸出缺頁(yè)率結(jié)果。四、實(shí)驗(yàn)方案指導(dǎo)熟悉頁(yè)面置換算法及其實(shí)現(xiàn)，了解計(jì)算機(jī)系統(tǒng)性能評(píng)價(jià)方法，編制頁(yè)面置換算法的模擬程序。方案設(shè)計(jì)重點(diǎn)提示如下。1．假定系統(tǒng)有固定數(shù)目的內(nèi)存塊F，物理塊號(hào)依次為O～F-l。進(jìn)程的大小為P頁(yè)，其邏輯頁(yè)號(hào)依次為O～P-l。隨機(jī)生成一個(gè)引用串RS，即從O～P-l組成的整數(shù)序列。定義一個(gè)整型數(shù)組intM[F]表示所有物理塊，如果M[i]=n，表示邏輯頁(yè)n存放在物理塊i中。2．生成引用串。用隨機(jī)數(shù)方法產(chǎn)生頁(yè)面走向，頁(yè)面走向長(zhǎng)度為L(zhǎng)。3．根據(jù)頁(yè)面走向，分別采用FIFO和LRU算法進(jìn)行頁(yè)面置換，設(shè)計(jì)一個(gè)函數(shù)自動(dòng)統(tǒng)計(jì)缺頁(yè)率。4．假定可用內(nèi)存塊和頁(yè)表長(zhǎng)度（進(jìn)程的頁(yè)面數(shù)）分別為m和k。初始時(shí)，進(jìn)程的頁(yè)面都不在內(nèi)存。5.參考其他設(shè)計(jì)項(xiàng)目，將不同置換算法設(shè)計(jì)實(shí)現(xiàn)為函數(shù)，能在界面上方便調(diào)用執(zhí)行。實(shí)驗(yàn)五進(jìn)程調(diào)度（建議4學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?．掌握進(jìn)程調(diào)度程序的功能和調(diào)度程序采用的調(diào)度算法。2．學(xué)會(huì)在Linux操作系統(tǒng)下使用C函數(shù)和系統(tǒng)調(diào)用的編程方法。3．掌握利用C語言設(shè)計(jì)實(shí)現(xiàn)不同調(diào)度策略的進(jìn)程調(diào)度算法。4．驗(yàn)證不同進(jìn)程調(diào)度算法對(duì)性能的影響。二、實(shí)驗(yàn)要求1．學(xué)生應(yīng)完成如下章節(jié)的學(xué)習(xí)：進(jìn)程和線程、調(diào)度。2．安裝Linux操作系統(tǒng)，使用C語言編程，利用相關(guān)系統(tǒng)調(diào)用完成設(shè)計(jì)實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1．定義、初始化進(jìn)程數(shù)據(jù)結(jié)構(gòu)及其就緒隊(duì)列。2．提供一個(gè)用戶界面，用戶利用它可輸入不同的分配策略及相關(guān)參數(shù)。3．設(shè)計(jì)實(shí)現(xiàn)調(diào)度程序，調(diào)用下面的功能函數(shù)。4．設(shè)計(jì)函數(shù)，實(shí)現(xiàn)計(jì)算平均周轉(zhuǎn)時(shí)間，實(shí)現(xiàn)不同調(diào)度算法。四、實(shí)驗(yàn)方案指導(dǎo)關(guān)鍵設(shè)計(jì)內(nèi)容如下，供參考。1．用C語言的結(jié)構(gòu)類型及其鏈表，完成PCB表數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)，并動(dòng)態(tài)生成一組進(jìn)程組成的就緒隊(duì)列鏈表。每個(gè)進(jìn)程都由PCB記錄運(yùn)行時(shí)間，優(yōu)先級(jí)、到達(dá)系統(tǒng)時(shí)間等數(shù)據(jù)。也可根據(jù)需要，自行添加不同調(diào)度算法需要的數(shù)據(jù)。2．設(shè)計(jì)實(shí)現(xiàn)不同調(diào)度算法的函數(shù)，如先來先服務(wù)法、短作業(yè)優(yōu)先法、優(yōu)先級(jí)法等。設(shè)計(jì)一個(gè)函數(shù)，計(jì)算出這組進(jìn)程的平均周轉(zhuǎn)時(shí)間。3.設(shè)計(jì)總控函數(shù)，實(shí)現(xiàn)進(jìn)程調(diào)度程序。根據(jù)用戶界面的輸入，調(diào)用相應(yīng)的調(diào)度算法，實(shí)現(xiàn)進(jìn)程調(diào)度，計(jì)算調(diào)度性能指標(biāo)。實(shí)驗(yàn)六銀行家算法（建議4學(xué)時(shí)）一、實(shí)驗(yàn)?zāi)康?．理解死鎖概念、銀行家算法及安全性檢測(cè)算法。2．學(xué)會(huì)在Linux操作系統(tǒng)下‘使用C語言函數(shù)和指針進(jìn)行編程的方法。3．掌握利用C語言設(shè)計(jì)實(shí)現(xiàn)銀行家算法的基本過程。4.驗(yàn)證銀行家算法對(duì)于避免死鎖的作用。二、實(shí)驗(yàn)要求1．學(xué)生應(yīng)完成如下章節(jié)的學(xué)習(xí)：進(jìn)程和線程的調(diào)度。死鎖。2．安裝Linux操作系統(tǒng)，使用C語言編程完成設(shè)計(jì)實(shí)現(xiàn)。三、實(shí)驗(yàn)內(nèi)容1.定義并初始化進(jìn)程及其資源數(shù)據(jù)結(jié)構(gòu)。2．提供一個(gè)用戶界面，用戶利用它可動(dòng)態(tài)輸入進(jìn)程和資源種類等相關(guān)參數(shù)3．設(shè)計(jì)實(shí)現(xiàn)安全狀態(tài)檢測(cè)和銀行家死鎖避免算法的功能函數(shù)。四、實(shí)驗(yàn)方案指導(dǎo)以如下幾組初始數(shù)據(jù)為例，設(shè)計(jì)相應(yīng)程序，判斷下列狀態(tài)是否安全。1.3個(gè)進(jìn)程共享12個(gè)同類資源狀態(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個(gè)進(jìn)程共享多類資源狀態(tài)c下：判斷系統(tǒng)是否安全？若安全，給出安全序列。若進(jìn)程2請(qǐng)求（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實(shí)現(xiàn)方案的主要作是如何輸入，如何初始數(shù)據(jù)，如何調(diào)用對(duì)應(yīng)功能函數(shù)，如何輸出結(jié)果。下面給出一個(gè)實(shí)現(xiàn)方案，供參考。1．開發(fā)一個(gè)交互程序，首先從文件中讀入系統(tǒng)描述信息，包括進(jìn)程的數(shù)目、資源的種類和數(shù)量、每個(gè)進(jìn)程的最大資源請(qǐng)求。程序自動(dòng)根據(jù)文件內(nèi)容創(chuàng)建一個(gè)當(dāng)前系統(tǒng)描述例如，每類資源的數(shù)目用…維數(shù)組R[m]描述，m為資源的種類。每個(gè)R[j]記錄資源Rj的數(shù)量。進(jìn)程的最大需求矩陣用P[n][m]表示，P[il[j]記錄進(jìn)程Pi對(duì)資源Rj的最人需求。分配矩陣和請(qǐng)求矩陣可使用二維數(shù)組表示。2.用戶輸入一個(gè)請(qǐng)求，格式類似：resquest(i,j,k),或release(i,j,k),在這里，i表示進(jìn)程Pi,j表示資源Rj，k是申請(qǐng)/釋放的數(shù)量。對(duì)每一個(gè)請(qǐng)求，系統(tǒng)回應(yīng)是滿足要求還是拒絕分配。3.設(shè)定一個(gè)申請(qǐng)和釋放序列，無任何檢測(cè)和避免死鎖的算法，分配會(huì)導(dǎo)致死鎖。4.設(shè)定一個(gè)申請(qǐng)和釋放序列，按照安全性算法進(jìn)行設(shè)計(jì)，回應(yīng)系統(tǒng)是否安全。然后實(shí)現(xiàn)銀行家算法，確保沒有死鎖的分配。實(shí)驗(yàn)七

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

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