Почему не возможен синхронизованный вывод двух потоков при использовании двух мутексов?

Question

[alienstone]

Здравствуйте,

Возникла задача - синхронизовать вывод родительской и дочерней нитей ( их всего 2) : сначала родительская нить выводит первую строку, затем дочерняя, затем родительская вторую строку и т.д. Использовать можно только мутексы, остальные средства синхронизации запрещены. Сходу не могу доказать, почему это невозможно. Подскажите, пожалуйста.

Исходный текст задачи:

Напишите программу, которая создает нить. Используйте атрибуты по умолчанию. Родительская и вновь созданная нити должны распечатать десять строк текста. Модифицируйте программу так, чтобы вывод родительской и дочерней нитей был синхронизован: сначала родительская нить выводила первую строку, затем дочерняя, затем родительская вторую строку и т.д. Используйте мутексы.

Явные и неявные передачи управления между нитями (sleep(3C)/usleep(3C), sched_yield(3RT)) и холостые циклы разрешается использовать только на этапе инициализации.

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

Заранее благодарен.

Comments

[Олег Цилюрик]

А кто это сказал, что это невозможно?

[alienstone]

Олег Цилюрик: преподаватель по курсу ОС.

[Олег Цилюрик]

alienstone:
А кто вам сказал, что преподаватель понимает ... курс?

[Eddy_Em]

Олег Цилюрик: преподаватель явно не понимает курс, т.к. я привел рабочее решение на двух мьютексах без использования каких-либо средств синхронизации (глобальная переменная используется лишь чтобы после 10 строчек все закончить, а не жать ctrl+c)

Answer 1

[xmoonlight]

https://ru.wikipedia.org/wiki/%D0%9C%D1%8C%D1%8E%D...
В каждый конкретный момент только один поток может владеть объектом, защищённым мьютексом

Comments

[alienstone]

Ну это-то из определения мьютекса исходит.
К сожалению, немного не догоняю, как это строго доказывает проблему. Не могли бы вы чуточку подробнее объяснить?

[xmoonlight]

alienstone: Могу, если зададите вопрос конкретнее, т.к. развёрнутый ответ на текущий - есть в википедии и достаточно хорошо там изложен.

[alienstone]

xmoonlight: ну вот например, мы можем пытаться реализовать множество разных вариантов. Например, создадим класс для каждого треда, в котором будет указатель на мьютекс текущего потока, и на мьютекс другого потока. Ну и в цикле проверять, если текущий свободен, то выводим пронумерованную строку на экран, потом освобождаем мьютексы. И какой-то мьютекс в самом начале захватить, до цикла. Но это не работает, может возникнуть race condition. Вот, очень схематично:

pthread_mutex_t parentMutex;
pthread_mutex_t childMutex;

class Params {
string name;
current_mutex;
other_mutex;
}
void* foo ( Params params ){
for ( int i = 0; i < 10; ++ i){
params.current_mutex.lock;

cout << string << i;

params.current_mutex.unlock;
params.other_mutex.unlock;
}
}

Я вижу, что это не возможно, но в голове мысль проскакивает, вдруг существует какая-нибудь другая реализация, при которой можно исхитриться так сделать. И не могу догнать, как строго доказать в принципе невозможность. Перебором всех вариантов? Но их же там огромное количество

[xmoonlight]

alienstone: можно создать дополнительно мьютекс управления синхронизацией в доп. потоке - master, а эти - будут slave. Он может избавить от race condition, расставляя приоритеты. А в slave-ах - проверять разрешение master-a.

[Олег Цилюрик]

alienstone:

в котором будет указатель на мьютекс текущего потока, и на мьютекс другого потока.

Какой ужас! ;-)

Answer 2

[Mercury13]

А точно нельзя?
Я бы сделал так…

Поток 1.

мютекс2.войди
поток2.старт
повторяй 10 раз
  мютекс1.войди
  writeln
  мютекс2.выйди
поток2.дождись
мютекс2.выйди

Поток 2.

повторяй 10 раз
  мютекс2.войди
  writeln
  мютекс1.выйди

Обратите внимание, мы входим в один мютекс и выходим из другого. Проверю, отпишусь.

