OS习题课部分答案.doc

______________________________________________________________________________________________________________
OS习题课部分答案
存储管理

2、某系统采用请求分页式管理，页面淘汰算法为LRU，每个作业占15页，其中一页用来存放程序，每一页存放200个整型变量，考虑如下程序：
int a[20][100],b[20][100],i,j;
for(i=1;i<=20;i++)
for(j=1;j<=100;j++)
a[i][j]=0;
for(i=1;i<=20;i++)
for(j=1;j<=100;j++)
b[i][j]=a[i][j];
设数组ab均按行存储，程序已经调入主存，变量ij放在程序页中，问此程序会产生多少次缺页中断？最后留在内存中有哪些页面？
解：
数组a，2000个元素，共需占用10个页面，每两行一页
数组b，2000个元素，共需占用10个页面，每两行一页
第一个循环，a[I,j]=0会将a矩阵全部调入内存被赋值0，发生10次缺页中断，还剩4块；
第二个循环，先读a，再写b，剩余的空闲4块内存，可放入b数组的0~7行，此时内存已满，若用A1表示a数组的a[0]和a[1]行占据的页面编号，则a数组的A0~A19和b数组的B0~B3页面（b[0]~b[7]行）均被读入内存，
即b[i][j]=a[i][j];的循环中从b[8]行开始要进行LRU淘汰，根据该循环特点，b[8]行=a[8]行
与b[9]行=a[9]行这两次循环的页面访问是A4B4A4B4，整个循环序列为：
A4B4A4B4,A5B5A5B5,…A13B13A13B13,可化简为A4B4,A5B5,…A13B13

A4
B4
A5
B5
A6
B6
A7
B7
A8
B8
A9
B9
A10
B10
A11
B11
A12
B12
A13
B13
A0

B4

B11

1

B5

B12

2

B6

B13

3

B7

4

A4

A11

5

A5

A12

6

A6

A13

7

A7

8

A8

9

B8

b0

A9

b1

B9

b2

A10

b3

B10

14次缺页中断

+

+

+

+

