实验8.4.1 Linux的进程调度模拟程序设计
1、题目简介给出进程调度的算法描述（如基于动态优先级和时间片轮转调度算法的描述）。用C语言设计一个对n个并发进程进行调度的程序，每个进程由一个进程控制块（PCB）结构表示，该进程控制块应包括下述信息：进程标识ID、进程优先数PRIORITY（并规定优先数与优先权成正比）、时间片数CHIP、进程已经占用CPU的时间CPUTIME，进程还需要运行的时间ALLTIME（当进程运行完毕时，其值为0）、..
·
1、题目简介
- 给出进程调度的算法描述（如基于动态优先级和时间片轮转调度算法的描述）。用C语言设计一个对n个并发进程进行调度的程序，每个进程由一个进程控制块（PCB）结构表示，该进程控制块应包括下述信息：进程标识ID、进程优先数PRIORITY（并规定优先数与优先权成正比）、时间片数CHIP、进程已经占用CPU的时间CPUTIME，进程还需要运行的时间ALLTIME（当进程运行完毕时，其值为0）、进程的状态STATE（为简化起见。设每个进程处于运行E（excecuting）、就绪R（ready）和完成F（finish）三种状态之一，并假设起始状态都是就绪状态R。），以及进程队列指针NEXT（用来将PCB排成队列）等，可按照调度算法的不同而增删。
- 调度程序应当包含2种不同的调度算法，运行时可以任选一种，以利于各种方法的分析和比较。
- 程序应能显示或打印各种进程状态和参数变化情况，便于观察。即要显示每个时间片内各进程的情况，并且指出运行进程及就绪和阻塞队列中的内容。
2、参考设计思路
进程控制块（PCB）的定义如下：
typedef struct process_pcb
{
int ID; //进程标识
int priority; //进程优先数，值越大，优先级越高
int arrive_time; //进程达到时间，以时间片为单位
int service_time; //进程需要总的服务时间，以时间片为单位
int start_time; //进程开始执行时间，以时间片为单位
int end_time; //进程结束时间，以时间片为单位
int all_time; //进程仍然需要运行时间，以时间片为单位
int cpu_time; //进程已占用cpu时间，以时间片为单位
STATE state; //进程状态
}
3、所有的函数定义：
//排序比较函数：按照进程到达时间升序排列
bool cmp_arrive_time(const PCB a, const PCB b);
//排序比较函数：按照进程优先数降序排序
bool cmp_priority(const PCB a, const PCB b);
//输入进程信息
void input_process();
//选择进程调度策略
int select_policy();
//打印所有进程信息
void print_all(int current);
//先来先服务算法
void FCFS();
//时间片轮转算法
void round_robin();
//动态优先级算法
void dynamic_prio();4、具体代码如下：
#include <iostream>
#include <queue>
using namespace std;
//进程三种状态，这里增加一种，表示虽然输入，但是还没有到达进入系统时刻
typedef enum ProcessState{Executing, Ready, Finish, Unarrive}STATE;
//用于打印进程三种状态
char* StateString[] = {"Executing", "Ready", "Finish", "--"};
typedef struct process_pcb
{
int ID; //进程标识
int priority; //进程优先数，值越大，优先级越高
int arrive_time; //进程到达时间，以时间片为单位
int service_time; //进程需要总的服务时间
int start_time; //进程开始执行时间
int end_time; //进程结束时间
int all_time; //进程仍然需要运行时间
int cpu_time; //进程已占用cpu时间
STATE state; //进程状态
}PCB;
//排序比较函数：按照进程到达时间升序排列
bool cmp_arrive_time(const PCB a, const PCB b);
//排序比较函数：按照进程优先数降序排序
bool cmp_priority(const PCB a, const PCB b);
//输入进程信息
void input_process();
//选择进程调度策略
int select_policy();
//打印所有进程信息
void print_all(int current);
//先来先服务算法
void FCFS();
//时间片轮转算法
void round_robin();
//动态优先级算法
void dynamic_prio();
PCB *running_process = NULL;//当前运行任务
vector<PCB> input_queue;//进程输入队列，如当前时刻小于进程到达时间，则该进程仍然在输入队列中
vector<PCB> ready_queue;//就绪队列
vector<PCB> finish_queue;//完成队列
int main()
{
printf("===================================================\n");
printf(" 操作系统进程调度模拟实验 \n");
printf("===================================================\n");
printf("\n");
input_process();
//-1标志为打印所有进程的初始状态
print_all(-1);
int policy = select_policy();
switch(policy)
{
case 1:
FCFS();
break;
case 2:
round_robin();
break;
case 3:
dynamic_prio();
break;
default:
FCFS();
break;
}
}
//按进程到达时间升序排列，先到达的排在队首
bool cmp_arrive_time(const PCB a, const PCB b)
{
return a.arrive_time < b.arrive_time;
}
//按进程优先级降序排列，优先级高的排在队首
//如优先级相同，先到的进程排在前面
bool cmp_priority(const PCB a, const PCB b)
{
if(a.priority != b.priority){
return a.priority > b.priority;
}else{
return a.arrive_time < b.arrive_time;
}
}
//选择进程调度策略
int select_policy()
{
printf("\n请选择调度算法(输入1、2、3选择)：\n");
printf("1.先来先服务调度(FCFS) \n");
printf("2.时间片轮转调度(Round-Robin) \n");
printf("3.动态优先级调度(DynamicPriority) \n");
int n;
printf("请输入调度算法序号:");
while(scanf("%d",&n)){
if(n > 3 || n < 1){
printf("对不起,输入有误,请重新输入!\n");
}else{
break;
}
}
return n;
}
//输入进程信息
void input_process()
{
int num;
printf("请输入进程数量:");
scanf("%d",&num);
PCB pro;
for(int i = 1; i <= num; i++){
printf("\n请输入第%d个进程的到达时间、服务时间及优先级（以空格隔开）:\n",i);
scanf("%d%d%d",&pro.arrive_time,&pro.service_time,&pro.priority);
pro.ID = i;
pro.all_time = pro.service_time;
pro.cpu_time = 0;
pro.start_time = -1;//开始时间、结束时间默认为-1，表示尚未被调度过
pro.end_time = -1;
pro.state = Unarrive;//初始化为尚未进入到达
input_queue.push_back(pro);
}
//按照到达时间升序排队
sort(input_queue.begin(), input_queue.end(), cmp_arrive_time);
}
//打印单个进程的信息
void print_process(PCB* pro)
{
if(pro == NULL){
return;
}
printf("%4d%10d%10d%8d%10s", pro->ID, pro->arrive_time, pro->service_time, pro->priority, StateString[pro->state]);
//如进程尚未开始，则开始时间、结束时间以及剩余时间以--表示
//如进程已经开始，但未结束，则其结束时间以--表示
if(pro->start_time == -1){
printf("%10s%10s%10s", "--", "--", "--");
}else{
if(pro->end_time == -1){
printf("%10d%10s%10d", pro->start_time, "--", pro->all_time);
}else{
printf("%10d%10d%10d", pro->start_time, pro->end_time, pro->all_time);
}
}
//仅进程结束后，才统计其周转时间及加权周转时间
if(pro->state == Finish)
{
printf("%10d%10.2lf\n", pro->end_time - pro->arrive_time, (float)(pro->end_time - pro->arrive_time)/(float)pro->service_time);
}else{
printf("%10s%10s\n", "--", "--");
}
}
//打印所有进程的信息，-1为打印进程初始输入状态
void print_all(int current)
{
if(current == -1){
printf("\n进程初始状态：\n", current);
}else{
printf("\n当前时刻为：%d\n", current);
}
printf("进程号 到达时间 服务时间 优先级 状态 开始时间 结束时间 剩余时间 周转时间 带权周转时间\n");
//打印正在运行的进程
if(running_process != NULL){
print_process(running_process);
}
vector<PCB>::iterator it;
//打印就绪队列中的进程
for(it = ready_queue.begin(); it != ready_queue.end(); it ++){
print_process(&(*it));
}
//打印完成队列中的进程
for(it = finish_queue.begin(); it != finish_queue.end(); it ++){
print_process(&(*it));
}
//打印仍在输入队列中的进程
for(it = input_queue.begin(); it != input_queue.end(); it ++){
print_process(&(*it));
}
}
//先来先服务算法
void FCFS()
{
int chip = 0;//初始的时间片为0
//需要调度标志，默认为true
bool need_schedule = true;
while(1)
{
//如当前无正在运行进程，同时输入队列和就绪队列都为空，则所有进程完成
if(!running_process && input_queue.empty() && ready_queue.empty()){
break;
}
//将输入队列中，到达时间小于等于当前时间片的进程放入就绪队列中，并从输入队列中删除
while(!input_queue.empty()){
PCB pro = input_queue[0];
if(pro.arrive_time <= chip){
pro.state = Ready;
//放入就绪队列队尾
ready_queue.push_back(pro);
//从输入队列中删除
input_queue.erase(input_queue.begin() + 0);
}else{
break;
}
}
//判断是否需要调度，如需要则从取出就绪队列队首进程进行调度
if(need_schedule && !ready_queue.empty())
{
running_process = new PCB;
*running_process = ready_queue[0];//取出就绪队首进程
ready_queue.erase(ready_queue.begin() + 0);//从就绪队列中删除之
//调度进程开始运行
running_process->start_time = chip;
running_process->state = Executing;
need_schedule = false;
}
print_all(chip);//打印当前时刻所有进程的信息
//当前运行任务完成1个时间片，更改其信息
if(running_process){
running_process->cpu_time += 1;
running_process->all_time -= 1;
if(running_process->all_time == 0){//任务运行结束
running_process->end_time = chip + 1;
running_process->state = Finish;
finish_queue.push_back(*running_process);//将其放入完成队列中
delete running_process;
running_process = NULL;
need_schedule = true;
}else{
//FCFS仅当该进程运行完毕后，才调度下一个任务
need_schedule = false;
}
}
chip += 1;
}
//所有任务全部完成后，打印一次
print_all(chip);
}
//时间片轮转算法
void round_robin()
{
int chip = 0;//初始的时间片为0
bool need_schedule = true;
while(1)
{
//如当前无正在运行进程，同时输入队列和就绪队列都为空，则所有进程完成
if(!running_process && input_queue.empty() && ready_queue.empty()){
break;
}
//将输入队列中，到达时间小于等于当前时间片的进程放入就绪队列中，并从输入队列中删除
while(!input_queue.empty()){
PCB pro = input_queue[0];
if(pro.arrive_time <= chip){
pro.state = Ready;
//放入就绪队列队尾
ready_queue.push_back(pro);
//从输入队列中删除
input_queue.erase(input_queue.begin() + 0);
}else{
break;
}
}
//判断是否需要调度，如需要则取出就绪队列队首进程进行调度
if(need_schedule && !ready_queue.empty())
{
running_process = new PCB;
*running_process = ready_queue[0];//从就绪队首中取出
ready_queue.erase(ready_queue.begin() + 0);//从就绪队列中删除之
//调度进程开始运行
if(running_process->start_time == -1){//首次运行
running_process->start_time = chip;
}
running_process->state = Executing;
need_schedule = false;
}
print_all(chip);//打印当前时刻所有进程的信息
//当前运行任务完成1个时间片，判断该任务是否已经完成
if(running_process){
running_process->cpu_time += 1;
running_process->all_time -= 1;
if(running_process->all_time == 0){//任务运行结束
running_process->end_time = chip + 1;
running_process->state = Finish;
finish_queue.push_back(*running_process);//将其放入完成队列中
delete running_process;
running_process = NULL;
need_schedule = true;
}else{//任务没有完成，如果就绪队列中仍有任务，则轮转调度，否则不调度
if(!ready_queue.empty()){
running_process->state = Ready;
ready_queue.push_back(*running_process);//将其放回就绪队列中
delete running_process;
running_process = NULL;
need_schedule = true;
}else{
need_schedule = false;
}
}
}
chip += 1;
}
//所有任务全部完成后，打印一次
print_all(chip);
}
//动态优先级算法
void dynamic_prio()
{
int chip = 0;//初始的时间片为0
bool need_schedule = true;
while(1)
{
//如当前无正在运行进程，同时输入队列和就绪队列都为空，则所有进程完成
if(!running_process && input_queue.empty() && ready_queue.empty()){
break;
}
//将输入队列中，到达时间小于等于当前时间片的进程放入就绪队列中，并从输入队列中删除
while(!input_queue.empty()){
PCB pro = input_queue[0];
if(pro.arrive_time <= chip){
pro.state = Ready;
//放入就绪队列队尾
ready_queue.push_back(pro);
//从输入队列中删除
input_queue.erase(input_queue.begin() + 0);
}else{
break;
}
}
if(!ready_queue.empty()){
//将就绪进程按照优先级降序排列
sort(ready_queue.begin(), ready_queue.end(), cmp_priority);
}
//判断是否需要调度，如需要则取出就绪队列队首进程进行调度
if(need_schedule && !ready_queue.empty())
{
running_process = new PCB;
*running_process = ready_queue[0];//取出就绪队首进程
ready_queue.erase(ready_queue.begin() + 0);//从就绪队列中删除之
//调度进程开始运行
if(running_process->start_time == -1){//首次运行
running_process->start_time = chip;
}
running_process->state = Executing;
need_schedule = false;
}
print_all(chip);//打印当前时刻，所有进程的信息
//当前运行任务完成1个时间片，判断该任务是否已经完成
if(running_process){
running_process->cpu_time += 1;
running_process->all_time -= 1;
if(running_process->all_time == 0){//任务运行结束
running_process->end_time = chip + 1;
running_process->state = Finish;
finish_queue.push_back(*running_process);//将其放入完成队列中
delete running_process;
running_process = NULL;
need_schedule = true;
}else{//任务没有完成，如果就绪队列中仍有任务，且优先级大于本任务的优先级，则轮转调度，否则不调度
if(running_process->priority > 1){
running_process->priority -= 1;//优先级最小为1
}
if(!ready_queue.empty() && ready_queue[0].priority > running_process->priority){
running_process->state = Ready;
ready_queue.push_back(*running_process);//将其放回就绪队列中
delete running_process;
running_process = NULL;
need_schedule = true;
}else{
need_schedule = false;
}
}
}
chip += 1;
}
//所有任务全部完成后，打印一次
print_all(chip);
}
更多推荐
3
0- 0
已为社区贡献2条内容
所有评论(0)