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

新书推介：《语义网技术体系》
作者：瞿裕忠，胡伟，程龚

XML论坛

W3CHINA.ORG讨论区

计算机科学论坛

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

>> 研友的交流园地，讨论关于计算机考研的方方面面。

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 北大必考题，PV经典案例分析。。。

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 29497 个阅读者　　

*	贴子主题：北大必考题，PV经典案例分析。。。	举报打印推荐 IE收藏夹
	本主题类别:

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

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

	第11楼

dear carroty,我在仔细捉摸您的程序啊！
不过，您可以注明您的在程序里面的 pv的实际意义吗？？？
如：封锁某某进程。。互斥某某资源。。好吗？？？？？？^____^
拜谢！！！！

以下是引用carroty在2006-9-30 10:00:00的发言：
学写了一个,大牛指正...
:)
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);
  }
}

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

2006/9/30 19:59:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

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

	第12楼

以下是引用mxf3306在2006-9-30 19:53:00的发言：
红黑客程序最后几行中的p(mutex)应该是v（mutex）吧。而且你并没有明确交代释放b/rmutex和mutex是在什么时机，上船后马上释放呢还是下船后再释放。

dear mxf3306,给出您的解法，好吗？？？？？ ^_____^
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/30 20:01:00

carroty

  等级：大四(GRE考了1600分!)
  文章：153
  积分：1257
  门派：IEEE.ORG.CN
  注册：2006/4/4

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

	第13楼

提示一下,参考书上的读者写者问题的解法.
当读者的数量满足一定条件的时候,调用一个p(write)阻塞写者.
可以考虑读者跟写者公平竞争的情况,跟这个题就比较象了.
其实,我写的不一定对:),等待大牛能提点意见出来.

2006/9/30 22:40:00

Supremgoooo

  等级：大四下学期(考上研究生啦!)
  文章：201
  积分：1872
  门派：XML.ORG.CN
  注册：2006/4/9

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

	第14楼

carroty：
很遗憾！你的算法已经快要实现互斥了，但是却出现了死锁：
某一时刻redman进去了一个，这时突然来了blackman，于是blackman被P（mutex）阻塞，redman的进程在执行了redcount++之后发现rednum>=3，于是执行P（bmutex），而由于前面那个blackman已经占有了bmutex，所以，redman被阻塞。。整个程序就这样死掉了！
另外，我认为你每过一次河就清空redcount和blackcount是不行的，这样可能抛弃一些进来而等待的人。而且你这个算法中并没有留住进去的人，写时忘记了？
我已经理解了你的思路，你是想进去一个人，如果他满足条件就上船，否则等待。对吧？
这个程序如果是这样做的话就算实现了，也不能说全对，为什么？你先想想吧：）
borlong：
一类读写模型（即写者优先）可以学到两点：
（1）对互斥资源的保护；
（2）实现不同队列间的互斥。
你的算法首先在互斥资源的使用上没有加锁，所以一定导致同时进临界区。

2006/9/30 22:54:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

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

	第15楼

以下是引用Supremgoooo在2006-9-30 22:54:00的发言：
carroty：
很遗憾！你的算法已经快要实现互斥了，但是却出现了死锁：
某一时刻redman进去了一个，这时突然来了blackman，于是blackman被P（mutex）阻塞，redman的进程在执行了redcount++之后发现rednum>=3，于是执行P（bmutex），而由于前面那个blackman已经占有了bmutex，所以，redman被阻塞。。整个程序就这样死掉了！
另外，我认为你每过一次河就清空redcount和blackcount是不行的，这样可能抛弃一些进来而等待的人。而且你这个算法中并没有留住进去的人，写时忘记了？
我已经理解了你的思路，你是想进去一个人，如果他满足条件就上船，否则等待。对吧？
这个程序如果是这样做的话就算实现了，也不能说全对，为什么？你先想想吧：）
borlong：
一类读写模型（即写者优先）可以学到两点：
（1）对互斥资源的保护；
（2）实现不同队列间的互斥。
你的算法首先在互斥资源的使用上没有加锁，所以一定导致同时进临界区。

