操作系统

【操作系统基础知识】进程同步和死锁

2020-06-15  本文已影响0人  程序员Anthony

基础内容整理，内容来自网络和个人笔记。 往期进程相关文章链接：
【JVM系统基础知识】Java中的进程管理

【操作系统基础知识】进程管理

【JVM系统基础知识】Java 中的并发

1 进程同步和互斥

  1. 进程同步和进程互斥

    • 什么是进程同步
      同步也称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上
      协调他们的工作秩序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作

    • 什么是进程互斥

      • 临界资源：一个时间段内只允许一个进程使用的资源。对于临界资源必须互斥的访问

      • 互斥也叫做间接制约关系：进程互斥是指当一个程序访问某临界资源时，另一个想访问该临界资源的进程
        必须等待当前访问资源的进程访问结束，释放该资源之后，另一个进程才能够访问该资源

      • 对临界资源的互斥访问了逻辑上可以分为四个部分：

        1. 进入区：负责检查是否可进入临界区，如果可进入，则应该设置正在访问临界资源的标志（“上锁”）
          以阻止其他进程同时进入临界区
        2. 临界区：访问临界资源的代码
        3. 退出区：负责解除正在访问临界资源的标志（“解锁”）
        4. 剩余区：做其他处理
          注意：进入区和退出区是负责实现互斥的代码段

      • 进程互斥访问临界资源时，需要遵循的原则

        1. 空闲让进：临界区空闲时，可允许一个请求进入临界区的进程立即进入临界区
        2. 忙则等待：当已有进程进入临界区时，其它试图进入临界区的进程必须等待
        3. 有限等待：对请求访问的进程，应保证在有限时间内进入临界区（保证不会饥饿）
        4. 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

  2. 进程互斥的软件实现方法

    1. 单标志法

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

      • 分析：


        • turn的初始值为0，只允许0号进程进入临界区。

        • 若P1先上处理机运行，则会一直卡在 5 直到P1的时间片用完，发生调度，切换P0上处理机运行，此时代码 1
          不会卡住P0，P0可以正常访问临界区，在P0访问临界区期间即时切换会P1，P1依然会卡在 5 只有P0在退出区
          将turn改为1后，P1才能进入临界区

        • turn表示当前允许进入临界区的进程号，而只有当前允许进入临界区的进程在访问了临界区之后，才会修改turn
          的值。也就是说，对于临界区的访问一直是P0->P1->P0->P1...一直轮流访问

        • 可能导致的问题：
          如果P0一直没有访问临界区，那么就算临界区一直空闲，P1也是不能访问的（因为turn的值需要在P0中修改）
          也就是说，单标志法违背了“空闲让进原则”

    2. 双标志先检验法

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

      • 分析


        • 若按照1，5,2，6,3，7顺序访问（并发执行）P0和P1将会同时访问临界区
        • 双标志检查法主要问题：违反“忙则等待”原则
          原因在于，进入区的检查和“上锁”两个处理不是一气呵成，“检查”后“上锁”可能发生进程切换

    3. 双标志后检查法

      • 算法思想：双标志先检查法的改版，前一个算法会导致两个进程同时进入临界区，人们就使用先“上锁”后“检查”的方法，
        来避免违反“忙则等待”原则

      • 分析


        • 若按照1,5,2,6...的顺序执行，P0和P1都无法进入临界区
        • 虽然解决“忙则等待”问题，但是又违背了“空闲让进”和“有限等待”原则，会因为各进程长期无法访问临界资源而产生
          饥饿现象。两个进程都争着想进入临界区，但是谁也不让着谁，最后两个都无法进入临界区

    4. Peterson算法

      • 算法思想：由于双标志后检查法两者相争没有进程能够进入临界区，Peterson就想到了在双标志后检查法的基础上主动让
        对方使用临界区

      • 分析：


        • Peteson算法用软件方法解决了进程互斥问题，遵循了空闲让进，忙则等待，有限等待三个原则，但是依然未
          遵循让权等待
        • 此算法进行了1,2,3步

  3. 进程互斥的硬件实现方法

    1. 中断屏蔽方法

      • 利用“开/关中断指令”实现（与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许中断
        也就不能发生进程切换，因此也就不可能发生两个同时访问临界区的情况）

      • 优点：简单,搞笑

      • 缺点：不适于多处理机，只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能在内核态运行
        这组指令如果能让用户随意使用会很危险）

    2. TestAndSet指令

      • 简称：TS指令，也称TestAndSetLock指令或TSL指令

      • TSL指令是用硬件实现的，执行过程中不允许中断，只能一气呵成

      • 相比软件实现方法，TSL指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作

      • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境

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

    3. Swap指令

      • 有地方也叫Exchange指令，或者XCHG指令

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

      • 分析：c语言逻辑
        //Swap指令的作用是交换两个变量的值
        Swap(bool *a, *b) {
        bool temp;
        temp = *a;
        *a = *b;
        *b = temp;
        }

        //lock表示当前临界区是否加锁
        bool old = true;
        while(old == true )
        Swap(& block，&old);
        临界代码区。。。
        lock = false;
        剩余代码区

        • 逻辑上Swap与TSL无太大区别，都是先记录下此时临界区是否已经被上锁（old变量）在将上锁标记设置为true
          最后检查old，如果old为false这说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区

        • 优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞，适用于多处理机环境

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

  4. 信号量机制

    • 概述

      • 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而方便的实现了进程同步和进程互斥
      • 信号量其实就是一个变量，可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，
        就可以设置一个初值为1的信号量
      • 原语的执行一气呵成，不可中断，软件提供的解决方案的主要问题就是“进入区的各种操作无法一气呵成”，那么
        如果能把进入区，退出区的操作都用原语实现，这些操作就能一气呵成实现了
      • 一对原语：wait(S)原语和signal(S)原语，括号里的函数S就是函数调用时传入的一个参数
      • wait，signal原语常简称为P、V操作

    • 整型信号量

      • 用一个整数型的变量作为信号量，用来表示系统中某种资源的数量（与普通整数变量的区别：对信号量的操作只有
        三种，即初始化，P操作，V操作）
      • 分析

