S_N>Для изменения всего лишь одного бита вводить ВСЕГДА критические секции совсем неэффективно. Ведь реально — РЕДКИЙ СЛУЧАЙ, когда оба потока будут ломиться именно к одному значению int в массиве. Поэтому, зачем лишние блокировки? Я решил синхронизировать потоки так — сначала поток записывает в специальную переменную тот номер int из массива который он намерен "захватить", и только потом его меняет. 2-й поток будет приостановлен только в РЕДКИХ случаях когда оба потока одновременно захотят изменить это значение. Т.е. 2-й поток увидев что значение захвачено и используется, сбросит свою метку,(он же тоже уже пометил, что хочет захватывать это значение), и заснет на какое-то время. Потом снова пометит, что он хочет менять, снова проверит, не захвачено ли значение другим потоком и т.д

Т.е. спинлок, хранящий в себе указатель на данные. Что ж... первый шаг к lock-free data structures выглядит именно так, только писать надо очень аккуратно и вдумчиво.