操作系统-理论-进程和线程

进程与线程

真并行与假并行

并行与并发

并发Concurrent：设有两个活动a1和a2，如果在某一指定的时间t，无论a1和a2是在同一处理机上还是在不同的处理机上执行，只要a1和a2都处在各自的起点和终点之间的某一处，则称a1和a2是并发执行的。

并行Parallel：如果考虑两个程序,它们在同一时间度量下同时运行在不同的处理机上，则称这两个程序是并行执行的。

对于并发执行：程序的并发执行是指若干个程序（或程序段）同时在系统中运行，这些程序（或程序段）的执行在时间上是重叠的。所谓执行在时间上是重叠的，是指执行一个程序（或程序段）的第一条指令是在执行另一个程序（或程序段）的最后一条指令完成之前开始。

程序并发执行时的特征：

• 间断性：并发程序具有“执行—暂停—执行”这种间断性的活动规律。
• 非封闭性：多个程序共享系统中的资源，这些资源的状态将由多个程序来改变，致使程序之间相互影响。
• 不可再现性：在初始条件相同的情况下，程序的执行结果依赖于执行的次序。

前驱图

程序在运行过程中会有相应的数据依赖，如B的执行必须依赖于A，也就是A必须在B之前完成，写作A->B。

前趋图是一个有向无循环图，图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示语句或程序段的执行次序。

只要保证相应的依赖关系即可，但由于OS调度策略不是一直不变的，具体的执行先后可能有所不同。

这是因为数据的竞争

竞争

竞争：多个进程在读写共享数据时的结果依赖于执行的相对时间

竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关

如果关注并发是否有确定的结果，那么需要关注数据的其他特性是否满足Bernstein条件

$R(Si)$：Si的读子集, 其值在Si中被引用的变量的集合

$W(Si)$：Si的写子集, 其值在Si中被改变的变量的集合

两个进程S1和S2可并发，当且仅当下列条件同时成立：

• $R(S1) \cap W(S2) = \Phi$
• $W(S1) \cap R(S2) = \Phi$
• $W(S1) \cap W(S2) = \Phi$​
• 即没有任何读写冲突

进程

==进程是程序的一次执行==，是在行为上的一个动作，包含了行为本身和行为相应的数据。其数据包括程序及相应的数据，是一个程序及其数据，在处理机上顺序执行时所发生的活动。

作为行为的抽象，进行是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。

进程的结构特征：程序段、数据段、进程控制器PCB

进程应该包括：

1. 程序的代码
2. 程序的数据
3. PC的值，用来表明下一条执行的指令
4. 上下文环境：一组通用寄存器的值、堆、栈
5. 一组系统资源（如打开的文件）

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

• 动态性：进程是程序的一次执行过程。动态性还表现为它因创建而产生，因调度而执行，因无资源而暂停，因撤消而消亡。而程序是静态实体。
• 并发性：多个进程实体同时存在于内存中，能在一段时间内同时运行。
• 独立性：在传统OS中，进程是独立运行的基本单位
• 异步性：也叫制约性，进程之间相互制约，进程以各自独立的不可预知的速度向前推进。
• 结构特征：程序段，数据段，进程控制块PCB

进程控制

进程控制主要任务是创建和撤销进程，以及实现进程的状态转换。由OS的内核实现。

创建进程的方法：

1. 提交一个批处理作业
2. 用户登录
3. 由OS创建，用以向一用户提供服务
4. 由已存在的一进程创建

撤销进程的方法：

1. 用户退出登录
2. 进程执行一中止服务请求
3. 出错及失败因素
4. 正常结束
5. 给定时限到

原语

原语：由若干条指令组成的指令序列，来实现某个特定的操作功能。

• ==指令序列执行是连续的，不可分割==
• 是操作系统核心组成部分
• 必须在内核态下执行，且常驻内存

创建原语：fork, exec

• 可以通过fork返回的值来判断当前进程是子进程还是父进程。
  • 在父进程中，fork返回新创建子进程的进程ID；
  • 在子进程中，fork返回0；
  • 如果出现错误，fork返回一个负值；
  • ==fork返回两次，有三种可能的取值==
• 父进程的fpid指向子进程的进程id, 子进程没有子进程，所以其fpid为0.

撤消原语：kill

• 释放资源、撤消子进程、重新调度。

进程的状态

• 就绪状态：进程已获得除处理机外的所需资源，等待分配处理机资源，只要分配CPU就可执行。

• 执行状态：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。

  在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。

• 阻塞状态：正在执行的进程，由于发生某种事件而暂时无法执行，便放弃处理机处于暂停状态。

• 就绪–>运行
  • 时间一到，调度程序选择一个进程运行
• 运行–>就绪
  • 运行进程用完了时间片
  • 运行进程被中断，因为==一高优先级进程处于就绪状态==
• 运行–>阻塞
  • 当一进程所需的东西必须等待时
  • OS尚未完成服务
  • 对一资源的访问尚不能进行
  • 初始化IO且必须等待结果
  • 等待某一进程提供输入（IPC）
• 阻塞–>就绪
  • 当所等待的事件发生时

进程控制块PCB

怎么实现进程机制：进程创建、进程管理、进程终止、进程的状态切换

OS为每个进程定义了一个数据结构：进程控制块PCB

进程控制块是进程管理和控制的最重要的数据结构，每一个进程均有一个PCB。在创建进程时，建立PCB，伴随进程运行的全过程，直到进程撤消而撤消。

系统中有相应的指针指向PCB，来戴白哦起到作用的PCB，如运行指针、就绪队列指针等。

PCB的作用

• 进程创建、撤销
• 进程的唯一标志
• 限制系统进程数目

PCB的内容

• 进程标识符:
  • 每个进程都必须有一个唯一的标识符，可以是字符串，也可以是一个数字。
  • Linux系统中就是一个整型数。在进程创建时由系统赋予。
• 程序和数据地址:
  • 把PCB与其程序和数据联系起来。记录到哪里寻找数据和程序
• 当前状态：
  • 为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列。
  • 等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘IO完成队列等等。
• 现场保护区:
  • 当进程因某种原因不能继续占用CPU时（等待打印机），释放CPU，这时就要将CPU的各种状态信息保护起来，为将来再次得到处理机恢复CPU的各种状态，继续运行。
• 同步与同步机制：
  • 用于实现进程间互斥、同步和通信所需的信号量等。
• 优先级：
  • 进程的优先级反映进程的紧迫程序，通常由用户指定和系统设置。Linux系统采用用户设置和系统计算相结合的方式确定进程的优先级。
• 资源清单：
  • 列出所拥有的除CPU外的资源记录，如拥有的IO设备，打开的文件列表等。
• 链接字：
  • 根据进程所处的现行状态，进程相应的PCB参加到不同队列中。PCB链接字指出该进程所在队列中下一个进程PCB的首地址。
• 其他信息：
  • 如进程记账信息，进程占用CPU的时间等。

PCB的组织方式

用PCB管理进程：本质是控制了OS执行的程序地址，相关的数据地址，实现了对进程的管理

• 线性表

  • 线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。

  • 这种方式适用于系统中进程数目不多的情况。

    

• 链接方式

  • 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立不同的表，如就绪索引表、阻塞索引表等。

    

• 索引方式

  • 链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。

    

进程上下文切换

执行不同的进程进行切换时，通常由调度器执行，保存进程的执行断点，切换相应的内存映射（页表基址，冲刷TLB），故一定会陷入内核。

