標籤: USB CONNECTOR

Dictionary<TKey,TValue>是日常.net開發中最常用的數據類型之一，基本上遇到鍵值對類型的數據時第一反應就是使用這種散列表。散列表特別適合快速查找操作，查找的效率是常數階O(1)。那麼為什麼這種數據類型的查找效率能夠這麼高效？它背後的數據類型是如何支撐這種查找效率的？它在使用過程中有沒有什麼局限性？一起來探究下這個數據類型的奧秘吧。

本文內容針對的是.Net Framework 4.5.1的代碼實現，在其他.Net版本中或多或少都會有些差異，但是基本的原理還是相同的。

本文的內容主要分為三個部分，第一部分是從代碼的角度來分析並以圖文並茂的方式通俗的解釋Dictionary如何解決的散列衝突並實現高效的數據插入和查找。第二部分名為“眼見為實”，由於第一部分是從代碼層面分析Dictionary的實現，側重於理論分析，因此第二部分使用windbg直接分析內存結構，跟第一部分的理論分析相互印證，加深對於這種數據類型的深入理解。最後是從數據結構的時間複雜度的角度進行分析並提出了幾條實踐建議。

本文內容：

• 第一部分 代碼分析
  • 散列衝突
  • Dictionary圖文解析
  • Dictionary的初始化
  • 添加第四個元素
• 第二部分 眼見為實
  • 添加第一個元素后的內存結構
  • 添加第四個元素后的內存結構
• 第三部分
  • 時間複雜度分析
  • 實踐建議

散列衝突

提到散列表，就不能不提散列衝突。由於哈希算法被計算的數據是無限的，而計算后的結果範圍有限，因此總會存在不同的數據經過計算后得到的值相同，這就是哈希衝突。（兩個不同的數據計算后的結果一樣）。散列衝突的解決方案有好幾個，比如開放尋址法、鏈式尋址法。

Dictionary使用的是鏈式尋址法，也叫做拉鏈法。拉鏈法的基本思想是將散列值相同的數據存在同一個鏈表中，如果有散列值相同的元素，則加到鏈表的頭部。同樣道理，在查找元素的時候，先計算散列值，然後在對應散列值的鏈表中查找目標元素。

用圖來表達鏈式尋址法的思想：

Dictionary<TKey,TValue>的內部數據結構

Dictionary的內部存儲數據主要是依賴了兩個數組，分別是int[] buckets和Entry[] entries。其中buckets是Dictionary所有操作的入口，類似於上文中解說拉鏈法所用的圖中的那個豎著的數據結構。Entry是一個結構體，用於封裝所有的元素並且增加了next字段用於構建鏈表數據結構。為了便於理解，下文中截取了一段相關的源代碼並增加了註釋。

//數據在Dictionary<TKey,TValue>的存儲形式，所有的鍵值對在Dictionary<TKey,TValue>都是被包裝成一個個的Entry保存在內存中
private struct Entry {
    public int hashCode;    // 散列計算結果的低31位數，默認值為-1
    public int next;        // 下一個Entry的索引值，鏈表的最後一個Entry的next為-1
    public TKey key;        // Entry對象的Key對應於傳入的TKey
    public TValue value;    // Entry對象的Value對應與傳入的TValue
}

private int[] buckets;      //hashCode的桶，是查找所有Entry的第一級數據結構
private Entry[] entries;    //保存真正的數據

下文中以Dictionary<int,string>為例，分析Dictionary在使用過程中內部數據的組織方式。

Dictionary初始化

初始化代碼：

Dictionary<int, string> dictionary = new Dictionary<int, string>();

Dictionary的初始化時，buckets和entries的長度都是0。

添加一個元素

dictionary.Add(1, "xyxy");

向Dictionary中添加這個新元素大致經過了7個步驟：

1. 首先判斷數組長度是否需要擴容（原長度為0，需要擴容）；
2. 對於數組進行擴容，分別創建長度為3的bucket數組和entries數組（使用大於原數組長度2倍的第一個素數作為新的數組長度）；
3. 整數1的hashcode為1；
4. 取低31位數值為1（計算公式：hashcode & 0x7FFFFFFF=1）；
5. 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
6. 將hashcode、key、value包裝起來（封裝到entries數組下標為0的結構體中）；
7. 設置bucket[1]的值為0（因為新元素被封裝到了entries數組下標為0的位置）；

當向Dictionary中添加一個元素后，內部數據結構如下圖（為了便於理解，圖上將bucket和entries中各個鏈表頭結點用線標出了關聯關係）：

添加第二個元素

dictionary.Add(7, "xyxy");

向Dictionary中添加這個元素大致經過了6個步驟：

1. 計算7的hashcode是7；
2. 取低31位數值為7（計算公式：hashcode & 0x7FFFFFFF=1）；
3. 該key的hashcode落到bucket下標為1的位置（計算公式：hashCode % buckets.Length=1）；
4. 將hashcode、key、value包裝起來（封裝到entries數組下標為1的結構體中，跟步驟3計算得到的1沒有關係，只是因為entries數組下標為1的元素是空着的所以放在這裏）；
5. 原bucket[1]為0，所以設置當前結構體的Entry.next為0；
6. 設置bucket[1]為1（因為鏈表的頭部節點位於entries數組下標為1的位置）

當向Dictionary中添加第二個元素后，內部數據結構是這樣的：

添加第三個元素

dictionary.Add(2, "xyxy");

向Dictionary添加這個元素經過了如下5個步驟：

1. 整數2計算的hashcode是2；
2. hashcode取低31位數值為2（計算公式：hashcode & 0x7FFFFFFF=2）；
3. 該key的hashcode落到bucket下標為2的位置（計算公式：hashCode % buckets.Length=2）；
4. 將hashcode、key、value包裝起來（封裝到entries數組下標為2的結構體中，到此entries的數組就存滿了）；
5. 原bucket[2]上為-1，所以bucket[2]節點下並沒有對應鏈表，設置當前結構體的Entry.next為-1；
6. 設置bucket[2]為2（因為鏈表的頭部節點位於entries數組下標為2的位置）

當向Dictionary中添加第三個元素后，內部數據結構：

添加第四個元素

dictionary.Add(4, "xyxy");

通過前面幾個操作可以看出，當前數據結構中entries數組中的元素已滿，如果再添加元素的話，會發生怎樣的變化呢？

假如再對於dictionary添加一個元素，原來申請的內存空間肯定是不夠用的，必須對於當前數據結構進行擴容，然後在擴容的基礎上再執行添加元素的操作。那麼在解釋這個Add方法原理的時候，分為兩個場景分別進行：數組擴容和元素添加。

數組擴容

在發現數組容量不夠的時候，Dictionary首先執行擴容操作，擴容的規則與該數據類型首次初始化的規則相同，即使用大於原數組長度2倍的第一個素數7作為新數組的長度（3*2=6，大於6的第一個素數是7）。

擴容步驟：

1. 新申請一個容量為7的數組，並將原數組的元素拷貝至新數組（代碼：Array.Copy(entries, 0, newEntries, 0, count);）
2. 重新計算原Dictionary中的元素的hashCode在bucket中的位置（注意新的bucket數組中數值的變化）；
3. 重新計算鏈表（注意entries數組中結構體的next值的變化）；

擴容完成后Dictionary的內容數據結構：

添加元素

當前已經完成了entries和bucket數組的擴容，有了充裕的空間來存儲新的元素，所以可以在新的數據結構的基礎上繼續添加元素。

當向Dictionary中添加第四個元素后，內部數據結構是這樣的：

添加這個新的元素的步驟：

1. 整數4計算的hashcode是4；
2. hashcode取低31位數值為4（計算公式：hashcode & 0x7FFFFFFF=4）；
3. 該key的hashcode落到bucket下標為4的位置（計算公式：hashCode % buckets.Length=4）；
4. 將hashcode、key、value包裝起來；（封裝到entries數組下標為3的結構體中)；
5. 原bucket[4]上為-1，所以當前節點下並沒有鏈表，設置當前結構體的Entry.next為-1；
6. 設置bucket[4]為3（因為鏈表的頭部節點位於entries數組下標為3的位置）

眼見為實

畢竟本文的主題是圖文並茂分析Dictionary<Tkey,Tvalue>的原理，雖然已經從代碼層面和理論層面分析了Dictionary<Tkey,Tvalue>的實現，但是如果能夠分析這個數據類型的實際內存數據結果，可以獲得更直觀的感受並且對於這個數據類型能夠有更加深入的認識。由於篇幅的限制，無法將Dictionary<Tkey,Tvalue>的所有操作場景結果都進行內存分析，那麼本文中精選有代表性的兩個場景進行分析：一是該數據類型初始化后添加第一個元素的內存結構，二是該數據類型進行第一次擴容后的數據結構。

