# 进程管理 1

知识结构

  • 进程与线程
    • 进程的概念;进程的状态与切换;
    • 进程控制;进程组织;
    • 进程通信;线程概念与多线程模型;
  • 处理机调度
    • 调度的基本概念;调度时机,切换与过程;
    • 调度的基本准则;调度方式;典型的调度算法
  • 进程同步
    • 进程同步的概念
    • 临界区互斥
    • 信号量;管程;经典同步问题
  • 死锁
    • 死锁的概念;死锁处理策略
    • 死锁预防;死锁避免;死锁的检测和接触

# 2.1 进程与线程

# 2.1.1 进程的概念和特征

  1. 进程的概念

为了使参与并发执行的程序能独立地运行,必须为之配置一个专门的数据结构,称为进程控制块。系统利用 PCB 来描述进程的基本情况和运行态,进而控制和管理进程。

  1. 进程的特征

进程是由多程序的并发执行而引出的,它和程序是两个截然不同的概念。进程的基本特征是对比单个程序的顺序执行提出的,也是对进程管理提出基本要求。

  • 动态性。进程是程序的一次执行,有着创建,活动,暂停,中止等过程,具有一定的生命周期
  • 并发性。多个进程实体同时存在于内存,能在一段时间内同时运行。
  • 独立性。进程实体是一个能独立运行,独立获得资源和独立接受调度的基本单位。
  • 异步性。由于进程的相互制约,使得进程具有执行的间断性,即进程按各自独立的,不可预知的速度向前推进。异步性会导致执行结果的不可再现性,为此在操作系统中必须配置相应的进程同步机制。
  • 结构性。每个进程都配置一个 PCB 对其进行描述。

# 2.1.2 进程的状态与转换

进程在其生命周期内,由于系统各进程之间的相互制约关系及系统的运行环境的变化,使的进程的状态也在不断地发生变化。通常进程有以下五种状态,前三种是进程的基本状态。

  • 运行态。进程正在处理机上运行。
  • 就绪态。进程已处于准备运行的状态,即进程获得了除处理机外的一切所需资源,一旦得到处理机即可运行。
  • 阻塞态。进程正在被创建,尚未转到就绪态。创建进程通常需要多个步骤:首先申请个空白的 PCB,并向 PCB 中填写一些控制和管理进程的信息;然后由系统为该进程分别运行时所需的资源。
  • 结束态。进程正从系统中消失,可能是进程正常结束也可能是其他原因,但不管怎么说,进程需要结束运行时,系统首先必须置进程为结束态,然后再进一步处理资源释放和回收等工作。

进程: 程序的一次执行过程

一个进程应该包括

  • 程序的代码
  • 程序处理的数据
  • 程序计数器——PC 指针
  • 一组通用寄存器保存的值
  • 一组系统资源(比如打开的文件)

程序和进程的联系

程序是产生进程的基础,程序的每次运行构成不同的进程; 通过多次执行,一个程序可对应多个进程; 通过调用关系,一个进程可包括多个程序(比如 Java 调用 C++ ?)

# 2.1.3 进程控制

  1. 进程的创建

允许一个进程创建另一个进程。此时创建者称为父进程,被创建的进程被称为子进程。子进程可以继承父继承所有用的资源。当子进程撤销,归还资源。此外当父进程撤销时,必须同时撤销所有的子进程。

操作系统创建一个新进程的过程如下:

  • 为新进程分配一个唯一的进程标志号
  • 为进程分配资源,为新进程的程序和数据及用户栈分配必要的内存空间。
  • 初始化进程控制块
  • 若进程就绪队列能够接纳新进程,则将新进程插入就绪队列,等待被调度运行。
  1. 进程的终止

引起进程终止的事件主要有:正常结束,异常结束。

  • 正常结束,表示进程的任务已经完成。
  • 异常结束,表示进程在运行时,发生了某种异常事件,使程序无法继续运行,如存储越界,保护错,非法指令。

