线程与进程

1、多道程序设计

概念：多道程序设计是指，允许多个程序同时进入一个计算机系统的主存储器并进行计算的方法

一个简单的例子：
例如计算某个数据处理问题，要求从输入机(速度为 6400字符／秒)输入 500 个字符，经处理(费时 52 毫秒)后，将结果(假定为 2000 个字符)存到磁带上(磁带机速度为 10 万字符／秒)，然后，再读 500 个字符处理，直至所有的输入数据全部处理完毕。如果处理器不具有和外围设备并行工作的能力，那么上述计算过程如图所示，不难看出在这个计算过程中，处理器的利用率为：
52 /（78 十 52 十 20）≈ 35%

image.png

而多道程序设计的处理器利用率为：
（52+42）/ 150 ≈ 63％

1.2、多道程序设计的实现

实现多道程序设计要解决三个问题：存储保护和程序浮动；处理器的管理与调度；系统资源的管理与调度

1. 存储保护和程序浮动
   在多道程序设计的环境中，主存储器为几道程序所共享，因此，硬件必须提供必要的手段，使得在主存储器中的各道程序只能访问它自己的区域，以避免相互干扰。特别是当一道程序发生错误时，不致影响其它的程序，这就是存储保护。
   同时，由于每道程序不是独占全机，这样，不能事先规定它运行时将放在哪个区域，所以，程序员在编制程序时无法知道程序在主存储器的确切地址。甚至，在运行过程中，一个程序也可能改变其运行区域，所有这些，都要求一个程序或某一部分能
   随机地从某个主存储器区域移动到另一个区域，而不影响其执行，这就是程序浮动。

2. 处理器的管理与调度
   在多道程序设计系统里，如果仅配置一个处理器，那么多个程序必须轮流占用处理器。
   将程序执行状态分为三种：运行态、等待态、就绪态

   • 运行态 当程序处于运行状态时
   • 等待态 当程序因等待某个事件的发生时
   • 就绪态 当程序满足可以运行，但是为占有处理器时

   例如程序甲处于等待外围设备 D 传输完毕的等待状态，当 D 传输结束时，程序甲就从等待态转为就绪态。从运行态也能转变为就绪态。例如，当程序乙运行时发生了设备 D 传输结束事件，而 D 的传输结束，使得程序甲从等待态转变为就绪态；假定程序甲的优先级高于程序乙，因此让程序甲占有处理器运行，这样，程序乙就从运行态转为就绪态。

3. 资源的管理与调度
   在多道程序设计系统里，系统的资源为几道程序所共享，例如处理器。它要按照一定的策略去分配和调度；

2、顺序性与并发性

2.1、程序执行的顺序性

顺序性是指在每个程序在顺序处理器上的执行是严格按序的，即只有当一个操作系统结束后，才能开始后继操作

顺序程序设计特点：

• 执行的顺序性，一个程序在顺序处理器上的执行是严格按序的，即每个操作必须在下一个操作开始之前结束。
• 程序环境的封闭性，即在顺序处理情况下，运行程序独占系统的全部资源。
• 程序执行结果的确认性，一个程序针对同一个数据集合一次执行的结果，在下一次执行时会重现。
• 顺序程序设计，导致计算机的系统效率不高，但是给程序的编制和调试带来很大方便；

2.2、程序执行的并发性

程序的并发性是指一组程序在执行时间上时重叠的。所谓执行在时间上是重叠的，是指执行一个程序的第一条指令是在执行另一个程序的最后一条指令完成之前开始。

例如：有两个程序 A 和 B，它们分别执行操作 a1，a2，a3 和 b1。b2，b3。在一个单处理器上，就 A 和 B 两个程序而言，它们的执行顺序分别为 al，a2，a3 和 bl，b2，b3，这是程序执行的顺序性。然而，这两个程序在单处理器上可能是交叉执行，如执行序列为 al，bl，a2，b2，a3，b3 或 a1，bl，a2，b2，b3，a3 等，则说 A 和 B 两个程序的执行是并发的。

采用并发程序的特点为：

• 并行性，它们的执行在时间上可以重迭，在单处理器系统中可以并发执行；在多处理器环境中可以并行执行。
• 共享性，它们可以共享某些变量，通过共享这些共享变量或其他通信机制可以互相交换信息，从而程序的运行环境不再是封闭的。
• 交往性，正因为它们具有共享性，所以一个程序的执行可能影响其它程序的执行结果，因此，这种交往必须是有控制的，否则会出现不正确的结果。即使在正确运行的前提下，程序结果也将可能是不确定的，计算过程具有不可再现性。
• 并发程序设计，其主要目的为：提高计算机的系统运行效率，有效利用资源；

3、进程的基本概念

3.1、进程的定义与性质

