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