操作系统 处理器管理

处理器管理

处理器管理是操作系统的中药组成部分之一，负责管理、调度和分派处理器资源以及控制程序的执行。处理器管理主要涉及两部分的内容：处理器资源的分配和运行的程序（进程）调度。

处理器基础知识

  • 处理器主要由控制器、运算器、寄存器、中断装置以及高速缓存（Cache）等组成

  • 处理器的寄存器包括通用寄存器、数据寄存器、地址寄存器和控制寄存器等多个寄存器

  • 机器指令（简称指令）是指示计算机执行某些操作的命令，一台计算机所有指令的集合称为指令集。

    • 按照指令复杂程度和指令数量可以将计算机分为复杂指令集计算机（Complex Instruction Set Computer，CISC）和精简指令集计算机（Reduced Instruction Set Computer，RISC）两种
    • 指令按照使用者可以分为特权指令（仅供操作系统内核使用的指令）和非特权指令两种

  • 为了防止普通用户使用特权指令，处理器需要区分当前运行的代码属于操作系统内核还是属于普通程序，所以处理器具有不同的状态，简单来说分为管理状态（也称特权状态、系统状态、特态、管态）和用户状态（也称目标状态、用户模式、常态、目态）两种。管理状态时CPU能够执行指令集支持的所有指令，而在用户状态时CPU只能执行非特权指令。

    • 处理器状态的转换通常通过中断（包括外部设备中断、应用程序的系统调用以及程序运行过程中发生的错误等）来完成

  • 程序状态字（Program Status Word，PSW）用于存储不同程序的处理器工作状态，每个处理器均有一组与程序执行相关的寄存器，这组寄存器就是当前该处理器上所运行程序的程序状态字。程序状态字通常包括程序的基本状态（例如下一条指令地址、状态位、条件码等），中断码和中断屏蔽位。

    借助程序状态字以及其他信息，操作系统能够记录当前并发运行的多个程序的状态，从而能够在这些程序之间无缝切换

中断技术

中断是用来向CPU报告某设备已完成某项操作的手段，它是并发程序的基础。当中断到来时，CPU将会暂停正在运行的程序，转而执行该中断的相关处理程序。中断的处理需要由硬件（中断装置，用于监测中断并在中断到来时保护现场、跳转到中断处理程序）和软件（中断处理程序）相互配合完成。

中断可以按照性质分为以下两种：

  • 强迫性中断，例如发生机器故障、程序运行发生错误、外部设备中断等
  • 自愿性中断，例如程序主动使用系统调用

中断可以按照中断信号的来源分为以下两种：

  • 外中断（中断），中断信号来自外部设备，例如时钟中断（由定时器发出）、输入输出设备中断等
    • 外中断与现行指令无关，通常可以被屏蔽、可以嵌套，只有在两条指令之间才能响应中断
  • 内中断（异常），中断信号来自机器自身，例如非法指令、缺页错误、算术操作溢出、校验错等
    • 内中断由现行指令引发，可以在一个指令周期被处理，通常不可屏蔽（不处理该中断程序无法继续运行）、不可嵌套。可以细分为出错（例如缺页错误，处理完成后回到出错指令处执行）和陷入（例如系统调用，处理完成后执行陷入指令的下一条指令）

硬件如何找到中断处理程序——通过中断向量表（Interrupt VectorTable，IVT）

中断事件处理的一般过程

  • Step 1：发现中断源（由硬件完成）
  • Step 2：初步保护现场（由硬件完成）
  • Step 3：转到中断处理程序（软件）执行
    • Step 3.1：进一步保护现场
    • Step 3.2：执行中断处理相关代码
    • Step 3.3：恢复部分现场（由软件保护的现场）
  • Step 4：恢复现场（硬件完成，恢复由硬件保护的现场）

中断的优先级

在同时有多个中断发生时，中断装置需要按照一定的顺序对其做出响应，这个顺序由优先级决定。优先级通常按照对计算机影响的严重程度设定，在处理高优先级的中断时，可以屏蔽低优先级的中断。

