Лекция 2. Процессы, потоки и планирование

1. Понятие процесса

1.1. Программа vs процесс

Программа — это пассивная сущность: исполняемый файл на диске (последовательность инструкций и данных).

Процесс — это активная сущность: экземпляр программы, загруженной в память и выполняющейся. Одна программа может порождать несколько процессов (например, несколько вкладок браузера).

  Программа (файл на диске)          Процесс (в памяти)
  ┌──────────────────────┐          ┌──────────────────────┐
  │  Машинный код        │          │  Машинный код        │
  │  Начальные данные    │  ──────> │  Данные (изменяемые) │
  │                      │  загрузка│  Стек                │
  │                      │          │  Куча (heap)         │
  │                      │          │  Контекст (регистры) │
  │                      │          │  PID, права, ресурсы │
  └──────────────────────┘          └──────────────────────┘

1.2. Адресное пространство процесса

Каждый процесс имеет собственное виртуальное адресное пространство, изолированное от других процессов:

Высокие адреса
┌────────────────────────┐
│        Ядро ОС         │  ← Недоступно из user mode
├────────────────────────┤
│         Стек           │  ← Локальные переменные, адреса возврата
│         │ ↓            │     Растёт вниз
│         ...            │
│         ↑ │            │
│         Куча (heap)    │  ← Динамически выделенная память (malloc/new)
├────────────────────────┤
│  Неинициализированные  │  ← BSS-сегмент (глобальные = 0)
│  данные (.bss)         │
├────────────────────────┤
│  Инициализированные    │  ← Глобальные переменные с начальными значениями
│  данные (.data)        │
├────────────────────────┤
│  Код (.text)           │  ← Машинные инструкции (только чтение)
└────────────────────────┘
Низкие адреса

1.3. Контекст процесса и PCB

Контекст процесса — вся информация, необходимая для возобновления выполнения процесса после приостановки.

PCB (Process Control Block) — структура данных в ядре, хранящая контекст каждого процесса:

Поле PCB	Описание
PID (Process ID)	Уникальный идентификатор процесса
Состояние	Текущее состояние (готов, выполняется, ожидает…)
Программный счётчик (PC)	Адрес следующей инструкции
Регистры CPU	Значения всех регистров процессора
Информация о памяти	Таблицы страниц, границы сегментов
Информация о вводе-выводе	Открытые файлы, устройства
Учётная информация	Владелец, приоритет, время CPU
Указатель на родителя	PID родительского процесса

В Linux PCB реализован как структура task_struct (~8 КБ). В Windows — структура EPROCESS в ядре.

2. Жизненный цикл процесса

2.1. Диаграмма состояний

Процесс проходит через несколько состояний:

                    ┌──────────────┐
      создание      │              │
   ─────────────>   │    Новый     │
                    │   (New)      │
                    └──────┬───────┘
                           │ допуск в очередь готовых
                           ▼
                    ┌──────────────┐         ┌──────────────┐
                    │              │ dispatch │              │
                    │   Готовый    │────────> │ Выполняется  │
                    │  (Ready)    │         │  (Running)   │
                    │              │ <────────│              │
                    └──────┬───────┘ preempt └──────┬───────┘
                           │                        │
                           │                        │ запрос I/O
                           │                        │ или событие
                           │                        ▼
                           │                ┌──────────────┐
                           │                │              │
                           │                │  Ожидание    │
                           │  событие       │  (Waiting/   │
                           │  произошло     │   Blocked)   │
                           │ <──────────────│              │
                           │                └──────────────┘
                           │
                           │         завершение
                           │         (от Running)
                           │                │
                           │                ▼
                           │        ┌──────────────┐
                           │        │ Завершённый  │
                           │        │ (Terminated) │
                           │        └──────────────┘

2.2. Описание состояний

Состояние	Описание	Пример ситуации
Новый (New)	Процесс создан, но ещё не допущен к выполнению	`fork()` вызван, ОС выделяет PCB
Готовый (Ready)	Ожидает выделения CPU	Процесс загружен, но CPU занят другим
Выполняется (Running)	Инструкции выполняются на CPU	Активный процесс на ядре процессора
Ожидание (Waiting)	Ждёт события (I/O, сигнал, таймер)	Процесс запросил чтение с диска
Завершённый (Terminated)	Выполнение окончено, ресурсы освобождаются	`exit()` вызван или процесс убит

