Linux0.11內核--進程調度分析之2.調度，linux0.11內核

Linux0.11內核--進程調度分析之2.調度，linux0.11內核

【版權所有，轉載請注明出處。出處：http://www.cnblogs.com/joey-hua/p/5596830.html 】

上一篇說到進程調度歸根結底是調用timer_interrupt函數，在system_call.s中：

#### int32 -- (int 0x20) 時鐘中斷處理程序。中斷頻率被設置為100Hz(include/linux/sched.h,5)，
# 定時芯片8253/8254 是在(kernel/sched.c,406)處初始化的。因此這裡jiffies 每10 毫秒加1。
# 這段代碼將jiffies 增1，發送結束中斷指令給8259 控制器，然後用當前特權級作為參數調用
# C 函數do_timer(long CPL)。當調用返回時轉去檢測並處理信號。
.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 %edx 							# we save %eax,%ecx,%edx as gcc doesn't
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 				# ds,es 置為指向內核數據段。
mov %ax,%ds
mov %ax,%es
movl $0x17,%eax 				# fs 置為指向局部數據段（出錯程序的數據段）。
mov %ax,%fs
incl _jiffies
# 由於初始化中斷控制芯片時沒有采用自動EOI，所以這裡需要發指令結束該硬件中斷。
movb $0x20,%al 				# EOI to interrupt controller #1
outb %al,$0x20 					# 操作命令字OCW2 送0x20 端口。
# 下面3 句從選擇符中取出當前特權級別(0 或3)並壓入堆棧，作為do_timer 的參數。
movl CS(%esp),%eax
andl $3,%eax 						# %eax is CPL (0 or 3, 0=supervisor)
pushl %eax
# do_timer(CPL)執行任務切換、計時等工作，在kernel/shched.c,305 行實現。
call _do_timer 						# 'do_timer(long CPL)' does everything from
addl $4,%esp 						# task switching to accounting ...
jmp ret_from_sys_call

前面一堆push指令保存當前的寄存器，然後在ret_from_sys_call中彈出。

movl $0x10,%eax把段選擇子0x10也就是內核數據段選擇子賦值給eax，然後再賦給ds、es；

然後_jiffies加1，jiffies在sched.h中定義：

extern long volatile jiffies;	// 從開機開始算起的滴答數（10ms/滴答）。

接下來三句指令比較關鍵：

movl CS(%esp),%eax
andl $3,%eax 						# %eax is CPL (0 or 3, 0=supervisor)
pushl %eax

從上面push的寄存器當中取出cs寄存器的值，也就是代碼段選擇子，根據選擇的結構，0-1位是特權級，andl $3,%eax就是取eax中0-1位的值，然後把eax壓棧當成do_timer的參數傳遞，4個字節。

好了，現在進入do_timer函數，在sched.c中：

//// 時鐘中斷C 函數處理程序，在kernel/system_call.s 中的_timer_interrupt（176 行）被調用。
// 參數cpl 是當前特權級0 或3，0 表示內核代碼在執行。
// 對於一個進程由於執行時間片用完時，則進行任務切換。並執行一個計時更新工作。
void do_timer (long cpl)
{
  extern int beepcount;		// 揚聲器發聲時間滴答數(kernel/chr_drv/console.c,697)
  extern void sysbeepstop (void);	// 關閉揚聲器(kernel/chr_drv/console.c,691)

  // 如果發聲計數次數到，則關閉發聲。(向0x61 口發送命令，復位位0 和1。位0 控制8253
  // 計數器2 的工作，位1 控制揚聲器)。
  if (beepcount)
    if (!--beepcount)
      sysbeepstop ();

  // 如果當前特權級(cpl)為0（最高，表示是內核程序在工作），則將內核程序運行時間stime 遞增；
  // [ Linus 把內核程序統稱為超級用戶(supervisor)的程序，見system_call.s,193 行上的英文注釋]
  // 如果cpl > 0，則表示是一般用戶程序在工作，增加utime。
  if (cpl)
    current->utime++;
  else
    current->stime++;

  // 如果有用戶的定時器存在，則將鏈表第1 個定時器的值減1。如果已等於0，則調用相應的處理
  // 程序，並將該處理程序指針置為空。然後去掉該項定時器。
  if (next_timer)
    {				// next_timer 是定時器鏈表的頭指針(見270 行)。
      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) ();		// 調用處理函數。
	}
    }
  // 如果當前軟盤控制器FDC 的數字輸出寄存器中馬達啟動位有置位的，則執行軟盤定時程序(245 行)。
  if (current_DOR & 0xf0)
    do_floppy_timer ();
  if ((--current->counter) > 0)
    return;			// 如果進程運行時間還沒完，則退出。
  current->counter = 0;
  if (!cpl)
    return;			// 對於超級用戶程序(內核態程序)，不依賴counter 值進行調度。
  schedule ();
}

傳遞來的參數cpl的作用就是如果為0，表示是內核程序，則stime加1，否則都是普通用戶程序，則utime加1。

用戶定時器等用到再說。

接下來判斷時間片counter，在sched.h的進程描述符中：

long counter;		// long counter 任務運行時間計數(遞減)（滴答數），運行時間片。

如果還有時間片則不調用調度函數schedule()，然後時間片減1並退出此函數。

如果時間片已用完（<=0），則置時間片為0，緊接著判斷特權級，如果是內核級程序則直接退出函數。否則進入最核心的調度函數schedule：

/*
 * 'schedule()'是調度函數。這是個很好的代碼！沒有任何理由對它進行修改，因為它可以在所有的
 * 環境下工作（比如能夠對IO-邊界處理很好的響應等）。只有一件事值得留意，那就是這裡的信號
 * 處理代碼。
 * 注意！！任務0 是個閒置('idle')任務，只有當沒有其它任務可以運行時才調用它。它不能被殺
 * 死，也不能睡眠。任務0 中的狀態信息'state'是從來不用的。
 */
void schedule (void)
{
  int i, next, c;
  struct task_struct **p;	// 任務結構指針的指針。

  /* check alarm, wake up any interruptible tasks that have got a signal */
  /* 檢測alarm（進程的報警定時值），喚醒任何已得到信號的可中斷任務 */

  // 從任務數組中最後一個任務開始檢測alarm。
  for (p = &LAST_TASK; p > &FIRST_TASK; --p)
    if (*p)
      {
    	// 如果設置過任務的定時值alarm，並且已經過期(alarm<jiffies),則在信號位圖中置SIGALRM 信號，
    	// 即向任務發送SIGALARM 信號。然後清alarm。該信號的默認操作是終止進程。
    	// jiffies 是系統從開機開始算起的滴答數（10ms/滴答）。定義在sched.h 第139 行。
	if ((*p)->alarm && (*p)->alarm < jiffies)
	  {
	    (*p)->signal |= (1 << (SIGALRM - 1));
	    (*p)->alarm = 0;
	  }
	// 如果信號位圖中除被阻塞的信號外還有其它信號，並且任務處於可中斷狀態，則置任務為就緒狀態。
	// 其中'~(_BLOCKABLE & (*p)->blocked)'用於忽略被阻塞的信號，但SIGKILL 和SIGSTOP 不能被阻塞。
	if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
	    (*p)->state == TASK_INTERRUPTIBLE)
	  (*p)->state = TASK_RUNNING;	//置為就緒（可執行）狀態。
      }

  /* this is the scheduler proper: */
  /* 這裡是調度程序的主要部分 */

  while (1)
    {
      c = -1;
      next = 0;
      i = NR_TASKS;
      p = &task[NR_TASKS];
      // 這段代碼也是從任務數組的最後一個任務開始循環處理，並跳過不含任務的數組槽。比較每個就緒
      // 狀態任務的counter（任務運行時間的遞減滴答計數）值，哪一個值大，運行時間還不長，next 就
      // 指向哪個的任務號。
      while (--i)
	{
	  if (!*--p)
	    continue;
	  if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
	    c = (*p)->counter, next = i;
	}
      // 如果比較得出有counter 值大於0 的結果，則退出124 行開始的循環，執行任務切換（141 行）。
      if (c)
	break;
      // 否則就根據每個任務的優先權值，更新每一個任務的counter 值，然後回到125 行重新比較。
      // counter 值的計算方式為counter = counter /2 + priority。[右邊counter=0??]這裡計算過程不考慮進程的狀態。
      for (p = &LAST_TASK; p > &FIRST_TASK; --p)
	if (*p)
	  (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
    }
  // 切換到任務號為next 的任務運行。在126 行next 被初始化為0。因此若系統中沒有任何其它任務
  // 可運行時，則next 始終為0。因此調度函數會在系統空閒時去執行任務0。此時任務0 僅執行
  // pause()系統調用，並又會調用本函數。
  switch_to (next);		// 切換到任務號為next 的任務，並運行之。
}

前面的比較好理解，直接分析主要部分，此部分的主要工作就是從所有的任務中找出時間片最大的任務，也就意味著運行的時間較少，next就指向這個任務並跳出循環去切換任務。

如果所有任務的時間片都為0，就根據每個任務的優先權值來更新每個任務的時間片counter值。然後重新找到next，最後切換任務，調用switch_to(next)：

// 宏定義，計算在全局表中第n 個任務的TSS 描述符的索引號（選擇符）。
#define _TSS(n) ((((unsigned long) n)<<4)+(FIRST_TSS_ENTRY<<3))

/*
* switch_to(n)將切換當前任務到任務nr，即n。首先檢測任務n 不是當前任務，
* 如果是則什麼也不做退出。如果我們切換到的任務最近（上次運行）使用過數學
* 協處理器的話，則還需復位控制寄存器cr0 中的TS 標志。
*/
// 輸入：%0 - 新TSS 的偏移地址(*&__tmp.a)； %1 - 存放新TSS 的選擇符值(*&__tmp.b)；
// dx - 新任務n 的選擇符；ecx - 新任務指針task[n]。
// 其中臨時數據結構__tmp 中，a 的值是32 位偏移值，b 為新TSS 的選擇符。在任務切換時，a 值
// 沒有用（忽略）。在判斷新任務上次執行是否使用過協處理器時，是通過將新任務狀態段的地址與
// 保存在last_task_used_math 變量中的使用過協處理器的任務狀態段的地址進行比較而作出的。
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__( "cmpl %%ecx,_current\n\t" \	// 任務n 是當前任務嗎?(current ==task[n]?)
  "je 1f\n\t" \			// 是，則什麼都不做，退出。
  "movw %%dx,%1\n\t" \		// 將新任務的選擇符??*&__tmp.b。
  "xchgl %%ecx,_current\n\t" \	// current = task[n]；ecx = 被切換出的任務。
  "ljmp %0\n\t" \		// 執行長跳轉至*&__tmp，造成任務切換。
// 在任務切換回來後才會繼續執行下面的語句。
  "cmpl %%ecx,_last_task_used_math\n\t" \	// 新任務上次使用過協處理器嗎？
  "jne 1f\n\t" \		// 沒有則跳轉，退出。
  "clts\n" \			// 新任務上次使用過協處理器，則清cr0 的TS 標志。
  "1:"::"m" (*&__tmp.a), "m" (*&__tmp.b),
  "d" (_TSS (n)), "c" ((long) task[n]));
}

分析這段代碼前先要知道，在32位保護模式下，有2種直接發起任務切換的方法：

1.call 0x0010:0x00000000

2.jmp 0x0010:0x00000000

在這兩種情況下，call和jmp指令的操作數是任務的TSS描述符選擇子或任務門。當處理器執行這兩條指令時，首先用指令中給出的描述符選擇子訪問GDT，分析它的描述符類型。如果是一般的代碼段描述符，就按普通的段間轉移規則執行；如果是調用門，按調用門的規則執行；如果是TSS描述符，或者任務門，則執行任務切換。此時，指令中給出的32位偏移量被忽略，原因是執行任務切換時，所有處理器的狀態都可以從TSS中獲得。

當任務切換發生的時候，TR寄存器的內容也會跟著指向新任務的TSS。在任務切換時，任務寄存器tr 由CPU 自動加載。這個過程是這樣的：首先，處理器將當前任務的現場信息保存到由TR寄存器指向的TSS；然後，再使TR寄存器指向新任務的TSS，並從新任務的TSS中恢復現場。

注意：任務門描述符可以安裝在中斷描述符表中，也可以安裝在GDT或者LDT中。

知道了理論知識，上面的代碼就不難分析了，關鍵的一句是把新任務的TSS選擇子賦值給%1也就是*&_tmp.b處，現在b的值就是TSS選擇子，注意這裡ljmp %0相當於ljmp *%0，表示是間接跳轉，相當於“ljmp *__tmp.a”，也就是跳轉到地址&__tmp.a中包含的48bit邏輯地址處。而按struct _tmp的定義，這也就意味著__tmp.a即為該邏輯地址的offset部分，__tmp.b的低16bit為seg_selector(高16bit無用)部分。

直到這行指令執行完，才算真正的任務切換！至此進程調度分析結束。