操作系统 处理器管理(一)

1. 进程

1.1 为什么要引入进程？

刻画系统的动态性，发挥系统的并发性，提高资源利用率
它能解决系统的“共享性”，正确描述程序的执行状态

1.2 进程定义

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

1.3 特性

• 结构性：由程序段、数据段和进程控制块（PCB)组成
• 共享性：多个不同的进程可以共享相同的程序
• 动态性：进程的实质是进程实体的一次执行过程
• 独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位
• 异步性(制约性)：进程按各自独立的、不可预知的速度向前推进
• 并发性：多个进程同存于内存中，能在一段时间内同时运行。

1.4 状态和转换

1.4.1 三态模型

• 就绪态：进程已经获得除CPU之外的所有资源

• 运行态：进程已获得CPU，正在CPU上运行

• 等待态（阻塞态）：由于发生某事件而暂时无法继续执行时处于的暂停状态

  

引起进程状态转换的具体原因如下：

• 运行态—→等待态：等待使用资源；如等待外设传输；等待人工干预。
• 等待态—→就绪态：资源得到满足；如外设传输结束；人工干预完成。
• 运行态—→就绪态：运行时间片到；出现有更高优先权进程。
• 就绪态—→运行态：CPU 空闲时选择一个就绪进程。

1.4.2 五态模型

新建态对应于进程刚刚被创建的状态。创建一个进程要通过两个步骤，

1. 为一个新进程创建必要的管理信息，
2. 让该进程进入就绪态。此时进程将处于新建态，它并没有被提交执行，而是在等待操作系统完成创建进程的必要操作。需要注意的是，操作系统有时将根据系统性能或主存容量的限制推迟新建态进程的提交

类似地，进程的终止也要通过两个步骤，首先,是等待操作系统进行善后，然后,退出主存。当一个进
程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进
程所终结，它将进入终止态。进入终止态的进程以后不再执行，但依然临时保留在操作系统中等待善后 。
一旦其他进程完成了对终止态进程的信息抽取之后，操作系统将删除该进程。

引起进程状态转换的具体原因如下：

• NULL—→新建态：执行一个程序，创建一个子进程。
• 新建态—→就绪态：当操作系统完成了进程创建的必要操作，并且当前系统的性能和虚拟内存的容量均允许。
• 运行态—→终止态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结。
• 终止态—→NULL：完成善后操作。
• 就绪态—→终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。
• 等待态—→终止态：未在状态转换图中显示，但某些操作系统允许父进程终结子进程。

1.4.3 PCB

进程控制块PCB，是操作系统用于记录和刻划进程状态及有关信息的数据结构
PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息
PCB的作用：使一个在多道程序环境下不能独立运行的程序，成为一个能独立运行的基
本单位。OS是根据PCB来对并发执行的进程进行控制和管理的。

PCB是进程存在的唯一标识。

1.4.4 进程通信

什么是进程通信

进程之间的信息交换，用户通过操作系统提供的一组通信指令高效地传送大量数据而不需关注通信实现方式

为了保证安全，一个进程不能直接访问另一个进程的地址空间。
但是进程之间的信息交换又是必须实现的，操作系统提供了一些方法。

1.4.4.1 共享存储器系统

• 共享数据结构的通信方式
  要求进程公用某些数据结构实现进程间的信息交换。如前篇文章中生产者与消费者模型中的缓冲池就是共享数据结构。缺点是共享数据结构需要由程序员维护并且只适合传递相对少量的数据、速度慢、限制多，是一种低级通信方式。
• 共享存储区的通信方式
  在存储器中划出了一块共享存储区，进程可以通过对共享存储区中数据的读或写实现通信。进程在通信之前，先向系统申请获得共享存储区中的一个分区，并指定该分区的关键字，如果系统已经给其他进程分配了这样的分区，则将该分区的描述符返回给申请者，然后申请者把获得的共享存储区 链接到本进程上。速度更快，是一种高级通信方式。

两个进程对共享空间的访问必须是互斥的

1.4.4.2 管道通信系统

1. 管道只能采用半双工通信，某一时间段内只能实现单向的传输。如果要实现双向同时通信，则需要设置
   两个管道。
