首页 / 技术分享 / 计算机基础 / 正文
原创

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题

来源:CSDN博客 作者:YY同学 2021-06-23 13:52:44
点击转到:计算机基础精品课程推荐

笔者:YY同学

生命不息,代码不止。好玩的项目尽在GitHub


文章目录

    • 什么是 IPC 问题?
    • 冲突域(Critical Section)
    • IPC 问题解决方案必须满足的四大准则
    • 五种 IPC 问题解决方案
    • 三类 IPC 问题模型


什么是 IPC 问题?

IPC(Inter Process Communication)问题是进程或线程之间相互通信时可能会发生的一系列问题,一般是共享数据的读写冲突问题。通常情况下,对于共享数据,我们希望在某个时刻只有一个进程(线程)在操作(增、删、查、改)它,这就意味着此时其他进程(线程)无法进入该数据域,这种性质就是互斥性(Mutual Exclusion),而该数据域又称冲突域(Critical Section),IPC 问题大多数是解决冲突域的问题,解决方案需要具备良好的互斥性。


冲突域(Critical Section)

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题

冲突域是指代码中可能存在读写冲突且含有共享变量的区域。上图表示的是 IPC 问题的一般解决思路,由进入冲突、冲突部分和退出冲突三个部分的代码块组成。其中,在冲突部分中实现单进程(线程)的读写会比较安全,这意味着这一过程将没有其他进程(线程)参与。


IPC 问题解决方案必须满足的四大准则

内容现实生活中的例子
准则一没有两个进程(线程)可以同时进入冲突域公共厕所单人隔间不可能同时进去两个人
准则二冲突域中的进程(线程)不能决定 CPU 处理速度以及限定 CPU 的 个数你无法预计你上厕所需要多久,而且你也不知道自己的排放量是多少
准则三当进程(线程)离开冲突域后不能将冲突域锁住,换言之此时其他进程(线程)要能够进入冲突域当你上完厕所后你不能把厕所门锁上然后翻墙出去,这样虽然厕所里并没有人在使用它,但其他人也无法进入
准则四没有进程(线程)可以永久占用冲突域,没有进程(线程)需要在进入冲突域前永久等待你不可能一直呆在厕所里,在外面等你的人也不能一直在外面等你

五种 IPC 问题解决方案

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题
解决方案一:禁用中断

  • 描述:在冲突域内部禁止使用上下文切换。
  • 优点:可以杜绝其他进程(线程)对进入冲突域的执行进程(线程)的干扰。
  • 缺点:当有进程(线程)进入冲突域之后,会对所有进程进行强制中断。
  • 评价:该解决方案虽然能达到目的,但是缺乏限制,太过随意。

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题
解决方案二:添加 🔒 变量

  • 描述:通过 lock 变量来判断当前冲突域是否有进程(线程)进入,如有则制止其他进程(线程)进入。
  • 优点:想法很不错,看似可行。
  • 缺点:但是 lock 本身也是共享变量,变量的公有性赋予了所有进程(线程)对其更改值的权力。
  • 评价:该解决方案没有办法达到目的,因为每个进程(线程)在进入冲突域前都可以更改 lock 的值,相当于门锁不起任何作用,任何人都可以从外面开锁。

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题

解决方案三:加入 turn 变量严格轮换

  • 描述:通过 turn 的值来判断当前轮到哪个进程(线程)进入冲突域并且制止其他进程(线程)进入。
  • 优点:与 lock 变量不同,turn 变量更改的位置是在冲突域之后,并且是多进程(线程)轮换。相当于只有等当前进程(线程)离开冲突域之后,turn 的值才会变化,别的进程(线程)此时才能进入冲突域,这符合我们的设计需要。
  • 缺点:CPU 执行效率较低,而且违反了第三准则。当 Process 0 离开冲突域时,turn 的值变为 1,此时只有 Process 1 能够进入冲突域,但是此时 Process 1 可能才刚刚开始执行冲突域之前部分的代码。此时 Process 1 并未进入冲突域,但是它把其他进程(线程)锁在外面了。
  • 评价:变量设置上可行,但是 CPU 执行效率较低且违背第三准则,所以该解决方案没有办法达到目的。

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题

解决方案四:彼得逊解决方案

  • 描述:使用 True 和 False 作为信号,每个进程(线程)信号独立。
  • 优点:采用分块理念,设置控制信号,使用函数封装块增加使用的便捷性,提高效率。
  • 缺点:浪费 CPU 执行时间,优先级颠倒问题(优先级高的进程可能会陷入忙等)。
  • 评价:结合前三种解决方案的优点,弥补其缺点。虽然仍有不足,但不失为一个可行的解决方案。

(计算机基础知识)【CO003】操作系统笔记4 —— IPC 问题

解决方案五:信号量(Semaphore)

  • 描述:在彼得逊解决方案的基础上推广到一般情况,设置信号量 *s,初始值为 1。当 *s = 0 的时候进程(线程)锁定。
  • 优点:使用原子操作函数 up() 和 down(),杜绝了冲突域内的上下文切换。
  • 缺点:无。
  • 评价:对于每个进程(线程),在进入冲突域前先锁定,离开冲突域之后再把锁打开。原子性保证互斥性的同时,也将时间效率最大化,是一个较完美的解决方案。

