<操作系统>OS2 进程管理

本文最后更新于：2023年6月27日 上午

OS2 进程管理

程序 就是一个指令的序列。一个具有独立功能的程序独占处理器直到得到最终结果的过程称为程序的 顺序执行。顺序执行有 顺序性、封闭性 的特点。其执行结果有 确定性、可再现性 的特点。

为实现程序并发执行，引入了进程、进程实体的概念。

进程实体（进程映像）：由 PCB、程序段、数据段 这三部分构成。一般情况下，可以将进程实体称为进程。

进程：进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

若程序在执行中被改变，则该程序的功能就是变化的，也就不能以同样方式为多个用户服务。能被多个用户同时调用的程序称为 可再入 程序。可再入程序必须在执行中不会被更改。即，可再入程序必须和有关数据区分离。

相比于程序，进程拥有以下特征：

  • 动态性：进程是程序的一次执行过程，是动态产生、变化、消亡的
  • 并发性：内存中有多个进程实体，能并发执行
  • 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
  • 异步性：各进程按各自独立的、不可预知的速度推进。操作系统要提供 “进程同步机制” 以解决异步问题
  • 结构性：每个进程会配置一个 PCB。结构上看，进程由 PCB、程序段、数据段 组成

OS2.1 进程的组成

进程（进程实体）的组成分为三部分：

  • PCB（进程控制块）：系统为每个进程配置一个 PCB，以描述进程信息

    创建进程，实质上是创建进程实体的 PCB；撤销进程，实质上是撤销进程实体的 PCB。PCB 是进程存在的唯一标志。

    PCB 的组成分为以下几部分：

    • 进程描述信息：进程标识符（PID）、用户标识符（UID）
    • 进程控制和管理信息：进程当前状态、进程优先级
    • 资源分配清单：程序段指针、数据段指针、键盘、鼠标
    • 处理机相关信息：各种寄存器值

  • 程序段：存放要执行的代码

  • 数据段：存放程序运行过程中处理的各种数据

一个系统中有许多 PCB。为了对他们进行有效管理，必须用适当方式对其进行组织。

进程的组织方式有两种：

  • 链接方式：按照进程状态将 PCB 分为多个队列，操作系统持有指向各个队列的指针
  • 索引方式：根据进程状态的不同，建立几张索引表。操作系统持有指向各个索引表的指针

OS2.2 进程的状态

进程有几种状态：

  • 运行态（Running）：占有 CPU，在 CPU 上运行

  • 就绪态（Ready）：具备运行条件，但没有空闲 CPU，所以暂时不能运行

  • 阻塞态（Blocked）：因某一事件而暂时不能运行

  • 创建态（New）：进程正被创建，操作系统为其分配资源、初始化 PCB

  • 终止态（Terminated）：进程正从系统中撤销，操作系统回收其拥有的资源、撤销 PCB

  • 挂起（Suspend）：可被进一步分为 就绪挂起、阻塞挂起。由虚拟内存技术被调到外存等待的状态

    ——虚拟内存技术，见 [OS2.6 处理机调度 - 内存调度]

graph LR
new(创建态)--系统完成创建工作-->ready(就绪态)--进程被调度-->running(运行态)--运行结束或出错-->terminated{{终止态}}
blocked-->ready
running--时间片到或处理机被占-->ready
running--系统调用-->blocked(阻塞态)

状态间的转换有以下几种情况：

  • 创建态 —> 就绪态：系统完成创建进程相关工作
  • 运行态 —> 终止态：进程运行结束，或运行中遭遇不可修复的错误
  • 就绪态 —> 运行态：进程被调度
  • 运行态 —> 就绪态：时间片到，或 CPU 被其他高优先级进程抢占
  • 运行态 —> 阻塞态：通过 “系统调用” 方式申请某种系统资源，或等待某事件发生。是进程主动做出的行为。
  • 阻塞态 —> 就绪态：系统调用处理完成。是被动行为。

OS2.3 进程控制

