多線程的內(nèi)存調(diào)度.pdf

1、本文主要考慮以下這個(gè)問(wèn)題：給定一臺(tái)服務(wù)器，如何調(diào)度同時(shí)遞交到該服務(wù)器的多個(gè)請(qǐng)求。具體地，每個(gè)用戶遞交的請(qǐng)求包含一系列的任務(wù)。在同一個(gè)請(qǐng)求序列中的不同任務(wù)需要按照到達(dá)的先后順序來(lái)處理。每一個(gè)任務(wù)既有可能在同一個(gè)用戶的請(qǐng)求序列中反復(fù)出現(xiàn)，也有可能在其他用戶的請(qǐng)求序列中反復(fù)出現(xiàn)。此外，該服務(wù)器帶有一個(gè)容量有限的內(nèi)存，它可以用來(lái)存儲(chǔ)任務(wù)。不同的任務(wù)需要的處理時(shí)間可能不同，其占用的空間也可能不同。當(dāng)服務(wù)某個(gè)任務(wù)時(shí)，如果該任務(wù)已經(jīng)在內(nèi)存中，則不產(chǎn)生

2、任何費(fèi)用；否則，產(chǎn)生相應(yīng)的處理時(shí)間，并且這個(gè)處理過(guò)的任務(wù)可以存放到內(nèi)存中(存放任務(wù)不需要時(shí)間)。因?yàn)檫@個(gè)內(nèi)存空間有限，這個(gè)存放過(guò)程可能導(dǎo)致內(nèi)存中其它的任務(wù)被刪除(刪除任務(wù)也不需要時(shí)間)。
　　 本文的目的是設(shè)計(jì)一個(gè)調(diào)度方案，來(lái)優(yōu)化某個(gè)目標(biāo)函數(shù)。首先，我們考慮極小化全部的請(qǐng)求的完工時(shí)間，這個(gè)問(wèn)題是經(jīng)典的只有一個(gè)用戶的內(nèi)存調(diào)度問(wèn)題的一個(gè)推廣。此外，我們還考慮了極小化全部請(qǐng)求鏈的平均完工時(shí)間。對(duì)于這兩個(gè)問(wèn)題，我們兼顧了兩個(gè)模型：強(qiáng)制模

3、型，選擇模型。對(duì)于前者，當(dāng)完成一個(gè)任務(wù)后，如果它不在內(nèi)存中，必須把它放進(jìn)內(nèi)存中；對(duì)于后者，則沒(méi)有這個(gè)要求。我們證明了所有的問(wèn)題事實(shí)上都是NP難。對(duì)于這些模型，我們?cè)O(shè)計(jì)了動(dòng)態(tài)規(guī)劃。此外，我們提出幾個(gè)近似算法，并分析它們的近似比。最后，我們?cè)O(shè)計(jì)了一些啟發(fā)式算法，并模擬運(yùn)行。
　　 事實(shí)上，從資源利用的角度上看，內(nèi)存也是一種資源。
　　 這樣，除了研究?jī)?nèi)存的使用，我們也研究帶有一個(gè)加速資源的兩臺(tái)平行機(jī)調(diào)度問(wèn)題。具體地，每個(gè)工件