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

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

Модератор: Olej

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

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

Непрочитанное сообщение Olej » 22 янв 2013, 03:21

Olej писал(а):P.S. Тесты очень несовершенные (для простоты): параллельные процессы, потоки - начинают непрерывно переключать контекст сразу после создания, т.е. пока создаются следующие параллельные ветки - без синхронизации начала своей работы.
Но при больших числе переключений (-s) и числе ветвей (-n) этот начальный этап нивелируется, что хорошо видно по сходимости и устойчивости результата.
Вот какая хорошая повторяемость при 100 переключающихся процессах/потоках и 10000 передиспетчеризаций в каждом из них:

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

bash-4.2$ sudo nice -n100 ./shedt -n100 -s10000
число потоков = 100, общее число переключений = 1000000,
число процессорных тактов = 1570269300, тактов на переключение = 1570
bash-4.2$ sudo nice -n100 ./shedt -n100 -s10000
число потоков = 100, общее число переключений = 1000000,
число процессорных тактов = 1571919040, тактов на переключение = 1571
bash-4.2$ sudo nice -n100 ./shedt -n100 -s10000
число потоков = 100, общее число переключений = 1000000,
число процессорных тактов = 1569241870, тактов на переключение = 1569

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

bash-4.2$ sudo nice -n100 ./shedp -n100 -s10000
число процессов = 100, общее число переключений = 1000000,
число процессорных тактов = 1701520280, тактов на переключение = 1701
bash-4.2$ sudo nice -n100 ./shedp -n100 -s10000
число процессов = 100, общее число переключений = 1000000,
число процессорных тактов = 1800534390, тактов на переключение = 1800
bash-4.2$ sudo nice -n100 ./shedp -n100 -s10000
число процессов = 100, общее число переключений = 1000000,
число процессорных тактов = 1675575550, тактов на переключение = 1675
Опять же, разница поток vs процесс в пределах 20%

И вот, собственно, всё содержательное тело теста для потоков:

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

void* threadfunc ( void* data ) {
   unsigned long i;
   for( i = 0; i < S; i++ ) pthread_yield();
   pthread_exit( NULL );
   return NULL;
};
...
   pthread_t *tid = (pthread_t*)calloc( sizeof( pthread_t ), N );
   for( i = 0; i < N; i++ ) {
      int status = pthread_create( tid + i, NULL, threadfunc, NULL );
      if( status != 0 ) {
         perror( "pthread_create" );
         continue;
      }
      nf++;
   }
   unsigned long long rdt = rdtsc();
   for( i = 0; i < nf; i++ )
      pthread_join( tid[ i ], NULL );
   rdt = rdtsc() - rdt;
И то же самое действие, выполняемое в параллель процессами:

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

   pid_t pid;
   for( i = 0; i < N; i++ ) {
      pid = fork();
      if( pid < 0 ) {
         perror( "fork error" );
         continue;
      }
      else if ( pid > 0 ) nf++;
      else {
         unsigned long i;
         for( i = 0; i < S; i++ ) sched_yield();
         exit( EXIT_SUCCESS );
      }
   }
   unsigned long long rdt = rdtsc();
   int status;
   for( i = 0; i < nf; i++ ) wait( &status );
   rdt = rdtsc() - rdt;

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

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

Непрочитанное сообщение Olej » 22 янв 2013, 03:30

Olej писал(а): Вот и вся разница в скорости переключений контекстов потоков vs процессов - в пределах 20%!
Вот вам и вся лёгкость. :-o
Кстати, на такие же выводы наталкивает изучение параллельных сетевых серверов, построенных на разных архитектурах: много серверов хороших и разных. И это очень любопытно рассмотреть для сравнения с тем, что здесь рассмотрено выше.

И оттуда заключение: если экземпляры параллельных ветвей выполнения не планируют плотно взаимодействовать между собой, то перевод их с fork()-реализации на потоки - заметного выигрыша в производительности не даст. А вот если ветви должны плотно взаимодействовать, то в fork()-реализации они могут это делать только с применением IPC механизмов, а эти механизмы - медленные (все, даже shared memory), и вот здесь сразу вылезет падение производительности. Но и это плата за изолированные адресные пространства, и надёжность и живучесть проекта.

