进程管理

进程与线程

进程概念的引入

两个基本概念：并发与并行

并发：宏观同时，微观交替

并行：同时

并发性的确定—Bernstein条件

定义：

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

Bernstein条件：

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

立：

• R(S1) ∩ W(S2) = Φ
• W(S1) ∩ R(S2) = Φ
• W(S1) ∩ W(S2) = Φ

Bernstein条件是判断程序并发执行结果是否可再现的充分条件。

进程的定义和特征

• 进程是程序的一次执行；
• 进程是可以和别的计算并发执行的计算；
• 进程可定义为一个数据结构，及能在其上进行操作的一个程序；
• 进程是一个程序及其数据在处理机上顺序执行时所发生的活动；
• 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。

一个进程应该包括：

• 程序的代码
• 程序的数据
• PC中的值
• 一组通用的寄存器的当前值，堆、栈
• 一组系统资源（如打开的文件）

进程与程序的区别

	进程	程序
	动态	静态
	暂时	永久
组成	程序、数据和进程控制块
两者之间的对应关系	通过多次执行，一个程序可以对应多个进程	通过调用关系，一个进程可包括多个程序

进程状态与控制

进程控制

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

原语

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

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

与系统调用的区别：不可中断

创建原语：fork, exec

在fork函数执行完毕后，如果创建新进程成功，则出现两个进程，一个是子进程，一个是父进程。在子进程中，fork函数返回0，在父进程中，fork返回新创建子进程的进程ID。我们可以通过fork返回的值来判断当前进程是子进程还是父进程。如果出现错误，fork返回一个负值。

撤消原语：kill

进程状态

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

执行状态：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。在没有其他进程可以执行时（如所有进程都在阻塞状态），通常会自动执行系统的idle进程（相当于空操作）。

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

graph TB;
	A[执行状态] --> |等待某个事件|B[阻塞状态]
	B --> |事件发生|C[就绪状态]
	A --> |时间片到|C
	C --> |调度|A

进程控制块

系统为每个进程定义了一个数据结构：进程控制块PCB（Process Control Block）。

作用：

• 进程创建、撤消；
• 进程唯一标志；

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

内容：

• 进程标识符：唯一。可以是字符串，也可以是一个数字（Linux系统中是一个整型数）。在进程创建时由系统赋予。
• 程序和数据地址
• 当前状态：为了管理的方便，系统设计时会将相同的状态的进程组成一个队列，如就绪进程队列，等待进程则要根据等待的事件组成多个等待队列，如等待打印机队列、等待磁盘I/O完成队列等等
• 现场保留区
• 互斥和同步机制：用于实现进程间互斥、同步和通信所需的信号量等
• 进程通信机制
• 优先级：反映进程的紧迫程度，通常由用户指定和系统设置。
• 资源清单：列出所拥有的除CPU外的资源记录，如拥有的I/O设备、打开的文件列表等。
• 链接字：根据进程所处的执行状态，进程相应的PCB加入到不同队列中。PCB链接字指出该进程所在队列中下一个进程PCB的首地址。
• 家族关系 …

PCB组织方式

线性表：适用于系统中进程数目不多的情况

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

辨析：进程上下文切换vs陷入内核

	进程上下文切换（Process Context Switch	陷入/退出内核（也称为模态切换，Mode Switch）
	通常由调度器执行，保存进程执行断点，切换内存映射(页表基址，flush TLB)	CPU状态改变，由中断、异常、Trap指令（系统调用）引起，需要保存执行现场（寄存器、堆栈等）
	进程上下文切换过程一定会陷入内核	陷入内核不一定会导致进程切换
		系统调用涉及到进程从用户态到内核态的切换（mode switch），这个时候涉及到的切换主要是寄存器上下文的切换，和通常所说的进程上下文切换不同，mode switch的消耗相对要小得多

线程概念的引入

线程的提出

进程的不足：

• 进程只能在一个时间处理一个任务，不能同时处理多个任务。
• 如果进程在执行时阻塞，整个进程都无法继续执行。

需要一种新的实体，满足：

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

进程与线程

实际上，进程包含了两个概念：资源拥有者和可执行单元。现代操作系统将资源拥有者称为进程，将可执行单元称为线程。线程将资源与计算分离，提高并发效率。

	进程	线程
