電梯調度算法的應用與實現*

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

1.甘肅省定西市隴西縣和平鄉黃寨小學；2.蘭州工業學院計算機與人工智能學院；

3.甘肅省定西市隴西縣文峰鎮東鋪小學；4.甘肅省定西市隴西縣翠屏小學

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

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

為適應快速發展的信息技術領域環境，切實提高信息技術教育教學質量，滿足當下學生對信息技術學習的需求，在信息教育教學過程中，除了踐行基本的信息技術知識和能力教育教學外，探索融入算法思想的教學，有一定的積極意義[4]。

本文以操作系統中典型磁盤調度算法之一，電梯調度算法的應用與實現為例，討論了在信息技術教學過程中融入算法教學的方案。結合中小學生興趣愛好、理解和接受能力，以比較容易理解的電梯調度算法原理的講解、程序的編寫和運行、程序運行結果的分析討論為教學環節，激發學生觀察事物的興趣，培養學生理解和分析身邊算法的能力，達到擴展操作系統知識模塊學習的目的，更好地為提高信息技術教育教學質量服務。

1 操作系統

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

1.1 操作系統知識模塊

《中小學信息技術課程指導綱要（試行）》文件中指出，操作系統是中小學信息技術課程教學內容的模塊之一。該指導綱要發布于2000年，對中小學信息技術課程教學內容中操作系統模塊教學部分內容的描述為“操作系統的簡單使用”和理解“操作系統簡單工作原理”[1]。經過20年左右的信息技術教育發展，學生的操作系統應用能力大幅提高，在該模塊教學過程中適當融入原理對應程序的調試、運行和結果討論，對提高教學效果和教學質量，有一定積極作用。

1.2 磁盤調度算法

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

圖1 磁盤結構圖Fig.1 Structure of the disk

2 電梯調度算法

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

3 電梯調度算法的應用與實現

為讓學生體驗、理解和分析電梯調度算法，該部分設計實現了一個電梯調度的實例，以便課堂教學所用。

3.1 電梯調度算法實例

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

表1 電梯調度算法應用實例Tab.1 An example of scan algorithm

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

3.2 電梯調度算法核心代碼

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

3.3 電梯調度算法實驗結果

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

圖2呈現的電梯調度算法實驗結果表明，當前磁頭停靠在86號磁道，磁臂移動方向為由內向外，從而依次為86，91和95號磁道提供的訪問請求服務。

圖2 電梯調度算法實驗結果Fig.2 The result of the experiment of scan algorithm

4 結語

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

引用

[1] 教育部關于印發《中小學信息技術課程指導綱要(試行)》的通知[J].教育部政報,2001(Z1):63-68.

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

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

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

[5] 林茶香.計算機操作系統現狀與發展分析[J].數字技術與應用,2021,39(9):192-194.

[6] 孔祥煜.單部電梯的優化SSTF調度算法[J].海峽科技與產業,2018(12):43+47.