三：同步与互斥

同步与互斥

进程同步、进程互斥

什么是进程同步

1. 进程具有异步性的特征。异步性是指，各并发执行的进程以各自独立的、不可预知的速度向前推进。
2. 同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。

什么是进程互斥

进程互斥的软件实现方式

单标志法

• 单标志法违背了“空闲让进”原则
  
  

双标志先检查法

• 双标志检查法违背了“忙则等待”原则
• 原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成。“检查”后，“上锁”前可能发生进程切换。
  
  

双标志后检查法

• 双标志后检查法解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，会因各进程都长期无法访问临界资源而产生“饥饿”现象。
  
  

Peterson算法

• Peterson算法用软件方法解决了进程互斥问题，遵顼了空闲让进、忙则等待、有限等待三个原则，但是依然未遵循让权等待的原则.
  
  
  
  

进程互斥的硬件实现方式

中断屏蔽方法

TestAndSet指令

• 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”
  

Swap指令

• 不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。
  

互斥锁

信号量机制

信号量机制 —> 整型信号量

信号量机制 —> 记录型信号量

1. 记录型信号量除了需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。记录型信号量得名于采用了记录型的数据结构
2. wait操作，S.value-表示进程请求一个该类资源，当S.value <0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入该类资源的等待队列S.L,可见该机制遵循了 “让权等待”的准则。
3. signal操作，表示进程释放一个资源,使系统中可供分配的该类资源数增1,因此有S.value ++。若加1后仍是S.valueWO,则表示在S.L中仍有等待该资源的进程被阻塞，因此还应调用wakeup原语，将S.L中的第一个等待进程唤醒。
   
   
   

用信号量机制实现进程互斥、同步、前驱关系

信号量机制实现进程互斥

信号量机制实现进程同步

信号量机制实现前驱关系

生产者消费者问题

1. 实现互斥的P操作一定要在实现同步的P操作之后
2. V操作不会导致进程阻塞，因此两个V操作顺序可以交换
   

多生产者–多消费者

1. 问题 –> 可不可以不用互斥信号量
2. 结论 –> 即使不设置专门的互斥变量mutex，也不会出现多个进程同时访问盘子的现象。
3. 原因 –> 本题种的缓冲区大小为1，在任何时刻，apple、orange、plate三个同步信号量中最多只有一个是1。因此任何时刻，最多只有一个进程的P操作不会被阻塞，并顺利地进入临界区。
4. 如果盘子的个数为2
   
   
   

吸烟者问题

读者–写者问题

哲学家进餐问题

管程

题目总结

1. 多个进程可以共享系统中的资源，一次仅允许一个进程使用的资源称为临界资源。访问临界资源的那段代码称为临界区。
2. 所谓临界区，并不是指临界资源，如共享的数据、代码或硬件设备等，而是指访问临界资源的那段代码程序，如P/V操作、加减锁等。
3. 临界资源是互斥共享资源，非共享数据不属于临界资源。打印机、共享变量和共享缓冲区都只允许一次供一个进程使用。
4. P、V操作是一种低级的进程通信原语，它是不能被中断的
5. 管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程并改变管程中的数据。
6. 共享程序段可能同时被多个进程使用，所以必须可重入编码，否则无法实现共享的功能
7. 管程由局限于管程的共享变量说明、对管程内的数据结构进行操作的一组过程及对局限于管程的数据设置初始值的语句组成。
8. 管程的signal操作与信号量机制中的V操作不同，信号量机制中的V操作一定会改变信号量的值S=S+1。而管程中的signal操作是针对某个条件变量的，若不存在该条件而阻塞的进程，则signal不会产生任何影响。
9. PV操作是一种低级的进程通信原语，不是系统调用。
10. 管程具有如下特性：①局部于管程的数据只能被局部于管程内的过程所访问。②一个进程只有通过调用管程内的过程才能进入管程访问共享数据。③每次仅允许一个进程在管程内执行某个内部过程。
11. 信号量方法可以实现让权等待。