Chapter2 - 进程管理

[TOC]

0x00 概述

CPU管理，也称为处理机管理，是操作系统的基本管理功能之一，它所关心的是处理机的分配问题，也就是把CPU（中央处理机）的使用权分给某个程序。

  • 通常把一个正准备进入内存的程序称为作业。
  • 当这个作业进入内存后，我们把它称为进程。

处理机管理分为作业管理和进程管理两个阶段，常常又把实行处理机时间分配的进程调度工作称为低级调度，而把作业调度称为高级调度。

  • 作业管理的主要功能是把用户手头的作业送入内存投入运行，所以此时的作业调度是由用户决定的。
    • 一旦将作业送入内存，便由进程管理为作业创建进程，由进程管理负责其运行的安排。
  • 进程管理的主要功能是把处理机分配给进程以及协调各个进程之间的相互管理。它由进程调度程序和交通控制（控制进程状态转换）程序这两部分内容组成。
    • 进程调度程序的功能是根据一定的调度原则（如优先数、简单轮转等），确定处理机应分配给哪一个等待CPU的进程。
    • 交通控制程序的功能是记住进程处于何种状态，并实现进程状态之间的转换。

进程通常具有三种状态：运行状态（正在使用CPU）、就绪状态（等待分配CPU）、阻塞状态（等待输入/输出）。

  • 当进程要从运行态变为阻塞态时，交通控制程序的工作就是改变进程状态，保存进程执行的现场，并收回处理机以便分配给其他进程。
  • 当进程从就绪态变为运行态时，除了相应地改变状态歪，还应恢复进程状态的现场使之能够继续运行。

0x01 进程的基本概念

1. 计算机执行程序的最基本方式——单道程序的执行

计算机执行某程序，需要满足两个基本条件：

  • 一是将程序放入内存；
  • 二是将改程序的地址送入程序计数器 PC（program counter）。

CPU的执行轨迹完全取决于PC的内容，即CPU要知道到内存的何处去取指令。因此，只需要把这个程序存入内存，并把该程序的起始地址送入PC中，CPU便可执行这个程序了，这便是单道程序执行的基本原理。

2. 多个程序驻留内存——多个程序依次顺序执行

当需要依次顺序执行多个程序时，则需要将这几个程序都放到内存中，并依次把各个程序的起始地址放入PC中，CPU依此顺序执行。

  • 保证上一个程序执行完毕后，再将下一个程序的起始地址放入PC。

这就是多道程序驻留于内存中的一种顺序执行方式。

3. 进程的概念和结构——多个程序并发执行

1）程序的顺序执行及其特性

image-20200917103752487

一切顺序执行的程序具有下列特性：

  • 顺序性：按照程序结构所指定的次序（可能有分支或循环）。
  • 封闭性：程序在执行过程中独占全部资源，计算机的状态只由于该程序本身的控制逻辑所决定，与外界环境无关。
  • 可再现性：初始条件相同则结果相同。

2）程序的并发执行及其特性

基本概念
  • 并发Concurrent：设有两个活动a1和a2，如果在某一指定的时间t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。
    • 在宏观上，这几道程序同时向前推进；微观上，由单CPU按照时间片轮转执行每个程序的一小部分代码。
    • 关键词：分时运行
  • 并行Parallel：如果考虑两个程序,它们在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的。
    • 关键词：同时运行

程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的。

  • 所谓执行在时间上是重叠的，是指执行一个程序（或程序段）的第一条指令是在执行另一个程序（或程序段）的最后一条指令完成之前开始
image-20200917104336101

程序的并发执行具有如下特性：

  • 间断性：并发程序具有“执行—暂停—-执行”这种间断性的活动规律。
  • 非封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。
  • 不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的次序。

由于程序并发执行而产生的的相互制约关系，使得并发执行程序具有“执行-暂停-执行”的活动规律。通常，程序的制约方式有如下两种：

  • 间接制约方式：等待资源，即由不同程序段竞争相同资源引起的。
  • 直接制约方式：逻辑上相互依赖，一般是由于各种程序段要求共享信息引起的。
    • 例如，要求信息通信或同步时，就会发生这种制约关系。这时可以使用系统提供的同步操作，来调节各程序段之间的并行控制。
Bernstein条件
image-20200917145302741
  • 竞争：多个进程在读写一个共享数据时结果依赖于它们执行的相对时间，这种情形叫做竞争。
  • 竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关，称为竞争（发生）条件。

什么条件下两个进程不会发生竞争？

image-20200917145637123

3）资源共享

  • 资源：指计算机处理一个任务或作业时的所有硬设备（处理机、内存、外存、I/O设备等）和软设备（文件、程序、数据、信息）的总称。
  • 资源共享：指并发执行的多个程序交替使用计算机硬件和软件资源。

通常来说，并发执行的多个程序所需资源总数总是大于系统可提供的资源数，因而必须由操作系统来提供一定的管理和协调手段。

操作系统是用来实现对计算机资源进行管理的一个大型系统程序，其基本特征之一就是资源共享。

操作系统提供了以下两种实现资源共享的方法：

  • 由操作系统统一管理和分配。进程不能直接擅自动用系统资源，必须向操作系统提出申请，以免出现混乱。
    • 一般地，硬件资源都是采用这种方法共享。
  • 由进程自行使用。系统中某些资源不必由系统分批，可供进程直接使用，可以通过进程之间的协调来实现资源的共享。
    • 例如某些数据结构、变量等。

4. 进程的定义

1）进程的定义

在多道程序系统和分时系统中，存在着多个并发执行的程序执行过程。为了描述和实现系统中各种活动的独立性、并发性、动态性、相互制约性以及“执行-暂停-执行”的活动规律，揭示操作系统的动态实质，引入了进程（Process）的概念。

目前为止，进程还没有一个严格的定义，根据应用的需要，对进程的描述会略有不同：

  • 进程是程序的一次执行；
  • 进程是可以和别的计算并发执行的计算；
  • 进程可定义为一个数据结构，及能在其上进行操作的一个程序；
  • 进程是一个程序及其数据，在处理机上顺序执行时所发生的活动；
  • 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

进程，作为程序执行的过程，有如下特性：

  • 动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。而程序是静态实体。
  • 并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
  • 独立性：在传统OS中，进程是独立运行的基本单位
  • 异步性：也叫制约性，进程之间相互制约，进程以各自独立的不可预知的速度向前推进。
  • 结构特征：程序段，数据段，进程控制块PCB

一个进程应该包括：

  • 程序的代码；
  • 程序的数据；
  • PC中的值，用来指示下一条将运行的指令；
  • 一组通用的寄存器的当前值，堆、栈；
  • 一组系统资源（如打开的文件）

2）进程与程序的区别

  • 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。
  • 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。
  • 进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。
  • 进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。

3）系统进程与用户进程

进程通常分为两类，一类是系统进程，另一类是用户进程。

  • 系统进程是操作系统用来管理系统资源并行活动的并发软件；
  • 用户进程是可以独立执行的用户程序段，它是操作系统提供服务的对象，是系统资源的实际享有者。

它们的区别是：

  • 系统进程之间的关系由操作系统负责，有利于增加系统的并行性；用户进程之间的关系主要由用户自己负责，便于用户管理自己的任务。
  • 系统进程直接管理有关的软、硬设备的活动；用户进程只能间接地和系统资源发生关系，即必须向系统提出申请，由系统统一调度和分配。
  • 在进程调度中，系统进程的优先级高于用户进程。不管是系统进程还是用户进程，对核心层来说它们都是基本的活动单位。

0x02 进程的状态和进程控制块

1. 进程的状态及状态转化

1）三态模型

进程的三种基本状态：

  • 就绪状态：等待处理机的状态。
    • 进程已获得除处理机外的所需资源，等待分配处理机资源，一旦获得处理机就立即投入运行。
  • 执行状态：进程正在处理机上运行的状态。
    • 该进程已获得必要的资源，也获得了处理机，用户程序正在处理机上运行。
    • 处于此状态的进程的数目小于等于CPU的数目。
    • 在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。
  • 阻塞状态：进程等待某种事件完成（例如等待I/O操作的完成）而暂时不能运行的状态。
    • 处于该状态的进程不能参与竞争处理机。

进程状态的转化：

  • 就绪 -> 运行
    • 时间一到，调度程序选择一个进程运行
  • 运行 -> 就绪
    • 运行进程用完了时间片；
    • 运行进程被中断，因为一高优先级进程处于就绪状态。
  • 运行 -> 阻塞
    • 当一进程所需的东西必须等待时
    • OS尚未完成服务
    • 对一资源的访问尚不能进行
    • 初始化I/O 且必须等待结果
    • 等待某一进程提供输入(IPC)
  • 阻塞 -> 就绪
    • 当所等待的事件发生时
image-20200917152442861

2）*五态模型

对于一个实际的系统，进程的状态及其转换更为复杂，引入新建态和终止态构成了进程的五态模型。

  • 新建态： 对应于进程刚刚被创建时没有被提交的状态，并等待系统完成创建进程的所有必要信息。
    • 进程正在创建过程中，还不能运行。
    • 操作系统在创建状态要进行的工作包括分配和建立进程控制块表项、建立资源表格（如打开文件表）并分配资源、加载程序并建立地址空间表等。
    • 创建进程时分为两个阶段，第一个阶段为一个新进程创建必要的管理信息，第二个阶段让该进程进入就绪状态。由于有了新建态，操作系统往往可以根据系统的性能和主存容量的限制推迟新建态进程的提交。
  • 终止态：进程已结束运行，回收除进程控制块之外的其他资源，并让其他进程从进程控制块中收集有关信息（如记帐和将退出代码传递给父进程）。
    • 类似的，进程的终止也可分为两个阶段，第一个阶段等待操作系统进行善后处理，第二个阶段释放主存。

补充：

  • 活跃就绪：是指进程在主存并且可被调度的状态。

  • 静止就绪（挂起就绪）：是指进程被对换到辅存时的就绪状态，是不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起就绪态进程具有更高的优先级，系统将把挂起就绪态进程调回主存并转换为活跃就绪。

  • 活跃阻塞：是指进程已在主存，一旦等待的事件产生便进入活跃就绪状态。

  • 静止阻塞：是指进程对换到辅存时的阻塞状态，一旦等待的事件产生便进入静止就绪状态。

静止xx，表示进程在辅存（外存）；活跃xx，表示进程在主存。

2. 进程控制块

1）PCB的定义

系统为每个进程定义了一个数据结构：进程控制块PCB（Process Control Block）。进程控制块是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB，在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。其作用是：

  • 进程创建、撤消；
  • 进程唯一标志；
  • 限制系统进程数目。

