class: title, center, middle

# Операционные системы

---
# Оглавление

1. [Введение](#intro)
2. [Управление памятью](#mem-management)
3. [Системные вызовы](#syscall)
4. [Невытесняющее планирование](#nonpreempt-scheduling)
5. [Таймеры и прерывания](#timers-interrupts)
6. [Вытесняющее планирование](#preemt-scheduling)
7. [Виртуальная память](#virtual-memory)
8. [Процессы](#processes)
9. [Взаимное исключение](#mutual-exclusion)
10. [Задачи взаимодействия процессов](#processes-interaction)
11. [Блочные устройства и файловые системы](#block-devs-fs)
12. [Многопроцессорные системы](#multiprocess-systems)
13. [Кеши и мультипроцессирование](#caches-in-multiproc)
14. [Сетевое программирование](#network-programming)
15. [Распределенные системы](#distributed-systems)
16. [Безопасность](#security)

[Практика](./practice/practice.html)

---
class: title, center, middle
name: intro

## Введение

???
На полпары.

---
# Про курс

Антон Козлов (<anton.p.kozlov@gmail.com>)

1. CS226 с одной стороны
 1. Э. Таненбаум "Современные операционные системы"

2. Практическая работа с другой
 1. ~~Э. Таненбаум, А. Вудхалл "Операционные системы. Разработка и реализация"~~
 2. https://github.com/embox/embox
 3. https://github.com/AntonKozlov/os226-2020

---
# Операционная система

```asciidrawing
+------------------+
|   Applications   |
+------------------+
| Lib/Util/Service | \
+------------------+  OS
|      Kernel      | /
+------------------+
|     Hardware     |
+------------------+
```

.def[Операционная система] -- это
1. .def[расширенная вычислительная машина]:
 * Дополнительные инструкции
 * Абстракция от оборудования
2. .def[менеджер ресурсов]:
 * временных
 * пространственных

---
# История .def[по Таненбауму]

Первое поколение (1945-1955):
* Электронные лампы
* ОС отсутствуют
* Программирование: машинный язык на коммутационной панели/электрические схемы

Второе поколение (1955-1965):
* транзисторы
* перфокарты
* системы пакетной обработки (IBM FSM)

Третье поколение (1965-1980):
* интегральные схемы
* программно-совместимые машины: ОS/360
* spooling
* многозадачность
* разделение времени: CTSS, MULTICS, UNIX

---

# История .def[по Таненбауму]

4 поколение (1980-):
* DOS, Mac OS, Windows, Linux, ….
* интерфейс пользователя
* сетевые, распределённые ОС (Plan9)
* мобильные ОС (Android, iOS)

Специализация ОС (для серверов/настольных компьютеров/…):
 * Что предоставляют?
 * Какие ограничения накладывают?

---
# История .def[по Хансену]

.it[P. Brinch Hansen, The evolution of operating systems]

> Автор оглядывается на первые полвека сущестования операционных систем и отбирает лучшие статьи о классических операционных системах.
> Эти статьи охватывают всю историю этой области, начиная с систем пакетной обработки в 1950-х годах, заканчивая распределёнными системаами в 1990-х.
> Каждая статья описыват операционную систему, которая совмещает значительные идеи элегантным способом.
> Большинство из них написано пионерами, которые обладали видением и энтузиазмом чтобы претворить их в жизнь.
> Автор делает выжимку из каждой статьи и делает вывод, что операционные системы основаны на удивительно небольшом количестве идей, которые всегда будут интересны.

---
## Open Shop: the idea of operating systems

* Каждому пользователю предоставлялся промежуток времени для работы на машине
* Существенную часть времени пользователь подготавливал окружение для работы
* Появляется идея об операцонной системе, призванная снизить накладные расходы на работу. "Если бы [наш компьютер] был бы намного больше, но с ним взаимодейстовали так же, количество возможных пользователей осталось бы прежним"

---
## Batch Processing: tape batching; first-in, first-out scheduling

* Компьютер может планировать свою собственную работу с помощью программного обеспечения
* Работа пользователей была оптимизированна: им теперь просто не позволялось работать на машине ("closed shop")
 * Данные и программы подготавливалась на перфокартах
 * Устройства для чтения карт и печати результатов были узким горлышком
 * .def[batch processing]: небольшой компьютер переписывал данные со множества перфокарт на ленту, которая потом отправлялась на исполнение в основной компьютер
 * Пока основной компьютер проводил вычисления (вход и выход на ленте), вспомогательный успевал распечатать данные с предыдущей выходной ленты и подготовить следущую
 * Задачи на ленте исполнялись последовательно (.def[FIFO]) -- лента была слишком медленная для произвольного доступа
 * Чем больше задач запланировано на один раз, тем меньше простоя и тем дольше пользователь ждал результатов

---

## Multiprogramming: processor multiplexing, indivisible operations, demand paging, input/output spooling, priority scheduling, remote job entry

* 1960: появление оперативной памяти, вторичной памяти с произвольным доступом, аппаратных прерываний
* .def[Multiprogramming]: симуляция одновременной работы нескольких программ и одновременная обработка операций ввода/вывода
 * .def[spooling]: обработка прерываний параллельно с вычислением, простейшая форма multiprogramming
* Становится возможна политика "самая-короткая-задача", т.к. задачи и промежуточные вычисления хранятся на жёстких дисках с быстрым произвольным доступом
* Подгрузка страниц по запросу позволяла иметь прозрачное взаимодейтсвие с памятью и диском

## Timesharing: simultaneous user interaction, on-line file systems

* .def[Разделение времени]: одновременное взаимодействие со многими пользователями.
У каждого есть отдельная консоль, компьютер может реагировать на каждое нажатие.
Пользовательские задачи занимают относительно малое количество времени, нужно быстрое переключение между задачами.
* Иерархическая файловай система с мгновенным доступом к файлам

---
## Concurrent Programming: hierarchical systems, extensible kernels, parallel programming concepts, secure parallel languages

* Борьба со сложностью операционных систем
* .def[Иерархическая система]: несколько программных уровней, преобразующих физческую машину в более понятную абстрактную
* Зарождение параллельного программирования: семафора, корутины,.. и безопасных языков программирования
* Появление .def[ядра] операционной системы; отделение политики от реализации

## Personal Computing: graphic user interfaces

* Графический дисплей, мышь, Ethernet
* Персональные компьютеры изначально сильно проще, чем большие машины
* ... программное обеспечение тоже, включая языки программирования

## Distributed Systems: remote servers

* Серверы предоставляют ресурсы клиентам
* Удалённый вызов процедур: насколько надёжен?
* Большинство распределённых систем основано на классических (обособленных) операционных системах

---
# ОС - виртуальная машина

```asciidrawing

OS                        os226

Как может выглядеть виртуальная машина на ОС ("ОС внутри ОС")?

Для начала:
 * программы - процедуры
 * виртуальная машина совпадает с физической

---
class: title, center, middle
name: mem-management

## Управление памятью

---
# Управление памятью

.def[Управление памятью] - поддержка информации о блоках свободной/занятой памяти и удовлетворение запросов:
 * выделение памяти опредлённого размера
 * (опционально) освобождение ранее выделенной памяти

Существенные ограничения:
* Запросы поступают online (последующие запросы неизвестны)
* Выделенная память не может быть самостоятельно
 * отозвана
 * (опционально) перемещена

Литература:
* Кнут, Искусство программирования, т.1, 2.5
* Wilson, Johnstone,... Dynamic Storage Allocation

---
# Типы и примеры

Автоматическое управление памятью:
 * сборка мусора
 * подсчёт ссылок

Ручное:
 * Выделение в куче (malloc/free)
 * специализированные аллокаторы (pool, ...)

Статическое:
 * глобальные данные
 * выделение на стеке

```asciidrawing
 | уменьшается гибкость
 | уменьшаются накладные расходы
 v увеличивается предсказуемость (в смысле real-time)
```

---
# Иерархия выделения памяти

ОС выделяет память большими блоками. Приложению нужны маленькие блоки.

.def[Иерархия выделения памяти] - упорядоченное множество алокаторов памяти.

Примеры:

```asciidrawing

+-------------+      +-------------+
| malloc/free |      |     pool    |
+-------------+      +-------------+
|     OS      |      |      GC     |
+-------------+      +-------------+
                     |      OS     |
                     +-------------+
```

---
# Ручное выделение

Обязательно:
 * освобождение ранее выделенной памяти
 * память не может быть перемещена

Составные части:
* .def[Стратегия] - направлена на эксплуатирование особенностей в потоке запросов.
* .def[Политика] - процедура размещения блоков памяти, допустимых стратегией.
* .def[Механизм] - набор алгоритмов и стурктур данных, реализующих политику.

Основные метрики:
 * фрагментация памяти
 * скорость выделения/освобождения

Метрики подсчитываются на записях .def[трасс] (последовательностях запросов) реальных программ.

---
# Фрагментация

.def[Внешняя] - наличие достаточного количества свободной памяти, которая не может быть выделена. Например, много несмежных блоков маленького размера. Причины появления:
 * точечные освобождения
 * смена фаз исполнения программы

.def[Внутренняя] - выделенный блок памяти больше, чем запрашиваемый. Причины:
 * отсутствует свободный блок подходящего размера
  * большие блоки _могут_ быть разделены для удовлетворения запроса. 
 * реализация не поддерживает блоки меньшего размера
 * политика не разделяет блоки, чтобы снизить внешнюю фрагментацию

---
# Последовательный поиск

Свободные блоки находятся в списке.

```asciidrawing

free_list
         |
         v
+-------+----+---+---+--------------+----+---+---+
|#######|next|len|...|##############|NULL|len|...|
+-------+----+---+---+--------------+----+---+---+
           |                           ^
           |                           |
           +---------------------------+
```

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

Освобождение: добавляем в список свободных.

---
# Последовательный поиск

Выбор свободного блока:
* First Fit (*)
* Best Fit (*)
* Next Fit
* Worst Fit, Optimal Fit, Half Fit

Добавление в список свободных:
* LIFO
* FIFO (*)
* Address Ordered (*)

Проблемы масштабирования: с ростом количества блоков время поиска растёт

???

# Optimal fit

Campbell introduced an optimal fit policy which is a variant of next fit intended to improve the
chances of a good fit without too much cost in extra searching. It is not optimal in any useful
sense.

The basic idea is that the allocator looks forward through the linear list for a bounded number of
links recording the best t found It then proceeds forward looking for another fit at least as good as
what it found in that sample  range If it fails to find one before traversing the whole list it uses the best
fit it found in the sample range. That is it degenerates into exhaustive best fit search when the sample
contains the best fit.

## J. A. Campbell, A note on an optimal-fit method for dynamic allocation of storage

### Abstract

The problem of maintaining a free-storage list of variable-size blocks when requests for storage are also of various sizes is considered. A strategy is proposed which is directly related to the solution of the optimal stopping problem on a Markov chain of given length. Results of tests which show a superiority of this strategy over the conventional first-fit method under some conditions are presented.

---
# Слияние

.def[Слияние] - объединение освобожденного блока с соседними свободными.

```asciidrawing

free_list
         |            free()
         v            v
+-------+----+---+---+--------------+----+---+---+
|#######|next|len|...|##############|NULL|len|...|
+-------+----+---+---+--------------+----+---+---+
           |                           ^
           |                           |
           +---------------------------+
```
```asciidrawing

free_list
         |
         v
+-------+----+---+-------------------------------+
|#######|NULL|len|...............................|
+-------+----+---+-------------------------------+
```

---
# Замечания

"Небольшой" остаток можно не отделять: повышает внутреннюю фрагментацию, уменьшает внешнюю.

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

Для освобождения нужно знать размер занятой области:
 * обязать пользователя указывать его
 * хранить размер выделенной области

---
# Граничные маркеры

```asciidrawing
Блок
|         Выделенная память
|         |
v         v
+----+---+-----------+----+---+
|size|tag|           |size|tag|
+----+---+-----------+----+---+
```

tag: бит занят/свободен

По адресу блока (занятого или свободного) можно определить определить соседние блоки. Позволяет ускорить слияние.

size + tag можно хранить в одном слове.

---
# Двоичные близнецы

Вариант Linux'а:

```asciidrawing
  +---+---+   +-+   +-+
0 |map|   |<->| |<->| |
  +---+---+   +-+   +-+
1 |map|   |
  +---+---+   +-------+
2 |map|   |<->|       |
  +---+---+   +-------+
```
Память управляется блоками по степеням двойки. Для каждой степени:
 * список свободных
 * битовая карта, каждый бит - пара блоков: 1 - оба заняты или свободны

Легко вычислить .def[близнеца] и определить его состояние => легко сливать
```
buddy_block(block, size) = block ^ (1 << size);
```
```
alloc/free(block, size_log2):
  binary_map[(block-base) >> (1+(size_log2)] ^= 1

```

---
# Метод близнецов

Частный случай раздельных свободных (best fit) + быстрый способ слияния.

Состояние (занят/свободен) хранится вне блоков:
 * низкая внутренняя фрагментация для объектов степени 2.

Большая фрагментация:
* для небольших объектов
* не сливает смежные блоки, не являющиеся близнецами

Бывают
* Двоичные близнецы
* Фибоначчи
* Взешенные

---
# Раздельные списки свободных

.def[Раздельный поиск] - отдельный список свободных блоков для каждого
 * размера
 * размера, округляемого вверх
 * класса размеров

.def[Раздельное хранение] - объекты разных размеров размещаются в разных областях => не нужно хранить размер каждого, только один размер для области

---
# Индексированный поиск

Используются структуры данных для поиска блока согласно требуемым характеристикам.

Пример: Best Fit по двоичному дереву, упорядоченному по размеру.

## Поиск по битовой шкале

Одна или несколько битовых шкал, хранящих пометки занят/свободен.

---
# Отложенное слияние

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

Можно не сливать сразу, а поддерживать несколько списков для недавно освобожденных блоков разных небольших размеров - кэш для аллокатора.

Очищать список:
 * частично или полностью
 * периодически/по исчерпанию основной кучи/по достижению предела длины
 * ...

Пример: Quick Fit

---
# Специализированные аллокаторы

* obstack
* pool
* slab

Литература:
 * Corbet, Rubini, Linux Device Drivers, Third Edition, ch. 8
 * Gorman, Understanding The Linux Virtual Memory Manager, ch. 8
 * Bonwick, The Slab Allocator

---
# Obstack

Стек-подобная структура (“object stack”).

Выделение - передвижение вершины obstack. Освобождение всего obstack.

```c
struct obstack {
        void *base;
        void *next;
        void *end;
}

alloc(size) {
        ...
        void *r = next;
        next += size;
        return r;
}
```

Свойства: быстрое, эффективное, удобное, но опасное.

---
# pool (Embox)

```c
struct pool {
        char *mem;
        unsigned long membsz;
        char *freestart;
        char *freeend;
        struct pool_free_block {
                struct pool_free_block *next;
        } *free;
}
void *pool_alloc(struct pool *p) {
        struct pool_free_block *fb = p->free;
        if (fb) {
                p->free = fb->next;
                return fb;
        }
        if (p->freestart < p->freeend) {
                void *r = p->freestart;
                p->freestart += p->membsz;
                return r;
        }
        return NULL;
}
```

---
# slab

```
struct foo {
	kmutex_t m;
	kcondvar_t cv;
	...
};

```

slab:
 * информация о типе объектов: размер, функция-конструктор,...
 * список кеш-блоков, каждый:
  * память под N объектов
  * состояние (полный/частично-свободный/свободный), статистика

* DRY
* учитывается в отладочной информации и статистике выделения
* позволяет другим подсистемам запрашивать память из SLAB

---
# slab - операции

## To allocate an object:

```
if (there’s an object in the cache) {
	take it (no construction);
} else {
	allocate memory;
	construct the object;
}
```

## To free an object

`return it to the cache (no destruction required);`

## To reclaim memory from the cache:

```
take some objects from the cache;
destroy the objects;
free the underlying memory;
```

---
class: title, center, middle
name: syscall

## Системные вызовы

---
# Взаимодействие с ОС

```asciidrawing

os226

--
Как программы взаимодействуют с ОС?.. Варианты:

* статическая линковка


--

* динамическая линковка

--

* ...

---
# Системные вызовы

Динамическая диспетчеризация:

```c
int main(int argc, char *argv[]) {
        printf("Hello, world\n");
        return 0;
}
```

```c
int main(int argc, char *argv[]) {
        const char *msg = "Hello, World!\n";
        const int len = strlen(msg);
        write(1, msg, len);
        return 0;
}
```
--

```sh
(gdb) disas write
   ...
   0x000000000043bbea <+10>:    mov    $0x1,%eax
   0x000000000043bbef <+15>:    syscall
   ...
```
Инструкция `syscall` процессора x86-64 генерирует .def[исключение].

---
# Исключения

```asciidrawing
        +--------+       +--------+      +---------+
        |  CPU   |       | Memory |      |   I/O   |
        +--------+       +--------+      +---------+
            ^                ^                ^
            |                |                |
            v                v                v
Bus +---------------------------------------------------
    +---------------------------------------------------
```

.def[Исключение] - событие, при котором процессор переходит на заранее определённый обработчик (процедуру)

1. Синхронные (внутренние)
 1. деление на ноль
 2. ошибки доступа к памяти
 3. инструкции программных исключений
 4. ...
2. Асинхронные (внешние)
 1. прерывания

---
# Обработка исключений

1. Сохранение базового контекста CPU
2. Подготовка и переключение в контекст обработки исключения
3. Сохранение полного контекста
4. (!) Обработка исключения
5. Acknowledgement исключения
6. Восстановление контекста

Обработчик исключения может менять контекст.

---
# Системный вызов

.def[Системный вызов] - исключение с семантикой вызова (определённой функции ядра).

ОС расширяет машину системными вызовами:

```asciidrawing
    +----------------------+
    |            App       |
    +----------------------+
    |         OS           |
    +------------------+---+
    |     Hardware     |
    +------------------+
```
Обработчик исключения может менять контекст =>
так можно возвращать значение.

---
# Режимы работы CPU

.def[Ядро] - участок ОС, исполняющийся в системном режиме (привелегированном, режиме супервизора).

В пользовательском режиме заблокирована часть инструкций, регистров, адресов памяти,..

```asciidrawing
        +------------------+
        |        App       |
    +---+------------------+
    |         OS           |
    +------------------+---+
    |     Hardware     |
    +------------------+
```

---
# Типы ядер ОС

* .def[Монолитные] - все функции находятся в ядре:

* планировщик
 * драйвера устройств
 * сетевые протоколы, файловые системы
 * реализация системных вызовов ФС, сети,...

Примеры: Linux, *BSD

* .def[Микроядерные] - только минимальная часть в ядре.

Большинство функций реализуется реализуется системными процессами, в ядре только:
  * планировщик
  * обработка исключений
  * обмен сообщениями между процессами

Примеры: MINIX, L4

* .def[Экзоядерные] - ядра нет/только мультиплексоры устройств

---

Часть определения .def[сигнала] - событие получаемое программой при исполнении некорректной инструкции (так же, как CPU генерирует исключение):
 * неопределённая инструкция -- SIGILL
 * привелегированная инструкция (только в системном режиме) -- SIGSEGV
 * инструкция с некорректными аргументами:
   - доступ по неправильному адресу -- SIGSEGV
   - деление на ноль -- SIGFPE

Поведение по умолчанию: завершить процесс, игнорировать, сгенерировать core файл, ...

Может быть переопределено: вызвать функцию-обработчик.

```c
void hnd(int sig) { ... }
int main() {
        signal(SIGSEGV, hnd);
```
```c
void hnd(int sig, siginfo_t *info, void *ctx) { ... }
int main() {
       struct sigaction act = { .sa_sigaction = hnd };
       sigaction(SIGSEGV, &act, NULL);
```

<!--
# Исследуем...

Rob Pike, Systems Software Research is Irrelevant:

* ... software is stagnant
* If systems research was relevant, we’d see new operating systems and new languages making inroads into the industry.
* Instead, we see a thriving software industry that largely ignores research, and a research community that writes papers rather than software.
* Change of scale: ... industry tends to do the big, defining projects operating systems, infrastructure, etc. - and small research groups must find smaller things to work on.  Three trends result:
  1. Don’t build, measure. (Phenomenology, not new things.)
  2. Don’t go for breadth, go for depth. (Microspecialization, not systems work.)
  3. Take an existing thing and tweak it.

-->
<!--
# Д/З

Перенести ваш шелл под Linux:

```
$ echo Hello, World
Hello, World
```
```
$ echo test1; echo test2
test1
test2
```

Добавить перенаправление pipe

```
$ seq 1 100 | grep 2 | grep 0
```

Можно считать, что и все программы лежат в `/usr/bin`

https://github.com/AntonKozlov/eduos/tree/next/shell
```
$ make -C shell test
```
```
$ (cd shell; make test)
```
-->

---
class: title, center, middle
name: nonpreempt-scheduling

## Невытесняющее планирование

---
# Процесс

.def[Процесс] - исполняемая программа (программа + её состояние) ~~ экземпляр виртуальной машины

```asciidrawing

+-------------------------------+
---------+                               +----.....->
         +-------------------------------+          t
         |                               |
         main() -- включение             exit() -- выключение
```

Пользовательская сессия:

```
$ app1
$ app2
$ app3 ; app4
```

```asciidrawing

Шелл  Задача 1  Шелл  Задача 2
         |     |         |     |
         +-----+---------+-----+---------+
---------+     |         |     |         +----.....->
         +-----+---------+-----+---------+          t
```

---
# Планирование

.def[Планирование] - распределение временного ресурса процессора(ов);
процесс определения, какой пользовательский процесс или поток (задача) будут исполняться.

Литература:
* Таненбаум, Современные ОС, 2.4

Пакетный режим:

```asciidrawing

Задача 1     Задача 2    ...
         |            |           |
         +------------+-----------+---------
---------+            |           |         ......->
         +------------+-----------+---------       t
         |
         Включение
```

Планирование: можно ли извлечь выгоду изменением порядка задач?

---
# Невытесняющее планирование

.def[Невытесняющее планирование] - планирование, при котором следующая задача выбирается по завершению предыдущей

.def[Планировщик] - модуль ОС, отвечающий за планирование задач (процессов)

Планировщик:
 * Очередь задач и механизм её поддержания (одно/двусвязный список, куча, ...)
 * Политики определения следущей задачи

---
# Задача

Задача:
 * Окружение ОС (если нужно, например):
  * таблица файловых дескрипторов
  * имя приложения на диске
  * адрес функции входа
  * ...
 * Состояние:
  * готова (для исполнения)
  * выполняется
  * завершена

Вызовы планировщика:
 * добавить новую задачу
 * текущая задача завершается, удалить её из очереди, запустить новую задачу (`exit()`)

---
# Реализация

Очередь - (дву)связный список:
 * queue.h (BSD)
 * list.h (Linux)
 * dlist/slist (Embox)

Состояние может быть представлено неявно:

состояние | представление
---|---
готова | в очереди, не первая
выполняется | первая в очереди
завершена | не в очереди

---
# Политика

.def[Политика] - алгоритм выбора следующей задачи

* FIFO

 * Наиболее короткая сначала: (добавляем "время работы" к задаче)
```
t10: task1
t20: task2
```
Важно: уменьшаем среднее время отклика

* Наиболее приоритетная сначала:

.def[Приоритет] - абстрактное значение, обозначающее важность для пользователя.
```
p10: task1
p20: task2
```

* С учётом принадлежности пользователю:

```
task1 (petya)
task2 (petya)
task3 (vasya)
```
---
# Политика

* С указанием крайнего времени завершения (deadline)

```
d10: task1
d20: task2
```

Нетривиальные политики должны уметь:
 * получать информацию о задачах заранее
 * получать задачи и откладывать их

Невытесняющее планирование:
 * вызывается относительно редко
 * политика определяет расписание на достаточно долгое время (long-term scheduling)
 * выбор нельзя отменить, к политике предъявляются определённые требования оптимальности

---
# Наблюдение

```asciidrawing
   main                                       +--+
   |                                          |##| в ядре
   +--+----------....----+--+---------        +--+
---+  |##########....####|  |#########...->
   +--+----------....----+--+---------    t   +--+
      |                     |                 |  | в пользовательском
      read                  read              +--+ режиме

```

В ядре (`read`):
* Запрос к оборудованию
* Ожидание результата
* Выход из системного вызова

```c
request()
while (!hw_ready()) {
	microsleep();
}
```

Это .def[активное ожидание]

---
# Пассивное ожидание

```asciidrawing

main                irq
   |                   |
   +--+--+             +--+--+
---+  |##+-------------+##|  +---...>
   +--+--+             +--+--+      t
      |
      read

```
```

bool done = false;
void irq_handler(void) {
        done = true;
}

set_irq_handler(&irq_handler);
request()
while (!done) {
        yield(); // переводит процессор в режим пониженного
                 // энергопотребления.
                 // В UNIX: pause(2)
}
```

---
# Кооперативное планирование

Разбить приложение на набор зависимых задач.
```
int main() {
	int ret = read(0, buf, sizeof(buf);
	...
}
```
```asciidrawing
        |
        v
```

```
void main() {
	aread(0, buf, sizeof(buf), &readcont);
}

void readcont(int ret, char *buf, size_t size) {
	...
}
```

Пример: `aio(7)`

---
# Реализация

Новые состояния задачи:
 * завершена
 * ожидает (не в очереди + бит отличия от "выполнена")

состояние | представление
---|---
завершена | не в очереди
ожидает | не в очереди + бит отличия

Новые вызовы планировщика:
 * добавить новую ожидающую задачу
 * разбудить задачу ("ожидает" -> "готова")

---

```asciidrawing
   main
   |
   +--+--+                  +--
---+  |##+------------------+  ......>
   +--+--+                  +--      t
      |           ^
      read        |
                  |(относится к 1й задаче)
                  |
         main    irq
         |       |
         +-------+--+---+---+
---------+       |##|   |###+-----...>
         +-------+--+---+---+        t
                        |
                        read
```

```c
void irq_handler(task) {
	wake(task);
}

add_waiting_task(&task);
set_irq_handler(&irq_handler, &task);
request()
```
---
# Кооперативные политики

Кооперативные политики учитывают принадлежность задач к процессам:
* round-robin: выполнять различные процессы по порядку
 * по сути, FIFO
* наименьшее _оставшееся_ время
* динамический приоритет (класс политик, накапливать статистику выполнения)
  - честная политика: стараться распределять время согласно соотношению приоритетов
  - многоуровневая очередь: позволяет выбрать разные политики для эквивалентных процессов

Кооперативная политика вызывается намного чаще пакетной.

---
class: title, center, middle
name: timers-interrupts

## Таймеры и прерывания

<!--
Измерение времени

* Ограничение времени исполнения задачи
* Поддержка запроса sleep
-->

---
# Аппаратный таймер

Устройство, отслеживающее время.

```asciidrawing

+---------+     +---------+
| counter |     | counter |     ...
+---------+     +---------+
                | reload  |
                +---------+
```
* counter: декрементируется аппаратурой с определённой частотой (например, 1Mhz)
* reload: (если есть и используется) новое значение counter, загружается аппаратурой автоматически по обнулению counter.

Когда counter становится равным `0`, генерируется прерывание.

Из частоты обновления counter определяется время возникновения прерывания (например, 20ms <-> counter = 20 * 10.sup[3])

Reload повышает точность периодической генерации прерываний за счёт отсутствия задержки программной записи в сounter во время прерывания.

---
Аппаратный таймер может быть сложнее:

.fitimg[![](pwm-output-mode.jpg)]

---
# Использование 1

Отмерение временных интервалов:
 * периодических
 * однократных

Пример: ограничение времени выполнения задачи.

После выбора новой задачи, перед её исполнением, программируем таймер, например, на 100ms.

Когда задача завершается, останавливаем таймер.

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

---
# Программные таймеры

Аппаратный таймер может отслеживать только 1 период времени.
```
sleep(100, hnd);        sleep(200, hnd);        while(true) { }
```

Программные таймеры - множество таймеров, основанных на одном аппаратном.

```asciidrawing
+- - - - - - -+    +- - - - - - -+           +- - - - - - -+
|  counter 1  |    |  counter 2  |           |  counter N  |
+- - - - - - -+    +- - - - - - -+    ...    +- - - - - - -+
|     ...     |    |     ...     |           |     ...     |
+- - - - - - -+    +- - - - - - -+           +- - - - - - -+

```

Каждый программный таймер содержит собственный обработчик прерывания (.def[программный] == виртуальный).

Задача обработчика прерывания аппаратного таймера: для всех программных таймеров
 * поддерживать counter
 * вызывать обработчики прерываний

---
# Реализация

Очередь - двусвязный список:
 * queue.h (BSD)
 * list.h (Linux)
 * dlist/slist (Embox)

Программируем reload = минимальным измеримым отрезоком времени (например, 1ms).

Тогда, counter программного таймеры содержит количество отрезков, оставшихся до истечения программного таймера (например, 20 для 20ms с отрезком в 1ms)

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

---
# Оптимизации

## Оптимизация обработки

Упорядочить таймеры по возрастанию срока срабатывания. Значения счётчиков (C.sub[i]) - функция от срока срабатывания (T.sub[i])

C.sub[0] = T.sub[0]

C.sub[i] = T.sub[i] - T.sub[i-1]

## Оптимизация прерываний

Известно самое раннее время срабатывания, можно настроить аппаратный таймер на это время (а не на минимальное измеримое время)

Уменьшение количества прерываний:
* ускоряет систему
* экономит энергию

---
# Использование 2

Определение текущего реального времени

Пример: `gettimeofday(2)`

Узнать текущее время
 * загрузить из Real Time Clock (RTC)
 * получить по Network Time Protocol (NTP)

По каждому прерыванию от аппаратного таймера подсчитывать прошедшее время (точность = минимальному измеримому отрезку)

Для получения прошедшего времени между прерываниями обращаться к counter аппаратного таймера

---
# Прерывание

.def[Прерывание] - исключение процессора, посылаемое оборудованием для оповещения о наступлении события

```asciidrawing
          +-----+    irq
          | USR +--------------+
          +--+--+              |
             |                 |
     syscall |                 |
             v                 v
          +-----+           +-----+
          | SYS +- - - - - >| IRQ |
          +-----+    irq    +-----+
```

Аппаратура выполняет (как и в системном вызове):
* приостановление текущего потока управления, сохранение информации для возврата в него (на текущий стек/на выделеныей стек/на специальный набор регистров)
* смену режима работы процессора на режим IRQ:
	* прерывания выключаются
	* включается самый слабый режим защиты
* переход на функцию-обработчик

---
# Обработчик таймера 1

Пишем функцию-обработчик:
* узнать причину прерывания (тип, номер прерывания)
* (*) произвести необходимые действия для конкретного номера прерывания
 * Для таймера: обойти множество программных таймеров, декрементировать счётчики, вызвать обработчики истёкших программных таймеров
* сообщить оборудованию, что прерывание обработано (позволяет оборудованию генерировать новые прерывания)
* провести действия по восстановлению контекста для выхода из прерывания (в отличие от системного вызова, здесь контекст нельзя менять!)

Проблема:
 * обработчик прерывания выполняется в режиме IRQ, прерывания выключены
 * пункт (*) может быть очень долгим

Почему это плохо?

---
# Обработка в 2 этапа


1. .def[top half] - критическая обработка прерывания, прерывания выключены
	1. узнать номер прерывания
	2. провести минимально-необходимые действия по обработке прерывания, сохранить информацию o дальнейших действиях
	3. сообщить оборудованию “обработано”
	4. подготовить более строгий контекст (с включенными прерываниями) и перейти в него
2. .def[bottom half] - отложеная обработка, прерывания включены
	1. получить информацию о неоконченой обработке
	2. провести оставшиеся действия
	3. переключиться в изначальный прерванный контекст

```asciidrawing

### IRQ mode               --- non-IRQ mode

CPU ------######-----------------
               |     |       |
              irq  bottom   exit
               |     |       |
      OS ------##############---------

```

---
# Обработчик таймера 2

1. top half
	1. узнать номер прерывания, он соответствует таймеру
	2. настроить новый период прерывания
	3. включить прерывания
2. bottom half
	1. обойти множество программных таймеров, декрементировать счётчики
	2. вернуться из прерывания

---
# ?

Как синхронизировать ожидание времени и прерывание?

```
int cur_time;
int hw_timer_pending;

hw_timer_hnd() {
        cur_time += 1;
        hw_timer_pending = soft_timers_remain();
        if (hw_timer_pending) {
              hw_timer_request_irq(1/*timeout*/, &hw_timer_hnd);
        }
}

void sched_sleep(unsigned ms) {
        int endtime = cur_time + ms;
        assert(hw_timer_pending);
        while (cur_time <= endtime && hw_timer_pending) {
              pause();
        }

if (!hw_timer_pending) {
              // ...
        }
}
```

---
class: title, center, middle
name: preemt-scheduling

## Вытесняющее планирование

---
# Мотивация

С точки зрения кооперативного планирования, зависшие и интенсивные вычислительные задачи (с небольшим количеством ввода/вывода) одинаково плохи:
 * блокируют исполнение других задач
 * могут быть только завершены (по истечению отрезка времени)

Можно решать синтетическим разделением длинных задач на небольшие:
 * требует модификации программ
 * ручное разделение не оптимально (квалификация, недостаток знания о системе)

---
# Определения

.def[Вытесняющее планирование] - планирование, при котором выполнение процесса может быть приостановлено.

.def[Переключение контекста] - процесс смены текущего исполняемого процесса:
 * изменение данных планировщика (указатель на текущий процесс, ...)
 * изменение состояния процессора (значения регистров, режима исполнения, ...)

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

.def[Квант времени процесса] - максимальный отрезок времени непрерывного исполнения процесса.

.def[Пвсево-параллельное исполнение] - переключение процессов с достаточно большой скоростью, создающее впечатление параллельного исполнения.

---
# Переключение

* Добровольное переключение -- системный вызов переключает контекст в ожидании события
 * Принудительное переключение -- по внешнему событию

.def[Принудительное переключение] происходит из обработчика прерывания, например:
 * таймера - истек квант вермени
 * ввода/вывода - доступен ввод/вывод, который ожидает более приоритетный процесс.

Принудительное переключение:
 * асинхронное событие
 * является .def[отложенным] - производится после обработки прерывания, до выхода в пользовательский режим (bottom half).

Почему отложенный?

.def[Критическая секция по отношению к IRQ] - участок потока исполнения, во время которого не может начаться обработка прерывания.

---
# Реализация

```asciidrawing
  main      switch
  |         |
  +--+------+---+                +----
--+  |##########+----------------+    ...>
  +--+--+-------+                +----
     |  |       |                              +-+ Пользовательский
   irq  bottom  exit to                        | | режим
        half    userspace                      +-+
                             switch
                             |                 +-+
                +-----+------+---+             |#| Ядерный режим
----------------+     |##########+----...>     +-+
                +-----+--+-------+
                      |  |       |
                    irq  bottom  exit to
                         half    userspace
```

---
# Добровольное

```asciidrawing
     main
     |
     +--+-------------+     +----
-----+  |#############+-----+####...>
     +--+-------------+     +----
        |             |     |
os_sys_read  ctx_switch     ctx_switch

+-----+
----------------------+#####+----...>
                      +-----+
                      |     |
             ctx_switch     ctx_switch
```

* синхронное событие
 * является .def[реальным] - производится сразу

Почему добровольное переключение не сделать отложенным? (инициировать выход в userspace и "вернуться" в новый процесс).

---
# Ожидание события

Событие (2) может произойти после начала его ожидания (1) но до переключения контекста (3).

```asciidrawing
    (1) if (!ready) {
     |
     +-------------+
-----+#############|
     +-----+-------+
           |       |
      irq (2)     (3) ctx_switch
```

1. Выключение прерывания на длительный срок, с (1) до (3)
2. Определение протокола оповещения о событии:
 * (1) Проецесс выставляет бит WAIT до проверки на событие
 * (2) Прерывание стирает бит WAIT после (1), но до (3)
 * (3) ctx_switch выключает прерывания, проверяет бит WAIT:
      * 1 - событие ещё не произошло, выполняет переключение
      * 0 - событие произошло, выходим сразу же (или помечаем задачу как READY)

---
# Системный вызов и квант времени

Может ли событие (например, истечение кванта времени) во время исполнения системного вызова запустить принудительное переключение?

Частный случай вопроса: когда обрабатываются top и bottom части прерываний, если возникают во время системного вызова?

* невытесняемое (nonpreemtive) ядро: не запускать bottom
 * +: в каждый момент времени не больше одного процесса исполняются в режиме ядра (1 процессор), простая синхронизация
 * +: синхронное исполнение => более простой анализ времени исполнения и корректности
 * -: долгие системные вызовы увеличивают задержку обработки прерывания
* вытесняемое (preemtive) ядро: запускать bottom
 * всё наборот
* seL4: не запускать top, но вставить проверки на ожидание прерывания на длинных путях исполнения.

---
# Планируемость

G. Buttazzo. Hard Real-Time Computing Systems

.def[Планируемость] - для множества задач, существование такого порядка выполнения, что для задач выполняются заданые ограничения:
 * deadline
 * очерёдность задач
 * доступные ресуры

Планирование:
 * вытесняющее/невытесняющее
 * статических задач/динамических
 * оптимальное/приближенное
 * online/offline

.def[Aномалии планирования]: для некоторых политик при ⬆ количества CPU или ⬇ времени исполнения задач или ⬇ количества задач может приводить к ⬆ общего времени исполнения.
 * такова политика "выбрать самый приоритетный процесс для первого простаивающего CPU".

---
# Вытеснение

Вытесняемое/невытесняемое планирование имеют разные теоретические свойства.
 * при невытесняемом, увеличение скорости выполнения может приводить к увеличению опоздания (время завершения - deadline)

.def[Earliest Deadline First (EDF)]: выполненять задачи с наименьшим deadline'ом

EDF оптимален:
 * при невытесняющем планировании и всех задачах доступных для выполнения
 * задачи поступают в процессе, есть вытесняющее планирование
   * если план существует, он будет найден

При невытесняемом планировании и поступающих задачах: решается перебором
 * EDF по прежнему оптимален в классе решений, не позволяющих простоев

---
class: title, center, middle
name: virtual-memory

## Виртуальная память

---
# Виртуальная память

Иерархия памяти:
* регистры
* кеш оперативной памяти
* оперативная память
* накопительные устройства

.def[Виртуальная память] - принцип позволяющий использовать больше оперативной памяти, чем есть на машине.

.def[Процесс] - исполняемая программа.
 * программа и её состояние
 * экземпляр виртуальной машины

.def[Адресное пространство] (процесса) - множество адресов в памяти, к которым процесс может запросить доступ.

.def[Потоки] - процессы, обладающие общим адресным пространством.

---
# Модель памяти

.def[Адресное пространство] (процесса) - множество адресов в памяти, к которым процесс может запросить доступ.

Физическая модель памяти:

```asciidrawing
0x0                                                 0x10000000
+-----+-------------+-----+------------+-----+-----+
|     |     RAM     |     |     IO     |     | Sys |
+-----+-------------+-----+------------+-----+-----+
```
Логическая: адресное пространство

В адресном пространстве процесса находятся все данные приложения и его код.

Для защиты, память ядра и других процессов не должны быть доступны.

---
# Реализация

Размещать данные процессов в общей памяти

```asciidrawing
       Процесс 1     Процесс 2
    +--------------+---------------------+
RAM | .text, ...   | .text, ...          | ...
    +--------------+---------------------+
```

Что делать с абсолютными адресами?
1. Исправлять абсолютные адреса на загрузке
1. Не использовать абсолютные адреса

.def[Swapping] - при нехватке памяти, вытеснить память процесса на диск.

---
# .def[Сегментная модель памяти]

Адресное пространство - набор .def[сегментов] - участков переменной длины.
Память адресуется с помощью пары `сегмент:смещение`.

Аппаратная поддержка:
* например, регистры .def[базы] и .def[размера]
* некорректное обращение приводит к исключению

При нехватке памяти, вытеснить сегмент на диск.
Процесс может работать, если он не обращается к выгруженному сегменту.

---
# .def[Страничная модель]

.left[
```asciidrawing
         0x0     0xff..f
Процесс  +-------------+
      1  | .text, ...  |
         +-------------+

0x0     0xff..f
Процесс  +-------------+
      2  | .text, ...  |
         +-------------+
```
```asciidrawing
Логическое пространство
+---+---+---+---+---+
|   |   |   |   |   |
+-+-+---+-+-+-+-+---+
  |       |   |
  +---+---+   +---+
+---+-v-+---+---+-v-+
|   |   |   |   |   |
+---+---+---+---+---+
Физическое пространство
```
]

Реализация адресного пространства с помощью .def[страниц] - участков памяти фиксированной длины.
Обращение к логическому (.def[виртуальному]) адресу преобразуется в обращение к физическому адресу.
Достаточно уметь отображать адреса страниц.

.def[Paging] - при нехватке памяти, вытеснить страницу на диск.

Процесс может работать, если он не обращается к выгруженной странице.

---
# Программная реализация

"Вариант" реализации.

.left[
```asciidrawing
         N            P        0
 Virtual +------------+--------+
    addr |    idx     | offset |
         +------------+--------+

0   1   2   3   4
+---+---+---+---+---+
| 0 |   | 1 | 1 |   |
+-+-+---+-+-+-+-+---+
  |   +---+---+
+-v-+-v-+
|   |   |
+---+---+
  0   1

Physical +------------+--------+
    addr |    base    | offset |
         +------------+--------+
         N            P        0
```
]

Отображение задавать таблицей: для каждой виртуальной страницы - адрес физической.

На каждое обращение памяти генерировать исключение:
 * вычислить номер виртуальной страницы (`адрес обращения >> разер страницы`)
 * по таблице определить номер физической страницы
 * вычислить физический адрес (`адрес физ страницы | offset`)

---
# Аппаратный кеш

Генерировать и обрабатывать исключение на каждое обращение к памяти дорого.

Отображение aппаратно ускоряется с помощью модуля процессора Memory Management Unit (MMU).

Возможная реализация - кеш:
 * (аппаратура) на каждое обращение к памяти получить номер/адрес странциы
 * (аппаратура) проверить кеш, если отображение не закешировано, сгенерировать исключение
 * обработчик добавляет новое значение в кеш, перезапускает инструкцию

Устройство кеша (например):
 * список пар: виртуальный/физический адрес страниц и тип доступа
 * аппаратная проверка кеша: проверить каждый виртуальный адрес из списка, при совпадении использовать физический адрес
 * обращения в память - долгая операция, кеш располагается в процессоре
 * _изменение_ записи в кеше == сброс и заполнение кеша заново

---

.left[
```asciidrawing
P - размер страницы

N            P        0
 Virtual +------------+--------+
    addr |    idx     | offset |
         +------------+--------+

+----------+
  0|  record  |
   +----------+
  1|  record  |
   +----------+
  .|  record  |
  .+----------+
  .|  record  |
   +------+---+
idx| base | f |
   +------+---+
   |  record  |
   +----------+

Physical +------------+--------+
    addr |    base    | offset |
         +------------+--------+
         N            P        0
```
]

MMU может самостоятельно выполнять логику отображения по таблице (слева).

Теперь, ПО не контролирует процесс отображения, нужна дополнительная информация:

```asciidrawing
+---------+---+---+---+---+---+---+
| phyaddr | R | W | X | M | A | E |
+---------+---+---+---+---+---+---+
```
* R/W/X - разрешение на чтение/запись/исполнение
* M - был ли доступ на запись
* A - был ли доступ на чтение
* E - другие поля записи определены

---

Для 32 битной архитектуры:

```
4б [запись] * (4Гб [пространство] / 4Kб [страница]) = 4Мб [таблица]
```

.left[
```asciidrawing
         N             P        0
 Virtual +------+------+--------+
    addr | idx1 | idx2 | offset |
         +------+------+--------+
                           t2 base
    +-------------+  +---->+-------------+
    |    record   |  |     |    record   |
    +-------------+  |     +---------+---+
    |    record   |  | idx2|   base  | f |
    +-------------+  |     +---------+---+
    |    record   |  |     |    record   |
    +---------+---+  |     +-------------+
idx1| t2 base | F +--+
    +---------+---+
    |    record   |
    +-------------+

Physical +-------------+--------+
    addr |     base    | offset |
         +-------------+--------+
         N             P        0
```
]

Большая часть страниц не отображена. Можно уменьшить потребление памяти с помощью многоуровневой страницы.

Просмотр многоуровненвых таблиц плохо сказывается на производительности.
Для ускорения вводят .def[Translation Lookaside Buffer] (TLB) - кеш отображений.

TLB это кеш: требуется инвалидация при обновлении таблиц.

---
# Paging

При обращении по неотображенному участку виртуальной памяти происходит исключение.

Реализация paging:
1. В начальный момент времени все страницы находятся в памяти
2. При запросе дополнительной памяти, который не может быть удовлетворён, ядро:
 * ищет страницу-жертву, которая будет вытеснена на диск
 * ищет адрес на диске для сохранения данных страницы
 * по завершению вытеснения, помечает страницу неотображенной для MMU, сохраняет адрес на диске
3. В течение работы может произойти обращение к вытесненной странице,
 * происходит исключение (страница не отображена)
 * ядро удостоверяется, что запрос произведён к вытесненной странице
 * определяется новая странца-жертва, которая вытесняется
 * на место жертвы c диска загружается целевая странца
 * устанавливается отображение
 * ядро выходит из исключения с повтором инструкции

---
# Выбор жертвы

.left[
```asciidrawing cut
X
.     Процесс 1
.+---+---+---+---+---+
.|   |   |   |   |   |
.+-+-+---+---+-+-+---+
.  |       +---+
.+-v-+---+-v-+
.|   |   |   |
.+---+-^-+---+
.  +---+
X  |       |   |
.+-+-+---+-+-+-+-+---+
.|   |   |   |   |   |
.+---+---+---+---+---+
.     Процесс 2
```
]

Выбор страницы-жертвы существенно влияет на производительность.

Выбор зависит от:
 * порядка планирования процессов
 * последовательности обращения самих процессов

.def[Пробуксовка] - ситуация, когда система находится в постоянной выгрузке/загрузке страниц, выполняя небольшое количество инструкций программ (полезной работы).

.clear[
Известны хорошие, но непрактичные алгоритмы:
* Belady's MIN: вытеснять страницы, которые будут использоваться как можно позже
  * не знаем будущее
* Least Frequently Used (LFU): вытеснять страницы, которые использовались нечасто
  * подсчитывать частоту использования дорого
]

---
# Алгоритмы выбора

## First In First Out (FIFO)

 * поддерживать список страниц, упорядоченный по времени загрузки, от самой старой страницы
 * вытеснять первую (самую старую) страницу

Вытесняет потенциально используемые страницы.

## Второй шанс (Second chance)

 * список страниц как FIFO
 * если бит Access первой страницы установлен, перенести её в конец списка, перейти к следующей

Вырождается в предыдущий алгоритм, если A установлен у всех страниц.

## Часы (Clock)

 * Второй шанс, но над кольцом вместо списка
 * перенести в конец == перейти к следующему элементу в кольце

Техническая оптимизация Второго шанса.

---
# Алгоритмы выбора

## Least Recently Used (LRU)

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

## Not Recently Used (NRU)

 * кольцо или список
 * периодически сбрасывать флаг A
 * при необходимости вытеснения выбрать страницу со сброшенным A
 * модификация: учитывать M, вытеснить первую из упорядочения по классам (биты A/M): 0/0, 0/1, 1/0, 1/1

---
# Алгоритмы выбора

## Not Frequently Used (NFU)

 * поддерживать счётчик обращений (аппаратно/периодически сбрасывать A, запоминая значение)
 * .def[старение] счётчика - уменьшение значения со временем
   * `C = C >> 1 | (A << 31)`

## Уменьшение набора сканирования страниц

 * поддерживать два класса страниц
   * active: в памяти, есть отображения на неё
   * inactive: в памяти, нет отображения
 * вытеснять страницы из inactive
 * переносить страницы из active в inactive
   * по статистике использования (NRU, NFU, ...)
   * по целевой эвристической функции
 * ошибочное перенесение в inactive быстро исправляется (страница ещё в памяти)

---
# Алгоритмы выбора

## Рабочий набор

 * w(k,t) - набор из страниц, к которым процесс получил доступ последние k обращений к памяти за последние t времени. Можно рассматривать w(inf, const)
 * вытеснять не попадающие в рабочий набор
   * снова нужно считать возраст страницы, теперь в .def[виртуальном] времени, которое процесс занимает процессор.
 * загружать не по одной странице по исключению, а рабочий набор или его часть

## WSClock

 * рабочий набор + часы
 * страницы в кольцевом списке
 * если A, сбросить бит, перейти к следующей
 * если обращение было давно
   * не M -- жертва найдена
   * M -- начать асинхронно сбрасывать страницу и перейти к следующей
 * если страница не найдена за один полный проход
   * если были начаты сбрасывания, повторорить
   * если нет (все страницы в рабочем наборе), выбрать произвольную

---
# Отображенные файлы

.def[Отображенный файл] - область памяти, которую ОС синхронизирует с файлом: `mmap(2)`.
* Чтение из области приводит к чтению из файла
  * изначально ничего не отображено, вызывается обработчик исключения
  * новую страницу
  * инициирует чтение, блокирует процесс
  * когда оно завершается, отображает страницу в пространство процесса
  * разблокирует процесс
* Запись может приводить к записи в файл (shared) или только в копию в памяти (private)

<!--
```
extern void *mmap(void *addr, size_t len, int prot, int flags,
                int fildes, off_t off);

int fd = open(file, O_RDONLY);
char *m = mmap(NULL, 0x1000, PROT_READ, 0, fd, 0);
// operate on m
```
-->

Интересное свойство: ядро так же управляет страницами отображенных файлов
 * выгружать изменения на диск в произвольные моменты (например, переход active->inactive)
 * переиспользовать страницы для другого файла в этом или другом процессе, под память процеса
  * read-only отображения не нужно сбрасывать на диск
  * shared отображения пишутся в файл, private должы быть сохранены в swap

Политика вытеснения может учитывать природу страниц: память процесса или отображенный файл.

---
# Совместно используемая память

В один момент времени одна физическая страница может быть отображена в адресные пространства нескольких процессов.
 * для динамических библиотек - одна копия секции кода библиотеки отображется в разные процессы, каждый процесс обладает своей копией секции данных
   * любые отображения только для чтения
 * .def[общая память] (shmem) - механизм для межпроцессного взаимодействия (IPC)
 * ...

---
# Реализация стека

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

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

Другие области так же могут имеют специальные права доступа
* Код: X, может быть R, может быть W
* Данные: RW, может быть X

Системный вызов `mprotect(2)` позволяет задать права доступа.

---
# Implicit Null Exception

```
        // r0 - object address
        cmp r0, #0
        beq throw_exception
        ld r0, [r0]
        ...
throw_exception:
        ...
```
 ---
```
signal_handler() {
        if (load_instruction && known_to_generate_NPE) {
                throw_exception()
        }
}
        ...
        // r0 - object address
        ld r0, [r0]
```
---
# Safepoint (barrier)

```
bool should_barrier;

...
if (should_barrier) {
        barrier();
}
...

should_barrier = true;
```
 ---
```
volatile char *should_barrier = mmap(NULL, 0x1000, PROT_READ,
                MAP_ANONYMOUS, -1, 0);
signal_handler() {
        barrier();
}
...
*should_barrier;
...
mprotect(should_barrier, 0x1000, PROT_NONE);
```

---
class: title, center, middle
name: processes

## Процессы

---
# Системные вызовы

Системные вызовы для управления адресным пространством:

* brk()

* mmap(ANON)

```asciidrawing

mmap()         mmap()
+------+    +-----------+  +-----------+
| text |....| heap part |..| heap part |....
+------+    +-----------+  +-----------+
```

* mprotect()

* ...

---
# Жизнь процесса

Цикл жизни процесса:
1. Создание
2. Выполнение
3. Завершение

Создание процесса:
* Инициализация системы.

В Unix: ядро запускает первый процесс init -- процесс отвечающий за запуск других процессов
* Существующий процесс создает другой процесс.

В Unix: системный вызов fork

---
# fork

Системный вызов `fork(2)` создает полную копию вызывающего процесса, за исключением кода возврата системного вызова.

```
$ man 2 fork
```

Создаются логически независимая копия:
 * адресного пространства
 * текущего состояния (набор значений регистров)
 * ресурсы ОС

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

Неточный пример:

```
	...
	int res = fork(); // системный вызов
	if (res == 0) {
		// new process
	} else {
		// old process
	}
```
---
# fork

```
	...
	int res = fork(); // код возврата 0
	if (res == 0) {
		// new process, исполняем это
	} else {
		// old process
	}
```
 ---

```
	...
	int res = fork(); // код возврата 0
	if (res == 0) {
		// new process, исполняем это
	} else {
		// old process
	}
```

---
# Иерархия процессов

При fork оригинальный и новый процессы становится .def[родителем] и .def[ребенком].

Процессы в системе образуют дерево иерархии.

```asciidrawing
+--------+
| parent |
+--------+
    |
    +---->...
    |
    |
    +---->...
    |
    |     +-------+
    +---->| child |
          +-------+
```

---
# Идентификация процессов

Процессы идентифицируются числом типа `pid_t`

```
	pid_t parent = getpid(); // получить id текущего процесса
	pid_t child = fork();
	if (child == 0) {
		// child process; child в родителе == getpid()
	} else {
		// parent process
	}
```

---
# exec

Системный вызов `exec` -- заместить текущий процесс программой с диска, с инициализацией начального состояния

Используется вместе с `fork` для создания нового процесса, исполняющего другие програмы, а не только копии оригинального процесса.

example.c:

```
static int global = 314;
int main(int argc, char *argv[]) {
	printf("%d\n", global);
	return 0
}
```
 ---
shell.c:
```
	pid_t child = fork();
	if (child == 0) {
		execl("./example", NULL);
	}
```
---
# Copy-on-Write

При fork + exec, существенное время требуется на создание бесполензной полной копии
* vfork: создать новый процесс с тем же адресным пространством
  - любые изменения ребенком памяти будут видны родителю
  - ребёнок может только выполнить `exec` или `exit`
      * например, нельзя выходить из функции, где вызывается `vfork`
  - родитель заблокирован пока ребёнок исполняется в адресном пространстве
* Copy-on-Write: создать адресное пространство с отображнеием в те же физические страницы
  - но пометить отображнеие в обоих процессках как только для чтения
  - при записи, сделать копию страницы и сделать отдельное отображение с возможностью записи

---
```asciidrawing

+---+---+---+---+---+
 | A |   |   | B |   |
 +-+-+---+---+-+-+---+
   |           |
   +---+       |
 +---+-v-+---+-v-+---+
 |   | A |   | B |   |
 +---+---+---+---+---+

```

---
```asciidrawing

+---+---+---+---+---+   +---+---+---+---+---+
 | A |   |   | B |   |   | A |   |   | B |   |
 +-+-+---+---+-+-+---+   +-+-+---+---+-+-+---+
   |       +---|-----------+           |
   +---+---+   +-----------------------+
 +---+-v-+---+-v-+---+
 |   | A |   | B |   |
 +---+---+---+---+---+

```
* fork (CoW)

---
```asciidrawing
                                       w
 +---+---+---+---+---+   +---+---+---+---+---+
 | A |   |   | B |   |   | A |   |   | B |   |
 +-+-+---+---+-+-+---+   +-+-+---+---+-+-+---+
   |       +---|-----------+           |
   +---+---+   +-----------------------+
 +---+-v-+---+-v-+---+
 |   | A |   | B |   |
 +---+---+---+---+---+

```
* fork (CoW)
* write attempt

---
```asciidrawing cut
                                       w
 +---+---+---+---+---+   +---+---+---+---+---+
 | A |   |   | B |   |   | A |   |   | B |   |
 +-+-+---+---+-+-+---+   +-+-+---+---+-+-+---+
   |       +---|-----------+           |
   +---+---+   |   +-------------------+
 +---+-v-+---+-v-+-v-+
 |   | A |   | B | B |
 +---+---+---+---+---+
X              |   |
               +---+
               copy
```
* fork (CoW)
* write attempt
* copy

---
```asciidrawing
                                       w
 +---+---+---+---+---+   +---+---+---+---+---+
 | A |   |   | B |   |   | A |   |   | B'|   |
 +-+-+---+---+-+-+---+   +-+-+---+---+-+-+---+
   |       +---|-----------+           |
   +---+---+   |   +-------------------+
 +---+-v-+---+-v-+-v-+
 |   | A |   | B | B'|
 +---+---+---+---+---+

```
* fork (CoW)
* write attempt
* copy
* write done

---
# Завершение процесса

1. Выход (с кодом завершения):
```
	exit(success ? 0 : 1);
```

2. Получение сигнала:
 * неперехватываемого SIGKILL
 * перехватываемого сигнала без установленного обработчика и поведением по умолчанию "завершение"

Замечания:
* существуют перехватываемые сигналы с поведением по умолчанию "игнорировать"
* можно изменить поведение для большинства сигналов с помощью установки обработчика сигнала

---
# Сигналы

Процесс получает сигнал:
 * сгенерированный операционной системой как результат выполнения программы (примерно: внутреннее исключение процессора):
  * SIGSEGV -- ошибка изоляции процесса
  * SIGILL -- исполнение невалидной инструкции процессора
  * ...
 * посланный другим процессом (очень примерно: прерывание от устройства)
  * `kill(pid, sig)`

---
# Подбор процесса

* .def[Подбор] -- получение родительским процессом информации о завершении дочернего, в том числе, кода возврата.

Часть ресурсов дочернего процесса не освобождается после его выхода, а сохраняется до подбора:
 * идентификатор процесса
 * память под код возврата

---
# waitpid

Подбор реализуется системным вызовом `waitpid(2)`

```
	pid_t child = fork();
	if (child == 0) {
		execl("./example", NULL);
	}
	int cstat;
	const int waitflags = 0;
	if (-1 == waitpid(child, &cstat, waitflags)) {
		perror("waitpid");
	}
	int childcode = WIFEXITED(cstat) ? WEXITSTATUS(cstat) : -1;
```

Выход из `waitpid` родительского процесса в примере происходит только тогда, когда дочерний процесс завершается.

Может быть отключено флагом `WNOHANG`

---
# Реализация sh

```sh
$ sleep 10 ; sleep 2
```
(fork, exec, wait)

```sh
$ test # shell built-in
$ myfunc() { ... }
$ myfunc
```
(..., но зависит от реализации)

```sh
$ ( echo 1 ; echo 2)
```
(fork, ..., wait)

```sh
$ sleep 10 & sleep 2
```
(fork, exec, ...)

---
# Файловые дескрипторы

```sh
$ seq 1 100 > temp.txt
$ grep 2 < temp.txt

$ seq 1 100 | grep 2
```

Как реализованы перенаправления?

* .def[Файловый дескриптор] -- объект операционной системы поддерживающий файловый интерфейс (`read(2)`, `write(2)`,...).

Для защиты, объекты ОС находятся в адресном пространстве ядра, т.е. недоступны процессу напрямую.

С процессом ассоциирована таблица (массив) файловых дескрипторов, находящаяся так же в адресном пространстве ядра.

Процесс оперирует с файловыми дескрипторами с помощью системных вызовов и индексов дескрипторов в таблице (т.е. косвенно).

---
# "Всё есть файл" (1)

Многие сущности представлены или могут быть представлены в качестве файловых дескрипторов

---
# Создание элементов таблицы

```asciidrawing

+------+
   +-+->| file |
   | |  +------+
   | |
+-+-+-+-
+-+-+-+-       kernel-space
............................
+---------+      user-space
| process |
+---------+
```
```c
	int fd = open("test.txt", O_WRONLY);
	dup(fd, 1);
```
---
# Удаление элементов

```asciidrawing

---
# `> text.txt`

`fork` копирует таблицу ресурсов.

```sh
$ seq 1 100 > test.txt
```

```c
	...
	pid_t child = fork();
	if (child == 0) {
		close(1);
		int fd = open("text.txt", O_WRONLY);
		assert(fd == 1);
		execl("/usr/bin/seq", "1", "100", NULL);
	}
	if (-1 == wait(NULL)) {
		perror("wait");
	}
```

---
# pipe

```sh
$ seq 1 100 | grep 2
```

Системный вызов `pipe(2)` создает буфер (в ядре ОС) и 2 ассоцированных с ним дескриптора: для записи и для чтения.

```asciidrawing
+---------------+    +-------------+    +--------------+
| pipe write fd |--->| pipe buffer |--->| pipe read fd |
+---------------+    +-------------+    +--------------+
       ^                                       ^
       |                                       |
    +-+-+-+-                                  +-+-+-+-
    +-+-+-+-                                  +-+-+-+-
       1                                       0
............................................................
   +-----------+                             +-----------+
   | process 1 |                             | process 2 |
   +-----------+                             +-----------+

write(1, ...)                             read(0, ...)
```

---
# Замечания

Так же pipe позволяет реализовать подстановки
```sh
$ echo $(cat -)
```
(вывод `cat` вычитывает через pipe сам интерпретатор)

Для диагностических ошибок выделен файловый дескриптор 2 (STDERR_FILE). Например,
```sh
$ cat notexist | grep 1
cat: notexist: Нет такого файла или каталога
```

Когда в буфере нет данных, читающий процесс приостанавливается. Аналогично, когда буфер полностью заполняется, пприостанавливается пишущий процесс.

<!--
# Д/З

Перенести ваш шелл под Linux:

```
$ echo Hello, World
Hello, World
```
```
$ echo test1; echo test2
test1
test2
```

Добавить перенаправление pipe

```
$ seq 1 100 | grep 2 | grep 0
```

Можно считать, что и все программы лежат в `/usr/bin`

https://github.com/AntonKozlov/eduos/tree/next/shell
```
$ make -C shell test
```
```
$ (cd shell; make test)
```
-->

---
class: title, center, middle
name: mutual-exclusion

## Взаимное исключение

---
# Состязательная ситуация

.def[Состязательная ситуация] (состояние гонки, race condition) - одновременный доступ одному ресурсу, при котором конечный результат зависит от порядка исполнения.

* Танненбаум, Современные ОС, 2.4
* Herlihy, Shavit The Art of Multiprocessor Programming

Пример: реализация `pipe`

```asciidrawing

process1                 process2
   |                        ^
   |                        |
   +--------> pipe ---------+
       +----------------+
       | char buf[]     |
       +----------------+
       | char *writeend |
       +----------------+
       | char *readend  |
       +----------------+
```

---
# Взаимное исключение

.def[Взаимное исключение] - подход для устранения состязательных ситуаций: предоставить гарантирию монопольного досутпа к ресурсу в течении некоторого времени.

.def[Критическая секция] - участок программы, в котором гарантируюется монопольный доступ.

Свойства взаимного исключения:
* монопольный доступ
* deadlock-freedom - если 2 процесса хотят завладеть ресурсом, то по крайней мере 1 преуспеет
* starvation-freedom - если процесс хочет завладеть ресурсом, то когда-нибудь он преуспеет

```c
	lock();
	write_pipe();
	unlock();
	...
	lock();
	read_pipe();
	unlock();
```

---
# Выключение прерываний

```c
lock() {
	irq_disable();
}

unlock() {
	irq_enable();
}
```

* для коротких секций в ядре
* нельзя давать пользователю

```c
lock() {
	sched_disable();
}

unlock() {
	sched_enable();
}
```

---
# Алгоритмически

## lock 1

```c
lock(self) { // 0 or 1
	other = 1 - self
	flag[self] = true
	while (flag[other]);
}

unlock(self) {
	flag[self] = false
}
```
--

## lock 2

```c
process victim = NULL
lock(self) {
	victim = self
	while (victim == self) {}
}

unlock(self) {
}
```

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

```c
lock(self) {
	other = 1 - self
	flag[self] = true
	victim = self
	while (victim == self && flag[other])
}

unlock(self) {
	flag[self] = false
}
```

---
# Блокирующая переменная

```c
bool locked = false;
lock() {
	while (locked);
	locked = true;
}

unlock() {
	locked = false;
}
```

---
# Блокирующая переменная

```c
atomic test_and_set(ptr) {
	bool old = *ptr
	if (!*ptr) {
		*ptr = true;
	}
	return old;
}
```

```c
bool locked = 0;
lock() {
	while (test_and_set(&locked));
}

unlock() {
	locked = 0;
}
```

---
# Блокирующая переменная

1. ожидание активно
2. проблема инверсии приоритета:
   * низкоприоритетный процесс исполненяется в критической секции
   * просыпается высокоприоритеный процесс и пытается зайти в критическую секцию

```c
low() {
        // locked = true
        ...
}

high() {
        while (locked) {
                ...
        }
}
```

---
# Семафор

.def[Семафор] - примитив синхронизации операционной системы; позволяет создавать критическую секцию, в которой может находится не больше определённого количества процессов.

Атомарные операции:
* down - вход в критическую секцию. проверяет счетчик возможных процессов в секции:
  * счётчик процессов больше 0:
      * счетчик декрементируется
      * процесс входит в критическую секцию
  * счётчик равен 0:
      * процесс засыпает, ожидая входа в секцию
* up - выход из критической секции
  * счётчик инкрементируется
  * посылается сигнал пробуждения ожидающему входа процессу (или нескольким)

.def[Mutex] - семафор, позволяющий 1 процесс в критической секции

---

```c
down(semaphore *s) {
    sched_lock();
    while (true) {
        if (0 < cnt) {
            --cnt;
            goto out;
        } else {
            s->q->add(self);
            sched_unlock_wait_relock();
        }
    }
out:
    sched_unlock()
}

```

```c
up(semaphore *s) {
    sched_lock();
    ++cnt;
    other = s->q->pop();
    if (other) {
        wake(other);
    }
    sched_unlock();
}

```
`sched_lock()/unlock()` -- низкоуровневые механизмы создания критических секций, обеспечивают атомарность операций (отосительно друг друга).

---
# Инверсия приоритета

```
LOW:                    HIGH:                   MED:
//work                  //sleep                 //sleep
down(m)
//work
//ready                 //wake
                        //work
//work                  down(m) //block
//ready                                         //wake,work
```
---
# Инверсия приоритета

```
LOW:                    HIGH:                   MED:
//work                  //sleep                 //sleep
down(m)
//work
//ready                 //wake
                        //work
//work,HIGH             down(m) //block
                                                //wake
//up(m),LOW,ready
                        //work
```

.def[Наследование приоритета] - процесс получает максимальный приоритет среди других процессов, ожидающих занятый ресурс.

Sha, Rajkumar, Lehoczky: "Priority Inheritance Protocols: An Approach to Real-Time Synchronization"

---
# Монитор

```c
	down(&sem)
	write_pipe();
	up(&sem);
	...
	down(&sem);
	read_pipe();
	up(&sem);
```
Программист:
 * должен вызвать `up`
 * количество вызовов `up` должно быть `<=` вызовов `down`

.def[Монитор] - примитив синхронизации над объектом, в каждый момент времени монитором объекта владеет не более одного метода.

```
class Pipe {
	public synchronized void write() { ...  }
	public synchronized void read() { ...  }
}
```

---
# Барьер

.def[Барьер] - примитив для синхронизации фаз исполнения.

```c
struct barrier {
    struct mutext m;
    int limit, now;
}
void init(struct barrier *b, int limit) {
    down(&b->m);
    b->limit = limit;
    b->now = 0;
    up(&b->m);
}
void wait(struct barrier *b) {
    down(&b->m);
    if (b->now + 1 < b->limit) {
        ++b->now;
        wait(&b->m);
    } else {
        notifyAll(&b->m);
    }
}
```
Например: [glibc](https://sourceware.org/git/gitweb.cgi?p=glibc.git;a=blob;f=nptl/pthread_barrier_wait.c;h=54bc727e39538ac711c4db6c9901b1ec05222a82;hb=HEAD#l25)

---
class: title, center, middle
name: processes-interaction

## Задачи взаимодействия процессов

---
# Литература

* Танненбаум, Современные ОС, 2.5
* Танненбаум, Современные ОС, 6
* Дейтел, Введение в операционные системы, 6
* P.J. Courtois, F. Heymans, and D.L. Parnas. Concurrent Control with "Readers" and "Writers"
* V.Popov, O.Mazonka. Faster Fair Solution for the Reader-Writer Problem

---
# Задача обедающих философов

.left[
```asciidrawing

f      +-----+      f
   +-+.....|  p  |.....+-+
   +-+     |     |     +-+
    .      +-----+      .
    .                   .
 +-----+             +-----+
 |  p  |             |  p  |
 |     |             |     |
 +-----+             +-----+
    .                   .
    .      +-----+      .
   +-+.....|  p  |.....+-+
   +-+     |     |     +-+
    f      +-----+      f
```
]

* Несколько паралельных процессов _p_, каждый в одном из двух состояний
* `state 1`: занимается локальной работой
* `state 2`: использует 2 ресурса _f_
* Процессы пересекаются по необходимым ресурсам

Пример перехода между состояниями:
```
// state 1
acquire left
acquire right
// state 2
```

Без синхронизации захват двух ресурсов приводит к deadlock'у.

Как организовать синхронизацию между процессами?

---
# C глобальной синхронизацией

```
// state 1
acquire m // глобальный mutex для системы
acquire left
acquire right
// state 2
release right
release left
release m
// state 1
```
В один момент времени не более одного процесса получает доступ к ресурсам

---
# C дополнительной синхронизацией

```
// state 1
acquire m
sl = try_acquire left
sr = try_acquire right
while not (sl and sr):
        if sr: release right
        if sl: release left
        atomic:
                release m
                wait
                acquire m
        sl = try_acquire left
        sr = try_acquire right
release m

// state 2
acquire m
release right
release left
wake process_left
wake process_right
release m
```
---
# Задача читателя/писателя

Есть область памяти, позволяющая чтение и запись.

Несколько процессов имеют к ней доступ на запись и чтение: при этом
 * одновременно могут читать сколько угодно процессов
 * писать — только один

---
# Приоритет читателям

```
int readcount = 0;
mutex m = UNLOCKED, w = UNLOCKED;

READER                   WRITER

acquire m
readcount += 1
if readcount == 1:
        acquire w
release m
                         acquire w
... reading ...          ... writing ...
                         release w
acquire m
readcount -= 1
if readcount == 0:
        release w
release m
```

---
# Честное распределение

```
int readcount = 0;
mutex in = UNLOCKED, m = UNLOCKED, w = UNLOCKED;

READER                                  WRITER

acquire in                              acquire in
        acquire m
                readcount += 1
                if readcount == 1
                        acquire w
        release m
release in
                                        acquire w
... reading ...                         ... writing ...
                                        release w
                                        release in
acquire m
readcount -= 1
if readcount == 0:
        release w
release m
```

---
# Приоритет писателям

```
int readcount = 0, writecount = 0;
mutex m1 = UNLOCKED, m2 = UNLOCKED, m3 = UNLOCKED, w = UNLOCKED;

READER                                  WRITER

acquire m3                              acquire m2
        acquire in                      writecount += 1
                acquire m1              if writecount == 1:
                readcount += 1                  acquire in
                if readcount == 1:      release m2
                        acquire w
                release m1
        release in
release m3

acquire w
... reading ...                         ... writing ...
                                        release w

acquire m1                              acquire m2
readcount -= 1                          writecount -= 1
if readcount == 0:                      if writecount == 0:
        release w                               release in
release m1                              release m2

```
???
mutex 3 is necessary because of our absolute insistence on priority
for writers. Without mutex 3 we have the possibility
that a writer and one or more readers will be simul-
taneously waiting for a V(in) to be done by a reader.
In that event we could not guarantee priority to the
writer, mutex 3 guarantees a reader exclusive access to
the block of code from "P(in)" to "V(in)" inclusive. As
a result there will be at most one process ever waiting
at in, and the result of a V is clear.

---
# Ресурсы и взаимоблокировки

.def[Взаимоблокировка] (тупик, deadlock) - ожидание системой события, которое никогда не наступит.

Пример:
```
process1() {            process2() {
        acquire m1              acquire m2
        acquire m2              acquire m1
        ...                     ...
        release m2              release m1
        release m1              release m2
}                       }
```

Ресурсы:
* выгружаемые - можно "отобрать" у программы:
  * процессор, память
* невыгружаемые - если отобрать, приведёт к сбою:
  * критические секции, устройства

Во взаимоблокировках участвуют невыгружаемые ресурсы.

---
# Условия возникновения

Коффман, Элфик и Шошани (1971): взаимоблокировка возникает, тогда и только когда выполняются все условия:
* Взаимное исключение при работе с ресурсами
* Удержание и запрос дополнительных ресурсов
* Ресурсы невыгружаемы
* Циклическое ожидание

---
# Предотвращение взаимоблокировок

.def[Предотвращение] - гарантировать невозможность взаимоблокировки построением системы так, чтобы не выполнялось какое-либо из необходимых условий.

Взаимное исключение:
* Снизить количество процессов, занимающих ресурс
* Минимизировать время удержания ресурса

Удержание и запрос:
* Запрашивать все ресурсы в начале работы
  * нужно знать необходимое количество ресурсов
  * неоптимальное использование ресуров

---
# Предотвращение взаимоблокировок (2)

Невыгружаемость:
* Процесс должен освобождать захваченные ресурсы если новый ресус не может быть захвачен
  * неэффективно: приходится отдавать ресурс, затем захватывать снова
  * голодание: нет гарантий успешного захвата на новой попытке

Циклическое ожидание:
* Позволять захватывать только 1 ресурс
  * потеря производительности
* Упорядочить захват ресурсов
  * необходим общий порядок для всех, может не существовать

---
# Уклонение

.def[Уклонение] - при возможности взаимоблокировки, не допускать её алгоритмически, например, с помощью политик удовлетворения запросов.

Алгоритм банкира (Дейкстра, 1965)

Условия:
 * имеется фиксированное количество ресурсов одного типа
 * фиксированное количество процессов
 * известны максимальное количество ресурсов, используемых каждым процессом
 * ресурсы освобождаются за конечное время

---
# Алгоритм банкира

.left[
Надёжное:

| Текущее | Максимальное
---|:-:|:-:
Процесс1 | 1 | 4
Процесс2 | 4 | 6
Процесс3 | 5 | 8
Резерв   | 2 |

Ненадёжное:

| Текущее | Максимальное
---|:-:|:-:
Процесс1 | 8 | 10
Процесс2 | 2 | 5
Процесс3 | 1 | 3
Резерв   | 1 |
]

.def[Состояние]:
 * надёжное: существует порядок планирования, позволяющий всем процессам завершиться в течение конечного времени
 * ненадёжное: в противном случае

Из ненадёжного состояния в случае неблагоприятной последовательности событий можно попасть в взаимоблокировку (но не обязательно)

Алгоритм:
* Удовлетворять запросы, переводящие систему из надёжного состояния в надёжное.
* Приостанавливать запросы, переводящие систему в ненадёжное состояние.

---
# Обнаружение и восстановление

.right.fitimg[![](detection_graph.png)]

.def[Обнаружение взаимоблокировки]: поддерживать или строить специальный граф процессов и ресурсов. При невозможности выполнить запрос, необходимо проверить граф на циклы.

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

.def[Восстановление]:
* завершение процесса
* приостановление/возобновление процесса
* восстановление контрольной точки

---
class: title, center, middle
name: block-devs-fs

## Блочные устройства и файловые системы

---
# Литература

* Таненбаум, Современные ОС, Глава 4
* https://www.kernel.org/doc/Documentation/filesystems/vfs.txt
* http://www.tldp.org/LDP/khg/HyperNews/get/fs/vfstour.html
* http://www.win.tue.nl/~aeb/linux/vfs/trail-3.html
* http://lwn.net/Articles/13325/
* http://habrahabr.ru/company/spbau/blog/218833/
* http://www.virtualblueness.net/Ext2fs-overview/Ext2fs-overview-0.1.html

---
# Иерархия памяти

Иерархия памяти:
* регистры
* кеш оперативной памяти
* оперативная память
* **накопительные устройства**

Накопительные устройства:
* Магнитная лента
* Жесткий диск
* Твердотельный (flash) диск
* Оптический диск

Свойства:
* Используется для долговременного хранения данных
* Самый медленный интерфейс
* Самый большой объем

---
# .f75[Взаимодействие]

.def[Блочные устройства] - энергонезависимые устройства хранения данных, оперирующие .def[блоками] - последовательностями байт фиксированного размера.

Варианты взаимодействия (для чтения):
 * Опрос (polling):
  1. Установить адрес блока
  1. Инициировать чтение (во внутренний буфер устройства)
  1. Ожидать, пока данные не будут прочитаны
  1. Скопировать прочитанные данные в оперативную память
 * Опрос с прерыванием:
  1. Установить адрес блока
  1. Установить обработчик прерывания, инициировать чтение
  1. ...
  1. В обработчике прерывания проверить готовность данных, скопировать в оперативную память
 * DMA:
  1. Установить адрес блока
  1. Установить базовый адрес в памяти
  1. Установить обработчик прерывания, инициировать чтение
  1. ...

---
# Файл

.def[Файл] - логический информационный блок, моделирующий ленточное устройство. Содержит данные и метаинформацию (аттрибуты):
* размер
* дата создания/изменения/доступа
* тип - `обычный`
* владелец
 * идентификатор пользователя
 * ... группы пользователей
* права:
 * блок из трёх бит: чтение, запись, исполнение
 * три блока бит для: владельца, группы владельцев, всех остальных

На устройстве файл представляется набором блоков.

---
# Взаимодействие с файлами

Файл представляет .def[последовательный побайтовый] интерфейс в возможностью .def[перемотки]:
* `ssize_t read(int fildes, void *buf, size_t nbyte)`
* `ssize_t write(int fildes, const void *buf, size_t nbyte)`
* `off_t lseek(int fildes, off_t offset, int whence)`
* `int close(int fildes)`

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

---
# Дерево файлов

Файлы идентифицируются по имени:
* `int open(const char *path, int oflag, ...)`
* получить аттрибуты: ` int stat(const char *pathname, struct stat *statbuf)`, ...
* записать аттрибуты: `chmod`, `chown`, ...

.def[Дерево файлов] - дерево, задающее иерархическую структуру для файлов, служит для
 * группировки
 * разрешения конфликтов в именовании
 * оптимизации поиска

Структура дерева:
 * файл с данными - лист
 * .def[каталог] - узел, содержащий перечисление дочерних элементов виде списка пар "имя - id дочернего элемента"

C точки зрения хранения, директория является файлом специального типа (т.е. так же является набором блоков)

---
# Дерево файлов (2)

Разные ОС используют разные разделители для элементов пути. Разделительный символ не может использоваться в имени файла.

Для удобства использования, для процесса определяется .def[рабочий (текущий) каталог].
Все имена файлов по-умолчанию интерпретируются как элементы поддерева текущего каталога.

.def[Абсолютный] (от корня дерева) путь указывается специальным образом:
 * `/usr/bin` (Unix)
 * `C:\windows` (Windows)

Каталог содержит специальные записи
 * "." - ссылка на сам каталог
 * ".." - ссылка на родительский каталог

---
# Взаимодействие с деревом

Просмотр каталога:
* `DIR *opendir(const char *name)`
* `struct dirent *readdir(DIR *dirp)`
* `int closedir(DIR *dirp)`

Изменение дерева:
* `int mkdir(const char *path, mode_t mode)`
* `int rmdir(const char *path)`
* `int unlink(const char *path)`
* `int rename(const char *oldpath, const char *newpath)`
* `int link(const char *path1, const char *path2)`

---
# Ссылки

link позволяет создать дополнительную ссылку от произвольного каталога к файлу. Таким образом, "дерево" файлов - на самом деле граф.

ОС реализует подсчёт ссылок на файлы: после unlink файл, если на него больше нет ссылок, удаляется; иначе, счетчик ссылок декрементируется.

Ссылки:
* .def[Жесткие] - записи в каталоге, управляются link/unlink
* .def[Мягкие] - специальные файлы, в которых содержится имя целевого файла

---
# Файловая система

.def[Файловая система] - структура организации каталогов и файлов на блочном устройстве

Одно устройство может быть разделено на логические области - .def[разделы], на каждом - собственная ФС.

Структура файловой системы:
* Суперблок
 * размер ФС
 * размер логического блока
* Информация о свободных блоках
* Корневой каталог
* Файлы и каталоги

---
# Непрерывное размещение

```asciidrawing
                     1         1
 0     3       7     0         5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
------ ------- ----------------- ...
Файл 1 Файл 2  Свободная область
```

---
# Связный список блоков

```asciidrawing
            +--------+    +--------+    +--------+    +--------+
            |    ----|--->|    ----|--->|    ----|--->|        |
            +--------+    +--------+    +--------+    +--------+
            |        |    |        |    |        |    |        |
 Файловый   | Блок 0 |    | Блок 1 |    | Блок 2 |    | Блок 3 |
   блок        ...           ...           ...           ...
            |        |    |        |    |        |    |        |
            +--------+    +--------+    +--------+    +--------+

Физический       4             7             2             8
   блок
```

---
# Связный список в таблице

```asciidrawing
Физический
      блок
           +---------+
         0 |         |
           +---------+
         1 |         |
           +---------+
         2 |    8    |
           +---------+
         3 |         |
           +---------+
         4 |    7    |  <- Файл A
           +---------+
         5 |         |
           +---------+
         6 |         |
           +---------+
         7 |    2    |
           +---------+
         8 |   -1    |
           +---------+
```

---
# inode (i-узлы)

```asciidrawing
+---------------+
|      ...      |
|               |
+---------------+
| Адрес блока 0 |
+---------------+
| Адрес блока 1 |
+---------------+
| Адрес блока 2 |
+---------------+
| Адрес блока 3 |
+---------------+     +---------------+
|  Адрес блока  |---->| Адрес блока 4 |
|   указателей  |     +---------------+
+---------------+     | Адрес блока 5 |
                      +---------------+
                      | Адрес блока 6 |
                      +---------------+
                      | Адрес блока 7 |
                      +---------------+
                      |      ...      |
                      +---------------+
                      |  Адрес блока  |
                      |   указателей  |
                      +---------------+
```
---
# Журнальная структура

---
# Восстановление после сбоев

Сбой для файловой системы:
 * пропало питание системы
 * пропало устройство
 * устройство некорректно обработало запрос
 * ...

Желательно, чтобы файловая система сохраняла данные и оставалась непротиворечивой:
* по блокам:
 * неучтенный свободный блок
 * блок принадлежит двум файлам
* по файлам:
 * счётчик ссылок не равен реальному количеству ссылок
...

---
# Журналирование

Традиционные ФС позаимствовали у ФС с журнальной структурой механизм предотвращения повреждения данных при сбоях - журналирование.

.def[Журналирование] - поддержание журнала о выполнямых изменениях:
 * перед началом изменения добавить запись в журнал
 * после изменения удалить запись

Восстановление после сбоя:
* проверить текущие записи в журнале, если есть:
 * определить, какие из действий были совершены; откатить их
 * повторить изменения из журнала: требуется, чтобы они были .def[идемпотентными] - позволяли повторное исполнение без нарушения корректности

Журнал может задавать .def[транзакции] - группу действий, совершаемых атомарно. Т.е. после после сбоя состояние системы должно соответствовать состоянию до изменений.

---
# Производительность

* размер блока ФС:
 * маленькие файлы занимают больше места
 * больший объем на устройстве поддерживается
 * меньше уровней в inode
* учёт свободных блоков:
 * список свободных
 * битовая карта
* кэширование блоков устройства в памяти
 * write-back
 * write-through
* опережающее чтение: читать в буфер больше данных, чем сейчас требуется
* планирование ввода/вывода: переупордочивать множество запросов к одному устройству исходя из знаний о его внутреннем устройстве (для жесткого диска - снижать количество перемещений головки диска)
* дефрагментация: переместить блоки файлов в последовательный порядок

---
# ВФС

.left[
```asciidrawing
         Запрос
            |
            v
+-----------------------+
|          ВФС          |
+-----------------------+
   |        |        |
   v        v        v
+-----+  +-----+  +-----+
| ФС1 |  | ФС2 |  | ФС3 |
+-----+  +-----+  +-----+
   ^        ^        ^
   |        |        |
   v        v        v
+-----+  +-----+  +-----+
|  У1 |  |  У3 |  |  У1 |
+-----+  +-----+  +-----+
```
]

.def[Виртуальная файловая система] - интерфейс для пользователя (процесса) для взаимодействия с различными ФС.

ВФС представляет одну файловую систему общим корнем. Другие файловые системы могут быть .def[смонтированы] в произвольное место существующей иерархии: дерево файлов смонтированной системы становится доступным в каталоге монтирования.

Так же содержит реализацию типовых частей для ФС:
 * разбиение строк-путей на символы
 * кэширование структуры каталогов

---
# Драйвера ФС

ВФС позволяет легко создавать новые драйвера:
 * ФС для блочных устройств: различные организации на блочном устройстве
 * сетевых ФС: удаленая машина предоставляет доступ к своей ФС
 * псевдо ФС: иерархия каталогов содержится полностью в оперативной памяти или генерируется на лету
   * /dev
   * tmpfs
   * procfs

Драйвер должен определять функции, позволяющие:
 * опознать ФС
 * смонтировать ФС
 * читать/модифицировать/удалять файлы, каталоги

Развитие идеи использования файловой системы произошло в ОС Plan9:
 * _все_ ресурсы представлены как файлы
 * возможность экспортировать/импортировать поддеревья файлов

---
# FUSE

Filesystem in Userspace

.fitimg[![](FUSE_structure.svg)]

---
class: title, center, middle
name: multiprocess-systems

## Многопроцессорные системы
---
# Мультипроцессоры

Типы многопроцессорных систем:
* мультипроцессоры
* мультикомпьютеры

.def[Мультипроцессор] - несколько процессоров имеют доступ к общей оперативной памяти.

Примеры: многопроцессорные, многоядерные машины.

Доступ к памяти:
* UMA (Uniform Memory Access) - время доступа не зависит от процессора или области памяти
* NUMA (Nonniform Memory Access) - в противном случае

UMA с шинной архитектурой:

```asciidrawing
+-----+  +-----+  +-----+
| CPU |  | CPU |  | Mem |
+--+--+  +--+--+  +--+--+
   |        |        |
+--+--------+--------+--+
+-----------------------+
```

---
# UMA

UMA с координатным коммутатором:

```asciidrawing

+-----+  +-----+  +-----+
         | Mem |  | Mem |  | Mem |
         +--+--+  +--+--+  +--+--+
            |        |        |
+-----+     |        |        |
| CPU +-----o--------+--------+--
+-----+     |        |        |
            |        |        |
+-----+     |        |        |
| CPU +-----+--------+--------o--
+-----+     |        |        |
            |        |        |
+-----+     |        |        |
| CPU +-----+--------o--------+--
+-----+     |        |        |

```
---
# UMA

.def[Omega network]: Lawrie, D. H. (1975). Access and alignment of data in an array processor

.f75img[![](Omega_Network.jpg)]

.def[Perfect shuffle]: `abcde` -> `bcdea`

---
# NUMA

```asciidrawing
                          Directory
+-----+  +-----+  +-----+ +--+
| CPU |  | CPU |  | CPU | +--+
+--+--+  +--+--+  +--+--+ +--+
   +--...   +--...   +----+--+ +-----+
   +--...   +--...   +---------+ Mem |
+--+--------+--------+--+      +-----+
+-----------------------+
```

Мы будем считать .def[многопроцессорные] машины и машины с .def[многоядерными] процессорами NUMA машинами
* ядра и процессоры могут обладать индивидуальными кешами

---
# ОС для мультипроцессоров

* Собственная ОС
* Ассиметричные мультипроцессоры
* Симметричные мультипроцессоры

---
# ОС для мультипроцессоров

Собственная ОС для каждого процессора:
* каждой ОС (экземпляру) отводится отдельная область памяти.

Достоинства:
* простота реализации
* ОС работают независимо, повышается надёжность, безопасность

Недостатки:
* процессы не мигрируют: неравномерная загрузка
* дублирование программных кешей
* статическое распределение памяти

---
# ОС для мультипроцессоров

AMP (Assymetric Multiprocessor):
* один управляющий исполняющий ядро ОС
* другие процессоры исполняют только пользовательский код
* исключения (в т.ч. системные вызовы) обрабатываются на управляющем.

Достоинства:
* Распределение ресурсов
* Возможно использовать процессоры разных архитектур

Недостатки:
* Управляющий процессор - узкое место
* Усложнение ОС: одна версия для управляющего процессора, другая для рабочих процессоров

---
# ОС для мультипроцессоров

SMP (Symmetric Multiprocessor): процессоры равноправны
 * каждый исполняет экземпляр одной ОС,
 * каждый может управлять всеми ресурсами: память, внешние устройства...
 * важна синхронизация между ними

---
# Планирование мультипроцессоров

Организация очереди:
* единая очередь
* по очереди на процессор
 * периодически балансировать задачи
 * job stealing

Одна из задач планирования: стараться не перемещать процессы на другой процессор (unix: get/setaffinity)

The Linux Scheduler: a Decade of Wasted Cores (http://www.i3s.unice.fr/~jplozi/wastedcores/)
---
# Реентерабельность

.def[Реентерабельность] - свойство частей программ, позволяющее выполнять одну и ту же последовательность инструкций нескольким параллельно.

Нереентерабельные части должны быть защищены.

`irq_lock`/`unlock` в мультипроцессорной среде недостаточно для обеспечения атомарности последовательности инструкций.

Нужен специальный примитив, обеспечивающий атомарность в мультипроцессорной среде.

---
# spinlock

.def[spinlock] - примитив для реализации критических секций для мультипроцессоров.
Реализуется на основе цикла -- отсюда и название.

Примерная реализация:

```
spin_lock(spin_t *spin) {
        while (true == test_and_set(spin));
}

spin_unlock(spin_t *spin) {
        *spin = false;
}
```

Реализация не корректна: не учитваются кэши.

Наивный подход требует постоянного блокирование шины, что может быть дорого (~100 тактов).

Исследования сосредоточены на создании lock-free и wait-free алгоритмов.

---
# Мультикомпьютеры

Системы, с собственным процессором и оперативной памятью, возможно, без накопительных устройств.

Например, мультикомпьютер из машин сопоставимых с ПК, но соединенных высокопроизводительной сетью.

Способы взаимодействия узлов:

* Посылка сообщений:
  * send/receive

* Удалённый вызов
  1. Вызов обычной функции,
  2. которая отправляет сообщение
  3. По приёму сообщения,
  4. вызывается требуемая функций

* Обмен страницами: создание видимости общей памяти
  * каждой страницей владеет один узел
  * при обращении узла к странице, находящейся на другом узле, она перемещается
  * важно обеспечивать минимальное количество перемещений страниц
  * неизменяемые страницы можно .def[реплицировать] - содержать копию на нескольких узлах

---
class: title, center, middle
name: caches-in-multiproc

## Кеши и мультипроцессирование

---
# Кеш

* U. Drepper. What Every Programmer Should Know About Memory
* P. McKenney. Memory Barriers: a Hardware View for Software Hackers
 * https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

.left[
```asciidrawing cut
X
 +-----------+
 |    Ядро   |
 +-----+-----+
 | L1i | L1d |
 +-----+-----+
 |    L2     |
 +-----------+ +-------+
 |    L3     | |  Mem  |
 +-----------+ +-------+
X
 +---------------------+
 +---------------------+
```
]

Операции с памятью (DRAM) имеют существенные задержки.
Проистекают из её физического устройства.

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

Кеш памяти используется для
* сохранения ранее полученых результатов
* группировки и предвыборки

Предполагается локальность доступа к данным и инструкциям.

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

---
# Полноассоциативный кеш

```asciidrawing
       +-----------------------------+--------------+
Адрес: |             tag             |    offset    |
       +-------------+---------------+--------------+
              +------+------+
              |      |      |
 Tag          |      |      |                        Data
+-----+     +-v-+    |      |                       +-----+
|     +---->| C +----+------+------+----------------+     |
+-----+     +---+  +-v-+    |      |                +-----+
|     +----------->| C +----+------+----------------+     |
+-----+            +---+  +-v-+    |                +-----+
|     +------------------>| C +----+----------------+     |
+-----+                   +---+    |                +-----+
                                   v
```
---
# С прямым отображением

```asciidrawing
       +--------------+--------------+--------------+
Адрес: |     tag      |     set      |    offset    |
       +------+-------+------+-------+--------------+
              +---+          |
            +-----+----------+----------------+
 Tag        v     |                           v      Data
+-----+   +---+   +---+                     +---+   +-----+
|     +-->| M |       v                     | M |<--+     |
+-----+   |   |     +---+                   |   |   +-----+
|     +-->| U +---->| C +---------+---------+ U |<--+     |
+-----+   |   |     +---+         |         |   |   +-----+
|     +-->| X |                   |         | X |<--+     |
+-----+   +---+                   |         +---+   +-----+
                                  v
```
---
# Устройство

```asciidrawing
       +--------------+--------------+--------------+
Адрес: |     tag      |     set      |    offset    |
       +--------------+--------------+--------------+
```

* 2.sup[l(offset)] - длина линейки (line)
* 2.sup[l(set)] - количество наборов
* ассоциативность - количество различных tag'ов в одном наборе

Примеры:
* полноассоциативный: l(set) == 0
* с прямым отображением: 1-ассоциативный кеш

---
# Запись

Как поддерживать консистентность кеша и памяти при записи?

* write-through: запись ведётся одновременно в кеш и в память
  * легко вытеснять
  * большой траффик на шине
* write-back: запись при вытеснении
  * ... или простое шины
  * лучшая производительность
  * как быть с несколькими ядрами/процессорами?

---
# Кеши и мультипроцессоры

```
/* volatile */ int a = 0;
/* volatile */ int b = 0;

void foo(void) {
        a = 1;
        b = 1;
}

void bar(void) {
        while (b == 0) continue;
        assert(a == 1);
}
```
CPU 0 исполняет `foo`, 1 -- `bar`.

---
# Кеши и мультипроцессоры

```
void foo(void) {
        a = 1;
        __asm__ __volatile__ (:::"memory");
        b = 1;
}

void bar(void) {
        while (b == 0) continue;
        assert(a == 1);
}
```

---
# Согласование кешей

.def[Протокол согласования кешей] - средство синхронизации между кешами для достижения консистентного представления о содержимом памяти.

MESI:
* Modified
* Exclusive
* Shared
* Invalid

Сообщения:
* Read
* Read Response
* Invalidate
* Invalidate Ack
* Read Invalidate
* Writeback

---
# Буфер записи

.left[
```asciidrawing
     CPU 0           CPU 1
       |               |
       |               |
       |  invalidate   |
       +------+        |
     s |      |        |
     t |      +------->|
     a |               |
     l |      +--------+
     l |      |        |
       |<-----+        |
       |  ack          |
       |               |
       v               v
```
]

CPU 0 производит запись, при этом линейка адреса находится у CPU 1

CPU 0 приходится ожидать, пока CPU 1 инвалидирует линейку и пришлет ответ.

Оптимизация: не ждать после invalidate, поместить запись в буфер. Когда ack придет, применить запись к кешу.

Чтение должно опрашивать не только кеш, но и буфер записи.

---
# Проблема

.left[
```
void foo(void) {
        a = 1;
        b = 1;
}

void bar(void) {
        while (b == 0);
        assert(a == 1);
}
```
]

```
foo, b - CPU0, bar, a - CPU1

0: a -> store buffer, read invalidate a >
                1: read b >
0: store b
0: read resp b==1 >
                1: read resp b==1 <
                1: while, assert
                1: read invalidata a <
```
---
# membarrier

.left[
```
void foo(void) {
        a = 1;
        smp_mb();
        b = 1;
}

void bar(void) {
        while (b == 0);
        assert(a == 1);
}
```
]

```
foo, b - CPU0, bar, a - CPU1

0: a -> store buffer, read invalidate a >
                1: read b >
0: b -> store buffer
0: read resp b==0 >
                1: read resp b==0 <
                ...
```
---
# Буфер инвалидации

Записи из store buffer применяются по invalidation ack.

Если кэш загружен, например, invalidation сообщениями, то ack будет выслан не сразу.

Поэтому, invalidation ack высылается сразу, а invalidation запоминается в буфер.

.left[
```
void foo(void) {
        a = 1;
        smp_mb();
        b = 1;
}

void bar(void) {
        while (b == 0);
        assert(a == 1);
}
```
]

```
b - M(cpu0), a - S
0: a -> store buf, inv a>
        1: read b >
        1: inv a <, a -> inv q, inv ack a >
0: store b, read b <, read resp b==1 >
        1: read resp b==1 <, read a
        1: inv a apply
```
---
# read membarrier

.left[
```
void foo(void) {
        a = 1;
        smp_wmb(); // было smp_mb
        b = 1;
}

void bar(void) {
        while (b == 0);
        smp_rmb();
        assert(a == 1);
}
```
]

Применять весь invalidation buffer перед чтением семантически связанных областей.

При исполнении rmb, все элементы буфера инвалидации помечаются.

Все последующие чтения задерживаются, пока все помеченные элементы буфера не будут применены к кешу.

---
# Переупорядочивания

.fitimg[![](ordering.png)]

---
# Read-Copy-Update

RCU - примитив синхронизации Linux для SMP систем. Предназначен для преобладающего чтения.

Концептуально, обновление:
1. Удаление (removal) ссылок на данные. Читатели видят либо старые, либо новые данные.
2. Ожидание, пока все читатели не выйдут из критических секций RCU чтения.
3. Утилизация (reclamation) старого ресура.

API:

`rcu_read_lock`/`unlock` - критическая секция (к записи).
Здесь запрещено блокирование.
Могут быть вложенными или пересекаться.

`rcu_dereference` - получить указатель из RCU-защищённого указателя

`synchronize_rcu` - блокироваться, пока все предшествующие читатели в критической секции (не все читатели вообще).

`rcu_assign_pointer` - присвоить новое значение указателю, защищенному RCU

---
# Пример

```
DEFINE_SPINLOCK(foo_mutex);
struct foo *gbl_foo;
int foo_get_a(void) {
        int retval;
        rcu_read_lock();
        retval = rcu_dereference(gbl_foo)->a;
        rcu_read_unlock();
        return retval;
}

void foo_update_a(int new_a) {
        struct foo *new_fp, *old_fp;
        new_fp = kmalloc(sizeof(*new_fp), GFP_KERNEL);
        spin_lock(&foo_mutex);
        old_fp = gbl_foo;
        *new_fp = *old_fp;
        new_fp->a = new_a;
        rcu_assign_pointer(gbl_foo, new_fp);
        spin_unlock(&foo_mutex);
        synchronize_rcu();
        kfree(old_fp);
}
```

---
# Реализация

```
#define rcu_assign_pointer(p, v) ({ \
        smp_wmb(); \
        (p) = (v); \
})

#define rcu_dereference(p) ({ \
        typeof(p) _________p1 = p; \
        smp_read_barrier_depends(); \
        (_________p1); \
})
```

Простая реализация 1:
```
static DEFINE_RWLOCK(rcu_gp_mutex);
void rcu_read_lock(void) {
        read_lock(&rcu_gp_mutex);
}
void rcu_read_unlock(void) {
        read_unlock(&rcu_gp_mutex);
}
void synchronize_rcu(void) {
        write_lock(&rcu_gp_mutex);
        write_unlock(&rcu_gp_mutex);
}
```

---
# Реализация

Простая реализация 2: для преимущественного чтения
```
void rcu_read_lock(void) { }
void rcu_read_unlock(void) { }
void synchronize_rcu(void) {
        int cpu;
        for_each_possible_cpu(cpu)
                run_on(cpu);
}

```
---
# Аллокаторы и кеши

Размещение памяти под объекты влият на загрузку шины между процессором и памятью.

SLAB:

```asciidrawing
0x0     0x20    0x40
+-------+-------+-------+
| obj 1 | obj 2 | obj 3 | (cache-block 0)
+-------+-------+-------+

0x0     0x20    0x40
+-------+-------+-------+
| obj 4 | obj 5 | obj 6 | (cache-block 1)
+-------+-------+-------+
```

Решение - раскраска кэша.

```asciidrawing

0x4     0x24    0x44
+-+-------+-------+-------+
|.| obj 4 | obj 5 | obj 6 | (cache-block 1)
+-+-------+-------+-------+
```

---
class: title, center, middle
name: network-programming

## Сетевое программирование

---
Литература:
* Таненбаум, Современные ОС, 8.4
* Таненбаум, Компьютерные сети

1950: телефонная сеть
![](chan_vs_packet.png)

---

* 1969: ARPANET
![](arpanet.png)

* 1976: TCP/IP как протокол передачи, не зависящий от сети (ARPANET, спутниковая связь, ...). Позже: Berkeley сокеты

* 1984: NSFNET с выходом в ARPANET

* Internet

---

.def[Коммутация] - способ взаимодействия между узлами:
* .def[Канальная] - для узлов резервируется линия связи - .def[канал] (телефонная сеть)
* .def[Пакетная] - узел передает множество пакетов информации (компьютерные сети)

Тип передачи:
* Направленная - один источник, один приемник
* Широковещательная - один источник, множество приемников

Размеры сетей:
* Персональные (Personal Area Network)
* Локальные (Local Area Network)
* Муниципальные (Metropolitan Area Network)
* Глобальные (Wide Area Network)

```asciidrawing
+-+ +-+                              +-+ +-+
+++ +++                              +++ +++
 |   |   +-+           +-+      +-+   |   |
 +---+---+M+-+---------+M|   +--+M+---+---+
         +-+ |         +++   |  +-+
             | +-+      |    |       +-+ +-+
+-+ +-+      +-+M+------+----+       +++ +++
+++ +++      | +-+      |       +-+   |   |
 |   |   +-+ |          +-------+M+---+---+
 +---+---+M+-+----------+       +-+
         +-+
```

---

![](arpanet.png)

```asciidrawing
+-------------------+                  +-------------------+
| Протокол уровня 3 +- - - - - - - - ->| Протокол уровня 3 |
+-------------------+                  +-------------------+
          v                                      ^
+-------------------+                  +-------------------+
| Протокол уровня 2 |- - - - - - - - ->| Протокол уровня 2 |
+-------------------+                  +-------------------+
          v                                      ^
+-------------------+                  +-------------------+
| Протокол уровня 1 +----------------->| Протокол уровня 1 |
+-------------------+                  +-------------------+
```
---
# Свойства протоколов

```asciidrawing
+-----+     +-----+                    +-----+
|Хост1| ... |ХостN|  - - - - - - - - ->|ХостM| ...
+-----+     +-----+                    +-----+
               v                          ^
+-------------------+                  +-------------------+
|  Маршрутизатор 1  |----------------->|  Маршрутизатор 2  |
+-------------------+                  +-------------------+
```

* Адресация
* Логические каналы, перенос данных между уровнями и (де)мультиплексирование
* Контроль ошибок

---
# Стек OSI

<ol reversed>
<li>Прикладной: приложения: http, ftp</li>
<li>Представления: преобразование представление данных</li>
<li>Сеансовый: поддержание сеансов связи</li>
<li>Транспортный: надёжная передача данных: TCP, UDP, ...</li>
<li>Сетевой: определение пути передачи: IP, ...</li>
<li>Канальный: определение границ кадров и контроль доступа: Ethernet, PPP, ...</li>
<li>Физический: передача битов</li>
</ol>

---
# Стек TCP/IP

<ol reversed>
<li>Прикладной: приложения</li>
<li>Транспортный: надёжная передача данных. Только TCP, UDP</li>
<li>Интернет: передача от хоста к хосту</li>
<li>Канальный: доставка IP пакетов от хоста в сеть</li>
</ol>

---
# Канальный уровень

Передача:
* данные делятся на кадры
* каждый кадр дополнятся контрольной суммой

Приём:
* из потока битов формируются кадры
* для каждого проверяется контрольная сумма

Хосты работают независимо, но обладают единым каналом передачи данных. Если 2 кадра пересекаются во времени, оба искажаются - .def[коллизия].

Для решения используется .def[контроль доступа к среде] - алгоритм определения возможности передачи.
Зависит от модели времени: дискретное/непрерывное; наличия контроля несущей: есть/нет.

Пример: Ethernet
* Двоичный экспоненциальный откат
* Время передачи минимального сообщения > 2*времени прохождения кадра (время распространения сигнала)

---
# Сетевой уровень

```asciidrawing
 +-+           +-+      +-+
-+M+-+---------+M|   +--+M+-
 +-+ |         +++   |  +-+
     | +-+      |    |
     +-+M+------+----+
     | +-+      |       +-+
 +-+ |          +-------+M+-
-+M+-+----------+       +-+
 +-+
```

* Единая адресация
* Независимость от топологии сети
* Пакетная/канальная коммутация

Интернет протоколы:
* Передача данных: IP
 * фрагментация
* Управляющий: ICMP
* Разрешение адресов: ARP

---
# Транспортный уровень

Типы
* Без соединения, без подтверждения: UDP.
* Без соединения, с подтверждением
* С соединением и подтверждением: TCP

UDP используется, когда нужно послать/принять набор пакетов
  * приложение готово мириться (обрабатывать) повторы, перестановку и потери пакетов

TCP используется, когда нужно переслать набор данных
  * требуется, чтобы данные дошли без искажений

.def[Порт] - идентификатор сетевого ресурса на узле.
* Для мультиплексирования, каждый сокет должен соответствовать порту протокола транспортного уровня.
* Но на один серверный порт может приходиться множество подключений.
Полный идентификатор канала на узле:

`локальный(адрес:порт) + удалённый(адрес:порт)`

---
# TCP

.left[
```asciidrawing
Host1                           Host2
+-+                               +-+
| |                               | |
| |          SYN(SEQ = x)         | |
| +------------------------------>| |
| |                               | |
| |   SYN(SEQ = y, ACK = x + 1)   | |
| |<------------------------------+ |
| |                               | |
| |  (SEQ = x + 1, ACK = y + 1)   | |
| +------------------------------>| |
| |                               | |

```
Пример: установление соединения
]

Свойства:
* обработка ошибок
* в правильном порядке
* без повторов
* управление потоком

В каждом сообщении:
* номер сегмента
* размер буфера

На каждое принятое сообщение - сообщение об успешном приёме и, возможно, данные (полнодуплексный протокол).
Сообщение перепосылается, если нет подтверждения в течение некоторого времени.

---
# Berkeley сокеты

Сокет - _канальный_ интерфейс работы с сетевым стеком

Сокет может быть
* .def[пакетным]: запись - отправка пакета; чтение - получение пакета c учётом границ
* .def[потоковым] (stream): запись и чтение игнорируют границы пакетов
 * протокол ответственен за разрешение проблем ненадёжной передачи

Общая инициализация:
* `int socket(int domain, int type, int protocol);` - создать сокет
* `int bind(int socket, sockaddr *address, socklen_t address_len);` - установить локальный адрес сокета
* (для клиента) `int connect(int socket, sockaddr *address, socklen_t address_len);` - подключиться к серверу

Обычная работа:
* `read` или `ssize_t recvmsg(int socket, msghdr *message, int flags);` - получить сообщение
* `write` или `ssize_t sendmsg(int socket, msghdr *message, int flags);` - послать сообщение

---

Инициализация для сервера:
* `int listen(int socket, int backlog);` - начать принимать подключения
* `int accept(int socket, sockaddr *restrict address, socklen_t *restrict address_len);` -
принять ожидающее подключение. Возвращает _ещё один_ сокет, соответсвующий новому соединению.
Изначальный сокет продолжает принимать подключения.

Деинициализация:
* `close` - закрыть сокет, в зависимости от типа, возможно, послать все отложенные исходящие сообщения

Ссылки:
1. Стивенс, "UNIX. Разработка сетевых приложений"
1. http://berb.github.io/diploma-thesis/original/042_serverarch.html

---
# HTTP

Протокол HTTP реализуется на TCP. Cхема протокола:

```
<method> <target> HTTP/1.1\r\n
<option>*\r\n
\r\n
<data>
```
Производительный http сервер должен быть способен обрабатывать множество существующих подключений и приём новых паралелльно.

Варианты реализации:
* Многопроцессная - новый экземпляр сервера на каждое соединение (fork)
* Многопоточная - отдельный поток сервера на каждое соединение
* Событийная:
 * Reactor - синхронно диспетчеризует запросы обработчикам
 * Proactor - асинхронный reactor

---
class: title, center, middle
name: distributed-systems

## Распределенные системы

---
# Литература

* Таненбаум. Распределённые системы
* Attiya, Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics
* Coulouris, Dollimore, Kindberg, Blair. Distributed Systems: Concepts and Design
* Lynch. Distributed Algorithms

---
# Распределённые системы

.def[Распределённая система] - набор вычислительных устройств, взаимодейстующих друг с другом.

Мультикомпютер - вычислитель, построенный из специальных узлов, соединенных высокопроизводительной сетью.

Распределенная система - множество устройств, соединенных обычной сетью

Фундаментальные проблемы:
 * Асинхронность
 * Ограниченное локальное знание
 * Отказы

Технические проблемы:
 * Гетерогенные ПО и АО

???
Таненбаум:

Мультикомпютер:
 * общая ФС
 * узел не имеет/имеет мало переферии

Распределенная система:
 * собственные ФС
 * полноценный компьютер

---
# Cильносвязанная

.def[Cильносвязанная система] (.def[Распределенная ОС]) - набор служб представляет распределенную систему как единую вычислительную.

.left[
```asciidrawing cut
X..........X..........X.........
.+--------+ +--------+ +--------+
.|+-------+-+--------+-+-------+|
.||         Приложения         ||
.|+-------+-+--------+-+-------+|
X|        | |        | |        |
.|+-------+-+--------+-+-------+|
.|| Службы  распрeделе нной ОС ||
.|+-------+-+--------+-+-------+|
X|        | |        | |        |
.|+------+| |+------+| |+------+|
.|| Ядро || || Ядро || || Ядро ||
.|+------+| |+------+| |+------+|
.+----+---+ +----+---+ +----+---+
.     |          |          |
.-----+----------+----------+----
```
]

Примеры:
 * Plan 9
 * Распределенные ФС, NFS

---
# Слабосвязанная

.def[Слабосвязанная система] - разные ОС, объединённые набором сервисов (.def[middleware])

.left[
```asciidrawing cut
X...........X...........X.........
.+---------+.+---------+.+---------+
.|+--------+-+---------+-+--------+|
.||         . Приложения          ||
.|+--------+-+---------+-+--------+|
X|         |.|         |.|         |
.|+--------+-+---------+-+--------+|
.||Службы пр.омежуточног.о уровня ||
.|+--------+-+---------+-+--------+|
X|         |.|         |.|         |
.|+-------+|.|+-------+|.|+-------+|
.||Службы ||.||Службы ||.||Службы ||
.||  ОС   ||.||  ОС   ||.||  ОС   ||
.|+-------+|.|+-------+|.|+-------+|
X|         |.|         |.|         |
.|+-------+|.|+-------+|.|+-------+|
.|| Ядро  ||.|| Ядро  ||.|| Ядро  ||
.|+-------+|.|+-------+|.|+-------+|
.+----+----+.+----+----+.+----+----+
.     |     .     |     .     |
.-----+-----------+-----------+-----

```
]

Примеры:
 * WWW

---
# Асинхронность

.def[Асинхронные системы]
 * сообщения доставляются независимо
 * нет верхней границы времени доставки

```asciidrawing cut
X
.Узел 1
.
X     |   |   |          |          |
.-----+---+---+----------+----------+-----
X     |   |   |          |          |
X       |      |     |        |      |
.-------+------+-----+--------+------+----
X       |      |     |        |      |
.Узел 2
```

.def[Синхронные системы] - определяется .def[раунды обмена сообщениями]
 * обмен сообщениями только в течении раунда
 * доставляются все сообщения
 * вычисления опираются на данные прошедшего раунда

```asciidrawing cut
X
.Узел 1
.----++--------++--------++-------++------
X    ||        ||        ||       ||
.----++--------++--------++-------++------
 Узел 2
```
На практик реализуется редко, но является хорошей моделью для разработки алгоритмов.

---

Построение остовного дерева с известным корнем
```
code for processor p[i], 0 < i < n — 1.

parent = 0, children = {}, and other = {}.

upon receiving no message:
        if p[i] = p[r] and parent = 0 then // root has not yet sent ("M")
             send ("M") to all neighbors
             parent := p[i]

upon receiving ("M") from neighbor p[j]:
        if parent = 0 then // p[i] has not received ("M") before
                parent := p[j]
                send ("parent") to p[j]
                send ("M") to all neighbors except p[j]
        else send ("already") to p[j]

upon receiving ("parent") from neighbor p[j]:
        add p[j] to children
        if children and other contains all neighbors except parent then
                terminate

upon receiving ("already") from neighbor p[j]:
        add p[j] to other
        if children and other contains all neighbors except parent then
                terminate
```
Дерево будет BFS, но только в синхронной сети.

---

Построение остновного дерева без выделенного корня, DFS

```
parent = NULL, leader = —1, children = {}, unexplored = all neighbors of p;
upon receiving no message:
        if parent = NULL then // wake up spontaneously
                leader := id; parent := pt; explore()

upon receiving ("leader",new-id) from p[j]:
        if leader < new-id then // switch to new tree
                leader := new-id; parent := p[j]; children := 0
                unexplored := all neighbors of p[i] except p[j]
                explore()
        else if leader = new-id then
                send ("already",leader) to p[j] // already in same tree
        // otherwise, leader > new-id and the DFS for new-id is stalled

upon receiving ("already",new-id) from p[j]:
        if new-id = leader then explore()

upon receiving ("parent",new-id) from p[j]:
        if new-id = leader then //otherwise ignore message
                add p[j] to children; explore()

procedure explore():
        if unexplored != {} then
                p[k] := a processor in unexplored
                remove p[k] from unexplored
                send ("leader",leader) to p[k]
        else
                if parent != p[i] then send ("parent",leader) to parent
                else terminate as root of spanning tree
```

---
# Лидер

Алгоритм для построения остовного дерева без выделенного корня для каждого узла пытается построить остовное дерево с корнем в этом узле.
Затем все узлы выбирают одно дерево в качестве ответа.

Этот алгоритм является .def[nonuniform] - зависит от числа узлов в системе.

Алгоритм является частным решением задачи определения .def[лидера] - выделенного узла среди изначально равноправных узлов.
---
# Лидер в кольце

```asciidrawing
    .................
    .               .
    .   +------+    .
    ..->| node +->...
        +------+
```

```
leader = —1
upon receiving no message:
        if leader = -1 then
                leader := id
                send (leader,id)

upon receiving ("leader",new-id) from p[j]:
        if leader < new-id then
                leader := new-id;
                send (leader,new-id)
        else if leader = new-id
                send (terminate)
                terminate
```
Этот алгоритм является uniform.

---
# Взаимное исключение

* Централизованный алгоритм
* Децентрализованный:
  * если получатель в крит. секции, сообщение помещается в буфер
  * если получатель вне крит. секции, высылается разрешение
  * если получатель в процессе входа в крит. секцию, входит тот, у кого время начала входа минимально

---
# Синхронизация времени

NTP: протокол синхронизации времени
 * перевод времени вперёд/назад: замедление и ускорение
 * корректировка ответного сообщения: (время приёма - время отправки)/2

Логическое время:
 * a < b, если происходят в одном процессе
 * отправка сообщения < приёма сообщения

Алгоритм Лампорта:
 * узел увеличивает своё время при каждом событии, в т. ч. передаче сообщения
 * к кажому сообщению прилагается отметка времени при посылке
 * при приеме сообщения узел устанавливает время больше, чем отметка в сообщении

---
# Алгоритм Лампорта
```asciidrawing

+--+         +--+         +--+        +--+         +--+         +--+
| 0|         | 0|         | 0|        | 0|         | 0|         | 0|
+--+         +--+         +--+        +--+         +--+         +--+
| 4+----+    | 6|         | 8|        | 4+----+    | 6|         | 8|
+--+    |    +--+         +--+        +--+    |    +--+         +--+
| 8|    +--->|12|         |16|        | 8|    +--->|12|         |16|
+--+         +--+         +--+        +--+         +--+         +--+
|12|         |18+----+    |24|        |12|         |18+----+    |24|
+--+         +--+    |    +--+        +--+         +--+    |    +--+
|16|         |24|    +--->|32|        |16|         |24|    +--->|32|
+--+         +--+         +--+        +--+         +--+         +--+
|20|         |30|         |40|        |20|         |30|         |40|
+--+         +--+         +--+        +--+         +--+         +--+
|24|         |36|    +----+48|        |24|         |36|    +----+48|
+--+         +--+    |    +--+        +--+         +--+    |    +--+
|28|         |42|<---+    |56|        |28|         |49|<---+    |56|
+--+         +--+         +--+        +--+         +--+         +--+
|32|    +----+48|         |64|        |32|    +----+55|         |64|
+--+    |    +--+         +--+        +--+    |    +--+         +--+
|36|<---+    |54|         |72|        |56|<---+    |61|         |72|
+--+         +--+         +--+        +--+         +--+         +--+
|40|         |60|         |80|        |59|         |67|         |80|
+--+         +--+         +--+        +--+         +--+         +--+
```

---

Векторные часы.
Часы Лампорта "стирают" информацию о независимости событий

```asciidrawing
        1    2
        1    1
        0    0
--------o----o---------------------------
       /      \
   0  /   0    \                  2
   1 /    2     \                 3
   0/     0      \                3
---o------o-------\---------------o------
                   \             /
            0       \  2     2  /
            0        \ 1     1 /
            1         \2     3/
------------o----------o-----o-----------
```

Решение - векторные часы:
 * время представляется вектором длины N (количество узлов в системе)
 * каждый узел поддерживает копию вектора времени
 * при внутренних событиях собственный компонент времени увеличивается
 * при отправке прикрепляется целый вектор
 * при приеме локальная копия вектора обновляется покомпонентным максимумом

F. Mattern. Virtual Time and Global States of Distributed Systems

---
# Отказы

Типы:
* .def[Авария] (crash) - узел выходит из строя. Часть сообщений доставляется.
* .def[Византийский отказ] - узел работает некорректно: могут исказиться ввод, локальное состояние, вывод

В такой модели узлы должны действовать согласовано.
Формально, достигать .def[консенсуса] - общего решения со свойствами:
* Конечность (Termination): каждый несбойный узел имеет своё решение
* Согласованность (Agreement): решения всех несбойный узлов совпадают
* Обоснованность (Validity): если все узлы предлагают одно значение, несбойные узлы должны согласиться на значение.

---
# Консенсус при авариях

Асинхронные системы: не существует алгоритмов консенсуса (в полностью асинхронных системах).

Синхронные системы: n процессов, f подвержен отаказам.

```
V = {x} // V contains pi input

round k, 1 <= k <= f + 1:
        send {v from V : pi has not already sent v} to all processors
        receive Sj from pj, 0 <= j <= n - 1, j != i
        V := V + { Sj : 0 <= j <= n - 1}
        if k = f + 1 then y := min(V) // decide
```
Любой алгоритм консенсуса для n (n > f + 2) процессов требует не менее f + 1 раундов, т.е. алгоритм оптимален.

---
# Консенсус при византийских отказах

Не существует алгоритма консенсуса при n <= 3f

Существует алгоритм с f + 1 раундами, при 3f + 1 <= n

---
# Отказоустойчивость

.def[Отказоустойчивость] - способность системы продолжать выполнять свою функцию при наличие отказов

Реализуется маскированием ошибок с помощью избыточности
 * пространственной (код Хемминга,...)
 * временной (TCP, ...)
 * физической (резервные системы, ...)

.def[Транзакция] - группа операций, происходящих атомарно. Свойства:
* Atomicity
* Consistency
* Isolation
* Durability

Интерфейс транзакций:
```
BEGIN
        modify
        modify
        COMMIT/ABORT
END
```
---
# Реализация

Возможноые реализации транзакций на одном узле

.def[Закрытое рабочее пространство].
Транзакции выполняются в отдельном пространстве.
Данные копируются COW.
При успешном применении данные записываются в основное пространство.
При неудаче закрытое пространство удаляется.

.def[Журнал с упреждающей записью].
Каждое изменение предваряется записью в журнал, затем изменение применяется.
Если транзакция успешна, то записи в журнале помечаются как применённые (журнал очищается)
В противном случае, изменения, описанные в журнале, отменяются начиная с самых новых в обратном порядке до последних применённых.

---
# .fsmall[В распределённой системе]

* .def[Вложенная транзакция] - состоит из независимых транзакций в дочерних независимых между собой системах
* .def[Распределённая транзакция] - состоит из дочерних транзакций к различным физическим частям единой распределённой системы.

Физические части могут иметь пересечение - .def[репликацию] данных для увеличения производительности, повышения надёжности

.def[Распределённое подтверждение] - реализация распределенной транзакции

2 Phase Commit:
1. Координатор рассылает всем VOTE_REQUEST
2. Участники отвечают VOTE_ABORT либо VOTE_COMMIT
3. Если все ответы VOTE_COMMIT, координатор выслыает всем GLOBAL_COMMIT; иначе - GLOBAL_ABORT
4. Участники получают GLOBAL_COMMIT, тогда транзакция применяется локально; GLOBAL_ABORT - отменяется

Участник(и) и координатор могут выйти из строя в любой момент.
 * timeout для определения вышедшего из строя узла
 * общение между узлами на время недоступности координатора

---
# Восстановление

.def[Восстановление] - переход в корректное состояние после ошибки

Типы восстановления:
 * обратное
 * прямое

Контрольные точки:
 * независимые
 * координированные

Протоколирование сообщений может использоваться для снижения накладных расходов на создание контрольных точек

---
class: title, center, middle
name: security

## Безопасность

---
# Литература

* Таненбаум. Современные операционные системы
* Таненбаум. Распределённые системы
* Schneier. Applied Cryptography

---
# Безопасность

Задачи:
* .def[Конфиденциальность] - ограничение получения информации
* .def[Целостность] - контроль изменения информации
* .def[Доступность] - беспрепятственный доступ

Составные части решения:
* Правила доступа (политики)
* Механизмы:
  - .def[идентификация] -
  - .def[авторизация] - проверка возможности выполнения действия
  - .def[аутентификация] - проверка неподдельности
* Реализация механизмов:
  - криптография
* Организационные мероприятия:
  - аудит

---
# Политика

* Модель Белла-Ла Падула (безопасность)

```asciidrawing cut
X
.+--------------+R      W+--------------+
.| Subject HIGH |<------>| Object HIGH  |
.+--------------+        +--------------+
.         ^                     ^
.       +-+---------------------+
X       | |
.       | +---------------------+
.+------+-------+R      W+------+-------+
.| Subject LOW  |<------>| Object LOW   |
.+--------------+        +--------------+
```
* Модель Биба (целостность)

```asciidrawing cut
X
.+--------------+R      W+--------------+
.| Subject HIGH |<------>| Object HIGH  |
.+--------+-----+        +------+-------+
.       +-+---------------------+
X       | |
.       | +---------------------+
.       v R                     v W
.+--------------+R      W+--------------+
.| Subject LOW  |<------>| Object LOW   |
.+--------------+        +--------------+
```

---
# Авторизация

* .def[Избирательная] (благоразумная).
Для объектов определено понятие владельца(/группы).
Субъекты могут передавать права доступа к объектам.
Типы задания:
  - матрица
  - списки контроля доступа (ACL)

* .def[Мандатная] (обязательная).
Объектам и субъектам присваиваются .def[метки] - классификаторы “секретности” информации.
Управление правами доступа осуществляется централизованно администратором.

* .def[Ролевая].
Субъекты имеют множество ролей.
Для каждого объекта определено множество ролей и типов доступа.
Субъекты, объекты и роли управляются централизовано (внутри организации).

* .def[На основе возможностей].
.def[Возможность] (capability) - ссылка на объект с определёнными набором прав.
Две разные возможности могут указывать на один объект с разными правами.
Возможности передаются между программами, составляя иерархии возможностей.

---
# Авторизация в UNIX

Избирательная:
 * процесс с uid=0 (root) может всё, в том числе сменить uid
 * uid!=0 не может сменить uid на произвольный
 * программа может иметь set-user-id (suid) бит: uid меняется при запуске

Capabilities:
 * каждая программа определяет новый набор
 * определены правила изменения активного набора процесса при execve
 * для процесса определен набор возможностей
   * активные
   * наследуемые
   * максимальные
   * ...

---
# Криптография

Задачи криптографии:
* конфиденциальность
* аутентификация
* целостность
* отсутствие отказов (nonrepudiation)

Например, источник хочет переслать сообщение приёмнику так, чтобы сообщение мог прочитать только приёмник.

.def[Шифрование] - процесс изменения сообщения, скрывающий его содержимое.
Дешифрование - обратный процесс.

.def[Стеганография] - передать сообщение, скрыв факт передачи:
* Невидимые чернила
* Сокрытия в графических изображениях
* Подделка статистических свойств

???
Статистические свойства:
Peter Wayner’s mimic functions obfuscate messages. These functions modify a message so that its
statistical profile resembles that of something else: the classifieds section of The New York Times, a
play by Shakespeare, or a newsgroup on the Internet [1584,1585]. This type of steganography won’t
fool a person, but it might fool some big computers scanning the Internet for interesting messages.

---
# Алгортимы

.def[Криптографический алгоритм] - математическая функция для шифрования/дешифрования.
* защищённые алгоритмы - безопасность основана на сокрытии алгоритма
* открытые алгоритмы - безопасность основана на сокрытии параметре алгоритма - .def[ключе]

Атаки:
* с шифрованными сообщениями
* с известным сообщением
* с выбранным сообщением
  * адаптивная с выбранным сообщением
* с выбранным шифрованным сообщением
* бандитская

---
# Шифры-подстановки

Каждый символ заменяется на другой
* Простая подстановка
* Несколько шифрованных символов на нешифрованный символ
* Группы символов кодируются вместе: ABA->RTQ; ABB->SLL
* В зависимости от позиции символа применяется один из простых шифров

Пример: XOR
```
a ^ a = 0; a ^ b ^ b = a
```

Взлом XOR:
1. XOR текста с собой со смещением, если кратно длине ключа, то много одинаковых байт
1. XOR текста с собой с найденным смещением, использовать статистические свойства языка

---
# Симметричные алгоритмы

Подстановки, XOR - примеры .def[симметричных] алгоритмов - ключ для дешифрования вычисляется из ключа для шифрования (часто ключи равны).

```
EK(M) = C; DK(C) = M
```

* Потоковые алгоритмы: работают на каждом бите (или байте)
* Блочные: на каждом наборе из бит - блоке

.def[Одноразовые блокноты] - симметричный алгортм с бесконечным ключом - последовательностю случайных символов.
При шифровании данных длины L, в качестве ключа используется префикс последовательности длины L.
После однократнго кодирования префикс больше не исиспользуется.

Не содержит статистических регулярностей языка, поэтому стоек.

Но нужна _случайная_ последовательность символов.

---
# Асимметричные алгоритмы

Односторонние функции:
```
f(x) = y; g(y) = x; // f - легко; g - сложно
```

Пример: односторонний хеш (MDn, SHA-n) - принимает вход произвольной длины, возвращает строку фиксированной длины.

Хороший хеш обладает низком числом коллизий: сложно сгенерировать два входа с одинаковым хешом

На основе односторонних функций строятся ассиметричные алгоритмы (1976: Diffie, Hellman)

K1 - открытый ключ; K2 - закрытый ключ

Закрытый ключ не может быть вычислен из открытого (за разумное время)

EK1(M) = C; DK2(C) = M

Пример: RSA

---
# Протокол

Последовательность шагов для двух или более сторон, направленных на выполнение задачи. Требования:
* стороны должны знать протокол
* выполнять его
* протокол должен быть однозначен
* должен охватывать все возможные ситуации

.def[Криптографический протокол] - невозможно совершить действие или получить информацию, кроме ситуаций, явно разрешённых протоколом
* с арбитром (arbitrated)
* с вспомогательным центром (adjudicated)
* самореализующийся (self-enforcing)

---
# В симметричной системе

Протокол обмена в симметричной криптосистеме:

1. Alice и Bob договариваются о
  - алгоритмах
  - ключах
1. Alice шифрует сообщение
1. Alice отправляет шифровку Bob
1. Bob расшифровывает сообщение

Проблемы:
* Ключи должны распространяться секретно
* Если ключ скомпрометирован, можно читать чужие сообщения и внедрять ложные
* Для каждой пары пользователей требуется ключ, количество O(n2)

---
# В асимметричной системе

Протокол обмена в асимметричной криптосистеме:

1. Alice и Bob договариваются о алгоритмах
1. Bob отправляет свой открытый ключ
1. Alice шифрует им сообщение и отправляет его Bob
1. Bob расшифровывает сообщение используя свой закрытый ключ

Проблемы:
* Ассиметричные алгоритмы медленные
* Уязвимы к атакам с выбранными сообщениям

???

Public-key cryptosystems are vulnerable to chosen-plaintext attacks. If C = E(P), when P is
one plaintext out of a set of n possible plaintexts, then a cryptanalyst only has to encrypt all n
possible plaintexts and compare the results with C (remember, the encryption key is public).
He won’t be able to recover the decryption key this way, but he will be able to determine P.

---
# Гибридные криптосистемы

Сессионные ключи для симметричного шифрования, которые выбираются с помощью асимметричного:
1. Bob отправляет свой открытый ключ
1. Alice генерирует сессионный ключ, шифрует его открытым ключом Bob
1. Bob расшифровывает сессионный ключ используя свой закрытый ключ
1. Используется симметричное шифрование с сессионным ключом

Алгортим Diffie-Hellman:
1. Alice и Bob несекретно выбирают простое n и его первообразный корень g
1. Alice выбирает случайно число x, высылает X = gx mod n
1. Bob выбирает случайно число y, высылает Y = gy mod n
1. Alice вычисляет k = Yx mod n = gxy mod n
1. Bob вычисляет k = Xy mod n = gxy mod n

---
# Атака Man-in-the-Middle

Предположим, существует Mallory - субъект, способный
видеть,
блокировать/менять/высылать новые сообщения.
Обмен ключами в ассиметричной системе:

1. Alice отправляет свой открытый ключ
1. Bob отправляет свой открытый ключ
1. Alice генерирует сессионный ключ, шифрует его открытым ключом Bob
1. Bob расшифровывает сессионный ключ используя свой закрытый ключ
1. Используется симметричное шифрование с сессионным ключом

Атака:
--

1. Mallory перехватывает открытый ключ Alice и отправляет Bob свой
1. Mallory перехватывает открытый ключ Bob и отправляет Alice свой
1. Mallory расшифровывает отправленное Alice и шифрует его собственным ключом
1. Mallory расшифровывает отправленное Bob и шифрует его собственным ключом

---

Атака:

Решение: алгоритм Interlock
1. Alice шифрует открытым ключом Bob, отправляет половину
1. Bob шифрует открытым ключом Alice, отправляет половину
1. Alice отправляет вторую половину
1. Bob расшифровывает, отправляет вторую половину
1. Alice расшифровывает сообщение

???

He
can still substitute his own public keys for Alice’s and Bob’s in steps (1) and (2). But now, when he
intercepts half of Alice’s message in step (3), he cannot decrypt it with his private key and re-encrypt
it with Bob’s public key. He must invent a totally new message and send half of it to Bob. When he
intercepts half of Bob’s message to Alice in step (4), he has the same problem. He cannot decrypt it
with his private key and re-encrypt it with Alice’s public key. He has to invent a totally new message
and send half of it to Alice. By the time he intercepts the second halves of the real messages in steps
(5) and (6), it is too late for him to change the new messages he invented. The conversation between
Alice and Bob will necessarily be completely different.

---
# Цифровая подпись

* подлинность: сообщение подписано
* неподдельность: подписано именно им
* не переиспользуется
* документ не менялся после подписания
* не может отрицаться

Пример: подпись с симметричным алгоритмом и арбитром.
Между каждым пользователем и арбитром установлен секретный ключ.

1. Alice шифрует сообщение и посылает арбитру
1. Арбитр дешифрует, шифрует с информацией “источник - Alice”, посылает Bob
1. Bob дешифрует сообщение и подпись

???
1. This signature is authentic. Trent is a trusted arbitrator and Trent knows that the message
came from Alice. Trent’s certification serves as proof to Bob.

2. This signature is unforgeable. Only Alice (and Trent, but everyone trusts him) knows K A ,
so only Alice could have sent Trent a message encrypted with K A . If someone tried to
impersonate Alice, Trent would have immediately realized this in step (2) and would not
certify its authenticity.

3. This signature is not reusable. If Bob tried to take Trent’s certification and attach it to
another message, Alice would cry foul. An arbitrator (it could be Trent or it could be a
completely different arbitrator with access to the same information) would ask Bob to produce
both the message and Alice’s encrypted message. The arbitrator would then encrypt the
message with K A and see that it did not match the encrypted message that Bob gave him. Bob,
of course, could not produce an encrypted message that matches because he does not know
K A .

4. The signed document is unalterable. Were Bob to try to alter the document after receipt,
Trent could prove foul play in exactly the same manner just described.

5. The signature cannot be repudiated. Even if Alice later claims that she never sent the
message, Trent’s certification says otherwise. Remember, Trent is trusted by everyone; what
he says is true.

---
# Подпись с асимметричным алгоритмом

1. Alice шифрует документ своим закрытым ключом (подпись)
1. Alice посылает подписанный документ
1. Bob дешифрует сообщение открытым ключом Alice

Но скрывать само сообщение не требуется, модификация с хешом:
1. Alice подсчитывает хеш документа
1. Alice шифрует хеш её закрытым ключом (подпись)
1. Alice посылает документ и подписанный хеш
1. Bob подсчитывает хеш и дешифрует хеш с Alice. Подпись верна, если хеши равны

???
1. The signature is authentic; when Bob verifies the message with Alice’s public key, he
knows that she signed it.

2. The signature is unforgeable; only Alice knows her private key.

3. The signature is not reusable; the signature is a function of the document and cannot be
transferred to any other document.

4. The signed document is unalterable; if there is any alteration to the document, the signature
can no longer be verified with Alice’s public key.

5. The signature cannot be repudiated. Bob doesn’t need Alice’s help to verify her signature.

---
# Генерация случайных чисел

https://www.schneier.com/wp-content/uploads/2015/12/fortuna.pdf

* .def[PRNG]: PseudoRandom Number Generator
* .def[RNG]: Random Number Generator
* .def[CRNG]: Cryptographically secure (pseudo)Random Number Generator

.left[
```asciidrawing
    entropy
  +--- |
  |    v
  | +-----+
  | |     +-+
  | |  E  | | alg
  | |     |<+
  | +-----+
  +--> | cryptohash
       v
      rnd
```
]

Linux: [char/random.c](https://github.com/torvalds/linux/blob/master/drivers/char/random.c)
* `/dev/random` (блокируется при недостатке энтропии)
* `/dev/urandom`

Недостаток энтропии на старте системы: сохранять энтропию при выключении и восстанавливать.

* [Widespread Weak Keys in Network Devices](https://factorable.net/)
 * [Weak Keys Remain Widespread in Network Devices](https://www.cis.upenn.edu/~nadiah/papers/weak-keys/weak-keys.pdfA)