• 进程调度模拟

    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)：

    1. #include 
    2. #include 
    3. #include 
    4. /*常量和状态定义*/
    5. #define PRO_NUM 0x03
    6. #define MAX_TIME 0xFF
    7. /*进程状态宏*/
    8. #define WAIT 0x01
    9. #define RUN 0x02
    10. #define FINISH 0x03
    11. #define ID_ERROR 0x10
    12. #define MIN_PRIOR 0xFF
    13. #define MAX_PRIOR 0x00
    14. typedef unsigned int Uint32;
    15. /*进程PCB*/
    16. struct PCB_Info
    17. {
    18. Uint32 s_id;
    19. Uint32 s_static_prior;
    20. Uint32 s_dynamic_prior;
    21. Uint32 s_start_time;
    22. Uint32 s_need_time;
    23. Uint32 s_used_time;
    24. Uint32 s_state;
    25. };
    26. /*进程队列*/
    27. struct PCB_Info g_queue[5];
    28. Uint32 g_time;
    29. /*模拟进程执行函数*/
    30. void Simulator();
    31. /*初始化5个进程函数*/
    32. void Init_Process();
    33. /*初始化进程队列函数*/
    34. void Init_Queue();
    35. /*创建进程函数*/
    36. Uint32 Create_Process(Uint32 pri, Uint32 needtime);
    37. /*系统运行函数*/
    38. void Run_Process();
    39. /*得到最高优先级进程 ID函数*/
    40. Uint32 Get_PriProcess();
    41. /*进程时间片执行函数*/
    42. void Work_Process(Uint32 id);
    43. /*改变进程状态和优先级函数*/
    44. void Change_Process(Uint32 id);
    45. /*打印进程状态函数*/
    46. void Print_State();
    47. /*结束系统函数*/
    48. void End_Process();
    49. /*入口函数*/
    50. int main(int argc, char *argv[])
    51. {
    52. Simulator();
    53. return 0;
    54. }
    55. void Simulator()
    56. {
    57. Init_Process();
    58. Run_Process();
    59. End_Process();
    60. }
    61. void Init_Process()
    62. {
    63. int i;
    64. Uint32 id;
    65. srand((unsigned)time(NULL));
    66. Init_Queue();
    67. for (i = 0; i
    68. {
    69. /*在这里修改随机数的范围，建议优先级取值为0到4之间，进程工作总时间为1到10之间*/
    70. id = Create_Process(rand() % 4, 1 + rand() % 10);
    71. if (id != ID_ERROR)
    72. {
    73. printf("**********************************\n");
    74. printf("创建进程成功\n");
    75. printf("进程ID号为:%d\n", id);
    76. printf("进程的静态优先权为:%d\n", g_queue[id].s_static_prior);
    77. printf("进程的动态优先权为:%d\n", g_queue[id].s_dynamic_prior);
    78. printf("进程的到达时间为:%d\n", g_queue[id].s_start_time);
    79. printf("进程需要时间为:%d\n", g_queue[id].s_need_time);
    80. printf("进程已用CPU时间为:%d\n", g_queue[id].s_used_time);
    81. printf("进程的状态为:%d\n", g_queue[id].s_state);
    82. printf("\n");
    83. }
    84. else
    85. {
    86. printf("创建进程失败\n");
    87. }
    88. }
    89. }
    90. void Init_Queue()
    91. {
    92. int i;
    93. for (i = 0; i
    94. {
    95. g_queue[i].s_id = i;
    96. g_queue[i].s_dynamic_prior = MIN_PRIOR;
    97. g_queue[i].s_need_time = 0;
    98. g_queue[i].s_start_time = 0;
    99. g_queue[i].s_static_prior = MIN_PRIOR;
    100. g_queue[i].s_used_time = 0;
    101. g_queue[i].s_state = FINISH;
    102. }
    103. }
    104. Uint32 Create_Process(Uint32 pri, Uint32 needtime)
    105. {
    106. int i = 0;
    107. Uint32 id = ID_ERROR;
    108. for (i = 0; i
    109. {
    110. if (g_queue[i].s_state == FINISH)
    111. {
    112. id = g_queue[i].s_id;
    113. g_queue[i].s_dynamic_prior = MIN_PRIOR;
    114. g_queue[i].s_need_time = needtime;
    115. g_queue[i].s_start_time = g_time;
    116. g_queue[i].s_state = WAIT;
    117. g_queue[i].s_static_prior = pri;
    118. g_queue[i].s_used_time = 0x0;
    119. break;
    120. }
    121. }
    122. return id;
    123. }
    124. void Run_Process()
    125. {
    126. Uint32 id;
    127. while ((id = Get_PriProcess()) != ID_ERROR)
    128. {
    129. Work_Process(id);
    130. Change_Process(id);
    131. }
    132. }
    133. void Print_State()
    134. {
    135. int i;
    136. printf("时间 进程ID\t状态 已用时间 需要时间 开始时间 静优先级 动优先级\n");
    137. for (i = 0; i
    138. {
    139. printf("%d\t%d\t%d\t%d\t%d\t%d\t%d\t%d\n", g_time, g_queue[i].s_id, 
    140. g_queue[i].s_state, g_queue[i].s_used_time, g_queue[i].s_need_time,
    141. g_queue[i].s_start_time, g_queue[i].s_static_prior, 
    142. g_queue[i].s_dynamic_prior);
    143. }
    144. }
    145. Uint32 Get_PriProcess()
    146. {
    147. Uint32 id = ID_ERROR;
    148. int i, prev_id = ID_ERROR;
    149. Uint32 prior = MIN_PRIOR * 2, temp_prior;
    150. for (i = 0; i
    151. {
    152. if (g_queue[i].s_state != FINISH)
    153. {
    154. temp_prior = g_queue[i].s_dynamic_prior + g_queue[i].s_static_prior;
    155. if (temp_prior <= prior)
    156. {
    157. id = i;
    158. prior = temp_prior;
    159. }
    160. }
    161. }
    162. return id;
    163. }
    164. void Work_Process(Uint32 id)
    165. {
    166. ++g_time;
    167. g_queue[id].s_state = RUN;
    168. ++g_queue[id].s_used_time;
    169. Print_State();
    170. }
    171. void Change_Process(Uint32 id)
    172. {
    173. int i;
    174. if (g_queue[id].s_need_time == g_queue[id].s_used_time)
    175. {
    176. g_queue[id].s_state = FINISH;
    177. }
    178. else
    179. {
    180. g_queue[id].s_dynamic_prior = MIN_PRIOR;
    181. g_queue[id].s_state = WAIT;
    182. }
    183. for (i = 0; i
    184. {
    185. if ((i != id) && (g_queue[i].s_state != FINISH))
    186. {
    187. g_queue[i].s_dynamic_prior>0 ? --(g_queue[i].s_dynamic_prior) : 0;
    188. }
    189. }
    190. }
    191. void End_Process()
    192. {
    193. printf("所有进程结束状态:\n");
    194. Print_State();
    195. printf("所有进程已经结束!\n");
    196. }

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

    公式：

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

    进程号

    到达时间

    要求执行时间

    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

    代码：

    1. #include 
    2. #include 
    3. #include 
    4.  
    5.  
    6. /*常量和状态定义*/
    7. #define PRO_NUM 0x0b // 11个进程
    8. #define MAX_TIME 0xFF // 动态优先级
    9.  
    10. /*进程状态宏*/
    11. #define WAIT 0x01
    12. #define RUN 0x02
    13. #define FINISH 0x03
    14. #define ID_ERROR 0x10
    15. #define MIN_PRIOR 0xFF
    16. #define MAX_PRIOR 0x00
    17. typedef unsigned int Uint32;
    18.  
    19. /*进程PCB*/
    20. struct PCB_Info
    21. {
    22. 	Uint32 s_id;
    23. 	Uint32 s_static_prior;
    24. 	Uint32 s_dynamic_prior;
    25. 	Uint32 s_start_time; // 改成进程到达时间
    26. 	Uint32 s_need_time;  // 需要时间
    27. 	Uint32 s_used_time; // 已使用cpu时间
    28. 	Uint32 s_state;
    29. };
    30.  
    31. /*周转时间数组*/
    32. Uint32 around_time[11];
    33.  
    34. /*带权周转时间数组*/
    35. float Qaround_time[11];
    36.  
    37. /*进程运行完毕标记*/
    38. bool flag[11];
    39.  
    40.  
    41. /*进程队列*/
    42. struct PCB_Info g_queue[11];
    43. Uint32 g_time;
    44. /*模拟进程执行函数*/
    45. void Simulator();
    46. /*初始化11个进程函数*/
    47. void Init_Process();
    48. /*初始化进程队列函数*/
    49. void Init_Queue();
    50. /*创建进程函数*/
    51. Uint32 Create_Process(Uint32 pri, Uint32 needtime, Uint32 arr_time);
    52. /*系统运行函数*/
    53. void Run_Process();
    54. /*得到最高优先级进程 ID函数*/
    55. Uint32 Get_PriProcess();
    56. /*进程时间片执行函数*/
    57. void Work_Process(Uint32 id);
    58. /*改变进程状态和优先级函数*/
    59. void Change_Process(Uint32 id);
    60. /*打印进程状态函数*/
    61. void Print_State();
    62. /*计算平均周转时间*/
    63. void Avg_around_time();
    64. /*计算带权平均周转时间*/
    65. void Avg_Qaround_time();
    66. /*结束系统函数*/
    67. void End_Process();
    68. /*入口函数*/
    69.  
    70. int main(int argc, char* argv[])
    71. {
    72. 	Simulator();
    73. 	return 0;
    74. }
    75. void Simulator()
    76. {
    77. 	Init_Process();
    78. 	Run_Process();
    79. 	End_Process();
    80. }
    81. void Init_Process()
    82. {
    83. 	int i;
    84. 	Uint32 id;
    85. 	srand((unsigned)time(NULL));
    86. 	Init_Queue();
    87. 	int time, arr_time; // 进程工作总时间自己设定，进程到达时间
    88. 	for (i = 0; i < PRO_NUM; ++i)
    89. 	{
    90. 		/*在这里修改随机数的范围，建议优先级取值为0到12之间，进程工作总时间自己设定，进程到达时间*/
    91. 		printf("进程序列号：%d", i);
    92. 		printf("\n");
    93. 		printf("输入本进程到达的时间:");
    94. 		scanf_s("%d", &arr_time);
    95. 		printf("输入本进程所需要的时间:");
    96. 		scanf_s("%d", &time);
    97. 		id = Create_Process(rand() % 12, time, arr_time);
    98. 		if (id != ID_ERROR)
    99. 		{
    100. 			printf("**********************************\n");
    101. 			printf("创建进程成功\n");
    102. 			printf("进程ID号为:%d\n", id);
    103. 			printf("进程的静态优先权为:%d\n", g_queue[id].s_static_prior);
    104. 			printf("进程的动态优先权为:%d\n", g_queue[id].s_dynamic_prior);
    105. 			printf("进程的到达时间为:%d\n", g_queue[id].s_start_time);
    106. 			printf("进程需要时间为:%d\n", g_queue[id].s_need_time);
    107. 			printf("进程已用CPU时间为:%d\n", g_queue[id].s_used_time);
    108. 			printf("进程的状态为:%d\n", g_queue[id].s_state);
    109. 			printf("\n");
    110. 		}
    111. 		else
    112. 		{
    113. 			printf("创建进程失败\n");
    114. 		}
    115. 	}
    116. }
    117. void Init_Queue()
    118. {
    119. 	int i;
    120. 	for (i = 0; i < PRO_NUM; ++i)
    121. 	{
    122. 		g_queue[i].s_id = i;
    123. 		g_queue[i].s_dynamic_prior = MIN_PRIOR;
    124. 		g_queue[i].s_need_time = 0;
    125. 		g_queue[i].s_start_time = 0;
    126. 		g_queue[i].s_static_prior = MIN_PRIOR;
    127. 		g_queue[i].s_used_time = 0;
    128. 		g_queue[i].s_state = FINISH;
    129. 	}
    130. }
    131. Uint32 Create_Process(Uint32 pri, Uint32 needtime, Uint32 arr_time)
    132. {
    133. 	int i = 0;
    134. 	Uint32 id = ID_ERROR;
    135. 	for (i = 0; i < PRO_NUM; ++i)
    136. 	{
    137. 		if (g_queue[i].s_state == FINISH)
    138. 		{
    139. 			id = g_queue[i].s_id;
    140. 			g_queue[i].s_dynamic_prior = MIN_PRIOR;
    141. 			g_queue[i].s_need_time = needtime;
    142. 			g_queue[i].s_start_time = arr_time;
    143. 			g_queue[i].s_state = WAIT;
    144. 			g_queue[i].s_static_prior = pri;
    145. 			g_queue[i].s_used_time = 0x0;
    146. 			break;
    147. 		}
    148. 	}
    149. 	return id;
    150. }
    151. void Run_Process()
    152. {
    153. 	Uint32 id;
    154. 	while ((id = Get_PriProcess()) != ID_ERROR)
    155. 	{
    156. 		Work_Process(id);
    157. 		Change_Process(id);
    158. 	}
    159. }
    160. void Print_State()
    161. {
    162. 	int i;
    163. 	printf("时间 进程ID\t状态 已用时间 需要时间 开始时间 静优先级 动优先级 周转时间 带权周转时间\n");
    164. 	for (i = 0; i < PRO_NUM; ++i)
    165. 	{
    166. 		// 当进程运行时间等于所需时间时，且进程已运行完毕标志存在
    167. 		// 防止进程运行完毕之后，周转时间仍然增加
    168. 		if (g_queue[i].s_used_time == g_queue[i].s_need_time && flag[i] == false) {
    169. 			around_time[i] = g_time - g_queue[i].s_start_time;
    170. 			Qaround_time[i] = around_time[i] / g_queue[i].s_need_time;
    171. 			flag[i] = true;
    172.  
    173. 		}
    174. 		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,
    175. 			g_queue[i].s_state, g_queue[i].s_used_time, g_queue[i].s_need_time,
    176. 			g_queue[i].s_start_time, g_queue[i].s_static_prior,
    177. 			g_queue[i].s_dynamic_prior,around_time[i],Qaround_time[i]);
    178. 	}
    179. }
    180. Uint32 Get_PriProcess()
    181. {
    182. 	Uint32 id = ID_ERROR;
    183. 	int i, prev_id = ID_ERROR;
    184. 	Uint32 prior = MIN_PRIOR * 2, temp_prior;
    185. 	for (i = 0; i < PRO_NUM; ++i)
    186. 	{
    187. 		// 防止有些进程还没到达就开始运行
    188. 		if (g_queue[i].s_state != FINISH && (g_time >= g_queue[i].s_start_time))
    189. 		{
    190. 			temp_prior = g_queue[i].s_dynamic_prior + g_queue[i].s_static_prior;
    191. 			if (temp_prior <= prior)
    192. 			{
    193. 				id = i;
    194. 				prior = temp_prior;
    195. 			}
    196. 		}
    197. 	}
    198. 	return id;
    199. }
    200. void Work_Process(Uint32 id)
    201. {
    202. 	++g_time;
    203. 	g_queue[id].s_state = RUN;
    204. 	++g_queue[id].s_used_time;
    205. 	Print_State();
    206. }
    207. void Change_Process(Uint32 id)
    208. {
    209. 	int i;
    210. 	if (g_queue[id].s_need_time == g_queue[id].s_used_time)
    211. 	{
    212. 		g_queue[id].s_state = FINISH;
    213. 	}
    214. 	else
    215. 	{
    216. 		g_queue[id].s_dynamic_prior = MIN_PRIOR;
    217. 		g_queue[id].s_state = WAIT;
    218. 	}
    219. 	for (i = 0; i < PRO_NUM; ++i)
    220. 	{
    221. 		if ((i != id) && (g_queue[i].s_state != FINISH))
    222. 		{
    223. 			g_queue[i].s_dynamic_prior > 0 ? --(g_queue[i].s_dynamic_prior) : 0;
    224. 		}
    225. 	}
    226. }
    227. void End_Process()
    228. {
    229. 	printf("所有进程结束状态:\n");
    230. 	Print_State();
    231. 	Avg_around_time();
    232. 	Avg_Qaround_time();
    233. 	printf("所有进程已经结束!\n");
    234. }
    235.  
    236. void Avg_around_time() {
    237. 	float sum = 0;
    238. 	for (int i = 0; i < PRO_NUM; i++) {
    239. 		sum += around_time[i];
    240. 	}
    241. 	printf("平均周转时间是：%.2f", sum / PRO_NUM);
    242. 	printf("\n");
    243. }
    244.  
    245. void Avg_Qaround_time() {
    246. 	float sum = 0;
    247. 	for (int i = 0; i < PRO_NUM; i++) {
    248. 		sum += Qaround_time[i];
    249. 	}
    250. 	printf("平均周转时间是：%.2f", sum / PRO_NUM);
    251. 	printf("\n"); 
    252. }

    运行截图：

    over!

  • 相关阅读:
    数据集搜集
    【面试普通人VS高手系列】线程池如何知道一个线程的任务已经执行完成
    git 本地分支基础操作
    基于电商平台的商品的关键词文本匹配任务 有代码有数据
    关于我们编写好的java程序是如何运行部署的
    GIT 提交规范
    单片非晶磁性测量系统典型磁参数的不确定度与重复性
    配置之别名优化，映射器优化 P7，P8
    【Mysql】表的增删查改
    [计算机毕业设计成品]精品社区心理健康服务平台小程序系统|前后分离VUE[包运行成功]
  • 原文地址：https://blog.csdn.net/princekin_even/article/details/127441257