Л4 Взаимодействие и планирование процессов

1. Взаимодействие и планирование процессов

2. Процессы и потоки

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

3. Взаимодействие процессов

Взаимодействие процессов в информационных системах — это обмен данными
и информацией между процессами, а планирование процессов — это
распределение процессорного времени между несколькими одновременно
существующими в системе процессами. Эти понятия связаны с управлением
процессами в операционных системах.
Процессы, которые влияют на поведение друг друга путём обмена
информацией, называют взаимодействующими.
Важно избегать состязательной ситуации — например, если общие данные или
файл используются одним процессом, возможность их использования всеми
другими процессами исключается.
Для этого используется взаимное исключение — правило, при котором если
общие данные или файл используются одним процессом, возможность их
использования всеми другими процессами исключается.

4. Взаимодействие процессов

Взаимодействие процессов возникает тогда, когда нескольким процессам
необходимо обмениваться данными или координировать свое поведение.
Основными способами взаимодействия являются:
• Сообщения: передача данных через очереди сообщений, сокеты или каналы.
• Совместно используемая память: выделение общей области памяти,
доступной двум или более процессам.
• Семафоры: специальный объект синхронизации, позволяющий ограничить
число одновременно исполняемых операций.
• Mutex'ы: механизм взаимоисключающей блокировки, гарантирующий, что
одновременно только один поток получает доступ к общему ресурсу.
• Сигналы: асинхронные уведомления процессов о событиях.

5. Взаимодействие процессов

Некоторые ситуации, когда процессам необходимо взаимодействовать:
• Совместное использование ресурсов (например, доступ к общему файлу).
• Ускорение вычислений — часто задачу разделяют на несколько подзадач,
чтобы ускорить её выполнение, и связанные процессы обмениваются
информацией, относящейся к задаче.
• Согласование действий процессов — например, когда один процесс
поставляет данные, а другой их выводит на печать.
Механизмы взаимодействия могут быть разными, например:
• Разделяемая память — несколько процессов совместно используют
некоторую область адресного пространства.
• Передача сообщений — процессы обмениваются информацией посредством
сообщений с помощью базовой операционной системы.
• Каналы (трубы) — псевдофайл, в который один процесс пишет, а другой
читает.

6. Взаимодействие процессов

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

7. Взаимодействие процессов

Типы планирования:
• Независимое планирование:
каждое ядро выбирает процесс независимо от остальных ядер.
• Симметричное планирование:
центральный диспетчер распределяет процессы равномерно между всеми
ядрами.
• Центральное планирование:
единый диспетчер управляет распределением процессов на ядра.
Алгоритмы планирования зависят от задач, для которых используется
операционная система.
Например:
• Алгоритм планирования без переключений (неприоритетный) — не требует
прерывания по аппаратному таймеру, процесс останавливается только когда
блокируется или завершает работу.
• Алгоритм планирования с переключениями (приоритетный) — требует
прерывания по аппаратному таймеру, процесс работает только отведённый
период времени, после этого он приостанавливается по таймеру, чтобы
передать управление планировщику.

8. Взаимодействие процессов

Необходимость алгоритма планирования зависит от задач, для которых будет
использоваться операционная система.
Основные три системы:
1. Системы пакетной обработки - могут использовать неприоритетный и
приоритетный алгоритм (например: для расчетных программ).
2. Интерактивные системы - могут использовать только приоритетный
алгоритм, нельзя допустить чтобы один процесс занял надолго процессор
(например: сервер общего доступа или персональный компьютер).
3. Системы реального времени - могут использовать неприоритетный и
приоритетный алгоритм (например: система управления автомобилем)
Задачи алгоритмов планирования:
1. Для всех систем
• Справедливость - каждому процессу справедливую долю процессорного
времени;
• Контроль над выполнением принятой политики;
• Баланс - поддержка занятости всех частей системы (например: чтобы были
заняты процессор и устройства ввода/вывода);

9. Взаимодействие процессов

2. Системы пакетной обработки
• Пропускная способность - количество задач в час;
• Оборотное время - минимизация времени на ожидание обслуживания и
обработку задач;
• Использование процесса - чтобы процессор всегда был занят;
3. Интерактивные системы
• Время отклика - быстрая реакция на запросы;
• Соразмерность - выполнение ожиданий пользователя (например:
пользователь не готов к долгой загрузке системы);
4. Системы реального времени
• Окончание работы к сроку - предотвращение потери данных;
• Предсказуемость - предотвращение деградации качества в мультимедийных
системах (например: потерь качества звука должно быть меньше чем видео)

10. Взаимодействие процессов

Выбор следующей задачи для выполнения определяется дисциплиной
планирования. Среди наиболее часто используемых дисциплин выделяют:
• FCFS (First-Come First-Served): обработка процессов в порядке поступления
запросов.
• SJF (Shortest Job First): сначала выполняются короткие процессы.
• RR (Round Robin): циклическое переключение между процессами с
фиксированным квантом времени.
• PSJF (Preemptive Shortest Job First): прерывается процесс с большим
временем выполнения, если поступает короткий процесс.
• MLFQ (Multi-level Feedback Queue): процессы перемещаются между
очередями разного приоритета в зависимости от поведения.

11. Lock-free структуры

Некоторые виды lock-free структур данных:
• Очереди — для операций с одним элементом, простой API из двух методов.
• Кольцевые буферы — позволяют обрабатывать несколько элементов за раз,
используют копии из стандартной библиотеки для массовых операций.
• Стеки — реализованы с помощью атомарных указателей, что позволяет
избежать блокировок.
Для синхронизации lock-free структур данных используются атомарные
операции — операции, которые выполняются как один неразделимый шаг.
Примеры атомарных примитивов:
• Compare-And-Swap (CAS) — проверяет, содержит ли переменная ожидаемое
значение, и, если да, заменяет её новым значением.
• Fetch-and-Add — атомарно увеличивает переменную и возвращает её
предыдущее значение.
• Load and Store — атомарно читает или записывает значение в атомарную
переменную.

12. Spinlock

Spinlock (англ. spinlock — циклическая блокировка) — низкоуровневый
примитив синхронизации в планировании процессов. Используется в
многопоточных и мультипроцессорных системах для защиты разделяемых
ресурсов (например, критических участков кода).
Преимущества:
• не требует переключения контекста;
• задержка минимальна при коротких критических секциях.
При попытке захватить спинлок поток (или процессор) повторно проверяет
доступность блокировки в цикле ожидания (spin), не переходя в состояние сна.
Механизм работы:
1. Попытка захвата: поток пытается установить значение флага блокировки
(например, atomic test-and-set или compare-and-swap).
2. Циклическое ожидание: если блокировка занята, поток входит в цикл
проверки, повторяя попытки захвата.
3. Освобождение: владелец блокировки снимает флаг, позволяя другим
потокам захватить спинлок.

13.

Задания
Ответьте на вопросы:
1) Что такое взаимодействие процессов в информационных системах ?
2) Перечислите основные способы взаимодействия;
3) Что такое планирование процессорного времени?
4) Что такое планировщик процессов?
5) Что такое FCFS?
6) Что такое SJF и PSJF?
7) Что такое RR?
8) Что такое MLFQ?
9) Перечислите основные механизмы синхронизации процессов;