Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!

Здравствуйте, Аноним, Вы писали:

А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.

Возможно ли разделить ответственность за объекты между потоками?
Т.е. потоки будут работать только с непересекающимися подмножествами основного множества.

Здравствуйте, hardcase, Вы писали:

H>Здравствуйте, Аноним, Вы писали:

А>>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.

H>Возможно ли разделить ответственность за объекты между потоками?
H>Т.е. потоки будут работать только с непересекающимися подмножествами основного множества.
Нет это абсолютно невозможно.

Здравствуйте, Аноним, Вы писали:

А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!

В теории процессорное время делится равномерно между потоками, поэтому если 4 потока стоят, пятый работает быстрее(в идеале потери скорости нет).
Почему просто не использовать глобальный lock для всех объектов?

Здравствуйте, Аноним, Вы писали:

H>>Возможно ли разделить ответственность за объекты между потоками?
H>>Т.е. потоки будут работать только с непересекающимися подмножествами основного множества.
А>Нет это абсолютно невозможно.

Хорошо, переформулирую идею, которая была в вопросе.

Я так понял что синхронизация нужна далеко не всегда — объектов слишком много, таким образом ее нужно производить не всегда.
Если на основании некоторого признака разделить объекты между потоками, то обращение к "своим" объектам потока происходит без синхронизации, а обращение к "чужим" — с ней. Это в некотором смысле похоже на NUMA архитектуру памяти.

Здравствуйте, Аноним, Вы писали:

А>В теории процессорное время делится равномерно между потоками
В какой именно теории об этом сказано?

Здравствуйте, hardcase, Вы писали:
H>Я так понял что синхронизация нужна далеко не всегда — объектов слишком много, таким образом ее нужно производить не всегда.
H>Если на основании некоторого признака разделить объекты между потоками, то обращение к "своим" объектам потока происходит без синхронизации, а обращение к "чужим" — с ней. Это в некотором смысле похоже на NUMA архитектуру памяти.
Нельзя... в данном случае.

Здравствуйте, Аноним, Вы писали:

А>Нельзя... в данном случае.

Т.е. у объектов совсем нет идентификаторов/хэшей?

H>Т.е. у объектов совсем нет идентификаторов/хэшей?
Есть идентификаторы.

Здравствуйте, Аноним, Вы писали:

А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!

Вы собираетесь держать все эти объекты в памяти постоянно?
Вам не нужно сохранять состояние объектов на диске(например при перезапуске)?
Может быть можно воспользоваться услугами СУБД(конкурирующие транзакции, кеширование).

Здравствуйте, HowardLovekraft, Вы писали:

HL>Здравствуйте, Аноним, Вы писали:

А>>В теории процессорное время делится равномерно между потоками
HL>В какой именно теории об этом сказано?

Например, у Соломона-Руссиновича. Если не играть с приоритетами потоков и не использовать priority boost явно или неявно, то это именно так.

Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Если
Вот именно, что "если"...

Здравствуйте, Аноним, Вы писали:

А>Есть миллиард объектов с которыми работает 5 потоков. Читают из них, пишут в них.
А>Понятно, что создавать миллиарт ReadWrite lockов накладно. Лучше бы их было по числу потоков... Вобще как решаются данные задачи и нет ли каких-то наработок. Любые предложиния и варианты велком!

Придётся писать своё. Например, завести словарик: <id ресурса, [список читающих потоков|пишущий поток]>. После чего словарик немедленно станет узким местом

Этап 2 (правильно): Вывернуть словарь наизнанку — для каждого потока завести списки читаемых/записываемых объектов. Для доступа к спискам — тож r/w lock.

Этап 2б (не всегда правильно): блокировать не отдельные ресурсы, а их диапазоны. Получаем ещё больше простоев из-за блокировок и повышенный шанс отхватить deadlock.

Этап 3: выкинуть велосипед и попробовать TPL, поплеваться и вернуться к велосипеду.

Здравствуйте, Аноним, Вы писали:

H>>Т.е. у объектов совсем нет идентификаторов/хэшей?
А>Есть идентификаторы.

Ответственность за объекты можно разделить простой мат.форумлой вроде: obj.ID % ThreadCount.
Каждому потоку необходимо знать его идентификатор, с каждым потоком нужно связать единственный ReadWrite-лок.
Если объект "свой" (ID потока = obj.ID % ThreadCount), то мы обращаемся с объектом в Read-режиме, если объект оказался "чужим", то получаем RW-лок того потока и работаем с объектом в режиме Write.

Здравствуйте, hardcase, Вы писали:

Собственно это и есть частный случай блокировки диапазонов.

Здравствуйте, Аноним, Вы писали:

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-лок нужен в любом случае — грязное чтение весьма опасная штука.

Вот иллюстрация решения:

var prtitionID = Partition(obj);

if(thisThreadID == prtitionID)
{
    thisThreadLock.EnterReadLock();
    
    DoWork(obj);
    
    thisThreadLock.ExitReadLock();
}
else
{
    var otherThreadLock = threadLocs[prtitionID];

    otherThreadLock.EnterWriteLock();
    
    DoWork(obj);
    
    otherThreadLock.ExitWriteLock();
}

Здравствуйте, 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.