Linux 0.12源码阅读之进程调度(一): 多任务管理

| 分类 linux  | 标签 linux 

1.80X86的多任务管理体系

Linux 0.12只支持80X86体系结构，非常依赖X86提供的多任务管理体系，X86体系结构中最为重要的是内存的分段和分页，中断和异常处理，以及构建在这个基础上的保护机制。首先来看X86体系结构中几个非常重要的概念：

  • 段描述符：描述了一个内存段, 具体的是BASE Address + Limit + 其他信息
  • 段选择符：选择了一个段描述符，具体的是段描述符index + TI+ RPL(TI: 0 GDT/1 LDT RPL:权限保护)。
  • IDT描述符: 一个中断向量对应的处理函数代码，具体的是段选择符 + offset +其他信息

1.2.GDT, LDT和IDT.

80X86提供了GDTR, LDTR, IDTR, TR等用来做多任务管理的寄存器. 在linux0.12中，GDTR和IDTR初始化以后都不会改变，在任务切换的时候TR和LDTR会随着任务的切换改变，对应CPU就会在任务代码直接切换。

  • GDTR(32 bits BASE + 16 bits limit)用来选择GDT,
  • LDTR(16 bits + 32 bits hidden)用来选择GDT中的某一项LDT
  • IDTR(32 bits BASE + 16 bits limit)用来选择IDT
  • TR(16 bits + 32 bits hidden)用来选择GDT中的某一项TSS

GDT里面的信息每一条是一个段(segment)，可以有CS, DS, TSS, LDT等。LDT里面的信息每一条页是一个段(segment)，不过只可以有CS, DS。 BASE代表的是一个32bit线性地址。GDT/LDT将内存分段。至于线性地址到物理地址的映射，由分页机制完成。Linux在初始化内存时，将物理内存16M一共1024*4个页面，一一映射到pg_dir 和pg0,pg1,pg2,pg3中。也就是说，初始化完成了线性地址空间0-16M到物理地址的映射。所以在GDT中写入的物理地址作为BASE，可以通过查找页目录表和页表，定位到具体的物理地址。

GDT CS/DS的BASE=0， GDT LDT/TSS的BASE为4M-16M的线性地址(==物理地址)。LDT 的BASE为线性地址 nr*64M，映射到4M-16M的物理地址(+swap)。而nr*64M的线性地址到物理地址的映射并不在初始化之内，所以任务初始化时需要将线性地址nr*64M到实际的物理地址映射的存储(即页表pgX)生成，并加到pg_dir中。而后续的线性地址到物理内存之间的映射，包括页表在内存中得生成等是由内存管理模块完成的。

IDT 里面的每一条代表的是程序入口(segment:offset)，其中segment index必须是GDT里面的。Intel X86体系中有中断和异常之分，

  • 中断发生在程序执行的任意时刻，一般来自外部硬件产生得事件，例如磁盘，网卡等I/O设备中断，中断一般和执行指令没有直接的关系，可以理解中断是Asynchronous(异步)的。
  • 异常一般是执行指令时由处理器捕捉到的错误，分为Fault, Trap和Aborts。另外一种异常是软中断/系统调用，用来和系统内核交互。 异常和执行指令有直接关系，比如执行了错误的指令，调用int系统调用等。从这层意义上理解可以说异常是同步(Synchronous)的。
    -- Faults — correctable; offending instruction is retried
    -- Traps — often for debugging; instruction is not retried
    -- Aborts — major error (hardware failure)

Linux0.12中主要使用了中断门和陷阱们，IDT中断描述符有3种

  • interupte_gate dpl:00(仅对内核态开放) type:01110(interrupt gate IF=0)
    0x20 timer_interrupt
    0x23 rs2_interupt
    0x24 rs1_interrupt
    0x2E hd_interupt
  • trap_gate dpl:00(仅对内核态开放) type:01111 (trap gate IF=1)
    00 divide_error
    01 debug
    02 nmi
    ...
    06 invalid_op
    ...
    14 page_fault
    ...
    0x26 flooy_interrupt
    39 parallel_interrupt
  • system_gate dpl:11(用户态开放) type:01111 (trap gate IF=1)
    0x03 int3
    0x04 overflow
    0x05 bounds
    0x80 system_call

