eXeL@B —› Программирование —› Синхнообъекты с "изберательной исключаемостью" |
Посл.ответ | Сообщение |
|
Создано: 28 декабря 2009 22:22 · Поправил: Vol4ok · Личное сообщение · #1 Суть задачи в следующем. Есть 2 типа методов назавем их условно методы группы А и методы группы Б, которые работают с разделяемыми ресурсами - Р. Нужно организовать синхронизацию таким образом чтобы 1) когда работает метод группы Б ни один другой метод из групп А и Б не мог получить доступ к Р. 2) когда работает метод группы А то ни один метод группы Б не мог получить досуп к Р, но методы группы А могли. Данная задача полезна в том случае когда нужно чтобы методы А могли вызывать другие методы группы А, не вызывая при этом дедлоков. Между собой эти вызовы безопасны, но должны исключать возможность одновременного вызова методов Б. Например, есть дерево, методы Б модифицируют его структуру, а методы А модифицируют данные листьев, можно скоко угодно раз паралельно модицировать значения листьев атомарными операциями, но нельзя чтобы при этом менялась структура дерева, и наоборот если меняется структура дерева нельзя чтобы медифицировались значения листьев. Может я тупой, но я пока сходу не вижу ни одной нормальной реализации такого на стандартных объектах синхронизации. Сильно извращаться не хотелось бы. |
|
Создано: 28 декабря 2009 22:48 · Личное сообщение · #2 |
|
Создано: 28 декабря 2009 23:06 · Личное сообщение · #3 n0name пишет: 2 мьютекса? Б захватывает оба. А захватывает Б-мьютекс. Ок, если один метод А захватил Б мьютекс, параллельно вызвали второй метод А, он должен висеть и ждать пока освободится Б - не катит. Или я чего то не понял в вашей схеме? хм, но в этом все равно чтото есть, если например использовать мьютес и эвент... надо подумать... |
|
Создано: 28 декабря 2009 23:26 · Личное сообщение · #4 |
|
Создано: 28 декабря 2009 23:55 · Личное сообщение · #5 есть вариант с использованием 2х критических секций и флага, если А захватывает КС - устанавливает флаг, если А будет будет вызван параллельно, то он сперва проверит флаг если флаг установлен то повторных вход в критическую секцию пропускается, в Б никаких проверок не надо. Вторая КС используется для того чтобы не допустить ситуацию рассинхронизации состояния первой КС и флага, например чтобы состояние КС не изменилось пока мы будем работать с флагом. По идее это должно давать 100% корректной работы, но я пока полностью не уверен. Вцелом вариант довольно корявый, может будут идеи по-красивее? |
|
Создано: 29 декабря 2009 00:13 · Личное сообщение · #6 немного не так написал, я имел ввиду не мьютекс, а крит. секцию. В потоке A - TryEnterCriticalSection(&critSectB); // теперь крит секция точно залочена, можем продолжать выполнение WaitForSingleObejct(eventA, -1); // ждем когда выполнится метод B В потоке B - EnterCriticalSection(&critSectB); Как-то так. |
|
Создано: 29 декабря 2009 00:54 · Поправил: Vol4ok · Личное сообщение · #7 неплохое решение, но как и мое тоже не дает 100% я придумал ситуацию где обломится как и мое так и ваше решение (если я конеш правильно понял ваше): Code:
вцелом в моем случае можно ввести решение со счетчиком входов, но это надо еще обдумать... |
|
Создано: 30 декабря 2009 23:09 · Поправил: ant_man · Личное сообщение · #8 |
|
Создано: 30 декабря 2009 23:41 · Личное сообщение · #9 |
|
Создано: 31 декабря 2009 01:51 · Личное сообщение · #10 ant_man респект, вроде не нашел косяков в вашем решении, только думаю может было бы лучше использовать критические секции вместо мьютекса. Я пришел примерно к такому же решению, но потом выяснил решение этой задачи существовало давно и называется RW lock (tnx ntldr). Принцип там примерно такой же, только устройство значительно сложнее. Я уже преступил к их написанию. sendersu спс, полезная книга. |
|
Создано: 31 декабря 2009 03:47 · Личное сообщение · #11 Проведем маленький бенчмаркинг разных вариантов синхрообъектов. За образец возьмем Slim Reader/Writer (SRW) Locks из Windows и критические секции оттуда же. Бенчмарк будем проводить в 64х потоках выполняя 100000 захватов синхрообъекта в каждом (половина на чтение, половина на запись) в случайном порядке. Результатом будет общее время для всех потоков (в миллисекундах). Код бенчмарка (для SRW locks): Code:
Результаты для процессора Core i7 (4 cores, 8 threads) - 2495 ms ----- PGP key |
|
Создано: 31 декабря 2009 03:50 · Личное сообщение · #12 Заменим SRW locks на обычные критические секции. Результаты для критических секций - 29164 ms, итого в 11.8 раза хуже SRW locks. ----- PGP key |
|
Создано: 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 |
|
Создано: 31 декабря 2009 03:55 · Поправил: sendersu · Личное сообщение · #14 |
|
Создано: 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 |
|
Создано: 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 |
|
Создано: 31 декабря 2009 07:09 · Личное сообщение · #17 Виндоз предоставляет минимальный функционал для синхронизации. Можно стопяцот не выполнимых задач придумать. Если к ресурсу обращения происходят слишком часто, например тысячи раз в секунду то используются циклы ожидания с атомарными проверками, спинблокировки и пр., что пожирает процессорное время, но это наилучшее решение. Иначе на обработку сервисов уйдёт времени больше, чем на полезную нагрузку которую выполняют потоки, в юзермоде такое вобще применяться не должно. |
|
Создано: 31 декабря 2009 21:15 · Личное сообщение · #18 |
eXeL@B —› Программирование —› Синхнообъекты с "изберательной исключаемостью" |