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

汪 謙,丁明波

(中國石油大學(華東)計算與通信工程學院,青島 266580)

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

汪 謙,丁明波

(中國石油大學(華東)計算與通信工程學院,青島 266580)

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

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

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

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

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

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

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

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

本文設計并實現(xiàn)了一種新型的多文件任務調(diào)度的算法,解決了上述文件在讀寫過程中,同時被同臺Slave讀寫的問題.

1 系統(tǒng)簡介

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

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

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

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

2 常用鎖機制簡介

2.1 文件鎖機制

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

Linux支持的文件鎖主要包括勸告鎖和強制鎖:

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

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

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

2.2 Test_and_set鎖機制

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

下面代碼展示的是使用test_and_set來實現(xiàn)鎖機制.

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

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

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

2.3 MCS Spinlock鎖機制

MCS Spinlock是基于鏈表的高性能、可擴展的自旋鎖.如圖2所示,將全體鎖申請者的信息構成一個單向鏈表,鎖申請者在使用前必須分配一個mcs_lock_node結構體,mcs_lock是一個指向最后一個申請者的mcs_lock_node結構的指針,并且當前進程鎖未被使用.

圖2 mcs_lock 結構圖

mcs_lock的結構體的偽代碼為:

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

1)將該mcs_lock_node加入mcs_lock隊列;

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

3)當?shù)却犃袌?zhí)行到該mcs_lock_node的時候,喚醒該 mcs_lock_node,并設置 is_locked=0,執(zhí)行mcs_lock_node的操作;

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

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

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

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

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

在隊列首部的Slave的is_idle為False,表示該Slave機器不是空閑,隊列后續(xù)的slave_queue的is_idle都為True,表示空閑,可以接受分配任務.

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

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

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

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

整個算法的過程如圖5所示.

1)Slave開始運行之后就在Slave_queue隊列中添加S0N標記,表明該Slave處于空閑狀態(tài);

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

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

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

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

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

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

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

圖5 算法過程圖

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

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

3 實驗部分

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

整個系統(tǒng)運行在一個共享文件夾中,對任務文件的生成,讀寫都在該共享文件夾中運行.

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

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

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

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

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

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

4 結語

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

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)核模塊實現(xiàn).微計算機應用,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 文件鎖技術的分析與實現(xiàn).電腦開發(fā)與應用,2009,22(4):43–44,51.

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

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

①基金項后:中國石油大學(華東)研究生創(chuàng)新工程資助項后(CX2013028);中央高?；究蒲袠I(yè)務類專項基金(14CX02032A)

2016-12-21;采用時間:2017-02-17