新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚
   XML论坛     W3CHINA.ORG讨论区     计算机科学论坛     SOAChina论坛     Blog     开放翻译计划     新浪微博  
 
  • 首页
  • 登录
  • 注册
  • 软件下载
  • 资料下载
  • 核心成员
  • 帮助
    		•   Add to Google

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 中文XML论坛 - 专业的XML技术讨论区 → 计算机理论与工程 → 『 计算机考研交流 』 → 写者优先和红黑客过河 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 32414 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 写者优先和红黑客过河 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客楼主
    发贴心情 写者优先和红黑客过河

    写者优先，条件为：
    （1）多个读者可以同时进行读；
    （2）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；
    （3）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。
    我写的算法：
    void Reader()
    {
    　　P(mutex);
    　　if(wwait>0||sta==WRITING) //有写者等或有写者写
    　　{
    　　　　rwait++;
    　　　　V(mutex);
    　　　　P(rw);
    　　}
    　　else
    　　{
    　　　　rc++;
    　　　　V(mutex);
    　　}

    　　reading....

    　　P(mutex);
    　　rc--;
    　　if(rc==0&&wwait>0) //没读者读且有写者等
    　　{
    　　　　sta=WRITING;
    　　　　wwait--;
    　　　　V(ww);
    　　}
    　　V(mutex);

    }
    /////////////////////////

    void Writer()
    {
    　　P(mutex);
    　　if(wwait>0||sta==READING) //有写者写或有读者读
    　　{
    　　　　wwait++;
    　　　　V(mutex);
    　　　　P(ww);
    　　}
    　　else V(mutex);

    　　writing....

    　　P(mutex);
    　　if(wwait>0) //有写者等
    　　{
    　　　　wwait--;
    　　　　V(ww);
    　　}
    　　else
    　　{
    　　　　if(rwait>0) sta=READING; //没写者等且有读者等
    　　　　for(;rwait>0;rwait--)
    　　　　{
    　　　　　　rc++;
    　　　　　　V(rw);
    　　　　}
    　　}
    　　V(mutex);
    }
    变量初值：
    ｒｗａｉｔ＝ｗｗａｉｔ＝０；／／表示等待的读者写者人数
    ｒｃ＝０；／／表示正在读的人数
    信号量初值：
    ｗｗ＝ｒｗ＝０；／／表示等待的写者和读者
    ｍｕｔｅｘ＝１；／／互斥资源保护

    总结：二类读写模型用来实现队列之间的优先级，狒狒过河模型用来实现队列之间的平级。Ｐ，Ｖ模型不能实现先来先服务。凡是历年考题中提到的“先来先服务”都可以视而不见。

    思考题：
    北京的长安街是中国最重要的地方，党中央办公处，天安门，人民大会堂都在这条街上。天安门每天都要接待大批的游客，人民大会堂时常举行重要会议。为保证大型的政治会议正常召开，避免参会官员们在路上耽误时间，现规定，当开会或散会等高峰时期，对长安街上的车辆进行限制措施，群众车辆要避让领导车辆。为简化问题，现假设群众车辆需要等待领导车辆过后方能行使。然而，每天傍晚时分，伴随着落日，天安门国旗班要举行降旗仪式，国旗班全体战士需要正步横穿长安街，此时领导的车辆也需要等待。编写程序，适用Ｐ，Ｖ原语实现上述同步互斥问题，要求不能出现死锁和饥饿。


       收藏   分享  
    顶(0)
      




    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/22 20:39:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第2楼
    发贴心情 
    红黑客过河问题的两种思路：
    （１）来一个人，检查他，如果船上有２红１黑他是红客，则阻塞他，否则他就上船；如果船上有２黑１红他是黑客，则阻塞他，否则他就上船。

    （２）有鸽巢原理可以得到：任意５个人中必有４个人，他们满足开船的条件，所以每到５个人，检查一下，让其中的４个人过河。

    评价：
    （１）不好，原因是某一时刻，如果船上２红１黑，而接下来很大时间内来的都是红客，则有很多人要等待，因为红客不能上船。所以第一个算法会造成多人等待的现象。所以该算法不能得满分。

    （２）好，至多有１人等待。该算法可以得满分。

    对（２）的改进：４各人中也可能满足过河条件，所以４个人时就检查一下。但是代码量增加。出错率增加。不建议。

    对（２）改进，红黑客算法不必要分开写，用ｇｅｔ＿ｐｅｒｓｏｎ＿ｃｏｌｏｒ（）函数得到颜色，使代码简化许多。这个改进很不错！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/22 20:55:00
     
     buddha 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(每天看1小时莱昂氏)
      文章：164
      积分：1022
      门派：XML.ORG.CN
      注册：2006/5/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给buddha发送一个短消息 把buddha加入好友 查看buddha的个人资料 搜索buddha在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看buddha的博客第3楼
    发贴心情 
    关于上面的读者写者问题
    "if(wwait>0||sta==READING) //有写者写或有读者读"
    这里不太明白,如果有写者在写按道理说应该是sta==WRITING吧~
    如果要用wwait>0来表示的话,在写者函数中,wwait>0就只能有三种情况1,有读者在读,2,有写者在写,3,无读者在读但有写者在等.当然,第三种情况在读者函数末尾已经给解决掉了,即置sta=WRITING,变成了第2种情况,因此就剩1,2两种情况的存在,那么,只要wwait>0就可以说明1或2 种情况的存在,直接用"if(wwait>0) "就可以说明有写者写或有读者读了吧.
    刚开始看PV,有些东西拿不大准,还请高手赐教~
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/23 15:18:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第4楼
    发贴心情 
    buddha：
    你看到了问题，但是还没看全。再想下，看你能否改正它：）
    carroty：
    写者优先跟红黑客没关系，我这里写的是两贴。
    你注意写者优先的条件，按照这个条件，前面贴子里讨论的算法都不是写者优先，因为它们都没有实现写者优先的条件。
    我给的思考题是模仿10年前的某年北大真题编的，那个题是有史以来最难的一道P，V题。你想做它前理解我写的写者优先算法。

    写者优先算法的条件：
    （1）多个读者可以同时进行读；
    （2）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；
    （3）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。
    由Courtois在1971年提出，他同时给出了算法，思想就是我上面写的程序。这个思想也是北大教学的主流思想。

    写者优先算法是P，V中最难的一个问题，上面这个思想是我所见过的唯一实现这三个条件的算法。由于这个思想太过复杂，即便理解了也很难一次写对，我上面的这个算法就有一点小问题，buddha已经快发现了。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/24 22:28:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第5楼
    发贴心情 
    1),首先,想弄明白一个问题,读者优先跟写者优先本质上来讲是不是:优先运行的进程是否需要互斥.以及低级的进程是不是互斥.(因为读者是可以共享的,写者是要互斥的,这也造成读者优先的算法比较简单),是不是这样的呢?

    2),回到长安街的这个题,是不是要把街做为临界区,按照优先级:
    群众:可以共享
    领导:可以共享,没有说领导需要互斥吧?
    国旗护卫队:只有一个,当把他看做写者的时候也不需要互斥.

    这样抽象对吧?不过我好象明白的问题所在了....

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 10:16:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第6楼
    发贴心情 
    我想我看出一些问题来了:
    写者最后这行,
    if(rwait>0) sta=READING
    在写者执行完后,如果没有读等待,则sta==Writing.
    如果过会过来一个读进程,此时根据sta应该等待,而实际应该运行,此时必须需要来一个写进程重新激活读进程.这显然是不合理的.

    做两处修改:
    void Reader()
    {
    　　P(mutex);
    　　if(wwait>0||sta==WRITING) //有写者等或有写者写
    　　{
    　　　　rwait++;
    　　　　V(mutex);
    　　　　P(rw);
    　　}
    　　else
    　　{
    　　　　rc++;
    　　　　V(mutex);
    　　}

    　　reading....

    　　P(mutex);
    　　rc--;
    　　if(rc==0&&wwait>0) //没读者读且有写者等
    　　{
    　　　　sta=WRITING;
    　　　　wwait--;
    　　　　V(ww);
    　　}
    　　V(mutex);

    }
    /////////////////////////

    void Writer()
    {
    　　P(mutex);
    　　if(wwait>0||rc>0)//sta==READING) //有写者写或有读者读
    　　{
    　　　　wwait++;
    　　　　V(mutex);
    　　　　P(ww);
    　　}
    　　else V(mutex);

    　　writing....

    　　P(mutex);
    　　if(wwait>0) //有写者等
    　　{
    　　　　wwait--;
    　　　　V(ww);
    　　}
    　　else
    　　{
    　　　　sta=READING; //没写者等且有读者等
    　　　　for(;rwait>0;rwait--)
    　　　　{
    　　　　　　rc++;
    　　　　　　V(rw);
    　　　　}
    　　}
    　　V(mutex);
    }

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 14:38:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第7楼
    发贴心情 
    这个是stalling那本书上的写者优先的算法,很巧妙:
    //注释是我自己加的.

    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); //put read here to ensure if p(read) by writer then no reader can enter the next section
    p(rmutex);
    rcount++;
    if(rcount==1)
     p(write);
    v(rmutex);
    v(read);
    v(rqueue);
    .....
    reading...
    .....
    p(rmutex);
    rcount--;
    if(rcount==0)
     v(write);
    v(rmutex);

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 14:45:00
     
     carroty 帅哥哟，离线，有人找我吗？
      
      
      等级：大四(GRE考了1600分!)
      文章：153
      积分：1257
      门派：IEEE.ORG.CN
      注册：2006/4/4

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第8楼
    发贴心情 
    修改了一下过街的这个:

    普通人:
    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);

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 15:24:00
     
     youngyt 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：3
      积分：68
      门派：XML.ORG.CN
      注册：2005/4/8

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给youngyt发送一个短消息 把youngyt加入好友 查看youngyt的个人资料 搜索youngyt在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看youngyt的博客第9楼
    发贴心情 
    关于这个解法我有一个问题：
    写者靠p(read)阻挡后面的读者，但是如果没有写者的话，那多个读者p(read)不就阻塞了吗？
    我稍微改了一下，请看看是否正确

    reader:
    p(rqueue);

    p(wmutex);
    if (wcount >0) then p(read);
    v(wmutex);

    p(rmutex);
    rcount++;
    if(rcount==1)
      p(write);
    v(rmutex);
    v(read);
    v(rqueue);
    .....
    reading...
    .....
    p(rmutex);
    rcount--;
    if(rcount==0)
      v(write);
    v(rmutex);


    以下是引用carroty在2006-10-25 14:45:00的发言：
    这个是stalling那本书上的写者优先的算法,很巧妙:
    //注释是我自己加的.

    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); //put read here to ensure if p(read) by writer then no reader can enter the next section
    p(rmutex);
    rcount++;
    if(rcount==1)
      p(write);
    v(rmutex);
    v(read);
    v(rqueue);
    .....
    reading...
    .....
    p(rmutex);
    rcount--;
    if(rcount==0)
      v(write);
    v(rmutex);



    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 21:39:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第10楼
    发贴心情 
    首先，我认为读者优先和写者优先不是同一性质的问题。它们两个的差别在于问题本身的描述:
    读者优先说道：“当读者到时，如果有读者正在读，则它就进。”但是如果没有读者正在读，它和写者具有相同的优先级，就是说读者的优先级只有在有读者正在读时才高于写者。在有些时候，该模型中的读者，写者之间是公平的，即写者的不公平是隐含的，相对的。

    写者优先说：“一旦有写者到，后来的读者绝对不能优先于这个写者。”这里问题中，写者的优先性是绝对的，任何时候，它都有比读者高的优先级。。。。所以它更像一个强实时算法，它不允许读者丝毫的优势。这也是我说其它算法不是真正的写者优先的原因，其它算法都隐含着这样一个事实：偶尔情况下读者可能优先于写者。

    长安街这个问题显然是一个写者优先的例子，在任何情况下，绝对不允许下级队列中的进程优先于上级队列中的进程。


    我写的算法虽然有问题，但是思想已经表达出来了。按照这个算法的思想，应该可以分析出其它算法的缺点。


    以下是引用carroty在2006-10-25 10:16:00的发言：
    1),首先,想弄明白一个问题,读者优先跟写者优先本质上来讲是不是:优先运行的进程是否需要互斥.以及低级的进程是不是互斥.(因为读者是可以共享的,写者是要互斥的,这也造成读者优先的算法比较简单),是不是这样的呢?

    2),回到长安街的这个题,是不是要把街做为临界区,按照优先级:
    群众:可以共享
    领导:可以共享,没有说领导需要互斥吧?
    国旗护卫队:只有一个,当把他看做写者的时候也不需要互斥.

    这样抽象对吧?不过我好象明白的问题所在了....



    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/10/25 23:06:00
     
     GoogleAdSense
      
      
      等级：大一新生
      文章：1
      积分：50
      门派：无门无派
      院校：未填写
      注册：2007-01-01
    给Google AdSense发送一个短消息 把Google AdSense加入好友 查看Google AdSense的个人资料 搜索Google AdSense在『 计算机考研交流 』 的所有贴子 访问Google AdSense的主页 引用回复这个贴子 回复这个贴子 查看Google AdSense的博客广告
    2024/5/29 10:48:28

    本主题贴数24，分页： [1] [2] [3]

    管理选项： 修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告
    W3C Contributing Supporter! W 3 C h i n a ( since 2003 ) 旗 下 站 点
    苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
    		 2,492.188ms