研发设计1进程调度算法模拟

1、山东科技大学学生课程设计设计 1 进程调度算法的模拟一、设计目的1、通过编程实现进程调度算法的模拟，了解进程调度的过程，理解进 程调度各方法的特点。二、设计要求1用语言来实现对 n 个进程采用不同调度算法的进程调度。2每个用来标识进程的进程控制块 PCB 用结构来描述，包括以下字 段：（1）进程优先数 ID，其中 0为闲逛进程， 用户进程的标识数为 1，2， 3。（2）进程优先级 Priority ，闲逛进程（ idle）的优先级为 0，用户进程 的优先级大于 0，且随机产生，优先数越大，优先级越高。 矚慫润 厲钐瘗睞枥庑赖。（3）进程占用的 CPU 时间 CPUtime，进程每运行一次，累计

2、值等于 4。（4）进程总共需要运行时间 Alltime ，利用随机函数产生。（5）进程状态， 0：就绪态； 1：运行态； 2：阻塞态。（6）队列指针 next，用来将多个进程控制块 PCB 链接为队列。3优先数改变的原则（1）进程在就绪队列中每呆一个时间片，优先数增加 1。 （2）进程每运行一个时间片，优先数减 3。1山东科技大学学生课程设计4在调度前，系统中拥有的进程数 PCB_number 由键盘输入，经初始化后，所有的进程控制块 PCB 链接成就绪队列。 聞創沟燴鐺險爱氇谴净。三、设计说明息FCFS算法，按照进程先后顺序输出SJS算法，按照 ALLTIME 从 小到大依次输出优先级算法，

3、按照优先从大 到小输出，进程执行依次 P-3，就绪队列中的进程 P+1RR 算法，按照时间片依次 执行进程， ALLTIME =4.结束1 FCFS 模块山东科技大学学生课程设计1.1 功能对于先到达的进程优先分配 CPU，按照先来先服务的原则依次执 行各进程。1.2 数据结构typedef struct PCBint ID;/进程优先数 ,用于标示不同的进程int Priority; / 进程优先级int CPUTime; /进程占用的 CPU 时间 CPUtime，进程 每运行一次，累计值等于 4int ALLTime;/进程总共需要运行时间 Alltimeint Status;/用于表示

4、进程状态， 0：就绪态； 1：运行态； 2：阻塞态PCB;1.3 算法void FCFS()山东科技大学学生课程设计Node *p=head-next;while(p!=NULL)cout 执行进程 endldata.ID;p=p-next;coutendl;cout 所有进程都执行完成 next!=NULL)pmin=head2-next;for(p=head2-next;p!=NULL;p=p-next)if(pmin-data.ALLTimep-data.ALLTime)pmin=p;山东科技大学学生课程设计cout 执 行 剩 余 区 间 长 度 最 短 的 进 程 endldata.

5、ID;for(p=head2;p!=NULL;p=p-next)if(p-next=pmin)p-next=p-next-next;free(pmin);printf(n);printf( 所有进程都执行完成。 nn);3 SearchMaxPRI 模块3.1 功能按照优先级从高到低依次执行程序3.2 数据结构q0 指向 q 的前一个进程，便于删除进程； p 返回优先级最大进程； q 用于遍历链表山东科技大学学生课程设计3.3 算法void SearchMaxPRI(int m)Node *p=head-next;Node *q=head-next;Node *q0=head;while(q!

6、=NULL)if(q-data.ALLTime=0)cout 进程已执行完成 endldata.ID;n-;q0-next=q0-next-next; free(q);q=q0-next;else山东科技大学学生课程设计if(q-data.Priorityp-data.Priority)p=q;q0=q0-next;q=q-next;if(n0)action(p);?执行完成后执酽锕极額閉镇桧猪訣锥。按照轮转的次序分配给每个程序一定的时间执行，行后面的进程 ，依次循环执行直到所有进程执行完成。4.2 数据结构4.3 算法void RR(int m)Node *p;while(head1-nex

7、t!=NULL)山东科技大学学生课程设计p=head1-next;Node *prep=head1;Node *q;while(p!=NULL)cout 执行进程一个时间片 data.ID;for(q=head1;q-next!=NULL;q=q-next)if(q-next=p)p-data.ALLTime-=4;p-data.CPUTime+=4;if(p-data.ALLTime=0)cout进程已执行完成 data.ID;prep-next=prep-next-next;山东科技大学学生课程设计free(p);p=prep-next;elseprep=prep-next;p=p-nex

