以文本方式查看主题 - 中文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));读者之间不互斥; 阻塞分析:当有写者在写时,其余写者阻塞在write上,第一个读者阻塞在read上,其他的读者堵塞在mutex3上。当一个写者写完后,若有写者等待,则唤醒一个写者,否则唤醒第一个读者,由第一个读者唤醒其余读者。 这里的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) 读 |
-- 作者:albani -- 发布时间:12/13/2007 11:10:00 PM --
这样感觉问题不是太大,但是好像没有充分体现写者优先,例如,现在有一写者在写,来了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 任一写者:
[此贴子已经被作者于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想法很好,可以允许互斥锁在不同进程,相同进程 传替, |
-- 作者:buddha -- 发布时间:12/25/2007 1:12:00 PM -- 有道理.... |
-- 作者:EagleSoaring -- 发布时间:12/26/2007 4:26:00 PM --
----------------------------------------------------------------------------------------------- 汗,遇到高人了 能具体解释一下吗? “把同步看作旋转门的集合点“,“记分板”“i do it for ","传替棒“, 谢谢 |
-- 作者:buddha -- 发布时间:12/27/2007 12:59:00 PM --
我也想知道哦.... |
-- 作者:sweepthesky -- 发布时间:12/28/2007 12:34:00 PM --
我说的意思是make no assumptions to process scheduler的时候。当然PV题写起来就不考虑这个了 |
-- 作者:sweepthesky -- 发布时间:12/28/2007 12:43:00 PM --
把同步看成集合点的意思实际上就是并行计算中的barrier。是指多个进程要共同执行到某个语句后才能一起往下走的意思。 |
-- 作者: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 |