进程调度算法

1、实验项目名称： 进程调度算法 一、实验目的编程实现FIFO和SPF调度算法二、实验内容1、综合运用相关知识，仿真实现进程调度算法（1）操作系统基本原理（2）软件工程中涉及软件分析、设计、实现和测试能力（3）数据结构与算法中的栈、队列、链表等的遍历方法（4）C+或java语言编程 （5）Linux系统的安装、配置与使用2、学习先来先服务算法、最短作业优先算法。3、计算出不同时间片是多进程调度的完成时间、周转时间。给定进程A,B,C,D,E，每个进程的运转时间4,3,4,2,4,每个进程的到达时间1,2,3,4,5;（1）进行时间片轮转调度算法的模拟；（2）时间片q=1，轮转调度算法的模拟并计算周

2、转时间、平均周转时间、带权周转时间。（3）时间片q=4，轮转调度算法的模拟并计算周转时间、平均周转时间、带权周转时间。4、按照一定的算法选取进程；5个进程各自运行所需要的时间及存储空间，即A、B、C、D、E，它们到达的时间分别是0、1、2、3、4，所要求的服务时间分别是4、3、5、2 、4。（1）进行进程调度算法的模拟；（2）按的原则进行调度；根据运行情况计算周转时间、平均周转时间、带权周转时间。（3）按的原则进行调度；根据运行情况计算周转时间、平均周转时间、带权周转时间。5、画出调度图或表。三、实验用设备仪器及材料计算机，实验室电力、实验报告用纸、电脑键盘、鼠标等。四、实验原理及接线1. 先

3、来先服务算法先来先服务(FCFS: first come first service)总是把当前处于就绪队列之首的那个进程调度到运行状态。也就说，它只考虑进程进入就绪队列的先后，而不考虑它的下一个CPU周期的长短及其他因素。2. 最短作业优先算法该算法从就绪队列中选出下一个“CPU执行期最短”的进程，为之分配处理机五、实验步骤1.程序流图（1）先来先服务算法（2）最短作业优先算法2.程序代码（1）先来先服务算法#include #include #include #include using namespace std;struct fcfs char name10; float daodat

4、ime; float fuwutime; float kaishitime; float wanchengtime; float zhouzhuangtime; float daiquantime;void input(fcfs *p, int N) int i; for(i = 0; i = N - 1; i+) scanf(%s %f %f, , &pi.daodatime, &pi.fuwutime); pi.kaishitime = 0; pi.wanchengtime = 0; pi.zhouzhuangtime = 0; pi.daiquantime = 0; voi

5、d print(fcfs *p, int N) int k; printf(进程 到达时间 服务时间 开始时间 完成时间 周转时间 带权周转时间n); for(k = 0; k N; k+) printf(%4s ,); printf(%8.0f ,pk.daodatime); printf(%8.0f ,pk.fuwutime); printf(%8.0f ,pk.kaishitime); printf(%8.0f ,pk.wanchengtime); printf(%8.0f ,pk.zhouzhuangtime); printf(%12.2lf,pk.daiquantime

6、); printf(n); void sort(fcfs *p, int N) int i,j; for(i = 1; i = 0 & t.daodatime pj.daodatime; j-) pj+1 = pj; pj+1 = t; void run(fcfs *p, int N) int k; for(k = 0; k N; k+) if(k = 0) pk.kaishitime = pk.daodatime; pk.wanchengtime = pk.daodatime + pk.fuwutime; else pk.kaishitime = pk - 1.wanchengtime; p

7、k.wanchengtime = pk.kaishitime + pk.fuwutime; for(k = 0; k N; k+) pk.zhouzhuangtime = pk.wanchengtime - pk.daodatime; pk.daiquantime = pk.zhouzhuangtime/pk.fuwutime; void FCFS_MAIN() int N; printf(请输入进程的数量:n); scanf(%d,&N); fcfs *p = new fcfsN; input(p, N); sort(p, N); run(p, N); print(p, N); delete

8、 p;int main() FCFS_MAIN(); return 0;（2）最短作业优先算法#include #include #define INF .0struct PCB char id10; double reachTime; double needTime; double startTime; double finishTime; double cTime; double wcTime; char state;int findNext( struct PCB arr, int length, double lastTime ) int i, p, q; double minNeed

9、Time, minReachTime; p = q = -1; minNeedTime = minReachTime = INF; for( i = 0; i length; i+ ) if( arri.state=R ) if( arri.reachTime=lastTime & arri.needTimelastTime & arri.reachTimeminReachTime ) q = i; minReachTime = arri.reachTime; if( p != -1 ) return p; return q;int main() int num, i; double last

10、Time; struct PCB *arr; printf( 请输入进程数: ); scanf( %d, &num ); arr = (struct PCB*)malloc(num*sizeof(struct PCB); lastTime = INF; for( i = 0; i arri.reachTime ) lastTime = arri.reachTime; double sum1=0.0, sum2=0.0; for( i = 0; i num; i+ ) int p = findNext( arr, num, lastTime ); if( arrp.reachTime=lastT

11、ime ) arrp.startTime = lastTime; else arrp.startTime = arrp.reachTime; arrp.finishTime = arrp.startTime + arrp.needTime; arrp.cTime = arrp.finishTime - arrp.reachTime; arrp.wcTime = arrp.cTime/arrp.needTime; arrp.state = F; sum1 += arrp.cTime; sum2 += arrp.wcTime; lastTime = arrp.finishTime; printf( n进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间n ); for( i = 0; i num; i+ ) printf( %4s %8.0lf %8.0lf , arri.id, arri.rea