进程调度 作业调度 主存空间的分配与回收 文件系统.doc

操作系统实验报告学 院 专 业 班 级 学 号 姓 名 指导教师 （2010年12 月） 计算机 学院 专业 班 学号： 姓名： 协作者：_ 教师评定： 考勤情况程序运行情况程序质量实验技能创新精神实验报告设计文档实验_一_题目_ 进程调度_ _ 第 8 周星期三 实验_二_题目_ 作业调度_ 第 9 周星期四 实验_三(综合性)题目_主存空间的分配与回收_ 第 10 周星期四实验_四 _题目_ 文件系统 _第 15 周星期四实验平台：1、 计算机及操作系统：Microsoft Windows XP Professional (SP3)2、 编程环境： VC+ 6.0源程序名和可执行程序名：实验一： 源文件： 三级反馈队列调度算法.cpp 可执行文件： 三级反馈队列调度算法.exe 实验二：源文件： 单道批处理系统作业调度.cpp 可执行文件：单道批处理系统作业调度.exe 实验三(综合性)：源文件： 主存空间分配和回收.cpp 可执行文件：主存空间分配和回收.exe 实验四：源文件： 文件系统.cpp 可执行文件： 文件系统.exe 学号： 姓名： 协作者：_实验_一_题目_ 进程调度_第 周星期_ _一、实验目的用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。二、实验内容和要求设计一个有 N个进程共行的进程调度程序。要求采用最高优先数优先算法，时间片轮转算法，多级队列调度算法这三种算法。 每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。 进程的运行时间以时间片为单位进行计算。 每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。 就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。 如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。 每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所有的进程都完成为止。三、实验主要仪器设备和材料实验环境 硬件环境：个人台式机 Microsoft Windows XP Professional (SP3) 软件环境：C语言编程环境，VC+ 6.0四、实验原理及设计方案1、实验原理（3）编写并调试一个模拟的进程调度程序，采用“多级反馈队列”调度算法对五个进程进行调度。 多级反馈队列调度算法的基本思想是：当一个新进程进入内存后,首先将它放入第一队列的末尾,按FCFS原则排队等待调度.当轮到该进程执行时,如它能在该时间片内完成,便可准备撤离系统;如果它在一个时间片结束时尚未完成,调度程序便将该进程转入第二队列的末尾,再同样地按FCFS原则等待调度执行，以此类推。1、设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。2、赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。3、当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片结束时尚未完成，将其转入第二队列末尾。4、当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。5、仅当时间片空闲时，才调度第二个队列中的进程。(1i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。2、 设计方案struct pcb char name10; /进程名 char state; /进程状态 w：等待 r：运行 int queue; /进程队列 1：2：3 int priority; / 数字越小优先级越高 int needtime; /需运行时间 int runtime; /已经运行时间 pcb *link; /进程队列下一指针*ready=NULL,*run;typedef struct pcb PCB;/分别设置三条就绪队列头指针和尾指针 PCB *First=NULL,*Second=NULL,*Third=NULL,*end1=NULL,*end2=NULL,*end3=NULL;/为三条就绪队列设置三个时间片：1：2：3int time3; 3、 程序流程图进程队列初始化Cpu调度进程进程i运行新进程插入？加入第一队列尾继续执行进程i进程i完成？第一级队列还有待运行进程吗？修改数据结构，继续运行下一进程YNYNY加入下一级队列尾时间片运行完N第二级队列还有待运行进程吗？第三级队列还有待运行进程吗？YNY进程调度结束N4、程序源代码65#include #include #include #define getpch(type) (type*)malloc(sizeof(type)#define NULL 0int time3; /为三条就绪队列设置三个时间片struct pcb char name10; /进程名 char state; /进程状态 int queue; /进程队列 int priority; / 数字越小优先级越高 int needtime; /需运行时间 int runtime; /已经运行时间 pcb *link;*ready=NULL,*run;typedef struct pcb PCB;/分别设置三条就绪队列头指针和尾指针 PCB *First=NULL,*Second=NULL,*Third=NULL,*end1=NULL,*end2=NULL,*end3=NULL;void sort(PCB *p) /设置3条就绪队列排序函数switch(p-queue)case 1:if(First=NULL) /First记录第一条队列头指针First=p;end1=p;p-link=NULL; elseend1-link=p;end1=p;p-link=NULL; p-state=w; break; case 2: if(Second=NULL) /Second记录第二条队列头指针 Second=p; end2=p; p-state=w; p-link=NULL; else end2-link=p; end2=p; p-link=NULL; p-state=w; break; case 3:if(Third=NULL) /Third记录第三条队列头指针Third=p;end3=p;p-link=NULL;elseend3-link=p;end3=p;p-link=NULL;p-state=w;break; default: break;void input()PCB *p;int i,num;system(cls);printf(nttt n);printf(n 请输入初始进程个数:); scanf(%d,&num); for(i=0;iname); getchar(); printf(n 输入进程优先级:); scanf(%d,&p-priority); printf(n 输入进程运行时间:); scanf(%d,&p-needtime); printf(n); p-queue=1; /初始进程队列设置为1 p-runtime=0; /初始进程运行时间设置为0 p-state=w; /初始进程状态设置为w p-link=NULL; sort(p);void disp(PCB * pr)printf(n 进程名 优先级 状态 列数 完成时间 运行时间 n);printf(|%st,pr-name);printf(|%dt,pr-priority); printf(|%ct,pr-state); printf(|%dt,pr-queue); printf(|%dt,pr-needtime); printf(|%dt,pr-runtime); printf(n);void check()/进程查看函数PCB *pr; printf(n*当前正在运行的进程【%s】,run-name); disp(run); printf(n*第一队列进程*);pr=First; while(pr!=NULL)disp(pr); pr=pr-link; printf(n*第二队列进程*);pr=Second; while(pr!=NULL) disp(pr); pr=pr-link; printf(n*第三队列进程*);pr=Third; while(pr!=NULL) disp(pr); pr=pr-link;void runing() /三个队伍的进程的执行函数 if(First!=NULL) /第一队列不空 ready=First;First=First-link;ready-state=r; else if(Second!=NULL) /第二队列不空ready=Second;Second=Second-link;ready-state=r; else if(Third!=NULL) /第三队列不空ready=Third;Third=Third-link;ready-state=r; elseready=NULL;run=ready; if(run!=NULL) /当前有进程运行check(); /显示运行及等待队列的状况 run-runtime=run-runtime+timerun-queue-1; if(run-runtime=run-needtime) /如果当前进程在时间片内运行完毕则销毁 printf(n进程【%s】已经完成n,run-name); else /否则加入下一队列末尾 run-queue+=1; sort(run);void main()PCB *add;int h=0;char ch,temp;input();time0=1; /3级队列时间片分别设置如下time1=2;time2=3; while(First|Second|Third) ch=getchar(); h+; printf(n*); printf(n本次进程调度轮次-%d n,h); printf(*n); runing(); printf(n当前是否有新进程加入(y/n)?); /进程插入temp=getchar(); if(temp=y|temp=Y) add=getpch(PCB); printf(n 输入进程名:); scanf(%s,add-name); getchar(); printf(n 输入进程优先级:); scanf(%d,&add-priority); printf(n 输入进程运行时间:); scanf(%d,&add-needtime); printf(n); add-queue=2; /进程队列设置为2 add-runtime=0; /进程运行时间设置为0 add-state=w; /进程状态设置为w sort(add); ch=getchar(); printf(n*n);printf(*整个进程运行完毕*n); printf(*n);getchar();五、实验结果及分析运行三及队列调度算法.exe,出现进程初始化界面，输入初始进程数目，接着必须按提示输入所有初始化进程，如下图所示：进程初始化完毕，按任意健运行第一轮调度，下图可看见三条队列运行显示情况，每一次运行完毕，都会出现新进程假如提示，输入y则发生进程进程抢占，按照提示输入新进程信息则自动加入第一列队尾，第二第三队列暂时空：第二轮进程调度结果，新进程55555已经加入第一列队尾，该轮次执行顺序如下图，第二队列有上轮未运行完毕进程11111： 第三轮次调度结果，该时间片33333正在运行，没有进程运行完毕，没有新进程抢占，下图是第一第二队列情况：以此类推，第六轮次调度，第一队列进程已经运行完毕，程序调度下一队列进程继续运行：第八轮次，进程33333已经完成并销毁，当前33333正在运行，第一队列进程已经运行完毕：以此类推，当进程调度至第11轮次时，全部进程运行完毕并销毁，三条队列全部微孔，整个进程调度完毕：六、调试总结及心得体会 第一次实验由于教材有类似的程序源码，所以相对来说还是比较简单，我只需要更改其中一部分算法就可以实现多级队列调度算法，但是我在实现过程中还是学到不少东西，重新温习了一遍C语言，特别是指针和结构体部分，完成一个功能模拟首先必须理解其中的算法，然后设计出良好的数据结构是完成这次实验的关键，在整个实验流程中，对于不同功能模块指针的设计和使用非常重要，必须确定那些指针是全局指针，运行时需不需要时常改变，哪些指针必须设置为局部作为第三者使用。这对后期调BUG给与了我很大的方便 。七、思考题1、分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结它们的适用范围答：“最高优先数优先”是根据进程的优先级数决定是否运行的，此算法用于批处理系统中，也作为多种操作系统中的进程调度算法，还可用于实时系统中。“轮转法”相当于先来先服务高度算法，每次都是调度后备作业中的第一个，这个算法比较有利于长进程，不利于短进程。学号： 姓名： 协作者：_实验_二_题目_ 作业调度_ 第 周星期 一、实验目的本实验要求学生模拟作业调度的实现，用高级语言编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解。二、实验内容和要求1、为单道批处理系统设计一个作业调度程序(1)、编写并调试一个单道处理系统的作业调度模拟程序。(2)、作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 先来先服务就是每次调度都是从后备作业队列中，选择一个最先进入该队列的作业，将它调入内存，为它分配资源、创建进程，然后放入就绪队列，投入运行，一直运行到完成或发生某事件而阻塞后，才放弃处理。最短作业优先是从后备队列中选择一个估计运行时间最短的作业，将它调入内存运行并一直执行到完成，或发生某事件而被阻塞放弃处理时，再重新调度。 响应比高者优先是通过计算出作业的响应比，按响应比高而进行调度的，其计算公式是：优先权（等待时间+要求服务时间）/要求服务时间.(3)、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU时限等因素。(4)、每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。(5)、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间，并比较各种算法的优缺点。三、实验主要仪器设备和材料实验环境 硬件环境：个人台式机 Microsoft Windows XP Professional (SP3) 软件环境：C语言编程环境，VC+ 6.0四、实验原理及设计方案1、实验原理 先来先服务算法：是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业，那么顺序挑选后面的作业。 FCFS算法简单易行，但性能却不大好。短作业优先算法：总是按照作业要求运行时间来选择作业，每次挑选要求作业执行时间短且资源要求能满足的作业优先分派处理机，通常后来的短作业不抢先正在执行的作业。SJF改善平均周转时间和平均带权周转时间，缩短作业的等待时间 ,提高系统的吞吐量,但对长作业非常不利。响应比高者优先算法：最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T 其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加。2、 设计方案struct source /*定义资源需求结构*/char memery5; /*主存需求*/int machine; /*磁带机数量*/;struct jcb /* 定义作业控制块PCB */ char name10; char state; /* 状态 */ double super; /* 响应比优先权 */ int ntime; /* 需要运行时间 */ int rtime; /* 开始运行时间 */int ptime; /*提交时间*/int ftime; /*完成时间*/ source *needsources; /*资源需求链*/ struct jcb* link; /* 下一个作业控制块的地址 */*ready=NULL,*run,*p;3、 程序流程图 开始初始化作业JCB和资源source，所有作业按照先后顺序排列，作业提交时间为系统默认时间p-ptime=Systemtim，作业完成时间p-ftime=0作业调度算法？321响应比高优先算法短作业优先算法先来先服务算法用响应比高优先算法，先计算所有作业高响应比，调度队响应比最高的首作业投入运行，更改作业状态为R，记录作业开始运行时间和完成时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间用短作业算法调度需求时间最短的作业投入运行，更改作业状态为R，记住作业开始运行时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间用先来先服务算法调度队首作业投入运行，更改作业状态为R，记住作业开始运行时间，修改下一作业指针等，计算运行作业i的完成时刻，周转时间和带权周转时间Y结束计算并打印这组作业的平均周转时间及带权平均周转时间等待队列空？作业运行完毕？释放该作业占用资源YNN4、程序源代码#include #include #include #define getpch(type) (type*)malloc(sizeof(type) int Select;int Systemtime = 0; /*系统初始时间*/int JCBnum = 0; /*总作业数*/int JCBtime = 0; /*总周转时间*/double JCBtotaltime =0; /*总带权周转时间*/struct source /*定义资源需求结构*/char memery5; /*主存需求*/int machine; /*磁带机数量*/;struct jcb /* 定义作业控制块PCB */ char name10; char state; /* 状态 */ double super; /* 响应比优先权 */ int ntime; /* 需要运行时间 */ int rtime; /* 开始运行时间 */int ptime; /*提交时间*/int ftime; /*完成时间*/ source *needsources; /*资源需求链*/ struct jcb* link; /* 下一个作业控制块的地址 */*ready=NULL,*run,*p; typedef struct jcb JCB;typedef struct source SOURCE;void display() int c; do system(cls); printf(ntt n); printf(ntt*tt); printf(nttt 1.先来先服务算法.); printf(nttt 2.最短作业优先算法.); printf(nttt 3.响应比高者优先算法); printf(nttt 0.退出程序.); printf(ntt*ttn); printf(ttt请输入选择所要操作(0-3):); scanf(%d,&c); system(cls); while(c3) ; switch(c) case 0: exit(0); break; case 1: Select=1; break; case 2: Select=2; break; case 3: Select=3; break; default: break; void sort() /* 建立对进程进行优先级排列函数*/ JCB *first, *second,*temp; int insert=0; switch(Select)case 1: /*先来先去服务算法*/if(ready=NULL) /*队首空插入队首*/p-link=ready;ready=p;else /*否则插入队尾*/first=ready;second=ready-link;while(second!=NULL)first=first-link;second=second-link;first-link=p;break;case 2: /*最短作业优先算法*/ if(ready=NULL)|(p-ntime)ntime) /*队首*/ p-link=ready; ready=p; else /* 往后搜索适当的位置插入*/ first=ready; second=first-link; while(second!=NULL) /*插入队伍中间*/ if(p-ntime)ntime) p-link=second; first-link=p; second=NULL; insert=1; else first=first-link; second=second-link; if(insert=0) first-link=p; /* 插入队尾*/ break;case 3: /*响应比高者优先算法*/ /*响应比=(等待时间+需求时间)/需求时间*/ temp=ready;p-super=(double)(Systemtime-p-ptime+p-ntime)/(double)(p-ntime); /*计算插入队列作业优先权*/ while(temp) /*计算就绪队列作业优先权*/ temp-super=(double)(Systemtime-temp-ptime+temp-ntime)/(double)(temp-ntime);temp=temp-link; /*响应比越大优先权越高*/ if(ready=NULL)|(p-super)(ready-ntime) /*队首*/ p-link=ready; ready=p; else /* 往后搜索适当的位置插入*/ first=ready; second=first-link; while(second!=NULL) /*插入队伍中间*/ if(p-super)(second-super) p-link=second; first-link=p; second=NULL; insert=1; else first=first-link; second=second-link; if(insert=0) first-link=p; /* 插入队尾*/ break; default:break; void input() /* 建立作业输入函数*/ int i,num;SOURCE *q; printf(nn请输入作业数目:); scanf(%d,&num); JCBnum+=num; /*总作业数*/ for(i=0;iname); getchar(); printf(请输入作业需要运行时间:);scanf(%d,&p-ntime); getchar(); printf(请输入作业主存资源需求:); scanf(%s,q-memery); getchar(); printf(请输入作业磁带机数量需求:); scanf(%d,&q-machine);p-needsources=q;p-ptime=Systemtime; /*作业提交时间为系统默认时间*/p-super=0; p-ftime=0; /*作业完成时间*/ p-state=W; p-link=NULL;sort(); void disp(JCB *pr) /*建立作业显示函数*/ printf(n 作业名 提交时间 需求时间 响应比 即时状态 主存需求 磁带机数量 n); printf( %st,pr-name); printf( %dt,pr-ptime); printf( %dt,pr-ntime); printf( %.2ft,pr-super); printf( %ct,pr-state); printf( %st,pr-needsources-memery); printf( %dt,pr-needsources-machine); printf( n); void check() /* 建立作业查看函数 */ JCB* pr; printf(n *当前正在运行的作业*); /*显示当前运行作业*/ disp(run); pr=ready; printf(n *当前就绪队列状态*); /*显示就绪队列状态*/ while(pr!=NULL) disp(pr); pr=pr-link; void destroy() /*建立作业撤销函数)*/ JCB *pr=run;run-ftime=Systemtime; printf(ntt 【作业 %s 已完成.】n,run-name); printf(n 开始时间 完成时间 周转时间 带权周转时间 释放主存资源 释放磁带机数量n); printf( %dt,run-rtime); printf( %dt,run-ftime); printf( %dt,Systemtime-run-ptime); printf( %ft,(double)(Systemtime-run-ptime)/(double)run-ntime); printf( %st,run-needsources-memery);printf( %dt,run-needsources-machine); printf( n); JCBtime += Systemtime-run-ptime; /*更新总周转时间*/ JCBtotaltime += JCBtime/(double)run-ntime; /*更新总带权周转时间*/ run=run-link;free(pr);pr=NULL; void running() /* 建立作业运行函数*/ run-rtime=Systemtime; /*作业开始时间为系统当前时间*/Systemtime += run-ntime; /*更新系统时间*/ destroy(); void main() /*主函数*/ int h=0; char ch; display(); input();Systemtime=0; /*初始系统时间*/ while(ready!=NULL) ch=getchar(); h+; printf(n 【作业调度轮次:%d】 n,h); run=ready; ready=ready-link; run-link=NULL; run-state=R; check(); running(); printf(ntt 按任一键继续.); ch=getchar(); printf(nnttt n); printf(ntt 作业数量 平均周转时间 带权周转时间 n); printf(tt %dt,JCBnum);printf( %ft,(doubl