操作系统进程调度编程.docx

1. 实验内容编写一个单处理机下的进程调度程序，模拟操作系统对进程的调度。2. 实验目的进程是操作系统中最基本、最重要的概念，进程调度又是操作系统的核心模块。本实验要求学生独立设计并实现进程调度模拟程序，以加深对进程控制块概念和各种进程调度算法的理解。3. 实验要求可以随机输入若干进程，支持先来先服务、短作业优先、最短剩余时间优先、时间片轮转、动态优先级调度算法，能够输出进程的调度过程。4. 程序中使用的数据结构及符号说明(1). PCB （进程控制块）1. struct pcb2. 3. int id;4. int arrive;5. int run;6. int priority;7. int time;8. bool done;9. ;说明：在进程控制块中记录了以下信息：数据项类型说明idint进程号pidarriveint进程到达时间runint进程运行时间priorityint进程优先级timeint进程运行的时间片donebool记录进程是否已经完成运行(2). PCB数组1. struct pcb processN;说明：process数组用于保存调度所涉及的进程的信息。5. 各种调度算法的处理流程，重要模块的详细设计及功能和接口说明(1). 预处理算法流程对应程序代码及注释1. int main()2. 3. / 初始化PCB数组4. memset(process, 0, sizeof(process);5. / 读入调度类型6. int type;7. scanf(%d,&type);8. / 读入调度进程数据9. for ( n = 0; scanf(%d/%d/%d/%d/%d,10. &processn.id, 11. &processn.arrive, 12. &processn.run, 13. &processn.priority, 14. &processn.time); n + );15. / 根据调度类型转到子程序进行调度16. switch ( type )17. 18. / 各调度子程序：19. case 1: fcfs(); break; / 先来先服务20. case 2: sjf(); break; / 短作业优先21. case 3: sltf(); break; / 最短剩余时间优先22. case 4: tpt(); break; / 时间片轮转23. case 5: dp(); break; / 动态优先级24. 25. return 0;26. (2). 先来先服务算法逻辑流程本题中算法实际流程对应程序代码及注释1. void fcfs()2. 3. / 按到达时间、pid排序4. sort(process, process+n, cmp_ar_id);5. / 初始化系统时间6. int time = 0;7. / 顺序遍历各进程8. for ( int i = 0; i n; i + )9. 10. / 若当前系统时间时没有待调度进程11. if ( time processi.arrive )12. 13. / 等待系统时间到达下一个进程到来14. time = processi.arrive;15. 16. / 否则17. / 进行进程调度18. printf(%d/%d/%d/%d/%dn, i+1, processi.id, time, time + processi.run, processi.priority);19. / 进程运行，系统时间流逝20. time += processi.run;21. 22. return ;23. (3). 短作业优先算法逻辑流程本题中算法实际流程对应程序代码及注释1. void sjf()2. 3. / 按运行时间、pid排序4. sort(process, process+n, cmp_run_id);5. / 初始化系统时间6. int time = 0;7. / 有未运行进程8. for ( int m = 1; m = n; )9. 10. / 找出已到达的未运行进程中，运行时间最短的进程11. int min = INT_MAX, mini = -1;12. for ( int i = 0; i n; i + )13. 14. if ( processi.arrive = time & / 已到达的进程15. processi.run min & / 运行时间最短的进程16. ! processi.done ) / 未运行的进程17. 18. min = processi.run;19. mini = i;20. 21. 22. / 若当前系统时间时没有待调度进程23. if ( -1 = mini )24. 25. / 找出下一个到达的时间26. int mint = INT_MAX;27. for ( int i = 0; i n; i + )28. 29. if ( processi.arrive mint & / 最近的到达时间30. ! processi.done ) / 未运行的进程31. 32. mint = processi.arrive;33. 34. 35. / 等待系统时间到达下一个进程到来36. time = mint;37. continue;38. 39. / 否则40. / 进行进程调度41. printf(%d/%d/%d/%d/%dn, m, processmini.id, time, time + processmini.run, processmini.priority);42. / 进程运行，系统时间流逝43. time += processmini.run;44. processmini.done = true;45. / 已运行进程数+146. m +;47. 48. (4). 最短剩余时间优先算法逻辑流程本题中算法实际流程主流程：调度器配置阶段：预调度阶段：进程调度阶段：进程运行阶段：对应程序代码及注释1. void sltf()2. 3. /* 调度器配置阶段 */4. / 按到达时间、运行时间、pid排序5. sort(process, process+n, cmp_run);6. / 初始化系统时间7. int time = process0.arrive;8. / 初始化调度程序配置9. int execi = -1, start = time;10. int k = 0, m = 0;11. / 有未运行进程12. for ( int i = 0; m n; )13. 14. /* 预调度阶段 */15. / 找到在当前系统时间已经到达的进程16. for ( ; processi.arrive = time & i n; i + );17. / 在已到达进程中查找剩余运行时间最短的未结束进程18. int min = INT_MAX, mini = -1;19. for ( int j = 0; j i; j + )20. 21. if ( processj.run min & ! processj.done )22. 23. min = processj.run;24. mini = j;25. 26. 27. / 若在当前系统时间之前到达的进程均已经结束28. if ( -1 = mini )29. 30. / 等待下一个进程到达后重新进行调度31. time = processi.arrive;32. continue;33. 34. / 若当前没有正在运行的进程35. if ( -1 = execi )36. 37. / 则执行找到的进程38. execi = mini;39. / 进程的开始运行时间设为现在的时间40. start = std:max(processexeci.arrive, time);41. 42. /* 进程调度阶段 */43. / 若找到的进程剩余运行时间小于当前正在运行进程的剩余运行时间44. if ( processmini.run = processexeci.run | runnable = 0 )56. 57. time += processexeci.run;58. printf(%d/%d/%d/%d/%dn, + k, processexeci.id, start, time, processexeci.priority);59. processexeci.run = 0;60. processexeci.done = true;61. m +;62. execi = -1;63. start = time;64. 65. / 若进程不能完成运行则运行一个时间片66. else67. 68. time += runnable;69. processexeci.run -= runnable;70. 71. 72. return ;73. 74.(5). 时间片轮转算法逻辑流程本题中算法实际流程对应程序代码及注释1. void tpt()2. 3. / 初始化进程队列4. queue qu;5. processn.arrive = INT_MAX;6. / 按到达时间、pid排序7. sort(process, process+n, cmp_ar_id);8. / 初始化系统时间9. int time = process0.arrive;10. / 所有进程是否均完成运行11. for ( int i = 0, k = 1, m = 0; m n; )12. 13. / 如果队列为空14. if ( qu.empty() )15. 16. / 等待新的进程到达17. time = processi.arrive;18. / 将当前系统时间之前的进程放入队列19. for ( ; processi.arrive = time & i temp.time )29. 30. / 进程调度31. printf(%d/%d/%d/%d/%dn, k +, temp.id, time, time + temp.time, temp.priority);32. / 将进程运行一个时间片33. time += temp.time;34. temp.run -= temp.time;35. / 将当前系统时间之前的进程放入队列36. for ( ; processi.arrive = time & i n; i + )37. 38. qu.push(processi);39. 40. / 将进程放回队列41. qu.push(temp);42. 43. / 如果进程可以完成运行44. else45. 46. / 进程调度47. printf(%d/%d/%d/%d/%dn, k +, temp.id, time, time + temp.run, temp.priority);48. / 将进程运行完49. time += temp.run;50. / 将当前系统时间之前的进程放入队列51. for ( ; processi.arrive = time & i n; i + )52. 53. qu.push(processi);54. 55. m +;56. 57. 58. return ;59. (6). 动态优先级算法逻辑流程本题中算法实际流程对应程序代码及注释1. void dp()2. 3. / 按到达时间、pid排序4. sort(process, process+n, cmp_ar_id);5. / 初始化系统时间6. int time = process0.arrive;7. int last = time;8. int min, mini = -1;9. for ( int i = 0, k = 1, m = 0; m n; )10. 11. / 找到在当前系统时间已经到达的进程12. for ( ; processi.arrive = time & i n; i + )13. 14. / 若进程在时间片中间到达，则算作是运行了一个时间片，优先级+115. if ( last processi.arrive & processi.arrive 0)?(processi.priority -1):0;18. 19. 20. / 找到优先级最高的进程21. min = INT_MAX, mini = -1;22. for ( int j = 0; j i; j + )23. 24. if ( processj.priority min & ! processj.done )25. 26. min = processj.priority;27. mini = j;28. 29. 30. / 若在当前系统时间之前到达的进程均已经结束31. if ( -1 = mini )32. 33. / 等待下一个进程到达后重新进行调度34. time = processi.arrive;35. continue;36. 37. last = time;38. / 如果进程可以运行完39. if ( processmini.run = processmini.time )40. 41. / 进程调度42. printf(%d/%d/%d/%d/%dn, k +, processmini.id, time, time + processmini.run, processmini.priority + 3);43. / 将进程运行完44. m +;45. time += processmini.run;46. processmini.done = true;47. 48. / 如果进程不能运行完49. else50. 51. / 进程调度52. printf(%d/%d/%d/%d/%dn, k +, processmini.id, time, time + processmini.time, processmini.priority + 3);53. / 将进程运行一个时间片54. time += processmini.time;55. processmini.run -= processmini.time;56. 57. / 调整进程优先级58. for ( int j = 0; j 0)?(processj.priority -1):0;72. 73. 74. 75. 76. return ;77. 6. 程序完整代码及注释#include #include #include #include #include using std:sort;using std:queue;const int N = 100; / 定义PCB数组大小int n; / 保存进程的总个数struct pcb / PCB （进程控制块） int id; / 进程号pid int arrive; / 进程到达时间 int run; / 进程运行时间 int priority; / 进程优先级 int time; / 进程运行的时间片 bool done; / 记录进程是否已经完成运行 processN; / PCB数组/ 按到达时间、pid排序bool cmp_ar_id(pcb a, pcb b) if (a.arrive = b.arrive) return a.id b.id; else return a.arrive b.arrive; / 按运行时间、pid排序bool cmp_run_id(pcb a, pcb b) if (a.run = b.run) return a.id b.id; else return a.run b.run; / 按到达时间、运行时间、pid排序bool cmp_run(pcb a, pcb b) if (a.arrive = b.arrive) if (a.run = b.run) return a.id b.id; else return a.run b.run; else return a.arrive b.arrive; / 先来先服务void fcfs() / 按到达时间、pid排序 sort(process, process+n, cmp_ar_id); / 初始化系统时间 int time = 0; / 顺序遍历各进程 for ( int i = 0; i n; i + ) / 若当前系统时间时没有待调度进程 if ( time processi.arrive ) / 等待系统时间到达下一个进程到来 time = processi.arrive; / 否则 / 进行进程调度 printf(%d/%d/%d/%d/%dn, i+1, processi.id, time, time + processi.run, processi.priority); / 进程运行，系统时间流逝 time += processi.run; return ;/ 短作业优先void sjf() / 按运行时间、pid排序 sort(process, process+n, cmp_run_id); / 初始化系统时间 int time = 0; / 有未运行进程 for ( int m = 1; m = n; ) / 找出已到达的未运行进程中，运行时间最短的进程 int min = INT_MAX, mini = -1; for ( int i = 0; i n; i + ) if ( processi.arrive = time & / 已到达的进程 processi.run min & / 运行时间最短的进程 ! processi.done ) / 未运行的进程 min = processi.run; mini = i; / 若当前系统时间时没有待调度进程 if ( -1 = mini ) / 找出下一个到达的时间 int mint = INT_MAX; for ( int i = 0; i n; i + ) if ( processi.arrive mint & / 最近的到达时间 ! processi.done ) / 未运行的进程 mint = processi.arrive; / 等待系统时间到达下一个进程到来 time = mint; continue; / 否则 / 进行进程调度 printf(%d/%d/%d/%d/%dn, m, processmini.id, time, time + processmini.run, processmini.priority); / 进程运行，系统时间流逝 time += processmini.run; processmini.done = true; / 已运行进程数+1 m +; / 最短剩余时间优先void sltf() /* 调度器配置阶段 */ / 按到达时间、运行时间、pid排序 sort(process, process+n, cmp_run); / 初始化系统时间 int time = process0.arrive; / 正在运行的进程置空，进程开始运行时间置为系统当前时间 int execi = -1, start = time; int k = 0, m = 0; / 有未运行进程 for ( int i = 0; m n; ) /* 预调度阶段 */ / 找到在当前系统时间已经到达的进程 for ( ; processi.arrive = time & i n; i + ); / 在已到达进程中查找剩余运行时间最短的未结束进程 int min = INT_MAX, mini = -1; for ( int j = 0; j i; j + ) if ( processj.run min & ! processj.done ) min = processj.run; mini = j; / 若在当前系统时间之前到达的进程均已经结束 if ( -1 = mini ) / 等待下一个进程到达后重新进行调度 time = processi.arrive; continue; / 若当前没有正在运行的进程 if ( -1 = execi ) / 则执行找到的进程 execi = mini; / 进程的开始运行时间设为现在的时间 start = std:max(processexeci.arrive, time); /* 进程调度阶段 */ / 若找到的进程剩余运行时间小于当前正在运行进程的剩余运行时间 if ( processmini.run = processexeci.run | runnable = 0 ) time += processexeci.run; printf(%d/%d/%d/%d/%dn, + k, processexeci.id, start, time, processexeci.priority); processexeci.run = 0; processexeci.done = true; m +; execi = -1; start = time; / 若进程不能完成运行则运行一个时间片 else time += runnable; processexeci.run -= runnable; return ;/ 时间片轮转void tpt() / 初始化进程队列 queue qu; processn.arrive = INT_MAX; / 按到达时间、pid排序 sort(process, process+n, cmp_ar_id); / 初始化系统时间 int time = process0.arrive; / 所有进程是否均完成运行 for ( int i = 0, k = 1, m = 0; m n; ) / 如果队列为空 if ( qu.empty() ) / 等待新的进程到达 time = processi.arrive; / 将当前系统时间之前的进程放入队列 for ( ; processi.arrive = time & i temp.time ) / 进程调度 printf(%d/%d/%d/%d/%dn, k +, temp.id, time, time + temp.time, temp.priority); / 将进程运行一个时间片 time += temp.time; temp.run -= temp.time; / 将当前系统时间之前的进程放入队列 for ( ; processi.arrive = time & i n; i + ) qu.push(processi); / 将进程放回队列 qu.push(temp); / 如果进程可以完成运行 else / 进程调度 printf(%d/%d/%d/%d/%dn, k +, temp.id, time, time + temp.run, temp.priority); / 将进程运行完 time += temp.run; / 将当前系统时间之前的进程放入队列 for ( ; processi.arrive = time & i n; i + ) qu.push(processi); m +; return ;/ 动态优先级void dp() / 按到达时间、pid排序 s