（当m>n时，每个进程最多可以请求（m+n-1）/n个该类资源）
3-15
解答：
这是进程之间的同步问题。
M2、M3和M4必须在接收到M1的消息后才能运行。
同理，M6必须在M2和M3之后运行，M7必须在M4，M5之后运行，M8必须在M3、M7之后运行。
如何保证呢？
需设置相应的信号量来保证：
S12，S13，S14，用来制约M2、M3和M4的运行；S26，S36，用来制约M6的运行；S47，S57，用来制约M7的运行；S38，S78用来制约M8的运行。
各进程的制约关系描述如下。
S12,S13,S14,S26,S36,S47,S57,S38,S78:
semaphore;
S12:
=0;S13:
=0;S14:
=0;S26:
=0;S36:
=0;S47:
=0;S57:
=0;S38:
=0;S78:
=0;
COBEGIN
PROCESSM1:
PROCESSM2:
BEGINBEGIN
V（S12）;P（S12）;
V（S13）;V（S26）;
V（S14）;END
END
PROCESSM3:
PROCESSM4:
BEGINBEGIN
P（S13）;P（S14）;
V（S36）;V（S47）;
V（S38）;END
END
PROCESSM5:
PROCESSM6:
BEGINBEGIN
V（S57）;P（S26）;
ENDP（S36）;
END
PROCESSM7:
PROCESSM8
BEGINBEGIN
P（S47）;P（S38）;
P（S57）;P（S78）;
V（S78）;END
END
COEND
3-16.叉子是临界资源，在一段时间内只允许一个哲学家使用。
一个信号量表示一把叉子，五个信号量构成信号量数组，这些信号量的初值为1。
intfork[0]=fork[1]=…=fork[4]=1;
第i个哲学家所执行的程序：
do{
P（mutex）;
P（fork[i]）;
P（fork[（i+1）mod5]）;
V（mutex）;
吃饭
V（fork[i]）;
V（fork[（i+1）mod5]）;
}while
（1）；
3-17.
（1）公平竞争（无写者时，读者仍遵循多个读者可以同时读）
rmutex互斥共享readcount;rwmutex读写互斥，写写互斥；
读写进程在z上排队。
intrmutex=1,rwmutex=1,readcount=0;
reader:
begin
p（z）;//读写进程在z上排队。
p（rmutex）;
if（readcount=0）thenp（rwmutex）;
endif
++readcount;
v（rmutex）;
v（z）;//无写者时，多个读者可以同时读.
readdata;
p（rmutex）;
--readcount;
if（readcount=0thenv（rwmutex）;
endif;
v（rmutex）;
…
end
writer:
begin
p（z）;//读写进程在z上排队。
p（rwmutex）;
writedata;
v（rwmutex）;
v（z）;
…
end
（2）写者优先
intreadcount,writecount;
semaphorermutex=1,wmutex=1,rwmutex=1,z=1,x=1;
reader：
//当来了一个写进程时，通过p（x）禁止其后读进程读，直到写进程写完为止。
while
（1）{
p（z）;//其他读进程在z上排队
p（x）;//一个读进程与一个写进程在x上竞争
p（rmutex）;//读进程互斥访问readcount
++readcount;
if（readcount==1）p（rwmutex）;
v（rmutex）;
v（x）;
v（z）;
readdata;//临界区
p（rmutex）;
--readcount;
if（readcount==0）v（rwmutex）;
v（rmutex）;
}
Writer：
while
（1）{
p（wmutex）;//写进程互斥访问writecount
++writecount;
if（writecount==1）p（x）;//一个写进程与一个读进程在x上竞争
v（wmutex）;
p（rwmutex）;//其他写进程在rwmutex上排队
writedata;//临界区
v（rwmutex）;
p（wmutex）;
--writecount;
if（writecount==0）v（x）;//写进程都写完时，通过v（x）允许读进程读
v（wmutex）;
}
附加题：
读者优先，规定仅允许5个进程同时读，怎样修改程序？
解：
增加一个资源信号量s，初值为5。
ints=5;
Reader：
begin
P（rmutex）;
readcount=readcount+1;
if（readcount==1）thenP（rwmutex）;
V（rmutex）;
P（s）;
read_file（）;
V（s）;
P（rmutex）;
readcount=readcount-1;
if（readcount==0）thenV（rwmutex）;
V（rmutex）;
end
writer:
begin
p（rwmutex）;
writedata;
v（rwmutex）;
…
end
3-18．
ints1=0,s2=n;
顾客进程：
P（s2）;
V（s1）;
坐椅子等理发
理发师进程：
P（s1）;
给顾客理发
V（s2）
读写管程
两个计数器rc和wc分别对读进程和写进程计数，用R和W分别表示允许读和允许写的条件变量，于是管理该文件的管程可如下设计：
typeread-writer=MONITOR
varrc,wc:
integer;
R,W:
condition;
definestart-read,end-read,start-writer,end-writer;
usewait,signal,check,release;
procedurestart-read;
begin
check（IM）;
ifwc>0thenwait（R,IM）;
rc:
=rc+1;
signal（R,IM）;
release（IM）;
end;
procedureend-read;
begin
check（IM）;
rc:
=rc-1;
ifrc=0thensignal（W,IM）;
release（IM）;
end;
procedurestart-write;
begin
check（IM）;
wc:
=wc+1;
ifrc>0orwc>1thenwait（W,IM）;
release（IM）;
end;
procedureend-write;
begin
check（IM）;
wc:
=wc-1;
ifwc>0thensignal（W,IM）;
elsesignal（R,IM）;
release（IM）;
end;
begin
rc:
=0;wc:
=0;R:
=0;W:
=0;
end.
任何一个进程读（写）文件前，首先调用start-read（start-write），执行完读（写）操作后，调用end-read（end-write）。
即：
cobegin
processreader
begin
……
callread-writer.start-read;
……
read;
……
callread-writer.end-read;
……
end;
processwriter
begin
……
callread-writer.start-write;
……
write;
……
callrear-writer.end-write;
……
end;
coend.
上述程序能保证在各种并发执行的情况下，读写进程都能正确工作，请读
3-19．
（2）和（4）会发生死锁。
3-20．
P1/剩余
P2/剩余
P3/剩余
系统剩余
1
3/5
7
2
2/4
5
3
4（不安全）
4
5/3
3
5
2（不安全）
6
（5+3）/0
0（8）
7
4/3
4
8
（2+2）/2
2
9
（1）P1占有5个资源，剩余3个资源请求。
P2占有2个资源，剩余4个资源请求。
P3占有0个资源，剩余7个资源请求。
系统剩余3个资源。
（2）P1的请求最先满足。
进程完成序列：
P1，P2，P3。
3-21．
（1）
最大需求矩阵：
分配矩阵：
剩余请求矩阵：
Max=Allocation=Need=
剩余资源向量：
Available=（1502）
（2）当前系统是安全的。
判断系统是否安全，只要检查系统剩余资源向量能否对各进程的剩余请求向量找到一个进程完成序列，当按照这个序列为各进程分配资源时，各进程都能成功完成。
若能找到，则系统是安全的，否则，为不安全。
先找到p0,因为p0已满足最大资源请求，它可以完成，释放其占有的资源，使系统剩余资源向量为（1514）
之后，系统剩余资源向量（1514），可满足进程p2,使p2可以完成，释放其占有的资源，使系统剩余资源向量为（2868）。
之后无论选哪一个进程都可成功完成。
故找到的进程完成序列可为：
p0,p2,p4,p3,p1;或p0,p2,p3,p1,p4等，故系统是安全的。
（3）因系统剩余可用向量为（1502），p2的剩余请求向量为（1002），即（1502）>（1002）。
故，当p2提出（1001）请求时，能满足。
进程完成序列：
p0,p2,p4,p3,p1
第4章习题答案
4-14内存有如下顺序排列的空闲块：
10K，40K，20K，18K，7K，9K，12K和15K，有如下的请求序列：
12K，10K，9K。
（1）若采用首次适应法：
（内存块的拆分）
●12K的请求：
将分配40K的空闲块，40K变为剩余的（40-12）K=28K，空闲队列变为：
10K，28K，20K，18K，7K，9K，12K和15K；
●10K的请求：
将分配10K的空闲块，空闲队列变为：
28K，20K，18K，7K，9K，12K和15K；
●9K的请求：
将分配28K的空闲块，空闲队列变为：
（28-9）=18K，20K，18K，7K，9K，12K和15K；
（2）若采用最佳适应法：
●12K的请求：
将分配12K的空闲块，空闲队列变为：
10K，40K，20K，18K，7K，9K和15K；
●10K的请求：
将分配10K的空闲块，空闲队列变为：
40K，20K，18K，7K，9K，12K和15K；
●9K的请求：
将分配9K的空闲块，空闲队列变为：
40K，20K，18K，7K，12K和15K；
（3）若采用最坏适应法：
●12K的请求，将分配40K的空闲块，空闲队列变为：
10K，28K，20K，18K，7K，9K和15K；
●10K的请求：
将分配28K的空闲块，空闲队列变为：
20K，18K，7K，9K，12K和15K；
●9K的请求：
将分配20K的空闲块，空闲队列变为：
10K，18K，11K，18K，7K，12K和15K。
4-15有如下图所示的页表中的虚地址与物理地址之间的关系，即该进程分得6个内存块。
页的大小为4096。
给出对应下面虚地址的物理地址：
（1）20；
（2）5100；（3）8300；（4）47000.
0
1
2
3
4
5
6
7
2
1
6
0
4
3
x
x
解：
（1）虚地址20变为页号0和页内偏移20
由页号查页表得0页对应内存块号为2，可计算得
物理地址=块号*页的大小+页内偏移=2*4096+20=8212
（2）虚地址5100变为页号1和页内偏移1004（5100/4096）
由页号查页表得1页对应内存块号为1，可计算得
物理地址=块号*页的大小+页内偏移=1*4096+1004=5100
（3）虚地址8300变为页号2和页内偏移108
由页号查页表得2页对应内存块号为6，可计算得
物理地址=块号*页的大小+页内偏移=6*4096+108=24684
（4）虚地址47000变为页号11和页内偏移1944
11＞7页号越界
4-16一个作业在执行过程中，按如下顺序依次访问各页，作业分得四个主存块，问分别采用FIFO、LRU和OPT算法时，要产生多少次缺页中断?
设进程开始运行时，主存没有页面。
页访问串顺序为：
01723271032517
（1）FIFO
01723271032517
采用FIFO淘汰算法，产生9次缺页中断。
（2）LRU
01723271032517
采用LRU算法时，产生11次缺页中断。
4-17考虑如图所示的段表，给出如下所示的逻辑地址所对应的物理地址。
段始址
段的长度
219
600
2300
14
92
100
1326
580
1954
96
（1）0，430219+430=649
（2）1，102300+10=2310
（3）2，500500＞100段内地址越界
（4）3，4001326+400=1726
（5）4，112112＞96段内地址越界
4-18一台计算机含有65536字节的存储空间，这一空间被分成许多长度为4096字节的页。
有一程序，其代码段为32768字节，数据段为16386字节，栈段为15870字节。
试问该机器的主存空间适合这个作业吗?
如果每页改成512字节，适合吗?
答：
（1）
存储空间每块为4096个字节，共可分成16块。
程序代码段占32768/4096=8块，数据段占16386/4096=5块，栈段占15870/4096=4块，合计为8+5+4=17块，故该机器的主存空间不适合这个作业。
（2）
当存储空间每块为512个字节，共可分成128块。
程序代码段占32768/512=64块，数据段占16386/512=33块，栈段占15870/512=31块，合计为64+33+31=128块，故该机器的主存空间是适合这个作业的。
4-19逻辑地址中，用9位表示页号，用10位表示页内地址。
升级会员 