該算法在本文中描述：Thread Scheduling for Multiprogrammed Multiprocessors。簡而言之，計算在進程中被分配，並且每個進程都有一個線程隊列來完成這項工作。一個進程可以將（彈出）線程推送到（或離開）其deque底部，而其他進程可以通過從頂部彈出線程來工作。因此，工作可以通過推動操作而產生。該算法如下。此線程調度多處理器算法是否適用於所有情況？
我的問題是有關的PoPToP（）工作stealling功能。我認爲它不會適用於所有情況。例如，假設一個進程A有一個隊列Q和一個進程B試圖從Q上竊取工作，調用popTop（）。假設此時B在popTop（）和localBot = X的第2行之後被搶先。如果A運行並且popBottom（）直到Q < = X的底部，當B恢復運行時，它將得到已經由A處理的線程。
我的想法是否正確？我需要驗證它，因爲我會實施它來在CUDA程序中進行工作平衡。
代碼使用cas（）（比較和交換）來嘗試和停止你描述的事情。如果popTop（）在第2行後停止，它在閱讀了age和bot之後停止。如果popBottom（）然後運行並返回一個線程，它將在年齡內增加字段並使用cas（）將遞增版本寫回到內存中。現在，當B重新開始並調用cas（）時，cas（）指令發現B爲年齡提供的值與內存中的值不匹配（這意味着對cas（）的調用不會修改內存）。所以B發現（oldAge == newAge）並返回ABORT。在這種情況下，你通常會再次嘗試，並希望下次有更好的運氣。這篇文章似乎是說，調用yield（）對於你有好運氣是必要的，但在任何情況下，popTop（）都不應該返回其他人抓取的線程。
當然有一個關於cas（）在http://en.wikipedia.org/wiki/Compare-and-swap的維基百科文章。
我會在並行代碼上面使用鎖定一級難度的上面的串行代碼，並且鎖定並行代碼的上一級難度鎖定並行代碼。我不會寫無鎖並行代碼，除非我確實知道我需要性能，並且沒有可以重用的現有已知可信代碼。我不會相信這樣的代碼，直到我對它進行了徹底的測試，而且如果可能的話，我更願意進行模型檢查。
這可能更適合cstheory，cs或數學。 – templatetypedef