linux内核调度 - 图文

本章将为大家介绍内核中存在的各种任务调度机理以及它们之间的逻辑关系（这里将覆盖进程调度、推后执行、中断等概念、），在此基础上向大家解释内核中需要同步保护的根本原因和保护方法。最后提供一个内核共享链表同步访问的例子，帮助大家理解内核编程中的同步问题。

内核任务调度与同步关系引言

对于从事应用程序开发的朋友来说，用户空间的任务调度与同步之间的关系相对简单，无需过多考虑需要同步的原因。这一是因为在用户空间中各个进程都拥有独立的运行空间，进程内部的数据对外不可见，所以在各个进程即使并发执行也不会产生对数据访问的竞争。第二是因为用户空间与内核空间独立，所以用户进程不会与内核任务交错执行，因此用户进程不存在与内核任务并发的可能。以上两个原因使得用户同步仅仅需要在进程间通讯和多线程编程时需要考虑。

但是在内核空间中情况要复杂的多，需要考虑同步的原因大大增加了。这是因为内核空间中的共享数据对内核中的所有任务可见，所以当在内核中访问数据时，就必须考虑是否会有其他内核任务并发访问的可能、是否会产生竞争条件、是否需要对数据同步。而内核并发的“罪魁祸首”便是内核中复杂多变的任务调度——这里的任务调度包含所有可能引起内核任务更换的情况。

并发，竞争和同步的概念，我们假定大家都有所了解，本文不再重申。下面一段描述了上述几个概念之间的大致关系，这种关系在内核中同样适用。

对于多线程程序的开发者来说，往往会利用多线程访问共享数据，避免繁琐的进程间通讯。但是多线程对共享数据的并发访问有可能产生竞争，使得数据处于不一致状态，所以需要一些同步方法来保护共享数据。多线程的并发执行是由于线程被抢占式的调度——一个线程在对共享数据访问期间（还未完成）被调度程序中断，将另一个线程投入运行——如果新被调度的线程也要对这个共享数据进行访问，就将产生竞争。为了避免竞争产生，需要使线程串行地访问共享数据 ，也就是说访问需要同步——在一方对数据访问结束后，另一方才能对同一数据进行访问。

内核任务

这里所定义的内核任务是指内核中执行的一切活动对象，每个内核任务都拥有一个独立的程序计数器、栈和一组寄存器。更重要的是它们都属于内核调度（这里的调度是广义上的，不要与进程调度混淆）对象，也就是说它们是可以在内核中交错执行的。 内核任务分类

内核任务包含“内核线程”、“系统调用”、“硬件中断”、“半底任务”等几类。下来我们就简要的讨论上述几类内核任务的特点。 系统调用

系统调用是用户程序通过门机制来进入内核执行的内核例程，它运行在内核态，处于进程上下文中（进程上下文包括进程的堆栈等等环境），可以认为是代表用户进程的内核任务，因此具有用户态任务的特性，比如可以执行进程调度程序（schedule()）、可以睡眠、可以访问当前进程数据（通过current）。但它属于内核任务，所以在执行过程中不能被抢占（2.6内核前），只能自己放弃cpu（睡眠）时，系统才能可能重新调度别的任务。（有关系统调用部分请看《系统调用》一章） 硬中断任务

硬中断是指那些由处理器以外的外设产生的中断，这些中断被处理器接收后交给内核中的中断处理程序处理。要注意的是：第一,硬中断是异步产生的，中断发生后立刻得到处理，也就是说中断操作可以抢占内核中正在运行的代码。这点非常重要。第二，中断操作是发生在中断上下文中的（所谓中断上下文指的是和任何进程无关的上下文环境）。中断上下文中不可以使用进程相关的资源，也不能够进行调度或睡眠。因为调度会引起睡眠，但睡眠必须针对进程而言（睡眠其实是标记进程状态，然后把当前进程推入睡眠列队），而异步发生的中断处理程序根本不知道当前进程的任何信息，也不关心当前那个进程在运行，它完全是个过客。（有关系统调用部分请看《硬件中断》一章） 下半底任务

半底的来历完全出自上面提到的硬中断的影响。硬件中断任务（处理程序）是一个快速、异步、简单的对硬件做出迅速响应并在最短时间内完成必要操作。硬中断处理程序可以抢占内核任务并且执行时还会屏

蔽同级中断或其它中断，因此中断处理必须要快、不能阻塞。这样一来对于一些处理要求过程比较复杂的任务就不合适在中断任务中一次处理。比如，网卡接收数据过程中首先网卡发送中断信号告诉CPU来取数据，然后系统从网卡中读取数据存入系统缓冲中，再下来解析数据然后送入应用层。这个过程如果都让中断处理程序处理显然过程太长，造成新来的中断丢失。因此Linux开发人员将这种任务分割为两个部分，一个叫上底，即中断处理程序，短平快地处理与硬件相关的操作（如从网卡读数据到系统缓存）；而把对时间要求相对宽松的任务（如解析数据的工作）放在另一个部分执行，这个部分就是我们这里要讲的下半底。

下半底是一种退后执行任务，它将某些不那么紧迫的任务推迟到系统更方便的时刻运行。内核中实现下半底的手段经过不断演化，目前以经从最原始的BH(bottom thalf)演生出BH、任务队列（Task queues）、软中断（Softirq）、Tasklet、工作队列（Work queues）（2.6内核中新出现的）。下面我们就介绍一下他们各自的特点。

软中断操作

软中断（softirq）不象硬中断那样是由硬件中断信号触发执行的，所以也不同于硬件中断那样时随时都能够被执行，笼统来讲软中断会在内核处理任务完毕后返回用户级程序前得到处理机会。具体的讲有三个时刻它将被执行(do_softirq())：硬件中断操作完成后；系统调用返回时；内核调度程序中；（另外的内核线程ksoftirqd周期执行软中断）。

从中可以看出软中断会紧随硬中断处理(好象虎假虎威),所以抢占内核

任务——至少在时钟中断后总有机会运行一次。还要记得软中断可以在不同处器上并发执行。

在对称多处理器的机器，那么两个任务就可以真正的在临界区中同时执行了，这种类型被称为真并发。相对而言在单处理器上并发其实并不是真的同时发生，而是相互交错执行，是伪并发。但它们都同样会造成竞争条件，而且也需要同样的保护。

软中断是很底层的机制，一般除了在网络子系统和SCSI子系统这样对性能要求很高以及要求并发处理的时候，才会选择使用软中断。软中断虽然灵活性高和效率高，但是你自己必须处理复杂的同步处理（因为它可在多处理器上并发），所以通常都不直接使用，而是作为支持Tasklet和BH的根本。

需要说明的是软中断的执行也处于中断上下文中，所以中断上下文对它的限制是和硬中断一样的。 Tasklet

Tasklet和bottom half都是建立在软中断之上的两种延迟机制，其中具体不同在于软中断是静态分配的，而且同类软中断可以并发地在几个CPU上运行；Tasklet可以动态分配，并且不同种类的Tasklets可以并发地在几个CPU上运行，但同类的tasklets 不可以；bottom half只能静态分配，实质上下半部分是一个不能与其它下半部分并发执行的高优先级tasklet，即使它们类型不同，而且在不同CPU上运行。Tasklet可以理解为软中断的派生，所以它的调度时机与软中断一致。

对于内核中需要延迟执行的多数任务都可以利用tasklet来完成，由于同类tasklet本身已经进行了同步保护，所以使用tasklet相比软中断要简单的多，而且效率也不错。 bottom half

BH时最早得内核延迟方法，它原始、简单容易控制，因为所有的BH处理程序都被严格地顺序执行——不允许任何两个BH处理程序同时并发执行，即使它们的类型不同也不可以，这样以来BH执行其间减少了许多同步保护。但是BH不得不被淘汰，因为它的“简便”牺牲了多处理器并发处理的高性能，等于一队人过独木桥那样速度受到牵制。 任务队列

任务列队是BH的替代品，来自BH，所以它的属性也和BH相同。它原意在于简化BH的操作接口，但它的随意性（数量随意、执行时机随意）却给系统带来了混乱，所以到今天已经被工作队列（在2.6内核中）所取代。

不过在2.4内核中任务队列还是被大量应用，尤其是调度队列、定时器队列和及时队列等三种任务队列（除了这三种系统已接管的特定任务队列外，你自己也可随心所欲的建立自己的任务队列，当然这时你要自己调度它）。调度队列的任务会在每次进程调度时得到处理，它是在进程上下文中处理的；定时器队列会在每次时钟滴答时得到处理；立即队列会在中断返回或调度时获得处理（所以处理最快），他们都是在中断上下问中处理的。

这些任务队列在内核内由一个统一的内核线程调度，该线程名为keventd，进程号是2（2.4.18）。你可用ps命令查看到该进程。 内核线程

内核线程可以理解成在内核中运行的特殊进程，它有自己的“进程上下”（借用调用它的用户进程的上下文），所以同样被进程调度程序调度，也可以睡眠——它和用户进程属性何其相似，不同之处就在于内核线程运行于内核空间，可访问内核数据，运行期间不能抢占。

传统的Unix系统把一些重要的任务委托给周期性执行的进程，这些任务包括刷新磁盘高速缓存，交换出不用的页框，维护网络链接等等。事实上，以严格线性的方式执行这些任务的确效率不高，如果把他们放在后台调度，不管是对它们的函数还是对终端用户进程都能得到较好的响应。因为一些系统进程只运行在内核态，现代操作系统把它们的函数委托给内核线程（Kernel Thread），内核线程不受不必要的用户态上下文的拖累。 内核中的同步

内核只要存在任务交错执行，就必然会存在对共享数据的并发问题，也就必然存在对数据的保护。而内核中任务交错执行原因归根结底还是由于内核任务调度造成的。我们下面归纳一下内核中同步的原因。 同步原因

? 中断——中断几乎可以在任何时刻异步发生，也就可能随时打断当

前正在执行的代码。

? 睡眠及与用户空间的同步——在内核执行的进程可能会睡眠，这就

会唤醒调度程序，从而导致调度一个新的用户进程执行。 ? 对称多处理——两个或多个处理器可以同时执行代码。

? 内核抢占——因为内核具有抢占性，所以内核中的任务可能会被另

一任务抢占（在2.6内核引进的新能力）。

后两种情况大大加深了内核任务并发执行的可能，使得并发随时随刻都有可能发生，而且不可清晰预见，规律难寻。 内核心任务之间的并发关系

上述内核任务很多情况是可以交错执行的——记住，一个下半部实际上可能在任何时候执行，所以很有可能产生竞争（都要访问同一个数据结构时，就产生了竞争）。下面分析这些内核任务之间有那些可能的并发行为。

可以抽象出，程序（用户态和内核态一样）并发执行的总原因无非是正在运行中得程序被其它程序抢占，所以我们必须看看内核任务之间的抢占关系：

? 中断处理程序可以抢占内核中的所有程序（当没有锁保护时），

包括软中断，tasklet，bottom half和系统的调用、内核线程，甚至也包括硬中断处理程序。也就是说中断处理程序可以和这些所有的内核任务并发执行，如果被抢占的程序和中断处理程序都要访问同一个资源，就必然有可能产生竞争。

? 软件中断也可以抢占内核中的所有任务，所以内核代码（比如，

系统调用、内核线程等）中有数据和软中断共享，就有会有竞争——除此外硬件中断处理程序也有可能被软中断打断，条件是硬中断被其它硬中断打断，软中断随即便获得了执行机会，因为软中断是跟在硬中断后执行的。此外要注意的是，软中断即使是同种类型的也可以并发的运行在不同处理器上，所以它们之间共享数据都会产生竞争。（如果在用一个处理器上软中断之间是不能相互抢占的）。

? 同类的tasklet不可能同时运行，所以对于同类tasklet之间是串

行运行的，他们不会产生并发；但两个不同种类的tasklet有可已在不同处理器上并发运行，如果之间有数据共享就会产生竞争（在同一个处理器上运行的tasklet不发生相互抢占的情况）。 ? Bottom half 无论是否是同类的，即使在不同处理器上也都不能

并发执行，它是绝对串行化的，所以它们之间永远不能产生竞争。任务列队属性基本同BH。

? 系统调用和内核线程这种运行在进程上下文中的内核任务可能

和各种内核任务并发，除了上面提到的中断（软，硬）抢占它产生并发外，它是有可能自发性地主动睡眠（比如在一些阻塞性的操作中），放弃处理器，重新调度其它任务，所以系统调用和内核线程除会与软硬中断（半底等）发生竞争，也会与其他（包括自己）系统调用与内核线程发生竞争。我们尤其要注意这种情况。

注意：tasklet和bottom half是建立在软中断之上的，所以它们也都遵从软中断的调度规则——都可以打断进程上下问中的内核代码（系统调用），都可被硬中断打断——这些都可能产生并发。

内核同步措施

为了避免并发，防止竞争。内核提供了一组同步方法来提供对共享数据的保护。 我们的重点不是介绍这些方法的详细用法，而是强调为什么使用这些方法和它们之间的差别。

Linux使用的同步机制可以说从2.0到2.6以来不断发展完善。从最初的原子操作，到后来的信号量，从大内核锁到今天的自旋锁。这些同步机制的发展伴随Linux从单处理器到对称多处理器的过度；伴随着从非抢占内核到抢占内核的过度。锁机制越来越有效，也越来越复杂。

目前来说内核中原子操作多用来做计数使用，其它情况最常用的是两重锁以及它们的变种，一个是自旋锁，另一个是信号量。我们下来就着重介绍一下这两中锁机制。 自旋锁

自旋锁是专为防止多处理器并发而引入的一种锁，它在内核中大量应用于中断处理等部分（对于单处理器来说，防止中断处理中的并发可简单采用关闭中断的方式，不需要自旋锁）。

自旋锁最多只能被一个内核任务持有，如果一个内核任务试图请求一个已被争用（已经被持有）的自旋锁，那么这个任务就会一直进行忙循环——旋转——等待锁重新可用。要是锁未被争用，请求它的内核任务便能立刻得到它并且继续进行。自旋锁可以在任何时刻防止多于一个

的内核任务同时进入临界区，因此这种锁可有效地避免多处理器上并发运行的内核任务竞争共享资源。

事实上，自旋锁的初衷就是：在短期间内进行轻量级的锁定。一个被争用的自旋锁使得请求它的线程在等待锁重新可用期间进行自旋（特别浪费处理器时间），所以自旋锁不应该被持有时间过长。如果需要长时间锁定,最好使用信号量。 自旋锁的基本形式如下： spin_lock(&mr_lock); /*临界区*/

spin_unlock(&mr_lock);

因为自旋锁在同一时刻只能被最多一个内核任务持有，所以一个时刻只有一个线程允许存在于临界区中。这点很好的满足了对称多处理机器需要的锁定服务。在单处理器上，自旋锁仅仅当作一个设置内核抢占的开关。如果内核抢占也不存在，那么自旋锁会在编译时被完全剔除出内核。

自旋锁在内核中有许多变种，如对bottom half 而言，可以使用spin_lock_bh()用来获得特定锁并且关闭半底执行。相反的操作由spin_unlock_bh()来执行；如果临界区的访问逻辑可以被清晰的分为读和写这种模式，那么可以使用读者/写者自旋锁，调用形式为：

读者的代码路径：

read_lock(&mr_rwlock); /*只读临界区*/

read_unlock(&mr_rwlock);

写者的代码路径：

write_lock(&mr_rwlock); /*读写临界区*/

write_unlock(&mr_rwlock);

简单的说，自旋锁在内核中主要用来防止多处理器中并发访问临界区，防止内核抢占造成的竞争。另外自旋锁不允许任务睡眠（持有自旋锁的任务睡眠会造成自死锁——因为睡眠有可能造成持有锁的内核任务被重新调度，而再次申请自己已持有的锁），它能够在中断上下文中使用。

死锁：假设有一个或多个内核任务和一个或多个资源，每个内核都在等待其中的一个资源，但所有的资源都已经被占用了。这便会发生所有内核任务都在相互等待，但它们永远不会释放已经占有的资源，于是任何内核任务都无法获得所需要的资源，无法继续运行，这便意味着死锁发生了。自死琐是说自己占有了某个资源，然后自己又申请自己已占有的资源，显然不可能再获得该资源，因此就自缚手脚了。 信号量

Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个已被持有的信号量时，信号量会将其推入等待队列，然后让其睡眠。这时处理器获得自由去执行其它代码。当持有信号量的进程将信号量释放后，在等待队列中的一个任务将被唤醒，从而便可以获得这个信号量。

信号量的睡眠特性，使得信号量适用于锁会被长时间持有的情况；只能在进程上下文中使用，因为中断上下文中是不能被调度的；另外当代码持有信号量时，不可以再持有自旋锁。 信号量基本使用形式为：

static DECLARE_MUTEX(mr_sem);//声明互斥信号量 …

if(down_interruptible(&mr_sem))

/*可被中断的睡眠，当信号来到，睡眠的任务被唤醒 */ /*临界区…*/ up(&mr_sem);

同自旋锁一样，信号量在内核中也有许多变种，比如读者－写者信号量等，这里不再做介绍了。 信号量和自旋锁区别

虽然听起来两者之间使用条件复杂，其实在实际使用中信号量和自旋锁并不易混淆。注意以下原则。

如果代码需要睡眠——这往往是发生在和用户空间同步时——使用信号量是唯一的选择。由于不受睡眠的限制，使用信号量通常来说更加简单一些。如果需要在自旋锁和信号量中作选择，应该取决于锁被持有的时间长短。理想情况是所有的锁都应该尽可能短的被持有，但是如果锁的持有时间较长的话，使用信号量是更好的选择。另外，信号量不同于自旋锁，它不会关闭内核抢占，所以持有自旋锁的代码可以被抢占。这意味者信号量不会对影响调度反应时间带来负面影响。 自旋锁对信号量