在中断处理过程中，如果又产生了新的中断，有如下几种不同的处理策略：

  • 串行处理
    • 在处理中断时不管其他中断，中断按照串行顺序逐个被处理
    • 可以通过关中断实现
  • 嵌套处理
    • 先暂停当前的中断处理过程，转而处理更高优先级的中断
  • 即时处理
    • 主要针对中断处理程序执行过程中发生的程序性中断，如果不处理，中断处理程序无法继续运行

信号机制

一种模拟硬件中断的进程间简单通信机制（软件中断），例如：Ctrl+C结束程序运行是由内核向进程发送了SIGINT信号。

  • 内核向进程（进程发生异常，内核向其通知）
  • 进程向进程（进程间通信，发送某个事件）
POSIX定义的信号类型

SIGABRT · SIGALRM · SIGFPE · SIGHUP · SIGILL · SIGINT · SIGKILL · SIGPIPE · SIGQUIT · SIGSEGV · SIGTERM · SIGUSR1 · SIGUSR2 · SIGCHLD · SIGCONT · SIGSTOP· SIGTSTP· SIGTTIN· SIGTTOU· SIGBUS · SIGPOLL· SIGPROF· SIGSYS · SIGTRAP· SIGURG· SIGVTALRM· SIGXCPUSIGXFSZ

进程

进程（Process）是一个可并发执行的具有独立功能的程序关于某个数据集合的一次执行过程，也是操作系统进行资源分配和保护的基本单位。

从理论角度来看，进程是对正在运行的程序活动规律的抽象。从实现角度来看，进程是刻画程序运行状态和系统动态变化的一种数据结构。

通过进程可以发挥系统的并发性，提高资源利用率，换言之，进程是并发程序设计的工具。此外，进程能够解决同一段代码的共享性的问题，它能够正确描述程序的执行状态（标识程序的多次运行）。

进程的状态和转换

进程的五态模型如下所示（忽略这糟糕的排版），

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
┌───────────────┐
│               │
│     新建态     │
│               │
└──────┬────────┘
       │
       │ 分配资源、加载程序
       │
       ▼
┌───────────────┐ 调度程序选中   ┌────────────────┐         ┌─────────────────┐
│               ├─────────────►│                │ 运行完成 │                 │
│     就绪态     │              │     运行态      ├────────►│     终止态       │
│               │◄─────────────┤                │         │                 │
└───────────────┘     落选      └───────┬────────┘         └─────────────────┘
       ▲                               │
       │                               │出现等待事件（例如Sleep）
       │                               │
       │                               ▼
       │                       ┌─────────────────┐
       │                       │                 │
       └───────────────────────┤      等待态      │
        等待结束                │                 │
                               └─────────────────┘

进程挂起是指将进程对换到外部存储器（例如：磁盘）上，释放器占有的系统资源（例如：内存），排除在进程调度之外。这样做的目的是提高系统资源利用率，减轻系统负载或者用于调试程序。

具有挂起状态的状态转换模型如下所示（忽略这糟糕的排版），

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
┌───────────────┐        ┌────────────────┐
│               │  提交   │                │            等待事件结束
│     新建态     ├───────►│    挂起就绪态    │◄──────────────────────────────────────────┐
│               │        │                │                                           │
└──────┬────────┘        └────┬───────────┘                                           │
       │          解除挂起      │  ▲    ▲                                               │
  提交  │  ┌───────────────────┘  │    │                                               │
       │  │                      │    │                                               │
       │  │  ┌───────────────────┘    │ 挂起                                           │
       ▼  ▼  │    挂起                 │                                               │
┌────────────┴──┐              ┌──────┴─────────┐         ┌─────────────────┐         │
│               ├─────────────►│                │         │                 │         │
│    就绪态      │              │     运行态      ├────────►│      终止态      │         │
│               │◄─────────────┤                │         │                 │         │
└───────────────┘              └───────┬────────┘         └─────────────────┘         │
       ▲                               │                                              │
       │                               │ 等待事件                                      │
       │                               │                                              │
       │                               ▼                                              │
       │                       ┌─────────────────┐  挂起     ┌───────────────┐         │
       │                       │                 ├────────► │               │         │
       └───────────────────────┤      等待态      │          │    挂起等待态   ├─────────┘
           等待事件结束          │                 │◄─────────┤               │
                               └─────────────────┘ 解除挂起  └───────────────┘

