Re[11]: внутренняя реализация std::mutex?
От: reversecode google
Дата: 17.05.18 08:29
Оценка: +1
B>возникла идея безумная. вот смотрите, ведь все равно- потоки используют общую память. т.е им не нужен "защищенный режим" изоляции друг от друга
B>можно ли на уровне ОС сделать "user mode" потоки?
B>например юзермодовское прерывание таймера, которое не меняет контекст (user to kernel)?
B>т.о. потоки в рамках одного процесса могут быстро останавливаться — юзермод таймер прерыванием — быстро переключать стек регистров — и продолжать управление.
B>т.е если общий квант времени, отведенного на процесс не истек — то получим сверхшустрые потоки в рамках этого кванта

это все от того что вы не хотите почитать все что уже придумано до вас фибры в винде https://msdn.microsoft.com/en-us/library/windows/desktop/ms682661(v=vs.85).aspx
curoutines в обеих ОС
ну и http://rsdn.org/forum/cpp/7147121.1
Автор: reversecode
Дата: 17.05.18
Re[11]: внутренняя реализация std::mutex?
От: lpd Черногория  
Дата: 17.05.18 08:30
Оценка: -1
Здравствуйте, barney, Вы писали:

lpd>>Переход в режим ядра и тем более переключение контекста на другой поток — достаточно долгие операции.


B>возникла идея безумная. вот смотрите, ведь все равно- потоки используют общую память. т.е им не нужен "защищенный режим" изоляции друг от друга

B>можно ли на уровне ОС сделать "user mode" потоки?
Раньше лет 15 назад в Linux потоки так и были реализованы без sys_futex(). Детали не знаю, но для переключения исполнения между потоками можно использовать user-level libc-функции setjmp()/longjmp().
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Отредактировано 17.05.2018 8:33 lpd . Предыдущая версия .
Re[12]: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 08:40
Оценка:
R> фибры в винде https://msdn.microsoft.com/en-us/library/windows/desktop/ms682661(v=vs.85).aspx

не совсем то — здесь поток сам планирует фибру, и она явно должна отдать управление назад

R>curoutines в обеих ОС


то же самое, проблема корутин — они явно должны делать yield()

имхо, тут нужно прерывание по таймеру, но не уводящее CPU в kernel mode
Re[12]: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 08:41
Оценка:
lpd>Раньше лет 15 назад в Linux потоки так и были реализованы без sys_futex(). Детали не знаю, но для переключения исполнения между потоками можно использовать user-level libc-функции setjmp()/longjmp().

любопытно! покопаю в эти setjmp()/longjmp()

но, подозреваю, там опять же без прерывания текущего потока исполнения по таймеру
т.е нечто вроде корутин
Re[13]: внутренняя реализация std::mutex?
От: lpd Черногория  
Дата: 17.05.18 08:43
Оценка:
Здравствуйте, barney, Вы писали:

B>но, подозреваю, там опять же без прерывания текущего потока исполнения по таймеру

B>т.е нечто вроде корутин

Нет, там было имнно переключение по таймеру. По-идее, вместо системного прерывания таймера можно просто использовать системные вызовы асинхронных таймеров.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Re[13]: внутренняя реализация std::mutex?
От: reversecode google
Дата: 17.05.18 08:48
Оценка:
B>имхо, тут нужно прерывание по таймеру, но не уводящее CPU в kernel mode

я и не сказал что соцпрограммы работают по таймеру
но примеры которые я +10500 раз привел, все объясняют как это сделано у других и размазано по ядрам цпу
Re: внутренняя реализация std::mutex?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 17.05.18 09:01
Оценка:
Здравствуйте, barney, Вы писали:

B>но это приводит не просто к простою потока, а постоянной нагрузке


Есть два принципиально разных случая
1) ожидая освобождения, можно стать в очередь и ждать, пока кто-то не разбудит
2) будить некому, нет варианта, кроме как крутиться в цикле

