电梯调度算法的应用与实现*

李自红李晓斌牛世军米凤霞

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.