c++ pipe 同步互斥_答疑（进程同步、互斥、死锁）之一

Love The Way You Lie 2023-01-01 12:57 214阅读 0赞

**问题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.**

![9fc2839ae7fe1987bb6dadf5808209e1.png][]

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

![7a7b0ea9d9e3585f286321e342857849.png][]

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

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

1. 就绪状态到运行状态的转换是由于进程调度程序将CPU分配给该进程。

2. 运行状态到就绪状态转变可能是由于时间片到或被抢先引起的。

3. 运行状态到阻塞状态是由于进程需要进行I/O操作或其他内核请求。

4. 阻塞到就绪是由于进程所等待的事件完成(可能是I/O完成)

5. 就绪状态到非常驻态转换是由于内存不足，系统将该进程所占用的内存中的信息保存在辅存中，把内存空间腾开，让需要的进程使用。

6. 阻塞状态到非常驻态转换与就绪状态到非常驻态转换类似。

**问题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); // 释放椅子       走出棋盘室; \}

[9fc2839ae7fe1987bb6dadf5808209e1.png]: /images/20221120/ada300e985ff412b8990c26f816919eb.png
[7a7b0ea9d9e3585f286321e342857849.png]: /images/20221120/e072310e7442470aabf7617f6b81cfc8.png