处理器概念

特权指令和非特权指令、管态和目态已在上一篇提及。

Intel的X86处理器具有四个特权级别，分别是RING0、RING1、RING2、RING3，RING0层拥有最高权限，依此向下RING3层即拥有最低的权限。

用户态切换为核心态是通过中断实现的。并且中断是唯一途径，用户手动触发中断的指令称为陷阱指令，也称为访管指令。

核心态切换为用户态是通过执行一个特权指令，将程序状态字(PSW)的标志位设置为用户态。

用户栈和核心栈

用户栈：是用户进程空间中开辟的内存区域，用于保存应用程序的子程序(函数)间相互调用的参数、返回值、返回点以及子程序的局部变量。

核心栈：每个进程被创建时捆绑一个核心栈，是内存中属于OS空间的区域，用途包括：用于保存中断现场；或保存OS程序间相互调用的参数、返回值、返回点以及程序局部变量。

程序状态字PSW

计算机如何知道当前处于管态还是目态？通常OS都引入程序状态字PSW（Program Status Word）来区别不同的处理器工作状态。

PSW用来控制指令执行顺序并保留和指示与程序有关的系统状态，主要作用是实现程序状态的保护和恢复。每个程序都有一个与其执行相关的PSW，每个处理器都设置一个PSW寄存器。程序占有处理器执行，它的PSW将占有PSW寄存器。

PSW寄存器包括以下内容：
+ 程序基本状态：
1. 程序计数器；
2. 条件码；
3. 处理器状态位。
+ 中断码：保存程序执行时当前发生的中断事件。
+ 中断屏蔽位：指明程序执行中发生中断事件时，是否响应出现的中断事件。

Intel x86中，PSW由标志寄存器EFLAGS和指令指针寄存器EIP组成，均为32位。

EFLAGS的低16位称FLAGS，标志可划分为三组：状态标志、控制标志、系统标志。

中断技术

中断是指程序执行过程中，遇到急需处理的事件时，暂时中止CPU上现行程序的运行，转去执行相应的事件处理程序，待处理完成后再返回原程序被中断处或调度其他程序执行的过程。

中断源分类

• 内中断：信号的来源是CPU内部，与当前执行的指令有关
  • I/O中断
  • 访管中断：调用访管指令，是程序自愿的
  • 硬件故障
  • 程序性中断（和编程时的问题有关）
• 外中断：信号的来源是CPU外部，与当前执行的指令无关
  • 外部设备请求
  • 时钟中断

外中断又分可屏蔽中断和不可屏蔽中断，内中断完全不可屏蔽。

时钟是操作系统进行调度工作的重要工具，如让分时进程作时间片轮转、让实时进程定时发出或接收控制信号、系统定时唤醒或阻塞一个进程、对用户进程进行记账。

中断优先级

每个不同中断具有不同的中断优先级，表示事件的紧急程度，在处理高一级中断时，往往会屏蔽部分或全部低级中断。级别高的有优先获得响应的权力，中断装置预定的这个响应顺序称为中断优先级。

多重中断事件的处理

中断正在进行处理期间，CPU又响应新的中断事件，于是暂时停止正在运行的中断处理程序，转去执行新的中断处理程序，就叫多重中断（又称中断嵌套）。处理方法：
1. 串行处理，
2. 嵌套处理，
3. 即时处理。

进程及其实现

进程概念

• 进程是可并发执行的程序在某个数据集合上的一次计算活动，也是操作系统进行资源分配和保护的基本单位。
• 进程是一个既能用来共享资源，又能描述程序并发执行过程的系统基本单位。
• 进程是一种支持程序执行的系统机制。

进程的属性：
+ 动态性
+ 共享性
+ 独立性：独立性会体现在虚存、程序计数器、内部状态上
+ 制约性
+ 并发性

进程状态和转换

本节参考和图片来源：进程的状态转换 - LRH呀 - 博客园

三态模型

三态模型，也是最基本的几个状态：

• 就绪态意味着运行条件满足，等待系统分配处理器以便运行
• 运行态是已分配处理器，正在运行的状态
• 等待态（也称为阻塞态）是不具备运行条件，等待某个事件完成，如IO输入。

五态模型

五态模型在三态模型的基础上加了新建态和终止态。