基本概念	程序的一次执行	进程中的可执行单元，进程中的一个实体，可以与其他同进程的线程共享进程拥有的所有资源，同时也拥有栈、PC等私有资源
资源共享	资源分配的单位，拥有运行程序所需要的全部资源	CPU调度的单位，只拥有必不可少的少量资源
系统开销	创建/撤销/切换/同步进程的开销大	系统开销小
并发程度	低	高

创建一个线程比一个进程快19-100倍。对于存在大量计算和大量I/O处理的应用，大幅度提高性能。在多CPU/多核CPU系统中更有优势。

线程的实现方式

用户级线程

线程在用户空间,通过library模拟的thread,不需要或仅需要极少的kernel支持。上下文切换比较快,因为不用更改page table等,使用起来较为轻便快速。提供操控视窗系统的较好的解决方案

优点：

• 线程切换与内核无关
• 线程的调度由应用决定，容易进行优化。
• 可运行在任何操作系统上，只需要线程库的支持

不足：

• 很多系统调用会引起阻塞，内核会因此而阻塞所有相关的线程。
• 内核只能将处理器分配给进程，即使有多个处理器，也无法实现一个进程中的多个线程的并行执行

内核级线程

内核级线程就是kernel有好几个分身，一个分身可以处理一件事。这用来处理非同步事件很有用，kernel可以对每个非同步事件产生一个分身来处理。支持内核线程的操作系统内核称作多线程内核。

优点：

• 内核可以在多个处理器上调度一个进程的多个线程实现同步并行执行
• 阻塞发生在线程级别
• 内核中的一些处理可以通过多线程实现

缺点：

• 一个进程中的线程切换需要内核参与，线程的切换涉及到两个模式的切换（进程-进程、线程-线程）
• 降低效率

用户级线程和内核级线程的比较

• 用户级线程执行系统调用指令时将导致其所属进程的执行被暂停，而内核级线程执行系统调用指令时，只导致该线程被暂停。
• 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核级线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度
• 用户级线程的程序实体是运行在用户态下的程序，而内核级线程的程序实体则是可以运行在任何状态下的程序

混合实现方式

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

同步与互斥

同步与互斥问题

临界资源：一次仅允许一个进程访问的资源。

临界区：每个进程中访问临界资源的那段代码称为临界区。

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

进程同步：指在互斥的基础上，通过其他机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有对资源的写入的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

临界区管理应满足的条件：

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

基于忙等待的互斥方法

软件方法

Dekker算法

第一个不需要严格轮换的互斥算法。

引入变量turn，以便在竞争时选出进入临界区的进程

pturn/qturn表示“我”想进入临界区，turn表示该哪个进程进入临界区了（轮流进）

P:
......
pturn = true;//I want to enter
while(qturn) {// other wants to enter
	if (turn == 1) {//it's not my turn
		pturn = false;//I (temporarily) don't want to enter
		while(turn == 1); // The other is automatically allowed to enter
		// other don't want to enter
		pturn = true;// I want to enter
	}
}
// other doesn't want to enter
//临界区
turn = 1;// it's the other's turn
pturn = false;// I don't want to enter
......

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

Peterson算法

解决了互斥访问的问题，而且克服了强制轮流法的缺点，可以完全正常地工作。

#define FALSE O
#define TRUE 1
#define N 2 //进程的个数
int turn; //轮到谁?
int interested[N]; //兴趣数组，初始值均为FALSE
void enter_region(int process)//process=0或1
{
	//另外一个进程的进程号
    int other;
    other = 1 - process;
    //表明本进程感兴趣
    interested[process]=TRUE;
    turn = other;//设置标志位
    //other也可以换成process，这其实是两种方式：谦让式vs争夺式
    while(turn == other && interested[other]==TRUE);
}

void leave_region(int process) {
	interested[process] = FALSE;
}

Bakery Algorithm(面包店算法)

• 在进入临界区之前，进程收到一个数字，具有最小数字的进程被允许进入临界区
• 如果进程 Pi 和 Pj 接收到相同数字, if i < j, then Pi 进入临界区；否则，Pj 进入临界区
• 产生的数字总是递增的，例如：1,2,3,3,3,3,4,5…

硬件方法

中断屏蔽方法

使用“开关中断”指令。执行“关中断”指令，进入临界区操作；退出临界区之前，执行“开中断”指令。

优点：简单

