操作系统笔记【进程互斥同步及通信死锁问题】

(一) 进程间的互斥关系

(1) 电影院多线程问题引入

由于我们今天的问题是基于并发的，所以我简单的通过一个 Java 多线程的例子来引入今天的内容（今天主要讲的是进程，这里的多线程问题，体会一下出现的问题就好了）

在SellTicket类中添加sleep方法，延迟一下线程，拖慢一下执行的速度

public class SellTickets implements Runnable {
    //电影票数
    private int ticket = 10;

    @Override
    public void run() {
        while (true){
            if (tickets > 0){
                try {
                    Thread.sleep(100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(Thread.currentThread().getName() 
                                   + "正在出售第" + (tickets--) + "张票");
            }
        }
    }
}

我这里为了篇幅只讲票数定义到了10张，自己测试可以设置的稍微多一些，更好看出结果

public class SellTicketsTest {
    public static void main(String[] args) {
        //创建资源对象
        SellTickets st = new SellTickets();

        //创建线程对象
        Thread t1 = new Thread(st, "窗口1");
        Thread t2 = new Thread(st, "窗口2");
        Thread t3 = new Thread(st, "窗口3");

        //启动线程
        t1.start();
        t2.start();
        t3.start();
    }
}

执行测试代码看一下结果

窗口3正在出售第10张票
窗口2正在出售第8张票
窗口1正在出售第9张票
窗口3正在出售第7张票
窗口2正在出售第5张票
窗口1正在出售第6张票
窗口2正在出售第4张票
窗口3正在出售第3张票
窗口1正在出售第3张票
窗口2正在出售第2张票
窗口1正在出售第1张票
窗口3正在出售第1张票

仅仅通过10张票，就能看到问题，首先票的顺序乱了，理应是10、9、8 … 2、1 但是出现了 10、8、9这种问题，其次例如 1 和 3 这两章票，却卖了多次，显然是极其不合理的，如果数量多的情况下，有时候还可能出现负数票，具体原因大家可以去看我 Java基础教程中的多线程入门那篇

我简单摘一下：

线程1执行的同时线程2也可能在执行，所以可能导致在读取 tickets-- 时原来的数值和减1过程的中间挤进了两个线程而出现重复，这就是重复票的问题，归根结底是因为多个线程不加控制的访问操作 ticket 这个变量

但是我们要解决这个问题怎么弄呢，当然有很多种方法，我们后面也会介绍，而 Java 中常用的一种方式就是加锁

下面是一个 Lock锁 的实例，当然还有其他的锁，例如同步锁等等，但是 Java 中的具体实现不是我们这篇文章想要讲的，我们对于这里看一下效果就好了

import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class SellTickets2 implements Runnable {

    private int tickets = 10;

    private Lock lock = new ReentrantLock();

    @Override
    public void run() {
        while (true) {
            try {
                lock.lock();
                ;
                if (tickets > 0) {
                    try {
                        Thread.sleep(150);
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                    System.out.println(Thread.currentThread().getName() + "正在出售第" + (tickets--) + "张票");
                }
            } finally {
                lock.unlock();
            }
        }
    }
}

执行一下

窗口1正在出售第10张票
窗口1正在出售第9张票
窗口2正在出售第8张票
窗口2正在出售第7张票
窗口2正在出售第6张票
窗口2正在出售第5张票
窗口2正在出售第4张票
窗口2正在出售第3张票
窗口2正在出售第2张票
窗口2正在出售第1张票

果然上面的问题得到了解决

而进程也是这样，在两个进程并发执行的过程中，如果一个进程对共享变量（例如：ticket）访问还没有完全结束，另外一个进程就开始访问的话，就会产生数据冲突。像这样的共享变量一次只允许一个进程访问，这样，两个进程在使用这种共享变量的时候就产生一种竞争关系，也就是进程间的互斥关系。如果在进程并发执行的过程中，没有考虑这种互斥关系，从而没有加以有效控制的话，就会出现问题

(2) 互斥

一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位执行 不允许两个以上的共享该资源的进程同时进入临界区

由于各进程要求共享资源，而有些资源需要互斥使用，即多个进程不能同时使用同一个资源，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥

(3) 临界区（Critical Section）

把不允许多个并发进程交叉执行的一段程序称作临界区

系统中某些资源一次只允许一个进程使用，这样的资源为临界资源（critical resource） 或互斥资源或共享变量

(4) 临界区的访问过程

这些名词会在介绍互斥方法的时候默认使用喔 ~

• 进入区：在进入临界区之前，检查是否可以进入临界区的一段代码，如果可以，设置正在访问临界区标志
• 临界区：进程中访问临界资源的一段代码
• 退出区：用于将正在访问临界区标志删除
• 剩余区：代码中的其余部分

(5) 临界区准则

• 有空让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入
• 无空等待：不允许两个以上的进程同时进入互斥区
• 多中择一：当没有进程在临界区，而同时有多个进程要求进入临界区，只能让其中之一进入临界区，其他进程必须等待
• 有限等待：任何进入互斥区的要求应在有限的时间内得到满足
• 让权等待：处于等待状态的进程应放弃占用 CPU
• 平等竞争：任何进程无权停止其它进程的运行，进程之间相对运行速度无硬性规定

(二) 加锁实现互斥的方式

(1) 单标志法

基本思想是设立一个公用整型变量 turn，描述允许进入临界区的进程标识

进入临界区之前先检查turn，如果等于进程号，就可以进入临界区，否则循环等待，因此可以实现互斥

这个图简单说一下，例如进程 Pi先进来，现在由于 turn = i 所以不进循环，直接进入临界区，如果这个时候进程 Pj 也想进来，但是却因为 turn = i所以只能进入 循环 while(tuen != j) 直到进程 Pi 从临界区出来后，重新将 trun 设置为 j 后面 Pj 就可以进入临界区了

特点：

• 等待期间会耗费处理器时间
• 两个进程交替使用处理器，执行速度取决于慢的进程
• 如果一个终止（无论是在临界区内还是临界区外），另一个会被永远阻塞

(2) 双标志法（先检查）

双标志是设立一个标志数组 flag[]：描述进程是否在临界区，初值均为 FALSE，表示进程不在临界区

其基本思想是：

• 先检查，后修改：在进入区检查另一个进程是否在临界区，不在时修改本进程在临界区的标志；
• 在退出区修改本进程在临界区的标志

优点：不用交替进入，可连续使用；

缺点：Pi 和 Pj可能同时进入临界区。在Pi 和 Pj都不在临界区时，假设 Pi Pj 进入区的两部并发执行时，会同时进入临界区。即在检查对方 flag 之后发生进程切换，结果都通过检查。这里的问题出在检查和修改操作不能连续进行

(3) 双标志法（后检查）

算法 3 类似于算法 2，与算法 2 的区别在于先修改后检查。可防止两个进程同时进入临

界区。其缺点为：Pi和 Pj 可能都进入不了临界区。在 Pi和 Pj 都不在临界区时，假设按 "Pi (第一步)

Pj (第一步) Pi (第二步) Pj (第二步)"顺序并发执行时，会都进不了临界区，即在设置进入临界区的标志后发生

进程切换，结果检查都不能通过

(4) 双标志法改进版

算法 4 结合算法 1 和算法 3，是正确的算法。当同时修改标志时，采用标志 turn 描述可进入的进程

其主要思想是在进入区先修改后检查，并检查并发修改的先后

• 检查对方 flag，如果不在临界区则自己进入——空闲则入
• 否则再检查 turn：保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入，即先到先入，后到等待

(三) 信号量实现互斥的方式

前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS 可从进程管理者的角度来处理互斥的问题，信号量就是 OS 提供的管理公有资源的有效手段。信号量的值代表可用资源实体的数量

每个信号量 s 除了一个整数值 s.count（计数）, 还有一个进程等待队列 s.queue，其中存储的是阻塞在该信号量的各个进程的标识。

信号量只能通过初始化和两个标准的原语（P、V原语）来访问——作为 OS 核心代码执行，不受进程调度的打断

信号量在始化时被指定一个非负整数值，表示空闲资源总数（又称为“资源信号量”）

在进程执行过程中，信号量的值（即其计数值）可能发生变化

• 若为非负值，表示当前的空闲资源数
• 若为负值，其绝对值表示当前等待临界区的进程数

(1) P 原语

在互斥问题中，申请使用临界资源时调用 P 原语，其实现原理为：

P(Semaphore s) {
    --s.count; //表示申请一个资源;
     if (s.count <0) { //表示没有空闲资源;
        调用进程进入等待队列 s.queue;
        阻塞调用进程;
    }
 }

(2) V 原语

V 原语通常唤醒进程等待队列中的头一个进程，其实现原理为：

V(Semaphore s ) {
    ++s.count; //表示释放一个资源；
    if (s.count <= 0) { //表示有进程处于阻塞状态；
        从等待队列 s.queue 中取出一个进程 P;
        进程 P 进入就绪队列;
    }
 }

(四) 加锁法和信号量法的区别

(五) 进程同步

(1) 基本概念

进程同步：把异步环境下的一组并发进程，因直接制约并互相发送消息而进行的相互合作、相互等待，并使进程按照一定的顺序和速度执行的过程

合作进程：具有同步关系的一组进程

消息：合作进程互相发送的信号，则可使用以下过程：

• Wait(消息名)：表示进程等待合作进程发来消息
• Signal(消息名)：表示向合作进程发送消息

(2) 信号量分类

私用信号量：也可以把各进程之间发送的消息作为信号量看待

公用信号量：互斥时使用的信号量称为公用信号量

(六) 经典互斥同步问题

(1) 生产者消费者问题

问题描述：若干进程通过有限的共享缓冲区交换数据。其中，"生产者"进程不断写入，

而"消费者"进程不断读出；共享缓冲区共有 N 个；任何时刻只能有一个进程可对共享缓冲区

进行操作。

• 任何时刻只能有一个进程可对共享缓冲区进行操作，可知使用共享缓冲区的生产者与生产者之间、生产者与消费者之间以及消费者与消费者之间存在互斥关系。
• 缓冲区不满，生产者才能写入；缓冲区不空，消费者才能读出，可知生产者与消费者之间存在同步关系。

(2) 读写问题

问题描述：对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许

多个，要求：

• “读－写” 互斥
• “写－写” 互斥
• “读－读” 允许

(3) 哲学家就餐问题

就餐条件：

哲学家想吃饭，先提出吃饭要求

提出吃饭要求后，并拿到两双筷子后，方可吃饭。如果筷子被他人获得，则必须等待此人吃完后，才能获取筷子

对于已经申请吃饭的任意一个哲学家在自己未拿到两只筷子吃饭之前，不放下自己的筷子

刚开始就餐时，只允许两个哲学家请求吃饭

要考虑的问题是如何保证哲学家们的动作有序进行？如：

• 不出现相邻者同时要求进餐；
• 不出现有人永远拿不到筷子

试着解答这几个问题：

（1）描述一个保证不会出现两个邻座同时要求吃饭的通信算法。

（2）描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。

（3）在什么情况下，5个哲学家全部吃不上饭？

解答第一问：

(1) 首先分析，5只筷子都属于临界资源，所以五个哲学家 philosopher(i) 取筷子的时候就需要互斥，为满足第一点所以就需要按一定顺序取筷子

设公用信号量 fork[i] 其初值为 1 ，i 的取值为 0-4，规定先取右边的，再取左边的 当 i = 4 左边的筷子是 (i + 1) mod 5 即等于0

算法结果如下：

i = 0,1,2,3,4
philosopher(i)
    begin
        //思考
        //就餐
        P(fork[i])
            P(fork[(i + 1) mod 5])
                eat()
            V(fork[(i + 1) mod 5])
        V(fork[i])
    end

上述的代码可以保证不会有两个相邻的哲学家同时进餐，但却可能引起死锁的情况。假如五位哲学家同时饥饿而都拿起的左边的筷子，就会使五个信号量chopstick都为0，当他们试图去拿右手边的筷子时，都将无筷子而陷入无限期的等待

解答第二问：

防止死锁策略1

(2) 这种情况，只需要有一位哲学家按相反的顺序取筷子

i = 0,1,2,3
philosopher(i)
    begin
        //思考
        //就餐
        P(fork[i])
            P(fork[i + 1])
                eat()
            V(fork[i + 1])
        V(fork[i])
    end

前三位依旧是先拿右边，再拿左边，而最后一位规定，先拿左边，再拿右边

philosopher(4)
    begin
        //思考
        //就餐
        P(fork[0])
            P(fork[4])
                eat()
            V(fork[4])
        V(fork[0])
    end

解答第三问：

(3) 第二种情况，解决了出现饿死的现象，第三种情况，就是在第一种情况下出现的，也就是当每位哲学家都取到了左边的筷子，试图去取右边的筷子，就会出现五位哲学家都吃不上饭的情况

当然防止死锁的方法有很多种，如果有兴趣，可以自己写成具体的代码试一试，以及参考一下别人一些好的算法

(七) 进程通信

(1) 分类

进程通信共有四种方式

A：主从式

主进程可以自由使用从进程资源

从进程的动作受到主进程的限制

主进程和从进程关系固定

应用于终端控制进程和终端进程

B：会话式

使用进程在使用服务进程提供的服务前，必须得到许可

服务进程根据使用进程的要求提供服务，单控制权属于服务进程本身使用进程和服务进程关系固定

应用于用户进程和磁盘管理

C：消息或邮箱机制

只要存在空缓存区或邮箱，发送进程就可以发送消息

发送进程和接受进程无直接联系

发送进程和接受进程之间存在缓冲区或邮箱用来存放被传输的消息

D：共享内存机制

共享内存方式不要求数据移动，两个需要互相交互的信息的进程通过对同一共享数据区（shared memory)的操作来达到互相通信的目的

(2) 消息缓冲机制

系统在操作系统空间设置一组缓冲区，其中每个 BUFFER 可以存放一个消息

当发送进程需要发送消息时，执行 send 系统调用，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程 copy 到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程

在以后某个时刻，当接收进程执行到 receive 接收原语时，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容 copy 到接收进程空间，之后收回缓冲区，如此就完成了消息的接收

由于消息缓冲机制中使用的缓冲区是公用缓冲区，使用消息缓冲机制传送数据时，通信进程应满足的条件：

进程对缓冲区的操作必须互斥 当缓冲区中无消息存在时，接收进程不能接受到任何消息 设置公用信号量mutex,接收进程私用信号量SM，消息m

Send (m):
Begin
向系统申请一个消息缓冲区
P(mutex)
将消息m发送到新申请的消息缓冲区
V(mutex)
V(SM)

Receive(m):
Begin
P(SM)
P(mutex)
将消息m从缓冲区复制到接收区并释放缓冲区
V(mutex)

(3) 邮箱通信

对于只有一个发送进程和一个接收进程使用的邮箱，进程间通信应满足以下条件：

• 发送进程发送消息时，邮箱中至少有一个存储消息的单元
• 接收进程接收消息时，邮箱中至少有一个消息存在

(4) 管道

Unix 系统从System V开始，提供有名管道和无名管道两种数据通信方式 无名管道为建立管道的进程及其子进程提供一条以比特流方式传送消息的通信管道。该管道在逻辑上是管道文件，物理上则由文件系统的高速缓冲区构成

管道是一条在进程间以字节流方式传送的通信通道，它由 OS 核心的缓冲区（通常几十KB）来实现，是单向的。在使用管道前要建立相应的管道，然后才可使用。

UNIX 系统中，通过 pipe 系统调用创建无名管道，得到两个文件描述符，分别用于写和读。具体调用形式为：

• int pipe(int fildes[2]);

其中，文件描述符 fildes[0]为读端，fildes[1]为写端

通信时，通过系统调用 write 和 read 进行管道的写和读

如果进程间需要双向通信，通常需要两个管道。

UNIX 无名管道只适用于父子进程之间或父进程安排的各个子进程之间（只有相关进程可以共享无名管道）；

UNIX 中的命名管道，可通过 mknod 系统调用建立（不相关进程只能共享命名管道，指定 mode 为 S_IFIFO），具体形式为：

• int mknod(const char *path, mode_t mode, dev_t dev); 例 1 利用无名管道实现父子进程通信

#include <stdio.h>
main() { 
    int x,fd[2];
    char buf[30],s[30];
     pipe(fd);
     while((x=fork()==-1);
     if(x==0) { 
        sprintf(buf, “This is an example\n”);
         write(fd[1],buf,30);
         exit(0);
     } else { 
         wait(0);
        read(fd[0],s,30);
         printf(“%s”,s);
     } 
}

(八) 死锁

(1) 基本概念

死锁的定义：当多个进程因竞争资源而造成的一种僵局，在无外力作用下，这些进程将永远不能继续向前推进，这种现象称为死锁

死锁的起因：并发进程的资源竞争、进程推进顺序不当

(2) 产生条件

• 互斥条件：资源的排他性
• 不剥夺条件：进程对获得的资源在未使用完毕前，不可被其他进程剥夺使用权利
• 部分分配条件：进程每次申请新资源时，同时还要占用已分配的资源
• 环路条件：存在进程循环链，链中每个进程已获得的资源同时被下一个进程申请

(3) 死锁的排除方法

A：死锁预防

• 一次性分配法
• 资源顺序分配法
• 先释放，后申请

B：死锁避免：

• 动态预防，系统根据某种算法在动态分配资源时，预测出死锁发生的可能性，并加以预防

C：死锁的检测与解除

• 一个给定的进程－资源图最终是可以化简的
• 剥夺资源
• 撤销进