第一篇：操作系統(tǒng)課程設(shè)計之請求式面頁管理
一、目的與要求
1、目的
近年來，由于大規(guī)模集成電路（LSI）和超大規(guī)模集成電路（VLSI）技術(shù)的發(fā)展，使存儲器的容量不斷擴大，價格大幅度下降。但從使用角度看，存儲器的容量和成本總受到一定的限制。所以，提高存儲器的效率始終是操作系統(tǒng)研究的重要課題之一。虛擬存儲技術(shù)是用來擴大內(nèi)存容量的一種重要方法。學(xué)生應(yīng)獨立地用高級語言編寫幾個常用的存儲分配算法，并設(shè)計一個存儲管理的模擬程序，對各種算法進行分析比較，評測其性能優(yōu)劣，從而加深對這些算法的了解。
任務(wù)三采用最佳淘汰算法(OPT)實現(xiàn)，任務(wù)四采用最近最少使用頁淘汰算法(LRU)實現(xiàn)。
2、要求
為了比較真實地模擬存儲管理，可預(yù)先生成一個大致符合實際情況的指令地址流。然后模擬這樣一種指令序列的執(zhí)行來計算和分析各種算法的訪問命中率。
二、示例
1、題目 本示例是采用頁式分配存儲管理方案，并通過分析計算不同頁面淘汰算法情況下的訪問命中率來比較各種算法的優(yōu)劣。另外也考慮到改變頁面大小和實際存儲器容量對計算結(jié)果的影響，從而可為算則好的算法、合適的頁面尺寸和實存容量提供依據(jù)。
本程序是按下述原則生成指令序列的：（1）50%的指令是順序執(zhí)行的。
（2）25%的指令均勻散布在前地址部分。（3）25%的指令均勻散布在后地址部分。
示例中選用最佳淘汰算法（OPT）和最近最少使用頁面淘汰算法（LRU）計算頁面命中率。公式為
命中率?1?頁面失效次數(shù)
頁地址流長度假定虛存容量為32K，頁面尺寸從1K至8K，實存容量從4頁至32頁。
2、算法與框圖
（1）最佳淘汰算法(OPT)。這是一種理想的算法，可用來作為衡量其他算法優(yōu)劣的依據(jù)，在實際系統(tǒng)中是難以實現(xiàn)的，因為它必須先知道指令的全部地址流。由于本示例中已預(yù)先生成了全部的指令地址流，故可計算出最佳命中率。
該算法的準(zhǔn)則是淘汰已滿頁表中不再訪問或是最遲訪問的的頁。這就要求將頁表中的頁逐個與后繼指令訪問的所有頁比較，如后繼指令不在訪問該頁，則把此頁淘汰，不然得找出后繼指令中最遲訪問的頁面淘汰?？梢娮罴烟蕴惴ㄒㄙM較長的運算時間。（2）最近最少使用頁淘汰算法(LRU)。這是一種經(jīng)常使用的方法，有各種不同的實施方案，這里采用的是不斷調(diào)整頁表鏈的方法，即總是淘汰頁表鏈鏈?zhǔn)椎捻?，而把新訪問的頁插入鏈尾。如果當(dāng)前調(diào)用頁已在頁表內(nèi)，則把它再次調(diào)整到鏈尾。這樣就能保證最近使用的頁，總是處于靠近鏈尾部分，而不常使用的頁就移到鏈?zhǔn)?，逐個被淘汰，在頁表較大時，調(diào)整頁表鏈的代價也是不小的。（3）程序框圖如下圖2所示。
產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)size=1assigned=4產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)AlgAlg=OPT/LRU產(chǎn)OPTLRU產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn)產(chǎn) 圖2 計算頁面命中率框圖
3、程序運行結(jié)果格式(1)程序運行結(jié)果格式
THE VIRTUAL ADDRESS STREAM AS FOLLOWS: a[0] =16895
a[1]=16896
a[2]=16897
a[3]=16302 a[4]=25403
a[5]=13941
a[6]=13942
a[7]=8767 ?? ?? ??
A[252]=23583
a[253]=20265
a[254]=20266
a[255]=20267 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = The algorithm is:opt PAGE NUMBER WITH SIZE 1k FOR EACH ADDRESS IS: pageno[0]=17 pageno[1]=17
pageno[2]=17
pageno[3]=16 pageno[4]=25
pageno[5]=14
pageno[6]=14
pageno[7]=9 ?? ?? ??
pageno[252]=24
pageno[253]=20
pageno[254]=20
pageno[255]=20
vmsize=32k
pagesize=1k---------------------------page assigned
pages_in/total references 4
7.***E-1 6
7.***E-1 8
8.***E-1 10
8.***E-1 12
8.***E-1 14
9.***E-1 16
9.***E-1 18
9.***E-1 20
9.***E-1 22
9.***E-1 24
9.***E-1 26
9.***E-1 28
9.***E-1 30
9.***E-1 32
9.***E-1 PAGE NUMBER WITH SIZE 2k EACH ADDRESS IS: ?? ?? ??
PAGE NUMBER WITH SIZE 4k EACH ADDRESS IS: ?? ?? ??
PAGE NUMBER WITH SIZE 8k EACH ADDRESS IS: ?? ?? ??
End the result for opt ** ********************************************** the algorithm is lru ?? ?? ??同上
End the result for lru *********************************************(2)示例中使用的有關(guān)數(shù)據(jù)結(jié)構(gòu)、常量和變量說明如下： length 被調(diào)試的指令地址流長度，可作為一個常量設(shè)定。called當(dāng)前請求的頁面號。
pagefault頁面失效標(biāo)志，如當(dāng)前請求頁called已在頁表內(nèi)，則置pagefault=false，否則為true。
table 頁表。table[i]=j,表示虛存的第j頁在實存的第i頁中。
used當(dāng)前被占用的實存頁面數(shù)，可用來判斷當(dāng)前實存中是否有空閑頁。（3）本程序啟動后，屏幕上顯示“the algorithm is：”，用戶可選擇最佳淘汰算法（打入“OPT”）或者最近最少使用淘汰算法(打入“LRU”)計算頁面命中率。當(dāng)然還可以加入各種其他的算法。
三、實習(xí)題
（1）編制和調(diào)試示例給出的請求頁式存儲管理程序，并使其投入運行。（2）增加1～2種已學(xué)過的淘汰算法，計算它們的頁面訪問命中率。試用各種算法的命中率加以比較分析。
提示：可選用FIFO方法，即先訪問的頁先淘汰，也可選用LRU方法中的其他方案。如在頁表中設(shè)置標(biāo)志位，按標(biāo)志位值得變化來淘汰。也可用LFU方法，為頁表中各頁面設(shè)置訪問計數(shù)器，淘汰訪問頻率最低的頁（注意：當(dāng)前訪問的頁不能淘汰）等等。
實驗步驟與源程序 #include “iostream” #include “stdio.h” #include “stdlib.h” using namespace std;#define Max 30 //某進程調(diào)入內(nèi)存中的最大頁面數(shù) #define Size 10 //系統(tǒng)為某進程分配的最大物理塊數(shù) void Init(int Block[],int m)//初始化物理塊 { int i;for(i=0;i Block[i]=-1;} } void creat(int Page[],int n)//輸入頁面串引用號 { int i;for(i=0;i cin>>Page[i];} } void Init1(int Block1[],int m1){ int i;for(i=0;i Block1[i]=-1;} } void creat1(int Page[],int n1){ int i;for(i=0;i Page[i];} } void LRU(int Page[],int Block1[],int n1,int m1){ int i,j,max_stay=0,count=0;int get=-1,flag=-1,block_num=-1;int time[Size];for(i=0;i time[i]=0;} for(i=0;i { if(Block1[j]==-1) { get=j;//物理塊j即將(/等待)駐入新頁面 break; } } for(j=0;j { if(Block1[j]==Page[i])//物理塊j中頁面與當(dāng)前期望調(diào)入內(nèi)存的頁面相同 { time[j]=0; flag=j; break; } } for(j=0;j { if(time[j]>max_stay) { max_stay=time[j]; block_num=j;//block_num標(biāo)記當(dāng)前序號物理塊中頁面駐留時間最久 } } if(flag==-1)//不存在相同頁面 { if(get!=-1)//物理塊即將(/等待)駐入新頁面 { Block1[get]=Page[i];//存入頁面 time[get]=0;//當(dāng)前物理塊重新計時 for(j=0;j<=get;j++)//已駐入頁面的駐留時間加1 { time[j]++; } get=-1; } else //頁面調(diào)度置換，序號block_num的物理塊是駐留時間最久的 { Block1[block_num]=Page[i]; time[block_num]=0; for(j=0;j { time[j]++; } block_num=-1; max_stay=0; count++; } } else //待調(diào)入頁面與序號flag的物理塊中頁面相同 { for(j=0;j { time[j]++; } flag=-1; } for(j=0;j { cout<<“ ”< } cout< } if(n1>m1) count=count+m1;cout<<“缺頁中斷次數(shù)為:”< { time[i]=0;} for(i=0;i { if(Block[j]==-1) { get=j; break; } } for(j=0;j { if(Block[j]==Page[i]) { flag=j; break; } } for(j=0;j { if(time[j]>max_stay) { max_stay=time[j]; block_num=j; } } if(flag==-1) { if(get!=-1) { Block[get]=Page[i]; time[get]=0; for(j=0;j<=get;j++) { time[j]++; } get=-1; } else { Block[block_num]=Page[i]; time[block_num]=0; for(j=0;j { time[j]++; } block_num=-1; max_stay=0; count++; } } else { for(j=0;j { time[j]++; } flag=-1; } for(j=0;j { cout<<“ ”< } cout< count=count+m;cout<<“缺頁中斷次數(shù)為:”< switch(t){ case '1':LRU(Page,Block1,n1,m1); continue;case '2':FIFO(Page,Block,n,m); continue;case '3':exit(0);} } } 測試數(shù)據(jù)與實驗結(jié)果 圖1 輸入要分配的物理塊數(shù)、頁面總數(shù)、頁面序列號 圖2 LRU算法的實現(xiàn) 圖3 FIFO算法的實現(xiàn) 4、小結(jié) (1)編制評測各種算法性能的模擬程序是研制系統(tǒng)程序，尤其是操作系統(tǒng)所必須的。模擬的環(huán)境愈是真實，其結(jié)果愈是可靠，也就更有利于選擇合適的方案。本實習(xí)雖屬簡單，但可作為一個嘗試。 (2)注意正整數(shù)的范圍只能從0??32767，限制程序中的虛存尺寸為32K，實際如采用更大的虛存實存，更能說明問題。 頁面置換算法理解比較容易，這次根據(jù)學(xué)號要求實現(xiàn)的是LRU和FIFO算法的實現(xiàn)。 其實這兩種算法的程序編寫比較容易，雖然不全是自己編寫的，一部分是參考的網(wǎng)上的例題，但是通過對每一語句的理解，自己弄懂了整個程序的執(zhí)行原理。但是，在編寫過程中自己還是遇到了一些問題。 最大的一個問題就是兩個算法的正確實現(xiàn)，在程序的編寫時，兩個程序是分開進行編寫的，分別執(zhí)行起來沒有什么問題，但是把兩個程序融合在一起后，卻出現(xiàn)了問題，即在執(zhí)行完成一個算法后再執(zhí)行另外一個算法時，開始的數(shù)據(jù)是緊接著上次算法結(jié)果的數(shù)據(jù)進行實驗的。這個問題困擾了我好長時間，直到現(xiàn)在還沒有很好的解決掉，程序只能分別執(zhí)行一次，如果再進行執(zhí)行的話，就會出現(xiàn)問題。 自己的編程技術(shù)不好，程序編的也很繁瑣，但是基本的要求已經(jīng)實現(xiàn)了，希望這次的實驗是自己動手的一個開始，自己應(yīng)該更加努力，再接再厲。 四、思考題 （1）設(shè)計一個界地址存儲管理的模擬系統(tǒng)，模擬界地址方式下存儲區(qū)的分配和回收過程。 提示：必須設(shè)置一個內(nèi)存分配表，按照分配表中有關(guān)信息實施存儲區(qū)的分配，并不斷根據(jù)存儲區(qū)的分配和回收修改該表。算法有首次匹配法，循環(huán)首次匹配法和最佳匹配法等?？捎酶鞣N方法的比較來充實實習(xí)內(nèi)容。可使用碎片收集和復(fù)蓋等技術(shù)。對分區(qū)的管理法可以是下面三種算法之一： 首次適應(yīng)算法 循環(huán)首次適應(yīng)算法 最佳適應(yīng)算法 #include /*修改已分配區(qū)表*/ i=0;while(used_table[i].flag!=0&&i }/*主存分配函數(shù)結(jié)束*/ void reclaim(char J)/*回收作業(yè)名為J的作業(yè)所占主存空間*/ { int i,k,j,s,t;float S,L;/*尋找已分配表中對應(yīng)登記項*/ s=0;while((used_table[s].flag!=J||used_table[s].flag==0)&&s for(i=1;i （2）自行設(shè)計或選用一種較為完善的內(nèi)存管理方法，并加以實現(xiàn)。提示：設(shè)計一個段頁式管理的模擬程序或通過一個實際系統(tǒng)的消化和分析，編制一個程序來模擬該系統(tǒng)。#include struct program { char name[30];long start;long length;struct program *next;}; struct space { long start;long length;struct space *next;}; void creat();void allot();void back();void callback(program *r);void sort(space *L);void sort(program *S);void display(space *L);void display(program *S); space *L;program *S; void creat(){ L=new space;space *p=new space;p->start=0;p->length=128;p->next=NULL;L->next=p;S=new program;S->next=NULL;} void allot(){ program *q;q=new program;cout<<“請輸入進程名和占用空間大小:”< p->next->length-=q->length;if(p->next->length!=0)p->next->start+=q->length;else { if(p->next->next!=NULL)p->next=p->next->next;else { r->next=NULL;delete p->next;} } } display(L);display(S);} void back(){ char name[30];cout<<“輸入要回收的進程名：”;cin>>name;program *p;p=S;while(p->next!=NULL){ if(strcmp(p->next->name, name)==0){ callback(p);return;} p=p->next;} if(p->next==NULL)cout<<“此進程不存在,內(nèi)存回收失敗”< { q->next=p->next;q->length=q->length+p->length+n;t->next=r->next;delete r;} else if(r->start+n==p->start)//下鄰空 { p->start-=n;p->length+=n;t->next=r->next;delete r;} else if(q->start+q->length==r->start){ q->length+=n;t->next=r->next;delete r;} else { space *sp=new space;sp->start=r->start;sp->length=n;sp->next=L->next;L->next=sp;t->next=r->next;delete r;} cout<<“此進程內(nèi)存回收完畢.”< length< length< { space *p=L->next, *q, *r;if(p!=NULL){ r=p->next;p->next=NULL;p=r;while(p!=NULL){ r=p->next;q=L;while(q->next!=NULL&&q->next->start start)q=q->next;p->next=q->next;q->next=p;p=r;} } } void sort(program *S)//鏈表排序 { program *p=S->next, *q, *r;if(p!=NULL){ r=p->next;p->next=NULL;p=r;while(p!=NULL){ r=p->next;q=S; 起始地址:“< start<<” 長 while(q->next!=NULL&&q->next->start start)q=q->next;p->next=q->next;q->next=p;p=r;} } } void main(){ creat();int a;cout<<“ 內(nèi)存分配與回收模擬”< #include “stdio.h” #include “string.h” #include “malloc.h” #include “stdlib.h” #define MAX 1000 struct file/*普通文件的結(jié)構(gòu)體*/ { //int type;//0無作用，當(dāng)做一個空節(jié)點存在；1為記錄型文件；2為執(zhí)行文件 //前兩個變量為文件的權(quán)限設(shè)置，1為允許操作，0為不允許操作 int write;//可寫 int read;//可讀 int length;//文件的長度 char ch[MAX];};typedef struct file File; typedef struct ffile/*定義文件類型的結(jié)構(gòu)體*/ { int type;//1為文件夾； 2為文件； char name[20];//文件(夾)名字 int open;//文件打開標(biāo)志，0為關(guān)，1為開 File iffile;//如果為文件時有的信息 struct ffile *parent;//指向上一級文件的指針 struct ffile *brother;//指向同級兄弟文件(夾)的指針 struct ffile *child;//指向下一級文件(夾)的指針 }Ffile;typedef Ffile *FFile; /*typedef struct Open/*記錄打開文件的結(jié)構(gòu)體 { char name[20];//記錄打開文件(夾)的名字 FFile* add;//記錄打開文件上一級文件地址的指針 }Open;*/ //全局變量 FFile user1;//用戶1 FFile user2;//用戶2 FFile copyf;//記錄被復(fù)制文件(夾)的上一級文件地址 //Open openf[20];//記錄打開文件的隊列 FFile init(void)/*初始化，創(chuàng)建根結(jié)點*/ { FFile c;c=(Ffile*)malloc(sizeof(Ffile)); c->type=2;c->open=0;//c->iffile.type=2;c->iffile.write=1;c->iffile.read=1;c->iffile.length=0;strcpy(c->name,“file1”);c->parent=NULL;c->child=NULL;c->brother=NULL;strcpy(c->iffile.ch,“NULL”);return(c);} /*void initopen(){ int a,b;a=20;for(b=1;b<=a;b++){ openf[b].add=NULL;} }*/ //傳遞要顯示文件的parent的地址 void show(FFile user)/*顯示當(dāng)前界面存在的文件*/ { user=user->child;if(user==NULL){ printf(“該文件內(nèi)沒有任何文件(夾)。n”);return;} printf(“n”);for(;user!=NULL;){ printf(“<%s”,user->name);if(user->type==2){ /*if(user->iffile.type==1) printf(“/記錄型文件/”); else printf(“/執(zhí)行文件/”);*/ printf(“/%dk”,user->iffile.length);} else { printf(“/文件夾”); } printf(“>n”); user=user->brother;} } void creatf(FFile user)/*創(chuàng)建文件 || 文件夾*/ { FFile parent;char ch[20];//FFile user0;//parent=(Ffile*)malloc(sizeof(Ffile));parent=user;printf(“輸入要創(chuàng)建文件(夾)的名字：n”); scanf(“%s”,ch);if(user->child==NULL){ user->child=(Ffile*)malloc(sizeof(Ffile)); user=user->child;}else { user=user->child; for(;;) { if(user->type==0)//開端的空結(jié)點，用新結(jié)點覆蓋 break; if(!strcmp(user->name,ch)) { printf(“錯誤：該文件名已經(jīng)存在，文件(夾)創(chuàng)建失??！n”); return; } if(user->brother==NULL) { user->brother=(Ffile*)malloc(sizeof(Ffile)); user=user->brother; break; } user=user->brother; } } } //設(shè)置新文件(夾)的信息 strcpy(user->name,ch);printf(“選擇創(chuàng)建對象：1文件夾； 2文件；n”);scanf(“%d”,&user->type);user->open=0;if(user->type==2)//添加文件信息 { //printf(“選擇文件類型：1記錄型文件；2執(zhí)行文件；n”);//scanf(“%d”,&user->iffile.type);printf(“能否對文件進行讀:0禁止；1允許；n”);scanf(“%d”,&user->iffile.read);printf(“能否對文件進行寫:0禁止；1允許；n”);scanf(“%d”,&user->iffile.write);//printf(“設(shè)置文件大小(單位：K):n”);//scanf(“%d”,&user->iffile.length);user->iffile.length=0;strcpy(user->iffile.ch,“NULL”);} user->brother=NULL;user->child=NULL;user->parent=parent;printf(“文件創(chuàng)建成功！n”);void deletechildtree(FFile user)/*刪除子樹--結(jié)合deletefile();使用*/ { if(user->brother!=NULL)//從下到上，從右到左刪除 { deletechildtree(user->brother);} if(user->child!=NULL){ deletechildtree(user->child);} if(user!=NULL){ free(user);} } void deletefile(FFile user,char ch[20])/*刪除文件 || 文件夾*/ { FFile p,parent; int a;parent=user;if(user->child==NULL){ printf(“錯誤：刪除失敗，該目錄下沒有可刪除的文件(夾)!n”);return;} user=user->child;p=user;for(a=1;;a++)//找出要刪除文件的所在位置 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：刪除失敗，當(dāng)前位置沒有該文件！n”); return;} if(a>1) p=user;user=user->brother;} if(user->open==1)//判斷文件的開關(guān)情況 { } printf(“錯誤：刪除失敗，選擇文件處于打開狀態(tài)！n”);return;if(p==user)//被刪文件在文件隊列的開頭 { if(user->brother==NULL)//該文件隊列只有有一個文件 { parent->child=NULL; if(user->child!=NULL)//刪除的是文件(夾)子樹 { deletechildtree(user);}else { free(user);//刪除的是文件(夾)結(jié)點 } printf(“刪除成功！n”);return;} //文件隊列有多個文件 p=user->brother; } parent->child=p;p->parent=parent;if(user->child!=NULL){ deletechildtree(user);}else { free(user);} printf(“刪除成功！n”);return;else//被刪文件不在隊列開頭 { if(user->brother==NULL)//被刪文件在文件隊列最末尾 { p->brother=NULL;if(user->child!=NULL){ deletechildtree(user);}else { free(user);} } printf(“刪除成功！n”);return; //被刪文件在文件隊列中間 p->brother=user->brother; if(user->child!=NULL) { deletechildtree(user); } else { free(user); } } printf(“刪除成功！n”);} FFile openfolder(FFile user)/*打開文件夾*/ { } //int a,b;//a=0;/*if(user->child==NULL){ user->child=(Ffile*)malloc(sizeof(Ffile));user->child->type=0;user->child->brother=NULL;user->child->parent=user;user->child->child=NULL; } /*for(b=1;b<=20;b++){ if(openf[b].add!=NULL) a++;} if(a==20){ printf(“錯誤：打開列表溢出！”);return(user);} for(b=1;;b++){ if(openf[b].add==NULL) break;}*/ user->open=1;//設(shè)置文件為打開 //strcpy(openf[b].name,user->name);//openf[b].add=user;printf(“文件夾打開成功。n”);return(user);//返回被打開的文件夾的地址 void openfile(FFile user)/*打開普通文件*/ { if(user->open==1){ printf(“錯誤：打開失敗，此文件已經(jīng)被打開！n”); return;} user->open=1;printf(“普通文件打開成功！n”);} FFile openff(FFile user)/*打開文件(夾)*/ { char ch[20];FFile parent; int a;printf(“選擇要打開的文件名:n”);scanf(“%s”,ch); parent=user;if(user->child==NULL){ printf(“錯誤：打開失敗，該目錄下沒有可打開的文件(夾)!n”);return(parent);} user=user->child;for(a=1;;a++)//找出要打開文件的所在位置 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：打開失敗，當(dāng)前位置沒有該文件！n”); return(parent);} user=user->brother;} if(user->type==1){ printf(“開始打開文件夾。。n”);user=openfolder(user);} else if(user->type==2){ printf(“開始打開普通文件。。n”); openfile(user); user=user->parent;} return(user);} void closefile(FFile user)/*關(guān)閉普通文件*/ { char ch[20];int a;printf(“選擇要打開的文件名:n”);scanf(“%s”,ch);if(user->child==NULL){ printf(“錯誤：關(guān)閉失敗，該目錄下沒有可關(guān)閉的文件!n”);return;} user=user->child;for(a=1;;a++)//找出要關(guān)閉文件的所在位置 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：關(guān)閉失敗，當(dāng)前位置沒有該文件！n”); return;} user=user->brother;} if(user->open==0){ printf(“錯誤：關(guān)閉失敗，該文件已經(jīng)是關(guān)閉狀態(tài)！n”); return;} user->open=0;printf(“文件已經(jīng)成功關(guān)閉！”);} /*沒有文件夾關(guān)閉原因： 文件夾一打開就會跳向打開的新文件里 而文件夾關(guān)閉就會直接返回上一級的目錄，若想整個文件夾都關(guān)閉，直接退出就可以了 因此不會直接關(guān)閉某個特定的文件*/ FFile backf(FFile user)/*返回上一層目錄*/ { if(user->parent==NULL){ printf(“錯誤：返回失敗，此處是最頂層目錄！n”); return(user);} } user->open=0;user=user->parent;return(user);void readfile(FFile user)/*讀文件*/ { char ch[20];int a; printf(“選擇要讀取的文件名:n”);scanf(“%s”,ch);if(user->child==NULL){ printf(“錯誤：讀取失敗，該目錄下沒有可讀取的文件!n”);return;} user=user->child;for(a=1;;a++)//找出要讀取文件的所在位置 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：讀取失敗，當(dāng)前位置沒有該文件！n”); return;} user=user->brother;} if(user->open==0){ printf(“錯誤：文件讀取失敗，該文件處于關(guān)閉狀態(tài)！n”);return;} else if(user->iffile.read==0){ printf(“錯誤：文件讀取失敗，該文件受保護，禁止讀取！n”);return;} printf(“讀操作，該文件中的內(nèi)容:n”);if(!strcmp(user->iffile.ch,“NULL”)){ printf(“該文件內(nèi)沒有可讀內(nèi)容！n”);return; } } printf(“%sn”,user->iffile.ch);printf(“文件讀取成功！n”);void writefile(FFile user)/*寫文件*/ { char ch[20];int a; } printf(“選擇要進行寫操作的文件名:n”);scanf(“%s”,ch);if(user->child==NULL){ printf(“錯誤：寫操作失敗，該目錄下沒有可寫的文件!n”);return;} user=user->child;for(a=1;;a++)//找出要讀取文件的所在位置 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：寫操作失敗，當(dāng)前位置沒有該文件！n”); return;} user=user->brother;} if(user->open==0){ printf(“錯誤：文件寫操作失敗，該文件處于關(guān)閉狀態(tài)！n”);return;} else if(user->iffile.write==0){ printf(“錯誤：文件寫操作失敗，該文件受保護，禁止寫！n”);return;} printf(“寫操作,輸入內(nèi)容：n”);scanf(“%s”,user->iffile.ch);user->iffile.length=strlen(user->iffile.ch);printf(“文件進行寫操作成功！n”); FFile copyfile(FFile user,FFile copyf)/*拷貝文件*/ { char ch[20];int a;printf(“選擇要進行拷貝的文件(夾)名:n”);scanf(“%s”,ch); if(user->child==NULL){ printf(“錯誤：拷貝失敗，該目錄下沒有可拷貝的文件!n”); return(NULL);} user=user->child;for(a=1;;a++)//找出要拷貝文件的所在位置，用user替代 { if(!strcmp(user->name,ch)) break; if(user->brother==NULL) { printf(“錯誤：拷貝失敗，當(dāng)前位置沒有該文件！n”); return(NULL); } user=user->brother;} copyf=user; } printf(“拷貝成功！n”);return(copyf);FFile fenpei(FFile copyf,FFile user,FFile parent)/*粘貼時，給已拷貝項分配內(nèi)存空間，以及給對應(yīng)信息賦值*/ { user=(Ffile*)malloc(sizeof(Ffile)); //parent對child的連接，以及brother之間的連接已經(jīng)完成if(copyf->brother==NULL && copyf->child==NULL){ user->parent=parent; user->child=NULL; user->brother=NULL;} else{ if(copyf->brother!=NULL){ user->brother=fenpei(copyf->brother,user->brother,parent);//brother連接,兄弟節(jié)點有同一個父結(jié)點 user->brother->parent=user->parent;} else { user->brother=NULL;} if(copyf->child!=NULL){ //parent=p;user->child=fenpei(copyf->child,user->child,user); user->child->parent=user;//完成child對parent的連接 //child連接，自己孩子的父結(jié)點就是自己 } else { user->child=NULL; user->child->parent=user;} } //設(shè)置結(jié)點對應(yīng)的信息 strcpy(user->name,copyf->name);user->open=copyf->open;user->type=copyf->type;if(user->type==2){ user->iffile.length=copyf->iffile.length; user->iffile.read=copyf->iffile.read; //user->iffile.type=copyf->iffile.type; user->iffile.write=copyf->iffile.write; strcpy(user->iffile.ch,copyf->iffile.ch);} return(user);} void prastefile(FFile user,FFile copyf)/*粘貼文件*/ //user是要粘貼的地方，copyf是要粘貼的內(nèi)容，//有相同文件名的會判斷會不會覆蓋，或者是重命名 //在原樹中進行新建操作 { int i,j;char ch[20];FFile p,user0,parent;parent=user;//記錄父結(jié)點 user=user->child; p=user;//記錄當(dāng)前結(jié)點的前一個brother結(jié)點 strcpy(ch,“NULL”);if(copyf==NULL)//判斷有沒有拷貝文件 { printf(“錯誤：粘貼失敗，還沒有拷貝任何文件(夾)！n”); return;} //p=(Ffile*)malloc(sizeof(Ffile));//p->child=(Ffile*)malloc(sizeof(Ffile));//先給粘貼項分配內(nèi)存空間 //p->child=fenpei(copyf,p->child,p); if(user==NULL)//當(dāng)前位置沒有任何文件結(jié)點 { } user=fenpei(copyf,user,parent);//是他自己要分配，不是孩子結(jié)點！!parent->child=user;user->brother=NULL;user->parent=parent;return;//該位置沒有任何文件 for(j=1;;j++){ if(user->type==0)//開端的空結(jié)點，用新結(jié)點覆蓋,即：當(dāng)前位置沒有文件結(jié)點 { user=user->parent; deletechildtree(p); user=fenpei(copyf,user->child,user);//返還增加的結(jié)點 user->brother=NULL; user->parent=parent; parent->child=user; } return;if(!strcmp(user->name,copyf->name)){ printf(“提示：該文件名已經(jīng)存在！n”); printf(“請重命名文件：n”); printf(“輸入新文件名：n”); scanf(“%s”,ch); } if(user->brother==NULL)//普通的退出條件 { break;} p=user;user=user->brother;} user->brother=fenpei(copyf,user->brother,user->parent);user->brother->parent=user->parent;//若要更名，粘貼分配完內(nèi)存空間返回時再改變 if(strcmp(ch,“NULL”)) strcpy(user->brother->name,ch);printf(“粘貼成功。n”);} void showroute(FFile user)/*顯示當(dāng)前路徑*/ { if(user->parent!=NULL){ showroute(user->parent);} printf(“%s/”,user->name);//路徑中每個結(jié)點的輸出項 } void change(FFile user){ char ch[20];int a,b; if(user->child==NULL) { } printf(“錯誤：屬性修改失敗，該目錄下沒有可修改的文件!n”);return;printf(“選擇要進行屬性修改的文件(夾)名:n”);scanf(“%s”,ch);user=user->child;for(a=1;;a++)//找出要拷貝文件的所在位置，用user替代 { if(!strcmp(user->name,ch)) break;if(user->brother==NULL){ printf(“錯誤：屬性修改失敗，當(dāng)前位置沒有該文件！n”); return;} user=user->brother;} if(user->type==1){ printf(“錯誤：文件夾不能進行屬性修改！n”);return;} for(;;){ printf(“1.修改讀權(quán)限；n”);printf(“2.修改寫權(quán)限；n”);printf(“3.返回；n”);printf(“選擇操作：n”);scanf(“%d”,&a);if(a==1){ printf(“0.禁止； 1.允許；n”);printf(“請選擇：n”);scanf(“%d”,&b);user->iffile.read=b;printf(“修改成功！n”);} else if(a==2){ printf(“0.禁止； 1.允許；n”);printf(“請選擇：n”);scanf(“%d”,&b);user->iffile.write=b; } } printf(“修改成功！n”);} else if(a==3){ return;} else { } printf(“錯誤：沒有該操作！n”);void main()/*主函數(shù)*/ { FFile d,e,f;//f記錄當(dāng)前顯示界面父結(jié)點位置 int a,b,c;char ch[20];a=0;printf(“******************************目錄******************************n”);printf(“ 1.選擇用戶n”);printf(“ 2.退出n”); printf(“****************************************************************n”);for(;;){ printf(“選擇操作：n”);scanf(“%d”,&a);if(a==1){ printf(“選擇用戶：n”);printf(“1.user1;n2.user2;n”);scanf(“%d”,&b);break;} else if(a==2){ printf(“歡迎使用。n”);exit(0);//系統(tǒng)退出的操作碼 } else { printf(“錯誤：沒有該操作！n”); } } //初始化打開列表 //initopen();//初始化各個用戶的信息 //copyf=(Ffile*)malloc(sizeof(Ffile));//copyf=NULL;copyf=NULL;user1=init();strcpy(user1->name,“user1”);user2=init();strcpy(user2->name,“user2”);d=init();e=init();user1->child=d;user2->child=e;d->parent=user1;e->parent=user2;printf(“%d”,user1->child->type);if(b==1){ printf(“已經(jīng)進入user1系統(tǒng)n”);f=user1;show(user1);}else{ } printf(“已經(jīng)進入user2系統(tǒng)n”);f=user2;show(user2); for(;;){ printf(“****************************************************************n”);printf(“1.創(chuàng)建文件(夾) 5.讀文件 9.顯示當(dāng)前路徑 n”);printf(“2.刪除文件(夾) 6.寫文件 10.返回上一層目錄 n”);printf(“3.打開文件(夾) 7.拷貝文件 11.改變普通文件屬性n”);printf(“4.關(guān)閉普通文件 8.粘貼文件 12.退出n”);printf(“****************************************************************n”);printf(“選擇操作：n”);scanf(“%d”,&c);if(c==12){ break;}else if(c==1){ creatf(f);} else if(c==2){ printf(“選擇要刪除的文件(夾)的名字：n”);scanf(“%s”,ch);deletefile(f,ch);} else if(c==3){ f=openff(f);} else if(c==4){ closefile(f);} else if(c==5){ readfile(f);} else if(c==6){ writefile(f);} else if(c==7){ copyf=copyfile(f,copyf);} else if(c==8){ prastefile(f,copyf);copyf=NULL;} else if(c==9){ printf(“路徑為：n”);showroute(f);printf(“n”);} else if(c==10){ } f=backf(f); } else if(c==11){ change(f);} else { continue;} show(f);} printf(“歡迎使用!n”); 操作系統(tǒng)課程設(shè)計 設(shè)計題目 動態(tài)分區(qū)分配存儲管理 學(xué)生姓名學(xué) 號 專業(yè)班級 指導(dǎo)教師 呂 霆 20102675 計算機10-01班 第一章 課程設(shè)計概述 1.1 設(shè)計任務(wù): 動態(tài)分區(qū)分配存儲管理 1.2 設(shè)計要求 建立描述內(nèi)存分配狀況的數(shù)據(jù)結(jié)構(gòu)； ?建立描述進程的數(shù)據(jù)結(jié)構(gòu)； ?使用兩種方式產(chǎn)生進程：（a）自動產(chǎn)生，（b）手工輸入； ? 在屏幕上顯示內(nèi)存的分配狀況、每個進程的執(zhí)行情況； ? 建立分區(qū)的分配與回收算法，支持緊湊算法； ? 時間的流逝可用下面幾種方法模擬：（a）按鍵盤，每按一次可認(rèn)為過一個時間單位；(b)響應(yīng)WM_TIMER； ? 將一批進程的執(zhí)行情況存入磁盤文件，以后可以讀出并重放； ? 支持算法：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法：最壞適應(yīng)算法。 1.3 設(shè)計目的 旨在讓我們更好的了解動態(tài)分區(qū)管理方面的知識.第二章 原理及算法描述 2.1動態(tài)分區(qū)分配算法原理 首次適應(yīng)算法 * 算法概述：分配內(nèi)存時，從鏈?zhǔn)组_始順序查找，找到滿足的空閑分區(qū)則劃出空間分配，余下的空閑空間仍保留在空閑鏈表中 * 實現(xiàn)方法：分配時從數(shù)組第一個元素開始比較，若符合條件則將該元素減去對應(yīng)作業(yè)的值 循環(huán)首次適應(yīng)算法 * 算法概述：由首次適應(yīng)算法演變，只是每次分配改為由上一次找到的空閑分區(qū)開始查找 * 實現(xiàn)方法：在首次適應(yīng)算法的基礎(chǔ)上增加一個值用于記錄找到的空閑分區(qū)的位置 最佳適應(yīng)算法 * 算法概述：每次為作業(yè)分配內(nèi)存時，總是把能滿足要求、又是最小的空閑分區(qū) 分配給作業(yè) * 實現(xiàn)方法：我們決定每次分配先把空閑分區(qū)按從小到大的順序排列，然后將第一個匹配分區(qū)分配給作業(yè) 最壞適應(yīng)算法 * 算法概述：每次為作業(yè)分配內(nèi)存時，總是挑選一個最大的空閑分區(qū)分割給作業(yè)使用 * 實現(xiàn)方法：算法與最佳適應(yīng)算法幾乎相同，僅在排序時把空閑分區(qū)表按從大到小的順序排列，所以未作詳細注釋 回收分區(qū) 當(dāng)進程運行完畢釋放內(nèi)存時,系統(tǒng)根據(jù)回收區(qū)的首址,從空閑區(qū)鏈(表)中找到相應(yīng)的插入點,此時可能出現(xiàn)以下四種情況之一;1)回收區(qū)與插入點的前一個空閑分區(qū)F1相鄰接,此時應(yīng)將回收區(qū)與插入點的前一分區(qū)合并,不必為回收區(qū)分配新表項,而只需修改其前一分區(qū)F1的大小.2)回收分區(qū)與插入點的后一空閑分區(qū)F2相鄰接,此時也可將兩分區(qū)合并,形成新的空閑分區(qū),但用回收區(qū)的首址作為新空閑區(qū)的首址,大小為兩者之和.3)回收區(qū)同時與插入點的前,后兩個分區(qū)鄰接,此時將三個分區(qū)合并,使用F1的表項和F1的首址,取消F2的表項,大小為三者之和.4)回收區(qū)既不與F1相鄰接,又不與F2鄰接.這時應(yīng)為回收區(qū)單獨建立一新表項,填寫回收區(qū)的首址和大小,并根據(jù)其首址插入到空閑鏈中的適當(dāng)位置.緊湊算法 通過移動內(nèi)存中的作業(yè)的位置,以把原來多個分散的小分區(qū)拼接成一個大分區(qū)的方法.第三章 開發(fā)環(huán)境 此程序是本人利用c++語言在vs2012的開發(fā)環(huán)境中實現(xiàn)的第四章 程序?qū)崿F(xiàn)--數(shù)據(jù)結(jié)構(gòu) #include int recycle;//需要回收的盤塊序號 int id1;//算法選擇號 int m;//內(nèi)存區(qū)數(shù) int n;//空閑區(qū)數(shù) int q;//進程數(shù) int r=0;//循環(huán)首次適應(yīng)算法：對應(yīng)的這次查找到的空閑分區(qū)序號 //打印輸出函數(shù) void vision(){ int i;int j;if(id1==1)stream.open(“first_fit.txt”, ios::app);if(id1==2)stream.open(“nextfirst_fit.txt”, ios::app);if(id1==3)stream.open(“best_fit.txt”,ios::app);if(id1==4)stream.open(“worst_fit.txt”, ios::app);if(id1==5)stream.open(“compact.txt”,ios::app);if(id1==6)stream.open(“huishou.txt”,ios::app);cout<<“-------------內(nèi)存分配狀態(tài)-------------”< } cout < } cout < } //作業(yè)信息的自動產(chǎn)生 void create_pro(){ } //作業(yè)的手動生成 void create_zuoye(){ int j;int choice2;int id3=rand()%10;m=id3;//內(nèi)存區(qū)數(shù)量 cout<<“產(chǎn)生”< } ary3[0]=42;ary3[1]=86;ary3[i]=rand()%100;if(ary3[i]==0){i--;} { } cout<<“--------------------------”< } //內(nèi)存信息的自動產(chǎn)生 void create_apply(){ int k=0;//空閑區(qū)數(shù)量 for(i=0;i if(ary1[i][3]!=2){ary2[k][0]=ary1[i][0];ary2[k][1]=ary1[i][1];ary2[k][2]=ary1[i][2];k++;} int i;for(i=0;i } ary1[i][0]=i+1;ary1[i][1]=rand()%100;if(i==0){ } ary1[i][3]=rand()%3;//cout < } cout<<“你創(chuàng)建了”< } //內(nèi)存信息的手動生成 int create_fenqu(){ } //首次適應(yīng)算法 void first_fit()int k,x,y,o=0;int a=0;cout<<“輸入想創(chuàng)建的內(nèi)存分區(qū)塊數(shù) : ”;cin>>k; cout<<“輸入”< } cout<<“輸入內(nèi)存塊的分配狀態(tài)”< } ary1[0][2]=0;ary1[1][2]=ary1[0][1];for(int i=2;i for(int i=0;i } n=a;return m,n;if(ary1[i][3]!=2){ } ary2[a][0]=ary1[i][0];ary2[a][1]=ary1[i][1];ary2[a][2]=ary1[i][2];a++;ary1[i][2]=ary1[i-1][2]+ary1[i-1][1];//起始地址 cin>>y;if(y==2){ } ary1[i][3]=y;//狀態(tài) n++;ary1[i][0]=i;//序號 cin>>x;ary1[i][1]=x;//大小 } n=k;//空閑塊數(shù)量 { vision();int i;int j;int k;int l;int d;//用來保存第k個的值 int id2=0;for(i=0;i for(j=0;j if(ary2[j][1]>=ary3[i])//進程占用空間小于等于其中一個空閑區(qū)的大小 { cout<<“[”< ary1[ary2[j][0]-1][3]=2;for(k=j+1;k ary2[k-1][0]=ary2[k][0];ary2[k-1][1]=ary2[k][1];ary2[k-1][2]=ary2[k][2];} n--; }else//否則的話，空閑鏈對應(yīng)的地方盤塊大小小了進程占用的大小，并且內(nèi)存分配從對應(yīng)的 { l=ary2[j][0];d=ary1[l-1][1];//大小 ary1[l-1][1]=ary3[i];ary1[l-1][3]=2;m++;for(k=m;k>ary2[j][0]+1;k--){ ary1[k-1][0]=ary1[k-2][0]+1;ary1[k-1][1]=ary1[k-2][1];ary1[k-1][2]=ary1[k-2][2];ary1[k-1][3]=ary1[k-2][3];那一項開始增加一項 } l=ary2[j][0]; } } { if(ary1[id2][3]!=2) } } n=k;} break;} else { } cout<<“[”< { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[l][0]=l+1;ary1[l][1]=d-ary3[i];ary1[l][2]=ary1[l-1][1]+ary1[l-1][2];ary1[l][3]=0;k=0;for(id2=0;id2 //首次循環(huán)適應(yīng)算法 void next_fit(){ vision();int i;int j;int k;int s;int d;int id2;for(i=0;i { for(j=r;j if(ary3[i]<=ary2[j][1]){ cout<<“[”< { } else//對應(yīng)的空閑塊大小大于進程需要大小 { //-----改變內(nèi)存分配情況-----r=(r+1)%n;//改變第k塊的內(nèi)容 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;//從k+1之后所有向后移一格 m++;//內(nèi)存塊數(shù)增加1 for(s=m-1;s>k;s--){ ary1[s][0]=ary1[s-1][0]+1;ary1[s][1]=ary1[s-1][1];ary1[s][2]=ary1[s-1][2];//---改變內(nèi)存分配---k=ary2[j][0];//得到對應(yīng)空閑塊對應(yīng)內(nèi)存塊的序號 k--;ary1[k][3]=2;//把對應(yīng)內(nèi)存塊標(biāo)志位上改成已分配 //------------------//--改變空閑塊表：把從這塊空閑塊以下的所有空閑塊向上移一格--n--;for(k=j;k } vision();//------------------break;ary2[k][0]=ary2[k+1][0];ary2[k][1]=ary2[k+1][1];ary2[k][2]=ary2[k+1][2];stream<<“[”< } } //思路：先把空閑列表檢索一遍，選出最佳答案，進行分配 void best_fit()//最佳算法--按順序檢索，把與進程要求內(nèi)存大小最接近的快分配給進程 { int i;int s;int j=-9999;//用來保存最接近的答案 int e;//用來存放進行比較時的中間結(jié)果 } { if(ary1[id2][3]!=2) } } else{ } cout<<“[”< { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} ary1[s][3]=ary1[s-1][3];} //改變第k+1塊內(nèi)容：對應(yīng)的數(shù)組是ary1[k] ary1[k][0]=ary1[k-1][0]+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];//--------------------------//----改變空閑表分配情況----k=0;for(id2=0;id2 }else { cout<<“[”< for(s=0;s } if(j<0){ cout<<“[”< if(ary2[j][1]==ary3[i]){ } else for(l=k;l } n--;ary2[l-1][0]=ary2[l][0];ary2[l-1][1]=ary2[l][1];ary2[l-1][2]=ary2[l][2];ary1[k-1][3]=2;k=ary2[j][0]; } //最壞適應(yīng)算法 void worst_fit() } { if(ary1[id2][3]!=2) } } vision();n=k; } for(k=j+1;k { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} { //把對應(yīng)的內(nèi)存分配進行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){ } k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];for(id2=0;id2 { }else { cout<<“[”< int e=-9999;//用來存放進行比較時的中間結(jié)果 int k;int l;int d;int id2;vision();{ j=-9999;e=-9999;for(s=0;s } if(j<0){ cout<<“[”< if(ary2[j][1]==ary3[i]){ k=ary2[j][0]; ary1[k-1][3]=2; for(l=k;l { if(ary1[id2][3]!=2) } } vision();n=k; } for(k=j+1;k { ary2[k][0]=ary1[id2][0];ary2[k][1]=ary1[id2][1];ary2[k][2]=ary1[id2][2];k++;} } else { //把對應(yīng)的內(nèi)存分配進行更改 k=ary2[j][0];d=ary1[k-1][1];ary1[k-1][1]=ary3[i];ary1[k-1][3]=2;m++;for(l=m;l>ary2[j][0]+1;l--){ } k=ary2[j][0];ary1[k][0]=k+1;ary1[k][1]=d-ary1[k-1][1];ary1[k][2]=ary1[k-1][1]+ary1[k-1][2];ary1[k][3]=0;k=0;ary1[l-1][0]=ary1[l-2][0]+1;ary1[l-1][1]=ary1[l-2][1];ary1[l-1][2]=ary1[l-2][2];ary1[l-1][3]=ary1[l-2][3];} n--;ary2[l-1][2]=ary2[l][2];for(id2=0;id2 } //回收內(nèi)存算法： /* 有共計八種情況，1.（1）回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊（2）回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊(3)回收區(qū)上下連接的都是空閑盤塊（4)空閑區(qū)上下鄰接的都是已分配盤塊 （5）要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊(6)要回收的盤塊就是第一個盤塊，但是向下鄰接著已分配盤塊(7)要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊(8)要回收的盤塊就是最后一個盤塊，但是向上鄰接的是已分配盤塊 */ void apply_recycle(){ ary1[0][1]=ary1[0][1]+ary1[1][1];ary1[0][3]=0;for(i=1;i if(recycle==1){ //cout< if(ary1[1][3]!=2){ cout<<“要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊”< } else { ary1[0][3]=0;n++;ary2[0][0]=1;ary2[0][1]=ary1[0][1];ary2[0][2]=ary1[0][2];vision();} stream<<“要回收的盤塊就是第一個盤塊，并且向下鄰接著空閑盤塊”< ary2[k][0]=ary1[j][0]; ary1[0][3]=0;k=0;for(j=0;j //cout<<“ary1[j][3]”< } else{ cout<<“要回收的盤塊就是第一個盤塊，但是向下鄰接著已分配盤塊”< } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; { } m--;// cout<<“" k=0;vision();//cout<<”ary1[0][3]“< cout<<”ary1[j][3]“< } else{ cout<<”要回收的盤塊就是最后一個盤塊，但是向上鄰接的是已分配盤塊“< } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } else if(recycle==m){ if(ary1[recycle-2][3]!=2){ cout<<”要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊“< } n=k;vision(); } ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;stream<<”要回收的盤塊就是最后一個盤塊，并且向上鄰接的是空閑盤塊“< ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; } else{//剩下比較復(fù)雜的四種情況 if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]==2))//回收區(qū)上鄰接著空閑盤塊，下連接著{cout<<”回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊“< } } n=k;vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; ary1[recycle-1][3]=0;k=0;for(j=0;j //cout<<”ary1[j][3]“< stream<<”回收區(qū)上鄰接著空閑盤塊，下連接著已分配盤塊“< ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i } m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } if((ary1[recycle-2][3]!=2)&&(ary1[recycle][3]!=2))//回收區(qū)上下連接的都是空閑盤塊 { cout<<”回收區(qū)上下連接的都是空閑盤塊“< } vision(); } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++; } n=k;vision();} if((ary1[recycle][3]!=2)&&(ary1[recycle-2][3]==2))//回收區(qū)下鄰接著空閑盤塊，上鄰接著{ cout<<”回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊“< stream<<”回收區(qū)下鄰接著空閑盤塊，上鄰接著已分配盤塊“< ary1[recycle-2][3]=0;ary1[recycle-2][1]=ary1[recycle-2][1]+ary1[recycle-1][1];for(i=recycle-1;i } m--;k=0;for(j=0;j //cout<<”ary1[j][3]“< } } } if((ary1[recycle-2][3]==2)&&(ary1[recycle][3]==2))//空閑區(qū)上下鄰接的都是已分配盤塊 { } ary1[recycle-1][3]=0;k=0;for(j=0;j } vision();//cout<<”ary1[j][3]“< } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;cout<<”回收區(qū)上下連接的都是空閑盤塊“< } m=m-2;k=0;for(j=0;j } vision();//cout<<”ary1[j][3]“< } ary2[k][0]=ary1[j][0];ary2[k][1]=ary1[j][1];ary2[k][2]=ary1[j][2];k++;ary1[recycle-1][0]=ary1[recycle+1][0]-2;ary1[recycle-1][1]=ary1[recycle+1][1];ary1[recycle-1][2]=ary1[recycle+1][2];ary1[recycle-1][3]=ary1[recycle+1][3];n=k;n=k; } //緊湊算法 void compact(){ num_avl=0;for(id2=0;id2 int num_avl;//記錄空閑盤塊數(shù)量 int sum_avl=0;//總共空閑區(qū)大小 int num_apl=0;//統(tǒng)計總共空閑區(qū)有多大 vision();for(id2=0;id2 } //最后一塊空閑塊 ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=sum_avl;ary1[num_apl][2]=ary1[num_apl-1][1]+ary1[num_apl-1][2];ary1[num_apl][3]=0;m=num_apl+1;//包括最后一個空閑區(qū) if(ary1[id2][3]==2){ } ary1[num_apl][0]=num_apl+1;ary1[num_apl][1]=ary1[id2][1];if(num_apl==0){ } ary1[num_apl][3]=2;num_apl++;//cout<<”num_apl“< } //主函數(shù)入口 void main(){ if(choice1==1){ } num=rand()&10;q=num;int id3=2+rand()%8;m=id3;//內(nèi)存區(qū)數(shù)量 create_apply();create_pro();int i;int j;int num;int choice1;//操作選擇標(biāo)記 int choice2;int flag=1;//標(biāo)記是否再執(zhí)行 while(flag==1){ cout<<”********************************************“< } n=num_avl;vision(); } ary2[num_avl][0]=ary1[id2][0];ary2[num_avl][1]=ary1[id2][1];ary2[num_avl][2]=ary1[id2][2];num_avl++;if(choice1==2){ } vision(); cout<<”**------------------請選擇處理算法----------------------**“< } } cout<<”**************************** “< cout<<”**1首次適應(yīng)算法-----2循環(huán)首次適應(yīng)算法-----3最佳適應(yīng)算法 **“< } {first_fit();} {next_fit();} {best_fit();} {worst_fit();} { compact();} if(id1==6){ cout<<”*******************生成內(nèi)存狀態(tài)******************“< } cout<<”錯誤:內(nèi)存中不存在此塊！“< } if(id2==-9999){ apply_recycle();} if(ary2[i][0]==recycle){ } cout<<”錯誤：輸入的為空閑盤塊！"< 中南林業(yè)科技大學(xué) 操作系統(tǒng)課程設(shè)計 課程題目：模擬磁盤文件管理的程序 姓名: 學(xué)號: 專業(yè): 計算機科學(xué)與技術(shù) 年級: 2006 計算機科學(xué)學(xué)院 2008年11月 模擬磁盤文件管理的程序 一、課程設(shè)計內(nèi)容 ⑴ 自定義磁盤文件管理的數(shù)據(jù)結(jié)構(gòu)； ⑵ 能夠自由創(chuàng)建、修改、刪除文件； ⑶ 文件具有一定自定義的屬性； ⑷ 能夠顯示當(dāng)前系統(tǒng)文件的狀態(tài)。 二、課程設(shè)計的數(shù)據(jù)結(jié)構(gòu)說明 程序中定義了兩個類： class file//文件類 {private: char name[10];//文件名 public: int tag;//刪除標(biāo)記 1:已刪 0:未刪 file(){ } char *getname(){return name;} //獲取文件名 int gettag(){return tag;} //獲取刪除標(biāo)記 int getlength(){return length;} //獲取文件大小 int getblocknum(){return blocknum;} // 磁盤塊數(shù) int getblocksum1(){return blocksum1;} //磁盤塊號的始點 int getblocksum2(){return blocksum2;} //磁盤塊號的終點 int length，blocknum，blocksum1，blocksum2; void setname(char na[ ]){strcpy(name,na);} //設(shè)置文件名 void delwenjian(){ tag=1;}//設(shè)置刪除標(biāo)記 1:已刪 0:未刪 void creatfile(char *na,int L,int num,int s1,int s2)//創(chuàng)建文件 void deltefile(char *na){tag=1;strcpy(name,na);} //刪除文件 void disp()//輸出文件信息 class fdatabase //文件庫類 { private: int top;//文件記錄指針 file f[50];public: fdatabase(){top=-1;} //構(gòu)造函數(shù) int search(char *fname)//按文件名查找 int creatfile(char *na,int L,int num,int s1,int s2)//創(chuàng)建文件時先查找是否存在 int deltefile(char *na)//刪除文件時先查找是否存在 void disp()//輸出所有文件信息 }; 三、課程設(shè)計的模板說明 1、初始化，建立文件系統(tǒng) 輸入磁盤大小（G），每個盤塊大小（M），自動建立位示圖，位示圖字長定為32位 輸出位示圖的行數(shù)，以及行號、列號與磁盤塊號的轉(zhuǎn)換公式（都從0開始編號）。 2、循環(huán)選擇執(zhí)行以下功能 1、存儲文件 輸入建立的文件名和文件大小，如果該文件名已經(jīng)存在，則輸出不能建立的信息否則計算所需的磁盤塊數(shù) 為其分配足夠多的磁盤塊，并記錄下來 輸出所占用的磁盤塊號 2、刪除文件 輸入要刪除的文件名，如果該文件名不存在，則輸出刪除錯誤信息，否則收回該文件所占用的磁盤塊 刪除該文件名 3、顯示位示圖情況 顯示位示圖的情況 顯示剩余磁盤塊的數(shù)目 4、顯示文件列表 顯示文件名，文件大小，占用的磁盤塊數(shù)目和磁盤塊號 四、課程設(shè)計的源代碼 #include char name[10];//文件名 public: int tag;//刪除標(biāo)記 1:已刪 0:未刪 file(){ } char *getname(){return name;} //獲取姓名 int gettag(){return tag;} //獲取刪除標(biāo)記 int getno(){return no;} //獲取文件編號 int getlength(){return length;} //獲取文件大小 int getblocknum(){return blocknum;} // 磁盤塊數(shù) int getblocksum1()//磁盤塊號的始點 { return blocksum1;} int getblocksum2()//磁盤塊號的終點 { return blocksum2;} int length;//文件大小 int blocknum;//盤塊數(shù) int blocksum1;//所占盤塊號的始點 int blocksum2;//所占盤塊號的終點 void setname(char na[ ])//設(shè)置文件名 {strcpy(name,na);} void delwenjian(){ tag=1;}//設(shè)置刪除標(biāo)記 1:已刪 0:未刪 void creatfile(char *na,int L,int num,int s1,int s2)//創(chuàng)建文件 { tag=0;length=L;blocknum=num;blocksum1=s1;blocksum2=s2;strcpy(name,na);blocknum=length/m;//盤塊數(shù)=文件大小/盤塊大小 if(length%m!=0)//盤塊數(shù)取上整 blocknum=blocknum+1;cout<<“ 所需磁盤塊數(shù)：”< for(;j<32;j++) a[i][j]=1;i=i+1;for(j=0;j<(sum+blocknum)-32;j++)//再進行剩余項賦值 { a[i][j]=1;} sum=sum+blocknum-32;} tt=tt+blocknum;//輸出文件所占用的盤塊號 cout<<“ 所占磁盤塊號：”< { for(ii=0;ii<=top;ii++) { if(strcmp(f[ii].getname(),fname)==0 && f[ii].tag==0) return 0; } return 1;} int creatfile(char *na,int L,int num,int s1,int s2)//創(chuàng)建文件時先查找是否存在 { int p;p=search(na); if(p==1) { top++; f[top].creatfile(na,L,num,s1,s2); return 1;} else {cout<<“！!該文件已存在,不能創(chuàng)建！!nn”; return 0;} } int deltefile(char *na)//刪除文件時先查找是否存在{int b,p,x=0,n1,n2,q1,q2,t;p=search(na);if(p==0)//若文件存在 { //進行刪除文件賦值 f[ii].tag=1;b=f[ii].length/m;//盤塊數(shù)=當(dāng)前文件大小/盤塊大小 if(ii==0)// 對第一個刪除文件進行賦值 for(k=0;k a[x][k]=0; else{ n1=(f[ii-1].blocksum2+1)/32;//被查找的文件之前文件所占用的盤塊數(shù) /32，//大于0表示跨行 n2=(f[ii].blocksum2+1)/32;//所有文件所占用的盤塊數(shù)/32，大于0表示跨行 q1=(f[ii-1].blocksum2+1)-n1*32;// 當(dāng)前文件的開始盤塊號 q2=(f[ii].blocksum2+1)-n2*32;// 用于跨行后計算盤塊號 t=n2-n1;if(t==0)//若n2與n1相等，表明當(dāng)前所有被占用盤塊在同一行 for(k=q1;k<1+b;k++) a[n2][k]=0; else { if((f[ii-1].blocksum2+1)%32==0)//前面所占用的盤塊數(shù)是32倍數(shù) { x=x+n1;//當(dāng)前文件賦值 for(;t-1>=0;t--,x++)//循環(huán)進行整行賦值 for(k=0;k<32;k++) a[x][k]=0; x=n2;//對剩余項賦值 for(k=0;k a[x][k]=0; } else //對當(dāng)前文件前幾項賦值 { x=n1; for(k=q1;k<32;k++) a[x][k]=0;x=x+1;int t1=t; for(;t-1>0;t--,x++)//中間整行賦值 for(k=0;k<32;k++) a[x][k]=0; x=n2;//最后剩余項賦值 for(k=0;k<(f[ii].blocksum2+1)-t1*32;k++) a[x][k]=0; } } return 1;} } else {cout<<“該文件不存在”; return 0;} } void disp()//輸出所有文件信息 { for(int i=0;i<=top;i++) if(f[i].tag==0) f[i].disp();} };void bit_map(int I){ int s=0;cout<<“-”< cout< out<<“--”< a[i][j]=0; cout<<“ 建立的位示圖為：”< cout<<“ 行數(shù)：”< cout <<“ttt1 存 儲 文 件nnttt2 刪 除 文 件 nnttt3 顯示位示圖情況 nnttt4 顯示文件列表”< case '1': cout <<“ 請輸入文件名: ”; cin>>fname; cout< if(q==0) { cout<<“！!該文件已存在,不能創(chuàng)建！!nn”; break;} cout <<“ 請輸入文件大小MB: ”; cin>>l; cout< if(l>g*1024) {cout<<“！!文件大小超過磁盤最大容量,無法進行分配！!”< break;} p.creatfile(fname,l,b,ss1,ss2); break; case '2': cout <<“ 請輸入文件名: ”; cin>>fname; cout<第二篇：操作系統(tǒng)課程設(shè)計文件管理
第三篇：操作系統(tǒng)課程設(shè)計_動態(tài)分區(qū)分配存儲管理
第四篇：操作系統(tǒng)課程設(shè)計++模擬磁盤文件管理的程序