Мониторинг реализации Hoare с использованием семафоров?

Question

Это мой экзамен за 4 дня, и я только что говорил со своим лектором, и он был крайне неясен относительно этой части лекции, и я действительно боролся со многими студентами, как это понять.

В основном, если вы хотите внедрить монитор Hoare с помощью семафора, какова последовательность шагов?

Ниже псевдокод

] 3

Обновить:

Я начинаю понимать это сейчас

поэтому первый слайд предназначен для доступа к монитору

если вы единственный, то вы вызываете wait(mutex)

залезай в монитор делай свои дела и уходи

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

для 2-го слайда с ожиданием (условие) и сигналом (условие)

когда u wait(c): c_count++ // число процессов, ожидающих этого условия, увеличивается на единицу if(next_count>0) up(next) // если число ожидающих процессов, которые хотят попасть в монитор, больше нуля, вверх (следующий), разблокировать один из процесса ожидания

else up(mutex) // если вы единственный, тогда up mutex, так что кто-то еще садится (c_sem) // блокирует себя для сна c_count-- // вы просыпаетесь, так что число процессов, ожидающих уменьшения этого условия

для части сигнала (с):

if (c_count> 0) // если число процессов, ожидающих этого условия, больше 0

next_counter ++ // номер процесса, который хочет попасть в монитор, увеличивается на единицу вверх (c_sem); // разблокировать один из процессов, ожидающих это условие down (next) // если место доступно, в противном случае получить блокировку и присоединиться к списку ожидающих процессов next_count--; // ты просыпаешься и пытаешься попасть в монитор

Answer 1

Чувак, я понимаю, почему ты запутался. Проблема здесь в том, что этот пример объединяет два понятия.

Семафор - это форма мьютекса. В абстрактном виде мьютекс - это просто переменная, которую можно атомарно увеличивать или уменьшать. Ваша функция приращения увеличивается. Ваша функция down уменьшает событие, если несколько процессов одновременно работают вверх или вниз. Если вы просто составите эквивалент count = count + 1, вы получите случайные результаты, если несколько процессов будут пытаться увеличиваться одновременно.

В реальном мире (за пределами научного сообщества) семафор делает больше, чем просто увеличивает. Вы также можете подождать на семафоре.

Итак, если я сделаю

 real_world_down (semaphore)

Мой процесс уменьшает семафор. Если ни один процесс (или поток) не заблокировал семафор (обычно = 0, где 1 является отправной точкой), мой процесс продолжается. Если другой процесс уже заблокировал семафор (значение после down < 0), мой процесс ждет.

Когда процесс, который заблокировал семафор, завершается и делает

 real_world_up (semaphore)

Операционная система выбирает один из ожидающих процессов для автоматического запуска.

Таким образом ваш монитор Hoare выглядит

  var 
     semaphore ; 
  Procedure Monitor

       real_world_down (semaphore) ;

       /* do whatever you want */

       real_world_up (semaphore) ;

 End ;

Или мы могли бы написать это как:

  var 
     semaphore ; 
  Procedure Monitor

       lock (semaphore) ;

       /* do whatever you want */

       unlock (semaphore) ;

 End ;

Это часть монитора. Часть вашего примера, которая вводит в заблуждение, состоит в том, что это плохо написанная блокировка / разблокировка с использованием академических семафоров, которые просто увеличиваются и уменьшаются атомарно и не знают, кто их ожидает.

Это ожидание эквивалентно моему замку. Это равносильно тому, что моя разблокировка полностью заправлена.

На этом этапе я бы оставил вам в качестве упражнения создание функции блокировки, которая позволит только одному процессу / потоку получить блокировку с использованием пары семафоров, но позволит нескольким процессам ждать и, когда разблокировано, позволит одному процессу ожидания / поток для продолжения.

Требуется функция разблокировки, которая разблокирует пару мьютексов, чтобы позволить одному процессу / потоку продолжить.

Answer 2

Прежде всего - я думаю, что 2 часа - это не так много времени, чтобы успокоить тебя, поэтому я даже не пытаюсь.

С другой стороны: это экзамен, а не хакатон. Сказав это,... почему бы вам не придерживаться академического уровня, который есть у слайдов вашего профессора.

Если вам нужна другая версия объяснения фундаментальной работы гениального CAR Hoare, чем взглянуть на эту PowerPoint - вы можете прочитать ее все, но самой важной для вас страницей должна быть страница 15: MonitorPPT

И: если вы хотите прочитать оригинальную статью после экзамена - чтобы подготовиться к борьбе за очки, которые вы не получили, или просто для удовольствия - вот оно: CAR Hoare - Мониторы: концепция структурирования операционной системы

Всего наилучшего на экзамене, Том!