第十一章 核心機制 本章主要描敘Linux核心為使核心其他部分能有效工作而提供的幾個常用任務與機制。 11.1 底層部分處理機制 圖11.1 底層部分處理機制數據結構 某些特殊時刻我們並不願意在核心中執行一些操作。例如中斷處理過程中。當中斷發生時處理器將停止
第十一章 核心機制
本章主要描敘Linux核心為使核心其他部分能有效工作而提供的幾個常用任務與機制。
11.1 底層部分處理機制
圖11.1 底層部分處理機制數據結構
某些特殊時刻我們並不願意在核心中執行一些操作。例如中斷處理過程中。當中斷發生時處理器將停止當前的工作, 操作系統將中斷發送到相應的設備驅動上去。由於此時系統中其他程序都不能運行, 所以設備驅動中的中斷處理過程不宜過長。有些任務最好稍後執行。Linux底層部分處理機制可以讓設備驅動和Linux核心其他部分將這些工作進行排序以延遲執行。圖11.1給出了一個與底層部分處理相關的核心數據結構。
系統中最多可以有32個不同的底層處理過程；bh_base是指向這些過程入口的指針數組。而bh_active和 bh_mask用來表示那些處理過程已經安裝以及那些處於活動狀態。如果bh_mask的第N位置位則表示bh_base的 第N個元素包含底層部分處理例程。如果bh_active的第N位置位則表示第N個底層處理過程例程可在調度器認 為合適的時刻調用。這些索引被定義成靜態的；定時器底層部分處理例程具有最高優先級（索引值為0）， 控制台底層部分處理例程其次（索引值為1）。典型的底層部分處理例程包含與之相連的任務鏈表。例如 immediate底層部分處理例程通過那些需要被立刻執行的任務的立即任務隊列（tq_immediate）來執行。
有些核心底層部分處理過程是設備相關的，但有些更加具有通用性：
TIMER
每次系統的周期性時鐘中斷發生時此過程被標記為活動，它被用來驅動核心的定時器隊列機制。
CONSOLE
此過程被用來處理進程控制台消息。
TQUEUE
此過程被用來處理進程tty消息。
NET
此過程被用來做通用
網絡處理。
IMMEDIATE
這是被幾個設備驅動用來將任務排隊成稍後執行的通用過程。
當設備驅動或者核心中其他部分需要調度某些工作延遲完成時，它們將把這些任務加入到相應的系統隊列中去，如定時器隊列，然後對核心發出信號通知它需要調用某個底層處理過程。具體方式是設置bh_active中的某些位。如果設備驅動將某個任務加入到了immediate隊列並希望底層處理過程運行和處理它,可將第8位置1。每次系統調用結束返回調用進程前都要檢查bh_active。如果有位被置1則調用處於活動狀態的底層處理過程。檢查的順序是從0位開始直到第31位。
每次調用底層處理過程時bh_active中的對應位將被清除。bh_active是一個瞬態變量，它僅僅在調用調度管理器時有意義；同時它還可以在空閒狀態時避免對底層處理過程的調用。
11.2 任務隊列
圖 11.2: 一個任務隊列
任務隊列是核心延遲任務啟動的主要手段。 Linux 提供了對隊列上任務排隊以及處理它們的通用機制。
任務隊列通常和底層處理過程一起使用；底層的定時器隊列處理過程運行時對定時器隊列進行處理。任務隊列的結構很簡單，如圖 11.2 所示，它由一個tq_struct結構鏈表構成，每個節點中包含處理過程的地址指針以及指向數據的指針。
處理任務隊列上元素時將用到這些過程，同時此過程還將用到指向這些數據的指針。
核心的所有部分，如設備驅動, 都可以創建與使用任務隊列。但是核心自己創建與管理的任務隊列只有以下三個:
timer
此隊列用來對下一個時鐘滴答時要求盡快運行的任務進行排隊。每個時鐘滴答時都要檢查此隊列看是否為空，如果不為空則定時器底層處理過程將激活此任務。當調度管理器下次運行時定時器隊列底層處理過程將和其他底層處理過程一道對任務隊列進行處理。這個隊列不能和系統定時器相混淆。
immediate
immediate 底層處理過程的優先級低於定時器底層處理過程，所以此類型任務將延遲運行。
scheduler
此任務隊列直接由調度管理器來處理。它被用來支撐系統中其他任務隊列，此時可以運行的任務是一個處理任務隊列的過程，如設備驅動。
當處理任務隊列時，處於隊列頭部的元素將從隊列中刪除同時以空指針代替它。這個刪除操作是一個不可中斷的原子操作。隊列中每個元素的處理過程將被依次調用。這個隊列中的元素通常使用靜態分配數據。 然而並沒有一個固有機制來丟棄已分配內存。任務隊列處理例程簡單的指向鏈表中下一個元素。這個任務才真正清除任何已分配的核心內存。
11.3 定時器（TIMER）
圖11.3 系統定時器
操作系統應該能夠在將來某個時刻准時調度某個任務。所以需要一種能保證任務較准時調度運行的機制。希望支持每種操作系統的微處理器必須包含一個可周期性中斷它的可編程間隔定時器。這個周期性中斷被稱為系統時鐘滴答，它象節拍器一樣來組織系統任務。
Linux的時鐘觀念很簡單：它表示系統啟動後的以時鐘滴答記數的時間。所有的系統時鐘都基於這種量度，在 系統中的名稱和一個全局變量相同-jiffies。
Linux包含兩種類型的系統定時器，它們都可以在某個系統時間上被隊列例程使用，但是它們的實現稍有區別。 圖11.3畫出了這兩種機制。
第一個是老的定時器機制，它包含指向timer_struct結構的32位指針的靜態數組以及當前活動定時器的屏蔽碼 ：time_active。
此定時器表中的位置是靜態定義的（類似底層部分處理表bh_base）。其入口在系統初始化時被加入到表中。 第二種是相對較新的定時器，它使用一個到期時間以升序排列的timer_list結構鏈表。
這兩種方法都使用jiffies作為終結時間，這樣希望運行5秒的定時器將不得不將5秒時間轉換成jiffies 的單位並且將它和以jiffies記數的當前系統時間相加從而得到定時器的終結時間。在每個系統時鐘滴答時,定時器的底層部分處理過程被標記成活動狀態以便調度管理器下次運行時能進行定時器隊列的處理。定時器底層 部分處理過程包含兩種類型的系統定時器。老的系統定時器將檢查timer_active位是否置位。
如果活動定時器已經到期則其定時器例程將被調用同時它的活動位也被清除。新定時器位於timer_list結構鏈表中的入口也將受到檢查。每個過期定時器將從鏈表中清除,同時它的例程將被調用。新定時器機制的優點之一是能傳遞一個參數給定時器例程。
11.4 等待隊列
進程經常要等待某個系統資源。例如某個進程可能需要描敘文件系統中某個目錄的VFS inode但是此inode可 能不在buffer cache中。此時這個進程必須等到該inode從包含此文件系統的物理介質中取出來才可以繼續 運行。
wait_queue
*task
*next
圖11.4 等待隊列
Linux核心使用一個非常簡單的隊列：等待隊列（見圖11.4）。它包含一個指向進程task_struct結構的指針以及等待隊列中下一個元素的指針。加入到等待隊列中的進程既可以是可中斷也可以是不可中斷的。可中斷 進程能夠被如定時器到期或者信號等時間中斷。此等待進程的狀態必須說明成是INTER
RUPTIBLE還是 UNINTERRUPTIBLE。由於進程現在不能繼續運行則調度管理器將接過系統控制權並選擇一個新進程運行而等待進程將被掛起。處理等待進程時，每個處於等待隊列中的進程都被置為RUNNING狀態。如果此進程已經從運行隊列中刪除則它將被重新放入運行隊列。下次調度管理器運行時, 由於這些進程不再等待所以它們都將是運行候選者。 等待隊列可以用來同步對系統資源的訪問, 同時它們還被Linux用於信號燈的實現中。
11.5 Buzz 鎖
它使用更頻繁的名字叫自旋鎖。這是一種保護數據結構或代碼片段的原始方式。在某個時刻只允許一個進程訪問臨界區內的代碼。Linux還同時將一個整數域作為鎖來限制對數據結構中某些域的存取。每個希望進入 此區域的進程都試圖將此鎖的初始值從0改成1。如果當前值是1則進程將再次嘗試，此時進程好象在一段緊循環代碼中自旋。對包含此鎖的內存區域的存取必須是原子性的，即檢驗值是否為0並將其改變成1的過程不能被任何進程中斷。多數CPU結構通過特殊指令提供對此方式的支持，同時我們可以在一個非緩沖主存中實現這個流言鎖。
當控制進程離開臨界區時它將遞減此Buzz鎖。任何處於自旋狀態的進程都可以讀取它，它們中最快的那個將遞增此值並進入臨界區。
11.6 信號燈
信號燈被用來保護臨界區中的代碼和數據。請記住每次對臨界區數據, 如描敘某個目錄VFS inode的訪問, 是通過代表進程的核心代碼來進行的。允許某個進程擅自修改由其他進程使用的臨界區數據是非常危險的。防止此問題發生的一種方式是在被存取臨界區周圍使用buzz鎖，但這種簡單的方式將降低系統
性能。Linux使用信號燈來迫使某個時刻只有唯一進程訪問臨界區代碼和數據，其他進程都必須等待資源被釋放才可使用。這些等待進程將被掛起而系統中其他進程可以繼續運行。
一個Linux semaphore結構包含了以下信息：
count
此域用來保存希望訪問此資源的文件個數。當它為正數時表示資源可用。負數和0表示進程必須等待。當它初始值為1時表示一次僅允許一個進程來訪問此資源。當進程需要此資源時它們必須將此count 值減1並且在使用完後將其加1。
waking
這是等待此資源的進程個數，同時也是當資源可利用時等待被喚醒的進程個數。
wait queue
當進程等待此資源時，它們被放入此等待隊列。
lock
訪問waking域時使用的buzz鎖。
假設此信號燈的初始值為1，第一個使用它的進程看到此記數為正數，然後它將其減去1而得到0。現在此進程 擁有了這些被信號燈保護的段代碼和資源。當此進程離開臨界區時它將增加此信號燈的記數值，最好的情況 是沒有其他進程與之爭奪臨界區的控制權。Linux將信號燈設計成能在多數情況下有效工作。
如果此時另外一個進程希望進入此已被別的進程占據的臨界區時，它也將此記數減1。當它看到此記數值為-1 則它知道現在不能進入臨界區, 必須等待到此進程退出使用臨界區為止。在這個過程中Linux將讓這個等待 進程睡眠。等待進程將其自身添加到信號燈的等待隊列中然後系統在一個循環中檢驗waking域的值並當waking非0時調用調度管理器。
臨界區的所有者將信號燈記數值加1，但是如果此值仍然小於等於0則表示還有等待此資源的進程在睡眠。在 理想情況下此信號燈的記數將返回到初始值1而無需做其他工作。所有者進程將遞增waking記數並喚醒在此 信號燈等待隊列上睡眠的進程。當等待進程醒來時，它發現waking記數值已為1，那麼它知道現在可以進入臨界區了。然後它將遞減waking記數，將其變成0並繼續。所有對信號燈waking域的訪問都將受到使用信號燈 的buzz鎖的保護。
