进程的概念

进程与程序的区别

• 程序是静态的，存放在磁盘中的一系列的指令集合。
• 进程是动态的，是程序的一次执行过程。同一个程序多次执行会对应多个进程。

进程的组成

进程控制块PCB🌟

进程控制块(Process Control Block)是一个数据结构，保存操作系统对进程管理所需的信息。具体有：

• 进程描述信息：可以让操作系统区分各个进程
  • 进程标识符PID：当进程被创建时，操作系统会为该进程分配一个唯一的、不重复的ID —— PID(Process ID，进程ID)
  • 用户标识符UID：进程所属用户ID
• 进程控制和管理信息：可用于实现操作系统对进程的控制、调度
  • 进程当前状态：就绪态/阻塞态/运行态等
  • 进程的运行情况：CPU、磁盘、网络流量使用情况统计等
• 资源分配清单：可用于实现操作系统对资源的管理
  • 进程正在使用哪些文件
  • 给进程分配了多少内存，正在使用哪些内存区域
  • 进程正在使用哪些I/O设备
• 处理机相关信息：可用于实现操作系统对进程的切换
  • 各个寄存器的值：PSW(程序状态字寄存器)、PC(指令寄存器)、通用寄存器等

PCB是进程存在的唯一标志，当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB。

程序段

内存中存储程序的指令序列的区域

数据段

程序在运行过程中产生和使用的各种数据(如：程序中定义的变量)在内存中的存储区域

程序的运行过程

• 首先，将该程序从硬盘调入内存中，与此同时，操作系统会为该程序的运行创建一个相对应的进程，也就是创建相应的PCB；
• 其次，组成该程序的一系列指令序列也需要读入内存，这一系列指令序列在内存中的存放区域被称为程序段。该程序在运行过程中产生和使用的数据在内存中的存放区域被称为数据段；
• 最后，CPU从程序段中一条条的取出指令来执行。

小结

• PCB是给操作系统用的。
• 程序段、数据段是给进程自己用的。
• 进程实体(进程映象)是进程在动态运行过程中某一时刻的快照，能够反映进程在某一时刻的状态
• 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• PCB、程序段、数据段三部分组成进程实体(进程映象)
• 如无特别说明，进程的组成就指进程实体的组成

进程的特征

程序是静态的，进程是动态的，相比于程序，进程拥有以下特征：

• 动态性：是进程最基本的特征。进程是程序的一次执行过程，是动态地产生、变化和消亡的
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能运行的、独立获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制”来解决异步问题

进程的状态及转换

进程的状态及转换🌟

• 创建态：进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB
• 就绪态：当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件，但由于没有空闲CPU，就暂时不能运行
• 运行态：如果一个进程此时在CPU上运行，那么这个进程处于“运行态”。CPU会执行该进程对应的程序(执行指令序列)
• 阻塞态：在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程离开CPU回到内存，并让它进入“阻塞态” 。当CPU空闲时，又会选择另一个“就绪态”进程上CPU运行
• 终止态：一个进程可以执行 exit 系统调用，请求操作系统终止该进程。此时该进程会进入“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了

进程的组织

连接方式

• 按照进程状态将PCB分为多个队列
• 操作系统持有指向各个队列的指针

索引方式

• 根据进程状态的不同建立索引表
• 操作系统持有指向各个索引表的指针

进程控制

基本概念

什么是进程控制

进程控制的主要功能是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换等功能。

简而言之，进程控制就是要实现进程状态转换

如何实现进程控制🌟

• 进程控制用"原语"实现。
• 原语是一种特殊的程序，它的执行具有原子性。也就是说，这段程序的运行必须一气呵成，不可中断。

如果进程控制不能“一气呵成”，就有可能导致操作系 统中的某些关键数据结构信息不统一的情况， 这会影响操作系统进行别的管理工作。

【例】假设PCB中的变量 state 表示进程当前所处状态，1表示就绪态，2表示阻塞态

假设此时进程2等待的事件发生，则操作系统中，负责进程控制的内核程序至少需要做这样两件事：

1. 将PCB2的 state 设为 1
2. 将PCB2从阻塞队列放到就绪队列

如果进程控制不能一气呵成，当CPU完成了第一步后收到中断信号，转而去执行其他指令；此时PCB2的state=1，但是它却未被放在就绪队列中。

如何实现原语的原子性

原语的执行具有原子性，即执行过程只能一气呵成，期间不允许被中断。

用 “关中断指令”和“开中断指令”这两个特权指令可以实现原语的原子性。

• 正常情况下，CPU每执行完一条指令都会检查是否有中断信号。
• 当CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。
• 这样，关中断和开中断之间的这些指令序列就不可被中断，实现了“原子性”

进程控制相关的原语

进程的创建

