湖南大学操作系统作业(3) - 图文

操作系统第二次作业

第五章

5.1 Why is it important for the scheduler to distinguishI/O-bound programs from CPU-bound programs?

为何调度器要区分IO约束程序和CPU约束程序？

答：二者对CPU的使用有较大差别，IO操作只需少量的CPU时间片，大部分时间用于IO的等待，而CPU约束操作需要用整块时间，在CPU操作的后台可以同时运行IO等待操作，二者互不影响，通过区分两种操作，加上系统的调度，可以更好的利用CPU资源，提高运行效率

5.3 Consider the exponential average formula used to predict the length of the next CPU burst. What are the implications of assigning the following values to the parameters used by the algorithm? a. = 0 and 0 = 100milliseconds b. = 0.99 and 0 = 10milliseconds

考虑预测下一个CPU区间的指数平均公式，当下列参数分别取对应值时的影响是什么

答：指数平均公式：T(n+1)=at(n)+(1-a)Tn 参数Tn+1的含义是预测下一CPU区间的预测值，tn为第n个CPU区间的长度，a代表预测值和上一区间长度的【相关度】，也就是说，a取值越大，上一个区间（真实发生的）长度对预测值的影响就越大，反之，a取值越小，预测值就主要体现为上一次的预测值。 a=0，t=100ms a=0代表真实发生的区间长度不会影响预测，也就是说预测值会一直保持为上一次预测值，即t，故本次预测值为100ms a=0.99 t=10ms a=0.99代表预测值基本完全体现为上一次真实发生的CPU区间长度，也就是说预测值基本是前一个区间的长度，比如tn=50ms，则下一次预测值也大致为50ms。

5.4 Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

Process Burst Time Priority P1 10 3 P2 1 1 P3 2 3 P4 1 4 P5 5 2

The processes are assumed to have arrived in the order P1 , P2 ,P3 , P4 , P5 , all at time 0.

a. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority),

and RR (quantum= 1) scheduling.

b. What is the turnaround time of each process for each of the scheduling algorithms in part a?

c. What is the waiting time of each process for each of the scheduling algorithms in part a?

d. Which of the schedules in part a results in the minimal average waiting time (over all processes)? 考虑下列进程，给出CPU区间长度，单位ms，进程假设在0时刻以P1,P2,P3,P4,P5的顺序到达。

A 作出4个gantt图表，来阐述使用FCFS,SJF，非抢占的优先调度（小数字代表高优先）和RR调度（时间片为1ms）的执行过程 B 求A中各个调度算法下各个进程的周转时间 C 求A中各个调度算法下各个进程的等待时间 D 那种调度算法会有最小的平均等待时间？

列表如下： a．

FCFS: P1 P2 P3 P4 P5 0 10 11 13 14 19 SJF: P2 P4 P3 P5 P1 0 1 2 4 9 19 nonpreemptive priority: P2 P5 P1 P3 P4 0 1 6 16 18 19

RR: P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 b．每个进程的周转时间： FCFS SJF Priority RR P1 10 19 16 19 P2 11 1 1 2 P3 13 4 18 7 P4 14 2 19 4 P5 19 9 6 14 c．每个进程的等待时间： FCFS SJF Priority RR P1 0 9 6 9 P2 10 0 0 1 P3 11 2 16 5 P4 13 1 18 3 P5 14 4 1 9 d．平均等待时间： FCFS SJF Priority RR avgTwait 9.6 3.2 8.2 5.4 SJF的平均等待时间最短

5.5 Which of the following scheduling algorithms could result in starvation? a. First-come, first-served b. Shortest job first c. Round robin d. Priority

下面哪种调度算法会造成进程饥饿？

A 先来先服务 B 短作业优先 C 轮转法D优先级调度法 答：进程饥饿的原因是某种调度算法在分配时无法照顾到所有进程，造成某些进程在队列中却一直分配不到CPU时间片的情况。

短作业优先中如果某个长进程处于队列中，且有源源不断的短进程补充进来，这种时候就会导致长进程饥饿而无法运行 优先级调度法也会导致进程饥饿，这是由于某个优先级较低的进程一直被高

优先级进程抢占，导致无法运行。这种情况是可以解决的，方法是进程老化，即每隔一定时间将队列中的进程优先级升高，这样一来在某一时间后，之前的低优先级进程也会分配到时间片。

5.9 Consider a preemptive priority scheduling algorithm based on dynamically changing priorities. Larger priority numbers imply higher priority. When a process is waiting for the CPU (in the ready queue, but not running), its priority changes at a rate;

when it is running, its priority changes at a rate . All processes are given a priority of 0 when they enter the ready queue. The parameters and can be set to give many different scheduling algorithms.

a. What is the algorithm that results from β>α> 0? b. What is the algorithm that results from α<β< 0?

考虑一个基于动态改变优先级的抢占式优先级调度算法，大优先级数代表高优先级，当一个进程在ready状态等待CPU时，他的优先级以某一速率α改变，当他在running状态时，其优先级又以另一速率β改变，所有进程进入队列时优先级均为0，可以通过设置参数来形成不同的调度算法 答a.

β>α> 0时，先进入ready队列的进程会先开始提高优先级以进入running队列，这就导致后来的进程永远追不上他的优先级，也就保证了先来先服务，即FCFS调度。

b.

α<β< 0时，先进入ready队列的进程先进入到running队列中，但是running队列中的优先级衰减速度快于ready队列，这就导致在某一进程加入ready队列时，优先级高于running队列的进程，会进行一次抢占，不停循环下去ready队列中的后进进程不断抢占running队列中的先进进程，这就导致了后进进程永远比先进进程有更高的优先级，这就是先入后出调度，即first in last out

第六章

6.1 The first known correct software solution to thecritical-section problemfor two processes was developed by Dekker. The twoprocesses, P0 and P1 , share the following variables:

boolean flag[2]; /* initially false */ int turn;

The structure of process Pi (i == 0 or 1) is shown in Figure 6.25;the other process is Pj (j == 1 or 0). Prove that the algorithmsatisfies all three requirements for the critical-section problem.

第一个为人熟知的正确解决两个进程的临界区问题的软件解法由dekker提出，两个进程P0,P1共享flag，turn变量，Pi的结构在6.25中，另一进程为Pj，证明这个算法满足所有临界区问题的三要求 该算法Pi结构： Do{ flag[i]=true;

while(flag[j]){

if(turn==j){

flag[i]=false;

while(turn==j);//do nothing flag[i]=true; } }

//critical section Turn=j;

Flag[i]=false;

//remaindering section }while(true)；

答：首先明确变量含义，flag[n]为true代表Pn进程想进入临界区，turn=n代表允许Pn进程进入临界区。

临界区问题的三要素为：互斥、前进、有限等待 对于进程Pi来说，首先将其flag设置为true，接下来进行while判断，在这个while判断中，如果系统if(turn==j)，也就是说允许Pj进入临界区，则将Pi的flag设置为false，并让其在while(turn==j);//do nothing这个语句中空等待，跳出这个循环的条件是当且仅当turn=i，也就是说只有系统不允许Pj继续执行，才允许Pi继续执行，这就满足了互斥性。而处于这个while循环中的Pi进程会是接

本文来源：https://www.bwwdw.com/article/a9a2.html