2）PCB的内容

  • 进程标识符：
    • 每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。
    • Linux系统中就是一个整型数。在进程创建时由系统赋予。
  • 程序和数据地址：
    • 把PCB与其程序和数据联系起来。
  • 当前状态：
    • 用于指明本晋城所处的状态。
  • 现场保护区：
    • 当进程因某种原因不能继续占用CPU时（等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。
  • 同步与同步机制：
    • 用于实现进程间互斥、同步和通信所需的信号量等。
  • 优先级：
    • 进程的优先级反映进程的紧迫程序，通常由用户指定和系统设置。
    • Linux系统采用用户设置和系统计算相结合的方式确定进程的优先级
  • 资源清单：
    • 列出所拥有的除CPU外的资源记录，如拥有的I/O设备，打开的文件列表等。
  • 链接字 ：
    • 根据进程所处的现行状态，进程相应的PCB参加到不同队列中。
    • 为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等
    • PCB链接字指出该进程所在队列中下一个进程PCB的首地址。
  • 其他信息：
    • 如进程记账信息，进程占用CPU的时间等。

在linux 中每一个进程都由task_struct 数据结构来定义，task_struct就是我们通常所说的PCB

PCB不但指出了进程的名称，而且标志了程序和数据集合的物理位置；不仅记录了系统管理进程所需要的各种控制信息，也给出了能够描述进程的瞬间特征的现场内容。只要有关程序修改相应进程的PCB的内容（状态字或调度信息等），就能动态地表达进程自身的状态变化以及它与外界环境的联系。

3）PCB的组织方式

  • 线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。
    • 这种方式适用于系统中进程数目不多的情况
image-20200917154535076
  • 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。
image-20200917154620717
  • 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等
image-20200917154656760

0x03 进程控制

进程控制的主要任务是创建和撤消进程，以及实现进程的状态转换，由内核来实现。

  • 进程的创建

    • 提交一个批处理作业
    • 用户登录
    • 由OS创建，用以向一用户提供服务
    • 由已存在的进程创建

  • 进程撤消

    • 用户退出登录
    • 进程执行一中止服务请求
    • 出错及失败因素
    • 正常结束
    • 给定时限到

1. 原语

原语是由若干条指令所组成的指令序列，用来实现某个特定的操作。

  • 指令序列执行是连续的，不可分割
  • 是操作系统核心（不是由进程而是由一组程序模块所组成）的一个组成部分
  • 必须在管态（内核态）下执行，且常驻内存

原语与广义指令（系统调用）都能被进程调用，二者的区别在于

  • 原语具有不可中断性。原语是通过在其执行过程中关闭中断实现的，且一般由系统进程调用。
    • 例如队列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行，就不能被中断。
  • 广义指令（系统调用）可由目态（用户态）下运行的进程调用，借助中断进入管态程序，然后转交给相应的系统进程实现其功能。
    • 例如文件的建立、打开、关闭、删除等。

引入原语的主要目的是为了实现进程的通信和控制。

2. 进程控制原语

1）创建原语

创建一个新进程的主要任务就是为进程建立一个PCB，将调用者的有关信息填入该PCB中。

  • 首先，根据进程名查找PCB表，若有同名，则非正常终止；否则，申请分配一块PCB空间。
  • 若进程的程序不再内存中，则应将它从外存调入内存，然后把有关信息（进程名、各信号量和状态位等）分别填入PCB的相应栏目中。
  • 把PCB链接到PCB链中。

2）撤销原语

进程撤销时，系统应及时回收它占有的全部资源。

  • 根据提供的进程名，在PCB链中查找对应的PCB，若找不到或该进程尚未停止，则转入异常终止作业处理；否则，从PCB链中撤销该进程及其所有子孙进程（这是因为如果仅撤销该进程可能导致其子进程与进程家族隔离开来，而成为难以控制的进程，类似野指针）。
  • 检查一下此进程是否有等待读取的消息，有则释放所有缓冲区，最后释放该进程的工作空间和PCB空间，以及其他资源。

值得注意的是，撤销原语撤销的是PCB，而不是进程的程序段。这是因为可能有多个进程共享该程序段。

3）阻塞原语

  • 首先中断处理机，停止进程运行，将CPU的现行状态存放到PCB的CPU状态保护区中；
  • 然后将该进程置为阻塞状态，并插入等待队列中。

4）唤醒原语

把除了处理机之外的一切资源都得到满足的进程置成就绪状态。

  • 首先找到被唤醒程序的内部名，让该进程脱离阻塞队列；
  • 将现行状态改为就绪状态，并插入就绪队列等待调度运行。

3. Fork()函数使用举例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <sys/types.h>
int glob = 6; /* external variable in initialized data */
int main(void)
{
    int var; /* automatic variable on the stack */
    pid_t fpid;
    var = 88;
    printf("before fork\n"); /* we don't flush stdout */
    
    if ( (fpid = fork()) < 0)
    	err_sys("fork error");
    else if (fpid == 0) { /* child */
    	glob++; /* modify variables */
    	var++;
    } else
        sleep(2); /* parent */
    
    printf(“pid = %d, glob = %d, var = %d\n", getpid(), glob, var);
    exit(0);
}

  • 在语句fpid=fork()之前，只有一个进程在执行这段代码，但在这条语句之后，就变成两个进程在执行了。

  • 在fork函数执行完毕后，如果创建新进程成功，则出现两个进程，一个是子进程，一个是父进程。

    • 在子进程中，fork函数返回0，在父进程中，fork返回新创建子进程的进程ID。
    • 我们可以通过fork返回的值来判断当前进程是子进程还是父进程

  • fpid的值为什么在父子进程中不同。

    • 其实就相当于链表，进程形成了链表，父进程的fpid指向子进程的进程id，因为子进程没有子进程，所以其fpid为0。
image-20200917162717194

0x04 线程的概念

1. 线程的引入

【案例】编写一个MP3播放软件。核心功能模块有三个：

（1）从MP3音频文件当中读取数据；

（2）对数据进行解压缩；

（3）把解压缩后的音频数据播放出来

image-20200917163725146

  • 进程的不足：

    • 进程的创建、撤销与切换需要付出较大的时空开销。
    • 进程只能在一个时间干一件事，如果想同时干两件事或多件事，进程就无能为力了。
    • 进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。

  • 引入线程的目的

    • 减小进程切换的开销
    • 提高进程内的并发程度
    • 共享资源

  • 线程：

    • 进程中的一个实体
    • 是一个CPU调度和分配的单位（可执行单元）
    • 基本上不拥有资源，只有必不可少的少量资源
    • 可以与其他同进程的线程共享进程拥有的所有资源
    • 将资源与计算分离，提高并发效率

  • 引入线程的好处：

    • 线程比进程轻量：容易创建、撤销
    • 有些应用要求并行实体共享同一个地址空间和所有可用数据的能力
    • 创建一个线程比一个进程快10-100倍
    • 对于存在大量计算和大量I/O处理的应用，大幅度提高性能
    • 在多CPU/多核CPU系统中更有优

2. 进程与线程的比较

image-20200917170629256

1）引入的目的（作用）

  • 引入进程好处：多个程序可以并发执行，改善资源使用率，提高系统效率

  • 引入线程好处：减少并发程序执行时所付出的时空开销，使得并发粒度更细、并发性更好

2）关系

  • 在传统的操作系统中，进程包含了两个概念：资源拥有者和可执行单元；
  • 在引入线程的操作系统中，把线程作为调度和分配的基本单元（可执行单元），而把进程作为资源拥有的基本单位。
  • 一个进程可以拥有多个线程，而一个线程同时只能被一个进程所拥有。
  • 线程不能单独执行，但是每一个线程都有程序的入口、执行序列以及程序出口，它必须组成进程才能被执行。

3）拥有资源

  • 进程拥有虚空间、进程映像、处理机保护、文件、I/O空间。

  • 线程共享进程的数据的同时，有自己额外的资源：运行状态、保存上下文（程序计数器）、执行栈、资源共享机制

image-20200917170548210

4）并发

  • 线程的划分尺度更小，并发性更高。

5）同步

  • 线程执行过程之中很容易进行协作同步，而进程需要通过消息通信进行同步。

3. 线程的实现方式

1）用户级线程：User level threads(ULT)

  • 用户级线程
    • 线程在用户空间，通过library模拟的thread，不需要或仅需要极少的kernel支持
    • 上下文切换比较快，因为不用更改page table等,使用起来较为轻便快速
    • 提供操控视窗系统的较好的解决方案
image-20200917171323224

  • 用户级的线程库的主要功能：

    • 创建和销毁线程
    • 线程之间传递消息和数据
    • 调度线程执行
    • 保存和恢复线程上下文

  • 典型的例子

    • POSIX Pthreads
    • Mach C-threads
    • Java Threads
image-20200917171159468
  • 用户级线程的优缺点
    • 优点
      • 线程切换与内核无关
      • 线程的调度由应用决定，容易进行优化
      • 可运行在任何操作系统上，只需要线程库的支持
    • 不足
      • 很多系统调用会引起阻塞，内核会因此而阻塞所有相关的线程。
      • 内核只能将处理器分配给进程，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行。

2）内核级线程：Kernel level threads (KLT)

  • 内核级线程
    • 内核级线程就是kernel有好几个分身,一个分身可以处理一件事.
    • 这用来处理非同步事件很有用, kernel可以对每个非同步事件产生一个分身来处理.
    • 支持内核线程的操作系统内核称作多线程内核
image-20200917171337292
  • 典型实现
    • Windows 2000/XP
    • OS/2
    • Linux
    • Solaris
    • Tru64 UNIX
    • Mac OS X
image-20200917171432940
  • 内核级线程的优缺点
    • 优点
      • 内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
      • 阻塞发生在线程级别
      • 内核中的一些处理可以通过多线程实现
    • 缺点
      • 一个进程中的线程切换需要内核参与， 线程的切换涉及到两个模式的切换（进程-进程、线程 -线程）
      • 降低效率

用户级线程和内核级线程的比较

  • 内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。

  • 用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言或用户库这一级处理的；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。

  • 用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断

  • 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。

  • 用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序

3）混合实现方式

  • 线程在用户空间创建和管理

  • 需要实现从用户空间的线程到内核空间线程（轻量级进程）的映射

image-20200917172615055

有些系统同时支持用户线程和内核线程由此产生了不同的多线程模型，即实现用户级线程和内核级线程的连接方式。

  • Many-to-One
  • One-to-One
  • Many-to-Many

Many-to-One Model

  • 将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。

  • 优点：

    • 线程管理是在用户空间进行的，因而效率比较高。

  • 缺点：

    • 当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；
    • 多个线程不能并行地运行在多处理机上
image-20200917173003214

One-to-one Model

  • 将每个用户级线程映射到一个内核级线程。
  • 优点：
    • 当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。
  • 缺点：
    • 每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能
image-20200917173051607

Many-to-Many Model

  • 将 n 个用户级线程映射到m 个内核级线程上，要求 m <= n。
  • 特点：在多对一模型和一对一模型中取了个折中，克服了多对一模型的并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。
image-20200917173147189

4. 思考：什么情况下不适合用多线程？

程序对执行顺序有要求时。

0x05 进程调度

1. 基本概念

1）进程调度的职能

进程调度亦可称为处理机调度，它的任务是协调和控制各进程对CPU的使用，即按照一定的策略（调度算法），从就绪队列中选择一个进程，并把CPU的控制权交给被选中的进程。

CPU调度需要解决的问题：

  • WHAT：按什么原则分配CPU —— 进程调度算法
  • WHEN：何时分配CPU —— 进程调度的时机
    • 正在运行的进程运行完毕
    • 运行中的进程要求I/O，或因其他某个原因被阻塞
    • 分配给运行进程的时间片已经用完
    • 执行某种原语操作
    • 一个优先级更高的进程申请运行（可抢占式）
  • HOW：如何分配CPU —— CPU切换过程（进程的上下文切换）
    • 在进程（上下文）中切换的步骤
      1. 保存处理器的上下文，包括程序计数器和其它寄存器；
      2. 用新状态和其它相关信息更新正在运行进程的PCB；
      3. 把进程移至合适的队列-就绪、阻塞；
      4. 选择另一个要执行的进程；
      5. 更新被选中进程的PCB；
      6. 从被选中进程中重装入CPU 上下文

2）调度的类型

高级调度

又称为“宏观调度”、“作业调度”。

  • 从用户工作流程的角度，一次提交的若干个作业，对每个作业进行调度。时间上通常是分钟、小时或天。
  • 接纳多少个作业；接纳哪些作业
中级调度

又称为“内外存交换”。

  • 从存储器资源的角度，将进程的部分或全部换出到外存上，将当前所需部分换入到内存。

    指令和数据必须在内存里才能被CPU直接访问。

低级调度

又称为“微观调度”、“进程或线程调度”。

  • 从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。

  • 低级调度又分为：

    • 非抢占式
    • 抢占式：时间片原则、优先权原则、短作业（进程）优先
CPU的三级调度
image-20200918102031401

3）调度的性能准则

从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。

面向用户的调度性能准则

  • 周转时间：作业从提交到完成（得到结果）所经历的时间 —— 批处理系统

    • 包括：外存等待时间、就绪等待时间、CPU执行时间、I/O操作时间，即在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待
    • 平均周转时间、带权平均周转时间（T/Ts)

  • 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间 —— 分时系统

  • 截止时间：开始截止时间和完成截止时间 —— 实时系统

    • 与周转时间有些相似。

  • 优先级：可以使关键任务达到更好的指标。

  • 公平性：不因作业或进程本身的特性而使上述指标过分恶化。

    • 如长作业等待很长时间。
