进程的描述与控制

前趋图和程序执行

前趋图

指一个有向无循环图，用于描述进程之间执行的先后顺序

程序顺序执行

程序的顺序执行

一个程序由若干程序组组成，每一个程序段完成特定的功能，在执行时按照先后顺序依次执行，仅前一段程序执行后，才会执行下一段程序

程序执行的特征

• 顺序性
  • 严格按照规定顺序执行
• 封闭性
  • 独占全集资源，只有程序本身可以改变资源状态，不受未接影响
• 可再现性
  • 程序初始环境和执行环境相同，不论怎么执行都可获得相同结果

程序并发执行

程序并发执行

不存在前趋关系，可以并发执行

程序并发执行时的特征

并发执行时，提高了系统的吞吐量、资源利用率，由于他们共享系统资源，是他们在执行程序时必形成相互制约关系

• 间断性
  • 共享系统资源，完成统一任务相互合作，使得这些程序之间形成制约关系，导致程序“执行————暂停————执行”间断性活动规律
• 失去封闭性
  • 资源共享，其中任一程序改变都会受到其他程序影响
• 不可再现性
  • 失去封闭性，导致不可再现性

---

进程的描述

进程的定义和特征

进程的定义

为了使并发执行的程序（含数据）都能独立运行，在操作系统中必须为配置一个专门的数据结构称之为进程控制块，一般情况下我们把进程实体就简称为进程，创建进程实质是创建进程实体中的PCB；撤销进程实质是撤销进程的PCB

• 进程是程序的一次执行
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
• 进程是具有独立功能的程序在一个数据集合上运行的过程，他是系统进行资源分配和调度的一个独立单位

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

进程的特征

• 动态性：进程的实质是进程实体的执行过程，“他由创建而产生，有调度而执行，有撤销而消亡”，可见进程有一定的生命周期。而程序只是一组有序指令集合，是静态的。
• 并发性：进程实体同存于内存中，且能在一段时间内运行。程序（没有建立PCB）是不能参与并发执行的
• 独立性：进程实体是一个能独立运行、独立获得资源和独立接收调度的基本单位
• 异步性：进程是按异步方式运行的，即按各自独立的、不可预知的速度向前推进

进程的基本状态及转换

进程的三种基本状态

• 就绪状态
  • 进程已获取除CUP外所有必要资源，只要获得CPU，便可立即执行
  • 系统中有许多出于就绪状态的进程，通常将他们按照一定的策略排成一个队列，成就绪队列
• 执行状态
  • 已获得CPU，正在执行的状态
  • 单机处理系统中，只有一个进程处于执行状态
  • 多处理机系统中，多个进程处于执行状态
• 阻塞状态
  • 正在执行进程由于发生某些事件暂时无法继续执行的状态
  • 此时OS把处理机分配给另外一个就绪进程，而让受阻进程处于暂停状态称为苏泽状态
  • 在较大系统中根据阻塞原因不能，设置多个阻塞队列

三种状态基本转换

创建状态和终止状态

• 创建状态
  • 申请一个空白PCB，向PCB中填写用于管理和控制的进程信息
  • 为该进程分配运行时所必须的资源
  • 把该进程转入就绪态并插入就绪队列中

如果进程所需资源商不能满足，进程不能被调度运行，此时进程属于创建状态

为保证进程调度必须在创建完成后进行，与确保进程控制块的完整性

• 终止状态
  • 等待操作系统善后处理
  • 将其PCB清零，将PCB返还系统

挂起操作和进程状态的转变

当挂起操作用于某个进程时，该进程将被挂起，意味着此时该进程处于静止状态。如果进程正在执行，它将暂停执行。若原本处于就绪状态，则该进程此时暂时不接受调度。与挂起操作对于的是激活操作

挂起操作的引入

• 终端用户的需要
  • 运行时发现问题，暂停程序运行
• 父进程请求
  • 父进程挂起自己某个进程
• 负荷调节的需要
• 操作系统的需要

引入挂起原语操作后三个进程状态转换

• 活动就绪—>静止就绪
• 活动阻塞—>禁止阻塞
• 禁止就绪—>活动就绪
• 禁止阻塞—>活动阻塞

