iOS-死锁原理(银行家算法)

俗话说“书卷多情似故人，晨昏忧乐每相亲”闲暇之时，我们还是要多和故人联络联络感情。哈哈，言归正传，安闲之余，看操作系统原理一书，里面有一章节讲解的是死锁，很多人认为，死锁是很高端的操作系统层面的问题，离我们很远，一般不会遇上。其实这种想法是非常错误的，作为一名iOS开发，在iOS中，下面这段常见的程序就会造成死锁：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        dispatch_sync(dispatch_get_main_queue(), ^(void){
            NSLog(@"这里死锁了");
        });
    }
    return 0;
}

分析这段代码，首先要知道dispatch_sync 和 dispatch_async 的区别：
dispatch_async(queue,block) async 异步队列，dispatch_async 函数会立即返回, block会在后台异步执行。

dispatch_sync(queue,block) sync 同步队列，dispatch_sync 函数不会立即返回，即阻塞当前线程,等待block同步执行完成。

同步

同步执行：比如这里的dispatch_sync，这个函数会把一个block加入到指定的队列中，而且会一直等到执行完blcok，这个函数才返回。因此在block执行完之前，调用dispatch_sync方法的线程是阻塞的。

异步

异步执行：一般使用dispatch_async，这个函数也会把一个block加入到指定的队列中，但是和同步执行不同的是，这个函数把block加入队列后不等block的执行就立刻返回了。

串行队列

串行队列：比如这里的dispatch_get_main_queue。这个队列中所有任务，一定按照FIFO(先来后到的顺序)执行。

并发队列

比如使用dispatch_get_global_queue。这个队列中的任务也是按照FIFO(先来后到的顺序)开始执行，注意是开始，但是它们的执行结束时间是不确定的，取决于每个任务的耗时。并发队列中的任务：GCD会动态分配多条线程来执行。具体几条线程取决于当前内存使用状况，线程池中线程数等因素。

总结：

执行这个dispatch_get_main_queue队列的是主线程。执行了dispatch_sync 同步函数后，将block添加到了main_queue中，同时调用dispatch_syn 同步这个函数的线程（也就是主线程）被阻塞，等待block执行完成，而执行主线程队列任务的线程正是主线程，此时他处于阻塞状态，所以block永远不会被执行，因此主线程一直处于阻塞状态。因此这段代码运行后，并非卡在block中无法返回，而是根本无法执行到这个block。

由上面的例子可以延展思考，造成死锁的原因有以下四点：

死锁001.jpg

那么处理死锁的基本方法也有以下四种

死锁002.jpg

死锁的避免，通过算法合理的分配资源，使系统处于安全状态，就牵扯了一个著名的算法---银行家算法

死锁003.jpg

下面通过一个例子，来讲解下银行家算法：

死锁004.jpg

图中已知的信息有:
(1).进程P0、P1、P2、P3、P4、P5；
(2).资源A、B、C 在T0时刻allocation已分配的情况；
(3).资源A、B、C 在T0时刻Max最大需求的数量；

求：(1)Need矩阵内容？ (2)此时系统是否安全？

1.根据已知的信息，我们首先算得A、B、C资源的Need还需要资源的情况，Need矩阵的内容计算过程如下：

Need还需要 = Max最大需求 - allocation已分配
P0：(7,5,3) - (0,1,0) = (7,4,3);
P1：(3,2,2) - (2,0,0) = (1,2,2);
P2：(9,0,2) - (3,0,2) = (6,0,0);
P3：(2,2,2) - (2,1,1) = (0,1,1);
P4：(4,3,3) - (0,0,2) = (4,3,1);

所以，算得的Max最大需求填到图005，如下所示：

死锁005.jpg

至此，此时第一步Need矩阵的内容计算完毕。

2.计算此时系统是否安全？

首先设置初始化变量：
work = Available = [3,3,2];
finish[0]=finish[1]= finish[2]=finish[3]= finish[4]=false；
需循环检测是否能找到⼀一个进程pi，满⾜足finish[i]=false且Needi<= Available；

• 2.1 因为： P0：finish[0] = false ，Need1 >= Available/work 即:(7,4,3)>= (3,3,2);
  所以：finish[0] = false ,不满足条件；
• 2.2 因为： P1：finish[1] = false ，Need1 <= Available/work ， 即：(3,3,2) <= (1,2,2)
  所以: finish[0] = true ,满足条件；
  此时Available可用资源为：
  work = Available - Need1 = [3,3,2] - [1,2,2] = [2,1,0];
  work =Available[2,1,0] + Max1[3,2,2] = [5,3,2];
  所以: 按程序执行的第一个进程为P1 ;

2.3 因为： P2：finish[2] = false ，Need2 >= **Available/work **， 即：(6,0,0) >= (5,3,2)；
所以：finish[2] = false ,不满足条件；

• 2.4 因为： P3：finish[3] = false ，Need3<= Available/work ** ，即：(0,1,1) <= (5,3,2);
  所以: finish[3] = true ,满足条件；
  此时work可用资源为：
  work = ** work[5,3,2] - Need3[0,1,1] = [5,2,1];
  work= work [5,2,1] + Max3[2,3,2] = [7,4,3];
  所以: 按程序执行的第二个进程为P3 ;

• 2.5 因为： P4：finish[4] = false ，Need4<= Available/work ** ，即：(4,3,1) <= (7,4,3);
  所以: finish[4] = true ,满足条件；
  此时work可用资源为：
  work = ** work[7,4,3] - Need4[4,3,1] = [3,1,2];
  work= work [3,1,2] + Max4[4,3,3] = [7,4,5];
  所以: 按程序执行的第三个进程为P4 ;

此时，P0--P4第一轮已经执行完毕，finish[1]=finish[3]= finish[4]=ture；，所以接下来我们需要再次检测finish[0] = finish[2]=false；在T1时刻是否是安全的，相同的方法进行第二轮检测：

• 2.6因为： P0：finish[0] = false ，Need0<= **Available/work ** ，即：(7,4,3) <= (7,4,5);
  所以: finish[0] = true ,满足条件；
  此时work可用资源为：
  work = work[7,4,5] - Need0[7,4,3] = [0,0,2];
  work= work[0,0,2] + Max0[7,5,3] = [7,5,5];
  所以: 按程序执行的第四个进程为P0 ;

• 2.7因为： P2：finish[2] = false ，Need2<= **Available/work ** ，即：(6,0,0) <= (7,5,5);
  所以: finish[2] = true ,满足条件；
  此时work可用资源为：
  work = work[7,5,5] - Need0[6,0,0] = [1,5,5];
  work= work [1,5,5] + Max2[9,0,2] = [10,5,7];
  所以: 按程序执行的第五个进程为P2 ;

所以T0时刻，找到的安全序列为< P1--P3 --P4 --P0 --P2 >
至此，再也找不到满足finish[i]=ture 并且Needi<= work条件的进程了，因此循环结束。

死锁006.png

死锁的学习暂时记录以上信息，方便日后查阅。