10.5 Реализация select

Предыдущие разделы детально рассмотрели отправку и приём данных по одному каналу (10.3). На практике, однако, горутина редко наблюдает лишь один канал: требуется реагировать на первую готовую операцию из нескольких отправок и приёмов и при этом избегать блокировки, если ни одна из них не готова. select создан именно для этого. Его семантика выглядит просто, однако реализация должна одновременно решить две нетривиальные задачи: как справедливо выбрать ветку, когда несколько из них готовы, и как избежать взаимоблокировки при захвате нескольких каналов в рамках одного select. Оба требования определяют всю структуру selectgo, и данный раздел построен вокруг них.

1
2
3
4
5
6
7
8

select {
case v := <-ch1:   // выполняется, когда ch1 может принять
    use(v)
case ch2 <- x:     // выполняется, когда ch2 может отправить
    sent()
default:           // выполняется, когда ни одна из веток не готова (необязательно)
    nonblocking()
}

Сформулируем соглашения заранее. Каждый case описывает одну операцию с каналом (приём или отправку), и после вычисления select выполняется не более одного взаимодействия. Если одновременно готовы несколько case, один выбирается равномерно случайным образом; если ни один не готов, то при наличии default выполняется default (что делает весь select неблокирующим), а без default select блокируется до тех пор, пока какой-либо case не станет готов. Спецификация языка (Select statements) фиксирует эту семантику; рантайм обеспечивает её выполнение, а компилятор преобразует синтаксическую форму в данные, пригодные для рантайма.

10.5.1 Понижение уровня компилятором: выделение простых случаев

Не каждый select заслуживает полного механизма. На фазе walk (cmd/compile/internal/walk/select.go) компилятор сначала отдельно транслирует несколько вырожденных форм в зависимости от их размера, и только оставшиеся передаются в общий selectgo:

• Ноль case (select {}): блокируется навсегда. Транслируется непосредственно в runtime.block(), который через gopark переводит текущую горутину в режим сна без последующего пробуждения.
• Один case (select { case ... }, без default): эквивалентно записи этой операции с каналом напрямую. Понижается до обычной отправки или приёма без входа в selectgo.
• Один case плюс default (ровно два case, один из которых — default): идиома неблокирующей отправки и приёма. Транслируется в один if с вызовом selectnbsend или selectnbrecv, которые являются не чем иным, как тонкими обёртками, устанавливающими аргумент block функций chansend / chanrecv в false:

1
2
3
4
5
6
7

// понижение уровня "select { case ch<-v: ...; default: ... }" компилятором (схематично)
if selectnbsend(ch, &v) { /* тело case */ } else { /* тело default */ }

// runtime/chan.go: неблокирующая отправка — это просто chansend с block=false
func selectnbsend(c *hchan, elem unsafe.Pointer) (selected bool) {
    return chansend(c, elem, false)
}

Смысл такого понижения: наиболее распространённый на практике вид select — это именно «один case плюс default» как неблокирующий зондирующий вызов; исключение таких case из selectgo позволяет избежать накладных расходов на построение массива case, вычисление двух порядков обхода и захват всех каналов. В selectgo попадает только select с двумя и более реальными ветками взаимодействия. Отдельно стоит отметить: даже если в исходном коде задано много case, если большинство каналов во время выполнения равны nil (case с nil-каналом никогда не готов, и его можно считать несуществующим), общий код всё равно обрабатывает это корректно, поэтому компилятор больше не формирует отдельный быстрый путь для «случайно оставшихся одного или двух эффективных case».

10.5.2 Два порядка: структуры данных selectgo

В selectgo поступает массив scase. В go1.26 структура scase сведена к минимуму:

1
2
3
4
5

// runtime/select.go: полное описание одного case
type scase struct {
    c    *hchan         // канал, с которым работает данный case
    elem unsafe.Pointer // адрес данных для отправки или адрес приземления для приёма
}

Признак того, является ли case отправкой или приёмом, больше не хранится в поле структуры, а кодируется позицией: компилятор располагает все case-отправки в начале массива, а все case-приёмы — в конце; selectgo(cas0, order0, pc0, nsends, nrecvs, block) использует nsends / nrecvs для определения границы. Индекс casi < nsends соответствует отправке, иначе — приёму. Это позволяет сэкономить одно поле kind на каждый case.