Dictionary添加第一個元素后的內存結構

執行代碼：

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
Console.Read();

打開windbg附加到該進程(由於使用的是控制台應用程序，當前線程是0號線程，因此如果附加進程后默認的不是0號線程時執行~0s切換到0號線程),執行!clrstack -l查看當前線程及線程上使用的所有變量：

0:000> !clrstack -l
OS Thread Id: 0x48b8 (0)
        Child SP               IP Call Site
0000006de697e998 00007ffab577c134 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e998 00007ffa96abc9c8 [InlinedCallFrame: 0000006de697e998] Microsoft.Win32.Win32Native.ReadFile(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)
0000006de697e960 00007ffa96abc9c8 *** ERROR: Module load completed but symbols could not be loaded for C:\WINDOWS\assembly\NativeImages_v4.0.30319_64\mscorlib\5c1b7b73113a6f079ae59ad2eb210951\mscorlib.ni.dll
DomainNeutralILStubClass.IL_STUB_PInvoke(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte*, Int32, Int32 ByRef, IntPtr)

0000006de697ea40 00007ffa972d39ec System.IO.__ConsoleStream.ReadFileNative(Microsoft.Win32.SafeHandles.SafeFileHandle, Byte[], Int32, Int32, Boolean, Boolean, Int32 ByRef)
    LOCALS:
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>
        <no data>

0000006de697ead0 00007ffa972d38f5 System.IO.__ConsoleStream.Read(Byte[], Int32, Int32)
    LOCALS:
        <no data>
        <no data>

0000006de697eb30 00007ffa96a882d4 System.IO.StreamReader.ReadBuffer()
    LOCALS:
        <no data>
        <no data>

0000006de697eb80 00007ffa97275f23 System.IO.StreamReader.Read()
    LOCALS:
        <no data>

0000006de697ebb0 00007ffa9747a2fd System.IO.TextReader+SyncTextReader.Read()

0000006de697ec10 00007ffa97272698 System.Console.Read()

0000006de697ec40 00007ffa38670909 ConsoleTest.DictionaryDebug.Main(System.String[])
    LOCALS:
        0x0000006de697ec70 = 0x00000215680d2dd8

0000006de697ee88 00007ffa97ba6913 [GCFrame: 0000006de697ee88] 

通過對於線程堆棧的分析很容易看出當前線程上使用了一個局部變量，地址為：0x000001d86c972dd8，使用!do命令查看該變量的內容：

0:000> !do 0x00000215680d2dd8
Name:        System.Collections.Generic.Dictionary`2[[System.Int32, mscorlib],[System.String, mscorlib]]
MethodTable: 00007ffa96513328
EEClass:     00007ffa9662f610
Size:        80(0x50) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffa964a8538  4001887        8       System.Int32[]  0 instance 00000215680d2ee8 buckets
00007ffa976c4dc0  4001888       10 ...non, mscorlib]][]  0 instance 00000215680d2f10 entries
00007ffa964a85a0  4001889       38         System.Int32  1 instance                1 count
00007ffa964a85a0  400188a       3c         System.Int32  1 instance                1 version
00007ffa964a85a0  400188b       40         System.Int32  1 instance               -1 freeList
00007ffa964a85a0  400188c       44         System.Int32  1 instance                0 freeCount
00007ffa96519630  400188d       18 ...Int32, mscorlib]]  0 instance 00000215680d2ed0 comparer
00007ffa964c6ad0  400188e       20 ...Canon, mscorlib]]  0 instance 0000000000000000 keys
00007ffa977214e0  400188f       28 ...Canon, mscorlib]]  0 instance 0000000000000000 values
00007ffa964a5dd8  4001890       30        System.Object  0 instance 0000000000000000 _syncRoot

從內存結構來看，該變量中就是我們查找的Dic存在buckets、entries、count、version等字段，其中buckets和entries在上文中已經有多次提及，也是本文的分析重點。既然要眼見為實，那麼buckets和entries這兩個數組的內容到底是什麼樣的呢？這兩個都是數組，一個是int數組，另一個是結構體數組，對於這兩個內容分別使用!da命令查看其內容：

首先是buckets的內容：

0:000> !da -start 0 -details 00000215680d2ee8 
Name:        System.Int32[]
MethodTable: 00007ffa964a8538
EEClass:     00007ffa966160e8
Size:        36(0x24) bytes
Array:       Rank 1, Number of elements 3, Type Int32
Element Methodtable: 00007ffa964a85a0
[0] 00000215680d2ef8
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[1] 00000215680d2efc
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 00000215680d2f00
    Name:        System.Int32
    MethodTable: 00007ffa964a85a0
    EEClass:     00007ffa96616078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  40005a2        0             System.Int32      1     instance                   -1     m_value

當前buckets中有三個值，分別是：-1、0和-1，其中-1是數組初始化后的默認值，而下錶為1的位置的值0則是上文中添加dic.Add(1, "xyxy");這個指令的結果，代表其對應的鏈表首節點在entries數組中下標為0的位置，那麼entries數組中的數值是什麼樣子的呢？

0:000> !da -start 0 -details 00000215680d2f10 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        96(0x60) bytes
Array:       Rank 1, Number of elements 3, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000215680d2f20
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000215680d2db0     value
[1] 00000215680d2f38
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[2] 00000215680d2f50
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

通過對於entries數組的分析可以看出，這個數組也有三個值，其中下標為0的位置已經填入相關內容，比如hashCode為1，key為1，其中value的內容是一個內存地址：000001d86c972db0，這個地址指向的就是字符串對象，它的內容是xyxy，使用!do指令來看下具體內容：

0:000> !do  00000215680d2db0
Name:        System.String
MethodTable: 00007ffcc6b359c0
EEClass:     00007ffcc6b12ec0
Size:        34(0x22) bytes
File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
String:      xyxy
Fields:
              MT    Field   Offset                 Type VT     Attr            Value Name
00007ffcc6b385a0  4000283        8         System.Int32  1 instance                4 m_stringLength
00007ffcc6b36838  4000284        c          System.Char  1 instance               78 m_firstChar
00007ffcc6b359c0  4000288       e0        System.String  0   shared           static Empty

簡要分析擴容后的內存結構

此次執行的代碼為：

Dictionary<int, string> dic = new Dictionary<int, string>();
dic.Add(1, "xyxy");
dic.Add(7, "xyxy");
dic.Add(2, "xyxy");
dic.Add(4, "xyxy");
Console.Read();

同樣採取附加進程的方式分析這段代碼執行后的內存結構，本章節中忽略掉如何查找Dictionary變量地址的部分，直接分析buckets數組和entries數組的內容。

首先是buckets數組的內存結構：

0:000> !da -start 0 -details 0000019a471a54f8 
Name:        System.Int32[]
MethodTable: 00007ffcc6b38538
EEClass:     00007ffcc6ca60e8
Size:        52(0x34) bytes
Array:       Rank 1, Number of elements 7, Type Int32
Element Methodtable: 00007ffcc6b385a0
[0] 0000019a471a5508
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    1     m_value
[1] 0000019a471a550c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    0     m_value
[2] 0000019a471a5510
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    2     m_value
[3] 0000019a471a5514
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[4] 0000019a471a5518
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                    3     m_value
[5] 0000019a471a551c
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value
[6] 0000019a471a5520
    Name:        System.Int32
    MethodTable: 00007ffcc6b385a0
    EEClass:     00007ffcc6ca6078
    Size:        24(0x18) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffcc6b385a0  40005a2        0             System.Int32      1     instance                   -1     m_value

然後是entries的內存結構：

0:000> !da -start 0 -details 00000237effb2fa8 
Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]][]
MethodTable: 00007ffa965135b8
EEClass:     00007ffa9662d1f0
Size:        192(0xc0) bytes
Array:       Rank 1, Number of elements 7, Type VALUETYPE
Element Methodtable: 00007ffa96513558
[0] 00000237effb2fb8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    1     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    1     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[1] 00000237effb2fd0
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    7     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    7     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[2] 00000237effb2fe8
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    2     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    2     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[3] 00000237effb3000
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    4     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                   -1     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    4     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     00000237effb2db0     value
[4] 00000237effb3018
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[5] 00000237effb3030
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value
[6] 00000237effb3048
    Name:        System.Collections.Generic.Dictionary`2+Entry[[System.Int32, mscorlib],[System.String, mscorlib]]
    MethodTable: 00007ffa96513558
    EEClass:     00007ffa966304e8
    Size:        40(0x28) bytes
    File:        C:\WINDOWS\Microsoft.Net\assembly\GAC_64\mscorlib\v4.0_4.0.0.0__b77a5c561934e089\mscorlib.dll
    Fields:
                      MT    Field   Offset                 Type VT     Attr            Value Name
        00007ffa964a85a0  4003502        8             System.Int32      1     instance                    0     hashCode
        00007ffa964a85a0  4003503        c             System.Int32      1     instance                    0     next
        00007ffa964a85a0  4003504       10             System.Int32      1     instance                    0     key
        00007ffa964aa238  4003505        0           System.__Canon      0     instance     0000000000000000     value

