操作系统第二章作业讲解

操作系统第二章作业讲解

第二章 习题讲解

1、进程之间存在着哪几种制约关系？各是什么原因引起的？下列活动分别属于哪种制约关系？

（1）若干同学去图书馆借书；（2）两队举行篮球比赛；（3）流水线生产的各道工序；（4）商品生产和社会消费。

答：进程之间存在着直接制约与间接制约这两种制约关系，其中直接制约（同步）是由于进程间的相互合作而引起的，而间接制约（互斥）则是由于进程间共享临界资源而引起的。

（1）若干同学去图书馆借书，是间接制约，其中书是临界资源；（2）两队举行篮球比赛，是间接制约，其中蓝球是临界资源；（3）流水线生产的各道工序，是直接制约，各道工序间需要相互合作，每道工序的开始都依赖于前一道工序的完成；（4）商品生产和社会消费，是直接制约，两者也需要相互合作：商品生产出来后才可以被消费；商品被消费后才需要再生产。

2、试写出相应的程序来描述下图所示的前趋图

var a,b,c,d,e,f:semaphore:=0,0,0,0,0,0;

begin S1; signal(a); signal(b); signal(c); end;

begin wait(a); S2; end;

begin wait(b); S3; signal(d); end;

begin wait(c); S4; end;

begin wait(d); S5; signal(e); signal(f); end;

begin wait(e); S6; end;

begin wait(f); S7; end;

3、已知一个求值公式(A2＋3B)/(B+5A)，若A、B已赋值，试画出该公式求值过程的前趋图，并使用信号量描述这些前趋关系。

答：根据求值公式，假设：

S1: X1=A*A

S2: X2=3*B

S3: X3=5*A

S4: X4=X1+X2

S5: X5=B+X3

S6: X6=X4/X5

var a,b,c,d,e:semaphore:=0,0,0,0,0;

begin S1; signal(a); end;

begin S2; signal(b); end;

begin S3; signal(c); end;

begin wait(a); wait(b); S4; signal(d); end

begin wait(c); S5; signal(e); end

begin wait(d); wait(e); S6; end

4、桌上有一只能容纳一个水果的盘子；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果，1）试用信号量实现他们的同步关系；2）如果有两个家庭的爸爸、妈妈、儿子、女儿和二只盘子呢？会需要专门的实现吗？

var empty,apple,orange:semaphore:= 1,0,0;

说明：empty与apple表示盘子为空与盘子中放入了苹果，用于表示爸爸与女儿间的同步关系；empty与orange表示盘子为空与盘子中放入了桔子，用于表示妈妈与儿子间的同步关系；

答案：1）使用记录型信号量

2）使用记录型信号量

var mutex,empty,apple,orange:semaphore:=1,2,0,0;

dish: array[0,1] of fruit;

in, out:integer:= 0,0;

5、试用信号量实现课件92页，司机与售票员进程的同步关系

var stop, door :semaphore:=0,0;

6、试用信号量解决读者—写者问题，使得写者与读者优先级根据到达顺序确定。

1）典型错误代码讲解：不增加任何信号量

Var rmutex, wmutex:semaphore∶= 1,1;

Readcount:integer ∶ = 0;

begin

parbegin

Reader:begin

repeat

wait(rmutex);

if Readcount=0 then wait(wmutex);

Readcount∶ = Readcount+1;

signal(rmutex);

…

perform read operation;

…

wait(rmutex);

Readcount∶= Readcount-1;

if Readcount=0 then signal(wmutex);

signal(rmutex);

until false;

end

writer:begin

repeat

if readcount>0 then wait(rumtex);

wait(wmutex);

perform write operation;

signal(rmutex);

signal(wmutex);

until false;

end

parend

end

到达序列：R1, R2, W1, R3, R4, W2

产生死锁

2）学习指导与题解上的解题思路

答：为使写者优先，可在原来的读优先算法基础上增加一个初值为1的信号量S，使得当至少有一个写者准备访问共享对象时，它可使后续的读者进程等待写完成。初值为0的整型变量writecount用来对写者进行计数；初值为1 的互斥信号量mutex用来实现多个写者对writecount的互斥访问。读者与写者进程算法描述如下：

var S, mutex, rmutex, wmutex: semaphore:=1,1, 1,1;

writecount, readcount: integer:=0,0;

reader: begin

repeat

wait(S);

wait(rmutex);

if readcount=0 then wait(wmutex);

readcount:=readcount+1;

signal(rmutex);

signal(S);

perform read operation;

wait(rmutex);

readcount:=readcount-1;

if readcount=0 then signal(wmutex);

signal(rmutex);

until false

end

writer: begin

repeat

wait(mutex);

if writecount=0 then wait(S);

writecount:=writecount+1;

signal(mutex);

wait(wmutex);

perform write operation;

signal(wmutex);

wait(mutex);

writecount:=writecount-1;

if writecount=0 then signal(S);

signal(mutex);

until false

end

到达序列：R1, R2, W1, R3, R4, W2

3）改写上述代码，真正实现读写平等策略

var S, rmutex, wmutex: semaphore:=1, 1,1;

readcount: integer:= 0;

reader: begin

repeat

wait(S);

wait(rmutex);

