可调试的信号量PV原语快速实现方法

2022-05-30魏星

电脑知识与技术 2022年31期

摘要：为解决操作系统原理教材中同步互斥经典算法验证问题，提出了一种线程级可调试的信号量PV原语快速代码实现方法。利用该方法对经典的简单生产者－消费者同步问题的伪代码算法进行了C语言编程演示。通过演示说明了该方法代码短小且可在多种操作系统下调试运行。

关键词：信号量；PV原语；同步；互斥；生产者－消费者问题

中图分类号：TP316 文献标识码：A

文章编号：1009-3044（2022）31-0090-03

1 概述

操作系统是计算机系统的核心和灵魂，进程是操作系统中最基本最重要的概念[1]。进程实现了并发多任务，多任务的同步互斥问题是操作系统原理课程的难点，对应用软件多任务设计具有指导意义。信号量（semaphore）是荷兰计算机科学家Dijkstra在1965年提出的同步工具，是一种变量类型，有两个分量：一个是信号量的值，另一个是信号量队列。该类变量仅能由同步原语PV对其进行操作，PV原语具有原子性。信号量是操作系统实现进程同步的经典机制，也是操作系统类课程中的最常用的同步机制[1-2]。PV原语的算法逻辑简单，但是能够灵活控制任务状态的变化，广泛应用在解决多任务速度匹配和资源调度问题中。尤其是对生产者－消费者问题、理发师问题都有基于信号量和PV原语的成熟解决算法。

在操作系统类课程中基于信号量和PV原语解决经典同步问题时，不能直接进行简洁代码演示，只能使用伪代码进行算法表述，结果由推理获得。由于伪代码没有明确标准，读者只能遵循经典教材的使用范例，但经典教材的风格也不统一。如在南大版费翔林和北大版陈向群的教材中信号量使用的是P操作和V操作，而在同样广泛使用的西电版汤小丹的教材中信号量使用的是Wait操作和Signal操作[3] 。由于相同问题可能会有不同版本的伪代码描述，伪代码不能直接运行输出结果，容易导致算法难以理解。

目前操作系统原理教学中逐步引入了多任务实验，实现方法有基于Java线程类方法、Linux+SystemV信号量方法[4]、基于Windows API的進程方法[5]。这些方法虽然能够实现多任务的同步与互斥，但涉及了较多的编程新概念，代码冗长，需要较复杂的编程环境支持。大量非关键的概念和函数，不利于突出信号量和PV原语的作用。C语言作为普通高校程序设计基础的必修课，同时也是操作系统实现的主要语言，具有很好的跨平台特性，基于C语言标准库提供可调试运行的信号量和PV原语具有一定的意义。

2 实现方法

现代操作系统中引入了线程概念。线程是轻量级的进程，是操作系统的可被调度和分派的基本单位。多线程环境中进程可以分为两部分：资源集合和线程集合。由于同一进程中的多线程会竞争处理器资源，或运行中出现等待输入输出事件，故线程状态也有运行态、就绪态、等待和终止态。经典进程同步问题就可以转换为线程同步问题，解决进程同步问题的基于PV原语算法可以在线程同步问题中来模拟实现。

线程实现方法分为内核级线程，如Windows 2003；用户级线程，如POSIX中的Pthread库、Java线程库；混合式线程，如Solaris 。内核级线程需要内核调试环境，配置非常复杂。用户级线程在用户应用程序中可以被编程管理，只需要普通的应用程序编程环境。用户级线程库在多种编程语言环境中有相关库或类支持，如C语言、Java语言、C#语言等。C语言作为操作系统和系统库的主要实现语言，在编制相关的多任务同步演示程序上具有一定的优势。由于多任务同步演示环境需要考虑在Windows平台和Unix平台上的实现，需要注意消除两种系统中实现源代码的差异性。虽然Java语言、C#语言本身具有跨平台的实现，但是集成开发编程环境庞大（一般大于1GB），不如纯粹的GNU C语言开发环境简洁，集成GNU C编译器的DEV C++集成开发环境安装包只有50MB左右。

