Сучасна диджитал-освіта для дітей — безоплатне заняття в GoITeens ×
Mazda CX 5
×

Когда ReadWriteLock бывает бесполезен

Хочу поделиться опытом использования ReadWriteLock — имплементации, поставляемой в JDK, нашим «разочарованием» в ней и о том, как мы обошли проблему ограничения scalability.

Но начнем мы издалека.

Существует два типа блокировок — spin lock и lock, обрашающийся к OS для переключения между потоками. Spin lock, как, я думаю, вы уже догадались, не переводит поток в состояние ожидания, а ждёт в цикле до тех пор, пока требуемый ресурс не осовбодится. Существует мнение, что spin lock — это прошлый век, и что надо пользоваться блокирущими lock’ами. На самом деле это не так.

Если даже не брать во внимание, что блокирующий lock вызывает переключение контекстов потоков, в нём также производится interpocessing method call — дорогая операция. Вызов метода OS может привести к высокой latency во время захвата монитора объекта.

Таким образом, если у вас время выполнения самого метода очень маленькое, то spin lock будет повышать скорость выполения программы сильнее, чем блокирующий lock. Если же у вас сам метод выполняется очень долго, то блокирущий lock выгоднее, так как он позволяет эфективнее перераспределить ресурсы OS.

ReadWriteLock использует в чем-то похожий подход. Сначала используется spin lock, и если получить доступ к ресурсу невозможно, вызывается метод  java.util.concurrent.locks.LockSupport#park(java.lang.Object) для передачи ресурсов OS другому потоку. Причем данный подход относится также к реализации exclusive lock на уровне JDK (java.util.concurrent.locks.ReentrantLock) и JVM (synchronized).

Теперь давайте расмотрим в деталях, как это реализовано.

Начнём с очень примитивной эксклюзивной блокировки (так называемый test-and-set lock):

public class TestAndSetLock {
    AtomicBoolean state = new AtomicBoolean(false);

    public void lock() {
   	 while (state.getAndSet(true)) {}
    }
    public void unlock() {
   	 state.set(false);
    }
}

Операция getAndSet является атомарной т.е. между get и set значение переменной гарантированно не поменяется, что и позволяет использовать её для данного spin lock.

Сделаем небольшой, далеко не идеальный, но показательный бенчмарк.
Основной код этого бенчмарка здесь:

public final class Countdown implements Callable<Long> {
   	 private final long iterations;

   	 public Countdown(long iterations) {
   		 this.iterations = iterations;
   	 }

   	 @Override
   	 public Long call() throws Exception {
   		 final long start = System.nanoTime();

   		 long cnt = iterations;
   		 while (cnt > 0) {
   			 spinLock.lock();
   			 cnt--;
			 spinLock.unlock();
   		 }

   		 final long end = System.nanoTime();
   		 return end - start;
   	 }
    }
}

Таким образом, мы выполняем N операций в каждом потоке (в нашем случае 2^24), сумируем время выполнения и смотрим среднее для одной операции.

Давайте сначала посмотрим время выполнения операции для одного потока:

Average execution time : 1 ns per operation.

Теперь посмотрим результат для 8 потоков:

Average execution time : 1163 ns per operation.

Ого! Разница просто невероятная. Такое увеличение времени операции связано, грубо говоря, с тем, что потоки постоянно конкурируют за один и тот же участок памяти.

Можно немного уменшить уровень contention между потоками (test-test-and-set-lock):

public class TestTestAndSetLock {
    AtomicBoolean state = new AtomicBoolean(false);
    public void lock() {
   	 while (true) {
   		 while (state.get()) {};
   		 if (!state.getAndSet(true))
   			 return;
   	 }
    }
    public void unlock() {
   	 state.set(false);
    }
}

И результаты его бенчмарка:
Average execution time : 948 ns per operation.

Что, собственно, и стоило ожидать.

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

Собственно имплементация:

public class CLHQueueLock {
    private final AtomicReference<Qnode> tail = new AtomicReference<Qnode>();

    private final ThreadLocal<Qnode> myNode = new ThreadLocal<Qnode>() {
   	 @Override
   	 protected Qnode initialValue() {
   		 return new Qnode();
   	 }
    };

    private final ThreadLocal<Qnode> myPred = new ThreadLocal<Qnode>();

    public CLHQueueLock() {
   	 final Qnode qnode = new Qnode();
   	 qnode.locked = false;

   	 tail.set(qnode);
    }

