2024年4月21日发(作者：)

ｌ｛）８　福　建　电脑　２０１３年第２期　

基于Ｌｉｎｕｘ随机进程调度算法的实现　

俞露　

（南京师范大学计算机科学与技术学院江苏南京２１００００）　

【摘　要】：本文分析了Ｌｉｎｕｘ　０．１１版本中的进程调度算法，并在此基础上设计了一种新的　

调度算法——进程随机调度算法。本文利用Ｗｉｎｌｍａｇｅ软件导出（导入）相应的进程调度文件至　

Ｗｉｎｄｏｗｓ系统（Ｌｉｎｕｘ系统），利用Ｅｄｉｔｐｌｕｓ软件将原有的进程调度算法替换成新的调ｋ　Ｓ－法，实　

现了Ｗｉｎｄｏｗｓ平台和Ｌｉｎｕｘ平台的交互，最后成功地完成了Ｌｉｎｕｘ内核的重新编译。　

【关键词】：Ｌｉｎｕｘ；内核；进程随机调度　

０、引言　

程的优先权．采取优先权调度算法来选择随后要　

管理进程是操作系统的重要任务之一　进程　执行的任务　

的调度（也称短程调度）则是进程管理的重中之　

２、优先权调度算法（Ｌｉｎｕｘ

Ｏ．１　１）：　

＿

重。在单处理器的环境中．任意时刻内存中有且仅　循环检查任务数组中的所有任务．根据每个　

ｅｒ．来选取该　

有一个进程占有处理器资源处于运行态．其余进　

就绪态任务剩余执行时间的值ｃｏｕｎｔ

程则处于等待态或就绪态。那么．操作系统怎样来　

值最大的一个任务．即所需剩余执行时间越长的　

并利用ｓｗｉｔｃｈ　ｔｏｆ）函数切换到　

分配处理器资源．又是怎样来防止进程的饥饿和　

任务的优先权越高，

死锁？开源的Ｌｉｎｕｘ操作系统的内核可以满足我　该任务　若所有就绪态任务该值都为０，表示此刻　

们的好奇心．我们可以在掌握Ｌｉｎｕ）【操作系统进　

所有任务的时间片都已经运行完毕．于是就根据　

程调度机制的基础上设计新的调度算法．实现对　

任务的优先权值ｐｒｉｏｒｉｔｙ．重置每个任务的运行时　

问片值ｃ０ｕｒｉｔｅｒ，ｃｏｕｎｔ：ＣＯｕｎｔ／２＋ｐｒｉｏｒｉｔｙ，再重新执　

行循环检查所有任务的执行时间片值　

３、随机调度算法及实验实现　

Ｌｉｎｕｘ内核调度函数决定采用何种调度策略　

选择就绪进程运行．确保进程所获得的ＣＰＵ访问　首先循环检查任务数组中的所有任务．将就　

ＬｉｎＵＸ内核重新编译　

１、Ｌｉｎｕｘ进程调度过程　

时间和其指定的优先级以及进程类型相匹配．消　

绪态进程依次从小到大标号．　并统计处于就绪态　

除进程对ＣＰＵ资源的饥饿状态　

进程的总数ｓｕｍ。利用ｉｉｆｉｆｅｓ产生随机数，选择标　

．

Ｌｉｎｕｘ内核中有关进程调度管理的文件为　号为ｉｉｆｆｉｅｓ％ｓｕｍ的进程作为ｓｗｉｔｃｈ　函数所切

ｔｏＯ　

ｓｃｈｅｄ．ｃ文件．在ｓｃｈｅｄ．ｃ文件中有一个重要的函　

换的进程　

数ｓｃｈｅｄｕｌｅ０负责选择系统中下一个将要运行的　

进程。　

同时．和上述算法一致．若所有进程的时问片　

是否都已耗尽．则重置每个任务的运行时间片值　

它首先对所有的任务进行选择．唤醒任何一　

ｃｏｕｎｔｅｒ。　

３．１实验平台　

个已经得到信号的任务　

其次．针对任务数组中的每个任务，检查其报　硬件平台：ＰＣ机　

警定时值ａｌａｒｍ　如果任务的ａｌａｒｍ时间已经过期　

（ａｌａｒｍ＜ｉｉｉｅｓ１，则在它的信号位网中设置　ｆ

操作系统：Ｌｉｎｕｘ　

