Блог

Я пересматриваю главу STM книги Марлоу. Там указано, что:

Когда несколько потоков блокируются на an MVar , они гарантированно будут разбужены в порядке FIFO

Однако то же самое невозможно сделать в случае STM:

Транзакция может быть заблокирована при произвольном условии, поэтому среда выполнения не знает, сможет ли какая-либо отдельная транзакция добиться прогресса после TVar изменения; она должна запустить транзакцию, чтобы узнать. Следовательно, когда есть несколько транзакций, которые могут быть разблокированы, мы должны запустить их все; в конце концов, все они могут быть в состоянии продолжить сейчас.

Чего я не понимаю, так это почему из этого следует, что

Поскольку среда выполнения должна запускать все заблокированные транзакции, нет гарантии, что потоки будут разблокированы в порядке FIFO …

Я ожидаю, что, хотя нам нужно запускать все транзакции в блоке STM, мы все равно можем разбудить потоки в порядке FIFO. Так что, я думаю, я упускаю некоторые важные детали.

Смысл STM в том, чтобы размышлять: мы пытаемся выполнить все транзакции, надеясь, что они не конфликтуют друг с другом (или выполняют a retry ). Когда мы обнаруживаем конфликт, мы разрешаем фиксацию некоторых транзакций, а конфликтующие транзакции откатываются.

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

Более технически, когда потоки ожидают a MVar , эти потоки будут выполняться при очень простом условии: MVar становиться непустыми. При пробуждении поток примет значение, сделав его пустым. Таким образом, не более одного потока может выполнить take, и нет смысла пробуждать более одного.

По определению, когда потоки ожидают из-за STM, условие намного сложнее. Предположим, что они ожидают, потому что ранее выполняли a retry , поэтому они ожидают изменения некоторых ранее прочитанных TVar . Когда это происходит, мы не можем точно знать, какой поток снова заблокируется, если мы не повторим его транзакцию. В отличие MVar от этого, теперь возможно, что их пробуждение приведет к тому, что все они завершатся без конфликтов, поэтому мы пытаемся сделать именно это. При этом мы надеемся, что многие (если не все) завершат работу, и снова подготовимся к откату для тех, кто этого не сделает.

Рассмотрим этот конкретный пример STM:

 Thread 1:
read X
if X is zero, retry
compute f(X)
write Y = f(X)

Thread 2:
read X
if X is zero, retry
compute g(X)
write Z = g(X)
 

Предположим, что в начале у нас есть «X = Y = Z = 0». Мы запускаем оба потока, но они повторяют попытку. Затем пишет третий поток X=1 . Мы можем разбудить оба, и нет смысла делать это в порядке FIFO, поскольку оба завершатся. Мы можем и должны вычислять f(X) и g(X) параллельно.

Теперь, если поток 2 записал Y вместо Z в конце, был бы конфликт. В этом случае последовательное выполнение транзакций было бы более эффективным (поскольку в противном случае мы вычисляем f(X) или g(X) дважды). Однако в общем случае трудно предсказать, возникнет конфликт или нет. STM не пытается, предоставляя программисту оптимизировать свой код.

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

TVar s — это не MVar s. У них нет дихотомии пустой / зарезервированный против полного / доступного. Это просто значения, к которым можно получить доступ и / или изменить транзакциями. Потоки не «блокируют ожидание TVar «; они просто считывают текущее значение для TVar , а затем решают, что они не могут добиться прогресса с этим значением (и так retry далее ).

Система времени выполнения знает, к каким TVar s обратился поток, поэтому она знает, что не следует снова пробуждать этот поток, если хотя бы один из них не TVar изменился; при чистом вычислении решение потока retry о том, должен он быть или нет, должно быть чистой функцией всех TVar прочитанных им s, поэтому мы знаем, что это не может сделатьпрогресс, пока один из них не изменится.

Но когда у вас есть куча ожидающих потоков retry , которые все читают одинаково TVar , и это меняется, система выполнения не хочет просто разбудить один. Нет оснований полагать, что только один из них сможет добиться прогресса с новым значением. Предполагается, что транзакции STM должны работать параллельно, оптимистично. Мы хотим разбудить их всех и позволить им попытаться запустить. Если они конфликтуют, мы выясним это позже, с помощью обычных средств обнаружения конфликта между транзакциями STM; мы не можем сказать это из того факта, что все они хотели прочитать одно и то же TVar .

Потенциально мы могли бы разбудить их все одновременно и (если их слишком много для доступных вычислительных единиц) попытаться убедиться, что планировщик запускает их в порядке FIFO. Может быть, это даже сделано; Я понятия не имею. Но я бы предположил, что они обрабатываются точно так же, как и любые другие потоки, которые стали доступны для планирования, и никаких специальных действий не предпринимается. Все они «должны» выполняться параллельно, поэтому не должно иметь значения, какой из них выходит из ворот первым.