操作系统原理-处理机管理-第二章.ppt

先来看解决实现进程同步的一般的解决方案 根据进程间的制约关系，来决定设置信号量。 * 生产者—消费者：是典型的进程同步问题，也叫有界缓冲区问题。可以用于其他进程同步的借鉴。 生产者-消费者问题是对相互合作的进程之间同步问题的一种抽象，因此介绍使用信号量来解决生产者和消费者问题对其他问题都有典型的借鉴作用。 例如，在输入和计算进程间，计算进程是消费者；而在计算和打印进程间，计算进程是生产者。 在说明如何用信号量机制解决生产者和消费者问题之前，先看两个概念：满缓冲区和空缓冲区。 满缓冲区：装有产品的缓冲区 空缓冲区：没装产品的缓冲区（没生产或该缓冲区的产品被消费） 解这类问题和使用信号量来进行互斥的方法是一致的： 1）分析进程之间的制约关系； 2）设置信号量，并说明信号量的物理含义。 3）写出算法 * 必须使用信号量来保证生产者和消费者先生产后消费的同步关系，以及进程访问临界区的互斥关系。 * * 一、Empty：初值为n： 1）P（empty）：值-1，判断是否有缓冲区可以放产品，如果大于等于0，表示有空的缓冲区可以放产品，当产品放到缓冲区全满时，值为0，不能继续生产了 2）V（empty）：值+1，表示消费者取走了一个产品，多了一个空缓冲区，通知生产者可以继续生产 二、Full：初值为0 1）P（full）：值-1，判断是否有产品可以消费，如果大于等于0，表示有产品可以被消费者消费 2）V（full）：值+1，表示生产者生产了一个产品，通知消费者可以进行消费 * 1、当P（S）和V（S）不成对出现时，可能导致程序出现错误。(如V(empty)忘记写了) 1）当消费者消费完产品后，由于没有执行V(empty)，导致生产者生产n个产品之后，没有缓冲区可以放产品 2、当生产者P(empty)和P(mutex)交换顺序，则 1）每次都是先抢得互斥锁之后，再判断是否有空余缓冲区，假设此时没有空余缓冲区，则生产者阻塞等待消费者进行消费，同时也不会释放互斥锁 2）消费者P(full)判断缓冲区有产品，再去抢互斥锁，由于生产者被阻塞，而互斥锁没有被释放，则消费者也被阻塞 3）消费者被阻塞后，始终不能执行V（empty），也即生产者始终收不到信号，这样产生了相互等待； 4）这就产生了所谓的死锁。 * 一、这是另一个典型的进程同步机制，还是按照前面所说的步骤进行分析： 1、分析各进程之间的制约关系； 2、设置信号量，给出信号量物理含义，以及信号量初值 3、写出利用信号量进行控制的各进程的流程/算法 二、相互的制约关系 1、写者和写者是互斥的； 2、读者和写者是互斥的；读者必须等待写者写完后，才能访问；写者必须等待所有读者全部出来以后，才能访问。 3、读者和读者是共享的：一个读者在里面，另一个读者也可以进去； 问题： 1、对于写者和写者的互斥，读者和写者的互斥，可以使用一个信号量来实现互斥，进入的时候加锁，出来的时候解锁； 2、但如果这样，读者和读者怎么能共享访问？ 思路：读者进来的时候，如果里面仍然有读者，则可以进去，否则，需要抢这把锁。 那如何判断里面仍然有读者呢？设置一个变量，读者进来的时候+1，读者出去的时候减1，进入时，如果为0，则要竞争这把互斥锁。出来时，如果为0，则解锁。 * 1、设置RW_mutex：进入的时候竞争这把锁，出来的时候释放这把锁，则可以保证同时只有一个读者或一个写者进入临界区； 2、显然，RW_mutex限制了多个读者共享； 3、只有第一个读者需要和写者互斥，可以设置一个变量RC（read count），来一个读者+1，走一个读者-1 4、读者共享：第一个进入的读者P(RW_mutex)，最后一个出去的读者V(RW_mutex)，这样可以达到当存在读者时，禁止写者进入，但不禁止新读者进入的目标 * 写者比较简单，先看写者。 * 因为红方、黑方都需要等待一个信号，因此设置两个信号量 * 另外一种解法：设hei的初值为0，其物理含义也发生了变化（P46） 1、仍然是设置两个信号量 1）hong，代表是否应该由红走子，初值为1 2）hei，代表是否应该由黑走子，初值为0 红方 P(hong) 走子 V（hei） 黑方 P（hei） 走子 V（hong） * 因为红方、黑方都需要等待一个信号，因此设置两个信号量 * 另外一种解法：设hei的初值为0，其物理含义也发生了变化（P46） 1、仍然是设置两个信号量 1）hong，代表是否应该由红走子，初值为1 2）hei，代表是否应该由黑走子，初值为0 * 这是个前驱后续图，从上