2020-计算机操作系统-Lecture2-处理器管理

Lecture2-处理器管理

  1. 处理器管理是操作系统的重要组成部分
    1. 处理器负责管理、调度和分配计算机系统的重要资源，并控制程序执行
    2. 处理器管理中最重要的是处理器调度，即进程调度，也就是控制、协调进程对处理器的竞争。
  2. 进程与线程
    1. 进程是资源分配和管理的单位
    2. 线程是处理器调度的基本单位。
  3. 管态与目态
    1. 管态又叫特权态(内核态、核心态)，可以执行特权指令，执行资源管理程序、为应用程序执行提供良好运行环境的各种原语等。
    2. 目态又叫用户态(普通态)，只能执行非特权指令

1. 处理器和寄存器

1.1. 处理器

部件简单示意图

  1. 上图各组件通过内部总线连接起来，构成一个不包含通用寄存器、I/O相关寄存器、地址寄存器、数据寄存器和Cache的示意图。
  2. CPU中的各组件描述
    1. 算数逻辑单元：计算结束之后会将结果的标志放置到标志寄存器Flag中。
    2. 控制单元：包含重要的指令译码器ID，而指令是放置在指令暂存器IR中。
    3. 程序计数器PC：下一条指令的地址
    4. 内存地址寄存器和内存数据寄存器：用来完成对内存数据的访问。
  3. 通过系统总线来访问内存中的数据，首先设置地址和数据，然后通过控制来完成数据的读取和写回。
  4. 时钟等外部信号来反应到处理器线程中来。

1.2. 寄存器

1.2.1. 用户程序可见寄存器

  1. 可以使程序员减少访问主存储器的次数，提高指令执行的效率
  2. 所有程序可使用，包括应用程序和系统程序
    1. 数据(通用)寄存器:AX、BX、CX、DX等
    2. 地址寄存器:索引(SI、DI)、栈指针(SP、BP)、段地址(CS、DS、SS、ES)、页表寄存器等

1.2.2. 控制和状态寄存器

  1. 控制和状态寄存器用于控制处理器的操作，主要是被具有特权的操作系统程序使用，以控制程序的执行
    1. 程序计数器PC：存储将取指令的地址
    2. 指令寄存器IR：存储最近使用的指令
    3. 条件码CC：CPU为指令操作结果设置的位，标志正/负/零/溢出等结果
  2. 标志位
位 描述
中断位 是否有中断发生了，中断源是什么
中断允许位 表示目前是否响应中断
中断屏蔽位 中断发生了，中断响应了，我们要不要屏蔽中断
处理器模式位 现在处理器是处于何种模式
内存保护位 对这段内存是只读还是读写还是不可操作

1.2.3. 程序状态字PSW

  1. PSW既是操作系统的概念，指记录当前程序运行的动态信息，通常包含：
    1. 程序计数器、指令寄存器、条件码
    2. 中断字、中断允许/禁止、中断屏蔽、处理器模式、内存保护、调试控制
  2. PSW也是计算机系统的寄存器
    1. 通常设置一组控制与状态寄存器
    2. 也可以专设一个PSW寄存器
  3. 标志划分为三组:状态标志、控制标志和系统标志(更多见P58)
    1. 状态标志：使得一条指令的执行结果影响其后指令的执行，比如溢出等标志
    2. 控制指令：控制操作系统行为，比如模式转换等。
    3. 系统标志：与进程管理有关，用于保护模式。

2. 指令与处理器模式

2.1. 机器指令

  1. 机器指令是计算机系统执行的基本命令，是中央处理器执行的基本单位。
  2. 指令由一个或多个字节组成，包括操作码字段、一个或多个操作数地址字段、以及一些表征机器状态的状态字以及特征码。
  3. 指令完成各种算术逻辑运算、数据传输、控制流跳转。

2.2. 指令执行过程

  1. CPU根据PC取出指令，放入IR，并对指令译码，然后发出各种控制命令，执行微操作系列，从而完成一条指令的执行
  2. 一种指令执行步骤如下：(还有更加细分，这只是一种示例)
    1. 取指：根据PC从存储器或高速缓冲存储器中取指令到IR
    2. 解码：解译IR中的指令来决定其执行行为
    3. 执行：连接到CPU部件，执行运算，产生结果并写回，同时在CC里设置运算结论标志；跳转指令操作PC，其他指令递增PC值

2.3. 指令执行周期与指令流水线

现在的操作系统不是顺序地完成指令执行，而是选择使用指令流水线的方式来执行指令

2.4. 特权指令与非特权指令

用户程序并非能够使用全部机器指令，那些与计算机核心资源相关的特殊指令会被保护

  1. 比如：启动I/O指令(启动打印机，打印文件会细分成按照行打印，可能导致逻辑上的失败)、置PC指令(多道程序调用)等等
  2. 核心资源相关的指令只能被操作系统程序使用(作为特权指令，不允许在用户态使用这些命令)

2.4.1. 特权指令

  1. 只有操作系统本身可以使用的指令，在内核态才能调用的命令，不仅仅影响运行程序本身，还会干扰其他程序及操作系统。
  2. 比如改变机器状态、修改寄存器值、置中断屏蔽位、加载程序状态字等。
  3. 如果应用程序执行特权指令则会导致非法执行而产生保护中断，进而转向操作系统的"用户非法执行特权指令"的异常处理程序处理。

2.4.2. 非特权指令

  1. 所有的用户程序都能够使用的指令，在用户态和内核态都可以调用的命令。
  2. 非特权命令在目态和管态的情况下都能工作。

2.5. 处理器模式

  1. 计算机通过设置处理器模式实现特权指令管理
  2. 计算器一般设置0、1、2、3等四种运行模式(保护级别)
    • 0:内核级，操作系统内核，可以执行全部指令，包括中断处理、处理I/O操作等命令
    • 1:系统调用级，执行系统调用，获得特定的和受保护的程序服务
    • 2:共享库级，可以多个运行进程共享，允许调用库函数，读取但不修改相关数据。
    • 3:用户程序，只能执行非特权指令，收到的保护最少
  3. 0模式可以执行全部指令；3模式只能执行非特权指令；其他每种运行模式可以规定执行的指令子集
  4. 一般来说，现代操作系统只使用0和3两种模式，对应于内核模式和用户模式
  5. 处理器模式是由处理器模式位决定的。

2.6. 处理器模式切换

  1. 简称模式切换，包括用户模式->内核模式和内核模式->用户模式的两种切换。
  2. 中断、异常或系统异常等事件导致用户程序向OS内核切换，触发：用户模式->内核模式，以下三种方式是唯一能触发的方式:
    1. 程序请求操作系统服务，执行系统调用
    2. 程序运行时发生异常(如发生程序性中断，或者目态执行特权指令)
    3. 程序运行时发生并响应中断(一般是I/O中断)
  3. 我们可以认为中断和异常是用户态到内核态转换的仅有途径。
  4. OS内核处理完成后，调用中断返回指令(如Intel的iret)触发：内核模式->用户模式，操作系统将控制权转交给应用进程。

2.7. 系统调用示例

3. 栈空间

3.1. 用户栈

  1. 用户栈是用户进程空间中开辟的一块区域，用于保存应用程序的子程序(函数)间相互调用的参数、返回值、返回点以及子程序的局部变量。
  2. 如果只有用户栈，没有核心栈，那么操作系统则很难对核心栈的数据提供相应的保护措施。

3.2. 核心栈

  1. 核心栈也叫系统栈或内核栈，是内存中属于操作系统空间的一块区域，其用途包含以下两种:
    1. 保存中断现场，嵌套中断
    2. 保存操作系统程序(函数)间相互调用的参数、返回值、返回点以及程序局部变量。
  2. 每个进程有一个核心栈:可读可写不可执行，大小有限
  3. 硬件栈指针只有一个

4. 中断

4.1. 中断、异常和系统异常

  1. 广义的中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程
  2. 狭义的中断指来源于处理器之外的中断事件，即与当前运行指令无关的中断事件，如I/O中断(为打印机结束后进行善后)、时钟中断(计算机系统计时，多一段时间就要更新系统时间)、外部信号中断(关机)等
  3. 异常指当前运行指令引起的中断事件，如地址异常(访问其他程序的内存、读写没有权利读写的内存、虚拟地址的异常)、算术异常(数字溢出、对0除法)、处理器硬件故障(奇偶校验位错误)等
  4. 来自于CPU内部的广义中断事件我们称之为异常，和狭义的中断构成了广义的中断。
  5. 系统异常指执行陷入指令而触发系统调用引起的中断事件，如请求设备、请求I/O、创建进程等，与硬件无关(通过系统异常请求服务)，系统异常可以被认为是异常中的一类

