进程调度
一、实验目的
用高级语言编写和调试一个进程调度程序，以加深对进程的概念及继承调度算法的理解。
二、实验内容和要求
设计一个有N个进程并发的进程调度程序，采用时间片轮转算法。
Ø 每一个进程用一个进程控制块PCB表示。PCB包含信息有：进程名name，进程号id，进程状态state，进程所需运行时间need_time,进程运行时间run_time。
Ø 进程所需的运行时间人为指定。进程运行时间以时间片为单位进行计算。（程序中以按任意键表示运行一次CPU时间片）
Ø 每个进程的状态有就绪W，运行R，和完成F（撤销进程）。
Ø 就绪的进程获得CPU后只能运行一个时间片，运行完运行时间run_time+1。
Ø 如果运行一个时间片后，进程的run_time等于need_time（即已经达到所需运行时间），则撤销该进程并提示，如果还未达到，则将其放到队尾，进入就绪状态等待下一次时间片分配。每一次调度程序都打印一次运行情况，包括：运行的进程，就绪队列的进程，已经所有进程的PCB（不包括已经撤销的进程）。
三、 实验主要仪器设备和材料
硬件环境：Window XP
软件环境：Microsoft Visual C++ 2010Express
四、 实验原理及方案
1、实验原理
本进程调度算法采用时间片轮转算法，具体是：每个进程被分配一个时间片，即该进程允许运行的时间。就绪的进程都存放在一个就绪链表中，队首的进程将获得时间片。如果在时间片结束时进程还在运行，则CPU将剥夺并分配给下一个进程。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。
2、设计方案
程序设计三个主要模块来进行模拟进程的调度。
一是main()函数，用来按步操作模拟CPU分配执行每一个时间片，并循环判断程序是否结束。
二是newPCB()函数，用来接收用户输入的进程信息（进程数目，PCB变量值）来创建一个就绪进程链表。
三是showPCB()函数，用来执行一次调度算法的操作（这里的算法采用时间片轮转调度算法），并刷新显示出来这次操作的结果（覆盖之前的操作结果显示）。
程序执行流程将是通过main函数调用newPCB()创建就绪进程链表，创建模拟CPU分配执行时间片循环，每一次循环调用一次showPCB()执行一次调度算法并显示结果，从而达到模拟CPU进程调度的效果。
3、相关数据结构的说明。
就绪队列中的进程采用链表的数据结构，方便进行进程调度。如图所示：
4、程序流程图
5、程序中源程序和可执行程序
void main(); /*主函数，用来进行调度操作*/
void newPCB(); /*建立PCB块并将他们组成一个队列*/
void pushPCB(); /*将新的PCB块放到链表末尾*/
void showPCB(); /*调度一次时间轮转算法并显示*/
void pinrtSort(); /*排序输出各个进程的PCB*/
6、代码清单：
/*
本程序实现模拟进程的时间片轮转调度算法，即每一个进程按照在队列中的顺序平均获得cpu执行时间，
如未能在时间片中完成，则该进程回到队尾等待调度，直到运行完毕
Author juju
*/
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include<windows.h>
static int id = 0;
int process_num;
int current_process;
struct pcb
{
char name[20];
int id;
char state;
int need_time;
int run_time;
struct pcb *next;
}*p, *q, *first_pcb =NULL;
typedef struct pcb PCB;
/* 排序输出各个进程PCB */
void printSort()
{
int i;
q = first_pcb;
for(i = 0; i < process_num;) {
if(i == q -> id) {
printf("|%s/t/t|%d/t/t|%c/t/t|%d/t/t|%d/n", q-> name, q -> id, q -> state, q -> need_time, q -> run_time);
i++;
q = first_pcb;
} else {
q = q -> next;
if(q == NULL) {
q = first_pcb;
i++;
}
}
}
}
/* 调度一次PCB并显示 */
void showPCB()
{
int i;
first_pcb -> run_time++;
first_pcb -> state = 'r';
/* 进程执行完毕，将其清除出链表 */
if((first_pcb -> run_time) == (first_pcb -> need_time)) {
current_process--;
printf("进程%s已经运行完毕", first_pcb -> name);
system("pause");
first_pcb = first_pcb -> next;
if(first_pcb == NULL) {
printf("所有进程都已经运行完毕");
system("pause");
return;
}
first_pcb -> state = 'r';
}
system("cls");
/* 显示运行的进程和就绪的进程 */
q = first_pcb -> next;
printf("-------当前运行的进程是：进程%s/n/n", first_pcb -> name);
printf("-------在等待队列的进程是：");
while(q != NULL) {
printf("进程%s", q -> name);
q = q -> next;
}
/* 显示相应的PCB块 */
printf("/n/n------------------------------进程详细PCB------------------------------------");
printf("/n/n|进程名/t/t|进程ID/t/t|进程状态/t|进程所需时间/t|进程运行时间/n");
printSort();
/* 进行一次时间片轮换调度算法， 将队首的进程放到队尾，之前第二位进程获得cpu时间片 */
q = first_pcb;
while(q -> next != NULL) {
q = q -> next;
}
first_pcb -> state = 'w';
q -> next = first_pcb;
first_pcb = first_pcb -> next;
q -> next -> next = NULL;
printf("/n");
printf("运行调度");
system("pause");
}
/* 将新的PCB块放到链表末尾 */
void pushPCB(int i)
{
q -> next = p;
q = p;
if(i == process_num - 1) q -> next = NULL;
}
/* 建立PCB块并将他们组成一个队列 */
void newPCB()
{
int i;
printf("请输入进程数：");
scanf("%d", &process_num);
q = (PCB*)malloc(sizeof(PCB));
first_pcb = (PCB*)malloc(sizeof(PCB));
for(i = 0; i < process_num; i++) {
system("cls");
p = (PCB*)malloc(sizeof(PCB));
printf("请输入第%d个进程名:", id + 1);
scanf("%s", p -> name);
printf("请输入进程需要的运行时间：");
scanf("%d", &p -> need_time);
p -> id = id++;
p -> run_time = 0;
p -> state = 'w';
if(i == 0) {
first_pcb = q = p;
p -> next = NULL;
}
else pushPCB(i);
}
}
void main()
{
newPCB();
current_process = process_num;
printf("按任意键开始进程调度/n");
system("pause");
while(current_process) {
showPCB();
}
}
五、 实验结果及分析
1、运行结果
测试数据：输入5个进程：a.exe b.exe c.exe d.exe e.exe，它们执行完毕所需 的CPU时间分别为 4，5，3，6，2（随意给出）。
2、实验结果的分析及说明
实验结果很明显的看出时间片轮转片算法的实质，即每一个进程按顺序公平的获得一定的CPU使用时间，如果没有运行结束，那么它将排到队尾等待下一次调度。等待队列中的进程也会有次序的排队等待调度。
六、调试总结及心得体会
1.代码编写总结
经分析实验目的和原理，初步确定程序目标后，设计出三个主要模块来进行程序编码。然后确定存放进程是数据结构为单链表。通过标准输入设备输入进程数（process_num）和PCB等基本信息，用newPCB函数将他们存放进链表里。同时保留first_pcb，即表头进程指针，用来进行调度。用循环指令执行每一次调度，调度算法简单，即将first_pcb中的state置’w’，run_time++，并判断有无结束，之后将它放到队尾。然后打印调度情况。
程序设计里有一个关键指针q，用来建立进程链表和遍历进程链表从而完成进程指针移动（即是调度），以及遍历查找进程从而打印输出。这里q很灵活，但也增加了模块间的耦合性（关键模块newPCB和showPCB都用到指针q），所以这也是设计里的一个缺陷。
2．心得总结
本次代码编辑主要总结出两条心得：
1. 界面设计应该在编写之前确定，因为本程序是用来模拟一个调度算法，需要不断地刷新显示结果，其清晰性很重要，界面不能很潦草，固然需要一开始就设计好。而不是作为一个中间环节在程序中不断调试。
2. 关键算法的编写。通常在编写时都是在IDE下直接写代码，如果有问题就进行调试，直到正确通过。但是有的关键算法稍微有点复杂，在运行出错时候多次调试后仍然不能正确，此时静下心来，在纸上画一下算法流程，以及数据结构图示，并将代码写到纸上修改，实践证明，如此方法效率更高。如在写printSort（排序输出打印PCB详细信息）算法时，一直不能取得理想效果，这时把思路理一下，在纸上思考，很快在纸上写出代码，调试一次通过。
七、思考题
1、分析不同调度算法的调度策略，比较不同调度算法的优缺点，总结他们的适用范围。
答：
² 优先级算法是指在进程创建时先确定一个初始优先数， 以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。适用于作业调度和进程调度，可分成抢先式和非抢先式。
² 时间片轮转法是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。时间片不能太长也不能太短，太长可能浪费一个进程的执行时间（可能不需要这么多），增加响应时间；太短一个进程要经过很多次调度才能完成，同样会增加响应时间。适用于进程的所需执行时间和数目适当的情况。
² 多级反馈队列算法是轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程。为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。不必估计进程的执行时间，动态调节。
2、哪种进程最适合于多级反馈队列调度，是偏重于处理机型还是偏重于I/O型？
答：偏重于I/O型进程。