параллельность + синхронизации (примеры)

Вопросы написания собственного программного кода (на любых языках)

Модератор: Olej

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 18 ноя 2015, 02:52

Olej писал(а):
Докажите, что данная задача не может быть решена с использованием двух мутексов
без использования других средств синхронизации.
Я не знаю откуда они такое взяли, вместе со своим университетским преподавателем :-o ...
Но делаем 1-й вариант, решающий такую задачу, на базе базовых 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 );
};
И 2-й вариант, функционально аналогичный, но на базе класса thread C++:

Код: Выделить всё

#include <iostream>
#include <thread>
#include <mutex>     
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();
};
Компиляция без особых изысков:

Код: Выделить всё

bash-4.2$ make
g++ -Wall -lpthread -std=c++11     2thr.cc   -o 2thr
g++ -Wall -lpthread -std=c++11     2thr+.cc   -o 2thr+
Выполнение 1-й вариант:

Код: Выделить всё

bash-4.2$ ./2thr
parent: строка №1
child: строка №1
parent: строка №2
child: строка №2
parent: строка №3
child: строка №3
parent: строка №4
child: строка №4
parent: строка №5
child: строка №5
Выполнение 2-й вариант:

Код: Выделить всё

bash-4.2$ ./2thr+
parent: строка №1
child: строка №1
parent: строка №2
child: строка №2
parent: строка №3
child: строка №3
parent: строка №4
child: строка №4
parent: строка №5
child: строка №5
Так что доказательство невозможности решения не удалась ;-) ... от противного.
Вложения
2thr.cc
(775 байт) 215 скачиваний
2thr+.cc
(531 байт) 188 скачиваний
2thr.tgz
(2.95 КБ) 209 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 18 ноя 2015, 03:02

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

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

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 18 ноя 2015, 03:52

Olej писал(а):Компиляция без особых изысков:
Это без особых изысков, когда это я делал в Fedora 21.
А вот когда Mint 17.1 / Mint 17.2, то подучается вот такая ошибка:

Код: Выделить всё

olej@mint1 ~/2015_WORK/2thr $ make
g++ -Wall -std=gnu++11 -lpthread 2thr.cc -o 2thr
/tmp/ccRkUYt9.o: In function `main':
2thr.cc:(.text+0xb9): undefined reference to `pthread_create'
2thr.cc:(.text+0x132): undefined reference to `pthread_join'
collect2: error: ld returned 1 exit status
make: *** [2thr] Ошибка 1

Код: Выделить всё

olej@mint1 ~/2015_WORK/2thr $ lsb_release -ircd
Distributor ID: LinuxMint
Description:    Linux Mint 17.2 Rafaela
Release:        17.2
Codename:       rafaela
Не находит библиотеки! ... и точно так же - элементарную libm.so

Напоминание!
Убил на это дело ... часа 3 времени: и библиотеки переустанавливал, и ldconfig обновлял...
Но об этом уже писалось: Mint.
Причина объясняется как сборка ld (gcc) с желанием экономить до 5% времени работы :lol: :lol: :lol: - вот здесь подробно. Там подробно описывается когда и почему это возникает...
В любом случае, технически достаточно просто записывать библиотеки в команде gcc позже, чем объектные файлы их использующие.
(такое в нескольких дистрибутивах ... экономные, блин! :twisted: )

Переписываем библиотеки в конец команды (в Makefile):

Код: Выделить всё

olej@mint1 ~/2015_WORK/2thr $ make
g++ -Wall -std=gnu++11  2thr.cc -o 2thr -lpthread
g++ -Wall -std=gnu++11  2thr+.cc -o 2thr+ -lpthread

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 19 мар 2019, 09:29

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

Код: Выделить всё

#include <sys/time.h>
#include <unistd.h>
#include <iostream>
using namespace std;

int rept = 10, msec = 100;
static pthread_spinlock_t loc; 
bool bspin = true;

static void* block_func( void* par ) {  // функция потока
   for( int i = 0; i < rept; i++ ) {
      if( bspin ) pthread_spin_lock( &loc );
      struct timespec pause = {         // интервал пассивной паузы 
         .tv_sec  = msec / 1000,
         .tv_nsec = ( msec % 1000 ) * 1000000L
      };
      nanosleep( &pause, NULL );
      if( bspin ) pthread_spin_unlock( &loc );
   }
   return NULL;
}

int main( int argc, char *argv[] ) {
   char c, sopt[] = "r:t:d:sv";
   int nthr = 5, debug_level = 0;
   while( -1 != ( c = getopt( argc, argv, sopt ) ) )
      switch( c ) {
         case 'r':        // число повторений в потоке
            rept = atoi( optarg );
            break;
         case 't':        // число потоков
            nthr  = atoi( optarg );
            break;
         case 'd':        // пауза в потоке, мсек.
            msec = atoi( optarg );
            break;
         case 's':        // без спин-блокировки
            bspin = false;
            break;
         case 'v':
            debug_level++;
            break;
         default :
            return( EXIT_FAILURE );
      }
   if( debug_level )
      cout << getpid() << ": число потоков = " << nthr << endl;
   pthread_spin_init( &loc, 1 );
   pthread_t *h = new pthread_t[ nthr ];
   struct timeval tb, tf;
   gettimeofday( &tb, NULL );
   if( debug_level )
      cout << "wait...";
   for( int i = 0; i < nthr; i++ )           // параллельные потоки
      if( pthread_create( h + i, NULL, &block_func, NULL ) != 0 ) {
         cerr << "ошибка создания потока " << i << endl;         
         return EXIT_FAILURE;
      }
   for( int i = 0; i < nthr; i++ ) 
      pthread_join( h[ i ], NULL );
   gettimeofday( &tf, NULL );
   cout << "\r";
   delete [] h;
   timersub( &tf, &tb, &tf );
   long interv = tf.tv_sec * 1000L + tf.tv_usec / 1000L +
                 ( tf.tv_usec % 1000 > 500 ? 1 : 0 );
   cout << "интервал выполнения: " << nthr << " x " << rept << " x " 
        << msec << " = " << interv << " миллисекунд" << endl;
   pthread_spin_destroy( &loc );
}

Простенько и без фокусов:
- когда имеется N процессоров и запускается N+1 и больше (сколько угодно!) потоков (опция -t)...
- то 1-й подошедший поток захватывает спин-блокировку, после чего отправляется спать в пассивный сон...
- все остальные потоки, каждый на своём процессоре, тупо активно вертятся на спин-блокировке, ожидая её освобождения...
- как только владеющий блокировкой поток её освобождает, так её тут же прихватывает следующий из ожидающих :lol:

Код: Выделить всё

olej@ACER:~/2019_WORK/own.WORK/SMP_block$ ./blocko -r30 -d30 -t3 -v
26171: число потоков = 3
интервал выполнения: 3 x 30 x 30 = 2709 миллисекунд
А теперь то же, но без захвата спин-блокировки (опция -s):

Код: Выделить всё

olej@ACER:~/2019_WORK/own.WORK/SMP_block$ ./blocko -r30 -d30 -t3 -v -s
26176: число потоков = 3
интервал выполнения: 3 x 30 x 30 = 904 миллисекунд
Теперь все потоки выполняются параллельно и завершают свою "работу" в -t раз быстрее!
Вложения
blocko.cc
(2.35 КБ) 69 скачиваний

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 19 мар 2019, 10:00

Olej писал(а): Простенько и без фокусов:
Ещё показательнее это на процессоре i7:

Код: Выделить всё

[olej@dell ~]$ nproc
8
Конечно там никакие не 8 процессоров, это гипертриэдинг: 4 ядра с гипертриэдингос = х2 на каждом... но это сути дела не меняет:

Код: Выделить всё

[olej@dell SMP_block]$ ./blocko -r100 -d50 -t9 -v 
19923: число потоков = 9
интервал выполнения: 9 x 100 x 50 = 45171 миллисекунд

[olej@dell SMP_block]$ top -p 19923
%Cpu(s): 97,7 us,  1,0 sy,  0,0 ni,  0,3 id,  0,0 wa,  0,9 hi,  0,1 si,  0,0 st
KiB Mem :  8152356 total,   436676 free,  4388376 used,  3327304 buff/cache
KiB Swap:  6288892 total,  6287988 free,      904 used.  3106248 avail Mem 

  PID USER      PR  NI    VIRT    RES    SHR S  %CPU %MEM     TIME+ COMMAND                                                     
19923 olej      20   0   89352   1804   1648 S 750,7  0,0   3:08.91 blocko                   
Как вам загрузочка под 750% ? :lol:
И для сравнения:

Код: Выделить всё

[olej@dell SMP_block]$ ./blocko -r100 -d50 -t9 -v -s
20070: число потоков = 9
интервал выполнения: 9 x 100 x 50 = 5019 миллисекунд
Ровно в 8 раз "параллельнее". :lol:

Или вот так:

Код: Выделить всё

[olej@dell SMP_block]$ ./blocko -r30 -d30 -t100 -v 
20236: число потоков = 100
интервал выполнения: 100 x 30 x 30 = 99786 миллисекунд

[olej@dell SMP_block]$ ./blocko -r30 -d30 -t100 -v -s
20127: число потоков = 100
интервал выполнения: 100 x 30 x 30 = 909 миллисекунд
Здесь а). 1 поток держит спин-блокировку, б). 8 других крутятся и загружают процессоры в ожидании освобождения спин-блокировки и в). остальные 91 потоков поочерёдно вытеснены ядром в состояние WAIT.

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

Re: параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 19 мар 2019, 10:14

Olej писал(а): Здесь а). 1 поток держит спин-блокировку, б). 8 других крутятся и загружают процессоры в ожидании освобождения спин-блокировки и в). остальные 91 потоков поочерёдно вытеснены ядром в состояние WAIT.
И уж совсем смешно - запустить эту задачу с приоритетом планирования реального времени и сравнить:

Код: Выделить всё

[olej@dell SMP_block]$ ./blocko -r30 -d30 -t9 -v 
20532: число потоков = 9
интервал выполнения: 9 x 30 x 30 = 8175 миллисекунд


[olej@dell SMP_block]$ time sudo chrt -r 20 ./blocko -r30 -d30 -t9 -v
20636: число потоков = 9
интервал выполнения: 9 x 30 x 30 = 18498 миллисекунд

real	0m18,533s
user	2m8,790s
sys	0m0,032s
В этом случае, на время выполнения задачи даже мышка у вас отбивается и переключение окон в DE (будьте осторожны и не задавайте слишком большие опции).
Почему время в режиме RR радикально отличается от нормального запуска? и откуда время time порядка 2 минут, когда задача завершается за 18-19 секунд?
Не знаю! :-o :lol:
Можно предположить, что такое "зависание" на спин-блокировке отодвигает и тормозит внутренние потоки ядра Linux! ... вплоть до того, что сбивает (замедляет?) службу времени ядра!
Во какие дела! :lol:


Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 20 ноя 2023, 19:30

Новый виток интереса к предмету - вот из за этой книги:
Is Parallel Programming Hard, And, If So, What Can You Do About It?
Которая вот-вот, на днях, выйдет в переводе в издательстве BHV.
The current version is v2023.06.11a [PDF] (single-column format [PDF], ebook format [PDF], change log).
Contributions are welcome, and to that end, a public git tree may be found at:
git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git.

Аватара пользователя
Olej
Писатель
Сообщения: 21336
Зарегистрирован: 24 сен 2011, 14:22
Откуда: Харьков
Контактная информация:

параллельность + синхронизации (примеры)

Непрочитанное сообщение Olej » 20 ноя 2023, 19:40

Olej писал(а):
20 ноя 2023, 19:30
Is Parallel Programming Hard, And, If So, What Can You Do About It?
Снимок экрана от 2023-11-20 18-30-59.png
Снимок экрана от 2023-11-20 18-30-59.png (98.79 КБ) 206 просмотров
662 страниц

Код: Выделить всё

olej@R420:~/2023/own.BOOKs/SMP.2$ ls -l perfbook.2023.06.11a.pdf 
-rw-rw-r-- 1 olej olej 8987440 ноя 20 18:33 perfbook.2023.06.11a.pdf
Здесь - все коды примеров, и все сопутствующие (рабочие) материалы автора:

Код: Выделить всё

olej@R420:~/2023/own.BOOKs/SMP.2$ git clone git://git.kernel.org/pub/scm/linux/kernel/git/paulmck/perfbook.git
Клонирование в «perfbook»...
remote: Enumerating objects: 29306, done.
remote: Total 29306 (delta 0), reused 0 (delta 0), pack-reused 29306
Получение объектов: 100% (29306/29306), 99.69 МиБ | 2.66 МиБ/с, готово.
Определение изменений: 100% (21892/21892), готово.
Updating files: 100% (1969/1969), готово.

Код: Выделить всё

olej@R420:~/2023/own.BOOKs/SMP.2$ du -hs perfbook
347M	perfbook

Ответить

Вернуться в «Программирование»

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 4 гостя