Анализ планирования ядра Linux (планирование процессов)

задняя часть алгоритм Linux Безопасность

Автор: No Dishwashing Studio - Marklux

Источник: marklux.cn/blog/64

Все права принадлежат автору, при перепечатке указывать источник

Эта статья представляет собой примечания к чтению главы 4 "Проектирование и реализация ядра Linux". Код взят из исходного кода Linux последней версии 4.6 (github). Пожалуйста, укажите источник.

Многозадачность

Параллелизм и параллелизм

Как многозадачная операционная система, Linux должна поддерживать параллельное выполнение программ.

Классификация

  1. Невытесняющая многозадачность

    Он будет продолжать выполняться, пока задача не завершится сама.

  2. Упреждающая многозадачность (Linux)

    В этом случае планировщик должен решить, когда остановить процесс, и это принудительное действие приостановки называется «вытеснением».. Основой для принятия вытесняющей многозадачности является использованиеМеханизм ротации интервалов времени**, позволяющий назначить каждому процессу единицу времени, которая может выполняться.

Планирование процессов Linux

История развития

Начиная с версии 2.5, в Linux появился метод, называемыйO(1)Планировщик, концепция справедливого планирования, была введена в планировщик в версии 2.6, заменив предыдущий планировщик, называемыйCFSАлгоритм (Полностью справедливый алгоритм планирования).

Стратегия

Потребление ввода-вывода и потребление процессора

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

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

Приоритет процесса

Linux использует два разных диапазона приоритетов.

  1. Используйте значения nice: большие значения nice означают более низкий приоритет. (между -19 ~ 20)

  2. Приоритет в реальном времени: настраиваемый, более высокий означает более высокий приоритет процесса.

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

  3. Временной интервал: Linux не выделяет временные интервалы с фиксированным значением времени (например, 10 мс), а делит коэффициент использования процессора как «квант времени» на процесс. Таким образом, фактическое время ЦП, полученное процессом, тесно связано с нагрузкой на систему.

Linux中的抢占时机取决于新的可运行进程消耗了多少处理器使用比，
如果消耗的使用比当前进程小，则立刻投入运行，否则将推迟其运行。

Пример

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

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

Как правило, ОС должна назначать текстовому редактору более высокий приоритет и больший временной интервал, но в Linux оба процесса являются обычными процессами, они имеют одинаковое значение nice, поэтому они получат одинаковый коэффициент использования процессора (50%).

Но что происходит в реальной эксплуатации? CFS сможет заметить, что текстовый редактор использует намного меньше процессорного времени, чем ему отведено (поскольку большую часть времени ожидает ввод-вывод), в этом случае добиться «справедливой» доли процессора среди всех процессов , что заставит текстовый редактор вытеснять видеодекодер, как только ему нужно будет запуститься (каждый раз).

Алгоритмы планирования Linux

Класс планировщика

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

Алгоритм CFS, упомянутый выше, представляет собой класс планировщика для обычных процессов.Базовый планировщик будет проходить классы планирования в порядке приоритета, и класс планировщика с наивысшим приоритетом исполняемого процесса побеждает и выбирает следующий процесс A для выполнения.

Планирование процессов в Unix

Существующие проблемы:

  1. Значение nice должно быть сопоставлено с абсолютным временем процессора, а это означает, что для двух процессов с одинаковым приоритетом, разделяющих 100 мс, количество происходящих переключений контекста неодинаково и может сильно различаться. Процессам с более низким приоритетом назначаются меньшие единицы кванта времени, но на самом деле им часто приходится выполнять много фоновых вычислений, что нецелесообразно.

  2. Проблемы, вызванные относительными значениями nice: для двух процессов с разными значениями nice, но одинаковой разницей размер выделенного временного интервала зависит от размера их значений nice: например, время, выделенное двум процессам с значениями nice из 18 и 19 Срезы равны 10 мс и 5 мс, но двум процессам с хорошими значениями 0 и 1 назначаются 100 мс и 95 мс Такое сопоставление нецелесообразно.

  3. Если мы хотим сопоставить приятные значения с временными срезами, у нас должна быть возможность иметь «абсолютный временной срез», который можно измерить (это включает в себя концепцию таймеров и метрономов). На самом деле квант времени изменяется с тактом таймера, и могут быть различия, когда одно и то же значение nice в итоге сопоставляется с процессорным временем.

  4. Чтобы иметь возможность быстрее разбудить процесс, необходимо повысить приоритет нового процесса для пробуждения, но это может нарушить «справедливость».

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

