Linux+26内核O1调度算法剖析-USB迷|专注于互联网分享

2024年1月24日发(作者：邱听云)

２００９年６月第３０卷第６期韶关学院学报·自然科学ＪｏｕｍａｌｏｆＳｈａｏｇｕａｎＵｎｉｖｅｒｓｉｔｙ·ＮａｔｕｒａｌＳｃｉｅｎｃｅＪｕｎ．２００９Ｖ０１．３０Ｎｏ．６Ｌｉｎｕｘ２．６内核０（１）调度算法剖析张永选。姚远耀（江西经济管理干部学院电子计算机应用系，江西南昌３３００８８）摘要：分析了Ｌｉｎｕｘ２．４内核调度机制存在的缺陷和Ｌｉｎｕｘ２．６内核进程调度机制的特点．对于Ｌｉｎｕｘ２．６内核，探讨了调度时机、调度策略以及Ｌｉｎｕｘ２．６内核新引入的内核抢占机制，重点讨论了调度有关的重要数据结构、ｏｏ）胡ｌ度算法及其实现的细节．关键词：Ｌｉｎｕｘ；内核；ｏ（Ｉ）；进程调度；内核抢占中图分类号：ＴＰ３１６．８１文献标识码：Ａ文章编号：１００７—５３４８（２００９）０６—０００５—０５进程调度机制是操作系统的灵魂，其主体——进程调度程序是操作系统最为核心的部分之一，也是多任务操作系统中执行频度最高的部分之一，其性能对操作系统整体性能有着十分重要的影响…．本文分析了Ｌｉｎｕｘ与进程调度有关的重要数据结构，探讨了调度时机、调度策略，重点剖析了Ｏ（１）算法的实现细节．１Ｌｉｎｕｘ２．４内核进程调度算法的缺陷根据对Ｌｉｎｕｘ２．４内核进程调度源代码的分析，Ｌｉｎｕｘ２．４内核的优点是内核调度简单有效、内核不可抢占等．但也可明显看到它的缺点：（１）调度算法复杂度是Ｏ（ｎ），与系统负荷关系较大；（２）系统只设置一个就绪队列ｒｕｎｑｕｅｕｅ．在ＳＭＰ系统中。调度器对它的所有操作都会因全局自旋锁而导致系统各个处理机之间的等待，使得就绪队列成为一个明显的瓶颈；（３）调度算法在内核态不可抢占．缺乏对实时进程良好的支持．２２．１Ｌｉｎｕｘ２．６内核进程调度算法剖析Ｌｉｎｕｘ２．６内核调度算法特点自／Ｊｎｕ艾２．５内核起，Ｌｉｎｕｘ采用了一种全新的Ｏ（１）调度算法．新的调度程序实现了如下目标：（１）完全实现Ｏ（１）算法．不管有多少进程，调度程序选择进程时所需的时间是恒定的；（２）增强了ＳＭＰ的可扩展性．每个处理器拥有独立的运行队列和自旋锁，不会产生互斥；（３）引入了内核抢占．提高了交互性能，增强了对软实时性的支持，保证了系统及时相应．２．２调度时机进程的调度时机与引起进程调度的原因和进程调度的方式有关．在Ｌｉｎｕｘ２．６中，除核心应用主动调用调度器之外，内核还在以下三种时机启动调度器工作：（１）从中断或系统调用返回到用户态；（２）某个进程允许被抢占ＣＰＵ；（３）进程主动进入休眠状态．２．３调度策略Ｌｉｎｕｘ２．６内核中进程的调度策略有以下几种：（１）ＳＣＨＥＤ＿ＦＩＦＯ先进先出式调度，除非有更高优先级进程申请运行，否则当前进程将保持运行至退出才让出ＣＰＵ；（２）ＳＣＨＥＤ—ＲＲＲｏｕｎｄＲｏｂｉｎ方式调度，当前进程被调度下来后将被置于运行队列的末尾；（３）ＳＣＨＥＤ—ＮＯＲＭＡＬ常规的分时调度策略．收稿日期：２００９－０１—２８作者简介：张永选（１９８１一）。男，山东金川人，江西经济管理干部学院电子计算机应用系教师，主要从事计算机操作系统、计算机网络方面的研究．万方数据

