第 21 章 多進(jìn)程

第 21 章 多進(jìn)程

上一章展示了續(xù)延是如何使運行中的程序獲知自己的狀態(tài)，并且把它保存起來以便之后重新執(zhí)行的。這一章將討論一種計算模型，在這種模型中，計算機運行的不是單個程序，而是一組獨立的進(jìn)程。進(jìn)程的概念和程序狀態(tài)這一概念相當(dāng)接近。通過在前一章的宏的基礎(chǔ)上再寫一層宏，我們就可以把多進(jìn)程的機制融入到 Common Lisp 程序中。

21.1 進(jìn)程抽象

多進(jìn)程這種表現(xiàn)形式，可以很方便地表示并行處理多個任務(wù)的程序。傳統(tǒng)的處理器同時只能執(zhí)行一條指令。我們稱多進(jìn)程能同時處理多件事情，并不是說它通過某種方式克服了硬件的限制，它真正的含義是：它使得我們可以在一個新的抽象層面上進(jìn)行思考，在這個層面上我們不需要明確地指定計算機在任何給定的時間在做什么。就像虛擬內(nèi)存給我們制造了一個錯覺，似乎計算機的可用內(nèi)存比它的物理內(nèi)存還要大，同樣的道理，多進(jìn)程的概念使得我們可以假設(shè)計算機可以一次運行多個程序。

從傳統(tǒng)上說，對進(jìn)程的研究屬于操作系統(tǒng)領(lǐng)域的范疇。但進(jìn)程抽象帶來的進(jìn)步并不局限于操作系統(tǒng)。它們在其他實時的應(yīng)用程序和計算機仿真中一樣能大展身手。

有很多對于多進(jìn)程的研究，它們的目的都是為了避免出現(xiàn)某些特定類型的問題。死鎖是多進(jìn)程的一個經(jīng)典問題：兩個進(jìn)程同時停下等待另一個做某些事情，就像兩個人都拒絕在另一個人之前跨過門檻。另一個問題是查詢有可能碰到系統(tǒng)中數(shù)據(jù)不一致的狀態(tài) 例如，一個余額查詢正好在系統(tǒng)將資金從一個賬戶轉(zhuǎn)移到另一個賬戶時發(fā)生。這一章只討論進(jìn)程抽象本身；這里展示的代碼可以用來測試避免死鎖和不一致狀態(tài)的算法，但代碼本身沒有對這些問題提供任何保護(hù)。

這一章中的實現(xiàn)遵循了本書所有程序默默恪守的一條準(zhǔn)則：盡可能少的擾亂Lisp。在本質(zhì)上來說，程序應(yīng)該盡可能多的讓自己像是對語言的修改，而不是用語言寫就的一個獨立的應(yīng)用程序。使程序與Lisp 協(xié)調(diào)一致可以使得程序更為健壯，好比部件配合良好的機器。這樣做也能事半功倍；有時你可以讓Lisp 為你代勞數(shù)量驚人的工作。

這一章的目標(biāo)是構(gòu)建一個支持多進(jìn)程的的語言。我們的策略是通過添加一些操作符，將Lisp 變成這樣的語言。我們語言的基本構(gòu)成元素如下：

函數(shù)?由前一章的 =defun 或者 =lambda 宏定義。

進(jìn)程?由函數(shù)調(diào)用實例化?；顒舆M(jìn)程的數(shù)量和一個函數(shù)能夠?qū)嵗倪M(jìn)程數(shù)量都沒有限制。每個進(jìn)程有一個優(yōu)先級，初始值由創(chuàng)建時給出的參數(shù)指定。

等待表達(dá)式(Waitexpressions)?等待表達(dá)式接受一個變量，一個測試表達(dá)式和一段代碼體。如果進(jìn)程遇到等待表達(dá)式，進(jìn)程將在這一點被掛起，直到測試表達(dá)式返回真。一旦進(jìn)程重新開始執(zhí)行，代碼體會被求值，變量則被綁定到測試表達(dá)式的值。測試表達(dá)式通常不應(yīng)該有副作用，因為它被求值的時間和頻率沒有任何保證。

