经典进程同步问题

    操作系统   操作系统 集成

一些比较经典的, 书上的进程同步问题。
总结的解题思路:

  1. 画图理解题目
  2. 判断题目类型
  3. 分析进程数目, 填写进程模板
  4. 补充基本代码
  5. 补充 PV 代码
  6. 检查调整代码

不同线程之间的同步问题

由于不同线程之间存在异步性, 两个线程的语句执行先后顺序无法确定. 使用信号量机制来实现不同线程之间的同步问题

以此为延申, 如何实现拓扑排序

注意在线程同步中信号量初值为 0, 但是在线程互斥中信号量初值为 1

生产者-消费者问题

分析

共享变量为缓存池里面的产品数 缓冲区满, 生产者必须等待. 缓冲区空, 消费者必须等待 因为缓冲区的数量是临界资源, 只使用一个互斥变量来实现线程互斥如何?

semaphore n = 5;
semaphore mutex=1;
producer (){
    do{
        wait(mutex);
        signal(n);
        // produce
        signal(mutex);
    }while(true);
}

consumer(){
    do{
        wait(mutex);
        wait(n);
        // consume
        signal(mutex);
    }while(true);
}

这个代码存在很严重的问题. 假设只有一个 consumer 进程先启动, 他顺利执行到 consume 操作. 但是此时的缓冲区中还没有商品. 我们对此进行分析一下.

  • 如果缓冲区满，生产者是不能生产的，所以生产者进程受到消费者进程的制约；
  • 如果缓冲区空，消费者是不能消费的，所以消费者进程受到生产者进程的制约。

所以 P/C 问题不仅仅是线程互斥, 还包含了线程同步, 线程同步仅仅使用一个信号量是不够的. 因此我们需要额外设置两个信号量来实现线程的同步问题. 生产者在乎的是剩余空间 empty. 消费者在乎的是占用空间 full. 生产者在生产商品之前应该 P(empty) , 消费者在消费商品之前应该 P(full).

 

semaphore mutex = 1;
semaphore empty = n;
semaphore full = 0;

producer(){
    do{
        wait(empty);  // P消耗一个空闲缓冲区
        wait(mutex);
        // produce
        signal(mutex);
        signal(full);  // V增加一个产品
    }while(true);
}

consumer(){
    do{
        wait(full);  // P消耗一个产品, 非缓冲区
        wait(mutex);
        // consume
        signal(mutex);
        signal(empty); // V增加一个空闲缓冲区
    }while(true);
}

是否可以交换 producer 或者 consumer 中的两个 P 操作呢? 我们交换 producer 里面的两个 P 操作

// producer
wait(mutex);
wait(empty);  // P消耗一个空闲缓冲区

假设此时缓冲区为满, empty = 0, full=n; producer 执行 P(mutex), mutex 变为 0, 执行 P(empty), 这个时候会被阻塞. 现在切换回 consumer 进程, 执行 wait(full) 没有问题, 执行 wait(mutex) 会被阻塞. 这样就会出现线程死锁. 因此实现互斥的 P 操作要在实现 同步的 P 操作之后执行 但是 V 操作的执行顺序不会导致线程.

套路

  1. 分析题目题型: 容器大小固定, 为 P/C 问题
  2. 分析进程数量: 不同个体对应不同的进程
  3. 分析每个进程关心的: 消费者只关心 占用空间, 生产者只关心 剩余空间
  4. 填写进程基本操作
  5. 补充 PV 代码

哲学家进餐问题

2019 王道考研 操作系统 哔哩哔哩 (゜-゜)つロ 干杯~-bilibili

分析

临界资源: 筷子 对哲学家进行编号, 第 i 位哲学家的活动可以描述为

semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
Pi(){
    do{
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]); // 对左右筷子互斥访问
        ////
        //eat
        ////
        signal(chopstick[i]);
        signal(chopstick[(i+1)%5]); // 释放
        ////
        //think
        ////
    }while(true);
}

但是这样会导致一个问题, 哲学家们可能会同时拿起左边的筷子, 在去拿右边的筷子时会发生阻塞 解决方案

  1. 最多允许四个哲学家同时拿左边的筷子
  2. 只有当哲学家左右两边的筷子均可以使用时才允许拿筷子
  3. 奇数哲学家先拿左边, 再拿右边的筷子. 偶数哲学家相反

方案 1

semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
semaphore r=4; // 只允许4个哲学家进餐
Pi(){
    do{
        wait(r);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]);
        //eat
        signal(chopstick[(i+1)%5]);
        signal(chopstick[i]);
        signal(r);
    }while(true);
}

获得信号量 r 的哲学家最多只有 4 个 最少有一个哲学家可以 eat, 使用完之后释放两只筷子, 不会出现死锁和饿死

方案 2

semaphore chopstick[5]={1,1,1,1,1}; // 筷子的信号量
semaphore mutex=1; // 互斥访问变量

Pi(){
    do{
        wait(mutex);
        wait(chopstick[i]);
        wait(chopstick[(i+1)%5]); //*
        signal(mutex);
        // eat
        signal(chopstick);
        signal(chopstick[(i+1)%5]);
        // think
    }while(true);
}

使用一个互斥变量实现线程同步, 但是, 这其实也不是一个完美的方案 假如一个哲学家 x 拿起了左右两边的筷子, 他右边的哲学家 y 拿起了他左边的筷子, 想去拿右边的筷子时会发生阻塞, 阻塞在 * 位置. 这个情况下只能等 x 放下了 x 左边的筷子, y 才能继续进行. 不过比较好的是, 这个方案并不会产生死锁的问题

方案 3

semaphore chopstick[5]={1,1,1,1,1};
Pi(){
    while(1){
        if(i%2！=0){//奇数号哲学家
            wait(chopstick[i]);//拿左边的
            wait(chopstick[(i+1)%5]);//右边的
        }else{//偶数号哲学家
            wait(chopstick[(i+1)%5]);//右边的
            wait(chopstick[i]);//左边的
        }
        // eat
        signal(chopstick[i]);//释放筷子资源
        signal(chopstick[(i+1)%5]);
    }
}

读者-写者问题

要求:

  1. 可以多个读者同时读
  2. 但是不允许多个写者同时写, 只允许一个写者写
  3. 不允许在写的时候读, 也不能有新的写者来写
  4. 写者执行写之前, 不应该有读者或写者在操作

共享数据是文件

分析

两类进程: 读, 写者进程 互斥关系: 1. 读进程-写进程 2. 写进程-写进程

写进程与其他进程都互斥. 首先, 写进程与写进程之间 需要一个信号量 rw, 在写者操作共享文件前后加上 PV 操作 其次, 读进程与写进程也互斥, 因此也需要 PV 操作. 但是如果一个读者在读取共享文件之前进行了 P(rw) 操作, 会导致其他读者无法读取. 怎么解决?

使用一个 count 变量来解决, 记录当前有多少读进程.
假设刚开始 count = 0 , 进行 P(rw) 保证不会有写进程参与进来, 之后 count++, 说明现在有一个读进程. 此时有另外一个读进程参与进来, 由于 count!=0, 那么他就不会进行 P(rw) 操作, 而是直接 count++. 这样我们就解决了读者进程之间的非互斥执行问题

semaphore rw=1; // 对文件的互斥访问
int count = 0; // 记录当前读进程数

reader(){
    do{
        if(count==0) // 如果当前没有读者
            wait(rw);
        count++;
        // read file
        count--;
        if(count==0) // 如果当前没有读者
            signal(rw);
    }while(true);
}

writer(){
    do{
        wait(rw);
        // write file
        signal(rw);
    }while(true);
}

还存在一个问题 , count 变量是共享变量, 设想这样一种情况, count=0 时, 读者 1 if 判断执行, 刚要执行 P(rw) 时, count 现在还是 0, 与此同时另外一位读者也通过了 if 判断. 那么, 在读者一获得了 rw 权限之后, 读者 2 就会被阻塞. 还需要一个互斥变量来保证一气呵成地操作 count 变量

semaphore rw=1; // 对文件的互斥访问
int count = 0; // 记录当前读进程数
semaphore mutex = 1; // 对count 变量的互斥访问
reader(){
    do{
        wait(mutex);
        if(count==0) // 如果当前没有读者
            wait(rw);
        count++;
        signal(mutex);

        // read file

        wait(mutex);
        count--;
        if(count==0) // 如果当前没有读者
            signal(rw);
        signal(mutex);

    }while(true);
}

writer(){
    do{
        wait(rw);
        // write file
        signal(rw);
    }while(true);
}

套路

写者关心文件是否被占用. 读者团:

  • 第一个读者关心文件是否被占有, 未被占有就占用.
  • 中间读者只增加读者团人数.
  • 最后一个读者释放文件.

设置一个信号量表示资源是否被占有, 使用另外一个信号量表示读者团中读者的数量.
特征: 资源占用, 团体性