KernelAnalysis-HOWTO: Linux 多任务

6.1 概述

本节将分析数据结构——Linux 下用于管理多任务环境的机制。

任务状态

一个 Linux 任务可以处于以下状态之一（根据 [include/linux.h]）

TASK_RUNNING，意味着它在“就绪列表”中
TASK_INTERRUPTIBLE，任务正在等待信号或资源（睡眠）
TASK_UNINTERRUPTIBLE，任务正在等待资源（睡眠），它在同一个“等待队列”中
TASK_ZOMBIE，没有父进程的子任务
TASK_STOPPED，正在被调试的任务

图形交互

       ______________     CPU Available     ______________
      |              |  ---------------->  |              |
      | TASK_RUNNING |                     | Real Running |  
      |______________|  <----------------  |______________|
                           CPU Busy
            |   /|\       
Waiting for |    | Resource  
 Resource   |    | Available             
           \|/   |      
    ______________________                     
   |                      |
   | TASK_INTERRUPTIBLE / |
   | TASK-UNINTERRUPTIBLE |
   |______________________|
 
                     Main Multitasking Flow

6.2 时间片

PIT 8253 编程

每 10 毫秒（取决于 HZ 值）会产生一个 IRQ0，这有助于我们进行多任务环境。这个信号来自 PIC 8259（在 arch 386+ 中），它连接到时钟频率为 1.19318 MHz 的 PIT 8253。

    _____         ______        ______        
   | CPU |<------| 8259 |------| 8253 |
   |_____| IRQ0  |______|      |___/|\|
                                    |_____ CLK 1.193.180 MHz
          
// From include/asm/param.h
#ifndef HZ 
#define HZ 100 
#endif
 
// From include/asm/timex.h
#define CLOCK_TICK_RATE 1193180 /* Underlying HZ */
 
// From include/linux/timex.h
#define LATCH ((CLOCK_TICK_RATE + HZ/2) / HZ) /* For divider */
 
// From arch/i386/kernel/i8259.c
outb_p(0x34,0x43); /* binary, mode 2, LSB/MSB, ch 0 */ 
outb_p(LATCH & 0xff , 0x40); /* LSB */
outb(LATCH >> 8 , 0x40); /* MSB */

因此，我们使用 LATCH = (1193180/HZ) = 11931.8 (当 HZ=100 时，默认值) 对 8253 (PIT，可编程间隔定时器) 进行编程。LATCH 表示频率除数因子。

LATCH = 11931.8 给 8253（在输出端）一个 1193180 / 11931.8 = 100 Hz 的频率，因此周期 = 10ms

因此，时间片 = 1/HZ。

在每个时间片中，我们临时中断当前进程的执行（不进行任务切换），并进行一些内务处理工作，之后我们将返回到我们之前的进程。

Linux 定时器 IRQ ICA

Linux Timer IRQ
IRQ 0 [Timer]
 |  
\|/
|IRQ0x00_interrupt        //   wrapper IRQ handler
   |SAVE_ALL              ---   
      |do_IRQ                |   wrapper routines
         |handle_IRQ_event  ---
            |handler() -> timer_interrupt  // registered IRQ 0 handler
               |do_timer_interrupt
                  |do_timer  
                     |jiffies++;
                     |update_process_times  
                     |if (--counter <= 0) { // if time slice ended then
                        |counter = 0;        //   reset counter           
                        |need_resched = 1;   //   prepare to reschedule
                     |}
         |do_softirq
         |while (need_resched) { // if necessary
            |schedule             //   reschedule
            |handle_softirq
         |}
   |RESTORE_ALL

函数可以在以下位置找到

IRQ0x00_interrupt, SAVE_ALL [include/asm/hw_irq.h]
do_IRQ, handle_IRQ_event [arch/i386/kernel/irq.c]
timer_interrupt, do_timer_interrupt [arch/i386/kernel/time.c]
do_timer, update_process_times [kernel/timer.c]
do_softirq [kernel/soft_irq.c]
RESTORE_ALL, while loop [arch/i386/kernel/entry.S]

