WHCSRL 技术网

C语言 操作系统实验 四种调度(最短优先算法SJF)_key

注:

本文是四个调度算法的第一篇算法。

本文是根据CSDN上某一FCFS调度算法魔改来的,所以FCFS的算法不会发到网站。

我是个菜鸡,发文是为了纪念自己完成了代码,以及累计自己的经验。

如有知识错误或者算法有逻辑漏洞请各位大佬高抬贵手。

实验环境:win10、VS2019(C++)

PS:虽然是cpp文件,实际上是披着cpp的c

        运行前,首先要在预处理器上插入_CRT_SECURE_NO_WARNINGS,避免运行错误,在插入前要用;隔开。

        具体位置就在解决方案下面一栏(名字是自己起的),右键属性即可找到。

  像这个样子

代码部分核心思路有三段:

一、将输入的链表按提交时间从小到大码好

        这一部分的核心思路是为了保证后面某一单元节点的提交时间远大于之前所有运行时间和最早提交时间的总和的情况下,即使其执行时间最短,其执行顺序也会放入到它之前的代码段后。

        这段思路和下一个核心思路是相连的。

上代码:

  1. void linkpcb()//先将链表尾插法连接起来 //如果行不通就执行方案2 即将这些先按到达顺序排序后,通过dolevel进行分层,在用sort进行最短排序
  2. {
  3. int insert = 0;
  4. if ((ready == NULL) || ((p->tr) <= (ready->tr) && p->tn < ready->tn )) /*提交兼执行时间最小者,插入队首*/
  5. {
  6. p->link = ready;
  7. ready = p;
  8. }
  9. else /* 进程比较提交时间,插入适当的位置中*/
  10. {
  11. first = ready;
  12. second = first->link;
  13. while (second != NULL)
  14. {
  15. if ((p->tr) < (second->tr)) /*若插入作业比当前作业提交时间小,*/
  16. {
  17. /*插入到当前进程前面*/
  18. p->link = second;//p插入到second前面
  19. first->link = p;
  20. second = NULL;//second只能在连接好的链表上运行
  21. insert = 1;
  22. }
  23. else /* 插入进程提交时间最高,则插入到队尾*/
  24. {
  25. first = first->link;
  26. second = second->link;
  27. }
  28. }
  29. if (insert == 0) first->link = p;//循环到最后若依旧没有比second大的,则first此时是p的前一个
  30. }
  31. }

(这段代码就是CSDN上某一FCSF的唯一核心代码段,且几乎没有修改)

二、计算提交时间和当前总时间的关系

        计算第一个提交的提交时间和执行时间的总值sum,因为第一个提交,所以第一个执行,所有提交时间小于sum的单元节点都是可以在第一个单元节点执行后能继续运行的,而不是前一个以及执行结束,而后面还没提交的情况出现。

代码:

  1. void dolevel()
  2. {
  3. if(second->tr <= sum)
  4. {
  5. sum = sum + second->tn;
  6. }
  7. else
  8. {
  9. sum = second->tr + second->tn;
  10. second->flag = 0;
  11. }
  12. second = second->link;
  13. }

在结构体中立一个小旗子flag = 1;

如果出现断档的情况,直接砍倒小旗子 flag = 0。

sum的值由新的提交时间+执行时间重新计算。

这样就会出现断档的首节点,每一档的层次就出现了。

三、将链表再次排序输出,排序方法按最短执行时间大小决定