在traps.c中初始化

set_trap_gate(0,&divide_error);
set_trap_gate(1,&debug);
set_trap_gate(2,&nmi);
set_system_gate(3,&int3);   /* int3-5 can be called from all */
set_system_gate(4,&overflow);
set_system_gate(5,&bounds);
set_trap_gate(6,&invalid_op);
set_trap_gate(7,&device_not_available);
set_trap_gate(8,&double_fault);
set_trap_gate(9,&coprocessor_segment_overrun);
set_trap_gate(10,&invalid_TSS);
set_trap_gate(11,&segment_not_present);
set_trap_gate(12,&stack_segment);
set_trap_gate(13,&general_protection);
set_trap_gate(14,&page_fault);
set_trap_gate(15,&reserved);
set_trap_gate(16,&coprocessor_error);
set_trap_gate(17,&alignment_check);
for (i=18;i<48;i++)
    set_trap_gate(i,&reserved);
set_trap_gate(45,&irq13);
outb_p(inb_p(0x21)&0xfb,0x21);
outb(inb_p(0xA1)&0xdf,0xA1);
set_trap_gate(39,&parallel_interrupt);

IF=0表示中断当前中断线上的屏蔽，会对当前同一中断线在所有处理器上屏蔽掉，这样可以防止同一中断线上接收另一个新的中断。通常情况下，所有其他的中断都是打开的，所以这些不同中断线上的其他中断都能被处理，但当前中断线总是被禁止的。由此可见，同一个中断处理程序绝不会被同时调用产生同一个处理中断函数被嵌套的情况。而且，也控制了整个中断处理的栈的深度，内核最多可以支持15个IRQ同时在线，也就是说最大的内核中断处理栈的深度为15。

系统调用这里是用了trap gate，随时可以被中断掉，典型的是陷入系统调用以后被磁盘中断掉，注意Linux2.4之前都是内核非抢占的，陷于system_call的内核态系统调用不会被时钟中断调度出去。

linux 中system_gate trap_gate intr_gate的segment=0x0008 (kernel CS段)，偏移量是&idt[n] 下图是段描述符

1.2.x86指令  - 程序控制

jmp dst调转到指定地点继续执行，不改变stack，相当于内部跳转。

EIP <—  dst

call dst(sub routine 调用)保存当前执行地址，然后跳转到指定地点继续执行

push %EIP
EIP  <—  dst

ret从函数过程中返回，将栈上的值取出放到EIP中，回到caller继续执行

pop %EIP

int中断调用,从TSS的SS和ESP中重新设置栈(即该被中断任务的内核栈)， 从IDT表里找到对应处理函数地址并赋值给CS:EIP去执行，同时，保存被中断任务的上下文 SS:ESP, EFLAGS, CS:EIP。以便iret返回被中断任务得以继续执行。

Load new SS and eSP value from TSS;
CS:EIP ← selector:offset from gate;
Push (long pointer to old stack) (* 3 words padded to 4 *);
Push (EFLAGS);
Push (long pointer to return location) (* 3 words padded to 4*);

iret从中断调用中返回

pop %EIP
pop CS
pop EFLAGS
pop %ESP
pop SS

ljmp床跳转指令，从对应地址加载TR寄存器，重新加载CPU各个寄存器，以便跳转到另外的任务代码执行。

2.抢占和上下文切换

任务切换是通过 ljmp _TSS(nr)，即跳转到GDT表中TSS nr描述符。

2.1.抢占方式