面向系统的调度性能准则

  • 吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系 —— 批处理系统

    • 平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。
    • 如：在2小时内完成4个作业，而平均周转时间是1.25小时，则吞吐量是2个作业/小时

  • 处理机利用率：—— 大中型主机

  • 各种资源的均衡利用：如CPU繁忙的作业和I/O繁忙的作业搭配 —— 大中型主机

    • 繁忙指次数多，每次时间短
调度算法本身的调度性能准则
  • 易于实现
  • 执行开销比小

2. 设计调度算法的要点

1）进程优先级（数）

  • 优先级和优先数是不同的。
    • 优先级表现了进程的重要性和紧迫性；
    • 优先数实际上是一个数值，反映了某个优先级。
  • 静态优先级
    • 进程创建时指定，运行过程中不再改变
  • 动态优先级
    • 进程创建时指定了一个优先级，运行过程中可以动态变化。
    • 如：等待时间较长的进程可提升其优先级

2）进程优先级就绪队列的组织

  • 静态优先级排列

    • 创建多个进程后按照不同的优先级进行排列，CPU调度优先级较高的进程进行执行

  • 动态优先级排列

    • 所有进程创建之后都进入到第一级就绪队列，随着进程的运行，可能会降低某些进程的优先级。
    • 如某些进程的时间片用完了，那么就会将其降级

3）抢占式调度与非抢占式调度

  • 不可抢占式方式
    • 一旦处理器分配给一个进程，它就一直占用处理器，直到该进程自己因调用原语操作或等待I/O等原因而进入阻塞状态，或时间片用完时才让出处理器
  • 抢占式方式
    • 就绪队列中一旦有优先级高于当前运行进程优先级的进程存在时，便立即进行进程调度，把处理器转给优先级高的进程

4）进程的分类

第一种分类
  • I/O Bound（I/O密集型）
    • 频繁的进行I/O，通常会花费很多时间等待I/O操作完成
  • CPU bound（CPU密集型）
    • 计算量大，需要大量的CPU时间
image-20200918104150566
第二种分类
  • 批处理进程（Batch Process)
    • 无需与用户交互，通常在后台运行
    • 不需要很快的响应
    • 典型的批处理程序：编译器、科学计算
  • 交互式进程（Interactive Process)
    • 与用户交互频繁，因此要花很多时间等待用户输入
    • 响应时间要快，平均延迟要低于50~150ms
    • 典型的交互式进程：Word、触控型GUI
  • 实时进程（Real-time Process)
    • 有实时要求，不能被低优先级进程阻塞
    • 响应时间要短且要稳定
    • 典型的实时进程：视频/音频、控制类

5）时间片

时间片（Time slice或quantum），确定了允许该进程运行的时间长度，需要考虑如下因素：

  • 系统的响应时间。
    • 当进程数目一定时，时间片的长短直接影响系统的响应时间。
  • 就绪队列中进程的数目。
    • 当系统对响应时间要求一定时，就绪队列中进程数越少则时间片越长，否则可能会导致频繁的进程切换。（见时间片轮转算法RR）
    • 反之亦然。
  • 进程切换的开销。
  • CPU的处理能力。
  • 进程的行为。

2. 批处理系统的调度算法

  • 吞吐量：吞吐量 = 作业数 / 总执行时间}，即单位时间内CPU完成的作业数量
  • 周转时间：完成时刻 - 提交时刻
    • 平均周转时间 = 作业周转时间之和 / 作业数
  • 带权周转时间 = 周转时间 / 服务时间（执行时间）
    • 平均带权周转时间 = 作业带权周转时间之和 / 作业数

1）先来先服务 FCFS

先来先服务 FCFS(First Come First Serve)，这是最简单的调度算法，按先后顺序调度。

  • 按照作业提交或进程变为就绪状态的先后次序，分派CPU；

  • 当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。

  • 在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。

    这意思，似乎是等待事件发生后，直接插入到就绪队列的队头？

FCFS的特点

  • 比较有利于长作业，而不利于短作业。
  • 有利于CPU繁忙的作业，不利于I/O繁忙的作业

2）最短作业优先 SJF

最短作业优先 SJF(Shortest Job First)，又称为“短进程优先”SPN(Shortest Process Next)，这是对FCFS算法的改进，其目标是减少平均周转时间。

  • 对预计执行时间短的作业（进程）优先分派处理机。
  • 通常后来的短作业不抢占正在执行的作业

优点

  • 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
  • 提高系统的吞吐量；

缺点：

  • 对长作业非常不利，可能长时间得不到执行；
  • 未能依据作业的紧迫程度来划分执行的优先级；
  • 难以准确估计作业（进程）的执行时间，从而影响调度性能

3）最短剩余时间优先 SRTF

最短剩余时间优先 SRTF(Shortest Remaining Time First)，将短作业优先进行改进，改进为抢占式，这就是最短剩余时间优先算法了。

  • 即一个新就绪的进程比当前运行进程具有更短的完成时间，系统抢占当前进程，选择新就绪的进程执行。
image-20200918133624488

缺点：

  • 源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象。

4）最高响应比优先 HRRF

最高响应比优先 HRRF(Highest Response Ratio First)，算法实际上是FCFS算法和SJF算法的折衷，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改善了调度性能。

  • 响应比RP的计算时间

    • 每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响应比最高者投入运行

  • 响应比RP的计算方法

    • RP = (已等待时间 + 要求运行时间) / 要求运行时间 = 1 + 已等待时间 / 要求运行时间

  • 响应比最高优先（HRRF）算法效果：

    • 短作业容易得到较高的响应比
    • 长作业等待时间足够长后，也将获得足够高的响应比
    • 饥饿现象不会发生

  • 缺点：

    • 每次计算各道作业的响应比会有一定的时间开销，性能比SJF略差

3. 分时系统（交互式系统）的调度算法

1）时间片轮转 RR

