消息队列的设计与实现
1. 简介
消息驱动机制是 GUI 系统的基础,消息驱动的底层设施之一是消息队列,它是整个 GUI 系统运转中
枢。本文介绍了一个基于环形队列的消息队列实现方法。
2. 环形队列
环形队列是一种首尾相连的队列数据结构,遵循先进先出原则,如下图所示:
在环形队列中用一组连续地址的存储单元依次存放从列头到列尾的元素,通过两个指针 read_pos 和
write_pos 分别指向读取位置和写入位置。初始化队列时,令 read_pos = write_pos = 0,每当写
入 一个新元素时 , write_pos 加 1 ;每 当 读 取 一 个元 素 时 , read_pos 加 1. 若 队 列 已 满, 则
(write_pos + 1)%QUEUE_SIZE = read_pos,不能再往队列中写入数据;若队列为空,则
write_pos = read_pos,不能再从队列中读取数据。
鉴于多个线程同时访问环形队列,需要考虑线程之间的互斥和同步问题,采用锁控制多个线程互斥访
问环形队列,使用信号量控制线程之间的同步。
一段时间内只能有一个线程获得锁,当它持有锁时,其它线程要访问环形队列必须等待,直到前者释
放锁。由此,锁可以保证多个线程互斥的访问环形队列。
线程从队列读数据前首先判断信号量是否大于 1,若是,则从队列读数据;否则,进入等待状态,直
到信号量大于 1 为止;线程往队列写入一个数据后,会将信号量加 1,若有线程等待,则会被唤醒。
由此,信号量实现了多线程同步访问环形队列。
3. 流程图
下图是环形缓冲区的初始化、读数据、写数据的主要流程:
评论1
最新资源