Синхронизация и взаимодействие процессов кратко

Обновлено: 07.07.2024

Процесс (задача) – программа, находящаяся в режиме выполнения.

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

Способы взаимодействия процессов:

1) Разделяемая память;

2) Каналы – псевдофайл, в который один процесс пишет, другой из него читает. Каналы могут быть реализованы как в пределах одного компьютера, так и по сети при помощи сокетов;

3) Сокеты – механизм, поддерживаемый ОС, предоставляющий возможность взаимодействия между процессами как в пределах одного компьютера, так и между двумя компьютерами по сети;

4) Механизм вызовов удаленных процедур (RPC), обеспечивающий передачу управления удаленному процессу.

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

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

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

Критические секции могут быть реализованы с использованием блокирующих переменных. Для синхронизации процессов в операционных системах применяются следующие механизмы:

1) Критические секции (critical section) – механизм, частный случай мьютексов в системах Windows. Представляет собой системную переменную, к которой получает непосредственный доступ только операционная система. Потоки же устанавливают эту переменную с помощью вызовов функций enter() и leave(). Если переменная занята одним потоком, никакой другой поток не может исполнить код, огражденный вызовами функций enter и leave. Критическая секция обеспечивает синхронизацию потоков только в пределах одного процесса.

2) Семафор – объект, позволяющий войти в заданный участок кода не более чем n потокам. Над семафором можно производить 3 операции: инициализацию некоторым значением, инкремент (Up) и декремент (Down). Прежде чем заблокировать процесс, Down проверяет семафор, если он равен нулю, то он блокирует процесс, если нет, то процесс снова становится активным, и уменьшает семафор на единицу. Up увеличит значение семафора на 1 или разблокирует процесс находящийся в ожидании. Down и Up выполняются как элементарное действие, т.е. процесс не может быть блокирован во время выполнения этих операций.

3) Мьютекс – одноместный семафор, один из вариантов семафорных механизмов для организации взаимного исключения. Они реализованы во многих ОС, их основное назначение — организация взаимного исключения для потоков из одного или из разных процессов. Мьютексы могут находиться в одном из двух состояний — отмеченном или неотмеченном (открыт и закрыт соответственно). Когда какой-либо поток, принадлежащий любому процессу, становится владельцем объекта мьютекса, последний переводится в неотмеченное состояние. Когда поток освобождает мьютекс, его состояние становится отмеченным. Ожидающие освобождения мьютекса процессы выстраиваются в очередь.

4) Механизм событий – более общий механизм для синхронизации. В разных операционных системах аппарат событий реализуется по-своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

4.4. Файловая система.

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

В широком смысле понятие "файловая система" включает:

§ совокупность всех файлов на диске,

§ наборы структур данных, используемых для управления файлами, такие, например, как каталоги файлов, дескрипторы файлов, таблицы распределения свободного и занятого пространства на диске,

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

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

Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.

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

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

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

Иерархия каталогов может быть деревом или сетью. Каталоги образуют дерево, если файлу разрешено входить только в один каталог, и сеть - если файл может входить сразу в несколько каталогов. В MS-DOS каталоги образуют древовидную структуру, а в UNIX'е - сетевую.

Физическая организация файла описывает правила расположения файла на устройстве внешней памяти, в частности на диске. Файл состоит из физических записей - блоков. Блок - наименьшая единица данных, которой внешнее устройство обменивается с оперативной памятью.

Варианты размещения файлов на диске:

1) Непрерывное размещение – простейший вариант физической организации, при котором файлу предоставляется последовательность блоков диска, образующий единый сплошной участок дисковой памяти.

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

3) Использование связанного списка индексов, который хранится в специальной таблице дисковой памяти (FAT в Windows). Если некоторый блок распределен некоторому файлу, то индекс этого блока содержит номер следующего блока данного файла.

4) Перечисление номеров блоков, занимаемым файлом.

Для того, чтобы определить для каждого пользователя список операций, которые он может производить с данным файлом, файловая система обеспечивает механизм прав доступа. В некоторых системах пользователи могут быть разделены на отдельные категории. Для всех пользователей одной категории определяются единые права доступа. Например, в системе UNIX все пользователи подразделяются на три категории: владельца файла, членов его группы и всех остальных.

Процесс (задача) – программа, находящаяся в режиме выполнения.

Способы взаимодействия процессов:

1) Разделяемая память;

4) Механизм вызовов удаленных процедур (RPC), обеспечивающий передачу управления удаленному процессу.

4.4. Файловая система.

В широком смысле понятие "файловая система" включает:

§ совокупность всех файлов на диске,

Файлы бывают разных типов: обычные файлы, специальные файлы, файлы-каталоги.

Варианты размещения файлов на диске:

4) Перечисление номеров блоков, занимаемым файлом.

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни.

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

Способы взаимодействия процессов (потоков) можно классифицировать по степени осведомленности одного процесса о существовании другого [10].

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

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

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

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

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

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

В случае конкурирующих процессов (потоков) возможно возникновение трех проблем. Первая из них – необходимость взаимных исключений ( mutual exclusion ). Предположим, что два или большее количество процессов требуют доступ к одному неразделяемому ресурсу, как например принтер (рис. 5.12). О таком ресурсе будем говорить как о критическом ресурсе , а о части программы, которая его использует, – как о критическом разделе ( critical section ) программы. Крайне важно, чтобы в критической ситуации в любой момент могла находиться только одна программа . Например, во время печати файла требуется, чтобы отдельный процесс имел полный контроль над принтером, иначе на бумаге можно получить чередование строк двух файлов.

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

Очень удобно моделировать условия возникновения тупиков , используя направленные графы [17] (предложено Holt, 1972). Графы имеют 2 вида узлов: процессы-кружочки и ресурсы-квадратики. Ребро , направленное от квадрата (ресурса) к кружку (процессу), означает, что ресурс был запрошен, получен и используется. В нашем примере это будет изображено так, как показано на рис. 5.13 а).

Ребро , направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу. В нашем примере граф надо достроить, как показано на рис. 5.13 б) или в). Цикл в графе означает наличие взаимной блокировки процессов.

Существует еще одна проблема у конкурирующих процессов – голодание. Предположим, что имеется 3 процесса ( Р1 , Р2 , Р3 ), каждому из которых периодически требуется доступ к ресурсам R. Представим ситуацию, в которой Р1 обладает ресурсом, а Р2 и Р3 приостановлены в ожидании освобождения ресурса R. После выхода Р1 из критического раздела доступ к ресурсу будет получен одним из процессов Р2 или Р3 .

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

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

Однако в этом случае вносится новое требование синхронизации процессов для обеспечения согласованности данных.

Пусть имеются два процесса, представленные последовательностью неделимых (атомарных) операций:

P: a; b; c; и Q: d; e; f;

где a, b, c, d, e, f – атомарные операции .

При последовательном выполнении активностей мы получаем следующую последовательность атомарных действий:

Что произойдет при исполнении этих процессов псевдопараллельно, в режиме разделения времени? Процессы могут расслоиться на неделимые операции с различным их чередованием, то есть может произойти то, что на английском языке принято называть словом interleaving . Возможные варианты чередования:

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

Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются общими для процессов? Легко видеть, что возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2) . Будем говорить, что набор процессов детерминирован, если всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные . В противном случае он недетерминирован. Выше приведен пример недетерминированного набора программ. Понятно, что детерминированный набор активностей можно безбоязненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.

Можно ли до получения результатов, заранее, определить, является ли набор активностей детерминированным или нет? Для этого существуют достаточные условия Бернстайна [17]. Изложим их применительно к программам с разделяемыми переменными.

Введем наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных – это наборы переменных, которые атомарная операция считывает и записывает. Набор входных переменных программы R(P) ( R от слова read ) суть объединение наборов входных переменных для всех ее неделимых действий. Аналогично, набор выходных переменных программы W(P) ( W от слова write ) суть объединение наборов выходных переменных для всех ее неделимых действий. Например, для программы

получаем R(P) = , W(P) = . Заметим, что переменная x присутствует как в R(P) , так и в W(P) .

Теперь сформулируем условия Бернстайна .

Если для двух данных процессов P и Q :

пересечение W(P) и W(Q) пусто,
пересечение W(P) с R(Q) пусто,
пересечение R(P) и W(Q) пусто,

тогда выполнение P и Q детерминировано.

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

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

Про недетерминированный набор программ говорят, что он имеет race condition ( состояние гонки , состояние состязания). В приведенном выше примере процессы состязаются за вычисление значений переменных x и y.

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

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

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

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

Из этого руководства по операционной системе вы узнаете:

