[出处] 教育教学论坛_2021年第43期

王立春 孔德慧 李敬华

[关键词] 案例教学法;关联案例教学;操作系统

[基金项目] 2019年度北京工业大学研究生课程建设项目“真实感计算机图形学”（CR201907）

[作者简介] 王立春（1975—），女，黑龙江绥化人，博士，北京工业大学信息学部教授，主要从事人工智能、人机交互研究;孔德慧（1968—），女，陕西吴堡人，博士，北京工业大学信息学部教授，主要从事多媒体技术研究;李敬华（1979—），女（满族），辽宁锦州人，北京工业大学信息学部副教授，博士，主要从事模式识别、图像处理研究。

[中图分类号] TP316   [文献标识码] A          [文章编号] 1674-9324（2021）42-0101-04   [收稿日期] 2021-04-30

一、引言

案例教学法以构建主义学习理论为指导，通常利用一种真实的教学情境切入教学内容，带领学生在对情境进行探讨的过程中理解抽象、复杂的概念或原理[1]。关联案例教学法强调教学案例与学生生活、专业相关联，本文在考虑以上关联的基础上进一步考虑知识点间的关联，针对计算机操作系统课程中的进程同步与互斥问题，通过设计生活相关且由简至繁的一系列案例引导学生渐进地理解如何利用信号量及PV原语实现进程间的互斥或同步[2]。

“计算机操作系统”是计算机科学与技术、软件工程、信息安全等信息类专业的核心和基础课程[3]，对于“数据结构”“计算机组成管理”“系统结构”“网络安全”等其他专业课有承上启下的作用，充分理解操作系统课程中的概念和原理可以帮助学生更好地理解其他理论课程涉及的概念和原理。

操作系统是计算机系统中最重要的系统软件，提供硬件和其他软件的接口、计算机和用户的接口;控制和管理计算机系统内的各种软硬件资源;有效地组织和管理多道程序的运行。在保证安全的前提下保障程序并发执行和资源共享是现代操作系统的重要特点，为了有效支持程序并发执行和资源共享，现代操作系统使用进程描述计算机程序的执行过程并将进程看作是资源分配的基本单位。因此，进程管理是操作系统的重要功能之一，透彻理解进程管理有助于深入理解操作系统的工作原理。

二、进程互斥/同步与信号量和PV原语

计算机系统的资源有限导致了进程之间的资源竞争和共享。一组并发进程中的一个或多个程序段，因共享某一共有资源而导致它们必须以一个不允许交叉执行的单位执行，称为进程的互斥;异步环境下的一组并发进程因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步[4]。

信号量和PV原语是实现进程同步与互斥的重要手段，公用信号量描述多进程共享的资源的使用情况，私用信号量描述同步进程中先序进程的完成情况，PV原语是用于信号量管理的原语。理解“基于信号量和PV原语实现进程同步与互斥”是操作系统课程中“进程管理”的重点内容，也是难点之一。

进程同步互斥的经典案例有“生产者—消费者问题”“读—写者问题”“哲学家就餐问题”“过桥问题”等，这些问题分别描述了不同资源限制条件下的同步和互斥问题，以值分别为例讲解进程同步互斥时需要在不同应用场景间切换，相比之下，分析单一应用场景下不同条件的问题设置更容易建立问题与解决方案之间的关联，更利于在讲解过程中引导学生经历逻辑渐进复杂的问题场景，从而递进式地展开问题分析。

本文针对以上问题，对生活场景密切相关的“过桥问题”进行修改，提出由简单到复杂的一系列问题，使其在用于解释进程同步和互斥问题时便于展开由浅入深的分析。

三、渐进复杂的进程互斥案例设计

针对进程同步问题，选择生活场景密切关联的“过桥”作为案例，考虑单向/双向通过、以及允许1人通过/允许N人同时通过，设计渐进复杂的竞争使用资源问题，以达到递进式分析问题的目的。

（一）单向—允许一人通过的过桥问题

过桥问题-1：一条河上架设了一座只允许单向通过的橋，且任意时刻桥上只能有一个人，过河的人只能沿着桥向前走而不能向后退，请设计利用PV原语实现多人顺利过河的算法。

问题分析：“任意时刻桥上只能有一个人”要求过桥的人互斥地通过桥，“只允许单向通过”以及“过河的人只能沿着桥向前走而不能向后退”的条件，意味着正在过桥的人只需要考虑同方向后续要过桥的人有共享公共资源的可能。

设置公用信号量semBridge表示桥是否可用，由于任意时刻桥上只能有一个人，因此该信号量初值为1。描述每个过桥人行为的伪码如下。

（二）单向—允许N人同时通过的过桥问题

过桥问题-2：一条河上架设了一座只允许单向通过的桥，且任意时刻桥上最多可以有N个人，过河的人只能沿着桥向前走而不能向后退，请设计利用PV原语实现多人顺利过河的算法。

问题分析：与“过桥问题-1”相比，新的问题描述是“任意时刻桥上最多可以有N个人”，这意味着公共资源的数量从1增加为N。

设置公用信号量semPeople表示桥可容纳的人数，由于任意时刻桥上最多可以有N个人，因此该信号量初值为N。

（三）雙向—允许N人同时通过的过桥问题

过桥问题-3：一条河上架设了一座桥，且任意时刻桥上最多可以有N个人，过河的人只能沿着桥向前走而不能向后退。过河时，只要对岸无人过桥，就可以过桥，但不允许河两岸的人同时过桥。请设计利用PV原语实现两个方向多人顺利过河的算法。（假定人源源不断地到达）

