动态分区式存贮区管理

1、  操作系统上机课程报告     姓 名： 姜 瑞 班号： 193151 学 号： 指导教师： 张求明 院（系）： 计算机学院 专业： 网络工程   2016 年 11 月独立工作成果声明 本人声明所呈交的操作系统上机报告，是我个人在导师指导下进行的程序编制工作及取得的成果。尽我所知，除文中已经标明的引用内容，和已经标明的他人工作外，本报告未包含任何抄袭自他人的工作成果。对本报告的工作做出贡献的个人，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 报告作者签名： 日期： 年 月 日实验一 多级

2、队列调度算法（1）课程设计题目：多级队列调度算法（2）程序功能及设计思路程序功能：模拟CPU在处理程序时的进程调度，使用循环轮转法和短进程优先调度的算法来完成一组请求。设计思路：1. 首先使用一个cpp文件将运行所需要的数据写入一个文件名为”1.txt”的文本文件，格式是 “Pi need turn”，每组数据之间换行隔开，则可以在运行的cpp文件中得到所需要运行的内容。2. 在程序实现的过程中，按照题目所给要求从文件中读取数据，前五项按照已等待时间排序成一个循环队列(已等待时间长的放在队伍的靠前的地方)，后五项按照需要运行的时间排成一个队列(运行时间短的放在队伍靠前的地方)。然后按照实现的描

3、述来进行数据的处理。最后输出每一个进程运行所需要的时间。（3）数据结构及算法设计数据结构:结构体struct tag_pcb队列循环队列文件流数据算法设计:对于循环队列RQ1，从文件中依次读取进程的信息，根据要求形成循环队列，然后从队首开始循环，每次使用一个时间片q的长度，看该进程是否运行完成，如果在时间片以内的时间运行完成，则仅耗费所需时间，然后将该进程的运行时间存入数组中，将该进程从队列中移除，并将队列连接完好，然后使用delete删除该进程所占用的内存空间，接下来从下一个进程继续，依次循环往复，直到所有的进程均运行完成。对于队列RQ2中形成队列时，按照要求形成单向队列，然后从需要时间短的

4、开始运行，运行完之后将时间存入数组，然后将该进程使用delete删除，然后将当前指针移到下一位置，进行下一个进程的处理。直到所有进程均运行完成，即队列为空的状态。在使用数组存放的时候ai对应相应的进程运行时耗费的时间，然后从a0输出到a9，即可输出对应时间。（4）程序运行情况（5）编程中遇到的困难及解决方法、实习心得或良好建议困难和解决方法：1.对于C+文件的写入和读取不是很熟练，在网上查找相关写法之后按照格式试验完成了文件的操作。2.对于链表形式的队列原本不是很熟悉，在写代码的过程中遇到了很多的麻烦，可以处理一次的队列操作，但是在写成循环时时常出现队列断链或者连错的情况，这个问题是经过自己多

5、次调试，反思原理之后改错完成的。3.在字符型char和整型int的转化中之前对于P10进程的判断有一些错误，之后经过调试发现问题，然后对字符串长度进行判断解决了这个问题。源代码贴在下方：/*写入数据.cpp*/#include<iostream>#include<fstream>using namespace std;struct tag_pcb char name8; int need; /需运行时间 int turn; /周转时间 struct tag_pcb *next;PCB10;int main() int i; for(i=0;i<10;+i) PCB

6、0='P' PCB1=i+49; PCB9.name1='1',PCB9.name2='0',PCB9.name3='0' PCB0.need=16;PCB1.need=11;PCB2.need=14; PCB3.need=13;PCB4.need=15;PCB5.need=21; PCB6.need=18;PCB7.need=10;PCB8.need=7; PCB9.need=14; PCB0.turn=6;PCB1.turn=5;PCB2.turn=4; PCB3.turn=3;PCB4.turn=2;

7、PCB5.turn=1; PCB6.turn=2;PCB7.turn=3;PCB8.turn=4; PCB9.turn=5; cout<<"写入文件的数据如下:"<<endl; for(i=0;i<10;+i) cout<<PCB<<' ' cout<<endl; for(i=0;i<10;+i) cout<<PCBi.need<<' ' cout<<endl; for(i=0;i<10;+i) cout<<

