操作系统习题1(含答案) 下载本文

OutP:begin repeat

wait(full2); wait(mutex2);

Take a data from buffer2; Add to printer controler; signal(mutex2); signal(empty2); start printer;

until false end

(评分标准:信号量设置2分,输入进程、计算进程、打印进程各2分)

11.在一个请求分页系统中,有一个长度为 5 页的进程,假如系统为它分配 3 个物理块 ,并且此进程的页面走向为 2,3,2,1,5,2,4,5,3,2,5,2。试用 FIFO 和 LRU 两种算法分别计算出程序访问过程中所发生的缺页次数。(10分) 解:FIFO:

2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 5 5 5 3 3 3 第2页 3 3 3 2 2 2 5 5 第3页 1 1 1 4 4 4 2

缺页中断次数 = 6

LUR:

2 3 2 1 5 2 4 5 3 2 5 2 第1页 2 2 2 2 5 5 5 3 第2页 3 3 5 2 3 3 5 第3页 1 1 4 4 2 2

缺页中断次数 = 5

12. 进程 A1,A2,?,An 通过 K 个缓冲区向进程 B1,B2,?,Bm 不断地发送消息。发送和接收工作遵循如下规则:

1. 每个发送进程一次发送一个消息,写入缓冲区,缓冲区大小与消息长度一致; 2. 对每个消息,B1,B2,?,Bm 都需接收一次,读入各自的数据区内; 3. K 个缓冲区都满时,发送进程等待,没有可读的消息时,接收进程等待。 试用 wait 和 signal 原语操作组织正确的发送和接收操作。(10分) 解: BEGIN

Integer Mutex, Avail[n], Full[m]; Integer I;

Mutex:=1;

FOR i:=1 TO m DO BEGIN

Avail[I] := k; Full[I] := 0; END

PROCEDURE Send(K) Integer I; BEGIN

13.一个进程的大小为5个页面,为它分配了四个物理块。当前每个块的情况如下表所示(都为十进制数,且从0开始计数。)。当虚页4发生缺页时,使用下列的页面置换算法,哪一个物理块将被换出?并解释原因.(10分) 页号 块号 加载时间 访问时间 访问位R 修改位M 2 0 60 161 0 1 1 1 130 160 0 0 0 2 26 162 1 0 3 3 20 163 1 1

1. IFO算法 2. LRU算法 3. CLOCK算法

4. 当页面的访问串为:“4,0,0,0,2,4,2,1,0,3,2”的OPT算法 解:1.换出第3号虚页,因为它加载的时间最早; 2.换出第1号虚页,因为它最近最久没被访问;

3.换出第1号虚页,因为它最近既没被访问,又没被修改; 4.换出第3号虚页,因为它离访问点最远。

14. 用整型信号量描述在哲学家进餐问题中,至多允许4个哲学家同时进餐的算法。(10分) 解:public class diningphilosophers {

semaphore [] fork = new semaphore [5] (1); semaphore room = new semaphore (4); int i;

void philosopher (int i) { while (true)

think(); wait (room); wait (fork[i]); wait (fork [(i+1) % 5]); eat();

signal (fork [(i+1) % 5]); signal (fork[i]); signal (room); void main() {

parbegin (philosopher (0), philosopher (1), philosopher (2), philosopher (3), philosopher (4));

15.考虑一个有150个存储器单元的系统,如下分配给三个进程: 进程

最大

占有

}

} }

———————————————————— 1 2 3

70 60 60

45 40 15

使用银行家算法,以确定下面的任何一个请求是否安全:

a.第4个进程到达,最多需要60个存储单元,最初需要25个单元; b.第4个进程到达,最多需要60个存储单元,最初需要35个单元; 如果安全给出安全序列;若不安全给出结果分配简表。(10分) 解:进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 25 2 60 40 20 3 60 15 45 4 60 25 35

安全序列为:1、2、3、4

所以系统是安全的,可以进行分配。 b. 进程 最大 占有 尚需 可用 ———————————————————————— 1 70 45 25 15 2 60 40 20 3 60 15 45 4 60 35 25

当前可用的资源不够任何一个进程运行完毕,所以不安全。

16. Jruassic 公园有一个恐龙博物馆和一个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在博物馆逛了一会儿,然后排队乘坐旅行车。当一辆车可用时,它载入一个旅客,然后绕公园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩,则想坐车的旅客需要等待;如果一辆车已经就绪,但没有旅客等待,那么这辆车等待。使用信号量同步m个旅客和n辆车的进程。(10分)

解:

visitors=m; cars=n; mutex=1; Pvi() Pci() { repeat { repeat wait(cars); wait(visitors); wait(mutex); wait(mutex); get on; start; travell; run; get off; stop; signal(cars); signal(visitors); wait(mutex); wait(mutex); until false; until false; } }

17.读者与写者问题 (reader -- writer problems ) (10分)

在计算机体系中,对一个共享文件进行操作的进程可分为两类:读操作和写操作,它们分别被称为读者和写者。访问该文件时读者和写者,写者和写者间必须实现互斥。只有在没有读者访问文件时,写者才允许修改文件。或者写者在修改文件时不允许读者去读,否则会造成读出的文件内容不正确。试写出算法描述读者和写者的问题。

解: 为了实现读者与写者的同步和互斥,我们设置一个信号量S,用于读者与写者之间或写者与读者之间的互斥,初值为“1”。用一个变量rc 表示当前正在读的读者个数,当进程可以去读或读结束后都要改变rc 的值,因此rc 又成为若干读进程的共享变量,它们必须互斥地修改rc。故必须定义另一个用于互斥的信号量Sr,初值也是“1”。读者--写者问题可描述如下:

S, Sr:semaphore; int rc = 0; S=Sr=1;

process Reader I (i=1,2,...,m) process Writer j (j=1,2,...,k)