进程管理

进程与线程

进程概念

进程概念的引入是为了实现程序的并发执行，并对并发执行的程序加以描述和控制。 为了使参与并发执行的程序都可以独立运行，操作系统会为每一个进程都配备一个进程控制块（PCB）。一个进程实体主要包括主要包括程序段、相关数据段、PCB。 PCB是进程存在的唯一标志，也就是说，系统根据PCB来判断系统内部目前有多少个进程。 相对于程序，进程更像是一个动态过程。一个不恰当的比喻，如果人作为一个生物体有一个大体类似的基因（程序），那具体的每一个人的一生，就是进程了。

进程的状态与转换

程序一般拥有五个状态：创建、就绪、阻塞、执行、终止。一般理解什么情况下会从什么态转换到什么态即可。有些操作系统还会引入一个挂起态（会将进程信息移除内存）

进程控制

进程的创建

在操作系统中，允许一个进程创建另外一个进程。通常把创建进程的进程成为父进程。在UNIX系统中，用树状图的结构来表示进程之间的父子关系，在PCB中有专门的族谱（家族关系表项）记录相关信息。而在Windows系统中不存在进程层次，而是用句柄来替代一个操作的权限。句柄是可以传递的，获得句柄就可以获得拥有控制其他进程的权力，因此 进程之间的关系不再是层级，而是线性的，是否获得句柄的关系。 引起进程创建的事件有几种：用户登录、作业调度、提供服务、应用请求。 进程的创建一般有以下几个步骤：

1. 申请PCB
2. 分配资源（如果资源不足不会直接创建失败，而是进入阻塞态）
3. 初始化PCB
4. 如果就绪队列有空位，则放入就绪队列

进程的终止

引起进程结束的事件一般有：正常结束、异常结束、外部干预。 进程结束的过程一般有以下步骤：

1. 根据要终止的标识符，从PCB集合中找到需要终止的进程PCB，读取进程状态
2. 若处于正在执行，则立即停止执行
3. 若还有子孙进程，则将子孙们也kill了
4. 进程原持有资源返还给父进程或操作系统
5. 将PCB移出所在队列

进程阻塞和唤醒

进程的切换

步骤如下：

1. 保存处理机上下文，包括程序计数器和其他寄存器
2. 更新PCB
3. 将PCB移入相应队列
4. 选择另一个进程执行 并更新PCB
5. 更新内存管理数据结构
6. 回复处理机上下文

要注意调度和切换的区别。调度是决定系统资源如何分配，属于决策，而切换属于实际分配行为，也就是执行。先有调度后有切换。

进程的组织

这一部分主要是了解进程实体所包含的内容

PCB

主要包括

1. 进程描述信息
2. 进程控制和管理信息
3. 资源分配清单
4. 处理机相关信息（主要是处理机寄存器的值）

程序段

代码段

数据段

数据段，有的会细分为数据堆段和数据栈段

一般来说，C语言编写程序使用内存一般分喂三个段

1. 正文段：代码和已赋值数据段，存放二进制代码和常量
2. 数据堆段：动态内存分配在数据堆段
3. 数据栈段：未赋初值的局部变量、临时使用的变量 实参传递等在栈段

进程通信

共享存储

共享存储一般可以分两种：低级方式的基于数据结构的共享；高级方式的基于存储区的共享。前者适用于量比较少的通信。对共享空间进行读写时，需要互斥进行。

消息传递

消息传递的方式不依靠存储区或数据结构，而是将数据格式化，使用操作系统提供的通信指令在进程间通信。根据实现方式可以将消息传递的方式分为两类：直接通信方式以及间接通信方式。 直接通信方式是手把手把信息交给进程，而间接通信方式可以理解为将信息暂存某处，接收进程需要时再去取。

管道通信

管道通信比较适合于传送大量文件，Linux系统中的管道通信使用pipe文件，限制每一个缓冲区为4kb。有以下要求

1. 互斥。有一个进程对pipe进行操作时，另外的文件只能等待。
2. 同步。写够4kb就会阻塞等待，读进程取走数据后（取走一次即作废）再继续写。
3. 确定双方存在才会通信。

因为有互斥同步的要求，管道通信必然是半双工通信

线程概念与多线程模型

进程的基本属性

进程有两个基本属性

1. 可拥有资源的独立单位
2. 可独立调度和分派的基本单位