Переключение контекста (context switch): когда ОС снимает один процесс с CPU и ставит другой, она сохраняет контекст текущего процесса в его PCB и загружает контекст нового. Это занимает порядка 1–10 микросекунд в зависимости от архитектуры.

3. Создание процессов

3.1. Модель Unix: fork() + exec()

В Unix-подобных системах создание процесса происходит в два этапа:

fork() — создаёт точную копию текущего процесса (дочерний процесс). Оба процесса продолжают выполнение с точки вызова fork(), но получают разные возвращаемые значения.
exec() — заменяет адресное пространство процесса новой программой.

Родительский процесс (PID 100)
     │
     │  pid = fork()
     │
     ├─────────────────────────────┐
     │ (родитель: pid = 200)      │ (потомок: pid = 0)
     │                             │
     │  wait()                     │  exec("/bin/ls")
     │  ...ждёт...                 │  ─── загружена ls ───
     │                             │  выполнение ls
     │                             │  exit(0)
     │  <── потомок завершён ──    │
     │  продолжает работу          │

Оптимизация: Copy-on-Write (CoW) — при fork() страницы памяти не копируются физически, а разделяются. Копирование происходит только при попытке записи.

3.2. Модель Windows: CreateProcess()

В Windows создание процесса — одна операция:

CreateProcess(
    "C:\\Windows\\notepad.exe",  // путь к программе
    NULL,                        // аргументы командной строки
    NULL, NULL,                  // атрибуты безопасности
    FALSE,                       // наследование дескрипторов
    0,                           // флаги создания
    NULL,                        // окружение
    NULL,                        // рабочий каталог
    &si,                         // информация о запуске
    &pi                          // информация о процессе
);

3.3. Сравнение моделей

Аспект	Unix (fork + exec)	Windows (CreateProcess)
Количество шагов	Два (fork, затем exec)	Один
Гибкость	Высокая: между fork и exec можно настроить окружение	Все параметры передаются сразу
Иерархия	Дерево процессов (родитель → потомки)	Плоская модель (нет строгого дерева)
Процесс-зомби	Да (ждёт wait() от родителя)	Нет (handle закрывается явно)
Копирование	CoW — эффективно	Нет копирования, загрузка с нуля

3.4. Дерево процессов

Linux/Unix: все процессы образуют дерево с корнем в init (PID 1) или systemd:

systemd (PID 1)
├── sshd
│   └── bash
│       └── vim
├── nginx
│   ├── nginx worker
│   └── nginx worker
├── cron
└── dockerd
    └── containerd

Windows: процессы не образуют строгого дерева. Связь «родитель—потомок» существует, но ОС не поддерживает её как иерархию. Любой процесс может завершиться, не влияя на потомков.

4. Потоки (Threads)

4.1. Что такое поток

Поток (thread) — это единица исполнения внутри процесса. Процесс содержит как минимум один поток. Несколько потоков одного процесса разделяют общие ресурсы, но имеют собственные:

Общие (на весь процесс)	Собственные (у каждого потока)
Адресное пространство (код, данные, куча)	Стек
Открытые файлы	Программный счётчик (PC)
Глобальные переменные	Регистры CPU
PID, права доступа	Состояние потока (готов/выполняется/ждёт)
Обработчики сигналов	Thread ID (TID)
Рабочий каталог	Приоритет

4.2. Преимущества потоков перед процессами

Быстрое создание: создать поток ~10x быстрее, чем процесс (не нужно копировать адресное пространство).
Быстрое переключение: переключение контекста между потоками одного процесса дешевле.
Общая память: потоки могут обмениваться данными напрямую, без IPC.
Масштабируемость: на многоядерных CPU потоки могут выполняться параллельно на разных ядрах.

4.3. Модели многопоточности

