geekos

李艾津，朱亮

（重庆文理学院 计算机学院，永川

402160）

摘要：本文介绍了教学用GeekOS操作系统的相关知识，重点对本系统要求完成的项

目三实验内容（四级队列反馈调度策略的实现）做了详细的讲解,与现有的时间片轮转调度策略做了对比分析。

关键字：GeekOS；四级调度；时间片轮转调度

GeekOS Scheduling Strategy Analysis

LI Aijin, ZHU Liang

(Chongqing University of Arts and Sciences, Commputer Institute, Yongchuan 402160)

Abstract: This paper describes the teaching GeekOS knowledge of the operating system,

with emphasis on the system required to complete the project three experimental content (4 queues implementation of feedback scheduling strategy) made a detailed explanation, with the existing time-slice round-robin scheduling strategy for doing compared and analyzed.

Keywords: GeekOS; four scheduling; time-slice round-robin scheduling

1 引言

操作系统是管理系统软，硬件资源，控制程序运行，改善人机界面，提供各种服务，合理组织计算机工作流程和为用户有效使用计算机提供良好运行环境的系统软件，它为用户使用计算机提供一个方便，灵活，安全，可靠的工作环境，也是其他应用软件赖以存在的基础。操作系统是计算机系统的重要组成部分，操作系统课程是计算机教育的必修课程，作为计算机专业的核心课程，不但高校计算机相关专业的学生必须学习操作系统，从事计算机行业的从业人员也需要深入了解它。

计算机操作系统课程是理论性和实践性都较强的课程，具有概念多，抽象，涉及面广的特点。在设置操作系统课程教学要求时，教师就要考虑对学生做出什么样的要求。是纯理论的对书本习题和概念做出解答就可以了呢，还是要求学生能动手参与实践。实践也有不同程度的要求，是单纯的实现操作系统的某些算法呢，还是实际编写或修改操作系统功能模块。由于实践环境的，许多高校目前都偏重对理论知识的要求，注重基本理论知识的掌握和一些典型算法的实践(一般选择UNIX或Linux作为实验环境，要求学生用C语言编程实现简单的进程创建，进程调度等算法)，所以学生基本没有机会去了解，实践操作系统的内部结构和实现技术。实践证明，要真正学好操作系统原理和设计技术，最好的方法就是让学生参与到操作系统的开发工作中。因此，越来越多的高校在开设操作系统理论课程的同时，会要求学生对现有操作系统进行功能改进或再开发，以增加学生对操作系统核心技术的实践，真正做到理论与实践相结合。

那么，能用作学生操作系统课程实践的平台有哪些呢？大家一般很容易想到使用现有的商业操作系统和开放源代码的操作系统，也有很多这样的操作系统可供学生选择，比较流行的有Linux，Minix等。虽然也有一些学校确实采用这些操作系统作为实践平台，但采用这些操作系统存在的缺点也是不容忽视的：这些操作系统一般都结构庞大，过于复杂，学生在短时间内很难理解，而且这些操作系统几乎已经实现了所有的功能(进程管理，存储器管理，文件系统等)，不需要学生自行设计或实现一些子系统，因此从教学实践的角度讲，价值不高。最好的方法不是选择一个完整的，实用的，庞大的商业操作系统，而是选择一个既具备基本操作系统核心功能，与实际使用的操作系统比较接近，但又易于理解，规模较小的操作系统作为教学平台，在这个教学平台上，学生可以修改和扩充基本系统以实现更多功能，这种操作系统称为教学操作系统。

当我们决定选用教学操作系统作为我们的操作系统课程实践平台后，剩下的工作就是在现有的多种教学操作系统中选择一种。教学操作系统有两大类，一类是针对RISC结构MIPS处理器的，另外一类是针对CISC结构的Intel IA-32(或X86)通用处理器的。这样分类是因为:处理器是操作系统运行的硬件环境中最重要的部分。 针对RISC结构MIPS处理器的教学操作系统有Nachos(Not Another Completely Heuristic Operating System)和OS/161。其中Nachos是建立在软件模拟的虚拟机之上的教学操作系统，采用MIPS R2/3000的指令集，能模拟主存，中断，网络以及磁盘系统等所必须的硬件系统，美国加州大学伯克利分校多次采用该操作系统作为课程设计平台。OS/161是运行在与操作系统无关的System/161模拟器上的，操作系统代码是MIPS对应的机器代码。但无论是Nachos还是OS/161，若学生使用Windows或Linux 开发环境的话，都需要使用交叉编译器才能把代码编译成MIPS相应的机器代码。

