操作系统考研习题.doc

1、哲学家进餐问题：
1）至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入到餐厅就餐，因此不会出现饿死和死锁的现象。

Var chopstick array of semaphore :={1，1，1，1，1};
room : semaphore :=4;
proce philosopher
repeat
think;
wait(room); //请求进入房间进餐
wait(chopstick[i]); //请求左手边的筷子
wait(chopstick[(i+1)%5]); //请求右手边的筷子
eat();
signal(chopstick[(i+1)%5]); //释放右手边的筷子
signal(chopstick[i]); //释放左手边的筷子
signal(room); //退出房间释放信号量room
until false;

2）规定奇数号的哲学家先拿起他左边的筷子,然后再去拿他右边的筷子;而偶数号的哲学家则相反.按此规定,将是1,2号哲学家竞争1号筷子,3,4号哲学家竞争3号筷子.即五个哲学家都竞争奇数号筷子,获得后,再去竞争偶数号筷子,最后总会有一个哲学家能获得两支筷子而进餐。而申请不到的哲学家进入阻塞等待队列，根FIFO原则，则先申请的哲学家会较先可以吃饭，因此不会出现饿死的哲学家。

Var chopstick array of semaphore :={1，1，1，1，1};
proce philosopher
repeat
think;
if (i%2 == 0) //偶数哲学家，先右后左。
wait (chopstick[ i + 1 ] mod 5) ;
wait (chopstick[ i]) ;
eat();
signal (chopstick[ i + 1 ] mod 5) ;
signal (chopstick[ i]) ;
Else //奇数哲学家，先左后右。
wait (chopstick[ i]) ;
wait (chopstick[ i + 1 ] mod 5) ;
eat();
signal (chopstick[ i]) ;
signal (chopstick[ i + 1 ] mod 5) ;
until false;
2、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。
VAR S, S1, S2 :semaphore=1,0,0;
Cobegin:
Process Father:
Begin:
Repeat
WAIT(S);
Put Apple;
SIGNAL(S1)；
Until false;
End；

Process Mother:
Begin:
Repeat
WAIT(S);
Put Orange;
SIGNAL(S2)；
Until false;
End；

Process Son:
Begin:
Repeat
WAIT(S2);
Get Orange;
SIGNAL(S)；
Until false;
End；

Process Daughter:
Begin:
Repeat
WAIT(S1);
Get Apple;
SIGNAL(S)；
Until false;
End；
CoEnd;

3、假设系统中有m个同类资源，并被n个进程所共享，进程每次只申请或释放一个资源，如果（1）每个进程至少要一个资源，且最多不超过m个资源，即对i=1,2,…,n，有0m。
（2）所有最大需求量之和小于m+n。
证明该系统不会发生死锁。
证明：
依题意，对任意Pi，i∈[1，n]，有 1≤Max(i)≤m
由条件（2）知：∑Max(i)< m+n
假设系统处于死锁状态，则有 ∑Allocation(i)=m
所以， ∑Need(i) < (m+n)-m=n
因此，至少存在一个进程Pi，有Need(i)＝0。
与条件（1）矛盾，由此假设不成立。
所以，该系统不会产生死锁。

4、两道批处理方式下的作业调度
有一个两道的批处理操作系统，作业调度采用最短作业优先的调度算法，进程调度采用基于优先数的抢占式调度算法，有如下的作业序列：

作业
进入时间
估计运行时间
优先数
JOB1
10：00
40分钟
5
JOB2
10：20
30分钟
3
JOB3
10：30
50分钟
4
JOB4
10：50
20分钟
6
其中，优先数数值越小优先级越高。
（1）列出所有作业进入内存时间及运行结束时间；
（2）计算作业平均周转时间和带权平均周转时间。

答：
两道批处理作业，作业调度采用最短作业优先，进程调度采用基于优先级的抢占式调度同时允许两个程序存在于主存中
作业
进入内存
运行时间段
周转时间
Job1
10:00
10:00-10:20
70
10:50-11:10
Job2
10:20
10:20-10:50
30
Job3
11:10
11:10-12:00
90
Job4
10:50
12:00-12:20
90
平均周转时间：
(70+30+90+90)/4=70
带权平均周转时间：
(70/40+30/30+90/50+90/20)/4=2.26