8、;PCBi.turn<<" "/接下来将数据以结构体的方式写入文件 ofstream out("E:1.txt"); for(i=0;i<10;+i) out<<PCB<<' '<<PCBi.need<<' '<<PCBi.turn; out<<endl; out.close(); cout<<endl<<"已完成数据输入文件"/*写入数据.cpp*/*实验1(操作系统).cpp

9、*/#include<iostream>#include<cstdlib>#include<cstring>#include<fstream>using namespace std;typedef struct tag_pcb char name8; int need; /需运行时间 int turn; /周转时间 struct tag_pcb *next;PCB;PCB * filein1(PCB *RQ1,ifstream &in)/形成RQ1队列 PCB *current,*pre; PCB *tmp=new PCB; RQ1=tm

10、p,RQ1->next=NULL; in>>tmp->name>>tmp->need>>tmp->turn; for(int i=0;i<4;+i) PCB *tmp=new PCB; in>>tmp->name>>tmp->need>>tmp->turn;/从文件写入信息 current=RQ1; pre=NULL; /初始化while(current!=NULL&&current->turn>tmp->turn) pre=current;

11、 current=current->next; tmp->next=current; if(pre=NULL) /如果位置在表头插入队首 tmp->next=current; RQ1=tmp; else pre->next=tmp; /将队尾的结点的next接到队首，形成循环队列 int i=4;current=RQ1; while(i-) current=current->next; current->next=RQ1; cout<<"RQ1队列数据读入完成"<<endl; return RQ1;PCB *fil

12、ein2(PCB *RQ2,ifstream &in)/形成RQ2队列 PCB *current,*pre; PCB *tmp=new PCB; RQ2=tmp,RQ2->next=NULL; in>>tmp->name>>tmp->need>>tmp->turn; for(int i=0;i<4;+i) PCB *tmp=new PCB;in>>tmp->name>>tmp->need>>tmp->turn;/从文件写入信息 current=RQ2; pre=NUL

13、L; /初始化while(current!=NULL&&current->need<tmp->need) pre=current; current=current->next; tmp->next=current; if(pre=NULL) /如果位置在表头插入队首 tmp->next=current; RQ2=tmp; else pre->next=tmp; cout<<"RQ2队列数据读入完成"<<endl; return RQ2;int main() PCB *RQ1,*RQ2; int

14、 clock=0,q=7,temp; int time10; ifstream in("E:1.txt"); if(!in) cerr << "open error!" << endl; exit(1); RQ1=filein1(RQ1,in); RQ2=filein2(RQ2,in); in.close(); /文件读入数据完成,关闭数据流/进行RQ1队列的调度 PCB *current=RQ1; PCB *pre=RQ1; while(pre->next!=current) pre=pre->next; while

15、(RQ1!=NULL) if(current->need-q>0) clock+=q; current->need-=q; else clock+=current->need; current->need=0; /将时间导入到数组中 temp=strlen(current->name); /计算序数的位数，便于转化 if(temp=2) temp=current->name1-'1' else if(temp=3)temp=(current->name1-'0')*10+current->name2-'

16、;1'timetemp=clock+current->turn; /存入周转时间 if(current->need=0) if(current->next=current) /如果循环队列为空 delete current; RQ1=NULL; else pre->next=current->next; delete current; current=pre->next; else current=current->next; pre=pre->next; /进行RQ2队列的调度 current=pre=RQ2; while(RQ2!=N

17、ULL) /RQ2已经排好序，直接模拟调度即可 while(current!=NULL) clock+=current->need; /将时间导入到数组中 temp=strlen(current->name); /计算序数的位数，便于转化 if(temp=2) temp=current->name1-'1' else if(temp=3) temp=(current->name1-'0')*10+current->name2-'1' timetemp=clock+current->turn; /存入周转时间 c