4.2. 操作系统与中断

  1. 操作系统是中断驱动的；换言之，中断是激活操作系统的唯一方式。
  2. 操作系统要求计算机硬件系统为其设置相应的中断激活的硬件机制，再配合操作系统的内核程序共同完成中断驱动方式，这个是操作系统实现的最根本的基础，中断处理需要借助硬件电路

4.3. 中断源分类

由硬件发出或产生的中断称为硬中断，按硬中断事件的来源和实现手段可将终端划分为外中断和内中断。

4.3.1. 外中断

  1. 外中断又称中断或异步中断，是指来自处理器之外的中断信号，包括时钟中断、键盘中断、它机中断和外部设备等、
  2. 外中断又可以分为可屏蔽中断和不可屏蔽中断，各个中断具有不同中断优先级。

4.3.2. 内中断

  1. 内中断又称异常或同步中断，是指来自处理器内部的中断信号，通常是由于程序执行过程中，发现与当前指令相关的、不正常或错误的时间，内中断可分为:
    1. 访管中断，由执行系统调用而引起
    2. 硬件故障中断，如电源失效、奇偶校验错误、总线超时等
    3. 程序性异常，如非法操作、地址越界、页面故障、调试指令、除数为0和浮点溢出等。

4.4. 中断和异常区别(P60)

中断 异常
CPU异步 CPU同步
内核态、用户态 大部分在用户态，内核态唯一的异常是"缺页异常"
一般中断处理程序提供的服务不是当前进程需要的 是当前的进程需要的
快速处理，不可以被打断 可以被阻塞
允许嵌套 大多为一重等
不可以被异常打断 可以被中断中断

5. 中断事件处理原则

5.1. 中断源:处理器硬件故障中断事件(硬中断)

  1. 由处理器、内存储器、总线等硬件故障引起，除了极少类的校验错误可以恢复以外，是非常严重的中断。
  2. 处理原则为：保护现场，停止设备，停止CPU，向操作员报告，等待人工干预
  3. 电脑会配置一个小电容保证尽可能较少硬件损伤

5.2. 中断源:程序性中断事件

处理器执行机器指令引起

  1. 语法错误：由编译程序发现
  2. 逻辑错误：由测试程序发现
  3. 程序运行过程中产生异常
    1. 除数为零、操作数溢出等算术异常：简单处理，报告用户；也可以由用户编写中断续元程序处理
    2. 非法指令、用户态使用特权指令、地址越界、非法存取等指令异常：终止进程
    3. 终止进程指令：终止进程
    4. 虚拟地址异常：指令和数据不在内存当中，调整内存后重新执行指令

5.3. 中断源:I/O中断事件

  1. 来源于外围设备报告I/O状态的中断事件
    1. I/O完成：调整进程状态，释放等待进程
    2. I/O出错：先向设备发命令索取状态字，分析产生故障的确切原因，再执行复执或请求人工干预，
    3. I/O异常：等待人工干预，缺纸，人工加纸
    4. 设备报道或设备结束:表示有设备接入可供使用或设备断开暂停使用
  2. 狭义中断事件

5.4. 中断源:自愿性中断事件(访管中断)

  1. 处理器执行陷入指令请求OS服务引起；在操作系统中，它一般又被称作系统调用，比如请求分配外设、请求I/O等等
  2. 处理流程是：
    1. 程序执行访管指令，并通过适当方式指明系统调用号。
    2. 通过中断机制进入访管中断处理程序，现场信息被保护到核心栈，按功能号实现跳转。
    3. 通过系统调用入口地址表找到对应中断服务历程的入口地址
    4. 执行终端服务例程

5.5. 中断源:外部中断事件

  1. 由外围设备发出的信号引起的中断事件
    1. 时钟中断、间隔时钟中断：记时与时间片处理，最常见
    2. 设备报到与结束中断：调整设备表
    3. 键盘/鼠标信号中断：根据信号作出相应反应
    4. 关机/重启动中断：写回文件，停止设备与CPU
  2. 时钟可以分为绝对时钟和间隔时钟
    1. 绝对时钟:固定周期发出中断请求
    2. 间隔时钟:每个时间切换点,将间隔时钟的内容减1，其值为0的时候，产生间隔时钟中断。
  3. 时钟间隔定时器
    1. real:按照实际经过的时间计时
    2. virtual:仅在用户态下执行才计时
    3. profile:进程执行用户态或用户态时都计时，当计时到达发送信号

6. 中断系统

  1. 中断系统是计算机系统中响应和处理中断的系统，包括硬件子系统和软件子系统两部分
    1. 中断响应由硬件子系统完成
    2. 中断处理由软件子系统完成
  2. 中断系统是操作系统的基础，中断系统也是软硬件协同系统的典型例子

6.1. 中断响应处理与指令执行周期

在指令执行周期最后增加一个微操作，以响应中断，CPU在完成执行阶段后，如果允许中断，则进入中断阶段

6.2. 中断装置

  1. 计算机系统中发现并响应中断/异常的硬件装置称为中断装置
  2. 由于中断源的多样性，硬件实现的中断装置有多种，分别处理不同类型的中断
  3. 这些中断装置因计算机而异，通常有：
    1. 处理器外的中断：由中断控制器发现和响应
    2. 处理器内的异常：由指令的控制逻辑和实现线路发现和响应，相应机制称为陷阱
    3. 请求OS服务的系统异常：处理器执行陷入指令时直接触发，相应机制称为系统陷阱

6.3. 中断控制器

  1. 中断控制器：CPU中的一个控制部件，包括中断控制逻辑线路和中断寄存器，中断控制器会记录中断是来自哪里
    1. 狭义中断:(异步过程)外部设备向其发出中断请求IRQ，在中断寄存器中设置已发生的中断
    2. (同步过程)指令处理结束前，会检查中断寄存器，若有不被屏蔽的中断产生，则改变处理器内操作的顺序，引出操作系统中的中断处理程序
  2. 狭义中断是异步进程，CPU正在做的事情和中断可能是两个不同部分

6.4. 陷阱与系统陷阱

陷阱与系统陷阱：指令的逻辑和实现线路的一部分

  1. 执行指令出现异常后，会根据异常情况转向操作系统的异常处理程序
  2. 出现虚拟地址异常后，需要重新执行指令，往往越过陷阱独立设置页面异常处理程序
  3. 执行陷入指令后，越过陷阱处理，触发系统陷阱，激活系统调用处理程序

6.5. 中断程序的处理&中断/异常响应过程

  1. 中断处理程序：操作系统处理中断事件的控制程序, 主要任务是处理中断事件和恢复正常操作。
  2. 是一个软件过程
  3. 中断/异常响应过程
    1. 发现中断源，提出中断请求(选择响应哪一个程序)
      1. 发现中断寄存器中记录的中断
      2. 决定这些中断是否被屏蔽
      3. 当有多个要响应的中断源时，根据规定的优先级选择一个
    2. 中断当前程序的执行(保护现场):保存当前程序的PSW(程序状态字)/PC到核心栈
    3. 转向操作系统的中断处理程序:处理器状态已从用户态转换至内核态。
    4. 恢复现场:恢复原运行程序的PSW，重新返回中断点，以便执行后续指令。

6.6. 恢复正常操作

  1. 情况一：对于某些中断，在处理完毕后，直接返回刚刚被中断的进程，比如计时中断。
  2. 情况二：对于其他一些中断，需要中断当前进程的运行，调整进程队列，启动进程调度，选择下一个执行的进程并恢复其执行，比如请求输入输出。
  3. 无论是哪个都是从内核态到用户态。

6.7. 中断系统处理流程

  1. 硬件设计受到操作系统的要求。
  2. 操作系统:大型软件系统，大型紧密结合软硬件设备的系统。

7. 多中断的响应与处理

7.1. 中断优先级

  1. 当计算机同时检测到多个中断时, 中断装置响应中断的顺序。
  2. 有优先度的响应中断：将紧迫程度相当的中断源归为同一级别，将紧迫程度差距较大的中断源归为不同级别。
  3. 一种可能的处理次序：(对几十个人使用的大型计算机系统很合理)，可以借助软硬件分别来完成实现。
    1. 处理机硬件故障中断事件。
    2. 自愿性中断事件。
    3. 程序性中断事件。
    4. 时钟中断等外部中断事件。
    5. 输入输出中断事件。
    6. 重启动和关机中断事件。
  4. 不同类型的操作系统有不同的中断优先级:PC做出关机操作表示放弃当前的所有的操作，所以重启动和关机中断是优先级最高的中断。

