# 进程与线程
# 进程实体
- 进程控制块PCB
- 程序段,用于保存程序的代码(指令序列)
- 数据段,运行过程中产生的各种数据(如程序中定义的变量)
PCB、程序段和数据段构成了进程实体,进程是程序(进程实体)的运行过程,是系统进行资源分配和调度的一个独立单位
# 进程控制块PCB
操作系统需要对各个并发运行的进程进行管理,但凡管理时所需要的信息,都会被放在PCB中。PCB是进程存在的唯一标记,当进程被创建时,操作系统为其创建PCB,当进程结束时,会回收其PCB。
# PCB组成
进程描述信息
- 进程标识符PID
- 用户标识符UID
进程控制和管理信息
- 进程当前运行状态
- 进程优先级
资源分配清单
- 程序段指针
- 数据段指针
- 正在使用的I/O设备
- 页/段表指针、消息队列指针、信号量
处理机相关信息
- 各种寄存器的值(用于实现进程的切换)
# PCB的组织方式
在一个操作系统中,通常有很多PCB,可以采取以下两种方式将它们组织起来
链接方式
即把具有相同状态的进程的PCB链接成一个队列,这样可以形成就绪队列、若干个阻塞队列,对就绪队列而言,往往按进程优先级将PCB从高到低进行排列,将阻塞原因不同排成多个阻塞队列,如等待I/O操作完成的队列和等待分配内存的队列。
索引方式
也是根据进程状态的不同,建立几张索引表,如就绪索引表、阻塞索引表等。
# 线程
# 什么是线程?为什么要引入线程?
进程是程序的一次执行,如果要使用QQ一边视频、文字聊天传送文件,在传统的操作系统下是需要使用不同的几段程序才能实现,并且这几段程序还要并发运行。
传统的操作系统下,这样的情况下需要多进程并发运行,每个进程都需要分配资源,而此时进程的切换需要保存/恢复进程运行环境,还需要切换内存地址空间(更新快表、更新缓存),开销很大,各个进程间不方便进行资源的共享。
引入线程后,进程依然是资源分配的基本单位,但是CPU调度的基本单位变成了线程,这样,同一进程之间的线程切换不会引起进程的切换,线程间的切换开销较小,且线程共享隶属进程的资源,方便资源共享。
引入线程后,进程之间可以并发,进程内的各线程之间也可以并发,进一步提高了系统的并发度。
在操作系统中引入线程,能够减少程序在并发执行时所付出的时空开销,使系统具有更好的并发性。
# 线程进程的区别
- 拥有资源方面:进程是资源分配的基本单位,但是线程不拥有资源,线程可以访问隶属进程的资源。
- 调度方面:线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换,从一个进程中的线程切换到另一个进程中的线程时,会引起进程切换。
- 系统开销方面:由于创建或撤销进程时,系统都要为之分配或回收资源,如PCB、内存空间、I/O 设备等,所付出的开销远大于创建或撤销线程时的开销。类似地,进程切换的代价比线程切换的代价要大得多,进程的切换需要保存/恢复进程运行环境,还需要切换内存地址空间(更新快表、更新缓存),开销很大,各个进程间不方便进行资源的共享。
- 通信方面:同一进程的线程间可以通过直接读写进程中的数据进行通信,但是进程通信需要借助管道、共享内存、套接字等。
# 线程通信
线程的通信问题其实是线程的同步问题,因为同一个进程的线程共享进程资源,因此应该从线程同步的角度讲。
- 使用volatile关键字,基于 volatile 关键字来实现线程间相互通信是使用共享内存的思想,多个线程同时监听一个变量,当这个变量发生变化的时候 ,线程能够感知到变量的修改。
- 使用Object类的 wait() 和 notify() 方法,使用这两个方法的前提是先获得锁,使用wait()方法让当前线程进入WAITING状态,同时释放锁,使用notify唤醒一个处于WAITING的线程
- 使用 ReentrantLock 结合 Condition
- 基本LockSupport的park()和unpark()方法实现线程间的阻塞和唤醒
- 使用JUC工具类 CountDownLatch
遵循happens-before规则确保变量的可见性
# 进程的状态与转换
# 进程五状态模型
- 创建状态(new) :进程正在被创建,操作系统为进程分配资源、初始化PCB,完成后变成就绪状态,也可能因为内存不足而无法完成创建。
- 就绪状态(ready) :进程已处于准备运行状态,即进程获得了除了处理器之外的一切所需资源,一旦得到处理器资源(处理器分配的时间片)即可运行。
- 运行状态(running) :进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
- 阻塞状态(waiting) :又称为等待状态,进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲,该进程也不能运行。
- 结束状态(terminated) :进程正在从系统中撤销,操作系统会回收进程拥有的资源、撤销PCB。
# 进程的切换
# 进程调度
进程调度是指计算机通过决策决定哪个就绪进程可以获得cpu的使用权,进程切换要进行上下文切换,主要涉及两方面
- 保留旧进程的运行信息
- 选择新进程,准备运行环境并分配cpu
调度算法
- 先来先服务,按照请求的顺序进行调度,非抢占
- 短进程优先,优先选择就绪队列中估计运行时间最短的进程,非抢占
- 最短剩余时间优先,按照剩余运行时间的顺序进行调度,抢占
- 高优先权优先,进程附带优先权,调度程序优先选择权重高的进程
- 时间片轮转,按照先来先服务的原则排列就绪进程,每次从队列头部取出待执行进程,分配一个时间片
# 进程通信
- 管道/匿名管道(Pipes) :用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
- 有名管道(Names Pipes) :匿名管道由于没有名字,只能用于亲缘关系的进程间通信。为了克服这个缺点,提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在,可以实现本机任意两个进程通信。
- 共享内存(Shared memory) :在内存中划出一块共享存储区域,各个进程可以对该共享区的读或写交换信息。这种方式需要依靠某种同步操作,如互斥锁和信号量等。可以说这是最有用的进程间通信方式。
- 套接字(Sockets) : 是一种通信机制,不仅可以实现本地单机进程的通信,还能够实现不同主机间的进程通信。Socket是应用层和传输层之间的桥梁。
- 信号量(Semaphores) :信号量是一个计数器,用于多进程对共享数据的访问,信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问题并避免竞争条件。
- 消息队列
# 匿名管道
匿名管道的创建,需要通过下面这个系统调用:
int pipe(int fd[2])
这里表示创建一个匿名管道,并返回了两个描述符,一个是管道的读取端描述符fd[0],另一个是管道的写入端描述符fd[1],这个匿名管道是特殊的文件,只存在与内存中(内核)。
所谓管道,其实就是内核里面的一串缓存。从管道的一段写入的数据,实际上是缓存在内核中的,另一端读取,也就是从内核中读取这段数据。
但是我们使用pipe这个系统调用是在一个进程中的,那么另一个进程是如何拿到写或读端的文件描述符的?
我们可以使用fork创建子进程,创建的子进程会复制父进程的文件描述符,这样两个线程就各自拥有fd[0]和fd[1]了。
管道只能从一端写入,另一端读出,所以上面这种模式容易造成混乱,实际应由发消息的一方保留fd[1],接受消息的一方保留fd[0],所以就变成了下图所示。
显然如果要用匿名管道实现双向通信,需要建立两个管道。
在linux下使用匿名管道
$ ps auxf | grep mysql
上述命令的意思就是:首先shell进程创建了两个进程,一个是ps打印信息进程,另一个是grep搜索进程,然后将ps auxf输出的信息通过匿名管道传递给grep进程,就是搜索ps auxf输出的信息中有mysql的文字。
匿名管道只能实现有血缘关系的进程间的通信。
# 有名管道
可以使用以下命令创建有名管道,也叫做FIFO,因为数据是先进先出的传输方式。
$ mkfifo myPipe
myPipe就是这个管道的名称,基于Linux一切皆文件的理念,管道也是以文件形式存在与磁盘中的,可以使用ls查看文件,文件类型是p。实际上也是在内核当中创建了一个缓冲区,只不过在内核中给它起了个名。
$ ls -l
prw-r--r--. 1 root root 0 Jul 17 02:45 myPipe
2
对于命名管道,它可以在不相关的进程间也能相互通信。因为命名管道提前创建了一个类型为管道的设备文件,当一个进程以读的方式打开文件,而另一个进程以写的方式打开文件,那么此时内核就会在这两个进程之间建立管道,所以FIFO实际上也由内核管理,不与硬盘打交道。
# 共享内存
共享内存与管道通信方式不同,管道通信都是基于内核缓冲区,而共享内存是基于内存。现代操作系统,对于内存管理,采用的是虚拟内存技术,也就是每个进程都有自己独立的虚拟地址空间,不同进程的虚拟内存映射到不同的物理内存中。所以,即使进程A和进程B的虚拟地址是一样的,其实访问的是不同的物理内存地址。
共享内存机制,就是拿出一块虚拟地址空间来,映射到相同的物理内存中。这样这个进程写入的东西,另一个进程马上就能看到了,而且进程间的通信速度很快。
# Socket
想跨网络与不同主机上的进程之间通信,就需要 Socket 通信了。实际上,Socket通信还可以实现同一主机间的进程通信。
# 进程同步
并发性带来了异步性,有时需要通过进程同步解决这种异步问题,有的进程之间需要相互配合完成工作,各个进程的工作推进需要遵循一定的先后顺序。
# 进程互斥
# 临界资源
临界资源是共享资源,但是无法同时被多个进程访问的资源。对临界资源进行访问的那段代码叫做临界区
对临界资源的访问
while(true){
进入区,上锁
临界区,访问临界资源
退出区,解锁
剩余区
}
2
3
4
5
6
# 访问临界资源的原则
- 空闲让进:资源无占用,允许进程使用
- 忙则等待:资源被占用,请求进程等待
- 有限等待:保证有限的等待时间内能够使用资源
- 让权等待:等待时,进程需要让出cpu,即进程从运行态变为阻塞态
# 进程互斥的硬件实现方法
# 开/关中断指令
利用“开/关中断指令”实现(与原语的实现思想相同,即在某进程开始访问临界区到结束访问为止都不允许被中断,也就不能发生进程切换,因此也不可能发生两个同时访问临界区的情况)
关中断后即不允许当前进程被中断,也必然不会发生进程切换
直到当前进程访问完临界区,再执行开中断指令,才有可能有别的进程上处理机并访问临界区
优点:简单、高效
缺点:不适用于多处理机;只适用于操作系统内核进程,不适用于用户进程(因为开/关中断指令只能运行在内核态,这组指令如果能让用户随意使用会很危险)
# TestAndSet 指令
简称 TS 指令,也有地方称为 TestAndSetLock 指令,或 TSL 指令,TSL 指令是用硬件实现的,执行的过程不允许被中断,只能一气呵成。以下是 C 语言描述的逻辑
// 如果lock为false,则返回false
bool TestAndSet(bool *lock){
bool old;
old = *lock;
*lock = true;
return old;
}
2
3
4
5
6
7
while(TestAndSet(&lock)); // 不断尝试上锁
// 临界区代码段
lock = false; // 解锁
2
3
若刚开始 lock 是 false,则 TSL 返回的 old 值为 false,while 循环条件不满足,直接跳过循环,进入临界区。若刚开始 lock 是 true,则执行 TLS 后 old 返回的值为 true,while 循环条件满足,会一直循环,直到当前访问临界区的进程在退出区进行“解锁”。
相比软件实现方法,TSL 指令把“上锁”和“检查”操作用硬件的方式变成了一气呵成的原子操作。
优点:实现简单,无需像软件实现方法那样严格检查是否会有逻辑漏洞;适用于多处理机环境。
缺点:不满足“让权等待”原则,暂时无法进入临界区的进程会占用CPU并循环执行TSL指令,从而导致“忙等”。
# 进程同步之信号量机制
# 整型信号量
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作,从而很方便的实现了进程互斥、进程同步。
原语是一种特殊的程序段,其执行只能一气呵成,不可被中断。原语是由关中断/开中断指令实现的。
一对原语:wait(S) 原语和 signal(S) 原语,可以把原语理解为我们自己写的函数,函数名分别为 wait 和 signal,括号里的信号量 S 其实就是函数调用时传入的一个参数。wait、signal 原语常简称为 P、V操作(来自荷兰语 proberen 和 verhogen)。
用一个整数型的变量作为信号量,用来表示系统中某种资源的数量。
int S = 1; // S代表资源的数量
void wait(int S){ // wait原语,不可被打断
while(S <= 0) ; // 单处理机下如果资源被占用线程如何退出?
S=S-1; // 如果有资源,则占用一个资源
}
void signal(int S){ // 原语,不可被中断,释放一个资源
S=S+1;
}
2
3
4
5
6
7
8
9
10
由于wait和signal都是原语,避免了并发、异步导致的问题,但是不满足“让权等待”的原则,会发生“忙等”。
# 记录型信号量
为了解决整型信号量“忙等”的现象,使用记录型数据结构表示信号量
// 记录型信号量的定义
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
// wait原语,也可称做P(S)操作
void wait(semaphore S){
S.value--;
if (S.value < 0){
block(S.L);
// 如果剩余资源不够,使用block原语使进程从运行态切换到阻塞态,
// 并将其挂到信号量S的等待队列中
}
}
// signal原语,也可称做V(S)操作
void signal(semaphore S){
S.value++;
if(S.value <= 0){
wakeup(S.L);
// 如果资源释放后,资源数小于等于0,说明有进程在等待资源,
// 使用wakeup原语唤醒等待队列中的一个进程,该进程从阻塞态变为就绪态
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
S.value >= 0 时表示剩余资源的数量,等于0表示资源刚好分配完毕
S.value < 0 时表示当前有-S.value个进程在等待队列中。
记录型信号量解决了“忙等”的问题。
# 信号量机制实现互斥
// 记录型信号量的定义
typedef struct {
int value; // 剩余资源数
struct process *L; // 等待队列
} semaphore;
semaphore mutex = 1; // 只有一个资源,只能同时一个进程访问临界区代码
f1(){
...
P(mutex);
// 临界区代码段
V(mutex);
...
}
f2(){
...
P(mutex);
// 临界区代码段
V(mutex);
...
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
- 分析并发进程的关键活动,划定临界区(如:对临界资源打印机的访问就应放在临界区)
- 设置互斥信号量 mutex,初值为 1
- 在进入区 P(mutex):申请资源
- 在退出区 V(mutex):释放资源
要对不同的临界资源设置不同的互斥信号量,且PV操作必须成对出现。
# 信号量机制实现进程同步
进程同步就是要让各并发进程按要求有序地推进。
f1(){
代码1;
代码2;
代码3;
}
f2(){
代码1;
代码2;
代码3;
}
2
3
4
5
6
7
8
9
10
11
比如f1和f2并发执行,由于存在异步性,两者交替运行的次序是不确定的。
若 P2 的“代码4”要基于 P1 的“代码1”和“代码2”的运行结果才能执行,那么我们就必须保证“代码4”一定是在“代码2”之后才会执行。
解决
semaphore S = 0; // 注意进程同步设置信号量为0
f1(){
代码1;
代码2;
V(S); // 释放资源
代码3;
}
f2(){
P(S); // 申请资源,当时一开始资源是0无法获得资源,只有当f1执行了V(S)之后S.value++后唤醒该进程
代码4;
代码5;
代码6;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
若先执行到 V(S) 操作,则 S++ 后 S=1。之后当执行到 P(S) 操作时,由于 S=1,表示有可用资源,会执行 S--,S 的值变回 0,P2 进程不会执行 block 原语,而是继续往下执行代码4。
若先执行到 P(S) 操作,由于 S=0,S-- 后 S=-1,表示此时没有可用资源,因此P操作中会执行 block 原语,主动请求阻塞。之后当执行完代码2,继而执行 V(S) 操作, S++,使 S 变回 0,由于此时有进程在该信号量对应的阻塞队列中,因此会在 V 操作中执行 wakeup 原语,唤醒 P2 进程。这样 P2 就可以继续执行代码4了。
这样就能保证代码4的执行一定是在代码1、2之后的。
# 信号量机制实现前驱关系
进程 P1 中有句代码 S1,P2 中有句代码 S2 ,P3中有句代码S3 ...... P6 中有句代码 S6。这些代码要求按如下前驱图所示的顺序来执行,就是说S2需要在S1之后执行,S6需要在3、4、5之后执行等。
# 进程同步之管程
和Java中的synchronized差不多
使用管程解决生产者消费者问题
class Monitor{
private List<Integer> produce = new ArrayList<>();
private int capacity;
Monitor(int capacity){
this.capacity = capacity;
}
public synchronized void produce(int item) throws InterruptedException {
if(produce.size() == capacity)
this.wait();
produce.add(item);
this.notifyAll();
}
public synchronized int consume() throws InterruptedException {
if(produce.size() == 0)
this.wait();
int item = produce.remove(produce.size()-1);
this.notifyAll();
return item;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 进程同步问题
# 生产者消费者问题
系统中有一组生产者进程和一组消费者进程,生产者进程每次生产一个产品放入缓冲区,消费者进程每次从缓冲区中取出一个产品并使用。(注:这里的“产品”理解为某种数据)
# 数据不一致问题(互斥访问临界资源)
生产者、消费者共享一个初始为空、大小为n的缓冲区。(两进程需要对缓存区互斥访问)
多个生产者生产产品,放在内存缓冲区中,消费者可以从缓冲区中去数据进行消费,生产者生产产品的时候先将内存中的count读到寄存器中,然后count+1,如果此时消费者进行消费,消费者也会将count读入寄存器,并对count-1,之后写回到内存中,然而生产者此时也将它的寄存器的count写入到内存中,这个时候count为11,按理来说生产者生产了一件产品,消费者消费了一件产品,count应该保持不变。
为什么进程不能够直接修改内存中的count,而需要先读入到寄存器中?
因为cpu速度很快,操作内存的速度很慢,这两者速度不匹配,所以为了匹配上cpu的速度,就有了寄存器,寄存器更快但更小,使用了寄存器就能更上cpu的速度,但是也会产生多程序并发的问题。可以使用进程互斥,使得同一时间最多只有一个进程能够访问临界资源,从而解决多进程修改临界资源带来的数据不一致问题。
# 同步问题缓存区为空时,消费者需要等待生产者生产产品。
缓冲区满时,生产者需要等待消费者消费产品。(同步关系)
# 使用信号量机制解决生产者消费者问题
semaphore mutex = 1; // 互斥信号量,实现对缓冲区的互斥访问
semaphore empty = 5; // 同步信号量,表示空闲缓存区数量,初值是缓冲区大小
semaphore full = 0; // 同步信号量,表示产品数量,初值为0
producer(){
while(1){
// 生产一个产品
P(empty); // 申请一个空闲位置
P(mutex); // 对临界区代码互斥访问
// 把产品放入缓冲区
V(mutex);
V(full); // 释放一个产品
}
}
consumer(){
while(1){
P(full); // 申请一个产品
P(mutex);
// 从缓冲区取走一个产品
V(mutex);
V(empty); // 释放一个空闲位置
// 消费产品
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
能够改变相邻P、V操作的顺序?
producer(){
while(1){
// 生产一个产品
P(mutex); // 1.
P(empty); // 2. 申请一个空闲位置
// 把产品放入缓冲区
V(mutex);
V(full); // 释放一个产品
}
}
consumer(){
while(1){
P(mutex); // 3.
P(full); // 4.申请一个产品
// 从缓冲区取走一个产品
V(mutex);
V(empty); // 释放一个空闲位置
// 消费产品
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
如果此时缓存区满,producer执行到2,此时producer阻塞,consumer执行到3也会进入阻塞,此时陷入死锁。
如果此时缓存区空,consumer执行到4,陷入阻塞,producer执行到1也会组摄,此时也陷入死锁。
因此不能随意交换P的顺序,实现互斥的P操作一定要在实现同步的P操作之后。而V操作不会导致进程阻塞,因此两个V操作的顺序可以交换。
# 哲学家进餐问题
有五位哲学家,围坐在圆桌旁
- 他们只做两件事,思考和吃饭,思考一会吃口饭,吃完饭后接着思考。
- 吃饭时要用两根筷子吃,桌上共有 5 根筷子,每位哲学家左右手边各有一根筷子。
- 如果筷子被身边的人拿着,自己就得等待。
如果哲学家们都同时拿起左手边或者右手边的筷子时,会发生死锁。
如何防止?
- 最多允许4个哲学家同时地去获取筷子,这是至少保证一个哲学家能够吃饭然后释放筷子,这种方式可以添加条件变量S=4,在哲学家申请筷子的时候执行P(S)操作,当吃完饭时执行V(S)操作
- 仅当哲学家的左右两只筷子均可用时,才允许他拿起筷子进餐,可以将P操作改造,传入左右两只筷子代表的信号量,如果能够其中一只筷子被占用了就让当前进程进入阻塞状态,只有当两只筷子都可用时才继续运行。
破坏死锁产生的四个必要条件
- 破坏互斥条件:一般不行
- 破坏请求保持条件:一次申请两双筷子。
- 破坏不可剥夺条件:或者使用可重入锁
ReentrantLock.tryLock()
方法,如果申请筷子得不到满足就放弃申请,同时释放已有的筷子。 - 破坏环路等待条件:给筷子排序,每次哲学家都必须从小的筷子拿
semaphore chopstick[5] = {1, 1, 1, 1, 1};
semaphore mutex = 4; // 最多只运行4个哲学家拿筷子
Pi(){
while(1){
P(mutex);
P(chopstick[i]); // 拿左筷子
P(chopstick[(i+1)%5]); // 拿右筷子
V(mutex);
V(chopstick[i]);
V(chopstick[(i+1)%5]);
}
}
2
3
4
5
6
7
8
9
10
11
12
13
使用Java中的锁解决死锁问题
public class ThreadTest {
public static void main(String[] args) throws InterruptedException {
Chopstick c1 = new Chopstick("1");
Chopstick c2 = new Chopstick("2");
Chopstick c3 = new Chopstick("3");
Chopstick c4 = new Chopstick("4");
Chopstick c5 = new Chopstick("5");
new Philosopher("苏格拉底", c1, c2).start();
new Philosopher("柏拉图", c2, c3).start();
new Philosopher("亚里士多德", c3, c4).start();
new Philosopher("赫拉克利特", c4, c5).start();
// 解决死锁方法一:将申请资源顺序改为c1,c5就不会产生死锁,因为这样破坏了环路等待条件
new Philosopher("阿基米德", c5, c1).start();
}
}
class Philosopher extends Thread {
Chopstick left;
Chopstick right;
public Philosopher(String name, Chopstick left, Chopstick right) {
super(name);
this.left = left;
this.right = right;
}
private void eat() throws InterruptedException {
System.out.println(Thread.currentThread().getName() + " - eating...");
Thread.sleep(1000);
}
@Override
public void run() {
while (true) {
// 获得左手筷子
synchronized (left) {
// 获得右手筷子
synchronized (right) {
// 吃饭
try {
eat();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
// 放下右手筷子
}
// 放下左手筷子
}
}
}
// 解决死锁方法二(破坏不可剥夺条件)
// 使用可重入锁ReentrantLock.tryLock()方法,如果申请筷子得不到满足就放弃申请,同时释放已有的筷子。
// @Override
// public void run() {
// while (true) {
// // 获得左手筷子
// if(left.tryLock()){
// try{
// if(right.tryLock()){
// try {
// eat();
// } catch (InterruptedException e) {
// e.printStackTrace();
// } finally {
// right.unlock();
// }
// }
// }finally {
// left.unlock();
// }
// }
// }
// }
class Chopstick extends ReentrantLock{
String name;
public Chopstick(String name) {
this.name = name;
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
使用jstack pid查看线程死锁
Java stack information for the threads listed above:
===================================================
"阿基米德":
at Philosopher.run(ThreadTest.java:46)
- waiting to lock <0x00000000d7eb3248> (a Chopstick)
- locked <0x00000000d7eb3348> (a Chopstick)
"苏格拉底":
at Philosopher.run(ThreadTest.java:46)
- waiting to lock <0x00000000d7eb3288> (a Chopstick)
- locked <0x00000000d7eb3248> (a Chopstick)
"柏拉图":
at Philosopher.run(ThreadTest.java:46)
- waiting to lock <0x00000000d7eb32c8> (a Chopstick)
- locked <0x00000000d7eb3288> (a Chopstick)
"亚里士多德":
at Philosopher.run(ThreadTest.java:46)
- waiting to lock <0x00000000d7eb3308> (a Chopstick)
- locked <0x00000000d7eb32c8> (a Chopstick)
"赫拉克利特":
at Philosopher.run(ThreadTest.java:46)
- waiting to lock <0x00000000d7eb3348> (a Chopstick)
- locked <0x00000000d7eb3308> (a Chopstick)
Found 1 deadlock.
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
可以看到每个哲学家都持有一只筷子,同时也在等待另一只筷子,这样就产生了死锁。
# 死锁
死锁就是各进程互相等待对方手里的资源,导致各进程都阻塞,无法向前推进的现象。
如何解决死锁问题?
- 死锁预防
- 死锁避免
- 死锁检测和解除
产生死锁的4个必要条件
- 互斥条件:某资源只能由一个进程使用,其他进程需要使用只能等待
- 请求保持条件:进程至少保持一个资源,有提出新的资源请求,请求无法被满足,而该进程又不释放自己保持的资源
- 不可剥夺条件:进程保持的资源只能由自己释放,其他进程不能够剥夺
- 环路等待条件:发送死锁时,必然存在进程资源的环形链
# 死锁预防
预防死锁的方法:破坏产生死锁的4个必要条件
- 破坏互斥条件:互斥条件是非共享设备所必须的,一般不能改变,主要是破坏其它三个条件。
- 破坏请求保持条件:系统规定进程运行之前,一次性申请所有需要的资源,进程在运行期间不会提出资源请求。
- 破坏不可剥夺条件:当一个进程请求新的资源得不到满足时,必须释放占有的资源,自己主动释放。
- 破坏环路等待条件:对可用资源线性排序,申请必须按照需要递增申请,线性申请不会形成环路。
应用在哲学家进餐问题上:
- 破坏请求保持条件:一次申请两双筷子。
- 破坏不可剥夺条件:或者使用可重入锁
ReentrantLock.tryLock()
方法,如果申请筷子得不到满足就放弃申请,同时释放已有的筷子。 - 破坏环路等待条件:给筷子排序,每次哲学家都必须从小的筷子拿
# 死锁避免:银行家算法
# 安全序列
所谓安全序列,就是指如果系统按照这种序列分配资源,则每个进程都能顺利完成。只要能找出一个安全序列,系统就是安全状态。当然,安全序列可能有多个。
如果分配了资源之后,系统中找不出任何一个安全序列,系统就进入了不安全状态。这就意味着之后可能所有进程都无法顺利的执行下去。当然,如果有进程提前归还了一些资源,那系统也有可能重新回到安全状态,不过我们在分配资源之前总是要考虑到最坏的情况。
如果系统处于安全状态,就一定不会发生死锁,如果系统进入不安全状态那么系统就有可能发生死锁(因为有可能进程提前释放资源),系统进入死锁那么一定处于不安全状态。
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态,以此决定资源分配请求,这就是银行家算法的核心思想。
# 算法详情
P0-P4表示进程,A、B、C是三种资源。
数据结构,n是进程个数,m是请求的资源种类数
- 可利用资源向量 Available,1×m
- 最大需求矩阵 Max,n×m
- 已分配矩阵 Allocation,n×m
- 需求矩阵 Need,Need = Max - Allocation
- 请求资源向量 Request,1×m
如果某进程有资源请求,通过以下步骤检查是否可以满足此次资源分配请求
- 检查此次申请是否超过了之前声明的最大需求数
- 检查此时系统剩余的可以资源是否还能满足这次需求
- 试探着分配,更改各数据结构
- 用安全性算法检查此次分配是否导致系统进入不安全状态
安全性算法步骤
- 检查当前剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收
- 不断重复以上过程,如果所有进程都加入了安全序列,那么这次请求就可以满足。
# 死锁检测和解除
# 死锁检测
资源分配图
- 进程结点,一个结点对应一个进程
- 资源结点,对应一类资源,一类资源可能有多个
- 请求边,由进程结点指向资源结点,一条边代表该进程想申请一个资源
- 分配边,由资源结点指向进程结点,一条边表示已经给该进程分配了一个资源
依次消除与不阻塞进程相连的边,直到无边可消,如果不能消除所有边,那么此时就是发生了死锁
不阻塞进程就是指资源申请能够被满足的进程,能够顺利执行下去然后释放资源。
# 死锁解除
用死锁检测算法化简资源分配图后,还连着边的那些进程就是死锁进程,我们需要对这些进程进行适当处理以便解除死锁。
- 资源剥夺法,挂起(暂时放到外存上)某些死锁进程,并抢占它的资源,将这些资源分配给其他死锁进程。
- 撤销进程法,强制撤销部分、或者全部死锁进程,并剥夺这些进程的资源。
参考链接
[1]. 进程通信:https://mp.weixin.qq.com/s/MnIcTR0KKpgnSoA3xaPUSA