    public void lock() {
   	 final Qnode localNode = myNode.get();
   	 localNode.locked = true;

   	 final Qnode pred = tail.getAndSet(localNode);
   	 myPred.set(pred);

   	 while (pred.locked) ;
    }

    public void unlock() {
   	 myNode.get().locked = false;

   	 myNode.set(myPred.get());
    }

    static final class Qnode {
   	 volatile boolean locked = true;
    }
}

И результаты бенчмарка:

Average execution time : 681 ns per operation.

Сначала сделаем небольшую таблицу сравнения результатов, а затем я дам объяснения по деталям реализации CLH-блокировки:

Test-and-set
test-test-and-set
CLH
Time/ op, ns
1163
948
681

Вообще-то наш бенчмарк совсем не идален — например, мы не смотрели, как изменятся показатели при росте количества потоков, не смотрели на девиацию результатов. Хотелось бы делать что-то более долгое, чем декрементирование счётчика. Кроме того, ведь System.nanoTime() тоже не бесплатный, однако его вполне достаточно, чтобы понять основную идею.

Теперь давайте посмотрим на примере, как работает CLH queue (хотя бы потому, что именно её модификация используется в OpenJDK), на примере трёх потоков.

Для каждого потока у нас есть QNode, которая показывает, отпустил ли данный поток необходимый ресурс. Состояние этой QNode мониторится потоком, который стоит за ним в очереди.

То есть при захвате ресурса потоки выстраиваются в очередь, и поток в голове очереди устанавливает флаг захвата ресурса, который мониторит поток, стоящий за ним, и определяет, может ли ожидающий поток использовать необходимый ресурс.

Итак, по шагам.

Thread_1 вызывает метод lock, получает фейковый QNode передыдущего потока (предыдущего потока просто нет) и помещает свой QNode в tail. И начинает выполнять необходимые ему действия. Причём фейковый QNode становится QNode данного потока при осовобождении блокировки.

Thread_2 получает QNode предыдущего потока. И ждёт, пока предыдущий поток не овободит ресурс, установив свой флаг захвата ресурса (locked) в false. Так же в tail помещается QNode с флагом locked, установленным в true.

Thread_3 Получает QNode из tail и ждёт уже второй поток.

Thread_1 устанаваливает locked флаг в false.
Thread_2 выполняет работу и устанаваливает locked флаг в false.
Thread_3 выполняет работу и устанаваливает locked флаг в false.

И на этом выполнение потоков заканчивается.

CLH queue на самом деле не всегда выигрывает по сравнению с test-test-and-set lock , но более детальный анализ блокировок — это уже другая истроия.

К чему, собственно, мы всё это рассмотрели? Хотя бы потому, что OpenJDK использует аналог CLH queue, но, как это ни странно, использует его для пробуждения заблокрированных потоков, а не для spin lockов. То есть когда поток освобождает ресурс, он пробуждает потоки, стоящие в очереди. Мы не будем рассматривать полностью, как работет RW lock, но в контексте этой статьи посмотрим, как рабоает read часть данной блокировки.

Когда мы пытаемся заблокировать ресурс на чтение, вызывается метод

 public final void acquireShared(int arg) {
    	if (tryAcquireShared(arg) < 0)
        	doAcquireShared(arg);
}

В контексте ReadWriteLock метод работает следующим образом (будем рассматривать только отдельные участки кода):
ReadWriteLock содержит переменную, хранящую в себе количесвто readers и writers, которые захватили данный lock. Она инкрементируется и декрементируется атомарно, то есть представляет собой, по сути, flag для spin lock.

java.util.concurrent.locks.ReentrantReadWriteLock.Sync#fullTryAcquireShared

 for (;;) {
            	int c = getState();
                        //получили колличество  writers  
            	if (exclusiveCount(c) != 0) {
                        //если у нас кто то захватил exclusive lock, но не мы  придётся заснуть
                	if (getExclusiveOwnerThread() != current)
                    	     return -1;
             	} else if (readerShouldBlock()) {
   //всё равно спим например для того, чтобы writers могли получить  доступ
    //при огромном колличестве readers
                            return -1;
            	}

                       //инкрементируем колличество reades. если writers нет будем делать до 
                       //победы
            	if (compareAndSetState(c, c + SHARED_UNIT)) {
                	            	return 1;
            	}
	}  

