湖南大学操作系统作业-(3).docx

操作系统第二次作业
第五章Why is it important for the scheduler to distinguish l/O-bound programs from CPU-bound programs?
为何调度器要区分10约束程序和CPU约束程序？
答：二者对CPU的使用有较大差别，10操作只需少量的CPU时间片，大部分时 间用于10的等待，而CPU约束操作需要用整块时间，在CPU操作的后台可以同 时运行10等待操作，二者互不影响，通过区分两种操作，加上系统的调度，可 以更好的利用CPU资源，提高运行效率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 = lOOmilliseconds= 0.99 and 0 = lOmilliseconds
考虑预测下一个CPU区间的指数平均公式，当下列参数分别取对应值时的影响 是什么答：指数平均公式：T(n+l)=at(n)+(l-a)Tn
参数Tn+1的含义是预测下一 CPU区间的预测值，tn为第n个CPU区间的长 度，a代表预测值和上一区间长度的【相关度】，也就是说，a取值越大，上一个 区间(真实发生的)长度对预测值的影响就越大，反之，a取值越小，预测值就 主要体现为上一次的预测值。
a=0, t=100ms
定0代表真实发生的区间长度不会影响预测，也就是说预测值会一直保持为 上一次预测值，即t,故本次预测值为100ms
a=0.99 t=10ms
a=0.99代表预测值基本完全体现为上一次真实发生的CPU区间长度，也就是 说预测值基本是前一个区间的长度，比如tn=50ms,则下一次预测值也大致为 50msoConsider the following set of processes, with the length of the CPU-burst time given in milliseconds:
Process Burst Time PriorityPl103
P211P323
P414P552
The processes are assumed to have arrived in the order Pl, 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那种调度算法会有最小的平均等待时间？
裁
)9⑥
系统

