（计算机应用技术专业论文）基于linux的进程调度算法的改进与实现.pdf

独创性声明 本人声明所呈交韵学位论文是本人在导师指导下遗行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其儋人已经发表或撰写过鹃研究成聚， 毡不包含 本人为获得江南大学娥其它教育机构的学位戚证书而使用过的材料 与我一嚣忑孬豹弱恚对零研究掰傲熬任舞贾献均邑在谚文中作了嚼 确的说明并表示谢意 签名： 日期；年多月即日 关于论文使用授权的说嚷 本学位论文作者完全了解江南大学有关保留、使用学位论文的规 定：江南大学有权保留并向匡家宥关部门或静t 橱送交论文的复印件和 磁盘，允许论文被查隧和借阔，珂虢将学位论文的全帮或部分内容编 入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、 汇编学位论文，并且本入电子文襁耱内容秘纸质论文蠹孽内容相一致。 保密的学位论文在解密后也遵守此规定。 馘：件罴糕 摘要 摘要 随着l i n u x 系统的逐渐推广，它被越来越多的计算机用户所了解和应用，各 国政府都在鼓励和支持l i n u x 在本国的发展。0 ( 1 ) 调度算法推出后，使调度器的 时间复杂度从o ( n ) 降到了0 ( 1 ) ，又激起了人们对基于l i n u x 的进程调度算法的 研究。 本文首先对l i n u x 系统进行了简要的介绍，介绍了国内外在调度算法方面的 研究现状，分析了课题研究的背景和意义。然后介绍了进程管理的相关理论知识。 其次，详细研究了o ( 1 ) 调度算法及其在l i n u x2 6 内核中的具体实现。0 ( 1 ) 调度器中增加了数据结构r u n q u e u e ，就绪队列被分成a c t i v e 和e x p i r e d ，结合 b i t m a p 口不必遍历整个就绪队列，查找n e x t 进程的时间复杂度降为0 ( 1 ) 。进程 运行时间片的重新分配更及时；动态优先级的计算过程更简单，计算时机更分散； 调度时机更宽松，提高了调度器的实时性能；调度流程更简单。也指出了，在 0 ( 1 ) 调度器下，不同用户执行相同的程序，他们创建的进程将获得相同的运行时 问片和周转时间。这样对高级别用户是不公平的。 最后，引入了用户级别的概念，证明了o ( 1 ) 调度器的以上不足。提出了一种 基于用户级别的进程调度策略，通过给不同用户指派不同的级别，使不同级别用 户创建的进程的时间片不同，以此使他们的周转时间不同，高级别用户将获得比 低级别用户更短的周转时间，使各级别的用户得到与其级别相适应的周转时间， 更加体现进程调度的公平性原则；并且，一般情况下，该调度策略下o 级用户的 周转时间比在0 ( 1 ) 调度策略下短。 0 ( 1 ) 调度器的研究紧跟了调度算法研究领域的前沿；用户级别的引入、基于 用户级别的进程调度策略的提出，开拓了进程调度研究的新思路，一定程度上促 进了我国自主操作系统的研究和发展。 关键字：l i n u x ，进程调度，周转时间，o ( 1 ) 调度算法，用户级别 江南大学硕士学位论文 b s t r a c t w i t ht h ep o p u la r 泣a t i o no fi j n u xo p e r a t es y s t e m ，“h a sb e e nl 【n o w na n du s e db y m o r ea i l dm o r cu s e r sa n dm o s to fg o v e 咖e n t sa r ee n c o u r a 舀n g 卸ds u p p o ni t s d e v e l 叩m e n t 1 1 1 e0 ( 1 ) p 眦s ss c h e d u l j n ga l g o r i t h m 化d u c e dt h ec o m p l e x i t yo f t h e t i m ef 咖0 ( n ) t oo ( 1 ) 1 ti n t e r e s t sr e s e a r c h e r st or c s e a r c ht h es c h e d u l i n ga l g o r i t h m b a s e do nl - j n u x n ei j n u xs y s t e mw a si n t i o d u c e df i r s t l y a n dt h es i g n i f i c a t i o no ft h i st h e s i sa n d t h ei e s e a r c hs t a t u so fs c h e d u l i n ga l g o r i t l l l l la r ei n t r o d u c e dt o o n e n ，t h e0 ( 1 ) s c h e d u l i n ga l g 叫t h ma n di t si m p l e m e n t a t i o ni nu n u x2 6k e m e l a r ef c s e a r c h e dd e t a i l e d d a t as t m c t i l r cm n q u e u ew a sa d d e da n di t ss e p a r a t e dj n t ot w o p a n s ：a d i v ea n de x p i r e d i l l t e g r a t ew i t hb i t m a p 【】，t h et i m e 咖p l e x i t ) ro fo ( 1 ) s c h e d u l e ri sr c a c h e dt oo ( 1 ) t h er e a 1 1 0 c a t i n go fp m c e s st i m e s l i c ei sm o r ei nt i m e t h ec a i c u l a t ec o u r s eo fp r o c e s sp r i o r i t yi sm o r es i m p l ea n dt h eo p p o n u n i t yi sm o r c d e c e n t r a l i z a t i o n t h e 叩p o n l l n i t yo fp r o c e s ss c h e d u l i n gi sm o f cr e l a x e d ，s ot h er e a l t i m ep e r f b m l a n c ew a si m p r o v e d t h ep m c e s so fs c h e d u l ej ss i m p l e rt o o a n dal a c k o ft h eo ( 1 ) s c h c d u l c ri sp o i n t e dt o o ：d i f f e r e n tu s e r sm nt h es 砌ep m g r 锄w i l lg e tt h e s 砌et i i i l e s l i c ca n dt 啪a r o u n d 血n e n sn o tf a i rt oh i g h e rp r i o r i t yu s e r s a tl a s tt h ec o n c e p tu s e rp r i o r i t yw 硒i n t m d u c e d t h es h o n a g em e n t i o n e da b o v eo f o ( 1 ) s c h e d u l e rw a sp m v e d 1 n h ep 眦e s ss c h e d u l i n gp o l i c yb a s e do 丑u s e r 州o r i t yw a s p r c s e n t e d n ep o l i c yd i s p a t c h e sd i 骶r e n tu s e rp r i 硎t yt ou s e r s ，d i 虢r e n tt j m e s l i c c a n dt u m a r o u n dt i m eo fp r o c e s st h a tw a sf o r k e db yu s e r sw j t hd i 丘b r e n tp r i o r i t y c o m p a r e dw i t hl o w e rp r i o r i t yu s e r s ，i tl e t st h et u m a r o u n dt i m eo fp r o c c s sf b r k e db y h i g l l e rp r i o r i t yu s e 幅s h o n e r t h ep o l i c y 舀v e st h ep r o c e s st u m a r o u n dt i m ea c c o r d i n g t oi t su s e r sp r i o r i ty s ot h ep m c e s ss c h e d u l i n gp o l i c yb a s e do nu s e rp r i o r i t yi sf h i r e f 1 nc o m m o n n d i t i o n s ，t h ep f o c e s sw i l lg e ts h o n e r t u 功a r o u n dt j m ew h e nn l nb y0 p r i 硎t yu s e r si nm i sp o l i c y t h er e s e a r c ho ft h eo ( 1 ) s c h e d u l e rf o l l o w so nt h eh e e i so ft h er c s e a r c hi nt l l i s f i e l d t h ei n t r o d u c t i o no fu s e rp r i o r i t ya n dt h ep r o c e s ss c h e d u l i l l gp o l i c yb a s e do n u s e rp r i o r i t yb m a d e nt h et c c h n i q u e so ft h e p r o c c s ss c h e d u l i i l ga l g o r i t h ma n d i m p r o v e dt h er e s e a i c ha n dd e v e l o p m e n to f0 si no u rc o u n 缸y k e y w o n l s ：i j n u x ，p r o c e s ss c h e d u l i n g ，t u m a r o u n dt i m e ，o ( 1 ) s c h e d u l i n ga l g o r i t h m ， u s e rp r i o r i t y 4 第一章绪论 1 1l i n u x 系统简介 1 1 什么是l i n 似 第一章绪论 l i n u x 是当今流行的操作系统之一简单地说，l i n u x 是一套免费使用和自 由传播的类u n i x 操作系统，它主要用于基于i i l t e lx 8 6 系列c p u 的计算机上1 2 l o 这个系统是由全世界各地的成千上万的程序员设计和实现的。其目的是建立不受 任何商品化软件的版权制约的、全世界都能自由使用的u n i x 兼容产品。 u n u x 的出现，最早开始于一位名叫l j n u st b r v a l d s 的计算机业余爱好者， 当时他是芬兰赫尔辛基大学的学生。 i j n u x 以它的高效性和灵活性著称。它能够在p c 计算机上实现全部的u n i x 特性，具有多任务、多用户的能力。i j n u x 是在g n u 公共许可权限下免费获得 的，是一个符合p o s i x 标准的操作系统。 i j n u x 之所以受到广大计算机爱好者的喜爱，主要原因有两个，一是它属于 自由软件，用户不用支付任何费用就可以获得它和它的源代码，并且可以根据自 己的需要对它进行必要的修改，无偿对它使用，无约束地继续传播。另一个原因 是，它具有u i x 的全部功能，任何使用u n i x 操作系统或想要学习u n i x 操作系 统的人都可以从u n u x 中获益。 1 1 2l i n u x 的组成 i j n u x 一般有四个主要部分：内核、s h e l l 、文件结构和实用工具。 1 l i n u x 内核 内核是系统的心脏，是运行程序和管理像磁盘和打印机等硬件设备的核心程 序。它从用户接受命令并把命令送给内核去执行。 2 l i n u xs h e l l s h e h 是系统的用户界面，提供了用户与内核进行交互操作的一种接口。它接 收用户输入的命令并把它送入内核去执行。实际上s h e l l 是一个命令解释器，它 解释由用户输入的命令并且把它们送到内核。不仅如此，s h e u 有自己的编程语 言用于对命令的编辑，它允许用户编写由s h e u 命令组成的程序。 同i j n u x 本身一样，s h e l l 也有多种不同的版本。目前主要有下列版本的s h e l l ： ( 1 ) b o u m es h e l l ：是贝尔实验室开发的。， ( 2 ) b a s h ：是g n u 的b o u m ea g a i ns h e l l ，是g n u 操作系统上默认的s h e l l 。 5 江南大学硕士学位论文 ( 3 ) k o ms h e i l ：是对b o u m es h e l l 的发展，在大部分内容上与b o u m es h e l l 兼容。 ( 4 ) c s h e l l ：是s u n 公司s h e l l 的b s d 版本。 3 l i n u x 文件结构 使用u n u x ，用户可以设置目录和文件的权限，以便允许或拒绝其他人对其 进行访问。i j n u x 目录采用多级树形结构，图1 1 表示了这种树形等级结构。用 户可以浏览整个系统，可以进入任何一个已授权进入的目录，访问那里的文件。 文件结构的相互关联性使共享数据变得容易，几个用户可以访问同一个文 件。u n u x 是一个多用户系统，操作系统本身的驻留程序存放在以根目录开始的 专用目录中，有时被指定为系统目录。图1 1 中那些根目录下的目录就是系统目 录。 图1 1 n u x 的目录结构 内核、s h e u 和文件结构一起形成了基本的操作系统结构。它们使得用户可以 运行程序、管理文件以及使用系统。此外，i j n u x 操作系统还有许多被称为实用 工具的程序，辅助用户完成一些特定的任务。 4 l i n u x 实用工具 标准的l j n u x 系统都有一套叫做实用工具的程序，它们是专门的程序，例如编辑 器、执行标准的计算操作等。 1 1 3l i n u x 的特性 l i n u x 操作系统在短短的几年之内得到了非常迅猛的发展，这与u n u x 具有 的良好特性是分不开的。i j n u x 包含了u n i x 的全部功能和特性。简单的说，l j n u x 具有以下主要特性： 1 开放性 开放性是指系统遵循世界标准规范，特别是遵循开放系统互连( 0 s i ) 国际 标准。凡遵循国际标准所开发的硬件和软件，都能彼此兼容，可方便地实现互连。 2 多用户 6 第一章绪论 多用户是指系统资源可以被不同用户各自拥有使用，即每个用户对自己的资 源( 例如：文件、设备) 有特定的权限，互不影响。 3 多任务 多任务是现代计算机的最主要的一个特点。它是指计算机同时执行多个程 序，而且各个程序的运行互相独立。i j n u x 系统调度每一个进程平等地访问微处 理器。由于c p u 的处理速度非常快，其结果是，启动的应用程序看起来好像在 并行运行。事实上，从处理器执行一个应用程序中的一组指令到i j n u x 调度微处 理器再次运行这个程序之间只有很短的时间延迟，用户是感觉不出来的。 4 设备独立性 u n u x 是具有设备独立性的操作系统，它的内核具有高度适应能力，随着更 多的程序员加入i j n u x 编程，会有更多硬件设备加入到各种i j n u x 内核和发行版 本中。另外，由于用户可以免费得到i j n u x 的内核源代码，因此，用户可以修改 内核源代码，以便适应新增加的外部设备。 5 提供了丰富的网络功能 完善的内置网络是u n u x 的一大特点。u n u x 在通信和网络功能方面优于其 他操作系统。其他操作系统不包含如此紧密地和内核结合在一起的连接网络的能 力，也没有内置这些联网特性的灵活性。而l j n u x 为用户提供了完善的、强大的 网络功能。 6 可靠的系统安全 l i n u x 采取了许多安全技术措施，包括对读、写进行权限控制、带保护的子 系统、审计跟踪、核心授权等，这为网络多用户环境中的用户提供了必要的安全 保障。 7 良好的可移植性 u n u x 是一种可移植的操作系统，能够在从微型计算机到大型计算机的任何 环境中和任何平台上运行。可移植性为运行i j n u x 的不同计算机平台与其他任何 机器进行准确而有效的通信提供了手段，不需要另外增加特殊的和昂贵的通信接 口。 1 2 进程调度算法 操作系统由四大功能模块组成：进程管理、存储器管理、设备管理和文件 管理，进程管理是其中最重要的一个模块。调度算法研究是进程管理的主要内容， 它的优劣关系到整个系统的性能。目前，国内外众多学者对该领域己进行了多年 广泛的研究，提出了很多种调度算法。下面对其作一下简要回顾： 7 江南大学硕士学位论文 1 2 1 常用调度算法 常用的进程调度算法有多种，它们大多还被目前流行的操作系统所采纳。下 面介绍其中最常见、经典的几个： 1 先来先服务调度算法f c f s f c f s ( f i r s tc o m ef i r s ts e n ，i c c ) 是一种最简单的进程调度算法。采用该调 度算法的系统按照进程进入就绪队列的时间先后将就绪进程排列在队列中，先入 队者在前( 靠近队首) ，后入队者在后。这样，队首进程就是最先进入就绪队列 的进程。每次需要进行进程调度时，调度程序将给就绪队列的队首进程分配资源 和处理机，让其运行，直到它运行完成或因发生某种事件而阻塞。 2 最短作业( 进程) 优先调度算法 s j ( p ) f ( s h o n e s tj o b ，p - 0 c e s s 髓t ) 是指以作业，进程的运行时间为依据， 对短作业进程进行优先调度的进程调度算法。由于作业进程在执行完毕之前， 它的运行时间是不可被计算的，所以这里的运行时间只能是事先估计的。s j ( p ) f 可分别用于作业调度和进程调度。 3 时问片轮转调度算法 为了保证人一机交互的及时性，很多系统一般都采用时间片轮转算法进行进 程调度。系统将用户创建的进程按一定原则( 如先来先服务原则) 组织在就绪队列 中，把c p u 的运行时间分割成一个个长短相等( 或者基本相等) 的微小时间区 间，即“时间片“i l l l e s l i c c ) ”。每次调度时把c p u 分配给队首进程，并令其独占 c p u 执行一个时问片。如果该时间片内进程执行完毕，它将释放c p u 、退出就 绪队列，调度器从就绪队列再选择一个进程让它占用c p u 来运行；如果在时间 片结束时进程还未运行完，则该进程将被剥夺c p u 的使用权，由计时器发出时 钟中断，调度器将它送入就绪队列的末尾，等待下一次执行，然后把c p u 分配 给就绪队列中另一个就绪进程( 如图1 2 所示) ，让它也执行一个时间片：如果进 程在时间片结束前阻塞，则c p u 当即进行切换【3 】。用户创建的进程就是这样断断 续续的执行的，直到最终完成。虽然在微观上( 微小时间片的数量级) 进程的执 行是断续的，作业运行是不连续的，但是在宏观上，用户的任何请求、服务总能 够在用户可以接受的时间内及时得到响应，让用户觉得只有他自己在使用一台主 机。 第一章绪论 图1 2时问片轮转调度 ( a 避程p a 为队首并占用c p u( b ) 进程p a 用完时间片被送入就绪队列末尾，进程p b 成为队 首并占用c p u 和时间片轮转调度算法相关的几个概念： ( 1 ) 进程的服务时问s 在没有其它进程干扰时，让进程p 一直占有处理机执行其程序，它需要在处 理机上执行一段时间后才能完成程序的执行，这段时间长度叫进程的服务时间。 ( 2 ) 轮转周期c 调度程序将所有就绪进程都调度一遍让其占用处理机来执行的时间间隔，或 者是某进程相邻两次被调度到的时间间隔。 ( 3 ) 最后一个时间段t 。 从轮转调度的算法描述中可以总结出它的一个特点：进程的整个运行过程需 要在处理机上执行n 个时间片和在晟后一个时间片内执行段时间( 小于或等于 时间片) ，本文称这段时间为最后一个时间段。 4 优先级调度算法 为了照顾到紧迫型作业能及时被处理机调度到，引入了优先级调度算法。进 程在进入就绪队列时，系统根据进程的紧迫程度，为每个进程赋予一个优先级， 越紧迫的进程的优先级越高，越早被调度到。调度程序在进行进程调度时，选择 就绪队列中优先级虽高的进程，为它分配处理机。 9 江南大学硕士学位论文 优先级调度又可进一步分成两种方式： ( 1 ) 非抢占式 在这种方式下，系统一旦把处理机分配为就绪队列中优先级最高的进程后， 该进程便一直占有c p u 执行下去，直到完成或因发生某事件使进程自动放弃处 理机时，其它进程方可占有处理机。 ( 2 ) 抢占式 这种方式下，系统同样把处理机分配给就绪队列中优先级最高的进程，使之 执行。但系统中一旦出现优先级更高的进程时，调度程序就停止当前进程的执行， 将处理机分配给优先级更高的进程。 优先级也可以分为静态优先级和动态优先级。 5 多级反馈队列调度算法 首先，设置多个就绪队列，为每个队列赋予不同的优先级。第一个队列的优 先级最高，队列的优先级逐个降低。并且仅当第1 i 任何一个队列中没有进程 时，调度程序才让第i + 1 队列中的进程运行。为每个队列中的进程分配的运行时 间片大小也各不相同，优先级越高的队列中的进程的时间片越小。当一个新进程 被创建后，首先将它插入第一个队列的末尾，按f c f s 原则排队。如果该进程在 此队列中被调度到时问片用完还没有执行完成，将其放到第二个队列中等待执 行。如果在第二个队列中仍未执行完毕，将其放入第三个队列中，依此类推。在 最后一个队列中按照时间片轮转算法调度。 1 2 2 国内外研究现状 虽然自从1 9 6 6 年j h s a l l e x e r 提出进程的概念以后，人们对进程调度问题 的研究已经经历了很多年，但早期的研究主要是针对一般目的的通用系统的调度 而作的研究。随着计算机科学的发展，出现了嵌入式系统等应用于某些特殊场合、 特殊目的的系统，经典的调度算法并不能完全满足他们的需求。于是后来学者在 前人研究的基础之上，又提出了一些新的算法。 目前，国内外在实时系统的进程调度方面的研究比较多。 实时系统分为硬实时系统和软实时系统。硬实时系统对时间的要求非常苛 刻，如果进程未能在既定时间内完成，就会导致系统失败。在一些对时间有严格 要求的场合，硬实时的应用也比较广泛，对此的研究相对较多。 文献【4 l 【5 1 解决的是每个进程都不允许被其它进程抢先调度的问题；文献【6 】用 处理的是另一类问题一一每个进程可被任意进程抢先调度。 x u s c h e d u l i i l 2 算法【8 】能对一组给定的进程在单个处理器上进行静态调度，以 找到一种调度解答，使得这一组进程满足时间约束和关系约束。文献1 9 j 在 x u s c h e d u l i n g 算法的基础上提出了一种预处理算法，它能够根据时间约束和关 1 0 第一章绪论 系约束尽量明确有排斥关系的每对进程的调度顺序，减少有关进程的截止时间。 在实时系统中，系统的正确性不仅依赖于计算的逻辑结果还依赖于结果产生 的时间【l o j 。文献【1 1 l 研究了开放式实时系统的调度理论和分析方法，提出了一种 调度对象的层次模型，适用于开放式实时调度环境。文献【1 2 l 【1 3 】分析了开放式实 时系统的特征，并提出了一种基于c u s 和t b s 服务器的调度方案。 优先级调度算法由于可以照顾到不同进程的需求，是一个比较公平的调度算 法。在优先级算法的基础上，根据具体应用的需要对其进行改进又产生了许多算 法。任务的优先级通常由任务的一个或多个特征参数来确定，如果仅仅是由某个 特征参数来确定是不够的【。金宏等提出了一种任务优先级的综合设计算法【1 5 l ， 该算法将任务的相对截止期和空闲时间这两个特征参数结合起来，综合设计任务 的优先级表，使得截止期越早或空闲时间越短，任务的优先级越高，而且任务的 优先级由相对截止期和空闲时间唯一确定。其它的基于优先级的调度算法还有： 单调速率算法、截止期最早优先( e a r l i e s t ，d e a d l i n ef i r s t ，简称e d n 、价值最高最 优先1 1 7 】、空闲时问最短最优先( 1 e a s ts l a c kf i r s t ，简称l s f ) 、最早放行最优先【1 8 】、 可达截止期最早最优先等等。 l j 删x 是一个非常高效的操作系统，其原因要归功于调度器的卓越设计。由 于其源码的开放性，现在操作系统设计的思想和技术能够不断运用于它的新版本 中【l j 。又由于可以修改其内核来定制自己的操作系统，近年来，基于i j n l l 】【的进 程调度研究比较活跃。文献【1 9 l 研究了n u x 的进程调度过程，指出i j n u x 采用 的是时间片轮转调度和可剥夺调度优先级相结合的调度策略。高珍1 2 0 l 等研究了 i j n u x 内核在进程调度时对对称多处理器的支持。 安智平、张德运等提出了一种进程的主从调度模型【2 “，并在i j n u x 系统中具 体实现。 有些研究则侧重于对现有调度算法在l j n u x 中的实现上，黄斌在文献【2 2 】中 通过修改i j 肌x 内核的进程调度模块，将1 2 1 节中的经典调度算法一多级反馈 队列调度算法在i j n u x 系统中得以具体实现，并取得了比原调度系统更好的平均 周转时间。 由于u n u x 的设计初衷就是为了满足个人计算机用户，它的调度系统对实时 的支持不是很好，在某些实时应用场合显得略有些不足。对于此，很多学者做了 大量研究，改进i j n u x 的实时性能。文献i 2 4 j 对l i n u x 进程调度的实时性进行了分 析，结合嵌入式实时系统的需求，提出了一种在x 8 6 环境下单一运行级别( 核 心态) 嵌入式实时u n u x 系统的方案并加以实现。 江南大学硕士学位论文 1 3 本文研究课题 1 3 1 论文范围与课题意义 本文主要研究了0 ( 1 ) 调度算法及其在l i n u x 系统中的实现，引入用户级别的 概念，提出基于用户级别的进程调度策略。 不讨论多处理机s m p 的调度问题，也不讨论实时进程的调度问题。 o ( 1 ) 调度器的研究紧跟了调度算法研究领域的前沿。现有调度算法大都只关 注进程本身，试图使所有进程的周转时间都降低，这是很难做到的。本文引入用 户级别的概念，提出基于用户级别的进程调度策略，使不同级别的用户得到不同 的周转时间，着重缩短高级别用户的周转时间，能更大范围的满足各级别用户的 需求。本文开拓了进程调度研究的新思路，一定程度上促进了我国自主操作系统 的研究和发展。基于用户级别的进程调度策略在多任务多用户的操作系统中将得 到一定的应用。 1 3 2 本文主要工作 本人所做的主要研究工作如下： ( 1 )详细研究了o ( 1 ) 调度算法及其在l i n u x2 6 内核中的具体实现。o ( 1 ) 调 度器中增加了数据结构r u n q u e u e ，就绪队列被分成a c t i v e 和e x p i r e d ，结合位 映射数组b i t m a p 不必遍历整个就绪队列，查找n e x t 进程的时间复杂度降为 o ( 1 ) 。进程运行时问片的重新分配更及时：动态优先级的计算过程更简单，计算 时机更分散；调度时机更宽松，提高了调度器的实时性能；调度流程更简单。描 述了和调度相关的主要接口函数及其功能，比较了2 4 和2 6 调度器性能之间的 差别。本文也指出了，在0 ( 1 ) 调度器下，不同级别的用户执行相同的程序，他 们创建的进程将获得相同的运行时间片和周转时间。这样对高级别的用户是不公 平的。 ( 2 )引入了用户级别的概念，证明了o ( 1 ) 调度策略的一个不足：在相同条件 下，不同级别的用户执行相同的程序他们的周转时间相同。提出了一种基于用户 级别的进程调度策略，通过给不同用户指派不同的级别，使不同级别用户创建的 进程的时间片不同，以此使他们的周转时间不同，高级别用户将获得比低级别用 户更短的周转时间，使各级别的用户得到与其级别相适应的周转时间，更加体现 进程调度的公平性原则；并且，在一般情况下，该调度策略下0 级用户的周转时 问比在o ( 1 ) 调度策略下短。 第一章绪论 1 3 3 内容组织 各章节的内容分布如下： 第一章首先对l i n u x 系统进行了简要的介绍，介绍了国内外在调度算法方面 的研究现状，分析了课题研究的背景和意义。 第二章介绍了进程管理的相关理论知识。首先是进程的定义及其特征；接着 描述了进程的三种基本状态，详细分析了基本状态间的转换及其转换的条件；然 后介绍了进程控制块p c b 及其主要构成；最后介绍了进程调度算法的评价指标。 第三章是对0 ( 1 ) 调度器的研究。首先分析了与l i n u x2 6 进程调度密切相 关的两个重要数据结构s t r u c tr u n q u e u e 和s t r u c tt a s k _ s t r u c t ；详细描述了 进程时间片的计算方法、优先级的计算过程、n e x t 进程的查找过程、调度的时 机、调度的策略和调度器的工作流程，介绍了和调度相关的主要接口函数及其功 能。最后从算法分析和h a c k b e n c h 测试两个方面对l i n u x2 4 和2 6 进程调度器 进行了对比。 第四章是基于用户级别的调度策略的研究部分。首先引入了用户级别的概 念，接着证明了在o ( 1 ) 调度策略下的一个不足之处，然后提出了基于用户级别 的进程调度策略，证明了在该调度策略下，在其它条件相同的情况下，不同级别 的用户执行相同的程序将得到不同的周转时间，并且高级别用户将获得比低级别 用户更短的周转时间；举例证明了在一般情况下，和0 ( 1 ) 调度策略下的周转时 间相比，0 级用户的周转时间缩短，1 级用户的周转时间大致相同。最后，用实 验结果论证了以上观点的正确性。 第五章是结论，同时介绍了今后需要进一步完善的工作。 1 3 第二章进程管理 第二章进程管理 计算机操作系统由四大功能模块组成：进程管理、存储器管理、设备管理和 文件管理，其中进程管理是最重要的一个模块。在多进程的操作系统中，进程调 度一个全局性的、关键性的问题，它对系统的总体设计、系统的实现、功能设置 以及各方面的性能都有着决定性的影响i 矧。根据调度结果所作的进程切换的速 度，也是衡量一个操作系统性能的重要指标。这一章我们将着重介绍进程管理的 相关知识。 2 1 进程的定义 “进程”这个概念是美国麻省理工学院的j h s a l l e x e r 在1 9 6 6 年提出的， 后来在该学院的删l t i c s 系统和i b m 公司的c t s s 3 6 0 系统中引入，之后有很多 学者从不同角度提出了他们对“进程”的理解： 1 进程是程序的一次执行； 2 进程是可以与别的计算并发执行的计算【冽； 3 进程可定义为一个数据结构及能在其上进行操作的一个程序； 4 进程是一个程序及其数据在处理机上顺序地执行时所发生的活动【2 6 】； 5 进程是程序在一个数据集合上的运行过程，是系统进行资源分配和调度的 一个独立单位； 6 进程是可并发执行的程序在一个数据集合上的运行过程； 从以上定义可以看出，虽然各学者对进程有各自的见解，但一点他们是有共识的， 那就是进程是个动态的概念，这也是进程最基本的特性。 2 2 进程的特征 进程是进程实体的执行过程，它是系统进行调度和资源分配的最小单位，它 有以下五个基本特征： ( 1 ) 动态性 进程是动态的，它是进程实体的运行过程，动态性是进程最基本的特征。动 态性还表现为：进程有自己的生命周期，它由创建而产生，由调度而执行，因得 不到资源而暂停执行，以及由撤消而消亡。 ( 2 ) 并发性 江南大学硕士学位论文 并发性指多个进程实体可以在一段时间内同存于内存中、同时运行。并发性 不仅是进程的重要特征也是操作系统的重要特征。 ( 3 ) 独立性 独立性指进程实体是能够独立运行的基本单位，也是系统中独立获得资源和 独立参与调度的基本单位。一个程序如果想参加运行就必须先建立进程，才能从 系统获得资源，进而参与、获得调度而运行。 ( 4 ) 异步性 异步性指各进程实体是以异步方式运行的，进程实体之间是独立地向前执行 的。因此，操作系统就必须采取一些措施来保证有先后次序的各进程之间能够按 照预定的顺序协调运行。 ( 5 ) 结构上的特征 从结构上看，进程实体是由程序段、数据段和进程控制块p c b ( p r o c e s s c o n t r o lb 1 0 c k ) 三部分组成，它们也叫“进程映像”。 2 3 进程的基本状态 进程是动态的概念，它有创建、执行、消亡的过程，这也是它的一个生命周 期。一个进程的生命期可以被划分为三种基本状态，通常来说，一个进程必须具 有这三种状态并且在某个时刻它只能是其中的一种状态。 2 3 1 就绪状态 一个进程已经具备运行条件，但由于无c p u 暂时不能运行的状态( 当调度给 其c p u 时，立即可以运行) 。处于就绪状态的进程叫就绪进程。在一个系统中可 以有多个就绪进程，系统通常把这些就绪进程排成一个或多个队列，称为就绪队 列。 2 3 2 执行状态 进程已被调度获得处理机，并在c p u 上运行。在单处理机系统中，只能有一 个进程处于执行状态；在多处理机系统中，则可能有多个进程同时处于执行状态。 处于执行状态的进程叫当前进程，在l i n u x 系统中，用c “r r 绷f 表示。 2 3 3 阻塞状态 进程因等待某种事件( 请求i 0 、等待某个信号量s i g n a l 、锁操作) 的发生而 暂时不能运行的状态( 即使c p u 空闲，该进程也不可运行) ，也可以称这种状态为 1 6 第二摩进程管理 等待状态或繇眠状态。处于隰塞状态的进程落被捧戮成一个绒多个酞两，称为阻 塞队列或等待队列。 在不霜酌操作系统中，避程静获态种类密些差异，毙热在l i n u x2 6 1 0 内 核中，进程被划分为七种状态：t a s n r u n n i n g 、t a s k i n t e r r u p t i b l e 、 t 矗s ( 一u k i 摊罩r r 馨p 羊i 瑟l e 、l 矗s k s 豫p 转、l 矗s 嚣l r 矗e 窭转、e l 罩z 铡b i e 、x i 羊一蚤a 蚤。 2 。毒进程状态的转换 遴程在菜令时刻总是处予蔡秘状态，随羲其叁炱豹雄进_ 耱终爨条 孛麴变缘， 进程的状态也随之改变。 鬻2 。l 逶攘基零状态转换嚣 ( 1 ) 就绪态斗执行态 鲶予裁缝状态的逡程，娄调疫程黟按照菜秘调发篱法必之分配了处理楗艇， 该进程就从就绪态转变为执彳亍态( 如图2 1 所示) 。 ( 2 ) 执行态卜裁缳态 处于执行状态的进程如网时间片用完或有更高优先级的进程需臻运行等原 因蔼被迫暂僚执行、被剥夺处理枫，该进程便由执行状态转变为就绪状态。同时， 下一个占有处理机的进程的状态变为执行状态。 ( 3 ) 执行态峰阻塞态 处于执行状态的进程囚提出某些请求而不能被满足、必须等待辩，它由执行 态转变为阻塞态。此时该进稷被插入譬q 相应的阻塞队列中去。例如：在s h e l l 命 令 中，第一个避程运行c a t 命令，将兰个文嵇连接越来著输爨。第二个进程送行 g r e p 命令，嵌从输入中选择所有包含单词“p r o c e s s ”的那些行。根据这两个进 程豹相对速波( 这取次于这巍令程痔鹣籀对复杂疫释器鑫瘊努酝到豹c 弼霹麓) ， 可能发生这种情况：“g r e p ”已经在运行，但输入还没有完成( c a t 还未执行完 1 7 江南大学硕士学位论文 毕) 。于是g r e p 就必须进入阻塞状态直到输入到来，即c a t 执行完成。 ( 4 ) 阻塞态+ 就绪态 处于阻塞状态的进程，当它等待的事件发生后，它就从阻塞态转变为就绪态。 此时，该进程从阻塞队列中被转移到就绪队列中。 例如，某个进程p 。被创建后进入就绪队列，此时它为就绪态；被调度器选中 后分配到处理机，它由就绪态变为执行态：时间片用完时他还未执行完毕，被调 度器剥夺处理机、重新被插入就绪队列，它由执行态变为就绪态：等再次被调度、 分配处理机后，它又由就绪态变为执行态，此时p 。要对就绪队列甩日h p h p 进行 操作，但另外一个进程p 。也在操作n 鲫e “e ，由于在l i n u x 系统中，所有对就 绪队列的操作都要先锁定该队列，故队列此时已经被加锁，进程p a 需等待进程 p b 操作完埘n g “p h e ，这时它不得不等待，由执行态变为阻塞态；直到进程p b 对就绪队列操作完成解锁后，进程r 被唤醒，从阻塞队列转移到就绪队列，由阻 塞态变为就绪态。 2 5 进程控制块p 进程控制块p c b ( p r o c e s sc o n t r o lb l o c k ) ，包含了进程的描述信息和控制信 息，并通过它表示进程的存在以及反应进程的变化，是刻画进程最重要的数据结 构，是进程存在的唯一标志。当系统创建一个新进程时，就为它建立一个p c b ； 进程结束时又回收其p c b ，进程也随之消亡。由于p c b 经常被系统访问、操作， 特别是被调度系统频繁的访问，为了提高系统的效率，大多操作系统都把p c b 常 驻内存。 一般来说，p c b 主要包括四类信息：进程标识信息、处理机状态信息、进程 调度信息和进程控制信息。对不同的操作系统，其进程控制块的结构并不完全相 同，而且同一操作系统的不同版本其结构也有所差异。在l i n u x 系统中，进程控 制块一直用数据结构s t r u c tt a s k s t r u c t 来表示，但不同的版本其数据成员是 不尽相同的。 2 6 调度算法评价指标 调度算法即调度策略是处理机调度的关键，选择的算法是否合适直接影响到 调度性能的优劣【2 8 1 。在讨论一个调度算法是否优劣之前，首先要确定其评价的指 标。通常使用的标准可分为两类：面向用户的和面向系统的【2 9 1 。 1 8 第二章进程管理 2 6 1 面向用户的指标 这是为了首先满足用户的需求时所应考虑的一些指标。经常使用的有以下几 点： 1 公平性 这是许多操作系统所追求的主要目标，特别是通用操作系统。公平性是指系 统应该平等地对待每个用户，所有用户都应该有同等的机会去竞争使用系统的各 种资源，防止某些进程长期独占处理机，避免出现某些进程因长时间得不到处理 机服务的饥饿现象。这种公平性主要体现在调度器选择进程去使用处理机时是公 平的。 本文认为，这种公平性应该是相对的公平，在进行进程调度时不仅要考虑该 进程的情况，还要综合考虑创建该进程的用户的情况和目前系统中所有进程的状 况。这一点我们将在第四章中再做详细的叙述。 2 响应时间 响应时间是指从用户提交请求开始，直到系统首次给出响应为止的这段时问 间隔。它包括： ( 1 ) 从键盘输入的请求信息传送到处理机的时间； ( 2 ) 处理机对请求信息进行处理的时间； ( 3 ) 将所形成的响应回送到显示器并显示的时问。 响应时间常用于评价分时操作系统的性能，分时系统中应尽量缩短进程的响 应时间，特别是交互式进程。 3 周转时间 周转时间是指任务从提交给系统开始，到任务完成为止的这段时间间隔。它 包括任务新创建后等待被处理机第一次调度的时间t 。；。和在处理机上运行的时 问t 。 4 优先权 每个进程要求被执行的紧迫程度是不同的，它们也是有轻重缓急的。实时进 程要求能够立刻被执行，否则将会造成严重的后果；有些普通进程则对时间不是 那么敏感，只有能被完成即可。我们可以为每个进程指派一个优先权来反应它们 的紧迫程度：越紧迫的进程的优先权越高，越早被调度到而执行；反之，进程的 优先权就越低，越晚被执行。 5 截至时间 截至时间是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。它 是用来评价实时系统的调度性能的重要指标。 1 9 江南大学硕士学位论文 2 6 2 面向系统的指标 这是为了满足系统要求时所要优先考虑的一些重要指标。 1 系统吞吐量 系统吞吐量是指在单位时间内系统所完成的作业数。它是评价批处理系统性 能的重要指标，因而，系统吞吐量高是选择批处理作业调度算法的重要准则。 2 处理机利用率 对于计算机系统来说，处理机是最重要、关键的资源，对于大、中型多用户 系统更是如此。因此，在大、中型系统中，在选择调度算法时，应尽量使处理机 保持繁忙状态，即处理机利用率要高。 3 各类资源平衡利用 不仅要提高处理机的利用率，还要尽量使系统内的各种资源都处于忙碌状 态，为此可以给不使用紧张资源的进程更高的优先权，使之尽快执行，从而提高 空闲资源的利用率。 2 7 本章小节 本章首先介绍了进程的定义，接着分析了进程的五个基本特征；然后描述了 进程的三个基本状态：就绪态、