Организация вычислительного процесса. Тема 2

1. Тема 2. Организация вычислительного процесса.

2.1. Концепция процессов и потоков. Задания,
процессы, потоки (нити), волокна
2.2. Мультипрограммирование. Формы
многопрограммной работы
2.3. Управление процессами и потоками
2.4. Создание процессов и потоков. Модели процессов
и потоков
2.5. Планирование процессов и потоков
2.6. Взаимодействие и синхронизация процессов и
потоков
2.7. Аппаратно-программные средства поддержки
мультипрограммирования
1

2. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Мультипрограммирование
(многозадачность, multitasking) - это такой
способ
организации
вычислительного
процесса, при котором на одном процессоре
попеременно
выполняются
несколько
программ.
2

3. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Чтобы
поддерживать
мультипрограммирование,
ОС
должна
определить для себя внутренние единицы
работы, между которыми будет разделяться
процессор и другие ресурсы компьютера.
В ОС пакетной обработки машин второго
и третьего поколения единицей работы было
задание.
3

4. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
В настоящее время в большинстве
операционных систем определены два типа
единиц работы: более крупная единица процесс или задача, и менее крупная - поток
или нить.
Процесс выполняется в форме одного
или нескольких потоков.
4

5. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Процесс – это выполняемая программа,
включая текущие значения счетчика команд,
регистров и переменных.
С каждым процессом связывается его
адресное пространство, содержащее саму
программу, данные к ней и ее стек.
5

6. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Все функционирующее на компьютере
программное
обеспечение,
включая
и
операционную систему, можно представить
набором процессов.
6

7. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Для решения задачи рационального
управления
процессами
и
ресурсами
компьютера операционная система должна
располагать
информацией
о
текущем
состоянии каждого процесса и ресурса.
Универсальный подход к предоставлению
такой информации заключается в создании и
поддержке таблиц с информацией по
каждому объекту управления.
7

8. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
В некоторых современных ОС, например
в Windows 2000/2003 вновь вернулись к такой
единице работы, как задание (Job).
Задание в Windows представляет собой
набор из одного или нескольких процессов,
управляемых как единое целое.
8

9. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

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

10. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

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

11. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

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

12. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Ресурсы системы
Память
Устройства
Файлы
Процессы
Управляющие
таблицы ОС
Таблицы памяти
Образ
процесса
Процесс 1
Таблицы ввода-вывода
Таблицы файлов
Первичные таблицы
процессов
Процессор
Процесс 1
Процесс 2
Процесс N
Процесс 3
Процесс N
Операционные системы
12

13. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Процессы
рассматриваются
операционной системой как заявки или
контейнеры для всех видов ресурсов, кроме
одного - процессорного времени.
Этот важнейший ресурс распределяется
операционной системой между другими
единицами работы - потоками.
13

14. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Каждый процесс начинается с одного
потока, но новые потоки могут создаваться
(порождаться) процессом динамически.
В простейшем случае процесс состоит из
одного потока, и именно таким образом
трактовалось понятие «процесс» до середины
80-х годов (например, в ранних версиях UNIX).
14

15. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
В некоторых современных ОС такое
положение сохранилось, т. е. понятие «поток»
полностью поглощается понятием «процесс».
Как
правило,
поток
работает
в
пользовательском режиме, но когда он
обращается к системному
вызову, то
переключается в режим ядра.
15

16. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
После завершения системного вызова
поток продолжает выполняться в режиме
пользователя.
У каждого потока есть два стека: один
используется в режиме ядра, другой - в
режиме пользователя.
16

17. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
У каждого потока есть состояние
(текущие значения всех объектов потока)
идентификатор и два стека, контекст (в
котором сохраняются его регистры, когда он
не работает), приватная область для его
локальных переменных, а также может быть
собственный маркер доступа (информация о
защите).
17

18. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Когда поток завершает свою работу, он
может прекратить свое существование.
Процесс завершается, когда прекратит
существование последний активный поток.
18

19. Взаимосвязь между заданиями, процессами и потоками

Задание
Процессы
Потоки
Стек в режиме
пользователя
Стеки потоков в
режиме ядра
Таблица
процесса
P
T
T
T
Маркеры доступа
Операционные системы
Таблица
процесса
T
P
19

20. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
Для
предоставления
сильно
облегченного псевдопараллелизма в Windows
2000 используются волокна (Fiber), подобные
потокам, но планируемые в пространстве
пользователя создавшей их программой.
20

21. 2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна

Основные понятия
У каждого потока может быть несколько
волокон, с той разницей, что когда волокно
логически блокируется, оно помещается в
очередь блокированных волокон, после чего
для работы выбирается другое волокно в
контексте того же потока.
При этом ОС «не
знает» о смене волокон, так как все тот же
поток продолжает работу.
21

22.

Задание (JOB)
Процесс 1
Процесс 2
Процесс N
Поток 1
Поток 2
Поток k
Thread 1
Thread 2
Thread k
Волокна (Fibers)
Объекты
Название
Описание
Задание
Набор процессов с общими
квотами и лимитами
Процесс
Контейнер для ресурсов и
потоков
Поток
Исполнение кода в процессе
Волокно
Облегченный поток,
полностью управляемый в
пространстве пользователя
Операционные системы
22

23.

2.2. Мультипрограммирование. Формы
многопрограммной работы
2.2.1. Мультипрограммирование в системах
пакетной обработки
Системы
пакетной
обработки
предназначаются для решения задач в
основном вычислительного характера, не
требующих быстрого получения результатов.
Максимальная пропускная способность
компьютера достигается в этом случае
минимизацией простоев его устройств и,
прежде всего, процессора.
Операционные системы
23

24.

2.2.1. Мультипрограммирование в системах
пакетной обработки
Для достижения этой цели пакет заданий
формируется так, чтобы получающаяся
мультипрограммная смесь сбалансированно
загружала все устройства машины.
Например, в такой смеси желательно
присутствие
задач
вычислительного
характера и с интенсивным вводом-выводом.
Операционные системы
24

25.

2.2.1. Мультипрограммирование в
системах пакетной обработки
Канал
Канальная программа
Ввод - вывод
t
Сигнал завершения
операции ввода-вывода
Команда запуска
канала
Центральный
процессор
Вычисления
t
Операции ввода–вывода
Контроллеры
t
Центральный процессор
t
Вычисления
Операционные системы
25

26.

2.2.1. Мультипрограммирование в системах
пакетной обработки
В компьютерах класса мэйнфреймов
совмещение достигается благодаря наличию в
машине
специализированных
процессоров
ввода-вывода (каналов).
Ввод-вывод
осуществляется
одновременно с вычислениями в центральном
процессоре, который «отвлекается» только
для выдачи команд каналам и приема
сигналов о завершении ввода-вывода.
Операционные системы
26

27.

2.2.1. Мультипрограммирование в системах
пакетной обработки
В благоприятных случаях общее время
выполнения смеси задач меньше, чем
суммарное время их последовательного
выполнения.
При этом время выполнения отдельной
задачи может быть больше, чем при
монопольном ее выполнении.
Операционные системы
27

28.

Ta+Tb=11
Ta=6
A
2
Tb=5
2
A
A
2 B
В ы ч и с л е н и я
B
3
B
2
1
t
1
t
Ввод–вывод
Ta+Tb= 8
Tb= 6
Ta= 7
A
2
B
A
3
A
B
2
A
1
2
B
1
В ы ч и с л е н и я
t
Ввод–вывод
1
B
1
t
Готовность (ожидание процессора)
Операционные системы
t
28

29.

2.2.2. Мультипрограммирование в системах
разделения времени
В
системах
разделения
времени
пользователям (в частном случае одному)
предоставляется возможность интерактивной
работы сразу с несколькими приложениями.
Для этого каждое приложение должно
регулярно получать возможность «общения» с
пользователем.
ОС
принудительно
периодически
приостанавливает приложения, не дожидаясь,
когда они «добровольно» освободят процессор.
Операционные системы
29

30.

2.2.2. Мультипрограммирование в системах
разделения времени
Всем
приложениям
попеременно
выделяются кванты времени процессора,
таким образом, пользователи, запустившие
программы
на
выполнение,
получают
возможность поддерживать с ними диалог со
своего терминала.
Если время кванта выбрано достаточно
небольшим, то у всех пользователей
складывается
впечатление
единоличной
работы на машине.
Операционные системы
30

31. 2.2.2. Мультипрограммирование в системах разделения времени

1
2
3
…
Центральный процессор
Операционные системы
n
TКВ = 0,02
мс
31

32.

2.2.3. Мультипрограммирование в системах
реального времени
Назначение систем реального времени:
1.управление
техническими
объектами
(спутник, ракета, атомные электростанции,
станок, научная установка и др.),
2.управление технологическими процессами
(гальваническая линия, долинный процесс и
т. п.),
3.управление
системами
обслуживания
разного рода (резервирование авиабилетов,
оплата покупок и счетов и др.).
Операционные системы
32

33.

2.2.3. Мультипрограммирование в системах
реального времени
Особенности реализации систем реального
времени:
1.существует предельно допустимое время, в
течение которого должна быть выполнена та
или иная программа управления объектом
(время реакции системы);
2.мультипрограммная смесь представляет
собой
фиксированный
набор
заранее
разработанных
программ
решения
функциональных
задач
управления
объектом или процессом;
Операционные системы
33

34.

2.2.3. Мультипрограммирование в системах
реального времени
3.выбор
программы
на
выполнение
осуществляется по прерываниям (исходя из
текущего
состояния
объекта)
или
в
соответствии с расписанием плановых работ;
4.закладывается
запас
вычислительной
мощности на случай пиковой нагрузки, а
также принимаются меры обеспечения
высокой
надежности
работы
системы
(резервирование, дублирование, троирование
с мажоритарным элементом и др.).
Операционные системы
34

35.

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

36.

2.2.3. Мультипроцессорная обработка
Мультипроцессирование поддерживают:
Sun Solaris 2.x, Santa Cruz Operation Open
Server 3.x, OS/2, Windows NT/2000/2003 ,
NetWare, начиная с версии 4.1.
Мультипроцессорные системы делятся на
симметричные и асимметричные.
Эти термины относятся, с одной стороны,
к архитектуре вычислительной системы, а с
другой
к
способу
организации
вычислительного процесса.
Операционные системы
36

37.

2.2.3. Мультипроцессорная обработка
Симметричная
архитектура
мультипроцессорной системы предполагает
однотипность и единообразие включения
процессоров и большую разделяемую между
этими
процессорами
память.
Масштабируемость, т. е. возможность
наращивания числа процессоров в данном
случае ограничена, т. к. все они используют
одну и ту же оперативную память и,
следовательно, должны располагаться в
одном корпусе.
Операционные системы
37

38.

2.2.3. Мультипроцессорная обработка
Такая конструкция (масштабирование по
вертикали) практически ограничивает число
процессоров до 4 или 8.
В симметричных архитектурах все
процессоры пользуются одной и той же схемой
отображения памяти, потому могут быстро
обмениваться данными.
Это обеспечивает достаточно высокую
производительность для приложений, в
которых несколько задач должны активно
взаимодействовать между собой (например,
при работе с базами данных).
Операционные системы
38

39.

2.2.3. Мультипроцессорная обработка
В
симметричных
архитектурах
вычислительных систем легко реализуется
симметричное мультипроцессирование общей
для всех процессоров операционной системой.
При этом все процессоры равноправно
участвуют и в управлении вычислительным
процессом, и в выполнении прикладных
задач.
Разные процессоры могут в какой-то
момент времени одновременно обслуживать
как разные, так и одинаковые модули общей
ОС.
Операционные системы
39

40.

2.2.3. Мультипроцессорная обработка
Программы
ОС
должны
быть
реентерабельными (повторновходимыми).
Операционная
система
полностью
децентрализована.
Ее модули выполняются на любом
доступном процессоре. Как только процессор
завершает выполнение очередной задачи, он
передает управление планировщику задач.
Последний выбирает из общей для всех
процессоров системной очереди задачу,
которая будет выполняться на данном
процессоре следующей.
Операционные системы
40

41.

2.2.3. Мультипроцессорная обработка
Все ресурсы выделяются для каждой
выполняемой задачи по мере возникновения
потребности в них и не закрепляются за
процессором.
В решении одной задачи может быть
занято несколько процессоров, если задача
допускает распараллеливание.
В случае отказа одного или более
процессоров
симметричные
системы
сравнительно просто реконфигурируются.
Операционные системы
41

42.

2.2.3. Мультипроцессорная обработка
В
вычислительных
системах
с
асимметричной архитектурой процессоры
могут
быть
различными
как
по
характеристикам
(производительность,
система команд), так и по функциональной
роли в работе системы.
Могут быть выделены процессоры для
вычислений, ввода-вывода и др.
Операционные системы
42

43.

2.2.3. Мультипроцессорная обработка
Эта неоднородность ведет к структурным
отличиям
во
фрагментах
системы,
содержащих разные процессоры (разные
схемы подключения, наборы периферийных
устройств,
способы
взаимодействия
процессоров с устройствами и др.).
Масштабирование в таких системах
реализуется иначе, поскольку отсутствует
требование единого корпуса.
Система может состоять из нескольких
устройств, каждое из которых содержит один
или несколько процессоров.
Операционные системы
43

44.

2.2.3. Мультипроцессорная обработка
Масштабирование в данном случае
называют
горизонтальным,
а
мультипроцессорную систему - кластерной.
В кластерной системе может быть
реализовано
только
асимметричное
мультипроцессирование
с
организацией
вычислительного процесса по принципу
«ведущий - ведомый».
В таких системах ОС работает на одном
процессоре, который называется ведущим и
организует централизованное управление
вычислительным
процессом
и
распределением всех ресурсов системы.
Операционные системы
44

45. 2.3. Управление процессами и потоками

2.3.1. Основные функции управления процессами и потоками
1. Создание процессов и потоков.
2. Обеспечение процессов и потоков необходимыми ресурсами.
3. Изоляция процессов.
4. Планирование выполнения процессов и потоков.
5. Диспетчеризация потоков.
6. Организация межпроцессного взаимодействия.
7. Синхронизация процессов и потоков.
8. Завершение и уничтожение процессов и потоков.
События, приводящие к созданию процессов:
1. Инициализация (загрузка) ОС.
2. Запрос процесса на создание дочернего процесса.
3. Запрос пользователя на создание процесса (например, при входе в
систему в интерактивном режиме).
4. Инициирование пакетного задания.
5. Создание операционной системой процесса какой-либо службы.
Операционные системы
45

46. 2.3. Управление процессами и потоками

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

47. 2.3. Управление процессами и потоками

2.3.1. Основные функции управления процессами и потоками
Ресурсы могут быть выделены процессу на все время его
жизни или только на определенный период.
Важнейшей задачей ОС является изоляция одного процесса от
другого. Для этого операционная система обеспечивает каждый
процесс отдельным виртуальным адресным пространством, так
что ни один процесс не может получить прямого доступа к
командам и данным другого процесса.
В ОС, где существуют процессы и потоки, процесс
рассматривается как заявка на потребление всех видов ресурсов,
кроме одного - процессорного времени.
Этот важнейший ресурс распределяется операционной
системой между другими единицами работы - потоками, которые
представляют собой последовательности (потоки выполнения)
команд.
Операционные системы
47

48. 2.3. Управление процессами и потоками

2.3.1. Основные функции управления процессами и потоками
Переход от выполнения одного потока к другому
осуществляется в результате планирования и диспетчеризации.
Планирование – это работа по определению того, в какой
момент необходимо прервать выполнение текущего потока и
какому потоку предоставить возможность выполняться.
Планирование
потоков
осуществляется
на
основе
информации, хранящейся в описателях процессов и потоков. При
планировании принимается во внимание приоритет потоков,
время их ожидания в очереди, накопленное время выполнения,
интенсивность обращения к вводу-выводу и другие факторы.
Диспетчеризация – это реализация найденного в результате
планирования решения, т. е. в переключении процессора с одного
потока на другой.
Операционные системы
48

49. 2.3. Управление процессами и потоками

2.3.1. Основные функции управления процессами и потоками
Диспетчеризация проходит в три этапа:
• сохранение контекста текущего потока;
• загрузка контекста потока, выбранного в результате планирования;
• запуск нового потока на выполнение.
Для общения друг с другом процессы и потоки могут
использовать широкий спектр возможностей: каналы (в UNIX),
почтовые ящики (Windows 2000), вызов удаленной процедуры,
сокеты (в Windows соединяют процессы на разных машинах).
Согласование скоростей потоков также очень важно для
предотвращения эффекта «гонок» (когда несколько потоков
пытаются получить доступ к одному и тому же ресурсу), взаимных
блокировок и других коллизий, которые возникают при
совместном использовании ресурсов.
Для решения этой задачи служит синхронизация потоков.
Операционные системы
49

50. 2.3. Управление процессами и потоками

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

51. 2.3. Управление процессами и потоками

2.3.1. Основные функции управления процессами и потоками
Каждый раз, когда процесс завершается, а это происходит
благодаря одному из следующих событий: обычный выход, выход
по ошибке, выход по неисправимой ошибке, уничтожение другим
процессом, - ОС предпринимает шаги, чтобы «зачистить следы»
его пребывания в системе.
Подсистема управления процессами закрывает все файлы, с
которыми работал процесс, освобождает области оперативной
памяти,
отведенные
под
коды, данные
и
системные
информационные структуры процесса.
Выполняется коррекция всевозможных очередей ОС и списка
ресурсов, в которых имелись ссылки на завершаемый процесс.
Операционные системы
51

52. 2.3.2. Роль процессов, потоков и волокон в мультипрограммировании

1. Отдельный процесс не может быть выполнен быстрее, чем в
однопрограммном режиме.
2. Однако приложение, выполняемое в рамках одного процесса, может
обладать внутренним параллелизмом, который в принципе мог бы
ускорить его выполнение.
3. Сложно создать программу, реализующую параллелизм в рамках
одного процесса.
4. Стандартные средства современных ОС не позволяют создать для
одного приложения несколько процессов для параллельных работ.
5. Операционной системе наряду с процессами нужен другой механизм
распараллеливания вычислений, который учитывал бы тесные связи
между отдельными ветвями вычислений одного и того же приложения.
6. Многопоточная обработка позволяет распараллелить вычисления в
рамках одного процесса.
Операционные системы
52

53. 2.3.2. Роль процессов, потоков и волокон в мультипрограммировании

