[發(fā)明專利]調(diào)度無(wú)用單元回收的方法

無(wú)效

• 申請(qǐng)?zhí)枺?/td>: 00800918.X
• 申請(qǐng)日: 2000-03-09
• 公開（公告）號(hào): CN1306644A
• 公開（公告）日: 2001-08-01
• 發(fā)明（設(shè)計(jì)）人: R·J·霍爾德斯沃斯
• 申請(qǐng)（專利權(quán)）人: 皇家菲利浦電子有限公司
• 主分類號(hào): G06F12/02
• 分類號(hào): G06F12/02;G06F9/45
• 代理公司: 中國(guó)專利代理(香港)有限公司
• 代理人: 欒本生,王忠忠

本發(fā)明涉及調(diào)度無(wú)用單元回收指令以便供其它進(jìn)程的指令執(zhí)行的方法和設(shè)備，具體地說(shuō)，本發(fā)明涉及對(duì)用于有指令級(jí)并行性的處理器的無(wú)用單元回收指令進(jìn)行調(diào)度。

當(dāng)今一代可用的計(jì)算機(jī)處理器體系結(jié)構(gòu)具有指令級(jí)并行性的能力，也就是說(shuō)，可在單個(gè)的時(shí)鐘周期內(nèi)執(zhí)行多個(gè)并發(fā)指令。用于這種處理器的指令發(fā)出寄存器一般被分成多個(gè)槽。在一個(gè)單個(gè)時(shí)鐘周期內(nèi)，處理器可以處理各槽中的一條指令。能提供這種特征的處理器結(jié)構(gòu)的實(shí)例是超標(biāo)量體系結(jié)構(gòu)和超長(zhǎng)指令字(VLIW)體系結(jié)構(gòu)。

就能執(zhí)行多條并發(fā)指令的處理器而言，每條指令及其效果必須與要在同一時(shí)鐘周期內(nèi)執(zhí)行的其它指令無(wú)關(guān)。例如，使數(shù)值變量的值加倍的指令在同一個(gè)時(shí)鐘周期內(nèi)不能被處理成將同一變量的值拷貝至另一個(gè)變量的指令。業(yè)已按多種不同的方式解決了判斷哪些指令是彼此獨(dú)立的從而能同時(shí)加以處理的需求。在該超標(biāo)量體系結(jié)構(gòu)中，用專用的硬件來(lái)判斷到達(dá)指令發(fā)出寄存器的獨(dú)立指令。在VLIW體系結(jié)構(gòu)中，用程序編譯器來(lái)生成超長(zhǎng)指令字，該超長(zhǎng)指令字由多個(gè)連在一起的獨(dú)立指示構(gòu)成，在每個(gè)時(shí)鐘周期中，都由處理器執(zhí)行一個(gè)單個(gè)的VLIW。

但是，兩種方法有同樣的局限性。很少的在VLIW、超標(biāo)量或類似體系結(jié)構(gòu)處理器上運(yùn)行的程序有足夠數(shù)量的獨(dú)立指令以便在所有的時(shí)侯都占據(jù)處理器的所有的槽。一般地說(shuō)，只有其中需要對(duì)大量獨(dú)立元素進(jìn)行大量處理的諸如聲音或圖像處理之類的多媒體應(yīng)用程序才幾乎能占據(jù)處理器的所有的槽。盡管有上述處理器的計(jì)算機(jī)的用戶不會(huì)注意到源于處理器的未用槽的負(fù)面效果，但是，希望能最充分地使用上述處理器及其并發(fā)處理能力。

在Sun?Microsystem的Java及諸如Modular-3和Cedar之類的某些其它語(yǔ)言和編程環(huán)境中，以與程序進(jìn)程相并行的方式運(yùn)行無(wú)用單元回收進(jìn)程。

