下载文档原格式
操作系统练习题：1 在南开大学和大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M（同时允许两辆自行车停留），可供两辆自行车已从两端进小路情况下错车使用，如图所示。
试设计一个算法使来往的自行车均可顺利通过。
解答:首先中间的安全岛M仅允许两辆自行车通过，应作为临界资源设置信号量。
但仔细分析发现，在任何时刻进入小路的自行车最多不会超过两辆（南开和天大方向各一辆），因此不需为安全岛M设置信号量。
在路口S处，南开出发的若干辆自行车应进行路口资源的争夺，以决定谁先进入小路SK段，为此设置信号量S，用以控制路口资源的争夺；同理，设置信号量T，控制天大方向自行车对路口T的争夺。
又小路SK段仅允许一辆车通过，设置信号量SK初值为1，同理设置小路LT段信号量LT初值为1。
程序如下：S ：= l; T：=1; SK ：＝1; LT：=1；Parbegin进程P:（南开方向自行车）beginP(S) ; {与其它同方向的自行车争夺路口S}P(SK); ｛同对面自行车争夺路段SK｝通过SK;进入M；**V (SK);｛一旦进入M，便可释放路段SK｝P (LT) ; {同对面的自行车争夺路段LT}通过LT;V (LT)；｛将路段LT释放｝V(S); ｛将路口S释放给同方向的正在路口S处等待的自行车｝end，进程Q:（天大方向自行车）beginP(T)；P(LT)；通过LT;进入M;V(LT)；P(SK)；通过SK;V(SK)；V(T)；End；Parend。
说明＊＊：P进程进入安全岛M后，释放了路段SK，但没有释放路口S，原因在于它是向对面的4进程释放路段资源SK，而在P进程离开小路LT后，才会将路口S 释放给其他P进程，如不这样，就会死锁。
请考虑如下情况：两个方向各有一辆车前进，若在P进程到达安全岛M后，执行V (S)及V (SK)操作，则有可能使得同方向的其它P进程得到路段SK的使用权，而进入小路；同理，Q进程到达安全岛后执行V (LT)及V (T)操作，有可能使得同方向的其它Q进程得到路段LT 而进入小路。
1【单选题】用P、V操作管理临界区时,互斥信号量的初值应定义为( A)。
•A，1•B，0•C，-1•D，任意值2【单选题】在操作系统中,对信号量S的P原语操作定义中,使进程进入相应等待队列等待的条件是( )。
•A，S>0•B，S = 0•C，S<0•D，S<>0我的答案：C3【单选题】信号量S的初值为8,在S上执行了10次wait 操作,6次signal操作后,S的值为(D )。
•A，10•B，8•C，6•D，4P操作每执行一次,信号量减1；V操作每执行一次,信号量加1.所以答案为8-10+6 = 44【单选题】用V操作唤醒一个等待进程时,被唤醒进程的状态应变成( B)状态。
•A，执行•B，就绪•C，阻塞•D，挂起被唤醒的进程由等待状态变为就绪状态。
5【单选题】利用Wait和signal操作可以( )。
•A，实现进程互斥和同步•B，检测死锁•C，解除死锁•D，防止死锁我的答案：A6【单选题】两个并发进程,设互斥信号量mutex(初值为1),若信号量=0;则(B )•A，表示没有进程进入临界区•B，表示有一个进程进入临界区•C，表示有一个进程进入临界区,另一个进程等待进入•D，表示两个进程进入临界区临界区不允许两个进程同时进入，D选项明显错误。
mutex初值为1，表示允许一个进程进入临界区，当有一个进程进入临界区且没有进程等待进入时，mutex值减1，变为0。
7【单选题】V操作是对信号量执行加1操作,意味着释放一个单位资源,加1后如果信号量的值等于零,则从等待队列中唤醒一个进程,现进程变为等待状态,否则现进程继续进行。
•A，对•B，错我的答案：B8【单选题】有3个进程,两台打印机,用wait和sigual操作来实现互斥访问打印机,则信号量S的取值范围是( )•A，2,1,0,-1•B，3,2,1,0•C，2,1,0,-1,-2•D，1,0,-1,-2我的答案：如果n个进程共享两个打印机，信号量取值范围：-(n-2)~2;9【单选题】设与某资源相关的资源信号量K,初值为3,当前值为1,则可用资源个数为( ),等待资源的进程数为( )。
操作系统练习题：1 在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M（同时允许两辆自行车停留），可供两辆自行车已从两端进小路情况下错车使用，如图所示。
试设计一个算法使来往的自行车均可顺利通过。
解答:首先中间的安全岛M仅允许两辆自行车通过，应作为临界资源设置信号量。
但仔细分析发现，在任何时刻进入小路的自行车最多不会超过两辆（南开和天大方向各一辆），因此不需为安全岛M设置信号量。
在路口S处，南开出发的若干辆自行车应进行路口资源的争夺，以决定谁先进入小路SK段，为此设置信号量S，用以控制路口资源的争夺；同理，设置信号量T，控制天大方向自行车对路口T的争夺。
又小路SK段仅允许一辆车通过，设置信号量SK初值为1，同理设置小路LT段信号量LT初值为1。
程序如下：S ：= l; T：=1; SK ：＝1; LT：=1；Parbegin进程P:（南开方向自行车）beginP(S) ; {与其它同方向的自行车争夺路口S}P(SK); ｛同对面自行车争夺路段SK｝通过SK;进入M；**V (SK);｛一旦进入M，便可释放路段SK｝P (LT) ; {同对面的自行车争夺路段LT}通过LT;V (LT)；｛将路段LT释放｝V(S); ｛将路口S释放给同方向的正在路口S处等待的自行车｝end，进程Q:（天大方向自行车）beginP(T)；P(LT)；通过LT;进入M;V(LT)；P(SK)；通过SK;V(SK)；V(T)；End；Parend。
说明＊＊：P进程进入安全岛M后，释放了路段SK，但没有释放路口S，原因在于它是向对面的4进程释放路段资源SK，而在P进程离开小路LT后，才会将路口S 释放给其他P进程，如不这样，就会死锁。
请考虑如下情况：两个方向各有一辆车前进，若在P进程到达安全岛M后，执行V (S)及V (SK)操作，则有可能使得同方向的其它P进程得到路段SK的使用权，而进入小路；同理，Q进程到达安全岛后执行V (LT)及V (T)操作，有可能使得同方向的其它Q进程得到路段LT 而进入小路。
操作系统自测题三一选择题1.以下________操作系统中的技术是用来解决进程同步的。
A.管道B.管程C.通道D.DMA2.以下________不是操作系统的进程通信手段。
A.管道B.原语C.套接字D.文件映射3.如果有三个进程共享同一程序段，而且每次最多允许两个进程进入该程序段，则信号量的初值应设置为________。
A.3B.2C.1D.04.下面有关进程的描述，________是正确的。
A.进程执行的相对速度不能由进程自己来控制B.进程利用信号量的P、V操作可以交换大量的信息C.并发进程在访问共享资源时，不可能出现与时间有关的错误D.P、V操作不是原语操作5.信号可以用来实现进程之间的________A.调度B.同步与互斥C.同步D.互斥6.对于两个并发进程都想进入临界区，设互斥信号量为S,若某时S=0，表示________。
A.没有进程进入临界区B.有1个进程进入了临界区C.有2个进程进入了临界区D.有1个进程进入了临界区并且另一个进程正等待进入7.信箱通信是一种________方式。
A.直接通信B.间接通信C.低级通信D.信号量8.以下关于临界区的说法，________是正确的。
A.对于临界区，最重要的是判断哪个进程先进入B.若进程A已进入临界区，而进程B的优先级高于进程A，则进程B可以打断进程A而自己进入临界区C.信号量的初值非负，在其上只能做P、V操作D.两个互斥进程在临界区内，对共享变量的操作是相同的9.并发是指________。
A.可平行执行的进程B.可先后执行的进程C.可同时执行的进程D.不可中断的进程10.临界区是________。
A.一个缓冲区B.一段数据区C.一段程序D.栈11.进程在处理机上执行，它们的关系是________。
A.进程之间无关，系统是封闭的B.进程之间相互依赖、相互制约C.进程之间可能有关，也可能无关D．以上都不对12.在单处理机中，如果系统中有N个进程，则就绪队列中的进程个数最多的是________。
操作系统同步试题1、设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆；正常行车；到站停车；售票员的活动：关车门；售票；开车门；在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。
设两个信号量S和C，初值为S＝0；C＝0；司机：L1：正常行车售票员：L2：售票到站停车P（S）V（S）开车门P（C）关车门启动开车V（C）GO TO L1 GO TO L22、桌子上有一个空盘子，允许存放一只水果，爸爸可以向盘中放苹果，妈妈向盘子中放橘子，女儿专门吃盘子中的苹果，儿子专门吃盘子中的橘子。
规定当盘子空的时候一次只能放一只水果，请用信号量实现他们之间的同步与互斥。
S, S1, S2 :semaphore=1,0,0;Cobegin:Process Father:Begin:L1: P(S);Put Apple;V(S1)；GO TO L1；End；Process Mother:Begin:L2: P(S);Put Orange;V(S2)；GO TO L2；End；Process Son:Begin:L3: P(S2);Get Orange;V(S)；GO TO L1；End；Process Daughter:Begin:L4: P(S1);Get Apple;V(S)；GO TO L4；End；2、写者优先的“读者――写者”问题：1）共享读2）互斥写、读写互斥3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）wmutex:semaphore=1 //读者与写者之间、写者与写者之间互斥使用共享数据S：semaphore=1 //当至少有一个写者准备访问共享数据时，它可使后续的读者等待写完成S2：semaphor＝1 //阻塞第二个以后的等待读者readcount,writecount: semaphore = 0,0; //当前读者数量、写者数量mutex1 :semaphore = 1 //多个读者互斥使用readcountmutex2 :semaphore = 1 //多个写者互斥使用writecountCobegin:Reader: beginRepeatWait（S2）；wait(S);wait(mutex1)if readcount=0 then wait(wmutex);readcount++;signal (mutex1);signal(S);signal（S2）；reading…wait(mutex1);readcount--;if readcount=0 then signal(wmutex);signal(mutex1);until false;begin;writer: beginrepeat;wait(mutex2);if writecount=0 then wait(S);writecount++;signal （mutex2）;wait(wmutex);writing…signal(wmutex);wait(mutex2);writecount--;if writecount=0 then signal(S);signal （mutex2）;until false;end;coend;4、有一个仓库，可以存放A、B两种产品，但要求：①每次只能存入一种产品（A或B）；②A产品数量－B产品数量<M；③B产品数量－A产品数量<N；其中M、N是正整数，使用P、V操作描述产品A与产品B的入库过程。
操作系统练习题：1 在南开大学和天津大学之间有一条弯曲的小路，其中从S到T一段路每次只允许一辆自行车通过，但中间有一个小的“安全岛”M（同时允许两辆自行车停留），可供两辆自行车已从两端进小路情况下错车使用，如图所示。
试设计一个算法使来往的自行车均可顺利通过。
K S南开天大T ML解答 :首先中间的安全岛 M仅允许两辆自行车通过，应作为临界资源设置信号量。
但仔细分析发现，在任何时刻进入小路的自行车最多不会超过两辆（南开和天大方向各一辆），因此不需为安全岛 M设置信号量。
在路口 S 处，南开出发的若干辆自行车应进行路口资源的争夺，以决定谁先进入小路SK段，为此设置信号量S，用以控制路口资源的争夺；同理，设置信号量T，控制天大方向自行车对路口T 的争夺。
又小路 SK段仅允许一辆车通过，设置信号量 SK初值为 1，同理设置小路 LT 段信号量 LT 初值为 1。
程序如下：S ： = l; T ： =1; SK ：＝ 1; LT ： =1；Parbegin进程P: （南开方向自行车）beginP(S) ; { 与其它同方向的自行车争夺路口 S}P(SK); ｛同对面自行车争夺路段 SK｝通过 SK;进入 M； **V (SK); ｛一旦进入 M，便可释放路段 SK｝P (LT) ; { 同对面的自行车争夺路段 LT}通过 LT;V (LT) ；｛将路段 LT 释放｝V(S); ｛将路口 S 释放给同方向的正在路口 S 处等待的自行车｝end，进程 Q:（天大方向自行车）beginP(T) ；P(LT) ；通过 LT;进入 M;V(LT) ；P(SK)；通过 SK;V(SK)；V(T) ；End；Parend。
说明＊＊：P 进程进入安全岛 M后，释放了路段 SK，但没有释放路口 S，原因在于它是向对面的 4 进程释放路段资源 SK，而在 P 进程离开小路 LT 后，才会将路口 S 释放给其他 P 进程，如不这样，就会死锁。
1、测量控制系统中的数据采集任务把所采集的数据送一单缓冲区；计算任务则从该缓冲区中取出数据并进行计算。
试写出利用信号量机制实现两者共享单缓冲区的同步算法。
Var Sempty，Sfull: semaphore:= 1,0BeginParbeginCollection:beginrepeat采集一个数据；wait(Sempty);数据放入缓冲区；signal(Sfull);untill false;end;Compute:beginrepeatwait(Sfull);从缓冲区取出数据;signal(Sempty);计算;` until false;end;ParendEnd2、有一阅览室，共有100个座位。
读者进入时必须先在一种登记表上登记，该表为每一座位列一个表目，包括座号和读者姓名。
读者离开时要注销掉登记内容。
试用wait和signal原语描述读者进程的同步问题。
var mutex, readcount :semaphore := 1,100; BeginParbeginProcess Reader:beginrepeatwait(readcount);wait(mutex);<填入座号和姓名完成登记>；signal(mutex);<阅读>wait(mutex)<删除登记表中的相关表项，完成注销>signal(mutex);signal(readcount);until false;end;parend;End;1）、桌上有一空盘，只允许放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子；女儿专吃盘中的苹果，儿子专吃盘中的桔子；试用wait 和signal原语实现爸爸、妈妈、女儿、儿子之间的同步问题。
var Sempty, Sapple, Sorange,: semaphore:= 1,0,0; beginparbeginFather: beginrepeatwait(Sempty);<put apple in tray>;signal(Sapple);until false;end;Mother: beginrepeatwait(Sempty);<put orange in tray>;signal(Sorange);until false;end;Son: beginrepeatwait(Sorange);<take orange>;signal(Sempty);until false;end;Daughter: beginrepeatwait(Sapple);<take apple>;signal(Sempty);until false;end;parend;end;1、在4×100米接力赛中，4个运动员之间存在如下关系，运动员1跑到终点把接力棒交给运动员2；运动员2一开始处于等待状态，在接到运动员1传来的接力棒后才能往前跑，他跑完100米后交给运动员3，运动员3也只有在接到运动员2传来的棒后才能跑，他跑完100米后交给运动员4，运动员4接到棒后跑完全程。
13. 对于生产者—消费者问题，假设缓冲区是无界的，试用信号灯与PV操作给出解法。
答：由于是无界缓冲区，所以生产者不会因得不到缓冲区而被阻塞，不需要对空缓冲区进行管理，可以去掉在有界缓冲区中用来管理空缓冲区的信号量及其PV操作。
semaphore mutex_in=1;
semaphore mutex_out=1;
semaphore empty=0;
int in=0，out=0;
生产者活动：
while(1){
produce next product;
P(mutex_in);
add the product to buffer[in]; in++;
v(mutex_in);
V(empty);
} 消费者活动：
while(1){
P(empty);
P(mutex_out);
take the product from buffer[out]; out++;
V(mutex_out);
}
14. 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:
-M≤A物品数量－B物品数量≤N
其中M和N为正整数。
试用信号灯和PV操作描述A、B两种物品的入库过程。
答：已知条件 -M≤A物品数量－B物品数量≤N 可以拆成两个不等式，即
A物品数量－B物品数量≤N，
B物品数量－A物品数量≤M。
这两个不等式的含义是：仓库中A物品可以比B物品多，但不能超过N个；Ｂ物品可以比A 物品多，但不能超过M个。
semaphore a=n;
semaphore b=m;
void main(){
createprocess(A,…);
createprocess(B,…);
}
A物品入库：void A(){ while(1){
P(a);
A物品入库; V(b);
}
}B物品入库：void B(){ while(1){
P(b);
B物品入库; V(a);
}
}
15. 试用信号灯与PV操作实现司机与售票员之间的同步问题。
设公共汽车上有一个司机和一个售票员，其活动如下图
所示。
v1.0 可编辑可修改
为了安全起见，显然要求: (1)关车门后方能启动车辆；(2)到站停车后方能开车门。
亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。
解：如果进程P2尚未推进到②处时，进程P1已经推进到①处，则P1应等待直到P2推进到②处为止；同样，如果进程P1尚未推进到③处时，进程P2已经推进到④处，则P2应等待直到P1推进到③处为止。
如果进程P1在①处发生了等待，则当进程P2执行到②处时应将P1唤醒；同样，如果进程P2在④处发生了等待，则当进程P2执行到③处时应将P1唤醒。
用信号量和P、V操作解决这一问题，需要定义两个信号量，一个信号量start表示是否允许司机启动车辆，另一个信号量open表示是否允许售票员开车门。
初始状态是车停在始发站，车门开着，等待乘客上车。
因此，两个信号量的初值都是0。
semaphore start=0;
semaphore open=0;
司机的活动: P1: do{
P(start); 启动车辆;正常行车;到站停车; V(open);售票员的活动: P2: do{
关车门;
V(start);
售票;
P(open);
开车门;
}while (1);}while (1);
16. 设有A、B、C三组进程，它们互斥地使用某一独占型资源R，使用前申请，使用后释放。
资源分配原则如下:
(1) 当只有一组申请进程时，该组申请进程依次获得R；
(2) 当有两组申请进程时，各组申请进程交替获得R，组内申请进程依次获得R；
(3) 当有三组申请进程时，各组申请进程轮流获得R，组内申请进程依次获得R。
试用信号灯和PV操作分别给出各组进程的申请活动程序段和释放活动程序段。
解：
int free=1;
设自行车生产线上有一只箱子，其中有N个位置(N≥3)，每个位置可存放一个车架或一个车轮; 又设有三个工人，其活动分别为:
工人1活动：do {
加工一个车架;车架放入箱中; }while(1)工人2活动：
do {
加工一个车轮;
车轮放入箱中;
}while(1)
工人3活动：
do {
箱中取一车架;
箱中取二车轮;
组装为一台车;
}while(1)
试分别用信号灯与PV操作、管程、会合实现三个工人的合作，要求解中不含死锁。
解：用信号灯与PV操作实现三个工人的合作，管程与会合解法可仿照给出。
首先不考虑死锁问题，工人1与工人3、工人2与工人3构成生产者与消费者关系，这两对生产/消费关系通过共同的缓冲区相联系。
从资源的角度来看，箱子中的空位置相当于工人1和工人2的资源，而车架和车轮相当于工人3的资源。
定义三个信号灯如下：semaphore empty=N;
一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。
试用信号灯和PV操作写出南、北两岸过桥的同步算法。
解：桥上可能没有人，也可能有一人，也可能有两人。
(a) 两人同时过桥(b) 两人都到中间(c) 南(北)来者到北(南)段
共需要三个信号量，load用来控制桥上人数，初值为2，表示桥上最多有2人；north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。
semaphore load=2;
semaphore north=1;
semaphore south=1;
tosouth(){ P(load);
P(north);过北段桥;tonorth(){ P(load);
P(south);过南段桥;
到桥中间; V(north); P(south);过南段桥;到达南岸V(south); V(load); }到桥中间V(south); P(north);过北段桥;到达北岸V(north); V(load); }
19.某寺庙，有小和尚、老和尚若干．庙内有一水缸，由小和尚提水入缸，供老和尚饮用。
水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。
水取自同一井中，水井径窄，每次只能容纳一个水桶取水。
设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。
semaphore empty=30;
设系统中有5台类型相同的打印机，依次编号为1～5。
又设系统中有n个使用打印机的进程，使用前申请，使用后释放。
每个进程有一个进程标识，用于区别不同的进程。
每个进程还有一个优先数，不同进程的优先数各异。
当有多个进程同时申请时，按照进程优先数由高到低的次序实施分配。
试用信号灯和PV操作实现对于打印机资源的管理，即要求编写如下函数和过程:
(1) 函数 require(pid，pri): 申请一台打印机。
参数pid为进程标识，其值为1到n的整数; pri为进程优先数，其值为正整数; 函数返回值为所申请到打印机的编号，其值为1到5的整数;
(2) 过程 return(prnt): 释放一台打印机。
参数prnt为所释放打印机的编号，其值为1
到5的整数。
解：
#define N 5
bool flag[N+1];//flag[0]表示可用打印机数,
//flag[i]表示第i号打印机的状态（1<=i<=N），0表示占用，1表示空闲PCB *queue=NULL;//进程阻塞队列
semaphore mutex_flag=1;//用于对flag数组的互斥操作
semaphore mutex_queue=1;//用于对阻塞队列的互斥操作
process(int i,int priority){
int print;
print=require(i,priority);
use print;
return(print);
}
int require(int pid,int priority){
P(mutex_flag);
if(flag[0]>0){
flag[0]--;
for(int i=1;i<N+1;i++)
if(flag[i]==1){
flag[i]=0;
break;
}
V(mutex_flag);
return i;
}
else{
V(mutex_flag);
p(mutex_queue);
将进程pid按其优先数插入到等待队列queue中；V(mutex_queue);
}
}
return(int print){
P(mutex_flag);
if(queue==NULL){
flag[0]++;
flag[print]=1;
V(mutex_flag);
}
else{
V(mutex_flag);
p(mutex_queue);
将print分配给queue队首进程；
queue下移；
V(mutex_queue);
}
}。