8、t;coutendl;cout 进入下一次轮转 endl;cout 所有进程都执行完成 endl;四、运行结果及分析10山东科技大学学生课程设计该程序实现了进程调度的四种不同调度算法下的调度顺序的输出情 况11山东科技大学学生课程设计五、总结通过该程序的实现，对进程的调度有了更多的了解，对于不同的系统和系 统目标，通常采用不同的调度算法。有的算法适用于为数众多的短作业调 度，有的算法为系统合理的响应时间提供了保证。调度算法的选择的合适 与否很重要。 彈贸摄尔霁毙攬砖卤庑。源代码：#include#include#include#include#include #define TRUE 1#de

9、fine FALSE 0#define OK 1typedef struct PCBint ID;int Priority;int CPUTime;12山东科技大学学生课程设计int ALLTime;int Status;PCB;typedef PCB Dt;typedef struct NodeDt data;struct Node *next;Node;Node *head=(Node *)malloc(sizeof(Node);Node *head1=(Node *)malloc(sizeof(Node);Node *head2=(Node *)malloc(sizeof(Node);

10、int n;void create(int n)int i=1;srand(int)time(0);head-next=NULL;Node *q=head;13山东科技大学学生课程设计cout 优先数 优先级 CPUTime AllTime Status endl;謀荞抟箧飆鐸怼类蒋薔。while(idata.ID=i;p-data.CPUTime=0;p-data.Status=0;p-data.Priority=rand()%10+1;p-data.ALLTime=rand()%8+1;cout data.ID data.Priority data.CPUTime data.ALLTime

11、 data.Statusnext=NULL;q-next=p;q=q-next;i+;Node *p0=head1;14山东科技大学学生课程设计head1-next=NULL;for(q=head-next;q!=NULL;q=q-next)Node *r=(Node *)malloc(sizeof(Node); r-data.ID=q-data.ID; r-data.CPUTime=q-data.CPUTime; r-data.Status=q-data.Status; r-data.Priority=q-data.Priority; r-data.ALLTime=q-data.ALLTim

12、e; p0-next=r;r-next=NULL;p0=p0-next;Node *p1=head2;head2-next=NULL;for(q=head-next;q!=NULL;q=q-next)Node *k=(Node *)malloc(sizeof(Node);k-data.ID=q-data.ID;15山东科技大学学生课程设计k-data.CPUTime=q-data.CPUTime; k-data.Status=q-data.Status; k-data.Priority=q-data.Priority; k-data.ALLTime=q-data.ALLTime; p1-nex

13、t=k;k-next=NULL;p1=p1-next;void FCFS()Node *p=head-next;while(p!=NULL)cout执行进程 endldata.ID;p=p-next;coutendl;16山东科技大学学生课程设计cout 所有进程都执行完成 next!=NULL)pmin=head2-next;for(p=head2-next;p!=NULL;p=p-next)if(pmin-data.ALLTimep-data.ALLTime)pmin=p;cout执行剩余区间长度最短的进程 endldata.ID;for(p=head2;p!=NULL;p=p-next)

14、if(p-next=pmin)17山东科技大学学生课程设计p-next=p-next-next;free(pmin);coutendl;cout 所有进程都执行完成 next;while(q!=NULL)coutdata.ID执行一个时间片的进程 data.Priority=q-data.Priority+1;else18山东科技大学学生课程设计q-data.Priority=q-data.Priority-3;if(q-data.ALLTime4)q-data.ALLTime-=4;elseq-data.ALLTime=0;q-data.Status=1;q=q-next;void Sear

15、chMaxPRI(int m) Node *p=head-next;Node *q=head-next;Node *q0=head;while(q!=NULL)19山东科技大学学生课程设计if(q-data.ALLTime=0)coutdata.ID 进程已执行完成 next=q0-next-next;free(q);q=q0-next;elseif(q-data.Priorityp-data.Priority)p=q;q0=q0-next;q=q-next;if(n0)action(p);20山东科技大学学生课程设计void RR(int m)Node *p;while(head1-next

16、!=NULL)p=head1-next;Node *prep=head1;Node *q;while(p!=NULL)coutdata.ID 执行进程一个时间片 next!=NULL;q=q-next)if(q-next=p)p-data.ALLTime-=4;21山东科技大学学生课程设计p-data.CPUTime+=4;if(p-data.ALLTime=0)coutdata.ID 进程已执行完成 next=prep-next-next;free(p);p=prep-next;elseprep=prep-next;p=p-next;coutendl;cout进入下一次轮转 endl;22山

17、东科技大学学生课程设计cout 所有进程都执行完成 endl;int main()cout 请输入系统进程数： n;int m=n;if(n=0)cout此时没有就绪进程 endl;elsecreate(n);coutendl;cout先来先服务调度 endl;FCFS();coutendl;cout最短作业优先调度 endl;SJF();23山东科技大学学生课程设计coutendl;cout优先权的分时调度 next!=NULL)SearchMaxPRI(m);cout所有进程都执行完成 endl;coutendl;cout轮转法调度 endl;RR(m);24山东科技大学学生课程设计设计

18、2 模拟银行家算法一、设计目的1、通过对银行家算法的模拟，理解银行家算法的实现过程，了解系统 解决死锁的方法、设计要求1、编程序模拟银行家算法2、能体现算法的全过程三、设计说明25山东科技大学学生课程设计1. bank 模块1.1 功能利用银行家算法，给系统分配资源，避免死锁。1.2 数据结构Typedef struct RESOURCEint availableR; / 系统可用资源数int allocationWR; /M 个进程已经得到 N 类资源的资源量int needWR; /M 个进程还需要 N 类资源的资源量int requestR; /请求资源个数 RESOURCE1.3 算法

19、int i=0,j=0;char choice=Y;while(choice=Y|choice=y)i=-1;while(i=M)26山东科技大学学生课程设计coutendli;if(i=M) cout 进 程 号 不 存 在 ， 重 新 输 入!endl;cout 请输入进程 i 申请各类资源的数量 :endl;for (j=0;jN;j+)cout 资源jrequestj;if(requestjneedij)coutendl 进 程i 申请 的资源数 大于 进程 i 还需要j 类资源的数量 !; 鹅娅尽損鹌惨歷茏鴛賴。cout 若继续执行系统将处于不安全状态 !availablej)cou

20、tendl 进程 i 申请的资源数大于系统 可用j 类资源的数量 !;籟丛妈羥为贍偾蛏练淨。cout 继续执行系统将处于不安全状态 !endl;choice=N;break;if(choice=Y|choice=y)distribute(i);if(check()restore(i);print();28山东科技大学学生课程设计elseprint();elsecoutendl;coutchoice;2. check 模块2.1 功能检查资源分配后系统是否处于安全状态。2.2 数据结构Typedef struct RESOURCE int availableR; / 系统可用资源数int all

21、ocationWR; /M 个进程已经得到 N 类资源的资源量int needWR; /M 个进程还需要 N 类资源的资源量int requestR; /请求资源个数29山东科技大学学生课程设计 RESOURCE2.3 算法int workR,finishW;int i,j;for(j=0;jN;j+) workj=availablej;for(i=0;iM;i+) finishi=FALSE;for(i=0;iM;i+)for(j=0;jN;j+)if(finishi=FALSE&needij=workj)workj=worki+allocationij;finishi=TRUE;30山东科

22、技大学学生课程设计for(i=0;iM;i+)if(finishi=FALSE)coutendl;cout 系统不安全 ! 资源申请失败 !endl;coutendl;return 1;elsecout 系统安全，分配成功 !endl;return 0;四、运行结果及分析31山东科技大学学生课程设计32山东科技大学学生课程设计通过实验结果可知银行家算法中，当进程申请的资源大于声明所需的 最大资源或者大于系统当前可用的资源时，系统将处于不安全状态，资源 分配失败，从而防止了死锁的产生。 預頌圣鉉儐歲龈讶骅籴。五、总结通过该算法的模拟可知银行家算法是一种最有代表性的避免死锁的算 法。在避免死锁方法

23、中允许进程动态地申请资源，但系统在进行资源分配 之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全 状态，则分配，否则等待。为实现银行家算法，系统必须设置若干数据结 构。 渗釤呛俨匀谔鱉调硯錦。源代码：33山东科技大学学生课程设计#include #include #include #define FALSE 0 #define TRUE 1 #define W 10 #define R 10 int allresourceW; int maxWR; int availableR; int allocationWR; int needWR; int requestR; int M

24、 ; int N ;void print()int i,j;cout各种资源总量 :endl;34山东科技大学学生课程设计for (j=0;jN;j+)cout 资源j: allresourcejendl;cout目前各种资源可利用数量 :endl;for (j=0;jN;j+)cout 资源j: availablejendl;cout各进程还需要的资源数量 :endlendl;cout resourceA resourceB resourceCendl;铙誅卧泻噦圣骋贶頂廡。for (i=0;iM;i+)cout进程 i: ;for (j=0;jN;j+)coutneedij ;couten

25、dl;cout各进程已经得到的资源量 : endlendl;cout resourceA resourceB resourceCendl; 擁締凤袜备訊顎轮烂蔷。for (i=0;iM;i+)35山东科技大学学生课程设计cout进程 i:;for (j=0;jN;j+)coutallocationij coutendl;void distribute(int l)/ 分配资源int j;for (j=0;jN;j+)availablej=availablej-requestj; allocationlj=allocationlj+requestj; needlj=needlj-requestj

26、;void restore(int l)/ 恢复资源int j;36山东科技大学学生课程设计for (j=0;jN;j+)availablej=availablej+requestj; allocationlj=allocationlj-requestj; needlj=needlj+requestj;int check()int workR,finishW;int i,j;for(j=0;jN;j+) workj=availablej;for(i=0;iM;i+) finishi=FALSE;for(i=0;iM;i+)for(j=0;jN;j+)if(finishi=FALSE&needi

27、j=workj)37山东科技大学学生课程设计workj=worki+allocationij;finishi=TRUE;for(i=0;iM;i+)if(finishi=FALSE)coutendl;cout 系统不安全 ! 资源申请失败 !endl;coutendl;return 1;elsecout 系统安全，分配成功 !endl;return 0;38山东科技大学学生课程设计void bank()int i=0,j=0;char choice=Y;while(choice=Y|choice=y)i=-1;while(i=M)coutendli;if(i=M) cout 进程号不存在，重新

28、输入 !endl; cout 请输入进程 i 申请各类资源的数量 :endl;for (j=0;jN;j+)cout 资源jrequestj;if(requestjneedij)coutendl 进程 i 申请的资源数大于进程 i 还需 要j 类资源的数量 !; 贓熱俣阃歲匱阊邺镓騷。cout 若继续执行系统将处于不安全状态 !availablej)coutendl 进程 i 申请的资源数大于系统可用j 类资源的数量 !; 坛摶乡囂忏蒌鍥铃氈淚。cout 继续执行系统将处于不安全状态 !endl;choice=N;break;40山东科技大学学生课程设计if(choice=Y|choice=y

29、)distribute(i);if(check()restore(i);print();elseprint();elseY/N coutendl;coutchoice;int main()41山东科技大学学生课程设计int i=0,j=0,p;coutt 银行家算法演示 coutendlM;coutN; cout请输入各类资源总数 :; for(i=0;iallresourcei;cout输入各进程所需要的各类资源的最大数量 for (i=0;iM;i+)for (j=0;jN;j+)doendl;:maxij;42山东科技大学学生课程设计if (maxijallresourcej)coute

30、ndl 占有资源超过了声明的该资源总数 ,请重新输入 allresourcej);cout输入各进程已经占据的各类资源的数量 :endl;for (i=0;iM;i+)for (j=0;jallocationij;if (allocationijmaxij)coutendl占有资源超过了声明的最大资源 ,请重新输入 maxij);43山东科技大学学生课程设计for (j=0;jN;j+)p=allresourcej;for (i=0;iM;i+)p=p-allocationij; availablej=p;if(availablej0)availablej=0;for (i=0;iM;i+)f

31、or(j=0;jN;j+)needij=maxij-allocationij;print();bank();44山东科技大学学生课程设计设计 3 磁盘调度算法一、设计目的1、通过对磁盘调度算法的实现， 了解磁盘调度的算法已经其寻道时间二、设计要求编程序实现下述磁盘调度算法 ,并求出每种算法的平均寻道长度1、先来先服务算法（ FCFS）2、最短寻道时间优先算法（ SSTF）3、扫描算法（ SCAN ）4、循环扫描算法（ CSCAN）三、设计说明1. FCFS 模块1.1 功能按先来先服务的策略输出磁盘请求序列，求平均寻道长度45山东科技大学学生课程设计1.2 数据结构1.3 算法void FCF

32、S(int cidao,int m)int now,sum=0,j,i,a;char str100;float ave;cout 磁盘请求序列为： for( i=0;im;i+)coutcidaoi ;46山东科技大学学生课程设计coutendl;coutstr;a=check(str);if(a=0)endl;cout 输入数据的类型错误 ,请重新输入！ goto B;elsenow=change(str,a);sum+=abs(cidao0-now);cout 磁盘扫描序列为： ;for( i=0;im;i+)coutcidaoi ;for(i=0,j=1;jm;i+,j+)47山东科技大

33、学学生课程设计sum+=abs(cidaoj-cidaoi); ave=(float)(sum)/(float)(m);coutendl;cout平均寻道长度： aveendl;2. SSTF 模块2.1 功能根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均 寻道长度，输出移动的平均磁道数。2.2 数据结构48山东科技大学学生课程设计2.3 算法void SSTF(int cidao,int m)int k=1,now,l,r,i,j,sum=0,a;char str100;float ave;cidao=order(cidao,m);coutstr; a=check(str);if(

34、a=0)endl;cout 输入数据的类型错误 ,请重新输入！ goto C;else now=change(str,a); if(cidaom-1=now)49山东科技大学学生课程设计cout=0;i-) coutcidaoi=now)cout磁盘扫描序列为：for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1)cout 磁盘扫描序列为： ;while(cidaok=0)&(rm)if(now-cidaol)=(cidaor-now) coutcidaol ; sum+=now-cidaol; now=cidaol;l=l-1;elsecoutcidaor ;

