汪 謙,丁明波

(中國(guó)石油大學(xué)(華東)計(jì)算與通信工程學(xué)院,青島 266580)

一種多文件任務(wù)調(diào)度算法①

汪 謙,丁明波

(中國(guó)石油大學(xué)(華東)計(jì)算與通信工程學(xué)院,青島 266580)

計(jì)算機(jī)在處理多文件任務(wù)的時(shí)候,會(huì)出現(xiàn)同時(shí)讀寫(xiě)文件的情況,文件將會(huì)出現(xiàn)數(shù)據(jù)讀寫(xiě)不全或數(shù)據(jù)缺失.在Linux內(nèi)核中,單處理器情況下,通過(guò)同步機(jī)制來(lái)進(jìn)行任務(wù)的分配和處理,其中經(jīng)典的有原子操作,信號(hào)量機(jī)制,互斥鎖等實(shí)現(xiàn)方案.在多處理器系統(tǒng)中則是通過(guò)test-and-set原語(yǔ)操作來(lái)實(shí)現(xiàn).本文通過(guò)設(shè)計(jì)一種多文件任務(wù)調(diào)度的算法,避免整個(gè)系統(tǒng)發(fā)生互斥訪(fǎng)問(wèn).本文通過(guò)Matlab編程實(shí)現(xiàn)該算法,其結(jié)果表明本文提出的多文件調(diào)度算法能夠有效的并行執(zhí)行多文件任務(wù).

多任務(wù);任務(wù)調(diào)度;并行計(jì)算;文件鎖

隨著計(jì)算機(jī)行業(yè)的蓬勃發(fā)展,計(jì)算機(jī)運(yùn)算速度也逐漸遇到了一個(gè)瓶頸.計(jì)算機(jī)的處理器發(fā)展趨勢(shì)為多核處理器,操作系統(tǒng)系統(tǒng)則向分布式系統(tǒng)發(fā)展,為了提高計(jì)算機(jī)整體的運(yùn)算速度和提高資源其利用率,系統(tǒng)通過(guò)動(dòng)態(tài)分配不同計(jì)算機(jī)中的多個(gè)通用的物理和邏輯資源來(lái)實(shí)現(xiàn)系統(tǒng)調(diào)度任務(wù),從而提高計(jì)算機(jī)運(yùn)算速度.

計(jì)算機(jī)在執(zhí)行運(yùn)算的時(shí)候,操作系統(tǒng)首先對(duì)任務(wù)進(jìn)行調(diào)度,在任務(wù)的處理過(guò)程中如果出現(xiàn)多個(gè)任務(wù)同時(shí)訪(fǎng)問(wèn)計(jì)算機(jī)的臨界資源,會(huì)導(dǎo)致計(jì)算機(jī)發(fā)生死鎖,現(xiàn)在的計(jì)算機(jī)在多核或分布式操作系統(tǒng)的情況下,更容易出現(xiàn)多個(gè)任務(wù)同時(shí)訪(fǎng)問(wèn)計(jì)算機(jī)的臨界資源的問(wèn)題.針對(duì)該問(wèn)題,國(guó)內(nèi)外許多優(yōu)秀的學(xué)者都提出了一些高性能的鎖機(jī)制.ML Scott等在2000年提出了一種MCS Spinlock[1-3],該自旋鎖通過(guò)鏈表高效的解決了自旋鎖的可擴(kuò)展問(wèn)題,保證了自旋鎖的公平性.Choi S 等在2010年提出了一種基于分布式管理器的主機(jī)鎖機(jī)制[4,5],該鎖機(jī)制支持集群中的多個(gè)客戶(hù)端共享磁盤(pán).該鎖機(jī)制還有一個(gè)顯著的特點(diǎn),隨著鎖的請(qǐng)求速度的增加,該鎖機(jī)制的優(yōu)勢(shì)越明顯,它很好地提高了處理速度與利用率.上述方法雖然能夠?qū)崿F(xiàn)對(duì)文件進(jìn)行加鎖和共享文件,但在對(duì)共享文件進(jìn)行處理的時(shí)候并不能保證集群機(jī)器對(duì)共享文件不被多臺(tái)機(jī)器同時(shí)讀寫(xiě),同時(shí)集群機(jī)器有較高的利用率.

本文的系統(tǒng)主要對(duì)文件進(jìn)行處理,在對(duì)文件進(jìn)行操作的過(guò)程中,多個(gè)任務(wù)或者多個(gè)處理器很容易同時(shí)對(duì)某個(gè)文件進(jìn)行讀寫(xiě).但是一個(gè)任務(wù)如果對(duì)正在被其他任務(wù)讀取的文件進(jìn)行讀寫(xiě)操作,可能會(huì)出現(xiàn)讀操作的任務(wù)讀取到一些不完整的或者已經(jīng)被破壞的數(shù)據(jù).

本文系統(tǒng)設(shè)計(jì)如下,主計(jì)算機(jī)(本文中稱(chēng)為Master機(jī)器)產(chǎn)生需要計(jì)算的文件,多臺(tái)從計(jì)算機(jī)(本文中稱(chēng)為Slave機(jī)器)來(lái)獲取Master機(jī)器產(chǎn)生的文件,計(jì)算該文件并將結(jié)果保存.

Slave機(jī)器需要掃描Master是否生成新的文件,如果有新的文件產(chǎn)生,需要對(duì)文件進(jìn)行判斷是否有其他Slave機(jī)器正在執(zhí)行該文件,如果產(chǎn)生新文件之后沒(méi)有其他Slave機(jī)器執(zhí)行該任務(wù),則將該文件分配給Slave機(jī)器,其他情況下該Slave進(jìn)入忙等待狀態(tài).在查看文件有沒(méi)有被其他Slave機(jī)器執(zhí)行的時(shí)候,需要對(duì)文件進(jìn)行加文件鎖[6-8],告知其他機(jī)器該文件正在被讀寫(xiě).整個(gè)系統(tǒng)需要能夠形成一個(gè)流水線(xiàn)執(zhí)行操作,保證每臺(tái)機(jī)器能夠保證高效的執(zhí)行,縮短整個(gè)系統(tǒng)處理文件的時(shí)間.

本系統(tǒng)中,需要實(shí)現(xiàn)文件鎖機(jī)制,但是簡(jiǎn)單的文件鎖,不能夠保證所有的文件在讀寫(xiě)的過(guò)程中不會(huì)同時(shí)被多個(gè)Slave機(jī)器讀寫(xiě),導(dǎo)致文件數(shù)據(jù)不全或者文件處理出錯(cuò),整個(gè)系統(tǒng)的任務(wù)處理出現(xiàn)問(wèn)題.

本文設(shè)計(jì)并實(shí)現(xiàn)了一種新型的多文件任務(wù)調(diào)度的算法,解決了上述文件在讀寫(xiě)過(guò)程中,同時(shí)被同臺(tái)Slave讀寫(xiě)的問(wèn)題.

1 系統(tǒng)簡(jiǎn)介

Master機(jī)器在生成一個(gè)新的文件之后,如果文件較多或文件運(yùn)算時(shí)間很長(zhǎng)的情況下,整個(gè)執(zhí)行過(guò)程將會(huì)耗費(fèi)很長(zhǎng)時(shí)間.本文假設(shè),如果將Master機(jī)器產(chǎn)生的文件,通過(guò)網(wǎng)絡(luò)連接或者共享資源的方式,分配給多個(gè)Slave機(jī)器,Slave機(jī)器并行的計(jì)算文件任務(wù),整個(gè)過(guò)程在不同的機(jī)器上,可以減少大量的計(jì)算時(shí)間.此時(shí)Master機(jī)器只需要產(chǎn)生文件和對(duì)文件任務(wù)進(jìn)行調(diào)度,不需要執(zhí)行文件計(jì)算任務(wù),Slave則對(duì)任務(wù)進(jìn)行計(jì)算,Master和Slave之間相對(duì)獨(dú)立的運(yùn)行,大量減少M(fèi)aster機(jī)器對(duì)文件生成和運(yùn)行的時(shí)間.整個(gè)系統(tǒng)的總體構(gòu)造圖如圖1所示.

