计算机科学论坛--北大必考题，PV操作中的疑惑。。。

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

XML论坛

W3CHINA.ORG讨论区

>>计算机科学论坛<<

SOAChina论坛

Blog

开放翻译计划

新浪微博

首页

软件下载

资料下载

核心成员

帮助

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

[返回] 计算机科学论坛 → 计算机理论与工程 → 『计算机考研交流』 → 北大必考题，PV操作中的疑惑。。。

◇查看新帖 ◇ 用户列表 ◇

(订阅本版)

您是本帖的第 20011 个阅读者　　

*	贴子主题：北大必考题，PV操作中的疑惑。。。	举报打印推荐 IE收藏夹
	本主题类别:

Supremgoooo

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

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

	第11楼

首先回答yangling_1985的疑惑，让我们再看这个定义：
v(s) //此时s表示等待进程的个数，即有|s|个等待进程
s=s+1;
若s<=0,释放等待队列中末尾的进程，否则，继续执行。//因为s加了1，所以此时有|s|+1个等待进程。
下面是carroty的问题：
本题考察队P，V定义的理解，P，V原本的意思唤醒上是随机的，即从所有的等待进程中随机的唤醒一个进程，这也体现了多道程序设计的不确定性，不可在现性。而本题说从末尾唤醒，首先它违背了P，V随机性这个特征，其次，每个进程是在不断的反复执行这个操所的，假设某一时刻P3在临界区内，P1，P2都P了而被阻塞，这时P4也P一下，P3执行完后，V一下，则P4进临界区，同时P3又P，之后P3又进。。。于是，P1，P2就永远的等待下去，此所谓饥饿。
一个进程就一个程序，在执行时无所谓队列。为什么要排队呢？就是因为有多个进程对一个资源进行抢夺，例如：你去食堂打饭，就你一个人，你需要排队吗？但是人很多的话，总是站在你后面的人先打饭，而你后面的人源源不断的补上来，那你不是要一直等下去？
下面回答borlong的问题：
饥饿就是一个进程因为长时间的得不到资源满足而一直等下去，它往往反映出算法的不合理。
漏斗思想是用队列来实现这个过程，就是把进程对资源的请求排队，首先要占到队尾，然后向前移动一位。。。直道站到队首。实现方法是队尾可以允许站4个人，就是信号量初值4，然后向前是3。。。1。算法你自己写吧。

2006/9/24 23:48:00

borlong

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

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

	第12楼

小弟在此激情感谢大家！
Dear Brothers, 您们让小弟见识不少啊！在此请教了！
pv程序设计出来以后，有什么特别的方法来测试正确与否吗？能够用一些简单的步骤来
判断出我的程序有无死锁或者饥饿等等之类的呢？
难道非一定要用列举法，分别一个一个的试探着进行吗？
我的pv思路越来越明了了！感谢大家！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/25 7:49:00

shenfuquan

  等级：大一新生
  文章：4
  积分：80
  门派：XML.ORG.CN
  注册：2006/5/10

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

	第13楼

v(s) //此时s表示等待进程的个数，即有|s|个等待进程
-------------------这是对的
s=s+1;
若s<=0,释放等待队列中末尾的进程，否则，继续执行。
------------------这时因为s信号量对应对列若有进程等待，此时s必为负值(s<0)，之后因为s加了1，所以应该为|s|-1个等待进程。

以下是引用Supremgoooo在2006-9-24 23:48:00的发言：
首先回答yangling_1985的疑惑，让我们再看这个定义：
v(s) //此时s表示等待进程的个数，即有|s|个等待进程
s=s+1;
若s<=0,释放等待队列中末尾的进程，否则，继续执行。//因为s加了1，所以此时有|s|+1个等待进程。
下面是carroty的问题：
本题考察队P，V定义的理解，P，V原本的意思唤醒上是随机的，即从所有的等待进程中随机的唤醒一个进程，这也体现了多道程序设计的不确定性，不可在现性。而本题说从末尾唤醒，首先它违背了P，V随机性这个特征，其次，每个进程是在不断的反复执行这个操所的，假设某一时刻P3在临界区内，P1，P2都P了而被阻塞，这时P4也P一下，P3执行完后，V一下，则P4进临界区，同时P3又P，之后P3又进。。。于是，P1，P2就永远的等待下去，此所谓饥饿。
一个进程就一个程序，在执行时无所谓队列。为什么要排队呢？就是因为有多个进程对一个资源进行抢夺，例如：你去食堂打饭，就你一个人，你需要排队吗？但是人很多的话，总是站在你后面的人先打饭，而你后面的人源源不断的补上来，那你不是要一直等下去？
下面回答borlong的问题：
饥饿就是一个进程因为长时间的得不到资源满足而一直等下去，它往往反映出算法的不合理。
漏斗思想是用队列来实现这个过程，就是把进程对资源的请求排队，首先要占到队尾，然后向前移动一位。。。直道站到队首。实现方法是队尾可以允许站4个人，就是信号量初值4，然后向前是3。。。1。算法你自己写吧。

2006/9/25 14:50:00

borlong

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

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

	第14楼

Dear Supremgoooo　ｓａｙｓ，Ｔｈｅｒｅ　ｉｓ　ａ　ｓｔａｒｖａｔｉｏｎ　ｉｎ
ｍｙ　ｃｏｐｒｏｇａｍｅ！！！　ｂｕｔ！！！
我。。我。。我。。我看不出我解法里面的饥饿啊！！！
我的解法：
pi: (i=1or2or3or4)
             while(1)
                     { p(s);
                        使用资源。
                       v(s);
                     }