进程控制 即实现进程状态的转换。进程控制是通过 原语 实现的。原语执行期间不允许中断，只能一气呵成。这种不能被中断的操作称为 原子操作。

原语采用 开中断指令 和 关中断指令 实现其原子操作。先发出开中断指令，此时起该进程操作不会中断。之后执行原语代码。执行结束后，发出关中断指令，之后的操作才继续受到外部中断信号影响。

开/关中断指令 的权限非常大，是只能在核心态下执行的特权指令

不论何种原语，其作用都能归为以下几类：

  • 更新 PCB 信息（如修改进程状态标志、将运行环境保存到 PCB、从 PCB 恢复运行环境）
  • 将 PCB 插入合适队列
  • 分配/回收资源

#进程创建

进程创建原语：

  • 先申请空白 PCB
  • 为新进程分配所需资源
  • 初始化 PCB
  • 最后将 PCB 插入就绪序列

引起进程创建的事件有：

  • 用户登录：分时系统中，用户登陆成功，系统会为其建立一个新的进程
  • 作业调度：多道批处理系统中，新的作业放入内存时，建立一个新的进程
  • 提供服务：用户向操作系统提出请求时，新建一个进程以处理该请求
  • 应用请求：由用户进程主动创建一个子进程

#进程终止

进程终止原语：

  • 从 PCB 集合中找到终止进程的 PCB
  • 若进程正在运行，则立即剥夺 CPU，将 CPU 分配给其他进程
  • 终止该进程的所有子进程
  • 将该进程拥有的所有资源归还给父进程或操作系统
  • 删除 PCB

引起进程终止的事件：

  • 进程正常结束
  • 进程异常结束
  • 外界干预

#进程阻塞

进程阻塞原语：

  • 找到要阻塞的进程对应的 PCB
  • 保护进程运行现场，将 PCB 状态设置为阻塞，暂时停止其运行
  • 最后，将 PCB 插入相应的阻塞事件的等待序列

引起进程阻塞的事件：

  • 需要等待系统分配某种资源
  • 需要等待相互合作的其他进程完成工作

#进程唤醒

唤醒进程原语：

  • 在事件等待队列中找到对应的 PCB
  • 将 PCB 从等待队列移除，状态设置为就绪
  • 将 PCB 插入就绪队列，等待被调度

引起进程唤醒的事件：

  • 等待的事件发生

#进程切换

切换进程原语：

  • 将运行环境信息存入 PCB
  • 将 PCB 移入相应队列
  • 选择另一个进程执行，并更新其 PCB
  • 根据 PCB 恢复进程所需的运行环境

引起切换进程的事件：

  • 当前进程时间片到
  • 有更高优先级的进程到达
  • 当前进程主动阻塞
  • 当前进程终止

OS2.4 进程通信

进程通信 即进程间的信息交换。进程是分配系统资源的单位，各进程拥有的内存地址空间相互独立。为保证安全，一个进程不能直接访问另一进程的地址空间。

为了实现进程间的安全通信，操作系统提供了一系列方法：

  • 共享存储（基于数据结构的共享、基于存储区的共享）

    两个进程对其共享空间的访问必须是 互斥 的。操作系统只提供共享空间和共享同步互斥工具。

    • 基于数据结构的共享：共享空间只能存放特定类型的数据结构。这种共享方式速度慢、限制多，是一种低级通信方式。
    • 基于存储区的共享：在内存中划出一块共享存储区，其中数据形式、存放位置由进程控制。这种共享方式速度更快，是一种高级通信方式。

  • 消息传递（直接通信、间接通信）

    进程间数据交换以 格式化消息（Message）为单位。格式化消息含消息头（发送进程 ID、接受进程 ID、消息类型、消息长度等）和消息尾。进程通过操作系统提供的 ”发送消息“、”接收消息“ 原语进行数据交换。

    • 直接通信方式：消息直接挂到接受进程的消息缓冲队列上
    • 间接通信方式：也称信箱通信方式。消息先发送到中间实体中，接受进程再从中取出消息

  • 管道通信

    管道（pipe）是用于连接读写进程的一个共享文件。在内存中开辟一个大小固定的缓冲区，以实现 半双工通信（某一时间段内只能单向传输）。要实现双向同时通信，则需要设置两个管道。

    数据以字符流方式写入管道。管道满时，写入（wirte()）系统调用会阻塞。管道空时，读取（read()）系统调用会被阻塞。

    若未写满，则不允许读。若未读空，则不允许写。数据一经读出即被管道抛弃，因此读进程只能有一个。

