Concurrent Programming: APIs and Challenges
原文： #2 Concurrent Programming
大陸網友的譯文http://blog.jobbole.com/52647/
Concurreny指的是同時執行許多事務，可以是在單一核心的CPU上利用不同時間片段(time slice)執行，或是將事務分配到多核心CPU上執行。
在OS X and iOS上的Concurrency API從底層到高層依序有
- pthread
- NSThread
- Grand Central Dispatch
- NSOperationQueue
另外還有一個比較不同的NSRunloop。
高層API是從低層封裝而來的，由於Concurrent程式碼非常複雜且難以管理，所以在撰寫程式時應該優先考慮高層API而非低層API。
Thread是Process的子單元，所有高層API都是從封裝thread得來的。你無法控制你的thread何時何地被列入排程，也無法決定會被執行多久。
使用thread最大的問題就是你必須自行管理thread，如果自己的程式跟底層framework都產生了大量的thread，這會被吃光memory與kernel資源。
Grand Central Dispatch
Grand Central Dispatch (GCD) 在OS X 10.6 and iOS 4被導入。GCD是從thread封裝而來，提供開發者高階的觀點來達成多工。GCD提供了幾個優先權不一的佇列(Queue)，開發者只要將程式碼片段放入佇列中，GCD就會依據目前資源使用的狀況，幫你決定這些工作要送到自身管理的thread pool中的某條thread去執行。GCD提供了五個不同的queue：
- Main queue: 最終會在main thread上執行
- High priority queue: 背景執行，優先權高
- Default priority queue: 背景執行，優先權中等
- Low priority queue: 背景執行，優先權低
- Background priority queue: 背景執行，優先權最低
更詳細的資料可以看 http://blog.csdn.net/mobanchengshuang/article/details/10839049
雖然不同優先權的工作使用不同的queue聽起來很合理，但是強烈建議大多數情況下還是用 default priority queue 就好。
原因是，如果這些task存取共享資源，低優先權task有可能會block高優先權的task，造成priority inversion，app會卡住。
Operation Queues
Operation Queues是對GCD的Cocoa封裝，在一般情況下是最好最安全的選擇。Operation Queues有兩種queue
- Main queue: 最終會在main thread上執行
- Custom queue: 在背景執行
Task會以NSOperation子類別的型態在queue中被處理。當建構自己的NSOperation子類別時，可以選擇override Main方法或是start方法，前者實作上較為簡易，系統會自動幫你處理isExecuting以及isFinished 等狀態；後者則是可讓你自行管理這些狀態，在執行asynchronous task時應該使用這個方法。特別注意到狀態屬性必須是KVO-compliant的，如果不使用default accessor method改變這些狀態，記得要手動發出KVO Message(willChange… , didChange…)。
@implementation YourOperation
- (void)main
{
// do your work here ...
}
@end
@implementation YourOperation
- (void)start
{
self.isExecuting = YES;
self.isFinished = NO;
// start your work, which calls finished once it's done ...
}
- (void)finished
{
self.isExecuting = NO;
self.isFinished = YES;
}
@end
要讓自訂的NSOperation支援取消，應該經常檢查isCancelled狀態。
- (void)main
{
while (notDone && !self.isCancelled) {
// do your processing
}
}
Operation queue提供一些使用GCD很難作正確的功能
- 控制被執行的operation個數
- 依據operation之間的相依性順序執行
[intermediateOperation addDependency:operation1];
[intermediateOperation addDependency:operation2];
[finishedOperation addDependency:intermediateOperation];
使用Operarion queue相較於GCD會有效能上的損失，但是在大多數情況下是微不足道的，應該盡量選擇使用Operarion queue來實作。
Run Loops
關於runloop的中文資料可以參考iOS多线程编程Part 1/3 - NSThread & Run Loop，講的非常詳細。
Runloop就是一個處理事件的loop，通常會綁定一個event source，如果沒有綁定source的話runloop會馬上結束。Event source分兩大類：
- Input sources
- Timer sources
當event source有新的事件時，runloop會被喚醒來處理事件，Timer sources的事件處理完後runloop不會結束，而Input sources事件處理完後runloop會結束。runloop自身有很多模式，可以想像成狀態，一次只能運行在一種模式下，在綁定event source時必須告訴runloop在哪些模式下要處理這個event source的事件。一個經典的情況就是，在Main Runloop的NSDefaultRunLoopMode綁定自訂的Timer source，如果使用者開始scroll的話，runloop會切換到UITrackingRunLoopMode模式，就不處理先前綁定的Timer source裡的事件了。解法就是讓這個Timer source裡的事件在多個模式下都可以被處理，那麼一開始綁定的時候就要設定NSRunLoopCommonModes模式，這是個模式集合，包含NSDefaultRunLoopMode、NSTaskDeathCheckMode、UITrackingRunLoopMode，只要runloop處於這三個模式其中之一，就會處理Timer source的事件。
一個runloop會綁定一個thread，main thread預設已經有main runloop運行。
Challenges of Concurrent Programming
撰寫concurrent program是極其複雜的，不同的task有可能會互相影響，進而導致未預期的結果。就連NASA這麼嚴謹的組織也會犯錯。
Sharing of Resources
在thread之間共享資源是許多concurrency問題的邪惡根源。
如果有兩條thread同時對某個整數property做increment，原值為17。兩條Thread「同時」讀出值，並在memory中加1，thread A先寫回結果18，thread B再寫回結果18，property最終結果為18，而非想像中的19，這就是race condition。
另外在實際情況中，一行程式碼會被編譯器解譯成好幾行的機器碼，包含讀取與寫入。而編譯器為了優化速度，有可能不會照順序放置這些機器碼，這也是我們必須列入考量的地方。
Mutual Exclusion
Mutual exclusive access就是保證一次只有一條thread存取資源。Cocoa提供了一些Synchronization Tool:
- Atomic Operations
- Memory Barriers and Volatile Variables
- Locks
- Conditions
- Perform Selector Routines
使用這些tool是有代價的，效能會受到影響，應該盡量設計結構讓程式不需要Synchronization。
用了lock之後經常會發生一次只有一條thread在做事的情況，使用CPU strategy view觀察執行的情況再做調整。
Dead Locks
Dead Lock就是thread獲取不到資源無法執行下去而卡死，有可能是兩條thread互相等待對方完成，也有可能是自己lock住但是重複嘗試獲取lock導致自己deadlock。
Starvation
高優先權的thread一直佔住資源不讓低優先權的thread做事，低優先權的thread就挨餓了。在Reader-Writer問題中如果使用單純的讀寫鎖，萬一Reader一直源源不絕進來佔住鎖，Writer就會Starvation。
可改用Write-preferring或RCU(Read-Copy Update)解決。
Write-preferring是當目前有writer在等待時，新的Reader就不能獲取鎖，直到writer寫入完畢才能再繼續。
RCU(Read-Copy Update)就是讀-拷貝修改。被RCU保護的資料結構Reader不需要鎖即可訪問。Writer先拷貝一份副本，並在副本上修改數據。修改完後，向垃圾回收器註冊一個callback，垃圾回收器等待所有正在讀取數據的Reader發送已不再讀取數據的訊號，全部接收到之後再調用callback將指向原數據的指標改成指向修改過後的數據。
Priority Inversion
如果有一高優先權task與一低優先權task共享資源，而低優先權task先佔住了資源，照理來說低優先權task應該儘快結束工作好讓高優先權task可以拿到資源做事，結果好死不死有中優先權task一直進來插隊做事，讓低優先權task遲遲無法釋放lock，高優先權task拿不到想要的資源，這就是Priority Inversion。
Jserv也有介紹NASA’s Pathfinder事件
Conclusion
Concurrent programming真的很複雜。
Concurrency model應該越簡單越好。
安全作法是在Main thread把資料拉到Background Operation queue做事，做完再放回Main queue。
