SLDDS問題的離散化與形式化.pdf

1、程序正確性驗(yàn)證不僅是計(jì)算機(jī)科學(xué)界一直關(guān)注的一個重要問題，也是推動計(jì)算機(jī)科學(xué)發(fā)展的主要動力之一。分離邏輯是此問題研究下出現(xiàn)的新研究領(lǐng)域，它是一個用來對關(guān)于共享可變數(shù)據(jù)結(jié)構(gòu)的程序進(jìn)行推理的邏輯系統(tǒng)，其主要的特征是支持局部推理。 時段演算是一個用于嵌入式實(shí)時軟件系統(tǒng)設(shè)計(jì)的演算系統(tǒng)，即在設(shè)計(jì)嵌入式實(shí)時軟件系統(tǒng)時，用該形式語言來描述軟件需求和特征，并且通過推理驗(yàn)證來保證最終的軟件產(chǎn)品是否滿足這些需求和具備這些特征。 當(dāng)前對實(shí)時任務(wù)調(diào)

2、度理論的研究很少考慮到空間的約束，往往只考慮實(shí)時限制，但在許多實(shí)際問題中，（比如鐵路交叉口控制、網(wǎng)絡(luò)服務(wù)的擁塞問題、城市交通的指揮問題、軟件系統(tǒng)資源共享問題等等）中，空間是一個不可忽視的因素。時段演算是規(guī)約實(shí)時系統(tǒng)的一個強(qiáng)有力工具，然而它幾乎沒有考慮空間因素；分離邏輯較好地解決了空間共享問題，但它不能夠較好地解決并發(fā)程序的同步問題。由此，在時段演算中引入空間概念顯得極為必要，我們采用的方法是在時段演算中引入空間變量，這為我們規(guī)約實(shí)時問題

3、中的空間共享與空間分離提供了方便。 本文從一些現(xiàn)實(shí)問題的背景中抽象出SLDDS模型，并研究此模型里的調(diào)度問題，最后考慮這個模型的形式化問題。 本文的主要內(nèi)容安排如下： 序言，介紹分離邏輯，時段演算的研究現(xiàn)狀和本文的出發(fā)點(diǎn)。 第1章介紹基礎(chǔ)分離邏輯。 第2章介紹時段演算。 第3章先將DDS模型擴(kuò)充為更一般的SLDDS問題，重新審視Liu-Layland定理，給出此類實(shí)時問題離散化的理論基礎(chǔ)，

4、然后研究SLDDS模型里的調(diào)度問題。 第4章先介紹我們所要用到的語言，然后初步給出該模型的形式化。 本文主要理論結(jié)論如下： 定理1 給定一個SLDDS問題Q，Q是可調(diào)度的當(dāng)僅當(dāng)存在對Q的一個劃分： P1=⊕K1j=1 Pj1,P2=⊕k2j=1Pj2,…,Pm=⊕kmj=1pjm使得所有的長條{di×ai│1≤i≤n}可以滿足如下要求放入長方塊 D×1中： (ⅰ)所有長條都是垂直而不重疊地；

5、(ⅱ)來自的任何兩個小長條一個不能在另一個的上方，即對來自某個di×Wi的所有小長條，通過長方塊底邊上任何點(diǎn)的垂線至多穿過其中一個的中間。 定理2 SLDDS問題Q有解的充要條件是存在[0,1] 上的一個階梯函數(shù)f(t)使: (ⅰ)(∨)t，t∈[0,1]，滿足f(t)≤│D│ (ⅱ)(∨)t，t∈[0,1],f(t)=∑ki=1δi,δi∈{d1,d2…dm} k∈N,這里f(t)=∑ki=1δi僅僅是一個符號表達(dá)