并發(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)層次化刻畫方法的核心操作。具體應(yīng)用到軟件的模塊設(shè)計(jì)中，有時(shí)需要比較系統(tǒng)在不同抽象層次上的描述，檢驗(yàn)它們能否實(shí)現(xiàn)相應(yīng)的功能，伴隨系統(tǒng)描述抽象層次的改變，相應(yīng)的原子級動(dòng)作集也在改變。當(dāng)系統(tǒng)不同抽象層次的動(dòng)作集確定以后，另一種垂直模塊化的方法就應(yīng)運(yùn)而生了，它不同于前面水平模塊化的方法，垂直模塊化的方法是先將復(fù)雜的系統(tǒng)描述成簡單的、抽象

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

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

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

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

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

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

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