进程的结构

进程的内存映像包括进程控制块（Process Control Block，PCB）、核心堆栈（供内核态使用）、用户堆栈（供用户态使用）以及用户私有地址空间（代码段、数据段等）和共享地址空间。

进程的物理实体和支持进程运行的环境合称为进程上下文，因此进程的上下文切换就是进程的切换。它包括：

  • 用户级上下文
    • 程序段、数据段、用户堆栈、共享存储区等
  • 寄存器上下文
    • 程序状态字（PSW）寄存器、栈指针寄存器、通用寄存器等
  • 系统级上下文
    • 进程控制块、主存管理信息（如页表、段表等）、核心堆栈

每个进程有且仅有一个进程控制块，它存储着进程标识信息、进程现场信息（通用寄存器、PSW寄存器等寄存器的值）以及进程控制信息（调度信息、通信信息、资源信息等）。

一个进程控制块刻画了一个进程的运行状态，而进程控制块的集合则刻画了一个操作系统当前的运行状态。进程控制块的使用和修改只能由操作系统内核来完成。

进程队列将同一状态（例如：等待队列、就绪队列）的所有进程控制块链接在一起，以便于操作系统进行统一的管理和调度。

进程控制

进程创建

常见原语：fork，clone，……

  • fork：用于创建子进程，创建出的进程与原进程是父子进程关系
  • clone：用于创建进程，创建出的进程与原进程是对等关系

创建过程：

  • 申请PCB（进程控制块）
  • 分配进程映像空间
  • 分配资源
  • 将进程内容装入分配空间
  • 初始化PCB，分配唯一标识
  • 加入就绪队列或投入运行
  • 通知操作系统其他模块

进程阻塞与唤醒

常见原语（阻塞）：wait，waitpid，sleep，……

进程阻塞过程：

  • 保存现场到PCB
  • 修改进程状态（运行态->等待态）
  • 将PCB加入相应的等待队列
  • 转到进程调度程序，调度执行其他进程

进程唤醒过程：

  • 从相应的等待队列中取出PCB
  • 修改进程状态（等待态->就绪态）
  • 将PCB加入就绪队列
  • 转到进程调度程序，或继续执行原进程

进程终止

常见原语：exit

终止过程：

  • 根据进程标识找到对应的PCB
  • 将该进程资源归还给父进程或操作系统
  • 若有子进程，则终止所有子（孙）进程
  • 将PCB移出队列，将PCB归还给PCB池

线程

从上面的讨论可以发现，以进程为单位的并发程序效率不高，存在着进程时空开销大（调度和进程切换时间长，空间占用大），通信代价高（需要借助操作系统），进程间并发粒度大等问题。

为了解决这些问题，将进程独立分配资源和独立分派调度这两项功能分离出来，就产生了线程（Thread）的概念。一个进程的多个线程共享同一个用户地址空间，但同时每个进程拥有自己独立的堆栈空间和指令执行序列，这样，同一进程的不同线程既可以访问相同的共享变量（存储于进程的数据空间中），又能够互不干扰地各自执行指令（拥有独立的堆栈和寄存器）。

在多线程环境下，进程是操作系统中进行保护和资源分配的基本单位，而线程是处理器调度和分配的基本单位，同一进程的所有线程共享进程获得的主存空间和资源。

线程的管理与实现

基本的线程管理原语：

  • thread_create 创建线程
  • thread_join 等待线程
  • thread_yield 出让（主动让出线程自身的执行机会）
  • thread_exit 终止线程

线程的实现方式分为内核级线程，用户级线程和前两者的混合实现，如下所示，

