完美的多線程編程方案，多線程編程方案
這是去年為了找工作，寫的一個技術演示：以多線程暴力破解MD5密碼為例，來演示一個完美的多線程編程方案。
在十年前，我寫過一個單線程的暴力破解MD5密碼程序（因為當時CPU還都是單核的），這次是把原來的程序多線程化了。
這個技術演示，寫了多個不同實現方式的多個版本，一共花了2天時間（2014年5月3日-2014年5月4日）。
加密密碼的暴力破解原理，不是本文重點，這裡就不詳細介紹了。
簡單舉例說明一下，對於嘗試字符集為 a-z 26個小寫字母，嘗試長度為8位的話，就是把 a, b, ... z, aa, ab, ... zy, zz, aaa, ... aaaaaaaa, aaaaaaab, ... zzzzzzzy, zzzzzzzz，這26個小寫字母，8位長度以內，所有的組合都嘗試一遍，所以叫做暴力破解。嘗試的結果，如果原加密密碼在這個范圍內，就必然找到。如果原加密密碼不在這個范圍內，那麼該范圍內的所有可能全部嘗試完後，沒有找到。嘗試的方法就是對自己生成的每一個嘗試串，進行和加密密碼相同加密方式的加密，然後把加密後的嘗試串，和加密密碼進行比較，相同就說明找到了。
這種暴力破解，需要CPU進行超大量的計算。而需要CPU進行超大量計算的場景，是多線程技術的一個非常重要的應用場景。
我們以實例，來對暴力破解計算量形成一些概念：
以26個小寫字母的各種組合進行嘗試的話：
試完單獨1位，需要對26種嘗試串（a-z），進行計算和比較。
試完單獨2位，需要對26+26*26=702種嘗試串，進行計算和比較。
試完單獨8位，需要對26的8次方+26的7次方+...+26=2171.80147158億種嘗試串，進行計算和比較。
使用四核 @3.4GHz 的CPU，以四線程（線程數超過CPU實際核數的話，速度不會提高）跑完2171.8億種可能的話，估計要4個多小時。而以單線程跑完2171.8億種可能的話，估計要16個小時以上。
大家有興趣的話，可以下載本文附帶的程序，自己嘗試一下。
可以看到在需要CPU進行超大量計算的場景，多線程技術的使用是多麼有意義。
多線程共同訪問和處理同一數據源，一個非常重要的問題是，訪問時需要互斥，否則的話，可能造成遺漏處理數據，或者重復處理數據。少量的重復處理數據是可以接受的，但是遺漏處理數據是不可接受的。為什麼會出現重復和遺漏，我們這裡不展開講了。所以，多線程共同訪問和處理同一數據源，訪問時必需要互斥。
下面我們就來看一下，我所嘗試過的幾種實現方案。
多線程方案1：
嘗試串只有1個。多個線程輪流取，然後再進行計算和比較。
這樣的話，各個線程進行嘗試的連續性好。但是，當一個線程在生成嘗試串的過程中，另幾個線程不能訪問嘗試串，線程需要阻塞等待。預計會經常出現這種情況，會很影響速度。
程序實現，
如果使用mutex來進行線程互斥的話，對速度的影響極為巨大，因為mutex部分代碼的執行，四線程版甚至比單線程版還要慢很多很多。（"ddzzzz"的md5的破解。四線程使用mutex互斥，118984ms。單線程大約13500ms。四線程比單線程還慢了8倍多）
如果使用InterlockedIncrement64，對程序的限制大。
多線程方案2：
把任務分成大致相等的n份（n為cpu的核數），然後創建n個線程，每個線程完成1份。
沒有互斥的問題。
邏輯清晰性差，將來如果用於不同應用場景，代碼比較難修改。
未作程序實現。
多線程方案3：
把任務分成固定的份數，然後創建n個線程（n為cpu的核數），每個線程做1份，做完之後，再去領1份，直到將所有的份數全部做完。
線程內，需要完成領一份的代碼。領一份部分需要互斥。互斥部分出現的頻率很少。
未作程序實現。
多線程方案4：
創建n個線程（n為cpu的核數）。
每個線程每次從總任務中，取一部分的任務進行處理，這部分任務處理完之後，再去取。直到將所有的任務全部處理完。好處是分配的比較均勻。連續性也較好。
程序實現，
"ddzzzz"的md5的破解，3線程4641ms。效果最好。
為什麼說多線程方案4，是一種比較完美的多線程編程方案：
1，在一個對執行效率有很高要求的場景下，執行效率很高。
2，代碼邏輯性非常好，適用性很廣。很少的改動，就可以應用在很多的應用場景中。
本文所附帶程序（http://pan.baidu.com/s/1i3ip4nb）說明：
MD5Calc.exe 圖形界面，將指定的明文密碼轉換為MD5加密密碼。
JiurlMd5CrackGui.exe 圖形界面，多線程暴力破解演示程序，以本文多線程方案4實現。可以自行設定使用的線程數，默認線程數為CPU內核數減1。
TryCharset.txt 指定嘗試字符集。
CryptedPassword.txt 指定要破解的密碼。
臨時主頁：http://blog.sina.com.cn/ddqqppb
QQ高大上交流群：91877299
