计算机科学论坛--北大必考题，PV经典案例分析。。。

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

pv操作题：
有红客和黑客两组人员需要过河。河上有船，但是每次只能乘坐4人，且每次
乘客满员时才能开船，到河对岸后空船返回。但船上乘客不能同时有
3个红客、1个黑客或者 1个红客、 3个黑客的组合。（其他组合安全）。
请编写程序，用pv操作解决红客、黑客过河的问题。
并说明所设置的信号量及其初值。

我的那充满痛苦的、郁闷的、坎坷的思路：
（怀着敬仰和焦急，请牛人们“根据小弟的思路”来分析和点拔 ^__^）

===========================================
第一步：具体编程（当作一般的程序设计）。

船上人数count=0
红客人数red=0
黑客人数black=0

red_black()
{...
  while(1)
   { if  船上人数count是4人，
          if  red!=3 或者 black!=3
               then 开船；
          else  发出警告！
     else                        //船上人数不足4人。
          等待来客。
...

     有人来了。
     if 是红客
          then  red++;
     if 是黑客
          then  black++;

船上人数count=red+black.
}
...
}
========================================
分析第一步：
当然第一步不是最终结果，而且如果试卷上写着这样，那么得分肯定是ZERO! ^___^

但是，从第一步，我可以找到某些信号量，哪些需要互斥，哪些需要同步。
因为真正的PV程序是个并发执行的，并非像上面的那样顺序执行。
所以，对red,black,count都需要互斥访问。

那么同步的呢？？？
同步在“开船上面”，即当人数符合条件时候，则开船。否则，发出错误信号。
于是，要对上面的程序进行“分离”，分离成2个并发的程序。
一个是等待客人的程序。另一个是安全检查后开船。（我的思路对吗？？？）

=========================================
第二步：
count=0 船上的人数。
s_count=1 互斥访问 count.

red=0 红客人数。
s_red=1 互斥访问 red.

black=0 黑客人数。
s_black=1 互斥访问 black.

s_wait=1 逐个检查来客的类别时，同步信号量
s_safe=0 安全检查同步信号量，人数为4的时候才能检查，检查时不准干扰

waiting()
{...
  if count<4
     then   p(s_wait);       //逐个检查是红客还是黑客
  ...
    while(1)
       {  ...

          有人来了。

         if 是红客
           then
                 p(s_red);
                   red++;
                 v(s_red);

         if 是黑客
            then
                 p(s_black);
                   black++;
                 v(s_black);

         p(s_count);
         船上人数count=red+black.
         if count=4
               then v(s_safe);            //安全检查,通知是否可以开船
         v(s_count);
        }
...
}

going()
{ ...
  p(s_safe)
  if  red!=3 或者 black!=3
             then 开船；
                  ...
                  到达了对岸，返回。
                  v(s_wait)           //继续等待客人
  else  发出警告！

}

===============================
写到这里，我的思路应该是清晰的。却不知道正确与否。
尤其是对同步信号量，我感觉是“硬塞”进去的！！！

还请牛人来指点一二啊。。。。 ^____^

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

。。。。。。
这个题是pv中最难的一个，你至少也要把读者-写者模型熟练掌握一下再来做。

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

。。。。。。
这个题是pv中最难的一个，你至少也要把读者-写者模型熟练掌握一下再来做。

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

以下是引用Supremgoooo在2006-9-29 23:09:00的发言：
。。。。。。
这个题是pv中最难的一个，你至少也要把读者-写者模型熟练掌握一下再来做。

我的解法很弱吧！！
让 dear Supremgoooo 认为我“读者-写者模型”都没有看过呢。^____^
其实，这些经典的模型，我非常的熟悉！！！
问题就在当我面临着一道pv题目时候，以前的pv知识，好像都没有学过！！
这种情况还是很少的！！除了离散和pv外！！
也不知道，还是我太笨，还是题目太怪！
总之，我拿到pv，第一，具体解法一片模糊。第二，就是做出来了，也无法检测。

苍天啊！！
我该怎么才能挣脱pv和离散图论文字证明的束缚呢？
怎样做，才能成为一个像dear Supremgoooo 和logician 这样的高手呢！！！
谁能告诉我？？？
当然，我只能默默的看书，做题去了。。。。相信，我一定有这么一天！
但愿这天在07年考研之前。。。。

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

