操作系统 进程调度

系别 计算机系 班级 学号 姓名 实验日期 2015/10/11 课程名称 计算机操作系统 实验名称 进程调度模拟算法 实验目的： 过本次实验，加深对进程概念的理解，进一步掌握进程状态的转变及进程调度策略。 一、实验条件： 计算机一台，软件vc++6.0 二、实验原理： 设计程序模拟进程的时间片轮转法调度过程。假设初始状态为：有ready个进程处于就绪状态，有blocked个进程处于阻塞状态。采用轮转法进程调度算法进行调度(调度过程中，假设处于执行状态的进程不会阻塞)，且每过counter个时间片，唤醒处于阻塞队列队首的进程。 三、实验内容 #include #include #define TRUE 1 #define FALSE 0 typedef struct PCB_type { char name; //进程名 int state; //进程状态 成绩 //2--表示\"执行\"状态 //1--表示\"就绪\"状态 //0--表示\"阻塞\"状态 int cpu_time; //运行需要的CPU时间（需要运行的时间片个数） }PCBtype; typedef struct QueueNode //定义结点 { 1 / 12

PCBtype PCB; struct QueueNode *next; } LinkQueueNode; typedef struct Queue //定义队列 { LinkQueueNode * head; LinkQueueNode * tail; } LinkQueue; LinkQueue rq,bq,runq; int deleteState=0; int ready=2; int blocked=3; int counter=5; int createq(LinkQueue *Q) //队列初始化 { } void fuzhi(PCBtype *PCB1,PCBtype *PCB2) { PCB1->name=PCB2->name; PCB1->state=PCB2->state; PCB1->cpu_time=PCB2->cpu_time; Q->head=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(Q->head !=NULL) { Q->tail=Q->head; Q->head->next=NULL; return (TRUE); } else return (FALSE); } int enterQueue(LinkQueue *Q,LinkQueueNode x) //入队列操作算法 2 / 12

{ } LinkQueueNode * deleteQ(LinkQueue *Q) { LinkQueueNode *NewNode; if(Q->head == Q->tail) { deleteState =0; LinkQueueNode *NewNode; NewNode=(LinkQueueNode*)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { fuzhi(&NewNode->PCB,&x.PCB); NewNode->next=NULL; Q->tail->next=NewNode; Q->tail=NewNode; return (TRUE); } else return(FALSE); } else { NewNode = Q->head->next; Q->head->next = NewNode->next; if(Q->tail == NewNode) Q->tail = Q->head; deleteState =1; } return NewNode ; } void display(LinkQueue Q) 3 / 12

{ } void create() { ); getchar(); fuzhi(&NewNode->PCB,pcbnode); printf(\" Enter继续输入,否则结束输入\\n\"); scanf(\"%c %d %d\int a=13; LinkQueueNode *NewNode; PCBtype *pcbnode; NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); pcbnode=(PCBtype *)malloc(sizeof(PCBtype)); printf(\"请按序输入进程名,进程状态,运行所需时间片个数:\\n\"); printf(\"\ 2-表示执行状态\\n\ 1-表示就绪状态\\n\ 0-表示阻塞状态\\n\"); while(a==13) { LinkQueueNode *Newhead=Q.head->next; while(Newhead !=Q.tail->next) { } printf(\"**************\\n\"); printf(\"该进程的名称为:%c\\n\printf(\"该进程的状态为:%d\\n\printf(\"进程运行所需的CPU时间为:%d\\n\printf(\"**************\\n\"); Newhead=Newhead->next; a=getch(); if(pcbnode->state==2)enterQueue(&runq,*NewNode); 4 / 12

if(pcbnode->state==1)enterQueue(&rq,*NewNode); if(pcbnode->state==0)enterQueue(&bq,*NewNode); } display(rq); display(bq); } int GetStateQueue(LinkQueue Q) { int retval; if(Q.head == Q.tail) retval=0; else } void dispath() { int counte=0,i=0,j; LinkQueueNode *deleteNode; int flag1,flag2; char name[20]; while(TRUE) { if(rq.head->next!=NULL||bq.head->next!=NULL) { if(GetStateQueue(rq)) { deleteNode=deleteQ(&rq); flag1 =enterQueue(&runq,*deleteNode); if(flag1) 5 / 12

retval=1; return retval; { printf(\"进程%c调度成功,状态由就绪变成运行!\\ } if(deleteNode->PCB.cpu_time>0) { deleteNode->PCB.state= 1; flag1 =enterQueue(&rq,*deleteNode); if(flag1) printf(\"进程%c调度成功,状态由运行变成就deleteNode->PCB.state = 2; printf(\" 进程状态变为:%d\\n\deleteNode->PCB.cpu_time--; name[i++]=deleteNode->PCB.name; 绪!\\ } else free(deleteNode); printf(\" 进程状态变为:%d\\n\} counte++; if(counte==counter) { if(GetStateQueue(bq)) { deleteNode = deleteQ(&bq); flag2 =enterQueue(&rq,*deleteNode); if(flag2) printf(\"进程%c调度成功,状态由阻塞变成就绪!\\ deleteNode->PCB.state=1; 6 / 12

} } printf(\" 进程状态变为:%d\\n\ counte=0; } } else break; } printf(\"执行序列为：\\n\"); for(j=0;jif(createq(&rq)&&createq(&bq)&&createq(&runq)) printf(\"\队列初始化成功!\\n\"); else { printf(\"队列初始化失败,程序将退出\\n!\"); exit(0); } create(); dispath(); ②输出数据：abababacbacadcddededd 五、结论： 预期的输出：abababacbacadcddededd 实际输出数据与预期的输出相同 六、用C语言实现提示 程序中进程可用PCB表示，其类型描述如下 struct PCB_type { char name ; //进程名 int state ; //进程状态 // 2——表示“执行”状态 // 1——表示“就绪”状态 // 0——表示“阻塞”状态 int cpu_time ; //运行需要的CPU时间（需运行的时间片个数） } 设置三个队列，队列类型描述如下 struct QueueNode{ struct PCB_type PCB; Struct QueueNode *next; } struct Queue { Struct QueueNode *head, *tail; } 并设三条队列指针： struct Queue *rq, *bq, *runq //ready队列、blocked队列、run队列 函数设计 void createq(struct Queue *queue); //创建队列 8 / 12

void enterq(struct Queue *q, struct QueueNode x); //x结点入队列q struct QueueNode deleteq(struct Queue *q); //删除队首结点 dispatch(); //模拟调度函数 main() //主函数 初始队列 ready=2 blocked=3 counter=5 runq->run_tail runq->head Λ rq_tail rq_head a 6 1 b 4 1 Λ a bq->tail bq->head c 3 0 d 6 0 e 2 0 Λ 9 / 12

begin count =0 ready队列不空或blocked队列不空 Y ready队列不空 Y N N p取ready队首元素；插入到run队列中； p->PCB.state置“运行”; 输出p->PCB.name； N p->PCB.cpu_time>0 Y 释放p p->PCB.state置“就绪”，p入ready队列队尾 count++ N count == counter Y blocked队不空，blocked队首进程入ready队尾；count =0 end 七、实验结果： 10 / 12

1）进程信息输入 2）输入的进程信息输出： 3）调度过程输出 11 / 12

12 / 12