#import "/utils/math.typ": *

== Особенности канальных средств связи

=== Буферизация

Обладает ли канал внутренней памятью

Случаи:
- Буфера нет

    Процесс-передатчик блокируется, пока процесс-получатель не считает данные

- Буфер неограниченной емкости (физически не реализуем)

    Процесс-передатчик никогда не ждет

- Буфер конечной емкости

    Самый частый случай

=== Модель передачи данных

- Потоковая модель

    - Операции приема/ передачи не интересуются содержанием данных и их
      происхождением
    - Данные не структурируются
    - Нет разделителей между записываемыми блоками
    - Можно считывать любое количество байт

- Модель сообщений

    - На данные накладывается некоторая структура
    - Отдельные сообщения явно разделены
    - Иногда сообщение хранит дополнительные данные, например, имя
      процесса-отправителя
    - Считывать можно только сообщение целиком

== Примеры средств связи

=== Pipe

- Потоковая модель
- Косвенная адресация
- Читать и писать может любое число процессов
- Однонаправленный

Через pipe могут общаться только процессы-родственники, так как
вход и выход в pipe не видны остальной ОС.

=== FIFO (именованный pipe)

Вход и выход именованы

Теперь общаться могут любые процессы, а не только родственники

== Надежность средств связи

Система считается надежным:
- Нет потери информации
- Нет повреждения информации
- Нет нарушения порядка
- Не появляется лишняя информация

== Как завершить связь?

Специальное действие для завершение нужно, если было нужно специальное средство
для завершения

Если один и процессов больше не будет использовать средство связи, то система
оповещает другой

= Нити исполнения (threads)

```
Ввести массив A
Ожидания ввода A
Ввести массив B
Ожидания ввода B
Ввести массив C
Ожидания ввода C
A = A + B
C = A + C
Вывсети массив C
Ожидание вывода C
```

Процессор много простаивает --- хочется распараллелить: нужен второй процесс:

#figure(
    table(
        columns: 3,
        stroke: none,
        table.header[*Процесс 1*][][*Процесс 2*],
        [Создание процесса 2], [], [],
        [], [Переключение контекста], [],
        [], [], [Доступ к общей памяти],
        [], [], [Ожидание ввода A и B],
        [], [Переключение контекста], [],
        [Доступ к общей памяти], [], [],
        [], [*TODO*], [],
    )
)

Нужны дополнительные действия:
- Породить процесс 2
- Получить разделяемую память
- Нужны переключения контекста

На одноядерной системе это неэффективно из-за доп расходов

Аналогия с железной дорогой:
- Поезд --- процессор с регистрами и данными в стеке
- Стрелки --- условные переходы
- Склады --- данные вне стрека/ операции ввода-вывода

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

Thread --- каждый из поездов

В процессе могут быть несколько thread-ов:
- Общие:
    - Системный контекст (всего процесса)
    - Код
    - Данные вне стека
- Разные:
    - Регистровый контекст
    - Стек
    - Системный контекст thread-а

Для создания нового thread-а используется системный вызов

Между thread-ами есть отношение родитель-ребенок

У thread-ов тоже есть состояния, как и у процессов

Master thread (главная нить) --- нить создаваемая при создании процесса

Thread-ы хороши, так как создавать их "дешевле", чем новые процессы

// TODO
// Процесс находится в сосотонии готовость, если хотя бы одна в состоянии
// готовность и ни одной в сотоии испольненеи
//
// Процесс в состоянии исполнение, если хотя бы одна нить в состоянии исполнение
//
// ОЖидание, если ни одной готовность исполнение, хотя бы одна в ожидании
//
// Закончил исполненеи, если все в исполнии

Thread-ы могут создавать либо на уровне библиотек, либо на уровне ядра

#figure(
    table(
        columns: 3,
        stroke: none,
        align: center,
        table.header[*Thread 1*][][*Thread 2*],
        text(fill: blue)[Создание нити 2], [], [],
        [Ввести массив A], [], [],
        [Ожидание ввода A], [], [],
        [], text(fill: blue)[Переключение контекста], [],
        [], [], [Ожидание ввода A и B],
        [], text(fill: blue)[Переключение контекста], [],
        [Ввести массив B], [], [],
        [Ожидание ввода B], [], [],
        [Ввести массив C], [], [],
        [Ожидание ввода C], [], [],
        [], text(fill: blue)[Переключение контекста], [],
        [], [], [A = A + B],
        [], text(fill: blue)[Переключение контекста], [],
        [C = A + C], [], [],
        [Вывести массив C], [], [],
        [Ожидание вывода C], [], [],
    )
)

= Алгоритмы синхронизации

Активность --- последовательное выполнение ряда действий, направленных на
достижение определенной цели

Операции внутри активности считаем атомарными (неделимыми):
между операциями "отвлекаться" можно, во время операции --- нельзя

Активность P из операций a b c

Активность Q из операций d e f

Последовательное выполнения PQ: a b c d e f

Псевдопараллельное выполнение (режим разделения времени):
порядок операций от каждой активности фиксирован, но они могут
чередоваться --- интерливинг. Например, *a* d e *b* *c* f

Если активности зависимы, то могут быть проблемы

Недетерминированный набор --- при одинаковых начальных результатах возможны
разные результаты

Детерминированый набор --- при одинаковых начальных данных результат всегда один

== Условие Бернштейна

Достаточные условия детерминированности набор

Входные данные активности (W): объединение множеств входных данных всех активностей
Выходные данные активности (R): объединение множеств выходных данных всех активностей

Условия (для двух активностей P и Q):
- $W(P) sect W(Q) = emptyset$
- $W(P) sect R(Q) = emptyset$
- $R(P) sect W(Q) = emptyset$

== Как чинить?

Нужно запретить "плохие" чередования

В недетерминированных наборах всегда встречается *race condition* (состояние
гонки).

*Mutual exclusion* (взаимоисключение): если процесс захватил ресурс, то больше
никто другой его не использует. Используется, когда не важно, кто первый
захватил ресурс

*Критические секции* --- участки, которые приводят к появлению race condition

Нужно сделать, чтобы критические секции выполнялись, как атомарные операции. Для
этого нужно ввести "пролог" и "эпилог" для критических секций

```
while (some condition) {
    entry section
    critical section
    exit section
    remainder section
}
```

Требования к алгоритмам синхронизации (от Дейкстры?):
- Алгоритм должен быть на уровне software
- Нет предположений об относительных скоростях выполнения и числе ядер
- Выполняется условие взаимоисключения (mutual exclusion) для критических участков
- Выполняется условие прогресса (progress):

    Только процессы, готовые войти в критическую секцию, принимаю решение, кто
    первый

    Решение не должно приниматься за конечное время

- Выполняется условие ограниченного ожидания (bound waiting):

    Каждый процесс "не пускают" не более заранее выбранного числа раз