时间片轮转(RR：Round Robin）算法主要用于微观调度（进程调度），设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。

  • 将系统中所有的就绪进程按照FCFS原则，排成一个队列。
  • 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
  • 在一个时间片结束时，发生时钟中断。
  • 调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
  • 进程可以未使用完一个时间片，就出让CPU（如阻塞）

时间片长度变化的影响：

  • 过长－> 退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。

  • 过短－> 用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长

image-20200918134633892

对响应时间的要求：

  • T(响应时间)=N(进程数目)*q(时间片)
  • 响应时间一定时
    • 就绪进程的数目越多，时间片越小
  • 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间，平均周转时间和平均带权周转时间延长

2）优先级算法

本算法平衡了各进程对响应时间的要求，适用于作业调度和进程调度，可分成抢占式和非抢占式。

这里教材上优先级算法分为了优先占有法和优先剥夺法两种类型：

  • 优先占有法（不可抢占式）：一旦某个最高优先级的就绪进程分得处理机后，只要不因为自身原因被阻塞（如要求I/O操作）而不能继续运行时，就一直运行下去，直至运行结束。
  • 优先剥夺法（抢占式）：无论何时（即使正在运行的进程其时间片未用完时），只要就绪队列中有一个比它优先级更高的进程，那么便可取而代之，而被剥夺的进程重新回到就绪队列。
静态优先级

创建进程时就确定，直到进程终止前都不改变，通常是一个整数。依据：

  • 进程类型（系统进程优先级较高）
  • 对资源的需求（对CPU和内存需求较少的进程，优先级较高）
  • 用户要求（紧迫程度和付费多少
动态优先级

在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能。如：

  • 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；
  • 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU

3）多级队列 MQ

多级队列（MQ：Multi-level Queue），本算法引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标。

  • 根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。
  • 不同队列可有不同的优先级、时间片长度、调度策略等；在运行过程中还可改变进程所在队列。
  • 如：系统进程、用户交互进程、批处理进程等

4）多级反馈队列 MFQ

多级反馈队列（MFQ： Multi-level Feedback Queue ），本算法是时间片轮转算法和优先级算法的综合和发展。

基本思想：

  • 设置多个就绪队列，分别赋予不同的优先级（如逐级降低），队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长（如逐级加倍）。
  • 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
  • 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。
  • 如果进程执行时有新进程进入较高优先级的队列，则抢占执行新进程，并把被抢占的进程投入原队列的末尾。
image-20200918140629937

优点：

  • 为提高系统吞吐量和缩短平均周转时间而照顾短进程
  • 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程
  • 不必估计进程的执行时间，动态调节

几点说明：

  • I/O型进程：让其进入最高优先级队列，以及时响应I/O交互，增大I/O设备利用率。
    • 通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。
  • 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
  • I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。

为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级

优先级倒置现象

高优先级进程（或线程）被低优先级进程（或线程）延迟或阻塞。

  • 例如：有三个完全独立的进程 Task A、Task B 和 Task C，Task A 的优先级最高，Task B 次之，Task C 最低。Task A 和 Task C 共享同一个临界资源 X。

image-20200918141852127

  • 执行情况如图：

    • t0时刻，C 占有处理机与临界资源X；
    • t1时刻，B 进入就绪队列，抢占处理机，C被迫进入就绪队列；
    • t2时刻，A进入就绪队列，抢占处理机，B被迫进入就绪队列；
    • t3时刻，当A到达临界区时，由于临界资源X已被C占有，不得不放弃处理机，进入阻塞状态，B获得处理机继续执行；
    • t4时刻，B执行完毕，此时A处于阻塞队列中，因而就绪队列内只有C，因而C获得处理机，继续执行；
    • t5时刻，C执行完毕，释放处理机和临界资源X，A获取临界资源X与处理机，继续执行；
    • t6时刻，A执行完毕。

  • All in all，Task A 和 Task C 共享同一个临界资源，高优先级进程 Task A 因低优先进程Task C 被阻塞，又因为低优先进程 Task B 的存在延长了被阻塞的时间。

解决办法 —— 优先级置顶

进程 Task C 在进入临界区后，Task C 所占用的处理机就不允许被抢占。这种情况下，Task C 具有最高优先级（Priority Ceiling） 。

image-20200918142427670

如果系统中的临界区都较短且不多，该方法是可行的。反之，如果 Task C 临界区非常长，则高优先级进程Task A 仍会等待很长的时间，其效果无法令人满意。

解决办法 —— 优先级继承

当高优先级进程 Task A 要进入临界区使用临界资源 X时，如果已经有一个低优先级进程 Task C 正在使用该资源，可以采用优先级继承（Priority Inheritance）的方法。

image-20200918142554667

此时一方面 Task A 被阻塞，另一方面由 Task C 继承Task A 的优先级，并一直保持到 Task C 退出临界区。

4. 实时系统的调度算法

实时系统

  • 实时系统是一种时间起着主导作用的系统。当外部的一种或多种物理设备给了计算机一个刺激，而计算机必须在一个确定的时间范围内恰当地做出反应。对于这种系统来说，正确的但是迟到的应答往往比没有还要糟糕。

  • 实时系统被分为硬实时系统和软实时系统。

    • 硬实时要求绝对满足截止时间要求（如：汽车和飞机的控制系统），而软实时倒是可以偶尔不满足（如：视频/音频程序）。

  • 实时系统通常将对不同刺激的响应指派给不同的进程（任务），并且每个进程的行为是可提前预测的

实时调度

  • 假设一任务集 S = {t1,t2,t3, …, tn}，周期分别是 T1,T2, …, Tn，执行时间为 c1, c2, …, cn，截至周期(deadline)为D1, D2, …, Dn，通常Di = Ti。CPU利用率：用 $U = \sum_1^n(ci/Ti)$ 表示；

  • 前提条件

    • 任务集（S）是已知的；
    • 所有任务都是周期性（T）的，必须在限定的时限（D）内完成；
    • 任务之间都是独立的，每个任务不依赖于其他任务；
    • 每个任务的运行时间（c）是不变的；
    • 调度, 任务切换的时间忽略不计

1）静态表调度 STS

静态表调度 STS （Static table-driven scheduling），通过对所有周期性任务的分析预测（到达时间、运行时间、结束时间、任务间的优先关系），事先确定一个固定的调度方案。

  • 特点：
    • 无任何计算，按固定方案进行，开销最小；
    • 无灵活性，只适用于完全固定的任务场景

2）单调速率调度 RMS

单调速率调度 RMS (Rate Monotonic Scheduling)，通过对系统资源利用率的计算来进行任务可调度性分析,

  • RMS已被证明是单处理器下的静态最优调度算法，开销小, 灵活性好, 是实时调度的基础性理论。

  • 特点

    • 任务的周期越小，其优先级越高，优先级最高的任务最先被调度
    • 如果两个任务的优先级一样，当调度它们时，RM算法将随机选择一个调度

3）最早截止时间优先算法 EDF

最早截止时间优先算法 EDF(Earliest Deadline First)。

  • 任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度。

  • 如果两个任务的优先级一样，当调度它们时，EDF算法将随机选择一个调度。

5. 多处理机调度

多处理机调度与单处理机调度的区别在于：

  • 注重整体运行效率（而不是个别处理机的利用率）；

  • 更多样的调度算法；

  • 多处理机访问OS数据结构时的互斥（对于享内存系统）。

  • 调度单位广泛采用线程

非对称式多处理系统(AMP)
  • AMP：Asymmetric Multi-Processor，指多处理器系统中，各个处理器的地位不同。
  • 主－从处理机系统，由主处理机管理一个公共就绪队列，并分派进程给从处理机执行。
  • 各个处理机有固定分工，如：执行OS的系统功能，I/O处理，应用程序。
  • 有潜在的不可靠性（主机故障造成系统崩溃）
对称式多处理系统(SMP)
  • SMP：Symmetric Multi-Processor，指多处理器系统中，各个处理器的地位相同。
  • 按控制方式，SMP调度算法可分为集中控制和分散控制。

下面所述静态和动态调度都是集中控制，而自调度是分散控制

  • 静态分配(static assignment)：

    • 每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。
    • 优点：调度算法开销小。
    • 缺点：容易出现忙闲不均。

  • 动态分配(dynamic assignment)：

    • 各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。
    • 可防止系统中多个处理器忙闲不均。

1）自调度

  • 自调度(self-scheduling)：

    • 各个CPU采用一个公共就绪队列，各个处理机自行在就绪队列中取任务。
    • 需要对就绪队列的数据结构进行互斥访问控制。
    • 是最常用的算法，实现时易于移植，采用单处理机的调度技术。

  • 优点：不需要专门的处理机从事任务分派工作。

  • 缺点: 当处理机个数较多（如十几个或上百个）时，对就绪队列的访问可能成为系统的瓶颈

2）成组调度

成组调度(gang scheduling)，将一个进程中的一组线程，每次分派时同时到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行。

  • 优点
    • 通常这样的一组线程在应用逻辑上相互合作，成组调度提高了这些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统吞吐量。
    • 每次调度可以完成多个线程的分派，在系统内线程总数相同时能够减少调度次数，从而减少调度算法的开销。

3）专用处理机调度

专用处理机调度(dedicated processor assignment)，为进程中的每个线程都固定分配一个CPU，直到该线程执行完成。

  • 缺点：线程阻塞时，造成CPU的闲置。
  • 优点：线程执行时不需切换，相应的开销可以大大减小，推进速度更快。
  • 适用场合：CPU数量众多的高度并行系统，单个CPU利用率已不太重要

0x06 进程通信

1. 同步与互斥问题

并发是OS的设计基础，也是所有（如，同步互斥）问题产生的原因。

进程（并发执行程序）的三个特征：

  • 并发：体现在进程的执行是间断性的；进程的相对执行速度是不可测的。（间断性）

  • 共享：体现在进程/线程之间的制约性（如共享打印机）。（非封闭性）

  • 不确定性：进程执行的结果与其执行的相对速度有关，是不确定的。（不可再现性）

并发执行，不可避免地产生了多个进程对同一个共享资源访问，造成了资源的争夺。

  • 竞争：两个或多个进程对同一共享数据同时进行访问，而最后的结果是不可预测的，它取决于各个进程对共享数据访问的相对次序。这种情形叫做竞争。
  • 竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关。
  • 临界资源：我们将一次仅允许一个进程访问的资源称为临界资源。
  • 临界区：每个进程中访问临界资源的那段代码称为临界区

1）进程的同步与互斥

  • 进程互斥（间接制约关系）：

    • 两个或两个以上的进程，不能同时进入关于同一组共享变量的临界区域，否则可能发生与时间有关的错误，这种现象被称作进程互斥。
    • 进程互斥是进程间发生的一种间接性作用，一般是程序不希望的。
    • 例如进程A、B共享一台打印机，若不加限制，则输出结果可能会混在一起。

  • 进程同步（直接制约关系）：

    • 系统中各进程之间能有效地共享资源和相互合作，有前后次序的等待关系，从而使程序的执行具有可再现性的过程称为进程同步。
    • 进程同步是进程间的一种刻意安排的直接制约关系。即为完成同一个任务的各进程之间，因需要协调它们的工作而相互等待、相互交换信息所产生的制约关系。
    • 例如，有一个单缓冲区为两个进程所共享，计算进程计算数据，打印进程输出计算结果。计算进程未完成计算则不能向缓冲区传送数据，此时打印进程未得到缓冲区的数据而无法输出打印结果。

2）同步与互斥的区别和联系

  • 互斥：某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。互斥无法限制访问者对资源的访问顺序，即访问是无序访问。
  • 同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有对资源的写入的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

3）机制设计上应遵循的准则

  • 空闲让进：临界资源处于空闲状态，允许进程进入临界区。如，临界区内仅有一个进程执行
  • 忙则等待：临界区有正在执行的进程，所有其他进程则不可以进入临界区
  • 有限等待：对要求访问临界区的进程，应在保证在有限时间内进入自己的临界区，避免死等。
  • 让权等待：当进程（长时间）不能进入自己的临界区时，应立即释放处理机，尽量避免忙等。

2. 基于忙等待的互斥方法

忙式等待：若while循环的循环条件成立，则进程将重复测试，直到条件为假，这种原地踏步被称为忙式等待。

1）软件方法

两个进程互斥的软件方法
Dekker算法
image-20200919155838430
Peterson算法
image-20200919160004420
N个进程互斥的软件方法
image-20200919160225829

进程互斥的软件实现算法有：Lamport面包店算法和Eisenberg算法。这两种算法均假定系统中进程的个数有限，如n个。

面包店算法

面包店算法（ Bakery Algorithm ）来源于顾客在面包店购买面包时的排队原理，即：顾客进入面包店前，首先抓取一个号码，然后按号码从小到大的次序依次进入面包店购买面包。

  • 基本思想：

    • 计算机系统中，顾客相当于进程，每个进程有一个唯一的标识，用Pi表示，对于Pi和Pj，若有i<j，即Pi先进入临界区，则先为Pi服务。
    • 设置一个发号器，按由小到大的次序发放号码，进程进入临界区前先抓取一个号码，然后按号码从小到大的次序依次进入临界区。
    • 若多个进程抓到相同的号码则按字典序排序。
      • 字典序：(a, c) < (b, d) -> (a < c) or ((a == c) and (b < d))

  • 数据结构：

1
2
3
int choosing[n]; 	// 表示进程是否正在抓号，初值为0。若进程i正在抓号，则 choosing[i]=1.

int number[n]; 		// 记录进程抓到的号码，初值为0。 若 number[i]=0，则进程i没有抓号.
  • 算法实现：
image-20200919161829696
  • 算法说明：
    • 当进程Pi计算完max(…)+1但尚未将值赋给number[i]时，进程Pj中途插入，计算max(…)+1，得到相同的值。在这种情况下，i和j可保证编号较小的进程先进入临界区，并不会出现两个进程同时进入临界区的情况。
Eisenberg算法

似乎不是重点，略…

2）硬件方法

硬件方案1：中断屏蔽

  • 中断屏蔽方法：使用“开关中断”指令。

    • 执行“关中断”指令，进入临界区操作；
    • 退出临界区之前，执行“开中断”指令。

  • 优点：简单

  • 缺点：

    • 不适用于多CPU系统：往往会带来很大的性能损失；
    • 单处理器使用：很多日常任务，都是靠中断的机制来触发的，比如时钟，如果使用屏蔽中断，会影响时钟和系统效率，而且用户进程的使用可能很危险！

  • 使用范围：内核进程（少量使用）

硬件方案2：使用test and set指令

TS（test-and-set ）是一种不可中断的基本原语（指令），它会写值到某个内存位置并传回其旧值。

在多进程可同时存取内存的情况下，如果一个进程正在执行TS，在它执行完成前，其它的进程不可以执行TS。

Test and Set指令

  • IBM370系列机器中称为TS；
  • 在INTEL8086中称为TSL；
  • MIPS中ll和sc指令
  • 语义
1
2
3
4
5
TestAndSet(boolean_ref lock) { 
    boolean initial = lock; 
    lock = true; 
    return initial; 
}
自旋锁Spinlocks
  • 利用test_and_set硬件原语提供互斥支持
  • 通过对总线的锁定实现对某个内存位置的原子读与更新
image-20200919164347804 image-20200919164449104
硬件方案3：使用swap指令

Swap（对换）指令与TSL指令一样，是不会被中断的原子指令，其功能是交换两个字的内容。

  • 语义：
1
2
3
4
5
6
Swap(boolean *a, Boolean *b) {
    Boolean temp;
    Temp = *a;
    *a = *b;
    *b = temp;
}
image-20200919164836611

采用Swap指令与采用TSL指令类似，也会由于循环对换两个变量，造成忙等的情况。

3）几个算法的共性问题

无论是软件解法（如Peterson）还是硬件（如TSL或XCHG）解法都是正确的，但它们都有一些共性问题：

  1. 忙等待

当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止，白白耗费CPU资源。

  1. 优先级反转

低优先级进程先进入临界区，高优先级进程一直忙等

  • 初始条件：greenbusy=redbusy=false
image-20200919163141490

3. 基于信号量的同步方法

同步中，进程经常需要等待某个条件的发生，如果使用忙等待的解决方案，势必浪费大量CPU时间。

解决方法：将忙等变为阻塞，可使用两条进程间的通信原语：Sleep和Wakeup

  • Sleep原语将引起调用进程的阻塞，直到另外一个进程用

  • Wakeup原语将其唤醒。很明显，wakeup原语的调用需要一个参数——被唤醒的进程ID。

e.g. 银行排队：

  • 忙等：看到队很长，坚持排队
  • 阻塞：看到队很长，先回家歇会儿（sleep），有空柜台了，大堂经理（scheduler）电话通知再过来（wakeup）。

1）信号量

信号量是Dijkstra于1965年提出的一种方法，它使用一个整型变量来累计唤醒次数，称作信号量（semaphore）。

  • 信号量是一类特殊的变量，程序对其访问都是原子操作，且只允许对它进行P(信号变量)和V(信号变量)操作。
信号量的定义

信号量：一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。

  • s为正，则该值等于发P操作后可立即执行的进程的数量（或资源的个数）；

  • s为0，那么发出P操作后进程被继续执行完；

  • s为负，那么发出P操作后的进程被阻塞，│s│是被阻塞的进程数（或等待进程的个数）。

  • q是一个初始状态为空的队列，当有进程被阻塞时就会进入此队列。

信号量的分类

  • 二元信号量和一般信号量

    • 二元信号量：取值仅为“0”或“1”，主要用作实现两个进程的互斥；
    • 一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题。

  • 强信号量和弱信号量

    • 强信号量：进程从被阻塞队列释放时采取FIFO
      • Guarantee freedom from starvation
    • 弱信号量：没有规定进程从阻塞队列中移除顺序
      • Will not guarantee freedom from starvation

2）信号量的操作：PV操作

  • Dijkstra建议设立两种操作，P(S)和V(S)操作。
    • P操作分配资源，V操作释放资源。
    • P操作也称为semWait或Down操作，V操作也称为semSignal或Up操作。
  • PV操作属于进程的低级通信。
二元信号量机制
1
2
3
4
5
6
7
P(S):
    while S <= 0 
        do skip
    S := S-1;

V(S):
    S := S+1;

应用时应注意：

  • 每个进程中用于实现互斥的P、V操作必须成对出现，先做P操作，进临界区，后做V操作，出临界区。
  • P、V操作应分别紧靠临界区的头尾部，临界区的代码应尽可能短，不能有死循环。
  • 互斥信号量的初值一般为1.
一般信号量机制

信号量的数据结构，包含:

  • 一个初始值为正的整数: s.count
  • 一个初始为空的队列: s.queue
1
2
3
4
struct semaphore {
    int count;
    queueType queue;
}

在其上定义了三个原子操作

  • 初始化操作

    • 一个信号量可能被初始化为一个非负整数

  • semWait 操作（P操作、Down操作）

    • S := S-1
    • 若 S < 0，则表示已无资源，执行semWait的进程被阻塞；
    • 若S >= 0，则表示有资源，该进程继续执行。

  • semSignal操作（V操作、Up操作）

    • S := S+1
    • 若 S > 0，则该进程继续执行；
    • 若S <= 0，则释放S信号量队列的排头等待着并清除其阻塞状态，即从阻塞态变为就绪态，等待V(S)者继续执行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void semWait(semaphore s) {
	s.count--;
    if (s.count < 0) {
        /* place this process in s.queue*/
        /* block this process */
    }
}

void semSignal(semaphore s) {
    s.count++;
    if (s.count <= 0) {
        /* remove a process P from s.queue */
        /* place process P on ready list */
    }
}
image-20200919175633090

3）信号量在并发中的典型应用

应用 描述
互斥（Mutual exclusion） 可以用初始值为1的信号量来实现进程间的互斥。一个进程在进入临界区之前执行semWait操作，退出临界区后再执行一个semSignal操作。
这是实现临界区资源互斥使用的一个二元信号量。
有限并发（Bounded concurrency） 是指有n（1≤n≤c，c是一个常量）个进程并发的执行一个函数或者一个资源。
一个初始值为c的信号量可以实现这种并发。
进程同步（Synchronization） 是指当一个进程Pi想要执行一个ai操作时，它只在进程Pj执行完aj后，才会执行ai操作。
可以用信号量如下实现：将信号量初始为0，Pi执行ai操作前执行一个semWait操作；而Pj执行aj操作后，执行一个semSignal操作。

3）应用：基本同步模式——汇合 (Rendezvous)

使用信号量实现两个线程在执行过程中一点汇合(Rendezvous)，直到两者都到后才能继续执行。

  • 条件：
    • a1永远在b2之前，而b1永远在a2之前
    • a1和b1的次序不加限制
image-20200919185306221
  • 解决
    • 定义两个信号量，aArrived, bArrived,并且初始化为0，表示a和b是否执行到汇合点。
image-20200919185341731

4）泛化：多进程同步原语——屏障Barriers

对rendezvous进行泛化，使其能够用于多个线程，可用于进程组的同步。

  • 科学计算中的迭代
  • 深度学习的卷进神经网络迭代
  • GPU编程中的渲染算法迭代

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
n = the number of threads
count = 0				// count记录到达汇合点的线程数
mutex = Semaphore(1)	// mutex保护count
barrier = Semaphore(0)	// barrier在当所有线程到达之前都是0或者负值，到达后取正值
    
mutex.wait()
count = count + 1
mutex.signal()
    
if count == n: 
	barrier.signal() 	// 唤醒一个线程
barrier.wait()
barrier.signal() 		// 一旦线程被唤醒，有责任唤醒下一个线程

5）拓展：信号量集机制

当利用信号量机制解决了单个资源的互斥访问后，我们讨论如何控制同时需要多个资源的互斥访问。

  • 信号量集是指同时需要多个资源时的信号量操作。
    • “AND型”信号量集
    • 一般信号量集
AND型信号量集机制

  • 基本思想：将进程需要的所有共享资源一次全部分配给它，待该进程使用完后再一起释放。

  • 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
P(S1, S2, ..., Sn):
	if (S1 >= 1 and S2 >= 1 and ... and Sn >= 1) then
		for i := 1 to n do 
			Si := Si - 1
		endfor
	else
		wait in Si
	endif

V(S1, S2, ..., Sn):
	for i := 1 to n do
		Si := Si + 1
		wake waited process
	endfor
一般“信号量集”机制
  • 基本思想：在AND型信号量集的基础上进行扩充
    • 进程对信号量Si的测试值为ti（用于信号量的判断，即Si >= ti，表示资源数量低于ti时，便不予分配）
    • 占用值为di（用于信号量的增减，即Si = Si - di和Si = Si +di）
  • 几个例子：
    • SP(S, d, d)：表示每次申请d个资源，当资源数量少于d个时，便不予分配。
    • SP(S, 1, 1)：表示互斥信号量。
    • SP(S, 1, 0)：可作为一个可控开关
      • 当 S≥1 时，允许多个进程进入临界区；
      • 当 S=0 时，禁止任何进程进入临界区。
  • 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
P(S1, t1, d1, ..., Sn, tn, dn):
	if (S1 >= t1 and S2 >= t2 and ... and Sn >= tn) then
		for i := 1 to n do 
			Si := Si - di
		endfor
	else
		wait in Si
	endif

V(S1, S2, ..., Sn):
	for i := 1 to n do
		Si := Si + di
		wake waited process
	endfor

6）总结：P、V操作的优缺点

  • 优点：

    • 简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）

  • 缺点：

    • 不够安全；
    • P.V操作使用不当会出现死锁；
    • 遇到复杂同步互斥问题时实现复杂。

4. 结构化的同步/互斥机制——管程

1）管程的概念

1973年，Hoare和Hanson所提出， “一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据”。

建立管程的基本理由是：

由于对临界区的执行分散在各进程中，这样不便于系统对临界资源的控制和管理，也很难发现和纠正分散在用户程序中的对同步原语的错误使用等问题。

为此，应把分散的同类临界区集中起来，并为每个可共享资源设立一个专门的管程来统一管理各进程对该资源的访问。这样既便于系统管理共享资源，又能保证互斥访问。

管程 (Monitor)**是在程序设计语言当中引入的一个成分，是一种高级同步机制**，由以下四部分组成：

  1. 管程的名称；
  2. 局部于该管程内部的共享数据，这些数据表示了相应资源的状态；
  3. 局部域该管程内部的若干过程，每个过程完成关于上述数据的某种规定（互斥）操作；
  4. 对局部于管程内部的共享数据的初始化语句。

作为一种同步机制，管程要解决的问题：

  • 互斥：

    • 管程每次只允许一个进程进入其内（即访问管城内的某个过程），即管程进入是互斥的。这是由编译系统来保证的（管程是一个语言机制 ）。

  • 同步：

    • 通过设置条件变量（CV） 以及在条件变量上实施的 wait 和 signal 操作，它可以使一个进程或线程，当条件不满足/满足的时候在条件变量上等待/唤醒。

2）条件变量

为了区别等待的不同原因，管程引入了条件变量及其操作。

  • 不同的条件变量，对应不同原因的进程阻塞等待队列，初始时为空。
  • 条件变量上能作 wait 和 signal 原语操作，若条件变量名为X，则调用同步原语的形式为 wait(X) 和 signal(X)。

条件变量与信号量的区别

  • 条件变量的值不可增减（“没有值的”），P-V操作的信号量值可增减（“有值的”）

    • wait操作一定会阻塞当前进程；但P操作只有当信号量的值小于0时才会阻塞。
    • 如果没有等待的进程，signal将丢失；而V操作增加了信号量的值，不会丢失。

  • 访问条件变量必须拥有管程的锁

3）多个进程同时在管程中出现

  • 场景：

    • 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权。
    • 当后面进入管程的进程执行唤醒操作时（例如P唤醒Q），管程中便存在两个同时处于活动状态的进程。

  • 三种处理方法：

    • P等待Q执行（Hoare管程）；
    • Q等待P继续执行（MESA管程）；
    • 规定唤醒操作为管程中最后一个可执行的操作（Hansen管程，并发pascal）

4）Hoare管程（没搞明白）

几个定义

  • **入口等待队列(entry queue)**：因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。

  • 紧急等待队列：如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继续，…，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程（已被唤醒，但由于管程的互斥进入而等待），因而还需要有一个进程等待队列，这个等待队列被称为紧急等待队列。它的优先级应当高于入口等待队列的优先级。

Hoare管程的条件变量
  • 由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量—-条件变量。　
  • 每个条件变量表示一种等待原因，并不取具体数值——相当于每个原因对应一个队列。
Hoare管程的同步原语
  • 同步操作原语wait和signal：针对条件变量x，x.wait()将自己阻塞在x队列中，x.signal()将x队列中的一个进程唤醒。
    • **x.wait()**：
      • 如果紧急等待队列非空，则唤醒第一个等待者；
      • 否则释放管程的互斥权，执行此操作的进程排入x队列尾部。
    • **x.signal()**：
      • 如果x队列为空，则相当于空操作，执行此操作的进程继续；
      • 否则唤醒第一个等待者，执行x.signal()操作的进程排入紧急等待队列的尾部。
    • 紧急等待队列与x队列的关系：紧急等待队列是由于管程的互斥进入而等待的队列，而x队列是因资源被占用而等待的队列。　
Hoare管程的信号量

  • 每个管程必须提供一个用于互斥的信号量 mutex（初值为1）。

    • 进程调用管程中的任何过程时，应执行P(mutex)；进程退出管程时应执行V(mutex)开放管程，以便让其他调用者进入。
    • 为了使进程在等待资源期间，其他进程能进入管程，故在wait操作中也必须执行V(mutex)，否则会妨碍其他进程进入管程，导致无法释放资源

  • 对每个管程，引入信号量next（初值为0）。

    • 凡发出signal操作的进程应该用P(next)挂起自己，直到被释放进程退出管程或产生其他等待条件。
    • 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。
    • next-count（初值为0），用来记录在next上等待的进程个数。

  • 引入信号量x-sem（初值为0）。

    • 申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源。
    • 执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现。
    • 用计数器x-count（初值为0）记录等待资源的进程数。
Hoare管程的实现
image-20200919194522747

5. 进程通信（IPC）的主要方法

进程间通信(Inter-Process-Comm)

  • 低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。

    • 缺点：
      • 传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。
      • 编程复杂：用户直接实现通信的细节，编程复杂，容易出错。

  • 高级通信：适用于分布式系统，基于共享内存的多处理机系统，单处理机系统，能够传送任意数量的数据，可以解决进程的同步问题和通信问题，主要包括三类：管道、共享内存、消息系统。

1）无名管道（Pipe）及命名管道（Named pipe或FIFO）

无名管道（Pipe）

  • 管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；

  • 只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）；

  • 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在在内存中。

  • 数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

image-20200920080548019
有名管道（Named Pipe或FIFO）

  • 无名管道应用的一个重大限制是它没有名字，因此，只能用于具有亲缘关系的进程间通信，在有名管道提出后，该限制得到了克服。

  • FIFO不同于管道之处在于它提供一个路径名与之关联，以FIFO的文件形式存在于文件系统中。

    • 这样，即使与FIFO的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过FIFO相互通信（能够访问该路径的进程以及FIFO的创建进程之间），因此，通过FIFO不相关的进程也能交换数据。

  • FIFO严格遵循先进先出（first in first out），对管道及FIFO的读总是从开始处返回数据，对它们的写则把数据添加到末尾。

2）消息队列（Message）

几个定义
  • 消息：指进程之间以不连续的成组方式发送的信息。
  • 消息缓冲区：指包含有指向发送进程的指针、指向消息接收进程的指针、指向下一个消息缓冲区的指针、消息长度、消息内容等信息的一个缓冲区。这个缓冲区构成了进程通信的一个基本单位。
实现方式
  • 每个进程都设置一个消息队列，当来自其他一些进程的消息传递给它时，就需要将这些消息链接成队列。
    • 其队列头由接收进程的PCB的队列指针指出；
    • 队列中的消息数量可由PCB中设置的信号量sm等级。
  • 当处理完一个消息之后，接收进程在同一缓冲区中向发送进程回送一个“回答信号”。
  • 每当发送进程发来一个消息，并将它挂载接收进程的消息队列上时，便在sm上执行V操作；
  • 而当接收进程需从消息队列中读取一个消息时，先对sm执行P操作，再从队列中移出已经读过的消息。
消息传递——两个通信原语（感觉有点问题）

  • 信号量的使用

    • buf-empty 初值为N，remaining可申请缓冲区的个数
    • buf-full 初值为0，相当于sm，表示当前进程消息队列中的消息数量
    • mutex1 初值为1
    • mutex2 初值为1

  • send (destination, &message)：send原语用来发送消息。

    • 首先查找接收进程的PCB，如果不存在，则由系统给出一个“哑”回答；
    • 如果接收进程存在，则申请一个存放消息的缓冲区；
      • 如果接收此消息的进程曾因等待此消息的到来而处于阻塞状态，此时就唤醒此进程。
    • 把消息的内容、发送原语的进程名和消息等，复制到刚刚申请的存放消息的缓冲区中；
    • 将该缓冲区连接到接收进程的PCB上；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Send(destination, &message)
{
	根据destination找接收进程，若未找到，则出错返回;
	
	P(buf-empty) // 申请空缓冲区;
	P(mutex1)
		取空缓冲区;
	V(mutex2)
	
	把消息从messsage处复制到空缓冲区;
	P(mutex2)
		把消息缓冲区挂到接收进程的消息队列;
	V(mutex2)
	
	V(buf-full)
}
  • receive(source, &message)：receive原语用来读取消息。
    • receive原语把消息缓冲区中的消息内容、消息长度以及发送进程的名称都读取到接收区；
    • 然后把消息缓冲区从链表中去掉，并释放消息缓冲区；
    • 如果没有消息可读取，则阻塞接收进程，直至消息发送来位置。
1
2
3
4
5
6
7
8
9
10
11
12
Receive(source, &message)
{
	P(mutex1)
		把消息从消息缓冲区复制到source的接收区;
	V(mutex1) 
	
	P(mutex2)
		把消息缓冲区从接收进程的消息队列释放
	V(mutex2)
	
    P(buf-full)
}

3）共享内存（Shared memory）

共享内存是最有用的进程间通信方式，也是最快的IPC形式（因为它避免了其它形式的IPC必须执行的开销巨大的缓冲复制）。两个不同进程A、B共享内存的意义是，同一块物理内存被映射到进程A、B各自的进程地址空间。

  • 当多个进程共享同一块内存区域，由于共享内存可以同时读但不能同时写，则需要同步机制约束（互斥锁和信号量都可以）。

  • 共享内存通信的效率高（因为进程可以直接读写内存）。

  • 进程之间在共享内存时，保持共享区域直到通信完毕

image-20200920085820602

4）信号量（Semaphore）

5）套接字（Socket）

6）信号（Signal）

6. 经典的进程同步与互斥问题

1）生产者－消费者问题(the producer-consumer problem)

问题描述

若干进程通过有限的共享缓冲区交换数据。其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；任何时刻只能有一个进程可对共享缓冲区进行操作。

image-20200920091350137
问题分析

  • 两个隐含条件：

    1. 消费者和生产者数量不固定。
    2. 消费者和生产者不能同时使用缓存区。

  • 行为分析：

    • 生产者：生产产品，放置产品(有空缓冲区)。
    • 消费者：取出产品(有产品)，消费产品。

  • 行为关系：

    • 生产者之间：互斥(放置产品)
    • 消费者之间：互斥(取出产品)
    • 生产者与消费者之间：互斥(放/取产品) 同步(先放置——后取出)
P/V操作

  • 信号量设置：

    • semaphore mutex = 1; //公共信号量，用于实现临界区互斥

    • semaphore empty = N; //指示空闲数量

    • semaphore full = 0; //指示产品数量

      实际上，full和empty是同一个含义：full + empty == N

  • 基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
生产者 
{
	P(empty)
	P(mutex)
		one >> buffer
	V(mutex)
	V(full)
}

消费者
{
	P(full)
	P(mutex)
		one << buffer
	V(mutex)
	V(empty)
}
  • 完整的伪代码写法
    • in 空缓冲块序号头指针；
    • out 满缓冲块序号头指针；
image-20200920092317891
采用Sleep和Wakeup原语的方法
采用管程的方法
采用AND信号集

2）读者－写者问题(the readers-writers problem)

问题描述

对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个。即：“读－写”互斥，“写－写”互斥，“读－读”允许。

image-20200920100028526
问题分析

  • 读进程的行为：

    • 系统中会有多个读进程同时访问共享数据。
    • 可分为三类：第一个进入的读进程(占有资源)，最后一个离开的读进程(释放资源)和其他读进程。
    • 需要设置一个计数器readcount来记录读进程的数目。

  • 写进程的行为：

    • 排他性的使用资源。

  • 确定同步与互斥关系：

    • 读者-读者：共享Data, 互斥访问readcount
    • 读者-写者：互斥访问Data
    • 写者-写者：互斥访问Data

  • 确定临界资源：

    • Data, readcount
P/V操作

  • 信号量设置：

    • int readcount=0; //“正在读”的进程数，初值是0。
    • semaphore rmutex=1; //信号量，用于readcount的互斥。
    • semaphore fmutex=1; //信号量，用于Data访问的互斥。

  • 基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
Writer
{
	P(fmutex)
		writing...
	V(fmutex)
}

Reader
{
	P(rmutex)	// 对readcount互斥
        if readcount == 0 then
            P(fmutex)	// 第一个申请使用data资源
        readcount = readcount + 1
	V(rmutex)
	
	reading...
	
	P(rmutex)
		readcount = readcount - 1
		if readcount == 0 then
			V(fmutex)	// 最后一个释放data资源
	V(rmutex)
}
对读者有利的算法
  • 写者必须确保
    • 没有正在读的读者和正在写的写者，才能开始写
    • 开始写后，其他写者、读者均不可进入
  • 读者必须确保
    • 从第一个读者开始读，到最后一个读者结束读之间不允许有写进程进入写过程。
对写者有利的算法

  • 信号量设置：

    • int readcount=0; //“正在读”的进程数，初值是0。
    • int writecount=0; //“正在读”的进程数，初值是0。
    • semaphore mutex1=1; //信号量，用于readcount的互斥。
    • semaphore mutex2=1; //信号量，用于writecount的互斥。
    • semaphore wmutex = 1;//信号量，用于同步，当有写者等待时，读者必须被阻塞。
    • semaphore rw = 1; //信号量，用于对Data的互斥访问

  • 基本框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
int readcount=0; 		//“正在读”的进程数，初值是0。
int writecount=0; 		//“正在读”的进程数，初值是0。
semaphore mutex1=1;   	//信号量，用于readcount的互斥。
semaphore mutex2=1;   	//信号量，用于writecount的互斥。
semaphore rw = 1;       //信号量，用于对Data的互斥访问
semaphore wmutex = 1;	//信号量，用于同步，当有写者等待时，读者必须被阻塞。

Reader
{
	while(true) {
        P(wmutex)	// 当有写者在等待时，阻塞读者
        P(mutex1)	// 对readcount互斥
            if readcount == 0 then
                P(rw)	// 第一个申请使用data资源
            readcount = readcount + 1
        V(mutex1)
		V(wmutex)	// 释放资源，允许读者或写者进入：
                	//         对于读者，wmutex只是走个过场
                	//         对于写者，获得wmutex锁后还要进一步获得rw锁才可进行写操作
                
        reading...	// 执行读操作

        P(mute1)
            readcount = readcount - 1
            if readcount == 0 then
                V(rw)	// 最后一个释放data资源
        V(mutex1)
    }
}

Writer
{
	while(true) {
        P(mutex2)
            if(writecount == 0) then
                P(wmutex)	// 获得wmutex锁，说明已有写进程在队列中或正在写
             writecount = writecount + 1
        V(mutex2)
        
        P(rw)
        	writing...	// 执行写操作
        V(rw)
                
        P(mutex2)
        	writecount = writecount - 1
            if(writecount == 0) then
                V(wmutex)
        V(mutex2)
    }
}

3）哲学家进餐问题(the dining philosophers problem)

问题描述

（由Dijkstra首先提出并解决）

  • 5个哲学家围绕一张圆桌而坐，桌子上放着5支筷子，每两个哲学家之间放一支；
  • 哲学家的动作包括思考和进餐：
    • 进餐时需要同时拿起他左边和右边的两支筷子；
    • 思考时则同时将两支筷子放回原处。
  • 如何保证哲学家们的动作有序进行？
    • 如：不出现相邻者同时要求进餐；不出现有人永远拿不到筷子
解题思路
  • 至多只允许四个哲学家同时（尝试）进餐，以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。设置信号量room=4。（破除资源互斥）
  • 对筷子进行编号，奇数号先拿左，再拿右；偶数号相反。（破除循环等待）
  • 同时拿起两根筷子，否则不拿起。（破除保持等待）

7. 进程同步/互斥类问题的求解

解题步骤：

  • 分析问题，确定哪些操作是并发的。在并发的操作中，哪些是互斥的，哪些是同步的。

    • 多个进程操作同一个临界资源就是互斥
    • 多个进程要按一定的顺序执行就是同步

  • 根据同步和互斥规则设置信号量，说明其含义和初值；

  • 用P、V操作写出程序描述。

0x07 死锁

1. 死锁的原因和必要条件

1）死锁的概念

由于资源占用的互斥，当某个进程提出资源申请之后，使得一些进程在无外力协助的情况下，永远分配不到必需的资源而无法运行。

2）死锁的原因

  • 竞争资源
    • 可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。 如CPU，内存
    • 非可剥夺资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放。如磁带机、打印机
    • 临时性资源：这是指由一个进程产生，被另一个进程使用，短时间后便无用的资源，故也称为消耗性资源。如消息、中断
  • 进程的推进顺序（并发执行的顺序不当）

3）死锁发生的四个必要条件

  • 互斥条件：
    • 指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
  • 请求和保持条件：
    • 指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
  • 不剥夺条件：
    • 指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
  • 环路等待条件：
    • 指在发生死锁时，必然存在一个进程——资源的环形链，即前一个进程占有的资源正式后一进程所需求的资源。
    • 如：进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源。

4）活锁与饥饿

  • 活锁（livelock）：是指任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。

    • 活锁和死锁的区别在于：
      • 处于活锁的实体是在不断的改变状态，即所谓的“活”，而处于死锁的实体表现为等待；
      • 活锁有可能自行解开，死锁则不能。
      • 避免活锁的简单方法是采用先来先服务的策略。

  • 饥饿（starvation）：某些进程可能由于资源分配策略的不公平导致长时间等待。

    • 当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿.
    • 当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)

