破晓的知识屋
0%

进程同步

发表于 分类于 ， 阅读次数： Valine：
本文字数： 3k 阅读时长 ≈ 3 分钟

[toc]

5.1 同步的概念#

不同进程之间需要相互制约，或者存在先后顺序，就会用到同步。

  • 临界资源： 1次只允许1个进程使用
    临界资源访问过程分为四步：
  1. 进入区： 检查和设置临界区标识
  2. 临界区： 访问和使用资源
  3. 退出区： 清楚临界区标志
  4. 剩余区：？

  • 同步： 也称作直接制约关系
    为完成某个任务，多个进程需要协调工作次序并等待，即这个制约关系应该是意料之中出现的。

  • 互斥： 间接制约关系
    因临界资源冲突而引发访问和等待，即不是他想要的制约关系。

  • 同步机制准则：
    空闲让进： 资源空闲的时候允许进入
    忙则等待： 临界区被占用，其他等待
    有限等待： 不能一直等待，出现出现饥饿
    让权等待： 无法进入临界区时，要放弃CPU挂起一段时间，避免一直占用CPU

5.2 临界区的互斥实现原理#

5.2.1 软件实现方式#

  • 单标志法：就是在临界区前后判断turn标志确认临界区谁可进， 当从临界区粗来，再修改临界区标志为另一个进程可进。
  • 双标志法先检查： flag[i]标识低i个进程是否在临界区。 每次检查flag确认是否能进
    可能检查时两个人都通过了，就出错。
    属于先查，后改
  • 双标志法后检查：
    即先改后查，可能2个人同时改，引发饥饿
  • peterson法：
    turn和flag[]一起用。
    用turn判断谁可以先进。这样避免2个人同时改。

5.2.2 硬件方式#

  • 中断屏蔽——禁止一切中断发生？？？ 这啥意思
  • 硬件指令
    TestAndSet 原子操作， 读取lock并修改lock为true
    swap： 原子交换命令， 交换2个字节内容。

5.3 常见同步方式#

5.3.1 信号量#

共享资源数目有限时一般使用信号量。

  • P操作——wait 申请和获取资源
    先减去信号量，再判断， 如果信号量<0，则进程加入阻塞队列

  • V操作——signal 释放资源
    每次操作时，直接增加信号量
    此时说明已经有人空闲了一个资源了。
    当发现信号量此时<=0， 则从阻塞队列里选一个出队

5.3.2 管程#

在内存中而非外村中
是一个共享数据结构

1次只允许1个进管道
可以理解为信号量变成了 只有1的管道
为满时，不可写
为空时，不可读

管程和信号量的区别：
1、信号量可以并发，并发量是取决于s的初始值，而管程则是在任意时刻都是只能有一个。

2、信号量的P操作在操作之前不知道是否会被阻塞，而管程的wait操作则是一定会被阻塞。

3、管程的进程如果执行csignal后，但是没有在这个条件变量上等待的任务的话，则丢弃这个信号。进程在发出信号后会将自己置于紧急队列之中，因为他已经执行了部分代码，所以应该优先于入口队列中的新进入的进程执行。

4、当前进程对一个信号量加1后，会唤醒另一个进程，被唤醒进程程与当前进程并发执行

5.4 同步经典例子#

5.4.1 生产者消费者模型#

简单的信号量模型

5.4.2 读写者问题#

读可以并发读
写的话，必须等读的人都结束了才能写。

5.4.3 哲学家吃饭问题#

每个人都先拿自己最左边的筷子，就会吃不上饭

1次拿2双即可，而不是先拿左手，再拿右手。

5.4.4 吸烟者问题#

3种原材料的供应问题
每个人只有1种材料。
但是吸烟要3种材料。
供应者用完了再上新的
于是吸烟者每次要直接拿2个，而不能1次只拿1个。

5.5 死锁#

5.5.1 原因#

  • 进程请求资源的顺序不对， 出现交叉申请的情况
  • 共同竞争不可剥夺资源

5.5.2 死锁的4个条件和预防#

  1. 互斥——1个资源只能1个进程使用
  2. 不可剥夺——不允许主动抢占，必须等对方释放了才能用。
  3. 请求和保持——
    请求：自己占用资源的情况下，还可以继续请求其他资源。
    保持： 被阻塞的情况下， 自己持有的资源仍然不会释放
  4. 循环等待： 出现循环等待链

根据上面4个条件，可以给出4个预防措施

  1. 破坏互斥——让资源可共享使用——无法实现
  2. 破坏不可剥夺—— 当请求不成功时，会释放自己的资源给别人使用（这样确认不会有人卡着，要么是有人正在全力计算，要么就是阻塞后直接释放，下次再请求）—— 可能引发反复申请，开销大
  3. 破坏请求和保持—— 一次性申请全部资源，不会申请到一半的情况（资源浪费，比如有时候确实得先用一半，接着再用另一半）
  4. 破坏循环等待—— 请求资源时，按照顺序请求资源，给资源编号按优先级申请。——太麻烦

5.5.3 死锁检测和解除#

该方法不会影响资源分配。 只会定时地去检测，然后看是否解除某些死锁

以进程和资源构建一张DAG图
在这里插入图片描述

  • 死锁检测定理：
  1. 找到申请资源充足的进程，消去该进程的所有边
  2. 继续消除，如果边被全部消完，说明无死锁。如果无法消除完，则存在死锁
  • 死锁接触：
    资源剥夺——把死锁进程暂时挂起， 以释放资源，等ok后再放回来。
    撤销进程法——按优先级，强制kill一些进程
    进程回退法—— 把请求资源的操作回退，直到回退到不会发生死锁的DAG

5.5.4 死锁避免算法#

这个算法会影响分配过程，即在资源分配前判断以下。

5.5.4.1 系统安全状态（什么时候系统是安全的）：#

  1. 存在一个安全序列P1\P2\P3， 理解为3个进程，并给出3个进程此时所需的资源
  2. 先把剩余资源都给P1，然后P1用完后再给P2， P2用完再给P3
  3. 按这个顺序下来都没发生资源不够的情况的花，则认为至少是安全的（即至少可通过顺序给资源保证顺利完成剩余任务）

5.5.4.2 银行家算法#

假设进程数量有n个
假设资源有r种

定义以下数组
各资源当前可用数量 Avaialbe[r]
各进程最大需求 max[n][r]
各进程当前已占资源 allocation[n][r]
各进程还需要的资源量 need[n][r]
此时的某进程i对各资源的请求量 request[r]

银行家算法描述：

  1. request必须小于等于need，否则request有错误（即你肯定不能要得过多，都超出需求了）
  2. 检查request是否比avali大，如果过大，则资源不足
  3. 如果1和2都检验通过， 则分配资源，修改avalible、allocation、need
  4. 执行安全性算法， 判断按照最优情况给资源时，是否会出现资源不足
    5.若分配不会导致系统进入不安全状态，则分配，否则等待一段时间，再判断

安全性算法描述：
按顺序，每次把进程剩余need的资源都占去，并剪掉avalid， 看下遍历完是否会出现不够用的情况

5.5 进程、线程同步的区别#

这个 同步 的概念都是一致的. 不论是进程还是线程.
不同在于所采用的同步方式, 进程的同步方式是线程的同步方式的子集. 换句话说, 进程之间的同步方式会比线程之间同步方式选择小. 就这样而已.

线程通信一般是指同一进程内的线程进行通讯，由于在同一进程内，共享地址空间，因此交互比较容易，全局变量之类的都能起到作用。

进程通信一般是指不同进程间的线程进行通讯，由于地址空间不同，因此需要使用操作系统相关机制进行“中转”，比如共享文件、管道、SOCKET。

5.6 linux延申#

linux的死锁检测、避免机制Lockdep
http://kernel.meizu.com/linux-dead-lock-detect-lockdep.html