7. Потоки одного процесса используют общие файлы, таймеры,
устройства, одну и ту же область оперативной памяти, одно и то же
адресное пространство; они разделяют одни и те же глобальные
переменные.
8. Многопоточная
(multithreading)
обработка
многопроцессорных вычислительных системах.
эффективна
в
9. Использование аппарата волокон (Windows 2000) повышает
эффективность мультипрограммирования за счет сокращения
переключения режима (пользовательский - привилегированный), но
увеличивает трудоемкость разработки приложений. Для управления
волокнами нет системных вызовов, однако есть вызовы Win32 API,
которые не обращаются к системным вызовам.
Операционные системы
53

54. 2.4. Создание процессов и потоков. Модели процессов и потоков

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

55. 2.4. Создание процессов и потоков. Модели процессов и потоков

2.4.1.Процессы и их модели
Примеры описателей процесса:
• блок управления задачей (ТСВ -Task Control Block) в
OS/360;
• управляющий блок процесса (РСВ -Process Control
Block) в OS/2;
• дескриптор процесса в UNIX;
объект-процесс
(object-process)
в
Windows
NT/2000/2003.
Создание процесса включает загрузку кодов и
данных исполняемой программы данного процесса с
диска в оперативную память.
Операционные системы
55

56. 2.4. Создание процессов и потоков. Модели процессов и потоков

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

57. 2.4. Создание процессов и потоков. Модели процессов и потоков

2.4.1.Процессы и их модели
При управлении процессами ОС использует два
основных типа информационных структур: блок
управления процессом (дескриптор процесса) и
контекст процесса.
Дескрипторы процессов объединяются в таблицу
процессов, которая размещается в области ядра. На
основании информации, содержащейся в таблице
процессов, ОС осуществляет планирование и
синхронизацию процессов.
Операционные системы
57

58. Дескриптор процесса (блок управления) содержит:

1. Информацию по идентификации процесса
(идентификатор процесса, идентификатор пользователя,
идентификаторы родительского и дочерних процессов).
2. Информацию по состоянию процесса
3. Информацию, используемую для управления
процессом
Операционные системы
58

59. Идентификация процесса

Каждому процессу присваивается числовой
идентификатор, который может быть просто
индексом в первичной таблице процессов.
При
создании
нового
процесса
идентификаторы указывают родительский и
дочерние процессы.
Процессу может быть присвоен идентификатор
пользователя, который указывает, кто из
пользователей отвечает за данное задание.
Операционные системы
59

60. Информация по состоянию и управлению процессом

Состояние процесса, определяющее его готовность к выполнению
(выполняющийся, готовый к выполнению, ожидающий события, приостановленный);
Данные о приоритете (текущий, по умолчанию, максимально возможный);
Информация о событиях – идентификация события, наступление которого
позволит продолжить выполнение процесса;
Указатели, позволяющие определить расположение образа процесса в
оперативной памяти и на диске;
Указатели на другие процессы (находящиеся в очереди на выполнение);
Флаги, сигналы и сообщения, имеющие отношение к обмену информацией между
двумя независимыми процессами;
Данные о привилегиях, определяющие права доступа к определенной области
памяти или возможности выполнять определенные виды команд, использовать
системные утилиты и службы;
Указатели на ресурсы, которыми управляет процесс;
Сведения по использованию ресурсов и процессора;
Информация, связанная с планированием.
Операционные системы
60

61. КОНТЕКСТ ПРОЦЕССА

Содержит информацию, позволяющую ОС приостанавливать и
возобновлять выполнение процесса с прерванного места:
• Содержимое регистров процессора, доступных пользователю
(обычно 8 – 32 регистра и до 100 регистров в RISC – процессорах);
• Содержимое счетчика команд;
• Состояние управляющих регистров и регистров состояния;
• Коды условия, отражающие результат выполнения последней
арифметической или логической операции (например, равенство
нулю,переполнение);
• Указатели вершин стеков,хранящие параметры и адреса вызова
процедур и системных служб.
Значительная часть этой информации фиксируется в виде слова
состояния программы PSW (program status word – EFLAGS в
процессоре Pentium).
Операционные системы
61

62. Простейшая модель процесса

Диспетчеризация
Вход
Выход
Не выполняется
Выполняется
Пауза
Граф состояний и переходов
Вход
Диспетчеризация
Очередь
Очередь
Пауза
Операционные системы
CPU
CPU
Выход
tкв
62

63. Простейшая модель процесса

В любой момент времени процесс либо
выполняется, либо не выполняется, т. е. имеет
только два состояния.
Если бы все процессы были всегда готовы к
выполнению, то очередь по этой схеме могла бы
работать вполне эффективно.
Такая очередь работает по принципу
обработки в порядке поступления, а процессор
обслуживает имеющиеся в наличии процессы
круговым методом (Round-robin).
Каждому процессу отводится определенный
промежуток времени, по истечении которого он
возвращается в очередь.
Операционные системы
63

64.

Новый
Вход
Готовый к
выполнению
Выполняющийся
в систему
Освобождение
Блокированный
Поступление
процесса
Завершающийся
Ожидание
события
Очередь готовых процессов
CPU
Тайм – аут ( tКВ )
Ожидание события
Модель с тремя состояниями
Операционные системы
64

65.

Модель с тремя состояниями
Все невыполняющиеся процессы делятся на на
два типа: готовые к выполнению и заблокированные.
Поскольку процессор работает намного быстрее
выполнения операций ввода-вывода, то вскоре все
находящиеся в памяти процессы оказываются в
состоянии ожидания ввода-вывода.
Что делать?
Можно увеличить емкость основной памяти, чтобы в
ней умещалось больше процессов.
Свопинг - перенос части процессов из оперативной
памяти на диск и загрузка другого процесса из
очереди приостановленных (но не блокированных!)
процессов, находящихся во внешней памяти.
Операционные системы
65

66. 2.4.2. Потоки и их модели

При создании потоков ОС генерирует специальную информационную
структуру - описатель потока, который содержит идентификатор потока,
данные о правах доступа и приоритете, о состоянии потока и другую
информацию.
Описатель потока: блок управления потоком и
контекст потока (в многопоточной системе процессы
контекстов не имеют).
Способы реализации пакета потоков:
в пространстве пользователя (user – level threads –
ULT);
в ядре (kernel – level threads – KLT).
Операционные системы
66

67. Поток на уровне пользователя (в пользовательском пространстве)

Процессы
Потоки
Библиотека
подпрограмм для
работы с потоками
Таблица
потоков
Пространство пользователя
Таблица
процессов
Операционные системы
Ядро
67

68. Поток на уровне пользователя (в пользовательском пространстве)

Если управление потоками происходит в
пространстве
пользователя,
каждому
процессу
необходима собственная таблица потоков.
Она аналогична таблице процессов, с той лишь
разницей, что отслеживает такие характеристики
потоков, как счетчик команд, указатель вершины
стека, регистры состояния и т. п.
Когда поток переходит в состояние готовности
или блокировки, вся информация, необходимая для
повторного запуска, хранится в таблице потоков.
Операционные системы
68

69. Поток на уровне пользователя (в пользовательском пространстве)

Приложение в начале своей работы состоит из
одного потока и его выполнение начинается как
выполнение этого потока.
Такое приложение вместе с составляющим его
потоком размещается в одном процессе, который
управляется ядром.
Все эти события происходят в пользовательском
пространстве в рамках одного процесса. Ядро даже «не
подозревает» об этой деятельности и продолжает
осуществлять планирование процесса как единого
целого и приписывать ему единое состояние
выполнения.
Операционные системы
69

70. Поток на уровне пользователя

ДОСТОИНСТВА:
можно реализовать в ОС, не поддерживающей потоки без какихлибо изменений в ОС;
высокая производительность, поскольку процессу не нужно
переключаться в режим ядра и обратно;
ядро о потоках ничего не знает и управляет однопоточными
процессами;
имеется возможность использования любых алгоритмов
планирования потоков с учетом их специфики;
управление потоками возлагается на программу пользователя.
Операционные системы
70

71.

Поток на уровне пользователя
НЕДОСТАТКИ:
системный вызов блокирует не только работающий поток, но и все
потоки того процесса, к которому он относится;
приложение не может работать в многопроцессорном режиме, так
как ядро закрепляет за каждым процессом только один процессор;
при запуске одного потока ни один другой поток а рамках одного
процесса не будет запущен пока первый добровольно не отдаст
процессор;
внутри одного потока нет прерываний по таймеру, в результате
чего невозможно создать планировщик по таймеру для
поочередного выполнения потоков.
Операционные системы
71

72. Поток на уровне ядра

Процессы
Потоки
Пространство пользователя
Ядро
Таблица
процессов
Операционные системы
Таблица
потоков
72

73. Поток на уровне ядра

В случае потоков на уровне ядра в области
приложения система поддержки исполнения
программ не нужна, нет необходимости и в
таблицах потоков в каждом процессе.
Вместо этого есть единая таблица потоков,
отслеживающая все потоки в системе.
Если потоку необходимо создать новый поток
или завершить имеющийся, он выполняет запрос
ядра, который создает или завершает поток, внося
изменения в таблицу потоков.
Ядро поддерживает информацию контекста
процесса как единого целого, а также контексты
каждого
отдельного
потока
процесса.
Планирование осуществляется ядром исходя из
состояния потоков.
Операционные системы
73

74.

