linux 24系统调度分析.docVIP

一． 前言 在开源操作系统中，Linux的发展最为显著，到目前为止，它在低端服务器市场已经占据了相当大的份额。从必威体育精装版的Linux 2.6系统来看，Linux的发展方向主要有两个：嵌入式系统和高端计算领域。 调度系统对于操作系统的整体性能有着非常重要的影响，嵌入式系统、桌面系统和高端服务器对于调度器的要求是很不一样的。Linux调度器的特点主要有两个： 核心不可抢占； 调度算法简单有效。 由于Linux适用于多种平台，本文所指缺省为i386下的SMP系统。    二． 相关数据结构 在Linux中，进程用task_struct表示，所有进程被组织到以init_task为表头的双向链表中（见[include/linux/sched.h]SET_LINKS()宏），该链表是全系统唯一的。所有CPU被组织到以schedule_data（对界后）为元素的数组之中。进程与所运行的CPU之间可以相互访问（详见下）。 所有处于运行态的进程（TASK_RUNNING）被组织到以runqueue_head为表头的双向链表之中，调度器总是从中寻找最适合调度的进程。runqueue_head也是全系统唯一的。 下面分别介绍这些与调度器工作相关的数据结构。 1． init_tss TSS，Task State Segment，80x86平台特有的进程运行环境，尽管Linux并不使用TSS，但将TSS所需要描述的信息保存在以cpu号为索引的tss_struct数组init_tss中，进程切换时，其中的值将获得更新。 2． task_struct 在Linux中，线程、进程使用的是相同的核心数据结构，可以说，在2.4的内核里只有进程，其中包含轻量进程。一个进程在核心中使用一个task_struct结构来表示，包含了大量描述该进程的信息，其中与调度器相关的信息主要包括以下几个： i. state Linux的进程状态主要分为三类：可运行的（TASK_RUNNING，相当于运行态和就绪态）；被挂起的（TASK_INTERRUPTIBLE、TASK_UNINTERRUPTIBLE和TASK_STOPPED）；不可运行的（TASK_ZOMBIE），调度器主要处理的是可运行和被挂起两种状态下的进程，其中TASK_STOPPED又专门用于SIGSTP等IPC信号的响应，而TASK_ZOMBIE指的是已退出而暂时没有被父进程收回资源的僵尸进程。 ii. need_resched 布尔值，在调度器中用于表示该进程需要申请调度（详见调度器工作流程）。 iii. policy 在Linux 2.4中，进程的调度策略可以有三种选择：SCHED_FIFO（先进先出式调度，除非有更高优先级进程申请运行，否则该进程将保持运行至退出才让出CPU）、SCHED_RR（轮转式调度，该进程被调度下来后将被置于运行队列的末尾，以保证其他实时进程有机会运行）、SCHED_OTHER（常规的分时调度策略）。另外，policy中还包含了一个SCHED_YIELD位，置位时表示主动放弃CPU。 iv. rt_priority 用于表征实时进程的优先级，从1-99取值，非实时进程该项应该为0。这一属性将用于调度时的权值计算（详见就绪进程选择算法）。 v. counter 该属性记录的是当前时间片内该进程还允许运行的时间（以CPU时钟tick值为单位，每个进程的counter初值与nice值有关，nice越小则counter越大，即优先级越高的进程所允许获得的CPU时间也相对越多），并参与就绪进程选择算法。在Linux 2.4中，每个（非SCHED_FIFO实时）进程都不允许运行大于某一时间片的时间，一旦超时，调度器将强制选择另一进程运行（详见调度器工作流程） vi. nice 用户可支配的进程优先级，将参与就绪进程选择算法，同时该值也决定了该进程的时间片长度（详见下）。 vii. cpus_allowed 以位向量的形式表示可用于该进程运行的CPU（见调度器工作流程）。 viii. cpus_runnable 以位向量的形式表示当前运行该进程的CPU（相应位为1）。如果不在任何CPU上运行，则为全1。这一属性和cpus_allowed属性结合，可以迅速判断该进程是否能调度到某一CPU上运行（位与）。 ix. processor 本进程当前（或最近）所在CPU编号。 x. thread 用于保存进程执行环境（各个寄存器的值以及IO操作许可权映射表），内容与TSS相近。因为TSS以CPU id为索引，而Linux无法预测被替换下来的进程下一次将在哪个CPU上运行，所以这些信息不能保存在TSS中。 3． current 核心经常需要获知当前在某CPU上运行的进程的task_struct，在Lin