任务抢占从linux0.12内核角度看主要有两种方式：

  • 用户抢占：分为两种，一种是从系统调用/异常处理程序返回用户空间时，检查当前任务的counter,如果counter=0则进行抢占；第二种是系统时钟中断，若当前处于用户态的任务，时间片到了以后会对任务进行切换。这时候用户态-内核态(时钟中断)切换。其他类型的中断处理不会引起任务的切换，比如磁盘控制器发起的磁盘读写请求结束的中断，中断程序还是会在当前被中断任务的内核态执行。
  • 内核抢占：也分为两种，一种是显式调用schedule；另一种则是任务阻塞隐式调用schedule，常见的为当前任务主动sleep，把cpu时间让给其他进程。自己则等待某个特定事件发生以后，由别的任务唤醒自己，然后调度程序调度CPU到该任务继续执行。一般都是通过系统调用完成此类切换。

2.1.1.系统时钟的例子

这是由timer时钟驱动，时钟中断自动完成的。

sched.c     set_intr_gate(0x20,&timer_interrupt); 
.align 2 
_timer_interrupt: 
    push %ds        # save ds,es and put kernel data space 
    push %es        # into them. %fs is used by _system_call 
    push %fs 
    pushl $-1        # fill in -1 for orig_eax 
    pushl %edx        # we save %eax,%ecx,%edx as gcc doesn not 
    pushl %ecx        # save those across function calls. %ebx 
    pushl %ebx        # is saved as we use that in ret_sys_call 
    pushl %eax 
    movl $0x10,%eax 
    mov %ax,%ds 
    mov %ax,%es 
    movl $0x17,%eax 
    mov %ax,%fs 
    incl _jiffies 
    movb $0x20,%al        # EOI to interrupt controller #1 
    outb %al,$0x20 
    movl CS(%esp),%eax 
    andl $3,%eax        # %eax is CPL (0 or 3, 0=supervisor) 
    pushl %eax 
    call _do_timer        # 'do_timer(long CPL)' does everything from 
    addl $4,%esp        # task switching to accounting ... 
    jmp ret_from_sys_call 

ret_from_sys_call: 
    movl _current,%eax 
    cmpl _task,%eax            # task[0] cannot have signals 
    je 3f 
    cmpw $0x0f,CS(%esp)        # was old code segment supervisor ? 
    jne 3f 
    cmpw $0x17,OLDSS(%esp)        # was stack segment = 0x17 ? 
    jne 3f 
    movl signal(%eax),%ebx 
    movl blocked(%eax),%ecx 
    notl %ecx 
    andl %ebx,%ecx 
    bsfl %ecx,%ecx 
    je 3f 
    btrl %ecx,%ebx 
    movl %ebx,signal(%eax) 
    incl %ecx 
    pushl %ecx 
    call _do_signal 
    popl %ecx 
    testl %eax, %eax 
    jne 2b        # see if we need to switch tasks, or do more signals 
3:  popl %eax 
    popl %ebx 
    popl %ecx 
    popl %edx 
    addl $4, %esp    # skip orig_eax 
    pop %fs 
    pop %es 
    pop %ds 
    iret           #从中断调用处回到原来被中断的指令地址，被中断的任务得以继续执行 


//时钟调度中断执行程序，传入的值为当前被中断进程的cpl, cpl=0表示被中断进程运行在内核态，
//cpl=3表示被中断程序运行在用户态
void do_timer(long cpl)
{
    static int blanked = 0;

    if (blankcount || !blankinterval) {
        if (blanked)
            unblank_screen();
        if (blankcount)
            blankcount--;
        blanked = 0;
    } else if (!blanked) {
        blank_screen();
        blanked = 1;
    }
    if (hd_timeout)
        if (!--hd_timeout)
            hd_times_out();

    if (beepcount)
        if (!--beepcount)
            sysbeepstop();

    if (cpl)
        current->utime++;
    else
        current->stime++;

    if (next_timer) {
        next_timer->jiffies--;
        while (next_timer && next_timer->jiffies <= 0) {
            void (*fn)(void);

            fn = next_timer->fn;
            next_timer->fn = NULL;
            next_timer = next_timer->next;
            (fn)();
        }
    }
    if (current_DOR & 0xf0)
        do_floppy_timer();
    if ((--current->counter)>0) return;
    current->counter=0;
    if (!cpl) return;
    schedule();
}