OS2.5 线程

有的进程要同时完成多项任务，为此引入了 线程，以增加并发度。可以把线程理解为 ”轻量级的进程“。线程是一个基本的 CPU 执行单元，是程序执行流的最小单位。

线程是处理机调度的单位。多 CPU 计算机中，进程的各个线程可以占用不同 CPU。

每个线程都有一个线程 ID，及 TCB（线程控制块）。线程也有 就绪、阻塞、运行 的三种基本状态。

线程几乎不拥有系统资源，同一进程的不同线程间共享进程资源。同一进程的不同线程共享内存地址空间，因而线程间通信也无需操作系统干预。

统一进程内的不同线程切换，不引起进程切换，其系统开销较少。不同进程间的线程切换会引起进程切换，系统开销较大。

引入线程后带来的变化：

  • 资源分配的调度

    传统进程机制中，进程是资源分配、调度的基本单位。

    引入线程后，进程是资源分配的基本单位，线程是调度的基本单位。

  • 并发性

    传统进程机制只能进程间并发

    引入线程后，不仅进程间能并发，进程内的线程间也能并发，从而进一步提升了系统的并发度。

  • 系统开销

    传统进程机制，进程间并发需要切换进程的运行环境，系统开销巨大

    引入线程后，若是同一进程内的线程切换则不必切换进程环境，并发带来的系统开销有所减少

#线程的实现方式

线程的实现方式有两种：

  • 用户级线程（ULT，User-Level Thread）

    用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责。

    用户级线程中，线程切换可以在 用户态 下完成，无需操作系统干预（用户级线程对用户透明，对操作系统不透明）

  • 内核级线程（KLT，Kernel-Level Thread）

    内核级线程管理工作必须由操作系统内核完成。线程调度、切换等都由操作系统负责，其线程切换必须在 核心态 下才能完成。

    操作系统只能操作内核级线程，因此 内核级线程才是处理机分配的单位

#多线程模型

  • 多对一模型：多个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程

    优点：用户级线程的切换在用户态即可完成，不需要切换核心态。系统开销小，效率高。

    缺点：一个用户级线程阻塞会导致整个进程都被阻塞，并发度低。多线程不能在多核处理机上运行

  • 一对一模型：一个用户级线程映射到一个内核级线程。每个用户进程有用户级线程数量的内核级线程。

    优点：一个用户级线程阻塞时，其他线程能继续执行，并发能力强。多线程能在多核处理机上执行

    缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统在核心态完成，管理成本高，开销大

  • 多对多模型：将 n 个用户级线程映射到 m 个内核级线程（n>=m）。每个用户进程对应 m 个内核级进程

    多对多模型集二者所长，在保留并发能力的同时，也不产生太大系统开销。

OS2.6 处理机的调度

在多道程序系统中，进程数量往往多于处理机个数。处理机调度 就是从就绪队列中按照一定算法选择一个进程并将处理机分配给它运行，以实现程序的并发执行。

处理机调度有三个层次：作业调度、内存调度、进程调度

#作业调度（高级调度）

按一定的算法，从外存上处于后备队列的作业中选一个（或多个）作业，为其分配内存等必要资源，并建立相应进程（创建 PCB），以使其获得竞争处理机的权利

高级调度是外存与内存间的调度。每个作业只调入一次，调出一次。作业调入时建立相应 PCB，调出时才撤销 PCB。

高级调度主要是指调入问题，因为只有调入时机需要操作系统决定，调出必然是作业运行结束时退出。