35、 sum+=cidaor-now; now=cidaor;r=r+1;51山东科技大学学生课程设计if(l=-1)for(j=r;jm;j+)coutcidaoj=0;j-)coutcidaoj ;sum+=cidaom-1-cidao0;ave=(float)(sum)/(float)(m);coutendl;52山东科技大学学生课程设计cout 平均寻道长度： aveendl;3. SCAN 模块3.1 功能选择移动臂的移动方向，根据当前磁道在已排的序列中的位置， 选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。 變黲癟報伥铉锚鈰赘。3.2 数据结构53山东科技大学学生课程设计3.

36、3 算法void SCAN(int cidao,int m)int k=1,now,l,r,d,i,j,sum=0,a;char str100;float ave;cidao=order(cidao,m);coutstr;a=check(str);if(a=0)endl;cout 输入数据的类型错误 ,请重新输入！ goto D;elsenow=change(str,a);if(cidaom-1=now)54山东科技大学学生课程设计cout=0;i-)coutcidaoi=now)cout磁盘扫描序列为： ;for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1)

37、 while(cidaoknow)k+;l=k-1;55山东科技大学学生课程设计r=k;(1 表示向外 ，0coutd;if(d=0)cout=0;j-)coutcidaoj ;for(j=r;jm;j+)coutcidaoj ;sum=now-2*cidao0+cidaom-1;else56山东科技大学学生课程设计cout 磁盘扫描序列为： ;for(j=r;jm;j+)coutcidaoj=0;j-)coutcidaoj ; sum=-now-cidao0+2*cidaom-1;ave=(float)(sum)/(float)(m);coutendl; cout平均寻道长度： aveend