2. 各进程要互斥地访问管道。
3. 数据以字符流的形式写入管道，当管道写满时，写进程的write()系统调用将被阻塞，等待读进程将数据
   取走。当读进程将数据全部取走后，管道变空，此时读进程的read()系统调用将被阻塞。
4. 如果没写满，就不允许读。如果没读空，就不允许写。
5. 数据一旦被读出，就从管道中被抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情

1.4.4.3 消息传递系统

消息传递系统是当前应用最为广泛的一种进程间的通信机制，进程之间的数据交换以格式化的消息为单位，程序员直接利用操作系统提供的一组通信命令实现消息的传递。可以根据实现方式的不同分为直接通信方式和间接通信方式

直接通信方式
发送进程利用OS所提供的发送命令，直接把消息发送给目标进程，此时发送进程和接收进程都以显示方式提供对方的标识符。可以用如下两条原语表示：

Send(Receiver, message);  //发送消息，Receiver指定发给哪个进程
Receiver(Sender, message);  //接收消息

接收进程无法事先指定发送进程，Receiver(Sender, message);中的Sender指的是源进程的参数，也是完成通信后的返回值

间接通信方式(信箱通信方式)
间接通信方式指进程之间的通信需要通过作为共享数据结构的实体，该实体用于暂存发送进程发送给目标进程的消息，接收进程则从实体中取出对方发送给自己的消息，通常把这种实体称为信箱。

2. 线程

2.1 什么是线程，为什么要引入线程

线程概念

• 一个可执行程序，定义了初始代码和数据。
• 一个私用地址空间，它是进程可以使用的一组虚拟主存地址。
• 进程执行时所需的系统资源（如文件，信号灯，通信端口等）是由操作系统分配的。
• 若系统支持线程运行，那么每个进程至少有一个执行线程。

进程中能够并发的实体，是进程的组成部分，也是处理器调度和分配的基本单位。允许进程中包含多个线程，这些线程共享进程的主存空间和资源，可以为完成某一项任务而协同工作
线程是进程中的一条执行路径，有自己私用的堆栈和处理机执行环境，共享父进程的主存，单个进程可以创建许多个线程。

线程引入？

操作系统中再引入线程，则是为了减少程序并发执行时所付出的时空开销，使得并发粒度更细、并发性更好。引入线程后不仅是进程之间可以并发，进程内的个线程也可以并发，从而进一步提升了系统的并发度，使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件等）。引入线程后，进程只作为除CPU之外的系统资源的分配单元

引入后变化

2.2 线程属性

• 线程是处理机调度的单位
• 多CPU计算机中，各个线程可占用不同的CPU
• 每个线程都有一个线程ID、线程控制块(TCB)
• 线程也有就绪、阻塞、运行三种基本状态
• 线程几乎不拥有系统资源
• 同一进程的不同线程间共享进程的资源
• 由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
• 同一进程中的线程切换，不会引起进程切换
• 不同进程中的线程切换，会引起进程切换
• 切换同进程内的线程，系统开销很小，切换进程系统开销大

2.3 线程实现方式

用户级线程
用户级线程由应用程序通过线程库实现。所有的线程管理工作都由应用程序负责(包括线程切换)用户级线程中,线程切换可以在用户态下即可完成,无需操作系统干预。在用户看来,是有多个线程。但是在操作系统内核看来,并意识不到线程的存在。(用户级线程对用户不透明,对操作系统透明)
内核级线程
内核线程：操作系统直接支持。管理由操作系统完成。内核在其空间内执行线程创建，调度和管理。内核线程的创建和管理比在用户级创建和管理用户线程要慢，但正是由于内核管理线程，当一个线程执行等待的系统调用时，内核能调度应用程序内的另一个线程去运行。

重点重点重点:操作系统只“看得见”内核级线程,因此只有内核级线程才是处理机分配的单位。例如:一个进程由两个内核级线程,三个用户级线程,在用户看来,这个进程中有三个线程。但即使该进程在一个4核处理机的计算机上运行,也最多只能被分配到两个核,最多只能有两个用户线程并行执行。

2.4 多线程模型

多对一模型：

多对一模型:多个用户及线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。

• 优点:用户级线程的切换在用户空间即可完成,不需要切换到核心态,线程管理的系统开销小,效率高
• 缺点:当一个用户级线程被阻塞后,整个进程都会被阻塞,并发度不高。多个线程不可在多核处理机上并行运行

