多線程相關(guān)

死鎖

死鎖四個(gè)條件：

1. 互斥條件

   • 臨界資源只能被一個(gè)線程擁有

2. 占有且等待

   • 線程/進(jìn)程擁有補(bǔ)發(fā)臨界資源兵钮，但同時(shí)請(qǐng)求另外一些臨界資源

3. 占有不釋放

   • 在請(qǐng)求到其它臨界資源前痊班，已擁有的臨界資源不會(huì)被釋放

4. 循環(huán)鏈

   • 多個(gè)線程/進(jìn)程形成循環(huán)請(qǐng)求鏈

饑餓

線程一直不能獲得所需要的資源梭姓，如：低優(yōu)先級(jí)線程請(qǐng)求資源一直被高優(yōu)先級(jí)線程持有

多線程操作特性

1. 原子性

   • 操作不可中斷

2. 有序性

   • 多線程操作是有序的仪搔，但可能出現(xiàn)cpu指令重排：

     • cpu采用流水線指令模式忧换，可能出現(xiàn)后面指令提前到前面執(zhí)行

3. 可見性

   • 線程對(duì)臨界資源的操作恬惯，其他線程能看到最新的臨界資源

   • violate

     • 保證有序性和可見性

     • 臨界資源發(fā)生變化時(shí)，強(qiáng)迫寫到共享內(nèi)存

線程狀態(tài)

1. 新建

   • new

2. 就緒

   • start：等待系統(tǒng)調(diào)度運(yùn)行

   • yield：從運(yùn)行切換到就緒包雀，重新參與資源競(jìng)爭(zhēng)

3. 運(yùn)行

   • run

4. 阻塞

   • join

   • sleep

   • suspend

5. 結(jié)束

   • 正常運(yùn)行結(jié)束

   • stop： 不建議使用

6. 中斷

   • 并不會(huì)中斷線程宿崭，只是設(shè)置中斷標(biāo)識(shí)位

   • 通過中斷，使線程跳出阻塞狀態(tài)（sleep等）

線程并發(fā)包：java.util.concurrent

1. synchronized

   • 重入鎖

     • 線程可重復(fù)訪問已獲得的臨界資源才写，無需釋放和再申請(qǐng)鎖

   • 配合object.wait葡兑，object.notify實(shí)現(xiàn)多線程通信

     • 使用前需獲得鎖

     • wait執(zhí)行完后自動(dòng)釋放鎖

     • notify/notifyall不會(huì)釋放鎖，只是發(fā)送一個(gè)通知赞草，當(dāng)同步塊執(zhí)行完后才會(huì)釋放鎖

2. 重入鎖：reentrantlock

   • 重入鎖

   • 可設(shè)置優(yōu)先響應(yīng)中斷讹堤，獲得鎖的過程中，可優(yōu)先響應(yīng)中斷厨疙，避免死鎖

   • 可設(shè)置超時(shí)時(shí)長(zhǎng)：獲取的過程中洲守，可設(shè)置等待時(shí)長(zhǎng)

   • 可設(shè)置是否為公平鎖

     • 公平鎖：按申請(qǐng)的先后順序獲得鎖

     • 不公平鎖：隨機(jī)分配

   • 可與condition(notify/signal)配合使用，實(shí)現(xiàn)多線程通信沾凄，類似synchronized+object.wait+object.notify

3. 信號(hào)量：semaphone

   • 實(shí)現(xiàn)多個(gè)線程同時(shí)訪問臨界資源

4. 讀寫鎖：writereadlock

   • 讀不阻塞

   • 寫阻塞

5. 計(jì)時(shí)器：countdownlatch

   • 計(jì)數(shù)為0時(shí)梗醇，線程訪問臨界資源，跳出阻塞

6. 循環(huán)柵欄：cyclebarrier

   • 類似countdownlatch撒蟀，但可重復(fù)計(jì)數(shù)

7. locksupport

   • 可實(shí)現(xiàn)線程的暫停和回復(fù)：park叙谨、unpark

   • 即使先unpark在park也無問題，不像suppend和resume保屯，resume發(fā)生在suppend前出問題

線程并發(fā)集合

1. concurrentmap

2. collections集合方法

3. copyandwritelist

4. blockingqueue

線程池

創(chuàng)建線程池的幾個(gè)參數(shù)：

1. corepoolsize：核心線程數(shù)

2. maxnumpoolsize：最大線程數(shù)

3. keepalive：閑置線程（非核心線程）存活時(shí)間

4. unit：存活時(shí)間單位