• 新建态：对应于进程被创建时的状态，尚未进入就绪队列。
  >创建一个进程需要通过两个步骤：
  1.为新进程分配所需要资源和建立必要的管理信息。
  2.设置该进程为就绪态，并等待被调度执行。
• 终止态：指进程完成任务到达正常结束点，或出现无法克服的错误而异常终止，或被操作系统及有终止权的进程所终止时所处的状态。
  >处于终止态的进程不再被调度执行，下一步将被系统撤销，最终从系统中消失。
  终止一个进程需要两个步骤：
  1.先等待操作系统或相关的进程进行善后处理（如抽取信息）。
  2.然后回收占用的资源并被系统删除。

七态模型

三态模型和五态模型都是假设所有进程都在内存中的事实上有序不断的创建进程，当系统资源尤其是内存资源已经不能满足进程运行的要求时，必须把某些进程挂起（suspend），对换到磁盘对换区中，释放它占有的某些资源，暂时不参与低级调度。 起到平滑系统操作负荷的目的。

七态模型在五态模型的基础上增加了挂起就绪态（ready suspend）和挂起等待态（blocked suspend）。

• 挂起就绪态：进程具备运行条件，但目前在外存中，只有它被对换到内存才能被调度执行。
• 挂起等待态：表明进程正在等待某一个事件发生且在外存中。

进程的描述和组成

进程映像

进程实体(进程映像)的组成：
+ 进程控制块（PCB）
+ 进程程序块
+ 进程核心栈
+ 进程数据块

进程控制块PCB，是OS用于记录和刻划进程状态及有关信息的数据结构。也是OS掌握进程的唯一资料结构，它包括进程执行时的情况，以及进程让出处理器后所处的状态、断点等信息。 PCB是进程存在的唯一标志。

进程控制块包含三类信息：
+ 标识信息，包括进程号（pid），进程组，用户标识符（uid）
+ 现场信息，包含中断时处理器的信息
+ 控制信息
+ 进程调度的相关信息，如进程优先级
+ 进程组成信息
+ 进程间的族系信息
+ 进程间通信信息

进程队列及其管理

处于同一状态的所有PCB链接在一起的数据结构称为进程队列。 可按先来先到的原则排成队列，也可按优先数或其它原则排队。

组织方式：
+ 线性方式
+ 链接方式：操作系统持有指向各个队列的指针
+ 索引方式：根据进程状态的不同，建立几张索引表，操作系统持有指向各个索引表的指针

进程上下文切换

进程切换是让处于运行态的进程中断运行，让出处理器，这时要做一次进程上下文切换、即保存老进程的上下文而装入被保护了的新进程的上下文，以便新进程运行。

中断运行的三种情况：
+ 被阻塞的高优先级进程变为就绪态
+ 运行进程的时间片耗尽
+ 运行进程执行阻塞型I/O指令（变为准备态）

当然，这些情况触发也不一定就会立即进行进程调度和切换，例外情况：
+ 内核正在处理中断的过程中
+ 进程运行在内核临界区中
+ 内核处在需要屏蔽中断的原子操作过程中

进程上下文切换的步骤：
1. 保存被中断进程的处理器现场信息
2. 修改被中断进程的PCB有关信息，如进程状态等
3. 把被中断进程的PSB加入有关队列
4. 选择下一个占有处理器运行的进程
5. 修改被选中进程的PSB的有关信息
6. 根据被选中进程设置操作系统用到的地址转换和存储保护信息
7. 根据被选中进程恢复处理器现场

当中断/系统调用发生时，暂时中断正在执行的用户进程，把进程从用户状态转换到内核状态，去执行操作系统服务程序以获得服务，这就是一次处理器状态转换。

处理器状态转换的步骤：
1. 保存被中断进程的处理器现场信息；
2. 处理器从用户态转换到核心态，以便执行服务程序或中断处理程序；
3. 如果处理中断，可根据规定的中断级设置中断屏蔽位；
4. 根据系统调用号或中断号，从系统调用表或中断入口表找到服务程序或中断处理程序地址。

进程管理原语

这个不属于进程上下文切换中的内容，思维导图里面是我弄错了。

进程管理原语用于进程控制，有：
+ 进程创建
+ 进程撤销
+ 进程阻塞
+ 进程唤醒
+ 进程挂起
+ 进程激活

进程创建的详细步骤：
1. 在进程列表中增加一项，从PCB池中申请一个空闲PCB，为新进程分配惟一的进程标识符
2. 为新进程的进程映像分配地址空间，以便容纳进程实体。进程管理程序确定加载到进程地址空间中的程序
3. 为新进程分配除主存空间外的其他各种所需资源；
4. 初始化PCB，如进程标识符、处理器初始状态、进程优先级等；
5. 把新进程状态置为就绪态，并移入就绪进程队列；
6. 通知操作系统的某些模块，如记账程序、性能监控程序。

linux创建进程/线程可以使用：
+ fork()：父子进程是独立的进程
+ clone()：父子进程允许共享资源
+ vfork()：子进程租用父进程地址空间

进程撤销的详细步骤：
1. 根据撤销进程标识号，从相应队列中找到并移出它
2. 将该进程拥有的资源归还给父进程或操作系统
3. 若该进程拥有子进程，先撤销它的所有子进程，以防它们脱离控制
4. 回收PCB，并归还到PCB池

进程阻塞步骤：
1. 停止进程执行，保存现场信息到PCB
2. 修改进程PCB有关内容，如进程状态由运行态改为等待态等，并把修改状态后的进程移入相应事件的等待队列中
3. 转入进程调度程序去调度其他进程运行

进程唤醒步骤：
1. 从相应的等待队列中移出进程
2. 修改进程PCB的有关信息，如进程状态改为就绪态，并移入就绪队列
3. 若被唤醒进程比当前运行进程优先级高，重新设置调度标志

线程及其实现

线程概念

OS中引入进程的目的是为了使多个程序并发执行，以改善资源使用率和提高系统效率，OS中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。

线程是OS进程中能够独立执行的实体（控制流），是处理器调度和分派的基本单位。线程是进程的组成部分，每个进程内允许包含多个并发执行的实体（控制流），这就是多线程。

线程优点

• 快速线程切换
• 通信易于实现
• 减少管理开销
• 并发程度提高

进程作为系统资源分配和保护的独立单位，不需要频繁地切换，而线程共享进程中的数据，利于通信。

多线程环境

线程组成

1. 线程控制块：线程唯一标识符及线程状态信息(运行态、就绪态、阻塞态和终止态)
2. 线程是一条执行路径，有独立的程序计数器；未运行时保护线程上下文
3. 线程有执行栈和存放局部变量的私用存储空间
4. 可访问所属进程的内存和资源，并与该进程中的其他线程共享这些资源

线程又称轻量进程，线程运行在进程的上下文中,并使用进程的资源和环境。系统调度的基本单位是线程而不是进程,每当创建一个进程时，至少要同时为该进程创建一个线程。

线程状态

线程状态有：运行、就绪、等待和终止，状态转换也类似于进程。

挂起状态对线程是没有意义，如果进程挂起后被对换出主存，则它的所有线程因共享进程的地址空间，也必须全部对换出去。

线程组织

进程中线程多种组织方式：
+ 调度员／工作者模式：一个线程担任调度员，用于分配任务并唤醒工作者，其他线程为工作者。
+ 组模式：各个线程都可以取得并处理工作请求，对特定任务建立相应线程队列（执行不同任务）
+ 流水线模式：线程排成某个次序，前一个线程产生的数据交给下一个线程处理

线程的实现

本节参考：操作系统学习记录之五：多线程实现的混合策略_小小柴的博客-CSDN博客

从实现角度看，线程分成:
+ 用户级线程ULT(如Java ,Informix)。
+ 内核级线程KLT(如OS/2)。
+ 混合式线程(如Solaris)。

内核级线程是内核支持的线程，线程管理工作由内核完成。优点是线程切换速度快、执行效率高。缺点是用户态运行、内核态管理导致系统开销大。

用户级线程是由应用程序所支持的线程实现, 内核意识不到用户级线程的实现。线程管理由应用程序完成。优点：
+ 节省系统模式转换开销和内核的宝贵资源
+ 允许进程按照应用的特定需要选择调度算法
+ 能够运行在任何操作系统上
+ 内核无须做任何改变

