3.4.3 · Механизмы управления параллелизмом

Порядок захвата блокировок против взаимной блокировки

Блокировки test-and-set, сценарий взаимной блокировки двух мьютексов и захват блокировок счетов по стабильному идентификатору перед переводом.

Вопрос для размышления

Как два индивидуально сериализованных ресурса все же могут взаимно заблокироваться, и какое правило упорядочения устраняет этот цикл?

Моделирование успешного и неудавшегося захвата test-and-set
Распознавание циклического ожидания между двумя отдельно удерживаемыми блокировками
Различение взаимного исключения и предотвращения взаимных блокировок
Выбор глобального порядка блокировок по стабильным идентификаторам счетов
Освобождение каждой захваченной блокировки после одной конечной защищенной операции

Первое расписание позволяет левой операции захватить lock a, а правой операции захватить lock b. Затем каждая запрашивает другую блокировку и терпит неудачу. Оба ресурса взаимно исключены, но ни одна смоделированная операция не может продолжить работу, так как расписание содержит циклическое ожидание. Программа представляет такое чередование как явные последовательные переходы состояний.

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

Код SICP682 из 1,048,576 байт UTF-8

(begin
  (define (make-lock) (list #f))
  (define (try-acquire! lock)
    (if (car lock)
        #f
        (begin
          (set-car! lock #t)
          #t)))
  (define (release! lock) (set-car! lock #f))
  (define lock-a (make-lock))
  (define lock-b (make-lock))
  (define left-first (try-acquire! lock-a))
  (define right-first (try-acquire! lock-b))
  (define left-second (try-acquire! lock-b))
  (define right-second (try-acquire! lock-a))
  (list left-first
        right-first
        left-second
        right-second
        (and left-first
             right-first
             (not left-second)
             (not right-second))
        (car lock-a)
        (car lock-b)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Модель взаимной блокировки возвращает (#t #t #f #f #t #t #t). Модель упорядоченного перевода возвращает ((90 50) (45 95) 95 45 #f #f).

На что обратить внимание в трассе

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

Попробуйте сами

Измените программу и сравните результат.

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

Показать подсказку

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

Завершить этот урок

В этой главе пройдено 0 из 21 урока0%