计算机科学论坛--写者优先和红黑客过河

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

这样才能体现写着优先阿，如果设成READING，则下一个先来的是写者怎么办？

这个算法写成这样我认为已经可以了。但是它确实还存在很多不合理的地方，如你说的这个问题。还有另外的问题：sta的初值应该为什么？

其实可以解决这些问题，让这个算法变得对读者更合理一些。如设3个状态：当没有人时状态：IDLE，它可以接受读者或写者。那样边界的处理显得麻烦一些，而且更容易出错。如果你感兴趣，可以写一个更完美的算法：）

这个算法关键是表达一种思想，当思想已经很好被表达出且它不错时，我认为已经完成了95%的工作。从爱好者的角度当然期待有100%的优秀算法。

btw：这个算法思想的原创人我认为是Dekker,1965,当时他曾用这种状态标志解决了两个进程的互斥（软件解法）。Dekker算法的缺点是它不能推广到一般，即2个进程可以，3个就麻烦些，。。n个就几乎不可以了。所以这个算法是不能对n个优先级队列进行处理的。斯大林书中的算法容易推广到n个优先队列，但是它对2个队列的处理显然没有Dekker算法好。所以我建议，对于2个队列，用Dekker算法，多个队列可以选择斯大林算法。当然对长安街那道题如果用斯大林算法则显得失去了讨论的价值。

以下是引用buddha在2006-10-28 15:14:00的发言：
感觉还是不懂,好象carroty谈到的问题还没解决
"if(rwait>0) sta=READING
在写者执行完后,如果没有读等待,则sta==Writing.
如果过会过来一个读进程,此时根据sta应该等待,而实际应该运行,此时必须需要来一个写进程重新激活读进程.这显然是不合理的."
为什么不保留carroty原来改的直接将sta=READING呢,这时rc的值为0,写者来了可以写,读者来了也可以读,否则,如果写者执行完了,没有读等待,sta=writing(这里只是状态,而并不代表真的是存在写进程执行),则后面到来的读者永远打破不了sta=writing的局面,造成读者来到后也不能够执行.

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

认真看完了，思想没问题。

边界处理还有点小问题：
（1）status的修改还不太完善，有些地方漏了。
（2）waitcount和count的使用还有问题，主要是领导处。

btw：看来你已经基本掌握这个算法了。呵呵!感觉如何？很难写对吧？我看了两个版本的北大助教写的这个算法，都是有些问题。这个算法考的可能性很小，因为一时半会确实很难写对！

以下是引用carroty在2006-10-25 15:24:00的发言：
修改了一下过街的这个:
普通人:
p(mutex)
if(status==LEADER||status==GUARD)
     nwait++;    //normal wait queue
     v(mutex)
     p(nw);
else
     nc++;
     v(mutex);
过街....
p(mutex)
nc--;
if(nc==0&&status==GUARD)
     v(gw);
else if(nc==0&&status==LEADER)
     while(lwait){
         v(lw);
         lwait--;
         lc++;
     }
v(mutex);
领导:
p(mutex)
if(status==GUARD)
     lwait++;
     v(mutex);
     p(lw);
else if(status==NORM){
     status=LEADER;        //rob the status
     lwait++;
     v(mutex);
     p(lw);
else
     lc++;
     v(mutex);
...
过街...
...
p(mutex);
lc--;
if(lc==0&&status==GUARD){
     v(gw);
}else if(lc==0){    //leader passed and no guard require return to NORM;
     status=NORM;
     while(nwait){
         v(nw);
         nc++;
         nwait--;
     }
}
v(mutex);
国旗队(guard):
p(mutex);
if(status!=GUARD){
     status=GUARD;
     v(mutex);
     p(gw);
}else
     v(mutex);
延迟....等待其他占用人都通过...
...
通过...
...
p(mutex);
if(lwait>0){
     status=LEADER;
     while(lwait){
         v(lw);
         lwait--;
         lc++;
     }
}else{    //return to norm
     status=NORM;
     while(nwait){
         v(nw);
         nwait--;
         nc++;
     }
}
v(mutex);

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

以下是引用Supremgoooo在2006-10-28 21:28:00的发言：
这样才能体现写着优先阿，如果设成READING，则下一个先来的是写者怎么办？

这个算法写成这样我认为已经可以了。但是它确实还存在很多不合理的地方，如你说的这个问题。还有另外的问题：sta的初值应该为什么？

这个算法关键是表达一种思想，当思想已经很好被表达出且它不错时，我认为已经完成了95%的工作。从爱好者的角度当然期待有100%的优秀算法。

[quote]以下是引用buddha在2006-10-28 15:14:00的发言：
感觉还是不懂,好象carroty谈到的问题还没解决
  "if(rwait>0) sta=READING
  在写者执行完后,如果没有读等待,则sta==Writing.
  如果过会过来一个读进程,此时根据sta应该等待,而实际应该运行,此时必须需要来一个写进程重新激活读进程.这显然是不合理的."
  为什么不保留carroty原来改的直接将sta=READING呢,这时rc的值为0,写者来了可以写,读者来了也可以读,否则,如果写者执行完了,没有读等待,sta=writing(这里只是状态,而并不代表真的是存在写进程执行),则后面到来的读者永远打破不了sta=writing的局面,造成读者来到后也不能够执行.
[/quote]

个人的观点认为,sta只是表示执行的状态,如果将sta改为writing,但此时的rc值为0,而且状态为reading,并不满足if(rc>0||sta==WRITING)因此如果下一个来的是写者,可以进行写操作.而且,我觉得在写和读的过程中应该自动包含状态的改变.即状态可以改为writing,然后会继续后面的操作.
是不是有点抠的太细了呢，不过我觉得，在思考的过程中才会加深理解

姓名：(无权查看)
城市：(无权查看)
院校：(无权查看)

还是stalling的算法比较完美，我想讨论一下rqueue信号量的作用。

writer:
p(wmutex);
wcount++;
if(wcount==1)
p(read);
v(wmutex);
p(write); //put the mutex write here to ensure the p(read) being execute;
.....
writing;
.....
v(write);
p(wmutex);
wcount--;
if(wcount==0)
v(read);
v(wmutex);

reader:
p(rqueue);
p(read); /*若此时有写者在等，则第一个reader等在read信号量上，后续reader等在rqueue信号量上。read队列中的等待的读者是如果没有rqueue的话，会有很多reader等在read上，则写者必须排在它们后面，不能优先了。若只有read信号量，一个写者在写，后续读者等在read，写完后，read中的读者进程被一个一个释放出来，在释放过程中如果有写者来了，则写者等在read上，这时按要求应立即停止对read队列的释放，但此时不能满足这个要求。有了rqueue，则任意实刻read中只有一个读者等待，释放了它后它再释放rqueue中的读者，刚被释放的读者的第一个动作是p(read),在释放过程中如果来了一个写者，则下一个从rqueue中释放的读者立即等在read中而不会继续释放其他的等待读者。*/
p(rmutex);
rcount++;
if(rcount==1)
p(write);//此时必定无写者等待，第一个reader对写行为上锁，保证这次读操作不被打断
v(rmutex);
v(read);
v(rqueue);
.....
reading...
.....
p(rmutex);
rcount--;
if(rcount==0)
v(write);
v(rmutex);


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