操作系统实验报告进程调度算法

1、HUNAN UNIVERSITY 进程调度算法 题 目 进程调度算法 学生姓名 学生学号 专业班级 完成日期 2013.12.06 一、实验题目 实现短进程优先调度算法（SPF） 实现时间片轮转调度算法（RR）二、实验目的 通过对进程调度算法的设计，深入理解进程调度的原理。 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 进程调度分配处理机，是控制协调进程对CPU的竞争，即按一定的调度算法从就绪队列中选中一个进程，把CPU的使用权交给被选中的进程。三、实验内容1. 先来先服务（FCFS）调度算法 原理：每次调度是从就绪队列中，选择一个最先进入就绪队列的进程，把

2、处理器分配给该进程，使之得到执行。该进程一旦占有了处理器，它就一直运行下去，直到该进程完成或因发生事件而阻塞，才退出处理器。 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。 按照就绪进程进入就绪队列的先后次序进行调度，简单易实现，利于长进程，CPU繁忙型作业，不利于短进程，排队时间相对过长。2. 时间片轮转调度算法RR 原理：时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度按一定时间片(q)轮番运行各个进

3、程. 进程按到达时间在就绪队列中排队，调度程序每次把CPU分配给就绪队列首进程使用一个时间片，运行完一个时间片释放CPU，排到就绪队列末尾参加下一轮调度，CPU分配给就绪队列的首进程。 固定时间片轮转法： 1 所有就绪进程按 FCFS 规则排队。 2 处理机总是分配给就绪队列的队首进程。 3 如果运行的进程用完时间片，则系统就把该进程送回就绪队列的队尾，重新排队。 4 因等待某事件而阻塞的进程送到阻塞队列。 5 系统把被唤醒的进程送到就绪队列的队尾。 可变时间片轮转法： 1 进程状态的转换方法同固定时间片轮转法。 2 响应时间固定，时间片的长短依据进程数量的多少由 T=N(q+t)给出的关系调

4、整。 3 根据进程优先级的高低进一步调整时间片，优先级越高的进程，分配的时间片越长。3. 算法类型:4. 模拟程序可由两部分组成，先来先服务(FCFS)调度算法，时间片轮转。流程图如下图所示:四 打印的源程序及附上的注释#includeusing namespace std;#define P_NUM 3/cpu4种状态 就绪 运行 等待 完成enum stateready,waiting,block,finish;/PCB 进程控制块 包括名称、优先级、占用CPU时间、需要时间struct pcbchar name4;int priority;int cputime;int needtime

5、;int count;int round;state process;pcb * next;/构建优先级队列;/建立一个优先权的队列pcb * get_process() pcb *q=NULL;pcb *t=NULL;pcb *p=NULL;int i=0;coutinput name and timeendl;while (iq-name;cinq-needtime;q-cputime=0;q-priority=P_NUM-i;q-process=ready;q-next=NULL;if (i=0)p=q;t=q;elset-next=q;t=q;i+; /whilereturn p; /

6、输出当前队列各个进程各种状态void display(pcb *p)coutname cputime needtime priority stateendl;while(p)coutname;cout ;coutcputime;cout ;coutneedtime;cout ;coutpriority;coutprocess)case ready:coutreadyendl;break;case waiting:coutwaitingendl;break;case block:coutblockendl;break;case finish:coutfinishnext;/检查队列中进程是否完成

7、int process_finish(pcb *q)int bl=1;while(bl&q)bl=bl&q-needtime=0;if(q-next!=NULL)q=q-next;return bl;/找到优先权最大的进程 执行void cpuexe(pcb *q)pcb *t=q;int tp=0;while(q)if (q-process!=finish)q-process=ready;if(q-needtime=0)q-process=finish;if(tppriority&q-process!=finish)tp=q-priority;t=q;q=q-next;if(t-needti

8、me!=0)t-needtime-;t-process=waiting;t-cputime+;/优先权调度void priority_cal()pcb * p=NULL;p=get_process();int cpu=0;while(!process_finish(p)cpu+;coutcputime:cpuendl;cpuexe(p);display(p);printf(All processes have finished,press any key to exit);/初始化界面void display_menu()cout选择CPU调度算法：endl;cout1 优先权endl;cou

9、t2 转轮法endl;cout3 退出endl;/轮转法调度初始化pcb * get_process_round()pcb *q=NULL;pcb *t=NULL;pcb *p=NULL;int i=0;coutinput name and time：endl;while (iq-name;cinq-needtime;q-cputime=0;q-round=0;q-count=0;q-process=ready;q-next=NULL;if (i=0)p=q;t=q;elset-next=q;t=q;i+; /whilereturn p;/cpu单位时间为1void cpu_round(pcb

10、 *q)q-cputime+=1;q-needtime-=1;if(q-needtimeneedtime=0;q-process=finish;return;q-count+;q-round+;q-process=waiting;/轮转法找到下一个可以CPU执行的程序pcb * get_next(pcb * k,pcb * head)pcb * t;t=k;t=t-next;while (t & t-process=finish)t=t-next;if(t=NULL)t=head;while (t-next!=NULL & t-process=finish)if(t-next=k)t=t-ne

11、xt;if(t-next!=NULL)t=t-next;return t;/整理队列里的进程状态void set_state(pcb *p)while(p)if (p-needtimeprocess=finish;if (p-process=waiting)p-process=ready;p=p-next;/每个CPU时间后输出每个进程状态void display_round(pcb *p)coutNAME CPUTIME NEEDTIME COUNT ROUND STATEendl;while(p)coutname;cout ;coutcputime;cout ;coutneedtime;cout ;coutcount;cout ;coutround;coutprocess)case ready:coutreadyendl;break;case waiting:coutwaitingendl;break;case finish:coutfinishnext;/转轮调度void round_cal()pcb * p=NULL;pcb * r=NULL;p=get_process_round();int cpu=0;r=p;while(!p