Кому написать и для чего?
N>синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
volatile не дает никаких гарантий атомарности. Тем более без указания платформы/компилятора.
Так что постановка вопроса некорректна.
Здравствуйте, nikholas, Вы писали:
N>Написать синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
Термин volatile в данном контексте спорный, но пусть. Обратимся к сути.
1. Сделаем очередь сообщений (на списке или кольцевом буфере) ровно для двух потоков ровно в одном направлении.
Она не нуждается в атомарных read-modify-write, — потому что один поток всегда будет переписывать только счётчик/указатель головы, а второй — только счётчик/указатель хвоста.
Напишем функции try_push и try_pull, — не ожидающие, а просто проверяющие: нет места/данных — ничего не делаем, есть — пишем/читаем.
На основе их напишем push и pull, ожидающие в цикле. (Просто while(!try_push(value))sleep())
2. Сделаем очередь много-к-одному.
Для этого запустим поток-помощник, который в цикле опрашивает (try_pull) очереди источников, и когда вычерпывает данное, — с ожиданием запихивает его в очередь приёмника.
3. Сделаем очередь один-ко-многим.
Для этого создадим встречную очередь много-к-одному.
Каждый приёмник отправляет свой идентификатор, затем ждёт, когда в его персональной очереди что-то появится.
Поток-помощник с ожиданием читает номер свободной кассы, затем с ожиданием читает из основной очереди данных, и отправляет это значение в очередь данных соответствующего приёмника.
В принципе, этого уже достаточно.
А на основании очередей сообщений можно построить семафоры, а на основании семафоров — построить всё что угодно, включая очереди сообщений...
Здравствуйте, nikholas, Вы писали:
N>Написать синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
Ещё более простое решение: глобальный мьютекс.
Пусть у нас N рабочих потоков.
Заводим N булевых переменных и одну (N+1)-ричную — номер текущего владельца.
И запускаем поток-помощник, который молотит цикл опроса.
— если номер текущего владельца выставлен — просто ждёт, когда тот сбросится
— ждёт, пока не будет взведён какой-нибудь флажок запроса
— сбрасывает этот флажок и выставляет номер
Рабочий поток
— выставляет свой флажок
— ждёт, пока не будет выставлен свой номер
— совершает работу
— сбрасывает номер
Здравствуйте, nikholas, Вы писали:
N>Написать синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
Делаем корявый test-and-set
struct Request {
int oldvalue, newvalue;
bool done, success;
};
class AtomicVar {
volatile Request* request = nullptr;
int var; // к ней имеет доступ только поток-помощник
thread helper = thread([]() {
while (true) {
Request* r = request;
if (!r) {
sleep();
continue;
}
if (var == r->oldvalue) { var = r->newvalue; r->success = true; } else { r->success = false; }
r->done = true;
// все, кто написал в этот момент, - неудачники. ничего, покрутят цикл.
request = nullptr;
}
});
public:
bool test_and_set(int oldvalue, int newvalue) {
Request req = { oldvalue, newvalue, false, false };
request = &req;
while(!req.done && request == &req) sleep(); // либо нашу заявку выполнили, либо перебили, либо выполнили и затем перебилиreturn req.success;
}
};
Здравствуйте, Кодт, Вы писали:
К>Здравствуйте, nikholas, Вы писали:
N>>Написать синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
К>Ещё более простое решение: глобальный мьютекс.
К>Пусть у нас N рабочих потоков. К>Заводим N булевых переменных и одну (N+1)-ричную — номер текущего владельца. К>И запускаем поток-помощник, который молотит цикл опроса. К>- если номер текущего владельца выставлен — просто ждёт, когда тот сбросится К>- ждёт, пока не будет взведён какой-нибудь флажок запроса К>- сбрасывает этот флажок и выставляет номер К>Рабочий поток К>- выставляет свой флажок К>- ждёт, пока не будет выставлен свой номер К>- совершает работу К>- сбрасывает номер
С потоком-помощником есть более простое решениеЖ две переменных, рабочий поток пишет в первою свой номер и ждет его во второй переменой,
помощник ждет в первой переменной ненулевое знвчение и пишет это значение во вторую.
Намного интереснее придумать решение без потока-помощника, хотя бы для 2 потоков
Здравствуйте, nikholas, Вы писали:
N>Написать синхронизацию между потоками, используя только volatile переменные (у которых атомарны только чтение и запись, но не модификация)
Здравствуйте, nikholas, Вы писали:
N>С потоком-помощником есть более простое решениеЖ две переменных, рабочий поток пишет в первою свой номер и ждет его во второй переменой, N>помощник ждет в первой переменной ненулевое знвчение и пишет это значение во вторую.
Ну и будет замерзание.
Первый рабочий записал свой номер и ждёт.
Второй рабочий перезаписал свой номер и ждёт.
Помощник увидел номер второго рабочего и квитировал.
Второй рабочий увидел свой номер и вошёл в крит.секцию
...
Второй рабочий вышел из крит.секции и?
— обнулил заявку — помощник обнулил квитанцию
— самостоятельно обнулил квитанцию
Первый поток продолжает ждать свою квитанцию...
Как вариант, — во время ожидания поток обновляет заявку. В этом случае мы разве что поймаем голодание.
С вектором заявок можно даже и от голодания избавиться — помощник возьмёт на себя задачу справедливой диспетчеризации (по своему усмотрению).
N>Намного интереснее придумать решение без потока-помощника, хотя бы для 2 потоков
Для двух потоков надо не мьютексы делать, а очереди сообщений.
Перекуём баги на фичи!
