標籤: 南投搬家公司費用

深入解讀Dictionary

文章作者作者: admin
文章發佈日期 2020-07-13

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個步驟：

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

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

添加第二個元素

dictionary.Add(7, "xyxy");

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

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

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

添加第三個元素

dictionary.Add(2, "xyxy");

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

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

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

添加第四個元素

dictionary.Add(4, "xyxy");

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

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

數組擴容

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

擴容步驟：

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

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

添加元素

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

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

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

整數4計算的hashcode是4；
hashcode取低31位數值為4（計算公式：hashcode & 0x7FFFFFFF=4）；
該key的hashcode落到bucket下標為4的位置（計算公式：hashCode % buckets.Length=4）；
將hashcode、key、value包裝起來；（封裝到entries數組下標為3的結構體中)；
原bucket[4]上為-1，所以當前節點下並沒有鏈表，設置當前結構體的Entry.next為-1；
設置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網頁設計為架站首選

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

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

※回頭車貨運收費標準

標籤 USB CONNECTOR , 南投搬家公司費用, 台北網頁設計, 新北清潔, 網站設計, 貨運

發燒車訊

無視巴黎氣候協定全球化石燃料產量遠高於限制

文章作者作者: admin
文章發佈日期 2020-07-10

摘錄自2019年11月20日中央通訊社報導

聯合國和頂尖研究團體今天（20日）發布報告警告，全球已規劃或準備進行的石油、天然氣和煤炭產量，將遠遠超越抑制全球暖化讓地球維持適合人居所需的產量目標。

聯合國環境規劃署（UN Environment Programme）和4個氣候變遷研究中心聯合發布報告指出，全球預計生產的化石燃料總量，較為了讓地表溫度較工業革命前水準升高不超過攝氏2度所容許的燃燒量，超出達50%。

若將地表升溫幅度限制在攝氏1.5度，則計劃中的化石燃料產量將較容許數量超出1倍多。2015年達成的巴黎氣候協定，要求將全球暖化限制在遠低於攝氏2度水準，可能的話僅升溫攝氏1.5度。

儘管截至目前全球僅升溫攝氏1度，但全世界已出現逐漸增強的致命熱浪、洪災和超級風暴，而超級風暴因海平面加速上升而破壞力更強大。研究人員警告，煤炭、石油和天然氣供應的「過度投資」，與未來數十年必須大幅縮減溫室氣體排放的目標，兩者直接相衝突。

聯合國去年發布的報告斷定，若要抑制地表升溫僅攝氏1.5度，則全球二氧化碳排放必須在2030年底前減少45%，並於2050年底前達到「淨零排放」。

斯德哥爾摩環境研究所（Stockholm Environment Institute）美國中心主任賴薩魯斯（Michael Lazarus）表示：「我們首次展現，巴黎（氣候協定的）溫度目標，和各國煤炭、石油和天然氣的生產計畫及政策，兩者間落差有多巨大。」

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

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

※回頭車貨運收費標準

標籤 USB CONNECTOR , 南投搬家公司費用, 台北網頁設計, 新北清潔, 網站設計, 貨運

發燒車訊

寫給大忙人看的死鎖全詳解

文章作者作者: admin
文章發佈日期 2020-07-09

前言

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

