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

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

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

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