Как реализовать приоритетную блокировку только с Compare_and_swap? - PullRequest
Новая
       20

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

2 голосов
/ 28 января 2010

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

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

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

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

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

Спасибо!

1 Ответ

0 голосов
/ 09 апреля 2012

Вам понадобится список ожидающих потоков. Вам необходимо добавлять и удалять элементы из списка безопасным для потоков способом. Вам нужно будет иметь возможность спать потоки, которые не могут получить блокировку. Вам нужно будет пробудить 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 установлен достаточно высоко, чтобы он обнаружил, что владелец блокировки не активен.

...