# Лекция 6. Методы обеспечения многозадачности в ОС. Процессы, потоки, волокна. Межпроцессное взаимодействие. Синхронизация > *OTda ko'p vazifalilikni ta'minlash usullari. Jarayonlar, oqimlar, tolalar. Jarayonlararo aloqa. Sinxronizatsiya.* --- ## План лекции 1. Многозадачность: основные понятия 2. Процесс: модель, состояния, PCB 3. Жизненный цикл процесса: `fork`, `exec`, `wait`, `exit` 4. Процессы в Windows 5. Планирование процессора: критерии и алгоритмы 6. Планировщики Linux и Windows. Переключение контекста 7. Потоки (threads) 8. Волокна (fibers) и сопрограммы 9. Межпроцессное взаимодействие: обзор 10. Каналы (pipe, FIFO) и сигналы 11. Разделяемая память, очереди сообщений, сокеты. IPC в Windows 12. Синхронизация: состояние гонки и критическая секция 13. Примитивы синхронизации 14. Классические задачи синхронизации 15. Взаимоблокировки (deadlock) 16. Инструменты наблюдения за процессами в Linux 17. Практические задания, типичные ошибки, контрольные вопросы --- # 1. Многозадачность: основные понятия **Многозадачность (multitasking)** — свойство ОС выполнять несколько задач (программ) так, что каждая из них продвигается вперёд, даже если процессор один. На компьютере одновременно работают браузер, редактор, музыкальный плеер, антивирус и десятки системных служб. Процессорных ядер обычно 4–16, а задач — сотни. ОС создаёт **иллюзию одновременности**, быстро переключая процессор между задачами. ### Конкурентность и параллелизм | Понятие | Определение | Пример | |---|---|---| | **Конкурентность (concurrency)** | Несколько задач *находятся в процессе выполнения* в один промежуток времени; на одном ядре они чередуются | Один официант обслуживает 5 столиков по очереди | | **Параллелизм (parallelism)** | Несколько задач *выполняются физически одновременно* на разных ядрах | 5 официантов обслуживают 5 столиков одновременно | ``` Конкурентность (1 ядро): Параллелизм (2 ядра): CPU0: A A B B A C C B A CPU0: A A A A A A CPU1: B B B B B B ``` Параллелизм невозможен без нескольких ядер, а конкурентность возможна и на одном ядре. ### Историческое развитие | Этап | Идея | Проблема, которую решает | |---|---|---| | **Пакетная обработка** | Задачи выполняются строго по очереди | Ручная загрузка программ | | **Мультипрограммирование** | В памяти несколько программ; пока одна ждёт ввода-вывода, выполняется другая | Простой процессора при операциях I/O | | **Разделение времени (time sharing)** | Каждой задаче выдаётся короткий **квант времени** | Интерактивность: много пользователей за терминалами | | **Многопроцессорность / многоядерность** | Настоящий параллелизм | Рост производительности без роста частоты | ### Кооперативная и вытесняющая многозадачность * **Кооперативная (non-preemptive)** — задача сама отдаёт процессор (вызывает `yield` или блокируется на I/O). Если программа зациклилась — «зависает» вся система. Так работали Windows 3.x и Mac OS до версии 9. * **Вытесняющая (preemptive)** — ОС сама отбирает процессор по **прерыванию таймера**, когда квант времени истёк. Ни одна программа не может монополизировать CPU. Так работают все современные ОС: Linux, Windows NT и новее, macOS. > **Ключевая идея:** вытеснение возможно благодаря аппаратному таймеру. Он периодически генерирует прерывание, управление попадает в ядро, и планировщик решает, кому отдать процессор дальше. ### Задачи, ограниченные процессором и вводом-выводом * **CPU-bound** — большую часть времени вычисляют (сжатие видео, компиляция). Длинные «всплески» CPU. * **I/O-bound** — большую часть времени ждут диска, сети, пользователя (текстовый редактор, веб-сервер). Короткие всплески CPU. Жизнь любого процесса — чередование **CPU burst** (работа на процессоре) и **I/O burst** (ожидание ввода-вывода). Хороший планировщик отдаёт приоритет I/O-bound задачам: они быстро освобождают CPU, а пользователь получает быстрый отклик. --- # 2. Процесс: модель, состояния, PCB **Процесс** — это программа в состоянии выполнения вместе со всеми ресурсами, которые ей выделила ОС: адресным пространством, открытыми файлами, учётными данными, состоянием регистров. **Программа** — пассивный файл на диске (`/usr/bin/python3`). **Процесс** — активная сущность. Из одной программы можно запустить много процессов: три окна терминала — это три процесса `bash`. ### Адресное пространство процесса ``` Высокие адреса ┌──────────────────────────┐ │ Стек (stack) ↓ │ локальные переменные, адреса возврата │ │ │ (свободно) │ │ │ │ Куча (heap) ↑ │ malloc / new ├──────────────────────────┤ │ BSS │ неинициализированные глобальные переменные │ Data │ инициализированные глобальные переменные │ Text (код) │ машинные инструкции, только чтение └──────────────────────────┘ Низкие адреса ``` Каждый процесс имеет **собственное виртуальное адресное пространство**. Адрес `0x601040` в процессе A и тот же адрес в процессе B указывают на **разные** физические ячейки. Поэтому процессы изолированы: ошибка в одном не портит память другого. ### Модель состояний процесса (5 состояний) ``` admit dispatch ┌─────┐ ─────▶ ┌───────┐ ──────────────────▶ ┌─────────┐ exit ┌────────────┐ │ New │ │ Ready │ │ Running │ ──────▶ │ Terminated │ └─────┘ └───────┘ ◀────────────────── └─────────┘ └────────────┘ ▲ interrupt (квант истёк) │ │ │ ожидание I/O или события │ I/O завершён ┌─────▼────┐ └───────────────────────── │ Waiting │ └──────────┘ ``` | Состояние | Описание | |---|---| | **New (новый)** | Процесс создаётся, ОС выделяет структуры | | **Ready (готов)** | Процесс готов выполняться и ждёт только процессора | | **Running (выполняется)** | Инструкции процесса исполняются на CPU | | **Waiting / Blocked (ожидание)** | Процесс ждёт события: окончания I/O, сигнала, освобождения мьютекса | | **Terminated (завершён)** | Процесс закончил работу, ОС освобождает ресурсы | Важно понимать переходы: * **Running → Ready** — процесс вытеснен (истёк квант или появился более приоритетный процесс). Он *мог бы* работать дальше. * **Running → Waiting** — процесс сам не может продолжать: он ждёт данных. * **Waiting → Running** напрямую **невозможен**: после окончания I/O процесс сначала попадает в очередь Ready. На одном ядре в состоянии Running в каждый момент находится **не более одного** процесса. ### Состояния процессов в Linux Команда `ps` показывает состояние в столбце `STAT`: | Код | Значение | |---|---| | `R` | Running или Runnable (выполняется или готов) | | `S` | Interruptible sleep — ожидание, которое можно прервать сигналом | | `D` | Uninterruptible sleep — ожидание I/O, сигналом не прерывается | | `T` | Stopped — остановлен (Ctrl+Z, `SIGSTOP`) | | `Z` | Zombie — завершился, но родитель не прочитал код возврата | Linux не различает Ready и Running: оба обозначены `R`. ### Блок управления процессом (PCB) **PCB (Process Control Block)** — структура данных ядра, в которой хранится всё, что ОС знает о процессе. В Linux это `struct task_struct`, в Windows — `EPROCESS` / `KPROCESS`. | Поле PCB | Пример | |---|---| | Идентификатор | PID, PPID (PID родителя) | | Состояние | Ready, Running, Waiting... | | Контекст CPU | Счётчик команд (PC), регистры, указатель стека | | Планирование | Приоритет, nice, использованное время CPU | | Память | Таблицы страниц, границы сегментов | | Файлы | Таблица открытых файловых дескрипторов | | Безопасность | UID, GID, capabilities | | Учёт | Время старта, потреблённое CPU-время | Часть PCB в Linux видна через псевдофайловую систему `/proc`: ```bash cat /proc/$$/status | head -12 # $$ — PID текущей оболочки ls -l /proc/$$/fd # открытые файловые дескрипторы cat /proc/$$/stat | awk '{print $3}' # состояние (R, S, ...) ``` --- # 3. Жизненный цикл процесса: `fork`, `exec`, `wait`, `exit` В Unix-подобных ОС создание процесса разделено на два шага: 1. **`fork()`** — создать **копию** текущего процесса. 2. **`exec()`** — заменить программу в этом процессе на другую. ### `fork()` — одна функция, два возврата `fork()` вызывается один раз, а возвращает управление **дважды**: в родителе и в потомке. | Где | Значение, возвращаемое `fork()` | |---|---| | В родителе | PID созданного потомка (> 0) | | В потомке | 0 | | При ошибке (в родителе) | −1, потомок не создан | ```c // gcc fork1.c -o fork1 #include #include #include #include int main(void) { int x = 5; pid_t pid = fork(); if (pid == -1) { perror("fork"); return 1; } if (pid == 0) { // потомок x += 10; printf("child: PID=%d PPID=%d x=%d\n", getpid(), getppid(), x); exit(0); } wait(NULL); // родитель ждёт потомка printf("parent: PID=%d child=%d x=%d\n", getpid(), pid, x); return 0; } ``` Вывод (PID будут другими): ``` child: PID=4312 PPID=4311 x=15 parent: PID=4311 child=4312 x=5 ``` > **Важно:** у родителя `x` осталась равной 5. После `fork()` у потомка **своя копия** памяти. Изменения в одном процессе не видны в другом. ### Copy-on-Write (COW) Копировать гигабайты памяти при каждом `fork()` было бы очень медленно. Поэтому ядро использует **копирование при записи**: после `fork()` родитель и потомок разделяют одни и те же физические страницы, помеченные «только чтение». Реальная копия страницы создаётся только тогда, когда один из процессов попытается её **изменить**. Если потомок сразу вызывает `exec()`, почти ничего копировать не приходится. ### Подсчёт процессов при нескольких `fork()` Каждый `fork()` удваивает число процессов, которые его выполняют. ```c fork(); fork(); fork(); printf("salom\n"); ``` ``` P0 fork1 ┌──┴──┐ P0 P1 fork2 ┌──┴┐ ┌┴──┐ P0 P2 P1 P3 fork3 ┌┴┐ ┌┴┐ ┌┴┐ ┌┴┐ P0 P4 P2 P5 P1 P6 P3 P7 → 2³ = 8 процессов, 8 строк "salom" ``` Общая формула: после `n` последовательных `fork()` получается **2ⁿ процессов** (из них 2ⁿ − 1 новых). Более хитрый случай — с логическими операторами. Операторы `&&` и `||` вычисляют правую часть **не всегда**: ```c if (fork() && fork()) // второй fork выполняет только РОДИТЕЛЬ (там первый fork() != 0) fork(); printf("x\n"); // итог: 4 процесса ``` > **Ловушка буферизации:** `printf` пишет в буфер `stdout`. Если вывод перенаправлен в файл или канал, буфер не сбрасывается по `\n`, и при `fork()` **копируется вместе с памятью** — строки печатаются по нескольку раз. Перед `fork()` вызывайте `fflush(stdout)` или отключайте буферизацию: `setvbuf(stdout, NULL, _IONBF, 0)`. ### `exec()` — запуск другой программы Семейство функций `exec` (`execl`, `execv`, `execvp`, `execve`...) **заменяет** код, данные и стек процесса новой программой. PID **сохраняется**, открытые файловые дескрипторы (без флага `FD_CLOEXEC`) — тоже. При успехе `exec` **не возвращается**. ```c pid_t pid = fork(); if (pid == 0) { execlp("ls", "ls", "-l", "/tmp", (char *)NULL); perror("execlp"); // выполнится, только если exec не удался _exit(127); } int status; waitpid(pid, &status, 0); if (WIFEXITED(status)) printf("ls завершился с кодом %d\n", WEXITSTATUS(status)); ``` Именно так оболочка `bash` запускает каждую команду: `fork()` → в потомке `exec()` → в родителе `wait()`. ``` bash ──fork()──▶ bash (копия) ──exec("ls")──▶ ls ──exit(0)──▶ zombie │ │ └──────────────────── waitpid() ◀──────────────────────────────┘ (bash забирает код возврата, zombie исчезает) ``` ### `exit()` и `wait()`: зомби и сироты * **`exit(code)`** завершает процесс. Ядро освобождает память и файлы, но **сохраняет запись в таблице процессов** с кодом возврата, пока его не прочитает родитель. * **`wait()` / `waitpid()`** — родитель ждёт завершения потомка и получает его код возврата. | Ситуация | Название | Что происходит | |---|---|---| | Потомок завершился, родитель ещё не вызвал `wait` | **Зомби (zombie, `Z`)** | Остаётся только запись в таблице процессов (PID и код возврата). Зомби не потребляет CPU и память, но занимает PID | | Родитель завершился раньше потомка | **Сирота (orphan)** | Потомка «усыновляет» процесс `init` / `systemd` (PID 1) или назначенный subreaper; он сам вызывает `wait` | > Один зомби безвреден. Но если сервер создаёт тысячи потомков и не вызывает `wait`, таблица процессов заполняется, и новые процессы создать нельзя. Зомби **нельзя убить** командой `kill`: он уже мёртв. Нужно, чтобы родитель вызвал `wait`, или завершить родителя — тогда зомби усыновит `init` и уберёт. ### Дерево процессов У каждого процесса (кроме PID 1) есть родитель. Все процессы образуют дерево с корнем в `systemd` (PID 1): ```bash pstree -p | head -20 ps -eo pid,ppid,stat,cmd --forest | head -20 ``` --- # 4. Процессы в Windows В Windows нет `fork()`. Процесс создаётся одной функцией **`CreateProcess`**, которая сразу загружает указанную программу: ```c STARTUPINFO si = { sizeof(si) }; PROCESS_INFORMATION pi; if (CreateProcess(L"C:\\Windows\\System32\\notepad.exe", NULL, NULL, NULL, FALSE, 0, NULL, NULL, &si, &pi)) { WaitForSingleObject(pi.hProcess, INFINITE); // аналог waitpid DWORD code; GetExitCodeProcess(pi.hProcess, &code); CloseHandle(pi.hThread); CloseHandle(pi.hProcess); } ``` | Аспект | Linux / POSIX | Windows | |---|---|---| | Создание | `fork()` + `exec()` | `CreateProcess()` (один шаг) | | Ожидание | `wait()`, `waitpid()` | `WaitForSingleObject(hProcess)` | | Идентификация | PID (число) | PID + **дескриптор (HANDLE)** | | Иерархия | Строгое дерево, PPID важен | Родитель запоминается, но иерархия слабая | | Зомби | Есть, пока родитель не вызвал `wait` | Объект процесса живёт, пока открыт хотя бы один HANDLE | | Группировка | Группы процессов, сессии, cgroups | **Job objects** (ограничения CPU, памяти на группу) | | Минимальная единица планирования | Поток (task) | Поток | Просмотр процессов в Windows: Диспетчер задач, `tasklist`, `Get-Process` в PowerShell, Process Explorer (Sysinternals). ```powershell Get-Process | Sort-Object CPU -Descending | Select-Object -First 5 tasklist /FI "IMAGENAME eq notepad.exe" taskkill /PID 4312 /F ``` --- # 5. Планирование процессора: критерии и алгоритмы **Планировщик (scheduler)** — компонент ядра, который выбирает, какой процесс из очереди Ready получит процессор. **Диспетчер (dispatcher)** выполняет само переключение. ### Когда принимается решение 1. Процесс переходит из Running в Waiting (запрос I/O). 2. Процесс переходит из Running в Ready (прерывание таймера). 3. Процесс переходит из Waiting в Ready (I/O завершён). 4. Процесс завершается. Если решения принимаются только в случаях 1 и 4 — планирование **невытесняющее**. Если также в 2 и 3 — **вытесняющее**. ### Критерии качества | Критерий | Определение | Цель | |---|---|---| | Загрузка CPU (utilization) | Доля времени, когда CPU занят | ↑ max | | Пропускная способность (throughput) | Число завершённых процессов в единицу времени | ↑ max | | **Время оборота (turnaround time)** | Завершение − Поступление | ↓ min | | **Время ожидания (waiting time)** | Время в очереди Ready = Оборот − Длительность CPU | ↓ min | | Время отклика (response time) | Первый запуск − Поступление | ↓ min | ### Алгоритмы планирования | Алгоритм | Принцип | Вытесняющий? | Плюсы | Минусы | |---|---|---|---|---| | **FCFS** (First Come, First Served) | Кто раньше пришёл, тот раньше выполняется | Нет | Просто, справедливо по порядку | **Эффект конвоя**: короткие задачи ждут за длинной | | **SJF** (Shortest Job First) | Выбирается задача с наименьшим CPU burst | Нет | Минимальное среднее время ожидания (среди невытесняющих) | Длительность заранее неизвестна; голодание длинных задач | | **SRTF** (Shortest Remaining Time First) | Вытесняющий SJF: новая короткая задача вытесняет текущую | Да | Минимальное среднее ожидание вообще | Частые переключения, голодание | | **Приоритетный** | Выполняется задача с наивысшим приоритетом | Оба варианта | Важные задачи быстрее | Голодание низкоприоритетных → решение: **старение (aging)** | | **RR** (Round Robin) | Очередь по кругу, каждому квант `q` | Да | Хорошее время отклика, нет голодания | Большое среднее время оборота; качество зависит от `q` | | **MLFQ** (многоуровневая очередь с обратной связью) | Несколько очередей с разными приоритетами; задача, израсходовавшая квант, опускается ниже | Да | Сам выделяет I/O-bound задачи | Сложная настройка | ### Разобранный пример Четыре процесса (время в миллисекундах): | Процесс | Поступление | CPU burst | |---|---|---| | P1 | 0 | 8 | | P2 | 1 | 4 | | P3 | 2 | 9 | | P4 | 3 | 5 | **FCFS:** ``` | P1 | P2 | P3 | P4 | 0 8 12 21 26 ``` Ожидание: P1 = 0, P2 = 8 − 1 = 7, P3 = 12 − 2 = 10, P4 = 21 − 3 = 18. **Среднее ожидание = (0 + 7 + 10 + 18) / 4 = 8,75 мс.** **SJF (невытесняющий):** в момент 0 есть только P1 — он выполняется до конца. В момент 8 выбираем кратчайший из готовых: P2 (4), затем P4 (5), затем P3 (9). ``` | P1 | P2 | P4 | P3 | 0 8 12 17 26 ``` Ожидание: P1 = 0, P2 = 7, P4 = 12 − 3 = 9, P3 = 17 − 2 = 15. **Среднее = 31 / 4 = 7,75 мс.** **SRTF (вытесняющий):** в момент 1 приходит P2 (4) — осталось у P1 7 > 4, P1 вытесняется. ``` |P1| P2 | P4 | P1 | P3 | 0 1 5 10 17 26 ``` Ожидание = Оборот − Burst: P1 = (17 − 0) − 8 = 9, P2 = (5 − 1) − 4 = 0, P4 = (10 − 3) − 5 = 2, P3 = (26 − 2) − 9 = 15. **Среднее = 26 / 4 = 6,5 мс.** **RR, квант q = 4:** ``` | P1 | P2 | P3 | P4 | P1 | P3 |P4| P3 | 0 4 8 12 16 20 24 25 26 ``` Ожидание: P1 = 20 − 8 − 0 = 12, P2 = 8 − 4 − 1 = 3, P3 = 26 − 9 − 2 = 15, P4 = 25 − 5 − 3 = 17. **Среднее = 47 / 4 = 11,75 мс.** | Алгоритм | Среднее ожидание | Среднее время оборота | |---|---|---| | FCFS | 8,75 | 15,25 | | SJF | 7,75 | 14,25 | | **SRTF** | **6,5** | **13,0** | | RR (q = 4) | 11,75 | 18,25 | > **Вывод:** SRTF даёт минимальное среднее ожидание, но требует знать будущее. RR проигрывает по среднему ожиданию, зато ни одна задача не ждёт дольше `(n − 1) · q` до своего следующего кванта — это и нужно интерактивным системам. ### Выбор кванта для RR * Квант **слишком большой** → RR превращается в FCFS, ухудшается отклик. * Квант **слишком маленький** → большая часть времени уходит на переключение контекста. * Практика: квант должен быть заметно больше времени переключения контекста (единицы микросекунд); типичные значения — от 1 до 100 мс. --- # 6. Планировщики Linux и Windows. Переключение контекста ### Linux: CFS и EEVDF * С 2007 года (ядро 2.6.23) в Linux работал **CFS (Completely Fair Scheduler)**. Он хранит для каждой задачи **виртуальное время выполнения** (`vruntime`) и всегда выбирает задачу с наименьшим `vruntime` (готовые задачи хранятся в красно-чёрном дереве). * С ядра **6.6** (2023) основным алгоритмом стал **EEVDF** (Earliest Eligible Virtual Deadline First). Он сохраняет идею справедливого деления CPU, но лучше учитывает требования к задержке. * Приоритет обычных задач задаётся значением **nice** от −20 (наивысший) до +19 (наинизший). Повысить приоритет (уменьшить nice) может только root. * Для задач реального времени есть политики `SCHED_FIFO` и `SCHED_RR` с приоритетами 1–99. Они всегда вытесняют обычные задачи. ```bash nice -n 10 ./long_job # запустить с пониженным приоритетом renice -n 5 -p 4312 # изменить nice работающего процесса chrt -p 4312 # показать политику планирования ps -eo pid,ni,pri,cls,cmd | head taskset -c 0 ./job # привязать процесс к ядру 0 (CPU affinity) ``` ### Windows Windows планирует **потоки** по **32 уровням приоритета**: 0 — поток обнуления страниц, 1–15 — динамические (обычные), 16–31 — реального времени. Используется вытесняющий RR внутри каждого уровня. Поток, дождавшийся ввода с клавиатуры, или поток активного окна получает **временное повышение приоритета (priority boost)**. ```powershell Start-Process notepad -PassThru | ForEach-Object { $_.PriorityClass = 'BelowNormal' } ``` ### Переключение контекста (context switch) **Переключение контекста** — сохранение состояния текущего процесса (потока) в его PCB и загрузка состояния следующего. ``` Процесс A Ядро Процесс B выполняется │ прерывание таймера └──────────▶ сохранить регистры A в PCB(A) планировщик: выбрать B загрузить регистры из PCB(B) (при смене процесса — сменить таблицы страниц) └──────────▶ выполняется ``` Переключение — это **накладные расходы**: полезная работа в это время не выполняется. Кроме того, после переключения «остывают» кэши процессора и TLB. Переключение между **потоками одного процесса** дешевле, чем между процессами: не нужно менять таблицы страниц. ```bash grep ctxt /proc/stat # всего переключений с момента загрузки grep ctxt_switches /proc/$$/status # voluntary / nonvoluntary для процесса vmstat 1 5 # столбец cs — переключений в секунду ``` * **Добровольное (voluntary)** — процесс сам заблокировался (ждёт I/O). * **Принудительное (nonvoluntary)** — процесс вытеснен (истёк квант). --- # 7. Потоки (threads) **Поток (thread)** — единица выполнения внутри процесса: собственная последовательность инструкций со своими регистрами и стеком. Все потоки процесса работают в **общем адресном пространстве**. ### Что общее, а что своё | Общее для всех потоков процесса | Своё у каждого потока | |---|---| | Код (text) | Счётчик команд (PC) | | Глобальные переменные, куча | Регистры | | Открытые файлы и сокеты | Стек | | PID, учётные данные (UID) | Идентификатор потока (TID) | | Обработчики сигналов | Маска сигналов, `errno` | | | Thread-Local Storage (TLS) | ``` Процесс (одно адресное пространство) ┌───────────────────────────────────────────────────┐ │ Код │ Глобальные данные │ Куча │ Файлы │ ├───────────────┬───────────────┬───────────────────┤ │ Поток 1 │ Поток 2 │ Поток 3 │ │ регистры, PC │ регистры, PC │ регистры, PC │ │ стек │ стек │ стек │ └───────────────┴───────────────┴───────────────────┘ ``` ### Зачем нужны потоки 1. **Отзывчивость** — GUI-поток отвечает пользователю, пока рабочий поток загружает файл. 2. **Разделение ресурсов** — потоки сразу видят общие данные, IPC не нужен. 3. **Экономия** — создать поток и переключиться между потоками дешевле, чем для процессов. 4. **Масштабирование** — потоки одного процесса выполняются параллельно на разных ядрах. Цена этих преимуществ — **нет изоляции**: ошибка в одном потоке (например, обращение по неверному указателю) завершает весь процесс, а одновременный доступ к общим данным требует **синхронизации** (разделы 12–13). ### Процесс или поток? | Критерий | Процесс | Поток | |---|---|---| | Адресное пространство | Своё | Общее с другими потоками процесса | | Стоимость создания | Высокая | Низкая | | Переключение | Дороже (смена таблиц страниц) | Дешевле | | Обмен данными | Через IPC | Через общую память напрямую | | Изоляция при сбое | Сбой одного не влияет на другие | Сбой убивает весь процесс | | Пример | Вкладки Chrome — отдельные процессы | Потоки веб-сервера, обрабатывающие запросы | ### Модели реализации потоков | Модель | Описание | Плюсы | Минусы | Пример | |---|---|---|---|---| | **N:1** (потоки пользовательского уровня) | Все потоки процесса отображаются на один поток ядра; переключает библиотека | Очень быстрое переключение | Блокирующий системный вызов останавливает **все** потоки; нет параллелизма | Ранние Green threads в Java | | **1:1** (потоки уровня ядра) | Каждый пользовательский поток — отдельный поток ядра | Настоящий параллелизм; блокировка одного не мешает другим | Создание дороже; ядро знает о каждом потоке | Linux NPTL, Windows | | **M:N** (гибридная) | M пользовательских потоков на N потоках ядра | Сочетает достоинства | Сложная реализация | Горутины Go, виртуальные потоки Java 21 | ### Потоки в Linux В ядре Linux нет отдельного понятия «поток»: и процесс, и поток — это **задача (task)**, описываемая `task_struct`. Разница в том, какие ресурсы задача **разделяет** с родителем. Её задают флаги системного вызова `clone()`: ``` fork() ≈ clone(SIGCHLD) — ничего не разделяет pthread_create() ≈ clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_THREAD | ...) — разделяет почти всё ``` У потоков одного процесса одинаковый **PID** (в ядре это TGID — идентификатор группы потоков), но разные **TID**. ```bash ps -eLf | head # LWP — идентификатор потока (TID), NLWP — число потоков ls /proc//task # каждый поток — подкаталог top -H -p # потоки процесса в top ``` ### POSIX Threads (pthreads) ```c // gcc threads.c -o threads -pthread #include #include void *worker(void *arg) { int id = *(int *)arg; printf("worker %d started\n", id); return NULL; } int main(void) { pthread_t t[3]; int ids[3] = {1, 2, 3}; for (int i = 0; i < 3; i++) pthread_create(&t[i], NULL, worker, &ids[i]); for (int i = 0; i < 3; i++) pthread_join(t[i], NULL); // ждём завершения, как wait() для процессов printf("all done\n"); return 0; } ``` | Функция | Назначение | |---|---| | `pthread_create` | Создать поток | | `pthread_join` | Дождаться завершения потока и получить результат | | `pthread_detach` | «Отсоединить» поток: ресурсы освободятся сами, `join` не нужен | | `pthread_exit` | Завершить текущий поток | | `pthread_self` | Идентификатор текущего потока | > Порядок строк `worker 1/2/3 started` **не определён**: его выбирает планировщик. Программа, которая полагается на определённый порядок без синхронизации, содержит ошибку. ### Потоки в Windows ```c DWORD WINAPI Worker(LPVOID arg) { /* ... */ return 0; } HANDLE h = CreateThread(NULL, 0, Worker, NULL, 0, NULL); WaitForSingleObject(h, INFINITE); // аналог pthread_join CloseHandle(h); ``` Для большого числа коротких задач и в Linux, и в Windows используют **пул потоков (thread pool)**: заранее создаётся несколько потоков, которые берут задачи из общей очереди. Так не приходится создавать и уничтожать поток на каждый запрос. --- # 8. Волокна (fibers) и сопрограммы **Волокно (fiber)** — «облегчённый поток», которым управляет **сама программа**, а не ядро. Волокна выполняются внутри обычного потока и переключаются **кооперативно**: волокно явно отдаёт управление другому волокну. ``` Поток ядра (видит планировщик ОС) └── Волокно A ──yield──▶ Волокно B ──yield──▶ Волокно C ──yield──▶ Волокно A ... (переключение — в пространстве пользователя, без системного вызова) ``` | Характеристика | Поток (thread) | Волокно (fiber) | |---|---|---| | Кто планирует | Ядро ОС | Программа (библиотека) | | Тип многозадачности | Вытесняющая | Кооперативная | | Стоимость переключения | Системный вызов, микросекунды | Сохранение нескольких регистров, наносекунды | | Параллелизм | Да, на разных ядрах | Нет внутри одного потока | | Блокирующий вызов | Блокирует один поток | Блокирует **все** волокна этого потока | | Число | Тысячи | Сотни тысяч и миллионы | ### Волокна в Windows ```c LPVOID mainFiber, f1; VOID CALLBACK FiberFunc(LPVOID arg) { printf("fiber: step 1\n"); SwitchToFiber(mainFiber); // явно отдать управление printf("fiber: step 2\n"); SwitchToFiber(mainFiber); } int main(void) { mainFiber = ConvertThreadToFiber(NULL); f1 = CreateFiber(0, FiberFunc, NULL); SwitchToFiber(f1); // → "fiber: step 1" SwitchToFiber(f1); // → "fiber: step 2" DeleteFiber(f1); return 0; } ``` В POSIX аналогичный механизм — функции `getcontext` / `makecontext` / `swapcontext` (``). Они объявлены устаревшими, но в glibc по-прежнему работают. ### Сопрограммы и современные языки **Сопрограмма (coroutine)** — функция, которая может приостановить выполнение и позже продолжить с того же места. Это та же идея кооперативной многозадачности на уровне языка: * `async` / `await` в Python, C#, JavaScript, Rust; * горутины Go (модель M:N, рантайм сам распределяет их по потокам ОС); * виртуальные потоки Java 21 (Project Loom). Волокна и сопрограммы хорошо подходят для серверов с огромным числом одновременных соединений, где задачи в основном **ждут сеть**: держать по потоку ядра на каждое соединение слишком дорого. ### Сравнение единиц выполнения | | Процесс | Поток | Волокно / сопрограмма | |---|---|---|---| | Изоляция памяти | Да | Нет | Нет | | Планирует | ОС | ОС | Программа | | Вытеснение | Да | Да | Нет (кооперативно) | | Параллелизм | Да | Да | Только через несколько потоков | | Стоимость | Высокая | Средняя | Низкая | --- # 9. Межпроцессное взаимодействие: обзор Процессы изолированы: один не может прочитать память другого. Но им нужно обмениваться данными: оболочка передаёт вывод `ls` в `grep`, браузер общается с процессом вкладки, веб-сервер — с базой данных. Для этого ОС предоставляет механизмы **межпроцессного взаимодействия (IPC, Inter-Process Communication)**. Существуют две принципиальные модели: ``` Передача сообщений Разделяемая память ┌──────┐ send ┌──────┐ ┌──────┐ ┌──────┐ │ A │ ──────▶ │ ядро │ │ A │ │ B │ └──────┘ │буфер │ └──┬───┘ └───┬──┘ └──┬───┘ │ ┌──────────┐ │ ┌──────┐ receive │ └──▶│ общая │◀──┘ │ B │ ◀──────────┘ │ память │ └──────┘ └──────────┘ ядро участвует в каждой передаче ядро участвует только при настройке ``` | Модель | Плюсы | Минусы | |---|---|---| | **Передача сообщений** (pipe, очередь сообщений, сокет) | Простота, ядро синхронизирует само, работает и по сети | Каждое сообщение копируется через ядро — медленнее | | **Разделяемая память** | Максимальная скорость: нет копирования | Программист сам отвечает за синхронизацию | ### Обзор механизмов IPC | Механизм | Направление | Родство процессов | Через сеть | Особенности | |---|---|---|---|---| | Анонимный канал (`pipe`) | Одностороннее | Только родственные (через `fork`) | Нет | Поток байтов, `|` в shell | | Именованный канал (FIFO) | Одностороннее | Любые | Нет | Имя в файловой системе | | Сигналы | Уведомление | Любые (с правами) | Нет | Только номер сигнала, без данных | | Очередь сообщений | Двустороннее | Любые | Нет | Сообщения с границами и приоритетами | | Разделяемая память | Общая | Любые | Нет | Самый быстрый, нужна синхронизация | | Семафоры (именованные) | — | Любые | Нет | Синхронизация, а не передача данных | | Сокеты Unix (`AF_UNIX`) | Двустороннее | Любые на одной машине | Нет | Можно передавать дескрипторы файлов | | Сокеты TCP/UDP | Двустороннее | Любые | **Да** | Универсальный механизм | | Файлы, отображённые в память (`mmap`) | Общая | Любые | Нет | Разделяемая память, связанная с файлом | --- # 10. Каналы (pipe, FIFO) и сигналы ### Анонимный канал **Канал (pipe)** — однонаправленный буфер в ядре. Один процесс пишет в него с одного конца, другой читает с другого. Данные читаются в порядке записи (FIFO). Вы используете каналы каждый день: ```bash ps aux | grep python | wc -l ``` Оболочка создаёт два канала и три процесса. Стандартный вывод `ps` соединяется со стандартным вводом `grep` и так далее. Системный вызов `pipe(fd)` создаёт два дескриптора: `fd[0]` — для чтения, `fd[1]` — для записи. После `fork()` потомок наследует оба. ```c // gcc pipe.c -o pipe #include #include #include #include int main(void) { int fd[2]; // fd[0] — чтение, fd[1] — запись if (pipe(fd) == -1) { perror("pipe"); return 1; } pid_t pid = fork(); if (pid == 0) { // потомок: читатель close(fd[1]); // ненужный конец закрываем char buf[64]; ssize_t n = read(fd[0], buf, sizeof buf - 1); buf[n] = '\0'; printf("child %d got: %s\n", getpid(), buf); close(fd[0]); return 0; } close(fd[0]); // родитель: писатель const char *msg = "salom, bola!"; write(fd[1], msg, strlen(msg)); close(fd[1]); // читатель получит EOF wait(NULL); return 0; } ``` Правила работы канала: * `read` из **пустого** канала **блокирует** процесс, пока не появятся данные. * `write` в **полный** канал блокирует процесс (ёмкость в Linux по умолчанию — 64 КиБ). * Когда **все** дескрипторы записи закрыты, `read` возвращает 0 — это конец файла (EOF). * Запись в канал, у которого нет ни одного читателя, порождает сигнал **`SIGPIPE`**. > **Типичная ошибка:** забыть закрыть неиспользуемый конец канала. Если потомок не закроет у себя `fd[1]`, он никогда не получит EOF: сам же «держит» конец записи открытым — и зависнет навсегда. ### Именованный канал (FIFO) У анонимного канала нет имени, поэтому им могут пользоваться только родственные процессы. **FIFO** — канал, у которого есть имя в файловой системе: ```bash mkfifo /tmp/myfifo ls -l /tmp/myfifo # prw-r--r-- ... тип 'p' — pipe # Терминал 1: cat /tmp/myfifo # блокируется, пока нет писателя # Терминал 2: echo "salom" > /tmp/myfifo # в терминале 1 появится "salom" rm /tmp/myfifo ``` Данные через FIFO **не записываются на диск** — имя в файловой системе нужно только для того, чтобы процессы нашли канал. ### Сигналы **Сигнал** — асинхронное уведомление процесса о событии. Сигнал несёт только **номер**, данных в нём нет. | Сигнал | № | Действие по умолчанию | Когда возникает | |---|---|---|---| | `SIGINT` | 2 | Завершение | Ctrl+C в терминале | | `SIGKILL` | 9 | Завершение | `kill -9`; **нельзя перехватить или игнорировать** | | `SIGSEGV` | 11 | Завершение + дамп памяти | Обращение к недопустимой памяти | | `SIGPIPE` | 13 | Завершение | Запись в канал без читателя | | `SIGTERM` | 15 | Завершение | `kill` по умолчанию; «вежливая» просьба завершиться | | `SIGCHLD` | 17* | Игнорируется | Потомок завершился или остановился | | `SIGSTOP` | 19* | Остановка | **Нельзя перехватить** | | `SIGTSTP` | 20* | Остановка | Ctrl+Z | | `SIGCONT` | 18* | Продолжение | `fg`, `bg`, `kill -CONT` | \* Номера для Linux на x86/ARM; на других системах они могут отличаться. В скриптах надёжнее писать имена: `kill -TERM`. Процесс может для каждого сигнала (кроме `SIGKILL` и `SIGSTOP`): выполнить действие по умолчанию, игнорировать его или установить **обработчик**. ```c // gcc sig.c -o sig #include #include #include volatile sig_atomic_t stop = 0; void on_sigint(int sig) { stop = 1; } // в обработчике — только установка флага int main(void) { struct sigaction sa = {0}; sa.sa_handler = on_sigint; sigaction(SIGINT, &sa, NULL); printf("PID=%d, press Ctrl+C\n", getpid()); while (!stop) pause(); // ждём сигнала printf("SIGINT received, clean shutdown\n"); return 0; } ``` > В обработчике сигнала можно вызывать только **async-signal-safe** функции. `printf` и `malloc` к ним **не относятся**. Правильный подход — установить флаг типа `volatile sig_atomic_t`, а всю работу сделать в основном цикле. ```bash kill -l # список сигналов kill -TERM 4312 # попросить процесс завершиться kill -9 4312 # убить принудительно (последнее средство) kill -STOP 4312; kill -CONT 4312 trap 'echo "Ctrl+C ushlandi"' INT # обработчик сигнала в bash ``` Почему сначала `SIGTERM`, а не сразу `SIGKILL`? `SIGTERM` позволяет программе корректно завершиться: сохранить данные, закрыть файлы, удалить временные файлы. `SIGKILL` убивает процесс мгновенно, и данные могут быть потеряны. --- # 11. Разделяемая память, очереди сообщений, сокеты. IPC в Windows ### Разделяемая память POSIX Самый быстрый способ обмена: несколько процессов отображают в свои адресные пространства **одну и ту же** область физической памяти. ```c // Писатель. gcc shm_writer.c -o shm_writer (на старых glibc нужен -lrt) #include #include #include #include #include int main(void) { int fd = shm_open("/demo_shm", O_CREAT | O_RDWR, 0600); // создать объект ftruncate(fd, 4096); // задать размер char *p = mmap(NULL, 4096, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0); strcpy(p, "salom from shared memory"); printf("written, run the reader\n"); munmap(p, 4096); close(fd); return 0; } ``` ```c // Читатель. gcc shm_reader.c -o shm_reader #include #include #include #include int main(void) { int fd = shm_open("/demo_shm", O_RDONLY, 0); char *p = mmap(NULL, 4096, PROT_READ, MAP_SHARED, fd, 0); printf("read: %s\n", p); munmap(p, 4096); close(fd); shm_unlink("/demo_shm"); // удалить объект return 0; } ``` В Linux объекты POSIX shared memory видны как файлы в `/dev/shm`: ```bash ls -l /dev/shm ``` > Разделяемая память **не синхронизирует** доступ. Если писатель и читатель работают одновременно, читатель может увидеть наполовину записанные данные. Поэтому её используют вместе с **семафорами** (`sem_open`) или мьютексами с атрибутом `PTHREAD_PROCESS_SHARED`. Существует и старый интерфейс **System V IPC** (`shmget`, `msgget`, `semget`). Его объекты не удаляются после завершения процессов и видны командой: ```bash ipcs -a # сегменты памяти, очереди, семафоры System V ipcrm -m # удалить сегмент ``` ### Очереди сообщений **Очередь сообщений** хранит сообщения с **сохранением границ** (в отличие от канала, который передаёт поток байтов) и, в POSIX-варианте, с **приоритетами**. ```c // gcc mq.c -o mq (в Linux: -lrt на старых glibc) mqd_t q = mq_open("/demo_mq", O_CREAT | O_RDWR, 0600, NULL); mq_send(q, "task-42", 8, 5); // сообщение с приоритетом 5 char buf[8192]; unsigned prio; mq_receive(q, buf, sizeof buf, &prio); // получает сообщение с наивысшим приоритетом mq_close(q); mq_unlink("/demo_mq"); ``` ### Сокеты **Сокет** — конечная точка двустороннего канала связи. Тот же интерфейс (`socket`, `bind`, `listen`, `accept`, `connect`, `send`, `recv`) работает: * **локально** — Unix domain sockets (`AF_UNIX`). Ими пользуются, например, Docker (`/var/run/docker.sock`) и systemd; * **по сети** — TCP/UDP (`AF_INET`, `AF_INET6`). ```bash ss -xl | head # слушающие Unix-сокеты ss -tlnp # слушающие TCP-сокеты и процессы ``` Сокеты — единственный механизм из рассмотренных, который позволяет процессам взаимодействовать **на разных компьютерах**. ### IPC в Windows | Механизм Windows | Аналог в Linux | |---|---| | Анонимные каналы (`CreatePipe`) | `pipe()` | | Именованные каналы (`\\.\pipe\name`, `CreateNamedPipe`) | FIFO, но **двусторонние** и работают по сети | | Отображение файлов (`CreateFileMapping` + `MapViewOfFile`) | `shm_open` + `mmap` | | Почтовые ящики (Mailslots) | Широковещательные дейтаграммы | | Сокеты (Winsock) | Сокеты BSD | | `WM_COPYDATA` (сообщения окон) | — | | COM / RPC / ALPC | D-Bus, RPC | | Сигналов нет; есть `GenerateConsoleCtrlEvent` и события | Сигналы | --- # 12. Синхронизация: состояние гонки и критическая секция ### Состояние гонки (race condition) **Состояние гонки** — ситуация, в которой результат работы программы зависит от того, в каком порядке выполнятся операции параллельных потоков или процессов. Классический пример — два потока по миллиону раз увеличивают общий счётчик: ```c // gcc race.c -o race -pthread #include #include #define N 1000000 long counter = 0; // общая переменная void *worker(void *arg) { for (int i = 0; i < N; i++) counter++; // НЕ атомарная операция! return NULL; } int main(void) { pthread_t t1, t2; pthread_create(&t1, NULL, worker, NULL); pthread_create(&t2, NULL, worker, NULL); pthread_join(t1, NULL); pthread_join(t2, NULL); printf("counter = %ld (expected %d)\n", counter, 2 * N); return 0; } ``` Реальный запуск на 2+ ядрах: ``` counter = 1068612 (expected 2000000) counter = 1049141 (expected 2000000) ``` Результат **каждый раз разный** и меньше ожидаемого. Почему? Операция `counter++` на уровне процессора — это **три** шага: ``` 1. LOAD R ← counter (прочитать из памяти в регистр) 2. ADD R ← R + 1 (увеличить) 3. STORE counter ← R (записать обратно) ``` Если потоки чередуются неудачно, одно увеличение **теряется**: | Шаг | Поток A | Поток B | counter в памяти | |---|---|---|---| | 1 | LOAD R=5 | | 5 | | 2 | | LOAD R=5 | 5 | | 3 | ADD R=6 | | 5 | | 4 | | ADD R=6 | 5 | | 5 | STORE 6 | | 6 | | 6 | | STORE 6 | **6** (а должно быть 7) | Это называется **потерянное обновление (lost update)**. > **Data race** — частный случай: два потока обращаются к одной ячейке памяти без синхронизации, и хотя бы один из них пишет. В C и C++ data race — это **неопределённое поведение**: компилятор вправе генерировать код, исходя из предположения, что гонок нет. ### Критическая секция **Критическая секция** — участок кода, в котором поток обращается к общим данным. Нужно гарантировать, что в критической секции одновременно находится **не более одного** потока. ``` вход (entry section) ← получить разрешение (lock) КРИТИЧЕСКАЯ СЕКЦИЯ ← работа с общими данными выход (exit section) ← освободить (unlock) остальной код ``` Корректное решение задачи критической секции должно удовлетворять **трём требованиям**: 1. **Взаимное исключение (mutual exclusion)** — в критической секции не более одного потока. 2. **Прогресс (progress)** — если секция свободна и кто-то хочет войти, решение о том, кто войдёт, принимается за конечное время; потоки, которые не претендуют на вход, не участвуют в этом решении. 3. **Ограниченное ожидание (bounded waiting)** — существует предел того, сколько раз другие потоки могут войти в секцию, пока данный поток ждёт. Иначе возможно **голодание**. ### Почему простая переменная-флаг не работает ```c int busy = 0; // вход: while (busy) { } // ждём busy = 1; // занимаем ``` Оба потока могут одновременно увидеть `busy == 0` и оба войдут. Проверка и установка флага — **две отдельные операции**, между которыми может произойти переключение. ### Алгоритм Петерсона (для двух потоков) Классическое программное решение для двух потоков (`i` = 0 или 1, `j = 1 − i`): ```c int flag[2] = {0, 0}; // flag[i] = 1: поток i хочет войти int turn; // чья очередь уступать void lock(int i) { int j = 1 - i; flag[i] = 1; // я хочу войти turn = j; // но уступаю очередь другому while (flag[j] && turn == j) { } // жду, пока другой хочет войти и сейчас его очередь } void unlock(int i) { flag[i] = 0; } ``` Алгоритм удовлетворяет всем трём требованиям. Но на **современных процессорах** он в таком виде не работает: процессор и компилятор могут **переупорядочивать** операции чтения и записи памяти. Для корректности нужны атомарные операции или барьеры памяти (`atomic_thread_fence`). Поэтому на практике используют аппаратную поддержку. ### Аппаратная поддержка: атомарные операции Процессор предоставляет инструкции, которые **выполняются неделимо**: * **Test-and-Set (TAS)** — атомарно прочитать старое значение и записать 1. * **Compare-and-Swap (CAS)** — атомарно: «если значение равно `expected`, записать `new`»; возвращает, удалось ли. * **Fetch-and-Add** — атомарно прибавить и вернуть старое значение (`lock xadd` на x86). ```c #include atomic_long counter = 0; atomic_fetch_add(&counter, 1); // атомарный counter++ — гонки нет ``` На основе TAS можно построить простейшую блокировку: ```c atomic_flag lk = ATOMIC_FLAG_INIT; void lock(void) { while (atomic_flag_test_and_set(&lk)) { } } // крутимся, пока занято void unlock(void) { atomic_flag_clear(&lk); } ``` --- # 13. Примитивы синхронизации ### Мьютекс (mutex) **Мьютекс** (mutual exclusion) — блокировка с **владельцем**: разблокировать её может только тот поток, который заблокировал. Если мьютекс занят, поток **засыпает** (переходит в Waiting) и не тратит процессор. ```c pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; void *worker(void *arg) { for (int i = 0; i < N; i++) { pthread_mutex_lock(&m); // вход в критическую секцию counter++; pthread_mutex_unlock(&m); // выход } return NULL; } ``` С мьютексом результат всегда `counter = 2000000`. ### Спин-блокировка (spinlock) Поток, ожидающий **спин-блокировку**, не засыпает, а **крутится в цикле** («активное ожидание»), постоянно проверяя её. | | Мьютекс | Спин-блокировка | |---|---|---| | Ожидание | Сон (без траты CPU) | Активное (тратит CPU) | | Цена захвата при занятости | Переключение контекста | Циклы процессора | | Когда выгодно | Критическая секция длинная или содержит I/O | Секция очень короткая, на многоядерной системе | | Где применяется | Пользовательские программы | Ядро ОС, обработчики прерываний | > На **одноядерной** системе спин-блокировка бессмысленна: пока ждущий поток крутится, владелец блокировки не может выполняться и освободить её. ### Семафор **Семафор** (Э. Дейкстра, 1965) — целочисленный счётчик `S` с двумя атомарными операциями: * **`wait(S)`** (P, `sem_wait`, «down»): если `S > 0`, уменьшить `S` на 1 и продолжить; иначе заблокироваться, пока `S` не станет положительным. * **`signal(S)`** (V, `sem_post`, «up»): увеличить `S` на 1 и разбудить один из ждущих потоков. Виды семафоров: * **Двоичный** (значения 0 и 1) — похож на мьютекс, но у него **нет владельца**: `signal` может вызвать любой поток. * **Считающий** (значения 0..N) — ограничивает число одновременных пользователей ресурса. Пример: не более 3 одновременных подключений к базе данных. ```c #include sem_t slots; sem_init(&slots, 0, 3); // 0 — между потоками одного процесса; начальное значение 3 sem_wait(&slots); // занять одно место (если 0 — ждать) use_database(); sem_post(&slots); // освободить место ``` > В macOS безымянные семафоры `sem_init` не поддерживаются; там используют именованные `sem_open`. В Linux работают оба варианта. Семафор можно использовать и для **упорядочивания**: «поток B должен выполнить шаг 2 только после шага 1 потока A»: ``` sem_t done = 0; Поток A: step1(); sem_post(&done); Поток B: sem_wait(&done); step2(); // step2 всегда после step1 ``` | | Мьютекс | Семафор | |---|---|---| | Значение | Заблокирован / свободен | Целое число ≥ 0 | | Владелец | Есть | Нет | | Назначение | Взаимное исключение | Подсчёт ресурсов и сигнализация между потоками | ### Условная переменная (condition variable) Иногда поток должен ждать не просто освобождения блокировки, а **выполнения условия** («в очереди появился элемент»). Крутиться в цикле, проверяя условие, — расточительно. **Условная переменная** позволяет уснуть до сигнала другого потока. ```c pthread_mutex_lock(&m); while (!condition) // ВСЕГДА while, а не if pthread_cond_wait(&cv, &m); // атомарно: отпустить m и уснуть; при пробуждении снова захватить m /* условие выполнено, m захвачен */ pthread_mutex_unlock(&m); // Другой поток: pthread_mutex_lock(&m); condition = 1; pthread_cond_signal(&cv); // разбудить один ждущий поток (broadcast — все) pthread_mutex_unlock(&m); ``` Почему `while`, а не `if`? Во-первых, бывают **ложные пробуждения (spurious wakeups)**. Во-вторых, пока разбуженный поток снова захватывал мьютекс, другой поток мог успеть «забрать» условие. Поэтому после пробуждения условие нужно проверить заново. ### Монитор **Монитор** — языковая конструкция, объединяющая данные, мьютекс и условные переменные: методы монитора автоматически выполняются со взаимным исключением. Примеры: `synchronized` + `wait/notify` в Java, `lock` + `Monitor` в C#. ### Блокировка чтения-записи и барьер * **Read-write lock** (`pthread_rwlock_t`) — **много читателей одновременно** или **один писатель**. Выгодна, когда чтений намного больше, чем записей (кэш, справочник). * **Барьер** (`pthread_barrier_t`) — точка, в которой N потоков ждут друг друга. Ни один не идёт дальше, пока не придут все. Применяется в параллельных вычислениях по шагам. ### Примитивы в Windows | Windows | POSIX | |---|---| | `CRITICAL_SECTION`, `SRWLOCK` | `pthread_mutex_t`, `pthread_rwlock_t` | | Mutex (`CreateMutex`) — объект ядра, работает между процессами | Мьютекс с `PTHREAD_PROCESS_SHARED` | | Semaphore (`CreateSemaphore`) | `sem_t` | | Event (`CreateEvent`, `SetEvent`) | Условная переменная + флаг | | `CONDITION_VARIABLE` | `pthread_cond_t` | | `Interlocked*` (`InterlockedIncrement`) | `` | | `WaitForSingleObject` / `WaitForMultipleObjects` | `sem_wait`, `pthread_join`, `waitpid`... | ### Как выбрать примитив | Задача | Примитив | |---|---| | Защитить простой счётчик или флаг | Атомарная переменная | | Защитить структуру данных | Мьютекс | | Много чтений, мало записей | Read-write lock | | Ограничить число одновременных пользователей | Считающий семафор | | Ждать, пока выполнится условие | Условная переменная + мьютекс | | Синхронизировать **процессы** | Именованный семафор, process-shared мьютекс в разделяемой памяти | | Очень короткая секция в ядре | Спин-блокировка | --- # 14. Классические задачи синхронизации Эти три задачи — модели реальных ситуаций. На них проверяют любой новый механизм синхронизации. ### 1. Производитель–потребитель (ограниченный буфер) Производитель кладёт элементы в буфер размера N, потребитель забирает их. Производитель должен ждать, если буфер **полон**; потребитель — если он **пуст**. **Решение на семафорах** (три семафора): ``` semaphore mutex = 1; // взаимное исключение при работе с буфером semaphore empty = N; // число свободных мест semaphore full = 0; // число занятых мест Производитель: Потребитель: item = produce(); wait(full); wait(empty); wait(mutex); wait(mutex); item = take(); put(item); signal(mutex); signal(mutex); signal(empty); signal(full); consume(item); ``` > **Порядок важен!** Если производитель сделает `wait(mutex)` **до** `wait(empty)` и буфер окажется полон, он уснёт, удерживая `mutex`. Потребитель не сможет войти, чтобы освободить место, — **взаимоблокировка**. **Решение на мьютексе и условных переменных** (проверено, вывод `sum = 55`): ```c // gcc pc.c -o pc -pthread #include #include #define SIZE 4 int buf[SIZE], in = 0, out = 0, count = 0; pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER; pthread_cond_t not_full = PTHREAD_COND_INITIALIZER; pthread_cond_t not_empty = PTHREAD_COND_INITIALIZER; void put(int x) { pthread_mutex_lock(&m); while (count == SIZE) // while, а не if! pthread_cond_wait(¬_full, &m); buf[in] = x; in = (in + 1) % SIZE; count++; pthread_cond_signal(¬_empty); pthread_mutex_unlock(&m); } int get(void) { pthread_mutex_lock(&m); while (count == 0) pthread_cond_wait(¬_empty, &m); int x = buf[out]; out = (out + 1) % SIZE; count--; pthread_cond_signal(¬_full); pthread_mutex_unlock(&m); return x; } void *producer(void *a) { for (int i = 1; i <= 10; i++) put(i); put(-1); return NULL; } void *consumer(void *a) { long sum = 0; int x; while ((x = get()) != -1) sum += x; printf("sum = %ld\n", sum); // 55 return NULL; } int main(void) { pthread_t p, c; pthread_create(&p, NULL, producer, NULL); pthread_create(&c, NULL, consumer, NULL); pthread_join(p, NULL); pthread_join(c, NULL); return 0; } ``` Где встречается: конвейер `cmd1 | cmd2` (буфер канала), очередь задач пула потоков, буфер печати, очередь сетевых пакетов. ### 2. Читатели–писатели Много потоков читают общие данные, некоторые — изменяют. Читатели могут работать **одновременно**, писатель — только **в одиночку**. ``` semaphore rw_mutex = 1; // доступ писателя (и первого читателя) semaphore mutex = 1; // защита read_count int read_count = 0; Писатель: Читатель: wait(rw_mutex); wait(mutex); write(); read_count++; signal(rw_mutex); if (read_count == 1) wait(rw_mutex); // первый читатель блокирует писателей signal(mutex); read(); wait(mutex); read_count--; if (read_count == 0) signal(rw_mutex); // последний читатель пускает писателей signal(mutex); ``` > В этом варианте («приоритет читателей») при непрерывном потоке читателей писатель может **голодать** вечно. Существуют варианты с приоритетом писателей и «справедливые». Готовая реализация — `pthread_rwlock_t`. ### 3. Обедающие философы Пять философов сидят за круглым столом, между соседями лежит по одной вилке (всего 5). Чтобы поесть, философу нужны **обе** соседние вилки. ``` Ф0 в4 в0 Ф4 Ф1 в3 в1 Ф3 в2 Ф2 ``` Наивное решение — «взять левую вилку, потом правую». Если все пятеро одновременно возьмут левые вилки, каждый будет вечно ждать правую — **взаимоблокировка**. Способы решения: 1. **Упорядочивание ресурсов:** нумеруем вилки, каждый берёт сначала вилку **с меньшим номером**. Философ Ф4 возьмёт сначала в0, а не в4, — цикл ожидания разорван. 2. **Ограничение числа едоков:** за стол одновременно садятся не более 4 философов (семафор со значением 4). 3. **Асимметрия:** чётные философы берут сначала левую вилку, нечётные — правую. 4. **Брать обе вилки атомарно**, под общим мьютексом. --- # 15. Взаимоблокировки (deadlock) **Взаимоблокировка (тупик, deadlock)** — ситуация, когда группа процессов (потоков) ждёт друг друга бесконечно: каждый удерживает ресурс, нужный другому, и ждёт ресурс, удерживаемый другим. ```c // Поток 1 // Поток 2 lock(A); lock(B); lock(B); // ждёт B у потока 2 lock(A); // ждёт A у потока 1 ``` **Пример из жизни:** две машины встретились на узком мосту. Каждая заняла половину моста, и никто не может проехать, пока другая не сдаст назад. ### Четыре условия Коффмана (1971) Взаимоблокировка возможна, только если **одновременно** выполняются все четыре условия: | № | Условие | Смысл | |---|---|---| | 1 | **Взаимное исключение** | Ресурс может использовать только один процесс | | 2 | **Удержание и ожидание (hold and wait)** | Процесс удерживает ресурс и ждёт другой | | 3 | **Отсутствие вытеснения (no preemption)** | Ресурс нельзя отобрать силой, его отдают только добровольно | | 4 | **Циклическое ожидание (circular wait)** | Существует цикл P1 → P2 → ... → Pn → P1, где каждый ждёт ресурс следующего | Достаточно **нарушить хотя бы одно** условие — и взаимоблокировка становится невозможной. ### Граф распределения ресурсов * Кружок — процесс, квадрат — ресурс, точки в квадрате — экземпляры ресурса. * Стрелка **P → R** — процесс *запрашивает* ресурс. * Стрелка **R → P** — ресурс *выделен* процессу. ``` ┌────┐ запрос ┌───┐ выделен ┌────┐ │ P1 │ ────────▶ │ B │ ──────────▶ │ P2 │ └────┘ └───┘ └────┘ ▲ │ │ выделен ┌───┐ запрос │ └──────────── │ A │ ◀──────────────┘ └───┘ Цикл P1 → B → P2 → A → P1 ⇒ взаимоблокировка ``` Правило: если у каждого ресурса **один экземпляр**, то **цикл в графе ⇔ взаимоблокировка**. Если экземпляров несколько, цикл — необходимое, но не достаточное условие. ### Методы борьбы с взаимоблокировками | Подход | Идея | Пример | |---|---|---| | **Предотвращение (prevention)** | Нарушить одно из 4 условий на этапе проектирования | Единый порядок захвата блокировок (нарушает циклическое ожидание); запрашивать все ресурсы сразу (нарушает удержание и ожидание) | | **Обход (avoidance)** | Выдавать ресурс, только если состояние останется **безопасным** | Алгоритм банкира | | **Обнаружение и восстановление (detection)** | Разрешить тупики, периодически искать циклы и устранять их | Завершить процесс-жертву, откатить транзакцию (так делают СУБД) | | **Игнорирование («страусиный алгоритм»)** | Считать тупики редкими и не тратить на них ресурсы | Так поступает большинство ОС общего назначения в отношении пользовательских программ | Самый практичный способ для программиста — **единый порядок захвата блокировок**: если все потоки всегда захватывают `A` раньше `B`, цикл образоваться не может. ### Алгоритм банкира (Дейкстра) ОС заранее знает **максимальную потребность** каждого процесса. Ресурс выдаётся, только если после выдачи система останется в **безопасном состоянии**: существует такой порядок завершения процессов, при котором каждый сможет получить недостающие ресурсы. Обозначения: **Allocation** — выделено сейчас; **Max** — максимальная потребность; **Need = Max − Allocation**; **Available** — свободно. **Пример** (3 типа ресурсов A, B, C; всего 10, 5, 7): | Процесс | Allocation (A B C) | Max (A B C) | Need (A B C) | |---|---|---|---| | P0 | 0 1 0 | 7 5 3 | 7 4 3 | | P1 | 2 0 0 | 3 2 2 | 1 2 2 | | P2 | 3 0 2 | 9 0 2 | 6 0 0 | | P3 | 2 1 1 | 2 2 2 | 0 1 1 | | P4 | 0 0 2 | 4 3 3 | 4 3 1 | **Available = (3, 3, 2).** Алгоритм проверки безопасности: `Work = Available`; ищем процесс, у которого `Need ≤ Work`; считаем, что он завершился и вернул ресурсы: `Work += Allocation`; повторяем. | Шаг | Процесс | Need ≤ Work? | Work после завершения | |---|---|---|---| | 1 | P1 | (1,2,2) ≤ (3,3,2) ✓ | (3,3,2) + (2,0,0) = **(5,3,2)** | | 2 | P3 | (0,1,1) ≤ (5,3,2) ✓ | + (2,1,1) = **(7,4,3)** | | 3 | P0 | (7,4,3) ≤ (7,4,3) ✓ | + (0,1,0) = **(7,5,3)** | | 4 | P2 | (6,0,0) ≤ (7,5,3) ✓ | + (3,0,2) = **(10,5,5)** | | 5 | P4 | (4,3,1) ≤ (10,5,5) ✓ | + (0,0,2) = **(10,5,7)** | Все процессы могут завершиться. Состояние **безопасно**, безопасная последовательность — **⟨P1, P3, P0, P2, P4⟩**. При **запросе** ресурсов процессом Pi: (1) проверить `Request ≤ Need`; (2) проверить `Request ≤ Available`, иначе ждать; (3) *условно* выделить ресурсы и запустить проверку безопасности; если состояние небезопасно — откатить и заставить процесс ждать. > Небезопасное состояние ≠ взаимоблокировка. Оно означает лишь, что ОС **не может гарантировать** отсутствие тупика. На практике алгоритм банкира в ОС общего назначения не используется: заранее знать максимальные потребности процессов невозможно. Но он отлично показывает идею безопасного состояния. ### Родственные проблемы * **Динамическая взаимоблокировка (livelock)** — потоки не заблокированы, они активно что-то делают, но прогресса нет. Как два человека в коридоре, которые одновременно уступают друг другу дорогу. * **Голодание (starvation)** — поток бесконечно не получает ресурс, потому что его постоянно обходят другие. Решение — старение (aging), справедливые очереди. * **Инверсия приоритетов** — высокоприоритетный поток H ждёт мьютекс, который удерживает низкоприоритетный L, а L не получает CPU, потому что работает среднеприоритетный M. Решение — **наследование приоритета**: L временно получает приоритет H (`PTHREAD_PRIO_INHERIT`). Знаменитый случай — сбои марсохода Mars Pathfinder в 1997 году. --- # 16. Инструменты наблюдения за процессами в Linux | Задача | Команда | |---|---| | Список процессов | `ps aux`, `ps -ef` | | Дерево процессов | `pstree -p`, `ps -ef --forest` | | Нагрузка в реальном времени | `top`, `htop` (в `top`: `H` — потоки, `1` — по ядрам) | | Потоки процесса | `ps -eLf`, `ls /proc//task`, `top -H -p ` | | Найти процесс по имени | `pgrep -a nginx`, `pidof nginx` | | Отправить сигнал | `kill -TERM `, `pkill -f script.py`, `killall firefox` | | Приоритет | `nice`, `renice`, `chrt` | | Системные вызовы процесса | `strace -f -p `, `strace -c ./prog` | | Открытые файлы и каналы | `lsof -p `, `ls -l /proc//fd` | | Объекты IPC | `ipcs -a`, `ls /dev/shm`, `ss -xl` | | Переключения контекста | `vmstat 1`, `pidstat -w 1` | | Фоновые задания оболочки | `jobs`, `bg`, `fg`, `&`, `Ctrl+Z`, `nohup`, `disown` | ```bash sleep 300 & # запустить в фоне jobs # [1]+ Running sleep 300 & ps -o pid,ppid,stat,ni,cmd -p $! # $! — PID последнего фонового процесса kill %1 # завершить задание 1 ``` Пример: увидеть потоки и каналы работающей программы: ```bash ./pc & # пример производитель–потребитель ps -o pid,nlwp,cmd -p $! # NLWP — число потоков strace -f -e trace=futex ./race 2>&1 | tail # мьютексы в Linux реализованы через futex ``` --- # 17. Практические задания Выполняйте задания в виртуальной машине с Linux (Ubuntu/Debian). Установите компилятор: `sudo apt install build-essential strace psmisc`. ### Задание 1. Дерево процессов 1. Выполните `pstree -p $$` и `ps -o pid,ppid,stat,cmd --forest`. 2. Запустите `sleep 100 &` и найдите его PPID. Кто его родитель? 3. Найдите в `/proc//status` поля `State`, `PPid`, `Threads`, `voluntary_ctxt_switches`. ### Задание 2. `fork` и зомби 1. Скомпилируйте программу `fork1.c` из раздела 3. Объясните, почему у родителя `x = 5`. 2. Напишите программу, в которой потомок сразу завершается, а родитель 30 секунд спит, **не** вызывая `wait`. В другом терминале найдите зомби: `ps -eo pid,ppid,stat,cmd | grep Z`. 3. Добавьте `wait(NULL)` и убедитесь, что зомби исчез. ### Задание 3. Подсчёт процессов Предскажите, сколько строк напечатает каждый фрагмент, затем проверьте (не забудьте `setvbuf(stdout, NULL, _IONBF, 0)`): ```c for (int i = 0; i < 3; i++) { fork(); printf("i=%d\n", i); } ``` ```c if (fork() || fork()) fork(); printf("y\n"); ``` ### Задание 4. Гонка и её устранение 1. Запустите `race.c` из раздела 12 пять раз. Запишите результаты. 2. Исправьте программу тремя способами: мьютекс, `atomic_fetch_add`, каждый поток считает в локальную переменную и прибавляет её к общей один раз под мьютексом. Сравните время: `time ./race`. ### Задание 5. Канал и FIFO 1. Скомпилируйте `pipe.c`. Удалите строку `close(fd[1])` в потомке и измените его так, чтобы он читал в цикле до EOF. Что произойдёт? Почему? 2. Через FIFO передайте вывод `ls -l /etc` из одного терминала в `wc -l` в другом. ### Задание 6. Сигналы 1. Скомпилируйте `sig.c`. Отправьте программе `SIGINT`, `SIGTERM` и `SIGKILL` из другого терминала. Чем отличается поведение? 2. Напишите bash-скрипт с `trap`, который при Ctrl+C удаляет свой временный файл. ### Задание 7. Производитель–потребитель и планировщик 1. Запустите `pc.c` и замените в нём `while` на `if`. Почему программа может работать неправильно, хотя вы этого, скорее всего, не увидите? 2. Запустите два бесконечных цикла `yes > /dev/null &` с nice 0 и nice 19 на одном ядре (`taskset -c 0`). Сравните `%CPU` в `top`. Объясните результат. --- # 18. Типичные ошибки | Ошибка | Последствие | Как правильно | |---|---|---| | Не проверять результат `fork()` | При ошибке −1 программа ведёт себя непредсказуемо | Обрабатывать `pid == -1` | | Не вызывать `wait()` для потомков | Накопление зомби, исчерпание PID | `wait`/`waitpid` или обработчик `SIGCHLD` | | `fork()` при непустом буфере `stdout` | Дублирование вывода | `fflush(stdout)` перед `fork()` | | Не закрывать неиспользуемые концы канала | Читатель не получает EOF и зависает | Закрывать ненужный конец сразу после `fork()` | | Доступ к общим данным без синхронизации | Гонка, «случайные» ошибки | Мьютекс или атомарные операции | | `if` вместо `while` перед `pthread_cond_wait` | Работа при невыполненном условии | Всегда проверять условие в цикле `while` | | Захват блокировок в разном порядке | Взаимоблокировка | Единый глобальный порядок захвата | | Долгая операция (I/O) внутри критической секции | Остальные потоки простаивают | Минимизировать критическую секцию | | Забыть `unlock` на пути с ошибкой | Вечная блокировка | Единая точка выхода, RAII (`std::lock_guard`) | | `volatile` вместо синхронизации | Гонка сохраняется: `volatile` не даёт атомарности | `atomic_*` или мьютекс | | `printf` в обработчике сигнала | Взаимоблокировка внутри libc | Только флаг `volatile sig_atomic_t` | | Сразу `kill -9` | Потеря данных, «грязные» временные файлы | Сначала `SIGTERM`, затем `SIGKILL` | --- # 19. Что нужно запомнить 1. **Многозадачность** — иллюзия одновременности за счёт переключения CPU; вытесняющая многозадачность основана на прерываниях таймера. 2. **Процесс** — программа в выполнении с собственным адресным пространством; ОС хранит о нём всё в **PCB**. 3. Основные состояния процесса: **New, Ready, Running, Waiting, Terminated**. 4. В Unix процесс создаётся парой **`fork()` + `exec()`**; родитель забирает код возврата через **`wait()`**, иначе остаётся **зомби**. 5. После `n` последовательных `fork()` существует **2ⁿ** процессов. 6. Планировщик выбирает процесс из очереди Ready; **SRTF** минимизирует среднее ожидание, **RR** обеспечивает хороший отклик. 7. **Поток** — единица выполнения внутри процесса; потоки разделяют память, но имеют свои стеки и регистры. 8. **Волокна и сопрограммы** переключаются кооперативно, в пространстве пользователя — дёшево, но без вытеснения. 9. **IPC**: передача сообщений (pipe, FIFO, очереди, сокеты) или разделяемая память (быстро, но нужна синхронизация). 10. **Гонка** возникает, когда результат зависит от порядка выполнения; `counter++` не атомарен. 11. Решение задачи критической секции: **взаимное исключение, прогресс, ограниченное ожидание**. Инструменты — мьютексы, семафоры, условные переменные, атомарные операции. 12. **Взаимоблокировка** требует всех четырёх условий Коффмана; на практике её предотвращают **единым порядком захвата блокировок**. --- # 20. Контрольные вопросы 1. Чем конкурентность отличается от параллелизма? Возможна ли конкурентность на одном ядре? 2. Чем вытесняющая многозадачность отличается от кооперативной? Какое устройство делает вытеснение возможным? 3. Чем программа отличается от процесса? 4. Нарисуйте диаграмму пяти состояний процесса. Почему невозможен переход Waiting → Running? 5. Что хранится в PCB? Как называется PCB в Linux? 6. Что возвращает `fork()` в родителе и в потомке? 7. Почему после `fork()` изменение переменной в потомке не видно в родителе? Что такое copy-on-write? 8. Сколько процессов будет после четырёх последовательных вызовов `fork()`? 9. Что делает `exec()`? Сохраняется ли PID? 10. Что такое процесс-зомби и процесс-сирота? Можно ли убить зомби командой `kill -9`? 11. Чем `CreateProcess` в Windows отличается от пары `fork` + `exec`? 12. Дайте определения времени ожидания и времени оборота. 13. Что такое эффект конвоя? Для какого алгоритма он характерен? 14. Почему SJF трудно реализовать на практике? 15. Как размер кванта влияет на работу RR? 16. Что такое `vruntime` в CFS? Какой планировщик используется в Linux начиная с версии 6.6? 17. Почему переключение между потоками дешевле, чем между процессами? 18. Что потоки одного процесса разделяют, а что у каждого своё? 19. Сравните модели потоков N:1, 1:1 и M:N. 20. Чем волокно отличается от потока? 21. Сравните модели IPC «передача сообщений» и «разделяемая память». 22. Почему читатель канала может зависнуть, если не закрыть конец записи? 23. Чем `SIGTERM` отличается от `SIGKILL`? Какие сигналы нельзя перехватить? 24. Почему `counter++` не является атомарной операцией? Покажите чередование, при котором теряется обновление. 25. Назовите три требования к решению задачи критической секции. 26. Чем мьютекс отличается от семафора? А от спин-блокировки? 27. Почему перед `pthread_cond_wait` используют `while`, а не `if`? 28. Что произойдёт в задаче производитель–потребитель, если поменять местами `wait(empty)` и `wait(mutex)`? 29. Назовите четыре условия Коффмана. Какое из них нарушает единый порядок захвата блокировок? 30. Определите по алгоритму банкира, безопасно ли состояние из раздела 15, и найдите безопасную последовательность. --- # 21. Глоссарий | Русский | O'zbekcha | English | |---|---|---| | Многозадачность | Ko'p vazifalilik | Multitasking | | Конкурентность / параллелизм | Konkurentlik / parallellik | Concurrency / parallelism | | Процесс | Jarayon | Process | | Поток | Oqim | Thread | | Волокно | Tola | Fiber | | Сопрограмма | Korutina (hamdastur) | Coroutine | | Блок управления процессом | Jarayonni boshqarish bloki | Process Control Block (PCB) | | Планировщик | Rejalashtiruvchi | Scheduler | | Квант времени | Vaqt kvanti | Time slice / quantum | | Переключение контекста | Kontekstni almashtirish | Context switch | | Вытеснение | Siqib chiqarish | Preemption | | Время ожидания / оборота | Kutish vaqti / aylanish vaqti | Waiting time / turnaround time | | Межпроцессное взаимодействие | Jarayonlararo aloqa | Inter-Process Communication (IPC) | | Канал | Kanal | Pipe | | Сигнал | Signal | Signal | | Разделяемая память | Umumiy xotira | Shared memory | | Очередь сообщений | Xabarlar navbati | Message queue | | Сокет | Soket | Socket | | Синхронизация | Sinxronizatsiya | Synchronization | | Состояние гонки | Poyga holati | Race condition | | Критическая секция | Kritik seksiya | Critical section | | Взаимное исключение | O'zaro istisno | Mutual exclusion | | Мьютекс | Myuteks | Mutex | | Семафор | Semafor | Semaphore | | Условная переменная | Shartli o'zgaruvchi | Condition variable | | Взаимоблокировка | O'zaro bloklanish (tupik) | Deadlock | | Голодание | Ochlik | Starvation | | Инверсия приоритетов | Ustuvorlik inversiyasi | Priority inversion | | Процесс-зомби / сирота | Zombi jarayon / yetim jarayon | Zombie / orphan process | --- # 22. Литература 1. Таненбаум Э., Бос Х. *Современные операционные системы.* 4-е изд. — СПб.: Питер, 2015. — Гл. 2 «Процессы и потоки», гл. 6 «Взаимоблокировки». 2. Silberschatz A., Galvin P., Gagne G. *Operating System Concepts.* 10th ed. — Wiley, 2018. — Ch. 3–8. 3. Arpaci-Dusseau R., Arpaci-Dusseau A. *Operating Systems: Three Easy Pieces.* — 2018 (бесплатно: ostep.org). — Части «Virtualization: CPU» и «Concurrency». 4. Kerrisk M. *The Linux Programming Interface.* — No Starch Press, 2010. — Гл. 20–37, 43–55. 5. Downey A. *The Little Book of Semaphores.* — Green Tea Press (бесплатно). 6. Russinovich M. и др. *Windows Internals.* 7th ed., Part 1. — Microsoft Press, 2017. — Гл. 3–4 (процессы, потоки, планирование). 7. Документация: `man 2 fork`, `man 3 exec`, `man 2 wait`, `man 7 pipe`, `man 7 signal`, `man 7 shm_overview`, `man 7 pthreads`, `man 7 sem_overview`, `man 7 sched`. 8. Microsoft Learn: *Processes and Threads*, *Synchronization*, *Interprocess Communications*.