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

Question

В многопоточном программировании мы можем найти разные термины для синхронизации передачи данных между двумя или более потоками / задачами.

Когда точно мы можем сказать, что какой-то алгоритм:

1)Lock-Free
2)Wait-Free
3)Wait-Freedom

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

1. Алгоритм предсказывает максимальное время выполнения этой подпрограммы.
2. Поток, который вызывает эту подпрограмму в начале, устанавливает уникальную ссылку (внутри этой подпрограммы).
3. Другие потоки, вызывающие ту же самую процедуру, проверяют эту ссылку и, если она установлена, подсчитывают количество тактов ЦП (время измерения) первого задействованного потока. Если это время на долгое время прерывает текущую работу вовлеченного потока и переопределяет его работу.
4. Поток, который не завершил задание, потому что был прерван из планировщика заданий (прерван) в конце, проверьте ссылку, если не принадлежит ему, повторите задание еще раз.

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

Добавлено RingBuffer.InsertLeft Функция:

function TgjRingBuffer.InsertLeft(const link: pointer): integer;
var
  AtStartReference: cardinal;
  CPUTimeStamp    : int64;
  CurrentLeft     : pointer;
  CurrentReference: cardinal;
  NewLeft         : PReferencedPtr;
  Reference       : cardinal;
label
  TryAgain;
begin
  Reference := GetThreadId + 1;                 //Reference.bit0 := 1
  with rbRingBuffer^ do begin
TryAgain:
    //Set Left.Reference with respect to all other cores :)
    CPUTimeStamp := GetCPUTimeStamp + LoopTicks;
    AtStartReference := Left.Reference OR 1;    //Reference.bit0 := 1
    repeat
      CurrentReference := Left.Reference;
    until (CurrentReference AND 1 = 0)or (GetCPUTimeStamp - CPUTimeStamp > 0);
    //No threads present in ring buffer or current thread timeout
    if ((CurrentReference AND 1 <> 0) and (AtStartReference <> CurrentReference)) or
      not CAS32(CurrentReference, Reference, Left.Reference) then
      goto TryAgain;
    //Calculate RingBuffer NewLeft address
    CurrentLeft := Left.Link;
    NewLeft := pointer(cardinal(CurrentLeft) - SizeOf(TReferencedPtr));
    if cardinal(NewLeft) < cardinal(@Buffer) then
      NewLeft := EndBuffer;
    //Calcolate distance
    result := integer(Right.Link) - Integer(NewLeft);
    //Check buffer full
    if result = 0 then                  //Clear Reference if task still own reference
      if CAS32(Reference, 0, Left.Reference) then
        Exit else
        goto TryAgain;
    //Set NewLeft.Reference
    NewLeft^.Reference := Reference;
    SFence;
    //Try to set link and try to exchange NewLeft and clear Reference if task own reference
    if (Reference <> Left.Reference) or
      not CAS64(NewLeft^.Link, Reference, link, Reference, NewLeft^) or
      not CAS64(CurrentLeft, Reference, NewLeft, 0, Left) then
      goto TryAgain;
    //Calcolate result
    if result < 0 then
      result := Length - integer(cardinal(not Result) div SizeOf(TReferencedPtr)) else
      result := cardinal(result) div SizeOf(TReferencedPtr);
  end; //with
end; { TgjRingBuffer.InsertLeft }

Вы можете найти RingBuffer здесь: RingBuffer , функции CAS: FockFreePrimitives и тестовую программу: RingBufferFlowTest

Answer 1

Я собираюсь поработать над этим, хотя формально не обучен и на самом деле не волнует, если это домашнее задание, так как то, что спрашивает опера, определяет «какой алгоритм», который для меня (поскольку плакат создает работу) - «нет ожидания» программирование состояния, включающее кортежи выполнения - именно такие вещи, которые системное программирование должно решать, в частности,

1. 1) Алгоритм предсказывает максимум время выполнения этой подпрограммы.

Необходимо определить размер набора данных, а также "O" структуры данных, примененной к набору данных. Это может включать «вырожденные случаи» (вещи, которые никто не планировал), которые приводят к хаосу в непредвиденные моменты. Таким образом, без дальнейших подробностей, выбирается хороший подход «общего случая», который имеет известные режимы сбоев и будет восстанавливаться без «разрушенных выходных». У Роберта Седжвика есть самая продвинутая работа, с которой я могу добиться какого-либо прогресса - работа очень четкая письменные ответы на вопросы, которые вы задаете.

2. 2) Поток, который вызывает эту процедуру в начало набора уникальных ссылок, что значит, что внутри этой рутины.

Некоторые языковые барьеры здесь, но я собираюсь догадаться, что вы спрашиваете, что путь выполнения кода (последовательность инструкций) начинается с «уникальной» «ссылки» на его набор данных - таким образом, уникальная ссылка означает именно это - поэтому мы просто перечитаем определение этого в стандартном словаре. (не собираюсь быть банальным, вот что я вижу здесь)

3. 3) Другие темы, которые вызывают та же самая рутина проверяет это ссылка и если установлено, чем считать количество тактов процессора (время измерения) Первая вовлеченная нить. Если это время это долго прерывать ток работа вовлеченного потока и переопределяет его работу.

Подсчет ссылок. Хорошо изучили - просто продолжайте читать и кодировать. Проработай это. Прерывание просроченного завершения потока чревато невидимыми режимами сбоя. Чтобы быть правдивым, выполнение реального планирования (потоков или процессов) выполняется правильно только на оборудовании, предназначенном для выполнения этой задачи. Ваш пост «Оптимизация сборки» работает на уровне, где это можно сделать. Предлагаю изучить алгоритм "AVL" Zero-Page. В какой-то момент процессор и последовательность инструкций, выполняющих планирование, по определению проблемы будут нуждаться в эксклюзивной блокировке некоторого значения -> в общем, хитрость заключается в том, чтобы не иметь двух потоков, пытающихся получить два элемента для блокировки без помех от другого указателя инструкций.

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

4. 4) Нить, которая не закончила работу потому что был прерван из задачи планировщик (отдан) в конце проверьте ссылку, если не принадлежит ему повторить задание снова.

Это задача планировщика.

Answer 2

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

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