從內存的結構來看，擴容后bucket數組中使用了下標為0、1、2和4這四個位置，entries中使用了0~3存儲了示例中添加的數據，符合前文中理論分析的結果，兩者相互之間具有良好的印證關係。

時間複雜度分析

時間複雜度表達的是數據結構操作數據的時候所消耗的時間隨着數據集規模的增長的變化趨勢。常用的指標有最好情況時間複雜度、最壞情況時間複雜度和均攤時間複雜度。那麼對於Dictionary<Tkey,TValue>來說，插入和查找過程中這些時間複雜度分別是什麼樣的呢？

最好情況時間複雜度：對於查找來說最好的是元素處於鏈表的頭部，查找效率不會隨着數據規模的增加而增加，因此該複雜度為常量階複雜度，即O(1)；插入操作最理想的情況是數組中有空餘的空間，不需要進行擴容操作，此時時間複雜度也是常量階的，即O(1)；

最壞情況時間複雜度：對於插入來說，比較耗時的操作場景是需要順着鏈表查找符合條件的元素，鏈表越長，查找時間越長（下文稱為場景一）；而對於插入來說最壞的情況是數組長度不足，需要動態擴容並重新組織鏈表結構（下文稱為場景二）；

場景一中時間複雜度隨着鏈表長度的增加而增加，但是Dictionary中規定鏈表的最大長度為100，如果有長度超過100的鏈表就需要擴容並調整鏈表結構，所以順着鏈表查找數據不會隨着數據規模的增長而增長，最大時間複雜度是固定的，因此時間複雜度還是常量階複雜度，即O(1);

場景二中時間複雜度隨着數組中元素的數量增加而增加，如果原來的數組元素為n個，那麼擴容時需要將這n個元素拷貝到新的數組中並計算其在新鏈表中的位置，因此該操作的時間複雜度是隨着數組的長度n的增加而增加的，屬於線性階時間複雜度，即O(n)。

綜合場景一和場景二的分析結果得出最壞情況時間複雜度出現在數據擴容過程中，時間複雜度為O(n)。

最好情況時間複雜度和最壞情況時間複雜度都過於極端，只能描述最好的情況和最壞的情況，那麼在使用過程中如何評價數據結構在大部分情況下的時間複雜度？通常對於複雜的數據結構可以使用均攤時間複雜度來評價這個指標。均攤時間複雜度適用於對於一個數據進行連續操作，大部分情況下時間複雜度都很低，只有個別情況下時間複雜度較高的場景。這些操作存在前後連貫性，這種情況下將較高的複雜度攤派到之前的操作中，一般均攤時間複雜度就相當於最好情況時間複雜度。

通過前面的分析可以看出Dictionary恰好就符合使用均攤時間複雜度分析的場景。以插入操作為例，假設預申請的entries數組長度為n，在第n+1次插入數據時必然會遇到一次數組擴容導致的時間消耗較高的場景。將這次較為複雜的操作的時間均攤到之前的n次操作后，每次操作時間的複雜度也是常量階的，因此Dictionary插入數據時均攤時間複雜度也是O(1)。

實踐建議

首先，Dictionary這種類型適合用於對於數據檢索有明顯目的性的場景，比如讀寫比例比較高的場景。其次，如果有大數據量的場景，最好能夠提前聲明容量，避免多次分配內存帶來的額外的時間和空間上的消耗。因為不進行擴容的場景，插入和查找效率都是常量階O(1)，在引起擴容的情況下，時間複雜度是線性階O(n)。如果僅僅是為了存儲數據，使用Dictionary並不合適，因為它相對於List<T>具有更加複雜的數據結構，這樣會帶來額外的空間上面的消耗。雖然Dictionary<TKey,TValue>的TKey是個任意類型的，但是除非是對於判斷對象是否相等有特殊的要求，否則不建議直接使用自定義類作為Tkey。

總結

C#中的Dictionary<TKey,TValue>是藉助於散列函數構建的高性能數據結構，Dictionary解決散列衝突的方式是使用鏈表來保存散列值存在衝突的節點，俗稱拉鏈法。本文中通過圖文並茂的方式幫助理解Dictionary添加元素和擴容過程這兩個典型的應用場景，在理論分析之後使用windbg分析了內存中的實際結構，以此加深對於這種數據類型的深入理解。隨後在此基礎上分析了Dictionary的時間複雜度。Dictionary的最好情況時間複雜度是O(1)，最壞情況複雜度是O(n)，均攤時間複雜度是O(1)，Dictionary在大多數情況下都是常量階時間複雜度，在內部數組自動擴容過程中會產生明顯的性能下降，因此在實際實踐過程中最好在聲明新對象的時候能夠預估容量，儘力避免數組自動擴容導致的性能下降。

參考資料

• Dictionary<TKey,TValue>源代碼(.net framework4.8版本)
• .NET中Dictionary<TKey, TValue>淺析
• 解決hash衝突的三個方法
• 算法複雜度分析（下）：最好、最壞、平均、均攤等時間複雜度概述

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準

摘要：本文主要講談及瀏覽器的渲染原理、流程以及相關的性能問題。

問題前瞻

1. 為什麼css需要放在頭部？
2. js為什麼要放在body後面？
3. 圖片的加載和渲染會阻塞頁面DOM構建嗎？
4. dom解析完才出現頁面嗎？
5. 首屏時間根據什麼來判定？

瀏覽器渲染

1.瀏覽器渲染圖解

[來自google開發者文檔]

瀏覽器渲染頁面主要經歷了下面的步驟：

1.處理 HTML 標記並構建 DOM 樹。
2.處理 CSS 標記並構建 CSSOM 樹。
3.將 DOM 與 CSSOM 合併成一個渲染樹。
4.根據渲染樹來布局，以計算每個節點的幾何信息。
5.將各個節點繪製到屏幕上。

為構建渲染樹，瀏覽器大體上完成了下列工作：

從 DOM 樹的根節點開始遍歷每個可見節點。

某些節點不可見（例如腳本標記、元標記等），因為它們不會體現在渲染輸出中，所以會被忽略。
某些節點通過 CSS 隱藏，因此在渲染樹中也會被忽略，例如，上例中的 span 節點---不會出現在渲染樹中，---因為有一個顯式規則在該節點上設置了“display: none”屬性。
對於每個可見節點，為其找到適配的 CSSOM 規則並應用它們。

發射可見節點，連同其內容和計算的樣式。

根據以上解析，DOM樹和CSSOM樹的構建對於頁面性能有非常大的影響，沒有DOM樹，頁面基本的標籤塊都沒有，沒有樣式，頁面也基本是空白的。所以具體css的解析規則是什麼？js是怎麼影響頁面渲染的？了解了這些，我們才能有的放矢，對頁面性能進行優化。

2.css解析規則

1
<div id="div1">
2
<div class="a">
3
<div class="b">
4
...
5
</div>
6
<div class="c">
7
<div class="d">
8
...
9
</div>
10
<div class="e">
11
...
12
</div>
13
</div>
14
</div>
15
<div class="f">
16
<div class="c">
17
<div class="d">
18
...
19
</div>
20
</div>
21
</div>
22
</div>

 

1
#div1 .c .d {}
2
.f .c .d {}
3
.a .c .e {}
4
#div1 .f {}
5
.c .d{}

從左向右的匹配規則

從右向左的匹配規則

如果css從左向右解析，意味着我們需要遍歷更多的節點。不管樣式規則寫得多細緻，每一個dom結點仍然需要遍歷，因為整個style rules還會有其它公共樣式影響。如果從右向左解析，因為子元素只有一個父元素，所以能夠很快定位出當前dom符不符合樣式規則。