圖1 系統(tǒng)總體構(gòu)造圖

當(dāng)出現(xiàn)多臺(tái)Slave機(jī)器和Master機(jī)器在同時(shí)執(zhí)行任務(wù)的情況下,整個(gè)系統(tǒng)將會(huì)是一個(gè)大的集群,對(duì)系統(tǒng)的魯棒性需要很強(qiáng)大的要求,需要有一個(gè)對(duì)文件任務(wù)分配比較穩(wěn)定的調(diào)度算法來(lái)避免整個(gè)系統(tǒng)分配和執(zhí)行文件任務(wù)過(guò)程中產(chǎn)生同時(shí)讀寫(xiě)文件的問(wèn)題.

系統(tǒng)要求Master機(jī)器生成文件和Slave機(jī)器執(zhí)行任務(wù)相對(duì)獨(dú)立,保證Master機(jī)器和Slave機(jī)器在運(yùn)行較多文件任務(wù)的情況下能夠正常的執(zhí)行下去.

2 常用鎖機(jī)制簡(jiǎn)介

2.1 文件鎖機(jī)制

文件鎖是Linux 2.6內(nèi)核及其之后的版本提出的概念[9],早期的Linux版本只支持對(duì)整個(gè)文件進(jìn)行加鎖,因此不能運(yùn)行數(shù)據(jù)庫(kù)等對(duì)多文件處理要求較高的程序.在文件進(jìn)行操作的時(shí)候,對(duì)文件進(jìn)行加文件鎖,可以保證當(dāng)前文件在執(zhí)行的過(guò)程中其他文件不能對(duì)該文件進(jìn)行讀寫(xiě).

Linux支持的文件鎖主要包括勸告鎖和強(qiáng)制鎖:

勸告鎖是一種類(lèi)似生產(chǎn)者和消費(fèi)者工作機(jī)制的鎖,內(nèi)核對(duì)文件提供加鎖機(jī)制并對(duì)文件進(jìn)行檢測(cè)是否已經(jīng)加鎖,但是內(nèi)核對(duì)文件鎖不進(jìn)行控制和協(xié)調(diào).勸告鎖機(jī)制不能防止進(jìn)程對(duì)文件的訪(fǎng)問(wèn),只能通過(guò)各個(gè)進(jìn)程在對(duì)文件讀寫(xiě)時(shí)候,檢查其他進(jìn)程是否已經(jīng)對(duì)該文件加鎖.

強(qiáng)制鎖是一種采取強(qiáng)制作用的文件鎖,內(nèi)核對(duì)文件進(jìn)行強(qiáng)制加鎖,當(dāng)對(duì)文件進(jìn)行讀寫(xiě)操作時(shí)候,內(nèi)核都要檢查該文件是否被加鎖和其他進(jìn)程調(diào)用時(shí)候會(huì)不會(huì)違反其強(qiáng)制鎖的約束.如果文件被加上了讀寫(xiě)鎖,其他進(jìn)程對(duì)這個(gè)文件進(jìn)行讀寫(xiě)的時(shí)候就會(huì)被阻止.

文件鎖機(jī)制在Linux 2.6之后的內(nèi)核中使用,其實(shí)現(xiàn)的過(guò)程較為復(fù)雜,在Windows或其他的操作系統(tǒng)中不能直接使用.本系統(tǒng)的算法借鑒其強(qiáng)制鎖的實(shí)現(xiàn)思路,來(lái)完成系統(tǒng)的設(shè)計(jì).