．６．韶关学院学报－自然科学２００９年ＳＣＨＥＤ＿ＮＯＲＭＡＬ是普通进程的调度策略；ＳＣＨＥＤ—ＦＩＦＯ和ＳＣＨＥＤ～ＲＲ都是实时进程调度策略．Ｏ（１）调度器以进程的动态优先级ｐｒｉｏ为调度依据，它总是选择目前就绪队列中优先级最高的进程作为候选进程ｎｅｘｔ．由于实时进程的优先级总是比普通进程高，故能保证实时进程总是比普通进程先被调度．Ｌｉｎｕｘ２．６内核中．优先级ｐｒｉｏ的计算不再集中在调度器选择ｎｅｘｔ进程时，分散在进程状态改变的任何时候．且优先级重新计算后，就会根据计算结果调整进程在就绪队列中的位置．２．４调度有关的数据结构２．４．１进程优先级的划分ｂｎｕｘ内核将进程优先级作以下规定：优先级范围是从０－ＭＡＸ＿ＰＲＩＯ一１，其中实时进程的优先级的范围是Ｏ■？ＭＡＸ—ＲＴ＿ＰＲＩＯ一１，普通进程的优先级是ＭＡＸ—ＲＬＰＲＩＯ－ＭＡＸ＿ＰＲＩＯ一１．数值越小优先级越高．２．４．２就绪队列ｓｔｒｕｃｔｓｔｒｕｃｔｒｕｎｑｕｅｕｅｒｕｎｑｕｅｕｅ是２．６内核调度器中一个非常重要的数据结构，它主要用于存放每个ＣＰＵ的就绪队列信息．限于篇幅．这里只介绍其中比较重要的部分：（１）ｐｒｉｏ＿ａｒｒａｙ＿ｔ’‘‘ａｃｔｉｖｅ，幸ｅｘｐｉｒｅｄ，ａｒｒａｙｓ这是ｒｕｎｑｕｅｕｅ中最重要的部分．每个ＣＰＵ的就绪队列都是一个数组，按照时间片是否用完将就绪队列分为两个部分，分别用指针ａｃｔｉｖｅ和ｅｘｐｉｒｅｄ来指向数组的两个下标［２］．ｐｒｉｏ＿ａｒｒａｙ＿ｔ的结构如下：ｓｔｒｕｃｔｐｒｉｏ＿ａｒｒａｙ｛产本进程数组中进程个数奉，ｑｕｅｕｅ［ＭＡＸ＿ＰＲＩＯ］；／半每个优先级的进程队列术／产上述进程队列的索引位图书／ｉｎｔｎｒ＿ａｃｔｉｖｅ；ｓｔｒｕｃｔｌｉｓｔ＿ｈｅａｄｕｎｓｉｇｎｅｄｌｏｎｇｂｉｔｍａｐ［ＢＩＴＭＡＰ＿ＳＩＺＥ］；）．数组ｑｕｅｕｅ［ｉ］里面存放的是优先级为ｉ（ＭＡＸＰＲＩＯ＞ｉ＞＝０）的进程队列的链表头．在结构体ｓｔｒｕｃｔｐｒｉｏ＿ａｒｒａｙ中有一个重要的数据ｕｎｓｉｇｎｅｄｌｏｎｇｂｉｔｍａｐ［ＢＩＴＭＡＰ＿ＳＩＺＥ］．这个数据是用来作为进程队列ｑｕｅｕｅ［ＭＡＸ＿ＰＲＩＯ］的索引位图．ｂｉｔｍａｐ的每一位都与ｑｕｅｕｅ［ｉ］对应．当ｑｕｅｕｅ［ｉ］的进程队列不为空时．ｂｉｔｍａｐ的相应位就为１；否则就为Ｏ．这样只需要通过汇编指令从进程优先级由高到低的方向找到第一个为１的位置ｉｄｘ，则ｉｄｘ即为当前就绪队列中最高的优先级（函数ｓｃｈｅｄ＿ｆｉｎｄ＿ｆｉｒｓｔ＿ｂｉｔ０就是用来实现该目的的）．那么ｑｕｅｕｅ［ｉｄｘ］一＞ｎｅｘｔ就是要找的候选进程．当一个时普通进程的时间片用完以后将重新计算进程的时间片和优先级。并将该进程从活动数组移到过期数组中相应优先级的进程队列中．当活动数组中没有进程时，则将ａｃｔｉｖｅ和ｅｘｐｉｒｅｄ指针调换一下就完成了切换工作．通过以上方法来实现时间片轮转，大大提高了效率．这也是Ｌｉｎｕｘ２．６调度器一个特点．（２）ｓｐｉｎｌｏｃｋ＿ｔ？ｌｏｃｋ就绪队列ｒｕｎｑｕｅｕｅ的自旋锁．当对ｒｕｎｑｕｅｕｅ进行操作的时候，需要对其加锁．２．４．３进程标识ｔａｓｋ＿ｓｔｒｕｃｔＬｉｎｕ）【内核使用ｔａｓｋ—ｓｔｒｕｃｔ结构来表示进程．Ｌｉｎｕｘ２．６内核的ｔａｓｋ—ｓｔｒｕｃｔ有上百个域，包括有关进程的所有信息．由于ｔａｓｋ—ｓｔｒｕｃｔ结构体比较复杂，本文只涉及它与进程调度相关的重要部分．该结构定义在／ｉｎ．ｃｌｕｄｅ／ｌｉｎｕｘ／ｓｃｈｅｄ．ｈ中．（１）ｉｎｔｐｒｉｏ，ｓｔａｔｉｃ＿ｐｒｉｏ进程的动态优先级和静态优先级．ｐｒｉｏ表示进程的动态优先级，ｓｔａｔｉｃ—ｐｒｉｏ表示进程的静态优先级．一个进程的初始时间片的大小完全取决于它的静态优先级，调度则依赖于其动态优先级．万方数据