换成语言描述是：任意进程ｐｉ来执行，先是执行p(s)，如果通过，则使用，否则等待啊！！！
这个程序有问题吗？？？　　我不明白！！！
难道是〉＝２个进程同时来执行时候会出现问题吗？
那么后果是怎样？？？　　这个地方，我是无法用思维去想象！！！
还请牛人来解释。。。　　：Ｐ　急切的期待！！！！！！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/25 17:13:00

shenfuquan

  等级：大一新生
  文章：4
  积分：80
  门派：XML.ORG.CN
  注册：2006/5/10

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

	第15楼

如果进程申请互斥资源的顺序如下:P1,P2,P3,P4,P1,P2,P3,P4,P1......
在P1进行V操作时,又有一个新的P1进程申请互斥资源而等待,而题目V的操作释放队列末尾的进程,所以P1进行V操作时,它释放的是新的P1进程,重复以上操作, 只有P1类进程才申请到互斥资源,(P2,P3,P3)类进程只会starvation(饥饿）。

以下是引用borlong在2006-9-25 17:13:00的发言：
Dear Supremgoooo　ｓａｙｓ，Ｔｈｅｒｅ　ｉｓ　ａ　ｓｔａｒｖａｔｉｏｎ　ｉｎ
ｍｙ　ｃｏｐｒｏｇａｍｅ！！！　ｂｕｔ！！！
我。。我。。我。。我看不出我解法里面的饥饿啊！！！
我的解法：
pi: (i=1or2or3or4)
              while(1)
                      { p(s);
                         使用资源。
                        v(s);
                      }
换成语言描述是：任意进程ｐｉ来执行，先是执行p(s)，如果通过，则使用，否则等待啊！！！
这个程序有问题吗？？？　　我不明白！！！
难道是〉＝２个进程同时来执行时候会出现问题吗？
那么后果是怎样？？？　　这个地方，我是无法用思维去想象！！！
还请牛人来解释。。。　　：Ｐ　急切的期待！！！！！！

2006/9/26 10:31:00

mxf3306

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

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

	第16楼

Supremgoooo兄，这倒二叉树和漏斗法不知你是从哪看来的，让人耳目一新，我翻了很多教材都没找到出处，相关东西似乎只在北大的讲义上有所提及。能否提供一下资料来源。

2006/9/26 18:33:00

borlong

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

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

	第17楼

dear shenfuquan，我懂了！这个饥饿跟v(s)定义有关系。因为从末尾处释放！
所以，有可能总会被同一个进程使用！！那么其他进程会饥饿。对不？？？
您有设计的方案吗？可否指点一二，：P
===========================================
对了！各位高手！
小弟我面临的最大的问题是：
当我看到一个pv程序或者别人或我写的程序。我无法用思维去模拟
该pv程序的执行！也就是无法去判断其是否正确，即不存在死锁、
饥饿等等。跟一般的程序大大的不同阿！！！
请问：能否有什么方法去判断呢？还是需要思维去模拟执行吗？？？
还是用图示等等方法去模拟。。。
请牛人给小弟解答！！！急切期待。。。: P
我也期待dear Supremgoooo,将倒二叉树和漏斗法贴出来！！
或者说明是哪个版本上的，小弟我也没有看到啊！！！: P
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/26 21:01:00

borlong

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

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

	第18楼

怎样去检测pv程序的正确与否啊？
怎样在大脑里模拟去执行呢？
因为小弟正在努力尝试着去想象 pv操作过程。这个不像一般的程序设计，还要考虑“次序”问题。我对这方面甚是迷惑！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/27 8:41:00

borlong

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

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

	第19楼

利用倒立二叉树来实现互斥，效率较高。恩。。不是太明白？？？
您所说的效率较高，或者能够迅速判定该pv程序的正确与否，如没有死锁、没有饥饿，到底是怎么去判断的啊？
就拿前面几位牛人的pv解法吧，你们是如何看出没有死锁或者饥饿的呢？？？
有什么妙的方法去解释呢？
能否有种方法如一般程序设计那样，可以在头脑中，稿纸上进行模拟执行呢？？？
小弟急切的希望牛人指点一二。
小弟让你们见笑了吧？
呵呵。。。对pv操作跟我的离散图论部分有些类似，总是无法彻底的把握！！！
小弟再次向各位高手请教了！！！！
----------------------------------------------
落花如雪胜雪香，秋风似水赛水凉。花下醉影不忍看，偏偏圆月又看窗！

2006/9/27 9:07:00

Supremgoooo

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

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

	第20楼

以下是引用shenfuquan在2006-9-25 14:50:00的发言：
v(s)  //此时s表示等待进程的个数，即有|s|个等待进程
-------------------这是对的
  s=s+1;
  若s<=0,释放等待队列中末尾的进程，否则，继续执行。
------------------这时因为s信号量对应对列若有进程等待，此时s必为负值(s<0)，之后因为s加了1，所以应该为|s|-1个等待进程。
//这个定义没有说s必为负值；从实际的角度出发，s也是可以不为负的。
//你的意思是说s为0时有-1个进程在等待。

2006/9/29 22:45:00

GoogleAdSense

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

	广告

2024/5/7 23:24:56

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

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


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