进程与线程 同步与互斥，死锁

进程和线程这两个话题是程序员绕不开的，操作系统提供的这两个抽象概念非常的重要，此篇导图主要讲述同步与互斥和死锁

第二章 进程与线程 2.3 同步与互斥

• 进程同步、进程互斥
  • 进程同步：并发性带来了异步性，有时需要通过进程同步解决这种异步问题。有的进程之间需要相互配合地完成工作，各进程的工作推进需要遵循一定的先后顺序。
  • 进程互斥：
    • 1.对临界资源的访问，需要互斥的进行。即同一时间段内只能允许一个进程访问该资源。
    • 2.四个部分：进入区：检查是否可进入临界区，若可进入，需要“上锁”。临界区：访问临界资源的那段代码。退出区：负责“解锁”。剩余区：其余代码部分。
  • 需要遵循的原则：
    • 1.空闲让进：临界区空闲时，应允许一个进程访问。
    • 2.忙则等待：临界区正在被访问时，其他试图访问的进程需要等待。
    • 3.有限等待：要在有限时间内进入临界区，保证不会饥饿。
    • 4.让全等待：进不了临界区的进程，要释放处理机，防止忙等。
• 进程互斥的软件实现方法
  • 单标志法
    • 算法思想：两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予，因此该算法可以实现“同一时刻最多只允许一个进程访问临界区”。
    • 在进入区只做“检查”，不“上锁”；在退出区把临界区的使用权转交给另一个进程（相当于在退出区既给另一进程“解锁”，又给自己“上锁”）
    • 主要问题：违背“空闲让进”原则。
  • 双标志先检查
    • 算法思想：设置一个布尔型数组flag[]，数组中各个元素用来标记各进程想进入临界区的意愿，比如“flag[0]=ture”意味着0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自身对应的标志flag[i]设为true，之后开始访问临界区。
    • 在进入区先“检查”后“上锁”，退出区“解锁”
    • 主要问题：不遵循“忙则等待”原则
  • 双标志后检查
    • 算法思想：双标志先检查法的改版。前一个算法的问题是先“检查”后“上锁”，但是这两个操作又无法一气呵成，因此导致了两个进程同时进入临界区的问题。因此，人们又想到先“上锁”后“检查”的方法，来避免上述问题。
    • 在进入区先“上锁”后“检查”，退出区“解锁”
    • 主要问题：不遵循“空闲让进、有限等待”原则，可能导致饥饿
  • Peterson算法
    • 算法思想：结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）。做一个有礼貌的进程。用软件方法解决了进程互斥问题，遵循了空闲让进、忙 则等待、有限等待三个原则，但是依然未遵循让权等待的原则。Peterson算法相较于之前三种软件解决方案来说，是最好的，但依然不够好。
    • 在进入区“主动争取—主动谦让—检查对方是否想进、己方是否谦让”
    • 主要问题：不遵循“让全等待”原则，会发生“忙等”
• 进程互斥的硬件实现方法
  • 中断屏蔽方法
    • 使用“开/关中断”指令实现；
    • 优点：简单高效。缺点：只适用于单处理机；只适用于操作系统内核进程
  • TestAndSet（TS指令/TSL指令）
    • old记录是否已被上锁；再将lock设为true；检查临界区是否已被上锁（若已上锁，则循环重复前几步）
    • 优点：实现简单；适用于多处理机环境；缺点：不满足让全等待
  • Swap指令（XCHG指令）：逻辑上同TSL
• 互斥锁
  • 概念：互斥锁（mutex lock），是解决临界区最简单的工具。一个进程在进入临界区时应获得锁；在退出临界区时释放锁。函数acquire()获得锁，release()释放锁。
  • 特性
    • 1.需忙等，进程时间片用完才下处理机，违反“让全等待”
    • 2.优点：等待时间不用切换进程上下文，多处理器系统中，若上锁的时间短，则等待代价很低
    • 3.常用于多处理器系统，一个核忙等，其他核照常工作，并快速释放临界区
    • 4.不太适用于单处理机系统，忙等的过程中不可能解锁。
• 信号量机制
  • 概念：用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
  • 信号量：一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
  • 原语：是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
  • 一对原语：wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。wait、signal原语常简称为P、V操作（来自荷兰语proberen和verhogen）。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)
  • 整形信号量
    • 用一个整数型变量作为信号量，数值表示某种资源数
    • 整形信号量与普通整型变量的区别：对信号量只能执行初始化、P、V三种操作
    • 存在的问题：不满足让全等待原则
  • 记录型信号量（超高频考点）
    • S.value表示某种资源数，S.L指向等待该资源的队列
    • P操作中，一定先是S.value--，之后可能需要执行block原语
    • V操作中，一定是先S.value++，之后可能需要执行wakeup原语
    • 注意：要能够推断在什么条件下需要执行block或wakeup
    • 可以用记录型信号量实现系统资源的“申请”和“释放”，以及实现进程互斥、同步
  • 注：若考试中出现P(S)、V(S)的操作，除非特别说明，否则默认S为记录型信号量。