Существует два уровня потоков: потоки ядра (управляются ОС) и пользовательские потоки (управляются библиотекой в user space). Модели отличаются тем, как они отображаются друг на друга.

Модель 1:1                  Модель N:1                Модель M:N
(один к одному)             (много к одному)          (много ко многим)

User:  T1  T2  T3           User:  T1 T2 T3 T4       User:  T1 T2 T3 T4 T5
        |   |   |                   \  |  |  /               \  |   |  / |
Kernel: K1  K2  K3           Kernel:    K1             Kernel: K1  K2   K3

Модель	Описание	Плюсы	Минусы	Примеры
1:1	Каждый пользовательский поток = поток ядра	Настоящий параллелизм, простота	Накладные расходы ядра на каждый поток	Linux (NPTL), Windows, macOS
N:1	Все пользовательские потоки → один поток ядра	Быстрое переключение, нет syscalls	Один заблокированный поток блокирует все	Green threads (ранняя Java), GNU Pth
M:N	M пользовательских потоков → N потоков ядра	Гибкость, масштабирование	Сложная реализация	Go (goroutines), Erlang/BEAM, Solaris LWP

4.4. Потоки в разных ОС

ОС	API для потоков	Модель	Примечания
Linux	POSIX Threads (pthreads)	1:1 (NPTL)	Потоки реализованы через `clone()`
Windows	Windows Threads API	1:1	`CreateThread()`, `_beginthreadex()`
macOS	POSIX Threads / GCD	1:1 + user-level (GCD)	Grand Central Dispatch — пулы потоков
Java	`java.lang.Thread`	1:1 (с Java 1.3+)	Virtual Threads (Project Loom, Java 21) — M:N
Go	Goroutines	M:N	Миллионы горутин на десятки потоков ОС

5. Планирование CPU

5.1. Зачем нужно планирование

На одном ядре процессора в каждый момент времени может выполняться только один поток. Если потоков больше, чем ядер (а так бывает почти всегда), ОС должна решать: кому выделить CPU и на сколько. Эту задачу решает планировщик (scheduler).

5.2. Критерии эффективности

Критерий	Описание	Важен для
Пропускная способность (throughput)	Число завершённых процессов за единицу времени	Серверов, пакетной обработки
Время отклика (response time)	Время от подачи запроса до начала ответа	Интерактивных систем, GUI
Время ожидания (waiting time)	Суммарное время в очереди готовых	Всех систем
Время оборота (turnaround time)	Время от подачи задачи до её завершения	Пакетных систем
Справедливость (fairness)	Равноценное выделение CPU всем процессам	Многопользовательских систем
Предсказуемость	Стабильное время выполнения	Систем реального времени

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

6. Алгоритмы планирования

6.1. FCFS (First Come, First Served)

Принцип: процессы обслуживаются в порядке прибытия — «первый пришёл, первый обслужен».

Пример:

Процесс	Время прибытия	Время выполнения (burst)
P1	0	24
P2	1	3
P3	2	3

Диаграмма Ганта:

|     P1 (24 мс)              |P2 (3)|P3 (3)|
0                             24     27     30

Среднее время ожидания: (0 + 23 + 25) / 3 = 16 мс
Среднее время оборота: (24 + 26 + 28) / 3 = 26 мс

Плюсы: простота реализации. Минусы: эффект конвоя — короткие процессы ждут за длинным.

6.2. SJF (Shortest Job First)

Принцип: сначала выполняется процесс с наименьшим временем burst. Оптимален по среднему времени ожидания (доказывается математически), но требует знания длительности заранее.

Тот же пример, но SJF (невытесняющий):

|     P1 (24 мс)              |P2 (3)|P3 (3)|
0                             24     27     30

(P1 уже на CPU, P2 и P3 пришли позже — не вытесняют)

Если все приходят одновременно (время = 0):

|P2 (3)|P3 (3)|     P1 (24 мс)              |
0      3      6                              30

Среднее время ожидания: (6 + 0 + 3) / 3 = 3 мс — значительно лучше!

Плюсы: оптимальное среднее время ожидания. Минусы: требует предсказания burst; возможно голодание (starvation) длинных процессов.

