Сейчас на форуме: tyns777, zds, JustLife (+3 невидимых)

 eXeL@B —› Программирование —› Синхнообъекты с "изберательной исключаемостью"
Посл.ответ Сообщение

Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 28 декабря 2009 22:22 · Поправил: Vol4ok
· Личное сообщение · #1

Суть задачи в следующем.
Есть 2 типа методов назавем их условно методы группы А и методы группы Б, которые работают с разделяемыми ресурсами - Р. Нужно организовать синхронизацию таким образом чтобы
1) когда работает метод группы Б ни один другой метод из групп А и Б не мог получить доступ к Р.
2) когда работает метод группы А то ни один метод группы Б не мог получить досуп к Р, но методы группы А могли.

Данная задача полезна в том случае когда нужно чтобы методы А могли вызывать другие методы группы А, не вызывая при этом дедлоков. Между собой эти вызовы безопасны, но должны исключать возможность одновременного вызова методов Б.

Например, есть дерево, методы Б модифицируют его структуру, а методы А модифицируют данные листьев, можно скоко угодно раз паралельно модицировать значения листьев атомарными операциями, но нельзя чтобы при этом менялась структура дерева, и наоборот если меняется структура дерева нельзя чтобы медифицировались значения листьев.

Может я тупой, но я пока сходу не вижу ни одной нормальной реализации такого на стандартных объектах синхронизации. Сильно извращаться не хотелось бы.



Ранг: 61.4 (постоянный), 1thx
Активность: 0.020
Статус: Участник

Создано: 28 декабря 2009 22:48
· Личное сообщение · #2

2 мьютекса?
Б захватывает оба.
А захватывает Б-мьютекс.



Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 28 декабря 2009 23:06
· Личное сообщение · #3

n0name пишет:
2 мьютекса?
Б захватывает оба.
А захватывает Б-мьютекс.

Ок, если один метод А захватил Б мьютекс, параллельно вызвали второй метод А, он должен висеть и ждать пока освободится Б - не катит. Или я чего то не понял в вашей схеме?

хм, но в этом все равно чтото есть, если например использовать мьютес и эвент... надо подумать...



Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 28 декабря 2009 23:26
· Личное сообщение · #4

мьютекс + эвент тоже не катит, так как если использовать мьютекс для взаимосключения между Б, а эвент для того чтобы исключить параллельно выполнение Б с А, таким образом будет выполнено условие 2, но все равно остается вариант когда при выполнении Б может запуститься А.



Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 28 декабря 2009 23:55
· Личное сообщение · #5

есть вариант с использованием 2х критических секций и флага, если А захватывает КС - устанавливает флаг, если А будет будет вызван параллельно, то он сперва проверит флаг если флаг установлен то повторных вход в критическую секцию пропускается, в Б никаких проверок не надо. Вторая КС используется для того чтобы не допустить ситуацию рассинхронизации состояния первой КС и флага, например чтобы состояние КС не изменилось пока мы будем работать с флагом.
По идее это должно давать 100% корректной работы, но я пока полностью не уверен. Вцелом вариант довольно корявый, может будут идеи по-красивее?



Ранг: 61.4 (постоянный), 1thx
Активность: 0.020
Статус: Участник

Создано: 29 декабря 2009 00:13
· Личное сообщение · #6

немного не так написал, я имел ввиду не мьютекс, а крит. секцию.
В потоке A -
TryEnterCriticalSection(&critSectB); // теперь крит секция точно залочена, можем продолжать выполнение
WaitForSingleObejct(eventA, -1); // ждем когда выполнится метод B

В потоке B -
EnterCriticalSection(&critSectB);

Как-то так.



Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 29 декабря 2009 00:54 · Поправил: Vol4ok
· Личное сообщение · #7

