Лекция 18 (21/05/04)





ЛЕКЦИЯ 18 (21/05/04)

Приложение

Традиционные задачки теории операционных систем

При решении разных задач, при разработке и синхронизации параллельных вычислений бывает полезно сравнить решаемую задачку с известными схемами и проверить применимость приобретенного решения к известной задачке Лекция 18 (21/05/04). Существует ряд таких "эталонных" задач, которые отражают более нередко возникающие перед разработчиками трудности.

§1 Схема "производитель-потребитель"

Эта схема тщательно рассматривалась ранее, потому тут только вспомним о ее существовании в ряду традиционных задач теории Лекция 18 (21/05/04) ОС.

§2 Схема "читатели-писатели"

^ Постановка задачки:

Пусть имеются некие данные, вместе применяемые рядом процессов. Эти данные могут находиться в файле на диске, в блоке основной памяти либо в регистрах микропроцессора. Есть Лекция 18 (21/05/04) некоторое количество процессов, которые только читают эти данные ("читатели") и несколько других, которые только записывают данные ("писатели"). При всем этом должны удовлетворяться последующие условия:

  1. хоть какое число "читателей" может сразу читать данные Лекция 18 (21/05/04) (пусть это будет для определенности, к примеру, файл);

  2. записывать информацию в файл в определенный момент времени может только один "писатель";

  3. когда "писатель" записывает данные в файл, ни один "читатель" не может его читать.

В описанной Лекция 18 (21/05/04) схеме "читатели" не изменяют данные, а "писатели" не считывают информацию. Задачка в таковой постановке является сужением более общей задачки, в какой каждый процесс может являться как читателем, так и писателем. В Лекция 18 (21/05/04) таком случае можно всякую часть процесса, которая обращается к данным, объявить критичным разделом, и использовать простейшее решение на базе взаимоисключений. Схема "читатели-писатели" является довольно всераспространенным личным случаем этой общей задачки Лекция 18 (21/05/04), для которого имеется еще более действенное решение. Вот поэтому ее принято выделять в отдельную задачку.

Примеры

  1. Представим для себя библиотечный каталог, в каком читатели могут находить подходящую им литературу, а работники библиотеки Лекция 18 (21/05/04) могут этот каталог обновлять. Работники при внесении конфигураций не должны мешать друг дружке, также не должны допускать читателей к данным в момент их конфигурации, чтоб предупредить получение читателями недостоверной инфы. Читатели могут Лекция 18 (21/05/04) воспользоваться каталогами по несколько человек сразу. Если рассматривать общее решение, то читатели могли быть обязаны заходить в каталог по одному, что вызвало бы неоправданные задержки и очереди.

  2. Традиционным примером рассматриваемой схемы является система подготовительной реализации Лекция 18 (21/05/04) билетов (авиа либо жд). Запросы кассира-оператора играют роль "читателя", и таких запросов к БД (базе данных) может поступить еще больше, чем реальных конфигураций БД. Когда клиент (может быть, после нескольких запросов Лекция 18 (21/05/04)) изберет для себя рейс и купит билет, тогда вступит в действие процесс-писатель – кассир занесет в базу конфигурации о наличии свободных мест на соответственный рейс. При всем этом кассир выступает поначалу Лекция 18 (21/05/04) в роли "читателя", а потом в роли "писателя", поточнее, запускает то один, то другой процесс.

Можно ли рассматривать схему "производитель-потребитель" в качестве личного варианта задачки "читатели-писатели" с одним "читателем" (потребитель) и Лекция 18 (21/05/04) одним "писателем" (производитель)? Оказывается, нет. Производитель – не просто писатель. Он должен смотреть за указателем очереди, чтоб найти, куда нужно заносить еще одну порцию инфы, и держать под контролем состояние буфера Лекция 18 (21/05/04), чтоб исключить возможность его переполнения. Аналогично, потребитель – не просто читатель; он изменяет значение указателя очереди, демонстрируя тем, что информация считана, и удаляет ее из буфера. Не считая того, он должен держать под Лекция 18 (21/05/04) контролем наличие инфы в буфере.

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

    1. ^ Приоритетное чтение

Приоритетное чтение значит Лекция 18 (21/05/04), что процесс-писатель будет допущен к разделяемым данным только тогда, когда все процессы-читатели окончат свою работу.

Нам будет нужно семафор для запрета доступа писателям в критичную секцию. Пусть это будет семафор Лекция 18 (21/05/04) W. Так как нужно организовать одновременную работу нескольких читателей, то состояние этого семафора должен инспектировать (и изменять) только 1-ый читатель, получивший доступ к разделяемым данным. Аналогично, если последний находившийся Лекция 18 (21/05/04) в КС читатель кончает чтение, только он должен открывать семафор W. Как следует, нужно иметь счетчик количества читателей, находящихся сразу в КС – пусть это будет R_Count. Для корректного конфигурации значения этого счетчика читателей Лекция 18 (21/05/04) необходимо ввести очередной дополнительный семафор S_R, который будет запираться лишь на время конфигурации счетчика R_Count.

Итак, разглядим программное решение:

Program R&W_prior_Reader;

Var R_Count: Integer Лекция 18 (21/05/04);

W, S_R : Semaphore;

Procedure Writer;

Begin

While true Do

Begin

P(W); {проверка (закрытие) собственного семафора}

ЗАПИСЬ;

V(W); {освобождение собственного семафора}

End;

End;

Procedure Reader;

Begin

While true Do

Begin

P(S_R); {если закрыт W Лекция 18 (21/05/04), тут читатели будут ждать}

Inc(R_Count); {читателей стало больше}

If R_Count=1 Then P(W);

V(S_R);

ЧТЕНИЕ;

P(S_R);

Dec(R_Count);

If R_Count=0 Then V(W);

V(S_R Лекция 18 (21/05/04));

End;

End;

Begin

InitSem(W,1); InitSem(S_R,1);

R_Count:=0;

Parbegin

Reader; Writer;

Parend;

End.

Недочетом рассмотренного варианта является тот, что при большенном наплыве читателей писатель возможно окажется в состоянии нескончаемого ожидания Лекция 18 (21/05/04). Схема с ценностью писателей дает возможность избежать этого явления.

    1. ^ Приоритетная запись

Приоритетная запись значит, что при возникновении первого же писателя прекращается доступ новых читателей к разделяемым данным (как следует, необходимо подсчитывать количество писателей аналогично тому Лекция 18 (21/05/04), как это было изготовлено с читателями.). Вновь пришедшие читатели выстраиваются в очередь на собственном семафоре – означает, для их будет нужно очередной семафор, R. Читатели, находившиеся в КС, равномерно завершают работу, а доступ Лекция 18 (21/05/04) новых закрыт. Как следует, в некий момент последний выходящий из КС читатель откроет семафор W и даст возможность писателю войти в КС. Если за этот период времени появились еще писатели, они Лекция 18 (21/05/04) ждут на семафоре W, который будет открыт до этого, чем семафор R, как следует, писатели получат преимущественное право работы с разделяемыми данными.

Program R&W_prior_Writer;

Var R_Count, W_Count: Integer Лекция 18 (21/05/04);

W, S_R, R, S_W : Semaphore;

Procedure Writer;

Begin

While true Do

Begin

P(S_W); Inc(W_Count);

If W_Count=1 Then P(R);

V(S_W);

P(W); {проверка (закрытие Лекция 18 (21/05/04)) собственного семафора}

ЗАПИСЬ;

V(W); {освобождение собственного семафора}

P(S_W); Dec(W_Count);

If W_Count=0 Then V(R);

V(S_W);

End;

End;

Procedure Reader;

Begin

While true Do

Begin

P(R); {если Лекция 18 (21/05/04) закрыт R, тут читатели будут ждать}

P(S_R);

Inc(R_Count); {читателей стало больше}

If R_Count=1 Then P(W);

V(S_R);

V(R); {нужно впустить других читателей}

ЧТЕНИЕ;

P(S_R Лекция 18 (21/05/04)); Dec(R_Count);

If R_Count=0 Then V(W);

V(S_R);

End;

End;

Begin

InitSem(W,1); InitSem(S_R,1);

InitSem(R,1); InitSem(S_W,1);

R_Count:=0; W_Count:=0;

Parbegin

Reader; Writer Лекция 18 (21/05/04);

Parend;

End.

В данном варианте трудности могут появиться при большенном количестве писателей – читатели будут ждать нескончаемо. Чтоб этого не случилось, можно использовать разные методы улучшения метода – к примеру, инспектировать время ожидания читателя Лекция 18 (21/05/04) в очереди либо длину этой очереди (в случае, если накопится очередь определенной длины, пропустить читателей и опять вернуть прежний режим.)

    1. ^ Реализация схемы с помощью мониторов

При реализации при помощи монитора будет нужно два Лекция 18 (21/05/04) условия – назовем их Reading_allow, Writing_allow, также общие переменные R_Count (счетчик числа читателей) и Writing (логическая переменная, настоящее значение которой значит, что идет запись). Для начала либо окончания чтения Лекция 18 (21/05/04) либо записи процесс должен обратиться с вызовом соответственной процедуры монитора. Команды WAIT и SIGNAL рассматривались при исследовании мониторов.

monitor Readers_Writers;

Var R_Count : Integer;

Writing : Boolean;

Reading_allow, Writing_allow : condition;

Procedure Start_Reading Лекция 18 (21/05/04);

Begin

If Writing or очередь (Writing_allow) Then

WAIT(Reading_allow);

inc(R_Count);

SIGNAL(Reading_allow);

End;

Procedure Finish_Reading;

Begin

dec(R_Count);

If R_Count=0 Then

SIGNAL(Writing_allow);

End;

Procedure Start Лекция 18 (21/05/04)_Writing;

Begin

If Writing or (R_Count>0) Then

WAIT(Writing_allow);

Writing:=true;

End;

Procedure Finish_Writing;

Begin

Writing:=false;

If очередь (Reading_allow) Then

SIGNAL(Reading_allow)

Else SIGNAL(Writing_allow)

End;

Begin Лекция 18 (21/05/04) {main}

R_Count:=0;

Writing:=false;

End.

§3 задачка "об обедающих философах"

Дейкстра определил эту любопытную задачку, которая иллюстрирует многие ситуации, соответствующие для параллельного программирования, а именно, трудности взаимоблокировки и голодания. Она может рассматриваться как обычная Лекция 18 (21/05/04) задачка, возникающая в многопоточных приложениях при работе с вместе применяемыми ресурсами, и, как следует, может выступать в роли испытательной при разработке новых подходов к синхронизации.

^ Постановка задачки:

П
ятеро философов посиживают Лекция 18 (21/05/04) за круглым столом. Жизнь каждого из их максимально ординарна: некое время он предается размышлениям, а некое время ест спагетти. Перед каждым философом находится блюдо спагетти, которое повсевременно пополняет особый слуга. На столе лежит ровно Лекция 18 (21/05/04) 5 вилок, по одной меж хоть какими 2-мя философами-соседями. Чтоб есть спагетти, философ в согласовании с правилами неплохого тона должен воспользоваться 2-мя вилками – правой и левой. (На рисунке вилки обозначены Лекция 18 (21/05/04) стрелочками)

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

Пусть вилки и философы Лекция 18 (21/05/04) пронумерованы от 1 до 5, для определенности по часовой стрелке. Тогда можно всякую вилку идентифицировать по ее номеру либо по месту относительно определенного философа (левая либо правая вилка). Для формального описания метода лучше 1-ый Лекция 18 (21/05/04) вариант, для словесного – 2-ой.

Тогда процедура Philosopher(i) будет обрисовывать поведение i-го философа и в общем случае смотреться последующим образом:

Procedure Philosopher(i);

Begin

While true Do

Begin

Thinking; {мыслит некое время Лекция 18 (21/05/04)}

Take(i); {берет i-ю вилку – пусть это будет его правая вилка}

Take(i mod 5 + 1); {это левая вилка}

Eating; {ест некое время}

Put(i); {кладет i-ю вилку}

Put(i+1); {кладет вторую вилку Лекция 18 (21/05/04)}

End;

End;

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

  1. Каждый философ берет – конкретно так, как описано в процедуре – поначалу правую, потом левую Лекция 18 (21/05/04) вилку. ^ Вероятная ситуация: все философы сразу возьмут свои правые вилки – возникнет полная блокировка всей системы (требуемый для окончания работы ресурс занят, а поток, который его держит, ожидает освобождения ресурса другим Лекция 18 (21/05/04) потоком, а тот, в свою очередь, также ожидает…).

  2. Каждый философ берет обе вилки сразу (если они свободны). ^ Вероятная ситуация: у некого определенного философа будут попеременно есть то его левый, то правый сосед, вследствие чего Лекция 18 (21/05/04) он может умереть с голоду – возникнет голодание (процесс долгое время не может получить требуемого ему ресурса, хотя вся система в целом работает).

  3. Каждый философ берет поначалу правую, потом левую вилку. Если левой Лекция 18 (21/05/04) вилки нет, то он кладет назад уже взятую им правую вилку (временный отказ от запроса для снятия вероятной блокировки, сброс флага), а потом возобновляет пробы по той же схеме. Вероятная ситуация Лекция 18 (21/05/04): при определенном стечении событий получаем 1-ый вариант, если философы начнут действовать "синхронно".

  4. Введем в компанию философов некое обилие. Пусть они имеют некие различия, а конкретно, есть "правые" философы и "левые" – заглавие философа соответствует Лекция 18 (21/05/04) тому, какую вилку он берет сначала. В таком случае, если во всей компании будет находиться хотя бы один философ другого типа, чем все другие (хотя бы один "левый" и хотя бы один "правый Лекция 18 (21/05/04)", другие – все равно какие), система будет работать без блокировок и голодания. Покажите, что это вправду так.


lekciya-15-filosofskoe-uchenie-o-bitii-ontologiya.html
lekciya-15-leksicheskie-omonimi-tipi-sinonimov-antonimi-v-russkoj-leksike.html
lekciya-15-po-uchebnoj-discipline-fizika.html