一对一模型：

一对一模型:一个用户及线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。

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

多对多模型：

多对多模型:n用户及线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程。

克服了多对一模型并发度不高的缺点,又克服了一对一模型中一个用户进程占用太多内核级线程,开销太大的缺点。

3. 调度算法的评价指标

3.1 CPU利用率

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

利用率=忙碌时间/总时间

Eg：某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒， 再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中， CPU利用率、打印机利用率分别是多少？
CPU利用率 =（5+5）/（5+5+5）= 66.66%
打印机利用率 =5/15= 33.33%

3.2 系统吞吐量

对于计算机来说，希望能用尽可能少的时间处理完尽可能多的作业
系统吞吐量：单位时间内完成作业的数量
$$系统吞吐量=\frac{总共完成了多少道作业 }{总共花了多少时间}$$
Eg：某计算机系统处理完10道作业，共花费100秒，则系统吞吐量为？
10/100 = 0.1 道/秒

3.3 等待时间

计算机的用户希望自己的作业尽可能少的等待处理机
等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。

对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进 程也是在被服务的，所以不计入等待时间。
对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。

一个作业总共需要被CPU服务多久，被I/O设备服务多久一般是确定不变的，因此调度算法其实只会 影响作业/进程的等待时间。当然，与前面指标类似，也有“平均等待时间”来评价整体性能。

3.4 响应时间

对于计算机用户来说，会希望自己的提交的请求（比如通过键盘输入了一个调试命令）尽早地开始被系 统服务、回应。
响应时间:指从用户提交请求到首次产生响应所用的时间。

4. 调度算法

4.1 先来先服务(FCFS)

先来先服务是最简单的策略，也成为先进先出FIFO。首先它是一个非抢占的。如字面的意思，它根据进程到达时间决定先运行哪一个进程。

4.2 短作业优先(SJF)

4.3 最短剩余时间优先(SRTN)

注意几个小节：

1. 如果题目中未特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的

2. 很多书上都会说“SJF 调度算法的平均等待时间、平均周转时间最少” 严格来说，这个表述是错误的，不严谨的。之前的例子表明，最短剩余时间优先算法得到的平均等待 时间、平均周转时间还要更少
   应该加上一个条件“在所有进程同时可运行时，采用SJF调度算法的平均等待时间、平均周转时间最 少”; 或者说“在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”;
   如果不加上述前提条件，则应该说“抢占式的短作业/进程优先调度算法（最短剩余时间优先, SRNT算 法）的平均等待时间、平均周转时间最少”

3. 虽然严格来说，SJF的平均等待时间、平均周转时间并不一定最少，但相比于其他算法（如 FCFS）， SJF依然可以获得较少的平均等待时间、平均周转时间

4. 如果选择题中遇到“SJF算法的平均等待时间、平均周转时间最少”的选项，那最好判断其他选项
   不是有很明显的错误，如果没有更合适的选项，那也应该选择该选项

4.4 高响应比优先(HRRN)

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度，该算法是对FCFS调度算法和SJF调度算法的一种综合平衡，同时考虑每个作业的等待时间和估计的运行时间。在每次进行作业调度时，先计算后备作业队列中每个作业的响应比，从中选出响应比最高的作业投入运行。
$$响应比 =\frac{等待时间+要求服务时间 }{要求服务时间}$$

根据公式可知：
当作业的等待时间相同时，则要求服务时间越短，其响应比越高，有利于短作业。
当要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。
对于长作业，作业的响应比可以随等待时间的增加而提高，当其等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。克服了饥饿状态，兼顾了长作业。

算法	思想&规则	可抢占	优点	缺点	考虑到等待时间&运行时间？	会导致饥饿？
FCFS	自己回 忆	非抢占式	公平；实现简单	对短作业不利	等待时间√ 运行时间×	不会
SJF/S PF	自己回 忆	默认为非抢占式， 也有SJF的抢占式 版本最短剩余时间 优先算法（SRTN)	“最短的”平均等待/周转时间	对长作业不利，可能导致饥饿；难以做到真正的短作业 优先	等待时间× 运行时间√	会
HRRN	自己回 忆	非抢占式	上述两种算法的权衡 折中，综合考虑的等 待时间和运行时间		等待时间√ 运行时间√	不会

