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

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

可绘制对象 Drawable 是 X 中所有可绘制对象的基本抽象结构,所有 GCOps 的操作都在某一种可绘制对象
Drawable 上完成.Drawable 又分为 Pixmap 和 Window 两种,一般认为,Pixmap 为单纯图像的位图,而 Window 则
可能包含标题栏、菜单栏、按钮栏和窗体等组成部分.本文算法主要针对 Window 类型的 Drawable 对象实现.
矩形填充函数 PolyFillRect 是帧缓存设备的 GCOps 的绘图操作函数指针之一,专门用来在帧缓存设备上填
充绘制由纯色填满的矩形.相应的参数包含 4 部分.
1) 指向 Drawable 对象的指针 pDrawable;
2) 指向 GC 的指针 pGC;
3) 该次绘制的矩形数量 nrect;
4) 该次调用需要填充的矩形结构链表的指针 prect.
PolyFillRect 一般随后会调用单个矩形绘制函数,例如 fbFill,逐个绘制链表 prect 所指向的所有矩形,fbFill
的前 2 个参数一般与 PolyFillRect 相同,后 4 个参数一般是矩形的左上顶点的坐标值(x,y)以及宽度 w 和高度 h.
本文算法就是针对在帧缓存设备上的矩形绘制进行多线程优化的,在单个矩形绘制函数 fbFill 中生成任务并分
发给多个子线程完成,其他绘制操作可以按照类似方法进行优化.

2 相关工作

针对 X 相关的多线程优化,已有的工作包括多调度队列算法、X 的输入线程化、CPU 和 GPU 协同多线程
等.Linux 内核调度器的多调度队列算法打破了集中调度的局限性,采用分散的多调度队列,降低了全局调度开
销.不过,针对其他具体应用场景,仍需要根据算法思想进行重新设计和优化.X 的输入线程化是指将处理鼠标键
盘事件的过程作为单独的线程分离出来,但并未进行多线程处理,也不涉及帧缓存设备的优化.CPU 和 GPU 协
同多线程优化主要涉及 CPU 端的数据准备和控制等方面的多线程优化,以便充分发挥高性能 GPU 的绘制性能
起辅助功能,但不包含 CPU 端针对帧缓存设备的优化工作.
2.1 多调度队列
在并行计算中,单调度队列带来的性能开销往往都是 O(n)的,全局单一的任务调度队列往往会带来访问冲
突、性能开销大等问题.例如:Linux 内核在 2.4 版本之前的调度器采用全局单一调度队列,调度的开销是 O(n);
而 2.6 版本之后引入的 O(1)调度器针对每个优先级分别设置私有的任务调度队列,将调度开销降低到 O(1)的常
数时间,可以做到调度开销与系统中线程个数无关.CFS 调度器则为每一个 CPU 核心维护一棵以时间为顺序的
红黑树,确保实现接近完全公平的进程调度 [33] .但针对其他具体应用场景仍需重新设计算法.
2.2 输入线程化

在通常的处理流程中,X 图形服务器在没有任何输入时一直保持睡眠状态,直到被鼠标键盘的输入事件激
发的 SIGIO 信号唤醒.因为信号处理开销较大,也容易发生无效唤醒(lost wakeup)的问题,开源社区已在尝试放
弃原先沿用的 SIGIO 信号,改用独立的单个线程处理输入事件.例如,Keith Packard 这几个月以来提交的
threaded input 补丁 [34] ,现在已经合并到主分支加以发布.输入线程从主事件循环中独立出来,将有效地减小主事
件循环中鼠标键盘的处理过程对图形绘制的影响,改造后,如图 3 所示,X 图形服务器根据用户请求绘制图形的
过程(process request)将不必再等待鼠标键盘处理过程(processInput)完成,而可以立即执行.但处理鼠标键盘的
输入线程仍为一个,没有考虑多用户的情况,具体可以参考第 5.3 节的讨论.
2.3 CPU和GPU协同多线程
即使在图 4(b)所示的 GPU 绘制模式中,CPU 也具有重要作用:CPU 将协助 GPU 准备所需的数据并进行控
制.由于现在很多 GPU 性能越来越高,所以不少情况下 CPU 端的计算也会成为系统的瓶颈,此时进行 CPU 的多
核优化将有助于消除这种绘制过程中的瓶颈.例如,最新的 Windows 平台上的图形开发库 DirectX 12 和 Linux
的下一代 OpenGL Vulkan 都已经实现了针对多核 CPU 的优化,图形渲染性能成倍提高 [35,36] .