系统调用涉及到进程从用户态到内核态的切换（mode switch），这个时候涉及到的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换不同，mode switch 的消耗相对要小很多。

线程

• 进程是OS中行为的抽象，是一个行为，无法同时做多件事。
• 进程在执行的过程中如果阻塞，例如等待输入，整个进程就会挂起，即使进程中有些工作不依赖于输入的数据，也将无法执行。

需要提出一种新的实体，满足以下特性：

• 实体之间可以并发地执行；
• 实体之间共享相同的地址空间；

进程获取了相应的资源，将对资源的执行进行更细粒度的划分：线程。

引入进程好处：多个程序可以并发执行，改善资源使用率，提高系统效率

引入线程好处：减少并发程序执行时所付出的时空开销，使得并发粒度更细、并发性更好

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

线程的基本概念

进程包含了两个概念：资源拥有者和可执行单元。现代操作系统将资源拥有者称为进程（process, task）。可执行单元称为线程（Thread）。

线程：将资源与计算分离，提高并发效率。

• 减小进程切换的开销（线程切换不用陷入内核，陷入内核开销较大）
• 提高进程内的并发程度
• 共享资源（同一进程的线程之间可以共享==进程拥有的所有资源==）

线程是进程中的一个实体，是CPU调度和分派的单位。基本上不拥有资源，可与其他线程共享资源。

线程VS进程

进程拥有虚空间、进程映像、处理机保护、文件、IO空间。

线程额外的资源：运行状态、保存上下文（程序计数器）、执行栈、资源共享机制。

• 一个进程可以拥有多个线程，而一个线程只能被一个进程拥有
• ==进程是资源分配的基本单位，线程是处理机调度的基本单位，所有的线程共享其所属进程的所有资源与代码。==
• ==线程执行过程之中很容易进行协作同步，而进程需要通过消息通信进行同步。==
• ==线程不能单独执行，但是每一个线程都有程序的入口、执行序列以及程序出口。它必须组成进程才能被执行。==

线程的实现方式

• 用户级线程：User level threads（ULT）
• 内核级线程：Kernel level threads（KLT）
• 混合实现方式

用户级线程

由用户手管理的线程。线程在用户空间，通过library模拟的thread，不需要或仅需要极少的kernel支持

上下文切换很快：不用修改页表

下图很关键：

用户级线程的优劣：

• 优点
  • 线程切换与内核无关，不用修改页表，效率较高
  • 线程的调度由应用决定，容易进行优化
  • 可运行在任何操作系统上，只需要线程库的支持
• 不足
  • 很多系统调用会引起阻塞，内核会因此而阻塞所有相关的线程。
  • 内核只能将处理器分配给进程，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行。

用户级的线程库的主要功能：

• 创建和销毁线程
• 线程之间传递消息和数据
• 调度线程执行
• 保存和恢复线程上下文

标准库是pthread

• pthread_create()：创建线程
• pthread_exit()：终止线程
• pthread_join()：阻塞线程
• pthread_yield()：释放锁等待
• pthread_attr_init()：对线程的属性进行初始化
• pthread_attr_destory()：销毁线程的属性

内核级线程

OS内核态本身就有多个线程执行相关任务，可以将用户的多个线程在内核也是真正的多线程执行。支持内核线程的操作系统内核称作多线程内核。

下图很关键：

优劣：

• 优点
  • 内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
  • 阻塞发生在线程级别
  • 内核中的一些处理可以通过多线程实现
• 缺点
  • 一个进程中的线程切换需要内核参与，线程的切换涉及到两个模式的切换（进程-进程、线程-线程）
  • 降低效率

用户级和内核级的比较

用户级线程的创建、撤消和调度不需要OS内核的支持，是在语言或用户库这一级处理的；而内核支持线程的创建、撤消和调度都需OS内核提供支持，而且与进程的创建、撤消和调度大体是相同的。

用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。

在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。

用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。

混合实现方式

线程在用户空间创建和管理。需要实现从用户空间的线程到内核空间线程（轻量级进程）的映射。

线程模型

内核级和用户级的连接关系。

Many-to-One

将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。

• 优点：线程管理是在用户空间进行的，因而效率比较高。
• 缺点：==当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞==；==多个线程不能并行地运行在多处理机上。==

One-to-One

将每个用户级线程映射到一个内核级线程。

• 优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。
• 缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样**==创建线程的开销比较大==**，会影响到应用程序的性能。

Many-to-Many

将n个用户级线程映射到m个内核级线程上，要求m<=n。

特点：在多对一模型和一对一模型中取了个折中，克服了多对一模型的并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。

进程同步

并发是OS的设计基础，也是所有同步互斥问题产生的原因。

进程的三个特征：

• 间断性：并发：体现在进程的执行是间断性的；进程的相对执行速度是不可测的。
• 非封闭性：共享：体现在进程/线程之间的制约性（如共享打印机）。
• 不可再现性：不确定性：进程执行的结果与其执行的相对速度有关，是不确定的。

同步与互斥

并发执行，不可避免地产生了多个进程对同一个共享资源访问，造成了资源的争夺。

• 竞争：两个或多个进程对同一共享数据同时进行访问，而最后的结果是不可预测的，它取决于各个进程对共享数据访问的相对次序。这种情形叫做竞争。
• 竞争条件：多个进程并发访问和操作同一数据且执行结果与访问的特定顺序有关。
• ==临界资源：我们将一次仅允许一个进程访问的资源称为临界资源==。
• 临界区：每个进程中访问临界资源的那段代码称为临界区。

基本概念

进程互斥：某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。互斥无法限制访问者对资源的访问顺序，即访问是无序访问。

进程同步：是指在互斥的基础上，通过其它机制实现访问者对资源的有序访问。

在大多数情况下，同步已经实现了互斥，特别是所有对资源的写入的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源，如同时读。

• 进程互斥是进程间发生的一种间接性作用，一般是程序不希望的。
• 进程同步是进程间的一种刻意安排的直接制约关系。即为完成同一个任务的各进程之间，因需要协调它们的工作而相互等待、相互交换信息所产生的制约关系。

机制原则

临界区原则：

1. 没有进程在临界区时，想进入临界区的进程可进入。
2. 任何两个进程都不能同时进入临界区（Mutual Exclusion）；
3. 当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区（Progress）；
4. 任何一个进程进入临界区的要求应该在有限时间内得到满足（Bounded Waiting）。

互斥机制的设计原则：

1. 空闲让进：临界资源处于空闲状态，允许进程进入临界区。
2. 忙则等待：临界区有正在执行的进程，所有其他进程则不可以进入临界区。
3. 有限等待：对要求访问临界区的进程，应在保证在有限时间内进入临界区，避免死等。
4. 让权等待：当进程长时间不能进入临界区时，应立即释放处理机，尽量避免忙等。

互斥方法

**所谓的锁，在计算机里本质上就是一块内存空间。**用一个锁的访问来代表临界区的访问。

世界上本来没有互斥，对于内存的修改是粗暴的，用锁这种方式来由操作系统实现锁、实线进程同步。

基于忙等待的同步方法

• 当一个程序想要进入临界区时，先检查是否允许进入
• 若不允许，则进程将原地等待，知道被允许进入
  • 空转浪费CPU时间

软件方法

如何通过软件完成相应的临界区涉及，达成互斥的效果？

程序可能会同时竞争相应的资源，由于资源的竞争导致可能同时死锁/进入临界区，所以要设置相应的方法。

Dekker算法：使用turn进行让权，保证只有一个能进入临界区

