【深度长文】聊聊神奇的无锁队列

// 鱼鹰*公***众**号：鱼鹰谈单片机，uint16_t queue[10000]; // 队列，0~9999，共 10000 uint16_t in;uint16_t out;
int get(void *parameter){ if(in == out) { rt_kprintf("当前没有顾客等待服务\n"); return -1; // 没有顾客在排队 }  rt_kprintf("请编号：【%04u】 到柜台办理服务\n",queue[out]); // 自加 1 ，但因为数组只有 10000 大小，所以需要让 out 在 0~9999 之间进行循环 out = (out + 1) % 10000;
 return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample);

int put(void){ if((in + 1) % 10000 == out) { // 因为 in 和 out 值相等时，可能为空和满的，无法判断哪种情况 // 所以为了避免这种情况，总是空一个位置，这样满的时候 in 和 out 的值就不一样 rt_kprintf("现在排队人数太多，请下次尝试\n"); return -1; // 队列满 } // 把当前的编号存入数组中进行排队 rt_kprintf("您当前领取的编号为 %04u\n",in);  queue[in] = in;  // 自加 1 ，但因为数组只有 10000 大小，所以需要让 in 在 0~9999 之间进行循环 in = (in + 1) % 10000;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 测试代码 V1.0// 鱼鹰*公***众**号：鱼鹰谈单片机，#define BUFF_SIZE 100uint16_t queue[BUFF_SIZE]; // 队列，0~99，共 100 uint16_t in;uint16_t out;uint16_t counter; // 记录
int get(void *parameter){ if(in == out) { rt_kprintf("当前没有顾客等待服务\n"); return -1; // 没有顾客在排队 }  rt_kprintf("请编号：【%04u】 到柜台办理服务\n",queue[out]); // 自加 1 ，但因为数组只有 100 大小，所以需要让 out 在 0~99 之间进行循环 out = (out + 1) % BUFF_SIZE;
 return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample);

int put(void){ if((in + 1) % BUFF_SIZE == out) { // 因为 in 和 out 值相等时，可能为空和满的，无法判断哪种情况 // 所以为了避免这种情况，总是空一个位置，这样满的时候 in 和 out 的值就不一样 rt_kprintf("现在排队人数太多，请下次尝试\n"); return -1; // 队列满 } // 把当前的编号存入数组中进行排队 rt_kprintf("您当前领取的编号为 %04u\n",counter);  queue[in] = counter;  counter = (counter + 1) % 10000; // 限制它的大小，不可超过四位数 // 自加 1 ，但因为数组只有 100 大小，所以需要让 in 在 0~99 之间进行循环 in = (in + 1) % BUFF_SIZE;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 测试代码 V1.5// 鱼鹰*公***众**号：鱼鹰谈单片机#define BUFF_SIZE 7
typedef struct { uint16_t queue[BUFF_SIZE]; // 队列，0~99，共 100  uint16_t in; uint16_t out; uint16_t used;}fifo_def; // 把队列相关的变量整合在一块，方便使用
uint16_t counter; // 记录
fifo_def fifo;
int get(void *parameter){ if(fifo.used == 0) { rt_kprintf("当前没有顾客等待服务\n"); return -1; // 没有顾客在排队 }  rt_kprintf("请编号：【%04u】 到柜台办理服务\n",fifo.queue[fifo.out]); // 自加 1 ，但因为数组只有 100 大小，所以需要让 out 在 0~99 之间进行循环 fifo.out = (fifo.out + 1) % BUFF_SIZE;  fifo.used--;  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 导出到命令行中使用
int put(void){ if(fifo.used >= BUFF_SIZE) { // 因为 in 和 out 值相等时，可能为空和满的，无法判断哪种情况 // 所以为了避免这种情况，总是空一个位置，这样满的时候 in 和 out 的值就不一样 rt_kprintf("现在排队人数太多，请下次尝试\n"); return -1; // 队列满 } // 把当前的编号存入数组中进行排队 rt_kprintf("您当前领取的编号为 %04u\n",counter);  fifo.queue[fifo.in] = counter;  counter = (counter + 1) % 10000; // 限制它的大小，不可超过四位数 // 自加 1 ，但因为数组只有 100 大小，所以需要让 in 在 0~99 之间进行循环 fifo.in = (fifo.in + 1) % BUFF_SIZE;   fifo.used++;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 测试代码 V2.0// 鱼鹰*公***众**号：鱼鹰谈单片机#define BUFF_SIZE 8 // 文章说的是 7，但是这是不能用的，只能为 2 的幂次方
typedef struct { uint32_t in; // 注意，这里是 32 位 uint32_t out; // 注意，这里是 32 位 uint8_t *queue; // 这里不再指定大小，而是根据实际情况设置缓存大小}fifo_def; // 把队列相关的变量整合在一块，方便使用
uint8_t counter; // 记录人数，也是发放的编号，因为队列类型变了，所以这里也改成 uint8_tuint8_t fifo_buff[BUFF_SIZE];
fifo_def fifo = {0,0,fifo_buff}; // 为了简化初始化过程，直接定义时初始化
int get(void *parameter){ if(fifo.in - fifo.out == 0) { // 也可以写成 fifo.in == fifo.out，效率或许会高一些 rt_kprintf("当前没有顾客等待服务\n"); return -1; // 没有顾客在排队 }  rt_kprintf("请编号：【%04u】 到柜台办理服务\n",fifo.queue[fifo.out % BUFF_SIZE]);  fifo.out++; // 直接自加  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 导出到命令行中使用
int put(void){     if(BUFF_SIZE - fifo.in + fifo.out == 0) { rt_kprintf("现在排队人数太多，请下次尝试\n"); return -1; // 队列满 } // 把当前的编号存入数组中进行排队 rt_kprintf("您当前领取的编号为 %04u\n",counter);  fifo.queue[fifo.in % BUFF_SIZE] = counter; // 这里用 fifo.in % (BUFF_SIZE - 1) 效率会高一些 counter += 1; // 递增计数器 
 fifo.in++; // 直接自加
 return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

 if(BUFF_SIZE - (fifo.in - fifo.out) == 0) { rt_kprintf("现在排队人数太多，请下次尝试\n"); return -1; // 队列满 }  if(fifo.in - fifo.out == 0) { // 也可以写成 fifo.in == fifo.out，效率或许会高一些 rt_kprintf("当前没有顾客等待服务\n"); return -1; // 没有顾客在排队 }

fifo.in++; // 直接自加
 fifo.out++; // 直接自加

BUFF_SIZE - (fifo.in - fifo.out)

BUFF_SIZE - (fifo.in - fifo.out)
fifo.in++; // 直接自加
fifo.out++; // 直接自加

// 测试代码 V2.5// 鱼鹰*公***众**号：鱼鹰谈单片机#define BUFF_SIZE 8
typedef struct { uint32_t in; // 注意，这里是 32 位 uint32_t out; // 注意，这里是 32 位 uint32_t size; // 设置缓存大小 uint8_t *buffer; // 这里不再指定大小，而是根据实际情况设置缓存大小}fifo_def; // 把队列相关的变量整合在一块，方便使用
uint8_t counter; // 记录人数，也是发放的编号，因为队列类型变了，所以这里也改成 uint8_tuint8_t fifo_buff[BUFF_SIZE];
fifo_def fifo = {0,0,BUFF_SIZE,fifo_buff}; // 为了简化初始化过程，直接定义时初始化
void init(fifo_def *pfifo,uint8_t *buff,uint32_t size){ if(size == 0 || (size & (size - 1))) // 2 的 幂次方 { retern; }  pfifo->in = 0 pfifo->out = 0; pfifo->size = size; pfifo->buffer = buff; }
int get(void *parameter){ fifo_def *pfifo = &fifo; // 这里直接使用全局变量，因为命令行不方便传参 uint32_t len = 2; // 这里假设一次获取 2 个字节数据  uint8_t buffer[2]; // 将队列中的数据提取到这个缓存中   uint32_t l;
 len = min(len, pfifo->in - pfifo->out);   /* first get the data from fifo->out until the end of the buffer */  l = min(len, pfifo->size - (pfifo->out & (pfifo->size - 1)));  memcpy(buffer, pfifo->buffer + (pfifo->out & (pfifo->size - 1)), l);   /* then get the rest (if any) from the beginning of the buffer */  memcpy(buffer + l, pfifo->buffer, len - l);   pfifo->out += len;  if(len) // 为了判断是否写入数据，加入调试信息 { for(int i = 0; i < len; i++) { rt_kprintf("请编号：【%04u】 到柜台办理服务\n",buffer[i]); }  } else { rt_kprintf("当前没有顾客等待服务\n"); }  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 导出到命令行中使用
int put(void){  fifo_def *pfifo = &fifo; // 这里直接使用全局变量，因为命令行不方便传参 uint32_t len = 1; // 这里假设一次写入 1 个字节数据    uint32_t l;          uint8_t buffer[1] = {counter}; // 存入编号，即将写入到队列中  len = min(len, pfifo->size - pfifo->in + pfifo->out);   /* first put the data starting from pfifo->in to buffer end */  l = min(len, pfifo->size - (pfifo->in & (pfifo->size - 1)));  memcpy(pfifo->buffer + (pfifo->in & (pfifo->size - 1)), buffer, l);   /* then put the rest (if any) at the beginning of the buffer */  memcpy(pfifo->buffer, buffer + l, len - l);   pfifo->in += len;  if(len) // 为了判断是否写入数据，加入调试信息 { rt_kprintf("您当前领取的编号为 %04u\n",buffer[0]); } else { rt_kprintf("当前没有顾客等待服务\n"); }  counter++;// 写完自加，不属于无锁队列内容
 return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

len = min(len, pfifo->in - pfifo->out);      /* first get the data from fifo->out until the end of the buffer */ l = min(len, pfifo->size - (pfifo->out & (pfifo->size - 1))); memcpy(buffer, pfifo->buffer + (pfifo->out & (pfifo->size - 1)), l);     /* then get the rest (if any) from the beginning of the buffer */ memcpy(buffer + l, pfifo->buffer, len - l);            

#define min(x,y) ((x) < (y) ? (x) : (y))

len = len < in - out ? len : in - out