Статьи

Реализация фильтра и блокировки хлебобулочных изделий в Java

Март 19, 2019

Для того, чтобы понять, как работают блокировки, хорошая реализация пользовательских блокировок. В этом посте будет показано, как реализовать блокировки Java и Bakery на Java (которые являются спин-блокировками), и будет проведено сравнение их производительности с ReentrantLock Java. Блокировки фильтра и хлебобулочных изделий удовлетворяют взаимному исключению и также являются алгоритмами без голодания, блокировка хлебобулочных изделий является блокировкой «первым пришел — первым обслужен» [1].

Для тестирования производительности значение счетчика увеличивается до 10000000 с разными типами блокировок, разным количеством потоков и разным количеством раз. Конфигурация тестовой системы: Intel Core I7 (имеет 8 ядер — 4 из них настоящие), Ubuntu 14.04 LTS и Java 1.7.0_60.

Блокировка фильтра имеет n-1 уровней, которые можно рассматривать как «комнаты ожидания». Нить должна пройти через эти комнаты ожидания, прежде чем захватывать замок. Есть два важных свойства для уровней [2]:

  1. По крайней мере, один поток пытается войти на уровень l успешно.
  2. Если более одного потока пытается войти на уровень l , то по крайней мере один из них блокируется (то есть продолжает ожидать на этом уровне).

Блокировка фильтра реализована следующим образом:

01
02
03
04
05
06
07
08
09
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
50
51
/**
* @author Furkan KAMACI
*/
public class Filter extends AbstractDummyLock implements Lock {
/* Due to Java Memory Model, int[] not used for level and victim variables.
Java programming language does not guarantee linearizability, or even sequential consistency,
when reading or writing fields of shared objects
[The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
*/
private AtomicInteger[] level;
private AtomicInteger[] victim;
private int n;
/**
* Constructor for Filter lock
*
* @param n thread count
*/
public Filter(int n) {
this.n = n;
level = new AtomicInteger[n];
victim = new AtomicInteger[n];
for (int i = 0; i < n; i++) {
level[i] = new AtomicInteger();
victim[i] = new AtomicInteger();
}
}
/**
* Acquires the lock.
*/
@Override
public void lock() {
int me = ConcurrencyUtils.getCurrentThreadId();
for (int i = 1; i < n; i++) {
level[me].set(i);
victim[i].set(me);
for (int k = 0; k < n; k++) {
while ((k != me) && (level[k].get() >= i && victim[i].get() == me)) {
//spin wait
}
}
}
}
/**
* Releases the lock.
*/
@Override
public void unlock() {
int me = ConcurrencyUtils.getCurrentThreadId();
level[me].set(0);
}
}

Алгоритм блокировки хлебобулочных изделий поддерживает свойство «первым пришел — первым обслужен», используя распределенную версию машин для выдачи номеров, часто встречающихся в пекарнях: каждый поток занимает номер в дверном проеме, а затем ожидает, пока не попытается ни один поток с более ранним номером ввести его [3].

Пекарский замок реализован следующим образом:

01
02
03
04
05
06
07
08
09
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/**
* @author Furkan KAMACI
*/
public class Bakery extends AbstractDummyLock implements Lock {
/* Due to Java Memory Model, int[] not used for level and victim variables.
Java programming language does not guarantee linearizability, or even sequential consistency,
when reading or writing fields of shared objects
[The Art of Multiprocessor Programming. Maurice Herlihy, Nir Shavit, 2008, pp.61.]
*/
private AtomicBoolean[] flag;
private AtomicInteger[] label;
private int n;
/**
* Constructor for Bakery lock
*
* @param n thread count
*/
public Bakery(int n) {
this.n = n;
flag = new AtomicBoolean[n];
label = new AtomicInteger[n];
for (int i = 0; i < n; i++) {
flag[i] = new AtomicBoolean();
label[i] = new AtomicInteger();
}
}
/**
* Acquires the lock.
*/
@Override
public void lock() {
int i = ConcurrencyUtils.getCurrentThreadId();
flag[i].set(true);
label[i].set(findMaximumElement(label) + 1);
for (int k = 0; k < n; k++) {
while ((k != i) && flag[k].get() && ((label[k].get() < label[i].get()) || ((label[k].get() == label[i].get()) && k < i))) {
//spin wait
}
}
}
/**
* Releases the lock.
*/
@Override
public void unlock() {
flag[ConcurrencyUtils.getCurrentThreadId()].set(false);
}
/**
* Finds maximum element within and {@link java.util.concurrent.atomic.AtomicInteger} array
*
* @param elementArray element array
* @return maximum element
*/
private int findMaximumElement(AtomicInteger[] elementArray) {
int maxValue = Integer.MIN_VALUE;
for (AtomicInteger element : elementArray) {
if (element.get() > maxValue) {
maxValue = element.get();
}
}
return maxValue;
}
}

