基于简化PBL的页面置换算法教学

李仲生　黄美玲

摘 要：针对操作系统课程教学的难点之一——动态页式内存管理的淘汰置换算法的教学，以认知心理学和信息加工心理学为基础，引入融合了建构理论的简化PBL学习模式，以当前的实际教学环境和学生的认知结构为参照，通过组合情境、协作、会话、建构四个要素，给出了一种教学思路。在这种教学思路下，学生将在问题的引导下沉入情境，思索学习，成为学习的主人。在实际教学中，采用情景构建、算法分析及假设验证、横向对比分析等具体步骤实施了前述教学思路，课堂活跃，教学效果明显。

关键词：PBL LBL 淘汰置换算法 建构理论 主动学习

中图分类号：G64 文献标识码：A 文章编号：1674-098X（2015）09（c）-0227-03

虚拟存储器是操作系统构筑的一个逻辑上的特大存储器，其空间可称为逻辑空间，其大小受地址寄存器位数和可用辅存大小的限制，在程序执行的局部性原理支持下为进程的并发执行、资源的充分利用准备了用武之地。要让虚拟存储器有效运作起来，有两个关键技术点必须达成：一是逻辑地址与物理地址的映射；二是存储页的管理，其中包括分配与淘汰算法。其中的淘汰算法直接关系到进程执行的流畅度，是个难点。

动态分页管理实现了虚拟存储器，它的淘汰算法众多，基本的有：最佳淘汰算法（OPT）；先进先出算法（FIFO）；最近最少使用算法（LRU）；最近最不常用页面置换算法（LFU）；最近未使用算法（NRU）等，这些算法引起了众多的研究者关注，如文献[1]对前述算法作了一个枚举式的技术介绍，文献[2]通过对前述置换算法编程作虚拟仿真，在统计数据的基础上作了类似的技术性比较。综观现有的关于页面置换算法的文献，发现它们都把目光集中在算法本身上，重在讨论算法的实现和算法的特点，很少考虑学生因素和相关知识因素，也就是说并未直接面对教学。为提升页面置换算法的教学针对性、激发学生的学习主动性，依据长期教学实践，简化PBL（Problem-Based Learning）[3-4]小团队教学，下文给出了一种页面置换算法教学思路。

1 简化PBL

PBL和LBL有着相对性和互补性。传统教学以讲授为基础（Lecture Based Learning，即LBL），是学科知识式学习，强调系统性、基础性、循序渐进性、完整性等，以教师为中心，以知识为内容，且学科界限分明，学生被动接受。相对地，PBL为问题式学习，以任务为导向，以问题为素材，营造真实情景，让学生自主地思考，去发现，搜索出问题背后的知识，让学生的思维在情景中潜移默化的独立起来、全面起来。

PBL教学模式最初由Barrows提出[3]，以认知心理学和信息加工心理学为基础，引入建构主义学习理论[5]的“情境、协作、会话和意义建构”等四大要素，加以综合而成。在这种模式下，学生的学习是相当自主的，学习途径也是多样的，多样的途径有利于加强基础理论和工程应用的联系、培养出学生的工程实战能力。

建构主义学习理论有以下基本观点：学习是一个建构过程，学习者是主动的，主动地根据已有认知结构去探索周边知识，进而建构出所探究的目标的意义；个人的知识是主观构建，围绕客观世界；为逼近客观，知识构建远非个人行为，尚需与他人讨论，并在讨论过程中不断修正深化；客观世界复杂多样，学习者各有自己的认知结构，对相同的目标，不同的学习者会建构出未必相同的意义。这些基本观点有两个思想贯穿其中：一是自主，；二是多途径学习。建构主义认为，知识是通过意义构建方式获得，实现意义构建需要必要的学习环境，这个学习环境有四大属性（或称4大要素）：情境、协作、会话及意义建构。

