题目 计算机操作系统进程同步与互斥基本理论及问题研究
摘要
在OS中引入进程后，虽然提高了资源的利用率和系统的吞吐量，但由于进程的异步性，也会给系统造成混乱，尤其是在他们征用临界资源时。进程同步包括进程的同步与进程的互斥两个方面。进程同步的主要任务是对多个相关进程在执行次序上进行协调，以使并发执行的诸进程之间能有效的共享资源和相互合作，从而使程序的执行具有可再现性。 关键词 进程同步、互斥 信号量 同步问题 正文
一、关于进程同步的基本理论 1、 进程同步与互斥概念
同步：指多个进程中发生的事件存在着某种时序关系，他们必须按规定时序执行，
以共同完成一项任务。如：4*100接力赛、工厂的流水线、商品的入库和出库等。
互斥：多个进程不能同时使用同一资源。如：几个同学去图书馆借同一本书、交叉
路口抢车道、争抢篮板球等。
2、 临界资源与临界区的概念
临界资源：一次仅允许一个进程使用的资源。许多硬件资源如打印机、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实现对这种资源的共享。
临界区：不论是硬件临界资源，还是软件临界资源，多个进程必须互斥的它进行访问。人们把在每个进程中访问临界资源的那段代码称为临界区
3、 同步机制应遵循的规则
为实现进程互斥地进入自己的临界区，可用软件方法，更多的是在系统中设置专门的同步机构来协调各进程间的运行。所有同步机制都应遵循下述四条准则：
1】 空闲让进。当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求
进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。
2】 忙则等待。当已有进程进入临界区时，表明临界资源正在被访问，因而其它试图进
入临界区的进程必须等待，以保证对临界资源的互斥访问。 3】 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区， 以免陷入“死等”状态。
4】让权等待。当进程不能进入自己的临界区时，应立即释放出处理机，以免进程陷入“忙等”状态。
4、 信号量机制
1965年。，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制又得到了很大的发展，它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在，信号量机制已被广泛地应用于单处理机和多处理机系统以及计算机网络中。 整型信息量
最初由Dijkstra把整型信号量定义为一个用于表示资源数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作wait(s)和signal(s)来访问。很长时间以来这两个操作一直被分别称为P、V操作。 记录型信号量
记录型信号量机制是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”
的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表指针L，用于链接上述的所有等待进程。
AND型信号量
AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部的分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其他所有可能为之分配的资源也不分配给它。亦即，对若干个临界资源的分配，采取原子操作方式：要么把它所请求的资源全部分配到进程，要么一个也不分配。 信号量集
在记录型信号量机制中，wait(s)或signal(s)操作仅能对信号量施以加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，便要进行N次wait(s)操作，显然这是低效的。此外，在有些情况下，当资源数量低于某一下线值时，便不与以分配。因而，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值。基于上述两点，可以对AND信号量机制加以扩充，形成一般化的“信号量集“机制。 5、 信号量的应用
（1）利用信号量实现进程互斥
为使多个进程能互斥地访问某临界资源，只须为该资源设置一互斥信号量mutex，并设其初始值为1，然后将各进程访问该资源的临界区CS置于wait（mutex）和siganl（mutex）操作之间即可。这样，每个欲访问该临界资源的进程在进入临界区之前，都要先对mutex执行wait操作，若该资源此刻未被访问，本次wait操作必然成功，进程便可进入自己的临界区，这时若再有其他进程的也欲进入自己的临界区，此时由于对mutex执行wait操作定会失败，因而该进程阻塞，从而保证了该临界资源能被互斥的访问。当访问临界资源的进程退出临界区后，又应对mutex执行siganl操作，以便释放该临界资源。 （2）利用信号量实现前趋关系
还可利用信号量来描述程序或语句之间的前驱关系。设有两个并发执行的进程P1和P2。P1中有语句S1;P2中有语句S2。我们希望在S1执行任务后再执行S2。为实现这种前驱关系，我们只须使进程P1和P2共享有一个公用信号量S，并赋予其初始值为0，将siganl（S）操作放在语句S1后面；而在S2语句前面插入wait（S）操作，即 在进程P1中，用S1;signal(S); 在进程P2中，用wait（S）；S2;
6、 管程机制
虽然信号量机制是一种既方便又有效地进程同步机制，但每个要访问临界资源的进程都必须自备同步操作分散在各个进程中，这不仅给系统管理带来了麻烦，而且还会因同步操作的使用不当而导致系统死锁。在解决上述问题中便产生了一种新的进程同步工具---管程。
管程有四部分组成：管程的名称、局部于管程内部的共享数据结构说明、对该数据结构进行操作的一组过程、对局部于管程内部的共享数据设置初始值的语句。
二、经典进程同步与互斥问题
进程同步与互斥的经典问题生产者---消费者问题可以帮助我们更好的理解进程同步的概念和实现方法。生产者—消费者（producer—consumer）问题是一个著名的进程同步问题。它描述的是：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生
产者进程与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，既不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。
1、 利用记录型信号量解决生产者---消费者问题
假定在生产者和消费者之间的公用缓冲池中，具有n个缓冲区，这时可利用互斥信号量mutex实现诸进程对缓冲池的互斥使用。利用信号量empty和full分别表示缓冲池中空缓冲区和满缓冲区的数量。又假定这些生产者和消费者相互等效，只要缓冲池未满，生产者便可将信息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池中取走一个消息。 2、 利用AND信号量解决生产者---消费者问题
对于生产者—消费者问题，也可利用AND信号量来解决，即用Swait(empty,mutex)来代替wait(empty)和wait(mutex);用Ssignal(mutex,full)来代替signal(mutex)和siganl(full);用Swait（full，mutex）来代替wait（full）和wait（mutex），以及用Ssiganl（mutex，empty）代替Ssiganl（mutex）和Ssiganl(empty)。
3、 利用管程解决生产者----消费者问题
在利用管程方法来解决生产者—消费者问题时，首先便是为它们建立一个管程，并命名为ProclucerConsumer，或简称为PC。其中包括两个过程：
（1） put（item）过程。生产者利用该过程将自己生产的产品投放到缓冲池中，并用整
型变量count来表示在缓冲池中已有的产品数目，当count>=n时,表示缓冲池已满,生产者需等待。
（2） get（item）过程。消费者利用该过程从缓冲池中取出一个产品，当count<=0时，
表示缓冲池中已无可取用的产品，消费者请等待。
总结：
OS引入进程后，由于进程的异步性，可能会导致程序执行结果的不确定性，使程序执行时出现不可再现性。进程互斥与同步的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。 参考文献：1】《计算机操作系统》 西安电子科技大学出版社 汤小丹 梁红兵 哲凤屏 汤子瀛 编著
2】计算机互联网