Слайд 1Тема 2. Организация вычислительного процесса.
2.1. Концепция процессов и потоков. Задания,
процессы, потоки (нити), волокна
2.2. Мультипрограммирование. Формы многопрограммной работы
2.3. Управление процессами
и потоками
2.4. Создание процессов и потоков. Модели процессов и потоков
2.5. Планирование процессов и потоков
2.6. Взаимодействие и синхронизация процессов и потоков
2.7. Аппаратно-программные средства поддержки мультипрограммирования
Слайд 22.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Мультипрограммирование (многозадачность, multitasking) - это такой способ организации вычислительного процесса,
при котором на одном процессоре попеременно выполняются несколько программ.
Слайд 32.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Чтобы поддерживать мультипрограммирование, ОС должна определить для себя внутренние единицы
работы, между которыми будет разделяться процессор и другие ресурсы компьютера.
В ОС пакетной обработки машин второго и третьего поколения единицей работы было задание.
Слайд 42.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
В настоящее время в большинстве операционных систем определены два типа
единиц работы: более крупная единица - процесс или задача, и менее крупная - поток или нить.
Процесс выполняется в форме одного или нескольких потоков.
Слайд 52.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Процесс – это выполняемая программа, включая текущие значения счетчика команд,
регистров и переменных.
С каждым процессом связывается его адресное пространство, содержащее саму программу, данные к ней и ее стек.
Слайд 62.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Все функционирующее на компьютере программное обеспечение, включая и операционную систему,
можно представить набором процессов.
Слайд 72.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Для решения задачи рационального управления процессами и ресурсами компьютера операционная
система должна располагать информацией о текущем состоянии каждого процесса и ресурса. Универсальный подход к предоставлению такой информации заключается в создании и поддержке таблиц с информацией по каждому объекту управления.
Слайд 82.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
В некоторых современных ОС, например в Windows 2000/2003 вновь
вернулись к такой единице работы, как задание (Job).
Задание в Windows представляет собой набор из одного или нескольких процессов, управляемых как единое целое.
Слайд 92.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
В частности, с каждым заданием ассоциированы квоты и лимиты
ресурсов, хранящиеся в соответствующем объекте задания.
Слайд 102.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Квоты включают такие пункты, как максимальное количество процессов, суммарное время
центрального процессора, доступное для каждого процесса в отдельности и для всех процессов вместе, а также максимальное количество используемой памяти для процесса и всего задания.
Слайд 112.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Задания также могут ограничивать свои процессы в вопросах безопасности,
например, запрещать или получать права администратора даже при наличии правильного пароля.
Слайд 12Операционные системы
2.1. Концепция процессов и потоков. Задания, процессы, потоки (нити),
волокна
Ресурсы системы
Управляющие таблицы ОС
Образ процесса
Процесс 1
Процесс N
Память
Устройства
Файлы
Процессы
Процесс 1
Процесс 3
Процесс 2
Процесс
N
Процессор
Первичные таблицы процессов
Таблицы памяти
Таблицы ввода-вывода
Таблицы файлов
Слайд 132.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Процессы рассматриваются операционной системой как заявки или контейнеры для
всех видов ресурсов, кроме одного - процессорного времени.
Этот важнейший ресурс распределяется операционной системой между другими единицами работы - потоками.
Слайд 142.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Каждый процесс начинается с одного потока, но новые потоки
могут создаваться (порождаться) процессом динамически.
В простейшем случае процесс состоит из одного потока, и именно таким образом трактовалось понятие «процесс» до середины 80-х годов (например, в ранних версиях UNIX).
Слайд 152.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
В некоторых современных ОС такое положение сохранилось, т. е.
понятие «поток» полностью поглощается понятием «процесс».
Как правило, поток работает в пользовательском режиме, но когда он обращается к системному вызову, то переключается в режим ядра.
Слайд 162.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
После завершения системного вызова поток продолжает выполняться в режиме
пользователя.
У каждого потока есть два стека: один используется в режиме ядра, другой - в режиме пользователя.
Слайд 172.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
У каждого потока есть состояние (текущие значения всех объектов
потока) идентификатор и два стека, контекст (в котором сохраняются его регистры, когда он не работает), приватная область для его локальных переменных, а также может быть собственный маркер доступа (информация о защите).
Слайд 182.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Когда поток завершает свою работу, он может прекратить свое
существование. Процесс завершается, когда прекратит существование последний активный поток.
Слайд 19Операционные системы
Взаимосвязь между заданиями, процессами и потоками
Процессы
T
T
P
T
Задание
Стек в режиме пользователя
Потоки
Таблица
процесса
Таблица процесса
Маркеры доступа
Стеки потоков в режиме ядра
T
P
Слайд 202.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
Для предоставления сильно облегченного псевдопараллелизма в Windows 2000
используются волокна (Fiber), подобные потокам, но планируемые в пространстве пользователя создавшей их программой.
Слайд 212.1. Концепция процессов и потоков. Задания, процессы, потоки (нити), волокна
Основные
понятия
У каждого потока может быть несколько волокон, с
той разницей, что когда волокно логически блокируется, оно помещается в очередь блокированных волокон, после чего для работы выбирается другое волокно в контексте того же потока. При этом ОС «не знает» о смене волокон, так как все тот же поток продолжает работу.
Слайд 22Операционные системы
Задание (JOB)
Объекты
Процесс 2
Процесс N
Процесс 1
Поток 2
Thread 2
Поток k
Thread k
Поток
1
Thread 1
Волокна (Fibers)
Слайд 23Операционные системы
2.2. Мультипрограммирование. Формы многопрограммной работы
Системы пакетной обработки предназначаются для
решения задач в основном вычислительного характера, не требующих быстрого получения
результатов. Максимальная пропускная способность компьютера достигается в этом случае минимизацией простоев его устройств и, прежде всего, процессора.
2.2.1. Мультипрограммирование в системах пакетной обработки
Слайд 24Операционные системы
Для достижения этой цели пакет заданий формируется так, чтобы
получающаяся мультипрограммная смесь сбалансированно загружала все устройства машины.
Например, в такой
смеси желательно присутствие задач вычислительного характера и с интенсивным вводом-выводом.
2.2.1. Мультипрограммирование в системах пакетной обработки
Слайд 25Операционные системы
Канальная программа
Ввод - вывод
В ы ч и с л
е н и я
Канал
Центральный процессор
Команда запуска канала
Сигнал завершения операции ввода-вывода
2.2.1.
Мультипрограммирование в системах пакетной обработки
О п е р а ц и и в в о д а – в ы в о д а
Контроллеры
Центральный процессор
В ы ч и с л е н и я
Слайд 26Операционные системы
В компьютерах класса мэйнфреймов совмещение достигается благодаря наличию в
машине специализированных процессоров ввода-вывода (каналов).
Ввод-вывод осуществляется одновременно с вычислениями в
центральном процессоре, который «отвлекается» только для выдачи команд каналам и приема сигналов о завершении ввода-вывода.
2.2.1. Мультипрограммирование в системах пакетной обработки
Слайд 27Операционные системы
В благоприятных случаях общее время выполнения смеси задач меньше,
чем суммарное время их последовательного выполнения.
При этом время выполнения отдельной
задачи может быть больше, чем при монопольном ее выполнении.
2.2.1. Мультипрограммирование в системах пакетной обработки
Слайд 28Операционные системы
A
2
2
2
A
B
3
B
1
Ta=6
Tb=5
Ta+Tb=11
В ы ч и с л е н и
я
В в о д – в ы в о
д
A
2
B
3
A
2
B
1
Ta= 7
Tb= 6
Ta+Tb= 8
В ы ч и с л е н и я
A
1
В в о д – в ы в о д
Готовность (ожидание процессора)
Слайд 29Операционные системы
В системах разделения времени пользователям (в частном случае одному)
предоставляется возможность интерактивной работы сразу с несколькими приложениями. Для этого
каждое приложение должно регулярно получать возможность «общения» с пользователем.
ОС принудительно периодически приостанавливает приложения, не дожидаясь, когда они «добровольно» освободят процессор.
2.2.2. Мультипрограммирование в системах разделения времени
Слайд 30Операционные системы
Всем приложениям попеременно выделяются кванты времени процессора, таким
образом, пользователи, запустившие программы на выполнение, получают возможность поддерживать с
ними диалог со своего терминала.
Если время кванта выбрано достаточно небольшим, то у всех пользователей складывается впечатление единоличной работы на машине.
2.2.2. Мультипрограммирование в системах разделения времени
Слайд 31Операционные системы
2.2.2. Мультипрограммирование в системах разделения времени
1
2
3
…
n
Центральный процессор
TКВ = 0,02
мс
Слайд 32Операционные системы
Назначение систем реального времени:
управление техническими объектами (спутник, ракета,
атомные электростанции, станок, научная установка и др.),
управление технологическими процессами (гальваническая
линия, долинный процесс и т. п.),
управление системами обслуживания разного рода (резервирование авиабилетов, оплата покупок и счетов и др.).
2.2.3. Мультипрограммирование в системах реального времени
Слайд 33Операционные системы
Особенности реализации систем реального времени:
существует предельно допустимое
время, в течение которого должна быть выполнена та или иная
программа управления объектом (время реакции системы);
мультипрограммная смесь представляет собой фиксированный набор заранее разработанных программ решения функциональных задач управления объектом или процессом;
2.2.3. Мультипрограммирование в системах реального времени
Слайд 34Операционные системы
выбор программы на выполнение осуществляется по прерываниям (исходя из
текущего состояния объекта) или в соответствии с расписанием плановых работ;
закладывается
запас вычислительной мощности на случай пиковой нагрузки, а также принимаются меры обеспечения высокой надежности работы системы (резервирование, дублирование, троирование с мажоритарным элементом и др.).
2.2.3. Мультипрограммирование в системах реального времени
Слайд 35Операционные системы
Мультипроцессорная обработка - это способ организации вычислительного процесса в
системе с несколькими процессорами, при котором несколько задач (процессов, потоков)
могут одновременно выполняться на разных процессорах системы (часто в качестве серверов ЛВС).
Мультипроцессорная обработка не исключает мультипрограммной обработки на каждом процессоре. При этом резко усложняются все алгоритмы управления ресурсами, т. е. операционная система.
2.2.3. Мультипроцессорная обработка
Слайд 36Операционные системы
Мультипроцессирование поддерживают: Sun Solaris 2.x, Santa Cruz Operation
Open Server 3.x, OS/2, Windows NT/2000/2003 , NetWare, начиная с
версии 4.1.
Мультипроцессорные системы делятся на симметричные и асимметричные.
Эти термины относятся, с одной стороны, к архитектуре вычислительной системы, а с другой - к способу организации вычислительного процесса.
2.2.3. Мультипроцессорная обработка
Слайд 37Операционные системы
Симметричная архитектура мультипроцессорной системы предполагает однотипность и единообразие
включения процессоров и большую разделяемую между этими процессорами память. Масштабируемость,
т. е. возможность наращивания числа процессоров в данном случае ограничена, т. к. все они используют одну и ту же оперативную память и, следовательно, должны располагаться в одном корпусе.
2.2.3. Мультипроцессорная обработка
Слайд 38Операционные системы
Такая конструкция (масштабирование по вертикали) практически ограничивает число
процессоров до 4 или 8.
В симметричных архитектурах все процессоры
пользуются одной и той же схемой отображения памяти, потому могут быстро обмениваться данными.
Это обеспечивает достаточно высокую производительность для приложений, в которых несколько задач должны активно взаимодействовать между собой (например, при работе с базами данных).
2.2.3. Мультипроцессорная обработка
Слайд 39Операционные системы
В симметричных архитектурах вычислительных систем легко реализуется симметричное
мультипроцессирование общей для всех процессоров операционной системой.
При этом все
процессоры равноправно участвуют и в управлении вычислительным процессом, и в выполнении прикладных задач.
Разные процессоры могут в какой-то момент времени одновременно обслуживать как разные, так и одинаковые модули общей ОС.
2.2.3. Мультипроцессорная обработка
Слайд 40Операционные системы
Программы ОС должны быть реентерабельными (повторновходимыми).
Операционная система полностью
децентрализована.
Ее модули выполняются на любом доступном процессоре. Как только
процессор завершает выполнение очередной задачи, он передает управление планировщику задач.
Последний выбирает из общей для всех процессоров системной очереди задачу, которая будет выполняться на данном процессоре следующей.
2.2.3. Мультипроцессорная обработка
Слайд 41Операционные системы
Все ресурсы выделяются для каждой выполняемой задачи по
мере возникновения потребности в них и не закрепляются за процессором.
В решении одной задачи может быть занято несколько процессоров, если задача допускает распараллеливание.
В случае отказа одного или более процессоров симметричные системы сравнительно просто реконфигурируются.
2.2.3. Мультипроцессорная обработка
Слайд 42Операционные системы
В вычислительных системах с асимметричной архитектурой процессоры могут
быть различными как по характеристикам (производительность, система команд), так и
по функциональной роли в работе системы.
Могут быть выделены процессоры для вычислений, ввода-вывода и др.
2.2.3. Мультипроцессорная обработка
Слайд 43Операционные системы
Эта неоднородность ведет к структурным отличиям во фрагментах
системы, содержащих разные процессоры (разные схемы подключения, наборы периферийных устройств,
способы взаимодействия процессоров с устройствами и др.).
Масштабирование в таких системах реализуется иначе, поскольку отсутствует требование единого корпуса.
Система может состоять из нескольких устройств, каждое из которых содержит один или несколько процессоров.
2.2.3. Мультипроцессорная обработка
Слайд 44Операционные системы
Масштабирование в данном случае называют горизонтальным, а мультипроцессорную
систему - кластерной.
В кластерной системе может быть реализовано только
асимметричное мультипроцессирование с организацией вычислительного процесса по принципу «ведущий - ведомый».
В таких системах ОС работает на одном процессоре, который называется ведущим и организует централизованное управление вычислительным процессом и распределением всех ресурсов системы.
2.2.3. Мультипроцессорная обработка
Слайд 45Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Создание процессов и потоков.
Обеспечение процессов и потоков необходимыми ресурсами.
Изоляция
процессов.
Планирование выполнения процессов и потоков.
Диспетчеризация потоков.
6. Организация межпроцессного взаимодействия.
7. Синхронизация процессов и потоков.
8. Завершение и уничтожение процессов и потоков.
События, приводящие к созданию процессов:
Инициализация (загрузка) ОС.
Запрос процесса на создание дочернего процесса.
Запрос пользователя на создание процесса (например, при входе в систему в интерактивном режиме).
Инициирование пакетного задания.
Создание операционной системой процесса какой-либо службы.
Слайд 46Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Обычно при загрузке ОС создаются несколько процессов. Некоторые из
них являются высокоприоритетными процессами, обеспечивающими взаимодействие с пользователями и выполняющими заданную работу.
Остальные процессы являются фоновыми, они не связаны с конкретными пользователями, но выполняют особые функции. Например, связанные с электронной почтой, Web-страницами, выводом на печать, передачей файлов по сети, периодическим запуском программ (например, дефрагментации дисков) и т. д. Фоновые процессы называют демонами.
Новый процесс может быть создан по запросу текущего процесса.
Подсистема управления процессами и потоками отвечает за обеспечение процессов необходимыми ресурсами. ОС поддерживает в памяти специальные информационные структуры, в которые записывает, какие ресурсы выделены каждому процессу.
Слайд 47Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Ресурсы могут быть выделены процессу на все время
его жизни или только на определенный период.
Важнейшей задачей ОС является изоляция одного процесса от другого. Для этого операционная система обеспечивает каждый процесс отдельным виртуальным адресным пространством, так что ни один процесс не может получить прямого доступа к командам и данным другого процесса.
В ОС, где существуют процессы и потоки, процесс рассматривается как заявка на потребление всех видов ресурсов, кроме одного - процессорного времени.
Этот важнейший ресурс распределяется операционной системой между другими единицами работы - потоками, которые представляют собой последовательности (потоки выполнения) команд.
Слайд 48Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Переход от выполнения одного потока к другому осуществляется в
результате планирования и диспетчеризации. Планирование – это работа по определению того, в какой момент необходимо прервать выполнение текущего потока и какому потоку предоставить возможность выполняться.
Планирование потоков осуществляется на основе информации, хранящейся в описателях процессов и потоков. При планировании принимается во внимание приоритет потоков, время их ожидания в очереди, накопленное время выполнения, интенсивность обращения к вводу-выводу и другие факторы.
Диспетчеризация – это реализация найденного в результате планирования решения, т. е. в переключении процессора с одного потока на другой.
Слайд 49Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Диспетчеризация проходит в три этапа:
• сохранение контекста текущего потока;
•
загрузка контекста потока, выбранного в результате планирования;
• запуск нового потока на выполнение.
Для общения друг с другом процессы и потоки могут использовать широкий спектр возможностей: каналы (в UNIX), почтовые ящики (Windows 2000), вызов удаленной процедуры, сокеты (в Windows соединяют процессы на разных машинах). Согласование скоростей потоков также очень важно для предотвращения эффекта «гонок» (когда несколько потоков пытаются получить доступ к одному и тому же ресурсу), взаимных блокировок и других коллизий, которые возникают при совместном использовании ресурсов.
Для решения этой задачи служит синхронизация потоков.
Слайд 50Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Современные операционные системы предоставляют множество механизмов синхронизации, включая семафоры,
мьютексы, критические области и события.
Все эти механизмы работают с потоками, а не процессами. Поэтому когда поток блокируется на семафоре, другие потоки этого процесса могут продолжать работу.
Слайд 51Операционные системы
2.3. Управление процессами и потоками
2.3.1. Основные функции управления процессами
и потоками
Каждый раз, когда процесс завершается, а это происходит благодаря
одному из следующих событий: обычный выход, выход по ошибке, выход по неисправимой ошибке, уничтожение другим процессом, - ОС предпринимает шаги, чтобы «зачистить следы» его пребывания в системе.
Подсистема управления процессами закрывает все файлы, с которыми работал процесс, освобождает области оперативной памяти, отведенные под коды, данные и системные информационные структуры процесса.
Выполняется коррекция всевозможных очередей ОС и списка ресурсов, в которых имелись ссылки на завершаемый процесс.
Слайд 52Операционные системы
2.3.2. Роль процессов, потоков и волокон в мультипрограммировании
Отдельный процесс
не может быть выполнен быстрее, чем в однопрограммном режиме.
Однако приложение,
выполняемое в рамках одного процесса, может обладать внутренним параллелизмом, который в принципе мог бы ускорить его выполнение.
Сложно создать программу, реализующую параллелизм в рамках одного процесса.
Стандартные средства современных ОС не позволяют создать для одного приложения несколько процессов для параллельных работ.
Операционной системе наряду с процессами нужен другой механизм распараллеливания вычислений, который учитывал бы тесные связи между отдельными ветвями вычислений одного и того же приложения.
Многопоточная обработка позволяет распараллелить вычисления в рамках одного процесса.
Слайд 53Операционные системы
2.3.2. Роль процессов, потоков и волокон в мультипрограммировании
Потоки одного
процесса используют общие файлы, таймеры, устройства, одну и ту же
область оперативной памяти, одно и то же адресное пространство; они разделяют одни и те же глобальные переменные.
Многопоточная (multithreading) обработка эффективна в многопроцессорных вычислительных системах.
Использование аппарата волокон (Windows 2000) повышает эффективность мультипрограммирования за счет сокращения переключения режима (пользовательский - привилегированный), но увеличивает трудоемкость разработки приложений. Для управления волокнами нет системных вызовов, однако есть вызовы Win32 API, которые не обращаются к системным вызовам.
Слайд 54Операционные системы
2.4. Создание процессов и потоков. Модели процессов и потоков
2.4.1.Процессы
и их модели
Создание процесса состоит в создании (прежде всего) описателя
процесса: нескольких информационных структур, содержащих все сведения (атрибуты) о процессе, необходимые операционной системе для управления им.
В число таких сведений могут входить:
идентификатор процесса, данные о расположении в памяти исполняемого модуля, степень привилегированности процесса (приоритет и права доступа) и т. п.
Слайд 55Операционные системы
2.4. Создание процессов и потоков. Модели процессов и потоков
2.4.1.Процессы
и их модели
Примеры описателей процесса:
• блок управления задачей (ТСВ -Task
Control Block) в OS/360;
• управляющий блок процесса (РСВ -Process Control Block) в OS/2;
• дескриптор процесса в UNIX;
• объект-процесс (object-process) в Windows NT/2000/2003.
Создание процесса включает загрузку кодов и данных исполняемой программы данного процесса с диска в оперативную память.
Слайд 56Операционные системы
2.4. Создание процессов и потоков. Модели процессов и потоков
2.4.1.Процессы
и их модели
Образ процесса: программа, данные, стек и атрибуты процесса
Слайд 57Операционные системы
2.4. Создание процессов и потоков. Модели процессов и потоков
2.4.1.Процессы
и их модели
При управлении процессами ОС использует два основных типа
информационных структур: блок управления процессом (дескриптор процесса) и контекст процесса.
Дескрипторы процессов объединяются в таблицу процессов, которая размещается в области ядра. На основании информации, содержащейся в таблице процессов, ОС осуществляет планирование и синхронизацию процессов.
Слайд 58Операционные системы
Дескриптор процесса (блок управления) содержит:
1. Информацию по идентификации процесса
(идентификатор процесса, идентификатор пользователя,
идентификаторы родительского и дочерних процессов).
2. Информацию по
состоянию процесса
3. Информацию, используемую для управления процессом
Слайд 59Операционные системы
Идентификация процесса
Каждому процессу присваивается числовой идентификатор, который может быть
просто индексом в первичной таблице процессов.
При создании нового процесса идентификаторы
указывают родительский и дочерние процессы.
Процессу может быть присвоен идентификатор пользователя, который указывает, кто из пользователей отвечает за данное задание.
Слайд 60Операционные системы
Информация по состоянию и управлению процессом
Состояние процесса,
определяющее его готовность к выполнению (выполняющийся, готовый к выполнению, ожидающий
события, приостановленный);
Данные о приоритете (текущий, по умолчанию, максимально возможный);
Информация о событиях – идентификация события, наступление которого позволит продолжить выполнение процесса;
Указатели, позволяющие определить расположение образа процесса в оперативной памяти и на диске;
Указатели на другие процессы (находящиеся в очереди на выполнение);
Флаги, сигналы и сообщения, имеющие отношение к обмену информацией между двумя независимыми процессами;
Данные о привилегиях, определяющие права доступа к определенной области памяти или возможности выполнять определенные виды команд, использовать системные утилиты и службы;
Указатели на ресурсы, которыми управляет процесс;
Сведения по использованию ресурсов и процессора;
Информация, связанная с планированием.
Слайд 61Операционные системы
КОНТЕКСТ ПРОЦЕССА
Содержимое регистров процессора, доступных пользователю (обычно 8
– 32 регистра и до 100 регистров в RISC –
процессорах);
Содержимое счетчика команд;
Состояние управляющих регистров и регистров состояния;
Коды условия, отражающие результат выполнения последней арифметической или логической операции (например, равенство нулю,переполнение);
Указатели вершин стеков,хранящие параметры и адреса вызова процедур и системных служб.
Значительная часть этой информации фиксируется в виде слова состояния программы PSW (program status word – EFLAGS в процессоре Pentium).
Содержит информацию, позволяющую ОС приостанавливать и возобновлять выполнение процесса с прерванного места:
Слайд 62Операционные системы
Простейшая модель процесса
Диспетчеризация
Пауза
Не выполняется
Выполняется
Вход
Выход
CPU
Вход
Выход
Очередь
Пауза
Диспетчеризация
CPU
Граф состояний и переходов
tкв
Слайд 63Операционные системы
Простейшая модель процесса
В любой момент времени процесс либо
выполняется, либо не выполняется, т. е. имеет только два состояния.
Если
бы все процессы были всегда готовы к выполнению, то очередь по этой схеме могла бы работать вполне эффективно.
Такая очередь работает по принципу обработки в порядке поступления, а процессор обслуживает имеющиеся в наличии процессы круговым методом (Round-robin).
Каждому процессу отводится определенный промежуток времени, по истечении которого он возвращается в очередь.
Слайд 64Операционные системы
Новый
Готовый к выполнению
Выполняю-щийся
Вход
в систему
Ожидание
Завершаю-щийся
Освобо-ждение
события
Блокирова-нный
CPU
Поступление процесса
Очередь готовых процессов
Тайм – аут
( tКВ )
Ожидание события
Модель с тремя состояниями
Слайд 65Операционные системы
Модель с тремя состояниями
Все невыполняющиеся процессы делятся на на
два типа: готовые к выполнению и заблокированные. Поскольку процессор работает
намного быстрее выполнения операций ввода-вывода, то вскоре все находящиеся в памяти процессы оказываются в состоянии ожидания ввода-вывода.
Что делать?
Можно увеличить емкость основной памяти, чтобы в ней умещалось больше процессов.
Свопинг - перенос части процессов из оперативной памяти на диск и загрузка другого процесса из очереди приостановленных (но не блокированных!) процессов, находящихся во внешней памяти.
Слайд 66Операционные системы
2.4.2. Потоки и их модели
Описатель потока: блок управления потоком
и контекст потока (в многопоточной системе процессы контекстов не имеют).
Способы
реализации пакета потоков:
в пространстве пользователя (user – level threads – ULT);
в ядре (kernel – level threads – KLT).
При создании потоков ОС генерирует специальную информационную структуру - описатель потока, который содержит идентификатор потока, данные о правах доступа и приоритете, о состоянии потока и другую информацию.
Слайд 67Операционные системы
Поток на уровне пользователя (в пользовательском пространстве)
Процессы
Пространство пользователя
Потоки
Библиотека
подпрограмм для работы с потоками
Ядро
Таблица процессов
Таблицапотоков
Слайд 68Операционные системы
Поток на уровне пользователя (в пользовательском пространстве)
Если управление потоками
происходит в пространстве пользователя, каждому процессу необходима собственная таблица потоков.
Она
аналогична таблице процессов, с той лишь разницей, что отслеживает такие характеристики потоков, как счетчик команд, указатель вершины стека, регистры состояния и т. п.
Когда поток переходит в состояние готовности или блокировки, вся информация, необходимая для повторного запуска, хранится в таблице потоков.
Слайд 69Операционные системы
Поток на уровне пользователя (в пользовательском пространстве)
Приложение в начале
своей работы состоит из одного потока и его выполнение начинается
как выполнение этого потока.
Такое приложение вместе с составляющим его потоком размещается в одном процессе, который управляется ядром.
Все эти события происходят в пользовательском пространстве в рамках одного процесса. Ядро даже «не подозревает» об этой деятельности и продолжает осуществлять планирование процесса как единого целого и приписывать ему единое состояние выполнения.
Слайд 70Операционные системы
Поток на уровне пользователя
можно реализовать в ОС,
не поддерживающей потоки без каких-либо изменений в ОС;
высокая производительность, поскольку
процессу не нужно переключаться в режим ядра и обратно;
ядро о потоках ничего не знает и управляет однопоточными процессами;
имеется возможность использования любых алгоритмов планирования потоков с учетом их специфики;
управление потоками возлагается на программу пользователя.
ДОСТОИНСТВА:
Слайд 71Операционные системы
Поток на
уровне пользователя
НЕДОСТАТКИ:
системный вызов блокирует не только работающий поток, но и все потоки того процесса, к которому он относится;
приложение не может работать в многопроцессорном режиме, так как ядро закрепляет за каждым процессом только один процессор;
при запуске одного потока ни один другой поток а рамках одного процесса не будет запущен пока первый добровольно не отдаст процессор;
внутри одного потока нет прерываний по таймеру, в результате чего невозможно создать планировщик по таймеру для поочередного выполнения потоков.
Слайд 72Операционные системы
Поток на уровне ядра
Процессы
Потоки
Ядро
Пространство пользователя
Таблица процессов
Таблица потоков
Слайд 73Операционные системы
Поток на уровне ядра
В случае потоков на уровне ядра
в области приложения система поддержки исполнения программ не нужна, нет
необходимости и в таблицах потоков в каждом процессе.
Вместо этого есть единая таблица потоков, отслеживающая все потоки в системе.
Если потоку необходимо создать новый поток или завершить имеющийся, он выполняет запрос ядра, который создает или завершает поток, внося изменения в таблицу потоков.
Ядро поддерживает информацию контекста процесса как единого целого, а также контексты каждого отдельного потока процесса. Планирование осуществляется ядром исходя из состояния потоков.
Слайд 74Операционные системы
Поток на уровне ядра
ДОСТОИНСТВА:
возможно планирование работы нескольких потоков одного и того же процесса на нескольких процессорах;
реализуется мультипрограммирование в рамках всех процессов (в том числе одного);
при блокировании одного из потоков процесса ядро может выбрать другой поток этого же (или другого процесса);
процедуры ядра могут быть многопоточными.
НЕДОСТАТКИ:
Необходимость двукратного переключения режима пользователь – ядро, ядро – пользователь для передачи управления от одного потока к другому в рамках одного и того же процесса.
Слайд 75Операционные системы
Потоки и их модели
С целью совмещения преимуществ реализации потоков
на уровне пользователя и на уровне ядра были оправданы многие
способы смешанной реализации.
Один из методов заключается в использовании управления ядром и последующем мультиплексировании потоков на уровне пользователя.
Предполагается, что у каждого потока ядра есть набор потоков на уровне пользователя, которые используют его по очереди.
Слайд 76Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Основная цель планирования
вычислительного процесса заключается в распределении времени процессора (нескольких процессоров) между
выполняющимися заданиями пользователей таким образом, чтобы удовлетворять требованиям, предъявляемым пользователями к вычислительной системе.
Такими требованиями могут быть пропускная способность, время отклика, загрузка процессора и др.
Слайд 77Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Слайд 78Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
В большинстве операционных
систем универсального назначения планирование осуществляется динамически (on-line), т. е. решения
принимаются во время работы системы на основе анализа текущей ситуации, не используя никаких предложений о мультипрограммной смеси.
Найденное оперативно решение в таких условиях редко бывает оптимальным.
Слайд 79Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Другой тип планирования
- статический (предварительный) может быть использован только в специализированных системах
с заданным набором задач (заранее определенным), например, в управляющих вычислительных системах или системах реального времени.
В этом случае статический планировщик (или предварительный планировщик) принимает решение не во время работы системы, а заранее (off-line).
Слайд 80Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Результатом его работы
является расписание - таблица, в которой указано, какому процессу, когда
и на какое время должен быть предоставлен процессор.
При этом накладные расходы ОС на исполнение расписания значительно меньше, чем при динамическом планировании.
Слайд 81Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Краткосрочный планировщик (диспетчер)
реализует найденное решение, т. е. переключает процессор с одного процесса
(потока) на другой.
Он вызывается при наступлении события, которое может приостановить текущий процессор или предоставить возможность прекратить выполнение данного процесса (потока) в пользу другого.
Слайд 82Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Примерами этих
событий могут быть:
• прерывание таймера;
• прерывание ввода-вывода;
• вызовы операционной системы;
•
сигналы.
Слайд 83Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Среднесрочное планирование является
частью системы свопинга.
Обычно решение о загрузке процесса в память принимается
в зависимости от степени многозадачности (например, OS MFT, OS MVT).
Слайд 84Операционные системы
2.5. Планирование заданий, процессов и потоков
Виды планирования
Диспетчеризация сводится к
следующему:
• сохранение контекста текущего потока, который требуется сменить;
• загрузка
контекста нового потока, выбранного в результате планирования;
• запуск нового потока на выполнение.
Слайд 85Операционные системы
Схема планирования с учетом очередей заданий (процессов)
Новый
Готовый / Приостановлен-ный
Готовый
в ОП
Выполняющийся в ОП
Завершаю-щийся
Долгосрочное планирование
Вызов ОС
Активация
Приостановка
Приостановка
Активация
Среднесрочное планирование
Освобождение
Ожидание события (прерывание ввода-вывода,
сообщение)
Диспетчеризация (краткосрочное планирование)
Тайм-аут (таймер)
Блокированный / Приостановленный
Диск
Диск
Блокированный в ОП
Наступление события
С в о п и н г
Наступление события
Слайд 86Операционные системы
Долгосрочное планирование
Тайм-аут
Очередь готовых заданий
Среднесрочное планирование
Среднесрочное планирование
Очередь готовых приостановленных заданий
Очередь
заблокированных приостановленных заданий
Очередь
заблокированных заданий
Событие
Интерактивные пользователи
Пакетные задания
Ожидание события
ЦП
Выход
ОП
Диск
Диск
ОП
Слайд 87Операционные системы
Граф состояния потока
В мультипрограммной системе поток (процесс, если операционная
система работает только с процессами) может находиться в одном из
трех основных состояний:
• выполнение - активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
Слайд 88Операционные системы
Граф состояния потока
ожидание - пассивное состояние потока, находясь в
котором поток заблокирован по своим внутренним причинам (ждет осуществления некоторого
события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);
• готовность - также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые ресурсы, готов выполняться, но процессор занят выполнением другого потока).
Слайд 89Операционные системы
Граф состояния потока
В течение своей жизни каждый поток переходит
из одного состояния в другое в соответствии с алгоритмом планирования
потоков, принятым в данной операционной системе.
Потоки образуют очереди соответственно ожидающих и готовых потоков.
Очереди организуются путем объединения в списки описателей отдельных потоков.
Слайд 90Операционные системы
Типичный граф состояния потока
ВЫПОЛНЕНИЕ
ГОТОВНОСТЬ
ОЖИДАНИЕ
Поток завершен или ошибка
Поток ожидает завершения
ввода-вывода или другого события
Ввод-вывод завершен (событие произошло)
Поток вытеснен (исчерпал квант)
Поток
выбран на выполнение
Вновь созданный поток
Слайд 91Операционные системы
Алгоритмы планирования потоков
Невытесняющие (non-preemptive)
планирование распределяется между ОС и
прикладными программами: активный поток сам решает, когда ему отдать управление
ОС, чтобы та выбрала из очереди готовый к выполнению поток;
необходимость частых передач управлений ОС, в противном случае возможна монополизация процессора приложением;
зависания приложений могут привести к краху системы;
более высокая скорость переключения потоков;
2. Вытесняющие (preemptive)
функции планирования сосредоточены исключительно в ОС;
планирование на основе квантования процессорного времени;
планирование на основе приоритетов потоков: статических, динамических, абсолютных, относительных, смешанных;
Слайд 92Операционные системы
Алгоритмы планирования потоков
В соответствии с концепцией квантования каждому потоку
поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени -
квант.
Смена активного потока происходит, если:
• поток завершается и покинул систему;
• произошла ошибка;
• поток перешел в состояние ожидания;
• исчерпан квант времени, отведенный данному потоку.
Слайд 93Операционные системы
Алгоритмы планирования потоков
Поток, который исчерпал свой квант, переводится в
состояние готовности и ожидает, когда ему будет предоставлен новый квант
процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых потоков.
Выше приведенный граф состояний потока, изображенный соответствует схеме планирования, приведенной далее.
Слайд 94Операционные системы
Простейший алгоритм планирования, реализующий состояния потока для типичного графа
состояния потоков
Тайм - аут
Процессор
Ожидание события
Очередь заблокированных потоков
Ввод-вывод завершен
Новый
поток
Очередь готовых потоков
Выход
Слайд 95Операционные системы
Кванты, выделяемые потокам, могут быть равными или различными (типичное
значение десятки - сотни миллисекунд).
Например, первоначально каждому потоку назначается достаточно
большой квант, а величина каждого следующего кванта уменьшается до некоторой заранее заданной величины.
В таком случае преимущество получают короткие задачи, которые успевают выполняться в течение первого кванта (второго и т. д.), а длительные вычисления будут проводиться в фоновом режиме.
Слайд 96Операционные системы
Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом
Некоторые потоки,
получив квант времени, используют его не полностью, например, из-за необходимости
выполнить ввод или вывод данных. В результате может возникнуть ситуация, когда потоки с интенсивным вводом-выводом используют только небольшую часть выделенного им процессорного времени.
Слайд 97Операционные системы
Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом
Можно создать
две очереди потоков: очередь 1 - для потоков, которые пришли
в состояние готовности в результате исчерпания кванта времени, и очередь 2 - для потоков, у которых завершилась операция ввода-вывода.
При выборе потока для выполнения сначала просматривается вторая очередь и, если она пуста, квант выделяется потоку из первой очереди.
Слайд 98Операционные системы
Алгоритм планирования, реализующий предпочтения потокам с интенсивным вводом-выводом
Ожидание события
Тайм
- аут
Процессор
Новый поток
Очередь 2
Очередь 1
Переключение контекстов потоков связано с потерями
процессорного времени.
С увеличением времени кванта ухудшается обслуживание пользователей.
В алгоритмах, основанных на квантовании, ОС не имеет никаких сведений о характеристиках решаемых задач.
Слайд 99Операционные системы
Граф состояния потока
Выполнение
Ожидание
Очередь готовых потоков 1
Очередь готовых потоков 2
Вновь
созданный поток
tКВ
tКВ
Тайм-аут
Завершение
(ошибка)
Событие (завершение ввода-вывода)
Запрос ввода-вывода
Слайд 100Операционные системы
Алгоритмы приоритетного планирования
В основе многих вытесняющих алгоритмов планирования лежит
приоритетное обслуживание. Оно предполагает наличие у потоков некоторой изначально известной
характеристики - приоритета, на основании которого определяется порядок выполнения потоков.
Чем выше приоритет, тем выше привилегии потока, тем меньше времени поток находится в очередях.
Приоритет задается числом (целым или дробным, положительным или отрицательным).
Слайд 101Операционные системы
Алгоритмы приоритетного планирования
В большинстве операционных систем, поддерживающих потоки, приоритет
потока связан с приоритетом процесса, в рамках которого выполняется поток.
Приоритет
процесса назначается операционной системой при его создании, его значение включается в описатель процесса и используется при назначении приоритета потоком этого процесса.
Слайд 102Операционные системы
Алгоритмы приоритетного планирования
При назначении приоритетов вновь созданному процессу ОС
учитывается, является ли этот процесс системным или прикладным, каков статус
пользователя, запустившего процесс (администратор, пользователь, часть и т. п.), было ли явное указание пользователя на присвоение процессу определенного уровня приоритета.
Поток может быть инициирован не только по команде пользователя, но и в результате выполнения системного вызова другим потоком. В этом случае ОС учитывает значения параметров системного вызова.
Слайд 103Операционные системы
Алгоритмы приоритетного планирования
Процессор
Назначение приоритета
Тайм-аут
Очередь высшего приоритета
Очередь низшего приоритета
Ожидание события
Ожидание
события
Тайм-аут
Завершение (ошибка)
Новый поток
Приоритетное переключение с квантованием
Слайд 104Операционные системы
Алгоритмы приоритетного планирования
Во многих ОС предусматривается возможность изменения приоритета
в течение жизни потока.
Изменения приоритета могут происходить по инициативе самого
потока, когда он обращается с соответствующим вызовом к ОС, или по инициативе пользователя, когда он выполняет соответствующую команду.
Кроме этого, сама ОС может изменить приоритеты потоков в зависимости от ситуации, складывающейся в системе.
В последнем случае приоритеты называются динамическими в отличие от неизменяемых, фиксированных приоритетов.
Слайд 105Операционные системы
Алгоритмы приоритетного планирования
Существуют две разновидности приоритетного планирования: с относительными
и абсолютными приоритетами.
В системах с относительными приоритетами активный поток выполняется
до тех пор, пока он сам не покинет процессор, перейдя в состояние ожидания (по вводу-выводу, например), или не завершится, или произойдет ошибка.
В системах с абсолютными приоритетами выполнение активного потока прерывается еще и по причине появления потока, имеющего более высокий приоритет, чем у активного потока. В этом случае прерванный поток переходит в состояние готовности.
Слайд 106Операционные системы
Алгоритмы приоритетного планирования
В Windows 2000/2003 (W2K) приоритеты организованы в
виде двух групп, или классов: реального времени и переменные.
Каждая из
групп состоит из 16 уровней приоритетов.
Потоки, требующие немедленного внимания, находятся в классе реального времени, который включает такие функции, как осуществление коммуникаций и задачи реального времени.
Поскольку W2K использует вытесняющий планировщик с учетом приоритетов, потоки с приоритетами реального времени имеют преимущество по отношению к прочим потокам.
Слайд 107Операционные системы
31
30
16
-1
0
15
Системные приоритеты
Пользоват. приоритеты
7
8
6
Наивысший
Повышенный
Обычный
Пониженный
Наинизший
Поток обнуления страниц
Пустой поток
Базовый приоритет
Наивысший
Наинизший
Очереди системных потоков
и потоков псевдореального времени
Наивысший
Наинизший
ПРОЦЕССОР
Слайд 108Операционные системы
Алгоритмы приоритетного планирования
В классе приоритетов реального времени все
потоки имеют фиксированный приоритет (от 16 до 31), который никогда
не изменяется, и все активные потоки с определенным уровнем приоритета располагаются в круговой очереди данного класса (t^- 20 мс для W2K Professional, 120 мс - для однопроцессорных серверов).
Слайд 109Операционные системы
Алгоритмы приоритетного планирования
В классе переменных приоритетов поток начинает
работу с базового приоритета процесса, который может принимать значение от
1 до 15. Каждый поток, связанный с процессом, имеет свой базовый приоритет, равный базовому приоритету процесса, или отличающийся от него не более чем на 2 уровня в большую или меньшую сторону.
После активации потока его динамический приоритет может колебаться в определенных пределах - он не может упасть ниже наименьшего базового приоритета данного класса, т. е. 15. (Для потоков с приоритетом 16 и выше никогда не делается никаких изменений приоритетов.)
Слайд 110Операционные системы
Изменение базового приоритета потока
Увеличение приоритета
+ 1 – завершение ввода-вывода по диску; + 2 – для последовательной линии; + 6 – клавиатура; + 8 – звуковая карта; + 2 – снимается блокировка по семафору (для потока переднего плана); + 1 - снимается блокировка по семафору (для потока непереднего плана); приоритет 15 на 2 кванта процессора, если готовый к выполнению поток простаивает более некоторого директивного времени.
Уменьшение приоритета
1 – если полностью использован квант времени процессора (многократно, вплоть до базового приоритета).
Последняя модификация алгоритма планирования W2K заключается в том, что когда окно становится окном переднего плана, все его потоки получают более длительные кванты времени (величина прибавки хранится в системном реестре).
Слайд 111Операционные системы
Резервный (3)
Выполняющийся (2)
Готовый (1)
Ожидание (5)
Транзит (6)
Завершенный (4)
Переключение
Вытеснение
Блокировка / Приостановка
Снятие
блокировки / возобновление. Ресурсов достаточно
Снятие блокировки. Ресурсов недостаточно
Ресурсов достаточно
Выбор для
выполнения
Завершение
Работоспособные процессы (потоки)
Неработоспособные процессы (потоки)
35
Инициализация (0)
Слайд 112Операционные системы
2.6. Взаимодействие и синхронизация процессов и потоков
2.6.1. Проблемы взаимодействия
и синхронизации
В мультипрограммных однопроцессорных системах процессы чередуются, обеспечивая эффективное выполнение
программ.
В многопроцессорных системах возможно не только чередование, но и перекрытие процессов.
Способы взаимодействия процессов (потоков) можно классифицировать по степени осведомленности одного процесса о существовании другого.
Слайд 113Операционные системы
2.6. Взаимодействие и синхронизация процессов и потоков
2.6.1. Проблемы взаимодействия
и синхронизации
Слайд 114Операционные системы
2.6.2. Конкуренция процессов в борьбе за ресурсы
Конкуренция – ситуация,
когда два или более процессов требуют доступ к одному и
тому же ресурсу (принтеру, файлу и т.п.), называемому критическим (неразделяемый ресурс). Часть программы, использующая критический ресурс, называется критической секцией.
Процесс А
Процесс В
Процесс А попадает в критическую область
T1
T2
T3
T4
Процесс А покидает критическую область
Процесс В пытается попасть в критическую область
Процесс В блокирован
Процесс В попадает в критическую область
Процесс В покидает критическую область
T
T
Процессы не должны одновременно находиться в критических областях.
В программе не должно быть предположений о скорости или количестве процессов.
Процесс, находящийся вне критической области, не может блокировать другие процессы.
Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.
Необходимость взаимоисключений:
Слайд 115Операционные системы
Взаимоблокировки (тупики, deadlock)
Группа процессов находится в тупиковой ситуации,
если каждый процесс из группы ожидает события, которое может вызвать
только другой процесс из этой же группы
Процесс
Ресурс
R1
P2
R2
P1
Исходное распределение ресурсов
R1
P2
R2
P1
P2
P1
R1
R2
Тупиковая ситуация
Слайд 116Операционные системы
Взаимоблокировки (тупики, deadlock)
ОС выделяет ресурс R1 процессу Р2,
а ресурс R2 - процессу Р1.
В результате каждый процесс ожидает
получения одного из двух ресурсов.
При этом ни один из них не освобождает уже имеющийся ресурс, ожидая получения второго ресурса для выполнения функций, требующих наличия двух ресурсов.
В результате процессы оказываются взаимно заблокированными.
Слайд 117Операционные системы
Взаимоблокировки (тупики, deadlock)
Удобно моделировать условия возникновения тупиков, используя
направленные графы.
Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики.
Ребро, направленное
от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется.
Ребро, направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу. Цикл в графе означает наличие взаимной блокировки процессов.
Слайд 118Операционные системы
Проблема “голодание”
R
R
R
R
P1
P2
P3
P1
P2
P3
P1
P2
P3
P1
P2
P3
Активный
Блокированные
Блокированные
Активный
Активный
Блокированные
Блокированные
Активный
Слайд 119Операционные системы
Проблема “голодание”
Пусть Р1 обладает ресурсом, а Р2 и РЗ
приостановлены в ожидании освобождения ресурса R.
После выхода Р1 из критического
раздела доступ к ресурсу будет получен одним из процессов Р2 или РЗ.
Пусть ОС предоставила доступ к ресурсу процессу РЗ.
Пока он работает с ресурсом, доступ к ресурсу вновь требуется процессу Р1.
Слайд 120Операционные системы
Проблема “голодание”
В результате по освобождении ресурса R процессом РЗ
может оказаться, что ОС вновь предоставит доступ к ресурсу процессу
Р1.
Тем временем процессу РЗ вновь требуется доступ к ресурсу R.
Теоретически возможна ситуация, в которой процесс Р2 никогда не получит доступа к требуемому ему ресурсу, несмотря на то что никакой взаимной блокировки в данном случае нет.
Слайд 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
Ситуации, в которых два или более процессов обрабатывают разделяемые данные (файлы) и конечный результат зависит от скоростей процессов (потоков), называются гонками.
Слайд 122Операционные системы
2.6.3. Сотрудничество с использованием разделения
Набор процессов называется детерминированным, если
всякий раз при псевдопараллельном исполнении для одного и того же
набора входных данных он дает одинаковые выходные данные.В противном случае он недетерминирован.
Детерминированный набор процессов можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.
Про недетерминированный набор программ говорят, что он имеет race condition (состояние гонки, состояние состязания).
Слайд 123Операционные системы
2.6.3. Сотрудничество с использованием разделения
Задачу упорядоченного доступа к разделяемым
данным (устранение race condition) в том случае, если нам не
важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным.
Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного с ним общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion).
Слайд 124Операционные системы
2.6.4. Сотрудничество с использованием связи
При сотрудничестве с использованием связи
различные процессы принимают участие в общей работе, которая их объединяет.
Связь
обеспечивает возможность синхронизации, или координации, различных действий процессов.
Обычно можно считать, что связь состоит из сообщений определенного вида.
Примитивы для отправки и получения сообщений могут быть предоставлены языком программирования или ядром операционной системы.
Слайд 125Операционные системы
2.6.4. Сотрудничество с использованием связи
Поскольку в процессе передачи сообщений
не происходит какого-либо совместного использования ресурсов, взаимоисключения не требуется, хотя
проблемы взаимоблокировок и голодания остаются актуальными.
Слайд 126Операционные системы
2.6.4. Методы взаимоисключений
Запрещение прерываний при входе в критическую область
и разрешение прерываний после выхода из критической области. Достоинства: простота
реализации. Недостатки: монополизация процессора, возможный крах ОС при сбое процесса, невозможность использования в многопроцессорных системах, так как прерывание относится к одному процессору
Глобальные блокирующие переменные (программный подход)
F(D)=1?
Да, свободен
Нет, занят
Попытка доступа к разделяемому ресурсу D
Занять ресурс F(D)=0
Критическая секция (работа с ресурсом D)
Освободить ресурс F(D)=1
Неделимая (атомарная) операция “проверка-установка”
Команды TC, BTR, BTS процессора Pentium (анализ и присвоение значения логической переменной)
Недостатки: необходимость постоянного опроса другими потоками, требующими тот же ресурс, блокирующей переменной; дополнительные затраты процессорного времени, применимы для потоков одного процесса
Слайд 127Операционные системы
3.Использование системных функций входа в критическую секцию
Системный вызов
EnterCriticalSection()
Попытка
доступа к разделяемому ресурсу D
F(D)=1?
Нет
Да
Перевести данный поток в ожидание D
Установить
блокирующую переменную в состояние “Занято”, F(D) = 0
Критическая секция (работа с ресурсом D)
Установить блокирующую переменную в состояние “Свободно”, F(D) = 1
Перевести поток, ожидающий ресурс D, в состояние Готовность
Системный вызов
LeaveCriticalSection()
Достоинство: исключается потеря времени процессора на циклическую проверку освобождения занятого ресурса.
Недостаток: растут накладные расходы ОС по реализации функции входа в критическую секцию и выхода из нее
Слайд 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 (Первым зашел – первым вышел).
Слайд 129Операционные системы
f
e
N
Начальные значения семафоров
e = N; f = 0
P(e)
Работа с
разделяемым ресурсом (e=e-1)
V(f) ( f=f+1)
Потоки-писатели
Потоки-читатели
Буферный пул
e > 0
P(f)
f > 0
Работа
с разделяемым ресурсом (f=f-1)
V(e) (e=e+1)
e – пустые буферы, f – занятые буферы
Слайд 130
Операционные системы
5. Мониторы Хоара и Хансена
Монитор — это механизм организации
параллелизма, который содержит как данные, так и процедуры, необходимые для
динамического распределения конкретного общего ресурса или группы общих ресурсов.
Суть этого механизма сводится к следующему.
Процесс, желающий получить доступ к разделяемым переменным, должен обратиться к монитору (вызвать его процедуру), который либо предоставит доступ, либо откажет в нем.
Механизм монитора гарантирует взаимное исключение процессов. Процессам, которые хотят войти в монитор, когда он уже занят, приходится ждать. Режимом ожидания автоматически управляет сам монитор.
При отказе в доступе монитор блокирует обратившийся к нему процесс и определяет условие ожидания. Проверка условия ожидания выполняется самим монитором, который и деблокирует ожидающий процесс.
Слайд 131Операционные системы
Описание структуры и функциональной схемы монитора
Внутренние данные монитора могут
быть либо глобальными (относящимися ко всем процедурам монитора), либо локальными
(относящимися только к одной конкретной процедуре). Ко всем этим данным можно обращаться только изнутри монитора. Процессы, находящиеся вне монитора только вызывают его процедуры, и не могут получить прямой доступ к данным монитора. При первом обращении (либо при создании) монитор присваивает своим переменным начальные значения. Значения глобальных переменных монитора сохраняются между обращениями.
Слайд 132Операционные системы
Абстрактное описание структуры монитора:
monitor monitor_name
{
Описание глобальных переменных;
void m1(…){
…………
}
void m2(…){
…………
}
…………….
void
mn(…){
…………
}
{
блок инициализации внутренних переменных
}
}
Слайд 133Операционные системы
Абстрактное описание структуры монитора:
Здесь функции m1, m2, … mn
представляют собой процедуры (функции члены) монитора, а блок инициализации глобальных
(внутренних) переменных содержит операции, которые выполняются только один раз: при создании монитора или при самом первом вызове какой-либо процедуры до ее выполнения.
Слайд 134Операционные системы
Описание функционирования монитора
Если процесс обращается к некоторой процедуре монитора,
а соответствующий ресурс уже занят, эта процедура выдает команду ожидания
WAIT с указанием условия ожидания. Процесс, переводящийся в режим ожидания, ждёт вне монитора того момента, когда необходимый ему ресурс освободится.
Со временем процесс, который занимал данный ресурс, обратится к монитору, чтобы возвратить ресурс системе, вызвав соответствующую процедуру монитора. Соответствующая процедура монитора принимает уведомление о возвращении ресурса (вносит его в список свободных), а затем ждёт, пока не поступит запрос от другого процесса, которому потребуется этот ресурс. Если процессы, ожидающие освобождения данного ресурса, уже имеются, то эта процедура монитора выполняет команду извещения (сигнализации) SIGNAL, чтобы один из ожидающих процессов мог получить данный ресурс и покинуть монитор.
Слайд 135Операционные системы
Описание функционирования монитора
Чтобы гарантировать, что процесс, находящийся в ожидании
некоторого ресурса, со временем получит этот ресурс, Хоар предложил, чтобы
ожидающий процесс имеет более высокий приоритет, чем новый процесс, пытающийся войти в монитор. Это исключает голодание. Несколько позже Хансен предложил другой подход: разбудивший процесс покидает монитор немедленно после исполнения операции SIGNAL.
Слайд 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;
}
}
Слайд 137Операционные системы
Пример монитора Хоара
Единственный ресурс динамически запрашивается и освобождается процессами,
которые обращаются к процедурам REQUEST (запрос) и RELEASE (освободить). Если
процесс обращается к процедуре REQUEST в тот момент, когда ресурс используется, значение переменной busy (занято) будет равно true, и процедура REQUEST выполнит операцию монитора WAIT(free). Эта операция блокирует не процедуру REQUEST, а обратившийся к ней процесс, который помещается в конец очереди процессов, ожидающих, пока не будет выполнено условие free (свободно).
Когда процесс, использующий ресурс, обращается к процедуре RELEASE, операция монитора SIGNAL деблокирует процесс, находящийся в начале очереди, не позволяя исполняться никакой другой процедуре внутри того же монитора. Этот деблокированный процесс будет готов возобновить исполнение процедуры REQUEST сразу же после операции WAIT(free), которая его и блокировала. Если операция SIGNAL(free) выполняется в то время, когда нет процесса, ожидающего условия free, то никаких действий не выполняется.
Слайд 138Операционные системы
Реализация мониторов
Мониторы представляют собой особые конструкции языка программирования. Компилятор
вызовы процедур монитора обрабатывает специальным образом, добавляя к ним пролог
и эпилог, реализующие механизм взаимоисключения.
Мониторы встречаются в таких языках программирования, как параллельный Евклид, параллельный Паскаль, Java и т.д.
Слайд 139Операционные системы
Решение задачи производитель-потребитель с помощью мониторов:
monitor ProducerConsumer
{
condition full, empty;
int
count;
void put()
{
if(count==N) wait(full);
put_item();
count++;
if(count==1) signal(empty);
}
Слайд 140Операционные системы
Решение задачи производитель-потребитель с помощью мониторов:
void get()
{
if(count==0) wait(empty);
get_item();
count--;
if(count==N-1) signal(full);
}
{
count=0;
}
}
Слайд 141Операционные системы
Решение задачи производитель-потребитель с помощью мониторов:
Producer:
while(1)
{
produce_item();
ProducerConsumer.put();
}
Consumer:
while(1)
{
ProducerConsumer.get();
consume_item();
}
Слайд 142Операционные системы
2.6.5. Взаимоблокировки (тупики)
Условия возникновения взаимоблокировки (тупиковой) ситуации:
Взаимное исключение. Каждый
ресурс в данный момент или отдан ровно одному процессу, или
недоступен.
Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы.
Отсутствие принудительной выгрузки ресурсов. У процесса нельзя забрать принудительно ранее полученные ресурсы.
Условие циклического ожидания. Существует круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Стратегии борьбы с взаимоблокировками:
1. Пренебрежение проблемой в целом. 2. Обнаружение и устранение взаимоблокировок (восстановление). 3. Недопущение тупиковых ситуаций с помощью аккуратного распределения ресурсов. 4. Предотвращать с помощью структурного опровержения одного из четырех условий, необходимых для взаимоблокировки
Слайд 143Операционные системы
Методы обнаружения взаимоблокировок
В системе один ресурс каждого типа.
Например,
пусть система из семи процессов (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.
ВОПРОС: Заблокирована ли эта система и если да, то какие процессы в этом участвуют?
ОТВЕТ МОЖНО ПОЛУЧИТЬ, ПОСТРОИВ ГРАФ РЕСУРСОВ И ПРОЦЕССОВ.
Слайд 144Операционные системы
цикл
R
A
C
S
F
D
B
T
E
U
W
G
V
Граф ресурсов и процессов
Слайд 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
. . . . . . . . . . . . . .
cn1 cn2 cnm rn1 rn2 . . . . Rnm
Слайд 146Операционные системы
Алгоритм обнаружения тупиков
Основан на сравнении векторов ресурсов. В исходном
состоянии все процессы не маркированы (не отмечены). По мере реализации
алгоритма на процессы будет ставиться отметка, обозначающая, что они могут закончить свою работу, т. е. не находятся в тупике. После завершения алгоритма любой немаркированный процесс находится в тупиковой ситуации.
Алгоритм
Ищется процесс Pi , для которого i – я строка матрицы R меньше вектора
A, т. е. Ri <= Aj или ri j <= Aj , j = 1, m.
Если такой процесс найден, он маркируется, и далее прибавляется I - я
строка матрицы С к вектору A, т.е. Aj := Aj + сi j , j = 1, m.
Возврат к шагу 1.
3. Если таких процессов не существует, работа алгоритма заканчивается. Если есть немаркированные процессы, то они попали в тупик.
Слайд 147Операционные системы
Методы устранения тупиков
Принудительная выгрузка ресурсов. Изъятие ресурса у процесса,
передача его другому процессу, а затем возврат ресурса таким образом,
что исходный процесс этого “ не замечает” (сложно и чаще всего невозможно).
Восстановление через “откат”. Процессы периодически создают контрольные точки, позволяющие запустить процесс с предыстории. При возникновении тупика процесс, занимающий необходимый ресурс “откатывается” к контрольной точке, после которой он получил ресурс. Если возобновленный процесс вновь попытается получить данный ресурс, он переводится в режим ожидания освобождения этого ресурса.
Восстановление путем уничтожения процессов.
Недопущение тупиков путем безопасного распределения ресурсов. Подобные алгоритмы базируются на концепции безопасных состояний. Например, Дейкстрой был разработан алгоритм планирования, позволяющий избегать взаимоблокировок (алгоритм банкира).
Слайд 148Операционные системы
2.6.6. Синхронизирующие объекты ОС
Для синхронизации потоков, принадлежащих разным процессам,
ОС должна предоставлять потокам системные объекты синхронизации.
К таким объектам относятся
события (event), мьютексы (mutex – mutual exclusion – взаимное исключение), системные семафоры и др.
Объект-событие используется для того, чтобы оповестить потоки о том, что некоторые действия завершены.
Мьютекс (простейший двоичный семафор) используется для управления взаимным исключением доступа к совместно используемым данным.
Семафоры используются для оповещения свершения последовательности событий.
Для синхронизации используются также “обычные ” объекты ОС: файлы, процессы, потоки
Все объекты синхронизации могут находиться в сигнальном и несигнальном (свободном) состоянии. Поток с помощью системного вызова WAIT(X) может синхронизировать свое выполнение с объектом синхронизации X. По этому вызову поток переводится ОС в состояние ожидания до тех пор, пока объект X не перейдет в сигнальное состояние. С помощью системного вызова SET(X) поток может перевести объект X в сигнальное состояние.
Слайд 149Операционные системы
2.6.6. Синхронизирующие объекты ОС
При переходе объекта в сигнальное состояние
ожидающий этот объект поток переводится в очередь готовых к выполнению
потоков.
В ОС определен набор сигналов для логической связи между процессами, а также процессами и пользователями (терминалами).
Сигналы дают возможность задаче реагировать на событие, источником которого может быть ОС или другая задача.
Слайд 150Операционные системы
2.6.6. Синхронизирующие объекты ОС
Синхронные сигналы чаще всего приходят от
системы прерывания процессора и свидетельствуют о действиях процесса, блокируемых аппаратурой,
например деление на нуль, ошибка адресации, нарушение защиты памяти и т. д.
Примером асинхронного сигнала является сигнал с терминала.
Обработка сигналов аналогична обработке аппаратных прерываний ввода-вывода.
Слайд 151
Операционные системы
2.6.7. Средства взаимодействия ОС между процессами
Программный канал связи (pipe),
или, как его иногда называют, конвейер, является средством, с помощью
которого процессы могут обмениваться данными между собой на основе механизма ввода-вывода файлов (в UNIX).
Конвейеры
Когда процесс А хочет отправить данные процессу В, он пишет их в канал, как если бы это был выходной файл (псевдофайл).
Процесс В читает данные из канала, как если бы он был входным файлом (псевдофайл).
Подобное средство взаимодействия используется в операционной системе UNIX.
Слайд 152
Операционные системы
Операции записи и чтения осуществляются потоком байтов, как это
принято в UNIX-системах.
Функции, с помощью которых выполняется запись в
канал и чтение из него, являются теми же самыми, что и при работе с файлами.
Конвейеры
Канал представляет собой поток данных между двумя (или более) процессами.
На самом деле конвейеры не являются файлами на диске, а представляют собой буферную память, работающую по принципу FIFO, то есть по принципу обычной очереди.
Слайд 153
Операционные системы
Конвейер имеет определенный размер, который не может превышать 64
Кбайт и работает циклически, как реализация очереди на массивах, когда
имеются указатели первого (head – голова) и последнего (tail – хвост) элементов очереди в массиве, которые перемещаются циклически по массиву.
Конвейеры
Слайд 154Операционные системы
В начальный момент оба указателя равны нулю. Добавление самого
первого элемента в пустую очередь приводит к тому, что указатели
на начало и на конец принимают значение, равное 1 (в массиве появляется первый элемент).
В последующем добавление нового элемента вызывает изменение значения второго указателя, поскольку он отмечает расположение именно последнего элемента очереди.
Чтение (и удаление) элемента (читается и удаляется всегда первый элемент из созданной очереди) приводит к необходимости модифицировать значение указателя на ее начало.
Конвейеры
Слайд 155Операционные системы
В результате операций записи (добавления) и чтения (удаления) элементов
в массиве, моделирующем очередь элементов, указатели будут перемещаться от начала
массива к его концу.
При достижении указателем значения индекса последнего элемента массива значение указателя вновь становится единичным (если при этом не произошло переполнение массива, то есть количество элементов в очереди не стало большим числа элементов в массиве).
Массив как бы замыкается в кольцо, организуя круговое перемещение указателей на начало и на конец, которые отслеживают первый и последний элементы в очереди.
Конвейеры
Слайд 156
Операционные системы
Как информационная структура конвейер описывается идентификатором, размером и двумя
указателями. Конвейеры представляют собой системный ресурс.
Конвейеры
Чтобы начать работу с
конвейером, процесс сначала должен заказать его у операционной системы и получить в свое распоряжение. Процессы, знающие идентификатор конвейера, могут через него обмениваться данными.
Слайд 157Операционные системы
Основные системные запросы для работы с конвейерами на примере
API OS/2:
Конвейеры
Функция чтения из конвейера:
DosRead (&ReadHandle, (PVOID)&Inform, sizeof(Inform). &BytesRead);
Здесь ReadHandle
— дескриптор чтения из конвейера, Inform — переменная любого типа, sizeof(Inform) — размер переменной Inform, BytesRead — количество прочитанных байтов. Данная функция при обращении к пустому конвейеру будет ожидать, пока в нем не появится информация для чтения.
Функция создания конвейера:
DosCreatePipe (&ReadHandle, &WriteHandle, PipeSize);
Здесь ReadHandle — дескриптор чтения из конвейера, WriteHandle — дескриптор записи в конвейер, PipeSize — размер конвейера.
Функция записи в конвейер:
DosWrite (&WriteHandle. (PVOID)&Inform, sizeofCInform),&SBytesWrite);
Здесь WriteHandle — дескриптор записи в конвейер, BytesWrite — количество записанных байтов.
Слайд 158
Операционные системы
Очереди (queues) сообщений представляют собой метод связи между
взаимодействующими процессами, позволяющий передавать данные (сообщения) из одного процесса в
другой процесс путем помещения их в некоторый буфер и последующего чтения из него.
2.6.7. Средства взаимодействия ОС между процессами
Очереди сообщений
Слайд 159
Операционные системы
С помощью очередей можно из одного или нескольких
процессов независимым образом посылать сообщения некоторой задаче-приемнику.
Очередь работает только в
одном направлении: только процесс-приемник может читать и удалять сообщения из очереди, а процессы-клиенты имеют право лишь помещать в очередь свои сообщения. Если же необходима двухсторонняя связь, то можно создать две очереди.
Очереди сообщений
Слайд 160
Операционные системы
Очереди сообщений предоставляют возможность использовать несколько дисциплин обработки
сообщений:
FIFO — сообщение, записанное первым, будет первым и прочитано;
LIFO —
сообщение, записанное последним, будет прочитано первым;
приоритетный доступ — сообщения читаются с учетом их приоритетов;
произвольный доступ — сообщения читаются в произвольном порядке.
При чтении сообщения из очереди его удаления не происходит (в отличие от канала).
Очереди сообщений
Слайд 161
Операционные системы
В очередях присутствуют не непосредственно сами сообщения, а
только их адреса в памяти и размер. Эта информация размещается
системой в сегменте памяти, доступном для всех задач, общающихся с помощью данной очереди.
Очереди сообщений
Каждый процесс, использующий очередь, должен предварительно получить разрешение на доступ в общий сегмент памяти с помощью системных запросов API, ибо очередь — это системный механизм, и для работы с ним требуются системные ресурсы и, соответственно, обращение к самой ОС.
Слайд 162
Операционные системы
Во время чтения из очереди задача-приемник пользуется следующей информацией:
идентификатор процесса (Process Identifier, PID), который передал сообщение;
адрес и
длина переданного сообщения;
признак необходимости ждать, если очередь пуста;
приоритет переданного сообщения;
номер освобождаемого семафора, когда сообщение передается в очередь.
Очереди сообщений
Слайд 163
Операционные системы
Перечень основных функций, управляющих работой очереди (без подробного описания
передаваемых параметров, поскольку в различных ОС обращения к этим функциям
могут существенно различаться):
CreateQueue — создание новой очереди;
OpenQueue — открытие существующей очереди;
ReadQueue — чтение и удаление сообщения из очереди;
PeekQueue — чтение сообщения без его последующего удаления из очереди;
WriteQueue — добавление сообщения в очередь;
CloseQueue — завершение использования очереди;
PurgeQueue — удаление из очереди всех сообщений;
QueryQueue — определение числа элементов в очереди.
Очереди сообщений
Слайд 164Операционные системы
Почтовые ящики, используемые в Windows 2000, в некоторых аспектах
подобны каналам, однако, в отличие от каналов, являются однонаправленными.
Они позволяют
отправляющему процессу использовать широковещание для рассылки сообщений сразу многим получателям.
Для прямой и непрямой адресации достаточно двух примитивов, чтобы описать передачу сообщений по линии связи - send и receive.
2.6.7. Средства взаимодействия ОС между процессами
Почтовые ящики
Слайд 165Операционные системы
В случае прямой адресации их можно обозначать так:
send(P,
message) - послать сообщение message процессу Р;
receive(Q, message) - получить
сообщение message от процесса Q,.
В случае непрямой адресации мы будем обозначать их так:
send(A, message) - послать сообщение message в почтовый ящик А;
receive(A, message) - получить сообщение message из почтового ящика А.
Почтовые ящики
Слайд 166Операционные системы
Примитивы send и receive уже имеют скрытый от наших
глаз механизм взаимоисключения.
Более того, в большинстве систем они уже имеют
и скрытый механизм блокировки при чтении из пустого буфера и при записи в полностью заполненный буфер.
Реализация решения задачи producer-consumer для таких примитивов становится тривиальной. Надо отметить, что, несмотря на простоту использования, передача сообщений в пределах одного компьютера происходит существенно медленнее, чем работа с семафорами и мониторами.
Почтовые ящики
Слайд 167Операционные системы
Сокеты (ОС Windows 2000) подобны каналам, с тем отличием,
что они при нормальном использовании соединяют процессы на разных компьютерах.
Например,
один процесс пишет в сокет, а другой на удаленной машине читает из него.
В принципе сокеты можно использовать для соединения процессов на одной машине, но это связано с большими накладными расходами.
2.6.7. Средства взаимодействия ОС между процессами
Сокеты
Слайд 168Операционные системы
Вызов удаленной процедуры (Remote Procedure Call, RPC) представляет собой
способ, которым процесс А просит процесс В вызвать процедуру в
адресном пространстве процесса В от имени процесса А и вернуть результат процессу А.
2.6.7. Средства взаимодействия ОС между процессами
Вызов удаленной процедуры
Слайд 169Операционные системы
Процессы могут совместно использовать память для одновременного отображения одного
и того же файла.
Все, что один процесс будет писать в
этот файл, будет появляться в адресном пространстве других процессов.
С помощью такого механизма легко реализовать общий буфер, применяемый в задаче производителя и потребителя (писатели – читатели).
Запись в этот файл одним из процессов мгновенно становится видной остальным.
2.6.7. Средства взаимодействия ОС между процессами
Разделяемая память
Слайд 170Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Классы прерываний: внешние,
внутренние, программные
1. Внешние прерывания – результат действий пользователя, сигналы от
периферийных устройств компьютера и управляемых объектов.
2. Внутренние прерывания – результат появления аварийных ситуаций при выполнении инструкции программы.
3. Программные прерывания – результат выполнения запланированных в программе особых инструкций (системный вызов).
Принципы построения систем прерываний:
аппаратная поддержка (контроллер прерываний, контроллер DMA, контроллеры внешних устройств, шины подключения внешних устройств, средства микропроцессора);
векторный, опрашиваемый и комбинированный способы прерываний;
приоритетный механизм обслуживания (с абсолютными и относительными приоритетами);
маскирование прерываний;
диспетчер прерываний и процедуры обслуживания прерываний.
Слайд 171Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Операционные системы имеют
специальные модули для работы с прерываниями - обработчики прерываний, или
процедуры обслуживания прерываний (Interrupt Service Routine, ISR).
Аппаратные прерывания обрабатываются драйверами соответствующих внешних устройств, исключения - специальными модулями ядра, а программные прерывания - процедурами ОС, обслуживающими системные вызовы.
Слайд 172Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Кроме этих
моделей в ОС может быть диспетчер прерываний, координирующий работу отдельных
обработчиков прерываний.
Существуют два основных способа, с помощью которых шины выполняют прерывания: векторный (vectored) и опрашиваемый (polled).
В обоих случаях процессору предоставляется информация об уровне приоритета прерывания на шине подключения внешних устройств.
Слайд 173Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
В случае
векторных прерываний в процессор передается информация о начальном адресе программы
обработки прерываний - обработчика прерывания.
При использовании опрашиваемых прерываний процессор получает от запросившего прерывания устройства только информацию об уровне приоритета прерывания.
С каждым уровнем может быть связано несколько устройств и соответственно несколько обработчиков прерываний.
Слайд 174Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
В этом
случае при возникновении прерывания процессор вызывает поочередно всех обработчиков прерываний
данного уровня приоритета, пока один из обработчиков не подтвердит, что прерывание прошло от обслуживаемого им устройства.
Возможен комбинированный подход, сочетающий векторный и опрашиваемый типы прерываний.
Такой подход реализован в ПК на основе процессоров Intel Pentium.
Слайд 175Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Вектор
прерываний в процессор Pentium поставляет контроллер прерываний, который отображает поступающий
от шины сигнал IRQ (Interrupt Request) на определенный номер вектора. Вектор прерываний представляет собой число, указывающее на одну из 256 программ обработки прерываний, адреса которых хранятся в таблице обработчиков прерываний.
В том случае, когда к каждой линии IRQ подключается только одно устройство, процедура прерываний работает как чисто векторная.
Слайд 176Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Однако
при совместном использовании одного уровня IRQ несколькими устройствами обработка прерываний
реализуется по схеме опрашиваемых прерываний, т. е. в данном случае необходимо выполнить опрос всех устройств, подключенных к данному уровню IRQ (Interrupt Request).
Слайд 177Операционные системы
2.7. Аппаратно-программные средства поддержки мультипрограммирования
2.7.1. Системы прерываний
Обычно в ОС
поддерживается механизм приоритезации и маскирование прерываний.
Каждый класс прерываний имеет свой
уровень приоритета.
Приоритеты могут обслуживаться как относительные и как абсолютные.
Маскирование позволяет запретить прерывания любого приоритета на некоторый промежуток времени.
Слайд 178Операционные системы
Последовательность действий при обработке прерываний
Первичное аппаратное распознавание типа прерывание.
Если прерывания запрещены, продолжается текущая программа. В противном случае вызывается
диспетчер прерываний и в зависимости от поступившей в процессор информации (вектор прерывания, приоритет и др.) производится вызов процедуры обработки прерывания.
Сохраняется некоторая часть контекста прерванного потока, которая позволит возобновить его исполнение после обработки прерывания (обычно слово состояния процессора – регистр EFLAGS в Pentium, регистры общего назначения). Может быть сохранен и полный контекст, если ОС обслуживает прерывание со сменой процесса.
В счетчик команд загружается адрес процедуры обработки прерывания и устанавливается новое PSW, которое определяет привилегированный режим работы процессора при обработке прерывания.
Маскированием прерываний временно запрещаются прерывания данного типа, чтобы не образовалась очередь вложенных друг в друга потоков одной и той же процедуры.
После обработки прерывания ядром операционной системы, прерванный контекст восстанавливается (частично аппаратно – PSW, содержимое счетчика команд, частично программно – извлечение данных из стека), снимается обработка прерываний данного типа и работа потока возобновляется с прерванного места.
Слайд 179Операционные системы
2.7.2. Системные вызовы
Системный вызов позволяет приложению обратиться к ОС
с просьбой выполнить то или иное действие, оформленное как процедура
кодового сегмента ОС.
Реализация системных вызовов должна удовлетворять следующим требованиям:
обеспечивать переключение в привилегированный режим;
обладать высокой скоростью вызова процедур ОС;
обеспечивать по возможности единообразное обращение к системным вызовам для всех аппаратных платформ, на которых работает ОС;
допускать простое расширение системных вызовов;
обеспечивать контроль со стороны ОС за корректным использованием системных вызовов.
Возможные схемы обслуживания системных вызовов:
1. Децентрализованная –за каждым системным вызовом закреплен свой вектор прерываний. Достоинство – высокая скорость обработки системных вызовов, недостаток – разрастание таблицы векторов прерываний. 2. Централизованная – с помощью диспетчера системных вызовов. При любом системном вызове приложение выполняет программное прерывание с определенным и единственным номером.
Слайд 180Операционные системы
Таблица прерываний системы
Адрес диспетчера системных вызовов
Диспетчер системных вызовов
Процедура обработки
системного вызова 21h
Процедура обработки системного вызова 22h
Процедура обработки системного вызова
23h
Виртуальное адресное пространство
RQ=21h
Системный
вызов
Адрес процедуры 21h
Адрес процедуры 22h
Адрес процедуры 23h
Централизованная схема обработки системных вызовов
Вектор 80h Linux
INT 2Eh Pentium
Слайд 181Операционные системы
Централизованная схема обработки системных вызовов
Перед выполнением прерывания приложение передает
операционной системе номер системного вызова, который является индексом в таблице
адресов процедур ОС, реализующих системные вызовы.
Передаются параметры (аргументы) системного вызова.
Слайд 182Операционные системы
Централизованная схема обработки системных вызовов
Любой системный вызов приводит к
запуску диспетчера системных вызовов, который представляет собой простую программу, сохраняющую
содержимое режимов в системном стеке (поскольку в результате программного прерывания процессор переходит в привилегированный режим) и проверяющую попадает ли запрошенный номер вызова в поддерживаемый ОС диапазон.
Если все условия соблюдены, диспетчер передает управление процедуре ОС, адрес которой задан в таблице адресов системных вызовов.
Слайд 183Операционные системы
Централизованная схема обработки системных вызовов
Процедура реализации системного вызова извлекает
из системного стека аргументы и выполняет заданное действие.
После завершения работы
системного вызова управление возвращается диспетчеру, при этом он получает код завершения этого вызова.
Диспетчер восстанавливает регистры процессора, помещает в определенный регистр код возврата и выполняет инструкцию возврата из прерывания, которая восстанавливает непривилегированный режим работы процессора.
Слайд 184Операционные системы
Централизованная схема обработки системных вызовов
Операционная система выполняет системные вызовы,
в синхронном и асинхронном режимах.
В первом случае процесс, сделавший такой
вызов, приостанавливается до тех пор, пока системный вызов не выполнит свою работу.
После этого планировщик переводит процесс в состояние готовности и при очередном выполнении процесс может воспользоваться результатами завершившегося системного вызова.
Слайд 185Операционные системы
Централизованная схема обработки системных вызовов
Асинхронный системный вызов не приводит
к переводу процесса в режимах ожидания и после выполнения некоторых
начальных системных действий, например запуска операции ввода-вывода, управление возвращается прикладному процессу. Такой режим работы характерен для ОС на основе микроядра.