进程是操作系统，最基本和最重要的概念。从理论角度看，它是对正在运行的程序的抽象，从实现的角度来看，则是一种数据结构，目的在于清晰地刻画并和动态系统的内在规律，有效管理和调度进入计算机系统主存储器运行的程序。它是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。

它具有以下特点：

• 结构性，进程包含了数据集合和运行于其上的程序
• 共享性，同一程序同时运行于不同数据集合上时，构成不同的进程，或者说，多个不同的进程可以共享相同的程序
• 动态性，进程是程序在数据集合上的一次执行过程，是动态概念。其具有一定的生命周期，
• 独立性，进程是系统中资源分配和保护的基本单位，也是系统调度的独立单位
• 制约性，并发进程之间存在制约性，进程在进行的关键点上需要相互等待与互通消息，以保证程序执行的可再现行性。
• 并发性，进程可以并发的执行。

3.2、进程的状态和转换

image.png

1. 三态模型
   • 运行态：占有处理器正在运行 ---running
   • 就绪态：处于可运行状态，等待系统分配处理器一边运行 ---ready
   • 等待态：不具备可运行条件，正在等待某事件的完成----blocked
   • 三种状态的转换如下：
     • 运行态--->就绪态：运行时间到或者出现更高优先权进程
     • 就绪态--->运行态：CPU空闲时，选择一个就绪进程
     • 运行态--->等待态：出现一个等待事件，或者等待使用资源、等待使用外设传输
     • 等待态--->就绪态：等待事件结束；
2. 五态模型
   在三态的基础上，重新引入了专门的新建态 new 和终止态 exit.
   • 新建态，对应进程刚被创建的状态。创建一个进程需要通过两个步骤，首先为一个新进程创建必要的管理信息，然后该进 程进入就绪态。
   • 终止态，首先等待操作系统进行善后，然后退出主存，
   • 各个状态的转换补充:
     • NULL---> new : 执行一个程序，创建一个子进程
     • 新建态---> 就绪态：操作系统完成了进程创建的必要操作，并且当前系统的性能和虚拟存储的容量均就绪
     • 运行态----> 终止态： 当一个进程到达了自然结束点，或者出现了当前无法克服的错误，或者被操作系统所终结。
     • 终止态---->NULL:完成善后工作，退出主存
     • 就绪态--->终止态： 未在状态转换图中显示，但是某些操作系统允许父进程终结子进程
     • 等待态--->终止态：未在状态转换图中显示，但是某些操作系统允许父进程终结子进程

3. 进程的挂起

所有的进程都存在内存之中，事实上，可能存在由于进程的不断创建，系统的资源已不能满足进程运行的要求，此时，必须把这些进程挂起 suspend，对换到磁盘镜像区中，暂时不参与进程的调度。

挂起的原因主要有：

• 操作系统的进程均处于等待状态，处理器空闲，此时把一些进程兑换出去，以留出足够的内存装入就绪进程运行
• 进程资源竞争，导致内存资源不足
• 把一些定期执行的进程对换出去，以减轻系统负荷
• 用户要求挂起自己的进程，已根据执行情况和中间结果进行某些调试、检查和改正
• 父进程要求挂起自己的后代进程

• 当系统出现故障时，需要挂起某些进程以排除故障

  
  image.png

3.3、进程的描述

1. 操作系统的控制结构

   首先介绍一下操作系统的控制结构。为了有限的管理进程和资源，操作系统必须掌握每一个进程和资源的当前状态。

   操作系统的控制，采用一组表来管理和维护进程和每一类资源的信息：

   • 存储控制表：
     用来管理一级和二级存储器，主要内容为：主存储器分分配信息，二次存储器的分配信息，存储保护和分区共享信息，虚拟存储器管理信息
   • I/O控制表：
     用来管理计算机系统的I/O设备和通道
   • 文件控制表：用来管理文件，比如：被打开文件的信息，文件在存储器的位置信息
   • 进程控制表：用来管理进程及其相关信息

2. 进程映像
   当一个程序进入计算机的主存储器进行计算，就构成了进程，其组成主要时一个进程映射：

   • 进程程序块：被执行的程序，规定了进程一次运行应完成的功能，通常是纯代码，作为一种资源被多个进程共享
   • 进程数据块： 程序运行时加工处理对象，包括全局变量、局部变量和长良等存放区以及开辟的工作区，常常为一个进程专用
   • 系统/用户堆栈： 每一个进程都捆绑一个系统/用户堆栈，用来解决过程调用或系统调用时的地址存储和参数传递
   • 进程控制块：每一个进程都将捆绑一个进程控制块，用来存储进程的标志信息、状态信息和控制信息，进程创建时，建立一个PCB，撤销时，回收PCB，它与进程一一对应
     即，每个进程都有四元素组成：控制块、数据块、程序块、堆栈。

