青岛理工大学操作系统作业答案.doc

第1章 作业
综合题
1、设内存中有三道程序A、B、C，它们按A、B、C的优先次序执行。它们的计算和I/O操作时间如表所示（单位：ms）。
三道程序的操作时间
程序
操作
A
B
C
计算
30
60
20
I/O
40
30
40
计算
10
10
20
假设三道程序使用相同设备I/O操作，即程序是以串行方式使用设备，调度程序的执行时间忽略不计，试计算出在单道和多道两种情况下，完成这三道程序各要花多少时间？要求画出多道运行的时序图。（假定在多道方式下采用的是基于优先级的非抢占调度程序）
解：采用单道方式运行这三道程序，运行次序为A、B、C，故总的运行时间为：(30+40+10)+(60+30+10)+(20+40+20)=260ms
采用多道方式运行这三道程序，A、B、C这三道进程的运行存在并行，故总的运行时间如图所示为180ms

第二章
1、如图所示，有一计算进程和一打印进程，它们共享一个单缓冲
区，计算进程不断地计算出结果并将它放入单缓冲区中，打印
进程则负责从单缓冲区中取出每一个结果进行打印。请用信号量来实现它们的同步关系。
答：方法一：从临界资源的角度来思考：本题中有两类临界资源：第一类是计算进程争用的空闲缓冲区，初始状态下有一个空闲缓冲可供使用，设置信号量empty，初值为1；第二类是打印进程争用的已放入缓冲区中的打印结果，初始状态下缓冲区中无结果可打印，设置信号量full，初值为0。
var full, empty: semaphore:=0,1;
begin
parbegin
cp:begin
repeat
computer next number;
wait(empty);
add the number to buffer;
signal(full);
until false
end
pp:begin
repeat
wait(full);
take a number from buffer;
signal(empty);
print the number;
until false
end
parend
end

2、试用信号量解决读者—写者问题，使得写者与读者优先级根据到达顺序确定（读写平等）。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试
列出类似如下测试结果
进程
行为
rmutex=1
wmutex=1
Readcount=0
状态
备注
R1
到达
rmutex=0

rmutex=1

wmutex=0

Readcount=1

执行/就绪

第1位读者

1）典型错误代码讲解：不增加任何信号量
Var rmutex, wmutex:semaphore∶=1,1;
Readcount:integer∶ =0;
begin
parbegin
Reader:begin
repeat
wait(rmutex);
if Readcount=0 then wait(wmutex);
Readcount∶ = Readcount+1;
signal(rmutex);
…
perform read operation;
…
wait(rmutex);
Readcount∶= Readcount-1;
if Readcount=0 then signal(wmutex);
signal(rmutex);
until false;
end

writer:begin
repeat
if readcount>0 then wait(rumtex);
wait(wmutex);
perform write operation;
signal(rmutex);
signal(wmutex);
until false;
end
parend
end
到达序列：R1, R2, W1, R3, R4, W2
进程
行为
rmutex=1
wmutex=1
Readcount=0
状态
备注
R1
到达
rmutex=0

rmutex=1

wmutex=0

Readcount=1

执行/就绪

第1位读者
R2
到达
rmutex=0

rmutex=1

Readcount=2

执行/就绪

W1
到达
rmutex=0

阻塞1

阻塞
Readcount>0
R3
到达
阻塞1

阻塞
rmutex=0
R4
到达
阻塞2

阻塞
rmutex=0
W2
到达
阻塞3

阻塞
rmutex=0
R1
离开
阻塞4

阻塞
rmutex=0
R2
离开
阻塞5

阻塞
rmutex=0
产生死锁
2）解决方案
var S, rmutex, wmutex: semaphore:=1, 1,1;
readcount: integer:= 0;
reader: begin
repeat
wait(S);
wait(rmutex);
if readcount=0 then wait(wmutex);
readcount:=readcount+1;
signal(rmutex);
signal(S);
perform read operation;
wait(rmutex);
readcount:=readcount-1;
if readcount=0 then signal(wmutex);
signal(rmutex);
until false
end
writer: begin
repeat
wait(S);
wait(wmutex);
perform write operation;
signal(wmutex);
signal(S);
until false
end
到达序列：R1, R2, W1, R3, R4, W2
进程
行为
S=1
rmutex=1
wmutex=1
readcount=0
备注
R1
到达
S=0

