操作系统实验三进程调度

操作系统实验

实验三 进程调度

学号 1215108019 姓名 李克帆 班级 12电子2班

华侨大学电子工程系

实验目的

1、理解有关进程控制块、进程队列的概念。

2、掌握进程优先权调度算法和时间片轮转调度算法的处理逻辑。

实验内容与基本要求

1、设计进程控制块PCB的结构，分别适用于优先权调度算法和时间片轮转

调度算法。 2、建立进程就绪队列。

3、编制两种进程调度算法：优先权调度算法和时间片轮转调度算法。

实验报告内容

1、优先权调度算法和时间片轮转调度算法原理。

优先权算法:（1）当该算法用于作业调度时，系统从后备作业队列中选择若干个优先级最高的，且系统能满足资源要求的作业装入内存运行。

（2）当该算法用于进程调度时，将把处理机分配给就绪进程队列中优先级最高的进程。

时间片轮转法:

系统将所有的就绪进程按先来先服务的原则,排成一个队列,每次调度时,把CPU分配给队首进程,并令其执行一个时间片.时间片的大小从几ms到几百ms.当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片.这样就可以保证就绪队列中的所有进程,在一给定的时间内,均能获得一时间片的处理机执行时间.

2、程序流程图。 3、程序及注释。 #include #include //使用timer()函数 #include //时间延迟

#define DELAY 200 //每次运算后的停留时间

//时间片

#define SJP 3 //这里的时间片是固定的，这就要求每个进程的服务时间略小于4

/**********全局变量声明**********/

unsigned short TIME=0; //无符号，定义时间 unsigned short NUM=0; //无符号，定义进程数量 char TYPE='1'; //模拟类型

//PCB结构体定义

typedef struct PCB// struct 结构体 {

char name[16];

char state; //[R]Run,[F]Finish,[P]Pause,[N]New

unsigned short priority; //数字越大，优先级越高，最小为1 unsigned short t_arrive; //到达时间 unsigned short t_start; //开始时间 unsigned short t_finish; //完成时间 unsigned short t_service; //服务时间 unsigned short t_run; //运行时间 unsigned short t_wait; //等待时间 struct PCB *next; } pcb;

pcb *now=NULL, //定义now指针，一开始不赋值。指向现在运行的pcb

*head=NULL; //pcb链头部指针

/**********函数声明**********/

void fcfs(); //先到先服务 void sjf(); //短作业优先 void gyxb(); //高优先比 void sjplz(); //时间片轮转

void init(); //初始化，完成pcb录入

pcb *sort(pcb*); //对init()录入的pcb按到达时间排序 void timer(); //定时器，每一个延迟自我调用一次 void result(); //打印结果

//先到先服务算法 void fcfs() {

if(now->t_arrive>TIME) //判断有无进程到达 {

printf(\时间：%d]\\t无进程运行\\n\ return; }

if(now->state=='N') //判断state的状态 {

now->state='R'; //如果是新的程序，将state改为R now->t_start=TIME;

printf(\时间：%d]\\t进程：%s 首次运行\\n\显示该程序第一次运行 }

else if(now->state=='R')//else if语句中嵌套两个if语句，用来判断进程处在运行阶段还是完成阶段 {

(now->t_run)++;//now取t_run中的地址，再取内容

if(now->t_run>=now->t_service)//判断任务是否完成，标准时运行时间大于服务时间 {

now->state='F';//如果完成，则state的状态由Run改为Finally now->t_finish=TIME;

printf(\时间：%d]\\t进程：%s 任务完成\\n\任务完成，跳出if

now=now->next;

if(now!=NULL) fcfs();//判断是否还有未完成的程序 }

else printf(\时间：%d]\\t进程：%s 正在运行，已运行时间：%d\\n\任务未完成，返回外层语句继续循环执行 } }

//短作业优先算法 void sjf() {

pcb *p=head,*p_min=NULL;//创建p和p_min两个指针 unsigned short t_min=9999;

