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