实现一个经典的“读者-写者”算法时,若当前临界区中有读者访问,写者再来时必须在临界区外面等候,如果其后读者源源不断地到达,按策略他们均可以进入临界区,始终保持临界区中有读者访问,那么写者可能长时间不能进入临界区而形成饥饿。为解决此类问题,我们修改访问策略,要求当写者到达时,写者具有优先权。具体说,写者到达后,已经在临界区内的读者继续读取直到结束,而后来的读者就不能进入临界区。等所有的读者离开临界区以后让写者先进去访问,然后等写者离开后再允许读者进入临界区。这所谓“写者优先读者-写者”问题。请用信号量和PV操作来描述这一组进程的工作过程。
参考答案:第一部分:假设临界区能容纳的最大读者数量为n。则:
typedef int semaphore; //定义信号量
semaphore mutex = 1; //读写的互斥量
semaphore readers = n; //读者的资源量
void Readers(void) //读者进程
{ while(TRUE) //调度
{
P(mutex); //读写互斥
P(readers); //读者资源量减一,为负时等待
V(mutex); //释放读写互斥
read_data(void); //读者读取数据
V(readers); //离开时释放读者数量,加一
}
}
Void Writers(void) //写者进程
{ while(TRUE)
{
P(mutex); //获取读写互斥量
for(int i=1; i<=n; i++)P(readers);
//将许可读者进入的资源量消耗光
write_data(void); //写入数据
for(int i=1; i<=n; i++)V(readers);
//释放读者的资源量
V(mutex);} //释放读写互斥量
}
第二部分:若对读者的数量不加以限制,那么应该如下书写程序。
typedef int semaphore; //定义信号量
semaphore rwmutex = 1; //读写的互斥量
semaphore rcmutex = 1; //访问读者计数器的互斥量
semaphore nrmutex = 1; //写者等待读者退出的互斥量
int readerscount=0; //读者计数器
void Readers(void) //读者进程
{ while(TRUE) //调度
{
P(rwmutex); //读写互斥
P(rcmutex); //进入修改读者计数器互斥
readerscount ++; //读者数量加一
if(readerscount= =1)P(nrmutex);
//若是第一个读者,互斥写者
V(rcmutex); //释放读者计数器互斥量
V(rwmutex); //及时释放读写互斥量,允许其他进程申请
read_data(void); //读者读取数据
P(rcmutex); //离开临界区时读者计数器互斥
readerscount - -; //读者数量减一
if(readerscount= =0)V(nrmutex);
//所有读者退出临界区
V(rcmutex); //离开时释放读者计数器互斥量
}
}
Void writers(void) //写者进程
{ while(TRUE)
{
P(rwmutex); //获取读写互斥量
P(nrmutex); //若临界区有读者,等待其退出
write_data(void); //写入数据
V(nrmutex); //允许后续第一个读者进入临界区
V(rwmutex); //允许新的读者和写者排队
}
}
上述程序不能保证在等待队列中写者更优一点,因为上述约束条件只能将读者无限制地进入临界区的情况给屏蔽了,而在临界区外,读者和写者还是按照先来先服务的方式排队。
第三部分给出的方法使得访问队列中只要有写者出现,它必然优先进入临界区。
typedef int semaphore; //定义信号量
semaphore rwmutex = 1; //读写的互斥量
semaphore rcmutex = 1; //访问读者计数器的互斥量
semaphore wcmutex = 1; //访问排队写者计数器的互斥量
semaphore nrmutex = 1; //写者等待读者退出的互斥量
int readerscount = 0; //读者计数器
int writerscount = 0; //写者计数器
void Readers(void) //读者进程
{ while(TRUE) //调度
{
P(rwmutex); //读写互斥
P(rcmutex); //进入修改读者计数器互斥
readeerscount++; //读者数量加一
if(readerscount= =1)P(nrmutex);
//若是第一个读者,互斥写者
V(rcmutex); //释放读者计数器互斥量
V(rwmutex); //及时释放读写互斥量,允许其他进程申请
read_data(void); //读者读取数据
P(rcmutex); //离开临界区时读者计数器互斥
readerscount - -; //读者数量减一
if(readerscount= =0)V(nrmutex);
//所有读者退出临界区
V(rcmutex); //离开时释放读者计数器互斥量
}
}
Void Writers(void) //写者进程
{ while(TRUE){
P(wcmutex); //获取写者队列互斥量
writerscount++; //写者队列加一
if(writerscount= =1)P(rwmutex);
//第一写者使用读写互斥量
V(wcmutex); //释放写者计数互斥量
P(nrmutex); //若临界区有读者,等待其退出
write_data(void); //写入数据
V(nrmutex); //释放后续第一个读者
P(wcmutex); //获取写者队列互斥量
writerscount - -; //写者队列减一
if(writerscount= =0)V(rwmutex);
//最后一个写者退出,释放临界区
V(wcmutex); //释放写者计数互斥量
}
}
每个读者进程最开始都要申请一下rwmutex信号量,之后在真正做读操作前即让出(使得写进程可以随时申请到rwmutex)。而只有第一个写进程需要申请nrmutex,之后就一直占着不放了,直到所有写进程都完成后才让出。等于只要有写进程提出申请就禁止读进程排队,从而提高了写进程的优先级。
解析: “写者优先读者-写者”问题也是考试的热点,解决此类问题也分两方面,一是读者访问临界区的最大数量是有限的,例如说n,那么程序就比较简单,看解答中第一部分。若是无限的,则必须设定一个排队的信号量,所有到达临界区的所有读者一写者均需在此排队,按先来先服务使用临界区,一旦进入临界区以后就释放该信号量。见解答的第二部分。
若需要彻底地让后到的写者跨越前面等待的读者,那么需要设定更多的限制,见解答的第三部分。