Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!
Здравствуйте, Аноним, Вы писали:
А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
Возможно ли разделить ответственность за объекты между потоками?
Т.е. потоки будут работать только с непересекающимися подмножествами основного множества.
/* иЗвиНите зА неРовнЫй поЧерК */
Re[2]: Синхронизация и большое кол-во ресурсов
От:
Аноним
Дата:
10.11.10 07:19
Оценка:
Здравствуйте, hardcase, Вы писали:
H>Здравствуйте, Аноним, Вы писали:
А>>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
H>Возможно ли разделить ответственность за объекты между потоками? H>Т.е. потоки будут работать только с непересекающимися подмножествами основного множества.
Нет это абсолютно невозможно.
Re: Синхронизация и большое кол-во ресурсов
От:
Аноним
Дата:
10.11.10 07:32
Оценка:
Здравствуйте, Аноним, Вы писали:
А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них. А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!
В теории процессорное время делится равномерно между потоками, поэтому если 4 потока стоят, пятый работает быстрее(в идеале потери скорости нет).
Почему просто не использовать глобальный lock для всех объектов?
Здравствуйте, Аноним, Вы писали:
H>>Возможно ли разделить ответственность за объекты между потоками? H>>Т.е. потоки будут работать только с непересекающимися подмножествами основного множества. А>Нет это абсолютно невозможно.
Хорошо, переформулирую идею, которая была в вопросе.
Я так понял что синхронизация нужна далеко не всегда — объектов слишком много, таким образом ее нужно производить не всегда.
Если на основании некоторого признака разделить объекты между потоками, то обращение к "своим" объектам потока происходит без синхронизации, а обращение к "чужим" — с ней. Это в некотором смысле похоже на NUMA архитектуру памяти.
Здравствуйте, Аноним, Вы писали:
А>В теории процессорное время делится равномерно между потоками
В какой именно теории об этом сказано?
Re[4]: Синхронизация и большое кол-во ресурсов
От:
Аноним
Дата:
10.11.10 08:01
Оценка:
Здравствуйте, hardcase, Вы писали: H>Я так понял что синхронизация нужна далеко не всегда — объектов слишком много, таким образом ее нужно производить не всегда. H>Если на основании некоторого признака разделить объекты между потоками, то обращение к "своим" объектам потока происходит без синхронизации, а обращение к "чужим" — с ней. Это в некотором смысле похоже на NUMA архитектуру памяти.
Нельзя... в данном случае.
Здравствуйте, Аноним, Вы писали:
А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них. А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!
Вы собираетесь держать все эти объекты в памяти постоянно?
Вам не нужно сохранять состояние объектов на диске(например при перезапуске)?
Может быть можно воспользоваться услугами СУБД(конкурирующие транзакции, кеширование).
Здравствуйте, HowardLovekraft, Вы писали:
HL>Здравствуйте, Аноним, Вы писали:
А>>В теории процессорное время делится равномерно между потоками HL>В какой именно теории об этом сказано?
Например, у Соломона-Руссиновича. Если не играть с приоритетами потоков и не использовать priority boost явно или неявно, то это именно так.
Здравствуйте, Аноним, Вы писали:
А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них. А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!
Придётся писать своё. Например, завести словарик: <id ресурса, [список читающих потоков|пишущий поток]>. После чего словарик немедленно станет узким местом
Этап 2 (правильно): Вывернуть словарь наизнанку — для каждого потока завести списки читаемых/записываемых объектов. Для доступа к спискам — тож r/w lock.
Этап 2б (не всегда правильно): блокировать не отдельные ресурсы, а их диапазоны. Получаем ещё больше простоев из-за блокировок и повышенный шанс отхватить deadlock.
Этап 3: выкинуть велосипед и попробовать TPL, поплеваться и вернуться к велосипеду.
Здравствуйте, Аноним, Вы писали:
H>>Т.е. у объектов совсем нет идентификаторов/хэшей? А>Есть идентификаторы.
Ответственность за объекты можно разделить простой мат.форумлой вроде: obj.ID % ThreadCount.
Каждому потоку необходимо знать его идентификатор, с каждым потоком нужно связать единственный ReadWrite-лок.
Если объект "свой" (ID потока = obj.ID % ThreadCount), то мы обращаемся с объектом в Read-режиме, если объект оказался "чужим", то получаем RW-лок того потока и работаем с объектом в режиме Write.
Здравствуйте, Аноним, Вы писали:
H>>Т.е. у объектов совсем нет идентификаторов/хэшей? А>Есть идентификаторы.
Дык попробуйте тогда сделать некую функцию f, чтобы f(id) однозначно давало номер потока. Тогда можно попробовать раздать ваш мульён объектов потокам, о чём говорил hardcase несколькими уровнями выше.
Если в такой постановке задача не решается — возможно, надо сделать пару шагов назад и пересмотреть решение, ибо если нужна потребность в столь "мелкозернистой" синхронизации — Вы явно перекладываете ответственность с хранилища объектов на использующих его клиентов.
Возьмите те же СУБД для примера. В таблице может быть милионо-милиард записей. Но два запроса смогут читать/писать её одновременно, при определенных условиях (мы говорим тут про блокировочники типа MS SQL, а не версионники а-ля Interbase). Возможность эта обусловлена тем, что блокировка в СУБД изначально ставится на страницу (группа из одной или более строк таблицы) — если два параллельно исполняемых запроса захотят данные, принадлежащие одной и той же странице, то "кто первым встал, того и тапки", второй ждёт. Если нет — то доступ будет тоже параллельным, т.к. каждый запрос работает со своей страницей/страницами данных. Лишь в самых тяжелых случаях СУБД расширяет блокировку до всей таблицы целиком.
Т.е. Ваша задача — перепроектировать свою задачу так, чтобы она допускала разбиение всего множества объектов на страницы/пулы/etc — назовите как хотите. И чтобы синхронизация доступа шла на уровне этой страницы/пула/etc.
Здравствуйте, hardcase, Вы писали:
H>Ответственность за объекты можно разделить простой мат.форумлой вроде: obj.ID % ThreadCount. H>Каждому потоку необходимо знать его идентификатор, с каждым потоком нужно связать единственный ReadWrite-лок. H>Если объект "свой" (ID потока = obj.ID % ThreadCount), то мы обращаемся с объектом в Read-режиме, если объект оказался "чужим", то получаем RW-лок того потока и работаем с объектом в режиме Write.
[КО]
1. Есть нехилый шанс отхватить деадлок.
2. Число потоков не должно меняться.
3. RW-лок нужен в любом случае — грязное чтение весьма опасная штука.
[/КО]
Здравствуйте, Sinix, Вы писали:
S>Здравствуйте, hardcase, Вы писали:
H>>Ответственность за объекты можно разделить простой мат.форумлой вроде: obj.ID % ThreadCount. H>>Каждому потоку необходимо знать его идентификатор, с каждым потоком нужно связать единственный ReadWrite-лок. H>>Если объект "свой" (ID потока = obj.ID % ThreadCount), то мы обращаемся с объектом в Read-режиме, если объект оказался "чужим", то получаем RW-лок того потока и работаем с объектом в режиме Write.
S>1. Есть нехилый шанс отхватить деадлок.
Пример ситуации приведи?
S>2. Число потоков не должно меняться.
Да.
S>3. RW-лок нужен в любом случае — грязное чтение весьма опасная штука.
Здравствуйте, HowardLovekraft, Вы писали:
HL>Здравствуйте, Pavel Dvorkin, Вы писали:
PD>>Если HL>Вот именно, что "если"...
А что именно-то ? Время квантуется равными порциями для потоков одинакового приоритета. Играть с повышением приоритета самому — ясно, что будет иначе. А priority boost сам по себе не возникает. Так что все правильно.
Здравствуйте, hardcase, Вы писали:
S>>1. Есть нехилый шанс отхватить деадлок. H>Пример ситуации приведи?
Одновременные операции над более чем одним элементом. Например:.
Поток 1:
a+=b
Поток 2:
b+=a
Чем сложнее объекты и чем больше между ними зависимостей — тем выше наши шансы
S>>3. RW-лок нужен в любом случае — грязное чтение весьма опасная штука. H>Вот иллюстрация решения:
Ага, я просто протормозил с выделенным.
Если объект "свой" (ID потока = obj.ID % ThreadCount), то мы обращаемся с объектом в Read-режиме, если объект оказался "чужим", то получаем RW-лок того потока и работаем с объектом в режиме Write.