10.1背景

利用信号量和管程解决同步互斥的问题

1、并发问题：竞争条件（竞态条件）

多程序并发存在大的问题

2、同步

1）线程共享公共数据的协调条件

2）包括互斥与条件同步

3）互斥：在同一时间只有一个线程可以执行临界区

3、解决同步问题正确比较难

1）需要高层次的编程抽象（如：锁）

2）从底层硬件支持编译

解决的过程图如下所示：

10.2信号量

（与信号灯有类似之处）

1、抽象数据类型

1）一个整形（sem），两个原子操作

2）p操作：sem减一

如果信号量sem<0，认为执行p操作的进程需要睡眠

如果信号量sem>0，认为执行p操作的进程可以继续执行，可以进入临界区

如果挡住了，就不能执行后续的程序，起到了一个阻挡的作用。

3）v操作：sem加一

如果信号量sem<=0，认为当前的进程等待在这一个信号量上面，然后会唤醒这个进程（一个或多个）

2、信号量的图解机制

如果再来一个列车，信号量就不够了，直到一个列车离开了这个临界区之后，会执行一个v操作，而进入临界区之前会执行一个p操作。

离开这个临界区执行v操作之后，这个进程将道空出来之后，还会通知等待的列车去执行

3、由来

10.3信号量的使用

一、基础

1、属性

1）信号量是整数（有符号数）

一开始通常会设定为一个大于0的数，所以一开始执行p操作不会被阻塞。但是多次执行p操作之后，执行p操作的进程就会等待在上面。这时需要起床进程执行v操作，然后唤醒等在这个上面的进程。（如果只能唤醒一个进程，一般是唤醒第一个等待的进程，FIFO对列）

2）信号量是被保护的变量

• 初始化完成后，唯一改变一个信号量的值的办法是通过p操作或者是v操作
• 操作必须是原子

3）p操作（信号量减一操作）能够阻塞，v操作（信号量加一操作）不会阻塞

4）假定信号量是公平的

• 没有线程被阻塞在p操作仍然阻塞如果v操作被无限频繁地调用（在同一个信号量）
• 在实践中，FIFO经常被使用

2、两种类型信号量

1）二进制信号量：可以是0或1（与前面的lock达到同样的效果）

2）一般/计数信号量：可取任何非负值

3）两者互相表现（给定一个可以实现另一个）

3、信号量可以用在两个方面

1）互斥

2）条件同步（调度约束–一个线程等待另一个线程的事件发生）

二、信号量的使用

1、思想介绍

1）用二进制信号量实现的互斥

解析：

一开始要设置一个初始值，为了模仿lock操作，实质了初始值为1。然后在临界区之前，作一个信号量的p操作，在临界区执行之后，作一个信号量的v操作。这个就是二进制信号量的最常用法，完全可以代替前面的lock操作。

2）用二进制信号量完成同步操作

3）其他复杂的问题

一个线程等待另一个线程处理事情

比如生产东西或消费东西

互斥（锁机制）是不够的

2、正确性要求：

1）buffer是有限的

2）任何一个时间只能有一个线程操作缓冲区（互斥）

允许一个或多个生产者往buffer中写数据，但是这时候不允许消费者读数据

允许一个或多个消费者往buffer中读数据，但是这时候不允许生产者写数据

3）当缓冲区为空时，消费者要休眠，消费者必须等待生产者（调度/同步约束）

4）当缓冲区已满时，生产者必须等待消费者（调度/同步约束）

3、使用分析

每个约束用一个单独的信号量

1）二进制信号量互斥

对buffer做添加或者取出的保障

2）一般信号量fullBuffers

代表一开始buffer的数据多少，如果为0，则表示一开始的buffer是空的

3）一般信号量emptyBuffers

代表当前生产者可以往这个buffer塞多少个数据

以上两个技术信号量用于同步操作，当buffer还有空间时，应唤醒生产者继续生产。

4、代码操作

1）数据可初始化如下：

2）生产者的操作：

调用这个函数实现生产者不停的添加数据

3）消费者的操作：

调用这个函数实现消费者不停的取出数据

4）解决互斥同步总实现代码分析

解析：

1）对于生产者来说，由于一开始的buffer设置允许塞进的数据是n，所以生产者可以往下执行。进行buffer的生产操作。

2）但是在生产之前，需要对mutex进程减操作，使之为0。。生产操作完成之后，将mutex加1操作。这次就保证了buffer的互斥问题，确保之间只有一个线程可以执行。两个操作确保了add buffer是一个互斥的操作，确保互斥性。

3）互斥操作完成之后，在将fullbuffer进行一个v操作，加1，提醒生产者可以正常的消费。

