进程同步 / 互斥

什么是进程同步

• 异步 : 并发执行的程序由于系统资源是有限(无论是CPU和是其他的一些资源)的, 并不能一气呵成的执行下去, 时断时续, 以不可预知的速度向前推进
• 有些操作需要规定一个顺序, 否则会造成未知的错误, 因此需要同步机制, 来规范一系列操作的执行顺序.
• 进程同步 : 直接制约关系. 为完成某个任务的多个进程, 为了保证结果的正确性, 必须协调他们的工作次序而产生的制约关系.

什么是进程互斥

• 进程的并发性需要共享的支持, 各个并发执行的进程不可避免的需要共享使用一些系统资源(比如内存, 打印机, 摄像头这样的I/O设备)

• 资源共享两种方式

  • 互斥共享 : 系统中的某些资源, 虽然可以提供给多个进程使用, 但是一个时间段只允许一个进程访问该资源
  • 同时共享 : 允许一个时间段内多个进程同多“同时”访问这些资源

• 临界资源 : 一个时间段内只允许一个进程使用的资源 (物理设备 : 摄像头, 打印机, 还有许多变量, 数据, 内存缓冲区)

• 对临界资源的访问必须互斥地进行, 亦称间接制约关系.

• 进程互斥 : 间接制约关系, 指当一个进程访问某临界资源时, 另一个想要访问该临界资源的进程必须等待.

• 对临界资源的访问逻辑上分为四部分

  • 进入区 : 负责检查是否可以进入临界资源, 若可进入, 则应设置正在访问临界资源的标识(上锁), 以阻止其余进程同时进入该临界区
  • 临界区 : 访问临界资源的代码
  • 退出区 : 负责解除正在访问临界资源的标识(解锁)
  • 剩余区 : 其他处理

• 临界区是访问临界资源的代码
  -进入区和退出区是负责实现互斥的代码段

• 临界区亦可称为临界段

如果一个进程暂时进不了临界区, 那么该进程是否应该一直占着处理机? 该进程有没有可能一直进不了临界区?

• 为了实现对临界资源的互斥访问, 同时保证系统的整体性能, 需要遵循四个原则
  • 空闲让进 : 临界区空闲时, 可以允许一个请求进入临界区的进程进入临界区
  • 忙则等待 : 当已有进程进入临界区时, 其他试图进入临界区的进程必须等待
  • 有限等待 : 对请求访问临界区的进程, 应该保证在有限时间内进入临界区 (保证不会饥饿 )
  • 让权等待 : 当进程不能进入临界区时, 应立即释放处理机, 防止进程忙等待

总结

• 进程同步是直接制约关系, 进程之间需要相互合作
• 进程互斥是间接制约关系, 没有相互合作, 只是因为资源有限

进程互斥的软件实现方法

• 学习思路
  • 理解各个算法的思想, 原理
  • 结合“实现互斥需要遵循的四个原则”, 重点理解各算法在进入区, 退出区都做了什么
  • 结合四个原则, 分析个算法存在的缺陷

单标志法

• 算法思想
  • 两个进程在访问完临界区后会把临界区的使用权转交给另一个进程, 也就是说每个进程进入临界区的权限只能被另一个进程赋予

双标志先检查法

• 算法思想
  • 设置一个布尔型数组flag[], 数组中的各元素用来标记各进程想进入临界区的意愿. 比如“flag[0] = true” 意味着0号进程现在想进入临界区. 每个进程进入临界区之前先检查当前有没有别的进程想进入临界区. 如果没有, 则把自身对应的标识flag[i]设为true, 之后开始访问临界区.

双标志后检查法

• 算法思想
  • 前一个版本的改进. 前一个算法的问题是先 “检查” 后 “上锁”. 但是这两个操作又无法一气呵成, 因此导致了两个进程同时进入临界区的问题. 因此, 人们想到了先“上锁” 后“检查”的方法, 来避免上述问题

Peterson算法

• 算法思想
  • 双标志后检查法中, 两个进程都想争着进入临界区, 但是谁都不让进, 最后谁都无法进入. Peterson想到一种方法, 如果双方都争着进入临界区, 可以让进程尝试“孔融让梨”, 主动让对方先使用临界区

总结