3.js加載和執行機制

首先明確一點，我們可以通過js去修改網頁的內容，樣式和交互等，這一意味着js會影響頁面的dom結構，如果js和dom構建并行執行，那麼很容易會出現衝突，所以js在執行時必然會阻塞dom和cssom的構建過程，不論是外部js還是內聯腳本。

js的位置是否影響dom解析？

首先我們為什麼提倡把js放在body標籤的後面去加載，因為從demo上看無論是放在head還是放在body后加載js，頁面domcontentload的時間都是一樣的：

我們從圖中可以看出js的加載和執行是阻塞dom解析的，但是因為頁面並不是一次就渲染完成，所以我們需要做的是盡量讓用戶看到首屏的部分被渲染出來，js放在頭部，則頁面的內容區域還沒有解析到就被阻塞了，導致用戶看到的是白屏，而js放在body後面，儘管此時頁面dom仍然沒有解析完成，但是已經渲染出一部分樓層了，這也是為什麼我們比較看重頁面的首屏時間。

只有DOM和CSSOM樹構建好后併合並成渲染樹才能開始繪製頁面圖形，那是不是把整個DOM樹和CSSOM樹構建好后才能開始繪製頁面？這顯然是不符合我們平時訪問頁面的認知的，實際上：

為達到更好的用戶體驗，呈現引擎會力求儘快將內容显示在屏幕上。它不必等到整個 HTML 文檔解析完畢之後，就會開始構建呈現樹和設置布局。在不斷接收和處理來自網絡的其餘內容的同時，呈現引擎會將部分內容解析並显示出來。

具體瀏覽器什麼時候進行首次繪製？可以查看本文對瀏覽器首次渲染時間點的探究。

4.圖片的加載和渲染機制

首先我們解答一下上面的問題：圖片的加載與渲染會不會阻塞頁面渲染？答案是圖片的加載和渲染不會影響頁面的渲染。

那麼標籤中的圖片和樣式中的圖片的加載和渲染時間是什麼樣的呢？

解析HTML【遇到標籤加載圖片】 —> 構建DOM樹
加載樣式 —> 解析樣式【遇到背景圖片鏈接不加載】 —> 構建樣式規則樹
加載javascript —> 執行javascript代碼
把DOM樹和樣式規則樹匹配構建渲染樹【遍歷DOM樹時加載對應樣式規則上的背景圖片】
計算元素位置進行布局
繪製【開始渲染圖片】

當然把DOM樹和樣式規則樹匹配構建渲染樹時，只會把可見元素和它對應的樣式規則結合一起產出到渲染樹，這就意味有不可見元素，當匹配DOM樹和樣式規則樹時，若發現一個元素的對應的樣式規則上有display:none，瀏覽器會認為該元素是不可見的，因此不會把該元素產出到渲染樹上。

性能優化

css優化

1.盡量減少層級

1
#div p.class {
2
color: red;
3
}
4

5
.class {
6
color: red;
7
}

層級減少，意味者匹配時遍歷的dom就少。
關於less嵌套的書寫規範也基於這個道理。

2.使用類選擇器而不是標籤選擇器

減少匹配次數

3.按需加載css

1
(function(){
2
window.gConfig = window.gConfig || {};
3
window.gConfig.isMobile = /iPhone|iPad|iPod|Android/i.test(navigator.userAgent);
4
var hClassName;
5
if(window.gConfig.isMobile){
6
hClassName = ' phone';
7

8
document.write('<link rel="stylesheet" href="https://res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/m/index.css" />');
9
document.write('<link rel="preload" href="//res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/m/index.js" crossorigin="anonymous" as="script" />');
10

11
}else{
12
hClassName = ' pc';
13

14
document.write('<link rel="stylesheet" href="https://res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/pc/index.css" />');
15
document.write('<link rel="preload" href="//res.hc-cdn.com/cpage-pep-discount-area-v6/2.0.24/pc/index.js" crossorigin="anonymous" as="script" />');
16

17
}
18
var root = document.documentElement;
19
root.className += hClassName ;
20

21
})();

async 與 defer