4）而对消费者来说，fullbuffer一开始初始值为0，所以是没有数据的。消费者不可能取到数据，所以在等待。所以刚刚生产者唤醒了消费者，和生产者fullbuffer的v操作相匹配。而后进行互斥的取数据操作

5）取出数据之后，会将emptybuffer进行v操作，表示唤醒生产者可以继续生产，也就是生产的进程可以继续执行。

以上就运用了互斥机制和同步机制来实现了一个完成的消费者和生产者的问题。需要注意好初值的确定。

问题：p，v操作的顺序有影响吗？

v操作是加一操作，所以没有影响

p操作是减一操作，会导致阻塞，所以会产生严重的影响，比如死锁的情况

10.4信号量的实现

不仅要会用信号量，还需要知道信号量使用的细节

1、伪代码实现

2、需要注意的问题

1）信号量的双用途

互斥和条件同步

但等待条件是独立的互斥

2）读/开发代码比较困难

程序员必须非常精彩信号量

3）容易出错

使用的信号量已经被另一个线程占用

忘记释放信号量

4）不能处理死锁问题

10.5管程

管程的抽象程度更高，更加容易的来完成相应的同步互斥的问题。

一、基础

1、目的：分离互斥和条件同步的关注

（一开始是完成编程语言的设计，而不是操作系统的设计的，所以其整体上是针对语言的并发机制来完成的）

2、什么是管程（moniter）

管程是包含了一系列的共享变量以及针对这些这些变量函数的一个组合或模块。其包括：

• 一个锁：指定临界区（确保互斥性，只能有一个线程）
• 0或者多个条件变量：等待/通知信号量用于管理并发访问共享数据

3、一般方法

• 收集在对象/模块中的相关共享数据
• 定义方法来访问共享数据

大致的结构图：

一开始，所有进程在右上角的排队队列中，排队完后进行wait()操作，等到signal()操作唤醒后，执行这个进程的代码。

分析：

实现：

解析：

1）这里的numwaiting代表的是当前等待线程的个数，而之前的sem是代表信号量的个数。

2）信号量的实现v操作和c操作是一定会执行的，也就是一定会执行加一操作或者是减一操作。

3）而这里的wait操作是会做加操作，而signal里面，不一定要做减操作。

4）这里在wait函数中，还没有require lock就要release（lock）的原因下面再进行讲解。

5）release(lock)之后，会做一次schedule(),表示会选择下一次线程去执行，因为本身这个线程已经处于睡眠状态了。

6）schedule()完毕再做一个require(lock)的操作，这里又是为什么？这里的release和require和之前的有所不同，下面讲解。

7）signal函数是作唤醒的操作，从等待队列里面取出一个线程唤醒，与之前的schedule()是对应的。wakeup(t)是对schedule的进一步触动机制。最后waiting再进行减减操作。

8）如果等待队列为0，则啥操作也不做这里的numwaiting代表的是当前等待线程的个数，而之前的sem是代表信号量的个数。

二、使用

1、对管程进行初始化

需要注意：

1）lock变量是保证互斥的操作。

2）condition条件变量，这里有两个条件变量，一个是buffer满，一个是buffer空，也就是

3）count中记录了buffer中的空闲情况，count=0，表面buffer是空的，如果buffer是n，表面buffer是满的。

2、互斥机制

生产者是Deposit()，消费者是Remove()。

需要注意：

1）这里不仅仅要对buffer做操作，响应的还要在count中记录下来。

2）信号量互斥的实现是仅仅靠着这个buffer的，而这里的互斥是在函数的头和尾。

3）buffer空了消费者会去睡眠，而buffer满了生产者会去睡眠。

为什么？ -----这是管程的定义来决定的

·因为管程定义，进入管程的时候，只有一个线程可以进去，才能执行管程所管理的所以函数。而既然这图中的两个函数是属于管程管理的两个访问共享变量的函数，就要确保其互斥性和唯一性。所以一进入这个函数就是互斥的。

3、同步机制

1）生产者的buffer未满操作

如何实现：buffer空了消费者会去睡眠，而buffer满了生产者会去睡眠的过程？

当buffer满的时候，也就是count=n，这时候会作一个 notfull.wait(&lock)操作。notfull是一个条件变量，不需要有一个初始值。notfull.wait(&lock)就表示当前已经满了，我需要睡眠，同时还带有一个lock。而这个lock就是管程的lock。

2）小插曲

这时先解释前面的问题：为什么是先relase再require一个锁呢？

解析：