doAcquireShared кладет поток в очередь ожидания, пытается захватить read lock (как описано выше), не получается — он засыпает, просыпается, и т.д.

final Node node = addWaiter(Node.SHARED);

	for (;;) {
		final Node p = node.predecessor();
		if (p == head) {
			int r = tryAcquireShared(arg);
			if (r >= 0) {                    
					return;
		}
		if (shouldParkAfterFailedAcquire(p, node) &&
			parkAndCheckInterrupt())
			interrupted = true;
}

Так вот, если посмотреть внимательно, то можно увидеть, что в случае наличия только readers наш ReadWriteLock очень похож на test-and-write lock со всеми вытекающими последствиями по потери производительности.

Теперь давайте немного изменим бенчмарк и сделаем следующее: посчитаем, скажем, с 16 000 000 до 0 на одном потоке, потом выполним то же число операций (8 потоков по 2 000 000 операций на каждом) на 8 потоках. А затем посчитаем суммарное время выполнения для всех потоков в наносекундах и время выполнения всей программы в милисекундах. Ведь читающие потоки не блокируют друг друга, правда?

Итак, на 1 потоке:

Count down for :     361 172 637 ns. Execution time is : 362 ms.

На 8 потоках:

Count down for :   21 824 811 292 ns. Execution time is : 2 780 ms.

То есть, грубо говоря, 8 читающих потоков работали в сумме в 9 раз медленее, чем один.

Тест несколько спекулятивный, но очень показательный, так как мы в своём проекте (NoSQL базы данных) столкнулись с подобной же ситуацией. Когда несколько потоков работали на чтение медленее, чем один.

Вообще довольно грустная перспектива, с учётом того, что нам очень хотелось получить масшатабирование системы на чтение.

И мы решили сделать свой собственный ReadWriteLock.
У нас есть некоторые особенности: мы редко используем глобальные блокировки, и глобальная блокировка на запись нам нужна была в тех, случаях когда:
1. Скорость записи была для нас не так критична, как чтение.
2. У нас было много частых и быстрых операций чтения.
3. Мы работаем с долгоживущими потоками (хотя, на мой взгляд, это не совсем обязательно).

Сразу приведу результат того сумашедшего бенчмарка, который мы прогнали:

Count down for :    1 221 961 202 ns. Execution time is : 166 ms.

Что в два раза быстрее, чем на одном потоке, не говоря уже о втором тесте.

Если у вас те же условия, вы можете воспользоваться нашим опытом и, собственно, самой блокировкой com.orientechnologies.common.concur.lock.OReadersWriterSpinLock в проекте github.com/...​rientechnologies/orientdb.

Как работает данный lock:

Write lock так же изначально представляет собой CLH-lock.

final WNode node = myNode.get();
node.locked = true;

final WNode pNode = tail.getAndSet(myNode.get());
predNode.set(pNode);

while (pNode.locked) {
  pNode.waitingWriter = Thread.currentThread();

  if (pNode.locked)
    LockSupport.park(this);
}

pNode.waitingWriter = null;

Дальше нам придется переключиться на чтение. Здесь ситуация несколько иная:
каждый reader имеет совю собсвенную thread local переменную, считающую колличество readers для данного потока.

threadCountersHashTable.increment();

Затем мы проверяем, захвачен ли write lock. Если да, то мы выполняем back off, декрементируя counter для текущего readerа.

WNode wNode = tail.get();
while (wNode.locked) {
    threadCountersHashTable.decrement();

    while (wNode.locked) {
       wNode.waitingReaders.add(Thread.currentThread());

       if (wNode == tail.get() && wNode.locked)
      	LockSupport.park(this);

        wNode = tail.get();
    }

    threadCountersHashTable.increment();
     wNode = tail.get();
}

Ждём, пока write lock освободится, и снова инкрементируем read lock counter для текущего потока.

Очень важно отметить, что таким образом каждый reader инкрементирует свой read counter, и readers не конкурируют между собой.

Теперь возвратимся к захвату write lock.

while (!threadCountersHashTable.isEmpty())
  	;

setExclusiveOwnerThread(Thread.currentThread());

Собственно говоря, write lock ждёт, пока все readers не закончат свою работу.

Освобождение write lock включает в себя сброс флага и нотификацию всех ожидающих readers, которые зарегистрировали себя в данном потоке.

Кстати, ситуация, когда мы зарегистрировали себя во wirter потоке, а он уже пробудил всех зарегистрированных readers, не возникнет, так как мы сначала добавляем себя в очередь ожидания

wNode.waitingReaders.add(Thread.currentThread());,

а засыпаем только если контролирующий поток всё ещё не разблокировал ресурс.

if (wNode == tail.get() && wNode.locked)
      	LockSupport.park(this);

Сами по себе thread local counters содержатся в HashMap, которая реализована на основе алгоритма lock free cuckoo hashing. К тому же, это HashMap рассматривает ячейку с local thread counter, для которой значение Thread.isAlive() = false как пустую, т.е. у вас никогда не будет переполнения памяти.

Вот и всё. Если вы найдёте ошибку в том, что мы сделали или написали, мы вам будем очень благодарны. Если Вам интересно узнать намного больше о многопоточном программировании, регистрируйтесь на наш курс.

Кроме того, успешно закончившие курс получат возможность трудоустройства в orientechnologies в качестве core developer, а часть прибыли с курса будет отправлена на благотворительность.

Все исходные коды вы можете найти здесь.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU

👍ПодобаєтьсяСподобалось0
До обраногоВ обраному0
LinkedIn

Схожі статті




43 коментарі

Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.

Ежики плакали, кололись но продолжали грызть кактус. И да — вы еще забыли о кешах ...

Да увы Вы правы )).
может Вы расширите Ваш комментарий, например вы имеете ввиду почему мы не использовали copy on wirte или STM, увеличили гранулярность блокировок или похожие подходы, к сожалению сложность структуры схемы, механизмы доступа по API и жизненный цикл не позволяли нам это сделать.

