Powered By Blogger

Thursday, September 27, 2012

Абстрактные типы данных - Бинарные деревья поиска 2


Дерамиды (декартовы деревья)
Вставка в декартово дерево
Удаление из декартова дерева
Заключение
Из предыдущей статьи "Абстрактные типы данных - Бинарные деревья поиска" Вы узнали, что бинарные деревья поиска являются мощной структурой данных для поиска и выборки данных. Бинарные деревья поиска могут быть довольно простыми, как и операции на них. Над бинарными деревьями возможны и более сложные операции. Однако, реализация более сложных операций не всегда так проста. В особенности, когда речь идёт о вращениях и прочих структурных преобразованиях дерева. Я также указывал уже на то, что в некоторых определённых случаях базовые алгоритмы на бинарных деревьях могут быть крайне неэфективны. Можно выделить три наихудших случая: данные, поступающие на вход, упорядочены по возрастанию:
bst2_0
Добавляемые данные отсортированы в убывающем порядке:
bst2_1
Или, наконец, чередующийся порядок, задом наперёд:
bst2_2
Ни в одном из этих случаев эффективность поиска на бинарном дереве не будет высокой, потому что структурно дерево, содержащее эти данные, эквивалентно связному списку. Эффективность поиска O(log N) вырождается в O(N). Учитывая то, что наибольший выигрыш от использования бинарных деревьев поиска достигается при работе с большими объёмами данных, результатом будет серьёзное падение производительности. К сожалению, классические методы поддержания дерева в оптимальном состоянии дико сложны. Простое решение - изучить усреднённый показатель эффективности на неком бинарном дереве поиска.
В среднем эффективность базового бинарного дерева поиска составляет O(log N). Здесь "в среднем" означает, что данные, поступающие на вход, достаточно случайны, чтобы создать то, что называется "рандомизированным бинарным деревом" (ну или случайным, уж простите за вольность), в котором каждый новый элемент данных с вероятностью 1/N будет помещён в корень произвольного поддерева:
Наиболее очевидный способ создания рандомизированного бинарного дерева - случайная перетасовка входящих данных. Но в большинстве случаев мы не имеем сразу доступа ко всем данным, которые должны храниться в дереве в данный момент времени. На самом деле, чаще всего мы будем добавлять по одному элементу данных из потока. Это крайне усложняет задачу перемешивания данных ещё до их добавления в дерево.
Случайное бинарное дерево может быть создано, если каждый элемент набора данных имеет одинаковые шансы стать вершиной поддерева. Мы можем прибегнуть к упомянутым в предыдущей статье функциям вставки в вершину. При каждой вставке мы можем случайным образом использовать вставку в вершину или обычную вставку. Таким образом мы получим случайное бинарное дерево. Алгоритм выглядит неплохо и на удивление прост для реализации. В реализации нашего алгоритма будем использовать структуры struct node и struct tree, описанные в предыдущей статье:

1 struct node {
2         struct node* link[2];
3         int data;
4 };
5
6 struct tree {
7         struct node* root;
8         size_t size;
9 };

Возьмём простую рекурсивную вставку на основе функций из предыдущей статьи "Абстрактные типы данных - Бинарные деревья поиска":

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else {
 6                 int dir = root->data < key;
 7                 root->link[dir] = insert_r (root->link[dir], item, key);
 8         }
 9
10         return root;
11 }
12
13 void insert (struct tree* tree, struct node* item, int key)
14 {
15         tree->root = insert_r (tree->root, item, key);
16         ++tree->size;
17 }

Предполагая сортированные данные на входе, используя этот алгоритм мы получим вырожденное дерево. Однако, два простых изменения помогут сократить вероятность вырождения дерева до пренебрежительно малого значения. Первая модификация: добавим аргумент sz в прототипе insert_r(). Начальное значение этого аргумента будет задаваться с помощью tree->size в insert(). При каждом рекурсивном вызове insert_r() будет передаваться половина данного значения, которое является грубой оценкой числа элементов в поддереве.
Вторая модификация: вставка в вершину; текущее поддерево будет вершиной в которую производится вставка. Вставка в вершину будет сделана с вероятностью 1/sz. В общем и в целом, подразумевая, что у нас есть функция root_insert(), изменения, сделанные нами в изначальном коде insert_r() и insert() будут выглядеть следующим образом:

 1 struct node* insert_r (struct node* root, struct node* item, int key, int sz)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else if (rand () % (sz + 1) == sz)        /* Вероятность 1/sz */
 6                 root = root_insert (root, item, key);
 7         else {
 8                 int dir = root->data < key;
 9                 root->link [dir] = insert_r (root->link [dir], item, key, sz / 2);
10         }
11
12         return root;
13 }
14
15 void insert (struct tree* tree, struct node* item, int key)
16 {
17         tree->root = insert_r (tree->root, item, key, tree->size);
18         ++tree->size;
19 }

Здесь мы используем вероятно не лучший источник случайных чисел, однако, на данный момент так будет проще. По поводу достоинств разных источников энтропии и их использования см. Random Numbers tutorial (eternallyconfuzzled.com). Пока же мы ограничимся функцией стандартной библиотеки.
Предположения о существовании root_insert() было достаточно на этапе "проектирования", но в реальном коде нам будет полезна конкретная реализация. Не вдаваясь в детали, возьмём такую примерную реализацию:

 1 struct node* root_insert (struct node* root, struct node* item, int key)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else {
 6                 struct node* save;
 7                 int dir = root->data < key;
 8
 9                 root->link [dir] = root_insert (root->link [dir], item, key);
10
11                 /* Поворот относительно вершины */
12                 save = root->link [dir];
13                 root->link [dir] = save->link [!dir];
14                 save->link [!dir] = root;
15                 root = save;
16         }
17
18         return root;
19 }

В этих функциях нет ничего нового, так что у любого, кто читал "Абстрактные типы данных - Бинарные деревья поиска", проблем с ними возникнуть не должно.
Альтернативой обычной вставке с поднятием нового элемета данных в выбранную с некоторой вероятностью вершину является вероятностное объединение поддеревьев. Этот метод используется в "официальных" реализациях случайных бинарных деревьев поиска, как описано у Martinez и Roura. Алгоритмы вставки на верхнем уровне не особо изменились и в целом уже знакомы нам:

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         int n = (root == NULL) ? 0 : root->size;
 4
 5         if (rand () % (n + 1) == n)
 6                 return root_insert (root, item);
 7         else {
 8                 int dir = root->data < key;
 9                 root->link [dir] = insert_r (root->link [dir], item, key);
10                 ++root->size;
11         }
12
13         return root;
14 }
15 
16 void insert (struct tree* tree, struct node* item, int key)
17 {
18         tree->root = insert_r (tree->root, item, key);
19 }

Вместо поиска вершины root со значением NULL единственным фактором при решении о месте вставки становится оценка вероятности. Заметьте, что вершина - это терминальный узел, n будет равно 0 и оценка вероятности будет такой, как нам и надо. Таким образом симулируется обычная вставка листового узла. Условия для предельного случая вставки на терминальном узле гарантированно соблюдаются.
Операция объединения будет выполняться функцией root_insert() с помощью split(). root_insert() не производит поиск; вместо этого она просто резервирует место для нового элемента и объединяет с деревом на выбранной вершине. Такая операция может быть непростой, ведь небходимо гарантировать что дерево останется правильно построенным бинарным деревом. Поэтому split() должна быть рекурсивной функцией, чтобы выполнять очистку на поддереве, присоединённом к данной вершине. Естественно функция split() не обязана быть рекурсивной, но в данном случае рекурсия - это то, что делает жизнь легче:

 1 void split (struct node* root, struct node* item, struct node** s, struct node** g)
 2 {
 3         if (root == NULL)
 4                 *s = *g = NULL;
 5         else if (item->data < root->data) {
 6                 *g = root;
 7                 split (root->link [0], item, s, &((*g)->link [0]));
 8         } else {
 9                 *s = root;
10                 split (root->link [1], item, &((*s)->link [1]), g);
11         }
12 }
13 
14 struct node* root_insert (struct node* root, struct node* item)
15 {
16         struct node *s, *g;
17
18         split (root, item, &s, &g);
19
20         root = item;
21         root->link [0] = s;
22         root->link [1] = g;
23         root->size = 1;
24
25         root->size += s == NULL ? 0 : s->size;
26         root->size += g == NULL ? 0 : g->size;
27
28         return root;
29 }

Такая реализация функции root_insert() крайне проста. Большую часть работы она передаёт split(). root_insert() просто берёт результат выполнения split() и присоединяет полученный элемент к вершине root, попутно убеждаясь, что размеры изменены корректно и соответствуют структурным изменениям в поддереве. split() несколько сложнее. В частности то, как она рекурсивно обеспечивает правильную структуру дерева. Рассмотрим следующий пример:
bst2_3
Скажем, мы хотим добавить в дерево узел c. split() нужно зарезервировать место для c, не нарушая структуру инвариантность бинарного дерева. Это достигается разделением двух поддеревьев нового узла без потери инвариантности. Здесь приведён пример разбиения поддеревьев для добавления узла с. Важным для для понимания алгоритма является момент, что каждый рекурсивный вызов оперирует на дочерних узлах s или g. (! обозначает текущий узел, ? - неопределённый указатель, ~ - NULL-указатель):
bst2_4