5）处理死锁的方法

打破四个必要条件的其中之一即可。

image-20200920111249842

2. 预防死锁

死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生。

1）打破互斥条件

即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等，这是资源本身的属性。

2）打破请求和保持条件

可以实行资源预先分配策略：只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程，否则不分配任何资源。

但是，这种策略也有如下缺点：

  1. 在许多情况下，由于进程在执行时是动态的，不可预测的，因此不可能知道它所需要的全部资源。
  2. 资源利用率低。无论资源何时用到，一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被用到一次，但该进程在生存期间却一直占有，这显然是一种极大的资源浪费。
  3. 降低进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数就必然少了。

3）打破不可剥夺条件

即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，当不能立即被满足时，须释放所占有的全部资源，以后再重新申请。

但该策略存在如下缺点：

这种预防死锁的方法实现起来困难，会降低系统性能。

4）打破环路等待条件

实行资源有序分配策略。即把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路。

  • 如哲学家就餐问题中，奇数先拿左边的，而偶数先拿右边的筷子。

但该策略存在如下缺点：

  1. 限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销；
  2. 为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。

3. 避免死锁

死锁的避免是排除死锁的动态策略，它不限制进程有关资源的申请，而是对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。

即分配资源时判断是否会出现死锁，有则加以避免。如不会死锁，则分配资源。

  • 死锁避免不那么严格限制产生死锁的四个必要条件（区别于死锁预防）