兩個進程獨佔性的訪問某個資源，從而等待另外一個資源的執行結果，會導致兩個進程都被阻塞，並且兩個進程都不會釋放各自的資源，這種情況就是 死鎖(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網頁設計為架站首選

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

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

※回頭車貨運收費標準

標籤 USB CONNECTOR , 南投搬家公司費用, 台北網頁設計, 新北清潔, 網站設計, 貨運

發燒車訊

澳洲森林大火空污程度空前

文章作者作者: admin
文章發佈日期 2020-07-08

摘錄自2019年11月22日中央通訊社澳洲報導

澳洲新南威爾斯省遍布森林野火，飄散出的煙霧使今天（22日）空污程度空前，造成就醫人數激增，並引起駕駛人視線不良等危險。

澳洲人口第一大城雪梨（Sydney）已連續4天被煙霧籠罩，罕見但一再成為世界空污最嚴重的10大城市之一。近幾天來某些時候，全球城市空氣品質監測網站Air Visual排行顯示，雪梨名列世界空污最嚴重的第8大城市，排名在雅加達及深圳之前，位居孟買之後。

隨著強風吹送林火煙霧以及因全澳3年乾旱而堆積的灰塵，波克鎮的空污比安全標準高出15倍。煙霾挾帶著來懸浮微粒污染物，形成官員所說新南威爾斯省紀錄中的最嚴重污染。這種粒子會被人體吸入血液中。

大火迄今仍在新南威爾斯省、維多利亞省（Victoria）、南澳省（South Australia）及昆士蘭省（Queensland）燃燒。澳洲總理莫里森（Scott Morrison）因為這次危機而受到壓力，批評者指稱，莫里森並未盡力處理氣候變遷的衝擊。氣象學家則指出，氣候變遷正導致野火季節的時間延長。

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

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

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

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

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

標籤 USB CONNECTOR , 南投搬家公司費用, 台北網頁設計, 新北清潔, 網站設計

發燒車訊

Tesla 挹注擴大 F-貿聯第三季營收季增幅度大

文章作者作者: admin
文章發佈日期 2020-07-07

Tesla 日前發表的儲能電池計畫，受到外界關注，法人評估，首波供應商 F-貿聯最快 8 月有機會開始交貨，明年下半年新計畫挹注逐步擴大。法人也預估，該公司本季營收季增個位數、且將挑戰單季新高，第三季起隨 Tesla 新 SUV 車款問世，6 月下旬起零件逐月放量，下季營收季增幅度將拉大，全年營收拚增兩位數。 F-貿聯與 Tesla 的往來關係深厚，早在 Tesla 還未成為全球知名的電動車大廠前，就已相互搭配，因此也成為該客戶的指標核心供應商。一直以來，貿聯較為人熟知是 Tesla 電動車電池管理系統線束的獨家供應商，此次配合與松下合資的超級電池工廠明年下半年量產，電池供應量將大增。據了解，F-貿聯已是特斯拉除能電池系統 Powerwall 與企業用 Powerpack 計畫的首波零件供應商，供貨品項仍為電池管理系統用線。法人預期，最快 8 月有望正式交貨，雖對今年的營收貢獻不大，但更確認了貿聯在 Tesla 各項計畫共同開發的核心地位，而明年下半年超級電池工廠如果順利量產，該計畫的挹注將明顯增溫。

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔

發燒車訊

三次握手四次揮手

文章作者作者: admin
文章發佈日期 2020-07-06

一直都知道 TCP 建立連接時需要三次握手，釋放連接時需要四次揮手，也大概能說出整個過程，但是一直對其中的設計思想理解不深，停留在“只可意會，不可言傳”的階段。這次寫一篇博客嘗試將其中的思想表達出來。

TCP 建連三次握手

首先解釋一下每個步驟的作用：
1、a 時刻，A 準備就緒，發送 SYN 包給 B，嘗試建立連接
2、b 時刻，B 收到 A 發來的 SYN 包，知道 A 要請求建連，回 SYN ACK 包，告訴 A 自己收到了建連請求，可以建連了
3、c 時刻，A 收到了 B 的回復，知道 B 準備好了，鏈路通暢，可以發送數據了。回 ACK 告知 B 收到了 B 的回復，下面要開始發送該數據了
4、d 時刻，B 收到了 A 的回復，知道 A 接下來要發數據了。至此，AB 雙方都確認整個鏈路已經可靠了，接下來可以發送數據了。

為什麼要多次確認呢？為什麼不可以 A 上來就直接發送數據給 B 呢？
這裏首先要明確一點，TCP 是傳輸層的協議，是建立在物理層、數據鏈路層、網絡層之上的協議，而底層的網絡是不可靠的，可能路由出問題，可能網關出問題，可能網線出問題，A 沒法保證自己發出來的消息 B 一定能收到，所以一定要反饋機制，即 ACK，這樣才能在不可靠的網絡層智商構建可靠的傳輸層。

類比一下生活中的例子，可以幫助我們理解
示例1，假設我們在火車上打電話，通話質量很差，我們的通話過程可能會是下面這樣：

AB 雙方首先需要確認彼此都能挺到對方的聲音，也就是保證電話通道是可靠的，之後才會開始說正事。如果一上來就直接說正事，可能 A 說完之後 B 根本就沒有聽到。
實際打電話過程中，如果遇到了斷線的情況，雙方可能需要進行多次“握手”確認。

示例2，假設我們給剛認識的人第一次打電話，通話過程可能是下面這樣：

AB 雙方都要確認對方的身份，也就是保證通話是在跟自己人進行，確保電話通道是可靠的，不是跟騙子通話，然後才會開始說正事。如果一上來沒有確認身份，不能保證通道是跟自己人進行的，那直接說出重要的事，很可能就泄漏了機密。

總之，握手過程的最終目的就是保證雙方都準備就緒，通路是可靠的，之後就可以放心的發送重要數據了。

那為什麼一定是三次呢，為什麼不是兩次或者四次呢？
先來說一下為什麼不能少。
一次可以嗎？不可以。設想一下，A 對 B 說：我要給你發數據。然後不等 B 的回復，接下來就開始發數據了。這時候根本不能保證 B 已經準備好了，那 A 發出來的數據就沒法保證 B 一定能收到。聯想生活中的場景，你隔着很遠的距離向對方喊話：我要把蘋果扔給你。然後不關心對方有沒有聽到，就直接扔了，那最終的結果通常就是對方接不到蘋果，因為對方可能根本沒有收到消息。
兩次可以嗎？不可以。設想一下，A 對 B 說：我要給你發數據，然後 B 收到消息后給 A 回復：收到，A 在收到 B 的回復后開始發送數據。這時候 A 端是可以準備就緒的，但是 B 端不知道 A 端當前的狀態。因為 B 在收到 A 的消息的時候，可能已經過去了很長時間，B 在回消息的時候，A 可能已經不在線了，此時 B 是不能直接發數據的。如果 A 再給 B 回一個 ACK，B 就可以確認當前鏈路狀態了，這就變成了三次握手。

接下來說一下為什麼不是四次。既然三次已經可以保證建立可靠通信，就不需要額外的一次交互了。

下面是幾個生活中相關的示例：

TCP 斷鏈四次揮手
1、a 時刻，A 向 B 發出 FIN 包，表示自己沒有數據要發送了
2、b 時刻，B 收到 FIN 包，回復 FIN ACK，表示收到了 A 的 FIN 包，不會再接收 A 的數據了
3、B 在發完 FIN ACK 后，可能還有數據要發給 A，這個數據是不能停止發送的，有數據還是需要繼續發送
4、d 時刻，B 發完了數據，也發出 FIN 包，告訴 A 自己的數據發完了，不再發送數據了
5、e 時刻，A 收到了 B 的 FIN 包，知道 B 也沒有數據要發送了，回復 FIN ACK。此時，連接可以斷開了

建連只需要交互三次，斷連卻需要四次，這是為什麼呢？其實斷開連接和建立連接還是不一樣的。建連的時候，只要雙方都告知對方自己準備好了就可以，但是斷連的時候，一方提出要斷開連接，不再發數據，另一方不能立即斷開，因為這一方可能還有數據要發送，直到數據全部發送完成后才能確認斷開。

下面是幾個生活中相關的示例：

以上是對於三次握手、四次揮手的簡單介紹，裏面沒有更詳細的狀態介紹，之後的博客會介紹，這裏先放兩張圖。
TCP 三次握手

TCP 四次揮手

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

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔

發燒車訊

老當益壯顯身手——記安徽省黃山市市場監管局綜合行政執法支隊恭弘=叶恭弘建德

文章作者作者: admin
文章發佈日期 2020-07-03

　　“12315嗎？我要投訴，屯溪區益康堂大藥房賣的飄安口罩生產日期有問題。”1月24日大年三十晚上，安徽省黃山市市場監管局接到了一個投訴。

　　領到任務的是該局綜合行政執法支隊主要負責人恭弘=叶恭弘建德。今年58歲的恭弘=叶恭弘建德是一名經驗豐富的市場監管老兵，深知執法辦案行動迅速的重要性。1月25日8：00，他和辦案人員便出現在藥房門口。

　　9：00，藥房一開門，辦案人員便現場檢查，查獲標註生產日期為2020年2月2日、2月6日的“飄安”口罩各5包。

　　恭弘=叶恭弘建德說，稍遲一步，這10包“早產”口罩就可能被買走。“沒有實物，就無法繼續辦案。”他說。

　　1月27日，在接到飄安集團出具的“這批口罩是假冒產品”的鑒別意見后，他又果斷決定啟動行刑銜接機制，及時調整辦案思路，移交公安機關先行偵辦。

　　在查處另一起假“民樂”口罩案時，恭弘=叶恭弘建德與執法人員第一時間趕到被舉報的藥房，卻沒查到實物。他們當機立斷，火速趕到批發這批口罩的黃山博宏醫藥銷售公司，查獲一個空外包裝紙箱和某醫院退回的10包口罩。“稍微一猶豫，可能就會空手而回。” 恭弘=叶恭弘建德說。

　　同事們都說，敢於克難是恭弘=叶恭弘建德辦案的一大特點。查辦假“民樂”口罩案時，消費者質疑口罩質量有問題，但銷售方出具了一家正規醫藥銷售公司的銷售單據、質檢報告。恭弘=叶恭弘建德和辦案人員並未被表面證據迷惑，立即聯繫生產廠家新鄉華康衛材有限公司。

　　“肯定是假冒產品。”廠家負責人通過對比上傳的產品及合格證圖片后，出具了鑒別意見，成為案件定性的重要證據。

　　“我們這裏藥房賣的飄安口罩可能也是假的。”益康堂大藥房銷售假“飄安”口罩被查處后，市場監管局也接到了其他消費者舉報。

　　群眾的呼聲就是行動的號角。恭弘=叶恭弘建德與辦案人員齊心協力，有訴必查、有查必果。之後，他們又查處了5起藥房銷售假“飄安”口罩案。

　　由於率先查處了假“飄安”口罩案和案值18.9萬元的假“民樂”口罩案，不少媒體紛紛報道，恭弘=叶恭弘建德成了“名人”。北京密雲、貴州六盤水、山東德州及本省其他地區市場監管部門紛紛向他請教，每次他都毫無保留，及時與同行分享辦案經驗。

　　由於假“飄安”、假“民樂”口罩數量達20多萬隻，恭弘=叶恭弘建德和辦案人員及時約談藥房經營者，要求其無條件全額退款。經過多日努力，購買假“飄安”口罩消費者的全部退款訴求均已解決。（鞠萱）

責任編輯：邊靜

本站聲明:網站內容來源再生能源資訊網http://www.ccn.com.cn/,如有侵權請聯繫我們,我們將及時處理

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔

發燒車訊

智慧充電管理軟體真的有效，加州電動交通車隊省下 40% 電費

文章作者作者: admin
文章發佈日期 2020-07-02

隨著綠能推展，全球無數新創事業應運而生，宣稱智慧軟體能在能源多元化時代為顧客省錢，也包括電動車隊的智慧充電管理系統，這些系統真能達到宣稱的效益嗎？如今第一波實際使用的成果已逐漸顯現。新創事業 Amply Power 於 2020 年 4 月發表系統應用於北加州康特拉科斯塔郡 Tri Delta 交通車隊電動車的成效，自 2020 年初以來，為車隊節省了 40% 電費。

隨著都市市區環保意識上升，以及各國推動減碳，加上電池降價使得電動車購置成本降低，越來越多公車與交通車隊改用電動車，目前全球有超過 200 家交通車隊採用電動車，並預計到 2025 年電動巴士將占全球交通車隊 30%。

Tri Delta 早在 2018 年就已經開始加入潮流，當時只先測試 4 輛電動車，2 輛來自比亞迪、2 輛來自加州電動巴士廠 Proterra，即使只是先測試 4 輛，對車隊的後勤作業就造成相當大的改變。少了 4 輛車需要柴油與一般引擎車的維修，但多出與電力公司交涉、升級變電器、安裝高壓電力裝置等任務，僅 4 輛車就導致最高電力需求負載高達 300 千瓦，這下突然得處理很多過去不曾想過的電力節費問題。

於是 2019 年底 Tri Delta 決定採用 Amply Power 的智慧充電管理軟體，由軟體管理充電時間，挑選電費較低的離峰時間充電，以節省電費，但又同時確保要用車的時候電力有充飽，車隊後勤人員不再需要思考何時插上充電座比較省錢，讓軟體決定就好了。此外，改採電動車之後，最大的困擾就是一旦充電沒有插好，等到隔天要用車，車子沒電才發現，就會造成調度嚴重問題，使用充電管理軟體後，充電若沒插好，軟體會發出警告，一勞永逸解決了這個防呆問題。

充電管理結果能否擴大適用還待驗證

使用充電管理軟體的期間，Tri Delta 的電力公司太平洋瓦電（PG&E）調整過尖峰用電時間表，Tri Delta 本身用電變化也讓所屬費率區間有變動，過去這些都會造成負責充電的員工傷透腦筋，每週的最佳充電時間都不同，一不小心就讓公司承受高額電費，這些變動更顯出充電管理軟體的重要性，充電管理軟體會自動依據電力公司的時間表與公式調整，算出最划算的充電時間。

經過幾個月使用下來，Tri Delta 節省了高達 40% 電費支出，這還只是第一季，進入夏季後，尖峰用電費率落差更大，會讓充電管理的效益更明顯。

不過，這僅是 4 輛電動車的充電管理結果，能否擴大適用到上百台規模的大車隊，尚需進一步驗證。不過越大的車隊，原理上來說，充電管理能達到的效益會更顯著，不僅節省電費更多，軟體最佳化分配車輛充電的時間，更可以讓硬體投資也跟著減少，例如設置較少充電座，或讓電力設備不需太大規模升級，節省建設成本與工程時間。

Amply Power 此實證案例，不僅證明充電管理的重要性，為許多管理軟體新創事業開創市場，另一方面，也同時為整個電動車產業打了一劑定心針：電動巴士車隊雖然成本較高，但可仰賴電費比燃料費用便宜來達成經濟效益，如今這商業模式面臨挑戰，因油價在全球新冠病毒疫情影響下降到低點，電動車的費用優勢可能消失，但是，若充電管理能省下 40% 電費，那麼，電動車隊尚可取回一部分競爭優勢。

（合作媒體：。首圖來源：）

本站聲明:網站內容來源於EnergyTrend https://www.energytrend.com.tw/ev/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔

發燒車訊

pythonic context manager知多少

文章作者作者: admin
文章發佈日期 2020-07-01

Context Managers 是我最喜歡的 python feature 之一，在恰當的時機使用 context manager 使代碼更加簡潔、清晰，更加安全，復用性更好，更加 pythonic。本文簡單介紹一下其使用方法以及常見使用場景。

本文地址：https://www.cnblogs.com/xybaby/p/13202496.html

with statement and context manager

Python’s with statement supports the concept of a runtime context defined by a context manager

new statement “with” to the Python language to make it possible to factor out standard uses of try/finally statements.

在 pep0343 中，通過引入 context manager protocol 來支持 With statement ， context manager 是用來管理 context（上下文）的，即保證程序要保持一種特定的狀態 — 無論是否發生異常。可以說，context manager 簡化了對 try-finally 的使用，而且更加安全，更加便於使用。

Transforming Code into Beautiful, Idiomatic Python 中，指出了 context manager 的最顯著的優點：

Helps separate business logic from administrative logic
Clean, beautiful tools for factoring code and improving code reuse

最廣為人知的例子，就是通過 with statement 來讀寫文件，代碼如下：

with open('test.txt') as f:
    contect = f.read()
    handle_content(content)

上面的代碼幾乎等價於

f = open('test.txt') 
try:
    contect = f.read()
    handle_content(content)
finally:
    f.close()

注意，上面的finally的作用就是保證file.close一定會被調用，也就是資源一定會釋放。不過，很多時候，都會忘了去寫這個finally，而 with statement 就徹底避免了這個問題。

從上述兩段代碼也可以看出，with statement 更加簡潔，而且將核心的業務邏輯（從文件中讀取、處理數據）與其他邏輯（打開、關係文件）相分離，可讀性更強。

實現context manager protocol

一個類只要定義了__enter__、__exit__方法就實現了context manager 協議

object.__enter__(self)
Enter the runtime context related to this object. The with statement will bind this method’s return value to the target(s) specified in the as clause of the statement, if any.

object.__exit__(self, exc_type, exc_value, traceback)
Exit the runtime context related to this object. The parameters describe the exception that caused the context to be exited. If the context was exited without an exception, all three arguments will be None.

If an exception is supplied, and the method wishes to suppress the exception (i.e., prevent it from being propagated), it should return a true value. Otherwise, the exception will be processed normally upon exit from this method.

Note that __exit__() methods should not reraise the passed-in exception; this is the caller’s responsibility.

__enter__方法在進入這個 context 的時候調用，返回值賦值給 with as X 中的 X

__exit__方法在退出 context 的時候調用，如果沒有異常，后三個參數為 None。如果返回值為 True，則Suppress Exception，所以除非特殊情況都應返回 False。另外注意， __exit__方法本身不應該拋出異常。

例子：BlockGuard

在看c++代碼（如mongodb源碼）的時候，經常看見其用 RAII 實現BlockGuard, 用以保證在離開 Block 的時候執行某些動作，同時，也提供手段來取消執行。

下面用python實現一下：

class BlockGuard(object):
	def __init__(self, fn, *args, **kwargs):
		self._fn = fn
		self._args = args
		self._kwargs = kwargs
		self._canceled = False

	def __enter__(self):
		return self

	def __exit__(self, exc_type, exc_value, traceback):
		if not self._canceled:
			self._fn(*self._args, **self._kwargs)
		self._fn = None
		self._args = None
		self._kwargs = None
		return False

	def cancel(self):
		self._canceled = True


def foo():
	print 'sth should be called'


def test_BlockGuard(cancel_guard):
	print 'test_BlockGuard'
	with BlockGuard(foo) as guard:
		if cancel_guard:
			guard.cancel()
	print 'test_BlockGuard  finish'

用yield實現context manager

標準庫 contextlib 中提供了一些方法，能夠簡化我們使用 context manager，如 contextlib.contextmanager(func) 使我們
無需再去實現一個包含__enter__ __exit__方法的類。

The function being decorated must return a generator-iterator when called. This iterator must yield exactly one value, which will be bound to the targets in the with statement’s as clause, if any.

例子如下：

from contextlib import contextmanager

@contextmanager
def managed_resource(*args, **kwds):
    # Code to acquire resource, e.g.:
    resource = acquire_resource(*args, **kwds)
    try:
        yield resource
    finally:
        # Code to release resource, e.g.:
        release_resource(resource)

>>> with managed_resource(timeout=3600) as resource:
...     # Resource is released at the end of this block,
...     # even if code in the block raises an exception

需要注意的是：

一定要寫 try finally，才能保證release_resource邏輯一定被調用
除非特殊情況，不再 catch exception，這就跟 __exit__ 一般不返回True一樣

例子: no_throw

這是業務開發中的一個需求, 比如觀察者模式，不希望因為其中一個觀察者出了 trace 就影響後續的觀察者，就可以這樣做：

from contextlib import contextmanager

@contextmanager
def no_throw(*exceptions):
	try:
		yield
	except exceptions:
		pass

def notify_observers(seq):
	for fn in [sum, len, max, min]:
		with no_throw(Exception):
			print "%s result %s" % (fn.__name__, fn(seq))

if __name__ == '__main__':
	notify_observers([])

在python 3.x 的 contexlib 中，就提供了一個contextlib.suppress(*exceptions), 實現了同樣的效果。

context manager 應用場景

context manager 誕生的初衷就在於簡化 try-finally，因此就適合應用於在需要 finally 的地方，也就是需要清理的地方，比如

保證資源的安全釋放，如 file、lock、semaphore、network connection 等
臨時操作的復原，如果一段邏輯有 setup、prepare，那麼就會對應 cleanup、teardown。

對於第一種情況，網絡連接釋放的例子，後面會結合 pymongo 的代碼展示。

在這裏先來看看第二種用途：保證代碼在一個臨時的、特殊的上下文（context）中執行，且在執行結束之後恢復到之前的上下文環境。

改變工作目錄

from contextlib import contextmanager
import os

@contextmanager
def working_directory(path):
    current_dir = os.getcwd()
    os.chdir(path)
    try:
        yield
    finally:
        os.chdir(current_dir)

with working_directory("data/stuff"):
    pass

臨時文件、文件夾

很多時候會產生一堆臨時文件，比如build的中間狀態，這些臨時文件都需要在結束之後清除。

from tempfile import mkdtemp
from shutil import rmtree

@contextmanager
def temporary_dir(*args, **kwds):
    name = mkdtemp(*args, **kwds)
    try:
        yield name
    finally:
        shutil.rmtree(name)

with temporary_dir() as dirname:
    pass

重定向標準輸出、標準錯誤

@contextmanager
def redirect_stdout(fileobj):
    oldstdout = sys.stdout
    sys.stdout = fileobj
    try:
        yield fieldobj
    finally:
        sys.stdout = oldstdout

在 python3.x 中，已經提供了 contextlib.redirect_stdout contextlib.redirect_stderr 實現上述功能

調整logging level

這個在查問題的適合非常有用，一般生產環境不會輸出 debug level 的日誌，但如果出了問題，可以臨時對某些制定的函數調用輸出debug 日誌

from contextlib import contextmanager
import logging

logger = logging.getLogger()
logger.setLevel(logging.INFO)

ch = logging.StreamHandler()
ch.setFormatter(logging.Formatter('%(asctime)s - %(levelname)s - %(message)s'))
logger.addHandler(ch)


@contextmanager
def change_log_level(level):
	old_level = logger.getEffectiveLevel()
	try:
		logger.setLevel(level)
		yield
	finally:
		logger.setLevel(old_level)


def test_logging():
	logger.debug("this is a debug message")
	logger.info("this is a info message")
	logger.warn("this is a warning message")

with change_log_level(logging.DEBUG):
	test_logging()

pymongo中的context manager使用

在 pymongo 中，封裝了好幾個 context manager，用以

管理 semaphore
管理 connection
資源清理

而且，在 pymongo 中，給出了嵌套使用 context manager 的好例子，用來保證 socket 在使用完之後一定返回連接池(pool)。

# server.py
@contextlib.contextmanager
def get_socket(self, all_credentials, checkout=False):
    with self.pool.get_socket(all_credentials, checkout) as sock_info:
        yield sock_info
        
# pool.py
@contextlib.contextmanager
def get_socket(self, all_credentials, checkout=False):
    sock_info = self._get_socket_no_auth()
    try:
        sock_info.check_auth(all_credentials)
        yield sock_info
    except:
        # Exception in caller. Decrement semaphore.
        self.return_socket(sock_info)
        raise
    else:
        if not checkout:
            self.return_socket(sock_info)

可以看到，server.get_socket 調用了 pool.get_socket, 使用 server.get_socket 的代碼完全不了解、也完全不用關心 socket 的釋放細節，如果把 try-except-finally-else 的邏輯移到所有使用socket的地方，代碼就會很醜、很臃腫。

比如，在mongo_client 中需要使用到 socket：

with server.get_socket(all_credentials) as sock_info:
    sock_info.authenticate(credentials)

references

With statement

Context Managers

contextlib

what-is-the-python-with-statement-designed-for

Transforming Code into Beautiful, Idiomatic Python

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

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔

發燒車訊

重學 Java 設計模式：實戰備忘錄模式「模擬互聯網系統上線過程中，配置文件回滾場景」

文章作者作者: admin
文章發佈日期 2020-06-30

作者：小傅哥
博客：https://bugstack.cn – 原創系列專題文章

沉澱、分享、成長，讓自己和他人都能有所收穫！

一、前言

實現不了是研發的借口？

實現不了，有時候是功能複雜度較高難以實現，有時候是工期較短實現不完。而編碼的行為又是一個不太好量化的過程，同樣一個功能每個人的實現方式不一樣，遇到開發問題解決問題的速度也不一樣。除此之外還很不好給產品解釋具體為什麼要這個工期時間，這就像蓋樓的圖紙最終要多少水泥砂漿一樣。那麼這時研發會盡可能的去通過一些經驗，制定流程規範、設計、開發、評審等，確定一個可以完成的時間範圍，又避免風險的時間點后。再被壓縮，往往會出一些矛盾點，能壓縮要解釋為什麼之前要那麼多時間，不能壓縮又有各方不斷施加的壓力。因此有時候不一定是借口，是要考慮如何讓整個團隊健康的發展。

鼓勵有時比壓力要重要！

在學習的過程中，很多時候我們聽到的都是，你要怎樣，怎樣，你瞧瞧誰誰誰，哪怕今天聽不到這樣的聲音了，但因為曾經反覆聽到過而導致內心抗拒。雖然也知道自己要去學，但是很難堅持，學着學着就沒有了方向，看到還有那麼多不會的就更慌了，以至於最後心態崩了，更不願意學。其實程序員的壓力並不小，想成長几乎是需要一直的學習，就像似乎再也不敢說精通java了一樣，知識量實在是隨着學習的深入，越來越深，越來越廣。所以需要，開心學習，快樂成長！

臨陣的你好像一直很着急！

經常的聽到；老師明天就要了你幫我弄弄吧、你給我寫一下完事我就學這次着急、現在這不是沒時間學嗎快給我看看。其實看到的類似的還有很多，很納悶你的着急怎麼來的，不太可能，人在家中坐，禍從天上落。老師怎麼就那個時間找你了，老闆怎麼就今天管你要了，還不是日積月累你沒有學習，臨時抱佛腳亂着急！即使後來真的有人幫你了，但最好不要放鬆，要儘快學會，躲得過初一還有初二呢！

二、開發環境

JDK 1.8
Idea + Maven
涉及工程一個，可以通過關注公眾號：bugstack蟲洞棧，回復源碼下載獲取(打開獲取的鏈接，找到序號18)

工程	描述
itstack-demo-design-17-00	開發配置文件備忘錄

三、備忘錄模式介紹

備忘錄模式是以可以恢復或者說回滾，配置、版本、悔棋為核心功能的設計模式，而這種設計模式屬於行為模式。在功能實現上是以不破壞原對象為基礎增加備忘錄操作類，記錄原對象的行為從而實現備忘錄模式。

這個設計在我們平常的生活或者開發中也是比較常見的，比如：後悔葯、孟婆湯(一下回滾到0)，IDEA編輯和撤銷、小霸王遊戲機存檔。當然還有我們非常常見的Photoshop，如下；

四、案例場景模擬

在本案例中我們模擬系統在發布上線的過程中記錄線上配置文件用於緊急回滾

在大型互聯網公司系統的發布上線一定是易用、安全、可處理緊急狀況的，同時為了可以隔離線上和本地環境，一般會把配置文件抽取出來放到線上，避免有人誤操作導致本地的配置內容發布出去。同時線上的配置文件也會在每次變更的時候進行記錄，包括；版本號、時間、MD5、內容信息和操作人。

在後續上線時如果發現緊急問題，系統就會需要回滾操作，如果執行回滾那麼也可以設置配置文件是否回滾。因為每一個版本的系統可能會隨着帶着一些配置文件的信息，這個時候就可以很方便的讓系統與配置文件一起回滾操作。

我們接下來就使用備忘錄模式，模擬如何記錄配置文件信息。實際的使用過程中還會將信息存放到庫中進行保存，這裏暫時只是使用內存記錄。

五、備忘錄模式記錄配置文件版本信息

備忘錄的設計模式實現方式，重點在於不更改原有類的基礎上，增加備忘錄類存放記錄。可能平時雖然不一定非得按照這個設計模式的代碼結構來實現自己的需求，但是對於功能上可能也完成過類似的功能，記錄系統的信息。

除了現在的這個案例外，還可以是運營人員在後台erp創建活動對信息的記錄，方便運營人員可以上下修改自己的版本，而不至於因為誤操作而丟失信息。

1. 工程結構

itstack-demo-design-17-00
└── src
    ├── main
    │   └── java
    │       └── org.itstack.demo.design
    │           ├── Admin.java
    │           ├── ConfigFile.java
    │           ├── ConfigMemento.java
    │           └── ConfigOriginator.java
    └── test
        └── java
            └── org.itstack.demo.design.test
                └── ApiTest.java

備忘錄模式模型結構

以上是工程結構的一個類圖，其實相對來說並不複雜，除了原有的配置類(ConfigFile)以外，只新增加了三個類。
ConfigMemento：備忘錄類，相當於是對原有配置類的擴展
ConfigOriginator：記錄者類，獲取和返回備忘錄類對象信息
Admin：管理員類，用於操作記錄備忘信息，比如你一些列的順序執行了什麼或者某個版本下的內容信息

2. 代碼實現

2.1 配置信息類

public class ConfigFile {

    private String versionNo; // 版本號
    private String content;   // 內容
    private Date dateTime;    // 時間
    private String operator;  // 操作人
    
    // ...get/set
}

配置類可以是任何形式的，這裏只是簡單的描述了一個基本的配置內容信息。

2.2 備忘錄類

public class ConfigMemento {

    private ConfigFile configFile;

    public ConfigMemento(ConfigFile configFile) {
        this.configFile = configFile;
    }

    public ConfigFile getConfigFile() {
        return configFile;
    }

    public void setConfigFile(ConfigFile configFile) {
        this.configFile = configFile;
    }
    
}

備忘錄是對原有配置類的擴展，可以設置和獲取配置信息。

2.3 記錄者類

public class ConfigOriginator {

    private ConfigFile configFile;

    public ConfigFile getConfigFile() {
        return configFile;
    }

    public void setConfigFile(ConfigFile configFile) {
        this.configFile = configFile;
    }

    public ConfigMemento saveMemento(){
        return new ConfigMemento(configFile);
    }

    public void getMemento(ConfigMemento memento){
        this.configFile = memento.getConfigFile();
    }

}

記錄者類除了對ConfigFile配置類增加了獲取和設置方法外，還增加了保存saveMemento()、獲取getMemento(ConfigMemento memento)。
saveMemento：保存備忘錄的時候會創建一個備忘錄信息，並返回回去，交給管理者處理。
getMemento：獲取的之後並不是直接返回，而是把備忘錄的信息交給現在的配置文件this.configFile，這部分需要注意。

2.4 管理員類

public class Admin {

    private int cursorIdx = 0;
    private List<ConfigMemento> mementoList = new ArrayList<ConfigMemento>();
    private Map<String, ConfigMemento> mementoMap = new ConcurrentHashMap<String, ConfigMemento>();

    public void append(ConfigMemento memento) {
        mementoList.add(memento);
        mementoMap.put(memento.getConfigFile().getVersionNo(), memento);
        cursorIdx++;
    }

    public ConfigMemento undo() {
        if (--cursorIdx <= 0) return mementoList.get(0);
        return mementoList.get(cursorIdx);
    }

    public ConfigMemento redo() {
        if (++cursorIdx > mementoList.size()) return mementoList.get(mementoList.size() - 1);
        return mementoList.get(cursorIdx);
    }

    public ConfigMemento get(String versionNo){
        return mementoMap.get(versionNo);
    }

}

在這個類中主要實現的核心功能就是記錄配置文件信息，也就是備忘錄的效果，之後提供可以回滾和獲取的方法，拿到備忘錄的具體內容。
同時這裏設置了兩個數據結構來存放備忘錄，實際使用中可以按需設置。List<ConfigMemento>、Map<String, ConfigMemento>。
最後是提供的備忘錄操作方法；存放(append)、回滾(undo)、返回(redo)、定向獲取(get)，這樣四個操作方法。

3. 測試驗證

3.1 編寫測試類

@Test
public void test() {
    Admin admin = new Admin();
    ConfigOriginator configOriginator = new ConfigOriginator();
    configOriginator.setConfigFile(new ConfigFile("1000001", "配置內容A=哈哈", new Date(), "小傅哥"));
    admin.append(configOriginator.saveMemento()); // 保存配置
    configOriginator.setConfigFile(new ConfigFile("1000002", "配置內容A=嘻嘻", new Date(), "小傅哥"));
    admin.append(configOriginator.saveMemento()); // 保存配置
    configOriginator.setConfigFile(new ConfigFile("1000003", "配置內容A=么么", new Date(), "小傅哥"));
    admin.append(configOriginator.saveMemento()); // 保存配置
    configOriginator.setConfigFile(new ConfigFile("1000004", "配置內容A=嘿嘿", new Date(), "小傅哥"));
    admin.append(configOriginator.saveMemento()); // 保存配置  

    // 歷史配置(回滾)
    configOriginator.getMemento(admin.undo());
    logger.info("歷史配置(回滾)undo：{}", JSON.toJSONString(configOriginator.getConfigFile()));  

    // 歷史配置(回滾)
    configOriginator.getMemento(admin.undo());
    logger.info("歷史配置(回滾)undo：{}", JSON.toJSONString(configOriginator.getConfigFile()));  

    // 歷史配置(前進)
    configOriginator.getMemento(admin.redo());
    logger.info("歷史配置(前進)redo：{}", JSON.toJSONString(configOriginator.getConfigFile()));   

    // 歷史配置(獲取)
    configOriginator.getMemento(admin.get("1000002"));
    logger.info("歷史配置(獲取)get：{}", JSON.toJSONString(configOriginator.getConfigFile()));
}

這個設計模式的學習有一部分重點是體現在了單元測試類上，這裏包括了四次的信息存儲和備忘錄歷史配置操作。
通過上面添加了四次配置后，下面分別進行操作是；回滾1次、再回滾1次，之後向前進1次，最後是獲取指定的版本配置。具體的效果可以參考測試結果。

3.2 測試結果

23:12:09.512 [main] INFO  org.itstack.demo.design.test.ApiTest - 歷史配置(回滾)undo：{"content":"配置內容A=嘿嘿","dateTime":159209829432,"operator":"小傅哥","versionNo":"1000004"}
23:12:09.514 [main] INFO  org.itstack.demo.design.test.ApiTest - 歷史配置(回滾)undo：{"content":"配置內容A=么么","dateTime":159209829432,"operator":"小傅哥","versionNo":"1000003"}
23:12:09.514 [main] INFO  org.itstack.demo.design.test.ApiTest - 歷史配置(前進)redo：{"content":"配置內容A=嘿嘿","dateTime":159209829432,"operator":"小傅哥","versionNo":"1000004"}
23:12:09.514 [main] INFO  org.itstack.demo.design.test.ApiTest - 歷史配置(獲取)get：{"content":"配置內容A=嘻嘻","dateTime":159320989432,"operator":"小傅哥","versionNo":"1000002"}

Process finished with exit code 0

從測試效果上可以看到，歷史配置按照我們的指令進行了回滾和前進，以及最終通過指定的版本進行獲取，符合預期結果。

六、總結

此種設計模式的方式可以滿足在不破壞原有屬性類的基礎上，擴充了備忘錄的功能。雖然和我們平時使用的思路是一樣的，但在具體實現上還可以細細品味，這樣的方式在一些源碼中也有所體現。
在以上的實現中我們是將配置模擬存放到內存中，如果關機了會導致配置信息丟失，因為在一些真實的場景里還是需要存放到數據庫中。那麼此種存放到內存中進行回復的場景也不是沒有，比如；Photoshop、運營人員操作ERP配置活動，那麼也就是即時性的一般不需要存放到庫中進行恢復。另外如果是使用內存方式存放備忘錄，需要考慮存儲問題，避免造成內存大量消耗。
設計模式的學習都是為了更好的寫出可擴展、可管理、易維護的代碼，而這個學習的過程需要自己不斷的嘗試實際操作，理論的知識與實際結合還有很長一段距離。切記多多上手！

七、推薦閱讀

1. 重學 Java 設計模式：實戰工廠方法模式「多種類型商品不同接口，統一發獎服務搭建場景」
2. 重學 Java 設計模式：實戰原型模式「上機考試多套試，每人題目和答案亂序排列場景」
3. 重學 Java 設計模式：實戰橋接模式「多支付渠道(微信、支付寶)與多支付模式(刷臉、指紋)場景」
4. 重學 Java 設計模式：實戰組合模式「營銷差異化人群發券，決策樹引擎搭建場景」
5. 重學 Java 設計模式：實戰外觀模式「基於SpringBoot開發門面模式中間件，統一控制接口白名單場景」
6. 重學 Java 設計模式：實戰享元模式「基於Redis秒殺，提供活動與庫存信息查詢場景」
7. 重學 Java 設計模式：實戰備忘錄模式「模擬互聯網系統上線過程中，配置文件回滾場景」

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

【其他文章推薦】

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

※評比前十大台北網頁設計、台北網站設計公司知名案例作品心得分享

※智慧手機時代的來臨，RWD網頁設計已成為網頁設計推薦首選

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

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

標籤 RWD網頁設計, USB CONNECTOR , 南投搬家公司費用, 台北網站設計, 台北網頁設計, 新北清潔