Единственное спорное «средство синхронизации» — в потоке 1 дождаться завершения потока 2.

Comments

[MiiNiPaa]

Должно работать и работает:
coliru.stacked-crooked.com/a/95e9caa32b6d2770
ideone.com/CDtScq

> Единственное спорное «средство синхронизации» — в потоке 1 дождаться завершения потока 2.
Технически его можно ожидать и в main(), на пару со вторым. Тогда придётся создавать в мэйне пустой поток, передавать ссылку на него в поток1 и присваивать ему новый поток.

[MiiNiPaa]

Как-то так: coliru.stacked-crooked.com/a/931416c55281e8d3

[Mercury13]

MiiNiPaa: Ну да, перевёл на нормальный язык программирования, и оно заработало.

Answer 3

[Eddy_Em]

Что за чушь? Для этого мьютексы и придумали. Блокируем мьютекс родителем, выводим строчку, устанавливаем некий глобальный ключ в 1, сбрасываем мьютекс, ждем, пока ключ не будет 0. В дочернем же ждем, пока ключ не будет 1, блокируем мьютекс, выводим строчку, сбрасываем ключ, разблокируем мьютекс.
Если используются не потоки (pthreads), а процессы (fork), то нужно убрать буферизацию или после каждой записи сбрасывать буферы.

См. мой ответ с двумя мьютексами в комментарии к этому ответу.

Comments

[alienstone]

Я бы и сам так сделал, а не писал тут вопрос, но, к моему глубокому сожалению, "остальные средства синхронизации запрещены".

[Олег Цилюрик]

alienstone:
А по-моему, вы просто слышали звон, но не разобрались откуда он... - не поняли о какой формулировке задачи шла речь.
Нормально сформулируйте задачу: кто и что выводит, и что такое "поочерёдно"?

[Олег Цилюрик]

alienstone:

остальные средства синхронизации запрещены

Какие такие "остальные средства синхронизации" упоминаются в данном выше ответе?

[alienstone]

Олег Цилюрик:
Прошу прощения, вот исходный текст задачи:
Напишите программу, которая создает нить. Используйте атрибуты по умолчанию. Родительская и вновь созданная нити должны распечатать десять строк текста. Модифицируйте программу так, чтобы вывод родительской и дочерней нитей был синхронизован: сначала родительская нить выводила первую строку, затем дочерняя, затем родительская вторую строку и т.д. Используйте мутексы.

Явные и неявные передачи управления между нитями (sleep(3C)/usleep(3C), sched_yield(3RT)) и холостые циклы разрешается использовать только на этапе инициализации.

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

[alienstone]

Олег Цилюрик: на сколько я знаю, глобальная переменная-флаг является средством синхронизации

[Олег Цилюрик]

alienstone:

на сколько я знаю,

Значит плохо знаете.
Простая переменная (не атомарная) никогда и никем не считалась средством синхронизации.
Примитивы синхронизации - это строго определённый ограниченный набор объектов кода ... а не то, что вы о них думаете.

[Олег Цилюрик]

alienstone:

глобальная переменная-флаг является средством синхронизации

Возьмите вот эту книгу (я другой более обстоятельной в природе не знаю):

И покажите на более пол-тыщи страниц место, где бы любая (глобальная, локальная, ... золотая) простая переменная называлась бы средством синхронизации?
Средством взаимодействия - да, синхронизации - никогда.

[Eddy_Em]

alienstone: Интересно, кто такую тупую формулировку задачи придумал?
Эта задача элементарно решается при помощи ОДНОГО мьютекса и ОДНОЙ глобальной переменной, либо же при помощи ДВУХ мьютексов.
Итак, как решить ее двумя мьютексами: пусть будут мьютексы writer и queue. Родитель пишет в поток лишь в случае, когда оба мьютекса разблокированы. Перед записью родитель блокирует writer, пишет, затем блокирует queue и разблокирует writer. Далее родитель опять ждет, пока будут разблокированы оба мьютекса.
"Сын" ждет, пока будет разблокирован writer и заблокирован queue (ясен пень, здесь нужны неблокирующие вызовы trylock на мьютекс writer с дальнейшим trylock на queue). Если все ОК, то он пишет в мьютекс, разблокирует queue и разблокирует writer.
Но это очень черезжопное решение, проще через глобальный флаг или хотя бы через условные переменные pthread_cond_t.

