Считаю себя близко знакомым с многопоточным программированием, но только из-за некоторых успехов в прикладной области, а не из-за понимания всех процессов, стоящих за потоками, примитивами синхронизации и т.п. Успехи были связаны сначала с применением pthread под linux при реализации сетевых серверов, затем связаны с применением boost::thread, boost::mutex, boost::condition_variable и т.п. в кросс-платформенных приложениях. Что стоит за вызовом pthread_lock() или блокировкой примитива из boost — не знаю, ассемблерный код не смотрел.

Понимаю, что синхронизация потоков реализуема на процессоре, если на нём есть (атомарная) машинная инструкция типа compare-and-change. Или ещё что-то? Догадываюсь, что высокоуровневая сущность типа семафор (который wait/post, [0,1,2,...)) достаточна, чтобы заменить собой мьютекс (который lock/unlock).

Интересно: (наивно и в лоб)

1. На каких конкретно машинных командах современных актуальных процессоров (intel core, arm v7, ...) обычно реализована (или может быть реализована) синхронизация? Какая последовательность ассемблерных команд обычно реализует семафор, например? (желателно с комментариями, чтобы было понятно как работает механизм и видно, где там атомарность).
2. Как изнутри устроена pthreads — делает ли она вызовы в ядро linux? Какие основные вызовы WinAPI наших дней являются краеугольным камнем меж-поточной синхронизации и вообще нужны ли вызовы в ядро? Подозреваю, что нужны, ведь сон (в который надо уйти, если примитив синхронизации заблокирован)- это понятие шедулера ОС.
3. Какие ядерные вызовы в linux/windows на тему синхнонизации потоков существуют вообще, на каких местах рейтинга быстродействия они находятся? Какие устаревшие, какие новые? Какие для каких особых ситуаций?
4. Какие современные/хитрые/быстрые принципы синхронизации потоков сущетвуют, возможно без вызовов в ядро? Например рассчитанные на то, что ресурс заблокирован менее короткое время, чем требуется процессорного времени на гуляние внутри соответствующего вызова ядра?
5. К каким WinAPI / linux-kernel-API вызовам сводятся основные манипуляции с примитивами синхронизации из boost?
6. Работал с Qt4, но никогда не было желания воспринимать её как библиотеку для чего-то, отличного от интерфейса. Никогда не стану использовать её сетевые или многопоточные средства. Но если кто-нибудь черкнёт про особенности реализации средств синхронизации потоков в Qt4 — будет спасибо.
7. Чего такого хитрого желательно понимать или почитать при разработке многопоточных приложений для многопроцессорных машин с NUMA-блоками и прочими крутыми вещами?
8. Совсем нечёткий вопрос. Что почитать на тему снижения хаотичности переключения/переназначения (между процессорами) потоков на многопроцессорных машинах с целью минимизации порчи кешей разных ЦП? Вопрос должен быть связан с вопросом (7).

Спасибо.

P.S.
Ясно, что я бы не мучал форум дурацкими вопросами, усердно поковырявшись в исходниках соответствующих библиотек. Но если мимо будет пробегать гуру, которому будет не лень черкнуть ответ на эти вопросы, ковыряние в исходниках было бы более замотивировано и сужено.

Я тоже не эксперт, но пару полезных ссылок могу привести:
Spinlock
Compare And Swap
Еще тут можно поискать посты, remark на эту тему писал много когда то.

Здравствуйте, pkl, Вы писали:

Пока у меня настроение, распишусь достаточно подробно.

pkl>Понимаю, что синхронизация потоков реализуема на процессоре, если на нём есть (атомарная) машинная инструкция типа compare-and-change. Или ещё что-то? Догадываюсь, что высокоуровневая сущность типа семафор (который wait/post, [0,1,2,...)) достаточна, чтобы заменить собой мьютекс (который lock/unlock).

Не всегда. Мьютексы отличаются тем, что они кроме обычных, которые эмулируются семафорами, могут быть также recursive (это когда один агент может захватывать один мьютекс много раз без дедлока, лишь бы освободил столько же раз) и error-checked (когда явно проверяют попытку захвата тем же агентом).
На семафоре такого не сделать. Так что множества мьютексов и семафоров не вложены первое во второе, а пересекаются их частями.

pkl>1. На каких конкретно машинных командах современных актуальных процессоров (intel core, arm v7, ...) обычно реализована (или может быть реализована) синхронизация?

x86 — на атомарных обменах (как просто XCHG, так и CMPXCHG). Аналогично для Sparc.
ARM — на шаблоне поведения LL/SC (см. соотв. статьи хотя бы в википедии). То же для PPC, MIPS, Alpha.

pkl> Какая последовательность ассемблерных команд обычно реализует семафор, например? (желателно с комментариями, чтобы было понятно как работает механизм и видно, где там атомарность).

Давайте разделим несколько базовых случаев.

