O Torvalds Linus

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

Список процессов

Mar-7-2012 By root

Первым примером двунаправленного списка, который мы рассмотрим, является список процессов, в котором собраны вместе все дескрипторы процессов. Каждая структура task struct включает в себя поле tasks типа list head, чьи поля prev и next указывают, соответственно, на предыдущий и следующий элемент task struct.

Голова списка процессов представляет собой дескриптор init task типа task struct. Это дескриптор так называемого процесса 0, или процесса swapper. Поле tasks ->prev дескриптора init task указывает на поле tasks процесса, занесенного в список последним.

Макросы set links и remove links служат для занесения дескриптора в список процессов и, соответственно, удаления его из списка. Эти макросы также определяют родительские отношения процесса.

Еще одним полезным макросом является for each process. Он перебирает все элементы списка процессов и определяется следующим образом:

define for_each_process(р) \

for (p=&init_task; (p=list_entry((р)->tasks.next, \

struct task_struct, tasks) \

) != &init_task; )

Этот макрос представляет собой заголовок оператора цикла, после которого программист ставит тело цикла. Обратите внимание, что дескриптор init task играет всего лишь роль головы цикла. Макрос начинает работу с того, что переходит от init task в следующей задаче и продолжает в том же духе, пока снова не дойдет до дескриптора init task (благодаря циклической структуре списка).

Списки процессов в состоянии TASK__RUNNING

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

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

В Linux 2.6 очередь на выполнение реализована иначе. Цель этой реализации —сделать так, чтобы планировщик выбирал процесс за постоянное время, независимо от количества выполняемых процессов. Каждый дескриптор task struct имеет поле run iist типа list head. Если приоритет процесса равен к (числу от 0 до 139), поле run iist связывает дескриптор процесса со списком выполняемых процессов, имеющих приоритет к. Кроме того, в многопроцессорной системе у каждого процессора есть собственная очередь на выполнение, т. е. собственное множество списков процессов. Это классический пример усложнения структур ради повышения производительности. Чтобы оптимизировать работу планировщика, один список разбивается на 140 списков!

Как мы увидим далее, ядро должно поддерживать большое количество данных в каждой очереди на выполнение. Основными структурами в такой очереди являются принадлежащие ей списки дескрипторов процессов. Все эти СПИСКИ реализуются ОДНОЙ структурой prio_array_t.

Функция enqueue_task(p, array) заносит дескриптор процесса В список очереди на выполнение.

Поле prio дескриптора процесса хранит динамический приоритет процесса, а поле array является указателем на структуру prio array t текущей очереди на выполнение. Аналогичным образом, функция dequeue__task(p, array) удаляет дескриптор процесса из списка.

Add A Comment