Задача о читателях и писателях.

Важной и часто встречающейся задачей, решение которой требует синхронизации, является задача «Читатели — писатели». Эта задача имеет много вариантов. Определить ее можно следующим образом. Имеются данные, совместно используемые рядом процессов. Данные могут находиться в файле в блоке основной памяти или даже в регистрах процессора. Имеются несколько процессов, которые только читают эти данные (Читатели), и несколько других, которые только записывают данные (Писатели). При этом должны удовлетворяться следующие условия.- Любое число читателей могут одновременно читать файл.- Записывать информацию в файл в определенный момент времени может только один Писатель.- Когда Писатель записывает информацию в файл, ни один Читатель не может его читать. Пример использования — работа с библиотечным каталогом. Другим типичным примером служит система автоматизированной продажи билетов. Процессы «Читатели» обеспечивают нас справочной информацией о наличии свободных билетов на тот или иной рейс. Процессы «Писатели» запускают с пульта кассира, когда он оформляет для нас тот или иной билет. Имеется большое количество как «Читателей», так и «Писателей». Наиболее характерная область использования этой задачи в вычислительной системе — при построении систем управления файлами. Два класса процессов имеют доступ к некоторому ресурсу (области памяти, файлам). «Читатели» — это процессы, которые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом. «Писатели» — это процессы, записывающие информацию в эту область памяти, исключая при этом и друг друга и процессы «Читатели». Широко распространены следующие условия: 1.Приоритетное чтение: Устанавливается приоритет в использование критического ресурса процесса Читатели. Это означает, что если хотя бы один Читатель пользуется ресурсом, то он закрыт для использования всем Писателям и доступен для использования всем Читателям. При появлении запроса от Писателя необходимо закрыть дальнейший доступ всем тем процессам Читателям, которые выдадут запрос на критический ресурс после него.

15 Задача о спящем брадобрее. Задача о спящем брадобрее. Действие еще одной классической проблемной ситуации межпроцесс-ного взаимодействия разворачивается в парикмахерской. В парикмахерской есть один брадобрей, его кресло и n стульев для посетителей. Если желаю-щих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, он должен разбудить брадо-брея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запро-граммировать брадобрея и посетителей так, чтобы избежать состояния состя-зания. В решении можно использовать три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитыва-ется — он уже не ждет); barbers, количество брадобреев 0 или 1), простаи-вающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожи-дающих посетителей. Она является копией переменной customers. Присутст-вие в программе этой переменной связано с тем фактом, что прочитать теку-щее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, дол-жен сосчитать количество ожидающих посетителей. Если посетителей мень-ше, чем стульев, новый посетитель остается, в противном случае он уходит. Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает, как показано на рис., и спит, пока не при-дет первый клиент. Приходя в парикмахерскую, посетитель выполняет про-цедуру customer, запрашивая доступ к mutex для входа в критическую об-ласть. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобо-ждает доступ к mutex и уходит. Если свободный стул есть, посетитель увели-чивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем самым активизируя поток брадо-брея. В этот момент оба — посетитель и брадобрей — активны. Когда посе-титель освобождает доступ к mutex, брадобрей захватывает его, проделывает некоторые служебные операции и начинает стричь клиента. По окончании 7 стрижки посетитель выходит из процедуры и покидает парикмахерскую. В отличие от предыдущих программ, цикла посетителя нет, поскольку каждого посетителя стригут только один раз. Цикл брадобрея существует, и брадо-брей пытается найти следующего посетителя. Если ему это удается, он стри-жет следующего посетителя, в противном случае брадобрей засыпает. Стоит отметить, что, несмотря на отсутствие передачи данных в проблеме читате-лей и писателей и в проблеме спящего брадобрея, обе эти проблемы относят-ся к проблемам межпроцессного взаимодействия, поскольку требуют син-хронизации нескольких процессов.

16 Алгоритмы планирования процессов.

Алгоритмы планирования процессов

Планирование процессов включает в себя решение следующих задач:

1. определение момента времени для смены выполняемого процесса;

2. выбор процесса на выполнение из очереди готовых процессов;

3. переключение контекстов "старого" и "нового" процессов.

FCFS - Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO (первым вошел, первым вышел). Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Round Robin (RR) Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться. Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта. 1.Время непрерывного использования процессора, необходимое процессу (остаток текущего CPU burst), меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново. 2.Продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале. На производительность алгоритма RR сильно влияет величина кванта времени. При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из n процессов работает на собственном виртуальном процессоре с производительностью ~ 1/n от производительности реального процессора.Shortest-Job-First (SJF). Гарантированное планирование. При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название "кратчайшая работа первой" или Shortest Job First (SJF). SJF-алгоритм краткосрочного планирования может быть как вытесняющим, так и невытесняющим. При невытесняющем SJF - планировании процессор предоставляется избранному процессу на все необходимое ему время, независимо от событий, происходящих в вычислительной системе. При вытесняющем SJF - планировании учитывается появление новых процессов в очереди готовых к исполнению (из числа вновь родившихся или разблокированных) во время работы выбранного процесса. Гарантированное планирование -При интерактивной работе N пользователей в вычислительной системе можно применить алгоритм планирования, который гарантирует, что каждый из пользователей будет иметь в своем распоряжении ~1/N часть процессорного времени. Пронумеруем всех пользователей от 1 до N. Для каждого пользователя с номером i введем две величины: T_i – время нахождения пользователя в системе или, другими словами, длительность сеанса его общения с машиной и τ_i – суммарное процессорное время уже выделенное всем его процессам в течение сеанса. Справедливым для пользователя было бы получение T_i/N процессорного времени. Если τ_i<<T_i/N то i-й пользователь несправедливо обделен процессорным временем. Если же τ_i>>T_i/N то система явно благоволит к пользователю с номером i. Вычислим для процессов каждого пользователя значение коэффициента справедливости τ_iN/T_i и будем предоставлять очередной квант времени готовому процессу с наименьшей величиной этого отношения. Предложенный алгоритм называют алгоритмом гарантированного планирования. К недостаткам этого алгоритма можно отнести невозможность предугадать поведение пользователей. Если некоторый пользователь отправится на пару часов пообедать и поспать, не прерывая сеанса работы, то по возвращении его процессы будут получать неоправданно много процессорного времени.

Приоритетное планирование. Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования. При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет, в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS. Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst. Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет. Алгоритмы назначения приоритетов процессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Алгоритмы SJF и гарантированного планирования используют внутренние параметры. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа. Планирование с использованием приоритетов может быть как вытесняющим, так и невытесняющим. При вытесняющем планировании процесс с более высоким приоритетом, появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом. В случае невытесняющего планирования он просто становится в начало очереди готовых процессов. Давайте рассмотрим примеры использования различных режимов приоритетного планирования. Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение. Или вычислительную систему приходится выключать, и они теряются. Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса, находящегося в состоянии готовность.