== Конкретные алгоритмы (программные)

=== Запрет прерываний

Существует команда процесса (Clear Interrupt), которая заставляет его
игнорировать почти все прерывания, кроме критических.

У процесса не могу отобрать процессор ни при каких условиях.

Существует парная команда, которая обрабатывает все запомненные и новые
прерывания.

```
while (some condition) {
    запретить все прерывания
    critical section
    разрешить все прерывания
    remainder section
}
```

Если в программе есть бесконечный цикл, то вся система насмерть зависнет.

Команды доступны только ядру. Прием используется только внутри кода ОС.

=== Переменная-замок

Общая переменная--замок для всех процессов в наборе

```
shared int lock = 0;
while (some condition) {
    while (lock == 1);
    lock = 1;
    critical section
    lock = 0;
    remainder section
}
```

Если между `while (lock == 1);` и `lock = 1;` перейдет передача управления, то
будет беда: оба процесса войдут в критическую секцию.

=== Строгое чередование

Введем порядок, в котором процессы будут проходить свои критические секции.

```
// для двух процессов
// i-ый процесс
shared int turn = 0;
while (some condition) {
    while (turn != i);
    critical section
    turn = (i + 1) % 2;
    remainder section
}
```

Если у процессов скорость выполнения сильно разная, то один из процессов может
очень долго ждать входа в критическую секцию.

=== Флаги готовности

```
shared int ready[proc_num] = {0};

while (some condition) {
    ready[i] = 1;
    while (ready[1 - i]);
    critical section
    ready[0] = 0;
    remainder section
}
```

Если оба процесса скажут, что они готовы, то беда: оба зависнут в цикле.

=== Алгоритм Петерсона

Совмещение идей очередности и готовности.

```
// для 0-ого процесса
shared int ready[2] = {0};
shared int turn;
while (some condition) {
    ready[0] = 1;
    turn = 1;
    while (ready[1] && turn == 1);
    critical section;
    ready[0] = 0;
    remainder section;
}
```

Все пять требований выполняются.


Для `n` процессов алгоритм сложнее, но существует.

=== Bakery algorithm (алгоритм булочной)

"Алгоритм регистратуры в поликлинике"

Основные идеи:
+ Процессы можно сравнивать по именам (id-шникам)
+ Перед входом в критическую секцию процессы получают "талон" с номером.
    Может случиться, что номера талонов совпали.
+ В критическую секцию входит тот, у кого меньше пара (номер талона, id-шник).

=== Заключение

Всё работало хорошо до 2005 года, пока не появились многоядерные системы

Раньше использовалась строгая модель консистентности памяти: из ячейки всегда считывается то значение,
которое последнее было туда записано.

Модель плоха с точки зрения hardware: кэши разных ядер и оперативу долго
синхронизировать.

Модель ослабили: синхронизацию производять только после накопления некоторого
числа изменений.

Алгоритмы синхронизации стали нерабочими: теперь после каждого изменения
shared переменной нужно атомарно синхронизировать кэши.

== Аппаратная поддержка

=== Команда Test-And-Set

```
int Test-And-Set(int* a) {
    int tmp = *a;
    *a = 1;
    return tmp;
}
// Но выполняется процессором атомарно
```

```
shared int lcok = 0;
while(some condition) {
    while (Test-And-Set(&lock));
    critical section
    lock = 0;
    remainder section
}
```

Нарушается условие ограниченного ожидания, но это легко чиниться.

=== Команда Swap

```
void Swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
```

```
shared int lock = 0;
int key = 0;
while (some condition) {
    key = 1;
    do Swap(&lock, &key);
    while (key);
    critical section
    lock = 0;
    remainder section
}
```

Тоже нарушается условие ограниченного ожидания, но это легко чиниться.


= Механизмы синхронизации

Механизмы внутри ОС

Недостатки программных алгоритмов:
+ Ослабленная модель консистентности памяти
+ Перевод цикла активного ожидания (busy wait) в цикл активного
    ожидания#footnote[это не всегда эффективно из-за накладных расходов]: "Кручение"
    в while-замке жрет процессорное время
+ Классические алгоритмы плохо работают в случае введения приоритетов процессов:

    Проблема, если низко приоритетный процесс вошел в критическую секцию, а у
    него отобрали управление:
        + высоко приоритетный не может войти в критическую секцию, так так там
            низко приоритетный
        + низко приоритетный не может выйти из критической секции, так как у
            него отняли управление

== Семафор Дейкстры

`S` --- семафор --- целая неотрицательная разделяемая переменная

При создании инициализируется любым неотрицательным значением

Допустимые *атомарные* операции:
+ `P(S)`:

    ```
    while (S == 0) block process
    S -= 1
    ```

+ `V(S):`

    ```
    S += 1
    ```

"Задача об обедающих философах"

== Проблема Producer--Consumer

Два процесса (в более сложной постановке процессов может быть больше):
+ Один производит информацию
+ Один --- потребляет

Обмениваются информацией через буфер конченого размера:
+ Если в буфере нет места, то Producer блокируется
+ Если в буфере пусто, то Consumer блокируется

Критическая секция --- работа с буфером

=== Решения с тремя семафорами

Семафоры:
+ Взаимоисключение работы буферов (`mut_ex`)
+ Блокировка Producer (`full`)
+ Блокировка Consumer (`empty`)

```
Semaphore mut_ex = 1;
Semaphore full = 0;
Semaphore empty = N;
```

#grid(
    columns: 2,
    row-gutter: 5pt,
    [Producer:], [Consumer:],

    // Producer
    ```
    while (1) {
        produce_item();
        P(empty);
        P(mut_ex);
        put_item();
        V(mut_ex):
        V(full);
    }
    ```,

    // Consumer
    ```
    while (1) {
        P(full)
        P(mut_ex)
        get_item();
        V(mut_ex);
        V(empty);
        consume_item();
    }
    ```
)

Вдруг совершили ошибку: в `Consumere` перепутали местами строки `P(full)` и
`P(mut_ex)`. Всё ломается: заходим в состояние вечного ожидания. Эту ошибку
сложно отследить, так как она возникает только при определенных условиях.

== Мониторы Хора (Hoare)

В ЯП встраиваются определенные конструкции --- мониторы Хора.

```
Monitor monitor_name {
    Описание внутренних переменных;
    void m1(...) {...}
    void m2(...) {...}
    ...
    void mn(...) {...}
    Блок инициализации переменных;
}
```

Со внутренними переменными можно работать только используя методы монитора.

Только один метод монитора может быть вызван (это достигается ОС и компилятором
языка).

=== Условные переменные

`Condition C;`

Всегда лежат внутри монитора.

Операции:
+ `C.wait`: Всегда блокирует данный процесс
+ `C.signal`: Разблокирует один процесс, который раньше выполнил `.wait`, если
    он есть. Процесс мгновенно вылетает из монитора.

=== Producer--Consumer

```
Monitor PC {
    Condition full, empty;
    int count;

    void put() {
        if (count == N) full.wait;
        put_item();
        ++count;
        if (count == 1) empty.signal; // Если ждал consumer, то разбудили его
    }

    void get() {
        if (count == 0) empty.wait;
        get_item();
        --count;
        if (count == N - 1) full.signal; // Если ждал producer, то разбудили его
    }

    { count = 0; }
}
```

#grid(
    columns: 2,
    row-gutter: 5pt,
    [Producer:], [Consumer:],

    // Producer
    ```
    while (1) {
        produce_item();
        PC.put();
    }
    ```,

    // Consumer
    ```
    while (1) {
        PC.get();
        consume_item();
    }
    ```
)

В этом методе хорошо то, что сложно налажать.
Плохо, что нужен ЯП с соответствующей конструкцией.
