Alan Carter - The Programmers' Stone (Программистский камень)

Мы начнем с того, что оказываем вам любезность предположением вашей разумности. Представим, что вы изучаете синхронные процессы совместного использования ресурсов. Как хороший картостроитель, вы изучаете литературу, и размышляете над тем, что сказали другие. Вы также пытаетесь экспериментировать сами. Очень скоро вы начинаете видеть глубокие инвариантные структуры, как удачные, так и неудачные. Вы приходите к заключению, что ситуация потенциального тупика (deadlock) -- это потенциальный тупик, не важно, замаскирован ли он сложностью. Вы также можете распознать потенциальный динамический тупик (livelock), когда с ним сталкиваетесь.

Для тех читателей, которые еще не пытались это изучить, мы советуем сделать это, поскольку слишком много часов работы программиста теряются именно на таких вещах, но кратенько расскажем о тупике и бесконечном цикле. Тупик (deadlock) возникает, когда два (или больше) процесса останавливаются во взаимном ожидании друг друга. Например, один процесс может захватить в исключительное пользование базу данных заказчиков, а другой захватывает в исключительное пользование базу данных о складе. Затем каждый процесс пытается получить в исключительное пользование базу, которой у него нет. Ни один из запросов не может быть удовлетворен, поскольку другой процесс уже получил запрошенное исключительное пользование. Поэтому менеджер базы данных оставляет оба запроса в подвешенном состоянии, оба процесса засыпают до момента, когда запрос сможет быть удовлетворен. Конечно же, этого никогда не произойдет, поскольку ни один из спящих процессов не освободит базу данных, которой он уже владеет, и спать им вечно. Самый простой способ избежать такой ситуации в реальных проектах -- сделать это случайно, и это не особенно мудро. Слово customer после сортировки по алфавиту стоит перед словом stock, поэтому при массовой закупке напитков стоит обратиться сначала к базе данных склада до обращения к базе данных заказчиков, даже если это означает, что возникают ситуации, где только один уже имеет доступ к базе данных склада, и поэтому приходится освобождать склад, запрашивать заказчика, запрашивать склад. Это стоит делать и пусть так и будет, либо доступ будет предоставляться одновременно либо некоторый другой нужный процесс будет попадать туда и циклы будут хорошо использоваться.

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

Итак, теперь вы знаете о динамическом тупике. По горькому опыту вы узнали динамический тупик, и вы распознаете потенциальный динамический тупик, когда с ним столкнетесь. Теперь представьте, что вы собираетесь встретиться с другом. Вы не уверены, в каком из двух баров вы хотите встретиться, поскольку всегда один оживленный, в то время как другой похож на морг, и вы никогда не можете сказать как все будет на этот раз. Вы не знаете, в какой из них пойдете сначала. Эти два бара находятся в разных концах квартала. Конечно, вы знаете о динамических тупиках. Вы же не собираетесь, как бегающий по планете Земля мохнатый зверек [тут, по-видимому, намек на бешеную собаку, которой семь верст не крюк - С.К.], впадать в динамический тупик, накручивая с товарищем круги между этими двумя барами в поисках друг друга. Когда придет время назначать встречу, вы -- тот, кто скажет: "А если ты захочешь проверить другой бар, погуляй по берегу реки у квартала, так что я увижу тебя, если попаду в ту же ситуацию!"

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

Итак, что мы поняли и что заплели. Когда вы понимаете динамический тупик, то понимание динамического тупика -- осознание того, что в мире происходят подобные вещи, и что вам приходится с ними сталкиваться -- становится частью вашего сознания.

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