注释

函数 “IRQ0x00_interrupt”（像其他 IRQ0xXY_interrupt 一样）直接由 IDT（中断描述符表，类似于实模式中断向量表，详见第 11 章）指向，因此每个到达处理器的中断都由 “IRQ0x#NR_interrupt” 例程管理，其中 #NR 是中断号。我们将其称为 “wrapper irq handler”（包装器中断处理程序）。
包装器例程被执行，例如 “do_IRQ”，“handle_IRQ_event” [arch/i386/kernel/irq.c]。
在此之后，控制权被传递给官方 IRQ 例程（由 “handler()” 指向），之前使用 “request_irq” [arch/i386/kernel/irq.c] 注册，在本例中为 “timer_interrupt” [arch/i386/kernel/time.c]。
“timer_interrupt” [arch/i386/kernel/time.c] 例程被执行，当它结束时，
控制权返回到一些汇编例程 [arch/i386/kernel/entry.S]。

描述

为了管理多任务，Linux（像每个其他 Unix 一样）使用一个 “counter”（计数器）变量来跟踪任务使用了多少 CPU 时间。因此，在每个 IRQ 0 上，计数器会递减（第 4 点），当它达到 0 时，我们需要切换任务来管理时间共享（第 4 点 “need_resched” 变量被设置为 1，然后，在第 5 点汇编例程控制 “need_resched” 并在需要时调用 “schedule” [kernel/sched.c]）。

6.3 调度器

调度器是选择在给定时间必须执行哪个任务的代码片段。

任何时候你需要更改正在运行的任务，请选择一个候选者。以下是 “schedule [kernel/sched.c]” 函数。

|schedule
   |do_softirq // manages post-IRQ work
   |for each task
      |calculate counter
   |prepare_to__switch // does anything
   |switch_mm // change Memory context (change CR3 value)
   |switch_to (assembler)
      |SAVE ESP
      |RESTORE future_ESP
      |SAVE EIP
      |push future_EIP *** push parameter as we did a call 
         |jmp __switch_to (it does some TSS work) 
         |__switch_to()
          ..
         |ret *** ret from call using future_EIP in place of call address
      new_task

6.4 底半部、任务队列和 Tasklet

概述

在经典的 Unix 中，当 IRQ 来自（设备）时，Unix 会进行 “task switching”（任务切换）以询问请求设备的任务。

为了提高性能，Linux 可以将非紧急工作推迟到以后，以便更好地管理高速事件。

自内核 1.x 以来，此功能由 “bottom half”（底半部，BH）管理。irq 处理程序 “marks”（标记）一个底半部，以便稍后在调度时间内执行。

在最新的内核中，有一个 “task queue”（任务队列），它比 BH 更具动态性，并且还有一个 “tasklet” 来管理多处理器环境。

BH 模式是

声明
标记
执行

声明

#define DECLARE_TASK_QUEUE(q) LIST_HEAD(q)
#define LIST_HEAD(name) \
   struct list_head name = LIST_HEAD_INIT(name) 
struct list_head { 
   struct list_head *next, *prev; 
};
#define LIST_HEAD_INIT(name) { &(name), &(name) } 
 
      ''DECLARE_TASK_QUEUE'' [include/linux/tqueue.h, include/linux/list.h]

“DECLARE_TASK_QUEUE(q)” 宏用于声明一个名为 “q” 的结构，该结构管理任务队列。

标记

这是 “mark_bh” [include/linux/interrupt.h] 函数的 ICA 模式

|mark_bh(NUMBER)
   |tasklet_hi_schedule(bh_task_vec + NUMBER)
      |insert into tasklet_hi_vec
         |__cpu_raise_softirq(HI_SOFTIRQ) 
            |soft_active |= (1 << HI_SOFTIRQ)
 
                   ''mark_bh''[include/linux/interrupt.h]

例如，当 IRQ 处理程序想要 “postpone”（推迟）一些工作时，它会 “mark_bh(NUMBER)”，其中 NUMBER 是一个声明的 BH（见前一节）。

执行

我们可以看到从 “do_IRQ” [arch/i386/kernel/irq.c] 函数的调用

|do_softirq
   |h->action(h)-> softirq_vec[TASKLET_SOFTIRQ]->action -> tasklet_action
      |tasklet_vec[0].list->func

“h->action(h);” 是先前排队的函数。

6.5 非常底层的例程

set_intr_gate

set_trap_gate

set_task_gate (未使用)。

(*interrupt)[NR_IRQS](void) = { IRQ0x00_interrupt, IRQ0x01_interrupt, ..}

NR_IRQS = 224 [kernel 2.4.2]

6.6 任务切换

任务切换何时发生？

现在我们将了解 Linux 内核如何从一个任务切换到另一个任务。

在许多情况下需要任务切换，例如以下情况

当时间片结束时，我们需要允许其他任务访问
当一个任务决定访问一个资源时，它会为此休眠，因此我们必须选择另一个任务
当一个任务等待管道时，我们必须允许其他任务访问，这将写入管道

任务切换

                           TASK SWITCHING TRICK
#define switch_to(prev,next,last) do {                                  \
        asm volatile("pushl %%esi\n\t"                                  \
                     "pushl %%edi\n\t"                                  \
                     "pushl %%ebp\n\t"                                  \
                     "movl %%esp,%0\n\t"        /* save ESP */          \
                     "movl %3,%%esp\n\t"        /* restore ESP */       \
                     "movl $1f,%1\n\t"          /* save EIP */          \
                     "pushl %4\n\t"             /* restore EIP */       \
                     "jmp __switch_to\n"                                \
                     "1:\t"                                             \
                     "popl %%ebp\n\t"                                   \
                     "popl %%edi\n\t"                                   \
                     "popl %%esi\n\t"                                   \
                     :"=m" (prev->thread.esp),"=m" (prev->thread.eip),  \
                      "=b" (last)                                       \
                     :"m" (next->thread.esp),"m" (next->thread.eip),    \
                      "a" (prev), "d" (next),                           \
                      "b" (prev));                                      \
} while (0)

技巧在这里

“pushl %4” 将 future_EIP 放入堆栈
“jmp __switch_to” 执行 “__switch_to” 函数，但与 “call” 相反，我们将返回到第 1 点中推送的值（因此是新任务！）

      U S E R   M O D E                 K E R N E L     M O D E

 |          |     |          |       |          |     |          |
 |          |     |          | Timer |          |     |          |
 |          |     |  Normal  |  IRQ  |          |     |          |
 |          |     |   Exec   |------>|Timer_Int.|     |          |
 |          |     |     |    |       | ..       |     |          |
 |          |     |    \|/   |       |schedule()|     | Task1 Ret|
 |          |     |          |       |_switch_to|<--  |  Address |
 |__________|     |__________|       |          |  |  |          |
                                     |          |  |S |          | 
Task1 Data/Stack   Task1 Code        |          |  |w |          |
                                     |          | T|i |          |
                                     |          | a|t |          |
 |          |     |          |       |          | s|c |          |
 |          |     |          | Timer |          | k|h |          |
 |          |     |  Normal  |  IRQ  |          |  |i |          | 
 |          |     |   Exec   |------>|Timer_Int.|  |n |          |
 |          |     |     |    |       | ..       |  |g |          |
 |          |     |    \|/   |       |schedule()|  |  | Task2 Ret|
 |          |     |          |       |_switch_to|<--  |  Address |
 |__________|     |__________|       |__________|     |__________|
 
Task2 Data/Stack   Task2 Code        Kernel Code  Kernel Data/Stack

6.7 Fork

概述

Fork 用于创建另一个任务。我们从一个父任务开始，并将许多数据结构复制到子任务。

 
                               |         |
                               | ..      |
         Task Parent           |         |
         |         |           |         |
         |  fork   |---------->|  CREATE |   
         |         |          /|   NEW   |
         |_________|         / |   TASK  |
                            /  |         |
             ---           /   |         |
             ---          /    | ..      |
                         /     |         |
         Task Child     / 
         |         |   /
         |  fork   |<-/
         |         |
         |_________|
              
                       Fork SysCall

哪些没有被复制

新创建的任务（“子任务”）几乎与父任务（“父任务”）相同，只有少数差异

显然是 PID
子进程 “fork()” 将返回 0，而父进程 “fork()” 将返回子任务的 PID，以便在用户模式下区分它们
所有子进程数据页都被标记为 “READ + EXECUTE”，没有 “WRITE”（而父进程对其自己的页面具有 WRITE 权限），因此，当写入请求到来时，会生成一个 “Page Fault”（页错误）异常，这将创建一个新的独立页面：这种机制称为 “Copy on Write”（写时复制）（更多信息请参见第 10 章）。

Fork ICA

|sys_fork 
   |do_fork
      |alloc_task_struct 
         |__get_free_pages
       |p->state = TASK_UNINTERRUPTIBLE
       |copy_flags
       |p->pid = get_pid    
       |copy_files
       |copy_fs
       |copy_sighand
       |copy_mm // should manage CopyOnWrite (I part)
          |allocate_mm
          |mm_init
             |pgd_alloc -> get_pgd_fast
                |get_pgd_slow
          |dup_mmap
             |copy_page_range
                |ptep_set_wrprotect
                   |clear_bit // set page to read-only              
          |copy_segments // For LDT
       |copy_thread
          |childregs->eax = 0  
          |p->thread.esp = childregs // child fork returns 0
          |p->thread.eip = ret_from_fork // child starts from fork exit
       |retval = p->pid // parent fork returns child pid
       |SET_LINKS // insertion of task into the list pointers
       |nr_threads++ // Global variable
       |wake_up_process(p) // Now we can wake up just created child
       |return retval
              
               fork ICA

sys_fork [arch/i386/kernel/process.c]
do_fork [kernel/fork.c]
alloc_task_struct [include/asm/processor.c]
__get_free_pages [mm/page_alloc.c]
get_pid [kernel/fork.c]
copy_files
copy_fs
copy_sighand
copy_mm
allocate_mm
mm_init
pgd_alloc -> get_pgd_fast [include/asm/pgalloc.h]
get_pgd_slow
dup_mmap [kernel/fork.c]
copy_page_range [mm/memory.c]
ptep_set_wrprotect [include/asm/pgtable.h]
clear_bit [include/asm/bitops.h]
copy_segments [arch/i386/kernel/process.c]
copy_thread
SET_LINKS [include/linux/sched.h]
wake_up_process [kernel/sched.c]

写时复制

为了实现 Linux 的写时复制

将所有复制的页面标记为只读，当任务尝试写入它们时，会导致页错误。
页错误处理程序创建一个新页面。

 
 | Page 
 | Fault 
 | Exception
 |
 |
 -----------> |do_page_fault
                 |handle_mm_fault
                    |handle_pte_fault 
                       |do_wp_page        
                          |alloc_page      // Allocate a new page
                          |break_cow
                             |copy_cow_page // Copy old page to new one
                             |establish_pte // reconfig Page Table pointers
                                |set_pte
                            
              Page Fault ICA

do_page_fault [arch/i386/mm/fault.c]
handle_mm_fault [mm/memory.c]
handle_pte_fault
do_wp_page
alloc_page [include/linux/mm.h]
break_cow [mm/memory.c]
copy_cow_page
establish_pte
set_pte [include/asm/pgtable-3level.h]