操作系统实验二进程调度(代码+结果).doc

实验二 ：进程调度

一、目的要求：
用C或C++语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解．
二、进程调度算法：
采用最高优先数优先的调度算法（即把处理机分配给优先数最高的进程）和先来先服务算法。
每个进程有一个进程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、优先数、到达时间、需要运行时间、已用CPU时间、进程状态等等。
进程的优先数及需要的运行时间可以事先人为地指定（也可以由随机数产生）。进程的到达时间为进程输入的时间。
进程的运行时间以时间片为单位进行计算。
每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish）三种状态之一。
就绪进程获得 CPU后都只能运行一个时间片。用已占用CPU时间加1来表示。
如果运行一个时间片后，进程的已占用 CPU时间已达到所需要的运行时间，则撤消该进程，如果运行一个时间片后进程的已占用CPU时间还未达所需要的运行时间，也就是进程还需要继续运行，此时应将进程的优先数减1（即降低一级），然后把它插入就绪队列等待CPU。
每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。
重复以上过程，直到所要进程都完成为止。
三 调度算法的流程图如下 :

四、程序代码：
#include<iostream>
using namespace std;
#define MAX 10
struct task_struct
{
char name[10]; /*进程名称*/
int number; /*进程编号*/
float come_time; /*到达时间*/
float run_begin_time; /*开始运行时间*/
float run_time; /*运行时间*/
float run_end_time; /*运行结束时间*/
int priority; /*优先级*/
int order; /*运行次序*/
int run_flag; /*调度标志*/
}tasks[MAX];
int counter; /*实际进程个数*/
int fcfs(); /*先来先服务*/
int ps(); /*优先级调度*/
int sjf(); /*短作业优先*/
int hrrn(); /*响应比高优先*/
int pinput(); /*进程参数输入*/
int poutput(); /*调度结果输出*/

void main()
{
int option;
pinput();
printf("请选择调度算法（0~4）:\n");
printf("1.先来先服务\n");
printf("2.优先级调度\n");
printf(" 3.短作业优先\n");
printf(" 4.响应比高优先\n");
printf(" 0.退出\n");
scanf("%d",&option);
switch (option)
{ case 0:
printf("运行结束。\n");
break;
case 1:
printf("对进程按先来先服务调度:\n\n");
fcfs();
poutput();
break;
case 2:
printf("对进程按优先级调度:\n\n");
ps();
poutput();
break;
case 3:
printf("对进程按短作业优先调度:\n\n");
sjf();
poutput();
break;
case 4:
printf("对进程按响应比高优先调度:\n\n");
hrrn();
poutput();
break;
}
}
int fcfs() /*先来先服务*/
{
float time_temp=0;
int i;
int number_schedul;
time_temp=tasks[0].come_time;
for(i=0;i<counter;i++)
{
tasks[i].run_begin_time=time_temp;
tasks[i].run_end_time=tasks[i].run_begin_time+tasks[i].run_time;
tasks[i].run_flag=1;
time_temp=tasks[i].run_end_time;
number_schedul=i;
tasks[number_schedul].order=i+1;
}
return 0;
}

