进程调度模拟

进程调度模拟"/>

进程调度模拟

1、核心思想：采用最高优先数的调度算法（即把处理机分配给优先数最高的进程）。

2、实现方案：

（1）先定义每个进程有一个进程控制块（PCB）表示。进程控制块包含如下信息：

• 进程名 id
• 静态优先级 static_prior
• 动态优先级 dynamic_prior
• 到达时间 start_time
• 需要运行时间 need_time
• 已用 CPU 时间 used_time
• 进程状态 state

（2）其次设计每个进程状态为就绪 W（Wait）、运行 R（Run）、或完成 F（Finish）三种状态。

（3）使用一个固定就绪队列与进程静、动态优先级相结合的方式实现进程调度。 进程优先级范围0~0xFF（即 0~255），以小的数字为高优先级，大的数字为低优先级。每次都使用循环得到最高优先级的进程并执行（静态优先级+动态优先级的值最小的进程），然后将其动态优先级重置为最低 0xFF，并将其他进程动态优先级减 1 以提高，如此保证每个进程都有机会运行。

（4）进程的静态优先级及需要的运行时间由随机数产生。每个进程在创建时默认动 态优先级为 0xFF。

（5）进程的运行时间以时间片为单位进行计算。就绪进程获得 CPU 后都只能运行 一个时间片。利用已占用 CPU 时间加 1 来表示。如果运行一个时间片后，进程的已占用 CPU 时间已达到所需要的运行时间，则撤销该进程。如果运行一个时间片后，进程的已占用 CPU 时间还未达到所需要的运行时间，

此时将进程的动态优先级重置为最低 0xFF，然后将它插入就绪队列等待 CPU。

（6）每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB，以便进行检查。重复以上过程，直到所有的进程都完成为止。

3、进程调度示意图

示例：

代码(procSched.c)：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
/*常量和状态定义*/
#define PRO_NUM 0x03
#define MAX_TIME 0xFF
/*进程状态宏*/
#define WAIT 0x01
#define RUN 0x02
#define FINISH 0x03
#define ID_ERROR 0x10
#define MIN_PRIOR 0xFF
#define MAX_PRIOR 0x00
typedef unsigned int Uint32;
/*进程PCB*/
struct PCB_Info
{
Uint32 s_id;
Uint32 s_static_prior;
Uint32 s_dynamic_prior;
Uint32 s_start_time;
Uint32 s_need_time;
Uint32 s_used_time;
Uint32 s_state;
};
/*进程队列*/
struct PCB_Info g_queue[5];
Uint32 g_time;
/*模拟进程执行函数*/
void Simulator();
/*初始化5个进程函数*/
void Init_Process();
/*初始化进程队列函数*/
void Init_Queue();
/*创建进程函数*/
Uint32 Create_Process(Uint32 pri, Uint32 needtime);
/*系统运行函数*/
void Run_Process();
/*得到最高优先级进程 ID函数*/
Uint32 Get_PriProcess();
/*进程时间片执行函数*/
void Work_Process(Uint32 id);
/*改变进程状态和优先级函数*/
void Change_Process(Uint32 id);
/*打印进程状态函数*/
void Print_State();
/*结束系统函数*/
void End_Process();
/*入口函数*/
int main(int argc, char *argv[])
{
Simulator();
return 0;
}
void Simulator()
{
Init_Process();
Run_Process();
End_Process();
}
void Init_Process()
{
int i;
Uint32 id;
srand((unsigned)time(NULL));
Init_Queue();
for (i = 0; i<PRO_NUM; ++i)
{
/*在这里修改随机数的范围，建议优先级取值为0到4之间，进程工作总时间为1到10之间*/
id = Create_Process(rand() % 4, 1 + rand() % 10);
if (id != ID_ERROR)
{
printf("**********************************\n");
printf("创建进程成功\n");
printf("进程ID号为:%d\n", id);
printf("进程的静态优先权为:%d\n", g_queue[id].s_static_prior);
printf("进程的动态优先权为:%d\n", g_queue[id].s_dynamic_prior);
printf("进程的到达时间为:%d\n", g_queue[id].s_start_time);
printf("进程需要时间为:%d\n", g_queue[id].s_need_time);
printf("进程已用CPU时间为:%d\n", g_queue[id].s_used_time);
printf("进程的状态为:%d\n", g_queue[id].s_state);
printf("\n");
}
else
{
printf("创建进程失败\n");
}
}
}
void Init_Queue()
{
int i;
for (i = 0; i<PRO_NUM; ++i)
{
g_queue[i].s_id = i;
g_queue[i].s_dynamic_prior = MIN_PRIOR;
g_queue[i].s_need_time = 0;
g_queue[i].s_start_time = 0;
g_queue[i].s_static_prior = MIN_PRIOR;
g_queue[i].s_used_time = 0;
g_queue[i].s_state = FINISH;
}
}
Uint32 Create_Process(Uint32 pri, Uint32 needtime)
{
int i = 0;
Uint32 id = ID_ERROR;
for (i = 0; i<PRO_NUM; ++i)
{
if (g_queue[i].s_state == FINISH)
{
id = g_queue[i].s_id;
g_queue[i].s_dynamic_prior = MIN_PRIOR;
g_queue[i].s_need_time = needtime;
g_queue[i].s_start_time = g_time;
g_queue[i].s_state = WAIT;
g_queue[i].s_static_prior = pri;
g_queue[i].s_used_time = 0x0;
break;
}
}
return id;
}
void Run_Process()
{
Uint32 id;
while ((id = Get_PriProcess()) != ID_ERROR)
{
Work_Process(id);
Change_Process(id);
}
}
void Print_State()
{
int i;
printf("时间 进程ID\t状态 已用时间 需要时间 开始时间 静优先级 动优先级\n");
for (i = 0; i<PRO_NUM; ++i)
{
printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n", g_time, g_queue[i].s_id, 
g_queue[i].s_state, g_queue[i].s_used_time, g_queue[i].s_need_time,
g_queue[i].s_start_time, g_queue[i].s_static_prior, 
g_queue[i].s_dynamic_prior);
}
}
Uint32 Get_PriProcess()
{
Uint32 id = ID_ERROR;
int i, prev_id = ID_ERROR;
Uint32 prior = MIN_PRIOR * 2, temp_prior;
for (i = 0; i<PRO_NUM; ++i)
{
if (g_queue[i].s_state != FINISH)
{
temp_prior = g_queue[i].s_dynamic_prior + g_queue[i].s_static_prior;
if (temp_prior <= prior)
{
id = i;
prior = temp_prior;
}
}
}
return id;
}
void Work_Process(Uint32 id)
{
++g_time;
g_queue[id].s_state = RUN;
++g_queue[id].s_used_time;
Print_State();
}
void Change_Process(Uint32 id)
{
int i;
if (g_queue[id].s_need_time == g_queue[id].s_used_time)
{
g_queue[id].s_state = FINISH;
}
else
{
g_queue[id].s_dynamic_prior = MIN_PRIOR;
g_queue[id].s_state = WAIT;
}
for (i = 0; i<PRO_NUM; ++i)
{
if ((i != id) && (g_queue[i].s_state != FINISH))
{
g_queue[i].s_dynamic_prior>0 ? --(g_queue[i].s_dynamic_prior) : 0;
}
}
}
void End_Process()
{
printf("所有进程结束状态:\n");
Print_State();
printf("所有进程已经结束!\n");
}

