进程调度算法 进程调度算法磁盘调度算法银行家算法操作系统课程设计大全

1、进程调度算法 进程调度算法磁盘调度算法银行家算法操作系统课程设计大全 操作系统课程设计学院名称：专业班级：姓 名：学 号：说明书 2010年7月16日评分标准 优秀：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确，程序完全实现设计要求，独立完成；良好：有完整的符合标准的文档，文档有条理、文笔通顺，格式正确；程序完全实现设计要求，独立完成，但存在少量错误；中等：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案正确； 及格：有完整的符合标准的文档，有基本实现设计方案的软件，设计方案基本正确；不及格：没有完整的符合标准的文档，软件没有基本实现设计方案，设计方案不正确。没有独立完成，

2、抄袭或雷同。 年 月 日目 录 一进程调度算法 二银行家算法 三磁盘调度算法 4-23 页 24-34 页 35-46页进程调度算法1设计目的在多道程序设计中，经常是若干个进程同时处于就绪状态，必须依照某种策略决定哪个进程优先占有处理机，因而必须解决进程调度的问题，进程调度算法就是要解决进程调度的问题。 2. 任务及要求2.1 设计任务设计程序来模拟进程的四种调度算法，模拟实现调度的基本功能。 2.2 设计要求产生的各种随机数要加以限制，如alltime限制在40以内的整数。进程的数量n不能取值过大。3. 算法及数据结构3.1算法的总体思想（流程）每个用来标识进程的进程控制块PCB用结构来描述

3、，包括以下字段：（1）进程优先数ID，其中0为闲逛进程，用户进程的标识数为1，2，3。 （2）进程优先级Priority，闲逛进程（idle）的优先级为0，用户进程的优先级大于0，且随机产生，优先数越大，优先级越高。（3）进程占用的CPU时间CPUtime，进程每运行一次，累计值等于4。 （4）进程总共需要运行时间Alltime，利用随机函数产生。 （5）进程状态，0：就绪态；1：运行态；2：阻塞态。 利用链表将数据连接起来，实现数据的存储。3.2 链表模块 3.2.1 功能实现链表的存储功能，以及实现存储的查找功能。3.2.2 数据结构构造链表这个数据结构，以及链表的初始化，链表的插入，链表

4、的长3.2.3 算法 typedef structElemType *elem; int length; int listsize; SqList;Status InitList(SqList &l) l.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType); if(!l.elem) exit(OVERFLOW); stsize) ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase) e

5、xit(OVERFLOW); L.elem=newbase;L.listsize+=LISTINCREMENT;ElemType *q=&L.elemi-1, *p=&L.elemL.length-1; while(p>=q) *(p+1)=*p; -p; /插入位置后的元素右移 *q=e; +L.length; return OK; Status GetElem(SqList L,int i,ElemType &e) if(iL.length)return ERROR; elsereturn OK;void Outputlist(SqList &L) i