Для такого рода алгоритмов следует предусмотреть или использовать систему идентификаторов потоков, которая начинается с 0 или 1 и увеличивается по порядку. Имена потоков установлены для этой цели. Следует также учитывать, что: язык программирования Java не гарантирует линеаризуемость или даже последовательную согласованность при чтении или записи полей общих объектов [4]. Итак, переменные уровня и жертвы для блокировки фильтра, переменные флагов и меток для блокировки пекарни определены как атомарные переменные. Тот, кто хочет протестировать эффекты Java Memory Model, может изменить эти переменные на int [] и boolean [] и запустить алгоритм с более чем двумя потоками. Затем можно увидеть, что алгоритм зависнет либо для фильтра, либо для хлебопекарни, даже если потоки живы.

Для тестирования производительности алгоритма реализован пользовательский класс счетчика, который имеет метод getAndIncrement следующим образом:

01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
/**
* gets and increments value up to a maximum number
*
* @return value before increment if it didn't exceed a defined maximum number. Otherwise returns maximum number.
*/
public long getAndIncrement() {
long temp;
lock.lock();
try {
if (value >= maxNumber) {
return value;
}
temp = value;
value = temp + 1;
} finally {
lock.unlock();
}
return temp;
}

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

1
2
3
if (value >= maxNumber) {
return value;
}

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

Эта конфигурация используется для сравнения производительности:

Потоки 1,2,3,4,5,6,7,8
Количество повторов 20
Максимальное количество 10000000

Это таблица результатов, которая включает стандартные ошибки:

сравнение

Прежде всего, когда вы запускаете блок кода в Java несколько раз, происходит внутренняя оптимизация для кодов. Когда алгоритм запускается несколько раз и первый вывод сравнивается со вторым выводом, можно увидеть эффект этой оптимизации. Из-за этого первое прошедшее время должно быть больше второй строки. Например:

1
2
currentTry = 0, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 500 (ms)
currentTry = 1, threadCount = 1, maxNumber = 10000000, lockType = FILTER, elapsedTime = 433 (ms)

Вывод

Из графика видно, что блокировка хлебобулочных изделий выполняется быстрее, чем блокировка фильтров с низкой стандартной ошибкой. Причина — метод блокировки Filter Lock. В блокировке хлебобулочных изделий потоки сбоя выполняются один за другим, а в блокировке фильтров они вычисляются друг с другом. ReentrantLock Java имеет лучшие по сравнению с другими.

С другой стороны, блокировка фильтра линейно ухудшается, а Bakery и ReentrantLock — нет (блокировка фильтра может иметь линейную графику, когда она работает с гораздо большим количеством потоков). Большее количество потоков не означает меньше прошедшего времени. 2 потока могут быть хуже, чем 1 поток из-за создания потока и блокировки / разблокировки. Когда количество потоков начинает увеличиваться, прошедшее время становится лучше для Bakery и ReentrantLock. Однако, когда количество потоков продолжает увеличиваться, становится хуже. Причина — это номер ядра тестового компьютера, на котором работают алгоритмы.

  • Исходный код для реализации фильтра и блокировки хлебобулочных изделий в Java можно скачать здесь: https://github.com/kamaci/filbak
  1. Искусство многопроцессорного программирования. Морис Херлихи, Нир Шавит, 2008, с.31.-33.
  2. Искусство многопроцессорного программирования. Морис Херлихи, Нир Шавит, 2008, с.28.
  3. Искусство многопроцессорного программирования. Морис Херлихи, Нир Шавит, 2008, с.31.
  4. Искусство многопроцессорного программирования. Морис Херлихи, Нир Шавит, 2008, с.61.
Ссылка: Внедрение фильтров и блокировок хлебобулочных изделий на Java от нашего партнера JCG Фуркана Камачи в блоге FURKAN KAMACI .
41
Share: