第5次 进程调度模拟

1、操作系统课程实验报告姓名学号系计算机科学与技术任课教师贺辉指导教师贺辉评阅教师贺辉实验地点实验时间实验编号与实验名称：第5次 进程调度模拟实验目的：进程调度是处理机管理的核心内容。通过本实验可以加深理解有关进程控制块（进程的概念）、进程队列的概念及进程调度算法的理解并体会和了解优先级和时间片轮转调度算法的具体实施办法。实验内容及要求（详见实验讲义）：本实验要求用C语言【也可以是其它你擅长的程序设计语言】编写和调试一个简单的进程调度模拟程序。须在实验报告中给出详细算法描述和流程图。设计进程控制块PCB表结构，分别适用于优先级调度算法和轮转调度算法。编制两种进程调度算法：1）优先级调度；2）轮转调

2、度建立进程就绪队列。对两种不同算法编制入队子程序【重点！】。实验用到的软件（：）Vs，word实验内容、关键步骤（流程图、代码等）及结果分析（70分）1.优先级调度（1）基本思想：为了防止高优先级进程无休止地运行下去，调度程序可以在每个时钟滴答（即每个时钟中断）降低当前进程的优先级。（2）实现：即给每个进程被赋予一个优先级，允许优先级最高的可运行进程先运行。进程之间再以优先级的高低，从高到低进行排序，之后开始执行进程，在规定的时间片当中，如果进程能够执行完毕，就从进程队列当中移除该进程，否则的话，减小该进程的优先级（运行一次，优先级-8），插入进程队列当中，整个进程队列依旧是按照优先级从高到低

3、的顺序进行排序，之后继续执行，判断进程队列是否为空，如果不为空，则就绪队列的首进程投入运行。最后直到进程队列为空，结束。（3）算法流程图优先级算法使用优先级算法给新加的五个进程进行cpu处理。初始化PCB，输入进程号及进程所需的cpu运行时间各进程由安照优先级程度高到低排序（优先级=100-所需cpu运行时间）就绪队列为空将首进程置入到就绪队列中，并运行。进程状态变为R。就绪队列为空进程开始运行，当时间时间片使用完，cpu的使用时间+1,进程所需的时间-1，优先级-8，状态置为w。判断进程所需cpu时间是否等于运行时间。如果等于，那么进程被cpu处理完，进程状态变为F，将cpu资源分配给其他进

4、程。重新对进程排序，按照进程的优先级高低。如果所有进程状态都为F，队列为空，即表明所有进程都被cpu处理完，结束。（4）步骤说明1）char algo;printf("选择算法：P/R(优先级算法/时间片轮转算法)；输入'e'结束n");scanf_s("%c", &algo);printf("输入进程数：n");scanf_s("%d", &N);选择算法，进程数量2）for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);c

5、in >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->state = 'w'p->prio = 100 - time;if (ready != NULL)insert1(p);elsep->next = ready;ready = p;初始化并创建进程，排序3）run = ready;ready = ready->next;run->state = 'R'将首进程进入就绪队列4）run-

6、>cputime = run->cputime + 1;run->needtime = run->needtime - 1;run->prio = run->prio - 8;if (ready != NULL)change(run);elserun->next = ready;ready = run;run = ready;ready = ready->next;run->state = 'R'进程运行及重新排序。5）if (run->needtime = 0)run->next = finish;finish

7、 = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();进程处理完，将cpu资源交予其他进程。（5）子函数关系图先选择优先级算法，再输入进程数传入create1函数。再利用create1创建进程。将新建进程传入insert1()函数进行从优先级程度高到低排序（优先级=100-所需cpu运行时间）将进程传进prt1()函数输出信息。将进程传进prt()函数。将进程传进prt2()函数输出排序后，进程的所有信息。跳转到priority()函数，并传入参数即进程数量。进程开始运行，时间片使用完，cpu的使用时间

8、+1,进程所需的时间-1，优先级-8，状态置为w。并判断进程是否被处理完，处理完将cpu资源给予其他进程。判断进程所需cpu时间是否等于运行时间。如果等于，那么进程被cpu处理完，进程状态变为F，将cpu资源分配给其他进程。将进程传入change（）函数，重新对进程排序，按照进程的优先级高低。（6）结果结果分析：和优先级算法结果一样。2. 轮转调度基本思想：每个进程被分配一个时间段，称为时间片，即允许改进程在该时间段中运行。如果时间片结束时改进程还在运行，则将剥夺cpu并分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则cpu立即进行切换。实现：每个进程都会被分配一个相同的时间片，并按照

9、先来先服务进行排序，允许该进程在该时间段中运行。如果在时间片结束时该进程还在运行，则将剥夺CPU并分配给另一个进程。如果该进程在时间片结束前阻塞或结束，则CPU立即进行切换。其中每个进程分配的相同时间片的大小设计为2，一个进程如果在该时间片当中没有结束，则将会被强制结束，将CPU分配给下一个进程，该进程将会被插入整个进程队列的最后，如果一个进程在规定的时间结束，则将CPU立刻分配给下一个进程，该进程从进程队列中移除。（3）算法流程图时间轮转算法先来先服务算法初始化PCB，输入进程号及进程所需的cpu运行时间先来先创建，先排序，后创建的插在队列后就绪队列为空将首进程置入到就绪队列中，并运行。进程