1. Агент — процессор/ядро/процессорный тред/etc., в общем, выделенная часть железки с собственным потоком
команд, и соревнуется с такими же железными участниками. В таком случае базовый примитив синхронизации — spinlock — потому что он spinning, то есть нет никаких вариантов, кроме как крутиться вокруг ячейки, читая состояние и ожидая нужного. (Оптимизация через, например, MONITOR/MWAIT имеет место быть, но не меняет принципа.)

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

3. Агент — тред, но шедулер не помогает (ну вот так получилось).

Для каждого из них свой специфический метод. Начнём с первого.
Представим себе функцию:

int atomic_xchg_int(int *where, int newvalue);

меняет атомарно и возвращает старое значение. Назначим свободному состоянию — 0, а занятому — 1.
Тогда спинлок блокируется так:

void spin_lock(volatile int *where) {
  for(;;) {
    if (*where == 0) {
       int old = atomic_xchg_int(where, 1);
       if (old == 0) { // успешно захватили
         mb();
         return;
       }
    }
  }
}

То есть читаем до посинения, пока не увидим 0. Увидели — пытаемся успеть засунуть в ячейку именно нашу 1
(а не другие). Если получилось, то старое будет 0, значит, всё ok. Нет — увидим 1 — значит, нас опередили, тогда ждём дальше. Не надо экономить на цикле чтения, пытаясь записать каждый раз: только задрочите шину без толку, мешая остальным.

mb() — это барьер памяти, на чтение или полный (потому что чтение 0 из ячейки самого лока должно отработаться гарантированно до любых следующих чтений). На x86 это превращается в no-op, на других архитектурах может быть реальной командой. Освобождение такого лока — запись 0 в ячейку, но с барьером перед записью (чтобы предыдущие записи отработались до освобождения лока). В терминах C++ atomic, mb после чтения — это чтение с acquire semantics, а mb до записи — это запись с release semantics.

Можно делать более навёрнуто. Например, во FreeBSD одно время были спинлоки из 32-битных переменных, где старшие 8 это id процессора (0xff — свободен), а остальные — счётчик рекурсивных захватов. В таком случае просто обмен не годится, нужно сравнение с обменом (запись (id<<24)+1 должна выполняться только если в ячейке продолжает лежать 0xff000000). В остальном метод тот же — ждём, пока не появится значение, которое можно считать признаком свободы мьютекса, и тогда пытаемся захватить его:

void spin_lock(volatile uint32_t *where) {
  unsigned myid = get_cpu_id();
  if ((*where >> 24) == myid) { // уже мы владеем, просто увеличим счётчик
    ++*where;
    return;
  }
  for(;;) {
    if (*where == 0xff000000u) {
      uint32_t old;
      if (atomic_cmpset_int(where, (get_cpu_id() << 24) + 1, &old)) // получилось поменять
      {
        mb();
        return;
      }
    }
  }
}

Тут надо заметить, что от обработчика прерываний так не защититься — если тот прервёт нас с захваченным спинлоком и будет ждать того же спинлока, то процессор уйдёт в бесконечный цикл. Поэтому перед захватом спинлока, разделяемого с обработчиком прерывания, надо запрещать прерывания, а разрешать их после освобождения спинлока. Это иногда называется "квадратная сериализация", в противоположность "скользящей". В Linux это всякие spin_lock_irqsave().

Теперь случай 2 — агенты — треды под шедулером. Тут можно, конечно, пытаться захватывать мьютекс методом того же спинлока. Но если это быстро не получается (например, за 100 итераций цикла), то надо уже дёргать системный вызов. Иногда (например, Mutex в WinAPI) это (звать ядро) единственный допустимый вариант. Шедулер должен уметь 1) ставить тред в очередь ждущих на мьютексе, 2) переключать выполнение на другой тред. Мьютексы не разрешается использовать в обработчиках прерываний не под шедулером, но разрешается в порождённых из них чисто ядерных тредах для продолжения обработки пришедших по прерыванию данных.

Случай 3 — спинлоки как в 1, но плюс к тому явное переключение на другой тред через sched_yield() с аналогами.

pkl>2. Как изнутри устроена pthreads — делает ли она вызовы в ядро linux?

Делает, конечно. Порождение треда это вызов clone() с флагами, которые дают общее пространство виртуальной памяти, файловых дескрипторов и тому подобного. Ожидание мьютекса делается адаптивно — если не сумели быстро захватить, зовётся то же самое через futex вызовы в ядре.

pkl> Какие основные вызовы WinAPI наших дней являются краеугольным камнем меж-поточной синхронизации и вообще нужны ли вызовы в ядро? Подозреваю, что нужны, ведь сон (в который надо уйти, если примитив синхронизации заблокирован)- это понятие шедулера ОС.

Именно. Но, например, критическую секцию оно пытается захватить не уходя в ядро, а уходит только если не получается (та же адаптивная схема). А вот то, что явно зовётся Mutex, получает вызов сразу, потому что оно вообще не является сущностью адресного пространства процесса.

pkl>3. Какие ядерные вызовы в linux/windows на тему синхнонизации потоков существуют вообще,

Именно ядерные для userland?
В случае Linux это операции с futex, через них делается всё остальное.

