Оптимизация накладных расходов блокировки и краткое описание CAS

задняя часть
Оптимизация накладных расходов блокировки и краткое описание CAS

Замок

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

Говоря о накладных расходах на блокировку, обычно говорят, что накладные расходы на блокировки очень велики, сколько накладных расходов на блокировки, где основное потребление и как повысить производительность блокировок.

замок над головой

Текущий механизм блокировки обычно использует фьютексы (быстрые мьютексы пользовательского пространства), гибридный механизм режима ядра и пользовательского режима. Когда фьютекса нет, как ядро ​​поддерживает синхронизацию и взаимоисключение? Ядро системы поддерживает объект, видимый всем процессам, который используется для управления мьютексами и уведомления заблокированных процессов. Если процесс А хочет войти в критическую секцию, то сначала зайти в ядро, чтобы проверить объект, есть ли другие процессы, занимающие эту критическую секцию, а когда он выйдет из критической секции, также зайти в ядро, чтобы проверить объект, нет ли другие процессы ожидают входа в критическую секцию. Затем разбудите ожидающий процесс в соответствии с определенной стратегией. Эти ненужные системные вызовы (или ловушки ядра) сильно снижают производительность. Чтобы решить эту проблему, появился Futex.

Futex — это механизм синхронизации, который сочетает в себе пользовательский режим и режим ядра. Во-первых, синхронизируемые процессы разделяют часть памяти через mmap.Переменная фьютекса находится в этой общей памяти, и операция является атомарной.Когда процесс пытается войти или выйти из мьютекса, сначала проверьте общую память.Переменная фьютекса, если конкуренции нет, только модифицировать фьютекс, не выполняя системный вызов. Когда процессу сообщают, что есть конкуренция по доступу к переменной фьютекса, все равно необходимо выполнить системный вызов для завершения соответствующей обработки (ожидания или пробуждения). Проще говоря, фьютекс проверяется в пользовательском режиме, (мотивация) если вы знаете, что нет конкуренции, то не надо лезть в ядро, что значительно повышает эффективность low-content.

Мьютекс реализован на основе фьютекса с общими переменными в памяти, если общая переменная установлена ​​внутри процесса, то это блокировка потока, если она установлена ​​в общей памяти между процессами, то это блокировка процесса. Поле _lock в pthread_mutex_t используется для обозначения занятости.Во-первых, используйте CAS, чтобы определить, занята ли _lock.Если она не занята, возвращайтесь напрямую. В противном случае поток принудительно засыпает, вызывая системный вызов SYS_futex через __lll_lock_wait_private. CAS — это инструкция процессора пользовательского режима. Если нет конкуренции, просто измените состояние блокировки и вернитесь, что очень эффективно. Только когда конкуренция найдена, она может попасть в режим ядра через системный вызов. Таким образом, FUTEX представляет собой механизм синхронизации, сочетающий режим пользователя и режим ядра, что обеспечивает эффективность получения блокировки в условиях низкой конкуренции.

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

Лучший способ определить что-то — это протестировать и понаблюдать за ним. Давайте напишем фрагмент кода для проверки накладных расходов на блокировку без конфликтов:

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

static inline long long unsigned time_ns(struct timespec* const ts) {
  if (clock_gettime(CLOCK_REALTIME, ts)) {
    exit(1);
  }
  return ((long long unsigned) ts->tv_sec) * 1000000000LLU
    + (long long unsigned) ts->tv_nsec;
}


int main()
{
    int res = -1;
    pthread_mutex_t mutex;

    //初始化互斥量，使用默认的互斥量属性
    res = pthread_mutex_init(&mutex, NULL);
    if(res != 0)
    {
        perror("pthread_mutex_init failed\n");
        exit(EXIT_FAILURE);
    }

    long MAX = 1000000000;
    long c = 0;
    struct timespec ts;

    const long long unsigned start_ns = time_ns(&ts);

    while(c < MAX) 
    {
        pthread_mutex_lock(&mutex);
        c = c + 1;
        pthread_mutex_unlock(&mutex);
    }

    const long long unsigned delta = time_ns(&ts) - start_ns;

    printf("%f\n", delta/(double)MAX);

    return 0;
}

Примечание. Следующие тесты производительности выполняются в процессоре Tencent Cloud Intel(R) Xeon(R) CPU E5-26xx v4, 1-ядерный, 2399,996 МГц.