辅助软件：Ｗｉｎｌｍａｇｅ、Ｅｄｉｔｐｌｕｓ　

３．２实验内容　

ＳＩＧＡＬＲＭ信号，然后清ａｌａｒｍ的值，ｆ　ｆｆｉｅｓ是一个　

修改Ｌｉｎｕｘ　０．１　１巾内核调度函数ｓｃｈｅｄｕｌｅＯ　

全局变量．是系统从开机开始算起的滴答数）如果　

进程的信号位图中除被阻塞的的信号外还有其他　函数．将原有的优先级调度算法修改成为随机｛Ｊ吉Ｉ　

并且重新编译内核。　

的信号．并且读进程处于可中断睡眠状态．则置进　

度算法．

程为就绪状态　

Ｉｊｎｕｘ调度函数是根据进程的时间片确定进　

３．３实验步骤　

①搭建Ｌｉｎｕｘ　０．１　ｌ平台，安装Ｗｉｎｌｍａｇｅ、Ｅｄ　

２０１３年第２期　福　建　电脑　１０９　

ｉｔｐｌｕｓ软件。　

／／以下代码是从任务数组的最后一个任务开始循环处理．　

②进入Ｌｉｎｕｘ内核，用ｍｃｏｐｖ命令将ｓｃｈｅｄ．ｃ　

并跳过不含任务的数组槽　

文件复制到相应磁盘巾　

ｗｈｉｌｅ，（：－－－ｉ）＇　

｛　

③用ＷｉｎＩｍａｇｅ软件将Ｌｉｎｕｘ系统相应磁盘　

ｉｆ　ｆ！　－－ｐ、，　

巾的ｓｃｈｅｄ．ｃ文件提取至Ｗｉｎｄｏｗｓ文件系统。④用　

ｃｏｎｔｉｎｕｅ；　

ＥｄｉｔｐｌＩｕｓ软件编辑ｓｃｈｅｄ．ｃ文件．修改进程捌度算　

（（　ｐ）一－＞ｓｔａｔｅ＝＝　队ＳＫ—ＲＵＮＮＩＮＧ＆＆　Ｐ）一＞　

ｃｏｕｎｔｅｒ＞Ｏ１　

法并保存　

ｆ　

⑤用ＷｉｎＩｍａｇｅ软件将相应磁盘中的ｓｃｈｅｄ．Ｃ　

ｓＬｌⅡｌ＋＋：　

／／统计处于就绪态并且时问片未耗尽的进程总数　

文件提取至ＬｉｎｔＵＸ系统下　

ｎｏ［ｈｉ＝ｉ；　

⑥进入Ｈｎｕｘ内核．用ｍｃｏｐｙ命令将修改后　

／／为每一个处于就绪态并且时间片未耗尽的进程编号。　

的ｓｃｈｅｄ．Ｃ文件复制到相应磁盘中　

ｎ＋＋：　

⑦用ｍａｋｅ　ｃｌｅａｎ语句清除以前编译的可执　

ｌ　

｝　

行文件及配置文件　

ｉｆ（ｓｕｍ）ｂｒｅａｋ；　

⑧用ｍａｋｅ语句重新编译内核。　

，／如果ｓｕｍ的值不为零．则存在ｃｏｕｎｔｅｒ值不等于０的进　

程，那么跳出最上层的ｗｈｉｌｅ循环，执行任务切换程序。否则代　

３．４实验部分代码　

表所有进程的时间片都已经使用完毕．需要重新设置时间片　

ｖｏｉｄ　ｓｃｈｅｄｕｌｅ（ｖｏｉｆ）　

值．重新执行。　

ｆ　

ｆ０　＝＆ＬＡＳＴ＿＿１　．ＳＫ；Ｐ＞＆ＨＲＳＴ＿ＴＡＳＫ；一１３）　

ｉｎｔ　ｉ，ｎ，．ｓｕｍ，ｒａｎｄ．，ｎｅｘｔ；　

ｉｆ　Ｐ）　

ｉｎｔ　ｎｏ［ＮＲ＿ＴＡＳＫＳ］；　

（　ｐ）一＞ｃｏｕｎｔｅｒ＝（（　ｐ）一＞ｃｏｕｎｔｅｒ＞＞１）＋（　ｐ）一－＞ｐｒｉｏｒｉ－－　

／／ｎｏ数组用于为内存中可以运行的进程（任务）编号。　

ｔｙ；　

／／ｓｕｍ记录可以参加调度的进程（任务）总数。　

ｌ　

／／ｒａｎｄ记录随机产生的数字。　

ｒａｎｄ＝ｊｉｆｉｅｓ％ｓｕｍ；／／ｊｉｆｉｆｅｓ为时钟滴答数．在此用来产生随机　

／／ｎｅｘｔ下一次访问的进程（任务）号。　

数　

ｓｔｒｕｃｔ　ｔａｓｋ

—

ｓｔｒｕｃｔ　ｐ；　

ｎｅｘｔ＝ｎｏ［ｒａｎｄ］；　

，，指向任务结构指针的指针　

ｓｗｉｔｃｈ　ｔｏ（ｎｅｘｔ）；／／ｔ￣换到任务号为ｎｅ：ｘｔ的任务。并运行。　

ｆｏｒｔｐ＝＆ＬＸＳ＇Ｉ＿’１＇ＡＳＫ；ｐ＞＆ＨＲＳ＇１’＿］　ＳＫ；一Ｐ）　

｝　

／从任务数组中的最后一个任务开始查找　

４、总结　

ｉｆ　ｐ）｛　

，，如果任务的ａｌａｒｍ时间已经过期（ａｌａｒｍ＜ｊｉｉｆｅｓ），在信号　

本次实验实现了进程的随机调度，算法简单，　

位图中置ＳＩＧＡＬＲＭ信号，然后清ａｌａｒｍ。　

且时间复杂度和空间复杂度都不高。在实际的运　

ｉｆ（　ｐ）一＞ａｌａｒｍ＆＆　ｐ）－＞ａｌａｍｌ＜ｊｉｍｅｓ）｛　

用中，根据系统的需求和实际情况，可以设计诸如　

（　ｐ）－＞ｓｉｇｎａｌｌ＝（１＜＜（ＳＩＧＡＬＲＭ－１））；　

（　＇ｐ）－＞ａｌａｒｍ＝Ｏ；　

多级反馈队列、彩票法等更加复杂的算法．在调度　

１　

的过程中更好地体现进程的优先级别。　

，／如果信号位图中除去被阻塞的信号外还有其他信号并　

且任务处于可中断状态．则置任务为就绪状态。　

ｉｆ“（　ｐ）一＞ｓｉｇｎａｌ＆￣（＿ＢＬＯＣＫＡＢＬＥ＆（　ｐ）－－－＞ｂｌｏｃｋｅｄ））＆＆（＇　ｐ）　

参考文献：　

一

＞ｓｔａｔｅ＝＝ＴＡＳＫ

【１】赵炯．Ｌｉｎｕｘ内核０．１１详细注释［Ｍ】．机械工业出版社，　

＿

ＩＮＴＥＲＲＵＰＴＩＢＬＥ１　

ｐ）一．＞ｓｔａｔｅ＝ＴＡＳＫ＿ＲＵＮＮＩＮＧ；　

２００４：７６－７７　

｝　

【２】孙忠秀．操作系统教程【Ｍ】．高等教育出版社，２０１２：一　

／／这是调度程序的主要部分　

ｗｈｉｌｅ（１）　

［３］ｃｎ２００８．读Ｌｉｎｕｘ内核０．１１完全注释［ＥＢ／ＯＬ］．２００６—　

ｆ　

３—７［２０１３—１—２８］．ｈｔｔｐ：／／ｏｓ．ｃｈｉｎａｕｎｉｘ．ｎｅｔ／ａ２００６／０３０７／　

／，变量的初始化。　

１００１／０００００１００１５７１．ｓｈｔｍ１．　

ｓｕｍ＝０；　

『４１雏勇，王青，李明树．Ｌｉｎｕｘ内核的实时支持的研究与实　

ｎ＝Ｏ：　

现Ｕ】．计算机研究与发展．２００２（０４￣ｌ：　

ｎｅｘｔ＝０：　

ｉ＝ＮＲ

『５１钟汉如，王创生．嵌入式Ｌｉｎｕｘ中调度算法的实现及优　

＿

ＴＡＳＫＳ；　

Ｐ＝＆ｔａｓｋ［ＮＲ＿％＇ＡＳＫＳ］；　

化ⅡＪ．计算机工程与科学．．２００２０３＇，ｌ：