[Eddy_Em]

Вот решение на двух мьютексах:

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

pthread_mutex_t writer = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t queue  = PTHREAD_MUTEX_INITIALIZER;

int global_ctr = 0;

static void *child(void *arg){
	while(global_ctr < 10){
		if(!pthread_mutex_trylock(&writer)){
			if(pthread_mutex_trylock(&queue)){
				printf("Child wrote this string\n");
				++global_ctr;
			}
			pthread_mutex_unlock(&queue);
			pthread_mutex_unlock(&writer);
		}
	}
	return NULL;
}

int main(){
	pthread_t thread;
	pthread_create(&thread, NULL, child, NULL);
	while(global_ctr < 10){
		if(!pthread_mutex_trylock(&writer)){
			if(!pthread_mutex_trylock(&queue)){
				printf("Parent wrote this string\n");
				++global_ctr;
			}
			pthread_mutex_unlock(&writer);
		}
	}
	return 0;
}

Проверяем:

gcc 1.c -lpthread && ./a.out 
Parent wrote this string
Child wrote this string
Parent wrote this string
Child wrote this string
Parent wrote this string
Child wrote this string
Parent wrote this string
Child wrote this string
Parent wrote this string
Child wrote this string
Parent wrote this string

Все, довольны?

[Олег Цилюрик]

Японский Городовой:

Все, довольны?

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

холостые циклы разрешается использовать только на этапе инициализации.

Т.е. его преподаватель хотел бы видеть это без активных циклов ожидания (у них это называется "холостые циклы"), без pthread_mutex_trylock(), только с чередованием блокированных состояний.

[Eddy_Em]

Олег Цилюрик: В задаче нужно что-то передавать. Без циклов это сделать невозможно. Нужен цикл по количеству сообщений, иначе смысл?

[Eddy_Em]

Олег Цилюрик: P.S. А "холостые циклы" это вообще-то что-то вроде for(x = 0; x < xmax; ++x) nop(), используемые иногда для реализации небольшой задержки в мелкоконтроллерах.

[Олег Цилюрик]

Японский Городовой:
Они называют холостыми циклы вида:

while(global_ctr < 10){
    if(!pthread_mutex_trylock(&writer)){
    }
}

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

[Олег Цилюрик]

Японский Городовой:

В задаче нужно что-то передавать. Без циклов это сделать невозможно.

Переделал а). по мотивам того, что писал MiiNiPaa, б). специально на C, т.к. thread C++ - это только обёртка к POSIX pthread_t и маскирует детали.

#include <pthread.h>
#include <iostream>
using namespace std;

pthread_mutex_t mux1 = PTHREAD_MUTEX_INITIALIZER,
                mux2 = PTHREAD_MUTEX_INITIALIZER;

void* tfunc ( void* parm ) {
   int rep = (int)parm;
   for( int i = 0; i < rep; i++ ) {
      pthread_mutex_lock( &mux2 );
      cout << "child: строка №" << i + 1 << endl;
      pthread_mutex_unlock( &mux1 );
   }
   return NULL;
};

int main( int argc, char *argv[] ) {
   pthread_mutex_lock( &mux2 );
   pthread_t tid;
   const int rep = 5;
   pthread_create( &tid, NULL, tfunc, (void*)rep );
   for( int i = 0; i < rep; i++ ) {
      pthread_mutex_lock( &mux1 );
      cout << "parent: строка №" << i + 1 << endl;
      pthread_mutex_unlock( &mux2 );
   }
   pthread_join( tid, NULL );
};

Здесь нет цикла активного ожидания мютекса, только чередование блокированных состояний.
Что опровергает первоначальную аксиому темы ;-)

$ ./2thr 
parent: строка №1
child: строка №1
parent: строка №2
child: строка №2
parent: строка №3
child: строка №3
parent: строка №4
child: строка №4
parent: строка №5
child: строка №5

[Олег Цилюрик]

только чередование блокированных состояний.

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