操作系统终止进程的过程如下:

  • 根据被终止进程的标识符,检索 PCB,从中读出该进程的状态。
  • 若被终止进程处于执行状态,立即终止该进程的执行,将处理机资源分配给其他进程。
  • 若该进程还有子进程,则应将所有子进程终止
  • 将该进程的所有资源归还给父进程,没有父进程则归还给操作系统
  • 将该 PCB 从所在队列中删除。
  1. 进程的阻塞和唤醒

正在执行的进程,由于期待的某些事件未发生,如请求系统资源失败,等待某些操作的完成等,由系统自动执行阻塞原语 Block,使得该进程进入阻塞态。 进程的阻塞时进程自身的一种主动行为,也只有处于运行态的进程可以转为阻塞态。

阻塞原语的执行过程如下。

  • 找到将要被阻塞进程的标识号对于的 PCB
  • 若该进程为运行态,则保护其现场,将其状态转为阻塞态,停止运行。
  • 把该 PCB 插入相应的事件

当阻塞的进程所期待事件出现时,比如 IO 操作已完成或数据已到达,由乡姑纳进程调用唤醒原语,将等待该事件的进程唤醒。

唤醒原语的执行过程如下:

  • 在该事件的等待队列中找到相应进程的 PCB
  • 将其从等待队列中移除,并置其状态为就绪态
  • 把该 PCB 插入就绪队列,等待调度程序调度。

原语

计算机进程的控制通常由原语完成。 所谓原语,一般是指由若干条指令组成的程序段,用来实现某个特定功能,在执行过程中不可被中断(原子性)。

  1. 进程切换

进程切换指处理机从一个进程的运行转到另一个进程上运行,在这个过程中,进程的运行环境发生了实质性的变化。

进程的切换过程如下:

  • 保存处理机上下文,包括程序计数器和其他寄存器。
  • 保存 PCB 信息
  • 把进程的 PCB 移入相应的队列,比如就绪,在某事件阻塞等队列
  • 选择另一个进程执行,并更新其 PCB。
  • 更新内存管理的数据结构。
  • 恢复处理机上下文

调度和切换

调度是指决定资源分配给那个进程的行为,是一种决策行为;切换是指实际分配的行为,是执行行为。 一般来说,现有资源的调度,然后才有进程的切换。

# 2.1.4 进程的组织

进程是一个独立的运行单位,也是操作系统进行资源分配和调度的基本单位。它一般由以下三部分组成。

  1. 进程控制块

进程创建时,操作系统新建一个 PCB 结构用于描述和管理该进程,该结构常驻内存,并在进程结束时删除。PCB 是进程实体的一部分,是进程存在的唯一标志。

PCB 的主要组成部分

  • 进程描述信息。进程标识符和用户标识符
  • 进程控制和管理信息。当前状态,优先级等
  • 资源分配清单。有关资源的内存地址空间,文件列表,IO 设备等
  • 处理机相关信息。主要指寄存器冲的值。
  1. 程序段

程序段就是能被进程调度程序调度到 CPU 执行的程序代码段

  1. 数据段

一个进程的数据段,存储程序的原始数据或中间产物,或最终结果等。

# 2.1.5 进程的通信

进程通信是指进程之间的信息交换。PV 操作是低级通信方式,高级通信方式是指以较高的效率传输大量数据的通信方式,主要有以下三类。

  1. 共享存储

在通信的进程之间存在一块可直接访问的共享空间,通过对这片共享空间进行读写操作实现进程之间的信息交换。在对共享空间进行读写操作时,需要使用同步互斥工具,不然多个进程同时操作一个内存空间势必会导致数据错乱。

  1. 消息传递

在消息传递系统中,进程间的数据交换是以格式化的消息为单位的。若通信的进程之间不存在可以直接访问的共享空间,则必须使用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接受消息两个原语进行数据交换。

直接通信方式