#内存调度（中级调度）

为提高内存利用率和系统吞吐量，引入了 虚拟内存 技术。暂时不能运行的进程被调至外存等待，直到其重新具备运行条件时，再重新调入内存。

暂时调到外存的进程进入 挂起状态（Suspend）。在此期间，PCB 不会被调到外存，而是常驻内存，并进入挂起队列。PCB 记录进程数据在外存中的存放位置、进程状态等信息。

中级调度就是决定进程的挂起和激活。一个进程可能会多次调出、调入内存，因此中级调度的发生频率高于高级调度。

![](/img/OS_InputImage/OS2_6 七状态模型图.webp)

（OS2_6 七状态模型图）

有的操作系统会将就绪挂起、阻塞挂起分为两个队列，甚至因挂起原因不同再将阻塞挂起分为多个队列。

#进程调度（低级调度）

按一定的算法，从就绪队列中选择一个进程，并为其分配处理机。

进程调度上述操作系统最基本的一种调度，一般的操作系统都必须配置进程调度。进程调度的频率很高，一般几十毫秒就调度一次。

当前进程主动放弃处理机，或当前进程 被动放弃处理机时，需要进程调度。有时不能进行进程调度。

  • 主动放弃处理机：程序正常终止、遭遇异常、请求阻塞

  • 被动放弃处理机：分配的时间片用完、高优先级进程插队、有紧急事件需要处理

  • 不能进行进程调度：在处理中断的过程中、进程在操作系统内核程序临界区中、在原子操作中

    一段时间内只允许一个进程使用的资源，称为 临界资源。各进程必须互斥地访问临界资源。访问临界资源的代码就是 临界区。

    操作系统内核程序临界区，访问的临界资源必须尽快释放，否则会影响操作系统内核的其他管理工作。因此，访问内核程序临界区时不能进行进程调度。但访问普通临界区时是可以进行进程调度的。

有的操作系统不允许被动放弃处理机。由此，将进程调度方式分为：非剥夺调度方式（非抢占方式，不允许进程被动放弃处理机）、剥夺调度方式（抢占方式，允许进程被动放弃处理机）

#调度算法

下面是一些评价调度算法的指标：

  • CPU 利用率：CPU 忙碌时间占总时间的比例。即：利用率=忙碌的时间总时间\text{利用率}=\dfrac{\text{忙碌的时间}}{\text{总时间}}

  • 系统吞吐量：单位时间内完成作业的数量。即：系统吞吐量=总共完成了多少作业总共花费了多少时间\text{系统吞吐量}=\dfrac{\text{总共完成了多少作业}}{\text{总共花费了多少时间}}

  • 周转时间：从作业被提交给系统起，到作业被完成为止的时间。即：周转时间=完成时间−提交时间\text{周转时间}=\text{完成时间}-\text{提交时间}

  • 平均周转时间：平均周转时间=周转时间之和作业数\text{平均周转时间}=\dfrac{\text{周转时间之和}}{\text{作业数}}

  • 带权周转时间：带权周转时间=作业周转时间作业实际运行时间=作业完成时间−作业提交时间作业实际运行时间\text{带权周转时间}=\dfrac{\text{作业周转时间}}{\text{作业实际运行时间}}=\dfrac{\text{作业完成时间}-\text{作业提交时间}}{\text{作业实际运行时间}}

  • 等待时间：进程/作业 处于等待处理机状态的时间之和。

    对于进程来说，等待时间是进程建立后，等待被服务的时间之和。等待 I/O 完成期间也视为被服务。

    对于程序来说，除进程的等待时间外，还要加上作业在外存后备队列中等待的时间

  • 响应时间：用户从提出请求，到首次产生响应所用的时间。