P:
pturn = true;
while (qturn) {
    // 让权等待
    if (turn == 1) {
        pturn = false;
        while (turn == 1);
        pturn = true;
    }
}
// 临界区
// 谦让给对方
turn = 1;
pturn = false;

Q:
qturn = true;
while (pturn) {
    // 让权等待
    if (turn == 0) {
        qturn = false;
        while (turn == 0);
        qturn = true;
    }
}
// 临界区
turn = 0;
qturn = false;

Peterson算法：

#define N 2
// 轮到谁
int turn;
// 初始值均为false
int interested[N];

// process = 0, 1
void enter_region(int process) {
    // 另一个进程的进程号
    int other = 1 - process;
    // 本进程感兴趣
    interested[process] = true;
    // 设置标志位
    turn = process;
	// 使用turn进行谦让，不用turn则可能会同时访问
    // 轮到我了并且你不敢兴趣：如果没到我（被抢占）或对方还没退出临界区
    while (turn == process && interested[other] == true);
}

void leave_region(int process) {
    // 进程离开临界区
    interested[process] = false;
}

enter_region(i);
// 临界区
leave_region(i);

硬件方法

• 中断屏蔽

  • 执行关中断指令，程序进入临界区进行操作
  • 退出临界区之前，执行开中断指令
  • 在多CPU情景下会带来很大的性能损失，单处理器情况下很多日常任务（如时钟中断）是靠中断机制实现的

• test-and-set方法实现的自旋锁

  • 使用硬件提供的test_and_set硬件原语提供互斥支持，是一种不可中断的基本原语。

    在多进程可以同时存取内存的情况下，如果一个进程正在执行检查并设置，在执行完成前，其他进程不可以执行检查并设置

  • 具体的硬件实现是通过对总线的锁定来实现对某个内存位置的原子读和更新

  • acquire(lock) {
        while(test_and_set(lock) == 1);
    }
    // 临界区
    release(lock) {
        lock = 0;
    }
    - swap指令
    
      - 也是不会被中断的原子指令，功能是交换两个字的内容
    
    ### 基于信号量的同步方法
    
    同步中，进程经常需要等待某个条件的发生，如果使用忙等待的解决方案，势必浪费大量CPU时间。
    
    - 忙等待：浪费CPU时间
    - ==优先级反转：低优先级的进程先进入临界区，高优先级的进程一直忙等==
    
    解决方法：增加进程间的通信手段，**将忙等变为阻塞**，使用了进程间的通信原语：`sleep`和`wakeup`。`wakeup`原语的调用需要一个参数**被唤醒的进程ID**。
    
    引入了信号量，是一类特殊的变量，**程序对其的访问都是原子操作**。信号量的**对象是资源**：记录了当前想要使用资源的进程数量和资源数量之间的关系。
    
    #### 信号量的数据结构
    
    信号量的具体数据结构为：一个确定的二元组`(s,q)`
    
    - s是一个具有非负初值的整形变量。
      - s的值是对应资源的数量，即当前可使用该资源的进程的数量
      - 若s大于等于0，则代表可使用的资源的数量
      - 若s小于0，则没有资源可供进程使用，则需要相关的阻塞，此时**`|s|`为被阻塞的进程的数量**
    - q是一个初始状态为空的队列
      - q中存储了被阻塞的进程的信息，记录了被阻塞的信息。
      - 强信号量：进程从q中释放时采用FIFO
      - 弱信号量：没有规定进程从阻塞队列中移除顺序
    
    信号量只有**增加V操作和减少P操作**两种。PV操作属于进程的**低级通信**。
    
    - 在进入临界区时，必须先进P操作，获得资源并减小信号量，阻塞其他想要竞争的资源。
      - P操作分配资源（给线程），信号量\-\-
    - 在出临界区时释放资源，进行V操作。
      - V操作（由线程）释放资源，信号量++
    
    ```c
    struct semaphore {
        int vount;
        queueType queue;
    }
    
    // 进程获取资源：P操作
    void semWait (semaphore s) {
        s.count--;
        if(s.count<0) {
            // 进行阻塞
            // |s.count|表示当前等待的进程个数
        }
    }
    
    // 进程释放资源：V操作
    void semSignal (semaphore s) {
        s.count++;
        if(s.count<=0) {
            // 释放了一个资源，则一个被阻塞的进程可接触阻塞
        }
    }
    
    

信号量的使用

• 互斥

  • 可以用==初始值为1==的二元信号量来实现进程间的互斥
  • 一个进程在进入临界区之前执行semWait操作
  • 退出临界区后再执行一个semSignal操作

• 有限并发

  • 是指有n个进程并发的执行一个函数或者一个资源。
  • 一个==初始值为c==的信号量可以实现这种并发。

• 进程同步

  • 是指当一个进程$P_i$想要执行一个$a_i$操作时，它只在进程$P_j$执行完$a_j$后，才会执行$a_i$操作。
  • 可以用信号量如下实现：将信号量初始为0，$P_i$执行$a_i$操作前执行一个semWait操作；而$P_j$执行$a_j$​​​操作后，执行一个semSignal操作。
  • 这是一种先将自己置于阻塞低位，等待被唤醒的操作

• 进程汇合

  • 任务$a_1,b_1$均完成后，对应的任务$a_2,b_2$才能发生

  • 同名的操作天然满足发生的约束，不同命的操作利用信号量实现

  • 将相应的信号量aArrive,bArrive初始化为0

  • // aStatemant
    {
        a1;
        aArrive.signal();
        bArrive.wait();
        a2;
    }
    // bStatement
    {
        b1;
        bArrive.signal();
        aArrive.wait();
        b2;
    }
    // 要理解本质的s.count
    - 同步原语Barriers
    
      - 对汇合进行泛化，相当于多个进程组的同步
    
      - 使用两个信号量标记一起进入和一起离开
    
      - ```c
        // 记录进程是否达到barrier
        turnstile = Semaphore(0);
        // 记录进程是否离开barrier
        turnstile2 = Semaphore(1);
        // 对同步计数量的写锁
        mutex = Semaphore(1);
        
        mutex.wait();
        	// 到达barrier的进程数量++
            count += 1;
        	if(count == n) {
                // 离开barrier的信号量
                t2.wait();
                t.signal();
            }
        mutex.signal();
        
        // 等待被唤醒
        // 如果count不达到n，不会有任何唤醒
        t.wait();
        // 负责唤醒下一个
        t.signal();
        
        mutex.wait();
        	count -= 1;
        	// 已经全部离开了barrier
        	if(count == 0) {
                t.wait();
                t2.signal();
            }
        mutex.signal();
        
        t2.wait();
        t2.signal();
        // 全部离开了
    
    
    

信号量集机制

同时需要多个资源的信号量操作

AND型信号量集机制

基本思想：将进程需要的所有共享资源一次全部分配给它；待该进程使用完后再一起释放。

SP(S1, S2, … ,Sn) {
    if(s1 >= 1 && s2 >=1 && ... && sn >= 1) {
        for i in (1,n+1) {
            P(si);
        }
    } 
    else {
        // 等待被阻塞进程
    }
}
// 等待所有临界资源都得到后，在开始进程的行为
SV(S1, S2, … ,Sn) {
    for i in range(1,n+1) {
        V(si);
        // 唤醒阻塞进程
    }
}

一般“信号量集”机制 SP(S,T,D)

SP(S,T,D)基本思想：在AND型信号量集的基础上进行扩充：

• 测试值为$t_i$：用于信号量分配的阈值，即$S_i<t_i$，表示资源数量低于$t_i$时，便不予分配

