基于多队列反馈的进程调度

《操作系统》综合实训项目设计文档

【大纲】

（不用打印，提交电子稿即可！）

一、 基本信息

项目名称：成人姓名、学号、完成日期 项目名称：基于时间片的多队列反馈的进程管理系统 完成日期:2017.5.24

二、 实验内容与目的

实验内容：编写程序完成单处理器系统的进程调度，要求采用基于

时间片多队列反馈式调度策略调度策略。 具体内容：

1.确定PCB内容及其组织方式。

2.要求模拟进程空闲（新）、就绪、运行、阻塞和完成5个状态。 3.实现进程创建、进程调度、进程阻塞、进程唤醒和进程撤销5个原语。

4.能够模拟进程从生到灭的完整过程。

实验目的:

1.加深进程概念理解，明确进程与程序区别。

教育资料

.

2.理解操作系统中进程的组织、创建和调度等方法。

三、 主要设计思路和流程图

设计思路： 1定义数据结构 2.设置队列 3.创建进程

4.创建的进程进入就绪队列 5.多级反馈调度

1.）在第一就绪队列里的进程被调度运行，进程状态由等待变为运行，设置时间片计数器，每次运行加1，时间片满后，该进程出队列，进入下一级别的就绪队列。若是在最后一级别的队列，则在该队列中进行时间片轮转调度

2.）运行进程若是被阻塞的话，该进程出就绪队列，进入阻塞队列，状态变为阻塞态

3.）若是唤醒被阻塞进程，则阻塞进程根据其时间片计数器计入相应的就绪队列

4.）撤销进程，该进程直接出就绪队列

四、 主要数据结构及其说明

typedef struct Node {

char name[20];

教育资料

.

char state;//进程所处的状态,N新建，W等待，B阻塞，R运行，F结束

int round;//时间片计数器 int time;//运行时间 struct Node *next; }LinkQueueNode,*PCB;//定义PCB typedef struct {

LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue;//定义队列

void initQueue(LinkQueue *Q)//队列的初始化函数 void Initializa()//初始化所有队列 void RunPrintf()//打印运行队列 void BlockPrintf()//打印阻塞队列

void ReadyPrintf(LinkQueue q)//打印就绪队列 void putout()//输出函数

void EnterQueue(LinkQueue *Q,PCB *p)//进程插入队列函数 int DeleteQueue(LinkQueue *Q,PCB *p)//进程出队列

void TransferRun(LinkQueue *q1,LinkQueue *q2,PCB q)//进程出就绪队列，入运行队列

void Transfer(LinkQueue *q1,LinkQueue *q2,PCB q)

教育资料

.

//进程唤醒或阻塞时队列转换的函数 int MultiDiapatch()

//调度函数，若此队列运行的进程时间片满，则进入下一级队列 int run()//模拟运行 void block()//模拟阻塞 void wake()//模拟唤醒

int Createprocess(LinkQueue *Q)//进程的创建 void meanu()//菜单函数

五、 程序运行时的初值和运行结果

教育资料

.

教育资料

.

教育资料

.

教育资料

.

教育资料

.

教育资料

.

教育资料

.

六、 源程序并附上注释【可是另一个源程序文

件，在此应说明该文件名】

#include #include #include #include

教育资料

.

typedef struct Node {

char name[20];

char state;//进程所处的状态,N新建，W等待，B阻塞，R运行，F结束

int round;//时间片计数器 int time;//运行时间 struct Node *next; }LinkQueueNode,*PCB;//定义PCB typedef struct {

LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue; int count=0;

LinkQueue qRun,qBlock,qReady1,qReady2,qReady3,qReady4;//定义四个就绪队列

void initQueue(LinkQueue *Q)//队列的初始化函数 {

Q->front

=

(LinkQueueNode

*)malloc(sizeof(LinkQueueNode)); if(Q->front!=NULL)

教育资料

.

{

Q->rear=Q->front; Q->front->next=NULL; } }

void Initializa()//初始化所有队列 {

initQueue(&qRun); initQueue(&qBlock); initQueue(&qReady1); initQueue(&qReady2); initQueue(&qReady3); initQueue(&qReady4); }

void RunPrintf()//打印运行队列 { PCB p;

printf(\"运行队列:\"); p=qRun.front->next; while(p) {

printf(\"%s\\

教育资料

.

p=p->next; }

p=qRun.front->next; printf(\"\\n需要时间:\"); while(p) {

printf(\"%d\\ p=p->next; }

printf(\"\\n进程状态:\"); p=qRun.front->next; while(p) {

printf(\"%c\\ p=p->next; } }

void BlockPrintf()//打印阻塞队列 { PCB p;

printf(\"\\n\\n阻塞队列:\");

教育资料

.

p=qBlock.front->next; while(p) {

printf(\"%s\\ p=p->next; }

printf(\"\\n需要时间:\"); p=qBlock.front->next; while(p) {

printf(\"%d\\ p=p->next; }

printf(\"\\n进程状态:\"); p=qBlock.front->next; while(p) {

printf(\"%c\\ p=p->next; } }

void ReadyPrintf(LinkQueue q)//打印就绪队列

教育资料

.

{ PCB p;

p=q.front->next; while(p) {

printf(\"%s\\ p=p->next; }

printf(\"\\n需要时间:\"); p=q.front->next; while(p) {

printf(\"%d\\ p=p->next; }

printf(\"\\n进程状态:\"); p=q.front->next; while(p) {

printf(\"%c\\ p=p->next; }

教育资料

.

}

void putout()//输出函数 {

PCB p;

printf(\"**************************************************************\\n\");

printf(\"**************************************************\");

printf(\"\\n**************************************************************\\n\");

printf(\"说明:程序中四个就绪队列的时间片分别为10，15，20，30\");

printf(\"\\n**************************************************************\\n\");

printf(\"**********************************************************\\n\");

printf(\"1.创建进程 2.阻塞进程 3.唤醒进程 4.撤销进程 0.退出\\n\");

printf(\"**************************************************************\\n\");

教育资料

多级反馈调度

菜单

.

RunPrintf(); BlockPrintf();

printf(\"\\n\\n队 列1:\"); ReadyPrintf(qReady1); printf(\"\\n\\n队 列2:\"); ReadyPrintf(qReady2); printf(\"\\n\\n队 列3:\"); ReadyPrintf(qReady3); printf(\"\\n\\n队 列4:\"); ReadyPrintf(qReady4);

printf(\"\\n**************************************************************\\n\"); }

void EnterQueue(LinkQueue *Q,PCB *p)//进程插入队列函数 {

(*p)->next=NULL; Q->rear->next=*p; Q->rear=*p; }

int DeleteQueue(LinkQueue *Q,PCB *p)//进程出队列 {

if(Q->front==Q->rear)

教育资料

.

return 0; *p=Q->front->next; Q->front->next=(*p)->next; if(Q->rear==*p) Q->rear=Q->front; return 1; }

void TransferRun(LinkQueue *q1,LinkQueue *q2,PCB q)//进程出就绪队列，入运行队列 {

DeleteQueue(q1,&q); q->state='R'; EnterQueue(q2,&q); }

void runprocess() { PCB p;

int state1=0,state2=0,state3=0,state4=0; //state来判断就绪队列是否还有进程 if(qReady1.front!=qReady1.rear) {

TransferRun(&qReady1,&qRun,p);

教育资料

.

state1=1; } else {

if(qReady2.front!=qReady2.rear) {

TransferRun(&qReady2,&qRun,p); state2=1; } else {

if(qReady3.front!=qReady3.rear) {

TransferRun(&qReady3,&qRun,p); state3=1; } else {

if(qReady4.front!=qReady4.rear) {

TransferRun(&qReady4,&qRun,p); state4=1;

教育资料

.

} } } }

if(state1==0&&state2==0&&state3==0&&state4==0) {

printf(\"队列中无就绪进程！\"); } else {

system(\"cls\"); putout(); } }

void Transfer(LinkQueue *q1,LinkQueue *q2,PCB q) //进程唤醒或阻塞时队列转换的函数 {

DeleteQueue(q1,&q); q->state='W'; EnterQueue(q2,&q); }

int MultiDiapatch()

教育资料

.

//调度函数，若此队列运行的进程时间片满，则进入下一级队列 { PCB p;

qRun.front->next->time--; ++count;

if(qRun.front->next->time==0) {

DeleteQueue(&qRun,&p); free(p); runprocess(); count=0; } else

if(qRun.front->next->round==count) {

if(count==10) {

qRun.front->next->round=15; Transfer(&qRun,&qReady2,p); }

if(count==15) {

教育资料

.

qRun.front->next->round=20; Transfer(&qRun,&qReady3,p);

}

if(count==20) {

qRun.front->next->round=30; Transfer(&qRun,&qReady4,p);

}

if(count==30) {

qRun.front->next->round=30; Transfer(&qRun,&qReady4,p);

}

runprocess(); count=0; } }

int run()//模拟运行 {

教育资料

.

if(qRun.front==qRun.rear)//运行队列空，则进行进程队列转换 runprocess(); else {

MultiDiapatch(); system(\"cls\"); putout(); } }

void block()//模拟阻塞 { PCB p;

if(qRun.front!=qRun.rear)//运行队列不为空，则运行进程出运行队列，进入阻塞队列 {

DeleteQueue(&qRun,&p); p->state='B';

EnterQueue(&qBlock,&p); system(\"cls\"); putout(); } else

教育资料

.

{

system(\"cls\"); putout();

printf(\"队列中没有进程在运行！\"); } }

void wake()//模拟唤醒 { PCB p;

if(qBlock.front!=qBlock.rear) {

//根据时间片；来决定进入的就绪队列 if(qBlock.front->next->round==10) {

Transfer(&qBlock,&qReady1,p); } else {

if(qBlock.front->next->round==15) {

Transfer(&qBlock,&qReady2,p);

教育资料

} } else {

教育资料

.

} else {

if(qBlock.front->next->round==20) {

Transfer(&qBlock,&qReady3,p); } else {

if(qBlock.front->next->round==30) {

Transfer(&qBlock,&qReady4,p); } } } .

system(\"cls\"); putout();

printf(\"无等待进程!\"); } }

void endprocess() { PCB p;

if(qRun.front==qRun.rear) {

printf(\"信息提示:无运行进程,请按Enter键运行进程!\"); } else {

DeleteQueue(&qRun,&p); free(p); system(\"cls\"); putout();

printf(\"信息提示:选择菜单功能或按Enter键执行进程!\"); } }

int CompareStr(LinkQueue q,char name[20])//比较字符串是否相

教育资料

.

同 {

PCB p;

p=q.front->next; while(p) {

if(strcmp(p->name,name)==0) {

return 0; }

p=p->next; } return 1; }

int CompareName(char name[20]) { PCB p;

p=qRun.front->next; int flag;

flag=CompareStr(qRun,name); if(flag==0) return 0;

教育资料

.

flag=CompareStr(qBlock,name); if(flag==0) return 0;

flag=CompareStr(qReady1,name); if(flag==0) return 0;

flag=CompareStr(qReady2,name); if(flag==0) return 0;

flag=CompareStr(qReady3,name); if(flag==0) return 0;

flag=CompareStr(qReady4,name); if(flag==0) return 0; return 1; }

int Createprocess(LinkQueue *Q)//进程的创建 {

PCB p; char n[20];

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

教育资料

.

printf(\"进程名: \"); fflush(stdin); scanf(\"%s\

while(!CompareName(n))//判断是否创建了已经创建过的进程 {

printf(\"已经有相同名字的进程存在\"); printf(\"\\n请重新输入未创建过的进程:\"); fflush(stdin); scanf(\"%s\ }

strcpy(p->name,n); printf(\"所需时间: \"); fflush(stdin);

scanf(\"%d\ while(p->time<0) {

printf(\"输入不合法\"); fflush(stdin);

scanf(\"%d\ }

p->state='W'; p->round=10;

教育资料

.

p->next=NULL; EnterQueue(Q,&p); }

void meanu()//菜单函数 {

char c;

printf(\"\\n选择功能：\"); scanf(\"%c\ while(1) {

if(c=='1') {

Createprocess(&qReady1); system(\"cls\"); putout();

printf(\"\\n选择菜单功能或者按程:\\n\");

while(1) {

fflush(stdin); scanf(\"%c\ if(c=='\\n')

教育资料

enter执行进 .

{

run();

printf(\"\\n选择功能或者按enter继续执行:\");

} else break; } }

else if(c=='2') {

if(c=='\\n') {

run();

printf(\"\\n行:\");

教育资料

printf(\"\\n选择功能:\"); while(1) fflush(stdin); scanf(\"%c\选择功能或者按enter继续执 {

block();

.

} else break; } else if(c=='3') { {

if(c=='\\n') {

run();

printf(\"\\n行:\");

} else break; }

教育资料

wake(); while(1) fflush(stdin); scanf(\"%c\选择功能或者按enter继续执 }

.

}

else if(c=='4') {

endprocess(); {

if(c=='\\n') {

run();

printf(\"\\n行:\");

} else break; } }

else if(c=='0') { 教育资料

fflush(stdin); scanf(\"%c\选择功能或者按enter继续执 while(1) exit(0);

.

} else {

printf(\"信息提示: 输入错误!请选择正确的菜单功能选项:\");

{

if(c=='\\n') {

run();

printf(\"\\n行:\");

} else break; } } }

教育资料

fflush(stdin); scanf(\"%c\选择功能或者按enter继续执 while(1) } .

int main() {

Initializa(); putout(); meanu(); }

教育资料