引入挂起操作后五个进程状态的转换

• NULL -> 创建
• 创建 -> 活动就绪
• 创建 -> 静止就绪
• 执行 -> 终止

进程管理中的数据结构

操作系统中用于管理控制的数据结构

在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信息表或进程信息表，其中包含了资源或进程的标识、描述、状态等信息以及一批指针。通过这些指针，可以将同类资源或进程的信息表，或者同一进程所占用的资源信息表分类链接成不同的队列，便于操作系统进行查找。

OS管理的这些数据结构一般分为以下四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。

进程控制块PCB的作用

• 作为独立运行基本单位的标志
  • 进程配置PCB后就表示他已是一个能在多道环境下独立运行的合法的基本单位，PCB称为进程存在系统的唯一标识
• 能实现间断性运行方式
  • 采用停停走走的间断性的运行方式运行
• 提供进程管理所需信息
• 提供进程调度所需信息
• 实现与其他进程的同步与通信

进程控制块中的信息

• 进程标识符：唯一标识一个进程。一个进程有两个标识符
  • 外部标识符
    • 方便进程间调用
  • 内部标识符
    • 方便系统对进程调用
• 处理机状态
  • 通用寄存器
  • 指令计时器
  • 程序状态字PSW
  • 用户占指针
• 进程调度信息
  • 进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据；
  • 进程优先级，是用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；
  • 进程调度所需的其他信息，它们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；
  • 事件，是指进程由执行状态转变为阻塞状态所等待发生的事件，即阻塞原因。
