操作系统第二章-进程与线程

操作系统第二章进程与线程

计算机学科基础：操作系统第二章进程与线程的学习笔记

一.进程与线程（✪）

1.进程的概念

进程与程序
- 程序：是静态的，一组有序的指令集合，是存放在磁盘里的可执行文件，如：QQ.exe
- 进程：是动态的，是程序的一次执行过程，如：可同时启动多次QQ程序
  同一个程序多次执行会对应多个进程
- 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
进程实体
- 进程实体又称进程映像，由程序段、相关数据段和PCB三部分构成
  PCB是给操作系统用的。程序段、数据段是给进程自己用的。
- 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
  进程实体是静态的，而进程则是动态的
- PCB（进程控制块）
  - 为了使参与并发执行的每个程序（含数据）都能独立地运行，必须为之配置一个专门的数据结构，称为进程控制块 PCB
  - PCB是进程存在的唯一标志，系统利用PCB来描述进程的基本情况和运行状态，进而控制和管理进程
    当进程被创建时，操作系统为其创建PCB，当进程结束时，会回收其PCB
- 程序段：程序的代码（指令序列）
- 数据段：运行过程中产生的各种数据 (如程序中定义的变量)

2.进程的组成

由PCB，程序段，数据段组成
PCB的组成
- 进程描述信息
  - 进程标识符（PID）：标志各个进程，每个进程都有一个唯一的标识号
  - 用户标识符（UID）：进程归属的用户，用户标识符主要为共享和保护服务
- 进程控制和管理信息
  - 进程当前状态：描述进程的状态信息，作为处理机分配调度的依据
  - 进程优先级：描述进程抢占处理机的优先级，优先级高的进程可优先获得处理机
- 资源分配清单
  - 用于说明有关内存地址空间或虚拟地址空间的状况，所打开文件的列表和所使用的输入输出设备信息
- 处理机相关信息
  - 也称处理机的上下文，主要指处理机中各寄存器的值。当进程处于执行态时，处理机的许多信息都在寄存器中。
  - 当进程被切换时，处理机状态信息都必须保存在相应的PCB中，以便在该进程重新执行时，能从断点继续执行。

3.进程的特征

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

4.进程的状态与转换（♚）

进程的五状态（就绪态、运行态、阻塞态是进程的三种基本状态）
- 创建态：进程正在被创建，操作系统为进程分配资源、初始化PCB
- 就绪态：进程已经具备运行条件，但由于没有空闲CPU，而暂时不能运行
- 运行态：进程占有CPU，并在CPU上运行
- 阻塞态（等待态）：在进程运行的过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或者等待其他进程的响应）
  在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”
- 终止态：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB
进程状态之间的转换
- 就绪态一>运行态：进程被调度
- 运行态一>就绪态：时间片到，或CPU被其他高优先级的进程抢占
- 运行态一>阻塞态：等待系统资源分配，或等待某事件发生（主动行为）
- 阻塞态一>就绪态：资源分配到位，等待的事件发生（被动行为）
- 创建态一>就绪态：系统完成创建进程相关的工作
- 运行态一>终止态：进程运行结束，或运行过程中遇到不可修复的错误、
- 图片
进程的组织
- 进程PCB中，会有一个变量state来表示进程的当前状态。如：1表示创建态、2表示就绪态、3表示运行态。
  为了对同一个状态下的各个进程进行统一的管理，操作系统会将各个进程的PCB组织起来。
- 链接方式
  - 链接方式将同一状态的PCB链接成一个队列，不同状态对应不同的队列；
    也可把处于阻塞态的进程的PCB，根据其阻塞原因的不同，排成多个阻塞队列
  - 图片
- 索引方式
  - 索引方式将同一状态的进程组织在一个索引表中，索引表的表项指向相应的PCB，
    不同状态对应不同的索引表，如就绪索引表和阻塞索引表等。
  - 图片

5.进程控制（♚）

进程控制就是要实现进程状态转换，用原语实现
原语是一种特殊的程序，它的执行具有原子性也就是说，这段程序的运行必须一气呵成，不可中断
原语的实现（使用关中断指令与开中断指令这两个特权指令实现原语）
- 正常情况下，CPU每执行完一条指令都会例行检查是否有中断信号需要处理，
  如果有，则暂停运行当前这段程序，转而执行相应的中断处理程序。
- CPU执行了关中断指令之后，就不再例行检查中断信号，直到执行开中断指令之后才会恢复检查。
  此时关中断、开中断之间的这些指令序列就是不可被中断的，这就实现了“原子性”
进程控制相关的原语（♚）
- 进程的创建
  - 创建原语的过程
    - 为新进程分配一个唯一的PID，并申请空白PCB
    - 为新进程分配所需资源，如内存、文件、I/O设备和CPU时间等（在PCB中体现）
      - 这些资源或从操作系统获得，或仅从其父进程获得。
      - 如果资源不足（如内存），则并不是创建失败，而是处于创建态，等待内存资源。
    - 初始化PCB，主要包括初始化标志信息、初始化处理机状态信息和初始化处理机控制信息，以及设置进程的优先级等。
    - 将PCB插入就绪队列，此时创建态→就绪态，等待被调度运行
  - 引起进程创立的事件
    - 用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程
    - 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
    - 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
    - 应用请求：由用户进程主动请求创建一个子进程
    - 启动程序执行
- 进程的终止
  - 可以使进程由就绪态/阻塞态/运行态→终止态→无
  - 终止原语的过程
    - 根据被终止进程的标识符，检索出该进程的PCB，从中读出该进程的状态。
    - 若被终止进程处于运行状态，立即终止该进程的执行，将处理机资源分配给其他进程
    - 若该进程还有子孙进程，则应将其所有子孙进程终止。
      进程间的关系是树形结构
    - 将该进程所拥有的全部资源，或归还给其父进程，或归还给操作系统。
    - 将该PCB从所在队列（链表）中删除。
  - 引起进程终止的过程
    - 正常结束：进程自己请求终止（exit系统调用）
    - 异常结束：整数除以0、非法使用特权指令，然后被操作系统强行杀掉
    - 外界干预：Ctrl+AIt+delete，用户选择杀掉进程
- 进程的阻塞与唤醒
  - 阻塞原语和唤醒原语必须成对使用
  - 进程的阻塞
    - 阻塞是进程自身的一种主动行为，使用阻塞原语可以将运行态→阻塞态
    - 阻塞原语的过程
      - 找到要阻塞的进程对应的PCB
      - 保护进程运行现场，将PCB状态信息设置为“阻塞态”，暂时停止进程运行
      - 将PCB插入相应事件的等待队列
    - 引起进程阻塞的事件
      - 需要等待系统分配某种资源（如申请临界资源，执行P(wait)操作）
      - 需要等待相互合作的其他进程完成工作：等待I/O操作（如从磁盘读数据）
  - 进程的唤醒
    - 将阻塞态转变为就绪态，因何事阻塞，就应由何事唤醒
      - 如退出临界区，I/O结束
    - 唤醒原语的过程
      - 在该事件等待队列中找到PCB
      - 将PCB从等待队列移除，设置进程为就绪态
      - 将PCB插入就绪队列，等待被调度
