目录
概述
代码结构
1. 头文件解析 (msgqueue.h)
2. 实现文件解析 (msgqueue.c)
核心功能解析
2.1 创建队列 (msgqueue_create)
2.2 放入消息 (msgqueue_put)
2.3 获取消息 (msgqueue_get)
2.4 交换队列 (__msgqueue_swap)
2.5 阻塞与非阻塞模式
2.6 销毁队列 (msgqueue_destroy)
3. 测试程序解析 (main_msgqueue.cpp)
关键点解析
4. 工作机制详解
4.1 Put队列和Get队列的分离
4.2 队列为空时的阻塞与交换
4.3 生产者与消费者的碰撞处理
4.4 阻塞与非阻塞模式
5. 示例程序运行流程
6. 运行示例
总结
高性能编程:无锁队列概念https://blog.csdn.net/weixin_43925427/article/details/142203825?sharetype=blogdetail&sharerId=142203825&sharerefer=PC&sharesource=weixin_43925427&sharefrom=from_linkMsgQueue
在多生产者多消费者(MPMC)场景下的实现原理及其工作机制。
概述
msgqueue
是一个用于多生产者多消费者场景的消息队列实现。它将队列分为put队列和get队列,分别用于生产者和消费者操作。其主要逻辑如下:
- Put队列:生产者线程将消息入队到put队列。
- Get队列:消费者线程从get队列中出队消息。
- 交换机制:当get队列为空时,尝试与put队列进行交换,使消费者能够获取新的消息。
- 阻塞与非阻塞:根据队列的状态和配置,决定是否阻塞消费者或生产者线程。
代码结构
代码分为三个主要部分:
- 头文件 (
msgqueue.h
):定义了消息队列的接口和数据结构。 - 实现文件 (
msgqueue.c
):实现了消息队列的功能。 - 测试程序 (
main_msgqueue.cpp
):演示了如何使用消息队列。
1. 头文件解析 (msgqueue.h
)
#ifndef _MSGQUEUE_H_
#define _MSGQUEUE_H_
#include <stddef.h>
typedef struct __msgqueue msgqueue_t;
#ifdef __cplusplus
extern "C"
{
#endif
/* 消息队列的接口函数 */
msgqueue_t *msgqueue_create(size_t maxlen, int linkoff);
void msgqueue_put(void *msg, msgqueue_t *queue);
void *msgqueue_get(msgqueue_t *queue);
void msgqueue_set_nonblock(msgqueue_t *queue);
void msgqueue_set_block(msgqueue_t *queue);
void msgqueue_destroy(msgqueue_t *queue);
#ifdef __cplusplus
}
#endif
#endif
msgqueue_create
:创建一个消息队列,maxlen
表示队列的最大长度,linkoff
表示消息结构中用于链接下一个消息的偏移量。msgqueue_put
:生产者将消息放入队列。msgqueue_get
:消费者从队列中获取消息。msgqueue_set_nonblock
/msgqueue_set_block
:设置队列为非阻塞或阻塞模式。msgqueue_destroy
:销毁消息队列,释放资源。
2. 实现文件解析 (msgqueue.c
)
#include <errno.h>
#include <stdlib.h>
#include <pthread.h>
#include "msgqueue.h"
/* 消息队列的内部结构 */
struct __msgqueue
{
size_t msg_max; // 队列的最大长度
size_t msg_cnt; // 当前消息数量
int linkoff; // 链接偏移量
int nonblock; // 是否为非阻塞模式
void *head1; // get队列的第一个头节点
void *head2; // put队列的第一个头节点
void **get_head; // 指向get队列头指针的指针
void **put_head; // 指向put队列头指针的指针
void **put_tail; // 指向put队列尾指针的指针
pthread_mutex_t get_mutex; // get队列的互斥锁
pthread_mutex_t put_mutex; // put队列的互斥锁
pthread_cond_t get_cond; // get队列的条件变量
pthread_cond_t put_cond; // put队列的条件变量
};
核心功能解析
2.1 创建队列 (msgqueue_create
)
msgqueue_t *msgqueue_create(size_t maxlen, int linkoff)
{
msgqueue_t *queue = (msgqueue_t *)malloc(sizeof(msgqueue_t));
int ret;
if (!queue)
return NULL;
ret = pthread_mutex_init(&queue->get_mutex, NULL);
if (ret == 0)
{
ret = pthread_mutex_init(&queue->put_mutex, NULL);
if (ret == 0)
{
ret = pthread_cond_init(&queue->get_cond, NULL);
if (ret == 0)
{
ret = pthread_cond_init(&queue->put_cond, NULL);
if (ret == 0)
{
queue->msg_max = maxlen;
queue->linkoff = linkoff;
queue->head1 = NULL;
queue->head2 = NULL;
queue->get_head = &queue->head1;
queue->put_head = &queue->head2;
queue->put_tail = &queue->head2;
queue->msg_cnt = 0;
queue->nonblock = 0;
return queue;
}
pthread_cond_destroy(&queue->get_cond);
}
pthread_mutex_destroy(&queue->put_mutex);
}
pthread_mutex_destroy(&queue->get_mutex);
}
errno = ret;
free(queue);
return NULL;
}
- 初始化互斥锁和条件变量:为
get
和put
操作分别初始化互斥锁和条件变量。 - 初始化队列头指针:
get_head
指向head1
,put_head
和put_tail
指向head2
,实现put
和get
队列的分离。
2.2 放入消息 (msgqueue_put
)
void msgqueue_put(void *msg, msgqueue_t *queue)
{
void **link = (void **)((char *)msg + queue->linkoff);
*link = NULL;
pthread_mutex_lock(&queue->put_mutex);
while (queue->msg_cnt > queue->msg_max - 1 && !queue->nonblock)
pthread_cond_wait(&queue->put_cond, &queue->put_mutex);
*queue->put_tail = link;
queue->put_tail = link;
queue->msg_cnt++;
pthread_mutex_unlock(&queue->put_mutex);
pthread_cond_signal(&queue->get_cond);
}
- 计算消息的链接指针:根据
linkoff
偏移量获取消息结构中用于链接下一个消息的指针。 - 设置链接指针为空:表示当前消息是链表的末尾。
- 锁定put队列:确保多个生产者线程安全地操作put队列。
- 阻塞条件:如果当前消息数量超过
msg_max - 1
且不是非阻塞模式,生产者线程将被阻塞,直到有空间可用。 - 入队操作:
- 将当前消息链接到put队列的尾部。
- 更新put队列的尾指针。
- 增加消息计数。
- 解锁put队列:释放锁,允许其他生产者继续入队。
- 通知消费者:通过条件变量
get_cond
唤醒可能被阻塞的消费者线程。
2.3 获取消息 (msgqueue_get
)
void *msgqueue_get(msgqueue_t *queue)
{
void *msg;
pthread_mutex_lock(&queue->get_mutex);
if (*queue->get_head || __msgqueue_swap(queue) > 0)
{
msg = (char *)*queue->get_head - queue->linkoff;
*queue->get_head = *(void **)*queue->get_head;
}
else
msg = NULL;
pthread_mutex_unlock(&queue->get_mutex);
return msg;
}
- 锁定get队列:确保多个消费者线程安全地操作get队列。
- 判断get队列是否有消息:
- 如果
*get_head
不为空,直接获取消息。 - 否则,调用
__msgqueue_swap
尝试将put队列和get队列交换。
- 如果
- 获取消息:
- 计算消息的实际地址(通过减去
linkoff
偏移量)。 - 更新get队列的头指针,指向下一个消息。
- 计算消息的实际地址(通过减去
- 解锁get队列:释放锁,允许其他消费者继续出队。
- 返回消息:如果队列为空,返回
NULL
。
2.4 交换队列 (__msgqueue_swap
)
static size_t __msgqueue_swap(msgqueue_t *queue)
{
void **get_head = queue->get_head;
size_t cnt;
queue->get_head = queue->put_head;
pthread_mutex_lock(&queue->put_mutex);
while (queue->msg_cnt == 0 && !queue->nonblock)
pthread_cond_wait(&queue->get_cond, &queue->put_mutex);
cnt = queue->msg_cnt;
if (cnt > queue->msg_max - 1)
pthread_cond_broadcast(&queue->put_cond);
queue->put_head = get_head;
queue->put_tail = get_head;
queue->msg_cnt = 0;
pthread_mutex_unlock(&queue->put_mutex);
return cnt;
}
- 交换get_head与put_head:将put队列的头指针赋值给get队列,使消费者能够获取新的消息。
- 锁定put队列:在交换过程中,确保生产者不会同时操作put队列。
- 阻塞条件:如果put队列为空且不是非阻塞模式,消费者线程将被阻塞,直到有新的消息入队。
- 获取消息计数:记录当前put队列中的消息数量。
- 条件广播:如果消息数量超过
msg_max - 1
,通过put_cond
唤醒被阻塞的生产者线程。 - 重置put队列:
- 将put队列的头尾指针指向之前的get_head。
- 重置消息计数。
- 解锁put队列:允许生产者线程继续入队。
- 返回消息计数:用于判断是否有新消息可供获取。
2.5 阻塞与非阻塞模式
void msgqueue_set_nonblock(msgqueue_t *queue)
{
queue->nonblock = 1;
pthread_mutex_lock(&queue->put_mutex);
pthread_cond_signal(&queue->get_cond);
pthread_cond_broadcast(&queue->put_cond);
pthread_mutex_unlock(&queue->put_mutex);
}
void msgqueue_set_block(msgqueue_t *queue)
{
queue->nonblock = 0;
}
msgqueue_set_nonblock
:- 设置队列为非阻塞模式。
- 通过条件变量唤醒所有被阻塞的生产者和消费者线程,防止死锁。
msgqueue_set_block
:- 设置队列为阻塞模式。
2.6 销毁队列 (msgqueue_destroy
)
void msgqueue_destroy(msgqueue_t *queue)
{
pthread_cond_destroy(&queue->put_cond);
pthread_cond_destroy(&queue->get_cond);
pthread_mutex_destroy(&queue->put_mutex);
pthread_mutex_destroy(&queue->get_mutex);
free(queue);
}
- 销毁互斥锁和条件变量:释放资源。
- 释放队列内存:销毁队列对象。
3. 测试程序解析 (main_msgqueue.cpp
)
#include "msgqueue.h"
#include <cstddef>
#include <thread>
#include <iostream>
// 消息结构体
struct Count {
Count(int _v) : v(_v), next(nullptr) {}
int v;
Count *next;
};
int main() {
// linkoff: Count结构体中用于链接下一个节点的指针的偏移量
msgqueue_t* queue = msgqueue_create(1024, sizeof(int));
// 生产者线程1
std::thread pd1([&]() {
msgqueue_put(new Count(100), queue);
msgqueue_put(new Count(200), queue);
msgqueue_put(new Count(300), queue);
msgqueue_put(new Count(400), queue);
});
// 生产者线程2
std::thread pd2([&]() {
msgqueue_put(new Count(500), queue);
msgqueue_put(new Count(600), queue);
msgqueue_put(new Count(700), queue);
msgqueue_put(new Count(800), queue);
});
// 消费者线程1
std::thread cs1([&]() {
Count *cnt;
while((cnt = (Count *)msgqueue_get(queue)) != NULL) {
std::cout << std::this_thread::get_id() << " : pop " << cnt->v << std::endl;
delete cnt;
}
});
// 消费者线程2
std::thread cs2([&]() {
Count *cnt;
while((cnt = (Count *)msgqueue_get(queue)) != NULL) {
std::cout << std::this_thread::get_id() << " : pop " << cnt->v << std::endl;
delete cnt;
}
});
// 等待所有线程完成
pd1.join();
pd2.join();
cs1.join();
cs2.join();
// 销毁队列
msgqueue_destroy(queue);
return 0;
}
关键点解析
-
消息结构体
Count
:- 包含一个整数值
v
和一个指针next
,用于链接下一个消息。 linkoff
设置为sizeof(int)
,表示next
指针在结构体中的偏移量。
- 包含一个整数值
-
创建消息队列:
msgqueue_t* queue = msgqueue_create(1024, sizeof(int));
-
maxlen
设置为1024
,表示队列的最大长度。 -
linkoff
设置为sizeof(int)
,表示消息结构体中next
指针的偏移量。
-
-
生产者线程:
-
两个生产者线程
pd1
和pd2
,分别放入四个不同的Count
消息。
-
- 消费者线程:
- 两个消费者线程
cs1
和cs2
,不断从队列中获取消息并打印,然后删除消息。 - 当队列为空且所有生产者已完成入队,
msgqueue_get
返回NULL
,线程结束。
- 两个消费者线程
- 销毁队列:
msgqueue_destroy(queue);
4. 工作机制详解
msgqueue
的工作机制可以概括为以下几个步骤:
4.1 Put队列和Get队列的分离
-
Put队列:
- 由生产者线程操作。
- 通过
put_head
和put_tail
指针管理,生产者将消息链接到put队列的尾部。 - 使用
put_mutex
和put_cond
确保线程安全和同步。
-
Get队列:
- 由消费者线程操作。
- 通过
get_head
指针管理,消费者从get队列的头部获取消息。 - 使用
get_mutex
和get_cond
确保线程安全和同步。
4.2 队列为空时的阻塞与交换
-
当Put队列和Get队列都为空时:
- 消费者线程会被阻塞,等待生产者线程入队新消息。
- 这是通过
__msgqueue_swap
函数中的pthread_cond_wait
实现的。
-
当Get队列为空但Put队列有消息时:
- 消费者线程尝试将put队列与get队列交换,使消费者能够获取新的消息。
- 这是通过
__msgqueue_swap
函数实现的,锁定put队列并交换头指针。 - 交换过程中,生产者和消费者可能会发生碰撞,即生产者正在入队时,消费者尝试交换队列。
- 其他情况下,生产者仅与生产者竞争put队列,消费者仅与消费者竞争get队列,避免了交叉竞争。
4.3 生产者与消费者的碰撞处理
-
碰撞情形:
- 当一个消费者尝试交换队列时,可能会与多个生产者线程同时操作put队列。
- 为了保证线程安全,
__msgqueue_swap
在交换过程中锁定了put队列的互斥锁,确保只有一个消费者能够成功交换。
-
非碰撞情形:
- 生产者仅操作put队列,锁定
put_mutex
,避免与其他生产者竞争。 - 消费者仅操作get队列,锁定
get_mutex
,避免与其他消费者竞争。
- 生产者仅操作put队列,锁定
4.4 阻塞与非阻塞模式
-
阻塞模式:
- 当队列满时,生产者线程会被阻塞,等待消费者线程出队腾出空间。
- 当队列空时,消费者线程会被阻塞,等待生产者线程入队新消息。
-
非阻塞模式:
- 通过调用
msgqueue_set_nonblock
将队列设置为非阻塞模式。 - 在非阻塞模式下,生产者和消费者线程不会因为队列满或空而被阻塞,而是立即返回。
- 通过调用
5. 示例程序运行流程
-
创建队列:
- 队列初始为空,
head1
和head2
均为NULL
。 get_head
指向head1
,put_head
和put_tail
指向head2
。
- 队列初始为空,
-
生产者入队:
pd1
和pd2
分别向put队列中入队4个消息。- 每次
msgqueue_put
操作:- 计算消息的链接指针。
- 锁定
put_mutex
。 - 检查队列是否已满,必要时阻塞。
- 将消息链接到put队列的尾部。
- 更新尾指针和消息计数。
- 解锁
put_mutex
并通知消费者。
-
消费者出队:
cs1
和cs2
不断调用msgqueue_get
获取消息。- 每次
msgqueue_get
操作:- 锁定
get_mutex
。 - 检查get队列是否有消息,若无则尝试交换。
- 获取消息并更新get队列的头指针。
- 解锁
get_mutex
并返回消息。 - 打印消息内容并删除消息对象。
- 锁定
-
交换队列:
- 当get队列为空且put队列有消息时,消费者线程调用
__msgqueue_swap
将put队列与get队列交换。 - 这样,消费者可以从新的get队列中获取到生产者入队的消息。
- 当get队列为空且put队列有消息时,消费者线程调用
-
线程同步:
- 生产者和消费者通过互斥锁和条件变量确保线程安全和同步。
- 队列的阻塞与非阻塞模式根据具体需求进行配置。
6. 运行示例
输出如下:
140353163797760 : pop 100
140353155405056 : pop 500
140353163797760 : pop 200
140353155405056 : pop 600
140353163797760 : pop 300
140353155405056 : pop 700
140353163797760 : pop 400
140353155405056 : pop 800
- 每一行显示了哪个消费者线程(通过线程ID标识)获取了哪个消息。
- 消费者线程交替获取生产者线程入队的消息,确保了队列的先进先出(FIFO)特性。
总结
msgqueue
通过将队列分为put和get两部分,并使用互斥锁和条件变量实现了多生产者多消费者的线程安全。然而,它仍依赖于传统的锁机制,而非真正的无锁操作。如果对性能有更高的要求,建议探索无锁队列的实现方法,如基于原子操作的Michael & Scott队列。此外,结合内存管理优化和缓存友好性设计,可以进一步提升队列的性能和效率。