操作系统 第二章 进程的描述与控制

前趋图和程序执行

前趋图

含义

指一个有向无循环图DAG( Directed Acyclic Graph)，它用于描述进程之间执行的先后顺序。

每个结点可用来表示一个进程或程序段，甚至一条语句，结点间的有向边则表示两个结点之间存在的偏序( Partial Order)或前趋关系( Precedence Relation）

表示方式

文字描述：用文字或符号来表示结点和边，以及它们之间的关系。例如，用“→”表示前趋关系，用“(Pi,Pj)∈→”表示Pi是Pj的直接前趋，用“[ ]”表示并发执行，等等

图形描述：用图形元素来表示结点和边，以及它们之间的关系。例如，用圆圈或方框表示结点，用箭头表示边，用不同的颜色或样式表示不同的属性，等等

矩阵描述：用矩阵来表示结点和边，以及它们之间的关系。例如，用邻接矩阵表示结点间是否有边，用关联矩阵表示结点和边的关系，用关系矩阵表示结点间的偏序关系，等等

顺序执行

含义

一个程序由若干个程序段执行，每个程序段完成特定的功能，在执行过程中，这些程序段需要按照某种顺序执行，当一个程序段完成后，才能运行后一段程序段。

特征

顺序性

?严格按照程序规定的顺序执行

封闭性

程序运行时独占全机资源

可再现性

当环境与初始条件一样时，执行的结果也一样

并发执行

含义

引入了多道程序技术，使程序或程序段之间能并发执行。只有不存在前趋关系的程序才有可能并发执行,否则无法并发执行。

特征

竞争性：并发执行的程序之间可能会争夺有限的系统资源，如CPU、内存、I/O设备等，这可能会导致程序的执行效率降低或出现死锁等问题

协作性：并发执行的程序之间可能会为了完成同一项任务而相互合作，如通过消息传递、信号量、管道等方式进行通信和同步

随机性：并发执行的程序之间的执行顺序和时间是不确定的，取决于系统的调度策略和运行环境，这可能会导致程序的执行结果不可预测

进程

描述

定义

(1)进程是程序的一次执行

(2)进程是一个程序及其数据在处理机上顺序执行时所发生的活动。

(3)进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

进程实体，Process Control Block，PCB

作用

PCB是操作系统中用于描述进程的基本情况和活动过程的数据结构，它是系统进行资源分配和调度的一个独立单位。通过PCB，操作系统可以对进程进行控制和管理。

组成

程序段：包含了执行的代码。

PC：程序计数器，存储了下一条要执行的指令的地址。

相关的数据段：包含了程序运行所需要的数据。

进程状态：如就绪、运行、等待等状态。

进程ID：唯一标识一个进程。

特征

动态性

进程的实质是程序在多道程序系统中的一次运行过程，它是动态产生，动态消亡的。

并发性

多个进程可以在同一段时间内交替地运行。

独立性

每个进程都是一个独立的运行单位，它们各自拥有独立的资源。

异步性

由于进程间的相互影响，使得进程具有不确定性，即同样的进程在不同的运行环境下可能会有不同的结果。

结构特征

每个进程都有自己独立的系统资源，如虚拟地址空间，打开文件，安全上下文等。

切换特性

进程可以被挂起，其状态被保存后，稍后再恢复运行，这种特性称为切换。

交互性

进程在运行过程中可能需要与用户或其他进程进行交互，以完成某些任务。

生命周期

每个进程从创建到终止，经历了一系列的状态，这就是进程的生命周期。

基本状态与转换

三种基本状态

就绪(Ready)状态

进程处于准备好运行的状态，一旦得到CPU就可以立即运行

执行(Running)状态

正在运行的进程所处的状态

阻塞(Block)状态

由于某些因素，导致该进程即使的到CPU也无法运行（还需要I/O设备），就会进入阻塞状态

状态转换

创建状态与终止状态

创建状态

进程是需要创建的，且创建进程的过程十分复杂

终止状态

分为两个步骤（首先，等待操作系统进行善后处理，然后将其PCB清零，将PCB空间返还系统）

挂起操作

引入

挂起处于静止，不再参与CPU的竞争

终端用户的需要

用户可能需要暂停某个进程的运行，以便进行其他操作，或者等待某些资源可用。

父进程的需要

父进程可能需要暂停子进程的运行，以便进行某些操作，或者等待子进程的某些结果。

负荷调节的需要

当系统负荷过大时，操作系统可能需要暂停一些低优先级的进程，以保证高优先级进程的运行。

操作系统的需要

操作系统可能需要暂停某个进程的运行，以进行系统级别的操作，如备份、恢复等。

操作过程：挂起操作通常包括以下步骤：

保存进程状态：操作系统保存进程的当前状态，包括程序计数器、寄存器值、内存状态等。

更新PCB：操作系统更新进程的PCB，将进程状态设置为挂起。

释放资源：操作系统释放进程占用的部分或全部资源，如CPU、内存等。

等待唤醒：进程在挂起状态下等待被唤醒。唤醒操作通常由用户、父进程或操作系统发起。

数据结构

定义

进程控制块PCB（Process Control Block）PCB是操作系统中最重要的记录型数据结构，它包含了操作系统需要管理和控制进程的所有信息。

作用

使一个多道程序环境下不能独立运行的程序成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。

特点

作为独立运行基本单位的标志：当系统创建一个新进程时，就会建立一个PCB，进程结束时随之消亡

能实现断性运行方式：通过保存和恢复进程的上下文信息，PCB使得进程能够在被中断后再次恢复运行。

提供进程管理所需的信息：PCB包含了进程的状态、优先级、CPU寄存器值和内存映射等信息，这些信息是操作系统进行进程管理和调度的基础。

提供进程调度所需要的信息：如果在优先级调度算法中，需要知道进程的优先级，这些信息都存储在PCB中。

实现与其他进程的同步与通信：PCB中包含了进程的同步和通信机制，如信号量、消息队列等，使得进程能够与其他进程进行同步和通信。

资源占用：PCB中还包含了进程所占用的资源信息，如打开的文件、分配的内存等。

父子关系：在有些操作系统中，PCB还包含了进程的父子关系信息，这对于进程的创建和终止非常重要。

保护和安全：PCB中还可能包含进程的保护和安全信息，如进程的权限、安全级别等。

信息

进程标识符(PLD)

外部标识符

用户和操作系统用来识别进程的标识符，通常是一个有意义的名字。

内部标识符

操作系统内部用来识别进程的标识符，通常是一个唯一的数字。

处理机状态

这包括程序计数器（PC），它存储了下一条要执行的指令的地址，以及其他寄存器的内容。这些信息在进程从运行状态切换到就绪状态或阻塞状态时被保存，然后在进程重新进入运行状态时被恢复。

进程调度信息

这包括进程的状态（如就绪、运行、阻塞），进程的优先级，以及其他用于进程调度的信息。这些信息用于决定哪个进程应该被分配到CPU。

进程控制信息

这包括进程同步和通信的机制，如信号量、消息队列等，以及进程的上下文切换信息。这些信息用于控制进程的执行，以及进程之间的交互。

组织方式

线性方式

线性方式是最简单的PCB组织方式，所有的PCB都被组织在一个线性表中。这种方式实现简单，但是查找效率较低，特别是当进程数量较多时。

链式方式

链式方式是把具有相同状态的进程的PCB分别通过PCB中的链接字链接成一个队列。这样，操作系统可以快速地找到所有具有特定状态的进程。这种方式查找效率较高，但是需要更复杂的管理策略。

索引方式

索引方式是系统根据所有进程状态的不同，建立几张索引表。每张索引表对应一种进程状态，表中的每一项都是一个指向具有该状态的进程的PCB的指针。这种方式查找效率最高，但是需要更多的存储空间。

双向链表方式

在链式方式的基础上，可以使用双向链表来组织PCB，这样可以更方便地插入和删除PCB。

哈希表方式

在索引方式的基础上，可以使用哈希表来组织PCB，这样可以进一步提高查找效率。

控制

定义

进程管理中最基本的功能，主要包括创建新进程、终止已完成的进程、将因发生异常情况而无法继续运行的进程置于阻塞状态、负责进程运行中的状态转换等功能。

进程控制一般是由操作系统的内核中的原语来实现的。

内容

创建

定义

在操作系统中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而被创建的进程称为子进程，子进程可以继承父进程所拥有的资源。在撤销父进程时必须撤销子进程。

引起

用户登录：当用户登录系统时，系统会为用户创建一个或多个进程，以运行用户的程序。

作业调度：当操作系统的调度器决定启动一个新的作业时，会创建一个新的进程来执行这个作业。

提供服务：当操作系统需要提供某种服务时，如处理用户的请求或响应硬件中断，可能会创建一个新的进程。

应用请求：应用程序在运行过程中，可能会请求操作系统创建一个新的进程，以完成某些任务。

过程

申请空白PCB：操作系统为新进程申请一个空白的进程控制块（PCB），并为新进程分配一个唯一的数字标识符。

为新进程分配资源：操作系统为新进程分配运行所需的资源，如CPU时间、内存空间等。

初始化PCB：操作系统初始化新进程的PCB，包括设置进程状态、初始化程序计数器、设置优先级等。

将新进程插入就绪队列：如果进程就绪队列能够接纳新进程，操作系统将新进程的PCB插入就绪队列。当CPU空闲时，调度器会从就绪队列中选择一个进程执行。

复制父进程的地址空间：在某些情况下，操作系统会复制父进程的地址空间到子进程，这样子进程就可以访问父进程的代码和数据。

设置子进程的状态：操作系统会设置子进程的状态为就绪，以便子进程可以被调度器选中执行。

终止

引起

正常结束：进程完成了它的任务，或者它的父进程请求它终止。

异常结束：进程可能因为各种错误条件而终止，例如：

越界错误：进程试图访问其地址空间之外的内存。

保护错误：进程试图执行一些它没有权限执行的操作。

非法指令：进程试图执行一条无效的机器指令。

特权指令错误：进程试图执行一条只有操作系统才能执行的特权指令。

运行超时：进程运行时间超过了某个预定的限制。

等待超时：进程等待某个事件的时间超过了某个预定的限制。

算术运算错误：进程在执行算术运算时发生错误，例如除以零。

I/O故障：进程在执行I/O操作时发生故障。

外界干预：用户或操作系统命令可以强制终止进程。

阻塞与唤醒

引起

向系统请求共享资源失败：如果进程请求的资源正在被其他进程使用，那么进程将被阻塞，直到资源可用。

等待某种操作的完成：例如，进程可能需要等待I/O操作完成。

新数据尚未到达：例如，进程可能正在等待从网络接收数据。

等待新任务的到达：例如，在交互式系统中，进程可能正在等待用户的输入。

挂起与激活

挂起：挂起是一种进程控制操作，使得进程处于静止状态，不再参与CPU的竞争。挂起操作的引入主要是出于以下几个需要：

终端用户的需要：用户可能需要暂停某个进程的运行，以便进行其他操作，或者等待某些资源可用。

父进程的需要：父进程可能需要暂停子进程的运行，以便进行某些操作，或者等待子进程的某些结果。

负荷调节的需要：当系统负荷过大时，操作系统可能需要暂停一些低优先级的进程，以保证高优先级进程的运行。

操作系统的需要：操作系统可能需要暂停某个进程的运行，以进行系统级别的操作，如备份、恢复等。

激活：当挂起的进程可以继续运行时，操作系统将激活该进程。激活操作通常由用户、父进程或操作系统发起。

通信

含义

进程间的信息交换是指在并发执行的进程之间传递信息的过程。这是实现进程同步和协调的重要手段。

进程之间的信息交换

类型

低级进程通信

这种通信方式效率较低，且对用户不透明。它通常涉及到直接操作系统调用和硬件操作。

高级进程通信

用户可以直接利用操作系统提供的一组通信命令来高效地传送大量数据。这种通信方式更加友好，易于使用。

实现方式

共享存储器系统(Shared-Memory System)

?进程间通过共享某些数据结构或共享存储区进行通信。这种方式需要处理好并发访问和数据一致性的问题。

管道(Pipe)通信

用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件（pipe文件）。管道机制必须提供的协调能力：互斥、同步、确定对方是否存在。

消息传递系统 (Message Passing System)

进程不必借助任何共享区或数据结构，而是以格式化的消息（message）为单位，将通信的数据封装在消息中，完成进程间的数据交换。因实现方式不同可以分为两类：

直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。也称为消息缓冲通信。

间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从（信箱）中取得消息。也称信箱通信。在网络中称为电子邮件系统。

客户机-服务器系统（Client-Server system）

客户端进程发送请求到服务器进程，服务器进程处理请求并将结果返回给客户端进程。这种模式广泛应用于网络服务中。

远程过程调用（RPC）

这是一种高级的进程间通信方式，允许一个进程在远程主机上执行另一个进程的函数或过程，就像在本地执行一样。

信号（Signal）

这是一种异步的通信方式，进程可以发送信号给其他进程，通知它们发生了某种事件。

线程

概念

进程：在操作系统中引入进程的目的是为了使多个程序能够并发执行，以提高资源的利用率和系统的吞吐量。每个进程都有自己的独立地址空间，每次进程切换都需要切换地址空间，这会导致较大的开销。

线程：在操作系统中引入线程，则是为了减少程序在并发执行时所付出的时空开销，使操作系统具有更好的并发性。线程是进程内的一个执行单元，也是进程内的并发执行的单位，线程在执行过程中，它们共享同一组系统资源，如虚拟地址空间和系统资源等，相对于进程，线程是一种更轻量级的、更小的执行单位。

引入

进程的两个基本属性：进程的两个基本属性是资源拥有权和调度/执行。资源拥有权是指进程是资源分配的基本单位，它拥有一定的资源；调度/执行是指进程是独立调度和分派的基本单位，它可以独立运行。

程序并发执行所须付出的时空开销：程序并发执行时，需要付出的时空开销主要包括进程切换、通信、同步等开销。为了减少这些开销，可以引入线程，使得在同一进程内的多个线程可以并发执行，从而减少了进程切换和通信的开销。

线程——作为调度和分派的基本单位：线程是进程内的一个执行单元，也是进程内的并发执行的单位。在多线程环境下，操作系统可以将CPU时间分配给任何准备好运行的线程，一个进程中的各个线程之间可以并发执行。

进程与线程比较

1.调度的基本单位

在传统的操作系统中，进程是调度的基本单位；

而在现代操作系统中，线程成为了调度的基本单位，这使得系统在进行任务切换时，可以避免切换整个进程带来的大量开销。

2.并发性

进程和线程都支持并发执行。在多道程序设计中，多个进程可以并发执行；在一个进程中，多个线程也可以并发执行。

3.拥有资源

进程是资源分配的基本单位，它可以拥有自己的资源；

而线程本身并不拥有系统资源，但它可以访问隶属于同一进程的其它线程所拥有的资源。

4.独立性

每个进程都拥有一个独立的地址空间和其他资源，除了共享全局变量外，不允许其它进程访问。

而在同一进程中的不同线程，它们共享进程的内存地址空间和其他资源，因此线程之间的通信更加方便。

5.系统开销

在创建和撤销进程时，系统都要为之分配和回收进程控制块、分配或回收其它资源，线程的切换的代价远远低于进程。

进程的创建和撤销需要分配和回收资源，如内存、I/O设备等，因此涉及到的系统开销较大。

而线程的切换只涉及到堆栈和寄存器等信息的保存与恢复，系统开销较小。

6.支持多处理机系统

在多处理机系统中，一个进程的多个线程可以被分配到多个处理机上并行执行，从而提高系统的并行性。

线程状态与线程控制块

线程状态

与传统的进程一样，在各线程之间也存在着共享资源和相互合作的制约关系，致使线程在运行时也具有间断性。

执行状态

线程已具备了所有执行条件，只需再获得CPU便可立即执行。这通常意味着线程已经准备好运行，但由于其他线程正在使用CPU，所以它暂时无法运行。

就绪状态

线程已具备了各种执行条件,只须再获得CPU便可立即执行;

阻塞状态

线程在执行过程中因某事件（如I/O操作、系统调用或等待某些资源）受阻而处于暂停状态。例如，当一个线程执行从键盘读入数据的系统调用时，该线程就会阻塞，直到数据输入完成。

终止状态

线程已完成执行或由于某种原因被终止，但系统尚未清除其对应的数据结构。在此状态下，线程等待其父进程读取其退出状态。

新建状态

线程已被系统识别，但尚未投入运行。在此状态下，线程等待系统分配给它必要的资源。

等待状态

线程主动放弃CPU，并转入等待状态，直到某个特定条件得到满足。例如，线程调用了sleep函数，或者等待一个信号量。

线程控制块

含义

TCB是操作系统用来描述线程最基本的信息的数据结构

组成

①线程标识符

这是一个唯一标识线程的标识符。

②一组寄存器

这包括程序计数器、堆栈指针以及其他寄存器。这些寄存器的值在每次线程切换时都会被保存和恢复。

③线程执行状态

这表示线程的当前状态，如运行、就绪、阻塞等。

④优先级

这是一个数字，表示线程的优先级。数字越大，优先级越高。

⑤专有存储区

这是线程自己的存储区，用于存储线程的局部变量等信息。

⑥信号屏蔽

这是一组标志，用于控制哪些信号可以被线程接收。

⑦堆栈指针

这是一个指针，指向线程的堆栈。堆栈用于存储函数调用的历史信息，如返回地址、局部变量等。

多线程操作系统中进程属性 在多线程操作系统中，进程主要包含以下属性：

进程标识符：这是一个唯一标识进程的标识符。

进程状态：这表示进程的当前状态，如运行、就绪、阻塞等。

进程控制块：这是一个数据结构，包含了进程的所有信息，如进程状态、寄存器值、内存映射等。

资源列表：这是一个列表，包含了进程所拥有的所有资源，如打开的文件、分配的内存等。

线程列表：这是一个列表，包含了进程中的所有线程。每个线程都有一个对应的线程控制块。

实现

实现方式

内核支持线程（Kernel-Level Threads，KLT）：这种线程由操作系统内核创建和管理。每个线程都被操作系统视为一个独立的调度实体，因此这种线程可以在多处理器系统中并行运行。但是，由于线程管理（如创建、同步、调度和终止线程）需要系统调用，所以这种线程的管理开销较大。

用户级线程（User-Level Threads，ULT）：这种线程完全在用户空间中实现，不需要内核支持。线程管理的所有工作都由应用程序完成，不需要系统调用，因此管理开销较小。但是，由于操作系统只看到单个、单线程的进程，因此这些线程不能在多处理器系统中并行运行。

两种线程的组合方式：一些系统同时使用用户级线程和内核级线程，以结合两者的优点。例如，应用程序可以创建多个用户级线程，并将这些线程映射到一个或多个内核级线程。

具体实现

KST（Kernel Supported Threads）：这是内核支持线程的一种具体实现方式。在这种方式中，所有线程操作（如创建、同步、调度和终止线程）都由内核直接完成。

ULT（User Level Threads）：这是用户级线程的一种具体实现方式。在这种方式中，线程库在用户空间中提供了一组API，应用程序可以调用这些API来完成线程操作。

创建与终止

创建：线程的创建通常由创建线程的函数完成，如pthread_create()。这个函数会分配并初始化一个新的线程控制块，然后将新线程添加到调度器的就绪队列中。

终止：线程的终止可以由线程自身、同一进程中的其他线程或父进程来完成。线程自身可以调用退出线程的函数，如pthread_exit()，来结束自己的执行。同一进程中的其他线程可以调用取消线程的函数，如pthread_cancel()，来结束一个线程。父进程可以通过发送信号来结束一个或多个线程。