дочитал C++ Concurrency in Action

был неиллюзорно поражен скудностью и лаконичностью главы 10 - Testing and Debugging Multithreaded Applications

Автор упоминает про combination simulation testing - идея в том чтобы протестировать все возможные комбинации всех локов всеми потоками на симуляторе. Несложно догадаться что сложность этого алгоритма O(N!), где N - сумма потоков и объектов блокировки, и вряд ли когда-нибудь этот метод будет реализован на практике. Однако - на самом деле нам не нужно прогонять все возможные комбинации при тестировании некоего куска кода - в большинстве случаев достаточно всего лишь прогнать все возможные комбинации одновременно работающих потоков, что на машине с n камнями и N потоками (как правило N > n) дает нам подмножества n конечных множеств из N (биномиальный коэффициент, ага). Практически этого можно достигнуть например применяя под linux соответствующим образом написанный планировщик - нужно дописать к нему интерфейс общения из user mode и ровно 3 ioctls:

• поместить некий поток в группу
• запустить перебор на одновременное исполнение для всех потоков в группе
• сообщить результаты перебора (готово-неготово-сколько циклов прогнано)

Также автор упоминает про tests with special library, но из целой одной странички, посвященной изложению темы, можно почерпнуть мало чего. Однако - это крайне богатая идея, например можно придумать достаточно простой алгоритм для нахождения взаимной блокировки потоков. Пусть у нас есть два три потока - A, B и С, и скажем поток C делает join к потоку B, поток B делает join к потоку A, а поток A собирается сделать join с потоку C, что даст в результате вечный deadlock. Нет ничего проще - заводим внешний орграф, в нем узлы - потоки, а операции join - ребра, при добавлении нового ребра проверяем граф на наличие циклов. Если цикл обнаружен - у нас deadlock в коде

Аналогично можно находить взаимоблокировки - например в каждом потоке вести множество залоченных объектов и объектов, которые поток пытается залочить. Пусть например есть два потока

• A, залочивший mutex a и пытающийся залочить mutex b
• поток B, залочивший mutex b и висящий на ожидании mutex a. 

По моему для случая двух потоков нахождение таких взаимоблокировок - совершенно тривиальная задача. Или можно представлять объекты синхронизации как узлы графа, а использующие их потоки - как ребра (например в вышеописанном примере поток A будет ребром между mutexes a & b, а поток B - ребром между b & a). Нахождение взаимоблокировки в таком случае - поиск циклов графа, составленных из ребер разных потоков.