2.1.2.高速缓存任务阻塞引起抢占的例子：buffer_head

  • 任务A --sleep (buffer_head上的等待对列,由于buffer内存大小有限，太多的读写时后面的必须排队等待)
    if (!bh) {
        sleep_on(&buffer_wait);
        goto repeat;
    }
  • 任务B释放缓存块，该队列上等待的任务可以继续执行 则wakeup该队列上的等待任务
//释放该块缓存，实际上数据仍然有效 (仍在hash queue中)。等到下一次读请求到底时，由于该buffer已经count置0并且解锁，是一个可以使用的
//缓存块，一旦该缓存块被选中(通过LRU算法，该缓存块最近最少使用)，则会从hash queue中删除表示该数据无效，
//并且读入新的数据，重新加入hash queue和free list中
void brelse(struct buffer_head * buf)
{
    if (!buf)
        return;
    wait_on_buffer(buf);
    if (!(buf->b_count--))
        panic("Trying to free free buffer");
    wake_up(&buffer_wait);
}

2.1.3.读写磁盘任务阻塞引起抢占的例子：ll_rw_page

任务A需要读写某个block数据，将当前任务设为TASK_UNINTERRUPTIBLE，并将请求加入设备读写请求队列以后调用schedule，让出CPU时间。 磁盘读写不断中断调用(平均分布到所有任务上)，一旦任务A对应的磁盘读写完成，则内核唤醒该任务继续执行。

*   任务A休眠
    //加入request需要等待的进程队列
    sleep_on(&wait_for_request);
    static inline void wait_on_buffer(struct buffer_head * bh)
    {
        cli();
        while (bh->b_lock)
            sleep_on(&bh->b_wait);
        sti();
    }
  • 磁盘读写完成唤醒等待进程。
    wake_up(&CURRENT->waiting);
    wake_up(&wait_for_request);

2.2.用户态和内核态

分成两种情况讨论：

1.若当前程序处于用户态 用户进程正在运行并且没有陷于内核态，被动等待时钟切片用完，时钟中断程序执行。这时候会有用户态-内核态切换，用户态的上下文SS:ESP, EFLAGES, CS:EIP被cpu执行int 0x20(时钟中断)时自动的保存到当前被中断程序的内核栈上，CPU转而在内核态执行任务切换调用，当前被中断程序的内核态SS:ESP，正在执行的内核CS: EIP(ljmp后面的指令地址)被保存到TSS中。CPU转而根据跳转到的任务TSS恢复上下文，在跳转到的任务B的内核空间执行被跳转程序(一定是在内核空间，为什么呢？反过来想，这个任务B什么情况下放弃了CPU执行呢？无非是时钟中断或者陷入内核调用通过sleep()放弃CPU使用，这两种情况下任务B一定是停留在内核态的。) 一旦被中断任务重新被CPU调度，则会从内核态代码ljmp后面继续执行，一直到从中断调用处离开iret回到用户态执行。

2.若当前程序处于内核态 比如说用户进程通过系统调用已进入内核态

  • 运行在内核态的代码主动的进行休眠或者任务切换，通过调用sleep或switch_to (another)，当前任务的内核态SS:ESP, 当前任务的内核CS: EIP(ljmp后面的指令地址)被保留到TSS中。 一旦该任务被唤醒从而被重新调度到，则会从内核代码ljmp后面继续执行，也即继续执行该任务的内核态代码(某个系统调用)。
  • 陷入内核态以后，被动等待时钟切片用完，时钟中断程序执行。在do_timer中判断被中断的任务运行在内核态，不会抢占该任务。所以得以从中断返回，继续执行该任务的内核态代码(某个系统调用)。