[Олег Цилюрик]

Ринат Велиахмедов:
Идёте и смотрите код реализации.

[Олег Цилюрик]

Ринат Велиахмедов:

однако в С++ данный код был бы не корректен

using namespace std;

mutex mux1, mux2;

void tfunc( int rep ) {
   for( int i = 0; i < rep; i++ ) {
      mux2.lock();
      cout << "child: строка №" << i + 1 << endl;
      mux1.unlock();
   }
};

int main( int argc, char *argv[] ) {
   mux2.lock();
   const int rep = 5;
   thread thr( tfunc, rep );
   for( int i = 0; i < rep; i++ ) {
      mux1.lock();
      cout << "parent: строка №" << i + 1 << endl;
      mux2.unlock();
   }
   thr.join();
};

Ну и кто там кого ... "не гарантирует"?

[Eddy_Em]

Ринат Велиахмедов: отвечу за него: если вдруг появится такой баг, софт будет пропатчен, чтобы и с багом в компиляторе работал правильно.

[Олег Цилюрик]

Ринат Велиахмедов:

Откуда вы можете быть уверены, что под всеми нужными вам системами потоки будут реализованы только так

- все мне нужные системы - POSIX ... всё что происходит в виндусях - меня не занимает
- библиотеки C++ - это только надстройка над стандартной библиотекой C libc.so - без этой библиотеки C++ просто не станут работать
- все API с потоками - это системные вызовы, к ядру ... они идут исключительно через интерфейс библиотеки libc.so, другого пути нет
- наконец, модель thread поздних стандартов C++ - это не C++, это полностью перенесенная реализация Boost (сравните) ... а в Boost в описаниях и в объяснениях в разных местах идёт отсылка "как это делается в POSIX".

[Олег Цилюрик]

Ринат Велиахмедов:

под Windows ваш код вызывает сбой программы из-за одновременной попытки писать в консоль из двух потоков.

Если вызывает - вы покажите как (цитированием и т.п.) ... и попробуйте объяснить почему.
А то всё слова, слова, слова...

[Eddy_Em]

Ринат Велиахмедов: > То, что вы пользуетесь только Linux (что тоже может измениться со временем)
Ну, когда наступит линуксокапец, придется, наверное, на BSD пересесть, но там тоже POSIX.

[Eddy_Em]

Ринат Велиахмедов: > Этот код не соответствует стандарту языка
Я без понятия, что там в стандартах це++, я это не использую. Только С.

[Eddy_Em]

Ринат Велиахмедов: ну, звиняйте. Что вопрос именно по с++ я не заметил. Тогда и ответ мой здесь совершенно не к месту.

[Олег Цилюрик]

Ринат Велиахмедов:

примите во внимание, что на pthread этот код тоже не корректен (почему - я писал в ответе к Олегу).

По стандарту POSIX 1 - корректен, по уточняющему стандарту POSIX 1003b - не корректен, по реализации в Linux - корректен.
И вам ещё раньше, после кода, написал почему:
- потому что в Linux мютекс реализован как бинарный семафор;
- поменяйте в примере кода мютекст на бинарный семафор - и он вас перестанет беспокоить ;-)

[Eddy_Em]

Ринат Велиахмедов: мне плевать. В линуксе работает - и хорошо! А под мастдайку я ничего писать не собираюсь, я еще не съехал с катушек, чтобы добровольно BDSM заниматься!

[Олег Цилюрик]

Ринат Велиахмедов:

вместо следования стандарту.

Какому стандарту? Какому из? ... я вам написал стандарты, они, вообще то, противоречат друг другу.
(или для вас стандарт: "MSDN наше фсё!" ?)

ваш код может быть выполнен неправильно, если после первой итерации в главном потоке итерация во втором выполнится дважды (строка из второго потока будет выведена 2 раза).

Не может.

[Eddy_Em]

Ринат Велиахмедов: > И если внезапно выпустят новую версию реализации мьютексов в ядре линуска, ваш код не будет под ним работать
В этом случае это уже будет не линуксом, а я переползу на BSD!
И еще: данный код приведен как пример того, что "профессор — лопух". Это не значит, что код реально будет использоваться. Я несколько иначе обычно синхронизации делаю и не имею привычки блокировать мьютекс в одном потоке, а разблокировать в другом. Для этого есть глобальные флаги.