• 进程控制信息
  • 进程和数据的地址，进程实体中的程序和数据的内存或外存地(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；
  • 进程同步和通信机制，这是实现进程同步和进程通信时必需的机制，如消息队列指针、信号量等，它们可能全部或部分地放在PCB中；
  • 资源清单，在该清单中列出了进程在运行期间所需的全部资源(除CPU以外)，另外还有一张已分配到该进程的资源的清单
  • 连接指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址。

进程控制块的组织方式

• 线性方式
  • 放入线性表中，将该表的首址存放在内存的一个专用区域中
    
• 链接方式
  • 链接成一个对列
    
• 索引方式
  • 根据状态不同建立几张索引表
    

---

进程控制

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

进程系统内核

• 系统泰（管态/内核态）
  • 有较高特权，能执行一切指令，访问所有寄存器和存储区，传统系统都在系统态中运行
• 用户态（目态）
  • 有较低的特权，仅能执行规定的指令，访问指定的寄存器和存储区

支撑功能

• 中断处理
  • 内核最基本的功能
• 始终管理
  • 内核一项基本功能
• 原语操作
  • 有若干指令组成的

进程的创建

允许一个进程创建另一个进程，创建进程称为父进程，被创建进程子进程，在UNIX中形成进程家族（组），子进程继承父进程拥有资源

• 申请空白PBC，为新进程申请获得唯一的数字标识
• 为进程分配所需资源
• 初始化进程控制块
  • 初始化标识信息，将系统分配的标识符和父进程标识符填入新PCB中
  • 初始化处理机状态信息，使程序计数器指向程序的入口地址
  • 初始化处理机控制信息，设置进程状态（就绪、静止状态）
  • 放入就绪队列（有空间）

进程的终止

• 引起进程终止事件
  • 正常结束
    • 进程的任务已经完成，准备退出运行
  • 异常结束
    • 越界错
      • 程序锁访问的存储区，已越出该进程的区域
    • 保护错
      • 访问不允许方的资源或文件
      • 不适当的方式访问
      • 例：写一个只读文件
    • 非法指令
      • 执行不存在指令
    • 特权指令错
      • 用户进程执行OS的指令
    • 运行超时
      • 进程执行时间超出指定时间最大值
    • 等待超时
      • 进程等待时间超出指定时间的最大值
    • 算数运算错
      • 执行一个禁止的运算
    • I/O 故障
      • 在I/O过程中发生了错误
  • 外界干预
    • 操作员或操作系统干预
    • 父进程请求
    • 因父进程终止
• 进程的终止及过程
  • 根据被终止进程标识符，从PCB集合中检索出该进程PCB，从中读取该进程状态
  • 若被终止进程处于执行状态，应立即终止进程的执行，设置调度标志为真，用于指示该进程被终止后应重新进行调度
  • 有子孙进程先结，将所有子孙进程终止，防止他们成为不可控进程
  • 把拥有的全部资源还给父进程，或者归还系统
  • 被终止进程（PBC）从所在队列（或链表）移出

进程的阻塞和唤醒

引起进程阻塞和唤醒的事件

• 向系统请求共享资源失败
  • 进程向系统请求共享资源时，系统无足够资源，此进程不能继续运行
• 等待某种操作的完成
• 新数据尚未到达
• 等待新任务的到达

进程阻塞过程（block）

阻塞市金城自身得的一种主动行为，执行–>阻塞，将PCB插入阻塞队列

进程唤醒过程（wakeup）

被阻塞进程所起的事件发生后，有关进程调用wakeup将改时间的进程唤醒。wakeup执行过程：

• 把被阻塞进从等待该事件的阻塞队列中移除
• 将其PCB中的现行状态油阻塞改为就绪
• 将该PCB插入到就绪队列中

进程的挂起与激活

进程的挂起

发生挂起进程事件后，OS将调用挂起原语suspend将制定进程或处于阻塞状态的进程挂起
suspend 执行过程

• 检查被挂起进程的状态（处于活动、就绪状态改为禁止就绪状态）
• 活动阻塞状态进程，改为禁止阻塞
• 把该进程的PCB复制到制定的内存区域
• 若被挂起的进程正在运行，则转向调度程序重新调度

进程的激活过程

发生激活事件后，OS利用激活active将指定进程激活

---

进程同步

硬件同步机制、信号量机制、管程机制

进程同步的基本概念

多个相关进程在执行次序上进行协调，使并发执行的诸进程之间按照一定规则共享系统资源

两种形式制约关系

• 间接相互制约关系
  • 共享系统资源，使这些并发执行的程序之间形成相互制约的关系
• 直接相互制约关系
  • 完成某项任务建立多个进程。这些进程完成同一项额任务而相互合作

临界资源

• 打印机
• 磁带机

临界区

• 每个进程中访问临界资源的代码称之为临界区
• 进入临界区之前，先对临界资源进行检查，看他是否正在被访问。若正在被访问，进程便可进入临界区对该资源进行访问，并设置正在访问标识

  while(true)
  {
  	进入区
  	临界区
  	退出区
  	剩余区
  }

同步机制应遵循的规则

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

硬件同步机制

关中断

进入锁测试之前关闭中断，知道完成锁测试并上锁之后才能打开中断

利用Test-and-Set指令实现互斥

利用Swap指令实现进程互斥

信号量机制

整形信号量

整型信号量定义为一个用于表示资源数目的整形量S，他与一般整型量不同，除初始化仅能通过两个标准的原子操作wait(S)和signal(S)来访问，被称为P、操作。原子操作不可中断

wait(S){
	while(S<=0);
	S--
}

signal(S){
	S++
}

记录信号量

一、整形信号量wait操作，只要S<= 就会不断地测试（未遵循“让权等待”的准则）而是进程处于忙等状态
二、记录型信号量机制不存在“忙等”现象的进程机制。但采取了“让权等待”后，会出现多个进程同时访问同一临界区资源，需要一个用于代表资源数目的变量value外还需要一个进程链表指针list，用于连接所有上述等待进程

AND型信号量

基本思想：进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。

信号量的应用

利用信号量实现进程互斥

为使多个进程能互斥的访问某临界资源，只需为该资源设置一互斥信号量mutex，并设其初始值为1

• 当mutex=0时，表示有一个进程进入临界区运行，另外一个必须等待，挂入阻塞队列；
• 当mutex=-1时，表示有一个进程正在临界区运行，另外一个进程因等待二阻塞在信号量队列中，需要被当前已在临界区运行的进程退出时唤醒

利用信号量实现前去关系

管程机制

管程定义

系统中各种硬件资源和软件资源均可用数据结构抽象的描述其资源特性，即少量信息和对该资源锁执行的操作来表示资源，而忽略他们的内部结构和实现细节。

• 管程的名称
• 局部于管程的共享数据结构说明
• 对该数据结构进行操作的一组过程
• 对局部于管程的共享数据设置初始值得语句

线程的基本概念

线程的引入

OS中引入进程目的为了使程序并发执行，提高资源利用率和系统吞吐量
OS中一如线程则是为了减少程序在并发执行时所付出的时空开销，使OS有更好的并发性

进程的两个基本属性

1. 进程是一个可拥有独立资源的独立单位，一个进程要独立运行，必须拥有一定资源（存放程序正文、数据的磁盘和内存地址空间以及I/O设备打开的文件、信号量等）
2. 进程同时又可是一个可独立运行调度和分配的基本单位，一个进程要独立运行，必须是一个可独立调度和分配的基本单位。每个进程在系统中有唯一的PCB，系统可根据其PCB感知进程的存在，也可以根据PCB中的信息对进程进行调度，还可以将端点信息保存在PCB中，利用进程PCB回复运行现场，程序独立运行的基本单位正是有这两个基本属性构成的

进程并发执行所需付出的时空开销

• 创建进程
• 撤销经常
• 进程切换

进程——作为资源调度分配的基本单位

线程与进程的比较

线程具有许多传统进程锁具有的特征

1. 调度的基本单位

• 进程
  • 进程是作为独立调度和分配的基本单位，因此进程是指能独立运行的基本单位。
  • 每次调度都时都需要进行上下文切换，开销较大
• 线程
  • 引入线程把线程作为调度和分配的基本单位，因而线程是能够独立运行的基本单位
  • 在线程切换时仅需保存和设置少量寄存器内容，切换代价远低于进程
  • 同一进程中，线程切换不会引起进程切换
  • 从一个进程中的线程切换到另一个进程中的线程时，必然会引起进程切换

2. 并发性

不仅进程之间可以并发执行，而在一个进程中的所有线程也可以并发执行，不同进程中的线程也可以并发执行

3. 拥有资源

• 进程可以拥有资源，并作为系统中拥有资源的一个基本单位
• 线程本身并不拥有系统资源，而且仅有一点必不可少的、能保证独立运行的资源
• 线程除了拥有自己的少量资源外，还允许多个进程共享该进程所拥有的资源
  • 属于同一进程的所有线程都具有相同的地址空间
  • 线程可以访问改地址空间中的每一个虚地址
  • 还可以访问进程所拥有的资源

4. 独立性

同一进程中的不同线程之间的独立性要比不能进程之间的独立性低得多

5. 系统开销

在创建或撤销进程时，系统都要为之分配和回收进程控制块、分配或回收其他资源

6. 支持多处理系统

多处理机系统中，对于传统的进程，单线程进程，不管有多少处理机该进程只能运行在一个处理机上。
多线程进程就可以将一个进程中的多个线程分配到多个处理机上

线程状态和线程控制块

1. 线程运行三个状态

• 执行状态
  • 已获得处理机正在运行
• 就绪状态
  • 以具备各种执行条件，只需获得CPU便可立即执行
• 阻塞状态
  • 因某事件受阻而处于暂停状态

2. 线程控制块TCB

每个线程配置一个线程控制块TCB，将所有用于控制和管理线程的信息记录在线程控制块中

• 线程标识符
• 一组寄存器
• 线程运行状态
• 优先级
• 线程专有存储区
• 信号品屏蔽
• 堆栈指针

3. 多线程操作系统属性

• 进程是一个可拥有资源的基本单位
• 多个线程可以并发执行
• 进程已不是可执行实体

线程的实现

线程的实现方式

线程已在许多系统中实现，但各系统的实现方式并不完全相同。在有的系统中，特别是一些数据库管理系统，如infomix所实现的是用户级线程； 而另一些系统(如Macintosh和OS/2操作系统)所实现的是内核支持线程；还有一些系统如Solaris操作系统，则同时实现了这两种类型的线程。

1. 内核支持线程KST(Kernel Supported Threads)

• 在OS中的所有进程，无论是系统进程还是用户进程，都是在操作系统内核的支持下运行的，是与内核紧密相关的。而内核支持线程KST同样也是在内核的支持下运行的，它们的创建、阻塞、撤消和切换等，也都是在内核空间实现的。为了对内核线程进行控制和管理，在内核空间也为每一个内核线程设置了一个线程控制块，内核根据该控制块而感知某线程的存在，并对其加以控制。当前大多数OS都支持内核支持线程。

• 这种线程实现方式主要有四个主要优点：

  • 在多处理器系统中，内核能够同时调度同一进程中的多个线程并行执行；
  • 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其它线程占有处理器运行，也可以运行其它进程中的线程；
  • 内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小；
  • 内核本身也可以采用多线程技术，可以提高系统的执行速度和效率。
  2. 用户级线程ULT(User Level Threads)

• 用户级线程是在用户空间中实现的。对线程的创建、 撤消、同步与通信等功能，都无需内核的支持，即用户级线程是与内核无关的。在一个系统中的用户级线程的数目可以达到数百个至数千个。由于这些线程的任务控制块都是设置在用户空间，而线程所执行的操作也无需内核的帮助，因而内核完全不知道用户级线程的存在。

• 使用用户级线程方式有许多优点：

  • 线程切换不需要转换到内核空间。
  • 调度算法可以是进程专用的。
  • 用户级线程的实现与OS平台无关，因为对于线程管理的代码是属于用户程序的一部分，所有的应用程序都可以对之进行共享。

• 而用户级线程方式的主要缺点则在于：

  • 系统调用的阻塞问题。在基于进程机制的OS中，大多数系统调用将使进程阻塞，因此，当线程执行一个系统调用时，不仅该线程被阻塞，而且，进程内的所有线程会被阻塞。而在内核支持线程方式中，则进程中的其它线程仍然可以运行。
  • 在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU，因此，进程中仅有一个线程能执行，在该线程放弃CPU之前，其它线程只能等待。

3. 组合方式

• 有些OS把用户级线程和内核支持线程两种方式进行组合，提供了组合方式ULT/KST 线程。在组合方式线程系统中，内核支持多个内核支持线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。
  

线程的实现

1. 内核支持线程的实现
   在仅设置了内核支持线程的OS中，一种可能的线程控制方法是，系统在创建一个新进程时，便为它分配一个任务数据区PTDA(Per Task Data Area)，其中包括若干个线程控制块TCB空间，
   

2. 用户级线程的实现

• 运行时系统(Runtime System)

  • 所谓“运行时系统”，实质上是用于管理和控制线程的函数(过程)的集合，其中包括用于创建和撤消线程的函数、线程同步和通信的函数，以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。

• 内核控制线程

  • 这种线程又称为轻型进程LWP(Light Weight Process)。每一个进程都可拥有多个LWP，同用户级线程一样，每个LWP都有自己的数据结构(如TCB)，其中包括线程标识符、优先级、状态，另外还有栈和局部存储区等。LWP也可以共享进程所拥有的资源。LWP可通过系统调用来获得内核提供的服务，这样，当一个用户级线程运行时，只须将它连接到一个LWP上，此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。
    

线程的创建和终止

1. 线程的创建

• 应用程序在启动时，通常仅有一个线程在执行，人们把线程称为“初始化线程”，它的主要功能是用于创建新线程。在创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的入口指针、堆栈的大小，以及用于调度的优先级等。在线程的创建函数执行完后，将返回一个线程标识符供以后使用。

2. 线程的终止

• 当一个线程完成了自己的任务(工作)后，或是线程在运行中出现异常情况而须被强行终止时，由终止线程通过调用相应的函数(或系统调用)对它执行终止操作。但有些线程(主要是系统线程)，它们一旦被建立起来之后，便一直运行下去而不被终止。在大多数的OS中，线程被中止后并不立即释放它所占有的资源，只有当进程中的其它线程执行了分离函数后，被终止的线程才与资源分离，此时的资源才能被其它线程利用。