Кстати раз мы уже заговорили про кеши можно у Вас попросить рекомендацию как бы Вы улучшили данный подход исходя из информации про механизмы обеспечения когерентности кешей и влияния fences в процессе исполнения многопоточной программы ?

P.S. У ребят разработчиков ядра Linux возникла та же самая проблема (они её решил немного похожим, но другим способом) и решили тоже есть кактус www.usenix.org/...4-paper-liu.pdf .

Я в java немного плаваю, но насколько я помню java-треды отображаются на системные posix-треды которые сами по себе — конец производительности. На суперскалярных архитектурах и нормальных («прямых») языках программирования адекватным выходом из ситуации является переделывание приложения в однопоточное.

Подробности можно узнать у Алана Кокса (например загуглив «Alan Cox threads») а рекомендации — на cайте lwn.net.

P.S. У ребят разработчиков ядра Linux возникла та же самая проблема (они её решил немного похожим, но другим способом) и решили тоже есть кактус www.usenix.org/...4-paper-liu.pdf .

Не путайте теплое с мягким. У вас в Яве нет достаточно свободы и обьективной информации чтобы ориентироватся на кернельные решения.

Но ведь JNI никто не отменял, верно?

Да для Linux, я про это тоже думал, но эти блокировки завязаны на ядро и как результат не портируемые. Я имею ввиду что они реализиваны в ядре потому как потоки для обеспечения похожей стратегии похожей на то что я описал они используют аппаратный протокол коммуникации между ядрами. А для обычных разработчиков написана обёртка вокруг ядра ))

Не страшно что не портируемые — просто приложишь к своему *.jar тучу *.so, *.dll, *.dylib для всех известных платформ (сколько их там — двадцать?) и со временем сузишь круг до 2-3 которые будут реально востребованы.

Да, забавно будет выглядеть — приложение на Java, а к нему ещё JNI библиотеки а к ним ещё и драйвера. Но если оно всех побьёт по производительности, и драйвера будут стабильными, то почему бы и нет? :)

jni не пустит вас так просто в потроха кернела

а какие могут быть препятствия для этого, если реализация идёт на низкоуровневом языке?

Единственное что я вижу, так это портирование реализации на другие платформы...
Если я что-то не допонимаю, то расширьте пожалуйста свой комментарий, Виталик.

Например MMU.

Если я что-то не допонимаю, то расширьте пожалуйста свой комментарий,

Лучше задавай наводящие вопросы :)

да тут задавать собственно нечего :) здесь опыт нужен и понимание, зачем такое делать. Я просто не могу себе представить случай для чего использовать MMU, какие другие возможные решения есть, и почему именно таким способом лучше решать проблему.

