操作系统中互斥与同步问题求解方法的探析

唐伎玲，黄 葵，谷 赫

(长春大学 计算机科学技术学院，长春130022)

0 前言

多个进程在并发执行时，由于共享同一变量或系统资源，如打印机等，使这些并发执行的进程只能互斥地访问，致使进程之间形成了相互制约的关系，称为进程互斥。

一组进程，为协调其推进速度，在某些关键点处需要相互等待与相互唤醒，进程之间这种相互制约的关系称为进程同步。

互斥与同步是操作系统与并发程序设计的核心问题，为此操作系统必须提供用于实现同步的机制。从本质上讲，同步工具就是能用于进程(线程)等待或唤醒的机制，信号量机制是解决同步问题的常用工具。

如何使用信号量机制解决各种同步问题，需要准确理解并牢记信号量机制的定义，还需要分析和学习典型例子，并通过一定数量的练习来提高解题的技巧。

1 经典案列

1.1 图书借阅系统

(x:某种书册数，设当前x=1)。

如图1 左图所示，在并发环境下，两个终端程序若按图中标记的数字顺序并发执行，则会出现将一本书借给两个读者的错误。为了避免出现这类的错误，对共享变量X 的访问必须互斥，设置信号量mutex，初值为1，控制的代码流程如图1 右图所示。

图1 图书借问系统

1.2 司机－售票员问题。

在并发环境下，司机进程和售票员进程向前推进过程中有两个制约关系，如图2 左图所示。这是典型的同步控制，设置信号量s1 和s2，初值均为0，控制的代码流程如图2 右图所示。

图2 司机－售票员问题

1.3 生产者－消费者问题

生产者－消费者问题是一个著名的进程同步问题。它描述的是:有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行，在两者之间设置了一个具有n 个缓冲区的缓冲池，生产者进程将它所生产的产品放入一个缓冲区中;消费者进程可从一个缓冲区中取走产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品，也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。

分析问题:将产品和缓冲区视为组合资源，生产者进程和消费者进程的推进过程中要不断使用和释放这对组合资源，因此设两个信号量empty=n 和full=0，分别来管理缓冲区和产品。生产者进程在生产产品放入缓冲区时，要先申请一个缓冲区，然后释放一个产品，因此先执行wait(empty)，后执行signal(full)。消费者从缓冲区取产品时，要先申请一个产品，然后释放一个缓冲区，因此要先执行wait(full)，后执行signal(empty)。又因缓冲区是多个进程共同访问，必须互斥，因此还需设置互斥信号量mutex=1，控制的主要代码如图3 所示。

1.4 读者－写者问题

所谓“读者－写者问题”是指一个数据文件或记录可被多个进程共享，允许多个进程同时读一个共享对象，因为读操作不会使数据文件混乱。但不允许一个写进程和其他读进程或其它写进程同时访问共享对象。因为这种访问将会引起文件内容的混乱。

分析问题:这是多个进程在共享过程中又有互斥控制的问题。因为写进程与写进程之间、写进程与读进程之间互斥，故设置一个信号量w=1。又因读进程之间共享，让第一个读进程执行wait(w)操作，最后一个读进程执行signal(w)。为了区分读进程，设置一个统计变量read_count，初值为0，每当一个读进程到达执行read_count+1，离开时执行read_count－1;read_count=1 时表示第1 个读进程到达，当read_count=0 时表示最后一个读进程要离开。由于read_count 是多个读进程共享变量，必须互斥访问，为此再设置一个信号量r=1。整个问题同步控制的主要代码如图4 所示。

图3 生产者－消费者问题

1.5 父母儿女吃水果问题

桌上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲则总是放香蕉到盘子中，一个儿子专等吃盘中的香蕉，而一个女儿专等吃盘中的苹果，试写出这两个并发进程能正确执行的程序。

分析问题:盘子放一个水果，这是互斥控制;女儿吃父亲放的苹果，儿子吃母亲放的香蕉，这是两个同步控制，因此设置一个互斥信号量S=1，初值为1，两个同步信号量a 和b，初值均为0。控制代码的流程如图5 所示。

图4 读者－写者问题

图5 父母儿女吃水果问题(一)

修改上述问题，桌上有一个盘子，可以存放两个水果，但每次存和取一个水果。父亲总是放苹果到盘子中，而母亲则总是放香蕉到盘子中，两个儿子专等吃盘中的香蕉，而两个女儿专等吃盘中的苹果，试写出这两个并发进程能正确执行的程序。

分析问题:由于盘子可以放两个水果，故设置同种资源信息量E=2，盘子每次放取水果只能一个，因此设置互斥信号量S=1，两个同步信号量a=0 和b=0。程序流程如图6 所示。

图6 父母儿女吃水果问题(二)

2 求解规律

通过上述案例的求解分析，关于互斥与同步问题总结出以下几种的常见类型。不同类型的同步问题利用信号量机制去求解时，信号量的初值设置以及wait 和signal 操作的规律如表1 所示。编写同步问题的代码时，要分析有哪些进程，进程在推进过程中使用哪类资源，以确定互斥和同步的类型;然后按着进程推进的活动编写代码，设置信号量的初值和wait、signal 操作。代码编写完成后，还需进一步分析是否有死锁和饥饿发生;若有则要解决，完善代码;最后还要优化代码，提高程序的并发度。

表1 同步问题类型表

3 结语

同步控制是操作系统、并发程序设计、多核多线程等计算机专业课程中的关键问题，也是难点问题。本文选择及设计了几个经典案例，通过对案例问题的求解分析，将同步控制问题划分为互斥、同步、同种资源等六种类型，并给出了解决这六种类型问题的求解规律，希望对学习者有所借鉴和帮助。

［1］ 汤小丹，汤子瀛.计算机操作系统［M］.西安:西安电子科学大学出版社，2007.

［2］ 左万历，周长林.操作系统教程［M］.北京:高等教育出版社，2007.

［3］ 左万历.操作系统习题与实验指导［M］.北京:高等教育出版社，2005.

［4］ Gary Nutt.操作系统现代观点［M］.孟祥山，晏益，译.北京:机械工业出版社，2004.