进程与线程

前驱图

​ 前驱图：是指一个有向无循环图，用于描述进程之间执行的先后循序。

1. 程序顺序执行时的特征：
   1. 顺序性
   2. 封闭性
   3. 可再现性
2. 程序并发执行时的特征
   1. 间断性
   2. 时区封闭性
   3. 不可再现性

封闭性：是指程序运行在一个封闭的环境中，即程序运行时独占系统的全部资源，这些资源的状态只能因程序的执行而改变，不受任何外界因素的影响。

所以引入进程，便于更好地描述和控制程序的并发执行，实现资源共享。

进程基本概念

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

进程的特征：

• 动态性：进程是程序在处理器上的一次执行过程，因而是动态的（动态性是进程的最基本的特征）
• 并发性：指多个进程实体同时存于内存中，能在一段时间内同时运行
• 独立性：是指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位
• 异步性：进程按照各自独立运行的、不可预知的速度向前推荐。
• 结构性：从结构上看，进程实体是由程序段、数据段和进程控制块 （PCB）三部分组成的。

程序段：是指程序的代码

数据段：是指运行过程中产生的各种数据

进程控制块（PCB）

​ PCB：是进程实体的重要组成部分，其中记录了用于描述进程情况及控制进程运行所需要的全部信息。通过PCB使得原来不能并发执行的程序，成为能并发执行的进程。在进程的控制和管理中，随进程的创建而建立PCB，因进程的状态变化而修改PCB的相关内容；当进程被撤销时，系统收回其PCB。可见，系统是根据PCB来感知进程的存在的，PCB是进程存在的唯一标志，一个进程只能有一个进程控制块。

进程控制块的组织方式

进程的基本状态

​ 进程有三种基本状态：就绪状态、执行状态、阻塞（等待）状态

引起进程阻塞和唤醒的事件：

1. 请求资源失败
2. 待某操作完成
3. 数据未到达
4. 待任务到达

引起创建进程的事件：

1. 用户登录
2. 作业调度
3. 请求服务
4. 应用请求

引起删除进程的事件：

1. 正常结束
2. 异常结束
3. 外界干预

进程状态间如何转换？

引起进程状态转换的经典事件：

1. 就绪 -> 执行
2. 执行 -> 就绪
3. 执行 -> 阻塞
4. 阻塞 -> 就绪

进程的控制

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

​ 用原语实现进程控制。原语的特点就是执行期间不允许中断，只能一气呵成。这种不可被中断的操作即原子操作。原语采用开中断指令和关中断指令实现。

• 进程创建原语：create/fork/vfork
• 进程终止原语：exit/terminate/_exit
• 阻塞原语：block/wait
• 唤醒原语：wakeup
• 挂起原语：susped/sleep
• 激活原语：active

进程状态转换的过程

1. 进程创建过程
   1. 申请PCB：赋予一个同意进程标识符
   2. 分配资源：为进程映像分配空间
   3. 初始化进程控制块：初始化标识信息、CPU状态信息、进程状态信息等
   4. 将进程插入就绪队列：设置相应的链接，把新进程加到就绪队列的链表中
2. 进程的终止过程
   1. 找到要终止进程的PCB，读取进程的状态
   2. 立刻终止
   3. 终止其所有子进程
   4. 释放资源
   5. 将PCB移除队列，等待其他进程来搜索信息
3. 过程阻塞过程
   1. 进程停止执行、保存CPU现场
   2. 改变状态
   3. 插入相应阻塞队列
   4. 调度进程重新调度

进程通信

​ 进程通信是指进程之间的信息交换。目前，高级通信机制可归纳结为四大类：共享存储器系统、管道通信系统、消息传递系统以及客户机——服务器系统

1. 共享存储器：在内存中分配一片空间作为共享存储区。需要进行通信的进程把它附加到自己的地址空间中，不需要则把它取消。共享存储器系统分两种：

   1. 基于共享数据结构的通信方式：在这种通信方式中，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。操作系统仅提供共享存储器，由程序员负责对公用数据结构的设置及对进程间同步的处理。该通信方式仅适于传递少量数据，通信效率低下，属于低级通信。
   2. 基于共享存储区的通信方式：为了传输大量数据，在内存中划出一块共享存储区域，诸进程可通过对该共享区的读或写交换信息，实现通信，数据的形式和位置甚至访问控制都是由进程负责，而不是OS。该通信方式属于高级通信。

