Критические области. Взаимное исключение с активным ожиданием.

Запрещение прерываний.

Самое простое решение заключается в запрещении всех прерываний при входе процесса в критическую область и разрешении прерываний при выходе из области.Если прерывания запрещены, то невозможно прерывание по таймеру. Поскольку процессор переключается с одного процесса на другой только по прерыванию. то отключение прерываний исключает передачу процессора другому процессу. Таким образом, запретив прерывания, процесс может спокойно считывать и сохранять совместно используемые данные, не опасаясь вмешательства другого процесса.
И все же было бы неразумно давать пользовательскому процессу возможность запрета прерываний. Представим, что процесс отключил все прерывания и в результате какого-либо сбоя не включил их обратно. Операционная система на этом моменте может закончить свое существование =)).
К тому жев многопроцессорной системе запрещение прерываний повлияет только на тот процессор, который выполнит инструкцию disable.Остальные процессоры продолжат работу и получат доступ к разделенным данным.

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

Переменные блокировки.

Теперь попробуем найтипрограммное решение.

Рассмотрим одну совместную переменную блокировки, изначально равную 0. Если процесс хочет попасть в критическую область, он предварительно считывает значение переменной блокировки. Если переменная равна 0, то процесс заменят ее значение на 1 и входит в критическую область. Если же переменная равна 1, то процесс ждет, пока ее значение сменится на 0. Таким образом, 0 означает, что ни одного процесса в критической области нет, а 1 означает, что какой либо процесс находится в критической области.
У этого метода есть свои проблемы. Представим, что один процесс считывает переменную блокировки, обнаруживает, что она равна 0, но прежде, чем он успевает заменить ее на 1, управление получает другой процесс, успешно заменяющий ее на 1. Когда первый процесс снова получит управление, то он тоже заменит значение переменной блокировки на 1 и два процесса одновременно окажутся в критических областях.

Строгое чередование

На рисунке =

1. целая переменная turn, изначально равная 0, отслеживает, чья очередь входить в критическую область.

2. Вначале процесс 0 проверяет значение turn, считывает 0 и входит в критическую область(*см. примечание ниже)

3. Процесс 1 также считывает значение turn, считывает 0 и после этого входит в цикл, непрерывно проверяя, когда значение turn будет равно 1.

*примечание:
-----------------------------------
на мой взгляд на картинке выше

Опечатка

,чтобы задуманное выполнилось(Вначале процесс 0 проверяет значение turn, считывает 0 и входит в критическую область) необходимо в левом цикле (а) вместо

?

while (turn!=0) ; // неправильно! (по-моему)

написать =

?

while (turn!=1) ; // правильно (по-моему)

так как именно во втором случаепроцесс 0при изначальном turn=0 сможет миновать цикл
-----------------------------------

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

Блокировка, использующая активное ожидание, называетсяспин-блокировкой.

Когда процесс 0 покидает критическую область, он изменяет значение turn на 1, позволяя процессу 1 попасть в критическую область.
Фактически этот метод требует, чтобы два процесса попадали в критическую область строго по очереди. Не один из них не может попасть в критическую секцию (например, послать файл на печать) два раза подряд.

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

Перед тем как обратиться к совместно используемым переменным(то есть перед тем, как войти в критическую область), процесс вызывает процедуру enter_region() со своим номером (0 или 1) в качестве параметра.
Поэтому процессу при необходимости придется подождать, прежде чем входить в критическую область.
После выхода из критической области процесс вызывает процедуру leave_region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область.

Команда TSL

Рассмотрим решение, требующее аппаратного обеспечения.
Многие компьютеры, особенно разработанные с расчетом на несколько процессоров, имеют команду
TSL RX.LOCK
(Test and Set Lock), которая действует следующим образом-
В регистр RX считывается содержимое слова памяти lock, а в ячейке памяти lock хранится некоторое ненулевое значение.
Гарантируется, что операция считывания слова и сохранения неделима - другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий команду TSL, блокирует шину памяти, чтобы остальные процессоры не могли обратиться к памяти.
Рассмотрим пример использования команды TSL для взаимного исключения.

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

15) Планирование процессов. Задачи алгоритмов планирвоания.

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

Планирование- это разделение вычислительных ресурсов системы между процессами и потоками.

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

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

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

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

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

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

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

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

· 1. Системы пакетной обработки данных.

· 2. Интерактивные системы.

· 3. Системы реального времени.

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

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

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

Задачи алгоритмов планирования.

Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать хороший алгоритм. Некоторые задачи зависят от среды (системы пакетной обработки, интерактивные или реального времени), но есть задачи, одинаковые во всех системах.

Список задач

представлен ниже .

# Для всех типов систем=

1. Справедливость - предоставление каждому процессу справедливой доли процессорного времени.

2. Принудительное применение политики - контроль за выполнением принятой политики.

3. Баланс - поддержка занятости всех частей системы.

# Для систем пакетной обработки данных=

1. Пропускная способность- максимальное количество задач в час

2. Оборотное время - минимизация времени, затрачиваемого на ожидание, обслуживание и обработку задачи.

3. Использование процессора - поддержка постоянной занятости процессора

# Для интерактивных систем=

1. Время отклика- быстрая реакция на запросы

2. Соразмерность - выполнение пожеланий пользователя

# Для систем реального времени=

1. Окончание работы к сроку - предотвращение потери данных

2. Предсказуемость - предотвращение деградации качества в мультимедийных системах

16) Активация планировщика (когда выполняется планирование).

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

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

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

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

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

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

17) Алгоритм пларирования FCFS

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия — First Come, First Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, организованы в очередь. Когда процесс переходит в состояние готовность, он, а точнее ссылка на его PCB, помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование FIFO — сокращение от First In, First Out (первым вошел, первым вышел).

18) Алгоритм пларирования SJF

ри рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название “кратчайшая работа первой” или Shortest Job First (SJF).

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

19) Алгоритм пларирования RoundRobin

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически — процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 - 100 миллисекунд (см. рисунок 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

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

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

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

20) Алгоритм пларирования "Multilevel Queue"

Для систем, в которых процессы могут быть легко рассортированы на разные группы, был разработан другой класс алгоритмов планирования. Для каждой группы процессов создается своя очередь процессов, находящихся в состоянии готовность (см. рисунок 3.5). Этим очередям приписываются фиксированные приоритеты. Например, приоритет очереди системных процессов устанавливается больше, чем приоритет очередей пользовательских процессов. А приоритет очереди процессов, запущенных студентами, — ниже, чем для очереди процессов, запущенных преподавателями. Это значит, что ни один пользовательский процесс не будет выбран для исполнения, пока есть хоть один готовый системный процесс, и ни один студенческий процесс не получит в свое распоряжение процессор, если есть процессы преподавателей, готовые к исполнению. Внутри этих очередей для планирования могут применяться самые разные алгоритмы. Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR. Подобный подход, получивший название многоуровневых очередей, повышает гибкость планирования: для процессов с различными характеристиками применяется наиболее подходящий им алгоритм.

21) Алгоритм пларирования "Multilevel Feedback Queue"

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

Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке 3.6. Планирование процессов между очередями осуществляется на основе вытесняющего приоритетного механизма. Чем выше на рисунке располагается очередь, тем выше ее приоритет. Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс. Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1. И, наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты. Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется появившимся. Планирование процессов внутри очередей 0—2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае, он переходит в очередь 1. Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается — остается в очереди 1. В очереди 2 величина кванта времени составляет 32 единицы. Если и этого мало для непрерывной работы процесса, процесс поступает в очередь 3, для которой квантование времени не применяется, и, при отсутствии готовых процессов в других очередях, он может исполняться до окончания своего CPU burst. Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать для своего выполнения. Таким образом, через некоторое время все процессы, требующие малого времени работы процессора окажутся размещенными в высокоприоритетных очередях, а все процессы, требующие большого счета и с низкими запросами к времени отклика, — в низкоприоритетных.

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

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

§ Количество очередей для процессов, находящихся в состоянии готовность.

§ Алгоритм планирования, действующий между очередями.

§ Алгоритмы планирования, действующие внутри очередей.

§ Правила помещения родившегося процесса в одну из очередей.

§ Правила перевода процессов из одной очереди в другую.

22) Взаимоблокировки. Условия взаимоблокировки.

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

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

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

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

Ресурсы бывают двух типов:

1. выгружаемые

2. и невыгружаемые.

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

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

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

· 1. Запрос ресурса.

· 2. Использование ресурса.

· 3. Возврат ресурса

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

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

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

· 1.Условие взаимного исключения.Каждый ресурс в данный момент или от­дан ровно одному процессу, или доступен.

· 2. Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы.

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

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

23) Управление памятью. Виртуальная память.