李仲生　黃美玲

摘 要：針對操作系統(tǒng)課程教學的難點之一——動態(tài)頁式內(nèi)存管理的淘汰置換算法的教學，以認知心理學和信息加工心理學為基礎(chǔ)，引入融合了建構(gòu)理論的簡化PBL學習模式，以當前的實際教學環(huán)境和學生的認知結(jié)構(gòu)為參照，通過組合情境、協(xié)作、會話、建構(gòu)四個要素，給出了一種教學思路。在這種教學思路下，學生將在問題的引導下沉入情境，思索學習，成為學習的主人。在實際教學中，采用情景構(gòu)建、算法分析及假設(shè)驗證、橫向?qū)Ρ确治龅染唧w步驟實施了前述教學思路，課堂活躍，教學效果明顯。

關(guān)鍵詞：PBL LBL 淘汰置換算法 建構(gòu)理論 主動學習

中圖分類號：G64 文獻標識碼：A 文章編號：1674-098X（2015）09（c）-0227-03

虛擬存儲器是操作系統(tǒng)構(gòu)筑的一個邏輯上的特大存儲器，其空間可稱為邏輯空間，其大小受地址寄存器位數(shù)和可用輔存大小的限制，在程序執(zhí)行的局部性原理支持下為進程的并發(fā)執(zhí)行、資源的充分利用準備了用武之地。要讓虛擬存儲器有效運作起來，有兩個關(guān)鍵技術(shù)點必須達成：一是邏輯地址與物理地址的映射；二是存儲頁的管理，其中包括分配與淘汰算法。其中的淘汰算法直接關(guān)系到進程執(zhí)行的流暢度，是個難點。

動態(tài)分頁管理實現(xiàn)了虛擬存儲器，它的淘汰算法眾多，基本的有：最佳淘汰算法（OPT）；先進先出算法（FIFO）；最近最少使用算法（LRU）；最近最不常用頁面置換算法（LFU）；最近未使用算法（NRU）等，這些算法引起了眾多的研究者關(guān)注，如文獻[1]對前述算法作了一個枚舉式的技術(shù)介紹，文獻[2]通過對前述置換算法編程作虛擬仿真，在統(tǒng)計數(shù)據(jù)的基礎(chǔ)上作了類似的技術(shù)性比較。綜觀現(xiàn)有的關(guān)于頁面置換算法的文獻，發(fā)現(xiàn)它們都把目光集中在算法本身上，重在討論算法的實現(xiàn)和算法的特點，很少考慮學生因素和相關(guān)知識因素，也就是說并未直接面對教學。為提升頁面置換算法的教學針對性、激發(fā)學生的學習主動性，依據(jù)長期教學實踐，簡化PBL（Problem-Based Learning）[3-4]小團隊教學，下文給出了一種頁面置換算法教學思路。

1 簡化PBL

PBL和LBL有著相對性和互補性。傳統(tǒng)教學以講授為基礎(chǔ)（Lecture Based Learning，即LBL），是學科知識式學習，強調(diào)系統(tǒng)性、基礎(chǔ)性、循序漸進性、完整性等，以教師為中心，以知識為內(nèi)容，且學科界限分明，學生被動接受。相對地，PBL為問題式學習，以任務(wù)為導向，以問題為素材，營造真實情景，讓學生自主地思考，去發(fā)現(xiàn)，搜索出問題背后的知識，讓學生的思維在情景中潛移默化的獨立起來、全面起來。

PBL教學模式最初由Barrows提出[3]，以認知心理學和信息加工心理學為基礎(chǔ)，引入建構(gòu)主義學習理論[5]的“情境、協(xié)作、會話和意義建構(gòu)”等四大要素，加以綜合而成。在這種模式下，學生的學習是相當自主的，學習途徑也是多樣的，多樣的途徑有利于加強基礎(chǔ)理論和工程應(yīng)用的聯(lián)系、培養(yǎng)出學生的工程實戰(zhàn)能力。

建構(gòu)主義學習理論有以下基本觀點：學習是一個建構(gòu)過程，學習者是主動的，主動地根據(jù)已有認知結(jié)構(gòu)去探索周邊知識，進而建構(gòu)出所探究的目標的意義；個人的知識是主觀構(gòu)建，圍繞客觀世界；為逼近客觀，知識構(gòu)建遠非個人行為，尚需與他人討論，并在討論過程中不斷修正深化；客觀世界復雜多樣，學習者各有自己的認知結(jié)構(gòu)，對相同的目標，不同的學習者會建構(gòu)出未必相同的意義。這些基本觀點有兩個思想貫穿其中：一是自主，；二是多途徑學習。建構(gòu)主義認為，知識是通過意義構(gòu)建方式獲得，實現(xiàn)意義構(gòu)建需要必要的學習環(huán)境，這個學習環(huán)境有四大屬性（或稱4大要素）：情境、協(xié)作、會話及意義建構(gòu)。