线程的三种实现

  • 内核级线程
    • 由内核管理的线程
    • 优点
      • 能够在多个处理器上同时执行多个线程
      • 某个进程中一个线程被阻塞，不会影响其他线程的运行
    • 缺点
      • 线程间切换代价高，需要涉及两次模式切换（用户态->内核态 内核态->用户态）
  • 用户级实现
    • 用户线程的建立、同步、销毁、调度完全在用户空间完成，不需要内核的帮助
    • 优点
      • 线程切换不涉及模式切换，代价小
      • 调度算法选择灵活（由进程自行调度）
    • 缺点
      • 同一进程的不同线程不能同时在多个处理器上运行
      • 一个线程的阻塞将导致整个进程的阻塞
      • 非抢占式调度
    • 改进机制
      • upcall机制
      • 非阻塞系统调用，增加select系统调用
  • 混合实现
    • 例如将若干个用户线程绑定到一个内核线程上
    • 设计得当，可结合前两者的优点
    • 设计不当，将产生更差的效果

内核提供一组虚拟处理器(LWP)给应用程序，应用程序可调度用户线程到一个可用的虚拟处理器上。内核需要告知用户该线程的运行状态，这个过程被称为upcall。详见https://blog.csdn.net/weixin_42250655/article/details/103571820

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

  • 易于实现多个活动间的通信（共享变量）
  • 更低的管理开销
  • I/O密集型应用能获得更好的性能
  • 能更好地利用多（核）处理器，加快程序执行

处理器调度

处理器调度的主要内容是：

  • 挑选作业进入内存
  • 在进程（线程）之间分配处理器时间

处理器调度可以分为：

  • 高级调度（作业调度、长程调度），为提交的作业分配资源，决定作业是否进入主存（即决定提交的作业置为就绪态还是挂起就绪态）
  • 中级调度（平衡负载调度、中程调度），决定哪些作业（进程）留在主存中，控制外存和内存的对换（例如，挂起->解除挂起）
  • 低级调度（进程/线程调度、短程调度），决定进程/线程是否占用处理器执行（例如，就绪->运行）

高级调度

在多道批处理系统中，高级调度的工作：

  • 后备作业->进程
  • 作业准备->启动->善后工作

在分时系统中，高级调度的工作：

  • 是否接受一个终端用户的连接
  • 交互作业能否被接纳，并创建进程

中级调度

  • 控制主存储器中容纳的进程数
  • 保证在合理数目的进程，竞争处理器和相关资源

挂起的进程不参与低级调度

低级调度

存在两种调度方式：

  • 抢占方式（剥夺方式）
    • 优先级抢占
    • 限时抢占
  • 非抢占方式（非剥夺方式）

抢占方式调度的开销通常大于非抢占方式，但是可以避免一个进程或线程长时间独占处理器。

调度算法

任何层次的处理器调度均由操作系统相应的调度程序实施，调度程序所使用的算法，被称为调度算法。

调度算法考虑的主要因素

  • 资源利用率 -> 不要让CPU空转
    • CPU有效工作时间/CPU总运行时间
  • 响应时间
    • 从作业提交到收到回应的时间
  • 周转时间
    • 作业提交到作业完成的时间
    • 平均周转时间、平均带权周转时间
  • 吞吐率
    • 单位时间处理的作业数
  • 公平性
    • 确保每个进程获得合理的资源份额

典型高级调度算法

先来先服务 First-Come First-Served FCFS

按照作业进入系统的作业后备队列的先后次序挑选作业，先进入系统的作业优先被选择

  • 优点
    • 实现简单
  • 缺点
    • 不利于短作业而优待长作业（先到达的长作业周转时间短于后到达的短作业）
    • 效率低

最短作业优先算法 SJF

以进入系统的作业所要求的CPU时间长短为标准，总是挑选时间最短的作业投入运行

  • 优点
    • 实现简单
    • 效率相对较高
  • 缺点
    • 在实际系统中，往往难以预测作业的CPU时间
    • 长作业等待时间可能会过长（持续有短作业进入系统，长作业将难以得到服务）

最短剩余时间优先 SRTF

每次调度时，总选择预测剩余运行时间最短的作业优先运行

  • 优点
    • 效率相对较高
  • 缺点
    • 调度频繁
    • 剩余运行时间难以预测
    • 长作业等待时间可能过长

响应比最高优先算法 HRRF

响应比=作业周转时间（响应时间）/作业预计计算时间=(作业预计计算时间+作业等待时间)/作业预计计算时间

