《OS课设之CPU调度算法的模拟实现》由会员分享,可在线阅读,更多相关《OS课设之CPU调度算法的模拟实现(27页珍藏版)》请在金锄头文库上搜索。
1、CPU 调度算法的模拟实现一、设计目的 利用 C+编写 CPU 调度算法,实现先来先服务调度算法 FCFS、优先级调度算法 PS、短作业优先调度算法 SJF、时间片轮转调度算法 RR 的运行过程和实现的结果,针对模拟进程,利用编写的 CPU 调度算法对需要运行的进程进行调度。进行算法评价,计算平均周转时间和平均等待时间。 二、设计要求 针对模拟进程,利用 CPU 调度算法进行调度,最后要进行算法评价,计算平均周转时间和平均等待时间,并且输出调度结果和输出算法评价指标。 调度所需的进程参数由输入产生(手工输入或者随机数产生)。三、设计说明 CPU 调度决策可在如下 4 种情况环境下发生: (1)
2、当一个进程从运行切换到等待状态(如:I/O 请求,或者调用 wait 等待一个子进程的终止) (2)当一个进程从运行状态切换到就绪状态(如:出现中断) (3)当一个进程从等待状态切换到就绪状态(如:I/O 完成) (4)当一个进程终止时对于第 1 和 4 两种情况,没有选择而只有调度。一个新进程(如果就绪队列中已有一个进程存在)必须被选择执行。对于第和第两种情况,可以进行选择。当调度只能发生在第 1 和 4 两种情况下时,称调度是非抢占的(nonpreemptive)或协作的(cooperative);否则,称调度方案为抢占的(preemptive)。采用非抢占调度,一旦 CPU 分配给一个进
3、程,那么该进程会一直使用 CPU 直到进程终止或切换到等待状态。抢占调度对访问共享数据是有代价(如加锁)的,有可能产生错误,需要新的机制(如,同步)来协调对共享数据的访问。抢占对于操作系统内核的设计也有影响。在处理系统调用时,内核可能忙于进程活动。这些活动可能涉及要改变重要内核数据(如 I/O 队列) 。因为根据定义中断能随时发生,而且不能总是被内核所忽视,所以受中断影响的代码段必须加以保护以避免同时访问。操作系统需要在任何时候都能够接收中断,否则输入会丢失或输出会被改写。为了这些代码段不被多个进程同时访问,在进入时就要禁止中断,而在退出时要重新允许中断。调度准则为了比较 CPU 调度算法所提
4、出的准则:CPU 使用率 : 需要使 CPU 尽可能忙吞吐量 : 指一个时间单元内所完成进程的数量周转时间 :从进程提交到进程完成的时间段称为周转时间,周转时间是所有时间段之和,包括等待进入内存、在就绪队列中等待、在 CPU 上执行和 I/O 执行平均周转时间 :即周转时间的算数平均值等待时间 : 在就绪队列中等待所花费时间之和平均等待时间 : 即等待时间的算数平均值响应时间 : 从提交请求到产生第一响应的时间。需要使 CPU 使用率和吞吐量最大化,而使周转时间、等待时间和响应时间最小化。绝大多数情况下需要优化平均值,有时需要优化最大值或最小值,而不是平均值四、详细设计4.1 先到先服务调度(
5、First-Come,First-Served scheduling)最简单的 CPU 调度算法是先到先服务算法(First-Come,First-Served scheduling):先请求 CPU 的进程先分配到 CPU。FCFS 策略可以用 FIFO 队列来容易实现。当一个进程进入就绪队列,其 PCB 链接到队列的尾部。当 CPU 空闲时,CPU 分配给位于队列头的进程,接着运行进程从队列中删除。FCFS 策略的代码编写简单且容易理解,不过采用 FCFS 策略的平均等待时间通常比较长。当进程 CPU 区间时间变化很大,平均等待时间会变化很大。算法原理:假设有 n 个进程分别在 T1, ,
6、Tn 时刻到达系统,它们需要的服务时间分别为 S1, ,Sn。分别采用先来先服务 FCFS 调度算法进行调度,计算每个进程的完成时间,周转时间和带权周转时间,并且统计 n 个进程的平均周转时间和平均带权周转时间。 程序要求如下: 1)进程个数 n;每个进程的到达时间 T1, ,Tn 和服务时间 S1, ,Sn。2)要求采用先来先服务 FCFS 调度进程运行,计算每个进程的周转时间,带权周转时间,并且计算所有进程的平均周转时间,带权平均周转时间; 3)输出:要求模拟整个调度过程,输出每个时刻的进程运行状态,如“时刻 3:进程 B 开始运行” 等等; 4)输出:要求输出计算出来的每个进程的周转时间
7、,带权周转时间,所有进程的平均周转时间,带权平均周转时间。实现简要过程:1)变量初始化; 2)接收用户输入 n,T1, ,Tn,S1, ,Sn; 3)按照选择算法进行进程调度,计算进程的完成时间、周转时 间和带权周转时间; 4)按格式输出调度结果。测试结果:案例分析:进程 区间时间P1 24P2 3P3 3如果按照 P1P2P3 顺序到达,Gantt 图如下: 0 24 27 30平均等待时间:(0+24+27)3=17平均周转时间:(24+27+30 )3=27如果按照 P2P3P1 顺序到达,平均等待时间:(0+3+6)3=3平均周转时间:(3+6+30)3=13另外考虑在动态情况下的性能
8、,假设有一个 CPU 约束进程和许多 I/O 约束进程,CPU 约束进程会移回到就绪队列并被分配到 CPU。再次所有 I/O 进程会在就绪队列中等待 CPU 进程的完成。由于所有其他进程都等待一个大进程释放 CPU,这称之为护航效果(convoy effect)。与让较短进程最先执行相比,这样会导致 CPU 和设备使用率变的很低。FCFS 调度算法是非抢占的。对于分时系统(每个用户需要定时的等待一定的 CPU 时间)是特别麻烦。允许一个进程保持 CPU 时间过长是个严重错误。4.2 优先级调度(priority scheduling algorithm)算法:每个进程有一个进程控制块( PCB
9、)表示。进程控制块可以包含如下信息:进程名、优先数、到达时间、需要运行时间、已用 CPU 时间、进程状态等等。 进程的优先数及需要的运行时间可以事先人为地指定(也可以由随机数产生)。进程的到达时间为进程输入的时间。进程的运行时间以时间片为单位进行计算。每个进程的状态可以是就绪 W( Wait)、运行 R(Run )、或完成 F(Finish)三种状态之一。就绪进程获得 P1 P2 P3CPU 后都只能运行一个时间片。用已占用 CPU 时间加 1 来表示。如果运行一个时间片后,进程的已占用 CPU 时间已达到所需要的运行时间,则撤消该进程,如果运行一个时间片后进程的已占用 CPU 时间还未达所需
10、要的运行时间,也就是进程还需要继续运行,此时应将进程的优先数减 1(即降低一级),然后把它插入就绪队列等待 CPU。每进行一次调度程序都打印一次运行进程、就绪队列、以及各个进程的 PCB,以便进行检查。 重复以上过程,直到所要进程都完成为止。SJF 算法可作为通用的优先级调度算法的一个特例。每个进程都有一个优先级与其关联,具有最高优先级的进程会分配到 CPU。具有相同优先级的进程按FCFS 顺序调度。 SJF,其优先级(p )为下一个 CPU 区间的倒数。CPU 区间越大,则优先级越小,反之亦然。优先级通常是固定区间的数字,如,但是数字大小与优先级的高低没有定论。测试结果:案例分析:(假设数字
11、越小优先级越高)进程 区间时间 优先级P1 10 3P2 1 1P3 2 4P4 1 5P5 5 2画出 Gantt 图:P2 P 5 P 1 P 3 P4 0 1 6 16 1819 平均等待时间:(0+1+6+16+18 )5=8.2平均周转时间:(1+6+16+18+19)5=12优先级可通过内部或外部方式来定义。内部定义优先级使用一些测量数据以计算进程优先级。外部优先级是通过操作系统之外的准则来定义,如进程重要性等。优先级调度可以是抢占的或非抢占的。优先级调度算法的一个重要问题是无限阻塞(indefinite blocking)或饥饿(starvation)。可以运行但缺乏 CPU 的
12、进程可认为是阻塞的,它在等待CPU。优先级调度算法会使某个有低优先级无穷等待 CPU。低优先级进程务求等待问题的解决之一是老化(aging)。老化是一种技术,以逐渐增加在系统中等待很长时间的进程的优先级。4.3 时间片轮转调度算法(round-robin,RR)专门为分时系统设计。它类似于 FCFS 调度,但是增加了抢占以切换进程。定义一个较小的时间单元,称为时间片(time quantum,or time slice)。将就绪队列作为循环队列。CPU 调度程序循环就绪队列,为每个进程分配不超过一个时间片段的 CPU。系统将所有的就绪进程按先来先服务的原则排成一个队列,每次调度时,把 CPU
13、分配给队首进程,并令其执行一个时间片。时间片的大小从几 ms 到几百 ms。当执行的时间片用完时,由一个计时器发出时钟中断请求,调度程序便据此信号来停止该进程的执行,并将它送往就绪队列的末尾;然后,再把处理机分配给就绪队列中新的队首进程,同时也让它执行一个时间片。如果在时间片结束时进程还在运行,则 CPU 将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束,则 CPU 当即进行切换。调度程序所要做的就是维护一张就绪进程列表,当进程用完它的时间片后,它被移到队列的末尾。RR 策略的平均等待时间通常较长测试结果:案例分析:(使用 4ms 时间片)进程 区间时间P1 24P2 3P3 3画
14、出 Gantt 图:P1 P2 P3 P1 P1 P1 P1 P10 4 7 10 14 18 22 26 30 平均等待时间:0+4+7+ ( 10-4) 3=5.66平均周转时间:(7+10+30)3=15.67 如果就绪,那么每个进程会得到 1n 的 CPU 时间,其长度不超过 q 时间单元。每个进程必须等待 CPU 时间不会超过(n1) q 个时间单元,直到它的下一个时间片为止。RR 算法的性能很大程度上依赖于时间片的大小。在极端情况下,如果时间片非常大,那么 RR 算法与 FCFS 算法一样。如果时间片很小,那么 RR 算法称为处理器共享,n 个进程对于用户都有它自己的处理器,速度为
15、真正处理器速度的 1/n。小的时间片会增加上下文切换的次数,因此,希望时间片比上下文切换时间长,事实上,绝大多数现代操作系统,上下文切换的时间仅占时间片的一小部分。周转时间也依赖于时间片的大小。4.4 最短作业优先调度(shortest-job-first scheduling,SJF)将每个进程与下一个 CPU 区间段相关联。当 CPU 为空闲时,它会赋给具有最短 CPU 区间的进程。如果两个进程具有同样长度,那么可以使用 FCFS 调度来处理。注意,一个更为适当地表示是最短下一个 CPU 区间的算法,这是因为调度检查进程的下一个 CPU 区间的长度,而不是其总长度。 这种策略是下一次选择所需处理时间最短的进程。是非抢占策略,目的也是为减少 FCFS 策略对长进程的偏向。测试结果: 案例分析:进程 区间时间P1