POSIX（Portable Operating System Interface，缩写为POSIX）翻译为可移植操作系统接口，是IEEE为要在各种UNIX操作系统上运行软件，而定义API的一系列互相关联的标准的总称。Pthread库是实现了POSIX线程规范的一套API，POSIX的信号量API可以和Pthread协同工作。Pthread库一般用于Unix-like POSIX 系统，如Linux、Solaris，在Microsoft Windows上也有实现，具有源代码级的可移植性。由于Pthread库可在用户空间实现，在通用操作系统上均能够比较方便获得。因此可以采用一定的封装技术，在通用操作系统上实现信号量和PV原语。

具体方法是使用线程实现多任务，利用Pthread提供的sem_t信号量实现传统的信号量，sem_t信号量的操作模拟为PV原语。为了减少类型和函数名称的差异带来的误解，引入自定义数据类型和宏定义进行封装。使用C语言自定义类型将Pthread库中的sem_t类型修改为semaphore类型，使用宏定义机制将sem_wait函数模拟P操作，sem_post函数模拟V操作，sem_init函数对信号量进行初始化。

#define P（S）（sem_wait（S））

#define V（S）（sem_post（S））

typedef sem_t semaphore;

经过基本封装后，PV原语变成两个普通的C语言函数，可以直接使用。信号量semaphore 变成一种自定义数据类型，利用Pthread多线程替代进程模拟多任务。

sem_t是Pthread库中的自定义union数据类型，通过源代码分析实际为一个整数，和经典的信号量定义相似。由于具体实现中，sem_t变量不能直接赋值，需要通过函数sem_init进行赋值，信号量的初始值为sem_init中的第3个参数。sem_wait 是Pthread库中的一个函数，功能和经典的P操作定义相似，在线程中被定义为一个原子操作，它的作用是从信号量的值减1，但它会先等待该信号量为一个非零值才开始做减法。sem_post是Pthread库中的一个函数，功能和经典的V操作定义相似，在线程中被定义为一个原子操作，它的作用是信号量的值加1。这两个函数都是用sem_t 型参数。C语言中宏定义机制能够为变量或者函数取别名，通过把sem_t转换为semaphore，把sem_wait转换为P操作，把sem_post转换为V操作，能够提高代码的可阅读性。

3 算法转换与应用

PV原语是解决经典多任务同步问题的有效工具，下面结合经典的简单生产者—消费者同步问题将伪代码进行可调试运行代码转换。简单生产者－消费者问题是生产者－消费者问题的特例，即只共享单个缓冲区，不需要使用缓冲区互斥操作。典型的简单生产者－消费者问题伪代码解法如图1所示[1]。该问题解法利用信号量和PV原语实现同步。Producer表示生产者任务，Consumer表示消费者任务，两个任务共用一个缓冲区。生产者和消费者是并发执行，两个任务的同步逻辑是缓冲区为空时消费者需要等待生产者，缓冲区满时生产者需要等待消费者。

在上述伪代码的解法中，编号①的部分进行缓冲区B和信号量的初始化，此处empty的值为1，full的初值为0。编号②部分由cobegin和coend组成，表示包裹的代码任务将并发执行，此处说明建立了producer和consumer任务。编号③部分producer是生产者任务实现代码，PV原语用于实现对缓冲区B的同步。编号④部分consumer是消费者任务实现代码，PV原语用于实现对缓冲区B的同步。信号量empty和full的初值和P操作的顺序都有严格规定，但是伪代码不能直观看出由于初值和顺序调整引起的执行结果变化。利用Pthread和封装的信号量PV原语，对应C语言代码如下图2所示。为了方便对比说明，将实现代码进行了重新编排。

图2的左上①部分描述了如何构造PV原语，基于C语言的宏定义有利于得到和伪代码一致的描述。图2的右上部分②完成信号量的初始化和任务的创建，信号量的初始值通过特定函数进行设置，任务创建后与主进程一起运行。其中pthread_create函数功能是创建线程并立即参与调度，pthread_join用来等待一个特定线程的结束，sem_init实现对信号量值的初始化。图2的下半部分③ producer描述了生产者的算法实现，循环执行P操作实现等待缓冲区为空，生产产品，然后通知消费者消费；图2下半部分④ consumer描述了消费者的算法实现，循环执行等待缓冲区有产品，消费产品，通知生产者生产。其中关键的P操作V操作位置、empty和full信号量的初值和伪代码描述一致。代码中添加的sleep函數用于模拟生产者和消费者执行时间不一致，同时sleep函数调用会主动触发任务进入阻塞状态，便于更好体现线程调度的作用。使用有限次数for循环代替无限while循环是为了观察分析输出结果。