Второй — это или межпроцессорные спинлоки за общий ресурс, или синхронизация между тредами/процессами/etc. при отсутствии толкового диспетчера.
Вариант "вместо кручения в цикле ждём на mwait" принципиально сути не меняет.

В первом, если не удалось захватить атомарным test-and-set или его аналогом (LL/SC на RISC), ставятся в очередь к диспетчеру, и тут коллеги уже расписали происходящее чуть более, чем во всех деталях.
The God is real, unless declared integer.
Re[3]: внутренняя реализация std::mutex?
От: smeeld  
Дата: 17.05.18 09:01
Оценка:
Здравствуйте, barney, Вы писали:


B>А POSIX функция pthread_mutex_lock уже, я так понимаю, использует некие функции ядра?

B>в LINUX это futex
B>асли это DARWIN/MACH то есть некие ядерные mach_ функции для блокировки/просыпания потоков, которые завязаны на мьютекс

POSIX API реализован как часть системной Cи либы. Функции этой либы, в свою очередь, опираются на функционал, предоставляемый ядром через сисколы. Это сисколы, в конечном итоге, дёргаются системными либами во в сех ОСях, и в DARWIN/MATCH. Сисколы базируются в предоставлении функционала на подсистемах ядра. Так, сискол вроде futex, уходит корнями в подсистему управления тредами в ядре. Чтоб узнать как реализовано оно всё в ядре-читайте исходники.
Re[2]: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 09:22
Оценка:
N>В первом, если не удалось захватить атомарным test-and-set или его аналогом (LL/SC на RISC), ставятся в очередь к диспетчеру, и тут коллеги уже расписали происходящее чуть более, чем во всех деталях.

Т.е без вызова диспатчера (и соотв. ухода в kernel mode сисколом) отключить поток от исполнения — нет способов?
Re[3]: внутренняя реализация std::mutex?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 17.05.18 09:42
Оценка:
Здравствуйте, barney, Вы писали:

N>>В первом, если не удалось захватить атомарным test-and-set или его аналогом (LL/SC на RISC), ставятся в очередь к диспетчеру, и тут коллеги уже расписали происходящее чуть более, чем во всех деталях.


B>Т.е без вызова диспатчера (и соотв. ухода в kernel mode сисколом) отключить поток от исполнения — нет способов?


Не-а
The God is real, unless declared integer.
Re: внутренняя реализация std::mutex?
От: AlexGin Беларусь  
Дата: 17.05.18 09:46
Оценка:
Здравствуйте, barney, Вы писали:

B>Интересно, как реализованы базовые примитивы мультипоточности в C++? Такие как mutex


B>насколько я понимаю, все базируется на атомарной test-and-set инструкции (которую я бы назвал fetch-and-set)

B>и spin_lock блокировке, которая выглядит примерно так:

B>

B>spin_outer:
B> cmp flag, 1
B> je spin_outer // waiting until 0

B>spin_inner:
B> test-and-set ax, flag //executed atomicly
B> // {
B> // mov ax, flag // fetch current value to ax
B> // mov flag, 1 // set flag to 1
B> // }

B> cmp ax, 1
B> jne spin_inner // if old value was 0

B> // now in critical section

B> call do_work

B> mov flag, 0 // clean flag
B>leave:


Примерно так.
Вот подобное в C/C++ синтаксисе:
http://anki3d.org/spinlock
вот подобное при использовании boost:
https://www.boost.org/doc/libs/1_61_0/doc/html/atomic/usage_examples.html#boost_atomic.usage_examples.example_spinlock

B>но это приводит не просто к простою потока, а постоянной нагрузке

+100500
Да, но предполагается, что проектировщик/разработчик это понимает и не будет сильно злоупотеблять этим.
То есть — между входом (s.lock()) и выходом (s.unlock()) — делаем что-то весьма короткое с общим (совместным) ресурсом,
чтобы избежать взаимной блокировки.

spinlock s;