线程的基本概念

最基本的理解就是，轻量级进程。线程是一个基本的CPU执行单元，也是程序执行流的最小单元。 线程由线程ID、程序计数器、寄存器组和、堆栈组成。线程是进程中的一个实体，是被独立调度、分配的基本单位，但线程共享同一进程下的线程资源。

线程进程的对比

1. 调度 传统OS中，进程是拥有资源和独立调度的基本单位，但引入线程的系统中，线程才是独立调度的基本单位。

2. 并发性 不仅进程可以并发运行，线程也可以并发运行。同一进程的线程切换不会引起进程切换。

3. 拥有资源 进程是拥有资源的基本单位，而线程不拥有系统资源。但线程可以访问所属进程的资源。

4. 独立性 线程独立性会比进程独立性差，这是因为线程可以访问所属进程资源。

5. 系统开销 进程的操作相对系统开销会比线程的大。

6. 支持多处理机 线程中的多线程可以运行在不同的处理器上，而单线程的进程只能运行在一个处理器上。

   线程的实现方式

   线程实现方式主要分为：用户级线程，内核级线程，分别对应了线程在哪部分实现。 内核级线程的主要优点在于：

   1. 多处理系统上，内核可以调度同一进程的多个线程并行执行。
   2. 如果一个线程阻塞，内核可以调度同一进程的其他线程占用处理机，也可以运行其他进程
   3. 内核支持线程具有的小数据结构以及堆栈，所以切换较快，开销小。
   4. 内核本身可以作为多线程程序，可以提高系统效率 缺点主要在于：
   5. 对于用户线程而言，内核线程切换开销大，从一个线程切换到另一个线程，需要转为核心态

   用户级线程中，对于单个进程的调度是公平的（时间片），但是对于进程内的线程是不公平的。用户级线程有如下优点：

   1. 切换不需要在核心态完成
   2. 调度算法可以是进程专用的，不用受os调度影响
   3. 用户级线程和os无关，易于跨平台

缺点在于：

1. 当进程内一个线程阻塞，其他线程也会被阻塞，而内核线程可以切换。
2. 用户级线程不能利用多处理机进行多重处理，每一个进程只会被分配一个CPU

处理机调度

调度的基本概念

调度是操作系统设计的核心问题

调度的层次

1. 高级调度 高级调度也称作业调度，调度的对象是作业。主要功能就是根据某种算法，将后备队伍的作业调入内存，为他们创建进程，分配资源，并将他们放在就绪队列。一般只有多道批系统需要作业调度，其他系统无需配置。
2. 中级调度 中级调度又称内存调度，作用是提高内存的使用效率和系统吞吐量。作用是将那些在内存里的，暂时无法运行的进程调到内存等待。把被这样调度后的进程称为挂起态。当系统已经具备运行他们的条件时，又将他们从外存调回来，并将状态改为就绪态。
3. 低级调度 低级调度又称进程调度，其任务是根据一定策略，将进程交给处理机运行。基本所有的系统都要配置进程调度，进程调度频率很高，几十毫秒一次。

调度时机、切换与过程

进程调度和切换程序是操作系统内核程序。 现代操作系统中，有以下不能进行调度和切换的情况：

1. 处理中断过程中
2. 进程在操作系统内核程序的临界区
3. 其他需要屏蔽中断的原子操作中

调度方式

有两种调度方式：非剥夺调度方式和剥夺调度方式 非剥夺调度方式特点在于，如果有更加紧急的任务进入，也必须让当前任务执行完才会切换。这种方式优点是实现简单，系统开销小，适用于批处理系统，但不适用于分时系统和大部分实时系统。 剥夺调度方式和前者相反，更加紧急任务到来时，会停止当前任务，切换到紧急的任务。这种调度方式的优点在于可以提高吞吐量和处理效率，但是这种剥夺式行为，必须遵循一定原则。

调度的基本准则

不同的系统类型遵循的基本准则不完全一致，分开讨论：

处理机调度算法共同目标

这类目标是各类系统都会追求的目标。

1. 资源利用率，最为重要的是CPU利用率： $$CPU利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$$
2. 公平性 每个进程都能合理得到CPU时间，避免发生饥饿现象。
3. 平衡性 保证IO型、计算型进程资源使用的平衡性。

批处理系统目标