3. 进程控制块：
   每一个进程都有一个且只有一个控制块，即PCB。
   它包含三类信息：

   • 标识信息：用于唯一的标识一个进程，常常分由用户使用的外部标识符和被系统使用的内部标识号。比如：用户进程名...
   • 现场信息：用于保留一个进程运行时存放在处理器现场中的各种信息，任何一个进程在让出处理器之前（退出运行状态）都把此时的处理器现场，保存到控制块中，以便重新恢复运行时，恢复处理器现场。比如：用户堆栈指针
   • 控制信息：用于管理和调度一个进程，常用的控制信息包括：
     1. 进程的调度相关信息，比如等待时间、原因、优先级等
     2. 进程通信的相关信息，如消息队列指针、信号量
     3. 进程在二级存储内的地址
     4. 资源的占用和使用信息
     5. 进程特权信息
     6. 资源清单

   进程控制块，是操作系统最为重要的数据结构，每一个进程控制块包含了操作系统管理所需的所有进程信息，进程控制块的集合事实上定义了一个操作系统的当前状态。进程控制块使用或修改权仅属于操作系统程序，包括调度程序、资源分配程序、中断处理程序、性能监视和分析程序等。有了进程控制块进程才能被调度执行，因而，进程控制块可以看作是一个虚的CPU

4. 进程队列 ：

   一般来说，处于同一进程状态的所有进程控制块都是连在一起的，比如就绪态队列。这样的数据结构被称为进程队列，对 于等待态，可以按照等待原因细分，然后进入相应的队列
   在一个队列中，连接进程控制块的方法可以是多样的，常见的是单向连接和多项连接。类似于单链表和双向链表

image.png

当发生的某个事件使一个进程的状态发生变化时，这个进程就要退出所在的某个队列而排入到另一个队列中去。一个进程从一个所在的队列中退出的工作称为出队，相反，一个进程排入到一个指定的队列中的工作称为入队。处理器调度中负责入队和出队工作的功能模块称为队列管理模块，简称队列管理。下图为 操作系统的队列管理和状态转换示意图。

image.png

3.4、进程的控制

通常操作系统提供若干基本操作以管理和控制进程，称之为进程控制原语

常见进程控制原语有：

• 建立进程原语
• 撤销进程原语
• 阻塞进程原语
• 唤醒进程原语
• 挂起进程原语
• 解除挂起进程原语
• 改变优先数原语
• 调度进程原语

1、进程的创建：

进程都有自己的生命周期，即从创建到消亡，当操作系统为一个程序构造一个进程控制块（PCB）并分配地址空间之后，就创建了一个进程，（加入到就绪队列）

它的来源只要为：

• 提交一个批处理作业
• 在终端上交互式的登录
• 操作系统创建一个服务进程
• 存在的进程孵化新的进程

2、进程的切换

中断是激活操作系统的唯一方法，它暂时中止当前进程，把处理器切换到操作系统的控制之下，操作系统再实现进程的切换

进程切换的步骤：

• 保存被中断进程的处理器现场信息。
• 修改被中断进程的进程控制块的有关信息，如进程状态等。
• 把被中断进程的进程控制块加入有关队列。
• 选择下一个占有处理器运行的进程。
• 修改被选中进程的进程控制块的有关信息。
• 根据被选中进程设置操作系统用到的地址转换和存储保护信息。
• 根据被选中进程恢复处理器现场。

3、进程的阻塞和唤醒

当一个等待事件结束之后，就会产生一个中断，从而激活操作系统，在操作系统的控制下将被阻塞的进程唤醒。

进程唤醒的步骤如下：

• 从对应的等待进程队列中，取出进程控制块
• 修改进程控制块的有关信息
• 把修改后的进程控制块加入到就绪进程队列中

4、进程的撤销

一个进程完成了特定的工作或出现了严重的异常后，操作系统收回器占用的地址空间和进程控制块

3.5、进程管理的实现模型

进程管理是不是一个进程呢？不同的操作系统有着不同的处理方法

1. 非进程内核模型

顾名思义：其进程管理不是一个进程；
它包括一个较大的操作系统内核程序，进程的执行
在内核之外。当中断发生时，当前运行进程的现场信息将被保存，并把控制权传递给操作系统内核。操作系统具有自己的内区和系统堆栈区，它将执行相应的操作，并根据中断的类型和具体的情况，或者是恢复被中断进程的现场并让它继续执行，或是
转向进程调度指派另一个就绪进程运行。

image.png

2. 用户进程模型

在用户进程模型中，大部分操作系统程序组织成一组例行程序供用户程序调用其功能，并在用户进程的上下文环境中执行。
Unix 、Windows,采用此种方法实现

3、基于进程的实现模型

基于进程的实现模型把操作系统程序组织成一组进程。如图所示，主要的操作系统内核功能被组织在一组分离的进程内实现，这组进程在内核模式下运行，而进程切换例行程序的执行仍然在进程之外。

image.png