操作系统:经典进程同步问题 之 生产者-消费者问题、读者-写者问题、哲学家进餐问题

操作系统:经典进程同步问题 之 生产者-消费者问题、读者-写者问题、哲学家进餐问题

 

在进程同步中,经典的同步问题有:生产者-消费者问题、读者-写者问题、哲学家进餐问题。

一、生产者与消费者问题:

问题描述:使用一个缓冲区来保存物品,只有缓冲区没有满,生产者才可以放入物品;只有缓冲区不为空,消费者才可以拿走物品。

1、使用信号量实现生产者-消费者问题:

down : 如果信号量大于 0 ,执行 -1 操作;如果信号量等于 0,进程睡眠,等待信号量大于 0;

up :对信号量执行 +1 操作,唤醒睡眠的进程让其完成 down 操作。

因为缓冲区属于临界资源,因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为,需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计,这里需要使用两个信号量:empty 记录空缓冲区的数量,full 记录满缓冲区的数量。其中,empty 信号量是在生产者进程中使用,当 empty 不为 0 时,生产者才可以放入物品;full 信号量是在消费者进程中使用,当 full 信号量不为 0 时,消费者才可以取走物品。

注意,不能先对缓冲区进行加锁,再测试信号量。也就是说,不能先执行 down(mutex) 再执行 down(empty)。如果这么做了,那么可能会出现这种情况:生产者对缓冲区加锁后,执行 down(empty) 操作,发现 empty = 0,此时生产者睡眠。消费者不能进入临界区,因为生产者对缓冲区加锁了,消费者就无法执行 up(empty) 操作,empty 永远都为 0,导致生产者永远等待下,不会释放锁,消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

2、使用管程实现生产者-消费者问题:

 // 管程
 monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count – 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

 

二、读者-写者问题:

允许多个进程同时对数据进行读操作,但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量,一个互斥量 count_mutex 用于对 count 加锁,一个互斥量 data_mutex 用于对读写的数据加锁。

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁,防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

 

三、哲学家进餐问题:

五个哲学家围着一张圆桌,每个哲学家面前放着食物。哲学家的生活有两种交替活动:吃饭以及思考。当一个哲学家吃饭时,需要先拿起自己左右两边的两根筷子,并且一次只能拿起一根筷子。

操作系统:经典进程同步问题 之 生产者-消费者问题、读者-写者问题、哲学家进餐问题

下面是一种错误的解法,考虑到如果所有哲学家同时拿起左手边的筷子,那么就无法拿起右手边的筷子,造成死锁。

#define N 5

void philosopher(int i) {
    while(TRUE) {
        think();
        take(i);       // 拿起左边的筷子
        take((i+1)%N); // 拿起右边的筷子
        eat();
        put(i);
        put((i+1)%N);
    }
}

为了防止死锁的发生,可以设置两个条件:

  • 必须同时拿起左右两根筷子;
  • 只有在两个邻居都没有进餐的情况下才允许进餐。
#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think();
        take_two(i);
        eat();
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);
    up(&mutex);
    down(&s[i]);
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);
    test(RIGHT);
    up(&mutex);
}

void test(i) {         // 尝试拿起两把筷子
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

 

 

文章转自:https://github.com/CyC2018/CS-Notes/blob/master/docs/notes/%E8%AE%A1%E7%AE%97%E6%9C%BA%E6%93%8D%E4%BD%9C%E7%B3%BB%E7%BB%9F.md#%E7%B3%BB%E7%BB%9F%E8%B0%83%E7%94%A8

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114623.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 从单一到融合,扫地机器人导航技术的“最优解”?

    从单一到融合,扫地机器人导航技术的“最优解”?人工智能浪潮下,智能家居产品层出不穷,但纵观行业发展能真正走入家庭中的产品屈指可数,而扫地机器人却是其中的“网红产品”。根据中怡康数据显示,2013年,我国扫地机器人市场规模仅为8.4亿元,而到了2020年,市场规模已达到94亿元。快速增长的市场同时也在倒逼扫地机器人的性能不断提升“下限”,尤其智能化已成为扫地机器人的高附加值特征。循次渐进,扫地机器人正逐步“完善”在经历2019年的市场寒潮后,2020年扫地机市场快速回暖,除了受疫情影响之外,最关键的原因仍是扫地机器人技术的创新和进步。尤其是各

  • Python assert 断言函数「建议收藏」

    使用assert断言是学习python一个非常好的习惯,pythonassert断言句语格式及用法很简单。在没完善一个程序之前,我们不知道程序在哪里会出错,与其让它在运行最崩溃,不如在出现错误条件时就崩溃,这时候就需要assert断言的帮助。本文主要是讲assert断言的基础知识。pythonassert断言的作用pythonassert断言是声明其布尔值必须为真的判定,如果发生异

  • 能关闭一切进程的无敌命令

    能关闭一切进程的无敌命令

  • java用那个软件编,java编译软件 编写java程序用什么软件?[通俗易懂]

    java用那个软件编,java编译软件 编写java程序用什么软件?[通俗易懂]其实装了JDK就可以做JAVA程序了,但要用文本编辑器之类的东西写程序的源代码,用JDK进行调试运行。适合初学者。当有了一定的经验以后你可以选择集成的JAVA编译器,如JCreator,eclipse。JCreator也适合初学者,因为靠近底层。现在企业开发软件最多用的就是eclipse,因为他是开源的,而且本身就是用JAVA编写的,所以兼容性更好。java用什么编译软件用JCreator或ecl…

  • Android获取Activity(应用)的执行状态及其它信息[通俗易懂]

    Android获取Activity(应用)的执行状态及其它信息

  • Latex数学公式表[通俗易懂]

    Latex数学公式表[通俗易懂]Latex的两种公式模式:行间(inline)模式:即在正文中插入数学内容。行间公式用$…$独立(display)模式:独立成行,可以有或没有编号。无编号用\[…\]

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号