啊！我在仔细阅读您的解答中，也渐渐能感受到pv的思路了阿。。。太好了！！
Supremgoooo！，我也要加油啦！！
国庆愉快哦！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/10/1 7:06:00

teng_t1986

  威望：1
  头衔：智能缔造者
  等级：计算机学士学位(版主)
  文章：368
  积分：2273
  门派：IEEE.ORG.CN
  注册：2006/4/8

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

	第16楼

以下是引用borlong在2006-9-30 19:56:00的发言：
[quote]以下是引用teng_t1986在2006-9-30 13:17:00的发言：
读者写者的变体嘛。
  其实我觉得pv不是那么难的。
都是些固定的模式加上一些简单的变化，其中比较典型的就是多生产者--消费者加读者写者的题，也很有意思。
[/quote]
dear teng_t1986,   读者写者的变体？？？？？？？？？？？？？？？
能够告诉我这道题与读者写者之间的类似性呢？
即：做一些资源、互斥信号量的“类比”呢？？？？？？？？
敬侯期待！！！！！
=====================================
较典型的就是多生产者--消费者   and  加读者写者的题.
从这些题目中，你能得出在pv编程时候那些规则呢？？？？
那么这些规则在这题中，如何起到作用，也就是怎么来用这些规则！！
能否指点在下呢！！！！ ^____^
=============
dear teng_t1986，您可以写出这道题的pv程序吗？？？？？？
拜谢！！！！！！！！

呵呵不要那么客气，讨论问题嘛~~（看你用一大串！？似乎挺激动的，注意保持心态哦）
红客黑客就是一次限制读者写者数量的读者写者问题呀（你愿意也可以说他是读者读者问题），加了一些限制而已，至于程序，我大概是5月份第一次看真题的时候做的，如前所述，那份真题打印的有问题，在那道题原来的基础上又加了变化……花了我30分钟才编出来。当时也是倍受打击啊……
在编pv题时最有效的方法就是套模式，把题目模型抽象成已知模型……
我没有弄懂你说的“规则”，狭义？广义？
至于正确程序，等我有时间的时候再贴出来吧，最近人变得有些懒，有些怕麻烦，呵呵：）
至于你说你那些基本模型都“非常的熟悉”，还是做不好pv，我也不清楚是怎么回事，你是不是其他的习题做少了，缺乏“把题目模型抽象成已知模型”的能力？？自己再钻研钻研吧……
----------------------------------------------
书山奋战不觉难，
一刻光阴莫等闲。
长路遥遥飞浩志，
前尘洗却作泥丸。
粗茶薄被心灯暖，
明月清窗几案寒。
欲待桂枝香万里，
海阔天空俱欢颜。
My blog:http://hi.baidu.com/tengteng2007

2006/10/1 12:09:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

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

	第17楼