6、f(0=L.length)printf(elsefor(int i=0;iprintf(3.3 主函数模块 3.3.1功能实现进程调度的四种算法，以及人机交互的菜单。 3.3.2 数据结构主要包括五个部分，分别是四种算法，和进程的输入和菜单部分，功能分别实现。 3.3.3算法void main() int number; PCB pcb100 ;srand(time(0); int max; int ppp100; int time=0; int time1; int m; int a100; a0=0;printf(*n printf(* printf(if(m!=1&&m!

7、=2&&m!=3&&m!=4) printf(if(m!=1&&m!=2&&m!=3&&m!=4) printf(scanf( printf(scanf( printf(scanf( printf(printf(for(int r=0;r for(int i=0;i pcbi.Priority=rand()%50; while(1)if(pcbi.Priority else break; pcbi.Alltime=rand()%40; while(1)if(pcbi.Alltimepcbi.Alltime=rand

8、()%40;elsebreak; if(m=1) printf( int coun=0; /计数变量 int wait100; /等待时间数组 wait0=0; int Allwait=0; for(int i1=0;i1为%dn coun+=pcbi1.Alltime; if(i1!=0) waiti1=pcbi1-1.Alltime+waiti1-1; for(int i2=0;i2 printf( if(m=2)int min=pcb0.Alltime;int wait1100;wait10=0;int in=0;int coun1=0;printf(度!*ncoutfor(i=0;ic

9、outprintf( for(i=0;imin=50;for(j=0;j作业优先调 if(pcbj.Alltimeif(m=3) printf( printf( for(int f=1;fint count=0,count1=0;for(int i=0;ipppi=pcbi.Priority;if(pcbi.Alltime!=0)count1+;count1-;time=time+count1*4;max=Max(ppp,number);if(pcbmax.Alltime=0)pppmax=-1;pcbmax.Priority=-1;max=Max(ppp,number);pcbmax.Pri

10、ority-=4;pcbmax.Alltime-=4;pcbmax.CPUtime+=4;if(pcbmax.Alltimepcbmax.Alltime=0; for(int w=0;w printf( 间n for(int k=0; kprintf(pcbk.Priority, pcbk.Alltime,pcbk.CPUtime); for(int l=0;l for(int k=0; kprintf(printf( printf( for(int f=1;f int count=0; for(i=0;i0) pcbi.Alltime-=4; continue; pcbi.CPUtime+=

11、4; if(pcbi.Alltime pcbi.Alltime=0; / printf( printf( for(int k=0; k / for(int l=0;l printf(4. 实验结果及分析4.1 实验结果先到先服务算法的实验结果如下： 最短作业优先调度的实验结果如下： 优先权调度算法的实验结果如下： 轮转法调度的实验结果如下： 4.2 结果分析本次试验基本实现了进程调度的四种算法，每一种算法都能模拟出算法的具体过程。相应的结果也完全符合预想的结果。同时，对于算法的实践编写进一步增加了编程的技巧，以及编程的熟练程度。 银行家算法 1设计目的银行家算法是避免死锁的一种十分重要的方法，

12、通过编写一个模拟的动态的银行家算法的程序，能够进一步加深对死锁的理解，以及产生死锁的必要条件。并掌握通过银行家算法来避免死锁。 2. 任务及要求2.1 设计任务根据银行家算法的基本思想来设计程序，模拟银行家算法的过程。用程序来实现银行家算法的具体动态过程。2.2 设计要求根据银行家算法的基本思想，编写和调试一个能实现动态的分配资源的模拟程序。并能够有效的防止死锁的发生。 3. 算法及数据结构3.1算法的总体思想（流程）银行家算法的基本思想是，系统中的所有进程放入进程集合，在安全状态下系统受到进程的请求后会试探性的把资源分配给他，现在系统将剩下的资源和进程集合中其他进程还需要的资源作对比，找出剩

13、余资源能满足的进程，从而保证进程运行完并释放资源继续满足剩下进程对资源的需要。最后检查集合为空集时表明本次申请可行，系统继续处于安全状态，可以实施本次分配。否则不能实施本次分配。3.2 显示资源矩阵 showdata() 模块3.2.1 功能主要是显示资源的矩阵，包括输入的已分配的的资源矩阵，以及输出的资源矩阵。3.2.2 数据结构最大需求矩阵max以及已分配矩阵allocation，分别定义为m*n阶的矩阵，利用二维数组来存储。3.2.3 算法 void showdata() /显示资源矩阵int i,j;coutfor(i=0;icoutcoutfor (j=0;jcoutcoutcout

14、coutcoutfor(j=0;jfor(i=0;icoutcoutcoutfor(i=0;icoutfor(j=0;jcoutcoutfor(j=0;jcoutcoutfor(j=0;jcoutcout 3.3 申请资源判定模块3.3.1功能利用银行家实现对申请的资源进行判定。3.3.2 数据结构对已经存储的矩阵进行比较。3.3.3算法 void share()/利用银行家算法对申请资源对进行判定 char ch;int i=0,j=0;ch=y;coutcin>>i;/输入须申请的资源号coutfor(j=0;j coutcin>>Requestj;/输入需要申请的

15、资源for (j=0;j if(Requestj>Needij)/判断申请是否大于需求，若大于则出错coutch=n;break;elseif(Requestj>Avaliablej)/判断申请是否大于当前资源，若大于则coutcoutch=n;break; if(ch=y)changdata(i);/根据进程需求量变换资源showdata();/根据进程需求量显示变换后的资源safe();/根据进程需求量进行银行家算法判断 3.4 主函数模块3.4.1功能实现银行家算法对资源的增加、删除、修改。 3.4.2 数据结构 对已经完成的模块进行功能集成。3.4.3算法 int main

16、() int i,j,number,choice,m,n,flag;char ming;cout cout *coutcoutcin>>n;coutN=n;for(i=0;icoutcin>>ming;namei=ming;coutcin>>number;Avaliablei=number;coutcoutcin>>m;M=m;coutfor(j=0;jcin>>Maxij;doflag=0;coutfor(i=0;ifor(j=0;j cin>>Allocationij;if(Allocationij>Maxij)

17、flag=1;Needij=Maxij-Allocationij;if(flag)cout showdata(); /显示各种资源safe(); /用银行家算法判定系统是否安全while(choice) cout coutcoutcoutcoutcoutcout coutcoutcin>>choice;switch(choice) case 1: addresources();break; case 2: delresources();break;case 3: changeresources();break;case 4: share();break;case 5: addpro

18、cess();break;case 0: choice=0;break;default: cout return 1;4. 实验结果及分析4.1 实验结果 4.2 结果分析银行家算法就是在系统分配资源时，找到一个安全序列，使得进程间不会发生死锁。若发生死锁则让进程等待。4.3实验总结通过本次试验，加深了我对银行家算法的理解，掌握了如何利用银行家算法来避免死锁。通过对代码的编写也加深了我对数据结构的进一步理解。 磁盘调度算法1设计目的加深对操作系统的磁盘调度的进一步理解以及进一步的认识。加强实践能力和动手动脑能力，同时加深对磁盘调度概念的理解，同时也再一次提高了自己编程的能力。2. 任务及要求2

19、.1 设计任务分析设计模拟磁盘管理系统的方法，加深对磁盘调度算法的了解以及个算法的特点。2.2 设计要求分别设计出先来先服务算法，最短寻道时间优先算法，扫描算法。并分别求出它们的平均寻道时间。3. 算法及数据结构3.1算法的总体思想（流程） 1.先来先服务的算法，即先来的请求先被响应。FCFS算法看起来是比较合理的算法，但是当请求频率过高的时候FCFS算法的响应时间就会大大的延长，这也是最基本的算法，直接实现的是由输入的顺序来顺序的执行。2.最短寻道时间优先算法，要求访问的磁道，与当前磁头所在的磁道的距离最近，从而以使每次的寻道时间最短。3.扫描磁盘调度，该算法不考虑与访问磁道与当前磁道的距离

20、，更优先考虑的磁头当前的移动方向，例如，当磁头正在有向外移动时，SCAN算法所考虑的下一个访问对象，应是其与访问的磁道，即在当前磁道之外，又是最近的。这样磁头逐渐的从外向里移动，直至再无更里面的磁道要访问，从而避免了出饥饿的情况。 3.2先来先服务模块3.2.1 功能实现磁盘调度的先来先服务调度。 3.2.2 数据结构用链表来存储输入的数据，即各待访问的磁道。然后遍历这个链表，依次对这个链表进行访问，从而实现先来先服务调度。3.2.3 算法 void fcfs(Node *head,int c,int f) /先来先服务算法void print(Node *);Node *l; /,*m,*n

21、;float num=0;l=head->next;for(int i=0;i num+=abs(l->data-f);f=l->data;l=l->next;num=num/c;coutprint(head);cout 3.3最短寻道时间优先模块 3.3.1功能实现磁盘调度的最短寻道时间调度。 3.3.2 数据结构以链表来存储数据，通过循环访问链表来寻找距本次磁道的最短距离，依次这样访问。3.3.3算法、 void sstf(Node *head,int c,int f)/最短寻道时间优先算法void print(Node *);Node *p,*q,*r,*s,*l

22、,*m;l=(Node *)malloc(sizeof(Node);l->next=NULL;m=l;q=head;p=head->next;s=head;r=head->next;for(int i=0;iint min=abs(f-r->data);for(int j=0;jp=p->next;q=q->next;if(abs(f-p->data)min=abs(f-p->data);r=p;s=q;num+=abs(f-r->data);f=r->data;s->next=r->next;r->next=NUL

23、L;m->next=r;m=r;q=head;p=head->next;s=head;r=head->next;coutprint(l);cout 3.4 扫描算法模块 3.4.1功能实现磁盘调度的扫描算法。 3.4.2 数据结构以链表来存储数据，以开始磁道为限来分磁道，分为大于的和小于的，然后分别访问两部分，按照开始的方向进行访问。3.4.3算法 void scan(Node *head,int c,int f) /扫描算法 void print(Node *);int min,max,i=0,j=0;float num=0;Node *p,*q,*r,*s,*m,*n,*

24、x,*y;r=(Node *)malloc(sizeof(Node);/存放比开始磁道小的磁道r->next=NULL;s=r;m=(Node *)malloc(sizeof(Node); /存放比开始磁道大的磁道m->next=NULL;n=m;x=(Node *)malloc(sizeof(Node);x->next=NULL;y=x;q=head;p=head->next;while(p->next!=NULL)if(p->data-f>0)q->next=p->next;p->next=NULL;n->next=p;n=

25、p;p=q->next;i+;elseq->next=p->next;p->next=NULL;s->next=p;s=p;p=q->next;j+; if(p->data>=f)n->next=p;n=p;i+;elses->next=p;s=p;j+;q=r; /对比开始磁道小的磁道排序p=r->next;while(q->next->next!=NULL)q=q->next;p=q->next;max=q->data;while(p->next!=NULL)if(p->data>max)max=p->data;p-&