bst2_5


bst2_6


bst2_7


bst2_8
После того, как split() разбила дерево, отдельные части выглядят приблизительно как на следующей диаграмме. Теперь всё, что осталось root_insert(), использовать s и g для реструктуризации дерева. Попробуйте пройтись по коду самостоятельно и проверьте правильность результата:
bst2_9
Все эти трюки служат одной цели - сохранить инвариантность дерева, т.е., гарантию того, что каждый элемент по-прежнему имеет больший ключ, чем вершина его левого поддерева и меньший, чем его вершина его правого поддерева. Без этого нам бы пришлось использовать вставку у листа и вращения, чтобы избежать сложных проблем, связанных с коррекцией объединения.
Заметьте: такая реализация insert() допускает повторение ключей. Есть несколько способов избавиться от дубликатов, начиная с самых простых, но не очень эффективных, до довольно сложных, но очень быстрых. При объединении самое простое решение - вызов find() перед каждой операцией вставки:

1 int insert (struct tree* tree, struct node* item, int key)
2 {
3         if (find (tree, key))
4                 return 0;
5
6         tree->root = insert_r (tree->root, item, key);
7
8         return 1;
9 }

Удаление из такого рандомизированного бинарного дерева - это "просто" операция, обратная разбиению, метко названная объединением. Код функции remove на данный момент будет выглядеть так:

 1 struct node* remove_r (struct node* root, struct node** old_item, int key)
 2 {
 3         struct node* save;
 4
 5         if (root != NULL) {
 6                 if (key == root->data) {
 7                         save = join (root->link [0], root->link [1]);
 8                         *old_item = root;
 9                         root = save;
10                 } else {
11                         int dir = root->data < key;
12                         root->link [dir] = remove_r (root->link [dir], old_item, key);
13                         --root->size;
14                 }
15         }
16
17         return root;
18 }
19
20 int remove (struct tree* tree, struct node** old_item, int key)
21 {
22         if (!find (tree, key))
23                 return 0;
24
25         tree->root = remove_r (tree->root, old_item, key);
26
27         return 1;
28 }

join() удаляет вершину root и заново соединяет структуры с помощью ссылок, сохраняя правильное построение рандомизированного бинарного дерева поиска, так что мы и дальше можем пользоваться оценкой вероятности. Код лаконичен, но возможно не совсем ясен:

 1 struct node* join (struct node* left, struct node* right)
 2 {
 3         int ln = left == NULL ? 0 : left->size;
 4         int rn = right == NULL ? 0 : right->size;
 5
 6         if (ln + rn == 0)
 7                 return NULL;
 8         else if (rand () % (ln + rn) < ln) {
 9                 left->link [1] = join (left->link [1], right);
10                 left->size += rn;
11                 return left;
12         } else {
13                 right->link [0] = join (left, right->link [0]);
14                 right->size += ln;
15                 return right;
16         }
17 }

Чтобы на примере рассмотреть работу функции join(), возьмём такое же дерево, как для примера со split(). Однако на сей раз мы будем удалять узел e вместо добавления c к e:
bst2_10
Принимая в качестве аргументов ссылки узла g (d и h), join() сначала проверяет, был ли узел g терминальным. С этой целью функция вычисляет сумму размеров поддеревьев узла. Если g был терминальным узлом, мы может просто заменить его указателем на NULL. Однако, в нашем случае у g есть два дочерних узла, так что придётся проделать чуть больше работы. Используя вероятность так же, как при вставке (1/sz), join() рекурсивно вызывает сама себя в поисках подходящей замены, основываясь на значении вероятности. Допустим, выбрано правое направление, тогда наше дерево примет такой вид:
bst2_11
Если бы был выбран левый путь, окончательная структура дерева выглядела бы так:
bst2_12
Так как трассировка выполнения этого алгоритма тривиальна, а трассировка рекурсивного алгоритма к тому же хорошая практика, я оставляю вам выяснение того, как алгоритм создаёт окончательную структуру представленных деревьев.

Дерамиды (декартовы деревья) [наверх]

Вычурно названные дерамиды являются структурой данных, совмещающих в себе свойства бинарной кучи и бинарного дерева поиска (вообще, этот АТД наверно более известен под названием "декартово дерево"). Если генерируемый для кучи приоритет - случайное число, то результат такой гибрилизации - на удивление хорошо сбалансированное рандомизированное бинарное дерево поиска. Дерамида (далее всё-таки буду придерживаться более распространённого названия в русскоязычной среде - "декартово дерево") должна подчиняться двум жёстким правилам:
Как бинарное дерево (для u с левым дочерним узлом v и правым - w):

