操作系统之同步与死锁

并发的原理

操作系统的核心问题是关于进程和线程的管理:

  • 多道程序设计技术:管理单处理器系统中的多个进程。
  • 多处理技术:管理多处理器系统中的多个进程
  • 分布式处理技术:管理多台分布式计算机系统中多个进程的执行。

其中”多道”,”多处理器”,”多台”都是指多个程序可以同时运行(重叠执行或者交替执行)。如果多程序同时独立运行则问题可能很少,但是如果多程序之间有数据的共享,硬件资源的使用,都会出现很大的问题。所以操作系统或者程序本身要处理这些问题。

虽然CPU也是一种资源,但是多进程对CPU使用权的进程是进程调度问题。二者的区别是,一个是谁先执行的问题,一个是怎么(谁先)使用资源的问题。

并发会出现什么问题呢?
举个例子:两个进程同时使用一个变量counter,对counter同时运行counter++操作。

// counter ++ 本质操作:
counter = counter + 1;
// CPU执行时的操作: register 表示寄存器
register = counter;
register = register + 1;
counter = register;

由于CPU对进程的切换会导致执行三个执行命令的不确定就会导致一些问题: (P1表示进程1,P2表示进程2,这里使用图片)
CPU执行示例

P1和P2对counter都进行了加一操作,但是最终结果却只有一个成功了(被覆盖)。所以如果不对counter的访问进行一些控制,结果可能是4,5,6。
通过上面的例子,可得出:多线程或者进程在读写一个共享数据时,结果依赖于他们执行的相对时间,这种情形就形成了竞争

操作系统为什么要关注同步相关的问题?
因为每一个进程都有自身的数据和对硬件资源的使用,操作系统必须保护每一个进程的数据和物理资源,避免其他进程的无意干扰。例如打印机设备,如果操作系统不对其进程管理,则每一个进程都是用,那么打印出来的结果可能都不是任何程序想要看到的。

同步

进程之间的交互可分为:

  • 进程间相互不知道对方的存在:这种情况更多的发生在硬件资源的请求上,进程都想要请求一个资源,这是操作系统知道这个硬件资源的使用情况,所以需要操作系统对进程的请求做处理。
    • 潜在的控制问题:互斥、死锁(可复用的资源)、饥饿
  • 进程间接知道对方的存在:这个情况是指进程间通过访问共享的数据区或对象,进程知道存在其他的进程访问,但是不知道具体是什么进程。比如I/O缓冲区。
    • 潜在的控制问题:互斥、死锁(可复用的资源)、饥饿、数据一致性
  • 进程直接知道对方的存在:进程明确知道一起合作的进程是谁(即通过进程ID通讯)。
    • 潜在的控制问题:死锁(可消费的资源)、饥饿

进程同步概览

在计算机世界中,很多问题的解决方案或多或少都会存在一些问题,而且一些问题的解决方案会带来其他的问题。
比如:为了解决多进程间合作运行,需要同步,通信,但是解决同步和通信的方法又会带来死锁等问题。

临界区

什么是临界区呢?说白了,就是可能会被多个线程执行时会出错的代码语句集合(没有两个进程可以在他们的临界区内同时执行)。比如,上面例子的counter++,这句就要放在临界区内,防止多进程/线程对数据的读写出现问题。
临界区图示

  • 进入区:实现进入临界区时的请求许可代码段
  • 退出区:临界区结束后的释放请求许可的代码段
  • 剩余区:退出区之后的代码所属的代码段
  • 临界区:只能有一个进程执行的代码段

临界区问题的解决方案所需的要求:

  • 互斥(mutual exclusion):如果有一个进程在临界区内运行,那么其他进程不能进入执行
  • 进步(progress):如果临界区内没有进程执行,并且有进程想进入,那么只有哪些不在剩余区内执行的进程可以参加选择。
  • 有限等待(bounded waiting):如果一个进程想要进入临界区,当他发起请求到可以进入必须具有有限的时间内。

其实还存在一个问题,就是:进程在进入区执行时,那么怎么保证只有一个进程获取许可呢?这其实就需要硬件的支持才可以。

如果想在软件方面支持,可以参考Peterson解决方案,这个解决方案放在现在的CPU指令执行方式,可能并不能保证正确性。
通过软件实现对临界区的保护方式称为加锁机制。

