{"id":5059,"date":"2021-02-06T19:49:25","date_gmt":"2021-02-06T11:49:25","guid":{"rendered":"https:\/\/damogame.cn\/wordpress\/?p=5059"},"modified":"2021-02-06T19:49:25","modified_gmt":"2021-02-06T11:49:25","slug":"%e6%b6%88%e6%81%af%e9%98%9f%e5%88%97%e4%bc%98%e5%8c%96-%e5%87%a0%e7%a7%8d%e5%9f%ba%e6%9c%ac%e5%ae%9e%e7%8e%b0","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/5059","title":{"rendered":"\u6d88\u606f\u961f\u5217\u4f18\u5316 — \u51e0\u79cd\u57fa\u672c\u5b9e\u73b0"},"content":{"rendered":"
\n
\u539f\u6587\u5730\u5740<\/a><\/div>\n<\/header>\n
\n
\n

 <\/p>\n

[\u6211\u7684blog\u539f\u5730\u5740\uff1a\u6d88\u606f\u961f\u5217\u4f18\u5316 — \u51e0\u79cd\u57fa\u672c\u5b9e\u73b0<\/a>\uff0c\u540e\u7eed\u4f1a\u6301\u7eed\u52aa\u529b\u540c\u6b65\u66f4\u65b0\u5230\u77e5\u4e4e\uff5e ]<\/p>\n

\n

\u542c\u8bf4\u4eca\u5929\u4e0d\u53d1blog\u5c31\u8981\u7b49\u56db\u5e74\u4e86\uff0c\u4e8e\u662f\u5360\u4e2a\u5751\u3002<\/p>\n

1. \u57fa\u672c\u5b9e\u73b0\u4e0e\u5bf9\u6bd4<\/h2>\n

\u8fd9\u4e24\u5468\u5199\u4e86\u4e00\u90e8\u5206\u5f88\u7b80\u5355\u7684\u5b9e\u73b0\uff0c\u9646\u7eed\u4e0a\u4f20\u5230\uff1a<\/p>\n

https:\/\/<\/span>github.com\/holmes1412\/q<\/span>ueue<\/span><\/a><\/p>\n

\u968f\u7740\u8fdb\u4e00\u6b65\u7684\u4e86\u89e3\uff0c\u73b0\u5728\u53ef\u4ee5\u5206\u522b\u5217\u4e00\u4e0b\u6211\u4eec\u8fd9\u6b21\u5173\u6ce8\u7684\u51e0\u79cd\u5b9e\u73b0\u7684\u5bf9\u6bd4\uff1a<\/p>\n

<\/figure>\n

\u53e6\u5916\u8bf4\u660e\uff1akfifo\u548cwork_stealing_queue\u662f\u65e0\u963b\u585e<\/b>\u7684\uff0c \u5e76\u4e14\u56e0\u4e3akfifo\u548cwork_stealing_queue\u7684\u57fa\u672c\u64cd\u4f5c\u90fd\u662f\u6ee1\u8db3\u5355\u751f\u4ea7\u8005\u5355\u6d88\u8d39\u8005<\/b>\uff0c\u6240\u4ee5\u8fd9\u91cc\u5bf9\u6bd4\u7684\u65f6\u5019\u8fd8\u662f\u6309\u7167\u7528\u4ed6\u4eec\u53bb\u5b9e\u73b0\u591a\u751f\u4ea7\u8005\u591a\u6d88\u8d39\u8005\u6765\u8ddf\u5176\u4ed6\u7684\u5b9e\u73b0\u76f8\u6bd4\u3002<\/p>\n

\u5176\u4e2d\u524d\u9762\u4e09\u79cd\u5b9e\u73b0\uff08\u5916\u52a0\u6700\u7b28\u7684\u5355\u9501\u961f\u5217\u9501\u5185\u5524\u9192\u7248\u672c\uff09\u4e5f\u7528\u6765\u5207\u4e86\u8fd9\u9053\u9898\uff1a<\/p>\n

https:\/\/<\/span>leetcode-cn.com\/problem<\/span>s\/design-bounded-blocking-queue\/<\/span><\/a><\/p>\n

<\/figure>\n

\u4ece\u6700\u65e9\u5230\u6700\u8fd1\u5206\u522b\u662f\u8fd9\u51e0\u7248\u961f\u5217\uff0c\u4e0d\u8fc7leetcode\u7684\u591a\u7ebf\u7a0b\u9898\u7684\u8017\u65f6\u662f\u975e\u5e38\u8bf4\u660e\u4e0d\u4e86\u95ee\u9898\u7684\uff0c\u6240\u4ee5\u81ea\u5df1\u5199\u4e86\u4e2ademo\uff0c\u4f46\u662f\u8fd9\u4e2a\u6d4b\u8bd5\u573a\u666f\u600e\u4e48\u624d\u6700\u80fd\u8bf4\u660e\u95ee\u9898\u662f\u6bd4\u8f83\u9700\u8981\u60f3\u60f3\u7684\uff0c\u800c\u4e14\u7531\u4e8eworkstealing\u8981\u6269\u5c55\u5230\u591a\u751f\u4ea7\u8005\u591a\u6d88\u8d39\u8005\u8fd8\u9700\u8981\u5c01\u88c5\u6d88\u8d39\u8005\u7ebf\u7a0b\u6c60\uff0c\u6240\u4ee5\u5269\u4e0b\u7684\u5de5\u4f5c\u90fd\u6253\u7b97\u653e\u5230\u4e0b\u4e00\u7bc7\u8bf4\u4e86\u3002<\/p>\n

2. CAS<\/h2>\n

\u8fd9\u91cc\u9009\u53d6linux\u5185\u6838\u7684kfifo.h<\/b>\u6765\u4e86\u89e3\u4e0b\uff0c\u5185\u6838\u4ee3\u7801\u5199\u5f97\u975e\u5e38\u6f02\u4eae\u3002kfifo\u662f\u4e00\u4e2a\u4f7f\u7528\u5faa\u73af\u6570\u7ec4<\/b>\u6765\u5b9e\u73b0\u7684first-in-first-out<\/b>\u961f\u5217\u7684\uff0c\u5728\u5355\u751f\u4ea7\u8005\u5355\u6d88\u8d39\u8005\u7684\u60c5\u51b5\u4e0b\uff0c\u53ef\u4ee5\u505a\u5230\u5f7b\u5e95\u65e0\u9501\u3002\u5982\u679c\u591a\u751f\u4ea7\u8005\u591a\u6d88\u8d39\u8005\uff0c\u53ef\u4ee5\u4f7f\u7528\u5e26spinlock<\/b>\u7684\u63a5\u53e3\u3002\u5148\u770b\u4e0b\u5355\u751f\u4ea7\u8005\u5355\u6d88\u8d39\u8005\u65e0\u9501\u7684\u539f\u7406\uff1a<\/p>\n

\n
struct<\/span> __kfifo<\/span> {<\/span>\r\n    unsigned<\/span> int<\/span>    in<\/span>;<\/span>\r\n    unsigned<\/span> int<\/span>    out<\/span>;<\/span>\r\n    unsigned<\/span> int<\/span>    mask<\/span>;<\/span>\r\n    unsigned<\/span> int<\/span>    esize<\/span>;<\/span>\r\n    void<\/span>           *<\/span>data<\/span>;<\/span>\r\n};<\/span>\r\n\r\n\/\/ \u57fa\u672c\u7684enqueue\u63a5\u53e3\r\n<\/span>extern<\/span> unsigned<\/span> int<\/span> __kfifo_in<\/span>(<\/span>struct<\/span> __kfifo<\/span> *<\/span>fifo<\/span>,<\/span> const<\/span> void<\/span> *<\/span>buf<\/span>,<\/span> unsigned<\/span> int<\/span> len<\/span>);<\/span>\r\n\r\n\/\/ \u57fa\u672c\u7684dequeue\u63a5\u53e3\r\n<\/span>extern<\/span> unsigned<\/span> int<\/span> __kfifo_out<\/span>(<\/span>struct<\/span> __kfifo<\/span> *<\/span>fifo<\/span>,<\/span> void<\/span> *<\/span>buf<\/span>,<\/span> unsigned<\/span> int<\/span> len<\/span>);<\/span>\r\n<\/code><\/pre>\n<\/div>\n
\u51e0\u4e2a\u8bf4\u660e\uff1a<\/p>\n
    \n
  1. \u961f\u5217\u5728\u521d\u59cb\u5316\u65f6\u4f1a\u8bb0\u5f55\u4e0bmask<\/b>\u4e3acapacity – 1<\/b>\uff0c\u8fd9\u662f\u7528\u4e8e\u5faa\u73af\u6570\u7ec4\u5bfb\u5740\u628a\u00a0pos % capcity<\/b>\u00a0\u8f6c\u6210\u00a0pos & (capacity – 1)<\/b>\uff1b<\/li>\n
  2. \u4e3a\u4e86\u5faa\u73af\u961f\u5217\u80fd\u591f\u5feb\u901f\u5bfb\u5740\uff0cpos\u4f7f\u7528\u4e86\u4e0a\u8ff0\u8f6c\u6362\uff0c\u56e0\u6b64capacity\u5fc5\u987b\u662f2\u7684\u5e42<\/b>\uff1b<\/li>\n
  3. in\u662f\u5165\u961f\u5217\u7684\u4f4d\u7f6e\uff0cout\u662f\u51fa\u961f\u5217\u7684\u4f4d\u7f6e\uff0c\u4e24\u4e2a\u503c\u4f1a\u4e00\u76f4\u52a0\u5230unsigned int\u6ea2\u51fa\u56de\u52300\u90fd\u662f\u6b63\u786e\u7684\uff1b<\/li>\n
  4. out()\u63a5\u53e3\u53ef\u4ee5\u770b\u5230\u5e26\u4e86\u4e2alen<\/b>\u53c2\u6570\uff0c\u8fd9\u662f\u4e00\u6279\u6211\u8981\u653e\u7684\u5143\u7d20\u7684\u4e2a\u6570\uff0c\u5185\u90e8\u5b9e\u73b0\u662f\u5148\u7b97\u4e00\u4e0b\u5f53\u524d\u662f\u4e0d\u662f\u591f\u653e\u3001\u5e94\u8be5\u5f80\u54ea\u653e\uff0c\u7136\u540e\u5148\u7b97\u51fa\u5f80\u6570\u7ec4\u540e\u534a\u90e8\u5206\u53ef\u4ee5\u653e\u7684\u4e2a\u6570\uff0c\u7136\u540e\u8981\u662f\u6ca1\u653e\u5b8c\u5c31\u4ece\u6570\u7ec4[0]\u4f4d\u7f6e\u7ee7\u7eed\u653e\uff1bget()\u4e5f\u662f\u7c7b\u4f3c\u7684\u9053\u7406\uff1b<\/li>\n
  5. \u5fc5\u987b\u5148\u64cd\u4f5c\u5b8c\u518d\u66f4\u65b0in\u6216out\u7684\u503c;<\/li>\n
  6. \u4f7f\u7528\u4e86smp_wmb()<\/b>\u505a\u5185\u5b58\u5c4f\u969c\uff0c\u4fdd\u8bc1\u5bf9\u65b9\u6b63\u786e\u89c2\u5bdf\u5230\u6211\u7684\u6267\u884c\u987a\u5e8f\u3002<\/li>\n<\/ol>\n
    \u5173\u4e8e\u5e26spinlock<\/b>\u7684\u63a5\u53e3\uff0c\u56e0\u4e3a\u81ea\u65cb\u9501\u662fbusy-waiting\uff0c\u6bd4\u8f83\u9002\u5408\u9501\u4e0a\u4e4b\u540e\u5f88\u5feb\u91ca\u653e\u7684\u573a\u666f\uff0c\u8fd9\u6837\u907f\u514d\u4e92\u65a5\u9501\u5207\u7ebf\u7a0b\u7684\u6027\u80fd\u635f\u8017\uff0c\u9002\u5408\u4e89\u62a2\u7684\u4eba\u6570\u5c0f\u4e8e\u7b49\u4e8ecpu\u6570\u7684\u573a\u666f\uff0c\u5426\u5219\u4f1a\u5bfc\u81f4cpu cache\u9891\u7e41\u5931\u6548\u6027\u80fd\u4f1a\u6025\u5267\u4e0b\u964d\u3002\u6240\u4ee5\u5728\u5b9e\u9645\u4f7f\u7528\u5e26spinlock\u7684\u6a21\u5757\u65f6\uff0c\u7ebf\u7a0b\u6570\u600e\u4e48\u6839\u636e\u4f7f\u7528\u60c5\u51b5\u548c\u6a21\u5757\u672c\u8eab\u7684\u7279\u70b9\u6765\u914d\u5c31\u5f88\u91cd\u8981\u4e86\u3002<\/p>\n
    \u800c\u6211\u4eec\u4f5c\u4e3a\u4e00\u4e2a\u901a\u7528<\/b>\u7684\u901a\u4fe1\u961f\u5217\uff0c\u751f\u4ea7\u8005\/\u6d88\u8d39\u8005\u7ebf\u7a0b\u6570\u91cf\u80af\u5b9a\u8fdc\u8fdc\u5927\u4e8ecpu\u6570\uff08\u56e0\u4e3a\u901a\u4fe1\u573a\u666f\u9664\u4e86\u5bf9epoll\u8fdb\u884c\u64cd\u4f5c\u4ee5\u5916\uff0c\u8fd8\u4f1a\u505a\u4e00\u4e9bread\/write\uff0c\u751a\u81f3\u662f\u5e8f\u5217\u5316\u53cd\u5e8f\u5217\u5316\u7684\u4e8b\u60c5\uff0c\u800c\u6211\u4eec\u4f5c\u4e3a\u6846\u67b6\u63d0\u4f9b\u8005\uff0c\u4e0d\u80fd\u4fdd\u8bc1\u4efb\u4f55\u4e00\u4e2a\u670d\u52a1\u54ea\u90e8\u5206\u8d44\u6e90\u4f7f\u7528\u4f1a\u66f4\u591a\uff09\uff0c\u5982\u679c\u5927\u5bb6\u90fd\u5728\u6bd4\u8f83\u95f2\uff0c\u5c31\u90fd\u5fd9\u7b49spinlock\uff0c\u8fd9\u663e\u7136\u975e\u5e38\u4e0d\u5408\u7406\u3002<\/p>\n
    \u56e0\u6b64\u6211\u4e2a\u4eba\u8ba4\u4e3a\uff0cCAS\u8fd9\u6837\u770b\u6765\u662f\u4e0d\u592a\u9002\u5408\u4e00\u4e2a\u901a\u7528\u7684\u961f\u5217\u5b9e\u73b0\u7684<\/b>\uff0c\u4f46\u662f\u8fd9\u4e24\u5929\u53c8\u770b\u5230\u8bb8\u591a\u5173\u4e8elock-free\u7684\u8d44\u6599\uff0c\u8fd8\u5f97\u6df1\u5165\u4e86\u89e3\u4e0b\u3002\u5982\u679c\u5927\u5bb6\u6709\u4e0d\u4e00\u6837\u7684\u573a\u666f\u4e5f\u6b22\u8fce\u4ea4\u6d41\uff5e<\/p>\n
    3. work stealing<\/h2>\n
    \u524d\u9762\u51e0\u79cd\u5177\u4f53\u5b9e\u73b0\u53ef\u4ee5\u8bf4\u90fd\u5c5e\u4e8ework sharing\uff08\u6240\u6709\u7ebf\u7a0b\u5171\u4eab\u4e00\u4e2a\u961f\u5217\uff09\uff0c\u800c\u8fd9\u91cc\u662f\u7ebf\u7a0b\u4e0d\u591f\u6d88\u8d39\u4e86\u518d\u53bbsteal\u3002\u6240\u4ee5\u8fd9\u91cc\u4e0a\u5347\u5230\u4e00\u4e2a\u66f4\u5927\u7684\u6982\u5ff5\u7684\u8bdd\uff0c\u91cc\u8fb9\u5177\u4f53\u7684\u4f18\u5316\u70b9\u5c31\u6709\u5f88\u591a\uff0c\u6bd4\u5982\uff1a<\/p>\n