5. workqueue：當(dāng)無空閑線程處理任務(wù)時(shí)手负，任務(wù)放到該工作隊(duì)列等待調(diào)度

   • BlockingQueue實(shí)例涤垫，不同實(shí)例對(duì)應(yīng)了不同調(diào)度策略和拒絕策略

6. threadfactory：線程創(chuàng)建工廠

7. handler：任務(wù)拒絕執(zhí)行策略

CAS

1. 比較并交換/無鎖/樂觀鎖

2. a-b-a問題

   • 線程x讀取遍歷z的值為a,線程y讀取到z的值也為a，但此時(shí)z的值可能已經(jīng)經(jīng)過多次變化

   • 可通過版本號(hào)優(yōu)化

3. AutoInteger等

   • 內(nèi)部采用死循環(huán)獲取臨界資源方式竟终，效率低

鎖優(yōu)化

1. 鎖持有時(shí)間

2. 加鎖粒度：細(xì)化蝠猬、粗化

3. 鎖分離

JVM

參考：https://juejin.im/post/5b85ea54e51d4538dd08f601

java內(nèi)存劃分

1. 堆

   • 線程共享

2. 方法區(qū)

   • 線程共享

3. native棧

4. java棧

5. pc

java堆劃分

1. 新生代minor

   • eden區(qū)

     • 對(duì)象一般分配在新生代的eden區(qū)，大對(duì)象和長(zhǎng)期存活對(duì)象分配在老年代

     • eden區(qū)對(duì)象經(jīng)過一次gc后统捶，將移動(dòng)到surrivor區(qū)榆芦，surrivor區(qū)經(jīng)過n次（一般為15次）gc后，將移動(dòng)到老年代

   • surrivor區(qū)

     • from區(qū)

     • to區(qū)

2. 老年代major

3. 永久代/元空間

java引用

1. 強(qiáng)引用

2. 軟引用

3. 弱引用

4. 虛引用

java如何標(biāo)識(shí)對(duì)象是否存活瘾境？

1. 引用計(jì)數(shù)：循環(huán)計(jì)數(shù)問題

2. 可達(dá)性分析：GCRoot

3. string對(duì)象存活：字符串無string對(duì)象引用

4. class存活：實(shí)例都釋放歧杏，且加載它的classloader被釋放

GC算法

1. 標(biāo)記清除

   • 標(biāo)記內(nèi)存回收對(duì)象，再回收

   • 效率高迷守，但存在內(nèi)存碎片問題

2. 復(fù)制

   • 將內(nèi)存劃分為兩塊犬绒，在其中一款分配對(duì)象，gc后兑凿，存活的對(duì)象移動(dòng)到另外一塊

3. 標(biāo)記整理

   • 類似復(fù)制凯力，但沒有將內(nèi)存劃分為兩塊，只是在內(nèi)存的一端分配對(duì)象礼华，存活的對(duì)象移動(dòng)到另外一端

4. 分代回收

   • 新生代：復(fù)制算法

     • 頻繁咐鹤、快、高效

   • 老年代：標(biāo)記清除圣絮、標(biāo)記整理

     • 慢祈惶，低效，時(shí)間間隔久

5. 常用gc處理器

   • 串行

   • 并發(fā)扮匠、并行：gc線程和用戶線程

設(shè)計(jì)模式

六大原則

1. 單一原則

   • 類捧请、接口、方法功能單一

2. 里氏代換原則

   • 子類應(yīng)擴(kuò)展父類抽象方法棒搜，但不應(yīng)該擴(kuò)展父類非抽象方法

3. 依賴倒置原則

   • 抽象不依賴細(xì)節(jié)疹蛉，細(xì)節(jié)應(yīng)該依賴抽象

4. 接口隔離原則

   • 接口方法盡量少，功能劃分為多個(gè)接口

5. 迪米特拉原則

   • 類對(duì)依賴的類了解盡可能少力麸，減少代碼耦合

6. 開放封閉原則

   • 擴(kuò)展開放可款，修改封閉

集合/數(shù)據(jù)結(jié)構(gòu)

Collections

1. set

   • 元素唯一

   • treeset

     • 紅黑樹結(jié)構(gòu)

   • hashset

     • hash算法計(jì)算元素存放地址

2. list

   • arraylist

     • 線性存儲(chǔ)

   • vector

     • 線程安全

   • linkedlist

     • 可實(shí)現(xiàn)fifo、stack

     • 同時(shí)實(shí)現(xiàn)了list和queue

3. queue

   • priorityqueue

     • 優(yōu)先隊(duì)列

map

1. hashmap

   • 數(shù)組+鏈表實(shí)現(xiàn)

   • 多個(gè)數(shù)據(jù)的hash值相同時(shí)克蚂，通過鏈表連接

2. hashtable

   • 線程安全

