Към съдържанието
wannacode

Заключване

Накратко: Ключалката (lock, mutex) пуска само една нишка наведнъж в критичната секция; в Java това е synchronized или ReentrantLock, а под нея стои само малкото, което трябва.

Проблем

Как да спреш другата каса

В урока „Race condition“ разпродажбата губеше продажби: две нишки правеха „прочети, извади, запиши“ наведнъж и едната презаписваше другата. Трите стъпки трябва да са едно цяло: докато една нишка е вътре, другата да чака отвън.

Точно това прави ключалката.

Идеята

Ключалката

Ключалката (mutex, от „mutual exclusion“, взаимно изключване) е обект с един собственик. Нишката я взима, прави своето и я пуска. Друга нишка, която я поиска междувременно, чака. Кодът между взимането и пускането е критичната секция: в нея е най-много една нишка.

В Java всеки обект може да е ключалка. synchronized (lock) { … } я взима при влизане в блока и я пуска при излизане, дори с изключение:
class Stock {
    private final Object lock = new Object();
    private int left;


    Stock(int left) {
        this.left = left;
    }


    void sell() {
        synchronized (lock) {
            left--;
        }
    }


    int left() {
        synchronized (lock) {
            return left;
        }
    }
}
Двете каси от миналия урок, със същите по 100 000 продажби:
Stock stock = new Stock(200_000);
Runnable checkout = () -> {
    for (int i = 0; i < 100_000; i++) {
        stock.sell();
    }
};
Thread a = new Thread(checkout);
Thread b = new Thread(checkout);
a.start();
b.start();
a.join();
b.join();
System.out.println("Поръчки: " + 2 * 100_000);
System.out.println("Продадени според склада:");
System.out.println(200_000 - stock.left());
Изход
Поръчки: 200000
Продадени според склада:
200000

Точно, при всяко пускане. Ключалката е поле, създадено веднъж: двете каси заключват една и съща.

Обектът ключалка е отделно частно поле, а не this. Така никой код отвън не може да заключи същия обект и да спре касите ти.

Виж го

Последната бройка, поправена

Проверката „има ли“ и вземането са в една и съща критична секция. Ако някой е вътре и проверява, другият не може да провери, преди първият да е взел:

class Stock {
    private final Object lock = new Object();
    private int left;


    Stock(int left) {
        this.left = left;
    }


    boolean reserve() {
        synchronized (lock) {
            if (left == 0) {
                return false;   // няма: отказ
            }
            left--;             // има: взимам бройката
            return true;
        }
    }


    int left() {
        synchronized (lock) {
            return left;
        }
    }
}
Стъпка по стъпка, с думи
  1. Остават 3 бройки, а 4 купувачи викат reserve() в един и същ момент.
  2. През synchronized минава само един, другите трима чакат пред него. Влиза купувач 1: вижда 3 и взима една. Остават 2.
  3. Купувач 1 излиза и пуска ключалката. Влиза купувач 2: вижда 2 и взима една. Остават 1.
  4. Купувач 2 излиза и пуска ключалката. Влиза купувач 3: вижда 1 и взима една. Остават 0.
  5. Купувач 4 влиза последен и вижда 0: отказ. Никой не видя число, което друг тъкмо сменя.
  6. 3 продадени, 1 отказ, наличност 0: вярно. Цената: купувачите се чакаха един друг пред турникета.

Четирима купувачи, три бройки, всички наведнъж:

Stock stock = new Stock(3);
boolean[] ok = new boolean[4];
List<Thread> buyers = new ArrayList<>();
for (int b = 0; b < 4; b++) {
    int buyer = b;
    Thread t = new Thread(() -> ok[buyer] = stock.reserve());
    buyers.add(t);
    t.start();
}
for (Thread t : buyers) {
    t.join();
}
int sold = 0;
for (boolean o : ok) {
    if (o) sold++;
}
System.out.println("Продадени: " + sold);
System.out.println("Отказани: " + (4 - sold));
System.out.println("Наличност: " + stock.left());
Изход
Продадени: 3
Отказани: 1
Наличност: 0

