Атомарни операции и неизменими обекти

Код на:JavaC#PythonJavaScript

Накратко: Атомарната операция се изпълнява наведнъж, без друга нишка да я прекъсне; Python няма атомарно цяло число и compare-and-set, затова там пазиш с ключалка, а неизменимият обект не се променя.

Проблем

Ключалка за едно +1

Флаш разпродажба: 100 слушалки на половин цена, в 10:00. Страницата на продукта се отваря хиляди пъти в секунда, а всяко отваряне увеличава брояча на изгледите. От урока за ключалките знаеш как да не се губят увеличения: ключалка около views++.

Това е правилно. Но всяка нишка застава на опашка пред ключалката заради едно-единствено +1. Нишка, която не получи ключалката, често бива приспана и после събудена от операционната система. Това струва много повече от самото събиране.

Втората беда е по-лоша. Последната бройка се купува с „ако има, намали с 1“. Това са две стъпки, а между тях друга нишка може да вземе същата бройка.

Идеята

Неделима стъпка

Процесорът има команди, които прочитат, сменят и записват една клетка от паметта с една неделима стъпка. Никоя друга нишка не може да се намеси по средата. Това е атомарна операция (atomic). Не трябва ключалка, никой не чака на опашка и никой не заспива.

В Python атомарно цяло число няма. views += 1 е няколко стъпки за интерпретатора, и с GIL, и без него. Затова в Python има три честни пътя:

• ключалка около увеличаването, както в урока за ключалките;
• опашка, в която нишките пращат събитията, а една нишка брои (в следващите уроци);
• всяка нишка брои в свое място, а накрая местата се събират. Тогава общо нещо няма и нищо не трябва да се пази.

Тук е третият път.

Виж го

Броячът на изгледите

Четири нишки, всяка с по 100 000 изгледа:

counts = [0] * 4


def visitor(slot):
    for _ in range(100_000):
        counts[slot] += 1  # само тази нишка пише тук


