操作系统课程设计报告题目处理机调度院、系计算机与控制工程学院专业计算机科学与技术班级计185 姓名张炜昊学号 201858505123 指导教师翟一鸣 2020 年 7 月 1 日目录 1 项目描述 1 2 系统结构分析 1 3 系统详细设计 1 4 系统主要算法 1 5 系统程序实现 1 6 程序实现结果 2 7 课程设计总结 2 附录：源程序 2 1 项目描述现代操作系统以进程并发、资源共享和随机访问为三个显著的特征。因而，常常有竞争处理机使用权的问题。为了使系统中各进程能有条不紊地工作，必须选择某些调度策略经过几级调度选择一个进程来使用处理机，并且，还要千方百计地提高处理机的使用效率。 2 系统结构分析处理及调度程序：选择一个合适的调度算法，实现处理机调度进程。调度算法包括：时间片轮转算法，短进程优先算法，高相应比优先算法，可抢占优先级算法 3 系统详细设计设计一个有多个进程共行的进程调度程序。进程调度算法：先来先服务算法、短进程优先算法、时间片轮转算法、可抢占式优先级算法、不可抢占式优先级算法以及高响应必优先调度算法，并采用菜单进行算法的选择。每个进程都有一个进程控制块（PCB）表示。进程控制块包含以下信息：进程名，优先数，到达时间，服务时间，进程状态等等。 1.界面菜单选项一级菜单提供两个选项 1.自动生成进程数量 2.手动输入所需进程数量一级菜单选择完毕后进入二级菜单 1.重新生成进程 2.时间片轮转法 3.短进程优先法 4.动态优先级法 5.退出程序 6. 4 系统主要算法 1)时间片轮转法，主要是设置一个当前的时间变量curTime和时间片roundTime。遍历进程组的时候，每运行一个进程，就把curTime+=roundTime。进程已运行时间加roundTime 2)短进程优先算法，短进程优先算法是对FCFS算法的改进，其目标是减少平均周转时间。该算法对预计执行时间短的进程（进程）优先分派处理机。通常后来的短进程不抢先正在执行的进程。遍历进程组，找到未运行并运行时间最短的进程，让它一次运行完成，如此往复，直到所有进程都完成。 3)动态优先级算法，遍历进程组，找到优先级高者先执行，直到所有进程都完成。每当一个进程完成后，适当增减剩余进程的优先级，已完成动态优先级 5 系统程序实现 PCB的设置 typedef struct PCB{ char name; //进程名 int priority; //优先数 int runningTime; //运行时间 int arriveTime; //到达时间 int beginTime; //开始时间 int finishTime; //完成时间 int cyclingTime; //周转时间 double weigthCyclingTime; //带权周转时间 int hadRunTime; //已经运行时间 int finish; //是否完成 }PCB; 获取随机数实现数据输入 //获取随机数 int GetRandomNumber(){ int xt; time_t t; srand((unsigned) time(&t)); xt = rand() % 19+2; return xt; } 进程数量的选择 // 选择进程数量 while (1) { if (processNum != 0) break; printf ("\n------------------------------------------------------------------------\n" ); printf (" 当前默认进程数范围%d--%d\n" ,MIN_PROCESS ,MAX_PROCESS ); printf ("1) 输入%d-%d范围内数字，回车，可生成指定数目进程\n>>>>>>" ,MIN_PROCESS,MAX_PROCESS ); int num = 0; scanf("%d" ,&num); if ((num >= MIN_PROCESS) && (num <= MAX_PROCESS )) { processNum = num; InitPCBGroup (pcbGroup,processNum); break; } else printf ("\n输入有误，请重新输入.\n"); } 算法的选择 // 选择算法 printf ("\n----------------------------- 请输入对应选项序号-----------------------------\n" ); printf ("0.重新生成进程| 1.时间片轮转法| 2.短进程优先算法| 3.动态优先级算法| q.退出\n>>>>>>" ); char ch; while ((ch = getchar()) == '\n'); switch (ch) { case'0'://0 重新生成进程 processNum = 0;break; case'1'://1 时间片轮转法 RoundRobin(pcbGroup, processNum);break; case'2'://2 短进程优先算法 ShortestJobFirst(pcbGroup, processNum);break; case'3'://3 动态优先级算法 DynamicPriorityFirst (pcbGroup,processNum);break; case'q'://q 退出 exit(0); default: break; } } return 0; } 将PCB清零，实现PCB的数据存入与输出。 //初始化PCB组 void InitPCBGroup( PCB p[], int num){ char name = 'A'; int i; for ( i = 0;i < num;i++){ p[i]. name = name; p[i]. priority = GetRandomNumber(); p[i]. runningTime =GetRandomNumber(); name++; } } void PrintResult( PCB p[], int num){ double avgCycTime = 0,avgWeiCycTime = 0; printf ("|进程名到达时间运行时间开始时间完成时间周转时间带权周转时间优先数|\n"); int i;for ( i = 0;i < num;i++){ printf ("|%3c %4d %4d %4d %4d %4d %6.2f %4d|\n",p[i]. name,p[i]. arriveTime,p[i]. runningTime ,p[i]. beginTime,p[i]. finishTime ,p[i]. cyclingTime ,p[i]. weigthCyclingTime ,p[i]. priority ); avgCycTime += p[i]. cyclingTime ; avgWeiCycTime += p[i]. weigthCyclingTime ; // 还原 p[i]. arriveTime = 0; p[i]. beginTime = 0; p[i]. finishTime = 0; p[i]. cyclingTime = 0; p[i]. weigthCyclingTime = 0; p[i]. hadRunTime = 0; p[i]. finish = 0; } avgWeiCycTime /= num; avgCycTime /= num; printf (" 平均周转时间： %.2f 平均带权周转时间:%.2f\n" ,avgCycTime,avgWeiCycTime); } 时间片轮转算法的程序实现 //时间片轮转法 void RealRoundRobin(PCB p[], int num,int roundTime){ printf ("\n\n----------------------------- 时间片： %d-------------------------------------\n" ,roundTime); int finishNum = 0; int curTime = 0; while (finishNum != num) { int i; for ( i = 0;i < num;i++) { if (p[i]. finish)continue; //开始时间 if (p[i]. beginTime == 0 && i != 0){ p[i]. beginTime = curTime; } //已经完成 if (p[i]. hadRunTime + roundTime >= p[i]. runningTime ){ p[i]. finishTime = curTime + p[i]. runningTime - p[i]. hadRunTime; p[i]. cyclingTime = p[i]. finishTime - p[i]. arriveTime ; p[i]. weigthCyclingTime = p[i]. cyclingTime /(double)p[i]. runningTime ; p[i]. finish = 1; finishNum ++; curTime += p[i]. runningTime - p[i]. hadRunTime; } else{ p[i]. hadRunTime += roundTime; curTime += roundTime; } } } PrintResult(p, num); } void RoundRobin(PCB p[], int num){ RealRoundRobin (p, num, 1); //时间片为1的结果 RealRoundRobin (p, num, 4); //时间片为4的结果 } //短进程优先算法 void ShortestJobFirst(PCB p[], int num){ printf ("\n\n----------------------------- 短进程优先算法---------------------------------\n" ); int finishNum = 0; int curTime = 0; while (finishNum != num) { int min = 0; // 查找短进程下标 int i;for ( i = 1;i < num;i++){ if (p[i]. finish == 0 && p[min]. runningTime >= p[i]. runningTime) min = i; else if (p[i]. finish == 0 && p[min]. finish == 1) min = i; } p[min]. beginTime = curTime; p[min]. hadRunTime = p[min]. runningTime; p[min]. finishTime = p[min]. beginTime + p[min]. runningTime; p[min]. cyclingTime = p[min]. finishTime - p[min]. arriveTime ; p[min]. weigthCyclingTime = p[min]. cyclingTime /( double)p[min]. runningTime ; p[min]. finish = 1; finishNum++; curTime = p[min]. finishTime ; } PrintResult(p, num); } //动态优先级算法 void DynamicPriorityFirst( PCB p[], int num){ printf ("\n\n----------------------------- 动态优先级算法---------------------------------\n" ); int finishNum = 0; int curTime = 0; while (finishNum != num) { int min = 0; // 查找优先级最高下标 int i;for ( i = 1;i < num;i++){ if (p[i]. finish == 0 && p[min]. priority >= p[i]. priority ) min = i; else if (p[i]. finish == 0 && p[min]. finish == 1) min = i; } p[min]. beginTime = curTime; p[min]. hadRunTime = p[min]. runningTime; p[min]. finishTime = p[min]. beginTime + p[min]. runningTime; p[min]. cyclingTime = p[min]. finishTime - p[min]. arriveTime ; p[min]. weigthCyclingTime = p[min]. cyclingTime /( double)p[min]. runningTime ; p[min]. finish = 1; finishNum++; curTime = p[min]. finishTime ; } PrintResult(p, num); } int main(int argc, const char * argv[]) { PCB pcbGroup[ 30]; //pcb数组 int processNum = 0; //进程数 while (1) { // 选择进程数量 while (1) { if (processNum != 0) break; printf ("\n------------------------------------------------------------------------\n" ); printf (" 当前默认进程数范围%d--%d\n" ,MIN_PROCESS ,MAX_PROCESS ); printf ("1) 输入0可随机生成进程数目\n2)输入%d-%d范围内数字，回车，可生成指定数目进程\n>>>>>>" ,MIN_PROCESS,MAX_PROCESS ); int num = 0; scanf("%d" ,&num); if (num == 0){ processNum = GetRandomNumber( ); break; } else{ if ((num >= MIN_PROCESS) && (num <= MAX_PROCESS )){ processNum = num; InitPCBGroup (pcbGroup,processNum); break; } else printf ("\n输入有误，请重新输入.\n"); } } 6 程序实现结果进入程序选择界面选择算法输入数据后的运行结果 7 课程设计总结附录：源程序 每个文件开头注释(示例) /*********************************************************** #include #include #include #include //最小进程数 #define MIN_PROCESS 2 //最大进程数 #define MAX_PROCESS 20 //最小优先数 #define MIN_PRIORITY 0 //最大优先数 #define MAX_PRIORITY 10 //最小运行时间 #define MIN_RUNNING_TIME 1 //最大运行时间 #define MAX_RUNNING_TIME 20 typedef struct PCB{ char name; //进程名 int priority; //优先数 int runningTime; //运行时间 int arriveTime; //到达时间 int beginTime; //开始时间 int finishTime; //完成时间 int cyclingTime; //周转时间 double weigthCyclingTime; //带权周转时间 int hadRunTime; //已经运行时间 int finish; //是否完成 }PCB; //获取随机数 int GetRandomNumber(){ int xt; time_t t; srand((unsigned) time(&t)); xt = rand() % 19+2; return xt; } //初始化PCB组 void InitPCBGroup( PCB p[], int num){ char name = 'A'; int i; for ( i = 0;i < num;i++){ p[i]. name = name; p[i]. priority = GetRandomNumber(); p[i]. runningTime =GetRandomNumber(); name++; } } void PrintResult( PCB p[], int num){ double avgCycTime = 0,avgWeiCycTime = 0; printf ("|进程名到达时间运行时间开始时间完成时间周转时间带权周转时间优先数|\n"); int i;for ( i = 0;i < num;i++){ printf ("|%3c %10d %10d %10d %10d %10d %6.2f %10d|\n",p[i]. name,p[i]. arriveTime,p[i]. runningTime ,p[i]. beginTime,p[i]. finishTime ,p[i]. cyclingTime ,p[i]. weigthCyclingTime ,p[i]. priority ); avgCycTime += p[i]. cyclingTime ; avgWeiCycTime += p[i]. weigthCyclingTime ; // 还原 p[i]. arriveTime = 0; p[i]. beginTime = 0; p[i]. finishTime = 0; p[i]. cyclingTime = 0; p[i]. weigthCyclingTime = 0; p[i]. hadRunTime = 0; p[i]. finish = 0; } avgWeiCycTime /= num; avgCycTime /= num; printf (" 平均周转时间： %.2f 平均带权周转时间:%.2f\n" ,avgCycTime,avgWeiCycTime); } //时间片轮转法 void RealRoundRobin(PCB p[], int num,int roundTime){ printf ("\n\n----------------------------- 时间片： %d-------------------------------------\n" ,roundTime); int finishNum = 0; int curTime = 0; while (finishNum != num) { int i;for ( i = 0;i < num;i++){ if (p[i]. finish)continue; //开始时间 if (p[i]. beginTime == 0 && i != 0){ p[i]. beginTime = curTime; } //已经完成 if (p[i]. hadRunTime + roundTime >= p[i]. runningTime ){ p[i]. finishTime = curTime + p[i]. runningTime - p[i]. hadRunTime; p[i]. cyclingTime = p[i]. finishTime - p[i]. arriveTime ; p[i]. weigthCyclingTime = p[i]. cyclingTime /(double)p[i]. runningTime ; p[i]. finish = 1; finishNum ++; curTime += p[i]. runningTime - p[i]. hadRunTime; } else{ p[i]. hadRunTime += roundTime; curTime += roundTime; } } } PrintResult(p, num); } void RoundRobin(PCB p[], int num){ RealRoundRobin (p, num, 1); //时间片为1的结果 RealRoundRobin (p, num, 4); //时间片为4的结果 } //短作业优先算法 void ShortestJobFirst(PCB p[], int num){ printf ("\n\n----------------------------- 短作业优先算法---------------------------------\n" ); int finishNum = 0; int curTime = 0; while (finishNum != num) { int min = 0; // 查找短作业下标 int i;for ( i = 1;i < num;i++){ if (p[i]. finish == 0 && p[min]. runningTime >= p[i]. runningTime) min = i; else if (p[i]. finish == 0 && p[min]. finish == 1) min = i; } p[min]. beginTime = curTime; p[min]. hadRunTime = p[min]. runningTime; p[min]. finishTime = p[min]. beginTime + p[min]. runningTime; p[min]. cyclingTime = p[min]. finishTime - p[min]. arriveTime ; p[min]. weigthCyclingTime = p[min]. cyclingTime /( double)p[min]. runningTime ; p[min]. finish = 1; finishNum++; curTime = p[min]. finishTime ; } PrintResult(p, num); } //动态优先级算法 void DynamicPriorityFirst( PCB p[], int num){ printf ("\n\n----------------------------- 动态优先级算法---------------------------------\n" ); int finishNum = 0; int curTime = 0; while (finishNum != num) { int min = 0; // 查找优先级最高下标 int i;for ( i = 1;i < num;i++){ if (p[i]. finish == 0 && p[min]. priority >= p[i]. priority ) min = i; else if (p[i]. finish == 0 && p[min]. finish == 1) min = i; } p[min]. beginTime = curTime; p[min]. hadRunTime = p[min]. runningTime; p[min]. finishTime = p[min]. beginTime + p[min]. runningTime; p[min]. cyclingTime = p[min]. finishTime - p[min]. arriveTime ; p[min]. weigthCyclingTime = p[min]. cyclingTime /( double)p[min]. runningTime ; p[min]. finish = 1; finishNum++; curTime = p[min]. finishTime ; } PrintResult(p, num); } int main(int argc, const char * argv[]) { PCB pcbGroup[ 30]; //pcb数组 int processNum = 0; //进程数 while (1) { // 选择进程数量 while (1) { if (processNum != 0) break; printf ("\n------------------------------------------------------------------------\n" ); printf (" 当前默认进程数范围%d--%d\n" ,MIN_PROCESS ,MAX_PROCESS ); printf ("1)输入%d-%d范围内数字，回车，可生成指定数目进程\n>>>>>>" ,MIN_PROCESS,MAX_PROCESS ); int num = 0; scanf("%d" ,&num); if ((num >= MIN_PROCESS) && (num <= MAX_PROCESS )){ processNum = num; InitPCBGroup (pcbGroup,processNum); break; } else printf ("\n输入有误，请重新输入.\n"); } // 选择算法 printf ("\n----------------------------- 请输入对应选项序号-----------------------------\n" ); printf ("0.重新生成进程| 1.时间片轮转法| 2.短作业优先算法| 3.动态优先级算法| q.退出\n>>>>>>" ); char ch; while ((ch = getchar()) == '\n'); switch (ch) { case'0'://0 重新生成进程 processNum = 0;break; case'1'://1 时间片轮转法 RoundRobin(pcbGroup, processNum);break; case'2'://2 短作业优先算法 ShortestJobFirst(pcbGroup, processNum);break; case'3'://3 动态优先级算法 DynamicPriorityFirst (pcbGroup,processNum);break; case'q'://q 退出 exit(0); default: break; } } return 0; }

“操作系统实验”实验报告