Главная хитрость — в массиве order0 длиной 2*ncases, разделённом на два сегмента, каждый из которых несёт свой ключевой инвариант select:

1
2
3
4

ncases := nsends + nrecvs
scases := cas1[:ncases:ncases]
pollorder := order1[:ncases:ncases]          // порядок опроса: определяет, какой case проверяется на готовность первым
lockorder := order1[ncases:][:ncases:ncases] // порядок захвата: определяет последовательность захвата блокировок каналов

pollorder обеспечивает справедливость, lockorder обеспечивает свободу от взаимоблокировок. Они решают две ортогональные задачи — именно поэтому используются два независимых порядка. Рассмотрим, как каждый из них строится.

10.5.3 pollorder: случайный опрос обеспечивает справедливость

Если бы selectgo всегда проверял case в порядке их записи в исходном коде, то при одновременной готовности нескольких case ранние case устойчиво получали бы предпочтение, а поздние могли бы испытывать голодание. Требование спецификации «выбрать один равномерно случайным образом» призвано именно предотвратить такое предпочтение. Реализация: перед проверкой готовности порядок обхода case перемешивается случайным образом, и тогда «первый найденный готовый case» оказывается равномерно распределённым по всем case.

Перемешивание выполняется in-place по алгоритму Фишера — Йетса, где в качестве источника случайности используется cheaprandn (дешёвый, lock-free, локальный для M генератор случайных чисел):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// построение pollorder: перемешивание Фишера — Йетса in-place (сокращено)
norder := 0
for i := range scases {
    cas := &scases[i]
    if cas.c == nil {       // case с nil-каналом никогда не готов, исключаем из опроса
        cas.elem = nil
        continue
    }
    j := cheaprandn(uint32(norder + 1)) // выбрать позицию равномерно из [0, norder]
    pollorder[norder] = pollorder[j]
    pollorder[j] = uint16(i)
    norder++
}
pollorder = pollorder[:norder]

Корректность алгоритма Фишера — Йетса — классический результат: он порождает все $n!$ перестановок с равными вероятностями за один проход $O(n)$ без дополнительной памяти. Использование cheaprandn обеспечивает справедливость select: каждый готовый case имеет равную вероятность быть выбранным. Здесь стоит обратить внимание на инженерное решение: источник случайности — cheaprandn, а не криптографически стойкий генератор, поскольку требуется равномерность в статистическом смысле, а не устойчивость к предсказанию; дешёвый вариант — правильный выбор.

Немного истории. Справедливость select была введена не произвольно, а в ответ на реальную инженерную проблему. В раннем issue golang/go#21806 обсуждалось: при определённых нагрузках пользователи наблюдали заметный перекос в выборе ветки select, что в итоге побудило сообщество закрепить «случайный опрос» как в описании спецификации, так и в реализации. cheaprandn в сочетании с алгоритмом Фишера — Йетса — это то, во что воплотилось данное требование справедливости.

10.5.4 lockorder: глобально согласованный порядок захвата блокировок предотвращает взаимоблокировку

Для выполнения одного select рантайм должен одновременно удерживать блокировки всех задействованных каналов: необходимо поочерёдно проверить каждый из них на готовность и, возможно, поставить горутину в очередь ожидания каждого канала — всё это должно происходить под соответствующими блокировками. Как только в игру вступает несколько блокировок, возникает угроза взаимоблокировки. Предположим, горутина A выполняет select { case <-x: ; case <-y: }, а горутина B — select { case <-y: ; case <-x: }. Если каждая захватывает блокировки в порядке записи, A удерживает блокировку x и ожидает y, тогда как B удерживает блокировку y и ожидает x — хрестоматийная перекрёстная взаимоблокировка.

Выход — классический приём параллельного программирования: задать единый глобально согласованный порядок захвата всех блокировок и заставить всех придерживаться именно этого порядка. Если все горутины захватывают x и y в одном и том же относительном порядке, цикл ожидания становится невозможным. selectgo в качестве ключа глобального порядка использует адрес канала (sortkey возвращает значение указателя), сортирует case по адресу канала и получает lockorder:

1
2
3

