进程调度算法课程设计报告

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

设计时间： 2011-1-9 至 2011-1-13 专业年级： 2008 级计算机科学与技术 4 班 一.设计目的：通过课程设计, 加深对操作系统各资源管理模块的理解,掌握操作系统的基本原理及功能, 具有初步 分析实际操作系统、设计、构造和开发现代操作系统的基本能力。

二.设计内容：2.题目：进程调度算法的设计 设计要求： ①设计进程控制块 PCB 表结构，分别适用于优先数调度算法和循环轮转调度算法。 ②建立进程就绪队列。对两种不同算法编制入链子程序。 ③编制两种进程调度算法：1)优先数调度；2)循环轮转调度开发环境：VC++6.0

设计技术参数: ①本程序用两种算法对五个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。 ②为了便于处理，程序中的某进程运行时间以时间片为单位计算。各进程的优先数或轮转时间数以及进程需运行的时间片数的初始值均由用户给定。

③在优先数算法中，优先数的值为 50 与运行时间的差值，即 P_TIME-process->needtime。进程每执行一次，优先数减 3,CPU 时间片数加 1,进程还需要的时间片数减 1。在轮转算法中，采用固定时 间片(即：每执行一次进程，该进程的执行时间片数为已执行了 2 个单位) ,这时，CPU 时间片数加 2, 进程还需要的时间片数减 2,并排列到就绪队列的尾上。

④对于遇到优先数一致的情况，采用 FIFO 策略解决。

三.设计过程 1、 2、 实现功能 添加功能

分别用优先数调度算法和循环轮转调度算法，实现对进程调度算法的模拟。

/* 函数功能： 将进程就绪队列中第一个放进就绪队列第 1 页 共 18 页

进程调度算法课程设计

函数原型： void firstin(void)

函数参数： void

函数返回值：void

*/

void firstin(void)

{

if(ready!=NULL)

{

run=ready;

ready=ready->next;

run->state='R';

run->next=NULL;

}

else

{

run=NULL;

}

}

Insert（）

/*

函数功能：优先级法调度将进程插入到就绪队列算法

函数原型：void insert1(PCB *q)

函数参数：PCB *q 待插入的队列进程控制块

优先级越高，插入越靠前

函数返回值：void

*/

void insert1(PCB *q)

{

PCB *p,*s,*r; /*p,r用来控制就绪队列滚动，S指向插入的队列*/

int b; /*b作为插入控制标志的*/

s=q;

p=ready;

r=p;

b=1;

if(s->prio>=ready->prio)

{

s->next=ready;

ready=s;

}

else

{

while((p!=NULL)&&b)

{

if(p->prio>=s->prio)

进程调度算法课程设计

r=p;

p=p->next;

}

else

{

b=0;

}

}

s->next=p;

r->next=s;

}

}

/*

函数功能：时间片轮转算法调度将进程插入到就绪队列算法

函数原型：void insert2(PCB *q)

函数参数：PCB *q 待插入的队列进程控制块

函数返回值：void

*/

void insert2(PCB *q)

{

tail->next=q;

tail=q;

q->next=NULL;

}

3、 设计思路

首先设计分成三个主要部分：

1优先数算法及其服务函数的设计:

首先是主算法函数priority的设计，在此函数中，优先数的值为50与运行时间的差值，即P_TIME-process->needtime。进程每执行一次，优先数减3，CPU时间片数加1，进程还需要的时间片数减1。随后设计为之服务的函数pcreate_task和insert1，负责创建任务和将进程插入到就绪队列中，最后设计相应的输出函数prt1，以输出进程运行状态。 2循环轮转调度算法及其服务函数的设计:

首先是主算法函数roundrun的设计，函数中采用固定时间片（每执行一次进程，该进程的执行时间片数为已执行了2个单位），CPU时间片数加2，进程还需要的时间片数减2，并排列到就绪队列的尾上。随后设计为之服务的函数rcreate_task和insert2，负责创建任务和将进程插入到就绪队列中，最后设计相应的输出函数prt2，以输出进程运行状态。 3主函数的设计：思路是输入用户一个选择性的字符（P或R），如果是P则执行优先数算法的程序，如果是R则执行循环轮转调度算法的程序。

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

4、

算法和流程图

Main 函数流程图： 开始

输入 P 或 R 到参数 algo

P

是 P 还 是R

R

以 pcreate_task 创建任务，代 表优先数算法

以 rcreate_task 创建任务，代 表轮转算法

priority(char algo),执行优 先数算法

roundrun(char algo) , 执行轮 转算法

终止

第 4 页 共 18 页

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

优先数算法流程图 开始

Y 进 程 运 行 完 毕？ N 运行数加 1; 需要时间减 1;优先数减 3;

是否运行完毕？ needtime==0? N

Y

N

就绪队列不空， 并且， 就绪队列队首优先数 大于运行的进程

run->next=finish; finish=run; run->state='F'; run=NULL;

Y run->state='W'; insert1(run); run=NULL;

将进程就绪队 列中第一个放 进运行队列

将进程就绪队 列中第一个放 进运行队列

打印运行情况

返回第 5 页 共 18 页

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

循环轮转调度算法流程图： 开始

Y 进 程 运 行 完 毕？ N 运行数加 1; 需要时间减 1;运行时间加 1;

是否运行完毕？ needtime==0? N

Y

N

时间片等于运行时间 run->count==run->ro und?

run->next=finish; finish=run; run->state='F'; run=NULL;

Y run->count=0;

将进程就绪队 列中第一个放 进运行队列

就绪队列 间为空？ run->count N ==run->rou run->state='W';insert2(rn; nd? firstin();

Y

打印运行情况

返回第 6 页 共 18 页

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

四．操作界面截图及分析

优先数调度算法运行过程：

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

回车直至结束：

进程调度算法课程设计

东莞理工学院操作系统课程设计报告

循环轮转调度算法运行过程：

进程调度算法课程设计

回车直至结束：

五.设计总结：

通过这次课程设计, 我加深了对进程调度算法的理解,掌握了操作系统中利用软件工程的方法和思想来设计大型软件的过程。基本掌握实际操作系统、设计、构造和开发的基本能力。将课本上学习到的理论知识与实际编程想结合，提高了实践的能力和经验，为以后进一步深造和钻研有关操作系统的学科建立了扎实的基础。

附录：

各程序主要函数及注释（用红色黑体标注自己设计的函数）

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

进程调度算法课程设计

/*进程控制块数据结构*/

typedef struct node

{

char name[10];/*进程名*/

int prio; /*进程优先级*/

int round; /*进程分配的时间片*/

int cputime; /*进程消耗的CUP时间*/

int needtime; /*进程需要的CUP时间*/

int count; /*进程运行时间*/

char state; /*进程的状态：'R':运行,'W'：等待,'F'：结束*/

struct node *next;/*指向下一个进程的指针*/

}PCB;

PCB *finish,*ready,*tail,*run;/*指向三个队列的队首的指针，tail为就绪队列的队尾指针*/

int N;/*定义进程的数目*/

/*

函数功能： 将进程就绪队列中第一个放进运行队列

函数原型： void firstin(void)

函数参数： void

函数返回值：void

*/

void firstin(void)

{

if(ready!=NULL)

{

run=ready;

ready=ready->next;

run->state='R';

run->next=NULL;

}

else

{

run=NULL;

}

}

/*

函数功能：输出进程信息的标题函数

函数原型：void prt1(char a)

函数参数：char a :a=='p'为优先级，=='r'为时间片轮转

函数返回值：void

*/

void prt1(char a)

进程调度算法课程设计

if(toupper(a)=='P')

{

printf("name cputime needtime priority state \n");

}

else

{

printf("name cputime needtime count round state \n");

}

}

/*

函数功能：输出单个进程信息的函数

函数原型：void prt2(char a,PCB *p)

函数参数：char a :a=='p'为优先级，=='r'为时间片轮转

PCB *p 为指向待输出的进程控制块的指针

函数返回值：void

*/

void prt2(char a,PCB *p)

{

if(toupper(a)=='P')

{

printf("%-7s%-9d%-10d%-10d%-5c\n",p->name,p->cputime,p->needtime,p->prio,p->state); }

else

{

printf("%-7s%-9d%-10d%-7d%-7d%-5c\n",p->name,p->cputime,p->needtime,p->count,p->round,p->state); }

}

/*

函数功能：输出所有进程信息的函数

函数原型：void prt(char algo)

函数参数：char a :a=='p'为优先级，=='r'为时间片轮转

函数返回值：void

*/

void prt(char algo)

{

PCB *p;

prt1(algo);

if(run!=NULL)

{

prt2(algo,run);

}

进程调度算法课程设计

while(p!=NULL)

{

prt2(algo,p);

p=p->next;

}

p=finish;

while(p!=NULL)

{

prt2(algo,p);

p=p->next;

}

getchar();

}

/*

函数功能：优先级法调度将进程插入到就绪队列算法

函数原型：void insert1(PCB *q)

函数参数：PCB *q 待插入的队列进程控制块

优先级越高，插入越靠前

函数返回值：void

*/

void insert1(PCB *q)

{

PCB *p,*s,*r; /*p,r用来控制就绪队列滚动，S指向插入的队列*/ int b; /*b作为插入控制标志的*/

s=q;

p=ready;

r=p;

b=1;

if(s->prio>=ready->prio)

{

s->next=ready;

ready=s;

}

else

{

while((p!=NULL)&&b)

{

if(p->prio>=s->prio)

{

r=p;

p=p->next;

}

进程调度算法课程设计

{

b=0;

}

}

s->next=p;

r->next=s;

}

}

/*

函数功能：时间片轮转算法调度将进程插入到就绪队列算法

函数原型：void insert2(PCB *q)

函数参数：PCB *q 待插入的队列进程控制块

函数返回值：void

*/

void insert2(PCB *q)

{

tail->next=q;

tail=q;

q->next=NULL;

}

/*

函数功能：采用优先级进程调度法时，进程初始化函数

函数原型：void pcreate_task(char algo)

函数参数：char algo:

函数返回值：void

*/

void pcreate_task(char algo)

{

PCB *p;

int i,time;

char na[10];

ready=NULL;

finish=NULL;

run=NULL;

for(i=0;i<N;i++)

{

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

printf("Enter the name of process\n");

scanf("%s",na);

printf("Enter the time of process\n");

scanf("%d",&time);

strcpy(p->name,na);

进程调度算法课程设计

p->needtime=time;

p->state='W';

p->prio=50-time;

if(ready==NULL)

{

ready=p;

ready->next=NULL;

}

else

{

insert1(p);

}

printf("Output the waiting processes information\n"); prt(algo);

}

firstin();

}

/*

函数功能：采用时间片轮转法进程调度法时，进程初始化函数 函数原型：void rcreate_task(char algo)

函数参数：char algo: R

函数返回值：void

*/

void rcreate_task(char algo)

{

PCB *p;

int i,time;

char na[10];

ready=NULL;

finish=NULL;

run=NULL;

for(i=0;i<N;i++)

{

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

printf("Enter the name of process\n");

scanf("%s",na);

printf("Enter the time of process\n");

scanf("%d",&time);

strcpy(p->name,na);

p->cputime=0;

p->needtime=time;

p->count=0;

p->state='W';

进程调度算法课程设计

if(ready!=NULL)

{

insert2(p);

}

else

{

p->next=ready;

ready=p;

tail=p;

}

printf("Output the waiting processes information\n");

prt(algo);

}

run=ready;

ready=ready->next;

run->state='R';

}

/*

函数功能：采用优先级进程调度法时，进程调度函数

函数原型：void priority(char algo)

函数参数：char algo:进程调度类别标志：'P'优先级 'R'时间片轮转 函数返回值：void

*/

void priority(char algo)

{

while(run!=NULL)

{

run->cputime+=1;

run->needtime-=1;

run->prio-=3;

if(run->needtime==0)

{

run->next=finish;

finish=run;

run->state='F';

run=NULL;

firstin();

}

else

{

if((ready!=NULL)&&(run->prio<ready->prio))

{

run->state='W';

insert1(run);

进程调度算法课程设计

firstin();

}

}

prt(algo);

}

}

/*

函数功能：采用时间片轮转法进程调度法时，进程调度函数 函数原型：void roundrun(char algo)

函数参数：char algo: R

函数返回值：void

*/

void roundrun(char algo)

{

while(run!=NULL)

{

run->cputime=run->cputime+1;

run->needtime=run->needtime-1;

run->count=run->count+1;

if(run->needtime==0)

{

run->next=finish;

finish=run;

run->state='F';

run=NULL;

if(ready!=NULL)

{

firstin();

}

}

else

{

if(run->count==run->round)

{

run->count=0;

if(ready!=NULL)

{

run->state='W';

insert2(run);

firstin();

}

}

}

进程调度算法课程设计

}

}

/*main 函数，运行直到用户退出*/

int main()

{

char algo;

char flag='Y';

char f=1;

while(toupper(flag)=='Y'){

printf("Choose the type of attemper P:priority R:timeround\n"); if(f==0){

getchar();

}

scanf("%c",&algo);

printf("Please enter the number of processes N:\n");

if(f==0){

getchar();

}

scanf("%d",&N);

if((algo=='P')||(algo=='p'))

{

pcreate_task(algo);

priority(algo);

}

else if((algo=='r')||(algo=='R'))

{

rcreate_task(algo);

roundrun(algo);

}

printf("Run one more time?(Y/N)\n");

scanf("%c",&flag);

f=0;

}

return 0;

}

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