进程的描述与控制

进程的描述与控制

1. 前驱图

所谓前驱图，是指一个有向循环图，可记为DAG，它用于描述进程之间执行的先后顺序。图中的每个结点可用来表示一个进程或程序段，乃至一条语句，结点间的有向边则表示两个结点之间存在的偏序或前趋关系。

P_i →P_j 表示P_i是P_j的直接前趋，P_j是P_i的直接后继。

在前趋图中，没有前趋的结点成为初始结点，没有后继的结点称为终止结点。

每个结点还有一个重量，用于表示该结点所含有的程序量或程序的执行时间。

注意：前趋图中是不允许有循环的，否则必然会产生不可能实现的前趋关系。

2. 进程的引入

2.1 顺序程序及特点

计算

程序的一次执行过程称为一个计算，它由许多简单操作所组成。

程序的顺序执行

一个计算的若干操作必须按照严格的先后次序顺序地执行，这类计算过程就是程序的顺序执行过程。 顺序执行的特点

① 单道系统的工作情况

​ 对用户作业的处理——

​ ➀ 输入用户的程序和数据

​ ➁ 进行计算

​ ➂ 打印计算结果

② 顺序程序的特点

顺序性——处理机的操作严格按照程序所规定的顺序执行封闭性——程序一旦开始执行，其计算结果不受外界因素的影响可再现性——程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关

2.2 并发程序

​ (1) 多道系统的工作情况

​

​ (2) 什么是程序的并发执行

​ ① 定义

若干个程序段同时在系统中运行，这些程序段的执行在时间上时重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠使很小的一部分，也称这几个程序段使并发执行的。

​ ② 三个并发执行的程序段

​

​ ③ 并行语句记号

​

​ (3) 并发程序的特点

​ ① 失去程序的封闭性和可再现性

​ 若一个程序的执行可以改变另一个程序的变量，那么，后者的输出就可能有赖于各程序执行的相对速度，即失去了程序的封闭性等特点。

​ ② 程序与计算不再一一对应

​ ③ 程序并发执行的相互制约

间接的相互制约关系——资源共享 直接的相互制约关系——公共变量

2.3 什么使与时间有关的错误

程序并发执行时，若共享了公共变量，其执行结果与各并发程序的相对速度有关，即给定相同的初始条件，若不加以控制，也可能得到不同的结果，此为与时间有关的错误。 因此，操作系统中引入进程概念，用来描述多道程序的同时运行过程和生命周期。

3. 进程的定义及描述

3.1 进程的定义

进程是具有独立功能的程序关于某个数据集合上的一次运行活动，是系统进行资源分配和调度的独立单位。程序的一次执行过程是正在运行程序的抽象将一个CPU变幻成多个虚拟的CPU系统资源以进程为单位分配，每个具有独立的地址空间操作系统将CPU调度给需要的进程

3.2 进程的特征

进程和程序是两个截然不同的概念，除了进程具有程序所没有的PCB结构外，还有如下特征：

​ (1) 动态性

​ (2) 并发性

​ (3) 独立性

​ (4) 异步性

(1) 进程与程序的区别

​ ① 程序是静态的概念，进程是动态的概念

​ ② 进程是一个独立运行的活动单位

​ ③ 进程是竞争系统资源的基本单位

​ ④ 一个程序可以对应多个进程，一个进程至少包含一个程序

3.3 进程地址空间

​

3.4 进程映像

对进程执行活动全过程的静态描述

由进程地址空间内容、硬件寄存器内容及与该进程相关的内核数据结构、内核栈组成 用户相关：进程地址空间(包括代码段、数据段、堆和栈、共享库…)寄存器相关：程序计数器、指令寄存器、程序状态寄存器、栈指针、通用寄存器等的值内核相关： 静态相关：PCB及各种资源数据结构动态部分：内核栈(不同进程在进入内核后使用不同的内核栈)

3.5 上下文切换

将CPU硬件状态从一个进程切换到另一个进程的过程称为上下文切换

进程运行时，其硬件状态保存在CPU上的寄存器中

