经典同步问题(哲学家进餐等)

1、模型分析模型分析 （1）生产者进行生产将物品放入仓库，同一时间只能有一个生产者将物品放入仓库，若仓库满，生产者将等待； （2）消费者从仓库中取出物品，同一时间只能有一个消费者取出物品，若仓库空，消费者等待； （3）生产者将物品放入仓库时消费者不能同时取； （4）消费者取物品时生产者不能放入物品。问题分析问题分析同步问题描述：同步问题描述： 当缓存满时，生产者必须等消费者从缓当缓存满时，生产者必须等消费者从缓存取走产品。设同步信号量为存取走产品。设同步信号量为empty，其，其初值为？。初值为？。 当缓存空时，消费者必须等生产者当缓存空时，消费者必须等生产者放产品至缓存。设同步信号量为放产品至缓

2、存。设同步信号量为full，其初，其初值为？。值为？。问题分析问题分析互斥问题描述：互斥问题描述： 将有界缓存视为临界资源。由于两个进将有界缓存视为临界资源。由于两个进程都要访问缓冲区，但是无论是生产者进程都要访问缓冲区，但是无论是生产者进程向缓冲区放入产品，还是消费者进程从程向缓冲区放入产品，还是消费者进程从缓冲区取走产品，都不能同时进行。所以，缓冲区取走产品，都不能同时进行。所以，两个进程访问缓冲区必须互斥地执行。两个进程访问缓冲区必须互斥地执行。 设互斥信号量设互斥信号量mutex的初始值为的初始值为1，以实现两进程对缓冲区访问的互斥。以实现两进程对缓冲区访问的互斥。问题分析问题分析 所

3、以，为了实现生产者进程和消费者进所以，为了实现生产者进程和消费者进程的同步与互斥，设置三个信号量：程的同步与互斥，设置三个信号量： 两个同步信号量两个同步信号量empty和和full， 一个互斥信号量一个互斥信号量mutex， 并在这三个信号量上施加正确的并在这三个信号量上施加正确的P、V操作，就可保障两进程正确无误地运行。操作，就可保障两进程正确无误地运行。思考思考 （1）若将两个）若将两个P操作互换位置，结果如何？操作互换位置，结果如何？ （2）若将两个）若将两个V操作互换位置，结果又如操作互换位置，结果又如何？何？应注意的问题（总结）应注意的问题（总结） (1) 在每个程序中必须先做在每

4、个程序中必须先做P(mutex)后做后做V(mutex)，二者要成对出现。，二者要成对出现。(2) 对同步信号量对同步信号量full和和empty的的P、V操作同样必须成对出现，但它们分别位于操作同样必须成对出现，但它们分别位于不同进程的代码中。不同进程的代码中。(3) 无论在生产者进程中还是在消费者无论在生产者进程中还是在消费者进程中，两个进程中，两个P操作的次序都不能颠倒。应操作的次序都不能颠倒。应先执行同步信号量的先执行同步信号量的P操作，再执行互斥信操作，再执行互斥信号量的号量的P操作；否则可能造成进程死锁操作；否则可能造成进程死锁问题提出问题提出 设有4个哲学家围坐在一张圆桌前讨论问

5、题和进餐。在在讨论时每人手中什么都不拿，当需要进餐时，每人需要用刀和叉各一把。餐桌上的布置如图所示，共有两把刀和两把叉，每把刀或叉供相邻的两个人使用。 请用信号量及PV操作说明4位哲学家的同步过程。问题分析和解题步骤问题分析和解题步骤 （1）确定进程的个数及其工作内容解题步骤解题步骤 （2）确定互斥信号量的个数、含义 （3）用P、V操作描述关系问题提出问题提出 有5个哲学家他们围坐在一张圆桌旁，每人面前有一菜盘，各菜盘之间有一根筷子。 每个哲学家或思考问题或就餐，当思考问题时放下筷子，饥饿的时候就吃菜。 想要夹菜时必须获得两根筷子，且每人且每人只能从自己的左边和右边去取筷子，只有只能从自己的左

6、边和右边去取筷子，只有在他拿到两只筷子时才能进餐。在他拿到两只筷子时才能进餐。就餐后放下筷子以供别人使用，自己继续思考问题。哲学家筷子盘子哲学家1号哲学家5号哲学家4号哲学家2号哲学家3号15324哲学家1号哲学家4号哲学家2号哲学家3号15324哲学家5号先拿左,拿到后再拿右,成功后进餐.吃完后先放左再放右.虽可保证不会有相邻的同时进餐,但可能死锁,如动画所示.此时没有一个哲学家可以完成进餐.解决方法解决方法 （1）至多只允许有）至多只允许有4位哲学家同时去拿左边的筷位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他