На сколько я прочла, то основная цель MMU — контроль чтения, записи, выполнения в памяти, мапинг виртуального адресного пространства на физический, но это просто сухое описание... Нужно узнать лучше проблему, и почему её (или подобное) лучше решать через MMU.

Если сможешь расширить мое понимание, буду очень тебе благодарна, Виталик.

Ок, сильно приближенно: MMU это элемент процессора которые отделяет программы от операционной системы и разделяет между собою, так чтобы никто никому не мешал. Стандартные интерфейсы ядра не предполагают передачу технических подробностей в программы (например тому же JNI) а MMU не позволит получить эту информацию минуя стандартные интерфейсы. Поэтому использование кернельных технологий в приложениях чревато непредсказуемым поведением или неэффективностью.

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

использование кернельных технологий в приложениях чревато непредсказуемым поведением или неэффективностью.
?

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

спасибо большое, Виталик, и на этом

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

Коментар порушує правила спільноти і видалений модераторами.

смотрите Ваша аргументация такая:
«на нормальном языке я пишу правильно, правильный подход , такой то ... почему это уже другое дело»
А на вопрос «а здесь тоже нужно однопоточное приложение» ответ не путайте «тёплое с мягким».

Не очень сильная аргументация.

Тогда я задам ещё вопрос мы делаем базу данных она тоже должна быть одно поточной ?
И ещё возможно Вы считаете, база на Java не пишутся, тогда скажите Вы Apache Cassandra тоже не относите к базам данных ?

> Тогда я задам ещё вопрос мы делаем базу данных она тоже должна быть одно поточной ?

если основной аппаратной платформой будет суперскалярная x86 или чтото аналогичное — то в некотором смысле — однозначно. Базы данных это не та область где обычные треды дадут чтото кроме головной боли. Поэтому если ваша java позволяет обходится без тредов — разумно этой возможностью воспользоватся.

> И ещё возможно Вы считаете, база на Java не пишутся, тогда скажите Вы Apache Cassandra тоже не относите к базам данных ?

мне то и незнать :)))

Я тут немного походил и мне пришла идея как обьяснить суть проблемы более доступно:

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

Извините за нубский комментарий, но мне не очень нравится слово «по умолчанию». По всему выходит что если надо, то можно сделать и по другому.

Что касается второй части комментария. Неужели многопоточность придумали только для того чтобы запускать паралельно несколько приложений? Я не то чтоб был гуру в многопоточности, но все что я читал до этого, а так же лабораторные работы из универа свидетельствует том что можно получить выгоду выполняя части алгоритма парралельно.
Конечно барьеры замедляют работу приложения, но если у вас есть выбор
50% работы и потом еще 50% работы
или
50%*10% оверхед и 50%*10%оверхед паралельно,
то становится очевидным что второй подход быстрее.

Дабы предотвратить комментарии о том что я защищаю джаву, добавлю что мне очень нравится подход node.js и erlang с так называемыми «зелеными потоками».

А комментарий я пишу только чтоб лучше понять вашу мысль.
Спасибо.

> Извините за нубский комментарий, но мне не очень нравится слово «по умолчанию». По всему выходит что если надо, то можно сделать и по другому.

В «нормальных» языках программирования можно попытатся поигратся с аффинити но это целесообразно только на узком круге специфических задач.

> Неужели многопоточность придумали только для того чтобы запускать паралельно несколько приложений?

Многопоточность придумали для того чтобы обойти промахи дизайна первых юниксовых ядер которые работали на RISC процессорах с минимальным кешем первого уровня. Сейчас все не так.

> так же лабораторные работы из универа свидетельствует том что можно получить выгоду выполняя части алгоритма парралельно.

«Академические» треды это немного не то что мы реально имеем в линуксе и довольно далеко от реальной жизни на суперскалярных платформах. Линуксовые треды это худший из возможных способ распаралеливания (получения возможной выгоды) но именно его по всей видимости используют ребята в коде в топике.

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

Вы тупые мифы-то не ретранслируйте, пожалуйста. Во-первых, «многопоточность» придумали ещё в OS/360, и это называлось «подзадачами» (да, у IBM своя терминология почти во всём, что касается ОС). Это было за почти десять лет до того, как первые RISC вообще начали воплощаться. И придуманы были они для того, чтобы не бодаться с FSM там, где в разы легче написать исполнение кода в привычном линейно-циклическом виде. Эта причина остаётся одной из основных даже сейчас, хотя принципы реализации многонитевости с тех пор существенно менялись не один раз. Во-вторых, Unix на RISC это ещё позже — начало 80-х — до этого Unix жил только на линии PDP (причём до 11-го ещё на кривых 18/36-разрядных уродцах), немного на VAX.