Поток на уровне ядра
ДОСТОИНСТВА:
возможно планирование работы нескольких потоков одного
и того же процесса на нескольких процессорах;
реализуется мультипрограммирование в рамках всех
процессов (в том числе одного);
при блокировании одного из потоков процесса ядро может
выбрать другой поток этого же (или другого процесса);
процедуры ядра могут быть многопоточными.
НЕДОСТАТКИ:
Необходимость
двукратного
переключения
режима
пользователь – ядро, ядро – пользователь для передачи
управления от одного потока к другому в рамках одного и
того же процесса.
Операционные системы
74

75.

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

76. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Основная цель планирования вычислительного
процесса заключается в распределении времени
процессора (нескольких процессоров) между
выполняющимися заданиями пользователей
таким
образом,
чтобы
удовлетворять
требованиям, предъявляемым пользователями к
вычислительной системе.
Такими
требованиями
могут
быть
пропускная
способность,
время
отклика,
загрузка процессора и др.
Операционные системы
76

77. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Вид планирования
Выполняемые функции
Долгосрочное
Решение о добавлении задания (процесса) в
пул выполняемых в системе
Среднесрочное
Решение о добавлении процесса к числу
процессов полностью или частично
размещенных в основной памяти
Краткосрочное
(диспетчеризация)
Планирование
ввода-вывода
Решение о том, какой из доступных
процессов (потоков) будет выполняться
процессором
Решение о том, какой из запросов процессов
(потоков) на операцию ввода-вывода будет
выполняться свободным устройством
ввода-вывода
Операционные системы
77

78. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
В большинстве операционных систем
универсального
назначения
планирование
осуществляется динамически (on-line), т. е.
решения принимаются во время работы
системы на основе анализа текущей ситуации,
не
используя
никаких
предложений
о
мультипрограммной смеси.
Найденное оперативно решение в таких
условиях редко бывает оптимальным.
Операционные системы
78

79. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Другой тип планирования - статический
(предварительный) может быть использован
только в специализированных системах с
заданным
набором
задач
(заранее
определенным), например, в управляющих
вычислительных
системах
или
системах
реального времени.
В этом случае статический планировщик
(или
предварительный
планировщик)
принимает решение не во время работы
системы, а заранее (off-line).
Операционные системы
79

80. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Результатом
его
работы
является
расписание - таблица, в которой указано, какому
процессу, когда и на какое время должен быть
предоставлен процессор.
При этом накладные расходы ОС на
исполнение расписания значительно меньше,
чем при динамическом планировании.
Операционные системы
80

81. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Краткосрочный планировщик (диспетчер)
реализует найденное решение, т. е. переключает
процессор с одного процесса (потока) на другой.
Он вызывается при наступлении события,
которое
может
приостановить
текущий
процессор или предоставить возможность
прекратить выполнение данного процесса
(потока) в пользу другого.
Операционные системы
81

82. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Примерами этих событий могут быть:
• прерывание таймера;
• прерывание ввода-вывода;
• вызовы операционной системы;
• сигналы.
Операционные системы
82

83. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Среднесрочное
планирование
является
частью системы свопинга.
Обычно решение о загрузке процесса в
память принимается в зависимости от степени
многозадачности (например, OS MFT, OS MVT).
Операционные системы
83

84. 2.5. Планирование заданий, процессов и потоков

1. Виды планирования
Диспетчеризация сводится к следующему:
• сохранение контекста текущего потока,
который требуется сменить;
• загрузка контекста нового потока, выбранного
в результате планирования;
• запуск нового потока на выполнение.
Операционные системы
84

85.

Схема планирования с учетом очередей заданий (процессов)
Долгосрочное планирование
Новый
Вызов ОС
Диспетчеризация
(краткосрочное планирование)
Готовый /
Приостановленный
Активация
Готовый
в ОП
Выполняющийся
в ОП
Завершающийся
Освобождение
Диск
Приостановка
Тайм-аут (таймер)
Среднесрочное
планирование
Наступление
события
Наступление
события
Ожидание события
(прерывание вводавывода, сообщение)
Активация
Блокированный /
Приостановленный
Диск
Блокированный
в ОП
Приостановка
С в о п и н г
Операционные системы
85

86.

Долгосрочное
планирование
Тайм-аут
Очередь готовых
заданий
ОП
Интерактивные
пользователи
Пакетные
задания
ЦП
Выход
Очередь готовых
приостановленных заданий
Диск
Среднесрочное
планирование
Очередь заблокированных
приостановленных заданий
Среднесрочное
планирование
Диск
Очередь
заблокированных заданий
Событие
Ожидание события
ОП
Операционные системы
86

87. Граф состояния потока

В мультипрограммной системе поток (процесс, если
операционная система работает только с процессами)
может находиться в одном из трех основных состояний:
• выполнение - активное состояние потока, во время
которого поток обладает всеми необходимыми
ресурсами
и
непосредственно
выполняется
процессором;
Операционные системы
87

88. Граф состояния потока

•ожидание - пассивное состояние потока, находясь в
котором поток заблокирован по своим внутренним
причинам (ждет осуществления некоторого события,
например
завершения
операции
ввода-вывода,
получения сообщения от другого потока или
освобождения какого-либо необходимого ему ресурса);
• готовность - также пассивное состояние потока, но в
этом случае поток заблокирован в связи с внешним по
отношению к нему обстоятельством (имеет все
требуемые ресурсы, готов выполняться, но процессор
занят выполнением другого потока).
Операционные системы
88

89. Граф состояния потока

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

90. Типичный граф состояния потока

Поток завершен
или ошибка
ВЫПОЛНЕНИЕ
Поток
выбран на
выполнение
Поток вытеснен
(исчерпал квант)
ГОТОВНОСТЬ
Вновь
созданный
поток
Поток ожидает
завершения вводавывода или другого
события
ОЖИДАНИЕ
Ввод-вывод
завершен (событие
произошло)
Операционные системы
90

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

1. Невытесняющие (non-preemptive)
планирование распределяется между ОС и прикладными
программами: активный поток сам решает, когда ему отдать
управление ОС, чтобы та выбрала из очереди готовый к
выполнению поток;
необходимость частых передач управлений ОС, в противном
случае возможна монополизация процессора приложением;
зависания приложений могут привести к краху системы;
более высокая скорость переключения потоков;
2. Вытесняющие (preemptive)
функции планирования сосредоточены исключительно в ОС;
планирование на основе квантования процессорного времени;
планирование на основе приоритетов потоков: статических,
динамических, абсолютных, относительных, смешанных;
Операционные системы
91

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

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

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

Поток,
который
исчерпал
свой
квант,
переводится в состояние готовности и ожидает, когда
ему будет предоставлен новый квант процессорного
времени, а на выполнение в соответствии с
определенным правилом выбирается новый поток
из очереди готовых потоков.
Выше приведенный граф состояний потока,
изображенный соответствует схеме планирования,
приведенной далее.
Операционные системы
93

94. Простейший алгоритм планирования, реализующий состояния потока для типичного графа состояния потоков

Очередь готовых потоков
Новый
Тайм - аут
Процессор
Выход
поток
Ввод-вывод завершен
Ожидание события
Очередь
заблокированных
потоков
Операционные системы
94

95.

Кванты, выделяемые потокам, могут быть
равными или различными (типичное значение
десятки - сотни миллисекунд).
Например, первоначально каждому потоку
назначается достаточно большой квант, а величина
каждого следующего кванта уменьшается до
некоторой заранее заданной величины.
В таком случае преимущество получают
короткие задачи, которые успевают выполняться в
течение первого кванта (второго и т. д.), а
длительные вычисления будут проводиться в
фоновом режиме.
Операционные системы
95

96. Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом

Некоторые потоки, получив квант времени,
используют его не полностью, например, из-за
необходимости выполнить ввод или вывод данных.
В результате может возникнуть ситуация,
когда потоки с интенсивным вводом-выводом
используют только небольшую часть выделенного
им процессорного времени.
Операционные системы
96

97. Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом

Можно создать две очереди потоков: очередь 1
- для потоков, которые пришли в состояние
готовности в результате исчерпания кванта
времени, и очередь 2 - для потоков, у которых
завершилась операция ввода-вывода.
При выборе потока для выполнения сначала
просматривается вторая очередь и, если она пуста,
квант выделяется потоку из первой очереди.
Операционные системы
97

98. Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом

Ожидание события
Процессор
Очередь 2
Новый поток
Очередь 1
Тайм - аут
1. Переключение контекстов потоков связано с потерями процессорного времени.
2. С увеличением времени кванта ухудшается обслуживание пользователей.
3. В алгоритмах, основанных на квантовании, ОС не имеет никаких сведений о
характеристиках решаемых задач.
Операционные системы
98

99. Граф состояния потока

Завершение
Тайм-аут
Выполнение
Запрос вводавывода
tКВ
Очередь готовых
потоков 1
Вновь
созданный
поток
(ошибка)
tКВ
Очередь готовых
потоков 2
Операционные системы
Ожидание
Событие
(завершение
ввода-вывода)
99

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

В основе многих вытесняющих алгоритмов
планирования лежит приоритетное обслуживание.
Оно предполагает наличие у потоков некоторой
изначально известной характеристики - приоритета,
на основании которого определяется порядок
выполнения потоков.
Чем выше приоритет, тем выше привилегии
потока, тем меньше времени поток находится в
очередях.
Приоритет задается числом (целым
дробным, положительным или отрицательным).
Операционные системы
или
100

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

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

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

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

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

Тайм-аут
Ожидание
события
Очередь низшего приоритета
Завершение (ошибка)
Очередь высшего приоритета
Процессор
Назначение приоритета
Новый поток
Тайм-аут
Ожидание
события
Приоритетное переключение с квантованием
Операционные системы
103

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

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

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

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

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

В Windows 2000/2003 (W2K) приоритеты
организованы в виде двух групп, или классов:
реального времени и переменные.
Каждая из групп состоит из 16 уровней
приоритетов.
Потоки, требующие немедленного внимания,
находятся в классе реального времени, который
включает такие функции, как осуществление
коммуникаций и задачи реального времени.
Поскольку W2K использует вытесняющий
планировщик с учетом приоритетов, потоки с
приоритетами
реального
времени
имеют
преимущество по отношению к прочим потокам.
Операционные системы
106

107.

Системные приоритеты
31
30
16
15
Пользоват. приоритеты
Очереди системных
потоков и потоков
псевдореального
времени
Наивысший
8
7
6
Наинизший
Наивысший
Базовый приоритет
Наивысший
Повышенный
Обычный
Пониженный
Наинизший
П
Р
О
Ц
Е
С
С
О
Р
Наинизший
0
-1
Поток обнуления страниц
Пустой поток
Операционные системы
107

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

В классе приоритетов реального времени все
потоки имеют фиксированный приоритет (от 16 до 31),
который никогда не изменяется, и все активные
потоки с определенным уровнем приоритета
располагаются в круговой очереди данного класса (t^20 мс для W2K Professional, 120 мс - для
однопроцессорных серверов).
Операционные системы
108

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

В классе переменных приоритетов поток
начинает работу с базового приоритета процесса,
который может принимать значение от 1 до 15.
Каждый поток, связанный с процессом, имеет
свой базовый приоритет, равный базовому приоритету
процесса, или отличающийся от него не более чем на 2
уровня в большую или меньшую сторону.
После активации потока его динамический
приоритет может колебаться в определенных пределах
- он не может упасть ниже наименьшего базового
приоритета данного класса, т. е. 15. (Для потоков с
приоритетом 16 и выше никогда не делается никаких
изменений приоритетов.)
Операционные системы
109

110.

Изменение базового приоритета потока
Увеличение приоритета
+ 1 – завершение ввода-вывода по диску;
+ 2 – для последовательной линии;
+ 6 – клавиатура;
+ 8 – звуковая карта;
+ 2 – снимается блокировка по семафору (для потока переднего плана);
+ 1 - снимается блокировка по семафору (для потока непереднего плана);
приоритет 15 на 2 кванта процессора, если готовый к выполнению поток
простаивает более некоторого директивного времени.
Уменьшение приоритета
-1 – если полностью использован квант времени процессора (многократно,
вплоть до базового приоритета).
Последняя модификация алгоритма планирования W2K заключается в том, что
когда окно становится окном переднего плана, все его потоки получают более
длительные кванты времени (величина прибавки хранится в системном реестре).
Операционные системы
110

111.

Работоспособные процессы (потоки)
Переключение
Выбор для
выполнения
Резервный
(3)
Инициализация (0)
Вытеснение
Готовый (1)
Ресурсов
достаточно
Транзит (6)
Снятие блокировки /
возобновление.
Ресурсов достаточно
Выполняющийся
(2)
Блокировка /
Приостановка
Ожидание
(5)
Снятие блокировки. Ресурсов
недостаточно
Неработоспособные
Операционные
системы
Завершение
Завершенный
(4)
35
111
процессы (потоки)

112. 2.6. Взаимодействие и синхронизация процессов и потоков 2.6.1. Проблемы взаимодействия и синхронизации

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

113. 2.6. Взаимодействие и синхронизация процессов и потоков 2.6.1. Проблемы взаимодействия и синхронизации

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

114. 2.6.2. Конкуренция процессов в борьбе за ресурсы

Конкуренция – ситуация, когда два или более процессов требуют доступ к одному
и тому же ресурсу (принтеру, файлу и т.п.), называемому критическим
(неразделяемый ресурс). Часть программы, использующая критический ресурс,
называется критической секцией.
Процесс А попадает в
критическую область
Процесс А
Процесс А покидает
критическую область
T
Процесс В пытается
попасть в
критическую область
Процесс В
Процесс В попадает в
критическую область
Процесс В покидает
критическую область
T
Процесс В блокирован
T1
T4
T2
T3
Необходимость взаимоисключений:
1. Процессы не должны одновременно находиться в критических областях.
2. В программе не должно быть предположений о скорости или количестве процессов.
3. Процесс, находящийся вне критической области, не может блокировать другие процессы.
4. Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.
Операционные системы
114

115. Взаимоблокировки (тупики, deadlock)

Группа процессов находится в тупиковой ситуации, если каждый
процесс из группы ожидает события, которое может вызвать только другой
процесс из этой же группы
Процесс
P2
P1
Ресурс
R1
R2
Исходное
распределение
ресурсов
P1
P2
P1
R1
R1
R2
R2
P2
Тупиковая ситуация
Операционные системы
115

116. Взаимоблокировки (тупики, deadlock)

ОС выделяет ресурс R1 процессу Р2, а ресурс
R2 - процессу Р1.
В результате каждый процесс
получения одного из двух ресурсов.
ожидает
При этом ни один из них не освобождает уже
имеющийся ресурс, ожидая получения второго
ресурса для выполнения функций, требующих
наличия двух ресурсов.
В результате процессы оказываются взаимно
заблокированными.
Операционные системы
116

117. Взаимоблокировки (тупики, deadlock)

Удобно моделировать условия возникновения
тупиков, используя направленные графы.
Графы имеют 2 вида узлов: процессы-кружочки
и ресурсы-квадратики.
Ребро, направленное от квадрата (ресурса) к
кружку (процессу), означает, что ресурс был
запрошен, получен и используется.
Ребро, направленное от процесса (кружка) к
ресурсу (квадрату), означает, что процесс в данный
момент заблокирован и находится в состоянии
ожидания доступа к этому ресурсу. Цикл в графе
означает наличие взаимной блокировки процессов.
Операционные системы
117

118. Проблема “голодание”

R
R
P1
Активный
P2
P3
Блокированные
P1
P2
Блокированные
R
P1
Активный
P3
Активный
R
P2
P3
Блокированные
P1
P2
Блокированные
Операционные системы
P3
Активный
118

119. Проблема “голодание”

Пусть Р1 обладает ресурсом, а Р2 и РЗ
приостановлены в ожидании освобождения ресурса
R.
После выхода Р1 из критического раздела
доступ к ресурсу будет получен одним из процессов
Р2 или РЗ.
Пусть ОС предоставила доступ к ресурсу
процессу РЗ.
Пока он работает с ресурсом, доступ к ресурсу
вновь требуется процессу Р1.
Операционные системы
119

120. Проблема “голодание”

В результате по освобождении ресурса R
процессом РЗ может оказаться, что ОС вновь
предоставит доступ к ресурсу процессу Р1.
Тем временем процессу РЗ вновь требуется
доступ к ресурсу R.
Теоретически возможна ситуация, в которой
процесс Р2 никогда не получит доступа к требуемому
ему ресурсу, несмотря на то что никакой взаимной
блокировки в данном случае нет.
Операционные системы
120

121. 2.6.3. Сотрудничество с использованием разделения

Процессы, взаимодействующие с другими процессами без наличия явной
информации о друг друге, обращаются к разделяемым переменным, к
совместно используемым файлам или базам данных.
Проблемы: взаимоисключение, взаимоблокировка, голодание.
Дополнительно: синхронизация процессов для обеспечения
согласованности данных
Пример: пусть должно выполняться a = b при начальном значении a = b = 1
1-й вариант: процессы выполняются последовательно
P1: a = a + 1; b = b + 1;
P2: b = 2 * b; a = 2 * a;
2-й вариант: процессы прерывают друг друга
P1: a = a + 1; прерывание; P2: b = 2 * b; прерывание;
P1: b = b + 1; прерывание; P2: a = 2 * a;
Согласование нарушено: a = 4, b = 3
Ситуации, в которых два или более процессов обрабатывают
разделяемые данные (файлы) и конечный результат зависит
от скоростей процессов (потоков), называются гонками.
Операционные системы
121

122. 2.6.3. Сотрудничество с использованием разделения

Набор
процессов
называется
детерминированным,
если
всякий
раз
при
псевдопараллельном исполнении для одного и того же
набора входных данных он дает одинаковые выходные
данные.В противном случае он недетерминирован.
Детерминированный набор процессов можно
безбоязненно выполнять в режиме разделения
времени. Для недетерминированного набора такое
исполнение нежелательно.
Про недетерминированный набор программ
говорят, что он имеет race condition (состояние гонки,
состояние состязания).
Операционные системы
122

123. 2.6.3. Сотрудничество с использованием разделения

Задачу упорядоченного доступа к разделяемым
данным (устранение race condition) в том случае, если
нам не важна его очередность, можно решить, если
обеспечить каждому процессу эксклюзивное право
доступа к этим данным.
Каждый процесс, обращающийся к разделяемым
ресурсам, исключает для всех других процессов
возможность одновременного с ним общения с этими
ресурсами,
если
это
может
привести
к
недетерминированному поведению набора процессов.
Такой прием называется взаимоисключением (mutual
exclusion).
Операционные системы
123

124. 2.6.4. Сотрудничество с использованием связи

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

125. 2.6.4. Сотрудничество с использованием связи

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

126. 2.6.4. Методы взаимоисключений

1. Запрещение прерываний при входе в критическую область и разрешение
прерываний после выхода из критической области. Достоинства:
простота реализации. Недостатки: монополизация процессора,
возможный крах ОС при сбое процесса, невозможность использования в
многопроцессорных системах, так как прерывание относится к одному
процессору
2. Глобальные блокирующие переменные (программный подход)
Попытка доступа к
Нет, занят
разделяемому ресурсу D
Неделимая (атомарная)
операция “проверкаустановка”
Команды TC, BTR, BTS
процессора Pentium
(анализ и присвоение
значения логической
переменной)
F(D)=1?
Да, свободен
Занять ресурс
F(D)=0
Критическая секция
(работа с ресурсом D)
Освободить ресурс F(D)=1
Операционные системы
Недостатки: необходимость
постоянного опроса другими
потоками, требующими тот
же ресурс, блокирующей
переменной;
дополнительные затраты
процессорного времени,
применимы для потоков
одного процесса
126

127. 3.Использование системных функций входа в критическую секцию

Попытка доступа
к разделяемому
ресурсу D
Нет
F(D)=1?
Перевести данный
поток в ожидание D
Да
Установить блокирующую
переменную в состояние
“Занято”, F(D) = 0
Системный вызов
EnterCriticalSection()
Критическая
секция (работа с
ресурсом D)
Установить блокирующую
переменную в состояние
“Свободно”, F(D) = 1
Системный вызов
LeaveCriticalSection()
Перевести поток, ожидающий
ресурс D, в состояние Готовность
Операционные системы
Достоинство:
исключается
потеря времени
процессора на
циклическую
проверку
освобождения
занятого ресурса.
Недостаток:
растут накладные
расходы ОС по
реализации
функции входа в
критическую
секцию и выхода
из нее
127

128. 4. Семафоры Дейкстры (Dijkstra)

Семафор: переменная S, примитивы P (proberen – проверка (==0);
уменьшение, down) и V (verhogen – увеличение, up)
V(S) – переменная S увеличивается на 1 единым действием. Выборка,
наращивание и запоминание не могут быть прерваны. К переменной S нет
доступа во время выполнения этой операции.
P(S) – переменная S уменьшается на 1, если это возможно, оставаясь в
области неотрицательных значений. Если S уменьшить невозможно, поток,
выполняющий операцию P, ждет, пока это уменьшение станет возможным
(Пока S==0 поток блокируется). Операция P неделима.
В частном случае семафор S может принимать двоичные значения 0 и 1,
превращаясь в блокирующую переменную (двоичный семафор – мьютекс).
Операция P заключает в себе потенциальную возможность перехода процесса,
который ее выполняет, в состояние ожидания (если S = 0).
Операция V может при некоторых обстоятельствах активизировать процесс,
приостановленный операцией P.
Для хранения процессов, ожидающих семафоры, используется очередь,
работающая по принципу FIFO (Первым зашел – первым вышел).
Операционные системы
128

129.

Начальные значения
семафоров
e = N; f = 0
P(e)
P(f)
e>0
f>0
f
N
Работа с
разделяемым
ресурсом
(e=e-1)
Работа с
разделяемым
ресурсом
(f=f-1)
e
V(f) ( f=f+1)
Потоки-писатели
V(e) (e=e+1)
Буферный пул
e – пустые буферы,
f – занятые буферы
Операционные системы
Потоки-читатели
129

130. 5. Мониторы Хоара и Хансена

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

131. Описание структуры и функциональной схемы монитора

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

132. Абстрактное описание структуры монитора:

monitor monitor_name
{
Описание глобальных переменных;
void m1(…){
…………
}
void m2(…){
…………
}
…………….
void mn(…){
…………
}
{
блок инициализации внутренних переменных
}
}
Операционные системы
132

133. Абстрактное описание структуры монитора:

Здесь функции m1, m2, … mn представляют собой процедуры (функции
члены) монитора, а блок инициализации глобальных (внутренних)
переменных содержит операции, которые выполняются только один
раз: при создании монитора или при самом первом вызове какой-либо
процедуры до ее выполнения.
Операционные системы
133

134. Описание функционирования монитора

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

135. Описание функционирования монитора

Чтобы гарантировать, что процесс, находящийся в ожидании
некоторого ресурса, со временем получит этот ресурс, Хоар предложил,
чтобы ожидающий процесс имеет более высокий приоритет, чем новый
процесс, пытающийся войти в монитор. Это исключает голодание.
Несколько позже Хансен предложил другой подход: разбудивший
процесс покидает монитор немедленно после исполнения операции
SIGNAL.
Операционные системы
135

136. Пример монитора Хоара

monitor Resourse
{
condition free; // условие - свободный
boolean busy ; // занят
void REQUEST() // запрос
{
if(busy) WAIT (free);
busy==true;
TakeOff();// выдать ресурс
}
void RELEASE()
{
TakeOn() ; // взять ресурс
busy=false;
SIGNAL ( free );
}
{
busy=false;
}
}
Операционные системы
136

137. Пример монитора Хоара

Единственный ресурс динамически запрашивается и освобождается
процессами, которые обращаются к процедурам REQUEST (запрос) и
RELEASE (освободить). Если процесс обращается к процедуре
REQUEST в тот момент, когда ресурс используется, значение
переменной busy (занято) будет равно true, и процедура REQUEST
выполнит операцию монитора WAIT(free). Эта операция блокирует не
процедуру REQUEST, а обратившийся к ней процесс, который
помещается в конец очереди процессов, ожидающих, пока не будет
выполнено условие free (свободно).
Когда процесс, использующий ресурс, обращается к процедуре
RELEASE, операция монитора SIGNAL деблокирует процесс,
находящийся в начале очереди, не позволяя исполняться никакой
другой процедуре внутри того же монитора. Этот деблокированный
процесс будет готов возобновить исполнение процедуры REQUEST сразу
же после операции WAIT(free), которая его и блокировала. Если
операция SIGNAL(free) выполняется в то время, когда нет процесса,
ожидающего условия free, то никаких действий не выполняется.
Операционные системы
137

138. Реализация мониторов

Мониторы представляют собой особые конструкции языка
программирования.
Компилятор
вызовы
процедур
монитора
обрабатывает специальным образом, добавляя к ним пролог и эпилог,
реализующие механизм взаимоисключения.
Мониторы встречаются в таких языках программирования, как
параллельный Евклид, параллельный Паскаль, Java и т.д.
Операционные системы
138

139. Решение задачи производитель-потребитель с помощью мониторов:

monitor ProducerConsumer
{
condition full, empty;
int count;
void put()
{
if(count==N) wait(full);
put_item();
count++;
if(count==1) signal(empty);
}
Операционные системы
139

140. Решение задачи производитель-потребитель с помощью мониторов:

void get()
{
if(count==0) wait(empty);
get_item();
count--;
if(count==N-1) signal(full);
}
{
count=0;
}
}
Операционные системы
140

141. Решение задачи производитель-потребитель с помощью мониторов:

Producer:
while(1)
{
produce_item();
ProducerConsumer.put();
}
Consumer:
while(1)
{
ProducerConsumer.get();
consume_item();
}
Операционные системы
141

142. 2.6.5. Взаимоблокировки (тупики)

Условия возникновения взаимоблокировки (тупиковой) ситуации:
1. Взаимное исключение. Каждый ресурс в данный момент или отдан ровно одному
процессу, или недоступен.
2. Условие удержания и ожидания. Процессы, в данный момент удерживающие
полученные ранее ресурсы, могут запрашивать новые ресурсы.
3. Отсутствие принудительной выгрузки ресурсов. У процесса нельзя забрать
принудительно ранее полученные ресурсы.
4. Условие циклического ожидания. Существует круговая последовательность из
двух и более процессов, каждый из которых ждет доступа к ресурсу,
удерживаемому следующим членом последовательности.
Стратегии борьбы с взаимоблокировками:
1. Пренебрежение проблемой в целом.
2. Обнаружение и устранение взаимоблокировок (восстановление).
3. Недопущение тупиковых ситуаций с помощью аккуратного распределения
ресурсов.
4. Предотвращать с помощью структурного опровержения одного из четырех
условий, необходимых для взаимоблокировки
Операционные системы
142

143. Методы обнаружения взаимоблокировок

1. В системе один ресурс каждого типа.
Например, пусть система из семи процессов (A, B, C, D, E, F, G) и шести
ресурсов
(R, S, T, V, W, U) в некоторый момент соответствует
следующему списку:
Процесс A занимает ресурс R и хочет получить ресурс S.
Процесс B ничего не использует, но хочет получить ресурс T.
Процесс C ничего не использует, но хочет получить ресурс S.
Процесс D занимает ресурс U и хочет получить ресурсы S и T.
Процесс E занимает ресурс T и хочет получить ресурс V.
Процесс F занимает ресурс W и хочет получить ресурс S.
Процесс G занимает ресурс V и хочет получить ресурс U.
ВОПРОС: Заблокирована ли эта система и если да, то какие процессы в этом
участвуют?
ОТВЕТ МОЖНО ПОЛУЧИТЬ, ПОСТРОИВ ГРАФ РЕСУРСОВ И ПРОЦЕССОВ.
Операционные системы
143