Вот теперь всё становится, в некоторой мере, на свои места.

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

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

Непрочитанное сообщение Olej » 06 сен 2014, 18:08

По параллельности + синхронизациям за прошедшее время можно много чего добавить:
- насколько всё разнообразнее (чем в книгах) поведение параллельностей при многопроцессорном исполнении, на многих ядрах...
- о других моделях параллельности, кроме процессы/потоки ... и как это реализуется в других языках, Go, например
- и вообще как параллельность реализуется в других языкх ...
- в Python, например, где реализация на параллельных процессах будет быстрее, чем на потоках ... а на потоках может быть медленнее, чем в последовательностном выполнении...
- и как потоки реализуются языковыми надстройками ... С++, например, или Boost, ... или APR для C ...

Много накопилось заметок и примеров.
Сяду это всё связать в единое описание ... если доведу до ума - выложу в форум.

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

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

Непрочитанное сообщение Olej » 07 сен 2014, 20:20

Olej писал(а):По параллельности + синхронизациям за прошедшее время можно много чего добавить:
- насколько всё разнообразнее (чем в книгах) поведение параллельностей при многопроцессорном исполнении, на многих ядрах...
- о других моделях параллельности, кроме процессы/потоки ... и как это реализуется в других языках, Go, например
- и вообще как параллельность реализуется в других языкх ...
- в Python, например, где реализация на параллельных процессах будет быстрее, чем на потоках ... а на потоках может быть медленнее, чем в последовательностном выполнении...
- и как потоки реализуются языковыми надстройками ... С++, например, или Boost, ... или APR для C ...

Много накопилось заметок и примеров.
Сяду это всё связать в единое описание ... если доведу до ума - выложу в форум.
Вот предварительные наброски:
SMP_04.odt
(179.45 КБ) 410 скачиваний
Это сам текст (правда "предварительности" там набралось почти на 100 стр. - 96 ;-) ).
Там много любоытного накопилось, это нужно было воедино свести + исполнением примеров подтвердить, чтобы не потерялось и не забылось:
- почему для процесса с 5-ю потоками после выполнения fork() создаётся процесс-дубль с 1-м потоком ... и как воссоздать все 5?
- как точно работает pthread_atfork()?, потому как про него во многих местах написаны откровенные глупости ...
- как динамически определять число процессоров SMP где сейчас выполняется задача?
- и как распределять эту задачу только на выбранные процессоры SMP?
Очень много любопытного особо возникает после массового внедрения SMP!

А вот архив к нему примеров кода:
examples.SMP.04.tgz
(302.5 КБ) 428 скачиваний
Многие из этих примеров давние, и показывались раньше ... но сейчас они все были перепроверены в Linux с ядром 3.15, и где нужно подправлены.

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

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

Непрочитанное сообщение Olej » 24 сен 2014, 12:37

Olej писал(а): Вот предварительные наброски:
Теперь очередная редакция (расширение) выложена: Параллелизм, конкурентность, многопроцессорность в Linux
Там же будут выкладываться все последующие расширения, улучшения и исправления.

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

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

Непрочитанное сообщение Olej » 09 дек 2014, 11:56

Интересный цирк получается ;-) ...
Вот такой фрагментик:

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

int finish = 1;                               // флаг завершения потока

void *RunCounter( void *res ) {    // потоковая функция
   long count = 0;
   while( finish ) {
//      gettimeofday( &cur, NULL );
      count += 1;
   };
   *(long*)res = count;
   return NULL;
}
...
pthread_create( &tid, NULL, RunCounter, (void*)res );
sleep( 1 );    // всё должно бы завершиться через 1 секунду!!!
finish = 0;
pthread_join( tid[ i ], NULL );
...
Вот такой простейший поток ... который считает счётчик ;-) , и должен завершиться по флагу finish.
Только это происходит так только если компилируется без какой-либо оптимизации:

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

$ gcc -Wall -O0 -lm -lpthread xxx.c -o xxx
Ну на худой конец:

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

