基于源码分析的多核操作系统研究与人才培养实践

文章编号：1672-5913(2011)21-0081-03 中图分类号：G642 文献标识码：A

基金项目：2010年“国家大学生创新性实验计划项目”资助(101002827)；“2011年首都师范大学课程建设立项项目”资助。

作者简介：徐远超，男，讲师，研究方向为多核操作系统、并行与分布式计算。

摘 要：多核已成为处理器的主流，在传统的操作系统教学中引入操作系统如何支持多核的内容十分必要。本文从多核操作系统启动流程分析和多核操作系统调度两方面介绍基于源码分析的研究方法，借助现有的文献资料，学生不仅加深了对操作系统抽象概念的理解，也可以优化和修改内核。该方法目标准确，避免了盲目性。实践经验表明，经过几个月的高强度训练，学生的能力提升明显。

关键词：操作系统；调度；多核；人才培养；源码分析

“操作系统”是计算机系统的核心，是计算机系统结构领域最重要的基础课程。世界著名大学都把操作系统的教学和研究摆在极其重要的位置，通常由资深教授担纲主讲，如美国UCSD大学主讲“Principles of Computer Operating Systems”的Yuanyuan Zhou教授就是系统结构领域世界著名的学者。国家重大科技专项“核心电子器件、高端通用芯片及基础软件产品”也对国产操作系统研发和应用提出了更高的要求，且急需大量高端人才。

然而，操作系统的学习和研究相对其他课程而言略显困难，原因在于概念比较抽象不容易理解、实践内容较为复杂不容易自学，内核不容易调试，缺少友好的人机界面，显得枯燥。因此，愿意从事操作系统研究的人很少。有些同学对Linux内核表现出兴趣，但缺少教师指导，深陷在无穷无尽的代码阅读中，始终找不到成就感或遇到困难没有人交流指导而不得不放弃。

笔者主讲“嵌入式操作系统”，除教学与科研外，每年指导几名本科生课外科研活动，如“校级学生科学研究项目”、“全国大学生创新性实验计划”等，课外实践是学生能力有效提升的最佳手段[1]。在选题时，“实用性、原创性、前瞻性、挑战性、延续性” 是考虑的重点，即研究的内容要有意义，必须对教学或科研有直接或间接的促进作用，如果通过大量的中英文文献检索确定研究的问题还没有满意的解决方案，那么，我们就需要寻找和设计新的方法，坚持高起点，不做纯粹的工程。另外，每年研究的问题要相对聚焦，在某一个方面做得尽可能深入，而不是浅尝辄止。

多核已成为处理器的主流，然而，操作系统教学中对操作系统如何支持多核的介绍却显得不足，如多核的启动流程、多核操作系统调度，等等[2]。本文将从这两个方面阐述如何引导学生开展这方面的研究，从而加深对操作系统的理解。

1 多核操作系统启动流程分析

由于多核与多处理器(SMP)十分相似，使得现有的多处理器操作系统基本不用修改就可以用在多核上。然而，很多讲解Linux内核的书都提到了Linux的启动流程，但很少详细阐述多核环境下的启动流程，网上的文献资料也都比较简单。

了解Linux的启动流程对深入了解操作系统的启动过程以及优化操作系统的快速启动很有帮助，于是，我们组织学生从阅读源码入手，借助相关文献，熟悉启动流程，陈莉君老师也十分认同此种做法[3]。

Linux中SMP启动主要流程如下。

1) BIOS初始化(屏蔽AP-Application Processor，建立系统配置表格)。

2) MBR里面的引导程序(Grub，Lilo等)将内核加载到内存。

3) 执行head.S中的startup_32函数(最后将调用start_kernel)。

4) 执行start_kernel()，这个函数相当于应用程序里面的main。

5) start_kernel()进行一系列初始化，最后将执行smp_init() 启动各个AP。

6) rest_init()，调用init()创建1号进程，自身执行 cpu_idle()成为0号进程。