（２）ｕｎｓｉｇｎｅｄｌｏｎｇｓｌｅｅｐ＿ａｖｇ进程的平均等待时间．ｓｌｅｅｐ＿ａｖｇ反映了该进程需要运行的紧迫性．进程休眠时该值增加．进程运行时该值减少．它是影响进程优先级最重要的元素，值越大，说明该进程越需要被调度．２．５０（Ｉ）调度算法分析２．５．１Ｏ（１）调度算法的实现ｓｃｈｅｄｕｌｅＯ是实现进程调度的主要函数，并负责完成进程切换工作．其用于确定最高优先级进程的代码非常快捷高效，它在／ｋｅｍｅｌ／ｓｃｈｅｄ．ｃ中的定义如下：ｔａｓｋ＿ｔ水ｐｒｅｖ．宰ｎｅｘｔ；ｒｕｎｑｕｅｕｅ＿ｔ芈ｒｑ；ｐｒｉｏ＿ａｒｒａｙ＿ｔ卑ａｒｒａｙ；ｉｎｔｉｄｘ；ｐｒｅｅｍｐｔ＿ｄｉｓａｂｌｅＯ；ｐｒｅｙ＝ｃｕｒｒｅｎｔ；－Ｌｉｎｕｘ２．６内核支持抢占。所以在对队列操作时需要设置为不可抢占．ｒｑ２ｔｈｉｓ＿ｒｑＯ；ａｒｒａｙ２ｒｑ一＞ａｃｔｉｖｅ；ｉｆ（ｕｎｌｉｋｅｌｙ（！ａｒｒａｙ一＞ｎｒ＿ａｃｔｉｖｅ））｛ｒｑ一＞ａｃｔｉｖｅ＝ｒｑ－＞ｅｘｐｉｒｅｄ；ｒｑ一＞ｅｘｐｉｒｅｄ＝ａｒｒａｙ；ａｒｒａｙ２ｒｑ一＞ａｃｔｉｖｅ；Ｊ．这段代码的作用是执行两个数组（活动数组ｒｑ一＞ａｃｔｉｖｅ和过期数组ｒｑ一＞ｅｘｐｉｒｅｄ）的切换．判断活动数组中如果没有进程了，则通过指针操作来切换两个数组．之前在过期数组中的进程时间片已经被计算好了．所以在两个数组切换后，过期数组中的进程都变为活动进程，交换数组的时间就是交换指针的时问．这种交换就是Ｏ（１）ＮＪ度算法的核心．Ｏ（１）调度算法不需要从头到尾一个一个地对进程进行时间片的计算，而是通过很简单的数组切换实现进程的切换，解决了之前算法中效率低下的弊端．该过程可用图１表示．图１０（１）算法的工作机制有了活动数组，并且各个进程都按优先级排好队等待被调度，继而就要选择候选进程了：ｉｄｘ＝ｓｃｈｅｄ—ｆｉｎｄｆｉｒｓｔ＿ｂｉｔ（ａｒｒａｙ－＞ｂｉｔｍａｐ）；ｑｕｅｕｅ＝ａｒｒａｙ一＞ｑｕｅｕｅ＋ｉｄｘ；ｎｅｘｔ＝ｌｉｓｔ＿ｅｎｔｒｙ（ｑｕｅｕｅ－＞ｎｅｘｔ，ｔａｓｋ＿ｔ，ｒｕｎ＿ｌｉｓｔ）；万方数据

．８．韶关学院学报·自然科学２００９年ｉｆ（ｕｎｌｉｋｅｌｙ（ｎｅｘｔ一＞ｐｆｉｏ！＝ｎｅｗ＿ｐｒｉｏ））｛ｄｅｑｕｅｕｅ＿ｔａｓｋ（ｎｅｘｔ，ａｒｒａｙ）；ｎｅｘｔ一＞ｐｆｉｏ＝ｎｅｗ＿ｐｆｉｏ；ｅｎｑｕｅｕｅｔａｓｋ（ｎｅｘｔ，ａｒｒａｙ）；）ｅｌｓｅｒｅｑｕｅｕｅ＿ｔａｓｋ（ｎｅｘｔ，ａｒｒａｙ）；．首先，要在活动数组中的索引位图里找到第一个被设置的优先级位，这里通过ｓｃｈｅｄ＿ｆｉｎｄ＿ｆｉｒｓｔ＿ｂｉｔ函数来实现．如前所述．该函数通过汇编指令从进程优先级由高到低的方向找到第一个为１的位置ｉｄｘ．因为优先级的个数是个定值，所以查找时间恒定，并不受系统到底有多少可执行进程的影响．这是Ｌｉｎｕｘ２．６内核实现Ｏ（１）调度算法的关键之一【２１．此外，Ｌｉｎｕｘ对它支持的每一种体系结构都提供了对应的快速查找算法，以保证对位图的快速查找［３］．很多体系结构提供了ｆｉｎｄ—ｆｉｒｓｔ—ｓｅｔ指令，这条指令对指定的字操作（在Ｉｎｔｅｌｘ８６体系结构上，这条指令叫做ｂｓｆｌ．在ＩＢＭＰＰＣ上。ｃｎｔｌｚｗ用于此目的）．在这些系统上，找到第一个要设置的位所花的时间至多是执行这条指令的两倍，这也在很大程度上提高了调度算法的效率．ｓｃｈｅｄ＿ｆｉｎｄ＿ｆｉｒｓｔ＿ｂｉｔ函数找到第一个被设置的优先级位后，再找到该优先级对应的可运行进程队列，接着找到该队列中的第一个进程，最后把找到的进程插入运行队列中．整个过程如下图２所示．图２０【１）调度算法找到候选进程的过程图２中的网格为１４０位索引位图，ｑｕｅｕｅ［７］为优先级为７的就绪进程链表．ｉｆ（１ｉｋｅｌｙ（１：Ｉｒｅｖ！＝ｎｅｘｔ））ｆｐｒｅｙ＝ｃｏｎｔｅｘｔ＿ｓｗｉｔｃｈ（ｒｑ，ｐｒｅｙ，ｎｅｘｔ）；）ｅｌｓｅｓｐｉｎ＿ｕｎｌｏｃｋｊｒｑ（＆ｒｑ－＞ｌｏｃｋ）；．如果候选进程不是当前运行进程，则需要进行进程切换．反之，仅仅释放之前对运行队列所加的锁．２．５．２时间片的计算方法与时机Ｌｉｎｕｘ２．４内核在所有就绪进程的时间片都耗完后再在调度器中～次性重算．重算是用ｆｏｒ循环实现的，相当耗时．新的Ｕｎｕｘ调度程序减少了对循环的依赖。取而代之的是为每个处理器维护两个优先级数组：活动数组和过期数组．活动数组内的队列上的进程都还有时间片剩余；而过期数组内的队列上的进程都耗尽万方数据