- 进程的切换
  - 进程的切换可以将运行态→就绪态，就绪态→运行态
  - 切换原语的过程
    - 将运行环境信息（进程上下文）存入PCB
    - 将PCB移入相应队列
    - 选择另一个进程执行，并更新其PCB
    - 根据PCB恢复新进程所需的运行环境
  - 引起进程切换的事件
    - 当前进程时间片到
    - 有更高优先级的进程到达
    - 当前进程主动阻塞
    - 当前进程终止

6.进程的通信

进程通信是指进程之间的信息交换。PV操作是低级通信方式，高级通信方式是指以较高的效率传输大量数据的通信方式
共享存储
- 共享存储的概述
  - 进程是分配系统资源的单位（包括内存地址空间），因此各进程拥有的内存地址空间相互独立。
    为了保证安全，一个进程不能直接访问另一个进程的地址空间，因此需要采用共享存储
  - 设置一块可直接访问的共享空间，并映射到进程的虚拟地址空间
    可通过对这片共享空间进行写/读操作实现进程之间的信息交换
- 共享存储的特点
  - 为避免出错，各个进程对共享空间的访问应该是互斥的，各个进程可使用操作系统内核提供的同步互斥工具(如P、V操作)
  - 操作系统只负责为通信进程提供可共享使用的存储空间和同步互斥工具，而数据交换则由用户自己安排读/写指令完成。
  - 进程空间一般都是独立的，进程运行期间一般不能访问其他进程的空间，
    想让两个进程共享空间，必须通过特殊的系统调用实现，而进程内的线程是自然共享进程空间的
- 基于数据结构的共享（低级）
  - 比如共享空间里只能放一个长度为10的数组。这种共享方式速度慢、限制多，是一种低级通信方式
  - 图片
- 基于存储区的共享（高级）
  - 操作系统在内存中划出块共享存储区。数据的形式和存放位置都由通信进程控制，而不是操作系统。
    这种共享方式速度很快，是一种高级通信方式。
  - 图片
消息传递
- 进程间的数据交换以格式化的消息(Message)为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换
- 消息包括消息头与消息体，消息头包括：发送进程ID、接受进程ID、消息长度等格式化的信息
- 直接通信方式
  - 消息发送进程要指明接收进程的ID，发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，
    接收进程从消息缓冲队列中取得消息
  - 图片：随后msg会移动到进程Q的地址空间上
- 间接通信方式
  - 发送进程把消息发送到某个中间实体，接收进程从中间实体取得消息
    以“信箱”作为中间实体进行消息传递，广泛运用在计算机网络中
  - 可以多个进程往同一个信箱send消息，也可以多个进程从同一个信箱中receive消息
  - 图片：随后msg会移动到进程Q的地址空间上
- 在微内核操作系统中，微内核与服务器之间的通信就采用了消息传递机制。
  由于该机制能很好地支持多处理机系统、分布式系统和计算机网络，因此也成为这些领域最主要的通信工具。
管道通信
- “管道”是一个特殊的共享文件，又名pipe文件。其实就是在内存中开辟一个大小固定的内存缓冲区
- 写进程向管道的一端写，读进程从管道的另一端读。数据在管道中是先进先出的。
- 各进程要互斥地访问管道（由操作系统实现）
- 管道的特征
  - 从管道读数据是一次性操作，数据一旦被读取，就释放空间以便写更多数据。
    普通管道只允许半双工通信，若要实现全双工通信，则需要定义两个管道。
  - 只要管道非空，读进程就能从管道中读出数据，若数据被读空，则读进程阻塞，
    直到写进程往管道中写入新的数据，再将读进程唤醒
  - 只要管道不满，写进程就能往管道中写入数据，若管道写满，则写进程阻塞，
    直到读进程读出数据，再将写进程唤醒
  - 管道中的数据一旦被读出，就彻底消失。因此，当多个进程读同一个管道时，可能会错乱。
    对此，通常有两种解决方案
    - ①一个管道允许多个写进程，一个读进程
    - ②允许有多个写进程，多个读进程，但系统会让各个读进程轮流从管道中读数据
- 图片

7.线程与多线程模型（♚）

线程的概念
- 线程的基本概念
  - 线程可以理解为“轻量级进程”，在引入线程后，线程是一个基本的CPU执行单元，也是程序执行流的最小单位
  - 引入线程后，进程的内涵发生了改变，进程只作为除CPU外的系统资源的分配单元，而线程则作为处理机的分配单元。
    由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。
- 引入线程的目的
  - 引入进程的目的是更好地使多道程序并发执行，提高资源利用率和系统吞吐量
    而引入线程的目的则是减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
  - 引入线程之后，不仅是进程之间可以并发，进程内的各线程之间也可以并发，从而进一步提升了系统的并发度，
    使得一个进程内也可以并发处理各种任务（如QQ视频、文字聊天、传文件）
  - 图片
线程与进程的比较（♚）
- 调度
  - 在传统的进程机制中，拥有资源和独立调度的基本单位都是进程，每次调度都要进行上下文切换，开销较大。
  - 在引入线程后，线程是独立调度的基本单位，而线程切换的代价远低于进程。
    - 此时进程仍然是资源分配的基本单位，而线程不是
  - 在同一进程中，线程的切换不会引起进程切换。但从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
- 并发性
  - 在传统的进程机制中，只能进程间并发
  - 在引入线程的操作系统中，不仅进程之间可以并发执行，而且一个进程中的多个线程之间亦可并发执行，甚至不同进程中的线程也能并发执行，从而使操作系统具有更好的并发性，提高了系统资源的利用率和系统的吞吐量。
- 拥有资源
  - 进程是系统中拥有资源的基本单位，而线程不拥有系统资源（仅有一点必不可少、能保证独立运行的资源）
    - 若线程也是拥有资源的单位，则切换线程就需要较大的时空开销，线程这个概念的提出就没有意义。
  - 线程可以与同属一个进程的其他线程共享进程所拥有的全部资源（可以访问其隶属进程的系统资源），
    这主要表现在属于同一进程的所有线程都具有相同的地址空间
  - 线程不能共享其他线程的资源
- 独立性
  - 每个进程都拥有独立的地址空间和资源，除了共享全局变量，不允许其他进程访问。
  - 某进程中的线程对其他进程不可见。同一进程中的不同线程是为了提高并发性及进行相互之间的合作而创建的，它们共享进程的地址空间和资源。