+
+
+
+
+
+
+
+
+
+
+
总共发生14+15=29次缺页中断，内存中最终页面A7-A13,B7-B13
3. 考虑以下程序：
int a[100][150],b[150][200],c[100][200],i,j,k;
For (i=1;i<=100;i++)
for(j=1;j<=200;j++)
for(k=1;k<=150;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
设a、b矩阵已经置好初值，c矩阵初始为0，各矩阵以页为单位连续存放；主存初始为空，请求分页时采用fifo算法。
问：当作业分配10个页面，每个页面可存储100整数，缺页次数是多少？留在内存的最后的页面abc矩阵各占多少页？
解：
矩阵a[100][150] 共需150页 每行占1.5个页面
矩阵b[150][200] 共需300页 每行占2个页面
矩阵c[100][200] 共需200页 每行占2个页面
程序的逻辑地址空间中，总共需要650个页面，试编号为：
a占用1-150号页面；b占151-450号；c占451-650号.
c[i][j]=c[i][j]+a[i][k]*b[k][j]è读a,读b,计算a*b,读c，计算c+a*b，写c；而与内存访问有关的操作可简化为：读a,读b,读c，写c
对于依次访问的a,b,c矩阵，只要不跨页，不会发生缺页中断；比如每次访问a[I,k]和c[I,j]时；但是，在每次访问b[k][j]的时候，由于是按列读取，必然跨页。采用fifo算法，页面调度过程如下：
循环变量
读写操作
内存页面
i,j,k

1
2
3
4
5
6
7
8
9
10
缺页
1,1,1
读a
1

缺

读b
1
151

缺

读c写c
1
151
451

缺
1,1,2
读a
1
151
451

读b
1
151
451
153

缺

读c写c
1
151
451
153

1,1,3
读a
1
151
451
153

读b
1
151
451
153
155

缺

读c写c
1
151
451
153
155

………每次循环发生1次缺页，且都是为读b而生，从151-165都被载入内存
1,1,8
读a
1
151
451
153
155
157
159
161
163

读b
1
151
451
153
155
157
159
161
163
165
缺

读c写c
1
151
451
153
155
157
159
161
163
165此时内存全满

1,1,9
读a
1
151
451
153
155
157
159
161
163
165

读b
167
151
451
153
155
157
159
161
163
165
缺

读c写c
167
151
451
153
155
157
159
161
163
165

1,1,10
读a
167
1
451
153
155
157
159
161
163
165
缺

读b
167
1
169
153
155
157
159
161
163
165
缺

读c写c
167
1
169
451
155
157
159
161
163
165
缺
1,1,11
读a
167
1
169
451
155
157
159
161
163
165

读b
167
1
169
451
171
157
159
161
163
165
缺

读c写c
167
1
169
451
171
157
159
161
163
165

………每次循环发生1次缺页
1,1,100
读a
1
331
333
335
337
339
341
343
345
347
缺

读b
1
349
333
335
337
339
341
343
345
347
缺

读c写c
1
349
451
335
337
339
341
343
345
347
缺
1,1,101
读a
1
349
451
2a矩阵跨页了

337
339
341
343
345
347
缺

读b
1
349
451
2
351
339
341
343
345
347
缺

读c写c
1
349
451
2
351
452c矩阵也跨页了

341
343
345
347
缺
………
100,200,148
读a
150
428
430
432
434
436
438
440
442
444
缺

读b
150
446
430
432
434
436
438
440
442
444
缺

读c写c
150
446
650
432
434
436
438
440
442
444
缺
100,200,149
读a
150
446
650
432
434
436
438
440
442
444

读b
150
446
650
448
434
436
438
440
442
444
缺

读c写c
150
446
650
448
434
436
438
440
442
444

100,200,150
读a
150
446
650
448
434
436
438
440
442
444

读b
150
446
650
448
450
436
438
440
442
444
缺

读c写c
150
446
650
448
450
436
438
440
442
444

规律：当循环次数为n*9+1或n*100+1时，读a,b,c都会发生缺页；其他情况，只有读b时发生1次缺页；
所以，读b总共发生缺页次数：100*200*150次，而对于b和c来说：
总共100*200*150=3000000次循环中，n*9+1出现次数为：3000000/9=333333次
而n*100+1出现的次数为：3000000/100=29999次;
而n*9+1与n*100+1均出现的次数为3000000/900=3333次，此次数有重复计数，需减去，所以总缺页次数为：
(100*200*150)+(333333+29999-3333)*2次，即3719998次缺页中断。

4、有一个虚拟存储系统采用LRU算法，每个程序占3页内存，其中一页存放程序和变量i,j(不做他用)。每一页可存放150个变量，程序A和B如下：
A：
int c[150][100],i,j;
for(i=0;i<=150;i++)
for(j=1;j<=100;j++)
c[i][j]=0;
B:
int c[150][100];
for(j=1;j<=100;j++)
for(i=1;i<=150;i++)
c[i][j]=0;
数组C按行存储，试问：
（1）程序A和B执行完后，分别缺页多少次？
（2）最后留在内存中的各是C的哪一部分？
解：
（1）数组C共需占100页，因为按行存储，所以每读入一个页面，会读入c数组的1.5行，如下所示：
页面1 页面2
c[1][1]………….. c[2][51]...............
…………c[1][100] ...............c[2][150]
c[2][1]………….. c[3][1]..................
…………c[2][50] ...............c[3][50]
对于程序A，c按行访问，每循环150次发生1次缺页中断，故总共发生100次缺页中断。
对于程序B，c按列访问，每循环3次就要发生2次调页，c[1][1],c[2][1],c[3][1]…..共发生2*15000/3=10000次缺页。
（2）对于程序A，后300次循环访问的c数组元素，是保存在最后两个页面中的元素
对于程序B，后3次循环访问的c数组元素，是保存在最后两个页面的元素。

１、 在南开大学与天津大学之间有一条小路，其中从S到T每次只允许一辆自行车通过，但中间有一个小的安全岛M（同时允许两辆自行车停留），可供两辆自行车在已从两端进入小路情况下错车使用，如下图所示。试用PV操作设计一个算法使得来往的自行车顺利通过。（南开９７）
天津大学
T

K M L

S
南开大学

２、设有8个进程，它们在并发系统中执行时有下图的顺序关系，试用PV操作实现这些进程的同步。（北大91考研题）

P1 P2

P3 P5
P4

P6 P7

P8

３、有一个仓库，可以存放A、B两种产品，仓库的存储空间足够大，但要求：
（1）每次只能存入一种产品（A或B）
（2）-n<A产品数-B产品数<m
其中，n和m是正整数。试用PV操作描述产品A、B的入库过程。
（北大91年考研题）

４、理发师问题：
理发店有n把椅子和一个理发师；
如果没有顾客，理发师睡觉；
如果顾客进入理发店，发现椅子满，离开；否则在空椅子上等待；
如果理发师正在睡觉，顾客必须唤醒他。试用PV操作写出工作流程
。

５、某高校开设上机实习课，机房共有2m台计算机，有2n名学生选修该课，规定：
（1）每2个学生1组，各占1台计算机，协同完成上机实习；
（2）只有1组2个学生都到齐，且机房有空闲计算机时，该组才能上机；
（3）上机实习由1名教师检查，检查完毕，一组学生同时离开机房。
试用PV操作模拟上机实习过程。（北大97考研题）

６、多进程共享一个文件，其中只读文件的进程称为读者，其他只写文件的称为写者；读者可以同时读，写者只能独立写。
（1）说明进程间的相互制约关系，应设那些信号量？
（2）用PV操作写出其同步算法。
（上交大99考研题）

７、有桥如下图所示。车流如箭头所示，假设该桥上每次只能有１辆车行驶，试用PV操作实现桥上的交通管理。（hust2001）

8、假定某计算机系统有R1 3台设备，R2 4台，它们被P1,P2,P3,P4这4个进程所共享，已经知道这4个进程均以下面所示的顺序使用现有设备。
—>声请R1->R2->申请R1->释放R1->释放R2->释放R1
(1) 说明系统运行中是否有产生死锁的可能？为何？
(2) 如果有可能的话，请举出一种情况,并画出其死锁状态的进程-资源图。（南开95）

9、设系统中有3类资源（A,B,C）和5个进程(P1,P2,P3,P4,P5),A资源数量为17,B 5, C 20,在T0时刻系统状态见下表：
最大资源需求量 已分配资源量
A B C A B C
P1 5 5 9 2 1 2
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
剩余资源数 2 3 3
以银行家算法为分配策略。
(1) T0时刻是否为安全状态，5个进程以何种顺序分配资源不会出现死锁？
(2) T0时刻若P2请求资源(0,3,4),能否实施资源分配？为什么？
(3) 在(2)的基础上，若进程P4请求资源(2,0,1),能否实施资源分配？为什么？
(4) 在（3）的基础上，若进程P1请求资源（0，2，0），能否实施资源分配？为什么？（PKU97）

10、证明：短作业优先的作业调度算法可以得到最短的平均响应时间。

答案：
１、 从天津大学到南开：T->L;into M;K->S;从南开到天津相反。
T-L和K-S路段1次只允许1辆，各1个信号量，M可2量，再设1个信号量。
又由于M只供错车使用，因此意味者每个方向上1次只能有1辆车在路上（若一个方向上出现2车，其速度快慢不同不好控制），因此再设2个信号量，代表两个方向上的车数：tn,nt
Main() TN() NT()
{ { p(tn) {p(nt);
int l=1,k=1,m=2,tn=1,nt=1; p(l); p(k);
cobegin: t->l; s->k;
TN();NT(); p(m); p(m);
v(l); v(k);
Coend into m; into m;
} p(k); p(l);
v(m); v(m);
k->s; l->t;
v(k); v(l);
v(tn); v(nt);
} }

２、
main() p1(){v(s3);v(s4);v(s5);}
{ p2(){同p1}
int s3=s4=s5=s6=s7=s8=0; p3(){ps3;ps3;vs6;}
cobegin: p4(){ps4;ps4;vs8;}
p1;p2;p3;p4;p5;p6;p7;p8; p5(){ps5;ps5;vs7}
coend p6(){ps6;vs8;}
} p7(){ps7;vs8;} p8(){ps8;ps8;ps8;}

３、 两个进程是通过数量上的关系达到相互制约的，因此是一个同步问题。
关键是搞清楚两个进程Pa Pb自己的私有信号量的问题。
AA…AA
B不能比A多n个以上，想象n-1个为满缓冲区，A为消费者，拿走1个B
BB……BBB
才能往里放1个，所以Pa的私有信号量Sa初值为n-1
AA……AA
A不能比B多m个，同理Pb的私有信号量Sb初值为m-1.
BB…BB
又：每次只能放1种产品，因此仓库是临界资源，设1个共有信号量m;
main() Pa Pb
{ {p(sb); {p(sa);
int m=1,sa=n-1,sb=m-1; p(m); p(m);
} v(m);v(sa);} v(m);v(sb);}

４、 理发师问题：理发师需要一个私有信号量barber,初值为0，代表刚开始时，理发师睡觉无资源。
顾客需要1个私有信号量customer，初值为0，代表刚开始时无顾客。
设变量count，代表顾客个数。理发师和顾客在访问椅子数量期间，必须对count互斥，故
设信号量mutex=1,代表对count的互斥。
Main()
{
int baber=0,customer=0,count=0，mutex=1;
}
baber() customer()
{ {p(mutex);//进来首先看有无空位，访问count
p(customer);//看看有无顾客，否则睡觉。 If(count<n)
P(mutex);//若有，准备理发前count— {count++;
Count--; v(mutex);
V(baber); v(customer);//告诉理发师有顾客来到
V(mutex); p(baber);//看理发师有无空闲
开始理发； 理发；
} }
else{v(mutex);exit;}
}

