基于簡化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.