OS C++

操作系统（进程管理）

Operating System (process management)

Posted by wykxwyc on March 13, 2019

如何让cpu充分忙碌起来，并且有一定秩序地执行程序？

目录

分别考虑两种情形，一种情形是cpu执行一个数据的累加操作，直接得到结果；另一种情形是cpu从内存中读取某个数据，然后再进行某种累加操作。在两种情况下，虽然只相差了从内存中读数据这一个操作，但最后两者相差的时间却非常大。因此我们需要引入进程的概念，让cpu充分忙碌起来。

进程概念

进程是资源分配的基本单位。 进程包括程序代码段，当前活动（通过程序计数器和处理器的寄存器内容表示），进程堆栈段（临时数据，函数参数，返回地址，局部变量），数据段（全局变量等）。还可能有堆（继承运行期间动态分配的内存）。

通俗来讲，进程是一段可执行程序加上一系列计算机资源。

进程状态

新的：进程正在被创建。
运行：指令正在被执行。
等待：进程等待某个事件的发生。
就绪：进程等待分配处理器。
终止：进程完成执行。

  • 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
  • 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程的状态如下图：

process

进程控制块

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

进程间通信机制(IPC)

IPC(interprocess communication)有两种基本模式：共享内存和消息传递。

两种通信模型图如下：

ipc-model

5种通信方式，参考这里：

管道

管道，通常指无名管道，是 UNIX 系统IPC最古老的形式。
特点：
它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端。
它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）。
它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

FIFO

FIFO，也称为命名管道，它是一种文件类型。
特点：
FIFO可以在无关的进程之间交换数据，与无名管道不同。
FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中。

FIFO可以拓展成客户进程—服务器进程通信的实例。
具体模型如下：

fifo-model

消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标识。
特点：
消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。
消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。
消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

1 #include <sys/msg.h>
2 // 创建或打开消息队列：成功返回队列ID，失败返回-1
3 int msgget(key_t key, int flag);
4 // 添加消息：成功返回0，失败返回-1
5 int msgsnd(int msqid, const void *ptr, size_t size, int flag);
6 // 读取消息：成功返回消息数据的长度，失败返回-1
7 int msgrcv(int msqid, void *ptr, size_t size, long type,int flag);
8 // 控制消息队列：成功返回0，失败返回-1
9 int msgctl(int msqid, int cmd, struct msqid_ds *buf);
信号量

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。
特点
信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。
信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。
每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。
支持信号量组。

共享内存

指两个或多个进程共享一个给定的存储区。
特点
共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。
因为多个进程可以同时操作，所以需要进行同步。
信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。

套接字（socket）

最早出现在UNIX系统中，是UNIX系统主要的信息传递方式。
它包括UDP和TCP通信两种方式。

两个基本概念：客户方和服务方。
当两个应用之间需要采用SOCKET通信时，首先需要在两个应用之间（可能位于同一台机器，也可能位于不同的机器）建立SOCKET连接。

发起呼叫连接请求的一方为客户方
在客户方呼叫连接请求之前，它必须知道服务方在哪里。所以需要知道服务方所在机器的IP地址或机器名称，如果客户方和服务方事前有一个约定就好了，这个约定就是PORT（端口号）。也就是说，客户方可以通过服务方所在机器的IP地址或机器名称和端口号唯一的确定方式来呼叫服务方。

接受呼叫连接请求的一方成为服务方。
在客户方呼叫之前，服务方必须处于侦听状态，侦听是否有客户要求建立连接。一旦接到连接请求，服务方可以根据情况建立或拒绝连接。当客户方的消息到达服务方端口时，会自动触发一个事件（event），服务方只要接管该事件，就可以接受来自客户方的消息了。

线程

单线程与多线程的差别

single-thread-and-muti-thread

用户级线程和内核级线程的关系