[Олег Цилюрик]

Ринат Велиахмедов:

Впрочем, я не читал стандарта POSIX и не могу утверждать, что он везде корректен, однако мне слабо верится, что там есть прямо противоположные утверждения.

Разные редакции стандарта, разных лет и т.д.
Но ход сильный: "Я не читал Пастернака, но я скажу..." ;-)

[Олег Цилюрик]

Ринат Велиахмедов:

2)

Я показываю вам работающий код, результат выполнений... Вы утверждаете: "там может быть бяка" - так вам и доказывать и показывать ... а не наоборот: презумпция невиновности ;-)

[Олег Цилюрик]

Ринат Велиахмедов:

Я написал "то стандарту POSIX, которому следует версия целевой ОС".

А какому же стандарту следует целевая ОС? ;-)

Как говорил товарищ генерал:

Ну, вы, блин, даёте.

Answer 4

[Олег Цилюрик]

Если вас смущает простая переменная (флаг) в ответе Японский Городовой ("Что за чушь?..." - что совершенно справедливо ;-) ), то я вам набросаю другую схему - каждый из потоков выполняет что-то подобное:

while( true ) {
   while( pthread_mutex_trylock( &mutex ) == EBUSY );
   cout << "это мя строка, ура!" << endl;
   pthread_mutex_unlock( &mutex ); 
}

Здесь то и переменных никаких нет кроме мютекса ... - компилируйте, выполняйте, насаждайтесь ;-)

Comments

[MiiNiPaa]

Не гарантировано чередование. Один поток может захватить мутекс два раза подряд. Можно тупо вставить 100мс ожидания после освобождения мутекса, тогда будет работать как надо в 99.99% случаев.

[Mercury13]

while( pthread_mutex_trylock( &mutex ) == EBUSY );
Холостой цикл

[Олег Цилюрик]

Mercury13:
Что значит "холостой цикл"? - здесь цикл ожидания.

[Mercury13]

Я не знаю, как действует функция pthread_mutex_trylock (описание крайне скудное). Но если, когда мютекс занят, выходим из неё мгновенно, это непроизводительный расход ресурсов процессора.

[Mercury13]

Олег Цилюрик: Многопоточники, когда не знают, как действовать, налаживают подобные циклы с задержкой «на разумное время». Но это всё хак, ибо привязывается к конкретной производительности компьютера.

[Mercury13]

Олег Цилюрик: И да, я знаю, что функция захвата мютекса внутри именно что привязывается к производительности процессора, прокручивая подобный холостой цикл с некоторым, рассчитанным статистикой, количеством итераций, а потом — отдаёт процессор другой задаче. Но сделано это только для повышения производительности в многопроцессорных системах (однопроцессорные ядра циклов не гоняют). Ну и пусть это будет системной функцией, а не прикладной программой.

[Олег Цилюрик]

Mercury13:

Я не знаю, как действует функция pthread_mutex_trylock (описание крайне скудное).

POSIX

[Mercury13]

Олег Цилюрик: Я имею в виду вот что: сколько она, по стандарту, должна ждать, пока не скажет: мютекс занят, не пытайся? И чем является это ожидание: пустым циклом, уступанием процессорного времени или чем-то ещё?

[Олег Цилюрик]

Mercury13:
1. это стандарт, POSIX, там всё однозначно регламентировано ... там нечего гадать
2. pthread_mutex_trylock() не ожидает нисколько в обоих случаях: в случае успеха тут-же захватывает мютекс, в случае невозможности тут же возвращает EBUSY

[Mercury13]

Если нисколько — то такой код не слишком кузяв, ибо, скорее всего, pthread_mutex_lock() написано оптимальнее.

[Олег Цилюрик]

Mercury13:
Да не может быть тёплое "оптимальнее" кислого - это радикально разные вещи.
И давайте не обсуждать хорошо или плохо оно в стандарте POSIX сделано, потому что он общепризнан, а нас по квалификации его формализовать не призывали ;-)