1. Функция чтения (ну пусть атомарно).
2. Функция записи (так же атомарно).
3. ГСЧ.
4. Функция задержки времени.
Нужно:
1. Считать число (изначально 0).
2. Увеличить число на 1.
3. Записать число.
Но при этом нужно чтобы все это корректно работало в многопоточной среде. Т.е. сколько было вызовов чтения/записи (ну или потоков, который выполнили чтение а затем конечную запись) — столько должно быть установлено значение счетчика.
Добавлю что считывать и записывать — можно произвольное значение, а не только числа.
Так же можно сузить определение гарантированности — считаем что GUID т.е. 16 случайных байт — гарантированно уникальный, что второй такой же не будет создан за время существования Вселенной.
Можно ли как-то гарантировать, не имея мьютексов и пр. блокировок — а только 4 функции из списка?
Здравствуйте, Shmj, Вы писали:
S>Ну давайте с простого. Имеем:
S>1. Функция чтения (ну пусть атомарно). S>2. Функция записи (так же атомарно). S>3. ГСЧ. S>4. Функция задержки времени.
S>Нужно:
S>1. Считать число (изначально 0). S>2. Увеличить число на 1. S>3. Записать число.
S>Но при этом нужно чтобы все это корректно работало в многопоточной среде. Т.е. сколько было вызовов чтения/записи (ну или потоков, который выполнили чтение а затем конечную запись) — столько должно быть установлено значение счетчика.
S>Добавлю что считывать и записывать — можно произвольное значение, а не только числа.
S>Так же можно сузить определение гарантированности — считаем что GUID т.е. 16 случайных байт — гарантированно уникальный, что второй такой же не будет создан за время существования Вселенной.
S>Можно ли как-то гарантировать, не имея мьютексов и пр. блокировок — а только 4 функции из списка?
1.Получаем значение гсч от 0 до бесконечности
2. Делаем задержку равную выданному гсч значению
3. Выполняем операции
В таком варианте вероятность что два потока помешают друг другу близка к нулю.
Здравствуйте, Shmj, Вы писали:
S>Ну давайте с простого. Имеем:
S>1. Функция чтения (ну пусть атомарно). S>2. Функция записи (так же атомарно). S>3. ГСЧ. S>4. Функция задержки времени.
S>Нужно:
S>1. Считать число (изначально 0). S>2. Увеличить число на 1. S>3. Записать число.
S>Но при этом нужно чтобы все это корректно работало в многопоточной среде. Т.е. сколько было вызовов чтения/записи (ну или потоков, который выполнили чтение а затем конечную запись) — столько должно быть установлено значение счетчика. S>Добавлю что считывать и записывать — можно произвольное значение, а не только числа. S>Так же можно сузить определение гарантированности — считаем что GUID т.е. 16 случайных байт — гарантированно уникальный, что второй такой же не будет создан за время существования Вселенной. S>Можно ли как-то гарантировать, не имея мьютексов и пр. блокировок — а только 4 функции из списка?
Да нефиг делать. Каждый поток имеет по своему счетчику и пусть увеличивает его атомарно наздоровье.
Здравствуйте, Qulac, Вы писали:
Q>1.Получаем значение гсч от 0 до бесконечности Q>2. Делаем задержку равную выданному гсч значению Q>3. Выполняем операции
Q>В таком варианте вероятность что два потока помешают друг другу близка к нулю.
Ну это рабочее решение, однако же не оптимальное.
А вот такой вариант:
1. Генерим GUID.
2. Считываем значение.
3. Если спец. символ (не число) с GUID — то ждем 2 единицы времени переходим к шагу 2.
5. Записываем спец. символ + наш GUID.
6. Считываем значение. Если GUID не совпадает — то переходим к шагу 2.
7. Записываем число.
Ну как-то типа того, если не путаю, должно работать. И без всяких бесконечных ожиданий вроде.
Здравствуйте, kov_serg, Вы писали:
_>Да нефиг делать. Каждый поток имеет по своему счетчику и пусть увеличивает его атомарно наздоровье.
Так у нас 1 функция, которая запишет 1 значение (можно любое) и вторая — умеет считать значение. Оно же когда записывает — то не смотрит что затирается.
Здравствуйте, Shmj, Вы писали:
S>Так у нас 1 функция, которая запишет 1 значение (можно любое) и вторая — умеет считать значение. Оно же когда записывает — то не смотрит что затирается.
Так пусть функция в зависимости от потока пишет и читает в разные участки памяти, делов-то
Здравствуйте, Shmj, Вы писали:
S>Здравствуйте, Qulac, Вы писали:
Q>>1.Получаем значение гсч от 0 до бесконечности Q>>2. Делаем задержку равную выданному гсч значению Q>>3. Выполняем операции
Q>>В таком варианте вероятность что два потока помешают друг другу близка к нулю.
S>Ну это рабочее решение, однако же не оптимальное.
S>А вот такой вариант:
S>1. Генерим GUID. S>2. Считываем значение.
Тут другой поток резко ускорился и выполнил шаги 3 — 7. и считанное значение стало устаревшим.
S>3. Если спец. символ (не число) с GUID — то ждем 2 единицы времени переходим к шагу 2. S>5. Записываем спец. символ + наш GUID. S>6. Считываем значение. Если GUID не совпадает — то переходим к шагу 2. S>7. Записываем число.
S>Ну как-то типа того, если не путаю, должно работать. И без всяких бесконечных ожиданий вроде.
Здравствуйте, Shmj, Вы писали:
S>А вот такой вариант:
S>1. Генерим GUID. S>2. Считываем значение. S>3. Если спец. символ (не число) с GUID — то ждем 2 единицы времени переходим к шагу 2. S>5. Записываем спец. символ + наш GUID. S>6. Считываем значение. Если GUID не совпадает — то переходим к шагу 2. S>7. Записываем число.
S>Ну как-то типа того, если не путаю, должно работать. И без всяких бесконечных ожиданий вроде.
Тогда уж проще. Договариваемся, что нулевой GUID означает, что ресурс не занят.
Поток делает примерно следущее
1. Читаем GUID в цикле. Если прочемся 0, выходим из цикла, иначе повторяем с некоторой случайной задержкой.
2. Пишем свой GUID, делаем фиксированную задержку и читаем. Если свой и прочёлся, едем дальше, иначе переходим к пункту 1.
3. Читаем счетчик, увеличиваем, записываем.
4. Записываем нулевой GUID.
Собственно, в пунктах 1, 2 и 4 мы сделали mutex
Задержка в пунтке 2 должна быть заведомо большей, чем случайная задержка, которую может вставить квантователь.
Здравствуйте, Shmj, Вы писали:
_>>Да нефиг делать. Каждый поток имеет по своему счетчику и пусть увеличивает его атомарно наздоровье.
S>Так у нас 1 функция, которая запишет 1 значение (можно любое) и вторая — умеет считать значение. Оно же когда записывает — то не смотрит что затирается.
А нахрена ему смотреть при записи? В счетчик потока никто другой не пишет.
На самом деле kov_serg дело говорит (единственный тут). Это будет работать быстро и надежно. И то что в этом подходе вообще не надо бредовые 3 и 4 это большой плюс тоже.
Здравствуйте, kov_serg, Вы писали:
S>>Так у нас 1 функция, которая запишет 1 значение (можно любое) и вторая — умеет считать значение. Оно же когда записывает — то не смотрит что затирается. _>Так пусть функция в зависимости от потока пишет и читает в разные участки памяти, делов-то
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, Shmj, Вы писали:
S>>А вот такой вариант:
S>>1. Генерим GUID. S>>2. Считываем значение. S>>3. Если спец. символ (не число) с GUID — то ждем 2 единицы времени переходим к шагу 2. S>>5. Записываем спец. символ + наш GUID. S>>6. Считываем значение. Если GUID не совпадает — то переходим к шагу 2. S>>7. Записываем число.
S>>Ну как-то типа того, если не путаю, должно работать. И без всяких бесконечных ожиданий вроде.
Pzz>Тогда уж проще. Договариваемся, что нулевой GUID означает, что ресурс не занят.
Pzz>Поток делает примерно следущее Pzz>1. Читаем GUID в цикле. Если прочемся 0, выходим из цикла, иначе повторяем с некоторой случайной задержкой. Pzz>2. Пишем свой GUID, делаем фиксированную задержку и читаем. Если свой и прочёлся, едем дальше, иначе переходим к пункту 1. Pzz>3. Читаем счетчик, увеличиваем, записываем. Pzz>4. Записываем нулевой GUID.
Pzz>Собственно, в пунктах 1, 2 и 4 мы сделали mutex
Pzz>Задержка в пунтке 2 должна быть заведомо большей, чем случайная задержка, которую может вставить квантователь.
Два потока одновременно выполняют пункт 1. Прочелся 0. Первый поток встал на тормоза, второй доходит до 3 считывает значение и встает на тормоза. Первый поток начинает работать, думает, что блокировки нет, и выполняет все пункты. Второй поток спускается с тормозов и выполняет до конца пункт 3 и 4. В итоге второй поток увеличивал устаревшее значение.
Здравствуйте, Qulac, Вы писали:
Q>Два потока одновременно выполняют пункт 1. Прочелся 0. Первый поток встал на тормоза, второй доходит до 3 считывает значение и встает на тормоза. Первый поток начинает работать, думает, что блокировки нет, и выполняет все пункты. Второй поток спускается с тормозов и выполняет до конца пункт 3 и 4. В итоге второй поток увеличивал устаревшее значение.
Поток сначала пишет свой GUID, потом встаёт на тормоза, потом проверяет, что GUID все еще принадлежит ему.
Соответственно, если оба потока прочтут 0 и запишут свой GUID, потом, после задержки, только одному из них посчастливится получирть свой GUID назад. А второй отправится ждать нуля.
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, Qulac, Вы писали:
Q>>Два потока одновременно выполняют пункт 1. Прочелся 0. Первый поток встал на тормоза, второй доходит до 3 считывает значение и встает на тормоза. Первый поток начинает работать, думает, что блокировки нет, и выполняет все пункты. Второй поток спускается с тормозов и выполняет до конца пункт 3 и 4. В итоге второй поток увеличивал устаревшее значение.
Pzz>Поток сначала пишет свой GUID, потом встаёт на тормоза, потом проверяет, что GUID все еще принадлежит ему.
Pzz>Соответственно, если оба потока прочтут 0 и запишут свой GUID, потом, после задержки, только одному из них посчастливится получирть свой GUID назад. А второй отправится ждать нуля.
Я про другое. Мы должны проектировать многопоточный код так, как буд-то про потоки известно только то, что следующий оператор когда ни будь выполнится. В этом случае предложенный алгоритм не дает 100% гарантии ожидаемой работы. На практике скорей всего этого не случится, но я больше про теорию.
Здравствуйте, Qulac, Вы писали:
Pzz>>Соответственно, если оба потока прочтут 0 и запишут свой GUID, потом, после задержки, только одному из них посчастливится получирть свой GUID назад. А второй отправится ждать нуля.
Q>Я про другое. Мы должны проектировать многопоточный код так, как буд-то про потоки известно только то, что следующий оператор когда ни будь выполнится. В этом случае предложенный алгоритм не дает 100% гарантии ожидаемой работы. На практике скорей всего этого не случится, но я больше про теорию.
Мы не должны.
Просто эта модель теоретически проще. Поэтому обычно мы стараемся ей следовать.
Но в некоторых ситуациях она не работает. Тогда, собственно, вариантов у нас два: или сидеть, горько плакать, или попробовать другие модели.
В данном случае я предложил альтернативную модель, введя дополнительное требование к модели исполнения: выполнение кода не должно прерываться на столь долгое время, что невозможно выбрать задержку, которая это время покроет. С практической точки зрения, это вполне достижимое, реалистичное требование.
