3.11.哲学家进餐问题

有五个哲学家，他们的生活方式是交替地进行思考和进餐，哲学家们共用一张圆桌，分别坐在周围的五张椅子上，在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐，该哲学家进餐完毕后，放下左右两只筷子又继续思考。

约束条件

(1)只有拿到两只筷子时，哲学家才能吃饭

(2)如果筷子已被别人拿走，则必须等别人吃完之后才能拿到筷子

(3)任一哲学家在自己未拿到两只筷子吃完饭前，不会放下手中已经拿到的筷子

1.每个进程需要两个或者多个临界资源

2.①限制最多有4个哲学家进餐

semaphore cur = 4;    //表示当前最多还能允许几个人几餐
semaphore chopstick[5] = {1, 1, 1, 1, 1};
i() {    //第i个哲学家
    while(1) {
        P(cur);
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5];
        进餐;
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5];
        V(cur);
    }
}

②用mutex实现对临界资源（拿筷子）的互斥访问：如果当前A正在进行拿左边筷子的操作，即A已经执行了P(mutex)，但还未执行V(mutex)，此时mutex = 0，若发生进程切换，切换到B后，将会阻塞在P(mutex)，也就不会发生死锁，直到切换回A执行完V(mutex)后，B将会被唤醒

semaphore mutex = 1;    //互斥信号，用于实现一次仅能有一个人进行拿筷子的操作
semaphore chopstick[5] = {1, 1, 1, 1, 1};
i() {
    while(1) {
        P(mutex);    
        P(chopstick[i]);
        P(chopstick[(i + 1) % 5];
        V(mutex);
        进餐;
        V(chopstick[i]);
        V(chopstick[(i + 1) % 5];
    }
}

3.12.管程

1.管程用于实现进程的同步和互斥（与信号量作用相同，但更加方便）

2.管程是一种特殊的软件模块，由①②③④组成：（类似于类）

①局部于管程的共享数据结构说明（例如生产者和消费者模型中的缓冲区，可以通过数据结构表示该缓冲区，对该缓冲区进行管理；若使用，则需要定义一种与该缓冲区相对应的数据结构）

②对该数据结构进行操作的一组过程（过程可以理解为函数，即管程中需要有一组对①中数据结构进行操作的函数）

③对局部于管程的共享数据设置初始值的语句（管程中需要有对①中数据结构初始化的语句）

④管程需要有个名字

3.管程的基本特征：

①局部于管程的数据只能被局部于管程的过程所访问

②一个进程只有通过调用管程内的过程才能进入管程访问共享数据

③每次仅允许一个进程在管程内执行某个内部过程（管程中虽然可能定义了很多个函数，但是同一时间只可能有一个进程在使用管程的某个函数，其余的进程若想执行管程的其他函数，需要等待该进程执行完该管程函数）

①②的意思是：管程中定义的数据结构只能被管程的函数修改，即想要修改管程中的数据需要调用管程的函数间接修改

③的作用是实现对缓冲区（临界资源）的互斥访问

4.死锁

4.1.死锁的概念

1.死锁：在并发环境下，各进程因抢占资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，无法继续执行的现象（每个进程都等待对方手里的资源，但是不放弃自己手里的资源，如果没有外力干涉，这些进程就无法继续向前推进）

2.死锁、饥饿、死循环的区别和联系：

3.死锁产生的必要条件：

①互斥条件：只有对必须互斥使用的资源的争夺才会导致死锁的发生（哲学家的筷子）；可以多个进程同时使用的资源不会发生死锁（内存）

②不剥夺条件：进程所获得的资源在其使用完之前，不能由其他进程强行拿走，只能主动释放

③请求和保持条件：进程已经至少持有一种资源的条件下，又申请了别的资源的请求，而该资源被其他进程所占有，此时请求进程被阻塞，但是对该进程已持有资源保持不放

④循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求（例如哲学家问题中，若每个人都持有左边的筷子，都在等待右边的筷子）

同类资源 > 1时：发生死锁时一定有循环等待链，但有循环等待链不一定发生死锁（必要非充分条件）；同类资源 = 1时，循环等待链的出现一定导致死锁的发生，死锁的发生一定有循环等待链（充分必要条件）

4.死锁的处理策略：

①预防死锁：破坏死锁产生的四个必要条件中的一个或多个

②避免死锁：用某种算法防止系统进入不安全状态，从而避免死锁（银行家算法）

③死锁的检测和解除：允许死锁发生，操作系统会检测出死锁的发生，并且解除死锁  

4.2.预防死锁

1.破坏互斥条件：

2.破坏不剥夺条件： 3.破坏请求和保持条件：导致饥饿是因为如果有源源不断的新的A类和B类进程，那么C类进程就将永远无法执行，即饥饿

4.破坏循环等待条件：

①实际使用资源的顺序可能和编号递增顺序不一致会导致资源浪费的原因：假设在实际使用过程中进程P3是先使用7号后使用5号，但根据编号递增顺序的要求，P3必须先申请使用5号，再申请使用7号，则在P3实际运行中5号某些时间是空闲的

②用户编程麻烦的原因：不同主机对不同设备的编号可能不同，但编号的不同会影响申请资源的顺序，即程序需要根据编号的不同而变化

4.3.避免死锁（银行家算法）

1.安全状态→不会死锁（充分条件）；死锁→不安全状态（不安全状态并不一定导致死锁）

2.只要有一个安全序列，就是安全状态（安全序列可能有多个）

3.银行家算法的思想：在资源分配前先预判这次分配是否会导致进入不安全状态，若会，则不进行此次分配‘若不会，则进行此次分配

4.①找到（3,3,2）能满足的进程→P1、P3加入安全队列，并且将P1、P3已分配资源拿回→（7,4,3）

②找到（7,4,3）能满足的进程（除P1、P3外）→P0、P2、P4都可以→安全队列：P1、P3、P0、P2、P4（不唯一）

4.4.死锁的检测和解除

4.4.1.死锁的检测

1.进程结点（圆）：一个结点对应一个进程

资源结点（矩形）：一个结点对应一类资源，该结点中的一个小结点（矩形中的圆）对应该类资源的一个资源（三个小结点则表示该类资源共有三个）

请求边（进程指向资源的边）：表示该进程对该类资源的请求，一条边对应一个资源

分配边（资源指向进程的边）：表示该类资源对该进程已经分配了几个资源，一条边对应一个资源

2.如果能消除所有边，则一定不会发生死锁；如果不能消除所有边，则发生死锁

（1）可以消除所有边，即不会发生死锁：

P1向R2请求一个资源，P2向R1请求一个资源；R1给P1分配了两个资源，R2给P2分配了一个资源

①P2申请R1的1个资源，而R1此时没有剩余资源，因此P2阻塞 ②R2剩余1个资源，可以满足P1的申请→P1执行完后，就可以将之前占用的两个R1归还

③R1剩余2个资源，可以满足P2的申请，即P1和P2的运行不会发生死锁

（2）不可以消除所有边，即发生死锁：

P1请求R2的两个资源，而R2的两个资源一个分配给P2，另一个分配给P3（P3的R2资源可以归还，但仍差一个）；P2请求R1的一个资源，而R1的三个资源两个分配给P1，一个分配给R1，无空闲的R1资源，发生死锁

3.检测死锁的方法：

①在资源分配图中，找到既不阻塞（该点申请资源的数量可以满足它的需求，如P1）又不是孤点（该点至少与一个有向边相连，P1和P2都不是孤点）的进程：P1符合条件

②消去该进程的所有请求边和分配边，使之成为孤点：消去P1所有的边，P1成为孤点

③消去该进程的边即释放该点的资源，因此，可以唤醒某些等待这些资源而被阻塞的进程：R1此时可以满足P2的申请，P2也可以消去所有的边，成为孤点

④所有边都可以消去，则该图是可完全简化；若该图是不可完全简化，则系统死锁

4.4.2.死锁的解除