操作系统实验三 进程调度

操作系统实验

实验三 进程调度

学号 姓名 班级

华侨大学电子工程系

一、实验目的

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

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

二、实验内容与基本要求

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

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

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

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

优先级调度算法细分成如下两种方式：

非抢占式优先级算法：

在这种调度方式下，系统一旦把处理机分配给就绪队列中优先级最高的进程后，该进程就能一直执行下去，直至完成；或因等待某事件的发生使该进程不得不放弃处理机时，系统才能将处理机分配给另一个优先级高的就绪进程。

抢占式优先级调度算法

在这种调度方式下，进程调度程序把处理机分配给当时优先级最高的就绪进程，使之执行。一旦出现了另一个优先级更高的就绪进程时，进程调度程序就停止正在执行的进程，将处理机分配给新出现的优先级最高的就绪进程。

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

对于时间片轮转法，时间片大小的确定是很重要的。一般可根据以下三点确定时间片大小：

1.系统对响应时间的要求 2.就绪队列中进程的数目 3.系统的处理能力

四、 程序流程图 1、 总流程图

输入进程数目创建进程就绪队列链表让用户依次输入各进程名、开始时间、运行时间、优先级打印创建后的进程链表，以便用户查看算法类型选择界面1、先来先服务算法2.时间片轮转算法3.优先级算法4、退出

2、时间片轮转算法流程图

在进入本算法前，已输入就绪队列及时间片值是判断进程就绪队列是否为空否剩余运行时间是否为0？否剩余运行时间是否大于时间片是否执行该进程，并将其剩余运行时间置0,将该进程的剩余运行时间置为原剩余运行时间与时间片timeturn的差完成标志位time2自加一就绪队列首进程移位否time2是否等于输入的进程数n是算法结束，返回算法选择界面

3、优先级算法流程图 采用非抢占式优先级算法。

输入就绪队列各进程PCB的参数，如进程名、到达时间等就绪队列是否为null是否将就绪队列链表按优先级排序就绪队列移位，队首变为优先级次高的进程执行就绪队列队首的进程直至完成将完成的进程移出就绪队列否就绪队列是否为空是算法结束，返回算法选择界面

五、 程序及注释

#include #include #include #include #include #include

struct pcb { };

typedef struct pcb PCB; 以后都可以用PCB去定义

//各子程序的声明 void *creat(int n);

//将struct pcb定义为新的数据类型PCB，这样

char name[10]; int come_time; int run_time; int VIP;

//进程名 //进程到达时间 //运行时间 //优先级

//定义名为pcb的结构体

struct pcb *next; //链表指针

void Firstcome_Firstserve(PCB *head); void Menue(PCB *head,int n); void*My_Copy(PCB *head); void Print( PCB *head,int len);

void TimeTurn_Firstserve(PCB *head,int timeturn,int n); void VIP_Firstserve(PCB *head);

/************************************************************************/

/* *创建进程就绪队列链表* */

/************************************************************************/