“情境”。古人云，入芝兰之室，久而不闻其香，此言充分体现出了情境的感化能力。在教学中，要让学生久而自香，情境设计是相当关键的，在设计过程中至少要考虑两个方面的因素；一是学习目标的实现：二是学生的已有知识结构和学习状态。在充分考虑各方面因素的基础上，设计有效的情境，给学生提供一个自主的、多元的思考环境，让学生能主动地完成意义构建，即完成学习。

“协作”。即学习者运用已有认知，互补地实施意义构建的具体过程，这些过程涉及到了一系列建构环节，比如：资料搜集分析、问题的提出和验证、阶段成果评价、情境转换、最终意义构建等。协作，存在于意义构建推进的全过程。

“会话”。客观世界是多样多变的，学习者的认知结构也各有特点，俗话说，三个臭皮匠，赛过诸葛亮，不同的学习者依据自己的认知结构，从不同的侧面对建构对象给出自己的意义建构，给出的建构从单体方面来说是多元化的，从整体上而言，对客观世界的反映较之单体显著不在一个层次上，更全面，更完整。为将单体意义建构融合成一个整体，会话成为关键的一环，高效的、有序的会话设计，将润滑意义建构的过程。

“意义建構”。意义建构完成意味着学习过程完成，其中的意义代表着应获得的知识，这些知识包括建构对象性质、建构对象组成的内在关联、已知和未知的规律等。要得到这些意义，可采取科学归纳化（即从已知推到未知）、假设与验证法、扩展推理探索法发现法等。值得注意的是，建构主义的目标并不是呆板地去照搬客观世界，在学习中这个客观世界就是教学目标，而是让学习者凭借已有的认知结构，主动沉入情境、参加协作、会话碰撞，最后丰满自己的认知结构，达成学习目标。

PBL教学模式是建构主义在教学中的有效诠释，它强调分组和团队，强调学习者的主动性，偏向于以基于问题的方式构筑情境，对复杂多变的教学内容有着极强的适应性，拥有着诸多优势，但由于一些现实原因，比如：宏观方面如知识的近于无限多变性、学习者的已知知识结构的千变万化性，微观方面如课时的有限性等，PBL教学模式在适应能力方面依旧有着一定的提升空间，它缺乏基础知识的系统性（注：与LBL相比），所强调的团队探讨式意义构建在课堂有限的时间内难以实施，因此，为了在课堂中真正引入PBL教学模式，对其进行有针对性的简化是十分必要的

简化的具体实现办法是：分析各学生的基础情况和平常表现，合理搭配，有效地作分组；探讨的参与者地位不全一样，将加入教师因素，让教师充当团队的引导者，控制全体团队的协作和会话节奏；教师将目标定位于以下几个方面的工作：一是合理组织会话过程，让学生有学习动机，强化学生的学习兴趣；二是勾勒出知识相关性，补充基础知识，提升知识的系统性，防止学生随波逐浪、在知识的海洋中迷失方向；三是归纳学生在构建过程中的探索成果，合并正确的，纠正错误的，让意义构建更加有效。以虚拟存储器的页面置换算法为例，以上办法在课前表现为教师根据教学内容和学生实际情况设计一系列问题、学生则完成分组，课中则表现为一种教学情境，这种情境中有问题的提出和回答、假设的构建和验证、算法的设计和运行等场景，下文给出了一种具体实施的实例。

2 简化PBL教学模式的实施

在虚拟存储器的页面置换算法的教学中引入简化PBL教学模式有三个基本步骤：一是置换算法运行大环境即情景的构建，针对周边知识，提出一系列环环相扣的问题；二是深入分析算法的流程，找出学生容易困惑或者产生疑难的点，提出相关的问题让学生寻找答案；三是对不同的算法作横向对比，设计一些问题，让学生在对比中自觉深化，并在讨论中形成自己的认识，即完成意义构建。

