• OS | 【二 PV操作】强化阶段 —— 应用题

    一、PV操作应用题详解

    所有有可能被并发访问的信号量 必须互斥进行。

    题型1 生产者 - 消费者问题（生产业：生产资源与消费资源的关系）

     解题步骤：

    • 1、梳理有几类进程？
      • 每一类进程对应一个函数。
    • 2、在函数内部，用中文描述动作
      • 分析动作是只做一次(不加while)还是不断重复( while(1) )。
    • 3、在每一个动作之前，是否需要P什么？
      • 若写P，则必V，立即思考V在哪。
      •  P：注意隐含的互斥条件（如 缓冲区访问）
    • 4、所有的PV写完之后，再定义信号量。
    • 5、检查多个P操作连续出现的地方，是否可能产生死锁。
      •  若仅有一个P操作，不可能出现死锁。请求和保持才可能出现死锁。
      • ① 若某信号量的P，V连续出现（中间没夹别的P）不可能死锁。
      • ② 连续多个P导致的死锁，可尝试调整 P 的顺序。
    • 同步在外，互斥在内。
    • 同步 前V后P；互斥 前P后V；

    【例】

    某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零件，装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后，都要分别把它们送到装配车间的货架F1、F2上。F1存放零件A，F2存放零件B，F1和F2的容量均可存放10个零件。装配工人每次从货架上取一个零件A和一个零件B后组装成产品。请用P、V操作进行正确管理。

    【解析】

    1、三类进程

            

    2、梳理同步关系

            

     3、梳理互斥关系：货架互斥

            

     4、定义信号量

    1. semaphore F1 = 10;   //F1货架的空闲位置
    2. semaphore F2 = 10;   //F2货架的空闲位置
    3. semaphore full1 = 0;  //F1货架的商品A数量
    4. semaphore full2 = 0;  //F2货架的商品B数量
    5. semaphore m1 = 1;  //互斥访问货架F1   
    6. semaphore m2 = 1;  //互斥访问货架F2
    7.  
    8. P1(){  //生产车间A
    9.     while(1){
    10.         生产A零件;
    11.         P(F1);      //申请F1货架空闲位置
    12.         P(m1);      //互斥访问F1货架
    13.         A放到货架F1上;
    14.         V(m1);      //释放货架F1
    15.         V(full1);   //货架F1上商品A数量加1
    16.     }
    17. }
    18.  
    19. P2(){  //生产车间B
    20.     while(1){
    21.         生产B零件;
    22.         P(F2);
    23.         P(m2);
    24.         B放到货架F2上;
    25.         V(m2);
    26.         V(full2);
    27.     }
    28. }
    29.  
    30. C(){  //装配车间
    31.     while(1){
    32.         P(full1);
    33.         P(m1);
    34.         从F1货架取得A商品;
    35.         V(m1);
    36.         V(F1);
    37.         P(full2);
    38.         P(m2);
    39.         从F2货架取得B商品;
    40.         V(m2);
    41.         V(F2);
    42.         组装产品;
    43.     }
    44. }

    【2014年统考】

    系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区（初始为空)。当缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待;当缓冲区未空时，消费者进程可以从缓冲区取走一件产品，否则等待。

    要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P，V(或wait()，signal())操作实现进程间的互斥与同步，要求写出完整的过程，并说明所用信号量的含义和初值。

    【解析】

    1、两类进程

            

     2、分析同步和互斥关系

            

            如果暂未取出十个 将会卡在 for循环或者10个full中。但是！

            注意此处：连续取出10个必须一气呵成，否则将会有其他进程P走属于你的full。

    3、定义信号量

    1. semaphore empty = 1000;  //缓冲区空位个数
    2. semaphore full = 0;  //缓冲区产品个数
    3. semaphore m1 = 1;    //互斥访问缓冲区
    4. semaphore m2 = 1;    //控制进程单次互斥访问缓冲区（实现连续取10次）
    5.  
    6. producer(){
    7.     while(1){
    8.         生产一个产品;
    9.         P(empty);    //占用一个空位
    10.         P(m1);       //互斥访问缓冲区
    11.         商品放入缓冲区;
    12.         V(m1);       //互斥访问缓冲区
    13.         V(full);     //产品数量+1
    14.     }
    15. }
    16.  
    17. consumer(){
    18.     while(1){
    19.         P(m2);   //连续取10次
    20.         for(int i=0;i<10;i++){
    21.             P(full);  //有商品
    22.             P(m1);    //互斥访问缓冲区
    23.             取出一个商品;
    24.             V(m1);    //互斥访问缓冲区
    25.             V(empty); //腾出一个空位
    26.             消费这件产品;
    27.         }
    28.         V(m2); 
    29. }

    【例题】

    某寺庙有小和尚、老和尚若干，有一水缸，由小和尚提水入缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入缸取水仅为1桶水，且不可同时进行。试给出有关从缸取水、入水的算法描述。

    【解析】

    1、两类进程

            

     2、

    先看老和尚：喝水的老和尚要桶 P(tong) ，也要缸里的水 P(full)。再加入互斥条件。

            

    再看小和尚：打水的小和尚要桶 P(tong)，要井 P(jing) ，要缸的空间 P(empty)

            

     3、定义信号量

    1. semaphore tong = 3; //三个桶
    2. semaphore full = 0; //缸中有几桶水
    3. semaphore empty = 10;  //水缸中剩余可容纳水的桶数
    4. semaphore jing = 1;  //小和尚互斥访问水井
    5. semaphore gang = 1;  //小和尚、老和尚互斥访问水缸

    4、检查是否可能出现死锁，连续的P操作。通常可以调换执行顺序解决。

            上述代码中，若有三个老和尚上来就把三个桶拿了，那小和尚就会一直请求桶，老和尚一直请求水，出现死锁。

            所以调整一下：老和尚要拿桶，你得先有水。小和尚要拿桶，你得先有井。

             

    题型2 理发店 - 理发师问题（服务业：提供服务与被服务的关系）

    通常要使用一个变量记录等待顾客的人数。且对此变量的访问互斥进行。

    【例题】

    理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子。如果没有顾客，理发师便在理发椅上睡觉，一个顾客到来时，顾客必须叫醒理发师，如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开。 

     【解析】

    1、两类进程

            

    【例题】

    面包师有很多面包，由n个销售人员推销。每个顾客进店后取一个号，并且等待叫号，当一个销售人员空闲下来时，就叫下一个号。试设计一个使销售人员和顾客同步的算法。

    【法一】

     【法二】

    题型3 读者写者问题 ―― 同类不互斥、异类互斥

    • 读者写者问题主要是解决互斥，他的访问关系分为两种类型，一种是可以同时访问(读和读），另一种是必须互斥访问(写和读,写和写）。
    • 因为多种关系,所以引入了计数器count，记录某一类进程有多少个，且对count的访问是互斥的 。
    • 互斥：mutex。
    • 写过程是不容其他过程的，所以直接P (mutex）；
    • 而读过程P(mutex）受计数器count影响，需要考虑是不是第一个读进程（负责P），以及退出时是不是一个最后一个退出的（负责V）
    • rw：读写之间的互斥
    1. P(){
    2.     if(count==0)
    3.         P(source);  //第一个为后面的兄弟们抢占资源，上锁
    4.     count++;
    5.     使用source;
    6.     count--;
    7.     if(count==0)   //最后一个解锁
    8.         V(source);
    9. }

      【例题】

     

     【解析】

    （1）

             

     （2）

            1、两类进程：需要记录各类进程中各有几个进程正在使用 临界资源

            2、异类互斥，第一个人上锁，最后一个解锁。

    1. P1(){
    2.     if(count1==0)
    3.         P(bridge);  //第一个为后面的兄弟们抢占大桥，上锁
    4.     count1++;
    5.     过桥;           //使用资源
    6.     count1--;
    7.     if(count1==0)   //最后一个解锁
    8.         V(bridge);
    9. }

            3、定义信号量

    【例题】 

     一个主修人类学、辅修计算机科学的学生参加了一个研究课题，调查是否可以教会非洲狒狒理解死锁。他找到一处很深的峡谷，在上边固定了一根横跨峡谷的绳索，这样狒狒就可以攀住绳索越过峡谷。

    同一时刻，只要朝着相同的方向就可以有几只狒狒通过。但如果向东和向西的狒狒同时攀在绳索上那么会产生死锁（狒狒会被卡在中间)，由于它们无法在绳索上从另一只的背上翻过去。如果一只狒狒想越过峡谷，它必须看当前是否有别的狒狒正在逆向通行。利用信号量编写一个避免死锁的程序来解决该问题。

    不考虑连续东行的狒狒会使得西行的狒狒无限制地等待的情况。

    【例题】

     假设一个录像厅有1、2、3三种不同的录像片可由观众选择放映，录像厅的放映规则为:

    1)任一时刻最多只能放映一种录像片，正在放映的录像片是自动循环放映的，最后一个观众主动离开时结束当前录像片的放映;

    2）选择当前正在放映的录像片的观众可立即进入，允许同时有多位选择同一种录像片的观众同时观看，同时观看的观众数量不受限制;

    3)等待观看其他录像片的观众按到达顺序排队，当一种新的录像片开始放映时，所有等待观看该录像片的观众可依次序进入录像厅同时观看。用一个进程代表一个观众，要求:用信号量方法PV操作实现，并给出信号量定义和初始值。

    题型4 哲学家问题（一类进程，同时拥有多种资源才可以运行）

    哲学家问题关键点是限制并行，主要是三种思路：

            1. 限制申请资源的顺序 —— 破坏死锁循环等待条件（解法一不通用，不建议使用）

                    如：规定单号哲学家先取左筷子，双号先取右筷子

            2. 信号量限制并发进程数（解法二通用，但并发度不高，不建议使用）

                    如：规定同一时间只能有一个哲学家就餐（禁止并行）

            3. 让进程一口气取得所有资源，再开始运行（解放三很通用，且 并发度高，建议使用）

                    如：哲学家只有能够取得两个筷子的时候才会就餐

                    P(Lock); if(检查资源是否足够);V(Lock);

    模板：用int型变量表示资源（并发度高）

    【2019年统考】

    (8分)有n (n≥3)位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有m (m≥1)个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的P、V操作 [wait()、signal()操作] 描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。

    【解析】

     1、定义资源信号量、互斥信号量。

            筷子和碗使用 int 型变量定义，便于加加减减。每支筷子属于不同类的资源。

            PV操作只能对 semaphore型信号量 进行操作

    1. int wan = m;
    2. int a[n]={1,1,1...1};  //筷子，a[i]=1表示有右筷子，a[i-1]=1表示有左筷子
    3. semaphore mutex = 1;         //互斥信号量

    2、只要你出手就一定可以运行，所以可以保证并发度最高。

    1. philosopher(){
    2.     while(1){
    3.         P(mutex);    //保证拿碗拿筷子的人只有一个
    4.         if(wan<=0){    //没碗
    5.             V(mutex);
    6.             continue;
    7.         }
    8.         if( !(a[i]==1 && a[(i+1)%n]==1) ){  //少根筷子
    9.             V(mutex);
    10.             continue;
    11.         }
    12.         wan--;
    13.         a[i]=0;a[(i+1)%n]=0;  //拿筷子拿碗
    14.         V(mutex);
    15.         进餐;
    16.     }
    17. }

    【例题】

    俗话说，“干饭人，干饭魂，干饭人吃饭得用盆"。一荤、一素、一汤、一米饭,是每个干饭人的标配。饭点到了，很多干饭人奔向食堂。每个干饭人进入食堂后，需要做这些事:拿一个盆打荤菜，再拿一个盆打素菜，再拿一个盆打汤，再拿一个盆打饭，然后找一个座位坐下干饭，干完饭把盆还给食堂，然后跑路。现在，食堂里共有N个盆，M个座位。请使用P、V操作描述上述过程的互斥与同步，并说明所用信号量及初值的含义。

    【解析】

            显然，上面这种解法会导致死锁。假设同时来了好多个干饭人，每个人都拿三个盆，盆很快就会被拿光。那所有人都无法得到第四个盆，就会发生死锁。

            下面我们模仿哲学家进餐问题的第二种解决思路。在哲学家问题中，共有5个哲学家，如果我们限制“最多允许4个哲学家同时进餐"，那么至少会有一个哲学家可以同时获得左右两只筷子，并顺利进餐，从而预防了死锁。

            同样的思路可以迁移到干饭人问题中。每个干饭人需要同时持有4个盆才能干饭，那么最糟糕的情况是每个干饭人都持有3个盆，同时在等待第四个盆。此时，但凡再多一个盆，就至少能有一个干饭人可以顺利干饭，就不会死锁。因此我们可以限制同时抢盆的人数为x，那么只要满足3x+1≤N,则一定不会发生死锁，可得x≤(N-1)/3。参考代码如下:

     

            上面这种做法，限制了人数上限，且先拿盆，再占座，一定不会发生死锁。当然，如果先占座、后拿盆，也不会死锁。事实上，如果座位的数量满足seat ≤ (N-1)/3,那么甚至可以不设置专门的信号量x，完全可以先占座，后拿盆，也一定不会死锁。因为座位的数量就可以限制同时抢盆的人数。 

            下面我们再模仿哲学家问题的第三种解决思路一—仅当一个哲学家左右两边的筷子都可用时才允许哲学家拿筷子。其实就是破坏了请求和保持条件，采用"静态分配"的思想，让进程一口气获得所有资源，再开始运行。代码如下:

            这个题目想告诉大家的是，哲学家进餐问题的解决思路中，后两种方法更为通用，可以作为考试时主要的策略。大家再思考一下，限制人数上限、一口气拿所有资源，哪种方案的并发度更高一些呢?显然是后者对吧。"限制人数上限""的方案中，最糟糕的情况是，只有一个人获得了4个盆，其余进程都只有3个盆，也就是说只有1个进程可以顺利运行下去，因此并发度低。

            也可以使用int型变量解题。

    1. int pot=N;
    2. int seat=M;
    3. semaphore mutex=1;
    4.  
    5. Eatman(){
    6.     进食堂;
    7. start:
    8.     P(mutex);
    9.     if(pot>=4) pot-=4;
    10.     else{
    11.         V(mutex);
    12.         goto start;
    13.     }
    14. }

    二、历年408PV真题

    【2009年计算机联考真题】

    三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put)送入缓冲区某一空单元中;P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数;P3每次用geteven)从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义（要求用伪代码描述)。

     【2011年计算机联考真题】

    某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下。请添加必要的信号量和P、V(或wait()、signal())操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

    【解析】

    互斥资源：取号机(一次只允许一位顾客领号)，因此设一个互斥信号量mutex对取号机进行管理；

    同步问题：

            顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。如果有空座位，新来的顾客可以到取号机上取号然后到座位上等待，如果无空座位，顾客不能取号。如果有顾客，营业员就得工作，如果无顾客，营业员可以休息，故设置两个信号量empty和full来实现这一同步关系。

            另外，顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量service来完成这一同步过程。

    1. semaphore mutex = 1;                //互斥使用取号机的信号量
    2. semaphore empty = 10;               //空座位的数量信号量
    3. semaphore full = 0;                 //已占座位的数量信号量
    4. semaphore service = 0;              //等待叫号信号量
    5. process 顾客i
    6. {
    7.     P(empty);
    8.     P(mutex);
    9.     从取号机获得一个号；
    10.     V(mutex);
    11.     V(full);
    12.     P(service);        //等待叫号
    13. }
    14. process 营业员
    15. {
    16.     while (true) {
    17.         P(full);
    18.         V(empty);
    19.         V(service);    //叫号
    20.         为顾客服务;
    21.     }
    22. }

    【2013年计算机联考真题】

    某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下，请添加必要的信号量和P、V(或wait()、signal())操作，以实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

    【2015年计算机联考真题】

    有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题。将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信箱最多放M个邮件，B的信箱最多放N个邮件。初始时A的信箱中有x个邮件(0

    【2017年计算机联考真题】

    某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。请添加必要的信号量和P、V(或wait()、signal()）操作，要求确保线程互斥访问临界资源，并且最大限度地并发执行。

    【解析】

            若单独对 y和z 使用互斥信号量访问，则会扣1分。

            因为未实现最大程度的并行。注意 线程 1,2 对y 仅进行读操作，而线程3 还进行了写操作。

            y1本质上是T1和T3对于y的使用权；y2本质上是T2和T3对于y的使用权；

     【2020年计算机联考真题】

    现有5个操作A、B、C、D和E，操作C必须在A和B完成后执行，操作E必须在C和D完成后执行，请使用信号量的wait()、signal()操作（P、V操作光描述上述操作之间的同步关系，并说明所用信号量及其初值。

      【2021年计算机联考真题】

    下表给出了整型信号量S的wait ()和signal ()操作的功能描述，以及采用开关中断指令实现信号量操作互斥的两种方法。

     请回答下列问题。

    1）为什么在 wait ()和 signal ()操作中对信号量s的访问必须互斥执行?

    2）分别说明方法1和方法2是否正确。若不正确，请说明理由。 

    3）用户程序能否使用开/关中断指令实现临界区互斥?为什么? 

    三、第二章大纲复习框架

    • (一)进程与线程
      • 1.进程与线程的基本概念
        • 进程：系统资源分配的基本单位（除CPU外的系统资源的分配单元）
          • 进程控制块PCB：给OS用的程序段，数据段是给进程自己用的。
            • PCB是进程存在的唯一标志。
            • 创建和撤销进程，其实就是对创建进程实体中的PCB。
            • PCB包含信息：进程描述信息（进程 PID 、用户标识符 UID）、进程控制和管理信息、资源分配清单、处理机相关信息（通用、地址、控制、标志寄存器值、状态字）
            • 组织方式：链接方式、索引方式
          • 进程实体/进程映像（静态）：程序段+相关数据段+PCB。
            • 程序段可被多个进程共享。
          • 进程是程序的一次执行过程。（动态）动态、并发、独立、异步
        • 线程：系统调度和分派的基本单位（CPU的分配单元）
          • 线程ID + PC + 寄存器集合 + 堆栈
          • 不同的线程可以执行相同的程序。
          • 线程控制块 TCB

          • 被终止但尚未释放资源的线程仍可被其他线程调用。
          • 一个线程可以读、写或甚至清除另一个线程的堆栈。
        • 属于同一进程的所有线程都具有相同的地址空间。
        • 每个进程都拥有独立的地址空间和资源。
        • 线程切换只需保存和设置少量寄存器。
      • 2.进程/线程的状态与转换
        • 运行态→阻塞态：主动（系统调用）
        • 阻塞态→运行态：被动（中断处理程序）

      • 3.线程的实现
        • 内核支持的线程，线程库支持的线程

        • 多线程模型
          • 多对一模型

          • 一对一模型

          • 多对多模型

          • 内核级线程才是处理机分配的单位。
      • 4.进程与线程的组织与控制
        • 原语：不可被中断的一小段程序，由“关中断”和“开中断”指令实现。原语属于操作系统内核，只有内核代码可以直接调用“原语”。
      • 5.进程间通信
        • 共享内存/共享存储：存在一块可直接访问的共享空间，对其使用同步互斥工具（如PV操作）进行读写操作。
          • 基于数据结构的共享（低级）
          • 基于存储区的共享（高级）
          • 操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读写指令完成。
        • 消息传递：以格式化的信息为单位。
          • 发送消息、接收消息两个原语
          • 直接通信方式：消息缓冲队列
          • 间接通信方式：信箱
        • 管道：pipe文件/共享文件
          • 半双工通信，读数据一次性操作。
          • 只要没空就能读，没满就能写。
          • 一个管道允许多个写，一个读。
    • (二)CPU调度与上下文切换
      • 1.调度的基本概念
        • ★调度是决定将系统资源分配给哪个进程，进程切换是实际分配系统资源。

      • 2.调度的目标
        • CPU利用率
        • 系统吞吐量：单位时间内CPU完成作业的数量
        • 周转时间 = 作业完成时间 - 作业提交时间
        • 带权周转时间 = 作业周转时间 / 作业实际运行时间 ≥1
        • 等待时间：进程等处理机时间之和
        • 响应时间：提交请求到首次响应
      • 3.调度的实现
        • 调度器/调度程序(scheduler)：排队器+分派器+上下文切换器（2组）
        • 调度的时机与调度方式 (抢占式/非抢占式)
          • 不能进行调度和切换的时机：处理中断、进程在OS内核临界区（普通临界区可以）、原子操作，此时置请求调度标志。
          • 非抢占式调度方式：批处理系统
          • 抢占调度方式
        • 闲逛进程
          • 没有就绪进程，就会调度闲逛进程 (idle) 运行，如果没有其他进程就绪，该进程就一直运行，并在执行过程中测试中断。
        • 内核级线程与用户级线程调度
      • 4.典型调度算法
        • FCFS 先来先服务调度算法：不会饥饿，长作业有利 —— CPU繁忙
        • SJF 短作业(短进程、短线程)优先调度算法：CPU使用时间最短，饥饿。
          • 在所有进程同时可运行时/几乎同时到达时，平均等待时间，平均周转时间最少。
        • SRTN 最短剩余时间优先算法：抢占式
        • 时间片轮转调度算法：抢占 —— 人机交互
          • 用户数越多，响应时间越长。
          • UNIX
        • 优先级调度算法：饥饿
          • 注意优先级和优先数的区别
          • 运行时间长，降低优先级；等待时间长，提高优先级。
        • 高响应比优先调度算法：非抢占
          • 等待+要求/要求
        • 多级队列调度算法：抢占
        • 多级反馈队列调度算法
      • 5.上下文及其切换机制 —— 只发生在内核态
    • (三)同步与互斥
      • 1.同步与互斥的基本概念
        • 临界资源：一次仅允许一个进程使用的资源
          • 如打印机、共享变量、共享缓冲区、公用队列
          • 非共享数据、私用数据、磁盘存储介质、可重入代码的程序不属于临界资源
          • 可重入代码：各个进程/线程并发执行这段代码，执行结果不会相互影响
        • 临界区：访问临界资源的代码程序
        • 实现互斥：进入区、退出区
        • 互斥遵循原则
          • 空闲让进：临界区空闲时，应允许一个进程访问
          • 忙则等待：临界区正在被访问时，其他试图访问的进程需要等待
          • 有限等待：要在有限时间内进入临界区，保证不会饥饿
          • 让权等待：让权等待进不了临界区的进程，要释放处理机，防止忙等
          • Peterson方法、swap指令、TestAndSet指令 —— 互斥且忙等
      • 2.基本的实现方法
        • 软件方法

          • 单标志法 —— 违背空闲让进
          • 双标志法先检查 —— 违背忙则等待
          • 双标志法后检查 —— 违背 空闲让进、有限等待
          • Peterson算法 —— 违背让权等待
        • 硬件方法/低级方法/元方法
          • 中断屏蔽方法：不适用多处理机、用户进程，只适用内核进程
          • 硬件指令方法 —— 违背让权等待
            • 仅有运行态和就绪态

      • 3.互斥锁 —— 硬件机制实现，缺点忙等
      • 4.信号量 前V后P
        • 信号量≥0时，已经进入临界区的进程数量 = 信号量初值 — 信号量的当前值
        • 信号量<0时，等待进入临界区的进程数量 = 信号量的绝对值；已经进入临界区的进程数量 = 信号量的初始值
      • 5.管程与条件变量
        • 管程
          • 组成
            • 共享数据结构、对数据结构初始化的语句、—组用来访问数据结构的过程(函数)
          • 各外部进程/线程只能通过管程提供的特定"入口"才能访问共享数据。
          • 每次仅允许一个进程在管程内执行某个内部过程。
          • 各进程必须互斥访问管程的特性是由编译器实现的。
          • 可在管程中设置条件变量及等待/唤醒操作以解决同步问题。
        • wait、signal；每个条件变量一个等待队列，没有具体值，仅实现排队。
      • 6.经典同步问题 同步在外，互斥在内
        • 生产者-消费者问题
        • 读者-写者问题
        • 哲学家进餐问题
    • (四)死锁
      • 1.死锁的基本概念
        • 多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。
        • 四个必要条件
          • 互斥条件
          • 不剥夺条件：资源只能由获得该资源的进程主动释放
          • 请求并保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已经被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
          • 循环等待条件：进程资源的循环等待链。
        • 资源分配图含圈 又不一定有死锁：同类资源数大于1，否则为充要条件。
      • 2.死锁预防
        • 破坏互斥条件：SPOOLing技术
        • 破坏不剥夺条件：常用于状态易于保存和恢复的资源，如CPU寄存器及内存资源，打印机不行哦。
          • ①规定请求新资源的进程得不到满足时，必须释放已有资源以后再重新申请。
          • ②操作系统协助（剥夺调度方式）
        • 破坏请求和并保持条件：预先静态分配策略
          • 一次申请完所需要的的全部资源。
          • 资源利用率低，饥饿。
        • 破坏循环等待条件：顺序资源分配法（资源编号）
      • 3.死锁避免
        • 安全状态：至少存在一个安全序列。
        • 处于不安全状态未必发生死锁，但发生死锁一定存在不安全状态。
        • 银行家算法：在资源分配之前预先判断是否会导致系统进入不安全状态。
          • 银行家算法步骤
            • ①检查此次申请是否超过了之前声明的最大需求数
            • ②检查此时系统剩余的可用资源是否还能满足这次请求
            • ③试探着分配，更改各数据结构
            • ④用安全性算法检查此次分配是否会导致系统进入不安全状态
          • 安全性算法步骤
            • 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，并把该进程持有的资源全部回收。
            • 不断重复上述过程，看最终是否能让所有进程都加入安全序列。
      • 4.死锁检测和解除
        • 资源分配图：请求边，分配边
        • 死锁定理：化简后还连着边的进程
        • 死锁解除
          • 资源剥夺法：挂起死锁进程暂时放到外存
          • 撤销进程法：撤销一个或所以死锁进程并剥夺其资源
          • 进程回退法

  • 相关阅读:
    CSS补充
    基于python高校选课系统设计与实现flask-django-nodejs-php
    DOSBox设置段并执行代码-例2
    ubuntu20.04安装MySQL8、MySQL服务管理、mysql8卸载
    普冉PY32系列(十三) SPI驱动WS2812全彩LED
    微信小程序源码合集8（iOS计算器+备忘录+仿今日头条+仿腾讯视频+艺术）
    实战系列（三）| Mybatis和MybatisPlus区别，包含详细代码
    HTML期末学生大作业-拯救宠物网页作业html+css
    VSCode打开Json 文件格式化
    基于51单片机智能热电偶温度检测PID控制恒温箱设计套件24-157
  • 原文地址：https://blog.csdn.net/weixin_47187147/article/details/126660487