缺点：

不适用于多CPU系统

往往会带来很大的性能损失。很多日常任务都是靠中断机制触发的，比如时钟，如果屏蔽中断，会影响时钟和系统效率。

用户进程的使用可能很危险，例如：关中断之后，不再打开中断，会导致整个系统无法继续运行。所以，使用范围一般为内核进程（少量使用）。

使用test and set指令

TS（test-and-set ）是一种不可中断的基本原语（指令）。它会把“1”写到某个内存位置并传回其旧值。在多进程可同时访问内存的情况下，如果一个进程正在执行TS指令，在它执行完成前，其它的进程不可以执行TS指令。

TestAndSet(boolean_ref *lock) { 
    boolean initial = *lock; 
    *lock = true; 
    return initial; 
}

自旋锁Spinlocks

利用test_and_set硬件原语提供互斥支持。通过对总线的锁定实现对某个内存位置的原子读与更新。

acquire(int *lock) {
    while(test_and_set(lock) == 1)
    	/* do nothing */;
}

release(int *lock) {
	*lock = 0;
}

当lock == 0时，线程执行完acquire获得锁，lock被修改为1。其他线程想获得锁时，执行acquire会被卡在while循环里，直到获得线程的锁执行完释放锁。

几个算法的共性问题

无论是软件还是硬件方法，解法都是正确的，但它们都有一个特点：当一个进程想进入临界区时，先检查是否允许进入，若不允许，则该进程将原地等待，直到允许为止。造成：

• 忙等待，浪费CPU时间
• 优先级反转：低优先级进程先进入临界区，高优先级进程一直忙等。如果使用用户级线程，低优先级线程不会被高优先级线程抢占(进入临界区一般需要系统调用，其他线程也同时会被阻塞)，因为抢占发生在进程级别。但是对于内核级线程的实现，这个是可能发生的。

补充：优先级反转

是指一个低优先级的任务持有一个被高优先级任务所需要的共享资源。高优先任务由于因资源缺乏而处于受阻状态，一直等到低优先级任务释放资源为止。而低优先级获得的CPU时间少，如果此时有优先级处于两者之间的任务，并且不需要那个共享资源，则该中优先级的任务反而超过这两个任务而获得CPU时间。如果高优先级等待资源时不是阻塞等待，而是忙循环，则可能永远无法获得资源，因为此时低优先级进程无法与高优先级进程争夺CPU时间，从而无法执行，进而无法释放资源，造成的后果就是高优先级任务无法获得资源而继续推进。

1. 优先级置顶：给临界区一个高优先级，进入临界区的进程都将获得这个高优先级
2. 优先级继承：当一个高优先级进程等待一个低优先级进程持有的资源时，低优先级进程将暂时获得高优先级进程的优先级别，在释放共享资源后，低优先级进程回到原来的优先级别
3. 中断屏蔽：通过禁止中断来保护临界区，采用此种策略的系统只有两种优先级——可抢占优先级和中断禁止优先级。前者为一般进程运行时的优先级，后者为运行于临界区的优先级。

解决方法

将忙等变为阻塞。见下节

基于信号量的同步方法

同步中，进程经常需要等待某个条件的发生，如果使用忙等待的解决方案，势必浪费大量CPU时间。

解决方法：将忙等变为阻塞，可使用两条进程间的通信原语：Sleep和Wakeup。Sleep原语将引起调用进程的阻塞，直到另外一个进程用Wakeup原语将其唤醒。很明显，wakeup原语的调用需要一个参数——被唤醒的进程ID。

信号量

是Dijkstra提出，它使用一个整型变量来累计唤醒次数，供以后使用。在他的建议中引入了一个新的变量类型，称作信号量（semaphore）。建议设立两种操作，P（也叫semWait）、V（也叫semSignal）。PV操作属于进程的低级通信。

信号量是一类特殊的变量，程序对其访问都是原子操作，且只允许对它进行P(信号变量)和V(信号变量)操作。

信号量的定义

一个确定的二元组(s, q)，其中s是一个具有非负初值的整型变量，q是一个初始状态为空的队列. 当发出P操作时：

• s为正，则该值等于可立即执行的进程的数量；s <= 0，那么发出P操作后的进程被阻塞（即发出P操作后s先减一，此时若s<0，则该进程被阻塞），│s │是被阻塞的进程数。
• q是一个初始状态为空的队列，当有进程被阻塞时就会进入此队列。

