部分cfs调度器的tuning参数

最近看了rhel6.2内核的cfs进程调度代码，作为学习总结，把相关的部分tuning参数做了下整理，摘录如下。

* sched_child_runs_first
  当创建子进程时，保证子进程会在父进程之前运行。在创建子进程时，首先会
  将子进程的虚拟运行时间设置为min_vruntime，这个min_vruntime大约等于当
  前运行队列中所有进程的虚拟运行时间的最小值，然后，看sched_features中
  是否设置了START_DEBIT位，如果这一位被设置了，表示要给新创建的进程的
  虚拟运行时间再增加一些，这样会让它的运行时间向后延迟，以防进程通过不
  停的fork来不停的获得cpu时间。当设置完子进程的虚拟运行时间之后，会判
  断sched_child_runs_first是不是设置为1，如果是的话就比较父进程和子进
  程的虚拟运行时间，如果父进程的虚拟运行时间比较小的话,就交换父子进程
  的虚拟运行时间，这样子进程就会在父进程之前运行了。

* sched_min_granularity_ns
  这个值在两个地方会用到。一个是计算nice值为0的进程运行一次需要的时间。
  如果进程的总数大于sched_latency/sched_min_granularity个，就用
  sched_min_granularity_ns的值乘以进程的个数，将乘积作为nice值为0的进程
  调度一次运行的时间。然后每个进程会以此为基准，按照自己的优先级来计算
  自己被调度一次的运行时间。。另一个用途是判断当前进程是否要被调度下
  CPU的时候。如果当前进程的执行时间已经超过了它被调度一次所允许的执行时
  间（其实也可以说是时间片,尽管cfs声称自己没有时间片），那么必然要被调
  度下CPU。但如果它的时间片还没到期，在判断它的运行时间是不是比
  sched_min_granularity_ns小。如果是的话，那么就肯定不把它调度下CPU，如
  果进程的运行时间比sched_min_granularity_ns大的话，就用当前进程的虚拟
  运行时间减去runqueue上虚拟运行时间最小的进程的虚拟运行时间，如果差值
  比当前进程的时间片（这个时间片确实不是传统的时间片，总是随当前负载的
  状况变化）还大的话，那么当前进程也会被调度下CPU。

* sched_latency_ns
  计算nice值为0的进程运行一次所需的时间时用到。。如果进程总数小于等于
  sched_latency/sched_min_granularity个，就将sched_latency_ns作为nice
  值为0的进程运行一次的时间，否则按照前面介绍sched_min_granularity_ns
  时的方法计算。

* sched_wakeup_granularity_ns
  判断一个进程是否可以抢占当前进程时用到。如果该进程的虚拟运行时间比当
  前进程的虚拟运行时间大，那么肯定不能抢占。如果该进程的虚拟运行时间比
  当前进程的虚拟运行时间小的话，就计算出两者之差vdiff。如果vdiff大于一
  定的范围的话，就可以抢占，否则不可以抢占。
  sched_wakeup_granularity_ns就是用来确定这个范围的。它表示一个nice值
  为0的进程要抢占当前进程，它的虚拟运行时间需要被当前进程的虚拟运行时
  间小多少，其他优先级的进程以此为基准进行调整，优先级越高的进程，需要
  的差值越小。

* sched_tunable_scaling
  当内核试图调整sched_min_granularity，sched_latency和
  sched_wakeup_granularity这三个值的时候所使用的更新方法，0为不调整，1
  为按照cpu个数以2为底的对数值进行调整，2为按照cpu的个数进行线性比例的
  调整。

* sched_features
  每个bit都表示调度器的一个特性是否打开。在sched_features.h文件中记录
  了全部的特性。

* sched_migration_cost
  用来判断一个进程是不是cache hot的。如果进程的运行时间小于
  sched_migration_cost就认为是cache host的，在多CPU之间进行负载均衡的
  时候不会转移cache hot的进程。

* sched_nr_migrate
  在多CPU情况下进行负载均衡时，一次最多移动sched_nr_migrate个进程到另
  一个CPU上。

关于linux内核抢占的一点思考

偶然看了一下rhel6.2系统内核中处理软中断的内核线程，很意外的产生了一点困
惑，这是ksoftirqd线程的主循环:

1    while (!kthread_should_stop()) {
2        preempt_disable();
3        if (!local_softirq_pending()) {
4            preempt_enable_no_resched();
5            schedule();
6            preempt_disable();
7        }
8
9        __set_current_state(TASK_RUNNING);
10
11        while (local_softirq_pending()) {
12            /* Preempt disable stops cpu going offline.
13               If already offline, we'll be on wrong CPU:
14               don't process */
15            if (cpu_is_offline((long)__bind_cpu))
16                goto wait_to_die;
17            do_softirq();
18            preempt_enable_no_resched();
19            cond_resched();
20            preempt_disable();
21            rcu_sched_qs((long)__bind_cpu);
22        }
23        preempt_enable();
24        set_current_state(TASK_INTERRUPTIBLE);
25    }

假设在23行执行完之后，有人试图唤醒这个线程，此时，线程还处于
TASK_RUNNING的状态，所以什么都不会发生。然后，在第24行，线程将自己设置
成了TASK_INTERRUPT状态，在执行第24行之后，线程被抢占了，那么，它在
TASK_INTERRUPT状态下被抢占，除非再次有人唤醒它，它岂不是再也返回不了了？
这样，不就丢失了一次唤醒吗？

