c++ pipe 同步互斥_答疑（进程同步、互斥、死锁）之一-蒲公英云

问题1： 内核支持线程与用户级线程最本质的区别是什么？答：内核支持线程( Kernel Supported threads, KST)。对于一切的进程，无论是系统进程还是用户进程，进程的创建和撤销，以及I/O操作都是利用系统调用进入到内核，由内核处理完成，所以说在KST下，所有进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。内核空间实现还为每个内核支持线程设置了一个线程控制快，内核是根据该控制快而感知某个线程是否存在，并加以控制。用户级线程(UserLevelThreads ，ULT)。用户进程ULT仅存在于用户空间中。对于这种线程的创建、撤销、线程之间的同步和通信等功能，都无需系统调用来实现。对于同一进程的线程之间切换仍然是不需要内核支持的。所以呢，内核也会是完全不会知道用户级线程的存在。 问题2：有两个并发进程P1、P2，它们共享同一个变量x，其程序代码如下： P1( ) { x=1; y=2; if (x>0) z=x+y; else z=x*y; print z; } P2( ) { x=-1; a=x+3; x=a+x; b=a+x; c=b*b; print c; } 问：(1)可能打印出的z值是哪些？(假设每条赋值语句是一个原子操作)

(2)可能打印出的c值有哪些？

答：我们先来分析z的输出值。进程P2的前3行代码会影响进程P1的输出结果。下面具体分析。 (1) 分析可能打印出的z值。 1) 把P2的前3行代码看作整体，则不论这3行代码在P1的何处执行，输出z的值都为3； 2) 如果P2的x=-1在if(x>0) 之前执行，则z=2*x; 此处的x的可能是-1，也可能是1(a=x+3;x=a+x;执行后)，所以输出z的值可能是-2或2； 3) 如果P2的x=-1在if(x>0) 之后z=x+y之前执行，则输出z=1；在z=x+y之后执行，则输出2； 4) 如果P1的x=1在P2的x=-1之后a=x+3之前执行，P2的x=a+x在if(x>0)之前执行，则输出7； 5) 如果P1的x=1在P2的a=x+3之后x=a+x之前执行，P2的x=a+x在if(x>0)之前执行，则输出5。所以可能打印出z的值有-2，1，2，3， 5，7. (2) 分析可能打印的c值有哪些。 c的值主要受a和x值的影响。在执行P2的b=a+x之前，a的取值可能是2或4，当a的值为2时，x的值可能为1或3，当a的值为4时，x的值为5，所以b的可能取值为3，5，9，c的输出值可能为9，25，81.

问题3：在Lock程序实现方法中，为什么test&set这个方法是atomic的？

在学操作系统进程/线程互斥时学到Lock，老师说一般有这么几种实现方法，其中包括test&set：

test&set (&address) {

　　result = M[&address];

　　M[&address] = 1;

　　return result;

}

老师说前两行代码可以保证是atomic的，但我不太明白，假设M[&address]一开始的初始值是0，有两个线程同时试图获取这个锁。线程1将M[&address]的值(0)读取到result，就在此时，线程2也将M[&address]的值(0)读取到result，继而线程1和2分别将M[&address]设为1，最后，这两个线程的返回值都是0，岂不是两个线程都以为自己获取了锁？什么地方我理解错了？

答：老师给你展示的是伪代码, 主要目的是为了让你能够理解这个操作的具体含义。具体实现时，前两行代码可以用一条机器指令完成，从而保证M测试和设置的完整性。

比如在x86中有位测试并设置指令BTS和位测试并复位指令BTC，它们的格式是：

BTS OPRD1，OPRD2

BTC OPRD1，OPRD2

其中OPRD1是寄存器或存储器，OPRD2是寄存器或立即数。

BTS的功能是把操作数OPRD1的第OPRD2位送标志位CF，并且把该位置1。BTC的功能是把操作数OPRD1的第OPRD2位送标志位CF，并且把该位清0。

利用这两条指令实现两个并发进程P1、P2互斥使用临界资源的描述如下：

// 利用M的第0位实现互斥

进程P1 进程P2

   ……                      ……

