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

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

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

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