Mutex與火車排班

在我心中，一直有個小心願，能以自己微弱的力量為這個社會多作些事情，包含免費的技術訓練，然而時間、精力是投入了，但不見得有效果，為此，我常常在反省。拜讀對岸高手Pengcheng Zou的blog - 「Linux地鐵」一文，我終於知道為什麼，畢竟技術或理論本身被提出，就是要克服現實問題，所以若能讓訓練本身更貼近現實，這樣才會發揮其價值。以下摘錄「Linux地鐵」一文的部份內容：

今天早上上班，快到地鐵就發現外面站了不少人，有做打車狀，有做打電話狀，隱約聽到有人說地鐵壞了。下到地鐵站台，果然看到兩列車停在那裡，站台上站滿了人。

後來在北京市地鐵運營有限公司網站上看到了事故原因：

11日早晨7點55分左右，地鐵2號線宣武門變電站瞬間過載跳閘，造成長椿街信號系統無法正常使用，列車運行方式被迫由自動閉塞改為電話閉塞，通過能力下降，運營間隔加大，造成長椿街臨近的復興門等重點站短時間乘客滯留。8點19分故障排除，地鐵運營方式隨後按自動閉塞方式運營，運營秩序逐步恢復正常。其間，2號線內外環西直門至宣武門早高峰列車間隔加大，列車最小間隔由原來3分半被迫延長到8至10分鐘，由於故障發生時正處於早高峰階段，客流本就較大，所以部分車站出現乘客短時滯留現象，地鐵1號線受此故影響有6列車在復興門站通過。13號線、八通線未受故障影響，運營正常。

何謂「閉塞」？寶貝爹地是鐵路的，正好請教。講 了半天，不甚了了。只好再從網上查，得知由車站向區間發車時必須確定區間內無車，還要防止兩個車站在同一線路上向同區間發車。這種按照一定的方法組織列車 在區間內的運行，稱為行車閉塞，用來聯絡的設備稱為閉塞設備。常用的閉塞設備有自動閉塞、半自動閉塞及電氣路籤閉塞等。地鐵採用自動閉塞設備。

這 下懂了，地鐵就是作業系統，所謂區間就是臨界區，閉塞裝置是各種同步機制，自動閉塞相當於spinlock，電話閉塞相當於semaphore。今天早上 效率比較高的spinlock失靈了，只好用效率較低而且不能用於中斷上下文的semaphore。所以導致系統性能下降，進程吞吐量明顯降低，客戶滿意 度下降。不少用戶轉而使用其他作業系統。

很多唸電腦科學的學生，往往在畢業後還不能理解那些同步理論的重要性，如今，火車排班就是最好的案例。Linux kernel中有兩種mutex (互斥)機制：

• semaphore
• spinlock

兩者主要區別是，semaphore在無法進入critical section (臨界區) 時，會引發context-switching，而若有硬體配合 (SMP) 的話，spinlock就沒有context-switching，這是許多教科書會提到的，但聽起來很奇怪吧？我們要思考的是本質，semaphore是process-level的操作，當有process要求進入critical section，好比在上面鐵路案例中，以電話要求區間的發車權，那麼，若critical section沒有被設置旗標，就可佔用並重設旗標，也就是我們可順利發車，但若不幸遇到該區間已經有車班呢？這時候該process就被迫「睡眠」，而本身也會被送入wait queue，這種枯等的經驗，想必很多通勤的朋友都能感受。我們也可以發現，這過程牽涉到process狀態的改變，因為勢必會有資源被釋放的時候 (但不保證)，屆時，被迫「睡眠」的項目也會因而被喚醒。

spinlock的本質是busy-waiting，聽起來很沒效率，但為何說在SMP很重要呢？最主要的原因是，沒有context-switch的負擔，沒有牽涉到process的狀態變化，在多處理器的環境下，spinlock相當有效率，而在單處理器上，卻只是disable/enable isr一類的操作。換過來想火車的案例，似乎就簡單多了，用電話通知本身涉及人與人的通訊內容、線路使用量，以及現實因素，可視為單處理器狀態，但如果是自動化，個別單元的協調時間是相當短的，所以可想成SMP架構，自然這兩者的mutex機制也有使用上的落差了。

當然，真的要探討Linux semaphore/spinlock的機制，其實複雜許多，特別在2.6 kernel還添入big kernel lock等新的機制，不過這些都出自典型作業系統理論 (命名可能有出入)，只要稍微變化一下，或許也能對應到現實。