У нас есть некоторый диапазон чисел от 0 до N, надо написать две функции int alloc() и free(int). Первая выбирает один из свободных идентификаторов из диапазона [0, N), а вторая соответственно — «возвращает» его для повторного использования(полагаем, что число N достаточно мало, что бы идентификаторы могли закончится если их не возвращать, но больше чем число выделенных в каждый конкретный момент времени идентификаторов). При этом на «нижнем уровне» у нас есть только DHT. Нету блокировок, и, кроме того, от алгоритмов требуется отказоустойчивость — если какой-то из узлов кластера «сложится» во время выполнения алгоритма поведение системы должно быть предсказуемо. Если задача интересна, а также интересно узнать почему отказоустойчивый сервис с такой сигнатурой невозможно корректно использовать, и как надо исправить сигнатуру что бы это стало возможно — добро пожаловать под кат.
Рубрика «concurrency» - 8
Failsafe resource allocator over DHT
2013-04-17 в 19:49, admin, рубрики: api, big data, concurrency, DHT, метки: concurrency, DHTJava: executor с уплотнением по ключам
2013-03-11 в 7:24, admin, рубрики: concurrency, data structures, java, multithreading, метки: concurrency, data structures, java, multithreading
Существует типичная проблема в большом классе задач, которая возникает при обработке потока сообщений:
— нельзя пропихнуть большого слона через маленькую трубу, или другими словами, обработка сообщений не успевает «проглотить» все сообщения.
При этом существуют некоторые ограничения на поток данных:
- поток не равномерный и состоит из событий разного типа
- количество типов событий заранее не известно, но некоторое конечное число
- каждый тип события имеет свою актуальность во времени
- все типы событий имеют равный приоритет
На диаграмме приведён пример разрешения проблемы: нагребатор(tm), работающий на нитке T1, в то время как разгребатор(tm) работает на нитке T2
- за время обработки события типа A успевают прийти новые события как типа B, так и A
- после обработки события типа B необходимо обработать наиболее актуальное событие типа A
Т.о. стоит задача о выполнении задач по ключу, так, что выполняется только самая актуальная из всех задач по данному ключу.
На суд публике представляется созданный нами ThrottlingExecutor.
Замечание терминологии: stream есть поток данных, тогда как thread есть нитка или нить выполнения. И не стоит путать потоки с нитками.
Замечание 1: проблема осложняется ещё тем, что может быть несколько нагребаторов(tm), при этом каждый нагребатор(tm) может порождать только события одного типа; с другой стороны есть потребность в нескольких (конечно же, для простоты можно выбрать N=1) разгребаторах(tm).
Замечание 2: мало того, что данный код должен работать в многопоточной (конкурентной) среде — т.е то самое множество нагребаторов(tm) — разгребаторов(tm), код должен работать с максимальной производительностью и низкими latency. Резонно к этим всем качествам добавить ещё и свойство garbage less.
И почти в каждом проекте так или иначе возникает эта задача, и каждый её решает по разному, но все они либо не эффективны, либо медленны, либо и то, и другое вместе взятое.
Пятничная история про synchronized-методы в классе Thread
2013-02-15 в 20:52, admin, рубрики: concurrency, java, метки: concurrency, java Недавно я наткнулся на интересную особенность синхронизации на классе Thread. Я создал класс, наследующий Thread и использовал в нем паттерн lock object для внутренней синхронизации. В какой-то момент мне показалось что lock object раздувает код, а поскольку созданный поток я использую из очень малого числа мест, я его выкинул, заменив на synchronized методы и wait/notify на this. Если хотите знать, что из этого маленького нарушения «кодекса» вышло — добро пожаловать под кат.
Читать полностью »
Библиотека OmniThreadLibrary — простая многопоточность в среде Delphi
2012-05-28 в 7:48, admin, рубрики: concurrency, Delphi, multithreading, Алгоритмы, многопоточность, Параллелизм, Программирование, разработка, синхронизация, метки: concurrency, Delphi, multithreading, Алгоритмы, многопоточность, Параллелизм, разработка, синхронизация Написать интересную статью на техническую тему очень сложно. Приходится балансировать между тем, чтобы не скатиться в технические дебри и тем, чтобы совсем ничего не сказать. Сегодня я попробую в общих словах (без деталей) поговорить о том, как обстоят дела с разработкой многопоточных desktop-приложений в не столь популярной на сегодняшний день, но наверняка знакомой многим российским разработчикам среде Delphi. Статья ориентирована на НЕ новичков в программировании, являющихся при этом новичками в области создания многопоточных приложений.
Читать полностью »
А как же всё-таки работает многопоточность? Часть I: синхронизация
2012-05-28 в 3:57, admin, рубрики: concurrency, java, kernel, multithreading, scheduler, switching, synchronization, Программирование, системное программирование, метки: concurrency, java, kernel, multithreading, scheduler, switching, synchronization, ОС (пост из серии «я склонировал себе исходники hotspot, давайте посмотрим на них вместе»)
Все, кто сталкивается с многопоточными проблемами (будь то производительность или непонятные гейзенбаги), неизбежно сталкиваются в процессе их решения с терминами вроде «inflation», «contention», «membar», «biased locking», «thread parking» и тому подобным. А вот все ли действительно знают, что за этими терминами скрывается? К сожалению, как показывает практика, не все.
В надежде исправить ситуацию, я решил написать цикл статей на эту тему. Каждая из них будет построена по принципу «сначала кратко опишем, что должно происходить в теории, а потом отправимся в исходники и посмотрим, как это происходит там». Таким образом, первая часть во многом применима не только к Java, а потому и разработчики под другие платформы могут найти для себя что-то полезное.
Перед прочтением глубокого описания полезно убедиться в том, что вы в достаточной мере разбираетесь в Java Memory Model. Изучить её можно, например, по слайдам Сергея Walrus Куксенко или по моему раннему топику. Также отличным материалом является вот эта презентация, начиная со слайда #38.
Читать полностью »
Безопасная публикация и инциализация Java-объектов
2012-05-06 в 14:02, admin, рубрики: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlocking, метки: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlockingПост из серии «будни перформанс-инженеров» и «JavaOne круглый год».
К моему величайшему facepalm'у на прошедшем JavaOne была тьма вопросов про double-checked locking, и как правильно делать синглетоны. На большую часть этих вопросов уже ответил Walrus, а здесь я хочу подытожить. Надеюсь этим постом раз и навсегда поставить точку в разговорах про double-checked locking и синглетоны. А то мне придётся сделать резиновую печать с URL этого поста и ставить её спрашивающим на лоб.
Читать полностью »
Безопасная публикация и инициализация Java-объектов
2012-05-06 в 14:02, admin, рубрики: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlocking, метки: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlockingПост из серии «будни перформанс-инженеров» и «JavaOne круглый год».
К моему величайшему facepalm'у на прошедшем JavaOne была тьма вопросов про double-checked locking, и как правильно делать синглетоны. На большую часть этих вопросов уже ответил Walrus, а здесь я хочу подытожить. Надеюсь этим постом раз и навсегда поставить точку в разговорах про double-checked locking и синглетоны. А то мне придётся сделать резиновую печать с URL этого поста и ставить её спрашивающим на лоб.
Читать полностью »
Безопасная публикация и инициализация Java-объектов, или #когдаужепочинятdoublecheckedlocking
2012-05-06 в 14:02, admin, рубрики: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlocking, метки: concurrency, double checked lock, java, java memory model, performance, когдажепочинятdoublecheckedlockingПост из серии «будни перформанс-инженеров» и «JavaOne круглый год».
К моему величайшему facepalm'у на прошедшем JavaOne была тьма вопросов про double-checked locking, и как правильно делать синглетоны. На большую часть этих вопросов уже ответил Walrus, а здесь я хочу подытожить. Надеюсь этим постом раз и навсегда поставить точку в разговорах про double-checked locking и синглетоны. А то мне придётся сделать резиновую печать с URL этого поста и ставить её спрашивающим на лоб.
Читать полностью »
SettableFuture<V>, или как выстрелить себе в ногу сферическим велосипедом в вакууме
2012-04-30 в 18:55, admin, рубрики: concurrency, java, велосипеды, метки: concurrency, java, велосипедыСегодня я расскажу про дизайн тривиального concurrent-класса в JDK. Может быть, это будет удобнее, чем абстрактно объяснять разные концепции из JMM и concurrent-кода.
Все продвинутые парни знают, что такое Future<V> — это обещание предоставить результат типа V. Future'ы удобны, чтобы предоставлять результат асинхронных задач. Например, ExecutorService возвращает Future для описания результата задачи, которая когда-нибудь выполнится в thread pool'е.
Частенько в написании хардкорного concurrent-кода требуется такой примитив, как SettableFuture<V>, который будет выполнять все функции Future<V>, но в который можно будет также выставить значение из другого потока. Эдакий асинхронный mailbox.
За свою недолгую жизнь я видел несколько вариантов реализации такого SettableFuture, рассмотрим некоторые из них, и на заботливо разложенные в них грабли. Большинство примеров реально существовали, некоторые из них были домыслены ради плавности изложения. Чтобы вам не было сильно скучно, попробуйте не читать объяснение после каждого примера, а найти грабли самостоятельно. Для уменьшения простыни мы реализуем только методы set() и get(). Все персонажи вымышлены, хотя пост и основан на реальных событиях.
Читать полностью »
Пишем кеш с определенным временем хранения объектов с использованием java.util.concurrent
2012-03-18 в 20:56, admin, рубрики: concurrency, java, кеш, метки: concurrency, java, кешНе так давно, мне выпала задача, написать кеш, который сам себя чистит по истечению некоторого определенного времени. Требования к нему были следующие:
- Легковесность
- Потокобезобасность
В общем-то и все. До написания данной задачи с java.util.concurrent дела не имел. На мысль использования этого пакета меня натолкнул один мой коллега, у которого было нечто подобное, но не соответствовало тому функционалу который был нужен. Итак, начнем:
В качестве ключа будет выступать внутренний класс, который помимо прямого назначения будет определять он является «живым» или его можно удалить с кеша, так как время его существования подошло к концу:
Читать полностью »