После запуска 1 миллиард раз это составляет около 2,2 нс для каждой операции блокировки/разблокировки на блокировку/разблокировку (после вычета времени цикла 2,7 нс).

В случае конфликтов блокировок накладные расходы не так уж и малы.

Во-первых, pthread_mutex_lock фактически вызовет sys_futex, чтобы войти в ядро ​​и попытаться заблокировать.После блокировки поток переходит в спящий режим, что приводит к накладным расходам на переключение контекста и планирование потоков.

Накладные расходы этого процесса можно проверить, написав два потока, которые разблокируют друг друга:

// Copyright (C) 2010 Benoit Sigoure
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/syscall.h>
#include <sys/wait.h>
#include <time.h>
#include <unistd.h>

#include <linux/futex.h>

static inline long long unsigned time_ns(struct timespec* const ts) {
  if (clock_gettime(CLOCK_REALTIME, ts)) {
    exit(1);
  }
  return ((long long unsigned) ts->tv_sec) * 1000000000LLU
    + (long long unsigned) ts->tv_nsec;
}

static const int iterations = 500000;

static void* thread(void* restrict ftx) {
  int* futex = (int*) ftx;
  for (int i = 0; i < iterations; i++) {
    sched_yield();
    while (syscall(SYS_futex, futex, FUTEX_WAIT, 0xA, NULL, NULL, 42)) {
      // retry
      sched_yield();
    }
    *futex = 0xB;
    while (!syscall(SYS_futex, futex, FUTEX_WAKE, 1, NULL, NULL, 42)) {
      // retry
      sched_yield();
    }
  }
  return NULL;
}

int main(void) {
  struct timespec ts;
  const int shm_id = shmget(IPC_PRIVATE, sizeof (int), IPC_CREAT | 0666);
  int* futex = shmat(shm_id, NULL, 0);
  pthread_t thd;
  if (pthread_create(&thd, NULL, thread, futex)) {
    return 1;
  }
  *futex = 0xA;

  const long long unsigned start_ns = time_ns(&ts);
  for (int i = 0; i < iterations; i++) {
    *futex = 0xA;
    while (!syscall(SYS_futex, futex, FUTEX_WAKE, 1, NULL, NULL, 42)) {
      // retry
      sched_yield();
    }
    sched_yield();
    while (syscall(SYS_futex, futex, FUTEX_WAIT, 0xB, NULL, NULL, 42)) {
      // retry
      sched_yield();
    }
  }
  const long long unsigned delta = time_ns(&ts) - start_ns;

  const int nswitches = iterations << 2;
  printf("%i thread context switches in %lluns (%.1fns/ctxsw)\n",
         nswitches, delta, (delta / (float) nswitches));
  wait(futex);
  return 0;
}

Скомпилируйте с помощью gcc -std=gnu99 -pthread context_switch.c.

Результат выполнения — 2003.4ns/ctxsw, поэтому стоимость конфликта блокировок примерно в 910 раз больше, чем отсутствие конфликта, что является неожиданно большой разницей.

Другая программа на языке C может использоваться для проверки накладных расходов на «чистое переключение контекста», когда поток просто использует sched_yield, чтобы отказаться от процессора и не переходит в спящий режим.

// Copyright (C) 2010 Benoit Sigoure
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <http://www.gnu.org/licenses/>.

#include <sched.h>
#include <pthread.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <errno.h>

static inline long long unsigned time_ns(struct timespec* const ts) {
  if (clock_gettime(CLOCK_REALTIME, ts)) {
    exit(1);
  }
  return ((long long unsigned) ts->tv_sec) * 1000000000LLU
    + (long long unsigned) ts->tv_nsec;
}

static const int iterations = 500000;

static void* thread(void*ctx) {
  (void)ctx;
  for (int i = 0; i < iterations; i++)
      sched_yield();
  return NULL;
}

int main(void) {
  struct sched_param param;
  param.sched_priority = 1;
  if (sched_setscheduler(getpid(), SCHED_FIFO, &param))
    fprintf(stderr, "sched_setscheduler(): %s\n", strerror(errno));

  struct timespec ts;
  pthread_t thd;
  if (pthread_create(&thd, NULL, thread, NULL)) {
    return 1;
  }

  long long unsigned start_ns = time_ns(&ts);
  for (int i = 0; i < iterations; i++)
      sched_yield();
  long long unsigned delta = time_ns(&ts) - start_ns;

  const int nswitches = iterations << 2;
  printf("%i thread context switches in %lluns (%.1fns/ctxsw)\n",
         nswitches, delta, (delta / (float) nswitches));
  return 0;
}

