Хочу рассказать в общих чертах об управлении процессами в Linux. Итак...

Может показаться, что в вашей системе все процессы выполняются одновременно, но это иллюзия, которую создает планировщик задач (sheduler). Планировщик задач отвечает за распределение процессорного времени между всеми процессами в системе.
Планировщик не представлен в виде какой-то одной функции, которая выполняла бы всю работу, но есть главная функция — schedule(), она определена в файле kernel/sched.c:

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

asmlinkage void __sched schedule(void) {         struct task_struct *prev, *next;         unsigned long *switch_count;         struct rq *rq;         int cpu; need_resched:         ...         cpu = smp_processor_id();         rq = cpu_rq(cpu);         ...         prev = rq->curr;         ...         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {                 if (unlikely(signal_pending_state(prev->state, prev)))                         prev->state = TASK_RUNNING;                 else                         deactivate_task(rq, prev, 1);                 switch_count = &prev->nvcsw;         }         ...         if (unlikely(!rq->nr_running))                 idle_balance(cpu, rq);                 put_prev_task(rq, prev);         next = pick_next_task(rq);                 if (likely(prev != next)) {                 ...                 rq->curr = next;                 ...                 context_switch(rq, prev, next); /* unlocks the rq */                 ...         } else                 spin_unlock_irq(&rq->lock);         ...         if (need_resched())                 goto need_resched; } EXPORT_SYMBOL(schedule);

В schedule() выбирается очередь выполнения (в старых версиях планировщика, таких как O(1)-scheduler, очередь содержала списки задач, которые обслуживались по принципу FIFO - First Input First Output), которая связанна с конкретным процессором в системе (если процессор один, то и очередь всего одна) и из очереди выбирается следующий наиболее подходящий процесс на выполнение.
Как уже было сказано, с каждым процессором связана своя очередь выполнения (run queue, см. рис. 1).



Рис.1. Каждому процессору соответствует своя очередь выполнения

Очередь описывается структурой struct rq, которая определена в файле kernel/sched.c:

1 2 3 4 5 6 7 8 9 10 11 12

struct rq {         ...         unsigned long nr_running;         ...         struct cfs_rq cfs;         struct rt_rq rt;         ...         struct task_struct *curr, *idle;         ...         int cpu;         ... };

• nr_running содержит количество задач готовых к выполнению;


• curr указывает на текущую выполняемую задачу;


• idle указывает на idle процесс, работает, когда нет ни одной другой готовой к выполнению задачи;


• cpu это номер процессора, с которым связана данная очередь;


• cfs очередь выполнения CFS (Completely Fair Scheduler);


• rt очередь выполнения RT (Real-Time).

В ядре Linux, начиная с версии 2.6.23, были введены классы планирования (schedule class). На сегодняшний день (для версии ядра 2.6.32) можно выделить два основных класса (есть третий для idle):

• CFS schedule class — отвечает за работу с обычными процессами (kernel/sched_fair.c);


• RT schedule class — отвечает за работу с процессами реального времени (kernel/sched_rt.c).

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

include/linux/sched.h:

1 2 3 4 5

struct task_struct {         ...                 const struct sched_class *sched_class;         ...         }

Структура класса определена в файле include/linux/sched.h и содержит в себе указатели на функции, такие как, например, включение и исключение из очереди выполнения:

1 2 3 4 5 6 7 8

struct sched_class {         const struct sched_class *next;         void (*enqueue_task) (struct rq *rq, struct task_struct *p,                                         int wakeup);         void (*dequeue_task) (struct rq *rq, struct task_struct *p,                                         int sleep);         ... }

При создании нового процесса происходит вызов функции sched_fork() из copy_process() (описанной в прошлых статьях), в которой определяется к какому классу принадлежит процесс:

kernel/sched.c:

1 2 3 4 5 6 7 8

void sched_fork(struct task_struct *p, int clone_flags) {         ...         p->prio = current->normal_prio;         if (!rt_prio(p->prio))                 p->sched_class = &fair_sched_class;         ... }

include/linux/sched.h:

1 2 3 4 5 6 7 8

#define MAX_USER_RT_PRIO        100 #define MAX_RT_PRIO             MAX_USER_RT_PRIO static inline int rt_prio(int prio) {         if (unlikely(prio < MAX_RT_PRIO))                 return 1;         return 0; }

Если приоритет процесса больше 99, то устанавливается принадлежность процесса к классу CFS, который будет отвечать за управление этим процессом.
В зависимости от класса, к которому принадлежит процесс, он будет находиться в той или иной очереди выполнения — cfs_rq или rt_rq (см. рис. 2).


Рис.2. Схематичное представление очереди

Возвращаясь к функции schedule() было сказано, что выбирается наиболее подходящий процесс на выполнение:

kernel/sched.c (в функции schedule()):

1 2 3

... next = pick_next_task(rq); ...

kernel/sched.c:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

static inline struct task_struct *pick_next_task(struct rq *rq) {         const struct sched_class *class;         struct task_struct *p;         if (likely(rq->nr_running == rq->cfs.nr_running)) {                 p = fair_sched_class.pick_next_task(rq);                 if (likely(p))                         return p;         }         class = sched_class_highest;         for ( ; ; ) {                 p = class->pick_next_task(rq);                 if (p)                         return p;                 class = class->next;         } }

Если количество процессов готовых к выполнению в общем равно количеству процессов принадлежащих к cfs_rq (rq->nr_running == rq->cfs.nr_running), то следовательно они все принадлежат к очереди cfs_rq и следующий процесс на выполнение будет выбираться по алгоритму CFS. В противном случае проходятся все классы, начиная с sched_class_highest (на самом деле это rt_sched_class), пока не будет выбран новый процесс на выполнение (см. рис. 3).


Рис. 3. Обход классов в поиске процесса


И последнее о чем хотелось бы еще сказать. Для многопроцессорных систем (SMP — Symmetric Multiprocessing) в планировщике реализована специальная функция load_balance() (kernel/sched.c), которая предназначена для того, чтобы процессор не только не «простаивал» (например, если его очередь пуста), но и как следствие, чтобы снизить нагрузку на другой процессор. Реализуется это за счет перемещения задач между очередями выполнения:


Рис. 4. Перемещение задачи из одной очереди в другую

P.S. Описано конечно же не все, а лишь малая часть, но как было сказано в самом начале преследовалась цель описать тему лишь в общих чертах.
P.P.S. И как всегда pdf'ка