【操作系统】Semaphore处理读者-写者问题

2024-04-08 08:01:27

“Reader-Writer”问题

问题描述
问题分析
问题解决

问题描述

有读者和写者两组并发进程，共享一个文件，当两个或以上的读进程同时访问共享数据时不会冲突，但如果某个写进程和其他进程同时访问共享数据时可能会导致数据不一致的错误。

问题分析

关系分析

此问题的描述中可以分析出4条要求：

多个读者可以同时不冲突地读取文件内容
写者只能单个向文件中写信息
任一写者在完成写操作之前不允许其他读者或写者工作
写者执行写操作之前，必须等待其他读者或写者退出

因此，直观分析一下可知，读者和写者之间是互斥的，写者之间也是互斥的，读者之间不存在互斥但有同步关系。

求解思路

读者和写者两类进程。
写者进程和任何进程互斥。
读者必须实现与写者的互斥和其他读者的同步。
针对读者的情况，需要设计一个计数器，判断当前是否有读者读文件。
不同读者对计数器的访问也是互斥的。

信号量设置

下面有两种处理方案，分别使用三个信号量和四个信号量（多一个w信号量）：

count：计数器，用于记录当前读者数量，初始值为0
mutex：互斥信号量，用于保护更新count变量时的互斥，初始值为1
rw：互斥信号量，用于保护读者和写者的互斥访问，初值为1
w：用于保障“写优先”的原则，防止写进程饿死

问题解决

方案一

int count = 0;  // 记录当前读者数量

semaphore mutex = 1;  // 用于保护更新count变量时的互斥
semaphore rw = 1;  // 用于保护读者和写者互斥地访问文件

writer() {
    while(1) {
        P(rw);  // 互斥访问文件
        // TODO 写入
        V(rw);  // 释放共享文件
    }
}

reader() {
    while(1) {
        P(mutex);  // 互斥访问count变量
        if (count == 0) {  // 当第一个读者进程读取共享变量时
            P(rw);  // 阻止写进程写入
        }
        V(mutex);  // 释放互斥变量mutex
        // TODO 读取共享文件内容
        P(mutex);  // 互斥访问count变量
        count--;  // 读者计数器-1
        if (count == 0) {  // 当最后一个读者进程读完共享文件
            V(rw);  // 允许写进程写入
        }
        V(mutex);  // 释放互斥变量count
    }
}

方案二

int count = 0;  // 记录当前读者数量

semaphore mutex = 1;  // 用于保护更新count变量时的互斥
semaphore rw = 1;  // 用于保护读者和写者互斥地访问文件
semaphore w = 1;    // 用于实现写优先

writer() {
    while(1) {
        P(w);   // 在无写进程请求时进入
        P(rw);  // 互斥访问文件
        // TODO 写入
        V(rw);  // 释放共享文件
        V(w);   // 恢复对共享文件的访问
    }
}

reader() {
    while(1) {
        P(w);   // 在无写进程请求时进入
        P(mutex);  // 互斥访问count变量
        if (count == 0) {  // 当第一个读者进程读取共享变量时
            P(rw);  // 阻止写进程写入
        }
        V(mutex);  // 释放互斥变量mutex
        V(w);   // 恢复对共享文件的访问
        // TODO 读取共享文件内容
        P(mutex);  // 互斥访问count变量
        count--;  // 读者计数器-1
        if (count == 0) {  // 当最后一个读者进程读完共享文件
            V(rw);  // 允许写进程写入
        }
        V(mutex);  // 释放互斥变量count
    }
}

对比

读与写比较起来，方案一的“读优先”可能会导致写进程饥饿，这是不公平的。所以，方案二在方案一的基础上增加了一个保障“写优先”的信号量，即当前无读进程正在读文件时“写优先”，这种机制相对公平。

码农公寓