• 用信号量实现：进程互斥、同步、前驱关系
  • 信号量机制：除了互斥、同步问题外，还会考察有多个资源的问题，有多少资源就把信号量初值设为多少。申请资源时进行P操作，释放资源时进行V操作即可。
    • 实现进程互斥：分析问题，确定临界区；设置互斥信号量,初值为1（互斥问题，信号量初值为1）；临界区之前对信号量执行P操作；临界区之后对信号量执行V操作。
    • 实现进程同步：分析问题，找出哪里需要实现"一前一后”的同步关系；设置同步信号量，初始值为0（同步问题，信号量初值为0）；在”前操作"之后执行V操作；在“后操作”之前执行P操作。
    • 实现进程的前驱关系：分析问题，画出前驱图，把每一对前驱关系都看成一个同步问题（前驱关系问题，本质上就是多级同步问题）；为每一对前驱关系设置同步信号量,初值为0；在每个“前操作"之后执行V操作；在每个"后操作"之前执行P操作。
• 问题举例：生产者-消费者问题、多生产者-多消费者问题、吸烟者问题、读者写者问题、哲学家进餐问题
• 管程
  • 为什么引入管程？解决信号量机制编程麻烦、易出错的问题
  • 定义和基本特征：
    • 管程是一种特殊的软件模块，有这些部分组成：
      • 1.局部于管程的共享数据结构说明；
      • 2.对该数据结构进行操作的一组过程；
      • 3.对局部于管程的共享数据设置初始值的语句；4.管程有一个名字。
    • 基本特征：
      • 1.局部于管程的数据只能被局部于管程的过程所访问；
      • 2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据；
      • 3.每次仅允许一个进程在管程内执行某个内部过程。
  • 拓展
    • 拓展1：用管程解决生产者消费者问题
      • 引入管程的目的无非就是要更方便地实现进程互斥和同步。
      • 1.需要在管程中定义共享数据（如生产者消费者问题的缓冲区）。
      • 2.需要在管程中定义用于访问这些共享数据的“入口”——其实就是一些函数（如生产者消费者问题中，可以定义一个函数用于将产品放入缓冲区，再定义一个函数用于从缓冲区取出产品）。
      • 3.只有通过这些特定的“入口”才能访问共享数据。
      • 4.管程中有很多“入口”，但是每次只能开放其中一个“入口”，并且只能让一个进程或线程进入（如生产者消费者问题中，各进程需要互斥地访问共享缓冲区。管程的这种特性即可保证一个时间段内最多只会有一个进程在访问缓冲区。注意：这种互斥特性是由编译器负责实现的，程序员不用关心）。
      • 5.可在管程中设置条件变量及等待/唤醒操作以解决同步问题。可以让一个进程或线程在条件变量上等待（此时，该进程应先释放管程的使用权，也就是让出“入口”）；可以通过唤醒操作将等待在条件变量上的进程或线程唤醒。
      • 程序员可以用某种特殊的语法定义一个管程（比如:monitor ProducerConsumer …… end monitor;），之后其他程序员就可以使用这个管程提供的特定“入口”（封装思想）很方便地使用实现进程同步/互斥了。
    • 拓展2：Java中类似于管程的机制
      • Java中，如果用关键字synchronized来描述一个函数，那么这个函数同一时间段内只能被一个线程调用。

2.4 死锁

• 死锁的概念
  • 概念：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进。
  • 死锁、饥饿、死循环的区别
    • 共同点：都是进程无法顺利向前推进的现象（故意设计的死循环除外）
    • 区别
      • 死锁：一定是“循环等待对方手里的资源”导致的，因此如果有死锁现象，那至少有两个或两个以上的进程同时发生死锁。另外，发生死锁的进程一定处于阻塞态。
      • 饥饿：可能只有一个进程发生饥饿。发生饥饿的进程既可能是阻塞态(如长期得不到需要的I/O设备)，也可能是就绪态(长期得不到处理机)
      • 死循环：可能只有一个进程发生死循环。死循环的进程可以上处理机运行（可以是运行态），只不过无法像期待的那样顺利推进。死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由代码逻辑的错误导致的。死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题。
  • 死锁产生的必要条件：必须同时满足以下四个条件
    • 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁（如哲学家的筷子、打印机设备）。
    • 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
    • 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
    • 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）
  • 什么时候会发生死锁？
    • 对不可剥夺资源的不合理分配，可能导致死锁。
  • 死锁的处理策略
    • 预防死锁：破坏死锁产生的四个必要条件中的一个或几个。
    • 避免死锁：防止系统进入不安全状态，从而避免死锁（银行家算法）
    • 死锁的检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
• 预防死锁
  • 破坏互斥条件
    • 把只能互斥使用的资源改造为允许共享使用的资源（如用SPOOLing技术将打印机改造为共享设备）
    • 缺点：很多时候无法破坏互斥条件
  • 破坏不剥夺条件
    • 方案一：当某个进程请求新的资源得不到满足时，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
    • 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如： 剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
    • 缺点：
      • 1.实现起来比较复杂。
      • 2.释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
      • 3.反复地申请和释放资源会增加系统开销，降低系统吞吐量。
      • 4.若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
  • 破坏请求和保持条件
    • 采用静态分配法：即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
    • 缺点：资源利用率极低；也有可能导致某些进程饥饿。
  • 破坏循环等待条件
    • 顺序资源分配法：首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完。
    • 缺点
      • 1.不方便增加新的设备，因为可能需要重新分配所有的编号；
      • 2.进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费；
      • 3.必须按规定次序申请资源，用户编程麻烦。
• 避免死锁
  • 安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
  • 系统的不安全状态
    • 如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
    • 安全状态就一定不会发生死锁；不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态
  • 如何避免系统进入不安全状态——银行家算法
    • “银行家算法”的核心思想：在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
    • 数据结构：假设系统中有n个进程，m种资源
      • 每个进程在运行前先声明对各种资源的最大需求数，则可用一个n*m的矩阵（可用二维数组实现）表示所有进程对各种资源的最大需求数。不妨称为最大需求矩阵Max，Max[i,j]=K表示进程Pi最多需要K个资源Rj。
      • 同理，系统可以用一个n*m的分配矩阵Allocation表示对所有进程的资源分配情况。Max–Allocation=Need矩阵，表示各进程最多还需要多少各类资源。
      • 另外，还要用一个长度为m的一维数组Available表示当前系统中还有多少可用资源。
      • 某进程Pi向系统申请资源，可用一个长度为m的一维数组Requesti表示本次申请的各种资源量。
    • 可用银行家算法预判本次分配是否会导致系统进入不安全状态：
      • ①如果Requesti[j]≤Need[i,j](0≤j≤m)便转向②；否则认为出错。
      • ②如果Requesti[j]≤Available[j](0≤j≤m)，便转向③；否则表示尚无足够资源，Pi必须等待。
      • ③系统试探着把资源分配给进程Pi，并修改相应的数据（并非真的分配，修改数值只是为了做预判）： Available=Available-Requesti; Allocation[i,j]=Allocation[i,j]+Requesti[j]; Need[i,j]=Need[i,j]–Requesti[j]
      • ④操作系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式分配；否则，恢复相应数据，让进程阻塞等待。
    • 安全性算法步骤：检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。
• 死锁的检测和解除
  • 检测
    • 为了能对系统是否已发生了死锁进行检测，必须：
      • ①用某种数据结构来保存资源的请求和分配信息；
      • ②提供一种算法，利用上述信息来检测系统是否已进入死锁状态。
      • 数据结构：资源分配图
        • 两种结点：进程结点；资源结点
        • 两种边：进程结点—>资源结点（请求边）；资源结点—>进程结点（分配边）
    • 死锁检测算法
      • 1）在资源分配图中，找出既不阻塞又不是孤点的进程Pi（即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量。如下图中，R1没有空闲资源，R2有一个空闲资源。若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源）。消去它所有的请求边和分配变，使之称为孤立的结点。在下图中，P1是满足这一条件的进程结点，于是将P1的所有边消去。 2）进程Pi所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。根据1）中的方法进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。即依次消除与不阻塞进程相连的边，直到无边可消。注：不阻塞进程是指其申请的资源数还足够的进程。
      • 如果按上述过程分析，最终能消除所有边，就称这个图是可完全简化的。此时一定没有发生死锁（相当于能找到一个安全序列）；如果最终不能消除所有边，那么此时就是发生了死锁；最终还连着边的那些进程就是处于死锁状态的进程。
      • 死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。
  • 解除
    • 一旦检测出死锁的发生，就应该立即解除死锁。补充：并不是系统中所有的进程都是死锁状态，用死锁检测算法化简资源分配图后，还连着边的那些进程就是死锁进程。
    • 解除死锁的主要方法
      • 1.资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但是应防止被挂起的进程长时间得不到资源而饥饿。
      • 2.撤销进程法（或称终止进程法）：强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大。因为有些进程可能已经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
      • 3.进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。