操作系统进程调度编程

1.实验内容编写一个单处理机下的进程调度程序，模拟操作系统对进程的调度。2.实验目的进程是操作系统中最基本、最重要的概念，进程调度又是操作系统的核心模块。本实验要求学生独立设计并实现进程调度模拟程序，以加深对进程控制块概念和各种进程调度算法的理解。3.实验要求可以随机输入若干进程，支持先来先服务、短作业优先、最短剩余时间优先、时间片轮转、动态优先级调度算法，能够输出进程的调度过程。4.程序中使用的数据结构及符号说明(1).PCB（进程控制块）1.structpcb2.{3.intid;4.intarrive;5.intrun;6.intpriority;7.inttime;8.booldone;9.};说明：在进程控制块中记录了以下信息：数据项类型说明idint进程号pidarriveint进程到达时间runint进程运行时间priorityint进程优先级timeint进程运行的时间片donebool记录进程是否已经完成运行(2).PCB数组1.structpcbprocess[N];说明：process数组用于保存调度所涉及的进程的信息。5.各种调度算法的处理流程，重要模块的详细设计及功能和接口说明(1).预处理算法流程对应程序代码及注释1.intmain()2.{3.//初始化PCB数组4.memset(process,0,sizeof(process));5.//读入调度类型6.inttype;7.scanf(%d,&type);8.//读入调度进程数据9.for(n=0;~scanf(%d/%d/%d/%d/%d,10.&process[n].id,11.&process[n].arrive,12.&process[n].run,13.&process[n].priority,14.&process[n].time);n++);15.//根据调度类型转到子程序进行调度16.switch(type)17.{18.//各调度子程序：19.case1:fcfs();break;//先来先服务20.case2:sjf();break;//短作业优先21.case3:sltf();break;//最短剩余时间优先22.case4:tpt();break;//时间片轮转23.case5:dp();break;//动态优先级24.}25.return0;26.}(2).先来先服务算法逻辑流程本题中算法实际流程对应程序代码及注释1.voidfcfs()2.{3.//按到达时间、pid排序4.sort(process,process+n,cmp_ar_id);5.//初始化系统时间6.inttime=0;7.//顺序遍历各进程8.for(inti=0;in;i++)9.{10.//若当前系统时间时没有待调度进程11.if(timeprocess[i].arrive)12.{13.//等待系统时间到达下一个进程到来14.time=process[i].arrive;15.}16.//否则17.//进行进程调度18.printf(%d/%d/%d/%d/%d\n,i+1,process[i].id,time,time+process[i].run,process[i].priority);19.//进程运行，系统时间流逝20.time+=process[i].run;21.}22.return;23.}(3).短作业优先算法逻辑流程本题中算法实际流程对应程序代码及注释1.voidsjf()2.{3.//按运行时间、pid排序4.sort(process,process+n,cmp_run_id);5.//初始化系统时间6.inttime=0;7.//有未运行进程8.for(intm=1;m=n;)9.{10.//找出已到达的未运行进程中，运行时间最短的进程11.intmin=INT_MAX,mini=-1;12.for(inti=0;in;i++)13.{14.if(process[i].arrive=time&&//已到达的进程15.process[i].runmin&&//运行时间最短的进程16.!process[i].done)//未运行的进程17.{18.min=process[i].run;19.mini=i;20.}21.}22.//若当前系统时间时没有待调度进程23.if(-1==mini)24.{25.//找出下一个到达的时间26.intmint=INT_MAX;27.for(inti=0;in;i++)28.{29.if(process[i].arrivemint&&//最近的到达时间30.!process[i].done)//未运行的进程31.{32.mint=process[i].arrive;33.}34.}35.//等待系统时间到达下一个进程到来36.time=mint;37.continue;38.}39.//否则40.//进行进程调度41.printf(%d/%d/%d/%d/%d\n,m,process[mini].id,time,time+process[mini].run,process[mini].priority);42.//进程运行，系统时间流逝43.time+=process[mini].run;44.process[mini].done=true;45.//已运行进程数+146.m++;47.}48.}(4).最短剩余时间优先算法逻辑流程本题中算法实际流程主流程：调度器配置阶段：预调度阶段：进程调度阶段：进程运行阶段：对应程序代码及注释1.voidsltf()2.{3./**********调度器配置阶段**********/4.//按到达时间、运行时间、pid排序5.sort(process,process+n,cmp_run);6.//初始化系统时间7.inttime=process[0].arrive;8.//初始化调度程序配置9.intexeci=-1,start=time;10.intk=0,m=0;11.//有未运行进程12.for(inti=0;mn;)13.{14./**********预调度阶段**********/15.//找到在当前系统时间已经到达的进程16.for(;process[i].arrive=time&∈i++);17.//在已到达进程中查找剩余运行时间最短的未结束进程18.intmin=INT_MAX,mini=-1;19.for(intj=0;ji;j++)20.{21.if(process[j].runmin&&!process[j].done)22.{23.min=process[j].run;24.mini=j;25.}26.}27.//若在当前系统时间之前到达的进程均已经结束28.if(-1==mini)29.{30.//等待下一个进程到达后重新进行调度31.time=process[i].arrive;32.continue;33.}34.//若当前没有正在运行的进程35.if(-1==execi)36.{37.//则执行找到的进程38.execi=mini;39.//进程的开始运行时间设为现在的时间40.start=std::max(process[execi].arrive,time);41.}42./**********进程调度阶段**********/43.//若找到的进程剩余运行时间小于当前正在运行进程的剩余运行时间44.if(process[mini].runprocess[execi].run)45.{46.//则进行调度47.printf(%d/%d/%d/%d/%d\n,++k,process[execi].id,start,time,process[execi].priority);48.execi=mini;49.start=time;50.}51./**********进程运行阶段**********/52.//运行进程53.intrunnable=process[i].arrive-time;54.//若进程可以完成运行则将进程运行完55.if(runnable=process[execi].run||runnable=0)56.{57.time+=process[execi].run;58.printf(%d/%d/%d/%d/%d\n,++k,process[execi].id,start,time,process[execi].priority);59.process[execi].run=0;60.process[execi].done=true;61.m++;62.execi=-1;63.start=time;64.}65.//若进程不能完成运行则运行一个时间片66.else67.{68.time+=runnable;69.process[execi].run-=runnable;70.}71.}72.return;73.}74.(5).时间片轮转算法逻辑流程本题中算法实际流程对应程序代码及注释1.voidtpt()2.{3.//初始化进程队列4.queuepcbqu;5.process[n].arrive=INT_MAX;6.//按到达时间、pid排序7.sort(process,process+n,cmp_ar_id);8.//初始化系统时间9.inttime=process[0].arrive;10.//所有进程是否均完成运行11.for(inti=0,k=1,m=0;mn;)12.{13.//如果队列为空14.if(qu.empty())15.{16.//等待新的进程到达17.time=process[i].arrive;18.//将当前系统时间之前的进程放入队列19.for(;process[i].arrive=time&∈i++)20.{21.qu.push(process[i]);22.}23.}24.//取队首进程25.pcbtemp=qu.front();26.qu.pop();27.//如果进程不能完成运行28.if(temp.runtemp.time)29.{30.//进程调度31.printf(%d/%d/%d/%d/%d\n,k++,temp.id,time,time+temp.time,temp.priority);32.//将进程运行一个时间片33.time+=temp.time;34.temp.run-=temp.time;35.//将当前系统时间之前的进程放入队列36.for(;process[i].arrive=time&∈i++)37.{38.qu.push(process[i]);39.}40.//将进程放回队列41.qu.push(temp);42.}43.//如果进程可以完成运行44.else45.{46.//进程调度47.printf(%d/%d/%d/%d/%d\n,k++,temp.id,time,time+temp.run,temp.priority);48.//将进程运行完49.time+=temp.run;50.//将当前系统时间之前的进程放入队列51.for(;process[i].arrive=time&∈i++)52.{53.qu.push(process[i]);54.}55.m++;56.}57.}58.return;59.}(6).动态优先级算法逻辑流程本题中算法实际流程对应程序代码及注释1.voiddp()2.{3.//按到达时间、pid排序4.sort(process,process+n,cmp_ar_id);5.//初始化系统时间6.inttime=process[0].arrive;7.intlast=time;8.intmin,mini=-1;9.for(inti=0,k=1,m=0;mn;)10.{11.//找到在当前系统时间已经到达的进