Спин-блокировки и кеш: TAS, TTAS, талоны и очередь MCS

Если ты знаешь, почему test-and-set в цикле тормозит всю машину, чем TTAS лучше TAS и зачем замку очередь, листай до «Теперь сам».

Как думаешь, что быстрее

Шестнадцать ядер ждут один замок. Вариант А: каждое крутит test_and_set(lock), пока не получит 0. Вариант Б: каждое крутит while lock == 1: pass и только потом пробует test_and_set. По логике оба делают одно и то же. Какой быстрее, и насколько?

Ответь себе до чтения. Разница в том, что первый вариант пишет в память на каждой попытке, а второй - читает. На одном ядре это почти одно и то же. На шестнадцати модель из разбора показывает разницу в полтора раза по числу сообщений между ядрами, а очередной замок MCS обходит оба почти в десять раз.

На что это похоже

Очередь у кабинета врача. Плохой вариант: каждые десять секунд кто-нибудь открывает дверь и спрашивает «можно?» - мешает и врачу, и пациенту внутри. Вариант получше: смотреть на табло «свободно/занято» и стучать, только когда загорится «свободно» - правда, тогда к двери кидаются все разом. Хороший вариант - электронная очередь: у каждого свой номер, и вызывают по одному. Каждый смотрит только на своё табло и не мешает остальным.

Механизм: кеш и строки

У каждого ядра свой кеш. Чтение ячейки, копия которой есть в кеше, не выходит за пределы ядра. Запись требует, чтобы копия была только у пишущего: остальные копии объявляются недействительными (протокол когерентности, MESI и родственники), и следующее чтение у них - промах с обращением по шине.

• TAS - каждая попытка test_and_set - запись. 16 ожидающих - непрерывный поток инвалидаций, и строка замка мечется между ядрами.
• TTAS (test-and-test-and-set) - ждём чтением из своего кеша; трафика нет, пока замок занят. При освобождении копии у всех сбрасываются, все разом читают, видят «свободно» и делают test_and_set - всплеск, но только один раз на передачу.
• Талоны: мой = fetch_add(следующий, 1), ждать, пока обслуживается == мой; выход - обслуживается += 1. Порядок честный, но все ждут на одной ячейке, и каждый выход будит всех.
• MCS (Меллор-Крамми и Скотт, 1991): очередь из узлов, каждый ждёт на флаге в СВОЁМ узле. Выходящий пишет только во флаг следующего - одна строка, одно ядро (если следующего нет, он атомарно сбрасывает хвост очереди).

Правило

Спин-блокировку нагружают не вычисления, а трафик когерентности: запись в общую строку сбрасывает её копии у всех ядер. TAS пишет на каждой попытке, TTAS ждёт чтением и пишет только при «свободно», талонный замок честен (не больше n − 1 обгонов), но будит всех, MCS - честен и передаёт замок за постоянное число сообщений, потому что каждый ждёт на своей ячейке.

Разбор: сколько сообщений на один захват

Модель кешей: у каждого ядра для каждой строки состояние I (копии нет), S (копия для чтения) или M (своя, можно писать). Промах при чтении и запись без своей копии - одно обращение к шине. Шестнадцать захватов замка, случайный планировщик, секция длится четыре шага.

import random

# строка кеша у ядра: "I" - копии нет, "S" - копия, "M" - своя
def chitat(kesh, yadro, stroka, shina):
    if kesh[yadro].get(stroka, "I") == "I":
        shina[0] = shina[0] + 1
        for k in range(len(kesh)):
            if kesh[k].get(stroka) == "M":
                kesh[k][stroka] = "S"
        kesh[yadro][stroka] = "S"

def pisat(kesh, yadro, stroka, shina):
    if kesh[yadro].get(stroka, "I") != "M":
        shina[0] = shina[0] + 1
        for k in range(len(kesh)):
            kesh[k][stroka] = "I"
        kesh[yadro][stroka] = "M"

def progon(vid, n, zahvatov, seed):
    # vid: "TAS", "TTAS", "талоны", "MCS"; секция длится 4 шага
    random.seed(seed)
    kesh = []
    for k in range(n):
        kesh.append({})
    shina = [0]
    zamok = 0
    sled_talon = 0
    obsluzh = 0
    ochered = []
    sost = [0] * n          # 0 - хочет войти, 1..4 - в секции
    talon = [-1] * n        # -1 - талона ещё нет
    uvidel = [False] * n    # TTAS: видел «свободно», дальше - TAS
    v_ocheredi = [False] * n
    sdelano = 0
    while sdelano < zahvatov:
        t = random.randint(0, n - 1)
        if sost[t] > 0:
            sost[t] = sost[t] + 1
            if sost[t] == 5:
                sost[t] = 0
                sdelano = sdelano + 1
                if vid == "талоны":
                    pisat(kesh, t, "zamok", shina)
                    obsluzh = obsluzh + 1
                elif vid == "MCS":
                    ochered.pop(0)
                    v_ocheredi[t] = False
                    if len(ochered) > 0:
                        pisat(kesh, t, "flag" + str(ochered[0]), shina)
                else:
                    pisat(kesh, t, "zamok", shina)
                    zamok = 0
        elif vid == "TAS":
            pisat(kesh, t, "zamok", shina)
            if zamok == 0:
                zamok = 1
                sost[t] = 1
        elif vid == "TTAS":
            # чтение и test-and-set - разные шаги: между ними успевают
            # прочитать и другие, отсюда всплеск при освобождении
            if not uvidel[t]:
                chitat(kesh, t, "zamok", shina)
                uvidel[t] = zamok == 0
            else:
                pisat(kesh, t, "zamok", shina)
                uvidel[t] = False
                if zamok == 0:
                    zamok = 1
                    sost[t] = 1
        elif vid == "талоны":
            if talon[t] == -1:
                pisat(kesh, t, "sled", shina)
                talon[t] = sled_talon
                sled_talon = sled_talon + 1
            chitat(kesh, t, "zamok", shina)
            if talon[t] == obsluzh:
                sost[t] = 1
                talon[t] = -1
        else:
            # очередь MCS здесь - список: важно лишь, что каждый ждёт
            # на своём флаге, а выходящий пишет во флаг следующего
            if not v_ocheredi[t]:
                pisat(kesh, t, "hvost", shina)
                ochered.append(t)
                v_ocheredi[t] = True
            chitat(kesh, t, "flag" + str(t), shina)
            if ochered[0] == t:
                sost[t] = 1
    return round(shina[0] / zahvatov, 1)