了时间片．当一个进程的时间片耗尽时．它会被移至过期数组．但在此之前，时间片已经重算好了，接下来只要在活动和过期数组之间切换即可．因为数组是通过指针访问的，所以交换它们的时间就是交换指针的时间．这种交换就是Ｏ（１）调度算法的核心．２．６内核抢占Ｌｉｎｕｘ２．４版之前的Ｌｉｎｕｘ和大部分Ｕｎｉｘ＿Ｕｋｅ系统一样，只支持用户抢占１３］．为了提高对交互式进程的支持，Ｌｉｎｕｘ２．６内核引入了内核抢占．只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务．只要进程没有持锁。内核就可以进行抢占．为支持内核抢占，Ｌｉｎｕｘ２．６内核对每个进程的ｔｈｒｅａｄ＿ｉｎｆｏ结构体（进程描述符ｔａｓｋ＿ｓｔｒｕｃｔ的成员变量，用来保存内核需要经常访问的重要信息）引入了成员变量ｐｒｅ—ｅｍｐｔ＿ｃｏｕｎｔ计数器．该计数器初始值为０，每当使用锁的时候数值加ｌ，释放锁的时候减１．当数值为Ｏ时，内核就是安全的，就可以执行抢占［引．３结束语Ｈｎｕｘ操作系统经过近２０年的发展．已经成为当今最成功的操作系统之一．Ｌｉｎｕｘ２．６版本的内核实现了一个高效的Ｏ（１）级调度算法，相对于Ｌｉｎｕｘ２．４版内核具有更好的实时性能、重负载下更高的ＣＰＵ使用率、以及交互作业更快的响应时间等优良特性．但Ｌｉｎｕｘ２．６版内核的实时性能仍然不能满足实时环境的要求；可抢占内核也只限于对ＣＰＵ的抢占。还不支持对内存等其他资源的抢占吲．所有这些都将是今后Ｌｉｎｕｘ发展过程中值得深入研究的课题．参考文献：［１］河秦，王洪涛．“ｎ吸２．６内核标准教程［Ｍ］．北京：人民邮电出版社，２００８．［２］ＬｉｎｕｓＴ．Ｌｉｎｕｘ－２．４．１，Ｌｉｎｕｘ一２．６．１５［ＥＢ／ＯＬ］．ｈｔｔｐ：／／ｗｗｗ．ｋｅｒｎｅｌ．ｏｒｇ，．［３］ＲｏｂｅｒｔＬＬｉｎｕｘＫｅｒｎｅｌＤｅｖｅｌｏｐｍｅｎｔ［Ｍ］．２ｎｄｅｄ．ＵＳ：ＮｏｖｅｌＰｒｅｓｓ，２００５．［４］陈莉君，张琼声，张宏伟．深入理解ＬＩＮＵＸ内核［Ｍ］．３版．北京：中国电力出版社，２００７．［５］何克右，周彩贞．Ｌｉｎｕｘ２．６进程调度机制的剖析ＣＪ］．华中师范大学学报：自然科学版，２００７（４）：１７６—１８３．ＴｈｅａｎａｌｙｓｉｓｏｆｔｈｅｐｒｏｃｅｓｓｓｃｈｅｄｕｌｉｎｇｍｅｃｈａｎｉｓｍｉｎＬｉｎｕｘｋｅｒｎｅｌ２．６ＺＨＡＮＧＹｏｎｇ—ｘｕａｎ，ＹＡ０Ｙｕａｎ—ｙａｏ（ＤｅｐａｒｔｍｅｎｔｏｆＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎ，ＪｉａｎｇｘｉＩｎｓｔｉｔｕｔｅｏｆＥｃｏｎｏｍｉｃＡｄｍｉｎｉｓｔｒａｔｏｒｓ，Ｎａｎｃｈａｎｇ３３００８８，Ｊｉａｎｇｘｉ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＳｅｖｅｒａｌｗｅａｋｎｅｓｓｅｓｏｆｔｈｅｐｒｏｃｅｓｓｓｃｈｅｄｕｌｉｎｇｏｆＬｉｎｕｘ２．４ｋｅｒｎｅｌａｎｄｓｏｍｅｓｔｒｏｎｇｐｏｉｎｔｓｏｆｔｈｅＬｉｎｕｘ２．６Ｋｅｒｎｅｌ’ＳＭｅｃｈａｎｉｓｍｏｆｐｒｏｃｅｓｓｓｃｈｅｄｕｌｉｎｇｇｉｅｓｉｎｓｃｈｅｄｕｌｉｎｇｔｉｍｅ，ｓｃｈｅｄｕｌｉｎｇｉｓｐｌａｃｅｄｏｎａｒｅｉｎｔｒｏｄｕｃｅｄ．ＦｏｒＬｉｎｕｘｋｅｒｎｅｌ２．６，ｔｈｉｓｐａｐｅｒａｎａｌｙｚｅｓｓｔｒａｔｅ－ｐｏｌｉｃｙ，ａｎｄｋｅｒｎｅｌｐｒｅｅｍｐｔｉｏｎｆｉｒｓｔｉｎｔｒｏｄｕｃｅｄｂｙｋｅｒｎｅｌ２．６．Ｔｈｅｎ，ｔｈｅｆｏｃｕｓａｎａｌｙｚｉｎｇａｎｄｄｉｓｃｕｓｓｉｎｇｃｏｒｒｅｓｐｏｎｄｉｎｇｄａｔａｓｔｒｕｃｔｕｒｅｓ，０（１）ｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍ，ａｎｄｉｔ’Ｓｉｍｐｌｅ－ｍｅｎｔａｔｉｏｎｄｅｔａｉｌｓ．Ｋｅｙｗｏｒｄｓ：Ｌｉｎｕｘ；ｋｅｒｎｅｌ；０（１）ｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍ；ｐｒｏｃｅｓｓｓｃｈｅｄｕｌｉｎｇ；ｋｅｒｎｅｌｐｒｅｅｍｐｔｉｏｎ（ＥＤ．：０，Ｙ）万方数据

Linux 2.6内核O(1)调度算法剖析作者：作者单位：刊名：英文刊名：年，卷(期)：被引用次数：张永选，姚远耀， ZHANG Yong-xuan， YAO Yuan-yao江西经济管理干部学院电子计算机应用系,江西,南昌,330088韶关学院学报JOURNAL OF SHAOGUAN UNIVERSITY2009，30(6)0次

1.河秦.王洪涛

Linux 2.6内核标准教程 T

Linux-2.4.1, L

Linux Kernel Development 20054.陈莉君.张琼声.张宏伟

深入理解LINUX内核 20075.何克右.周彩贞

Linux2.6进程调度机制的剖析[期刊论文]-华中师范大学学报(自然科学版) 2007(04)

1.学位论文

谢伟毅

Linux 2.6内核在嵌入式系统中的应用——Linux 2.6内核到

2006 长期以来，linux作为优秀的开源操作系统软件被广泛应用于嵌入式系统中。而linux操作系统内核是整个系统中最为关键的部分，关系到整个系统的稳定性、可靠性和系统性能。Linux内核的发展非常之快，现在的版本已经到了2.6.14，但由于历史以及厂商的原因，当今的linux嵌入式操作系统中普遍使用的还是2.4的内核。2.6的内核较之于2.4的内核有了很多的改进和bug的修补，在稳定性、可靠性以及性能上都有较大的提升。而要在嵌入式系统中使用新的内核，首先要做的就是内核移植的工作。因此本人把2.6的内核通过修改移植到SH7751RBBNVP嵌入式开发平台中，希望为把2.6内核应用在嵌入式系统中提供条件。本课题的研究内容主要有以下几个方面：文章开始讲述了嵌入式系统以及嵌入式Linux的相关知识，分析了Linux 2.6内核的改进以及性能的提升。接着详细分析了为新的硬件添加Linux支持的原理和方法，然后在此基础之上阐述了在Linux 2.6中为本课题使用的SH7751RBBNVP增加支持的方法，并且通过引用所增加代码的结构和作用进行了进一步分析。最后讲述了实际系统运行的环境的搭建方法。本课题将linux 2.6的内核移植到SH7751RBBNVP嵌入式开发平台中，为Linux 2.6内核在嵌入式系统中的应用提供了条件。2.期刊论文

付智杰.周群彪.FU Qunbiao

MCS spinlock的Linux内核模块实现

-微计算机应用2009,30(7) 研究和分析了Linux系统对SMP支持的特点及其主要的内核路径互斥方法,阐述了MCS spinlock的原理及其优点,最后结合Linux内核的特点,给出MCSspinlock作为最新版本Linux内核的内核模块的实现,及该模块的使用方法.3.学位论文

李彬

基于应用程序的嵌入式Linux内核自动裁剪

2006 嵌入式操作系统作为嵌入式系统的核心组成部分，必须满足嵌入式系统资源有限、面向特定应用、专用硬件和与应用软件密切相关等重要特征。但是，每个嵌入式系统在功能、处理器性能、成本、体积、规模、实时性等各个方面的要求都不相同，因此研究与开发一个嵌入式实时操作系统来满足嵌入式系统多样性要求具有很重要的理论和现实价值，而嵌入式操作系统的可定制剪裁的研究对满足嵌入式系统的多样性要求同样具有重要的理论和实用价值。而目前对Linux操作系统内核的剪裁配置方法大都是在源代码基础上，通过配置工具生成配置文件，然后根据配置文件条件编译生成目标系统内核。但这种方法裁剪的定制能力有限，工具集成度不高，需要通过命令干预，其配置方案、编译过程复杂且需手动完成。因此开发一种高可定制的，能够根据应用程序自动裁剪Linux内核的方法有较高的理论和实践意义。针对以上情况，本文对Linux内核实时性能进行改进，并实现了一种高可定制的、基于应用程序的嵌入式Linux内核自动裁剪，以下是本文实现嵌入式Linux实时内核自动裁剪所完成的工作步骤及内容： 1) 分析Linux应用于嵌入式实时系统的优势、不足，以及嵌入式Linux实时性增强的方法，在此基础上，提出了基于Linux构建一个的嵌入式实时操作系统的方案； 2) 对Linux内核进行细粒度的可定制裁剪，接着主要分析阐述了嵌入式Linux文件系统及网络功能部分，并对文件系统和网络功能部分进行细粒度的裁剪划分，为自动裁剪做好准备： 3) 对Linux内核原有剪裁机制的进行了分析，总结了基于源代码的Linux内核裁剪技术，引入基于应用程序的嵌入式Linux内核自动裁剪方法，根据应用程序调用的函数集合，自动选择需要的功能内核模块，然后自动修改内核．config文件和autoconf.h文件，提供给内核编译使用，实现可视化的Linux内核自动裁剪。最后，针对嵌入式Linux自动裁剪方法，进行了实例验证与分析，并对Linux在嵌入式内核自动裁剪，需要解决一些问题和进一步提高自动裁剪的定制能力提出了白己的建议。4.期刊论文

黄武陵.何小庆.艾云峰

嵌入式Linux实时化技术

-电子产品世界2009,16(2) Linux已经被移植到多种嵌入式处理器,并得到广泛应用.主流内核实时性能不断增强,但在工业控制等特定场合仍无法满足强实时性需求.本文分析了Linux内核时延和实时化主流技术,对实时抢占内核技术进行了分析和评测.5.期刊论文

朱岩.ZHU Yan

应用Linux Test Project组件测试Linux内核的研究

-中国测试2009,35(5) Linux Test Project(简称LTP)是一个以改善日益庞大的Linux内核为目标的组织机构,它通过引入自动化测试来完成Linux内核的测试.为了实现自动化测试这一目标,LTP开发出了可运行在多种Linux操作系统上的测试工具组件.实验结果表明,LTP测试工具组件不仅可以充分用于验证Linux内核的可靠性、健壮性和稳定性,而且它也是改善Linux内核测试最有效的方法之一.6.期刊论文

丁晓波.桑楠.张宁

Linux 2.6内核的内核对象机制分析

-计算机应用2005,25(1) 文中介绍了Linux 2.6内核中管理设备及其驱动程序的内核对象机制,重点分析了该机制的主要数据结构、工作原理和操作函数.提出了基于嵌入应用

时简化目录结构的方法.7.学位论文

归剑峰

Linux系统下Kprobes内核调试过程管理的研究与实现

2007 本文主要研究Linux内核调试技术，阐述了Linux内核调试的基本概念，内核调试的原因、难点及意义。文章对目前主要使用的printk()调试技术，/proc文件系统调试技术，/Sysfs文件系统调试技术，Oops输出信息调试技术，KGDB调试技术，KDB调试技术，SystemTap调试技术等7种Linux内核调试技术进行分析。分别针对这7种目前最常用的Linux内核调试技术进行原理性分析，使用方法的介绍，并且讨论了这些调试技术各自的优势以及不足之处。其次本文重点研究了一种新型的内核调试技术—Kprobes。Kprobes是一个轻量级的内核调试工具，利用Kprobes技术可以在运行的内核中动态的插入探测点，在探测点处执行用户预定义的操作．本文根据Kprobes在Linux内核中的源码实现，针对LinuxCPU异常技术，single—step技术，Loadable KernelModule技术以及RCU同步技术在Kprobes中的应用进行了研究。其次，针对Kprobes目前所支持的kprobe，jprobe，kretprobe等三种调试手段的实现进行了详细的分析研究。最后总结了Kprobes内核调试技术的长处以及缺陷．根据目前Kprobes内核调试技术在管理以及使用上的部分不足提出了基于/proc文件系统的调试过程管理实现方案。实现方案分为四部分实现：第一部分实现方案改进了Kprobes技术无法有效获得全局调试点信息的不足，实现了全局探测点详细信息的检索功能，使得调试者对当前Kprobes的调试状态有一个全面的了解。第二部分实现方案为Kprobes的探测点提供了内核定时器，调试者可以定义探测点的有效时间，增大了调试的灵活性．第三部分利用/proc文件系统对每个探测点都导出控制文件，实现调试点打开和关闭的功能。调试者可以在需要的时候打开、定时或关闭某个探测点并可以获得当前探测点的信息，有效的对每一个内核调试点进行了管理。第四部分实现方案利用函数指针数组实现了单探测点多处理手段的功能，可以在不同时刻选择适合的调试手段，提高了调试的灵活性和调试效率．8.学位论文