1）安全序列

  • 安全序列的定义：所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列{P1，P2，…，Pn}就是安全序列。

  • 如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。

  • 安全序列{P1，P2，…，Pn}是这样组成的：若对于每一个进程Pi，它需要的附加资源可以被系统中当前可用资源加上所有进程Pj当前占有资源之和所满足，则{P1，P2，…，Pn}为一个安全序列。

2）安全状态

  • 安全状态：系统存在一个进程执行序列<p1,p2,…pn>可顺利完成

  • 不安全状态：不存在可完成的序列

    • 必要非充分：系统进入不安全状态（四个死锁的必要条件同时发生）也未必会产生死锁。当然，产生死锁后，系统一定处于不安全状态。
image-20200920112223844

3）银行家算法

当一个进程申请使用资源的时候，银行家算法通过先 试探 性的讲资源分配给该进程，然后通过安全性算法判断分配后的系统是否处于安全状态，若不安全则试探分配作废，让该进程继续等待。

数据结构

  • n为进程数量，m为资源类型数量

  • 可利用资源向量Available：m维向量

    • 具有m个元素的向量，其中每一个元素代表一类可利用的资源数目，其初值是系统中所配置的该类全部可用资源数目。
    • 如果 $Available[j] = k$， 表示系统中现有Rj类资源k个。

  • 最大需求矩阵Max： n×m矩阵

    • 定义了系统中n个进程中的每一个进程对m类资源的最大需求。
    • 如果 $Max(i, j) = k$，表示进程i 需要 Rj 类资源的最大数目为k

  • 分配矩阵Allocation： n×m矩阵

    • 定义了系统中每一类资源当前已分配给每一进程的资源数。如果 $Allocation(i, j) = k$， 表示进程i 当前已分得 Rj 类资源k个。

  • 需求矩阵Need： n×m矩阵

    • 表示每一个进程尚需的各类资源数。
    • 如果 $Need(i, j) = k$， 表示进程i还需要Rj类资源k个，方能完成其任务。
    • $Need(i, j) = Max(i, j) - Allocation(i, j)$