L1:BTS M,0 L2: BTS M,0

  JC L1                       JC L2
  CS1                          CS2
  BTC M,0                   BTC M,0
   ……                          ……

变量M的初值为0，P1和P2利用变量M的第0位，实现了两个进程的互斥。指令 BTS M,0 执行的结果是将W的第0位送入标志位CF，并设置W的第0位为1。指令 BTC M,0 执行的结果是将W的第0位送入标志位CF，并设置W的第0位为0。例如，若进程P1已进入了临界区CS1，则W的第0位为1，当P2想进入临界区CS2时，要执行指令BTS M,0，获得标志位CF为1，此时P2执行指令JC L2时条件成立，转L2循环测试等待，直到P1退出临界区，并执行了BTC M,0指令后，将W的第0位清0，此时，P2才能进入临界区CS2。显然，通过这两条指令可实现进程之间的互斥。

问题4：(考研题目)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

cobegin { process 顾客 i { 从取号机获取一个号码；等待叫号；获取服务； } process 营业员 { while(TRUE) { 叫号；为客户服务； } } } coend

请添加必要的信号量和P、V(或 wait()、signal())操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

解：互斥资源：取号机(一次只允许一位顾客领号)，因此设一个互斥信号量mutex；

同步问题：顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量empty和full来实现这一同步关系。另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量service来完成这一同步过程。

semaphore mutex=1； //互斥使用取号机 semaphore empty=10； //空座位的数量 semaphore full=0； //已占座位的数量 semaphore service=0； //等待叫号 cobegin { process顾客i { P(empty)； P(mutex)；从取号机获得一个号； V(mutex)； V(full)； P(service)； //等待叫号获得服务； } process营业员 { while(TRUE) { P(full)； V(empty)； V(service)； //叫号为顾客服务； } } } coend

问题5：(考研题目)面包师有很多面包，由n个销售人员推销。每个顾客进店后取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号。试设计一个使销售人员和顾客同步的算法。

分析：顾客进店后按序取号，并等待叫号；销售人员空闲之后也是按序叫号，并销售面包。因此同步算法涉及到顾客与销售人员的同步，以及取号和叫号的互斥问题。我们使用两个变量 i和j分别记录当前的取号值和叫号值，并各自使用一个互斥信号量用于对i和j的进行访问和修改，使用buyer和seller两个信号量对顾客和销售人员之间的同步。 int i=0; // 取的号码 int j=0; // 叫的号码 semaphore mutex_i=1; // 共享变量i互斥 semaphore mutex_j=1; // 共享变量j互斥 semaphore buyer=0; // 顾客人数 semaphore seller=n; // 销售人数 Consumer(){ // 顾客进入面包店; p(mutex_i); // 取号 i++; V(mutex_i); // 取号结束 V(buyer); P(seller); 买面包; 离开; } Sell() { //销售 while(1){ P(buyer); P(mutex_j); //互斥访问j j++; 叫编号为j的顾客 V(mutex_j); //释放对j的访问卖面包给顾客j; 顾客离开; V(seller); } }

问题6. 一个生产进程和两个消费进程共享一个单缓冲区，缓冲区只能放一条消息，生产进程生产一条消息并向缓冲区写入，两个消费进程都要从缓冲区中取出这条消息消费，此过程循环往复，用信号量机制解决这三个进程间的同步问题。

解：该问题是“生产者—消费者”问题的变种，假设生产进程为P，两个消费者进程分别为C1和C2，缓冲区为B．这3个进程间存在以下的同步关系： (1) 进程P与进程C1和C2存在同步关系，当缓冲区B空闲时，进程P往缓冲区中写一条信息，当缓冲区不空时，C1和C2竞争读缓冲区B中的信息。当B不空时，P等待，当B空时，C1和C2等待。 (2) 进程C1和C2要等待P往缓冲区B里放入一条消息后，竞争读该消息。 (3) 3个进程都要互斥地使用缓冲区B。但由于使用同步信号量可以避免三个进程同时使用缓冲区，因此，无需使用互斥信号量。因此，仅需设置2个同步信号量即可：一个同步信号量为S0，初值为1，表示缓冲区B初始时为空；一个同步信号量为S1，初值为0，表示缓冲区B初始时无消息。 semaphore S0=1；//同步信号量，表示缓冲区空 semaphore S1=0；//同步信号量，表示缓冲区中的消息数 cobegin { // 生产者进程 P( ) { Lp: P(S0)； // 缓冲区空时，写信息 Write a message to Buffer； // 写信息到缓冲区中 V(S1)； // 缓冲区空时，写信息 goto Lp； // 写下一条信息 } //消费者C1 C1( ) { Lc1：P(S1) ; // 缓冲区中有消息吗？从缓冲区中去除消息消费； V(S0) ; // 释放缓冲区 goto Lc1 ; // 消费下一条消息 } //消费者C2 C2( ) { Lc2：P(S1) ; // 缓冲区中有消息吗？从缓冲区中去除消息消费； V(S0) ; // 释放缓冲区 goto Lc2 ; // 消费下一条消息 } coend 问题7.