Справедливое планирование (CFS)

Отправная точка: эффект планирования процессов должен быть таким, как если бы система имела идеальный многозадачный процессор — мы можем запланировать любой процесс с бесконечно малым периодом времени, поэтому в любом измеримом диапазоне мы можем дать n процессам больше времени выполнения.

В качестве примера, чтобы отличить планирование Unix от CFS: есть два процесса, работающих с одинаковым приоритетом, в Unix это может быть 5 мс каждый, полностью занимая процессор во время выполнения, но в «идеальном случае» он должен быть, способным запустить два процесса одновременно в течение 10 мс, каждый из которых использует половину мощности процессора.

Практика CFS состоит в том, чтобы вычислить время, в течение которого процесс должен выполняться, исходя из общего числа всех запущенных процессов.Значение nice больше не используется в качестве стандарта для распределения временных интервалов, а используется для обработки веса использования процессора, полученного расчет.

Далее рассмотрим период планирования, теоретически, чем меньше период планирования, тем ближе он к «идеальному планированию», но на практике это неизбежно приведет к серьезному потреблению переключений контекста. В CFS устанавливается приблизительная цель на минимально достижимый период планирования, называемая «целевой задержкой», и в то же время, во избежание недопустимого потребления переключения контекста, устанавливается размер временного среза, который может получить каждый процесс. итог - минимальная гранулярность (обычно 1мс).

Когда среднее время выполнения каждого процесса больше, чем минимальная степень детализации, CFS, несомненно, является справедливой, и значение nice используется для расчета доли процессорного времени, которое процесс должен получить в текущем минимальном цикле планирования, так что даже если nice value отличается, пока разница одинакова, всегда получается один и тот же квант времени. Мы предполагаем, что минимальный период планирования составляет 20 мс, а разница между значениями nice двух процессов равна 5:

  • Хорошие значения двух процессов соответственно равны 0 и 5. Временной интервал, полученный последним, составляет 1/3 от первого, поэтому в итоге он получает 15 мс и 5 мс соответственно.
  • Хорошие значения двух процессов соответственно равны 10 и 15. Временной интервал, полученный последним, составляет 1/3 от первого, а окончательные результаты также составляют 15 мс и 5 мс.

Приведенный выше вывод может быть немного трудным для понимания, поэтому давайте рассмотрим его глубже и посмотрим, как разница в базовом nice влияет на долю области обработки.

Прежде всего, на нижнем уровне, прежде чем фактически вычислить коэффициент процессора процесса, ядро ​​​​сначала преобразует значение nice в весовое значение. Формула для этого преобразования выглядит следующим образом:

weight = 1024/(1.25^nice)

Например, процесс со значением nice по умолчанию получает вес 1024/(1,25^0) = 1024/1 = 1024.

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

Хорошо, теперь предположим, что у нас есть n процессов в нашей очереди исполняемых процессов, их веса иw(1)+w(2)+...+w(n)отмечен какw(queue), то окончательная производительность любого процесса i будетw(i)/w(queue).

Тогда нетрудно сделать вывод, что доля процессоров, выделяемых любыми двумя процессами i и j, должна бытьw(i)/w(j), окончательный результат можно получить после простого математического вывода:1.25^(nice(i)-nice(j)), что означает, что пока разница между двумя значениями nice одинакова, доля процессоров, полученных двумя процессами, всегда будет одинаковой, что решает третью проблему выше.

