локинг списков
Тогда надо что-нибудь вроде:
взять мьютекс A
взять мьютекс n-1
взять мьютекс n+1
отдать мьютекс A
Ну скорее всего не так напрямую, а что-нибудь вроде реализации общего семафора с использованием только двоичных.
взять мьютекс A
взять мьютекс n-1
взять мьютекс n+1
отдать мьютекс A
Ну скорее всего не так напрямую, а что-нибудь вроде реализации общего семафора с использованием только двоичных.
Тогда надо что-нибудь вроде:
взять мьютекс A
взять мьютекс n-1
взять мьютекс n+1
отдать мьютекс A
Тред 1 берет мьютекс n |
| Тред 2 берет мьютекс n - 1
Тред 1 блокируется |
на взятии n-1 |
| Тред 2 берет n - 2
| Тред 2 блокируется на n
deadlock налицо
Ну скорее всего не так напрямую, а что-нибудь вроде реализации общего семафора с использованием только двоичных.Не понял.
Перед тем как взять n или n-1 тред берёт общий на список мьютекс A.
Ну в первом посте этот вариант отметался как сильно снижающий производительность.
Если дальше будет производиться работа с этими элементами, то в это время другие уже смогут нормально работать. Неужели функции захвата настолько медленные?
А то как же ты ещё хочешь их разделить от доступа в одно место? Может и можно как-нибудь по-другому, но это скорее всего будет настолько извратно, что оно будет тормозить другим местом.
А то как же ты ещё хочешь их разделить от доступа в одно место? Может и можно как-нибудь по-другому, но это скорее всего будет настолько извратно, что оно будет тормозить другим местом.
Я понял. Брать мьютекс списка, брать мьютексы элементов, отдавать мьютекс списка. Я подумаю об этом.
, это стандартное решение или ты его придумал?
Вообще на ВМК есть лекции на эту тему?
, это стандартное решение или ты его придумал?
Вообще на ВМК есть лекции на эту тему?
> стандартное решение или ты его придумал?
маза ты не описал, как собираешься работать с элементами списка,
точнее как организовывать одновременный доступ к элементам: конкурентное чтение, запись, удаление
думаю, оптимальное решение будет зависить от этого
маза ты не описал, как собираешься работать с элементами списка,
точнее как организовывать одновременный доступ к элементам: конкурентное чтение, запись, удаление
думаю, оптимальное решение будет зависить от этого
При удаление/добавление элементов списков блокировать соседние элементы, после действий с соседей снимай блокировку.
Ради интереса посмотри лекции Кузнецова по BD(там есть про проблему паралельной работы)
Ради интереса посмотри лекции Кузнецова по BD(там есть про проблему паралельной работы)
Удаление и вставление. Если бы только чтение или запись, то вопросов бы не возникало - мьютекс на каждый элемент и все.
При удаление/добавление элементов списков блокировать соседние элементы, после действий с соседей снимай блокировку.Я не вижу последовательности при которой не будет deadlock.
Ради интереса посмотри лекции Кузнецова по BD(там есть про проблему паралельной работы)Где их взять?
Не замечаешь?
Смотри: чтобы например что-то вставить, нужно сначала иметь ссылку на соседний элемент.
Значит, нужно знать, что этот соседний элемент из другого треда никто не удалит,
пока ты с ним разбираешься. Значит, ты уже какой-то лок держишь, соотвественно уже
не в любом порядке можешь брать.
А может, у тебя там подсчёт ссылок с атомарными изменениями счётчика - тогда другое дело.
Смотри: чтобы например что-то вставить, нужно сначала иметь ссылку на соседний элемент.
Значит, нужно знать, что этот соседний элемент из другого треда никто не удалит,
пока ты с ним разбираешься. Значит, ты уже какой-то лок держишь, соотвественно уже
не в любом порядке можешь брать.
А может, у тебя там подсчёт ссылок с атомарными изменениями счётчика - тогда другое дело.
приведи пример : deadlock.
ftp://cradle/Upload/Temp/СУБД.doc ~47 стр
ftp://cradle/Upload/Temp/СУБД.doc ~47 стр
Смотри: чтобы например что-то вставить, нужно сначала иметь ссылку на соседний элемент.Вообще-то эта мысль проходит через весь тред и именно из за неё я вопрос и задал.
Значит, нужно знать, что этот соседний элемент из другого треда никто не удалит,
пока ты с ним разбираешься. Значит, ты уже какой-то лок держишь, соотвественно уже
не в любом порядке можешь брать.
Мысль в том, что ты недостаточно описал задачу для того, чтобы можно было указать на оптимальное решение.
Какое отношение имеют лекции по СУБД к данному вопросу?
Да, элементы будут удаляться и вставляться. Если бы это было не так, то задача не вызвала бы у меня трудностей.
в субд проблемы паралельного использования нет!
Поздравляю.
Поздравляю.
в субд проблемы паралельного использования нет!Проблемы парраллельного использования есть в ГЗшном блоке, где один проездной на двоих. Но решаются они не мьютексами. И не транзакциями.
Я не понимаю, ты мне предлагаешь просто почитать интересные лекции или переносить свои данные в SQL и решать проблему совместного использования транзакциями?
> Проблемы парраллельного использования есть в ГЗшном блоке, где один проездной на двоих.
> Но решаются они не мьютексами. И не транзакциями.
И нет гарантий, что он не будет проёбан.
> Но решаются они не мьютексами. И не транзакциями.
И нет гарантий, что он не будет проёбан.
Пусть тебе надо удалить элимент из списка.
На этот элемент ссылаются 2 соседних элемента.
Ты блокируешь элемент(удаляемый) типом блокировки X(S-элемент читается, X-изменяется он не должен быть блокирован. Соседние элементы блокируешь XI- нельзя двигаться по ссылкам этих элементов, а читать данные из них можно. Удаляешь элемент и правишь ссылки соседних элементов. Снимаешь блокировку XI.
Все.
На этот элемент ссылаются 2 соседних элемента.
Ты блокируешь элемент(удаляемый) типом блокировки X(S-элемент читается, X-изменяется он не должен быть блокирован. Соседние элементы блокируешь XI- нельзя двигаться по ссылкам этих элементов, а читать данные из них можно. Удаляешь элемент и правишь ссылки соседних элементов. Снимаешь блокировку XI.
Все.
В каком порядке блокируются соседние элементы?
не пренципиально.
Например сначала справа, потом слева.
Если надо удалить два соседних элемента(одновременно перешли в X то левый при определение, что провый сосед в блокировке X, снимает с себя X(заменяет на S напр) и через таймаут пытается снова удалить.
Например сначала справа, потом слева.
Если надо удалить два соседних элемента(одновременно перешли в X то левый при определение, что провый сосед в блокировке X, снимает с себя X(заменяет на S напр) и через таймаут пытается снова удалить.
Если два треда лочат элементы n и n+1, то дальше они взаимно блокируются на лоченье соседей.
читай строчки 3,4,5
Если элемент в S, то его можно лочить в XI
Если элемент в S, то его можно лочить в XI
хехе
мне бы ваши проблемы.
мне бы ваши проблемы.
Ну так что?
субд не рулит?
субд не рулит?
Я пока доделаю с локингом целого списка (в моём случае не все тривиально, потому что есть три списка логически связанные друг с другом а потом уже буду заниматься оптимизацией. Тогда перечитаю твои посты и раскритикую
P.S. И причем здесь СУБД?
P.S. И причем здесь СУБД?
Потому-что в субд тоже есть проблема блокирования и оттуда можно почерпнуть идеи для твоей реализации. Все что я предлагал основано на организации в system R. Если ты не знаешь как что-то делать, то либо сам придумывай, либо ищи того кто решел уже эту проблему.
Если у тебя зависимые списки, то в зависимости от их связи надо смотреть как блокировать зависимые.
P.S. А критика полезная штука, если она обосновона.
Если у тебя зависимые списки, то в зависимости от их связи надо смотреть как блокировать зависимые.
P.S. А критика полезная штука, если она обосновона.
Оставить комментарий
sergey_m
Есть список, для простоты будем считать что слинкованный в двух направлениях. Есть два треда, которые могут вставлять и выдергивать из списка элементы. Вопрос состоит в том, как организовать локинг. Если защищать мьютексом сам список, то получается большая потеря производительности. Практически никакого преимущества перед синхронной программой.Первая мысль такая: запихнуть мьютекс в каждый элемент списка и при удалении брать мьютексы предыдущего и последующего. Сразу встает вопрос в каком порядке их брать? Ведь если брать всегда "сверху-вниз", то получится dead lock если один тред будет работать с элементом n, а второй с элементом n+2.
P.S. Интересует более общая задача, не только двунаправленный список, но и все что есть в sys/queue.h