操作系统大题

8.吃苹果
桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等
吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸、儿子、女儿三个并发进程的同
步。
设置三个信号量S,So,Sa ，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，
可否取苹果。

9、哲学家进餐
有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间
放一只筷子。
chopstick[5]={1,1,1,1,1}；
count=4；
Philosopher (int i)：
while (true) //哲学家i
{
思考；
P(count)；
P(chopstick[i])； //检查左边的筷子
P(chopstick[(i+1) mod 5])；//检查右边的筷子
进餐；
V(chopstick[i])； //放下左边的筷子
V(chopstick[(i+1) mod 5])；//放下右边的筷子
V(count)；
}

银行家算法
23大题：、设系统中有三种类型的资源（A，B，C）和五个进程（P1，P2，P3，P4，P5），A资源的数量
17，B资源的数量为5，C资源的数量为20。在T0时刻系统状态如下表所示。系统采用银行家算法来避免
死锁。请回答下列问题：
（1）T0时刻是否为安全状态？若是，请给出安全序列。
（2）若进程P4请求资源（2，0，1），能否实现资源分配？为什么？
（3）在（2）的基础上，若进程P1请求资源（0，2，0），能否实现资源分配？为什么？
T0时刻系统状态
进程 最大资源需求量 已分配资源量 系统剩余资源数量
A B C A B C A B C
P1 5 5 9 2 1 2 2 3 3
P2 5 3 6 4 0 2
P3 4 0 11 4 0 5
P4 4 2 5 2 0 4
P5 4 2 4 3 1 4

（1）T0时刻为安全状态。其中的一个安全序列为（P4，P5，P3，P2，P1）
（其他可能的安全序列有：（P4，P5，X，X，X），（P4，P2，X，X，X），（P4，P3，X，X，X），（P5，X，
X，X，X））
（2）可以为P4分配资源，因为分配后的状态还是安全的，其安全序列的分析如下表：
WORK NEED ALLOCATION 新WORK FINISH
2，3，3 分配给P4：（2，0，1） 0，3，2
P4 0，3，2 0，2，0 4，0，5 4，3，7 True
P5 4，3，7 1，1，0 3，1，4 7，4，11 True
P1 7，4，11 3，4，7 2，1，2 9，5，13 True
P2 9，5，13 1，3，4 4，0，2 13，5，15 True
P3 13，5，15 0，0，6 4，0，5 17，5，20 True
（3）进程P1再请求资源（0，2，0），则不能为之分配资源。因为分配资源后，不存在安全序列，其分析
如下表：
WORK NEED ALLOCATION 新WORK FINISH
0，3，2 分配给P1：（0，2，0） 0，1，2
P4 0，2，0 此时，WORK不能满足任何一个进程的请求使之运行结束，即进入了不安全状态。 False
P5 1，1，0 False
P1 3，2，7 False
P2 1，3，4 False
P3 0，0，6 False

置换算法FIFO
课后题：
18、考虑下面存储访问序列：
10，11，104，170，73，309，185，245，246，434，458，364
该程序大小为460字，设页面大小是100字，请给出该访问序列的页面走向。又设该程序
基本可用内存是200字，采用FIFO置换算法，求出其缺页率。如果采用LRU置换算法，缺
页率是多少？如果采用最优淘汰算法，其缺页率又是多少？
参考答案：根据页面大小100字，可知页面走向为：
0， 1，0，3，1，2，4，3
程序基本可用内存是200字，表明其内存块数为2，
采用FIFO置换算法的计算过程如下所示：
0 1 0 3 1 2 4 3

1 0 0 3 3 3 4 4
1 1 1 1 2 2 3
     
缺页率＝6/12×100％＝50％
采用LRU置换算法的计算过程如下所示：
0 1 0 3 1 2 4 3

1 0 0 0 1 1 4 4
1 1 3 3 2 2 3
      
缺页率＝7/12×100％＝58.3％
采用最优淘汰算法的计算过程如下所示：
0 1 0 3 1 2 4 3

1 0 0 3 3 3 3 3
1 1 1 1 2 4 4
    
缺页率＝5/12×100％＝41.7％
说明：
1）缺页率等于缺页次数与全部访问内存次数之比
2）缺页率等于缺页次数与访问页面总次数之比（只给出页面走向时，为该串的长度）

磁盘调度算法
10、假定一个磁盘有200个柱面，编号为0一199，在完成了磁道125外的请求后，当前正在
磁道143处为一个请求服务。若请求队列的先后顺序为86，147，91，177，94，1 50，10
2，175，130 试分别采用FCFS（先来先服务），SSTF（最短寻道时间优先）和SCAN
（扫描）算法完成上述请求，写出磁头移动的顺序，并计算存取臂移动总量
【解答】采用FCFS算法调度时，磁头移动顺序为：
143→86→147→91→177→94→150→102→175→130
磁头移动总量是565（柱面）
采用SSTF算法调度时，磁头移动顺序为：
143→147→150→130→102→94→91→86→175→177
磁头移动总量是162（柱面）
采用SCAN算法调度时，磁头移动顺序为：
143→147→150→175→177→130→102→94→91→86
磁头移动总量是125（柱面）

计算方法：
fcfs: 顺序是：143--86--147--91--177--94--150--102--175--130
(143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-13
0)=565
sstf:顺序是：143--147--150--130--102--94--91--86--175--177

(147-143)+(150-147)+(150-130)+(130-102)+(102-94)+(94-91)+(91-86)+(175-86)+(177-17
5)
=162
scan:顺序是：先移动到最大柱面号(199)再移动到最小柱面号(0)再移动到130
(199-143)+(199-0)+(130-0)=385 ？？？

第三章 有关作业和进程调度算法的习题
1. 有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采
用抢占式的优先级调度算法，在下表的作业序列，作业优先数即为进程优先数，优先数越
小优先级越高。
作业名 到达时间 估计运行时间 优先数
A 8:00 40分钟 10
B 8:20 30分钟 5
C 8:30 50分钟 8
D 8:50 20分钟 2

（1）列出所有作业进入内存时间及结束时间。
（2）计算这批作业的平均周转时间及平均带权周转时间。
解：
作业执行过程如下：
8:00 A到达，内存空，A进入内存，无竞争开始运行；
8:20 B到达，进入内存，优先数为5，由于A的优先数为10，相比B优先级低，被剥夺处
理器，B开始运行；
8:30 C到达，内存满，不可进入内存；
8:50 B运行结束，同时D到达，同C争夺内存，由于D运行时间短，按照短作业优先的调
度算法，D被调入内存；D与A的优先数相比，A的优先级别高，获得处理器继续运行；
9:10 A运行结束，C进入内存，C的优先级别高于D，C开始运行；
10:00 C运行结束，D开始运行；
10:20 D运行结束。
1）所有作业进入内存时间及结束时间如下表所示：
作业 到达时间 进入内存时间 结束时间 执行时间（分钟） 周转时间 （分钟） 带权周转时
间（分钟）
A 8:00 8:00 9:10 40 70 7/4
B 8:20 8:20 8:50 30 30 1
C 8:30 9:10 10:00 50 90 9/5
D 8:50 8:50 10:20 20 90 9/2

2）作业周转时间=作业结束时间-作业到达时间
这批作业的平均周转时间=(70+30+90+90)/4=70分钟
这批作业的平均带权周转时间=(7/4+1+9/5+9/2)/4=2.26