先上代码:

  1. void sort() /* 建立对作业进行提交时间排列函数,分出第一层*/
  2. {
  3. first = ready;//first归位
  4. p = ready;
  5. last = ready;
  6. if (last->flag == 0)//置1
  7. {
  8. last->flag = 1;
  9. }
  10. while ((last->flag == 1 && last->link != NULL))//一层中找到最小的 最后一个会被强制退出
  11. {
  12. if (last->tn < p->tn)
  13. {
  14. p = last;
  15. }
  16. last = last->link;
  17. if (last->link == NULL)//在最后一个被踢出前先进行比较
  18. {
  19. if (last->tn < p->tn)
  20. {
  21. p = last;
  22. }
  23. }
  24. }
  25. last = p->link;
  26. if (ready == p)//防止最小可能是头单元节点造成ready成空指针
  27. {
  28. ready = ready->link;
  29. }
  30. while (ready == p)//防止最小是自己
  31. {
  32. first = first->link;
  33. }
  34. first->link = last;
  35. p->link = NULL;
  36. check();
  37. disp(p);
  38. eti += p->ti;
  39. ewi += p->wi;
  40. running();
  41. }

        这段代码的思路是在同一个档次内不断循环,查找执行时间最小的节点p,输出并销毁当前节点,直至此档内全部输出完毕。

        这里没有记录同一档次内的个数,所以flag = 0;的作用就显现出来了

        flag置1是为了在断档时能继续输出设置的,而此时前一档的单元节点已经全部输出完毕。

        在第一个while中有一个单独的if判断,如果不加此判断,则会出现最后一个单元节点直接跳过不参与运算。

完整代码:

  1. #include "stdio.h"
  2. #include <stdlib.h>
  3. #include <conio.h>
  4. #define getpch(type) (type*)malloc(sizeof(type))
  5. #define NULL 0
  6. //定义作业jcb结构体
  7. struct jcb
  8. {
  9. char name[100];
  10. int tr;//作业提交时间
  11. int tn;//作业运行时间
  12. int ts;//作业开始时间
  13. int tf;//作业完成时间
  14. float ti;//作业周转时间
  15. float wi;//作业带权周转时间
  16. int flag;//顺序
  17. struct jcb* link;
  18. }*ready = NULL, * h, * p;
  19. typedef struct jcb JCB;
  20. JCB* first, * second, * last;
  21. int time = 0;
  22. int num = 0; //作业数量
  23. int sum = 0;//目前总时间
  24. float eti = 0.0;
  25. float ewi = 0.0;
  26. void linkpcb()//先将链表尾插法连接起来,将这些先按到达顺序排序后,通过dolevel进行分层,在用sort进行最短排序
  27. {
  28. int insert = 0;
  29. if ((ready == NULL) || ((p->tr) <= (ready->tr) && p->tn < ready->tn )) /*提交兼执行时间最小者,插入队首*/
  30. {
  31. p->link = ready;
  32. ready = p;
  33. }
  34. else /* 进程比较提交时间,插入适当的位置中*/
  35. {
  36. first = ready;
  37. second = first->link;
  38. while (second != NULL)
  39. {
  40. if ((p->tr) < (second->tr)) /*若插入作业比当前作业提交时间小,*/
  41. {
  42. /*插入到当前进程前面*/
  43. p->link = second;//p插入到second前面
  44. first->link = p;
  45. second = NULL;//second只能在连接好的链表上运行
  46. insert = 1;
  47. }
  48. else /* 插入进程提交时间最高,则插入到队尾*/
  49. {
  50. first = first->link;
  51. second = second->link;
  52. }
  53. }
  54. if (insert == 0) first->link = p;//循环到最后若依旧没有比second大的,则first此时是p的前一个
  55. }
  56. }
  57. void dolevel()
  58. {
  59. if(second->tr <= sum)
  60. {
  61. sum = sum + second->tn;
  62. }
  63. else
  64. {
  65. sum = second->tr + second->tn;
  66. second->flag = 0;
  67. }
  68. second = second->link;
  69. }
  70. void destroy() /*建立作业撤消函数(进程运行结束,卸载作业)*/
  71. {
  72. free(p);
  73. }
  74. void running() /* 建立作业就绪函数(作业运行时间到,置就绪状态*/
  75. {
  76. if (p->link == NULL)
  77. destroy(); /* 调用destroy函数*/
  78. }
  79. void disp(JCB* pr) /*建立作业显示函数,用于显示当前作业*/
  80. {
  81. printf(" %%s ", pr->name);
  82. printf(" %%d ", pr->tr);
  83. printf(" %%d ", pr->tn);
  84. printf(" %%d ", pr->ts);
  85. printf(" %%d ", pr->tf);
  86. printf(" %%-0.2f ", pr->ti);
  87. printf(" %%-0.2f ", pr->wi);
  88. printf(" ");
  89. }
  90. void check() /* 建立作业查看函数 */
  91. {
  92. //累加变量time 记录当前用时 !!!
  93. if (time >= p->tr)
  94. {
  95. p->ts = time;
  96. p->tf = p->ts + p->tn;
  97. time = p->tf;
  98. }
  99. else
  100. {
  101. p->ts = p->tr;
  102. p->tf = p->ts + p->tn;
  103. time = p->tf;
  104. }
  105. p->ti = p->tf - p->tr;
  106. p->wi = p->ti / p->tn;
  107. //!!!
  108. }
  109. void sort() /* 建立对作业进行提交时间排列函数,分出第一层*/
  110. {
  111. first = ready;//first归位
  112. p = ready;
  113. last = ready;
  114. if (last->flag == 0)//置1
  115. {
  116. last->flag = 1;
  117. }
  118. while ((last->flag == 1 && last->link != NULL))//一层中找到最小的 最后一个会被强制退出
  119. {
  120. if (last->tn < p->tn)
  121. {
  122. p = last;
  123. }
  124. last = last->link;
  125. if (last->link == NULL)//在最后一个被踢出前先进行比较
  126. {
  127. if (last->tn < p->tn)
  128. {
  129. p = last;
  130. }
  131. }
  132. }
  133. last = p->link;
  134. if (ready == p)//防止最小可能是头单元节点造成ready成空指针
  135. {
  136. ready = ready->link;
  137. }
  138. while (ready == p)//防止最小是自己
  139. {
  140. first = first->link;
  141. }
  142. first->link = last;
  143. p->link = NULL;
  144. check();
  145. disp(p);
  146. eti += p->ti;
  147. ewi += p->wi;
  148. running();
  149. }
  150. void input() /* 建立作业控制块函数*/
  151. {
  152. int i;
  153. printf(" 请输入即将运行的进程总数目");
  154. scanf("%%d", &num);
  155. for (i = 0; i < num; i++)
  156. {
  157. p = getpch(JCB);
  158. printf(" 输入作业名:");
  159. scanf("%%s", p->name);
  160. printf(" 输入作业提交时间:");
  161. scanf("%%d", &p->tr);
  162. printf(" 输入作业运行时间:");
  163. scanf("%%d", &p->tn);
  164. printf(" ");
  165. p->ts = 0;
  166. p->tf = 0;
  167. p->ti = 0.0f;
  168. p->wi = 0.0f;
  169. p->link = NULL;
  170. p->flag = 1;
  171. linkpcb();
  172. }//此时排序顺序是 提交顺序
  173. p->link = NULL;
  174. printf(" 名称 提交 运行 开始 完成 周转 带权周转 ");
  175. first = ready;
  176. second = ready->link;//第二个
  177. last = ready;
  178. sum = ready->tr + ready->tn;
  179. p = ready;
  180. check();//对最先到达那个进行特殊输出
  181. disp(p);
  182. eti += p->ti;
  183. ewi += p->wi;
  184. ready = ready->link;
  185. first = ready;
  186. last = ready;
  187. p->link = NULL;
  188. running();
  189. p = ready;
  190. do
  191. {
  192. dolevel();
  193. } while (second->link != NULL);//second此时是末尾节点
  194. for (i = 1; i < num; i++)
  195. {
  196. sort(); /* 调用sort函数,对提交顺序和执行时间进行比较*/
  197. }
  198. }
  199. int main() /*主函数*/
  200. {
  201. input();//此时已经按提交顺序排好了
  202. eti /= num;
  203. ewi /= num;
  204. printf(" 该组作业平均周转时间为:%%0.2f", eti);
  205. printf(" 该组作业平均带权周转时间为:%%0.2f", ewi);
  206. return 0;
  207. }

 由于时间关系,详细内容会在时间片轮转法中详细讲述。

推荐阅读