操作系统 - 第二章、进程管理 - 《计算机基础知识》

2.1 进程与线程
2.2 处理机的调度
- 2.2.1 处理机调度的概念与层次
  - 补充知识：进程的挂起态与七状态模型
2.2.2 进程调度的时机、切换与过程、方式
2.2.3 调度算法的评价指标
2.2.4 作业/进程调度算法（FCFS先来先服务、SJF短作业有限、HRRN高响应比优先）
2.2.5 作业/进程调度算法（时间片轮转~、优先级~、多级反馈队列~）
2.3 进程的同步与互斥
2.4 死锁

2.1 进程与线程

2.1.1 进程的定义、特征、组成、组织

程序:就是一个指令序列。
程序段、数据段、PCB（进程控制块）三部分组成了进程实体(进程映像)。一般情况下，我们把进程实体就简称为进程,例如，所谓创建进程，实质上是创建进程实体中的PCB;而撤销进程，实质上是撤销进程实体中的PCB。

PCB是进程存在的唯一标志 !

从不同的角度，进程可以有不同的定义，比较传统典型的定义有:
1.进程是程序的一次执行过程。
2.进程是一个程序及其数据在处理机上顺序执行时所发生的活动。
3.进程是具有独立功能的程序在数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

注:严格来说，进程实体和进程并不一样，进程实体是静态的，进程则是动态的。

进程的组织
在一个系统中，通常有数十、数百乃至数千个PCB。为了能对他们加以有效的管理，应该用适当的方式把这些PCB组织起来。
注:进程的组成讨论的是一个进程内部由哪些部分构成的问题，而进程的组织讨论的是多个进程之间的组织方式问题

进程的组织——链接方式：

进程的组织——索引方式：

进程的特征：

2.1.2 进程的状态与转换

注意:单核处理机环境下，每时刻最多只有一个进程处于运行态。(双核环境下可以同时有两个进程处于运行态)
进程已经拥有了除处理机之外所有需要的资源，一旦获得处理机，即可立即进入运行态开始运行。即:万事俱备，只欠CPU
另外两种状态
操作系统需要完成创建进程。操作系统为该进程分配所需的内存空间等系统资源，并为其创建、初始化PCB (如:为进程分配PID)
进程运行结束(或者由于bug导致进程无法继续执行下去，比如数组越界错误)，需要撤销进程。
操作系统需要完成撤销进程相关的工作。完成将分配给进程的资源回收，撤销进程PCB等工作

进程的状态转换

2.1.3 原语实现对进程的控制

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

如何实现进程控制

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

思考：为何进程控制（状态转换）的过程要“一气呵成”？如果不能“一气呵成”，就有可能导致操作系\统中的某些关键数据结构信息不统一的情况，这会影响操作系统进行别的管理工作。

进程控制相关源语

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

创建原语

撤销原语

阻塞、唤醒原语

切换原语

2.1.4 进程之间的通信

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

基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式。基于存储区的共享：在内存中画出一块共享存储区，数据的形式、存放位置都由进程控制，而不是操作系统。相比之下，这种共享方式速度更快，是一种高级通信方式。

管道通信

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

消息传递
进程间的数据交换以格式化的消息（Message）为单位。进程通过操作系统提供的“发送消息 / 接收消息”两个原语进行数据交换。

2.1.5 线程概念与多线程模型

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

多线程模型

2.2 处理机的调度

2.2.1 处理机调度的概念与层次

在多道程序系统中，进程的数量往往是多于处理机的个数的，这样不可能同时并行地处理各个进程。处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
调度的三个层次：
高级调度（作业调度）

由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定将作业调入内存的顺序。
高级调度（作业调度）。按一定的原则从外存上处于后备队列的作业中挑选一个（或多个）作业，给他们分配内存等必要资源，并建立相应的进程（建立PCB），以使它（们）获得竞争处理机的权利。

高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

中级调度（内存调度）
引入了虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。
这么做的目的是为了提高内存利用率和系统吞吐量。

暂时调到外存等待的进程状态为挂起状态。值得注意的是，PCB并不会一起调到外存，而是会常驻内存。PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程PCB会被放到的挂起队列中。

中级调度（内存调度），就是要决定将哪个处于挂起状态的进程重新调入内存。
一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。

补充知识：进程的挂起态与七状态模型

暂时调到外存等待的进程状态为挂起状态（挂起态，suspend）
挂起态又可以进一步细分为就绪挂起、阻塞挂起两种状态
五状态模型 ——-> 七状态模型

低级调度（进程调度）

低级调度（进程调度），其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
进程调度的频率很高，一般几十毫秒一次。

三层调度的联系、对比

小结

2.2.2 进程调度的时机、切换与过程、方式

总览

进程调度的时机

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

进程的调度方式

非剥夺调度方式，又称非抢占方式。即，只允许进程主动放弃处理机。在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
剥夺调度方式，又称抢占方式。当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。

进程的切换与过程

“狭义的进程调度”与“进程切换”的区别:
狭义的进程调度指的是从就绪队列中选中一个要运行的进程。(这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程,后一种情况就需要进程切换）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。

广义的进程调度包含了选择一个进程和进程切换两个步骤。

进程切换的过程主要完成了:
1.对原来运行进程各种数据的保存2.对新的进程各种数据的恢复
(如:程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块)
注意:进程切换是有代价的，因此如果过于频繁的进行进程调度、切换，必然会使整个系统的效率降低，使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

小结

2.2.3 调度算法的评价指标

总览

CPU利用率

系统吞吐量

周转时间

等待时间

调度算法只会影响作业/进程的等待时间

响应时间

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

小结

2.2.4 作业/进程调度算法（FCFS先来先服务、SJF短作业有限、HRRN高响应比优先）

这三类算法用于批处理操作系统

总览

先来先服务（FCFS，First Come First Serve）

短作业优先（SJF，Shortest Job First）

第二章、进程管理 - 图52

高响应比优先（HRRN，Highest Response Ratio Next）

小結

2.2.5 作业/进程调度算法（时间片轮转~、优先级~、多级反馈队列~）

常用于分时操作系统

总览

时间片轮转（RR，Round-Robin）

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

一般设计时间片时要让切换进程的开销占比不超过1%