廖凯

现代操作系统的实时性研究—基于Linux的路由器RTOS实现

2003 该文针对通用Linux内核在实时性能上的诸多问题,充分利用有关实时操作系统的研究成果与实现方法,独创性地提出了一种分层资源内核(Hierarchical Resource Kernel)的调度框架,并基于该框架实现了一个Linux的实时变种HR-Linux.首先,我们总结了Linux实时化改造工作的主要成果,概括出Linux实时化的四种途径,即:兼容内核、双内核、核心内核以及资源内核. 在这一调度框架里,我们将传统的内核调度器分成了两个子层,即资源接入层和资源调度层;从而在一个统一的调度机制下,实现了对不同调度策略的灵活支持——内核调度器的分层设计是HR-Linux的第一大特点.另外,我们在内核空间实现了一个资源分配器,它与调度翻译器一起组成了我们的资源接入层,并根据具体的调度策略完成实时应用对CPU等系统资源的申请与准入控制,实现了基于不同资源集的应用程序资源隔离——基于资源预约和资源集的资源分配与管理是HR-Linux的第二大特点.此外,我们将资源调度子层中的核心调度器设计成一种多级调度模型,有效地实现了对非周期任务的调度支持,将周期任务与非周期任务的调度有机地融合——支持非周期任务调度的多级资源调度器(MRD)是HR-Linux的第三大特点.同时,我们也利用数学工具对两种典型的实时调度算法:速率单调算法RMA和最早期限优先算法EDF,进行了可调度性分析,在此基础上仔细讨论了优先级倒置问题及其解决方法——对资源同步过程中优先级倒置问题的解决是HR-Linux的第四大特点.其次,我们对内核可抢占、中断线程化等实时技术进行了探讨,并根据Linux内核中基于对称多处理器(SMP)的自旋锁机制,实现了一种全局互斥抢占锁——内核的可抢占是HR-Linux的第五大特点.最后,我们也对中断驱动机制的一个共同问题即接收活锁进行了分析,给出了一种基于中断线程化的反馈控制活锁避免解决方案.在论文的结尾,我们采用了实验的方法,对标准的Linux内核、Linux实时变种RTAI和HR-Linux内核进行了比较.9.学位论文

杜传业

嵌入式Linux内核解析

2007 嵌入式系统的应用与开发是当今计算机行业的一个热点。作为最主要的开放源码软件之一，Linux 因具有内核源码公开、性能稳定、兼容UNIX、支持多种处理器、网络功能强、安全性高、内核可以剪裁等一系列优点，在嵌入式领域得到广泛的应用。本文以Linux 内核源代码为基础，分析了进程调度策略、中断处理机制、系统调用、文件系统等Linux 的内核机制。详细分析Linux 在嵌入式应用中实时性不强的原因以及基于Linux2.6 内核进行实时开发的优点。本文对内核的进程调度和中断系统进行了实时性优化，在分析常见的实时调度算法的基础上提出了改进的最小空闲时间优先算法，减轻了原有算法所产生的颠簸现象。并且分析了标准Linux 的中断机制及其在满足实时性方面的不足之处，针对其不足提出了中断线程化的改进方法。在内核实时性改造的基础上，本文还优化了Linux 的内核裁剪机制，对Linux 内核进行细粒度的可定制裁剪。并且对Linux 内核原有剪裁机制的进行了分析，总结了基于源代码的Linux 内核裁剪技术，引入基于应用程序的嵌入式Linux 内核自动裁剪方法，根据应用程序调用的函数集合，自动选择需要的功能内核模块，提供给内核编译使用，实现可视化的Linux 内核自动裁剪，使之能够更好的适应嵌入式设备。10.期刊论文

易昭华.杜晓黎.金正操

采用统一接口采集Linux内核信息的方法研究

-计算机应用2004,24(12) Linux操作系统本身为用户程序提供了大量接口用于采集内核信息,每一种类型的内核信息都有一个相应的接口.一个对Linux内核进行全面监控的监控系统需要采集大量的内核信息,这就需要调用大量的接口,这给监控系统带来了很大的复杂性.文中提出了一种采用统一接口采集内核信息的方法,并对其进行了研究与实现,采用这种方法.用户程序从同一个接口可以采集到所有的内核信息,简化了用户程序对内核信息的访问.

本文链接：/Periodical_授权使用：菏泽学院图书馆(hzxytsg)，授权号：d92086ab-7f2f-4490-bf1e-9e8e010f7ca9下载时间：2011年2月18日