信号量的分类

二元信号量和一般信号量

• 二元信号量：取值仅为“0”或“1”，主要用作实现互斥；
• 一般信号量：初值为可用物理资源的总数，用于进程间的协作同步问题。

强信号量和弱信号量

• 强信号量：进程从被阻塞队列释放时采取FIFO

  –不会出现“饥饿”（某个进程长时间被阻塞）

• 弱信号量：没有规定进程从阻塞队列中移除顺序

  –可能出现“饥饿“

信号量的操作

• 一个信号量可能被初始化为一个非负整数.
• semWait 操作（P操作）使信号量减1。若值为负，则执行semWait的进程被阻塞。否则进程继续执行。
• semSignal操作（V操作）使信号量加1。若值小于或等于零，则被semWait操作阻塞的进程被解除阻塞。

信号量在并发中的典型应用

互斥：可以用初始值为1的信号量实现。一个进程在进入临界区之前执行P操作，退出临界区后执行V操作。这是实现临界区资源互斥使用的一个二元信号量。

有限并发：可以用初始值为c的信号量实现n（1<=n<=c)个进程的并发执行一个函数或一个资源。

进程同步：指当⼀个进程Pi想要执⾏⼀个ai操作时，它只在进程Pj执⾏完aj后，才会执⾏ai操作。可以⽤信号量如下实现：将信号量初始为0，Pi执⾏ai操作前执⾏⼀个semWait操作；⽽Pj执⾏aj操作后，执⾏⼀个semSignal操作。

屏障Barriers：只有当该线程/进程组中所有线程到达屏障点（可称之为同步点）时，整个程序才得以继续执行。信号量实现如下：n个进程就有n个信号量，屏障进入前对除本进程对应信号量以外的其他进程进行V操作，然后对本进程对应信号量进行P操作。

//两个进程
semaphore s0 = 0
semaphore s1 = 0
P0:
//code before barrier
V(s0)
P(s1)
//code after barrier

P1:
//code before barrier
V(s1)
P(s0)
//code after barrier

//多个进程
n = the number of threads
count = 0//到达汇合点的线程数
semaphore mutex = 1//互斥对count的访问
semaphore barrier = 0 //线程到达之前都是0或者负值，到达后取正值

P:
P(mutex)
count++
if count == n:
	V(barrier) //唤醒一个线程
V(mutex)

P(barrier)
V(barrier)//一旦线程被唤醒，有责任唤醒下一个线程

P(mutex)
count--
if count == 0:
	P(barrier)//“关门”
V(mutex)

P、V操作的优缺点

优点：简单，而且表达能力强（用P、V操作可以解决任何同步、互斥问题）

缺点：不够安全，PV操作使用不当会出现死锁，遇到复杂同步互斥问题时实现复杂。

基于管程的同步与互斥

管程的定义和组成

管程（Monitor）是在程序设计语言当中引入的一种高级同步机制。

一个管程定义了一个数据结构和能（在该数据结构上）被并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。（挺像Java里一个类的组成）

管程由四部分组成：

1. 管程的名称
2. 局部于管程内部的共享数据结构（变量）说明
3. 对该数据结构进行操作的一组互斥执行的过程（可以理解为函数 / Java里被synchronized的方法）
4. 对局部于管程内部的共享数据设置初始值的语句

条件变量与信号量的区别

条件变量	信号量
值不可增减	可增减
wait操作一定会阻塞当前进程	P操作只有当信号量的值小于0时才会阻塞
如果没有等待的进程，signal将会丢失	V操作增加了信号量的值，不会丢失
访问条件变量必须拥有管程的锁

进程通信（Interprocess Communication）的主要方法

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

  缺点：传送信息量小；编程复杂

• 高级通信：适用于分布式系统、基于共享内存的多处理机系统、单处理机系统。

  主要包括三类：管道、共享内存、消息系统

管道

无名管道（Pipe）

• 管道是半双工的，数据只能向一个方向流动；需要双方通信时，需要建立起两个管道；
• 只能用于父子进程或者兄弟进程之间（具有亲缘关系的进程）；
• 单独构成一种独立的文件系统：管道对于管道两端的进程而言，就是一个文件，但它不是普通的文件，它不属于某种文件系统，而是单独构成一种文件系统，并且只存在于内存中。
• 数据的读出和写入：一个进程向管道中写的内容被管道另一端的进程读出。写入的内容每次都添加在管道缓冲区的末尾，并且每次都是从缓冲区的头部读出数据。

有名管道（Named Pipe，又称FIFO）

FIFO不同于无名管道之处在于它提供一个路径名与之关联，以FIFO的文件形式存在于文件系统中。这样，即使与FIFO的创建进程不存在亲缘关系的进程，只要可以访问该路径，就能够彼此通过FIFO相互通信（能够访问该路径的进程以及FIFO的创建进程之间），因此，通过FIFO不相关的进程也能交换数据。

注意：FIFO严格遵循先进先出（first in first out），对管道及FIFO的读总是从开始处返回数据，对它们的写则把数据添加到末尾

消息传递

• 管程：过度依赖编译器；适用于单机环境。
• 消息传递——两个通信原语（OS系统调用）
  • send (destination, &message)
  • receive(source, &message)

调用方式

• 阻塞调用
• 非阻塞调用

主要问题：

• 解决消息丢失、延迟问题（TCP协议）
• 编址问题：mailbox

共享内存

共享内存是最有用的进程间通信方式，也是最快的IPC形式（因为它避免了其它形式的IPC必须执行的开销巨大的缓冲复制）。

两个不同进程A、B共享内存的意义是，同一块物理内存被映射到进程A、B各自的进程地址空间。当多个进程共享同一块内存区域，由于共享内存可以同时读但不能同时写，则需要同步机制约束（互斥锁和信号量都可以）。

共享内存通信的效率高（因为进程可以直接读写内存）。

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

经典同步与互斥问题

生产者-消费者问题

semaphore empty = N//空闲数量
semaphore full = 0//产品数量
semaphore mutex = 1
producer() {
	while(true) {
		P(empty);
		P(mutex);
		...
		V(mutex);
		V(full)
	}
}

consumer() {
	P(full)
	P(mutex)
	...
	V(mutex)
	V(empty)
}

读者-写者

读者优先

int readcount=0;//正在读的进程数
semaphore rmutex=1;//用户readcount的互斥访问
semaphore mutex=1;//用户数据访问的互斥

read() {
	P(rmutex)
	if readcount == 0 then P(mutex)
	readcount++
	V(rmutex)
	...
	P(rmutex)
	readcount--
	if readcount == 0 then V(mutex)
	V(rmutex)
}

write(){
	P(mutex)
	...
	V(mutex)
}

读写公平(先来先服务)

int readcount=0;//正在读的进程数
semaphore rmutex=1;//用户readcount的互斥访问
semaphore mutex=1;//用户数据访问的互斥
semaphore rwmutex = 1;
read() {
	P(rwmutex)
	P(rmutex)
	if readcount == 0 then P(mutex)
	readcount++
	V(rmutex)
	V(rwmutex)
	...
	P(rmutex)
	readcount--
	if readcount == 0 then V(mutex)
	V(rmutex)
}

write(){
	P(rwmutex)
	P(mutex)
    V(rwmutex)
	...
	V(mutex)
}

