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