Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Вопрос на засыпку про starvation в synchronized / 14 сообщений из 14, страница 1 из 1
30.07.2013, 16:24:51
    #38349065
iMove
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Коллеги, помогите вспомнить один термин. Дано:
Код: java
1.
2.
3.
4.
5.
6.
while (true) {
    synchronized(this) {
	    // Что-то
		System.out.println(Thread.currentThread().getName());
	}
}


Этот код вызывается с нескольких потоков. И если вы посмотрите на аутпут этого кода, то увидите странную картину, когда один и тот же поток может последовательно входить в synchonized секцию сотни и тысячи раз, не передавая контроль другим потокам. Starvation налицо.

Стал я думать, в чем может быть причина.
1) Понятно, что synchornized не fair, никто никаких гарантий не дает. Но не до такого же маразма, что один поток может напрочь подавить все остальные. Не катит.
2) Есть такая штука, как lock coarsening. Может быть JIT раздвинул границы synchronized за пределы цикла while? Нет, то же не катит. Во-первых, JIT бы это просек не сразу, и сначала я скорее всего увидел бы нормальное переключение потоков. Во-вторых, переключения все таки иногда происходят. Наконец, волшебная опция -XX:-EliminateLocks не помогает.
3) Наконец, я вспомнил, что на какой-то презентации из JUG парни из Оракла (то ли Шипилев, то ли Иванов - не помню) рассказывали, что на ХотСпоте есть такая фигня, что если тред отпускает монитор и почти сразу же пытается снова его захватить, то этот тред оказывается в приоритете относительно остальных ждущих, дабы сэкономить на cas-ах.

И они как-то называли эту технику, каким-то термином. А я не помню его, потому и не могу загуглить деталей. Может быть кто-нибудь в курсе, как по научному называется эта чертовщина? Уж ооочень лень пересматривать эти многочасовые презенташки.
...
Рейтинг: 0 / 0
30.07.2013, 16:35:29
    #38349091
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
iMove.
3) Наконец, я вспомнил, что на какой-то презентации из JUG парни из Оракла (то ли Шипилев, то ли Иванов - не помню) рассказывали, что на ХотСпоте есть такая фигня, что если тред отпускает монитор и почти сразу же пытается снова его захватить, то этот тред оказывается в приоритете относительно остальных ждущих, дабы сэкономить на cas-ах.

Не очень понимаю какая тут экономия на CAS-ах. По-моему здесь вполне логичная экономия на переключении контекста. Текущий поток активный. Остальные спят. Значит если текущему можно отдать монитор без переключения контекста.
...
Рейтинг: 0 / 0
30.07.2013, 16:40:16
    #38349108
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Возможно, забытый термин - spinlock. Но он к указаной проблеме отношения не имеет.
...
Рейтинг: 0 / 0
30.07.2013, 16:52:34
    #38349132
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Вот здесь немного расписано о проблеме. Тоже ничего специального. Вполне логично описано почему активный поток успеет захватить раньше спящих.
http://www.onjava.com/pub/a/onjava/2004/10/20/threads2.html?page=4
...
Рейтинг: 0 / 0
30.07.2013, 17:02:18
    #38349153
GKS_Samara
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Добрый день, iMove!

4) Synchronized умеет делать biased lock, когда первый занявший его
поток имеет массу преимуществ. 2 года назад Lock такого не умел.

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

--
Алексей
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
30.07.2013, 17:14:49
    #38349169
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
GKS_Samara4) Synchronized умеет делать biased lock, когда первый занявший его
поток имеет массу преимуществ. 2 года назад Lock такого не умел.

Это оптимизация однопоточного доступка к synchronized секции. К описаному starvation она отношения не имеет. Проблема о которой пишет автор описана в статье 2004го года. Задолго до реализаци biased lock оптимизации.

GKS_SamaraВообще проблема у вас, что очень узкое место синхронизировано.

Проблема известная. Решается локом с указанием fair order policy. Можно и явно отдавать управление другим потокам перед захватом лока. Но это вообще костыль будет.
...
Рейтинг: 0 / 0
30.07.2013, 18:17:18
    #38349271