- 系统开销
  - 在创建或撤销进程时，系统都要为之分配或回收进程控制块PCB及其他资源，如内存空间、I/O设备等
    而创建线程和撤销线程时所用的开销则较小
  - 传统的进程间实现并发时，需要切换进程的运行环境，涉及进程上下文的切换，系统开销很大，
    而线程切换时只需保存和设置少量寄存器内容，开销很小。
  - 此外，由于同一进程内的多个线程共享进程的地址空间，因此这些线程之间的同步与通信非常容易实现，甚至无须操作系统的干预。
- 支持多处理机系统
  - 对于传统单线程进程，不管有多少处理机，进程只能运行在一个处理机上
  - 对于多线程进程，可以将进程中的多个线程分配到多个处理机上执行。
线程的属性
- 线程是处理机的独立调度单位，多个线程是可以并发执行的。
  - 在单CPU的计算机系统中，各线程可交替地占用CPU
  - 在多CPU的计算机系统中，各线程可同时占用不同的CPU
- 线程是一个轻型实体，它不拥有系统资源，同一进程中的各个线程共享该进程所拥有的资源
  由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
- 每个线程都应有一个唯一的标识符和一个线程控制块（TCB），线程控制块记录了线程执行的寄存器和栈等现场状态。
- 不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。
  - 同一进程中的线程切换，不会引起进程切换，不同进程中的线程切换，会引起进程切换
  - 切换同进程内的线程，系统开销很小，切换进程，系统开销较大
- 一个线程被创建后，便开始了它的生命周期，直至终止。
  线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化

8.线程的实现方式

用户级线程（ULT）
- 用户级线程的特点
  - 用户级线程由应用程序通过线程库实现，所有的线程管理工作都由应用程序负责并在用户空间中完成（包括线程切换)
    应用层序可以通过线程库设计成多线程程序
  - 用户级线程中，线程切换可以在用户态下即可完成，无需操作系统干预。
  - 在用户看来，是有多个线程。但是在操作系统内核看来，并意识不到线程的存在
  - 对于设置了用户级线程的系统，其调度仍是以进程为单位进行的，各个进程轮流执行一个时间片
- 用户级线程的优点（节省开销）
  - 线程切换在用户空间就可完成，不需要转换到内核空间，节省了模式切换的开销
  - 调度算法可以是进程专用的，不同的进程可根据自身的需要，对自己的线程选择不同的调度算法。
  - 用户级线程的实现与操作系统平台无关，对线程管理的代码是属于用户程序的一部分
- 用户级线程的缺点（并发度不高）
  - 系统调用的阻塞问题，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都被阻塞
  - 不能发挥多处理机的优势，内核每次分配给一个进程的仅有一个CPU,因此进程中仅有一个线程能执行。
- 图片
内核级线程（KLT）
- 内核级线程的特点
  - 内核级线程的管理工作由操作系统内核完成。
    线程调度、切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成。
  - 操作系统会为每个内核级线程建立相应的TCB(线程控制块)通过TCB对线程进行管理。
  - “内核级线程”就是“从操作系统内核视角看能看到的线程
- 内核级线程的优点
  - 多线程可在多核处理机上并行执行，内核能同时调度同一进程中的多个线程并行执行，
  - 如果进程中的一个线程被阻塞，内核可以调度该进程中的其他线程占用处理机，也可运行其他进程中的线程，并发能力强
  - 内核支持线程具有很小的数据结构和堆栈，线程切换比较快、开销小
  - 内核本身也可采用多线程技术，可以提高系统的执行速度和效率。
- 内核级线程的缺点
  - 一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大
- 图片
组合方式（多线程模型）
- 一对一模型
  - 一个用户级线程映射到一个内核级线程。每个用户进程有与用户级线程同数量的内核级线程。
  - 优点：当一个线程被阻塞后，别的线程还可以继续执行，并发能力强。多线程可在多核处理机上并行执行
  - 缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理的成本高，开销大。
- 多对一模型
  - 多个用户级线程映射到一个内核级线程。且一个进程只被分配一个内核级线程
  - 优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高
  - 缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行
  - 操作系统只“看得见”内核级线程，因此只有内核级线程才是处理机分配的单位。
  - 图片
- 多对多模型
  - n个用户及线程映射到m个内核级线程(n>=m)。每个用户进程对应m个内核级线程
  - 克服了多对一模型并发度不高的缺点（一个阻塞全体阻塞）
  - 又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点
  - 图片

二.处理机调度（✪）

1.调度的概念

处理机调度是对处理机进行分配，即从就绪队列中按照一定的算法(公平、高效的原则)选择一个进程并将处理机分配给它运行，以实现进程并发地执行。
调度的层次（三级调度）
- 高级调度（作业调度）
  - 内存空间有限，有时无法将用户提交的作业全部由外存放入内存
    此时按一定的原则从外存的作业后备队列中挑选一个作业调入内存，分配相关资源并创建进程。
  - 为外存与内存之间的调度，每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB。
  - 注：作业=一个具体的任务，用户向系统提交一个作业≈用户让操作系统启动一个程序（来处理一个具体的任务）
- 中级调度（内存调度）
  - 挂起状态的概念
    - 内存不够时，可将某些进程调出外存。等内存空闲或者进程需要运行时再重新调入内存。
    - 暂时调到外存等待的进程状态为挂起态。被挂起的进程PCB会被组织成挂起队列
  - 按照某种策略决定将哪个处于挂起状态的进程重新调入内存，此时修改其状态为就绪态，送入就绪队列。
  - 一个进程可能会被多次调出、调入内存，因此中级调度发生的频率要比高级调度更高。
  - 中级调度可以提高内存利用率和系统吞吐量
- 低级调度（进程、处理机调度）
  - 按照某种策略从就绪队列中选取一个进程，将处理机分配给它
  - 进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。
  - 进程调度的频率很高，一般几十毫秒一次。
- 区别
阻塞挂起与就绪挂起以及七状态模型：挂起是在外存中等待的状态

2.调度的目标

CPU利用率：指CPU“忙碌”的时间占总时间的比例。
系统吞吐量：单位时间内完成作业的数量
周转时间：是指从作业被提交给系统开始，到作业完成为止的这段时间间隔。
- 包括四个部分（后三项在一个作业的整个处理过程中，可能发生多次
  - 作业在外存后备队列上等待作业调度（高级调度）的时间
  - 进程在就绪队列上等待进程调度（低级调度）的时间
  - 进程在CPU上执行的时间
  - 进程等待I/O操作完成的时间
- 周转时间=作业完成时间一作业提交时间
- 平均周转时间=$\large\frac{各作业周转时间之和}{作业数}$
- 带权周转时间=$\large \frac{作业周转时间}{作业实际运行时间}=\frac{作业完成时间一作业提交时间}{作业实际运行时间}$（一定大于1，越小越好）
- 平均带权周转时间=$\large \frac{各作业带权周转时间之和}{作业数}$（越小越好）
- 对于周转时间相同的两个作业，实际运行时间长的作业在相同时间内被服务的时间更多，带权周转时间更小，用户满意度更高
- 对于实际运行时间相同的两个作业，周转时间短的带权周转时间更小，用户满意度更高。
等待时间：指进程/作业处于等待处理机状态时间之和，等待时间越长，用户满意度越低。
- 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间。（等待时间=周转时间-运行时间-等待I/O操作的时间）
- 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
- 处理机调度算法实际上并不影响作业执行或输入/输出操作的时间，只影响作业在就绪队列中等待所花的时间。
  因此，衡量一个调度算法的优劣，常常只需简单地考察等待时间
