DDS并行模型及其形式化.pdf

1、DDS模型是實(shí)時(shí)系統(tǒng)早期研究中取得的重要成果之一，其具有很強(qiáng)的代表性，很多現(xiàn)實(shí)生活中存在的諸如網(wǎng)絡(luò)擁塞、生產(chǎn)流程調(diào)度、交通運(yùn)輸?shù)葐?wèn)題的解決都可以借助該模型。由于DDS模型未考慮空間限制這一約束條件，而在現(xiàn)實(shí)生活中，空間卻是一個(gè)很關(guān)鍵的因素，這就限制了DDS模型在現(xiàn)實(shí)工作中的應(yīng)用?？紤]了空間因素后的DDS并行模型能較好地解決這一問(wèn)題。如果要設(shè)計(jì)一個(gè)大型自動(dòng)化調(diào)度系統(tǒng)，其軟件部分首先要解決的，即是如何將問(wèn)題形式化。傳統(tǒng)的時(shí)段演算可以很好地對(duì)

2、DDS模型進(jìn)行形式化，但卻不能描述加入了空間限制條件的DDS并行模型。注意到分離邏輯能很好地體現(xiàn)空間分離這一概念，本文重點(diǎn)研究了如何將分離邏輯與時(shí)段演算相結(jié)合，以便更好地對(duì)DDS并行模型進(jìn)行形式化這一課題。 文章的主要內(nèi)容安排如下： 第一章：前言，介紹與本文相關(guān)的研究歷史和現(xiàn)狀； 第二章：DDS并行模型，完成了數(shù)學(xué)模型的構(gòu)建。通過(guò)在原始的DDS模型中加入空間限制，允許有多個(gè)處理器同時(shí)運(yùn)行，得到DDS并行模型。隨后

3、在該模型下給出了極大空間相容組等概念，并且提出了主調(diào)度算法和全局調(diào)度算法，得出了本文的兩個(gè)重要結(jié)論： 定理2.2任給一個(gè)極大空間相容組Q,存在Q的主調(diào)度算法。 定理2.3設(shè)為任務(wù)集合的一個(gè)劃分，對(duì)每一極大空間相容組，以記為它的主導(dǎo)任務(wù)，則全局調(diào)度算法可行的充要條件是主導(dǎo)任務(wù)組成的任務(wù)集合滿足第三章：時(shí)段演算(DC)簡(jiǎn)介，主要介紹時(shí)段演算的字母表、形成規(guī)則、推理規(guī)則等基本邏輯設(shè)置； 第四章：分離邏輯語(yǔ)言及其應(yīng)用，系