操作系统概念作业五.docVIP

操作系统第五次作业 5.1为什么对调度程序而言，区分CPU约束程序和I/O约束程序很重要？ 答：CPU的成功调度依赖于进程的如下属性：进程执行由CPU执行和I/O等待周期组成，进程在这两个状态之间切换。进程执行从CPU区间开始，在这之后是I/O区间，接着是另一个CPU区间，如此进行下去；最终，最后的CPU区间通过系统请求终止执行。这些CPU区间的长度呈现出指数或超指数形式的频率曲线，具有大量短CPU区间和少量长CPU区间。I/O约束程序通常具有很多短CPU区间。CPU约束程序可能有少量的长CPU区间。所以区分出CPU约束程序和I/O约束程序能够使调度程序更好的执行和选择合适的CPU调度算法。 5.4 a.画出4个Gantt图分别演示用FCFS、SJF、非抢占优先级（数字小代表优先级高）和RR（时间片＝1）算法调度时进程的执行过程。 FCFS P1 P2 P3 P4 P5 0 10 11 13 14 19 SJF P2 P4 P3 P4 P5 0 1 2 4 9 19 非抢占优先级 P2 P5 P1 P3 P4 0 1 6 16 17 19 RR P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P1 19 b.周转时间 FCFS RR SJF 非抢占优先级 P1 10 19 19 16 P2 11 2 1 1 P3 13 7 4 18 P4 14 4 2 19 P5 19 14 9 6 c.等待时间 FCFS RR SJF 非抢占优先级 P1 0 9 9 6 P2 10 1 0 0 P3 11 5 2 16 P4 13 3 1 18 P5 14 9 4 2 d.平均等待时间 FCFS RR SJF 非抢占优先级 T 19.6 5.4 3.2 6.6 由表格可知，SJF算法的平均的等待时间最小。 5.5下面哪种调度算法能导致饥饿？ a.先到先服务（FCFS）： FCFS调度算法是一种最简单的调度算法，该调度算法既可以用于作业调度也可以用于进程调度。在作业调度中，算法每次从后备作业队列中选择最先进入该队列的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。 在进程调度中，FCFS调度算法每次从就绪队列中选择最先进入该队列的进程，将处理机分配给它，使之投入运行，直到完成或因某种原因而阻塞时才释放处理机。 FCFS调度算法属于不可剥夺算法。从表面上看，它对所有作业都是公平的，但若一个长作业先到达系统，就会使后面许多短作业等待很长时间，因此它不能作为分时系统和实时系统的主要调度策略。但它常被结合在其他调度策略中使用。例如，在使用优先级作为调度策略的系统中，往往对多个具有相同优先级的进程按FCFS原则处理。 FCFS调度算法的特点是算法简单，但效率低；对长作业比较有利，但对短作业不利（相对SJF和高响应比）；有利于CPU繁忙型作业，而不利于I/O繁忙型作业。 所以先来先服务算法不会引起饥饿现象。 b.最短作业优先（SJF）： 短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。短作业优先(SJF)调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法，则是从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它，使之立即执行，直到完成或发生某事件而阻塞时，才释放处理机。 SJF调度算法也存在不容忽视的缺点： 该算法对长作业不利， SJF调度算法中长作业的周转时间会增加。更严重的是，如果有一长作业进入系统的后备队列，由于调度程序总是优先调度那些 (即使是后进来的）短作业，将导致长作业长期不被调度。该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业会被及时处理。由于作业的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。 由此可见，SJF算法会导致长作业一直在等待的情况，会导致饥饿现象。 c.轮转法（RR）： 时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中第一个进程执行，即先来先服务的原则，但仅能运行一个时间片，如100ms。在使用完一个时间片后，即使进程并未完成其运行，它也必须释放出（被剥夺）处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队