• 异步性是导致上述算法存在缺陷的根本原因

进程互斥的硬件实现方法

• 学习思路
  • 理解各方法的原理
  • 了解各方法的优缺点

中断屏蔽算法

• 利用“开/关中断”实现 (与原语的实现思想相同, 记载某进程开始访问临界区到结束访问为止 都不允许被中断, 也就不能发生进程切换, 因此也不存在两个进程同时访问临界区的情况)

• 在多个处理机上, 一个处理机上使用开关中断, 使得那个处理机上只能有一个进程访问临界区. 但是别的处理机并不受影响, 当别的处理机上的进程也许要访问同一个临界资源时, 就会违反 “忙则等待” 原则

• 同时“开/关中断“指令权限极高, 只能用于内核态, 因此不适用于用户进程
  

TestAndSet (TS指令/ TSL指令)

• TestAndSet : TS (TestAndSetLock : TSL)
• TSL指令是用硬件实现的, 被执行的过程不允许被中断, 只能一气呵成

Swap指令(XCHC指令)

• 有的地方也叫做Exchange指令, 或建成XCHG指令

• Swap指令也是用硬件实现的, 执行过程不允许被中断, 只能一气呵成.

• 先将此时的临界区上锁, 暂时记录在old变量上, 然后循环检测, 这个临界区之前是否已经上锁(lock变量), 如果已经上锁, 则交换后, old始终为true, 一直循环. 如果之前没有上锁, 则交换后, 将其上了锁, 并且自己退出了循环进入临界区.

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

总结

信号量机制

• 进程互斥的软件实现方式有四种

  • 单标志法
  • 双标志先检查法
  • 双标志后检查法
  • Peterson算法

• 进程互斥的硬件实现方式有三种

  • 屏蔽中断的方法
  • TS指令(TSL指令)
  • Swap指令(XCHG指令)

• 双标志检查法中, 进入区的检查, 上锁操作无法一气呵成, 从而导致了两个进程可能同时进入临界区

• 所有的解决方案都实现“让权等待”

• 1965年, 荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥, 同步的方法 ---- 信号量机制

• 用户进程通过使用操作系统提供的一对原语来对信号量进行操作, 从而很方便的实现进程互斥, 进程同步

• 信号量其实就是一个变量 (可以是一个整数, 也可以是更复杂的记录型变量), 可以用一个信号量来表示系统中某种资源的数量, 比如: 系统中只有一台打印机, 就可以设置一个初值为1的信号量. (使用一对原语对其进行操作)

• 原语 是一种特殊的程序段, 其执行只能一气呵成, 不可被中断. 原语是由开/关中断实现指令实现的.

  • 软件解决方案的主要问题 : “进入区的各种操作无法一气呵成”. 因此如果能把进入区, 退出区的操作都用原语实现, 就能避免这些问题.

• 一对原语 : wait(S) 原语 和 signal(S) 原语. 可以把原语理解为我们自己写的函数. 函数名分别为wait 和 signal. 括号里的信号量S其实就是函数调用时传入的一个参数

  • wait, signal原语通常简称为P、V操作(来自两个荷兰语proberen 和 verhogen), 因此, 做题时常把wait(S), signal(S)两个操作分别写为P(S)、V(S)

整型信号量

• 用一个整数型的变量作为信号量, 用来表示系统中某种资源的数量

  • 与普通整数型变量的区别: 对信号量的操作只有三种 : 初始化, P操作, V操作

• wait原语类似于之前的双标志先检查法 : 先检查后上锁. 只是wait原语使这两个操作成了原语.

• 存在的问题 : 不满足“让权等待”, 会发生“忙等”.

• 这样表示存在的一个问题 : wait原语不可中断, 如果此时资源数量不够, 一直在while循环中出不来. 按理来说会一直占用处理机不被切换.

记录型信号量

• 整型信号量的缺陷存在“忙等”的问题, 因此人们又提出了记录型信号量, 即用记录型数据结构表示的信号量

总结

使用信号量机制

信号量机制实现进程互斥

• 分析并发进程的关键活动, 划定临界区 (如: 对临界区资源打印机的访问就应该放在临界区)
• 设置互斥信号量mutex, 初值为1
• 临界区之前执行P(mutex)
• 临界区之后执行V(mutex)