用户级线程需要内核级线程的支持，用户级线程和内核级线程有三种对应模式：

  • 多对一模型
    将多个用户级线程对应到一个内核级线程。但这样做时，一个用户级线程阻塞了，那么cpu会认为对应的这个内核级线程阻塞了，转而执行其他内核级线程，从而会导致其他用户级线程不能执行，整个进程阻塞。

  • 一对一模型
    将每个用户线程映射到一个内核线程。
    这种模型比多对一模型的并发性更好，但是每创建一个用户线程就需要一个内核线程，开销大，系统可能无法创建那么多的线程。

  • 多对多模型
    开发人员可穿件任意多的用户线程，当一个线程执行阻塞系统调用时，内核能调度另一个线程来执行。

进程与线程的区别

Ⅰ 拥有资源
进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

Ⅱ 调度
线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

Ⅲ 系统开销
由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

Ⅳ 通信方面
线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

线程池

线程池的思想是在进程开始时创建一定数量的线程，并放到池中以等待工作。当服务器收到请求时，它会唤醒池中的一个线程（如果有可用线程的话），并将要处理的请求传递给它。一旦线程完成了服务，它会返回到池中再等待工作。如果池中没有可用的线程，那么服务器会等待直到有空的线程为止。

线程池的优点：

  • 用现有线程比创建新线程要快。
  • 线程池限制了线程数量，对那些不能支持大量并发的系统很重要。

调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。 参考：CyC2018@github

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

  • 先来先服务 first-come first-serverd（FCFS）
    按照请求的顺序进行调度。
    有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

  • 短作业优先 shortest job first（SJF）
    按估计运行时间最短的顺序进行调度。
    长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

  • 最短剩余时间优先 shortest remaining time next（SRTN）
    按估计剩余时间最短的顺序进行调度。

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

  • 时间片轮转
    将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
    时间片轮转算法的效率和时间片的大小有很大关系：
    因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
    而如果时间片过长，那么实时性就不能得到保证。
    时间片轮转

  • 优先级调度
    为每个进程分配一个优先级，按优先级进行调度。
    为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

  • 多级反馈队列
    一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。

每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

多级反馈队列

实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程同步

PV操作：P相当于wait(),V相当于signal(),wait()和signal()操作必须都要是原子操作。

wait(S){
	while(S<=0); // busy wait
	S--;
}

signal(S){
	S++;
}
临界区

通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

优点：保证在某一时刻只有一个线程能访问数据的简便办法

缺点：虽然临界区同步速度很快，但却只能用来同步本进程内的线程，而不可用来同步多个进程中的线程。

互斥量

互斥量（Mutex）:为协调共同对一个共享资源的单独访问而设计的。

互斥量跟临界区很相似，比临界区复杂，互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。

优点：使用互斥不仅仅能够在同一应用程序不同线程中实现资源的安全共享，而且可以在不同应用程序的线程之间实现对资源的安全共享。

缺点：互斥量是可以命名的，也就是说它可以跨越进程使用，所以创建互斥量需要的资源更多，所以如果只为了在进程内部是用的话使用临界区会带来速度上的优势并能够减少资源占用量。因为互斥量是跨进程的，互斥量一旦被创建，就可以通过名字打开它。

通过互斥量可以指定资源被独占的方式使用，但如果有下面一种情况通过互斥量就无法处理，比如现在一位用户购买了一份三个并发访问许可的数据库系统，可以根据用户购买的访问许可数量来决定有多少个线程/进程能同时进行数据库操作，这时候如果利用互斥量就没有办法完成这个要求，信号量对象可以说是一种资源计数器。

信号量

信号量（Semaphore）:为控制一个具有有限数量用户资源而设计。它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。互斥量是信号量的一种特殊情况，当信号量的最大资源数=1就是互斥量了。

优点：
适用于对Socket（套接字）程序中线程的同步。（例如，网络上的HTTP服务器要对同一时间内访问同一页面的用户数加以限制，只有不大于设定的最大用户数目的线程能够进行访问，而其他的访问企图则被挂起，只有在有用户退出对此页面的访问后才有可能进入。）

缺点：
信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点；

