操作系统原理学习笔记（八）-经典进程同步问题

操作系统原理学习笔记目录

生产者-消费者问题

利用记录型信号量解决生产者-消费者问题：
假定在生产者与消费者之间的公用缓冲池有n个缓冲区，
可利用互斥信号量mutex实现诸进程对缓冲区的互斥使用，
利用信号量empty与full分别表示空缓冲区与满缓冲区的数量。
又假定这些生产者和消费者等效，只要缓冲池未满，生产者可将消息送入缓冲池。只要缓冲池未空，消费者可从缓冲池取走消息。

生产者消费者描述如下：

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void producer() {
    do {
        producer an item nextp;
        ...
        wait(empty);
        wait(mutex);
        buffer[in] = nextp;
        in = (in+1) % n;
        signal(mutex);
        signal(full);
    }while(true);
}
void consumer() {
    do {
        wait(full);
        wait(mutex);
        nextc = buffer[out];
        out = (out+1) % n;
        signal(mutex);
        signal(empty);
        consumer the item in nextc;
        ...
    }while(true);
}
void main() {
    cobegin
        producer();
        consumer();
    coend
}

注意：
每个程序中的wait(mutex)与signal(mutex)需要成对出现，
对资源信号量signal和full的wait和signal操作，也需要成对出现（在不同的程序中出现）。
wait操作的顺序不能颠倒，应先对资源信号量进行wait操作，再对互斥信号量进行wait操作，否则可能出现进程死锁。

利用AND信号量解决生产者-消费者问题：
将AND信号量替换纪录型信号量即可：
用Swait(empty, mutex)代替wait(empty)和wait(mutex)，
用Ssignal(mutex, full)代替signal(mutex)和signal(full)，
用Swait(full, mutex)代替wait(full)和wait(mutex)，
用Ssignal(mutex, empty)代替signal(mutex)和signal(empty)。

int in=0, out=0;
item buffer[n];
semaphore mutex=1, empty=n, full=0;
void producer() {
    do {
        producer an item nextp;
        ...
        Swait(empty, mutex);
        buffer[in] = nextp;
        in = (in+1) % n;
        Ssignal(mutex, full);
    }while(true);
}
void consumer() {
    do {
        Swait(full, mutex);
        nextc = buffer[out];
        out = (out+1) % n;
        Ssignal(mutex, empty);
        consumer the item in nextc;
        ...
    }while(true);
}

利用管程解决生产者-消费者问题：
在利用管程方法解决生产者-消费者问题时，首先为它们建立一个管程，并命名为producerconsumer(PC)
书上写procducerconsumer，但是后面代码没有c，大概率是这里打错了。

包括两个过程：
put(x)过程：将产品投入缓冲池，用count表示缓冲池已有产品数，当count≥N时，缓冲池已满，生产者等待。
get(x)过程：从缓冲池取出产品。用count表示缓冲池已有产品数，当count≤0时，缓冲池已空，消费者等待。
对于条件变量notfull与notempty，分别有过程cwait与csignal对它们操作：
cwait(condition)：管程被占用，其他进程调用该管程时，被阻塞，并挂在条件condition的队列上。
csignal(condition)：唤醒cwait执行后阻塞在条件condition队列的进程，如果不止一个，则选择一个，如果队列为空，则略过。

PC管程的描述如下：

Monitor producerconsumer{
    item buffer[N];
    int in, out;
    condition notfull, notempty;
    int count;
    public:
    void put(item x) {
        if(count >= N) cwait(notfull);
        buffer[in] = x;
        in = (in+1) % N;
        count++;
        csignal(notempty);
    }
    void get(item x) {
        if(count <= 0) cwait(notempty);
        x = buffer[out];
        out = (out+1) % N;
        count--;
        csignal(notfull);
    }
    {
        in = 0;
        out = 0;
        count = 0;
    }
}PC;

利用管程解决生产者-消费者问题可描述为：

罢工了，这代码我写了又不看，照搬太累了，
这段代码在第68页，书名在目录页面有写，目录页在文章顶部。
如果没有书，评论一下我拍照发出来。

哲学家进餐问题

哲学家进餐问题（The Dinning Philosophers Problem）是由Dijkstra提出的典型同步问题。
问题描述：五名哲学家坐在五把椅子上共用一张圆桌，圆桌上有五个碗和五支筷子，哲学家在饥饿时停下思考，拿去左右手最近的两支筷子，拿到两支筷子后才进餐，进餐后才继续思考。

利用记录型信号量解决哲学家进餐问题：
分析可知，筷子是临界资源，为了实现对筷子的互斥使用，可以用一个信号量表示一支筷子，由五个信号量构成信号量数组，描述如下：
semaphore chopstick[5] = {1, 1, 1, 1, 1};
所有信号量被初始化成1，第i名哲学家的活动可描述为：

69页代码

容易看出，如果五名哲学家同时伸手拿走左手边的筷子，那么就会出现死锁，这种情况可如此避免：
1.最多允许四名哲学家拿筷子，这样至少会有一名可以获得筷子。
2.左右两支筷子都在时才可拿筷子（类似AND信号量）。
3.奇数号先取左手的筷子，再取右手的筷子，偶数号则相反（筷子必须按顺序拿，没筷子则阻塞等待）。

利用AND信号量机制解决哲学家进餐问题：
即上面讲的第二种方法，描述如下：

70页代码

读者-写者问题

读者-写者问题（Reader-Writer Problem）描述：
一个数据文件可被多个进程共享，将读文件的进程称为“reader进程”，将写文件的进程称为“writer进程”。
允许多个进程同时读取一个数据文件（因为互不影响），但在writer写数据时，不允许reader与其它writer操作。
该问题的核心在于保证一个writer进程必须与其他进程访问共享对象的同步，常被用来测试新同步原语。

利用记录型信号量解决读者-写者问题：
设置一个互斥信号量wmutex，再设置一个整型变量readcount表示reader参与的数量，
只要有一个reader正在读，即readcount＞0时，writer不允许执行，
仅当readcount=0时，reader才需执行wait(wmutex)，操作成功才可读数据。
当readcount执行-1操作变为0后，才需执行signal(wmutex)，允许writer写程序。
因为readcount可能被多个reader同时访问，也属于临界资源，因此也需要一个互斥信号量rmutex。

读者-写者问题可描述为：

71页代码

利用信号量集机制解决读者-写者问题：
这里的问题有了新的限制，最多允许RN个读者同时读。为此，又引入了信号量L，并赋予初值为RN。
通过wait(L, 1, 1)操作来控制读者的数目，每当有一个读者进入时，就要执行wait(L, 1, 1)操作，使L减1，有RN个读者进入读后，L减为0，禁止其他reader进入。

描述如下：

72页代码

其中，sWait(mx, 1, 0)语句起着开关作用。无writer进程时，mx=1，reader可执行，
但一旦writer进入写操作，mx=0，reader进程无法执行。
Swait(mx, 1, 1, L, RN, 0)语句表示无writer进程（mx=1），且无reader进程在读操作（L=RN），writer才能进入临界区操作。