10、状态变为R。进程开始运行，当时间时间片使用完，占用cpu时间+2,进程所需的时间-2，计数+1，时间片长度不变，状态置为w。并将进程置于队尾。判断进程所需cpu时间是否等于计数*2。如果等于，那么进程被cpu处理完，进程状态变为F，将cpu资源分配给其他进程。进程被插入到队尾。如果所有进程状态都为F，队列为空，即表明所有进程都被cpu处理完，结束。（4） 步骤说明1）char algo;printf("选择算法：P/R(优先级算法/时间片轮转算法)；输入'e'结束n");scanf_s("%c", &algo);printf(&q

11、uot;输入进程数：n");scanf_s("%d", &N);选择算法，进程数量2）p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->count = 0;p->state = 'w'p->round = 2;if (ready != NULL)insert2(p);elsep->next = ready;

12、ready = p;tail = p;初始化并创建进程，按照先来先服务排序3）run = ready;ready = ready->next;run->state = 'R'将首进程进入就绪队列4）run->cputime = run->cputime + 2;run->needtime = run->needtime - 2;if (run->needtime < 0)run->needtime = 0;run->count = run->count + 1;prt(alg);进程运行5）if (run->

13、;needtime = 0)run->next = finish;finish = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();elseif (run->count*2 = run->round)run->count = 0;if (ready != NULL)run->state = 'w'insert2(run);firstin();处理过的或者处理完的都插入队尾。当所有都为F时，结束。（5）子函数关系图选择轮转调度算法，再输入进程数传入create

14、2函数。再利用create2创建进程。将新建进程传入insert2()函数。按照进程先创建先服务，进行排序。将进程传进prt1()函数输出信息。将进程传进prt()函数将进程传进prt2()函数输出排序后，进程的所有信息。跳转到roundrun()函数，并传入参数即进程数量。进程开始运行，当时间时间片使用完，占用cpu时间+2,进程所需的时间-2，计数+1，时间片长度不变，状态置为w。并将进程置于队尾。并判断进程是否被处理完。将处理完的进程，由函数firstin()将cpu资源给予其他进程，改变其他状态变为就绪状态。通过传入处理完进程到insert2()函数，并将此进程置于队尾。（6） 结果结

15、果分析：和时间片轮转调度算法结果一样。3.代码/ ConsoleApplication4.cpp : 定义控制台应用程序的入口点。/#include "stdafx.h"#include "stdio.h"#include "stdlib.h"#include "string.h"#include "ctype.h"#include "conio.h"#include "malloc.h"#include <iostream>using nam

16、espace std;typedef struct nodechar name10;int prio;int round;int cputime;int needtime;int count;char state;struct node *next;PCB;PCB *finish, *ready, *tail, *run;int N;void firstin()run = ready;run->state = 'R'ready = ready->next;void prt1(char a)if (toupper(a) = 'P')printf(&qu

17、ot; 进程号 已占用CPU时间 所需时间 优先数 状态n");elseprintf(" 进程号 已占用CPU时间 所需时间 计数 时间片长度 状态n");void prt2(char a, PCB *q)if (toupper(a) = 'P')printf(" %-10s%-15d%-10d%-7d %cn", q->name,q->cputime, q->needtime, q->prio, q->state);elseprintf(" %-12s%-12d%-12d%-12d%-1

18、2d %-cn", q->name,q->cputime, q->needtime, q->count, q->round, q->state);void prt(char algo)PCB *p;prt1(algo);if (run != NULL)prt2(algo, run);p = ready;while (p != NULL)prt2(algo, p);p = p->next;p = finish;while (p != NULL)prt2(algo, p);p = p->next;getchar();void insert1

19、(PCB *q)PCB *p1, *s, *r;int b;s = q;p1 = ready;r = p1;b = 1;while (p1 != NULL) && b)if (p1->prio >= s->prio)r = p1;p1 = p1->next;elseb = 0;if (r != p1)r->next = s;s->next = p1;elses->next = p1;ready = s;void insert2(PCB *p2)tail->next = p2;tail = p2;p2->next = NULL

20、;void change(PCB *q)PCB *p1, *s, *r;int b;q->state = 'w's = q;p1 = ready;r = p1;b = 1;while (p1 != NULL) && b)if (p1->prio >= s->prio)r = p1;p1 = p1->next;elseb = 0;if (r != p1)r->next = s;s->next = p1;elses->next = p1;ready = s;void create1(char alg, int N)PC

21、B *p;int i, time;char na10;ready = NULL;finish = NULL;run = NULL;printf("输入进程号、运行时间：n");for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->state = 'w'p->prio = 100 - tim

22、e;if (ready != NULL)insert1(p);elsep->next = ready;ready = p;printf(" 优先数算法输出信息：n");printf("*n");prt(alg);run = ready;ready = ready->next;run->state = 'R'void create2(char alg, int N)PCB *p;int i, time;char na10;ready = NULL;finish = NULL;run = NULL;printf("

23、输入进程号、运行时间：n");for (i = 1; i <= N; i+)p = (PCB *)malloc(sizeof(PCB);cin >> na;cin >> time;strcpy_s(p->name, na);p->cputime = 0;p->needtime = time;p->count = 0;p->state = 'w'p->round = 2;if (ready != NULL)insert2(p);elsep->next = ready;ready = p;tail =

24、 p;printf(" 轮转调度算法输出信息n");printf("*n");prt(alg);run = ready;ready = ready->next;run->state = 'R'void priority(char alg)while (run != NULL)run->cputime = run->cputime + 1;run->needtime = run->needtime - 1;run->prio = run->prio - 8;if (run->needti

25、me = 0)run->next = finish;finish = run;run->state = 'F'run = NULL;if (ready != NULL)firstin();if (ready != NULL)change(run);elserun->next = ready;ready = run;run = ready;ready = ready->next;run->state = 'R'prt(alg);void roundrun(char alg)while (run != NULL)run->cputime = run->cputime + 2;run->needtime = run->needt