Вариант SRTF (Shortest Remaining Time First): вытесняющая версия SJF — если приходит процесс с меньшим оставшимся временем, текущий процесс прерывается.

6.3. Round Robin (Циклическое планирование)

Принцип: каждый процесс получает квант времени (time quantum, q). По истечении кванта процесс переходит в конец очереди готовых.

Пример (q = 4 мс):

Процесс	Burst
P1	24
P2	3
P3	3

Диаграмма Ганта:

|P1(4)|P2(3)|P3(3)|P1(4)|P1(4)|P1(4)|P1(4)|P1(4)|
0     4     7    10    14    18    22    26    30

P2 и P3 завершаются быстро (7 и 10 мс), P1 получает оставшееся время порциями.

Выбор кванта:

q слишком большой → вырождается в FCFS.
q слишком маленький → слишком много переключений контекста (overhead).
Типичное значение: 10–100 мс.

Плюсы: справедливость, хорошее время отклика. Минусы: среднее время оборота может быть хуже SJF; overhead от переключений.

6.4. Приоритетное планирование

Принцип: каждому процессу назначается приоритет (число). CPU получает процесс с наивысшим приоритетом.

Может быть вытесняющим (preemptive) или невытесняющим (non-preemptive).
Приоритеты могут быть статическими (заданы при создании) или динамическими (меняются со временем).

Проблема: голодание (starvation) — низкоприоритетные процессы могут никогда не получить CPU.

Решение: старение (aging) — приоритет процесса постепенно повышается с ростом времени ожидания.

6.5. Многоуровневые очереди с обратной связью (MLFQ)

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

Очередь 0 (высший приоритет, q = 8 мс)
┌────────────────────────────────────┐
│  Новые и интерактивные процессы    │ ──→ CPU (квант 8 мс)
└────────────────┬───────────────────┘     │
                 │ не завершился за квант  │
                 ▼                         │
Очередь 1 (средний приоритет, q = 16 мс)  │
┌────────────────────────────────────┐     │
│  Процессы, не уложившиеся в q=8   │ ──→ CPU (квант 16 мс)
└────────────────┬───────────────────┘     │
                 │ не завершился           │
                 ▼                         │
Очередь 2 (низший приоритет, FCFS)        │
┌────────────────────────────────────┐     │
│  Длительные CPU-bound процессы    │ ──→ CPU (FCFS)
└────────────────────────────────────┘

Правила MLFQ:

Новый процесс попадает в очередь с наивысшим приоритетом.
Если процесс использовал весь квант — понижается.
Если процесс отдал CPU досрочно (ожидание I/O) — остаётся на текущем уровне или повышается.
Периодический boost — все процессы возвращаются наверх (предотвращение голодания).

Плюсы: адаптивность — интерактивные процессы получают быстрый отклик, CPU-bound процессы не голодают. Минусы: много параметров для настройки (число очередей, кванты, правила перемещения).

6.6. Сравнительная таблица алгоритмов

Алгоритм	Вытеснение	Голодание	Лучше для	Сложность
FCFS	Нет	Нет	Простых пакетных задач	Минимальная
SJF / SRTF	Нет / Да	Да	Минимального времени ожидания	Средняя (предсказание)
Round Robin	Да	Нет	Интерактивных систем	Низкая
Приоритетное	Опционально	Да (без aging)	Систем с чёткими приоритетами	Средняя
MLFQ	Да	Нет (с boost)	Универсальных ОС	Высокая

7. Планирование в реальных ОС

7.1. Linux: CFS (Completely Fair Scheduler)

С 2007 года (ядро 2.6.23) основным планировщиком Linux является CFS, разработанный Инго Молнаром.

Ключевая идея: каждый процесс должен получить справедливую долю процессорного времени. CFS отслеживает, сколько «виртуального времени» (vruntime) каждый процесс уже получил, и выбирает для выполнения процесс с наименьшим vruntime.

Структура данных: красно-чёрное дерево (сбалансированное BST), упорядоченное по vruntime.

           Красно-чёрное дерево CFS

                [vruntime=50]
               /              \
        [vruntime=30]    [vruntime=70]
        /         \              \
  [vruntime=10] [vruntime=40]  [vruntime=90]
       ↑
  Следующий на выполнение (минимальный vruntime)