А ето двамата купувачи от миналия урок, които купуваха последната бройка. Таксуването на картата (~100 ms) е след ключалката: бройката е запазена, а картата се таксува, без другият да чака:

Stock stock = new Stock(1);
boolean[] bought = new boolean[2];
Runnable[] buyers = new Runnable[2];
for (int b = 0; b < 2; b++) {
    int buyer = b;
    buyers[b] = () -> {
        if (stock.reserve()) {
            pause(100);   // таксуването на картата, ~100 ms
            bought[buyer] = true;
        }
    };
}
Thread first = new Thread(buyers[0]);
Thread second = new Thread(buyers[1]);
first.start();
second.start();
first.join();
second.join();
int sold = (bought[0] ? 1 : 0) + (bought[1] ? 1 : 0);
System.out.println("Наличност преди: 1");
System.out.println("Продадени: " + sold);
System.out.println("Отказани: " + (2 - sold));
System.out.println("Наличност: " + stock.left());
Изход
Наличност преди: 1
Продадени: 1
Отказани: 1
Наличност: 0

Един продаден, един отказан, наличност 0. При всяко пускане.

Пробвай

Не забравяй да пуснеш

Освен synchronized Java има и ключалка-обект, ReentrantLock: lock() я взима, unlock() я пуска. Пускането е във finally, за да стане и при изключение:
class Stock {
    private final ReentrantLock lock = new ReentrantLock();
    private int left;


    Stock(int left) {
        this.left = left;
    }


    void sell() {
        lock.lock();
        try {
            left--;
        } finally {
            lock.unlock();
        }
    }


    int left() {
        lock.lock();
        try {
            return left;
        } finally {
            lock.unlock();
        }
    }
}

Какво пуска ключалката?

void sell() {
    lock.lock();
    try {
        left--;
    } finally {
        
    }
}

Пробвай

Ключалката, която не заключва

Колегата е добавил ключалка, но касите пак губят продажби. Кой ред е грешен?

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

Идеята

Колко струва ключалката

Ключалката работи, като кара нишките да се чакат. Колкото повече стои вътре една нишка, толкова повече чакат другите. Това е борбата за ключалката (contention).

Магазин с 10 бройки и четири поръчки наведнъж. Всяка поръчка вади бройка и праща имейл (~200 ms), а Network от урока „Защо нишки“ брои кръговете чакане:

class Network {
    private int inFlight = 0;
    private int rounds = 0;


    // Пита услуга по мрежата: отговорът идва след ~200 ms.
    String call(String service, String answer) {
        synchronized (this) {
            if (inFlight == 0) rounds++;   // никой не чака: нов кръг
            inFlight++;
        }
        try {
            Thread.sleep(200);
        } catch (InterruptedException e) {
            Thread.currentThread().interrupt();
        }
        synchronized (this) {
            inFlight--;
        }
        return service + ": " + answer;
    }


    synchronized int rounds() {
        return rounds;
    }
}
class Shop {
    private final Object lock = new Object();
    private final Network net;
    private int left = 10;


    Shop(Network net) {
        this.net = net;
    }


    // Лошо: имейлът тръгва, докато ключалката е взета.
    void orderSlow(String customer) {
        synchronized (lock) {
            left--;
            net.call("имейл", customer);
        }
    }


    // Добре: под ключалката е само наличността.
    void order(String customer) {
        synchronized (lock) {
            left--;
        }
        net.call("имейл", customer);
    }


    int left() {
        synchronized (lock) {
            return left;
        }
    }
}
С orderSlow имейлът е под ключалката:
Network net = new Network();
Shop shop = new Shop(net);
List<Thread> orders = new ArrayList<>();
for (int c = 1; c <= 4; c++) {
    String customer = "клиент " + c;
    Thread t = new Thread(() -> shop.orderSlow(customer));
    orders.add(t);
    t.start();
}
for (Thread t : orders) {
    t.join();
}
System.out.println("Поръчки: 4, наличност: " + shop.left());
System.out.println("Кръгове чакане: " + net.rounds());
Изход
Поръчки: 4, наличност: 6
Кръгове чакане: 4