print("ядер   TAS  TTAS  талоны  MCS")
for n in [2, 4, 8, 16]:
    stroka = [n]
    for vid in ["TAS", "TTAS", "талоны", "MCS"]:
        stroka.append(progon(vid, n, 16, n))
    print(stroka)

ядер   TAS  TTAS  талоны  MCS
[2, 2.3, 2.9, 3.1, 3.0]
[4, 10.3, 8.0, 5.1, 3.3]
[8, 27.4, 13.8, 9.2, 3.9]
[16, 46.9, 33.1, 17.6, 4.9]

Обращения к шине на один захват. У TAS они растут примерно как 3n: на 16 ядрах - 47, и большая часть - бесполезные попытки ожидающих. TTAS - 33: ожидание бесплатно, но каждое освобождение вызывает всплеск - все, кто прочитал «свободно», по очереди делают test_and_set. Талоны - около n, 17,6 на шестнадцати: каждый выход сбрасывает копию у всех ожидающих, и каждый перечитывает её по разу. MCS почти не растёт: 3 на двух ядрах, 4,9 на шестнадцати. Модель грубая, но порядок величин тот же, что в замерах Херлихи и Шавита на настоящих машинах.

Разбор: честность TAS и талонов

Второй вопрос - не сколько стоит передача, а кому она достаётся. Тот же случайный планировщик; считаем, сколько раз в худшем случае другие захватили замок, пока один поток ждал.

import random

def obgony(vid, n, zahvatov, seed):
    # сколько чужих захватов случилось, пока поток ждал; худший случай
    random.seed(seed)
    zanyat = -1
    zhdet_s = [0] * n        # номер захвата, с которого поток ждёт
    talon = [-1] * n
    sled = 0
    obsluzh = 0
    sdelano = 0
    hudshij = 0
    v_sekcii = 0
    while sdelano < zahvatov:
        t = random.randint(0, n - 1)
        if zanyat == t:
            v_sekcii = v_sekcii + 1
            if v_sekcii == 3:
                zanyat = -1
                v_sekcii = 0
                obsluzh = obsluzh + 1
                zhdet_s[t] = sdelano
                talon[t] = -1
            continue
        if vid == "талоны" and talon[t] == -1:
            talon[t] = sled
            sled = sled + 1
            zhdet_s[t] = sdelano
        if zanyat == -1:
            if vid == "TAS" or talon[t] == obsluzh:
                zanyat = t
                hudshij = max(hudshij, sdelano - zhdet_s[t])
                sdelano = sdelano + 1
    return hudshij

print("ядер  худший обгон: TAS, талоны")
for n in [2, 4, 8, 16]:
    print(n, obgony("TAS", n, 100, n), obgony("талоны", n, 100, n))

ядер  худший обгон: TAS, талоны
2 7 1
4 15 3
8 34 7
16 94 15

У талонного замка худший обгон ровно n − 1: очередь есть очередь. У TAS на шестнадцати ядрах один поток пропустил вперёд 94 захвата из сотни: кто успел сделать test_and_set сразу после освобождения, тот и вошёл, и невезучему потоку может не везти сколько угодно. На настоящем железе хуже: ядро, только что освободившее замок, держит строку в своём кеше и успевает перехватить её первым.

Что ломается без этого

TAS-цикл на сервере. Счётчик на одном замке, 32 ядра, и производительность падает с ростом числа ядер: ожидающие своими записями тормозят владельца, которому нужна та же строка, чтобы выйти.

Ложное разделение. Замок и часто изменяемая переменная в одной 64-байтовой строке кеша: каждая запись в переменную сбрасывает копию замка у всех ожидающих. Лечат, раскладывая их по разным строкам: выравнивание с дополнением до 64 байт (alignas(64) в C++ вместе с заполнением, @Contended в Java).

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

Зачем это в работе

Ядро Linux прошло этот путь целиком: TAS-подобные спин-блокировки, с 2008 года талонные (честность), с 2015-го qspinlock - вариант MCS, ужатый в 4 байта. Многие мьютексы (адаптивный мьютекс glibc, sync.Mutex в Go) при конкуренции сначала коротко крутятся, а потом засыпают через futex или планировщик. В Java ReentrantLock построен на очереди в духе CLH - родственника MCS.

Теперь сам

1. Почему TTAS почти не создаёт трафика, пока замок занят, и почему всё же создаёт всплеск при освобождении?
2. Сколько обгонов в худшем случае допускает талонный замок на 32 потоках?
3. В MCS выходящий пишет во флаг следующего. Сколько ядер получают сообщение об этой записи?