发送进程直接把消息发送给接收进程

间接通信方式

发送进程把消息发送到某个中间实体,接收进程从中间实体取得消息,这种中间实体一般称为信箱

  1. 管道通信

管道通信是消息传递的一种特殊方式。所谓“管道”,是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件,又称“pipe”文件。向管道提供输入的发送进程,以流的形式将大量输入送入管道;而接受管道输出的接受进程,则从管道中接受数据。

为了协调双方通信,管道必须提供一下三方面的协调能力:

  • 互斥
  • 同步
  • 确定对方的存在

管道是一种文件

从本质上来说,管道也是一种文件,但它和一般文件有所不同,管道可以克服使用文件进行通信的两个问题,具体表现如下:

  • 限制管道的大小。实际上管道是一个固定大小的缓冲区。管道变满时,下一个 write()调用将默认被阻塞
  • 读进程可以比写进程快。管道变空时,下一个 read()调用将默认被阻塞。

# 2.1.6 线程概念和多线程模型

  1. 线程的基本概念

引入进程的目的是为了更好的使多道程序并发执行,提高资源利用率。

引入线程的目的是为了减少程序在执行是所付出的时间空间开销。

线程的最直接理解就是“轻量级进程”,是一个基本的 CPU 执行单元,也是程序执行流的最小单元。

一个线程由以下部分组成:

  • 线程 ID
  • 程序计数器
  • 寄存器集合
  • 堆栈

由于线程之间的相互制约,只是线程在运行中呈现出间断性。线程也有就绪,阻塞和运行三种基本状态。

引入线程之后,进程只作为除 CPU 以外的系统资源的分配单位,线程直接作为 CPU 的分配单元。

  1. 线程与进程的比较
  • 调度

在引入线程的操作系统中,进程是拥有资源的基本单位,线程是独立调度的基本单元。在不同进程中进行线程切换,会引起进程切换。

  • 拥有资源

线程不拥有资源,但可以访问其隶属进程的系统资源

  • 并发性

在引入线程的操作系统中,不仅进程之间可以并发执行,而且多个线程之间也可以并发执行,提高了系统的资源利用率。

  • 系统开销

线程切换和线程间通信的开销远小于进程的开销

  • 地址空间和其他资源

进程之间互相独立,进程内线程共享进程的资源

  • 通信方面

进程间通行需要进程同步和互斥工具的辅助,以保证数据的一致性。而线程可以通过读写进行数据段来通信(线程间的共享内存)

  1. 线程的属性

线程的主要属性如下:

  • 线程是一个轻型实体,不直接拥有系统资源
  • 不同的线程可以执行相同的程序
  • 同一进程内的线程可以共享资源
  • 线程是 CPU 的独立调度单位
  • 一个线程被创建后,便开始了它的生命周期
  1. 线程的实现方式

线程的实现可以分为两类: 用户级线程和内核级线程

  • 用户级线程

在用户级线程中,有关线程管理的所有工作都有应用程序完成

  • 内核级线程

在内核级线程中,线程管理的所有工作由内核完成

  1. 多线程模型

用户级线程可以映射到内核级线程

# 2.2 处理机调度

# 2.3.1 调度的概念

  1. 调度的基本概念

在多道程序系统中,进程的数量往往多于处理机的个数,因此进程争用处理机的情况在所难免。 处理机调度是对处理机进行分配,即就绪队列按照一定的算法选择一个进程,并将处理机分配给它运行,以实现进程并发的执行。

  1. 调度的层次

一个作业从提交开始直到完成,往往要经历以下三个调度。

  • 作业调度,又称高级调度,其主要任务是从外存中挑选作业,给它分配资源。对于每个作业只调入一次,调出一次。
  • 内存调度,又称中级调度,其作用是提高内存利用率和系统吞吐量。将暂时不能运行的进程挂起,将具备运行条件的进程改为就绪。
  • 进程调度,又称低级调度,其主要任务是从就绪队列中选择一个进程,将处理机分配给它执行。此调度频率很高。
  1. 三级调度的联系
  • 作业调度为进程活动做准备,进程调度使进程正常活动起来,中级调度将暂时不能运行的进程挂起。
  • 作业调度次数少,中级略多,进程调度频率最高。
  • 作业调度是最基本的,不可或缺的。