• 作业：一个具体的任务
• 用户向系统提交一个作业=用户让操作系统启动一个程序(来处理一个具体的任务)
• 作业调度：按一定的原则将程序从外存调入内存，并创建进程

进程的终止

进程的阻塞和唤醒

进程的切换

• CPU中的寄存器是进程间共用的，因此在进程切换时需要先在PCB中保存这个进程的运行环境(保存一些必要的寄存器信息)。比如：PSW(程序状态字寄存器)、PC(程序计数器)存放下一条指令的地址、通用寄存器中的值。
• 当原来的进程再次投入运行时，可以通过它的PCB恢复它的运行环境

小结

进程控制会导致进程状态的转换。无论哪个进程控制原语，要做的无非三类事情：

• 更新PCB中的信息
  • 所有的进程控制原语一定都会修改进程状态标志
  • 剥夺当前运行进程的CPU使用权必然需要保存其运行环境
  • 某进程开始运行前必然要恢复期运行环境
• 将PCB插入合适的队列
• 分配/回收资源

线程

线程的引入

在未引入进程之前，系统中各个程序只能串行执行。在引入进程之后，各程序可以并发执行。但进程是程序的一次执行。同一程序的不同功能仍不能并发执行。例如QQ的视频、文字聊天、传送文件不能同时进行。

• 有的进程可能需要“同时”做很多事，而传统的进程只能串行地执行一系列程序。为此，引入了“线程”，来增加并发度。
• 引入线程之前，进程是程序执行流的最小单位，CPU并发的执行各个进程；引入线程后，线程成为了程序执行流的最小单位，CPU并发的执行各个线程。

引入线程后的变化

进程是资源分配的基本单位，线程是调度的基本单位。

线程的属性

线程的实现方式

用户级线程

用户级线程（User-Level Thread, ULT）

• 早期操作系统不支持线程，当时的"线程"是在由程序员写的线程库来实现的，线程库创建了逻辑上的线程。在操作系统的视角中，并没有线程这一概念。

• 上图中由于while循环的执行速度非常快且i不断在0，1，2之间切换，所以三段if代码逻辑可以看作三个并发执行的线程，while循环就是一个最简单的"线程库"。

• 很多编程语言都提供了强大的线程库(用户级线程)，可以实现线程的创建、销毁、调度等功能。

• 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责（包括线程切换）

• 用户级线程中，线程切换在用户态下即可完成，无需操作系统干预。

• 在用户看来是有多个线程的，但是操作系统内核意识不到线程的存在。“用户级线程”就是“从用户视角看能看到的线程”

• 优缺点

  • 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

  • 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行。

内核级线程

内核级线程（Kernel-Level Thread, KLT, 又称“内核支持的线程”）

• 内核级线程是由操作系统支持的线程。大多数现代操作系统都实现了内核级线程，如Windows、Linux等

• 内核级线程的管理工作由操作系统内核完成。

• 线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。

• 操作系统会为每个内核级线程建立相应的 TCB(Thread Control Block，线程控制块)，通过TCB对线程进行管理。“内核级线程”就是“从操作系统内核视角看能看到的线程”

• 优缺点

  • 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行。
  • 缺点：一个用户进程会占用多个内核级线程， 线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。

多线程模型

在支持内核级线程的系统中，根据用户级线程和内核级线程的映射关系，可以划分为几种多线程模型

一对一模型

多对一模型

多对多模型

小结

处理器调度

基本概念

当有一堆任务要处理，但由于资源有限，这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序，这就是“调度”研究的问题

三个层次🌟

高级调度(作业调度)

• 作业：一个具体的任务
• 用户向系统提交一个作业 ≈ 用户让操作系统启动一个程序(来处理一个具体的任务）
• 内存空间有限，有时无法将用户提交的作业全部放入内存
• 高级调度(作业调度)：按一定的原则从外存的作业后备队列中挑选一个作业调入内存，并创建进程。每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。

中级调度(内存调度)

• 内存不够时，可将某些进程的数据调出内存。等内存空闲或者进程需要运行时再重新调入内存。
• 暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列
• 中级调度(内存调度)：按照某种策略决定将哪个处于挂起状态的进程重新调入内存。 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

低级调度(进程调度)

• 低级调度(进程调度/处理器调度)：按照某种策略从就绪队列中选取一个进程，将处理器分配给它。
• 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。 进程调度的频率很高，一般几十毫秒一次。

三层调度的联系和对比

进程的挂起态与七状态模型

• 五状态模型→七状态模型
• 暂时调到外存等待的进程状态为挂起状态(挂起态，suspend)
• 挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
• “挂起”和“阻塞”的区别
  • 两种状态都是暂时不能获得CPU的服务，
  • 但挂起态是将进程映像调到外存去了，而阻塞态下进程映像还在内存中。
• 有的操作系统会把就绪挂起、阻塞挂起分为两个挂起队列，甚至会根据阻塞原因不同再把阻塞挂起进程进一步细分为多个队列。

小结

进程调度

进程调度(低级调度)：按照某种算法从就绪队列中选择一个进程为其分配处理机。

进程调度的时机

• 有的系统中，只允许进程主动放弃处理机
• 有的系统中，进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机(被动放弃)

• 进程在操作系统内核程序临界区中不能进行调度与切换。但是进程在普通临界区中是可以进行调度、切换的
• 临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥地访问临界资源。
• 临界区：访问临界资源的那段代码。
• 内核程序临界区一般是用来访问某种内核数据结构的。例如：进程的就绪队列(由各就绪进程的PCB组成)
• 内核程序临界区访问的临界资源如果不尽快释放的话，极有可能影响到操作系统内核的其他管理工作。因此在访问内核程序临界区期间不能进行调度与切换。
• 普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。因此在访问普通临界区时可以进行调度与切换。

进程的切换与过程

“狭义的进程调度”与“进程切换”的区别：

• 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程， 也可能是另一个进程，后一种情况就需要进程切换)
• 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
• 广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了：

