Сильный Семафор Очередь Дисциплины и Голодания

Question

В книге Уильяма Сталлингса по операционным системам он определяет сильный семафор как тот, который имеет дисциплину очереди FIFO, и слабый семафор , который неупорядочен.Конечно, есть другие дисциплины очереди для сильных семафоров, например, по приоритету?Или это больше не будет сильный семафор, поскольку голод станет возможным?(Сталлингс говорит, что сильные семафоры не допускают голодания.) Является ли основное различие между сильным и слабым упорядоченным / неупорядоченным, или голодание возможно / невозможно?

Answer 1

Да, одна не голодная возможность без FIFO (среди многих) - это выбрать следующий процесс циклическим образом. Например, если порядок равен 1, 2, 3, 4, и когда 1 содержит семафор, 4, а затем 3 запрашивают его, то следующий процесс увеличивается до 3. Ни один процесс P не останавливается, поскольку после каждого запроса P каждый другой процесс имеет не более одного критического раздела, прежде чем запрос P будет удовлетворен.

Определения «сильного семафора» на первых страницах обращений от Google делятся на «без голода» и «FIFO». Какой из них «правильный» - дело вкуса - учитывая этот беспорядок (и общее чрезмерное употребление сильного в качестве прилагательного в математическом письме), я бы, вероятно, не использовал ни того, ни другого.

Answer 2

Что касается литературы по семафорам, я никогда не видел (с моими ограниченными знаниями) кого-либо, кто использовал бы FIFO или какую-либо форму упорядочения в качестве критерия слабой / сильной категоризации. На самом деле, голодная свобода тоже не всегда критерий. Первоначальная литература (из-за того, что Моррис ('79) , Мартин и Дж. Р. Берч ('85) , Уддинг ('86) , Фридберг и Петерсон ('87) и Халдар и Субраманиан ('88) ) использовали определенные характеристики операций 'P' и 'V' определить слабый семафор. Интересно, что все определения цитируемых исследователей в конечном итоге предполагают возможное голодание в случае слабых семафоров. Кроме того, хотя FIFO гарантирует свободу от голода, ссылка на термин FIFO или некоторая форма упорядочения, на мой взгляд, ограничивает поведение семафора. Одна из форм ограничения может заключаться в том, что, например, упорядочение FIFO подразумевает, что к семафору прикреплен какой-то буфер, чтобы отслеживать заблокированные процессы / потоки в операции 'P' . , Для аппаратной реализации семафоров это определение может быть слишком ограничительным. Другая форма ограничений может заключаться в том, что вместо рассмотрения всех возможных схем упорядочения с одинаковым ограниченным обгоном k (т. Е. Ни один процесс не будет обгонен более чем k раз), можно ограничиться Рассмотрите каждую схему как один другой вид семафора. Таким образом, мое личное мнение состоит в том, чтобы определить слабый семафор как тот, который НЕ гарантирует свободу от голода (но гарантирует свободу тупиков). Тем не менее, если вы более глубоко погружены в исследовательскую деятельность, то вы всегда можете использовать более математические и / или детализированные определения по своему усмотрению.

Answer 3

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