無(wú)用單元回收是自動(dòng)回收最后被程序使用以后的系統(tǒng)存儲(chǔ)器空間。John?Wiley?&?Son于1996年出版的Jones等人著的《無(wú)用單元回收——用于自動(dòng)動(dòng)態(tài)存儲(chǔ)器管理的算法》(ISBN0-471-94148-4)一書中1至18頁(yè)以及載于1992年國(guó)際存儲(chǔ)器管理工作組會(huì)議錄(St.Malo,France,1992年8月)的P.R.Wilson的“單處理器無(wú)用單元回收技術(shù)”一文均說(shuō)明了無(wú)用單元回收技術(shù)的多個(gè)實(shí)例。盡管許多計(jì)算機(jī)程序的存儲(chǔ)要求是簡(jiǎn)單的并且是可預(yù)測(cè)的，但是，在存儲(chǔ)器分配和恢復(fù)由程序設(shè)計(jì)人員或編譯器來(lái)處理的情況下，有趨于帶更為復(fù)雜的執(zhí)行模式的功能語(yǔ)言的傾向，因此，特定數(shù)據(jù)結(jié)構(gòu)的壽命在運(yùn)行時(shí)之前不再是確定的，因此，在程序運(yùn)行時(shí)自動(dòng)回收存儲(chǔ)器是很關(guān)鍵的。

如上述Wilson的參考文獻(xiàn)所述的多種無(wú)用單元回收技術(shù)的一個(gè)共同特征是遞增地遍歷由獨(dú)立存儲(chǔ)的數(shù)據(jù)對(duì)象攜帶的參照指針?biāo)纬傻臄?shù)據(jù)結(jié)構(gòu)。這種技術(shù)包括用連接數(shù)據(jù)對(duì)象的指針通過(guò)跟蹤路徑首先標(biāo)記出所存儲(chǔ)的其它對(duì)象可達(dá)到的或來(lái)自外部存儲(chǔ)單元的所有存儲(chǔ)對(duì)象。

然后是掃描或壓縮存儲(chǔ)器，也就是說(shuō)，檢查存儲(chǔ)在存儲(chǔ)器中的每一個(gè)對(duì)象，以確定未被標(biāo)記的對(duì)象，然后回收這些對(duì)象的空間。

通常，無(wú)用單元回收和回收進(jìn)程以與程序進(jìn)程相并行的方式在計(jì)算機(jī)上運(yùn)行，無(wú)用單元回收器和回收進(jìn)程對(duì)程序進(jìn)程的數(shù)據(jù)對(duì)象所占據(jù)的堆棧(存儲(chǔ)區(qū))進(jìn)行操作，因此，能盡快地檢測(cè)到來(lái)自程序進(jìn)程的無(wú)用單元，可回收適當(dāng)?shù)馁Y源。

除程序進(jìn)程以外為了還實(shí)現(xiàn)無(wú)用單元回收進(jìn)程，每個(gè)進(jìn)程通常都作為對(duì)共享堆棧進(jìn)行操作的獨(dú)立線程來(lái)加以執(zhí)行。按獨(dú)立的線程來(lái)執(zhí)行所述進(jìn)程會(huì)在兩個(gè)進(jìn)程必須共享同樣的處理器資源時(shí)降低兩個(gè)進(jìn)程的效率。在處理一個(gè)線程時(shí)，可將另一個(gè)線程掛起，反之亦然。

在VLIW處理器中，可以獨(dú)立地編譯和執(zhí)行各個(gè)線程，在兩個(gè)線程之間交替地交換處理器資源。

依照本發(fā)明，提供了調(diào)度要由處理器并發(fā)執(zhí)行的指令的方法，所述處理器能同時(shí)執(zhí)行預(yù)定數(shù)量的指令，所述方法包括下列步驟：

按預(yù)定的規(guī)則使來(lái)自第一進(jìn)程和第二進(jìn)程的指令相交錯(cuò)，以給出第三進(jìn)程；以及

調(diào)度來(lái)自上述第三進(jìn)程的指令，以便在第一時(shí)間點(diǎn)由處理器加以執(zhí)行；

其中，第一進(jìn)程的指令生成這樣的數(shù)據(jù)結(jié)構(gòu)，這些數(shù)據(jù)結(jié)構(gòu)包括用存儲(chǔ)器堆棧中的標(biāo)識(shí)指針連接起來(lái)的數(shù)據(jù)對(duì)象，并且，所述第二進(jìn)程包括無(wú)用單元回收進(jìn)程，該進(jìn)程用于遍歷存儲(chǔ)器堆棧并回收分配給第一進(jìn)程未使用的數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)器。

本發(fā)明的一個(gè)優(yōu)點(diǎn)是，在不對(duì)正在執(zhí)行的進(jìn)程產(chǎn)生影響的情況下，將處理器的未用的并發(fā)執(zhí)行資源用于無(wú)用單元回收。