Билетный замок ограничен без ожидания?(при определенных допущениях) - PullRequest
Новая
       22

Билетный замок ограничен без ожидания?(при определенных допущениях)

1 голос
/ 11 октября 2011

Я говорю о блокировке заявки, которая может выглядеть следующим образом (в синтаксисе псевдо-C): 

    unsigned int ticket_counter = 0, lock_counter = 0;

void lock() {
    unsigned int my_ticket = fetch_and_increment(ticket_counter);

    while (my_ticket != lock_counter) {}
}

void unlock() {
    atomic_increment(lock_counter);
}

Давайте предположим, что такая блокировка заявки синхронизирует доступ к критической секции S, которая не требует ожиданиявыполнение критического раздела занимает ровно c циклов / инструкций.Предполагая, что в системе не более p потоков, синхронизация S с использованием блокировки заявок ограничена без ожидания?

По моему мнению, так и есть, поскольку блокировка билетов является справедливой и, следовательно, верхняяожидание - O (p * c).

Я ошибаюсь?Я немного смущен.Я всегда думал, что блокировка подразумевает не быть (ограниченной) без ожидания из-за следующего утверждения: «Невозможно построить реализацию без очереди ожидания, стека, очереди приоритетов, набора или списка из набора атомарных регистров.«.(Следствие 5.4.1 в Искусстве многопроцессорного программирования, Херлихи и Шавит)

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

Напомним определение ограниченного ожидания без ожиданияв «Искусстве многопроцессорного программирования», стр.59 Херлихи и Шавита:

«Метод не требует ожидания, если он гарантирует, что каждый вызов завершает свое выполнение за конечное число шагов.свободен, если есть ограничение на количество шагов, которые может выполнить вызов метода. "

1 Ответ

1 голос
/ 11 октября 2011

Что ж, я считаю, что вы правы, с некоторыми оговорками.

А именно, свойство ограниченного бездействия сохраняется, только если критический раздел S не является вытесняющим, что, я полагаю, вы можете гарантировать только для ядракосмический код (путем отключения прерываний в критическом разделе).В противном случае ОС может решить переключиться на другой поток, пока один поток находится в критической секции, а затем время ожидания не ограничено, нет?

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

...