release(lock)：实际上说让当前的生产者释放到这个锁，这使得其他的线程才有可能进入管程去执行。因为这时候生产者要休眠了，所以必须要把这把锁释放。而其释放是由于之前其有一个lock->Acquire(),已经获得了这个锁。所以在wait操作一定要释放，不然所以等待的线程都在等待，系统会停滞。

一旦将来被唤醒了，也意味着可以继续从schedule中继续往下执行，再去完成一次require(lock)。一旦获取了lock之后，就会跳出wait操作，看看count是否等于n。

3）消费者的buffer未满操作

而在notfull的另一边，需要有一个唤醒机制，所以消费者这边会有一个notfull.signal()操作。一旦count做了一个减减操作，buffer满了消费了一个操作，这是buffer句未满了，所以需要去进行唤醒，去唤醒正在等待在这上面的线程。

4）消费者的buffer为空操作与生产者的buffer非空唤醒操作

这消费者这边，buffer空的时候，也同样会有一个while操作，会判断count是否等于0，如果是会作一个notempty的wait操作，直到生产有一个notempty.signal的信号唤醒才可以继续去执行。两者合在一起就是完整的管程来解决生产者消费者的问题。

5）总的实现与和信号量的代码比较

管程实现：

信号量实现：

两者相比，可以看出，与信号量实现的总体功能是一样的，但是实现的细节不一样。

三、两种特别的方式

问题：

管程实现生产者消费者问题中，还需要注意到一点，当线程在管程中执行时，如果线程这时候要执行针对某一个条件变量的signal唤醒操作之后。这时候，是执行等待在这个条件变量上的线程？还是发出唤醒的线程执行完毕后再让那个等待的线程执行？

1、两种方法

1）Hoare方法（比较完美）

一旦发出了signal操作之后，就应该让等待的线程继续执行，而其自身去睡眠。直到等待的线程执行了release之后，这个线程才能继续执行。

特点：比较直观，但是实现起来比较困难

执行的流程如下：

2）Hansen方法：

当发出了signal操作之后，不一定要马上放出对cpu的控制权，而是等发出signal的线程执行完release操作之后才转移cpu控制权。

特点：实现起来比较容易

执行的流程如下：

2、比较

Hoare的while操作可以用if操作来实现，而Hansen的不行，这是唤醒机制不同而造成的。

1）对于Hansen来说，其并没有马上让等待在这上面的线程执行，所以其必须要做relseae才能释放，所以这时会存在多个被唤醒的线程，抢这个继续执行的count。所以当选择自己的时候，count已经不为n了，所以要循环的查询。

2）对于Hoare来说，执行之后会马上的转移cpu、控制权，而这时只要一个线程被唤醒，不存在多个的问题。而其一定可以往下执行，因为count一定不为n。

四、总结

10.6经典同步问题1----读者优先读写者问题

一、读者写者问题

1、动机：共享数据的访问

2、两种类型的使用者

1）读者：不需要修改数据

2）写者：读取和修改数据

3、问题的约束

1）允许同一时间有多个读者，但在任何时候只有一个写者

2）当没有写者时读者才能访问数据

3）当没有读者和写者时写者才能访问数据

4）在任何时候只能有一个线程可以操作共享变量

5）读者优先，不按时间顺序

4、共享数据的设计

1）数据集

2）信号量CountMutex初始化为1

保证count的读写是互斥的

3）信号量WriteMutex初始化为1

保证写者的互斥保护，因为只允许一个写操作

4）整数Rcount初始化1

当前读者的数量，因为可以有多个读者同时操作

二、实现的过程

• sem_wait：就是p操作，也就是减一操作
• sem_post：就是v操作，也就是加一操作

1、写者的互斥保证

分析：

包起来之后确保只有一个线程可以进行写操作。且一旦写者在写，读者就不能读，只能等待。而当读者在读数据的时候，写者也不能写数据。完成了读者写者的互斥操作与写者与写者的互斥操作。

但是没有体现可以允许多个读者读数据

2、多读者体现

分析：

1）rcount=0，代表当时没有读者，所以只要没有写者，就可以继续的执行。

2）但是当如果rount！=0的时候，表明当前已经有读者线程在读数据了，也意味着接下来的操作，写者是一定进不来的，rcount++操作完成读就好。

3）当读完的时候，如果rcount=0，也就是说读者已经读完了，这时外面可能存在写者，所以要唤醒。

3、多读者的互斥

分析：

确保不会存在多个读者同时对rcount进行操作，也就是保证rcount数据的互斥性。

4、完整的读者优先的读者写者问题

三、读者优先与写者优先的区别：

10.7经典同步问题1—写者优先读写者问题

利用管程实现写者优先的读者写者问题

