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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 北大必考题，PV操作中的疑惑。。。 ◇查看新帖 ◇ 用户列表 ◇

      发表一个新主题  发表一个新投票  回复主题  (订阅本版) 您是本帖的第 20134 个阅读者浏览上一篇主题  刷新本主题   树形显示贴子　浏览下一篇主题
     * 贴子主题： 北大必考题，PV操作中的疑惑。。。 举报  打印  推荐  IE收藏夹 
       本主题类别:     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客楼主
    发贴心情 北大必考题，PV操作中的疑惑。。。

    对设置同步信号量，那位牛人能给点经验啊！
    题：某系统如此定义p,v操作：
        p(s)
             s=s-1;
             若s<0，本进程进入s信号量等待队列的末尾；否则，继续执行。
       v(s)
            s=s+1;
            若s>=0,释放等待队列中末尾的进程，否则，继续执行。
    现有4个进程p1,p2,p3,p4竞争使用某一个互斥资源（每个进程可能反复使用多次），试用上面的定义的p,v操作正确解决p1,p2,p3,p4对该互斥资源的使用问题。

       收藏   分享  
    顶(0)
      




    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第2楼
    发贴心情 
    恩这个定义有问题。你的疑惑是啥？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/22 23:11:00
     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客第3楼
    发贴心情 
    以下是引用Supremgoooo在2006-9-22 23:11:00的发言：
    恩这个定义有问题。你的疑惑是啥？


    对，作者在定义v(s)时好像有问题。
       v(s)
            s=s+1;
            若s>=0,释放等待队列中末尾的进程，否则，继续执行。
    其中s>=0是不是应该是s<=0，如果是这样的话，该题就成为《操作系统》教材第一版第四章的37题（P139），这道题可以用层层加锁或二叉树的方式来实现互斥。且二叉树的方式效率较高。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/23 7:24:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第4楼
    发贴心情 
    不好意思。。。我太粗心了！
    因为我对pv操作很是模糊，就是说小弟我对pv程序设计没有信心啊！
    上述的的确应该更正!!!!!!! 谢谢啦！
         v(s)
          s=s+1;
         若s<=0,释放等待队列中末尾的进程，否则继续执行。

    对不起大家了。。：P

    我的问题是：(a),在本题v（s）操作中，若s依然<0，那么按照定义还要释放等待队列吗？？？？？
    s<0不就是说明，已经没有可用资源了吗？那么释放进程有什么意义呢？

    (b),难道这题的解法是这样的？？？：

        pi: (i=1or2or3or4)
                 while(1)
                         { p(s);
                            使用资源。
                           v(s);
                         }

    难道是仅此而已，如此简单，不会吧！！！还是怎么解法呢？

    希望牛人能给点建议，小弟不胜感激啊!
    但愿我的问题没有让您感到可爱。。。：p

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/23 19:15:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第5楼
    发贴心情 
    当信号量s>0可以理解为可用资源数为s ;当s<0时，说明此时等待队列中有|s|个进程。
    一个进程结束时，会释放它所占用的一个资源。
    此时，
    若s<0(即s+1<=0),则说明等待队列中有|s|个进程在等待，于是从取队列中第一个进程，并将释放的资源分配给这个进程；
    反之，若s>=0，则表明无进程在等待资源，即所有进程均获得所需资源。故什么都不用做。
    不知道我说明白了没有。
    ps:很久没看操作系统了，感觉那个题目的解法没有大问题。
    请大家指教。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/23 22:56:00
     
     Supremgoooo 帅哥哟，离线，有人找我吗？
      
      
      等级：大四下学期(考上研究生啦!)
      文章：201
      积分：1872
      门派：XML.ORG.CN
      注册：2006/4/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第6楼
    发贴心情 
    （a）要。你要明白s<0的意义，表示有|s|+1个进程被阻塞，所以需要唤醒其中的一个。

    （b）可以。但是这样会出现先到进程的饥饿（STARVATION），算法不合理。本题有两种比较好的解法：漏斗法和倒二叉树法，前者比较难理解，我介绍一下后者：

    思想：因为这个定义对两个互斥进程是没问题的，所以把4个互斥进称变成两两互斥。即将4个进程分成两组，然后引入两个虚资源，每组进程为了争夺互斥资源，必须先得到虚资源。

    semaphore s;       //初值为1
    semaphore vs1;    //初值为1
    semaphore vs2;    //初值为1

    void Proc_P1_P2()
    {
    L:   P(vs1);
         P(s);
         Do sth...
         V(s);
         V(vs1);
         goto L;
    }

    void Proc_P3_P4()
    {
    L:   P(vs2);
         P(s);
         Do sth...
         V(s);
         V(vs2);
         goto L;
    }

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/23 23:04:00
     
     yangling_1985 帅哥哟，离线，有人找我吗？
      
      
      等级：大三(研究MFC有点眉目了!)
      文章：63
      积分：507
      门派：XML.ORG.CN
      注册：2006/4/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给yangling_1985发送一个短消息 把yangling_1985加入好友 查看yangling_1985的个人资料 搜索yangling_1985在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看yangling_1985的博客第7楼
    发贴心情 
    以下是引用Supremgoooo在2006-9-23 23:04:00的发言：
    （a）要。你要明白s<0的意义，表示有|s|+1个进程被阻塞，所以需要唤醒其中的一个。


    我觉得当s<0时应该是表示有|s|个进程阻塞吧。
    设初始状态是所有已申请资源的进程都获得资源且所有资源均已分配（S初值为0），N为阻塞的进程数（初值为0）
    每当有一个新的进程申请资源时(P(S)) ,S=S-1，且进入阻塞队列。同时N=N+1.
    当有一进程运行结束，则（v(s)) s=s+1.同时 从等待队列中取出一个进程。N=N-1
    设次过程中始终有等待进程，则可得出N=|S|。

    SUPREMGOOOO兄中的S是不是指在V(S)中以自加一次的S?

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

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

    是不是还会早成同一组里的早到进程的饥饿呢?

    比如两个队列:

    vs1:2,3,4,5,....
    vs2:12,13,14,15.....
    s:11
    runing :1
    代号代表到达的先后顺序.

    为什么不是每个类型的进程自己一个队列呢?
    这样似乎等待的队列还会更短一些.


    其实,我不知道这个题到底要考察什么?

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/24 10:49:00
     
     apolor 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(汇编考了97分!)
      文章：39
      积分：382
      门派：XML.ORG.CN
      注册：2006/9/10

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给apolor发送一个短消息 把apolor加入好友 查看apolor的个人资料 搜索apolor在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看apolor的博客第9楼
    发贴心情 
    以下是引用Supremgoooo在2006-9-23 23:04:00的发言：
    （b）可以。但是这样会出现先到进程的饥饿（STARVATION），算法不合理。本题有两种比较好的解法：漏斗法和倒二叉树法，前者比较难理解，我介绍一下后者：

    思想：因为这个定义对两个互斥进程是没问题的，所以把4个互斥进称变成两两互斥。即将4个进程分成两组，然后引入两个虚资源，每组进程为了争夺互斥资源，必须先得到虚资源。

    semaphore s;       //初值为1
    semaphore vs1;    //初值为1
    semaphore vs2;    //初值为1

    void Proc_P1_P2()
    {
    L:   P(vs1);
          P(s);
          Do sth...
          V(s);
          V(vs1);
          goto L;
    }

    void Proc_P3_P4()
    {
    L:   P(vs2);
          P(s);
          Do sth...
          V(s);
          V(vs2);
          goto L;
    }



    利用倒立二叉树来实现互斥，效率较高。虽然不会发生饥饿，但有个小问题：如果进程申请使用资源的次序为P1、P2、P3、P4，而实际使用临界资源的次序可能为：P1、P3、P2、P4。

    下面介绍一个层层加锁的方式实现的互斥，就当拓展一下思路吧。该实现效率很低，每层只锁住一个进程。
    semaphore mutex1=1;
    semaphore mutex2=2;
    semaphore mutex3=3;

    Proc(i){
        while(true){
              P(mutex3);
              P(mutex2);
              P(mutex1);
                  do sth...
              V(mutex1);
              V(mutex2);
              V(mutex3);
        }
    }

    另外，Supremgoooo能否把提到的“漏斗法”实现贴上来，开阔一下眼界:)

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/9/24 15:23:00
     
     borlong 帅哥哟，离线，有人找我吗？魔羯座1986-12-30
      
      
      等级：大三(面向对象是个好东东!)
      文章：106
      积分：519
      门派：XML.ORG.CN
      注册：2006/6/26

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给borlong发送一个短消息 把borlong加入好友 查看borlong的个人资料 搜索borlong在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看borlong的博客第10楼
    发贴心情 
    小弟在此谢过大家了。

    Brother  supremgoooo :您说，可以。但是这样会出现先到进程的饥饿（STARVATION），算法不合理。本题有两种比较好的解法：漏斗法和倒二叉树法。

    您能否解释下，饥饿的过程呢？ 就是简要说明一下，如何饥饿的。
    因为小弟正在努力尝试着去想象 pv操作过程。这个不像一般的程序设计，还要考虑“次序”问题。我对这方面甚是迷惑！

    您能否将“漏斗法”也贴出来呢？让我仔细思考一下其中的奥妙呢。
    您的os书本是什么教材啊？怎么这么丰富呢？北大的os上没有你说的方法啊！
    麻烦您了啊！ 谢谢啦！ ：P

    在此感谢大家对小弟的关心和帮助！

    ----------------------------------------------
    落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

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

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

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