怎么样才算互斥呢?或者说互斥的要求是什么:

  1. 必须强制是是互斥:对与相同资源或共享对象的临界区的所有进程中,一次只允许一个进程执行。
  2. 一个在非临界区停止的不能干涉其他进程
  3. 绝不允许出现需要访问临界区的进程被无限推迟的情况
  4. 如果当前临界区没有任何进程,则只要有进程想要进入,则可以立即进入
  5. 对于相关进程的执行滚速度和处理器数目没有要求
  6. 一个进程驻留在临界区中的事件必须是有限度的。

    —- 《操作系统精髓和设计原理 P144》

创建实现互斥的方法:

  1. 由并发执行的进程担负这个职责,这叫做软件方法
  2. 使用专门的机器指令
  3. 使用操作系统或程序设计语言中提供支持,比如Go的协程则是在语言级别上支持

硬件上支持同步

使用硬件支持其本质就是寻找一个原子性的指令,保证同一时刻只能有一个进程/线程成功。所以,对于单CPU环境,临界区问题只需要在修改共享变量时禁用终端就可以实现;但是对于多处理器结构,禁用中断需要消耗需要性能,而且会影响系统其他功能。所以现在对于多处理器系统,需要硬件提供硬件指令,用于检测和修改字的内容,或者原子性的交换两个字。CAS原理为这提供了一个思路:
CAS(Compare-and-Swap),即比较并替换,CAS需要三个操作数:需要读写的内存地址V、进行比较的值A,需要写入的新值B。当且仅当V的值等于A时,CAS才会通过原子的方式用新值B更新V的值,否则不会执行任何操作。

CAS的含义:认为V的值应该是A,如果是,(说明没有任何其他的进程更改过),那么就可以将V的值更新为B,否则不修改并告诉V的值实际是多少。 —- 《Java并发编程实战 P263》

硬件提供的特有指令可以抽象为两种形式:test_and_set(),compare_and_swap()

术语介绍:忙等待或者叫自旋等待指的是进程在得到临界区访问权之前,他只能继续执行测试变量的指令来得到访问权,除此之外不能做其他事情。 —- 《操作系统精髓和设计原理 P144》

test_and_set()指令进行抽象则可以表示为:


// 指令test_and_set的定义
boolean test_and_set(boolean *target){
    boolean rv = *target;
    *target = true;

    return rv;
}

// -------------------------

// 采用指令test_and_set的互斥实现
do{
    // 如果没有得到期望的false值,则一直处于执行while循环
    // 直到临界区的进程执行退出区的代码段
    while(test_and_set(&lock))
        ; /* do nothing */

    /* critical section */
    lock = false;  // quit section
    /* remainder section */
}while(true);

compare_and_swap()指令进行抽象则可以表示为:

// 指令compare_and_swap的语义解释
int compare_and_swap(int *value, int expected, int new_value){
    int temp = *value;

    // 测试原来的值是否被其他进程改变,如果没有改变,则设置新值,否则返回 
    if(*value == expected)
        *value = new_value;

    return temp;
}

// 采用指令compare_and_swap的互斥实现

do{
    // 测试期望值是否是0,即退出条件是否成立
    while(compare_and_swap(&lock, 0, 1) != 0)
        ; /* do nothing */

    /* critical section */

    lock = 0;  // 退出段

    /* remainder section */
} while(true);

以上两种虽然满足互斥要求,但是对于有限等待并没有满足。

有界等待互斥的test_and_set()实现:


// 共享数据结构,都初始化为false
boolean waiting[n]; // n是进程数
boolean lock; // 表示是否允许进入

do{
    // 将要执行的进程
    waiting[i] = true;
    key = true;
    while(waiting[i] && key){
        key = test_and_test(&lock);
    }

    // 取消自己的等待
    waiting[i] = false;

    /* critical section */

    // 这个while循环时寻找下一个可用的进程
    // 为了让每一个进程的等待时间最大为n-1次执行时间。
    j = (i + 1) % n;
    while((j != i) && !waiting[j]){
        j = (j + 1) % n;
    }

    // 退出区代码 
    if( j == i){
        // 如果没有新的进程等待,则直接退出
        lock = false;
    } else {
        // 如果找到下一个等待的进程,则直接设置其进入临界区
        waiting[j] = false;
    }

    /* remainder section */
} while(true);

硬件指令方法的特点
优点:

  • 适用于在单处理其或共享内存的多处理器上的任何数目的进程
  • 简单且易于证明
  • 支持多个临界区,每个临界区可以用自己定义的变量定义
    缺点:
  • 使用了忙等待,比较消耗cpu时间
  • 可能产生饥饿:当一个进程离开临界区后,其他进程再次进入是随意的,即有些进程会进入无线等待,上面最后一个实现可以解决。
  • 可能死锁:这种是在单处理器下,当一个进程获得临界区后,却被CPU让给更高优先级的进程,但是更高优先级的进程也想使用临界区,这样,一个要被执行但是无法执行,一个可以释放资源,但是没有机会释放资源,就会导致死锁问题。

