Понятие процесса F(x)= x F(4)=?F(1)=? t Понятие процесса характеризует некоторую совокупность набора исполняющихся команд, ассоциированных с ним ресурсов (выделенная для исполнения память или адресное пространство, стеки, используемые файлы и устройства ввода-вывода и т. д.) и текущего момента его выполнения (значения регистров, программного счетчика, состояние стека и значения переменных), находящуюся под управлением операционной системы. Не существует взаимно- однозначного соответствия между процессами и программами, обрабатываемыми вычислительными системами.

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

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

Набор операций создание процесса – завершение процесса; приостановка процесса (перевод из состояния исполнение в состояние готовность) – запуск процесса (перевод из состояния готовность в состояние исполнение); блокирование процесса (перевод из состояния исполнение в состояние ожидание) – разблокирование процесса (перевод из состояния ожидание в состояние готовность) ; изменение приоритета процесса.

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

Упрощенный генеалогический лес процессов При рождении процесса система заводит новый PCB с состоянием процесса рождение и начинает его заполнять. Новый процесс получает собственный уникальный идентификационный номер. После завершения какого- либо процесса его освободившийся идентификационный номер может быть повторно использован для другого процесса.Процесс, инициировавший создание нового процесса, принято называть процессом-родителем (parent process), а вновь созданный процесс – процессом-ребенком (child process). Процессы-дети могут в свою очередь порождать новых детей и т. д., образуя, в общем случае, внутри системы набор генеалогических деревьев процессов – генеалогический лес.

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

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

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

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

алгоритмы, основанные на приоритетах: В системах с относительными приоритетами активный процесс выполняется до тех пор, пока он сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение активного процесса прерывается еще при одном условии: если в очереди готовых процессов появился процесс, приоритет которого выше приоритета активного процесса. В этом случае прерванный процесс переходит в состояние готовности. На рисунке показаны графы состояний процесса для алгоритмов с относительными (а) и абсолютными (б) приоритетами.

Проблема синхронизации

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

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связы- вается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связан- ной с данным процессом), и значение 0, если ресурс занят. Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

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

Тупики

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

Интервал между двумя последовательными достижениями солнцем наивысшей точки на небе называется солнечным днем. Солнечная секунда равняется 1/86400(24*3600) части солнечного дня. В 1940-х годах было установлено, что период вращения земли не постоянен - земля замедляет вращение из-за приливов и атмосферы. Геологи считают, что 300 миллионов лет назад в году было 400 дней. Происходят и изменения длительности дня по другим причинам. Поэтому стали вычислять за длительный период среднюю солнечную секунду. В настоящее время 50 лабораторий в разных точках земли имеют часы, базирующиеся на частоте излучения Цезия-133. Среднее значение является международным атомным временем (TAI), исчисляемым с 1 июля 1958 года. Отставание TAI от солнечного времени компенсируется становится добавлением секунды тогда, когда разница больше 800 мксек. Это скорректированное время, называемое UTC (Universal Coordinated Time), заменило прежний стандарт (Среднее время по Гринвичу - астрономическое время). Синхронизация времени

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

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

Ставится задача создания такого механизма ведения времени, который бы для каждого события а мог указать значение времени Т(а), с которым бы были согласны все процессы в системе. При этом должно выполняться условие: если а ® b, то Т(а) < Т(b). Кроме того, время может только увеличиваться и, следовательно, любые корректировки времени могут выполняться только путем добавления положительных значений, и никогда - путем вычитания. Рассмотрим алгоритм решения этой задачи, который предложил Lamport. Для отметок времени в нем используются события. На рисунке показаны три процесса, выполняющихся на разных машинах, каждая из которых имеет свои часы, идущие со своей скоростью. Как видно из рисунка, когда часы процесса 0 показали время 6, в процессе 1 часы показывали 8, а в процессе Предполагается, что все эти часы идут с постоянной для себя скоростью.

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

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

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

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

Алгоритм Token Ring Совершенно другой подход к достижению взаимного исключения в распределенных системах иллюстрируется следующим рисунком. Все процессы системы образуют логическое кольцо, т.е. каждый процесс знает номер своей позиции в кольце, а также номер ближайшего к нему следующего процесса. Когда кольцо инициализируется, процессу 0 передается так называемый токен. Токен циркулирует по кольцу. Он переходит от процесса n к процессу n+1 путем передачи сообщения. Когда процесс получает токен от своего соседа, он анализирует, не требуется ли ему самому войти в критическую секцию. Если да, то процесс входит в критическую секцию. После того, как процесс выйдет из критической секции, он передает токен дальше по кольцу. Если же процесс, принявший токен от своего соседа, не заинтересован во вхождении в критическую секцию, то он сразу отправляет токен в кольцо. Следовательно, если ни один из процессов не желает входить в критическую секцию, то в этом случае токен просто циркулирует по кольцу с высокой скоростью.

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

Неделимые транзакции Модель неделимой транзакции пришла из бизнеса. Представьте себе переговорный процесс двух фирм о продаже-покупке некоторого товара. В процессе переговоров условия договора могут многократно меняться, уточняться. Пока договор еще не подписан обеими сторонами, каждая из них может от него отказаться. Но после подписания контракта сделка (transaction) должна быть выполнена. Компьютерная транзакция полностью аналогична. Один процесс объявляет, что он хочет начать транзакцию с одним или более процессами. Они могут некоторое время создавать и уничтожать разные объекты, выполнять какие-либо операции. Затем инициатор объявляет, что он хочет завершить транзакцию. Если все с ним соглашаются, то результат фиксируется. Если один или более процессов отказываются (или они потерпели крах еще до выработки согласия), тогда измененные объекты возвращается точно к тому состоянию, в котором они находились до начала выполнения транзакции. Такое свойство "все-или-ничего" облегчает работу программиста.

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

32 Механизмы обеспечения синхронизации Средства синхронизации Низкоуровневые Централизованный алгоритм Алгоритм с круговым маркером Высокоуровневые Атомарные транзакции Двухфазный протокол утверждения

33 Низкоуровневые средства синхронизации Централизованный алгоритм – Все процессы запрашивают у координатора разрешения на вход в критическую секцию и ждут разрешения. – Координатор обслуживает запросы в порядке их поступления. – Получив разрешение координатора, процесс входит в критическую секцию. – Завершив работу, процесс докладывает об этом координатору. Алгоритм с круговым маркером – Все процессы образуют логическое кольцо, при этом каждый знает, кто следует за ним. – По кольцу циркулирует маркер, дающий право на критическую секцию. – Получив маркер, процесс либо входит в критическую секцию, держа маркер у себя, либо перенаправляет маркер дальше, если ему не нужна критическая секция. – Дважды подряд входить в критическую секцию, не отдавая маркер, нельзя.

34 Атомарные транзакции Атомарные транзакции это высокоуровневые средства синхронизации, представляющие логические единицы работы. – Логическая единица работы, как правило, является согласованием ряда операций. – Система, поддерживающая процесс транзакции, гарантирует, что если во время выполнения некоторых операций произошла ошибка, то все обновления будут аннулированы. – В результате транзакция либо полностью выполняется, либо полностью отменяется. – Транзакции пришли в программирование из области деловых отношений, когда переговоры могут вернуться к своему начальному состоянию в любой момент до заключения соглашения. Транзакции обеспечиваются администратором транзакций с помощью следующих операторов: – BEGIN_TRANSACTION объявляет начало транзакций; – END_TRANSACTION объявляет успешное завершение транзакции и утверждает ее; – ABORT_TRANSACTION указывает на неудачное завершение транзакции, в результате чего все изменения должны быть отменены, и восстанавливает начальные значения; – READ служит для чтения данных; – WRITE служит для записи данных.

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

36 Двухфазный протокол утверждения Двухфазный протокол утверждения важен в тех случаях, когда транзакция может взаимодействовать с несколькими независимыми администраторами ресурсов. – Каждый из них руководит своим собственным набором восстанавливаемых ресурсов и поддерживает собственный файл регистрации. – Для транзакции не имеет смысла выполнять оператор завершения отдельно для каждого из администраторов ресурсов. Вместо этого должна быть выполнена единая общесистемная команда END_TRANSACTION или ABORT_TRANSACTION. Рассмотрим пример работы координатора. Пусть транзакция успешно завершена и ее нужно утвердить. Координатор осуществляет двухфазный процесс. – Координатор записывает в протокол "транзакция готова к утверждению". Координируемые процессы, получив сообщение, записывают в свой протокол "готов к транзакции" и отсылают координатору сообщение "готов". Координатор в конце первой фазы собирает все сообщения о готовности. – Когда все ответы собраны, координатор записывает в протокол "транзакция утверждена" и рассылает всем процессам сообщение "транзакция утверждена". Координируемые процессы, получив сообщение, записывают в свой протокол "транзакция утверждена" и отсылают координатору "готов". Если все ответы во время первой фазы собрать не удалось или хотя бы один из ответов содержит отказ от транзакции, то координатор дает команду ABORT_TRANSACTION.

38 Тупики в распределенных системах Подобны тупикам в централизованных системах, только их еще сложнее обнаруживать и предотвращать. Стратегии, применяемые при борьбе с тупиками, таковы: Полное игнорирование проблемы ("алгоритм страуса"). Этот подход в распределенных системах так же популярен, как и в централизованных Обнаружение тупиков. Для этого существует два основных метода: – централизованное обнаружение тупиков заключается в распространении идеи графа распределения ресурсов на распределенную систему. Координатор строит единый граф для всех узлов системы и на нем выполняет редукцию (приведение) – распределенное обнаружение тупиков. В этом методе инициирование задачи обнаружения тупика начинает процесс, который подозревает, что система находится в тупике. Он посылает тем процессам, которые держат нужный ему ресурс, сообщение из трех информационных полей. Первое поле содержит номер процесса, инициировавшего поиск, и оно не меняется при дальнейшей пересылке. Второе и третье поля содержат соответственно номер процесса, который зависит от ресурса, и номер процесса, который держит этот ресурс. Если, в конце концов, сообщение вернется к тому процессу, который инициировал поиск, то он приходит к выводу, что система зациклена и он должен предпринять действия по ликвидации тупика Предотвращение тупиков в распределенных системах базируется на идее упорядочивания процессов по их временным меткам. Допустимой будет ситуация, когда "старший" процесс ждет ресурсы, которые захватил "младший" процесс. В обратном случае "младший" процесс должен отказаться от ожидания.