int ps() /*优先级调度*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter;
int max_priority;
max_priority=tasks[i].priority;
j=1;
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].priority>tasks[i].priority)
{
max_priority=tasks[j].priority;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;
while (temp_counter<counter)
{
max_priority=0;
for(j=0;j<counter;j++)
{ if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if (tasks[j].priority>max_priority)
{
max_priority=tasks[j].priority;
number_schedul=j;
}
} /*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;

}return 0;
}

int sjf() /*短作业优先*/
{
float temp_time=0;
int i=0,j;
int number_schedul,temp_counter;
float run_time;
run_time=tasks[i].run_time;
j=1;
while ((j<counter)&&(tasks[i].come_time==tasks[j].come_time))
{
if (tasks[j].run_time<tasks[i].run_time)
{
run_time=tasks[j].run_time;
i=j;
}
j++;
} /*查找第一个被调度的进程*/
/*对第一个被调度的进程求相应的参数*/
number_schedul=i;
tasks[number_schedul].run_begin_time=tasks[number_schedul].come_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].order=1;
temp_counter=1;
while (temp_counter<counter)
{
for(j=0;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{ run_time=tasks[j].run_time;number_schedul=j;break;}
}

for(j=0;j<counter;j++)
{ if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
if(tasks[j].run_time<run_time)
{run_time=tasks[j].run_time;
number_schedul=j;
}
}
/*查找下一个被调度的进程*/
/*对找到的下一个被调度的进程求相应的参数*/
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
tasks[number_schedul].run_flag=1;
temp_time=tasks[number_schedul].run_end_time;
temp_counter++;
tasks[number_schedul].order=temp_counter;
}return 0;
}

int hrrn() /*响应比高优先*/
{ int j,number_schedul,temp_counter;
float temp_time,respond_rate,max_respond_rate;
/*第一个进程被调度*/
tasks[0].run_begin_time=tasks[0].come_time;
tasks[0].run_end_time=tasks[0].run_begin_time+tasks[0].run_time;
temp_time=tasks[0].run_end_time;
tasks[0].run_flag=1;
tasks[0].order=1;
temp_counter=1;
/*调度其他进程*/
while(temp_counter<counter)
{
max_respond_rate=0;
for(j=1;j<counter;j++)
{
if((tasks[j].come_time<=temp_time)&&(!tasks[j].run_flag))
{ respond_rate=(temp_time-tasks[j].come_time)/tasks[j].run_time;
if (respond_rate>max_respond_rate)
{
max_respond_rate=respond_rate;
number_schedul=j;
}
}
} /*找响应比高的进程*/
tasks[number_schedul].run_begin_time=temp_time;
tasks[number_schedul].run_end_time=tasks[number_schedul].run_begin_time+tasks[number_schedul].run_time;
temp_time=tasks[number_schedul].run_end_time;
tasks[number_schedul].run_flag=1;
temp_counter+=1;
tasks[number_schedul].order=temp_counter;
}
return 0;
}
int pinput() /*进程参数输入*/
{ int i;
printf("please input the process counter:\n");
scanf("%d",&counter);

for(i=0;i<counter;i++)
{ printf("******************************************\n");
printf("please input the process of %d th :\n",i+1);
printf("please input the name:\n");
scanf("%s",tasks[i].name);
printf("please input the number:\n");
scanf("%d",&tasks[i].number);
printf("please input the come_time:\n");
scanf("%f",&tasks[i].come_time);
printf("please input the run_time:\n");
scanf("%f",&tasks[i].run_time);
printf("please input the priority:\n");
scanf("%d",&tasks[i].priority);
tasks[i].run_begin_time=0;
tasks[i].run_end_time=0;
tasks[i].order=0;
tasks[i].run_flag=0;
}
return 0;
}
int poutput() /*调度结果输出*/
{
int i;
float turn_round_time=0,f1,w=0;
printf("任务 编号 到来t 运行t 开始运行t 运行结束t 优先级 运行次序 周转t\n");
for(i=0;i<counter;i++)
{
f1=tasks[i].run_end_time-tasks[i].come_time;
turn_round_time+=f1;
w+=(f1/tasks[i].run_time);
printf(" %s %3d %6.2f %5.2f %7.2f %8.2f %7d %7d %9.2f\n",tasks[i].name,tasks[i].number,tasks[i].come_time,tasks[i].run_time,tasks[i].run_begin_time,tasks[i].run_end_time,tasks[i].priority,tasks[i].order,f1);
}
printf("平均周转时间=%5.2f\n",turn_round_time/counter);
printf("带权周转时间=%5.2f\n",w/counter);
return 0;
}
五、实验结果：