func (c *hchan) sortkey() uintptr {
    return uintptr(unsafe.Pointer(c)) // адрес канала как ключ глобального порядка
}

Для сортировки применяется пирамидальная сортировка (heapsort), а не пакет sort, и тому есть конкретная причина: все данные select находятся на стеке горутины, а heapsort гарантирует время $O(n\log n)$ при постоянном потреблении стека, не утяжеляя этот предположительно лёгкий путь рекурсией или дополнительными аллокациями. Сортировка отправной точкой берёт pollorder (что позволяет заодно стабильно группировать несколько case одного и того же канала), а результат помещается в lockorder:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// с адресом канала в качестве ключа, heapsort сортирует case in-place для получения глобально согласованного порядка захвата (сокращено)
for i := range lockorder {           // построить кучу снизу вверх, беря элементы из pollorder
    j := i
    c := scases[pollorder[i]].c
    for j > 0 && scases[lockorder[(j-1)/2]].c.sortkey() < c.sortkey() {
        k := (j - 1) / 2
        lockorder[j] = lockorder[k]
        j = k
    }
    lockorder[j] = pollorder[i]
}
for i := len(lockorder) - 1; i >= 0; i-- { // извлекать вершину кучи по одному, получая отсортированную последовательность
    // ... стандартное просеивание кучи вниз, сравнение по sortkey ...
}

Захват и освобождение блокировок выполняются по lockorder: sellock захватывает в прямом порядке, selunlock освобождает в обратном; при этом одному и тому же каналу (несколько case могут использовать один и тот же канал) блокировка захватывается и освобождается лишь один раз:

1
2
3
4
5
6
7

func sellock(scases []scase, lockorder []uint16) {
    var c *hchan
    for _, o := range lockorder {
        c0 := scases[o].c
        if c0 != c { c = c0; lock(&c.lock) } // не захватывать повторно соседние одинаковые каналы
    }
}

Теперь разделение труда между двумя порядками очевидно: pollorder определяет порядок просмотра (для справедливости), lockorder — порядок захвата блокировок (для свободы от взаимоблокировок). Они не мешают друг другу — именно поэтому используются два массива, а не один.

10.5.5 Полный поток выполнения: три прохода

После подготовки данных тело selectgo представляет собой три прохода по case. Сначала общая схема:

flowchart TD
    START["вход в selectgo"] --> BUILD["построить pollorder (случайный)<br/>и lockorder (по адресу)"]
    BUILD --> LOCK["sellock: захватить все каналы согласно lockorder"]
    LOCK --> P1["проход 1: найти готовый case по pollorder"]
    P1 -->|найден готовый case| DO["send/recv, selunlock, вернуть индекс case"]
    P1 -->|нет готовых| HASDEF{есть default?}
    HASDEF -->|да| DEF["selunlock, вернуть default"]
    HASDEF -->|нет| P2["проход 2: по lockorder добавить sudog<br/>в очередь ожидания каждого канала<br/>(isSelect=true)"]
    P2 --> PARK["gopark: selparkcommit снимает блокировки по порядку, затем усыпляет горутину"]
    PARK -->|разбужен одним из case| RELOCK["sellock повторно"]
    RELOCK --> P3["проход 3: удалить собственный sudog из очередей остальных каналов,<br/>определить case, который разбудил горутину"]
    P3 --> DO2["selunlock, вернуть индекс case"]

Проход первый: найти уже готовый case. Удерживая блокировки, проверяем case один за другим по pollorder. Case-приём проверяет, есть ли ожидающий отправитель в очереди отправки, есть ли данные в буфере, закрыт ли канал; case-отправка проверяет, не закрыт ли канал (отправка в закрытый канал должна вызвать панику), есть ли ожидающий получатель в очереди приёма, есть ли свободный слот в буфере. При первом совпадении выполняется переход к соответствующей ветке для завершения отправки или приёма (прямая передача, работа через буфер или чтение нулевого значения из закрытого канала), после чего блокировки освобождаются и происходит возврат. Если этот проход даёт результат, select завершается одной синхронной отправкой или приёмом без какой-либо блокировки.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

