• 竞争条件和临界区

  • 先思考，为什么要引入同步技术？因为系统中进程的并行和并发已经成为常态。现代OS中，进程可以在任何时候发生中断。
  • 数据不一致性
    • 多个进程对共享数据的并发/并行访问，解决不一致问题可以引入同步和互斥机制。
    • 拿生产者消费者的例子，count表示生产者生产一个或者消费者消费一个。count++对应的伪机器代码register1 = count，register1 = register1 + 1，count = register1。count--对应的伪机器代码register2 = count，register2 = register2 - 1，count = register2。这6句分别用a-f表示，如果abdecf这样一个操作性次序，则会导致count最终的结果不一致，++得到6，--得到4，然而正确的应该是5。为此引入原子操作，也就是一组操作在执行期间不能中断，必须是连续的。这样一来上面的例子也就只能有2种执行次序abcdef或者defabc。
    • 导致数据不一致的原因是什么呢？
      • 是进程之间存在竞争条件，即多个进程并发访问同一共享数据，而共享数据的最终结果取决于最后操作的进程。所以可以阻止这种竞争，也就是同步和互斥机制。
    • 同步
      • 协调进程的执行次序，使并发进程间能够有效的共享数据和相互合作。比如AB两个进程共享一个缓冲区，A进行写入，B进行读取操作。B需要拿到A的数据才能继续，那么AB之间必须有一个消息通知机制，只有得到通知了再去共享缓冲区里使用数据，才不会出问题，否则可能A写入的数据B还没有来得及读取，A再次写入，这样就把一些数据覆盖掉了。这就是一个简单的进程同步问题。
    • 互斥(本质上是同步的一个特例)
      • 进程排他性的执行某段代码，任何时候只能有一个进程执行。独占资源。
      • 互斥是同步中最简单最粗暴的解决办法。
  • 临界资源
    • 一次只允许一个进程使用的资源，又称互斥资源、独占资源或者共享变量。与之相反的是共享资源。数据的不一致性一般是多个进程访问临界资源造成的。
  • 临界区
    • 把涉及临界资源的代码称作临界区，1）临界区是一个代码片段，2）临界区是进程内的代码，3）每个进程可以有一个或者多个临界区，4）临界区的设置由程序员设定。如果能够保证各个进程互斥进入具有相同临界资源的临界区，则可以实现对临界资源的互斥访问。
    • 如何实现进程之间互斥使用临界区？
      • 为此提出了临界区的访问准则
        1. 互斥准则：假定进程Pi某个临界区执行，其他进程将被排斥在临界区外。(如果把临界区看成一个小房子，软件里面实现这个机制的方式就是加锁。)
        2. 有空让进准则：当临界区内无进程执行时，不能无限期的延长下一个需要进入临界区进程的等待时间(也就是说，让临界区执行完了，需要解锁)。
        3. 有限等待准则：每个进程进入临界区前的等待时间必须有限，不能无限等待(所以临界区一般要小，这段代码的执行时间也不能太长，好比人在房间里睡觉，那外面的人就等着急了)。
      • 访问临界区的方法
        • 进入区(实现互斥准则，保证任何时候只有一个进程进入临界区(进入小房间))
        • 临界区
        • 退出区(实现有空让进准则，你出去时，房门打开让别人可以进去)
        • 其他区

• 信号量

  • 信号量就是同步和互斥的一种实现方法，同步和互斥问题早期采用硬件方法，太过复杂。后来出现了软件解决方案--信号量。信号量类似于红绿灯，他保证交叉方向车辆不能同时进入十字路口，十字路口就好比临界资源。信号量的解决方案：

    • 保证两个或多个代码段不被并发调用
    • 在进入关键代码段前，进程必须获取一个信号量，否则不能运行
    • 执行完关键代码段后，必须释放信号量
    • 信号量有值，为正说明它空闲，为负说明其忙碌。

  • 整形信号量：

    • 最简单的信号量。即一个整数，大于0表示可以获得信号量，小于0表示无法获得信号量。如在使用临界区时，一个进程必须获得一个信号量才能进入临界区。否则需要等待。即互斥准则。同时他还满足有空让进准则。信号量本身就是一个临界资源。如果可以随意访问它，那么就会出现数据不一致问题，为此引入两个不可分割的原子操作来访问信号量。wait(又称为P操作，P取自其发明者Dijkstra家乡的单词首字母)和signal(V操作)，进程调用wait(S)表示要获取一个信号量S，如果S>0,则该进程可以获得一个S信号量，继续运行。S<=0则无法获得信号量，无法运行下去。整形信号量的问题是忙等，在wait(s)中，当s<=0时，不断执行循环，其他什么也不做，s>0时，s--。所以，当一个进程无法获取信号量，则一直做while循环，白白耗费了cpu时间，这就是忙等。signal()中只有一句s++。

  • 记录型信号量：

    • 记录型信号量可以消除忙等，记录型信号量增加了一个等待队列，当一个进程无法获得一个信号量时，马上释放cpu并把自己转化成等待状态(block())，加入该信号量的等待队列。具体可以看https://www.icourse163.org/learn/SUDA-1001752241?tid=1450173443#/learn/content?type=detail&id=1214322157&sm=1中6.2节的6-9分钟。总之记录型信号量通过加入阻塞和唤醒操作消除了忙等。

  • 信号量可以分为两类

    • 计数信号量：没有限制的整数值，又称同步信号量。
    • 二值信号量：变化范围限于{0，1}，又称互斥信号量。
    • 信号量S的使用方法：1)信号量必须置一次且只能置一次初值(计数信号量初值一般为一个整数，二值信号量初值一般为1)
      2)S初值不能为负数 3)除了初始化，只能通过P、V操作来访问S。

  • 两种信号量的使用

    • 互斥信号量
      • 一般用于临界区，wait()和signal()操作一般位于同一进程内，使用步骤一般是1)初始化信号量S，2)wait(S)，进入临界区或者block()，3)signal(S)，释放信号量并查看等待队列中是否有阻塞的进程，如果有则wakeup()一个进程。
    • 同步信号量
      • wait()和signal()操作一般位于两个不同进程内，相对比较复杂。

下面是三个经典问题

• 生产者消费者问题(如何共享有限的缓冲区)

  • 使用同步和互斥机制来保证生产者和消费者在并发执行时，数据一致性的问题。
  • 问题描述
  • 互斥分析
    • 生产者内的in指针和计数器count，都需要互斥。
    • 消费者内的out指针的计数器count，都需要互斥。

• 读者写者问题(如何协同数据的读写操作)

• 哲学家就餐问题(针对资源竞争问题)

• 管程