操作系统学习（进程间通信 -- 竞争条件）

竞争条件：  两个或多个进程读写某些共享数据

 

对于一个好的解决方案， 需要满足以下4个条件：

        1)任何两个进程不能同时处于其临界区。

        2)不应对CPU的速度和数量做任何假设。

        3)临界区外运行的进程不得阻塞其他进程。

        4)不得使进程无限期等待进入临界区。

 

 

防止进入竞争条件的方法：

 

        1. 屏蔽中断  缺点： 用户进程控制中断，不可靠。 多核cpu中，单个核心屏蔽中断 不能阻止其他核心访问。    //通常不使用

        2. 锁变量，通过一个变量记录谁在使用。     //不能解决多进程同时访问这个变量而进入竞争条件

        3. 严格轮换法(两个进程速度不匹配的时候会出现比较大的问题： 进程0被一个临界区之外的进程阻塞，违反条件3)  

                             

             只有在有理由认为等待时间是非常短的情形下， 才使用忙等待。 用于忙等待的锁， 称为自旋锁（spin lock） 。

 

        4.  .Peterson解法

 

                                 

        5.  TSL（Test and Set Lock）指令（硬件实现）

                 测试并加锁（Test and Set Lock） ， 它将一个内存字lock读到寄存器RX中， 然后在该内存地址上存一个非零值。 读字和写字操作保证是不可分割的， 即该指令结束之前其他处理器均不允许访问该内存字。 执行TSL指令的CPU将锁住内存总线， 以禁止其他CPU在本指令结束之前访问内存。

 

结论： 4,5 是正确的解法。但是缺点： 1. 产生等待，浪费CPU时间。  2.优先级反转问题 。（临界区外就绪的线程有更高优先级。而低优先级线程阻塞在临界区） 

 

 

睡眠与唤醒

 

生产者-消费者问题(线程)

 

信号量：

信号量是一个特殊的变量，程序对其访问都是原子操作，且只允许对它进行等待（即P(信号变量))和发送（即V(信号变量))信息操作。最简单的信号量是只能取0和1的变量，这也是信号量最常见的一种形式，叫做二进制信号量。所谓原子操作， 是指一组相关联的操作要么都不间断地执行， 要么都不执行（即不会被打断）。 原子操作在计算机科学的其他领域也是非常重要的。

 

用信号量解决生产者-消费者问题。用其简化版本：互斥量。

互斥量是一个可以处于两态之一的变量：解锁和加锁。 这样， 只需要一个二进制位表示它， 不过实际上， 常常使用一个整型量， 0表示解锁， 而其他所有的值则表示加锁。

互斥量使用两个过程。 当一个线程（或进程） 需要访问临界区时， 它调用mutex_lock。 如果该互斥量当前是解锁的（即临界区可用） ， 此调用成功， 调用线程可以*进入该临界区。

另一方面， 如果该互斥量已经加锁， 调用线程被阻塞， 直到在临界区中的线程完成并调用mutex_unlock。 如果多个线程被阻塞在该互斥量上， 将随机选择一个线程并允许它获得锁。

 

在取锁失败时， 线程调用thread_yield将CPU放弃给另一个线程。 这样， 就没有忙等待。   //进程和线程的区别。在线程中， 没有时钟停止运行时间过长的线程。

进程中： 一直等待到另一个进程离开临界区。   线程中：可以不断放弃CPU时间给其他线程。

  

 

条件量：

条件变量则允许线程由于一些未达到的条件而阻塞。

 

 

管程（monitor）

 

 

    管程是一个编程语言概念， 编译器必须要识别管程并用某种方式对其互斥做出安排。 C、 Pascal以及多数其他语言都没有管程， 所以指望这些编译器遵守互斥规则是不合理的。

 

这里的结论是：

信号量太低级了， 而管程在少数几种编程语言之外又无法使用， 并且， 这些原语均未提供机器间的信息交换方法。 所以还需要其他的方法。

 

 

上面提到的其他的方法就是消息传递（message passing）

 

不使用共享内存，起而代之的是消息传递。

    非缓存  ------  发送者，接受者。两个不同步时必有一个阻塞。

    缓存  --------   中间有信箱作为缓存。                         producer---------mailbox ------------  consumer

 

屏障（另一种同步机制，特殊场景）

       

  

场景： 如多个线程协同解大型矩阵，只有每个线程都完成第一阶段后才能一同进行下一层的迭代