s.lock();
// здесь делаем что-то элементарное!
s.unlock();


B>при использовании std::mutex для критической секции такого не наблюдается.


По критическим секциям — вот интересная статья (от нашего коллеги Павла Блудова):
http://rsdn.org/article/baseserv/critsec.xml
Автор(ы): Павел Блудов
Дата: 14.03.2005
В статье рассматриваются аспекты работы с критическими секциями, их внутреннее устройство и способы отладки

В конце — важные выводы:
— Код, ограниченный критическими секциями, лучше всего свести к минимуму.
— Находясь в критической секции, не стоит вызывать методы "чужих" объектов.


B>как же работает мютекс?


В отличие от критической секции, мьютекс — объект системного ядра (в том же Windows API).
Предположу, что там "ожидание" это не простой цикл в условным/переходом на метку, я передача управления стстемному диспетчеру потоков.
В этом случае, задача STL (std::mutex) будет сведена просто к вызову соответствующих системных методов WinAPI или Posix.
Отредактировано 17.05.2018 9:56 AlexGin . Предыдущая версия . Еще …
Отредактировано 17.05.2018 9:51 AlexGin . Предыдущая версия .
Re: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 09:47
Оценка:
вот, сделал, учебную реализацию спин-блокировки через test-and-set для x64
На мак оси работает с ошибками,
в общем виде вывод смешан (как и должно быть, тк main thread не блочится)
но даже между обоими spinner почему то такая блокировка не работает:
"INSIDE THE LOCK" выводится не всегда неразрывно со spin_count
хотя здесь должна быть жесткая гарантия

#include <iostream>
#include <thread>

int mutex = 0;

inline void Lock(int * flag) {
    
    int spins_count = 0;
    
    __asm {
    outer:
        mov rbx,flag
        mov eax,[rbx]
        cmp eax,0
        jne outer
        
        xor ecx,ecx
        xor eax, eax
        mov rbx,flag
    loop:
        inc ecx
        lock bts [rbx], eax   // lock + bts atomic test-and-set
        jnc loop
        mov spins_count,ecx
    }
    // locked
    std::cout << "\nINSIDE_THE_LOCK:" << spins_count << "\n";
    __asm {
        mov rbx,flag
        xor eax,eax
        mov [rbx],eax
    }
}

void spinner(char * id) {
    
    while (true) {
        Lock(&mutex);
        // not locked
        std::cout << "·" << "SPINNER:" << id << "·";
    }
}

int main() {
    char * Q = "Q";
    char * W = "W";
    
    std::thread t1(spinner, Q);
    std::thread t2(spinner, W);
    
    while (true) {
        // not locked
        std::cout << "•";
    }
}


Вывод вот такой:
  вывод
•
INSIDE_THE_LOCK:••2•
•
INSIDE_THE_LOCK:·•2SPINNER:•
Q•··•SPINNER:
INSIDE_THE_LOCK:•W2•·
•
INSIDE_THE_LOCK:·•2SPINNER:•
Q•··•SPINNER:
INSIDE_THE_LOCK:•W2•·
•·
INSIDE_THE_LOCK:•SPINNER:2•
Q•··•SPINNER:
INSIDE_THE_LOCK:•W2•·
•·
INSIDE_THE_LOCK:•SPINNER:2•Q
•··•
INSIDE_THE_LOCK:SPINNER:•2W•
·•·
INSIDE_THE_LOCK:•SPINNER:2•Q
•··•
INSIDE_THE_LOCK:SPINNER:•2W•


Вот "INSIDE_THE_LOCK:SPINNER:•2W•"
здесь должно быть "INSIDE_THE_LOCK:2" или "INSIDE_THE_LOCK: ••2" но SPINNER должен был вывестись ПОСЛЕ
Re[2]: внутренняя реализация std::mutex?
От: andrey.desman  
Дата: 17.05.18 09:52
Оценка: +3
Здравствуйте, Videoman, Вы писали:

V>Под Windows, например (VS2013), std::mutex реализован без использования вызовов WinAPI, почти так, как вы и описали, но spin блокировка крутится заданное число циклов (сейчас 4000) и уже по истечении этого времени квант потока отдается (он засыпает на pause). Фактически в С++ рантайм вынесены "кишки" стандартной critical section.



Серьезно? А как же очередь ожидающих и приоритизация? То есть, какой-то один поток может бесконечно долго висеть и не захватить мьютекс?
Re[2]: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 09:53
Оценка:
Спасибо за ссылочки, любопытно

AG>В конце — важные выводы:

AG>
AG>- Код, ограниченный критическими секциями, лучше всего свести к минимуму.
AG>- Находясь в критической секции, не стоит вызывать методы "чужих" объектов.


Воот...
Вообще бы, хотелось программировать в какой то иной парадигме,
без критических секций и мьютексов.
Мне нравится идея максимально заполнять ядра процессора работой,
с помощью work queue или thread pool
Увы, они реализованы внутри тоже с применением cond_variable и эти потоки "засыпают" через вызов функций ядра.
Т.к кусочки работы могут быть вполне небольшими — например обновить значение текстовой строки в UI по возвращению данных из сети и тд.
Впрочем, если бы можно было переключать потоки из user mode легковесным образом, (тут уже обсуждали выше user mode таймер)
была бы чистая шустрая и элегантная система воркеров!
Re[2]: внутренняя реализация std::mutex?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 17.05.18 09:55
Оценка:
Здравствуйте, barney, Вы писали:

B>вот, сделал, учебную реализацию спин-блокировки через test-and-set для x64


1. Что за компилятор?

2. Явная ошибка:

B> __asm {

B> outer:
B> mov rbx,flag
B> mov eax,[rbx]
B> cmp eax,0
B> jne outer

B> xor ecx,ecx

B> xor eax, eax
B> mov rbx,flag
B> loop:
B> inc ecx
B> lock bts [rbx], eax // lock + bts atomic test-and-set
B> jnc loop

CF=0 как раз если было 0, то есть спинлок захвачен. Нафига в этом случае возвращаться на loop? Ты делаешь всё наоборот — если захватил, идёшь на круг
Тут лучше ложится jc outer (и вообще, outer и loop совместить)

B> mov spins_count,ecx

B> }
B> // locked
B> std::cout << "\nINSIDE_THE_LOCK:" << spins_count << "\n";
B> __asm {
B> mov rbx,flag
B> xor eax,eax
B> mov [rbx],eax

Вот уж где ассемблер нафиг не нужен, достаточно простого присвоения... хотя, если компилятор системы MSVC или близкий, лучше так.
The God is real, unless declared integer.
Re[2]: внутренняя реализация std::mutex?
От: reversecode google
Дата: 17.05.18 09:57
Оценка: +2 -1
Здравствуйте, barney, Вы писали:

B>вот, сделал, учебную реализацию спин-блокировки через test-and-set для x64


атомики в С++ уже давно ввели
вы с какого года к нам с асмом пришли ? переставте число обратно на 2003 на своей машине времени
Re[3]: внутренняя реализация std::mutex?
От: netch80 Украина http://netch80.dreamwidth.org/
Дата: 17.05.18 09:59
Оценка:
Здравствуйте, barney, Вы писали:

B>Мне нравится идея максимально заполнять ядра процессора работой,

B>с помощью work queue или thread pool
B>Увы, они реализованы внутри тоже с применением cond_variable и эти потоки "засыпают" через вызов функций ядра.

Только когда нет работы. Когда она есть — им незачем спать.
Короткий момент в mutex_lock, когда другие воркеры разбираются с задачами и их отсутствием, не считаем.

B>Т.к кусочки работы могут быть вполне небольшими — например обновить значение текстовой строки в UI по возвращению данных из сети и тд.

B>Впрочем, если бы можно было переключать потоки из user mode легковесным образом, (тут уже обсуждали выше user mode таймер)
B>была бы чистая шустрая и элегантная система воркеров!

Это всё зависит от легковесности самих тредов.
The God is real, unless declared integer.
Re[2]: внутренняя реализация std::mutex?
От: lpd Черногория  
Дата: 17.05.18 10:02
Оценка:
Здравствуйте, barney, Вы писали:

B>Вот "INSIDE_THE_LOCK:SPINNER:•2W•"

B>здесь должно быть "INSIDE_THE_LOCK:2" или "INSIDE_THE_LOCK: ••2" но SPINNER должен был вывестись ПОСЛЕ

Лучше пиши в std::cerr, т.к. std::cout вообще буферизуется, хотя отладить так все равно нельзя.

Для отладки spinlock можно сделать глобальную переменную int counter, и инкрементировать ее заданное число раз из разных потоков.
Без синхронизации или с неправильным мьютексом значение counter в конце почти всегда будет меньше, чем должно.
У сложных вещей обычно есть и хорошие, и плохие аспекты.
Берегите Родину, мать вашу. (ДДТ)
Отредактировано 17.05.2018 10:03 lpd . Предыдущая версия .
Re[3]: внутренняя реализация std::mutex?
От: barney  
Дата: 17.05.18 10:06
Оценка:
Здравствуйте, netch80, Вы писали:

N>1. Что за компилятор?


Apple LLVM version 9.1.0

N>2. Явная ошибка:


B>> __asm {

B>> outer:
B>> mov rbx,flag
B>> mov eax,[rbx]
B>> cmp eax,0
B>> jne outer

B>> xor ecx,ecx

B>> xor eax, eax
B>> mov rbx,flag
B>> loop:
B>> inc ecx
B>> lock bts [rbx], eax // lock + bts atomic test-and-set
B>> jnc loop

N>CF=0 как раз если было 0, то есть спинлок захвачен. Нафига в этом случае возвращаться на loop? Ты делаешь всё наоборот — если захватил, идёшь на круг

N>Тут лучше ложится jc outer (и вообще, outer и loop совместить)

ммм... моя логика такая:
если мьютекс еще не захвачен ( == 0) то вызов 'bts [rbx], eax' в керри положит старое значени 0, и атомарно в память 1
(но, до этого момента, другой поток УЖЕ мог прочитать 0 в таком же outer цикле, и перейти на inner этап)
теперь проц дает гарантию что lock bts атомарно положит там 1 хотя бы в одном из потоков!
т.е у кого то carry будет == 0 а у кого == 1
вот у того, кого 0 — тот захватил первым
Re[3]: внутренняя реализация std::mutex?
От: AlexGin Беларусь  
Дата: 17.05.18 10:16
Оценка:
Здравствуйте, barney, Вы писали:

B>Вообще бы, хотелось программировать в какой то иной парадигме,

B>без критических секций и мьютексов.

Всё зависит от задач.
Я обычно мьютексы не использую, так как это "тяжёлые" системные объекты.
Насчет критических секций — не вижу ничего предосудительного в их применении.
Часто я аккуратно пользуюсь ими. Здесь важно — НЕ вводить в облась, защищенную секцией много кода:
::EnterCriticalSection(m_pCS);
// Самые элементарные действия с общими ресурсами
::LeaveCriticalSection(m_pCS);


B>Мне нравится идея максимально заполнять ядра процессора работой,

B>с помощью work queue или thread pool
Как я понимаю, это примерно так:
https://stackoverflow.com/questions/3458397/boostthread-and-creating-a-pool-of-them

Заполнять ядра CPU работой — это палка о двух концах:
При работе таких приложений, компьютер очень медленно реагирует на действия пользователя.
Правильнее — где-то в циклах рабочих потоков вводить ::Sleep(100...500);
— чтобы отдать управление системе (исключить жуткие тормоза для end-user-а).
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.