 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编辑过]
|
[返回] 计算机科学论坛 →
计算机理论与工程 → 『 计算机考研交流 』 → P,V题的学习方法
(订阅本版)
2006/9/26 23:25:00
顶端 
新浪微博
