并發(fā)實時系統(tǒng)的模型及其形式化.pdf

1、廣西師范大學(xué)碩士學(xué)位論文并發(fā)實時系統(tǒng)的模型及其形式化姓名：陳艷申請學(xué)位級別：碩士專業(yè)：應(yīng)用數(shù)學(xué)指導(dǎo)教師：王駒20080401II得到并發(fā)模型。建立簡單的并發(fā)模型LCM：令1D=k是一個固定的正整數(shù)，且2k≥。對每個iP，1jjiitt????是iP在第j個請求周期內(nèi)的運行時段，jH∈。假設(shè)對每個iP，在時間段1jjiitt????內(nèi)從不間歇。()ivt是如下定義的動態(tài)函數(shù)：()11110jijjjiiiittCttkvtjHtttik?

2、???????????????????==??∈如果如果使得否則。iP在時段tt????，內(nèi)的時空占用量定義為()tvtit∫，我們的目標(biāo)是找到一個有效的算法使時空利用率rat盡可能大?？紤]下面一個算法（貪心算法）：①當(dāng)0t=時，我們在開始時刻運行k個任務(wù)。②每個進程一旦運行就直至完成才結(jié)束。③當(dāng)且僅當(dāng)1k的空間被釋放，我們才讓另一個任務(wù)切入進來并開始運行。我們采用MAPLE環(huán)境編程。根據(jù)程序輸出的結(jié)果，猜測LCM在貪心算法的調(diào)度下，時

3、空利用率的上界是212kk?。由此提出猜想：定理定理4.1對于并發(fā)模型LCM，212kk?是任意一個有效的調(diào)度算法()t∑的時空利用率的上界。鑒于貪心算法將導(dǎo)致復(fù)雜的并發(fā)進程控制，我們提出了循環(huán)算法：①當(dāng)0t=僅讓一個任務(wù)1P運行。②當(dāng)21ntk=?時，021nnk?是正整數(shù)，，開始一個新的任務(wù)1nP。③當(dāng)1t=時，任務(wù)1P的進程結(jié)束，且正好有1k的空間空余出來，同一時刻任務(wù)1P的進程再次被切入，將所有空間填滿。④當(dāng)121ntk=?時，