原子操作函数伪代码

void down(semaphore *s) { 
    if( *s > 0 )
        *s = *s - 1;
    else
        sleep();
}

void up(semaphore *s) { 
    if( *s == 0 )
        wakeup_proc();
    *s = *s + 1;
}

三类 IPC 问题模型

  1. 生产者-消费者模型(Producer-Consumer Model)
  • 进程(线程)池中有若干生产者和消费者,以及一个产品仓库。
  • 生产者负责生产产品存入仓库,消费者负责从仓库消化生产者生产的产品。
  • 同时只能有一个进程(线程)在运行且产品仓库的容量一定,会实时显示当前仓库中有多少产品。
  • 当仓库满的时候生产者将会停止生产产品(进入 sleep 状态),直到仓库有空位出现;同理,当仓库空的时候,消费者会停止消费产品(进入 sleep 状态)。

伪代码

#define N 100
typedef int semaphore;
semaphore mutex = 1;  // mutual exclusive,互斥信号量,等于 0 时锁定
semaphore empty = N;  // 表示一开始有 N 个位置是空的
semaphore full = 0;   // 表示一开始有 0 个位置是满的

/*  Producer  */
void producer(void) {
    int item;
    while(TRUE) {
        item = produce_item();
        down(&empty);  // 如果满了就让自己睡眠,由消费者唤醒
        down(&mutex);  // mutex 必须放在后面,避免发生死锁(dead lock)
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

/*  Consumer  */
void consumer(void) {
    int item; 
    while(TRUE) {
        down(&full);   // 如果空了就让自己睡眠,由生产者唤醒
        down(&mutex);  // mutex 必须放在后面,避免发生死锁(dead lock)
        item = remove_item();
        up(&mutex);
        up(&empty);
        consume_item(item);
    }
}

  1. 数据库读写模型(Database R&W Model)
  • 进程(线程)池中有若干进程(线程),分别代表不同的 Reader 和 Writer。
  • 在 Writer 没有写入数据的情况下,多个 Reader 可以同时读取数据,并且在 Reader 读数据的时候 Writer 无法写入数据。
  • 在 Writer 写入数据时,所有其他 Reader 和 Writer 无法读写。

伪代码

semaphore db = 1;     // 确保读写进程无冲突
semaphore mutex = 1;  // 确保单个进程无冲突
int read_count = 0;

void writer(void) {
    while(TRUE) {
        prepare_write();
        down(&db);  // 写的时候不能有其他读写
        
        write_database();
        up(&db);
    }
}

void reader(void) {
    while(TRUE) {
        down(&mutex);
        read_count++;
        if(read_count == 1)
            down(&db);  // 读的时候不能写可以读,但是读需要一个个读,所以要暂时锁住
        up(&mutex);

        read_database();

        down(&mutex);
        read_count--;
        if(read_count == 0)
            up(&db);  // 一个读完,打开门锁,读下一个
        up(&mutex);
        process_data();
    }
}

  1. 哲学家进餐模型(Dining Philosopher Model)
  • 5 个哲学家围着圆桌吃饭,桌上有 5 根筷子。
  • 每个哲学家需要拿到一双筷子( 2 根)才能吃饭。
  • 每个哲学家吃完饭后会把手中的筷子放回桌上,供别的哲学家吃饭。

伪代码

#define N 5
#define LEFT  ((i+N-1) % N)  // 我们假定每根筷子摆在两个哲学家中间,谁都可以拿起筷子
#define RIGHT  ((i+1) % N)  // LEFT 和 RIGHT 分别代表当前哲学家左边和右边的人

int state[N];  // 三种状态 THINKING,HUNGRY 和 EATING
semaphore mutex = 1;
semaphore s[N];  // 控制哲学家状态的信号量

void philosopher(int i) {
    think();
    take_chopsticks(i);  // Entry of Critical Section
    eat();  // Critical Section
    put_chopsticks(i);  // Exit of Critical Section
}

void take_chopsticks(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    test(i);  // 测试是否能拿起一双筷子
    up(&mutex);
    down(&s[i]);  // 可以拿起筷子的话就吃饭,不可以就 sleep
}

void test(int i) {
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING){
        state[i] = EATING;
        up(&s[i]);  // 唤醒还没吃饭的哲学家
    }
}

void put_chopsticks(int i) {
    down(&mutex);
    state[i] = THINKING;
    test(LEFT);   // 放下筷子后绅士地问左边的哲学家吃不吃
    test(RIGHT);  // 放下筷子后绅士地问右边的哲学家吃不吃
    up(&mutex);
}

版权声明:什么课程值得买倡导尊重与保护知识产权。未经许可,任何人不得复制、转载、或以其他方式使用本站《原创》内容,违者将追究其法律责任。本站文章内容,部分图片来源于网络,如有侵权,请联系我们修改或者删除处理。

精品课程推荐

热门文章

在线
客服

官方客服

如遇课程问题,可联系客服为您解决

电话客服:18482185493

Q Q客服:联系客服

工作时间:9:00-18:00,节假日休息

顶部