3. treemap

   • 紅黑樹

4. linkedhashmap

   • 基于雙向鏈表實(shí)現(xiàn)的hashmap

   • 支持插入排序和訪問排序

     • 訪問排序：每次訪問完后的元素放在鏈表頭闺鲸，lru算法

其他

1. hash指元素使用hash算法計(jì)算存儲(chǔ)地址

2. link/tree，指元素是鏈表或者樹的結(jié)構(gòu)

IO

1. 字節(jié)流

2. 字符流

3. randomaccessfile

4. NIO

   • 非阻塞埃叭、內(nèi)存映射方式翠拣，面向塊

   • channel

   • buffer

     • 外部數(shù)據(jù)讀寫 與buffer交互

   • selector

     • 異步IO

序列化

1. 原理

   • java為序列化對(duì)象采用序列號(hào)機(jī)制，當(dāng)序列化一個(gè)對(duì)象時(shí)游盲，先檢查該對(duì)象是否已經(jīng)序列化

     • 未序列化误墓，采用流中數(shù)據(jù)構(gòu)建，并為該對(duì)象關(guān)聯(lián)一個(gè)序列號(hào)

     • 已序列化益缎，直接根據(jù)關(guān)聯(lián)的序列號(hào)谜慌，獲得該對(duì)象引用

2. 版本號(hào)

   • 根據(jù)類的超類、接口和域等屬性計(jì)算得到莺奔，當(dāng)上述信息發(fā)生變化時(shí)欣范，版本號(hào)會(huì)發(fā)生變化

   • 一般將版本號(hào)靜態(tài)寫死，防止序列化時(shí)版本號(hào)不一致發(fā)生異常

3. static令哟、transient域和方法恼琼，不能被序列化

4. 序列化產(chǎn)生新的對(duì)象（不調(diào)用構(gòu)造函數(shù)），單例模式失效

創(chuàng)建對(duì)象的幾種方式

1. 調(diào)用構(gòu)造函數(shù)

2. new

3. 反射

4. 序列化

   • 不調(diào)用構(gòu)造函數(shù)屏富，通過二進(jìn)制流構(gòu)造

5. clone

   • 不調(diào)用構(gòu)造函數(shù)

其他

1. classloader

   • 雙親委派模型

   • 引導(dǎo)classloader

     • 最頂層的加載類晴竞，主要加載核心類庫，%JRE_HOME%\lib下的rt.jar狠半、resources.jar噩死、charsets.jar和class等

   • 擴(kuò)展classloader

     • 加載目錄%JRE_HOME%\lib\ext目錄下的jar包和class文件

   • 系統(tǒng)（應(yīng)用）classloader

     • 加載當(dāng)前應(yīng)用classpath所有類

• https://mp.weixin.qq.com/s/izdIkiU5YcR-rIOw0ehU4g

• https://blog.csdn.net/linzhiqiang0316/article/details/80473906

常用算法

1. 深搜，DFS

Node* DFS(Node* root,int data)
{
    if(root.key == data)
        return root;

    Node*[] chids = data->childs();
    for(Node* child : childs)
    {
        if(child.key == data)
            return child;      
        
        DFS(child,data);
    }
}

2. 廣搜

Node* BFS(Node* root,int data)
{
    if(root.key == data)
        return root;
    
    FIFO<Node*> fifo = new FIFO<Node*>();
    fifo.queue(root);
    
    return BFS_Visit(fifo,data);
}

Node* BFS_Visit(FIFO<Node*> fifo,int data)
{
    while(!fifo.isEmpty())
    {
        Node* item = fifo.dequeue();
        if(item.key == data)
            return item;
        
        for(Node* child : item.childs())
            fifo.queue(child);
    }
}

3. 排序

   • 參考：http://blog.sina.com.cn/s/blog_714cb3040102vexf.html

   • 計(jì)數(shù)排序

   • 快排

int quick_sort_part(int data[], int start, int end)
{
       int i = start;
       int j = start;
       int key = end;
       while (i <= end)
       {
              if (data[i] < data[key])
              {
                     exchange(data[i], data[j]);
                     j++;
              }
              i++;
       }
       if (j != key)
       {
              exchange(data[j], data[key]);
       }
       return j;
}

//快速排序
void quick_sort(int data[], int start, int end)
{
       if (start < end)
       {
              int k = quick_sort_part(data, start, end);
              quick_sort(data, start, k - 1);
              quick_sort(data, k + 1, end);
       }
}

• 合并排序

• 堆排序

  • 最大堆

  • 最小堆

• 樹

  • 二叉樹

  • 二叉搜索樹

  • b樹

  • 紅黑樹