// проход 1 — найти уже готовый case по случайному pollorder (сокращено)
for _, casei := range pollorder {
    casi = int(casei); cas = &scases[casi]; c = cas.c
    if casi >= nsends {            // case-приём
        if sg := c.sendq.dequeue(); sg != nil { goto recv }
        if c.qcount > 0 { goto bufrecv }
        if c.closed != 0 { goto rclose }
    } else {                       // case-отправка
        if c.closed != 0 { goto sclose }
        if sg := c.recvq.dequeue(); sg != nil { goto send }
        if c.qcount < c.dataqsiz { goto bufsend }
    }
}
if !block {                        // нет готовых и есть default (block==false)
    selunlock(scases, lockorder)
    casi = -1; goto retc
}

default представлен здесь в виде block == false: компилятор кодирует наличие default в аргументе block. Если первый проход не находит ни одного готового case и block равен false, немедленно снимаются блокировки и возвращается -1 (вызывающий код соответственно выполняет тело default), тем самым превращая select в неблокирующую операцию.

Проход второй: прикрепиться к каждому каналу. Если ни один case не готов и требуется блокировка, горутина не может ждать лишь на одном канале; она должна оставить метку «я жду» на каждом канале, чтобы первый из них, ставший готовым, мог разбудить горутину. Для этого для каждого case берётся sudog, устанавливается isSelect = true, они нанизываются в цепочку waiting горутины по lockorder и каждый ставится в очередь отправки или приёма соответствующего канала:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// проход 2 — добавить sudog на все каналы (сокращено)
nextp = &gp.waiting
for _, casei := range lockorder {
    casi = int(casei); cas = &scases[casi]; c = cas.c
    sg := acquireSudog()
    sg.g = gp
    sg.isSelect = true             // пометить: это ожидатель, добавленный через select
    sg.elem.set(cas.elem)
    sg.c.set(c)
    *nextp = sg; nextp = &sg.waitlink // нанизать в цепочку gp.waiting по lockorder
    if casi < nsends { c.sendq.enqueue(sg) } else { c.recvq.enqueue(sg) }
}
gp.param = nil
gopark(selparkcommit, nil, waitReason, traceBlockSelect, 1)

Метка isSelect обязательна. Обычный sudog отправки/приёма привязан лишь к одному каналу, и тот, кто его будит, просто извлекает его из очереди; sudog select, напротив, одновременно находится в нескольких каналах, и будитель обязан знать, что «этот ожидатель принадлежит select и за него может одновременно бороться другой канал», и захватить его через CAS (посредством gp.selectDone), тем самым гарантируя, что один select пробуждается ровно одним каналом. Функция selparkcommit, переданная в gopark, обходит цепочку gp.waiting, уже упорядоченную по lockorder, и поочерёдно освобождает блокировку каждого канала перед тем, как перевести горутину в сон. Порядок здесь соответствует lockorder — чтобы не вносить новый цикл на пути разблокировки.

Проход третий: очистить состояние после пробуждения. Некий канал стал готов и разбудил горутину. Она снова вызывает sellock, захватывая блокировки всех каналов, затем обходит lockorder: в канале, который её разбудил, собственный sudog уже извлечён другой стороной (горутина опознаёт его и фиксирует сработавший case); во всех остальных каналах собственный sudog по-прежнему висит, и каждый нужно удалить через dequeueSudoG, иначе они засорят очереди ожидания «молчащих» каналов. Каждый sudog возвращается через releaseSudog, блокировки снимаются, и возвращается индекс сработавшего case.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// проход 3 — после пробуждения удалить себя из очередей каналов, которые не сработали (сокращено)
sg = (*sudog)(gp.param)            // будитель сообщает нам, какой sudog, через gp.param
sglist = gp.waiting; gp.waiting = nil
for _, casei := range lockorder {
    if sg == sglist {              // это case, который меня разбудил
        casi = int(casei); cas = &scases[casi]
    } else {                       // остальные case: удалить оставшийся sudog
        c = scases[casei].c
        if int(casei) < nsends { c.sendq.dequeueSudoG(sglist) } else { c.recvq.dequeueSudoG(sglist) }
    }
    sgnext = sglist.waitlink; sglist.waitlink = nil
    releaseSudog(sglist); sglist = sgnext
}

