Linux 2.4调度系统分析--转
|
副标题[/!--empirenews.page--]
简介：?本文详尽地分析了Linux 2.4内核中调度系统的工作原理，特别是i386体系结构下SMP系统的调度表现。通过对2.4调度系统实现原理及其细节的分析，文章在文末指出了2.4调度系统在功能上、实时性上以及多处理机系统表现上存在的不足，为后继的2.6系统的分析作铺垫。 在开源操作系统中，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也是全系统唯一的。 下面分别介绍这些与调度器工作相关的数据结构。 TSS，Task State Segment，80x86平台特有的进程运行环境，尽管Linux并不使用TSS，但将TSS所需要描述的信息保存在以cpu号为索引的tss_struct数组init_tss中，进程切换时，其中的值将获得更新。 在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中。 核心经常需要获知当前在某CPU上运行的进程的task_struct，在Linux中用current指针指向这一描述符。current的实现采用了一个小技巧以获得高效的访问速度，这个小技巧与Linux进程task_struct的存储方式有关。 在Linux中，进程在核心级运行时所使用的栈不同于在用户级所分配和使用的栈。因为这个栈使用率不高，因此仅在创建进程时分配了两个页（8KB），并且将该进程的task_struct安排在栈顶。（实际上这两个页是在分配task_struct时申请的，初始化完task_struct后即将esp预设为页尾作为进程的核心栈栈底，往task_struct方向延伸。） 因此，要访问本进程的task_struct，只需要执行以下简单操作： __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
此句将esp与0x0ffffe0作"与"运算，获得核心栈的首页基址，此即为task_struct的地址。 task_struct是用于描述进程的数据结构，其中包含了指向所运行CPU的属性。在Linux中，另有一个数据结构对应于CPU，可以利用它访问到某CPU上运行的进程，这个数据结构定义为schedule_data结构，包含两个属性：curr指针，指向当前运行于该CPU上的进程的task_struct，通常用cpu_curr(cpu)宏来访问；last_schedule时间戳，记录了上一次该CPU上进程切换的时间，通常用last_schedule(cpu)宏来访问。 为了使该数据结构的访问能与CPU的Cache line大小相一致，schedule_data被组织到以SMP_CACHE_BYTES为单位的aligned_data联合数组中，系统中每个CPU对应数组上的一个元素。 调度器并不直接使用init_task为表头的进程链表，而仅使用其中的"idle_task"。该进程在引导完系统后即处于cpu_idle()循环中（详见"其他核心应用的调度相关部分"之"IDLE进程"）。SMP系统中，每个CPU都分别对应了一个idle_task，它们的task_struct指针被组织到init_tasks[NR_CPUS]数组中，调度器通过idle_task(cpu)宏来访问这些"idle"进程（详见"调度器工作流程"）。
（编辑：东莞站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
?