第一步是运行大环境即情景的构建。本步教学目标是让学生明白硬件环境和软件运行的本质，即明白内存、外存及操作系统的页面管理分别承担着什么样的角色，让学生有身临其境的感觉、知其然且知其所以然，将根据课堂情形以适当顺序提出以下问题：逻辑空间在哪？物理空间指什么？虚拟存储器的大小决定于那两个因素（若提出此问题，则要提醒同学们回顾计算机组成原理的相关内容，强化教学内容的系统性）？为什么？是不是每个进程都有自己独立的虚拟空间？虚拟空间地址怎么编？逻辑页与物理页有什么异同？为什么要换页？为什么只给每个进程少量的物理页？主观上推测一下，如果一个进程的物理页太少，会出现什么情况？如果太多，又会出现什么情况？最后归纳一下，一个进程分多少物理页由哪些因素决定？对于逻辑地址组121、225、134、543、453、130、332、465、223、447，假如页面大小为100，它们对应的页面号是多少？

第二步工作是分析算法流程，根据教学经验和学生实际情况找出学生的困惑点或者疑难点，有针对性地提问，可选择的方案众多，以教师的教学经验的依赖性强，通常地，宜以简单明了的方案为最佳期望。此处不妨设第一步中所提及的逻辑地址组代表着进程访问逻辑地址的顺序，采用先进先出调度算法，给出对应的调度过程如下表1所示。

从表1中可以算出，缺页率达到80%，淘汰率达50%。依据表格提出以下问题：表格所代表的进程分到了几个物理块？淘汰率是不是必然小于缺页率？表中出现了几次刚换出又重新换入的情况？这种情况可用什么原理解释？学生在作题时易困扰的问题是：比如页面1，在第一列被访问，在第三列再次被访问，它进入内存的时间是以第一列为准而是第三列为准？在基本问题完毕后，引入假设和验证模式，让同学们作假设：假设增加一个物理块，高度过程将有什么变化？减少一个物理块呢？

第三步工作是横向对比，即拿不同算法的页面置换结果作比较，找出其中的差异，比较不同算法间的得失，深化学生们的印象，扩展学习内容，提升学习效果。表1所示的进程与局部性原理有着较好的吻合性，但在用先进先出算法进行调度时，出现了较高的缺页率和淘汰率，显示出了算法的不适应性。如果采用最佳淘汰算法，必能降低缺页率和淘汰率，但问题是最佳淘汰算法要预知未来，难以真正实现，折衷地，采用最近最少使用调度算法，调度结果见表2。

从表2中可以算出，缺页率60%，淘汰率30%，优于先进先出算法，为什么？根据表2，进一步设计以下问题供学生讨论：假如为每个物理块设计一个寄存器，如何用它们来衡量最近是多久、最少使用的是谁？如果用堆栈呢？要是让你在虚拟存储器中设计页面置换算法，你会怎么作？

3 结语

上文基于简化PBL学习模式，给出了一种内存页面淘汰置换算法的教学思路，从建立情境、理清算法特别是弄清学生在实际解决问题时容易迷糊的点、不同算法对比参照以强化内容的建构三个角度规范知识点的教学。这种教学思路把众多的淘汰算法置入了一个整体环境，并用问题驱动将它们串联成线，展露出它们的相关性，方便学生思考理解并最终掌握。实际教学显示，该方法是行之有效的。进一步的工作，是将这种教学思路向操作系统及相关课程的其他知识难点加以推广。

参考文献

[1] 陈文明.对虚拟存储中置换算法的探讨[J].湖北三峡职业技术学院学报， 2005，2（2）：73-77.

[2] 江波.操作系统中页面置换算法的对比研究[J].广西民族师范学院学报， 2010，27（3）：56-59.

[3] Howard S Barrows.How to design a problem-based curriculum for the preclinical years[M].New York：Springer Pub Co，1985.

[4] 陈庆章，古辉，王子仁，等.PBL理论探讨及教师角色认识[J].计算机教育，2011（9）：103-107.

[5] 林潔璇.建构主义视角下开放英语自主学习模式的构建策略研究[J].文理导航，2015（24）：5-6.