算法流程

设 $Request_i$ 是进程 $P_i$ 的请求向量，如果进程 $P_i$ 需要K个 $R_j$ 类资源，当 $P_i$ 发出资源请求后，系统按下述步骤进行检查：

  1. 如果 $Request_i ≤ Need_i$ ，则转向步骤2；否则，表示它所需要的资源数已超过它所宣布的最大值，error。

  2. 如果 $Request_i ≤ Available$ ，则转向步骤3；否则，表示系统中尚无足够的资源，Pi必须等待

  3. 系统试探把要求的资源分配给进程Pi，并修改下面数据结构中的数值：

    • $Available := Available - Request_i$
    • $Allocation := Allocation + Request_i $
    • $Need_i := Need_i - Request_i$

  4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。

    • 若安全，正式将资源分配给进程Pi， 以完成本次分配；
    • 否则，将试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
安全性算法

  1. 设置两个向量（数组）

    • 工作向量Work，它表示系统可提供给进程继续运行所需要的各类资源的数目。
      • 它含有 m 个元素，执行安全算法开始时，$Work := Available$。
    • 完成向量Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。
      • 开始时先做 $Finish[i] := false$；
      • 当有足够的资源分配给进程时，令 $Finish[i] := true$ 。

  2. 从进程集合中找到一个能满足下述条件的进程：

    • ①$Finish[i] = false$; ②$Need_i ≤ Work$。
    • 如找到，执行步骤3；否则执行步骤4。

  3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故执行如下操作：

    • $Work := Work + Allocation$;
    • $Finish[i] := true$;
    • Goto step2;

  4. 如果所有进程的 $Finish[i] = true$，则表示系统处于安全状态；否则，系统处于不安全状态。