7.2. 中断屏蔽

  1. 当计算机检测到中断时, 中断装置通过中断屏蔽位决定是否响应已发生的中断。
  2. 有选择的响应中断：由计算机决定。
    1. 延迟或禁止某些中断的响应以避免共享数据结构受到破坏。
    2. 协调中断响应与终端处理的关系，保证优先级顺序。
    3. 防止同级中断互相干扰。
  3. 计算机均配置可编程中断控制器。

7.3. 中断的嵌套处理

  1. 当计算机响应中断后，在中断处理过程中，可以再响应其他中断
  2. 操作系统是性能攸关的程序系统，且中断响应处理有硬件要求，考虑系统效率和实现代价问题，中断的嵌套处理应限制在一定层数内，如3层
  3. 中断的嵌套处理改变中断处理次序，先响应的有可能后处理

7.4. 多中断的响应与处理

决定了中断处理次序的因素

  1. 中断屏蔽可以使中断装置不响应某些中断
  2. 中断优先级决定了中断装置响应中断的次序
  3. 中断可以嵌套处理, 但嵌套的层数应有限制
  4. 中断的嵌套处理改变了中断处理的次序

7.5. 多重中断处理

7.5.1. 顺序中断处理(串行处理)

X、Y两个中断同时发生，如下图所以，系统先响应X，屏蔽Y，待X响应完成后，系统再响应并处理Y

7.5.2. 嵌套中断处理(嵌套处理)

X、Y两个中断同时发生，根据中断有限级，先响应中断X，因为没有屏蔽Y，则响应并处理Y，处理Y完成后，再处理X。

7.5.3. 即时处理

  1. 在运行中断处理程序时，如果出现程序性中断事件，在一般情况下，表明此时中断程序有异常，应对其立即响应并处理。

7.6. 中断处理的例子：Linux内核处理流程

  1. 中断信号源:中断向量
    1. 中断，分为所有外部设备产生的屏蔽中断请求，和硬件故障等紧迫时间引发的非屏蔽中断。
    2. 异常:CPU发出的中断信号，主要有故障、陷阱、终止和编程异常等
  2. 更多见P66-71页

8. 进程及其状态

8.1. 进程的提出

  1. 操作系统必须全方位地管理计算机系统中运行的程序。因此，操作系统为正在运行程序建立一个管理实体:进程

8.2. 进程的概念

  1. 进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动。
    1. 具有一定独立功能的程序:进程是相对独立的
    2. 关于某个数据集合:对于不同数据集合的操作不是同一个进程。
    3. 一次运行活动:有生命周期
  2. 进程是操作系统进行资源分配和调度的一个独立单位:这只限于单线程单进程的情况下
    1. 资源分配:除了CPU之外的资源的分配，比如内存和外设等
    2. 单线程情况下，进程的资源分配和调度就是处理器的。
    3. 调度特指处理器的调度
  3. 有的将进程叫做process，Linux以及一些企业中，把进程称为Task。
  4. 进程可以看为可运行程序加载到内存，配合相应的数据集，在操作系统中的一个实例，程序可以多次被加载进入成为进程。

8.3. 进程的属性

  1. 动态性:进程是程序在数据结合上的一次执行过程，是动态概念，同时它有声明周期，而程序是一组有序指令序列，是静态概念，所以程序作为系统中的一种资源是永久存在的。
  2. 共享性:同一程序同时运行于不同数据集合上时都是不同的进程，即不同的进程可以运行相同的程序。
  3. 独立性:每个进程是操作系统中的一个独立实体。有自己的虚存空间、程序计数器和内部状态.
  4. 制约性:进程因共享资源或协同工作产生相互制约关系，造成进程执行速度的不可预测性，必须对进程的执行次序或相对执行速度予以协调。
  5. 并发性:多个进程的执行在时间上可以重叠。

8.4. 进程的组成

一个进程包括五个实体部分，分别是：

  1. (OS管理运行程序的)数据结构P
  2. (运行程序的)内存代码C
  3. (运行程序的)内存数据D
  4. (运行程序的)通用寄存器信息R
  5. (OS控制程序执行的)程序状态字信息PSW

8.5. 单线程结构进程和多线程结构进程

  1. 单线程结构进程:进程级别，负责完成资源分配和CPU调度。
  2. 多线程结构进程:线程级别，负责完成资源分配(进程完成)和CPU调度(代表一个执行流)，并且一个进程中可以包含很多线程。
  3. 操作系统最开始设计的时候并没有设计多线程。

8.6. 进程举例

  1. 以下的程序与数据集都是内存级的。
  2. 不同时段针对同一个外存数据文件运行同一个外存程序文件意味着完全不同的(P, C, D, R, Psw)

8.6.1. 无关进程

不同程序在不同数据集上运行：构成两个无关进程

8.6.2. 共享数据的交往进程

不同程序在相同数据集上运行：构成两个共享数据的交往进程

8.6.3. 共享代码的无关进程

  1. 相同代码在不同数据集上运行：构成两个共享代码的无关进程
  2. 共享的代码称为可再入程序，如编辑器可再入程序是纯代码的，可再入程序必须是纯代码的

8.6.4. 共享代码和数据的进程

可以共享代码或者共享数据

9. 进程状态和转换

9.1. 进程三态模型

  1. 只要操作系统支持多道程序设计，就必须要设计进程转换模型来管理，必须实现三个进程状态和四个跳转关系，进程状态转换一定有内核的参与。
  2. 运行被中断进程时需要找到被中断时的信息并恢复。

9.1.1. 三种状态

  1. 运行态:进程占有处理器正在运行的状态。
  2. 就绪态:进程具备运行条件，等待系统分配处理器以便运行的状态，面向调度的，处理器只会挑选就绪态进程(就绪队列进程)
  3. 等待态:又称阻塞态或睡眠态，指进程不具备运行条件，正在等待某个事件完成的状态，暂时被剥夺处理机会。
  4. 处于运行态个数不能大于处理器个数。
  5. 进程创建后一般是处于就绪态

9.1.2. 四种状态转换

  1. 运行态→\rightarrow等待态：等待资源、I/O、信号量
  2. 等待态→\rightarrow就绪态：资源满足、I/O结束、信号量完成
  3. 运行态→\rightarrow就绪态：运行时间片到(倒计时到，不缺少其他东西，只缺少CPU，退回就绪态)、有更高优先权进程，低级调度问题
  4. 以上四个状态转换，一个不能少，一个也不能多，其他的转换不存在的原因如下：
    1. 没有就绪态到等待态:到等待态需要内核参与。
    2. 没有等待态到运行态:等待的资源还没有就绪，无法进入运行态。

9.1.3. 时间片与进程转换

  1. 时间片用完，计算没有做完，被抢占的进程运行态->就绪态：启动内核的处理器调度算法.
  2. 时间片内，用户进程发生中断或系统调用，运行态->等待态
  3. 时间片内，用户进程完成全部计算完成退出系统，运行态->终止态，激活内核，时间片被撤销。

9.1.4. 进程三态模型总结与扩展

  1. 进程映像定义其数据结构和存储结构
  2. 状态转化模型(队列模型)定义其生命周期和状态转换
  3. 然后围绕以上两部分开发出相应的操作和算法
  4. 进程状态和模型与信号量同样相关，后续深入讨论。

9.2. 进程七态模型(P74)

9.2.1. 新添加的状态

  1. 新建态:对应于进程被创建的状态，尚未进入就绪队列，创建进程的两个步骤
    1. 为新进程分配所需资源和建立必要的管理信息
    2. 设置进程为就绪态，等待被调度执行
  2. 终止态:
    1. 进程完成认为到达正常结束点
    2. 出现无法克服的错误而异常终止
    3. 操作系统及有终止权的进程所终止时所处的状态，处于终止态的进程不再被调度执行
    4. 下一步就将被系统撤销，最终从系统中消失。
  3. 挂起就绪态:表明进程具备运行条件，但目前在外存中，只有它被对换到内存才能调度执行。
  4. 挂起等待态:表明进程正在等待某一个事件发生且在外存中。

9.2.2. 进程挂起的源头

  1. 到目前为止:随着不断创建进程，当系统资源尤其是内存资源已经不能满足进程运行的要求时，必须把某些进程挂起，对换到磁盘对换区中，释放它占有的某些资源，暂时不参与低级调度，起到平滑系统负荷的目的；也可能系统出现故障，需要暂时挂起一些进程，以便故障消除后再接触挂起并恢复进程运行。
  2. 进程挂起的原因是多种多样的。

9.3. 进程挂起