На приведенную выше формулу преобразования ссылаются: https://oakbytes.wordpress.com/2012/06/06/linux-scheduler-cfs-and-nice.

Подводя итог, процессорное время, которое получает любой процесс, равноОпределяется относительной разницей между собой и значениями nice всех других исполняемых процессов., поэтому мы можем сказать, что CFS, по крайней мере, гарантирует справедливое соотношение загрузки процессора для каждого процесса, что является почти идеальным методом планирования многозадачности.

Реализация планирования Linux

Давайте взглянем на то, как реализуется CFS, в целом мы разделим его на 4 основные части для анализа.

учет рабочего времени

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

1. Структура объекта планировщика

Структура данных, используемая для записи времени выполнения процесса в CFS, представляет собой «сущность планирования», которая определена в<linux/sched.h>середина:

struct sched_entity {
	/* 用于进行调度均衡的相关变量，主要跟红黑树有关 */
	struct load_weight		load; // 权重，跟优先级有关
	unsigned long			runnable_weight; // 在所有可运行进程中所占的权重
	struct rb_node			run_node; // 红黑树的节点
	struct list_head		group_node; // 所在进程组
	unsigned int			on_rq; // 标记是否处于红黑树运行队列中

	u64				exec_start; // 进程开始执行的时间
	u64				sum_exec_runtime; // 进程总运行时间
	u64				vruntime; // 虚拟运行时间，下面会给出详细解释
	u64				prev_sum_exec_runtime; // 进程在切换CPU时的sum_exec_runtime，简单说就是上个调度周期中运行的总时间

	u64				nr_migrations;

	struct sched_statistics		statistics;
	
	// 以下省略了一些在特定宏条件下才会启用的变量
}

Примечание. Весь исходный код Linux, использованный в этой статье, взят из официальной библиотеки git для Linux на github (2018.01).

2. Виртуальный режим реального времени (vruntime)

Теперь давайте поговорим о значении переменной vruntime в структуре выше. Мы называем это «виртуальное время выполнения», и время выполнения рассчитывается путем нормализации (или просто взвешивания) общего количества всех запущенных процессов. Он находится в ns и больше не связан с тактом таймера.

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

В результате чем выше вес, тем медленнее рост: результирующее время планирования меньше — CFS использует его для отслеживания того, как долго выполняется программа и как долго она должна работать.

Давайте взглянем на исходный код реализации этой функции учета (kernel/sched/fair.c)

/*
 * Update the current task's runtime statistics.
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;

	if (unlikely(!curr))
		return;
	
	// 获得从最后一次修改负载后当前任务所占用的运行总时间
	delta_exec = now - curr->exec_start;
	if (unlikely((s64)delta_exec <= 0))
		return;
		
	// 更新执行开始时间
	curr->exec_start = now;

	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));

	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);

	// 计算虚拟时间，具体的转换算法写在clac_delta_fair函数中
	curr->vruntime += calc_delta_fair(delta_exec, curr);
	update_min_vruntime(cfs_rq);

	if (entity_is_task(curr)) {
		struct task_struct *curtask = task_of(curr);

		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
		cgroup_account_cputime(curtask, delta_exec);
		account_group_exec_runtime(curtask, delta_exec);
	}

	account_cfs_rq_runtime(cfs_rq, delta_exec);
}

Эта функция вычисляет время выполнения текущего процесса и сохраняет его вdelta_execпеременная, затем используйтеclac_delta_fairФункция вычисляет соответствующее виртуальное время работы и обновляет его.vruntimeценность.

Эта функция периодически вызывается системным таймером (независимо от состояния процесса), поэтому vruntime может точно измерить время выполнения данного процесса и использовать его как основу для вывода о том, какой процесс будет выполняться следующим.

Выбор процесса

Вот основная часть планирования.Обобщим суть алгоритма CFS в одном предложении:Выберите процесс с наименьшим временем выполнениякак следующий запланированный процесс.

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

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

1. Найдите следующий узел задачи

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

Исходный код для реализации этого процесса выглядит следующим образом (kernel/sched/fair.c):

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *left = __pick_first_entity(cfs_rq);
	struct sched_entity *se;

	/*
	 * If curr is set we have to see if its left of the leftmost entity
	 * still in the tree, provided there was anything in the tree at all.
	 */
	if (!left || (curr && entity_before(curr, left)))
		left = curr;

	se = left; /* ideally we run the leftmost entity */

	/*
	 * 下面的过程主要针对一些特殊情况，我们在此不做讨论
	 */
	if (cfs_rq->skip == se) {
		struct sched_entity *second;

		if (se == curr) {
			second = __pick_first_entity(cfs_rq);
		} else {
			second = __pick_next_entity(se);
			if (!second || (curr && entity_before(curr, second)))
				second = curr;
		}

		if (second && wakeup_preempt_entity(second, left) < 1)
			se = second;
	}

	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
		se = cfs_rq->last;

	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
		se = cfs_rq->next;

	clear_buddies(cfs_rq, se);

	return se;
}