Minix和GeekOS是针对CISC结构的Intel IA-32 (或X86)通用处理器的。其中，Minix是Andrew S。 Tanenbaum(AST)于1987年开发的，目前主要有1。5 版和2。0 版两个版本在使用。Minix系统是免费的，可以从许多FTP 上下载，但Minix是一个包括了虚拟内存管理，文件系统，设备驱动程序，网络和用户态程序等的比较完整的操作系统，它由两万多行代码组成，对于教学有点过于庞大和复杂，而且由于它已 经实现了操作系统的全部基本功能，没有留下合适的练习让学生自己完成。 大家知道，最通用的处理器是CISC结构的Intel IA-32 (或X86)通用处理器，所以选用针对该结构的教学操作系统是比较合适的，我们选用GeekOS作为操作系统课程设计平台主要原因还有:它是一个用C语言开发的操作系统，学生可以在Linux或UNIX环境下对其进行功能扩充，也可以在Windows下使用Cygwin工具进行开发，且其针对进程，文件系统，存储管理等操作系统核心内容分别设计了7个难度逐渐增加的项目供教师选择。我们将在后面的章节中详细为大家介绍GeekOS教学操作系统。

2 GeekOS及其调度策略

2.1 GeekOS概述

GeekOS是一个基于X86架构的PC上运行的微操作系统内核，由美国马理兰大

学的教师开发，主要用于操作系统课程设计，目的是使学生能够实际动手参与到一个操作系统的开发工作中。出于教学目的，这个系统内核设计简单，却又兼备实用性，它可以运行在真正的X86 PC硬件平台。作为一个课程设计平台，GeekOS由一个基本的操作系统内核作为基础，提供了操作系统与硬件之间的所有必备接口，实现了系统引导，实模式到保护模式的转换，中断调用及异常处理，基于段式的内存管理，FIFO进程调度算法以及内核进程，基本的输入输出(键盘作为输入设备，显示器作为输出设备)，以及一个用于存放用户程序的只读文件系统PFAT。

2.2 轮转调度算法

轮转法调度(Round-Robin ,RR)也称时间片调度，具体做法是：调度程序每次把CPU分配给就绪队列首进程/线程使用规定的时间间隔，称为时间片，通常为10ms~200ms，就绪队列中的每个进程/线程轮流地运行一个时间片，当时间片耗尽时，就强迫当前运行进程/线程让出处理器，转而排列到就绪队列尾部，等候下一轮调度，所以，一个耗时型进程/线程需要经过多次轮转才能完成。实现这种调度需要使用间隔时钟，进程/线程开始运行时，就将时间片的值置入间隔时钟内，发生间隔时钟中断时，表明连续运行且用光时间片，此时，时钟中断处理程序通知处理器调度进行进程/线程切换。RR调度策略可以防止那些很少使用设备的进程/线程长时间地占用处理器，导致要使用设备的那些进程/线程没有机会去启动设备。 轮转法调度是一种剥夺式调度，系统耗费在进程/线程切换上的开销比较大，这个开销与时间片的大小有关。如果时间片取值太小，将导致大多数里程/线程都不可能在一个时间片内运行完毕，就会频繁切换，开销显著增大，所以，从系统效率的角度来看，时间片取大一点好；另一方面，时间片的长度较大，那么，随着就绪队列中进程/线程数目的增加，轮转一次所耗费的总时间加长，即对每个进程/线程的响应速度均放慢，甚至时间片大到让进程/线程足以完成其所有任务，RR调度算法便退化成FCFS算法。为了满足用户对响应时间的要求，要么就绪队列中的进程/线程数量，要么采用变化的时间片长度，根据当前负载状况，及时调整时间片大小。所以，确定时间片长度要从进程数目、切换开销、系统效率和响应时间等多方面加以考虑。

2.3 多级反馈队列调度算法

多级反馈队列调度(Multi-Level Feedback Queue ,MLFQ)又称反馈循环队列，其主要思想是：由系统建立多个就绪队列，每个队列对应于一个优先级，第一个队列的优先级最高，第二个队列的优先级次之，其后队列的优先级逐个降低。较高优先级队列的进程/线程分配给较短的时间片，较低优先级队列的进程/线程分配给较长的时间片，最后一个队列进程/线程按FCFS算法进行调度。处理器调度每次先从第一个队列中选取执行者，同一队列中的进程/线程按FCFS原则排队，只有在未选到时，才从较低一级的就绪队列中选取，仅当前面所有队列为空时，才会运行最后一个就绪队列中的进程/线程。