[來自https://www.growingwiththeweb.com/2014/02/async-vs-defer-attributes.html]

使用

• 如果腳本是模塊化的並且不依賴於任何腳本，請使用async。
• 如果該腳本依賴於另一個腳本或由另一個腳本所依賴，則使用defer。

減少資源請求

瀏覽器的併發數量有限，所以為了減少瀏覽器因為優先加載很多不必要資源，以及網絡請求和響應時間帶來的頁面渲染阻塞時間，我們首先應該想到的是減少頁面加載的資源，能夠盡量用壓縮合併，懶加載等方法減少頁面的資源請求。

延遲加載圖像

儘管圖片的加載和渲染不會影響頁面渲染，但是為了盡可能地優先展示首屏圖片和減少資源請求數量，我們需要對圖片做懶加載。

1
document.addEventListener("DOMContentLoaded", function() {
2
let lazyImages = [].slice.call(document.querySelectorAll("img.lazy"));
3
let active = false;
4

5
const lazyLoad = function() {
6
if (active === false) {
7
active = true;
8

9
setTimeout(function() {
10
lazyImages.forEach(function(lazyImage) {
11
if ((lazyImage.getBoundingClientRect().top <= window.innerHeight && lazyImage.getBoundingClientRect().bottom >= 0) && getComputedStyle(lazyImage).display !== "none") {
12
lazyImage.src = lazyImage.dataset.src;
13
lazyImage.srcset = lazyImage.dataset.srcset;
14
lazyImage.classList.remove("lazy");
15

16
lazyImages = lazyImages.filter(function(image) {
17
return image !== lazyImage;
18
});
19

20
if (lazyImages.length === 0) {
21
document.removeEventListener("scroll", lazyLoad);
22
window.removeEventListener("resize", lazyLoad);
23
window.removeEventListener("orientationchange", lazyLoad);
24
}
25
}
26
});
27

28
active = false;
29
}, 200);
30
}
31
};
32

33
document.addEventListener("scroll", lazyLoad);
34
window.addEventListener("resize", lazyLoad);
35
window.addEventListener("orientationchange", lazyLoad);
36
});

詳情參考延遲加載圖像和視頻

大促活動實踐

2.1 懶加載與異步加載

懶加載與異步加載是大促活動性能優化的主要手段，直白的說就是把用戶不需要或者不會立即看到的頁面數據與內容全都挪到頁面首屏渲染完成之後去加載，極限減小頁面首屏渲染的數據加載量與js，css執行帶來的性能損耗。

2.1.1 導航下拉的異步加載

導航的下拉內容是一塊結構非常複雜的html片段，如果直接加載，瀏覽器渲染的時間會拖慢頁面整體的加載時間：

所有我們需要通過異步加載方式來獲取這段html片段，等頁面首屏渲染結束后再添加到頁面上,大致的代碼如下:

1
$.ajax({
2
url: url, async: false, timeout: 10000,
3
success: function (data) {
4
container.innerHTML = data;
5
var appendHtml = $('<div class="footer-wrapper">' + container.querySelector('#footer').innerHTML + '</div>');
6
var tempHtml = '<div style="display:none;">' + '<script type="text/html" id="header-lazyload-html-drop" class="header-lazyload-html" data-holder="#holder-drop">' + appendHtml.find('#header-lazyload-html-drop').html() + '<\/script><script type="text/html" id="header-lazyload-html-mbnav" class="header-lazyload-html" data-holder="#holder-mbnav">' + appendHtml.find('#header-lazyload-html-mbnav').html() + '<\/script></div>';
7
$('#footer').append(tempHtml);
8
feloader.onLoad(function () {
9
feloader.use('@cloud/common-resource/header', function () {
10
});
11
$('#footer').css('display', 'block');
12
});
13
},
14
error: function (XMLHttpRequest, textStatus, errorThrown) {
15
console.log(XMLHttpRequest.status, XMLHttpRequest.readyState, textStatus);
16
},
17
});

2.1.2 圖片懶加載

官網的cui套件中已經有lazyload的插件支持圖片懶加載,使用方法頁非常簡單：

1
<div class="list">
2
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/1" src="佔位圖片URL" />
3
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/2" src="佔位圖片URL" />
4
<img class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/3" src="佔位圖片URL" />
5
<div class="lazyload" data-src="http://www.placehold.it/375x200/eee/444/3"></div>
6
...
7
</div>

從代碼我們差不多可以猜出圖片懶加載的原理，其實就是我們通過覆蓋img標籤src屬性，使得img標籤開始加載時由於沒有src的具體圖片地址而不去加載圖片，等到重要資源加載完之後，通過監聽onload的時間或者滾動條的滾動時機再去重寫對應標籤的src值來達到圖片懶加載：

1
/**
2
* load image
3
* @param {HTMLElement} el - the image element
4
* @private
5
*/
6
_load(el) {
7
let source = el.getAttribute(ATTR_IMAGE_URL);
8
if (source) {
9
let processor = this._config.processor;
10
if (processor) {
11
source = processor(source, el);
12
}
13

14
el.addEventListener('load', () => {
15
el.classList.remove(CLASSNAME);
16
});
17
// 判斷是否是什麼元素
18
if (el.tagName === 'IMG') {
19
el.src = source;
20
} else {
21
// 判斷source是不是一個類名，如果是類名的話，則加到class裏面去
22
if (/^[A-Za-z0-9_-]+$/.test(source)) {
23
el.classList.add(source);
24
} else {
25
let styles = el.getAttribute('style') || '';
26
styles += `;background-image: url(${source});`;
27
el.setAttribute('style', styles);
28
el.style.backgroundImage = source; // = `background-image: url(${source});`;
29
}
30
}
31

32
el.removeAttribute(ATTR_IMAGE_URL);
33
}
34
}

具體的插件代碼大家可以查看https://git.huawei.com/cnpm/lazyload。

同時官網的頁腳部分也採用了採用其它的加載方式也實現了懶加載的效果，頁腳的圖片都在css中引用，想要延遲加載頁腳圖片就需要延遲加載頁腳的css，但是延遲加載css造成的後果就是頁面加載的一瞬間頁腳會因為樣式確實而显示錯亂，所以我們可以在css樣式加載前強勢隱藏掉頁腳部分，等css加載完成后,頁腳dom自帶的display:block會自動显示頁腳。（==因為頁腳的seo特性沒有對其進行懶加載==）

2.1.3 樓層內容的懶加載

基於xtpl自帶的懶加載能力，配合pep定製頁面模板的邏輯，我們可以實現html的懶加載。在頁面初次渲染的時候，只有每個樓層的大體框架和標題等關鍵信息，如果需要的話可以給默認圖片等佔位，或設置最小高度佔位，防止錨點定位失效。
當頁面滾動到該樓層的位置，js代碼方會執行，在初始化函數中，對該樓層的html進行加載，渲染，實現樓層圖片和html的懶加載，減少了首屏時間。
具體代碼如下：

1
<div class="nov-c6-cards j-content">
2
</div>

 

1
public render(){
2
this.$el.find('.j-content').html(new Xtemplate(tpl).render(mockData))
3
...
4
}

2.1.4 套餐數據懶加載

套餐數據的加載一直以來都是令人頭疼的，本次雙十一對於套餐腳本也做了優化，不僅對數據進行了緩存，同時也可以在指定的範圍進行套餐數據的渲染——和上述所說的樓層懶加載配合，可以做到未展示的樓層，套餐數據不請求，下拉框不渲染，詢價接口不調用，在首屏不出現大量套餐的情況下，可以大大提升首屏加載的性能。

2.2.資源整合

2.2.1.頁頭頁尾資源統一維護

基礎模板的優化涉及到資源的合併，壓縮與異步加載，dom的延遲加載和圖片的懶加載。首先我們給出官網基礎模板引用的一部分js資源的表格：

這部分js存在問題是分散在pep的各個資產庫路徑維護，有些壓縮了，有些沒有壓縮，js的加載也基本是順序執行，所以我們對這個部分的js和css資源進行了一個整合，進行的操作是遷移，合併，壓縮。

建立common-resource倉庫去統一維護管理頁頭頁腳及公共資源代碼。

2.2.2.合併加載方式相同的基礎功能js並壓縮

common.js

1
import './common/js/AGrid';
2
import './common/js/jquery.base64';
3
import './common/js/lang-tips';
4
import './common/js/setLocaleCookie';
5
import './common/js/pepDialog';

如上面代碼,將官網中用的分散的基礎功能js合併成一個common.js，經過伏羲流水線發布，cui套件會自動將js壓縮，這樣做的效果當然是減少官網頁面請求資源數，減小資源大小。

2.2.3.資源異步加載

觀察2.2.1中的表格可以發現，官網大部分js都是放在頭部或者是body后順序加載的，這些資源的加載時間必定是在DOMOnLoad之前

這些js都是會阻塞頁面的渲染，導致頁面首屏加載變慢，我們需要做的就是通過之前頭尾資源的整理得出哪些資源是可以在onload之後去加載的，這些我們就可以把頁面加載時不需要執行的js和css全部移到頁面渲染完成後去加載，少了這部分的js邏輯執行時的阻塞，頁面首屏渲染的時間也會大大降低。

通過cui套件中的feloader插件，我們可以比較便捷的控制js和css加載的時機：

1
feloader.onLoad(function () {
2
feloader.use([
3
'@cloud/link-to/index',
4
'@cloud/common-resource/uba',
5
'@cloud/common-resource/footer',
6
'@cloud/common-resource/header',
7
'@cloud/common-resource/common',
8
'@cloud/common-resource/prompt.css',
9
'@cloud/common-resource/footer.css',
10
]);
11
});

下圖可以明顯看到js的加載都轉移到onload之後了：

2.2.4 圖片壓縮

除了對設計給出的圖片有壓縮要求外，我們還通過對一部分不常更新的小圖標圖片進行base64編碼來減少頁面的圖片請求數量。

2.3預解析與預加載

除了延遲加載外，基礎模板還進行了諸如dns預解析，資源預加載的手段來提前解析dns和加載頁面資源。

2.3.1 DNS 預解析

當用戶訪問過官網頁面后，DNS預解析能夠使用戶在訪問雙十一活動頁之前提前進行DNS解析，從而減少雙十一活動頁面的dns解析時間，提高頁面的訪問性能，其實寫法也很簡單：

1
<link rel="dns-prefetch" href="//res.hc-cdn.com">
2
<link rel="dns-prefetch" href="//res-static1.huaweicloud.com">
3
<link rel="dns-prefetch" href="//res-static2.huaweicloud.com">
4
<link rel="dns-prefetch" href="//res-static3.huaweicloud.com">

2.3.2 preload 預加載

活動頁的部分js還使用了preload預加載的方式來提升頁面加載性能，preload的為什麼可以達到這種效果，我們需要看下面這段摘錄：

Preloader 簡介

HTML 解析器在創建 DOM 時如果碰上同步腳本（synchronous script)，解析器會停止創建 DOM，轉而去執行腳本。所以，如果資源的獲取只發生在解析器創建 DOM時，同步腳本的介入將使網絡處於空置狀態，尤其是對外部腳本資源來說，當然，頁面內的腳本有時也會導致延遲。

預加載器（Preloader）的出現就是為了優化這個過程，預加載器通過分析瀏覽器對 HTML 文檔的早期解析結果（這一階段叫做“令牌化（tokenization）”），找到可能包含資源的標籤（tag），並將這些資源的 URL 收集起來。令牌化階段的輸出將會送到真正的 HTML 解析器手中，而收集起來的資源 URLs 會和資源類型一起被送到讀取器（fetcher）手中，讀取器會根據這些資源對頁面加載速度的影響進行有次序地加載。

基於以上原理，我們對官網相對重要的js資源進行preload預加載，以使得瀏覽器可以儘快地加載頁面所需的重要資源。

1
<link rel="preload" href="//res.hc-cdn.com/cnpm-feloader/1.0.6/feloader.js" as="script"/>
2
<link rel="preload" href="//polyfill.alicdn.com/polyfill.min.js?features=default,es6" as="script"/>
3
<link rel="preload" href="https://res-static3.huaweicloud.com/content/dam/cloudbu-site/archive/commons/3rdlib/jquery/jquery-1.12.4.min.js" as="script"/>
4
<link rel="preload" href="//res.hc-cdn.com/cnpm-wpk-reporter/1.0.6/wpk-performance.js" as="script"/>
5

6
<link rel="preload" href="//res.hc-cdn.com/cpage-pep-2019nov-promotion/1.1.15/components/activity-banner/images/banner_mb.jpg" as="image" media="(max-width: 767px)">

優化效果

3.總結

前端性能優化的方法手段並不僅限於文章陳述，官網前端團隊還會在前端性能優化的道路上學習更多，探索更多，將華為雲官網頁面的加載性能做到極致！

 