Три прохода в совокупности составляют полную блокирующую семантику select: первый проход берёт то, что уже готово; если ничего нет — второй проход прикрепляется ко всем каналам и переводит горутину в сон; после пробуждения третий проход отменяет лишние привязки и фиксирует только тот случай, который вызвал пробуждение. reflect.Select (reflect_rselect) проходит через тот же selectgo, только предварительно преобразуя case, описанные через рефлексию, в массив scase.

10.5.6 Проектные решения и происхождение

Если рассмотреть несколько ключевых решений selectgo, каждое из них имеет чёткое обоснование:

• Два порядка, а не один. Справедливость (случайный опрос) и безопасность (упорядоченный захват блокировок) — ортогональные требования; объединение их в один порядок лишь создало бы взаимные ограничения. Разделение нагрузки на два массива pollorder и lockorder стоит одного дополнительного сегмента стека размером ncases, обеспечивая при этом максимально чистое раздельное решение каждой задачи.
• Адрес как глобальный порядок захвата блокировок. Использование значения указателя в качестве ключа сортировки выглядит почти примитивным, однако точно удовлетворяет единственному требованию — «глобальной согласованности». Оно не требует семантического приоритета между каналами, а лишь того, чтобы все горутины видели один и тот же порядок. Это роднит данный подход с классическим методом предотвращения взаимоблокировок — «захватывать несколько блокировок в фиксированном порядке», — отражение которого можно увидеть в двухфазной блокировке баз данных и в упорядочивании блокировок ядра ОС.
• Heapsort вместо общей сортировки. Это обеспечивает постоянное потребление стека и детерминированное время $O(n\log n)$ — ещё один пример «экономии на аллокациях и глубине стека на горячем пути», того же инженерного духа, что и экономия аллокатора на строках кэша (12.2).
• isSelect и захват через CAS. Sudog select соотносится с несколькими каналами одновременно, что вводит новый вид состязания — «один ожидатель оспаривается несколькими сторонами»; оно разрешается меткой isSelect и атомарным захватом gp.selectDone, гарантируя, что один select завершается ровно один раз. Эта дополнительная сложность — необходимая цена самой возможности «ожидать нескольких каналов одновременно».

В контексте своего происхождения select является прямым наследником охраняемых команд (guarded commands) теории CSP. В CSP Хора 1978 года (10.1) процесс формирует выбор из множества охраняемых взаимодействий, а «инструкция выбора» продвигает один из готовых охранников; ещё раньше (1975) Дейкстра абстрагировал этот недетерминизм «несколько кандидатов, выполнить один» в языковую конструкцию — охраняемые команды. select в Go переносит эту теорию в рантайм: охранник — это case, «выбрать один» — три прохода selectgo, а теоретически расплывчатое «недетерминированно выбрать один» конкретизировано в Go как «равномерно случайным образом», реализованное посредством cheaprandn и алгоритма Фишера — Йетса. Языки occam и Newsqueak (ближайшие родственники модели конкурентности Go) выбрали тот же путь для своих аналогичных конструкций. Таким образом, select был спроектирован не с нуля; это теоретическая нить длиной более сорока лет, воплощённая инженерными средствами в сегодняшние несколько сотен строк select.go.

Дополнительная литература

1. The Go Authors. runtime/select.go (selectgo, sellock, selparkcommit, sortkey). https://github.com/golang/go/blob/master/src/runtime/select.go
2. The Go Authors. cmd/compile/internal/walk/select.go (понижение уровня для нуля case / одного case и default). https://github.com/golang/go/blob/master/src/cmd/compile/internal/walk/select.go
3. The Go Authors. The Go Programming Language Specification: Select statements. https://go.dev/ref/spec#Select_statements
4. Go issue #21806. runtime: select is not fair / biased case selection. https://github.com/golang/go/issues/21806
5. C. A. R. Hoare. “Communicating Sequential Processes.” Communications of the ACM, 21(8), 1978. https://doi.org/10.1145/359576.359585
6. Edsger W. Dijkstra. “Guarded Commands, Nondeterminacy and Formal Derivation of Programs.” Communications of the ACM, 18(8), 1975. https://doi.org/10.1145/360933.360975
7. Эта книга: 10.1 Каналы и проектирование CSP, 10.3 Отправка, приём и прямая передача, 10.4 Семантика закрытия, 10.6 Модель памяти и эволюция без блокировок.