５、 此为进程间执行次序问题。关键是要加1个monitor进程，充当守门。

Monitor:信号量为student
信号量为enter,此时访问computer
teacher:信号量为finish
信号量为check,此时释放computer
设1个共有信号量computer代表实验室里的计算机资源，初值为2m
main()
{
int student=0,finish=0,check=0,enter=0,computer=2m;
}
student() monitor() teacher()
{ { {
v(student); p(student); p(finish);
p(enter); p(student); p(finish);
p(computer); v(enter); 检查；
实验； v(enter); v(check);
v(finish); } v(check);
p(check); }
v(computer);
}

６、 读写者问题：
进程间3类制约关系：读者之间允许同时读；读者与写者间须互斥；写者间须互斥。
设1个公有信号量mutex代表文件资源，实现读写者和写写者的互斥。
关键：读者进程是可以并发的，当读者进程数从0——>1时，必须对写者互斥，直到全部读者均已经读完，读者进程数为0时，才开放对写者的互斥。因此
设一个变量rc，代表读者进程的个数。Rc本身为临界资源，设1个公有信号量Sr互斥。
Main() reader()
{ {p(sr);
int mutex=1,sr=1,rc=0; rc++;
} if(rc==1) p(mutex);//当只有1读者时，才需要对写者互斥
v(sr);//多于1个的读者后来进来时，无须对写者互斥，直接rc++
开始读；
p(sr);
sr--;
if(rc==0) v(mutex);
v(sr);}
writer()
{
p(mutex);
开始写；
v(mutex);
}