这让我很困扰，于是，我自己写了个测试程序，启动一个内核线程，然后让它把
自己设置成TASK_INTERRUPTIBLE的状态，再进行几秒钟的忙循环。正常来说，执
行几秒钟的忙循环的话，肯定会被抢占了。然后我看它还能不能再被调度上来。
结果意外的发现rhel6的内核编译时是配置成不可抢占的（后来发现rhel5也这
样），我那个单核的虚拟机一执行忙循环就hang住。于是，重新编译了一个可抢
占的内核跑起来。结果发现，执行忙循环后，还是能被调度上来的。但如果我不
执行忙循环，而是调用schedule()函数，那么，除非被唤醒，否则就不能再被调
度上来了。

用systemtap跟踪了一下我的内核线程进入schedule()函数时的一些信息，结果
发现如果我主动调用schedule()函数，在进入schedule()函数时，thread_info
中的preempt_count的值是0x00000005，而如果在执行忙循环时被抢占调用
schedule函数时，preempt_count的值是0x10000005。这个最高位1在内核中被定
义为PREEMPT_ACTIVE。

原来，每当在抢占点上执行schedule函数时，这个标志会被设置，比如，从中断
返回时，调用：
retint_kernel
-> preempt_schedule_irq
   -> schedule

在preempt_schedule_irq函数中，就会调用这几行代码：

        add_preempt_count(PREEMPT_ACTIVE);
        local_irq_enable();
        schedule();
        local_irq_disable();
        sub_preempt_count(PREEMPT_ACTIVE);

设置PREEMPT_ACTIVE后，再调用schedule()函数，然后再清除PREEMPT_ACTIVE标
志。

而在schedule()函数中，有这样一段代码：

    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        if (unlikely(signal_pending_state(prev->state, prev)))
            prev->state = TASK_RUNNING;
        else
            deactivate_task(rq, prev, DEQUEUE_SLEEP);
        switch_count = &prev->nvcsw;
    }

prev就是当前要被调度下cpu的进程。prev->state为0表示TASK_RUNNING的状态。
如果进程的状态不是TASK_RUNNING并且PREEMPT_ACTIVE标志没有被设置，再判断进程是否有pending的信号，如果有，就把进程状态设置成TASK_RUNNING状态，
如果没有pending的信号，就把进程从RUNNING的进程队列里拿下来。

因此，逻辑关系是这样的：
如果PREEMPT_ACTIVE被设置了，说明进程是由于内核抢占被调度下CPU的，这时不
把它从RUNNING的队列里移除，如果进程不是由于内核抢占被调度下来的，看它
有没有未处理的信号，如果有的话，也不把它从RUNNING的队列里移除。只有再
上述两种情况都为假的情况下，进程才会被从RUNNING的队列里移除。

这就解释了为什么内核线程把自己设置成TASK_INTERRUPTIBLE状态之后，只要不
是主动调用schedule()函数，而是被抢占调度下cpu的，它就还会获得机会运行。

linux内核的cfq IO调度算法的tuning参数

                              cfq_tuning
                              ==========

Author: yu peng
Date: 2012-07-27 19:58:01 HKT


Table of Contents
=================
1 概要
2 back_seek_max 和 back_seek_penalty
3 slice_async，slice_sync，和 slice_async_rq
4 low_latency
5 quantum
6 fifo_expire_async 和 fifo_expire_sync
7 slice_idle
8 group_idle
9 group_isolation


1 概要
-------
  以rhel6系统所用的2.6.32内核为基础，分析cfq io调度器的tuning参数。

2 back_seek_max 和 back_seek_penalty
-------------------------------------
  这两个参数是用来确定，对于给定的两个IO，哪个更适合作为“下一个”IO被
  传送给设备。判定的方法就是谁距离磁头更近。磁头的位置就是上一次IO完成
  的位置。比如磁头的位置last是sector 100。两个IO，io1的起始扇区号是105，
  io2的起始扇区号是110那么，io1距离磁头更近，下一次要发送IO，就先发io1，
  再发io2。
  如果io1的起始扇区号是90，io2的起始扇区号是110呢？两个io距离磁头的距离
  都是10，这时该如何选择呢？一般来说，把磁头向前移动（从扇区100向扇区
  90移动）需要花费的时间要多一些，所以cfq倾向于选择向后移动（从扇区100
  向扇区110移动）。
  如果io1的起始扇区号是95，io2的起始扇区号是110呢？虽然io1在磁头的前面，
  io2在磁头的后面，但io1距离磁头更近一些，这时该如何选择呢？具体的判断
  方法就用到了back_seek_penalty。比如io1在磁头的前面，距离磁头的距离是
  s1，io2在磁头的后面，距离磁头的距离是s2，如果s1*back_seek_penalty小于
  s2，就认为io1距离磁头比较近，否则，就认为io2距离磁头比较近。
  如果io1在磁头的前面，而io2在磁头的后面，但io1距离磁头太远了，超过了
  back_seek_max，那么无论io2是不是距离磁头更远，都选择io2。