點擊關注，第一時間了解華為雲新鮮技術~

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【【其他文章推薦】

※帶您來了解什麼是 USB CONNECTOR  ?

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※如何讓商品強力曝光呢? 網頁設計公司幫您建置最吸引人的網站，提高曝光率!

※綠能、環保無空污,成為電動車最新代名詞，目前市場使用率逐漸普及化

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

※教你寫出一流的銷售文案?

前言

計算機系統中有很多獨佔性的資源，在同一時刻只能每個資源只能由一個進程使用，我們之前經常提到過打印機，這就是一個獨佔性的資源，同一時刻不能有兩個打印機同時輸出結果，否則會引起文件系統的癱瘓。所以，操作系統具有授權一個進程單獨訪問資源的能力。

兩個進程獨佔性的訪問某個資源，從而等待另外一個資源的執行結果，會導致兩個進程都被阻塞，並且兩個進程都不會釋放各自的資源，這種情況就是 死鎖(deadlock)。

死鎖可以發生在任何層面，在不同的機器之間可能會發生死鎖，在數據庫系統中也會導致死鎖，比如進程 A 對記錄 R1 加鎖，進程 B 對記錄 R2 加鎖，然後進程 A 和 B 都試圖把對象的記錄加鎖，這種情況下就會產生死鎖。

下面我們就來討論一下什麼是死鎖、死鎖的條件是什麼、死鎖如何預防、活鎖是什麼等。

首先你需要先了解一個概念，那就是資源是什麼

資源

大部分的死鎖都和資源有關，在進程對設備、文件具有獨佔性（排他性）時會產生死鎖。我們把這類需要排他性使用的對象稱為資源(resource)。資源主要分為 可搶佔資源和不可搶佔資源

可搶佔資源和不可搶佔資源

資源主要有可搶佔資源和不可搶佔資源。可搶佔資源(preemptable resource) 可以從擁有它的進程中搶佔而不會造成其他影響，內存就是一種可搶佔性資源，任何進程都能夠搶先獲得內存的使用權。

不可搶佔資源(nonpreemtable resource) 指的是除非引起錯誤或者異常，否則進程無法搶佔指定資源，這種不可搶佔的資源比如有光盤，在進程執行調度的過程中，其他進程是不能得到該資源的。

死鎖與不可搶佔資源有關，雖然搶佔式資源也會造成死鎖，不過這種情況的解決辦法通常是在進程之間重新分配資源來化解。所以，我們的重點自然就會放在了不可搶佔資源上。

下面給出了使用資源所需事件的抽象順序

如果在請求時資源不存在，請求進程就會強制等待。在某些操作系統中，當請求資源失敗時進程會自動阻塞，當自資源可以獲取時進程會自動喚醒。在另外一些操作系統中，請求資源失敗並显示錯誤代碼，然後等待進程等待一會兒再繼續重試。

請求資源失敗的進程會陷入一種請求資源、休眠、再請求資源的循環中。此類進程雖然沒有阻塞，但是處於從目的和結果考慮，這類進程和阻塞差不多，因為這類進程並沒有做任何有用的工作。

請求資源的這個過程是很依賴操作系統的。在一些系統中，一個 request 系統調用用來允許進程訪問資源。在一些系統中，操作系統對資源的認知是它是一種特殊文件，在任何同一時刻只能被一個進程打開和佔用。資源通過 open 命令進行打開。如果文件已經正在使用，那麼這個調用者會阻塞直到當前的佔用文件的進程關閉文件為止。

資源獲取

對於一些數據庫系統中的記錄這類資源來說，應該由用戶進程來對其進行管理。有一種管理方式是使用信號量(semaphore) 。這些信號量會初始化為 1 。互斥鎖也能夠起到相同的作用。

這裏說一下什麼是互斥鎖(Mutexes):

在計算機程序中，互斥對象(mutex) 是一個程序對象，它允許多個程序共享同一資源，例如文件訪問權限，但並不是同時訪問。需要鎖定資源的線程都必須在使用資源時將互斥鎖與其他線程綁定（進行加鎖）。當不再需要數據或線程結束時，互斥鎖設置為解鎖。

下面是一個偽代碼，這部分代碼說明了信號量的資源獲取、資源釋放等操作，如下所示

typedef int semaphore;
semaphore aResource;

void processA(void){
  
  down(&aResource);
	useResource();
  up(&aResource);
  
}

上面显示了一個進程資源獲取和釋放的過程，但是一般情況下會存在多個資源同時獲取鎖的情景，這樣該如何處理？如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useAResource();
  useBResource();
  up(&aResource);
  up(&bResource);
  
}

對於單個進程來說，並不需要加鎖，因為不存在和這個進程的競爭條件。所以單進條件下程序能夠完好運行。

現在讓我們考慮兩個進程的情況，A 和 B ，還存在兩個資源。如下所示

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

在上述代碼中，兩個進程以相同的順序訪問資源。在這段代碼中，一個進程在另一個進程之前獲取資源，如果另外一個進程想在第一個進程釋放之前獲取資源，那麼它會由於資源的加鎖而阻塞，直到該資源可用為止。

在下面這段代碼中，有一些變化

typedef int semaphore;
semaphore aResource;
semaphore bResource;

void processA(void){
  
  down(&aResource);
  down(&bResource);
	useBothResource();
  up(&bResource);
  up(&aResource);
  
}

void processB(void){
  
  down(&bResource); // 變化的代碼 
  down(&aResource); // 變化的代碼
	useBothResource();
  up(&aResource); // 變化的代碼 
  up(&bResource); // 變化的代碼 
  
}

這種情況就不同了，可能會發生同時獲取兩個資源並有效地阻塞另一個過程，直到完成為止。也就是說，可能會發生進程 A 獲取資源 A 的同時進程 B 獲取資源 B 的情況。然後每個進程在嘗試獲取另一個資源時被阻塞。

在這裏我們會發現一個簡單的獲取資源順序的問題就會造成死鎖，所以死鎖是很容易發生的，所以下面我們就對死鎖做一個詳細的認識和介紹。

死鎖

如果要對死鎖進行一個定義的話，下面的定義比較貼切

如果一組進程中的每個進程都在等待一個事件，而這個事件只能由該組中的另一個進程觸發，這種情況會導致死鎖。

簡單一點來表述一下，就是每個進程都在等待其他進程釋放資源，而其他資源也在等待每個進程釋放資源，這樣沒有進程搶先釋放自己的資源，這種情況會產生死鎖，所有進程都會無限的等待下去。

換句話說，死鎖進程結合中的每個進程都在等待另一個死鎖進程已經佔有的資源。但是由於所有進程都不能運行，它們之中任何一個資源都無法釋放資源，所以沒有一個進程可以被喚醒。這種死鎖也被稱為資源死鎖(resource deadlock)。資源死鎖是最常見的類型，但不是所有的類型，我們後面會介紹其他類型，我們先來介紹資源死鎖

資源死鎖的條件

針對我們上面的描述，資源死鎖可能出現的情況主要有

• 互斥條件：每個資源都被分配給了一個進程或者資源是可用的
• 保持和等待條件：已經獲取資源的進程被認為能夠獲取新的資源
• 不可搶佔條件：分配給一個進程的資源不能強制的從其他進程搶佔資源，它只能由佔有它的進程显示釋放
• 循環等待：死鎖發生時，系統中一定有兩個或者兩個以上的進程組成一個循環，循環中的每個進程都在等待下一個進程釋放的資源。

發生死鎖時，上面的情況必須同時會發生。如果其中任意一個條件不會成立，死鎖就不會發生。可以通過破壞其中任意一個條件來破壞死鎖，下面這些破壞條件就是我們探討的重點

死鎖模型

Holt 在 1972 年提出對死鎖進行建模，建模的標準如下：

• 圓形表示進程
• 方形表示資源

從資源節點到進程節點表示資源已經被進程佔用，如下圖所示

在上圖中表示當前資源 R 正在被 A 進程所佔用

由進程節點到資源節點的有向圖表示當前進程正在請求資源，並且該進程已經被阻塞，處於等待這個資源的狀態

在上圖中，表示的含義是進程 B 正在請求資源 S 。Holt 認為，死鎖的描述應該如下

這是一個死鎖的過程，進程 C 等待資源 T 的釋放，資源 T 卻已經被進程 D 佔用，進程 D 等待請求佔用資源 U ，資源 U 卻已經被線程 C 佔用，從而形成環。

總結一點：吃着碗里的看着鍋里的容易死鎖