1 v->data < u->data < w->data

Как куча:

1 w->priority < v->priority < u->priority

При присвоении приоритетам случайных значений или хэшировании данных с одной стороны и соблюдении условий для бинарной кучи и дерева мы получаем прекрасную возможность построить хорошо сбалансированное дерево. В худшем случае его эффективность всё же будет линейно зависеть от числа элементов O(n), как и в случае прочих разновидностей рандомизированного бинарного дерева. Однако вероятность вырождения дерева не так велика. Там, где гарантия лучшего случая не является необязательной, декартово дерево демонстрирует приемлемую эффективность и его легко реализовать.

Вставка в декартово дерево [наверх]

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

 1 struct node {
 2         struct node* link [2];
 3         int priority;
 4         int data;
 5 };
 6
 7 struct node NullItem = { &NullItem, &NullItem, RAND_MAX, 0 };
 8 struct node *Null = &NullItem;
 9
10 struct tree {
11         struct node *root;
12 };

Мы добавили поле приоритета. Кроме того, я определил две глобальные переменные типа struct node, проинициализированные предельными значениями, и указателями на себя. Наше декартово дерево будет использовать Null вместо NULL для обозначения терминального листа. Это выглядит, как необязательная модификация, но это изменение сильно упрощает алгоритм удаления.
Рекурсивный алгоритм вставки, реализованный в insert для декартова дерева - сама простота:

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         if (root == Null)
 4                 root = item;
 5         else {
 6                 int dir = root->data < key;
 7
 8                 root->link[dir] = insert_r (root->link [dir], item, key);
 9
10                 if (root->priority < root->link [dir]->priority) {
11                         struct node* save = root->link [dir];
12                         root->link [dir] = save->link [!dir];
13                         save->link [!dir] = root;
14                         root = save;
15                 }
16         }
17
18         return root;
19 }
20 
21 void insert (struct tree* tree, struct node* item, int key)
22 {
23         tree->root = insert_r (tree->root, item, key);
24 }

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

 1 if (key < root->data) {
 2         root->link [0] = insert_r (root->link [0], item, key);
 3
 4         if (root->priority < root->link [0]->priority) {
 5                 struct node* save = root->link [0];
 6                 root->link [0] = save->link [1];
 7                 save->link [1] = root;
 8                 root = save;
 9         }
10 } else {
11         root->link [1] = insert_r (root->link [1], item, key);
12
13         if (root->priority < root->link [1]->priority) {
14                 struct node* save = root->link [1];
15                 root->link [1] = save->link [0];
16                 save->link [0] = root;
17                 root = save;
18         }
19 }

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

 1 int insert (struct tree* tree, struct node* item, int key)
 2 {
 3         struct node* walk;
 4         struct node* up [50];
 5         int dir;
 6         int top = 0;
 7
 8         /* Дерево пустое */
 9         if (tree->root == Null) {
10                 tree->root = item;
11                 return 1;
12         }
13
14         /* Поиск пустой ссылки */
15         walk = tree->root;
16
17         for ( ; ; ) {
18                 if (walk->data == key)
19                         return 0;
20
21                 dir = walk->data < key;
22
23                 if (walk->link[dir] == Null)
24                         break;
25
26                 up [top++] = walk;
27                 walk = walk->link [dir];
28         }
29
30         /* Вставка нового элемента */
31         walk->link [dir] = item;
32
33         /* Проход в обратном направлении и вращение */
34         while (item != tree->root) {
35                 if (walk->priority > item->priority)
36                         break;
37
38                 dir = item == walk->link [1];
39                 walk->link [dir] = item->link [!dir];
40                 item->link [!dir] = walk;
41
42                 /* Применяем изменения к остальным частям дерева */
43                 if (top > 0 && up [top - 1] != Null) {
44                         dir = (walk == up [top - 1]->link [1]);
45                         up [top - 1]->link [dir] = item;
46                 }
47
48                 /* Сброс вершины, если надо */
49                 if (tree->root == walk)
50                         tree->root = item;
51
52                 /* Двигаемся вверх и начинаем новый проход */
53                 walk = up [--top];
54         }
55 
56         return 1;
57 }

Очевидно, что это просто копипаст из "Абстрактные типы данных - Бинарные деревья поиска" с небольшими изменениями для обеспечения соблюдения свойств бинарной кучи. Что может быть проще, чем позаимствовать готовый код и адаптировать его под свои нужды?