这里值得注意的是，处于内核态的任务是不可以被抢占的，这一点使得内核栈不会无限的增大，最多有一个用户态-内核态切换的用户态栈保存，然后是中断调用需要保存的一些寄存器值。除非该任务在内核代码部分自己通过调用sleep将CPU时间让给别的任务。这一点是linux2.4之前非抢占式内核的一个简化设计。（参加Linux Kernel Development一书）

//0x80系统中断发生时内核栈 
old SS 
old ESP 
old EFLAGS 
old CS 
old EIP                  —int  iret 
DS                         — system_call 
ES 
FS 
-1 
EDX 
ECX 
EBX 
next EIP 
call _sys_xxx 
EAX   （系统调用号) 
jmp ret_from_sys_call 

//0x20系统中断发生时内核栈 
old SS 
old ESP 
old EFLAGS 
old CS 
old EIP                  —int  iret 
DS                        — system_interrupt 
ES 
FS 
-1 
EDX 
ECX 
EBX 
EAX   （系统调用号) 
CPL 
call _do_timer  
addl $4,%esp   // 
jmp ret_from_sys_call

2.3.两个问题的思考

这点有两个问题需要澄清一下：

第一个问题是，当时钟周期达到，需要对任务进行切换，如果当前被中断的进程运行在user space，则会进行任务切换，切换以后，当前任务下一条执行的指令是被打断时候的用户进程的next EIP，还是当前时钟中断时执行任务调转ljmp的下一条语句？

 /* switch_to(n) should switch tasks to task nr n, first
 * checking that n isn't the current task, in which case it does nothing.
 * This also clears the TS-flag if the task we switched to has used
 * tha math co-processor latest.
 */
 //任务切换，主要current定义在sched.c中
 //ljmp 48mem [16 bit segment selector + 32 bits offset]
 //16 bit segment selector即为_TSS(n)
 //32 bits offset为__tmp.a
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,_current\n\t" \
    "je 1f\n\t" \
    "movw %%dx,%1\n\t" \
    "xchgl %%ecx,_current\n\t" \
    "ljmp %0\n\t" \                   //这句调用之后，cpu会执行其他任务的代码流
    "cmpl %%ecx,_last_task_used_math\n\t" \
    "jne 1f\n\t" \
    "clts\n" \
    "1:" \
    ::"m" (*&__tmp.a),"m" (*&__tmp.b), \
    "d" (_TSS(n)),"c" ((long) task[n])); \
}

我们知道，ljmp会进行TSS保存和切换，当前被切换任务的上下文(SS, ESP, CS,EIP, LDTR,CR3等)都被如数保存到TSS中，当前正在运行的CS为0x0001为内核代码段，EIP显然是ljmp的下一条指令，即cmpl %%ecx,_last_task_used_math。那么当前被中断任务重新调度成功后，又如何回到原来的被中断指令处继续执行呢？

在int指令调用前，当前被中断任务的SS:ESP(用户态堆栈), EFLAGS, CS:EIP(用户态代码及下一条执行指令)被压入栈，从中断调用do_timer返回时iret指令又将这些值悉数重新加载，所以当前被中断任务在重新被调度成功之后，将会继续执行。

第二个问题是，int中断调用会把被中断程序用户态的CS, EIP, EFLAGS, SS:ESP等压入内核栈，中断调用可能会被阻塞，例如读写文件，等待socket打开等，等到当前被中断程序重新被CPU调度到, TSS切换执行ljmp下一条指令时，内存布局有可能改变。如何保证执行逻辑的不变？

我的理解是，内存布局不会改变。改变的只可能是内存从RAM到swap分区的交换，本质上已分配正在使用的内存数据不会销毁。 内核堆栈是位于task_struct的顶端的，task_struct数据页是位于16M以内的线性地址空间，用户态线性地址空间位于线性地址64M*nr~64M*(nr+1)，包括代码段CS和SS:ESP等，注意这两个部分内存都是从主存中分配得到的，而且不会主动释放掉。对于活动的进程程序执行的逻辑是不会改变的。