Как работает синхронизация процессов?

Например, процесс A изменяет данные в ячейке памяти, в то время как другой процесс B пытается прочитать данные из той же ячейки памяти. Существует высокая вероятность того, что данные, прочитанные вторым процессом, будут ошибочными.

Разделы программы

Вот четыре основных элемента критического раздела:

Что такое проблема критического сечения?

Критическая секция — это сегмент кода, который может быть доступен при обработке сигнала в определенный момент времени. Раздел состоит из общих ресурсов данных, которые должны быть доступны для других процессов.

Запись в критическую секцию обрабатывается функцией wait () и представляется как P ().
Выход из критической секции контролируется функцией signal (), представленной как V ().

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

Правила для критического раздела

В критическом разделе должны соблюдаться все три правила:

Решения для критического раздела

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

Вот несколько широко используемых методов для решения проблемы критического сечения.

Peterson Solution

Решение Петерсона является широко используемым решением критических проблем сечения. Этот алгоритм был разработан компьютерным ученым Петерсоном, поэтому он назван решением Петерсона.

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

пример

Предположим, что существует N процессов (P1, P2, … PN), и каждый процесс в какой-то момент времени требует входа в критический раздел
Поддерживается массив FLAG [] размера N, который по умолчанию равен false. Поэтому, когда процессу требуется войти в критическую секцию, он должен установить свой флаг как true. Например, если Pi хочет войти, он установит FLAG [i] = TRUE.
Другая переменная с именем TURN указывает номер процесса, который в настоящее время ожидает ввода в CS.
Процесс, который входит в критическую секцию при выходе, изменит ОБОРОТ на другой номер из списка готовых процессов.
Пример: поворот равен 2, затем P2 входит в критическую секцию и при выходе из хода = 3, и, следовательно, P3 выходит из цикла ожидания.

Оборудование для синхронизации

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

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

Мьютекс Замки

Аппаратное обеспечение синхронизации не простой метод для реализации для всех, поэтому был также введен строгий программный метод, известный как Mutex Locks.

При таком подходе в разделе ввода кода получается LOCK для критических ресурсов, используемых внутри критического раздела. В секции выхода эта блокировка снята.

Семафорное Решение

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

Он использует две атомарные операции: 1) ожидание и 2) сигнал для синхронизации процесса.

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

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

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

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

Существуют в основном две проблемы взаимодействия процессов, это:

Для исключения проблем при обмене данными между процессами, разделении данных, при доступе к процессору и устройствам ввода-вывода необходимасинхронизация.

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

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

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

Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш .

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

Во многих ОС эти средства называются средствами межпроцессного взаимодействия — Inter Process Communication (IРС). Обычно к средствам IРС относят не только средства межпроцессной синхронизации, но и средства межпроцессного обмена данными.

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

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

Возникновение гонок при доступе к разделяемым данным

характеристики вычислительного процесса, например вероятность его завершения за данный период времени.

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

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

Рассмотрим, например, задачу ведения базы данных клиентов некоторого предприятия.

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

-поток А заносит в базу данных информацию о заказах, поступивших от клиентов, и

-поток В фиксирует в базе данных сведения об оплате клиентами выставленных счетов.

Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага:

1. Считать из файла базы данных в буфер запись о клиенте с заданным иденти-фикатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

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

Обозначим соответствующие шаги для потока А как А1, А2 и А3, а для потока В как В1, В2 и В3.

Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг А3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.

Предположим также, что потоку В потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. В буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

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

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

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

Проблема гонок может решаться:

1) приостановкой и активизацией процессов,

2) организацией очередей,

3) блокированием и освобождением ресурсов.

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

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

Очень удобно моделировать условия возникновения ткпиков, используя напрвленные графы. Графы имеют 2 вида узлов:процессы – кружочки, ресурсы – квадратики.

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

Исходное распределение ресурсов

Ребро, направленное от процесса (кружка) к ресурсу (квадрату), означает, что процесс в данный момент заблокирован и находится в состоянии ожидания доступа к этому ресурсу.

В нашем случае получим следующий граф

Цикл в графе означает наличие взаимной блокировки процессов.

В общем случае проблема тупиков эффективного решения не имеет.

Рассмотрим пример аппаратного тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, диск и последовательный порт. На следующем рисунке показаны фрагменты соответствующих программ.