2.2 Test_and_set鎖機(jī)制

Test_and_set[9]是一種不可中斷的原語(yǔ)操作,是特定的匯編指令,用來(lái)交換兩個(gè)內(nèi)存某一單元的值,將新值寫(xiě)入內(nèi)存特定的位置并傳回其舊值.多個(gè)進(jìn)程存取內(nèi)存的情況下,如果一個(gè)進(jìn)程正在執(zhí)行test_and_set,在它執(zhí)行完成前,其他的進(jìn)程不可以執(zhí)行test_and_set.

下面代碼展示的是使用test_and_set來(lái)實(shí)現(xiàn)鎖機(jī)制.

1)程序讀取 lock,如果 lock=0,設(shè)置 lock=1,程序加鎖,讀取臨界區(qū)資源.

2)如果 lock=1,直接返回 1,繼續(xù)進(jìn)行忙等待狀態(tài).

Test_and_set在執(zhí)行的時(shí)候,需要硬件配合完成,系統(tǒng)需要較大資源開(kāi)銷(xiāo)來(lái)保證內(nèi)存、緩存、以及寄存器等硬件之間數(shù)據(jù)一致.同時(shí),test_and_set不能保證任務(wù)按照FIFO順序獲取鎖,特殊情況下,部分程序需要很長(zhǎng)時(shí)間才能獲得鎖.

2.3 MCS Spinlock鎖機(jī)制

MCS Spinlock是基于鏈表的高性能、可擴(kuò)展的自旋鎖.如圖2所示,將全體鎖申請(qǐng)者的信息構(gòu)成一個(gè)單向鏈表,鎖申請(qǐng)者在使用前必須分配一個(gè)mcs_lock_node結(jié)構(gòu)體,mcs_lock是一個(gè)指向最后一個(gè)申請(qǐng)者的mcs_lock_node結(jié)構(gòu)的指針,并且當(dāng)前進(jìn)程鎖未被使用.

圖2 mcs_lock 結(jié)構(gòu)圖

mcs_lock的結(jié)構(gòu)體的偽代碼為:

每個(gè)處理器都代表著一個(gè)msc_lock_node,當(dāng)某個(gè)mcs_lock_node需要執(zhí)行時(shí):

1)將該mcs_lock_node加入mcs_lock隊(duì)列;

2)如果當(dāng)前隊(duì)列還有其他的node在等待,則設(shè)置is_locked=1,進(jìn)入忙狀態(tài),等待其他 node的執(zhí)行;

3)當(dāng)?shù)却?duì)列執(zhí)行到該mcs_lock_node的時(shí)候,喚醒該 mcs_lock_node,并設(shè)置 is_locked=0,執(zhí)行mcs_lock_node的操作;

4)新添加的或者任務(wù)執(zhí)行結(jié)束的處理器需要繼續(xù)執(zhí)行任務(wù),則按照 1,2,3 步驟來(lái)繼續(xù)執(zhí)行.

MCS spinlock在多線(xiàn)程任務(wù)的系統(tǒng)中能夠?qū)崿F(xiàn)較好的性能,本文實(shí)現(xiàn)的多任務(wù)調(diào)度算法,則通過(guò)改進(jìn)的MCS Spinlock 來(lái)實(shí)現(xiàn)的.

2.4 本系統(tǒng)的多任務(wù)調(diào)度算法

為了防止文件任務(wù)在處理的時(shí)候被多個(gè)Slave同時(shí)進(jìn)行讀寫(xiě),從而產(chǎn)生文件讀寫(xiě)錯(cuò)誤的情況.本系統(tǒng)將Slave執(zhí)行一個(gè)文件任務(wù)的過(guò)程設(shè)計(jì)為閉環(huán)模式,在Slave執(zhí)行某個(gè)文件任務(wù)的時(shí)候,該文件任務(wù)不能被其他Slave讀寫(xiě),保證該文件執(zhí)行的時(shí)候處于加鎖狀態(tài),Slave執(zhí)行完該文件之后才可以執(zhí)行其他文件任務(wù),保證整個(gè)處理過(guò)程的完整性.文件處理過(guò)程中,需要兩個(gè)隊(duì)列,Master機(jī)器生成的任務(wù)文件為file_task_queue隊(duì)列,Slave 機(jī)器在計(jì)算為 slave_queue 隊(duì)列,兩個(gè)隊(duì)列結(jié)構(gòu)體偽代碼如下:

