第一篇：操作系統(tǒng)課程設(shè)計(jì)六種算法
《計(jì)算機(jī)操作系統(tǒng)》
學(xué)號(hào)：班級(jí)：軟技姓名：張靖?jìng)?課 程 設(shè) 計(jì) 報(bào) 告
4班
1367003270
目錄 實(shí)驗(yàn)：進(jìn)程調(diào)度算法——時(shí)間片輪轉(zhuǎn)算法 2 實(shí)驗(yàn)：銀行家算法3 實(shí)驗(yàn)：分區(qū)分配算法——4 實(shí)驗(yàn)：頁面置換算法——5 實(shí)驗(yàn)：磁盤調(diào)度算法——
BF和FF
FIFO和LRU SCAN和SSTF 1實(shí)驗(yàn)：進(jìn)程調(diào)度算法——時(shí)間片輪轉(zhuǎn)算法
1.實(shí)驗(yàn)設(shè)計(jì)說明
用時(shí)間片輪轉(zhuǎn)算法模擬單處理機(jī)調(diào)度。
（1）建立一個(gè)進(jìn)程控制塊PCB來代表。PCB包括：進(jìn)程名、到達(dá)時(shí)間、運(yùn)行時(shí)間和進(jìn)程后的狀態(tài)。
進(jìn)程狀態(tài)分為就緒（R）和刪除（C）。
（2）為每個(gè)進(jìn)程任意確定一個(gè)要求運(yùn)行時(shí)間和到達(dá)時(shí)間。
（3）按照進(jìn)程到達(dá)的先后順序排成一個(gè)隊(duì)列。再設(shè)一個(gè)指針指向隊(duì)首和隊(duì)尾。（4）執(zhí)行處理機(jī)調(diào)度時(shí)，開始選擇對(duì)首的第一個(gè)進(jìn)程運(yùn)行。（5）執(zhí)行： a)輸出當(dāng)前運(yùn)行進(jìn)程的名字；
b)運(yùn)行時(shí)間減去時(shí)間片的大小。
（6）進(jìn)程執(zhí)行一次后，若該進(jìn)程的剩余運(yùn)行時(shí)間為零，則刪除隊(duì)首，并將該進(jìn)程的狀態(tài)置為C；若不為空，則將向后找位置插入。繼續(xù)在運(yùn)行隊(duì)首的進(jìn)程。
（7）若進(jìn)程隊(duì)列不空，則重復(fù)上述的（5）和（6）步驟直到所有進(jìn)程都運(yùn)行完為止。
2.實(shí)驗(yàn)代碼
/*****************時(shí)間片輪轉(zhuǎn)調(diào)度算法*******************/ #include
char pname[N];int runtime;/*進(jìn)程名*/ /*服務(wù)時(shí)間*/ int arrivetime;/*到達(dá)時(shí)間*/ char state;/*進(jìn)程狀態(tài)*/ struct pcb*next;/*連接指針*/ }PCB;typedef struct back_team/*后備隊(duì)列定義*/ { PCB*first,*tail;}BACK_TEAM;typedef struct pre_team/*就緒隊(duì)列定義*/ { PCB*first,*tail;}PRE_TEAM;PCB*creat()/*創(chuàng)建PCB*/ {
char s[N];printf(“請(qǐng)輸入進(jìn)程名：n”);scanf(“%s”,s);printf(“請(qǐng)輸入進(jìn)程服務(wù)時(shí)間(/秒)：n”);int t;scanf(“%d”,&t);PCB*p=(PCB*)malloc(sizeof(PCB));strcpy(p->pname,s);p->runtime=t;printf(“請(qǐng)輸入進(jìn)程到達(dá)時(shí)間(/秒)：n”);scanf(“%d”,&t);p->arrivetime=t;p->state='R';p->next=NULL;getchar();return p;} PCB*copy(PCB*p)/*復(fù)制一個(gè)進(jìn)程*/ {
} PCB*getnext(PCB*p,BACK_TEAM*head)/*得到隊(duì)列中下一個(gè)進(jìn)程*/ {
} void del(BACK_TEAM*head,PRE_TEAM*S)/*釋放申請(qǐng)的空間*/ {
PCB*p=head->first->next;while(p){ free(head->first);head->first=p;PCB*s=head->first;if(!p)return NULL;if(!p)return NULL;PCB*s=(PCB*)malloc(sizeof(PCB));strcpy(s->pname,p->pname);s->next=NULL;s->arrivetime=p->arrivetime;s->runtime=p->runtime;s->state=p->state;return s;while(strcmp(s->pname,p->pname))s=s->next;return s->next;
} } p=p->next;head->first=head->tail=NULL;free(head);free(S);BACK_TEAM*creatbt(BACK_TEAM*head)/*創(chuàng)建后備隊(duì)列*/ {
} bool recognize(PRE_TEAM*s1)/*判斷運(yùn)行是否結(jié)束*/ {
if(!s1||!s1->first)return false;PCB*p=creat();if(!head->first)else head->tail->next=p;head->first=p;head->tail=p;return head;if(s1->first==s1->tail)
if(s1->first->state!='C')else return false;return true;PCB*test=s1->first;while(test!=s1->tail&&(test->state!='C'))test=test->next;if(test==s1->tail)
} return true;else return false;PCB*run(PRE_TEAM*s)/*在CPU中運(yùn)行*/ {
if(!s->first){
} printf(“%dt%st”,time,s->first);s->first->runtime--;time++;if(s->first->runtime<=0){
} PCB*p=s->first;s->first->state='C';printf(“%cn”,s->first->state);s->first=p->next;free(p);if(!s->first){
} goto next;s->tail=NULL;spe=false;return NULL;spe=false;return NULL;printf(“%cn”,s->first->state);next:PCB*head=s->first;
} int CREAT(PCB*HEAD,PRE_TEAM*head2,bool*test,PCB*c)/*創(chuàng)建就緒隊(duì)列*/ {
int i=0;if(!head2->first)
if(HEAD){
} if(c){
} head2->first=head2->tail=HEAD;return 1;head2->first=c;c->next=HEAD;head2->tail=HEAD;return 1;s->first=head->next;if(!s->first){
} head->next=NULL;return head;s->tail=NULL;spe=true;if(head2->first==head2->tail){
} else {
} if(*test){
} if(c){
} head2->tail->next=c;head2->tail=c;if(head2->first->arrivetime!=time)for(i=0;i
} if(c->arrivetime!=time){
} head2->tail->next=c;head2->tail=c;time++;return 1;if(HEAD){ head2->tail->next=HEAD;
} } head2->tail=HEAD;return 1;int main(void){
BACK_TEAM*head1=(BACK_TEAM*)malloc(sizeof(BACK_TEAM));head1->first=head1->tail=NULL;PRE_TEAM *head2=(PRE_TEAM*)malloc(sizeof(PRE_TEAM));head2->first=head2->tail=NULL;char ask;int num=0;bool test=true;do{
printf(“要?jiǎng)?chuàng)建進(jìn)程嗎(y/n):”);if((ask=getchar())=='y'||ask=='Y'){
} else if(ask=='n'||ask=='N')else return 1;break;head1=creatbt(head1);num++;}while(1);PCB*p=copy(head1->first);PCB*HEAD=NULL;head2->first=head2->tail=copy(head1->first);printf(“時(shí)刻t進(jìn)程名t狀態(tài)n”);
} while(spe||recognize(head2)){
} del(head1,head2);return 1;CREAT(HEAD,head2,&test,p);HEAD=run(head2);p=copy(getnext(p,head1));3.實(shí)驗(yàn)結(jié)果
和不馬上運(yùn)行:
當(dāng)有兩個(gè)進(jìn)程的時(shí)候
當(dāng)有多個(gè)進(jìn)程的時(shí)候：
4.實(shí)驗(yàn)結(jié)果分析
RR算法：每次調(diào)度時(shí)，把CPU分配給隊(duì)首進(jìn)程，并且令其執(zhí)行一個(gè)時(shí)間片，時(shí)間片的大小從幾個(gè)ms到幾百ms。當(dāng)執(zhí)行的時(shí)間片用完時(shí)，由一個(gè)計(jì)時(shí)器發(fā)出時(shí)鐘中斷請(qǐng)求，調(diào)度程序便依據(jù)此信號(hào)來停止該進(jìn)程的執(zhí)行；并且把它送往就緒隊(duì)列的隊(duì)尾；然后，再把處理劑分配給就緒隊(duì)列中的新隊(duì)首進(jìn)程，同時(shí)也讓它執(zhí)行一個(gè)時(shí)間片。這樣就可以保證就緒隊(duì)列中的所有進(jìn)程在一個(gè)給定時(shí)間內(nèi)均能獲得一時(shí)間片的處理機(jī)執(zhí)行時(shí)間。換言之，系統(tǒng)能在給定的時(shí)間內(nèi)相應(yīng)所有用戶的請(qǐng)求.2實(shí)驗(yàn)：銀行家算法
1.實(shí)驗(yàn)設(shè)計(jì)說明
1.該算法通過建立幾個(gè)簡(jiǎn)單的二維數(shù)組Available,Max,Allocation,Need簡(jiǎn)單的模擬銀行家算法和安全性算法，每個(gè)二維數(shù)組默認(rèn)[][0]為A資源，[][1]為B資源，[][2]為C資源,默認(rèn)有5個(gè)進(jìn)程
2.程序首先要輸入各個(gè)進(jìn)程的三種資源的情況，包括每個(gè)進(jìn)程最大的需求量，已經(jīng)分配的資源量和現(xiàn)在還需要的資源量，以及系統(tǒng)現(xiàn)在剩余的資源量。3.程序會(huì)判斷輸入的信息是否在程序的規(guī)定范圍內(nèi)，正確才運(yùn)行。
4．在執(zhí)行安全算法開始時(shí)，Work∶=Available;② Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finish［i］∶=false;當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish［i］∶=true 5.從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finish［i］=false;并且 Need［i,j］≤Work［j］； 若找到，執(zhí)行6，否則，執(zhí)行7。
6.當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行：
Work［j］∶=Work［i］+Allocation［i,j］;Finish［i］∶=true;然后繼續(xù)執(zhí)行5。
7.如果所有進(jìn)程的Finish［i］=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。
2.實(shí)驗(yàn)代碼
#include
return false;printf(“p%d可以運(yùn)行n”,p);Work[0]+=Allocation[p][0];Work[1]+=Allocation[p][1];Work[2]+=Allocation[p][2];Finish[p]=1;while(num<=25){
if(!Finish[i]&&(Need[i][0]<=Work[0])&&(Need[i][1]<=Work[1])&&(Need[i][2]<=Work[2]))
{
printf(“p%d可以運(yùn)行n”,i);
Work[0]+=Allocation[i][0];
Work[1]+=Allocation[i][1];
Work[2]+=Allocation[i][2];
Finish[i]=1;
}
num++;
i=(i+1)%5;
if(i==p)
i++;} for(m=0;m<5;m++)
if(Finish[m]==0)
break;if(m==5)
return true;else {
printf(“系統(tǒng)處于不安全狀態(tài)!n”);
return false;} } void Banker(int p,int i,int j,int k){ int able[3]={Available[0],Available[1],Available[2]};int need[3]={Need[p][0],Need[p][1],Need[p][2]};int allocation[3]={Allocation[p][0],Allocation[p][1],Allocation[p][2]};if(i<=Need[p][0]&&j<=Need[p][1]&&k<=Need[p][2])
if(i<=Available[0]&&j<=Available[1]&&k<=Available[2])
{
Available[0]-=i;
Available[1]-=j;
Available[2]-=k;
Allocation[p][0]+=i;
Allocation[p][1]+=j;
Allocation[p][2]+=k;
Need[p][0]-=i;
Need[p][1]-=j;
Need[p][2]-=k;
if(!Safe(p))
{
Available[0]=able[0],Available[1]=able[1],Available[2]=able[2];
Need[p][0]=need[0],Need[p][1]=need[1],Need[p][2]=need[2];
Allocation[p][0]=allocation[0],Allocation[p][1]=allocation[1],Allocation[p][2]=allocation[2];
printf(“系統(tǒng)可能發(fā)生死鎖!n”);
}
}
else
printf(“等待!系統(tǒng)資源不足!n”);else
printf(“錯(cuò)誤!申請(qǐng)的資源錯(cuò)誤!n”);} int main(void){ int i,j,k=0,p;printf(“請(qǐng)輸入進(jìn)程的三種資源的情況max{a,b,c} allocation{a,b,c} need{a,b,c}:n”);for(i=0;i<5;i++){
for(j=0;j<3;j++)
scanf(“%d”,&Max[i][j]);
for(j=0;j<3;j++)
scanf(“%d”,&Allocation[i][j]);
for(j=0;j<3;j++)
scanf(“%d”,&Need[i][j]);} printf(“請(qǐng)輸入Available{a,b,c}情況:”);for(i=0;i<3;i++)
scanf(“%d”,&Available[i]);printf(“MaxtAllotNeedtAvain”);for(i=0;i<5;i++){
for(j=0;j<3;j++)
printf(“%d ”,Max[i][j]);
printf(“t”);
for(j=0;j<3;j++)
printf(“%d ”,Allocation[i][j]);
printf(“t”);
for(j=0;j<3;j++)
printf(“%d ”,Need[i][j]);
printf(“t”);
if(k!=4)
printf(“n”);
k++;} for(i=0;i<3;i++)printf(“%d ”,Available[i]);printf(“n請(qǐng)輸入要申請(qǐng)的進(jìn)程和資源<0~4>:”);scanf(“%d %d %d %d”,&p,&i,&j,&k);if(p>=0&&p<=4)Banker(p,i,j,k);else printf(“沒有此進(jìn)程!”);return 1;} 3.實(shí)驗(yàn)結(jié)果
4.實(shí)驗(yàn)結(jié)果分析
這個(gè)實(shí)驗(yàn)只是簡(jiǎn)單的演示了進(jìn)程申請(qǐng)資源之后的進(jìn)程運(yùn)行的其中一個(gè)運(yùn)行序列，因?yàn)檫@個(gè)算法課本上已經(jīng)有詳細(xì)的解說，所以這個(gè)程序并沒有把算法的過程展現(xiàn)出來，只展現(xiàn)了進(jìn)程的運(yùn)行序列結(jié)果，另外，如果申請(qǐng)錯(cuò)誤的話程序會(huì)有不同的結(jié)果
有時(shí)會(huì)發(fā)生死鎖 實(shí)驗(yàn)：分區(qū)分配算法——BF和FF 1.實(shí)驗(yàn)設(shè)計(jì)說明
1.這個(gè)算法模擬的是對(duì)內(nèi)存空間的管理，這個(gè)程序用了一個(gè)簡(jiǎn)單的二維數(shù)組模擬分區(qū)表。2.程序首先要輸入固定的五個(gè)分區(qū)的大小和始址，其次要輸入作業(yè)的大小和實(shí)現(xiàn)的算法，由于這個(gè)程序把FF和BF放到一個(gè)程序中，便于比較兩個(gè)算法。
首次適應(yīng)算法FF(First Fit)把分區(qū)大于等于請(qǐng)求作業(yè)請(qǐng)求的分區(qū)分給請(qǐng)求者，余下部分仍留在空閑區(qū)中，然后修改分區(qū)表。然后打印出分配后的分區(qū)表 最佳適應(yīng)算法BF（Best Fit）
首先把分區(qū)表按空間大小從小到大排序。然后把分區(qū)大于等于請(qǐng)求作業(yè)請(qǐng)求的分區(qū)分給請(qǐng)求者，余下部分仍留在空閑區(qū)中，然后修改分區(qū)表。然后打印出分配后的分區(qū)表
2.實(shí)驗(yàn)代碼 #include
int i,j;for(j=0;j<3;j++)
for(i=0;i<5;i++)
if(ta[i][1]>=job[j]){
} ta[i][1]-=job[j];ta[i][2]+=job[j];break;if(i==5)printf(“內(nèi)存不足!請(qǐng)等待!n”);
} printf(“空閑區(qū)t大小t始址n”);for(j=0;j<5;j++){
} for(i=0;i<3;i++)printf(“%dt”,ta[j][i]);printf(“n”);void BestFit(int job[3]){
int j1,temp1,temp2,temp3,i,j;for(j1=0;j1<3;j1++){
for(i=0;i<5;i++)
for(j=0;j<4;j++)
if(table[j][1]>table[j+1][1]){ temp1=table[j][0];temp2=table[j][1];temp3=table[j][2];
table[j][0]=table[j+1][0];table[j][1]=table[j+1][1];table[j][2]=table[j+1][2];
}
table[j+1][0]=temp1;table[j+1][1]=temp2;table[j+1][2]=temp3;
} if(i==5)printf(“內(nèi)存不足!請(qǐng)等待!n”);printf(“空閑區(qū)t大小t始址n”);for(j=0;j<5;j++){
} for(i=0;i<3;i++)printf(“%dt”,table[j][i]);
} for(i=0;i<5;i++)
if(table[i][1]>=job[j1]){
} table[i][1]-=job[j1];table[i][2]+=job[j1];break;printf(“n”);void main(){
int table1[5][3],job[3],j,i;printf(“請(qǐng)輸入5個(gè)空分區(qū)的大小和始址：”);for(i=0;i<5;i++){
} for(j=0;j<5;j++){
} printf(“請(qǐng)輸入3個(gè)要運(yùn)行作業(yè)的大?。骸?;for(i=0;i<3;i++)scanf(“%d”,&job[i]);for(i=0;i<3;i++)printf(“%dt”,table[j][i]);table[i][0]=i+1;table1[i][0]=i+1;for(j=1;j<3;j++){
} scanf(“%d”,&table[i][j]);table1[i][j]=table[i][j];printf(“n”);printf(“請(qǐng)輸入要實(shí)現(xiàn)的算法1(FF)2(BF):”);
} char c;scanf(“%d”,&i);getchar();if(i==1){
} else
if(i==2){
} BestFit(job);printf(“還要實(shí)現(xiàn)FF嗎(y/n)”);if((c=getchar())=='y')FirstFit(job,table1);FirstFit(job,table1);printf(“還要實(shí)現(xiàn)BF嗎(y/n)”);if((c=getchar())=='y')BestFit(job);3.實(shí)驗(yàn)結(jié)果
4.實(shí)驗(yàn)結(jié)果分析
首先輸入分區(qū)表的分區(qū)情況，然后輸入運(yùn)行作業(yè)的大小，選擇要實(shí)現(xiàn)的算法。第一個(gè)作業(yè)是96，所以找到第四個(gè)分區(qū)，第四個(gè)分區(qū)變?yōu)?22，316，接著到第二個(gè)作業(yè)20，然后把第一個(gè)分區(qū)分給第二個(gè)作業(yè)，則第一個(gè)分區(qū)信息變?yōu)?22，316，到第三個(gè)作業(yè)時(shí)，由于內(nèi)存表中沒有比第三個(gè)請(qǐng)求的分區(qū)還大的分區(qū)，所以會(huì)提示內(nèi)存不足；
然后到BF算法，因?yàn)槭前纯臻g大小排序的，所以第一個(gè)作業(yè)96被分配給了已經(jīng)排好序的內(nèi)存為96的第五個(gè)分區(qū)，第二個(gè)作業(yè)被分配給大小為36的分區(qū)，第三個(gè)作業(yè)被分配給內(nèi)存大小為218的分區(qū)，然后又對(duì)剩余空間再次排隊(duì)，用來給下一批作業(yè)分配。實(shí)驗(yàn)：頁面置換算法——FIFO和LRU 1實(shí)驗(yàn)設(shè)計(jì)說明
程序設(shè)置了兩個(gè)結(jié)構(gòu)體,freeBlock和jobQueue,其中freeBlock代表物理塊,初次創(chuàng)建物理塊時(shí),物理塊的計(jì)時(shí)器time=0,還有代表作業(yè)的index=-1;物理塊有添加和刪除的功能，每一次添加或刪除都要初始化物理塊。并且可以重復(fù)添加和刪除，這樣可以很好的測(cè)試算法的性能。2.算法設(shè)計(jì)的思想是：進(jìn)入物理塊時(shí)間越長(zhǎng)的則物理塊的計(jì)時(shí)器數(shù)值越大，如果物理塊中有要訪問的頁面，則那個(gè)含頁面的物理塊的計(jì)數(shù)器變成1；并且物理塊要滿才會(huì)發(fā)生置換，于是設(shè)置了物理塊計(jì)數(shù)器Time；
2.實(shí)驗(yàn)代碼 #include
jobQueue*job=(jobQueue*)malloc(sizeof(jobQueue));job->index=num;job->next=NULL;if(!head){
jobQueue*j=head;while(j->next)j=j->next;j->next=job;head=job;else
} } return head;freeBlock*creat(freeBlock*head){
} freeBlock*inse(freeBlock*head){
} freeBlock*dele(freeBlock*head){ freeBlock*test=head;while(test){
} freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=head;head=free;return head;test->index=-1;test->time=0;test=test->next;freeBlock*free=(freeBlock*)malloc(sizeof(freeBlock));free->index=-1;free->time=0;free->next=NULL;if(head)free->next=head;head=free;return head;
} freeBlock*test=head;while(test){
} freeBlock*f=head;head=f->next;free(f);return head;test->index=-1;test->time=0;test=test->next;bool check(freeBlock*free,int j){
} void LRU(freeBlock*free,jobQueue*job){
int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){ freeBlock*f=free;while(f){
} return false;if(f->index==j)return true;f=f->next;
} size++;ftest=ftest->next;printf(“LRU置換頁面為：”);while(jtest){
ftest=free;while(ftest){
} ftest=free;while((time==size)&&ftest){ if(check(free,jtest->index)){ if(ftest->index==jtest->index){
} ftest->time++;if(Time
}
}
}
} time=0;Time=0;break;if(ftest->time==Time){
} ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void FIFU(freeBlock*free,jobQueue*job){
int size=0,Time=0,time=0;jobQueue*jtest=job;freeBlock*ftest=free;while(ftest){
} size++;ftest=ftest->next;
printf(“FIFU置換頁面為：”);while(jtest){
ftest=free;while(ftest){
} ftest=free;while((time==size)&&ftest){
if(check(free,jtest->index)){
} if(ftest->time==Time)time=0;Time=0;break;if(ftest->index==-1){
} ftest->time++;if(Time
}
}
} {
} ftest=ftest->next;printf(“%d ”,ftest->index);ftest->index=jtest->index;ftest->time=1;time=0;Time=0;break;jtest=jtest->next;printf(“n”);void main(){
int num,ch,p;freeBlock*block=NULL;jobQueue*job=NULL;printf(“請(qǐng)輸入物理塊數(shù)目：”);scanf(“%d”,&p);for(int i=0;i
} job=creat(job,ch);FIFU(block,job);LRU(block,job);while(true){
printf(“增加物理塊（1）減少物理塊（2）,否則按任意鍵scanf(”%d“,&num);if(num==1){
} else if(num==2){
printf(”要減少幾塊：“);scanf(”%d“,&ch);if(ch>=p){
} for(i=0;i } } } FIFU(block,job);LRU(block,job);else ；break;3.實(shí)驗(yàn)結(jié)果 4.實(shí)驗(yàn)結(jié)果分析 程序開始要輸入物理塊數(shù)目和作業(yè)個(gè)數(shù),然后再輸入作業(yè).在測(cè)試后可以隨意添加或刪除物理塊來測(cè)試算法的性能。實(shí)驗(yàn)：磁盤調(diào)度算法——SCAN和SSTF 1.實(shí)驗(yàn)設(shè)計(jì)說明 算法定義了一個(gè)雙向鏈表，利用雙向鏈表可以很好的進(jìn)行方向的轉(zhuǎn)換，且雙向鏈表的中有代表磁盤號(hào)的標(biāo)識(shí)符index；兩個(gè)算法均采用訪問完一個(gè)磁盤序列時(shí)刪除該序列，其中scan算法實(shí)現(xiàn)時(shí)有點(diǎn)麻煩，首先要找到當(dāng)前磁盤號(hào)序列的Max最大值和最小值Min及指向他們的指針pmax，pmin，另外還要找到當(dāng)前磁頭的相鄰的兩個(gè)訪問序列信息psmax，psmin；還有一個(gè)重要的標(biāo)志，那就是訪問的方向test；當(dāng)遇到最大值或最小值時(shí)，便會(huì)反置test的值，也就是訪問的方向 2.實(shí)驗(yàn)代碼 #include printf(“請(qǐng)輸入磁道隊(duì)列以-1結(jié)束！n”);int ch;memory*head=NULL,*tail,*p;scanf(“%d”,&ch);while(ch!=-1){ p=(memory*)malloc(sizeof(memory));p->index=ch;p->left=p->right=NULL; } } if(!head)head=p;else { } tail=p;scanf(“%d”,&ch);tail->right=p;p->left=tail;return head;void SSTF(memory*head,int index){ int index1=index,num;memory*p1=head,*p,*p2=NULL;while(true){ num=abs(p1->index-index1);p=p1;while(p){ } if((abs(p->index-index1))<=num){ } p=p->right;num=abs(p->index-index1);if(p!=p1)p2=p;p=p1->right;if(p2){ } else { printf(“%d ”,p1->index);index1=p2->index;printf(“%d ”,p2->index);p2->left->right=p2->right;if(p2->right)p2->right->left=p2->left;free(p2);p2=NULL; } } } index1=p1->index;if(!p){ } else { } p=p1;p1=p1->right;free(p);continue;free(p1);break;void SCAN(memory*head,int index){ int index1=index,num,test,max=0,min=199,Max,Min;printf(“請(qǐng)輸入磁頭查詢方向<0正向><1負(fù)向>!n”);scanf(“%d”,&test);memory*p1=head,*p,*p2=NULL,*pmax,*pmin,*psmax=NULL,*psmin=NULL; while(p1){ } p1=head;while(p1){ if(!test){ if(!test){ } else { } p1=p1->right;pmin=p1;if(p1->index<=min)Min=min=p1->index;pmax=p1;if(p1->index>=max)Max=max=p1->index; } } pmin=p1;if(p1->index<=min)Min=min=p1->index; else { } p1=p1->right;pmax=p1;if(p1->index>=max)Max=max=p1->index;p1=head;while(true){ num=abs(p1->index-index1);p=p1;while(p){ if(!test){ if(p->index>=index1&&p->index<=max) } } if((abs(p->index-index1))<=num){ } psmin=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;else { } p=p->right;if(p->index<=index1&&p->index>=min) if(abs(p->index-index1)<=num){ } psmax=p; num=abs(p->index-index1);if(p->left&&p->right)p2=p;if(p2) { if(!test){ } else { index1=psmax->index;p=psmax;if(index1==Min){ } test=0;Max=Min=-1;p1=pmin;index1=psmin->index;p=psmin;if(index1==Max){ } test=1;Min=Max=-1;p1=pmax; } printf(“%d ”,index1);if(!test){ } else { if(psmax)if(psmin){ } else { } psmax->right->left=psmax->left;if(psmax->left) psmax->left->right=psmax->right;psmin->left->right=psmin->right;if(psmin->right) psmin->right->left=psmin->left;free(psmin);free(psmax); } } { } else { } psmin->right->left=psmin->left;if(psmin->left) psmin->left->right=psmin->right;psmax->left->right=psmax->right;if(psmax->right) psmax->right->left=psmax->left;free(psmax);free(psmin);else { if(!test){ if(p1->index==Max){ test=1; } } Min=Max=-1;else { } if(psmax){ } else { } printf(“%d ”,index1);index1=psmin->index;p=psmin;index1=psmax->index;p=psmax;if(p1->index==Min){ } test=0;Max=Min=-1; } } } if(p->left&&!p->right){ } else if(p->right&&!p->left){ } else if(!p->right&&!p->left){ } free(p);free(p);break;p1=p->right;p1->left=NULL;p1=p->left;p1->right=NULL;p2=psmax=psmin=NULL;void main(){ int p,t;memory*head=creat();printf(“請(qǐng)輸入磁頭當(dāng)前的位置(0-199)”);scanf(“%d”,&p);printf(“要進(jìn)行的算法：<0:SCAN><1:SSTF>”);scanf(“%d”,&t);if(!t)SCAN(head,p);else SSTF(head,p);} 3.實(shí)驗(yàn)結(jié)果 4.實(shí)驗(yàn)結(jié)果分析 輸入要訪問的磁盤號(hào)，然后選擇要實(shí)現(xiàn)的算法就可以看到結(jié)果，當(dāng)選0（正向）的時(shí)候由于當(dāng)前的磁頭在143處，所以要訪問的磁盤號(hào)就必須大于143，當(dāng)最大的磁盤號(hào)訪問完時(shí)，就轉(zhuǎn)向小于143的磁盤開始由大向小訪問，選1的話則相反。最短尋道時(shí)間算法是從整個(gè)隊(duì)列中選擇距離磁頭最近的訪問，算法的實(shí)現(xiàn)運(yùn)用了絕對(duì)值的概念 1.實(shí)驗(yàn)題目: 磁盤調(diào)度算法。 建立相應(yīng)的數(shù)據(jù)結(jié)構(gòu)； 在屏幕上顯示磁盤請(qǐng)求的服務(wù)狀況； 將一批磁盤請(qǐng)求的情況存磁盤文件，以后可以讀出并重放； 計(jì)算磁頭移動(dòng)的總距離及平均移動(dòng)距離； 支持算法：FIFO、SSTF、SCAN、CSCAN; 2.設(shè)計(jì)目的: 調(diào)度磁盤I/O請(qǐng)求服務(wù)，采用好的方式能提高訪問時(shí)間和帶寬。本實(shí)驗(yàn)通過編程對(duì)磁盤調(diào)度算法的實(shí)現(xiàn)，加深對(duì)算法的理解，同時(shí)通過用C++語言編寫程序?qū)崿F(xiàn)這些算法，并在windos平臺(tái)上實(shí)現(xiàn)，更好的掌握操作系統(tǒng)的原理以及實(shí)現(xiàn)方法，提高綜合運(yùn)用專業(yè)課知識(shí)的能力。 3.任務(wù)及要求 3.1 設(shè)計(jì)任務(wù) 編程實(shí)現(xiàn)下述磁盤調(diào)度算法，并求出每種算法的平均尋道長(zhǎng)度： 1、先來先服務(wù)算法（FCFS） 2、最短尋道時(shí)間算法（SSTF） 3、掃描算法（SCAN） 4、循環(huán)掃描算法（CSCAN） 3.2 設(shè)計(jì)要求 對(duì)用戶指定的磁盤調(diào)度請(qǐng)求序列，基于以上四種算法，實(shí)現(xiàn)各自的調(diào)度順序并輸出，同時(shí)計(jì)算出各種算法下的平均尋道長(zhǎng)度。 4.算法及數(shù)據(jù)結(jié)構(gòu) 4.1算法的總體思想 queue[n] 為請(qǐng)求調(diào)度序列，diskrode為磁盤磁道數(shù)，headstarts為正在調(diào)度的磁道 ①先來先服務(wù)算法（FCFS）按queue[n]數(shù)組的順序進(jìn)行磁盤調(diào)度，將前一個(gè)調(diào)度磁道與下一個(gè)調(diào)度磁道的差值累加起來，得到總的尋道長(zhǎng)度，再除以n得到平均尋道長(zhǎng)度。 ②最短尋道時(shí)間優(yōu)先算法（SSTF）將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，通過循環(huán)語句找出離起始磁頭最短的位置。 ③掃描算法（SCAN） 將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當(dāng)?shù)蓝它c(diǎn)（queue[0]或queue[n-1]）時(shí)，再在定位處反向遍歷到另一端。當(dāng)調(diào)度磁道不在queue端點(diǎn)時(shí)，總的尋道長(zhǎng)度為為前一個(gè)磁道與后一個(gè)磁 道差值的累加，當(dāng)?shù)竭_(dá)端點(diǎn)且queue[n]未全調(diào)度時(shí)，總尋道長(zhǎng)度加上端點(diǎn)值再加上下一個(gè)調(diào)度磁道的值，再按前面的算法進(jìn)行，直到磁道全部都調(diào)度完畢，得到總的尋道長(zhǎng)度，除以n得到平均尋道長(zhǎng)度。 ④循環(huán)掃描算法（CSCAN）將queue[n]進(jìn)行由小到大的排序，首先定位當(dāng)前調(diào)度磁headstarts在queue[n]的位置，然后在此位置按給定的方向遍歷queue[n]，當(dāng)?shù)蓝它c(diǎn)（queue[0]或queue[n-1]）時(shí)，反向到另一端點(diǎn)再以此方向進(jìn)行遍歷，直到queue[n]中所有都調(diào)度完。當(dāng)調(diào)度磁道不在queue端點(diǎn)時(shí)，總的尋道長(zhǎng)度為為前一個(gè)磁道與后一個(gè)磁道差值的累加，當(dāng)?shù)竭_(dá)端點(diǎn)且queue[n]未全調(diào)度時(shí)，總尋道長(zhǎng)度加上端點(diǎn)值再加上磁盤磁道總長(zhǎng)度，再加上下一個(gè)調(diào)度磁道的值，再按前面的算法進(jìn)行，直到磁道全部都調(diào)度完畢，得到總的尋道長(zhǎng)度，除以n得到平均尋道長(zhǎng)度。 5、源代碼： #include 1、先來先服務(wù)算法（FCFS)**********”< cout<<“****** 2、最短尋道時(shí)間優(yōu)先算法(SSTF)**********”< cout<<“****** 3、掃描算法(SCAN)**********”< cout<<“****** 4、循環(huán)掃描算法(CSCAN)**********”< cout<<“****** 5、退出 **********”< /*======================初始化序列=======================*/ void init(int queue[],int queue_copy[],int n){ int i;for(i=0;i //對(duì)當(dāng)前正在執(zhí)行的磁道號(hào)進(jìn)行定位，返回磁道號(hào)小于當(dāng)前磁道中最大的一個(gè) int fix(int queue[], int n, int headstarts){ int i =0;while(i /* ====================以下是FCFS算法==================*/ void FCFS(int queue[],int n,int diskrode,int headstarts)//queue是請(qǐng)求調(diào)度序列，n為其個(gè)數(shù)，diskroad為磁盤磁道數(shù)，headstarts為正在調(diào)度的磁道 { cout<<“************以下為FCFS調(diào)度算法***********”< /*=====================SSTF算法====================*/ void SSTF(int queue[], int n, int diskrode, int headstarts){ int k=1;int l,r;int i,j,count=0;queue =bubble(queue,n);cout<<“************以下為SSTF調(diào)度算法***********”< -headstarts)){ cout< /*======================以下是SCAN算法====================*/ void SCAN(int queue[], int n, int diskrode, int headstarts){ int direction, i, fixi;cout<<“***********以下是SCAN調(diào)度算法*************”< /*======================以下是CSCAN算法====================*/ void CSCAN(int queue[],int n,int diskrode,int headstarts){ int direction,i,fixi;cout<<“***********以下是CSCAN調(diào)度算法*************”< void main(){ int n, i, diskrode, headstarts;//n表示調(diào)度磁盤請(qǐng)求序列queue的長(zhǎng)度，diskrode表示磁盤磁道的個(gè)數(shù)，headstarts表示目前正在調(diào)度的磁道； cout<<“請(qǐng)輸入磁盤的總磁道數(shù):”< if(menux ==2)SSTF(queue,n,diskrode,headstarts); if(menux ==3)SCAN(queue,n,diskrode,headstarts);if(menux ==4)CSCAN(queue,n,diskrode,headstarts);if(menux ==5)cout<<“程序結(jié)束,謝謝使用！”< 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 Noi 目 錄 1 課程設(shè)計(jì)目的及要求……………………………………………………錯(cuò)誤！未定義書簽。2 相關(guān)知識(shí)…………………………………………………………………錯(cuò)誤！未定義書簽。3 題目分析…………………………………………………………………2 4 概要設(shè)計(jì)…………………………………………………………………2 4.1 先來先服務(wù)（FCFS）的設(shè)計(jì)思想……………………………….2 4.2 最短尋道時(shí)間優(yōu)先調(diào)度（SSTF）的設(shè)計(jì)思想…………………..2 4.3 掃描算法（SCAN）的設(shè)計(jì)思想…………………………………2 4.4 循環(huán)掃描（CSCAN）的設(shè)計(jì)思想………………………………..2 5 代碼及流程………………………………………………………………3 5.1 流程圖……………………………………………………………...3 5.2 源代碼……………………………………………………………...8 6 運(yùn)行結(jié)果…………………………………………………………………16 7 設(shè)計(jì)心得…………………………………………………………………19 參考文獻(xiàn)…………………………………………………………………………19 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No1 1 課程設(shè)計(jì)目的及要求 設(shè)計(jì)目的：加深對(duì)操作系統(tǒng)原理的進(jìn)一步認(rèn)識(shí)，加強(qiáng)實(shí)踐動(dòng)手能力和程序開發(fā)能力的培養(yǎng)，提高分析問題解決問題的能力，培養(yǎng)合作精神，以鞏固和加深磁盤調(diào)度的概念。操作系統(tǒng)是一門工程性很強(qiáng)的課程，它不僅要求學(xué)生掌握操作系統(tǒng)的工作原理和理論知識(shí)，也要求學(xué)生的實(shí)際動(dòng)手能力，以加深對(duì)所學(xué)習(xí)內(nèi)容的理解，使學(xué)生熟練地掌握計(jì)算機(jī)的操作方法，使用各種軟件工具，加強(qiáng)對(duì)課程內(nèi)容的理解。這次課程設(shè)計(jì)，就是通過模擬磁臂調(diào)度來加深對(duì)操作系統(tǒng)中磁臂調(diào)度概念的理解。使學(xué)生熟悉磁盤管理系統(tǒng)的設(shè)計(jì)方法；加深對(duì)所學(xué)各種磁盤調(diào)度算法的了解及其算法的特點(diǎn)。 設(shè)計(jì)要求：編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法,并求出每種算法的平均尋道長(zhǎng)度；要求設(shè)計(jì)主界面可以靈活選擇某算法，且以下算法都要實(shí)現(xiàn) 1、先來先服務(wù)算法（FCFS） 2、最短尋道時(shí)間優(yōu)先算法（SSTF） 3、掃描算法（SCAN） 4、循環(huán)掃描算法（CSCAN）相關(guān)知識(shí) 數(shù)據(jù)結(jié)構(gòu)：數(shù)組 now:當(dāng)前磁道號(hào); array[]:放置磁道號(hào)的數(shù)組; void FCFS(int array[],int m)先來先服務(wù)算法(FCFS)void SSTF(int array[],int m)最短尋道時(shí)間優(yōu)先算法(SSTF)void SCAN(int array[],int m)掃描算法(SCAN)void CSCAN(int array[],int m)循環(huán)掃描算法(CSCAN)磁盤調(diào)度：當(dāng)有多個(gè)進(jìn)程都請(qǐng)求訪問磁盤時(shí)，采用一種適當(dāng)?shù)尿?qū)動(dòng)調(diào)度算法，使各進(jìn)程對(duì)磁盤的平均訪問（主要是尋道）時(shí)間最小。目前常用的磁盤調(diào)度算法有：1）閑來先服務(wù)2）最短尋道時(shí)間優(yōu)先3）掃描算法4）循環(huán)掃描算法等 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No2 3 題目分析 選擇一個(gè)自己熟悉的計(jì)算機(jī)系統(tǒng)和程序設(shè)計(jì)語言模擬操作系統(tǒng)基本功能的設(shè)計(jì)方法及其實(shí)現(xiàn)過程 完成各分項(xiàng)功能。在算法的實(shí)現(xiàn)過程中，要求可決定變量應(yīng)是動(dòng)態(tài)可變的；同時(shí)模塊應(yīng)該有一個(gè)合理的輸出結(jié)果。具體可參照實(shí)驗(yàn)的程序模擬.各功能程序要求自行編寫程序?qū)崿F(xiàn)，不得調(diào)用現(xiàn)有操作系統(tǒng)提供的模塊或功能函數(shù)。磁盤調(diào)度程序模擬。先來先服務(wù)調(diào)度算法.最短尋道時(shí)間優(yōu)先調(diào)度，循環(huán)（SCAN）調(diào)度算法。程序設(shè)計(jì)語言自選，最終以軟件（含源代碼以及執(zhí)行程序）和設(shè)計(jì)報(bào)告的形式提交課程設(shè)計(jì)結(jié)果.。磁盤調(diào)度讓有限的資源發(fā)揮更大的作用。在多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，各個(gè)進(jìn)程可能會(huì)不斷提出不同的對(duì)磁盤進(jìn)行讀/寫操作的請(qǐng)求。由于有時(shí)候這些進(jìn)程的發(fā)送請(qǐng)求的速度比磁盤響應(yīng)的還要快，因此我們有必要為每個(gè)磁盤設(shè)備建立一個(gè)等待隊(duì)列。概要設(shè)計(jì) 1.先來先服務(wù)（FCFS）的設(shè)計(jì)思想 即先來的請(qǐng)求先被響應(yīng)。FCFS策略看起來似乎是相當(dāng)“公平”的，但是當(dāng)請(qǐng)求的頻率過高的時(shí)候FCFS策略的響應(yīng)時(shí)間就會(huì)大大延長(zhǎng)。FCFS策略為我們建立起一個(gè)隨機(jī)訪問機(jī)制的模型，但是假如用這個(gè)策略反復(fù)響應(yīng)從里到外的請(qǐng)求，那么將會(huì)消耗大量的時(shí)間。為了盡量降低尋道時(shí)間，看來我們需要對(duì)等待著的請(qǐng)求進(jìn)行適當(dāng)?shù)呐判颍皇呛?jiǎn)單的使用FCFS策略。這個(gè)過程就叫做磁盤調(diào)度管理。有時(shí)候fcfs也被看作是最簡(jiǎn)單的磁盤調(diào)度算法。 2.最短尋道時(shí)間優(yōu)先調(diào)度（SSTF）的設(shè)計(jì)思想 最短時(shí)間優(yōu)先算法選擇這樣的進(jìn)程。要求訪問的磁道，與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短。 3.掃描算法（SCAN）的設(shè)計(jì)思想 掃描（SCAN）調(diào)度算法:該算法不僅考慮到欲訪問 的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮的是磁頭當(dāng)前的移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，SCAN算法所考慮的下一個(gè)訪問對(duì)象，應(yīng)是其欲訪問的磁道，既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外的訪問，直至再無更外的磁道需要訪問時(shí)，才將磁道換向自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來調(diào)度，也就是要訪問的當(dāng)前位置內(nèi)距離最近者，這樣，磁頭又逐步地從外向里移動(dòng)，直至再無更里面的磁道要訪問，從而避免了出現(xiàn)“饑餓”現(xiàn)像。 4.循環(huán)掃描（CSACN）的設(shè)計(jì)思想 循環(huán)掃描（CSCAN）算法：當(dāng)磁頭剛從里向外移動(dòng)而越過了某一磁道時(shí)，恰好又有一進(jìn)程請(qǐng)求訪問此磁道，這時(shí)，該里程就必須等待，為了減少這種延遲，CSCAN算法規(guī)定磁頭單向移動(dòng)，而本實(shí)驗(yàn)過程中我們所設(shè)計(jì)的是磁頭從里向外移動(dòng)，而從外向里移動(dòng)時(shí)只須改方向而已，本實(shí)驗(yàn)未實(shí)現(xiàn)。但本實(shí)驗(yàn)已完全能演示循環(huán)掃描的全過程。 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No3 5 代碼及流程 1.先來先服務(wù)（FCFS） 圖 1—1 FCFS的流程圖 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No4 2.最短尋道時(shí)間優(yōu)先調(diào)度（SSTF） 圖1—2 SSTF的流程圖 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No5 3.掃描算法（SCAN） 圖1—3 SCAN的流程圖 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No6 4.循環(huán)掃描（CSCAN） 圖1—4 CSCAN的流程圖 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No7 圖1—5 主函數(shù)的流程圖 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No8 源代碼： #include“stdio.h” #include“stdlib.h” //#include“iostream.h” #define maxsize 100 //定義最大數(shù)組域 //先來先服務(wù)調(diào)度算法 void FCFS(int array[],int m){ int sum=0,j,i;int avg;printf(“n FCFS調(diào)度結(jié)果: ”);for(i=0;i } avg=sum/(m-1);//計(jì)算平均尋道長(zhǎng)度 printf(“n 移動(dòng)的總道數(shù)： %d n”,sum);printf(“平均尋道長(zhǎng)度： %d n”,avg);} //最短尋道時(shí)間優(yōu)先調(diào)度算法 void SSTF(int array[],int m){ int temp;int k=1;int now,l,r;int i,j,sum=0;int avg;for(i=0;i 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No9 array[i]=array[j];array[j]=temp;} } } for(i=0;i for(i=m-1;i>=0;i--)//將數(shù)組磁道號(hào)從大到小輸出 printf(“%d ”,array[i]);sum=now-array[0];//計(jì)算移動(dòng)距離 } else if(array[0]>=now)//判斷整個(gè)數(shù)組里的數(shù)是否都大于當(dāng)前磁道號(hào) { for(i=0;i printf(“%d ”,array[l]);sum+=now-array[l];//計(jì)算移動(dòng)距離 now=array[l];l=l-1;} else 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No10 { printf(“%d ”,array[r]);sum+=array[r]-now;//計(jì)算移動(dòng)距離 now=array[r];r=r+1;} } if(l=-1){ for(j=r;j printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//計(jì)算移動(dòng)距離 } else { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} sum+=array[m-1]-array[0];//計(jì)算移動(dòng)距離 } } avg=sum/m;printf(“n 移動(dòng)的總道數(shù)： %d n”,sum);printf(“平均尋道長(zhǎng)度： %d n”,avg);} //掃描算法 void SCAN(int array[],int m)//先要給出當(dāng)前磁道號(hào)和移動(dòng)臂的移動(dòng)方向 { int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No11 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n SCAN調(diào)度結(jié)果: ”);for(i=m-1;i>=0;i--){ printf(“%d ”,array[i]);//將數(shù)組磁道號(hào)從大到小輸出 } sum=now-array[0];//計(jì)算移動(dòng)距離 } else if(array[0]>=now)//判斷整個(gè)數(shù)組里的數(shù)是否都大于當(dāng)前磁道號(hào) { printf(“n SCAN調(diào)度結(jié)果: ”);for(i=0;i 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No12 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=r;j //循環(huán)掃描算法 void CSCAN(int array[],int m){ int temp;int k=1;int now,l,r,d;int i,j,sum=0;int avg;for(i=0;i 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No13 { temp=array[i];array[i]=array[j];array[j]=temp;} } } for(i=0;i printf(“n CSCAN調(diào)度結(jié)果: ”);for(i=0;i printf(“%d ”,array[i]);//將磁道號(hào)從小到大輸出 } sum=now-array[0]+array[m-1];//計(jì)算移動(dòng)距離 } else if(array[0]>=now)//判斷整個(gè)數(shù)組里的數(shù)是否都大于當(dāng)前磁道號(hào) { printf(“n CSCAN調(diào)度結(jié)果: ”);for(i=0;i printf(“%d ”,array[i]);//將磁道號(hào)從小到大輸出 } sum=array[m-1]-now;//計(jì)算移動(dòng)距離 } else { while(array[k] 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No14 { for(j=l;j>=0;j--){ printf(“%d ”,array[j]);} for(j=m-1;j>=r;j--){ printf(“%d ”,array[j]);} sum=2*(array[m-1]-array[0])-array[r]+now;//計(jì)算移動(dòng)距離 }//磁道號(hào)減小方向 else { for(j=r;j // 操作界面 int main(){ int c;FILE *fp;//定義指針文件 int cidao[maxsize];//定義磁道號(hào)數(shù)組 int i=0,count;fp=fopen(“cidao.txt”,“r+”);//讀取cidao.txt文件 if(fp==NULL)//判斷文件是否存在 { printf(“n 請(qǐng) 先 設(shè) 置 磁 道!n”);exit(0);} while(!feof(fp))//如果磁道文件存在 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No15 { fscanf(fp,“%d”,&cidao[i]);//調(diào)入磁道號(hào) i++;} count=i-1;printf(“n-------------------n”);printf(“ 10-11OS課程設(shè)計(jì)--磁盤調(diào)度算法系統(tǒng)n”);printf(“ 計(jì)算機(jī)科學(xué)與技術(shù)二班n”);printf(“ 姓名：宋思揚(yáng)n”);printf(“ 學(xué)號(hào)：0803050203n”);printf(“ 電話：************n”);printf(“ 2010年12月29日n”);printf(“n-------------------n”);printf(“n 磁道讀取結(jié)果：n”);for(i=0;i 1、先來先服務(wù)算法（FCFS）n”);printf(“ 2、最短尋道時(shí)間優(yōu)先算法（SSTF）n”);printf(“ 3、掃描算法（SCAN）n”);printf(“ 4、循環(huán)掃描算法（CSCAN）n”);printf(“ 5.退出n”);printf(“n”);printf(“請(qǐng)選擇：”);scanf(“%d”,&c);if(c>5)break;switch(c)//算法選擇 { case 1: FCFS(cidao,count);//先來先服務(wù)算法 printf(“n”);break;case 2: SSTF(cidao,count);//最短尋道時(shí)間優(yōu)先算法 printf(“n”);break;case 3: 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No16 SCAN(cidao,count);//掃描算法 printf(“n”);break;case 4: CSCAN(cidao,count);//循環(huán)掃描算法 printf(“n”);break;case 5: exit(0);} } return 0;} 6 運(yùn)行結(jié)果 圖2—1 運(yùn)行界面 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No17 圖2—2 運(yùn)行FCFS的界面 圖2—3 運(yùn)行SSTF的界面 圖2—4 運(yùn)行SCAN的界面 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No18 圖2—5 運(yùn)行SCAN的界面 圖2—6 運(yùn)行CSCAN的界面 圖2—7 運(yùn)行CSCAN的界面 沈陽理工大學(xué) 沈陽理工大學(xué)課程設(shè)計(jì)專用紙 No19 運(yùn)行結(jié)果： 四種磁盤調(diào)度運(yùn)行結(jié)果正確，與預(yù)期的相符。設(shè)計(jì)心得 此次操作系統(tǒng)的課程設(shè)計(jì)，從理論到實(shí)踐，在兩個(gè)星期的日子里，可以說是苦多于甜，但是可以學(xué)到很多很多的的東西，同時(shí)不僅可以鞏固了以前所學(xué)過的知識(shí)，而且學(xué)到了很多在書本上所沒有學(xué)到過的知識(shí)。通過這次課程設(shè)計(jì)使我懂得了理論與實(shí)際相結(jié)合是很重要的，只有理論知識(shí)是遠(yuǎn)遠(yuǎn)不夠的，只有把所學(xué)的理論知識(shí)與實(shí)踐相結(jié)合起來，從理論中得出結(jié)論，才能真正為社會(huì)服務(wù)，從而提高自己的實(shí)際動(dòng)手能力和獨(dú)立思考的能力。 本次實(shí)驗(yàn)首先要了解磁盤調(diào)度的工作原理及四種調(diào)度方法的工作原理。在課程設(shè)計(jì)前的準(zhǔn)備工作時(shí)，先把這部分工作做完了。在設(shè)計(jì)總的程序框架的時(shí)候，要注意各功能模塊的位置，盡量做到簡(jiǎn)潔、有序；各功能模塊與主程序要正確銜接。 在設(shè)計(jì)的過程中遇到許多問題，我設(shè)計(jì)的是四種調(diào)度算法中的后兩種。例如：在最初程序設(shè)計(jì)時(shí)主要有兩種構(gòu)思：1）選用數(shù)據(jù)結(jié)構(gòu)是鏈表的。2）選用數(shù)組。我最初嘗試了用鏈表，覺得方便易懂，但是在循環(huán)掃描處出現(xiàn)了些問題，后來又轉(zhuǎn)變了設(shè)計(jì)思路，選用了數(shù)組，直接進(jìn)行排序，然后再聯(lián)系到各功能模塊。 同時(shí)在設(shè)計(jì)的過程中發(fā)現(xiàn)了自己的不足之處，對(duì)以前所學(xué)過的知識(shí)理解得不夠深刻，掌握得不夠牢固，自身知識(shí)的很多漏洞，看到了自己的實(shí)踐經(jīng)驗(yàn)還是比較缺乏，理論聯(lián)系實(shí)際的能力還急需提高。比如說編語言掌握得不好，應(yīng)用程序編寫不太會(huì)……通過這次課程設(shè)計(jì)之后，一定把以前所學(xué)過的知識(shí)重新溫故。在此，也感謝在課程設(shè)計(jì)過程中幫我解惑的老師和同學(xué)。參考文獻(xiàn) [1] 《操作系統(tǒng)》 人民郵電出版社 宗大華 宗濤 陳吉人 編著 [2] 《C語言程序設(shè)計(jì)》 清華大學(xué)出版社 馬秀麗 劉志嫵 李筠 編著 [3] 《操作系統(tǒng)實(shí)驗(yàn)指導(dǎo)書》 沈陽理工大學(xué) 唐巍 菀勛 編著 沈陽理工大學(xué) 《操作系統(tǒng)》課程設(shè)計(jì)報(bào)告 課題： 銀行家算法 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名 班級(jí) 計(jì)算機(jī) 學(xué)號(hào) 指導(dǎo)教師 信息工程學(xué)院 一、實(shí)驗(yàn)要求和實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)?zāi)康模罕菊n程設(shè)計(jì)是學(xué)生學(xué)習(xí)完《操作系統(tǒng)原理》課程后，進(jìn)行的一次全面的綜合訓(xùn)練，通過課程設(shè)計(jì)，讓學(xué)生更好地掌握操作系統(tǒng)的原理及實(shí)現(xiàn)方法，加深對(duì)操作系統(tǒng)基礎(chǔ)理論和重要算法的理解，加強(qiáng)學(xué)生的動(dòng)手能力。 實(shí)驗(yàn)要求：從課程設(shè)計(jì)的目的出發(fā)，通過設(shè)計(jì)工作的各個(gè)環(huán)節(jié)，達(dá)到以下教學(xué)要求：兩人一組，每組從所給題目中任選一個(gè)（如自擬題目，需經(jīng)指導(dǎo)教師同意），每個(gè)學(xué)生必須獨(dú)立完成課程設(shè)計(jì)，不能相互抄襲，同組者文檔不能相同；設(shè)計(jì)完成后，將所完成的工作交由指導(dǎo)教師檢查；要求寫出一份詳細(xì)的設(shè)計(jì)報(bào)告。 二、設(shè)計(jì)內(nèi)容： 課題一、編制銀行家算法通用程序，并檢測(cè)所給狀態(tài)的系統(tǒng)安全性。 1）銀行家算法中的數(shù)據(jù)結(jié)構(gòu)： 可利用資源向量Available。這是一個(gè)含有m個(gè) 元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動(dòng)態(tài)地改變。Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj 類資源K個(gè)。 最大需求矩陣Max。這是一個(gè)n*m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i，j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。 1.分配矩陣Allocation。這也是一個(gè)n*m的矩陣，它定義了系統(tǒng)中每一類資料當(dāng)前已分配給沒一進(jìn)程的資源數(shù)。如果Allocation[i，j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的數(shù)目為K。需求矩陣Need。這也是一個(gè)n*m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。 上述三個(gè)矩陣存在如下關(guān)系： Need[i,j]= Max[i，j]- Allocation[i，j] 2）銀行家算法 設(shè)Request[i] 是進(jìn)程Pi的請(qǐng)求向量，如果Request[i，j]=K,表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查：如果Request[i，j]<= Need[i,j]，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 三、設(shè)計(jì)思路 設(shè)計(jì)思路A、設(shè)計(jì)進(jìn)程對(duì)各在資源最大申請(qǐng)表示及初值確定。B、設(shè)定系統(tǒng)提供資源初始狀態(tài)。C、設(shè)定每次某個(gè)進(jìn)程對(duì)各類資源的申請(qǐng)表示。D、編制程序，依據(jù)銀行家算法，決定其申請(qǐng)是否得到滿足。 四、詳細(xì)設(shè)計(jì) 1、初始化：由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。 2、銀行家算法：在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。銀行家算法的基本思想是分配資源之前,判斷系統(tǒng)是否是安全的;若是,才分配。它是最具有代表性的避免死鎖的算法。 設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。 (1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)(2)；否則，出錯(cuò)。 (2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)(3)；否則，出錯(cuò)。 銀行家算法的數(shù)據(jù)結(jié)構(gòu) 假設(shè)有M個(gè)進(jìn)程N(yùn)類資源，則有如下數(shù)據(jù)結(jié)構(gòu): #define W #define R int M ; //總進(jìn)程數(shù) int N ; //資源種類 int ALL_RESOURCE[W]; //各種資源的數(shù)目總和 int MAX[W][R]; //M個(gè)進(jìn)程對(duì)N類資源最大資源需求量 int AVAILABLE[R]; //系統(tǒng)可用資源數(shù) int ALLOCATION[W][R]; //M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量 int NEED[W][R]; //M個(gè)進(jìn)程還需要N類資源的資源量 int Request[R]; //請(qǐng)求資源個(gè)數(shù) 3.“安全性檢測(cè)“算法 1)先定義兩個(gè)變量,用來表示推算過程的數(shù)據(jù).F[n]=A[n],表示推算過程中,系統(tǒng)中剩余資源量的變化.J[n]=False表示推算過程中各進(jìn)程是否假設(shè)“已完成“ 系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLE[i]-=REQUEST[cusneed][i]; ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];、NEED[cusneed][i]-=REQUEST[cusneed][i]; 4、安全性檢查算法 1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH 2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH==false; NEED<=Work; 如找到，執(zhí)行(3)；否則，執(zhí)行(4) 3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。 Work+=ALLOCATION; Finish=true; GOTO 4)如所有的進(jìn)程Finish= true，則表示安全；否則系統(tǒng)不安全。 安全狀態(tài): 在某時(shí)刻系統(tǒng)中所有進(jìn)程可以排列一個(gè)安全序列:{P1,P2,`````Pn},剛稱此時(shí),系統(tǒng)是安全的.所謂安全序列{P1,P2,`````Pn}是指對(duì)于P2,都有它所需要剩余資源數(shù)量不大于系統(tǒng)掌握的剩余的空間資源與所有Pi(j 最大需求 尚需 P1 P2 P3 4?????????????2 在每一次進(jìn)程中申請(qǐng)的資源,判定一下,若實(shí)際分配的話,之后系統(tǒng)是否安全.銀行家算法的數(shù)據(jù)結(jié)構(gòu).五、代碼清單 #include #include #include #include #include #include const int MAX_P=20; const int MAXA=10; //定義A類資源的數(shù)量 const int MAXB=5; const int MAXC=7; typedef struct node{ int a; int b; int c; int remain_a; int remain_b; int remain_c; }bank; typedef struct node1{ char name[20]; int a; int b; int c; int need_a; int need_b; int need_c; }process; bank banker; process processes[MAX_P]; int quantity; //初始化函數(shù) void initial() { int i; banker.a=MAXA; banker.b=MAXB; banker.c=MAXC; banker.remain_a=MAXA; banker.remain_b=MAXB; banker.remain_c=MAXC; for(i=0;i strcpy(processes[i].name,““); processes[i].a=0; processes[i].b=0; processes[i].c=0; processes[i].need_a=0; processes[i].need_b=0; processes[i].need_c=0; } } //新加作業(yè) void add() { char name[20]; int flag=0; int t; int need_a,need_b,need_c; int i; cout< cout<<“新加作業(yè)“< cout<<“請(qǐng)輸入新加作業(yè)名:“; cin>>name; for(i=0;i if(!strcmp(processes[i].name,name)){ flag=1; break; } } if(flag){ cout<<“錯(cuò)誤,作業(yè)已存在“< } else{ cout<<“本作業(yè)所需A類資源:“; cin>>need_a; cout<<“本作業(yè)所需B類資源:“; cin>>need_b; cout<<“本作業(yè)所需C類資源:“; cin>>need_c; t=1; cout< if(need_a>banker.remain_a){ cout<<“錯(cuò)誤,所需A類資源大于銀行家所剩A類資源“< t=0; } if(need_b>banker.remain_b){ cout<<“錯(cuò)誤,所需B類資源大于銀行家所剩B類資源“< t=0; } if(need_c>banker.remain_c){ cout<<“錯(cuò)誤,所需C類資源大于銀行家所剩C類資源“< t=0; } if(t){ strcpy(processes[quantity].name,name); processes[quantity].need_a=need_a; processes[quantity].need_b=need_b; processes[quantity].need_c=need_c; quantity++; cout<<“新加作業(yè)成功“< } else{ cout<<“新加作業(yè)失敗“< } } } //為作業(yè)申請(qǐng)資源 void bid() { char name[20]; int i,p; int a,b,c; int flag; cout< cout<<“要申請(qǐng)資源的作業(yè)名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ cout<<“該作業(yè)要申請(qǐng)A類資源數(shù)量:“; cin>>a; cout<<“該作業(yè)要申請(qǐng)B類資源數(shù)量:“; cin>>b; cout<<“該作業(yè)要申請(qǐng)C類資源數(shù)量:“; cin>>c; flag=1; if((a>banker.remain_a)||(a>processes[p].need_a-processes[p].a)){ cout<<“錯(cuò)誤,所申請(qǐng)A類資源大于銀行家所剩A類資源或該進(jìn)程還需數(shù)量“< flag=0; } if((b>banker.remain_b)||(b>processes[p].need_b-processes[p].b)){ cout<<“錯(cuò)誤,所申請(qǐng)B類資源大于銀行家所剩B類資源或該進(jìn)程還需數(shù)量“< flag=0; } if((c>banker.remain_c)||(c>processes[p].need_c-processes[p].c)){ cout<<“錯(cuò)誤,所申請(qǐng)C類資源大于銀行家所剩C類資源或該進(jìn)程還需數(shù)量“< flag=0; } if(flag){ banker.remain_a-=a; banker.remain_b-=b; banker.remain_c-=c; processes[p].a+=a; processes[p].b+=b; processes[p].c+=c; cout<<“為作業(yè)申請(qǐng)資源成功“< } else{ cout<<“為作業(yè)申請(qǐng)資源失敗“< } } else{ cout<<“該作業(yè)不存在“< } } //撤消作業(yè) void finished() { char name[20]; int i,p; cout< cout<<“要撤消作業(yè)名:“; cin>>name; p=-1; for(i=0;i if(!strcmp(processes[i].name,name)){ p=i; break; } } if(p!=-1){ banker.remain_a+=processes[p].a; banker.remain_b+=processes[p].b; banker.remain_c+=processes[p].c; for(i=p;i processes[i]=processes[i+1]; } strcpy(processes[quantity-1].name,““); processes[quantity-1].a=0; processes[quantity-1].b=0; processes[quantity-1].c=0; processes[quantity-1].need_a=0; processes[quantity-1].need_b=0; processes[quantity-1].need_c=0; quantity--; cout<<“撤消作業(yè)成功“< } else{ cout<<“撤消作業(yè)失敗“< } } //查看資源情況 void view() { int i; cout< cout<<“銀行家所剩資源(剩余資源/總共資源)“< cout<<“A類:“< cout<<“ B類:“< cout<<“ C類:“< cout< if(quantity>0){ for(i=0;i cout<<“作業(yè)名:“< cout<<“A類:“< cout<<“ B類:“< cout<<“ C類:“< cout< } } else{ cout<<“當(dāng)前沒有作業(yè)“< } } //顯示版權(quán)信息函數(shù) void version() { cout< cout<<“ 銀行家算法 “< cout< } void main() { int chioce; int flag=1; initial(); version(); while(flag){ cout<<“1.新加作業(yè) 2.為作業(yè)申請(qǐng)資源 3.撤消作業(yè)“< cout<<“4.查看資源情況 0.退出系統(tǒng)“< cout<<“請(qǐng)選擇:“; cin>>chioce; switch(chioce){ case 1: add(); break; case 2: bid(); break; case 3: finished(); break; case 4: view(); break; case 0: flag=0; break; default: cout<<“選擇錯(cuò)誤“< } } } 六、使用說明 運(yùn)行環(huán)境C-FREE4.0，新建任務(wù)。將編制好的代碼輸入此運(yùn)行環(huán)境中。 按F5：出現(xiàn)如上圖所示窗口。按照提示，新建一個(gè)作業(yè)：wujun。為作業(yè)分配資源，A：3；B：4；C：5。輸入2，為作業(yè)分配資源。三種資源的數(shù)量分配分別為:A:3;B:5;C:4。輸入4，查看資源情況。出現(xiàn)出錯(cuò)提示，所申請(qǐng)的B類資源超過銀行家所剩B類資源或作業(yè)申請(qǐng)資源失敗。輸入0，退出系統(tǒng)。 重新加入一個(gè)作業(yè)：wujun1.并為作業(yè)分配資源分別為A:3;B:3;C:3，為該作業(yè)分配資源A:3;B:2;C:2.輸入4查看資源情況。 顯示輸出，銀行家算法所剩資源（剩余資源、總共資源）。 七、實(shí)驗(yàn)心得 八、參考文獻(xiàn) 湯子瀛等.計(jì)算機(jī)操作系統(tǒng).西安電子科技大學(xué)出版社.2001年5月 蔣靜 徐志偉.操作系統(tǒng)原理?技術(shù)與編程『M』.北京:機(jī)械工業(yè)出版社,2004 《計(jì)算機(jī)操作系統(tǒng)》 課 程 設(shè) 計(jì) 報(bào) 告 題 目： 銀行家算法 班 級(jí)： XXXXXXXXXXXXXXXX 姓 名： XXM 學(xué) 號(hào)： XXXXXXXXXXXX 指導(dǎo)老師: XXXXXXXXXXXXXX 設(shè)計(jì)時(shí)間: XXXXXXXXXXXXXXX 一.設(shè)計(jì)目的 1、掌握死鎖概念、死鎖發(fā)生的原因、死鎖產(chǎn)生的必要條件; 2、掌握死鎖的預(yù)防、死鎖的避免; 3、深刻理解死鎖的避免：安全狀態(tài)和銀行家算法; 二.銀行家算法 1.簡(jiǎn)介 銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實(shí)現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。 2.數(shù)據(jù)結(jié)構(gòu) 1）可利用資源向量Available 是個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。2）最大需求矩陣Max 這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。3）分配矩陣Allocation 這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。4）需求矩陣Need 這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。Need[i,j]=Max[i,j]-Allocation[i,j].3.算法原理 操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程本次申請(qǐng)的資源數(shù)是否超過了該資源所剩余的總量。若超過則拒絕分配資源，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。 三.算法實(shí)現(xiàn) 1.初始化 由用戶輸入數(shù)據(jù)，分別對(duì)可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED賦值。 2.銀行家算法 在避免死鎖的方法中，所施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖。 銀行家算法的基本思想是分配資源之前，判斷系統(tǒng)是否是安全的；若是，才分配。設(shè)進(jìn)程cusneed提出請(qǐng)求REQUEST [i]，則銀行家算法按如下規(guī)則進(jìn)行判斷。(1)如果REQUEST [cusneed] [i]<= NEED[cusneed][i]，則轉(zhuǎn)（2)；否則，出錯(cuò)。(2)如果REQUEST [cusneed] [i]<= AVAILABLE[cusneed][i]，則轉(zhuǎn)（3)；否則，出錯(cuò)。(3)系統(tǒng)試探分配資源，修改相關(guān)數(shù)據(jù)： AVAILABLE[i]-=REQUEST[cusneed][i];ALLOCATION[cusneed][i]+=REQUEST[cusneed][i];NEED[cusneed][i]-=REQUEST[cusneed][i];(4)系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探險(xiǎn)性分配作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程等待。 3.安全性檢查算法 (1)設(shè)置兩個(gè)工作向量Work=AVAILABLE;FINISH(2)從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程，F(xiàn)INISH==false;NEED<=Work;如找到，執(zhí)行（3)；否則，執(zhí)行（4)(3)設(shè)進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work+=ALLOCATION;Finish=true;GOTO 2(4)如所有的進(jìn)程Finish= true，則表示安全；否則系統(tǒng)不安全。 4.算法流程圖 1)初始化算法流程圖 2)銀行家算法流程圖： 3)安全性算法流程圖： 4.代碼（C語言） #include /*M個(gè)進(jìn)程對(duì)N類資源最大資源需求量*/ int MAX[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}};/*系統(tǒng)可用資源數(shù)*/ int AVAILABLE[N]={10,5,7};/*M個(gè)進(jìn)程對(duì)N類資源最大資源需求量*/ int ALLOCATION[M][N]={{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}; /*M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量 */ int NEED[M][N]={{7,5,3},{3,2,2},{9,0,2},{2,2,2},{4,3,3}}; /*M個(gè)進(jìn)程還需要N類資源的資源量*/ int Request[N]={0,0,0}; void main(){ int i=0,j=0;char flag; void showdata();void changdata(int);void rstordata(int);int chkerr(int);showdata();enter:{ printf(“請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)（從0到”); printf(“%d”,M-1); printf(“）:”); scanf(“%d”,&i);} if(i<0||i>=M){ printf(“輸入的進(jìn)程號(hào)不存在，重新輸入!n”); goto enter;} err:{ printf(“請(qǐng)輸入進(jìn)程”); printf(“%d”,i); printf(“申請(qǐng)的資源數(shù)n”); printf(“類別: A B Cn”);printf(“ ”); for(j=0;j { scanf(“%d”,&Request[j]); if(Request[j]>NEED[i][j]) { printf(“%d”,i); printf(“號(hào)進(jìn)程”); printf(“申請(qǐng)的資源數(shù) > 進(jìn)程”); printf(“%d”,i); printf(“還需要”); printf(“%d”,j);printf(“類資源的資源量!申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇!n”); goto err; } else { if(Request[j]>AVAILABLE[j]) { printf(“進(jìn)程 ”); printf(“%d”,i); printf(“申請(qǐng)的資源數(shù)大于系統(tǒng)可用”); printf(“%d”,j); printf(“類資源的資源量!申請(qǐng)不合理，出錯(cuò)!請(qǐng)重新選擇!n”); goto err; } } } } changdata(i);if(chkerr(i)){ rstordata(i); showdata();} else showdata(); printf(“n”); printf(“按'y'或'Y'鍵繼續(xù),否則退出n”); flag=getch(); if(flag=='y'||flag=='Y'){ goto enter; } else { exit(0);} } /*顯示數(shù)組*/ void showdata(){ int i,j;printf(“系統(tǒng)可用資源向量:n”);printf(“***Available***n”);printf(“資源類別: A B Cn”);printf(“資源數(shù)目:”);for(j=0;j printf(“%d ”,AVAILABLE[j]);} printf(“n”);printf(“n”);printf(“各進(jìn)程還需要的資源量:n”);printf(“******Need******n”);printf(“資源類別: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“號(hào)進(jìn)程:”); for(j=0;j { printf(“ %d ”,NEED[i][j]); } printf(“n”);} printf(“n”);printf(“各進(jìn)程已經(jīng)得到的資源量: n”);printf(“***Allocation***n”);printf(“資源類別: A B Cn”);for(i=0;i printf(“ ”); printf(“%d”,i); printf(“號(hào)進(jìn)程:”); /*printf(“:n”);*/ for(j=0;j { printf(“ %d ”,ALLOCATION[i][j]); } printf(“n”); } printf(“n”);} /*系統(tǒng)對(duì)進(jìn)程請(qǐng)求響應(yīng)，資源向量改變*/ void changdata(int k){ int j; for(j=0;j AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j];} } /*資源向量改變*/ void rstordata(int k) { int j; for(j=0;j AVAILABLE[j]=AVAILABLE[j]+Request [j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; } } /*安全性檢查函數(shù)*/ int chkerr(int s){ int WORK,FINISH[M],temp[M];int i,j,k=0; for(i=0;i WORK=AVAILABLE[j]; i=s; printf(“n”); while(i { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { printf(“系統(tǒng)不安全!本次資源申請(qǐng)不成功!n”); printf(“n”); return 1; } } } WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; temp[k]=i;k++;i=0; printf(“n”); printf(“經(jīng)安全性檢查，系統(tǒng)安全，本printf(”n“); printf(” 本次安全序列：n“);printf(”進(jìn)程依次為“);for(i=0;i printf(”%d“,temp[i]); 次分配成功。n”);} else { i++;} } for(i=0;i printf(“-> ”);} printf(“n”);return 0;四．程序運(yùn)行截圖 0號(hào)進(jìn)程申請(qǐng)資源{1,2,3},各向量發(fā)生變化 0和進(jìn)程繼續(xù)申請(qǐng)資源{2,2,0}，各向量變化 2號(hào)進(jìn)程申請(qǐng)資源，由于NEED[2]={9,0,2},前兩次申請(qǐng)不合理，系統(tǒng)處于不安全狀態(tài)太。第三次2號(hào)申請(qǐng)資源向量為{1,0,2}，系統(tǒng)回到安全狀態(tài)，并得出新的安全序列3-0-1-2-4。 五．心得體會(huì) 從此次的課程設(shè)計(jì)中，我收獲很多。首先也是最重要的一點(diǎn)是對(duì)處理機(jī)調(diào)度與死鎖有了深入的理解；其次，再次鞏固了C語言編程。 在用C語言設(shè)計(jì)和編寫銀行家算法和安全性檢查算法時(shí)遇到了一些困難都克服了。在使程序界面美觀、能夠持續(xù)循環(huán)運(yùn)行時(shí)用了很多方法，花了比較多的時(shí)間。最后選擇用goto語句控制，我覺得在此實(shí)驗(yàn)中比較好，代碼閱讀起來更加方便。第二篇：操作系統(tǒng)課程設(shè)計(jì)-磁盤調(diào)度算法
第三篇：操作系統(tǒng)課程設(shè)計(jì),磁盤調(diào)度算法范文
第四篇：銀行家算法《操作系統(tǒng)》課程設(shè)計(jì)報(bào)告
第五篇：計(jì)算機(jī)操作系統(tǒng) 課程設(shè)計(jì)報(bào)告 銀行家算法
點(diǎn)擊咨詢 