“情境”。古人云，入芝蘭之室，久而不聞其香，此言充分體現(xiàn)出了情境的感化能力。在教學中，要讓學生久而自香，情境設(shè)計是相當關(guān)鍵的，在設(shè)計過程中至少要考慮兩個方面的因素；一是學習目標的實現(xiàn)：二是學生的已有知識結(jié)構(gòu)和學習狀態(tài)。在充分考慮各方面因素的基礎(chǔ)上，設(shè)計有效的情境，給學生提供一個自主的、多元的思考環(huán)境，讓學生能主動地完成意義構(gòu)建，即完成學習。

“協(xié)作”。即學習者運用已有認知，互補地實施意義構(gòu)建的具體過程，這些過程涉及到了一系列建構(gòu)環(huán)節(jié)，比如：資料搜集分析、問題的提出和驗證、階段成果評價、情境轉(zhuǎn)換、最終意義構(gòu)建等。協(xié)作，存在于意義構(gòu)建推進的全過程。

“會話”?？陀^世界是多樣多變的，學習者的認知結(jié)構(gòu)也各有特點，俗話說，三個臭皮匠，賽過諸葛亮，不同的學習者依據(jù)自己的認知結(jié)構(gòu)，從不同的側(cè)面對建構(gòu)對象給出自己的意義建構(gòu)，給出的建構(gòu)從單體方面來說是多元化的，從整體上而言，對客觀世界的反映較之單體顯著不在一個層次上，更全面，更完整。為將單體意義建構(gòu)融合成一個整體，會話成為關(guān)鍵的一環(huán)，高效的、有序的會話設(shè)計，將潤滑意義建構(gòu)的過程。

“意義建構(gòu)”。意義建構(gòu)完成意味著學習過程完成，其中的意義代表著應(yīng)獲得的知識，這些知識包括建構(gòu)對象性質(zhì)、建構(gòu)對象組成的內(nèi)在關(guān)聯(lián)、已知和未知的規(guī)律等。要得到這些意義，可采取科學歸納化（即從已知推到未知）、假設(shè)與驗證法、擴展推理探索法發(fā)現(xiàn)法等。值得注意的是，建構(gòu)主義的目標并不是呆板地去照搬客觀世界，在學習中這個客觀世界就是教學目標，而是讓學習者憑借已有的認知結(jié)構(gòu)，主動沉入情境、參加協(xié)作、會話碰撞，最后豐滿自己的認知結(jié)構(gòu)，達成學習目標。

PBL教學模式是建構(gòu)主義在教學中的有效詮釋，它強調(diào)分組和團隊，強調(diào)學習者的主動性，偏向于以基于問題的方式構(gòu)筑情境，對復雜多變的教學內(nèi)容有著極強的適應(yīng)性，擁有著諸多優(yōu)勢，但由于一些現(xiàn)實原因，比如：宏觀方面如知識的近于無限多變性、學習者的已知知識結(jié)構(gòu)的千變?nèi)f化性，微觀方面如課時的有限性等，PBL教學模式在適應(yīng)能力方面依舊有著一定的提升空間，它缺乏基礎(chǔ)知識的系統(tǒng)性（注：與LBL相比），所強調(diào)的團隊探討式意義構(gòu)建在課堂有限的時間內(nèi)難以實施，因此，為了在課堂中真正引入PBL教學模式，對其進行有針對性的簡化是十分必要的

簡化的具體實現(xiàn)辦法是：分析各學生的基礎(chǔ)情況和平常表現(xiàn)，合理搭配，有效地作分組；探討的參與者地位不全一樣，將加入教師因素，讓教師充當團隊的引導者，控制全體團隊的協(xié)作和會話節(jié)奏；教師將目標定位于以下幾個方面的工作：一是合理組織會話過程，讓學生有學習動機，強化學生的學習興趣；二是勾勒出知識相關(guān)性，補充基礎(chǔ)知識，提升知識的系統(tǒng)性，防止學生隨波逐浪、在知識的海洋中迷失方向；三是歸納學生在構(gòu)建過程中的探索成果，合并正確的，糾正錯誤的，讓意義構(gòu)建更加有效。以虛擬存儲器的頁面置換算法為例，以上辦法在課前表現(xiàn)為教師根據(jù)教學內(nèi)容和學生實際情況設(shè)計一系列問題、學生則完成分組，課中則表現(xiàn)為一種教學情境，這種情境中有問題的提出和回答、假設(shè)的構(gòu)建和驗證、算法的設(shè)計和運行等場景，下文給出了一種具體實施的實例。

2 簡化PBL教學模式的實施

在虛擬存儲器的頁面置換算法的教學中引入簡化PBL教學模式有三個基本步驟：一是置換算法運行大環(huán)境即情景的構(gòu)建，針對周邊知識，提出一系列環(huán)環(huán)相扣的問題；二是深入分析算法的流程，找出學生容易困惑或者產(chǎn)生疑難的點，提出相關(guān)的問題讓學生尋找答案；三是對不同的算法作橫向?qū)Ρ?，設(shè)計一些問題，讓學生在對比中自覺深化，并在討論中形成自己的認識，即完成意義構(gòu)建。