這里file_id表示當(dāng)前Master生成的文件任務(wù)的id編號(hào),current_file_queue表示已經(jīng)執(zhí)行完文件的編號(hào),slave_name表示Slave機(jī)器的主機(jī)名(本文中稱(chēng)為S01,S02 …),is_idle 表示當(dāng)前 Slave 是否空閑.

在隊(duì)列首部的Slave的is_idle為False,表示該Slave機(jī)器不是空閑,隊(duì)列后續(xù)的slave_queue的is_idle都為T(mén)rue,表示空閑,可以接受分配任務(wù).

系統(tǒng)的設(shè)計(jì)的兩個(gè)隊(duì)列的效果圖,如圖3,系統(tǒng)對(duì)Slave和任務(wù)兩個(gè)隊(duì)列進(jìn)行調(diào)度執(zhí)行效果,如圖4.

圖3 系統(tǒng)隊(duì)列圖

圖4 隊(duì)列執(zhí)行效果圖

通過(guò)獲取Slave_queue和File_task_queue兩個(gè)隊(duì)列的頭部數(shù)據(jù),生成一個(gè)標(biāo)識(shí)文件Si_T0j_0,這時(shí)候告知T0j(表示任務(wù)編號(hào))任務(wù)已經(jīng)被分配,同時(shí)Si(Slave機(jī)器編號(hào))機(jī)器is_idle為False,該Slave機(jī)器不是空閑狀態(tài).

整個(gè)算法的過(guò)程如圖5所示.

1)Slave開(kāi)始運(yùn)行之后就在Slave_queue隊(duì)列中添加S0N標(biāo)記,表明該Slave處于空閑狀態(tài);

2)Master從Slave_queue隊(duì)列中獲知S0N空閑,File_task_queue隊(duì)列中的file_id(這里稱(chēng)為M),給S0N分配T000M文件,生成標(biāo)記文件S0N_T000M_0標(biāo)志文件(其中_0表示文件未被執(zhí)行,_1表示文件已經(jīng)被執(zhí)行),在Slave_queue中刪除SN標(biāo)志;

3)Slaver0N 掃描文件得到 S0N_T000M_0,執(zhí)行T000M文件,當(dāng)文件執(zhí)行完之后,繼續(xù)在Slave_queue中添加S0N節(jié)點(diǎn),同時(shí)File_task_queue中的file_id加1 操作,將標(biāo)記文件 S0N_T000M_0 刪除,并生成標(biāo)記文件S0N_T000M_1,方便系統(tǒng)以后檢查文件執(zhí)行過(guò)程;

4)當(dāng)文件任務(wù)被 Slave 執(zhí)行完之后,繼續(xù)重復(fù) 1,2,3步驟執(zhí)行,系統(tǒng)高效地對(duì)文件任務(wù)進(jìn)行調(diào)度和執(zhí)行.

根據(jù)上述算法的介紹,Salve機(jī)器處理一個(gè)任務(wù)的過(guò)程是一個(gè)閉環(huán)的處理過(guò)程,其執(zhí)行的流程圖如圖6,處理過(guò)程如下:

1)從Slave空閑隊(duì)列里面找到某個(gè)空閑的Slave 機(jī)器 Slave N,對(duì)該 Slave N 加標(biāo)記 S0N,告知其處于空閑狀態(tài),能夠被分配文件任務(wù).

2)Master機(jī)器通過(guò)識(shí)別 Slave 隊(duì)列,獲取隊(duì)列隊(duì)首S0N標(biāo)志,從而知道Slave N為空閑,則在任務(wù)的隊(duì)列中隊(duì)首選擇需要執(zhí)行的任務(wù)Task M,將Slave和需要執(zhí)行的文件設(shè)置成S0N_T0M_0標(biāo)志,并且刪掉S0N 標(biāo)志,此時(shí) Slave N 處于忙狀態(tài),同時(shí) Task M 處于加鎖狀態(tài)只能被Slave N進(jìn)行讀取.

3)當(dāng) Task M 執(zhí)行完之后,Master機(jī)器獲知對(duì)標(biāo)志S0N_T0M_1,這時(shí)Slave N已經(jīng)執(zhí)行完一個(gè)文件任務(wù),Slave N 恢復(fù)空閑狀態(tài).

圖5 算法過(guò)程圖

Slave在完成一個(gè)文件任務(wù)的處理之后,轉(zhuǎn)而進(jìn)入下一個(gè)文件任務(wù),每一個(gè)任務(wù)的執(zhí)行都是一個(gè)完整的閉環(huán)的過(guò)程.當(dāng)系統(tǒng)中存在著多個(gè)Slave機(jī)器和多個(gè)任務(wù)的時(shí)候,整個(gè)系統(tǒng)將會(huì)處于高效且并行的狀態(tài)運(yùn)行.

圖6 Slave 執(zhí)行效果圖

3 實(shí)驗(yàn)部分

本文實(shí)驗(yàn)在Windows環(huán)境中,通過(guò)Matlab編程環(huán)境實(shí)現(xiàn).使用的是 4 臺(tái) Windows 7 64 位電腦,其中的一臺(tái)電腦作為Master機(jī)器來(lái)生成任務(wù),剩下的三臺(tái)電腦作為Slave機(jī)器來(lái)對(duì)Master機(jī)器生成的任務(wù)進(jìn)行監(jiān)控,解析和計(jì)算.Master機(jī)器上運(yùn)行著Master程序,Slave機(jī)器上則運(yùn)行著Slave程序.

整個(gè)系統(tǒng)運(yùn)行在一個(gè)共享文件夾中,對(duì)任務(wù)文件的生成,讀寫(xiě)都在該共享文件夾中運(yùn)行.

Master機(jī)器在分別產(chǎn)生 100,500,1000 個(gè)小文件任務(wù)(Slave處理文件的時(shí)間小于1S)的時(shí)候,各個(gè)Slave機(jī)器所執(zhí)行的任務(wù)個(gè)數(shù),如表1所示.

表1 Slave 執(zhí)行小文件效果

當(dāng)Master機(jī)器分別產(chǎn)生100、500、1000個(gè)大文件任務(wù)(Slave處理文件的時(shí)間大于10S)的時(shí)候,各個(gè)Slave及其所執(zhí)行的任務(wù)個(gè)數(shù),如表2所示.

表2 Slave 及其執(zhí)行大文件效果

結(jié)果顯示,整個(gè)系統(tǒng)能夠較好的執(zhí)行Master產(chǎn)生的文件任務(wù),Slave執(zhí)行文件的數(shù)量基本相等,調(diào)度程序在對(duì)文件處理的時(shí)候具有較好的性能.同時(shí),每個(gè)文件任務(wù)在處理的時(shí)候都是相對(duì)獨(dú)立,沒(méi)有出現(xiàn)多個(gè)Slave讀寫(xiě)同一個(gè)文件的情況.

系統(tǒng)設(shè)計(jì)的多任務(wù)調(diào)度算法,在Windows或其他操作系統(tǒng)下也能夠比較容易編程實(shí)現(xiàn),不需要添加其他硬件支持,僅僅需要設(shè)置網(wǎng)絡(luò)接口或者機(jī)器在局域網(wǎng)的情況下,使用共享文件夾的方式就可以執(zhí)行.