寄存器：程序计数器、程序状态寄存器、栈指针、通用寄存器、其他控制寄存器的值

进程不运行时，这些寄存器的值保存在进程控制块PCB中；当操作系统要运行一个新的进程时，将PCB中的相关值送到对应的寄存器中

3.6 进程控制块PCB

3.6.1 PCB的定义

PCB: Process Control Block 又称 进程描述符、进程属性操作系统用于管理控制进程的一个专门数据结构记录进程的各种属性，描述进程的动态变化过程 PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的 进程表：所有进程的PCB集合

3.6.2 进程的组成

​ ① 程序和数据 —描述进程本身所应完成的功能

​ ② PCB —进程的动态特征，该进程与其他进程和系统资源的关系

3.6.3 进程控制块的主要内容

​ ① 进程描述信息

进程标识符(process ID),唯一，通常是一个整数

进程名，通常基于可执行文件名，不唯一用户标识符(user ID)进程组关系

​ ② 进程控制信息

当前状态优先级代码执行入口地址程序的磁盘地址运行统计信息(执行时间、页面调度)进程间同步和通信进程的队列指针进程的消息队列指针

​ ③ 所拥有的资源和使用情况

虚拟地址空间的状况打开文件列表

​ ④ CPU现场信息

4. 进程的状态与转换

4.1 进程的三种基本状态

进程的三种基本状态 运行态(Running)—占有CPU，并在CPU上运行就绪态(Ready)—已经具备运行条件，但由于没有空闲CPU，而暂时不能运行等待态(Waiting/Blocked)—因等待某一事件而暂时不能运行

4.2 三状态模型及状态转换

​

​ ① 就绪 → 运行

​ 调度程序选择一个新的进程运行

​ ② 运行 → 就绪

​ 1.运行进程用完了时间片

​ 2.一个高优先级进程进入就绪状态，抢占正在运行的进程

​ ③ 运行 → 等待

​ 当一个进程等待某个事件发生时

​ ④ 等待 → 就绪

​ 所等待的事发生了

4.3 进程的其他状态

创建 已完成创建一进程所必要的工作—PID、PCB但尚未同意执行该进程—因为资源有限 终止 终止完成后，进程进入该状态可完成一些数据统计工作资源回收 挂起 用于调节负载进程不占用内存空间，其进程映像交换到磁盘上

4.4 进程的五状态模型

4.5 进程的七状态模型

4.6 LINUX状态示意图

4.7 进程队列

操作系统为每一类进程建立一个或多个队列队列元素PCB伴随进程状态的改变，其PCB从一个队列进入另一个队列 多个等待队列等待的事件不同就绪队列也可以多个单CPU情况下，运行队列中只有一个进程

5. 进程的控制

进程控制操作完成进程各状态之间的转换，由具有特色功能的原语完成

原语

完成某种特定功能的一段程序，具有不可分割性或不可中断性，即原语的执行必须事连续的，在执行过程中不允许被中断

5.1 进程的创建

给新进程分配一个唯一标识以及进程控制块为进程分配地址空间初始化进程控制块 设置默认值 设置相应的队列指针

5.2 进程的撤销

结束进程

收回进程所占有的资源 关闭打开的文件、断开网络连接、回收分配的内存、… 撤销该进程的PCB

5.3 进程阻塞

处于运行状态的进程，在其运行过程中期待某一事件发生，当被等待的事件未发生时，由进程自己执行阻塞原语，使自己由运行态变为阻塞态

5.4 UNIX的几个进程控制操作

fork() 通过复制调用进程来建立新的进程，是最基本的进程建立过程exec() 包括一系列系统调用，它们都是通过用一段新的程序代码覆盖原来的地址空间，实现进程执行代码的转换wait() 提供初级进程同步操作，能使一个进程等待另外一个进程的结束exit() 用来终止一个进程的运行

6. 进程同步

