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

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

 

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

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

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

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)


相关推荐

  • 单射、满射、双射(一一映射)

    单射、满射、双射(一一映射)设函数f:X->Y,y=f(x)单射:任给x1和x2属于X,若x1≠x2,则f(x1)≠f(x2),称f为单射满射:任给y属于Y,都存在x属于X使得f(x)=y,称f为满射双射:若f既是单射又是满射,称f为双射,也叫一一对应。

  • ida反汇编使用方法_开源反汇编工具

    ida反汇编使用方法_开源反汇编工具本文详细介绍反汇编工具IDAPro的使用。

    2022年10月22日
  • 内网安全 信息收集(收集内网计算机的所有信息 进行攻击.)

    内网安全 信息收集(收集内网计算机的所有信息 进行攻击.)?“信息收集”会对渗透测试工程师和网络安全工程师具有重大作用:???在渗透测试人员进入一个内网后,面对的是一片“未知的区域”,所以渗透测试人员首先会对当前所处的网络环境进行判断,通常的判断分为三种.?(1)我是谁?——对计算机的角色进行判断.?(2)我在哪?——对目前机器所处位置区域的判断。?(3)这是哪?——对目前机器所处网络环境的拓扑结构进行分析和判断。

  • @Page validateRequest=false「建议收藏」

    @Page validateRequest=false「建议收藏」validateRequest=false是禁用了请求验证,同时他也就把一些安全的意识给去掉了,比如跨服务器脚本攻击(xss)。(建议不要这样做)想要截获错误的信息给用户一个好的体验。1protectedvoidPage_Error(objectsender,EventArgse)2{3Exceptionex=Server.GetLastE…

  • visual studio新手使用教程「建议收藏」

    visual studio新手使用教程「建议收藏」目录1.下载安装VisualStudio2.新建工程3.新建项目4.添加源文件5.编译一闪而退的问题6.使用scanf函数报错问题7.VS常用调试程序快捷键8.VS的调试窗口9.工具->选项对于刚刚接触编程的新手来说,最先需要熟练掌握的当然是语言之祖——C语言,而C语言编译器首当其冲的必然是visualstudio,小编入门使用VC6.0,…

  • Mac 计算机的日常使用 和 从零开始搭建Python开发环境

    Mac 计算机的日常使用 和 从零开始搭建Python开发环境Mac计算机的日常使用和从零开始搭建Python开发环境本文作者:魏泯效率魔法师,最后更新时间:2019年1月10日在进行学习mac常用操作的时候,保证你的mac已经连接网络。目录&#

发表回复

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

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