写者优先(TODO

readSwitch = Lightswitch() 
writeSwitch = Lightswitch() 
noReaders = Semaphore(1) 
noWriters = Semaphore(1)

Reader：
noReaders.wait() 
	readSwitch.lock(noWriters)
noReaders.signal()
	# critical section for readers
readSwitch.unlock(noWriters)

Writer：
writeSwitch.lock(noReaders) 
	noWriters.wait() 
		# critical section for writers 
	noWriters.signal() 
writeSwitch.unlock(noReaders) 

最初信号量都是解锁态。如果reader在临界区，会给noWriter上锁。但是不会给noReader上锁。如果这时候writer到来，会给noReader加锁，会让后续读者排队在noReader。当最后一个读者离开，他会signal noWriter，这时写者可以进入。

当写者进入临界区，他同时拿着noreader和nowriter两个锁。一方面，其他读者和写者不能同时访问临界区。另一方面，writeSwitch 允许其他写者通过，并在noWriter等待。但是读者只能在noReader等待。这样，所有排队的写者能够通过临界区，而不需要signal noreader。当最后一个写者离开，noreader才解锁。写者才能进入。

哲学家就餐

求解思路

1. 至多只允许四个哲学家同时（尝试）进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。设置信号量room=4。（破除资源互斥）
2. 对筷子进行编号，每个哲学家按编号从低到高拿起筷子。或者对哲学家编号，奇数号哲学家先拿左，再拿右；偶数号相反。（破除循环等待）
3. 同时拿起两根筷子，否则不拿起。（破除保持等待）

调度

基本概念

调度的类型

• 高级调度：又称为“宏观调度”、“作业调度”。时间单位通常是分钟、小时、天
• 中级调度：又称为“内外存交换”
• 低级调度：又称为“微观调度”、“进程或线程调度”。时间单位通常是毫秒

面向用户的调度性能准则

• 周转时间（批处理系统）：作业从提交到完成所经历的时间

  带权周转时间 = 周转时间 / 服务时间（即执行时间）

• 响应时间（分时系统）：用户输入一个请求到系统给出首次响应的时间

• 截止时间（实时系统）：开始截止时间和完成截止时间，与周转时间有些相似

• 优先级

• 公平性

面向系统的调度性能准则

• 吞吐量（批处理系统）：单位时间完成的作业数
• 处理机利用率（大中型主机）
• 各种资源的均衡利用（大中型主机）：如CPU繁忙的作业和I/O繁忙的作业搭配

调度算法本身的调度性能准则

• 易于实现
• 执行/开销比小

设计调度算法要考虑的问题

1. 进程优先级（数）

   优先级和优先数是不同的，优先级表现了进程的重要性和紧迫性，优先数实际上是一个数值，反映了某个优先级。

   有静态、动态优先级之分，主要看优先级会不会在运行过程中改变。

2. 进程优先级就绪队列的组织

3. 抢占式调度与非抢占式调度

4. 进程的分类

   1. I/O Bound（密集型）与CPU Bound

   2. 批处理进程、交互式进程、实时进程

5. 时间片

批处理系统的调度算法

先来先服务（FCFS）

特点：有利于长作业，不利于短作业；有利于CPU繁忙的作业，不利于I/O繁忙的作业

最短作业优先（SJF）/短进程优先（SPN）

这是对FCFS算法的改进，其目标是减少平均周转时间。做法是对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢占正在执行的作业。

优点：与FCFS相比改善了平均（&带权）周转时间、作业的等待时间；提高系统的吞吐量。

缺点：长作业可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业的执行时间，从而影响调度性能。

最短剩余时间优先（SRTF）

上面的方法SJF修改条件“通常后来的短作业不抢占正在执行的作业”为抢占式

最高响应比优先（HRRF）

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

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

$$RP = \frac{作业已等待时间 + 作业的服务时间}{作业的服务时间} = 1 + \frac{作业已等待时间}{作业的服务时间}$$

响应比的计算时机：每当调度一个作业运行时，都要计算后备作业队列中每个作业的响应比，选择响应比最高者投入运行。

交互式系统的调度算法

时间片轮转(RR：Round Robin）

多级队列（MQ：Multi-level Queue）

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

不同队列可有不同的优先级、时间片长度、调度策略等；在运行过程中还可改变进程所在队列。如：系统进程、用户交互进程、批处理进程等

多级反馈队列（MFQ： Multi-level Feedback Queue ）

是时间片轮转算法和优先级算法的综合和发展

1. 设置多个就绪队列，分别赋予不同的优先级（如逐级降低），队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长（如逐级加倍）。
2. 新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按“时间片轮转”算法调度直到完成。
3. 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾
4. 如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾

优先级反转问题

实时系统的调度算法

实时系统是一种时间起着主导作用的系统。分为硬实时（绝对满足截止时间要求，如汽车和飞机的控制系统）和软实时（可以偶尔不满足）

实时调度的前提条件

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

算法

• 静态表调度（Static table-driven scheduling）：通过对所有周期性任务的分析预测，事先确定一个固定的调度方案。

• 单调速率调度（RMS：Rate Monotonic Scheduling） 静态最优调度算法：任务的周期越小，其优先级越高，优先级最高的任务最先被调度；如果两个任务的优先级一样，当调度它们时，RM算法将随机选择一个调度。静态、抢先式调度。前提

  $$\sum_{i=1}^n \frac{C_i}{T_i} <= n(\sqrt[n]{2} - 1) \to ln2 \approx 0.69 (n \to \infty)$$

• 最早截止时间优先算法（EDF：Earliest Deadline First）：任务的绝对截止时间越早，其优先级越高，优先级最高的任务最先被调度。如果两个任务的优先级一样，当调度它们时，RM算法将随机选择一个调度。抢占式。任务集可调度的充分必要条件(C是执行时间，T是周期)：

  $$\sum_{i=1}^n \frac{C_i}{T_i} <= 1$$

• 最低松弛度优先算法（LLF：Least Laxity First）：根据任务紧急/松弛程度，来确定任务的优先级，使优先级高的优先执行。

  $$松弛度Laxity = 任务截止时间 - 本身剩余运行时间 - 当前时间$$

  调度时机：有任务执行完时，或有进程Laxity为0时（直接抢占）

多处理机调度

与单处理机调度的区别：

• 注重整体运行效率，而不是个别处理机的利用率
• 更多样的调度算法
• 多处理访问os数据结构时的互斥（对于共享内存的系统）

调度单位广泛采用线程

1. 非对称式多处理系统(AMP：Asymmetric Multi-Processor)：指多处理器系统中各个处理器的地位不同。

   • 主－从处理机系统，由主处理机管理一个公共就绪队列，并分派进程给从处理机执行。

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

   • 有潜在的不可靠性（主机故障造成系统崩溃）。

2. 对称式多处理系统（SMP）

   • 集中控制

     • 静态调度：每个CPU设立一个就绪队列，进程从开始执行到完成，都在同一个CPU上。

       优点：调度算法开销小。

       缺点：容易出现忙闲不均

     • 动态调度：各个CPU采用一个公共就绪队列，队首进程每次分派到当前空闲的CPU上执行。可防止系统中多个处理器忙闲不均。

   • 分散控制

     • 自调度：所有CPU采用一个公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。需要对就绪队列的数据结构进行互斥访问控制。最常用的算法，实现时易于移植，采用单处理机的调度技术

死锁

死锁的概念

死锁发生的四个必要条件

1. 互斥条件：在一段时间内某资源只由一个进程占用
2. 请求和保持条件：进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放
3. 不可剥夺条件：指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放
4. 环路等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，···，Pn}中的P0正在等待一个P1占用的资源；P1正在等待P2占用的资源，……，Pn正在等待已被P0占用的资源

活锁livelock

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

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

饥饿（starvation)：

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