Ну а про внутри ядра я чуть уже рассказал.

pkl>4. Какие современные/хитрые/быстрые принципы синхронизации потоков сущетвуют, возможно без вызовов в ядро? Например рассчитанные на то, что ресурс заблокирован менее короткое время, чем требуется процессорного времени на гуляние внутри соответствующего вызова ядра?

См. выше про адаптивный метод захвата. А вообще хитростей много. Например, вместо описанного выше кручения вокруг одной ячейки может быть их целый массив и общая переменная — индекс. Не помню, как это зовётся, но получается быстрее.

Здравствуйте, netch80, Вы писали:


Крутой ответ! Под него надо идти чай наливать (-; Хорошее чтиво, не на 1 подход. Спасибо.

Здравствуйте, netch80, Вы писали:

N>Не всегда. Мьютексы отличаются тем, что они кроме обычных, которые эмулируются семафорами, могут быть также recursive (это когда один агент может захватывать один мьютекс много раз без дедлока, лишь бы освободил столько же раз) и error-checked (когда явно проверяют попытку захвата тем же агентом).
N>На семафоре такого не сделать. Так что множества мьютексов и семафоров не вложены первое во второе, а пересекаются их частями.

Спорим, можно сделать? Ибо, семафор образует базис.
Всё, что нам нужно — это ещё функцию get_tid(), возвращающую хэндл текущего потока.

// базовый API
semaphore_t sem_init(int initial_level);
void sem_take(semaphore_t);
void sem_give(semaphore_t);
thread_id_t get_tid();

// рекурсивный мьютекс
class mutex
{
  semaphore_t sem;
  thread_id_t tid;
  int         count;
  bool        recursive;

public:
  explicit mutex(bool rec) : sem(sem_init(1)), tid(BAD_HANDLE), count(0), recursive(rec) {}

  void lock()
  {
    if(ATOMIC tid == get_tid())
    {
      // это значит, что семафор уже опущен нами

      if(!recursive)
        fail_some_way(); // исключение, код ошибки, и т.п.

      ++count;
    }
    else
    {
      sem_take(sem);
      // с этого момента семафор опущен нами, мы сами себя защитили
      ATOMIC tid = gettid();
      count = 1;
    }
  }

  void unlock()
  {
    if(ATOMIC tid != get_tid())
      fail_some_way();

    // в любом случае, семафор уже опущен нами - сами себя защитили
    if(--count == 0)
    {
      ATOMIC tid = BAD_HANDLE;
      sem_give(sem);
    }
  }
};

Поскольку одну из проверок (tid == gettid()) нужно сделать до захвата основного семафора, — то все операции с tid придётся совершать атомарно.
Для этого маньяки-пуристы могут завести ещё один семафор, а прагматики — воспользоваться соответствующими функциями. Тут даже CAS не нужно

Здравствуйте, Кодт, Вы писали:

N>>На семафоре такого не сделать. Так что множества мьютексов и семафоров не вложены первое во второе, а пересекаются их частями.
К>Спорим, можно сделать? Ибо, семафор образует базис.

Ты неправильно понял, что я имел в виду. Обвязка вокруг семафора — это уже не сам семафор.

Но пример полезный, как для данного треда, пойдёт как обучающий. Только тут надо пояснить, что под атомарными операциями имеется в виду всего лишь атомарные чтение и запись, и что это не очевидная возможность, а тоже то, о чём надо явно подумать (например, если tid 64-битный, а место в памяти для него не выровнено на 8 байт, то чтение и запись могут идти в 2 раздельных операции шины).

Здравствуйте, netch80, Вы писали:

N>Ты неправильно понял, что я имел в виду. Обвязка вокруг семафора — это уже не сам семафор.

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

N>Но пример полезный, как для данного треда, пойдёт как обучающий. Только тут надо пояснить, что под атомарными операциями имеется в виду всего лишь атомарные чтение и запись, и что это не очевидная возможность, а тоже то, о чём надо явно подумать (например, если tid 64-битный, а место в памяти для него не выровнено на 8 байт, то чтение и запись могут идти в 2 раздельных операции шины).

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

Здравствуйте, Кодт, Вы писали:

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

Если не ошибаюсь в винде все примитивы — надстройка над евентами

Здравствуйте, carpenter, Вы писали:

К>>Мьютекс и CV тоже образуют базис. С их помощью можно реализовать, в том числе, и семафоры, и очереди сообщений, и прочая, и прочая.
C>Если не ошибаюсь в винде все примитивы — надстройка над евентами

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

Здравствуйте, pkl, Вы писали:

pkl>1. На каких конкретно машинных командах современных актуальных процессоров (intel core, arm v7, ...) обычно реализована (или может быть реализована) синхронизация? Какая последовательность ассемблерных команд обычно реализует семафор, например? (желателно с комментариями, чтобы было понятно как работает механизм и видно, где там атомарность).

Приведу ссылку по которой можно найти описание инструкций LDREX, STREX и CLREX, там есть пример.