4 結(jié)語(yǔ)

本文提出的算法實(shí)現(xiàn)簡(jiǎn)單,能更方便地處理多文件任務(wù)并行調(diào)度和執(zhí)行的問(wèn)題,Slave機(jī)器在一個(gè)閉環(huán)操作之后,立即進(jìn)入下一個(gè)閉環(huán)操作,整個(gè)過(guò)程具有較強(qiáng)的魯棒性.系統(tǒng)在保證整個(gè)運(yùn)行環(huán)境穩(wěn)定的條件下,能夠較好的處理文件任務(wù),并對(duì)集群中機(jī)器有著較高的使用率,同時(shí)大幅度降低使用一個(gè)機(jī)器來(lái)執(zhí)行整個(gè)計(jì)算過(guò)程需要的時(shí)間.

1 Mellor-Crummey JM,Scott ML.Algorithms for scalable synchronization on shared-memory multiprocessors.ACM Trans.on Computer Systems,1991,9(1):21–65.[doi:10.1145/103727.103729]

2 付智杰,周群彪.MCS spinlock 的 Linux 內(nèi)核模塊實(shí)現(xiàn).微計(jì)算機(jī)應(yīng)用,2009,30(7):55–59.

3 Peng ZW,Xu XA.The analysis of Linux kernel spinning lock on SMP.Journal of Jiangxi Institute of Education(Comprehensive),2005,26(3):23–25,28.

4 Snaman W,Thiel D.The VAX/VMS distributed lock manager.Digital Technical Journal,1987.

5 Choi S,Choi M,Lee C,et al.Distributed lock manager for distributed file system in shared-disk environment.Proc.of the 10th International Conference on Computer and Information Technology (CIT).Bradford,UK.2010.2706–2713.

6 周超,劉云朋.Linux 文件鎖技術(shù)的分析與實(shí)現(xiàn).電腦開(kāi)發(fā)與應(yīng)用,2009,22(4):43–44,51.

7 博韋,西斯特.深入理解 LINUX 內(nèi)核.陳莉君，張瓊聲，張宏偉,譯.3 版.北京:中國(guó)電力出版社,2007.

8 陳莉君.Linux 操作系統(tǒng)內(nèi)核分析.北京:人民郵電出版社,2000.

9 Zhou C,Liu Y P.Analysis and realization of file lock in Linux.Computer Development &Applications,2009,22(4):43–44,51.

10 Alistarh D,Attiya H,Gilbert S,et al.Fast randomized testand-set and renaming.Proc.of the 24th International Conference on Distributed Computing Cambridge,MA,USA.2010.94–108.

Algorithm for Scheduling Multi-Task

WANG Qian,DING Ming-Bo

(School of Computer &Communication,China University of Petroleum,Qingdao 266580,China)

When the computer is handling multi-file tasks,it may read and write a file at the same time,resulting in the failure of the file data to be fully read and written or in the loss of some data.In the Linux kernel,with the single processor,task allocation and processing is made with the synchronization mechanism.The classic approach is atomic operations,semaphore mechanisms,mutexes,etc.In the multi-processor systems,the test-and-set primitive operation is made to solve the problem.In this paper,we design a new task scheduling scheme for multitasking to avoid mutual exclusion access.We use a Matlab program to realize the algorithm,and the result shows that the algorithm can effectively realize the multi-file tasks parallel execution.

multi-file;task scheduling;concurrent computation;file lock

汪謙,丁明波.一種多文件任務(wù)調(diào)度算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(9):140–144.http://www.c-s-a.org.cn/1003-3254/5993.html

①基金項(xiàng)后:中國(guó)石油大學(xué)(華東)研究生創(chuàng)新工程資助項(xiàng)后(CX2013028);中央高校基本科研業(yè)務(wù)類(lèi)專(zhuān)項(xiàng)基金(14CX02032A)

2016-12-21;采用時(shí)間:2017-02-17