2. 管道通信系统：管道（pipe文件）：是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件。由于发送进程和接收进程是利用管道进行通信的，故有称为管道通信。这种方式首创于UNIX系统，由于它能有效地传送大量数据，因而又被引入到其他操作系统中。为了协调双方的通信，管道机制必须提供以下三方面的协调能力：

   1. 互斥：即当一个进程正在对pipe执行读/写操作时，其他进程必须等待。
   2. 同步：把一定数量的数据写入pipe，便去睡眠等待，直到读进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直到写进程将数据写入管道后才能将之唤醒。
   3. 确认对方是否存在：只要确定了对方已存在时才能进行通信。

3. 消息传递系统：在该机制中，进程不必借助任何存储区或数据结构，而是以格式化的消息为单位，将通信的数据封装在消息中，并利用操作系统提供一组通信命令（原语），在进程间进行消息传递，完成进程间的数据交换。该方式隐藏了通信实现细节，使通信过程对用户透明化，降低了通信程序设计的复杂性和错误率称为当前应用最为广泛的一类进程间通信的机制。消息传递系统分成两类：

   1. 直接通信方式：是指发送进程利用OS所提供的发送原语，直接把消息发送给目标进程；
   2. 间接通信方式：是指发送和接收进程，都通过共享中间实体（称为邮箱）的方式进行消息的发送和接收，完成进程间的通信。

线程

​ 线程是独立调度的基本单位，一个进程中可以有多个线程，他们共享进程资源。减少程序并发执行所需付出的时空开销，使操作系统具有更好发的并发性。

​ 线程的实现方式：

1. 内核支持线程KST
2. 用户级线程ULT
3. 组合方式：组合方式下包括三种不同的模型，如下图所示：

线程的优缺点

用户线程优缺点：

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

内核级线程优缺点

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

进程与程序的区别

1. 最本质的区别：进程是动态的，程序是静态的
2. 程序可以写在纸上或在某一个存储介质上长期保存，而进程具有生存期，创建后存在，撤销后消亡
3. 一个程序可以对应多个进程，但一个进程只能对应一个程序。

进程和线程的主要区别

1. 调度：在传统操作的操作系统中，独立调度的基本单位是进程，而在引入线程的操作系统中，线程是调度和分派的基本单位。
2. 并发性：在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的多个线程之间亦可并发执行，因而操作系统具有更好的并发性，能更有效地使用系统资源和提高系统吞吐量。
3. 拥有自由：不论是传统的操作系统，还是设有线程的操作系统，进程都是拥有资源和分配的独立单位，进程拥有自己的资源。一般地说，线程不拥有系统资源，但它可以访问隶属进程的资源
4. 系统开销：切换进程时操作系统所付出的开销远大于切换线程的开销

CPU调度与上下文切换

调用的基本概念

​ 调度的实质是一种资源分配，处理机调度是对处理机资源进行分配。按照一定策略动态把处理机分配给处于就绪列的某个进程执行

1. 处理机调度的层次：
   1. 高度调度（作业调度）：选符合条件的作业装入内存
   2. 中级调度（内存调度）
   3. 低级调度（进程调度）：从就绪进程中选一个占用处理机
2. 处理机调度算法的目标：
   1. 资源利用率
   2. 公平性
   3. 平衡性
   4. 策略强制执行

作业生存期：

• 提交状态
• 后备状态（收容）
• 运行状态
• 完成状态

衡量调度算法的性能指标

1. CPU利用率：CPU 处于忙状态的时间与开机运行总时间的比值。
2. 系统吞吐量：表示单位时间内CPU完成作业的数量
3. 响应时间：指用户从提交请求到系统首次产生响应所用的时间
4. 等待时间：作业处于等待处理机状态之和
5. 周转时间：指作用从提交到完成所经历的时间。
   1. 周转时间 = 作业完成时间 - 作业提交时间
   2. 平均周转时间 = （作业1的周转时间 + … + 作业n的周转时间）/ n
   3. 带权周转时间 = 作业周转时间 / 作业实际运行时间

一般情况下，应根据设计的总体目标，合理地选择以上指标，从而有利于确定优良的调度算法。

进程调度的时机

进程调度的时机有以下两种情况：

1. 当前进程主动放弃处理机
   1. 进程正常终止
   2. 进程运行中发生异常终止
   3. 进程请求阻塞，如I/O请求
2. 当前进程被动放弃处理机
   1. 分配给进程的时间片用完
   2. 有更紧急的事要处理（如I/O中断）
   3. 有更高优先级的进程进入队列

不能进行进程调度与切换的情况：

