【操作系统原理】第三章课后习题

前言

• 课本： 操作系统原理（第五版）[费翔林，骆斌编著]
• 习题： 主要习题内容是第一章到第六章，具体内容如下表

习题三思考题

1. 试述顺序程序设计的特点以及采用顺序程序设计的优、缺点

解：程序顺序执行与其速度无关，即程序的最终输出仅与初始输人数据有 关, 而与时间无关。顺序程序设计具有的顺序性、封闭性、确定性和可再现性表明程序及程序的执行 (计算) 是一一对应的，这为程序的编制和调试带来很大方便，缺点是计算机系统效率不高。

2. 试述并发程序设计的特点以及采用并发程序设计的优、缺点

解：并发程序的实质是处理器在几个程序之间的多路复用，并发是对有限物理资源强制行使多用户共享，消除计算机部件之间的互等现象，好处是能提高系统资源利用率，但是程序的并发执行产生资源共享的需求，从而使程序失去封闭性、 顺序性、确定性和可再现性，除此之外 CPU 需要处理很多额外的工作如调度执行，进程挂起，进程等待等。

7. 解释进程的竞争关系和协作关系

解：

• 竞争关系：系统中同时存在多个交互式进程，它们共享一套计算机系统资源，使得多个进程因共享资源而产生交互和制约关系这是间接制约关系，又称互斥关系，由于竞争资源的独立进程之间并不交换信息，一个进程的执行可能影响到竞争资源的其他进程。资源竞争会引发两个控制问题, 一是死锁 (deadlock)， 二是饥饿 (starvation)。
• 协作关系：一个作业可涉及一组并发进程，它们为了完成共同任务需要分工协作由于程都独立地以不可预知的速度推进，需要相互进程在某些关键点上协调各自的工作。当其中一个进程到达关键点后，若同伴进程没有完成则阻塞自己， 需等待协作者发来信号或消息后方被唤配并继续执行。

8. 试述进程的互斥和同步两个概念之间的异同

解：

• 相同：进程在互斥和同步的时候均要有一方处于阻塞（等待）的状态，也就 是只有一个进程在占用 CPU 资源，进程互斥是一种特殊的进程同步。
• 不同：互斥是更特殊的一种同步，同步需要按一定的次序来进行等待和协 调，而互斥则是逐次使用互斥共享资源。除此之外互斥进程不会交换信息，而同 步进程会交换信息。

9. 什么是临界区和临界资源? 临界区管理的基本原则是什么?

• 临界区：并发进程中与共享变量有关的程序段称为临界区 (critical section)。共享变量所代表的资源称为临界资源 (critical resource) 即一次仅能供一个进程使用的资源。
• 临界区管理的基本原则：1. 一次至多只有一个进程进入临界区内执行。2. 如果已有进程在临界区中, 试图进入此临界区的其他进程应等待。3. 进入临界区内的进程应在有限时间内退出, 以便让等待队列中的一个进程进入

22. 试述信号通信机制及其实现

解：信号通信机制：为了通过信号量传送信号, 进程可利用 P 和 V 两个特殊操作来发送和接收信号, 如果协作进程的相应信号仍未送到, 则进程被挂起直至信号到达为止。信号有一个产生、传递、捕获、释放的过程。在这个过程中主要的 工具是中断，利用中断来完成进程间的调度。

信号通信的实现：使用一般信号量、二值信号量来作为共享变量。具体实现 如下：