144.

Граф ресурсов и процессов
R
C
A
B
S
D
F
U
W
T
E
цикл
V
G
Операционные системы
144

145. 2. В системе несколько ресурсов каждого типа.

P = {P1, P2, . . . , Pn} – множество процессов, n – число процессов;
E = {E1, E 2, . . . , Em } – множество ресурсов, m – число типов ресурсов;
A = {A1, A2, . . . , Am} – вектор свободных ресурсов; AJ <= EJ, j = 1, m;
C = {cI J | i = 1, n; j = 1, m } – матрица текущего распределения ресурсов,
сij – количество ресурсов класса j, занятого процессом Pi;
R = {ri j | i = 1, n; j = 1, m } – матрица запрашиваемых ресурсов, rij –
количество ресурсов класса j, запрашиваемого процессом Pi.
Существующие ресурсы
Доступные ресурсы
E = {E1, E 2, . . . , Em }
A = {A1, A2, . . . , Am}
c11
c12 . . . .
c1m
r11
r12 . . . .
r1m
c21
c21 . . . .
c2m
r21
r22
....
r2m
.
.
.
....
.
cnm
rn1
.
.
cn1
cn2
....
rn2 . . . .
Rnm
n
ΣC
ij
+ Aj = Ej , j = 1, m
Операционные
I=1
системы
145

146. Алгоритм обнаружения тупиков

Основан на сравнении векторов ресурсов. В исходном
состоянии все процессы не маркированы (не отмечены). По
мере реализации алгоритма на процессы будет ставиться
отметка, обозначающая, что они могут закончить свою работу,
т. е. не находятся в тупике. После завершения алгоритма
любой немаркированный процесс находится в тупиковой
ситуации.
Алгоритм
1. Ищется процесс Pi , для которого i – я строка матрицы R меньше вектора
A,
т. е.
Ri <= Aj или ri j <= Aj , j = 1, m.
2. Если такой процесс найден, он маркируется, и далее прибавляется I - я
строка матрицы С к вектору A, т.е. Aj := Aj + сi j , j = 1, m.
Возврат к шагу 1.
3. Если таких процессов не существует, работа алгоритма заканчивается.
Если есть немаркированные процессы, то они попали в тупик.
Операционные системы
146

147. Методы устранения тупиков

1. Принудительная выгрузка ресурсов. Изъятие ресурса у процесса, передача его
другому процессу, а затем возврат ресурса таким образом, что исходный процесс
этого “ не замечает” (сложно и чаще всего невозможно).
2. Восстановление через “откат”. Процессы периодически создают контрольные точки,
позволяющие запустить процесс с предыстории. При возникновении тупика процесс,
занимающий необходимый ресурс “откатывается” к контрольной точке, после
которой он получил ресурс. Если возобновленный процесс вновь попытается
получить данный ресурс, он переводится в режим ожидания освобождения этого
ресурса.
3. Восстановление путем уничтожения процессов.
Недопущение тупиков путем безопасного распределения
ресурсов. Подобные алгоритмы базируются на концепции
безопасных состояний. Например, Дейкстрой был разработан
алгоритм
планирования,
позволяющий
избегать
взаимоблокировок (алгоритм банкира).
Операционные системы
147

148. 2.6.6. Синхронизирующие объекты ОС

Для синхронизации потоков, принадлежащих разным процессам, ОС
должна предоставлять потокам системные объекты синхронизации.
К таким объектам относятся события (event), мьютексы (mutex – mutual
exclusion – взаимное исключение), системные семафоры и др.
Объект-событие используется для того, чтобы оповестить потоки о том, что
некоторые действия завершены.
Мьютекс (простейший двоичный семафор) используется для управления
взаимным исключением доступа к совместно используемым данным.
Семафоры используются для оповещения свершения последовательности
событий.
Для синхронизации используются также “обычные ” объекты ОС:
файлы, процессы, потоки
Все объекты синхронизации могут находиться в сигнальном и несигнальном
(свободном) состоянии. Поток с помощью системного вызова WAIT(X) может
синхронизировать свое выполнение с объектом синхронизации X. По этому вызову
поток переводится ОС в состояние ожидания до тех пор, пока объект X не перейдет в
сигнальное состояние. С помощью системного вызова SET(X) поток может перевести
объект X в сигнальное состояние.
Операционные системы
148

149. 2.6.6. Синхронизирующие объекты ОС

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

150. 2.6.6. Синхронизирующие объекты ОС

Синхронные сигналы чаще всего приходят от
системы прерывания процессора и свидетельствуют о
действиях процесса, блокируемых аппаратурой,
например деление на нуль, ошибка адресации,
нарушение защиты памяти и т. д.
Примером асинхронного
сигнал с терминала.
сигнала
является
Обработка сигналов аналогична
аппаратных прерываний ввода-вывода.
обработке
Операционные системы
150

151. 2.6.7. Средства взаимодействия ОС между процессами

Конвейеры
Программный канал связи (pipe), или, как его иногда
называют, конвейер, является средством, с помощью которого
процессы могут обмениваться данными между собой на основе
механизма ввода-вывода файлов (в UNIX).
Когда процесс А хочет отправить данные
процессу В, он пишет их в канал, как если бы это был
выходной файл (псевдофайл).
Процесс В читает данные из канала, как если
бы он был входным файлом (псевдофайл).
Подобное
средство
взаимодействия
используется в операционной системе UNIX.
Операционные системы
151

152. Конвейеры

Операции записи и чтения осуществляются потоком
байтов, как это принято в UNIX-системах.
Функции, с помощью которых выполняется запись в
канал и чтение из него, являются теми же самыми, что и при
работе с файлами.
Канал представляет собой поток данных между двумя (или
более) процессами.
На самом деле конвейеры не являются файлами на диске,
а представляют собой буферную память, работающую по
принципу FIFO, то есть по принципу обычной очереди.
Операционные системы
152

153. Конвейеры

Конвейер имеет определенный размер, который не может
превышать 64 Кбайт и работает циклически, как реализация
очереди на массивах, когда имеются указатели первого (head –
голова) и последнего (tail – хвост) элементов очереди в
массиве, которые перемещаются циклически по массиву.
Операционные системы
153

154. Конвейеры

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

155. Конвейеры

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

156. Конвейеры

Как информационная структура конвейер описывается
идентификатором, размером и двумя указателями. Конвейеры
представляют собой системный ресурс.
Чтобы начать работу с конвейером, процесс сначала
должен заказать его у операционной системы и получить в
свое распоряжение. Процессы, знающие идентификатор
конвейера, могут через него обмениваться данными.
Операционные системы
156

157. Конвейеры

Основные системные запросы для работы с конвейерами
на примере API OS/2:
Функция создания конвейера:
DosCreatePipe (&ReadHandle, &WriteHandle, PipeSize);
Здесь ReadHandle — дескриптор чтения из конвейера, WriteHandle —
дескриптор записи в конвейер, PipeSize — размер конвейера.
Функция чтения из конвейера:
DosRead (&ReadHandle, (PVOID)&Inform, sizeof(Inform). &BytesRead);
Здесь ReadHandle — дескриптор чтения из конвейера, Inform —
переменная любого типа, sizeof(Inform) — размер переменной Inform,
BytesRead — количество прочитанных байтов. Данная функция при
обращении к пустому конвейеру будет ожидать, пока в нем не появится
информация для чтения.
Функция записи в конвейер:
DosWrite (&WriteHandle. (PVOID)&Inform, sizeofCInform),&SBytesWrite);
Здесь WriteHandle — дескриптор записи в конвейер, BytesWrite —
количество записанных байтов.
Операционные системы
157

158.

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

159.

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

160.

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

161.

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

162.

Очереди сообщений
Во время чтения из очереди задачаприемник пользуется следующей информацией:
• идентификатор процесса (Process Identifier, PID),
который передал сообщение;
• адрес и длина переданного сообщения;
• признак необходимости ждать, если очередь
пуста;
• приоритет переданного сообщения;
• номер
освобождаемого
семафора,
когда
сообщение передается в очередь.
Операционные системы
162

163.

Очереди сообщений
Перечень основных функций, управляющих
работой очереди (без подробного описания передаваемых
параметров, поскольку в различных ОС обращения к
этим функциям могут существенно различаться):
• CreateQueue — создание новой очереди;
• OpenQueue — открытие существующей очереди;
• ReadQueue — чтение и удаление сообщения из очереди;
• PeekQueue — чтение сообщения без его последующего
удаления из очереди;
• WriteQueue — добавление сообщения в очередь;
• CloseQueue — завершение использования очереди;
• PurgeQueue — удаление из очереди всех сообщений;
• QueryQueue — определение числа элементов в очереди.
Операционные системы
163

164.

2.6.7. Средства взаимодействия ОС между
процессами
Почтовые ящики
Почтовые ящики, используемые в Windows
2000, в некоторых аспектах подобны каналам, однако,
в отличие от каналов, являются однонаправленными.
Они позволяют отправляющему процессу
использовать
широковещание
для
рассылки
сообщений сразу многим получателям.
Для прямой и непрямой адресации достаточно
двух примитивов, чтобы описать передачу сообщений
по линии связи - send и receive.
Операционные системы
164

165.

