沈云琴 成浩晖

摘要：本文深入分析了进程同步中的经典问题“生产者-消费者问题”、“读者-写者问题”的同步和互斥关系，并对各种算法进行了分析和对比，进而让读者深入理解信号量机制的应用和 PV 原语的使用。

关键词：生产者;消费者;同步;互斥;信号量

一、引言

《操作系统原理》课程是计算机科学与技术、大数据、物联网等计算机相关专业的基础课程、核心课程，也是计算机408研究生考试中计算机类专业的一门必考专业课，一直受到国内外计算机专业教师的高度重视。课程内容涉及到操作系统的原理与技术、具体的设计与实现，主要内容包括处理机管理、进程管理、存储管理、设备管理和文件系统管理等核心功能的设计与实现。通过学习，使学生建立起对操作系统的整体及各个功能的认识，让学生了解和掌握操作系统是如何管理和控制计算机系统中的所有软硬件资源，以及操作系统是如何为用户提供一个方便灵活、安全可靠的工作环境的。从而进一步提升学生的软件开发能力乃至系统软件开发能力。

目前的操作系统都建立在进程这一基本概念之上。在传统的操作系统中，为了提高资源利用率和系统吞吐量，通常采用多道程序技术将多个程序同时装入内存，使它们并发执行，此时，进程作为资源分配和调度的基本单位，为保证多个进程能有条不紊地运行，必须引入进程同步机制，所以进程管理是该课程中及其重要的内容。其中，进程的同步和互斥也是课程中的难点。进程同步中的“信号量机制”是解决进程同步互斥问题中的一种有效方法。本文将围绕经典进程同步问题对这一机制进行论述，说明这个机制的应用和引申。

二、信号量机制介绍

信号灯是人类社会中应用于交通管理等领域的一种设备，人们可以利用信号灯的状态（颜色）来规范相关活动。如十字路口的交通管理等。操作系统中的信号量机制类似于信号灯，起着规范进程运行的作用。

1965年，荷兰学者Dijkstra提出了信号量（Semaphores）机制，其是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制得到了很大的发展，它从整型信号量经记录型信号量、AND型信号量，进而发展为“信号量集”机制。现在，信号量机制已被广泛应用于单处理机和多处理机系统以及计算机网络中。

1、整型信号量

最初由Dijkstra把整型信号量定义为一个表示自愿数目的整型量S，它与一般整型量不同，除初始化外，仅能通过两个标准的原子操作来访问，即wait（s） 和signal（s）操作，这两个操作也被成为P操作和V操作，可描述为：

wait（S）{

while S<=0; /*do no-op*/

S--;

}

signal（S）{ /*V（S） */

S++;

}

2、记录型信号量

记录型信号量是不存在“忙等”现象的进程同步机制。除需要一个用于代表资源数目的整型变量value外，再增加一个进程链表L，用于链接所有等待该资源的进程。

3、AND型信号量

AND型信号量机制的基本思想是：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它。

4、信号量集

记录型信号量只能做+1或-1运算，当一次需要多个资源时，可能要进行多次操作。有时对资源还有一个低限要求，当低于最低限是就不许再分配了。因此在每次分配之前，要检查以上两个因素。基于此，可以对AND信号量机制加以扩充，形成一般化的信号量集机制。即针对进程所申请的所有资源以及每类资源不同的需求量，在一次wait（s）或signal（s）操作中完成它们的申请或释放。

三、信号量的应用

在多道程序环境下，进程同步问题十分重要，也相当有趣，因此吸引了不少学者对它进行研究，由此产生了一系列经典的进程同步问题，其中较有代表性的是“生产者-消费者问题”、“读者-写者问题”、“哲学家进餐问题”。下面就“生产者-消费者问题”、“读者-写者问题”进行讨论。

1、利用记录型信号量解决“生产者-消费者问题”

1）问题描述：一组生产者进程和一组消费者进程共享一个初始为空、大小为n的缓冲区，只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待;只有缓冲区不空时，消费者才能从中取出消息，否则必须等待。由于缓冲区是临界资源，它只允许一个生产者放入产品，或一个消费者从中取出产品。

