PV操作

• 进程间的制约

进程1、进程2共享打印机缓冲区（公有资源），显然它们应互斥地向缓冲区写数据——间接制约
进程1、进程2共享它们之间的缓冲区（私有资源），显然应同步地使用缓冲区——直接制约

• 产生制约的原因

进程并发执行——>资源共享
资源有限——>资源竞争
制约的分类
1.间接制约（由共享和竞争公共资源引起的制约）一组在异步环境下的并发进程，由于不允许并发进程交叉使用共享公有资源，从而限制各进程的执行速度的过程称为并发进程间的间接制约
2.直接制约（由共享和竞争私有资源引起的制约）
一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发执行进程间的直接制约
互斥：因间接制约而形成的进程执行方式
同步：因直接制约而形成的进程执行方式

• 临界资源与临界区

临界资源
任意时刻只允许一个进程使用的资源
如：打印机、键盘、一些数据、表格、队列等
临界区
访问临界资源的程序（程序段），即不允许并发进程交叉执行的程序（程序段）
如：写打印机缓冲区的程序，……
临界资源的访问方式——互斥

进程互斥执行应满足的准则

• 不能假设各并发进程的相对执行速度

    各并发进程享有平等的、独立的竞争和使用共有资源的权利
    在不采取任何措施的条件下，在临界区内任一指令结束时，其它并发进程可以进入临界区

• 并发进程中的某个进程不在临界区时，它不阻止其它进程进入临界区
• 并发进程中的若干个进程申请进入临界区时，只允许一个进程进入
• 并发进程中的某个进程从申请进入临界区开始，应在有限时间内进入临界区，也应在有限时间之内退出临界区

• 信号量

例
交通系统中的信号灯——它表示当前道路是否可以通行
信号量——某种资源可以使用的状况，用整型变量s表示
s>0——资源还有s个可供使用
s=0——资源也用尽
s<0——有| s |个进程等待使用资源

• 用P、V操作实现进程互斥

原理
设信号量S为全局变量，初值为S=1
S对应的资源同一时刻最多只能有一个进程使用
访问资源前调用P操作，访问结束时调用V操作
使用资源的两个互斥进程描述为
     PA                                           PB
        ……                                          ……
        P(S)                                          P(S)
        <资源调用>                               <资源调用>
        V(S)                                          V(S)
        ……                                          ……
例
设A，B两站之间是单轨铁路，用P、V操作对通过该段铁路的列车设置安全保护

• 进程同步的实现

例
计算进程PC将计算结果写到缓冲区Buf中，打印进程PP从Buf中取出数据进行打印。要求是
只有Buf为空时，PC才能写入数据；
只有Buf为满时，PP才能取出数据
从Buf中取出数据后，Buf为空
初始时Buf为空
分析
显然PC与PP在执行时必须协调速度，即对Buf的操作应该是：PC写，PP取，PC写，PP取， PC写，PP取，……
问题要求PC与PP同步
实现同步的方法可以是
PP等PC写之后再取
PC等PP取之后再写

求解
设Buf有两个状态：Bufempty，Buffull
用State记Buf的状态……
PP与PC为
PP                                      PC
    ……                                       ……
    repeat                                   repeat
    until State=Bufempty                     until State=Buffull
    计算                                     取出Buf中的内容
    计算结果放入Buf                          Buf清空
    State=Buffull                            State=Bufempty
    ……                                     ……
上述Bufempty，Buffull成为PP与PC之间的公用变量，但对系统或其它进程来讲并不知道它们的存在，故称其为PP与PC的私有信号量

• 用P、V操作实现进程同步

原理
为并发进程设置信号量，
初始化它们的值
用P、V操作限定进程的执行顺序
同步进程的模式
PA                          PB
    ……                    ……
    P(S)                    P(T)
    <使用同步资源>     <使用同步资源>
    V(T)                    V(S)
    ……                    ……

• 生产者—消费者问题

进程互斥和同步问题可以抽象为生产者—消费者问题

生产者生产出产品后，消费者才能消费
当部分产品消费后，生产者才继续生产
一件产品，不能既在生产又在消费
该问题可形式化为
有界缓冲区共n个单元
生产者进程向缓冲区中写数据，每次写一个单元
消费者进程读缓冲区中的数据，每次写一个单元
缓冲区至少有一个单元有数据（满）时，才能读
缓冲区至少有一个单元无数据（空）时，才能写
生产者进程与消费者进程不能同时操作缓冲区

假设：PA——生产者进程， PB——消费者进程
生产者与消费者的互斥
设公共信号量：mutex，初值为1
     PA                           PB
         ……                       ……
         P（mutex）               P（mutex）
         生产者生产               缓冲区中取出数据
         数据放入缓冲区           消费者消费
         V（mutex）               V（mutex）
         ……                              ……
生产者与消费者的同步
设生产者进程的私有信号量：avail——当前可用的缓冲区单元数，初值为n
设消费者进程的私有信号量：full——缓冲区中有数据的单元数，初值为0
生产者与消费者的同步为：
         PA                             PB
         ……                          ……
         P（avail）                  P（full）
         生产者生产                  缓冲区中取出数据
         数据放入缓冲区              消费者消费
         V（full）                   V（avail）
         ……                          ……

生产者与消费者问题的解
        PA                             PB
         ……                          ……
         P（avail）                  P（full）
         P（mutex）                  P（mutex）
         生产者生产                  缓冲区中取出数据
         数据放入缓冲区              消费者消费
         V（full）                   V（avail）
         V（mutex）                  V（mutex）
         ……                          ……
问题

• k个生产者之间的生产互斥吗？为什么？

• m个生产者之间的生产互斥吗？为什么？

• 如何才能使得多个生产者可以同时生产？多个消费者之间可以同时消费？