银行家算法的特点

  • 允许互斥、部分分配和不可抢占，可提高资源利用率；

  • 要求事先说明最大资源要求，在现实中很困难。

4. 检测死锁

上面讨论的死锁预防和死锁避免的方法都比较保守，且都是以牺牲机器效率和浪费资源为代价的。如果们采取较为大胆的方法，即允许有死锁出现，但操作系统能不断地监督各进程的共同进展路径，一旦死锁发生，采取专门的措施加以克服，并以最小的代价使系统恢复正常，这正是我们所期望的。

死锁检测指的是保存资源的请求和分配信息，利用某种算法对这些信息加以检查，以判断是否存在死锁。死锁检测算法主要是检查是否有循环等待。

  • 进程等待表和资源分配表；

  • 例如，在UNIX系统中，PS；Windows中的任务管理器

1）进程-资源图

进程的死锁可以用进程-资源图来描述，也叫资源分配图 RAG(Resource Allocation Graph)。进程资源图是由结点集合N和边集合E组成的一对偶 $G = (N, E)$ ，定义如下：

  • N = P U R。P为进程，R为资源，P = {p1, p2, … , pn}，R = {r1, r2, … , rm}，两者为互斥子集。

  • E：有向边的集合，e = (pi, rj) 或 e = (rj, pi)

    • e = (pi, rj) 是请求边，由进程点指向资源点，表示进程pi请求一个单位的rj资源；
    • e = (rj, pi) 是分配边，由资源点指向进程点，表示为进程pi分配了一个单位的rj资源。

  • 在资源分配图中，圆圈表示进程，矩形表示资源，矩形中的小圈代表每个资源。

image-20200920144209441
  • 思考：如果一个资源分配图中存在环路，是否一定存在死锁？
    • 不一定
image-20200920144332395

2）RAG的化简算法

（1）从图中选出一个进程结点Pi；

（2）对于该进程Pi，检查是否有请求边。

  • 如果没有请求边，则删除该进程结点的所有分配边，使该结点称为孤立结点，并转步骤（3）；
  • 如果有请求边，则对每个请求边，检查是否有对应的资源可以分配给该进程，
    • 如果可以满足请求，则将请求边改为分配边，重复步骤（2）；
    • 如果无法满足请求，则保留此请求边，转步骤（3）

（3）转步骤（1）继续处理其他进程结点，直到所有进程结点都经过上述处理。

（4）经过上述处理后，如果所有进程结点都变成孤立结点，则称该资源分配图可以完全化简，表明系统没有死锁；否则，称不可完全化简，表情系统存在死锁。

1
2
3
4
5
6
7
8
9
for Pi in P do
	for 请求边 in Pi do
		if 该请求边的请求可以得到满足 then
			将请求边改为分配边
		else
			break	// 处理其他的进程结点
		endif
	endfor
endfor

3）死锁定理

系统中某个时刻t为死锁状态的充要条件是t时刻系统的资源分配图是不可完全化简的。

5. 解除死锁

死锁解除重要的是以最小的代价恢复系统的运行，死锁解除后，释放资源的进程应恢复它原来的状态，才能保证该进程的执行不会出现错误。

  • 两种方法：
    • 撤消进程：使全部死锁的进程夭折掉，按照某种顺序逐个地撤消（回退）进程，直至有足够的资源可用，死锁状态消除为止。
    • 剥夺资源：使用挂起/激活挂起一些进程，剥夺它们的资源以解除死锁，待条件满足时，再激活进程

6. 死锁检测、预防和避免方法小结

image-20200920150249246

7. 思考题

问

  1. 在某系统中，三个进程共享四台同类型的设备资源，这些资源一次只能一台一台地为进程服务和释放，每个进程最多需要两台设备资源，试问 在系统中是否会产生死锁？

  2. 某系统中有n个进程和m台打印机，系统约定： 打印机只能一台一台地申请、一台一台地释放， 每个进程需要同时使用的打印机台数不超过m。 如果n个进程同时需要使用打印机的总数小于 m+n，试讨论，该系统可能发生死锁吗?并简述理由。

  3. 仅涉及一个进程的死锁有可能存在吗?为什么?

答

  1. 不可能，假设每个进程都占用了一台设备资源，仍然有一台设备空闲，也就是说，能过保证至少有一个进程可以获得其所需的两台设备资源。
  2. 不可能，由题目条件知，有 nm < n+m，即 n(m-1) < n ，显然 n < m，因而有 n(m-1) < m 恒成立。也就是说，即便每个进程都占用了m-1台设备，也能够保证至少有一台设备空闲，进而提供给某进程使用。
  3. 不可能，一个进程，不存在竞争，当然也无从谈死锁了。

考点积累

常考知识点

  • 在多对一的线程模型中，当一个多线程机制中的某个线程执行一个需阻塞的系统调用时，整个进程都将被阻塞。

  • 用户可通过系统调用建立和撤销进程。

    • 创建和撤销进程的工作由内核完成，只能通过系统调用来完成。

  • 注意P/V操作，都是先对s.count进行计算，再进行判断；

    • P：s.count–; if(s.count < 0) 阻塞当前进程
    • V：s.count++; if(s.count <= 0) 唤醒一个进程

  • 进程通信的常用方式有管道、消息队列、共享内存。

  • 实现进程之间同步与互斥的通信工具为P/V操作。

  • N个进程共享某一临界资源，则互斥信号量的取值范围是 -(N-1) ~ 1。

  • *进程通信有直接通信和间接通信两种方式，信箱是消息通信机制中的一种方法，是间接通信。

  • 在消息缓冲通信方式中，临界资源为消息队列。

  • 在现代操作系统中，必不可少的是进程调度。

    • 分配处理机

  • 关于作业优先权大小

    • I/O型 > 计算型
    • 短作业 > 长作业
    • 资源要求少的 > 资源要求多的
    • 动态优先权中，进程执行时间增加，优先权降低

  • 关于死锁预防，哪种策略破坏了哪个必要条件，要区分清楚。

  • 如果系统的资源分配图每种资源只有一个，并出现了环路，则系统处于死锁状态。

  • 程序的顺序执行具有顺序性、封闭性、可再现性。
  • 在一个单处理机系统中，若有5个用户进程，且假设当前时刻为用户态，则处于就绪态的用户进程最多有4个，最少有0个。
  • 如果系统中有n个进程，则在等待队列中进程的个数最多为n个。
  • 进程是一个独立运行的基本单位，也是资源分配和调度的基本单位。
  • 临界资源的概念是__，临界区的概念是 _。
  • 用于实现互斥的同步机制必须遵循空闲让进、忙则等待、有限等待和让权等待四条准则。
  • 实现一个管程时必须考虑的3个主要问题包括互斥、同步、条件变量。
  • 为实现基于消息缓冲队列的进程通信，在进程控制块中应增加消息队列指针、消息队列的互斥信号量以及消息队列的资源信号量三个数据项。
  • 按命令接口对作业控制方式的不同可将命令接口分为联机命令接口和脱机命令接口。
  • 作业调度又称高级调度/宏观调度，其主要功能是按照一定的调度算法从后备队列中选取作业进入内存，并为作业做好运行前的准备工作和作业完成的善后处理工作。
  • 确定作业调度算法时应注意系统资源的均衡使用，使计算型作业和I/O型作业搭配运行。
  • 进程调度负责处理机的分配工作。
  • 在抢占式调度中，抢占的原则有时间片原则，优先权优先原则，短进程优先原则。
  • 若使当前运行的进程总是优先级最高的进程，应选择抢占式最高优先权优先进程调度算法。
  • 确定优先权的方法有两种：静态和动态。
  • 死锁的主要原因是竞争资源和进程的推进顺序不当。
  • 设备分配只针对现有进程，因此不会导致创建新进程

管道

  • 半双工通信，要实现父子进程双方互动通信，需要定义两个管道

  • 管道只允许一边写入、另一边读出

    • 写进程会先把缓冲区写满，才让读进程读
    • 当缓冲区中还有数据时，写进程不会往缓冲区写数据

  • 从管道中读数据是一次性操作，数据一旦被读取，将被抛弃，释放空间以便继续写入数据，

  • 当写>读时，管道可能变满，写进程将被阻塞；当读>写时，管道可能变空，读进程将被阻塞

内存段的分配

  • 正文段：存放代码，赋值数据段，常量
  • 堆：动态分配的存储区（malloc）
  • 栈：未赋值的局部变量，实参

错题积累

  • 线程没有自己独立的地址空间，而是共享进程的地址空间；因此，线程之间的通信可以直接通过他们共享的存储空间。
  • 一个进程释放了一台打印机，它可能会改变另一个等待打印机的进程的状态
  • 在一个多道系统中，若就绪队列不空，就绪的进程数目越多，处理器的效率不变。
    • 因为CPU一直处于运行太
  • 在以下描述中，___并不是多线程系统的特长
    • 键盘驱动程序为每个正在运行的应用配备一个线程，以响应该应用的键盘输入
    • 这是因为人的速度较慢，一个线程就够了

辨析：进程上下文切换 vs 陷入内核

  • 进程上下文切换（Process Context Switch）

    • 通常由调度器执行
    • 保存进程执行断点
    • 切换内存映射（页表基址、flush TLB）

  • 陷入/退出内核（也称为模态切换, Mode Switch)

    • CPU状态改变
    • 由中断、异常、Trap指令（系统调用）引起
    • 需要保存执行现场（寄存器、堆栈等）

  • 系统调用涉及到进程从用户态到内核态的切换（mode switch），这个时候涉及到的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换（Process Context Switch）不同，mode switch 的消耗相对要小很多。