多处理器系统中的线程调度研究

摘要

随着超线程和多核等新兴技术不断涌现,当前的SMP系统硬件结构更加复杂,系统硬件性能也更加强劲,随之而来的问题是:传统的SMP操作系统已不能充分发挥现代SMP硬件系统性能,为了适应当前硬件技术的这种变化,我们有必要在研究传统SMP系统的基础上,对操作系统中那些不适应的部分加以改进或用新的算法替换,从而使软件系统能最大限度地发掘硬件系统的潜在性能。
　　 本论文首先介绍了课题研究背景和研究意义,简要阐述了目前在单个处理器物理封装中实现多个进程或线程并行执行的两大主流技术:同时多线程技术(Simultaneous Multi-Threading,SMT)和多核技术(Chip Mulfi-Processor,CMP),另外论文还概要介绍了L,inux操作系统以及该系统在研究smp系统调度时的重要作用。其次,论文剖析了经典的smp系统组织结构以及各种操作系统中常用的一些经典进程调度算法,这些硬件架构知识和软件概念都为我们后面研究smp操作系统进程调度算法打下了坚实基础。接下来论文将理论联系实际,以最新版本的Linux内核作为研究对象,详细剖析了它的进程调度系统。当前的Linux内核采用了一种全新的名为完全公平调度(Completely Fair Schedule,CFS)的进程调度策略,为了能够理解CFS的调度原理以及它对smp系统的相关支持,论文在详细介绍CFS调度原理的同时,剖析了对应的CFS调度源代码。论文最后章节总结了影响smp调度系统性能的几大关键因素,并分析了我们在设计smp调度系统时应注意的设计要点,以这些理论分析为基础,论文提出了一个高效的smp调度系统模型。
　　 在前面章节理论分析的前提下,论文还以一个针对Linux内核的smp系统进程调度优化作为结尾,介绍了我们应当如何对smp调度系统优化进行思考以及在有了优化方案后如何把方案应用于实践并做出实验及验证分析。

目录

文摘

英文文摘

第一章 绪论

1.1 课题研究背景

1.2 论文的主要工作

1.3 论文的组织结构

第二章 SMP系统及线程调度

2.1 SMP系统

2.1.1 基于总线的SMP

2.1.2 基于交叉开关的SMP

2.1.3 基于多级交换网络的SMP

2.2 进程与线程

2.2.1 进程概念及原理

2.2.2 线程概念及原理

2.3 进程调度及调度算法

2.3.1 调度算法分类

2.3.2 常用调度算法

2.4 本章小结

第三章 LINUX调度系统及CFS剖析

3.1 Linux内核调度器简史

3.2 O(1)调度器概要

3.3 完全公平调度器概要

3.3.1 模块化的调度器接口

3.3.2 CFS调度器

3.3.3 CFS组调度

3.4 CFS实现核心

3.5 红黑树介绍

3.6 CFS关键数据结构

3.6.1 struct task struct的变化

3.6.2 struct sched entity结构体

3.6.3 struct sched class结构体

3.6.4 struct cfs rq结构体

3.6.5 struct task_group结构体

3.7 CFS核心代码剖析

3.7.1 scheduler_tick(...)函数

3.7.2 task_tick_fair(...)函数

3.7.3 entity_tick(...)函数

3.7.4 update_curr(...)及_update_curr(...)相关函数

3.7.5 check_preempt_tick(...)函数

3.7.6 schedule(...)函数

3.7.7 put_prev_task_fair(...)及相关函数

3.7.8 pick_next_task_fair(...)及相关函数

3.8 源代码分析总结

3.9 CFS组调度支持

3.10 CFS与SMP

3.10.1 调度域

3.10.2 Linux SMP系统调度层级结构

3.10.3 CFS之SMP负载平衡

3.11 本章小结

第四章 高性能SMP调度系统研究

4.1 SMP调度基础

4.1.1 同步机制

4.1.2 局部性原理

4.1.3 SMP负载均衡策略

4.1.4 调度策略

4.2 高效SMP调度系统分析

4.2.1 较小粒度的锁

4.2.2 独立的运行队列

4.2.3 分级的负载平衡机制

4.2.4 高效SMP调度系统图例

4.3 Linux SMP调度优化

4.3.1 优化原理分析

4.3.2 Futex概要原理

4.3.3 内核改动分析及实现

4.3.4 简单验证及分析

4.4 本章小结

第五章 总结与展望

致谢

参考文献

攻硕期间取得的研究成果