[發(fā)明專利]基于陣列的線程倒計(jì)時(shí)

有效

• 申請(qǐng)?zhí)枺?/td>: 201110037368.1
• 申請(qǐng)日: 2011-01-28
• 公開(kāi)（公告）號(hào): CN102141906A
• 公開(kāi)（公告）日: 2011-08-03
• 發(fā)明（設(shè)計(jì)）人: E·A·奧瑪拉;J·J·達(dá)菲
• 申請(qǐng)（專利權(quán)）人: 微軟公司
• 主分類號(hào): G06F9/38
• 分類號(hào): G06F9/38
• 代理公司: 上海專利商標(biāo)事務(wù)所有限公司 31100
• 代理人: 陳斌;錢(qián)靜芳

技術(shù)領(lǐng)域

本發(fā)明涉及計(jì)算系統(tǒng)中的線程處理，尤其涉及線程處理中的線程分配。

背景

多處理器計(jì)算系統(tǒng)能夠在過(guò)程中同時(shí)執(zhí)行多個(gè)線程，這常被稱為并行處理。獲得較好并行處理的最簡(jiǎn)單且有效的方式之一是分叉/加入并行性。如果線程遇到可被細(xì)分成多個(gè)獨(dú)立任務(wù)的特定任務(wù)，則可發(fā)生分叉操作，在其中向不同線程分配不同的獨(dú)立任務(wù)。當(dāng)完成所有的任務(wù)時(shí)，加入分叉線程來(lái)允許初始線程繼續(xù)工作。由此，在分叉/加入并行性中，檢測(cè)何時(shí)完成了執(zhí)行其有關(guān)的分叉子任務(wù)的所有線程是重要的。

檢測(cè)何時(shí)完成了所有線程的一種方式是在啟動(dòng)分叉的時(shí)間設(shè)置鎖存。用計(jì)數(shù)N來(lái)初始化該鎖存，其中N是分叉線程在分叉子任務(wù)上操作的獨(dú)立線程的數(shù)量。由于每一分叉線程完成其子任務(wù)，該線程向鎖存發(fā)信號(hào)，這導(dǎo)致鎖存將該計(jì)數(shù)遞減1。所完成的分叉線程可隨后在鎖存上等待。當(dāng)鎖存計(jì)數(shù)達(dá)到零的時(shí)候，意味著所有分叉線程已完成并發(fā)信號(hào)給鎖存。此時(shí)，所有線程都被喚醒。

該鎖存的一實(shí)現(xiàn)是使用在構(gòu)造時(shí)被設(shè)置為計(jì)數(shù)N且在每次信號(hào)調(diào)用時(shí)遞減的單個(gè)整數(shù)變量。當(dāng)該變量變成零的時(shí)候設(shè)置鎖存。

發(fā)明內(nèi)容

本文描述的至少一個(gè)實(shí)施例涉及線程分叉的操作。在運(yùn)行時(shí)，任務(wù)被標(biāo)識(shí)為被分成多個(gè)線程(即，分叉線程)要完成的多個(gè)子任務(wù)。為了能夠驗(yàn)證分叉線程何時(shí)完成其任務(wù)，當(dāng)分叉線程完成時(shí)設(shè)置和更新多個(gè)計(jì)數(shù)器存儲(chǔ)器位置。在聚集中對(duì)多個(gè)計(jì)數(shù)器存儲(chǔ)器位置求值以便確定是否完成了所有的分叉線程。一旦分叉線程被確定為已完成，就可以執(zhí)行加入操作。

使用多個(gè)存儲(chǔ)器位置而不是單個(gè)存儲(chǔ)器位置來(lái)考慮線程完成。這降低了線程爭(zhēng)用的風(fēng)險(xiǎn)。在一個(gè)實(shí)施例中，存儲(chǔ)器位置與高速緩存行的邊界對(duì)應(yīng)，從而使得較不可能發(fā)生線程爭(zhēng)用。

本發(fā)明內(nèi)容并非旨在標(biāo)識(shí)所要求保護(hù)的主題的關(guān)鍵特征或必要特征，也不旨在用于幫助確定所要求保護(hù)的主題的范圍。

附圖簡(jiǎn)述

為了描述可以獲得本發(fā)明的上文所列舉的及其他優(yōu)點(diǎn)和特征的方式，下面將通過(guò)參考附圖來(lái)呈現(xiàn)對(duì)各實(shí)施例的更具體的描述。可以理解，這些附圖只描繪了示例實(shí)施例，并且因此不被認(rèn)為是對(duì)其范圍的限制，將通過(guò)使用附圖并利用附加特征和細(xì)節(jié)來(lái)描述和解釋各實(shí)施例，在附圖中：

圖1示出了可用于采用此處所描述的實(shí)施例的示例計(jì)算系統(tǒng)；

圖2示出了用于執(zhí)行線程并發(fā)分叉和加入操作的方法的流程圖；

圖3示出了具有被分成多個(gè)分叉任務(wù)由多個(gè)分叉線程在不同時(shí)間所完成的任務(wù)的線程；

圖4A示出了在其中計(jì)數(shù)器存儲(chǔ)器位置的數(shù)量與分叉線程的數(shù)量相同的計(jì)數(shù)器存儲(chǔ)器位置的配置；

圖4B示出了在其中計(jì)數(shù)器存儲(chǔ)器位置的數(shù)量小于分叉線程的數(shù)量的計(jì)數(shù)器存儲(chǔ)器位置的配置；以及

圖4C示出了在其中計(jì)數(shù)器存儲(chǔ)器位置的數(shù)量大于分叉線程的數(shù)量的計(jì)數(shù)器存儲(chǔ)器位置的配置。

詳細(xì)描述

根據(jù)本文描述的各實(shí)施例，描述了線程分叉的操作。在運(yùn)行時(shí)，任務(wù)被標(biāo)識(shí)為被分成多個(gè)線程(即，分叉線程)要完成的多個(gè)子任務(wù)。為了能夠驗(yàn)證分叉線程何時(shí)完成其任務(wù)，當(dāng)分叉線程完成時(shí)設(shè)置和更新多個(gè)計(jì)數(shù)器存儲(chǔ)器位置。在聚集中對(duì)多個(gè)計(jì)數(shù)器存儲(chǔ)器位置求值以便確定是否完成了所有的分叉線程。一旦分叉線程被確定為已完成，就可以執(zhí)行加入操作。首先，關(guān)于計(jì)算系統(tǒng)的某些介紹性討論將參考圖1來(lái)描述。隨后，分叉操作的使用的各種實(shí)施例將參考圖2至4C來(lái)描述。

首先，關(guān)于多處理器計(jì)算系統(tǒng)的介紹性討論將參考圖1來(lái)描述。計(jì)算系統(tǒng)現(xiàn)在越來(lái)越多地采取各種形式。計(jì)算系統(tǒng)可以是，例如，手持式設(shè)備、電器、膝上型計(jì)算機(jī)、臺(tái)式計(jì)算機(jī)、大型機(jī)、分布式計(jì)算系統(tǒng)，或者甚至常規(guī)上不被視為計(jì)算系統(tǒng)的設(shè)備。在本說(shuō)明書(shū)以及權(quán)利要求書(shū)中，術(shù)語(yǔ)“計(jì)算系統(tǒng)”被廣義地定義為包括包含至少一個(gè)處理器以及其上能含有可由處理器執(zhí)行的計(jì)算機(jī)可執(zhí)行指令的存儲(chǔ)器在內(nèi)的任何設(shè)備或系統(tǒng)(或其組合)。存儲(chǔ)器可以采取任何形式，并可以取決于計(jì)算系統(tǒng)的性質(zhì)和形式。計(jì)算系統(tǒng)可以分布在網(wǎng)絡(luò)環(huán)境中，并可包括多個(gè)組成計(jì)算系統(tǒng)。

如圖1所示，多處理計(jì)算系統(tǒng)100在其最基本的配置中通常包括至少兩個(gè)處理器102A和102B，但可包括更多、或許多得多的處理器，如省略號(hào)102C所表示的。計(jì)算系統(tǒng)100還可包括存儲(chǔ)器104，可以是物理系統(tǒng)存儲(chǔ)器，可以是易失性的、非易失性的、或兩者的某種組合。術(shù)語(yǔ)“存儲(chǔ)器”在此也可用來(lái)指諸如物理存儲(chǔ)介質(zhì)等非易失性大容量存儲(chǔ)。如果計(jì)算系統(tǒng)是分布式的，則處理、存儲(chǔ)器和/或存儲(chǔ)能力也可以是分布式的。如此處所使用的，術(shù)語(yǔ)“模塊”或“組件”可以指在計(jì)算系統(tǒng)上執(zhí)行的軟件對(duì)象或例程。此處所描述的不同組件、模塊、引擎，以及服務(wù)可以實(shí)現(xiàn)為在計(jì)算系統(tǒng)上執(zhí)行的對(duì)象或進(jìn)程(例如，作為分離的線程)。