响应时间：指从用户提交请求到系统首次产生响应所用的时间。
- 在交互式系统中，周转时间不是最好的评价准则，一般采用响应时间作为衡量调度算法的重要准则之一

3.调度的实现

进程调度的时机
- 需要进行进程调度与切换的情况
  - 当前运行的进程主动放弃处理机
    - 进程正常终止
    - 运行过程中发生异常而终止
    - 进程主动请求阻塞(如等待I/O)
  - 当前运行的进程被动放弃处理机
    - 分给进程的时间片用完
    - 有更紧急的事需要处理(如I/O中断)
    - 有更高优先级的进程进入就绪队列
- 不能进行进程调度与切换的情况
  - 在处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换。
  - 进程在操作系统内核程序临界区中（普通的临界区可以进行进程调度）
  - 在原子操作过程中（原语），原子操作不可中断，要一气呵成（如修改PCB中进程状态标志，并把PCB放到相应队列）
进程调度的方式
- 非剥夺调度方式，又称非抢占方式
  - 即只允许进程主动放弃处理机，在运行过程中即便有更紧迫的任务到达，当前进程依然会继续使用处理机，直到该进程终止或主动要求进入阻塞态。
  - 实现简单，系统开销小但是无法及时处理紧急任务，适合于早期的批处理系统
- 剥夺调度方式，又称抢占方式。
  - 当一个进程正在处理机上执行时，如果有一个更重要或更紧迫的进程需要使用处理机，则立即暂停正在执行的进程，将处理机分配给更重要紧迫的那个进程。
  - 可以优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（通过时钟中断）。
  - 适合于分时操作系统、实时操作系统
进程的切换与过程
- 狭义的进程调度”与“广义的进程调度”的区别
  - 狭义的进程调度指的是从就绪队列中选中一个要运行的进程。
    这个进程可以是刚刚被暂停执行的进程，也可能是另一个进程，后一种情况就需要进程切换
  - 进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程。
  - 广义的进程调度包含了选择一个进程和进程切换两个步骤
- 进程切换的过程
  - 对原来运行进程各种数据的保存
  - 对新的进程各种数据的恢复
    如：程序计数器、程序状态字、各种数据寄存器等处理机现场信息，这些信息一般保存在进程控制块
- 进程切换是有代价的，因此如果过于频繁的进行进程调度与切换，必然会使整个系统的效率降低使系统大部分时间都花在了进程切换上，而真正用于执行进程的时间减少。

4.典型的调度算法（♚）

前三种算法适用于批处理系统，后三种算法适用于交互式系统
先来先服务(FCFS，First Come First Serve)
- 算法思想：主要从“公平”的角度考虑（类似于我们生活中排队买东西的例子），考虑的是等待时间
- 算法规则：按照作业/进程到达的先后顺序进行服务
- 可用于作业调度与进程调度
  - 用于作业调度时，考虑的是哪个作业先到达后备队列
  - 用于进程调度时，考虑的是哪个进程先到达就绪队列
- 是非抢占式的算法
- 优缺点
  - 优点：公平、算法实现简单
  - 缺点：排在长作业（进程）后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好。
    FCFS算法对长作业有利，对短作业不利
- 是否会导致饥饿：不会
  饥饿：某进程/作业长期得不到服务
- 有利于CPU繁忙型作业，不利于I/O繁忙型作业
短作业优先(SJF，Shortest Job First)
- 算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均平均带权周转时间
- 算法规则
  - 短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。（非抢占式）
  - 最短剩余时间优先算法
    - 每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，
      则由新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度（抢占式）
    - 图片
- 可用于作业和进程调度，用于进程调度时称为短进程优先(SPF，Shortest Process First)算法
- SJF和SPF是非抢占式的算法，但也有适用于可抢占式的算法：短剩余时间优先算法(SRTN，Shortest Remaining Time Next)
- 优点：“最短的”平均等待时间、平均周转时间
- 缺点：不公平。对短作业有利，对长作业不利。
- 会产生饥饿现象。
- SJF调度算法的平均等待时间、平均周转时间最少
高响应比优先(HRRN，Highest Response Ratio Next)
- 算法思想：要综合考虑作业/进程的等待时间和要求服务的时间
  满足短作业优先且不会导致饥饿
- 算法规则
  - 只有当前运行的程主动放弃CPU时(正常/异常完成，或主动阻塞)，才需要行调度，
    调度时计算所有就绪进程的响应比，选响应比最高进程上处理机。
  - 响应比=$\large \frac{等待时间+要求服务时间}{要求服务时间}$ (响应比≥1)
  - 图片
- 可用于作业调度与进程调度
- 是非抢占式的算法。只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比
- 优点
  - 综合考虑了等待时间和运行时间（要求服务时间）
  - 等待时间相同时，要求服务时间短的优先(SJF的优点)
  - 要求服务时间相同时，等待时间长的优先(FCFS的优点)
  - 对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题
- 不会导致饥饿
时间片轮转调度算法(RR)
- 算法思想：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应
  更注重响应时间，不计算周转时间，适用于分时系统，多个用户能及时干预系统
- 算法规则
  - 按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，
    若进程未在一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队。
  - 图片
- 只用于进程调度：只有作业放入内存建立了相应的进程后，才能被分配处理机时间片
- 属于抢占式的算法：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，回到就绪队列
  由时钟装置发出时钟中断来通知CPU时间片已到
- 优点：公平；响应快，适用于分时操作系统
- 缺点：由于高频率的进程切换，因此有一定开销且不区分任务的紧急程度
- 不会导致饥饿
- 时间片的选择
  - 如果时间片太大，使得每个进程都可以在一个时间片内就完成，
    则时间片轮转调度算法退化为先来先服务调度算法，并且会增大进程响应时间。因此时间片不能太大。
  - 如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，
    从而导致实际用于进程执行的时间比例减少。进程调度、切换是有时间代价的(保存、恢复运行环境)
优先级调度算法
- 算法思想：随着计算机的发展，特别是实时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理顺序
- 算法规则
  - 对于非抢占式的算法：每次调度时选择当前已到达且优先级最高的进程，当前进程主动放弃处理机时发生调度。
  - 对于抢占式的算法：每次调度时选择当前已到达且优先级最高的进程。当前进程主动放弃处理机时发生调度。
    另外，当就绪队列发生改变时也需要检查是会发生抢占。
- 既可用于作业调度，也可用于进程调度，还可用于I/O调度
- 抢占式、非抢占式都有。非抢占式只需在进程主动放弃处理机时进行调度即可，
  而抢占式还需在就绪队列变化时，检查是否会发生抢占。
