并發(fā)系統(tǒng)的動作細化理論.pdf

1、自項向下逐步細化的層次化設(shè)計方法，是人們廣泛接受的設(shè)計計算機硬件系統(tǒng)和軟件系統(tǒng)的最主要方法之一，動作細化是系統(tǒng)層次化刻畫方法的核心操作。具體應(yīng)用到軟件的模塊設(shè)計中，有時需要比較系統(tǒng)在不同抽象層次上的描述，檢驗它們能否實現(xiàn)相應(yīng)的功能，伴隨系統(tǒng)描述抽象層次的改變，相應(yīng)的原子級動作集也在改變。當系統(tǒng)不同抽象層次的動作集確定以后，另一種垂直模塊化的方法就應(yīng)運而生了，它不同于前面水平模塊化的方法，垂直模塊化的方法是先將復(fù)雜的系統(tǒng)描述成簡單的、抽象

2、的形式，然后一步一步細化成實際的、復(fù)雜的執(zhí)行過程；這種描述，連同建立在描述之上的分析，可以一層一層的進行，這樣每次只是專注于從上一個層次到這一個層次的相關(guān)細節(jié)。這個著名的方法就是通常被稱為分層描述的方法。這種方法在順序系統(tǒng)中的運用很成功，產(chǎn)生了“自上而下”的系統(tǒng)設(shè)計方法，“自上而下”的設(shè)計方法將宏觀的功能模塊一層一層的細化，直到最底級的執(zhí)行代碼，我們要探討的動作細化，就是運用數(shù)學(xué)的方法來描述這一問題，為各種動作細化建立模型，探討動作細化

3、的操作語義和指稱語義。 本文系統(tǒng)闡述了動作細化理論的各個分支，具體包括：原子動作細化與非原子動作細化。原子動作細化是指：在動作細化以前，動作在相應(yīng)的描述層次上是原子級的，原子動作經(jīng)過細化變成一個進程后，原來動作執(zhí)行的原子性繼續(xù)保留。非原子細化，是一種更加自由的、松散的動作細化，這種觀點的依據(jù)是動作的原子性只對于特定的描述層次，對于其他抽象描述層次上，動作間執(zhí)行的關(guān)系根據(jù)特定的抽象層次，會發(fā)生相應(yīng)的改變，即在某一個特定的描述層次上

4、，所有的動作都是原子級的，細化到更具體的層次上，原來原子級的動作將可能細化成其他的非原子級的執(zhí)行關(guān)系，這種動作細化后優(yōu)化了進程的執(zhí)行，但是對原來進程間的執(zhí)行關(guān)系會造成某種程度上會破壞。 不論是原子動作細化，還是非原子動作細化，在本質(zhì)上都有兩種解釋方法：語法上的和語義上的。解釋表現(xiàn)在語法上，主要是動作細化對于過程調(diào)用的拷貝式處理，比如順序程序設(shè)計中嵌入主程序的動作調(diào)用。在語義的解釋中，用來解釋進程語句的的替換操作都定義在一個語義域

5、中。t[α→μ]的語義可以用這種操作來定義。例如，有時我們將語義的域構(gòu)建在事件結(jié)構(gòu)(Event Structure)上，而事件結(jié)構(gòu)ε=[u]代表u的語義，可以被事件結(jié)構(gòu)[t]中每個標簽為α的事件d所替換。在事件結(jié)構(gòu)域中動作細化的語義是保持的：包括進程間的沖突關(guān)系、順序執(zhí)行關(guān)系等等。 當我們把動作細化當成對于語言的一個操作算子時，很自然的出現(xiàn)一個關(guān)鍵性問題：如何找到這個操作算子基于全等的等價關(guān)系。經(jīng)典的進程代數(shù)提供了互模擬等價關(guān)系

6、，這種等價關(guān)系就是基于交織語義的，交織語義在解釋非并發(fā)進程間的等價關(guān)系是很有說服力的，但是復(fù)雜系統(tǒng)中包含大量的并發(fā)進程，交織語義對于并發(fā)進程間的等價關(guān)系的描述是不完全的，有些片面。本文對于等價關(guān)系的探討，主要集中在真并發(fā)語義上。 另一種以更加弱化的方法來處理動作細化問題的方法：就是不要將操作細化作為一個算子來對待，而是將動作細化看作是一種執(zhí)行關(guān)系。在很長的一段時間內(nèi)，人們將動作細化理論建立在這樣一種認識上：就是當進程，相對于進程

7、S更加便于直接執(zhí)行，特別是針對選擇算子時有更加明確的語義的時候，我們就將進程，當作是另一個進程S的一個執(zhí)行。 在探討了經(jīng)典動作細化的各種理論分支以后，很多研究人員意識到經(jīng)典的動作細化缺乏數(shù)量上的約束，鑒于此，本文對動作細化理論中的原子動作細化理論進行了實時、隨機和概率三個方面的擴展。對動作細化理論擴充的數(shù)量約束，每一種都有特定的現(xiàn)實背景和應(yīng)用。實時的模型中，對進程執(zhí)行的時間控制添加了超時算子，即一個進程如果在允許的時間內(nèi)沒有完成

8、相應(yīng)的動作，那么就會激活一個超時操作，原動作被禁止執(zhí)行，系統(tǒng)開始執(zhí)行一個新的動作(進程)。對于隨機模型，我們將馬爾可夫鏈引入進程代數(shù)中，這個模型的引入對于評價系統(tǒng)的性能帶來和很大的方便，這種模型將概率和時間兩個因素同時引入了動作細化理論，動作的執(zhí)行有了自己的概率和執(zhí)行時間，更加貼近于現(xiàn)實中的情況。概率事件在現(xiàn)實的生產(chǎn)生活中普遍存在和發(fā)生，因此，我們將概率模型也引入了動作細化理論。 針對上面提到的每一種數(shù)量約束，我們首先給出相應(yīng)的