7.3.4. Выявляйте циклы активного ожидания и помогайте другим потокам

В последнем примере очереди мы видели, что поток, выполняющий операцию push(), должен дождаться, пока другой поток, выполняющий ту же операцию, завершит свои действия. Если ничего не предпринимать, то этот поток будет крутиться в цикле активного ожидания, впустую расходуя процессорное время и не продвигаясь ни на шаг. Наличие цикла ожидания в действительности эквивалентно блокирующей операции, а тогда с равным успехом можно было бы воспользоваться мьютексами. Модифицировав алгоритм таким образом, что ожидающий поток выполняет неполные шаги, если планировщик выделил ему время до завершения работы в исходном потоке, мы сможем устранить активное ожидание и сделать операцию неблокирующей. В примере очереди нам для этого потребовалось сделать одну переменную-член атомарной и использовать для ее установки операции сравнения с обменом, но в более сложных структурах данных могут понадобиться более обширные изменения.

Отталкиваясь от структур данных с блокировками, описанных в главе 6, мы в этой главе продемонстрировали простые реализации структур данных без блокировок на примере все тех же стека и очереди. Мы видели, как внимательно нужно подходить к упорядочению доступа к памяти в атомарных операциях, чтобы избежать гонок и гарантировать, что каждый поток видит непротиворечивое представление структуры данных. Мы также поняли, что управление памятью в структурах данных без блокировок оказывается значительно сложнее, чем в структурах с блокировками, и изучили несколько подходов к решению этой проблемы. Еще мы узнали, как предотвращать циклы активного ожидания, помогая завершить работу потоку, которого мы ждем.

Проектирование свободных от блокировок структур данных — сложная задача, при решении которой легко допустить ошибки, зато такие структуры обладают свойствами масштабируемости, незаменимыми в некоторых ситуациях. Надеюсь, что, проработав приведенные в этой главе примеры и ознакомившись с рекомендациями, вы будете лучше подготовлены к разработке собственных структур данных без блокировок, реализации алгоритмов, описанных в научных статьях, или к поиску ошибок, допущенных бывшим сотрудником компании.

Во всех случаях, когда некоторые данные разделяются между потоками, нужно задумываться о применяемых структурах данных и о синхронизации. Проектируя структуры данных с учетом параллелизма, вы сможете инкапсулировать ответственность в самой структуре, позволив основной программе сосредоточиться на решаемой задаче, а не на синхронизации доступа к данным. Этот подход будет продемонстрирован в главе 8, где мы перейдём от параллельных структур данных к написанию параллельных программ. В параллельных алгоритмах для повышения производительности используется несколько потоков, и выбор подходящей параллельной структуры данных приобретает решающее значение.