Выбор следующего процесса: O(1) — самый левый узел дерева.
Вставка/удаление: O(log n).
nice значение процесса влияет на скорость роста vruntime: у процесса с высоким приоритетом vruntime растёт медленнее → он чаще выбирается.

Примечание: с ядра Linux 6.6 (2023) появился EEVDF (Earliest Eligible Virtual Deadline First) — эволюция CFS с учётом deadline.

7.2. Windows: планировщик на основе приоритетов

Windows использует вытесняющее приоритетное планирование с 32 уровнями приоритета:

Приоритеты Windows:
  0       — Idle (только системный обнулитель страниц)
  1-15    — Обычные (variable priority) — динамически меняются
  16-31   — Реального времени (real-time priority) — фиксированные

Приоритетные классы процессов: Idle, Below Normal, Normal, Above Normal, High, Realtime.

Dynamic Priority Boosting:

Поток, получивший ввод от пользователя (нажатие клавиши, клик мыши), получает временное повышение приоритета → быстрый отклик GUI.
Поток, завершивший ожидание I/O, также повышается в приоритете.
После использования кванта приоритет постепенно снижается обратно.

7.3. macOS/iOS: Grand Central Dispatch (GCD)

macOS использует классический приоритетный планировщик Mach, но прикладной уровень предлагает GCD — систему пулов потоков с очередями:

Программист не создаёт потоки напрямую, а ставит задачи в dispatch queues.
ОС сама решает, сколько потоков создать и на каких ядрах выполнять.
Quality of Service (QoS) классы: User Interactive, User Initiated, Utility, Background.

8. Межпроцессное взаимодействие (IPC)

Процессы изолированы друг от друга (разные адресные пространства), но часто нуждаются в обмене данными. Для этого существуют механизмы IPC (Inter-Process Communication).

8.1. Обзор механизмов IPC

Механизм	Направленность	Скорость	Сложность	Типичное применение
Канал (pipe)	Однонаправленный	Высокая	Низкая	`ls \| grep txt` — конвейер в shell
Именованный канал (FIFO / Named Pipe)	Одно-/двунаправленный	Высокая	Низкая	Связь между независимыми процессами
Сигнал (signal)	Асинхронное уведомление	Мгновенная	Низкая	SIGTERM, SIGKILL, SIGHUP — управление процессами
Очередь сообщений (message queue)	Двунаправленная	Средняя	Средняя	Обмен структурированными сообщениями
Разделяемая память (shared memory)	Двунаправленная	Максимальная	Высокая	Обмен большими объёмами данных
Сокеты (sockets)	Двунаправленная	Средняя (сеть)	Средняя	Сетевое взаимодействие, клиент-сервер
Файлы с отображением в память (mmap)	Двунаправленная	Высокая	Средняя	Совместная работа с файлами

8.2. Каналы (Pipes)

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

Процесс A                    Процесс B
(stdout) ───── pipe ──────> (stdin)
           write()            read()

Пример в shell: cat file.txt | grep "error" | wc -l

Именованный канал (named pipe / FIFO): существует как файл в файловой системе, позволяет обмен между независимыми процессами.

Linux: mkfifo /tmp/mypipe
Windows: \\.\pipe\mypipe

8.3. Сигналы

Сигнал — это асинхронное уведомление, посылаемое процессу. Процесс может: обработать сигнал (handler), игнорировать его, или позволить выполнить действие по умолчанию.

Основные сигналы (Unix/Linux):

Сигнал	Номер	Действие	Описание
SIGTERM	15	Завершение	«Пожалуйста, завершись» (можно перехватить)
SIGKILL	9	Уничтожение	Немедленное убийство (нельзя перехватить)
SIGINT	2	Прерывание	Ctrl+C в терминале
SIGSTOP	19	Остановка	Приостановка процесса (нельзя перехватить)
SIGCONT	18	Продолжение	Возобновление после SIGSTOP
SIGSEGV	11	Дамп ядра	Обращение к неверному адресу памяти
SIGCHLD	17	Игнорирование	Дочерний процесс завершился

