操作系统pv金典（史上最强的关于pv原语操作的总结）.pdf

发布时间：2022-06-09 发布人：admin 分类：说明书资料大小：0.87M 资料格式：pdf 举报版权申诉

gjh_a-2970151-4744302543383704898.pdf-第1页.png

第1页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第2页.png

第2页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第3页.png

第3页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第4页.png

第4页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第5页.png

第5页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第6页.png

第6页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第7页.png

第7页 / 共76页

gjh_a-2970151-4744302543383704898.pdf-第8页.png

第8页 / 共76页

1 The P,V Theorem

1 Introduction of P,V Theorem

1 Some Conceptions

2 The Most Important Conceptions

2 Several Typical Examples

1 生产者一消费者问题(producer-consumer problem)

2 读者一写者问题(Readers-Writers Problem)

3 哲学家进餐问题(The Dining Philosophers Problem)

4 理发师问题(Barber Problem)

5 吸烟者问题 (Smoker Problem)

2 Typical Excises

1 生产者-消费者问题扩展

1 扩展一(北大1991)

2 扩展二(北大1995)

3 扩展三

2 读者-写者问题扩展

1 扩展一

2 扩展二(苏州大学2004)

3 吸烟者问题扩展

1 扩展一(北大1999)

2 扩展二

3 九阴真经之研究生题辑

1 真经之银行排队问题(北京大学2000)

2 真经之生产消费问题扩展(浙江大学2001)

3 华南理工2000

4 真经之生产者消费者扩展(同济1996)

5 真经之理发师问题扩展(电子科技大学2000)

6 真经之读者写者问题扩展(南航2001)

7 真经之南航2002

8 真经之管道通信问题(西北工大2000)

9 真经之吃水果问题(南京大学2000)

10 真经之安全岛问题(南开1997)

11 真经之珍珑棋局问题

12 真经之公交车问题(哈尔滨工业大学2000)

13 真经之少林寺问题

14 真经之过桥问题

15 真经之帐户问题(南京大学2000)

16 真经之机房上机问题(北大1997)

17 真经之3进程问题

18 真经之生产消费问题扩展(北大1994)

19 真经之流程问题(北大1991)

20 九阴真经之北航篇

1 智取考场

2 读写者问题(2005)

3 吸烟者问题

4 生产者-消费者扩展

5 阅览室问题

6 P,V改错(2001)

7 面包店(2001)

8 公交车问题(2002)

9 P,V改错(2002)

4 福尔摩斯探案之网络搜捕

1 打印机问题

2 批处理系统问题

3 桔子汁生产线问题

4 保管员问题

5 招聘问题

6 博物馆-公园问题

7 生产流水线问题

8 知错能改

5 独孤九剑之一剑定乾坤

1 试题类型总结

1 名词解释

2 填空题

3 判断题

4 P,V题

5 计算题

6 证明题

2 常考概念归纳

操操操作作作系系系统统统之之之 P V 金金金典典典本本本版版版作作作者者者：：：王昭礼中中中文文文版版版本本本：：：版本 1.0，2008年4月邮邮邮箱箱箱地地地址址址：：：WZLF11@163.com

Preface 本文仅供学习交流使用，严禁商业交易。题目主要来自于网络以及本人搜集整理的各个高校考研试题(文中业已注明)，答案多数经我个人的检查修改后收录该文，还有一些答案是由我自己写的。目的在于让大家更加系统掌握P,V操作题目的处理技巧。在此声明：若有错误请与我联系，我会尽快更正其中的错误并升级版本。若有更为新颖的题目也可以和我联系继续添加到文章当中。若有版权争议，请与我本人联系！♥

目目目录录录第二章 Typical Excises 第一章 The P,V Theorem ······························································· 4 一 Introduction of P,V Theorem ··················································· 4 (一) Some Conceptions ························································· 4 ·········································· 4 (二) The Most Important Conceptions 二 Several Typical Examples ······················································ 5 (一) 生产者一消费者问题(producer-consumer problem)··························· 5 (二) 读者一写者问题(Readers-Writers Problem) ································· 6 ························ 8 (三) 哲学家进餐问题(The Dining Philosophers Problem) ············································· (四) 理发师问题(Barber Problem) 9 ············································· 10 (五) 吸烟者问题(Smoker Problem) ······························································· 13 一生产者-消费者问题扩展 ······················································ 13 (一) 扩展一(北大1991) ························································· 13 (二) 扩展二(北大1995) ························································· 13 (三) 扩展三 ·································································· 15 二读者-写者问题扩展···························································· 16 (一) 扩展一 ·································································· 16 ··················································· 17 (二) 扩展二(苏州大学2004) 三吸烟者问题扩展······························································· 18 (一) 扩展一(北大1999) ························································· 18 (二) 扩展二 ·································································· 18 第三章九阴真经之研究生题辑························································· 20 ·········································· 20 一真经之银行排队问题(北京大学2000) 二真经之生产消费问题扩展(浙江大学2001)······································· 21 ······························································· 23 三华南理工2000 ·········································· 24 四真经之生产者消费者扩展(同济1996) 五真经之理发师问题扩展(电子科技大学2000) ···································· 24 ·········································· 26 六真经之读者写者问题扩展(南航2001) 七真经之南航2002······························································· 27 ·········································· 28 八真经之管道通信问题(西北工大2000) 九真经之吃水果问题(南京大学2000) ············································· 29 ················································ 30 十真经之安全岛问题(南开1997) 十一真经之珍珑棋局问题 ························································· 32 2