# 2.2.2 调度的时机,切换与过程

进程调度和切换程序是操作系统内核程序,请求调度的事件发生后,才可能运行进程调度程序,调度了新的就绪进程后,才会进行进程间的切换。

进程切换往往在调度完成后立刻发生,它要求保存原进程当前切换点的现场信息(类似汇编在循环前将之前存在寄存器中的值存入堆栈中),恢复被调度进程的现场信息。

现场切换时,操作系统内核将原进程的现场信息推入当前进程的内核堆栈来保存他们,并更新堆栈指针。

内核完成从新进程的内核栈中装入新进程的现场信息,更新当前运行进程空间指针,重设 PC 寄存器等相关工作之后,开始运行新的进程。

# 2.2.3 进程调度方式

所谓进程调度方式,就是指当某个进程正在处理机上执行时,有优先级更高的进程进入就绪队列,此时该如何分配处理机。

于是就引出了一下两种进程调度策略:

  • 非剥夺式:等待当前进程执行完成进入阻塞态,然后再执行队列内的高优先级进程
  • 剥夺式:立即停止当前进程,执行队列内的高优先级进程

采用剥夺 Ⅹ 的调度,对提高系统的吞吐率和响应效率有明显的好处,但必须遵顼一定的原则,主要有优先权,短进程优先和时间片原则等。

# 2.2.4 调度的基本准则

为了比较处理机调度算法的性能,人们提出了很多评价标准,下面介绍主要的几种:

  • CPU 利用率,尽可能使 CPU 保持“忙”状态
  • 系统吞吐量,单位时间 CPU 完成作业的数量
  • 周转时间,作业提交到完成所经历的时间
  • 等待时间,进程处于等处理机状态的时间之后
  • 响应时间,从用户提交请求到系统首次产生响应所用的时间

# 2.2.5 典型的调度算法

操作系统中存在多种调度算法,下面介绍几种常用的调度算法。

  1. 先来先服务调度算法,最简单最容易想到的算法
  2. 短作业优先调度算法,平均等待时间最短,但对长任务不友好
  3. 优先级调度算法,考虑优先级进行调度
  4. 高响应比优先调度算法,综合先来后到和短任务优先进行响应比的评估
  5. 时间分片轮转调度算法,将 CPU 资源切分为一个个小的时间片进行资源分配
  6. 多级反馈队列调度算法,综合优先级和时间分片,开多个队列分配不同优先级和不同长度的时间片

# 2.3 进程同步

# 2.3.1 进程同步的基本概念

再多道程序环境下,进程是并发执行的,不同进程之间存在着不同的相互制约的关系。为了协调进程与进程之间的相互制约关系,引入了进程同步的概念,来保证计算机和我们的程序能产出正确的计算结果。

  • 临界资源

虽然多个进程可以共享系统中的各种资源,但其中许多资源一次只能为一个进程所用,我门将一次仅允许一个进程使用的资源称为临界资源。

许多物理设备都属于临界资源,此外许多变量,数据被多个进程共享,也属于临界资源

对临界资源的访问,必须互斥地进行

  • 同步

同步亦称直接制约关系,多个进程因为需要再某个位置上协调它们的工作次序而等待,传递信息所产生的制约关系。这种关系源于进程之间的相互合作。

  • 互斥

互斥也称作间接制约关系,当一个进程进入临界区使用资源时,另一个进程必须等待。这种关系源于临界资源的限制。