问题分析：任意一个在桥上的人要考虑两种互斥地使用桥的情况：同方向后续要过桥的人，对岸要过桥的人。为了方便描述过桥人的方向，设过桥的两个方向记为正向和反向（后续问题采用相同记法）。

从第一个过桥人的角度分析，假定这个人的方向是正向，那么只有桥上没有反向的过桥人的情况下，此人才可能过桥，因此正向第一个过桥的人拥有对桥的控制权，同理反向第一个过桥的人也拥有对桥的控制权;同时为了使对立方向的人能够获得过桥的机会，正在过桥的这一方向最后一个过桥的人有必要释放对桥的控制权。因此需要设置公用信号量semBridge表示桥是否可用，由于该信号量用于描述桥的控制权，因此初值为1。

由于是同方向第一个人获得桥的控制权、最后一个人释放桥的控制权，因此需要设置计数器用于统计过桥人的次序，又由于正向和反向都需要统计过桥人的次序，因此有必要设置两个计数器counterZ和counterF分别用于正向和反向的计数。对于正向的过桥人来说，计数器counterZ是所有正向过桥人互斥使用的公共资源，因此设置公用信号量semCounterZ，初值为1;反向计数器counterF的使用同理，设置公用信号量semCounterF，初值为1。

“任意时刻桥上最多可以有N个人”的条件仍然存在，即公共资源数量为N，因此设置公用信号量semPeople表示桥可容纳的人数，初值为N。

描述正向每个过桥人行为的伪码如下（反向过桥与正向过桥原理相同，此处省略伪码）。

过桥问题-3中，如果正向的人开始过桥且过桥的人有无穷个人，则反方向的人永远也无法获得过桥机会，不存在最后一个人来释放桥，反向过桥情况亦然。

四、递进复杂的进程同步案例设计

针对进程同步问题，承接进程互斥问题的场景设计，考虑双向通过时允许1人或N人交替通过的情况，设计渐进复杂的同步且同时存在竞争使用资源的情况。

（一）双向—允许一人交替通过的过桥问题

过桥问题-4：一条河上架设了一座桥，且任意时刻桥上只能有一个人，过河的人只能沿着桥向前走而不能向后退。要求正向和反向的人交替过桥，请设计利用PV原语实现多人顺利过河的算法。

问题分析：与“过桥问题-1”相近，问题描述增加了“正向和反向的人交替过桥”，即正向过桥人和反向过桥人之间存在同步关系，因此分别为正向过桥人和反向过桥人设置私用信号量semPassF和semPassZ表示“反向已过桥”和“正向已过桥”。假定正向优先过桥，则semPassF初值为1，semPassZ初值为0。由于“任意时刻桥上只能有一个人”，因此需要设置公用信号量semBridge表示桥是否可用，初值为1。

描述正向每个过桥人行为的伪码如下（反向过桥与正向过桥原理相同，此处省略伪码）。

（二）双向—允许N人交替通过的过桥问题

过桥问题-5：一条河上架设了一座桥，且任意时刻桥上最多可以有N个人，过河的人只能沿着桥向前走而不能向后退。要求正向的N个人和反向的N个人交替过桥且正方先过桥，请设计利用PV原语实现多人顺利过河的算法。

问题分析：假定正向优先过桥，则semPassF初值为N，semPassZ初值为0。此外，由于“正向的N个人和反向的N个人交替过桥”，因此正向或反向的第一个过桥的人拥有对桥的控制权;同时正向或反向的第N个过桥的人释放对桥的控制权。因此需要为正向和反向分别设置两个计数器，上桥计数器semCounterZup和semCounterFup用于记录正向过桥和反向过桥的第一个人，下桥计数器semCounterZdown和semCounterFdown用于记录正向过桥和反向过桥的第N个人，与前述问题中使用计数器相同，同方向的过桥人互斥地使用计数器，因此需要为每个计数器设置对应的公用信号量。

描述正向每个过桥人行为的伪码见下页（反向过桥与正向过桥原理相同，此处省略伪码）。

五、教学实施情况

以上提出的系列过桥问题，在相同应用背景下逐渐增加问题的复杂度，有助于在教学过程中借助简单问题的解决方案逐步展开对更复杂问题的分析。

过桥问题-1条件最简单，在理解进程互斥、信号量和PV原语的基础上，引导学生分析具体问题中的公共资源是什么、互斥使用公共资源的进程有哪些，从而定义恰当的公用信号量及其初值;过桥问题-2中变化量只是公共资源的数量，学生可以轻易地提出解决方案;过桥问题-3描述的问题进一步复杂化，有了解决前两个过桥问题的经验，学生更乐于参与对过桥问题-3的讨论，提出各种解决方案，针对学生提出的解决方案分析利弊且在此过程中进一步明确了公共资源、进程互斥、信号量以及PV原语的概念。

讨论了过桥问题-3之后，过桥问题-4的条件设定对学生来说不复杂，借用相同场景进一步明确了进程同步、信号量和PV原语的概念;过桥问题-5相比过桥问题-4复杂且与过桥问题-3有相似之处，相似又不同的问题设定吸引学生在课后继续钻研提供解决方案，较好地达到了激发学生学习兴趣的目的。

六、结语

本文针对操作系统课程中进程同步与互斥设计的系列过桥问题，既考虑了案例问题与学生生活的关联，也考虑了进程同步与进程互斥两个既有知识点之间的关联。案例问题的条件由简单到繁难，学生通过解决简单问题获得经验，从而更有信心解决复杂问题;系列问题之间既有相似性也有差异性，激发学生解决复杂问题的好奇心和兴趣，从而有利于通过分析系列问题帮助学生更深入地理解进程同步、进程互斥、信号量以及PV原语的概念。