• 进程与线程

    一、同步与互斥

    【2016统考】进程P1和P2均包含并发执行的线程，部分伪代码描述如下。


    下列选项中，需要互斥执行的操作是（）

    A、a = 1 与 a = 2        B、a = x 与 b = x         C、x+=1 与 x+=2        D、x += 1 与 x += 3

    解析：

    D、P1和P2中的x属于不同范围的x，互不影响；

    C、同一进程内的x会相互影响，所以x+=1、x+=2的不互斥执行会导致x有不同的值；

    B、a = x，b = x即使不互斥也不会影响最后的结果，一个改变a，一个改变b

    A、a = 1，a = 2，赋值不影响结果

    【2009统考】三个进程P1，P2，P3互斥使用一个包含N（N>0）个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲去某一个空单元；P2每次用getodd()从该缓冲区取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区取出一个偶数并用counteven()统计偶数个数。

    用信号量机制实现这三个进程的同步者互斥活动，并说明所定义的信号量的含义

    多消费者模型，消费者和生产者对临界区的访问是互斥的，但取奇数、取偶数与P1是同步的，P1生产了P2、P3才能取。

    同步：奇数、偶数的同步信号量odd、even

    互斥：缓冲区空位的个数N，互斥信号量mutex

    1. semaphore mutex = 1;
    2. semaphore odd = 0,even = 0;
    3. semaphore empty = N;
    4. cobegin{
    5. P1()
    6.     while(true){
    7.     x = produce();
    8. P(empty);
    9. P(mutex);
    10. Put();
    11. V(mutex);
    12. if(x%2)
    13.     V(even);
    14. else
    15.     V(odd);
    16.  
    17. }
    18. P2()
    19.     while(true){
    20. P(odd);
    21. P(mutex);
    22.     getodd();
    23. V(mutex);
    24. V(empty);
    25.     countodd();
    26.     }
    27. P3()
    28.     while(true){
    29. P(even);
    30. P(mutex);
    31.     geteven();
    32. V(mutex);
    33. V(empty);    
    34.     counteven();
    35.     }
    36. }

    【2011统考】某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

    1. cobegin{
    2. process 顾客i
    3. {
    4.     从取号机获取一个号码;
    5.     等待叫号;
    6.     获取服务;
    7. }
    8. process 营业员
    9. {
    10.     while(TRUE)
    11.     {
    12.     叫号；
    13.     为客户服务;
    14.     }
    15. }
    16. coend

    请添加必要的信号量和P，V[或wait()，signal()]操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

    解析：

    同步：空闲座位数N = 10，人数初值full = 0（空闲的座位数控制人能不能进，人数多少控制了窗口要不要开始）

    互斥：取号机的使用mutex，营业员的服务service

    1. semaphore N = 10;
    2. semaphore mutex = 1;
    3. semaphore full = 0;
    4. semaphore service = 0;
    5. cobegin{
    6. process 顾客i
    7. {   
    8.     P(N);    
    9.     P(mutex);
    10.     从取号机获取一个号码;
    11.     V(mutex);
    12.     V(full);
    13.     P(service);
    14.     获取服务;
    15. }
    16. process 营业员
    17. {
    18.     while(TRUE)
    19.     {
    20.     P(full);//没有顾客则休息
    21.     V(N);//离开座位
    22.     V(service);//叫号
    23.     为顾客服务；
    24.     }
    25. }
    26. coend

    【2013统考】某博物馆最多可容纳500人同时参观，有一个出入口，该出入口一次仅允许一人通过。参观者的活动描述如下：

    1. cobegin{
    2. 参观者进程i{
    3. ……
    4. 进门。
    5. ……
    6. 参观：
    7. ……
    8. 出门：
    9. ……
    10. }
    11. }coend

    互斥：出入口的使用mutex = 1

    同步：馆内的空位empty = 500

    cobegin{

    semaphore mutex = 1;

    semaphore full = 0;

    semaphore empty = 500;

    参观者进程i{

    P(empty);

    P(mutex);

    进门；

    V(mutex);

    参观；

    P(mutex);

    出门；

    V(mutex);

    V(empty);

    ……

    }coend

    【2014统考】系统中有多个生产者进程和多个消费者进程，共享一个能存放1000件产品的环形缓冲区。缓冲区未满时，生产者进程可以放入其生产的一件产品，否则等待；缓冲区未空时，消费者进程可从缓冲区取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品。请使用信号量P，V操作实现进程间的互斥与同步。

    互斥：缓冲区的访问需要互斥锁mutex=1

    同步：产品的数量full = 0，还能放多少产品empty = 1000

    cobegin{

    semaphore mutex1 = 1,mutex2 = 1;

    //mutex1用来控制消费者能连续取10个，不会被别的消费者进程破坏

    semaphore full = 0;

    semaphore empty = 1000;

    Producer i{

            P(empty);

            P(mutex2);

    放入缓冲区；

            V(mutex2);

            V(full);

    }

    Consumer i{

    int x = 10;

            P(mutex1);

    while(x--){

            P(full);

            P(mutex2);

    从缓冲区中取出一件产品；

            V(mutex2);

            V(empty);

            }

            V(mutex1);

    }

    }coend

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

    当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入信箱，否则等待。

    信箱A的邮件数fullA = x ，信箱B的邮件数fullB = y；信箱A还能存的邮件数emptyA = M，信箱BemptyB = N；对信箱A的访问互斥mutex1 = 1，对信箱B的访问互斥mutex2 = 1.

    semaphore fullA = x, fullB = y;

    semaphore emptyA = M, emptyB = N;

    semaphore mutex1 = 1 , mutex2 = 1;

    cobegin{

    A{

            P(fullA);

            P(mutex1);

    回答问题；

            V(mutex1);

           V(emptyA);

            P(emptyB);

            P(mutex2);

    放入邮件；

            V(mutex2);

            V(fullB);

    }

    B{

            P(fullB);

            P(mutex2);

    回答问题；

            V(mutex2);

           V(emptyB);

            P(emptyA);

            P(mutex1);

    放入邮件；

            V(mutex1);

            V(fullA);

    }

    }coend

    【2017统考】某进程中有3个并发执行的线程thread1，thread2和thread3，其伪代码如下

    解析：

    互斥：y，z的互斥使用, mutex_y1 = 1, mutex_y2 = 1 , mutex_z = 1.

    semaphore mutex_y1 = 1, mutex_y2 = 1 , mutex_z = 1;//y1用于thread1和thread3互斥，y2用于thread2和thread3互斥，thread1和thread2之间不存在互斥，若用一个互斥量则效率变慢

    thread1{

            cnum w;

    P(mutex_y1);

            w = add(x,y);

    V(mutex_y1);  

    }

    thread2{

    cnum w;

    P(mutex_y2);

    P(mutex_z);

            w = add(y,z);

    V(mutex_z);

    V(mutex_y2);  

    }

    thread3{

    cnum w;

    w.a = 1;

    w.b = 1;

    P(mutex_z);

            z = add(z,w);

    V(mutex_z);

    P(mutex_y1);

    P(mutex_y2);

            y = add(y,w);

    V(mutex_y1)

    V(mutex_y2);

    }

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

    1）s是多个进程共享的变量，多个进程都可以通过wait，signal进行读写操作。

    2）方法1 不正确，方法2正确，若进入wait之后s如果小于等于0，则无法跳出循环，陷入死锁。

    3）不能，开关中断指令属于特权指令，只能在内核区执行。

    semaphore A = B = C = D = E = F = 0;

    //线程之间的并发进行，不是要线程内的操作进行互斥同步

    T1{

    A;

    signal(A);

    wait(C);

    E;

    F;

    }

    T2{

    B;

    wait(A);

    C;

    signal(C);

    D;

    }

    二、死锁

     1、安全性算法

    解析：

    A、Avail = Avail +  P1.Alloc = （2，2，1）  Avail < P2.Need 不合法

    B、Avail = Avail + P1.Alloc = (2,2,1) Avail < P3.Need 不合法

    ……最后得到结论，安全序列不存在

    tips:

    计算安全序列：

    1、先求need矩阵（尚需要分配）

    2、将可用资源与need做比较，得到第一个need < avail (需要的 < 可用的）的进程 ，若不存在则不安全

    3、将已分配的资源加到可用矩阵之中

    4、重复步骤2

    【2020统考】​​​​​​​某系统中有A、B两类资源各6个，t时刻的资源分配及需求情况如下表所示。

    进程A已分配数量B已分配数量A需求总量B需求总量
    P12344
    P2

    2

    		131
    P31234
    t时刻安全性检测结果（B）

    A、存在安全性序列P1、P2、P3        B、存在安全性序列P2、P1、P3

    C、存在安全性序列P2、P3、P1        D、不存在安全序列

    解析：

    Max - Allocation = \begin{bmatrix}4 & 4 \\ 3 & 1 \\3 & 4\end{bmatrix} - \begin{bmatrix}2 & 3 \\ 2 & 1 \\ 1 & 2 \end{bmatrix} = \begin{bmatrix} 2& 1\\1 & 0\\ 2& 2\end{bmatrix}

    Available = [1,0]，比较可用矩阵和需求矩阵，最接近的是P2，所以先选择P2 ，此时Available = [3,1]，选择P1，最后选择P3

    2、死锁条件

    【2014统考】某系统有n台互斥使用的同类设备，三个并发进程分别需要3、4、5台设备，可确保系统不发生死锁的设备数n最小为（B）

    A、9 B、10 C、11 D、12

    解析：

    四个死锁条件缺一不可（循环等待，互斥使用，不剥夺，请求并保持）

    现在缺少一个循环等待的条件：需要三者都同时等待对方释放设备。所以，只要满足一个进程的条件就不会发生死锁。所以，3 + 3 + 4 = 10台就不会发生死锁。

    tips：想不发生死锁，只需破坏死锁条件

    【2015统考】若系统S1采用死锁避免方法，S2采用死锁检测方法。下列叙述中，正确的是（B）

            1、S1会限制用户申请资源的顺序，而S2不会

            2、S1需要进程运行所需的资源总量信息，而S2不需要

            3、S1不会给可能导致死锁的进程分配资源，而S2会

    A、仅1、2        B、仅2、3         C、仅1、3        D、1、2、3 

    解析：

    死锁避免：在分配资源时的保护措施，不分配给会导致死锁的进程

    死锁检测：不采取任何操作，边分配边检测，发生死锁则立马采取措施解除死锁。S2中记录的是当前状态的资源，而非运行所需的资源总量信息

    三、处理机调度

    【2009】下列进程调度算法中，综合考虑进程等待时间和执行时间的是（D）

    A、时间片轮转调度算法        B、短进程优先调度算法

    C、先来先服务调度算法        D、高响应比优先调度算法

    解析：

    时间片轮转调度算法：给定时间片，在时间片内执行，时间片结束后立马结束

    高响应比优先调度算法：响应比=（等待时间 + 要求服务时间）/ 要求服务时间，克服饥饿现象，满足短作业优先

    【2012】一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它的计算和I/O操作顺序如下：

    P1:    计算60ms，I/O 80ms，计算20ms

    P2:    计算120ms，I/O 40ms，计算40ms

    若不考虑调度和切换时间，则完成两个作业需要的时间最少是（B）

    A、240ms       B、260ms        C、340ms        D、360ms

    画甘特图

    P1:        ｜——60——｜——80——｜              ｜—20—｜

    P2:        ｜-5-｜          ｜————120————｜——40——｜——40——｜ 

    所以需要260ms

    【2016】某单cpu系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入，计算和输出分别为2ms，3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是（B）

    A、15ms       B、17ms        C、22ms        D、27ms

    ｜-2-｜--3--｜---4---｜

               ｜-2-｜｜--3--｜ ｜---4---｜

                          ｜-2-｜     ｜--3--｜      ｜---4---｜

    ｜—2—3——4——————4—————4———｜=17ms

    【2018】某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1us，在T时刻就绪对列中有三个进程P1，P2和P3，其在就绪对列中的等待时间，需要的CPU时间和优先权如下表所示。

    进程等待时间需要的CPU时间优先权
    P130us12us10

    P2

    		15us24us30
    P318us36us20

    若优先权值大的进程优先获得CPU，从T时刻系统开始进程调度，则系统的平均周转时间为（D）

    A、54us        B、73us        C、74us        D、75us

    ｜1｜——24——｜1｜​​​​​​​————36————｜1｜——12——

    t1 =  15 + 24 + 1= 40ms 

    t2 = 36 + 24 + 2 + 18 = 80ms

    t3 = 12 + 24 + 36 + 3 + 30 = 105ms

    平均：（41 + 81 + 106 ）/ 3 =75us

    【2020】下列与进程调度有关的因素中，在设计多级反馈对列调度算法时需要考虑的是（D）

    1、就绪队列的数量                      2、就绪队列的优先级        

    3、各就绪队列的调度算法        4、进程在就绪队列间的迁移条件

    A、仅1、2        B、仅3、4        C、仅2、3、4        D、1、2、3和4

    解析：就绪队列的数量会影响长进程的最终完成时间

    【2016】某进程调度程序采用基于优先数的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整的优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0.进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1.

    1）若调度程序只将nice的值作为进程的优先数，即priority = nice，则可能会出现饥饿现像，为什么？

    2）使用nice，cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用

    1）就绪队列中，一直有优先级数小的进程，导致优先级大的进程一直无法进入执行态，从而产生饥饿现象。

    2）priority = nice + cpuTime * k1 - waitTime * k2 + k3

    waitTime越大代表在就绪队列中等待的时间越长，所以优先级会越高，从而避免饥饿现象

    四、进程与线程

    【2010】下列选项中，导致创建新进程的操作是（C）

    1、用户登录        2、设备分配        3、启动程序执行

    A、仅1、2        B、仅2、3        C、仅1、3        D、1、2、3

    设备分配时通过在系统中设置对应的数据结构（DCT,COCT,CHCT,SDT)实现的，不需要创建进程，是操作系统I/O核心子系统的内容。

    【2010】下列选项中，降低进程优先级的合理时机是（A）

    A、进程时间片用完                     B、进程刚完成I/O操作，进入就绪队列

    C、进程长期处于就绪队列        D、进程从就绪态转为运行态

    应该在时间片用完时才降低优先级

    刚完成I/O、长期处于就绪队列应该提高优先级

    【2011】在支持多线程的系统中，进程P创建的若干线程不能共享的是（D）

    A、进程P的代码段               B、进程P中打开的文件        

    C、进程P的全局变量           D、进程P中某线程的栈指针

    线程间：

    独有：标识符，寄存器，栈，信号屏蔽字，errno，优先级
    共享：虚拟地址空间（代码段和数据段），文件描述符表，信号的处理回调函数，用户ID/组ID/工作路径；

    【2014】下列关于管道（Pipe）通信的叙述中，正确的是（C）

    A、一个管道可实现双向数据传输

    B、管道的容量仅受磁盘容量大小限制

    C、进程对管道进行读操作和写操作都可能被阻塞

    D、一个管道只能有一个读进程或一个写进程对其操作

    管道的容量是固定的

    当管道为空的时候，读进程就会被阻塞

    实现双向数据传输必须要两个管道

    可以两个进程操作（并非双向），只要不同时操作就不会出错。

    【2018】下列选项中，可能导致当前进程P阻塞的事件是（C）

    1、进程P申请临界资源        2、进程P从磁盘读数据        

    3、系统将CPU分配给高优先权的进程

    A、1        B、2        C、1，2        D、1，2

    临界资源正在被他人使用、磁盘数据缺失

    只要请求资源就有可能导致阻塞

    【2019】下列关于线程的描述中，错误的是（B）

    A、内核级线程的调度由操作系统完成

    B、操作系统为每个用户级线程建立一个线程控制块

    C、用户级线程间的切换比内核级线程间的切换效率高

    D、用户级线程可以在不支持内核级线程的操作系统上实现

    用户级线程与操作系统无关​​​​​​​

    操作系统用户级线程建立的线程控制块与多线程模型有关，一对一模型中，每个用户级线程建立一个线程控制块

    内核级线程需要从用户态切换到核心态，开销大

    【2020】下列关于父进程与子进程的叙述中，错误的是（B）

    A、父进程与子进程可以并发执行

    B、父进程与子进程共享虚拟地址空间

    C、父进程与子进程有不同的进程控制块

    D、父进程与子进程不能同时使用同一临界资源

    子进程复制父进程的数据段、BSS段、代码段、堆空间、栈空间和文件描述符

    子进程复制了父进程虚拟地址空间，而不是共享，共享是时时刻刻都一样，复制只是fork之后短时间内相同。

    【2022】下列事件或操作中，可能导致进程P由执行态变为阻塞态的是（D）

    1、进程P读文件        2、进程P的时间片用完

    3、进程P申请外设        4、进程P执行信号量的wait（）操作

    A、仅1、4        B、仅2、3        C、仅3、4        D、仅1、3、4

    进入阻塞态：请求资源（3）、等待I/O（1）、wait操作（4）

    时间片结束时会进入就绪态

    ​​​​​​​唤醒：从阻塞态离开变成就绪态

  • 相关阅读:
    一文解决Word中公式插入问题(全免费/latex公式输入/texsWord)
    楼市越来越冷，业主们能否靠出租增值？
    健康先行微信小程序设计与实现
    【QT开发笔记-基础篇】| 第四章 事件QEvent | 4.4 鼠标按下、移动、释放事件
    Bean初始化扩展点
    【21天Python进阶学习挑战赛】[day9]操作MongoDB数据库
    单实例单实例Oracle数据库，RMAN，故障的应对
    postgresql-类型转换函数
    《effecttive C++》和一些其他C++开发的东西的学习总结（长期更新）
    论文研读1——对抗样本(Adversarial Example)综述
  • 原文地址：https://blog.csdn.net/m0_53210180/article/details/132542365