2.2.4 并发进程的相互制约——同步与互斥
并发是操作系统最基本的特征,多道环境下的操作系统支持进程并发,并发进程的运行面临很多问题,诸如进程间的通信、资源的共享与争用、多个进程运行速度的协调等,本小节讨论单机多道环境下的并发进程关系。
并发的进程既有独立性又有相互制约性。独立性是指各进程都可以独立向前推进;制约性则是指进程之间有时会相互制约。这种制约分为两种,一种是直接制约,一种是间接制约。直接制约源于进程间的合作,间接制约源于进程对资源的共享和争用。一般称进程的直接制约为同步关系,间接制约为互斥关系。进程间的同步与互斥需要操作系统设有控制措施,这是并发系统的关键问题,关系到操作系统的成败。
1.互斥
当并发进程竞争使用同一个资源时,它们之间会发生冲突。比如,两个或多个进程在执行过程中需要访问同一个资源,它们之间没有任何信息交换,每个进程不知道其他进程的存在,并且每个进程也不受其他进程的影响。但是,一旦操作系统将这个竞争资源分配给其中一个进程,其他进程就必须等待,直到前者完成任务释放资源为止,这就是进程的互斥。
竞争资源的进程首先面临的是互斥的要求,这种要求与竞争的资源特性有关,某些资源由于其物理特性,一次只允许一个进程使用,不能多进程同时共享,我们称其为临界资源。多个进程之间需要互斥使用临界资源,即一个进程正在访问临界资源,另一个要访问该资源的进程必须等待,直到前者使用完毕并释放之后,后者才能使用。许多物理设备属于临界资源,如打印机、磁带机;许多变量、数据、队列也可以由若干进程共享使用,这时这些资源也是临界资源,被称为软临界资源,如车票文件。软临界资源互斥使用的原因是为了避免与时间有关的错误(如2.2.1节中的火车售票系统),导致错误的原因有两个:一是共享了变量(例中的车票数量变量),二是同时使用了这个变量。所谓同时是指在一个进程开始使用但尚未结束使用期间,另一个进程也开始了使用(例中的同时读出、写入车票数量变量)。
临界资源的物理特性是不能改变的,于是转而讨论访问临界资源的程序(进程),我们将一个进程分为两部分考虑:使用临界资源的程序和不使用临界资源的程序,并发进程在使用临界资源时必须互斥使用,而在不使用临界资源时则没有约束。为了控制进程的互斥,可将这两段程序从概念上分开,把访问临界资源的程序段称为临界区(CS,Critical Section),而把其他程序段统称为非临界区(non_CS),并且把与同一个临界资源相关联的临界区称为同类临界区。这样,互斥使用临界资源的问题就可以转变为控制不允许进程同时进入各自的同类临界区的问题。使用临界区的基本要求总结如下。
·互斥进入:在共享同一个临界资源的所有进程中,在同一时间,每次至多有一个进程处在临界区内,即只允许一个进程访问该临界资源。
·不互相阻塞:如果有若干进程都要求进入临界区,必须在有限时间内允许一个进程进入,不应互相阻塞,以至于哪个进程都无法进入。
·公平性:进入临界区的进程要在有限时间内退出,不让等待者无限等待。
要想满足以上3个基本要求,应该在临界区前后都加以标识和控制,每一个进程的描述如下。
可以看出,解决互斥问题的关键在于临界区的入口控制代码和出口控制代码,计算机专家从20世纪60年代中期开始,不断提出代码中控制互斥的相应算法,不断改进,直到使用信号量机制和管程概念才为用户提供了简单的、成熟的解决互斥问题的方法。
2.同步概念与同步问题
同步(Synchronism)是指有协作关系的进程之间需要调整它们之间的相对速度。例如,两个合作进程,计算进程(Computing)和打印进程(Printer),共同使用同一个单缓冲区(一个存储单位),Computing进程对数据进行计算,并把结果送入单缓冲区;然后由Printer进程把单缓冲区的数据打印出来。这是两个具有协作关系的进程,在运行过程中存在一种制约关系:当计算结果未出来前,Printer进程必须等待;反之,当上一次计算结果还在缓冲区未被打印时,Computing进程不能向其中送入新的计算结果,计算进程必须等待。这就需要调整它们的相对速度,即同步。同步现象在计算机内到处可见,其实,互斥也是一种特殊的同步,而同步时共享的资源(缓冲区)也是临界资源,因此有时将同步和互斥面临的问题统称为同步问题。
为了有效管理进程的同步和互斥,实现进程互斥地进入自己的临界区,操作系统设置了专门的同步机制来协调各进程间的运行。所有同步机制都应遵循下述4条准则。
①空闲让进。当无进程进入临界区,即临界资源处于空闲状态时,应允许一个请求进入临界区的进程立即进入临界区。
②忙则等待。当已有进程进入临界区,即临界资源正在被访问,其他请求进入临界区的进程必须等待,以保证对临界资源的互斥访问。
③有限等待。对请求进入临界区的进程,应保证在有限时间内能够进入临界区,避免“死等”。
④让权等待。当进程不能进入自己的临界区时,应立即释放已占用资源,以免产生死锁。