1. 每个进程 task_strut 结构中的 signal 域专门保存接收到的信号内核根据所发生的事件产生相应的信号并发送给接收进程。进程接收到信号时, 对应位设置为 1, 相当于“中断请求寄存器”的某位置位, 由于所发送的信号被置于接收进程的进程控制块中, 所以无论进程是否在内存, 总可以立即被记录。
2. 进程 task_struct 结构中的 blocked 是信号屏标记相当于“中断寄存器”。进程需要忽略某信号时就把对应位设置为 1。sigpending 标志指示在sigqueue 队列中是否有挂起的信号, 如果信号发送之后目标进程在睡眠就唤醒它, 让它接收和处理信号, 任何时候一种类型的信号至多只有一个信号挂起
3. 信号处理函数的人口存放在进程 task_struct 的 sigaction[ ] 数组中利用 sigac-tion 函数为进程设置信号处理函数。共有 64 个元素每个元素占 32 位信号的编号对应于数组下标, 数组元素的值是信号处理程序的人口地址。使用信号安装函数 signal(sig,void(* handler)) 来设定某信号的处理方法参数 sig 指出要设置处理方法的信号, 参数 handler 是一个处理函数。
4. 函数 sigaction(signo,act,oldact) 为指定信号设置处理函数 signo 指出接收信号的类型,act 是收到信号后希望调用信号处理函数地址,oldact 存放最近一次为信号 signo 定义的函数地址。为保持兼容性仍保留 signal 函数但功能上已被 sigaction 替代。
5. 函数 kill(pid,sig) 用来向指定的进程或进程组发送指定信号。当信号被发送时, 内核的工作是更新进程控制块的信号域, 并对与信号相关的数据结构进行操作, 如置位、屏蔽和清除等。pid 确定信号 sig 所发往的进程,sig 是信号类型由于这种信号要知道所发往进程的标识号, 所以信号发送通常在关系密切的进程之间进行。进程还可用 raise() 向自身发送信号。
6. 信号检测和响应总发生在系统空间。在中断或异常处理程序末尾, 当进程从内核态返回用户态之前, 或在处理运行进程所遇到的时钟中断结束之前, 或进程以 interruptible 状态进入等待队列之前 (若它已收到信号就不睡眠) 系统会调用内核函数 do_signal() 检查此进程是否已收到信号, 若是则执行 handle_signal() 让它返回用户态并转入信号处理程序执行。当信号处理结束后, 通过执行系统调用 sigreturn() 再次陷人内核, 内核做好善后工作后返回用户态, 从应用程序的断点继续执行。

25. 试述产生死锁的必要条件

解：系统产生死锁必定同时保持如下 4 个必要条件。