７、 设一个信号量mutex代表桥就行。
Main() ps() pn()与ps()相同。
{int mutex=1;} {
p(mutex);
过桥；
v(mutex);
}

８、 R1有3,R2有4;
（1）4个进程每个均需R1 2台，R2 2台，即总共需要(8,8)台，可能发生死锁。只要具备4条件。
(1) （2）当3个进程执行完第1步（各得R1 一台），开始执行第2步时，第4个进程会被阻塞；
(2) 当这3个进程执行完第2步后（各的一台R2）,3个进程又同时申请R1(此时R1为0)，全部被阻塞，出现死锁。

P1 P2 P3 P4

9、（1）T时刻为安全状态，因为可以按照P4->P5->P1->P2->P3顺序进行资源分配。
（2）不能分配，P2请求(0,3,4),但C资源只有3个。
（3）系统还有(2,3,3),P4请求(2,0,1),可以满足；分配完成后：总(0,3,2),P1(3,4,7),P2(0,3,4),P3(0,0,6),P4(0,2,0),P5(1,1,0);所以，按照P4P5P1P2P3顺序可以进行。
（4）P4完成后，系统还有(0,3,2)，此时P1(0,2,0),完成后：总(0,1,2),P1(3,2,7),P2(0,3,4),P3(0,0,6),P4(0,2,0),P5(1,1,0)没有一个可以分配得下，所以不能分配。