Вы, наверно, озвучиваете отголоски первых реализаций Unix на Sparc и особенности этого процесса. Да, там было много странного. Например, идея TLS была рождена в этих кругах сильно позже (и свидетельством функции типа read_r()). Но Sparc вообще очень перекошенная, по сравнению с обычными, архитектура, и проблема кэшей там далеко не главная.

На сейчас многонитевость — обязательное доступное средство, хотя использовать его или нет, и как именно использовать — вопрос отдельный. Кто-то, как шарповцы с их async/await, считает, что от неё лучше максимально уходить, сделав явные переключения по выделенным точкам. Кто-то оптимизирует именно работу при условии ядерного переключения. Как по мне, оба подхода имеют и право, и обязанность на существование. Ну а чем будет легче в конкретном случае — в нём и определится... главное, чтобы было чем адекватно измерить, вот это на сейчас основная проблема. Например, у Intel есть такие средства, но нормально сделаны только под Windows, что нам не подходит.

Спасибо за экскурс в историю но я использовал RISC как имя нарицательное. Как антоним для «суперскалярная архитектура». Для меня это главное значение этого слова со времен «Теории микропроцеесоров» в университете. Извиняюсь за путницу.

Хм. Видимо, эта теория давно устарела, потому что сейчас и RISC может быть суперскалярным (например, старшие ARM выполняют 2 операции за такт, если те не дерутся между собой). RISC отличается не полным отказом от суперскалярности, а оптимизацией на то, что и на дешёвом процессоре без оной скорость работы будет разумной. Поэтому в таком виде оно уже не опознаётся.

возможно — знания протухают :(( Если бы топик стартер не уклонился от развития дискусии то у нас была бы возможность освежить знания ...

Вы тупые мифы-то не ретранслируйте, пожалуйста. Во-первых, «многопоточность» придумали ещё в OS/360, и это называлось «подзадачами» (да, у IBM своя терминология почти во всём, что касается ОС). Это было за почти десять лет до того, как первые RISC вообще начали воплощаться. И придуманы были они для того, чтобы не бодаться с FSM там, где в разы легче написать исполнение кода в привычном линейно-циклическом виде. Эта причина остаётся одной из основных даже сейчас, хотя принципы реализации многонитевости с тех пор существенно менялись не один раз. Во-вторых, Unix на RISC это ещё позже — начало 80-х — до этого Unix жил только на линии PDP (причём до 11-го ещё на кривых 18/36-разрядных уродцах), немного на VAX.

Я тут вспомнил на чем я основывался: «Практика программирования» Керниган и Пайк. У меня нет под рукой копии чтобы процитировать но смысл гдето такой: Возможность программировать без использования тредов была одной из основных фич при создания первого Юникса ибо ребята заколебались отлаживать много тредовые приложения под какойто тогдашней осью.

Ну, это заметно не о том. Они предельно удешевили системный процесс для того, чтобы можно было каждую отдельную элементарную работу выносить в свой процесс, а взаимодействие возложили на пайпы и тому подобное. Это да, отличная защита от проблем всяких внутренних поломок. Интересно, что это за ось такая проблемная у них была?

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

P.S. Спасибо за ссылку на статью, это позволило мне понять Вашу точку зрения.

Я в прошлом достаточно много времени провел в исследованиях как максимально загрузить конвеер не прибегая к много поточности. В результате в моих проэктах я ни разу не встречал ситуации когда производительности конвеера на одном потоке нехватает и мне бы требовалось распаралеливание на несколько конвееров. Да, я использовал C и подобное а не Яву и слышал что Ява в состоянии загрузить конвеер работой но обычно разговоры про треды и распаралеливание начинаются при уровне загрузки конвеера 2-3% и является безсмыслицей и напрасной тратой времени и ресурсов.

Или вы как Оракл — оптимизируете свою базу под Ниагары?

Доброго времени суток, спасибо за статью.
Есть только пожелание и вопрос.
Пожелание добавить номера строк в листинги кода, если это просто сделать.
А вопрос в следующем, я конечно не специалист, но так и не понял зачем складывать предыдущий QNode в ThreadLocal

Вот листинг:

         final Qnode pred = tail.getAndSet(localNode);
   	 myPred.set(pred);

   	 while (pred.locked) ;

Вопрос был разрешен с применением моего мозга, спасибо большое.

А можно попросить Вас поделиться для других, и тем самым сэкономить мне время ? ))