饥饿: 指一个可运行的进程尽管能继续执行,但是被调度器无期限的忽略,而不能被调度执行的情况。
死锁: 两个或者两个以上的进程因为每一个而进程都在等待其他进程做完某些事情而不能继续执行的情况。

信号量

信号量是操作系统和用于提供并发性的程序设计语言的一种同步机制。即信号量是在操作系统和程序设计语言层面上为开发程序提供的一种同步机制。例如Go语言通过通道传递信号,控制另一个线程(协程)的执行。

除了信号量外,还有互斥量,管程,条件变量,消息传递等。

信号量最早是由荷兰的Dijkstra提出,其主要思想是:两个或者多个进程可以通过简单的信号进行合作,一个进程可以被迫在某一位置停止,直到它接受到一个特定的信号。
通常可把信号量看作一个具有整型数值的变量,在它之上定义三个操作:

  • 一个信号量可以被初始化成非负数
  • 操作wait()最初称为P(荷兰语proberen,测试), 其使信号量减一,如果信号量值变成负数,则执行wait()的进程被阻塞。
  • 操作signal()最初被称为V(荷兰语verhogen,增加),其使信号量加一,如果值小于或者等于零,则被wait()操作阻塞的进程被解除阻塞。

    wait()和signal()操作应该为一个原子操作。

对于信号量的解释:
开始时,信号量的值为0或者整数。如果该值为正数,则它的值等于发出wait()操作后可立即继续执行的进程数量。如果该值为0(或者由于初始化,或者由于有等待信号量初值的进程已经等待),则发出wait()操作的下一个进程会被阻塞,此时该信号量的值变成负数。之后,每一个后续的wait()操作都会使信号量的负值更大(即负数方向数值增大)。该数值等于正在等待解除阻塞的进程的数量。在信号量为负值的情形下,每一个signal()操作都会将等待进程中的一个进程解除阻塞。

— 《操作系统精髓与设计原理》

信号量的原语定义:

struct semaphore{
    int count; // 可用资源数
    queueType queue; // 等待资源进程的队列,直到有资源可用在从里面移除。
};

void wait(semaphore s){
    // 这里只是wait原语的抽象表示,所以整个函数都是原子性,即可认为`s.count --`操作也是不可分割的。
    s.count --; 
    if (s.count < 0){
        /* 把当前进程插入到队列中 */
        /* 阻塞当前进程 */
    }
}

void signal(semaphore s){
    s.count++;
    if (s.count <= 0){
        /* 把进程从队列中删除 */
        /* 把进程插入到就绪队列中 */
    }
}

二元信号量

如果信号量的值只能是0和1,则称这样的信号量为二元信号量。除了二元信号量外的信号量称为计数信号量或者一般信号量

由于二元信号量的取值只能是0和1,则可以使用的操作定义:

  • 一个二元信号量可以初始化成0或1;
  • wait()操作检查信号的值,如果为0,则进程执行wait()就会被阻塞。如果值位1,则将值改为0,继续执行该进程;
  • signal()操作检查是否有任何进程在该信号上受阻,如果有,那么通过signal()操作,受阻的金册灰姑娘就会被唤醒;如果没有进程受阻,那么值被设为1;

通过上面的定义,我们可以定义二元信号量原语:

struct binary_semaphore{
    enum {zero, one} value;
    queueType queue;
}

void wait(semaphore s){
    if(s.value == one){
        s.value = zero;
    } else {
        /* 把当前进程插入到队列中 */
        /* 阻塞当前进程 */
    }
}

void signal(semaphore s){
    if(s.queue is empty()){
        // 没有进程请求资源
        s.value = one;
    }else {
        /* 把进程从队列中删除 */
        /* 把进程插入到就绪队列中 */
    }
}

还有一个点,就是信号量的阻塞队列的问题:进程按照什么顺序从队列中移除?
最公平的最简单的方式就是先进先出(FIFO),我们把使用这个策略的信号量称为强信号量;如果没有规定进程从队列中移除顺序,则称为弱信号量,这种弱信号可能会产生饥饿,而强信号量则不会。

信号量的使用–互斥

这是使用上面的wait()和signal()原语保持进程的互斥,这种可以设置允许多个进程同时访问(当存在多个资源时),对于资源已经没有的情况下,则wait()的进程被阻塞,直到signal()的唤醒。

