基于Linux系统中进程调度分析

[摘要]Linux是一个多用户多任务的操作系统,Linux中实现了对多个进程公平、高效的调度,并不是采用单一的调度策略,而是几种调度策略有机地综合应用。

[关键词] 进程调度 优先级 时间片轮转 实时进程

在任何一种操作系统中,进程调度一直是一个核心问题,进程调度策略的选择对整个系统性能有至关重要的影响,一个好的调度算法应该考虑很多方面:公平、有效、响应时间、周转时间、系统吞吐量等等,但这些因素之间又是相互矛盾的,最终的取舍根据系统要达到的目标而定,本文以Linux操作系统为例,分析其进程调度策略,以期对进程调度过程有更深层次的认识。

一、 Linux的进程调度

Linux支持多进程,进程控制块PCB(Process Control Block)是系统中最为重要的数据结构之一,用来存放进程所必需的各种信息,PCB用结构task-struct来表示,包括进程的类型、进程状态、优先级、时钟信息等,Linux系统中,进程调度操作由schedule()函数执行,这是一个只在内核态运行的函数,函数代码为所有进程共享。

二、 Linux进程调度时机

Linux的进程调度时机与现代操作系统中的调度时机基本一致,为了判断是否可以执行内核的进程调度程序来调度进程,Linux中设置了进程调度标志need-resched,当标志为1时,可执行调度程序.通常,Linux调度时机分以下两种情况:(1)主动调度:指显式调用schedule()函数明确释放CPU,引起新一轮调度.一般发生在当前进程状态改变,如:进程终止、进程睡眠、进程对某些信号处理过程中等,(2)被动调度:指不显示调用schedule()函数,只是PCB中的need-resched进程调度标志,该域置位为1将引起新的进程调度,而每当中断处理和系统调用返回时,核心调度程序都会主动查询need-resched的状态(若置位,则主动调用schedule()函数),一般发生在新的进程产生时、某个进程优先级改变时、某个进程等待的资源可用被唤醒时、当前进程时间片用完等。

三、Linux进程调度策略

一般来说,不同用途的操作系统的调度策略是不同的,Linux进程调度是将优先级调度、时间片轮转法调度、先进先出调度综合起来应用,Linux系统中,不同类型的进程调度策略也不一样。

1. 与进程调度相关的数据结构

每个进程都是一个动态的个体,其生命周期依次定义的数据结构为:TASK-RUNNING,TASK-INTERRUPTIBLE,TASK-UNINTERRUPTIBLE,TASK-ZOMBIE和TASK-STOPPED,一个进程在其生存期间,状态会发生多次变化,与其数据结构相对应的即是Linux进程的状态,分别是:运行态、等待态、暂停态和僵死态。

2. 进程状态及其转换过程的描述

进程创建时的状态为不可打断睡眠,在do-fork()结束前被父进程唤醒后,变为执行状态,处于执行状态的进程被移到run-queue就绪任务队列中等待调度,适当时候由schedule()按调度算法选中,获得CPU,若采用轮转法,即时,由时钟中断触发timer-interrupt(),其内部调用schedule(),引起新一轮调度,当前进程的状态仍处于执行状态,因而把当前进程挂到ruil-queue队尾。

获得CPU且正在运行的进程若申请不到某资源,则调用sleep-on()或interruptible-sleep-on()睡眠,其task-struct进程控制块挂到相应资源的wait-queue等待队列,如果调用sleep-on(),则其状态变为不可打断睡眠,如果调用interruptible-sleep-on(),则其状态变为可打断睡眠,Sleep-on()或interruptible-sleep-on()将调用schedule()函数把睡眠进程释放.

3.进程分类和相应的进程调度策略

Linux系统中,为了高效地调度进程,将进程分成两类:实时进程和普通进程(又称非实时进程或一般进程),实时进程的优先级要高于其他进程,如果一个实时进程处于可执行状态,它将先得到执行,实时进程又有两种策略:时间片轮转和先进先出,在时间片轮转策略中,每个可执行实时进程轮流执行一个时间片,而先进先出策略每个进程按各自在运行队列中的顺序执行且顺序不能变化。

在Linux中,进程调度策略共定义了3种:

Linux系统中的每个进程用task-struct结构来描述,进程调度的依据是task-struct结构中的policy、priority、counter和rt-priority,PCB中设置Policy数据项,其值用于反映针对不同类型的进程而采用的调度策略。SCHED- RR和SCHED-FIFO用于实时进程,分别表示轮转调度策略和先进先出调度策略;SCHED-OTHER表示普通进程,也按照轮转调度策略处理。这三类调度策略均基于优先级.PCB中设置Priority数据项,其值为普通进程的调度优先级.普通进程的可用时间片的初始值即为该值,该值通过系统调用是可以改变的。

PCB中设置rt-priority数据项,其值是实时进程专用的调度优先级,实时进程的可用时间片的初始值即为该值,该优先级也可以用系统调用来修改,PCB中设置counter数据项,用于进程可用时间片时值的计数,初始值为rt-priority或Priority,进程启动后该值随时钟周期递减。

通过对Linux进程调度策略的简单分析,可以看出多进程的管理是一种非常复杂的并发程序设计,每个进程的状态不仅由其自身决定,而且还要受诸多外在因素的影响,而在此基础上的进程调度,为了保证操作系统的稳定性、提高效率和增加灵活性,还必须采用很多方法,这些都是值得我们去研究和探讨的。

参考文献:

[1]刘振鹏李亚平王煜:操作系统[M].北京:中国铁道出版社,2003

[2]赵明富李太福陈鸿雁:Linux嵌入式系统的实时性分析[J].电脑知识与技术,2003,29(18):53―55