进程调度模拟_Java-终身学习网

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 
#include 
#include 

#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;

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();

void Init_Process();

void Init_Queue();

Uint32 Create_Process(Uint32 pri, Uint32 needtime);

void Run_Process();

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; i0 ? --(g_queue[i].s_dynamic_prior) : 0;
}
}
}
void End_Process()
{
printf("所有进程结束状态:n");
Print_State();
printf("所有进程已经结束!n");
}

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

公式：

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

进程号	到达时间	要求执行时间
0	0	1
1	1	35
2	2	10
3	3	5
4	6	9
5	7	21
6	9	35
7	11	23
8	12	42
9	13	1
10	14	7

代码：

#include 
#include 
#include 



#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;


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();

void Init_Process();

void Init_Queue();

Uint32 Create_Process(Uint32 pri, Uint32 needtime, Uint32 arr_time);

void Run_Process();

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)
	{
		
		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号为:%dn", id);
			printf("进程的静态优先权为:%dn", g_queue[id].s_static_prior);
			printf("进程的动态优先权为:%dn", g_queue[id].s_dynamic_prior);
			printf("进程的到达时间为:%dn", g_queue[id].s_start_time);
			printf("进程需要时间为:%dn", g_queue[id].s_need_time);
			printf("进程已用CPU时间为:%dn", g_queue[id].s_used_time);
			printf("进程的状态为:%dn", 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("时间 进程IDt状态 已用时间 需要时间 开始时间 静优先级 动优先级 周转时间 带权周转时间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("%dt%dt%dt%dt%dt%dt%dt%dt  %dt   %.2fn", 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!

进程调度模拟

Java相关栏目本月热门文章