2. Добавьте новый процесс в очередь

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

Процесс добавления его в очередь — это, по сути, процесс вставки нового узла в красно-черное дерево:

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
	bool curr = cfs_rq->curr == se;

	/*
	 * 如果要加入的进程就是当前正在运行的进程，重新规范化vruntime
	 * 然后更新当前任务的运行时统计数据
	 */
	if (renorm && curr)
		se->vruntime += cfs_rq->min_vruntime;

	update_curr(cfs_rq);

	/*
	 * Otherwise, renormalise after, such that we're placed at the current
	 * moment in time, instead of some random moment in the past. Being
	 * placed in the past could significantly boost this task to the
	 * fairness detriment of existing tasks.
	 */
	if (renorm && !curr)
		se->vruntime += cfs_rq->min_vruntime;

	/*
	 * 更新对应调度器实体的各种记录值
	 */
	 
	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
	update_cfs_group(se);
	enqueue_runnable_load_avg(cfs_rq, se);
	account_entity_enqueue(cfs_rq, se);

	if (flags & ENQUEUE_WAKEUP)
		place_entity(cfs_rq, se, 0);

	check_schedstat_required();
	update_stats_enqueue(cfs_rq, se, flags);
	check_spread(cfs_rq, se);
	if (!curr)
		__enqueue_entity(cfs_rq, se); // 真正的插入过程
	se->on_rq = 1;

	if (cfs_rq->nr_running == 1) {
		list_add_leaf_cfs_rq(cfs_rq);
		check_enqueue_throttle(cfs_rq);
	}
}

Вышеупомянутая функция в основном используется для обновления времени работы и различной статистики, а затем вызывает__enqueue_entity()Чтобы фактически вставить данные в красно-черное дерево:

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	bool leftmost = true;

	/*
	 * 在红黑树中搜索合适的位置
	 */
	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * 具有相同键值的节点会被放在一起
		 */
		if (entity_before(se, entry)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(&se->run_node, parent, link);
	rb_insert_color_cached(&se->run_node,
			       &cfs_rq->tasks_timeline, leftmost);
}

Цикл while() — это процесс обхода дерева для поиска совпадающих значений ключей, то есть процесс поиска сбалансированного дерева. После нахождения выполняем на родительском узле позиции для вставкиrb_link_node()чтобы вставить в него узлы, а затем обновить связанные с самобалансировкой свойства красно-черного дерева.

