操作系统进程调度编程

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

分析

定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析

(1). 采用的测试方法 l 对于本实验中的程序主要采用的测试方法是白盒测试 l 对于提交后有无法通过的测试用例时采用了其他已经通过同学的测试用例进行了黑盒测试 l 对于测试用例中未明确指出的情况对测试数据进行了暴力猜解 (2). 对测试结果以及错误的分析 l 白盒测试主要用于

检测

工程第三方检测合同工程防雷检测合同植筋拉拔检测方案传感器技术课后答案检测机构通用要求培训

程序的边界数据的执行情况，目的是要走过程序中的全部路径。主要的测试点有以下几个方面：  l 变量和数组的初始化的情况 l 第一个进程的到达时间不为0的情况 l 两个进程的到达时间差过大导致CPU空闲的情况 l 在当前状态下是需要调度，还是原进程继续执行 l 当前进程剩余执行时间大于、等于和小于时间片时间长度的三种情况 l 进程的到达时间先于、等于和后于当前系统时间的情况 l 排序的结果是否正确 l 使用的数据结构是否会越界 l 循环控制变量（一般是已经完成运行的进程的个数）是否被正常累加 l PCB中的标记是否正常工作 l 没有待调度进程的情况 l 黑盒测试主要使用了一下几个测试用例 1. 3 2. 1/1/5/1/1 3. 2/2/4/1/1 4. 3/99/1/1/1 1. 4 2. 1/0/13/1/20 3. 2/100/17/1/20 4. 3/0/18/1/20 5. 4/0/14/1/20 6. 3/0/18/1/20 1. 3 2. 1/60/10/1/20 3. 2/50/49/1/20 4. 3/0/100/1/20 1. 3 2. 1/70/10/1/20 3. 2/50/70/1/20 4. 3/0/100/1/20 1. 3 2. 1/40/20/1/20 3. 2/10/60/1/20 4. 3/80/10/1/20 5. 4/0/50/1/20 1. 3 2. 1/0/100/1/20 3. 2/35/35/1/20 4. 3/35/10/1/20 5. 4/50/25/1/20 1. 3 2. 1/0/100/1/20 3. 2/95/10/1/20 4. 3/97/10/1/20 1. 5 2. 1/1/3/1/2 3. 2/0/4/1/2 4. 3/0/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/0/3/1/2 3. 2/1/4/1/2 4. 3/0/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/0/3/1/2 3. 2/0/4/1/2 4. 3/1/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/1/3/1/2 3. 2/1/4/1/2 4. 3/0/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/1/3/1/2 3. 2/0/4/1/2 4. 3/1/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/0/3/1/2 3. 2/1/4/1/2 4. 3/1/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 1. 5 2. 1/1/3/1/2 3. 2/1/4/1/2 4. 3/1/2/3/2 5. 4/2/1/1/2 6. 5/2/4/4/2 l 另外，对于对于测试用例中未明确指出的情况对测试数据进行了暴力猜解。主要的测试点有：  l 测试用例6 ~ 10分别对应哪种调度方法 l 是否存在pid和到达时间的对应关系 l 对于完全等价的情况的输出顺序 8. 本次实验经验及体会 在本次试验中，通过编写一个模拟的调度程序，加深对了对进程控制块概念和各种进程调算法的理解。通过对于算法的逻辑理论的理解结合本实验的测试数据，重新设计了基于本题目的调度算法，成功地完成了本次实验。由于测试数据的原因，导致整个调度算法的设计并不能按照实际情况，给出一种合理的解即可，而是必须给出输出数据要求的调度顺序，因此在完成进程的调度工作之外，还做了一些的额外的工作来保证输出的结果符合测试数据。 由于测试数据所限，无法按照真实的情况编写一个真正的调度程序，但我在本次试验中尽量保证了调度算法的原貌，同时也给出了基于各个算法原貌的粗略设计。为了最大程度上保持算法的原貌，在实现时只是在基于输入数据已经完全给出了的基础上进行了一些调整，对于某些实际需要消耗时间的步骤进行了适当的抽象和省略。 总体来说，本实验的实验目标已经达成，已经了解了各个调度算法的实现方法以及实现过程中的注意事项。