В Windows аналог сигналов — события (events) и сообщения консоли (Ctrl+C → CTRL_C_EVENT).

8.4. Разделяемая память

Самый быстрый механизм IPC: два процесса отображают один участок физической памяти в свои адресные пространства.

Процесс A                    Процесс B
┌──────────┐                 ┌──────────┐
│ Виртуальн│                 │ Виртуальн│
│ адр.     │                 │ адр.     │
│ простр.  │                 │ простр.  │
│   ...    │                 │   ...    │
│ ┌──────┐ │                 │ ┌──────┐ │
│ │shared│─┼────────┐  ┌────┼─│shared│ │
│ │memory│ │        │  │    │ │memory│ │
│ └──────┘ │        ▼  ▼    │ └──────┘ │
└──────────┘     ┌──────┐   └──────────┘
                 │Физич.│
                 │память│
                 └──────┘

Linux: shmget() / shmat() (System V) или shm_open() / mmap() (POSIX).
Windows: CreateFileMapping() + MapViewOfFile().

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

9. Проблемы конкурентного доступа

9.1. Гонки (Race Conditions)

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

Классический пример: общий счётчик

Два потока одновременно выполняют counter++ (counter = 5):

Поток A                         Поток B
─────────                       ─────────
1. Прочитать counter (= 5)
                                2. Прочитать counter (= 5)
3. Увеличить: 5 + 1 = 6
                                4. Увеличить: 5 + 1 = 6
5. Записать counter = 6
                                6. Записать counter = 6

Результат: counter = 6 (ожидалось 7!)

Операция counter++ не является атомарной: она состоит из трёх машинных инструкций (load, increment, store).

9.2. Взаимные блокировки (Deadlock)

Deadlock — ситуация, когда два или более процесса бесконечно ждут друг друга.

Поток A                         Поток B
─────────                       ─────────
1. Захватить мьютекс M1    ✓
                                2. Захватить мьютекс M2    ✓
3. Захватить мьютекс M2    ⏳ (ждёт B)
                                4. Захватить мьютекс M1    ⏳ (ждёт A)
                  ═══ DEADLOCK ═══

Четыре условия Коффмана (все должны выполняться одновременно):

Взаимное исключение — ресурс может использоваться только одним процессом.
Удержание и ожидание — процесс удерживает ресурс и ждёт другой.
Невозможность отнятия — ресурс нельзя принудительно забрать.
Циклическое ожидание — существует цикл из ожидающих процессов.

Способы борьбы:

Предотвращение: нарушить одно из условий (например, упорядочить захват ресурсов).
Обнаружение: граф ожидания (wait-for graph), поиск циклов.
Избегание: алгоритм банкира (Дейкстра).
Игнорирование: «страусиный алгоритм» — перезагрузка при зависании (используется в большинстве настольных ОС).

9.3. Голодание (Starvation)

Голодание — процесс бесконечно ждёт ресурса, который постоянно достаётся другим (более приоритетным) процессам.

Отличие от deadlock: при голодании система в целом работает, просто один процесс «обделён».

Решение: aging (старение) — постепенное повышение приоритета ожидающего процесса.

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

10.1. Мьютекс (Mutex)

Мьютекс (mutual exclusion) — объект синхронизации, который может быть заблокирован (locked) или свободен (unlocked). Только один поток может удерживать мьютекс.

Поток A                         Поток B
─────────                       ─────────
lock(mutex)    ✓                lock(mutex)   ⏳ (ждёт)
  counter++                       ...
unlock(mutex)                   lock(mutex)    ✓ (получил)
                                  counter++
                                unlock(mutex)

Результат: counter корректно увеличен на 2.

10.2. Семафор (Semaphore)

Семафор — обобщение мьютекса. Содержит целочисленный счётчик:

wait(S) (P-операция): если S > 0, уменьшить S и продолжить; иначе — заблокировать поток.
signal(S) (V-операция): увеличить S; если есть ожидающие потоки — разбудить один.

