- 論壇徽章:
- 0
|
第8章. 加鎖速度
在考慮使用鎖的代碼的速度問題上，主要有三件事需要關注。首先是并發(fā)性：當鎖被別人持有時，有多少事情是我們需要等待的。其次是，需要花多少時間來獲取與釋放一把無爭議的鎖。第三呢，是盡量使用更少的──或曰更靈活的──鎖。當然，這里我已經假定鎖的使用非常頻繁，否則你都不用擔心效率問題的。
并發(fā)性依賴于鎖被持有多長時間：你持有鎖的時間，就應該同確實需要持有它的時間一樣長，不要更長。在上面那個關于cache的例子中，我們在創(chuàng)建對象時是不持有鎖的，只有在已經準備好把它插入到鏈表中時才去獲取鎖。
獲取鎖的時間依賴于加鎖操作對于管道線(pipeline stalls)做了多少破壞性工作，以及本CPU是最后一個試圖獲取該鎖的CPU(亦即：對本CPU來說，鎖是否為緩存密集的(cache-hot))的可能性有多大：在具有很多CPU的機器上，這種可能性迅速降低�？紤]一個700MHz的Intel Pentium III處理器：一條指令大約花費0.7納秒，一次原子增加操作大約花費58納秒，一次緩存密集的的加鎖操作大約花費160納秒，而從其他CPU上的一次緩存行轉換還要額外花費170到360納秒。(這些數據來自于Paul McKenney的Linux Journal RCU article )
這兩個目標會發(fā)生沖突：通過把鎖分成不同的的部分，可以減少持有鎖的時間(例如上面例子中“每個對象一把的鎖”)，但是這增加了獲取鎖這一操作的數量，因而結果一般是比只有一把鎖的情況要慢一些。這也是推崇加鎖簡潔性的一個理由。
第三個考慮點放到了下面：的確存在一些方法能夠減少鎖的使用。
8.1. 讀/寫鎖變體
自旋鎖與信號量都具有讀/寫變體：rwlock_t和struct rw_semaphore。它們把使用者分成了兩類：讀者和寫者。如果你只需要讀數據，你該獲取讀鎖；但如果你需要寫數據，你需要獲取寫鎖�？梢杂泻芏嗍褂谜咄瑫r獲取讀鎖，但寫鎖卻只能有單個使用者持有。
如果你的代碼可以簡潔的劃分出讀和寫的界限(就象我們上面的cache代碼那樣)，而且讀者通常需要很長時間的持有讀鎖，使用讀寫鎖會更好。它們要比普通的鎖要稍微慢點兒，所以在實踐中rwlock_t通常并不很值得使用。
8.2. 避免鎖的使用：RCU
有一種特殊的讀/寫鎖定方法叫做RCU(Read Copy Update)，讀者可以完全避免使用鎖：由于我們希望我們的cache被讀取遠比被更新來的頻繁(否則的話，還引入cache干什么？)，使用RCU就是一個可選擇的優(yōu)化。
如何移除讀鎖呢？移除讀鎖意味著寫者可能在存在讀者的情況下更新鏈表。這很簡單：要向鏈表中添加元素的代碼足夠小心，我們就可以在它添加的同時讀取鏈表。例如，把new元素添加到list鏈表中：
- new->next = list->next;
- wmb();
- list->next = new;
-
wmb()是一個寫內存屏障。它保證了第一個操作（設置新元素的next指針）是完整的，而且立即為其它CPU所見，這發(fā)生在第二個操作（把新元素添加到鏈表中）之前。這是很重要的，因為現代CPU和編譯器可能會改變指令的執(zhí)行順序，除非明確告訴它們不要這樣：我們希望一個讀者要么完全看不到新元素的插入，要么能夠看到新元素插入之后的next指針正確指向了鏈表的剩余部分。
幸運的是，有一個函數專門添加標準的struct list_head鏈表：list_add_rcu() (include/linux/list.h)。
從鏈表中刪除元素更簡單：假設我們要刪除的元素為A，我們讓指向A的指針重新指向A的后繼者，讀者要么完全看到了它，要么完全忽略了它。
list->next = old->next;
有一個list_del_rcu()函數(include/linux/list.h)來做該工作（而普通版本的刪除操作會毒害(poison)要移除的對象，這是我們不愿看到的）。
讀者也一定要小心：有些CPU會觀察next指針以便預取下一個元素，但這樣的話，如果next指針恰恰在這時候發(fā)生了變化，那么這些CPU預取的(pre-fetched)內容就是錯誤的。還好，有一個list_fro_each_entry_rcu()函數(include/linux/list.h)可以幫助你。當然，寫者可以只使用list_for_each_entry() （譯者案：這里的“只使用”，是說不用但是是否需要一個XXX_rcu()這樣的函數），因為不可能同時有兩個寫者。
我們的困難最終是：什么時候我們可以真正的刪除元素？記住，一個讀者可能正在訪問要被刪除的元素：如果我們釋放掉這個元素，而讓next指針指向新元素，讀者將立即訪問到垃圾內存并崩潰。我們必須等待到所有正在遍歷鏈表的讀者都結束了遍歷，才能真正釋放掉元素。我們用call_rcu()函數注冊一個回調函數，當所有讀者結束遍歷時，它會真正銷毀對象。
但是，RCU如何得知什么時候讀者結束遍歷了呢？首先，讀者總是在rcu_read_lock()/rcu_read_unlock()之間執(zhí)行遍歷：這會禁止搶占（而且只是禁止搶占，其它什么都不做），因此讀者在遍歷鏈表期間不會睡眠。
RCU一直等待到其他的CPU至少睡眠了一次：因為讀者不會在讀取過程中睡眠，此時我們就知道我們等待其結束的那些讀者終于都結束了。于是回調函數被調用。真實的RCU代碼要比這里講述的更優(yōu)化些，但這里講的是它的基礎。
- --- cache.c.perobjectlock 2003-12-11 17:15:03.000000000 +1100
- +++ cache.c.rcupdate 2003-12-11 17:55:14.000000000 +1100
- @@ -1,15 +1,18 @@
- #include <linux/list.h>
- #include <linux/slab.h>
- #include <linux/string.h>
- +#include <linux/rcupdate.h>
- #include <asm/semaphore.h>
- #include <asm/errno.h>
-
- struct object
- {
- - /* 下面兩個域由cache_lock保護 */
- + /* 下面由RCU保護 */
- struct list_head list;
- int popularity;
-
- + struct rcu_head rcu;
- +
- atomic_t refcnt;
-
- /* 一旦創(chuàng)建就不要更改. */
- @@ -40,7 +43,7 @@
- {
- struct object *i;
-
- - list_for_each_entry(i, &cache, list) {
- + list_for_each_entry_rcu(i, &cache, list) {
- if (i->id == id) {
- i->popularity++;
- return i;
- @@ -49,19 +52,25 @@
- return NULL;
- }
-
- +/* 一旦我們知道沒有讀者了，立即最終丟棄對象. */
- +static void cache_delete_rcu(void *arg)
- +{
- + object_put(arg);
- +}
- +
- /* 必須在持有cache_lock的情況下調用 */
- static void __cache_delete(struct object *obj)
- {
- BUG_ON(!obj);
- - list_del(&obj->list);
- - object_put(obj);
- + list_del_rcu(&obj->list);
- cache_num--;
- + call_rcu(&obj->rcu, cache_delete_rcu, obj);
- }
-
- /* 必須在持有cache_lock的情況下調用 */
- static void __cache_add(struct object *obj)
- {
- - list_add(&obj->list, &cache);
- + list_add_rcu(&obj->list, &cache);
- if (++cache_num > MAX_CACHE_SIZE) {
- struct object *i, *outcast = NULL;
- list_for_each_entry(i, &cache, list) {
- @@ -85,6 +94,7 @@
- obj->popularity = 0;
- atomic_set(&obj->refcnt, 1); /* cache本身占一個引用計數 */
- spin_lock_init(&obj->lock);
- + INIT_RCU_HEAD(&obj->rcu);
-
- spin_lock_irqsave(&cache_lock, flags);
- __cache_add(obj);
- @@ -104,12 +114,11 @@
- struct object *cache_find(int id)
- {
- struct object *obj;
- - unsigned long flags;
-
- - spin_lock_irqsave(&cache_lock, flags);
- + rcu_read_lock();
- obj = __cache_find(id);
- if (obj)
- object_get(obj);
- - spin_unlock_irqrestore(&cache_lock, flags);
- + rcu_read_unlock();
- return obj;
- }
注意讀者會在__cache_find()中改變popularity域的值，但是沒有使用鎖。我們的方案應該把它變成atomic_t類型的，但是對本例來說我們不會導致競態(tài)條件：近似的結果就已經不錯了，所以我沒做改變。
結果是，cache_find()函數并不需要與其它函數同步，因此它在SMP上幾乎跟在UP上一樣快。
此處還存在一個更縱深的可能的優(yōu)化：想一想我們最初的cache代碼，那時沒有引用計數，無論何時調用者想訪問對象，就要持有鎖。這仍然是可能的：如果你持有鎖，就沒人能夠刪掉對象，因此你就不必讀取并寫回引用計數了。
由于RCU中的“讀鎖”會禁止搶占（而且只是禁止搶占，其它什么都不做），調用者如果調用cache_find()或object_put()之前已經禁止搶占了，就并不需要讀取并寫回引用計數：我們可以把__cache_find()變成非static的從而暴露給其它文件，這時候調用者就可以直接調用這些函數了。
此處的優(yōu)勢是：引用計數并不被寫入，對象并不被更改，這在SMP機器上會非�？飑ぉび捎贑PU的caching的原因。
8.3. Per-CPU數據
另一種使用相當廣泛的避免鎖的技術是，為每個CPU使用數據的一份拷貝。例如，如果你想為一個普通的條件保持一個計數，你可能會使用自旋鎖和一個計數器，這簡單而漂亮。
如果它表現的太慢了(通常不會，但是如果你的確測試到這種情況發(fā)生了)，你就該改變一下策略：為每個CPU保持一個計數器，這樣，沒有一個計數器需要互斥的鎖來保護。參考DEFINE_PER_CPU()，get_cpu_var()和put_cpu_var() (include/linux/percpu.h)。
Per-CPU計數器的另一個用場是local_t數據類型，和cpu_local_inc()以及其它的相關函數。這在某些體系結構上是比簡單的加鎖代碼更高效的。(include/asm/local.h)
注意，對計數器來說，根本不存在簡單而可靠的方法可以精確的得到它的值而不需要引入鎖。只不過某些情況下這不是問題罷了。
8.4. 中斷服務例程通常使用哪些數據
如果數據只是在中斷服務例程內部訪問，你根本不需要鎖：內核本身已經保證了中斷服務例程不會同時在多個CPU上運行。
Manfred Spraul指出，即使數據會偶爾被用戶上下文或softirqs/tasklets訪問，你仍然可以這樣。中斷服務例程自身不需要鎖，其它所有的訪問者這樣做：
- spin_lock(&lock);
- disable_irq(irq);
- ...
- enable_irq(irq);s
- spin_unlock(&lock);
disable_irq()禁止了中斷服務例程的運行(如果此刻已經在別的CPU上運行了，那就等待它的結束)。自旋鎖禁止了同時刻其它任何可能的訪問。自然，這比單個spin_lock_irq()調用要慢些，所以只有這種訪問很少發(fā)生時這種用法才是合理的。 |
|
免費注冊
樓主: albcamus
發(fā)表于 2005-11-25 17:56