調(diào)度?通過優(yōu)先級來完成。在所有能夠重新開始執(zhí)行的進(jìn)程中，系統(tǒng)會運行優(yōu)先級最高的進(jìn)程。

默認(rèn)進(jìn)程?在其他進(jìn)程都不能執(zhí)行時運行。它是一個 read-eval-print 循環(huán)。

創(chuàng)建和刪除?絕大多數(shù)對象的操作可以即時進(jìn)行。正在運行中的進(jìn)程可以定義新的函數(shù)，實例化或者殺死進(jìn)程。

續(xù)延使得保存 Lisp 程序的狀態(tài)成為可能。能夠同時保存多個狀態(tài)離實現(xiàn)多進(jìn)程也不太遠(yuǎn)了。有了前一章定義的宏做基礎(chǔ)，我們只要不到 60 行的代碼就可以實現(xiàn)多進(jìn)程。

21.2 實現(xiàn)

[示例代碼 21.1] 進(jìn)程結(jié)構(gòu)及實例化

(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 包含了所有用來支持多進(jìn)程的代碼。[示例代碼 21.1] 包含了基本數(shù)據(jù)結(jié)構(gòu)、默認(rèn)進(jìn)程、初始化、進(jìn)程實例化的代碼。進(jìn)程，或者說procs，具有如下結(jié)構(gòu)：

pri : 進(jìn)程的優(yōu)先級，它應(yīng)該是一個正數(shù)。

state : 是一個續(xù)延，它用來表示一個掛起進(jìn)程的狀態(tài)。我們可以 funcall 一個進(jìn)程的 state 來重新啟動它。

wait : 通常是一個函數(shù)，如果要讓進(jìn)程重新執(zhí)行，它必須返回真，但剛創(chuàng)建的進(jìn)程的 wait 為 nil 。wait 為空的進(jìn)程總是可以被重新執(zhí)行。

程序使用三個全局變量：procs ，當(dāng)前被掛起的進(jìn)程列表；proc ，正在運行的進(jìn)程；還有 default-proc ，默認(rèn)進(jìn)程。

默認(rèn)進(jìn)程僅當(dāng)沒有其他進(jìn)程可以運行時才會運行。它模擬 Lisp 的 toplevel 循環(huán)。在這個循環(huán)中，用戶可以終止程序，或者輸入讓掛起進(jìn)程恢復(fù)執(zhí)行的表達(dá)式。請注意，默認(rèn)進(jìn)程顯式地調(diào)用了 eval。這是少數(shù)幾個合理使用 eval 的情形之一。一般來說，我們不贊成在運行時調(diào)用 eval ，這有兩個原因：

1. 效率低下：eval 直接處理原始列表，要么當(dāng)場進(jìn)行編譯，要么在解釋器中進(jìn)行求值。不管哪種方式都比先編譯再調(diào)用來得慢。

2. 功能不夠強大，因為表達(dá)式不在詞法上下文中進(jìn)行求值。舉個例子，這就意味著你不能引用在被求值表達(dá)式之外可見的普通變量。

通常來說，顯式調(diào)用eval 就像在機場禮品店買東西一樣。已經(jīng)是最后關(guān)頭，你只得高價購買選擇有限的劣質(zhì)商品。

像本例這樣兩條理由都不適用的情況是很少見的。我們沒法提前將表達(dá)式編譯好。直到讀取它們的時候才知道表達(dá)式是什么，所以沒法事先知道。同樣的，表達(dá)式無法引用它周遭的詞法環(huán)境，因為在toplevel 輸入的表達(dá)式處于空的詞法環(huán)境中。事實上，這個函數(shù)的定義直接反映了它的英語描述：它讀取并求值用戶的輸入。

宏 fork 使用一個函數(shù)調(diào)用來實例化進(jìn)程。函數(shù)像平時一樣由 =defun 定義：

(=defun foo (x)
  (format t "Foo was called with ~A.~%" x)
  (=values (1+ x)))

現(xiàn)在當(dāng)我們以一個函數(shù)調(diào)用和優(yōu)先級數(shù)值作為參數(shù)調(diào)用 fork 時：

(fork (foo 2) 25)

一個新進(jìn)程被加入到了 procs 里面。新進(jìn)程的優(yōu)先級為 25，因為它還沒有執(zhí)行，所以 proc-wait 為 nil ，而 proc-state 包含了以 2 為參數(shù)的對 foo 的調(diào)用。

宏 program 使我們可以創(chuàng)建一組進(jìn)程并一起執(zhí)行它們。下面的定義：

(program two-foos (a b)
  (fork (foo a) 99)
  (fork (foo b) 99))

宏展開成了兩個 fork 表達(dá)式，被夾在負(fù)責(zé)清除掛起進(jìn)程的代碼，以及不斷選擇進(jìn)程來運行的代碼中間。在這個循環(huán)外面，program 宏設(shè)置了一個 tag，把控制流拋(throw) 到這個 tag 的話，就會終止這個程序(program)。因為這個 tag 是個生成符號，所以它不會與用戶設(shè)置的 tag 沖突。定義成 program 的一組進(jìn)程不返回任何值，而且它們只應(yīng)該在 toplevel 被調(diào)用。

進(jìn)程實例化之后，進(jìn)程調(diào)度代碼開始執(zhí)行。它的代碼見 [示例代碼 21.2]。函數(shù) pick-process 在可以繼續(xù)執(zhí)行的進(jìn)程中，選出優(yōu)先級最高的一個，然后運行它。把這個進(jìn)程找出來是 most-urgent-process 的工作。如果一個掛起的進(jìn)程沒有 wait 函數(shù)或者它的 wait 函數(shù)返回真，那么它就被允許運行。在所有被允許運行的進(jìn)程中，具有最高優(yōu)先級的被選中。勝出的進(jìn)程和它的 wait 函數(shù)(如果有的話) 返回的值被返回給 pick-process 。獲勝進(jìn)程總是存在，因為默認(rèn)進(jìn)程總是想要執(zhí)行。

[示例代碼 21.2] 中其余的代碼定義了用于在進(jìn)程間切換控制權(quán)的操作符。標(biāo)準(zhǔn)的等待表達(dá)式是wait ，就像[示例代碼 21.3] 中函數(shù) pedestrian 使用的那樣。在這個例子中，進(jìn)程一直等到列表 open-doors 中有東西為止，然后打印一條消息：

> (ped)
>> (push 'door2 *open-doors*)
Entering DOOR2
>> (halt)
NIL

一個 wait 在實質(zhì)上來說與 =bind (第 20.2 節(jié)) 相似，而且有著一樣的限制，那就是它必須在最后被求值。任何我們希望在wait 之后執(zhí)行的東西必須被放在它的代碼體中。因此如果我們想要讓一個進(jìn)程等待多次，那等待表達(dá)式必須被嵌套。通過聲明互相針對的事實，進(jìn)程可以相互配合以達(dá)到某個目標(biāo)，就像在 [示例代碼 21.4] 中一樣。

【】譯者注：即 (eval (read)) 【】譯者注：catch 操作符的用法可見CLHS 中的Special Operator CATCH 一節(jié)。

[示例代碼 21.2] 進(jìn)程調(diào)度

(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] 有一個等待的進(jìn)程

(defvar *open-doors* nil)

(=defun pedestrian ()
  (wait d (car *open-doors*)
    (format t "Entering ~A~%" d)))

(program ped ()
  (fork (pedestrian) 1))

如果被給予相同的 door ，從 visitor 和 host 實例化的進(jìn)程會通過黑板上的消息互相交換控制權(quán)：

> (ballet)

[示例代碼 21.4]： 利用黑板進(jìn)行同步

(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.
>>

還有另外一類更簡單的等待表達(dá)式：yield ，它的唯一目的是讓其他更高優(yōu)先級的進(jìn)程有機會運行。

setpri 重置當(dāng)前進(jìn)程的優(yōu)先級，一個進(jìn)程可能在執(zhí)行 setpri 表達(dá)式后想要讓出控制權(quán)。就像 wait 一樣，在 yield 之后執(zhí)行的代碼都必須被放在它的代碼體中。

[示例代碼 21.5] 中的程序說明了這兩個操作符如何相互工作。開始時，野蠻人有兩個目的：占領(lǐng)羅馬和掠奪它。占領(lǐng)城市有著(稍微) 高一些的優(yōu)先級，因此會先執(zhí)行。然而，在城市淪陷之后，capture 進(jìn)程的優(yōu)先級減小到 1 。之后會有一次投票，而 plunder ，作為最高優(yōu)先級的進(jìn)程開始運行。

> (barbarians)
Liberating ROME.
Nationalizing ROME.
Refinancing ROME.
Rebuilding ROME.
>>

只有在蠻族掠奪了羅馬的宮殿，并勒索了貴族之后，capture 進(jìn)程才會恢復(fù)執(zhí)行，此時他們開始為其領(lǐng)地建筑防御工事。

等待表達(dá)式的背后是一個更通用的 arbitrator。這個函數(shù)保存當(dāng)前進(jìn)程，然后調(diào)用 pick-process 來再次執(zhí)行某個進(jìn)程(有可能與當(dāng)前進(jìn)程為同一個)。它有兩個參數(shù)：一個測試函數(shù)和一個續(xù)延。前者會被存儲為掛起進(jìn)程的 proc-wait ，在以后被調(diào)用來檢查它是否可以被重新執(zhí)行。

宏 wait 和 yield 通過簡單的把它們的代碼體包在 --表達(dá)式中來建立這個續(xù)延函數(shù)。例如：

[示例代碼 21.5] 改變進(jìn)程優(yōu)先級的效果

(=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] 列出的限制，構(gòu)造一個 wait 代碼體的閉包就可以保存當(dāng)前的整個續(xù)延。隨著它的 =values 被展開，第二個參數(shù)變成：

#'(lambda (d) (funcall *cont* d))

由于這個閉包中有一個指向 cont 的引用，被這個等待函數(shù)掛起的進(jìn)程將會擁有一個句柄(handle)，通過它，這個進(jìn)程就能回到它當(dāng)初被掛起的那一刻。

halt 操作符通過將控制權(quán)拋回program 展開式建立的標(biāo)簽終止整個進(jìn)程組。它接受一個可選參數(shù)，該參數(shù)的值會被作為這個進(jìn)程組的值返回。因為默認(rèn)進(jìn)程始終想要執(zhí)行，所以終止整個程序的唯一的方法是顯式的調(diào)用halt 。halt 后面是什么代碼并沒有關(guān)系，因為這些代碼不會被求值。

單個進(jìn)程可以通過調(diào)用 kill 來殺死。如果沒有參數(shù)，這個操作符殺死當(dāng)前進(jìn)程。這種情況下，kill 就像是一個不保存當(dāng)前進(jìn)程的等待表達(dá)式。如果 kill 給定了參數(shù)，它們將成為進(jìn)程列表上的 delete 操作的參數(shù)。在現(xiàn)在的代碼中，kill 表達(dá)式?jīng)]有什么好說的，因為進(jìn)程沒有許多的屬性來被引用。然而，更復(fù)雜的系統(tǒng)會為它的進(jìn)程附加更多的信息 時間戳、擁有者等等。默認(rèn)進(jìn)程不能被殺死，因為它并沒有被保存在procs?中。

21.3 不那么快速的原型

通過續(xù)延模擬的進(jìn)程，其性能遠(yuǎn)不及真實操作系統(tǒng)的進(jìn)程。那么，這一章中的程序又有什么用處呢？

這些程序的用處類似于草圖。不管在探索式編程還是快速原型開發(fā)中，這些程序其自身并不是最終目的，更多的是作為實現(xiàn)人們想法的手段。在許多其他領(lǐng)域，為這個目的服務(wù)的東西被稱為草圖。在理論上，建譯者注：可以認(rèn)為宏program 建立的由一組同時執(zhí)行的進(jìn)程組成的程序，但為與 "程序" 相區(qū)別，這里把 program 翻譯成 "進(jìn)程組"。

筑師可以在他的腦海里構(gòu)思出整棟大樓。但多數(shù)建筑師似乎在手里握著筆的時候能想得更周詳一些：一棟大樓的設(shè)計通常在一系列草圖中成型。

快速原型開發(fā)就是給軟件作草圖。就像建筑師的第一張草圖，軟件原型往往也會由草草幾筆一揮而就。在最初把想法付諸實現(xiàn)的時候，開銷和效率的問題根本就沒有納入考量。結(jié)果是，在這一階段得到的往往就是無法施工的設(shè)計圖，或是低效得不可救藥的軟件。但無論如何，草圖依然有它的價值，因為

1. 它們簡明的傳達(dá)了信息

2. 它們提供了試驗的機會

像后續(xù)章節(jié)中的程序一樣，這一章描述的程序還只是初步的設(shè)計。它僅用寥寥幾筆就勾勒出了多進(jìn)程大略

的模樣。而且，盡管它可能因為不夠高效，不能使用在產(chǎn)品軟件中，但是它對于在多進(jìn)程的其他方面作一些嘗試還是很有用的，比如用來進(jìn)行調(diào)度算法方面的試驗。

第 22--24 章展示了其他使用續(xù)延的例子。它們都不夠高效而不能使用在產(chǎn)品級的軟件中。因為Lisp 和快速原型開發(fā)一同演化，Lisp 包含了很多專為原型開發(fā)打造的特性：低效但是方便的功能如屬性列表，關(guān)鍵字參數(shù)；推而廣之，列表也是這類特性之一。續(xù)延可以說屬于這一類特性。它們保存了程序通常所需要的更多的狀態(tài)。所以我們基于續(xù)延的Prolog 實現(xiàn)就是一個例子，通過這個實現(xiàn)我們能很好地理解這門語言，但是它的實現(xiàn)方式卻是低效的。

本書更多的關(guān)注使用 Lisp 可以建立的抽象而不是效率問題。重要的是要意識到，Lisp 既是一個適合寫產(chǎn)品軟件的語言也是一個適合寫原型的語言。如果 Lisp 有著低效的名聲，那大部分是因為程序員止步于原型。

用Lisp 寫出快速的程序很容易。不幸的是，用它寫出低效的程序更是容易。最初版本的 Lisp 程序可以像鉆石一樣：嬌小玲瓏，清澈透明，而又笨重昂貴。也許有很大的誘惑使人們就讓它保留原狀。

在其他的語言中，一旦你大功告成，程序能夠運行，那時程序的效率可能就已經(jīng)可以接受了。如果你用指甲蓋大小的瓷磚來鋪地板，自然是不會浪費多少的。習(xí)慣用這種原則來開發(fā)軟件的人可能會發(fā)現(xiàn)，克服 "程序能工作就完工" 這樣的思維有些困難。"雖然用 Lisp 你輕而易舉就能把程序?qū)懗鰜恚? 他可能會想，"但哥們，這些程序跑得太慢了。" 事實上，兩種看法都有問題。你可以寫出快速的程序，但你得為此付出努力。

從這角度上說，使用 Lisp 就像生活在一個富裕而非貧窮的國度：似乎人們不得不通過工作來保持身材是種不幸，但這肯定比為了活下去而工作，自然只得消瘦下來要好。

在使用抽象能力較差的語言的時候，你想方設(shè)法實現(xiàn)的是功能。而在用 Lisp 的時候，你努力改進(jìn)的則是程序的運行速度。幸運的是，提升速度更容易一些；大多數(shù)程序只在少數(shù)幾個關(guān)鍵的地方才會關(guān)心速度。