//从现在时间以前并且未结束的进程中，选出服务时间最小的进程 while(p!=NULL && p->t_arrive<=TIME) {

if(p->state=='F')//判断程序是否结束 {

p=p->next; continue; }

if((p->t_service-p->t_run)

t_min=p->t_service; p_min=p; } p=p->next; }

if(p_min==NULL) //如果为空，判断全部进程是否都已完成 {

char k='Y'; p=head; while(p!=NULL) {

if(p->state!='F')//state状态为F时也被视为无程序在运行 k='N';

p=p->next;//p前往下一个程序进行扫描 } if(k=='Y') now=NULL;

else printf(\时间：%d]\\t无进程运行\\n\

return; }

if(p_min!=now)//如果选出的进程和之前的不同 {

if(now->state=='R')//暂停现在正在运行的程序，将state的状态改为P {

now->state='P';

printf(\时间：%d]\\t进程：%s 暂停运行\\n\ } }

if(p_min==NULL) now=head; else now=p_min;

if(now->state=='N')//将新进程的状态改为正在运行的进程，并标显示进程正在运行 {

now->state='R'; now->t_start=TIME;

printf(\时间：%d]\\t进程：%s 首次运行\\n\ } else {

if(now->state=='P')//若进程被暂停，则将进程开启 {

now->state='R';

printf(\时间：%d]\\t进程：%s 继续运行\\n\ }

(now->t_run)++;

if(now->t_run>=now->t_service)//把服务时间赋予运行时间 {

now->state='F'; now->t_finish=TIME;

printf(\时间：%d]\\t进程：%s 任务完成\\n\ gyxb(); }

else printf(\时间：%d]\\t进程：%s 正在运行，已运行时间：%d\\n\ } }

//高优先比算法 void gyxb() {

pcb *p=head,*p_min=NULL; unsigned short t_min=0;

//从现在时间以前并且未结束的进程中，选出服务时间最小的进程 while(p!=NULL && p->t_arrive<=TIME) {

if(p->state=='F')//检查运行完成的程序，标准时state的状态为Finish {

p=p->next; continue; }

//动态优先比

if(p->state=='P')//设置动态优先比 {

p->t_wait++;

p->priority+=p->t_wait/p->t_service+1;///////////////////////////////////////////////////////////////////////// }

if(p->priority>t_min)//如果现有的程序优先级大于先前程序的优先级，则进行替换。 {

t_min=p->priority; p_min=p; } p=p->next; }

//如果为空，判断全部进程是否都已完成 if(p_min==NULL) {

char k='Y'; p=head; while(p!=NULL) {

if(p->state!='F')//state状态为F时也被视为无程序在运行 k='N';

p=p->next;//运用p指针逐个扫描 } if(k=='Y') now=NULL;

else printf(\时间：%d]\\t无进程运行\\n\ return; }

//如果选出的进程和之前的不同 if(p_min!=now) {

if(now->state=='R')//进程不同则暂停现在运行的程序 {

now->state='P';

printf(\时间：%d]\\t进程：%s 暂停运行\\n\ } }

if(p_min==NULL) now=head; else now=p_min;

if(now->state=='N') {

now->state='R'; now->t_start=TIME;

printf(\时间：%d]\\t进程：%s 首次运行\\n\ } else {

if(now->state=='P') {

now->state='R'; now->t_wait=0;

printf(\时间：%d]\\t进程：%s 继续运行\\n\ }

(now->t_run)++;

if(now->t_run>=now->t_service) {

now->state='F'; now->t_finish=TIME;

printf(\时间：%d]\\t进程：%s 任务完成\\n\ sjf(); }

else printf(\时间：%d]\\t进程：%s 正在运行，已运行时间：%d\\n\ } }

//时间片轮转算法 void sjplz() {

pcb* p=head,*q=now;//p,q分别取head和now的地址 //每个 时间片结束时的处理

if(TIME%SJP==0 && TIME/SJP>0)//如果时间片结束时程序还没有完成则执行下面的语句 {