早期计算机造价昂贵，早期的批处理系统更注重平均周转时间等指标。早期批处理系统主要有以下几种调度算法：

  • FCFS（First Come First Serve，先到先得）

    按照 作业/进程 到达的先后顺序进行服务。

    用于作业调度时，考虑哪个作业先到达后备队列。用于进程调度时，考虑哪个进程先到达就绪队列。

    FCFS 算法是一种非抢占式算法，不会导致饥饿（特定进程长时间得不到服务）。

    FCFS 算法较公平，但对长作业有利，对短作业不利。

  • SJF（Shortest Job First，短作业优先）

    最短的 作业/进程 优先得到服务，以追求最少的 平均等待时间 和最少的 平均带权等待时间

    SJF 既可用于作业调度，也能用于进程调度。用于进程调度时称为 SPF（Shortest Process First，短进程优先）算法

    SJF 和 SPF 是非抢占式算法。但也有抢占式的版本：SRTN（Shortest Remaining Time First，最短剩余时间优先）。SJF 算法可能导致饥饿/饿死。

    SJF 算法对短作业有利，对长作业不利。此外，作业/进程 的时间是由用户提供的，不一定能做到真正的短作业优先。

  • HRRM（高响应比优先）

    在每次调度时计算各个 作业/进程 的响应比，选择响应比高的 作业/进程 为其服务。

    响应比的计算方法：响应比=等待时间+要求服务时间要求服务时间\text{响应比}=\dfrac{\text{等待时间}+\text{要求服务时间}}{\text{要求服务时间}}

    HRRM 算法是非抢占式算法。HRRM 算法避免了产生饥饿问题。

    HRRM 算法是上述两种算法的折中，综合考虑了等待时间和运行时间。

由于计算机造价大幅降低，之后出现的交互式系统更注重系统响应时间、公平性、平衡性的指标。对于交互式操作系统，有以下几种调度算法：

  • 时间片轮转调度算法（RR，Round Robin）

    按照各进程到达就绪队列的顺序，轮流让每个进程执行一个时间片。时间片用完后，剥夺处理机，将进程重新放到就绪队列尾排队。

    时间片太大时，算法退化为 FCFS 算法，会增大进程响应时间。时间片太小时，进程切换过于频繁，系统花费过多时间用于进程切换，会导致进程执行时间比例减少。通常时间片要让切换进程的开销比例不超过 1%。

    时间片轮转调度算法是抢占式算法，由时钟装置发出时钟中断来提示 CPU 时间片到。

    时间片轮转算法较为公平，且响应时间快，也不会产生饥饿，适用于分时操作系统。但切换进程会引起开销，也不能区分任务的紧急程度。

  • 优先级调度算法

    每个 作业/进程 拥有一个优先级，调度时选择优先级高的执行。

    优先级调度算法有抢占式、非抢占式版本。非抢占式只在进程主动放弃处理及时进行调度，而抢占式版本会额外在就绪队列变化时检测是否要发生抢占。

    根据优先级是否能动态改变，可以将优先级分为 静态优先级 和 动态优先级。通常，系统进程 优先级高于 用户进程；前台进程 优先级高于 后台进程。

    操作系统更偏好 I/O 型繁忙型进程。与 I/O 繁忙型进程相对的是 CPU 繁忙型进程。因为 I/O 设备与 CPU 能并行工作，I/O 繁忙型进程越优先，I/O 设备就能越早投入工作，资源利用率、系统吞吐量也能得到提升。

    优先级调度算法能区分紧急程度、重要程度，适用于实时操作系统。但若有源源不断的高优先级进程到来，可能导致饥饿。

  • 多级反馈队列调度算法

    多级反馈队列调度算法是对其他调度算法的这种权衡：

    1. 先设置多级就绪队列，各级队列的优先级从高到低，时间片从小到大。
    2. 新进程到达时先进入第一级队列，按照 FCFS 原则排队等待时间片。时间片用完时，进入下一级队列末尾。已经在最下级队列时，仍回到最下级队尾。
    3. 仅当第 k 级队列为空时，才为下一级队列分配时间片。

    多级反馈队列调度算法是抢占式算法。对各类进程相对公平。每个到达的进程都能快速得到响应，短进程也能较快完成。不必估计进程运行时间，也能灵活调整对各类型的偏好程度。

    若有源源不断的高优先级进程到来，仍可能导致饥饿。

