電梯調(diào)度算法的應(yīng)用與實現(xiàn)*

李自紅李曉斌牛世軍米鳳霞

1.甘肅省定西市隴西縣和平鄉(xiāng)黃寨小學(xué)；2.蘭州工業(yè)學(xué)院計算機與人工智能學(xué)院；

3.甘肅省定西市隴西縣文峰鎮(zhèn)東鋪小學(xué)；4.甘肅省定西市隴西縣翠屏小學(xué)

隨著信息技術(shù)教育在各級各類學(xué)校的普及，學(xué)生整體的信息技術(shù)應(yīng)用能力得以大幅提高。信息技術(shù)教育的普及，培養(yǎng)了學(xué)生的信息技術(shù)應(yīng)用興趣，提高了學(xué)生使用基本信息技術(shù)的能力，增強了學(xué)生應(yīng)用信息的能力。為培養(yǎng)全面發(fā)展，尤其適應(yīng)未來高科技生活的各類人才，作出了巨大貢獻(xiàn)[1]。

近年來，隨著人工智能、機器人設(shè)計等信息學(xué)科的蓬勃發(fā)展，基本的信息技術(shù)應(yīng)用學(xué)習(xí)，如文字處理、繪圖工具使用和多媒體作品編輯等已不能完全滿足各級各類學(xué)生的信息技術(shù)學(xué)習(xí)需求[2,3]。

為適應(yīng)快速發(fā)展的信息技術(shù)領(lǐng)域環(huán)境，切實提高信息技術(shù)教育教學(xué)質(zhì)量，滿足當(dāng)下學(xué)生對信息技術(shù)學(xué)習(xí)的需求，在信息教育教學(xué)過程中，除了踐行基本的信息技術(shù)知識和能力教育教學(xué)外，探索融入算法思想的教學(xué)，有一定的積極意義[4]。

本文以操作系統(tǒng)中典型磁盤調(diào)度算法之一，電梯調(diào)度算法的應(yīng)用與實現(xiàn)為例，討論了在信息技術(shù)教學(xué)過程中融入算法教學(xué)的方案。結(jié)合中小學(xué)生興趣愛好、理解和接受能力，以比較容易理解的電梯調(diào)度算法原理的講解、程序的編寫和運行、程序運行結(jié)果的分析討論為教學(xué)環(huán)節(jié)，激發(fā)學(xué)生觀察事物的興趣，培養(yǎng)學(xué)生理解和分析身邊算法的能力，達(dá)到擴展操作系統(tǒng)知識模塊學(xué)習(xí)的目的，更好地為提高信息技術(shù)教育教學(xué)質(zhì)量服務(wù)。

1 操作系統(tǒng)

操作系統(tǒng)是計算機體系結(jié)構(gòu)中的重要系統(tǒng)軟件，為管理計算機提供資源支持，為用戶和機器之間提供交互接口。它是第一層安裝于計算機整體系統(tǒng)中核心軟件部分，也是計算機系統(tǒng)正常運行的基本保障[5]。

1.1 操作系統(tǒng)知識模塊

《中小學(xué)信息技術(shù)課程指導(dǎo)綱要（試行）》文件中指出，操作系統(tǒng)是中小學(xué)信息技術(shù)課程教學(xué)內(nèi)容的模塊之一。該指導(dǎo)綱要發(fā)布于2000年，對中小學(xué)信息技術(shù)課程教學(xué)內(nèi)容中操作系統(tǒng)模塊教學(xué)部分內(nèi)容的描述為“操作系統(tǒng)的簡單使用”和理解“操作系統(tǒng)簡單工作原理”[1]。經(jīng)過20年左右的信息技術(shù)教育發(fā)展，學(xué)生的操作系統(tǒng)應(yīng)用能力大幅提高，在該模塊教學(xué)過程中適當(dāng)融入原理對應(yīng)程序的調(diào)試、運行和結(jié)果討論，對提高教學(xué)效果和教學(xué)質(zhì)量，有一定積極作用。

1.2 磁盤調(diào)度算法

磁盤是計算機系統(tǒng)中重要的資源，磁盤調(diào)度是操作系統(tǒng)研究的重要內(nèi)容之一。如圖1所示簡要描述了磁盤的結(jié)構(gòu)。磁盤調(diào)度算法是研究磁盤存儲器管理的算法。旨在提高磁盤的利用率，從而服務(wù)于提高整體計算機系統(tǒng)性能。常見的磁盤調(diào)度算法有先來先服務(wù)FCFS(First-Come, First Served)，最短尋道時間優(yōu)先SSTF(Shortest Seek Time First)和電梯調(diào)度算法（SCAN算法）等。其中能引起學(xué)生濃厚興趣且跟日常生活結(jié)合緊密的是電梯調(diào)度算法[6]。

圖1 磁盤結(jié)構(gòu)圖Fig.1 Structure of the disk

2 電梯調(diào)度算法