Мне самой стало интересно, верно ли я сама поняла, описание CLHQueueLock из Вашей статьи, Андрей.

Мое понимание:
Если Thread_1 поставит свойство locked в true у Qnode (в моем понимании — объект, по которому происходит синхронизация потоков) и после этого прибегут Thread_2 и др. потоки за этим же локом (вызовут метод lock у CLHQueueLock), то после выполнения потоком Thread_1 метода unlock будет запущен следующий Thread_2 и после выполнения метода unlock потоком Thread_2 следующий и тд. Ждать придётся поток, который захватил лок потому, что только у него есть ссылка в tail на Qnode, который он поместил из переменной localNode: final Qnode pred = tail.getAndSet(localNode);. И до тех пор, пока этот поток не присвоит localNode свойству locked - false: myNode.get().locked = false; (во время выполнения метода unlock), следующий поток будет ожидать на шаге while (pred.locked) ;, см. код:

final Qnode pred = tail.getAndSet(localNode);
myPred.set(pred);
while (pred.locked) ;
Интересным и непонятным куском кода для меня показался myNode.set(myPred.get()); из метода unlock, так как я считала (после прочтения документации), что если переменная сохраняется в ThreadLocal, то при этом создается копия этой переменной, чтобы обеспечить потокобезопасность, но получилось в этом конкретном случае, что это не так, так как когда во втором потоке мы выполняем myNode.set(myPred.get());, то видим уже значение не то, которое установили еще до этапа ожидания в myPred.set(pred);. И тут до меня дошло, что это может быть только благодаря volatile boolean locked = true; а именно ключевому слову volatile и по этому вопросу я нашла интересный комментарий, в котором один умный парень -Stephen объяснил, почему: Volatile Keyword & the thread local memory, а именно:

Volatile variables are not stored on the stack.
после чего такое поведение мне стало казаться вполне предсказуемым.

Если я не правильно поняла, объясните тогда пожалуйста мою ошибку.

Ирина, всё верно.
Кроме того, что копия переменной не делается при установки ThreadLocal.
ThreadLocal работает следующим образом.
Каждый поток содержит в себе HashMap которая реализована по алгоритму linear probing en.wikipedia.org/.../Linear_probing который является довольно не эффективным если бы не метод генерации hash code для каждой Thread Local . Когда вы работаете с ThreadLocal Вы работаете с hash map так как каждый поток содержит свой instance hash map у вас все ссылки активны только внутри данного потока вот и весь секрет работы ThreadLocal.

Теперь относительно того, зачем мы берём pred ссылку и делаем её current во время unlock.
Это приводит к тому, что по окончании цикла «борьбы за ресурсы» мы получим то же состояние, что и в самом начале т.е. одна fake qnode не принадлежащая ни одному из потоков. Т.е. получаем «закрытую» корректную модель.

Что будет если вместо fake qnode мы получим ситуация когда одна из qnode будет по окончании процесса блокировки будет находится в хвосте и принадлежать потоку ?

Например у нас два потока t1 qnode одновременно находится и в tail.
t1 выполняет

 
final Qnode localNode = myNode.get();
localNode.locked = true;

затем t2 выполняет :

final Qnode localNode = myNode.get();
localNode.locked = true;

final Qnode pred = tail.getAndSet(localNode);
while (pred.locked) ;

и ждёт ведь pred.locked == true (поток t1)

но затем t1 выполняет:

 final Qnode pred = tail.getAndSet(localNode);
 while (pred.locked) ;

и тоже ждёт ведь и здесь pred.locked == true (поток t2)

т.е. у нас dead lock на блокировках :-)

Чтобы уточнить, когда я имел ввиду, что

Когда вы работаете с ThreadLocal Вы работаете с hash map так как каждый поток содержит свой instance hash map
то я имел ввиду, что каждый класс Thread содержит поле java.lang.Thread#threadLocals .

Спасибо, Андрей, хорошая статья.

А могли бы Вы пожалуйста еще немножко написать об области и проблеме, которую Вы пытались решить описанными Вами способами, хотелось бы лучше с Вами разделить эту боль? ;)

