Skip to content

进程同步经典问题

:material-circle-edit-outline: 约 648 个字 :fontawesome-solid-code: 56 行代码 :material-clock-time-two-outline: 预计阅读时间 3 分钟

Bounded-Buffer Problem

生产者消费者问题（Producer-consumer problem），也称有限缓冲问题（Bounded-buffer problem）

生产者消费者模型有三个要求，一个互斥，两个同步：

  1. 有限缓冲池（bounded buffer pool）的访问是互斥的，一次只能有一个进程访问
  2. 要先生产，然后才能开始取走
  3. 先 free buffer，再使用 buffer

解决方法

对于多生产者和多消费者，N 个 buffer 的情况，我们设置三个信号量

  • Shared data: semaphore full, empty, mutex
    • 前两个解决同步问题，表示有几个 buffer 用了，几个还没用
    • 后一个解决互斥问题

Initially: full = 0, empty = n, mutex = 1

structure of Producer Process

 do { 
     produce an item in nextp

     wait(empty);
     wait(mutex);

     add nextp to buffer

     signal(mutex);
     signal(full);
 } while (1);

structure of the Consumer Process

do { 
    wait(full);
    wait(mutex);

    remove an item from buffer to nextc

    signal(mutex);
    signal(empty);

    consume the item in nextc
} while (1);

Readers-Writers Problem

A data set is shared among a number of concurrent processes

  • 读读允许
  • 读写、写写互斥

清点一下要求：

  1. 允许多个读者读取
  2. 同一时间只允许一个写者写
  3. 写者写完前不允许其它读者写者访问
  4. 写者进行写操作前确保所有读者写者不在访问

有两个问题

  • The first readers-writers problem
    • 允许多个读者同时读，只允许写者一个一个去写，这样的话写者可能饿死
  • The second readers-writers problem
    • 写者只要 ready，就尽快写掉，这样的话读者可能饿死

解决办法

我们用两个信号量，以及一个整数

  • mutex = 1, wrt = 1
    • 前者控制多个读者互斥修改 readcount
  • readcount = 0
    • 有几个读者在同时读

The structure of a Reader Process

do {
    wait(mutex);
        readcount++; 
        if (readcount == 1) // 表明之前没有读者
            wait(wrt);  // 不准写
    signal(mutex);

reading is performed

    wait(mutex);
        readcount--;
        if (readcount == 0)
            signal(wrt);
    signal(mutex);
} while (TRUE);

The structure of a Writer Process

do {
    wait (wrt) ;                

writing is performed

    signal (wrt) ;
} while (TRUE);

写者在读者之间就可能造成饥饿问题

Dining-Philosophers Problem

N 个哲学家围着一个圆桌坐，两个相邻的人之间有一根筷子用于共用

一个哲学家吃饭需要左右两根筷子

我们希望避免饥饿问题

解决方法

  • Shared data
    • Bowl of rice (data set)
    • Semaphore chopstick [5] initialized to 1

对于第 i 个哲学家

do {
    wait(chopstick[i])
    wait(chopstick[(i+1) % 5])
    …
    eat
    …
    signal(chopstick[i]);
    signal(chopstick[(i+1) % 5]);
    …
    think
    …
} while (1);

死锁是可能发生的，我们可以额外加限制条件，例如：

  1. Allow only 4 philosophers to be hungry at a time.
  2. Allow pickup only if both chopsticks are available. ( Done in critical section )
  3. Odd# philosopher always picks up left chopstick 1st, even# philosopher always picks up right chopstick 1st.
  4. 为了避免死锁，把哲学家分为三种状态：思考、饥饿、吃饭，并且一次拿到两只筷子，否则不拿。（Dijkstra）

每个哲学家拿起第 1 根筷子一定时间后，若拿不到第 2 根筷子，再放下第 1 根筷子，可能会出现没哲学家同时拿筷子，这样就死锁了

同时拿起左边的筷子也会死锁，情况很多