4.1 实验目的
多道程序设计中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实验要求学生：
（1）理解进程的各个状态、进程控制块PCB的结构。
（2）理解处理机调度算法，模拟在单处理器情况下的处理器调度。
4.2 背景知识
（1）熟悉C语言源程序的调试和编译知识。
（2）掌握优先数调度算法和时间片轮转法的原理。
4.3 实验内容
（1）设计一个按优先数调度算法实现处理器调度的程序。
[提示]：① 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为：
进程名 |
指针 |
要求运行时间 |
优先数 |
状态 |
其中，进程名——作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。
指针——按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。
要求运行时间——假设进程需要运行的单位时间数。
优先数——赋予进程的优先数，调度时总是选取优先数大的进程先执行。
状态——可假设有两种状态，“就绪”状态和“结束”状态。五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。
②在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。
③为了调度方便，把五个进程按给定的优先数从大到小连成队列。用一单元指出队首进程，用指针指出队列的连接情况。例：
队首标志
K2
K1 | P1 | K2 | P2 | K3 | P3 | K4 | P4 | K5 | P5 |
0 | K4 | K5 | K3 | K1 | |||||
2 | 3 | 1 | 2 | 4 | |||||
1 | 5 | 3 | 4 | 2 | |||||
R | R | R | R | R | |||||
PCB1 | PCB2 | PCB3 | PCB4 | PCB5 |
④处理器调度总是选队首进程运行。采用动态改变优先数的办法，进程每运行一次优先数就减“1”。由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，只进行相应的参数的修改，即执行：
优先数-1
要求运行时间-1
来模拟进程的一次运行。
提醒注意的是：在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。在这里省去了这些工作。
⑤ 进程运行一次后，若要求运行时间¹0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。
⑥ 若“就绪”状态的进程队列不为空，则重复上面④和⑤的步骤，直到所有进程都成为“结束”状态。
⑦ 在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。
⑧ 为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。
（2）设计一个按时间片轮转法实现处理器调度的程序。
[提示]：① 假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的格式为：
进程名 |
指针 |
要求运行时间 |
已运行时间 |
状态 |
其中，进程名——作为进程的标识，假设五个进程的进程名分别为Q1，Q2，Q3，Q4，Q5。
指针——进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。
要求运行时间——假设进程需要运行的单位时间数。
已运行时间——假设进程已经运行的单位时间数，初始值为“0”。
状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。当一个进程运行结束后，它的状态为“结束”，用“E”表示。
② 每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。
③ 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到P2执行，则有：
标志单元
K2
K1 | Q1 | K2 | Q2 | K3 | Q3 | K4 | Q4 | K5 | Q5 |
K2 | K3 | K4 | K5 | K1 | |||||
2 | 3 | 1 | 2 | 4 | |||||
1 | 0 | 0 | 0 | 0 | |||||
R | R | R | R | R | |||||
PCB1 | PCB2 | PCB3 | PCB4 | PCB5 |
④ 处理器调度总是选择标志单元指示的进程运行。由于本实验是模拟处理器调度的功能，所以，对被选中的进程并不实际的启动运行，只进行相应的参数的修改，即执行：
已运行时间+1
来模拟进程的一次运行，表示进程已经运行过一个单位的时间。
请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已经运行满一个时间片。
⑤ 进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间¹已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前面一个进程的指针位置。
⑥ 若“就绪”状态的进程队列不为空，则重复上面的④和⑤的步骤，直到所有的进程都成为“结束”状态。
⑦ 在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及运行一次后进程队列的变化。
⑧ 为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中的进程名以及进程控制块的动态变化过程。
4.4 参考程序
4.4.1 按优先数调度算法实现处理器调度的参考程序
#include<iostream>
#include<string>
using namespace std;
//-----------------------
struct _proc //定义一个结构体表示进程的PCB
{
char name[32]; //进程名
struct _proc *next; //指向下一个PCB的指针
int run_time; // 要求运行的时间
int priority; // 优先数
int state;//进程状态
};
_proc *root;
//向就绪队列中插入进程,按照降序
void Insert(_proc* pr)
{
_proc *q=root;
_proc *p=root->next;
if(root->state!=0)
{
while(p!=NULL)
{
if(p->priority>pr->priority)
{
q=p;
p=p->next;
}
else
{
break;
}
}
}
pr->next=p;//插入进程结点
q->next=pr;
++root->state;//进程个数加1
}
//创建进程
_proc Creat(char name[],int priority,int run_time)
{
_proc pr;
strcpy(pr.name,name);
pr.priority=priority;
pr.run_time=run_time;
pr.state=0;
pr.next=NULL;
return pr;
}
//删除就绪队列中队首进程
_proc* Delete()
{
_proc *pr=root->next; //此时pr为指向结构体的指针，指向队首进程
root->next=root->next->next;
--root->state; //进程个数减1
return pr; //返回被删除进程的地址
}
//对就绪队列排序,按照降序
void Sort()
{
if(root->next->run_time==0)//队首进程的要执行时间为0时，从就绪队列中删除该进程
{
Delete();
root->next->state=1;
}
else//不为0时，先删除，再根据变化后的优先级，插入到相应位置
{
_proc *pr=Delete();
Insert(pr);
}
}
void OutPut()
{ //取队首的进程，模拟进程执行，输出执行进程名
cout<<root->next->name<<endl;
--root->next->priority;//动态改变优先数，优先级减1
--root->next->run_time;//运行时间减1
}
void Solve()
{ //定义根结点，指向第一个进程
root=new _proc;
root->state=0;//队列中的进程个数
root->next=NULL;
//创建几个进程,并插入就绪队列
_proc pr1=Creat("p1",2,1);
Insert(&pr1);
_proc pr2=Creat("p2",3,5);
Insert(&pr2);
_proc pr3=Creat("p3",1,3);
Insert(&pr3);
_proc pr4=Creat("p4",2,4);
Insert(&pr4);
_proc pr5=Creat("p5",4,2);
Insert(&pr5);
cout<<"调度序列："<<endl; //输出
while(root->state!=0)
{
OutPut(); //取队首进程模拟执行一个单位时间数
Sort(); //重新排序
}
}
int main()
{
Solve();
getchar();
getchar();
return 0;
}
4.4.2 按时间片轮转法实现处理器调度的参考程序。
#include<iostream>
#include<string>
using namespace std;
//-----------------------
struct _proc //定义一个结构体表示进程的PCB
{
char name[32]; //进程名
struct _proc *next; //指针
int run_time; //要求运行的时间
int alloc_time; //已运行的时间
int state;//进程状态
};
_proc *root;
//向就绪队列中插入进程,按照降序
void Insert(_proc* pr)
{
if(root->next==NULL)
{
root=pr;
pr->next=pr;
return;
}
pr->next=root->next;//插入
root->next=pr;
root=pr;
}
//创建进程
_proc Creat(char name[],int run_time,int alloc_time)
{
_proc pr;
strcpy(pr.name,name); //进程名取参数名
pr.run_time=run_time; //取参数的要求运行时间
pr.alloc_time=alloc_time; //取参数的已运行时间
pr.state=0;
pr.next=NULL;
return pr;
}
//删除就绪队列中对首进程
void Delete()
{
if(root->next==root)
{ //队列已为空
root=NULL;
return;
}
root->next=root->next->next;
}
//输出进程号,模拟进程执行
void OutPut()
{
cout<<root->next->name<<endl;//输出
++root->next->alloc_time;//已运行时间加1
}
void Solve()
{ //定义根结点，指向下一个运行的进程
root=new _proc;
root->state=0;//队列中的进程个数
root->next=NULL;
//创建几个进程,并插入就绪队列
_proc pr1=Creat("Q1",2,1);
Insert(&pr1);
_proc pr2=Creat("Q2",3,0);
Insert(&pr2);
_proc pr3=Creat("Q3",1,0);
Insert(&pr3);
_proc pr4=Creat("Q4",2,0);
Insert(&pr4);
_proc pr5=Creat("Q5",4,0);
Insert(&pr5);
cout<<"调度序列："<<endl; //输出
while(root!=NULL)//一直循环遍历
{
OutPut();//执行root指向的进程
if(root->next->alloc_time==root->next->run_time)//执行完毕
{
Delete();//从就绪队列中删除该进程
continue;
}
root=root->next;//root指针后移，执行下一个进程做准备
}
}
int main()
{
Solve();
getchar();
return 0;
}