7、用过的两只筷子，从而使更在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。多的哲学家能够进餐。 （2）仅当哲学家的左、右两只筷子均可用时，）仅当哲学家的左、右两只筷子均可用时，才允许他拿起筷子进餐。才允许他拿起筷子进餐。 （3）规定奇数号哲学家先拿他左边的筷子，然）规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；而偶数号哲学家则相反。后再去拿右边的筷子；而偶数号哲学家则相反。最后总会有一位哲学家能获得两只筷子而进餐最后总会有一位哲学家能获得两只筷子而进餐。哲学家1号哲学家4号哲学家2号哲学家3号15324哲学家5号此时5号哲学家被禁止拿筷子.1号哲学家拿起他右边即5号哲学家

8、左边的筷子.1号哲学家开始进餐,完成后放下筷子,其它哲学家开始进餐哲学家1号哲学家4号哲学家2号哲学家3号哲学家5号设1号进餐,则3,4两位哲学家可以拿筷子1号进餐完毕,放下筷子,先左后右.1号放下左边筷子的同时,3号可拿起右边筷子3号开始进餐,同时1号放下右边的筷子此时4号条件不再满足,放下筷子.此时5号条件满足,可在下一时钟周期拿左筷子哲学家4号哲学家1号哲学家2号哲学家3号1524哲学家5号这种方法将出现1,2号哲学家单键1号筷子,3,4号哲学家竞争3号筷子的情况.而5号没有人与他竞争,得到左边的筷子若4号在与3号的竞争中得到筷子,则与5号竞争4号筷子.无论无论4号号5号谁号谁得到得到4

9、号筷子号筷子,都都有一个可以进餐有一个可以进餐若4号在与3号的竞争中没有得到筷子,则5号得到4号筷子,进餐问题提出问题提出 某数据库有一个写进程、多个读进程，某数据库有一个写进程、多个读进程，它们之间读、写操作的互斥要求是：写进它们之间读、写操作的互斥要求是：写进程运行时，其他读、写进程不能对数据库程运行时，其他读、写进程不能对数据库进行操作。读进程之间不互斥，可以同时进行操作。读进程之间不互斥，可以同时读数据库。请用信号量及读数据库。请用信号量及PV操作描述这一操作描述这一组进程的工作过程。组进程的工作过程。问题分析问题分析 本题涉及对同一个数据库的读写操作。当多个本题涉及对同一个数据库的读

10、写操作。当多个进程对其读时，因不改变其中的数值，可以不加进程对其读时，因不改变其中的数值，可以不加限制。当既有的读进程，又有写进程时，应加以限制。当既有的读进程，又有写进程时，应加以限制。此时，数据库就是一个临界资源，读写进限制。此时，数据库就是一个临界资源，读写进程必须对其进行互斥操作。程必须对其进行互斥操作。 因为写进程执行时，不能执行其他读写进程，因为写进程执行时，不能执行其他读写进程，所以还必须设置一个计数器统计读进程的个数。所以还必须设置一个计数器统计读进程的个数。如果是第一个读进程，就与写进程竞争数据库。如果是第一个读进程，就与写进程竞争数据库。如果是最后一个读进程，就释放数据库。

11、因计数如果是最后一个读进程，就释放数据库。因计数器是一个临界资源，所以多个读进程对计数器的器是一个临界资源，所以多个读进程对计数器的操作又是互斥操作。操作又是互斥操作。这是一个互斥问题，也是典型的读者和写者问题。这是一个互斥问题，也是典型的读者和写者问题。解题步骤解题步骤 （1）确定进程的个数及工作。本题只有读写两类进程，各自的工作如图所示。 （2）确定信号量的个数、含义及PV操作。 本题应当设置2个信号量和1个共享变量：count为共享变量，记录当前正在读数据库的进程数目； rmutex为读互斥信号量，使进程互斥地访问共享变量count，其初值为1； 对于写进程与读进程、写进程与写进程来说，

12、数据库是临界资源，一次只能被一个进程使用。所以设置wmutex为互斥信号量，其初值为“1”。 所以，本题有两个临界资源：共享变量count和数据库，对它们要实施互斥操作。 （3）用类C语言描述同步关系。课堂习题课堂习题 三个进程三个进程P1，P2，P3协作解决文件打协作解决文件打印问题，印问题，P1将文件记录从磁盘读入内存的将文件记录从磁盘读入内存的缓冲区缓冲区1，每执行一次读一个记录；，每执行一次读一个记录；P2将缓将缓冲区冲区1的内容取出放到缓冲区的内容取出放到缓冲区2中；中；P3将缓将缓冲区冲区2的内容打印出来，每执行一次打印一的内容打印出来，每执行一次打印一个记录。缓冲区的大小和一个记录大小一个记录。缓