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

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. FCFS

FCFS расшифровывается как «первым пришёл — первым обслужен» . Эта
аббревиатура обозначает простую, но мощную систему планирования, в
которой процесс, задача или запрос, поступивший первым, будет обслужен
первым. Это само определение невытесняющего, хронологического метода,
основанного исключительно на времени и порядке.
Другие названия этого метода — «первым пришёл, первым ушёл» (FIFO) и
«первым пришёл, первым выбрал» (FCFC) . Независимо от термина, значение
FCFS остаётся неизменным: задачи выполняются в порядке их поступления.

12. SJF

SJF (Shortest Job First) — алгоритм планирования процессов в операционных
системах, который выбирает в первую очередь процесс с минимальным
ожидаемым временем выполнения.
Принцип работы: алгоритм сортирует процессы в очереди по ожидаемому
времени выполнения от меньшего к большему. Затем назначает ЦП сначала
процессам с коротким временем выполнения, а затем всё более и более
длинным.

13. RR

Round Robin (циклический или карусельный метод) — алгоритм балансировки
нагрузки, который циклически распределяет входящие запросы между
серверами в пуле. Цель — равномерно распределить нагрузку, предотвращая
перегрузку отдельных узлов.
Преимущества: простота реализации, равномерное распределение запросов,
предсказуемое поведение.
Когда использовать: Round Robin наиболее эффективен в однородных
серверных средах, где оборудование одинаковое, а входящие запросы примерно
равны по сложности и требованиям к ресурсам.
Алгоритм проходит по списку серверов последовательно — начиная с первого и
заканчивая последним — а затем повторяет цикл.
Процесс:
1. Первый запрос отправляется на первый сервер в списке.
2. Второй запрос — на второй сервер и так далее.
3. Когда очередь доходит до последнего сервера, следующий запрос снова
направляется на первый сервер, и процесс повторяется.

14. PSJF

PSJF (preemptive SJN — SJN с вытеснением) — алгоритм планирования
процессов, в котором текущий активный процесс прерывается, если его
оставшееся время выполнения больше, чем у новоприбывшего процесса.
Суть алгоритма: всегда выполняется процесс с наименьшим оставшимся
временем, даже если это приводит к прерыванию текущего выполняющегося
процесса.
PSJF обеспечивает большее предпочтение коротким процессам перед
длинными.

15. MLFQ

Multilevel Feedback Queue (MLFQ) — алгоритм планирования процессов в
операционных системах, который использует несколько очередей с разными
приоритетами.
Цель — динамически расставлять приоритеты на основе поведения процессов и
истории их выполнения, обеспечивая эффективное использование CPU.
Особенности MLFQ:
• Несколько очередей с разным уровнем приоритета, обычно иерархически.
• Динамическая настройка приоритетов — процессы могут двигаться между
очередями на основе своего поведения.
• Механизм обратной связи — система регулирует приоритет процессов на
основе истории их выполнения.

16. Критерии планирования

Критерии планирования определяют, насколько хорошо выполнена та или иная
стратегия. Основные критерии:
• Время отклика: среднее время ожидания между поступлением запроса и
началом его выполнения.
• Среднее время завершения: средняя продолжительность выполнения
процессов.
• Загрузка процессора: процент загрузки центрального процессора.
• Количество переключений контекста: частота смены активных процессов.

17. Синхронизация процессов

Синхронизация необходима, когда потоки работают параллельно и нуждаются в
доступе к общим ресурсам. Основные механизмы синхронизации:
• Lock-free структуры: структуры данных, не использующие блокировки.
• Spinlock: простой примитив синхронизации, блокирующий поток до
освобождения ресурса.
• Semaphore: сигнальное устройство, разрешающее определенное количество
параллельных обращений к ресурсу.
• Atomic operations: атомарные операции чтения-записи, исключающие гонки
данных.

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

Lock-free структуры данных (без блокировок) — это структуры, доступ к
которым возможен одновременно из разных потоков без использования
традиционных примитивов синхронизации (мьютексов). Смысл в том, что даже
если несколько потоков работают с данными одновременно, хотя бы один из
них гарантированно завершит операцию успешно.
Преимущества lock-free структур:
• Высокая производительность — несколько потоков могут работать без
блокировки других.
• Отсутствие дедлоков — нет риска, что один поток бесконечно ждёт, пока
другой освободит блокировку.
• Улучшенная масштабируемость —
несколько потоков могут прогрессировать
без блокировки других, что подходит для
высокопроизводительных систем.

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

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

20. Spinlock

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

21. Spinlock

