## 第 21 章 多進程 上一章展示了續延是如何使運行中的程序獲知自己的狀態，并且把它保存起來以便之后重新執行的。這一章將討論一種計算模型，在這種模型中，計算機運行的不是單個程序，而是一組獨立的進程。進程的概念和程序狀態這一概念相當接近。通過在前一章的宏的基礎上再寫一層宏，我們就可以把多進程的機制融入到 Common Lisp 程序中。 ### 21.1 進程抽象 多進程這種表現形式，可以很方便地表示并行處理多個任務的程序。傳統的處理器同時只能執行一條指令。我們稱多進程能同時處理多件事情，并不是說它通過某種方式克服了硬件的限制，它真正的含義是：它使得我們可以在一個新的抽象層面上進行思考，在這個層面上我們不需要明確地指定計算機在任何給定的時間在做什么。就像虛擬內存給我們制造了一個錯覺，似乎計算機的可用內存比它的物理內存還要大，同樣的道理，多進程的概念使得我們可以假設計算機可以一次運行多個程序。 從傳統上說，對進程的研究屬于操作系統領域的范疇。但進程抽象帶來的進步并不局限于操作系統。它們在其他實時的應用程序和計算機仿真中一樣能大展身手。 有很多對于多進程的研究，它們的目的都是為了避免出現某些特定類型的問題。死鎖是多進程的一個經典問題：兩個進程同時停下等待另一個做某些事情，就像兩個人都拒絕在另一個人之前跨過門檻。另一個問題是查詢有可能碰到系統中數據不一致的狀態 例如，一個余額查詢正好在系統將資金從一個賬戶轉移到另一個賬戶時發生。這一章只討論進程抽象本身；這里展示的代碼可以用來測試避免死鎖和不一致狀態的算法，但代碼本身沒有對這些問題提供任何保護。 這一章中的實現遵循了本書所有程序默默恪守的一條準則：盡可能少的擾亂Lisp。在本質上來說，程序應該盡可能多的讓自己像是對語言的修改，而不是用語言寫就的一個獨立的應用程序。使程序與Lisp 協調一致可以使得程序更為健壯，好比部件配合良好的機器。這樣做也能事半功倍；有時你可以讓Lisp 為你代勞數量驚人的工作。 這一章的目標是構建一個支持多進程的的語言。我們的策略是通過添加一些操作符，將Lisp 變成這樣的語言。我們語言的基本構成元素如下： > **函數**?由前一章的 =defun 或者 =lambda 宏定義。 > > **進程**?由函數調用實例化。活動進程的數量和一個函數能夠實例化的進程數量都沒有限制。每個進程有一個優先級，初始值由創建時給出的參數指定。 > > **等待表達式(Waitexpressions)**?等待表達式接受一個變量，一個測試表達式和一段代碼體。如果進程遇到等待表達式，進程將在這一點被掛起，直到測試表達式返回真。一旦進程重新開始執行，代碼體會被求值，變量則被綁定到測試表達式的值。測試表達式通常不應該有副作用，因為它被求值的時間和頻率沒有任何保證。 > > **調度**?通過優先級來完成。在所有能夠重新開始執行的進程中，系統會運行優先級最高的進程。 > > **默認進程**?在其他進程都不能執行時運行。它是一個 read-eval-print 循環。 > > **創建和刪除**?絕大多數對象的操作可以即時進行。正在運行中的進程可以定義新的函數，實例化或者殺死進程。 續延使得保存 Lisp 程序的狀態成為可能。能夠同時保存多個狀態離實現多進程也不太遠了。有了前一章定義的宏做基礎，我們只要不到 60 行的代碼就可以實現多進程。 ### 21.2 實現 * * * **[示例代碼 21.1] 進程結構及實例化** ~~~ (defstruct proc pri state wait) (proclaim '(special *procs* *proc*)) (defvar *halt* (gensym)) (defvar *default-proc* (make-proc :state #'(lambda (x) (format t "~%>> ") (princ (eval (read))) (pick-process)))) (defmacro fork (expr pri) '(prog1 ',expr (push (make-proc :state #'(lambda (,(gensym)) ,expr (pick-process)) :pri ,pri) *procs*))) (defmacro program (name args &body body) '(=defun ,name ,args (setq *procs* nil) ,@body (catch *halt* (loop (pick-process))))) ~~~ * * * [示例代碼 21.1] 和圖 21.2 包含了所有用來支持多進程的代碼。[示例代碼 21.1] 包含了基本數據結構、默認進程、初始化、進程實例化的代碼。進程，或者說procs，具有如下結構： pri : 進程的優先級，它應該是一個正數。 state : 是一個續延，它用來表示一個掛起進程的狀態。我們可以 funcall 一個進程的 state 來重新啟動它。 wait : 通常是一個函數，如果要讓進程重新執行，它必須返回真，但剛創建的進程的 wait 為 nil 。wait 為空的進程總是可以被重新執行。 程序使用三個全局變量：*procs* ，當前被掛起的進程列表；*proc* ，正在運行的進程；還有 *default-proc* ，默認進程。 默認進程僅當沒有其他進程可以運行時才會運行。它模擬 Lisp 的 toplevel 循環。在這個循環中，用戶可以終止程序，或者輸入讓掛起進程恢復執行的表達式。請注意，默認進程顯式地調用了 eval。這是少數幾個合理使用 eval 的情形之一。一般來說，我們不贊成在運行時調用 eval ，這有兩個原因： 1. 效率低下：eval 直接處理原始列表，要么當場進行編譯，要么在解釋器中進行求值。不管哪種方式都比先編譯再調用來得慢。 2. 功能不夠強大，因為表達式不在詞法上下文中進行求值。舉個例子，這就意味著你不能引用在被求值表達式之外可見的普通變量。 通常來說，顯式調用eval 就像在機場禮品店買東西一樣。已經是最后關頭，你只得高價購買選擇有限的劣質商品。 像本例這樣兩條理由都不適用的情況是很少見的。我們沒法提前將表達式編譯好。直到讀取它們的時候才知道表達式是什么，所以沒法事先知道。同樣的，表達式無法引用它周遭的詞法環境，因為在toplevel 輸入的表達式處于空的詞法環境中。事實上，這個函數的定義直接反映了它的英語描述：它讀取并求值用戶的輸入。 宏 fork 使用一個函數調用來實例化進程。函數像平時一樣由 =defun 定義： ~~~ (=defun foo (x) (format t "Foo was called with ~A.~%" x) (=values (1+ x))) ~~~ 現在當我們以一個函數調用和優先級數值作為參數調用 fork 時： ~~~ (fork (foo 2) 25) ~~~ 一個新進程被加入到了 *procs* 里面。新進程的優先級為 25，因為它還沒有執行，所以 proc-wait 為 nil ，而 proc-state 包含了以 2 為參數的對 foo 的調用。 宏 program 使我們可以創建一組進程并一起執行它們。下面的定義： ~~~ (program two-foos (a b) (fork (foo a) 99) (fork (foo b) 99)) ~~~ 宏展開成了兩個 fork 表達式，被夾在負責清除掛起進程的代碼，以及不斷選擇進程來運行的代碼中間。在這個循環外面，program 宏設置了一個 tag，把控制流拋(throw) 到這個 tag 的話，就會終止這個程序(program)。因為這個 tag 是個生成符號，所以它不會與用戶設置的 tag 沖突。定義成 program 的一組進程不返回任何值，而且它們只應該在 toplevel 被調用。 進程實例化之后，進程調度代碼開始執行。它的代碼見 [示例代碼 21.2]。函數 pick-process 在可以繼續執行的進程中，選出優先級最高的一個，然后運行它。把這個進程找出來是 most-urgent-process 的工作。如果一個掛起的進程沒有 wait 函數或者它的 wait 函數返回真，那么它就被允許運行。在所有被允許運行的進程中，具有最高優先級的被選中。勝出的進程和它的 wait 函數(如果有的話) 返回的值被返回給 pick-process 。獲勝進程總是存在，因為默認進程總是想要執行。 [示例代碼 21.2] 中其余的代碼定義了用于在進程間切換控制權的操作符。標準的等待表達式是wait ，就像[示例代碼 21.3] 中函數 pedestrian 使用的那樣。在這個例子中，進程一直等到列表 *open-doors* 中有東西為止，然后打印一條消息： ~~~ > (ped) >> (push 'door2 *open-doors*) Entering DOOR2 >> (halt) NIL ~~~ 一個 wait 在實質上來說與 =bind (第 20.2 節) 相似，而且有著一樣的限制，那就是它必須在最后被求值。任何我們希望在wait 之后執行的東西必須被放在它的代碼體中。因此如果我們想要讓一個進程等待多次，那等待表達式必須被嵌套。通過聲明互相針對的事實，進程可以相互配合以達到某個目標，就像在 [示例代碼 21.4] 中一樣。 【】譯者注：即 (eval (read)) 【】譯者注：catch 操作符的用法可見CLHS 中的Special Operator CATCH 一節。 * * * **[示例代碼 21.2] 進程調度** ~~~ (defun pick-process () (multiple-value-bind (p val) (most-urgent-process) (setq *proc* p *procs* (delete p *procs*)) (funcall (proc-state p) val))) (defun most-urgent-process () (let ((proc1 *default-proc*) (max -1) (val1 t)) (dolist (p *procs*) (let ((pri (proc-pri p))) (if (> pri max) (let ((val (or (not (proc-wait p)) (funcall (proc-wait p))))) (when val (setq proc1 p max pri val1 val)))))) (values proc1 val1))) (defun arbitrator (test cont) (setf (proc-state *proc*) cont (proc-wait *proc*) test) (push *proc* *procs*) (pick-process)) (defmacro wait (parm test &body body) '(arbitrator #'(lambda () ,test) #'(lambda (,parm) ,@body))) (defmacro yield (&body body) '(arbitrator nil #'(lambda (,(gensym)) ,@body))) (defun setpri (n) (setf (proc-pri *proc*) n)) (defun halt (&optional val) (throw *halt* val)) (defun kill (&optional obj &rest args) (if obj (setq *procs* (apply #'delete obj *procs* args)) (pick-process))) ~~~ * * * **[示例代碼 21.3] 有一個等待的進程** ~~~ (defvar *open-doors* nil) (=defun pedestrian () (wait d (car *open-doors*) (format t "Entering ~A~%" d))) (program ped () (fork (pedestrian) 1)) ~~~ * * * 如果被給予相同的 door ，從 visitor 和 host 實例化的進程會通過黑板上的消息互相交換控制權： ~~~ > (ballet) ~~~ * * * **[示例代碼 21.4]： 利用黑板進行同步** ~~~ (defvar *bboard* nil) (defun claim (&rest f) (push f *bboard*)) (defun unclaim (&rest f) (pull f *bboard* :test #'equal)) (defun check (&rest f) (find f *bboard* :test #'equal)) (=defun visitor (door) (format t "Approach ~A. " door) (claim 'knock door) (wait d (check 'open door) (format t "Enter ~A. " door) (unclaim 'knock door) (claim 'inside door))) (=defun host (door) (wait k (check 'knock door) (format t "Open ~A. " door) (claim 'open door) (wait g (check 'inside door) (format t "Close ~A.~%" door) (unclaim 'open door)))) (program ballet () (fork (visitor 'door1) 1) (fork (host 'door1) 1) (fork (visitor 'door2) 1) (fork (host 'door2) 1)) ~~~ * * * ~~~ Approach DOOR2. Open DOOR2. Enter DOOR2. Close DOOR2. Approach DOOR1. Open DOOR1. Enter DOOR1. Close DOOR1. >> ~~~ 還有另外一類更簡單的等待表達式：yield ，它的唯一目的是讓其他更高優先級的進程有機會運行。 setpri 重置當前進程的優先級，一個進程可能在執行 setpri 表達式后想要讓出控制權。就像 wait 一樣，在 yield 之后執行的代碼都必須被放在它的代碼體中。 [示例代碼 21.5] 中的程序說明了這兩個操作符如何相互工作。開始時，野蠻人有兩個目的：占領羅馬和掠奪它。占領城市有著(稍微) 高一些的優先級，因此會先執行。然而，在城市淪陷之后，capture 進程的優先級減小到 1 。之后會有一次投票，而 plunder ，作為最高優先級的進程開始運行。 ~~~ > (barbarians) Liberating ROME. Nationalizing ROME. Refinancing ROME. Rebuilding ROME. >> ~~~ 只有在蠻族掠奪了羅馬的宮殿，并勒索了貴族之后，capture 進程才會恢復執行，此時他們開始為其領地建筑防御工事。 等待表達式的背后是一個更通用的 arbitrator。這個函數保存當前進程，然后調用 pick-process 來再次執行某個進程(有可能與當前進程為同一個)。它有兩個參數：一個測試函數和一個續延。前者會被存儲為掛起進程的 proc-wait ，在以后被調用來檢查它是否可以被重新執行。 宏 wait 和 yield 通過簡單的把它們的代碼體包在 --表達式中來建立這個續延函數。例如： * * * **[示例代碼 21.5] 改變進程優先級的效果** ~~~ (=defun capture (city) (take city) (setpri 1) (yield (fortify city))) (=defun plunder (city) (loot city) (ransom city)) (defun take (c) (format t "Liberating ~A.~%" c)) (defun fortify (c) (format t "Rebuilding ~A.~%" c)) (defun loot (c) (format t "Nationalizing ~A.~%" c)) (defun ransom (c) (format t "Refinancing ~A.~%" c)) (program barbarians () (fork (capture 'rome) 100) (fork (plunder 'rome) 98)) ~~~ * * * ~~~ (wait d (car *bboard*) (=values d)) ~~~ 被展開成： ~~~ (arbitrator #'(lambda () (car *bboard*)) #'(lambda (d) (=values d))) ~~~ 如果代碼遵循了 [示例代碼 20.5] 列出的限制，構造一個 wait 代碼體的閉包就可以保存當前的整個續延。隨著它的 =values 被展開，第二個參數變成： ~~~ #'(lambda (d) (funcall *cont* d)) ~~~ 由于這個閉包中有一個指向 *cont* 的引用，被這個等待函數掛起的進程將會擁有一個句柄(handle)，通過它，這個進程就能回到它當初被掛起的那一刻。 halt 操作符通過將控制權拋回program 展開式建立的標簽終止整個進程組。它接受一個可選參數，該參數的值會被作為這個進程組的值返回。因為默認進程始終想要執行，所以終止整個程序的唯一的方法是顯式的調用halt 。halt 后面是什么代碼并沒有關系，因為這些代碼不會被求值。 單個進程可以通過調用 kill 來殺死。如果沒有參數，這個操作符殺死當前進程。這種情況下，kill 就像是一個不保存當前進程的等待表達式。如果 kill 給定了參數，它們將成為進程列表上的 delete 操作的參數。在現在的代碼中，kill 表達式沒有什么好說的，因為進程沒有許多的屬性來被引用。然而，更復雜的系統會為它的進程附加更多的信息 時間戳、擁有者等等。默認進程不能被殺死，因為它并沒有被保存在*procs*?中。 ### 21.3 不那么快速的原型 通過續延模擬的進程，其性能遠不及真實操作系統的進程。那么，這一章中的程序又有什么用處呢？ 這些程序的用處類似于草圖。不管在探索式編程還是快速原型開發中，這些程序其自身并不是最終目的，更多的是作為實現人們想法的手段。在許多其他領域，為這個目的服務的東西被稱為草圖。在理論上，建譯者注：可以認為宏program 建立的由一組同時執行的進程組成的程序，但為與 "程序" 相區別，這里把 program 翻譯成 "進程組"。 筑師可以在他的腦海里構思出整棟大樓。但多數建筑師似乎在手里握著筆的時候能想得更周詳一些：一棟大樓的設計通常在一系列草圖中成型。 快速原型開發就是給軟件作草圖。就像建筑師的第一張草圖，軟件原型往往也會由草草幾筆一揮而就。在最初把想法付諸實現的時候，開銷和效率的問題根本就沒有納入考量。結果是，在這一階段得到的往往就是無法施工的設計圖，或是低效得不可救藥的軟件。但無論如何，草圖依然有它的價值，因為 1. 它們簡明的傳達了信息 2. 它們提供了試驗的機會 像后續章節中的程序一樣，這一章描述的程序還只是初步的設計。它僅用寥寥幾筆就勾勒出了多進程大略 的模樣。而且，盡管它可能因為不夠高效，不能使用在產品軟件中，但是它對于在多進程的其他方面作一些嘗試還是很有用的，比如用來進行調度算法方面的試驗。 第 22--24 章展示了其他使用續延的例子。它們都不夠高效而不能使用在產品級的軟件中。因為Lisp 和快速原型開發一同演化，Lisp 包含了很多專為原型開發打造的特性：低效但是方便的功能如屬性列表，關鍵字參數；推而廣之，列表也是這類特性之一。續延可以說屬于這一類特性。它們保存了程序通常所需要的更多的狀態。所以我們基于續延的Prolog 實現就是一個例子，通過這個實現我們能很好地理解這門語言，但是它的實現方式卻是低效的。 本書更多的關注使用 Lisp 可以建立的抽象而不是效率問題。重要的是要意識到，Lisp 既是一個適合寫產品軟件的語言也是一個適合寫原型的語言。如果 Lisp 有著低效的名聲，那大部分是因為程序員止步于原型。 用Lisp 寫出快速的程序很容易。不幸的是，用它寫出低效的程序更是容易。最初版本的 Lisp 程序可以像鉆石一樣：嬌小玲瓏，清澈透明，而又笨重昂貴。也許有很大的誘惑使人們就讓它保留原狀。 在其他的語言中，一旦你大功告成，程序能夠運行，那時程序的效率可能就已經可以接受了。如果你用指甲蓋大小的瓷磚來鋪地板，自然是不會浪費多少的。習慣用這種原則來開發軟件的人可能會發現，克服 "程序能工作就完工" 這樣的思維有些困難。"雖然用 Lisp 你輕而易舉就能把程序寫出來，" 他可能會想，"但哥們，這些程序跑得太慢了。" 事實上，兩種看法都有問題。你可以寫出快速的程序，但你得為此付出努力。 從這角度上說，使用 Lisp 就像生活在一個富裕而非貧窮的國度：似乎人們不得不通過工作來保持身材是種不幸，但這肯定比為了活下去而工作，自然只得消瘦下來要好。 在使用抽象能力較差的語言的時候，你想方設法實現的是功能。而在用 Lisp 的時候，你努力改進的則是程序的運行速度。幸運的是，提升速度更容易一些；大多數程序只在少數幾個關鍵的地方才會關心速度。