const int n = 12; // 进程数
semaphore s = {
    .count= 1,   // 定义的资源个数
    .queue= newQueue() // 阻塞队列
    };

void P(int i) {

    while(true){
        wait(s);
        // 临界区
        signal(s);
        // 剩余区
    }
}

void main(){
    parbegin(P(1), P(2), .... , P(n));
}

信号量的使用–生产者/消费者问题

并发中最常见的一个问题就是生产者/消费者问题:有一个或者多个生产者生产某种类型的数据,并放置在缓冲区中;有一个消费者从缓冲区中取数据,每次取一项。
这个问题的本质就是对缓冲区的控制:

  • 缓冲区为空时,消费者不能从中移走数据
  • 缓冲区满时,生产者不能继续向其中添加数据

对于缓冲区可分为两种方式:

  • 使用二元信号量或计数信号量控制的无线缓冲区
  • 使用计数信号量控制的有限缓冲区

使用二元信号量解决无限缓冲区的生产者/消费者问题:

int n;
binary_semaphore s= 1, delay = 0;

void producer(){
    while(true){
        produce(); // 生产一个数据
        wait(s);   // 防止其他进程
        append();  // 临界区,设置数据
        n++ ;
        if(n == 1) signal(delay);  // 当n为0时,消费者被阻塞,这里是判断消费者是否被阻塞。如果阻塞则唤醒消费者
        signal(s); // 退出临界区 
    }
}

void consumer(){
    int m; // 局部变量
    wait(delay); // 判断是否有数据可以被处理
    while(true){
        wait(s); // 设置临界区
        take();  // 取出数据
        n -- ; 
        m = n;  // 防止生产者改变
        signal(s); // 这里退出了临界区,如果不设置m=n的话,那么下面使用的n可能就会被生产者改变
        consume(); // 消费数据
        if(m == 0) signal(delay); // 如果发现数据已经没有的话,则进入阻塞 
    }
}

void main(){
    n = 0;
    parbegin(producer, consumer);
}

使用计数信号量解决无限缓冲区的生产者/消费者问题:

semaphore n = 0, s = 1;
void producer(){
    while(true){
        produce();
        wait(s);
        append();
        signal(s);
        signal(n); // 记录生产的数据个数 
    }
}

void consumer(){
    while(true){
        wait(n); // 判断是否有数据可以被消费,如果可以被消费,则计数减一,否则阻塞等待
        wait(s);
        take();
        signal(s);
        consume();
    }
}

void main(){
    parbegin(producer, consumer);
}

使用计数信号量解决有限缓冲区的生产者/消费者问题:

const int sizeOfBuffer = 10; // 缓冲区大小
semaphore s = 1, n = 0, e = sizeOfBuffer;

void producer(){
    while (true){
        produce();
        wait(e); // 增加缓冲区使用的个数
        wait(s); // 临界区
        append();
        signal(s); // 结束临界区
        signal(n); // 设置生产的数据个数
    }
}

void producer(){
    while (true){
        wait(n); // 消费一个数据,如果为0,则阻塞
        wait(s); // 临界区
        take();
        signal(s);
        signal(e); // 减少缓冲区使用的个数
        consume();
    }
}

void main(){
    parbegin(producer, consumer);
}

信号量的使用–信号量的实现

信号量的本质就是互斥:任何时候只能有一个进程可以操作waitsignal,而waitsignal的操作实现不许保证是原子原语实现,即类似于一条指令,一旦调用,必须执行完成,不能执行期间中断。
对于这,最简单的方案就是使用硬件或固件实现。如果使用软件实现,则可以考虑Dekker算法或者Peterson算法;

使用硬件支持的方式有:CAS类指令或者中断禁用的方式。

CAS指令代码举例:

wait(s){

    while(compare_and_swap(s.flag, 0, 1) == 1){
        ; // 不做任何事情 
    }

    s.count --;  // 减少信号量

    if(s.count < 0){
        /* 进程进入s.queue队列 */
        /* 阻塞该进程 */
    }
    s.flag = 0;
}

signal(s){

    while(compare_and_swap(s.flag, 0, 1) == 1){
        ; /* 不做任何事情  */
    }
    s.count ++; // 增加信号量,即释放资源
    if(s.count <= 0){
        /* 从s.queue队列中移除进程 */
        /* 进程进入就绪队列 */
    }
    s.flag = 0;
}

中断方式类似上面:

wait(s){

    // 禁用中断

    s.count --;  // 减少信号量

    if(s.count < 0){
        /* 进程进入s.queue队列 */
        /* 阻塞该进程 */
    } else{
        // 允许中断
    }
}