- 优点：用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度。
- 缺点：若源源不断地有高优先级进程到来，则可能导致饥饿
- 会导致饥饿
- 关于优先级
  - 就绪队列未必只有一个，可以按照不同优先级来组织。另外，也可以把优先级高的进程排在更靠近队头的位置
  - 根据优先级是否可以动态改变，可将优先级分为静态优先级和动态优先级两种
    - 静态优先级：创建进程时确定，之后一直不变
    - 动态优先级：创建进程时有一个初始值，之后会根据情况动态地调整优先级
  - 优先级的设置
    - 系统进程优先级高于用户进程
    - 前台进程优先级高于后台进程（交互型进程>非交互型进程）
    - I/O型进程(或称I/O繁忙型进程)优先级高于计算型进程(或称CPU繁忙型进程)
      - 操作系统更偏好I/O型进程，I/O设备（如打印机）的处理速度要比CPU慢得多，
        因此若将I/O型进程的优先级设置得更高，就更有可能让I/O设备尽早开始工作，
      - I/O设备和CPU可以并行工作。如果优先让I/O繁忙型进程运行则越有可能让I/O设备尽早地投入工作，
        则资源利用率、系统吞吐量都会得到提升，进而提升系统的整体效率。
  - 采用动态优先级时，何时调整（可以从追求公平、提升资源利用率等角度考虑）
    - 如果某进程在就绪队列中等待了很长时间，则可以适当提升其优先级
    - 如果某进程占用处理机运行了很长时间，则可适当降低其优先级
    - 如果发现一个进程频繁地进行I/O操作，则可适当提升其优先级
多级反馈队列调度算法
- 算法思想：对其它调度算法的折中权衡，不必事先估计进程的执行时间
- 算法规则
  - 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
  - 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾
  - 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
- 用于进程调度
- 是抢占式的算法。在k级队列的进程运行过程中，若更上级的队列(1~k-1级)中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾。
- 优点
  - 对各类型进程相对公平(FCFS的优点)
  - 每个新到达的进程都可以很快就得到响应(RR的优点)
  - 短进程只用较少的时间就可完成(SPF的优点)
  - 不必实现估计进程的运行时间（避免用户作假）
  - 可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程
    可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先级
- 会导致饥饿
几种进程调度算法的区别
例题
- 例1，通过画甘特图来求解
- 例2，在操作系统中CPU计算和I/O操作可以同时进行
- 例3，如果单独说输入设备和输出设备的话，那么这三种设备是可以并行进行的
- 例4，关于多级队列的题目

三.同步与互斥（✪）

1.同步与互斥的基本概念

进程同步：进程具有异步性的特征。异步性：各并发执行的进程以各自独立的、不可预知的速度向前推进。
操作系统要提供“进程同步机制”来解决异步问题
临界资源
- 临界资源的概念
  - 共享是操作系统的基本特征之一，资源共享的方式分为了同时共享方式和互斥共享方式
    互斥共享方式指：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源
  - 临界资源：一个时间段内只允许一个进程使用的资源，属于互斥共享资源
  - 许多物理设备(比如摄像头、打印机)都属于临界资源。共享变量、公用队列、内存缓冲区等都属于临界资源。
    非共享数据不属于临界资源（私有的），在一段时间内能被并发使用的资源不属于临界资源，如可重入的程序代码
  - 对临界资源的访问，必须互斥地进行。
    - 互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。
    - 当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
    - 例题：此时两个进程内部的线程同享变量x；对于A/B选项，两段代码执行顺序的先后不影响最终的结果，D跨越进程不是；因此选C（执行顺序先后会影响结果）
- 临界资源的访问过程
  - 进入区：负责检查是否可进入临界区，若可进入，则应设置正在访问临界资源的标志
    可理解为“上锁”，以阻止其他进程同时进入临界区
  - 临界区：也可称为临界段，临界区是进程中访问临界资源的代码段
  - 退出区：负责解除正在访问临界资源的标志(可理解为“解锁”)
  - 剩余区：代码中的其它部分
  - 进入区和退出区是负责实现互斥的代码段
  - 代码
    1
    2
    3
    4
    5
    6
    do{
    entry section; //进入区（上锁）
    critical section; //临界区（访问临界资源）
    exit section; //退出区（解锁）
    remainder section; //剩余区
    }while(true)
同步机制的规则
- 空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
- 忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待
- 有限等待：对请求访问的进程，应保证能在有限时间内进入临界区（保证不会饥饿）
- 让权等待：当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。

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

软件实现方法

单标志法（谦让）

算法思想
- 该算法设置一个公用整型变量，用于指示被允许进入临界区的进程编号，若为0则允许P0进程进入临界区。该算法可确保每次只允许一个进程进入临界区。
- 两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程。也就是说每个进程进入临界区的权限只能被另一个进程赋予
- 因此，该算法可以实现“同一时刻最多只允许一个进程访问临界区”

代码与运行逻辑

int turn=0; //turn 表示当前允许进入临界区的进程号，初始值设为0，允许P0进程访问
//P0进程：               //P1进程：     
while(turn!=0);			while(turn!=1);	//检查，如果不能由自己使用则一直循环等待（只检查，不上锁）	
critical section;		critical section;	
//退出区，此时将使用权转交给另一个进程（相当于在退出区既给另一进程“解锁”，又给自己“上锁”）
turn=1;					turn=0;	
remainder section;		remainder section;

算法的特点：该算法可确保每次只允许一个进程进入临界区。但两个进程必须交替进入临界区。
若某个进程不再进入临界区，则另一个进程也将无法进入临界区(违背“空闲让进”)。这样很容易造成资源利用不充分。

双标志先检查法（表达访问意愿）

算法思想
- 在每个进程访问临界区资源之前，先查看临界资源是否正被访问，若正被访问，该进程需等待；
  否则，进程才进入自己的临界区。
- 为此，设置一个布尔型数组flag，如第i个元素flag[i]为FALSE，表示Pi进程未进入临界区，
  如为TRUE，表示Pi进程进入临界区

代码与运行逻辑

bool flag[2];       //创建表达意愿的数组
flag[0]=false;		//刚开始两个进程都没有意愿进入临界区
flag[1]=false;
Pi进程：				Pj进程：	
//在进入区先"检查"后"上锁”
while(flag[j]);		  while(flag[i]);//检查对方是否在访问临界资源,如果在则一直循环等待,
flag[i]=TRUE;         flag[j]=TRUE;	//如果临界资源没有被访问则上锁，表达访问意愿
critical section;	  critical section;
flag[i]=FALSE;		  flag[j]=FALSE;   //访问结束之后开锁
remainder section;	  remainder section;

优点：不用交替进入，可连续使用
缺点：可能将将会同时访问临界区。违反“忙则等待”原则。
原因在于，进入区的“检查”和“上锁”两个处理不是一气呵成的。“检查”后，“上锁”前可能发生进程切换。