schwa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
BlazkowiczGKS_Samara4) Synchronized умеет делать biased lock, когда первый занявший его
поток имеет массу преимуществ. 2 года назад Lock такого не умел.

Это оптимизация однопоточного доступка к synchronized секции. К описаному starvation она отношения не имеет. Проблема о которой пишет автор описана в статье 2004го года. Задолго до реализаци biased lock оптимизации.

На самом деле тоже имеет. В данном случае biased locking эту проблему мог несколько усугубить. Т.к. он может помочь в случае, если локи захватываются редко и малым числом потоков.
Пару лет назад видел сравнения с выключенными и включенными, где были такие же результаты как стартовом посте, но сейчас нагуглить их не смог. Но вот другой пример https://issues.apache.org/jira/browse/CASSANDRA-5360
...
Рейтинг: 0 / 0
30.07.2013, 18:22:15
    #38349281
schwa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
хотя в той issue потом в итоге и не нашли, но в каких-то версиях jvm проблема с biased locking-ом вроде бы была.
...
Рейтинг: 0 / 0
30.07.2013, 19:04:49
    #38349331
iMove
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Не, biased в моем случае ни при чем, я их и трейсил, и отключал - ноль эффекта. Хотя это было понятно с самого начала, ибо контеншн есть.

Собственно, ответ мне более-менее понятен.

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

Кстати, я тут в одной холиварной теме просил народ написать мне striped-lock. Моя решение выглядело вот так:
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
public class Handler<E> {
    private final ConcurrentHashMap<E, CountDownLatch> locks = new ConcurrentHashMap<>();
	
    public void process(E event) {
        lock(event)
		
	try {
	    // Логика.
	}
	finally {
	    // Безопасность.
	    unlock(event);
	}
    }
	
    private void lock(E event) {
        // Наш латчик
	CountDownLatch latch = new CountDownLatch(1);
		
	// Спин
	while (true) {
	    CountDownLatch oldLatch = locks.putIfAbsent(event, latch);
			
	    if (oldLatch != null) {
	        // Не смогли положить, значит ждем другой тред
               oldLatch.await();

                // Как только дождались завершения друго треда, пробуем подсунуть в коллекцию себя
		// Если не получлось, значит кто-то другой успел подсунуть свой латч, спинимся
                if (locks.replace(event, oldLatch, latch))
                    break;
            }
            else
	        // Заблокировали ключ, выходим.
                break;
        }	
    }
	
    private void unlock(E event) {
        // Вытаскиваем латч. Я уверен, что это именно тот, который я положил в методе lock()
        CountDownLatch latch = locks.get(event);
		
	// Отпускаем латч, что бы другие треды начали бороться за ивент.
	latch.countDown();
		
	// Удаляем латч, если его еще никто не перезаписал.
        locks.remove(event, latch);
    }
}

То есть у нас один экземпляр хэндлера, и многие треды вызывают на нем process(E event). Если !event1.equals(event2) то они должны выполняться в параллель, иначе - последовательно.
Так вот, бенчмарки с одним единственным событием показывали, что это решение так же страдает от starvation, хотя и не так выражено. Здесь я до сути пока не докопался. Вероятнее всего, где в методе unlock() собака порылась аналогичным образом, как это происходит в начале топика.
...
Рейтинг: 0 / 0
30.07.2013, 21:46:16
    #38349456
Usman
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
iMoveИ они как-то называли эту технику, каким-то термином. А я не помню его, потому и не могу загуглить деталей. Может быть кто-нибудь в курсе, как по научному называется эта чертовщина? Уж ооочень лень пересматривать эти многочасовые презенташки. "Greedy" threads.
...
Рейтинг: 0 / 0
30.07.2013, 22:03:01
    #38349468