38、l;4. CSCAN模块4.1 功能规定移动臂单向反复的从内向外移动，根据当前磁道在已排的序57山东科技大学学生课程设计列中的位置，选择扫描的顺序，求出平均寻道长度，输出移动的 平均磁道数。 買鲷鴯譖昙膚遙闫撷凄。4.2 数据结构4.3 算法void CSCAN(int cidao,int m)int k=1,now,l,r,i,j,sum=0,a;char str100;float ave;58山东科技大学学生课程设计cidao=order(cidao,m);coutstr;a=check(str);if(a=0)endl;cout 输入数据的类型错误 ,请重新输入！goto E;elsen

39、ow=change(str,a);if(cidaom-1=now)cout 磁盘扫描序列为： ;for(i=0;im;i+)coutcidaoi=now)59山东科技大学学生课程设计cout 磁盘扫描序列为： ;for(i=0;im;i+)coutcidaoicidao0&nowcidaom-1)cout 磁盘扫描序列为： ;while(cidaoknow)k+;l=k-1;r=k;for(j=r;jm;j+)coutcidaoj ;for(j=0;jr;j+)60山东科技大学学生课程设计coutcidaoj ;sum=2*cidaom-1+cidaol-now-2*cidao0;ave=(float)(sum)/(float)(m);coutendl;cout 平均寻道长度： aveendl;四、运行结果及分析61山东科技大学学生课程设计从实验结果可知各种磁盘调度的磁道顺序以及寻道时间，由此可以比62山东科技大学学生课程设计较出各种调度算法的优缺点。五、总结通过改程序对操作系统的基础知识了解得更透彻了，同时对磁盘调度 的四种算法先来先服务算法 （