双标志后检查法（先斩后奏）

算法思想：在前一个算法的基础上实现先上锁再检查，可以确保同一时间内最多只有一个进程访问临界资源

代码与运行逻辑

P进程：
//在进入区先“加锁"后“检查”
flag[i]=TRUE;   //要访问临界区时先上锁，表达访问意愿
while(flag[j]);   //此时再来检查是否临界区被人使用
critical section;
flag[i]=FALSE;		//访问结束之后，开锁
remainder section;

算法的缺点
- 两个进程几乎同时都想进入临界区时，它们分别将自己的标志值flag设置为TRUE，并且同时检测对方的状态
  执行while语句，发现对方也要进入临界区时，此时谁也进不了临界区
- 双标志后检查法虽然解决了“忙则等待”的问题，但是又违背了“空闲让进”和“有限等待”原则，
  会因各进程都长期无法访问临界资源而产生“饥饿”现象。

Peterson算法（结合以上算法的特点）

算法思想
- 结合双标志法、单标志法的思想。如果双方都争着想进入临界区，那可以让进程尝试“孔融让梨”（谦让）
  做一个有礼貌的进程
- 此时最后表示谦让的一方失去主动权，则另外一方将执行

代码与运行逻辑

bool flag[2];   //表示进入临界区意愿的数组，初始值都是false
int turn 0;    //turn表示优先让哪个进程进入临界区（表达谦让）
//P0进程：
flag[0]=true;     //表示自己想进入临界区
turn=1;			 //主动谦让，给对方优先信号
while(flag[1]&&turn==1); //检查对方是否也想使用，如果对方不想使用则自己使用；如果对方想使用且表达了其谦让意愿（最后一次）则自己使用；
critical section;
flag[0]=false;   //访问完临界区之后表达自己不想使用了
remainder section;

//P1进程：e
flag[1]=true;
turn=0;
while (flag[0]&&turn==0); //只有同时满足对方想要使用且自己是最后的谦让方时，此时才开始等待
critical section;
flag[1]=false;
remainder section;

算法的特点：Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待的原则，
但是依然未遵循让权等待的原则（不能进入临界区时还在还在处理机上，造成忙等待）。

硬件实现方法

中断屏蔽方法
- 利用“开/关中断指令”实现，与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，
  也就不能发生进程切换，因此也不可能发生两个同时访问临界区的情况
- 优点：简单、高效
- 缺点：不适用于多处理机；只适用于操作系统内核进程，不适用于用户进程，
  开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用会很危险

硬件指令方法

TestAndSet指令（TSL指令)

指令思想
- TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
- 若刚开始Iock是false，则TSL返回的old值为false，while循环条件不满足，直接跳过循环，进入临界区。
- 若刚开始Iock是true，则执行TLS后old返回的值为true，while循环条件满足，会一直循环，
  直到当前访问临界区的进程在退出区进行“解锁”。

代码逻辑

//布尔型共享变量lock表示当前临界区是否被加锁
//true表示已加锁，false表示末加锁
bool TestAndSet (bool *lock){
bool old;
oLd=*Lock;     //old用来存放Lock原来的值
*Lock=true;    //无论之前是否已加锁，都将Lock设为true
return old;    //返回Lock原来的值
}
//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock);// 实现"上锁并"检查"
临界区代码段
lock false;   //解锁
剩余区代码段

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

SWAP指令

指令思想
- Swap指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。
- 逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old上），
  再将上锁标记Iock设置为true，最后检查old
- 如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区。

代码逻辑

//Swap指令的作用是交换两个变量的值
Swap (bool *a,bool *b){
bool temp;
temp =*a;
*a=*b;
*b temp;
}

//以下是用Swap指令实现互斥的算法逻辑
//1ock表示当前临界区是否被加锁
bool old true;
while (old==true)
	Swap (&lock,&old);
临界区代码段，，，
lock false;
剩余区代码段，，，

优点：实现简单，无需像软件实现方法那样严格检查是否会有逻辑漏洞；适用于多处理机环境
缺点：不满足“让权等待”原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致“忙等”。

3.信号量（♚）

信号量的概念
- 信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，
  可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。
- 信号量的分类
  - 信号量是一个特殊的整型变量，只有初始化和PV操作才能改变其值。通常，信号量分为互斥量和资源量
  - 互斥量的
    - 初值一般为1，表示临界区只允许一个进程进入，从而实现互斥。
    - 当互斥量等于0时，表示临界区已有一个进程进入，临界区外尚无进程等待
    - 当互斥量小于0时，表示临界区中有一个进程，互斥量的绝对值表示在临界区外等待进入的进程数。
  - 资源信号量
    - 初值可以是任意整数，表示可用的资源数
    - 当资源量小于0时，表示所有资源已全部用完，而且还有进程正在等待使用该资源，等待的进程数就是资源量的绝对值。
- PV操作的概念
  - 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，可以满足在进入区，退出区的操作一气呵成，
    从而很方便的实现了进程互斥、进程同步。
  - wait(S)原语和signal(S)原语，wait、signal原语常简称为P、V操作，可以分别写为P(S)、V(S)
  - PV操作是一种低级进程通信原语，由两个不可被中断的过程组成，但不是系统调用命令

整型信号量（非重点）

代码逻辑

整型信号量被定义为一个用于表示资源数目的整型量S

wait(S){	//wait原语，相当于“进入区”
	while(S<=0);  //如果资源数不够，就一直循环等待
	S=S-1;   //如果资源数够，则占用一个资源
}
signal(S){  //signal原语，相当于“退出区”
	S=S+1;	//使用完资源后，在退出区释放资源
}

优点：检查”和“上锁”一气呵成避免了并发、异步导致的问题
存在的问题：不满足让权等待原则，会发生“忙等”

记录型信号量（♛）

记录型信号量的定义以及申请资源和释放资源

P操作中，一定是先S.value—，之后可能需要执行block原语
V操作中，一定是先S.value++，之后可能需要执行wakeup原语

typedef struct{
    int value; //剩余资源数，S.value的初值表示系统中某种资源的数目
    struct process *L;  //定义等待队列
}semaphore;   //记录型信号量的定义

//P操作：wait(s):某进程需要使用资源时 用wait原语申请资源
void wait(semaphore S){
    S.value--;  
    if(S.value<0){
        block(S.L); //如果剩余资源数不够，则使用block原语使进程从运行态进入阻塞态，并把其挂到信号量S的等待队列中（阻塞队列）
    }
}

//V操作：进程使用完资源后，通过signal原语释放
void signal(semaphore S){
    S.value++;
    if(S.value<=0){
        wakeup(S.L);  //释放资源后，若还有别的进程在等待这种资源，则使用wakeup原语唤醒等待队列中一个进程,该进程从阻塞态变为就绪态
    }
}

该机制遵循了“让权等待”原则，不会出现“忙等”现象

