Jepson's Blog

死锁定义

线程死锁是指由于两个或者多个线程互相持有对方所需要的资源，导致这些线程处于等待状态，无法前往执行。

必要条件

互斥：每个资源要么已经分配给了一个进程，要么就是可用的。

占有和等待：已经得到了某个资源的进程可以再请求新的资源。

不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。

环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

死锁的处理策略

1. 鸵鸟策略

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

   因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

   当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

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

2. 死锁预防：破坏死锁的四个条件之一

   破环互斥条件：允许资源共享；

   破环占有和等待条件：一次性分配所有资源，只要缺少一个资源，其它资源也都不给他分配；

   破坏不可抢占：请求新资源得不到时，释放已经保持占有的资源，待以后重新申请；

   破坏环路等待：采用顺序资源分配法，给每个资源编号，进程申请资源的时候按照编号顺序申请，释放的时候则相反；

3. 死锁检测与解除：

   检测死锁：利用死锁原理化简资源分配图检测死锁的存在

   死锁解除：资源剥夺、撤销进程、进程回退

    剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态；
   
    撤消进程：可以直接撤消死锁进程或撤消代价最小的进程，直至有足够的资源可用，死锁状态.消除为止；所谓代价是指优先级、运行代价、进程的重要性和价值等。
   

4. 死锁避免：死锁避免事先预防策略，但是是采用资源动态分配的过程中，防止系统进入不安全状态，以避免死锁。

   预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得 较满意的系统性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。

   银行家算法：首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况。因此，状态包含两个向量Resource（系统中每种资源的总量）和Available（未分配给进程的每种资源的总量）及两个矩阵Claim（表示进程对资源的需求）和Allocation（表示当前分配给进程的资源）。安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。

银行家算法

银行家算法是仿照银行发放贷款时采用的控制方式而设计的一种死锁避免算法，该算法的策略是实现动态避免死锁。

算法思想

银行家算法的基本思想是：分配资源之前，判断系统是否安全，如果安全才会进行资源分配。

我们把操作系统看做是银行家，操作系统管理的资源相当于银行家的资金，线程向操作系统请求分配资源就是用户向银行家要贷款。

算法在每次分配资源前需要要求： request < available && request < needing;

算法实例

系统中有R1，R2，R3三种资源，在time0时刻，5个线程T0，T1，T2，T3，T4对资源占用和需求的情况如下表，此时系统的可用资源向量为(3,3,2)。求T0时刻系统是否存在安全序列？

我们假设每个线程执行时间为一个时刻。

1、在time0时刻，available(3,3,2) > T1.needing(1,2,2)； 所以T1可以执行，T1执行完毕之后available = T1.allocated(2,0,0) + available(3,3,2) = (5,3,2);

2、进入time1时刻，available(5,3,2) > T3.needing(0,1,1)；所以T3可以执行，T3执行完毕之后available = T3.allocated(2,1,1)+available(5,3,2) = (7,4,3)；

3、进入time2时刻，available(7,4,3) > T4.needing(4,3,1)；所以T4可以执行，T4执行完毕之后available = T4.allocated(0,0,2) + available(7,4,3) = (7,4,5)；

4、进入time3时刻，available(7,4,5) > T2.needing(6,0,0)；所以T2可以执行，T2指向完毕之后available = T2.allocated(3,0,2) + available(7,4,5) = (10,4,7)；

5、进入time4时刻，因为available(10,4,7) > T0.needing(7,4,3)；所以执行T0。完成安全序列。

上面只是安全序列的一个例子，可能还存在其他安全序列。

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

进程同步：控制多个进程按一定顺序执行；

进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

   它具有以下限制：

   只支持半双工通信（单向交替传输）；
   只能在父子进程或者兄弟进程中使用。

2. FIFO

   也称为命名管道，去除了管道只能在父子进程中使用的限制。

3. 消息队列

   相比于 FIFO，消息队列具有以下优点：

    消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
   
    避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
    
    读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。
   

4. 信号量

   它是一个计数器，用于为多个进程提供对共享数据对象的访问。

5. 共享存储

   允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制，所以这是最快的一种 IPC。

   需要使用信号量用来同步对共享存储的访问。

   多个进程可以将同一个文件映射到它们的地址空间从而实现共享内存。另外 XSI 共享内存不是使用文件，而是使用内存的匿名段。

6. 套接字
   与其它通信机制不同的是，它可用于不同机器间的进程通信。

目前的瓶颈：应用场景

有源方案的问题：头上只有两个点，测朝向有局限性

无源方案的问题：只做头部朝向的分类，太小了

都存在的问题：呼吸和心跳融不进头部朝向

卖技术：一个技术能在很多场景应用

卖故事：把一个应用场景的故事讲的很好

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

1
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

typedef int samephore;

void down(int* x){}
void up(int* y){}

int count = 0;
samephore count_mutex = 1;
samephore data_mutex = 1;

void reader(){
    while(true){

        down(&count_mutex);
        count ++;
        if(count==1) down(&data_mutex);
        up(&count_mutex);
        //read
        down(&count_mutex);
        count --;
        if(count==0) up(&data_mutex);
        up(&count_mutex);
    }
}
void writer(){
    while(true){
        down(&data_mutex);
        //write
        up(&data_mutex);
    }
}

此解法中读者是优先的，当存在读者时，写者将被延迟，且只要有一个读者活跃，随后而来的读者都将被允许访问此文件，从而导致写者长时间等待，并有可能出现写者饥饿现象。

增加信号量并修改此程序，让写者与读者平等：

1
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

samephore s = 1;

void reader(){
    while(true){
        down(&s);
        down(&count_mutex);
        count ++;
        if(count==1) down(&data_mutex);
        up(&count_mutex);
        up(&s);

        //read
        
        down(&count_mutex);
        count --;
        if(count==0) up(&data_mutex);
        up(&count_mutex);
    }
}
void writer(){
    while(true){
        down(&s);
        down(&data_mutex);
        //write
        up(&data_mutex);
        up(&s);
    }
}

假设进程队列：R1、W1、W2、R2、R3

当R1刚刚执行完V(s)，W1进程若调度会卡在P(writeblock)，而W2R2R3想要运行，均会卡在P(s)，当R1读完，V(writeblock)完成，W1可以运行，以此类推，R1W1W2R2R3按顺序调度。

同步

同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

进程间的直接制约关系就是源于它们之间的相互合作。例如：上面两个程序可以看成5+3*5中的加法程序和乘法程序。若先执行乘法程序再执行加法程序，则5+3*5=20。这个答案一定是对的吗？其实不然。如果我们想要的答案是40，就要先执行加法程序再执行乘法程序，(5+3)*5=40。我们通过加 () 改变了运算的先后顺序，使先乘除后加减变成了先加减后乘除，这就是一种同步机制。

互斥

互斥亦称间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

例如，在仅有一台打印机的系统中，有两个进程A和进程B，如果进程A需要打印时，系统已将打印机分配给进程B，则进程A必须阻塞。一旦进程B将打印机释放，系统便将进程A唤醒，并将其由阻塞状态变为就绪状态。为禁止两个进程同时进入临界区，同步机制应遵循以下准则：

空闲让进：临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。

忙则等待：当已有进程进入临界区时，其他试图进入临界区的进程必须等待。

有限等待：对请求访问的进程，应保证能在有限时间内进入临界区。

让权等待：当进程不能进入临界区时，应立即释放处理器，防止进程忙等待。