信号量机制功能强大，但使用时对信号量的操作分散， 而且难以控制，读写和维护都很困难，加重了程序员的编码负担；

核心操作P-V分散在各用户程序的代码中，不易控制和管理，一旦错误，后果严重，且不易发现和纠正。

P操作原语与V操作原语：

procedure P(semaphore:s) {
s = s – 1; //信号量减去1
if (s < 0) W(s); //若信号量小于0，则调用进程
被置成等待信号量s的状态
}

procedure V(semaphore:s) {
s := s + 1; //信号量加1
if (s <= 0) R(s); //若信号量小于等于0，则释放
一个等待信号量s的进程
}

PV操作解决机票问题:

Int A[m];
Semaphore s;
s = 1;
cobegin
process Pi {
	int Xi;
	Li:按旅客定票要求找到A[j]；
	P(s)；
	Xi = A[j];
	If (Xi>=1) { Xi=Xi-1; A[j]=Xi; V(s); 输出一张票；
	} else { V(s); 输出票已售完;}
goto Li;
}
coend

两个注意点：
1.P操作与V操作在执行路径上一一匹配
2.只有相同航班的票数才是相关的临界资源，所以用一个信号量处理全部机票会影响进程并发度

改进：

Int A[m];
Semaphore s[m];
For (int j=0;j<m;i++) s[j] = 1;
cobegin
	process Pi {
	int Xi;
	L1:按旅客定票要求找到A[j]；
	P(s[j])；
	Xi = A[j];
	If (Xi>=1) { Xi=Xi-1; A[j]=Xi; V(s[j]); 输出一张票；
	} else { V(s[j]); 输出票已售完； }
	goto L1;
}
coend;
事件

用来通知线程有一些事件已发生，从而启动后继任务的开始。

优点：事件对象通过通知操作的方式来保持线程的同步，并且可以实现不同进程中的线程同步操作。

事件像是条件变量？

临界区不是内核对象，只能用于进程内部的线程同步，是用户方式的同步。
互斥、信号量是内核对象可以用于不同进程之间的线程同步（跨进程同步）。

互斥其实是信号量的一种特殊形式。互斥可以保证在某一时刻只有一个线程可以拥有临界资源。信号量可以保证在某一时刻有指定数目的线程可以拥有临界资源。

管程

为什么需要管程？

虽然信号量机制是一种既方便、又有效的进程同步机制,但每个要访问临界资源的进 程都必须自备同步操作 wait(S)和 signal(S)。这就使大量的同步操作分散在各个进程中。这不仅给系统的管理带来了麻烦,而且还会因同步操作的使用不当而导致系统死锁。这样, 在解决上述问题的过程中,便产生了一种新的进程同步工具——管程(Monitors)。

管程结构确保一次只有一个进程在管程内活动。因此程序员不需要显式地编写同步代码。

需要自己编写同步方案的程序员可以定义一个或多个condition类型的变量。

condition x,y;

操作x.wait()意味着调用操作的进程会挂起，直到另一进程调用x.signal();
(对上面这句话的理解：wait把线程扔到条件x的等待队列里，signal把在等待条件x的一个线程拿出来运行)

管程用到的队列：

semaphore mutex;// 排队进入管程过程的低优先级队列，阻塞在这里
semaphore next; // 释放之后，让释放者挂起的高优先级队列
int next_count; // 在next上等待的进程数

信号量就是一个等待进程队列

互斥调用管程过程的框架：
先在低优先级的过程上排，如果没有人调用管程过程的话，它就可以进去，否则它就得要排。
出来的时候它需要开放管程，开放管程的时候它首先得去释放高优先级的。
高优先级队列没有，再去释放低优先级的队列。

...
wait(mutex);
...
body of F
...
if (next_count > 0)
	signal(next);
else
	signal(mutex);
...

管程wait()和signal()中使用到的全局变量说明：

semaphore mutex;// 排队进入管程过程的低优先级队列，阻塞在这里
semaphore next; // 释放之后，让释放者挂起的高优先级队列
int next_count; // 在next上等待的进程数