那麼如何避免死鎖呢？我們還是通過死鎖模型來聊一聊

假設有三個進程 (A、B、C) 和三個資源(R、S、T) 。三個進程對資源的請求和釋放序列如下圖所示

操作系統可以任意選擇一個非阻塞的程序運行，所以它可以決定運行 A 直到 A 完成工作；它可以運行 B 直到 B 完成工作；最後運行 C。

這樣的順序不會導致死鎖（因為不存在對資源的競爭），但是這種情況也完全沒有并行性。進程除了在請求和釋放資源外，還要做計算和輸入/輸出的工作。當進程按照順序運行時，在等待一個 I/O 時，另一個進程不能使用 CPU。所以，嚴格按照串行的順序執行並不是最優越的。另一方面，如果沒有進程在執行任何 I/O 操作，那麼最短路徑優先作業會優於輪轉調度，所以在這種情況下串行可能是最優越的

現在我們假設進程會執行計算和 I/O 操作，所以輪詢調度是一種合理的調度算法。資源請求可能會按照下面這個順序進行

下圖是針對上面這六個步驟的資源分配圖。

這裏需要注意一個問題，為什麼從資源出來的有向圖指向了進程卻表示進程請求資源呢？筆者剛開始看也有這個疑問，但是想了一下這個意思解釋為進程佔用資源比較合適，而進程的有向圖指向資源表示進程被阻塞的意思。

在上面的第四個步驟，進程 A 正在等待資源 S；第五個步驟中，進程 B 在等待資源 T；第六個步驟中，進程 C 在等待資源 R，因此產生了環路並導致了死鎖。

然而，操作系統並沒有規定一定按照某種特定的順序來執行這些進程。遇到一個可能會引起死鎖的線程后，操作系統可以乾脆不批准請求，並把進程掛起一直到安全狀態為止。比如上圖中，如果操作系統認為有死鎖的可能，它可以選擇不把資源 S 分配給 B ，這樣 B 被掛起。這樣的話操作系統會只運行 A 和 C，那麼資源的請求和釋放就會是下面的步驟

下圖是針對上面這六個步驟的資源分配圖。

在第六步執行完成后，可以發現並沒有產生死鎖，此時就可以把資源 S 分配給 B，因為 A 進程已經執行完畢，C 進程已經拿到了它想要的資源。進程 B 可以直接獲得資源 S，也可以等待進程 C 釋放資源 T 。

有四種處理死鎖的策略：

• 忽略死鎖帶來的影響（驚呆了）
• 檢測死鎖並回復死鎖，死鎖發生時對其進行檢測，一旦發生死鎖后，採取行動解決問題
• 通過仔細分配資源來避免死鎖
• 通過破壞死鎖產生的四個條件之一來避免死鎖

下面我們分別介紹一下這四種方法

鴕鳥算法

最簡單的解決辦法就是使用鴕鳥算法(ostrich algorithm)，把頭埋在沙子里，假裝問題根本沒有發生。每個人看待這個問題的反應都不同。數學家認為死鎖是不可接受的，必須通過有效的策略來防止死鎖的產生。工程師想要知道問題發生的頻次，系統因為其他原因崩潰的次數和死鎖帶來的嚴重後果。如果死鎖發生的頻次很低，而經常會由於硬件故障、編譯器錯誤等其他操作系統問題導致系統崩潰，那麼大多數工程師不會修復死鎖。

死鎖檢測和恢復

第二種技術是死鎖的檢測和恢復。這種解決方式不會嘗試去阻止死鎖的出現。相反，這種解決方案會希望死鎖盡可能的出現，在監測到死鎖出現后，對其進行恢復。下面我們就來探討一下死鎖的檢測和恢復的幾種方式

每種類型一個資源的死鎖檢測方式

每種資源類型都有一個資源是什麼意思？我們經常提到的打印機就是這樣的，資源只有打印機，但是設備都不會超過一個。

可以通過構造一張資源分配表來檢測這種錯誤，比如我們上面提到的

的算法來檢測從 P1 到 Pn 這 n 個進程中的死鎖。假設資源類型為 m，E1 代表資源類型1，E2 表示資源類型 2 ，Ei 代表資源類型 i (1 <= i <= m)。E 表示的是 現有資源向量(existing resource vector)，代表每種已存在的資源總數。

現在我們就需要構造兩個數組：C 表示的是當前分配矩陣(current allocation matrix) ，R 表示的是 請求矩陣(request matrix)。Ci 表示的是 Pi 持有每一種類型資源的資源數。所以，Cij 表示 Pi 持有資源 j 的數量。Rij 表示 Pi 所需要獲得的資源 j 的數量

一般來說，已分配資源 j 的數量加起來再和所有可供使用的資源數相加 = 該類資源的總數。

死鎖的檢測就是基於向量的比較。每個進程起初都是沒有被標記過的，算法會開始對進程做標記，進程被標記后說明進程被執行了，不會進入死鎖，當算法結束時，任何沒有被標記過的進程都會被判定為死鎖進程。

上面我們探討了兩種檢測死鎖的方式，那麼現在你知道怎麼檢測后，你何時去做死鎖檢測呢？一般來說，有兩個考量標準：

• 每當有資源請求時就去檢測，這種方式會佔用昂貴的 CPU 時間。
• 每隔 k 分鐘檢測一次，或者當 CPU 使用率降低到某個標準下去檢測。考慮到 CPU 效率的原因，如果死鎖進程達到一定數量，就沒有多少進程可以運行，所以 CPU 會經常空閑。

從死鎖中恢復

上面我們探討了如何檢測進程死鎖，我們最終的目的肯定是想讓程序能夠正常的運行下去，所以針對檢測出來的死鎖，我們要對其進行恢復，下面我們會探討幾種死鎖的恢復方式

通過搶佔進行恢復

在某些情況下，可能會臨時將某個資源從它的持有者轉移到另一個進程。比如在不通知原進程的情況下，將某個資源從進程中強製取走給其他進程使用，使用完后又送回。這種恢復方式一般比較困難而且有些簡單粗暴，並不可取。

通過回滾進行恢復

如果系統設計者和機器操作員知道有可能發生死鎖，那麼就可以定期檢查流程。進程的檢測點意味着進程的狀態可以被寫入到文件以便後面進行恢復。檢測點不僅包含存儲映像(memory image)，還包含資源狀態(resource state)。一種更有效的解決方式是不要覆蓋原有的檢測點，而是每出現一個檢測點都要把它寫入到文件中，這樣當進程執行時，就會有一系列的檢查點文件被累積起來。

為了進行恢復，要從上一個較早的檢查點上開始，這樣所需要資源的進程會回滾到上一個時間點，在這個時間點上，死鎖進程還沒有獲取所需要的資源，可以在此時對其進行資源分配。

殺死進程恢復

最簡單有效的解決方案是直接殺死一個死鎖進程。但是殺死一個進程可能照樣行不通，這時候就需要殺死別的資源進行恢復。

另外一種方式是選擇一個環外的進程作為犧牲品來釋放進程資源。

死鎖避免

我們上面討論的是如何檢測出現死鎖和如何恢復死鎖，下面我們探討幾種規避死鎖的方式

單個資源的銀行家算法

銀行家算法是 Dijkstra 在 1965 年提出的一種調度算法，它本身是一種死鎖的調度算法。它的模型是基於一個城鎮中的銀行家，銀行家向城鎮中的客戶承諾了一定數量的貸款額度。算法要做的就是判斷請求是否會進入一種不安全的狀態。如果是，就拒絕請求，如果請求后系統是安全的，就接受該請求。

比如下面的例子，銀行家一共為所有城鎮居民提供了 15 單位個貸款額度，一個單位表示 1k 美元，如下所示

城鎮居民都喜歡做生意，所以就會涉及到貸款，每個人能貸款的最大額度不一樣，在某一時刻，A/B/C/D 的貸款金額如下

上面每個人的貸款總額加起來是 13，馬上接近 15，銀行家只能給 A 和 C 進行放貸，可以拖着 B 和 D、所以，可以讓 A 和 C 首先完成，釋放貸款額度，以此來滿足其他居民的貸款。這是一種安全的狀態。

如果每個人的請求導致總額會超過甚至接近 15 ，就會處於一種不安全的狀態，如下所示

這樣，每個人還能貸款至少 2 個單位的額度，如果其中有一個人發起最大額度的貸款請求，就會使系統處於一種死鎖狀態。

這裏注意一點：不安全狀態並不一定引起死鎖，由於客戶不一定需要其最大的貸款額度，但是銀行家不敢抱着這種僥倖心理。