• 在处理中断的过程中
• 在操作系统内核程序临界区中
• 在原语中

1. 临界资源：在一段时间内只允许一个进程访问的资源
   1. 硬件资源：打印机，磁带机
   2. 软件资源：栈、变量、表格
2. 临界区：每个进程中访问临界资源的那段代码

进程调度的任务与方式

进程调度的任务

1. 保存镜像：保存处理机的现场信息
2. 调度算法：按某种算法选取进程
3. 进程切换：把处理机分配给进程
4. 处理机回收：从进程收回处理机

进程调度的方式

1. 非抢占式：实现简单系统开销小，但是无法及时处理紧急任务适合于早起的批处理系统
2. 抢占式：可以优先处理紧急任务，也可以以时间片轮流执行，适用于分时系统和实时系统

经典调度算法

先来先服务调度算法（FCFS）

• 作业调度、进程调度
• 非抢占式

根据就绪队列按进入的先后次序获取CPU

平均周转时间 $t=1.725$

平均带权周转时间 $w=6.875$

短作业优先调度算法（SJF）

• 作业调度、进程调度
• 非抢占式

该算法根据下一次所需时间的长短，从就绪状态中选择运行时间最短的进程首先占有CPU。有利于提高设备利用率，但同意出现饿死现象。

平均周转时间 $t=1.55$

平均带权周转时间 $w=5.15$

饥饿：某些进程也可能会长时间等待，当等待时间给进程推进和响应带来明显影响

饿死：当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义

高响应比优先调度算法（HRRN）

• 作业调度

• 非抢占式

响应比 = （等待时间+要求服务时间）/ 要求服务时间

1. 作业1响应比：$(0+2)/2=1$
2. 作业2响应比：$(1.5+0.5)/0.5=4$
   1. 作业2响应比：$(1.6+0.5)/0.5=4.2$
3. 作业3响应比：$(1+0.1)/0.1=11$
4. 作业4响应比：$(0.5+0.2)/0.2=3.5$
   1. $(0.6+0.2)/0.2=4$

前三种算法都是非抢占式，一般适用于早起的批处理系统

时间片轮转调度算法（RR）

• 进程调度
• 抢占式

按一定时间片轮番运行各进程，如果时间片式一个定值，则对各个进程机会均等，适用分时操作系统

1. 每次选择就绪队列中的第一个进程，但是只能运行一个时间片大小
2. 时间片长短的选择参考因素：系统的响应时间、就绪队列中的进程数目、系统的处理能力。时间片太大，相当于FCFS；太小，处理机切换频繁，开销增大

优先级调度算法（PAS）

• 作业调度、进程调度
• 抢占/非抢占式

优先级调度法是为每个进程确定一个优先级，并按其高低确定占有CPU的次序，从而消除饿死现象。

1. 根据更高优先级进程是否可以抢占正在执行的进程，分类为：
   1. 抢占式优先级调度算法
   2. 非抢占式优先级调度算法
2. 根据进程的优先级是否可以改变，将进程的优先级分为：
   1. 静态优先级
   2. 动态优先级
3. 优先级：
   • 系统 > 用户
   • 交互型 > 非交互型
   • I/O型 > 计算型
   • 短作业 > 长作业

多级反馈队列调度算法（MFQ）

• 进程调度
• 抢占式

1. 调度机制
   1. 设置多个就绪队列，并为每个队列赋予不同的优先级。（第一梯队优先级最高，其余队列优先级依次降低）
   2. 各个队列中进程执行时间片大小不同。（优先级越高的队列中进程运行的时间片越小）
   3. 除第 n 队列外，每个队列都采用 FCFS 算法，第 n 队列中按 RR 方式运行
2. 调度算法的优势
   1. 终端型用户：短作业优先
   2. 短批处理作业用户：周转时间短
   3. 长批处理作业用户：经历前面队列的部分执行，不会出现 “饥饿”

经典调度算法总结

上下文及其切换机制

进程上下文：进程物理实体和支持进程运行的环境

上下文切换：进程在当前上下文中运行，当系统调度新进程占有处理机时，新老进程发生上下文切换一个进程的上下文可以分为三个部分：

上下文切换发生在操作系统调度一个新进程到处理器时，需要完成以下三件事

1. 保存现场信息：将当前处理器的寄存器上下文保存到当前进程的系统级上下文的现场信息中；
2. 恢复现场信息：将新进程系统级上下文的现场信息作为新的寄存器上下文恢复到处理器的各个寄存器中；
3. 转移：将控制转移到新进程执行。