condition x;    // 条件变量x
semaphore x_sem;// 信号量x_sem
int x_count;	// 阻塞在x上的进程数

管程的wait()过程：
等待这个条件变量的进程数计数要加上1，然后在挂起自己之前，我们需要开放管程过程。
首先去让高优先级队列当中的进程释放，如果没有高优先级的，再释放低优先级的。
释放了别人之后，立即把自己挂起。
后面这个减数是需要的，因为你计数前面加1了，下次人家执行wait(x_sem)操作(等价于V操作)把你放了，那等待的进程就要减掉一个，所以这个也是很自然的。

void x.wait(){
	x_count++;
	if (next_count > 0) //高优先级队列中有没有进程
		signal(next);   // =V(next),释放高优先级的队列
	else
		signal(mutex);  // =V(mutex),没有高优先级的队列就去释放低优先级的
	wait(x_sem);        // =P(x_sem),把自己挂到条件变量上,和管程过程的wait()操作不一样。
	x_count--;
}

管程的signal()过程：
它去判断有没有等待条件变量的进程，如果没有,signal()操作就是一个空操作，就等于什么都没有执行，如果有，那么它显而易见要把自己挂起来。
（两个进程停留在管程中，得要挂起一个，但是挂谁呢？霍尔方法约定挂自己） 计数加1，然后把别人放了，然后把自己挂起来， 自己挂起来总有一天也会被释放，那么计数就要去减去1。

void x.signal(){
	if (x_count > 0) {
		next_count++; 
		signal(x_sem);// =V(x_sem),把别人放了
		wait(next);   // =P(next),相当于P操作，把自己挂起来，把自己挂到高优先级队列上
		next_count--;
	}
}

哲学家问题

五个哲学家围坐在一个圆桌旁,桌中央有一盘通心面,每人面前有一只空盘子,每两人之间放一把叉子。
每个哲学家思考,饥饿,然后吃通心面,为了吃面哲学家必须获得自己左边和右边的两把叉子。

管程方法解决哲学家问题：
定义5个条件变量，根据盘子，每个哲学家一个盘子，5个条件变量。
1.每个哲学家处于3个状态：思考, 饥饿, 吃。
2.如果他吃不上又饿，那么他就进等待队列。
3.如果他思考和他吃，那么都是很正常的情况。
4.如果我要吃通心粉，那我就调用这个pickup(i)的过程，首先状态变成饿了，然后去测试一下我能不能吃。
5.如果测试同意我吃了，那么我就去吃，如果测试的状态我不能吃，那么我就进等待进程队列。

测试的过程： 测试的过程很简单，就是去看看我左手的在不在吃，我右手的在不在吃，然后我自己是不是饿了。如果这三个条件都满足了，那么我就能吃了。

如果我们通过了拿起叉子的这个测试过程我们就可以吃了，吃完了之后我就得把它放了。也就是说不能永远吃，吃完了之后总要把叉子还掉。
思考完了我们还有两件事要做。要看看左手是不是因为你在等待，再看看右手是不是因为你在等待。
这个时候就回头去看看，如果左手和右手能够变成吃了，我这个signal操作就有意义了。

monitor DiningPhilosophers
{
	enum {THINKING, HUNGRY, EATING} state[5];
	condition self[5];

	void pickup(int i) {
		state[i] = HUNGRY;
		test(i);
		if (state[i] != EATING)
		self[i].wait();
	}
	
	void putdown(int i) {
		state[i] = THINKING;
		test((i + 4) % 5); // i-1等价于i+4
		test((i + 1) % 5); // 检查左右两边是不是因为你在等待。
	}

	void test(int i) {
		if ((state[(i + 4) % 5] != EATING) &&
		(state[i] == HUNGRY) &&
		(state[(i + 1) % 5] != EATING)) {
			state[i] = EATING;

			// 这个signal操作看起来有点多余
			// 这个条件变量量就只有我一个进程在用
			// 既然我还没有吃上，我还没有等，我测试的时候就当它是一个空操作而已
			self[i].signal();  
		}
	}

	initialization_code() {
		for (int i = 0; i < 5; i++)
			state[i] = THINKING;
	}
}