2）关系分析：生产者和消费者对缓冲区互斥访问是互斥关系，同时生产者和消费者又是一个相互协作的关系，只有生产者生产之后，消费者才能消费，它们也是同步关系。这两个进程存在着互斥关系和同步关系。那么需要解决的是互斥和同步PV操作的位置。

3）信号量设置：信号量mutex作为互斥信号量，用于控制互斥访问缓冲区，互斥信号量初值为1;信号量full用于记录当前缓冲池中的满缓冲区数，初值为0，信号量empty用于当前记录缓冲池中的空缓冲区数，初值为n。

2、问题引申

1）该类问题要注意对缓冲区大小为n的处理，P（full） 、P（empty）与P（mutex）的顺序不可颠倒。

设想生产者进程已将缓冲区放满，消费者进程并没有取产品，即empty=0，当下次仍然是生产者进程运行时，它先執行P（mutex）封锁信号量，在执行P（empty）时将被阻塞，希望消费者取出产品将其唤醒。轮到消费者进程运行时，它先执行P（mutex），然而由于生产者进程已经封锁mutex信号量，消费者进程也会被阻塞，这样一来生产者、消费者进程都将阻塞，都指望对方唤醒自己，因此陷入了无休止的等待。同理，若消费者进程已将缓冲区取空，即full=0，下次若还是消费者先运行，也会出现类似的死锁。不过生产者释放信号量时，mutex、full先释放哪一个无所谓，消费者先先释放mutex或empty都可以。

2）关于Mutex互斥信号量的设置是否必要的问题。

在生产者和消费者都是唯一的问题中，生产者和消费者是同步关系，生产者和消费者之间使用empty和full两个资源信号量进行同步，一定满足“放完才能取”的条件，因此此时互斥信号量mutex可以去掉。但在多生产者和消费者的情况下，需要保证多个生产者和多个消费者互斥地访问缓冲池，否则会导致出错。例如，两个生产者执行了P（empty）操作，此时第一个生产者执行buffer（in）=nextp，这时第二个生產者也执行这条语句，由于第一个生产者没有来得及执行in=（in+1） % n，即没有使指针后移，导致第二个生产者的数据覆盖了第一个生产者的数据，而不是放在了第一个数据的下一个缓冲区，接下来两个进程分别执行一次后移指针操作，这样就导致了有一个空缓冲区（本来应当放置第二个数据的缓冲区）被当作已有数据缓冲区对待，从而出错。因此，在多生产者或多消费者的情况下，必须设置mutex互斥信号量，以保证对缓冲池的互斥访问。

3、利用记录型信号量解决“读者-写者问题”

1）问题描述：有读者和写者两组并发进程，共享一个文件，两个或以上的读进程同时访问共享数据时不会产生副作用，但若某个写进程和其他进程（读进程或写进程）同时访问共享数据时则可能导致数据不一致的错误。因此要求：允许多个读者可以同时对文件执行读操作;只允许一个写者往文件中写信息;任一写者在完成写操作之前不允许不允许其他读者或写者工作;写者执行写操作前，应让已有的读者和写者全部退出。

2）关系分析：读者和写者、写者和写者是互斥的，读者和读者不互斥。两个进程，即读者和写者。写者较简单，它和任何进程互斥，用互斥信号量的P、V操作即可解决。读者的问题比较复杂，它必须在实现与写者互斥的同时，实现与其他读者的同步，因此简单的一对P操作、V操作无法解决。

3）信号量设置。为实现Reader与Writer进程间在读或写时的互斥而设置了一个互斥信号量mutex。另外，再设置一个整型变量Readcount表示正在读的进程数目。又因为Readcount是一个可被多个Reader进程访问的临界资源，因此，应该为它设置一个互斥信号量rmutex。算法如下：

semaphore rmutex=1;

semaphore mutex=1;

int readcount=0;

void reader（ ;） {

do {

wait（rmutex）;

if （readcount==0） wait（mutex）;

readcount++;

signal（rmutex）;

… …

perform read operation;

… …

wait（rmutex）;

readcount--;

if （readcount==0） signal（mutex）;

signal（rmutex）;//

}while（TRUE）;

}