目录 3 十二真经之公交车问题(哈尔滨工业大学2000)······································· 32 十三真经之少林寺问题 ···························································· 33 十四真经之过桥问题······························································· 34 十五真经之帐户问题(南京大学2000)················································ 39 十六真经之机房上机问题(北大1997)················································ 40 十七真经之3进程问题 ···························································· 41 ·········································· 46 十八真经之生产消费问题扩展(北大1994) ··················································· 48 十九真经之流程问题(北大1991) 二十九阴真经之北航篇 ···························································· 50 (一) 智取考场 ······························································· 50 (二) 读写者问题(2005) ························································· 50 (三) 吸烟者问题 ······························································· 51 (四) 生产者-消费者扩展 ······················································ 52 (五) 阅览室问题 ······························································· 52 (六) P,V改错(2001) ···························································· 54 ···························································· 54 (七) 面包店(2001) (八) 公交车问题(2002) ························································· 54 (九) P,V改错(2002) ···························································· 54 第四章福尔摩斯探案之网络搜捕 ······················································ 56 一打印机问题 ·································································· 56 二批处理系统问题······························································· 62 三桔子汁生产线问题 ···························································· 63 四保管员问题 ·································································· 64 五招聘问题 ····································································· 65 六博物馆-公园问题 ···························································· 67 七生产流水线问题······························································· 68 八知错能改 ····································································· 70 第五章独孤九剑之一剑定乾坤························································· 73 一试题类型总结 ······························································· 73 (一) 名词解释 ······························································· 73 (二) 填空题 ·································································· 73 (三) 判断题 ·································································· 73 (四) P,V题····································································· 74 (五) 计算题 ·································································· 74 (六) 证明题 ·································································· 74 二常考概念归纳 ······························································· 74

第第第一一一章章章 The P,V Theorem 在操作系统理论中有一个非常重要的概念叫做P,V原语。在我们研究进程间的互斥的时候经常会引入这个概念，将P,V操作方法与加锁的方法相比较，来解决进程间的互斥问题。实际上，他的应用范围很广，他不但可以解决进程管理当中的互斥问题，而且我们还可以利用此方法解决进程同步与进程通信的问题。一 Introduction of P,V Theorem 阐述P,V原语的理论不得不提到的一个人便是赫赫有名的荷兰科学家E.W.Dijkstra。如果你对这位科学家没有什么印象的话，提起解决图论中最短路径问题的Dijkstra算法应当是我们再熟悉不过的了。P,V原语的概念以及P,V操作当中需要使用到的信号量的概念都是由他在1965年提出的。 1 Some Conceptions 信号量是最早出现的用来解决进程同步与互斥问题的机制，包括一个称为信号量的变量及对它进行的两个原语操作。信号量为一个整数，我们设这个信号量为：S。很显然，我们规定在S大于等于零的时候代表可供并发进程使用的资源实体数，S小于零的时候，表示正在等待使用临界区的进程的个数。根据这个原则，在给信号量附初值的时候，我们显然就要设初值大于零。 p操作和v操作是不可中断的程序段，称为原语。P,V原语中P是荷兰语的Passeren，相当于英文的pass,V是荷兰语的Verhoog,相当于英文中的incremnet。 P原语操作的动作是：（1）S减1；（2）若S减1后仍大于或等于零，则进程继续执行；（3）若S减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。 V原语操作的动作是：（1）S加1；（2）若相加结果大于零，则进程继续执行；（3）若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。需要提醒大家的是：P,V操作首先是一个原语操作，对于每一个进程来说，都只能进行一次。而且必须成对使用。且在P,V愿语执行期间不允许有中断的发生。对于具体的实现，方法非常多，可以用硬件实现，也可以用软件实现。这里不再赘述。 2 The Most Important Conceptions 临界资源是指每次仅允许一个进程访问的资源。属于临界资源可以是硬件的打印机、磁带机等,软件的有消息缓冲队列、变量、数组、缓冲区等。每个进程中访问临界资 4

