Web 前端 – 又不僅限於 Web 前端 – 協程鎖問題

• 2021 年 4 月 1 日
• 筆記
• javascript, Javascript / Typescript, typescript, 公平鎖, 協程鎖, 可重入鎖, 自旋鎖

前言

　　最近兩天的 web 前端開發中，早前的鎖實現 (自旋鎖) 出現了一些不合理的現象，所以有了這片隨筆

　　什麼是協程鎖？能點進這個部落格的的你肯定是明白的，不明白的人根本搜不到我這隨筆，不多做贅述。

一些個人認識和實現經驗

1. 可重入鎖：協程由於沒有像『執行緒』那樣的變數隔離，即缺少『計數標識』的掛載位置（多執行緒中計數標識直接或間接掛載在執行緒對象上），未實現可重入鎖之前，編碼開發中應該避免嵌套相同鎖調用，否則造成死鎖，
   所以『可重入鎖』暫時沒有太好的實現思路，希望有大神可以指點迷津。
2. 自旋鎖：優點是通俗易懂，一行 while(lock = getLock( lockKey )) await sleep(20) 就可以實現，缺點是不能保證程式碼的順序性，造成無法預知的 Bug，如 非同步打開遮罩 -> 非同步關閉遮罩 的執行順序將不可控，棄用。
3. 公平鎖：保證 FIFO 策略，使協程對鎖先取先得，解決自旋鎖的缺陷。
4. 歸一鎖：類似多執行緒中的雙重檢驗鎖，在多執行緒中多用於單例的初始化或賦值，在 Web 前端可將重複非同步冪等操作消減歸一。如『獲取用戶資訊』多個模組都調用此非同步函數，只接發出一個『獲取用戶資訊』的請求，多餘 1 個的所有協程將進入 Pending 狀態，一起等待返回結果。
   （ 結合公平鎖，實現順序等待調用）
5. 等侯鎖：只允許一個協程進入操作，多餘 1 的所有協程進入 Pending 狀態，等待被調用。
   （結合公平鎖，實現順序等待調用）

　　暫時想到這麼多，歡迎補充。

設計

1. 歸一鎖：asyncOne( asyncFunction:AsyncFunction, …keys:any[] )
2. 等侯鎖：asyncWait( asyncFunction:AsyncFunction, …keys:any[] )

實現

1. 鎖管理器 ( 核心 )：根據一組 keys ，提供 查、加、解 鎖的能力。
   getPendings(keys) / addPendings(keys) / delPendings(keys)
   

   // Synchronized async function
   const NEXT = Symbol();
   const PREV = Symbol();
   type LevelsNode = { [NEXT]?: LevelsMap; pendings?: PendingPromise<any>[]; [PREV]?: LevelsNode; key: string };
   type LevelsMap = Map<any, LevelsNode>;
   
   function findSyncNode(syncMap: LevelsMap, keys: any[], creation: false): [LevelsMap | undefined, LevelsNode | undefined, PendingPromise<any>[] | undefined];
   function findSyncNode(syncMap: LevelsMap, keys: any[], creation: true): [LevelsMap, LevelsNode, PendingPromise<any>[]];
   function findSyncNode(syncMap: LevelsMap, keys: any[], creation: boolean) {
     let prntNode: LevelsNode | undefined;
     let map: LevelsMap | undefined = syncMap;
     for (let i = 0; !!map && i < keys.length - 1; i++) {
       let lastNode = prntNode;
       prntNode = map.get(keys[i]);
       if (!prntNode) {
         if (creation) {
           prntNode = { [NEXT]: new Map(), [PREV]: lastNode, key: keys[i] };
           map.set(keys[i], prntNode);
           map = prntNode[NEXT];
         } else {
           map = undefined;
         }
       } else if (!(map = prntNode[NEXT])) {
         if (creation) {
           prntNode[NEXT] = new Map();
           map = prntNode[NEXT];
         } else {
           if (i < keys.length - 2) prntNode = undefined;
         }
       }
     }
     let mapNode = map?.get(keys[keys.length - 1]);
     if (creation) {
       if (!map) {
         Throwable("Impossible Error: No Prev Map.");
       } else if (!mapNode) {
         map.set(keys[keys.length - 1], (mapNode = { pendings: [], [PREV]: prntNode, key: keys[keys.length - 1] }));
       } else if (!mapNode.pendings) {
         mapNode.pendings = [];
       }
     }
     return [map, mapNode, mapNode?.pendings];
   }
   const getPendings = (syncMap: LevelsMap, keys: any[]) => findSyncNode(syncMap, keys, false)[2];
   const addPendings = (syncMap: LevelsMap, keys: any[]) => findSyncNode(syncMap, keys, true)[2];
   const delPendings = (syncMap: LevelsMap, keys: any[]) => {
     const [finalMap, finalVal] = findSyncNode(syncMap, keys, false);
     if (!!finalMap && !!finalVal) {
       // delete pending
       delete finalVal.pendings;
       // delete above including self
       tryDeleteNodeAndAbove(syncMap, finalVal);
     }
   };
   const tryDeleteNodeAndAbove = (syncMap: LevelsMap, node?: LevelsNode) => {
     while (!!node) {
       const nextMap = node[NEXT];
       if (!node.pendings && (!nextMap || nextMap.size === 0)) {
         const nodeKey = node.key;
         node = node[PREV];
         const map = node?.[NEXT] || syncMap;
         map.delete(nodeKey);
       } else {
         break;
       }
     }
   };

    

   
   

2. 歸一鎖演算法：
   

   const asyncOneMap: LevelsMap = new Map<any, LevelsNode>();
   export const asyncOne = async <T>(call: () => Promise<T>, ...keys: any[]): Promise<T> => {
     let pendings = getPendings(asyncOneMap, keys);
     if (!!pendings) {
       return (pendings[pendings.length] = pendingResolve<T>());
     } else {
       pendings = addPendings(asyncOneMap, keys);
       try {
         const result = await call.call(null);
         pendings.forEach(p => setTimeout(() => p.resolve(result)));
         return result;
       } catch (e) {
         pendings.forEach(p => setTimeout(() => p.reject(e)));
         throw e;
       } finally {
         delPendings(asyncOneMap, keys);
       }
     }
   };

    

3. 等侯鎖演算法：
   

   const asyncWaitMap: LevelsMap = new Map<any, LevelsNode>();
   export const asyncWait = async <T>(call: () => Promise<T>, ...keys: any[]) => {
     let pendings = getPendings(asyncWaitMap, keys);
     /*sleep*/ if (!!pendings) await (pendings[pendings.length] = pendingResolve<void>());
     /*continue-------------*/ else pendings = addPendings(asyncWaitMap, keys);
     try {
       return await call.call(null);
     } finally {
       const next4awaken = pendings.shift();
       /*awaken the next*/ if (next4awaken !== undefined) next4awaken.resolve();
       /*unlock-----------------------------------*/ else delPendings(asyncWaitMap, keys);
     }
   };

    

4. 依賴項 ( 第二關鍵 )：pendingResolve<T>:  <T>()=>PendingPromise<T>
   返回一個永久 pending 狀態的 Promise, 充當協程斷點的角色，必要時才手動 resolve / reject。
   本文不多贅述，請參考我的另一篇隨筆: Web 前端 – 淺談外部手動控制 Promise 狀態：PendingPromise<T>
5. 依賴項 ( 輕微重要 )：aw: ( ms: number)=>Promise<void>
   類似於多執行緒語言中的 sleep( ms:number )
   本文不多贅述，請參考我的另一篇隨筆: Web 前端 – 優雅地 Callback 轉 Promise ：aw