* 存在问题：不满足让权等待原则，会发生忙等

  1. 如何用信号量机制实现进程互斥，进程同步和进程的前驱关系

    • 信号量机制实现进程互斥

      1. 分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应该放在临界区）
      2. 设置互斥信号量mutex，初值为1
      3. 在临界区之前执行P(mutex)
      4. 在临界区之后执行P(mutex)
      • 注意：对于不同的临界资源需要设置不同的互斥信号量。
        P/V操作必须成对出现，缺少P(mutex)就不能保证临界资源的互斥访问。缺少V(mutex)会导致资源永不释放
        等待进程永远不会被唤醒

    • 信号量机制实现进程同步

      • 回顾

        • 进程同步：要让个进程按要求有序的执行

        • 分析
          比如：P1,P2并发执行，由于存在异步性，因此二者交替推进的秩序是不确定的

          P1() {
          代码1;
          代码2;
          代码3;
          }

          P2() {
          代码4;
          代码5;
          代码6;
          }

          若P2的“代码4”要基于P1的“代码1”和“代码2”的运行结果才能执行，那么我们就必须保证“代码4”
          一定是在“代码2”之后会执行
          这就是进程同步问题，让本来异步并发的进程互相配合，有序推进

      • 实现

        1. 分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作
        2. 设置同步信号量S,初始值为0
        3. 在“前操作”之后执行V(S)。也就是指在执行完上述“一前一后”中前面那个操作之后执行V(S)
        4. 在“后操作”之前执行P(S).也就是指在执行完上述“一前一后”中后面那个操作之后执行P(S)

        • 分析



          分了两种情况（这就保证代码4一定是在代码2之后执行）

          • 若先执行到V(S),则S++后 S = 1。之后当执行到P(S)操作时，由于S = 1，表示有可用资源
            执行性S--，S的值变回0，P2进程不会执行block原语，而是继续执行代码4

          • 若先执行到P(S)操作，由于S = 0，S--后S = -1，表示此时没有可用资源，因此P操作中会执行
            block原语，主动要求阻塞，之后当P1进程执行完代码2,继而执行V(S)操作，S++，使S变回0，由
            于此时有进程在该信号量对应的阻塞队列中，因此会在V(S)操作中执行wakeup原语，唤醒P2进程，
            然后P2就能继续执行代码4

    • 信号量机制实现前驱关系

      • 值的注意的是每一对前驱动操作都是一个进程同步问题（需要保证一前一后的操作）
        因此实现前驱动关系需要：
        1. 为每一对前驱动关系设置一个同步变量
        2. 在“前操作”之后对相应的同步变量执行V操作
        2. 在“后操作”之前对相应的同步变量执行P操作

  2. 生产者消费者的问题

    • 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一组产品放入缓冲区，消费者进程
      每次从缓存区中取出一个产品使用（这里的产品其实就是指一组数据）

    • 生产者，共享一个初始值为空、大小为n的缓存区

    • 只有缓存区没满时，生产者才能把产品放入缓存区，否则必须等待（同步）

    • 只有缓存区不空时，消费者才能从中取出产品，否则必须等待（同步）

    • 缓存区是临界资源，各个进程必须互斥的访问（互斥）

    • 实现细节
      生产者每次要消耗一个空闲的缓存区时，都需要进行一次P操作，而生产一个产品则需要执行V操作，
      消费者每次消耗一个产品需要执行一次P操作，释放一个空闲的缓存区时，需要执行一次V操作

    • 代码分析


  1. 多生产者多消费者
    • 案例：如果不设置互斥访问的变量，那么可能会导致儿子，女儿在执行P操作时，就可进入阻塞状态
      注意：如果缓存区大于1的话，那么，父亲和母亲（两个进程）可以同时访问缓存区，就有可能导致
      两个进程写入缓存区的数据相互覆盖的情况，所以，如果缓存区大于1得换，就必须设置一个
      互斥信号量mutex来保证互斥访问缓存区
  1. 吸烟者问题

    • 问题：假如有一个供应原料者，依次供应胶水和烟叶（组合一），烟叶和卷纸（组合二），卷纸和胶水（组合三），
      有三个吸烟者，它们只有三个原料中的一个，那么，我们需要实现三个吸烟者轮流吸烟。就需要通过PV操作来实现

    • 经过分析：发现同步关系有4组（从事件的角度分析）

      1. 桌子上有组合一 ---> 第一个抽烟者取走东西
      2. 桌子上有组合二 ---> 第二个抽烟者取走东西
      3. 桌子上有组合三 ---> 第三个抽烟者取走东西
      4. 发出完成喜好 ---> 供应则将下一个组合放到桌上

    • 代码实现分析


  1. 读者和写者问题

    • 有读者和写者两组并发进程，共享一个文件，当两个或两个以上的读写进程同时访问共享数据时，不会产生副作用，但若
      某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致。

    • 实现要求：

      1. 允许多个读者可以同时对文件执行读文件操作
      2. 只允许一个写者往文件中写信息
      3. 任一写着在完成写操作之前不允许其他写者或读者工作
      4. 写者在执行写操作之前，应该让已有的读者或写者全部退出

    • 代码实现


  2. 哲学家就餐问题