CHAPTER1. THEP,VTHEOREM 5 源的那段程序称为临界区（临界资源是一次仅允许一个进程使用的共享资源）。每次只准许一个进程进入临界区，该进程进入后不允许其他进程进入。进程的同步和互斥互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。二 Several Typical Examples 本节我们讨论几个利用信号量来实现进程互斥和同步的经典例子。这里的问题关键是如何选择信号量和如何安排P、V原语的使用顺序。依据信号量与进程的关系，我们可把进程中使用的信号量分成私有信号量和公用信号量。私有信号量是指只与制约进程和被制约进程有关的信号量；公用信号量是指与一组并发进程有关的信号量。这里请不要和C++、JAVA 等编程语言的公有、私有相混淆。这里指的是相对于共享资源来说的。 1 生产者一消费者问题(producer-consumer problem) 生产者一消费者问题(producer-consumer problem)是指若干进程通过有限的共享缓冲区交换数据时的缓冲区资源使用问题。问题描述：假设“生产者”进程不断向共享缓冲区写人数据(即生产数据)，而“消费者”进程不断从共享缓冲区读出数据(即消费数据)；共享缓冲区共有n个；任何时刻只能有一个进程可对共享缓冲区进行操作。所有生产者和消费者之间要协调，以完成对共享缓冲区的操作。 Figure 1.1: producer-consumer problem 我们可把共享缓冲区中的n个缓冲块视为共享资源，生产者写人数据的缓冲块成为消费者可用资源，而消费者读出数据后的缓冲块成为生产者的可用资源。为此，可设置三个信号量：full、empty和mutex。其中：full表示有数据的缓冲块数目，初值是0；empty表示空的缓冲块数初值是n；mutex用于访问缓冲区时的互斥，初值是1。实际上，full和empty间存在如下关系：full+ empty = N The P,V code Using Pascal buffer: array [0..k-1]of integer; in,out: 0..k-1;//in记录第一个空缓冲区，out记录第一个不空的缓冲区 empty,full,mutex: semaphore; //empty控制缓冲区不满,full控制缓冲区不空,mutex保护临界区；

CHAPTER1. THEP,VTHEOREM 6 //初始化empty=k,full=0,mutex=1 cobegin procedure producer: while true then begin produce(&item); p(empty); p(mutex); buffer[in]:=item; in:=(in+1) mod k; v(mutex); v(full); end coend procedure consumer: while true then begin p(full); p(mutex); item:=buffer[out]; out:=(out+1) mod k; v(mutex); v(empty); consume(&item); end 注意：这里每个进程中各个P操作的次序是重要的。各进程必须先检查自己对应的资源数在确信有可用资源后再申请对整个缓冲区的互斥操作；否则，先申请对整个缓冲区的互斥操后申请自己对应的缓冲块资源，就可能死锁。出现死锁的条件是，申请到对整个缓冲区的互斥操作后，才发现自己对应的缓冲块资源，这时已不可能放弃对整个缓冲区的占用。如果采用AND信号量集，相应的进入区和退出区都很简单。如生产者的进入区为Swait(empty，mutex)，退出区为Ssignal(full，mutex)。 2 读者一写者问题(Readers-Writers Problem) 问题描述：有一个许多进程共享的数据区，这个数据区可以是一个文件或者主存的一块空间；有一些只读取这个数据区的进程（Reader）和一些只往数据区写数据的进程(Writer)，此外还需要满足以下条件：（1）任意多个读进程可以同时读这个文件；（2）一次只有一个写进程可以往文件中写；（3）如果一个写进程正在进行操作，禁止任何读进程度文件。实验要求用信号量来实现读者写者问题的调度算法。实验提供了Semaphore类，该类通过P()、V()两个方法实现了P、V原语的功能。实验的任务是修改Reader类的Read方法以及Writer类的Write方法。我们需要分两种情况实现该问题：读优先：要求指一个读者试图进行读操作时，如果这时正有其他读者在进行操作，他可直接开始读操作，而不需要等待。写优先：一个读者试图进行读操作时，如果有其他写者在等待进行写操作或正在进行写操作，他要等待该写者完成写操作后才开始读操作。 The P,V code Using Pascal 读者优先算法： rwmutex 用于写者与其他读者/写者互斥的访问共享数据 rmutex 用于读者互斥的访问

CHAPTER1. THEP,VTHEOREM 7 readcount 读者计数器 var rwmutex, rmutex ： semaphore := 1, 1 ； int readcount = 0; cobegin procedure reader_i // i=1,2,…. begin P(rmutex); Readcount + +; if (readcount = = 1) P(rwmutex); V(rmutex); 读数据； P(rmutex); Readcount - -; if (readcount = = 0) V(rwmutex); V(rmutex); end procedure Writer_j // j = 1,2,…. begin P(rwmutex); 写更新； V(rwmutex); end Coend The P,V code Using Pascal 写者优先： 1）多个读者可以同时进行读 2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行） 3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）如果读者数是固定的，我们可采用下面的算法： rwmutex：用于写者与其他读者/写者互斥的访问共享数据 rmutex：该信号量初始值设为10，表示最多允许10个读者进程同时进行读操作 var rwmutex, rmutex ： semaphore := 1, 10 ； cobegin procedure reader_i // i=1,2,…. begin P(rwmutex); //读者、写者互斥 P(rmutex); V(rwmutex); // 释放读写互斥信号量，允许其它读、写进程访问资源读数据； V(rmutex); end procedure Writer_j begin P(rwmutex); // j = 1,2,….

分享到：

赞收藏

资料库

操作系统pv金典（史上最强的关于pv原语操作的总结）.pdf

相关推荐

课程资源

热门标签

最新资料