kk Blog —— 通用基础

软中断分析

1. 为什么要软中断

编写驱动的时候，一个中断产生之后，内核在中断处理函数中可能需要完成很多工作。但是中断处理函数的处理是关闭了中断的。也就是说在响应中断时，系统不能再次响应外部的其它中断。这样的后果会造成有可能丢失外部中断。于是，linux内核设计出了一种架构，中断函数需要处理的任务分为两部分，一部分在中断处理函数中执行，这时系统关闭中断。另外一部分在软件中断中执行，这个时候开启中断，系统可以响应外部中断。

关于软件中断的理论各种书籍都有介绍，不多叙述。而要真正体会软件中断的作用就必须从代码的角度来分析。我们做工作时候讲求的是professional，当一个人在某个领域一无所知的时候，我们称他为小白，偶，非苹果电脑。小白的脑子里充满了各种问题。慢慢的当这些疑惑解释完之后，小白就脱白了。此时，我们对这个领域的基本框架有了解，但这和professional还有一定的差距。再加以时日，逐渐融会贯通该领域才能达到专业的境界。

2. 什么时候触发处理软件中断

说了这么多废话，赶快步入正题。初识软中断，脑子里肯定有不少的疑问，首先就是软件中断在什么地方被触发处理？这个问题的答案就是：一个硬件中断处理完成之后。下面的函数在处理完硬件中断之后推出中断处理函数，在irq_exit中会触发软件中断的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

asmlinkage void __exception asm_do_IRQ(unsigned int irq, struct pt_regs *regs)
{
	struct pt_regs *old_regs = set_irq_regs(regs);
 
	irq_enter();
 
	/*
	 * Some hardware gives randomly wrong interrupts.  Rather
	 * than crashing, do something sensible.
	 */ 
	if (irq >= NR_IRQS)
	    handle_bad_irq(irq, &bad_irq_desc);
	else 
	    generic_handle_irq(irq);
 
	/* AT91 specific workaround */ 
	irq_finish(irq);
 
	irq_exit();
	set_irq_regs(old_regs);
}

这里要注意，invoke_softirq必须满足两个条件才能被调用到，一个就是不是在硬件中断处理过程中或者在软件中断处理中，第二个就是必须有软件中断处于pending状态。第二个好理解，有软件中断产生才去处理，没有就不处理。第一个就不好理解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

/*
* Exit an interrupt context. Process softirqs if needed and possible:
*/ 
void irq_exit(void)
{
	account_system_vtime(current);
	trace_hardirq_exit();
	sub_preempt_count(IRQ_EXIT_OFFSET);
	if (!in_interrupt() && local_softirq_pending())
	    invoke_softirq();
 
#ifdef CONFIG_NO_HZ
	/* Make sure that timer wheel updates are propagated */ 
	rcu_irq_exit();
	if (idle_cpu(smp_processor_id()) && !in_interrupt() && !need_resched())
	    tick_nohz_stop_sched_tick(0);
#endif 
	preempt_enable_no_resched();
}

在linux系统的进程数据结构里，有这么一个数据结构

1

#define preempt_count() (current_thread_info()->preempt_count)，

利用preempt_count可以表示是否处于中断处理或者软件中断处理过程中。

1
2
3
4
5
6
7
8
9
10
11
12
13

#define PREEMPT_MASK    (__IRQ_MASK(PREEMPT_BITS) << PREEMPT_SHIFT)
#define SOFTIRQ_MASK    (__IRQ_MASK(SOFTIRQ_BITS) << SOFTIRQ_SHIFT)
#define HARDIRQ_MASK    (__IRQ_MASK(HARDIRQ_BITS) << HARDIRQ_SHIFT)
 
#define PREEMPT_OFFSET    (1UL << PREEMPT_SHIFT)
#define SOFTIRQ_OFFSET    (1UL << SOFTIRQ_SHIFT)
#define HARDIRQ_OFFSET    (1UL << HARDIRQ_SHIFT)

sub_preempt_count(IRQ_EXIT_OFFSET);

#define in_interrupt() (irq_count())

#define irq_count() (preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK))

preempt_count的8～23位记录中断处理和软件中断处理过程的计数。如果有计数，表示系统在硬件中断或者软件中断处理过程中。系统这么设计是为了避免软件中断在中断嵌套中被调用，并且达到在单个CPU上软件中断不能被重入的目的。对于ARM架构的CPU不存在中断嵌套中调用软件中断的问题，因为ARM架构的CPU在处理硬件中断的过程中是关闭掉中断的。只有在进入了软中断处理过程中之后才会开启硬件中断，如果在软件中断处理过程中有硬件中断嵌套，也不会再次调用软中断，because硬件中断是软件中断处理过程中再次进入的，此时preempt_count已经记录了软件中断！对于其它架构的CPU，有可能在触发调用软件中断前，也就是还在处理硬件中断的时候，就已经开启了硬件中断，可能会发生中断嵌套，在中断嵌套中是不允许调用软件中断处理的。Why？我的理解是，在发生中断嵌套的时候，表明这个时候是系统突发繁忙的时候，内核第一要务就是赶紧把中断中的事情处理完成，退出中断嵌套。避免多次嵌套，哪里有时间处理软件中断，所以把软件中断推迟到了所有中断处理完成的时候才能触发软件中断。

3. 软件中断的处理过程

之前我已经说到，软中断的一个很大的目的就是避免中断处理中，处理的操作过多而丢失中断。同时中断还需要考虑到一件事情就是中断处理过程过长就会影响系统响应时间。如果一个中断处理一秒钟，那你一定能感受到串口卡住的现象。从另外一方面说呢，我们又必须考虑中断处理的操作一定的优先度，毕竟是硬件触发的事务，关系到网络、块设备的效率问题。Linux内核就中断方面就必须考虑平衡这三个方面的问题。而下面我要分析的__do_softirq函数就恰似在这三者之间打太极，游刃有余，面面俱到！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/*
* We restart softirq processing MAX_SOFTIRQ_RESTART times,
* and we fall back to softirqd after that.
*
* This number has been established via experimentation.
* The two things to balance is latency against fairness -
* we want to handle softirqs as soon as possible, but they
* should not be able to lock up the box.
*/ 
#define MAX_SOFTIRQ_RESTART 10 
 
asmlinkage void __do_softirq(void)
{
	struct softirq_action *h;
	__u32 pending;
	int max_restart = MAX_SOFTIRQ_RESTART;
	int cpu;
 
	pending = local_softirq_pending();
	account_system_vtime(current);
 
	__local_bh_disable((unsigned long)__builtin_return_address(0));
	trace_softirq_enter();
 
	cpu = smp_processor_id();
restart:
	/* Reset the pending bitmask before enabling irqs */ 
	set_softirq_pending(0);
 
	local_irq_enable();
 
	h = softirq_vec;
 
	do 
	{
	    if (pending & 1)
	    {
	        int prev_count = preempt_count();
 
	        h->action(h);
 
	        if (unlikely(prev_count != preempt_count()))
	        {
	            printk(KERN_ERR "huh, entered softirq %td %p" 
	                   "with preempt_count %08x," 
	                   " exited with %08x?\n", h - softirq_vec,
	                   h->action, prev_count, preempt_count());
	            preempt_count() = prev_count;
	        }
 
	        rcu_bh_qsctr_inc(cpu);
	    }
	    h++;
	    pending >>= 1;
	}
	while (pending);
 
	local_irq_disable();
 
	pending = local_softirq_pending();
	if (pending && --max_restart)
	    goto restart;
 
	if (pending)
	    wakeup_softirqd();
 
	trace_softirq_exit();
 
	account_system_vtime(current);
	_local_bh_enable();
}

__do_softirq函数处理软件中断过程如下图流程分析

1. 首先调用local_softirq_pending函数取得目前有哪些位存在软件中断

2. 调用local_bh_disable关闭软中断，其实就是设置正在处理软件中断标记，在同一个CPU上使得不能重入do_softirq函数

3. 重新设置软中断标记为0，set_softirq_pending重新设置软中断标记为0，这样在之后重新开启中断之后硬件中断中又可以设置软件中断位。

4. 开启硬件中断

5. 之后在一个循环中，遍历pending标志的每一位，如果这一位设置就会调用软件中断的处理函数。在这个过程中硬件中断是开启的，随时可以打断软件中断。这样保证硬件中断不会丢失。