«Чистое переключение контекста» потребляет около 381,2 нс/ctxsw.

Таким образом, мы можем грубо разделить накладные расходы на конфликты блокировок на три части: накладные расходы на «чистое переключение контекста», которые составляют около 381,2 нс, и накладные расходы планировщика (перевод потока из спящего режима в готовый или наоборот) составляют около 1622,2 нс. N. В многоядерной системе также возникают накладные расходы на межпроцессорное планирование, и эта часть является дорогостоящей. В реальных сценариях приложений также следует учитывать накладные расходы на промахи кэша и промахи TLB, вызванные переключением контекста, и эти накладные расходы будут только увеличиваться.

Блокировка оптимизации

Из вышеизложенного видно, что на самом деле время тратится не на количество блокировок, а на количество конфликтов блокировок. Сокращение количества конфликтов блокировок является ключом к повышению производительности. Благодаря более тонкой блокировке количество конфликтов блокировок может быть уменьшено. Упомянутая здесь степень детализации включает время и пространство. Например, хеш-таблица содержит серию хэш-сегментов. Если для каждого сегмента установлена ​​блокировка, пространственная степень детализации будет намного меньше — доступы с неконфликтующими хэш-значениями не будут вызвать конфликты блокировок. , что гораздо менее вероятно, чем поддержание блокировки для всей хеш-таблицы. Уменьшение детализации по времени также легко понять.Объем блокировки включает только необходимые сегменты кода, постарайтесь сократить время между получением блокировки и снятием блокировки и, самое главное, никогда не выполняйте никаких операций, которые могут заблокировать в блокировке. . Использование блокировок чтения-записи также является хорошим способом уменьшить конфликты.Операции чтения не являются взаимоисключающими, что значительно уменьшает количество конфликтов.

Если предположить, что в односвязном списке имеется несколько операций вставки/удаления, а основной операцией является поиск, то подход, основанный на одиночной блокировке, будет работать плохо. В этом случае следует рассмотреть возможность использования блокировки чтения-записи, т. е. pthread_rwlock_t, которая позволяет нескольким потокам одновременно выполнять поиск в связанном списке. Операции вставки и удаления по-прежнему блокируют весь связанный список. Предполагая, что выполняется примерно одинаковое количество операций вставки и поиска, но мало операций удаления, нецелесообразно блокировать весь связанный список во время вставки, и в этом случае лучше разрешить в непересекающейся точке связанного списка. вставки, также используя подход, основанный на блокировке чтения-записи. Блокировка выполняется на двух уровнях, связанный список имеет блокировку чтения-записи, каждый узел содержит мьютекс, а во время вставки поток записи устанавливает блокировку чтения для связанного списка и продолжает обработку. Перед вставкой данных заблокируйте узел, после которого должны быть добавлены новые данные, освободите узел после вставки и снимите блокировку чтения-записи. Операция удаления устанавливает блокировку записи в связанном списке. Нет необходимости приобретать блокировки, связанные с узлом, блокировки взаимного исключения устанавливаются только на определенном рабочем узле, что значительно снижает количество конфликтов блокировок.

Поведение самой блокировки также имеет возможность дальнейшей оптимизации.Функция системного вызова sys_futex заключается в том, чтобы усыпить текущий поток, который заблокирован, и позволить процессору использоваться другими потоками.Поскольку потребление этого процесса очень велико , то есть если он залочен Если время не превышает этого значения, то для блокировки в ядро ​​входить не надо - высвободившегося процессорного времени не хватит на потребление. Потребление времени sys_futex достаточно для запуска CAS много раз, то есть для системы с частыми конфликтами блокировок и относительно коротким средним временем блокировки стоит рассмотреть оптимизацию, состоящую в вызове CAS в цикле, чтобы попытаться получить блокировку. (эта операция также называется спин-блокировкой), а затем войти в ядро ​​для фактической блокировки после нескольких сбоев. Конечно, эта оптимизация может работать только в многопроцессорной системе (для ее разблокировки должен быть другой процессор, иначе спин-блокировка не имеет смысла). В реализации pthread в glibc этот механизм можно использовать, установив атрибут PTHREAD_MUTEX_ADAPTIVE_NP в pthread_mutex.

CAS

Некоторые проблемы с замками:

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

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

CAS (comapre и swap или check and set), сравнить и заменить, ссылаясь на вики, — это атомарная инструкция для синхронизации данных потока.

Алгоритм ядра CAS включает три параметра, а именно значение памяти, значение обновления и ожидаемое значение, инструкция CAS сначала проверяет, содержит ли ячейка памяти ожидаемое значение, если да, копирует новое значение в эту ячейку и возвращает true; если нет, вернуть false. CAS соответствует ассемблерной инструкции CMPXCHG и поэтому является атомарным.

bool compare_and_swap (int *accum, int *dest, int newval)
{
  if ( *accum == *dest ) {
      *dest = newval;
      return true;
  }
  return false;
}

Как правило, программа будет использовать CAS в цикле для непрерывного выполнения транзакционной операции, обычно включая копирование общей переменной в локальную переменную, затем использование локальной переменной для выполнения задач по вычислению нового значения и, наконец, использование CAS для сравнения и сохранения. Затем попробуйте отправить модификацию со старым значением и значением памяти локальной переменной.Если попытка не удалась, значение памяти будет прочитано снова, пересчитано, и, наконец, будет использован CAS для попытки отправить модификацию и так далее. Например:

void LockFreeQueue::push(Node* newHead)
{
    for (;;)
    {
        // 拷贝共享变量(m_Head) 到一个局部变量
        Node* oldHead = m_Head;

        // 执行任务，可以不用关注其他线程
        newHead->next = oldHead;

        // 下一步尝试提交更改到共享变量
        // 如果共享变量没有被其他线程修改过，仍为 oldHead，则 CAS 将 newHead 赋值给共享变量 m_Head 并返回
        // 否则继续循环重试
        if (_InterlockedCompareExchange(&m_Head, newHead, oldHead))
            return;
    }
}

Приведенная выше структура данных задает общий головной узел m_Head.При нажатии нового узла новый узел будет добавлен после головного узла, не верьте, что выполнение программы непрерывное, а выполнение ЦП многократное. многопоточный параллельный. До того, как _InterlockedCompareExchange будет CAS, поток может быть запланирован вне, потому что квант времени израсходован, новый запланированный поток завершил операцию отправки, а несколько потоков совместно используют переменную m_Head. В это время m_Head был изменен. Если исходный поток продолжает выполняться, перезапись oldHead в m_Head приведет к потере узлов, выдвинутых другими потоками. Поэтому необходимо сравнить, равен ли m_Head по-прежнему oldHead, если да, то это означает, что головной узел неизменен, и можно использовать newHead для перезаписи m_Head, если нет, то это означает, что другой поток протолкнул новый узел , то вам нужно использовать последнюю версию m_Head, чтобы обновить значение oldHead и повторить цикл. В цикле _InterlockedCompareExchange автоматически назначит m_Head значению oldHead.

АВА-проблема

Потому что CAS нужно проверить, изменилось ли ожидаемое значение и значение памяти при отправке модификации, и если нет, обновить его, но если исходное значение изменится с A на B, а затем на A, то при использовании CAS для проверки это обнаружил, что значение не изменилось, но на самом деле произошел ряд изменений.

Утилизация памяти может вызвать серьезные проблемы с CAS:

T* ptr1 = new T(8, 18);
T* old = ptr1; 
delete ptr1;
T* ptr2 = new T(0, 1);
 
// 我们不能保证操作系统不会重新使用 ptr1 内存地址，一般的内存管理器都会这样子做
if (old1 == ptr2) {
    // 这里表示，刚刚回收的 ptr1 指向的内存被用于后面申请的 ptr2了
}

Проблема ABA — это общая проблема при реализации структур без блокировок, которая в основном может быть выражена как:

  • Процесс P1 считывает значение A
  • P1 приостановлен (исчерпан временной интервал, прерван и т. д.), начинается выполнение процесса P2
  • P2 изменяет значение A на значение B, а затем изменяет его обратно на A
  • P1 пробуждается, и после сравнения обнаруживается, что значение A не изменилось, и программа продолжает выполняться.

Для P1 значение A не изменилось, но фактически A было изменено, и дальнейшее использование может вызвать проблемы. В операциях CAS эта проблема усугубляется тем, что большинство сравнений являются указателями. Рассмотрим следующую ситуацию:

Существует куча (первым пришел, последним вышел) с вершиной и узлом А, узел А в настоящее время находится на вершине кучи, а верхний указатель указывает на А. Теперь есть процесс P1, который хочет извлечь узел, поэтому выполните операцию без блокировки следующим образом.

pop()
{
  do{
    ptr = top; // ptr = top = NodeA
    next_prt = top->next; // next_ptr = NodeX
  } while(CAS(top, ptr, next_ptr) != true);
  return ptr;   
}

Процесс P2 прерывает P1 перед выполнением операции CAS и выполняет ряд операций извлечения и отправки в кучу, так что куча приобретает следующую структуру:

Процесс P2 сначала выталкивает NodeA, а затем выталкивает два NodeB и C. Из-за механизма повторного использования памяти, широко используемого в механизме управления памятью, адрес NodeC согласуется с предыдущим NodeA.

В это время снова запускается P1.При выполнении операции CAS, поскольку top по-прежнему указывает на адрес NodeA (который фактически стал NodeC), значение top меняется на NodeX.В это время структура кучи составляет:

После операции CAS верхний указатель неправильно указывает на NodeX вместо NodeB.

АВА-решение

Тегированная ссылка на состояние, добавление дополнительных битов тега, это как номер версии, например, один из алгоритмов состоит в том, чтобы записывать число изменений указателя в нижней части адреса памяти. следующий CAS вернет ошибку, даже если память Механизм повторного использования приводит к тому же адресу. Иногда мы называем этот механизм АВА', потому что делаем второй А немного отличным от первого. Битовая длина тега повлияет на количество модификаций записи.При существующем ЦП использование 60-битного тега не вызовет проблемы переполнения в течение 10 лет без перезапуска программы, в ЦП X64 он стремится поддерживать 128-битный бит инструкций CAS, поэтому более гарантировано избежать проблем с ABA.

Процесс реализации ссылки на тегированное состояние описан ниже со ссылкой на код библиотеки liblfds.

Один из способов избежать проблемы ABA — использовать более длинные указатели, для чего требуется инструкция CAS, поддерживающая длину двойного слова. Как liblfds реализует 128-битные инструкции на разных платформах?

В liblfds инструкция CAS — это макрос LFDS710_PAL_ATOMIC_DWCAS, и его полная форма выглядит так:

LFDS710_PAL_ATOMIC_DWCAS( pointer_to_destination, pointer_to_compare, pointer_to_new_destination, cas_strength, result)
  • pointer_to_destination: [in, out], указатель на пункт назначения, который представляет собой массив из двух 64-битных целых чисел;
  • pointer_to_compare: [in, out], указатель, используемый для сравнения с целевым указателем, который также является массивом из двух 64-битных целых чисел;
  • pointer_to_new_destination: [in], новый указатель обменивается с указателем назначения;
  • результат: [out], если 128-битный pointer_to_compare равен pointer_to_destination, используйте pointer_to_new_destination для перезаписи pointer_to_destination, и результат возвращает 1; если нет, pointer_to_destination остается неизменным, а значение pointer_to_compare становится pointer_to_destination.

Как видно выше, библиотека liblfds использует одномерный массив из двух элементов для представления 128-битных указателей.

Linux предоставляет cmpxchg16b для реализации 128-битных инструкций CAS, а в Windows используется _InterlockedCompareExchange128. Только 128-битные указатели считаются равными, если они точно равны.

См. реализацию CAS для Windows в разделе liblfds/liblfds7.1.0/liblfds710/inc/liblfds710/lfds710_porting_abstraction_layer_compiler.h:

#define LFDS710_PAL_ATOMIC_DWCAS( pointer_to_destination, pointer_to_compare, pointer_to_new_destination, cas_strength, result ) \
{ \                                              
    LFDS710_PAL_BARRIER_COMPILER_FULL; \
    (result) = (char unsigned) _InterlockedCompareExchange128( (__int64 volatile *) (pointer_to_destination), (__int64) (pointer_to_new_destination[1]), (__int64) (pointer_to_new_destination[0]), (__int64 *) (pointer_to_compare) ); \
    LFDS710_PAL_BARRIER_COMPILER_FULL; \
}

Затем сосредоточьтесь на определении new_top и процессе модификации представления.

