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

高珑 等:并行帧缓存设备:基于多核 CPU 的 Xorg 并行显示优化 3315

PROCEDURE Process(q k)
INPUT:子线程运行队列 q k

BEGIN

WHILE (队列 q k 不为空){
弹出 q k 头部任务 R

绘制任务 R
}
END
Fig.9 Process function
图 9 Process 子函数
3.2.1 任务封装
首先,单个矩形 R(x,y,w,h,seq)被封装成为独立的矩形填充任务 t,如图 6(b)所示,其中包含矩形的坐标〈x,y〉、
宽 w、高 h、标记时间顺序的序列号 seq 等内容,这样便于将多个矩形填充任务加入队列.序列号 seq 代表任务
生成时的时间戳,如图 5 所示算法,每生成一次序列号 seq 加 1.seq 采用长整型类型 long int,一般假定 seq 在
Drawable 生存周期中不会溢出.因此,如果某任务的序列号较小,那么该任务的生成时间也较早.
3.2.2 条件等待
每一个任务队列都设有加入任务和弹出任务两个条件等待变量,分别用于控制向队列中加入任务和弹出
任务.当任务队列 l 为空时,所有从队列 l 中弹出任务的线程,将自动进入睡眠状态等待,直到有线程向队列 l 中压
入任务后,将自动唤醒所有等待任务的线程,继续从队列中弹出任务.同样地,若队列 l 的长度超出阈值后,所有向
队列 l 中增加任务的线程将获得一个错误返回值,表明队列长度已经超过限定值;此时可以采取相应措施应对,
本算法采取的是主子线程负载均衡的措施,具体见第 3.3 节中的讨论.图 7 和图 8 所示算法中,都隐含了操作队
列时的唤醒和睡眠动作.
3.2.3 私有缓冲区
在标准的单生产者多消费者模型中 [37] ,多消费者共享的公用缓冲区容易产生拥塞.如果采用共享的公用缓
冲区,如图 6(a)所示,则将导致两个问题:(1) 共享的公用缓冲区将带来竞争冲突,某一个消费者在读写访问公用
缓冲区时,其他消费者只能等待;(2) 每一个消费者遍历共享的公用缓冲区的开销较大,遍历开销与缓冲区的长
度 N 成正比,如果共享的公用缓冲区较大,还将导致线程间的竞争开销急剧增长.
在并行帧缓冲算法中,每个消费者都具有私有的队列缓冲区.主线程既是生产者,也要负责将任务分配到适
当的子线程中去.主线程将按照分屏规则把每一个矩形放入相应的消费者子线程的私有队列缓冲区中去.由于
主线程分配任务时处于串行模式没有竞争,可以较快完成,所以这样既避免了消费者遍历共享的公用缓冲区挑
选任务的开销,也避免了多消费者在访问共享的公用缓冲区时可能产生的竞争冲突.具体如图 6(b)所示,在并行
帧缓存设备算法中,每个消费者子线程 T k 都拥有两个相对独立的私有任务队列:就绪队列 Q k 和运行队列 q k .生
产者主线程 T 0 产生矩形填充任务后,根据第 3.1 节中的分屏规则,将任务放入与子屏幕 D k 绑定的子线程 T k 的就

绪队列 Q k 中.每个消费者子线程 T k 每次从自身的就绪队列 Q k 中弹出不多于 M 个任务,放入自身的运行队列 q k
中,再根据运行队列 q k 中各个任务的内容逐个完成矩形填充的绘制工作.
3.2.4 就绪和运行双队列
与传统的生产者消费者模型不同,如图 6(b)所示,并行帧缓存设备算法中的每个消费者子线程 T k (1≤k≤
S x ⋅S y )都有两个分离的队列:就绪队列 Q k 和运行队列 q k ,分别存放等待绘制的任务和正在绘制的任务.这样,当生
产者线程独占就绪队列 Q k 并向 Q k 中添加产品时,消费者线程仍然可以独占运行队列 q k 来消费产品,而不会产
生互斥竞争;反之亦然.另一方面,消费者每次最多从就绪队列 Q k 中弹出 M 个任务到运行队列 q k ,相比每次仅弹
出 1 个任务就进行处理而言,也减少了消费者互斥访问就绪队列 Q k 的频率,降低了与生产者之间发生私有任务
队列访问冲突的概率.

3.3 主子线程负载均衡
在经典的生产者消费者模型中,当有限产品缓冲区满时,生产者都是处于空闲等待状态,等待消费者消耗缓