9.3.1. 进程挂起的概念

  1. OS无法预期进程的数目与资源需求，计算机系统在运行过程中可能出现资源不足的情况
  2. 运行资源不足表现为性能低和死锁两种情况。
  3. 解决办法：剥夺某些进程的内存及其他资源，调入OS管理的对换区，不参加进程调度，待适当时候再调入内存、恢复资源、参与运行，这就是进程挂起
  4. 挂起态与等待态有着本质区别
    1. 进程挂起:没有任何资源
    2. 进程等待:占有已申请到的资源处于等待
  5. 结束挂起状态的命令只能由操作系统和父进程发出。

9.3.2. 进程挂起的选择与恢复

  1. 挂起的选择：
    1. 一般选择等待态进程进入挂起等待态
    2. 也可选择就绪态进程进入挂起就绪态
    3. 运行态进程还可以挂起自己
  2. 挂起的恢复
    1. 等待事件结束后，挂起等待态进入挂起就绪态
    2. 一般选择挂起就绪态进程予以恢复
    3. 操作系统极其空闲才会选择调入挂起等待态的进程

9.3.3. 挂起进程的特点

  1. 进程不能被立即执行
  2. 进程可能会有等待事件，但是等待事件是独立于挂起条件的，事件结束并不能导致进程具备执行条件
  3. 由于操作系统、父进程或进程自身阻止其运行

9.4. 补充：SVR4 进程状态模型

preempted:抢占，虚线表示合为一体。

10. 进程的描述与组成

进程的设计时要考虑进程的声明周期，从而引入三态模型

10.1. 进程映像，Process Image

  1. 某一时刻进程的内容及其执行状态集合：
    1. 进程控制块: 每个进程捆绑一个，保存进程的标识信息、现场信息和控制信息。进程创建时创建进程控制块，进程撤销时回收进程控制块，与进程一一对应。
    2. 进程程序块: 进程执行的程序空间，规定进程一次运行所应完成的功能。
    3. 进程数据块: 进程处理的数据空间，是进程的私有地址空间，包括各类私有数据、处理函数的用户栈和可修改的程序
    4. 进程核心栈: 每个进程捆绑一个，进程在内核模式下运行时使用的堆栈，中断或系统过程使用，保存函数调用的参数、局部变量和返回地址等。
  2. 进程运行时如果遇到要执行操作系统内核函数，此时则保存应用程序的全部现场信息及其用户栈，使其不被内核程序破坏。而内核函数运行时使用进程的核心栈来放置工作信息。
  3. 进程映像是内存级的物理实体，又称为进程的内存映像
  4. 进程的内存映像示意图

10.2. 进程控制块，Process Control Block，PCB，又称进程描述符

  1. 进程控制块PCB是OS用于记录和刻画进程状态及环境信息的数据结构，是进程存在的唯一标识，是操作系统刻画进程的执行状态及环境信息的数据结构，是进程动态特征的汇集，是操作系统掌握进程的唯一资料结构和进程调度的主要依据
  2. 包括标识信息、现场信息和控制信息。

10.2.1. 标识信息

用于存放唯一标识该进程的信息

  1. 系统分配的标识号
  2. 系统分配的进程组标识号
  3. 用户定义的进程名
  4. 用户定义的进程组名

10.2.2. 现场信息

用于存放该进程运行时的处理器现场信息

  1. 用户可见寄存器内容：数据寄存器、地址寄存器
  2. 控制与状态寄存器内容：PC、IR、PSW
  3. 栈指针内容：核心栈与用户栈指针

10.2.3. 控制信息

用于存放与管理、调度进程相关的信息

  1. 调度相关信息：状态、等待事件/原因、优先级
  2. 进程组成信息：代码/数据地址、外存映像地址
  3. 队列指引元：进程队列指针、父子兄弟进程指针
  4. 通信相关信息：消息队列、信号量、锁
  5. 进程特权信息：如内存访问权限、处理器特权
  6. 处理器使用信息：占用的处理器、时间片、处理器使用时间/已执行总时间、记账信息
  7. 资源清单信息：如正占有的资源、已使用的资源

10.3. 进程上下文，Process context

  1. 进程的执行需要环境支持，包括CPU现场和Cache中的执行信息。
  2. 在操作系统中，进程物理实体和支持进程运行的环境合称进程上下文。
  3. OS中的进程物理实体和支持进程运行的环境合成进程上下文，包括以下：
    1. 用户级上下文：
      1. 用户程序块(可执行的机器指令序列)
      2. 用户数据区(进程可访问的信息)
      3. 用户栈(存放函数调用过程中的信息)
      4. 用户共享内存(进程通信使用的内存区)
      5. 对换至磁盘的分段或页面仍然是用户级上下文的组成部分。
    2. 寄存器上下文(存储在进程控制块中)：
      1. 处理器状态寄存器(进程当前状态)
      2. 指令计数器(下一条该执行的指令地址)
      3. PSW/栈指针(指向用户栈或核心栈当前地址)
      4. 通用寄存器等
    3. 系统级上下文
      1. PCB(Process Control Block，进程的状态)
      2. 内存区管理信息(进程页表或段表)
      3. 核心栈(进程内核态运行时的工作区)
  4. 进程上下文刻画了进程的执行情况

10.4. 进程队列及其管理

  1. 进程队列分类
    1. 运行队列：通常只有一个进程
    2. 等待(阻塞)队列:也是有机会被调入，他等待的资源或事件完成后，调入就绪队列。
    3. 就绪队列:从就绪队列中挑选进程调入运行，按照优先级或FCFS的原则排队

最后通过系统调用结束处理，进程实现的队列模型不适合使用堆栈(堆栈是先进后出的)

  1. 进程队列组织方式
    1. 链接方式：采用单向链接或双向链接。
    2. 索引方式：利用索引表记录不同状态进程的PCB地址或在PCB表中的编号
    3. 核心是完成入队和出队操作
    4. 进程与资源调度围绕进程队列展开

11. 进程的管理

11.1. 概念级的OS进程管理软件

关键的进程管理软件包括：

  1. 系统调用/中断/异常处理程序:
  2. 队列管理模块:操作系统用来管理进程控制块的信息，核心程序包，是操作系统实现进程管理的核心模块
  3. 进程控制程序:操作系统用于控制进程状态转换用到的程序包
  4. 进程调度程序(独立进程居多)
  5. 进程通信程序(多个程序包)
  6. 终端登录与作业控制程序、性能监控程序、审计程序等外围程序

11.2. 部分进程管理原语(P81)

  1. 进程创建：
    1. 操作系统初始启动时会创建承担系统资源分配和控制管理的一些系统进程，同时会创建一个所有用户集成的祖先，其他用户进程实在用户程序被提价与选中运行时被创建的。
    2. 操作系统通常将创建关系通过父子进程的关系来表示。
    3. 创建原语：进程表加一项、申请PCB(进程控制块)并初始化、生成唯一进程标识、建立进程映像、分配各种资源、移入就绪队列、通知操作系统某些模块
  2. 进程撤销：
    1. 完成特定工作或出现严重错误后需要撤销，分为正常撤销和非正常撤销。
    2. 产生原因：运行结束、执行非法指令、用户态执行特权指令、时间配额到、等待时间超时、越界错误、共享内存区非法使用、程序性故障等。
    3. 撤销原语：从队列中移除、归还资源、撤销标识、回收PCB、移除进程表项
  3. 进程阻塞：
    1. 使得进程让出处理器转而等待一个事件，比如等待资源等，阻塞是同步时间。
    2. 阻塞原语：保存现场信息、修改PCB、移入等待队列、调度其他进程执行
  4. 进程唤醒：
    1. 等待时间完成时产生一个中断，激活操作系统，在系统的控制下将被阻塞进程唤醒
    2. 唤醒原语：等待队列中移出、修改PCB、移入就绪队列(该进程优先级高于运行进程触发抢占)
  5. 进程挂起：
    1. 出现引起挂起的事件时，系统或进程会利用挂起原语把指定进程或处于等待态的进程挂起。
    2. 挂起原语：修改状态并出入相关队列、收回内存等资源送至对换区。
    3. 挂起原语可以由进程自己或其他进程调起。
  6. 进程激活：
    1. 当系统资源尤其是内存资源充裕或请求激活进程时，系统或相关进程会调用激活原语将指定进车行激活。
    2. 激活原语：分配内存，修改状态并出入相关队列。
    3. 激活原语只能由其他进程调用。
  7. 其他：如修改进程特权，以上是一个进程控制的流程

11.3. 原语与进程控制原语(Primitive)

  1. 进程控制过程中涉及对OS核心数据结构(进程表/PCB池/队列/资源表)的修改，不是进程处理的所有指令都是。
  2. 为防止与时间有关的错误，应使用原语
  3. 原语是由若干条指令构成的完成某种特定功能的程序，执行上具有不可分割性(保证对核心资源的访问是正确的，原语涉及到的资源都是共享核心资源，只能是唯一的)，进入原语区间，立刻关闭中断完成，然后再开中断响应。
  4. 原语的执行可以通过关中断实现，进程控制使用的原语被称为进程控制原语，另一类常用原语是进程通信原语

11.4. 进程切换与模式切换(状态转换)

11.4.1. 进程切换

  1. 进程切换指从正在运行的进程中收回处理器，让待运行进程来占有处理器运行
  2. 进程切换实质上就是被中断运行进程与待运行进程的上下文切换。
  3. 进程切换必然发生在内核态而非用户态。

11.4.2. 进程切换的工作过程

  1. (中断/异常等触发)正向模式切换并压入PSW/PC
  2. 保存被中断进程的现场信息
  3. 处理具体中断/异常
  4. 把被中断进程的系统堆栈指针SP值保存到PCB
  5. 调整被中断进程的PCB信息，如进程状态
  6. 把被中断进程的PCB加入相关队列
  7. 选择下一个占用CPU运行的进程
  8. 修改被选中进程的PCB信息，如进程状态
  9. 设置被选中进程的地址空间，恢复存储管理信息
  10. 恢复被选中进程的SP值到处理器寄存器SP
  11. 恢复被选中进程的现场信息进入处理器
  12. (中断返回指令触发)逆向模式转换并弹出PSW/PC

11.4.3. 进程切换的发生时机

进程切换一定发生在中断/异常/系统调用处理过程中，常见的情况是：

  1. 阻塞式系统调用、虚拟地址异常导致被中断进程进入等待态
  2. 时间片中断、I/O中断后发现更高优先级进程，导致被中断进程转入就绪态
  3. 终止用系统调用、不能继续执行的异常导致被中断进程进入终止态

11.4.4. 内核不能执行调度和切换的情况

  1. 内核正在处理中断的过程中
  2. 进程运行在内核临界区
  3. 内核处在需要屏蔽中断的原子操作过程中。

11.4.5. 模式切换(状态转换)

  1. 进程切换必须在操作系统内核模式下完成，这就需要用到模式切换。
  2. 模式切换又称处理器状态切换，包括：
    1. 用户模式到内核模式由中断/异常/系统调用中断用户进程执行而触发
    2. 内核模式到用户模式OS执行中断返回指令将控制权交还用户进程而触发

11.4.6. 模式切换(状态转换)的基本工作任务

  1. 中断装置完成正向模式切换，包括：
    1. 处理器模式转为内核模式
    2. 保存当前进程的PC/PSW值到核心栈
    3. 转向中断/异常/系统调用处理程序
  2. 中断返回指令完成逆向模式转换，包括：
    1. 从待运行进程核心栈中弹出PSW/PC值
    2. 处理器模式转为用户模式

11.4.7. 模式切换(状态转换)的处理器情况

  1. 用户空间中，处于进程上下文，应用进程在用户态下运行，使用用户栈。
  2. 内核空间中，处于进程上下文，内核代表进程在内核态下运行，使用核心栈。
  3. 内核空间中，处于中断上下文，与任何进程无关，中断服务例程在内核态下处理特定中断。
  4. 内核空间中，内核线程(无用户地址空间的进程)运行于内核态。

11.4.8. 进程切换与模式切换(状态转换)

  1. 一些中断/异常不会引起进程状态转换，不会引起进程切换，只是在处理完成后把控制权交回给被中断进程，处理流程是：
    1. (中断/异常触发)正向模式切换压入PSW/PC
    2. 保存被中断进程的现场信息
    3. 处理中断/异常
    4. 恢复被中断进程的现场信息
    5. (中断返回指令触发)逆向模式转换弹出PSW/PC
  2. 比如计时中断，中断处理完成后直接恢复
  3. 模式切换是进程仍在自己的上下文进行处理，仅仅是处理器状态发生了变化，内核仍然被中断进程的上下文中进行处理。

12. 多线程技术概述

  1. 最开始设计进程的时候并没有体现线程的概念

12.1. 单线程结构

传统进程是单线程结构进程

12.1.1. 单线程结构进程的问题

单线程结构进程在并发程序设计上存在的问题

  1. 进程切换开销大:10个人干100天的活动->开会等活动产生的开销，进程切换要进行模式切换，然后再启动进程调度，选择一个就绪进程占用处理器，恢复现场，然后再反向进行。
  2. 进程通信开销大:指令流如果分布在不同进程中，那么每次交互都需要由内核完成。
  3. 限制了进程并发的粒度:如果没有线程概念，那么进程中本身不可以并发，粒度比较高
  4. 降低了并行计算的效率

12.1.2. 解决问题的思路

  1. 把进程的两项功能分离开来
    1. 独立分配资源(进程概念上)，进程作为系统资源分配和保护的独立单位，不需要频繁地切换
    2. 被调度分派执行(线程概念上)，线程作为系统调度和分派的基本单位，能轻装运行，会被频繁地调度和切换
  2. 线程的出现会减少进程并发执行所付出的时空开销，使得并发粒度更细、并发性更好
  3. 两项功能绑定就是单线程进程，两项功能分离就是多线程进程。

12.2. 多线程结构进程

12.2.1. 多线程环境下进程的概念

  1. 在多线程环境中，进程是操作系统中除处理器以外的资源分配和保护的独立单位。具有:
    1. 用来容纳进程映像的虚拟地址空间
    2. 对进程、文件和设备的存取保护机制

12.2.2. 多线程环境下线程的概念

  1. 线程是进程能够并发执行的实体，是进程的组成单位，也是处理器调度和分派的基本单位。
  2. 进程是一条执行路径，有独立的程序计数器，未运行时保护线程上下文。
  3. 同一个进程中的所有线程共享进程获得的主存空间和资源。它具有：
    1. 线程执行状态
    2. 受保护的线程上下文，当线程不运行时，用于存储现场信息
    3. 独立的程序指令计数器
    4. 执行堆栈
    5. 容纳局部变量的静态存储器
    6. 线程控制块

12.2.3. 多线程结构进程中的进程与线程

  1. 于是，进程可以分为两部分:
    1. 资源集合
    2. 线程集合。
  2. 进程要支撑线程运行，为线程提供虚拟地址空间和各种资源。
  3. 进程封装管理信息，包括对指令代码、全局数据、打开的文件和信号量等共享部分的管理。
  4. 线程封装执行信息，包括状态信息、寄存器、执行栈（用户栈指针与核心栈指针）和局部变量、过程调用参数、返回值等私有部分的管理。
  5. 由于线程具有传统进程的许多特征，所以也把线程称为轻量级进程(Light Weight Process,LWP)

12.2.4. 多线程环境下线程的状态与调度

  1. 线程状态有运行、就绪和等待和终止，(没有挂起状态时因为挂起和资源有关，而进程是资源管理的单位，与线程无关)
  2. 与线程状态变化有关的线程操作有：孵化、封锁、活化、剥夺、指派、结束
  3. OS感知线程环境下：
    1. 处理器调度的对象是线程
    2. 线程的存在、状态等都需要被操作系统内核感知到，进程没有三状态，或者说只有挂起状态。
  4. OS不感知线程环境下：
    1. 处理器调度的单位仍然是进程
    2. 用户空间中的用户调度程序调度线程，内核不参加线程调度。
  5. 状态转换模型
    1. 运行态->终止态(撤销Return)
    2. 运行态->就绪态(中断系统)
    3. 运行态->就绪态(时间片用完)
    4. 就绪态->运行态
  6. DBMS:Client(请求方，Request)和Server(应答，Response)，Client频繁请求，Server频繁响应，Jacketing避免阻塞

12.3. 并发多线程程序设计的优点

  1. 快速线程切换：改变堆栈和寄存器，不需要改变地址空间
  2. 减少(系统)管理开销：线程的创建和撤销要简单很多
  3. (线程)通信易于实现：自动共享进程的内存和文件
  4. 并行程度提高
  5. 节省内存空间

12.4. 多线程技术的应用

  1. 前台和后台工作:word的输入和拼写检查
  2. C/S应用模式:用户和服务器，其他线程调用
  3. 加快执行速度
  4. 设计用户接口

13. KLT与ULT

13.1. 内核级线程 KLT, Kernel-Level Threads

  1. 线程管理的所有工作由OS内核来做，并提供了一个应用程序设计接口API，供开发者使用KLT，
  2. 创建时：内核为其创建进程和一个基线程，线程实行过程中通过内核的创建线程原语来创建其他线程。
  3. OS直接调度KLT，KLT用于解决物理并行性问题，内核可以感知到所有的内核级线程，可以控制器其数据结构，内核调度在线程的基础上进行。

13.1.1. 内核级线程示意图

13.1.2. 内核级线程的特点

  1. 优点：
    1. 在多处理器上内核可以同时调度统一进程的多个线程运行。
    2. 进程中的某一线程被阻塞了，内核能调度同一进程的其它线程占有处理器运行，也可以运行其他进程。
    3. 由于内核比较小，内核自身也可用多线程技术实现，能提高操作系统的执行速度和效率。
  2. 缺陷：
    1. 应用程序线程在用户态运行，线程调度和管理在内核实现，在同一进程中，控制权从一个线程传送到另一个线程时需要模式切换，系统开销较大。
    2. 线程调度开销大，线程通信开销小。

13.2. 用户级线程ULT, User-Level Threads

  1. 用户空间运行的线程库，提供多线程应用程序的开发和运行支撑环境。任何应用程序均需通过线程库进行程序设计，再与线程库连接后运行
  2. 线程管理的所有工作都由应用程序完成，内核没有感知到线程的存在，内核感知到的单位是进程。

13.2.1. 用户级线程示意图

13.2.2. 用户级线程的特点

  1. 优点：
    1. 节省开销和内核资源:所有线程管理数据结构均在进程的用户空间中，线程切换不需要内核模式，能节省模式切换开销和内核的宝贵资源。
    2. 允许进程按应用特定需要选择调度算法，甚至根据应用需求裁剪调度算法。
    3. 可移植性好:能运行在任何OS上，内核在支持ULT方面不需要做任何工作。
    4. ULT可以解决逻辑并行性问题。
  2. 缺点：
    1. 不能利用多处理器的优点，OS调度进程，仅有一个ULT能执行。
    2. 一个ULT的阻塞，将引起整个进程的阻塞:不能完成切换线程，因为内核感知不到进程中的线程的存在。
  3. ULT可以解决逻辑并行性问题。

13.3. Jacketing技术

  1. 把阻塞式系统调用改造成非阻塞式的:解决一个ULT的阻塞导致整个进程阻塞，避免进程因此从运行态→\rightarrow阻塞态，如此的频繁切换会带来比较大的开销。
  2. 当线程陷入系统调用时，执行Jacketing程序。
  3. 由Jacketing程序来检查资源使用情况，以决定是否执行进程切换或传递控制权给另一个线程

13.4. 用户级线程 vs. 内核级线程

  1. 受限条件下的并行:受限条件是同步关系(等待)
  2. ULT适用于解决逻辑并行性问题
  3. KLT适用于解决物理并行性问题

13.5. 多线程实现的混合式策略

  1. 在用户空间完成所有的线程的创建工作。
  2. 单应用的多个ULT可以映射成一些KLT，通过调整KLT数目，可以达到较好的并行效果。
  3. 在混合式线程中，内核必须支持内核级多线程的建立、调度和管理，同时也允许应用程序建立、调度和管理用户级线程。
  4. 用户级线程的切换仅在用户空间中且仅需要少量机器指令，而内核级线程需要用户态到内核态到用户态的完整上下文切换，修改内存映像，使得高速缓存失效，导致数量级的延迟。

13.5.1. 多线程实现混合式策略的特点

  1. 合并了用户级线程/内核级线程设施
  2. 线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行
  3. 一个应用中的多个用户级线程被映射到一些(小于等于用户级线程数目)内核级线程上
  4. 程序员可以针对特定应用和机器调节内核级线程的数目，以达到整体最佳结果
  5. 该方法将会结合纯粹用户级线程方法和内核级线程方法的优点，同时减少它们的缺点

13.5.2. 线程混合式策略下的线程状态

  1. KLT的三态模型，由系统调度负责
  2. ULT的三态模型，由用户调度负责
  3. 活跃态的ULT代表绑定KLT的三态
  4. 活跃态的ULT运行时可激活用户调度，非阻塞系统调用可使用Jacketing启动用户调度，调整活跃态ULT

  1. 为什么是活跃态绑定KLT的三态？
  2. 因为如果绑定的KLT不再运行，则也不再运行。活跃态代表了KLT，可能是运行态、可运行态、阻塞态

13.5.3. 多线程实现的各种策略总结

混合式多线程合并了内核级多线程和用户级多线程的优势，甚至可以指派到CPU，或由操作系统绑定。

13.5.4. Solris 多线程技术

包含了多种情况，上图引入了轻量级线程，将轻量级线程与内核级线程映射，原来的多线程设计是Process2，只有一个处理进程，允许给一个进程配置超过一个处理器。

  1. 进程一:单进程单线程，内核级多线程
  2. 进程二:单进程双线程，进程映射到两个轻量级线程，相当于用户级多线程
  3. 进程三:两进程三线程，内核级多线程
  4. 进程四:两进程两线程，内核级多线程
  5. 进程五:三进程四线程，混合级线程，直接做指派意味着线程非常重要，需要单独指派。

一个进程的线程可以被分发到各个位置上并行完成，处理器只能感知进程，不能感知线程，并且只会将一个处理器分配给线程，然后用户空间将得到的处理器分配给线程。

14. 处理器调用

14.1. 处理器调度层次

  1. 高级调度：又称长程调度、作业调度，决定能否加入到执行的进程池中，管理从创建进程到调度运行再到结束阶段后的善后部分的全过程。
  2. 中级调度，又称平衡调度、中程调度，根据内存资源情况决定内存中所能容纳的进程数目，并完成外存和内存中的进程对换工作。
  3. 低级调度：又称短程调度、进程调度/线程调度，根据某种原则决定就绪队列中哪个进程/线程获得处理器，并将处理器让出给它使用。

14.1.1. 处理器调度层次与进程状态转换

这个说明录入各级调度和七态模型的情况，三个框分别表明不同调度层次，如上图所示。资源紧张时挂起，资源空闲时解挂

14.1.2. 处理器调度层次与关键状态转换

14.1.3. 高级调度

  1. 在分时操作系统中，高级调度决定：
    1. 是否接受一个终端用户的连接
    2. 命令能否被系统接纳并构成进程
    3. 新建态进程是否加入就绪进程队列
  2. 批处理OS中，高级调度又称为作业调度，功能是按照某种原则从后备作业队列中选取作业进入主存，并为作业做好运行前的准备工作和完成后的善后工作

14.1.4. 中级调度

  1. 引进中级调度是为了提高内存利用率和作业吞吐量
  2. 中级调度决定那些进程被允许驻留在主存中参与竞争处理器及其他资源，起到短期调整系统负荷的作用
  3. 中级调度把一些进程换出主存，从而使之进入"挂起"状态，不参与进程调度，以平顺系统的负载

14.1.5. 低级调度

  1. 低级调度：又称处理器调度、进程调度、短程调度，按照某种原则把处理器分配给就绪态进程或内核级线程
  2. 进程调度程序：又称分派程序，操作系统中实现处理器调度的程序，是操作系统的最核心部分
  3. 处理器调度策略的优劣直接影响到整个系统的性能，这个进程被很多操作系统称为0号进程，所有进程的父进程
  4. 低级调度主要是负责记录进程或内核级线程的状态、决定某个进程或内核级线程什么时候获得处理器以及占用时间、将处理器分配给进程或内核级线程、回收处理器。

14.1.6. 综述三级调度

  1. 一般操作系统都配置了高级调度和低级调度，而功能完善的操作系统为了提高内存利用率和作业吞吐率引进了中级调度。
  2. 因此，从处理器调度的层次来讲，可以划分为三级调度模型和两级调度模型。

14.2. CPU从进程到进程的切换

  • 内核态进程占用时间不应该过多，应当尽量避免频繁的模式切换
    1. 正向切换(从用户态转换到内核态):Trap、系统调用、中断
    2. 反向切换(从内核态转换到用户态):ret

14.3. 进程抽象

我们需要不断完善中断处理子系统，内核态是将特权指令和非特权指令混搭使用。

15. 处理器调度算法

15.1. 选择处理器调度算法的原则

在以下的五个方面进行巧妙的平衡来完成操作系统的设计。

  1. 资源利用率：使得CPU或其他资源的使用率尽可能高且能够并行工作

CPU利用率=CPU有效工作时间CPU总运行时间CPU总运行时间=CPU有效工作时间+CPU空闲等待时间\begin{aligned} &CPU利用率 = \frac{CPU有效工作时间}{CPU总运行时间} \\ &CPU总运行时间 = CPU有效工作时间 + CPU空闲等待时间 \\ \end{aligned}

  1. 吞吐量：单位事假内CPU处理作业的个数，服务器的TPS，例如12306或淘宝
  2. 公平性：确保每个用户每个进程获得合理的CPU份额或其他资源份额
  3. 响应时间：
    1. 使交互式用户的响应时间尽可能小，或尽快处理实时任务
    2. 细分包含输入的程序命令传送到CPU时间、CPU处理请求命令的时间、处理所形成的响应回送到终端显示器的时间。
  4. 周转时间：提交给系统开始到执行完成获得结果为止的这段时间间隔称周转时间，应该使周转时间或平均周转时间尽可能短。

作业i周转时间ti=完成时刻tf−提交时刻ts平均作业周转时间T=∑i=1ntin作业带权周转时间wi=周转时间ti运行时间tk平均带权做作业周转时间W=∑i=1nwin\begin{aligned} &作业i周转时间t_i = 完成时刻t_f - 提交时刻t_s \\ &平均作业周转时间T = \frac{\sum\limits_{i=1}\limits^nt_i}{n}\\ &作业带权周转时间w_i = \frac{周转时间t_i}{运行时间t_k} \\ &平均带权做作业周转时间W =\frac{\sum\limits_{i=1}\limits^nw_i}{n} \end{aligned}

15.2. 短程调度准则

  1. 与性能相关
    1. 面向用户：周转时间、响应时间、最后期限
    2. 面向系统：吞吐量、处理器利用率
  2. 与性能无关
    1. 面向用户：可预测性
    2. 面向系统：公平、强制优先级、平衡资源

15.3. 低级调度的主要功能

  1. 调度：实现调度策略，确定就绪态进程/线程竞争使用处理器的次序的裁决原则。
  2. 分派：实现调度机制，确定如何时分复用CPU，处理上下文切换，完成进程/线程同CPU的绑定以及放弃的实际工作

15.4. 调度的模式

  1. 抢占式(剥夺式)调度：当前正在运行的进程可能被操作系统中断，并转移到就绪态。处理器剥夺原则：
    1. 高优先级进程/线程可剥夺低优先级进程/线程。
    2. 运行进程/线程时间片用完后被剥夺。
  2. 非抢占式(非剥夺式)调度：一个进程一旦处于运行态，它就不断执行直到终止，或者为等待I/O或请求某些操作系统服务而阻塞自己。
  3. 与非抢占式调度相比，抢占式调度可能会导致较大的开销，但是可能对所有进程提供更好的服务，可以避免任何一个进程独占处理器太长时间

15.5. 优先数调度算法

  1. 操作系统往往无法判断进程会使用CPU多久，所以现代操作系统一般会使用时间片轮转来完成调度。
  2. 排列论:随机过程(Stochastic Process，Markor)

15.5.1. 根据分配给进程的优先数决定运行进程

  1. 抢占式(Preemptive)优先数调度算法，出现高优先级则中断，抢占一定是从运行态到就绪态的转换，抢占点的安排可能不一样，在实时系统中将抢占点提前，不等一个进程使用完时间片，而是新进程到达就发生抢占，或者时间片用完抢占。
  2. 非抢占式(non-preemptive)优先数调度算法，出现CPU空闲再选择。

15.5.2. 优先数的确定准则

  1. 进程负担任务的紧迫程度
  2. 进程的交互性
  3. 进程使用外设的频度:使用外设的优先
  4. 进程进入系统的时间长短:公平性和周转的问题

15.5.3. 调度算法分类

  1. FCFS (先来先服务) 非抢占
  2. RR (时间片轮转) 抢占
  3. SPN (最短进程优先) 非抢占，真正操作系统没有办法使用
  4. SRT (最短剩余时间优先) 抢占，真正操作系统没有办法使用
  5. HRRF (最高响应比优先) 非抢占，真正操作系统没有办法使用
  6. Feedback (多级反馈调度) 抢占

15.6. 与进入系统时间相关的优先数

  1. 计算时间短(作业/进程)优先
  2. 剩余计算时间短进程优先：商业操作系统可以这么处理，但是别的可能有一定的问题。
  3. 响应比高者(作业/进程)优先：

响应比=等待时间+期待服务时间期待服务时间=1+等待时间期待服务时间\begin{aligned} &响应比 = \frac{等待时间 + 期待服务时间}{期待服务时间}\\ &\qquad\qquad = 1 + \frac{等待时间}{期待服务时间} \\ \end{aligned}

  1. 先来先服务：先进队先被选择：多用于高级调度；低级调度中，以计算为主的进程过于优越

16. 具体调度算法

16.1. FCFS (先来先服务)

  1. 当某个进程就绪时，就加入就绪队列(ready queue)，当前正在运行的进程停止执行时，选择在就绪队列到达时间最长的进程运行
  2. 平均作业周转时间与作业提交和调度顺序有关。
  3. 两个弊端
    1. 一个短进程可能不得不等待很长时间才能获得执行，导致吞吐率很难提高，加权中转时间会上升，最差的情况就是计算型死循环，导致完全无法调度。
    2. 偏袒计算为主的进程:I/O多的进程不得不等待计算为主的进程做完，因为需要等待资源，离开后需要重新排队。
  4. 性能会非常差，不被现在的操作系统使用。
  5. 先来先服务算法示例：

  1. 平均作业周转时间T+3+7+9+12+125=8.6T + \frac{3 + 7 + 9 + 12 + 12}{5} = 8.6
  2. 平均带权作业周转时间T+33+76+94+125+1225≈2.563T + \frac{\frac{3}{3} + \frac{7}{6} + \frac{9}{4} + \frac{12}{5} + \frac{12}{2}}{5} \approx 2.563

16.2. SPN (最短进程优先)

  1. SPN是一种非抢占式调度，会选择处理时间最短的进程，短进程将会越过长进程，优先获得调度，又称为SJF。

  1. 平均作业周转时间T=3+7+11+14+35=7.6T = \frac{3 + 7 + 11 + 14 + 3}{5} = 7.6
  2. 平均带权作业周转时间W=33+76+114+145+325≈1.843W = \frac{\frac{3}{3} + \frac{7}{6} + \frac{11}{4} + \frac{14}{5} + \frac{3}{2}}{5} \approx 1.843
  3. 问题:
    1. 需要预知作业所需的CPU运行时间
    2. 忽略了作业的等待时间：只要持续不断地提供更短的进程，长进程就有可能饿死，同样也会服务不到。
    3. 分时、实时处理仍然不理想。

16.3. SRT，Shortest Remaining Time，最短剩余时间优先

  1. SRT是一种抢占式调度，调度器总是选择预期剩余时间更短的进程
  2. 当一个新进程加入就绪队列，他可能比当前运行的进程具有更短的剩余时间，只要新进程进入就绪队列，调度器就可能抢占当前正在运行的进程

  1. 平均等待时间=(3−3−0)+(15−6−2)+(8−4−4)+(20−5−6)+(10−2−8)5=3.2=\frac{(3 - 3 - 0) + (15 - 6 - 2) + (8 - 4 - 4) + (20 - 5 - 6) + (10 - 2 - 8)}{5} = 3.2
  2. 平均周转时间=(3−0)+(15−2)+(8−4)+(20−6)+(10−8)5=7.2=\frac{(3 - 0) + (15 - 2) + (8 - 4) + (20 - 6) + (10 - 8)}{5} = 7.2

16.4. HRRN (最高响应比优先)Highest Response Ratio Next

  1. 非抢占式算法，性能略差与SPN(SJF)
  2. 选择响应比最高的进程：出发点是兼顾公平，对于短进程有利
  3. 每当需要调度时，计算出所有的响应比，选择最高的。

响应比=等待时间+期待服务时间期待服务时间=1+等待时间期待服务时间\begin{aligned} &响应比 = \frac{等待时间 + 期待服务时间}{期待服务时间}\\ &\qquad\qquad = 1 + \frac{等待时间}{期待服务时间} \\ \end{aligned}

时刻 A B C D E
0时刻 11 未到 未到 未到 未到
3时刻 完成 1+16≈1.171 + \frac{1}{6} \approx 1.17 未到 未到 未到
9时刻 完成 完成 1+54=2.251 + \frac{5}{4} = 2.25 1+35=1.61 + \frac{3}{5} = 1.6 1+12=1.51 + \frac{1}{2} = 1.5
13时刻 完成 完成 完成 1+75=2.61 + \frac{7}{5} = 2.6 1+52=3.51 + \frac{5}{2} = 3.5
15时刻 完成 完成 完成 1+125=3.41 + \frac{12}{5} = 3.4 万=完成