―――――――――――――――――――――――――――――――

需求 建议的加锁方法 低开销加锁 优先使用自旋锁

短期琐定 优先使用自旋锁 长期加锁 优先使用信号量 中断上下文中加锁 使用自旋锁 持有锁是需要睡眠、调度 使用信号量

―――――――――――――――――――――――――――――――

引自 《Linux内核开发》

防止并发的方式除了上面提到的外还有很多，我们不详细介绍了。说了这么多希望大家认识到，并发控制在内核编程中是个特别难缠的问题，要驾御它必须清楚的认识到内核中各种任务的调度时机与特点，并且在开发初期就应特别小心保护共享数据（一切共享数据、一切能被别人看到的数据都要注意保护），别等到开发完成才去亡羊补牢。 内核中的调度与同步实例 代码功能介绍

我们希望能在内核中能“制造”一些“冲突”——多种内核任务并发访问共享数据——从而来观察在Linux内核中到底会存在那些潜在的并发危险，有哪些冲突可能造成系统故障，又有哪些措施可以化解冲突。

我们假设存在这样一个的内核共享资源：链表。另外我们构造一个内核多任务访问链表的场景：内核线程向链表加如新节点；内核定时器定时删除接点；系统调用删除销毁链表。

上面三种内核任务并发时，有可能会破坏链表数据的完整性，所以我们会对链表进行同步访问保护，以确保数据一致性。 代码结构体系介绍 内核任务简介和并发关系

内核任务本文中是指处于内核态执行的任务，具体讲包括：“内核线程”、“系统调用”、“硬件中断”、“半底任务”等几类，下面简要介绍几种我们将用到的内核任务。

系统调用：系统调用是用户程序通过门机制来进入内核执行的内核例程，它运行在内核态，处于进程上下文中（进程上下文包括进程的堆栈等等环境），可以认为是代表用户进程的内核任务，因此具有用户态任务的特性。

但它属于内核任务，所以在执行过程中不能被抢占（2.6内核前），只能自己放弃cpu（睡眠）时，系统才能可能重新调度别的任务。

内核线程：内核线程可以理解成在内核中运行的特殊进程，它有自己的“进程上下”（借用调用它的用户进程的上下文），所以同样被进程调度程序调度，也可以睡眠——它和用户进程属性何其相似，不同之处就在于内核线程运行于内核空间，可访问内核数据，运行期间不能抢占。

传统的Unix系统把一些重要的任务委托给周期性执行的进程，这些任务包括刷新磁盘高速缓存，交换出不用的页框，维护网络链接等等。事实上，以严格线性的方式执行这些任务的确效率不高，如果把他们放在后台调度，不管是对它们的函数还是对终端用户进程都能得到较好的

响应。因为一些系统进程只运行在内核态，现代操作系统把它们的函数委托给内核线程（Kernel Thread），内核线程不受不必要的用户态上下文的拖累。

定时器任务队列：任务队列属于是半底bottom half操作的替代品，主要有调度队列、定时器队列和及时队列等三种任务队列（除了这三种系统已接管的特定任务队列外，你自己也可随心所欲的建立自己的任务队列，当然这时你要自己调度它）。我们使用的定时器队列会在每次时钟滴答时得到处理，它处于中断上下问中处理的。

上述三种内核任务存在如下竞争关系——系统调用和内核线程这种运行在进程上下文中的内核任务可能和各种内核任务并发，除了中断（定时器任务队列属于软中断范畴）抢占它产生并发外，它是有可能自发性地主动睡眠（比如在一些阻塞性的操作中），放弃处理器，重新调度其它任务，所以系统调用和内核线程除会与定时器任务队列发生竞争，也会与其他（包括自己）系统调用与内核线程发生竞争。 基本函数

我们主要的共享资源是链表（mine）,操作它的内核任务有三种：一个是100个内核线程（sharelist），它们负责从表头将新节点（struct my_struct）插入链表。二是定时器任务(qt_task)，它负责每个时钟滴答时从链表头删除一个节点。三是系统调用（由rmmod命令调用的share_exit），它负责销毁链表并卸载模块。

我们利用模块（sharelist.o）实现上述场景。加载模块时会建立定时器任务列队，并将要执行的任务(task.rounting=qt_task)插入定时器队列（tq_timer），然后反复调度执行（但别不停的执行）。与此同时利用系统中的keventd内核线程（它的目的是执行任务队列,由schedule_task激活，PID=2），创建100个内核线程(创建函数kernel_thread)执行插入链表的工作（由sharelist完成）——但当链表长度超过100时，则从链表尾删除节点。最后当你需要卸载模块时，调用share_exit函数销毁整个链表，并做一些诸如销毁我们建立的内核进程的收尾工作。

另外我们要注意在程序中该如何保护我们的链表。上述场景中存在的内核并发包括——内核线程之间的并发、内核任务与定时器任务的并发。要知道内核线程执行在进程上下文中，而定时器任务属于下半部分，执行在中断上下文中。在这两部分交错执行中进行保护则需要采用自旋锁。我们例子中使用了spin_lock_bh()锁在内核线程的执行路径中对链表进行保护；在下半部分由于任务队列是串行执行并且不能被内核任务或系统调用打断，所以不必加锁。另外在卸载模块时，删除链表中仍然存在系统调用与下半部分的并发可能，因此也需要按上述方式加锁。

除了对共享链表访问使用自旋锁以外，还有两个需要同步的地方，一是计数（count），该变量属于原子类型，用于记录链表接点的id。另外一个是利用信号量同步内核创建线程，调度keventd后执行被堵塞住(down)，等内核线程实际启动后,才可继续执行（up）。下面的图给出了个任务的基本关系和对链表的操作。

Sharelist

该函数是作为内核线程由keventd调度执行的，作用是向链表中加如新节点（如果到达100个节点则删除尾部节点，因为我们不能无限制耗用内核内存），为了防止定时器任务队列抢占执行时，造成数据链表数据不一致，所以需要在操作链表期间进行同步保护——加锁，即spin_lock_bh()禁止或spin_unlock_bh开启定时器任务执行权能。 start_kthread

顾名思义，该函数用来触发执行内核线程Sharelist的封装函数。我们的目的是用keventd[1]来启动内核线程。我们不直接利用kernel_thread启动内核线程，而要交由keventd内核来间接启动sharelist的原因是——防止直接启用sharelist内核线程时会继承用户父进程的“不良”属性（如insmod等的属性），影响其执行，所以我们利用keventd——它没有“前科”——启动sharelist则可保证sharelist不会染上父进程的“不良习惯”。

该函数首先必须对任务队列进行初始化——如初始化调度任务队列头；注册sharelist触发函数；将任务加如调度任务队列（以等待keventd执行调度）。

tq.sync=0;

INIT_LIST_HEAD(&tq.list); tq.routine=kthread_launcher; tq.data=NULL; schedule_task(&tq);

kthread_launcher

该函数作用仅仅是通过kernel_thread方法启动内核线程sharelist。注意为了能依次建立（且启动）内核线程，我们start_kthread函数会在将任务加入调度队列后利用信号量自我堵塞（down(&sem)），直到在内核线程执行后才解除堵塞up(&sem)，这种同步保证了串行创建内核线程。

qt_task

该函数作为定时器任务运行，删除链表节点。为了防止不知节制的删除，我们指定删除次数为count＝1200次。

定时器任务队列为tq_timer，任务结构为struct tq_struct task，具体任务函数

为qt_task。将任务加入到定时器队列需要调用queue_task(&task,&tq_timer)——没次执行定时器任务前都需要将任务填加到队列中。

share_init

该函数是我们的模块注册函数，也是通过它启动我们的定时器任务和内核线程。它先初始化定时器任务队列，注册定时器任务qt_task：

init_waitqueue_head(&queue);

task.routine=(void*)qt_task;

task.data=NULL;

queue_task(&task,&tq_timer);

然后依次启动1000个内核线程start_kthread()。到此我们开始对链表进行操作。

share_exit

该函数是模块注销函数，它和注册函数一样属于系统调用，负责销毁链表。由于销毁时刻内核线程与定时器任务都在运行，所以作为一个系统调用操作链表时，应该进行同步保护，所以要锁住链表，在这里就是停止定时器任务队列——spin_lock_bh（同时也会停止内核线程对链表的操作，因为自旋锁保证了任务执行的串行化，此刻其它任务没机会执行了），当链表销毁重新打开自旋锁允许任务队列运行。

除了对共享链表访问使用自旋锁以外，还有两个需要同步的地方，一是计数（count），该变量属于原子类型，用于记录链表接点的id

share_exit

sharelist

链表

qt_task kevent

start_kthread

进程上下文

中断上下文

进程上下文 down up 上锁

添加节点

删除节点

关键代码解释

链表是内核开发中的常见数据组织形式，因此为了方便开发和统一结构，内核提供了一套辅助例程帮助操作链表：声明链表结构LIST_HEAD()、