该问题解决方法的代码长度可控制到50行，与伪代码有较好的对应关系，并可以灵活修改。在Ubuntu Linux 14+GCC 4.2环境下和Windows 7/8/10 + Dev Cpp V5.0 开发环境均能够正常运行。输出结果如图3所示为交替输出生产和消费值。在代码中生产者的任务执行时间和消费者任务执行时间虽然不一致，但是通过合理地使用信号量和PV原语，仍然实现了生产—消费同步约束逻辑，即缓冲区空时才能执行生产任务，缓冲区满时才能执行消费任务，结果符合生产者—消费者问题信号量同步算法的预期。

由于本方法是由C语言程序实现，可以通过修改源代码方式对信号量设置不同的初值，以及修改PV原语的位置能够获得多种输出，通过信号量和PV原语算法进行推导解释。比如对同步信号量full如果初值设置为1，empty初值也设置为0，表示缓冲区任务开始时缓冲区已经满的情况。由于是单缓冲情形，生产者任务在缓冲区满的情况下应该不能运行，而消费者任务应该可以运行，所以预期运行结果应该是消费者任务先运行，但是消费任务输出应该为0。基于信号量PV操作的同步算法，只需要修改图1源程序中行36和行37，修改后代码如图4所示。

信号量值修改后运行结果如图5所示，其中消费者任务先运行而缓冲区初始值为0，所以输出为消费0，而本程序是只设计运行四次，所以没有消费4输出。符合同步算法预期结果，能够直观反映出信号量PV原语在同步机制中的作用。

综上所述，本方法中信号量和PV原语与伪代码中的信号量和PV原语基本一致，教材中基于信号量和PV原语实现的同步互斥问题算法伪代码能够快速转换为可运行的C语言代码。类似的一些教材中基于信号量的wait操作和signal操作表示的等待唤醒伪代码，也能够使用本方法进行C语言转换。为了便于验证和使用源代码，已经在Gitee网站（码云）上建立代码仓库网址是https：//gitee.com/wayxingwork/pcdemo。

4 结束语

通过把Pthread库中的信号量和相关操作进行友好封装，实现了多操作系统平台下对经典进程同步互斥问题的可调试编程，便于学习者理解掌握多任务同步互斥算法知识。同时，具体实现方法考虑了开发环境和代码获取等因素，方便在线开放课程教学和课堂演示。

操作系统原理作为计算机专业基础课程，教学课时一般为48学时，主要采用讲授法进行理论教学。在应用型本科和高职高专层次教学过程中，经常出现教学效果不佳等问题。改进的方法主要是教师优化教学模式[6]和教学方法[7]，或者是创新理论推导公式[8]等方法，以及大量的典型习题训练。通过对经典问题提供可对照可调试的代码解决方法也是一个改进的途径。

由于进程和线程的概念差异性，本方法是在用户空间多任务层次实现了可调试运行的信号量和PV原语，和传统的信号量的定义仍有一定的差异，如何封装类似管程的高级同步机制，后续需进行相关方面探索研究。

参考文献：

[1] 费翔林，骆斌.操作系统教程[M].5版.北京：高等教育出版社，2014.

[2] 陈向群，杨芙清.操作系统教程[M].2版.北京：北京大学出版社，2006.

[3] 汤小丹，梁红兵，哲凤屏.计算机操作系统[M].3版.西安：西安电子科技大学出版社，2007.

[4] 费翔林，李敏，叶保留.Linux操作系统实验教程[M].北京：高等教育出版社，2009.

[5] 金海东，徐云龙.“操作系统”课程中进程同步互斥教学研究[J].计算机教育，2009（14）：60-62.

[6] 李欣.计算机操作系统课程中PBL教学模式的应用研究[J].信息技术与信息化，2016（11）：123-124.

[7] 王秋芬，王永新.基于OBE的操作系统原理课程教学方法改革与实践[J].教育教学论坛，2019（12）：167-168.

[8] 鲁力，韩洁，徐琴.PV操作解决进程同步问题的难点研究与实现[J].电脑知识与技术，2017，13（13）：38-39.

【通联编辑：谢媛媛】

收稿日期：2022-05-08