16.5. 优先级调度

  1. 调度器总是选择优先级较高的进程，提供多个就绪队列(一组就绪队列)，代表各个级别的优先级。
  2. 低优先级的进程可能很难被执行到？一个进程的优先级应该随着它的时间或执行的历史而变化。
  3. 如果就绪队列中出现优先级高的进程/线程，系统可以预先规定策略为非剥夺式和剥夺式策略。
  4. 优先级的确定
    1. 用户给出优先级
    2. 系统综合考虑各因素，包括打开文件数、资源申请情况等等
  5. 优先级确定方式
    1. 静态：生命周期内不改变，容易造成饥饿问题。
    2. 动态：生命周期内可能会发生改变，正在运行的进程逐渐降低优先级，正在等待的进程逐渐提高优先级。

16.6. RR(时间片轮转调度算法)

  1. 本质也是先来先服务，但是要按照时间片来进行调度。
  2. 根据各个进程进入就绪队列的时间先后轮流占有CPU一个时间片，基于时钟做抢占式调度。
  3. 时间片中断：以一个周期性间隔产生时钟中断，当中断发生时，当前正在运行的进程被置于就绪队列队尾，然后基于FCFS策略选择下一个就绪进程运行
  4. 时间片的确定：选择长短合适的时间片，一般为10ms到200ms
    1. 过长则退化为先来先服务算法
    2. 过短则调度开销显著增大
  5. 时间片分为单时间片、多时间片和动态时间片三种
  6. 使用时间片轮转调度算法，在给一个进程分配处理器的时候，不需要知道进程需要多长时间
  7. 很多的调度都会结合时间片轮转调度算法来实现
  8. 如果时间片还没有用完就已经完成了进程的事务，那么就立即释放时间片，调度下一个进程进入占用新的时间片运行。

16.6.1. 使用情况

  1. 先进先出/最短时间/剩余时间/响应比优先算法，无法判断进程需要占用多长时间的CPU
  2. 有预估时间的调度，用在作业调度、云计算调度中比较合适，在低级调度中不合适

16.6.2. 进程分类

  1. 以计算为主的进程：不需要内核参与，没有从运行态到阻塞态的情况，如果出现死循环进程也必须要遵循时间片轮换，如果进程比较多，就可以淡化死循环的影响
  2. I/O(外设)频繁的进程：发生运行态到阻塞态的可能性比较大，根据各个进程进入就绪队列的时间先后轮流占用CPU一个时间片，时间片到即发生时间片中断。

16.6.3. 时间片轮转调度算法示例

务必关注就绪队列

16.7. 多级反馈调度 (Multi-level Feedback Queue，MLFQ)，又称分级调度

  1. 基本思想
    1. 建立多个不同优先级的就绪进程队列
    2. 多个就绪进程队列之间按照优先数调度
    3. 高优先级的就绪进程, 分配的时间片短
    4. 单个就绪进程队列中的进程的优先数和时间片相同,按照先来先服务算法调度
  2. 分级原则：外设访问、交互性、时间紧迫程度、系统效率、用户立场
  3. 现代操作系统的实现模型
    1. 多个高优先级的实时进程队列，如：硬实时、网络、软实时
    2. 多个分时任务的进程队列，根据基准优先数和执行行为调整
    3. 队列数可能多达32-128个
  4. 如果没做完会惩罚降级，做题目要至少画一下前几个RQ。如果进程掉出去的同时，有新的进程进入，那么新的进程优先进入就绪队列
  5. 对以计算为主的长进程不友好，就绪队列越深获得调度的机会越小
  6. 不同的进程可以设置不同的时间片长度:q=2iq = 2^i，i是层数，所以第一层时间片长为1，第二层长为2
  7. 多级队列更能够发现先到达的，时间片比较短的处理完。
  8. 除了极少数的硬实时操作系统使用抢占式调度算法，绝大多数操作系统有效地组合时间片调度算法和优先数调度算法，采用分级调度算法的策略加以实现
  9. 如果没有竞争不掉下去，时刻1(根据考试具体情况决定)

16.7.1. q = 1 时的多级反馈调度的示例

16.7.2. q = 2i2^i时的多级反馈调度的示例

16.7.3. 多级反馈调度的示意图

  1. 如果没有进程竞争，那么会不会导致进程掉下去，根据具体情况分析，可能掉下去也可能没有掉下去。
  2. 此时RQ0是A，RQ2是C，当前A在做，那么A掉下来后是运行A还是C，可以考虑运行A进程：因为掉到了RQ1，也可以考虑运行C进程，具体情况要看操作系统时间中的细节
  3. 刚好做完的时刻，B同步进入也需要细规则来完善。

16.8. 彩票调度算法

  1. 基本思想：为进程发放针对系统各种资源(如CPU时间)的彩票；当调度程序需要做出决策时，随机选择一张彩票，持有该彩票的进程将获得系统资源
  2. 功能比保证调度好的多，服务器和客户：客户需要调用服务器服务，则将彩票交给服务器
  3. 合作进程之间的彩票交换
  4. 一般不会在实时操作系统中使用，但是可以在服务器端进行使用，特别是视频点播服务器

16.9. 传统Unix系统的调度(例)

  1. 多级反馈队列，每个优先级队列使用时间片轮转
  2. 每秒重新计算每个进程的优先级
  3. 给每个进程赋予基本优先级的目的是把所有进程划分成固定的优先级区
  4. 可控调节因子

16.10. Unix SVR4调度算法(例)

  1. 100-159是实时部分任务

  2. 60-99是内核部分任务

  3. 0-59是分时部分任务

  4. 多级反馈队列，每一个优先数都对应于一个就绪进程队列

    1. 实时优先级层次：优先数和时间片都是固定的，在抢占点执行抢占
    2. 分时优先级层次：优先数和时间片是可变的，从0优先数的100ms到59优先数的10ms

16.11. Bands

优先级递减：对换、块I/O设备控制、文件操作、字符I/O设备控制、用户进程

16.12. Windows调度算法(例)

  1. 主要设计目标：基于内核级线程的可抢占式调度，向单个用户提供交互式的计算环境，并支持各种服务器程序
  2. 优先级和优先数
  3. 实时优先级层次(优先数为31-16)：用于通信任务和实时任务，优先数不可变
  4. 可变优先级层次(优先数为15-0)：用于用户提交的交互式任务，优先数可动态调整
  5. 多级反馈队列，每一个优先数都对应于一个就绪进程队列
  6. 优先数可动态调整原则
    1. 线程所属的进程对象有一个进程基本优先数，取值范围从0到15
    2. 线程对象有一个线程基本优先数，取值范围从-2到2
    3. 线程的初始优先数为进程基本优先数加上线程基本优先数，但必须在0到15的范围内
    4. 线程的动态优先数必须在初始优先数到15的范围
  7. 当存在N个处理器时，N-1个处理器上将运行N-1个最高
    先级的线程，其他线程将共享剩下的一个处理器

17. 批处理作业的调度

17.1. 批处理作业的管理

  1. 作业说明语言和作业说明书
  2. 脱机控制方式(批处理控制方式)
  3. 作业控制块JCB
  4. 作业状态
    1. 输入状态：作业正在从输入设备上预输入信息
    2. 后备状态：作业预输入结束但尚未被选中执行
    3. 执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行
    4. 完成状态：作业运行结束，正在等待缓输出
  5. 作业默认所有的资源调度都是静态调度(静态分配)完成的，输出井来完成。

17.2. 批处理作业的状态作业调度与进程调度

  1. 作业调度：按一定的策略选取若干个作业让它们进入内存、构成进程去竞争处理器以获得运行机会
  2. 用户立场：自己作业的周转时间尽可能的小
  3. 系统立场：希望进入系统的作业的平均周转时间尽可能的小
  4. 适当的作业调度算法必须既考虑用户的要求又有利于系统效率的提高

18. 补充

18.1. 习题(进程管理的fork系统调用)
  1. fork会克隆出一个新的进程，但是是同一个PC，也就是从父进程的当前步骤开始往下做
  2. 第一次fork A -> B
  3. 第二次fork A -> C, B -> D
  4. 到三次fork A -> E, B -> F, C -> G, D -> H

18.2. 阿里云平台

  1. 章文嵩:Linux集群，LVS，尽量节能
  2. 使用了灵动处理器
2020-计算机操作系统
#课程笔记 #进程 #中断 #处理器 #计算机操作系统 #调度
2020-计算机操作系统-Lecture2-处理器管理
https://spricoder.github.io/2020/01/18/2020-OS/2020-OS-Lecture2-%E5%A4%84%E7%90%86%E5%99%A8%E7%AE%A1%E7%90%86/
作者
SpriCoder
发布于
2020年1月18日
许可协议