• 对原来运行进程各种数据的保存
• 对新的进程各种数据的恢复(如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)

进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低， 使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

进程调度的方式

• 非剥夺调度方式，又称非抢占方式。即只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
  • 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
• 剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
  • 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能(通过时钟中断)。适合于分时操作系统、实时操作系统

小结

调度算法的评价指标

CPU利用率

由于早期的CPU造价极其昂贵，因此人们会希望让CPU尽可能多地工作

CPU利用率：指CPU “忙碌”的时间占总时间的比例。

$$利用率=\frac{忙碌的时间}{总时间}$$

【例】某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中，CPU利用率、打印机利用率分别是多少？

CPU利用率 = 5+5/(5+5+5) = 66.66%

打印机利用率 = 5/15 = 33.33%

通常会考察多道程序并发执行的情况，可以用“甘特图”来辅助计算

系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业

系统吞吐量：单位时间内完成作业的数量

$$系统吞吐量=\frac{总共完成了多少道作业}{总共花了多少时间}$$

【例】某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？

10/100 = 0.1 道/秒

周转时间

对于计算机的用户来说，他很关心自己的作业从提交到完成花了多少时间。

周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。它包括四个部分：

• 作业在外存后备队列上等待作业调度(高级调度)的时间
• 进程在就绪队列上等待进程调度(低级调度)的时间
• 进程在CPU上执行的时间
• 进程等待I/O操作完成的时间

后三项在一个作业的整个处理过程中，可能发生多次

$$(作业)周转时间 = 作业完成时间 – 作业提交时间$$

对于用户来说，更关心自己的单个作业的周转时间

$$平均周转时间=\frac{各作业周转时间之和}{作业数}$$

对于操作系统来说，更关心系统的整体表现，因此更关心所有作业周转时间的平均值

有的作业运行时间短，有的作业运行时间长，因此在周转时间(等待时间+运行时间)相同的情况下，运行时间长的作业，用户感觉更好。由此对周转时间概念做出扩展：

$$带权周转时间=\frac{作业周转时间}{作业实际运行的时间}=\frac{作业完成时间-作业提交时间}{作业实际运行的时间}$$

带权周转时间必然 ≥ 1

带权周转时间与周转时间都是越小越好

$$平均带权周转时间=\frac{各作业带权周转时间之和}{作业数}$$

对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高。

对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。

等待时间

计算机的用户希望自己的作业尽可能少的等待处理器

等待时间，指进程/作业处于等待处理器状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。

对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

响应时间

对于计算机用户来说，会希望自己提交的请求(比如通过键盘输入了一个调试命令)尽早地开始被系统服务、回应。

响应时间，指从用户提交请求到首次产生响应所用的时间。

小结

调度算法🌟

先来先服务(FCFS)

【例题】

短作业优先(SJF)

【例题1】非抢占式短作业优先算法SJF

【例题2】抢占式短作业优先算法，又称"最短剩余时间优先算法"

一些小细节

高响应比优先(HRRN)

【例题】

小结

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

【例题1】时间片大小为2

时间片轮转调度算法常用于分时操作系统，更注重“响应时间”，因而此处不计算周转时间

【例题2】时间片大小为5

若按照先来先服务调度算法的结果(下图中第二行)

• 如果时间片太大，使得每个进程都可以在一个时间片内就完成，则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
• 另一方面，进程调度、切换是有时间代价的(保存、恢复运行环境)，因此如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的时间比例减少。可见时间片也不能太小。

优先级调度算法

【例题1】非抢占式的优先级调度算法

【例题2】抢占式的优先级调度算法

多级反馈队列调度算法

【例题】

小结