Проблема
Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная со многими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли ждущие клиенты. Если есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.
Каждый приходящий клиент смотрит на то, что делает парикмахер. Если парикмахер спит, то клиент будит его и садится в кресло. Если парикмахер работает, то клиент идет в приёмную. Если есть свободный стул в приёмной, клиент садится и ждёт своей очереди. Если свободного стула нет, то клиент уходит. Основываясь на наивном анализе, вышеупомянутое описание должно гарантировать, что парикмахерская функционирует правильно с парикмахером, стригущим любого пришедшего, пока есть клиенты, и затем спящим до появления следующего клиента. На практике есть много проблем, которые могут произойти, которые иллюстрируют общие проблемы планирования.
Все проблемы связаны с фактом, что все действия и парикмахера, и клиента (проверка приёмной, вход в парикмахерскую, занятие места в приёмной, и т. д.) занимают неизвестное количество времени. Например, клиент может войти и заметить, что парикмахер работает, тогда он идет в приёмную. Пока он идет, парикмахер заканчивает стрижку, которую он делает и идет, чтобы проверить приемную. Так как там никого нет (клиент еще не дошел) он возвращается к своему месту и спит. Парикмахер теперь ждет клиента, и клиент ждет парикмахера. В другом примере два клиента могут прибыть в то же самое время, когда в приемной есть единственное свободное место. Они замечают, что парикмахер работает, идут в приёмную, и оба пытаются занять единственный стул.
Проблема спящего парикмахера часто приписывается Эдсгеру Дейкстра (1965), одному из пионеров информатики.
Решение
Доступно множество возможных решений. Основной элемент каждого - mutex , который гарантирует, что изменить состояние (state ) может только один из участников. Парикмахер должен захватить это mutex исключение, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить mutex, прежде чем войти в магазин, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Семафоры также обязаны указывать на состояние системы. Например, можно было бы сохранить число людей в приемной.
У варианта с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.
См. также
- Проблема курильщиков
Ссылки
- Modern Operating Systems (2nd Edition) by Andrew S. Tanenbaum (ISBN 0-13-031358-0)
- The Little Book of Semaphores by Allen B. Downey, http://greenteapress.com/semaphores
- Cooperating sequential processes by E.W. Dijkstra. Technical Report EWD-123, 1965, Technological University, Eindhoven, The Netherlands.
Wikimedia Foundation . 2010 .
Проблема
Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная со многими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли ждущие клиенты. Если есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.
Каждый приходящий клиент смотрит на то, что делает парикмахер. Если парикмахер спит, то клиент будит его и садится в кресло. Если парикмахер работает, то клиент идет в приёмную. Если есть свободный стул в приёмной, клиент садится и ждёт своей очереди. Если свободного стула нет, то клиент уходит. Основываясь на наивном анализе, вышеупомянутое описание должно гарантировать, что парикмахерская функционирует правильно с парикмахером, стригущим любого пришедшего, пока есть клиенты, и затем спящим до появления следующего клиента. На практике есть много проблем, которые могут произойти, которые иллюстрируют общие проблемы планирования.
Все проблемы связаны с фактом, что все действия и парикмахера, и клиента (проверка приёмной, вход в парикмахерскую, занятие места в приёмной, и т. д.) занимают неизвестное количество времени. Например, клиент может войти и заметить, что парикмахер работает, тогда он идет в приёмную. Пока он идет, парикмахер заканчивает стрижку, которую он делает и идет, чтобы проверить приемную. Так как там никого нет (клиент еще не дошел) он возвращается к своему месту и спит. Парикмахер теперь ждет клиента, и клиент ждет парикмахера. В другом примере два клиента могут прибыть в то же самое время, когда в приемной есть единственное свободное место. Они замечают, что парикмахер работает, идут в приёмную, и оба пытаются занять единственный стул.
Доступно множество возможных решений. Основной элемент каждого - mutex , который гарантирует, что изменить состояние (state ) может только один из участников. Парикмахер должен захватить это mutex исключение, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить mutex , прежде чем войти в магазин, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Семафоры также обязаны указывать на состояние системы. Например, можно было бы сохранить число людей в приемной.
У варианта с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.
Классическая задача. Читатели и писатели
Дана некоторая разделяемая область память, к этой структуре данных может обращаться произвольное количество «читателей» и произвольное количество «писателей».
Несколько читателей могут получить доступ одновременно, писатели в этот момент не допускаются. Только один писатель может получить доступ, другие писатели и читатели должны ждать.
Первое решение
Читатель может войти в критическую секцию, если нет писателей.
Это решение несправедливо, так как отдает предпочтение читателям
Плотный поток запросов от читателей может привести к тому, что писатель никогда не получит доступа к критической секции – ситуация «голодания» (starvation).
Второе решение
Отдадим предпочтение писателям, то есть читатель не входит в критическую секцию, если есть хотя бы один ожидающий писатель.
Данное решение отдает приоритет писателям, и тоже несправедливо, так как возможно «голодание»
(starvation) читателей.
Третье решение
Не отдавать никому приоритета, просто использовать мьютекс .
Билеты для подготовки к экзамену по Информатике. Трофимов Владислав, Махонин Кирилл
Файловые системы
FAT - File Allocation Table
FAT12 для дискет
FAT16 диски до 2гб
UFAT можно использовать нелатинские символы в названиях
FAT32 имя хранится в заголовке файла
MBR – главная загрузочная запись (размер кластера, место загрузки ОС)
FAT – таблица разметки.
имя файла
свойства файлов
начальная позиция на диске
В последнем байте при фрагментации файла – адрес след. фрагмента файла.
Каждый следующий фрагмент в начале имеет ссылку на предыдущий фрагмент.
HPFS – High Performance File System
Super block – аналог главной загрузочной записи
Spear block – информация в процентном отношении о занятости каждой битовой карты (картотека битовых карт)
Bitmap – битовая карта, аналог FAT, показывает, какие данные записаны (размер 8мб)
Билеты для подготовки к экзамену по Информатике. Трофимов Владислав, Махонин Кирилл
NTFS – New technologies file system
Log MFT – загрузочная запись, аналог mbr
MFT – ссылка на адрес журнала событий (записи о каждом файле на диске(имя, владелец, создатель, атрибуты, дата последнего изменения, наличие мягких и твердых ссылок) размером 1 Кб, или любые другие файлы размером до 1кб). Занимает 12%. Если не хватает, то система будет сдвигать границу.
В парикмахерской есть один брадобрей, его кресло и n стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов.
В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается - он уже не ждет); barbers, количество брадобреев 0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей. Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает и спит, пока не придет первый клиент.
Приходя в парикмахерскую, посетитель выполняет процедуру customer, запрашивая доступ к mutex для входа в критическую область. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобождает доступ к mutex и уходит.
Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем самым активизируя поток брадобрея. В этот момент оба - посетитель и брадобрей - активны. Когда посетитель освобождает доступ к mutex, брадобрей захватывает его, проделывает некоторые служебные операции и начинает стричь клиента.
По окончании стрижки посетитель выходит из процедуры и покидает парикмахерскую. В отличие от предыдущих программ, цикла посетителя нет, поскольку каждого посетителя стригут только один раз. Цикл брадобрея существует, и брадобрей пытается найти следующего посетителя. Если ему это удается, он стрижет следующего посетителя, в противном случае брадобрей засыпает. Стоит отметить, что, несмотря на отсутствие передачи данных в проблеме читателей и писателей и в проблеме спящего брадобрея, обе эти проблемы относятся к проблемам межпроцессного взаимодействия, поскольку требуют синхронизации нескольких процессов.
12. Логическая организация ФС. Операции над файлами. Методы доступа к файлам.
Файлы последовательного доступа наиболее просты как в организации, так и в работе с ними. Записи обрабатываются последовательно одна за другой. Информация в таких файлах хранится в виде текста в кодах ASCII. Подобные файлы легко просмотреть на экране, используя любой простейший редактор, или в самом Бейсике. Но, как всегда, у каждой медали две стороны. Простота – хорошо, а последовательность в данном случае – плохо. Если информация об интересующих меня объектах упорядочена в файле по алфавиту, то мне всякий раз придется перебирать практически весь файл, чтобы добраться до нужной записи. Отсюда, при большом информационном объеме файла обработка его резко замедляется.
Файлы прямого доступа хранят информацию в специальном формате, в котором каждая запись занимает строго фиксированную одинаковую с остальными длину. То, что такие файлы могут занимать на диске больше места, чем файлы последовательного доступа, с лихвой компенсируется скоростью работы с ними.
Важной и часто встречающейся задачей, решение которой требует синхронизации, является задача «Читатели - писатели». Эта задача имеет много вариантов. Определить ее можно следующим образом. Имеются данные, совместно используемые рядом процессов. Данные могут находиться в файле в блоке основной памяти или даже в регистрах процессора. Имеются несколько процессов, которые только читают эти данные (Читатели), и несколько других, которые только записывают данные (Писатели). При этом должны удовлетворяться следующие условия.- Любое число читателей могут одновременно читать файл.- Записывать информацию в файл в определенный момент времени может только один Писатель.- Когда Писатель записывает информацию в файл, ни один Читатель не может его читать. Пример использования - работа с библиотечным каталогом. Другим типичным примером служит система автоматизированной продажи билетов. Процессы «Читатели» обеспечивают нас справочной информацией о наличии свободных билетов на тот или иной рейс. Процессы «Писатели» запускают с пульта кассира, когда он оформляет для нас тот или иной билет. Имеется большое количество как «Читателей», так и «Писателей». Наиболее характерная область использования этой задачи в вычислительной системе - при построении систем управления файлами. Два класса процессов имеют доступ к некоторому ресурсу (области памяти, файлам). «Читатели» - это процессы, которые могут параллельно считывать информацию из некоторой общей области памяти, являющейся критическим ресурсом. «Писатели» - это процессы, записывающие информацию в эту область памяти, исключая при этом и друг друга и процессы «Читатели». Широко распространены следующие условия: 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 <
Приоритетное планирование. Алгоритмы SJF и гарантированного планирования представляют собой частные случаи приоритетного планирования . При приоритетном планировании каждому процессу присваивается определенное числовое значение – приоритет , в соответствии с которым ему выделяется процессор. Процессы с одинаковыми приоритетами планируются в порядке FCFS . Для алгоритма SJF в качестве такого приоритета выступает оценка продолжительности следующего CPU burst . Чем меньше значение этой оценки, тем более высокий приоритет имеет процесс. Для алгоритма гарантированного планирования приоритетом служит вычисленный коэффициент справедливости. Чем он меньше, тем больше у процесса приоритет . Алгоритмы назначения приоритетов процессов могут опираться как на внутренние параметры, связанные с происходящим внутри вычислительной системы, так и на внешние по отношению к ней. К внутренним параметрам относятся различные количественные и качественные характеристики процесса такие как: ограничения по времени использования процессора, требования к размеру памяти, число открытых файлов и используемых устройств ввода-вывода, отношение средних продолжительностей I/O burst к CPU burst и т. д. Алгоритмы SJF и гарантированного планирования используют внутренние параметры. В качестве внешних параметров могут выступать важность процесса для достижения каких-либо целей, стоимость оплаченного процессорного времени и другие политические факторы. Высокий внешний приоритет может быть присвоен задаче лектора или того, кто заплатил $100 за работу в течение одного часа. Планирование с использованием приоритетов может быть как вытесняющим , так и невытесняющим . При вытесняющем планировании процесс с более высоким приоритетом , появившийся в очереди готовых процессов, вытесняет исполняющийся процесс с более низким приоритетом . В случае невытесняющего планирования он просто становится в начало очереди готовых процессов. Давайте рассмотрим примеры использования различных режимов приоритетного планирования . Главная проблема приоритетного планирования заключается в том, что при ненадлежащем выборе механизма назначения и изменения приоритетов низкоприоритетные процессы могут не запускаться неопределенно долгое время. Обычно случается одно из двух. Или они все же дожидаются своей очереди на исполнение. Или вычислительную систему приходится выключать, и они теряются. Решение этой проблемы может быть достигнуто с помощью увеличения со временем значения приоритета процесса , находящегося в состоянии готовность.
Литература по операционным системам содержит множество интересных проблем, которые широко обсуждались и анализировались с применением различных методов синхронизации. В этом разделе мы рассмотрим три наиболее известные проблемы.
Проблема обедающих философов
В 1965 году Дейкстра сформулировал и решил проблему синхронизации, названную им проблемой обедающих философов. С тех пор каждый, кто изобретал еще один новый примитив синхронизации, считал своим долгом продемонстрировать достоинства нового примитива на примере проблемы обедающих философов. Проблему можно сформулировать следующим образом: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каждыми двумя тарелками лежит одна вилка.
Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. (Разумеется, это абстракция, даже применительно к философам, но остальные процессы жизнедеятельности для нашей задачи несущественны.) Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает? (Кое-кто считает, что необходимость двух вилок выглядит несколько искусственно. Возможно, нам следует заменить итальянскую пищу блюдами китайской кухни, спагетти - рисом, а вилки - соответствующими палочками.)
Можно изменить программу так, чтобы после получения левой вилки проверялась доступность правой. Если правая вилка недоступна, философ отдает левую обратно, ждет некоторое время и повторяет весь процесс. Этот подход также не будет работать, хотя и по другой причине. Если не повезет, все пять философов могут начать процесс одновременно, взять левую вилку, обнаружить отсутствие правой, положить левую обратно на стол, одновременно взять левую вилку, и так до бесконечности. Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием процесса (по-английски starvation, буквально «умирание от голода». Этот
Термин применяется даже в том случае, когда проблема возникает не в итальянском или китайском ресторане, а на компьютерах).
Вы можете подумать: «Если философы будут размышлять в течение некоторого случайно выбранного промежутка времени после неудачной попытки взять правую вилку, вероятность того, что все процессы будут продолжать топтаться на месте хотя бы в течение часа, невелика». Это правильно, и для большинства приложений повторение попытки спустя некоторое время не является проблемой. Например, в локальной сети Ethernet в ситуации, когда два компьютера посылают пакеты одновременно, каждый должен подождать случайно заданное время и повторить попытку - на практике это решение хорошо работает. Тем не менее в некоторых приложениях предпочтительным является другое решение, работающее всегда и не зависящее от случайных чисел (например, в приложении для обеспечения безопасности на атомных электростанциях).
Внести улучшение, исключающее взаимоблокировку и зависание процесса: защитить пять операторов, следующих за запросом think, бинарным семафором. Тогда философ должен будет выполнить операцию Down на переменной mutex прежде, чем потянуться к вилкам. А после возврата вилок на место ему следует выполнить операцию Up на переменной mutex. С теоретической точки зрения решение вполне подходит. С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам.
Решение, исключает взаимоблокировку и позволяет реализовать максимально возможный параллелизм для любого числа философов. Здесь используется массив state для отслеживания душевного состояния каждого философа: он либо ест, либо размышляет, либо голодает (пытаясь получить вилки). Философ может начать есть, только если ни один из его соседей не ест. Соседи философа с номером i определяются макросами LEFT и RIGHT (то есть если i = 2, то LEFT=
Проблема читателей и писателей
Проблема обедающих философов полезна для моделирования процессов, соревнующихся за монопольный доступ к ограниченному количеству ресурсов, например к устройствам ввода-вывода. Другой известной задачей является проблема читателей и писателей , моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей?
Чтобы избежать такой ситуации, нужно немного изменить программу: если пишущий процесс ждет доступа к базе, новый читающий процесс доступа не получает, а становится в очередь за пишущим процессом. Теперь пишущему процессу нужно подождать, пока базу покинут уже находящиеся в ней читающие процессы, но не нужно пропускать вперед читающие процессы, пришедшие к базе после него. Недостаток этого решения заключается в снижении производительности, вызванном уменьшением конкуренции. В представлено решение, в котором пишущим процессам предоставляется более высокий приоритет.
Проблема спящего брадобрея
Действие еще одной классической проблемной ситуации межпроцессного взаимодействия разворачивается в парикмахерской. В парикмахерской есть один брадобрей, его кресло и п стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит.Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания. У этой задачи существует много аналогов в сфере массового обслуживания, например информационная служба, обрабатывающая одновременно ограниченное количество запросов, с компьютеризированной системой ожидания для запросов.
В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается - он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.
Она является копией переменной customers. Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
Когда брадобрей приходит утром на работу, он выполняет процедуру barber, блокируясь на семафоре customers, поскольку значение семафора равно 0. Затем брадобрей засыпает, и спит, пока не придет первый клиент.
Приходя в парикмахерскую, посетитель выполняет процедуру customer, запрашивая доступ к mutex для входа в критическую область. Если вслед за ним появится еще один посетитель, ему не удастся что-либо сделать, пока первый посетитель не освободит доступ к mutex. Затем посетитель проверяет наличие свободных стульев, в случае неудачи освобождает доступ к mutex и уходит.
Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем
Самым активизируя поток брадобрея. В этот момент оба - посетитель и брадобрей - активны. Когда посетитель освобождает доступ к mutex, брадобрей захватывает его, проделывает некоторые служебные операции и начинает стричь клиента.
По окончании стрижки посетитель выходит из процедуры и покидает парикмахерскую. В отличие от предыдущих программ, цикла посетителя нет, поскольку каждого посетителя стригут только один раз. Цикл брадобрея существует, и брадобрей пытается найти следующего посетителя. Если ему это удается, он стрижет следующего посетителя, в противном случае брадобрей засыпает.
Стоит отметить, что, несмотря на отсутствие передачи данных в проблеме читателей и писателей и в проблеме спящего брадобрея, обе эти проблемы относятся к проблемам межпроцессного взаимодействия, поскольку требуют синхронизации нескольких процессов.