1. 互斥条件 (mutualexclusion): 临界资源是独占资源, 进程应互且排他地使用这些资源。
2. 有和等待条件 (holdand wait: 进程在请求资源得不到满足而等待时不释放已占有资源。
3. 不剥夺条件 (no preemption): 又称不可抢占已获资源只能由进程自愿释放, 不允许被其他进程剥夺
4. 循环等待条件 (circular wait): 又称环路条件, 存在循环等待链, 其中每个进程都在等待链中等待下一个进程所持有的资源, 造成这组进程处于永远等待状态。

27. 何谓银行家算法? 试述其基本思想

解：银行家算法是一个能够避免死锁的调度方法，它的基本思想如下，假设 CPU 的总资源为 M，被 N 个进程共享，每个进程在申请 CPU 资源的时候需要预先说明需要使用的资源量，并且在资源不足以全部分配给该进程的时候。通过分量 多次的提供给该进程，在进程运行后应该在有限时间内归还资源。若 N < M 则CPU 会允许该进程进入内存，若资源不足则会让进程进行等待，但在有限的时间里会保证其享有相应的 CPU 资源。

28. 解释: 进程-资源分配图、死锁判定法则、死锁定理

解：

• 进程-资源分配图：每个进程用一个圆圈来表示, 用有向边表示进程申请资源和资源被分配的情况。约定 P-R 为请求边, 表示进程 P 申请资源类反之,R 一 P 为分配边, 表示 R 类资源中的一个资源已被进程 P 占用, 故此有向边从方框内的某个黑圆点出发指向进程。如图一。

• 死锁判定法则：
  (1)如果进程-资源分配图中无环路此时系统没有发生死锁
  (2)如果进程-资源分配图中有环路且每个资源类中仅有一个资源则系统中发生死锁。此时, 环路是系统发生死锁的充分和必要条件, 环路中的进程就是死锁进程。
  (3)如果进程-资源分配图中有环路且所涉及的资源类中有多个资源则环路的存在只是产生死锁的必要条件而不是充分条件, 系统未必会发生死锁。
• 死锁定理：如果在进程-资源分配图中找出一个既不阻塞又与其他进程因请求资源相关联的进程, 它在有限的时间内有可能获得所需资源类中的资源而继续执行直到运行结束, 再释放其所占有的全部资源。这相当于消去进程-资源分配图中此进程的所有请求边和分配边, 使之成为孤立点。接着可使进程-资源分配图中另一个进程获得前面进程释放的资源而继续执行, 直到完成后释放其所占用的所有资源, 再次消除图中的若干请求边和分配边。如此往复, 经过一系列简化后, 若能消去图中的所有边, 使所有进程成为孤立点, 则此进程-资源分配图是可完全简化的; 否则称此图是不可完全简化的。系统处于死锁状态的充分条件是: 当且仅当此状态的进程-资源分配图是不可完全简化的, 这一充分条件称为死锁定理。

习题三应用题

3.有两个优先级相同的进程 \(P_1\) 和\(P_2\) 其各自执行的操作如下信号量 \(S_1\) 和 \(S_2\) 的初值均为 0 试问 \(P_1P_2\) 并发执行后,x 的值各为多少?

解：X 的值各为 15 和 10。

4. 现有语句如下，试用 Bernstein 条件证明语句 S2 和 S3 可以并发执行, 而语句 S3 和S4 不可并发执行。

•S1 : a = 5 −x;
•S2 : b = a∗x;
•S3 : c = 4 ∗x;
•S4 : d = b + c;
•S5 : e = d + 3

解：证明如下图：

8. 设在公共汽车上司机和售票员的活动分别如下，在汽车不断地到站、停车、行驶的过程中这两个活动之间有什么同步关系? 用信号量和 PV 操作实现其同步

司机的活动: 启动车辆, 正常行车, 到站停车。
售票员的活动: 关车门, 售票, 开车门

解：售票员关了车门才能启动车辆，正常行驶后车辆到站停车，由售票员开车门，售完票后在关车门形成一个循环。如下所示：

semaphore S0=0;// 允 许 司 机 开 车
semaphore S1=0;// 允 许 售 票 开 开 门

d r i v e r ( ) ;
waiter ( ) ;

p r o c e s s Driver (){
	while ( true ){
 		P( S1 ) ;
 		start ( ) ;
 		drive ( ) ;
 		stop ( ) ;
 		V( S1 ) ;
	}
}

process waiter (){
	while ( true ){
		P( S0 ) ;
		open ( ) ;
		sell ( ) ;
		close ( ) ;
		V( S0 ) ;
	}
}

16. 一个经典的同步问题: 吸烟者问题。三名吸烟者在同一个房间内, 还有一位香烟供应者。为了制造并抽掉香烟, 每位吸烟者需要三样东西: 烟草、纸和火柴, 供应者有丰富的货物提供。三位吸烟者中, 第一个人有自己的烟草, 第二个人有自己的纸, 第三个人有自己的火柴。供应者随机地将两样东西放在桌子上, 允许一位吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者 供应者再把两样东西放在桌子上, 唤醒另一位吸烟者。试采用信号量和 PV 操作

解：具体代码如下

int i=0;  
semaphore S0=0;//定义第一个所需要的资源纸和火柴
semaphore S1=0;//定义第二个所需要的资源烟草和火柴
semaphore S2=0;//定义第三个所需要的资源烟草和纸
semaphore F=0;//定义信号量表示抽烟是否完成  


process Offer(){  
    if(i==0)  
        V(S0); 
    else if(i==1)  
        V(S1);  
    else if(i==2)  
        V(S2);
    put();  // 供应商摆放资源
    P(F);  
    i=(i+1)%3;
}  
process Customer(){
    while(1){  
        P(S[k]); //申请自己所需的资源  
        take();
        V(F);  
    }  
}  

17. 有4个进程\(P_i(i=0,1,...,3)\)和4个信箱\(M_j(j=0,1,...,3)\),进程间借助相邻的信箱传递消息即\(P_i\)每次从\(M_i\)中取出一条消息,经加工后送入\(M(i+11)mod4\),其中\(M_0M_1M_2M_3\)分别可存放3、3、2、2条消息。在初始状态下,\(M_0\)装了三条消息,其余为空。试以 PV 操作为工具写出\(P_i(i=0,1,..,3)\)的同步工作算法。

解：解法代码如下

semaphore mutex0=mutex1=mutex2=mutex3 = 0;
semaphore empty0=0, empty1=3, empty2=empty3=2; //信箱剩余空间
semaphore full0=3, full1=full2=full3=0; //信箱剩余信件数

int index; //信箱的位置，初始均为0

cobegin
process P0( ) {
    while(true) {
        P(full0);
        P(mutex0);
        takOut();//从信箱中取出消息
        index = ( index + 11 ) % 4;
        V(mutex0);
        V(empty0);
        process();//加工邮件
        // 将要把加工的邮件发给相应的邮箱，将其剩余空间减一
        P(empty<index>); 
        P(mutex<index>);
        send();//发送其邮件
        V(mutex<index>);
        V(full<index>);
    }
} 
.... //其他进程与其类似
process Pi(){

}

23. 设当前的系统状态如下,此时\(Available =(1,1,2)\)

1. 计算各个进程还需要的资源数 Cki-Aki。
2. 系统是否处于安全状态,为什么?
3. 进程\(P_2\)发出请求向量 request2(1,0,1)系统能把资源分配给它吗?
4. 若在进程\(P_2\)申请资源后,\(P_1\)发出请求向量request1(1,0,1),系统能把资源分配给它吗?
5. 若在进程\(P_1\)申请资源后,\(P_3\)发出请求向量request3(0,0,1),系统能把资源分配给它吗?

解：各小问解答如下：

1. P1:(2,2,2);P2:(1,0,2);P3:(1,0,3);P4:(4,2,0)
2. 处于安全状态，因为存在一个安全序列P2P1P3P4。
3. 可以分配给它，\(request2(1,0,1) < Need(1,0,2) < Available(1,1,2)\)并且存在P2P1P3P4的安全序列。
4. 即使\(request1(1,0,1) < Need(2,2,2)\)但是\(request1(1,0,1) < Available(1,1,2) - request2(1,0,1) = Available(0,1,1)\)，故不分配给它。
5. 因为\(request3(0,0,1) < Need(1,0,3)\) 且 \(Available(1,1,2) - request1(1,0,1) = Available(0,1,1) > request3(0,0,1)\)，故能分配给它。

24. 系统有A、B、C、D共4种资源在某时刻进程\(P_1、P_2、P_3\)和\(P_4\)对资源的有和需求情况如下表所示,试解答下列问题。

1. 系统此时处于安全状态吗?
2. 若此时进程\(P_1\)发出请求request1(1,2,2,2)系统能分配资源给它吗?为什么?

解：

1. 系统此时处于安全状态，因为存在安全序列P0P3P1P2P4。
2. 虽然\(request1(1,2,2,2) < Available(1,6,2,2)\)但是\(P_1\)在一开始的时候并没有声明需要请求D资源，也就是\(Claim_{P0}.d = 0\)，所以系统不会分配资源给它不分配给它。

25. 把死锁检测算法用于下面的数据

1. 系统此时处于安全状态吗?
2. 若第二个进程提出资源请求request2(0,0,1,0)系统能分配资源给它吗?
3. 若第五个进程提出资源请求request5(0,0,1,0)系统能分配资源给它吗?

解：

1. 系统此时处于安全状态，因为存在安全序列P3P0P1P2P4。
2. \(request2(0,0,1,0) < Need(0,1,1,2)\)，并且此时\(Available = (1,0,2,0) - (0，0，1，0) = (1,0,1,0)\)，并且此时也存在一个安全序列P3P0P1P2P4，故系统会分配资源给它。
3. 虽然\(request5(0,0,1,0) < Need(2,1,1,0)\)，但是现在的\(Available = (1,0,1,0) - (0,0,1,0) = (1,0,0,0)\)，找不到一个安全序列，所以系统现在是处于不安全模式，因此系统不会给它分配资源。

30. 某系统有\(R_1\)设备三台,\(R_2\)设备4台,它们被P1P2P3和P4进程共享,且已知这4个进程均按以下顺序使用设备：\(\to\) 申请\(R_1\) \(\to\) 申请\(R_2\) \(\to\) 申请\(R_1\) \(\to\) 释放\(R_1\) \(\to\) 释放\(R_2\) \(\to\) 释放\(R_1\)

系统运行过程中可能产生死锁吗?为什么?
若有可能请列举一种情况并画出表示此死锁状态的进程-资源图。

解：

1. 会发生死锁，因为各个进程所需要的\(R_1\)设备为2台\(R_2\)设备为1台，\(R_2\)足够但是\(R_1\)不够，所以可能会发生死锁，其中一种情况是P1、P2、P3均申请了一台\(R_1\)和一台\(R_2\)，这时候三个进程均等待其他进程释放\(R_1\)，从而形成死锁。
2. 下图为一种死锁状态的进程-资源图
   

38. 桌上有一只盘子,最多可以容纳两个水果,每次仅能放入或取出一个水果。爸爸向盘子中放苹果(apple),妈妈向盘子中放橘子(orange),两个儿子专等吃盘子里的橘子,两个女儿专等吃盘子里的苹果。试用信号量和 PV 操作来实现爸爸妈妈儿子女儿间的同步与斥关系。

解：下面为具体的解法

semaphore empty = 2; //定义空盘子
semaphore appleFull=0;//定义盘子里面苹果可用数
semaphore orangeFull=0;//定义盘子里面橘子可用数
semaphore mutex=1;//互斥信号


process Dad(){  
 while(true){
  P(empty);
  P(mutex);
  putApple();//往盘子中放苹果
  V(appleFull);
  V(mutex);
 }
}  
process Mom(){
 while(true){
  P(empty);
  P(mutex);
  putOrange();//往盘子中放橘子
  V(orangeFull);
  V(mutex);
 }
}
process Daughter1(){
 while(true){
  V(empty);
  P(mutex);
  eatApple();//吃苹果
  P(appleFull);
  V(mutex);
 }
}
process Daughter2(){
 //与daughter1相同
}
process Son1(){
 while(true){
  V(empty);
  P(mutex);
  eatOrange();//吃橘子
  P(orangeFull);
  V(mutex);
 }
}
process Son2(){
 //与son1相同

39. 一组生产者进程和一组消费者进程共享9个缓冲区每个缓冲区可以存放一个整数。生产者进程每次一次性地向三个缓冲区中写人整数消费者进程每次从缓冲区取出一个整数。请用信号量和PV操作写出能够正确执行的程序。

semaphore empty = 9; //定义空缓冲区
semaphore full=0;//定义缓冲区可用数
semaphore mutex=1;//互斥信号


process producer(){  
 while(true){
  //请求三个空缓冲区
  P(empty);
  P(empty);
  P(empty);
  P(mutex);
  produce();//生产
  V(full);
  V(full);
  V(full);
  V(mutex);
 }
}  
process consumer(){
 while(true){
  V(empty);
  P(mutex);
  consume();//消费
  P(full);
  V(mutex);
 }
}

41.下述流程是解决两进程互斥访问临界区问题的一种方法。试从互斥(mutualexclusion)空闲让进(progress)有限等待(bounded waiting)等三方面讨论其正确性。如果它是正确的,则证明之;如果它不正确,请说明理由。

解：

1. 互斥：该流程并不能实现互斥访问临界区，存在这样一种情况：a.P1执行完c1 = 1-c2 = 0，c2=1进入临界区；b.后跳转到P2执行，c2 = 1 - c1 = 1，c1 = 0准备进入临界区；c.转到P1上继续执行，此时c1 =1；c2 = 1;d.再次跳转到p2，因为c1 = 1，c2 = 1，故直接进入临界区；e.回到p1，此时也能直接进入临界区。
2. 空闲让进：该流程能够实现空闲让进，因为使用完临界区后会将c1和c2初始化为1，这样在进行进程跳转后就能访问到临界区了。
3. 有限等待：该流程可能不能完成有限等待，因为如果一个进程在临界区里执行，那么它c1或者c2就会一直为0，永远不会为1，所以另一方则会进入无限的等待。

43. 现有三个生产者\(P_1\)、\(P_2\)、\(P_3\),他们都要生产橘子汁,每个生产者都已分别购得两种不同的原料,待购齐第三种原料后就可配制成橘子汁装瓶出售。有一供应商能源源不断地供应糖、水、橘子精但每次只拿出一种原料放入容器中供应给生产者。当容器中有原料时,需要这种原料的生产者可以取走,当容器空时供应商又可放入一种原料。假定:生产者\(P_1\)已购得糖和水;生产者\(P_2\)已购得水和橘子精;生产者\(P_3\)已购得糖和橘子精。试用信号量与 PV 操作,写出供应商和三个生产者之间能正确同步的程序。

int i=0;  
semaphore S0=0;//定义P1所需要的橘子精
semaphore S1=0;//定义P2所需要的糖
semaphore S2=0;//定义P3所需要的水
semaphore finish=1;//定义信号量容器是否空


process Offer(){  
    if(i==0)  
        V(S0); 
    else if(i==1)  
        V(S1);  
    else if(i==2)  
        V(S2);
    put();  // 供应商摆放资源
    P(finish);  
    i=(i+1)%3;
}  
process producer(){
    while(1){  
        P(S[k]); //申请自己所需的资源  
        take();
        produce();
        V(finish);  
    }  
}  

50. 某寺庙有小和尚和老和尚若干,水缸一只,由小和尚提水入缸供老和尚饮用。水缸可容水 10桶,水取自同一口水井中。水井径窄,每次仅能容纳一只水桶取水,水桶总数为三个。每次放入、取出的水量仅为1桶,而且不能同时进行。试用一种同步工具写出小和尚和老和尚放入水、取水的活动过程。

解：

semaphore bucketEmpty = 3; //定义空水桶缓冲区
semaphore bucketFull = 0; //定义满水桶缓冲区
semaphore tankEmpty = 10; //定义空水缸可容水桶缓冲区
semaphore mutex=1;//互斥信号


process takeInWater(){  
 while(true){
  P(bucketEmpty);
  P(mutex);
  takeInWater();//把水装入水桶
  V(bucketFull);
  V(mutex);
 }
}  

process takeInTank(){  
 while(true){
  P(bucketFull);
  takeInWater();//把水桶里的水装入水缸
  V(bucketEmpty);
  P(tankEmpty);
 }
} 

process sentTankToOldMonk(){
 while(true){
  if(tankEmpty == 0){
	sentTankToOldMonk();
	tankEmpty = 10;
  }
 }
}

结束语

如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！