# 2.3.2 实现临界点互斥的基本方法

  • 软件方法
  1. 算法一:单标志法。设置一个公用整型变量,用于指示被允许进入临界区的进程编号。缺点,可能被单个进程占用编号但并未使用资源,导致资源利用不充分
  • 硬件方法
  1. 中断屏蔽方法。当一个进程正在使用临界资源时,禁止一切中断的发生
  2. 硬件指令方法。使用定义一个原子操作,不可分割(没搞明白)

# 2.3.3 信号量

信号量机制是一种功能较强的机制,可用来解决互斥和同步问题。它只能被两个标准的原语访问,wait 和 signal,也可几位P操作P操作

原语是指完成某种功能且不被分割,不被中断执行的操作序列,通常可由硬件来实现。比如前面说的硬件指令方法。

原语之所以不能被中断执行,是因为对变量的操作若被打断,可能会去运行另一个会对同一变量进行操作的过程,从而出现临界段问题。

WARNING

暂时略过

  1. 整形信号量
  2. 记录型信号量
  3. 利用信号量实现同步
  4. 利用信号量实现进程互斥
  5. 利用信号量实现前驱关系
  6. 分析进程同步和互斥问题的方法步骤

# 2.3.4 管程

管程用于管理线程?王道书上这一段没看懂,后续再去看其他更加深入的书进行了解吧。

Wiki

管程 (英语:Monitors,也称为监视器) 是一种程序结构,结构内的多个子程序(对象或模块)形成的多个工作线程互斥访问共享资源。

管程实现了在一个时间点,最多只有一个线程在执行管程的某个子程序。

  1. 管程的定义

    系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对资源所执行的操作来表征该资源,而忽略它们的内部结构和实现细节。
    管程是由一组数据及定义在这组数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程。

  2. 管程的组成

  • 局部于管程的共享结构数据
  • 对该数据结构进行操作的一组过程
  • 对局部于管程的共享数据设置初始值的语句
  1. 管程的基本特性
  • 局部于管程的数据只能被局部于管程内的过程所访问
  • 一个进程只有通过调用管城内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管城内执行某个过程

管程是一个语言成分,通常由编程语言的编译器实现,因此管程的互斥访问完全由编译程序在编译时自动添加,而且保证准确。

# 2.3.5 经典同步问题

WARNING

暂时略过

  1. 生产者-消费者问题
  2. 读者-写者问题
  3. 哲学家进餐问题
  4. 吸烟者问题

# 2.4 死锁

# 2.4.1 死锁的概念

  1. 死锁的定义
  2. 死锁产生的原因

# 2.4.2 死锁的处理策略

  1. 死锁预防
  2. 避免死锁
  3. 死锁的检测及接触

# 2.4.3 死锁的预防

  1. 破坏互斥条件
  2. 破坏不剥夺条件
  3. 破坏请求并保持条件
  4. 破坏循环等待条件

# 2.4.4 死锁的避免

  1. 系统安全专状态
  2. 银行家算法
  3. 安全性算法举例

# 2.4.5 死锁的检测和接触

  1. 资源分配图
  2. 死锁定理
  3. 死锁接触

# 2.5 本章疑难点

进程与程序的区别和联系

  1. 进程是程序及其数据在计算机上的一次运行活动,是一个动态概念。从静态角度看,进程是由程序、数据和进程控制块三部分组成。
  2. 进程是程序的一次执行过程,是动态地创建和消亡那个的,具有一定的生命周期。
  3. 一个进程可以执行一个或几个程序,一个程序也可构成多个进程。

死锁与饥饿

银行家算法的工作原理

进程同步、互斥的区别和联系

并发进程的执行会产生相互制约的关系:

  • 一是进程间竞争使用临界资源,只能让它们逐个使用,称为互斥
  • 二是进程之间协同完成任务,在关键点上一个进程等待另一个进程,称为同步

作业和进程的关系

进程是系统资源的使用者,系统的资源大部分都是以进程为单位进行分配的。而用户使用计算机的目的是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。