第一章引言
“数据结构”是一门自立的课程在国外是从1968年才开始设立的。1968年美国唐·欧·克努特教授开创了数据结构的最初体系，他编著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构、存储结构及其操作的著作。“数据结构”在计算机科学中是一门综合性的专业基础课，它是介十数学、计算机硬件和计算机软件二者之间的一门核心课程。数据结构课程的内容不但是一般程序设计(尤其是非数值性程序设计)的基础，同时也是设计和实现编译程序、操作系统、数据库系统及其他系统程序的重要基础。
数据结构是计算机存储、组织数据的方式。通常情况下，精心选择的数据结构能够实现更高的运行效率或存储效率的算法。数据结构往往与高效的检索算法和索引技术有关。数据结构在计算机科学中是一门综合性的专业基础课，研究非数值计算程序设计问题中计算机的操作对象以及它们之间的关系和操作等问题。它和计算机的硬件，尤其是计算机软件的研究有着密切的关系，是介十数学、计算机硬件和软件二者之间的一门核心课程，无论是汇编程序还是操作系统，都涉及到研究数据兀素在存储器中的分配问题。
数据结构不仅涉及到图论，表，树的理论，目前还扩充到网络、集合代数论、格、关系等方面。它对操作系统的发展有着推波助澜的作用，是操作系统的重要基础。而操作系统是配置在计算机硬件上的第一层软件，是一组程序的集合，其他所有的软件如汇编程序等等，都将依赖操作系统的支持，获取它的服务。同时，操作系统也离不开相关软件的支持，它的数据如何分配，软件所采取的数据结构、算法，都将大大影响到本系统的性能。既然许多学科都涉及到数据兀素在存储器中的分配问题，因此不能把数据结构和操作系统视为两个独立无关的学科，而是应该把它们结合起来研究，融会贯通。
计算机解决一个实际问题时，大致需要经过下列几个步骤:首先要从具体问题中抽象出一个适当的、正确的数学模型，然后设计一个解决此数学模型的算法(Algorithm)，最后编出程序、进行测试、调试直至得到最终解答。建立数学模型的实质是分析具体问题，从中提取要操作的对象，并找出这些操作对象之间包含的关系，然后运用数学的语言进行描述。计算机算法与数据的结构关系非常密切，算法必须依附十具体的数据结构，数据结构直接关系到算法的选择和运行效率。既然运算是由计算机来完成，这就要设计与之相对应的插入、删除和修改等算法。即数据结构还需要给出每一种结构类型所定义的各种运算的算法。
本论文是基十操作系统的角度，着眼十数据结构，分析研究其在大型软件系统中的重要地位，对系统中各类资源的表示与组织，不仅要能够最大限度的利用系统资源，同时还要使资源得到公平合理的利用。在许多类型的程序设计中，数据结构的选择是一个最基本的设计考虑因素。很多大型系统的构造经验表明，系统实现的困难程度和系统构造的质量很大程度上都依赖十是否选用了最优化的数据结构。在解决实际问题的过程中，一旦确定了数据结构，算法就容易设计了。不过有些情况也会颠倒过来，需要根据特定算法来选择最相适应的数据结构。无论属十哪一类情况，选择正确合适的数据结构都是非常重要的，因为数据结构直接影响着算法的设计与执行效率。
本论文选择Linux作为研究对象。Linux是一种能够在多种平台上运行、源代码公开、免费、功能强大、遵守POSiX标准、并目_与UNiX兼容的操作系统。
Linux最初版本是由Linus Benedict Torvalds编写的，为了能够使Linux更加完善，Torvalds在网络上公开了Linux的源代码，邀请全世界的志愿者来参与Linux的完善与开发。在全世界爱好者的共同帮助下，Linux得到不断的完善，并在短时期内迅速崛起。现在，Linux内核还在以相当快的速度不断地发展着。事实证明，linux是一个很有发展前途的操作系统，也是为数不多可以与Microsoft旗下操作系统相竞争的操作系统。
我国的it产业起步较晚，技术落后十西方经济发达国家。在我国，由十受知识产权的限制，无论是PC平台上使用的Windows桌面系统，还是使用应用十大中型机的UNiX，都无法窥视到其内部结构。目前信息化社会的大环境，迫切需要有我们自己研发的安全操作系统。计算机体系中的安全包括:操作系统安全、数据库安全、网络安全和应用软件安全。操作系统是所有上层应用的接口、平台，因此如果没有安全的操作系统作为基础，那么所有的上层应用安全问题都不能得到真正的解决。既然要设计自己的安全操作系统，对现有操作系统内核的透彻研究是必不可少的i作。Linux的开放源码为这一项i作提供了条件。
本论文将以操作系统的基本原理作为指导思想，以分析内核主要数据结构为核心，以理清数据结构间的关系为线索，以分析实现机制为前期基础i作的目的。深透理解Linux作为多用户任务操作系统的本质及其i作原理，思考优化改进的途径，以提高现有操作系统的效率。
第一章 引言......... 8-10
第二章 linux 内核整体.........10-13
2.1 Linux 内核的五......... 10-12
2.2 小结......... 12-13
第三章 LINUX 中的数据结构......... 13-20
3.1 链表......... 13-17
3.2 树......... 17-19
3.2.1 二叉排序树 .........18-19
3.2.2 红黑树......... 19
3.3 小结......... 19-20
第四章 Linux 的进程结构......... 20-43
4.1 相关概念简述......... 20-34
4.1.1 Linux 进程......... 20
4.1.2 task_struct......... 20-34
4.2 进程组织中数据......... 34-42
4.2.1 等待队列......... 34-39
4.2.2 等待事件......... 39-42
4.3 小结......... 42-43
结束语
我用了二个月的时间详细的阅读并注释Linux内核源代码，尤其对其中进程调度和进程控制部分的源代码作了较深入的分析。近年来，Linux以其优秀的稳定性、灵活的架构、丰富的设备驱动、开放的源码以及良好的伸展性等特点，在桌面系统、低端服务器、高端服务器以及嵌入式系统等各方面都表现出越来越强的竞争力，对十一个仍然处十“集市式“开放开发模式的操作系统来说，能做到这一点简直就是一个奇迹。这也是我之所以选择linux作为研究对象的原因。
但从调度系统的实现上，通过分析，我认为Linux的长项仍然在桌面系统上，它仍然保持着早年开发时“利己主义“的特点，即自由软件开发者的开发动力，很大程度上来自十改变现有系统对自己“不好用“的现状，很大程度是为了为自己的某一些需求服务。尽管出十种种动机和动力，Linux表现出与Windows等商用操作系统竞争的强势，但从开发者角度来看，这种愿望与自由软件的开发特点是有矛屑的。对十Linux的市场来说，最紧迫、最活跃的需要在十嵌入式系统。但至少从调度系统来看，Linux2. 6并没有在这方面下很大功夫，研究证明它并不能满足某些嵌入式系统的特殊要求，比如嵌入式系统在实时反馈及控制的要求。从市场的角度来看，由十Linux在真正商品的研发过程中具有比较大的难度，从而使得linux的应用在市场中占的比例还相对较少。