最短尋道時間優(yōu)先算法雖能獲得較好尋道性能，卻可能導(dǎo)致某個進(jìn)程的“饑餓”(Starvation)現(xiàn)象發(fā)生。若不斷有新進(jìn)程到達(dá)，且其即將訪問的磁道與磁頭所在磁道的距離較近，這種新進(jìn)程的請求必須優(yōu)先滿足，導(dǎo)致較遠(yuǎn)距離的磁道永遠(yuǎn)不能得到訪問，即“饑餓”(Starvation)現(xiàn)象發(fā)生。對SSTF算法修改后形成的電梯調(diào)度算法，可防止老進(jìn)程出現(xiàn)“饑餓”現(xiàn)象。電梯調(diào)度算法模擬電梯的運行原理，磁頭朝某一方向運行，逐次掃描且滿足所經(jīng)有請求的磁道的訪問請求，直至同一方向所有請求的磁道得以滿足；然后磁頭調(diào)轉(zhuǎn)方向，重新進(jìn)行另一方向的掃描和對發(fā)出請求的磁道進(jìn)行服務(wù)。

3 電梯調(diào)度算法的應(yīng)用與實現(xiàn)

為讓學(xué)生體驗、理解和分析電梯調(diào)度算法，該部分設(shè)計實現(xiàn)了一個電梯調(diào)度的實例，以便課堂教學(xué)所用。

3.1 電梯調(diào)度算法實例

假定一磁盤有100個柱面，編號為0一99，磁頭當(dāng)前正在磁道33處為一個請求服務(wù)。若請求隊列的先后順序為86，17，91，26，95，且磁頭向磁道號減少方向訪問。試采用電梯調(diào)度算法完成上述請求，分析并寫出磁頭移動的順序。如表1所示呈現(xiàn)了電梯調(diào)度算法完成上述請求的磁道訪問順序。

表1 電梯調(diào)度算法應(yīng)用實例Tab.1 An example of scan algorithm

表1呈現(xiàn)了電梯調(diào)度算法解決問題的磁頭訪問順序。由于初始狀態(tài)磁頭停靠在33號磁道，且磁頭向磁道號減少方向訪問，則接受訪問的磁道號為26和17；然后磁頭調(diào)轉(zhuǎn)方向，向磁道號增大方向移動，依次訪問86，91和95號磁道。因此，此實例中，電梯調(diào)度算法訪問的磁道順序為：26，17，86，91，95。

3.2 電梯調(diào)度算法核心代碼

上述程序段描述了磁盤調(diào)度算法的基本工作原理。磁頭朝磁道號減少方向運行，逐次掃描且滿足所經(jīng)有請求的磁道的訪問請求，直至同一方向所有請求的磁道得以滿足；然后磁頭調(diào)轉(zhuǎn)方向，磁頭朝磁道號增大方向運行，重新進(jìn)行掃描和對發(fā)出請求的磁道進(jìn)行服務(wù)。

3.3 電梯調(diào)度算法實驗結(jié)果

運行電梯調(diào)度算法程序，依次加入磁道號86，17，91，26，95到訪問請求隊列，便可模擬電梯調(diào)度算法訪問磁道的過程。如圖2所示顯示的是此訪問請求序列被服務(wù)的部分截圖。

圖2呈現(xiàn)的電梯調(diào)度算法實驗結(jié)果表明，當(dāng)前磁頭停靠在86號磁道，磁臂移動方向為由內(nèi)向外，從而依次為86，91和95號磁道提供的訪問請求服務(wù)。

圖2 電梯調(diào)度算法實驗結(jié)果Fig.2 The result of the experiment of scan algorithm

4 結(jié)語

該工作實現(xiàn)了電梯調(diào)度算法的工作原理展示；編程實現(xiàn)了電梯調(diào)度算法思想。實驗運行過程能體現(xiàn)電梯調(diào)度算法的核心原理，可以有效地激發(fā)學(xué)生探索程序設(shè)計算法的興趣，積極投身信息技術(shù)教育教學(xué)活動，發(fā)現(xiàn)并分析身邊的事物體現(xiàn)的算法思想，一定程度達(dá)到提高信息技術(shù)教育教學(xué)質(zhì)量的目的。

引用

[1] 教育部關(guān)于印發(fā)《中小學(xué)信息技術(shù)課程指導(dǎo)綱要(試行)》的通知[J].教育部政報,2001(Z1):63-68.

[2] 王進(jìn)學(xué).淺析小學(xué)信息技術(shù)教育存在的問題與有效對策[J].考試周刊,2019(A0):107-108.

[3] 陳紫揚.人工智能技術(shù)與小學(xué)信息技術(shù)課程的融合[J].中國信息技術(shù)教育,2021(15):88-91.

[4] 王蕾.信息技術(shù)課堂教學(xué)中微項目設(shè)計的實證研究:以《生活中的算法》為例[J].中國信息技術(shù)教育,2020(24):24-27.

[5] 林茶香.計算機操作系統(tǒng)現(xiàn)狀與發(fā)展分析[J].數(shù)字技術(shù)與應(yīng)用,2021,39(9):192-194.

[6] 孔祥煜.單部電梯的優(yōu)化SSTF調(diào)度算法[J].海峽科技與產(chǎn)業(yè),2018(12):43+47.