Как семафорная очередь защищена несколькими потоками?

Question

В одном из интервью меня спросили...

Wait(semaphore sem) {                           
   DISABLE_INTS
   sem.val--
   if (sem.val < 0){
      add thread to sem.L
      block(thread)
    }
ENABLE_INTS

Выше приведена реализация ожидания семафора (скопированная из другого потока). Как защищена очередь sem.L, когда несколько потоков пытаются поставить в очередь (когда им не удается получить блокировку)? Берем ли мы блокировку перед обновлением очереди?

Answer 1

Это реализация для системы с одним ядром. Параллелизм управляется отключением прерываний во время критических секций. Вот что значит "DISABLE_INTS" и "ENABLE_INTS" в этом коде.

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

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

Переключатели контекста бывают двух видов: добровольные и невольные. Произвольное переключение контекста происходит, когда код явно запрашивает его. Этот код не запрашивает переключение контекста, так что это не проблема. Непроизвольное переключение контекста может быть инициировано только прерыванием, и этот код отключает прерывания в его критической секции. Это был типичный способ, которым "блокировки" были реализованы в коде ядра для одноядерных систем.