缺点：
+ 线程的阻塞将引起整个进程的阻塞
+ 不可能得益于多线程的并发执行

混合式线程：线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用中的多个用户级线程被映射到一些(小于等于用户级线程数目)内核级线程上。该方法将会结合纯粹用户级线程方法和内核级线程方法的优点，同时减少它们的缺点。

处理器调度

调度层次

作业从进入系统成为后备作业开始，直到运行结束退出系统为止，需经历不同级别的调度：

高级调度，又称作业调度、长程调度。任务是选择作业进入内存，控制多道程序的道数。

中级调度，又称平衡调度、中程调度。任务是完成外存和内存中的进程对换工作、转换就绪态和等待态,提高内存利用率和系统吞吐率。

低级调度，又称进程调度/线程调度、短程调度。任务是决定就绪队列中的某个进程/线程获得处理器。

选择调度算法原则

原则就是性能指标，包含：

• 资源利用率：CPU利用率=CPU有效工作时间/CPU总的运行时间。CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间。
• 吞吐率：单位时间内CPU处理作业的个数。
• 公平性：确保每个进程都能获得合理的资源份额，不会出现饥饿现象。
• 响应时间：交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。
• 周转时间：从提交作业开始到作业完成的时间。

作业的管理与调度

作业和进程的关系

作业是任务实体，进程是完成任务的执行实体;没有作业任务，进程无事可干，没有进程，作业任务没法完成。

作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。

作业控制块

多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。

JCB通常是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。

JCB的主要内容包括：
1. 作业情况
2. 资源需求
3. 资源使用情况

批处理作业的调度

1. 选择作业：按照调度算法选择
2. 分配资源
3. 创建进程：被调度时，系统为作业创建进程，并生成PCB及各种进程实体
4. 作业控制：按说明书运行
5. 后续处理：调度程序做好作业撤离和善后工作

低级调度功能和类型

调度程序两项任务： 调度和分派。调度决定就绪态线程竞争使用处理器的次序，分派决定如何时分复用CPU，处理上下文切换。

低级调度的基本类型：第一类称剥夺式，有两种处理器剥夺原则，其一是高优先级进程/线程可剥夺低优先级进程/线程，另一种是当运行进程/线程时间片用完后被剥夺。第二类称非剥夺式，进程/线程开始运行后不再让出处理器

作业调度和低级调度算法：

• 先来先服务算法FCFS

先来先服务是按照作业进入系统后备队列的先后次序来挑选作业，先进入系统的作业优先被挑选进入内存。 它是非剥夺式算法，不利于短作业（短作业的平均周转时间会较长，因为需要等待前面的作业完成）

• 最短作业优先算法SJF

SJF算法以进入系统的作业所要求的CPU时间为标准，总选取估计计算时间最短的作业投入运行。（但是由于这个时间只是估算的，并不能保证实际上一定是最短作业）。它也是非剥夺式算法，缺点是长作业可能出现饥饿现象（一直得不到调度），缺少剥夺机制，对分时实时处理不理想。

• 最高响应比优先算法HRRF

FCFS只考虑等待时间而忽视了作业的计算时间，SJF只考虑用户估计的作业计算时间而忽视了作业等待时间，因而比较片面。HRRF是介于FCFS与SJF之间的折中算法，既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改进了调度性能。

响应比 = 周转时间/处理时间 = 1+已等待时间/估计运行时间

因而这种算法会根据作业已等待的时间和估计运行时间动态调整调度的优先级，短作业容易得到较高响应比，长作业等待时间足够长后，也将获得足够高的响应比，饥饿现象不会发生。

• 优先级调度算法

永远先选取优先级高的，这个优先级可能是用户指定的，也可能是系统根据作业的重要性等信息调整的。

• 最短剩余时间优先算法SRTF

这是一种剥夺式算法，当一个新作业进入就绪状态，如果新作业需要的CPU时间比当前正在执行的作业剩余下来还需的CPU时间短，SRTF强行赶走当前正在执行作业。

• 轮转调度算法RR

轮流使用时间片，剥夺式调度。合适选取时间片的长度很重要，如果时间片太长了就会变成FCFS，如果太短了就会使系统调度开销很大。

• 多级反馈队列调度算法MLFQ

又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。

处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。