signal(s){

    // 禁用中断

    s.count ++; // 增加信号量,即释放资源
    if(s.count <= 0){
        /* 从s.queue队列中移除进程 */
        /* 进程进入就绪队列 */
    }

    // 允许中断
}

管程

什么是管程?我的理解就是防止开发人员错误使用信号量等方式而导致程序出现问题的一种手段。比如,信号量的wait和signal的调用,如果存在一个程序只调用wait但是不调用signal则程序就会出现问题。
为了防止上面的情况发生就产生了管程:资源的请求和释放,以及进程的阻塞都有管程处理,开发人员只需要在管程内写临界区代码就可以了。

管程示意图
管程是由一个或多个进程、初始化序列和局部数据组成的软件模块,主要特点:

  • 局部变量只能被管程的过程访问,任何外部过程够不可以访问
  • 一个进程通过管程的一个过程进入管程
  • 在任何时候,只能一个进程在管程中执行,调用管程的任何其他进程都被阻塞,以等待管程可用。

    管程类型属于ADT类型,提供一组由程序员定义的,在管程内互斥的操作。 — 《操纵系统概念 P189》

一个很好的管程例子就是Java的同步:synchronized修饰的同步块。

public class Example{
    public void test(){
        synchronized(this){
            System.out.println("Hello");
        }
    }
}

反编译Example

同步的一些问题

这里介绍一些常见的同步问题:缓冲区相关的生产者消费者问题,读者/写者问题和哲学家问题。

生产者-消费者问题

关于使用信号量处理的这类问题可以看上面关于信号量的介绍,这里说一下关于使用管程。

管程类型中定义初始化块,函数。

管程定义:

monitor boundedbuffer;
char buffer [N];     // 分配N个数据项空间
int nextin, nextout; // 缓冲区指针
int count;           // 缓冲区中的数据项个数
cond notfull, notempty; // 为同步设置的条件变量,条件成立才可进入到管程中

void append(char x){
    if(count == N) wait(notfull); // 缓冲区满,阻塞等待消费
    buffer[nextin] = x;
    nextin = (nextin + 1) % N;
    count ++;
    signal(notempty);   // 释放任何一个等待消费的进程
}

void take(char x){
    if (count == 0) wait(notempty);  // 缓冲区空,阻塞等待
    x = buffer[nextout];
    nextout = (nextout + 1) % N;
    count --;
    signal(notfull);  // 释放任何一个等待添加数据的进程
}
{
    // 缓冲区初始化为空
    nextin = 0;
    nextout = 0;
    count = 0;
}

管程的使用:

void producer(){
    char x;
    while(true){
        produce(x);
        append(x);
    }
}
void consumer(){
    char x;
    while(true){
        take(x);
        consumer(x);
    }
}
void main(){
    parbegin(producer, consumer);
}

读者-写者问题

生产者-消费者问题是两者的操作都会对数据产生影响,而读者-写者问题中,读者不会对共享数据产生影响,只有写操作会产生影响的同步模型。
读者-写者问题定义:有一个多进程共享的数据区,这个数据区可以是一个文件或者一块内存空间,或者是一组寄存器。对于这个数据区,可以允许多个进程同时读取里面的数据,但是只能同步操作数据。
即成立的条件:

  • 任意多的读进程可同时读共享数据区
  • 一次只有一个写进程可以写共享数据区
  • 如果一个写进程正在写文件,禁止任何读进程读文件

从上可以分出来两个问题:当读写进程同时到来时,实现读取数据,还是先写数据。

  1. 读者优先

这种情况是当有读写进程时,写进程先等待所有的读进程就绪后再操作。这种其实可能会导致写进程进入饥饿状态。
使用信号量的实现方式:

int readcount;
semaphore x = 1, wsem = 1; // wsem 信号量是否有写进程已经在访问共享数据区

void readder(){
    while(true){
        wait(x); // 临界区
        readcount ++; // 增加一个读进程
        if(readcount == 1) 
            wait(wsem); // 如果有进程正在写,则等待,否则设置不允许进程写
        signal(x);

        READUNIT();  // 读取资源

        wait(x); // 临界区
        readcount -- ; // 表示一个读进程结束
        if(readcount == 0) 
            signal(wsem); // 如果没有进程读,则唤醒释放写信号,可以让写进程获取资源
        signal(x);    
    }
}

void writer(){
    while(true){
        wait(wsem); // 开始写时,请求资源,如果没有进程在读,则可以直接进入写,则否阻塞
        WRITEUNIT();
        signal(wsem);
    }
}

void main(){
    readcount = 0;
    parbegin(reader, writer);
}
  1. 写者优先

写着优先保证了当一个进程写时,其他读进程都必须阻塞,等待写操作完成后才可以再读取。
使用信号量的实现方式:

int readcount, writecount;
semaphore x = 1, y = 1, z = 1, 
        wsem = 1,  // 写信号,当其他进程在读些时,阻塞等待 
        rsem = 1;  // 读信号,用于当写操作时,阻塞读进程

void reader(){
    while(true){
        wait(z); // 临界区
            wait(rsem);  // 当写进程正在执行时,读进程不能读取,在这里阻塞
                wait(x); // 临界区
                    readcount++;  // 添加一个读进程
                    if(readcount == 1);  
                        wait(wsem); // 如果存在读进程开始读取时,设置写进程不能执行
                signal(x);
            signal(rsem); // 释放共享区的资源,可以让写进程进入执行
        signal(z);

        READUNIT();

        wait(x); // 临界区
            readcount--;
            if(readcount == 0)
                signal(wsem);   // 当没有读进程后,释放请求,可以让写进程执行
        signal(x);
    }
}

void writer(){
    while(true){
        wait(y); // 临界区
            writecount++;  // 增加一个写进程
            if(readcount == 1)
                wait(rsem); // 如果存在进程在读,则等待,否则则阻塞所有读进程执行
        signal(y);

        wait(wsem); // 阻塞其他写进程执行
        WRITEUNIT();
        signal(wsem);

        wait(y); // 临界区
            writecount --; // 减少写进程
            if(writecount == 0)
                signal(rsem); // 如果没有写进程,则释放资源,让资源给读进程
        signal(y);
    }
}

void main(){
    readcount = writecount = 0;
    parbegin(reader, writer);
}

上面的信号情况可为:
| 系统中的进程状态 | 信号情况 |
|:–|:–|
|系统中只有读进程 | 设置wsem、没有队列 |
|系统中只有写进程 | 设置wsem和rsem、写进程在wsem上排队 |
|既有读进程,又有写进程,但读者优先 | 由读进程设置wsem、有写进程设置rsem、所有写进程在wsem上排队、一个读进程在rsem上排队、其他读进程在z上排队 |
|既有读进程,又有写进程,但写者优先 | 由写进程设置wsem、由写进程设置rsem、写进程在wsem上排队、一个读进程在rsem上排队、其他读进程在z上排队 |

对于读者-写者问题也可以使用消息传递的方式解决。

哲学家就餐问题

哲学家就餐问题针对的是多进程之间分配多个资源,并且不会出现死锁和饥饿的同步模型。
具体描述:5个哲学家,他们的生活只有思考和吃饭。他们共用一个圆桌,每一位都有一把椅子。在桌子中央有一碗米饭,在桌子上有5根筷子。当一位哲学家思考时,他与其他同时不交流。当他感觉饥饿时,拿起与他相近的两根筷子(筷子在他左边和右边)。一个哲学家只能一次拿起一个筷子,而且不能从别人手里拿筷子。当一个饥饿的哲学家同时拥有两根筷子时就可以吃,吃完后,放下筷子并开始思考。

哲学家问题图示

图来源于:由Benjamin D. Esham / Wikimedia Commons,CC BY-SA 3.0,https://commons.wikimedia.org/w/index.php?curid=56559

一个简单的解决方法就是每一个筷子使用一个信号量,当一个哲学家左右两边的筷子(信号)都是可用时,则它就可以吃饭了。

semaphore chopstick[5] = {1, 1, 1, 1, 1};

void eat(int i){
    do{
        // 思考
        wait(chopstick[i]);
        wait(chopstick[(i + 1) % 5]);
        // 吃饭
        signal(chopstick[i]);
        signal(chopstick[(i + 1) % 5]);
        // 思考
    }while(true);
}

其实这种方案还是存在一些问题:

  1. 相邻的两个人不能吃饭
  2. 有可能导致死锁:当五个人都拿起筷子,则每一个都等待别人释放另一个筷子,这就造成了死锁。

那么怎么处理死锁呢?造成死锁的必须条件又是什么?



死锁

操作系统引入了多进程或多线程运行,导致资源的不能合理使用,有引入了同步手段使多进程或多线程之间合作,控制对资源的访问。但是使用同步中,我们也发现了会产生两个问题:死锁饥饿

  1. 死锁:一组相互竞争系统资源或进程通信的进程间的“永久”阻塞。
  2. 饥饿:指一个可运行的进程始终得不到CPU资源,导致无法运行。

死锁的原理

当一组进程内的每一个进程偶的在等待一个事件,而这个事件只能由这组进程中的另一个进程引起,那么这组进程就处于死锁状态。

在正常情况下,一个进程使用资源的步骤:

  1. 向操作系统申请,如果资源被其他进程占用,则申请的进程一直处于等待,直到获得该资源
  2. 使用资源
  3. 释放资源

    资源通常可以分为:

    • 可重用资源:指一次只能提供一个进程使用,并且不会由于使用而耗尽的资源
    • 可消耗资源:指可以被创建(生产)和销毁(消耗)的资源

但是当有进程申请的资源一直得不到则就进入了死锁。
例如:一个系统有一台打印机和一个DVD驱动器,假如进程A占用DVD驱动器而进程B占用打印机。如果进程A申请打印机而进程B申请DVD驱动器,那么这就产生了死锁。

死锁产生需要什么条件呢?通过之前的例子,可得出:

  • 互斥:一次只能一个进程使用,其他进程只能等待该进程使用完成才可以在使用。
  • 占有且等待:一个进程占有一个资源,并且等待另一个资源,而该资源被其他进程占有。
  • 不可抢占:资源不能被强制让出,只能由拥有该资源的进程主动释放。
  • 循环等待:存在一个封闭的进程链,这个链中的每一个进程至少占有此链中下一个进程所需的一个资源。

    第四个条件循环等待其实暗含了在了占有并等待中,换句话说,其实前三个条件就直接导致了第四个条件的成立,即第四个条件不可解。

上面的四个条件是造成死锁的充分必要条件。

怎么描述死锁呢?通常都是通过一个称为系统资源分配图有向图表示。
系统资源分配图
发生死锁
不发生死锁

现在我们已经知道死锁是怎么产生的?那么我们怎么处理死锁呢?其实我们可以考虑一下怎么处理失火:从条件出发,切断条件之一就可以做到。在这里也是,我们只要把四个条件中的某一个条件不成立就可以了。

操作系统对死锁的处理方法:

  • 通过协议来预防或者避免死锁,确保系统不会进入死锁状态
  • 可以允许系统进入死锁,然后检测它,并加以恢复。
  • 可以忽略这个问题,认为死锁不会在系统内发生(大多数操作系统采用,包括Linux和Windows),所以需要用户程序开发人员处理

死锁预防

死锁预防:确保死锁的条件中至少有一个必必要条件不成立

  • 互斥条件:对于互斥条件,这个条件是必须成立的,如果需要对资源互斥访问,则操作系统必须支持互斥。
  • 持有且等待:如果这个条件不成立,则可以要求进程一次请求所需要的所有资源,并且阻塞这个进程知道所有请求都完成。但是这样是低效,而且有些进程并不知道自己所需的所有资源。
  • 不可抢占:
    • 如果一个进程请求另一个资源时被拒绝,则该进程释放之前请求到的资源,之后再次重新请求资源。
    • 如果一个进程请求的资源被另一个进程使用,操作系统可以抢占另一个进程的资源,即使另一个进程被抢占。这种方案对优先级的进程更好。
  • 循环等待:通过定义资源类型的线性访问顺序来预防。如果一个进程已经分配了R类型的资源,那么它接下来请求的资源只能使排在R类型之后的资源类型。我的理解是:死锁发生时,所有进程请求的资源是一个固定集合,每一个进程都想要两种或者更多资源,所以只要这个集合有序,并且使用时也不许一个进程先使用后面的资源,再使用前面的资源,这样就保证了这些进程会在请求一个资源的时候被阻塞,另一个可以运行,所以死锁也就不成立了。

死锁避免

死锁避免:操作系统事先得到有关进程申请资源和使用资源的额外信息。即约束资源请求,防止必要条件中的至少一个发生。死锁避免和死锁预防的区别是,死锁预防是通过死锁的必须条件至少一个不成立,而死锁避免是允许死锁的条件成立,但是需要一些方法对进程的资源请求做控制,使其不能达到死锁。

死锁避免的方法:

  • 如果一个进程的请求会导致死锁,则不启动此进程
  • 如果一个进程增加的资源请求会导致死锁,则不允许分配。

安全状态

安全状态,是指系统能按某种进程推进顺序( P1, P2, …, Pn),为每个进程Pi分配其所需资源,直至满足每个进程对资源的最大需求,使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列,则称系统处于不安全状态

例子:假设系统中有三个进程P1、P2和P3,共有12 台磁带机。进程P1总共需要10台磁带机,P2和P3 分别需要4台和9台。假设在T0时刻,进程P1、P2 和P3已分别获得5合、2台和2台,尚有3台未分配,见下表

进程 最大需求 当前需求 还需 可用
P1 10 5 5 3
P2 4 2 2
P3 9 2 7

解题:

  1. 刚开始时,系统给三个进程分配完当前需求,则还剩3个资源可用。
  2. 寻找是否存在一个安全序列,即这三个进程先后执行,资源需求可以满足。
  3. 三个进程排序则可组成:
    1. P1, P2, P3: P1需要执行则需要5个资源,不足
    2. P1, P3, P2: P1需要执行则需要5个资源,不足
    3. P2, P1, P3: P2需要2个,小于3,则可以;之后P2使用完成后释放资源,则还剩5个满足P1执行,P1执行完成释放资源,P3执行,满足安全序列。
    4. P2, P3, P1: P2需要2个,小于3,则可以,之后P2释放资源,还剩5个不满足P3执行
    5. P3, P1, P2: 所剩资源不满足P3执行
    6. P3, P2, P3: 所剩资源不满足P3执行
  4. 安全序列为P2, P1, P3。则只要操作系统按照这个安全序列执行就可以正常执行。

银行家算法(资源分配拒绝策略)

对于每种资源类型有多个实例的资源分配系统,现在更多的是使用一种基于安全状态银行家算法

当一个新的进程进入系统时,其应声明可能需要的每一种资源实力的最大数量,这个值不能超过系统资源的总和。
当用户申请一组资源时,系统应确定这些资源的分配是否会使系统处于安全状态。如果会则分配资源,否则,进程应该等待直到其他进程释放足够多的资源为止。

如果要实现银行家算法则需要保存系统资源和进程的一些数据:(n为系统进程的数量,m为资源类型的种类)

  • Available:长度为m的向量,表示每一种资源的可用实例数量
  • Max:$n * m$矩阵,定义每一个进程的最大需求。
  • Allocation:$n * m$矩阵,定义每一个进程现在已经分配的每种资源类型的实例数量。
  • Need:$n * m$矩阵,表示每一个进程还需要的剩余资源。

算法描述:

  1. 令Work和Finish分别表示长度m和n的向量。对于$i= 0,1, …, n -1,$初始化$Work = Available$和$Finish[i] = false$;
  2. 查找这样的$i$使其满足:
    1. $$Finish[i] == false$$
    2. $$Need_i \leq Work$$
      如果没有找到这样的$i$存在,则转到第4步
  3. $$Work = Work + Allocation_i$$
    $$Finish[i] = true $$
    返回到第2步。
  4. 如果对所有i,有Finish[i] = true, 那么系统处于安全状态。

代码实现:略(^_^)。

死锁检测

如果一个系统不采用上面两种方式避免死锁,那么死锁可能出现,这种环境下,系统可以提供:

  • 一个用来检测系统环境状态从而确定是否出现死锁的算法。
  • 一个用来从死锁状态种恢复的算法。
  1. 当每种资源只有单个实例的时候
    在这种情况下,可以通过资源分配图转化出等待图。然后判断是否有环,如果存在,则说明发生死锁;反之则说明不存在死锁。
  2. 当每种资源可有多个实例的时候
    对于这,所使用的算法类似于银行家算法:
    • Available:长度为m的向量,表示每一种资源的可用实例数量
    • Allocation:$n * m$矩阵,定义每一个进程现在已经分配的每种资源类型的实例数量。
    • Request:$n * m$矩阵,表示当前每个进程的每种资源的当前请求。
      算法描述
    1. 令Work和Finish分别表示长度m和n的向量。初始化$Work=Available$。对于$i= 0,1, …, n -1$,如果$Allocation_i$不为0,则$Finish[i] = false$,否则$Finish[i] = true$;
    2. 查找这样的$i$使其满足:
      1. $$Finish[i] == false$$
      2. $$Request_i \leq Work$$
        如果没有找到这样的$i$存在,则转到第4步
    3. $$Work = Work + Allocation_i$$
      $$Finish[i] = true$$
      返回到第2步。
    4. 如果对某个i(0 <= i < n),有Finish[i] = false, 那么系统死锁。而且,如果 $Finish[i] == false$,则进程$P_i$死锁。

死锁恢复

一旦检测到死锁,常见的恢复策略有(按复杂递增):

  1. 取消所有死锁的进程
  2. 把每个死锁进程回滚到前面定义的某个检查点,并且重启所有进程
  3. 连续取消死锁进程直到不在存在死锁
  4. 连续抢占资源直到不在发生死锁

   转载规则


《操作系统之同步与死锁》 吴欢庆 采用 知识共享署名 4.0 国际许可协议 进行许可。
  目录