неплохое решение, но как и мое тоже не дает 100% я придумал ситуацию где обломится как и мое так и ваше решение (если я конеш правильно понял ваше):
Code:
  1. поток А1 [----------]
  2. поток А2        x------------
  3. поток B                  [------------]
  4.                          ****
  5.  
  6. где 
  7. ----- - выполнение потока
  8. [] - вход выход в синхрообъект
  9. - неудачный вход в КС.
  10. * - зона пересечения несовместимых потоков


вцелом в моем случае можно ввести решение со счетчиком входов, но это надо еще обдумать...



Ранг: 27.7 (посетитель), 2thx
Активность: 0.01=0.01
Статус: Участник

Создано: 30 декабря 2009 23:09 · Поправил: ant_man
· Личное сообщение · #8

А

вход
WaitMutex
WaitEvent0Time
++count
ReleaseMutex

...

выход
WaitMutex
if(! --count)SetEvent
ReleaseMutex


Б

вход
again: WaitEventInfinite
WaitMutex
if (count) ReleaseMutex and goto again;

...

выход
ReleaseMutex

------
Фуух. С четвертой правки, кажется, получилось.
Итого: Мутекс+Евент+счетчик.



Ранг: 512.7 (!), 360thx
Активность: 0.270.03
Статус: Модератор

Создано: 30 декабря 2009 23:41
· Личное сообщение · #9

Vol4ok

Есть книга "TheLittleBookofSemaphores" by AllenB.Downey
(на аглицком)
Находится легким движеньем руки по гуглыку
прочитав ее вопросов по синхро появятся не скоро, надеюсь )



Ранг: 47.1 (посетитель), 2thx
Активность: 0.030
Статус: Участник

Создано: 31 декабря 2009 01:51
· Личное сообщение · #10

ant_man
респект, вроде не нашел косяков в вашем решении, только думаю может было бы лучше использовать критические секции вместо мьютекса. Я пришел примерно к такому же решению, но потом выяснил решение этой задачи существовало давно и называется RW lock (tnx ntldr). Принцип там примерно такой же, только устройство значительно сложнее. Я уже преступил к их написанию.

sendersu
спс, полезная книга.



Ранг: 369.8 (мудрец), 400thx
Активность: 0.390
Статус: Участник

Создано: 31 декабря 2009 03:47
· Личное сообщение · #11

Проведем маленький бенчмаркинг разных вариантов синхрообъектов. За образец возьмем Slim Reader/Writer (SRW) Locks из Windows и критические секции оттуда же. Бенчмарк будем проводить в 64х потоках выполняя 100000 захватов синхрообъекта в каждом (половина на чтение, половина на запись) в случайном порядке. Результатом будет общее время для всех потоков (в миллисекундах).

Код бенчмарка (для SRW locks):

Code:
  1. #define N_THREADS 64
  2. #define N_TESTS   100000
  3.  
  4. static u_long   total_time;
  5. static u_long   test_var;
  6. static SRWLOCK  test_srw;
  7.  
  8. static DWORD WINAPI test_thread(void *param)
  9. {
  10.          u_long time = GetTickCount();
  11.          int    i;
  12.  
  13.          for (= 0; i < N_TESTS; i++)
  14.          {
  15.                  if (rand() % 2)
  16.                  {
  17.                         AcquireSRWLockShared(&test_srw);
  18.                         ReleaseSRWLockShared(&test_srw);
  19.                  } else
  20.                  {
  21.                         AcquireSRWLockExclusive(&test_srw);
  22.                         test_var++;
  23.                         ReleaseSRWLockExclusive(&test_srw);
  24.                  }
  25.          }
  26.          time = GetTickCount() - time;
  27.          _InterlockedExchangeAdd(&total_time, time);
  28.          return 0;
  29. }
  30.  
  31. int main(int argc, char* argv[])
  32. {
  33.          HANDLE h_threads[N_THREADS];
  34.          int    i;
  35.  
  36.          InitializeSRWLock(&test_srw);
  37.  
  38.          for (= 0; i < N_THREADS; i++) {
  39.                  h_threads[i] = CreateThread(NULL, 0, test_thread, NULL, 0, NULL);
  40.          }
  41.          WaitForMultipleObjects(N_THREADS, h_threads, TRUE, INFINITE);
  42.  
  43.          printf("time: %d\n", total_time);
  44.          _getch();
  45.          
  46.          return 0;
  47. }