new_top — это одномерный массив с двумя элементами, которые являются указателями на struct lfds710_stack_element, помеченными POINTER 0 и COUNTER 1 соответственно. COUNTER эквивалентен тегу tag, упомянутому выше, а POINTER сохраняет реальный указатель узла. В X64 длина указателя составляет 64 бита, поэтому для изменения записи здесь используется 64-битный указатель записи тега.

liblfds инициализирует новый верхний СЧЕТЧИК с помощью исходного верхнего СЧЕТЧИКА + 1, то есть использует СЧЕТЧИК для отметки времени замены ss->top, так что каждый раз, когда заменяется верхний, СЧЕТЧИК в верхнем будет меняться.

Только когда POINTER и COUNTER ss->top и original_top точно равны, new_top перезапишет ss->top, в противном случае ss->top будет использоваться для перезаписи original_top, а в следующем цикле будет использоваться последний original_top для работы и сравните еще раз.

Обратитесь к liblfds/liblfds7.1.0/liblfds710/src/lfds710_stack/lfds710_stack_push.c, реализации стека без блокировки:

void lfds710_stack_push( struct lfds710_stack_state *ss,
                         struct lfds710_stack_element *se )
{
  char unsigned
    result;

  lfds710_pal_uint_t
    backoff_iteration = LFDS710_BACKOFF_INITIAL_VALUE;

  struct lfds710_stack_element LFDS710_PAL_ALIGN(LFDS710_PAL_ALIGN_DOUBLE_POINTER)
    *new_top[PAC_SIZE],
    *volatile original_top[PAC_SIZE];

  LFDS710_PAL_ASSERT( ss != NULL );
  LFDS710_PAL_ASSERT( se != NULL );

  new_top[POINTER] = se;

  original_top[COUNTER] = ss->top[COUNTER];
  original_top[POINTER] = ss->top[POINTER];

  do
  {
    se->next = original_top[POINTER];
    LFDS710_MISC_BARRIER_STORE;

    new_top[COUNTER] = original_top[COUNTER] + 1;
    LFDS710_PAL_ATOMIC_DWCAS( ss->top, original_top, new_top, LFDS710_MISC_CAS_STRENGTH_WEAK, result );

    if( result == 0 )
      LFDS710_BACKOFF_EXPONENTIAL_BACKOFF( ss->push_backoff, backoff_iteration );
  }
  while( result == 0 );

  LFDS710_BACKOFF_AUTOTUNE( ss->push_backoff, backoff_iteration );

  return;
}

Применение принципа CAS

  1. структуры данных без блокировок, см.GitHub.com/Суббота ван дер Сар/Суббота…
  2. CAS в высокопроизводительном разрушителе очереди памяти, ссылкаifeve.com/disruptor/
  3. Оптимистическая блокировка базы данных

Ссылаться на

[wiki Compare-and-swap] En. Wikipedia.org/wiki/com пар…

[wiki ABA problem] En. Wikipedia.org/wiki/ABA_Cheat…

[Реализация очереди без блокировки мыши для левого уха]классная оболочка.cai/articles/82…

[IBM разрабатывает параллельные структуры данных, которые не используют мьютексы]Woohoo. IBM.com/developer Я…

[ABA problem] Pavement 2015.GitHub.IO/lock free pro…

[_InterlockedCompareExchange128] docs.microsoft.com/en-US/CPP/i…

[Принцип реализации мьютекса Linux (pthread_mutex_t)]Woohoo.BBS max.com/A/small 9J2WX VW5…

[Введение в механизм фьютекса]blog.CSDN.net/Есть 33988979/Ах…

[an-introduction-to-lock-free-programming] Это pre.com/20120612/press…

[Проблемы производительности на многопроцессорных, многопоточных и многопроцессорных вычислительных платформах]blog.CSDN.net/J Milk/art IC…

[Implement Lock-Free Queue] Эта функция работает. Я упоминал. Простой. Quota/view doc/Dow…

[Тест производительности переключения контекста и планирования потоков]GitHub.com/complaint, что/conte…

[Тест производительности чистого переключения контекста]GitHub.com/complaint, что/conte…

[блокировка над головой]Чин тоже GitHub.IO/2015/12/31/…

[Анализ реализации мьютекса пакета pthread]blog.CSDN.net/Амулет того же типа/Ах…

[IBM Universal Thread: Подробное объяснение потоков POSIX]Woohoo. IBM.com/developer Я…

Категории