１０、 证明：
设有n个作业j1~jn,其执行时间t1~tn,满足t1<t2<…<tn;
则，按照短作业优先算法，作业执行顺序为j1~jn，则该系统的平均响应时间为：
T1=(t1+(t1+t2)+(t1+t2+t3)+…+(t1+…+tn))/n=(n*t1+(n-1)*t2+…+tn)/n
若用非短作业优先算法，作业执行顺序为：ji1,ji2,…,jin,其中i1~in为1~n的一个排列，其平均响应时间为：
T2=(n*ti1+ti2(n-1)+…+tin)/n
因为t1<t2<…<tn;n>(n-1)>…>1;有t1*n+t2*(n-1)+…+tn是两式相乘最小的，
所以T1<T2

１１、 在一间酒吧里有三个音乐爱好者，第一位音乐爱好者只有随身听；第二个只有CD；第三个只有电池，而要听音乐就要三者齐全。酒吧老板一次借出这三种物品中的任意两种；当一名音乐爱好者得到这三种物品，并开始听完一首乐曲后，老板才能再一次借出任意两种，于是第二名音乐爱好者才能得到这三种物品并开始听音乐。不断循环下去。
解：
制约关系：
1） 听音乐的爱好者不听完，老板不会新一轮借出。
2） 老板不借出2/3的物品，对应的拥有1/3物品的爱好者不能开始听音乐；
关键问题在于，要根据借出的2/3物品，将各种物品组合分开.
1） 制约关系，设音乐爱好者私有信号量wait，代表是否听完音乐，初值为0
2） 制约关系，设老板的私有信号量S{s1,s2,s3}对应三种物品组合：
S1:CD+电池；S2：电池+随身听；S3：CD+随身听
Boss()
{
int s=genservice();//生成三种物品组合
if(s==1) v(S1);
else if(S==2) v(S2);
else v(S3);
P(wait);
}
Fans(i)
{
P(Si);
听音乐；
V(wait);
}

12

解：
制约关系：在过相同的某一号船闸的时候，P2A方向应该互斥A2P方向，纯互斥问题。
int S[T]=1;//为每个船闸设置一个信号量
countPA[T]=0;//Pacific to Atlantic的船数量
countAP[T]=0;//Atlantic to Pacific的船数量
A2P()
{
for(j=1;j<=T;j++)
{
P(mutex);
if(count[j]==0)
P(s[j]);
count[j]++;
V(mutex);
过第j+1船闸;
P(muntex);
count[j]--;
if(count[j]==0)
V(s[j]);
V(mutex);
}
}
int mutex=1;//对两类count进行互斥
P2A()
{
for(i=1;i<=T;i++)
{
P(mutex);
if(count[i]==0)
P(s[i]);
count[i]++;
V(mutex);
过第i+1船闸;
P(muntex);
count[i]--;
if(count[i]==0)
V(s[i]);
V(mutex);
}
}

１３、 某银行有人民币储蓄业务，由n个柜员负责。每个顾客进入银行后先取一个号，并等着叫号。当一个柜台人员空闲下来，就叫下一个号。使用PV操作实现同步。
解：
制约关系：
1） 柜员不空闲，不会给顾客服务；设柜员的私有信号量S1，代表有无空闲柜员，初值n;
2） 没有顾客，柜员受到制约；设顾客私有信号量S2,代表有无顾客，初值0;
对于叫号机，需要设共有信号量mutex，互斥一切并发访问。
main()
{
int mutex=1,S1=n,S2=0;
cobegin:
teller();customer();
coend;
customer()
{
P(mutex);取号;V(mutex);
P(S1);
享受服务;
V(S2);}
Teller()
{
P(S2);P(mutex);
叫号;
V(mutex);
服务;
V(S1);}
}

另解：
号码队列list：新号由队尾插入，叫号由队头取出；设信号量mutex对其互斥；
只需为customer设一个私有信号量S，初值为0;
Teller()
{
P(S);P(mutex);
从队列list中叫号;
V(mutex);
服务;
}
customer{生成新号;
P(mutex);
新号入list;
V(mutex);
V(S);
享受服务；
}

注：teller无私有资源，也就是说不管你有无空闲，叫号队列是不断增长的。

18、写者优先问题：
解1：(对应题目如果要求“一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者”)
考虑到互斥的情况，设变量readcount，初始值为0，并设置信号量mutex。
设读者与写者两个队列（ReadQ与WriterQ），文件状态 FileState变量。
对应的，设三个信号量，依次为mutexReadQ，mutexWriterQ和mutexFileState。
代码如下：
Reader（）
｛
           P(mutexWriteQ);
          while(WriteQ.Length()!=0) ； //这里体现写者优先
          V(mutexWriteQ);
         P(mutex); //只有写者为0，才能走到这里
         readcount ++;
         if (readcount==1)
                  P(mutexFileState); //首个读者将文件加锁，后续读者不
                  V(mutex);
                   Read.do(); //读者执行读操作
‍ P(mutex);
readcount --;
if (readcount==0)
    V(mutexFileState);
V(mutex);
｝

Writer()
{
          P(mutexWriteQ);
          WriterQ.push(); //写者入队
           V(mutexWriteQ);
         P(mutexFileState);//这里似乎无法互斥非首个读者
         P(mutexWriteQ);
           writer=WriterQ.pop()；
          V(mutexWriteQ);
             writer.do(); //写者执行写操作
             V(mutexFileState);
     V(mutexWriteQ);
}
另解：
设变量rc=0，代表读者的数目；为它设一互斥信号量mutex=1；
信号量Sr=1，实现对文件的互斥，包括读写互斥，写写互斥；
信号量w=1，实现写-读优先；
Reader()
{
P(w); //任何一个读者都要与写者互斥w
P(mutex);
rc++;
if(rc==1) P(Sr); //这里保证读者对写者互斥，即读-写互斥
V(mutex);
V(w); // rc++后，读者就要释放出w
开始读；
读完；
P(mutex);
rc--;
if(rc==0) V(Sr);
V(mutex);
}
Writer()
{
P(w); //只要有读者在其后来到，保证writer先于它们；同时保证写-写互斥
P(Sr); //保证文件的互斥
写；
V(Sr);
V(w);
}

19、桌上有1只盘子，每次只能放/取1个水果；爸爸专门向盘中放苹果，妈妈专门放桔子；女儿专吃苹果，儿子专吃桔子；请用PV操作实现4个人的同步关系。

解：
制约关系：
1） 盘子不为空，father受到（儿子或女儿）制约，mother也受到（儿子或女儿）制约；儿子或者女儿每运行一次，会产生一个空盘子；
所以，为儿子女儿设共同的私有信号量S=1，代表盘子是否为空.
2） 儿子受到mother制约，为mother设私有信号量So=0，代表有无苹果
3） 女儿受到father制约，为father设私有信号量Sa=0