利用信号量实现进程互斥

过程
- 分析并发进程的关键活动，划定临界区(如：对临界资源打印机的访问就应放在临界区)
- 设置互斥信号量mutex，初值为1，（信号量表示进入临界区的名额）对不同的临界资源需要设置不同的互斥信号量。
- 在临界区之前对信号量实行P操作，在临界区之后对信号量实行V操作，P、V操作必须成对出现

代码逻辑

semaphore mutex=1;//初始化信号量

P1(){
P(mutex); //使用临界资源前需要加锁，信号量减一表示占用了一个名额
临界区代码段,,,
V(mutex);//使用临界资源后需要解锁，信号量加一表示归还了一个名额，若此时信号量小于等于零，则将阻塞队列中的进程唤醒进入就绪队列
}

P2(){
P(mutex);//在没有访问临界区的名额时，此时将进入阻塞态（信号量减一后小于0则会触发阻塞）
临界区代码段,,,
V(mutex);
}

利用信号量实现同步

过程
- 进程同步问题是让本来异步并发的进程互相配合，有序推进。
  需要分析什么地方需要实现“同步关系”，即必须保证“一前一后”执行的两个操作
- 设置同步信号量S，初始为0，信号量S代表“某种资源”，刚开始是没有这种资源的。
  P2需要使用这种资源，而又只能由P1产生这种资源
- 在“前操作”之后执行V(S)，在“后操作”之前执行P(S)，前V后P

代码逻辑

semaphore S=0;//初始化同步信号量，初始值为0
//此时可以保证代码4一定在代码2之后执行
P1(){ 			P2(){		
代码1;		   P(S);//如果不按照顺序来执行的话，此时信号量减一后将会由于信号量小于等于0而被阻塞
代码2;		   代码4;
V(S);			}
//执行完V操作之后，信号量才能由0变为1
//如果执行完V操作之后，发现信号量小于等于0，说明已经有进程尝试先发运行，则通过唤醒原语将被阻塞的进程变为就绪态
代码3;
}

利用信号量实现前驱关系

4.管程

引入管程的目的：解决信号量机制编程麻烦，易出错的问题
管程是由编程语言支持的进程同步机制
管程的组成
- 局部于管程的共享数据结构说明
- 对该数据结构进行操作的一组过程（函数）
- 对局部于管程的共享数据设置初始值的语句
基本特征
- 局部于管程的数据只能被局部于管程的过程所访问
- 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
- 每次仅允许一个进程在管程内执行某个内部过程。
补充
- 管程是被进程调用的，管程是语法范围，无法创建和撤销
- 各进程必须互斥访问管程的特性是由编译器实现的
- 可在管程中设置条件变量及等待/唤醒操作以解决同步问题

5.经典同步问题（♚）

生产者-消费者问题

问题分析
- 系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，
  消费者进程每次从缓冲区中取出一个产品并使用。(注：这里的“产品”理解为某种数据)
- 生产者、消费者共享一个初始为空、大小为n的缓冲区。
  缓冲区是临界资源，各进程必须互斥地访问
- 只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待
- 只有缓冲区不空时，消费者才能从中取出产品，否则必须等待

代码逻辑

实现互斥是在同一进程中进行PV操作
实现两进程的同步关系，是在其中一个进程中执行P，另外一个进程中执行V（一前一后，前V后P）

四.死锁（✪）

1.死锁的概念

死锁、饥饿与死循环
- 死锁：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象
  发生死锁后若无外力干涉，这些进程都将无法向前推进
- 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象。
  比如：在短进程优先(SPF)算法中，若有源源不断的短进程到来，则长进程将一直得不到处理机，从而发生长进程“饥饿”
- 死循环：某进程执行过程中一直跳不出某个循环的现象。有时是因为程序逻辑bug导致的，有时是程序员故意设计的。
- 三者的区别
死锁产生的必要条件
- 产生死锁必须同时满足一下四个条件，只要其中任一条件不成立，死锁就不会发生。
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁 (如哲学家的筷子、打印机设备)
  像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的（因为进程不用阻塞等待这种资源）
- 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，
  此时请求进程被阻塞，但又对自己己有的资源保持不放。只需要一个资源的进程不会进入死锁
- 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求
  死锁发生至少有两个进程
  - 发生死锁时一定有循环等待，但是发生循环等待时未必死锁
  - 如果同类资源数大于1，则即使有循环等待，也未必发生死锁
  - 但如果系统中每类资源都只有一个，那循环等待就是死锁的充分必要条件了
死锁产生的原因（对不可剥夺资源的不合理分配，可能导致死锁）
- 对系统资源的竞争
  - 各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源(CPU)的竞争是不会引起死锁的
- 进程推进顺序非法，请求和释放资源的顺序不当，也同样会导致死锁。
  - 如并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1
    两者会因为申请的资源被对方占有而阻塞，从而发生死锁。
- 信号量的使用不当也会造成死锁。
  - 如生产者消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。
    可以把互斥信号量、同步信号量也看做是一种抽象的系统资源
死锁的处理策略
- 不允许死锁发生
  - 静态策略：预防死锁，破坏死锁产生的四个必要条件中的一个或几个。
  - 动态策略：避免死锁，用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）
- 允许死锁发生
  - 死锁的检测和解除，允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
- 预防死锁和避免死锁都属于事先预防策略，预防死锁的限制条件比较严格，实现起来较为简单，但往往导致系统的效率低，资源利用率低，
  避免死锁的限制条件相对宽松，资源分配后需要通过算法来判断是否进入不安全状态，实现起来较为复杂。
例题（✪）
- 重要定则：n个进程，每个进程需要k个资源，则当总资源数至少为$n(k-1)+1$时，不会发生死锁
- 例2，本题即为各自需要的资源数-1之和再加一：2+3+4+1=10
- 例3，此时结合题目来看，算出至少得资源数为3*(2-1)+1=4，此时所拥有的资源数刚好满足，不会发生死锁
- 例4，本题选C，此时为循环等待的经典例子

2.死锁的预防

破坏互斥条件（无法破坏）
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁。
  如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。
- 操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备
- 缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。
破坏不剥夺条件
- 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
- 方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。
  即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
- 方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。
  这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
- 策略的缺点
  - 实现起来比较复杂
  - 释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU.
  - 反复地申请和释放资源会增加系统开销，降低系统吞吐量
  - 若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。
    如果一直发生这样的情况，就会导致进程饥饿。
破坏请求和保持条件
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，
  此时请求进程被阻塞，但又对自己已有的资源保持不放。
- 可以采用静态分配方法，即进程在运行前一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。
  一旦投入运行后，这些资源就一直归它所有，该进程就不会再请求别的任何资源了。
- 该策略的缺点
  - 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一直保持着所有资源，就会造成严重的资源浪费，资源利用率极低。
  - 该策略也有可能导致某些进程饥饿
