2011. Машбук (1114722), страница 36

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 36)

Опускается семафор mutex, которыйиспользуется для синхронизации входа в критическую секцию. Внутри критическойсекции меняем состояние философа (помечаем его состоянием HUNGRY). Затемпредпринимается попытка начать есть (вызывается функция Test). Функция Test127проверяет, что если i-ый философ голоден, а его соседи в данный момент не едят (т.е.правая и левая вилки свободны), то этот философ начинает прием пищи (состояниеEATING), а его семафор поднимается (заметим, что изначально этот семафоринициализирован нулем). После этого мы возвращаемся обратно в функцию TakeForks, вкоторой далее происходит выход из критической секции (поднимаем семафор mutex), азатем опускаем семафор этого философа.

Если внутри функции Test философу удалосьначать прием пищи, то семафор поднят, и операция down обнулит его, не блокируясь.Если же функция Test не изменит состояние философа, а также не поднимет его семафор,то операция down (в функции TakeForks) в этой точке заблокируется до тех пор, пока обасоседа не освободят вилки.Внутри функции освобождения вилок PutForks сначала происходит опусканиесемафора mutex, происходит вход в критическую секцию. Затем меняется статусфилософа (на статус THINKING), после чего проверяем его соседей: если любой из нихбыл заблокирован лишь из-за того, что наш i-ый философ забрал его вилку, то мы егоразблокируем, и он начинает прием пищи. После этого происходит выход из критическойсекции путем подъема семафора mutex.Заметим, что использование механизма взаимоисключающего нахождения внутрикритической секции (за счет семафора mutex) гарантирует, что не возникнет ситуация,когда два процесса, соответствующие соседним философам, будут так спланированы наобработку на процессоре, что функция Test в каждом из них проработает и разрешиткаждому из них начать прием пищи (что, конечно же, является ошибкой).

Если же этогомеханизма не будет, то возможно, что один из процессов-соседей входит в Test, делаетпроверку на возможность начала приема пищи. Проверка дает истинное значение,управление переходит к первой команде внутри if-блока. После этого происходит сменапроцесса на процессоре, управление получает сосед этого философа. Тот тоже делаетпроверку внутри функции Test и также получает положительный ответ, и управлениепереходит к первой инструкции if-блока. Дальнейшая работа будет некорректной.Задача «читателей и писателей». Представим произвольную системурезервирования ресурса.

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

Тоесть процесс-писатель будет ожидать момента, когда все желающие процессы-читателиокончат свои действия в системе и покинут ее./* переопределение типа семафор */typedef int semaphore;/* семафор для доступа в критическую секцию - контроль задоступом к «rc» (разделямый ресурс) */semaphore mutex = 1;/* семафор для доступа к базе данных */semaphore db = 1;/* количество читателей внутри хранилища */int rc = 0;/* процесс-читатель */128void Reader(void){while(true){down(&mutex); /* получить эксклюзивный доступ к «rc»*/rc = rc + 1; /* еще одним читателем больше *//* если это первый читатель, нужно заблокироватьэксклюзивный доступ к базе */if(rc == 1)down(&db);up(&mutex); /*освободить ресурс rc */ReadDataBase(); /* доступ к данным */down(&mutex); /*получить эксклюзивный доступ к «rc»*/rc = rc – 1; /* теперь одним читателем меньше *//*если это был последний читатель, разблокироватьэксклюзивный доступ к базе данных */if(rc == 0)up(&db);up(&mutex); /*освободить разделяемый ресурс rc*/UseDataRead(); /* некритическая секция */}}/* процесс-писатель */void Writer(void){while(TRUE){ThinkUpData(); /* некритическая секция */down(&db); /* получить эксклюзивный доступ к данным*/WriteDataBase(); /* записать данные */up(&db); /* отдать эксклюзивный доступ */}}В приведенном решении процесс-читатель в каждом цикле своей работы входит вкритическую секцию (опускает семафор mutex), увеличивает счетчик читателей,находящихся в хранилище, на 1.

Затем проверяет, что является ли он первым читателем(т.е. в данный момент он единственный клиент в хранилище). Если да, то он опускаетсемафор db, тем самым, препятствуя писателям войти в систему, если они того пожелают.Если же семафор db уже был опущен, то это означает, что в данный момент в хранилищеприсутствует писатель, и этот первый читатель заблокируется на этой операции, ожидаявыхода писателя из системы. (Заметим, что эта блокировка происходит внутрикритической секции, поэтому остальные читатели будут блокироваться на опусканиисемафора mutex.) После этого происходит выход из критической секции (подымаемсемафор mutex), чтение информации из хранилища.

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

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

Однако, обратная сторона данногорешения в том, что оно несколько снижает производительность процессов-читателей, т.к.вынуждает их ждать в тот момент, когда ресурс не занят в эксклюзивном режиме.Данная задача иллюстрирует модель доступа к разделяемому ресурсу процессов,имеющих разные приоритеты.Задача о «спящем парикмахере». Рассмотрим парикмахерскую, в которойработает один парикмахер, имеется одно кресло для стрижки и несколько кресел вприемной для посетителей, ожидающих своей очереди. Если в парикмахерской нетпосетителей, парикмахер засыпает прямо на своем рабочем месте. Появившийсяпосетитель должен его разбудить, в результате чего парикмахер приступает к работе.

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

Понадобится 3 семафора: customers —подсчитывает количество посетителей, ожидающих в очереди, barbers — статуспарикмахера (0 - занят, 1 - свободен)1 и mutex — используется для синхронизации доступак разделяемой переменной waiting. Переменная waiting, как и семафор customers,содержит количество посетителей, ожидающих в очереди. Эта переменная используется впрограмме для того, чтобы иметь возможность проверить, имеется ли свободное креслодля ожидания, и при этом не заблокировать процесс, если кресла не окажется. Заметим,что как и в предыдущем примере, эта переменная является разделяемым ресурсом, идоступ к ней охраняется семафором mutex./* количество стульев в комнате ожидания */#define CHAIRS 5/* переопределение типа СЕМАФОР */typedef int semaphore;/* наличие посетителей, ожидающих парикмахера */semaphore customers = 0;/* количество парикмахеров, ожидающих посетителей (0 или 1)*/semaphore barbers = 0;/* семафор для доступа в критическую секцию - контроль задоступом к переменной waiting */semaphore mutex = 1;/* количество ожидающих посетителей */int waiting = 0;1В принципе возможно расширение задачи для случая N парикмахеров, в этом случае, снезначительными коррекциями программ, barbers – количество свободных парикмахеров.130/* Брадобрей */void Barber(void){while(TRUE){/* если customers == 0, т.е.

Характеристики

Список файлов лекций