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

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

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

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

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

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

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

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

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