Spinlock эффективен для кратковременных критических секций и в системах с
высокой конкуренцией за ресурсы, где переключение контекста дорогостоящо.
Также спинлоки используются:
в ядре операционных систем;
в системах реального времени с минимальной задержкой;
в высокопроизводительных параллельных вычислениях;
в управлении разделяемыми ресурсами в многопоточных приложениях.

22. Semaphore

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

23. Semaphore

Использование семафоров предъявляет ряд требований к планировщику и
реализации семафоров, чтобы предотвратить ресурсное голодание, которое
недопустимо в многозадачных приложениях. Например:
• Если есть хотя бы одна задача, готовая к исполнению, она должна
исполняться.
• Если задача готова к исполнению, время до начала её исполнения должно
быть конечным.
• Если происходит сигнализирование семафором, по которому есть
заблокированные задачи, то, по крайней мере, одна из них должна перейти в
состояние готовности к
исполнению.

24. Atomic operations

Atomic operations (атомарные операции) в планировании процессов — это
операции, которые выполняются как единое целое, не могут быть прерваны
другими потоками или процессами. Это обеспечивает целостность данных в
многопоточных или распределённых системах, где несколько потоков могут
одновременно работать с одними и теми же данными.
Основная идея — все шаги операции выполняются в одной
последовательности, без вмешательства других потоков. Это гарантирует, что
операция будет завершена успешно, или если произойдёт ошибка, она будет
возвращена в исходное состояние.
Некоторые типы атомарных операций:
• Атомарные загрузки и записи — обеспечивают безопасную работу с
памятью, разделяемой между несколькими потоками.
• Атомарные арифметические операции — включают сложение, вычитание,
инкремент, декремент и т. п..
• Атомарные операции сравнения и обмена (Compare-And-Swap, CAS) —
позволяют атомарно сравнить текущее значение в памяти с ожидаемым и,
если они совпадают, заменить его на новое значение.

25. Atomic operations

Атомарность операций может обеспечиваться аппаратно или программно:
• Аппаратно — используются особые машинные инструкции, атомарность
выполнения которых гарантируется аппаратурой.
• Программно — используются специальные программные средства
синхронизации, с помощью которых осуществляется блокировка
разделяемого ресурса, а после блокировки выполняется операция, которую
требуется выполнить атомарно.
В современных языках
программирования, таких как
C++ и Java, существуют
встроенные механизмы для
реализации атомарных операций.

26.

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

27.

Задания
Практические задания:
1. Изучение методов синхронизации процессов
Задание: выберите два разных метода синхронизации процессов (например,
семафоры и mutex’ы) и создайте небольшие фрагменты кода на языке
программирования Python или C++, демонстрируя оба метода в действии.
Покажите, как один процесс ждёт освобождения ресурса другим процессом.
Порядок выполнения:
1) Начните с простейшего примера с двумя потоками, один из которых
владеет ресурсом, а другой хочет его захватить.
2) Реализуйте пример, показывая, как процесс блокируется до момента
освобождения ресурса.
3) Дополнительно добавьте комментарий к каждому участку кода,
объясняющий его назначение.

28.

Задания
Практические задания:
2. Сценарий захвата и освобождения спинлока
Задание: напишите программу на языке Си, демонстрирующую использование
спинлока (spinlock) для защиты критической секции. Покажите, как два
процесса ждут освобождения ресурса и завершают операцию.
Порядок выполнения:
1) Используйте переменную для представления спинлока.
2) Два процесса будут пытаться захватить и освободить замок
последовательно.
3) Добавьте печать сообщений, чтобы отслеживать активность обоих
процессов.

29.

Задания
Практические задания:
3. Круговое планирование RR (Round Robin)
Задание: смоделируйте схему простого кругового планирования (Round Robin) с
фиксированным размером кванта времени. Каждый процесс должен получать
равное время выполнения, пока не исчерпает лимит.
Порядок выполнения:
1) Создайте коллекцию процессов с произвольными временами выполнения.
2) Исполнение задач должно происходить порциями, равных кванту времени.
3) Завершившими считают процессы, которые полностью исполнили
назначенное время.

30.

Задания
Практические задания:
4. Сокращение времени ожидания при планировании SRTF
Задание: напишете программу, реализующую стратегию планирования SRTF
(Shortest Remaining Time First). Нужно моделировать запуск процессов с разным
оставшимся временем выполнения и следить за тем, какой процесс получит
доступ первым.
Порядок выполнения:
1) Генерация набора процессов с разными начальными моментами запуска и
продолжительностью выполнения.
2) Переходите к следующему процессу всякий раз, когда появляется новый
процесс с меньшим оставшимся временем выполнения.
3) Показывайте промежуточные значения и статистику.

31. Благодарю за внимание