加节点到链表list_add()、删除节点list_del()、遍历链表list_entry()。

任务队列结构 struct tq_struct

STEP BY STEP——观察结果

结果中可看到，内核线程加入节点速度很快，每次时钟间隔（删除节点）期间都可加入一百个左右的节点（由于内核中还有其他任务运行，影响内核线程和定时器任务运行频率，所以定时器任务执行期间加入节点数会有所不同）。 由于内核线程填加节点速度快于定时器任务删除

节点速度，所以很快就链表长度就会达到我们指定长度（800），这时新内核线程就会从删除头节点（最早加入的节点）。 结束

并发的发生随处都有，但是有它引起的错误可并非每次都有，因为并发过程中引起错误的地方往往就一两步，因此交错执行这一两步要靠“运气”，出错的几率有时很小。但是一旦发生后果都是灾难性的，比如宕机，破坏数据完整性等。所以我们对并发绝不能掉以轻信，必须拿出“把纸老虎当真老虎的”决心来对待一切内核代码中的并发可能，即便在单处理器上编程也需要到移植到多处理器的情况，总之一切都要谨慎小心。

进程的管理与调度

进程管理

进程描述符及任务结构

进程存放在叫做任务队列（tasklist）的双向循环链表中。链表中的每一项包含一个具体进程的所有信息，类型为task_struct，称为进程描述符（process descriptor），该结构定义在文件中。

Linux通过slab分配器分配task_struct结构，这样能达到对象复用和缓存着色（cache coloring）的目的。另一方面，为了避免使用额外的寄存器存储专门记录，让像x86这样寄存器较少的硬件体系结构只要通过栈指针就能计算出task_struct的位置，该结构为thread_info，在文件中定义。 Linux中可以用ps命令查看所有进程的信息。

Linux基础篇之内存管理机制 http://www.linuxidc.com/Linux/2014-03/98293.htm

Linux内存管理之高端内存 http://www.linuxidc.com/Linux/2013-06/85693.htmLinux内存管理之分段机制 http://www.linuxidc.com/Linux/2012-11/74480.htmLinux内存管理伙伴算法 http://www.linuxidc.com/Linux/2012-09/70711.htm

进程状态

task_struct中的state描述进程的当前状态。进程的状态一共有5种，而进程必然处于其中一种状态：

1）TASK_RUNNING（运行）——进程是可执行的，它或者正在执行，或者在运行队列中等待执行。这是进程在用户空间中执行唯一可能的状态；也可以应用到内核空间中正在执行的进程。

2）TASK_INTERRUPTIBLE（可中断）——进程正在睡眠（也就是说它被阻塞）等待某些条件的达成。一旦这些条件达成，内核就会把进程状态设置为运行，处于此状态的进程也会因为接收到信号而提前被唤醒并投入运行。

3）TASK_UNINTERRUPTIBLE（不可中断）——除了不会因为接收到信号而被唤醒从而投入运行外，这个状态与可打断状态相同。这个状态通常在进程必须在等待时不受干扰或等待事件很快就会发生时出现。由于处于此状态的任务对信号不作响应，所以较之可中断状态，使用得较少。

4）TASK_ZOMBIE（僵死）——该进程已经结束了，但是其父进程还没有调用wait4()系统调用。为了父进程能够获知它的消息，子进程的进程描述符仍然被保留着。一旦父进程调用了wait4()，进程描述符就会被释放。

5）TASK_STOPPED（停止）——进程停止执行，进程没有投入运行也不能投入运行。通常这种状态发生在接收到SIGSTOP，SIGTSTP，SIGTTIN，SIGTTOU等信号的时候。此外，在调试期间接收到任何信号，都会使进程进入这种状态。

需要调整进程的状态，最好使用set_task_state(task, state)函数，在必要的时候，它会设置内存屏障来强制其他处理器作重新排序（SMP）。 进程的各个状态之间的转化构成了进程的整个生命周期，

进程的创建

在Linux系统中，所有的进程都是PID为1的init进程的后代。内核在系统启动的最后阶段启动init进程。该进程读取系统的初始化脚本（initscript）并执行其他的相关程序，最终完成系统启动的整个进程。

Linux提供两个函数去处理进程的创建和执行：fork()和exec()。首先，fork()通过拷贝当前进程创建一个子进程。子进程与父进程的区别仅仅在于PID（每个进程唯一），PPID（父进程的PID）和某些资源和统计量（例如挂起的信号）。exec()函数负责读取可执行文件并将其载入地址空间开始运行。

fork()使用写时拷贝（copy-on-write）页实现。内核在fork进程时不复制整个进程地址空间，让父进程和子进程共享同一个拷贝，当需要写入时，数据才会被复制，使各进程拥有自己的拷贝。在页根本不会被写入的情况下（fork()后立即exec()），fork的实际开销只有复制父进程的页表以及给子进程创建唯一的task_struct。

创建进程的fork()函数实际上最终是调用clone()函数。创建线程和进程的步骤一样，只是最终传给clone()函数的参数不同。比如，通过一个普通的fork来创建进程，相当于：clone(SIGCHLD, 0)；创建一个和父进程共享地址空间，文件系统资源，文件描述符和信号处理程序的进程，即一个线程：clone(CLONE_VM | CLONE_FS | CLONE_FILES |CLONE_SIGHAND, 0)。

在内核中创建的内核线程与普通的进程之间还有个主要区别在于：内核线程没有独立的地址空间，它们只能在内核空间运行。 fork和vfork的区别

fork（）与vfock（）都是创建一个进程，那他们有什么区别呢？总结有以下三点区别： 1. fork （）：子进程拷贝父进程的数据段，代码段 vfork （ ）：子进程与父进程共享数据段 2. fork （）父子进程的执行次序不确定

vfork 保证子进程先运行，在调用exec 或exit 之前与父进程数据是共享的,在它调用exec 或exit 之后父进程才可能被调度运行。

3. vfork （）保证子进程先运行，在她调用exec 或exit 之后父进程才可能被调度运行。如果在

调用这两个函数之前子进程依赖于父进程的进一步动作，则会导致死锁。

Linux内核之CFS调度和组调度

Linux支持三种进程调度策略，分别是SCHED_FIFO 、 SCHED_RR和SCHED_NORMAL。Linux支持两种类型的进程，实时进程和普通进程。实时进程可以采用SCHED_FIFO 和SCHED_RR调度策略；普通进程采用SCHED_NORMAL调度策略。

本文主要讨论普通进程的调度算法，为了描述方便，后面章节中的“进程”指“普通进程”。

从Linux2.6.23内核到目前最新的Linux3.3.5内核的普通进程（采用调度策略SCHED_NORMAL）采用了绝对公平调度算法，CFS(completely fair schedule)。CFS从RSDL/SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再区分交互式进程。它将所有的进程都统一对待，这就是公平的含义。CFS 调度中，进程数据结构中的动态优先级成员prio还继续有效，只是内核不再动态调整进程的动态优先级了。

进程的优先级为100—139，对应的nice值为-20—19。和之前版本的优先级规定相同。Nice 和优先级对应关系如下

如何实现公平调度的？内核给每个进程维护了一个虚拟运行时间vruntime，每个进程运行一段时间后，虚拟运行时间会增加，但是运行同样的实际时间每个

进程增加的数值是不同的。比如nice值为0的进程运行了10ms，其虚拟运行时间增加了1vms（vms为1虚拟毫秒，为了描述方便而定义）；nice为19的进程运行10ms，其虚拟运行时间增加了1000vms。进程在其生命周期中，其虚拟运行时间一直都是在增加的。内核把虚拟运行时间看做实际运行时间，为了公平起见要选择运行时间短的进程进行运行。所以内核在调度中总是选择虚拟运行时间小的进程。对内核来说，这样就很公平了，O(∩_∩)O

同样运行10ms，如何确定一个进程该增加多少vms？增加的虚拟运行时间和进程的优先级nice数值有关，每个nice数值对应一个权重数值，见下图。

每个进程虚拟运行时间增加的时间量和 （NICE_0_LOAD/nice_n_weight） 成正比。其中NICE_0_LOAD 为1024，即nice数值为0的权重，nice_n_weight即为nice数值为n的进程的权重，如nice为-20（优先级最高的普通进程）的权重为88761。从这种算法也可以看出，优先级高的进程的虚拟运行时间增加的慢，其实际运行时间累计数值也就长。同样，这种算法能保证优先级低的进程也有运行机会，只是实际运行的时间比较短。

内核要把所有running状态的进程放到一起，在需要调度时从中取出一个虚拟运行时间短的进程。因为发生调度的频率非常高，查找合适进程的算法就变的很重要了。在CFS调度中，内核采用了以进程虚拟运行时间为key值的红黑树数据结构挂接各个running的进程。有关红黑树请参考《linux内核之红黑树》。 先要引入一个重要概念，调度实体(sched entiy)：就是调度的对象。每个进程的task_struct包含了调度实体成员变量se。为何要引入调度实体，而不是直接使用进程的task_struct？是因为在CFS中支持CFS组调度，一个组中可能包含1个或多个进程。不能通过组中任何进程的task_struct来调度组，所以引入了调度实体的概念。为了统一起见，进程组和进程都使用调度实体保存调度相关的信息。后面会介绍CFS组调度。