你这个解法很有问题，基本上还是过程编程的思维，解PV题用的应该是进程的观点。这个题目跟售票员--公交车题目相似，肯定有一个进程是船，其他进程是客，分红黑两种属性。客满船开和到岸船停客下船，是一个同步关系；船上只能容四个人，是一个互斥关系，而且还加上了一定限制，你的PV不能只是检查非法情况的发生，更重要是要防止非法情况的发生。

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

学写了一个,大牛指正...

samphore mutex=1;//用于互斥访问blacknum,rednum
rmutex=1;//用于红客互斥
bmutex=1;//用语黑客互斥
int blacknum=0;rednum=0;//用语记录当前红黑客数量

void redman()
{
while(1)
{
  p(rmutex);
  p(mutex)
  if((blacknum==0&&rednum<4)||(blacknum<=2&&rednum<2))
   rednum++;
   上船；
  if(rednum>=3||blacknum==2)
   p(bmutex);
  p(mutex)
  v(rmutex);
}
}

void blackman()
{
while(1)
{
  p(bmutex);
  p(mutex);
  if((rednum==0&&blacknum<4)||(rednum<=2&&blacknum<2))
   blacknum++;
   上船；
  if(blacknum>=3||rednum==2)
   p(rmutex);
  p(mutex);
  v(bmutex);
}
}

void ship()
{
while(1)
{
  p(mutex);
  if(blacknum+rednum==4)
  {
   过河。。。
   blacknum=rednum=0;
   返回。。。
   v(rmutex);
   v(bmutex);
  }
  v(mutex);
}
}

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

读者写者的变体嘛，
让我郁闷的是自己原来的一份04的真题卷上有错误，题目成了：“有红客和黑客两组人员需要过河。河上有船，但是每次只能乘坐4人，且每次乘客满员时才能开船，到河对岸后空船返回。但船上乘客不能同时有3个红客、1个黑客或者 1个A红客、 3个B黑客的组合。（其他组合安全）。请编写程序，用pv操作解决红客、黑客过河的问题。”

,害得我做那道题时还另设了A红客、B黑客的进程…………
其实我觉得pv不是那么难的，都是些固定的模式加上一些简单的变化，其中比较典型的就是多生产者--消费者加读者写者的题，也很有意思。

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

以下是引用mxf3306在2006-9-30 9:47:00的发言：
你这个解法很有问题，基本上还是过程编程的思维，解PV题用的应该是进程的观点。这个题目跟售票员--公交车题目相似，肯定有一个进程是船，其他进程是客，分红黑两种属性。客满船开和到岸船停客下船，是一个同步关系；船上只能容四个人，是一个互斥关系，而且还加上了一定限制，你的PV不能只是检查非法情况的发生，更重要是要防止非法情况的发生。

dear mxf3306,能否给出一个详细的解答呢？？？？
可以“注明”您的pv处的理由或者原因吗？？？？

我想和“售票员--公交车”做一个类比！！！！ ^____^
从中获得我需要的信息！

最近一阶段我在闭关修炼“pv”和图论的文字证明题！！！

希望dear mxf3306能给小弟指点一二！！！
拜谢！！！！！

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

红黑客程序最后几行中的p(mutex)应该是v（mutex）吧。而且你并没有明确交代释放b/rmutex和mutex是在什么时机，上船后马上释放呢还是下船后再释放。

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

以下是引用teng_t1986在2006-9-30 13:17:00的发言：
读者写者的变体嘛。

其实我觉得pv不是那么难的。
都是些固定的模式加上一些简单的变化，其中比较典型的就是多生产者--消费者加读者写者的题，也很有意思。

dear teng_t1986, 读者写者的变体？？？？？？？？？？？？？？？
能够告诉我这道题与读者写者之间的类似性呢？
即：做一些资源、互斥信号量的“类比”呢？？？？？？？？
敬侯期待！！！！！
=====================================
较典型的就是多生产者--消费者 and 加读者写者的题.

从这些题目中，你能得出在pv编程时候那些规则呢？？？？
那么这些规则在这题中，如何起到作用，也就是怎么来用这些规则！！
能否指点在下呢！！！！ ^____^

=============
dear teng_t1986，您可以写出这道题的pv程序吗？？？？？？

拜谢！！！！！！！！


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