Курынин Р.В., Машечкин И.В., Терехин А.Н. - Конспект лекций по ОС (1114685), страница 31

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

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

Рассмотрим иное решение./* количество философов */#define N 5110/* Номера левого и правого */#define LEFT (i-1)%N#define RIGHT (i+1)%N/* состояния философов:«думает»,«желает поесть»,«кушает»*/#define THINKING 0#define HUNGRY 1#define EATING 2/* переопределяем тип СЕМАФОР */typedef int semaphore;/*массив состояний каждого из философов, инициализированный нулями*/int state[N];/* семафор для доступа в критическую секцию */semaphore mutex = 1;/*массив семафоров по одному на каждого из философов,инициализированный нулями*/semaphore s[N];/* Процесс-философ (i = 0..N) */void Philosopher(int i)111{while(TRUE){Think();TakeForks(i);Eat();PutForks(i);}}/* получение вилок */void TakeForks(int i){/* вход в критическую секцию */down(&mutex);state[i] = HUNGRY;Test(i);/* выход из критической секции */up(&mutex);down(&s[i]);}/* освобождение вилок */void PutForks(int i){/* вход в критическую секцию */down(&mutex);state[i] = THINKING;112Test(LEFT);Test(RIGHT);/* выход из критической секции */up(&mutex);}void Test(int i){if(state[i] == HUNGRY &&state[LEFT] != EATING &&state[RIGHT] != EATING){state[i] = EATING;up(&s[i]);}}В этом решении каждый философ живет по аналогичному циклическому распорядку:размышляет некоторое время, затем берет вилки, кушает, кладет вилки.

Рассмотрим процедуруполучения вилок (TakeForks). Опускается семафор mutex, который используется длясинхронизации входа в критическую секцию. Внутри критической секции меняем состояниефилософа (помечаем его состоянием «голоден»). Затем предпринимается попытка начать есть(вызывается функция Test).

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

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

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

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

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

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

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

Если свободных кресел нет, то вновь приходящие клиенты сразу же покидают заведение.Когда посетителей нет, парикмахер может сидеть в своем кресле и дремать.Данная задача является иллюстрацией модели клиент-сервер с ограничением на длинуочереди клиентов.Рассмотрим реализацию данной модели./* количество стульев в комнате ожидания */#define CHAIRS 5/* переопределение типа СЕМАФОР */typedef int semaphore;/* наличие посетителей, ожидающих парикмахера */semaphore customers = 0;/*количество парикмахеров, ожидающих посетителей (0 или 1)*/semaphore barbers = 0;/* семафор для доступа в критическую секцию */semaphore mutex = 1;/* количество ожидающих посетителей */int waiting = 0;/* Брадобрей */116void Barber(void){while(TRUE){down(&customers);down(&mutex);waiting = waiting – 1;up(&barbers);up(&mutex);CutHair();}}/* Посетитель */void Customer(void){down(&mutex);if(waiting < CHAIRS){waiting = waiting + 1;up(&customers);up(&mutex);down(&barbers);GetHaircut();}else{up(&mutex);117}}Процесс-парикмахер первым делом опускает семафор customers, уменьшив тем самымколичество ожидающих посетителей на 1.

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

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

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