本章描述了 Linux 核心的一些基本任務和機制, 有了它們， 核心中的其他部份才能夠在 一起有效地運轉. 11.1 Bottom Half Handling (任務的延遲處理)
圖 11.1 ：Bottom Half Handling 資料結構
圖 11.2: 一個任務隊列
圖 11.3: 系統定時器
|
*task |
| *next |
本章描述了 Linux 核心的一些基本任務和機制, 有了它們， 核心中的其他部份才能夠在 一起有效地運轉. 11.1 Bottom Half Handling (任務的延遲處理)核心中經常會遇到一些需要延遲處理的工作。 中斷處理的過程就是一個很好的例子。 當中斷發生時， 處理器停下正在做的工作， 作業系統把中斷事件通知給相應的設備驅動 程式。 設備驅動程式不應當用過多的時間處理這個中斷， 因為這時系統的其他部份全部 停了下來。 通常總是有一部份工作不必非要現在就做完， 晚一點處理也行， (從而讓系 統的其他部份能夠早點恢復運行)。 Linux 中設計了 bottom half handlers 使設備驅動程式和 核心的其他部份能夠排隊處理延遲的工作。 圖11.1中給出了同 bottom half handling 有關的 核心資料結構。 核心中最多可以有32個不同的 bottom half handler， bh_base 是一個指標向量， 這些指 針就指向核心的各個 bottom half haldling 過程。 bh_active 和 bh_mask 中的 bit 位指示了系 統中安裝的 handler 和正在進行處理的 handler。 如果 bh_mask 的第 N bit 位是1， 那麼 bh_base 向量中的第N個指標份量就指向一個 bottom half 處理過程。 如果bh_active的第N bit 位是1， 那麼核心中的排程程式就會在適當的時候調用這個 handler。 Handler 的順序 是靜態定義的: timer bottom half haldler 優先級最高, console bottom half handler 其次， ... 通常 bottom half handling 過程具有自己的 task 列表。 例如， immediate bottom half handler 就用 immediate tasks queue (tq_immediate) 來排隊需要及時處理的 task。 核心中有些 bottom half handler 是設備專用的， 下面一些則是通用的: TIMER (定時器) 這個 handler 每當系統的時鐘中斷發生時就啟動， 系統用這個 handler 來驅動核心的 timer 隊列. CONSOLE (控制台) 這個 handler 處理控制台消息。 TQUEUE 這個 handler 處理 tty 消息。 NET 這個 handler 負責網路方面的處理工作。 IMMEDIATE 這是一個通用的 handler， 一些設備驅動程式用它來排隊需要延遲處理的工作。 當設備驅動程式或者核心的其他部份需要安排延遲完成的工作時， 就把工作加到系統 隊列去， 比如 timer隊列， 然後通知核心有 bottom half handling 需要完成， 方法就是設置 bh_active 的相應的 bit 位。 如果驅動程式把工作加入了 immediate 隊列並要求 immedia bottom half handler 來處理它， 就會設置 bh_active 的第8 bit位。 在每次系統調用結束，返 回調用程序之前， 核心就要檢查 bh_active ， 如果有某個 bit 位被設置了， 相應的 handler 就會被調用。 檢查的順序是先第0 bit， 最後是第31 bit。 當某個 handler 被調用了之後， bh_active 中的相應 bit 就被清除。 所以 bh_active 的值 只在瞬間有效。 它只在對排程器的調用之間有意義， 是為了避免無謂地調用這些 handling 例程。 11.2 Task Queues (任務隊列) 核心中使用任務隊列管理延遲的工作。 Linux 有一個通用的機制來對工作排隊， 以便 以後處理。 任務隊列經常和 bottom half handler 一起使用。 例如： 當 timer queue buttom half handler 運行時， 它要處理 timer 任務隊列， 提供定時器服務。 任務隊列是一個簡單的數 據結構， 請參看圖 11.2， 它包括一個 tq_struct 資料結構的單鏈結串列， tq_struct 包括一個例 程的位址以及一個指標指向一些資料。 當這個任務隊列被處理的時候， 每個 tq_struct 單元中的例程就會被調用， 參數則是那 個指標。 核心的各個部份， 例如設備驅動程式， 都能創建並使用任務隊列。 核心自己創建和管 理著下面3個隊列： 1。 timer (定時器) 這個隊列中的工作在下一次系統時鐘中斷發生時就會被處理。 每當時鐘滴答一次， 就檢查一下這個隊列是不是有工作要處理， 如果有， timer queue bottom half handler 就被 標記為 active. 當排程器下次被調用的時候， 就會調用 timer queue bottom half handler。 不 要把這個隊列和系統定時器混淆起來， 那是一個復雜得多的機制。 2。 immediate (盡快) 這個隊列也會被排程器處理。 但是它的優先級沒有定時器隊列那麼高。 3。 scheduler (排程器) 這個任務隊列由排程器直接處理。 這是被用來支援系統中的其他任務隊列的。 也就 是說， 它的任務是一個個處理任務隊列的例程， 例如， 設備驅動程式的任務隊列的處理 就會被添加到這裡。 處理任務隊列的時候， 隊列中指向第一個節點的指標被刪除， 代之以一個空指標。 實 際上， 這個操作不可中斷， 是個 "最基本" 操作。 然後隊列中的每個節點的處理例程都會被 依次調用。 隊列中的節點通常是靜態分配的資料。 但是沒有一個統一的機制來時方所分 配的記憶體。 負責處理任務列表的例程在調用完節點的處理例程之後， 就簡單地移向下一 個節點。 那個任務自己應該擔負起釋放核心記憶體的責任。 11.3 Timers (定時器) 作業系統經常需要能把一項活動安排在將來某個時間進行。 需要有一種機制保証能夠 把任務安排到一個相對比較精確的時間進行處理。 任何能夠支援作業系統的微處理器必 定有一個可程式化的間隔定時器， 能夠周期性地中斷處理器。 這個周期性的中斷就是系統 時鐘的滴答。 如果把系統比作一個交響樂隊， 它就像一個節拍器， Linux 對於時間的理 解很簡單： 它從系統啟動開始記錄系統時鐘的滴答數目， 以此衡量時間。 系統中用到時 間的地方都以此為衡量的基礎， 這就是所說的 jiffy 單位的由來。 核心中有一個全局變數 叫 jiffies, 就是這個記錄的值。 Linux 中有兩種系統定時器， 都能把事務排隊等到某個系統時間來處理。 但是這兩者 的實現稍有不同。 圖 11.3 中對比了這兩種機制。 第一種是老式的定時器機制， 有一個靜態的陣列， 包含32個 timer_struct 資料結構以及 一個用位元遮罩指示活動定時器的整數： timer_active 。 由於定時器列表中的定時器是靜態定義的， (就像 bottom half handler 表中的 bh_base)， 表中的表項一般都是在系統初始化的時候加入的。 第二種新機制使用了 time_list 資料結構的鏈結串列把定時器按到達時間的早晚從早到晚鏈接 起來。 兩種機制都使用了 jiffy 作為時間單位。 因此， 一個5秒的定時器要把5秒轉換為 jiffy 單 位， 然後和目前系統時間相加， 以此設置定時器。 每當系統時鐘滴答一次， timer bottom half handler 就被標記為 active， 這樣當排程器被運行時， 就會處理定時器隊列。 timer bottom half handler 對兩種系統定時器都要處理。 對於老式的系統定時器， 要檢查 timer_active 位元遮罩找出設定了相應位的定時器， 如 果某個定時器設定的時間已到(它設定的時間小於目前系統時間)， 它的定時器例程就會被 調用。 並且對應的位元遮罩會被清除。 對於新式的系統定時器， 則檢查 timer_list 鏈結串列中的 節點， 每個到期的定時器會被從鏈結串列中清除， 並且節點中的定時器例程會被調用。 新機 制的好處是在調用定時器例程的時候能夠傳遞一個參數。 (當然新機制的顯而易見的好處 是不限制定時器的數目， 這是老式的機制不能做到的， 譯者注)。 11.4 Wait Queues (等待隊列) 程序經常需要等待系統資源。 例如， 程序可能需要一個目錄的 VFS i節點而這個節點 可能不在檔案系統的高速緩衝區中。 這時， 程序就必須等待系統從包含這個 i節點的實體 介質上面得到這個節點的內容才能繼續運行。 wait_queue
*task
*next
圖 11.4: 等待隊列 Linux 核心使用了一個很簡單的資料結構， 叫做等待隊列(見 圖 11.4)， 它包含一個指向 程序的 task_struct 結構的指標， 還有一個指向隊列中下一個節點的指標。 被加進這個隊列的程序既有不可中斷的(uninterruptible)有又可以中斷(interruptible)的(進 程的狀態中有 UNINTERRUPTIBLE 和 INTERRUPTIBLE 來標誌). 可中斷的程序可能會被事 件打斷， 比如它的定時器到時了， 或者有信號發送給這個程序。 因為現在這個程序不能 繼續運行， 排程器會運行， 當它選擇了新的程序運行時， 這個等待的程序就被暫停了。 在處理等待隊列的時候， 隊列中的每個程序的狀態都被設置為 RUNNING (運行態)。 如 果這個程序已經被移出了運行隊列(run queue), 它又會被放回去。 當排程器下次運行時， 等待隊列中的程序就又有機會被選中運行了， 因為它們已經不再等待什麼了。 當處於等 待隊列中的程序被排程運行時， 它做的第一件事就是把自己從等待隊列中移出。 等待隊 列可以被用於同步對系統資源的存取， 在 Linux 系統中用於實現 semaphore (信號量， 下 面會講到)。 11.5 Buzz Locks (Buzz 鎖) 更多的叫法是轉鎖(spin lock)。 它是保護資料結構或者一段程式碼的最基本的方法。 它一 次只允許一個程序處於危險(可能產生衝突)的程式碼區域(臨界區)。 在 Linux 中， Buzz 鎖被 用於限制對資料結構中的域的存取。 使用一個整數作為鎖， 初始值為1。 每個想進入臨 界區的程序試圖把鎖的值從0改變為1。 如果目前的值就是1， 程序就會再試一次。 通過 一個緊致的循環反復嘗試。 對保存鎖的值的記憶體區域的存取必須是最基本化的， 讀取目前 數值， 檢查是不是0以及把它改為1這些操作必須一次完成， 不能被別的程序中斷。 大多 數 CPU 提供了特殊的指令來實現這一點， 但是也能夠使用不緩衝的主記憶體來實現 buzz 鎖。 當擁有這個鎖的程序離開臨界區之後， 它需要釋放鎖， 把鎖的值改為0。 其它正在轉 這把鎖的程序現在就會讀出0。 第一個來讀的程序將會再把它改為1並進入臨界區。 11.6 Semaphores (信號量) 信號量被用於保護程式碼的臨界區或資料結構。 請注意每次對臨界資料的存取， 例如存 取一個目錄的 VFS i節點， 是由核心程式碼代表用戶程序進行的。 允許一個程序能夠改變 改變另一個程序的也在使用的臨界資料結構是非常危險的。 一種辦法是使用 buzz 鎖來防 止衝突， 但是這種最簡單的方法性能很差。 Linux 系統中使用信號量來做保護： 只有得 到信號量保護的資源的那個程序能夠存取臨界區， 而其它等待資源的程序被暫停。 Linux 中的信號量資料結構包含下列信息： count (計數) 這裡記錄需要使用資源的程序的數目。 一個正的數值表明這個資源現在可用。 一個 負的數值和0表明現在有程序在等待這個資源。 如果初始數值為1， 那麼同一個時刻只能 有一個程序能夠使用這個資源。 如果程序需要使用這個資源， 就把計數值減1， 使用完 資源之後再把這個值加1。 waking (喚醒) 這是正在等待資源的程序的數目。 當資源被釋放的時候， 就有這麼多程序等待被喚 醒。 wait queue (等待隊列) 當程序等待這個資源的時候， 它們被放在這個等待隊列裡面。 lock 一個 buzz 鎖用來保護對 waking 域的存取。 假設信號量的初始值是1， 第一個來訪的程序看到數值1， 並把它減1 變為0。 這個進 程就"擁有"了被信號量鎖保護的資源。 當程序不再需要使用資源之後， 就把信號量的計 數加1。 最理想的情況就是沒有其它的程序競爭這個資源。 Linux 對信號量的實現在這種 最常見的情況下效率很高。 當另一個程序也想同時存取臨界區的時候， 它也要把計數減1。 因為現在計數為 -1， 所以這個程序不能進入臨界區。 Linux 讓這個等待的程序睡眠(進入等待狀態)。 直到擁有 資源的程序釋放資源的時候來喚醒它。 等待的程序把自己添加到信號量的等待隊列上， 然後進入循環， 檢查 waking 域的值並調用排程器直到 waking 域的值不為0。 擁有資源的程序在釋放資源的時候， 增加信號量的計數， 並檢查， 在理想情況下， 計數被恢復為1， 沒有什麼事情要做﹔ 如果不大於0， 說明還有程序在等待這個資源。 這時， 就增加 waking 域的值， 並喚醒一個在信號量的等待隊列裡的程序。 當這個等待 的程序被喚醒的時候， waking 現在是1， 它就知道自己現在擁有這個資源， 可以進入臨 界區了。 它就減少 waking 的值， 然後繼續運行。 對 waking 域的存取要通過一個 buzz 鎖 來保護， 這個鎖使用信號量的 lock 域作為自己的值。