char k='Y';

while(p!=NULL) {

if(p->state!='F') { k='N'; break; } p=p->next; }

if(k=='Y') {

now=NULL; return; }

if(p!=NULL) {

while(1) {

if (q->next!=NULL) {

if((q->next)->state=='F') {

q=q->next; continue; } else {

now=q->next; break; } } else {

q=head;

if(q->state=='F') continue; else {

now=head; break;

} }

} } else { p=head;

while(p->next!=NULL) p=p->next; now=p; } }

if(now->t_arrive>TIME) {

printf(\时间：%d]\\t无进程运行\\n\ return; }

if(now->state=='N') {

now->state='R'; now->t_start=TIME;

printf(\时间：%d]\\t进程：%s 首次运行\\n\ }

else if(now->state=='R') {

(now->t_run)++;

if(now->t_run>=now->t_service) {

now->state='F'; now->t_finish=TIME; printf(\时间：%d]\\t\\n\

if(now!=NULL) fcfs(); }

else printf(\时间：%d]\\t进程：%s 正在运行，已运行时间：%d\\n\ }

else if(now->state=='F')

printf(\时间：%d]\\t无进程运行\\n\ }

void result()//结果的显示 {

pcb *p=head; //输出语句 printf(\运行结果===========\\n\\n\

printf(\名称 优先级 到达时间 开始时间 完成时间 服务时间 周转时间 带权周转时间\\n\ while(p!=NULL) {

进程：%s 任务完成

printf(\rive,

p->t_start,p->t_finish,p->t_service,p->t_finish-p->t_arrive, 1.0*(p->t_finish-p->t_arrive)/p->t_service); p=p->next; }

getchar();

}

void timer()//用timer来选取即将用的函数 {

if(TYPE=='1') fcfs(); else if(TYPE=='2') sjf(); else if(TYPE=='3') gyxb(); else if(TYPE=='4') sjplz(); if(now==NULL) return; TIME++; Sleep(DELAY); timer(); }

void init() {

pcb *p,*q; unsigned short i;

printf(\

3NEMO===========================\\n\\n\

实

验

printf(\ ***输入服务类型*** \\n\

printf(\ 1:先来先服务\\n\

printf(\ 2:短作业优先\\n\

printf(\ 3:高优先权优先\\n\printf(\ 4:时间片轮转\\n\

scanf(\ printf(\输入进程数目:\\n\ scanf(\

for(i=0; i

p=(pcb *)malloc(sizeof(pcb));

printf(\第%d个] 依次输入：名称 优先权 到达时间 服务时间 \\n\

scanf(\ if(head==NULL) {

head=p; q=p; }

q->next=p;//利用确定的p，q指针进行初始化 p->t_start=0; p->t_finish=0; p->t_run=0; p->t_wait=0; p->next=NULL; p->state='N'; q=p; }

getchar();

}

//按到达时间冒泡排序 pcb* sort_pcb(pcb *h_head) {

pcb *p,*p1,*p2,*p3;//设置p,p1,p2,p3,p4四个指针 pcb h, t;

if (h_head == NULL) return NULL; h.next=h_head;

p=&h; //p作为指针，存储了h的地址 while (p->next!=NULL) {

p=p->next; }

p=p->next=&t; while (p!=h.next)// {

p3=&h; p1=p3->next; p2=p1->next; while (p2!=p) {

if ((p1->t_arrive)>(p2->t_arrive))//按到达的时间比较 {

p1->next=p2->next; p2->next=p1; p3->next=p2; p3=p2; p2=p1->next;

} else {

p3=p1; p1=p2; p2=p2->next; } } p=p1; }

while (p->next!=&t) {

p=p->next; }

p->next=NULL; return h.next; }

void main() { init();

system(\ head=sort_pcb(head); now=head;

printf(\进程正在运行……\\n\ timer(); result(); return; }

4、运行结果以及结论。

本文来源：https://www.bwwdw.com/article/uhmp.html