OS2.7 进程的同步与互斥

进程同步 又称直接制约关系。为了解决并发进程异步问题，使进程间相互制约，从而协调各进程的工作次序。

进程互斥 又称间接制约关系。一个进程访问临界资源时，另一访问该临界资源的进程必须等待。

对临界资源的互斥访问，可在逻辑上分为几部分：

  1. 进入区：检查是否能进入临界区。若能进入，则设置正在访问临界区的标志（如互斥锁）
  2. 临界区：访问临界资源的代码
  3. 退出区：解除正在访问临界区的标志
  4. 剩余区：做其他处理

进程互斥遵循以下原则：空闲让进、忙则等待、有限等待（保证不会发生饥饿）、让权等待（不能进入临界区时，释放处理机，防止忙等）

#进程互斥的软件实现方法

  • 单标志法

    进程访问完临界区后，将临界区权限转移给另一进程。每个进程进入临界区的权限只能被其他进程赋予。

    单标志法的主要问题是，不满足 空闲让进 原则

  • 双标志先检查

    设置一个布尔数组以标记每个进程进入临界区的意愿。进程进入临界区前检查是否有其他程序有进入意愿。若都无意愿，则将自身意愿标志标记为 true，并开始访问临界区。退出时，将自身意愿标志标记为 false。

    双标志先检查法的主要问题是，检查与上锁操作不是同时完成，可能违背 忙则等待 原则。

  • 双标志后检查

    双标志先检查法的改进版。先设置进入意愿，再检查其余进程的进入意愿。

    虽然做到了 ”忙则等待“，但违背了 空闲让进 和 有限等待 原则。

  • Peterson 算法

    双标志后检查法的改进版。多个进程都想进入临界区时，那些进程会主动让对方使用临界区。

    下面是其中一种情况：

    sequenceDiagram
autonumber
participant 进程A
participant 临界资源
participant 进程B
进程B ->> 临界资源: flag[进程B] = true
进程A ->> 临界资源: flag[进程A] = true
进程A ->> 临界资源: trun = 进程B
进程B ->> 临界资源: trun = 进程A
loop
	进程B --> 临界资源: while(flag[进程A] && turn == 进程A)
	note left of 进程B: 进程 B 阻塞
end
loop
	进程A --> 临界资源: while(flag[进程B] && turn == 进程B)
	note right of 进程A: 进程 A 进入临界区
end
进程A ->> 临界资源: 临界区
进程A ->> 临界资源: flag[进程A] = false
loop
	进程B --> 临界资源: while(flag[进程A] && turn == 进程A)
	note left of 进程B: 进程 B 进入临界区
end
进程B ->> 临界资源: 临界区
进程B ->> 临界资源: flag[进程B] = false

    Peterson 算法遵循了 空闲让进、忙则等待、有限等待 的原则。但仍未遵循 让权等待 的原则。

#进程互斥的硬件实现方法

  • 中断屏蔽方法

    利用 开/关中断指令 实现。与原语类似，某进程开始访问临界区起，至访问结束止，期间不允许中断。不允许中断就不能发生进程切换，也就避免了两个进程同时访问临界区。

    中断屏蔽方法简单高效，但不适用于多处理机。且开/关中断指令只能在内核态进行，故只适用于操作系统内核进程，不适用于用户进程。

  • TestAndSet 指令

    简称 TS 指令（也称 TSL 指令、TestAndSetLock 指令），是用硬件实现的指令。执行过程中不允许中断，只能一气呵成。

    使用布尔型共享变量 lock 记录临界区加锁状态（初始 false）。检查时返回原先 lock 值，并将 lock 值变为 true。仅当进程退出临界区时，将 lock 变为 false。

    下面是模拟那个实现逻辑的伪代码：

    static bool lock = false

TSL() {
	old := lock
	lock = true
	return old
}

