以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  讨论一下写者优先问题的<官方>答案  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=56620)


--  作者:lionx
--  发布时间:12/11/2007 4:02:00 PM

--  讨论一下写者优先问题的<官方>答案
void reader()
{
P(mutex3);
   P(read);
      P(mutex1);
         readcount++;
         if (readcount==1)
            P(write);
      V(mutex1);
   V(read);
V(mutex3);
reading;
P(mutex1);
   readcount--;
   if (readcount==0)
      V(write);
V(mutex1);
}
void writer()
{
P(mutex2);
   writecount++;
   if (writecount==1)
      P(read);
V(mutex2);
P(write);
   writing;
V(write);
P(mutex2);
   writecount--;
   if (writecount==0)
      V(read);
V(mutex2);
}
06年11月习题课的答案

下面是我的分析:
问题:写者在写,则其余写者和读者等待;写者写完,优先释放下一个写者;
读者在读,若无写者等待,则其他读者可读;读者在读,若有写者等待,则其他读者等待。

互斥:写者之间互斥(故设置信号量write(初值为1)),读者和写者之间互斥(read(1));读者之间不互斥;
记录当前读者个数(readcount(0))和写者个数(writecount(0)),读者对readcount互斥访问(mutex1(1)),写者对writecount互斥访问(mutex2(1));
为保证在有读者等待的时候,新写者到来也优先释放写者,让等待的读者继续等待,不能将读者和写者阻塞在同一队列上(mutex3(1))。

阻塞分析:当有写者在写时,其余写者阻塞在write上,第一个读者阻塞在read上,其他的读者堵塞在mutex3上。当一个写者写完后,若有写者等待,则唤醒一个写者,否则唤醒第一个读者,由第一个读者唤醒其余读者。
当有读者在读时,一读者R通过P(read)还未V(read),此时新到来的第一位写者W阻塞在read上,其余写者阻塞在mutex2上;新到来的第一位读者R1阻塞在read上,其余读者阻塞在mutex3上:(1)若正在等待的第一位写者W先于读者R1到来,则他先被读者R释放,接着W会释放其余写者,使原阻塞在mutex2上的写者通过mutex2,重新阻塞在write上,而所有等待的读者仍然阻塞在原来的地方;(2)否则读者R先释放读者R1,R1代替R的位置,原来等待在mutex3上的第一位读者R2被阻塞在read上,但此时R2在read等待队列上必处于写者W之后,成为情况(1)。因此可以看到,在上面的方案中,新写者到来后,最多再放行一位读者。

这里的mutex1好像没什么作用,因为read的初值是1,故而read可以保护readcount而无需mutex1了。


--  作者:EagleSoaring
--  发布时间:12/11/2007 7:52:00 PM

--  
还是有用的,read可以保护上面的readcount,保护不了下面的readcount


--  作者:lionx
--  发布时间:12/11/2007 10:41:00 PM

--  
呵呵是我说错了,我是说
void reader()
{
P(mutex3);
   P(read);
      P(mutex1);
         readcount++;
         if (readcount==1)
            P(write);
      V(mutex1);
这里的P(mutex1)和V(mutex1)好像没什么用
--  作者:albani
--  发布时间:12/11/2007 10:54:00 PM

--  
有用的,保护readcount,新来的读者是不会同时修改readcount
但是可能和下面完成的读者发生错误
--  作者:EagleSoaring
--  发布时间:12/11/2007 11:15:00 PM

--  
去掉上面的P(mutex1)和V(mutex1) 之后,
readcount会出错

--  作者:okdavinci
--  发布时间:12/12/2007 11:05:00 PM

--  
reader()
{
   P(read)
    P(mutex)
   V(read)
     readcount ++
    if(readcount == 1)
       P(write)
   V(mutex)

  读
  
  P(mutex)
  readcount --
  if(readcount == 0)
     V(write)
V(mutex)
==============
读者是这样应该可以吧?
}


--  作者:albani
--  发布时间:12/13/2007 11:10:00 PM

--  
以下是引用okdavinci在2007-12-12 23:05:00的发言:
reader()
{
    P(read)
     P(mutex)
    V(read)
      readcount ++
     if(readcount == 1)
        P(write)
    V(mutex)

   读
   
   P(mutex)
   readcount --
   if(readcount == 0)
      V(write)
  V(mutex)
==============
读者是这样应该可以吧?
}


这样感觉问题不是太大,但是好像没有充分体现写者优先,例如,现在有一写者在写,来了N个读者全部被挂在read上,写者完成后,读者一个一个的释放,在还没全释放完的时候来了个写者,这个写者只能等这N个读者完成后才能写。


--  作者:EagleSoaring
--  发布时间:12/14/2007 3:14:00 AM

--  
同意楼上的
--  作者:lionx
--  发布时间:12/14/2007 11:48:00 AM

--  
是的,所以我认为官方的答案还是不错的。要是想要绝对的写者优先,应该要读者也能访问writecount
--  作者:zewixi
--  发布时间:12/20/2007 11:05:00 PM

--  
第二类读者-写者问题的如下解法:
众大牛帮忙找找错误吧!谢过先!

int readCnt=0;       //表示当前读者数目,初值为0
int writeCnt=0;      //表示当前写者数目,初值为0
Semaphore mutexRC;   //互斥对readCnt变量的使用,初值为1
Semaphore mutexWC;   //互斥对writeCnt变量的使用,初值为1
Semaphore read;      //互斥对文件的读与写,初值为0
Semaphore write;     //互斥对文件的写与写,初值为1
Semaphore mutexR;    //用于第一个等待的读者释放后续等待的读者,初值为1


任一读者:
void Reader_i() {
    P(mutexR);
    P(mutexWC);
    if(writeCnt>0) {    //检查是否有写者等待
        V(mutexWC);
        P(read);        //写者优先有则等待
    }//end if
    else
        V(mutexWC);
    V(mutexR);
    P(mutexRC);
    readCnt=readCnt+1;
    if(readCnt==1)      //第一个读者开始读
        P(write);       //阻止后来的写者
    V(mutexRC);
    读文件;
    P(mutexRC);
    readCnt=readCnt-1;
    if(readCnt==0)      //最后一个读者读完
        V(write);       //唤醒等待的写者
    V(mutexRC);
}//end Reader

任一写者:
void Writer_i() {
    P(mutexWC);
    writeCnt=writeCnt+1;
    V(mutexWC);
    P(write);
    写文件;
    V(write);
    P(mutexWC);
    writeCnt=writeCnt-1;
    if(writeCnt==0)    //无写者等待或正在写
        V(read);       //才唤醒读者
    V(mutexWC);
}//end Writer

[此贴子已经被作者于2007-12-21 10:36:42编辑过]

--  作者:applestar
--  发布时间:12/21/2007 6:31:00 PM

--  
至于优先问题要看你怎么考虑,比如读者优先问题大家意见都很一致,都是肯定当有读者在读时新来的读者不需要等待,但是如果有写者在写同时还有写者在等待,然后又来了读者,那是否允许读者跳过等待的读者呢。显然大部分解决方案没有考虑跳过这个问题,都默认按照时间顺序,如果是要求觉得读者优先我认为应该读者应该跳过等待写者。至于写者优先显然不同版本考虑不一致有的考虑了绝对优先即写者最多等待一个读者即使读者比写者先来,这样就要求在read外再加一个信号量以保证最多只有一个读者在read上等待,从而写者易于跳过read上的读者因为最多只有一个读者在上面等待。如果不要求写者那么霸道可以不需要外层的信号量。一些国外教材有的考虑了,有的没有考虑因此两个版本都有,这主要取决于题目要求。而且读写问题作为基本模型不同的扩展模型要求不一样具体考虑就是了。此外还有一些要求无饥饿的读写问题等等。pv实现无饥饿也是很重要的。我发现饥饿问题在很多时候大家都不考虑。
--  作者:sweepthesky
--  发布时间:12/23/2007 11:58:00 AM

--  
第二类读写者问题。
就用信号量来讲,想实现严格的在每一个写者到来之时如文件没被读写则下一个操作文件的一定是写者。是做不到的。
实现写者优先,实际上是读写争夺一个token,当写者得到token之后,就一直不放直到没有剩余的写者进来。而每一个读者得到token之后成为candidate(不一定就可以马上读)了就马上释放token。
这就是第二类的思想。
PV题一大类题就是第二类的思想,实际上可以更普遍化这个问题,试着写一写读者写者地位平等的代码,大家一定会受益匪浅。
--  作者:applestar
--  发布时间:12/24/2007 6:54:00 PM

--  
什么意思“想实现严格的在每一个写者到来之时如文件没被读写则下一个操作文件的一定是写者。是做不到的”


其实,写者优先要求的尽可能优先唤醒写者,主要就是看在有很多读者排在前面怎么让写者跳过去。

一些变形如无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写问题,等等,大家也可以考虑下。

关于把互斥信号看作token想法很好,可以允许互斥锁在不同进程,相同进程 传替,
还有一些需要把同步看作旋转门的集合点问题,这个近三年考得pv题都是这方面,此外
pv题还有一些设计模式值得注意,常见的“记分板”“i do it for ","传替棒 等


--  作者:buddha
--  发布时间:12/25/2007 1:12:00 PM

--  
有道理....
--  作者:EagleSoaring
--  发布时间:12/26/2007 4:26:00 PM

--  
以下是引用applestar在2007-12-24 18:54:00的发言:

一些变形如无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写问题,等等,大家也可以考虑下。

关于把互斥信号看作token想法很好,可以允许互斥锁在不同进程,相同进程 传替,
还有一些需要把同步看作旋转门的集合点问题,这个近三年考得pv题都是这方面,此外
pv题还有一些设计模式值得注意,常见的“记分板”“i do it for ","传替棒 等



-----------------------------------------------------------------------------------------------
汗,遇到高人了
能具体解释一下吗?

“把同步看作旋转门的集合点“,“记分板”“i do it for ","传替棒“,
无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写

谢谢


--  作者:buddha
--  发布时间:12/27/2007 12:59:00 PM

--  
以下是引用EagleSoaring在2007-12-26 16:26:00的发言:
[quote]以下是引用applestar在2007-12-24 18:54:00的发言:

  一些变形如无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写问题,等等,大家也可以考虑下。

  关于把互斥信号看作token想法很好,可以允许互斥锁在不同进程,相同进程 传替,
  还有一些需要把同步看作旋转门的集合点问题,这个近三年考得pv题都是这方面,此外
  pv题还有一些设计模式值得注意,常见的“记分板”“i do it for ","传替棒 等
[/quote]
-----------------------------------------------------------------------------------------------
汗,遇到高人了
能具体解释一下吗?

“把同步看作旋转门的集合点“,“记分板”“i do it for ","传替棒“,
无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写

谢谢



我也想知道哦....
--  作者:sweepthesky
--  发布时间:12/28/2007 12:34:00 PM

--  
以下是引用applestar在2007-12-24 18:54:00的发言:
什么意思“想实现严格的在每一个写者到来之时如文件没被读写则下一个操作文件的一定是写者。是做不到的”


其实,写者优先要求的尽可能优先唤醒写者,主要就是看在有很多读者排在前面怎么让写者跳过去。

一些变形如无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写问题,等等,大家也可以考虑下。

关于把互斥信号看作token想法很好,可以允许互斥锁在不同进程,相同进程 传替,
还有一些需要把同步看作旋转门的集合点问题,这个近三年考得pv题都是这方面,此外
pv题还有一些设计模式值得注意,常见的“记分板”“i do it for ","传替棒 等


我说的意思是make no assumptions to process scheduler的时候。当然PV题写起来就不考虑这个了


--  作者:sweepthesky
--  发布时间:12/28/2007 12:43:00 PM

--  
以下是引用EagleSoaring在2007-12-26 16:26:00的发言:
[quote]以下是引用applestar在2007-12-24 18:54:00的发言:

  一些变形如无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写问题,等等,大家也可以考虑下。

  关于把互斥信号看作token想法很好,可以允许互斥锁在不同进程,相同进程 传替,
  还有一些需要把同步看作旋转门的集合点问题,这个近三年考得pv题都是这方面,此外
  pv题还有一些设计模式值得注意,常见的“记分板”“i do it for ","传替棒 等
[/quote]
-----------------------------------------------------------------------------------------------
汗,遇到高人了
能具体解释一下吗?

“把同步看作旋转门的集合点“,“记分板”“i do it for ","传替棒“,
无饥饿的第一类读写,并发的'"写者"优先,以及三类不同的优先级的读写

谢谢


把同步看成集合点的意思实际上就是并行计算中的barrier。是指多个进程要共同执行到某个语句后才能一起往下走的意思。
记分板应该是说有多个整形变量,用一个mutex保护起来,然后case操作。
i do it for估计楼上是想写i'll do it for you。思想是同步其他进程时,要注意在自己的mutex仍在手上时把刚才同步的信号量引起的整型变量变化一并处理掉,不然就会错误。这个可以到这个地址去下一篇文章http://cs.rit.edu/~kar/papers
传递棒的意思就是在一些问题中如果一个mutex不是总能马上释放的话,可以在一个V操作后就噶然停止。就相当于原来属于自己的那个mutex交给了自己刚V的那个进程。
无饥饿的第一类读写实际上实现起来并发度不会很高,思想是在每个读者写者的第一步都要争夺一个互斥信号量并持有它直到自己能参与文件的竞争。
三类不同优先级的读写建议大家都想想,思想是用两级信号量。不过优先级如果超过3层了,我暂时还没想到怎么解决。可能用局部变量合整体队列结合能解决但是效率注定不高。


--  作者:applestar
--  发布时间:12/29/2007 3:28:00 PM

--  
回答的很充分!
因为最近比较忙,所以暂时没有时间写过详细的总结和实现
总的说pv设计跟程序设计一样是一门艺术。大家多看看论文
与有关书籍吧。值得指出的是pv问题在生活中很常见,到处都是
但基本上都是基本模型的拓展变形,或者组合,抓住本质就行了


--  作者:peterhertz
--  发布时间:1/17/2008 3:30:00 PM

--  
P-V操作题怎么这么难,跟汇编式的,尽是不容易想到的招,那本信号量的pdf小书倒是非常好,可惜从头看到尾吃透怕要花不少时间
--  作者:yyc0424
--  发布时间:10/16/2008 11:01:00 AM

--  
什么意思啊,看不懂
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
15,248.050ms