3. Удалить процесс из очереди

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

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	/*
	 * 更新“当前进程”的运行统计数据
	 */
	update_curr(cfs_rq);

	/*
	 * When dequeuing a sched_entity, we must:
	 *   - Update loads to have both entity and cfs_rq synced with now.
	 *   - Substract its load from the cfs_rq->runnable_avg.
	 *   - Substract its previous weight from cfs_rq->load.weight.
	 *   - For group entity, update its weight to reflect the new share
	 *     of its group cfs_rq.
	 */
	update_load_avg(cfs_rq, se, UPDATE_TG);
	dequeue_runnable_load_avg(cfs_rq, se);

	update_stats_dequeue(cfs_rq, se, flags);

	clear_buddies(cfs_rq, se);

	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);
	se->on_rq = 0;
	account_entity_dequeue(cfs_rq, se);

	/*
	 * 重新规范化vruntime
	 */
	if (!(flags & DEQUEUE_SLEEP))
		se->vruntime -= cfs_rq->min_vruntime;

	/* return excess runtime on last dequeue */
	return_cfs_rq_runtime(cfs_rq);

	update_cfs_group(se);

	/*
	 * Now advance min_vruntime if @se was the entity holding it back,
	 * except when: DEQUEUE_SAVE && !DEQUEUE_MOVE, in this case we'll be
	 * put back on, and if we advance min_vruntime, we'll be placed back
	 * further than we started -- ie. we'll be penalized.
	 */
	if ((flags & (DEQUEUE_SAVE | DEQUEUE_MOVE)) == DEQUEUE_SAVE)
		update_min_vruntime(cfs_rq);
}

Как и в случае со вставкой, фактическая работа над операциями с узлами дерева выполняется__dequeue_entity()выполнить:

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

Видно, что удалить узел гораздо проще, чем вставить, благодаря реализации самого красно-черного дереваrb_erase()функция.

запись планировщика

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

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

В этой функции важно только то, что она выполняетpick_next_task()Эта функция (определенная вkenerl/sched/core.c), он по очереди проверяет каждый класс планирования в порядке приоритета и выбирает процесс с наивысшим приоритетом из класса планирования с наивысшим приоритетом.

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * 优化：如果当前所有要调度的进程都是普通进程，那么就直接采用普通进程的调度类（CFS）
	 */
	if (likely((prev->sched_class == &idle_sched_class ||
		    prev->sched_class == &fair_sched_class) &&
		   rq->nr_running == rq->cfs.h_nr_running)) {

		p = fair_sched_class.pick_next_task(rq, prev, rf);
		if (unlikely(p == RETRY_TASK))
			goto again;

		/* Assumes fair_sched_class->next == idle_sched_class */
		if (unlikely(!p))
			p = idle_sched_class.pick_next_task(rq, prev, rf);

		return p;
	}

// 遍历调度类
again:
	for_each_class(class) {
		p = class->pick_next_task(rq, prev, rf);
		if (p) {
			if (unlikely(p == RETRY_TASK))
				goto again;
			return p;
		}
	}

	/* The idle class should always have a runnable task: */
	BUG();
}

Каждый класс планирования реализуетpick_next_task()метод, который возвращает указатель на следующий процесс, который может быть запущен, или NULL, если нет. Запись планировщика выбирает следующий исполняемый процесс из первого класса, который возвращает не NULL.

спать и просыпаться

Процесс сна и пробуждения в Linux выглядит следующим образом:

  • Сон: процесс помечает себя как бездействующий, затем удаляет его из исполняемого красно-черного дерева, помещает в очередь ожидания, а затем вызываетschedule()Выберите и выполните дополнительный процесс.
  • Пробуждение: процесс устанавливается в исполняемое состояние, а затем перемещается из очереди ожидания в исполняемое красно-черное дерево.

Спящий режим имеет два состояния в Linux: одно игнорирует сигнал, а другое просыпается и отвечает при получении сигнала. Однако процессы в этих двух состояниях находятся в одной очереди ожидания.

1. Очередь ожидания

В отличие от сложной структуры исполняемой очереди, реализация очереди ожидания в Linux представляет собой простой связанный список. Все структуры данных, относящиеся к очередям ожидания, определены вinclude/linux/wait.h, конкретный код реализации определен вkernel/sched/wait.cсередина.