Возникновение взаимных блокировок при выполнении программы

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

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

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

Очередь - это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Она возникает тогда, когда ресурс недоступен в данный момент, но через некоторое время он освободится, и процесс продолжает свое выполнение. Тупик же является в некотором роде неразрешимой ситуацией.

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

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

Условия возникновения тупиков были сформулированы Коффманом, Элфиком и Шошани в 1970 г.

1. Условие взаимоисключения (Mutual exclusion). Одновременно использовать ресурс может только один процесс.

2. Условие ожидания ресурсов (Hold and wait). Процессы удерживают ресурсы, уже выделенные им, и могут запрашивать другие ресурсы.

3. Условие неперераспределяемости (No preemtion). Ресурс, выделенный ранее, не может быть принудительно забран у процесса. Освобожден он может только процессом, который их удерживает.

4. Условие кругового ожидания (Circular wait). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.

Для образования тупика необходимым и достаточным является выполнение всех четырех условий.

Основные направления борьбы с тупиками:

- игнорирование данной проблемы;

- распознавание тупиков и восстановление системы после тупиков.

Важным понятием синхронизации процессов является понятие «критической секции« программы.

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

- антидедлоки и т.д.

Вопрос 18.

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

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

Вопрос 20.

Алгоритм Петерсона

Первое решение проблемы, удовлетворяющее всем требованиям и использующее идеи ранее рассмотренных алгоритмов, было предложено датским математиком Деккером (Dekker). В 1981 году Петерсон (Peterson) предложил более изящное решение. Пусть оба процесса имеют доступ к массиву флагов готовности и к переменной очередности.

shared int ready[2] = ;

shared int turn;

while (some condition)

При исполнении пролога критической секции процесс P_i заявляет о своей готовности выполнить критический участок и одновременно предлагает другому процессу приступить к его выполнению. Если оба процесса подошли к прологу практически одновременно, то они оба объявят о своей готовности и предложат выполняться друг другу. При этом одно из предложений всегда следует после другого. Тем самым работу в критическом участке продолжит процесс, которому было сделано последнее предложение.

Давайте докажем, что все пять наших требований к алгоритму действительно удовлетворяются.

Удовлетворение требований 1 и 2 очевидно.

Докажем выполнение условия взаимоисключения методом от противного. Пусть оба процесса одновременно оказались внутри своих критических секций. Заметим, что процесс P_i может войти в критическую секцию, только если ready[1-i] == 0 или turn == i. Заметим также, что если оба процесса выполняют свои критические секции одновременно, то значения флагов готовности для обоих процессов совпадают и равны 1. Могли ли оба процесса войти в критические секции из состояния, когда они оба одновременно находились в процессе выполнения цикла while? Нет, так как в этом случае переменная turn должна была бы одновременно иметь значения 0 и 1 (когда оба процесса выполняют цикл, значения переменных измениться не могут). Пусть процесс P₀ первым вошел в критический участок, тогда процесс P₁ должен был выполнить перед вхождением в цикл while по крайней мере один предваряющий оператор (turn = 0;). Однако после этого он не может выйти из цикла до окончания критического участка процесса P₀, так как при входе в цикл ready[0] == 1 и turn == 0, и эти значения не могут измениться до тех пор, пока процесс P₀ не покинет свой критический участок. Мы пришли к противоречию. Следовательно, имеет место взаимоисключение.

Докажем выполнение условия прогресса. Возьмем, без ограничения общности, процесс P₀. Заметим, что он не может войти в свою критическую секцию только при совместном выполнении условий ready[1] == 1 и turn == 1. Если процесс P₁ не готов к выполнению критического участка, то ready[1] == 0, и процесс P₀ может осуществить вход. Если процесс P₁готов к выполнению критического участка, то ready[1] == 1 и переменная turn имеет значение 0 либо 1, позволяя процессу P₀ либо процессу P₁ начать выполнение критической секции. Если процесс P₁ завершил выполнение критического участка, то он сбросит свой флаг готовности ready[1] == 0, разрешая процессу P₀ приступить к выполнению критической работы. Таким образом, условие прогресса выполняется.

Отсюда же вытекает выполнение условия ограниченного ожидания. Так как в процессе ожидания разрешения на вход процесс P₀ не изменяет значения переменных, он сможет начать исполнение своего критического участка после не более чем одного прохода по критической секции процесса P₁.

Читайте также: