《操作系统》课程设计报告-多道批处理调度的模拟.doc

课 程 设 计 课程名称 操作系统 _ 题目名称 多道批处理调度的模拟学生学院 计算机学院 专业班级 2007 级计科（5）班 2010年 07月 03日广东工业大学课程设计任务书一、课程设计的内容本课程设计要求模拟实现一个的多道批处理系统的两级调度。通过具体的作业调度、进程调度、内存分配等功能的实现，加深对多道批处理系统的两级调度模型和实现过程的理解。 二、课程设计的要求与数据1 要求作业从进入系统到最后完成，要经历两级调度：作业调度和进程调度。作业调度是高级调度，它的主要功能是根据一定的算法，从输入井中选中若干个作业，分配必要的资源，如主存、外设等，为它们建立初始状态为就绪的作业进程。进程调度是低级调度，它的主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。2 假定某系统可供用户使用的主存空间共100kb，并有4台磁带机。主存分配采用可变分区分配方式且主存中信息不允许移动，对磁带机采用静态分配策略，作业调度分别采用先来先服务算法和最小作业优先算法，进程调度采用先来先服务和最短进程优先算法。（能增加实现更多的调度算法则可以获得加分）。3 假定“预输入”程序已经把一批作业的信息存放在输入井了，并为它们建立了相应作业表。测试数据如下：作业 到达时间 估计运行时间 内存需要 磁带机需要job1 10：00 25分钟 15k 2台job2 10：20 30分钟 60k 1台job3 10：30 10分钟 50k 3台job4 10：35 20分钟 10k 2台job5 10：40 15分钟 30k 2台4 分别在不同算法控制下运行设计的程序，依次显示被选中作业、内存空闲区和磁带机的情况。比较不同算法作业的选中次序及作业平均周转时间。5 选用程序设计语言：c、c等。三、课程设计应完成的工作1充分理解设计的任务，完成设计的基本要求。然后根据自己的基础和能力选择不同难度的算法和实现方式，以取得更高的分数。 2. 独立完成系统的分析、设计、编码、测试工作。3完成设计报告的撰写。4以光盘（以班为单位刻录）方式提交已调试通过的完整的相关源程序和能够运行的执行文件；提交“课程设计报告”的书面和电子两种版本。四、课程设计进程安排序号设计各阶段内容地点起止日期1查阅资料、分析题目、概要设计分散周一2详细设计、编码分散周二3调试实验室周三4撰写设计报告分散周四5运行、验收实验室周五五、应收集的资料及主要参考文献1 计算机操作系统， 汤小丹等 ，西安电子科技大学出版社2 操作系统实验指导书，傅秀芬，广东工业大学（自编）3 计算机操作系统教程 ( 第二版 )， 张尧学、 史美林，清华大学出版社4 现代操作系统，a.s.tanenbaum 著，陈向群等译机械工业出版社发出任务书日期：2010年6月27日 指导教师签名：林穗计划完成日期： 2010年7月3日 基层教学单位责任人签章：傅秀芬一 设计背景本次课程设计的目的是模拟实现一个多道批处理系统的两级调度。在这之前，我们的操作系统课程已经做过了四次实验，分别是进程调度，作业调度，主存空间的分配和回收，文件系统。而此次多道批处理系统的两级调度将在采用前三次实验（即进程调度，作业调度，主存空间的分配和回收）成果的基础上，对他们进行整合，完成一个完整的模拟多道批处理系统两级调度的系统程序。本课程设计将按要求规定的步骤进行：设计背景（查询资料和分析题目），概要设计，详细设计，编码，调试和测试，总结和撰写报告。二 概要设计1.要求作业从进入系统到最后完成，要经历两级调度：作业调度和进程调度。作业调度是高级调度，它的主要功能是根据一定的算法，从输入井中选中若干个作业，分配必要的资源，如主存、外设等，为它们建立初始状态为就绪的作业进程。进程调度是低级调度，它的主要功能是根据一定的算法将cpu分派给就绪队列中的一个进程。2假定“预输入”程序已经把一批作业的信息存放在输入井了，并为它们建立了相应作业表。测试数据如下：作业 到达时间 估计运行时间 内存需要 磁带机需要job1 10：00 25分钟 15k 2台job2 10：20 30分钟 60k 1台job3 10：30 10分钟 50k 3台job4 10：35 20分钟 10k 2台job5 10：40 15分钟 30k 2台3使用visual c+设计如下各功能界面。放在输入井的作业列表：内存分配的情况：已经进入内存并存在的作业：已经完成的作业列表：程序设置区：包括开始时间，磁带机和内存初始值，调度算法的选择作业添加区，可以输入作业及它的各个参数。程序运行状态区。如开始，暂停，继续和重置等个人信息的显示：三 详细设计。1 相关数据结构的设计。typedef struct job/建立作业信息结构char jname10; /作业名int hour; /到达时刻时钟数int minute; /到达时刻分钟数int run; /运行时间int memory; /要求主存空间int sign; /所要磁带机数int fhour; /完成时刻时钟数int fminute; /完成时刻分钟数int enterhour;/进入内存时时刻时钟数int enterminute;/进入内存时刻分钟数bool done;/记录是否作业已完成，完成true，否则falsejob,job;typedef struct jcb/作业信息结构intnu/记录作业位于主存分区表的分区号char name10;/作业名int rtime;/运行时间int memory;/申请主存空间jcb,jcb;typedef struct spart/分区表信息结构int num;/分区序号int sadd;/分区始址int space;/分区大小char situ10;/分区状态spart,spart;typedef struct pcb /* 定义进程控制块pcb */ char name10; / 进程名 int ntime; / 所需要的运行时间 int stime; /剩余时间pcb,pcb;typedef struct qbnode pcb base; struct qbnode *next;qbnode,*qcb;typedef struct int tip; / 就绪队列时间片 int num; / 就绪队列成员数 qcb front; / 队头指针 qcb rear; / 队尾指针 queuejob jwork5=/定义五个作业joba,10, 0,25,15,2,0,0,0,0,false,jobb,10,20,30,60,1,0,0,0,0,false,jobc,10,30,10,50,3,0,0,0,0,false,jobd,10,35,20,10,2,0,0,0,0,false,jobe,10,40,15,30,2,0,0,0,0,false;int disk=4;/磁带机数5int memory=100;/系统可用主存100kbint hour=9;/系统时间int minute=55;/9:55vector jexe;/主存作业队列vector jwait; /后备作业队列vector jdone;/完成作业队列vector jdisk;/输入井作业队列vectorqjcb;/作业队列vectorqproce;/位于主存的作业队列vectorqpart;/分区表状态队列vectorqfree;/空闲分区表项vectorpronum;/完成作业的主存分区号vector:iterator pnext;/记录空闲分区表分配主存后下一个空闲位置intsystime = 0;/系统时间，初始化为0intsysmemory = 100;/主存空间100kbintpnadr = -1;/记录pnext所要指向的分区始址，-1表示无空闲分区float progressflag = 0;/进度条标志位status initqueue(queue &q)/* 构造空队列q */ q.front=(qcb)malloc(sizeof(qbnode); q.rear=q.front; if(!q.front)return -2;q.num=0;q.tip=0; q.front-next=null; return 1;status enqueue(queue &q,pcb &e)/* 插入元素e为q的新的队尾元素 */ qcb p; p=(qcb)malloc(sizeof(qbnode); if(!p)return -2; p-base=e; p-next=null; q.rear-next=p;q.rear=p; return 1;status dequeue(queue &q,pcb &e)/* 若队列非空，则删除q的队头元素，用e返回其值 */ qcb p; if(q.front=q.rear)return 0;/* 空队列 */ p=q.front-next; e=p-base; q.front-next=p-next; if(q.rear=p)q.rear=q.front; p-next=null; free(p); return 1;status emptyqueue(queue &q)/判断q是否为空队列，是返回1,否返回0if(q.front-next=null)return 1;elsereturn 0;queue al;/进程队列2主存空间分配和回收的设计：循环首次适应法。使用链指针把所有的空闲分区链成一条链，为了实现对空闲分区的分配和链接，在每个分区的起始部分设置状态位、分区的大小和链接各个分区的前向指针，由状态位指示该分区是否分配出去了；同时，在分区尾部还设置有一后向指针，用来链接后面一个分区；分区的中间部分是用来存放作业的空闲内存空间，当该分区分配出去后，状态位改变。设计一个内存空闲分链，内存空闲分区通过空闲分区链来管理，在进行内存分配时系统统优先使用空闲区低端的空间。设计一个空闲分区说明链，设计一个某时刻主存空间占用情况表，作为主存当前使用基础。初始化空闲区和已分配区说明表的值。设计作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。当一个作业执行完成撤离时，作业所占的分区应该归还给系统。归还的分区如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。此时，相邻空闲区的合并问题，要求考虑四种情况：1）、释放区下邻空闲区（低地址邻接）2）、释放区上邻空闲区（高地址邻接）3）、释放区上下都与空闲区邻接4）、释放区上下都与空闲区不邻接3作业调度算法：先来先服务和短作业优先。（1）先来先服务算法：是按照作业进入输入井的先后次序来挑选作业，先进入输入井的作业优先被挑选，当系统中现有的尚未分配的资源不能满足先进入输入井的作业时，那么顺序挑选后面的作业。（2）短作业优先算法：总是按作业要求运行的时间来选择作业，每次挑选要求运行时间短且资源要求能满足的作业先进入主存执行。（3）程序流程图（仅以先来先服务调度算法说明过程）4进程调度算法：短进程优先和先来先服务。（1）先来先服务算法：是按照作业进入内存的先后次序来创建进程，先进入内存的作业优先被挑选，只要cpu一空闲，立即分配给队首的进程，让它拥有处理机资源，运行。（2）短进程优先算法：总是按进程要求运行的时间来选择进程，每次挑选要求运行时间最短进程先分配cpu执行。（3）程序流程图（仅以先来先服务调度算法说明过程）四编码。相应算法的实现（其中的重点部分）：void pclock(int &hour,int &minute)/时钟函数+minute;if(minute59)minute=0;+hour;if(hour23)hour=0;void calt(job &job,int hour,int minute) /计算完成时刻job.fminute=minute;job.fhour=hour;void pfcfsinput(queue &al1,vector &q)/* 建立先来先服务进程队列模块函数 */if(al1.num != q.size()/此时有新作业进入内存，则为它建立进程pcb p;while(al1.num q.size()strcpy(,qal1.num.jname);p.ntime = qal1.num.run;enqueue(al1,p);al1.num +;void psjfinput(queue &al1,vector &q) /建立短进程优先进程队列模块if(al1.num != q.size()pcb p;qcb ip1,ip2;int id = al1.num;while(al1.num next;/指向队列的首元素while(ip2 != null)if(p.ntime base.ntime)/新进程比正在运行的进程还要短break;ip1 = ip2;ip2 = ip1-next;pi-base = p;/插入进程pi-next = ip2;ip1-next = pi;al1.num +;while(al1.rear-next != null)/派完序注意要更新队尾指针al1.rear = al1.rear-next;vector:iterator ip;for(ip = q.begin();ip != q.end();+ip)if(ip-jname = qid.jname)break;vector jev(ip,q.end();/记录将要被删除作业q.erase(ip,q.end();/把这部分删除，以便从新排序for(id = 0;id jev.size();+id)/插入排序ip = q.begin();while(ip != q.end()if(jevid.run run)break;else+ip;q.insert(ip,jevid);void prun(queue &al1)/进程队列运行模块pclock(hour,minute); if(emptyqueue(al1) = 0)/进程队列非空，则执行al1.front-next-base.ntime -;/进程队列首元素正在执行if(al1.front-next-base.ntime next-base.ntime = 0;int sub = jexe0.run - al1.front-next-base.ntime; progressflag = (float)(sub)/(float)(jexe0.run);if(al1.front-next-base.ntime = 0)/进程已完成要撤销该进程pcb e;jexe0.done = true;dequeue(al1,e);al1.num -;vector:iterator itor = qproce.begin();while(itor != qproce.end()if(strcmp(itor-name,) = 0)itor-rtime = 0; break;else+itor;void insert(vector &q)/插入作业处理模块vector:iterator itor = pnext;sysmemory -= q0.memory;/分配主存空间if(q0.memory = itor-space)/空闲分区大小恰好等于作业大小strcpy(qpartitor-num.situ,q0.name);/将作业装入内存相应分区中jcb job = q0;q.erase(q.begin();/删除已装进主存的作业队列的作业job.num = pnext-num;/新作业的分区号int sub = qpart.size() - 1;if(pnext-num = sub)/新作业恰好位于末尾分区qproce.push_back(job);/新作业插入主存作业队列末尾elsevector:iterator jp;int id;id = pnext-num + 1;jp = qproce.begin();while(jp-num != id) /找到要插入新作业的位置+jp;qproce.insert(jp,job);+itor;if(itor = qfree.end()/指向原空闲分区表的最后一个元素qfree.erase(pnext);/删除已分配的空闲分区项pnext = qfree.begin();/pnext指向qfree首元素elsevector:iterator reg ;/记录要删除项的下一项reg = qfree.erase(pnext);/删除已分配的空闲分区项pnext = reg;/令pnext指向下一个空闲分区else/空闲分区大小大于作业申请空间大小spart part;/分割后位于分区表的空闲分区part.num = pnext-num + 1;part.sadd = pnext-sadd + q0.memory;part.space = pnext-space - q0.memory;strcpy(part.situ,pnext-situ);jcb job = q0;job.num = pnext-num;int sub = qpart.size() - 1;if(pnext-num = sub)/新作业装入原分区的最后的空闲分区qproce.push_back(job);elsevector:iterator jp;int id;jp = qproce.begin();id = pnext-num + 1;while(jp-num != id)/记录作业分区号需要改变的首位置+jp;vector:iterator ip;ip = jp;while(ip != qproce.end()/改变新作业之后作业的分区序号+(ip-num);+ip;qproce.insert(jp,job);/插入新作业vector:iterator spt;vector:iterator reg;spt = qpart.begin();while(spt-sadd !=qpartpnext-num.sadd)/记录分区表插入qpart所需要的位置+spt;qpartpnext-num.space = q0.memory;strcpy(qpartpnext-num.situ,q0.name);/把作业装进主存相应分区下+spt;reg = spt;while(reg != qpart.end()/更改其下的分区号+(reg-num);+reg;qpart.insert(spt,part);/插入part，分区表相应项序号已更改(*pnext) = part;/分割后的空闲分区项+itor;while(itor != qfree.end()/更改其下的空闲分区号+(itor-num);+itor;q.erase(q.begin();/删除已装进主存的作业队列的作业if(pnext != qfree.end()/空闲分区表非空pnadr = pnext-sadd;/赋pnext所指空闲分区的分区始址elsepnadr = -1;int disproce(vector &q)/主存分配处理模块if(qfree.empty()/无空闲空间分配q.erase(q.begin();/直接删除首元素return 0;elseif(q0.memory space)/空闲分区足够装入作业insert(q);return 1;else/搜索其它空闲分区if(qfree.size() 1)vector:iterator itor;itor = pnext;+itor;while(itor != pnext)if(itor = qfree.end()itor = qfree.begin();if(q0.memory space)/z找到合适的分区break/跳出while循环，停止搜索+itor;if(q0.memory space)pnext = itor;insert(q);return 1;q.erase(q.begin();/直接删除首元素return 0;void jsjfpro(vector &m) /短作业优先作业调度vector:iterator itor;vector:iterator reg;itor = jdisk.begin();while(itor != jdisk.end()/输入井作业if(itor-hour minute = minute) /当有作业在特定时刻申请进入主存jwait.push_back(*itor);/将作业插入就绪队列reg = jdisk.erase(itor);itor = reg;else+itor;if(!jwait.empty()/后备队列非空，按短作业排序vector jev(jwait);jwait.clear();vector:iterator ip;for(vector:size_type id = 0;id jev.size();+id)ip = jwait.begin();while(ip != jwait.end()if(jevid.run run )break;else+ip;jwait.insert(ip,jevid);m.clear();int i = 0;jcb m;ip = jwait.begin();while(ip != jwait.end()m.memory = ip-memory;m.rtime = ip-run;strcpy(,ip-jname);m.push_back(m);+i;+ip;/就绪队列作业，存放已到达而因资源不足而阻塞的作业itor=jwait.begin();while(itor!=jwait.end()if(disk=itor-sign) /当主存空间磁带机足够用时if(disproce(m) = 1)job job=*itor; /复制作业信息job.enterhour = hour;/进入主存时钟数job.enterminute = minute;/进入主存分钟数memory-=itor-memory; /分配主存空间disk-=itor-sign;/分配磁带机reg=jwait.erase(itor); /删除就绪队列将要插入主存的作业jexe.push_back(job); /将job插入主存队列尾itor=reg;/指向被删除作业的下一个位置else+ itor;/往主存队列添加作业直至主存空间不足或者就绪作业队列为空else+itor;m.erase(m.begin();void jfcfspro(vector &m)/先来先服务作业调度vector:iterator itor;vector:iterator reg;itor = jdisk.begin();while(itor != jdisk.end()/输入井作业if(itor-hour minute = minute) /当有作业在特定时刻申请进入主存jwait.push_back(*itor);/将作业插入就绪队列reg = jdisk.erase(itor);itor = reg;else+itor;if(!jwait.empty()m.clear();int i = 0;jcb m;vector:iterator ip;ip = jwait.begin();while(ip != jwait.end()m.memory = ip-memory;m.rtime = ip-run; strcpy(,ip-jname);m.push_back(m);+i;+ip; /就绪队列作业，存放已到达而因资源不足而阻塞的作业itor=jwait.begin();while(itor!=jwait.end()if(disk = itor-sign) /当主存空间磁带机足够用时if(disproce(m) = 1)job job= *itor; /复制作业信息job.enterhour = hour;/进入主存时钟数job.enterminute = minute;/进入主存分钟数memory-=itor-memory; /分配主存空间disk-=itor-sign;/分配磁带机reg=jwait.erase(itor); /删除就绪队列将要插入主存的作业jexe.push_back(job); /将job插入主存队列尾itor=reg;/指向被删除作业的下一个位置else+ itor;/往主存队列添加作业直至主存空间不足或者就绪作业队列为空else+itor;m.erase(m.begin();void jfinjob()/完成作业处理模块if(!jexe.empty()/主存作业非空if(jexe0.done = true) /如果作业已完成 job work=*jexe.begin();/作业完成，要将其插入到完成作业队列calt(work,hour,minute);memory+=jexe.begin()-memory; /释放占用的主存空间disk+=jexe.begin()-sign;/释放磁带机jexe.erase(jexe.begin(); /删除主存模块的首作业jdone.push_back(work);/添加到完成队列void recproce()/作业释放处理模块for(vector:size_type i = 0;i pronum.size();+i)sysmemory += qpartpronumi.space;/释放主存strcpy(qpartpronumi.situ,空闲内存);/释放已完成的作业pronum.clear();vector:iterator del;vector:iterator it;del = qpart.begin();+del;/主存队列首分区分配已给系统while(del != qpart.end()/更新分区表qpartif(strcmp(del-situ,空闲内存) = 0)/指定分区为空闲分区it = del;+it;if(it != qpart.end()if(strcmp(it-situ,空闲内存) = 0)/del的下一分区也空闲/合并del和it指向的分区int adr1,adr2;adr1 = del-sadd;adr2 = it-sadd;it-num = del-num;it-sadd = del-sadd;it-space += del-space;it = qpart.erase(del);/合并分区，删除无用分区if(pnadr != -1)if(pnadr = adr1)|(pnadr = adr2) /pnext记录的内容恰好指向原分区表的del和it位置pnadr = it-sadd;/记录pnext所要指向it所指位置的始址，以便更新qfree表elsepnadr = it-sadd;elseif(pnadr = -1)/原空闲分区表为空pnadr = del-sadd;/令pnext指向分区表的第一个空闲分区位置，便于更新qfreedel = it;else/指向的分区为作业分区，则跳过+del;void memfreeproce()/主存释放处理模块vectorpreg;/记录主存作业队列中未完成的作业队列for(vector:size_type i = 0;i qproce.size();+i)if(qprocei.rtime = 0)/说明作业已完成pronum.push_back(qprocei.num);/记录要释放的主存分区号elsepreg.push_back(qprocei);qproce.clear();qproce = preg;if(!pronum.empty()/有作业要释放recproc