Использование ядраwait_queue_head_tСтруктура для представления очереди ожидания, которая на самом деле является головным узлом связанного списка, но добавлена ​​спин-блокировка для обеспечения согласованности (очередь ожидания может быть изменена в любое время при прерывании).

struct wait_queue_head {
	spinlock_t		lock;
	struct list_head	head;
};
typedef struct wait_queue_head wait_queue_head_t;

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

Возможный поток выглядит следующим образом:

  1. вызов макросаDEFINE_WAIT()Создать элемент очереди ожидания (узел связанного списка)
  2. перечислитьadd_wait_queue()Добавьте себя в очередь. Очередь разбудит процесс, когда будут выполнены условия, которых она ожидает.Конечно, конкретная операция пробуждения должна быть определена самим процессом (вы можете понимать это как обратный вызов)
  3. перечислитьprepare_to_wait()Метод изменяет свое состояние на одно из двух состояний сна, упомянутых выше.

Вот исходный код упомянутого выше метода:

void add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
	unsigned long flags;

	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&wq_head->lock, flags);
	__add_wait_queue(wq_head, wq_entry);
	spin_unlock_irqrestore(&wq_head->lock, flags);
}

static inline void __add_wait_queue(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
	list_add(&wq_entry->entry, &wq_head->head);
}

void
prepare_to_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
{
	unsigned long flags;

	wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&wq_head->lock, flags);
	if (list_empty(&wq_entry->entry))
		__add_wait_queue(wq_head, wq_entry);
	// 标记自己的进程状态
	set_current_state(state);
	spin_unlock_irqrestore(&wq_head->lock, flags);
}

2. Просыпайтесь

Операция пробуждения в основном осуществляется черезwake_up()Реализовано, он разбудит все процессы в указанной очереди ожидания. внутреннеtry_to_wake_up()Функция помечает соответствующий процесс какTASK_RUNNINGгосударство, а затем позвонитеenqueue_task()Добавьте процесс в красно-черное дерево.

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

/*
 * The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
 * wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
 * number) then we wake all the non-exclusive tasks and one exclusive task.
 *
 * There are circumstances in which we can try to wake a task which has already
 * started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
 * zero in this (rare) case, and we handle it by continuing to scan the queue.
 */
static int __wake_up_common(struct wait_queue_head *wq_head, unsigned int mode,
			int nr_exclusive, int wake_flags, void *key,
			wait_queue_entry_t *bookmark)
{
	wait_queue_entry_t *curr, *next;
	int cnt = 0;

	if (bookmark && (bookmark->flags & WQ_FLAG_BOOKMARK)) {
		curr = list_next_entry(bookmark, entry);

		list_del(&bookmark->entry);
		bookmark->flags = 0;
	} else
		curr = list_first_entry(&wq_head->head, wait_queue_entry_t, entry);

	if (&curr->entry == &wq_head->head)
		return nr_exclusive;

	list_for_each_entry_safe_from(curr, next, &wq_head->head, entry) {
		unsigned flags = curr->flags;
		int ret;

		if (flags & WQ_FLAG_BOOKMARK)
			continue;

		ret = curr->func(curr, mode, wake_flags, key);
		if (ret < 0)
			break;
		if (ret && (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
			break;

		if (bookmark && (++cnt > WAITQUEUE_WALK_BREAK_CNT) &&
				(&next->entry != &wq_head->head)) {
			bookmark->flags = WQ_FLAG_BOOKMARK;
			list_add_tail(&bookmark->entry, &next->entry);
			break;
		}
	}
	return nr_exclusive;
}

Преимущественное прерывание и переключение контекста

переключатель контекста

Переключение контекста означает переключение с одного исполняемого процесса на другой исполняемый процесс. определяетсяkernel/sched/core.cсерединаcontext_switch()выполнить:

static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next, struct rq_flags *rf)
{
	struct mm_struct *mm, *oldmm;

	prepare_task_switch(rq, prev, next);

	mm = next->mm;
	oldmm = prev->active_mm;
	/*
	 * For paravirt, this is coupled with an exit in switch_to to
	 * combine the page table reload and the switch backend into
	 * one hypercall.
	 */
	arch_start_context_switch(prev);
	
	// 把虚拟内存从上一个内存映射切换到新进程中
	if (!mm) {
		next->active_mm = oldmm;
		mmgrab(oldmm);
		enter_lazy_tlb(oldmm, next);
	} else
		switch_mm_irqs_off(oldmm, mm, next);

	if (!prev->mm) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}

	rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

	/*
	 * Since the runqueue lock will be released by the next
	 * task (which is an invalid locking op but in the case
	 * of the scheduler it's an obvious special-case), so we
	 * do an early lockdep release here:
	 */
	rq_unpin_lock(rq, rf);
	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);

	/* Here we just switch the register state and the stack. */
	// 切换处理器状态到新进程，这包括保存、恢复寄存器和栈的相关信息 
	switch_to(prev, next, prev);
	barrier();

	return finish_task_switch(prev);
}