S=1

rmutex=0

rmutex=1

wmutex=0

readcount=1

第一个读者

执行/就绪
R2
到达
S=0

S=1

rmutex=0

rmutex=1

readcount=2

执行/就绪
W1
到达
S=0

阻塞1

第一个写者
R3
到达
阻塞1

R4
到达
阻塞2

W2
到达
阻塞3

R1
离开

rmutex=0

rmutex=1

readcount=1

R2
离开

rmutex=0

rmutex=1

wmutex=1

readcount=0
负责唤醒W1
W1
被唤醒

wmutex=0

执行/就绪
W1
离开

S=1

wmutex=1

负责唤醒R3

3、请给出一个写者优先的“读者—写者”问题的算法描述。然后用到达序列：R1, R2, W1, R3, R4, W2进行测试
列出类似如下测试结果
进程
行为
rmutex=1
wmutex=1
Readcount=0
状态
备注
R1
到达
rmutex=0

rmutex=1

wmutex=0

Readcount=1

执行/就绪

第1位读者
答：为使写者优先，可在原来的读优先算法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成。初值为0的整型变量writecount用来对写者进行计数；初值为1 的互斥信号量mutex用来实现多个写者对writecount的互斥访问。读者与写者进程算法描述如下：
var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1;
writecount, readcount: integer:=0,0;
reader: begin
repeat
wait(S);
wait(rmutex);
if readcount=0 then wait(wmutex);
readcount:=readcount+1;
signal(rmutex);
signal(S);
perform read operation;
wait(rmutex);
readcount:=readcount-1;
if readcount=0 then signal(wmutex);
signal(rmutex);
until false
end
writer: begin
repeat
wait(mutex);
if writecount=0 then wait(S);
writecount:=writecount+1;
signal(mutex);
wait(wmutex);
perform write operation;
signal(wmutex);
wait(mutex);
writecount:=writecount-1;
if writecount=0 then signal(S);
signal(mutex);
until false
end
到达序列：R1, R2, W1, R3, R4, W2
进程
行为
S=1
mutex=1
rmutex=1
wmutex=1
writecount=0
readcount=0
备注
R1
到达
S=0

S=1

rmutex=0

rmutex=1

wmutex=0

readcount=1

第一个读者

执行/就绪
R2
到达
S=0

S=1

rmutex=0

rmutex=1

readcount=2

执行/就绪
W1
到达

S=0
mutex=0

mutex=1

阻塞1

writecount=1

第一个写者
R3
到达
阻塞1

R4
到达
阻塞2

W2
到达

mutex=0

mutex=1

阻塞2

writecount=2

R1
离开

rmutex=0

rmutex=1

readcount=1

R2
离开

rmutex=0

rmutex=1

wmutex=1

readcount=0
负责唤醒W1
W1
被唤醒

wmutex=0

执行/就绪
W1
离开

mutex=0

mutex=1

wmutex=1

writecount=1

负责唤醒W2

3、假设一个系统中有4个进程，它们的到达时间和服务时间如表所示，忽略I/O以及其他开销时间，若分别按先来先服务（FCFS）、非抢占及抢占的短进程优先（SPF）、高响应比优先（HRRN）、时间片轮转（RR，时间片=1）、多级反馈队列调度算法（MFQ，第i级队列的时间片=2i-1）进行CPU调度，请给出各进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，填入下表中（抢占式算法要求画出调度时序图，HRRN算法要求列出调度时的响应比）。30”
进程
到达时间
服务时间
A
0
5
B
1
2
C
3
9
D
6
7

算法
时间
进程
平均时间
A
B
C
D

FCFS
完成时间
周转时间
带权周转时间