Process() {
	while(TSL()) {}
	CriticalSection()		// <-- 临界区
	lock = false
}

    TSL 指令实现简单，适用于多处理机环境。由于采用硬件方式，将 上锁 和 检查 变为了原子操作，TSL 指令无需像软件实现方法那样严格检查逻辑漏洞。

    暂时进入临界区的进程会占用 CPU 循环执行 TSL 指令，故不满足 让权等待 原则。

  • Swap 指令

    也称 XCHG 指令或 Exchange 指令，是用硬件实现的指令。执行过程中不允许中断，只能一气呵成。

    Swap 指令能交换两个变量的值。其逻辑与 TSL 指令相似，只是硬件实现不同。

    使用布尔型共享变量 lock 记录临界区加锁状态（初始 false），每个进程再各自持有加锁标记 old（初始 true）。判断时，若 old 为 true 则持续交换 lock 与 old。仅当进程退出临界区时，将 lock 变为 false。

    下面是模拟那个实现逻辑的伪代码：

    static bool lock = false

Swap(bool old) {
	lock, old = old, lock
}

Process() {
	old := true
	while (old) { Swap(old) }
	CriticalSection()		// <-- 临界区
	lock = false
}

    Swap 指令的优/缺点与 TSL 指令相同。

#信号量机制

信号量机制是由 Dijkstra 提出的，能遵循进程互斥原则的方法。

信号量 是一个变量，表示系统中某种资源的数量。信号量机制 是用户进程通过使用操作系统提供的 一对低级通讯原语（wait(S) 原语与 signal(S) 原语。简称为 P(S)、V(S) 操作）来对 信号量 进行操作，从而实现进程互斥和同步。

  • 整形信号量

    用整数型变量记录信号量。

    检查时（wait(S)），信号量为 0 则等待。退出临界区后，设置资源量（signal(S)）

    下面是模拟那个实现逻辑的伪代码：

    static int S = 1

wait(int S) {
	while(S <= 0) {}
	S -= 1
}

signal(int S) {
	S += 1
}

Process() {
	wait(S)
	CriticalSection()		// <-- 临界区
	signal(S)
}

    不满足 让权等待 原则，可能发生忙等。

  • 记录型信号量

    用记录型数据结构记录信号量。

    检查时，先设置资源量，之后若无资源则阻塞。退出临界区后，若有其他进程阻塞，则唤起一个进程。

    下面是模拟那个实现逻辑的伪代码：

    struct semaphore {
	int val
	queue<*process> L 
}

static semaphore S = {0, queue<>{}}

wait(semaphore S) {
	S.val -= 1
	if (S.val < 0) block(S.L)
}

signal(semaphore S) {
	S.val += 1
	if (S.val <= 0) wakeup(S.L)
}

block(semaphore S) {
	s.L.add(this)
	this.block
}

wakeup(semaphore S) {
	S.L.poll().wakeup
}

Process() {
	wait(S)
	CriticalSection()		// <-- 临界区
	signal(S)
}

    记录型信号量遵循了 让权等待 原则

#管程

用信号量机制实现线程同步、互斥，编写程序困难，也容易出错。为更方便地实现进程同步和互斥，引入了管程。

管程 是一种特殊的软件模块，由几个部分组成：名称、共享数据结构、访问数据结构的函数、初始化语句

管程有如下特征：

  • 局部于管程的数据只能被局部于管程的函数访问
  • 一个进程只有通过调用管程内的函数才能进入管程访问共享数据
  • 每次仅允许一个进程在管城内执行某个内部过程

管程被进程的互斥访问特性是由编译器实现的。可以在管程中设置条件变量及等待/唤醒 操作以解决同步问题

OS2.8 死锁

死锁：在并发环境中，各进程互相持有对方需求资源，导致各进程都被阻塞无法推进的现象。

饥饿：由于长期得不到资源，某一进程无法向前推进的现象。

死循环：某进程执行过程中始终不能跳出某一循环的现象。通常由代码逻辑问题导致。

