基于簡化PBL的頁面置換算法教學(xué)

李仲生　黃美玲

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

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

中圖分類號：G64 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2015）09（c）-0227-03

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

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

1 簡化PBL

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

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

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

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

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

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

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

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

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

2 簡化PBL教學(xué)模式的實(shí)施

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

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

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

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

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

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

3 結(jié)語

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

參考文獻(xiàn)

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

[2] 江波.操作系統(tǒng)中頁面置換算法的對比研究[J].廣西民族師范學(xué)院學(xué)報(bào)， 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理論探討及教師角色認(rèn)識[J].計(jì)算機(jī)教育，2011（9）：103-107.

[5] 林潔璇.建構(gòu)主義視角下開放英語自主學(xué)習(xí)模式的構(gòu)建策略研究[J].文理導(dǎo)航，2015（24）：5-6.