破坏循环等待条件
- 循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求。
- 可采用顺序资源分配法。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完，限制用户申请资源的顺序
- 原理分析
  - 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。
    按此规则，已持有大编号资源的进程不可能逆向地回来申请小编号的资源，从而就不会产生循环等待的现象
  - 在任何一个时刻，总有一个进程拥有的资源编号是最大的，那这个进程申请之后的资源必然畅通无阻。
    不可能出现所有进程都阻塞的死锁现象
- 该策略的缺点
  - 不方便增加新的设备，因为可能需要重新分配所有的编号
  - 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费
  - 必须按规定次序申请资源，用户编程麻烦。

3.死锁避免（♚）

安全序列与安全状态
- 安全序列是指如果系统按照这种序列分配资源，则每个进程都能顺利完成，安全序列可能有多个。
- 只要能找出一个安全序列，系统就是安全状态。如果分配了资源之后，系统中找不出任何一个安全序列，
  系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。
- 当如果有进程提前归还了一些资源，那系统也有可能重新回到安全状态，不过在分配资源之前总是要考虑到最坏的情况。
安全状态与死锁的联系
- 如果系统处于安全状态，就一定不会发生死锁。如果系统进入不安全状态，就可能发生死锁
  处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态
- 因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。
  这也是“银行家算法”的核心思想。
银行家算法
- 核心思想（避免系统进入不安全状态）
  - 在每次进行资源分配时，它首先检查系统是否有足够的资源满足要求，若有则先进行试分配，并对分配后的新状态进行安全性检查。
  - 在试分配时，利用安全性算法判断此次分配是否会导致系统进入不安全状态。
    若新状态安全，则正式分配上述资源，如果会进入不安全状态，就暂时不答应这次请求，让该进程先阻塞等待。
  - 银行家算法只能避免系统进入死锁，不能用于判断系统是否处于死锁
- 银行家算法手算规则（核心是找到安全序列）
  - 首先可以找到P1,P3满足当前剩余分配的资源，可以顺利分配并回收资源，此时将P1/P3加入安全序列
  - 回收之后，即可以满足所有的需求，此时得出安全序列，说明处于安全状态，不会发生死锁
- 银行家算法的数据结构描述（系统中有n个进程,m种资源）
  - 可利用资源向量Available
    - 含有m个元素的数组，其中每个元素代表一类可用的资源数目。$Available[j]=K$表示系统中现有$R_j$类资源$K$个
  - 最大需求矩阵Max
    - n×m矩阵，定义系统中n个进程中的每个进程对m类资源的最大需求。
    - 一行代表一个进程，一列代表一类资源，$Max[i,j]=K$表示进程$i$需要$R_j$类资源的最大数目为K.
  - 分配矩阵Allocation
    - n×m矩阵，定义系统中每类资源当前已分配给每个进程的资源数。
    - $Allocation[i,j]=K$表示进程$i$当前已分得$R_j$类资源的数目为K。
  - 需求矩阵Need
    - n×m矩阵，表示每个进程接下来最多还需要多少资源。
    - $Need[i,j]=K$表示进程$i$还需要$R_j$类资源的数目为K.
  - 上述三个矩阵间存在下述关系：$Need=Max-Allocation$
  - 图片
- 银行家算法步骤（给出一个请求：Request）
  - 检查此次申请是否超过了之前声明的最大需求数（Need）
  - 检查此时系统剩余的可用资源是否还能满足这次请求（Available）
  - 试探着分配，更改各数据结构
    - Available=Available-Request
    - Allocation=Allocation+Request
    - Need=Need-Request
  - 用安全性算法检查此次分配是否会导致系统进入不安全状态，若安全，才正式分配
    否则，恢复相应数据，让进程阻塞等待。
- 安全性算法步骤
  - 检查当前的剩余可用资源是否能满足某个进程的最大需求，如果可以，就把该进程加入安全序列，
    并把该进程持有的资源全部回收。不断重复上述过程，看最终是否能让所有进程都加入安全序列。

4.死锁检测与解除

在死锁的检测和解除中，系统为进程分配资源时不采取任何措施，但提供死锁的检测和解除手段
死锁检测
- 检测死锁的方法
  - 用某种数据结构来保存资源的请求和分配信息
  - 提供一种算法，利用上述信息来检测系统是否已进入死锁状态
- 资源分配图
  - 用圆圈代表一个进程，用框代表一类资源
  - 由于一种类型的资源可能有多个，因此用框中的一个圆代表一类资源中的一个资源。
  - 从进程到资源的有向边称为请求边，表示该进程申请一个单位的该类资源；
  - 从资源到进程的边称为分配边，表示该类资源已有一个资源分配给了该进程
  - 图片
    - 进程P1已经分得了两个R1资源，并又请求一个R2资源；
      进程P2分得了一个R1资源和一个R2资源，并又请求一个R1资源
- 死锁检测算法
  - 在资源分配图中，找出既不阻塞又不是孤点的进程P
    即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中己有空闲资源数量（资源数量-出度）
  - 若所有的连接该进程的边均满足上述条件，则这个进程能继续运行直至完成，然后释放它所占有的所有资源
    消去它所有的请求边和分配边，使之称为孤立的结点。
  - 进程P所释放的资源，可以唤醒某些因等待这些资源而阻塞的进程，原来的阻塞进程可能变为非阻塞进程。
    进行一系列简化后，若能消去途中所有的边，则称该图是可完全简化的。
  - 如果最终不能消除所有边，那么此时就是发生了死锁，最终还连着边的那些进程就是处于死锁状态的进程
    资源分配图是不可完全简化的，称为死锁定理
  - 死锁的充分必要条件是每种资源只有一个，并出现环路
  - 图片
死锁解除
- 资源剥夺法：挂起（暂时放到外存上）某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。
  但是应防止被挂起的进程长时间得不到资源而饥饿。
- 撤销进程法（或称终止进程法）
  - 强制撤销部分、甚至全部死锁进程，并剥夺这些进程的资源。这种方式的优点是实现简单，但所付出的代价可能会很大
    因为有些进程可能己经运行了很长时间，已经接近结束了，一旦被终止可谓功亏一篑，以后还得从头再来。
- 进程回退法。让一个或多个死锁进程回退到足以避免死锁的地步。这就要求系统要记录进程的历史信息，设置还原点。

操作系统第二章 进程与线程

一.进程与线程（✪）

1.进程的概念

2.进程的组成

3.进程的特征

4.进程的状态与转换（♚）

5.进程控制（♚）

6.进程的通信

7.线程与多线程模型（♚）

8.线程的实现方式

二.处理机调度（✪）

1.调度的概念

2.调度的目标

3.调度的实现

4.典型的调度算法（♚）

三.同步与互斥（✪）

1.同步与互斥的基本概念

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

3.信号量（♚）

4.管程

5.经典同步问题（♚）

四.死锁（✪）

1.死锁的概念

2.死锁的预防

3.死锁避免（♚）

4.死锁检测与解除

操作系统第二章进程与线程