Результаты для процессора Core i7 (4 cores, 8 threads) - 2495 ms

-----
PGP key <0x1B6A24550F33E44A>




Ранг: 369.8 (мудрец), 400thx
Активность: 0.390
Статус: Участник

Создано: 31 декабря 2009 03:50
· Личное сообщение · #12

Заменим SRW locks на обычные критические секции.
Результаты для критических секций - 29164 ms, итого в 11.8 раза хуже SRW locks.

-----
PGP key <0x1B6A24550F33E44A>




Ранг: 369.8 (мудрец), 400thx
Активность: 0.390
Статус: Участник

Создано: 31 декабря 2009 03:54
· Личное сообщение · #13

Теперь вставим в бенчмарк реализацию RW locks by ant_man (исходный код в аттаче).
Я с трудом дождался завершения теста, результат - 3999474 ms, что в 1603 раза хуже SRW locks и в 137 раз хуже критических секций.

4851_30.12.2009_CRACKLAB.rU.tgz - antlock.zip

-----
PGP key <0x1B6A24550F33E44A>




Ранг: 512.7 (!), 360thx
Активность: 0.270.03
Статус: Модератор

Создано: 31 декабря 2009 03:55 · Поправил: sendersu
· Личное сообщение · #14

ntldr

Впервые о таких слышу, чесно говоря, ето чего то новое (SRW locks),
спасибо

из мсдн

Requirements
Minimum supported client Windows Vista
Minimum supported server Windows Server 2008




Ранг: 369.8 (мудрец), 400thx
Активность: 0.390
Статус: Участник

Создано: 31 декабря 2009 03:59
· Личное сообщение · #15

Теперь оптимизируем реализацию RW locks by ant_man, заменив мьютекс на критическую секцию.
Результат - 434410 ms, итого в 174 раза хуже SRW locks и в 15 раз хуже критических секций.

c48c_30.12.2009_CRACKLAB.rU.tgz - antlock.zip

-----
PGP key <0x1B6A24550F33E44A>




Ранг: 369.8 (мудрец), 400thx
Активность: 0.390
Статус: Участник

Создано: 31 декабря 2009 04:08
· Личное сообщение · #16

Ещё немного оптимизируем RW locks by ant_man, чтобы нам не приходилось постоянно делать ResetEvent.
Результат - 304747 ms, в 122 раз хуже SRW locks и в 10 раз хуже критических секций. Для синхропримитива на таком принципе это ИМХО предел.

Выводы:
1 - Каждый вызов ядра обходится невероятно дорого, в идеальном синхропримитиве они должны быть как можно реже.
2 - Преимущество RW locks by ant_man над критическими секциями может возникать только при длительной обработке данных внутри блокировки, т.к. издержки самой блокировки очень велики.
3 - Преимущество виндовых SRW locks неоспоримо в любых режимах работы. Куда ни глянь - идеальный результат.

1dfb_30.12.2009_CRACKLAB.rU.tgz - antlock.zip

-----
PGP key <0x1B6A24550F33E44A>




Ранг: 255.8 (наставник), 19thx
Активность: 0.150.01
Статус: Участник
vx

Создано: 31 декабря 2009 07:09
· Личное сообщение · #17

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



Ранг: 65.3 (постоянный), 10thx
Активность: 0.020
Статус: Участник

Создано: 31 декабря 2009 21:15
· Личное сообщение · #18

Может, сделать один семафор с большим начальным значением (заведомо больше числа потоков А), каждый А понижает его на 1, В - на все initial count?


 eXeL@B —› Программирование —› Синхнообъекты с "изберательной исключаемостью"
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати