面試手撕併發演算法題

来源:https://www.cnblogs.com/afei688/archive/2022/08/23/16618105.html
-Advertisement-
Play Games

面試手撕併發演算法題 固定列印順序 使用 wait-notify 實現以下功能：先列印 b，再列印 a 思路一 線程t1和t2同時運行，t1中列印 a，t2中列印 b，但 t1 列印得有個前提，就是 t1要在t2運行完釋放鎖了才能列印 a。如果t1先得到鎖，但t2沒有執行，還是得釋放鎖，讓t2得到鎖先 ...


面試手撕併發演算法題

固定列印順序

使用 wait-notify 實現以下功能：先列印 b，再列印 a

思路一

線程t1和t2同時運行，t1中列印 a，t2中列印 b，但 t1 列印得有個前提，就是 t1要在t2運行完釋放鎖了才能列印 a。如果t1先得到鎖，但t2沒有執行，還是得釋放鎖，讓t2得到鎖先列印b，t2執行完，喚醒t1再列印a，實現固定順序列印。

@Slf4j
public class OrderPrint {

    static Object obj = new Object();
    static boolean is2Run = false;	// t2 運行標記， 代表 t2 是否執行過

    public static void main(String[] args) {
        m1();
    }

    private static void m1() {
        Thread t1 = new Thread(() -> {
            synchronized (obj) {
                // 如果 t2 沒有執行過
                while (!is2Run) {
                    try {
                        // t1 先等一會，釋放鎖
                        obj.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            }
            log.debug("a");
        }, "t1");

        Thread t2 = new Thread(() -> {
            log.debug("b");
            synchronized (obj) {
                is2Run = true;      // syn 自帶可見性
                obj.notifyAll();    // 通知 obj 上等待的線程
            }
        }, "t2");

        t1.start();
        t2.start();
    }
}

思路二

思路一有以下幾個問題需要註意：

  1. 需要保證先 wait 再 notify，否則 wait 線程永遠得不到喚醒。因此使用了『運行標記』來判斷該不該 wait；
  2. 如果有些干擾線程錯誤地 notify 了 wait 線程，條件不滿足時還要重新等待，因此使用了 while 迴圈來解決此問題；

可以使用 LockSupport 類的 park 和 unpark 來簡化上面的題目：

    private static void m2() {
        Thread t1 = new Thread(() -> {

            try {
                TimeUnit.SECONDS.sleep(1L);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            // 線程暫停
            LockSupport.park();
            log.debug("a");
        }, "t1");

        Thread t2 = new Thread(() -> {
            log.debug("b");
            // 喚醒線程
            LockSupport.unpark(t1);
        }, "t2");
        t1.start();
        t2.start();
    }

park 和 unpark 比較靈活，有以下特點：

  • park 和 unpark 不需要先獲取鎖，這一點和Object中的wait-notify，Condition介面提供的await-signal都不同。
  • 喚醒方法 unpark 在 等待方法 park 之前或之後運行，線程都能夠被喚醒，這一點其他兩種機制都不行，Object 和 Condition 中的喚醒必須在等待之後調用，線程才能被喚醒；

交替列印

準備三個線程t1、t2和t3，其中 t1 線程列印a，t2 線程列印 b，t3 線程列印 c，交替列印 ABCABC，列印100個字元。

思路：可以使用一個狀態變數來表示列印abc，如 state=1 代表列印 a， state=2代表列印 b，state=3代表列印 c；使用synchronized 加鎖。

@Slf4j
public class AlternatePrint {
    // 初始狀態為1
    private static int state = 1;
    private static int loopNumber = 5;
    private static int count;

    private static Object obj = new Object();

    public static void print(int waitState, int nextState, String str) {
        while (true) {

            synchronized (obj) {
                // 當前獲得鎖的線程狀態不是 state，等待釋放鎖
                while (state != waitState) {
                    try {
                        obj.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                // 如果 count 達到了100，進入if的線程修改為下一狀態，並喚醒另兩個線程，本線程結束
                // 另兩個線程爭奪鎖，最終都會執行結束（可以分析一波）
                if(count == 100) {
                    state = nextState;  // syn 保證可見性
                    obj.notifyAll();
                    break;
                }
                // 當前獲得鎖的線程狀態就是 state，列印要列印的字元串
                log.debug(str);
                count++;

                // 列印完，輪到下一個線程列印了，把狀態改成 nextState
                state = nextState;  // syn 保證可見性
                obj.notifyAll();
            }
        }
    }

    public static void main(String[] args) {
        // t1線程，如果當前狀態是1，就列印a，下一個線程的狀態是2
        new Thread(() -> {
            print(1, 2, "a");
        }, "t1").start();
        // t2線程，如果當前狀態是2，就列印b，下一個線程的狀態是3
        new Thread(() -> {
            print(2, 3, "b");
        }, "t2").start();
        // t3線程，如果當前狀態是3，就列印c，下一個線程的狀態是1
        new Thread(() -> {
            print(3, 1, "c");
        }, "t3").start();
    }
}

交替列印變式

準備三個線程t1、t2和t3，其中 t1 線程列印a，t2 線程列印 b，t3 線程列印 c，交替列印 abcabc...

思路一：wait - notify

定義一個全局變數 state 來實現按順序列印，使用wait - notify機制來處理條件不滿足時等待釋放鎖，滿足時列印並喚醒所有處於等待的線程；

@Slf4j
public class AlternatePrint {
    // 初始狀態為1
    private static int state = 1;
    private static int loopNumber = 5;

    private static Object obj = new Object();

    public static void print(int waitState, int nextState, String str) {
        for (int i = 0; i < loopNumber; i++) {
            synchronized (obj) {
                // 當前獲得鎖的線程狀態不是 state，等待釋放鎖
                while(state != waitState) {
                    try {
                        obj.wait();
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
                // 當前獲得鎖的線程狀態就是 state，列印要列印的字元串
                log.debug(str);
                // 列印完，輪到下一個線程列印了，把狀態改成 nextState，確保下一次列印的線程的狀態一定是 nextState
                state = nextState;  // syn 保證可見性
                obj.notifyAll();
            }
        }
    }

    public static void main(String[] args) {
        // t1線程，如果當前狀態是1，就列印a，下一個線程的狀態是2
        new Thread(() -> {
            print(1, 2, "a");
        }, "t1").start();
        // t2線程，如果當前狀態是2，就列印b，下一個線程的狀態是3
        new Thread(() -> {
            print(2, 3, "b");
        }, "t2").start();
        // t3線程，如果當前狀態是3，就列印c，下一個線程的狀態是1
        new Thread(() -> {
            print(3, 1, "c");
        }, "t3").start();
    }
}

思路二：Lock條件變數

使用 ReentrantLock中的條件變數 Condition 實現等待喚醒機制，每次只會有一個線程在列印，而其他兩個線程在各自的休息室等待（可以把創建出來的Condition 對象 理解成線程休息室）；

剛開始運行時，三個線程都會在各自的休息室等待，所以這個時候需要有一個發起者，就讓主線程發起，喚醒a休息室中等待的線程 t1；

@Slf4j
public class AlternatePrint1 extends ReentrantLock {

    private int loopNumber;     // 迴圈次數

    public AlternatePrint1(int loopNumber) {
        this.loopNumber = loopNumber;
    }

    /**
     * @param cur  進入哪一件休息室等待
     * @param next	cur休息室的線程列印完後，要喚醒下一個休息室中等待的線程
     * @param str	要列印的字元串
     */
    public void print(Condition cur, Condition next, String str) {
        for (int i = 0; i < loopNumber; i++) {
            this.lock();
            try {
                cur.await();    // 每個線程獲取鎖進來，直接去各自的休息室等待
                log.debug(str);
                next.signal();  // 喚醒下一間休息室的線程
            } catch (InterruptedException e) {
                e.printStackTrace();
            } finally {
                this.unlock();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        // 創建對象，設置列印次數為5
        AlternatePrint1 ap = new AlternatePrint1(5);
        // 為三個線程分別創建三個休息室
        Condition a = ap.newCondition();
        Condition b = ap.newCondition();
        Condition c = ap.newCondition();

        new Thread(() -> {
            ap.print(a, b, "a");
        }, "t1").start();

        new Thread(() -> {
            ap.print(b, c, "b");
        }, "t2").start();

        new Thread(() -> {
            ap.print(c, a, "c");
        }, "t3").start();

        // 以上三個線程都去各自的休息室等待去了，1s之後，主線程喚醒a休息室中的線程
        TimeUnit.SECONDS.sleep(1L);
        try {
            ap.lock();
            // 讓主線程先喚醒在a休息室中等待的線程
            a.signal();
        } finally {
            ap.unlock();
        }
    }
}

TODO


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 03 開源任務管理系統：創建一個任務
    雖說是一個任務管理系統，但簡單地講，其實就是任務的增刪改查(CRUD)。 其中最重要的又當屬增，即創建任務，此為數據之源，刪改查都依賴於它所產生的數據。接下來就從交互設計到前端，服務端，資料庫一步步去實現任務的創建。 ...
  • 妙啊！純 CSS 實現拼圖游戲
    本文，將向大家介紹一種將多個 CSS 技巧運用到極致的技巧，利用純 CSS 實現拼圖游戲。 本技巧源自於 Temani Afif 的 CodePen CSS Only Puzzle game。一款完全由 CSS 實現的拼圖游戲。 我們要做的，就是將散落的圖片碎塊，複原成一幅完整的圖，像是這樣： 註意 ...
  • Vue3中插槽(slot)用法彙總
    Vue中的插槽相信使用過Vue的小伙伴或多或少的都用過，但是你是否瞭解它全部用法呢？本篇文章就為大家帶來Vue3中插槽的全部用法來幫助大家查漏補缺。 什麼是插槽 簡單來說就是子組件中的提供給父組件使用的一個坑位，用<slot></slot> 表示，父組件可以在這個坑位中填充任何模板代碼然後子組件中< ...
  • ts的介面和泛型的基本語法
    內聯模板 點擊打開視頻講解更加詳細 當 inline-template 這個特殊的 attribute 出現在一個子組件上時，這個組件將會使用其裡面的內容作為模板，而不是將其作為被分發的內容。這使得模板的撰寫工作更加靈活。 <my-component inline-template> <div> < ...
  • MyBatis數據輸入，總體機制的概括
    1. MyBatis數據輸入 1.1 Mybatis總體機制概括 1.2 概念說明 註意：這裡的簡單類型不是指的基本數據類型。 1.3 單個簡單類型參數 1.3.1 Mapper介面中的抽象方法 public interface EmpMapper { /** * 通過這個方法對應Mapper配置文 ...
  • 對抗軟體複雜度的戰爭
    服務一個人的系統，和服務一億人的系統，複雜度有著天壤之別。本文從工程師文化、組織戰略、公司內部協作等角度來分析軟體複雜度形成的原因，並提出了一些切實可落地的解法。 ...
  • spring介面多實現類，該依賴註入哪一個？
    一、問題的描述 在實際的系統應用開發中我經常會遇到這樣的一類需求，相信大家在工作中也會經常遇到： 同一個系統在多個省份部署。 一個業務在北京是一種實現方式，是基於北京用戶的需求。 同樣的業務在上海是另外一種實現方式，與北京的實現方式大同小異 遇到這樣的需求，我們通常會定義一個業務實現的介面，比如： ...
  • Chapter 1
    1 讓自己習慣C++ 條款 01 視 C++ 為一個語言聯邦 C : C++以C為基礎，block、語句、預處理器、內置數據類型、數組、指針都來自於C。當使用C++中的C成分工作時，沒有模板(Template)、沒有異常(Exceptions)、沒有重載(overloading)。 Object-O ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類