思考练习：设计编写一个进程调度模拟程序（用C语言实现），完成对以下N个进程进行调度，并为整个进程序列计算出平均周转时间和平均带权周转时间。根据程序执行的打印结果，通过检测和笔算的一致性，来进行校验。

公式：

周转时间=完成时间-提交时刻
平均周转时间=周转总时间/作业总个数
带权周转时间=周转时间/运行时间
平均带权周转时间=带权周转总时间/作业总个数

代码：

#include <stdlib.h>
#include <stdio.h>
#include <time.h>/*常量和状态定义*/
#define PRO_NUM 0x0b // 11个进程
#define MAX_TIME 0xFF // 动态优先级/*进程状态宏*/
#define WAIT 0x01
#define RUN 0x02
#define FINISH 0x03
#define ID_ERROR 0x10
#define MIN_PRIOR 0xFF
#define MAX_PRIOR 0x00
typedef unsigned int Uint32;/*进程PCB*/
struct PCB_Info
{Uint32 s_id;Uint32 s_static_prior;Uint32 s_dynamic_prior;Uint32 s_start_time; // 改成进程到达时间Uint32 s_need_time;  // 需要时间Uint32 s_used_time; // 已使用cpu时间Uint32 s_state;
};/*周转时间数组*/
Uint32 around_time[11];/*带权周转时间数组*/
float Qaround_time[11];/*进程运行完毕标记*/
bool flag[11];/*进程队列*/
struct PCB_Info g_queue[11];
Uint32 g_time;
/*模拟进程执行函数*/
void Simulator();
/*初始化11个进程函数*/
void Init_Process();
/*初始化进程队列函数*/
void Init_Queue();
/*创建进程函数*/
Uint32 Create_Process(Uint32 pri, Uint32 needtime, Uint32 arr_time);
/*系统运行函数*/
void Run_Process();
/*得到最高优先级进程 ID函数*/
Uint32 Get_PriProcess();
/*进程时间片执行函数*/
void Work_Process(Uint32 id);
/*改变进程状态和优先级函数*/
void Change_Process(Uint32 id);
/*打印进程状态函数*/
void Print_State();
/*计算平均周转时间*/
void Avg_around_time();
/*计算带权平均周转时间*/
void Avg_Qaround_time();
/*结束系统函数*/
void End_Process();
/*入口函数*/int main(int argc, char* argv[])
{Simulator();return 0;
}
void Simulator()
{Init_Process();Run_Process();End_Process();
}
void Init_Process()
{int i;Uint32 id;srand((unsigned)time(NULL));Init_Queue();int time, arr_time; // 进程工作总时间自己设定，进程到达时间for (i = 0; i < PRO_NUM; ++i){/*在这里修改随机数的范围，建议优先级取值为0到12之间，进程工作总时间自己设定，进程到达时间*/printf("进程序列号：%d", i);printf("\n");printf("输入本进程到达的时间:");scanf_s("%d", &arr_time);printf("输入本进程所需要的时间:");scanf_s("%d", &time);id = Create_Process(rand() % 12, time, arr_time);if (id != ID_ERROR){printf("**********************************\n");printf("创建进程成功\n");printf("进程ID号为:%d\n", id);printf("进程的静态优先权为:%d\n", g_queue[id].s_static_prior);printf("进程的动态优先权为:%d\n", g_queue[id].s_dynamic_prior);printf("进程的到达时间为:%d\n", g_queue[id].s_start_time);printf("进程需要时间为:%d\n", g_queue[id].s_need_time);printf("进程已用CPU时间为:%d\n", g_queue[id].s_used_time);printf("进程的状态为:%d\n", g_queue[id].s_state);printf("\n");}else{printf("创建进程失败\n");}}
}
void Init_Queue()
{int i;for (i = 0; i < PRO_NUM; ++i){g_queue[i].s_id = i;g_queue[i].s_dynamic_prior = MIN_PRIOR;g_queue[i].s_need_time = 0;g_queue[i].s_start_time = 0;g_queue[i].s_static_prior = MIN_PRIOR;g_queue[i].s_used_time = 0;g_queue[i].s_state = FINISH;}
}
Uint32 Create_Process(Uint32 pri, Uint32 needtime, Uint32 arr_time)
{int i = 0;Uint32 id = ID_ERROR;for (i = 0; i < PRO_NUM; ++i){if (g_queue[i].s_state == FINISH){id = g_queue[i].s_id;g_queue[i].s_dynamic_prior = MIN_PRIOR;g_queue[i].s_need_time = needtime;g_queue[i].s_start_time = arr_time;g_queue[i].s_state = WAIT;g_queue[i].s_static_prior = pri;g_queue[i].s_used_time = 0x0;break;}}return id;
}
void Run_Process()
{Uint32 id;while ((id = Get_PriProcess()) != ID_ERROR){Work_Process(id);Change_Process(id);}
}
void Print_State()
{int i;printf("时间 进程ID\t状态 已用时间 需要时间 开始时间 静优先级 动优先级 周转时间 带权周转时间\n");for (i = 0; i < PRO_NUM; ++i){// 当进程运行时间等于所需时间时，且进程已运行完毕标志存在// 防止进程运行完毕之后，周转时间仍然增加if (g_queue[i].s_used_time == g_queue[i].s_need_time && flag[i] == false) {around_time[i] = g_time - g_queue[i].s_start_time;Qaround_time[i] = around_time[i] / g_queue[i].s_need_time;flag[i] = true;}printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\t  %d\t   %.2f\n", g_time, g_queue[i].s_id,g_queue[i].s_state, g_queue[i].s_used_time, g_queue[i].s_need_time,g_queue[i].s_start_time, g_queue[i].s_static_prior,g_queue[i].s_dynamic_prior,around_time[i],Qaround_time[i]);}
}
Uint32 Get_PriProcess()
{Uint32 id = ID_ERROR;int i, prev_id = ID_ERROR;Uint32 prior = MIN_PRIOR * 2, temp_prior;for (i = 0; i < PRO_NUM; ++i){// 防止有些进程还没到达就开始运行if (g_queue[i].s_state != FINISH && (g_time >= g_queue[i].s_start_time)){temp_prior = g_queue[i].s_dynamic_prior + g_queue[i].s_static_prior;if (temp_prior <= prior){id = i;prior = temp_prior;}}}return id;
}
void Work_Process(Uint32 id)
{++g_time;g_queue[id].s_state = RUN;++g_queue[id].s_used_time;Print_State();
}
void Change_Process(Uint32 id)
{int i;if (g_queue[id].s_need_time == g_queue[id].s_used_time){g_queue[id].s_state = FINISH;}else{g_queue[id].s_dynamic_prior = MIN_PRIOR;g_queue[id].s_state = WAIT;}for (i = 0; i < PRO_NUM; ++i){if ((i != id) && (g_queue[i].s_state != FINISH)){g_queue[i].s_dynamic_prior > 0 ? --(g_queue[i].s_dynamic_prior) : 0;}}
}
void End_Process()
{printf("所有进程结束状态:\n");Print_State();Avg_around_time();Avg_Qaround_time();printf("所有进程已经结束!\n");
}void Avg_around_time() {float sum = 0;for (int i = 0; i < PRO_NUM; i++) {sum += around_time[i];}printf("平均周转时间是：%.2f", sum / PRO_NUM);printf("\n");
}void Avg_Qaround_time() {float sum = 0;for (int i = 0; i < PRO_NUM; i++) {sum += Qaround_time[i];}printf("平均周转时间是：%.2f", sum / PRO_NUM);printf("\n"); 
}

运行截图：

over!