Удаление из декартова дерева [наверх]

Удаление узла - не такая важная операция, как вставка и часто её обходят без упоминания. Хотя я согласен с таким подходом, но всё же приведу небольшой кусочек кода, если он может оказаться полезным. Это чувство у меня появилось во времена тщетных попыток вывести полезный код удаления из примеров, когда я сам изучал структуры данных. Алгоритм удаления из декартова дерева в точности противоположен вставке, удивительно, но факт. Нам нужно нати элемент данных и произвести поворот (нисходя далее по дереву от нашего элемента), пока не достигнут лист, а затем наш элемент просто удаляется. Операция обычно называется "проталкиванием вниз" (продавливанием?), что лишь в очередной раз подтверждает наличие отсутствие особой фантазии у учёных, работающих в области теории вычислительных машин и систем. Алгоритм краток:

 1 struct node* remove_r (struct node* root, struct node** old_item, int key)
 2 {
 3         if (root != Null) {
 4                 struct node* save;
 5
 6                 if (key == root->data) {
 7                         int dir = root->link [0]->priority > root->link [1]->priority;
 8
 9                         save = root->link [dir];
10                         root->link [dir] = save->link [!dir];
11                         save->link [!dir] = root;
12                         root = save;
13
14                         if (root != Null)
15                                 root = remove_r (root, old_item, key);
16                         else {
17                                 *old_item = root->link [1];
18                                 root->link [1] = Null;
19                         }
20                 }
21                 else {
22                         int dir = root->data < key;
23                         root->link [dir] = remove_r (root->link [dir], old_item, key);
24                 }
25         }
26 
27         return root;
28 }
29 
30 void remove (struct tree* tree, struct node** old_item, int key)
31 {
32         tree->root = remove_r (tree->root, old_item, key);
33 }

Поиск прост: если корень root не является терминальным узлом, двигаемся влево или право, соответственно. Иначе, совершаем поворот в соответствующем направлении и рекурсивно идём дальше, пока root не станет терминальным узлом. Если root является терминальным узлом, то простая его замена на Null достаточна для удаления узла из дерева. После удаления алгоритм должен пройти в обратном направлении вверх и исправить испорченные ссылки.
Изучив этот код, Вы увидите, почему я предпочитаю специальные метки вместо простого указателя на NULL чтобы отметить терминальный узел. Если бы я использовал NULL-указатели, следующий кусок кода наверняка спровоцировал бы ошибку, т.к. при разыменовании root содержит неверный указатель.

1 if (root != Null)
2         root = remove_r (root, old_item, key);
3 else {
4         *old_item = root->link [1];
5         root->link [1] = Null;
6 }

Заключение [наверх]

Бинарные деревья поиска хороши для начала, но при этом имеющие место худшие случаи для них действительно худшие и что немаловажно, они отнюдь не редки. Используя рандомизацию при добавлении данных в дерево мы можем избегать худших случаев большу часть времени. Хотя я затронул лишь три вариации рандомизированных деревьев, на самом деле их больше. Не должно пройти незамеченным и сходство с алгоритмом быстрой сортировки. Базовый алгоритм быстрой сортировки похож на алгоритмы на базовых бинарных деревьях поиска: быстрый, но с такими же худшими случаями, коотрые очень сильно бьют по эффективности. Использование рандомизации в алгоритмах быстрой сортировки, и алгоритмах на бинарных деревьях поиска помогает минимизировать вероятность возникновения ситуаций, развивающихся по наихудшему сценарию. Таким образом эти алгоритмы становятся более полезными для среднестатистического программиста, причём особых усилий такое усовершенствование не требует.
Оригинал этой статьи вы можете найти здесь: eternallyconfuzzled.com.
mind_fuck

Wednesday, March 7, 2012

Примитивы синхронизации ядра - RCU

1. Авторские права и уведомления
2. Введение
2.1. Что такое механизм чтения-копирования при обновлении (RCU)?
2.2. Почему именно RCU?
2.3. Дополнительные источники
3. Описание примитивов RCU
3.1. struct rcu_head
3.2. call_rcu()
3.3. synchronize_kernel
3.4. Использование барьеров памяти
4. Применения RCU
4.1. RCU в хэш-таблице со счётчиком ссылок refcnt
4.2. Использование RCU совместно с kmem_cache_free()

1. Авторские права и уведомления [наверх]

Copyright © 2001 IBM Corporation. Авторские права защищены.

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

Данный документ предоставляется "AS IS," ("как есть") без каких-либо явных или подразумеваемых гарантий. Используя информацию из данного документа, вы действуете на свой страх и риск.

Особые замечания:

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

