Взаимодействие процессов и задача их синхронизации
Синхронизация процессов в ОС
Процессам часто нужно взаимодействовать друг с другом с целью совместного использования аппаратных и информационных ресурсов вычислительной системы, например, один процесс может передавать данные другому процессу, или несколько процессов могут обрабатывать данные из общего файла.
Процессы в общем случае протекают независимо, асинхронно друг другу.Одной из функций ОС явялется обеспечение санкционированного взаимодействия процессов.
Взаимодействие процессв в вычислительной системе напоминает жизнь в коммунальной квартире. Постоянное ожидание в очереде к местам общего пользования (процессору) и ежедневная борьба за ресуосы (кто опять занял все конфорки на плите?)
Для нормального функционирования процессов ОС старается максимально обособить их друг от друга. Каждый процесс имеет собственное адресное пространство (каждая семья должна жить в отдельной комнате), нарушение которого, как правило, приводит к аварийной остановке процесса(вызов милиции). Каждому процессу по возможности предоставляются свои дополнительные ресурсы (каждая семья предпочитает иметь собственный холодильник). Тем не менее для решения некотопых задач (приготовление праздничного стола на всю кваритиру) процессы могут объединять свои усилия.
Существуют в основном две проблемы взаимодействия процессов, это:
- «конкуренция» процессов в борьбе за ресурсы;
- «сотрудничество» с использованием разделяемых переменных, совместно используемых данных или баз данных.
Для исключения проблем при обмене данными между процессами, разделении данных, при доступе к процессору и устройствам ввода-вывода необходима синхронизация.
Любое взаимодействие процессов связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки процесса до наступления некоторого события и последующей его активизации при наступлении этого события.
Синхронизация лежит в основе любого взаимодействия процессов, связано ли это взаимодействие с разделением ресурсов или с обменом данными. Например(синхронизация по информации), поток-получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился к данным до момента их поступления в буфер, то он должен быть приостановлен.
Например(синхронизация при совместном использовании аппаратных ресурсов), активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в данный момент в состоянии ожидания, то ОС приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится.
Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш <Сtrl+С>.
Ежесекундно в ВС происходит сотни событий, связанных с распределением и освобождение ресурсов. Поэтому ОС должна иметь надежные и производительные средства, позволяющие ей синхронизировать процессы с происходящими в системе событиями.
Во многих ОС эти средства называются средствами межпроцессного взаимодействия — 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). Существует кольцевая цепь процессов, в которой каждый процесс ждет доступа к ресурсу, удерживаемому другим процессом цепи.
Для образования тупика необходимым и достаточным является выполнение всех четырех условий.
Основные направления борьбы с тупиками:
- игнорирование данной проблемы;
- обнаружение тупиков,
- распознавание тупиков и восстановление системы после тупиков.
- предотвращение тупиков.
Важным понятием синхронизации процессов является понятие «критической секции« программы.
Критическая секция - это часть программы, в которой осуществляется доступ к разделяемым ресурсам. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. В нашем примере такими критическими данными являлись записи файла базы данных. Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этим ресурсом, находилось не более одного процесса. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение - позволить процессу, находящемуся в критической секции, запрещать все прерывания на время его нахождения в критической секции. Однако этот способ непригоден, так как опасно доверять управление системой пользовательскому процессу; он может надолго занять процессор, а при крахе процесса в критической области крах потерпит вся система, потому что прерывания никогда не будут разрешены.ОС использует разные способы взаимного исключения:
Процесс
Ресурс
