O Torvalds Linus

Сайт о *nix системах и всем что с ними связано

Возможно, вы желаете знать, откуда взялась константа 0х9еЗ 70001 (= 2 654 404 609). Данная хеш – функция основана на умножении индекса на подходящее большое число с такой целью, чтобы результат вызвал переполнение, и значение 32 – битовой переменной можно было считать результатом операции деления с остатком. Кнут предположил, что хорошие результаты можно получить, когда большой сомножитель является простым числом, примерно равным золотому сечению от 232 (32 бита —это размер регистров в архитектуре 80×86). Число 2 654 404 609 является простым, близким к 232х(л/5 —1)/2. Кроме того, на него легко умножать, выполняя сложение и сдвиг битов, потому что оно равно 231 + 229-225 + 222-219-216 + 1.

Функция не гарантирует взаимно-однозначного соответствия между идентификаторами процессов и табличными индексами.Каждая запись таблицы является головой двунаправленного списка конфликтующих идентификаторов процессов. На рис. 3.5 изображена хеш – таблица идентификаторов процессов, имеющая два списка. Процессы с идентификаторами 2890 и 29 384 отображаются в двухсотый элемент таблицы, а процесс с идентификатором 29 385 —в элемент 1466.

Хеширование с применением цепных списков предпочтительнее линейного преобразования идентификаторов процессов в табличные индексы, потому что в любой момент времени количество процессов в системе, как правило, намного меньше, чем 32 768 (максимальное количество допустимых идентификаторов процессов). Было бы неразумно тратить память на таблицу из 32 768 записей, если в каждый момент времени большинство из них останется неиспользованным.

Структуры данных, используемые в хеш – таблицах идентификаторов процессов, довольно сложны, потому что они должны отражать взаимоотношения между процессами. В качестве примера предположим, что ядро должно выбрать все процессы, принадлежащие данной группе потоков, т. е. все процессы, у которых поле tgid равно заданному числу. Поиск в хеш – таблице по заданному номеру группы потоков возвратит только один дескриптор процесса, а именно дескриптор лидера группы потоков. Чтобы быстро получить остальные процессы в группе, ядро должно поддерживать список процессов для каждой группы потоков. Аналогичная ситуация возникает при поиске процессов, принадлежащих заданному сеансу или заданной группе процессов.

Структуры данных в хеш – таблицах решают все эти проблемы, потому что они позволяют определить список процессов для любого идентификатора процесса, включенного в хеш – таблицу. Основной структурой является массив из четырех структур pid, встроенный в поле pids дескриптора процесса. Основанный на хеш – таблице pidtype tgid. Второй элемент массива pid hash хранит адрес хеш – таблицы, т. е. массива структур hiist head, являющихся головами цепных списков. В цепном списке, растущем из 71 – й записи хеш – таблицы, находятся два дескриптора процессов, соответствующие идентификаторам процессов 246 и 4351 (двойные стрелки представляют пары указателей вперед/назад). Идентификаторы процессов хранятся в поле nr структуры pid, встроенной в дескриптор процесса (кстати, поскольку номер группы потоков совпадает с идентификатором процесса – лидера, эти числа также хранятся в поле pid дескриптора процесса). Рассмотрим список для группы с идентификатором 4351. Голова этого списка хранится в поле pid iist дескриптора процесса, включенного в хеш – таблицу, а ссылки на предыдущий и следующий элементы списка хранятся также и в поле pid iist каждого элемента списка.

Для работы с хеш – таблицами идентификаторов процессов применяются следующие функции и макросы:

do_each_task_pid(nr, type, task) И while_each_task_pid(nr, type, task) —отмечают начало и конец цикла do – while, который перебирает список, ассоциированный с идентификатором процесса nr, имеющим тип type. На каждом шаге цикла переменная task указывает на дескриптор процесса для текущего элемента;

Find task by pid type (type, nr) —эта функция ищет процесс, имеющий идентификатор nr, в таблице типа type. Функция возвращает указатель на дескриптор процесса, если поиск завершился успешно, или null в противном случае;

ind_task_by_pid(nr) —те же действия, что find_task_by_pid_ type (PIDTYPE_PID, nr);

attach_pid(task, type, nr) —заносит дескриптор процесса, на который указывает аргумент task, в хеш – таблицу идентификаторов процессов, имеющую тип type, с учетом идентификатора процесса nr. Если дескриптор процесса, имеющего идентификатор nr, уже находится в таблице, функция просто заносит процесс task в принадлежащий ему список;

detach_pid(task, type) —удаляет дескриптор процесса, на который указывает аргумент task, из отдельного списка типа type, содержащего этот дескриптор. Если список не становится пустым, функция завершает работу. В противном случае она удаляет дескриптор процесса из хеш – таблицы типа type. И, наконец, если идентификатор процесса отсутствует во всех остальных хеш – таблицах, функция сбрасывает соответствующий бит в битовой карте идентификаторов процессов, чтобы этот идентификатор можно было использовать повторно;

next thread(task) —возвращает адрес дескриптора облегченного процесса, следующего за дескриптором процесса task в хеш – таблице типа pidtype tgid. Поскольку список в хеш – таблице является циклическим, то, будучи вызванным для обычного процесса, этот макрос возвращает адрес дескриптора самого процесса.

Add A Comment