2. Введение [наверх]

Данный документ описывает использование механизма чтения-копирования при обновлении (Read-Copy Update, RCU) в ядре Linux для реализации масштабируемых взаимных исключений. Здесь приводятся примеры и пояснения относительно интерфейса. Также поясняется, как экономить циклы используя RCU.

2.1. Что такое механизм чтения-копирования при обновлении (RCU)? [наверх]

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

Механизм чтения-копирования при обновлении (далее по тексту просто RCU для краткости) является одним из таких методов взаимного исключения, при котором читающие потоки (потоки, получающие доступ к данным, но не модифицирующие их) могут обращаться к разделяемым структурам без захвата традиционной блокировки. В то же самое время пишущие потоки (потоки, модифицирующие данные) используют особую схему обратного вызова для обновления данных. Все глобальные ссылки на модифицируемые данные обновляются и замещаются ссылками на изменённые данные. Механизм обратного вызова используется для освобождения старых копий данных после того, как все процессоры в системе теряют локальные ссылки на разделяемые данные при переходе в неактивное состояние (например, переключение контекста). Т.к. обеспечение доступа для записи более затратно по сравнению с обеспечением доступа по чтению, RCU наиболее подходит для осуществления сценариев, когда защищаемые данные чаще считываются, чем изменяются. На однопроцессорных системах RCU можно использовать, как альтернативу маскированию прерываний для обеспечения взаимного исключения. Т.о., RCU хорошо подходит для использования при обслуживании таблиц марштрутизации сетевых пакетов, таблиц состояний устройств, отложенного удаления структур данных, обеспечения многопутевого ввода-вывода (multi-path I/O) и т.д..

Изначально механизм RCU был разработан для DYNIX/ptx, вариант UNIX от Sequent Computer Systems Inc., ныне часть IBM. Сходные методы были использованы в проектах Tornado и K42 в универститете Торонто и исследованиях IBM.

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

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

2.2. Почему именно RCU? [наверх]

Ниже приводятся доводы, почему вам следует использовать механизм RCU, а также объясняются мотивы начала разработок в этом направлении.

Растущая цена традиционных блокировок

Скорости процессоров увеличиваются в 1,5-2 раза каждый год. Однако, рост скорости соединений (цепи на печатных платах и шины) составляет где-то лишь на 15% в год. Т.о., рост издержек использования традиционных блокировок стимулирует введение таких схем взаимного исключения, которые бы не зависели так сильно от путей коммуникации между относительно быстрыми процессорами.

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

Устранение сложноразрешимых ситуаций гонок

Механизм RCU не несёт риска взаимных блокировок (deadlocks), в отличие от явных блокировок. Снижение такого рода риска позволяет сократить или вовсе избежать использования избыточного кода, который бы потребовался в противном случае для отслеживания и исправления, а также предотвращения взаимных блокировок. Это, в свою очередь, снижает стоимость разработки и обслуживания программного обеспечения.

Оптимальное использование кэширования при неблокирующем чтении

Устраняя необходимость взведения блокировок при операциях чтения RCU позволяет избежать забивания строк кэша, которые бы использовались для обеспечения блокировок. В случаях, когда данные чаще читаются, такая безблокировочная система заметно выгоднее. Одним из примеров может служить синтетический тест производительности - "chat", где множество клонированных задач разделяют между собой данные в files_struct. Даже при использовании блокировки чтение-запись в процессе чтения файла через fget(), слишком интенсивное использование строк кэша для обеспечения самих блокировок ощутимо снижает эффективность системы при большом числе процессоров. Используя RCU, fget() может обращаться к указателю на файл без захвата блокировок, что существенно улучшит производительность системы.

2.3. Дополнительные источники [наверх]

Дополнительную информацию об RCU вы можете найти на домашней странице RCU http://lse.sourceforge.net/locking/rcupdate.html. Техническое описание реализации RCU в Linux было опубликовано на Linux-симпозиуме в Оттаве Ottawa в 2001. Этот документ можно найти здесь: http://lse.sourceforge.net/locking/rclock_OLS.2001.05.01c.sc.pdf.

3. Описание примитивов RCU [наверх]