iMove
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
Usman"Greedy" threads.Нет! Нашел!!! Barging ! Monitor barging !
И знаете, как я это нашел? Пишу я, значит, очередной пример для тренинга - один распространенный паттерн на основе ReadWriteLock. Много потоков делают readLock(). tryLock() , один поток делает writeLock.lock(). И тут я вижу, что writeLock у меня уходит в старвейшн - не пускают его ридеры. Я такой немного охереваю - ведь я всегда думал, что ожидающий врайтер должен брать приоритет над ридерами, это логично! И я много раз на это полагался. А тут бац - и не работает.
Ну окей, думаю, дай попробую выставить fair = true. Пробую - нифига, все по старому, ридеры полностью подавили врайтера.
Начинаю читать доку по tryLock(), и вижу, там заветное слово - barging. То есть семантика tryLock() такова, что плевал он на врайтеров, плевал он fairness, если может захватить лок - захватит. А вот tryLock(long, TimeUnit) - уже работает нормально.

ААА! Как я мог не знать этого! ПИПЕЦ! Пишу тренинги для вас, а в итоге сам учусь Круто.
...
Рейтинг: 0 / 0
30.07.2013, 23:00:45
    #38349504
schwa
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
iMove,
Можно в lock() после неудач вставить несколько yield-ов. Это несколько улучшит картину, если задача очень быстрая.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
private void lock(E event) {
        // Наш латчик
	CountDownLatch latch = new CountDownLatch(1);
		
	// Спин
	while (true) {
	    CountDownLatch oldLatch = locks.putIfAbsent(event, latch);
			
	    if (oldLatch != null) {
               /*1*/Thread.yield();//Не смогли, то можно отдохнуть.

               // Не смогли положить, значит ждем другой тред
               oldLatch.await();

                // Как только дождались завершения друго треда, пробуем подсунуть в коллекцию себя
		// Если не получлось, значит кто-то другой успел подсунуть свой латч, спинимся
                if (locks.replace(event, oldLatch, latch))
                    break;
                else 
                 /*2*/Thread.yield();//Не получилось, то тоже можно отдохнуть.
            }
            else
	        // Заблокировали ключ, выходим.
                break;
        }	
    }
...
Рейтинг: 0 / 0
31.07.2013, 10:32:34
    #38349712
maxkar
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
iMove,

У вас пример интересный. Он еще показывает различные "уровни" синхронизации в JVM. На семерке/восьмерке первые 5 тысяч строк выводятся достаточно случайно. Там еще работает spin lock. К концу пятой тысячи JVM этот бардак надоедает и она переходит на более сложную синхронизацию (с использованием OS-зависимых операций). Потоки перестают крутить циклы и встают в очередь. А там уже как раз из-за monitor barging текущий поток имеет приоритет при следующем захвате монитора. На однопроцессорной системе он просто выполняется дальше, на многопроцессорной - другие потоки не успевают запуститься до следующего захвата монитора.
...
Рейтинг: 0 / 0
31.07.2013, 10:42:08
    #38349733
iMove
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Вопрос на засыпку про starvation в synchronized
maxkariMove,

У вас пример интересный. Он еще показывает различные "уровни" синхронизации в JVM. На семерке/восьмерке первые 5 тысяч строк выводятся достаточно случайно. Там еще работает spin lock. К концу пятой тысячи JVM этот бардак надоедает и она переходит на более сложную синхронизацию (с использованием OS-зависимых операций). Потоки перестают крутить циклы и встают в очередь. А там уже как раз из-за monitor barging текущий поток имеет приоритет при следующем захвате монитора. На однопроцессорной системе он просто выполняется дальше, на многопроцессорной - другие потоки не успевают запуститься до следующего захвата монитора.Очень сомневаюсь, что там есть biased locking, про который вы говорите. Во-первых, там есть контеншн. Во-вторых, biased locking изначально отключен, он включается только после некоторого прогрева JVM. Попробуйте сделать следующее:
1) Отключите биасы: -XX:-UseBiasedLocking , и посмотрите на результаты
2) Включите биасы так, чтобы они работали с самого начала: -XX:+UseBiasedLocking -XX:BiasedLockingStartupDelay=0 -XX:+TraceBiasedLocking -XX:+TraceMonitorInflation
Я думаю, что у вас ничего не изменится.

Возможно, там какой-то замут со спинингом на обычных мониторах (-XX:+UseSpinning и связанные с ним ключики)
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Вопрос на засыпку про starvation в synchronized / 14 сообщений из 14, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]