• 占用值为di：依次分配$d_i$个临界资源，即$S_i = S_i - d_i$和$S_i = S_i +d_i$​

• SP(s1, t1, d1, ..., sn, tn, dn) {
      if(s1 >= t1 && s2 >= t2 && ... && sn >= tn) {
          for i in (1,n+1) {
              si = si - di;
          }
      } 
      else {
          // 等待被阻塞进程
      }
  }
  // 等待所有临界资源都得到后，在开始进程的行为
  SV(s1, t1, d1, ..., sn, tn, dn) {
      for i in range(1,n+1) {
          si = si + di;
          // 唤醒阻塞进程
      }
  }
  - $SP(S, d, d)$：表示每次申请d个资源，当资源数量少于d个时，便不予分配
  
  - $SP(S, 1, 1)$：表示互斥信号量
  
  - $SP(S, 1, 0)$：可作为一个可控开关
  
    当$S>=1$时，允许多个进程进入临界区；当$S=0$时禁止任何进程进入临界区
  
  ### 管程
  
  > 可以联想Java中的signal和wait操作，基本上是等价的
  
  信号量这种机制具有一些缺点，如用信号量及PV操作解决问题时，程序编写需要很高的技巧。如果没有合理地安排PV操作的位置，就会导致一些出错的结果，如出现死锁等问题。
  
  管程是在程序设计语言当中引入的一个成分，是一种**高级同步机制**。管程就是指管理共享变量以及对共享变量的操作过程，让它们支持并发。
  
  - 管程**是一种语言机制，定义了一种程序结构**，结构内的多个子程序（对象或模块）形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件设备或一群变量。
    - 管程的名称
    - 局部于管程内部的**共享数据结构（变量）说明**
    - 对该数据结构进行操作的一组**互斥执行的过程**
    - 对局部于管程内部的共享数据**设置初始值的语句**
  - 管程实现了在一个时间点，**最多只有一个线程在执行管程的某个子程序**。这种封装好的操作实现简化了程序设计。
  - 管程提供了一种机制，线程可以临时放弃互斥访问，等待某些条件得到满足后，重新获得执行权恢复它的互斥访问。
  
  ==**管程和信号量是等价的，所谓等价指的是用管程能够实现信号量，也能用信号量实现管程。**==
  
  #### 管程的实现
  
  管程的实现具有**面向对象的思想**，定义了一个共享变量的数据结构和能对数据结构进行的操作（需要保证互斥）。在管程模型里，共享变量和对共享变量的操作是被封装起来的。
  
  1. 管程的名称；
  2. 局部于管程内部的共享数据结构（变量）说明；
  3. 对该数据结构进行操作的**一组互斥执行的过程**；
  4. 对局部于管程内部的共享数据**设置初始值**的语句。
  
  管程作为一种同步机制，需要解决三个问题
  
  1. 互斥：只能有一个进程可对其内部数据结构进行相应的操作，即==**管程进入是互斥的**，**由编译器来保证**（**管程是一个语言机制**）==。
  
  2. 同步：通过设置条件变量（CV）以及在条件变量上实施的`wait`和`signal`操作，它可以使一个进程或线程，当条件不满足/满足的时候在条件变量上等待/唤醒。
  
  3. 条件变量：为了**区别等待的不同原因，管程引入了条件变量**。
  
     不同的条件变量，对应**不同原因的进程阻塞等待队列**，初始时为空。
  
     条件变量上能作`wait`和`signal`原语操作，若条件变量名为X，则调用同步原语的形式为`wait(X)`和`signal(X)`
  
  #### 管程和信号量的区别
  
  - **条件变量的值不可增减**，P-V操作的信号量值可增减
    - wait操作一定会阻塞当前进程；但P操作只有当信号量的值小于0时才会阻塞。
    - **如果没有等待的进程，signal将丢失**；而V操作增加了信号量的值，不会丢失。
  - 访问条件变量必须拥有管程的锁
  
  #### 管程模型
  
  管程只是==保证了同一时刻只有一个进程在管程内活动==，即管程内定义的操作在同一时刻只被一个进程调用（由编译器实现)。
  
  但是这样并不能保证进程以设计的顺序执行，因此需要设置条件变量，让进入管程而无法继续执行的进程阻塞自己。
  
  Hasen模型、Hoare模型和MESA模型等解决的问题就是：==当后续的进程P唤醒被阻塞的进程Q时，哪一个应该先执行==：
  
  - Hoare模型：Q执行完成后P执行
  - MESA模型：P执行完成后Q执行（java的方式）
  - Hansen管程：规定唤醒操作时管程中**最后一个**可执行的操作
  
  ##### Hoare模型
  
  ###### 数据结构
  
  入口等待队列(entry queue)：因为管程是**互斥进入的**，所以当一个进程试图进入一个已被占用的管程时它应当**在管程的入口处等待**，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列。
  
  紧急等待队列：管程内部由于相互唤醒造成的等待队列。
  
  如果进程Ｐ唤醒进程Ｑ，则Ｐ等待Ｑ继续，如果进程Ｑ在执行又唤醒进程Ｒ，则Ｑ等待Ｒ继续。
  
  如此，在管程内部，**由于执行唤醒操作，可能会出现多个等待进程**：已被唤醒，但由于管程的互斥进入而等待。因而还需要有一个进程等待队列，这个等待队列被称为**紧急等待队列**。它的优先级应当高于入口等待队列的优先级。
  
  <img src="https://pigkiller-011955-1319328397.cos.ap-beijing.myqcloud.com/img/202404170014411.png" alt="image-20240417001445265" style="zoom: 67%;" />
  
  ==每个条件变量表示一种等待原因，每个原因对应一个队列。==
  
  ###### 操作原语
  
  同步操作原语wait和signal：针对条件变量x，`x.wait()`将自己阻塞在x队列中，`x.signal()`将x队列中的一个进程唤醒。
  
  - `x.wait()`：
    - 如果紧急等待队列非空，则唤醒第一个等待者：释放了一个资源
    - 否则释放管程的互斥权，执行此操作的进程排入x队列尾部
    - 紧急等待队列与x队列的关系：紧急等待队列是由于管程的互斥进入而等待的队列，而x队列是**因资源被占用而等待**的队列
  
  - `x.signal()`：
    - 如果x队列为空，则相当于空操作，执行此操作的进程继续
    - 否则唤醒第一个等待者，执行`x.signal()`操作的进程排入紧急等待队列的尾部。
  
  
  ###### 信号量
  
  1. 用于互斥的信号量`mutex`：保证管程本身只有一个进程进入
     1. 进程==**调用管程中的任何过程时**==，应执行P(mutex)（\-\-）；进程退出管程时应执行V(mutex)（++）开放管程，以便让其他调用者进入。
     2. 为了使进程在等待资源期间，其他进程能进入管程，故==在**wait操作中也必须执行V(mutex)**==，否则会妨碍其他进程进入管程，导致无法释放资源。
  2. 对于每个管程发出signal后挂起自身的信号量`next`
     1. 凡发出signal操作的进程应该用P(next)**挂起自己**（Hoare管程为发出signal的进程等待执行），直到被释放进程退出管程或产生其他等待条件。
     2. 进程在退出管程的过程前，须检查是否有别的进程在信号量next上等待，若有，则用V(next)唤醒它。`next-count`（初值为0），用来记录在next上等待的进程个数。
  3. 申请资源未被满足的信号量`x-sem`
     1. 申请资源得不到满足时，执行P(x-sem)挂起。由于释放资源时，需要知道是否有别的进程在等待资源，用计数器`x-count`（初值为0）**记录等待资源的进程数**。
     2. 执行signal操作时，应让等待资源的诸进程中的某个进程立即恢复运行，而不让其他进程抢先进入管程，这可以用V(x-sem)来实现
  
  ```c
  // 编译器对管程外部调用的出入口设置
  // 管程入口
  P(mutex);
  	// 管程的调用
  	// 如果有进程在等待队列等待
  	if(next_count > 0)
          V(next);
  	else
          // 退出管程
          V(mutex);
  // 管程出口
  
  // X.wait
  x_count++;
  if(next_count > 0)
      V(next);
  else
      V(mutex);
  P(x_sem);
  x_count--;
  
  // X.signal
  if(X_count > 0) {
      next_count++;
      V(x_sem);
      P(next);
      next_count--;
  }
  
  

进程通信的方法

低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。

缺点：

• 传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。
• 编程复杂：用户直接实现通信的细节，编程复杂，容易出错。

高级通信：适用于分布式系统，基于共享内存的多处理机系统，单处理机系统，能够传送任意数量的数据，可以解决进程的同步问题和通信问题，主要包括三类：管道、共享内存、消息系统。

• 管道（Pipe）及命名管道（Named pipe或FIFO）
• 消息队列（Message）
• 共享内存（Shared memory）
• 信号量（Semaphore）
• 套接字（Socket）
• 信号（Signal）

管道

分为有名管道和无名管道。其实质是内核中的一片缓存

无名管道

无名管道，或者就叫管道，由于无名，故不存储相应的路径，==只能用于具有亲缘关系的进程（父子进程或兄弟进程）之间的通信==。

==数据只能向一个方向流动；需要双方通信时，需要建立起两个管道。==

单独构成一种独立的文件系统：==管道对于管道两端的进程而言，就是一个文件==，但它不是普通的文件，它不属于某种文件系统，而是自立门户，单独构成一种文件系统，并且只存在在内存中。

数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

有名管道

也叫FIFO，带有先进先出的意思。

提供一个路径名与之关联，==以FIFO的文件形式存在于文件系统中==。这样，即使与FIFO的创建进程不存在亲缘关系的进程，==只要可以访问该路径，就能够彼此通过FIFO相互通信==：能够访问该路径的进程以及FIFO的创建进程之间。

FIFO严格遵循先进先出，对管道及FIFO的读总是从开始处返回数据，对它们的写则把数据添加到末尾。

消息队列

send(destination,&message)和receive(source,&message)是两个通信原语，由OS进行调用。

消息队列是内核中的一个链表，一个消息就是链表的一个节点。

用户进程将数据传输到内核后，内核另外添加一些包括用户 ID、组 ID、进程 ID、优先级在内的信息后，打成的一个数据包称为消息。

允许一个或多个进程往消息队列中写入或读取消息，但是一个消息只能被一个进程读取，读取完毕后自动删除。

消息队列具有一定 FIFO 特性，也可以按照一些特定的方式读取。

消息队列的实现包括打开与创建、发送消息、读取消息、控制消息队列（获取或修改属性、销毁）。

数据结构为：

struct msqid_ds {
    struct ipc_perm msg_perm;
    msgqnum_t msg_qnum;        // the number of messages on queue
    msglen_t  msg_qbytes;      // the max number of bytes on queue
    pid_t     msg_lspid;       // the pid of the last msgsnd()
    pid_t     msg_lrpid;       // the pid of the last msgrcv() 
    time_t    msg_stime;       // the last msgsnd() time
    time_t    msg_ctime;       // last change time
    // ...
}

共享内存

共享内存是==最有用的进程间通信方式==，通信效率高，其避免了其它形式的IPC必须执行的开销巨大的缓冲复制。

两个不同进程A、B共享内存的意义是，==同一块物理内存被映射到进程A、B各自的进程地址空间==。

当多个进程共享同一块内存区域，由于共享内存可以同时读但不能同时写，则==需要同步机制约束==。

进程之间在共享内存时，保持共享区域直到通信完毕。

经典的进程同步和互斥问题

• 生产者－消费者问题
• 读者－写者问题
• 哲学家进餐问题

生产者消费者模型

本质是若干进程通过有限的共享缓冲区交换数据。

其中，“生产者”进程不断写入，而“消费者”进程不断读出；共享缓冲区共有N个；

==任何时刻只能有一个进程可对共享缓冲区进行操作。==

Semaphore full = 0;		// 产品数量
Semaphore empty = n;	// 空闲原料数量
Semaphore mutex = 1;	// 互斥锁
ItemType buffer[0..n-1];
int in = 0, out =0;

producer() {
    while(true){
        // 生产产品nextp;
        P(empty);
            P(mutex);
                buffer[in] = nextp;
                in = (in + 1) MOD n;
            V(mutex);
        V(full);
    }
}

consumer() {
    while(true){
        P(full);
            P(mutex);
                nextc = buffer[out];
                out = (out + 1) MOD n;
            V(mutex);
        V(empty);
        // 消费nextc中的产品
    }
}

读者-写者问题

对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个。

读写、写写互斥，允许读读

读进程的行为：

• 系统中会有多个读进程同时访问共享数据。
• 可分为三类：第一个进入的读进程（占有资源），最后一个离开的读进程(释放资源)和其他读进程。
• 需要设置一个计数器readcount来记录读进程的数目。

写进程的行为：排他性的使用资源。

int readcount=0; //“正在读”的进程数，初值是0。
semaphore rmutex=1; //信号量，用于readcount的互斥。
semaphore fmutex=1; //信号量，用于Data访问的互斥。

// Reader
P(rmutex);
    if(readcount == 0) {
        P(fmutex);
    }
    
	readcount = readcount + 1;
    V(rmutex);
    	// read
    P(rmutex)
    readcount = readcount - 1;
    
	if(readcount == 0) {
        V(fmutex);
    }
V(rmutex)
    
// Writer
P(fmutex);
	write
V(fmutex);

对读者有利，在高负载情况下，写者可能根本没机会写！需要设计一个均衡了读写的方法。

利用queue实现了写者优先算法：

semaphore fmutex = 1;		// fmutex --> access to file;
semaphore rdcntmutex = 1;	// rdcntmutex --> access to readcount
semaphore wtcntmutex = 1;	// wtcntmutex --> access to writecount
semaphore queue = 1;

int readcount = 0, writecount = 0;

void reader() {
    while(1) {
        // 设计queue实现写者优先
        P(queue);
            P(rdcntmutex);
                if(readcount == 0)
                    P(fmutex);
                readcount = readcount + 1;
            V(rdcntmutex);
        V(queue);
        
        //Do read operation ...
        P(rdcntmutex);
            readcount = readcount - 1;
            if(readcount == 0)
            	V(fmutex);
        V(rdcntmutex);
    }
}

void writer() {
    while(1) {
        P(wtcntmutex);
            if(writecount == 0)
                P(queue);
            writecount = writecount + 1;
        V(wtcntmutex);
        
        P(fmutex);
        //Do write operation ...
        V(fmutex);
        
        P(wtcntmutex); 
            writecount = writecount - 1;
            if( writecount == 0)
                V(queue);
        V(wtcntmutex); 
    }
}

给定读写序列：r1,w1,w2,r2,r3,w3…

• 读者优先：r1,r2,r3,w1,w2,w3…
• 写者优先：r1,w1,w2,w3,r2,r3…
• 读写公平：r1,w1,w2,r2,r3,w3…

哲学家进餐问题

同时获取两个锁的死锁问题：设置获取锁的相应的顺序。

需要破除资源互斥、循环等待、保持等待。

调度

CPU调度：控制、协调多个进程对CPU的竞争。N个进程，M个CPU，OS如何进行合适的调度。

基本概念

调度必然伴随着进程的切换：

• 用户调用：来自程序的显式请求(如：打开文件)，该进程多半会被阻塞
• 陷阱：最末一条指令导致出错，会引起进程移至退出状态
• 中断：外部因素影响当前指令的执行，控制被转移至中断处理程序

进程切换的流程：

• 保存处理器的上下文，包括程序计数器和其它寄存器；
• 用新状态和其它相关信息更新正在运行进程的PCB；
• 把进程移至合适的队列-就绪、阻塞；
• 选择另一个要执行的进程；
• 更新被选中进程的PCB；
• 从被选中进程中重装入CPU 上下文。

调度类型

高级调度/宏观调度/作业调度：从用户工作流程的角度，一次提交的若干个作业，对每个作业进行调度。时间上通常是分钟、小时或天。

中级调度/内外存交换：从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。

低级调度/微观调度/进程或线程调度：从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。

• 抢占式
• 非抢占式
  • 时间片原则
  • 优先权原则
  • 短作业优先

性能评价标准

• ==周转时间：作业**从提交到完成（得到结果）**所经历的时间。==

• 周转时间=完成时刻-提交时刻

  • 包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待

  • 外存等待时间、就绪等待时间、CPU执行时间、IO操作时间

• ==带权周转时间：周转时间/服务时间==

  • 权是服务时间的倒数，服务时间越短反而权重越大，更关注同等服务时间下谁的周转时间长
  • 服务时间就是执行时间

• ==平均周转时间：作业周转时间之和/作业数==

• ==平均带权周转时间：作业带权周转时间之和/作业数==

• 响应时间：用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间

• 截止时间：开始截止时间和完成截止时间

• 优先级：可以使关键任务达到更好的指标。

• 公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。

• 吞吐量：单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系

  • 吞吐量=作业数/总执行时间
  • 批处理系统
  • 平均周转时间不是吞吐量的倒数，因为并发执行的作业在时间上可以重叠。

基本调度

进程优先级

优先级表现了进程的重要性和紧迫性

优先数是一个数值，反映了某个优先级

• 静态优先级：进程创建时指定，运行过程中不再改变

• 动态优先级：进程创建时指定了一个优先级，运行过程中可以动态变化。

  如：等待时间较长的进程可提升其优先级。

进程就绪队列

当由多个就绪进程等待调度时，如何组织合适的队列，让进程能够以一定顺序被合理调度

按优先级排队方式

创建多个进程后按照不同的优先级进行排列，CPU调度优先级较高的进程进行执行。

动态优先级队列

这个名字是自己起的

所有进程创建之后都进入到第一级就绪队列，随着进程的运行，可能会降低某些进程的优先级。

如某些进程的时间片用完了，那么就会将其降级。

占用CPU的方式

不可抢占式方式：一旦处理器分配给一个进程，它就一直占用处理器，直到该进程自己因调用原语操作或等待IO等原因而进入阻塞状态，或时间片用完时才让出处理器，重新进行

抢占式方式：就绪队列中==一旦有优先级高于当前运行进程优先级的进程存在时==，便立即进行进程调度，把处理器转给优先级高的进程

进程的分类方式

一种方式

• IO密集型：频繁地进行IO操作，通常会发挥很多时间等待IO操作完成
• CPU密集型：计算量大，需要大量的CPU时间

另一种方式：

批处理进程（Batch Process)

• 无需与用户交互，通常在后台运行
• 不需很快的响应
• 典型的批处理程序：编译器、科学计算

交互式进程（Interactive Process)

• 与用户交互频繁，因此要花很多时间等待用户输入
• 响应时间要快，平均延迟要低于50~150ms
• 典型的交互式进程：Word、触控型GUI

实时进程（Real-time Process)

• 有实时要求，不能被低优先级进程阻塞
• 响应时间要短且要稳定
• 典型的实时进程：视频/音频、控制类

批处理系统的常用调度算法

==批处理系统：无需与用户交互，通常在后台运行，不需要很快的响应速度==

• 先来服务FCFS
• 最短作业优先SJF
• 最短剩余时间优先FRTF
• 最高响应比优先HRRF

先来服务FCFS

按照作业提交或进程变为就绪状态的先后次序，分派CPU。

==不可抢占式==：当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU。在作业或进程唤醒后（如IO完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。

最简单的算法

• 比较有利于长作业，而不利于短作业。
• 有利于CPU繁忙的作业，不利于IO繁忙的作业：会频繁地陷入等待其他进程的等待时间中。

短作业优先SJF

对FCFS算法的改进，其目标是减少平均周转时间。

对预计执行时间短的作业（进程）优先分派处理机。

为==非抢占式==，通常后来的短作业不抢先正在执行的作业。

优点：

• 比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；
• 提高系统的吞吐量；

缺点：

• 对长作业非常不利，可能长时间得不到执行；
• 未能依据作业的紧迫程度来划分执行的优先级；
• 难以准确估计作业（进程）的执行时间，从而影响调度性能。

最短剩余时间优先FRTF

将短作业优先进行改进，改进为==抢占式==：当一个新就绪的进程比当前运行进程具有更短的完成时间，系统抢占当前进程，选择新就绪的进程执行。

缺点：源源不断的短任务到来，可能使长的任务长时间得不到运行，导致产生“饥饿”现象。

最高响应比优先HRRF

是FCFS算法和SJF算法的折中：既考虑作业等待时间，又考虑作业的运行时间，既照顾短作业又不使长作业的等待时间过长，改善了调度性能。

在每次选择作业投入运行时，先计算后备作业队列中每个作业的响应比RP，然后选择其值最大的作业投入运行。

相应比RP定义为：==$\text{RP}=\frac{\text{已等待时间＋要求运行时间}}{\text{要求运行时间}}=1+\frac{已等待时间}{要求运行时间}$==

• 短作业容易得到较高的响应比
• 长作业等待时间足够长后，也将获得足够高的响应比
• 饥饿现象不会发生

每次计算各道作业的响应比会有一定的时间开销，性能比SJF略差。

交互式系统的调度算法

==交互式系统：与用户交互频繁，因此要花很多时间等待用户输入。响应时间要快。==

• 时间片轮转算法RR
• 优先级算法PS
• 多级队列算法MQ
• 多级反馈队列算法MFQ

时间片轮转算法RR

1. 将系统中所有的就绪进程按照先来服务的顺序，排成一个队列。
2. 每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。
3. 在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。
4. ==进程可以未使用完一个时间片，就出让CPU（如阻塞）==。

对于时间片的安排：

• 过长–>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
• 过短–>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。

T（响应时间）=N（进程数目）*q（时间片）

系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间、平均周转时间和平均带权周转时间延长。

优先级算法PS

平衡各进程对相应时间的要求，适用于作业调度和进程调度。

分为抢占式和非抢占式。

• 静态优先级：创建进程时就确定，直到进程终止前都不改变
  • 进程类型：系统进程优先级较高
  • 对资源的需求：对CPU和内存需求较少的进程，优先级较高
  • 用户要求：紧迫程度和付费多少
• 动态优先级：在创建进程时赋予的优先级，在进程运行过程中可以自动改变，以便获得更好的调度性能
  • 在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；
  • 进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让CPU。

多级队列算法MQ

引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标

根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个作业固定归入一个队列

==不同队列可有不同的优先级、时间片长度、调度策略等==。

在运行过程中还可改变进程所在队列。如：系统进程、用户交互进程、批处理进程等

多级反馈队列算法MFQ

设置多个就绪队列，分别赋予不同的优先级。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长（如逐级加倍）。为==抢占式==。

1. 新进程进入内存后，先投入最高优先级队列的末尾，按FCFS算法调度；
2. 若按高优先级队列一个时间片未能执行完，则降低投入到次优先级队列的末尾，同样按FCFS算法调度；
3. 直至降低到最后的队列，按“时间片轮转”算法调度直到完成。

==仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。==

如果进程执行时有新进程进入较高优先级的队列，则==抢先执行新进程==，并把被抢先的进程投入原队列的末尾。

优点：

• 为提高系统吞吐量和缩短平均周转时间而照顾短进程：在高优先级队列中优先被执行
• 为获得较好的IO设备利用率和缩短响应时间而照顾IO型进程
• 不必估计进程的执行时间，动态调节

对于不同类型进程：

• IO型进程：让其进入最高优先级队列，以及时响应IO交互。==通常执行一个小时间片，要求可处理完一次IO请求的数据==，然后转入到阻塞队列。
• 计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
• IO次数不多，而主要是CPU处理的进程：在IO完成后，放回IO请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。
• 为适应一个进程在不同时间段的运行特点，==IO完成时，提高优先级；时间片用完时，降低优先级==；

优先级倒置现象

优先级倒置：高优先级进程/线程被低优先级进程/线程延迟或阻塞

假设存在ABC三个进程，优先级为A>B>C，存在一种临界资源X，由A和C共享：当C访问X时，A被阻塞，而由相应的优先级算法，B也得不到调度，致使延长了被阻塞的时间。

解决优先级倒置现象的方法有：

• 优先级置顶
• 优先级继承

优先级置顶：低优先级变为最高优先级

优先级置顶是解决优先级倒置现象的一种方法。

置顶：访问临界区资源的进程拥有最高的优先级。相应进程进入临界区后，处理机就不允许被抢占。

• 如果系统中的临界区都较短且不多，该方法是可行的。
• 但如果C的临界区非常长，则高优先级进程A仍会等待很长的时间，其效果无法令人满意。

优先级继承：低优先级变为新进入的高优先级

继承：在低优先级进程访问临界区时，继承对应的高优先级进程的优先级，一直保持到退出临界区。

实时系统的调度算法

实时系统是一种时间起着主导作用的系统。要求计算机对外部的输入有较快的反馈，必须在一个确定的时间范围内恰当地做出反应。

实时系统被分为硬实时系统和软实时系统。

• 硬实时要求绝对满足截止时间要求（如：汽车和飞机的控制系统）
• 软实时可以偶尔不满足（如：视频/音频程序）。

实时系统通常将对不同刺激的响应指派给不同的进程（任务），并且每个进程的行为是可提前预测的。

基本概念

相关术语：

• 任务集：$S={t_1,t_2,...,t_n}$
• 任务集中的任务周期分别为：$T_1,T_2,...,T_n$
• 执行时间分别为：$c_1,c_2,...,c_n$
• 截至周期：$D_1,D_2,...,D_n$，通常有$D_i=T_i$
• CPU利用率：$U=\sum_{i=1}^n\frac{c_i}{T_i}$

前提条件：

• 任务集S是已知的；
• 所有任务都是周期性的，周期为T，必须在限定的时限D内完成；
• 任务之间都是独立的，每个任务不依赖于其他任务；
• 每个任务的运行时间c是不变的；
• 调度、任务切换的时间忽略不计。

静态调度算法

通过对所有周期性任务的分析预测（到达时间、运行时间、结束时间、任务间的优先关系），事先确定一个固定的调度方案。

• 无任何计算，按固定方案进行，开销最小；
• 无灵活性，只适用于完全固定的任务场景。

单调速率调度RMS

任务的周期越小，其优先级越高，优先级最高的任务最先被调度。如果两个任务的优先级一样，当调度它们时，RM算法将随机选择一个调度

单调速率（RM）调度算法采用==抢占式的、静态优先级的策略==，调度周期性任务。

其中心思想为：有一被调度任务集S，对于周期T最短的任务，其任务优先级P最高，即优先级与周期成反比。

当较低优先级的进程正在运行且较高优先级的进程可以运行时，较高优先级进程会抢占低优先级。

RM算法有如下的限制：

1. 所有具有硬时限的任务均为周期任务，且周期等于时限。
2. 所有具有硬时限的任务必须在其时限到来前结束。
3. 所有具有硬时限的任务相互独立。
4. 所有具有硬时限的任务均具有恒定的运行时间。
5. 系统中所有非周期任务均为软实时任务，它们的执行超越死限对系统正常运行没有影响

已被证明是单处理器下的最优静态调度算法，具有开销小、灵活性好的特点。

最早截止期调度EDF

任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度。如果两个任务的优先级一样，当调度它们时，EDF算法将随机选择一个调度。

这里的截止时间是，当前运行情况下，进程需要进行强制切换的截止时期，会随着进程的周期性运行周期性变化。

在每个任务的周期处进行调度。

多处理机调度

多处理机的==调度单位广泛采用线程==。注重整体的运行效率，也因而有更多样的调度算法。

非对称多处理系统AMP

多处理器系统中各个处理器的地位不同。采用主-从处理机系统，由主处理机管理一个公共就绪队列，并分派进程给从处理机执行。

各个处理机有固定分工，如执行OS的系统功能，IO处理，应用程序。

非对称式具有有潜在的不可靠性，如主机故障造成系统崩溃。

对称式多处理系统SMP

多处理器系统中，各个处理器的地位相同。

按控制方式，SMP调度算法可分为集中控制和分散控制。

集中控制

• 静态调度
  • 每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。
  • 优点：调度算法开销小。
  • 缺点：容易出现忙闲不均
• 动态调度
  • 各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。可防止系统中多个处理器忙闲不均。

分散控制

• 自调度：各个处理机自行在就绪队列中取任务。

  • 各个CPU采用一个公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。需要对就绪队列的数据结构进行互斥访问控制。

    生产者-消费者模型

  • 是最常用的算法，实现时易于移植，==采用单处理机的调度技术==。

  • 优点：不需要专门的处理机从事任务分派工作。

  • 缺点: 当处理机个数较多时，对就绪队列的访问可能成为系统的瓶颈。

• 成组调度

  • 将一个进程中的一组线程，每次分派时同时到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行。
  • 优点：
    • 通常这样的一组线程在应用逻辑上相互合作，成组调度提高了这些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统吞吐量。
    • 每次调度可以完成多个线程的分派，在系统内线程总数相同时能够减少调度次数，从而减少调度算法的开销。

• 专用处理机调度

  • 为进程中的每个线程都固定分配一个CPU，直到该线程执行完成。
  • 适用于CPU数量众多的高度并行系统，单个CPU利用率已不太重要
  • 缺点：线程阻塞时，造成CPU的闲置。
  • 优点：线程执行时不需切换，相应的开销可以大大减小，推进速度更快。

死锁

定义：由于资源占用的互斥，当某个进程提出资源申请之后，使得一些进程在无外力协助的情况下，永远分配不到必需的资源而无法运行。

• 可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺。如CPU，内存；
• 非可剥夺资源：当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放。如磁带机、打印机；
• 临时性资源：这是指由一个进程产生，被另一个进程使用，短时间后便无用的资源，故也称为消耗性资源。如消息、中断；

死锁的产生

进程推进顺序不当竞争资源不当可能会造成死锁

死锁的四个必要条件：

1. 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源，则请求者只能等待，直至占有资源的进程用毕释放。
2. 请求和保持条件：指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
3. 不剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。
4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合$\{P_0,P_1,P_2,...,P_n\}$中的$P_0$正在等待一个$P_1$占用的资源；$P_1$正在等待$P_2$占用的资源，……，$P_n$正在等待已被$P_0$占用的资源。

处理死锁的基本方法

预防死锁

1. 打破互斥条件：即允许进程同时访问某些资源。

2. 打破占有且申请条件：可以实行资源预先分配策略。

   只有当系统能够满足当前进程的全部资源需求时，才一次性地将所申请的资源全部分配给该进程，否则不分配任何资源。

   由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又申请资源的现象，因此不会发生死锁。

   缺点为：

   • 很多是否进程所需要的资源是不可预测的，无法直到可能用到的全部资源
   • 资源利用率低
   • 降低了进程的并发性

3. 打破不可剥夺条件：即允许进程强行从占有者那里夺取某些资源。

   当一个进程已占有了某些资源，它又申请新的资源，当不能立即被满足时，须释放所占有的全部资源，以后再重新申请。

   它所释放的资源可以分配给其它进程。这就相当于该进程占有的资源被隐蔽地强占了。

   这种预防死锁的方法实现起来困难，会降低系统性能。

4. 打破循环等待条件：实行资源有序分配策略。

   ==把资源事先分类编号，按号有序分配，使进程在申请，占用资源时不会形成环路。==

   所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源，才能申请大号资源，就不会产生环路，从而预防了死锁。

   资源的利用率和系统吞吐量都有很大提高，但存在以下缺点：

   • 限制了进程对资源的请求，同时给系统中所有资源合理编号也是件困难事，并增加了系统开销；
   • 为了遵循按编号申请的次序，暂不使用的资源也需要提前申请，从而增加了进程对资源的占用时间。

避免死锁

死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生。

死锁避免是排除死锁的动态策略，它不限制进程有关资源的申请，而是对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。即分配资源时判断是否会出现死锁，有则加以避免。如不会死锁，则分配资源。

安全序列：若对于每一个进程$P_i$，它需要的附加资源可以被系统中当前可用资源加上所有其他进程$P_j$当前占有资源之和所满足，则$\{P_1，P_2,...,P_n\}$为一个安全序列。

所谓系统是安全的，是指系统中的所有进程能够按照某一种次序分配资源，并且依次地运行完毕，这种进程序列$\{P_1，P_2,...,P_n\}$就是安全序列。如果存在这样一个安全序列，则系统是安全的；如果系统不存在这样一个安全序列，则系统是不安全的。

• 安全状态：系统存在一个进程执行序列$<p_1,p_2,...p_n>$可顺利完成
• 不安全状态：不存在可完成的序列

银行家算法

设n为进程数量，m为资源类型数量：

• 可利用资源向量$Available=()_{m*1}$，$Av[i]=k$表示系统中还有$R_i$类资源k个
• 最大需求矩阵$Max=()_{n * m}$，$M[i][j]=k$表示第i个进程对$R_j$​类资源的最大需求为k
• 分配矩阵$Allocation=()_{n*m}$，$Al[i][j]=k$表示第i个进程已经被分配到$R_j$类资源k个
• 需求矩阵$Need=()_{n*m}$，$N[i][j]=k$表示第i个进程还需要$R_j$​类资源k个
• $Need[i][j]=Max[i][j]-Allocation[i][j]$

判断安全状态的步骤：对于第i个进程

1. 如果$Max[i]<=Need[i]$，则转向步骤2，否则认为出错

2. 如果$Max[i]<=Available[i]$，则转向步骤3，否则认为出错

3. 尝试把资源分配给第i个进程。完成分配后，检查系统是否安全

   安全：之后的所有进程能够顺利结束

进程资源图

用有向图描述系统资源和进程的状态。

定义图$G=(N,E)$​，其中N为点的集合，代表进程和资源，E为边的集合，代表资源的分配和释放。

• $N=P\cup R$，P为进程集合，R为资源集合
• $e=(p_i,r_j)或e=(r_j,p_i)$，分别代表进程请求资源和进程释放资源

资源分配图算法RAG

有向图G的顶点为资源或进程，从资源R到进程P的边表示R已分配给P，从进程P到资源R的边表示P正因请求R而处于等待状态。

• 封锁进程：是指某个进程由于请求了超过了系统中现有的未分配资源数目的资源，而被系统封锁的进程。
• 非封锁进程：即没有被系统封锁的进程

资源分配图的化简方法：假设某个RAG中存在一个进程Pi，此刻Pi是非封锁进程，那么可以进行如下化简：

1. 当Pi有请求边时，首先将其请求边变成分配边（即满足Pi的资源请求）
2. 一旦Pi的所有资源请求都得到满足，Pi就能在有限的时间内运行结束，并释放其所占用的全部资源
3. 此时Pi只有分配边，删去这些分配边（实际上相当于消去了Pi的所有请求边和分配边），使Pi成为孤立结点。
4. 反复进行1-3

系统中某个时刻t为死锁状态的充要条件是t时刻系统的资源分配图是不可完全化简的：

• 在经过一系列的简化后，若能消去图中的所有边，使所有的进程都成为孤立结点，则称该图是可完全化简的；
• 反之的是不可完全化简的。

资源向量(矩阵)算法

每类资源多个的死锁检测

• E：存在资源向量：表示各类资源存在的总量
• A：可用资源向量：表示当前未分配可使用的资源数
• C：当前分配矩阵：第i个行向量对应第i个进程已经分配到的各类资源数量
• R：请求矩阵：第i个行向量表示进程i所需要的资源数量
• $\sum_{i=1}^nC_{ij}+A_{j}=E_j$

检测算法：

1. 寻找进程Pi，其在R矩阵中对应的第i行小于等于A
2. 如果找到，将C矩阵的第i行加入A，释放资源，并标记该进程执行完毕，转到第1步。
3. 如果找不到，结束。
4. 算法结束时，如存在未标记进程，则他们为死锁进程。

死锁恢复

• 资源抢占法

  挂起一些占有资源的进程，剥夺它们的资源以解除死锁，将资源分配给另一个死锁进程使其能够执行完毕，然后再激活被挂起的进程。

• 杀死进程法

  • 杀死一个或者若干进程，释放其资源，直到打破死循。

  • 根据资源占有情况，杀死环内进或者环外进程

  • 杀死重新执行无副作用的进程

• 回滚法

  • 设置检查点，根据死锁时所需要的资源，将一个拥有资源的进程滚回到一个未占用资源的检查点状态，从而使得其他死锁进程能够获得相应的资源。
  • 定期创建检查点
    • 保存存储镜像和资源获取的状态
    • 需要占用存储资源
  • 检测到死锁后
    • 恢复到资源未分配时的检查点
    • 将资源分配给其他进程，继续执行

小结

活锁与饥饿

活锁（livelock）：是指任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。

活锁和死锁的区别在于，处于活锁的实体是在不断的改变状态，即所谓的“活”，而处于死锁的实体表现为等待；活锁有可能自行解开，死锁则不能。避免活锁的简单方法是采用先来先服务的策略。

饥饿（starvation)：某些进程可能由于资源分配策略的不公平导致长时间等待。当等待时间给进程推进和响应带来明显影响时，称发生了进程饥饿，当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死(starve to death)。