Почтовые ящики
В случае прямой адресации их можно
обозначать так:
send(P, message) - послать сообщение message процессу
Р;
receive(Q, message) - получить сообщение message от
процесса Q,.
В случае непрямой адресации мы будем обозначать их
так:
send(A, message) - послать сообщение message в
почтовый ящик А;
receive(A, message) - получить сообщение message из
почтового ящика А.
Операционные системы
165

166.

Почтовые ящики
Примитивы send и receive уже имеют скрытый
от наших глаз механизм взаимоисключения.
Более того, в большинстве систем они уже
имеют и скрытый механизм блокировки при чтении
из пустого буфера и при записи в полностью
заполненный буфер.
Реализация решения задачи producer-consumer
для таких примитивов становится тривиальной.
Надо отметить, что, несмотря на простоту
использования, передача сообщений в пределах
одного
компьютера
происходит
существенно
медленнее, чем работа с семафорами и мониторами.
Операционные системы
166

167.

2.6.7. Средства взаимодействия ОС между
процессами
Сокеты
Сокеты (ОС Windows 2000) подобны каналам, с
тем
отличием,
что
они
при
нормальном
использовании соединяют процессы на разных
компьютерах.
Например, один процесс пишет в сокет, а другой
на удаленной машине читает из него.
В принципе сокеты можно использовать для
соединения процессов на одной машине, но это
связано с большими накладными расходами.
Операционные системы
167

168.

2.6.7. Средства взаимодействия ОС между
процессами
Вызов удаленной процедуры
Вызов удаленной процедуры (Remote Procedure
Call, RPC) представляет собой способ, которым
процесс А просит процесс В вызвать процедуру в
адресном пространстве процесса В от имени процесса
А и вернуть результат процессу А.
Операционные системы
168

169.

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

170. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Классы прерываний: внешние, внутренние, программные
1. Внешние прерывания – результат действий пользователя, сигналы от
периферийных устройств компьютера и управляемых объектов.
2. Внутренние прерывания – результат появления аварийных ситуаций
при выполнении инструкции программы.
3. Программные прерывания – результат выполнения запланированных
в программе особых инструкций (системный вызов).
Принципы построения систем прерываний:
аппаратная поддержка (контроллер прерываний, контроллер DMA, контроллеры
внешних устройств, шины подключения внешних устройств, средства
микропроцессора);
векторный, опрашиваемый и комбинированный способы прерываний;
приоритетный механизм обслуживания (с абсолютными и относительными
приоритетами);
маскирование прерываний;
диспетчер прерываний и процедуры обслуживания прерываний.
Операционные системы
170

171. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Операционные системы имеют специальные
модули для работы с прерываниями - обработчики
прерываний,
или
процедуры
обслуживания
прерываний (Interrupt Service Routine, ISR).
Аппаратные
прерывания
обрабатываются
драйверами соответствующих внешних устройств,
исключения - специальными модулями ядра, а
программные прерывания - процедурами ОС,
обслуживающими системные вызовы.
Операционные системы
171

172. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Кроме этих моделей в ОС может быть
диспетчер прерываний, координирующий работу
отдельных обработчиков прерываний.
Существуют два основных способа, с помощью
которых шины выполняют прерывания: векторный
(vectored) и опрашиваемый (polled).
В обоих случаях процессору предоставляется
информация об уровне приоритета прерывания на
шине подключения внешних устройств.
Операционные системы
172

173. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
В случае векторных прерываний в процессор
передается информация о начальном адресе
программы обработки прерываний - обработчика
прерывания.
При использовании опрашиваемых прерываний
процессор получает от запросившего прерывания
устройства только информацию об уровне
приоритета прерывания.
С каждым уровнем может быть связано
несколько устройств и соответственно несколько
обработчиков прерываний.
Операционные системы
173

174. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
В
этом
случае
при
возникновении
прерывания процессор вызывает поочередно всех
обработчиков
прерываний
данного
уровня
приоритета, пока один из обработчиков не
подтвердит,
что
прерывание
прошло
от
обслуживаемого им устройства.
Возможен
комбинированный
подход,
сочетающий векторный и опрашиваемый типы
прерываний.
Такой подход реализован в ПК на основе
процессоров Intel Pentium.
Операционные системы
174

175. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Вектор прерываний в процессор Pentium
поставляет контроллер прерываний, который
отображает поступающий от шины сигнал IRQ
(Interrupt Request) на определенный номер вектора.
Вектор прерываний представляет собой число,
указывающее на одну из 256 программ обработки
прерываний, адреса которых хранятся в таблице
обработчиков прерываний.
В том случае, когда к каждой линии IRQ
подключается только одно устройство, процедура
прерываний работает как чисто векторная.
Операционные системы
175

176. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Однако при совместном использовании
одного уровня IRQ несколькими устройствами
обработка прерываний реализуется по схеме
опрашиваемых прерываний, т. е. в данном случае
необходимо выполнить опрос всех устройств,
подключенных к данному уровню IRQ (Interrupt
Request).
Операционные системы
176

177. 2.7. Аппаратно-программные средства поддержки мультипрограммирования

2.7.1. Системы прерываний
Обычно в ОС поддерживается механизм
приоритезации и маскирование прерываний.
Каждый класс прерываний имеет свой уровень
приоритета.
Приоритеты
могут
обслуживаться
как
относительные и как абсолютные.
Маскирование
позволяет
запретить
прерывания любого приоритета на некоторый
промежуток времени.
Операционные системы
177

178.

Последовательность действий при обработке прерываний
1. Первичное аппаратное распознавание типа прерывание. Если прерывания запрещены,
продолжается текущая программа. В противном случае вызывается диспетчер
прерываний и в зависимости от поступившей в процессор информации (вектор
прерывания, приоритет и др.) производится вызов процедуры обработки прерывания.
2. Сохраняется некоторая часть контекста прерванного потока, которая позволит
возобновить его исполнение после обработки прерывания (обычно слово состояния
процессора – регистр EFLAGS в Pentium, регистры общего назначения). Может быть
сохранен и полный контекст, если ОС обслуживает прерывание со сменой процесса.
3. В счетчик команд загружается адрес процедуры обработки прерывания и
устанавливается новое PSW, которое определяет привилегированный режим работы
процессора при обработке прерывания.
4. Маскированием прерываний временно запрещаются прерывания данного типа, чтобы
не образовалась очередь вложенных друг в друга потоков одной и той же процедуры.
5. После обработки прерывания ядром операционной системы, прерванный контекст
восстанавливается (частично аппаратно – PSW, содержимое счетчика команд, частично
программно – извлечение данных из стека), снимается обработка прерываний данного
типа и работа потока возобновляется с прерванного места.
Операционные системы
178

179. 2.7.2. Системные вызовы

Системный вызов позволяет приложению обратиться к ОС с просьбой выполнить то
или иное действие, оформленное как процедура кодового сегмента ОС.
Реализация системных вызовов должна удовлетворять следующим требованиям:
o обеспечивать переключение в привилегированный режим;
o обладать высокой скоростью вызова процедур ОС;
o обеспечивать по возможности единообразное обращение к системным вызовам для
всех аппаратных платформ, на которых работает ОС;
o допускать простое расширение системных вызовов;
o обеспечивать контроль со стороны ОС за корректным использованием системных
вызовов.
Возможные схемы обслуживания системных вызовов:
1. Децентрализованная –за каждым системным вызовом закреплен свой
вектор прерываний. Достоинство – высокая скорость обработки системных
вызовов, недостаток – разрастание таблицы векторов прерываний.
2. Централизованная – с помощью диспетчера системных вызовов. При любом
системном вызове приложение выполняет программное прерывание с
определенным и единственным номером.
Операционные системы
179

180.

С
и
с
т
е
м
н
ы
й
в
ы
з
о
в
Вектор
80h
Linux
RQ=21h
Таблица
прерываний
системы
Виртуальное адресное
пространство
Диспетчер
системных вызовов
Адрес диспетчера
системных
вызовов
Адрес процедуры 21h
Адрес процедуры 22h
Процедура обработки
системного вызова 21h
Адрес процедуры 23h
Процедура обработки
системного вызова 22h
INT 2Eh
Pentium
Процедура обработки
системного вызова 23h
Централизованная схема обработки системных вызовов
Операционные системы
180

181. Централизованная схема обработки системных вызовов

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

182. Централизованная схема обработки системных вызовов

Любой системный вызов приводит к запуску
диспетчера системных вызовов, который представляет
собой простую программу, сохраняющую содержимое
режимов в системном стеке (поскольку в результате
программного прерывания процессор переходит в
привилегированный режим) и проверяющую попадает
ли запрошенный номер вызова в поддерживаемый ОС
диапазон.
Если все условия соблюдены, диспетчер передает
управление процедуре ОС, адрес которой задан в
таблице адресов системных вызовов.
Операционные системы
182

183. Централизованная схема обработки системных вызовов

Процедура реализации системного вызова
извлекает из системного стека аргументы и выполняет
заданное действие.
После завершения работы системного вызова
управление возвращается диспетчеру, при этом он
получает код завершения этого вызова.
Диспетчер
восстанавливает
регистры
процессора, помещает в определенный регистр код
возврата и выполняет инструкцию возврата из
прерывания,
которая
восстанавливает
непривилегированный режим работы процессора.
Операционные системы
183

184. Централизованная схема обработки системных вызовов

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

185. Централизованная схема обработки системных вызовов

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