同步与互斥

互斥和同步

间接相互制约关系（互斥）：进程排他性访问共享资源。

互斥问题是相互无逻辑关系的进程间竞争使用相同的资源所发生的制约关系

直接相互制约关系（同步）：进程间的合作，比如管道通信。

同步问题是存在逻辑关系的进程之间相互等待产生的制约关系

互斥实现方法

软件实现法

单标志法

双标记法先检查

布尔型数组flag[]

flag[i]为true，进程已进入临界区

flag[i]为false，进程未进入临界区

双标志法后检查

布尔型数组flag[]

flag[i]为true，进程已进入临界区

flag[i]为false，进程未进入临界区

皮特森算法（Peterson’s Algorithm）

硬件实现方法

中断屏蔽法（关中断/开中断）：当一个进程正在使用处理机执行他的临界区代码时，防止其他进程进入其临界区进行访问的最简方法是。禁止一切中断发生，或称之为屏蔽中断、关中断。

TSL指令（Test-And-Set-Lock）：这条指令是原子操作，指执行该代码时不允许被中断。其功能是读出指定标记后把该标志为真。

Swap指令：这条指令是原子操作，交换两个变量的值。

1. 软件实现方法：
   1. 单标志法：违背 “空闲让进”
   2. 双标志法先检查：违背 “忙则等待”
   3. 双标志后检查：违背 “空闲让进”、“有限等待”
   4. 皮特森算法（Peterson‘s Algorithm）：违背 “让权等待”，会发生 “忙等”
2. 硬件实现方法：
   1. 中断屏蔽法（关中断/开中断）：禁止一切中断发生
   2. TLS指令（Test-And-Set-Lock）：原子操作，读取指定标志后把该标志设置为真
   3. Swap指令：原子操作，交换两个变量的值

信号量（Semaphore）机制

PV操作：

• P操作：wait原语，进程等待
• V操作：signal原语，唤醒等待进程

经典同步问题

生产者-消费者问题

读者-写者问题

哲学家进餐问题

死锁

死锁的基本概念

1. 死锁的定义：死锁是指多个进程因竞争资源而造成的一种相互等待，若无外力作用，这些进程都将无法继续运行。
2. 产生死锁的原因：
   1. 竞争不可抢占性资源
   2. 进程推进顺序不当
3. 产生死锁的必要条件：产生死锁必须同时具备下面四个必要条件，只要其中一个条件不成立，死锁就不会发生。
   1. 互斥条件：共享资源的排他性访问
   2. 请求和保持条件：保持当前资源时请求另一个资源
   3. 不可抢占条件：存在共享资源的循环等待链

死锁的处理方法

预防死锁

预防死锁的方法是通过破坏产生死锁的四个必要条件中的一个或几个，从而避免死锁的产生。

互斥条件是非共享设备所必须得，不仅不能改变，还应加以保护。

1. 破坏“请求和保持”条件
   1. 方法：所有进程在开始运行之前，必须一次性地申请其在整个运行过程的所有资源。
2. 破坏“不可抢占”条件
   1. 方法：当一个进程，提出新的资源请求而不能得到满足时，它必须释放已经保持的所有资源。
3. 破坏“循环等待”条件
   1. 方法：对系统所有资源类型进行线性排序，并赋予不同的序号。每个进程必须按序号递增的顺序请求资源。

死锁避免

在资源的动态分配中，用某种方法防止系统进入不安全状态，从而可以避免发生死锁。

常用的方法：

1. 系统安全状态
   1. 安全状态是指系统能按某种进程顺序为每个进程P分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。此时称（P1，P2，…，Pn）为安全序列。
   2. 如果系统无法找到这样一个安全序列，则系统处于不安全状态。
2. 利用银行家算法避免死锁

死锁检测

1. 资源分配图

资源分配图中有环不一定存在死锁，无环一定没有死锁。

资源分配图中的符号表示：

1. 圆圈代表一个进程。
2. 方框代表一类资源。
3. 方框中的一个点代表一类资源中的一个资源。
4. 由进程出发到资源的有向边表示请求边。
5. 由资源出发到进程的有向边表示分配边。

环p1->r1->p2->r2->p3->r3->p1会发生死锁

2. 死锁定理：状态S为死锁状态的充分条件是当且仅当S状态的资源分配图不可完全简化。

死锁解锁

当检测到系统中已发生死锁时，就采用相当措施。将进程从死锁状态中解脱出来。常用的方法：

1. 资源剥夺法
2. 终止进程法
3. 进程回退法