进程同步机制的主要任务，是对多个相关进程在执行次序上进行协调，使并发执行的进程之间在执行次序上进行协调，使并发执行的进程之间能按照一定的规则(或时序)共享系统资源，并能很好地相互协作，从而使进程的执行具有可再现性。

6.1 进程同步的概念

什么是进程同步

并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。具体地说，一个进程运行道某一点时，要求另一伙伴进程为它提供消息，在未获得消息之前，该进程进入阻塞态，获得消息后被唤醒进入就绪态

进程并发执行的相互制约关系

间接相互制约关系(资源共享—互斥)

直接相互制约关系(公共变量—同步)

进程互斥和同步统称为"进程同步"

进程互斥

由于各进程要求共享资源(变量、文件等)，而这些资源需要排他性使用

临界资源

系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量

临界区(互斥区)

各个进程中对某个临界资源(共享变量)实施操作的程序片段

临界资源的定义

​ 一次仅允许一个进程使用的资源称为临界资源

临界区(互斥区)的使用原则

没有进程在临界区时，想进入临界区的进程可进入不允许两个进程同时处于其临界区中临界区外运行的进程不得阻塞不得阻塞其他进程进入临界区不得使进程无限期等待进入临界区

同步机制应遵循的规则

空闲让进忙则等待有限等待让权等待

7. 经典进程的同步问题

7.1 信号量及P、V操作

信号量

一个特殊变量

用于进程间传递信息的一个整数值

定义如下：

struct semaphore { int count; queueType queue; }

P 操作——Wait(s)

P(s){ s.count--; if(s.count<0){ 该进程状态置为阻塞状态; 将该进程插入相应的等待队列s.queue末尾; 重新调度; } }

V 操作——Signal(s)

V(s){ s.count++; if(s.count <= 0){ 唤醒相应等待队列s.queue中等待的一个进程; 改变其状态为就绪态，并将其插入就绪队列; } }

用PV操作解决进程间互斥问题

分析并发进程的关键活动，划定临界区设置信号量mutex，初值为1在临界区前实施P(mutex)在临界区之后实施V(mutex)

7.2 生产者/消费者问题

问题描述

一个或多个生产者生产某种类型的数据放置在缓冲区中有消费者从缓冲区中取数据，每次取一项只能有一个生产者或消费者对缓冲区进行操作

要解决的问题

当缓冲区已满时，生产者不会继续向其中添加数据当缓冲区为空时，消费者不会从中移走数据

用信号量解决生产者/消费者问题

8. 进程的描述与控制

8.1 线程的引入

三个理由

应用的需要开销的考虑 创建一个新线程花费时间少(撤销亦如此)两个线程切换花费时间少线程之间相互通信无须调用内核(同一进程内的线程共享内存和文件) 性能的考虑 多个线程，有的计算，有的I/O

9. 线程的基本概念

进程的两个基本属性: ①资源的拥有者—进程还是资源的拥有者 ②CPU调度单位—线程继承了这一属性

定义

进程中的一个运行实体，是CPU的调度单位，有时将线程称为轻量级进程

属性

有标识符ID有状态及状态转换→需要提供一些操作不运行时需要保存的上下文有自己的栈和栈指针共享所在进程的地址空间和其他资源可以创建、撤销另一个线程 程序开始是以一个单线程进程方式运行的

10. 线程的实现

10.1 用户级线程

功能

在用户空间建立线程库：提供一组管理线程的过程运行时系统：完成线程的管理工作(操作、线程表)内核管理的还是进程，不知道线程的存在线程切换不需要内核态特权

优点

线程切换快调度算法是应用程序特定的用户级线程可运行在任何操作系统上(只需要实现线程库)

缺点

内核只将处理器分配给进程，同一进程中的两个线程不能同时运行于两个处理器上大多数系统调用是拥塞的，因此，由于内核阻塞进程，故进程中所有线程也被阻塞

10.2 核心级线程

功能

内核管理所有线程管理，并向应用程序提供API接口内核维护进程和线程的上下文线程的切换需要内核支持以线程为基础进行调度

10.3 混合模型

线程创建在用户空间完成，线程调度等在核心态完成