处理死锁的基本方法

• 不允许死锁发生

  预防死锁（静态）：防患于未然，破坏死锁的产生条件

  避免死锁（动态）：在资源分配前进行判断

• 允许死锁发生

  检测与接触死锁

  无所作为：鸵鸟算法

避免死锁

安全序列

安全序列的定义：一个序列{P1，P2，…，Pn}安全的，是指若对于每一个进程Pi，它需要的资源可以被系统中当前可用资源加上所有进程Pj（j < i）当前占有资源之和所满足，则{P1，P2，…，Pn}为一个安全序列。

如果系统不存在这样一个安全序列，则系统是不安全的。

系统进入不安全状态也未必会产生死锁。产生死锁后系统一定处于不安全状态

银行家算法(避免死锁算法)

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

• 可利用资源向量Available：m维向量
• 最大需求矩阵Max：n x m 矩阵
• 分配矩阵Allocation：n x m矩阵
• 需求矩阵Need：n x m矩阵

$$Need(i, j) = Max(i,j) - Allocation(i,j)$$

死锁检测

资源分配图/进程-资源图

用有向图描述系统资源和进程的状态。二元组G=（ N， E），N： 结点的集合，N=P∪R。

P为进程， R为资源，P = {p1, p2, … , pn}，R = {r1, r2, … , rm}，两者为互斥资源。E：有向边的集合，e属于E，e = (pi , rj ) 或e = (rj , pi )。

• e = (pi, rj)是请求边，进程pi请求一个单位的rj资源；
• e = (rj, pi)是分配边，为进程pi分配了一个单位的rj资源

资源分配图(RAG)算法

资源分配图的化简：首先，找到一个非孤立点进程结点且只有分配边，去掉分配边，将其变为孤立结点。接着，将相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边。重复以上步骤，直到所有进程化简完成，即进程与资源间无连线，则系统无死锁

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

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

死锁解除

剥夺资源

撤销进程