进程/线程的优先级可事先规定。例如，使用设备频繁者优先级高，计算型进程/线程的优先级低；终端用户定为高优先级，非终端用户定为低优先级。优先级也可事先不规定，一个新进程/线程被创建后，首先移入第一个就绪队列末尾等待调度，如果能够在给定的时间片内完成，便可从系统中撤离；凡是耗尽时间片仍未运行结束的，就移入下一个就绪队列的末尾，直至进入最低优先级就绪队列。

MLFQ调度算法具有较好的性能，能满足各类应用的需要。对于分时交互型短作业，系统通常可在第一队列(最高优先级队列)规定的时间片内完成工作，使终端型用户感到满意；对于短的批处理作业，通常只需在第一队列和第二队列中各执行一个时间片就能完成工作，

周转时间仍然很短；对于长的批处理作业，它将依次在第一队列、第二队列、第三队列等各个队列中获得时间片运行。 MLFQ调度算法会导致“饥饿”问题。假如有一个长作业进入系统，它最终必将移入优先级最低的就绪队列中，如果其后有源源不断的短作业进入系统，且形成稳定的作业流，则长作业一直等待，陷入“饥饿”状态。解决此问题的一种有效方法是对于低优先级队列中等待时间足够长的进程提升其优先级，从而让它获得运行机会。如图1所示是三级调度算法示例。

2级就绪队列(低) 超过时间片 等待其它外设 要求启动其它外设 运行 选中，时间片200ms 1级就绪队列(中) 选中，时间片500ms 要求启动磁盘、磁带 等待磁盘、磁带 选中，时间片100ms 0级就绪队列(高)

图1 三级反馈队列调度算法示例

3 GeekOS调度策略实现及分析

3.1 GeekOS中的四级反馈队列调度策略实现

实现思想是：给四个准备运行队列不同的优先级，优先级别标记为数字0~3 ，如果数

字为0表示最高优先级，数字为3表示最低优先级。 首先，新创建的进程被入优先级最高的准备运行队列，即优先级为0的准备运行队列。若优先级为0的进程被调度后，在给定时间片内无法完成，那么进程就被移到下一优先级队列的尾部（即优先级为1的准备运行队列），以此类推，直到进程被放到优先级为3的队列为止。因此，要求运行时间较长的进程最终会被放入到优先级为3的准备运行队列。若进程被阻塞，每经过一个时间片，进程优先级都将增加1，所以当进程阻塞达连续的3个时间片后，又将升到最高优先级。进程调度总是优先调度优先级高的进程运行，当优先级为0的进程队列为空时，进程调度从优先级为1的队列选择进程调度。大家应该还记得系统中的空闲进程Idle ，在四级反馈队列调度中，该进程应始终放在优先级为3的进程队列尾部，以便系统中没有其他可调度进程时就运行它。 为实现四级队列，设计中首先要修改s_runQueue (在 src/GeekOS/kthread.c) 的定义，从原来的一个结构体改为一个4元素的结构体数组，每一个结构体元素用于存放一个优先级队列的队首指针。在进程调度时，首先在最高优先级（优先级0）的队列里面找，如果有进程存在，则调度它运行。如果没有，那就在次优先级的队列里面找，以此类推，直到找到一个进程投入运行为止。GeekOS系统将Idle (系统空闲) 进程始终放在优先级为3的进程队列末尾，且不允许移动到其他队列，以保证进程调度时一定能找到进程投入运行。 当实现四级反馈队列调度策略后，GeekOS系统就拥有2种进程调度策略，即单队列时间片轮转调度策略和四级反馈队列调度策略。那么系统究竟采用何种调度策略呢？调度策略的确定是通过系统调用Sys_SetSchedulingPloicy 实现的，函数原型为：static int Sys_SetSchedulingPloicy (struct Interrupt_State* state);

参数sate定义为如下struct Interrupt_Stae类型： struct Interrupt_State{ uint_t gs; uint_t fs;

uint_t es; uint_t ds; uint_t ebp; uint_t edi; uint_t esi; uint_t edx; uint_t ecx; uint_t ebx; uint_t eax; uint_t intNum; uint_t errorCode; uint_t eip; uint_t cs; uint_t eflags;

}; 系统使用ebx成员ecx成员记录调度策略和时间片长度，其中，state->ebx成员用于指定调度策略，它的取值为0或1，值为0代表系统采用时间片轮转调度策略，值为1则代表系统采用四级反馈队列调度策略，若取其他值则出错。State->ecx成员用于记录相应调度策略下的时间片长度。时间片长度默认值是4，用DEFAULT_MAX_TICKS（在timeer.c中定义）表示。将g_Quantum作为一个可以由系统调用来设置的全局变量，以实现可变时间片。

3.2 进程调度策略评价

进程调度策略的优劣可以用进程的运行时间（一个进程从创建到结束完成所需要花费的时间）来衡量。进程的运行时间可以通过系统调用 Sys_GetTimeOfDay得到。

要对扩充后GeekOS系统的这两种调度算法进行评价，可以在两个算法中分别用不同的时间片长度运行应用程序workload.exe来测算。如果图2、图3所示，分别测试了两种调度时间片为1ms和100ms时的运行时间。

图2 两种调度时间片为1ms时的运行时间

图3 两种调度时间片为100ms时的运行时间

经过测评知道在GeekOS系统中的四级反馈队列调度策略要优于时间片轮转调度策略。

3.3 进程调度策略分析

时间片轮转调度中要引起重视的是时间片的长度。从一个进程切换到另一个进程是需要一定时的--保存和装入寄存器值及内存映像，更新各种表格和队列等。假如进程切换(process switch) - 有时称为上下文切换(context switch)，需要5毫秒，再假设时间片设为20毫秒，则在做完20毫秒有用的工作之后，CPU将花费5毫秒来进行进程切换。CPU时间的20%被浪费在了管理开销上。

为了提高CPU效率，我们可以将时间片设为500毫秒。这时浪费的时间只有1%。但考虑在一个分时系统中，如果有十个交互用户几乎同时按下回车键，将发生什么情况？假设所有其他进程都用足它们的时间片的话，最后一个不幸的进程不得不等待5秒钟才获得运行机会。这将让用户不得不为一条简短命令而等待5秒钟。同样的问题在一台支持多道程序的个人计算机上也会发生。

所以一个时间片轮转调度的优劣，一般取决于它的时间片。时间片设得太短会导致过多的进程切换，降低了CPU效率；而设得太长又可能引起对短的交互请求的响应变差。将时间片设为100毫秒通常是一个比较合理的折衷。个人认为可以将时间片设置为动态的改变策略，根据进程的完成时间，动态改变时间 片，以达到CPU的利用率尽可能的提高，也不至于使交互请求响应变得太长。

针对可变级数队列反馈调度算法，就克服了这点缺点了，这里采用的是4级队列反馈调度算法，也就是包含四个就绪队列。这里的四个队列优先级依此变低，而且赋予每个队列不同的时间片，改变了时间片轮转调度策略中的时间片一尘不变的缺点。优先级越高时间片越低的特点，有助于克服饥饿现象。

它的执行方式是当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片结束时尚未完成，将其转入第二队列末尾。当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。仅当时间片空闲时，才调度第二个队列中的进程。(1~i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。（这里的n就是就绪队列的个数，GeekOS中采用的是4级）可以看出这个调度策略是一个可抢占型的调度策略，是个简单易实现且能满足大多数用户要求的策略。

4 结束语

大多数操作系统都有自己的不完善之处，比如说现在的Windows系列操作系统，也是在不断的更新版本中不断的修改以达到完善。现在的操作系统也在不断的接近人性化，这也将是未来操作系统的发展方向。这里的GeekOS也是如此，虽然现在的它只是一个用于教学的操作系统，但是GeekOS也有一定的发展空间，相信不久的将来我们将看到一个完美的GeekOS ，因为正在学习的我们中不乏有一部分天才存在，将会改写它、完善它。现在的GeekOS调度策略只有以上的两种方式 ，但是以后将会有更多的更优秀的调度算法，来改写现在的状况。

参考文献

[1] 黄廷辉，王宇英.计算机操作系统实践教程.北京：清华大学出版社，2007.5. [2] 孙钟秀，费翔林，骆斌.操作系统教程.北京：高等教育出版社，2008.4. [3] 罗宇，等.操作系统[M].2版.北京：电子工业出版社，2007.

[4] 毛德操，等.Linux内核源代码情景分析[M].杭州：浙江大学出版社，2002. [5] 尤晋元.UNIX操作系统教程[M].西安：西安电子科技大学出版社，2000. [6] 于渊.自己动手写操作系统[M].北京：电子工业出版社，2005. [7] 赵烔.Linux内核完全注释[M].北京：机械工业出版社，2004.

[8] 杨季文.80x86汇编语言程序设计[M].北京：清华大学出版社，1998.

[9] 沈美明，温冬婵.IBM PC汇编语言程序设计(第二版).北京：清华大学出版社，2001.