Page 338 - 《软件学报》2020年第10期

3314 Journal of Software 软件学报 Vol.31, No.10, October 2020

任务分发方向 单线程逐个执行任务 子线程 T k+1
主线程 T 0

(a) 共享队列模式 子线程 T k+2
子线程 T k,k>0

(b) 私有队列模式
任务分发方向
主线程 T 0
运行队列 q 0

子线程数量共 S x⋅S y 个
子线程 T k,k>0

…
位置(x,y,w,h)
序列号 seq
其他相关参数
就绪队列 运行队列 溢出队列 子线程 T k+1
Q k q k
填充矩形 R 的任务 t 长度 N 长度 M

Fig.6 Multi-task queues
图 6 多任务调度队列

PROCEDURE Master(pDrawable,pGC,x,y,w,h)
INPUT:Drawable 指针 pDrawable,GC 指针
pGC,矩形坐标 x,y,矩形大小 w,h;
OUTPUT:子线程就绪队列 Q k.
BEGIN
建立 S x⋅S y 个子线程
新建任务 R(x,y,w,h,seq++)
计算 R 应当归属的子屏幕和子线程序号 k
Q k,并唤醒所有等待 Q k 的子线程
将任务 R 加入子线程 T k 的就绪队列
IF (Q k 的长度>N) DO{
取出 Q k 的最多前 M 个任务加入到主线程 T 0 的运行队列 q 0
Process(q 0)
}
END
Fig.7 Master T 0 thread
图 7 主线程 T 0 算法

PROCEDURE Worker(Q k)
INPUT:子线程就绪队列 Q k;
BEGIN
DO{
IF (就绪队列 Q k 的长度>0){
从 Q k 中取出包含最多 M 个任务放入子线程 T k 的运行队列 q k

Process(q k)
} ELSE
睡眠等待 Q k
} WHILE (True)
END
Fig.8 Worker T k thread
图 8 子线程 T k 算法