注：这几种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但 是不关心“响应时间”，也并不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算
法一般适合用于早期的批处理系统，当然，FCFS算法也常结合其他的算法使用，在现在也扮演着很重要的 角色。而适合用于交互式系统的调度算法将在下个小节介”…

4.5 时间片轮转法（RR)

对于轮转法，最重要的是时间片的长度。轮转算法以一个周期（q）产生中断，当中断发生时，当前运行的程序置于就绪队列（队尾）中，然后基于FCFS选择下一个就绪作业运行。

• 0时刻（P1(5)):0时刻只有P1到达就绪队列，让P1上处理机运行一个时间片
• 2时刻（P2(4) →P1(3)):2时刻P2到达就绪队列，P1运行完一个时间片，被剥夺处理机，重新放到队尾。
  此时P2排在队头，因此让P2上处理机。（注意：2时刻，P1下处理机，同一时刻新进程P2到达，如果在题目中遇到这种情况，默认新到达的进程先进入就绪队列)
• 4时刻（P1(3) → P3(1) → P2(2)):4时刻，P3到达，先插到就绪队尾，紧接着，P2下处理机也插到队尾
• 5时刻（P3(1) → P2(2) → P4(6)):5时刻，P4到达插到就绪队尾（注意：由于P1的时间片还没用完，因此
  暂时不调度。另外，此时P1处于运行态，并不在就绪队列中)
• 6时刻（P3(1) → P2(2) → P4(6) → P1(1)):6时刻，P1时间片用完，下处理机，重新放回就绪队尾，发生调度
• 7时刻（P2(2) → P4(6) → P1(1)）：虽然P3的时间片没用完，但是由于P3只需运行1个单位的时间，运行
  完了会主动放弃处理机，因此也会发生调度。队头进程P2上处理机。
• 9时刻（P4(6) → P1(1)）：进程P2时间片用完，并刚好运行完，发生调度，P4上处理机
• 11时刻（P1(1) → P4(4)）：P4时间片用完，重新回到就绪队列。P1上处理机
• 12时刻（P4(4))：P1运行完，主动放弃处理机，此时就绪队列中只剩P4，P4上处理机
• 14时刻（)：就绪队列为空，因此让P4接着运行一个时间片。
• 16时刻：所有进程运行结束

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

4.5 优先级调度算法

非抢占式优先级调度算法

抢占式优先级调度

补充：
就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级 高的进程排在更靠近队头的位置 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种
静态优先级：创建进程时确定，之后一直不变。 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级。

通常：
系统进程优先级高于用户进程
前台进程优先级高于后台进程
操作系统更偏好 I/O型进程（或称 I/O繁忙型进程）
注：与I/O型进程相对的是计算型进程（或称 CPU繁忙型进程）

4.6 多级反馈队列

1. 在采用 FB 的系统中，设置了多个不同优先级的就绪队列，并赋予各个队列大小不同的时间片，使优先级越高的时间片越小。
2. 新就绪的进程总是进入最高优先级队列的队尾，并按 FCFS
   原则等待调度；当轮到该进程执行时，若它能在规定的时间片内完成，便可准备撤离系统，否则将他转入第二级队列末尾，再同样按 FCFS原则等待调度；如果它在第二级队列上运行一个时间片后仍未完成，再依次将它转入第三级队列，……，如此下去，当一个长作业从第一级队列降到最后一级队列时，便在该队列中采取 RR 算法运行。
3. 系统总是调度第一级队列中的进程执行，仅当第一级队列空时，才调度第二级上队列上的进程执行。以此类推，仅当第 1~（i -1）级队列空时，才调度第 i 级队列上的程序执行。

算法	思想&规则	可抢占	优点	缺点	会导致饥饿？	补充
时间片轮转法		抢占式	公平，适用于分时操作系统	平凡切换有开销，不区分优先级	不会
优先级调度		有抢占式的也有非抢占式的	区分优先级，是用于实时操作系统	可能导致饥饿	会
多级反馈队列		抢占式	平衡优秀	一般不说有缺点，可能会导致饥饿	会

注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括
分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也 能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈
队列调度算法）