(L 7
(% Y
PlP2
P3 P4 P5
010 1113 1419
SJF：
P2
P4 P3
P5
Pl
0 1
non
24919
□reemptive priority:
P4列表如下:
a.
FCFS:
P2P5
PlP3
0 1
Pl
P2
P3
P4
P5
Pl
P3
P5
Pl
P5
Pl
P5
Pl
P5
Pl
Pl
Pl
Pl
Pl
RR：
61618 19
b.每个进程的周转时间:

FCFS
SJF
Priority
RR
Pl
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
Pl
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.3 Which of the following scheduling algorithms could result in starvation?
a. First-come, first-served b. Shortest job firstRound 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>a> 0?
b. What is the algorithm that results from a<P< 0?
考虑一个基于动态改变优先级的抢占式优先级调度算法，大优先级数代表高优 先级，当一个进程在ready状态等待CPU时，他的优先级以某一速率a改变， 当他在running状态时，其优先级又以另一速率。改变，所有进程进入队列时优 先级均为0,可以通过设置参数来形成不同的调度算法 答a.
P>a> 0时，先进入ready队列的进程会先开始提高优先级以进入running队 列，这就导致后来的进程永远追不上他的优先级，也就保证了先来先服务，即FCFS 调度。
b.
a<P< 0时，先进入ready队列的进程先进入到running队列中，但是running 队列中的优先级衰减速度快于ready队列，这就导致在某一进程加入ready队列 时，优先级高于running队列的进程，会进行一次抢占，不停循环下去ready队 列中的后进进程不断抢占running队列中的先进进程，这就导致了后进进程永远 比先进进程有更高的优先级，这就是先入后出调度，即first in last out第八草
6.1 The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, PO and Pl , 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 algorithm satisfies all three requirements for the critical-section problem.
第一个为人熟知的正确解决两个进程的临界区问题的软件解法由dekker提出， 两个进程PO,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 sectionTurn=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进程会是接 下来进入临界区的所有选择，所以也满足前进性
在Pj执行完之后，Pi进程的flag也被设置为true, Pi进程进入临界区，执行 完毕后又将执行许可给Pj进程，且设置Pi的flag为false,这就说明了 Pi不会一 直占用临界区，满足有限等待要求The first known correct software solution to the critical-section problem for n processes with a lower bound on waiting of n? 1 turns was presented by Eisenberg and McGuire.
The processes share the following variables:
enum pstate (idle, wantjn, in_cs};pstate flag[n];
int turn;All the elements of flag are initially idle; the initial value of turn is immaterial (between 0 and n-1). The structure of process Pi is shown in Figure 6.26. Prove that the algorithm satisfies all hree requirements for the critical-section problem.
类似于上一题，这题是对于n个进程的等待次数为n-1的软件解决方法，进程间 共享 flag、turn。
Flag的所有元素都被初始化idle, turn的初值是。到n・l的某个值，Pi的结构在 6.26中，证明它满足临界三要素。
答:书上给的代码少了半个大括号，感觉应该是加到第一个if的后面。我 就照这个理解来分析代码。
Pi进程的结构：假设进程j进入了临界区，根据算法可得则此时的 flag[j]==incso这时其他想要进入临界区并且已经将自己的flag设为in cs的进程 在 while((j<n)&&(j==i11flag[j]!=incs))检测到进程 j 的 flag 为 in cs,则跳出 while 循环，如无其他进程为in_cs或turn进程为idle,才能允许Pi进入临界区
退出临界区后，又一次进行轮询，选出下一个要进入临界区的进程并改变其flag和设置tumo
综上，一个进程Pi进入临界区的条件为：设置flag变量、确保turn和i之 间的flag 均为idle、将其flag 升为jn cs, 并检查有无其它进程也设置了 jn cs, 如无其他进程为in cs或turn进程为idle,则该进程进入临界区。
接下来论证临界三要素
互斥：
假设进程j进入了临界区，根据算法可得则此时的flag[j]==incso这时其他想要 进入临界区并且已经将自己的flag设为in cs的进程在while((j<n)&&(j==i 11flag[j]!=incs))检测到进程 j 的 flag 为 in cs 测跳出 while 循 环，并且下一句if判断由于j>=n不成立所以该进程返回最开始的while(true)循 环而不能够进入临界区。故满足互斥。
前进：
假设进程j刚出临界区且当前没有进程在临界区，j将turn设为下一个想要进入 (want in)或已经等待进入(in cs)的进程号(若没有想进入的则又把turn设置回自 己，这是为了满足flag[turn]==idle以便让i进入的情况)，再将自己的flag值设 为idle,然后j进入剩余区，这时可以被选择进入临界区的进程只有除j以外的 进程而不包括在剩余区的j,若j想要再次进入临界区则需要重新到进入区才会 被选择进入。故满足前进条件。
有限等待：
假设进程i做出进入临界区的请求，则在进入区它需要在：
j=turn；
while(j!=i)(if(flag[j]!=idle j=turn;
else j=(j+l)%n；}
这里等待j=i,当有进程出临界区之后，通过：
j=(turn+l)%n
while(flag[j]==idle)
j=(j+l)%n
turn=j;
将turn设置为从它往后数下一个flag为want in或in cs的进程，则进程i最 多只需等待从i+1到n-1号进程，以及从0到i-1号的进程进入临界区(共n-1 个)便可进入。即等待其他进程进入临界区的次数有限故满足有限等待。
6.9 Show that, if the wait() and signal() semaphore operations are not executed atomically, then mutual exclusion may be violated.
说明如果wait和signal不是原子操作，那么互斥可能被破坏。
答：简单地说，对于某个指令，在原子状态下的执行会限定函数体内的代码 会无中断地执行，但是非原子状态下，如果多个进程同时执行该语句中的变量变 化指令，如s-,由于该指令是靠寄存器传值的(三个步骤，把s传给寄存器a, 寄存器a=a-l,把a・l传给s),多个进程的调用会导致s的值混乱，从而影响互 斥。
Wait和signal的原子操作原理大致相同，如果多个进程以如下顺序同时执行 wait和signal操作(默认s为0的情况下)
S->value-;
S・>value++;
if(S->value<0)(
add this process to S->list;block();
)
if(S->value<=0)(
remove a process P from S->list;
wakeup(P);
)
这样执行的结果是：i进程判断S->value<0时不满足，则不会被挂起，j进程 唤醒的进程也不是i,与原先原子操作的结果不符。
6.11 The Sleeping-Barber Problem.
A barbershop consists of a waiting room with n chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate the barber and the customers.
理发店问题，理发店里有n个椅子，1个理发椅，如无顾客，理发师就去睡觉, 如顾客进入理发店且所有椅子都占有，顾客离开，如理发师在忙且有椅子，顾客 坐椅子上等待，如理发师在睡觉，则唤醒理发师，写一个程序来反映这个问题。
答：
Mutex=l, customer=0, baber=l, wait count=0;Barber
while (true){P(customer); //没有顾客就睡觉
P(mutex); 〃来顾客了，准备理发 wait_count--; 〃顾客坐到理发椅上V(mutex);
cut hair;//理完了一个，可以理下一个了
V(barber);)
Costumerwhile (true){
P(mutex); //互斥，防止抢椅子if (wait_count<n){ wait_count++; //有椅子坐，不走了 V(mutex);
V(costumer); //叫醒理发师
P(barber); //理发师忙就等一会 get haircut;}
else//没有椅子了，不剪了
leave;
V(mutex);}
6.15 Discuss the tradeoff between fairness and throughput of operations in the readers-writers problem. Propose a method for solving the readers- writers problem without causing starvation.
讨论读者写者问题的公平性和吞吐量，提出一个不会造成饥饿的算法答：上课提过，课本上给出的读者进程满足的是如果有读者和写者同时在读者进 程内wait (wrt)等待时，并非先来先服务，而是对于读者优先，也就是先来的 写者会造成饥饿(如果有源源不断的读者进程到来的话)，这显然是不公平的，
在这种情况下，吞吐量由读者决定
不会造成饥饿的算法只要添加一个信号量rd,代码在课件中已经给出，结构 如下：
写者进程
do{
wait(rd); wait(wrt);• • •
//writing is performed• • •
signal(wrt); signal(rd);)while(true)
读者进程do{
wait(rd); wait(mutex);
readcount++；
if (readcount == 1)
wait(wrt); signal(mutex); signal(rd);• • •
//reading is performed• • •
wait(mutex); readcount-;if (readcount == 0) signal(wrt);
signal(mutex):
}while(true)
这样，在读者的wait(rd)中如果阻塞了写者进程，前一个读者进入读者临界区 后写者便可以在wait(wrt);处挂起，而其他后进读者进程必须在wait(rd)处挂起, 这样就可以使先到的写者先被服务，防止写者饥饿。