Как реализовать приоритетную блокировку только с помощью compare_and_swap?

Учитывая только сравнение и обмен, я знаю, как реализовать блокировку.

Однако, как мне реализовать спин-блокировку

1) несколько потоков могут блокироваться на нем при попытке блокировки 2), а затем потоки разблокируются (и получают блокировку) в том порядке, в котором они были заблокированы на нем?

Это вообще возможно? Если нет, то какие еще примитивы мне нужны?

Если да, то как мне это сделать?

Спасибо!


locking compare-and-swap
person anon    schedule 28.01.2010    source источник

Ответы (1)


arrow_upward
0
arrow_downward

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

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

cFails = 0
while (1) {
  NewState = OldState = State;
  if (cFails > 3 || OldState.Lock) {
    sleep();  // not too sophisticated, because they cant be awoken
    cFails = 0;
    continue;
  }

  Look for item in skiplist
  return item if we found it

  // to add the item to the list we need to lock it

  // ABA lock uses a version number
  NewState.Lock=1;
  NewState.nVer++;
  if (!CAS(&State,OldState, NewState)) {
    ++cFails;
    continue; 
  }

  // if the thread gets preempted right here, the lock is left on, and other threads
  // spinning would waste their entire time slice.

  // unlock
  OldState = NewState;
  NewState.Lock = 0;
  NewState.nVer++;
  CAS(&State, OldState,NewState);  
}

Мы ожидаем, что список пропуска обычно находит элемент и лишь изредка добавляет его. У нас редко бывает гонка, которую нужно добавить, даже при большом количестве потоков. Мы проверили это с наихудшим сценарием, состоящим из множества потоков, добавляющих и ищущих миллионы элементов в один список. В результате мы редко видели, чтобы потоки не могли получить блокировку. Так что простой подход, который является высокой производительностью для ожидаемого случая, работает для нас. Есть одна плохая вещь, которая может случиться - поток вытесняется, удерживая блокировку. Это происходит, когда cFails > 3 ловит это и усыпляет ожидающие потоки, чтобы мы не тратили их кванты времени на миллион бесполезных вращений. Таким образом, cFails имеет достаточно высокое значение, чтобы определить, что владелец блокировки неактивен.

person johnnycrash    schedule 09.04.2012