以下是引用teng_t1986在2006-10-1 12:09:00的发言：
[ 红客黑客就是一次限制读者写者数量的读者写者问题呀（你愿意也可以说他是读者读者问题），加了一些限制而已，至于程序，我大概是5月份第一次看真题的时候做的，如前所述，那份真题打印的有问题，在那道题原来的基础上又加了变化……花了我30分钟才编出来。当时也是倍受打击啊……
在编pv题时最有效的方法就是套模式，把题目模型抽象成已知模型……

那么自己编出pv程序来后，怎样去检验正确与否呢？
不想普通程序，pv测试程序中有很多不确定因素。如进程到达的次序！有太多的组合！！！
难道要一个一个的去检测？？？？？？？？
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/10/1 12:50:00

mxf3306

  等级：大三(研究MFC有点眉目了!)
  文章：112
  积分：823
  门派：XML.ORG.CN
  注册：2006/7/6

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

	第18楼

red()
{
p(mutex);
while(redcount+blackcount==4||blackcount==3)
{
firstcount++;//进入第一队列
if(secondcount>0)
  v(seconddelay);//第二队列有人，让其进行下一轮测试
else
  v(mutex);//不满足上船条件，且第二队列没人，让进新的进程
p(firstdelay);
firstcount--;
secondcount++;
if(firstcount>0)
  v(firstdelay);//只要第一队列里还有人，统统让进第二队列
else
  v(seconddelay);//否则让第二队列的人进行下一轮测试
p(seconddelay);
secondcount--;
}
上船;
redcount++;
v(start);
if(firstcount>0)
v(firstdelay);
else if(secondcount>0)
v(seconddelay);
else
v(mutex);
p(stop);
下船
}
boat()
{
while(1)
{
p(start); //很累赘，但怎么保证满四个人才开船？
p(start); //如果在red()中加上if(redcount+blackcount==4) v(start);
p(start); //那之前的几个进程就会跳过这个判断，直接下船了。
p(start);
过河;
v(stop);
v(stop);
v(stop);
v(stop);
返回;
p(mutex);
redcount=0;//之所以在这清空，是因为如果由客下船后自行减计数器的话，就等于说允许等待的客不等船返回就上船
blackcount=0;
v(mutex);
}
}
main()
{
semaphore mutex=1;
semaphore firstdelay=seconddelay=0;
semaphore start=stop=0;
firstcount=secondcount=0;
parbegin(boat(),red(),black());
}
firstdelay：第一次等待队列
seconddelay: 第二次等待队列
为什么要两个队列？因为要保证有限等待。设只有一个队列，排列为黑黑黑红|黑黑黑黑|黑黑黑黑|.....，则轮到红客时，不符合条件，怎么办？堵住队头会出现死锁，重新放回队尾，则红客将永无出头之日，因为每次它都不符合条件而被重置于队列最后端。如果设两个队列，一个红客专用，一个黑客专用，那空船情况下，谁上？可能出现一种情况，那就是每一次选的都是红客，黑客将饿死。(不知谁有什么更好的方法解决吗？）
基本思想：只要符合while条件，就一直在两个队列之间进行循环转换。一旦有进程不符合while条件，就表明可能有空位，将第一队列中进程转到第二队列，再将第二队列进程全部唤醒,重新测试条件。
to borlong：似乎没有很有效的方法检验，这也是之所以产生管程的原因。

2006/10/1 13:02:00

borlong

  等级：大三(面向对象是个好东东!)
  文章：106
  积分：519
  门派：XML.ORG.CN
  注册：2006/6/26

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

	第19楼

to borlong：似乎没有很有效的方法检验，这也是之所以产生管程的原因。
[/quote]
明白！！
开来只有通过练习来训练自己啦！！！^___^
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/10/1 13:18:00

teng_t1986

  威望：1
  头衔：智能缔造者
  等级：计算机学士学位(版主)
  文章：368
  积分：2273
  门派：IEEE.ORG.CN
  注册：2006/4/8

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

	第20楼

的确没有很有效的方法检验pv的正确性，所以要引入套路，就像当大型软件开发陷入泥潭中时引入“模式”和“软件工程”的概念一样（有兴趣看GoF的design patterns吗？）
----------------------------------------------
书山奋战不觉难，
一刻光阴莫等闲。
长路遥遥飞浩志，
前尘洗却作泥丸。
粗茶薄被心灯暖，
明月清窗几案寒。
欲待桂枝香万里，
海阔天空俱欢颜。
My blog:http://hi.baidu.com/tengteng2007

2006/10/2 11:55:00

GoogleAdSense

  等级：大一新生
  文章：1
  积分：50
  门派：无门无派
  院校：未填写
  注册：2007-01-01

	广告

2024/5/22 0:11:24

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

管理选项：修改tag | 锁定 | 解锁 | 提升 | 删除 | 移动 | 固顶 | 总固顶 | 奖励 | 惩罚 | 发布公告


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