1. 并发原理
关于并发(concurrency)和并行(parallelism),参照Ch4 区别并发和并行
根据上图,并发中最重要的就是控制问题:控制不同进程的共享资源的访问
2. 互斥
(Mutual Exclusion)
假设多进程访问不可共享资源,称其为临界资源(critical resource),使用临界资源的程序段叫做临界区(critical section),为了避免控制问题,一次只能有一个程序处于临界区,互斥实现中会遇到下列问题:
- 死锁:进程循环等待
- 饥饿:进程被无限拒绝
3. 信号量
3.1 基本原理
两个或多个进程合作时使用semaphore强迫一个进程在某个位置停止:
- 发送信号,执行semSignal(s)
- 接收信号:执行semWait(s)
| 把信号量视为int变量,在其上定义了三个操作:
- initialize: 信号量初始化为非负数(通常为1)
- semWait: 信号量-1,当s<0,阻塞执行semWait的进程
- semSignal:
| —- |信号量+1,若s>=0,被semWait阻塞的进程解除阻塞<br /> |
3.2 二元信号量
对信号量规范定义:
- initialize: 二元信号量只可以初始化为0或1
- semWaitB:检查信号量s
- s=0->进程阻塞
- s=1,则s置为0,继续执行
- semSignalB: 检查是否有进程受阻
4. 生产者/消费者问题
| 问题描述 | 生产者/消费者问题是互斥的典型问题:有一个或多个producer将数据放入buffer,有一个consumer从中取数据,每次取一项,在任何时候: - 只能有一个P或C访问buffer - buffer满时P不会再放数据,buffer空时C不会取数据 |
|---|---|
| 解决思路 |  |
4.1 无限缓冲+二元信号量
算法准备 | 数据结构：给定缓冲区数组
- produce()->元素in
- consume()->元素out
|
|
| —- | :—-: |
| 给定以下变量和信号量:
- n=(in-out),即缓冲区中数据个数
- s, 互斥信号量
- delay, 数据信号量,强迫consumer在数据空时等待
|
|实现 | 原始算法 | 分析 | 修正 | | :—-: | :—-: | :—-: | |
| 该算法不能保证任何情况下的正确：
正确前提:
Producer总能在Consumer之前工作,即消费时,n总为1
错误情况:
- consumer刚出临界区还未执行consume(),n=0
- producer抢占,n++ ->1且delay->1,表示有数据
- consumer恢复,消费后不满足n==0,delay保持1
- consumer连续执行,n— ->0,消费后满足n==0,此时delay==1,semWait(1)表示进程继续,产生矛盾:n==0,缓冲区无数据,却还能继续take()
| 
|
| 产生错误的直接原因: n变化—>delay的更新失败—>consumer第二次先于producer执行
consumer本身满足n==0,准备在此处阻塞,delay置为0,但被抢占后,n++,delay保持1,使得consumer恢复后delay未能阻塞连续消费的发生 | | 算法因为”被producer抢占后n++,导致delay更新错误”而产生,因此使用m局部变量保存consumer中的n,使producer的抢占不会影响delay的更新 |
4.2 无限缓冲+一般信号量
| 
| 使用一般信号量时:
n本身替代了delay作为数据信号量,判断当前缓冲区数据
交换producer中两语句—无影响:
- 图中顺序,当producer出临界区后立刻被抢占,consumer的semWait(n)也会阻塞消费
- 交换,全在临界区进行,更不会抢占
交换consumer中两语句—产生死锁:
- 系统偶然错误,在n==0时,consumer进入临界区执行semWait(n),此时producer无法进入临界区,无法改变n,死锁
|
| :—-: | —- |
4.3 有限缓冲+一般信号量
4.4 信号量的实现
关于信号量的实现,必须满足semWait和semSignal操作作为原子原语
- 可以使用Dekker或Peterson算法(参考PDF P166)
- compare&swap指令
- 禁用中断(仅适用于单处理器系统)
5. 管程
5.1 概述
管程是一种软件模块,由一个或多个过程,一个初始化序列和局部数据组成,有下列特征：
- 任何时候,只能有一个进程在管程中执行,其他调用管程的进程都堵塞
-
5.2 同步&互斥
管程通过条件变量实现互斥,下列函数操作条件变量
cwait(c):进程的执行在条件c上阻塞,管程可被其他进程使用
- csignal(c):恢复等待条件c的进程执行
5.3 有限缓冲+管程
6. 消息传递
6.1 概述
| 消息传递 | 进程交互需要满足同步和通信.为了实时互斥,进程需要同步,为了合作,需要通信.消息传递可以提供以上功能,且可在分布式系统,共享内存的多处理器系统和单处理器系统实现 | |
|---|---|---|
| 基本实现 | 两个重要原语: - send(destination, message) - receive(source, message) |
- 进程以message的形式给目标进程destination发送消息; - 进程通过receive接收消息,当中指明了源进程source和消息message |
6.2 同步&互斥
send和receive分别可能阻塞/非阻塞
| send阻塞/receive阻塞 | 发送进程和接收进程都阻塞,直到完成投递 |
|---|---|
| send无阻塞/receive阻塞 | 接收者阻塞,直到接收到消息(最自然的方式) |
| send无阻塞/receive无阻塞 | 双方都不等待 |
同步作为互斥的基础,在无阻塞send/阻塞receive下,消息传递可以实现互斥,当box中无消息,receive阻塞
6.3 有限缓冲+消息
 |
两个进程两个信箱: - 初始化:mayproduce填满空消息 - 生产:mayproduce中始终放空消息,生产前从mayproduce中接收空消息,当没有空消息,说明缓冲区没有空间,阻塞直到消费后产生空间 - 消费:消费前从maycosume中接收消息,当没有消息,说明缓冲区中无数据,阻塞,直到产生消息 |
|---|---|
7. 读者/写者问题
| 读者/写者问题 | 一个共享的数据区,一些进程(reader)只读取数据,一些进程(writer)只写数据,且满足
- 读者可多个同时读取
- 同时只能一个人写
- 写的时候不能读
即读进程不排除其余读进程,写进程排除所有进程 |
| :—-: | —- |
| 对比P/C问题 | 主要在于对共享空间的访问
- R/W问题中,读者不会写数据,写者不会读数据,
- P/C问题中P可能读取队列指针确定写的位置以及是否已满,c也会调整缓冲区表示其消费了数据
|
| 问题分类
| 读者优先:只要有一个读进程执行,就为读进程保留数据区控制权,其余读进程可同时进行,写进程可能饥饿 |
| | 写者优先:当一个写进程要执行,假设此时一个读进程正执行,暂时阻塞写进程,但其余读进程也被阻塞不能再执行,且优先恢复写进程 |
若有收获，就点个赞吧
0 人点赞