銀行家算法就是對每個請求進行檢查，檢查是否請求會引起不安全狀態，如果不會引起，那麼就接受該請求；如果會引起，那麼就推遲該請求。

類似的，還有多個資源的銀行家算法，讀者可以自行了解。

破壞死鎖

死鎖本質上是無法避免的，因為它需要獲得未知的資源和請求，但是死鎖是滿足四個條件后才出現的，它們分別是

• 互斥
• 保持和等待
• 不可搶佔
• 循環等待

我們分別對這四個條件進行討論，按理說破壞其中的任意一個條件就能夠破壞死鎖

破壞互斥條件

我們首先考慮的就是破壞互斥使用條件。如果資源不被一個進程獨佔，那麼死鎖肯定不會產生。如果兩個打印機同時使用一個資源會造成混亂，打印機的解決方式是使用 假脫機打印機(spooling printer) ，這項技術可以允許多個進程同時產生輸出，在這種模型中，實際請求打印機的唯一進程是打印機守護進程，也稱為後台進程。後台進程不會請求其他資源。我們可以消除打印機的死鎖。

後台進程通常被編寫為能夠輸出完整的文件后才能打印，假如兩個進程都佔用了假脫機空間的一半，而這兩個進程都沒有完成全部的輸出，就會導致死鎖。

因此，盡量做到盡可能少的進程可以請求資源。

破壞保持等待的條件

第二種方式是如果我們能阻止持有資源的進程請求其他資源，我們就能夠消除死鎖。一種實現方式是讓所有的進程開始執行前請求全部的資源。如果所需的資源可用，進程會完成資源的分配並運行到結束。如果有任何一個資源處於頻繁分配的情況，那麼沒有分配到資源的進程就會等待。

很多進程無法在執行完成前就知道到底需要多少資源，如果知道的話，就可以使用銀行家算法；還有一個問題是這樣無法合理有效利用資源。

還有一種方式是進程在請求其他資源時，先釋放所佔用的資源，然後再嘗試一次獲取全部的資源。

破壞不可搶佔條件

破壞不可搶佔條件也是可以的。可以通過虛擬化的方式來避免這種情況。

破壞循環等待條件

現在就剩最後一個條件了，循環等待條件可以通過多種方法來破壞。一種方式是制定一個標準，一個進程在任何時候只能使用一種資源。如果需要另外一種資源，必須釋放當前資源。對於需要將大文件從磁帶複製到打印機的過程，此限制是不可接受的。

另一種方式是將所有的資源統一編號，如下圖所示

進程可以在任何時間提出請求，但是所有的請求都必須按照資源的順序提出。如果按照此分配規則的話，那麼資源分配之間不會出現環。

儘管通過這種方式來消除死鎖，但是編號的順序不可能讓每個進程都會接受。

其他問題

下面我們來探討一下其他問題，包括 通信死鎖、活鎖是什麼、飢餓問題和兩階段加鎖

兩階段加鎖

雖然很多情況下死鎖的避免和預防都能處理，但是效果並不好。隨着時間的推移，提出了很多優秀的算法用來處理死鎖。例如在數據庫系統中，一個經常發生的操作是請求鎖住一些記錄，然後更新所有鎖定的記錄。當同時有多個進程運行時，就會有死鎖的風險。

一種解決方式是使用 兩階段提交(two-phase locking)。顧名思義分為兩個階段，一階段是進程嘗試一次鎖定它需要的所有記錄。如果成功后，才會開始第二階段，第二階段是執行更新並釋放鎖。第一階段並不做真正有意義的工作。

如果在第一階段某個進程所需要的記錄已經被加鎖，那麼該進程會釋放所有鎖定的記錄並重新開始第一階段。從某種意義上來說，這種方法類似於預先請求所有必需的資源或者是在進行一些不可逆的操作之前請求所有的資源。

不過在一般的應用場景中，兩階段加鎖的策略並不通用。如果一個進程缺少資源就會半途中斷並重新開始的方式是不可接受的。

通信死鎖

我們上面一直討論的是資源死鎖，資源死鎖是一種死鎖類型，但並不是唯一類型，還有通信死鎖，也就是兩個或多個進程在發送消息時出現的死鎖。進程 A 給進程 B 發了一條消息，然後進程 A 阻塞直到進程 B 返迴響應。假設請求消息丟失了，那麼進程 A 在一直等着回復，進程 B 也會阻塞等待請求消息到來，這時候就產生死鎖。

儘管會產生死鎖，但是這並不是一個資源死鎖，因為 A 並沒有佔據 B 的資源。事實上，通信死鎖並沒有完全可見的資源。根據死鎖的定義來說：每個進程因為等待其他進程引起的事件而產生阻塞，這就是一種死鎖。相較於最常見的通信死鎖，我們把上面這種情況稱為通信死鎖(communication deadlock)。

通信死鎖不能通過調度的方式來避免，但是可以使用通信中一個非常重要的概念來避免：超時(timeout)。在通信過程中，只要一個信息被發出后，發送者就會啟動一個定時器，定時器會記錄消息的超時時間，如果超時時間到了但是消息還沒有返回，就會認為消息已經丟失並重新發送，通過這種方式，可以避免通信死鎖。

但是並非所有網絡通信發生的死鎖都是通信死鎖，也存在資源死鎖，下面就是一個典型的資源死鎖。

當一個數據包從主機進入路由器時，會被放入一個緩衝區，然後再傳輸到另外一個路由器，再到另一個，以此類推直到目的地。緩衝區都是資源並且數量有限。如下圖所示，每個路由器都有 10 個緩衝區（實際上有很多）。

假如路由器 A 的所有數據需要發送到 B ，B 的所有數據包需要發送到 D，然後 D 的所有數據包需要發送到 A 。沒有數據包可以移動，因為在另一端沒有緩衝區可用，這就是一個典型的資源死鎖。

活鎖

你會發現一個很有意思的事情，死鎖就跟榆木腦袋一樣，不會轉彎。我看過古代的一則故事：

如果說死鎖很痴情的話，那麼活鎖用一則成語來表示就是 弄巧成拙。

某些情況下，當進程意識到它不能獲取所需要的下一個鎖時，就會嘗試禮貌的釋放已經獲得的鎖，然後等待非常短的時間再次嘗試獲取。可以想像一下這個場景：當兩個人在狹路相逢的時候，都想給對方讓路，相同的步調會導致雙方都無法前進。

現在假想有一對并行的進程用到了兩個資源。它們分別嘗試獲取另一個鎖失敗后，兩個進程都會釋放自己持有的鎖，再次進行嘗試，這個過程會一直進行重複。很明顯，這個過程中沒有進程阻塞，但是進程仍然不會向下執行，這種狀況我們稱之為 活鎖(livelock)。

飢餓

與死鎖和活鎖的一個非常相似的問題是 飢餓(starvvation)。想象一下你什麼時候會餓？一段時間不吃東西是不是會餓？對於進程來講，最重要的就是資源，如果一段時間沒有獲得資源，那麼進程會產生飢餓，這些進程會永遠得不到服務。

我們假設打印機的分配方案是每次都會分配給最小文件的進程，那麼要打印大文件的進程會永遠得不到服務，導致進程飢餓，進程會無限制的推后，雖然它沒有阻塞。

總結

死鎖是一類通用問題，任何操作系統都會產生死鎖。當每一組進程中的每個進程都因等待由該組的其他進程所佔有的資源而導致阻塞，死鎖就發生了。這種情況會使所有的進程都處於無限等待的狀態。

死鎖的檢測和避免可以通過安全和不安全狀態來判斷，其中一個檢測方式就是銀行家算法；當然你也可以使用鴕鳥算法對死鎖置之不理，但是你肯定會遭其反噬。

也可以在設計時通過系統結構的角度來避免死鎖，這樣能夠預防死鎖；也可以破壞死鎖的四個條件來破壞死鎖。資源死鎖並不是唯一性的死鎖，還有通信間死鎖，可以設置適當的超時時間來完成。

活鎖和死鎖的問題有些相似，它們都是一種進程無法繼續向下執行的狀態。由於進程調度策略導致嘗試獲取進程的一方永遠無法獲得資源后，進程會導致飢餓的出現。

尾聲

提出一個勘誤，已反饋給出版社

關於我

我自己現在寫了三本 PDF，讀者回復都非常不錯，現在免費分享出來，關注我的公眾號即可領取

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

※USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

※台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨，RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準