Skip to content

ch6 Process Synchronization.pdf

智云课堂

操作系统（本）2024-11-07 第 7-8 节

经典进程同步问题

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

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);

Review Questions

image-20241107135325834

  1. 问上面的 if+signal 能不能和下面的 signal 互换，能不能互换

    • 不能，不然可能读写互斥

  2. 不能，可能还没判断时又有读者访问，然后你又说写者可以访问，那不就读写互斥了

  3. 第 5 个，写者在读者之间就可能造成

image-20241107141007606 这就是一个简单的互斥问题，一个临界资源（说复杂点就是只有写者的读者写者问题)

image-20241107141124948

这是个读者优先问题，看代码

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）

[!QUESTION] 每个哲学家拿起第 1 根筷子一定时间后，若拿不到第 2 根筷子，再放下第 1 根筷子

可能会出现没哲学家同时拿筷子，这样就死锁了

Review Questions

image-20241112095112130

  1. mutex 解决互斥，另两个解决同步
    • 如果将两个 wait 互换可能会死锁，两个 signal 交换不会
  2. 因为缓冲区是临界资源（只支持一个一个地访问，性能太差了）
  3. wrt 负责写者互斥，mutex 负责读者对 readcount 互斥
  4. 因为变量修改不是原子的
  5. 同时拿起左边的筷子

*Monitors

Monitors（管程）是一种高级同步机制，保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程，管程比信号量好控制

管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块

略

ch6 Process Synchronization.pdf