6. 之后关闭硬件中断，查看是否又有软件中断处于pending状态，如果是，并且在本次调用__do_softirq函数过程中没有累计重复进入软件中断处理的次数超过10次，就可以重新调用软件中断处理。如果超过了10次，就调用wakeup_softirqd();唤醒内核的一个进程来处理软件中断。设立10次的限制，也是为了避免影响系统响应时间。

4. 处理软中断内核线程

之前我说到不能让CPU长时间来处理中断事务，这样会影响系统的响应时间，严重影响用户和系统之间的交互式体验。所以在之前的__do_softirq中最多将循环执行10次，那么当执行了10次仍然有软中断在pending状态，这个时候应该怎么处理呢？系统将唤醒一个软件中断处理的内核进程，在内核进程中处理pending中的软件中断。这里要注意，之前我们分析的触发软件中断的位置其实是中断上下文中，而在软中断的内核线程中实际已经是进程的上下文。

这里说的软中断上下文指的就是系统为每个CPU建立的ksoftirqd进程。

看完这个函数，我不得不佩服这个函数设计的精巧！而我更多的从中体会到其中蕴藏的一种做人的道理。那就是做人要霸道一点，太谦和太恭维不行，但是又不能横行霸道，原则的问题要公平讲理，一定的时候顾及别人的利益，好处不能一个人独吞。这就跟下面ksoftirqd处理过程一样，该狠的时候禁止抢占，其它进程别想调度到哦，但是自己占用CPU时间过长的话，也自觉的问一问是不是该释放CPU给其它进程了。

下面我们就来分析一下这个处理过程怎么就体现了上面的这种说法呢？软中断的内核进程中主要有两个大循环，外层的循环处理有软件中断就处理，没有软件中断就休眠。内层的循环处理软件中断，并每循环一次都试探一次是否过长时间占据了CPU，需要调度释放CPU给其它进程。具体的操作在注释中做了解释。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

static int ksoftirqd(void *__bind_cpu)
{
	set_current_state(TASK_INTERRUPTIBLE);
 
	while (!kthread_should_stop())
	{
	    /*不管三七二十一首先禁止抢占，我掌握CPU，并全凭我自己掌握调度*/ 
	    preempt_disable();
	    if (!local_softirq_pending())
	    {
	        preempt_enable_no_resched();
	        /*如果没有软中断在pending，那就让出CPU来吧*/ 
	        schedule();
	       /*我被唤醒了，首先掌握CPU，不让自己被抢占，自己决定自己的是否要调度*/ 
	        preempt_disable();
	    }
 
	    __set_current_state(TASK_RUNNING);
 
	    while (local_softirq_pending())
	    {
	        /* Preempt disable stops cpu going offline.
	           If already offline, we'll be on wrong CPU:
	           don't process */ 
	        if (cpu_is_offline((long)__bind_cpu))
	            goto wait_to_die;
	        /*处理软中断*/ 
	        do_softirq();
	        /*虽然我自己掌握是否要调度，虽然我可以一直不调度，但是我是
	        个正直的人，运行一段时间后我会看看是否需要调度，还其它进程运行*/ 
	        preempt_enable_no_resched();
	        cond_resched();
	        preempt_disable();
	        rcu_qsctr_inc((long)__bind_cpu);
	    }
	    preempt_enable();
	    set_current_state(TASK_INTERRUPTIBLE);
	}
	__set_current_state(TASK_RUNNING);
	return 0;
 
wait_to_die:
	preempt_enable();
	/* Wait for kthread_stop */ 
	set_current_state(TASK_INTERRUPTIBLE);
	while (!kthread_should_stop())
	{
	    schedule();
	    set_current_state(TASK_INTERRUPTIBLE);
	}
	__set_current_state(TASK_RUNNING);
	return 0;
}

1、

cpu的中断管理和指令执行（运算器）是两套硬件，他们互相独立又有关联。

2、

无论中断是否允许，运算器都按自己的节奏工作，无须花时间去查询是否由中断到达。

3、

中断管理器则不断地探测是否有中断信号到达，若有且中断允许，则保存当前执行状态信息，然后打断当前取指序列，强行转到特定地址（中断向量）取指令，整个过程运算器并不知道，它只是忠实地执行取指电路取得的指令。
因此，只要没有中断信号到达，就不存在cpu边走边看的问题。 为保证正确访问临界数据区和正确执行临界代码段，操作系统一般有：关中断、关调度、信号量，还有些操作系统提供原子变量的方法，linux中广为人知的锁其实是用信号量实现的。那么，这么多的方法中，什么情况适用哪一种方法呢？是有规律的。

1、原子变量

原子变量可以保证一个变量单次操作的正确性，其保护甚至比信号量还完善，信号量只能保护全局数据不被其他线程破坏，而原子变量能保证全局数据不被中断破坏。

1
2
3
4

example1：
	atomic int a;
int b,c;
a = a + b + c;

上述代码中，cpu对a有一个读、修改、写的过程，这个过程如果被打断，并在其他线程中修改了a值，执行结果将出现错误，而原子变量将保证不会发生这样的错误。 原子变量不能保护一系列操作的原子性，若把上述代码改为

1
2
3
4
5

example2：
atomic int a;
int b,c;
a = a + b; //L1
a = a + c; //L2

原子变量不能保证L1和L2两行程序间a不被其他线程修改，因此example2不一定能得到正确的结果。

2、信号量

稍微完善一点的操作系统都提供信号量机制，用于保护临界代码。上述example2就应该用下列代码替代L1和L2：

1
2
3
4

获取信号量；
a = a + b; //L1
a = a + c; //L2
释放信号量；

当一个全局变量可能被多个线程操作时，就应该用信号量保护，注意，不能在中断中访问用信号量保护的变量。

3、关调度

关调度是一种比较粗暴的方式，关调度后，操作系统不会再进行线程上下文切换，而是专心执行一个线程，但是中断仍然开着。关调度可以起到替代信号量保护全局变量的作用，但一般不这样用，太粗暴了。但是如果某一段代码的执行时间有要求，希望cpu全速执行不被打断，但又不希望关中断时，可用关调度的方法。注意，从逻辑上，关调度能替换信号量，但不能替换原子变量。

4、关中断

关中断是最粗暴的一种方式，用于保证最严格的时序执行，比如某段代码要在IO上输出两个高精度脉冲，脉冲宽度2uS，间隔2uS，这种需求只能通过用精确的指令延时来实现，延时过程中，如果被中断，或者发生线程切换，将不能正确输出脉冲。从逻辑上，前面所讲的三种保护，都可以用关中断实现，只是，太粗暴了。

http://blog.csdn.net/cybertan/article/details/5686451

调度

公平调度 (fair-share scheduling) 的进程调度算法：

一、公平分享的调度策略

Linux 的调度算法是相对独立的一个模块，而且较容易理解。因此很多系统高手都爱对调度算法做改进。但是可以说调度器是一个非常神秘，难以捉摸的精灵。可能通过改变一个关键参数你就可以大大提高系统的效率。
对于一般进程， CPU 的使用时间都是系统平均分配给每一个进程的，因此这种公平分享都是从 进程的角度 出发的。 Bach 在 1986 年提出了公平分享调度策略（ Fair_Share scheduling ）来解决这个问题。和 Linux 三种内建策略比，公平分享调度策略是一种更抽象的调度策略。它认为 CPU 应该根据拥有进程的组（对 Linux 来说是用户）来分配时间，它实现了从 用户角度 考虑的公平原则。

由内核的结构来看，实现这个算法有很多种方式。我们可以在与调度相关的程序里做小小的改动来实现，如改动一些数据结构并改写 schedule() 函数。当然也可以做得很复杂，比如重写 schedule() 来实现所需要的结果。但是有一点我们是要必须牢记的，那就是大部分的 Linux 核心都是以短小高效为最高目标。所以，改进的算法必须尽量向这个目标靠拢。

二、新调度策略的实现：分析

1 、这里所说的 ‘ 组 ’ 的概念，在 Linux 中是一个用户。我们所关心的是 Linux 的用户，而不是 UNIX 系统下的用户组或是别的什么概念。因此 在公平共享调度策略中，一个进程能够分配到的时间与登录的系统用户数以及拥有该进程用户开辟进程数的多少有关。
2 、超级用户的进程是 独立于公平分享算法 的，因此它拥有的进程得到的调度时间应该和现在的进程调度算法分配时间相当。
3 、对于实时进程，调度算法仍旧给予比普通进程更高的优先权。不过也不用担心会花太多的时间去实现，只要在现在调度算法的基础上稍做改进就可以简单实现。
4 、新的调度算法对系统的吞吐量不能有太多的影响。比如说，如果定义的时间片少于 2 个 “ 滴答 ” ，那么新实现的调度器效率将变得很差。因为过于频繁的进程切换将耗费大部分的系统时间，而真正用于程序计算的时间则排在第二位了。 此条说明时间片的划分不能太小。
5 、我们所实现的算法并不需要绝对的公平，严格的平均是需要用效率为代价来换取的。如果算法过于精确，那就需要复杂的数据结构和耗时的计算过程，所以我们可以在以速度为第一原则的基础上实现 “ 模糊 ” 的公平分享。
6 、我们首先需要的是不断地思考和设计，只有将所有的问题都考虑清楚以后才可以开始动手。调度器是操作系统的核心，它将被频繁调用，因此其作用和影响也将是巨大的。我们要花费最小的代价实现算法，并且这种改动对系统核心的影响要降到最小。

Linux 的进程调度机制：

概述：
在多进程的操作系统中，进程调度是一个全局性的、关键性的问题。可以说，关于进程调度的研究是整个操作系统理论的核心，它对系统的总体设计、系统的实现、功能设置以及各方面的性能都有着决定性的影响。

1、 150ms ：当系统中有大量进程共存时，根据测定，当每个用户可以接受的相应速度延迟超过１５０ ms 时，使用者就会明显地感觉到了。

2、 在设计一个进程调度机制时要考虑的具体问题主要有：

调度的时机：什么情况下、什么时候进行调度；
调度的政策：根据什么准则挑选下一个进入运行的进程；
调度的方式：是 “ 可剥夺 ” 还是 “ 不可剥夺 ” 。当正在运行的进程并不自愿暂时放弃对ＣＰＵ的使用权时，是否可以强制性地暂时剥夺其使用权，停止其运行而给其他进程一个机会。如果是可剥夺的，那么是否在任何条件下都可剥夺，有没有例外？

3、linux 内核的调度机制：

１）调度的时机：

• 首先，自愿的调度 ( 主动调度 ) 随时都可以进行：在内核里面，一个进程可以通过 schedule() 启动一次调度。也就是由当前进程自愿调用 schedule() 暂时放弃运行的情景。
• 除此之外，调度还可以非自愿的，即强制地发生在每次从系统调用返回的前夕，以及每次从中断或者异常处理 返回到用户空间 的前夕。

上述红字说明：只有在用户空间（当ＣＰＵ在用户空间运行时）发生的中断或者异常才会引起调度。

1
2
3
4
5
6
7
8
9
10
11
12

ret_from_exception:
	movl SYMBOL_NAME(bh_mask),%eax
	andl SYMBOL_NAME(bh_active),%eax
	jne handle_bottom_half
	ALIGN
ret_from_intr:
	GET_CURRENT(%ebx)
	movl EFLAGS(%esp),%eax        # mix EFLAGS and CS
	movb CS(%esp),%al
	testl $(VM_MASK | 3),%eax    # return to VM86 mode or non-supervisor?
	jne ret_with_reschedule
	jmp restore_all

　　 从上述代码中 (arch/i386/kernel/entry.S) ，可以看出，转入 ret_with_reschedule 的条件为中断或异常发生前 CPU 的运行级别为３，即用户态。

这一点 ( 只有在用户空间发生的中断或者异常才会引起调度 ) 对于系统的设计和实现有很重要的意义：因为这意味着当 CPU 在内核中运行时无需考虑强制调度的可能性。发生在系统空间中的中断或异常当然是可能的，但是这种中断或者异常不会引起调度。这使得内核的实现简化了，早期的 Unix 内核正是靠这个前提来简化其设计与实现的。否则的话，内核中所有可能为一个以上进程共享的变量和数据结构就全都要通过互斥机制 ( 如信号量 ) 加以保护，或者说放在临界区里面。即在内核中由于不会发生调度而无需考虑互斥。但是在多处理器 SMP 系统中，这种简化正在失去重要性：因为我们不得不考虑在另一个处理器上运行的进程访问共享资源的可能性。这样，不管在同一个 CPU 上是否可能在内核中发生调度，所有可能为多个进程 ( 可能在不同的 CPU 上运行 ) 共享的变量和数据结构，都得保护起来。这就是为什么读者在阅读代码时看到那么多的 up() 、 down() 等信号量操作或者加锁操作的原因。

注意： “ 从系统空间返回到用户空间 ” 只是发生调度的必要条件，而不是充分条件。也就是说，这个条件满足了，调度并不是一定会发生的，具体是否发生调度还要判断当前进程的 task_struct 结构中的 need_resched 成员是否为非０，非０时才会转到 reschedule 处调用 schedule():

1
2
3
4
5
6
7
8
9

 ret_with_reschedule:
	cmpl $0, need_resched(%ebx)
	jne reschedule
	cmpl $0,sigpending(%ebx)
	jne signal_return
....
 reschedule:
	call SYMBOL_NAME( schedule )    # test
	jmp ret_from_sys_call

need_resched 成员是内核设置的，因为在用户空间是访问不到进程的 task_struct 结构的。除了当前进程通过系统调用自愿让出运行以及在系统调用中因某种原因受阻以外，主要就是当因某种原因唤醒一个进程的时候，以及在时钟中断服务程序发现当前进程已经连续运行太久的时候，内核会对 need_resched 成员进行设置 ( 非０ ) ，以重新调度。

２）调度的方式：

Linux 内核的调度方式可以说是 “ 有条件的可剥夺 ” 方式。 ＊当进程在用户空间运行时，无论自愿不自愿，一旦有必要 ( 例如该进程已经运行了足够长的时间 ) ，内核就可以暂时剥夺其运行而调度其他进程进入运行。

＊但是，一旦进程进入了内核空间，或者说进入 “ 系统态 ” 。这时候，尽管内核知道应该要调度了，但是实际上调度并不会发生，直到该进程即将 “ 下台 ” ，也就是 回到用户空间的前夕 才能剥夺其运行权力。所以， linux 的调度方式从原则上来说是可剥夺的，可是实际上由于调度时机的限制而变成了有条件的。

３）调度策略：

基本上是从 UNIX 继承下来的 以优先级为基础 的调度。内核为系统中的每个进程计算出一个反映其运行 “ 资格 ” 的权值，然后挑选权值最高的进程投入运行。在运行的过程中，当前进程的资格 ( 权值 ) 随时间而递减，从而在下一次调度的时候原来资格较低的进程可能就更有资格运行了。到所有的进程的资格都变为０时，就重新计算一次所有进程的资格。
但是，为了适应各种不同应用的需要，内核 在此基础上 实现了三种不同的策略： SCHED_FIFO 、 SCHED_RR 、 SCHED_OTHER 。每个进程都有自己适用的调度策略，并且，进程还可以通过系统调用 sched_setscheduler() 设定自己适用的调度策略。下面介绍一下他们的区别：
SCHED_FIFO ：适用于时间性要求比较强，但每次运行所需的时间比较短的进程，因此多用于实时进程；
SCHED_RR:RR 表示 Round Robin ，是轮流的意思 ( 轮换调度 ) ，这种策略适合比较大、也就是每次运行时间较长的程序。使用 SCHED_RR 策略地进程在 schedule() 调度中有一点特殊的处理。　

上两者的比较： SCHED_FIFO 、 SCHED_RR 都是基于优先级的调度策略，可是在怎样调度具有相同优先级的进程的问题上两者有区别：
调度策略为 SCHED_FIFO 的进程一旦受到调度而开始运行之后，就要一直运行到自愿让出或者被优先级更高的进程剥夺为止。对于每次受到调度时要求运行时间不长的进程，这样并不会有多大的影响。可是， 如果是受到调度后可能执行很长时间的进程 ，这样就不公平了。这种不公正性是对具有相同优先级的进程而言的，同级的进程必须等待该进程自愿让出或者直到其运行结束。因为具有更高优先级的进程可以剥夺他的运行，而优先级则本来就没有机会运行，谈不上不公正。

　所以，对于执行时间可能会很长的进程来说，应该使用 SCHED_RR 调度策略，这种策略 在相同的优先级的进程上实行轮换调度。 也就是说：对调度策略为 SCHED_RR 的进程有个时间配额，用完这个配额就要让具有相同优先级的其他就绪进程先运行。看 schedule() 的５４０行对调度策略为 SCHED_RR 的当前进程的处理。

SCHED_OTHER ：是传统的调度策略，比较适合于交互式的分时应用。

问题：既然每个进程都有自己的适用的调度策略，内核怎样来调用使用不同调度策略的进程的呢？是根据什么挑选出下一个要运行的进程呢？

实际上，挑选的原则最后还是归结到每个进程的权值，只不过是在计算资格的时候将适用的策略也考虑进去了，就好像考大学时符合某些特殊条件的考生会获得加分一样。同时，对于适用不同策略地进程的优先级别也加了限制。

4、调度程序 schedule() ：

调度程序 schedule() 是一个非常频繁地执行的函数，因此要将运行效率放在第一位，函数中使用了很多的 goto 语句。
前面讲过，对 schedule() 只能由进程在内核中主动 调用，或者在当前进程从系统空间返回用户空间的前夕被动的 发生，而不能在一个中断服务程序的内部发生。即使一个中断服务程序有调度的要求，也只能通过把当前进程的 need_resched 字段设为１来表达这种要求，而不能直接调用 schedule() 。所以，如果在某个中断服务程序内部调用了 schedule() ，那一定是有问题的，所以转向 scheduling_in_interrupt.(kernel/sched.c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

	asmlinkage void schedule(void)
509 {
510 struct schedule_data * sched_data;
511 struct task_struct *prev, *next, *p;
512 struct list_head *tmp;
513 int this_cpu, c;
514
515 if (!current>
active_mm) BUG();
516 need_resched_back:
517 prev = current;
518 this_cpu = prev>
processor;
519
520 if (in_interrupt())
521 goto scheduling_in_interrupt ;
522
523 release_kernel_lock(prev, this_cpu);
524
525 /* Do "administrative" work here while we don't hold any locks */
526 if (softirq_active(this_cpu) & softirq_mask(this_cpu))
　　 /* 检查是否有内核软中断服务请求在等待，若有，就转入 handle_softirq 为这些请求服务 */
527 goto handle_softirq;
528 handle_softirq_back:

我们来看一下内核对这种问题的响应：

1
2
3
4
5

[schedule()]
686 scheduling_in_interrupt:
687 　　 printk("Scheduling in interrupt/n");
688 　　 BUG();
689 　　 return;

内核对此的响应是显示或者在 /var/log/messages 文件末尾添上一条出错信息，然后执行一个宏操作 BUG 。

接着往下看 schedule() ：
如果有内核软中断服务请求在等待，那么就转入 handle_softirq ：

1
2
3
4

　 [schedule()]
675 handle_softirq:
676 　　　 do_softirq();
677 　　　 goto handle_softirq_back;

执行 softirq 队列完毕以后继续往下看：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

　　 ==================== kernel/sched.c 528 541 ====================
[schedule()]
528 handle_softirq_back:
529
530 /*
531 * 'sched_data' is protected by the fact that we can run
532 * only one process per CPU.
533 */
534 sched_data = & aligned_data[this_cpu].schedule_data;
535
536 spin_lock_irq(&runqueue_lock);
537
538 /* move an exhausted RR process to be last.. */
539 if (prev>policy == SCHED_RR)
540 　　　 goto move_rr_last;
541 move_rr_back:

指针 sched_data 指向一个 schedule_data 数据结构，用来保存供下一次调度时使用的信息。此数据结构的定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

==================== kernel/sched.c 91 101 ====================
91 /*
92 * We align perCPU
scheduling data on cacheline boundaries,
93 * to prevent cacheline pingpong.
94 */
95 static union {
96 　　 struct schedule_data {
97 　　　　 struct task_struct * curr;
98 　　　　 cycles_t last_schedule;
99 　　　 } schedule_data;
100 　　　 char __pad [SMP_CACHE_BYTES];
101 } aligned_data [ NR_CPUS ] __cacheline_aligned = { };

这里的 cycles_t 实际上是无符号整数，用来记录调度发生的时间。这个数据结构是为多处理器 SMP 结构而设的，因此我们不必关心。数组中的第一个元素，即 CPU0 的 schedule_data 结构初始化为 {&init_task,0} ，其余的则全为｛０，０｝。代码中的 __cacheline_aligned 表示数据结构的起点应与高速缓存中的缓冲线对齐。

下面就要涉及可执行进程队列了，所以先将这个队列锁住 (536 行 ) ，以防止其他处理器的干扰。从 538 行开始：如果当前进程 prev 的调度策略是 SCHED_RR ，也就是轮换调度，那就要先进行一点特殊的处理 ( 540 : goto move_rr_last; ) 。 （对使用 SCHED_RR 策略的当前进程的处理）

1
2
3
4
5
6
7
8

  ==================== kernel/sched.c 679 685 ====================
 [schedule()]
679  move_rr_last:
680   if (!prev>counter) {
681       prev>counter = NICE_TO_TICKS (prev>nice);
682       move_last_runqueue(prev);
683     }
684 goto move_rr_back;

这里的 prev>counter ：代表这当前进程的运行时间配额，其数值在每次时钟中断时都要递减 (update_process_times() 中实现的 ) 。因此，不管一个进程的时间配额有多高，随着运行时间的积累最终总会递减到０。对于调度策略为 SCHED_RR 的进程，一旦其时间配额降到０，就要从 可执行进程队列 runqueue 中当前的位置上移动到队列的末尾，同时恢复其最初的时间配额（ NICE_TO_TICKS ），以等待下一次的调度。对于具有相同优先级的进程，调度的时候排在前面的进程优先，所以这使队列中具有相同优先级的其他进程有了优势。
宏操作 NICE_TO_TICKS 根据系统时钟的精度将进程的优先级别换算成可以运行的时间配额。在 kernel/sched.c 中定义。
　将一个进程的 task_struct 结构从可执行队列中的当前位置移到队列的末尾是由 move_last_runqueue() 完成的 (kernel/sched.c) 。把进程移到可执行进程队列的末尾意味着：如果队列中没有资格更高的进程，但是有一个资格与之相同的进程存在，那么，这个资格虽然相同而排在前面的进程会被选中。

继续看 schedule() ：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

==================== kernel/sched.c 541 553 ====================
[schedule()]
541 move_rr_back:
542
543 switch ( prev>state ) {
544 case TASK_INTERRUPTIBLE:
545 　　　 if (signal_pending(prev)) {
546 　　　　　　 prev>state = TASK_RUNNING;
547 　　　　　　 break;
548 　　　　 }
549 default:
550 　　　 del_from_runqueue(prev);
551 case TASK_RUNNING:
552 }
553 prev>need_resched = 0;

当前进程，就是正在执行的进程，当进入 schedule() 时其状态却不一定是 TASK_RUNNING 。例如：当前进程如已经在 do_exit() 中将其状态改成 TASK_ZOMBIE ，又如当前进程在 sys_wait4() 中调用 schedule() 时的状态为 TASK_INTERRUPTIBLE 。所以，这里的 prev>state 与其说是当前进程的状态不如说是其意愿。当其意愿既不是继续执行也不是可中断的睡眠时，就要通过 del_from_runqueue() 把这个进程从可执行队列中撤下来。另一方面， 也可以看出 TASK_INTERRUPTIBLE 和 TASK_UNINTERRUPTIBLE 两种睡眠状态之间的区别： 前者在进程有信号等待处理时要将其改成 TASK_RUNNING ，让其处理完这些信号再说，而后者则不受信号的影响。

最后，将 prev>need_resched 恢复为０，因为所需求的调度已经在进行了。 下面的任务就是要 挑选出一个进程来运行了 ( 这一部分是很重要的，通过对就绪进程队列进行扫描 ) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

==================== kernel/sched.c 555 576 ====================
[schedule()]
555 /*
556 * this is the scheduler proper:
557 */
558
559 repeat_schedule:
560 /*
561 * Default process to select..
562 */
563 next = idle_task (this_cpu);
564 c = 1000;
565 if ( prev>state == TASK_RUNNING )
566      goto still_running;
567
568 still_running_back:
569      list_for_each (tmp, &runqueue_head) {
570          p = list_entry(tmp, struct task_struct, run_list);
571          if (can_schedule(p, this_cpu)) {
572           int weight = goodness (p, this_cpu, prev>active_mm);
573           if ( weight > c )
574            c = weight, next = p;
575          }
576 }

在这段程序中， next 总是指向已知最佳的候选进程， c 则是这个进程的综合权值，或者是运行资格。

挑选的过程是从 idle 进程即 0 号进程开始，其权值为－ 1000 ，这是可能的最低值，表示仅在没有其他进程可以运行时才会让他运行。
然后，遍历可执行队列 runqueue 中的每个进程 ( 在单 CPU 系统中 can_schedule() 的返回值永远是 1) ，也就是一般操作系统书中所称的就绪进程。为每一个就绪进程通过函数 goodness () 计算出他当前所具有的权值，然后与当前的最高值 c 相比。注意这里的条件： weight > c ， 这意味着 “ 先入为大 ” 。也就是说，如果两个进程有相同的权值的话，排在队列前面的进程胜出，优先运行。

这里还有一个小插曲：如果当前进程的意图是继续运行，那么就要先执行一下 still_running(kernel/sched.c) ：

1
2
3
4
5
6
7

  ==================== kernel/sched.c 670 674 ====================
[schedule()]
670 still_running:
671    c = goodness(prev, this_cpu, prev>active_mm);
672    next = prev;
673    goto still_running_back;
674

也就是说，如果当前进程想要继续运行，那么在挑选候选进程时以当前进程此刻的权值开始比较。而且这意味着，对于具有相同权值的其他进程来说，当前进程优先。

那么，进程的当前权值是怎样计算的呢？也就是 goodness() 是怎样执行的呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

==================== kernel/sched.c 123 187 ====================
[schedule()> goodness() ]
123 /*
124 * This is the function that decides how desirable a process is..
125 * You can weigh different processes against each other depending
126 * on what CPU they've run on lately etc to try to handle cache
127 * and TLB miss penalties.
128 *
129 * Return values:
130 * 1000:never select this
131 * 0: out of time, recalculate counters (but it might still be
132 * selected)
133 * +ve: "goodness" value (the larger, the better)
134 * +1000: realtime process, select this.
135 */
136
137 static inline int goodness(struct task_struct * p, int this_cpu, struct mm_struct *this_mm)
138 {
139 int weight;
140
141 /*
142 * select the current process after every other
143 * runnable process, but before the idle thread.
144 * Also, dont trigger a counter recalculation.
145 */
146 weight = -1 ;
147 if (p>policy & SCHED_YIELD )
148 goto out;
149
150 /*
151 * Non RT process normal case first.
152 */
153 if ( p>policy == SCHED_OTHER ) {
154 /*
155 * Give the process a firstapproximation goodness value
156 * according to the number of clockticks it has left.
157 *
158 * Don't do any other calculations if the time slice is
159 * over..
160 */
161    weight = p->counter;
162    if (!weight)
163    goto out;
164
165 #ifdef CONFIG_SMP
166 /* Give a largish advantage to the same processor... */
167 /* (this is equivalent to penalizing other processors) */
168 if (p->processor == this_cpu)
169    weight += PROC_CHANGE_PENALTY;
170 #endif
171
172 /* .. and a slight advantage to the current MM */
173   if (p->mm == this_mm || !p->mm)
174       weight += 1;
175    weight += 20- p>nice;
176    goto out;
177 }
178
179 /*
180 * Realtime process, select the first one on the
181 * runqueue (taking priorities within processes
182 * into account).
183 */
184      weight = 1000 + p->rt_priority;
185 out:
186      return weight;
187 }

＊首先，如果一个进程通过系统调用 sched_yield() 明确表示了 “ 礼让 ” 后，就将其权值定位 -1 。这是很低的权值，一般就绪进程的权值至少是 0 。
＊对于没有实时要求的进程 ，即调度策略为 SCHED_OTHER 的进程，其权值主要取决于两个因素：一个是剩下的时间配额 p->counter ，如果用完了则权值为 0 。另一个是进程的优先级 nice ，这是从早期 Unix 沿用下来的负向优先级 ( 越负，优先级越高 ) ，其取值范围为 19~-20 ，只有特权用户才能把 nice 值设置为小于 0 。所以，综合的权值 weight 在时间配额尚未用完时基本上是二者之和。 此外，如果是内核线程，或者其用户 空间与当前进程的相同，因而无需切换用户空间，则会得到一点小 “ 奖励 ” ，将权值额外加 1 。
＊对于实时进程，即调度策略为 SCHED_FIFO 或者 SCHED_RR 的进程，则另有一种正向的优先级 ，那就是实时优先级 rt_priority ，而权值为 1000 + p->rt_priority 。可见， SCHED_FIFO 或者 SCHED_RR 两种有时间要求的策略赋予进程很高的权值 ( 相对于 SCHED_OTHER) 。这种进程的权值至少是 1000 。另一方面， rt_priority 的值对于实时进程之间的权值比较也起着重要的作用，其数值也是在 sched_setscheduler() 中与调度策略一起设置的。

从上面可以看出：对于这两种实时调度策略，一个进程已经运行了多久，即时间配额 p->counter 的当前值，对权值的计算不起所用。不过，前面讲到，对于使用 SCHED_RR 策略地进程，当 p->counter 达到 0 时会导致将进程移到队列尾部。
实时进程的 nice 数值与优先级无关，但是对 使用 SCHED_RR 策略地进程的时间配额大小有关 ( 宏操作 NICE_TO_TICKS()) 。由于实时进程的权值有个很大的基数 (1000) ，因此当有实时进程就绪时，非实时进程是没有机会运行的。

由此可见， linux 内核中对权值的计算是很简单的，但是 goodness() 函数并不代表 linux 调度算法的全部，而要与前面讲到的 对 SCHED_RR 进程的特殊处理 、 对意欲继续运行的当前进程的特殊处理 ‘ 以及下面要讲到的 recalculate 结合起来分析。

上面 still_running_back 运行结束后，变量 c 的值有几种可能：一种可能是一个大于 0 的正数，此时 next 指向挑选出来的进程；另一种可能是 c 的值为 0 ，发生于就绪队列中所有进程的权值都是 0 的时候。由于除了 init 进程和调用了 sched_yield() 的进程以外，每个进程的权值最低为 0 ，所以只要队列中有其他就绪进程存在就不可能为负数。因此，队列中所有其他进程的权值都已经降到 0 了，说明这些进程的调度策略都是 SCHED_OTHER ，即系统中当前没有就绪的实时进程，因为如果有策略为 SCHED_FIFO 或者 SCHED_RR 的进程存在，其权值至少也有 1000 。

let`s go on ：回到 schedule()

1
2
3
4
5
6

==================== kernel/sched.c 578 580 ====================
[schedule()]
578 /* Do we need to recalculate
counters? */
579 if (!c)
580 goto recalculate;

如果当前已经选择的进程（权值最高的进程）的权值为 0 ，那就要重新计算各个进程的时间配额。如上所述，这说明系统中当前没有就绪的实时进程。而且，这种情况已经持续了一段时间，否则 SCHED_OTHER 进程的权值就没有机会消耗到 0 。

1
2
3
4
5
6
7
8
9
10
11
12
13

 ==================== kernel/sched.c 658 669 ====================
[schedule()]
658 recalculate:
659 {
660     struct task_struct *p;
661     spin_unlock_irq(&runqueue_lock);
662     read_lock(&tasklist_lock);
663     for_each_task (p)
664         p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
665     read_unlock(&tasklist_lock);
666     spin_lock_irq(&runqueue_lock);
667 }
668  goto repeat_schedule;

这里所作的运算是将每个进程的当前的时间配额 p->counter 除以 2 ，再在上面加上由该进程的 nice 值换算过来的 tick 数量。宏操作 NICE_TO_TICKS 的定义在前面已经见过，显然 nice 值对于非实时进程既表示优先级也决定着时间配额。
注意：这里的 for_each_task() 是对所有进程的循环，而并不是仅对就绪进程队列的循环，对于不再就绪进程队列中的非实时进程 ，这里得到了提升其时间配额、从而提升其综合权值的机会。不过，这种对综合权值的提升是很有限的，每次重新计算都将原有的时间配额减半，再与 NICE_TO_TICKS(p->nice) 相加，这样就决定了重新计算以后的综合权值永远也不可能达到 NICE_TO_TICKS(p->nice) 的两倍。因此，即使经过很长时间的韬光养晦，也不可能达到可与实时进程竞争的地步，所以只是对非实时进程之间的竞争有意义。
至于实时进程，时间配额的增加并不会提升其综合权值，而且对于 SCHED_FIFO 进程，时间配额就没有什么意义。 重新计算完权值以后，程序转回 repeat_schedule( 跳回前面，再次执行挑选进程 ) 处重新挑选。这样，当再次完成对就绪进程队列的扫描时，变量 c 的值就应该不为 0 了，此时 next 指向挑选出来的进程。
至此，已经挑选好进程了（权值最高的进程）。

还没有结束阿？哈哈
进程挑好之后，接下来要做的就是切换的事情了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

[schedule()]
581 /*
582 * from this point on nothing can prevent us from
583 * switching to the next task, save this fact in
584 * sched_data.
585 */
586 sched_data>curr = next;
587 #ifdef CONFIG_SMP
.....
590 #endif
591 spin_unlock_irq(&runqueue_lock);
592
593 if ( prev == next ) 
594     goto same_process;
595
596 #ifdef CONFIG_SMP
==================== kernel/sched.c 612 657 ====================
612 #endif /* CONFIG_SMP */
613
614 kstat.context_swtch++;
615 /*
616 * there are 3 processes which are affected by a context switch:
617 *
618 * prev == .... ==> (last => next)
620 * It's the 'much more previous' 'prev' that is on next's stack,
621 * but prev is set to (the just run) 'last' process by switch_to().
622 * This might sound slightly confusing but makes tons of sense.
623 */
624 prepare_to_switch ();
625 {
626   struct mm_struct *mm = next->mm;
627   struct mm_struct *oldmm = prev->active_mm;
628   if (!mm) {
629         if (next>active_mm) BUG();
630         next>active_mm = oldmm;
631         atomic_inc(&oldmm>mm_count);
632          enter_lazy_tlb(oldmm, next, this_cpu);
633 } else {
634      if (next>active_mm != mm) BUG();
635     switch_mm(oldmm, mm, next, this_cpu);
636 }
637
638 if (!prev>mm) {
639       prev>active_mm = NULL;
640       mmdrop(oldmm);
641 }
642 }
643
644 /*
645 * This just switches the register state and the
646 * stack.
647 */
648 switch_to(prev, next, prev);
649 __schedule_tail(prev);
650
651 same_process:
652     reacquire_kernel_lock(current);
653     if (current>need_resched)
654        goto need_resched_back;
655
656    return;

跳过对 SMP 结构的条件编译部分。
首先，如果挑选出来的进程 next 就是当前进程 prev ，就不用切换，直接跳转到 same_process 处就返回了。这里的 reacquire_kernel_lock() 对于 i386 单 CPU 结构而言是空语句。前面已经把当前进程的 need_resched 清 0 ，如果现在又成了非 0 ，则一定是发生了中断并且情况有了变化，所以转回 need_resched_back 再调度一次。
否则，如果挑选出来的进程 next 与当前进程 prev 不同，那就要切换了。对于 i386 单 CPU 结构而言， prepare_to_switch() 也是空语句。而 649 行的 __schedule_tail() 则只是将当前进程 prev 的 task_struct 结构中的 policy 字段里的 SCHED_YIELD 标志位清成 0 。所以实际上只剩下了两件事：对用户虚存空间的处理；进程的切换 switch_to() 。

实验：
第二部分：如何在 sched.c 中实现算法？

首先，确定何时进行算法的计算过程。 是在 schedule() 中选择下一运行进程之前？
选择下一运行进程时？选择下一运行进程之后？还是直接修改 goodness() 函数以确定下一运行进程呢？
在以上提到的各个位置都可以添加代码实现我们的算法，但是考虑到 schedule() 函数是被频繁调用的一个函数 ，它的运行效率直接影响到了系统的吞吐量，因此我们所添加的代码段应该是被调用的频率越小越好。
在这种原则的指导之下，我们发现有一段代码只有在 CPU 的时间段（ epoch ）全部耗尽的时候才去调用，而在此时刻可以根据一些信息调度进程，达到给每个用户平均分配 CPU 时间的效果。在 schedule() 函数选择了一个进程之后，它将判断是否需要重新计算进程的 counter 值，这个过程只有在运行队列中所有进程的都用完了时间片时才被调用。在这段代码中加入我们的算法是最合适不过的了。

　原文为：http://www.cublog.cn/u2/69737/showart_1070708.html

http://zzjlzx.blog.chinaunix.net/uid-29060569-id-4076183.html

调度：

操作系统的调度程序的两项任务：

1： 调度：

实现调度策略，决定就绪的进程、线程竞争cpu的次序的裁决原则。说白了就是进程和线程何时应该放弃cpu和选择那个就绪进程、线程来执行。

2： 分派：

原来实现调度机制如何时分复用cpu，处理好上下文交换的细节、完成进程、线程和cpu的绑定和放弃的具工作。

linux 2.4 调度：

1：policy ：
进程的调度策略：

1
2
3

1）SCHED_FIFO : 实时进程使用的的先进先出策略，进程会一直占用cpu除非其自动放弃cpu。
2）SCHED_RR : 实时进程的轮转策略，当分配个u进程的时间片用完后，进程会插入到原来优先级的队列中。
3）SHED_OTHER：普通进程基于优先级的的时间片轮转调度。

2：priority：进程的静态优先级。
3：nice：进程用来控制优先级的因子。在-20～19间的整数。增加nice的值会使优先级降低。默认值为0。
4：rt_priority：实时进程的优先级。
5：counter：一个计时器，进程目前的剩余时间片。用来动态计算进程的动态优先级。系统将休眠次数多的进程的剩余时间叠会加起来。
6：schedule()的流程：

1
2
3
4
5
6
7

1）检查是否有软中断请求。有则先执行。
2）如果当前进程的调度策略为RR并且counter==0,将此进程移到运行进程队列的尾部。重新计算counter的值。
3）若当前进程的状态为 TASK_INTERRUPTIBLE 且有信号接收，则将进程状态设置为TASK_RUNNING，
   若当前进程的状态不是TASK_RUNNING,则将进程从可执行的队列中移出，将其进程描述符的need_resched置为0。
4）选择出可运行队列中最大权值，保存在变量c中，与之对应的进程描述符保存在变量next中。
5）检查c是否为0,c==0,则队列中的所有进程的时间片都用完了。此时对队列中所有进程的时间片重新计算。重新执行第5步。
6）如果netx==当前进程，则结束调度进程。否则，进行进程切换。

过程：2.4的调度算法，将所有的就绪进程组织成一条可运行队列，不管是单核环境还是smp环境，cpu都只从这条可运行队列中循环遍历直到挑选到下一个要运行的进程。如果所有的进程的时间片都用完，就重新计算所有进程的时间片。

2.4调度的数据结构：

2.4调度的不足：

1）一个明显的缺点就是时间复杂度为O(n)，每次都要遍历队列，效率低！。虽然说O(n)的复杂度看起来不是很糟糕，而且系统能容纳进程数量也不一定会很大，但复杂度为O(n)还是很难忍受的。
2）由于在smp环境下多个cpu还是使用同一条运行队列，所以进程在多个cpu间切换会使cpu的缓存效率降低，降低系统的性能。
3）多个cpu共享一条运行队列，使得每个cpu在对队列操作的时候需要对运行队列进行加锁，这时如果其他空闲cpu要访问运行队列，则只能等待了。由2、3两点可以看出2.4的调度算法对smp环境的伸缩性不高！不能很好地支持smp环境。
4）不支持内核抢占，内核不能及时响应实时任务，无法满足实时系统的要求（即使linux不是一个硬实时，但同样无法满足软实时性的要求）。
5）进程的剩余时间是除了nice值外对动态优先级影响最大的因素，并且系统将休眠次数多的进程的剩余时间叠加起来，从而得出更大的动态优先级。这体现了系统更倾向优先执行I/O型进程。内核就是通过这种方式来提高交互进程的优先级，使其优先执行。但休眠多的进程就代表是交互型的进程吗？并不是的，这只能说明它是I/O型进程。I/O型进程需要进行I/O交互，如读写磁盘时进程会经常处于休眠的状态。如果把这种进程当成是交互进程，反而会影响其他真正的交互进程。
6）简单的负载平衡。那个cpu空闲就把就绪的进程调度到这个cpu上去执行。或者某个cpu的进程的优先级比某个进程低，就调度到那个cpu上去执行。这样简单的负载平衡缺点不言而喻。进程迁移比较频繁，而且出现2、3的情况。这样的负载平衡弊大于利！

linux 2.6 O(1)调度：

1：policy：调度策略跟2.4的一样。
2：rt_priority：实时进程的优先级。在0～99之间。MAX_RT_PRIO为100。不参与优先级的计算。
3：static_prio：非实时进程的静态优先级，由nice值转换而来，-20 <= nice <= 19。static_prio = MAX_RT_PRIO + nice + 20。所以 100 <= static_prio <= 139。
4：sleep_avg：进程平均等待时间。进程等待时间与执行时间的差。反映进程的交互性，又表示了进程需要运行的紧急程度。这个值越大，进程的优先级就越高。
5：prio：进程的动态优先级。主要影响进程的prio的因素是sleep_avg。其计算时机为：

1
2
3
4

1）进程在创建时继承父进程的prio。
2）进程由睡眠到被唤醒时进行优先级修正。
3）时钟中断中重新计算进程的优先级并且进程进入相应的队列。
4）负载平衡/修改nice/修改调度策略等都有可能修改prio的值。

6：time_slice：进程的时间片余额。进程的默认时间片与static_prio有关。
7：load_weight：平衡负载用的权重。

linux 2.6 O(1)调度的数据结构代码：

1：运行队列：部分代码如图：

2：优先级数组代码如图：

1
2
3

1）nr_active：数组内可运行的进程
2）DECLARE_BITMP(...)：优先级位图的宏。找出优先级最高的且有就绪进程的队列。
3）list_head queue：使用通用链表，优先级队列。

linux 2.6 O(1)调度的数据结构（active or expired）：

每个cpu维护一个自己的运行队列，每个运行队列有分别维护自己的active队列与expried队列。当进程的时间片用完后就会被放入expired队列中。当active队列中所有进程的时间片都用完，进程执行完毕后，交换active队列和expried。这样expried队列就成为了active队列。这样做只需要指针的交换而已。当调度程序要找出下一个要运行的进程时，只需要根据上面提过的位图宏来找出优先级最高的且有就绪进程的队列。这样的数据组织下，2.6的调度程序的时间复杂度由原来2.4的O(n)提高到O(1)。而其对smp环境具有较好的伸缩性。

数据结构的组织如下：

linux 2.6 O(1) 调度的进程优先级：

2.6调度有140个优先级级别，由0～139, 0～99 为实时优先级，而100～139为非实时优先级。上面的图有说。

特点：

1）动态优先级是在静态优先级的基础上结合进程的运行状态和进程的交互性来计算。所以真正参与调度的是进程的动态优先级。而进程的交互性是通过进程的睡眠时间来判断的（这点从根本上来说还是和2.4思想的一样）。所以动态优先级是通过静态优先级和进程睡眠时间来计算的。这里要注意的是，动态优先级是非实时进程插入优先级队列的依据。但实时进程是根据rt_prioirty来插入队列的，实时进程的实时优先级由进程被创建到进程结束都是不会改变的。但其执行的时间片是根据静态优先级来计算的。
2）进程优先级越高，它每次执行的时间片就越长。
3）使用TASK_INTERACTIVE()宏来判断进程是否为交互进程，该宏是基于nice来判断的，nice值越高，优先级越低，这样交互性越低。
4）如果一个进程的交互性比较强，那么其执行完自身的时间片后不会移到expired队列中，而是插到原来队列的尾部。这样交互性进程可以快速地响应用户，交互性会提高。如果被移到expired队列，那么在交换队列指针前，交互性进程可能就会发生严重的饥饿，从而使交互性严重下降
5）在创建新的进程时，子进程会与父进程平分进程的剩余时间片。即在 fork()——>do_fork() 后父子进程的时间片之和等于原来父进程的时间片大小。这样做的原因是为了防止父进程利用创建子进程来窃取时间片。如果子进程在退出时，从来没有被重新分配时间片，且还有时间片剩余，则其剩余的时间片会返还给父进程。这样父进程就不会因为创建子进程而受到时间片上的惩罚。

2.6 O(1)调度动态优先级的计算代码：

1）effective_prio(p)：

2）normal_prio：

3）__normal_prio：

linux 2.6 O(1)调度的调度与抢占时机：

1：直接调度：当前进程因为阻塞而直接调用schedule()主动放弃cpu。

1
2
3
4

1）当前进程被放入相应的等待队列。
2）改变当前进程的进程状态。由TASK_RUNNING 改为TASK_UNINTERRUPTIBLE 或者 TASK_INTERRUPTIBLE。
3）选择新的进程运行。调用schedule() 来获得下一个需要运行的进程。
4）当资源可用时，把当前进程从等待队列中移除。

2：被动调度：当前进程因为时间片用完，或者被更高优先级的进程抢占，而被逼放弃cpu。这时当前进程不会立刻被调度出去，而是通过设置TIF_NEED_RESCHED位为1来告知kernel需要调度了。在适当的时机kernel会重新调度。

1）问题：为什么不能立刻调度？

进程在内核里运行时，可能要申请共享资源，如自旋锁，如果这个时候去抢占当前进程，使其立刻让出cpu，如果新进程也需要相同的共享资源的话，那么会导致死锁！所以这里进程只设置了标志位通知内核需要调度。

2）问题：什么时候才是合适的时机？

内核在即将返回用户空间时会检查TIF_NEED_RESCHED，如果设置了就调用schedule()，这样就会发生用户抢占。
a：从中断处理程序返回用户空间时。
b：从系统调用返回用户空间时。

linux 2.6 O(1)调度的负载平衡：

复杂！

linux 2.6 O(1)调度的过渡：

1：SD调度器：

O(1)调度的复杂性主要来至于动态优先级的计算。调度器根据一些难以理解的经验公式和平均休眠时间来决定、修改进程的优先级。这是O(1)调度一个比较大的缺点（甚至可以说是致命的。）。SD调度的特点：

1）数据结构跟O(1)调度差不多，不过少了expired队列。
2）进程在用完其时间片后不会放到expired队列，而是放到下一个优先级队列中（这就是为什么没有expired队列的原因）。当下降到最低一级时，时间片用完，就回到初始优先级队列去，重新降级的过程！每一次降级就像我们下楼梯的过程，所以这被称为楼梯算法。
3）两种时间片：粗粒度、细粒度。粗粒度由多个细粒度组成，当一个粗粒度时间片被用完，进程就开始降级，一个细粒度用完就进行轮回。这样cpu消耗型的进程在每个优先级上停留的时间都是一样的。而I/O消耗型的进程会在优先级最高的队列上停留比较长的时间，而且不一定会滑落到很低的优先级队列上去。
4）不会饥饿，代码比O(1)调度简单，最重要的意义在于证明了完全公平的思想的可行性。
5）相对与O(1)调度的算法框架还是没有多大的变化，每一次调整优先级的过程都是一次进程的切换过程，细粒度的时间片通常比O(1)调度的时间片短很多。这样不可避免地带来了较大的额外开销，使吞吐量下降的问题。这是SD算法不被采用的主要原因！

2：RSDL调度器：

对SD算法的改进，其核心思想是“完全公平”，并且没有复杂的动态优先级的调整策略。引进“组时间配额” → tg 每个优先级队列上所有进程可以使用的总时间 ，”优先级时间配额“ → tp, tp不等于进程的时间片，而是小于进程时间片。当进程的tp用完后就降级。与SD算法相类似。当每个队列的tg用完后不管队列中是否有tp没有用完，该队列的所有进程都会被强制降级。

linux 2.6 O(1)调度的不足：

1：复杂的难以理解的经验公式。
2：公平吗？
3：实时性？

linux 杰出的调度算法 → cfs：

按照cfs的作者的说法：”cfs的 80% 的工作可以用一句话来概括：cfs在真实的硬件上模拟了完全理想的多任务处理器。“ 在完全理想的多任务处理器下，每个进程都能够同时获得cpu的执行时间，当系统中有两个进程时，cpu时间被分成两份，每个进程占50%。

1：虚拟运行时间。进程的 vt 与其实际的运行时间成正比，与其权重成反比。权重是由进程优先级来决定的，而优先级又参照nice值的大小。进程优先级权重越高，在实际运行时间相同时，进程的vt就越小。所有的非实时的可运行的进程用红黑树来组织起来，调度时选择的vt最小的那个进程。因为这里的红黑树左子树的键值比右边的小，所以每次调度时都选择树的最左下角的那个进程（实体）就可以了。
2：完全公平的思想。cfs不再跟踪进程的休眠时间、也不再区分交互式进程，其将所有的进程统一对待，在既定的时间内每个进程都获得了公平的cpu占用时间，这就是cfs里的公平所在！
3：cfs 引入了模块化、完全公平调度、组调度等一系列特性。虽说是完全公平调度，但进程之间本来就不公平的（有些内核线程用于处理紧急情况），所以这种完全公平是不能够实现的。cfs使用weight 权重来区分进程间不平等的地位，这也是cfs实现公平的依据。权重由优先级来决定，优先级越高，权重越大。但优先级与权重之间的关系并不是简单的线性关系。内核使用一些经验数值来进行转化。 如果有a、b、c 三个进程，权重分别是1、2、3,那么所有的进程的权重和为6, 按照cfs的公平原则来分配，那么a的重要性为1/6, b、c 为2/6, 3/6。这样如果a、b、c 运行一次的总时间为6个时间单位，a占1个，b占2个，c占3个。

cfs调度器：

各个部分的数据结构关系图如下：

虚拟运行时间

在完全理想的多任务处理器下，每个进程都能同时获得cpu的时间。但实际上当一个进程占用cpu时，其他的进程必须等待，这样就产生了不公平。所以linux 的cfs调度引入了虚拟运行时间。虚拟运行时间主要由两个因素决定，一个是实际的运行时间，一个是其权重，它随自己的实际运行时间增加而增加，但又不等于实际运行时间。上面提过内核采用红黑树来对虚拟运行时间来排序，这样红黑树最左边的进程（调度实体）就是受到了最不公平待遇的进程，需要作为下一个被调度的进程。 进程的虚拟运行时间由calc_delta_fair()来计算。在每次时钟中断后都会进行更新。公式为：

1
2
3
4

if (se.load.weight != NICE_0_LOAD)
	vruntime += delta * NICE_0_LOAD / se.load.weight;
else
	vruntime += delta;

delta是进程增加的实际的运行时间。 NICE_0_LOAD为nice 0进程的权重。虚拟运行时间与权重成反比，进程的权重越大虚拟运行时间就增加得越慢，位置就越左，越有可能被调度。

对cfs的理解最好就是看源代码了，下面贴出代码（网上有人整理得很好了）：
各个函数的调用关系图：
（1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

tick中断
在tick中断处理函数中,会调用scheduler_tick()函数.该函数代码如下:
在tick中断处理函数中，会调用scheduler_tick()函数。该函数代码如下:
void scheduler_tick(void)
{
  /*取得当前CPU*/
int cpu = smp_processor_id();
/*取得当前CPU对应的runqueue*/
	struct rq *rq = cpu_rq(cpu);
/*当前运行的进程*/
	struct task_struct *curr = rq->curr;
 
	sched_clock_tick();
 
	spin_lock(&rq->lock);
	/*更新rq的当前时间戳.即使rq->clock变为当前时间戳*/
	update_rq_clock(rq);scheduler_tick()
	/*更新rq的负载*/
	update_cpu_load(rq);
	/*调用调度模块的task_tick函数*/
	curr->sched_class->task_tick(rq, curr, 0);
	spin_unlock(&rq->lock);
 
#ifdef CONFIG_SMP
	rq->idle_at_tick = idle_cpu(cpu);
	trigger_load_balance(rq, cpu);
#endif
}
我们从上面的代码中可以看到,经过一部份共同处理之后,流程会转入调度模块的task_tick()函数.
对应CFS,它的sched_class结构如下:
static const struct sched_class fair_sched_class = {
	.next = &idle_sched_class,
	.enqueue_task = enqueue_task_fair,
	.dequeue_task = dequeue_task_fair,
	.yield_task = yield_task_fair,
 
	.check_preempt_curr = check_preempt_wakeup,
 
	.pick_next_task = pick_next_task_fair,
	.put_prev_task = put_prev_task_fair,
 
#ifdef CONFIG_SMP
	.select_task_rq = select_task_rq_fair,
 
	.load_balance = load_balance_fair,
	.move_one_task = move_one_task_fair,
#endif
 
	.set_curr_task = set_curr_task_fair,
	.task_tick = task_tick_fair,
	.task_new = task_new_fair,
 
	.prio_changed = prio_changed_fair,
	.switched_to = switched_to_fair,
 
#ifdef CONFIG_FAIR_GROUP_SCHED
	.moved_group = moved_group_fair,
#endif
};
即对应task_tick的处理函数为task_tick_fair().代码如下:

（2）

1
2
3
4
5
6
7

schedule()的执行过程
当进程需要被抢占或者是进程主运让出处理器,则会调用schedule()函数.为了减小篇幅,在这里就不分析schedule()函数代码.只列出在该函数中调用模块的主要函数.如下示:
Schedule()---->
sched_class->put_prev_task(rq,prev)---->
sched_class->pick_next_task()
 
对应到CFS中,put_prev_task()函数为put_prev_task_fair(),该操作就是将进程放回队列.

（3）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

新进程的调度过程
在创建新进程的时候,在do_fork()中有如下过程:
long do_fork(unsigned long clone_flags,
		  unsigned long stack_start,
		  struct pt_regs *regs,
		  unsigned long stack_size,
		  int __user *parent_tidptr,
		  int __user *child_tidptr)
{
 
	
	if (unlikely(clone_flags & CLONE_STOPPED)) {
		/*
		 * We'll start up with an immediate SIGSTOP.
		 */
		sigaddset(&p->pending.signal, SIGSTOP);
		set_tsk_thread_flag(p, TIF_SIGPENDING);
		__set_task_state(p, TASK_STOPPED);
	} else {
		wake_up_new_task(p, clone_flags);
	}

｝
即在末带CLONE_STOPPED标志创建进程时,就会对新进程调用wake_up_new_task().

好像改这行就能直接用了

1
2
3
4

610c610
< # http_access deny all
---
>  http_access allow all

一个centos5上不干扰系统haproxy、squid独立运行的提取 haproxy_squid.tar.gz

安装

1

yum install squid

centos 5

ERROR:

1
2
3
4
5
6
7
8
9
10

While trying to retrieve the URL: http://192.168.34.80/

The following error was encountered:

Unable to forward this request at this time.
This request could not be forwarded to the origin server or to any parent caches. The most likely cause for this error is that:

The cache administrator does not allow this cache to make direct connections to origin servers, and
All configured parent caches are currently unreachable.
Your cache administrator is root. 

将 /etc/squid/squid.conf 中

1

never_direct allow all

改成

1

always_direct allow all

再去掉cache_peer

centos 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# diff /tmp/orig_squid.conf /etc/squid/squid.conf
610c610
< # http_access deny all
---
> http_access allow all
615,616c615,616
< http_access allow manager localhost
< http_access deny manager
---
> #http_access allow manager localhost
> #http_access deny manager
618c618
< http_access deny !Safe_ports
---
> #http_access deny !Safe_ports
620c620
< http_access deny CONNECT !SSL_ports
---
> #http_access deny CONNECT !SSL_ports
636,637c636,637
< http_access allow localhost
< http_access deny all
---
> #http_access allow localhost
> #http_access deny all
921c921
< http_port 3128
---
> http_port 3128 accel vhost vport
4007a4008
> always_direct allow all