这道题目来自《操作系统：精髓与设计原理》，该题出的不怎么样，所以在英文第9版中去掉了这道题，非常驻态类似于挂起状态，当内存不足时，把当前在内存中的一个或多个进程移除内存到辅存中。如果把该题用表表示的状态转换为图来表示的话如下所示。

由图可见，这不是一个完整的状态转换图，缺少从非常驻态到就绪或阻塞的转换，这可能是在第九版中抛弃该题的原因吧。

有了这张图就可以回答本题问题了。

就绪状态到运行状态的转换是由于进程调度程序将CPU分配给该进程。
运行状态到就绪状态转变可能是由于时间片到或被抢先引起的。
运行状态到阻塞状态是由于进程需要进行I/O操作或其他内核请求。
阻塞到就绪是由于进程所等待的事件完成(可能是I/O完成)
就绪状态到非常驻态转换是由于内存不足，系统将该进程所占用的内存中的信息保存在辅存中，把内存空间腾开，让需要的进程使用。
阻塞状态到非常驻态转换与就绪状态到非常驻态转换类似。

问题8. 有n个(n为偶数)椅子供人下棋，一盘围棋由两个人来下，下棋者来时需要看一看有没有空椅子。一个服务员，当有两个人到来且都申请到空椅子时，才允许两个人下棋。一个裁判员，当两个下棋者下完棋后，为两个人裁定胜负。两个人下完棋后，交还椅子离去。使用PV操作实现上述过程。

分析：本题类似理发师问题，但没有说当下棋者看到没有椅子时如何行动，我们假定，下棋者看到没有椅子时等待。定义变量： in_people=0; 表示进入棋盘室还没下棋的棋手人数的奇偶数，0表示偶数，1表示奇数。 out_people=0; 表示下完棋准备离开棋盘室的棋手人数的奇偶数，0表示偶数，1表示奇数。定义信号量： Semaphore Chair=n; //空椅子数，n为偶数 Semaphore Waiter=1；//服务员 Semaphore Referee=1；// 裁判员 Semaphore OpIn=1; // 对in_people互斥使用 Semaphore OpOut=1; // 对out_people互斥使用 Semaphore WaitIn=0；//2棋手下棋同步信号量 Semaphore WaitOut=0; //2棋手离开同步信号量整个过程用PV操作描述如下： Chess_player() { 一个棋手走进棋室； P(Chair); // 申请椅子 P(OpIn); //互斥使用in_people in_people = (in_people+1) % 2; if (in_people == 0) { //偶数, 棋手人数够了，开盘 P(Waiter); // 等待服务员服务员安排2人下棋; V(Waiter); //服务员安排完毕 V(WaitIn); // 叫对手过来下棋 V(OpIn); //释放使用in_people }else { V(OpIn); //释放使用in_people P(WaitIn); //等待对手 } 开始下棋；下棋结束； P(OpOut); // 互斥使用out_people out_people = (out_people+1) % 2; if (out_people == 0) { // 偶数，将要离开 P(Referee); // 等待裁判员裁判员裁定胜负; V(Referee); V(WaitOut); // 叫对手一块离开 V(OpOut); //释放使用out_people }else { V(OpOut); //释放使用out_people P(WaitOut); //等待对手一块离开 } V(Chair); // 释放椅子走出棋盘室; }