操作系统部分作业参考答案.doc

第二章 进程管理
作业3. 在测量控制系统中的数据采集任务DataCollection()时，把所有采集的数据送到一个单缓冲区，计算任务DataCompute()从该缓冲区取出数据进行计算。试写出利用信号量机制实现两任务共享缓冲区Buffer的同步算法。
方法一：
Var mutex, empty, full: semaphore:=1, 1, 0;
DataCollection:
begin
repeat
……
gather data in nextp;
wait(empty);
wait(mutex);
buffer:=nextp;
signal(mutex);
signal(full);
until false;
end

DataCompute:
begin
repeat
……
wait(full);
wait(mutex);
nextc:=buffer;
signal(mutex);
signal(empty);
compute data in nextc;
until false;
end

方法二：
Var empty, full: semaphore:=1, 0;
DataCollection:
begin
repeat
……
gather data in nextp;
wait(empty);
buffer:=nextp;
signal(full);
until false;
end

DataCompute:
begin
repeat
……
wait(full);
nextc:=buffer;
signal(empty);
compute data in nextc;
until false;
end

如下的方法三有问题吗？
Var mutex: semaphore:=1;
DataCollection:
begin
repeat
……
gather data in nextp;
wait(mutex);
buffer:=nextp;
signal(mutex);
until false;
end

DataCompute:
begin
repeat
……
wait(mutex);
nextc:=buffer;
signal(mutex);
compute data in nextc;
until false;
end
答：如果有多个DataCollection和多个DataCompute，则可能会出现多个同类进程依次操作同一数据的情况，这种情况通常是不允许的。比如，多个DataCollection依次生产了多个data，只有最后一个数据得以保留。

算法
进程名
A
B
C
D
E
平 均
到达时间
0
1
3
4
6

服务时间
5
7
3
8
2
FCFS
完成时间
5
12
15
23
25

周转时间
5
11
12
19
19
13.2
带权周转时间
1
11/7
4
19/8
19/2
5.29
SJF
完成时间
5
17
8
25
10

周转时间
5
16
5
21
4
10.2
带权周转时间
1
16/7
5/3
21/8
2
2

2. 用时间片轮转法RR调度进程A、B、C、D和E，时间片q分别为2和4，完成下面的表格（参考教材P96 图3-6）。
算法
进程名
A
B
C
D
E
平 均
到达时间
0
1
2
3
4

服务时间
6
2
5
9
8
RR
q=2
完成时间
16
4
21
28
30

周转时间
16
3
19
25
26
17.8
带权周转时间
8/3
1.5
3.8
25/9
3.25
3.25
RR
q=4
完成时间
22
6
11
26
30

周转时间
22
5
9
23
26
17
带权周转时间
22/6
5/2
9/5
23/9
26/8
2.75

3. 在银行家算法中，出现如下资源分配情况：
进程/资源
Allocation
Need
Available
A B C
A B C
A B C
P0
P1
P2
P3
P4
0 2 1
1 0 1
0 1 3
3 2 1
0 2 0
4 1 0
2 3 1
4 0 4
4 2 2
5 1 3
3 5 2

问：（1）该状态是否安全，如果不安全说明理由，如果安全给出安全序列；
安全序列是：P1,P0,P2,P3,P4

（2）若进程P3提出请求Request(1,2,1)后，系统是否安全，如果不安全说明理由，如果安全给出分配后的安全序列。

假设P3的请求Request(1,2,1)得到满足，即：
进程/资源
Allocation
Need
Available
A B C
A B C
A B C
P0
P1
P2
P3
P4
0 2 1
1 0 1
0 1 3
4 4 2
0 2 0
4 1 0
2 3 1
4 0 4
3 0 1
5 1 3
2 3 1

安全序列是：P1,P3,P0,P2,P4

1. 假设有一批作业A、B、C、D、E、F，它们的大小分别为A:7KB、B:18KB、C:9KB、D:20KB、E:35KB、F:8KB，根据不同的算法把它们分配到如下空闲分区表中。

16
16
8
32
64
32
8
16
64

1） 首次适应算法
A7*
C9*
F8*
8
8
B18*
14
D20*
E35*
9
32
8
16
64

2） 循环首次适应算法
A,F,1
16
8
B,14
C,55
D,12
8
16
E,29

3） 最佳适应算法
16
16
A7*
1
B18*
C9*
5
E35*
29
D20*
12
F8*
16
64

4） 最坏适应算法
16
16
8
F,24
A,C,D28
32
8
16
B,E,11

“*”表示已分配

2. 假设物理块数M=3，有一个作业的页面走向为
4、3、2、1、4、3、5、4、3、2、1、5、6、2、3、7、1、2、6、1
1） 采用先进先出FIFO页面置换算法，计算访问过程中所发生的缺页次数和缺页率；
4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
6
1
4
3
2
1
4
3
5

2
1

6

3
7
1
2
6

4
3
2
1
4
3

5
2

1

6
3
7
1
2

4
3
2
1
4

3
5

2

1
6
3
7
1

缺页率：15/20=75%

2） 采用最佳页面Optimal置换算法，计算访问过程中所发生的缺页次数和缺页率；
4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
6
1
4
4
4
4

4

2
2

2

2
2

6

3
3
3

3

3
1

1

1
1

1

2
1

5

5
5

6

3
7

7

缺页率：11/20=55%

3） 采用最近最久未使用LRU置换算法，计算访问过程中所发生的缺页次数和缺页率。
4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
6
1
4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
6
1

4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
6

4
3
2
1
4
3
5
4
3
2
1
5
6
2
3
7
1
2
*
*
*
*
*
*
*

*
*
*
*
*
*
*
*
*
*

缺页率：17/20=85%