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

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

冲区里面的产品之后 [37] ,生产者才能加入新的产品.但空闲的生产者可能浪费系统软硬件资源.
3.3.1 溢出队列
与经典生产者消费者模型不同,本算法设立了私有任务队列的溢出队列,用于主子线程间的负载均衡 [38,39] .

如图 6 中的溢出队列所示:当某个子线程 T k 的就绪队列 Q k 长度大于队列长度预设阈值 N 时,生产者主线程 T 0
将暂停生产任务,并协助任务已满的子线程绘制矩形.具体就是从 Q k 中弹出等待最久的若干任务形成溢出队列,
并加入到主线程 T 0 的运行队列 q 0 中,由主线程 T 0 尽快地将溢出的任务绘制完成.当生产者主线程 T 0 完成所有
子线程的溢出任务后,生产者主线程 T 0 才再次重新转换回生产者角色,继续生产任务.
这种主子线程间的负载均衡主要有以下好处.
1) 防止子线程任务队列长度的无限快速增长.如图 7 所示算法,如果不进行负载均衡,主线程 T 0 将任务放
入恰当的子线程 T k 的就绪队列 Q k 后,并不需要做任何实际的矩形填充绘制工作即可返回,所以从调
用主线程 T 0 的应用程序来看,矩形填充操作都将会以异常快的速度完成,而此时的任务实际上仍然在
某个子进程的私有缓冲区中,并没有实际绘制完成.如果不对生产产品的速度加以限制,这将可能导
致过长的就绪队列 Q k .当 Drawable 所属的整个进程退出时,相应子线程将不得不耗费非常长的时间
来处理并清空这些任务队列;
2) 防止图形界面进入无响应的等待状态.因为如果 Xorg 主线程 T 0 发现任务生产过多后,不进行负载均
衡而是立即进入睡眠状态,这将导致 Xorg 进入无响应的等待状态,停止响应用户的鼠标键盘,图形交
互系统也将失去响应,当前窗口将变灰无法操作.
值得注意的是:因为没有线程给生产者主线程 T 0 分配任务,所以 T 0 的就绪队列 Q 0 一直保持为空.

4 测试和结论

4.1 测试平台和用例

测试平台采用一台商用 DELL OPTIPLEX 3010 台式机,4 核心,4G 内存,操作系统采用 Ubuntu 15.10,内核为
4.2.0.测试用例采用通用的 x11perf -rect100 测试用例,如图 10 所示.

S x 份

屏幕分成

绘制小矩形

屏幕分成 S x 份

Fig.10 x11perf -rect100
图 10 x11perf -rect100 测试用例
上述的测试平台在单线程的普通帧缓存模式下,x11perf -rect100 的得分约为 454 000.在并行帧缓存算法中,
将把图 10 所示的测试窗口按照 x 轴和 y 轴分别均分成 S x 和 S y 份,共被分为 S x ⋅S y 个互不相交的子屏幕.测试结
果如图 11~图 19 所示.