经典IPC问题 - 读者-写者问题

 

读者-写者问题(Courtois et al,1971)为数据库访问建立了一个模型。例如,设想一个飞机订票系统,其中有许多竞争的进程试图读写其中的数据。多个进程同时读是可以接受的,但如果一个进程正在更新数据库,则所有其他进程都不能访问数据库,即便是读操作也不行。

这里的问题是如何对读者和写者进行编程。下面给出了一种解法(允许多个读者操作数据库,写者可能被饿死)。

typedef int semaphore;

semaphore mutex = 1;    /* 控制对读者数量rc的访问 */
semaphore db = 1;       /* 控制对数据库的访问 */

int rc = 0;

void reader(void)
{
    while (TRUE)
    {
        down (&mutex);
        rc = rc + 1;
        if (rc == 1) down(&db);
        up(&mutex);
        read_db();
        down (&mutex);
        rc = rc - 1;
        if (rc == 0) up(&db);
        up (&mutex);
        ...
    }
}

void writer(void)
{
    while(true)
        {
            down(&db);
            write_db();
            up(&db);
        }
}

该解法中,第一个读者对信号量db执行down操作。随后的读者只是递增一个计数器rc。当读者离开时,它们递减这个计数器,而最后一个读者则对db执行up操作,这样就允许一个阻塞的写者(如果存在)访问数据库。

现在假设一个写者到来,由于写操作是排他的,所以该写者不能访问数据库,而是被挂起。随后,又有读者出现,这样只要有一个读者活跃,随后而来的读者就都被允许访问数据库。这种策略的结果是只要有读者陆续到来,它们一来就被允许进入,而写者将一直被挂起直到没有一个读者为止。

为了防止这种情况,程序可以略做如下改动:当一个读者到来而正有一个写者在等待时,则读者被挂在写者后边,而不是立即进入。这样,写者只需等待它到来时就处于活跃状态的读者结束,而不用等那些在它后边到来的读者。这种解法的缺点是并发性较低,从而性能较差。

(Courtois 1971)给出的写者优先的解法

typedef int semaphore;

semaphore mutex_rc = 1, mutex_wc = 1;   /* 控制对读者写者数量的控制 */
semaphore w = 1, r = 1;                 /* 控制对数据库的访问 */

int rc = 0, wc = 0;                     /* 读者数量、写者数量 */

void reader(void)
{
    while (TRUE)
    {
        down (&mutex_rc);
        down (&r);
        rc = rc + 1;
        if (rc == 1) down(&w);
        up (&r)
        up (&mutex_rc);
        read_db();
        down (&mutex_rc);
        rc = rc - 1;
        if (rc == 0) up(&w);
        up (&mutex_rc);
    }
}

void writer(void)
{
        while(TURE)
        {
            down (&mutex_wc);
            wc = wc + 1;
            if (wc == 1) down(&r);
            up (&mutex_wc);
            down(&w);
            write_db();
            up(&w);
            down (&mutex_wc);
            wc = wc - 1;
            if (wc == 0) up(&r);
            up (&mutex_wc);
        }
}