RCU состоит из интерфейса, который регистрирует функцию обратного вызова. Эта функция вызывается, когда все процессоры в системе прошли через одно из "состояний покоя" (переключение контекста, холостой цикл или переключение на пользовательский код). Данная функция может быть использоваться для обновления разделяемых структур данных. Однако, единовременно не может быть произведено более одной операции обновления, поэтому сами обновления должны происходить последовательно и управляться каким-либо традиционным механизмом взаимоисключения. Типичный код функции обновления должен следовать нижеописанным шагам:

  1. Захват блокировки.
  2. Обновление глобального указателя на данные (struct rcu_head) либо новым значением - адресом блока новых данных, либо NULL. После этого шага любой новый поток ядра, выполняемый на другом процессоре, увидит только новый указатель.
  3. Передача управления функции обратного вызова (call_rcu) для освобождения копии старых данных после прохождения всеми процессорами состояния покоя. Данный шаг гарантирует, что после удаления копии старых данных ни один из процессоров не будет ссылаться на эти данные.
  4. Освобождение блокировки механизма обновления.

Необходимые определения находятся в заголовочном файле linux/rcupdate.h.

3.1. struct rcu_head [наверх]

Эта структура содержит всю необходимую для RCU информацию, которая используется для выполнения очередных обновлений. Каждая операция обновления описывается одной структурой типа struct rcu_head. Как правило, rcu_head внедряется в ту структуру, которая использует RCU для обновлений и поиска содержащихся в ней данных.

        struct rcu_head {
                struct list_head list;
                void (*func)(void *obj);
                void *arg;
        };


        #define RCU_HEAD_INIT(head) \
                { LIST_HEAD_INIT(head.list), NULL, NULL }
        #define RCU_HEAD(head) \
                struct rcu_head head = RCU_HEAD_INIT(head)
        #define INIT_RCU_HEAD(ptr) do { \
                        INIT_LIST_HEAD(&(ptr)->list); (ptr)->func = NULL; \
                        (ptr)->arg = NULL; \
                } while (0)

3.2. call_rcu() [наверх]

void call_rcu(struct, rcu_head, *head, void, (*func) (void, *head) );

call_rcu вызывает callback-функцию func после того, как все процессоры прошли хотя бы через одно состояние покоя. В целях обеспечения лучшей производительности хорошая реализация RCU не дожидается завершения цикла покоя. Вместо ожидания код такой реализации помещает функцию в очередь и возвращает управение. Все функции обратного вызова будут выполнены пакетом когда все процессоры в системе пройдут хотя бы одно из состояний покоя. Функция обратного вызова может получить управление в контексте обработки нижней половины прерывания. Пользователь должен принимать это во внимание.

3.3. synchronize_kernel [наверх]

void synchronize_kernel(void);
Данная функция интерфейса ждёт, когда все процессоры в системе пройдут через состояние покоя, вроде переключения контекста. Этот вызов блокирует выполнение вызывающего потока, поэтому он может быть использован только в контексте процесса. Вызов этой функции из контекста процесса полезен в ситуациях, когда производительность операции обновления данных RCU не критична. Например, выгрузка модуля не критична в плане производительности, поэтому использование этого интерфейса допустимо, если мы имеем дело с данными, защищёнными RCU.

3.4. Использование барьеров памяти [наверх]

Порядок выполнения операций чтения и записи неявно обеспечивается в критических секциях, защищаемых традиционными механизмами блокировки. Однако при безблокировочном чтении данных в случае RCU важно обеспечить явный порядок процессорных операций доступа к памяти. Ядро Linux предоставляет множество функций, реализующих барьеры памяти. Наиболее часто используемые при работе с RCU функции: wmb() и rmb().

Примечение: в будущих версиях ядра имена этих функций могут быть изменены на write_barrier() и read_barrier() соответственно.

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

На стороне обновляющего кода:

  • Пометить элемент данных, как устаревший
  • Удалить его из списка
  • Запланировать выполнение функции обратного вызова RCU, чтобы удалить данные после цикла покоя

В читающем коде:

  • Для каждого элемента данных
    Если элемент данных element устарел - продолжить
  • если element->value == key
    возвратить element;

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

Пометить элемент данных element, как устаревший
wmb(); /* write_barrier() later */
Удалить элемент данных из списка
Запланировать вызов callback-функции для удаления данных после цикла покоя

Например, на процессорах типа DEC Alpha, wmb() не гарантирует, что записи будут видны читающему коду в том порядке, в каком они должны быть согласно логике пишущего кода, даже в том случае, если есть некая зависимость данных (установка указателя на элемент в начале цикла и использование этого указателя в теле цикла). На таких архитектурах порядок чтения должен быть обеспечен явным образом с помощью rmb():

Для каждого элемента
        rmb();
        если элемент element неактуален
                продолжить
        если element->value == key
                возвратить element;

На большинстве процессорных архитектур порядок обеспечивается по умолчанию, если есть зависимость данных. Чтобы избежать ненужных операций разрабатывается интерфейс read_barrier_depends(). Эта функция предусматривает rmb() только для архитектуры Alpha.

4. Применения RCU [наверх]

В этом разделе описывается несколько примеров применения механизма RCU.

4.1. RCU в хэш-таблице со счётчиком ссылок refcnt [наверх]

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

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

struct element {
        struct element *next;
        struct element *prev;
        atomic_t refcnt;
        int address;
        int data;
        struct rcu_head rcu;
};

/*
 * Ищет элемент с данным адресом, захватывает его блокировку и возвращает указатель на него.
 * Возвращает NULL если такой адрес не был найден.
 */
struct element *search(int addr)
{
        struct element *p;
        struct element *p0;

        p0 = &head[hashit(addr)];
        rmb(); /* read_barrier_depends() */
        p = p0->next;

        while (p != p0) {
                rmb(); /* read_barrier_depends() */

                if (p->address == addr) {
                        atomic_inc(&p->refcnt);
                        return (p);
                }

                p = p->next;
        }

        return ((struct element *)NULL);
}

/*
 * Вставка нового элемента в хэш-таблицу
 */
void insert(struct element *element)
{
        struct element *p0;

        p0 = &head [hashit(p->addr)];
        p->next = p0->next;

        /*
         * Необходимо убедиться, что следующий указатель добавленных данных
         * видим всем другим процессорам до собственно вставки. Это позволит
         * обеспечить безблокировочный поиск узла данных во всём списке.
         */
        wmb();
        p0->next = p;
}

void myfree(void *obj)
{
        struct element *p = obj;

        /*
         * Теперь мы можем безопасно проверить счётчик ссылок refcnt,
         * т.к. никто больше не воспользуется неактуальным указателем
         * на данный элемент после безблокировочного поиска через
         * search().
         */
        if (atomic_read(&p->refcnt)) {
                /*
                 * Позволим другому механизму сборки мусора
                 * удалить его.
                 */
                return;
        }

        kfree(obj);
}

/*
 * Удаляем указанный элемент из таблицы. Элемент должен быть под блокировкой.
 */
void delete(struct element *p)
{
        /*
         * Захватываем глобальную блокировку. Возможности взаимной блокировки нет,
         * т.к. глобальная блокировка всегда захватывается после взведения блокировки
         * отдельного элемента.
         */

        spin_lock(&hash_lock);

        /*
         * Удаляем элемент данных из списка, освобождаем блокировку,
         * удаляем элемент из памяти и возвращаем управление.
         */
        p->next->prev = p->prev;
        p->prev->next = p->next;
        spin_unlock(&hash_lock);

        call_rcu(&p->rcu, myfree, p);
        return;
}

4.2. Использование RCU совместно с kmem_cache_free() [наверх]

В отличие от [kv]free(), kmem_cache_free() требует дополнительного параметра в виде указателя на кэш, из которого был захвачен блок памяти. При использовании RCU это может быть проблемой, потому что мы имеем дело с обычным указателем (не структурой). Вы можете избежать этой проблемы, используя специальную функцию-деструктор для каждого кэша, который требует отложенного освобождения памяти. Если указатель на кэш - глобальная переменная, функция-деструктор может использовать эту переменную напрямую и вызывать kmem_cache_free() из функции обратного вызова. В ином случае внедрить указатель на кэш можно вместе с указателем на структуру типа struct rcu_head в данные, которые должны удаляться, так, что функция-деструктор сможет получить необходимую информацию оттуда.

Для случая с глобальным указателем на кэш наша функция будет выглядеть так:

static kmem_cache_t xxx_cache;

struct xxx_entry {
        struct xxx_entry *next;
        struct xxx_entry *prev;
        int flag;
        int info;
        struct rcu_head rch;
}

void xxx_destroy(void *ptr)
{
        struct xxx_entry *xp = (struct xxx_entry *)ptr;
        kmem_cache_free(&xxx_cache, (void *)xp);
}

void xxx_delete(struct xxx *xp)
{
        call_rcu(&xp->rch, xxx_destroy, xp);
}

Если указатель на кэш недоступен глобально, его можно внедрить в структуру данных и работать с ним при освобождении памяти, как показано ниже:

struct xxx_entry {
        struct xxx_entry *next;
        struct xxx_entry *prev;
        int flag;
        int info;
        kmem_cache_t *cachep;
        struct rcu_head rch;
}

void xxx_destroy(void *ptr)
{
        struct xxx_entry *xp = (struct xxx_entry *)ptr;
        kmem_cache_free(&xp->cachep, (void *)xp);
}

void xxx_delete(struct xxx *xp)
{
        call_rcu(&xp->rch, xxx_destroy, xp);
}

ПОСЕТИТЕЛИ

free counters