void writer（ ） {

do {

wait（mutex）;

perform write operation;

signal（mutex）;

} while（TRUE）;

}

4、公平算法（按照到达顺序进行操作）

在上面的算法中，读进程是优先的，即当存在读进程时，写操作将被延迟，且只要有一个读进程活跃，随后而来的读进程都将被允许访问文件。这样的方式会导致写进程可能长时间等待，存在写进程饿死的情况。可增加一个信号量在上面程序的reader（ ）和writer（ ）函数中各增加一对PV操作，就可解决写进程优先。

进程的执行顺序完全按照到达顺序，即一个读者试图进行读操作时，如果有写者正等待进行写操作或正在进行写操作，后续读者要等待先到达的写者完成操作后才开始读操作。增设一个信号量，初值为1，用于表示是否存在正在写或者等待的写者，若存在，则禁止新读者进入。

由于存在互斥信号量，因此当第一个写者到来时，就会占用该信号量，从而阻止了后续其他读者的进入请求，只有当之前申请写操作的写者进入数据区完成写操作后，才会释放互斥信号量，后续读者才能进入。在这个算法中，将读写两种进程放在平等的地位，完全按照进程到达的顺序来执行。设置互斥信号量的目的在于控制进程按照顺序来进行操作，避免读进程的优先）。

5、写者优先算法

即当写者和读者同时等待时，后续写者到达时可以插队到等待的读者之前，只要等待队列中有写者，不管何时到达，都优先于读者被唤醒，则需要增设额外的信号量进行控制。增设信号量，用于控制写者到达时可以优先于读者进入临界区，当有写者到达时，只需要等待前面的写者写完就可以直接进入临界区，而不论读者是在该写者之前还是之后到达。另外，需要增设一个整数用于统计写者的数量，再设置信号量，用于控制写者互斥访问该整数。

该算法增设了信号量，用于实现写者插队的目的。当第一个写者到达时，申请占用该信号量，占用成功后就一直占用，后续到达的读者进程会因申请不到该信号量而阻塞，而后续写者到达时，由于不需要申请该信号量，因此就排在这个写者后面，从而达到插队目的。直到所有写者已经写完，最后一个写者释放了该信号量，读者才能继续执行读操作。当新的写者到达时，继续占用该信号量，阻止后续的读者进行读操作，重复进行此过程。此算法真正实现了写者优先，新写者也可以优先于先到的等待读者占用数据区进行操作。

四、结语

只要有多个同类进程（同类进程是指使用同一个记录型信号量的进程，比如若干消费者进程都在使用empty信号量），就一定要使用互斥信号量;若同类进程只有一个，则记录型信号量即可完成进程同步。换句话说，互斥信号量是给同类进程准备的。“读者-写者问题”中又引入了读者优先、写者优先、公平算法进一步讨论，使学生更加深刻地理解进程之间同步互斥的关系，信号量的应用以及PV原语的使用。作者通过多年的操作系统原理授课经验得出，这种讲授方法言简意赅，把抽象的内容融入案例中，循序渐进，能调动学生的学习积极性、主动性及热情，实践表明此方法教学效果良好，深得学生好评。

参考文献：

[1]汤小丹，汤子瀛等.计算机操作系统（第4版）[M].西安：西安电子科技大学出版社，2014：57-72.

[2][美]威廉·斯托林斯（William Stallings）主编.操作系统精髓与设计原理（第8版）[M].人民邮电出版社.2019：181-192.

[3]]李姗姗，董威，罗宇，文艳军，廖湘科 .国产操作系统研发对系统能力培养的需求与实践[J].2018，11（40）：32-36.

[4]蔡学森，于繁华，戴金波，顾晗昕，周洋洋.案例法在操作系统原理教学中的应用[J].长春师范大学学报，2015（8）：123-125.

[5]徐为民.研究生课程“线性系统理论”教学内容的组织方式探索[J].教育教学论坛，2017（36）：233-234.

作者简介：

沈云琴（1982-），女，云南昭通人，硕士，讲师，研究方向：云计算技术及数据分析。

成浩晖（2002-），男，陕西渭南人，本科，研究方向：计算机软件。