Спасибо, Ирина, за отзыв :-)

У нас довольно специфичная область, создание базы данных. Поэтому я не хотел её раскрывать, так как прочитав её может создастся мнение, что обычного разработчика это не касается. Но дело в том, что я несколько раз видел в коде пример на подобии этого:

setValue(value) {
 writeLock.lock();
 try {
 this.value = value;
 } finaly {
  writeLock.unlock()
 }
}

getValue() {
 readLock.lock();
 try {
 return value;
 } finaly {
  readLock.unlock()
 } 
}

потому как для этого вроде бы RWLock и существует и код масштабируем, но увы это не так.

Что касается того где мы применяем данную блокировку, то это: чтение данных из схемы базы, у нас база графовая с поддержкой наследования и схема соответственно не плоская, а иерархическая. Блокировка области данных в кеше при переименовании файла или закрытии базы.

Я вот кстати нашла интересную презентацию www.infoq.com/...sentations/LMAX , на которой ребята рассказывают как создавали высоконагруженную систему, способную обрабатывать более 100K транзакций/сек с задержкой меньше, чем в 1мс. В своей презентации они рассказывают о проблемах, с которыми сталкивались во время разработки многопоточного приложения и как их решали. В начале конечно больше общего, но к середине тема хорошо прогревается и может подогреть Ваш интерес к их решениям, Андрей ;) Вдруг Вы эту презентацию ещё не видели, и может что-нибудь полезное для себя или своего проекта в ней найдете.

Вот краткое описание этой презентации:


Martin Thompson and Michael Barker talk about building a HPC financial system handling over 100K tps at less than 1ms latency by having a new approach to infrastructure and software. Some of the tips include: understand the platform, model the domain, create a clear separation of concerns, choose data structures wisely, and run business logic on a single thread.

Да, кстати забыла добавить еще один вариант презентации того же видеодоклада ребят Martin Thompson’а и Michael Barker’а: www.slideshare.net/...z-nir-published

+ презентации:

Ирина, спасибо за ссылки.
Я вроде бы написал комментарий, но он не появился. Так что извините если будет две копии.
Я читал про Disruptor , но правда давно. Но вот, что интересно, часть решений из Disruptor мы реализуем на практической части курса вместе со студентами. Так же на мой взгляд есть более быстрые решения на базе Single Producer Single Consumer очереди , это bqueue (не мог найти ссылки быстро )) ) и FastFlow sourceforge.net/...ts/mc-fastflow . Мы их дадим в качестве экзаменационного задания объяснив перед этим конечно алгоритм работы.
Если Вам это интересно вот список всех структур и тем, надеюсь мне буде позволительно это выложить — docs.google.com/...dit?usp=sharing

Андрей, а можно было бы Вас попросить написать статью, где Вы бы сравнили решение на базе шаблона Disruptor с решениями на базе шаблона Single Producer Single Consumer Queue (bqueue, FastFlow реализации), по результатам которой можно было бы прочувствовать природу выигрыша от использования Single Producer Single Consumer Queue?

Не уверена конечно, но может всё-таки есть случай, в котором лучше использовать Disruptor шаблон, чем Single Producer Single Consumer Queue шаблон? Конечные решения ведь в основном принимаются исходя из частных случаев, особенно когда речь идет о больших нагрузках и масштабируемости? Как Вы считаете, Андрей?

Да конечно Ирина,
Я абсолютно уверен, что такие случаи есть, тем более, что я уверен, что люди писавшие Disruptor знали о данной реализации. Мы собираемся использовать этот тип очереди внутри базы данных и я попытаюсь сравнить разные реализации очередей. Возможно будет чем поделиться.

Кстати попала на парня, которого зовут Martin Thompson, просто фанатеющего от решений сложных проблем, связанный с оптимизацией высоконагруженных систем и паралельных вычислений. Его блог можно прочитать здесь:
Mechanical Sympathy

Также этот товарищь провел вполне увлекательное исследование Lock-Based vs Lock-Free Concurrent Algorithms, которое Вам может быть также интересным:
mechanical-sympathy.blogspot.com/...concurrent.html

Здесь у него лежит код с тестами, который он реализовал на базе one producer and one consumer, используя Ring Buffer: LMAX Collections и статья по этой реализации: The Coalescing Ring Buffer.

+ у него много другого материала по форматам сообщений, архитектурам GC, CPU, кешам и прочее...

Підписатись на коментарі