１、在南开大学与天津大学之间有一条小路，其中从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
其中，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 ５、 此为进程间执行次序问题。关键是要加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)(2)设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条件。 （2）当3个进程执行完第1步（各得R1 一台），开始执行第2步时，第4个进程会被阻塞； 当这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 则，按照短作业优先算法，作业执行顺序为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 百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库os习题课在线全文阅读。
相关推荐：