К настоящему времени мы разработали понятие блокировки и увидели, как ее можно правильно построить с помощью сочетания аппаратного обеспечения и поддержки операционной системы. К сожалению, блокировки - не единственные примитивы, необходимые для создания параллельных программ.
В частности, существует много случаев, когда поток желает проверить, является ли условие истинным, прежде чем продолжить выполнение. Например, родительский поток может захотеть проверить, завершился ли дочерний поток, прежде чем продолжить выполнение (это часто называется join()); как следует реализовать такое ожидание? Давайте посмотрим на рисунок 30.1.
Мы хотели бы видеть здесь следующий результат:
Мы могли бы попробовать использовать общую переменную, как вы видите на рисунке 30.2. Это решение, как правило, будет работать, но оно крайне неэффективно, так как родитель вращается в цикле и тратит впустую процессорное время.
Вместо этого мы хотели бы каким-то образом усыпить родительский поток до тех пор, пока не сбудется условие, которого мы ждем (например, выполнение дочернего потока завершено).
ЗАДАЧА: КАК ДОЖДАТЬСЯ ВЫПОЛНЕНИЯ УСЛОВИЯ
В многопоточных программах потоку часто бывает полезно дождаться, пока какое-либо условие станет истинным, прежде чем продолжить выполнение. Простой подход, заключающийся во вращении в цикле до тех пор, пока условие не станет истинным, крайне неэффективен и тратит впустую циклы процессора, а в некоторых случаях может быть неверным. Возникает вопрос: как поток должен ждать выполнения условия?
30.1 Определение и процедуры
Чтобы дождаться, пока условие станет истинным, поток может использовать так называемую condition variable. Condition variable - это явная очередь, в которую потоки могут помещаться, когда какое-либо состояние выполнения (т.е. какое-либо условие (condition)) не соответствует желаемому (ожидая (waiting) выполнения условия); какой-либо другой поток, когда он изменяет указанное состояние, может затем разбудить один (или несколько) из этих ожидающих потоков и, таким образом, разрешить им продолжить (сигнализируя (signaling) об этом условии). Идея восходит к использованию Дейкстрой “private semaphores” [D68]; аналогичная идея позже была названа Хоаром “condition variable” в его работе над мониторами [H74].
Чтобы объявить такую переменную условия, нужно просто написать что-то вроде этого: pthread cond t c;, который объявляет c в качестве переменной условия (примечание: также требуется правильная инициализация). С переменной условия связаны две операции: wait() и signal(). Вызов wait() выполняется, когда поток хочет перевести себя в спящий режим; вызов signal() выполняется, когда поток что-то изменил в программе и, таким образом, хочет разбудить спящий поток, ожидающий этого условия. В частности, вызовы POSIX выглядят следующим образом:
Мы часто будем называть их wait() и signal() для простоты. Одна вещь, которую вы можете заметить в вызове wait(), заключается в том, что он также принимает мьютекс в качестве параметра; предполагается, что этот мьютекс заблокирован при вызове wait(). Ответственность wait() состоит в том, чтобы снять блокировку и перевести вызывающий поток в спящий режим (атомарно); когда поток просыпается (после того, как какой-либо другой поток подал сигнал об этом), он должен повторно получить блокировку, прежде чем вернуться к работе. Эта сложность проистекает из желания предотвратить возникновение определенных условий гонки, когда поток пытается перевести себя в спящий режим. Давайте взглянем на решение проблемы join (рис. 30.3), чтобы лучше понять это.
Есть два случая, которые следует рассмотреть. В первом случае родитель создает дочерний поток, но продолжает работать сам (предположим, что у нас только один процессор) и, таким образом, немедленно вызывает функцию join(), чтобы дождаться завершения дочернего потока. В этом случае он получит блокировку, проверит готовность дочернего потока (он не готов), и переведет себя в спящий режим, вызвав функцию wait() (следовательно, снимет блокировку). Дочерний элемент в конечном итоге запустится, выведет сообщение “дочерний элемент” и вызовет функцию exit(), чтобы разбудить родительский поток; этот код просто захватывает блокировку, устанавливает переменную состояния done и сигнализирует родительскому потоку. Наконец, родитель запустится (вернется из wait() с удерживаемой блокировкой), разблокирует блокировку и выведет окончательное сообщение “parent: end”.
Во втором случае дочерний поток запускается сразу после создания, устанавливает значение done равным 1, вызывает signal для пробуждения спящего потока (но его нет, поэтому он просто возвращается) и завершается. Затем родительский поток запускается, вызывает функцию join(), видит, что done равно 1, и, следовательно, не ждет и возвращается к выполнению.
Последнее замечание: вы можете заметить, что родитель использует цикл while вместо простого оператора if при принятии решения о том, следует ли ждать выполнения условия. Хотя это не кажется строго необходимым в соответствии с логикой программы, это всегда хорошая идея, как мы увидим ниже.
Чтобы убедиться, что вы понимаете важность каждой части кода thr_exit() и thr_join(), давайте попробуем несколько альтернативных реализаций. Во-первых, вам может быть интересно, нужна ли нам переменная состояния done. Что, если бы код выглядел так, как в приведенном ниже примере? (Рисунок 30.4)
К сожалению, этот подход не сработает. Представьте себе случай, когда дочерний поток немедленно запускается и немедленно вызывает функцию exit(); в этом случае дочерний поток подаст сигнал, но не существует потока который ожидает сигнала. Когда родительский поток запустится, он просто вызовет wait и застрянет; ни один поток никогда не разбудит его. Из этого примера вы должны оценить важность переменной состояния done; она записывает значение, которое потоки заинтересованы знать. Sleeping, waking и locking - все это построено вокруг этой переменной.
Здесь (рис. 30.5) показана еще одна плохая реализация. В этом примере мы представляем, что для того, чтобы подать сигнал и подождать, не нужно удерживать блокировку. Какая проблема может здесь возникнуть? Подумай об этом*!
*Обратите внимание, что этот пример не является “реальным” кодом, потому что вызов pthread cond wait() всегда требует мьютекса, а также переменной условия; здесь мы просто притворяемся, что интерфейс этого не делает ради отрицательного примера.
Проблема здесь заключается в race condition. В частности, если родитель вызывает thr_join(), а затем проверяет значение done, он увидит, что оно равно 0, и, таким образом, попытается перейти в спящий режим. Но как раз перед тем, как он вызывает wait, чтобы перейти в спящий режим, родитель прерывается, и потомок запускается. Дочерний поток изменяет переменную состояния done на 1 и подает сигнал, но ни один поток не ожидает сигнала и, следовательно, ни один поток не пробуждается. Когда родитель снова запускается, он засыпает навсегда, что печально.
Надеюсь, из этого простого примера использования join вы сможете увидеть некоторые основные требования к правильному использованию переменных условий. Чтобы убедиться, что вы понимаете, теперь мы рассмотрим более сложный пример: проблема producer/consumer или bounded-buffer.
ПОДСКАЗКА: ВСЕГДА УДЕРЖИВАЙТЕ БЛОКИРОВКУ ЕСЛИ ПОДАЁТЕ СИГНАЛ ДРУГОМУ ПОТОКУ
Хотя это строго необязательно во всех случаях, вероятно, проще и лучше всего удерживать блокировку во время передачи сигналов при использовании переменных условия. Приведенный выше пример показывает случай, когда вы должны удерживать блокировку для корректности; однако есть некоторые другие случаи, когда, скорее всего, можно этого не делать, но, вероятно, это то, чего вам следует избегать. Таким образом, для простоты удерживайте блокировку при вызове сигнала.
Обратная сторона этого совета, то есть удержание блокировки при вызове wait, является не просто советом, а скорее предписывается семантикой wait, потому что wait всегда (а) предполагает, что блокировка удерживается при ее вызове, (б) освобождает указанную блокировку при переводе вызывающего абонента в спящий режим и (в) повторно получает блокировку непосредственно перед возвратом. Таким образом, обобщение этого совета является правильным: удерживайте блокировку при вызове signal или wait, и вы всегда будете в хорошей форме.
30.2 Проблема Producer/Consumer (Bounded Buffer)
Следующая проблема синхронизации, с которой мы столкнемся в этой главе, известна как проблема производителя/потребителя, или иногда как проблема ограниченного буфера, которая была впервые поставлена Дейкстрой [D72]. Действительно, именно эта проблема производителя / потребителя привела Дейкстру и его коллег к изобретению обобщенного семафора (который может использоваться либо как блокировка, либо как переменная условия) [D01]; мы узнаем больше о семафорах позже.
Представьте себе один или несколько потоков-производителей и один или несколько потоков-потребителей. Производители генерируют элементы данных и помещают их в буфер; потребители извлекают указанные элементы из буфера и каким-то образом потребляют их.
Такое поведение встречается во многих реальных системах. Например, на многопоточном веб-сервере производитель помещает HTTP-запросы в рабочую очередь (т. е. в ограниченный буфер); потоки-потребители берут запросы из этой очереди и обрабатывают их. Ограниченный буфер также используется, когда вы передаете выходные данные одной программы в другую, например, grep foo file.txt | wc -l. В этом примере одновременно выполняются два процесса; группа записывает строки из file.txt со строкой foo в них к тому, что, по его мнению, является стандартным выводом; оболочка UNIX перенаправляет вывод в так называемый канал UNIX (созданный системным вызовом pipe). Другой конец этого канала подключен к стандартному входу процесса wc, который просто подсчитывает количество строк во входном потоке и выводит результат. Таким образом, процесс grep является производителем; процесс wc является потребителем; между ними находится ограниченный буфер внутри ядра; вы, в этом примере, просто счастливый пользователь.
Поскольку ограниченный буфер является общим ресурсом, мы, конечно, должны требовать синхронизированного доступа к нему, чтобы не возникло условие гонки. Чтобы лучше понять эту проблему, давайте рассмотрим некоторый фактический код.
Первое, что нам нужно, - это общий буфер, в который производитель помещает данные и из которого потребитель извлекает данные. Давайте просто используем одно целое число для простоты (вы, конечно, можете представить, что вместо этого вы помещаете указатель на структуру данных в этот слот) и две внутренние процедуры для ввода значения в общий буфер и получения значения из буфера. Подробности см. на рис. 30.6.
Довольно просто, не так ли? Процедура put() предполагает, что буфер пуст (и проверяет это с помощью assert), а затем просто помещает значение в общий буфер и отмечает его заполненным, установив значение count равным 1. Процедура get() делает обратное, устанавливая буфер пустым (т.е. устанавливая значение count равным 0) и возвращая значение. Не волнуйтесь, что в этом общем буфере есть только одна запись; позже мы обобщим ее на очередь, которая может содержать несколько записей, что будет еще интереснее, чем кажется.
Теперь нам нужно написать несколько подпрограмм, которые знают, когда можно получить доступ к буферу, чтобы либо поместить в него данные, либо извлечь из него данные. Условия для этого должны быть очевидны: помещать данные в буфер только тогда, когда счетчик равен нулю (т.е. когда буфер пуст), и получать данные из буфера только тогда, когда счетчик равен единице (т. е. когда буфер заполнен). Если мы напишем код синхронизации таким образом, что производитель помещает данные в полный буфер, или потребитель получает данные из пустого, мы сделали что-то неправильно (и в этом коде сработает assertion).
Эта работа будет выполняться двумя типами потоков, один набор которых мы будем называть потоками-производителями, а другой набор, который мы будем называть потоками-потребителями. На рисунке 30.7 показан код для производителя, который помещает целое число в общий буфер несколько раз, и потребителя, который получает данные из этого общего буфера, каждый раз распечатывая извлеченный элемент данных из общего буфера.
Неверная реализация
Теперь представьте, что у нас есть только один производитель и один потребитель. Очевидно, что процедуры put() и get() имеют внутри себя критические разделы, так как put() обновляет буфер, а get() считывает из него данные. Однако наложение блокировки на код не работает; нам нужно что-то большее.
Неудивительно, что нечто большее - это некоторые переменные условия. В этой (неработающей) первой попытке (рис. 30.8) у нас есть единственная переменная условия cond и связанный с ней мьютекс блокировки.
Давайте рассмотрим логику передачи сигналов между производителями и потребителями. Когда производитель хочет заполнить буфер, он ожидает, пока он не станет пустым (p1–p3). Потребитель имеет точно такую же логику, но ожидает другого условия: заполненности (c1–c3).
Код, показанный на рисунке 30.8, работает только с одним производителем и одним потребителем. Однако, если у нас есть более одного из этих потоков (например, два потребителя), решение имеет две критические проблемы. Что это за проблемы?
... (здесь сделайте паузу, чтобы подумать) ...
Давайте разберемся с первой проблемой, которая связана с оператором if перед ожиданием. Предположим, что есть два потребителя (Tc1 и Tc2) и один производитель (Tp). Сначала запускается потребитель (Tc1); он получает блокировку (c1), проверяет, готовы ли какие-либо буферы к потреблению (c2), и, обнаружив, что ни один из них не готов, ожидает (c3) (который снимает блокировку).
Затем запускается производитель (Tp). Он получает блокировку (p1), проверяет, заполнены ли все буферы (p2), и, обнаружив, что это не так, продолжает и заполняет буфер (p4). Затем производитель сигнализирует о том, что буфер заполнен (p5). Критически важно, что это переводит первого потребителя (Tc1) из режима ожидания для переменной условия в очередь готовности; Tc1 теперь может выполняться (но еще не запущен). Затем производитель продолжает до тех пор, пока не осознает, что буфер заполнен, и в этот момент он переходит в спящий режим (p6, p1–p3).
Вот где возникает проблема: другой потребитель (Tc2) проникает и потребляет одно существующее значение в буфере (c1, c2, c4, c5, c6, пропуская ожидание в c3, потому что буфер заполнен). Теперь предположим, что Tc1 запускается; непосредственно перед возвращением из ожидания он повторно запрашивает блокировку, а затем возвращается. Затем он вызывает get() (c4), но буферов для использования нет! Срабатывает assertion, и код не работает должным образом. Очевидно, что мы должны были каким-то образом предотвратить попытку запуска Tc1, потому что Tc2 прокрался и извлёк значение из буфера. На рисунке 30.9 показано действие, выполняемое каждым потоком, а также состояние его планировщика (Готовность, Выполнение или Спящий режим) с течением времени.
Проблема возникает по простой причине: после того, как производитель разбудил Tc1, но до того, как Tc1 был запущен, состояние ограниченного буфера изменилось (благодаря Tc2). Сигнал потока только пробуждает их; таким образом, это намек на то, что состояние мира изменилось (в данном случае значение было помещено в буфер), но нет никакой гарантии, что при запуске пробужденного потока состояние по-прежнему будет таким, как хотелось бы. Эту интерпретацию того, что означает сигнал, часто называют семантикой Mesa, после первого исследования, в котором таким образом была создана переменная условия [LR80]; контракт, называемый семантикой Хоара, сложнее построить, но он обеспечивает более надежную гарантию того, что разбуженный поток будет запущен сразу после пробуждения. [H74]. Практически каждая система, когда-либо созданная, использует семантику Mesa.
Лучше но всё ещё неверно: while, not if
К счастью, это легко исправить (рис. 30.10): измените if на while.
Подумайте о том, почему это работает; теперь потребитель Tc1 просыпается и (с удерживаемой блокировкой) немедленно повторно проверяет состояние общей переменной (c2). Если в этот момент буфер пуст, потребитель просто возвращается в спящий режим (c3). Выражение if также изменяется на while в producer (p2).
Благодаря семантике Mesa простое правило, которое следует запомнить при работе с переменными условий, - всегда использовать циклы while. Иногда вам не нужно перепроверять условие, но это всегда безопасно; просто делайте это и будьте счастливы.
Однако в этом коде все еще есть ошибка, вторая из двух проблем, упомянутых выше. Вы можете её увидеть? Это как-то связано с тем фактом, что существует только одна переменная условия. Попробуйте выяснить, в чем проблема, прежде чем читать дальше. СДЕЛАЙ ЭТО! (сделайте паузу, чтобы подумать, или закройте глаза...)
Давайте подтвердим, что вы все поняли правильно, или, возможно, давайте подтвердим, что вы сейчас проснулись и читаете эту часть книги. Проблема возникает, когда два потребителя запускаются первыми (Tc1 и Tc2) и оба переходят в спящий режим (c3). Затем производитель запускается, помещает значение в буфер и будит одного из потребителей (скажем, Ts1). Затем производитель выполняет обратный цикл (освобождая и повторно запрашивая блокировку по пути) и пытается поместить больше данных в буфер; поскольку буфер заполнен, производитель вместо этого ожидает выполнения условия (таким образом, переходит в спящий режим). Теперь один потребитель готов к запуску (Tc 1), а два потока находятся в состоянии ожидания (Tc2 и Tp). Мы вот-вот создадим проблему: все становится захватывающим!
Затем потребитель Tc1 просыпается, возвращаясь из ожидания ((c3), перепроверяет условие (c2) и, обнаружив, что буфер заполнен, потребляет значение (c4). Затем этот потребитель, что критически важно, сигнализирует о состоянии (c5), пробуждая только один поток, который находится в спящем режиме. Однако какой поток он должен разбудить?
Поскольку потребитель опустошил буфер, он явно должен разбудить производителя. Однако, если это делает потребитель Tc2 (что определенно возможно, в зависимости от того, как управляется очередь ожидания), у нас возникает проблема. В частности, потребитель Tc2 проснется и обнаружит, что буфер пуст (c2), и вернется в спящий режим (c3). Производитель Tp, у которого есть значение для ввода в буфер, остается в спящем режиме. Другой поток-потребитель, Tc1, также переходит в спящий режим. Все три потока остаются спящими, явная ошибка; смотрите рисунок 30.11, чтобы увидеть жестокий пошаговую картину этого ужасного бедствия.
Сигнализация явно необходима, но должна быть более направленной. Потребитель не должен будить других потребителей, только производителей, и наоборот.
Решение для consumer/producer c одним буфером
Решение здесь снова небольшое: используйте две переменные условия вместо одной, чтобы правильно сигнализировать, какой тип потока должен просыпаться при изменении состояния системы. На рисунке 30.12 показан результирующий код.
В коде потоки-производители ожидают выполнения условия empty, а сигналы условия fill. И наоборот, потоки-потребители ожидают сигнала fill а сигнализируют сигналом empty. Поступая таким образом, вторая проблема, описанная выше, устраняется на уровне архитектуры: потребитель никогда не сможет случайно разбудить потребителя, а производитель никогда не сможет случайно разбудить производителя.
СОВЕТ: ИСПОЛЬЗУЙТЕ WHILE (НЕ IF) ДЛЯ УСЛОВИЙ
При проверке условия в многопоточной программе использование цикла while всегда является правильным; использование только оператора if возможно и зависит от семантики сигнализации (Mesa, Hoar). Таким образом, всегда используйте while, и ваш код будет вести себя так, как ожидалось.
Использование циклов while вокруг условных проверок также обрабатывает случай, когда возникают ложные пробуждения. В некоторых пакетах потоков, из-за деталей реализации, возможно, что два потока будут разбужены, хотя произошел только один сигнал [L11]. Ложные пробуждения являются еще одной причиной для повторной проверки состояния, которого ожидает поток.
Корректное решение проблемы consumer/producer
Теперь у нас есть работающее решение для производителей и потребителей, хотя и не полностью общее. Последнее изменение, которое мы вносим, заключается в том, чтобы обеспечить больший параллелизм и эффективность; в частности, мы добавляем больше слотов буфера, чтобы перед переходом в режим ожидания можно было создавать несколько значений и аналогичным образом использовать несколько значений перед переходом в режим ожидания. При использовании только одного производителя и потребителя этот подход более эффективен, поскольку он уменьшает переключение контекста; при использовании нескольких производителей или потребителей (или обоих) он даже позволяет осуществлять одновременное производство или потребление, тем самым увеличивая параллелизм. К счастью, это небольшое изменение по сравнению с нашим текущим решением.
Первое изменение для этого правильного решения находится внутри самой структуры буфера и соответствующих функций put() и get() (рис. 30.13). Мы также немного меняем условия, которые проверяют производители и потребители, чтобы определить, спать или нет. Мы также показываем правильную логику ожидания и сигнализации (рис. 30.14). Производитель переходит в спящий режим только в том случае, если все буферы в данный момент заполнены (p2); аналогично, потребитель переходит в спящий режим только в том случае, если все буферы в данный момент пусты (c2). И таким образом мы решаем проблему производителя/потребителя; время откинуться на спинку стула и выпить холодного.
30.3 Немного о covering conditions
Теперь мы рассмотрим еще один пример того, как можно использовать переменные условия. Это исследование кода взято из статьи Лэмпсона и Ределла о Pilot [LR80], той же группы, которая впервые внедрила семантику Mesa, описанную выше (язык, который они использовали, был Mesa, отсюда и название).
Проблема, с которой они столкнулись, лучше всего показана на простом примере, в данном случае в простой многопоточной библиотеке выделения памяти. На рисунке 30.15 показан фрагмент кода, демонстрирующий проблему.
Как вы можете видеть в коде, когда поток вызывает код выделения памяти, ему, возможно, придется подождать, пока освободится больше памяти. И наоборот, когда поток освобождает память, он сигнализирует о том, что свободной памяти стало больше. Однако в нашем приведенном выше коде есть проблема: какой ожидающий поток (их может быть несколько) следует разбудить?
Рассмотрим следующий сценарий. Предположим, что свободных байтов нет; поток Ta вызывает allocate(100), за которым следует поток Tb, который запрашивает меньше памяти, вызывая allocate(10). Таким образом, и Ta, и Tb ожидают выполнения условия и переходят в спящий режим; свободных байтов недостаточно для удовлетворения любого из этих запросов.
В этот момент предположим, что третий поток, Tc, вызывает free(50). К сожалению, когда он вызывает сигнал для пробуждения ожидающего потока, он может не разбудить правильный ожидающий поток Tb, который ожидает освобождения всего 10 байт; Ta должен оставаться в ожидании, так как еще недостаточно свободной памяти. Таким образом, код на рисунке не работает, так как поток, пробуждающий другие потоки, не знает, какой поток (или потоки) нужно разбудить.
Решение, предложенное Лэмпсоном и Ределлом, простое: замените вызов pthread_cond_signal() в приведенном выше коде вызовом pthread_cond_broadcast(), который пробуждает все ожидающие потоки. Поступая таким образом, мы гарантируем, что все потоки, которые должны быть разбужены, будут разбужены. Недостатком, конечно, может быть негативное влияние на производительность, поскольку мы можем без необходимости разбудить множество других ожидающих потоков, которые (пока) не должны быть активными. Эти потоки просто проснутся, повторно проверят состояние, а затем немедленно вернутся в спящий режим.
Лэмпсон и Ределл называют такое условие covering condition, поскольку оно охватывает все случаи, когда поток должен проснуться (консервативно); цена такого подхода, как мы уже обсуждали, заключается в том, что может быть разбужено слишком много потоков. Проницательный читатель, возможно, также заметил, что мы могли бы использовать этот подход раньше (см. Проблему производителя / потребителя только с одной переменной условия). Однако в этом случае у нас было лучшее решение, и поэтому мы им воспользовались. В общем, если вы обнаружите, что ваша программа работает только тогда, когда вы меняете свои сигналы на широковещательные (но вы не думаете, что в этом должна быть необходимость), у вас, вероятно, есть ошибка; исправьте ее! Но в случаях, подобных описанному выше выделению памяти, широковещательная передача может быть наиболее простым доступным решением.
30.4 Выводы
Мы рассмотрели еще один важный примитив синхронизации - переменные условий. Позволяя потокам переходить в спящий режим, когда какое-либо состояние программы не соответствует желаемому, CVs позволяет нам аккуратно решать ряд важных проблем синхронизации, включая известную (и все еще важную) проблему producer/consumer, а также covering conditions. Здесь было бы более драматичное заключительное предложение, например: “He loved Big Brother” [O49].
Ссылки
[D68] “Cooperating sequential processes” by Edsger W. Dijkstra. 1968. Available online here: http://www.cs.utexas.edu/users/EWD/ewd01xx/EWD123.PDF. Another classic from Dijkstra; reading his early works on concurrency will teach you much of what you need to know
[D72] “Information Streams Sharing a Finite Buffer” by E.W. Dijkstra. Information Processing Letters 1: 179–180, 1972. http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD329.PDF The famous paper that introduced the producer/consumer problem.
[D01] “My recollections of operating system design” by E.W. Dijkstra. April, 2001. Available: http://www.cs.utexas.edu/users/EWD/ewd13xx/EWD1303.PDF. A fascinating read for those of you interested in how the pioneers of our field came up with some very basic and fundamental concepts, including ideas like “interrupts” and even “a stack”!
[H74] “Monitors: An Operating System Structuring Concept” by C.A.R. Hoare. Communications of the ACM, 17:10, pages 549–557, October 1974. Hoare did a fair amount of theoretical work in concurrency. However, he is still probably most known for his work on Quicksort, the coolest sorting algorithm in the world, at least according to these authors.
[L11] “Pthread cond signal Man Page” by Mysterious author. March, 2011. Available online: http://linux.die.net/man/3/pthread cond signal. The Linux man page shows a nice simple example of why a thread might get a spurious wakeup, due to race conditions within the signal/wakeup code
[LR80] “Experience with Processes and Monitors in Mesa” by B.W. Lampson, D.R. Redell. Communications of the ACM. 23:2, pages 105-117, February 1980. A classic paper about how to actually implement signaling and condition variables in a real system, leading to the term “Mesa” semantics for what it means to be woken up; the older semantics, developed by Tony Hoare [H74], then became known as “Hoare” semantics, which is a bit unfortunate of a name.
[O49] “1984” by George Orwell. Secker and Warburg, 1949. A little heavy-handed, but of course a must read. That said, we kind of gave away the ending by quoting the last sentence. Sorry! And if the government is reading this, let us just say that we think that the government is “double plus good”. Hear that, our pals at the NSA?