7) 1号进程即init进程完成余下的工作。

由于BIOS代码并不是支持多线程的，所以在SMP中，系统必须让所有AP进入中断屏蔽状态，不与BP一起执行BIOS代码。BIOS要同时完成对APIC以及其他与MP相关的系统组件初始化过程，并建立相应的系统配置表格，以便操作系统使用。到了启动的第2步，BIOS开始调入执行启动引导区程序，录入Linux操作系统的启动部分。因此我们可以看到，在系统加电启动过程中，实际上只有一个CPU(BP-bootstrap processor)负责启动工作，而其他的CPU则处于中断屏蔽状态，等待着操作系统的激活。

在初始化阶段，BP先完成自身的初始化，进入保护模式并开启分页式存储管理机制，在完成系统特别是内存的初始化，然后从start_kernel调用smp_init进行SMP结构的初始化，代码在init/main.c中。这个函数的主体是smp_boot_cpus，它依次启动系统中各个AP，让他们各自走过初始化的第一个阶段。内核中有个全局变量MAX_CPUS，表示系统识别的最大的CPU数量，可以在内核配置菜单中设置。各个AP在完成了自身的初始化以后都要停下来等待一个统一的“起跑”命令。而BP则在完成所有AP的启动以后通过smp_commence发出这个命令。初始化的方式是通过APIC发送IPI。当BP初始化完毕所有的AP之后，就继续执行start_kernel中的其余部分代码。

BP将AP在一开始被唤醒后需要执行的代码(trampoline.S)的首地址写入热启动向量(warm reset vector)，即从40:67开始的两个字。这样，当BP对AP发送IPI时，AP响应中断，自动跳入这个trampoline.S代码部分继续执行。为了AP有足够的时间响应中断，BP在发送中断请求后要延迟一段时间，在这以后，事实上AP已经在工作了。AP响应中断直接跳转至trampoline.S的入口处，trampoline.S在载入符号表(GDT)和局部符号表(LDT)之后进入保护模式并跳至head.S的入口处。AP转入head.S继续执行，但是执行的代码与BP所执行的并不完全一致。由于ready的值被改变，不再等于1，所以就继续向前执行，调用initialize_secondary函数，而不是像BP一样调用start_kernel函数。initialize_secondary是一段内嵌汇编程序，将程序跳转至current->thread.esp，即前面的idle->thread.esp)处。CPU执行start_secondary函数，进入空闲状态，等待以后的系统调度。

至此，一个AP的初始化过程就完成了。所有的AP启动后，系统中所有的CPU就不再有主次之分，即它们是完全平等的。

2 多核操作系统调度

调度是操作系统的基本功能，单核上的调度器只需要解决何时(when)运行哪一个任务的问题，主要实现轮转方式或高优先级优先的方式进行任务的切换。

多核环境下的调度器不仅要完成任务的切换，还要解决任务在哪个核上(where)运行的问题，这使得问题一下子复杂了很多，虽然有大量的文献资料介绍各种版本的调度原理，但都不完备。为了让学生深入了解任务调度的全过程，我们安排学生阅读了从任务创建、分配、调度运行以及负载均衡相关的所有核心代码，并做了详细的注解。源码是信息的第一手资料，最真实可信。尽管有一些文献可参阅，但阅读的过程仍不轻松，但理解和印象却十分深刻。通过源码分析，学生了解到，当任务创建时，存在任务到核之间的首次分配问题，如果分配不合理，还有机会通过负载均衡得到修正，但并不能保证一定会被迁移。在此过程中，学生了解了调度域的概念，也了解了核的负载计算办法、任务迁移规则、时间片的计算以及如何保证调度的公平。

考虑到高版本的Linux内核过于复杂，也不容易编译通过，我们选取了比较常用的2.6.18版本。在深入了解了调度器的工作原理后，我们又组织学生开展了异构多核调度器的研究工作，这是一个探索性课题。