对不同的临界资源需要设置不同的互斥信号量
P、V操作必须成对出现

信号量机制实现进程同步

• 进程同步 : 要让各并发进程按要求有序地推进

• 用信号量机制实现进程痛殴
  • 分析什么地方需要实现“同步关系”, 即必须要“一前一后”执行的两个操作
  • 设置同步信号量S, 初始化为0
  • 在“前操作”之后执行V(S)
  • 在"后操作"之前执行P(S)
    • 除非前操作先执行, 将S+1, 才能让P(S)不被阻塞, 后操作才能执行. 否则后操作会被阻塞

信号量机制实现前驱关系

总结

• 多少个资源就把信号量初始化为多少
• 多少个临界资源设置多少个信号量
• 多少个前驱关系设置多少个信号量
  

生产者-消费者模型

• 缓冲区是临界资源, 需要互斥访问
  • 如果有两个生产者进程, 发现缓冲区某个为置为空, 他们都会向其中放入数据, 造成其中一个数据丢失
• 临界区需要互斥访问, 一个互斥信号量mutex=1 (操作前P操作后V)
• 缓冲区满, 只能消费者要比生产者先执行, 一个同步信号量 (empty=0 生产者不能使用. 生产者减少P, 消费者增加V)
• 缓冲区空, 只能生产者比消费者先执行, 一个同步信号量 (full=0是生产者不能使用,生产者增加V, 消费者减少P )
  • 初始时, 空闲缓冲区数量n, empty=n, 非空缓冲区数量0, full=0; (产品数量)

• 生产者生产产品, 放入缓冲区之前, 需要先检查缓冲区是否有空余位置, P(empty), 如果有就要对缓冲区进行互斥访问, P(mutex) V(mutex), 放入之后需要对产品数量+1, V(full)
• 消费者消费前, 先检查是否有产品P(full), 如果有则互斥访问P(mutex), V(mutex), 拿到之后空闲缓冲区增加V(empty);
• 若果缓冲区为空(full=0), 必须先生产, 后取出, 生产之后V, 取出之前P
• 如果缓冲区满(empty=0), 必须先消费, 后生产, 消费之后V, 生产之前P
• 同步量初始值为0, 所以就要考虑缓冲区空时, 什么是0, 缓冲区满时什么是0

• 临界区的代码应该尽量少, 只方核心代码, 减少进程在临界区的时间, 提高并发度
• 防止死锁, 需要先执行同步, 在执行互斥
  • 需要先判断, 再进去. 如果判断发现不能用, 就等着不进去, 无事发生.
  • 如果先进去, 再判断, 进去之后判断发现不能用, 那就一直关在里面了

总结

多生产者-多消费者

总结

• 进程同步问题(一前一后问题), 不能从单个进程执行前后分析, 这里的”一前一后“需要看作是“事件”的前后关系, 一个事件可以由多个进程造成.
• 盘子变空事件 -> 放入水果事件

吸烟者问题 (一对多)

总结

• 使用一个整型变量i, 循环改变, 轮流让三个吸引着吸烟
• 如果随机, 设置一个随机变量取模即可.
  

读者-写者问题

总结

• 读者读者之间不需要互斥, 设置一个count计数器来记录正在访问共享文件的读进程数.

哲学家进餐问题

• • 第一种方法 : 设置一个初始值为4的信号量
    
• 第一种情况
  • 0号哲学家, 拿起了左边筷子, 这时候切换到了2号哲学家, 2号哲学家会被阻塞, 直到0号哲学家拿起了右边的筷子并执行了V操作
• 第二种情况
  • 0号哲学家顺利拿起了左右两只筷子, 开始吃饭. 这时切换到了1号哲学家, 在拿左边筷子时会被阻塞, 这是再切换到2号哲学家, 在第一个P(mutex)就会被阻塞, 因为此时1号哲学家正已经执行过了p(mutex). 这时2号哲学家两边筷子均可以使用, 但是无法获取
• 第三种情况
  • 0号哲学家顺利拿起了左右两只筷子, 开始吃饭. 这时切换到了4号哲学家, 拿起了左边筷子后, 就再等待右边筷子被阻塞

总结