process producer_i begin

L1 : produce a product ; SP ( sput , mutex ) ; B [ in ]:= product ; in ：=（in + 1 ) mod k ; SV ( mutex , sget ) ; goto L1 ; end ;

process consumer_j begin

L2 : SP ( sget , mutex ) ; Product := B[out] ；

out : = [out + 1] mod k ; SV ( mutex , sput ) ; consume a product : goto L2 ; end ; coend end

57、 试用AND 型信号量和SP 、SV 操作解决五个哲学家吃通心面问题。答： Var forki：array [ 0 ? 4 ] of semaphore ; forki := 1 ; cobegin

process Pi / * i = 0 , 1 , 2 , 3 * / begin L1 : 思考；

SP ( fork [ i ] ，fork [ i + 1 ] mod 5 ) ; / * 1 = 4 时，SP ( fork [ 0 〕 ，fork [ 4 ] ) * / 吃通心面；

V(fork[i],Vfork[i+1] mod 5); Goto L1; End;

58、 如果AND 型信号量SP 中，并不把等待进程的程序计数器地址回退，亦即保持不变，则应该对AND 型信号量SV 操作做何种修改？

答：要保证进程被释放获得控制权后，能再次检测每种资源是否＞= 1 。故可在else 部分增加一条goto 语句，转向if 语句再次检测每种资源状况。

59、一般型信号量机制（参见汤子派等编著的计算机操作系统，西安电子科技大学出版社）

对AND 型信号量机制作扩充，便形成了一般型信号量机制，SP ( s1;,t1 , d1, ；? ；sn , tn , dn ) 和SV ( s1 ,d1；? sn,tn,dn）的定义如下： procedure SP ( s1 , t1 , d1 ；? ：sn , tn , dn ) var S1 ，? ，Sn：semaphore ;

t1 : ? ，tn：integer ; dl ，? ，dn : integer ; begin

if S1 > = t1 ＆? ＆Sn ＞= Tn then begin for i : = 1 to n do S1 : = S1 - di ; end else

｛进程进入第一个遇到的满足si < ti 条件的S1 信号量队列等待，同时将该进程的程序计数器地址回退，置为SP 操作处。｝; end end

procedure SV ( S1 , d1；? sn , dn ) var S1 ，? Sn：semaphore ; d1 ，? dn：integer ; begin

for i : = 1 to n do begin S1:= S1 + di ;

｛从所有s 。信号量等待队列中移出进程并置入就绪队列。｝; end end

其中，ti为这类临界资源的阀值，di为这类临界资源的本次请求数。试回答一般型信号量机制的主要特点，适用于什么场合？

答：在记录型和同时型信号量机制中，P 、V 或SP 、SV 仅仅能对信号量施行增1 或减1 操作，每次只能获得或释放一个临界资源。当一请求n 个资源时，便需要n 次信号量操作，这样做效率很低。此外，在有些情况下，当资源数量小于一个下限时，便不预分配。为此，可以在分配之前，测试某资源的数量是否大于阀值t 。对AND 型信号量机制作扩充，便形成了一般型信号量机制。 60 下面是一般信号量的一些特殊情况： ● SP ( s , d , d ) ● SP ( s , 1 , 1 ) ● SP ( s , 1 , 0 )

试解释它们的物理含义或所起的作用。 答：

● SP ( s , d , d ）此时在信号量集合中只有一个信号量、即仅处理一种临界资源，但允许每次可以申请d 个，当资源数少于d 个时，不予分配。

1. sP ( s , 1 , 1 ）此时信号量集合已蜕化为记录型信号量（当s > 1 时）或互斥信号量( s

= l 时）。

2. sP ( s , 1 , 0 ）这是一个特殊且很有用的信号量，当s > = l 时，允许多个进程进入指

定区域；当s 变成0 后，将阻止任何进程进入该区域。也就是说，它成了一个可控开关。 61、试利用一般信号量机制解决读者一写者问题·

答：对读者一写者问题作一条限制，最多只允许m 个读者同时读。为此，又引入了一个信号量L ，赋予其初值为m ，通过执行SP ( L , 1 , 1 ）操作来控制读者的数目，每当一个读者进入时，都要做一次SP ( L , 1 , 1 ）操作，使L 的值减1 。当有m 个读者进入读后，L 便减为0 ，而第m + 1 个读者必然会因执行sP ( L , 1 , 1 ）操作失败而被封锁。 利用一般信号量机制解决读者一写者问题的算法描述如下： var m : integer ; / ＊允许同时读的读进程数

L : semaphore : = m ; / ＊控制读进程数信号量，最多m W : semaphore : = 1 ; begin cobegin

process reader begin repeat

SP ( L , 1 , 1 ; W , 1 , 0 ) ; Read the file ; SV ( L , 1 ) ; until false ; end

process writer begin Repeat

SP ( W , 1 , 1 ; L , rn , 0 ) ; Write the file ; SV ( W , 1 ) ; until false ; end coend end .

上述算法中，SP ( w , 1 , 0 ）语句起开关作用，只要没有写者进程进入写，由于这时w = 1 , 读者进程就都可以进入读文件。但一旦有写者进程进入写时，其W = 0 ，则任何读者进程及其他写者进程就无法进入读写。sP ( w , 1 , 1 ; L , rn , 0 ）语句表示仅当既无写者进程在写（这时w = 1）、又无读者进程在读（这时L = rn ）时，写者进程才能进行临界区写文件。

首入门学程序计算机考计算机电子硬件知网络知专业课程答案视频教程下页 习 员 研 书下载 识 识 下载 载

第四章

作者：佚名 来源：网络

1 在一个请求分页虚拟存储管理系统中，一个程序运行的页面走向是：

1 、2 、3 、4 、2 、1 、5 、6 、2 、1 、2 、3 、7 、6 、3 、2 、1 、2 、3 、6 。

分别用FIFO 、OPT 和LRU 算法，对分配给程序3 个页框、4 个页框、5 个页框和6 个页框的情况下，分别求出缺页中断次数和缺页中断率。 答：

页框数 FIFO 16 14 12 9 LRU 15 10 8 7 OPT 11 8 7 7 3 4 5 6 只要把表中缺页中断次数除以20，便得到缺页中断率。

2 在一个请求分页虚拟存储管理系统中，一个作业共有5 页，执行时其访问页面次序

为：( 1 ) 1 、4 、3 、1 、2 、5 、1 、4 、2 、1 、4 、5 ( 2 ) 3 、2 、1 、4 、4 、5 、5 、3 、4、3、2、1、5

若分配给该作业三个页框，分别采用FIFO和LRU 面替换算法，求出各自的缺页中断次数和缺页中断率。 答：( 1 ）采用FIFO 为9 次，9 / 12 = 75 ％。采用LRU 为8 次，8 / 12 = 67 ％。( 2 ）采用FIFO 和LRU 均为9 次，9 / 13 = 69 ％。 3 一个页式存储管理系统使用FIFO 、OPT 和LRU 页面替换算法，如果一个作业的页面走向为：

( l ) 2 、3 、2 、l 、5 、2 、4 、5 、3 、2 、5 、2 。 ( 2 ) 4 、3 、2 、l 、4 、3 、5 、4 、3 、2 、l 、5 。 ( 3 ) 1 、2 、3 、4 、1 、2 、5 、l 、2 、3 、4 、5 。

当分配给该作业的物理块数分别为3 和4 时，试计算访问过程中发生的缺页中断次数和缺页中断率。

答：( l ）作业的物理块数为3 块，使用FIFO 为9 次，9 / 12 = 75 ％。使用LRU 为7 次，7 / 12 = 58 ％。使用OPT 为6 次，6 / 12 = = 50 ％。 作业的物理块数为4 块，使用FIFO 为6 次，6 / 12 = 50 ％。使用LRU 为6 次，6 / 12 = 50 ％。使用OPT 为5 次，5 /12 = 42 ％。

( 2 ）作业的物理块数为3 块，使用FIFO 为9 次，9 / 12 = 75 ％。使用LRU 为10 次，10 / 12 = 83 ％。使用OPT 为7 次，7/12 = 58 ％。

作业的物理块数为4 块，使用FIFO 为10 次，10 / 12 = 83 ％。 使用LRU 为8 次，8/12＝66％。使用OPT为6次，6/12＝50%.

其中，出现了Belady 现象，增加分给作业的内存块数，反使缺页中断率上升。 4、在可变分区存储管理下，按地址排列的内存空闲区为：10K 、4K 、20K 、18K 、7K 、9K 、12K 和15K 。对于下列的连续存储区的请求：( l ) 12K 、10K 、9K , ( 2 ) 12K 、10K 、15K 、18K 试问：使用首次适应算法、最佳适应算法、最差适应算法和下次适应算法，哪个空闲区被使用？ 答：( 1 ）空闲分区如图所示。

答

分区号 分区长 10K 4K 20K 18K 7K 9K 12K 15K 1 2 3 4 5 6 7 8 1. 首次适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。10KB 选中分区1 ，恰好分配故应删去分区1 。9KB 选中分区4 ，这时分区4 还剩9KB 。 2 ）最佳适应算法

12KB 选中分区7 ，恰好分配故应删去分区7 。1OKB 选中分区1 ，恰好分配故应删去分区1 。9KB 选中分区6 ，恰好分配故应删去分区6 。 3 ）最差适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。1OKB 选中分区4 ，这时分区4 还剩8KB 。9KB 选中分区8 ，这时分区8 还剩6KB 。 4 ）下次适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。10KB 选中分区4 ，这时分区4 还剩8KB 。9KB 选中分区6 ，恰好分配故应删去分区6 。 ( 2 ）原始分区情况同上图。 1 ）首次适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。10KB 选中分区1 ，恰好分配故应删去分区1 。15KB 选中分区4 ，这时分区4 还剩3KB 。最后无法满足18KB 的申请，应该等待。 2 ）最佳适应算法

12KB 选中分区7 ，恰好分配故应删去分区7 。1OKB 选中分区1 ，恰好分配故应删去分区1 。15KB 选中分区8 ，恰好分配故应删去分区8 。18KB 选中分区4 ，恰好分配故应删去分区4 。 3 ）最差适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。10KB 选中分区4 ，这时分区4 还剩8KB 。15KB 选中分区8 ，恰好分配故应删去分区8 。最后无法满足18KB 的申请，应该等待。 4 ）下次适应算法

12KB 选中分区3 ，这时分区3 还剩8KB 。1OKB 选中分区4 ，这时分区4 还剩8KB 。15KB 选中分区8 ，恰好分配故应删去分区8 。最后无法满足15KB 的申请，应该等待。 5 给定内存空闲分区，按地址从小到大为：100K 、500K 、200K 、300K 和600K 。