计算机科学论坛--P,V题的学习方法

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

最近学习比较紧张，上网的时间和次数都少，大家的一些问题不能及时回答，见谅！

我写的P，V的帖子引起大家的热烈讨论，我想原因有二：（1）北大必考P，V；（2）P，V很难，题目不知道咋作。我这里写篇文章给大家参考：

首先，P，V习题是没有统一的做题方法的，没有说哪种解法可以通用，我前面说的倒二叉树法，漏斗法都只是对那个题而言。

其次，如何学习P，V？
分析北大近21年的os考验试题和市面上一般的os教程，不外乎如下几个模型：
（1）生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；
（2）读者-写着模型，分两种：读者优先，写着优先；
（3）哲学家就餐模型，共3种解法；
（4）吸烟者问题，1种解法；
（5）面包师问题，1种解法；
（6）类似面包师的理发师问题，可以推广到多个理发师问题；
（7）狒狒过河问题；
（8）另类P，V问题。
你把每个模型熟练掌握之后，P，V就变的很简单了。
它们的实例是：
（1）教材上有；
（2）读者优先有，写者优先条件为：
（i）多个读者可以同时进行读；
（ii）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；
（iii）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。
（3）教材上有；
（4）教材课后的那道酒吧问题；
（5）教材课后的那道银行问题；
（6）教材上有；
（7）教材课后的那道运河题；
（8）borlong的帖子里。
关于模型8的漏斗解法（注：我自己起的名字，有老师叫它筛子解法，我认为叫漏斗更确切些），算法如下：
Semaphore S[n-1];  // S[i]的初值为i+1
Procedure_i ()
{
   int  i;
L：for(i=n-2; i>=0; i--)
      P(S[i]);
    DO_JOB_IN_CRITICAL_SECTION;
    for(i=0;i<n－1;i++)
      V(S[i]);
   goto L;
}
这个算法很难理解，它其实是一个漏斗模型，一个进程就像我们倒油时用的漏斗一样从大到小滑下去。这道题在北大历史上考过若干次了，最近的一次发生在05年，我建议大家最好只记另外一种方法。

最后，谈谈我的P,V学习，当年也是一头雾水，最后才发现掌握这些基本模型后做题就简单了。我是可以把上面的答案都贴出来，但是这样大家反而更难掌握P，V了。做P，V，只有你把所有的错误都犯一遍后，你才能真正理解P，V的含义.当你作完后，要反复想自己的算法是否合理，想象各种极端情况下算法的执行情况，最后把你的算法可以贴出来，大家讨论。你可以轻易指出别人算法错误的时候，自己也是P，V高手了。

注：难一些的模型，如（2），我10月底会贴出来。

[此贴子已经被作者于2006-9-29 22:52:43编辑过]

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

楼主强人。。。。。。。。。。

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

To Supremgoooo:
"否则就像shenfuquan的帖子——他并没有理解P，V的真正含义"
呵呵,谈谈你说这句话的依据:)给大家开开眼界.

以下是引用Supremgoooo在2006-9-26 23:25:00的发言：
最近学习比较紧张，上网的时间和次数都少，大家的一些问题不能及时回答，见谅！
我写的P，V的帖子引起大家的热烈讨论，我想原因有二：（1）北大必考P，V；（2）P，V很难，题目不知道咋作。我这里写篇文章给大家参考：
首先，P，V习题是没有统一的做题方法的，没有说哪种解法可以通用，我前面说的倒二叉树法，漏斗法都只是对那个题而言。
其次，如何学习P，V？
分析北大近21年的os考验试题和市面上一般的os教程，不外乎如下几个模型：
（1）生产-消费模型，推广到多个生产者，多个消费者的生产消费模型；
（2）读者-写着模型，分两种：读者优先，写着优先；
（3）哲学家就餐模型，共3种解法；
（4）吸烟者问题，1种解法；
（5）面包师问题，1种解法；
（6）类似面包师的理发师问题，可以推广到多个理发师问题；
（7）狒狒过河问题；
（8）另类P，V问题。
你把每个模型熟练掌握之后，P，V就变的很简单了。
它们的实例是：
（1）教材上有；
（2）读者优先有，写者优先条件为：
（i）多个读者可以同时进行读；
（ii）写者必须互斥（只允许一个写者写，同时也不能读者、写者同时进行）；
（iii）写者优先于读者（一旦有写者来，则后续读者必须等待，唤醒时优先考虑写者）。
（3）教材上有；
（4）教材课后的那道酒吧问题；
（5）教材课后的那道银行问题；
（6）教材上有；
（7）教材课后的那道运河题；
（8）borlong的帖子里。
关于模型8的漏斗解法（注：我自己起的名字，有老师叫它筛子解法，我认为叫漏斗更确切些），算法如下：
Semaphore S[n-1];  // S[i]的初值为i+1
Procedure_i ()
{
    int  i;
L：for(i=n-2; i>=0; i--)
       P(S[i]);
     DO_JOB_IN_CRITICAL_SECTION;
     for(i=0;i<n－1;i++)
       V(S[i]);
    goto L;
}
这个算法很难理解，它其实是一个漏斗模型，一个进程就像我们倒油时用的漏斗一样从大到小滑下去。这道题在北大历史上考过若干次了，最近的一次发生在05年，我建议大家最好只记另外一种方法。
最后，谈谈我的P,V学习，当年也是一头雾水，最后才发现掌握这些基本模型后做题就简单了。我是可以把上面的答案都贴出来，但是这样大家反而更难掌握P，V了。做P，V，只有你把所有的错误都犯一遍后，你才能真正理解P，V的含义，否则就像shenfuquan的帖子——他并没有理解P，V的真正含义。当你作完后，要反复想自己的算法是否合理，想象各种极端情况下算法的执行情况，最后把你的算法可以贴出来，大家讨论。你可以轻易指出别人算法错误的时候，自己也是P，V高手了。
注：难一些的模型，如（2），我10月底会贴出来。

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

我会用心学习dear Supremgoooo 的关于pv的方法，我也会尝试着去写，希望能得到您的指点啊！！！！ ^____^

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

搬个板凳过来听

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

推荐一下我觉得讲PV比较好的教材吧，一本是经典的Operating System Concept，一本是stallings的操作系统内核，北大的讲义也不错，比教材内容丰富很多，但所有讲义都有一个缺点：太过简略。

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

读者，写者问题树上已经有了，不知大牛说的是不是那个！


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