$ gcc -Wall -lm -lpthread xxx.c -o xxx
Но стоит поставить хотя бы минимальный уровень оптимизации:

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

$ gcc -Wall -O1 -lm -lpthread xxx.c -o xxx
И цикл потоковой функции никогда не завершается! :-o
Во как наоптимизировал GCC... :-x

Но стоит в цикл поставить любой (?) системный вызов (там где закомментирован gettimeofday( &cur, NULL ); ) и всё восстанавливается.

Т.е. при "оптимизации" цикла (в любом месте программы!):

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

   while( finish ) count++;
Он никогда не заканчивается.

От такой ошибки поседеть можно! :-o

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

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

Непрочитанное сообщение Olej » 09 дек 2014, 12:52

Подсказали здесь ;-) ...

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

int volatile finish = 1;                    // флаг завершения потока

void *RunCounter( void *res ) {    // потоковая функция
   long count = 0;
   while( finish ) count++;
   *(long*)res = count;
   return NULL;
}
И вот теперь всё ОК, при:

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

$ gcc -Wall -O3 -lm -lpthread xxx.c -o xxx

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

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

Непрочитанное сообщение Olej » 10 дек 2014, 12:38

Olej писал(а):Интересный цирк получается ;-) ...
Это занятие у меня не от скуки ... А решил разобраться как и кто из языковых систем программирования умеют управляться с многопроцессорностью (многоядерностью, SMP), и умеет задействовать эти много процессоров в параллель.

Потому как конкурентность (то что есть всякая техника использования потоков/процессов) и параллельность (возможность гонять эти потоки одновременно на разных процессорах) - это вовсе не одно и то же.

Это совсем отчётливо понимают, по-моему, только разработчики языка Go, и много этому уделяют места в развитии. А в других языках разработки этому мало уделяют внимания... Как самый характерный пример - Python, где можно разделить работу на 4 части для раскладывания её на 4 процессора, и в результате получить удлиннение общего выполнения на 30% по сравнению с 1-м процессором! :-o

В чисто компилирующих языках проблемы не должно возникать - там скомпилировали переключение контекста (с поддержкой аппаратного переключения задач или нет) и оно так и будет выполняться. Но таких чисто компилирующих языков что в природе осталось?: C, C++, Go ... вот и всё.

А вот там где выполнение при поддержке исполняющей системы, виртуальной языковой машины, байт-кода, интерпретатора - вот там возникают вопросы...
Либо для поддержки новой ветки (поток/процесс) должен создаваться новый экземпляр виртуальной машины (дочерние процессы в Python), выполняющиеся на разных процессорах, либо потоки будут шедулироваться не операционной системой, а виртуальной машиной языка, и разнести их по процессорам не представляется возможным.

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

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

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

Непрочитанное сообщение Olej » 10 дек 2014, 15:03

Olej писал(а): Вот для этого (тестирования, проверки) нужно бы писать подобные многопоточные приложения на разных языках:
- потоки должны бы выполнять циклы наиболее простой работы...
- независимо, без синхронизации, по возможности не задействуя механизмы синхронизации (которые в разы медленнее простых операций)...
- и обрываться принудительно по истечению времени тестирования.
И вот по итоговому числу выполненных "порций" элементарной работы можно судить о том сколько процессоров было вовлечено в работу программы.
Логика в такие приложения может быть заложена ... я по крайней мере, на первый взгляд вижу 3 варианта...
Во всех - потоковая функция только тупо инкрементирует целочисленный счётчик в цикле (которое потом пройденное число циклов и будем анализировать по завершению).
Все N потоков нужно запускать одновременно и обрубать их одновременно ... вариант фиксированного интервала выполнения каждого потока был бы точнее (на маленький разбег времени запуска потоков), но так делать нельзя: N+1 поток, тупо прождавший N-й, будет довыполняться уже после завершения N-го (и ещё скольки то там...).
А вот вариантов как остановить все потоки и видится все три:

1. Каждый поток знает время общего старта и интервал выполнения, по завершению отпущенного времени сам завершается. Это хороший вариант в смысле отсутствия каких-либо синхронизация (каждый поток себе барин), но ... в каждом цикле кроме инкремента счётчика потоку нужно делать системный вызов считывания времени, типа gettimaofday(), который может вызывать wait-состояние, чем нарушать параллельное выполнение абсолютно активных потоков. От этого хорошего варианта я отказался (т.е. он и был 1-м реализованным, но потом отброшенным).

2. Иметь в цикле инкремента потока логическую переменную "пора завершаться" ;-) :

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

while( finish ) count++;
Вот отсюда и сложность, которая обнаружилась выше... Но она решаемая, а эффекты - очень интересные ... в разных языках программирования. ;-)
Запускающий поток будет выполнять sleep() нужный интервал, после чего менять условие finish - потоки завершаться сами.

3. После sleep() запускающего потока, выполнять в нём pthread_cancel() для каждого считающего потока.
Очень чистая идея ... но осложнённая тем, что разные реализации модели потоков придумывают (C++11, Boost) свои обёртки для pthread_t, в которых а). такие "тонкие" ;-) штучки как pthread_cancel() они забывают сделать, а б). к самому pthread_t их модели-обёртки не так просто добраться.
Напомню, что pthread_cancel() не убивает поток, а говорит, что тому "пора завершаться" ... когда он дойдёт до ближайшей точки завершаемости, поэтому сам поток перед циклическим инкрементом должен сделать что-то типа:

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

   pthread_setcancelstate( PTHREAD_CANCEL_ENABLE, NULL );
   pthread_setcanceltype( PTHREAD_CANCEL_ASYNCHRONOUS, NULL );

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

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

Непрочитанное сообщение Olej » 10 дек 2014, 16:02

Olej писал(а):Подсказали здесь ;-) ...
Попутно и кстати...
Для тех, кто занимается преподаванием, обучением, объяснениями коллегам и т.д.
Очень интересные и наглядные конструкции получаются в таких кодах.
Вспомните, как вам объясняли смысл volatile в C? ... как: это что-то, где-то, в железе-аппаратуре, в прерываниях, может когда-то ;-) ... Вот так, на пальцах, без всякого иллюстрирующего кода (потому что такой работающий код действительно придумать не просто).
Или то же самое относительно synchronized в Java...

А здесь необходимо писать код такого вот типа, потому что без этого он просто не работает!:

C, 2-я модель:

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

int volatile finish = 1;                // флаг завершения потока

void *RunCounter( void *res ) {         // потоковая функция
   long count = 0;
   while( finish ) count++;
   *(long*)res = count;
   return NULL;
}


C, 3-я модель:

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

void *RunCounter( void *res ) {         // потоковая функция
   pthread_setcancelstate( PTHREAD_CANCEL_ENABLE, NULL );
   pthread_setcanceltype( PTHREAD_CANCEL_ASYNCHRONOUS, NULL );
   volatile long *p = (long*)res;
   while( 1 ) *p += 1;
   return NULL;
}
C++11, используется класс thread:: :

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

void thrfunc( volatile long *res ) {         // потоковая функция
   pthread_setcancelstate( PTHREAD_CANCEL_ENABLE, NULL );
   pthread_setcanceltype( PTHREAD_CANCEL_ASYNCHRONOUS, NULL );
   while( true ) ++*res;
}

class RunCounter : public thread {
private:
   long volatile count;
public:
   RunCounter() : thread( thrfunc, &count ), count( 0 ) {}
   void cancel() {
      ostringstream msg;
      msg << get_id();
      pthread_cancel( stoul( msg.str() ) );
   }
   long getCount() { return count; }
};


Java:

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

class RunCounter extends Thread {
   private static boolean finish = false;       // флаг завершения
   synchronized static void setFinal() { finish = true; };
   synchronized static boolean getFinal() { return finish; }
   private long count;
   RunCounter() { count = 0;  }
   public void run() {
     while( !getFinal() ) count++;
   }
   long getCount() { return count; }
}
И в каждом из них стоит убрать volatile из нужного места и ... работающий код перестаёт быть таким.
Или ещё хуже: при компиляции без оптимизации (-O0) он рабочий, а при малейшем уровне оптимизации компилятором (-O1) - дохлый. :-o

Ответить

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

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

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