实验三操作系统进程调度算法一、实验目的和要求：目的：对操作系统中使用的进程调度算法进行改进性设计。
要求：对教材中所讲述的几种进程调度算法进行深入的分析，然后选取其中的一种算法进行改进，并编程实现此算法。
二、实验内容：1、设计进程控制块PCB表结构，分别适用于优先数调度算法和先来先服务调度算法。
2、建立进程就绪队列。
对两种不同算法编制入链子程序。
3、编制两种进程调度算法：1）优先数调度；2）先来先服务三、实验原理：先来先服务调度算法：按进程进入就绪队列的先后次序选择可以占用处理器的进程。
优先级调度算法：对每个进程确定一个优先数，该算法总是让优先数最高的进程先使用处理器。
对具有相同优先数的进程，再采用先来先服务的次序分配处理器。
系统常以任务的紧迫性和系统效率等因素确定进程的优先数。
进程的优先数可以固定的，也可随进程执行过程动态变化。
一个高优先数的进程占用处理器后，系统处理该进程时有两种方法，一是"非抢占式"，另一种是"可抢占式"。
前者是此进程占用处理器后一直运行到结束，除非本身主动让出处理器，后者则是严格保证任何时刻总是让优先数最高的进程在处理器上运行（本实验采用“可抢占式”）。
四、实验提示：1、用两种算法对多个进程进行调度，每个进程可有三个状态，并假设初始状态为就绪状态。
2、为了便于处理，程序中的某进程运行时间以时间片为单位计算。
各进程的优先数及进程需运行的时间片数的初始值均由用户给定。
3、在优先数算法中，优先数可以先取值为n，进程每执行一次，优先数减3，进程还需要的cpu时间片数减1。
在先来先服务算法中，采用固定时间片（即：每执行一次进程，该进程的执行时间片数为已执行了2个单位），这时进程还需要的时间片数减2，并排列到就绪队列的尾上。
4、对于遇到优先数一致的情况，采用FIFO策略解决。
5、流程图五、实验结论FCFS算法：void FCFS(){intstartWorkTime = 0;int first = get_firstProcess();isFinished_FCFS[first] = true;FinishTime[first] = ArrivalTime[first] + ServiceTime[first];startWorkTime += ServiceTime[first];WholeTime[first] = FinishTime[first] - ArrivalTime[first];WeightWholeTime[first] = WholeTime[first]/ServiceTime[first];intnextProcess = n;for (inti=1;i<n;i++){nextProcess = n;for (int j=0;j<n;j++){if (!isFinished_FCFS[j]){if (ArrivalTime[j]<=startWorkTime){if (nextProcess==n){nextProcess = j;}else{if (ArrivalTime[nextProcess]>ArrivalTime[j]){nextProcess=j;}}}}}isFinished_FCFS[nextProcess] = true;FinishTime[nextProcess] = ServiceTime[nextProcess] + startWorkTime;startWorkTime += ServiceTime[nextProcess];WholeTime[nextProcess] = FinishTime[nextProcess] - ArrivalTime[nextProcess];WeightWholeTime[nextProcess] =(double)WholeTime[nextProcess]/ServiceTime[nextProcess];}doubletotalWT = 0;doubletotalWWT = 0;for (inti=0;i<n;i++){totalWT+=WholeTime[i];totalWWT+=WeightWholeTime[i];}AverageWT_FCFS = totalWT/n;AverageWWT_FCFS = totalWWT/n;display();cout<<"平均周转时间="<<AverageWT_FCFS<<endl;cout<<"平均带权周转时间="<<AverageWWT_FCFS<<endl;cout<<"******************************************************"<<endl; }SJF算法：void SJF(){intstartWorkTime_SJF = 0;int first = get_firstProcess();isFinished_SJF[first] = true;FinishTime[first] = ArrivalTime[first] + ServiceTime[first];startWorkTime_SJF += ServiceTime[first];WholeTime[first] = FinishTime[first] - ArrivalTime[first];WeightWholeTime[first] = (double)WholeTime[first]/ServiceTime[first];intnextProcess_SJF = n;for (inti=1;i<n;i++){nextProcess_SJF = n;for (int j=0;j<n;j++){if (!isFinished_SJF[j]){if (ArrivalTime[j]<=startWorkTime_SJF){if (nextProcess_SJF==n){nextProcess_SJF = j;}else{if (ServiceTime[nextProcess_SJF]>ServiceTime[j]){nextProcess_SJF = j;}}}}}//for(j)isFinished_SJF[nextProcess_SJF] = true;FinishTime[nextProcess_SJF] = ServiceTime[nextProcess_SJF] + startWorkTime_SJF;startWorkTime_SJF += ServiceTime[nextProcess_SJF];WholeTime[nextProcess_SJF] = FinishTime[nextProcess_SJF] - ArrivalTime[nextProcess_SJF];WeightWholeTime[nextProcess_SJF] = (double)WholeTime[nextProcess_SJF]/ServiceTime[nextProcess_SJF];}//for(i)doubletotalWT = 0;doubletotalWWT = 0;for (inti=0;i<n;i++){totalWT+=WholeTime[i];totalWWT+=WeightWholeTime[i];}AverageWT_SJF = totalWT/n;AverageWWT_SJF = totalWWT/n;display();cout<<"平均周转时间="<<AverageWT_SJF<<endl;cout<<"平均带权周转时间="<<AverageWWT_SJF<<endl;cout<<"******************************************************"<<endl;}六、实验过程中所遇问题思考与讨论通过此次实验模拟了FCFS和FJS算法先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。
当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。
在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。
该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。
SJF调度算法也存在不容忽视的缺点：该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。
更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。
该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。
由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。
通过此次实验，获益匪浅。