【深度長(zhǎng)文】聊聊神奇的無(wú)鎖隊(duì)列

// 魚(yú)鷹*公***眾**號(hào)：魚(yú)鷹談單片機(jī)，uint16_t queue[10000]; // 隊(duì)列，0~9999，共 10000 uint16_t in;uint16_t out;
int get(void *parameter){ if(in == out) { rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); return -1; // 沒(méi)有顧客在排隊(duì) }  rt_kprintf("請(qǐng)編號(hào)：【%04u】 到柜臺(tái)辦理服務(wù)\n",queue[out]); // 自加 1 ，但因?yàn)閿?shù)組只有 10000 大小，所以需要讓 out 在 0~9999 之間進(jìn)行循環(huán) out = (out + 1) % 10000;
 return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample);

int put(void){ if((in + 1) % 10000 == out) { // 因?yàn)?in 和 out 值相等時(shí)，可能為空和滿的，無(wú)法判斷哪種情況 // 所以為了避免這種情況，總是空一個(gè)位置，這樣滿的時(shí)候 in 和 out 的值就不一樣 rt_kprintf("現(xiàn)在排隊(duì)人數(shù)太多，請(qǐng)下次嘗試\n"); return -1; // 隊(duì)列滿 } // 把當(dāng)前的編號(hào)存入數(shù)組中進(jìn)行排隊(duì) rt_kprintf("您當(dāng)前領(lǐng)取的編號(hào)為 %04u\n",in);  queue[in] = in;  // 自加 1 ，但因?yàn)閿?shù)組只有 10000 大小，所以需要讓 in 在 0~9999 之間進(jìn)行循環(huán) in = (in + 1) % 10000;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 測(cè)試代碼 V1.0// 魚(yú)鷹*公***眾**號(hào)：魚(yú)鷹談單片機(jī)，#define BUFF_SIZE 100uint16_t queue[BUFF_SIZE]; // 隊(duì)列，0~99，共 100 uint16_t in;uint16_t out;uint16_t counter; // 記錄
int get(void *parameter){ if(in == out) { rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); return -1; // 沒(méi)有顧客在排隊(duì) }  rt_kprintf("請(qǐng)編號(hào)：【%04u】 到柜臺(tái)辦理服務(wù)\n",queue[out]); // 自加 1 ，但因?yàn)閿?shù)組只有 100 大小，所以需要讓 out 在 0~99 之間進(jìn)行循環(huán) 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) { // 因?yàn)?in 和 out 值相等時(shí)，可能為空和滿的，無(wú)法判斷哪種情況 // 所以為了避免這種情況，總是空一個(gè)位置，這樣滿的時(shí)候 in 和 out 的值就不一樣 rt_kprintf("現(xiàn)在排隊(duì)人數(shù)太多，請(qǐng)下次嘗試\n"); return -1; // 隊(duì)列滿 } // 把當(dāng)前的編號(hào)存入數(shù)組中進(jìn)行排隊(duì) rt_kprintf("您當(dāng)前領(lǐng)取的編號(hào)為 %04u\n",counter);  queue[in] = counter;  counter = (counter + 1) % 10000; // 限制它的大小，不可超過(guò)四位數(shù) // 自加 1 ，但因?yàn)閿?shù)組只有 100 大小，所以需要讓 in 在 0~99 之間進(jìn)行循環(huán) in = (in + 1) % BUFF_SIZE;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 測(cè)試代碼 V1.5// 魚(yú)鷹*公***眾**號(hào)：魚(yú)鷹談單片機(jī)#define BUFF_SIZE 7
typedef struct { uint16_t queue[BUFF_SIZE]; // 隊(duì)列，0~99，共 100  uint16_t in; uint16_t out; uint16_t used;}fifo_def; // 把隊(duì)列相關(guān)的變量整合在一塊，方便使用
uint16_t counter; // 記錄
fifo_def fifo;
int get(void *parameter){ if(fifo.used == 0) { rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); return -1; // 沒(méi)有顧客在排隊(duì) }  rt_kprintf("請(qǐng)編號(hào)：【%04u】 到柜臺(tái)辦理服務(wù)\n",fifo.queue[fifo.out]); // 自加 1 ，但因?yàn)閿?shù)組只有 100 大小，所以需要讓 out 在 0~99 之間進(jìn)行循環(huán) fifo.out = (fifo.out + 1) % BUFF_SIZE;  fifo.used--;  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 導(dǎo)出到命令行中使用
int put(void){ if(fifo.used >= BUFF_SIZE) { // 因?yàn)?in 和 out 值相等時(shí)，可能為空和滿的，無(wú)法判斷哪種情況 // 所以為了避免這種情況，總是空一個(gè)位置，這樣滿的時(shí)候 in 和 out 的值就不一樣 rt_kprintf("現(xiàn)在排隊(duì)人數(shù)太多，請(qǐng)下次嘗試\n"); return -1; // 隊(duì)列滿 } // 把當(dāng)前的編號(hào)存入數(shù)組中進(jìn)行排隊(duì) rt_kprintf("您當(dāng)前領(lǐng)取的編號(hào)為 %04u\n",counter);  fifo.queue[fifo.in] = counter;  counter = (counter + 1) % 10000; // 限制它的大小，不可超過(guò)四位數(shù) // 自加 1 ，但因?yàn)閿?shù)組只有 100 大小，所以需要讓 in 在 0~99 之間進(jìn)行循環(huán) fifo.in = (fifo.in + 1) % BUFF_SIZE;   fifo.used++;  return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

// 測(cè)試代碼 V2.0// 魚(yú)鷹*公***眾**號(hào)：魚(yú)鷹談單片機(jī)#define BUFF_SIZE 8 // 文章說(shuō)的是 7，但是這是不能用的，只能為 2 的冪次方
typedef struct { uint32_t in; // 注意，這里是 32 位 uint32_t out; // 注意，這里是 32 位 uint8_t *queue; // 這里不再指定大小，而是根據(jù)實(shí)際情況設(shè)置緩存大小}fifo_def; // 把隊(duì)列相關(guān)的變量整合在一塊，方便使用
uint8_t counter; // 記錄人數(shù)，也是發(fā)放的編號(hào)，因?yàn)殛?duì)列類(lèi)型變了，所以這里也改成 uint8_tuint8_t fifo_buff[BUFF_SIZE];
fifo_def fifo = {0,0,fifo_buff}; // 為了簡(jiǎn)化初始化過(guò)程，直接定義時(shí)初始化
int get(void *parameter){ if(fifo.in - fifo.out == 0) { // 也可以寫(xiě)成 fifo.in == fifo.out，效率或許會(huì)高一些 rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); return -1; // 沒(méi)有顧客在排隊(duì) }  rt_kprintf("請(qǐng)編號(hào)：【%04u】 到柜臺(tái)辦理服務(wù)\n",fifo.queue[fifo.out % BUFF_SIZE]);  fifo.out++; // 直接自加  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 導(dǎo)出到命令行中使用
int put(void){     if(BUFF_SIZE - fifo.in + fifo.out == 0) { rt_kprintf("現(xiàn)在排隊(duì)人數(shù)太多，請(qǐng)下次嘗試\n"); return -1; // 隊(duì)列滿 } // 把當(dāng)前的編號(hào)存入數(shù)組中進(jìn)行排隊(duì) rt_kprintf("您當(dāng)前領(lǐng)取的編號(hào)為 %04u\n",counter);  fifo.queue[fifo.in % BUFF_SIZE] = counter; // 這里用 fifo.in % (BUFF_SIZE - 1) 效率會(huì)高一些 counter += 1; // 遞增計(jì)數(shù)器 
 fifo.in++; // 直接自加
 return 0;}MSH_CMD_EXPORT(put, RT-Thread first led sample);

 if(BUFF_SIZE - (fifo.in - fifo.out) == 0) { rt_kprintf("現(xiàn)在排隊(duì)人數(shù)太多，請(qǐng)下次嘗試\n"); return -1; // 隊(duì)列滿 }  if(fifo.in - fifo.out == 0) { // 也可以寫(xiě)成 fifo.in == fifo.out，效率或許會(huì)高一些 rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); return -1; // 沒(méi)有顧客在排隊(duì) }

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

BUFF_SIZE - (fifo.in - fifo.out)

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

// 測(cè)試代碼 V2.5// 魚(yú)鷹*公***眾**號(hào)：魚(yú)鷹談單片機(jī)#define BUFF_SIZE 8
typedef struct { uint32_t in; // 注意，這里是 32 位 uint32_t out; // 注意，這里是 32 位 uint32_t size; // 設(shè)置緩存大小 uint8_t *buffer; // 這里不再指定大小，而是根據(jù)實(shí)際情況設(shè)置緩存大小}fifo_def; // 把隊(duì)列相關(guān)的變量整合在一塊，方便使用
uint8_t counter; // 記錄人數(shù)，也是發(fā)放的編號(hào)，因?yàn)殛?duì)列類(lèi)型變了，所以這里也改成 uint8_tuint8_t fifo_buff[BUFF_SIZE];
fifo_def fifo = {0,0,BUFF_SIZE,fifo_buff}; // 為了簡(jiǎn)化初始化過(guò)程，直接定義時(shí)初始化
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; // 這里直接使用全局變量，因?yàn)槊钚胁环奖銈鲄?/span> uint32_t len = 2; // 這里假設(shè)一次獲取 2 個(gè)字節(jié)數(shù)據(jù)  uint8_t buffer[2]; // 將隊(duì)列中的數(shù)據(jù)提取到這個(gè)緩存中   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) // 為了判斷是否寫(xiě)入數(shù)據(jù)，加入調(diào)試信息 { for(int i = 0; i < len; i++) { rt_kprintf("請(qǐng)編號(hào)：【%04u】 到柜臺(tái)辦理服務(wù)\n",buffer[i]); }  } else { rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); }  return 0; }MSH_CMD_EXPORT(get, RT-Thread first led sample); // 導(dǎo)出到命令行中使用
int put(void){  fifo_def *pfifo = &fifo; // 這里直接使用全局變量，因?yàn)槊钚胁环奖銈鲄?/span> uint32_t len = 1; // 這里假設(shè)一次寫(xiě)入 1 個(gè)字節(jié)數(shù)據(jù)    uint32_t l;          uint8_t buffer[1] = {counter}; // 存入編號(hào)，即將寫(xiě)入到隊(duì)列中  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) // 為了判斷是否寫(xiě)入數(shù)據(jù)，加入調(diào)試信息 { rt_kprintf("您當(dāng)前領(lǐng)取的編號(hào)為 %04u\n",buffer[0]); } else { rt_kprintf("當(dāng)前沒(méi)有顧客等待服務(wù)\n"); }  counter++;// 寫(xiě)完自加，不屬于無(wú)鎖隊(duì)列內(nèi)容
 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