18、urrent=current->next; delete pre; pre=current; RQ2=NULL; /完成调度，输出周转时间数组的结果 cout<<endl<<endl; for(int i=0;i<10;+i) cout<<'P'<<i+1<<"的周转时间为:"<<timei<<endl;/*实验1(操作系统).cpp*/实验二 银行家算法（1）课程设计题目：银行家算法（2）程序功能及设计思路程序功能：使用银行家算法在动态分配资源的时候来

19、避免死锁。银行家算法要求进入系统的进程必须说明他对各类资源类型的实例的最大需求量。这一数量不能超过系统各类资源的总数。设计思路：先将数据写入文件，在E:/2.txt文件中按如下格式进行存放数据，第一行放入Available的三类资源的数据，然后下面开始放入Pi的Alloc（已占用资源）和Need（还需要资源的最大需求量），然后记下来存放四次请求，按照发出请求的进程号+三类请求的数量作为一行，记录下提供数据的四次请求。然后在运行时，依次读取请求数据来进行请求的判断，是否非法请求，是否阻塞，然后进行试探性分配，若满足安全性状态，则确定分配，否则取消试探性分配。（3）数据结构及算法设计数据结构：数组

20、文件流数据算法设计：首先从文件中读取数据建立当前的系统状态。然后从头开始读取请求，判断请求是否结束（在文件流输入的过程中判断是否读取到文件的尾部），若结束就退出程序，完成本次调度。否则判断请求是否超过还需要的最大需求量，若超过就输出该请求为非法请求，读取下一次请求。否则判断请求是否超过可用资源，若超过则输出该请求会使Pi进程阻塞，读取下一次请求，否则进行试探性分配。调用try_assign()函数，来将进程的资源进行分配。然后调用checksafe()函数来判断状态是否满足安全性状态的要求，若满足要求，则输出完成该请求，否则取消试探性分配，说明不满足安全性状态。在上一步骤完成后继续读取下一条请

21、求。（4）程序运行情况（5）编程中遇到的困难及解决方法、实习心得或良好建议遇到的困难和解决方法：在编程中遇到了request数组传参的问题，因为另外几数组都是以全局变量的形式存在，在最开始编写代码时没有考虑传递参数的问题，导致在函数体中无法调用request数组的情况，导致了判断的失效，修改后把request数组和指针p（代表发起请求的进程号）传入函数体即可正常使用。在进行安全性状态的判别时，因为理解问题没有考虑到分配之后从头（P1）开始判断是否满足安全性状态，所以在碰到一个安全性状态不满足的情况也是直接跳出循环而使程序运行错误（例如P1不满足时应判断P2，若满足则work=work+Allo