Четири кръга: имейлите тръгват един по един, а последният клиент чака около 800 ms. С order под ключалката е само наличността:

Network net = new Network();
Shop shop = new Shop(net);
List<Thread> orders = new ArrayList<>();
for (int c = 1; c <= 4; c++) {
    String customer = "клиент " + c;
    Thread t = new Thread(() -> shop.order(customer));
    orders.add(t);
    t.start();
}
for (Thread t : orders) {
    t.join();
}
System.out.println("Поръчки: 4, наличност: " + shop.left());
System.out.println("Кръгове чакане: " + net.rounds());
Изход
Поръчки: 4, наличност: 6
Кръгове чакане: 1

Същата наличност, един кръг. Правилата:

  • Под ключалката само общите данни. Пресмятай, форматирай и чакай отвън. Вътре само прочети и запиши.
  • Никога чакане под ключалка: мрежа, диск, база данни, sleep. Вземи каквото трябва, пусни ключалката и тогава чакай.
  • Една ключалка за едни данни. Наличността и оборотът са отделни: всяко със своя ключалка, за да не се чакат касите, които пипат само едното.
По-точно, за любопитните
  • synchronized е повторно влизаща (reentrant): нишка, която вече държи ключалката, може да влезе пак в блок със същата ключалка, без да чака себе си. ReentrantLock също, оттам е и името.
  • ReentrantLock може повече от synchronized: tryLock() (взимам, ако е свободна, иначе правя друго), tryLock(100, TimeUnit.MILLISECONDS) и честна опашка с new ReentrantLock(true).
  • Без ключалка и left() може да върне старо число: ключалката гарантира и видимостта, за която пишеше в миналия урок.

Ключалката не е единственият начин. За един брояч има атомарни операции, които изобщо не карат нишките да се чакат, а данни, които никой не променя, не искат ключалка: урокът „Атомарни операции и неизменими обекти“. А две ключалки, които две нишки взимат в различен ред, могат да спрат програмата завинаги: урокът „Deadlock“.

Упражнение

Оборотът и поръчката от много бройки

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

Оборотът. Поправи задачата от миналия урок: две каси по 50 000 продажби по 3 €, а Revenue пази total с ключалка. Пусни програмата няколко пъти: оборотът трябва да е един и същ всеки път.

Очакваш
Каса 1: 50000 продажби
Каса 2: 50000 продажби
Оборот (€):
300000

Поръчка от няколко бройки. В склада има 5 бройки. Напиши reserve(count): ако има поне count, взима ги и връща истина, иначе не взима нищо и връща лъжа. Трима клиенти искат по 2 бройки наведнъж, всеки в своя нишка.

Очакваш
Поръчани: 3
Приети: 2
Отказани: 1
Наличност: 1

Още задачи

  • Цената на ключалката. Пусни двете каси по 1 000 000 продажби с ключалка и без нея и засечи времето. Колко по-бавно е с ключалка? А с 8 каси?
  • Две ключалки. Добави оборот към склада, със своя ключалка. Продажбата вади от наличността и добавя към оборота. Пази ли двете заедно, ако някой прочете наличност и оборот между двете ключалки? - tryLock. Направи продажба, която чака ключалката най-много 50 ms с tryLock, а ако не успее, връща „опитай пак“.

Тест

Провери се

1. Две нишки викат sell(), който прави left-- под една и съща ключалка. Какво става, когато втората стигне до ключалката, докато първата е вътре?
2. Проверката „има ли бройки“ е под ключалката, а изваждането е в отделен блок под същата ключалка. Двама купуват последната бройка. Какво става?
3. Под ключалката е изваждането от наличността и изпращането на имейл (~200 ms). Четири поръчки идват наведнъж. Колко чака последната?
4. Какво е грешно в synchronized (new Object()) { left--; }? (C#: lock (new object()), Python: with threading.Lock())

Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·