2.4.任务切换的例子

综合以上的理解，我们来看一个实际的例子，这个例子假设已经有两个任务A和B在系统中运行。

  • 任务A在用户空间运行一段CPU时间,定时器中断int 0x20触发；
  • CPU的中断处理过程开始，任务A用户空间的上下文(用户空间堆栈SS:ESP, CPU状况EFLAGES, 正在执行的代码CS:EIP)被保存到任务A的内核堆栈上。do_timer函数在任务A的内核空间执行，对任务A的执行时间计时，经过调度决策，开始执行ljmp task B;
  • ljmp长跳转被CPU执行，任务B的TSS被置换到CPU的各个寄存器如EAX,EBP,ESP等，同时任务A的当前上下文被保存到任务A的TSS。而任务B TSS中的CS:EIP保存的是上次任务B在定时器中断触发时，切换到任务A的下一条代码(CS=0x10为运行在内核代码段)，正是前面解释过的cmpl %%ecx,_last_task_used_math。于是从ljmp返回，从该指令往下执行，就会执行到ret_from_sys_call，在这里进行信号处理，最后调用iret从int 0x20中断返回到任务B的用户空间，CPU自动把任务B的内核堆栈上保存过的，任务B用户空间的上下文(用户空间堆栈SS:ESP, CPU状况EFLAGES, 正在执行的代码CS:EIP)加载到CPU寄存器上，完成任务B内核态-用户态的转换；
  • 任务B在在用户空间运行一段CPU时间,定时器中断int 0x20触发,过程循环反复。

2.5.多任务的同步

对于0.12系统而言，处理的CPU是单核的，内核代码暴露出来的主要方式是中断，所以，对于运行在内核态的代码而言，是没有race condition的。处于内核态的任务是不可以被抢占的，这一点使得内核栈不会无限的增大，最多有一个用户态-内核态切换的用户态栈保存，然后是中断调用需要保存的一些寄存器值。除非该任务在内核代码部分自己通过调用sleep将CPU时间让给别的任务。这一点是linux2.4之前非抢占式内核的一个简化设计。（Linux Kernel Development一书）。唯一的情况是从用户空间直接调用内核代码，比如读写硬盘，比如申请内存，若此时有其他中断产生则该任务可能被中断掉，对应的数据结构等就要考虑到这种特殊的情况，绝大多数的系统内核代码通过关闭中断cli的方式，规避掉这种race condition。典型的例子有

磁盘I/O

ll_rw_blk.c 
static void add_request(struct blk_dev_struct * dev, struct request * req)
{
    struct request * tmp;

    req->next = NULL;
    //关闭IF，使得该操作不能被硬盘读写中端
    cli();
    if (req->bh)
        req->bh->b_dirt = 0;
    //当前设备没有请求，则将该请求加入，并直接执行request_fn
    if (!(tmp = dev->current_request)) {
        dev->current_request = req;
        //打开IF，下面的磁盘读写可以被timer中端
        sti();
        (dev->request_fn)();
        return;
    }
    for ( ; tmp->next ; tmp=tmp->next) {
        if (!req->bh)
            if (tmp->next->bh)
                break;
            else
                continue;
        //如果tmp到req 或者 req到tmp->next
        if ((IN_ORDER(tmp,req) ||
            !IN_ORDER(tmp,tmp->next)) &&
            IN_ORDER(req,tmp->next))
            break;
    }
    //当前req放入requst链表
    req->next=tmp->next;
    tmp->next=req;
    //打开IF
    sti();
}

内存分配

malloc.c
void *malloc(unsigned int len)
{
    struct _bucket_dir  *bdir;
    struct bucket_desc  *bdesc;
    void            *retval;

    /*
     * First we search the bucket_dir to find the right bucket change
     * for this request.
     */
    for (bdir = bucket_dir; bdir->size; bdir++)
        if (bdir->size >= len)
            break;
    if (!bdir->size) {
        printk("malloc called with impossibly large argument (%d)\n",
            len);
        panic("malloc: bad arg");
    }
    /*
     * Now we search for a bucket descriptor which has free space
     */
    cli();  /* Avoid race conditions */
    ...
    sti();  /* OK, we're safe again */
}

cli和sti中间的内核代码意味着不可以被任意硬件中断“打断”，但是处于内核态的代码本身是可以被“打断”的，如自己主动sleep放弃对CPU的使用；异常处理程序也是可以继续下去的，例如内核代码访问某线性地址空间，该线性地址空间不可用从而引发CPU缺页中断，加载对应的物理内存。

3.进程的休眠(等待)和唤醒(继续执行)

上面提到了有效情况下，进程需要等待某个资源可用，在此之前需要将进程休眠以让出CPU执行时间片，等待某个资源可以用的时候，内核再唤醒该进程使之可以继续执行。这些策略主要是通过sleep_on, wake_up函数来达成的。

函数sleep_on(task_struct **p)会根据不同的资源产生不同的任务等待队列。

注意这里传入的是一个指针地址，该指针变量存储的是队列头指针地址。*p=head。这样不同的task_struct对象形成不同的任务等待队列。下图是一个任务队列示意图。

sleep_on常见的例子在I/O比较多，多对应系统调用read, write等，比如有：

  • 高速缓存区对应的某个block块的读写任务，控制对象在bh->b_wait，这种控制有两层含义，第一层相当于是多个进程对特定的block块的读写并发操作控制。如果已经有进程对该块数据申请了读写操作，另外的读进程显然需要等待完成后才能被调度到。第二层含义是所有对该块数据申请了读写操作的进程(包括第一个申请进程), 都必须等待慢吞吞的磁盘I/O把读写请求执行完,由I/O模块通知读写完成，所有等待I/O的进程得以继续往下执行。
  • 高速缓存区由于内存大小限制，需要将请求排队，形成一个请求队列。队列长度由高速缓存区大小限制， 队列头指针为buffer_wait。 当高速缓存区数据都被占满，没有办法满足新的请求时，新的任务必须等待其他进程完成I/O以后才可以被CPU调度执行。在此之前，新任务必须休眠。这相当于使用队列进行限流操作。
  • i_node对应的读写任务 inode->i_wait
  • Super_block 对应的 sb->s_wait
  • Block dev本身控制的读写缓冲区队列大小。相当于硬盘的读写缓冲区，通过这个缓冲区控制对硬盘电机的压力，这个读写缓冲区对上承接高速缓存，文件系统i_node, super_block以及内存管理模块的swap。队列头为 wait_for_request。对于读操作，32为队列长度，而对应写操作，32*2/3为队列长度。下面是源码中的注释
    #define NR_BLK_DEV  7
    /*
     * NR_REQUEST is the number of entries in the request-queue.
     * NOTE that writes may use only the low 2/3 of these: reads
     * take precedence.
     *
     * 32 seems to be a reasonable number: enough to get some benefit
     * from the elevator-mechanism, but not so much as to lock a lot of
     * buffers when they are in the queue. 64 seems to be too many (easily
     * long pauses in reading when heavy writing/syncing is going on)
     */
    #define NR_REQUEST  32

下面讨论一下多个进程同时竞争相同的block数据的情形。假设有三个进程，进程1，进程2和进程3同时对一块block数据buffer_head申请读操作，进程1首先会调用lock_buffer将该block锁住。并把读请求加入到block drv的请求队列中。之后进程1会继续往下执行。

static inline void lock_buffer(struct buffer_head * bh)
{
    cli();
    while (bh->b_lock)
        sleep_on(&bh->b_wait);
    bh->b_lock=1;
    sti();
}

同时进程1，进程2，进程3在申请读操作时分别从bread()中调到wait_on_buffer，形成一个等待bh->b_wait结束的等待队列。一旦该块数据被读出，则进程1，进程2和进程3如多米诺骨牌按顺序唤醒执行

static inline void wait_on_buffer(struct buffer_head * bh)
{
    cli();
    while (bh->b_lock)
        sleep_on(&bh->b_wait);
    sti();
}

如前所述，进程1会将b_lock置成1，然后继续执行，进程1，进程2则会和进程3组成一个等待队列，后申请的进程3为队列头指针。如果cpu调度进程2，则根据sleep_on的算法进程2会被休眠；如果cpu调度进程3，则进程3执行，并唤醒进程2. 但是进程3在执行到while(bh->b_lock)时，发现该缓存数据仍然是lock的，进程3只好继续休眠，和进程2仍然组成一个等待队列。队列头仍然是进程3. 重复以上步骤，进程3和进程2在该缓存变为unlock之前不能有其他操作。

当位于block dev层次的该请求块读写结束时，会对CURRENT->bh请求队列, 当前块请求进程CURRENT->waiting队列，块请求队列wait_for_request等进行唤醒操作。

/*结束块读写请求 唤醒等待在当前block rw上的任务*/
extern inline void end_request(int uptodate)
{
    DEVICE_OFF(CURRENT->dev);
    //解除block并唤醒等待该block的任务队列
    if (CURRENT->bh) {
        CURRENT->bh->b_uptodate = uptodate;
        unlock_buffer(CURRENT->bh);
    }
    if (!uptodate) {
        printk(DEVICE_NAME " I/O error\n\r");
        printk("dev %04x, block %d\n\r",CURRENT->dev,
            CURRENT->bh->b_blocknr);
    }
    //唤醒可能的swap等待任务，注意swap读写时会一直阻塞并且req.waiting= current。 
    wake_up(&CURRENT->waiting);
    //唤醒等待加入block dev请求队列的任务
    wake_up(&wait_for_request);
    CURRENT->dev = -1;
    CURRENT = CURRENT->next;
}

对应于第一个唤醒unlock_buffer，bh->b_wait上的等待进程1，进程2和进程3将得以调度，从wait_on_buffer中得以往下继续执行。

static inline void unlock_buffer(struct buffer_head * bh)
{
    if (!bh->b_lock)
        printk("ll_rw_block.c: buffer not locked\n\r");
    bh->b_lock = 0;
    wake_up(&bh->b_wait);
}

CURRENT->waiting上的等待进程应该是swap读写进程，也会被唤醒从而继续执行。 wait_for_request上的等待任务也可以获得一个block req对象句柄从而将请求加入读写请求队列。

读到这里，优先读者可能会问，swap有可能多个进程同时访问同一个swap page么，如果有怎么做到进程同步，类似bh->b_waiting的机制的？

我们知道，swap_in函数是用来从swap分区读取对应的一页数据，swap_in函数唯一的使用情形是内存缺页。当CPU访问不在内存中的线性地址时，会产生一个中断异常，进一步进入中断处理程序调用do_no_page，如果此时发现该页已经初始化过并被交换到硬盘swap分区，则调用swap_in并且等待(block by cpu schedule)。这里swap_in针对的是线性地址(虚拟地址)，不同的进程分配的是不同的线性地址范围, 64M*nr~64M*(nr+1)，所以多个不同的进程被缺页中断时，swap_in访问的是不同的线性地址，映射到不同的swap分区位置(swap_nr不同)。所以不可能产生多个进程排队等待同一个swap page数据的情形。

至于两个不同的swap page倒是有可能对应相同的binary内容，比如inode A被进程1和进程2同时加载，某段相同的代码被映射到不同的线性地址空间，然后被交换到swap分区的不同位置中。

同样的道理对于swap_out，每次都会对不同的线性地址空间进行swap_out，也会写到swap分区的不同位置(swap_nr不同)


上一篇     下一篇