操作系统 进程调度算法程序设计

华北科技学院计算机系综合性实验报告PAGE 第7页华北科技学院计算机系综合性实验实验报告课程名称操作系统B实验学期2011至2012学年第2学期学生所在系部基础部年级09级专业班级计算B091班学生姓名张成林学号200909014101任课教师实验成绩计算机系制

《操作系统B》课程综合性实验报告开课实验室：基础六机房2012年6月7日实验题目进程调度算法程序设计一、实验目的通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。二、设备与环境1.硬件设备：PC机一台2.软件环境：安装Windows操作系统或者Linux操作系统，并安装相关的程序开发环境，如C\C++\Java等编程语言环境。三、实验内容（1）用C语言（或其它语言，如Java）实现对N个进程采用短进程优先的算法的调度。（2）编写SPF算法：.每个用来标识进程的进程控制块PCB可用结构来描述，包括以下字段：进程（PRO_ID，arrive_time，sum_time，flag）每个进程需要赋予进程ID、进程到达时间、进程需要运行的总时间的属性；（3）调试无误后运行；（4）输入需要排序的进程的相关参数；（5）查看执行结果，根据执行结果判断实验是否成功；四、实验结果及分析1.实验代码#include"stdafx.h"#include"stdio.h"#definen5#definenum5#definemax65535typedefstructpro//结构体pro{ intPRO_ID;//进程号 intarrive_time;//进程到达时间 intsum_time;//进程完成时间 intflag;}Pro;//整数排序intpaixu(inttemp[]){ inti,j,tem=0; for(i=1;i<num;i++) { intlastX=1; for(j=0;j<num-i;j++) { if(temp[j]>temp[j+1])//按从小到大排序 { tem=temp[j]; temp[j]=temp[j+1]; temp[j+1]=tem; lastX=0; } } if(lastX==1)break; } returntemp[0];}//进程排序Propaixu(Prop[])//定义结构体的排序函数{ inti,j; Protemp={0}; Pros[num]; for(i=0;i<num;i++){ s[i]=p[i]; } for(i=1;i<num;i++) { intlastX=1; for(j=0;j<num-i;j++) { if(s[j].sum_time>s[j+1].sum_time) { temp=s[j]; s[j]=s[j+1]; s[j+1]=temp; lastX=0; } } if(lastX==1)break; } returns[0];}voidSPF(intp){ if(n>0) { inti,j,k,l,tc=0; Proseq[n]; Protemp_seq[n]; printf("短进程优先调度算法SPF\n"); printf("请依次输入5个进程的进程号、到达时间和执行时间\n"); printf("成员变量用逗号隔开；进程间用回车隔开\n"); for(i=0;i<n;i++){ scanf("%d,%d,%d",&seq[i].PRO_ID,&seq[i].arrive_time,&seq[i].sum_time); } printf("调度顺序是：\n"); //初始化tc inttemp[num];//定义中间变量 for(i=0;i<num;i++) { temp[i]=seq[i].arrive_time;//将每个进程的到达时间赋给temp[i] } tc=paixu(temp);//tc是断点,将进程中服务时间最短的赋给tc //flag表示对应i的pro的队列情况 //-1表示未进入过队列，0表示在队列中，1表示被清除了 for(i=0;i<n;i++){ seq[i].flag=-1;//将所有进程定义为未进入过 }for(i=0;i<n;i++){//选第一次执行的进程 for(j=0;j<n;j++){ if(seq[j].flag!=1&&seq[j].arrive_time<=tc){ seq[j].flag=0;//将满足条件的进程定义为0 } } for(j=0;j<n;j++){//其他不满足条件的进程，将其执行时间赋为最大值 temp_seq[j]=seq[j]; if(seq[j].flag!=0){ temp_seq[j].sum_time=max; } } l=paixu(temp_seq).PRO_ID;//利用结构体调用最小进程的id for(j=0;j<n;j++){ if(l==seq[j].PRO_ID){ k=j; } } tc=tc+paixu(temp_seq).sum_time;//更新tc seq[k].flag=1; printf("%d",l); } printf("\n"); }}voidmain(){ SPF(n);}2.实验结果如下图3.实验结果分析调度顺序为14253分析可知：短进程优先调度算法先由各进程的到达时间进行排序，然后对后进入系统的进程和系统中等待执行的进程进行计算、比较以服务时间由小到大排序，并按此顺序进行调度，最后实现算法调度，具体设计思想如下：进程（PRO_ID，arrive_time，sum_time，flag）(1)比较停顿时间点，小于等于当前停顿时间点tc的到达时间点seq[i].arrive_time的进程seq[i]的PRO_ID加入到队列中；(2)在现有更新后的队列temp_seq中，用paixu函数选出最短执行时间的进程的PRO_ID；(3)选进程（算法核心L=paixu（inttemp[]）），更新下一个停顿时间点tc就是当前停顿时间点tc+L的执行时间sum_time；(4)将已经执行过的进程X踢出队列。seq[i].flag，-1表示未进入过队列，0表示在队列中，1表示被踢了；设当前时间点为tc，对pro.arr<=tc且seq[i].flag！=1的seq[i]，将seq[i].flag标记为0；创建临时变量temp_seq[]=seq[];对所有flag[i]==0的temp_seq[i]，bubble(temp_seq)，返回的是Pro进程类型。将tc更新，tc==tc+paixu(temp_seq).sum_time;找出该paixu(temp_seq)对应的原来seq[i]，标记为1（这步最容易错，注意下标和PRO_ID并不是一回事）。怎么选第一个tc：设tc=0；如果出现最小的pro.arr不是0的话，那么需要初始化：paixuseq[i].arrive_timetc=min{seq[i].arrive_time}4.实验心得通过本次综合实验，我熟悉了短进程优先调度算法的原理，代码实现了其算法和功能，收获很大。开始设计之时完全没头绪，对与理论学习不够扎实的我深感“书到用时方恨少”只好再把书上介绍的相关知识重新阅读一遍，对知识进行了全面而系统的梳理，遇到难处首先是苦思冥想寻求方法，再向同学请教，终于熟练掌握了基本理论知识，而且领悟了诸多平时学习难以理解掌握的的较难的知识，如短进程算法的缺点、如何改正以及动态调度算法的优缺点和算法思想。这些是我在上课时我都似懂非懂的。我还学会了如何思