22、ci，再从P1开始从头判断是否满足true或者false的条件），修改的方法是使用goto语句，在从P1开始判断的地方加一个label标签，让进行了work=work+Alloci;则跳转至开头开始循环判断。实习心得：使用函数体进行判断非法和溢出的时候对于返回值true或者false的理解还有对if(!check2(request,*p)的真值判断一直有些混淆，不知道到底为真还是为假，在实习中理清了思路和判断。在安全性状态判别的checksafe()函数中在查找Finishi=false且Needi<=work条件的时候对于Needi<=work使用了第一个check1()函数已经

23、写的功能，改变传入参数的变量即可完成所需要求，即if(finishi=false&&!check1(work,i)，这样的写法减少了代码量，比较巧妙。源代码如下:/*写入数据.cpp*/#include<iostream>#include<fstream>using namespace std;#define n 5 /进程个数#define m 3 /资源种类int Availablem=2,3,3;int Allocnm=2,1,2,4,0,2,3,0,5,2,0,4,3,1,4;int Neednm=3,4,7,1,3,4,0,0,3,2,2,1,

24、1,1,0;int request44=2,0,3,4,4,1,0,1,1,2,0,1,3,0,0,2;int main() int i,j;/显示已分配资源和资源需求量 cout<<"已分配资源量t资源需求量"<<endl; cout<<" A B Ct A B C"<<endl; for(i=0;i<n;+i) cout<<'P'<<i+1<<' ' for(j=0;j<m;+j) cout<<Allocij&l

25、t;<' ' cout<<'t' for(j=0;j<m;+j) cout<<' '<<Needij; cout<<endl; /写入文件操作 ofstream out("E:2.txt");/写入已经存在的系统状态 for(i=0;i<3;+i) out<<Availablei<<' ' out<<endl; for(i=0;i<5;+i) for(j=0;j<3;+j) out<<A

26、llocij<<' ' for(j=0;j<3;+j) out<<Needij<<' ' out<<endl; /写入请求操作数据 for(i=0;i<4;+i) for(j=0;j<4;+j) out<<requestij<<' ' out<<endl; out.close();/显示进程请求内容 for(i=0;i<4;+i) cout<<"进程P"<<requesti0<<&qu

27、ot;请求资源("<<requesti1 <<','<<requesti2<<','<<requesti3<<')'<<endl; cout<<"写入文件操作成功"<<endl;/*写入数据.cpp*/*实验2(操作系统).cpp*/ #include<iostream>#include<fstream>#include<cstdlib>using namespace std

28、;#define n 5 /进程个数#define m 3 /资源种类int Availablem,Allocnm,Neednm;bool input(ifstream &in) int i,j; for(i=0; i<m; +i) in>>Availablei; for(i=0; i<n; +i) for(j=0; j<m; +j) in>>Allocij; for(j=0; j<m; +j) in>>Needij; / cout<<"已分配资源量t资源需求量"<<endl;/ c

29、out<<" A B Ct A B C"<<endl;/ for(i=0;i<n;+i)/ / cout<<'P'<<i+1<<' '/ for(j=0;j<m;+j)/ cout<<Allocij<<' '/ cout<<'t'/ for(j=0;j<m;+j)/ cout<<' '<<Needij;/ cout<<endl;/ return t

30、rue;bool read_req(ifstream &in,int *p,int *request) if(!in) return false; in>>*p; if(in.eof() return false; else for(int j=0; j<m; +j) in>>requestj; return true;bool check1(int *request,int p) /判断request和Need的关系 for(int i=0; i<m; +i) if(requesti>Needpi) return false; return

31、true;bool check2(int *request,int p) for(int i=0; i<m; +i) if(requesti>Availablei) return false; return true;void try_assign(int *request,int p,int d)/试探性分配,1为试探性分配,0表示取消试探性分配 if(d=1) for(int i=0; i<m; +i) Availablei-=requesti; for(int i=0; i<m; +i) Allocpi+=requesti; for(int i=0; i<m

32、; +i) Needpi-=requesti; else for(int i=0; i<m; +i) Availablei+=requesti; for(int i=0; i<m; +i) Allocpi-=requesti; for(int i=0; i<m; +i) Needpi+=requesti; cout<<"进程P"<<p+1<<"的请求不能达到安全性状态,取消分配"<<endl; bool checksafe() bool finishn=false; int workm,i

33、,j; for(i=0;i<m;+i) worki=Availablei;label: for(i=0;i<n;+i) if(finishi=false&&!check1(work,i) finishi=true; for(j=0;j<3;+j) workj+=Allocij; goto label; for(i=0;i<n;+i) if(finishi!=true) return false; return true;int main()/打开文件写入数据 int requestm; ifstream in("E:2.txt");

34、if(!in) cerr << "open error!" << endl; exit(1); input(in); int *p=new int; /用来表示请求资源的进程号 while(1) if(!read_req(in,p,request) /如果请求结束 break; if(!check1(request,*p-1) cout<<"进程"<<*p<<"进行非法请求"<<endl; else if(!check2(request,*p) cout<&

35、lt;"进程"<<*p<<"阻塞"<<endl; else /进行试探性分配 try_assign(request,*p-1,1); if(checksafe() cout<<"进程P"<<*p<<"请求资源("<<request0 <<','<<request1<<','<<request2<<")已完成调度"<<endl; else try_assign(request,*p-1,0); /取消试探性分配 cout<<"已完成所有请求"<<endl; in.close(); delete p;/*实验2(操作系统).cpp*/实验三  动态分区式存贮区管理（1）课程设计题目：银行家算法（2）程序功能及设计思路程序功能：模拟主存分区是存储区管理的方式，对进程的提出的申请内存和释放进程的请求进行处理，设计思路：（3）数据结构及算法设计数据结构：结构体链表算法