以文本方式查看主题

-  计算机科学论坛  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  想讨论下03的那道PV题  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=38493)


--  作者:teng_t1986
--  发布时间:9/30/2006 1:43:00 PM

--  想讨论下03的那道PV题
就是那道江苏运河问题,原题我不重复了,想必大家都耳熟能详。
我想说的是原题的最后一句话:“由于运输繁忙,不会出现两个分运河上都没有船只的现象”。那么我想能不能用下面这个方法解这道题:
int small=1;
int big=1;
int finish=1;

cobegin{
     process monitor
     repeat:
            v(small);
            v(small);
            v(small);
            p(finish);
            p(finish);
            p(finish);
            v(big);
            p(finish);
     until false;

     process bigship
     repeat:
            p(big);
            go through....
            v(finish);
     until false;

     process smallship
     repeat:
            p(small);
            go through....
            v(finish);
     until false;
}coend;

反正前提是两条运河上都不会没有船,不会发生饥饿或阻塞……

而我原来的解法使用的是第二类读者写者混合模型,只不过最多只允许三个读者同时读,如下(有点麻烦,希望大家耐心看):
int smallship=3;//小船资源
int bigship=1;//大船资源
int mutex=1;//小船间互斥
int b&s_mutex=1;//大小船之间互斥信号
int smallship_num=0;//小船数

cobegin{
      process smallship
      repeat:
            P(b&s_mutex);
            p(smallship);//请求小船资源
            p(mutex);//小船之间互斥
            smallship_num++;//修改小船数
            if(smallship_num==1)
                  p(bigship);//资源分配给了小船,将大船资源剥夺
            v(mutex);
            v(b&s_mutex);
            go through...//过运河
            p(mutex);
            smallship_num--;//修改小船数
            if(smallship_num==0)
                   v(bigship);//小船过完,释放大船资源
            v(mutex);
            v(smallship);//该小船已经通过运河,释放小船资源
      until false;

      process bigship
      repeat:
            p(b&s_mutex);//大小船互斥
            p(bigship);//申请大船资源
            go through....
            v(bigship);
            v(b&s_mutex);
      until false;
}coend;

[此贴子已经被作者于2006-9-30 17:39:44编辑过]

--  作者:teng_t1986
--  发布时间:9/30/2006 1:47:00 PM

--  
第二个解法就算一条运河上无船也不会使另一条运河上阻塞。
或者还有其他的解法,也请帖上来大家一同讨论。
--  作者:Supremgoooo
--  发布时间:9/30/2006 11:04:00 PM

--  
这道题是一个变型的一类读写问题,或是变型的狒狒过河问题。从考试的角度,我认为已经对了。

另外请参考关于信号量的定义,不要用int。

btw:这个题陈老师写了“先到先过”这么一句,如果真正用pv实现是很难的,我认为可以假装没看见这句话。


--  作者:teng_t1986
--  发布时间:10/1/2006 11:53:00 AM

--  
哦,原来是这样,呵呵
另外,我看《现代操作系统》里的IPC问题samphore都是使用int的…………
还有浙大的一本辅导书也是,这个问题我倒是没怎么在意过,多谢提醒!
--  作者:Supremgoooo
--  发布时间:10/2/2006 11:30:00 PM

--  
那时因为C里面没有信号量对应的变量类型,所以大师为了保证C的完整性才这样做的。即便这样,也要在类型定义一下,以便区别于int。如果你熟悉java中的信号量定义,就清楚为什么不用int了。
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
5,859.375ms