进程调度“写者优先问题”的思考

2019-04-28  本文已影响0人  地球上的新新人

教材:林果园等.计算机操作系统[M],北京:清华大学出版社,2011.

注:在P45页下方,书上给出了写者优先算法,对于其中的信号量wr的作用有点想法。以下纯属个人思考,联系邮箱03170908@cumt.edu.cn,欢迎交流探讨。

书本程序如下:

int readcount=0,writecount=0;
semaphore mrc=1,mwc=1,wr=1,wsem=1,rsem=1;
cobegin

void reader_i(){
P(wr);P(rsem);
P(mrc);readcount++;if(readcount==1)P(wsem);V(mrc);
V(rsem);V(wr);
READ;
P(mrc);readcount--;if(readcount==0)V(wsem);V(mrc);}

void writer_i(){
P(mwc);writecount++;if(writecount==1)P(rsem);V(mwc);
P(wsem);WRITE;V(wsem);
P(mwc);writecount--;if(writecount==0)V(rsem);V(mwc);}

coend

写者优先的两个方面体现

公平情况下,根据到达时间的先后,决定执行的先后顺序。写者优先,意味着写者可以实现插队,优先于一部分在他前面到达并正排队中的读者执行。
情况1:正在运行的是写者,新的写者过来时可以优先于所有正在等待的读者,运行。
情况2:正在运行的是读者,新的写者过来时可以优先于大部分正在等待的读者,运行。

1.关于rsem的作用

当第一个写者到达申请占用rsem信号量,成功之后便一直占用,后续到达的读者会因申请不到rsem信号量而阻塞。后续写者到达时,由于不需要申请rsem信号量,因而可以直接排在这个写者后面,实现了上面的情况1。

2.关于wr的作用

当一个读者执行完计数,将要进入READ步骤而未释放rsemwr时,此时的其他读者等待在wr的阻塞队列,而其他写者等待在rsem的阻塞队列。因为先执行V(rsem)后执行V(wr),所以在同时等待时,写者会被优先唤醒,实现了情况2。

PS:这里对于写者的插队情况做一个详细分析:

1.针对情况1运行的是写者,无疑问的,因为在运行的写者始终持有着rsem,阻塞了所有等待中的读者,所以新来的写者可以直接插队到所有正在排队中的读者前面,插队到最前面

2.针对情况2运行的是读者,因为信号量wr的作用是,当有读者占有着rsem而未释放时,至多让一个读进程在rsem上排队,其余的读进程只能在wr上排队。所以写者到来时,如果有一队读者正在排队,新写者可以优先于所有处于wr的等待队列的读者,即插到第二位的位置。

上一篇 下一篇

猜你喜欢

热点阅读