SPF（非抢占）
完成时间
周转时间
带权周转时间

SPF（抢占）
完成时间
周转时间
带权周转时间

RR（q=1）
完成时间
周转时间
带权周转时间

MFQ（q=2i-1）
完成时间
周转时间
带权周转时间

作业号
到达时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
调度依据

平均周转时间为：
平均带权周转时间为：

算法
时间
进程
平均时间
A
B
C
D

FCFS
完成时间
周转时间
带权周转时间
5
5
1
7
6
3
16
13
1.44
23
17
2.43

10.25
1.97
SPF（非抢占）
完成时间
周转时间
带权周转时间
5
5
1
7
6
3
23
20
2.22
14
8
1.14

9.75
1.835
SPF（抢占）
完成时间
周转时间
带权周转时间
7
7
1.4
3
2
1
23
20
2.22
14
8
1.14

9.25
1.435
RR（q=1）
完成时间
周转时间
带权周转时间
12
12
2.4
4
3
1.5
23
20
2.22
22
16
2.29

12.75
2.1
MFQ（q=2i-1）
完成时间
周转时间
带权周转时间
13
13
2.6
6
5
2.5
23
20
2.22
21
15
2.14

13.25
2.365

作业号
到达时间
运行时间
开始时间
完成时间
周转时间
带权周转时间
调度依据
A
0
5
0
5
5
1
就绪队列中只有A
B
1
2
5
7
6
3
RPB=3
RPC=11/9=1.22
C
3
9
7
16
13
1.44
RPC=15/9=1.67
RPD=10/7=1.43
D
6
7
16
23
17
2.43
就绪队列中只有D
平均周转时间为：10.25
平均带权周转时间为：1.97

4、在一个软实时系统中有四个周期性任务，任务A、B、C、D分别要求每50ms、100ms、200ms、250ms执行一次，假定A、B、C、D的执行时间分别为35ms、20ms、10ms与x ms，那么要使得这个实时系统为可调度的，x的最大值为多少？（要求列出计算公式）10”
答：实时系统可调度的条件为： ，其中Ci 表示处理时间，Pi表示周期时间
根据题目所列条件，必须满足35/50 + 20/100 + 10/200 + x/250<=1，所以x的最大值为12.5ms

5、什么是最低松弛度优先调度算法？它采用何种调度方式？抢占时机是什么？10”
答：LLF算法根据实时任务的松弛度（松弛度 = 必须完成的时间 – 其本身的运行时间 - 当前时间）来确定任务的优先级，即任务的松弛度愈低，其优先级愈高。在实现该算法时，要求系统中有一个按松弛度排序的实时任务就绪队列。该算法主要用于可抢占调度方式中，当一任务的最低松弛度减为0时，它便立即抢占CPU，以保证按截止时间的要求完成任务。

6、若有4个周期性任务，任务A要求每30ms执行一次，执行时间为15ms；任务B要求每50ms执行一次，执行时间为5ms；任务C要求每50ms执行一次，执行时间为15ms；任务D要求每100ms执行一次，执行时间为10ms，应如何按最低松弛度优先算法对它们进行CPU调试？ （要求画出0-150ms时段的调度时序图，并列出每次切换时每个任务的松弛度）20”

对于上面的4个周期性任务，利用最低松弛度优先算法进行调度的情况如图所示：
130
140
150
120
110
0
90
80
70
60
40
30
20
10
100
50

B2,C2
A6,B4
C4
A5
A4
A3
A2
A1,B1
C1,D1
B3,C3
D2

到达时间

必须完成时间

A5,B3
C3
A4
A3
A2
A1
B2,C2
D1

B1,C1

80
65
140
145
125
110
90
95
50
35
30
15
0

松弛度

D2=45
A5=10
B3=20D2=65
A4=10
D1=10
B2=15
B2=45
C2=35
D1=40
A2=15
B1=15
D1=60
A1=15
B1=45
C1=35
D1=90

B3=5D2=60
B3=35
C3=25
D2=80
A4=15
B2=5
A3=10
B2=30
D1=25
A2=10
D1=55
B1=30
C1=20
D1=75

D1
B3
A3
C2
D2
A5
C3
A4
B2
A2
B1
C1
A1

任务执行

80
65
155
140
110
145
125
95
50
35
30
15
0
90

10、在银行家算法中，若出现下面的资源分配情况： 30”
Process
Allocation
Need
Available
P0
0 0 3 2
0 0 1 2
1 5 2 2
P1
1 0 0 0
1 6 5 0
P2
1 3 5 4
2 3 5 6
P3
0 1 3 2
0 5 5 2
P4
0 0 1 4
0 6 5 8
试问：1）该状态是否安全（要求列出安全性算法检查表）？
2）若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它（要求根据分配算法列出检查过程）？
3）如果系统立即满足P2的上述请求，请问，系统是否立即进入死锁状态，请说明原因？
答：1）利用安全性算法对上面的状态进行分析，找到了一个安全序列{P0、P3、P1、P2、P4}，故系统是安全的。
资源情况
进程
Work
A B C D
Need
A B C D
Allocation
A B C D
Work+Allocation
A B C D
Finish
P0
P3
P1
P2
P4
1 5 2 2
1 5 5 4
1 6 8 6
2 6 8 6
3 9 13 10
0 0 1 2
0 5 5 2
1 6 5 0
2 3 5 6
0 6 5 8
0 0 3 2
0 1 3 2
1 0 0 0
1 3 5 4
0 0 1 4
1 5 5 4
1 6 8 6
2 6 8 6
3 9 13 10
3 9 14 14
True
True
True
True
True
2）P2发出请求向量Request(1,2,2,2)后，系统按银行家算法进行检查：
①Request2(1,2,2,2)<=Need2(2,3,5,6)
②Request2(1,2,2,2)<=Available(1,5,2,2)
③系统先假定可为P2分配资源，并修改Available，Allocation2和Need2向量：
Available=（0，3，0，0）
Allocation2=(2,5,7,6)
Need2=（1，1，3，4）
④进行安全性检查：此时对所有的进程，条件Needi<=Available(0,3,0,0)都不成立，即Available不能满足任何进程的请求，故系统进入不安全状态。
此时当进程P2提出请求Request(1,2,2,2)后，系统不能将资源分配给它。
3）系统立即满足进程P2的请求（1，2，2，2）后，并没有马上进入死锁状态。因为，此时上述进程并没有申请新的资源，并因得不到资源而进入阻塞状态。只有当上述进程提出新的请求，并导致所有没有执行完的多个进程因得不到资源而阻塞时，系统才进入死锁状态。

11、进程资源的使用情况和可用情况如表所示，请画出资源分配图，并对资源图进行简化，这种情况下系统会发生死锁吗？20”
进程
当前分配数
待分配的请求
可用资源
R1
R2
R3
R1
R2
R3
R1
R2
R3
P1
P2
P3
P4
2
3
1
0
0
1
3
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
1
0
0
0
0

存在两种化简序列1）p2-p1-p4-p3；2）p2-p4-p1-p3

12、要使下表中描述的状态安全，可用资源的最小数目应为多少？（注意，问题问的是可用资源的数目，而不是存在的资源数）。10”
进程
当前分配数
最大分配数
R1
R1
P1
P2
P3
P4
1
1
3
2
3
2
9
7
答：如果R1有一个资源可用，能保证P2运行完。然后P2释放它现在使用的资源，使得R1类型的资源2个可用，这将允许P1执行完。P1释放它使用的资源后，R1类型的资源数增加为3个可用。只有3个R1类型的资源，如果P3、P4请求分配最大数目的资源，P3与P4就仍然处于死锁状态。如果一开始就有3个R1类型资源，而不是1个，P4就可以获得5个R1的可用资源并运行完。再加上P4原来占用的2个R1资源，就可以让P3运行。所以使该状态安全的所需可用资源的最小个数为3。