3 slice_async，slice_sync，和 slice_async_rq
---------------------------------------------
  每个进程发下来的IO都被分成三类：异步，同步，idle。cfq先处理所有进程
  发下来的同步IO，然后处理所有进程发下来的异步IO,最后处理idle IO。进一
  步的，同步和异步的IO又被分别分成了8个不同等级的优先级。同一个进程发
  送下来的同步IO，都有同样的优先级，异步的也是如此。对于每个进程的IO，
  都被组织到一个叫做cfq_queue的结构体中。对于一个进程发送下来的IO，所
  有的同步IO有一个cfq_queue，所有的异步IO有另一个cfq_queue。cfq会给每
  个cfq_queue都分配一个时间片。比如当一个进程的同步IO的时间片用完后，就
  开始发送另一个进程的同步IO。时间片的大小由两个因素决定，一个是IO的优
  先级，这是和进程的IO优先级相关的，如果进程没有设置IO优先级，就按照
  nice值成正比计算出一个，另一个因素就是slice_async和slice_sync这两个
  参数。如果这两个参数越大，那么所有异步和同步IO的时间片粒度就越大，反
  之则粒度越小。对于异步IO，还有一个限制，如果在一个时间片内，已经发送
  的异步IO总数大于slice_async_rq，那么也视为时间片到期。idle类型的IO没
  有时间片，每次只发送一个。
  注意，这里说的异步IO和linux内核提供的AIO机制是两码事，一点关系都没有。
  一般来说，用户进程发送的读操作和设置direct标志的写操作都是sync类型的
  IO，普通的写操作会写道cache里面，再由内核进程通过cache发送到IO调度器
  的是async类型的IO。

4 low_latency
--------------
  如果这个参数被设置了，那么当前面计算出的cfq_queue的时间片大于
  low_latency时，会把时间片强行设置为low_latency。

5 quantum
----------
  除了idle类型的IO是一个一个的放到块设备的queue里面之外，sync和async类
  型的IO每次都是批量放入queue里面的。quantum就是一次批处理的数量。

6 fifo_expire_async 和 fifo_expire_sync
----------------------------------------
  cfq对不同进程发下来的IO分时间片进行处理，但在处理同一个进程发下来的
  IO时，采用与dead line类似的做法。尽量按照减小磁头移动的方式选择IO，
  但如果有些IO等待的时间太久了的话，就转而处理这些等待太久的IO。
  fifo_expire_async和fifo_expire_sync就是分别用来设置async类型IO和sync
  类型IO的超时时间的。

7 slice_idle
-------------
  在cfq中，最后被处理的IO是idle类型的IO，当调度器中已经没有任何的同步
  或异步类型的IO，并且这种状况已经持续了slice_idle这么长的时间，那么
  cfq就认为现在处于idle状态了，就发送一个idle类型的IO，然后再等待
  slice_idle这么长的时间，如果还是没有其他IO，就再发送一个idle类型的IO。
  补充一下，这个参数，以及所有本文中提到的和时间有关的参数，单位都是毫秒。

8 group_idle
-------------
  我的理解，不一定准确：
  当这个参数被设置之后，每当属于一个cgroup的进程的IO都提交完了，但时间
  片还没有耗尽，那么不会马上提交属于另一个cgroup的IO，而是会等待
  group_idle这么长的时间，如果在这个时间段内，该cgroup又有IO提交了进来，
  那么就继续处理。
  这个参数的引入是为了针对磁盘阵列或者固态硬盘这样的设备做优化用的，参
  看这篇文章：
  [http://lwn.net/Articles/395769/]
  以及内核文档blkio-controller.txt中的描述：
CFQ sysfs tunable
=================
/sys/block/<disk>/queue/iosched/slice_idle
------------------------------------------
On a faster hardware CFQ can be slow, especially with sequential workload.
This happens because CFQ idles on a single queue and single queue might not
drive deeper request queue depths to keep the storage busy. In such scenarios
one can try setting slice_idle=0 and that would switch CFQ to IOPS
(IO operations per second) mode on NCQ supporting hardware.

That means CFQ will not idle between cfq queues of a cfq group and hence be
able to driver higher queue depth and achieve better throughput. That also
means that cfq provides fairness among groups in terms of IOPS and not in
terms of disk time.

/sys/block/<disk>/queue/iosched/group_idle
------------------------------------------
If one disables idling on individual cfq queues and cfq service trees by
setting slice_idle=0, group_idle kicks in. That means CFQ will still idle
on the group in an attempt to provide fairness among groups.

By default group_idle is same as slice_idle and does not do anything if
slice_idle is enabled.

One can experience an overall throughput drop if you have created multiple
groups and put applications in that group which are not driving enough
IO to keep disk busy. In that case set group_idle=0, and CFQ will not idle
on individual groups and throughput should improve.

What works
==========
- Currently only sync IO queues are support. All the buffered writes are
  still system wide and not per group. Hence we will not see service
  differentiation between buffered writes between groups.

  在高速存储上，这样一组经验值可以获得较好的性能：
  slice_idle = 0
  quantum = 64
  group_idle = 1
  这些值在/sys/block/devicename/queue/iosched/中可以找到。

9 group_isolation
------------------
kernel document中有一个blkio-controller.txt文件，对这个参数做出了解释，
将其原文摘抄如下：
CFQ sysfs tunable
=================
/sys/block/<disk>/queue/iosched/group_isolation

If group_isolation=1, it provides stronger isolation between groups at the
expense of throughput. By default group_isolation is 1. In general that
means that if group_isolation=0, expect fairness for sequential workload
only. Set group_isolation=1 to see fairness for random IO workload also.

Generally CFQ will put random seeky workload in sync-noidle category. CFQ
will disable idling on these queues and it does a collective idling on group
of such queues. Generally these are slow moving queues and if there is a
sync-noidle service tree in each group, that group gets exclusive access to
disk for certain period. That means it will bring the throughput down if
group does not have enough IO to drive deeper queue depths and utilize disk
capacity to the fullest in the slice allocated to it. But the flip side is
that even a random reader should get better latencies and overall throughput
if there are lots of sequential readers/sync-idle workload running in the
system.

If group_isolation=0, then CFQ automatically moves all the random seeky queues
in the root group. That means there will be no service differentiation for
that kind of workload. This leads to better throughput as we do collective
idling on root sync-noidle tree.

我的理解，不一定准确：
cfq支持cgroup机制，可以区别对待属于不同cgroup的进程发下的io，给他们分
配不同的带宽。但这样会对效率造成比较大的影响。因为每个进程发送下来的读
写请求的位置可能差别很大，这样就会造成磁盘磁头来回的移动。所以，cfq提
供了这样一个参数，当group_isolation为0的时候，就把所有属于
SYNC_NOIDLE_WORKLOAD类型的cfq_queue都移动到root_group这个cgroup中。每
个进程都有几个它自己的cfq_queue，进程发送下来的IO，会根据IO的种类分别
放到不同的cfq_queue中去。从这个函数里我们可以看到怎么判断cfq_queue的种
类：
static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
{
        if (!cfq_cfqq_sync(cfqq))
                return ASYNC_WORKLOAD;
        if (!cfq_cfqq_idle_window(cfqq))
                return SYNC_NOIDLE_WORKLOAD;
        return SYNC_WORKLOAD;
}
如果cfq_queue里面放的是同步的IO,那么它就是ASYNC_WORKLOAD类的，如果
cfq_queue里面放的不是idle类型的IO（优先级最低的一种IO，只在空闲时才处
理），那么它就是SYNC_NOIDLE_WORKLOAD类型的，否则（也就是idle类型的IO），它
就是SYNC_WORKLOAD类型的。

cfq io调度算法简介

本文以rhel5.6所使用的2.6.18内核进行分析。

1 cfq用到的几个数据结构
~~~~~~~~~~~~~~~~~~~~~~~~
  在cfq中，进程被按照优先级分组。cfq尽量优先处理高优先级组中的请求，同
  时也避免低优先级组中的请求被饿死。一个进程可能同时向多个不同的块设备
  提交io请求，而一个使用cfq调度算法的块设备又要处理多个进程中传下来的
  请求，并将它们分组。所以，cfq使用下面这些数据结构分别描述进程，优先
  级组，以及一个cfq块设备。

1.1 struct io_context
======================
   每个进程都有一个io_context结构体，从其定义中包含
   struct as_io_context *aic;
   和
   struct rb_root cic_root;
   这两位来看，它是专为as和cfq两个io调度算法准备的，在cfq中，它是
   struct cfq_io_context的基类。

1.2 struct cfq_io_context
==========================
   cfq_io_context是cfq中为每个进程分配的结构体，继承自io_context。每个
   进程都只有一个io_context，但它同时向多少个使用cfq调度算法的块设备提
   交io请求，就会有多少个cfq_io_context，这些个cfq_io_context被组织在
   一个红黑树中，树根是io_context中的cic_root，cfq_io_context中的"void
   *key"位用作红黑树的键值。由于每个cfq_io_context对应一个使用cfq调度
   算法的块设备，所以实际上cfq使用struct cfq_data结构体的地址作为键值，
   每个使用cfq算法的块设备都有唯一的一个struct cfq_data结构体。

1.3 struct cfq_queue
=====================
   当多个进程向同一个块设备提交io请求的时候，cfq会对进程按照优先级进行
   分组，进程的优先级信息存储在进程结构体的"unsigned short ioprio"位中，
   如果该位没有进行设置，cfq按照进程的nice值计算出一个优先级。默认共有
   8个优先级，对于每个优先级组，使用一个cfq_queue结构体进行表示。

1.4 struct cfq_data
====================
   每个使用cfq调度算法的块设备都有一个cfq_data结构，保存在struct
   elevator_queue的void *elevator_data位中。

1.5 struct cfq_rq
==================
   每个request都有一个cfq_rq，保存在request的void *elevator_private位
   中。

2 cfq_set_request函数
~~~~~~~~~~~~~~~~~~~~~~
  每当有一个新的io请求提交之后，电梯算法都会调用cfq_set_request函数让
  cfq为该请求分配必要的资源。
  首先调用cfq_get_io_context函数获取一个struct cfq_io_context结构，如
  果没有的话cfq_get_io_context函数会分配一个新的。
  接下来看cfq_io_context的"struct cfq_queue *cfqq"位有没有包含一个
  struct cfq_queue，如果没有的话就调用cfq_get_queue函数。
  cfq_get_queue函数计算当前进程的io优先级，并检察当前块设备的struct
  cfq_data结构中有没有对应该优先级的cfq_queue，有的话就返回，没有的话
  就分配一个新的。然后调用cic_set_cfqq函数让当前进程的cfq_io_context指
  向该cfq_queue。
  接下来分配一个新的对应于当前请求的struct cfq_rq结构。

3 cfq_insert_request函数
~~~~~~~~~~~~~~~~~~~~~~~~~
  调用完cfq_set_request函数后，电梯算法会调用cfq_insert_request将新提
  交的请求插入到cfq的数据结构中。
  首先检查cfq_queue的优先级是否改变，如果改变将相应的信息更新。然后将
  该请求对应的cfq_rq插入到以cfq_queue的"struct rb_root sort_list"为根
  的红黑树中。将请求按照提交时间的先后顺序放到cfq_queue的fifo链表上，
  如果该请求是可合并的，则将请求放到cfq_data的哈希表中，在合并请求时，
  会用到该哈希表。最后，调用cfq_crq_enqueued函数更新一些时间戳以及统计
  信息。

4 cfq_dispatch_requests函数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  每当电梯算法要补充一些请求到请求队列上的时候，会调用
  cfq_dispatch_request函数。
  首先调用cfq_select_queue选择一个优先级队列，然后调
  用__cfq_dispatch_requests函数将该优先级队列上的一部分请求放到请求队
  列上。
  选择优先级队列时，总是从最高等级的优先级队列开始选择，但每个等级都有
  一个时间片，如果该等级的时间片到期，则选择下一个等级的队列。

5 merge
~~~~~~~~

5.1 cfq_merge函数
==================
   电梯算法调用cfq_merge函数判断一个新的请求是否能和以前的请求合并。
   首先判断是否能进行后向合并。cfq_data中有一个哈希表，储存了所有可以
   合并的请求，并且以请求的结束扇区号作为键值。所以，以当前请求的起始
   扇区号作为键值进行搜索，如果能够搜到一个请求，则说明搜到的请求的结
   束扇区号和当前请求的起始扇区号相等，可以进行后向合并。
   如果没有找到能够进行后向合并的请求，则尝试寻找是否有能进行前向合并
   的请求。以当前请求的结束扇区号为键值，在与当前请求的io优先级相等的
   cfq_queue的红黑树中寻找。由于该红黑树中的成员是以请求的起始扇区号为
   键值的，如果找到，说明可以进行前向合并。
   cfq_merge的返回值会告诉调用它的函数是可以进行前向合并，还是后向合并，
   还算不可以合并。如果可以合并，会将可用来合并的请求放到struct
   request **req中返回。

5.2 cfq_merged_request函数
===========================
   所谓合并，就是将一个新传递进来的bio放到一个以前的request中。实际的
   合并操作是在ll_rw_blc.c和elevator.c中完成的。在合并完成之后，电梯算
   法会调用cfq_merged_request函数让cfq进行一些必要的更新。由于进行了合
   并，request的起始扇区号和结束扇区号可能会发生变化，而cfq内部所用的
   哈希表以及红黑树是以这两个值作为键值的。所以,cfq_merged_request的作
   用就是检验这两个值是否变化，若变化了则以新的键值放置相应的数据结构
   成员

linux的deadline io 调度算法分析

1 linux的deadline io 调度算法分析
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  以rhel5.6系统（kernel version 2.6.18）为基础分析linux内核的块设备层
  的deadline io 调度算法。

2 把bio添加到请求中以及把请求添加到请求队列中
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2.1 最简单的情况，请求队列中一个请求都没有的时候，添加第一个bio
================================================================
   bio通过generic_make_request函数传递进来。generic_make_request函数会
   调用请求队列的make_request_fn函数指针完成实际的io操作。如果使用电梯
   算法，请求队列的make_request_fn函数指针将指向__make_request函数。
   我们只考虑与电梯算法相关的部分。

   首先，调用elv_merge函数检查是否可以将当前的bio合并到以前的request
   中。如果是第一次执行到这里，当然没有可以合并的request，于是调用
   get_request_wait函数获取一个新的request，然后调用
   init_request_from_bio函数将bio添加到request中。接下来调用
   add_request函数将request添加到request_queue中。

   add_request中的函数调用流程：
   add_request->__elv_add_request->elv_insert
   elv_insert函数会将新创建的request挂到request_queue的queue_head链表
   上，并让request_queue的last_merge指针指向当前的request。最
   后，elv_insert函数会调用到函数指针：
   q->elevator->ops->elevator_add_req_fn
   如果deadline是该块设备的io调度算法的话，这个指针就指向了
   deadline_add_request函数。

   deadline算法中有两个红黑树（读写请求各有一个），两个双向链表（读写
   请求各有一个），一个哈希表（所有读写请求都在同一个哈希表上）。

   deadline_add_request函数会将传递进来的request添加到与请求的读写方
   向相对应的红黑树与双向链表中，以及哈希表上。同时，也记录下这个请求
   的到期时间。

   deadline中的红黑树以起始扇区号作为键值进行排序。双向链表按照request提
   交进来的先后顺序进行排序，最先加进来的request放在链表的头部。因此，每
   新添加一个请求的时候，都放在链表的尾部。哈希表使用request的结束扇
   区号（即rq->sector + rq->nr_sectors）作为键值进行索引。读请求的期
   满值默认为0.5秒，写请求的期满值默认为5秒。在合并与分发请求时，我们
   会看到deadline算法如何使用这些数据。

   调用完add_request函数后，__make_request的任务基本就结束了。每一个
   请求队列，在真正处理请求的时候都会有一个延迟，一般默认设为3毫秒。
   如果这3毫秒内又有request到来，则将该请求提交给io调度算法，并重新设
   置延迟的期满时间为3毫秒。

2.2 将bio merge到request中
===========================
   每当一个bio提交到__make_request函数中的时候，该函数总是调用
   elv_merge函数检查是否能将当前的bio合并到以前的request中。elv_merge
   函数分两步进行判断。

   第一步，判断判断bio是否可以合并到request_queue的last_merge指针指向
   的request。last_merge总是指向上一次提交进来的请求。如果进行连续读
   写的话，这是可能性最大的情况。判断的方法很简单，首先看request的结
   尾扇区号是否等于bio的起始扇区号，如果是的话就能够进行back merge，
   然后判断request的起始扇区号是否等于bio的结尾扇区号，如果是的话就能
   够进行front merge。

   第二步，如果bio不能和last_merge指向的request进行合并的话，则调用io
   调度算法的elevator_merge_fn成员函数，判断bio是否能和某个request进
   行合并。

   对于deadline调度算法，elevator_merge_fn指向deadline_merge函数。该
   函数首先判断是否能进行back merge。以bio的起始扇区号为键值在哈希表
   中寻找。由于deadline中的哈希表是以request的结束扇区号为键值的，所
   以如果找到这样的request的话，说明这个request的结语扇区号与bio的起
   始扇区号相等，因此bio可以back merge到这个request中。如果没有找到这
   样的request，说明无法进行back merge，则继续尝试能否进行front merge。
   方法是以bio的结束扇区号为键值在红黑树中进行搜索。红黑树是以request
   的起始扇区号为键值进行排序的，因此，如果找到符合条件的request，说
   明该request的起始扇区号等于bio的结束扇区号，可以进行front merge。
   无论是back merge还是front merge，如果找到符合条件的request的话，都
   要把request从哈希表上拿下来，再按照新的键值重新放上去，至于红黑树，会
   在后续的操作中进行处理。

   若是可以进行合并，elv_merge会返回用来合并的request指针，并且，通过
   返回值表示是何种合并，ELEVATOR_BACK_MERGE表示back merge，
   ELEVATOR_FRONT_MERGE表示front merge，ELEVATOR_NO_MERGE表示无法进行
   合并。

2.2.1 back merge
-----------------
    若是进行back merge，则调用函数指针q->back_merge_fn对request_queue
    和request进行一些必要的处理，这个指针通常指向ll_back_merge_fn函数。
    然后修改request的biotail，biotail->next，以及nr_sector等位，将bio
    添加到request中。接下来调用attempt_back_merge函数，该函数的作用是
    检查是否可以进一步的进行合并，例如，原先请求队列中有这样两个请
    求，request1写块设备的secotr0到sector4，request2写块设备的
    sector 8到sector 12。现在新加入的bio写sector5到sector7，bio被合并
    到了request1中，request1变成写sector0到sector7，此时，request1和
    request2可以进行合并了。若发生这种情况，attempt_back_merge函数会
    进行处理，若没有，则调用elv_merged_request函数进行最后的收尾处理。
    该函数会调用调度器的elevator_merged_fn方法，对于deadline调度器，
    该方法指向deadline_merged_request函数。该函数的作用很简单，由于进
    行了合并，request的起始扇区号和结束扇区号可能改变了，用新的扇区号
    做键值更新request在哈希表和红黑树中的位置。

2.2.2 front merge
------------------
    与back merge的处理基本对称，不再赘述。

3 从请求队列中取出一个请求
~~~~~~~~~~~~~~~~~~~~~~~~~~~
  正常情况下，每当request_queue等待3毫秒还没有新的bio提交后，就会出发
  unplug，最终会调到request_queue的request_fn方法。以scsi磁盘驱动为
  例，该方法指向scsi_request_fn函数。scsi_request_fn会调用
  elv_next_request函数来从请求队列中取出一个请求进行处理。而该函数会
  调用__elv_next_request找出一个合适的请求。

  __elv_next_request函数首先从request_queue的queue_head链表上寻找
  request，如果找到的话就返回这个request，没找到的话就调用调度器的
  elevator_dispatch_fn方法，通常，这个方法会将一些request放到
  queue_head链表上。然后再检查request_queue的queue_head链表。一直循
  环，直到从queue_head上找到一个request，将其返回，或者
  elevator_dispatch_fn方法返回0，则__elv_next_request函数返回一个空指
  针。

  对于deadline调度器来说，elevator_dispatch_fn函数指针指向
  deadline_dispatch_requests函数。

  deadline_dispatch_requests函数负责从已经提交给调度器的request中选择
  一个放到request_queue的queue_head链表中。

  为了优化读写磁盘的效率，deadline调度器会对请求进行批处理，每当选定
  一个请求方向时（读或写），总是连续处理该方向上的16个请求。然后才重
  新选择另一个方向上的请求。当然，如果某个方向上已经没有请求了，则马
  上选择另一个方向上的请求。

  每当处理了一个方向上的请求，就将该方向上的下一个请求放到
  next_drq[WRITE]中或next_drq[READ]中。因此，当进入
  deadline_dispatch_requests函数的时候，首先判断next_drq[WRITE]或
  next_drq[READ]是否为空，这两个指针至多有一个不为空。如果其中有一个
  不为空，我们就获得了一个request。接下来判断这个request和上一次发送
  的请求是否是连续的，若不是连续的，则打破批处理，然后判断当前的批处
  理进行了多少次，如果超过了最大的允许次数，也要打破批处理，重新选择
  request。这是为了防止在某一个方向上有大量连续的request，导致饿死了
  另一个方向上的request。

  如果确定要继续批处理，则直接跳到函数的末尾，即标签
  “dispatch_find_request”处，递增批处理的统计次数，将同方向上的下一个
  请求放到next_drq[WRITE]或next_drq[READ]中，记录当前request的结束扇区
  号，以便再进入本函数时判断下一个request是否和当前这个是连续的。最后
  把这个请求从deadline算法内部维护的哈希表，红黑数和链表上面移除，放到
  request_queue的queue_head链表上。

  如果前面判断不进行批处理，则先看是否有读请求需要处理。若读写请求都
  有的话，就把starved变量加一，表示忽略了一次写请求。如果忽略的写请求
  次数超过了变量writes_starved的值（默认为2），那么就不再忽略写请求，
  跳转到标签“dispatch_writes”的位置，将变量data_dir设为WRITE，表示提
  交一个写请求。否则将data_dir设为READ，表示提交一个读请求。

  现在已经选择了request的方向（READ或WRITE），接下来判断在该方向上最
  先进来的request是否已经超时了，或者该方向上还有没有request的起始扇
  区号比上一个请求更靠后的request了（这样的request即使不连续也可以让
  磁盘的磁头大体上朝一个方向移动）。如果两个条件中有一个条件为真，就
  选择该方向上时间最早的request提交。如果这两个条件都为假的话，即没有
  任何请求超时，而且有一个起始扇区号比上一个request大的请求，就提交这
  个请求。

  完。

linux内核中SH_DIV宏分析

在读linux内核中关于时钟部分的代码时，遇到了一个叫SH_DIV的宏，它包含的
技巧颇为有趣。自己写代码时可能用得到。

下面是这个宏的注释和定义：

/* Suppose we want to devide two numbers NOM and DEN: NOM/DEN, the we can
 * improve accuracy by shifting LSH bits, hence calculating:
 *     (NOM << LSH) / DEN
 * This however means trouble for large NOM, because (NOM << LSH) may no
 * longer fit in 32 bits. The following way of calculating this gives us
 * some slack, under the following conditions:
 *   - (NOM / DEN) fits in (32 - LSH) bits.
 *   - (NOM % DEN) fits in (32 - LSH) bits.
 */
#define SH_DIV(NOM,DEN,LSH) (   (((NOM) / (DEN)) << (LSH))              \
                             + ((((NOM) % (DEN)) << (LSH)) + (DEN) / 2) / (DEN))


计算 (N << L) / D，可以等价于下面的算式：
(N / D) << L + ( (N % D) << L + (D / 2) ) / D

下面是推导过程：

N = (N / D) * D + (N % D)

N << L = N * 2^L
       = ( (N / D) * D + (N % D) ) * 2^L
       = (N / D) * D * 2^L + (N % D) * 2^L

(N << L) / D = ( (N / D) * D * 2^L + (N % D) * 2^L ) / D
             = ( (N / D) * D * 2^L ) / D + ( (N % D) * 2^L ) / D
         = (N / D) * 2^L + ( (N % D) * 2^L ) / D
         = (N / D) << L + ( (N % D) << L ) / D

这时与最终的等式只差一个(D / 2)，当在C语言中进行除法运算(N / D)时，结
果总是向下取整，余数部分全都被舍去了，因此，在计算除法前给被除数加上除
数的一半，可以起到四舍五入的效果，即：(N + (D / 2)) / D。
所以，在前面推导过程的最后一步时，在除以D前要加上(D / 2)，即：
(N << L) / D = (N / D) << L + ( (N % D) << L + (D / 2) ) / D

甄姬洛神后摸桃子的概率

我考虑的是这样一种情况： 不包括任何扩展牌，牌堆中共104张牌，52红，52黑，红牌中有8张桃子。牌洗好 后甄姬开始洛神，直到洛神失败，然后抓两张牌。计算这种情况下甄姬至少摸到 一张桃子的概率。 首先，看白板武将至少摸到一张桃子的概率如何计算 ： 先 计算白板武将一张桃子都摸不到的概率，然后用1减去它得到的就是至少摸到 一张桃子的概率。白板武将摸两张牌，相当于从104张牌中随机抽出两张牌，共有 104*103种抽法。不是桃子的牌共有96张，抽出两张不是桃子的牌，共有96*95种 抽法。所以，白板武将摸不到桃子的概率p1 = (96*95)/(104*103)。1-p1得到的 就是白板武将至少摸到一张桃子的概率。 为了给计算甄姬摸桃子的概率做铺垫，再考虑另一种计算白板武将摸桃子的概率。 还是先考虑一张桃子的摸不到的概率。 104 张牌进行排列组合，共有104的阶乘，即104!种排列方法。再看看前两张牌都 不是桃子共有多少种排列方法：先从96张不是桃子的牌中取一张放在最上面， 再 从剩下的95张不是桃子的牌中取1张放在牌库顶的第二张，再将剩下的102张牌任 意排列，共有：96*95*102!种排列方法。因此，白板武将摸不到 桃子的概率p1 = (96*95*102!)/(104!) = (96*95)/(104*103)与前一种方法的计算结果一致。 现在，我们来看甄姬洛神直到失败后，至少摸到一张桃子的概率。依然，我们还 是计算甄姬一张桃子都摸不到的概率，然后用1减去它得到甄姬至少摸到一张桃子 的概率。 104张牌进行排列组合，共有104!种排列方法。 甄姬洛神后抓牌，共有如下这么多种可能： 0 洛神到0张黑牌，即一张牌都没洛到。0.1 洛神的判定牌不是桃子从 44张不是 桃子的牌中任选一张放在牌库顶，不是桃子的牌共96张，其中有一张红的作为判 定牌放在牌库顶了，从剩下的95张中选一张放在牌库顶的第二张的位 置，再从剩 下的94张中选一张放在第三张的位置（我们现在计算的是1张桃子都摸不到的概率， 所以从不是桃子的牌中选2张给甄姬摸），1张放在了牌库顶，不 是桃子的牌中选 出了两张给甄姬摸，总共104张牌，还剩101张牌可以任意排列，共有101!种排列 方法。因此，洛神第一张就是红色，并且不是桃子共有这末多种情况：44 * 95 * 94 * 101!  0.2 洛神的判定牌是桃子与0.1的算法类似，从8张桃子中选一 张放在牌库顶，然后从96张不是桃子的牌中选1张放在牌库顶第二张，再从剩下的 95张不是桃子的牌中选一张放在牌库顶第三张，剩下的101张牌任意排列，共有这 末多种情况：8 * 96 * 95 * 101! 1 洛神到1张黑牌。从52张黑牌中选1张放到牌库顶，共有52种情况，接下来： 1.1 判定牌不是桃子从44张不是桃子的红牌中选1张放到洛神的牌后面，洛神1张 牌加上判定牌1张，还剩94张不是桃子的牌，从中选一张放在判定牌后面，再从剩 下的93张不是桃子的牌中选一张放在后面，此时包括桃子总共还剩100张牌，可以 任意排列，于是共有这末多种情况：52 * 44 * 94 * 93 * 100!  1.2 判定牌是 桃子从8张桃子中选1张放到洛神的牌后面，除去洛神的1张牌，还有95张牌不是桃 子，从中选1张放到判定牌后面，再从剩下的94张不是桃子的牌中选1张放到后面， 然后剩下的100张牌任意排列，共有这末多种情况：52 * 8 * 95 * 94 * 100! 2 洛神到2张黑牌从52张黑牌中选1张放到牌库顶，再从剩下的51张黑牌中选1张放 到牌库顶第二张，共有52*51种情况2.1 判定牌不是桃子从44张不是桃子的红牌中 选1张放到洛神的牌后面，洛神2张加上判定牌1张，还剩93张不是桃子的牌，从中 选1张放到判定牌后面，再从剩下的92张不是桃子的牌中选1张放到后面，一共还 剩99张牌，可以任意排列，共有这末多种情况：(52 * 51) * 44 * 93 * 92 * 99!  2.2 判定牌是桃子从8张桃子中选1张放到洛神的牌后面，除去洛神2张牌， 还剩94张不是桃子的牌，从中选1张放到判定牌后面，再从剩下的93张不是桃子的 牌中选1张放到后面，一共还剩99张牌，可以任意排列，共有这末多种情况： (52 * 51) * 8 * 94 * 93 * 99! 依此类推，可以得到： 3 洛神到3张黑牌从52张牌中选3张放到牌库顶，共有52 * 51 * 50种情况3.1 判 定牌不是桃子(52 * 51 * 50) * 44 * 92 * 91 * 98!  3.2 判定牌是桃子 (52 * 51 * 50) * 8 * 93 * 92 * 98! ...... 51 洛神到51张黑牌从52张牌中选51张放到牌库顶，共有52 * 51 * 50 * ...... * 2种情况51.1 判定牌不是桃子(52 * 51 * ... * 2) * 44 * 44 * 43 * 50!  51.2 判定牌是桃子(52 * 51 * ... * 2) * 8 * 45 * 44 * 50! 52 洛神到52张黑牌52.1 判定牌是桃子(52 * 51 * ... * 2 * 1) * 44 * 43 * 42 * 49!  52.2 判定牌不是桃子(52 * 51 * ... * 2 * 1) * 8 * 44 * 43 * 49! 将上面的所有情况相加，得到的就是所有洛神后摸不到桃子的情况。经计算得到， 洛神后摸不到桃子共有这末多种情况： no_peach = 8768393644112035467653013895319007081912845854144094315049335792122609241987921866302232452367163796631068635340901979516433835590933660303360000000000000000000000000 又由于104张牌全排列共有104!种情况 因此，甄姬摸不到桃子的概率p2 = no_peach / 104! no_peach刚好可以被102!整除，因此计算p2时分子分母同时约去102! 得到：p2 = 9120 / (104 * 103) = (96 * 95) / (104 * 103) = p1 即，甄姬洛神后摸不到桃子的概率，和白板武将摸两张牌后摸不到桃子的概率是 一样的，所以，他们至少摸到1张桃子的概率也是一样的，均为1 - (96 * 95) / (104 * 103)，约等于0.148618371919。 我把计算no_peach的值的程序放到github上了 https://github.com/yupeng820921/luoshen calc.py 是个python写的小程序。