第3章 进程线性模型
单选题6题 多选题2题
3.1 多道程序设计模型
程序的顺序执行
- 程序：在时间上按严格次序前后相继的操作序列，操作是机器指令或高级语言编写的语句
- 传统的——顺序程序设计——CPU一次执行一条指令，对内存一次访问一个字节或字，对外部设备一次传送一个数据块
- 程序的顺序执行：一个具有独立功能的程序独占CPU直到得到最终结果的过程
- 程序的顺序执行具有如下特点：
- 顺序性——严格地按顺序执行
- 封闭性——结果只取决于程序自身，最终结果由初始条件决定，不受外界因素地影响
- 确定性——结果与执行速度无关，也称为程序执行结果与时间无关性
- 可再现性——只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果
多道程序系统中程序执行环境的变化
多道程序设计技术的引入——提高系统资源的利用率 + 缩短作业的周转时间
采用到多程序技术，使多种硬件资源能并行工作
- 系统中的软、硬件资源不再是单个程序独占，而由几道程序所共享
- 工作方式不再是单独串行的，而是多道程序并发执行的
- 单CPU系统：并发程序按时间片交替地在处理机上执行，其执行地时间是重叠的
- 多CPU的系统：并发程序在各自处理机上运行
(1) 多道程序设计技术的引入
结论：采用多道程序设计技术能大大改进系统性能
(2) 多道程序设计环境的特点
- 多道程序设计
- 定义：允许多个程序同时进入内存并运行
- 目的：提高整个系统的效率
- 系统的资源利用率高，则单位时间内所完成的有效工作多，吞吐量大
- 在实现多道程序设计时，必须协调好资源使用者与被使用资源之间的关系
- 多道程序设计的特点
- 独立性——每道程序都是逻辑上独立的，且执行速度与其他程序无关， 执行的起止时间也是独立的。
- 随机性——程序和数据的输入与执行开始时间都是随机的。
- 资源共享性——多道程序共享CPU、I/O设备、内存等资源；资源共享将导致对进程执行速度的制约。
程序的并发执行
- 程序并发执行：是指两个或两个以上程序在系统中，同处于已开始执行且尚未结束的状态。
- 并发程序：是指能够参与并发执行的程序。
- 并发程序在执行期间具有相互制约关系
- 资源共享和竞争制约了各道程序的执行速度，形成了“执行一暂停一执行”的活动规律
- 程序与计算不再一一对应
- 允许多个作业共同使用一个共享程序段，这种调用形成了多个“计算”
- 并发程序执行结果不可再现
- 执行结果与其执行的相对速度有关，且关系不确定
3.2 进程及其状态
进程的概念
- 进程：是具有一定独立功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源分配和调度的一个独立单位。
- 进程的类别
- 系统进程——执行操作系统程序，完成操作系统的某些功能
- 用户进程——运行用户程序，直接为用户服务
(1) 进程与程序的联系和区别
- 联系：
- 程序是构成进程的组成部分之一，进程的运行目标是执行它所对应的程序
- 从静态的角度看，进程是由程序（指令代码）、数据和进程控制块(PCB)正部分组成。
- 区别：
- 程序是静态的，而进程是动态的。
- 进程是程序的执行过程，有生命周期的，有诞生亦有消亡。
- 程序的存在是永久的，而进程的存在是暂时的，动态地产生和消亡。
- 一个进程可以执行一个或几个程序 ，一个程序亦可以构成多个进程。
- 进程具有创建其他进程的功能。被创建的进程称为子进程，创建者称为父进程，从而构成进程家族。
(2) 进程的特性
操作系统的并发性和共享性正是通过进程的活动体现出来的。进程具有以下特性：
- 并发性——可以同其他进程一道向前推进
- 动态性——进程对应着程序的执行过程，动态产生和消亡，且状态动态变化
- 独立性——一个进程是一个相对完整的资源分配单位
- 交互性——一个进程在运行过程中可能会与其他进程发生直接的或间接的相互作用
- 异步性——每个进程按照各自独立的，不可预知的速度向前推进
进程的状态机及其状态转换
(1) 三状态进程模型
运行状态(Running)
- 是指进程已获得CPU，并且在CPU上执行的状态
- 在一个单CPU系统中，最多只有一个进程处于运行态
就绪状态(Ready)
- 指进程已具备除CPU以外的运行条件的状态。
- 处于就绪状态的进程可以是多个。
等待状态(Waiting)
- 也称阻塞状态或封锁状态。
- 指进程因等待某种事件发生而暂时不能运行的状态。
- 系统中处于等待状态的进程可以有多个。
状态切换
模型
特点
- 转换由操作系统完成
- 对用户是透明的
- 体现了进程的动态性
(2) 五状态进程模型
运行状态(Runing)：进程占用处理机资源
就绪状态(Ready)：进程已获得除处理机外的所需资源，等待分配处理机资源;
阻塞状态(Blocked)：由于进程等待I/O操作或进程同步等条件而暂停运行时处于阻塞状态。
创建状态(New)：进程正在创建过程中，还不能运行。
结束状态(Exit)：进程已结束运行，回收除进程控制块之外的其他资源,并让其他进程从进程控制块中收集有关信息
状态转换
模型
进程的主要状态交替循环有两个
- 由调度与超时这两个转换构成
- 由调度、等待时间和事件出现这3个转换构成
过程
创建进程 -> 提交 -> 调度运行 -> 释放 -> 超时 -> 事件等待 -> 事件出现
(3) 七状态进程转换
七状态的引入：五状态进程模型没有区分进程地址空间位于内存还是外存，而在操作系统中引入虚拟存储管理技术后，需要进一步区分进程的地址空间状态，从而引入了挂起和激活操作。
这种做法可得到下列的好处：
- 提高处理机效率
- 可为运行进程提供足够内存
- 有利于调试。
模型
- 就绪挂起状态：进程在外存，只要进入内存即可运行
- 阻塞挂起状态：进程在外存并等待某事件的发生。
挂起（把一个进程从内存转到外存）
- 阻塞到阻塞挂起——没有进程处于就绪状态或就绪进程要求更多内存资源
- 就绪到就绪挂起——有高优先级阻塞（系统认为会很快就绪的）进程和低优先级就绪进程
- 运行到就绪挂起——对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起
激活（把一个进程从外存转到内存）
- 就绪挂起到就绪——就绪挂起进程优先级高于就绪进程或没有就绪进程
- 阻塞挂起到阻塞——当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起进程激活，系统认为会很快出现该进程所等待的事件
事件出现（进程等待的事件出现）
- 阻塞到就绪——针对内存进程的事件出现
- 阻塞挂起到就绪挂起——针对外存进程的事件出现
提交——完成一个新进程的创建过程，新进程进入就绪状态或就绪桂起状态——系统希望保持一个大的就绪进程表（挂起和非挂起）
3.3 PCB和进程控制
进程控制块
- 进程控制块(PCB)：为进程定义了一个专门的数据结构，来描述进程的基本情况以及进程的运行变化过程，是进程存在的唯一标志。
- 当系统创建一个进程时，为进程设置一个PCB，再利用PCB对进程进行控制和管理。
- 撤销进程时，系统收回它的PCB，进程也随之消亡。
(1) PCB的内容
- 调度信息
- 供进程调度时使用，描述了进程当前所处的状况
- 包括进程名、进程号、存储信息、优先级、当前状态、资源清单、“家族”关系、消息队列指针等
- 现场信息
- 刻画了进程的运行情况
- 只记录那些可能会被其他进程改变的寄存器，如程序状态字、时钟、界地址寄存器等。
- 一旦中断进程的运行，须把中断时刻的内容记入PCB的现场信息。
(2) 进程的组成
- 指令——指令和数据是进程的“躯体”，该段代码是可再人程序，且与数据分离。
- 数据——同上
- 进程控制块——进程的“灵魂”保存有进程的地址信息
(3) PCB的组织
- 线性方式：将所有的PCB不分状态组织在一个连续表（称PCB表）中
- 优点：简单，且不需要额外的开销，适用于进程数目不多的系统
- 缺点：需要扫描整个PCB表。
- 索引方式：对于具有相同状态的进程，分别设置PCB索引表，构成了就绪索引表和等待索引表，表目为PCB在PCB表（线性表）中的地址。
- 内存中设置3个指针，分别指示就绪索引表、等待索引表的起始地址以及执行态进程的PCB在PCB表中的地址。
- 链接方式：相同状态进程的PCB，通过PCB中的链接字构成队列。
- 链接字指出本队列下一PCB在PCB表中的编号(或地址)，编号为0表示队尾。
- 队首由内存中的队列指针指示,形成就绪队列和等待队列。
- 就绪队列的排队原则与调度算法有关，可以按优先级排序，也可以按“先进先出”原则出队等。
(4) 进程的队列
- 就绪队列——就绪状态的进程按照某种原则排列在该队列中，入队和出队与调度算法有关，可能有多个。
- 等待队列——一个等待事件一个队列。当进程等待某事件时，进人与该事件相应的等待队列。事件发生时,与该事件相关的一个或多个进程离开相应的等待队列
- 运行队列——单CPU系统中整个系统有一个运行队列。 实际上，一个运行队列中只有一个进程，可用一个指针指向该进程。
进程控制
- 进程控制的作用：对进程在整个生命周期中各种状态之间的转换进行有效的控制。
- 进程控制是通过原语来实现的。
- 由若干条指令所组成，用来实现某个特定的操作
- 通过一段不可分割的或不可中断的程序实现其功能
- 执行必须是连续的，一旦开始执行就不能间断直到执行结束
- 必须在管态下执行，并且常驻内存
(1) 进程控制原语
- 创建进程
- 创建进程：用创建原语创建新进程，前者称为父进程，后者称为子进程
- 主要任务：建立进程控制块PCB。
- 操作过程：先申请空闲PCB区域，填入有关信息，设置就绪状态，最后把它插入就绪队列中
- 撤销进程
- 撤销进程：释放进程所占用的资源
- 实质：撤销PCB
- 操作过程：找到要被撤销进程的PCB，将它从所在队列中消去
- 阻塞原语
- 进程执行过程中，需要执行I/O操作，调用阻塞原语把进程从运行状态转换为阻塞状态。
- 操作过程：中断CPU执行，把CPU的当前状态保存在PCB的现场信息中，设置进程状态为等待状态，并插入到该事件的等待队列
- 唤醒原语
- 进程因等待事件而处于等待状态，当事件完成后，用唤醒原语将其转换为就绪状态
- 操作过程：在等待队列中找到该进程，置进程的当前状态为就绪状态，然后将它从等待队列中撤出并插入到就绪队列中，等待调度执行
(2) UNIX类操作系统的进程控制操作
- 在UNIX类操作系统中，父进程通过调用fork()函数创建子进程：
- 为子进程分配一个空闲的proc结构（进程描述符）
- 赋予子进程唯一标识pid
- 以一次一页的方式复制父进程用户地址空间
- 获得子进程继承的共享资源的指针，如打开的文件和当前工作目录等
- 子进程就绪，加入调度队列
- 对子进程返回标识符0；向父进程返回子进程的pid
- 说明
- 新创建的子进程基本与父进程相同：子进程得到与父进程用户地址空间相同的一份拷贝，包括文本、数据和bss段、堆以及用户栈;
- 子进程还获得与父进程的打开文件描述符相同的拷贝，当父进程调用fork())函数时，子进程可以读写父进程中打开的任何文件。
- 父进程和新建子进程的区别在于它们有不同的pid。
- fork()函数特点
- 一次调用，两次返回
- 父进程中，fork()返回子进程的pid；子进程中，fork()返回0
- 子进程需要运行不同于父进程的程序代码，需调用exec()函数来替换父进程的代码
3.4 线程的引入
线程的引入
- 引入进程的目的为了使多个程序并发执行，以改善资源利用率及提高系统效率,在操作系统中再引入线程，则是为了减少程序并发执行时所付出的时间和空间开销，使操作系统具有更好的并发性。
- 进程具有两个基本属性，构成了进程并发执行的基础
- 是一个可拥有资源的独立单位
- 又是一个可以独立调度和分配的基本单位
基本概念
- 概念
- CPU调度和分配的基本单位
- 自己不拥有系统资源，只拥有一点在运行中必不可少的资源
- 可与同属一个进程的其他线程共享进程所拥有的全部资源
- 线程可以创建和撤销另一个线程，多个线程之间可以并发执行
- 有就绪、等待和运行三种基本状态
- 属性
- 每个线程有一个唯一的标识符和一张线程描述表
- 不同的线程可以执行相同的程序
- 同一进程中的各个线程共享该进程的内存地址空间
- 线程是处理器的独立调度单位，多个线程是可以并发执行的
- 一个线程被创建后便开始了它的生命周期
- 引入线程的好处
- 创建和撤销一个新线程花费时间少
- 线程的切换花费时间少
- 无需额外的通信机制，信息传送速度更快
- 线程独立执行，能充分利用和发挥处理器与外围设备并行能力
- 进程与线程的对比
- 传统——进程拥有资源的基本单位和独立调度、分派的基本单位
- 引入线程
- 线程作为调度和分派的基本单位
- 进程作为资源拥有的基本单位
- 区别
- 在同一进程中，线程的切换不会引起进程切换
- 一个进程中的线程切换到另一 进程中的线程时，将会引起进程切换
- 并发性
- 进程之间可以并发执行
- 在一个进程中的多个线程之间也可以并发执行
- 拥有资源
- 不论是传统还是引入线程的OS，进程都是拥有资源的一个独立单位，可以拥有自己的资源
- 线程不拥有系统资源（也有一-点必不可少的资源），但可以访问其隶属进程的资源。
- 进程中的资源可供同一进程的其他所有线程共享。
- 系统开销
- 进程切换——涉及整个当前进程CPU环境的保存以及新被调度运行的进程的CPU环境的设置
- 线程切换——只需保存和设置少量寄存器的内容，并不涉及存储器管理方面的操作
- 概念
线程的实现机制
(1) 用户级线程——只存在于用户态中，不依赖于内核（典型OS为Linux）
概念
- 在一个运行时系统的顶部运行,进程需要有其专用的线程表，用来跟踪该进程中的线程。
- 当一个线程转换到就绪状态或阻塞状态时,在该线程表中存放重新启动该线程所需的信息。
- 用户线程切换过程：当某个线程引起阻塞后,该线程所属进程将调用一个运行时系统的过程，检查该线程是否必须进入阻塞状态。
- 在线程完成运行时，运行时系统可以把该线程的信息保存在线程表中，调用线程调度程序来选择另一个要运行的线程。
优点
- 可在不支持线程的操作系统上实现
- 可用函数库实现线程
- 用户线程的切换只需检查所需进程中的线程表
- 允许每个进程有自己定制的调度算法
(2) 内核级线程——依赖于内核，创建、撤销和切换都由内核实现
- 内核中保留了一个线程控制块，系统根据该控制块而感知该线程的存在并对线程进行控制
- 线程表设置在内核中，保存了每个线程的寄存器、状态和其他信息。
- 所有能够阻塞线程的调用都以系统调用的形式实现。
(3) 混合实现方式——同时实现了用户级线程和内核级线程
Pthread线程包
Pthread是基于IEEE标准1003.1c定义实现的线程包，大部分UNIX系统都支持该标准。
线程调用 返回值类型 返回值含义 描述 pthread_create int 新线程id 创建一个新线程 pthread_exit void 无 结束调用的线程 pthread_join int 0:成功；非0:错误号 等待一个特定的线程退出 pthread_yield 释放CPU来运行另外一个线程 pthread_attr_init int 0:tid；非0:错误号 创建并初始化一个线程的属性结构 pthread_attr_destroy int 0:成功；非0:错误号 删除一个线程的属性结构
3.5 进程（线程）调度
调度的分类
- 高级调度——也称作业调度，其主要任务是按一定的原则，选择磁盘中处于后备状态的作业，调入内存并为其创建进程
- 中级调度——主要任务是按照给定的原则和策略，将处于磁盘对换区中且具备运行条件的就绪进程调入内存，或将处于内存中的处于就绪状态或阻塞状态的进程交换到对换区
- 低级调度——即进程（线程）调度，是决定就绪队列中哪个进程将获得处理机，并实际将处理机分配给该进程的操作。
进程调度的概述
(1) 主要功能
- 记录系统中所有进程（线程）的执行状况
- 根据一定的调度算法，从就绪队列中选出一个进程（线程），准备把CPU分配给它
- 把CPU分配给进程（线程）， 即把选中进程（线程）的PCB内有关的现场信息，如程序状态字、通用奇存器等内容送入处理器相应的奇存器中，从而让它占用CPU运行。
(2) 调度时机
- 正在执行的进程（线程）运行完毕
- 时间片用完
- 正在执行的进程（线程）调用阻塞原语将自己阻塞起来进入等待状态
- 正在执行的进程（线程）因为资源不足而被阻塞；或调用了唤醒原语操作激活了等待资源的进程（线程）
- 就绪队列中，某个进程（线程）的优先级高于当前运行进程（线程），引发进程（线程）调度。
调度算法设计原则
(1) 设计目标
- 资源利用率——为提高资源的利用率，应使CPU和所有其他资源尽量保持忙碌。
- 公平性——相似的进程应得到相似的服务，不同类型的进程可采用不同方式处理。
- 平衡性——用户对一件事情需要多长时间有固有的看法，调度算法应该尽可能保持系统的资源使用的平衡性。
- 策略强制执行——对制定的策略尤其是安全策略，只要需要，就必须转却执行。
(2) 系统分类
- 批处理
- 吞吐量——系统每小时可完成多少作业
- 周转时间——完成作业需要多长时间
- CPU利用率——知道什么时候CPU利用率接近100%
- 交互式系统
- 分时系统——有不同的指标
- 服务器——有不同的指标
- 最小响应时间——从发出命令到得到响应之间的时间
- 实时系统
- 特点——满足所有的（或大多数）截止时间要求
- 进程调度程序必须是最高度可预测的和有规律的
调度算法
- 非抢占式的先来先服务(FCFS)
- 最简单的非抢占式算法
- 方式——按照请求CPU的顺序使用CPU
- 主要优点——易于理解并且便于在程序中运行
- 缺点——没有考虑进程的实际需要
- 非抢占式的最短作业优先(SJF)
- 周转时间 = 等待时间 + 运行时间
- 易产生饥饿现象
- 适用于可以预知运行时间的非抢占式批处理调度算法
- 思想：估计运行时间最短的作业，将处理机分配给它，使它立即执行
- 只有在所有的作业都同时可运行的情形下，最短作业优先算法才是最优化的
- 抢占式的最短剩余时间优先(SRTF)
- 最短作业优先的抢占式版本是最短剩余时间优先算法
- 思想：在了解运行时间提前下，调度程序总是选择其剩余运行时间最短的进程运行
- 当前进程的剩余时间与一个新的作业比较时间
- 若新的作业时间长，则继续运行当前进程
- 若当前进程时间长，则当前进程被挂起，运行新进程
- 最高响应比优先算法(HRRF)
- 思想：在每次调度时选择响应比最高的作业投入运行
- 响应比 Rp = (等待时间 + 预计运行时间) / 预计运行时间 = 响应时间 / 预计运行时间
- 优点：在一定程度上改善了调度的公平性和调度的效率
- 缺点：需要消耗系统的资源，存在一定的系统开销
- 时间片轮转法(RR)
- 思想：最早来自分时系统，将CPU的处理时间划分成一个个时间片，就绪队列中的诸进程轮流运行一个时间片。
- 设计时间片值（响应时间T、时间片长度Q）
- 系统响应时间T——当进程数目一定时，Q正比于T，即Q = T / N
- 就绪进程的数目——当T一定时，Q反比于就绪进程数
- 计算机的处理能力——处理速度越高，Q就可以越小
- 最高优先级算法(HPF)
- 可分为可抢占式和不可抢占式的最高优先级算法
- 思想：每次将处理机分配给具有最高优先级的就绪进程（线程）【优先级由进程（线程）优先级决定】
- 静态优先级
- 在进程（线程）创建时根据进程(线程)初始特性或用户要求而确定的
- 在进程（线程）运行期间不能再改变
- 动态优先级
- 在进程（线程）创建时先确定一个初始优先数
- 在进程（线程）运行中随着进程（线程）特性的改变（如等待时间增长），不断修改优先数
- 多级反馈队列算法
- 是综合了先进先出调度算法、时间片轮转算法和可抢占式最高优先级算法的一种进程（线程）调度算法。
- 基本思想
- 被调度队列的设置——按优先级设置若干就绪队列；不同优先级队列有不同的时间片，优先级高的队列分配较小的时间片
- 同一队列内的调度原则——除了最后一集队列按RR调度外，其他各级均按FCFS调度
- 不同队列间的调度原则——总是先调度优先级较高的队列，仅当高级别的队列为空时才去调度次一级队列中的进程（线程）
- 优先级调度原则——当正在执行的进程（线程）用完其时间片后，便被换出进入次一级的就绪队列。当等待进程（线程）被唤醒时,则进入与其优先级相同队列;若其优先级高于正在执行的进程（线程），便抢占CPU。
- 最短进程优先
- 如何从当前可运行进程中找出最短的那个进程？
- 方法：老化算法，即根据进程过去的行为进行推测，估计运行时间那个进程最短
- 某终端上每条命令的估计运行时间为T0，假设测量到其下一次运行时间为T1，可用加权和来改进估计时间，即aT0 + (1-a)T1
- 在三轮过后，T0在新的估计值中所占的比重下降到1/8
- 实时系统中的调度算法
- 实时任务
- 硬实时任务——必须满足最后期限的限制，否则会给系统带来不可接受的破坏或者致命的错误。
- 软实时任务——有最后期限，并希望能满足期限要求，但并非强制即使超过，完成这个任务仍有意义。
- 实时任务可以按照响应方式划分为：周期性（以规则的时间间隔发生）事件或非周期性（发生时间不可预知）事件。
- 可调度实时系统，需满足如下条件：设有m个周期事件，事件i以周期Pi发生，并需要Ci秒CPU时间处理一个事件，那么可以处理负载的条件：1到m求和(Ci / Pi) <= 1
- 实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策；后者在运行过程中进行调度决策。
- 实时任务
- 非抢占式的先来先服务(FCFS)
预览: