1632 字
8 分钟
互斥、同步、信号量
2025-05-20
操作系统
C++

互斥(mutex)#

Peterson算法#

Peterson算法成功解决了两个进程互斥地去访问同一个资源。

其中flag表示两个进程访问资源的意愿以及是否占有这个资源。turn表示一种谦让的想法，但是只会谦让一次。

  1. flag[0] = true: 表示自己要去访问资源
  2. turn = 1: 表示谦让，让对方先进入
  3. while(flag[1] == true && turn == 1): 只有当对方想进去，且是对方的回合。等待。
  4. 当对方结束了flag[1]=false，或者开始进入了turn=0，都会改变flag和turn。从而结束当前的等待。
flag[2] = {false, false};
turn = 0;
// P1
flag[0] = true;
turn = 1;
while(flag[1] == true && turn == 1){
    // busy wait
}
// get into critical secion


flag[0] = false;




// P2
flag[1] = true;
turn = 0;
while(flag[1] == true && turn = 0){
    // busy wait
}
// get into critical section


flag[1] = false;

Peterson算法实现的是在软件层面的互斥，但是在现代多核计算机中，假设当进程A在while()等待进程B离开critical section以获取资源时，进程B接收到了操作系统的中断去执行了其他非常复杂的代码，此时进程A就会一直等待进程B释放资源。

因此要实现真正的互斥，必须要操作系统提供系统调用。

系统调用#

同步: 条件变量#

条件变量#

生产者消费者#

以下是一个有界缓冲区的生产者消费者模型。

消费者根据队列中是否有数据来读取。如果没有数据就等待。

生产者会不断地生产数据，如果队列已满，则停止生产。每生产一次数据就唤醒消费者。

  • 当满足wait_condition=true时，进行等待。 cv.wait(lock, []{ return !(wait_condition); });

注意：使用 !(wait_condition)，让代码逻辑更加易懂。

#include <mutex>
#include <iostream>
#include <queue>
#include <thread>
#include <condition_variable>
#include <chrono>
#include <atomic>


std::queue<int> buffer;


std::mutex mtx;
std::condition_variable consumer_cv; // 实现消费者同步
std::condition_variable producer_cv; // 防止缓冲区溢出
const unsigned int MAX_SIZE = 1000;
std::atomic<bool> done(false); // 生产者完成标志，通知消费者结束。
// consumer


// producer
void producer(){
    for(int i = 0; i < 100; i++){
        std::unique_lock<std::mutex> lk(mtx);


        // 如果队列满了，就等待
        //
        producer_cv.wait(lk, []{ return !(buffer.size >= MAX_SIZE); });
        // while(buffer.size() >= MAX_SIZE){
        //     producer_cv.wait(lk);
        // }


        std::cout << "producer push: " << i << std::endl;
        buffer.push(i);


        // 生产数据，唤醒消费者
        lk.unlock();
        consumer_cv.notify_one();


        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
    done = true;
    consumer_cv.notify_all(); // 唤醒所有消费者
    std::cout << "producer done" << std::endl;
}


void consumer(int id){
    while(true){
        std::unique_lock<std::mutex> lk(mtx);


        // 空 结束 quit
        // 空 未结束 wait
        // 有 结束 read
        // 有 未结束 read


        // 队列为空,且生产者未结束，等待
        consumer_cv.wait(lk, [] { return !(buffer.empty() && !done); });


        // while(buffer.empty() && !done){
        //     consumer_cv.wait(lk);
        // }


        // 如果队列为空且生产者完成，退出
        if(buffer.empty() && done){
            std::cout << "[" << id << "] consumer done" << std::endl;
            break;
        }


        // 如果队列不为空，消费数据
        int value = buffer.front();
        buffer.pop();
        value = id * 1000 + value;
        std::cout << "[" << id << "] consumed: " << value << std::endl;


        // 消费数据，唤醒生产者
        lk.unlock();
        producer_cv.notify_one();


        std::this_thread::sleep_for(std::chrono::milliseconds(10));
    }
}


int main() {
    std::thread prod1(producer);
    std::thread cons1(consumer, 1);
    std::thread cons2(consumer, 2);
    std::thread cons3(consumer, 3);
    std::thread cons4(consumer, 4);


    prod1.join();
    cons1.join();
    cons2.join();
    cons3.join();
    cons4.join();


    return 0;
}

同步: 信号量#

信号量#

当存在多个线程，需要访问有限数量的同类资源，信号量可以让这些线程有序的获取这些资源。当资源被消耗完后，线程需要等待其他线程返还资源。

例如：当多个车需要进入停车场时，停车位就是一个共享资源。当车进入停车场消耗一个停车位，当车离开停车场后，创造一个停车位。

以生产者消费者模式书写的代码：每个用户即是生产者，也是消费者。

void P(sem_t * sem){
    mutex_lock(&sem->lk);
    while(!(sem->count > 0)){
        cond_wait(&sem->cv, &sem->lk);
    }
    sem->count--; // 消耗一个信号量
    mutex_unlock(&sem->lk);
}


void V(sem_t *sem){
    mutex_lock(&sem->lk);
    sem->count++; // 创建一个信号量
    cond_broadcast(&sem->cv);
    mutex_unlock(&sem->lk);
}

信号量的应用#

  1. 当信号量最大为1时，就可以实现两个用户的同步。

    A -> V(sem) -> P(sem) -> B

    B想要获取资源V(sem)，需要等待A释放一次资源P(sem)

  2. 当信号量为n时，可以管理计数型的资源，给多个用户并发访问。

    由于 P V 操作是互斥的，通过判断信号量sem的值 0 or max_size 来判断事件的结束。

信号量: 优雅地实现生产者消费者#

以工厂生产车辆为例，资源为工厂中的停车车位。根据状态可以分为 空车位 和 被占的车位 两种。

sem_t empty = SEM_INIT(MAX_SIZE); // 多少个空车位
sem_t fill = SEM_INIT(0); // 占了多少个车位


// 进入一辆车（生产车）
void produce(){
    P(&empty); // 消费一个空车位
    // produce
    V(&fill); // 产生一个车（放在停车场）
}


// 离开一辆车（消费车）
void consume(){
    P(&fill); // 消费一个车（提走了）
    // consume
    V(&empty); // 产生一个空车位
}

总结：

  1. 生产者生产，就会消费空位，产生资源。

  2. 消费者消费，就会消费资源，产生空位。

或者说：将P()操作看作为等待的动作，V()操作看作唤醒的动作。

信号量 v.s. 条件变量#

信号量

  • 优雅，能够完美地解决生产者消费者问题。
  • 但是信号量sem的数值，无法表示所有的同步条件。

条件变量

  • 万能：总是可以使用。(可以写一个复杂的条件判断，不满足条件就等待)
  • 反直觉：总觉得线程会一直等待，浪费资源。

哲学家吃饭问题#

有 5位哲学家 围坐在一张圆桌旁，他们的生活模式如下循环：

思考（thinking）-> 饿了（hungry） -> 吃饭（eating）-> 思考…

桌子上放有5根筷子，每位哲学家坐在两根筷子之间。

每位哲学家需要左右两根筷子才能吃饭。

筷子是共享资源，一次只能被一个哲学家使用。

条件变量#

只要把每根筷子抽象成一个条件变量即可。

简单无脑，写好执行条件就行。

  • 执行条件： available[lhs] && available[rhs]

  • 只要两边的筷子都能获取就吃饭。

信号量#

  • 获取筷子：P(&sem[lhs]) && P(&sem[rhs])

  • 吃完饭，创建/放下筷子：V(&sem[lhs]) && V(&sem[rhs])

但是：如果5个哲学家同时举起左手的筷子，就会产生死锁。

  1. 只能最多有4个人吃饭

  2. 给筷子编号，总是先拿编号小的筷子

终极方案#

额外提供一个调度器(Scheduler)/线程，负责根据系统整体的状态信息，调度每个哲学家，告诉他们应该做什么。

互斥、同步、信号量
https://chrisnake11.github.io/blog/posts/coding/os/互斥同步信号量/
作者
Zheyv
发布于
2025-05-20
许可协议
CC BY-NC-SA 4.0
vcpkg配置redis库
协程Async_Server_Coroutine
© 2025 Zheyv. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari