深入分析Linux內核源碼－進程調度(1)
1 Linux時間系統
計算機最基本的時間單元是時鐘周期，例如取指令、執行指令、存取內存等。時間系統是計算機系統非常重要的組成部分，特別是對于Unix類分時系統尤為重要。時間系統主要任務是維持系統時間并且防止某個進程獨占CPU及其他資源，也就是驅動進程的調度。
1.1 時鐘硬件
大部分PC機中有兩個時鐘源，他們分別叫做RTC和OS（操作系統）時鐘。RTC（Real Time Clock，實時時鐘）也叫做CMOS時鐘，它是PC主機板上的一塊芯片，它靠電池供電，即使系統斷電，也可以維持日期和時間。由于它獨立于操作系統，所以也被稱為硬件時鐘，它為整個計算機提供一個計時標準，是最原始***層的時鐘數據。
Linux只用RTC來獲得時間和日期；然而，通過作用于/dev/rtc設備文件，也允許進程對RTC編程。通過執行/sbin/clock系統程序，系統管理員可以配置時鐘。
OS時鐘產生于PC主板上的定時/計數芯片，由操作系統控制這個芯片的工作，OS時鐘的基本單位就是該芯片的計數周期。在開機時操作系統取得RTC中的時間數據來初始化OS時鐘，然后通過計數芯片的向下計數形成了OS時鐘，它更應該被稱為一個計數器。OS時鐘只在開機時才有效，而且完全由操作系統控制，所以也被稱為軟時鐘或系統時鐘。下面我們重點描述OS時鐘的產生。
OS時鐘輸出脈沖信號，接到中斷控制器上，產生中斷信號，觸發后面要講的時鐘中斷，由時鐘中斷服務程序維持OS時鐘的正常工作。
1.2 時鐘運作機制
RTC和OS時鐘之間的關系通常也被稱作操作系統的時鐘運作機制。一般來說，RTC是OS時鐘的時間基準，操作系統通過讀取RTC來初始化OS時鐘，此后二者保持同步運行，共同維持著系統時間。保持同步運行是什么意思呢？就是指操作系統運行過程中，每隔一個固定時間會刷新或校正RTC中的信息。
圖2 時鐘運作機制
我們可以看到，RTC處于***層，提供最原始的時鐘數據。OS時鐘建立在RTC之上，初始化完成后將完全由操作系統控制，和RTC脫離關系。操作系統通過OS時鐘提供給應用程序所有和時間有關的服務。
1.3 Linux時間基準
以上我們了解了RTC（實時時鐘、硬件時鐘）和OS時鐘（系統時鐘、軟時鐘）。下面我們具體描述OS時鐘。OS時鐘是由可編程定時/計數器產生的輸出脈沖觸發中斷而產生的。輸出脈沖的周期叫做一個“時鐘滴答”。計算機中的時間是以時鐘滴答為單位的，每一次時鐘滴答，系統時間就會加1。操作系統根據當前時鐘滴答的數目就可以得到以秒或毫秒等為單位的其他時間格式。
定義“時間基準”的目的是為了簡化計算，這樣計算機中的時間只要表示為從這個時間基準開始的時鐘滴答數就可以了。“時間基準是由操作系統的設計者規定的。例如DOS的時間基準是1980年1月1日，Unix的時間基準是1970年1月1日上午12點，Linux的時間基準是1970年1月1日凌晨0點。
1.4 Linux的時間系統
OS時鐘記錄的時間也就是通常所說的系統時間。系統時間是以“時鐘滴答”為單位的，而時鐘中斷的頻率決定了一個時鐘滴答的長短，例如每秒有100次時鐘中斷，那么一個時鐘滴答的就是10毫秒（記為10ms），相應地，系統時間就會每10ms增1。
Linux中用全局變量jiffies表示系統自啟動以來的時鐘滴答數目。在/kernel/time.c中定義如下：
unsigned long volatile jiffies
在jiffies基礎上，Linux提供了如下適合人們習慣的時間格式，在/include/linux/time.h中定義如下：
struct timespec {／* 這是精度很高的表示*／
long tv_sec; ／* 秒 （second） *／
long tv_nsec; /* 納秒：十億分之一秒（ nanosecond）*／
}；
struct timeval {／* 普通精度*／
int tv_sec; /* 秒*／
int tv_usec; /* 微秒：百萬分之一秒（microsecond）*／
};
struct timezone {/* 時區 *／
int tz_minuteswest;／* 格林尼治時間往西方的時差 *／
int tz_dsttime;/* 時間修正方式 *／
};
tv_sec表示秒（second），tv_usec表示微秒（microsecond），tv_nsec表示納秒（nanosecond）。定義tb_usec和tv_nsec的目的是為了適用不同的使用要求，不同的場合根據對時間精度的要求選用這兩種表示。另外，Linux還定義了用于表示更加符合大眾習慣的時間表示：年、月、日。但是萬變不離其宗，所有的時間應用都是建立在jiffies基礎之上的。簡而言之，jiffies產生于時鐘中斷！
2 時鐘中斷
#p#2.1 時鐘中斷的產生
“時鐘中斷”是特別重要的一個中斷，因為整個操作系統的活動都受到它的激勵。系統利用時鐘中斷維持系統時間、促使環境的切換，以保證所有進程共享CPU；利用時鐘中斷進行記帳、監督系統工作以及確定未來的調度優先級等工作。可以說，“時鐘中斷”是整個操作系統的脈搏。
時鐘中斷的物理產生如圖3所示：
圖3 8253和8259A的物理連接方式
脈沖信號接到中斷控制器8259A_1的0號管腳，觸發一個周期性的中斷，我們就把這個中斷叫做時鐘中斷，時鐘中斷的周期，也就是脈沖信號的周期，我們叫做“滴答”或“時標”（tick）。從本質上說，時鐘中斷只是一個周期性的信號，完全是硬件行為，該信號觸發CPU去執行一個中斷服務程序，我們就把這個服務程序叫做時鐘中斷。
2.2.Linux實現時鐘中斷的全過程
1. 和時鐘中斷相關的函數
下面我們看時鐘中斷觸發的服務程序，該程序代碼比較復雜，分布在不同的源文件中，主要包括如下函數：
時鐘中斷程序：timer_interrupt( )；
中斷服務通用例程do_timer_interrupt();
時鐘函數：do_timer( )；
中斷安裝程序：setup_irq( );
中斷返回函數：ret_from_intr( );
前三個函數的調用關系如下：
timer_interrupt( )
do_timer_interrupt()
do_timer( )
(1) timer_interrupt( )
這個函數大約每10ms被調用一次，實際上， timer_interrupt( )函數是一個封裝例程，它真正做的事情并不多，該函數主要語句就是調用do_timer_interrupt()函數。
(2) do_timer_interrupt()
do_timer_interrupt()函數有兩個主要任務，一個是調用do_timer( )，另一個是維持實時時鐘(RTC，每隔一定時間段要回寫)，其實現代碼在/arch/i386/kernel/time.c中， 為了突出主題，筆者對以下函數作了改寫，以便于讀者理解：
static inline void do_timer_interrupt(int irq， void *dev_id， struct pt_regs *regs)
{
do_timer(regs); /* 調用時鐘函數，將時鐘函數等同于時鐘中斷未嘗不可*/
if(xtime.tv_sec > last_rtc_update + 660)
update_RTC();
/*每隔11分鐘就更新RTC中的時間信息，以使OS時鐘和RTC時鐘保持同步，11分鐘即660秒，xtime.tv_sec的單位是秒，last_rtc_update記錄的是上次RTC更新時的值 */
}
其中，xtime是前面所提到的timeval類型，這是一個全局變量。
(3) 時鐘函數do_timer() (在/kernel/sched.c中)
void do_timer(struct pt_regs * regs)
{
(*(unsigned long *)&jiffies)++; /*更新系統時間，這種寫法保證對jiffies操作的原子性*/
update_process_times（）;
++lost_ticks;
if( ! user_mode ( regs ) )
++lost_ticks_system;
mark_bh(TIMER_BH);
if (tq_timer)
mark_bh(TQUEUE_BH);
}
其中，update_process_times（）函數與進程調度有關，從函數的名子可以看出，它處理的是與當前進程與時間有關的變量，例如，要更新當前進程的時間片計數器counter，如果counter<=0，則要調用調度程序。
與時間有關的事情很多，不能全都讓這個函數去完成，這是因為這個函數是在關中斷的情況下執行，必須處理完最重要的時間信息后退出，以處理其他事情。那么，與時間相關的其他信息誰去處理，何時處理？這就是由第三章討論的后半部分去去處理。上面timer_interrupt()所做的事情就是上半部分。
（4）中斷安裝程序
從上面的介紹可以看出，時鐘中斷與進程調度密不可分，因此，一旦開始有時鐘中斷就可能要進行調度，在系統進行初始化時，所做的大量工作之一就是對時鐘進行初始化，其函數time_init ()的代碼在/arch/i386/kernel/time.c中，對其簡寫如下：
void __init time_init(void)
{
xtime.tv_sec=get_cmos_time();
xtime.tv_usec=0;
setup_irq（0，＆irq0）;
}
其中的get_cmos_time()函數就是把當時的實際時間從CMOS時鐘芯片讀入變量xtime中，時間精度為秒。而setup_irq（0，＆irq0）就是時鐘中斷安裝函數，那么irq0指的是什么呢，它是一個結構類型irqaction，其定義及初值如下：
static struct irqaction irq0 = { timer_interrupt， SA_INTERRUPT， 0， "timer"， NULL， NULL};
setup_irq(0， &irq0)的代碼在/arch/i386/kernel/irq.c中，其主要功能就是將中斷程序連入相應的中斷請求隊列，以等待中斷到來時相應的中斷程序被執行。
我們將有關函數改寫如下，體現時鐘中斷的大意：
do_timer_interrupt( ) ／*這是一個偽函數 *／
{
SAVE_ALL ／*保存處理機現場 *／
intr_count += 1; ／* 這段操作不允許被中斷 *／
timer_interrupt() ／* 調用時鐘中斷程序 *／
intr_count -= 1;
jmp ret_from_intr /* 中斷返回函數 *／
}
#p#其中，jmp ret_from_intr 是一段匯編代碼，也是一個較為復雜的過程，它最終要調用jmp ret_from_sys_call，即系統調用返回函數，而這個函數與進程的調度又密切相關，，因此，我們重點分析jmp ret_from_sys_call。
2．系統調用返回函數：
系統調用返回函數的源代碼在/arch/i386/kernel/entry.S中
ENTRY(ret_from_sys_call)
cli # need_resched and signals atomic test
cmpl $0，need_resched(%ebx)
jne reschedule
cmpl $0，sigpending(%ebx)
jne signal_return
restore_all:
RESTORE_ALL
ALIGN
signal_return:
sti # we can get here from an interrupt handler
testl $(VM_MASK)，EFLAGS(%esp)
movl %esp，%eax
jne v86_signal_return
xorl %edx，%edx
call SYMBOL_NAME(do_signal)
jmp restore_all
ALIGN
v86_signal_return:
call SYMBOL_NAME(save_v86_state)
movl %eax，%esp
xorl %edx，%edx
call SYMBOL_NAME(do_signal)
jmp restore_all
….
reschedule:
call SYMBOL_NAME(schedule) # test
jmp ret_from_sys_call
這一段匯編代碼就是前面我們所說的“從系統調用返回函數”ret_from_sys_call，它是從中斷、異常及系統調用返回時的通用接口。這段代碼主體就是ret_from_sys_call函數，在此我們列出相關的幾個函數：
（1）ret_from_sys_call：主體
（2）reschedule：檢測是否需要重新調度
（3）signal_return：處理當前進程接收到的信號
（4）v86_signal_return：處理虛擬86模式下當前進程接收到的信號
（5）RESTORE_ALL：我們把這個函數叫做徹底返回函數，因為執行該函數之后，就返回到當前進程的地址空間中去了。
可以看到ret_from_sys_call的主要作用有：
檢測調度標志need_resched，決定是否要執行調度程序；處理當前進程的信號；恢復當前進程的環境使之繼續執行。
最后我們再次從總體上瀏覽一下時鐘中斷：
每個時鐘滴答，時鐘中斷得到執行。時鐘中斷執行的頻率很高：100次/秒，時鐘中斷的主要工作是處理和時間有關的所有信息、決定是否執行調度程序以及處理下半部分。和時間有關的所有信息包括系統時間、進程的時間片、延時、使用CPU的時間、各種定時器，進程更新后的時間片為進程調度提供依據，然后在時鐘中斷返回時決定是否要執行調度程序。下半部分處理程序是Linux提供的一種機制，它使一部分工作推遲執行。
【編輯推薦】