死锁

  1. 什么是死锁

    • 相关概念：

      1. 死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里资源，导致各进程都阻塞，都无法向前
        推进的现象，就是死锁。发生死锁后若无外力的干涉，这些进程都无法向前推进

      2. 饥饿:由于长期等待不到想要的资源，某进程无法向前推进的现象。例如：在短进程优先的算法中，若有源源不断
        的短进程到来，则长进程一直得不到处理机，从而发生饥饿现象

      3. 死循环：某进程执行过程中一直跳不出某个循环的现象。有可能是由于程序造成的bug，也有可能是自己设计的

      • 注意：死锁和饥饿问题是由于操作系统分配资源的策略不合理导致的，而死循环是由于代码的逻辑错误而导致的。
        死锁和饥饿是管理者（操作系统）的问题，死循环是被管理者的问题

  2. 产生死锁的必要条件

    1. 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。像内存，扬声器这样可以同时让多个进程使用的资源是
      不会导致死锁的

    2. 不剥夺条件：进程所获得的资源在资源未使用完之前，不能由其他进程强行剥夺，只能是强行释放

    3. 请求和保持条件：进程已经保持有了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请
      求资源被阻塞，但又对自己已有的资源保持不放

    4. 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程以获得的资源同时被下一个进程所请求

    • 注意：发生循环等待一定有未必就是死锁，但是发生死锁就一定会有循环等待

  3. 什么时候会发生死锁

    1. 对系统资源的竞争。各进程对不可剥夺资源的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的

    2. 进程推进的顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1,P2分别占用了资源
      R1,R2，而之后进程P1又申请R2，P2进程又申请R1，那么两者会因为申请的资源被对方占用而阻塞，从而发生死锁

    3. 信号量的使用不当也可能会造成死锁。例如：在生产者消费者问题中，如果实现互斥的P操作在实现同步的P操作之前
      就可能会导致死锁

  4. 死锁的处理策略

    • 策略概述

      1. 预防死锁。破坏死锁产生的必要条件中的一个或几个

      2. 避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

      3. 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测操作系统的发生，然后采取措施解除死锁

  5. 预防死锁

    1. 破坏互斥条件

      • 实现：将互斥使用的资源改造为共享使用的资源，那么系统就不会进入死锁状态。比如：使用SPOOLing技术
        可以将独占的设备逻辑上变为共享的设备。

      • 举例：假如有两个进程A,B想使用打印机，在正常情况下，使用打印机，只能是A先使用然后B使用（或者B先
        使用，然后A使用），但是在使用了SPOOLing技术后，在个进程看来自己使用打印机的请求会立即被
        处理了，就不需要再进行阻塞等待

      • 缺点：并非所有的资源都能够改造成可共享使用的资源，为了保护系统安全，很多时候依然需要保护这种互斥
        性。因此很多时候都无法破坏互斥条件

    2. 破坏不剥夺条件

      • 实现：

        1. 当某个进程请求的资源得不到满足时，他必须立即释放保持的所有资源，待以后需要时在再申请。
        2. 当某个进程需要的资源被其他进程所占有时，可以由操作系统协助，将想要的资源强行剥夺过来。这种方式
          需要考虑优先级（比如：剥夺调度方式）

      • 缺点：

        1. 实现起来比较复杂
        2. 释放已经获得的资源可能导致前一阶段的工作失效
        3. 反复申请和释放资源会增加系统得开销
        4. 方案一，需要释放所有资源，需要时重新申请，如果一直发生这样的情况可能会导致进程饥饿

    3.破坏请求和保持条件
    * 实现：采用静态分配方法，即进程在运行前一次性申请完它所需的全部资源，在它资源未满足前，不让它投入运行
    一旦投入运行后，这些资源就一直归它所有，该进程就不会申请其他任何资源了

