|
|
|
在多道程序设计系统中，同一时刻可能有许多进程，这些进程之间存在两种基本关系：竞争关系和协作关系。
|
|
|
|
第一种是竞争关系，系统中的多个进程之间彼此无关，它们并不知道其他进程的存在。例如，批处理系统中建立的多个用户进程，分时系统中建立的多个终端进程。由于这些进程共用了一套计算机系统资源，因而，必然要出现多个进程竞争资源的问题。当多个进程竞争共享硬设备、变量、表格、链表、文件等资源时，可能导致处理出错。
|
|
|
|
（1）进程的互斥（Mutual Exclusion）。
|
|
|
|
是解决进程间竞争关系的手段。指若干个进程要使用同一共享资源时，任何时刻最多允许一个进程去使用，其他要使用该资源的进程必须等待，直到占有资源的进程释放该资源。临界区管理可以解决进程互斥问题。
|
|
|
|
第二种是协作关系，某些进程为完成同一任务需要分工协作。
|
|
|
|
（2）进程的同步（synchronization）。
|
|
|
|
是解决进程间协作关系的手段。指一个进程的执行依赖于另一个进程的消息，当一个进程没有得到来自于另一个进程的消息时则等待，直到消息到达才被唤醒。
|
|
|
|
不难看出，进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源。
|
|
|
|
|
|
下面通过例子来进一步阐明进程同步的概念。著名的生产者－消费者（Producer-Consumer）问题是计算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等。解决好了生产者－消费者问题就解决好了一类并发进程的同步问题。
|
|
|
|
生产者－消费者问题表述如下：有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上，故又叫有界缓冲问题。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；类似地，只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。
|
|
|
|
|
|
|
|
其中，假如一般的高级语言都有sleep（）和wakeup（）这样的系统调用。从上面的程序可以看出，算法是正确的，两进程顺序执行结果也正确。但若并发执行，就会出现错误结果，出错的根源在于进程之间共享了变量counter，对counter的访问未加限制。
|
|
|
|
生产者和消费者进程对counter的交替执行会使其结果不唯一。例如，counter当前值为8,如果生产者生产了一件产品，投入缓冲区，拟做conuter加1操作。同时消费者获取一个产品消费，拟做counter减1操作。假如两者交替执行加或减1操作，取决于它们的进行速度，counter的值可能是9，也可能是7，正确值应为8。
|
|
|
|
操作系统实现进程同步的机制称为同步机制，它通常由同步原语组成。不同的同步机制采用不同的同步方法，迄今己设计出许多同步机制，最常用的同步机制：信号量及PV，管程。
|
|
|
|
|
|
1965年荷兰的计算机科学家E.W.Dijkstra提出了新的同步工具——信号量和P、V操作。他将交通管制中多种颜色的信号灯管理交通的方法引入操作系统，让两个或多个进程通过信号量（semaphore）展开交互。信号量仅能由同步原语对其进行操作，原语是操作系统中执行时不可中断的过程，即原子操作（Atomic Action）。Dijkstra发明了两个同步原语：P操作和V操作（荷兰语中“测试（Proberen）”和“增量（verhogen）”的头字母。利用信号量和P、V操作既可以解决并发进程的竞争问题，又可以解决并发进程的协作问题。
|
|
|
|
使用PV操作实现同步时，对共享资源的管理分散在各个进程之中，进程能直接对共享变量进行处理，因此，难以防止有意或无意的违法同步操作，而且容易造成程序设计错误。如果能把有关共享变量的操作集中在一起，就可使并发进程之间的相互作用更为清晰，更容易编写出正确的并发程序。
|
|
|
|
|
|
在1974年和1975年，霍尔（Hoare）和汉森（Brinch Hansen）提出了一个新的同步机制——管程。把系统中的资源用数据结构抽象地表示出来，因此，对资源的管理就可用数据及在其上实施操作的若干过程来表示；对资源的申请和释放通过过程在数据结构上的操作来实现。而代表共享资源的数据及在其上操作的一组过程就构成了管程，管程被请求和释放资源的进程所调用。
|
|
|
|
管程是一种程序设计语言结构成分，便于用高级语言来书写，它和信号量有同等的表达能力。管程是由若干公共变量及其说明和所有访问这些变量的过程所组成的；进程可以互斥地调用这些过程；管程把分散在各个进程中互斥地访问公共变量的那些临界区集中了起来。管程可以作为语言的一个成分，采用管程作为同步机制便于用高级语言来书写程序，也便于程序正确性验证。
|
|
|
