CS-Notes全部笔记在阅读器中打开

计算机操作系统 - 进程管理 - 进阶

经典同步问题

读者-写者问题

主线见计算机操作系统 - 进程管理 · 读者-写者问题，那里用 count、count_mutex 和 data_mutex 实现的是读者优先：只要还有读者在读，后到的读者可以直接进入，写者要一直等待。

三种实现的差别可以用同一组到达顺序来比较（按主线和本节的代码逐行模拟，信号量按先进先出的顺序唤醒）：

读者-写者问题的配图

以下内容由 @Bandi Yugandhar 提供。

主线中的实现可能导致写者饥饿。下面的实现是写者优先的：写者进入队列之后，只需要等待在它之前进入的读者，不会被之后到达的读者一直阻塞。

int readcount, writecount;                     // 初值都为 0
semaphore rmutex, wmutex, readLock, resource;  // 初值都为 1

void reader() {
    // 进入
    down(&readLock);         // 有写者在排队时，读者在这里被挡住
    down(&rmutex);           // 保护 readcount
    readcount++;
    if (readcount == 1)
        down(&resource);     // 第一个读者锁住资源，防止写者进入
    up(&rmutex);
    up(&readLock);

    // 读

    // 退出
    down(&rmutex);
    readcount--;
    if (readcount == 0)
        up(&resource);       // 最后一个读者释放资源
    up(&rmutex);
}

void writer() {
    // 进入
    down(&wmutex);           // 保护 writecount
    writecount++;
    if (writecount == 1)
        down(&readLock);     // 第一个写者挡住之后到达的读者
    up(&wmutex);

    down(&resource);         // 写者之间互斥，并等待正在读的读者退出
    // 写
    up(&resource);

    // 退出
    down(&wmutex);
    writecount--;
    if (writecount == 0)
        up(&readLock);       // 最后一个写者放行读者
    up(&wmutex);
}

每个读者都必须先获取 readLock，而只有第一个写者需要获取 readLock，并且直到队列中没有写者时才会释放，因此这种实现可能导致读者饥饿。

以上两种实现总有一方可能饥饿。下面的实现使用一个先进先出的 serviceQueue 让读者和写者按到达顺序排队，获取共享数据的锁总能在有限时间内完成，因此不会出现饥饿。

int readCount;              // 正在读的读者数，初值为 0
semaphore resourceAccess;   // 控制对资源的读写，初值为 1
semaphore readCountAccess;  // 保护 readCount，初值为 1
semaphore serviceQueue;     // 按到达顺序排队，初值为 1，要求按先进先出的顺序唤醒

void writer() {
    down(&serviceQueue);    // 排队
    down(&resourceAccess);  // 等待独占资源
    up(&serviceQueue);      // 轮到下一个

    writeResource();        // 写

    up(&resourceAccess);
}

void reader() {
    down(&serviceQueue);    // 排队
    down(&readCountAccess);
    if (readCount == 0)
        down(&resourceAccess);  // 第一个读者锁住资源，写者被挡住
    readCount++;
    up(&serviceQueue);      // 轮到下一个
    up(&readCountAccess);

    readResource();         // 读

    down(&readCountAccess);
    readCount--;
    if (readCount == 0)
        up(&resourceAccess);    // 最后一个读者释放资源
    up(&readCountAccess);
}

参考资料

在阅读器中可以用目录和搜索、切换深色模式、练习这篇笔记中的面试题：打开《计算机操作系统 - 进程管理 - 进阶》