举例：假设进程A,B分别需要使用资源R1,R2,而进程C需要同时拥有R1,R2，才能运行，那么此时可能由于A
多次请求资源R1,那么这就可能导致C一直不能获取到R1从而进入饥饿状态

  1. 破坏循环等待条件
  1. 死锁的处理

    1. 什么是安全序列

      • 安全序列：就是指如果系统按照这种序列分配资源，则每个进程都能够顺利完成。只要能找出一个安全序列，系统就是
        安全状态。安全序列可能有多个。

      • 如果分配了资源之后。系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后可能所有进程都无
        法顺利的进行下去。当然如果有进程提前归还了一些资源，那系统也可能重新回到安全状态，不过在分配资源之前总是
        要考虑到最坏情况。

      • 如果系统处于安全状态，就一定不会发生死锁。如果系统不处于安全状态，就可能发生死锁（处于不安全状态未必就发生
        了死锁，但发生死锁时一定是在不安全状态）

      • 安全性算法的实现步骤

        1. 检查当前的剩余可用资源是否还能满足某个进程的最大请求，如果可以就把该进程加入安全序列，并把该进程持有
          的资源全部收回

        2. 循环上面操作，查看是否所有进程都能够进入安全序列

    2. 银行家算法

      • 银行家算法的核心思想：在分配资源之前预先判断这次分配是否会导致系统进入不安全状态。如果会进入不安全状态，就
        暂时不答应这次请求，让该进程先阻塞等待

      • 实现步骤

        1. 检查此次申请是否超过了之前声明的最大需求数
        2. 检查系统剩余的可用资源是否还能满足这次请求
        3. 试探着分配，更改个数据结构
        4. 用安全性算法检查此次分配是否会导致系统进入不安全状态
  1. 死锁的检测和解除

    • 死锁的检测

      1. 用某种数据结构来保存资源的请求和分配信息
      2. 提供一种算法，利用上述信息来检测系统是否已进入死锁状态

    • 死锁的解除

      • 主要方法

        1. 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程。但是应该
          防止被挂起的进程长时间得不到资源而饥饿
        2. 撤销进程法（终止进程法）：强制撤销部分，甚至全部死锁进程，并剥夺这些进程的资源。这种方式优点是实现简单
          但是付出的代价可能会很大。因为有些进程可能运行很长时间，一旦撤销，需要从头再来
        3. 进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步，这就要求系统要记录这些历史信息，设置还原点

      • 判断对那个进程进行上述操作的依据：

        1. 进程优先级
        2. 已执行多长时间
        3. 还要多久能完成
        4. 进程已经使用了多少资源
        5. 考虑进程是交互式的还是批处理式的进程（抛弃批处理进程）
上一篇下一篇

猜你喜欢

热点阅读