第一步是運行大環(huán)境即情景的構(gòu)建。本步教學目標是讓學生明白硬件環(huán)境和軟件運行的本質(zhì)，即明白內(nèi)存、外存及操作系統(tǒng)的頁面管理分別承擔著什么樣的角色，讓學生有身臨其境的感覺、知其然且知其所以然，將根據(jù)課堂情形以適當順序提出以下問題：邏輯空間在哪？物理空間指什么？虛擬存儲器的大小決定于那兩個因素（若提出此問題，則要提醒同學們回顧計算機組成原理的相關(guān)內(nèi)容，強化教學內(nèi)容的系統(tǒng)性）？為什么？是不是每個進程都有自己獨立的虛擬空間？虛擬空間地址怎么編？邏輯頁與物理頁有什么異同？為什么要換頁？為什么只給每個進程少量的物理頁？主觀上推測一下，如果一個進程的物理頁太少，會出現(xiàn)什么情況？如果太多，又會出現(xiàn)什么情況？最后歸納一下，一個進程分多少物理頁由哪些因素決定？對于邏輯地址組121、225、134、543、453、130、332、465、223、447，假如頁面大小為100，它們對應(yīng)的頁面號是多少？

第二步工作是分析算法流程，根據(jù)教學經(jīng)驗和學生實際情況找出學生的困惑點或者疑難點，有針對性地提問，可選擇的方案眾多，以教師的教學經(jīng)驗的依賴性強，通常地，宜以簡單明了的方案為最佳期望。此處不妨設(shè)第一步中所提及的邏輯地址組代表著進程訪問邏輯地址的順序，采用先進先出調(diào)度算法，給出對應(yīng)的調(diào)度過程如下表1所示。

從表1中可以算出，缺頁率達到80%，淘汰率達50%。依據(jù)表格提出以下問題：表格所代表的進程分到了幾個物理塊？淘汰率是不是必然小于缺頁率？表中出現(xiàn)了幾次剛換出又重新?lián)Q入的情況？這種情況可用什么原理解釋？學生在作題時易困擾的問題是：比如頁面1，在第一列被訪問，在第三列再次被訪問，它進入內(nèi)存的時間是以第一列為準而是第三列為準？在基本問題完畢后，引入假設(shè)和驗證模式，讓同學們作假設(shè)：假設(shè)增加一個物理塊，高度過程將有什么變化？減少一個物理塊呢？

第三步工作是橫向?qū)Ρ龋茨貌煌惴ǖ捻撁嬷脫Q結(jié)果作比較，找出其中的差異，比較不同算法間的得失，深化學生們的印象，擴展學習內(nèi)容，提升學習效果。表1所示的進程與局部性原理有著較好的吻合性，但在用先進先出算法進行調(diào)度時，出現(xiàn)了較高的缺頁率和淘汰率，顯示出了算法的不適應(yīng)性。如果采用最佳淘汰算法，必能降低缺頁率和淘汰率，但問題是最佳淘汰算法要預知未來，難以真正實現(xiàn)，折衷地，采用最近最少使用調(diào)度算法，調(diào)度結(jié)果見表2。

從表2中可以算出，缺頁率60%，淘汰率30%，優(yōu)于先進先出算法，為什么？根據(jù)表2，進一步設(shè)計以下問題供學生討論：假如為每個物理塊設(shè)計一個寄存器，如何用它們來衡量最近是多久、最少使用的是誰？如果用堆棧呢？要是讓你在虛擬存儲器中設(shè)計頁面置換算法，你會怎么作？

3 結(jié)語

上文基于簡化PBL學習模式，給出了一種內(nèi)存頁面淘汰置換算法的教學思路，從建立情境、理清算法特別是弄清學生在實際解決問題時容易迷糊的點、不同算法對比參照以強化內(nèi)容的建構(gòu)三個角度規(guī)范知識點的教學。這種教學思路把眾多的淘汰算法置入了一個整體環(huán)境，并用問題驅(qū)動將它們串聯(lián)成線，展露出它們的相關(guān)性，方便學生思考理解并最終掌握。實際教學顯示，該方法是行之有效的。進一步的工作，是將這種教學思路向操作系統(tǒng)及相關(guān)課程的其他知識難點加以推廣。

參考文獻

[1] 陳文明.對虛擬存儲中置換算法的探討[J].湖北三峽職業(yè)技術(shù)學院學報， 2005，2（2）：73-77.

[2] 江波.操作系統(tǒng)中頁面置換算法的對比研究[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] 林潔璇.建構(gòu)主義視角下開放英語自主學習模式的構(gòu)建策略研究[J].文理導航，2015（24）：5-6.