哲学家问题的调用：

semaphore mutex;// 排队进入管程过程的低优先级队列，阻塞在这里
semaphore next; // 释放之后，让释放者挂起的高优先级队列
int next_count; // 在next上等待的进程数

void philosopher(int i){
	thinking();
	wait(mutex);
	DiningPhilosophers.puckup(i)
	if (next_count > 0) signal(next); else  signal(mutex);
	
	eating();
	
	wait(mutex);
	DiningPhilosophers.putdown(i);
	if (next_count > 0) signal(next); else  signal(mutex);
}

哲学家进餐问题的思维精髓是: 考虑能不能一次拿起两只筷子才做决定的话，就会避免死锁问题

读者写者问题（第一类，读者优先）

第二类写者优先参考地址：这里
有两组并发进程：读者与写者，共享一个文件，要求：
1)允许多个读者同时执行读操作
2)不允许多个写者同时操作
3)不允许读者、写者同时操作

考虑的方式

  • 如果读者执行： 无其他读者、写者，该读者可以读
    若已有写者等，但有其他读者正在读， 则该读者也可以读
    若有写者正在写，该读者必须等

  • 如果写者执行： 无其他读者、写者，该写者可以写
    若有读者正在读，该写者等待
    若有其他写者正在写，该写者等待

信号量解决读者写者问题：
读操作和写操作就是一个临界区，但和一般临界区有点不同的是：
1.我们要解决多个读者可以同时读的问题。因此不需要每个读者进入临界区做P(w)和V(w)。
2.第一个读者他到来的时候如果没有其他的读者和写者，那么他就可以去读，他在读之前首先要把临界区保护起来。所以第一个读者要做P(w)。而后续的读者只要前面有读者在读，那么后续来的读者就都可以读。
3.当所有的读者都读完了，那么就会把临界区换回来，那么就是最后一个读者去做V(w)操作。
4.因此就是让第一个读者去做P(w),让最后一个读者去做V(w)。

reader-writer-wrong

rc表示读者的计数。
判断一下他是不是第一个读者，如果是，就让他去做P(w)的工作。
因为每一个读者走的时候rc都要减1，当最后一个读者走的时候，就要去做V(w)的操作。
这时候会引出另一个问题，因为每个读者都会对rc进行操作，那么rc就成为了一个临界区。因此需要针对rc这个临界区，增加一个互斥的信号量。需要对rc进行保护。

reader-writer-right

死锁

参考地址：CyC2018@github

死锁的必要条件
  • 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
  • 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
  • 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
  • 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。
处理方法

主要有以下四种方法：

  • 鸵鸟策略
  • 死锁检测与死锁恢复
  • 死锁预防
  • 死锁避免
鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

死锁检测与死锁恢复

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1.每种类型一个资源的死锁检测
resource-graph

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

2.每种类型多个资源的死锁检测
multi-resource-graph

上图中，有三个进程四个资源，每个数据代表的含义如下：

E 向量：资源总量
A 向量：资源剩余量
C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
R 矩阵：每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1)寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2)如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
3)如果没有这样一个进程，算法终止。

3.死锁恢复

  • 利用抢占恢复
  • 利用回滚恢复
  • 通过杀死进程恢复
死锁预防

在程序运行之前预防发生死锁。

  1. 破坏互斥条件
    例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。

  2. 破坏占有和等待条件
    一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。

  3. 破坏不可抢占条件

  4. 破坏环路等待
    给资源统一编号，进程只能按编号顺序来请求资源。

死锁避免

在程序运行时避免发生死锁。

  • 单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

single-banker

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

  • 多个资源的银行家算法

multi-banker

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：
1)查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
2)假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
3)重复以上两步，直到所有进程都标记为终止，则状态是安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

FEATURED TAGS
SLAM LeGO-LOAM C++ OS Database Redis
FRIENDS