一种基于任务窃取的并发队列访问控制系统

摘要

本发明公开了一种基于任务窃取的并发队列访问控制方法及系统，基于任务窃取的并发队列访问控制系统由安全访问模块(1)、并发访问度监控模块(2)、任务调度模块(3)和预测模块(4)组成。本发明方法通过将双端队列的操作与访问控制分开，建立队列并发访问度的监控机制，在任务窃取的过程中，根据队列并发访问度来动态自适应选取队列进行操作，从而将双端队列的并发访问均匀的分担到每个双端队列上，并对每个双端队列的访问采用阻塞方式来保障对双端队列执行操作的线程安全。本发明方法支持不同的任务窃取策略，且对于运行在并行随机访问机上的使用任务窃取的应用，具有更高的吞吐率和加速效果。

主权项

一种基于任务窃取的并发队列访问控制系统，在PRAM系统上运行基于任务窃取的并发队列访问控制系统，其特征在于：所述基于任务窃取的并发队列访问控制系统由安全访问模块(1)、并发访问度监控模块(2)、任务调度模块(3)和预测模块(4)组成；任务调度模块(3)首先从PRAM系统中获得所有双端队列DEQUE＝{deque₁,deque₂,…,deque_i,…,deque_n}、所有并发访问度S＝{s₁,s₂,…,s_i,…,s_n}和所有线程THREAD＝{thread₁,thread₂,…,thread_i,…,thread_n}；其中，deque₁表示第一个双端队列，deque₂表示第二个双端队列，deque_i表示第i个双端队列，deque_n表示最后一个双端队列，n表示双端队列的标识号；s₁表示第一个双端队列deque₁的并发访问度，s₂表示第二个双端队列deque₂的并发访问度，s_i表示第i个双端队列deque_i的并发访问度，s_n表示最后一个双端队列deque_n的并发访问度，所述s_n中包括有当前被阻塞的线程个数a和双端队列deque_n中的任务个数b，则s_n＝(a,b)；所述双端队列DEQUE＝{deque₁,deque₂,…,deque_i,…,deque_n}包括有本地双端队列和外部双端队列；然后：(A)由任务调度模块(3)从DEQUE＝{deque₁,deque₂,…,deque_i,…,deque_n}中选取除deque_i以外的第一个待定‑双端队列deque₁，并记录下该deque₁的并发访问度s₁；继而，并发访问度监控模块(2)从deque₁提取出deque₁对应的s₁，由队列预测模块(4)依据并发访问度s₁来预测第一个待定‑双端队列deque₁是否存在访问密集，访问密集预测关系a表示当前被阻塞的线程个数，b表示双端队列deque_n中的任务个数，若则第一个待定‑双端队列deque₁被选取，成为第一个选定‑双端队列deque₁，执行安全访问模块(1)；若则放弃第一个待定‑双端队列deque₁，执行(B)；(B)由任务调度模块(3)从DEQUE＝{deque₁,deque₂,…,deque_i,…,deque_n}中选取除deque_i以外的第二个待定‑双端队列deque₂，并记录下该deque₂的并发访问度s₂；继而，并发访问度监控模块(2)从deque₂提取出deque₂对应的s₂，由队列预测模块(4)依据并发访问度s₂来预测第二个待定‑双端队列deque₂是否存在访问密集，访问密集预测关系a表示当前被阻塞的线程个数，b表示双端队列deque_n中的任务个数，若则第二个待定‑双端队列deque₂被选取，成为第二个选定‑双端队列deque₂，执行安全访问模块(1)；若则放弃第二个待定‑双端队列deque₂，执行(C)；(C)由任务调度模块(3)从DEQUE＝{deque₁,deque₂,…,deque_i,…,deque_n}中选取除deque_i以外的最后一个待定‑双端队列deque_n，并记录下该deque_n的并发访问度s_n；继而，并发访问度监控模块(2)从deque_n提取出deque_n对应的s_n，由队列预测模块(4)依据并发访问度s_n来预测最后一个待定‑双端队列deque_n是否存在访问密集，访问密集预测关系a表示当前被阻塞的线程个数，b表示双端队列deque_n中的任务个数，若则最后一个待定‑双端队列deque_n被选取，成为最后一个选定‑双端队列deque_n，执行安全访问模块(1)；若则放弃最后一个待定‑双端队列deque_n；安全访问模块(1)判断第一个选定‑双端队列deque₁是否被线程占用，若说明deque₁被线程占用，则会等待，直到变化为时止；若说明deque₁未被线程占用，则线程thread_i获得访问权，对deque₁执行获取任务操作；安全访问模块(1)判断第二个选定‑双端队列deque₂是否被线程占用，若说明deque₂被线程占用，则会等待，直到变化为时止；若说明deque₂未被线程占用，则线程thread_i获得访问权，对deque₂执行获取任务操作；安全访问模块(1)判断最后一个选定‑双端队列deque_n是否被线程占用，若说明deque_n被线程占用，则会等待，直到变化为时止，线程thread_i获得访问权；若说明deque_n未被线程占用，则线程thread_i获得访问权，对deque_n执行获取任务操作；对于外部双端队列的任务窃取包括有下列步骤：步骤101：双端队列并发度的监控当本地线程thread_i的双端队列deque_i中，没有任何任务时，则由任务调度模块(3)选择任意一个待定‑双端队列deque_n；然后由并发访问度监控模块(2)从所述待定‑双端队列deque_n中提取出并发访问度s_n＝(a,b)；随后执行步骤102；步骤102：预测能否高效获取对双端队列的访问预测模块(4)依据并发访问度s_n来预测所述待定‑双端队列deque_n是否存在访问密集，访问密集预测关系a表示当前被阻塞的线程个数，b表示双端队列deque_n中的任务个数，若则所述待定‑双端队列deque_n被选取，成为选定‑双端队列deque_n，执行安全访问模块(1)；若则放弃所述待定‑双端队列deque_n；步骤103：获取队列的访问权当本地线程thread_i需要对所述选定‑双端队列deque_n进行获取任务操作时，需要获取deque_n的访问权若说明deque_n未被线程占用，则线程thread_i获得访问权，执行步骤104；若说明deque_n被线程占用，则会等待，直到变化为时止，线程thread_i获得访问权，随后执行步骤104；步骤104：阻塞的访问队列在本地线程thread_i获得访问权后，会标记所述选定‑双端队列deque_n被线程thread_i占用；直至thread_i完成获取任务操作后，才会释放对选定‑双端队列deque_n的占用标记；最后，安全访问模块(1)向PRAM系统发出选定‑双端队列deque_n未被线程占用的信息；对于本地双端队列的任务窃取包括有下列步骤：步骤201：获取队列的访问权当本地线程thread_i的双端队列deque_i中存在任务时，判断deque_i的访问权若说明deque_i未被线程占用，则线程thread_i获得访问权，执行步骤202；若说明deque_i被线程占用，则会等待，直到变化为时止，线程thread_i获得访问权，随后执行步骤202；步骤202：阻塞的访问队列在本地线程thread_i获得访问权后，会标记deque_i双端队列被线程thread_i占用；直至thread_i完成获取任务操作后，才会释放对deque_i的占用标记；最后，安全访问模块(1)向PRAM系统发出deque_i未被线程占用的信息。