死锁的产生必须同时满足以下四种条件：

  • 互斥条件：只有对必须互斥使用的资源才会发生死锁
  • 不剥夺条件：进程获得资源在使用完成前，不能由其他进程强行夺走，只能主动释放
  • 请求和保持条件：进程已经持有资源时提出新的资源请求，被阻塞时已占有的资源不释放
  • 循环等待条件：存在进程资源的循环等待链

一些可能发生死锁的情况：对系统资源的竞争、进程推进顺序非法、信号量的不当使用。

死锁有三种基本的处理策略：预防死锁、避免死锁、检测和解除死锁

#预防死锁

破坏死锁四个必要条件中的一个或几个

  • 破坏互斥条件

    如果把只能互斥使用的资源改造成能共享使用，系统就不会进入死锁。

    SPOOLing 技术：操作系统可以采用 SPOOLing 技术将独占设备在逻辑上改造成共享设备

    缺点：并非所有资源都能被改造成共享资源。而且为了系统安全，很多地方必须保持互斥性。很多时候无法破坏互斥条件。

  • 破坏不剥夺条件

    有以下几种方案：

    • 某进程请求资源被阻塞时，其持有的资源必须释放，使用时再重新申请。该方案可能导致饥饿。
    • 当请求资源被其他进程占有时，由操作系统协助，将请求资源强行剥夺。需考虑进程优先级。

    缺点：实现复杂。剥夺资源可能造成前一阶段工作失效，故只适用于易保存和恢复状态的资源（如 CPU）。反复申请和释放资源增加了系统开销，降低系统吞吐量。

  • 破坏请求和保持条件

    静态分配方法：在进程运行前一次性申请所有资源。未满足条件时不许运行。一旦运行，资源就始终被其持有。

    缺点：造成严重资源浪费，资源利用率极低，且可能导致某些进程饥饿。

  • 破坏循环等待条件

    顺序资源分配法：给系统资源编号，每个进程必须按照编号递增顺序请求资源。同类资源一次性申请完成。

    持有小编号资源时才能申请大编号资源，大编号资源持有者不会申请小编号资源，也就不会发生循环等待。

    缺点：编程麻烦，也不方便增加新设备。使用资源顺序与编号顺序不一致，会导致资源浪费。

#避免死锁

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

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

若系统处于安全状态，则 必定不会 发生死锁。若系统进入不安全状态，则 可能 发生死锁。

在每次分配资源前判断该分配是否让系统进入不安全状态，以此决定分配方式，这就是 银行家算法

安全性算法：计算每个进程的剩余需求量。之后，用现有资源量逐一比对。现有资源满足剩余需求时，将该进程加入序列，并让现有资源加上该进程的已分配资源。循环比对后，所有进程进入序列时，该序列为安全序列。

#检测和解除死锁

允许死锁发生，但使操作系统检测和处理死锁

检测死锁：

  • 使用一种数据结构保存资源的请求与分配信息

    这种数据结构：存在两种节点（资源节点、进程节点）和两种边（进程—>资源，资源—>进程）

  • 提供一种算法，利用上述信息检测系统是否进入死锁状态

    死锁检测算法：若进程的资源需求都被满足，则其可以正常执行。其执行完后就能消除进程节点对应的边。那之后，可能激活其他的阻塞进程。上述循环分析后，若能消除所有边，则称该图 可简化，此时必定没有发生死锁。否则，必定是发生了死锁，那些仍有边相连的进程是死锁进程。

解除死锁：

  • 资源剥夺法：挂起某些死锁进程，并抢占其资源。应采取措施防止挂起资源饥饿
  • 撤销进程法：强制撤销部分甚至全部死锁的进程，并剥夺资源。虽然实现简单，但代价巨大。
  • 进程回退法：使一些死锁进程进度回退到避免死锁的地步。需要系统记录进程的历史信息，设置还原点。
操作系统
#基础课目 #操作系统
<操作系统>OS2 进程管理
https://i-melody.github.io/2022/12/22/操作系统/2 进程管理/
作者
Melody
发布于
2022年12月22日
许可协议