if readcount=0 then wait(wmutex);

readcount:=readcount+1;

signal(rmutex);

signal(S);

perform read operation;

wait(rmutex);

readcount:=readcount-1;

if readcount=0 then signal(wmutex);

signal(rmutex);

until false

end

writer: begin

repeat

wait(S);

wait(wmutex);

perform write operation;

signal(wmutex);

signal(S);

until false

end

到达序列：R1, R2, W1, R3, R4, W2

7、试说明PCB的作用，为什么说PCB是进程存在的唯一标志？（课本第7题）

答：进程控制块的作用，是使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基本单位，即一个能与其他进程并发执行的进程。

在创建进程时，系统将为它配置一个PCB；在进行进程调度时，系统将根据PCB中的状态和优先级等信息来选择新进程，然后将老进程的现场信息保存到它的PCB中，再根据新进程PCB中所保存的处理机状态信息来恢复运行的现场；执行中的进程，如果需要访问文件或者需要与合作进程实现同步或通信，也都需要访问PCB；当进程因某种原因而暂停执行时，也必须将断点的现场信息保存到它的PCB中；当进程结束时，系统将回收它的PCB。可见，在进程的整个生命周期中，系统总是通过其PCB对进程进行控制和管理，亦即，系统是根据其PCB而不是任何别的什么而感知到进程的存在，所以说，PCB是进程存在的唯一标志。

8、同步机构应遵循哪些基本准则？为什么？（课本第18题）

答：空闲让进、忙则等待、有限等待、让权等待。这样才能保证多个进程对临界资源的互斥访问，不会造成系统的混乱、程序执行结果的不确定性或死锁的产生。

9、试从物理概念上说明记录型信号量wait和signal。（课本第19题）

答：一个信号量通常对应一类临界资源，在使用前，信号量必须经过定义并赋适当的初值。每次对它进行wait操作意味着申请一个单位的该资源，signal操作操作意味着归还一个单位的该类资源。当S.value>0时，它的值表示系统中该类资源当前可用的数目；S.value<=0时，表示该类资源已经分配完毕，其绝对值表示系统中因申请资源而阻塞在S.L队列上的进程数目。

10、在生产者—消费者问题中，如果缺少了signal(full)或signal(empty)，对执行结果将会有何影响？（课本第23题）

答：如果生产者进程中缺少了signal(full)，生产者一开始是不断往缓冲池送消息，而消费者一开始就因为full为0而处于阻塞状态，当所有缓冲区装满之后，由于empty由n减为0，而消费者已经阻塞，生产者也会因为wait(empty)而处于阻塞状态。产生死锁。

消费者进程中缺少了signal(empty)，缓冲区指针in从0指向了n-1后，生产者就会因为执行wait(empty)处于阻塞状态；生产者阻塞后，消费者消费掉所有的产品，即缓冲区指针out从0指向了n-1后，也会因为执行wait(full) 处于阻塞状态。产生死锁。

11、我们为某临界资源设置一把锁W，当W=1时表示关锁；当W=0时表示锁已经打开，试写出开锁和关锁原语，并利用它们去实现互斥。（课本第25题）

答：相应的关锁原语lock(W)和开锁原语unlock(W)可描述如下：

lock(W): while W=1 do no-op;

W:=1;

unlock(W): W:=0;

在利用关锁原语和开锁原语实现进程互斥时，可将临界区CS放在其间，即：

lock(W);

CS;

unlock(W);

12、当前有哪几种高级通信机制？（课本第34题）

答：有三种：共享存储器系统、消息传递系统、管道通信系统

13、试从调度性、并发性、拥有资源及系统开销方面对进程和线程进行比较。（课本第38题）

答：进程和线程之间在调度性、并发性、拥有资源及系统开销方面的比较如下：

1）调度性：在传统的OS中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。在引入线程的OS中，则把线程作为调度和分派的基本单位，而把进程作为资源拥有的基本单位。

2）并发性：在引入线程的OS中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而它比传统的OS具有更好的并发性

3）拥有资源：在两种OS中，拥有资源的基本单位都是进程。线程除了一点在运行中必不可少的资源外，本身基本不拥有系统资源，但它可以访问其隶属进程的资源。

4）开销：由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、I/O设备等。进程切换时所要保存和设置的现场信息也要明显多于线程。因此，OS在创建、撤消和切换进程时所付出的开销将明显地大于线程。由于隶属于同一个进程的多个线程共享同一地址空间和该进程的所有已找开文件，从而使它们之间的同步和通信的实现也比进程更容易。

14、何谓用户级线程和内核支持线程？（课本第41题）

答：内核支持线程是在内核支持下实现的，即每个线程的线程控制块设置在内核中，所有对线程的操作（如创建、撤消和切换等），都是通过系统调用，由内核中的相应处理程序完成。设置了内核支持线程的系统，其调度是以线程为单位进行的。

用户级线程仅存在于用户空间中，即每个线程的控制块设置在用户空间中，所有对线程的操作也在用户空间中完成，而无需内核的帮助。设置了用户级线程的系统，其调度仍是以进程为单位进行的。

本文来源：https://www.2haoxitong.net/k/doc/6cc6991477a20029bd64783e0912a21615797f5c.html