异构多核处理器是近年逐渐被企业认可的一种新型体系结构，即片上多个核不完全一致，表现为功能异构或性能异构。所谓功能异构是指每个核的处理单元存在差异，往往表现为指令集异构；性能异构是指每个核的性能存在差异，指令集完全相同。研究发现，不同的程序之间甚至同一个程序运行时的不同阶段常常表现出不同的行为特性，对于这种程序行为的多样性，理论与实验都已证明，使用异构多核处理器比使用同构多核处理器往往具有更好的性能功耗比，程序行为的差异越大，性能功耗比越明显。异构多核处理器的设计并不复杂，但所有的处理器厂商都没有推出商用的异构多核处理器，根本原因就在于目前的所有操作系统，包括Windows和Linux都不支持异构多核。操作系统设计者在设计之初就没有想到异构，比如Linux，在启动时查询BP的特征，然后直接将其它核AP的特征视为与BP一样，CPU的频率也只定义了一个变量cpu_khz，并没有定义成数组。异构感知是有效调度的基础，因此必须对内核代码加以修改。同样，只有将线程合理的映射到最适合的核上，功效才会最佳，但实现这种合理的映射除了知道核的快慢外，还要清楚线程的属性，传统的调度器丝毫没有考虑到程序行为的差异，而如何将程序行为分析与操作系统调度有机结合是必须解决的关键问题，信息是否准确、运行时开销、对程序员是否透明是考虑的重点。最后就是调度策略问题，尤其是负载均衡调度策略，由于频率的差异，core的负载需要重新折算，在迁移时，还要考虑目标core的属性与待迁移线程是否满足资源按需分配的原则。

在阅读了大量英文资料后，学生进行了初步设计，开始了代码修改和调试工作，这一过程十分艰辛，但收获很大，从项目之初畏惧代码、看不懂代码到项目结束时充满自信、可以轻松修改调试代码。

实际上，围绕多核和调度还有很多的工作可以去做，比如，功耗感知的多核调度器，虽然这是一个经典问题，但远未成熟；如何编写适应多核调度的多线程程序，程序的性能不仅取决于调度，还取决于程序编写的质量。

3 结语

以上的尝试都是依托学生课外实践活动完成的，参与的学生是来自计算机学科各个专业的Linux内核爱好者，每年这样的学生只有几名，但足以组成一个团队，对于学生能力普遍较强的高校，可以采取研究型教学[4]。兴趣是学习的最大动力，没有兴趣，面对枯燥的代码、艰难的调试是很难坚持的，这也是因材施教的体现方式[5]。

参考文献:

[1] 罗宇,邹鹏,吴庆波,等.“操作系统”国家精品课程建设总结[J]. 计算机教育,2009(14):39-41.

[2] 臧斌宇,朱东来. 借鉴国际先进经验,加强计算机系统方向基础教学[J]. 计算机教育,2009(16):147-149.

[3] 陈莉君,梁琛,王小银. 基于“Linux内核分析”的教学内容研究与实践[J]. 计算机教育,2009(14):81-82.

[4] 郭玲玲,袁满,富宇,等. 基于案例驱动的研究性教学[J]. 计算机教育,2011(5):75-78.

[5] 陈渝,向勇.“操作系统”课程实验教学探讨[J]. 计算机教育,2009(14):135-136.

Multi-core Operating System Research and Professional Training Practice Based on Source Code Analysis

XU Yuanchao，SUN Weizhen，LIU Yu，ZHANG Congxia

(College of Information Engineering, Capital Normal University，Beijing 100048，China)

Abstract: Multi-core has already become the main trend of processor. It is necessary to introduce the content about multi-core into traditional operating system teaching. This paper introduces an approach based on source code analysis and presents two cases: multi-core booting and multi-core scheduling. Student will have a deep understanding to abstract concept of operating system, and also can optimize and modify kernel. Practice shows that student ability has improved obviously after several months’ high-intensive training.

Key words: operating system; scheduling; multi-core; professional training; source code analysis