读者-写者问题(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);
}
}