优先调度、时间片轮转概要

1、计算机操作系统课程实验报告姓名：学号：班级：完成日期：目 题 验 实成 完 立 独设计目的度的 务调 容 服务 内 。 先 分先 解部 理 先来 各 的 先 理 念 、 管 概 法 程 程 数 法 进 先 算 对 优 度 深 解 调 加 了 先 1 2 业 。作解 短理设计预备知识短 法 算 度 调 务 服 先 来 先设计内容优出给序(已 拟程 开 程。 (调 一 也可 制 含 度 优 要 合 的 程 包 调 的 序 适 同 的 少 程 出 。 程 计 不 计 至 进 给 ) 拟 设 对 设 个 拟 在 选 模一 模 以 自 的 ） ） ） 计 法 可 可 计 1 2 3 设 算 计 言 设

2、（ （ （ 数设语先的发一、设计理论描述a) 优先数调度算法为了照顾紧迫型作业， 使之在进入系统后便获取优先处理， 引入了最高优先 权优先调度算法， 此算法常被用于批处理系统中， 作为作业调度算法木， 也作为 多钟操作系统中的进程调度算法， 还可以用于实时操作系统中。 当把该算法用于 作业调度时，系统将从后备队列中选择若干优先权最高的作业装入内存。b) 时间片轮转调度算法在早期的时间片轮转法中， 系统将所有的就绪进程按照先来先服务的原则排 成一个队列，每次调度时，把 CPU 分配桂队首进程，并执行一个时间片。当执 行时间片用完时， 由一个计时器发出时钟中断请求， 调度程序便据此信号停止该 进程

3、的执行，并将它送往就绪队列的队尾。二、设计思想、设计分析及数据结构模型1、 优先数调度算法（1）设计思想按某种原则对就绪队列中的每个进程赋予一个优先级 ,进程调度时则根据进 程的优先级确定选择顺序， 即把处理机分配给就绪队列中优先级高的进程。 由于 进程的优先级别通常用数字表示， 所以又称为进程的优先数。 有些操作系统中规 定优先数愈小，其优先级愈高， 本设计研究的是优先数愈高， 优先级愈高的情况。优先数调度算法一般可以采用抢占式优先调度算法或非抢占优先调度算法。在采用抢占式优先调度算法时， 系统同样是把处理机分配给优先数最高的进 程，使之执行。但在其执行期间，只要又出现了另一个其优先数更高的

4、进程，进 程调度程序就立即停止当前进程 （原优先数最高的进程） 的执行， 重新将处理机 分配给新到的优先数最高的进程。在采用非抢占式优先调度算法时， 系统一旦把处理机分配给就绪队列中优先 数最高的进程后， 该进程便一直执行下去， 直至结束； 或因发生某事件使该进程 放弃处理机时， 系统方可再将处理机重新分配给另一优先数最高的进程。 这种调 度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。（2）设计分析进程调度所依赖的数据结构通常是调度队列， 由于调度的原因不同， 在单处 理器系统中设置了多种等待队列； 只有就绪队列中的进程能够获得处理器而最终 运行，其他队列中的进程从队列

5、中调度出来后， 必须进入就绪队列才能分配处理（3）数据结构模型用结构体变量定义进程控制块的优先级，进程需要占用 CPU 的时间 （cputime），运行后还需要 CPU 的时间，进程的状态，及指向 pcb 结构体变量的 指针。具体代码如下：typedef struct nodechar name10; /* 进程标识符 */int prio; /* 进程优先数 */int cputime; /* 进程占用 CPU 时间 */int needtime; /* 进程到完成还要的时间 */char state; /* 进程的状态 */struct node *next; /* 链指针 */PCB;进

6、程名next优先数占用 CPU 时间到完成还要的时间状态2、 时间片轮转调度算法（1）设计思想时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的 时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出 来。时间片轮转算法中，系统将所有的就绪进程按先来先服务的原则排成一个队 列，每次调度时，把 CPU 分配给队首进程，并令其执行一个时间片。时间片的 大小从几 ms 到几百 ms。当执行的时间片用完时， 由一个计时器发出时钟中断请 求，调度程序便据此信号来停止该进程的执行， 并将其送往就绪队列的末尾； 然 后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个

7、时间片。 这样就可以保证就绪队列中的所有进程在一定给定的时间内均能获得一时间片 的处理机执行时间。换言之，系统能在给定时间内响应所有用户的请求。（2）设计分析 每个进程用一个 PCB表示。 PCB 包括进程名，到达时间，运行时间，剩余 时间，进程状态，链接指针。其中，进程名，到达时间和运行时间由用户输入， 剩余时间的初值等于运行时间。为简单起见，进程状态设为三种：就绪，运行和 完成。链接指针指向下一个进程的 PCB；按照进程到达的先后顺序排成一个队 列。设置一个队头指针指向队列中第一个进程， 并设置一个队尾指针指向队列中 的最后一个进程； 执行调度时，先选择队首的第一个进程运行。另外设置一个

8、指向当前运行进程的指针。（3）数据结构模型 用结构体变量定义进程控制块的优先级，进程需要占用 CPU 的时间 （cputime），运行后还需要 CPU 的时间，进程的状态，分配 cpu 时间，执行次数 及指向 pcb 结构体变量的指针。具体代码如下：typedef struct nodechar name10;/* 进程标识符 */int cputime;/* 进程占用 CPU 时间*/int needtime;/* 进程到完成还要的时间char state;/* 进程的状态 */int round;/* 分配 cpu 的时间片 */int count;/* 执行次数 */struct nod

9、e *next;/* 链指针 */int prio;/* 进程优先数 */PCB;进程名next优先数占用 CPU 时间到完成还要的时间状态分配 CPU 的时间片执行次数三、变量说明及程序流程图优先数调度算法：时间片轮转调度算法：四、源代码#include<stdio.h> #include<stdlib.h> #include<string.h> #include<conio.h> typedef struct nodechar name10;/* 进程标识符 */int prio;/* 进程优先数 */int cputime;/* 进程占用

10、CPU 时间 */int needtime;/* 进程到完成还要的时间char state;/* 进程的状态 */struct node *next;/*链指针 */int round;/*分配 cpu 的时间片 */int count;/* 执行次数 */*/PCB;PCB *finish,*ready,*run; /* 队列指针 */ int N; /* 选择数 */* 将就绪队列中的第一个进程投入运行*/ void firstin()run=ready; /* 就绪队列头指针赋值给运行头指针 */ run->state='R' /* 进程状态变为运行态 */ rea

11、dy=ready->next; /* 就绪对列头指针后移到下一进程 */void prt1()/* 标题输出函数 */if(N=1)cputime needtime priority staten");cputime needtime state countn");printf(" name elseprintf(" namevoid prt2(PCB *q)/*进程 PCB 输出 */ if(N=1)printf(" %-10s%-10d%-10d%-10d %cn",q->name,q->cputime,q-&g

12、t;needtime,q->prio,q->state);else q->count=q->cputime/q->round;printf(" %-10s%-10d%-10d %ct%-10dn",q->name, q->cputime,q->needtime,q->state,q->count);void prt()/* 输出函数 */PCB *p;prt1(); /* 输出标题 */if(run!=NULL) /* 如果运行指针不空 */prt2(run); /* 输出当前正在运行的 PCB*/p=ready;

13、/* 输出就绪队列 PCB*/while(p!=NULL)prt2(p);p=p->next;p=finish; /* 输出完成队列的 PCB*/ while(p!=NULL)prt2(p);p=p->next;getch(); /* 按任意键继续 */void insert(PCB *q)/* 优先数的插入算法 */PCB *p1,*s,*r;int b;s=q; /*待插入的 PCB 指针 */p1=ready; /* 就绪队列头指针 */r=p1; /*r 做 p1 的前驱指针 */b=1;while(p1!=NULL)&&b) /* 根据优先数确定插入位置

14、*/ if(p1->prio>=s->prio)r=p1;p1=p1->next;elseb=0;if(r!=p1) /* 如果条件成立说明插入在 r 与 p1 之间 */r->next=s;s->next=p1;elses->next=p1; /* 否则插入在就绪队列的头 */ ready=s;void create()/* 优先数创建初始 PCB 信息 */PCB *p;int i,time;char na10;PCB*/ready=NULL; /* 就绪队列头指针 */ finish=NULL; /* 完成队列头指针 */ run=NULL; /

15、* 运行队列指针 */ printf("nn 输入 5个进程标识和所需时间 n"); /* 输入进程标识和所需时间创建 for(i=1;i<=5;i+)p=(PCB*)malloc(sizeof(PCB);printf(" 输入第 %d 个进程的名字和时间 :",i);scanf("%s",na); scanf("%d",&time);strcpy(p->name,na);p->cputime=0;p->needtime=time;p->state='w'if(

16、N=1)p->prio=35-time;/* 进程的优先数以 35-time 构成 */elsep->prio=50; /* 进程的优先数都为 50*/if(ready!=NULL) /* 就绪队列不空调用插入函数插入 */insert(p);elsep->next=ready; /* 创建就绪队列的第一个 PCB*/ ready=p;system("cls");printf("output of process:n");*n");printf(prt(); /*输出进程 PCB 信息 */run=ready; /* 将就绪队

17、列的第一个进程投入运行 */ready=ready->next;run->state='R'void priority()/* 优先数调度算法 */while(run!=NULL) /* 当运行队列不空时，有进程正在运行 */run->round=1;/* 时间片 */run->cputime=run->cputime+1;/*CPU 时间片数加 1*/if(N=1) run->needtime=run->needtime-1;/* 进程还需要的时间片数减 1*/ run->prio=run->prio-2; /* 每运行一

18、次优先数降低 2 个单位 */else run->needtime=run->needtime-run->round;/* 进程还需要的时间片数减时间片*/run->prio=run->prio-5; /* 每运行一次优先数降低 5 个单位 ,即该进程到队列最 后*/if(run->needtime=0) /* 如所需时间为 0 将其插入完成队列 */run->next=finish;finish=run;run->state='F'/* 置状态为完成态 */run=NULL;/* 运行队列头指针为空 */if(ready!=NU

19、LL)/* 如就绪队列不空 */firstin(); /* 将就绪对列的第一个进程投入运行 */* 没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列 */else if(ready!=NULL)&&(run->prio<ready->prio)run->state='W'insert(run);firstin(); /* 将就绪队列的第一个进程投入运行 */prt(); /* 输出进程 PCB 信息*/* 主函数 */ void main()system("cls");*n");printf(printf(" 请选择算法 :1.优先数调度算法； 2.时间片轮转算法