threads = [threading.Thread(target=visitor, args=(slot,))
           for slot in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(f"Изгледи: {sum(counts)}")

Изход

Изгледи: 400000

400 000 при всяко пускане. Всяка нишка пише само в своето counts[slot], затова никой никого не пречи. sum(counts) се вика чак след join, когато нишките са свършили.

По-точно, за любопитните

В чужд код ще срещнеш next(counter) върху itertools.count() като „атомарен“ брояч. В CPython с GIL това наистина не губи стойности, но е подробност на реализацията, не обещание на езика. В Python 3.13 без GIL (free-threaded) не разчитай на нея. В Java тази идея (брой поотделно, събери накрая) е готов клас: LongAdder.

Колко по-бързо е от ключалка? Зависи от машината и от това колко нишки се бият за една клетка. Без борба атомарното +1 е няколко наносекунди. Ключалката без борба е близо до него. Разликата идва при много нишки: тогава ключалката приспива, а атомарната операция само повтаря.

Идеята

Провери и смени: compare-and-set

Купуването не е само −1. То е „ако има поне една, намали с 1“. Проверката и смяната трябва да са една стъпка.

За това има по-обща атомарна операция: compare-and-set (CAS, „сравни и смени“). Казваш ѝ две числа: какво мислиш, че има, и какво искаш да има. Тя сменя стойността само ако тя е още тази, която мислиш, и казва дали е успяла. Ако друга нишка я е сменила междувременно, CAS не пипа нищо и отговаря „не“.

Тогава купуването е цикъл:

1. прочети наличността;
2. ако е 0, отказ;
3. CAS: „ако е още толкова, направи я с 1 по-малко“;
4. ако CAS не успее, някой е купил междувременно: върни се на 1.

Python няма CAS. За да видиш идеята, AtomicCell отдолу е малък заместник: compare_and_set прави проверката и смяната под Lock. Истинският CAS е една команда на процесора, без ключалка.

Виж го

Последните три слушалки

class AtomicCell:
    """Python няма CAS: малък заместник с Lock"""

    def __init__(self, value):
        self._value = value
        self._lock = threading.Lock()

    def get(self):
        return self._value

    def compare_and_set(self, expected, new):
        with self._lock:
            if self._value != expected:
                return False
            self._value = new
            return True


class FlashSale:
    def __init__(self, items):
        self.stock = AtomicCell(items)

    def try_buy(self):
        while True:
            left = self.stock.get()
            if left == 0:
                return False  # разпродадено
            if self.stock.compare_and_set(left, left - 1):
                return True
            # друг е сменил stock: прочети пак

Стъпка по стъпка, с думи

1. Последните 3 слушалки: наличността е 3. Нишките A и B викат try_buy() едновременно.
2. A прочита наличността: left = 3.
3. B я прочита, преди A да е сменила нещо: също 3.
4. B: compare_and_set(3, 2). „Ако още е 3, направи го 2.“ Още е 3, затова се записва 2. B купи.
5. A пробва същото: „ако още е 3…“. Вече е 2, затова нищо не се записва и отговорът е false. Нищо не е загубено.
6. A не чака и не се отказва: цикълът се завърта и A прочита пак: 2. Нито една нишка не е заспивала.
7. A: „ако още е 2, направи го 1“. Още е 2: записва се 1. A също купи.
8. Двама купувачи, две продадени, наличност 1. Ключалка няма: процесорът проверява и записва с една стъпка, а който загуби, само повтаря цикъла.

Никой не чака: нишката, която загуби, само повтаря два реда. Това се казва lock-free (без ключалка). Сто купувачи на 160 опита:

sale = FlashSale(100)
results = []  # list.append е безопасен от много нишки


def buyers():
    for _ in range(40):
        results.append(sale.try_buy())


threads = [threading.Thread(target=buyers) for _ in range(4)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Продадени:", results.count(True))
print("Отказани:", results.count(False))
print("Наличност:", sale.stock.get())

Изход

Продадени: 100
Отказани: 60
Наличност: 0

Колко пъти се е завъртял цикълът, е различно при всяко пускане. Затова програмата не го печата. Сборът е винаги един и същ: 100 продадени, 60 отказа, 0 на склад.

По-точно, за любопитните

В истински Python код не пишеш AtomicCell. Слагаш ключалка около проверката и намаляването, и тя прави същото:

class FlashSale:
    def __init__(self, items):
        self.stock = items
        self.lock = threading.Lock()

    def try_buy(self):
        with self.lock:
            if self.stock == 0:
                return False  # разпродадено
            self.stock -= 1
            return True

Изход

Продадени: 100
Отказани: 60
Наличност: 0

Пробвай

Предвиди изхода

Тук двете „нишки“ са написани една след друга в една нишка, за да е редът същият като в сцената при всяко пускане. Какво ще отпечата?

AtomicCell е класът от сцената.

stock = AtomicCell(3)
seen_by_a = stock.get()
seen_by_b = stock.get()
print("B:", stock.compare_and_set(seen_by_b, seen_by_b - 1))
print("A:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
seen_by_a = stock.get()
print("A отново:", stock.compare_and_set(seen_by_a, seen_by_a - 1))
print("Наличност:", stock.get())

Отговор

B: True
A: True
A отново: False
Наличност: 1

B: True
A: False
A отново: True
Наличност: 1

B: True
A: True
A отново: True
Наличност: 0

Провери

Пробвай

Попълни

Срещу какво сравнява CAS при купуването?

if self.stock.compare_and_set(, left - 1):

Провери

Пробвай

Намери грешката

Колега е опростил купуването. Всеки ред сам е безопасен, а при разпродажбата пак се продават 103 слушалки от 100. На кой ред е грешката?

Избери реда с грешката.

1def try_buy(self):2 if self.stock > 0:3 with self.lock:4 self.stock -= 15 return True6 return False

Провери

Проблем

Ценоразписът, който се сменя по средата

В 10:00 администраторът пуска промоцията: слушалки от 60 на 48 €, калъф от 15 на 12 €, кабел от 5 на 4 €. В същото време касите смятат колички. Ако цените са в един общ речник и се сменят една по една, касата може да прочете новата цена на слушалките и старата на калъфа:

# администраторът
prices["headphones"] = 48
prices["case"] = 12
prices["cable"] = 4

# касата, в същото време
total = sum(prices[item] for item in cart)

Количката излиза 68 €: сума, която не е била вярна в нито един момент. Не по старите цени (80 €), не по новите (64 €).

Идеята

Не променяй, а смени целия

Ценоразписът се чете много пъти и се сменя рядко. Тогава не го променяй никога. Направи го неизменим обект (immutable): веднъж създаден, той остава същият. За промоцията администраторът прави нов ценоразпис и сменя една референция: „текущият ценоразпис е този“.

• Обект, който никой не променя, се чете от колкото искаш нишки без никаква защита.
• Единственото общо нещо е референцията, а смяната ѝ е една атомарна стъпка.
• Касата взима референцията веднъж, в началото на количката, и смята цялата количка по нея. Тя вижда целия стар или целия нов ценоразпис, никога смес.

@dataclass(frozen=True) забранява смяната на полетата. Речникът вътре обаче може да се променя, затова е MappingProxyType: изглед към речника само за четене. Смяната е обикновено присвояване: current = PriceList(...). Присвояването на име в Python е една стъпка, затова касата чете или стария, или новия обект.

@dataclass(frozen=True)
class PriceList:
    version: int
    prices: MappingProxyType  # само за четене

    def total(self, cart):
        return sum(self.prices[item] for item in cart)

regular = MappingProxyType({"headphones": 60, "case": 15, "cable": 5})
promo = MappingProxyType({"headphones": 48, "case": 12, "cable": 4})
cart = ["headphones", "case", "cable"]
current = PriceList(1, regular)
mixed = 0


def admin():
    global current
    for v in range(2, 1002):
        prices = promo if v % 2 == 0 else regular
        current = PriceList(v, prices)  # нов снимък с една референция


def checkout():
    global mixed
    for _ in range(20_000):
        price_list = current  # един снимък за цялата количка
        total = price_list.total(cart)
        if total not in (80, 64):
            mixed += 1


threads = [threading.Thread(target=admin), threading.Thread(target=checkout)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print("Проверени суми: 20000")
print("Смесени суми:", mixed)
print(f"Последна версия: {current.version}, сума {current.total(cart)} €")

Изход

Проверени суми: 20000
Смесени суми: 0
Последна версия: 1001, сума 80 €

Касата е проверила десетки хиляди колички, докато ценоразписът се е сменял хиляда пъти, и нито една сума не е смесена. Колко колички са минали по стария и колко по новия, е различно при всяко пускане, затова програмата не го печата.

По-точно, за любопитните

Така работят и колекциите „копирай при запис“: CopyOnWriteArrayList в Java, ImmutableList в C#. Всяка промяна прави ново копие, а четенето е без ключалка. Струва си, когато се чете много, а се пише рядко. Ако се пише често, копирането става скъпо.

Неизменимостта е честна само докато е до дъно. Обект с final поле, което сочи променлив списък, не е неизменим: списъкът може да се смени отвън. Затова frozen=True не стига, а речникът е MappingProxyType.

Как е в другите езици: record и Map.copyOf с AtomicReference в Java; record с ImmutableDictionary и Volatile или Interlocked.Exchange в C#; frozen dataclass, tuple или MappingProxyType и присвояване в Python; Object.freeze и съобщения между Worker-и в JavaScript.

Идеята

Когато атомарното не стига

Резервацията мести бройка от наличността в резервираните. Правилото е, че двете заедно са винаги 10 000. Две атомарни променливи не го пазят:

stock = 10
reserved = 0


def reserve():
    global stock, reserved
    stock -= 1     # в Python и един ред не е атомарен,
    reserved += 1  # а двата заедно още по-малко

Между двата реда ревизорът вижда 9 999 общо. Атомарното пази една стойност. Когато правилото е за няколко стойности заедно, трябва ключалка около всички промени и около проверката:

class Warehouse:
    def __init__(self, stock):
        self.stock = stock
        self.reserved = 0
        self.lock = threading.Lock()

    def reserve(self):
        with self.lock:  # двете или нито една
            if self.stock == 0:
                return False
            self.stock -= 1
            self.reserved += 1
            return True

    def audit(self):
        with self.lock:
            return self.stock + self.reserved

    def report(self):
        with self.lock:
            return f"Наличност: {self.stock}, резервирани: {self.reserved}"

warehouse = Warehouse(10_000)
broken = 0


def reserver():
    while warehouse.reserve():
        pass


def auditor():
    global broken
    for _ in range(20_000):
        if warehouse.audit() != 10_000:
            broken += 1


threads = [threading.Thread(target=f) for f in (reserver, reserver, auditor)]
for thread in threads:
    thread.start()
for thread in threads:
    thread.join()
print(warehouse.report())
print("Счупени проверки:", broken)

Изход

Наличност: 0, резервирани: 10000
Счупени проверки: 0

По-точно, за любопитните

Друг начин без ключалка: двете стойности в един неизменим обект (наличност, резервирани), а смяната с CAS върху референцията. Нов обект с двете нови стойности замества стария наведнъж. Това съчетава двете идеи от урока, но ключалката обикновено е по-ясна.

Кога кое:

• една стойност, брояч или флаг: атомарна операция;
• проверка и смяна на една стойност: цикъл с CAS;
• данни, които се четат много и се сменят рядко: неизменим обект и смяна на референцията;
• няколко свързани стойности: ключалка.

Упражнение

Купон с ограничен брой

Реши задачата в редактора си.

Купонът „SPRING20“ може да се ползва 50 пъти. Осем нишки, всяка с по 10 клиента, опитват да го ползват едновременно. Напиши Coupon с try_use() така, че купонът никога да не се ползва повече от 50 пъти. С ключалка около проверката и намаляването. Отпечатай колко пъти е ползван, колко отказа е имало и колко остават:

Изход

Използвани: 50
Отказани: 30
Остават: 0

Още задачи

• Максимумът. Пази най-голямата поръчка на деня, докато много нишки добавят поръчки. Подсказка: CAS цикъл, който записва само ако новата е по-голяма.
• Две промоции. Направи ценоразписа с версия и пусни двама администратори, които публикуват едновременно. Как да не се загуби промоцията на единия? (Подсказка: смени референцията с CAS само ако версията е още тази, която си прочел.)
• Ревизорът без ключалка. Сложи наличността и резервираните в един неизменим обект и смени го с CAS. Провери, че ревизорът пак вижда винаги 10 000.

Тест

Провери се

1. Наличността е 6. Нишка вика CAS „ако е 5, направи го 4“. Какво става?

Нищо не се записва, а отговорът е „не успя“: нишката трябва да прочете пакНишката заспива, докато стойността стане 5Записва се 4

2. В tryBuy има „ако наличността е > 0“ и после „намали с 1“. И двата реда са атомарни. Защо пак се продава повече, отколкото има?

Защото атомарните операции понякога губят увеличенияНе може: щом всеки ред е атомарен, целият метод е безопасенМежду проверката и намаляването друга нишка може да вземе последната бройка: всяка стъпка е неделима, но двете заедно не са

3. Касите четат ценоразписа хиляди пъти в секунда, а той се сменя веднъж на ден. Какъв е най-добрият начин да го делят?

Един общ речник, в който администраторът сменя цените една по еднаНеизменим обект: администраторът прави нов ценоразпис и сменя една референция; всяка каса чете целия стар или целия новКлючалка около всяко четене на цена

4. Резервираш бройка: наличността пада с 1, а резервираните растат с 1. Ревизорът проверява, че сборът е винаги 10 000. Какво трябва?

Две атомарни променливиКлючалка около двете промени и около проверкатаНищо: сборът се смята след края

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Нишки · Защо нишки · Race condition · Заключване
• Продължава в: Deadlock · Производител и потребител · Как се тества конкурентен код
• Задачи по темата: Нишки и race conditions