在多核系统中，每个CPU（此处指一个核心）对应一个全局变量

per_cpu_runqueues，其数据结构为struct rq，该变量为调度的最顶层的数据结构。在该数据结构中包含了cfs，其数据结构为struct cfs_rq。cfs 就是在该cpu上CFS调度的顶级结构，或者说是CFS调度的入口点。其实rq中还包括了rt成员变量，rt是实时进程调度的顶级结构。

struct cfs_rq { 为了说明方便，只保留部分成员变量 struct rb_root tasks_timeline; struct rb_node *rb_leftmost;

struct sched_entity *curr, *next, *last, *skip; }

其中成员变量tasks_timeline指向了红黑树的根，所有的进程都挂到这棵红黑树上（有些是间接挂接的）。如下图中的单个进程，进程数据结构task_struct中包含了成员变量se，即调度实体。调度实体se中包含了run_node节点，se通过该节点挂接到红黑树上。在选择需要调度的进程时，内核将搜索这个红黑树，找到虚拟运行时间小的进程，并把该进程从树上摘下。同时会把切换出（因运行时间长而被剥夺运行的进程插入红黑树）。由于红黑树的特性，其插入、摘除和超找的效率都很高，从而保证了CFS调度的效率。 因下图不清楚，直接把原始的word文档传上了：组调度.doc

linux内核之CFS调度和

CFS组调度

为何要引入CFS组调度呢？假设用户A和B共用一台机器。我们可能希望A和B能公平的分享CPU资源，但是如果用户A使用创建了8个进程、而用户B只创建1个进程，根据CFS调度是基于进程的（假设用户进程的优先级相同），A用户占用的CPU的时间将是B用户的8倍。

如何保证A、B用户公平分享CPU呢？组调度就能做到这一点。把属于用户A和B的进程各分为一组，调度程序将先从两个组中选择一个组，再从选中的组中选择一个进程来执行。如果两个组被选中的机率相当，那么用户A和B将各占有约50%的CPU。

相关数据结构

在linux内核中，使用task_group结构来管理组调度的组。所有存在的task_group组成一个树型结构。

