Использование блокировки памяти при синхронизации параллельных процессов
Использование блокировки памяти при синхронизации параллельных процессов - раздел Информатика, Программное обеспечение можно разделить на две группы: системное программное обеспечение СПО и прикладное программное обеспечение ППО Все Вычислительные Машины И Системы Имеют Такое Средство Для Организации Взаи...
Все вычислительные машины и системы имеют такое средство для организации взаимного исключения, как блокировка памяти. Это средство запрещает одновременное исполнение двух (и более) команд, которые обращаются к одной и той же ячейке памяти. Поскольку в некоторой ячейке памяти хранится значение разделяемой переменной, то получить доступ к ней может только один процесс, несмотря на возможное совмещение выполнения команд во времени на различных процессорах (или на одном процессоре, но с конвейерной организацией параллельного выполнения команд).
Механизм блокировки памяти предотвращает одновременный доступ к разделяемой переменной, но не предотвращает чередование доступа. Таким образом, если критические интервалы исчерпываются одной командой обращения к памяти, данного средства может быть достаточно для непосредственной реализации взаимного исключения. Если же критические секции требуют более одного обращения к памяти, то задача становится сложной, но алгоритмически разрешимой. Рассмотрим различные попытки использования механизма блокировки памяти для организации взаимного исключения при выполнении критических интервалов и покажем некоторые важные моменты, пренебрежение которыми приводит к неприемлемым или даже ошибочным решениям.
Возможные проблемы при организации взаимного исключения посредством использования только блокировки памяти
Пусть имеются два (или более) циклических процесса, в которых есть абстрактные критические секции, то есть каждый из процессов состоит из двух частей: некоторого критического интервала и оставшейся части кода, в которой нет работы с общими (критическими) переменными. Пусть эти два процесса асинхронно разделяют во времени единственный процессор либо выполняются на отдельных процессорах, каждый из которых имеет доступ к некоторой общей области памяти, с которой и работают критические секции. Проиллюстрируем эту ситуацию с помощью рис. 6.4.
Рис. 6.4. Модель взаимодействующих процессов
Проблема кажется легко решаемой, если потребовать, чтобы процессы ПР1 и ПР2 входили в свои критические интервалы попеременно. Для этого одна общая переменная может хранить указатель того, чья очередь войти в критическую секцию. Текст такого решения на языке, близком к Pascal, приведен в листинге 6.1.
Листинг 6.1. Первый вариант попытки реализации взаимного исключения
var перекл : integer;
begin перекл := 1; {при перекл=1 в CS находится процесс ПР1 }
parbegin
while true do
begin
while перекл = 2 do begin end;
CS1; { Критическая секция процесса ПР1 }
перекл := 2;
PR1; { оставшаяся часть процесса ПР1 }
end
and
while true do
begin
while перекл = 1 do begin end;
CS2; { Критическая секция процесса ПР2 }
перекл := 1;
PR2; { оставшаяся часть процесса ПР2 }
end
parend
end.
Здесь и далее конструкция следующего типа
parbegin...S11;S12; ... ; S1N1
and... S21; S22; ... ; S2N2
and... SK1; SK2; ... ; SKNk
parend
означает параллельность К описываемых последовательных процессов. Конструкция из операторов S11; S12; ... ; S1N1 выполняется оператор за оператором, о чем свидетельствует наличие точки с запятой между операторами.
Конструкция
while true do
begin S1; S2;…SN end
означает, что каждый процесс может выполняться неопределенное время. Конструкция типа begin end означает «пустой» оператор.
Итак, решение, представленное в листинге 6.1, обеспечивает взаимное исключение в работе критических интервалов. Однако если бы часть программы PR1 была намного длиннее, чем программа PR2, или если бы процесс ПР1 был заблокирован в секции PR1, или если бы процессор для ПР2 был с большим быстродействием, то процесс ПР2 вскоре вынужден был бы ждать (и, может быть, чрезвычайно долго) входа в свою критическую секцию CS2, хотя процесс ПР1 и был бы вне CS1. То есть при таком решении один процесс вне своей критической секции может помешать вхождению другого в свою критическую секцию.
Попробуем устранить это блокирование с помощью использования двух общих переключателей, которые используются как флаги для указания, находится ли соответствующий процесс вне своей критической секции.
Пусть с каждым из процессов ПР1 и ПР2 будет связана переменная, по смыслу являющаяся переключателем, которая принимает значение true, когда процесс находится в своем критическом интервале, и false — в противном случае. Прежде чем войти в свой критический интервал, процесс проверяет значение переключателя другого процесса. Если это значение равно true, процессу не разрешается входить в свой критический интервал. В противном случае процесс «включает» свой собственный переключатель и входит в критический интервал. Этот алгоритм взаимного исключения представлен в листинге 6.2.
Данный алгоритм не гарантирует полного выполнения условия нахождения только одного процесса внутри критического интервала. Отсутствие гарантий связано с различными, в общем случае, скоростями развития процессов. Поэтому, например, между проверкой значения переменной перекл2 процессом ПР1 и последующей установкой им значения переменной перекл1 параллельно выполняющийся процесс ПР2 может установить перекл2 в значение true, так как перекл1 еще не успел установиться в значение true. Отсюда следует, что оба процесса могут войти одновременно в свои критические интервалы.
Листинг 6.2. Второй вариант попытки реализации взаимного исключения
Var перекл1,перекл2: boolean;
begin перекл1:=false;
перекл2:=false;
parbegin
while true do
begin
while перекл2 do
begin end;
переклl:=true;
CS1; (* Критический интервал процесса ПР1 *)
nepeклl:=false:
PR1; (* процесс ПР1 после критического интервала *)
end
and
while true do
begin
while перекл1 do
begin end;
перекл2:=true;
CS2; (* Критический интервал процесса ПР2 *)
перекл2:=fa1se;
PR2; (* процесс ПР2 после критического интервала *)
end
parend
end.
Следующий (третий) вариант решения этой задачи (листинг 6.3) усиливает взаимное исключение, так как в процессе ПР1 проверка значения переменной перекл2 выполняется после установки переменной перекл1 в значение true (аналогично для ПР2).
Листинг 6.3. Третий вариант попытки реализации взаимного исключения
var перекл1,перекл2 : boolean;
begin перекл1:=false;
перекл2:=false;
parbegin
ПР1: while true do
begin
перекл1:=true:
while перекл2 do
begin end;
CS1;{ Критический интервал процесса ПР1 }
перекл1:=false;
PR1;{ ПР1 после критического интервала }
end
and
ПР2: while true do
begin
перекл2:=trueж
while перекл1 do
begin end;
CS2; { Критический интервал процесса ПР2 }
перекл2:=false;
PR2; { ПР2 после критического интервала }
end
parend
end.
Алгоритм, приведенный в листинге 6.3, также имеет свои недостатки. Действительно, возможна ситуация, когда оба процесса одновременно установят свои переключатели в значение true и войдут в бесконечный цикл. В этом случае будет нарушено требование отсутствия бесконечного ожидания входа в свой критический интервал. Предположив, что скорости исполнения процессов произвольны, мы получили такую последовательность событий, при которой процессы вообще перестанут нормально выполняться.
Рассмотренные попытки решить проблему критических интервалов иллюстрируют некоторые тонкости, лежащие в основе этой проблемы.
Последний вариант решения задачи взаимного исключения, использующий только блокировку памяти, который мы рассмотрим, — это известный алгоритм, предложенный математиком Деккером.
Программное обеспечение это общий термин для обозначения quot неосязаемых quot в отличие от физических составных частей компьютерной системы... Программное обеспечение можно разделить на две группы системное программное... СПО управляет ресурсами компьютерной системы и позволяет пользователям программировать в более выразительных языках...
Системное программное обеспечение
В англоязычной технической литературе термин System Software (системное программное обеспечение) означает программы и комплексы программ, являющиеся общими для всех, кто совместно использует техн
Понятие операционной среды
Операционная система выполняет функции управления вычислительными процессами в вычислительной системе, распределяет ресурсы вычислительной системы между различными вычислительными процессами и об
Понятия вычислительного процесса и ресурса
Понятие «вычислительный процесс» (или просто — «процесс») является одним из основных при рассмотрении операционных систем. Последовательный процесс (иногда называемый «задачей») — это выполнение от
Диаграмма состояний процесса
Необходимо различать системные управляющие процессы, представляющие работу супервизора операционной системы и занимающиеся распределением и управлением ресурсов, от всех других процессов: системн
Реализация понятия последовательного процесса в ОС
Контекст и дескриптор процесса
На протяжении существования процесса его выполнение может быть многократно прервано и продолжено. Для того, чтобы возобновить выполнение процесса, необходимо
Процессы и треды
Понятие процесса было введено для реализации идей мультипрограммирования. Напомним, в свое время различали термины «мультизадачность» и «мультипрограммирование». Таким образом, для реализации «мул
Прерывания
Прерывания представляют собой механизм, позволяющий координировать параллельное функционирование отдельных устройств вычислительной системы и реагировать на особые состояния, возникающие при работ
Основные виды ресурсов
Рассмотрим кратко основные виды ресурсов вычислительной системы и способы их разделения. Прежде всего, одним из важнейших ресурсов является сам процессор, точнее — процессорное время. Процессорное
Управление задачами в операционных системах
Итак, время центрального процессора и оперативная память являются основными ресурсами в случае реализации мультипрограммных вычислений.
Оперативная память — это важнейший ресурс любой вычи
Стратегии планирования
Прежде всего следует отметить, что при рассмотрении стратегий планирования, как правило, идет речь о краткосрочном планировании, то есть о диспетчеризации. Долгосрочное планирование, как мы уже от
Дисциплины диспетчеризации
Когда говорят о диспетчеризации, то всегда в явном или неявном виде имеют в виду понятие задачи (потока). Если ОС не поддерживает механизм тредов, то можно заменять понятие задачи на понятие процес
Вытесняющие и не вытесняющие алгоритмы диспетчеризации
Диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая многозадачность (non-preemptive multitasking) — это такой способ диспетчеризации процессов, при котором активный
Диспетчеризация задач с использованием динамических приоритетов
При выполнении программ, реализующих какие-либо задачи контроля и управления (что характерно, прежде всего, для систем реального времени), может случиться такая ситуация, когда одна или несколько
Управление памятью.
Память является важнейшим ресурсом, требующим тщательного управления со стороны мультипрограммной операционной системы. Распределению подлежит вся оперативная память, не занятая операционной систем
Управление вводом/выводом
Необходимость обеспечить программам возможность осуществлять обмен данными с внешними устройствами и при этом не включать в каждую двоичную программу соответствующий двоичный код, осуществляющий с
Режимы управления вводом/выводом
Как известно, имеются два основных режима ввода/вывода: режим обмена с опросом готовности устройства ввода/вывода и режим обмена с прерываниями. Рассмотрим рис. 4.1.
Закрепление устройств, общие устройства ввода/вывода
Как известно, многие устройства не допускают совместного использования. Прежде всего, это устройства с последовательным доступом. Такие устройства могут стать закрепленными, то есть быть предостав
Основные системные таблицы ввода/вывода
Каждая ОС имеет свои таблицы ввода/вывода, их состав (количество и назначение каждой таблицы) может сильно отличаться. В некоторых ОС вместо таблиц создаются списки, хотя использование статических
Синхронный и асинхронный ввод/вывод
Задача, выдавшая запрос на операцию ввода/вывода, переводится супервизором в состояние ожидания завершения заказанной операции. Когда супервизор получает от секции завершения сообщение о том, что
Файловая система.
Файловая система - это часть операционной системы, назначение которой состоит в том, чтобы обеспечить пользователю удобный интерфейс при работе с данными, хранящимися на диске, и обеспечить совмест
Имена файлов
Файлы идентифицируются именами. Пользователи дают файлам символьные имена, при этом учитываются ограничения ОС как на используемые символы, так и на длину имени. До недавнего времен
Типы файлов
Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.
Обычные файлы в свою очередь подразделяются на текстовые и двоичные. Текстовые
Логическая организация файла
Программист имеет дело с логической организацией файла, представляя файл в виде определенным образом организованных логических записей. Логическая запись - это наименьший элемент да
Физическая организация и адрес файла
Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности на диске. Файл состоит из физических записей - блоков. Блок - наименьшая
Кэширование диска
В некоторых файловых системах запросы к внешним устройствам, в которых адресация осуществляется блоками (диски, ленты), перехватываются промежуточным программным слоем-подсистемой б
Общая модель файловой системы
Функционирование любой файловой системы можно представить многоуровневой моделью, в
которой каждый уровень предоставляет некоторый интерфейс (набор функций) вышележащему уровню, а сам, в с
Отображаемые в память файлы
По сравнению с доступом к памяти, традиционный доступ к файлам выглядит запутанным и неудобным. По этой причине некоторые ОС, начиная с MULTICS, обеспечивают отображение файлов в ад
Современные архитектуры файловых систем
Разработчики новых операционных систем стремятся обеспечить пользователя возможностью работать сразу с несколькими файловыми системами. В новом понимании файловая система состоит из
Принципы построения интерфейсов операционных систем
Напомним, что ОС всегда выступает как интерфейс между аппаратурой компьютера и пользователем с его задачами. Под интерфейсами операционных систем здесь и далее следует понимать специальные интерфе
Интерфейс прикладного программирования
Прежде всего необходимо однозначно разделить общий термин API (application program interface, интерфейс прикладного программирования) на следующие направления:
API как интерфейс высо
Реализация функций API на уровне ОС
При реализации функций API на уровне ОC за их выполнение ответственность несет ОС. Объектный код, выполняющий функции, либо непосредственно входит в состав ОС (или даже ядра ОС), либо поставляется
Реализация функций API на уровне системы программирования
Если функции API реализуются на уровне системы программирования, они предоставляются пользователю в виде библиотеки функций соответствующего языка программирования. Обычно речь идет о библиотеке
Реализация функций API с помощью внешних библиотек
При реализации функций API с помощью внешних библиотек они предоставляются пользователю в виде библиотеки процедур и функций, созданной сторонним разработчиком. Причем разработчиком такой библиот
Платформенно-независимый интерфейс POSIX
POSIX (Portable Operating System Interface for Computer Environments) — платформенно независимый системный интерфейс для компьютерного окружения. Это стандарт IEEE, описывающий системные интерфейсы
Независимые и взаимодействующие вычислительные процессы
Основной особенностью мультипрограммных операционных систем является то, что в их среде параллельно развивается несколько (последовательных) вычислительных процессов. С точки зрения внешнего наблю
Алгоритм Деккера
Алгоритм Деккера основан на использовании трех переменных (листинг 6.4): перекл1, перекл2 и ОЧЕРЕДЬ. Пусть по-прежнему переменная перекл1=true тогда, когда процесс ПР1 хочет войти в свой критическ
Семафорные примитивы Дейкстры
Понятие семафорных механизмов было введено Дейкстрой. Семафор — переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух операций: «закрытия» и «отк
Мьютексы
Одним из вариантов семафорных механизмов для организации взаимного исключения являются так называемые мъютексы (mutex). Термин mutex произошел от английского словосочетания mutual exclusion semap
Мониторы Хоара
Анализ рассмотренных задач показывает, что, несмотря на очевидные достоинства (простота, независимость от количества процессов, отсутствие «активного ожидания»), семафорные механизмы имеют и ряд н
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Новости и инфо для студентов