1. 周转时间 $$周转时间=作业完成时间-时间提交时间$$ $$平均周转时间=\frac{总周转时间}{进程数}$$ $$带权周转时间=\frac{作业周转时间}{作业实际运行时间}$$ $$平均带权周转时间=\frac{总带权周转时间}{进程数}$$
2. 吞吐量高
3. 处理及利用率高

分时系统目标

1. 响应时间快
2. 均衡性 指的是系统响应时间快慢和用户所请求服务复杂性相适应

实时系统目标

1. 截止时间保证 即最晚开始时间需要保证
2. 可预测性

典型调度算法

先来先服务 FCFS

可用于作业调度和进程调度。FCFS算法属于不可剥夺算法，从表面看对任意的进程都是公平的，但如果一个长时间作业先到达系统，后面的进程就会长时间等待。因此分时系统和实时系统不会将其作为主要调度策略，但常常会结合到其他策略中，例如有优先级的调度中，同一优先级的进程就会按FCFS来调度。

短作业优先 SJF

作业越短，优先级越高。 短作业优先算法相对FCFS已经有所提升，但是依旧会有缺点：

1. 必须预先知道作业的运行时间
2. 对长时间作业非常不利。会出现饥饿现象
3. 无法实现人机交互
4. 无优先级处理，无法处理紧急任务 SJF算法的平均等待时间、平均周转时间最少

优先级调度算法

根据是否剥夺当前进程可以分为两种。 根据优先级是否可以更改也分为静态优先级和动态优先级 一般来说优先级设置可以根据以下原则进行：

1. 系统进程>用户进程
2. 交互进程>非交互进程
3. IO进程>计算型进程（让低速的IO设备今早开始黑奴）

高响应比优先调度算法HRRN

$$响应比 = \frac{等待时间+要求服务时间}{要求服务时间} $$ 有以下特点：

1. 要求服务时间越短，响应比越高。故利于短作业
2. 要求服务相同，则响应比取决于等待时间，则有利于先来的服务
3. 克服了SJF的饥饿现象

时间片轮转调度RR

时间片循环轮流上岗。时间片的选择很重要。

多级反馈队列调度

每一级优先级递减，时间片为上一级的两倍。每一个队列采用FCFS算法。直到最后一级使用时间片轮转算法。 多级反馈队列的优点如下：

1. 对于终端型作业：短作业优先。（前面的队列就可以完成）
2. 短批处理作业：周转时间较短
3. 长批处理作业：不会饥饿。

同步与互斥

进程同步的基本概念

临界资源

一次仅允许一个进程使用的资源叫临界资源。临界资源访问必须互斥进行。

同步

也叫直接制约关系。进程间的直接制约关系来源于他们的相互合作。

互斥

互斥也称间接制约关系。间接制约关系可以理解为来源于竞争。

同步互斥原则

1. 空闲让进
2. 忙则等待
3. 有限等待
4. 让权等待

实现临界区互斥的基本方法

软件方法

1. 单标志法 用一个标志位表示轮到谁使用，严格次序轮流使用临界区 优点：实现简单 缺点：可能会违背空闲让进，浪费资源
2. 双标志优先检查 进入临界区前像判定临界区是否被使用。但无法避免的是，检查和切换操作不是原子操作，可能会在两者之间出现其他进程进入临界区的情况。 优点：不用交替进入，可连续使用 缺点：可能违背忙则等待。
3. 双标志位后检查法 上一算法先检测对方状态，再置自己的flag，因此这个算法先立flag，管他有没有人使用，立了之后再检查有没有人使用，没人使用我再使用。这个算法问题在于，可能两者同时都立了flag，然后检查对方的flag发现都立了flag，都以为对方进入了临界区，结果都没有进入临界区。因此可能造成饥饿现象。
4. 皮特森算法 为了防止后检查法的饥饿现象，又设置了一个公共turn变量。每个进程先立flag，然后改turn，再检测对方的flag和公共的turn，以保证每次只有一个进程进入临界区。简单来说就是双重保证，flag保证不会有空闲，turn保证只会有一个进程进入。这个算法太过复杂。

硬件方法

1. 中断屏蔽 当一个进程进入临界区后，将禁止一切中断发生，这样就不会进行进程的调度，保证临界区访问。 但这种方式限制了处理机交替执行的能力，并且如此高的权限交给蠢用户并不安全。同时这种方法也无法限制多处理器。
2. 硬件指令 使用Test and Set指令。这条指令是原子操作，不会被中断，因此也不会有双标志先检查法的问题。为每一个临界资源设置一个lock变量，一旦有进程进入临界区，使用此原子指令将lock上锁。若有其他进程希望进入临界区，需要不停的查询lock状态，当lock是开锁状态时才允许进入。 使用Swap指令。这条指令很好理解，就是将两个变量值交换，同样也是原子操作。为每个临界区设立lock和key变量，在进程进入临界区前，先使用Swap交换lock和key的值，然后检查key的状态。进程无法进入临界区时，则一直交换lock和key的值，直到key变成了flase。当进程退出临界区，则将lock设置为false。

硬件方法优点：

1. 可以用作任意数量进程
2. 简单
3. 可以支持多个临界区

硬件方法缺点：

1. 如果进入不了临界区会一直循环检测变量状态，无法做到让权等待
2. 当临界区空闲时是随机选择一个进程进入，因此可能会有饥饿现象

信号量

整形信号量

wait:资源-1 signal:资源+1 应用于PV操作 缺点：没有遵循让权等待原则。

记录型信号量

不存在忙等现象，除了需要代表资源数目的value外，还需要一个进程链表指针list，用于记录等待的进程链接。

管程*

一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块,这组操作能初始化并改变管程中的数据和同步进程 管程的组成:

1. 管程名称
2. 局部于管程的共享数据结构说明
3. 对该数据结构的一组过程
4. 对局部于管程的共享数据设置初始值语句

可以理解为软件实现的PV操作

经典同步问题

暂略

死锁

死锁的概念

所谓死锁，是指多个进程因为竞争资源导致陷入僵局，如果没有外力的作用，进程将永远无法向前推动。 造成死锁的原因可以归结为：

1. 竞争资源
2. 进程推进顺序非法

产生死锁的必要条件有四种：

1. 互斥条件
2. 请求和保护条件
3. 不剥夺条件
4. 循环等待条件

死锁处理策略

有四种处理死锁的方法：

1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁

死锁预防

死锁的预防一般是破坏产生死锁的四个必要条件：

1. 破坏互斥条件
2. 破坏不剥夺条件 如果自己新申请的资源无法被满足，那就要把以前的也吐出来。这种方法是实现起来要负很大的代价。
3. 破坏请求并保持条件
   • 开始运行之前，把他要的资源先全给他，如果给不了，那就不开始。这种方法破坏了“请求”这一特点。优点是简单易行安全，但是有浪费资源，会让进程饥饿等缺点。
   • 允许进程只获得运行初期的资源便开始运行，运行过程中释放使用完毕的资源，再申请新的资源。
4. 破坏循环等待条件 将资源排序，必须按编号从小到大申请资源。这样申请了较高序号资源的进程继续申请的资源必定是空闲的。这样的作法相对而言比较先进，但是序号是相对固定的，不好添加新的设备。以及使用资源顺序不同，可能会导致资源浪费。

避免死锁

####系统安全状态 安全状态是指系统能按某种循序来为进程分配资源，使得每个资源都可以顺利完成。如果系统存在不安全序列，则称系统处于不安全状态。

银行家算法

实现银行家算法需要附加一些数据结构：

• 可利用资源向量 Available;
• 最大需求矩阵 Max;
• 分配矩阵 Allocation;
• 需求矩阵 Need

死锁的检测和解除

死锁的检测

为了可以检测死锁，系统必须：

1. 保存有关资源的请求和分配信息
2. 提供一种算法检测是否进入了死锁

死锁的解除

1. 剥夺资源
2. 撤销进程
   • 终止所有进程
   • 逐个终止

易错点

1. 一个系统资源准备好后，不会改变所有需求进程的状态， 只会改变一个需求进程状态。
2. 同一个系统的进程可以由系统调用方法被不同进程多次使用。
3. 就绪队列在不空的情况下的长度增加，不会影响CPU的运作效率
4. 操作系统对用户线程的线程控制块分配数量取决于使用的是哪有连接方式（一对一 一对多等）
5. 公用队列属于临界资源
6. 如果使用互斥变量比如mutex，当前值如果为0，如果还有资源继续申请，数值会持续变小而不是一直保持0，所以如果一个进程使用V操作唤醒了一个进程后，mutex的值是小于等于0的。
7. 一个进程离开管程才会使用signal