void *creat(int n) {

PCB *head,*p,*q;

assert (head=(PCB*)malloc(sizeof(PCB)));

//malloc函数向系统

申请分配sizeof(PCB)个字节的内存空间

息

getchar(); gets(q->name);

puts(\进程开始时间\p=head; p->next=NULL;

while(n--) {

p=head;

if( ( q=(PCB*)malloc(sizeof(PCB))) == NULL) { }

puts(\进程名:\

//开始读入PCB的信

printf(\exit(0);

}

}

scanf(\puts(\进程运行时间\scanf(\puts(\优先级\scanf(\if(p->next==NULL) { } else {

while (p->next!=NULL && q->come_time >p->next->come_time ) { }

q->next=p->next; p->next=q;

q->next=NULL; p->next=q;

//在插入节点时排序

p=p->next;

}

return head;

/************************************************************************/

/* 拷贝链表 */

/************************************************************************/

void *My_Copy(PCB *head1) { }

/********************************打印就绪队列链表

PCB *head2=NULL; PCB *p2=NULL; PCB *p1=head1->next; PCB *node=NULL;

assert(head2=(PCB*)malloc(sizeof(PCB))); p2=head2;

while(p1!=NULL) { }

return head2;

assert(node = (PCB*)malloc(sizeof(PCB)));

strcpy(node->name,p1->name); node->come_time=p1->come_time; node->run_time=p1->run_time; node->VIP=p1->VIP;

node->next=NULL; p2->next=node;

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

//p1、p2指针后移

//拷贝进程

//新链表头结点

*****************************************/

void Print( PCB *head,int len) {

printf(\

puts(\进程名 到达时间 运行时间 优先级\for(i=0;inext) {

head=head->next; int i=0;

,head->VIP);

}

/************************************************************************/

/* *时间片轮转算法* */

/************************************************************************/

void TimeTurn_Firstserve(PCB *head,int timeturn,int n) {

PCB *Head=My_Copy(head); PCB *p; int time;

}

static int time2=0;

p=head->next; while(p!=NULL) {

//time2为完成标志位，对完成的进程的计数位

//判断进程就绪队列是否为空

if(p->run_time!=0 && p->run_time<=timeturn) //若剩

余运行时间不为0，且剩余运行时间不大于时间片，则执行以下指令

{

time=p->run_time;

printf(\进程:%-5s 到达时间:%-5d,剩余运行时间:%-5d,优先

级:%d\\n\

while(time) { } puts(\p->run_time=0; time2++;

//time2自加，表示已完成进程

printf(\正在执行 %d \\r\time--; Sleep(1000);

多了一个

} else

if(p->run_time!=0 && p->run_time>timeturn)

//若剩

余运行时间不为0，且剩余运行时间大于时间片，则执行以下指令

{

time=timeturn;

printf(\进程:%-5s到达时间:%-5d,剩余运行时间:%-5d,优先

级:%d\\n\

while(time)

{ } puts(\

p->run_time -= timeturn;

//run_time被置为了

printf(\正在执行 %d \\r\time--; Sleep(1000);

runtime-timeturn

算法

}

/************************************************************************/

/* *优先级优先* */

/************************************************************************/

void VIP_Firstserve(PCB *head) {

PCB *Head=My_Copy(head);

return; }

}

p=p->next; if(p==NULL) { }

if(time2==n)

//若所有的进程都已完成，则退出本

p=head->next;

建

PCB *Head_Link;//建新队列

PCB *Link,*node;//建节点，在新队列中会用到。 PCB *flg;//标记指针的位置 PCB *p,*q; static int flag0;

int time_over; //进程结束时间 int time1;

p = Head; q = p->next;

assert(Head_Link = (PCB*)malloc(sizeof(PCB))); //新队列的头结点的创

Head_Link->next = NULL;

while(q->next != NULL) {

if(q==Head->next) {

if(flag0==0) {

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,

优先级:%d\\n\

while(time_over) {

time_over=q->run_time;

printf(\正在执行 %d \\r\Sleep(1000);

}

puts(\执行完毕！\

flag0++;

}// end of if(flag0==0) else if(flag0==1) {

if(q->next->come_time > q->run_time) //等待下一个进程 {

time1 = q->next->come_time - q->run_time; //等待时间 puts(\while(time1) { }

printf(\time1--; Sleep(1000);

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

间:%-5d,优先

级:%d\\n\

time_over = q->next->run_time; while(time_over) { }

puts(\执行完毕！\

printf(\正在执行 %d \\r\time_over--; Sleep(1000);

p = q; q = q->next;

} //end of if (q->next->come_time > q->run_time) else if(q->next->come_time <= q->run_time) //将 在q进程

执行完之前，就进入的进程入队。

time_over))

点

节点

节点

节点

节点

{ time_over = q->run_time;

while((q->next != NULL) && (q->next->come_time < {

assert(node=(PCB*)malloc(sizeof(PCB))); //建节

node->come_time=q->next->come_time;

//拷贝

strcpy(node->name,q->next->name);

//拷贝

node->run_time=q->next->run_time;

//拷贝

node->VIP=q->next->VIP;

//拷贝

//插入 法按短作业升序 插入节点， if(Head_Link->next == NULL) { flg = q;//标记 node->next = NULL; Head_Link->next = node;

}

else

{

if(node->VIP < Head_Link->next->VIP) { } else {

Link = Head_Link->next; flg = q;

node->next = Head_Link->next; Head_Link->next = node;

//while((Link->next != NULL) &&

(node->run_time > Link->next->run_time)) 2010_11_15修改

while((Link->next != NULL) &&

(node->VIP > Link->next->VIP))

}

q = q->next;

}

node->next = Link->next; Link->next = node;

{ }

Link = Link->next;

}//end of while((q->next != NULL) &&

(q->next->come_time < time_over))

//执行队里的头进程

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

间:%-5d,优先

级:%d\\n\

run_time,Head_Link->next->VIP);

///////////////////////////////////////////////////////////////////////

time1 = Head_Link->next->run_time; while(time1) { }

puts(\执行完毕！\

Link = Head_Link->next;

Head_Link->next = Head_Link->next->next; free(Link); p = flg;

printf(\正在执行 %d \\r\time1--; Sleep(1000);

}//end of else if(q->next->come_time <= q->run_time)

}// end of else if(flag0==1)

}// end of if(q==Head_Link->next)

///////////////////////////////////////

else {

time_over = q->come_time + q->run_time;

if(q->next->come_time >= time_over)//假如q 的下一个进程在他

结束后还未到达。等待（队为空）还是出队首进程（对非空） 。。

{

if(Head_Link->next == NULL) //队为空时 1。先执行等待

进程 2。判断等待进程完成之前有无进程等待

{

time1 = q->next->come_time - time_over;

puts(\while(time1) { }

//执行该进程

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

printf(\time1--; Sleep(1000);

间:%-5d,优先

级:%d\\n\

time1 = q->next->run_time; while(time1) { }

puts(\执行完毕！\

//将 在p的next进程执行完成之前的进程 入队 time_over = q->run_time + q->come_time;

while((q->next != NULL) && (q->next->come_time <

printf(\正在执行 %d \\r\time1--; Sleep(1000);

time_over))

点

{

assert(node=(PCB*)malloc(sizeof(PCB))); //建节

node->come_time=q->next->come_time; //拷贝节点 strcpy(node->name,q->next->name); //拷贝节点 node->run_time=q->next->run_time; //拷贝节点 node->VIP=q->next->VIP; //拷贝节点

//插入 法按短作业升序 插入节点， if(Head_Link->next == NULL) { } else {

if(node->VIP < Head_Link->next->VIP) { } else {

Link = Head_Link->next;

while((Link->next != NULL) && flg = q;

node->next = Head_Link->next;

Head_Link->next = Head_Link->next->next; flg = q;//标记 node->next = NULL; Head_Link->next = node;

(node->VIP > Link->next->VIP))

{ }

node->next = Link->next;

Link = Link->next;

}

}

Link->next = node;

}//end of while((q->next != NULL) &&

(q->next->come_time < time_over))

//执行队里的头进程 if(Head_Link->next!=NULL) {

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

间:%-5d,优先

级:%d\\n\run_time,Head_Link->next->VIP);

} else {

q = q->next;

time1 = Head_Link->next->run_time; while(time1) { }

puts(\执行完毕！\

Link = Head->next;

Head_Link->next = Head_Link->next->next; free(Link); q = flg;

printf(\正在执行 %d \\r\time1--; Sleep(1000);

}

}

else if(Head_Link->next != NULL) {

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

间:%-5d,优先

级:%d\\n\run_time,Head_Link->next->VIP);

time1 = Head_Link->next->run_time; while(time1) { }

puts(\执行完毕！\

Link = Head->next;

Head_Link->next = Head_Link->next->next; free(Link); p = flg;

printf(\正在执行 %d \\r\time1--; Sleep(1000);

}//end of else if(Head_Link->next != NULL)

}//end of if(q->next->come_time > time_over) else {

time_over = q->run_time;

while((q->next != NULL) && (q->next->come_time <

time_over))

{

Link->next->VIP))

assert(node=(PCB*)malloc(sizeof(PCB))); //建节点 node->come_time=q->next->come_time; //拷贝节点 strcpy(node->name,q->next->name); //拷贝节点 node->run_time=q->next->run_time; //拷贝节点

node->VIP=q->next->VIP; //拷贝节点

//插入 法按短作业升序 插入节点， if(Head_Link->next == NULL) { flg = q;//标记 node->next = NULL; Head_Link->next = node;

} else { if(node->VIP < Head_Link->next->VIP) { flg = q;

node->next = Head_Link->next;

Head_Link->next = Head_Link->next->next; } else { Link = Head_Link->next;

while((Link->next != NULL) && (node->VIP > {

Link = Link->next;

}

}

}

node->next = Link->next; Link->next = node;

}//end of while((q->next != NULL) && (q->next->come_time

< time_over))

优先

级:%d\\n\run_time,Head_Link->next->VIP);

}

if( Head_Link ->next != NULL)

}

time1 = Head_Link->next->run_time; while(time1) { }

puts(\执行完毕！\

Link = Head->next;

Head_Link->next = Head_Link->next->next; free(Link); p = flg;

printf(\正在执行 %d \\r\time1--; Sleep(1000);

//执行队里的头进程

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,

}//end of else

{

Link = Head_Link->next; while(Link != NULL) {

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先

级:%d\\n\

}

/************************************************************************/

/* *先来先服务算法* */

/************************************************************************/

void Firstcome_Firstserve(PCB *head) {

PCB *Head=My_Copy(head); int counter=1; PCB *h=Head->next; }

}

time1 = Link->run_time; while(time1) { }

Link = Link->next;

printf(\正在执行 %d \\r\time1--; Sleep(1000);

PCB *p;

int time; //进程结束时间, int time2;

while(h!=NULL) {

if(h==Head->next) {

puts(\

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,优先

级:%-5d\\n\

} else {

time=p->run_time+p->come_time ;

if(time < h->come_time) //p结束但是h还未到达 h的开始

时间就是到达时间

{

puts(\

// Sleep(p->run_time*1000); 2010_06修改 ：优化 while(p->run_time) { }

printf(\执行结束！\\n\

time2=h->come_time-time;

printf(\正在执行 %d \\r\p->run_time--; Sleep(1000);

printf(\等待下一个进程\while(time2>0) { } puts(\

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时间:%-5d,

printf(\Sleep(1000); time2--;

优先级:%d\\n\

优化

while(p->run_time) { }

printf(\执行结束！\\n\

puts(\

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

printf(\正在执行 %d \\r\p->run_time--; Sleep(1000);

} else

if(time == h->come_time)//p结束而且h刚好到达 {

// Sleep(p->run_time*1000);

2010_06修改 ：

间:%-5d,优先级:%d\\n\

} else

if(time > h->come_time)//p结束前h已到达

{

puts(\

time2=p->run_time-(time-h->come_time); //p从

到来至h进程等待钱执行时间

while(time2) { }

printf(\进程:%-5s等待\\n\time2=time-h->come_time;

while(time2) //p从h

printf(\正在执行 %d \\r\Sleep(1000);

等待到完成市时间

{ }

printf(\进程:%-5s正在运行，到达时间:%-5d,运行时

printf(\正在执行 %d \\r\Sleep(1000);

间:%-5d,优先级:%d\\n\

}

/************************************************************************/

/* *用户菜单*

}

}

counter++; p=h; h=h->next;

}

*/

/************************************************************************/

void Menue(PCB *head,int n) {

int choice;

//定义时间片

int timeturn; int LOOP=1;

while(LOOP) ┐\\n\

\\n\

\\n\

\\n\

printf(\printf(\

│ 4.退出 │\\n\ └──────────────────┘\\n\

printf(\

│ 3.先来先服务算法 │

printf(\

│ 2.时间片轮转算法 │

printf(\

│ 1.优先级服务算法 │

{

printf(\┌──────────────────

printf(\请输入您的选择：\\n\

scanf(\switch(choice) { case 1:

VIP_Firstserve(head);break;

case 2:

printf(\输入时间片：\\n\scanf(\

TimeTurn_Firstserve(head,timeturn,n);break;

case 3:

Firstcome_Firstserve(head);break;

case 4:

exit(0);

default: LOOP=0; break;

}

}

}

/*****************************主函数部分***************************************/

void main() {

PCB *head; int n;

printf(\

| _______________ | \\n\\ | I I | \\n\\ | I 姜博玮 I | \\n\\ | I 1115107019 I | \\n\\ | I 11电子2 I | \\n\\ | I_____________I | \\n\\ !_________________! \\n\\ \

//n为创建的进程数目

}

printf(\请输入进程个数:\\n\scanf(\head=creat(n);

Print(head,n);

Menue(head,n);

//请用户选择算法类型

//将创建后的进程链表打印，以便用户查看

//创建进程就绪队列链表

六、 运行结果及结论 运行结果：

输入3个进程，a、b、c，命名、开始、到达时间、优先级等信息如图所示；

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