переключение контекста поschedule()Функция вызывается при переключении процессов. Но ядро ​​должно знать, когда вызыватьschedule(), если только явно вызывается пользовательским кодом, код может выполняться вечно.

Для этого ядро ​​устанавливает для каждого процессаneed_reschedФлаг, указывающий, следует ли повторно выполнять планирование, когда процесс должен быть вытеснен,scheduler_tick()Этот флаг будет установлен, когда процесс с высоким приоритетом переходит в исполняемое состояние,try_to_wake_up()Этот флаг также будет установлен, и ядро ​​будет вызывать, когда этот флаг установлен.schedule()перенести.

Преимущественное право пользователя

Когда ядро ​​собирается вернуться в пространство пользователя, еслиneed_reshcedбит флага установлен, вызоветschedule()вызывается, и в это время происходит вытеснение пользователя. Это означает, что, поскольку его необходимо перепланировать, вы можете продолжить выполнение процесса до входа в состояние ядра, а также можете полностью повторно выбрать другой процесс для запуска, поэтому, если вы установитеneed_resched, ядро ​​выберет для запуска более подходящий процесс.

Проще говоря, вытеснение пользователя произойдет в следующих двух ситуациях:

  • Возврат в пространство пользователя из системного вызова
  • Возврат в пространство пользователя из обработчика прерывания

вытеснение ядра

В отличие от большинства других вариантов Unix, Linux поддерживает полное вытеснение ядра.

Система, не поддерживающая вытеснение ядра, означает, что код ядра может выполняться до его завершения, выполнение задач уровня ядра нельзя перепланировать, задачи работают совместно, и нет возможности вытеснения.

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

Для поддержки вытеснения ядра в Linux внесены следующие изменения:

  • для каждого процессаthread_infoпредставилpreempt_countСчетчик используется для записи количества удерживаемых блокировок.Если он равен 0, это означает, что процесс может быть вытеснен.
  • При возврате в пространство ядра из прерывания будет проверятьсяneed_reschedиpreempt_countзначение, еслиneed_reschedотмечен, иpreempt_countЕсли он равен 0, значит, есть процесс, который нужно планировать еще, а текущая ситуация безопасна и может быть вытеснена, то в это время будет вызван планировщик.

Помимо возврата после ответа на прерывание, также бывает ситуация, когда происходит вытеснение ядра, то есть процесс в ядре явно вызывает прерывание.schedule()Чтобы выполнить явное вытеснение ядра: Конечно, этот процесс явно вызывает процесс планировщика, что означает, что он знает, что вытеснение безопасно, поэтому нам не нужна дополнительная логика для проверки проблем безопасности.

Ниже приведен список возможных вытеснений ядра:

  • Обработка прерывания выполняется и перед возвратом в пространство ядра
  • Когда код ядра снова становится вытесняемым
  • Задачи в ядре вызываются явноschedule()
  • Задача в ядре заблокирована


Категории