Тип	Счётчик	Назначение
Бинарный семафор	0 или 1	Аналог мьютекса
Счётный семафор	0..N	Ограничение числа одновременных доступов (пул ресурсов)

10.3. Монитор (Monitor)

Монитор — высокоуровневый механизм синхронизации, объединяющий данные и операции над ними в одном модуле с автоматическим взаимным исключением. Только один поток может выполнять метод монитора.

В языках программирования: ключевое слово synchronized в Java, lock в C#.

10.4. Условная переменная (Condition Variable)

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

wait(cond, mutex) — освобождает мьютекс и засыпает, пока не получит сигнал.
signal(cond) — будит один ожидающий поток.
broadcast(cond) — будит все ожидающие потоки.

10.5. Классические задачи синхронизации

Задача «Производитель—Потребитель» (Producer—Consumer):

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

Производитель                    Буфер [N]                    Потребитель
─────────────                    ──────────                   ────────────
  Создать элемент                 ┌───┬───┬───┬───┐
  wait(empty)     ────────>       │ A │ B │   │   │   <──── wait(full)
  lock(mutex)                     └───┴───┴───┴───┘         lock(mutex)
  Добавить в буфер                                          Извлечь из буфера
  unlock(mutex)                   empty = N - count          unlock(mutex)
  signal(full)                    full  = count              signal(empty)

Задача «Читатели—Писатели» (Readers—Writers):

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

Ситуация	Допускается?
Читатель + Читатель	Да
Читатель + Писатель	Нет
Писатель + Писатель	Нет

Задача «Обедающие философы» (Dining Philosophers):

Пять философов сидят за круглым столом. Между каждыми двумя — одна вилка. Чтобы есть, нужно взять обе соседние вилки. Классическая иллюстрация deadlock.

         Ф0
     🍴      🍴
   Ф4    🍝    Ф1
     🍴      🍴
      Ф3  🍴  Ф2

Решения:

Ограничить число одновременно обедающих (семафор на 4).
Нечётные философы берут сначала левую вилку, чётные — правую (нарушение циклического ожидания).
Использовать монитор с условными переменными.

10.6. Сводная таблица механизмов синхронизации

Механизм	Уровень	Семантика	Пример API
Мьютекс	Ядро / библиотека	Один владелец	`pthread_mutex_lock()`, `EnterCriticalSection()`
Семафор	Ядро	Счётчик доступов	`sem_wait()`, `WaitForSingleObject()`
Монитор	Языковой	Автоматическая блокировка	`synchronized` (Java), `lock` (C#)
Условная переменная	Библиотека	Ожидание условия	`pthread_cond_wait()`, `SleepConditionVariableCS()`
Спинлок	Ядро	Активное ожидание	`pthread_spin_lock()`, `KeAcquireSpinLock()`
RWLock	Библиотека	Читатели/писатели	`pthread_rwlock_rdlock()`, `SRWLock` (Windows)

11. Вопросы для самопроверки

Чем процесс отличается от программы? Какие компоненты входят в адресное пространство процесса?
Нарисуйте диаграмму состояний процесса. Какие события вызывают переход из состояния «Выполняется» в состояние «Ожидание»?
Сравните модели создания процессов в Unix (fork/exec) и Windows (CreateProcess). В чём преимущества каждого подхода?
Чем поток отличается от процесса? Какие ресурсы потоки одного процесса разделяют, а какие имеют собственные?
Сравните модели многопоточности 1:1, N:1 и M:N. Приведите пример технологии для каждой модели.
Продемонстрируйте на примере (с диаграммой Ганта), как алгоритм Round Robin с квантом 4 мс обработает три процесса с burst-временами 8, 4 и 2 мс.
Объясните принцип работы CFS в Linux. Почему используется красно-чёрное дерево?
Что такое гонка (race condition)? Приведите пример с общей переменной и покажите, как мьютекс решает проблему.
Назовите четыре условия Коффмана для deadlock. Какие стратегии существуют для предотвращения взаимных блокировок?
Опишите задачу «Производитель—Потребитель». Какие примитивы синхронизации необходимы для её корректного решения?