总是选择响应比最高的作业投入运行，从而防止了作业等待时间过长的“饥饿”现象发生

典型低级调度算法

先来先服务 First-Come First-Served FCFS

非抢占式调度方式，可以使用就绪队列实现先进先出，但是效率不高，不利于I/O频繁操作的进程（一发生I/O就被移至就绪队列队尾，从而需要等待较长时间才能再次执行）

时间片轮转 Round-Robin

抢占式调度方式，基本原理是利用时钟中断轮流执行各进程

  • 分类
    • 基本时间片轮转法，各进程时间片相同
    • 动态时间片轮转法，各进程时间片不同
  • 时间片选取
    • 时间片过长->FCFS
    • 时间片过短->调度频繁，效率不高

优先数调度 Priority Scheduling

抢占（高优先级进程抢占低优先级进程）和非抢占式（低优先级进程无法抢占高优先级进程）调度方式。总是取优先级最大的进程执行

  • 分类
    • 静态优先数
    • 动态优先数
      • 基本原则：一个进程连续占用处理器的时间越长，则其优先数越小；一个进程等待处理器的时间越长，则其优先数越大
      • 计算优先数需要占用较多的CPU时间，为降低调度开销，应选择合适的时机和合适的计算对象
      • 具体细节可以参考早期UNIX调度算法的实现

最短进程优先 Shortest Process First

下次持续执行时间短的进程优先。

  • 下次持续执行时间的估算使用老化（aging）算法，即\(aT_0+(1-a)T_1\)，其中\(a\)为老化系数。

多级反馈队列调度 Multiple Queues

基本思想：将就绪队列分为多级队列，较高的队列分配时间片较短，但是具有较高的优先权占有处理器；较低的队列分配时间片较长，但是占有处理器的优先权较低。同一队列的进程按照先来先服务的原则进行调度。进程的分级可以静态分级也可以动态分级。

保证调度 Guaranteed Scheduling

基本思想：对每个进程做出性能保证，并在调度中尽力实现该保证。例如，在有n个进程时，保证每个进程获得1/n的处理器能力，那么调度时总是优先执行实际获得处理器时间与应得处理器时间差距最大的进程。

彩票调度 Lottery Scheduling

基本思想：为进程发放针对系统资源的“彩票”，当调度程序选择进程时，随机选择一张“彩票”，持有该“彩票”的进程将被选择。这样，进程持有的彩票越多，它被分配系统资源的概率就越大。

实时系统及其调度算法

实时系统的计算正确性不仅取决于计算的逻辑正确性，还取决于产生结果的时间。如果未满足系统的时间约束，则认为系统失效。也就是说，实时系统对响应时间具有特殊要求，在这类系统中，时间是非常关键的因素。

  • 分类
    • 软实时系统：提供统计意义上的实时。例如，有的应用要求系统在95%的情况下都会确保在规定的时间内完成某个动作，而不一定要求100%
    • 硬实时系统：实时性必须达到100%，例如卫星发射系统、核反应堆控制系统等
  • 构成
    • 将程序分为多个进程，每个进程负责处理相应的周期性事件
  • 特点
    • 规模小，进程切换快，处理时间短，能够管理多个高精度计时器

可调度

可调度是指在忽略调度本身所花费CPU时间的前提下，系统能够在各事件规定的响应时间内处理完成这些事件。

对于周期事件，可以使用下面的公式判断系统是否可调度：

  • \(C_1/P_1+C_2/P_2+...+C_m/P_m\le 1\)，其中\(m\)为事件总数，\(C_i\)为某个事件的处理时间，\(P_i\)为事件发生的周期

典型实时调度算法

单比率调度算法（静态）

令进程的优先级与对应事件出现频率成正比，该算法理论上最优

限期调度算法（动态）

进程的就绪队列按照对应事件的截止期限排序

最少裕度调度算法（动态）

裕度=截止时间-(就绪时间+计算时间)，该算法总是选择裕度最小的进程优先执行

操作系统
#OS #调度算法 #CPU #进程
操作系统 处理器管理
https://young-cloud-creator.github.io/os-schedule/
作者
Young Cloud Creator
发布于
2022年6月21日
许可协议