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

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

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

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

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

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

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

S>>1. Есть нехилый шанс отхватить деадлок.
H>Пример ситуации приведи?
Одновременные операции над более чем одним элементом. Например:.

Поток 1:
a+=b

Поток 2:
b+=a

Чем сложнее объекты и чем больше между ними зависимостей — тем выше наши шансы

S>>3. RW-лок нужен в любом случае — грязное чтение весьма опасная штука.
H>Вот иллюстрация решения:
Ага, я просто протормозил с выделенным.

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

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

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

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

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

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

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

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

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

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

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

Здравствуйте, 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();
}

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

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

S>>>1. Есть нехилый шанс отхватить деадлок.
H>>Пример ситуации приведи?
S>Одновременные операции над более чем одним элементом. Например:.

S>

S>Поток 1:
S>a+=b

S>Поток 2:
S>b+=a
S>

S>Чем сложнее объекты и чем больше между ними зависимостей — тем выше наши шансы

Да, все верно, но к сожалению ТС ничего о природе объектов и связях не рассказывает.

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

MD>Возьмите те же СУБД для примера. В таблице может быть милионо-милиард записей. Но два запроса смогут читать/писать её одновременно, при определенных условиях (мы говорим тут про блокировочники типа MS SQL, а не версионники а-ля Interbase). Возможность эта обусловлена тем, что блокировка в СУБД изначально ставится на страницу (группа из одной или более строк таблицы) — если два параллельно исполняемых запроса захотят данные, принадлежащие одной и той же странице, то "кто первым встал, того и тапки", второй ждёт. Если нет — то доступ будет тоже параллельным, т.к. каждый запрос работает со своей страницей/страницами данных. Лишь в самых тяжелых случаях СУБД расширяет блокировку до всей таблицы целиком.

MD>Т.е. Ваша задача — перепроектировать свою задачу так, чтобы она допускала разбиение всего множества объектов на страницы/пулы/etc — назовите как хотите. И чтобы синхронизация доступа шла на уровне этой страницы/пула/etc.
Вообще-то, RDBMS типа MS SQL умеют также работать с блокировками на уровне строки таблицы. Поэтому, перепроектирования задачи здесь не требуется.

Требуется сделать менеджер блокировок. Который не будет требовать предварительного создания отдельного объекта блокировки на каждый элемент коллекции.

Реализация страничной или какой другой структуры нужна для оптимизации менеджера блокировок, чтобы в ситуациях, когда одна транзакция меняет много строк, не приходилось создавать слишком много блокировок.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А что именно-то ? Время квантуется равными порциями для потоков одинакового приоритета. Играть с повышением приоритета самому — ясно, что будет иначе. А priority boost сам по себе не возникает. Так что все правильно.

H>Да, все верно, но к сожалению ТС ничего о природе объектов и связях не рассказывает.
Не ТС, TS

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

H>>Да, все верно, но к сожалению ТС ничего о природе объектов и связях не рассказывает.
А>Не ТС, TS

Чем вам не нравится "топикстартер"?

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

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

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

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

PD>А что именно-то ? Время квантуется равными порциями для потоков одинакового приоритета. Играть с повышением приоритета самому — ясно, что будет иначе. А priority boost сам по себе не возникает. Так что все правильно.

Плюс спящий на примитиве синхронизации поток практически бесплатен для системы — так что, при спящих четырёх, пятый будет в самом деле работать быстрее в соло (с учетом, что все эти пять потоков привязаны на одно ядро).

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

1. А если создавать объекты синхронизации когда они понадобяться и удалять когда никто к объекту не обращается? Можно какой нить пул организовать.

2. Если в объект добавить 4 байта, и замутить свою синхронизацию, накладно?

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

vf>1. А если создавать объекты синхронизации когда они понадобяться и удалять когда никто к объекту не обращается? Можно какой нить пул организовать.

vf>2. Если в объект добавить 4 байта, и замутить свою синхронизацию, накладно?
Да... к этому я и пришел пока...
А почему 4 байта? 2 бит вроде должно хватить?

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

vf>>1. А если создавать объекты синхронизации когда они понадобяться и удалять когда никто к объекту не обращается? Можно какой нить пул организовать.

ИМХО, это более универсальный подход. Хотя тут по памяти может и дороже выйти, смотря как-где объекты храняться... а указатели тоже имееют размер.

vf>>2. Если в объект добавить 4 байта, и замутить свою синхронизацию, накладно?
А>Да... к этому я и пришел пока...
А>А почему 4 байта?

Я то просто написал чтобы под Interlocked подходило.

А>2 бит вроде должно хватить?

Это зависит... 2 бита как-то маловато, один читатель — один писатель? По идее если читателей несколько, наверное для них нужен какой нить счетчик.

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

vf>Это зависит... 2 бита как-то маловато, один читатель — один писатель? По идее если читателей несколько, наверное для них нужен какой нить счетчик.

Наверное 3 бита для 5 потоков. А приостанавливать поток как, Sleep?! Не очень эстетично

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