Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет.
Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается.
Как такое можно реализовать? Мысль ясно надеюсь выразил?
В какую сторону рыть?
Здравствуйте, Аноним, Вы писали:
А>Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет. А>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>Как такое можно реализовать? Мысль ясно надеюсь выразил? А>В какую сторону рыть?
Используй mutex или critical section
Посмотри в сторону библиотеки wxWidgets там синхронизация объектов хорошо сделана и
документация доходчивая.
Здравствуйте, Аноним, Вы писали:
А>Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет. А>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>Как такое можно реализовать? Мысль ясно надеюсь выразил? А>В какую сторону рыть?
классическая read/write (rwlock) блокировки. Подробнее в гугл
основной поток, чтобы не блокироваться, делает try write lock или try read lock. Вспомогательный — read lock. Учитывая что только вспомогательный только читает и идеей rwlock несколько читателей не блокируют друг друга, основной поток при чтении может сразу вызывать read lock (вместо try read lock)
Re[2]: Как правильно реализовать алгоритм?
От:
Аноним
Дата:
10.07.07 18:56
Оценка:
Здравствуйте, paccbet, Вы писали: P>Используй mutex или critical section
Здравствуйте, Аноним, Вы писали:
А>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>Как такое можно реализовать? Мысль ясно надеюсь выразил?
Здравствуйте, kondrik, Вы писали:
K>Здравствуйте, Didro, Вы писали: D>>Платформа, язык реализации? K>Visual C++ 6
Достаточно давно не работал с С++.
Общая идея решения конкретно вашей проблемы — "при этом основной поток не должен блокироваться" — проста и была озвучена выше в посте ilnar.
Она выражается в том, что вам нужно найти библиотеку для С++, в которой будет такой элемент как, назовем его, try write lock — поток перед тем как пытаться захватывать блокировку будет спрашивать, "а не захвачена ли она уже?" — и если захвачена, то он блокироваться не будет, а будет идти себе дальше (обрабатывая сообщения или делая ещё чего-нибудь). Правда в этом случае основной поток должен будет сам реализовать очередь. Примером такого примитива является OMP_TEST_LOCK в библиотекеOpenMP:
OMP_TEST_LOCK
Пробует захватить указанный замок. Если это невозможно, возвращает .FALSE.
думаю есть и более элегантные решения...и в других библиотеках.
Однако, если я правильно понимаю, то даже если мы вынесем очередь в отдельный поток (или сделаем её частью библиотеки), то встанет проблема согласованности основного потока и общих данных — например, перед тем как производить чтение данных, основной поток все равно должен будет дождатся пока данные из очереди попадут в общие данные и на это время он будет заблокирован. Ведь так?
Здравствуйте, Аноним, Вы писали:
А>Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет. А>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>Как такое можно реализовать? Мысль ясно надеюсь выразил? А>В какую сторону рыть?
Вообще говоря можно реализовать очередь в которой операция добавления не блокируется операциями извлечения данных из очереди (в случае FIFO)
Не уверен есть ли говорые реализации, но написать можно если аккуратно продумать случай пустой очереди и очереди с одним элементом, где однавременное добавление и извлечение требует синхронизации.
У MS была реализация Lock-Free cписка. Но я не уверен, что она задокументирована.
А вообще так ли важно вам требование чтобы основной поток не блокировался? Если обернуть в критическую секцию только добавление и извлечение сообщений из очереди, то вероятность длительной блокировки потока не велика, если время обработки сообщения сколько-нибудь значительно по сравнению с тривиальной операцией извлечения из очереди. (Если это не так, то нет смысла городить потоки, проще обработать сообщение и не класть его в очередь)
Здравствуйте, Risk Server, Вы писали:
RS>Здравствуйте, Аноним, Вы писали:
А>>Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет. А>>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>>Как такое можно реализовать? Мысль ясно надеюсь выразил? А>>В какую сторону рыть?
RS>Вообще говоря можно реализовать очередь в которой операция добавления не блокируется операциями извлечения данных из очереди (в случае FIFO) RS>Не уверен есть ли говорые реализации, но написать можно если аккуратно продумать случай пустой очереди и очереди с одним элементом, где однавременное добавление и извлечение требует синхронизации. RS>У MS была реализация Lock-Free cписка. Но я не уверен, что она задокументирована.
RS>А вообще так ли важно вам требование чтобы основной поток не блокировался? Если обернуть в критическую секцию только добавление и извлечение сообщений из очереди, то вероятность длительной блокировки потока не велика, если время обработки сообщения сколько-нибудь значительно по сравнению с тривиальной операцией извлечения из очереди. (Если это не так, то нет смысла городить потоки, проще обработать сообщение и не класть его в очередь)
Основной поток допускается чтобы блокировался на короткое время. Дополнительный поток (поток чтения) выполняет функцию поиска — он занимает до 15 секунд, а это много для блокирования основного потока. Во время поиска может прийти 1 сообщение на изменение данных основному потоку. Остается както бросить его в очередь и по окончании поиска — выполнить изменение данных. Чуствую что както нужно прикрепить TryEnterCriticalSection и очередь.
Здравствуйте, Аноним, Вы писали:
А>Есть основной поток в приложении и дополнительный. Они работают с одними и теми же данными.Основной поток данные может читать и изменять, а дополнительный их только читает, но не изменяет. А>Если идет изменение данных, то никто не должен иметь права читать, а если идет чтение, то нельзя изменять данные, при этом основной поток не должен блокироваться (сообщения должны как бы собираться в очередь), для дополнительного потока блокирование допускается. А>Как такое можно реализовать? Мысль ясно надеюсь выразил? А>В какую сторону рыть?
отвечу всем сразу здесь.
1. что такое rwlock тому подобное — гугл все расскажет теорию и реализации. для С++ на visual6 найдете codeproject.com по rwlock. для pthread из линукса есть стадартные вызова. для дотнета кажется, тоже есть стандартные объекы
2. автор сообщения недостаточно описал, что за общие данные и откуда и зачем тут очередь? если один поток заполняет очередь, а другой читает — это pool задач или потоков или все вместе. в том же codeproject найдете treadpool, и тому подобное. Если это очередь операций на модификацию — другое — тут очередь не нужно синхронизировать, а просто выполнить когда станут доступны данные на запись
3. почти все римитивы блокировок содержат варианты TRY — это пробная блокировка, если заблокировал, возвращается удача и можешь работать. Если кем-то уже заблокировано, то не блокируешься в ожидании, а просто получаешь код что пока занято, подойдешь позже, в очередь ожидающих освобожения не встаешь.
4. давайте не соваться в OpenMP, область его применения — директивное распараллеливание. при заранее заданных 2-х потоках с требованиеями к параллельности — не его задача, хоть и возможно. Вы же не ездите с москвы в петербург через нью-йорк?
Здравствуйте, kondrik, Вы писали:
K>Основной поток допускается чтобы блокировался на короткое время. Дополнительный поток (поток чтения) выполняет функцию поиска — он занимает до 15 секунд, а это много для блокирования основного потока. Во время поиска может прийти 1 сообщение на изменение данных основному потоку. Остается както бросить его в очередь и по окончании поиска — выполнить изменение данных. Чуствую что както нужно прикрепить TryEnterCriticalSection и очередь.
Основной поток:
EnterCriticalSection
EqueueWork(запрос на выполнение поиска или изменение данных)
LeaveCriticalSection
Вспомогательный поток:
ЕnterCriticalSection
DequeueWork // — занимает очень мало времени, потому не блокирует основной поток надолго
LeaveCriticalSection
SearchOrChangeData // — занимает 15 секунд, но основной поток не блокирует
Здравствуйте, ilnar, Вы писали:
I>2. автор сообщения недостаточно описал, что за общие данные и откуда и зачем тут очередь? если один поток заполняет очередь, а другой читает — это pool задач или потоков или все вместе. в том же codeproject найдете treadpool, и тому подобное. Если это очередь операций на модификацию — другое — тут очередь не нужно синхронизировать, а просто выполнить когда станут доступны данные на запись
Все приложение в упрощенном виде представляет виртуальный список. Основной поток — виртуальный список и интерфейс работы с ним. Дополнительный поток — вычитка данных с какогото источника (база данных, сеть и т.п.).
Заполнение списка выполняется в 2 шага:
1) В дополнительном потоке считываются и обрабатываются данные (ресурсоемкая процедура которая длится десятки секунд), когда данные подготовлены устанавливается флаг основному потоку, что пора их забрать.
2) Основной поток забирает данные (операция длится доли секунды) и устанавливает флаг что можно дальше дополнительному потоку вычитывать/обрабатывать данные.
И так происходит по циклу. Это уже реализовано. Все здесь очень просто вышло.
Теперь нужно добавить поиск в этот список. Сейчас добавил его в основной поток, но когда длится поиск (ресурсоемкая процедура длится до 15 секунд), то соответственно весь интерфейс блокируется и понятно что пользователь в это время ничего не может сделать.
Чтобы этого не происходило — решил выделить поиск во второй дополнительный поток (поток поиска). Т.е. чтобы когда нужно искать данные — основной поток дает команду потоку поиска на поиск, а сам дальше продолжает свою работу. При этом данные не должны изменяться. Когда поток поиска даст результат — дать возможность изменять данные.
Здесь кажется полностью описал задачу.
Все варианты которые я придумал по поводу потока поиска очень сложные. Думаю это можно решить попроще.
Здравствуйте, kondrik, Вы писали:
K>Здравствуйте, ilnar, Вы писали:
I>>2. автор сообщения недостаточно описал, что за общие данные и откуда и зачем тут очередь? если один поток заполняет очередь, а другой читает — это pool задач или потоков или все вместе. в том же codeproject найдете treadpool, и тому подобное. Если это очередь операций на модификацию — другое — тут очередь не нужно синхронизировать, а просто выполнить когда станут доступны данные на запись
K>Все приложение в упрощенном виде представляет виртуальный список. Основной поток — виртуальный список и интерфейс работы с ним. Дополнительный поток — вычитка данных с какогото источника (база данных, сеть и т.п.). K>Заполнение списка выполняется в 2 шага: K>1) В дополнительном потоке считываются и обрабатываются данные (ресурсоемкая процедура которая длится десятки секунд), когда данные подготовлены устанавливается флаг основному потоку, что пора их забрать. K>2) Основной поток забирает данные (операция длится доли секунды) и устанавливает флаг что можно дальше дополнительному потоку вычитывать/обрабатывать данные. K>И так происходит по циклу. Это уже реализовано. Все здесь очень просто вышло.
K>Теперь нужно добавить поиск в этот список. Сейчас добавил его в основной поток, но когда длится поиск (ресурсоемкая процедура длится до 15 секунд), то соответственно весь интерфейс блокируется и понятно что пользователь в это время ничего не может сделать. K>Чтобы этого не происходило — решил выделить поиск во второй дополнительный поток (поток поиска). Т.е. чтобы когда нужно искать данные — основной поток дает команду потоку поиска на поиск, а сам дальше продолжает свою работу. При этом данные не должны изменяться. Когда поток поиска даст результат — дать возможность изменять данные. K>Здесь кажется полностью описал задачу. K>Все варианты которые я придумал по поводу потока поиска очень сложные. Думаю это можно решить попроще.
зачем основному потоку проверять флаг и забирать данные? пусть данные ложит в список дополнительный поток сразу после обработки.
а другой поток может вести поиск в списке. чтобы надолго не блокировать, пусть перед поиском создает другой список с указателями на данные основного списка — слепок для работы, и обновления списка при работе со слепком уже не страшны, если нет удаления данных
дополнительный поток:
1. получает данные и обрабатывает их
2. эксклюзивно блокирует весь список или только изменяемую часть,
3. вносит данные
4. разблокирует блокировку, полученную на шаге 2
поток поиска:
1. блокирует весь список
2. снимает слепок списка (создает другой список с указателями на данные основного списка)
3. разблокирует блокировку из шага 1
4. производит поиск.
вот и получается, что список находится в блокировке очень малое время. годится обычная критическая секция
Здравствуйте, ilnar, Вы писали:
I>дополнительный поток: I>1. получает данные и обрабатывает их I>2. эксклюзивно блокирует весь список или только изменяемую часть, I>3. вносит данные I>4. разблокирует блокировку, полученную на шаге 2
I>поток поиска: I>1. блокирует весь список I>2. снимает слепок списка (создает другой список с указателями на данные основного списка) I>3. разблокирует блокировку из шага 1 I>4. производит поиск.
I>вот и получается, что список находится в блокировке очень малое время. годится обычная критическая секция
У меня список занимает гдето 16 Мб в памяти. И может занимать до 100 Мб. Если делать слепок — действительно получается все просто, но при таких объемах данных — память сильно будет расходоваться. Хорошо что у меня пока только поиск есть, а если придется прикручивать другую функциональность?. И тем более пока произведется поиск — данные могут сильно устареть. Могу позволить во время поиска — не обновлять данные — тогда все будет согласовано. Хотя над тем что ты предложил стоит подумать.
Здравствуйте, kondrik, Вы писали:
K>У меня список занимает гдето 16 Мб в памяти. И может занимать до 100 Мб. Если делать слепок — действительно получается все просто, но при таких объемах данных — память сильно будет расходоваться. Хорошо что у меня пока только поиск есть, а если придется прикручивать другую функциональность?. И тем более пока произведется поиск — данные могут сильно устареть. Могу позволить во время поиска — не обновлять данные — тогда все будет согласовано. Хотя над тем что ты предложил стоит подумать.
слепок — не полная копия списка. если каждый объект из списка занимает по килобайту, то список и слепок состоит из 16 тысяч или 100 тысяч объектов. все же не все копируется.
если есть боязнь, то можно чуть изменить. пусть дополнительный поток обрабатывает данные и вносит результат в "пул модификаций": добавить объект в список, изменить список, ....
поток поиска или других операций блокирует пул модификаций и вносит эти модификации в список, разблокируется, а потом работает со списком
дополнительный поток:
1. получает данные и обрабатывает их
2. эксклюзивно блокирует пул модификаций
3. вносит данные в пул модификаций
4. разблокирует пул модификаций
поток поиска:
1. эксклюзивно блокирует пул модификаций
2. вносит модификации из пула модификаций в список
4. разблокирует пул модификаций
4. производит поиск в списке
список один, не копируется, не блокируется, имеет корректное состояние. Что касается устарения во время поиска, в твоем случае ты даже не смог бы узнать об устарении, поиск проводил бы в таком же списке, блокируя при этом прием и обработку данных
K>Здравствуйте, ilnar, Вы писали:
I>>дополнительный поток: I>>1. получает данные и обрабатывает их I>>2. эксклюзивно блокирует весь список или только изменяемую часть, I>>3. вносит данные I>>4. разблокирует блокировку, полученную на шаге 2 I>>поток поиска: I>>1. блокирует весь список I>>2. снимает слепок списка (создает другой список с указателями на данные основного списка) I>>3. разблокирует блокировку из шага 1 I>>4. производит поиск.
K>У меня список занимает гдето 16 Мб в памяти. И может занимать до 100 Мб. Если делать слепок — действительно получается все просто,
У меня вопрос по слепку (список указателей на элементы исходного списка). Объясните, пожалуйста, смысл создания слепка в контексте потоко-безопасности и целостности исходного списка.
Спасибо.
Здравствуйте, Didro, Вы писали:
D>У меня вопрос по слепку (список указателей на элементы исходного списка). Объясните, пожалуйста, смысл создания слепка в контексте потоко-безопасности и целостности исходного списка. D>Спасибо.
целостность исходного списка достигается блокировками во время работы с ней. если данные в исходный список только добавляются, то указатели в слепке корректны. а потоко-безопасность слепка за счет того, что слепок будет собственностью только одного потока, например, список в стеке или в TLS
Здравствуйте, ilnar, Вы писали:
D>>У меня вопрос по слепку (список указателей на элементы исходного списка). Объясните, пожалуйста, смысл создания слепка в контексте потоко-безопасности и целостности исходного списка. I>целостность исходного списка достигается блокировками во время работы с ней. если данные в исходный список только добавляются, то указатели в слепке корректны. а потоко-безопасность слепка за счет того, что слепок будет собственностью только одного потока, например, список в стеке или в TLS
Извиняюсь — все равно не понял
Слепок(список указателей(не данных)) — фактически окно, опеределяющее границы в которых поток будет работать с исходным списком. Судя по приведенному алгоритму дополнительный поток блокирует основной список и вносит изменения, в это время поток поиска может работать со слепком = с основным списком => оба потока в одно и тоже время работают с основным списком — один его меняет, другой его читает(производит поиск). Какая же тут потоко-безопасность и целостность?
Т.е. фактически вопрос возник к этой фразе:
пусть перед поиском создает другой список с указателями на данные основного списка — слепок для работы, и обновления списка при работе со слепком уже не страшны, если нет удаления данных
Почему обновления списка не старшны ? Хорошо если так int-ы лежат в списке, а если сложная ссылочная структура — тогда параллельное чтение и модификация её элементов из разных потоков приведет к нарушению целостности. (извиняюсь, что так подробно, просто не могу понять, где я туплю)
Здравствуйте, Didro, Вы писали:
D>Здравствуйте, ilnar, Вы писали:
D>>>У меня вопрос по слепку (список указателей на элементы исходного списка). Объясните, пожалуйста, смысл создания слепка в контексте потоко-безопасности и целостности исходного списка. I>>целостность исходного списка достигается блокировками во время работы с ней. если данные в исходный список только добавляются, то указатели в слепке корректны. а потоко-безопасность слепка за счет того, что слепок будет собственностью только одного потока, например, список в стеке или в TLS
D>Извиняюсь — все равно не понял
ничего страшного, обязательно нужно понять, а не кивать как студент и потом ничего не делать, прийти перед днем сдачи и сказать что у тебя что-то есть, но это не оно и чуток не работает :D
D>Слепок(список указателей(не данных)) — фактически окно, опеределяющее границы в которых поток будет работать с исходным списком. Судя по приведенному алгоритму дополнительный поток блокирует основной список и вносит изменения, в это время поток поиска может работать со слепком = с основным списком => оба потока в одно и тоже время работают с основным списком — один его меняет, другой его читает(производит поиск). Какая же тут потоко-безопасность и целостность?
D>Т.е. фактически вопрос возник к этой фразе:
D>
D>пусть перед поиском создает другой список с указателями на данные основного списка — слепок для работы, и обновления списка при работе со слепком уже не страшны, если нет удаления данных
D>Почему обновления списка не старшны ? Хорошо если так int-ы лежат в списке, а если сложная ссылочная структура — тогда параллельное чтение и модификация её элементов из разных потоков приведет к нарушению целостности. (извиняюсь, что так подробно, просто не могу понять, где я туплю)
как я понял автора задачи, в список данные только добавляются. значит сами данные меняться не будут. меняются список, то что связано с организацией структуры данных под названием список. а он у нас у каждого свой — у потока поиска слепок, у дополнительного потока — основной список. значит надо синхронизировать только доступ к части список, а не данных.
допустим, что понадобилось менять данные. тогда лучше применять подход из другой ветки: единственный список данных и список/пул задач модификации основного списка. поток поиска применяет этот пул задач, что видимо, очень быстро, и занимается поиском в списке. никто больше модифицирует список и не читает во время модификации. тут нужен rwlock
скопирую и сюда с некоторым изменением на случай нескольких потоков типа поиска
дополнительный поток:
1. получает данные и обрабатывает их
2. блокирует на запись пул модификаций
3. вносит данные в пул модификаций
4. разблокирует пул модификаций
потоки типа поиска:
1. блокирует на чтение пул модификаций
2. блокирует на запись список
3. вносит модификации из пула модификаций в список
4. разблокирует список
5. разблокирует пул модификаций
6. блокирует на чтение список
7. производит поиск в списке
8. разблокирует список
если блокировки будут в описанном порядке, то дедлока не будет.
если нужно чтобы несколько потоков поиска не ожидали друг-друг, например, один на внесение изменений (блокировка на запись), когда другой заблокировал на чтение, можно пункт 2 изменить так:
потоки типа поиска:
1. блокирует на чтение пул модификаций
2. пробует блокировать на запись список, если не удается, переходит в п.5
3. вносит модификации из пула модификаций в список
4. разблокирует список
5. разблокирует пул модификаций
6. блокирует на чтение список
7. производит поиск в списке
8. разблокирует список