一个task_group可以包含具有任意调度类别的进程（具体来说是实时进程和普通进程两种类别），task_group包含实时进程对应的调度实体和调度队列，以及普通进程对应的调度实体和调度队列。见下面的结构定义 struct task_group{ 删除无关的成员变量 #ifdef CONFIG_FAIR_GROUP_SCHED

struct sched_entity **se; 普通进程调度实体，每个cpu上一个 struct cfs_rq **cfs_rq; 普通进程调度队列，每个cpu上一个 #endif

#ifdef CONFIG_RT_GROUP_SCHED

struct sched_rt_entity **rt_se; 实时进程调度实体，每个cpu上一个 struct rt_rq **rt_rq; 实时进程调度队列，每个cpu上一个 #endif }

下面只描述CFS组调度。在多核处理器平台上，内核在创建组的时候，内核会在每个cpu上给该组创建一个调度实体和一个调度队列，见上面图中红色方框外的部分。组在各个cpu上的调度实体se是单独被调度的。红色方框内是指在一个cpu上的调度数据结构。如果组在该cpu上有可以运行的进程，则组在该cpu上的调度实体se就会挂到该cpu上cfs_rq的红黑树上。组在该cpu上可以运行的进程则挂到了组调度实体se中my_q指向的红黑树上，参见上图中右下角单个进程。

CFS组的优先级。组在创建时其优先级是固定的，其nice值为0。组在某cpu上所能获得的运行时间和一个单独的nice为0的进程获得的运行时间相同。组的se在获得了一定运行时间后，按照CFS算法相同的方法把实际运行时间分配给其my_q上的所有进程。从而实现了A用户和B用户占用相同的CPU时间的目的。

疑问：有关进程权重表使用的疑问，在计算进程虚拟运行时间时，总是需要进行一次乘法和一次除法运算。大家都知道乘法和除法运算是比较消耗CPU周期的，为何不直接修改一下权重表prio_to_weight[]中的数值，使得其中的每一项数值都等于目前的数值除以15后取整（当然是人工计算出结果后替换到表中），使得优先级最小的进程的权重为1。在计算虚拟运行时间时可以直接乘以权重值，这样就可以减少一次除法了。这样是否更好？

另外，从代码中看到，nice为0的进程在计算虚拟运行时间时是直接增加了真实的时间差，而没有进行乘和除的过程，如下图，是否是因为设计初衷认为大多数的普通进程的nice值都是0的缘故？

linux内核的三种调度方法

1，SCHED_OTHER 分时调度策略，

2，SCHED_FIFO实时调度策略，先到先服务 3，SCHED_RR实时调度策略，时间片轮转

实时进程将得到优先调用，实时进程根据实时优先级决定调度权值，分时进程则通过nice和counter值决定权值，nice越小，counter越大，被调度的概率越大，也就是曾经使用了cpu最少的进程将会得到优先调度。

SHCED_RR和SCHED_FIFO的不同：

当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪队列尾。放在队列尾保证了所有具有相同优先级的RR任务的调度公平。

SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先级任务到达或自己放弃。

如果有相同优先级的实时进程（根据优先级计算的调度权值是一样的）已经准备好，FIFO时必须等待该进程主动放弃后才可以运行这个优先级相同的任务。而RR可以让每个任务都执行一段时间。 相同点：

RR和FIFO都只用于实时任务。 创建时优先级大于0(1-99)。 按照可抢占优先级调度算法进行。 就绪态的实时任务立即抢占非实时任务。

所有任务都采用linux分时调度策略时。

1，创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。 2，将根据每个任务的nice值确定在cpu上的执行时间(counter)。 3，如果没有等待资源，则将该任务加入到就绪队列中。

4，调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这 个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。 5，此时调度程序重复上面计算过程，转到第4步。

6，当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。

所有任务都采用FIFO时，

1，创建进程时指定采用FIFO，并设置实时优先级rt_priority(1-99)。

2,如果没有等待资源，则将该任务加入到就绪队列中。

3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu，该FIFO任务将一直占有cpu直到有优先级更高的任务就绪(即使优先级相同也不行)或者主动放弃(等待资源)。

4，调度程序发现有优先级更高的任务到达(高优先级任务可能被中断或定时器任务唤醒，再或被当前运行的任务唤醒，等等)，则调度程序立即在当前任务 堆栈中保存当前cpu寄存器的所有数据，重新从高优先级任务的堆栈中加载寄存器数据到cpu，此时高优先级的任务开始运行。重复第3步。

5，如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪队列中删除，加入等待队列，此时重复第3步。

所有任务都采用RR调度策略时

1，创建任务时指定调度参数为RR，并设置任务的实时优先级和nice值(nice值将会转换为该任务的时间片的长度)。

2，如果没有等待资源，则将该任务加入到就绪队列中。

3，调度程序遍历就绪队列，根据实时优先级计算调度权值(1000+rt_priority),选择权值最高的任务使用cpu。

4，如果就绪队列中的RR任务时间片为0，则会根据nice值设置该任务的时间片，同时将该任务放入就绪队列的末尾。重复步骤3。

5，当前任务由于等待资源而主动退出cpu，则其加入等待队列中。重复步骤3。

系统中既有分时调度，又有时间片轮转调度和先进先出调度

1，RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。 2，当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。 3，RR进程和FIFO进程都采用实时优先级做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两个进程的优先级一样，则这两个优先 级一样的进程具体执行哪一个是由其在队列中的位置决定的，这样导致一些不公正性(优先级是一样的，为什么要让你一直运行?),如果将两个优先级一样的任务 的调度策略都设为RR,则保证了这两个任务可以循环执行，保证了公平。

调度？咋这熟悉，我们是不是常在哪里听到。没错，是的，调度我们时常听过，比如交通管制调度啦等。这不，夏天这热， 标语贴的好：相应国电电力调度，做文明市民,好别扭啊!不管了。你要是还是不懂，再啰嗦讲个事，过年回家，和漂亮的GF回家，为了张普通的硬座票还要排老久对，甚至还可能被坑拿到黄牛票，这时你嘴里咧咧的啥：XX,啥火车站，做的啥春运调度啊！唉，这次你说到点上了。

总结一下：调度就是通过调度程序的合理调度，实现系统资源的最大限度发挥作用。多

进程的并发正是这样的效果。其实原理一点也不复杂，道理也一样简单：只要又可以执行的进程，那么就总是会有进程正在执行。但简单的问题也会复杂化，比如：我们买票为啥抱怨调度，归根接地感谢当年的人海战术(多说一句，其实现实的很多问题，一个人海战术解决所有，这战术中国人用起来最得心应手)。好么，一般系统中进程的数目总会比处理器的个数多，所以竞争在所难免，调度的问题就集中在解决竞争的问题。

种类问题不多说：抢占和非抢占。linux提供了抢占式的多任务模式，下一阶段谁得到CPU的执行时间由调度程序决定。这怎么决定，是不是请个客，喝个酒啥的。对不起，linux无情的说，我是开源的，对所有人公平，哥不吃这一套。我有自己的一套原则(策略，这个我们待会儿再讲)。接着来术语，上面的过程叫做抢占，进程得到CPU的执行机会这段时间叫时间片，是由系统定义好的。后面我们会看到，linux调度程序采用动态方法计算时间片。说了抢占，再说说非抢占，就是说没人跟你抢，除非自己放弃，否则你自己运行下去吧。进程主动放弃挂起自己的行为叫让步。这种机制看似很和谐(不要被和谐哦)，但问题挺多，比如系统不知道每个进程执行多长时间。而且一旦一个悬挂进程不愿意或者忘了做出让步，那系统崩了咋办，我的money，我的future，我的lover，从此一去不复返。

说了那多，开始正题。原则，一切都有原则，linux的原则。开始原则以前，再来认识一下我们前边说过的进程，其实进程远不如以前那样简单。进程也有种类的，至少分为IO型和CPU型。IO型指那种大部分时间用来提交I/O请求或是等待I/O请求的进程。这样的进程挺讨人厌的，他通常都是运行一小小会儿，因为它总是在等待更多的I/O请求时最后总会阻塞。与之对应的则是CPU型进程。这样的进程把时间大多放在执行代码上，除非被抢占，他们就一直贪得无厌的运行。因为它们没有太多的IO请求。由于它们不是IO驱动类型，也就不存在用户交互的问题(IO驱动不仅仅指磁盘，还指键盘鼠标等)，所有从系统交互响应速度而言，调度器不应该经常让他们运行。即降低它们的运行频率，而将它们的运行时间拖长一些。这里所说的原则就是：调度策略要在进程响应迅速(相应时间短)和进程吞吐量高之间做出艰难的决定。这个原则有时不公平，很残酷。残酷的让人不懂，不懂低优先级的有时不能公平对待。由于交互式进程属于IO型进程，所以linux为了保证交互式应用，所以调度策略会向IO型进行倾斜。

上面提到优先级，调度算法中最基本的一类当然就是基于优先级的调度。挺简单：优先级高的先运行，相同优先级的按轮转式进行调度。优先级高的进程使用的时间片也长。调度程序总是选择时间片未用尽且优先级最高的进程运行。这句话就是说用户和系统可以通过设置进程的优先级来响应系统的调度。基于此，linux设计上一套动态优先级的调度方法。一开始，先为进程设置一个基本的优先级，然而它允许调度程序根据需要来加减优先级。linux内核提供了两组独立的优先级范围。第一种是nice值，范围从-20到19，默认为0.nice值越大优先级越小。另外nice值也用来决定分配给进程时间片的长短。第二种范围是实时优先级。默认范围是从0到99.任何实时的优先级都高于普通优先级。这个我们后面再说。 说了那么多的时间片，说起来不费劲，做起来那不是一个麻烦可以说清楚的。时间片就是一个数值，它表明进程在被抢占前所能持续运行的时间。默认的时间片是20ms，很短。linux调度程序还能根据进程的优先级动态调整分配给他的时间片。特别说明的是，进程不一定要一次用完所有分配给它的时间片。一旦进程的时间片耗尽后，就认为进程到期了。没有时间片的进程不会再投入运行。除非等到其他的进程都耗尽了它们的时间片，这时，所有进程的时间片就会被重新计算。

前边讲到了抢占的话题，当一个进程进入TASK_RUNNING状态时，内核就会检测它的优先级是否高于当前正在执行的进程。如果是，则调度程序会被唤醒，重新选择新的进程执行(套用书上的话， 应该是刚刚进入可运行状态的这个进程)。此外，当一个进程的时间片变为0时，它会被抢占，调度程序被唤醒以选择一个新的进程。(具体的例子大家可以看看参

考书籍的p28页3.1.5)

linux的调度程序定义于kernel/sched.c中，在2.6内核中的调度程序和以前有了很大的差别，体现在下面：

1.充分实现O(1)调度.这个应该懂得，可以懂的 2.在多核处理器的今天，linux也不落伍，全面实现SMP的扩展性。每个处理器拥有自己的锁和自己的可执行队列 3.强化SMP的亲和力。这是有关多核CPU亲和力的说明，我目前正在研究这个，后面我会专门在一篇博文中详细说明。 4.加强交互能力。 5.保证公平。 6.虽然最常见的优化情况是系统中只有1~2个可运行进程，但是优化也完全有能力扩展到具有多处理器且每个处理器上运行多个进程的系统中。 上面第二条可执行队列，它是调度程序中最基本的数据结构，定义于kernel/sched.c中，由结构runquene表示。它是给定处理器上的可执行进程的链表，每个处理器维护一个。每个可投入运行得进程都唯一的归属于一个可执行队列。此外，可执行队列中还包含每个处理器的调度信息。具体的结构这里就不给了，自己要有看源代码的能力哦。宏cpu_rq(processor)用于返回给定处理器可执行队列的指针，this_rq()用于来返回当前处理器的可执行队列，task_rq(task)返回给定任务所在的队列指针。 在其拥有者读取或改写其队列成员的时候，可执行队列包含的锁用来防止队列被其他代码改动，由于每个可执行队列唯一地对应一个处理器，所以很少出现一个处理器需要锁其他处理器的可执行队列的情况，但这种情况是事实存在的。最常见的情况是发生在一个特定的任务在运行队列上执行时。此时需要用到task_rq_lock()和task_rq_unlock()函数，或者可以用this_rq_lock()来锁住当前的可执行队列，用rq_unlock(struct runqueue *rq)释放给定队列上的锁。关于锁的操作，我们再次飘过，为啥？一方面，这超出了本节的重点，二者我在linux驱动理论帖中对加解锁做了详细说明，三者，我后面可能还会详细说。所以，那句话真是太真理了：暂时的放下，是再次的拿起。

从运行队列的结构中，我们发现了两个有关优先级的数组(定义在kernel/sched.c中，名字叫prio_array,具体自己去看吧)：活跃的和过去的。这两个数组是实现O(1)级算法的数据结构。优先级数组使可运行处理器的每一种优先级都包含一个相应的队列，而这些队列包含对应优先级上的可执行进程链表。结构中的优先级位图主要是为了帮助提高查找当前系统内拥有最高优先级的可执行进程的效率而设计的。关于结构中的定义常量，MAX_PRIO定义了系统拥有的优先级个数，默认值是140，BITMAP_SIZE是优先级位图数组的大小，值是5，这个是可以计算出来的。比如：位图数组的类型是unsigned long类型，长是32位，假定每一位代表一个优先级(4*32 = 128<140),就需要5个这样的长整型才能表示。所以，bitmap就正好含有5个数组项。

开始时，位图成员的所有位都被清0，当某一优先级的进程开始准备执行时，位图中对应的位就置1，这样，查找系统中最高的优先级就变成了查找位图中被设置的第一位。鉴于优先级个数的定值性，查找的时间就不受系统到底有多少可执行进程的影响，是个定值。关于对位图的快速查找算法对应的函数是sched_find_first_bit().

优先级数组的list_head队列是一个链表，这个链表包含了该处理器上相应优先级的全部可运行线程。要找到下一个要运行的任务，直接从该链表中选择下一个元素。对于给定的优先级，按轮转方式调度任务。优先级数组的计数器nr_active,它保存了该优先级数组内可执行进程的数目。

下一话题，我前边反复提到时间片的话题，一旦所有进程的时间片都用完会怎样了，

总不能系统宕掉吧，好在操作系统提供了一种显式的方法来重新计算每个进程的时间片。典型就是循环访问每个进程。借用书上的一个例子： for (系统中的每个任务)｛ 重新计算优先级 重新计算时间片 ｝ 这种方法简单，但弊端很多： 1.可能耗费相当长的时间。 2.为了保护任务队列和每个进程的描述符，必要要用到锁的机制。这样做很明显会加剧对锁的争用，影响系统性能。 3.重算时间片的时机不确定。 4.实现显得很粗糙。 现在采用的是新的调度方法，每个处理器拥有上面提到的两个优先级数组，活动数组上的进程都有时间片剩余，而过期数组中的进程都耗尽了时间片，当一个进程的时间片耗尽时，它会移至过期数组，但在此之前，时间片已经给它重新计算好了，重新计算时间片现在变的非常简单，只要在活动和过期数组之间来回切换就可以了。又因为数组是通过指针进行访问的，所以交换它们用的时间就是交换指针需要的时间。这个动作由schedule()完成： struct prio_array *array = rq->active; if(!array->nr_active){ rq->active = rq->expired; rq->expired = array; } 这种交换是O(1)级调度程序的核心。O(1)级调度程序根本不需要从头到尾都忙着重新计算时间片，它只要完成一个两个步骤就能实现数组的切换，这种实现完美地解决了前面列举的所有弊端。linux的调度程序是在schedule()函数实现的。当内核代码想要休眠时，会直接调用该函数，如果哪个进程将被抢占，也会被唤起执行。调度的第一步是判断谁是优先级最高的进程： struct task_struct *prev, *next; struct list_head *queue; struct prio_array array; int idx; prev = current; array = rq->active; idx = sched_find_first_bit(array->bitmpa); queue = array->queue + idx; next = list_entry(queue->next, struct task_struct, run_list); 分析上面这段代码，首先在活动优先级数组中找到第一个被设置的bit位，该位对应着最高的可执行进程。然后，调度程序选择这个级别链表里的头一个进程。这个进程就是系统中优先级最高的可执行程序，也是马上就会被调度执行的进程。上面中的prev和next不等，说明被选中的进程不是当前进程，这时就要调用context_switch来进程切换。最后强调一点，不存在任何影响schedule()时间长短的因素，因为前边说过，所用的时间是恒定的。

前边多次说过：调度程序是利用优先级和时间片来做出决定的。下边看看实际代码的实

现方式。进程结构体告诉我们进程拥有一个初始的优先级，叫做nice值，最低是19，最高是20，结构体的static_prio域就存放这个值，static就是说这个一开始就由用户指定好了，不能改变。调度程序要用的动态优先级用prio域表示，两者的关系在于通过一个关于静态优先级和进程交互性的函数计算而来。啥叫进程交互性？这是个新词，第一次提到，这样说吧，我们前边说过I/O消耗性和CPU消耗性的进程区别，进程交互性就是指IO消耗性的，因为和用户进行交互就是电脑IO和用户交互，像鼠标键盘等。但我们怎么确定一个进程的交互性的强弱呢？最明显的标准莫过于通过计算进程休眠的时间长短来做预测了。大部分时间都在休眠的进程当然是IO消耗型的，如果一个进程把所有的时间几乎都放在了CPU执行处理上，那..不说了。在linux中，用值tast_struct中的sleep_avg域记录了一个进程用于休眠和用于执行的时间，范围为0~MAX_SLEEP_AVG,默认值是10ms。当一个进程从休眠状态恢复到执行状态时，sleep_avg会根据它休眠时间的长短而增长直到最大。相反，进程没运行一个时钟节拍，sleep_avg就做相应的递减，到0为止。这种方法不仅会奖励交互性强的进程，还会惩罚处理器耗时量的进程。再加之奖励和处罚都是建立在作为基数的nice值上，所有用户仍然能够通过改变nice指来调整程序的调度。effective_prio()函数可以返回一个进程的动态优先数，该函数以nice值为基数，再加上我们上面提到的从-5到+5的进程交互性型奖励处罚分。

一旦有了上面的动态优先级，再来重新计算时间片就方便多了。另外，当一个进程创建的时候，新建的子进程和父进程均分父进程剩余的时间片。这样的分配很平均并且防止用户通过不断的创建新进程来不断攫取时间片。task_timeslice()函数为给定任务返回一个新的时间片，时间片的计算只需要把优先级按比例缩放，使其符合时间片的数值范围要求就可以了。优先级最高的进程能获得的最大时间片长度(MAX_TIMESLICE)是200ms，最短时间片(MIN_TIMESLICE)是10ms。默认优先级(nice值为0，没有交互性奖罚分)的进程得到的时间片长度为100ms。上面我们也提到过，活动数组内的可执行队列上的进程的时间片耗尽时，它就会移植到过期数组。但是，如果一个进程的交互性很强，特别特别强，那么调度程序支持另外一种机制来支持这种交互进程：当时间片用完后，它会被再放置到活动数组而不是过期数组中。回忆一下上面O(1)调度器的实现机制：进程用尽其时间片后，都会被移动到过期数组，当活动数组中没有剩余进程的时候，这个时候两个数组就会被交换。但是在发生这种交换以前，交互性很强的一个进程有可能已经处于过期数组中了，当他需要交互的时候，这时可能数组交互还没有发生，所以交互也就无法进行，这时对于这种交互特别特别强的进程重新插入到活动数组就可以避免这种问题。注意，虽然被放回到活动数组，但不会立即就运行，它还要和其他具有相同优先级的进程轮流运行。该逻辑在scheduler_tick()中实现，该函数会被定时器中断调用。看下面的实现代码： struct task_struct *task = current; struct runqueue *rq = this_rq(); if(!—task->time_slice){ if(!TASK_INTERACTIVE(task) || (EXPIRED_STARVING(rq))) enqueue_task(task, rq->expired); else enqueue_task(task, rq->active); } 这段代码先减少进程时间片的值。宏TASK_INTERACTIVE主要是基于进程的nice值来查看这个进程是否是交互性很强的进程。宏EXPIRED_STARVING负责检查过期数组内的进程是否处于饥饿状态，是否有相当长的时间没有发生数组交换了。如果最近一直没有发生切换，那么再把当前的进程放置到活动数组会进一步拖延切换--过期数组内的进程会来越来越饿.

只要不发生这种情况，进程就会被重新设置在活动数组里，否则，进程会被放入过期数组里。 有关休眠我就不用多讲了。内核对休眠的处理都相同：进程把自己标记成休眠状态，然后将自己从可执行队列移出，放入等待队列，然后调用schedule()选择和执行一个其他进程，唤醒的过程刚好相反。要明白一点就是：即使休眠也有两种进程状态，TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE.前者如果接收到一个信号会被提前唤醒并响应该信号，后者会忽略信号。这两种进程位于同一等待队列(wake_queue_head_t)上，等待某些事情，不能够运行。有关等待队列的知识，跳过(我已经在Linux驱动开发理论帖里讲过，自己去看吧)现在，在内核中进行休眠的推荐操作相比较以前而言复杂了很多，但更安全：

1.调用DECLARE_WAITQUEUE() 创建一个等待队列的项。 2.调用add_wait_queue()把自己加入到等带对列中。 3.将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE. 4.检查条件是否为真，如果是的话，就没必要休眠了。不为真，就调用schedule(). 5.当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环，如果不是，它再次调用schedule()并一直重复这步操作。 6.当条件满足后，进程将自己设置为TASK_RUNNING并调用remove_wait_queue把自己移出等待队列。 如果在进程开始休眠之前条件就已经达成了，那么循环会退出，进程不会存在错误的进入休眠的倾向。有休眠就有唤醒，唤醒是通过wake_up()进行。她唤醒指定的等待队列上的所有进程。它调用try_to_wake_up,该函数负责将进程设置为TASK_RUNNING状态，调用active_task()将此进程放入可执行队列，如果被唤醒进程的优先级比当前正在执行的进程的优先级高，还要设置need_resched标志。编程的技巧，通常哪段代码促使等待条件达成，它就要负责随后调用wake_up函数。说明：存在虚假的唤醒，有时候进程被唤醒并不是因为它所等待的条件达成了，所以才需要用一个循环处理来保证它等待的条件真正到达。 开始新的问题，现在市场上，你说单核CPU，你都没脸见人，现在是啥时代，多核的时代，瞧，我这都酷睿i7了(四核)，我用的服务器实验平台是8核心的。和我有啥关系，和我今天讲的有啥关系。关系大了去了。前边提到过，linux的调度程序为对称多处理器系统的每个处理器准备了单独的可执行队列和锁，出于效率的考虑，整个调度系统从每个处理器来看都是独立的。那么这样的情况咋办呢？一个处理器上有5个进程，另外一个处理器的队列上只有一个进程，这时很明显出现了系统负载不均衡的情况。这时咋办呢？由负载均衡程序来解决(kernel/sched.c的load_balance来实现)。它有两种调用方法，在schedule执行的时候，只要当前的可执行对列为空，它就会被调用。此外，它也会被定时器调用，系统空闲时每隔1ms调用一次或者在其他情况下每隔200ms调用一次。单系统中，它不会被调用，甚至不会被编译进内核，因为那里边只有一个可执行队列，根本没有平衡负载的必要。load_balances调用时需要锁住当前处理器的可执行队列并且屏蔽中断，以避免可执行队列被并发的访问，所完成的操作步骤如下所示：

1.load_balance()调用find_busiest_queue(),找到最繁忙的可执行队列(进程数目最多)并返回该队列。如果没有哪个可执行队列中进程的数 目比当前队列中的数目多25%或25%以上。它就返回NULL,同时load_balance也返回。 2.load_balance从最繁忙的运行队列中选择一个优先级数组以便抽取进程。最好是过期数组，如果过期数组为空，那就只能选活动数组。 3.load_balance寻找到含有进程并且优先级最高的链表，因为把优先级高的进程分散开来才是最重要的。 4.分析找到的所有这些优先级相同的进程，这样一个不是正在执行，也不会因为处理器相关性而不可移动，并且不在高速缓存中的进程。如 果有，就调用pull_task将其从最繁忙的队列中抽取到当前队列 5.只要可执行队列之间仍然不平衡，就重复上面两个步骤，这最终会消除不平衡。然后解除对当前运行队列进行的锁定，从load_balance返 回。 我们后面会提到的上下文切换，就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c的context_switch函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule就会调用该函数。它主要完成如下两个工作： 1.调用定义在include/asm/mmu_context.h中的switch_mm().该函数负责把虚拟内存从上一个进程映射切换到新进程中。 2.调用定义在include/asm/system.h的switch_to(),该函数负责从上一个进程的处理器状态切换到新进程的处理器状态，这包括保存，恢复 栈信息和寄存器信息。 内核也必须知道什么时候调用schedule(),单靠用户代码显示调用schedule(),他们可能就会永远地执行下去，相反，内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志，当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。下表给出了用于访问和操作need_resched的函数。 函数 set_tsk_need_resched(task) clear_tsk_need_resched(task) need_resched() 说明 设置指定进程中的need_resched标志 清除指定进程中的nedd_resched标志 检查need_resched标志的值，如果被设置就返回真，否则返回假 再返回用户空间以及从中断返回的时候，内核也会检查need_resched标志，如果已被设置，内核会在继续执行之前调用该调度程序。最后，每个进程都包含一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量要快(因为current宏速度很快并且描述符通常都在高速缓存中)。在2.6内核中，他被移到了thread_info结构体里，这是和以前不同的。

抢占，还是抢占！我们总是逃不了抢占的话题。内核放回到用户空间的时候，如果need_resched标志被设置，就会导致schedule()被调用。简儿言之，用户抢占在以下情况下发生：从系统调用返回到用户空间和从中断处理程序返回用户空间。

在linux2.6内核中，内核引入了抢占内力。为了支持内核抢占所做的第一个变动就是为每个进程的thread_info引入preempt_count计数器，该计数器初始为0，每当使用锁的时候，该值减1。当为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值，如果need_resched被设置，并且preempt_count为0的时候，这说明有一个更重要的任务需要执行并且安全地抢占，此时，调度程序就会被调度。如果，preempt_count不为0，说明当前任务持有锁，这时抢占是不安全的。这时，就会想通常那样直接从中断返回当前执行进程。如果当前进程持有的锁都被释放了，那么preempt_count就会重新为0。此时，释放锁的代码会检查need_sheduled是否被设置，如

果是的话，就会调用调度程序，有些内核需要允许或禁止内核抢占，这个后面具体问题具体分析。如果内核中的进程阻塞了，或它显示地调用了schedule(),内核抢占也会显示地发生，这种形式的内核抢占从来都是支持的，因为根本无需额外的逻辑来保证内核可以安全地被抢占，如果代码显示的调用了schedule(),那么它清楚自己是可以安全地被强化的。

我们前边讲的是普通的，非实时的调度策略(SCHED_OTHER),Linux也支持两种实时调度策略(SCHED_FIFO和SCHED_RR).SCHED_FIFO从名字中我们也知道，就不说了。它不使用时间片。该级的进程会比任何SCHED_OTHER级的进程都先得到调度。一旦一个SCHED_FIFO级进程处理可执行状态，就会一直执行，直到它自己被阻塞或是显示地释放处理器为止。由于不基于时间片，所以它会一直执行下去。多个SCHED_FIFO级进程存在时，他们会轮流执行。而且只要有SCHED_FIFO级的进程存在，普通级进程级只能等待它结束后才有机会执行。SCHED_RR是一种带有时间片的SCHED_FIFO。以上两种实时调度算法实现都是静态优先级的。内核不为实时进程计算动态优先级。这样就能保证给定优先级级别的实时进程总能抢占优先级比它低的进程。

linux的实时调度算法分为软实时和硬实时。软实时的含义是，内核调度进程尽可能使进程在它的限定时间到来前执行，但内核不会拍着胸脯说：我一定能保证。对应地，硬实时会这样哥们义气哦。linux下的实时调度不做任何保证，只保证只要实时进程可执行，就尽量去执行它。现在开来，效果还是不错的。

实时优先级范围从0~MAX_RT_PRIO-1.默认情况下，MAX_RT_PRIO为100.SCHED_OTHER级进程的nice值共享了这个取值空间。它的取值范围是从MAX_RT_PRIO到MAX_RT_PRIO+40.也就是说，nice值从-20到+19对应的是从100到140的实时优先级范围。

linux内核调度算法（1）--快速找到最高优先级进程 为什么要了解内核的调度策略呢？呵呵，因为它值得我们学习，不算是废话吧。内核调度程序很先进很强大，管理你的LINUX上跑的大量的乱七八糟的进程，同时还保持着对用户操作的高灵敏响应，如果可能，为什么不把这种思想放到自己的应用程序里呢？或者，有没有可能更好的实现自己的应用，使得操作系统能够以自己的意志来分配资源给自己的进程？

带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序，基本上就两种类型，1、IO消耗型：比如hadoop上的trunk服务，很明显它的消耗主要在IO上，包括网络IO磁盘IO等等。2、CPU消耗型，比如mapreduce或者其他的需要对大量数据进行计算处理的组件，就象对高清视频压缩成适合手机观看分辨率的进程，他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时，操作系统会如何调度它们呢？现在的服务器都是SMP多核的，那么一个进程在多CPU时会来回切换吗？如果我有一个程序，既有IO消耗又有CPU消耗，怎么让多核更好的调度我的程序呢？

又多了几个问题。来看看内核调度程序吧，我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。

首先看下面的优先级队列，每一个runqueue都有。runqueue是什么？下面会详细说下，现在大家可以理解为，内核为每一颗CPU分配了一个runqueue，用于维护这颗CPU可以

运行的进程。runqueue里，有几个成员是prio_array类型，这个东东就是优先队列，先看看它的定义：

[cpp] view plaincopy

1. struct prio_array {

2. unsigned int nr_active; 表示等待执行的进程总数

3. unsigned long bitmap[BITMAP_SIZE]; 一个unsigned long在内核中只有32位

哈，大家要跟64位OS上的C程序中的long区分开，那个是64位的。那么这个bitmap是干什么的呢？它是用位的方式，表示某个优先级上有没有待处理的队列，是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级，我只需要四位就能表示某个优先级上有没有进程要运行，例如优先级是2和3上有进程，那么就应该是0110.......非常省空间，效率也快，不是吗？

4. struct list_head queue[MAX_PRIO]; 与上面的bitmap是对应的，它存储所有等

待运行的进程。 5. };

看看BITMAP_SIZE是怎么算出来的：#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

那么，LINUX默认配置（如果你用默认选项编译内核的话）MAX_PRIO是140，就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中，可能包含许多种优先级的进程，但，LINUX是个抢占式调度算法的操作系统，就是说，需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5，那么bitmap实际是32*5=160位，这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的？看2649行代码：idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计：

[cpp] view plaincopy

1. static inline int sched_find_first_bit(unsigned long *b) 2. {

3. if (unlikely(b[0])) 4. return __ffs(b[0]); 5. if (unlikely(b[1]))

6. return __ffs(b[1]) + 32; 7. if (unlikely(b[2]))

8. return __ffs(b[2]) + 64; 9. if (b[3])

10. return __ffs(b[3]) + 96; 11. return __ffs(b[4]) + 128; 12. }

那么__ffs是干什么的？

[cpp] view plaincopy

1. static inline int __ffs(int x) 2. {

3. int r = 0; 4.

5. if (!x) 6. return 0; 7. if (!(x & 0xffff)) { 8. x >>= 16; 9. r += 16; 10. }

11. if (!(x & 0xff)) { 12. x >>= 8; 13. r += 8; 14. }

15. if (!(x & 0xf)) { 16. x >>= 4; 17. r += 4; 18. }

19. if (!(x & 3)) { 20. x >>= 2; 21. r += 2; 22. }

23. if (!(x & 1)) { 24. x >>= 1; 25. r += 1; 26. }

27. return r; 28. }

sched_find_first_bit返回值就是最高优先级所在队列的序号，与queue是对应使用的哈，queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的，非常值得我们学习。

好，优先级队列搞明白了，现在来看看runqueue，每个runqueue包含三个优先级队列。

[cpp] view plaincopy

1. struct runqueue {

2. spinlock_t lock; 这是个自旋锁，nginx里解决惊群现象时也是用这个。与普通锁的

区别就是，使用普通锁时，你去试图拿一把锁，结果发现已经被别人拿走了，你就在那睡觉，等别人锁用完了叫你起来。所以如果有一个人拿住锁了，一百个人都在门前睡觉等。当之前的人用完锁回来后，会叫醒所有100个等锁的人，然后这些人开始互相抢，抢到的人拿锁进去，其他的人继续等。自旋锁不同，当他去拿锁发现锁被别人拿走了，他在那不睡觉的等，稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗？

本文来源：https://www.bwwdw.com/article/u4b7.html