一、基础

1、方法构思

需要注意：

1）读者进行读操作时要注意当前是否有写者（两类：正在写数据的写者和正在等待的写者），这两类写者只要有一个存在，那么读者就需要等待。都不存在才有机会进行读操作。

2）读完之后，检测是否有写者正在等待，其有责任去唤醒。

3）当当前有读者正在读的读者或者正在写的写者时，需要等待。（正在等待的读者不需等待，写者优先）

4）写操作之后，唤醒正在等待的写者或者正在等待的读者。

2、数据结构

AR：当前处于读数据库读者的个数

AW：当前正在写的个数

WR：当前正在等待读者的个数

WW：当前正在等待写者的个数

oktoread：表示当前可以去读

oktowrite：表示当前可以去写

lock：确保只有一个函数进入管程去执行

二、实现

1、读者的具体实现

解析：

1）因为读者读数据的时候，要确保没有正在写的写者和正在等待的写者（写者优先），所以while语句中判断的依据是（AW+WW）>0的时候，都需要等待，并且不断记录被等待的读者，也就是WR++。等到没有写者的时候，被唤醒，其中一个等待的读者可以继续执行，并且WR–。

2）当完成读数据库的操作时，正在读的读者减一操作。并且当此时已经没有读者而且正在有等待的写者时，进行唤醒写者的操作。但是当还有读者的时候，为了保证读写的互斥，就没有必要唤醒写者了。

2、写者的具体实现

解析：

1）当一个写者想写数据的时候，首先进行判断当前有无正在读的读者或者是正在写的写，等待的不需考虑。若没有时，说明可以有机会被唤醒去执行后面的操作。否者继续等待，直到被唤醒，然后等待的写者++。

2）当写完数据时，正在写的写者减一操作（其实我认为AW只有01两个取值，有正在写的写者，或者没有正在写的写者），此时表面没有正在写的写者，而当有等待的写者，既去唤醒其中的一个写者执行。否则，当有正在等待的读者时，去唤醒全部的读者。

3）需要注意，signal是唤醒等待在这个条件变量上的一个，而broadcast是唤醒等待在这个条件变量上面的全部。

10.8经典同步问题2—哲学家就餐问题

一、基础与尝试

1、问题描述

拿叉子，减一的p操作

放叉子，加一的v操作

2、尝试解决（可以跳过）

方案一：

结果：会导致死锁，谁都拿不了右边的叉子

方案二：

结果：会重复过程

方案三：等待随机的时间

结果：等待时间随机变化，可行，但非万全之策。可能等待时间长的哲学家一直在等待。

方案四：

使用信号量的互斥锁来保护

结果：

互斥访问可以实现不会出现死锁的情况，但是每次只允许一个人进餐。本来可以并行两个哲学家同时吃饭，这与问题项背，效率较低。

其将就餐（而不是叉子）看成是必须互斥访问的临界资源，因此回造成（叉子）资源的浪费。

二、实现思路

1、不同的思考

1）哲学家维度

2）计算机维度

2、编写

1）思路

2）数据结构

3）操作方法

3、具体的实现

1）函数take_forks的定义

需要注意：

hungry的状态需要互斥保护

拿两把叉子的过程其实也是在互斥的保护之中

2）函数test_take_left_right_forks的定义

分析：

1）首先确保自己是出于饥饿状态的，然后判断两旁的人是否是出于eatting状态，如果都不是，意味两边都有叉子，就可以吃饭了。

2）可以看出，两把叉子到手，没有一个具体的变量来体现，而是说用状态来表示（因为拿一把叉子是没有意义的）。

3）而在前面赋初值的时候，s[i]的初值是0，v操作之后，自身编变成了1，也就是自己通知自己可以吃饭了。

问题：为什么会通知自己吃饭？

因为在take_forks函数的最后，会有一个p操作，加1之后会减1操作，所以这里的p操作不会被阻塞。只是使得同步信号量加一操作之后，使这里的减一操作不会被阻塞。

3）函数put_forks的定义

功能：把两把叉子放回原处，并在需要的时候去唤醒左岭右舍

需要注意：

这里查看自己的左邻居能否进餐的时候，还有看自己左邻居的左邻居的状态。如果自己左邻居的左邻居的状态是进餐状态，这左邻居不可能进餐。自己的右邻居同理。

4）程序设计的思考过程

以一般的思路分许问题，写出一个伪代码，再将伪代码变成程序。

在这个过程中要设定好变量（同步和互斥的机制）

逐步细化的方式实现这个处理的过程，一般来说是会匹配的（p操作和v操作）

参考链接：https://www.bilibili.com/video/av6538245