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

    >> 研友的交流园地，讨论关于计算机考研的方方面面。
    [返回] 计算机科学论坛 → 计算机理论与工程 → 『 计算机考研交流 』 → 另一个P,V难问题 ◇查看新帖 ◇ 用户列表 ◇

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

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

    在一个os实验室里有人数确定的若干名导师和若干名学生，导师都想尽量的多完成一些项目，为达到此目的并且配合学校的政策，做如下规定：
    （1）实验室所有项目的总数是一个固定的常数；
    （2）一个导师接到一个项目后，必须给每个学生都分配一些任务；
    （3）必须所有学生都完成了所给的任务后，一个项目才能完成；
    （4）一名导师一次只能申请一个项目；
    （5）实验室的项目依次编号，一个学生拿到i号项目当且仅当先完成t号（t<i）项目；
    编写P，V程序，正确实现上述问题，要求不能出现死锁和饥饿。

       收藏   分享  
    顶(0)
      




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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第2楼
    发贴心情 
    这似乎是个多对多的同步问题;
    我考虑的问题:学生做项目时,是保持一个大体的同步(也就是在所有学生都完成项目i后才分配下一个项目),这样实现比较容易.

    但是我选择,让每个学生尽力发挥,完成早的可以进入下一个项目.如果下一个项目还没有来,则等待下一项目,这样似乎不好.再想想...

    leader:

    p(limit);
    jobid=getjob();        
    for(int i=1;i<=N;i++){
        p(mutex1);    // mutex for assignjob
        assignjob(jobid,i);        //assign job jobid to i student
        v(student[i]);        //send message to student[i];
        v(mutex1);
    }    
    p(finished);
    v(limit);
        
    students(i)
    {
        int jobid;
        
        while(1){
        jobid=student_job[i];
        p(student[i]);
        p(mutex1);
        while(!getjob(jobid));
        v(mutex1);
        dojob(student_job[i]);
        p(mutex);
        student_status[i]==DONE;
        int j=1;
        while(j<=n&&
        ((student_status[j]==DONE&&student_job[j]==jobid)||(student_job[j]>jobid)))
        {
            j++;
        }
        if(j>=n){
            v(finished);
        }
        student_job[i]++;    // to do next job
        v(mutex);
        }
    }

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第3楼
    发贴心情 
    这个问题是陈老师所说的“P，V三大难问题”中的一个。

    你理解上还有些偏差。
    提示：这是一个生产-消费问题。

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/2 12:37:00
     
     ychj 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：58
      积分：440
      门派：XML.ORG.CN
      注册：2006/8/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给ychj发送一个短消息 把ychj加入好友 查看ychj的个人资料 搜索ychj在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看ychj的博客第4楼
    发贴心情 
    这个问题似乎并不太难，今晚花点时间搞定，呵呵。
    对了，陈老师说的"PV三大难问题"，是哪三个？
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/2 21:27:00
     
     ychj 帅哥哟，离线，有人找我吗？
      
      
      等级：大二期末(C++考了100分!)
      文章：58
      积分：440
      门派：XML.ORG.CN
      注册：2006/8/9

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给ychj发送一个短消息 把ychj加入好友 查看ychj的个人资料 搜索ychj在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看ychj的博客第5楼
    发贴心情 
    今晚花了点时间做了一下。
    其实这道题目是生产者-消费者问题中的一个问题的变种,但是相对简单些。
    具体解答我就不给出了,大家想想应该都没问题的。
    主要注意以下几点:
    (1) 对于结构在PV操作题目中的使用;
    (2) 具体到这道题目，当资源结束时，注意用Exit退出程序，以免死锁;
    carroty仁兄给出的算法在理解上错误,并且招法有问题,不过没关系,好好操练操练就可以了,赫赫。
    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/3 1:11:00
     
     DavidPotter 帅哥哟，离线，有人找我吗？
      
      
      等级：大三暑假(ITELS考了6.5分!)
      文章：150
      积分：852
      门派：Lilybbs.net
      注册：2006/3/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给DavidPotter发送一个短消息 把DavidPotter加入好友 查看DavidPotter的个人资料 搜索DavidPotter在『 计算机考研交流 』 的所有贴子 点击这里发送电邮给DavidPotter 引用回复这个贴子 回复这个贴子 查看DavidPotter的博客第6楼
    发贴心情 
    我感觉和那个生产者一次生产m个，消费者一次一个类似。对吗？

    ----------------------------------------------
    Don‘t try so hard, the best things come when you least expect them to.

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第7楼
    发贴心情 
    今天看了操作系统课后的一道题,就是哪个多进程对多进程发消息的那个,应该跟这个题是一个原型,并且,条件似乎更弱一些.

    重写了一下:

    int index=0;
    semaphore pnum=M,mutex=1,ready[M]={0...0},teacher_wait[L]={0....0};
    int count[M]={0...0};
    //pnum表示总任务数，count[i]为i所代表的的任务的完成情况，ready[i]表示i所表示的项目的情况；

    teacher:
    while(1){
        p(pnum);
        p(mutex);
        建立项目index;
        index1=index%M;//M是最大项目数，这里取模
        count[index1]=n;//n为学生数
        v(ready[index1]);
        index++;
        v(mutex);
        p(teacher_wait[k1];
    }

    student k:
    int j=0;
    while(1){
        p(ready[j]);
        p(mutex);
        取自己在项目j中的任务，完成之...;
        j1=j%M;
        count[j1]--;
        if(count[j1]!=0)
            v(ready[j1]);
        else
        {
            通知项目j完成;
            k1=project.teacher;//取项目对应的老师号
            v(teacher_wait[k1]);
            v(pnum);
        }
    }

    点击查看用户来源及管理<br>发贴IP：*.*.*.* 2006/11/6 23:09:00
     
     feina1 帅哥哟，离线，有人找我吗？
      
      
      等级：大一新生
      文章：1
      积分：58
      门派：XML.ORG.CN
      注册：2006/11/7

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给feina1发送一个短消息 把feina1加入好友 查看feina1的个人资料 搜索feina1在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看feina1的博客第8楼
    发贴心情 
    有一些模糊的地方，不像是简单的多对多消费者生产者问题
    消费者生产者问题的消费者是自己取任务的，而此题是老师（生产者）主动分配任务，这样任务的生产就不可避免的和学生（消费者）的状态有关了。比较麻烦
    还有，老师是分配完了才再申请项目，还是等学生都做完了再申请任务？两者做法也不同的

    对于这种不确定的情况，师兄是怎么做的呢？诚意请教，新来的，hehe

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给carroty发送一个短消息 把carroty加入好友 查看carroty的个人资料 搜索carroty在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看carroty的博客第9楼
    发贴心情 
    老师似乎只用把任务分配了就好了,学生可以自己去取自己的部分.

    而且应该注意到只能存在m个项目.如果非要写的清清楚楚,可以多用几个pv相互通知一下.

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

    姓名：(无权查看)
    城市：(无权查看)
    院校：(无权查看)
    给Supremgoooo发送一个短消息 把Supremgoooo加入好友 查看Supremgoooo的个人资料 搜索Supremgoooo在『 计算机考研交流 』 的所有贴子 引用回复这个贴子 回复这个贴子 查看Supremgoooo的博客第10楼
    发贴心情 
    feina1：老师和学生的关系就是生产者和消费者的关系，在生产者和消费者模型中，两帮人之间本来就有同步的关系，所以主动和被动存在是必然的。

    这个算法没有写者优先那么难，基本上能搞清楚它是生产-消费模型就可以解了。

    思路：把原模型的信号量变成信号量数组。carroty在7楼给的算法正确。但是表达不很清楚，我帮你修改一下：
    void Techer()
    {
    L:   P(pnum);
         get_a_project();
         P(mutex_1);
           index1=index;
           index=(index+1)%M;
         V(mutex_1);
         div_project(index1,k);
         
         V(Ready[index1])*k
         P(teacher_wait[index1])*k;
         V(pnum);
         goto L;
    }

    //////////////////////////

    void Student(int i)
    {
    L:    P(mutex_2);
              j1=index2[i];        //注意，index2是k项的数组。
              index2=(index2[i]+1)%M;
          V(mutex_2);
          P(Ready[j1]);
          Do_and_finish_it();
          V(teacher_wait[j1]);
          goto L;
    }

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

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

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