Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 20
Меня всегда радуют такие топики. Все еще есть достойные статьи и тут. Но где обсуждение?
> Второй поток (стиратель) удаляет устаревшие объекты. Время от времени, первый поток пытается оперировать объектом, который второй поток пытается удалить. Это классический сценарий, который можно найти практически в любой многопоточной программе.
А можно пример? На самом деле непонятно.
Когда надо получить ссылку на объект из списка, лочим список. Когда надо удалить ссылку на объект из списка, лочим список. В общем, манипуляции со списком делаем под локом.
Объект удаляется, когда число ссылок на него становится равным нулю.
> А если его счетчик ссылок больше, чем один? В этом случае мы должны ждать, пока счетчик ссылок потоков не станет нулевым.
Зачем надо ждать? Если число ссылок больше, чем один, значит кто-то захватил объект. Вот когда он освбодит, будет проверено, есть ли еще ссылки не объект. Если нет, то объект удаляется.
Скорее всего я просто не понял сценарий.
А можно пример? На самом деле непонятно.
Когда надо получить ссылку на объект из списка, лочим список. Когда надо удалить ссылку на объект из списка, лочим список. В общем, манипуляции со списком делаем под локом.
Объект удаляется, когда число ссылок на него становится равным нулю.
> А если его счетчик ссылок больше, чем один? В этом случае мы должны ждать, пока счетчик ссылок потоков не станет нулевым.
Зачем надо ждать? Если число ссылок больше, чем один, значит кто-то захватил объект. Вот когда он освбодит, будет проверено, есть ли еще ссылки не объект. Если нет, то объект удаляется.
Скорее всего я просто не понял сценарий.
Насчет примеров — самые яркие из них это работа с данными в БД. Положим, в некоторой непродуманной архитектуре есть процесс 1, который периодически чистит таблицу, например вчерашние данные («DELETE FROM mytable WHERE mydate<SYSDATE-1»), а другой процесс 2, оперируя закешированными данными или непосредственно делая предварительную выборку данных захочет поменять какую-то строку, предполагаемую для удаления процессом 1. процесс 2 считывает данные, процесс 1 удаляет данные, процесс 2 пытается изменить удаленную строку. Упс. Это еще не худший вариант, ибо есть deadlock'и
Лочить весь список — не вариант в многопоточном приложении. Как и было сказано «Если все, что делает поток манипулятора — это поиск записей и их обработка, то поток стирателя просто не сможет получить доступ к структуре данных». Т.е. манипулятор в этом случае будет лочить список постоянно и без остановок.
Именно об этом и говорится в тексте. Если число ссылок больше чем один, значит объект еще пользуется каким-то процессом, мы его удалить не можем и потоку придется ждать его освобождения.
Можно еще, чтобы не ждать, реализовать callback на нулевое число ссылок, хотя в этом случае никто не гарантирует отсутствие дополнительных проблем.
Лочить весь список — не вариант в многопоточном приложении. Как и было сказано «Если все, что делает поток манипулятора — это поиск записей и их обработка, то поток стирателя просто не сможет получить доступ к структуре данных». Т.е. манипулятор в этом случае будет лочить список постоянно и без остановок.
Зачем надо ждать? Если число ссылок больше, чем один, значит кто-то захватил объект. Вот когда он освободит, будет проверено, есть ли еще ссылки не объект. Если нет, то объект удаляется.
Именно об этом и говорится в тексте. Если число ссылок больше чем один, значит объект еще пользуется каким-то процессом, мы его удалить не можем и потоку придется ждать его освобождения.
Можно еще, чтобы не ждать, реализовать callback на нулевое число ссылок, хотя в этом случае никто не гарантирует отсутствие дополнительных проблем.
Скорее всего я просто не понял сценарий.
Если кратко, то при наличии структуры объектов, лочить ее mutex'ом всю при операциях над объектами несколькими потоками — слишком накладно и может увеличить простои одного из процессов в бесконечность.
В этом смысле аналогией может быть работа общественной уборной.
Если при каждом заходе в уборную на 10 кабинок будет лочится вся уборная — вырастет огромная очередь.
А уборная должна периодически чиститься. И уборщица не знает заняты ли места в уборной или нет.
Заходящий в уборную должен оповестить других о занятости кабинки. Потому заходя в кабинку сигнализирует об этом (atomic counter). Не исключено, что он может туда зайти и не один, но выйти все равно должны когда-то все из кабинки и разлочить ее. Периодически в уборную заглядывает уборщица. И когда она видит, что все двери разлочены — оставляет знак перед входом об уборке (mutex) и чистит уборную.
Интересный подход с мютексом на весь список и счетчиком в каждом объекте, жаль что сугубо заточен под задачу где есть поток удалятор, и 1-N поток юзателей.
И я не очень понял и как получить (использовать) объект? получается мне нужно перед использованием объекта сделать что то вроде iterator->lock(), iterator->unlock()?
В принципе было бы логично и итераторы тогда для такой очереди сделать которые как смарт поинтеры работали бы. Но в этом случае нельзя полагаться на то что объект используется минуту. Тогда встает вопрос, а как это делать?
И я не очень понял и как получить (использовать) объект? получается мне нужно перед использованием объекта сделать что то вроде iterator->lock(), iterator->unlock()?
В принципе было бы логично и итераторы тогда для такой очереди сделать которые как смарт поинтеры работали бы. Но в этом случае нельзя полагаться на то что объект используется минуту. Тогда встает вопрос, а как это делать?
жаль что сугубо заточен под задачу где есть поток удалятор, и 1-N поток юзателей
да, можно еще сказать, что наличие объекта определяется единичным счетчиком, а остальные операции — счетчиком большим 1.
Можно еще обобщенно представить это в таком подобии псевдокода (разумеется, в оригинале объект сразу инициализируется в 1, как частный случай реализации):
eraser {
atomic++;
updater1 {
atomic++;
job();
atomic--;
}
updater2 {
...
}
atomic--;
}
Может, это натолкнет на мысли об альтернативном использовании. А какая именно схема интересна?
И я не очень понял и как получить (использовать) объект?
Похоже, автор статьи больше «затачивался» в ней на чистом Си, потому и не стал писать примеры C++.
Использование зависит от реализации. В этом смысле, думаю, мысль в правильном направлении — можно сделать шаблон аналогичный смарт поинтерам или даже наследоваться от какого-нибудь из них с перегрузкой для инкремента/декремента атомарного счетчика. Т.е. получается, что итератор будет модифицированным смарт поинтером. Но тут проблема — получается, что локинг будет при каждом обращении к поинтеру, потому iterator->lock()/unlock() вполне вариант. Можно еще как вариант сделать класс сессионности, лочащего и разлочивающего объект в своей зоне видимости.
Но в этом случае нельзя полагаться на то, что объект используется минуту.
На это точно не стоит полагаться. Какой-то из потоков может вовсе зависнуть.
Но в данном случае минута — относится больше к специфике задачи.
В остальном, можно рассмотреть, как вариант, сериализацию доступа к объекту (пул потоков).
Интересно, а чем не нравится реализация std::shared_ptr или boost::shared_ptr? Там в моменте, когда счетчик равен 0 автоматически удаляется объект и сам счетчик. Почему необходимо обязательно выжидать дополнительного момента и проверять объект через некоторое время, да еще и сравнивать timestamp?
интересно а как вы ее использовать собрались? Список в самом простом его представлении это структура вида
{
next*
prev*
data
}
когда вы удаляете элемент вам нужно изменить не один а три элемента. next у предыдущего должен указывать на следующий за удаляемым. prev следующего за удаляемым должен указывать на предыдущий перед удаляемым. И только потом уже можно удалять элемент.
Тут есть два вариант, либо лочить всю очередь. Либо, может быть, возможно придумать, как лочить только три объекта удаляемые, и те что слева справа от него. Но это крайне сложно, так как делать это по сути нужно атомарно. Но так же это будет офигенски многопоточная очередь.
{
next*
prev*
data
}
когда вы удаляете элемент вам нужно изменить не один а три элемента. next у предыдущего должен указывать на следующий за удаляемым. prev следующего за удаляемым должен указывать на предыдущий перед удаляемым. И только потом уже можно удалять элемент.
Тут есть два вариант, либо лочить всю очередь. Либо, может быть, возможно придумать, как лочить только три объекта удаляемые, и те что слева справа от него. Но это крайне сложно, так как делать это по сути нужно атомарно. Но так же это будет офигенски многопоточная очередь.
Насколько я понял, здесь речь идет о том, что у нас есть объекты в каком-то контейнере, например hashmap, правильно? Тогда рассмотрим следующее утверждение:
В этом случае потоку манипулятора приходится удерживать мьютекс заблокированным до тех пор, пока он не найдет объект и не обработает его.
Т.е. речь идет о том, что необходимо залочить весь контейнер, пока мы не найдем объект и не завершим операцию над ним. Так вот, это утверждение в корне ошибочно. Можно поступить следующим образом:
— лочим наш контейнер
— находим объект
— инкрементируем счетчик
— анлочим контейнер
— лочим объект
— работаем
— анлочим объект
— уменьшаем счетчик
— если счетчик==0 => удаляем
Как видно, эта последовательность решает нашу задачу без каких-либо проблем, которые связаны с дополнительным потоком и таймстемпами. Т.е. во время работы над объектом можно производить удаление и поиск объектов, а также их изменение. А вот проблема, которая действительно есть в статье: это то, что объект может быть использован двумя потоками одновременно. Как она решается?
В этом случае потоку манипулятора приходится удерживать мьютекс заблокированным до тех пор, пока он не найдет объект и не обработает его.
Т.е. речь идет о том, что необходимо залочить весь контейнер, пока мы не найдем объект и не завершим операцию над ним. Так вот, это утверждение в корне ошибочно. Можно поступить следующим образом:
— лочим наш контейнер
— находим объект
— инкрементируем счетчик
— анлочим контейнер
— лочим объект
— работаем
— анлочим объект
— уменьшаем счетчик
— если счетчик==0 => удаляем
Как видно, эта последовательность решает нашу задачу без каких-либо проблем, которые связаны с дополнительным потоком и таймстемпами. Т.е. во время работы над объектом можно производить удаление и поиск объектов, а также их изменение. А вот проблема, которая действительно есть в статье: это то, что объект может быть использован двумя потоками одновременно. Как она решается?
еще раз, вы не можете сделать
— если счетчик==0 => удаляем
не залочив весь список. Удаление объекта сказывается как минимум на предшествующем и последующем объекте. А если это ассоциативный контейнер то может и на всем списке.
А вот проблема, которая действительно есть в статье: это то, что объект может быть использован двумя потоками одновременно. Как она решается?
read-write блокировки. И ни как иначе.
— если счетчик==0 => удаляем
не залочив весь список. Удаление объекта сказывается как минимум на предшествующем и последующем объекте. А если это ассоциативный контейнер то может и на всем списке.
А вот проблема, которая действительно есть в статье: это то, что объект может быть использован двумя потоками одновременно. Как она решается?
read-write блокировки. И ни как иначе.
Можем. Только об этом надо написать немного подробнее.
В самом начале у нас объект есть в контейнере, счетчик равен 1. Когда мы его получаем из контейнера, то счетчик становится равным 2. Затем, например, мы его удаляем из контейнера, используя следующую последовательность:
— лочим контейнер
— удаляем элемент из контейнера, счетчик = 1
— анлочим контейнер
Затем когда счетчик становится равным нулю, то удаляем из памяти. Локи берутся на короткое время, поэтому можно не бояться проблем с производительностью. Все просто и понятно.
В самом начале у нас объект есть в контейнере, счетчик равен 1. Когда мы его получаем из контейнера, то счетчик становится равным 2. Затем, например, мы его удаляем из контейнера, используя следующую последовательность:
— лочим контейнер
— удаляем элемент из контейнера, счетчик = 1
— анлочим контейнер
Затем когда счетчик становится равным нулю, то удаляем из памяти. Локи берутся на короткое время, поэтому можно не бояться проблем с производительностью. Все просто и понятно.
Добавлю к предыдущему комментарию, что shared_ptr — не обеспечивает полного thread safety.
Как сказано в документации к последнему Boost 1.50:
В c++0x говорится о том же.
В целом же, основная проблема потокобезопасности shared_ptr в том, что его экземпляр — потокобезопасен, а объект, на который он ссылается — нет.
Как сказано в документации к последнему Boost 1.50:
Объекты shared_ptr обеспечивают тот же уровень потокобезопасности что и встроенные типы. Экземпляр shared_ptr-а может «считываться» одновременно несколькими потоками (доступ с использованием только константных операций). В различные экземпляры shared_ptr-а может производиться «запись» (доступ с использованием изменяемых операций, таких как оператор= или reset) одновременно несколькими потоками (даже если эти экземпляры — копии и разделяют внутри один и тот же счетчик ссылок).
Любые другие варианты одновременного доступа приводят к непредсказуемому поведению.
В c++0x говорится о том же.
В целом же, основная проблема потокобезопасности shared_ptr в том, что его экземпляр — потокобезопасен, а объект, на который он ссылается — нет.
А как эта проблема решается в статье? Т.е. вот я получил доступ к объекту, а как происходит понимание, что никто не может его изменить кроме меня?
в статье — не решается. да и статья не предназначалась быть панацеей.
как и было сказано выше Cupper — можно использовать для этой цели read()/write()-блокировки, но опять же — реализация зависит от задачи.
как и было сказано выше Cupper — можно использовать для этой цели read()/write()-блокировки, но опять же — реализация зависит от задачи.
Отлично! Тогда другой вопрос: раз в статье не решается, то почему shared_ptr должен это решать? Я всего лишь привел аналог того, что описано в статье, ни больше ни меньше.
в чистом виде полного thread safety для любых задач нельзя получить ни основываясь описанным в статье, ни с использованием shared_ptr.
у каждой из этих методов есть свои преимущества и недостатки.
задача статьи была не столько описать 100% решение, сколько раскрыть вариант логики работы со списком объектов пользуясь мьютексными и атомарными блокировками.
у каждой из этих методов есть свои преимущества и недостатки.
задача статьи была не столько описать 100% решение, сколько раскрыть вариант логики работы со списком объектов пользуясь мьютексными и атомарными блокировками.
недавно попалась хорошая презентация по java pdf, где расписаны некоторые приемы программирования без блокировок.
Спорно.
Начиная с «Мы можем поместить мьютекс в сам объект, но это создаст следующую дополнительную проблему.… Ой». Потому что решение этой проблемы описано чуть ниже «Как только поток стирателя решит удалить какой-либо объект, ему нужно сначала удалить его из структуры данных», только почему-то это решение стоит под заголовком «атомарные переменные». То есть проблема (общая) описана для мьютексов, а ее решение (общее) — для атомарных переменных. Не очень хорошо так передергивать.
И это «RCU» решение. RCU — это Read-Copy-Update. Что-то я не заметил, что там куда копируется в авторском варианте. При чем тут RCU?
Начиная с «Мы можем поместить мьютекс в сам объект, но это создаст следующую дополнительную проблему.… Ой». Потому что решение этой проблемы описано чуть ниже «Как только поток стирателя решит удалить какой-либо объект, ему нужно сначала удалить его из структуры данных», только почему-то это решение стоит под заголовком «атомарные переменные». То есть проблема (общая) описана для мьютексов, а ее решение (общее) — для атомарных переменных. Не очень хорошо так передергивать.
И это «RCU» решение. RCU — это Read-Copy-Update. Что-то я не заметил, что там куда копируется в авторском варианте. При чем тут RCU?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Подсчет ссылок атомарными переменными в C/C++ и GCC