Приоритетное планирование

По сравнению с SCHED_FIFO и SCHED_RR, политика SCHED_SPORADIC ( спорадическое планирование ) представляется гораздо более сложной. Она базируется на учете двух основных параметров: доступного бюджета вычислительных ресурсов и периода пополнения бюджета . Период пополнения бюджета характеризуется значением элемента sched_ss_repl_period описанной ранее структуры типа sched_param. Доступный бюджет вычислительных ресурсов инициализируется значением элемента sched_ss_init_budget той же структуры.

Политика спорадического планирования предусматривает ряд дополнительных условий, при выполнении которых приоритет потока управления "переключается" между значениями элементов sched_priority и sched_ss_low_priority структуры типа sched_param.

Приоритет потока определяется следующим образом. Если доступный бюджет вычислительных ресурсов положителен и число ждущих операций пополнения бюджета меньше значения элемента sched_ss_max_repl структуры типа sched_param, потоку управления присваивается приоритет sched_priority, в противном случае - sched_ss_low_priority. Если значение sched_priority не больше, чем sched_ss_low_priority, приоритет считается неопределенным. Изменение доступного бюджета вычислительных ресурсов и, следовательно, присваиваемого приоритета, производится по следующим правилам.

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

Приведенное описание выглядит довольно замысловатым, хотя основная идея относительно проста. Определенные вычислительные ресурсы резервируются для обработки непериодических событий с высоким приоритетом ( sched_priority ). Если отведенного времени не хватило, остальные события обрабатываются в фоновом режиме с (низким) приоритетом sched_ss_low_priority. Истраченное "приоритетное" время возвращается в бюджет в результате выполнения планируемых операций пополнения, по истечении периода пополнения. При этом поток может вернуться с низкого приоритета на высокий.

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

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

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

Используемые в приложении политики и параметры планирования выбираются с целью выполнения предъявляемых требований реального времени, которые, в свою очередь, являются отражением условий функционирования приложения. Если это условия постоянны, нет нужды динамически менять политику и/или приоритеты. Чаше всего так и бывает. Но в некоторых случаях (например, при спуске космического аппарата) условия могут измениться кардинально, что требует если и не смены приложения, то его существенной перестройки. В этой связи важно отметить, что стандарт POSIX-2001 предоставляет достаточно средств для динамического изменения значений атрибутов планирования.

Вообще говоря, установки и изменения атрибутов планирования могут производиться мелкими порциями, путем обращения к множеству функций вроде pthread_setschedprio(), или массово, в результате вызова одной функции с несколькими аргументами или одним структурным аргументом (такой, например, как pthread_setschedparam() ). При начальной установке второй подход предпочтительнее. Из соображений минимальности интерфейса его следует распространить и на другие ситуации, что в общем и целом и сделано в стандарте POSIX-2001. Дополнительным доводом в пользу данного подхода является простота поддержания целостности конфигурации планирования, если значения отдельных характеристик могут оказаться некорректными для определенных реализаций: вызов "массовой" функции изменит все или ничего.

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

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

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

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

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

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

Несмотря на то, что в стандарте POSIX-2001 приняты определенные меры для ограничения инверсии приоритетов – при захвате мьютекса приоритет потока управления повышается в соответствии с протоколом, являющимся одним из атрибутов мьютекса (см. выше раздел, посвященный мьютексам), это конечно, нельзя считать полным решением проблемы инверсии (например, для семафоров ничего подобного не предусмотрено). Тем не менее, POSIX-2001 служит хорошей основой для разработки мобильных приложений реального времени, в том числе применительно к весьма сложным и тонким аспектам.

Функции управления планированием

Мы приступаем к рассмотрению функций для опроса и/или установки политики и/или параметров планирования применительно к процессам. Функции аналогичной направленности для потоков управления были рассмотрены нами ранее.

Стандарт POSIX-2001 предусматривает следующие функции управления планированием: sched_getscheduler() ( опрос политики планирования процесса ), sched_getparam() ( опрос параметров планирования процесса ), sched_setscheduler() ( установка политики и параметров планирования процесса ) и sched_setparam() ( установка параметров планирования процесса ) (см. листинг 6.1).

#include <sched.h>

int sched_getscheduler (pid_t pid);

int sched_getparam (pid_t pid, 
	struct sched_param *param);

int sched_setscheduler (pid_t pid, 
    int policy, 	
    const struct sched_param *param);

int sched_setparam (pid_t pid, 
    const struct sched_param *param);

Функция sched_getscheduler() возвращает в качестве (нормального) результата политику планирования процесса с заданным идентификатором (в случае неудачи результат равен -1 ). Если значение аргумента pid равно нулю, имеется в виду вызывающий процесс. Вообще говоря, опрос атрибутов других процессов подвержен контролю прав доступа, зависящему от реализации.

Функция sched_getparam() записывает параметры планирования заданного процесса по указателю param, в структуру типа sched_param ; ее нормальный результат равен нулю. (Напомним, что, согласно стандарту POSIX-2001, у структуры типа sched_param только одно обязательное поле – приоритет sched_priority.)

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

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

Любопытно отметить, что стандарт POSIX-2001 не требует атомарности вызова sched_setscheduler() с точки зрения выполняющихся потоков управления. Хотя в итоге изменится все или ничего, эти изменения могут наблюдаться как поэтапные; соответственно они будут сказываться на поведении потоков.

Функция sched_setparam(), в отличие от sched_setscheduler(), изменяет только параметры планирования, но ее воздействие на заданный процесс стандартизовано детальнее.

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

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

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

Стандарт POSIX-2001 предоставляет средства для опроса характеристик политик планирования – минимального ( sched_get_priority_min() ) и максимального ( sched_get_priority_max() ) среди допустимых приоритетов, а также величины кванта выделяемого процессорного времени для политики циклического планирования ( sched_rr_get_interval() ) (см. листинг 6.2).

#include <sched.h>

int sched_get_priority_min (int policy);

int sched_get_priority_max (int policy);

int sched_rr_get_interval (pid_t pid, 
    struct timespec *q_ptr);

Функция sched_rr_get_interval() записывает по указателю q_ptr в структуру типа timespec величину кванта процессорного времени, выделяемого заданному процессу, и возвращает нуль в качестве нормального результата. Нормальными результатами функций sched_get_priority_min() и sched_get_priority_max(), разумеется, служат, соответственно, минимальный и максимальный приоритеты.

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

#include <sched.h>
int sched_yield (void);

Следующая программа (см. листинг 6.4) иллюстрирует применение описанных функций. Возможные результаты ее выполнения для ОС Linux и операционной системы реального времени oc2000 показаны на листингах 6.5 и 6.6.

/* * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Программа опрашивает характеристики политик планирования, */
/* а также атрибуты планирования текущего процесса 	*/
/* * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h>
#include <sched.h>

int main (void) {
	struct sched_param shdprm; 	/* Значения параметров 	*/
											/* планирования 	*/
	struct timespec qp; 			/* Величина кванта 	*/
											/* процессорного времени 	*/

	printf ("Допустимые диапазоны приоритетов для разных "
				"политик планирования\n");
	printf ("SCHED_FIFO : от %d до %d\n", 
		sched_get_priority_min (SCHED_FIFO), 
		sched_get_priority_max (SCHED_FIFO));
	printf ("SCHED_RR   : от %d до %d\n", 
		sched_get_priority_min (SCHED_RR), 
		sched_get_priority_max (SCHED_RR));
	printf ("SCHED_OTHER: от %d до %d\n", 
		sched_get_priority_min (SCHED_OTHER), 
		sched_get_priority_max (SCHED_OTHER));

	printf ("Текущая политика планирования для текущего "
				"процесса: ");
	switch (sched_getscheduler (0)) {
		case SCHED_FIFO:
			printf ("SCHED_FIFO\n");
			break;
		case SCHED_RR:
			printf ("SCHED_RR\n");
			break;
		case SCHED_OTHER:
			printf ("SCHED_OTHER\n");
			break;
		case -1:
			perror ("SCHED_GETSCHEDULER");
			break;
		default:
			printf ("Неизвестная политика планирования\n");
	}

	if (sched_getparam (0, shdprm) == 0) {
		printf ("Текущий приоритет текущего процесса: %d\n", 
					shdprm.sched_priority);
	} else {
		perror ("SCHED_GETPARAM");
	}

	shdprm.sched_priority = 50;
	if (sched_setscheduler (0, SCHED_RR, shdprm) == -1) {
		perror ("SCHED_SETSCHEDULER");
	}

	if (sched_rr_get_interval (0, qp) == 0) {
		printf ("Квант процессорного времени при "
					"циклическом планировании: %g сек\n", 
					qp.tv_sec + qp.tv_nsec / 1000000000.0);

	} else {
		perror ("SCHED_RR_GET_INTERVAL");
	}

	return 0;
}

Допустимые диапазоны приоритетов для разных политик планирования

	SCHED_FIFO : 		от 1 до 99
	SCHED_RR : 		от 1 до 99
	SCHED_OTHER : 	от 0 до 0

Текущая политика планирования для текущего процесса: SCHED_OTHER 
Текущий приоритет текущего процесса: 0 
Квант процессорного времени при циклическом планировании: 0.15 сек

Допустимые диапазоны приоритетов для разных политик планирования
	SCHED_FIFO : 		от 1 до 255
	SCHED_RR : 		от 1 до 255
	SCHED_OTHER : 	от 0 до 255
Текущая политика планирования для текущего процесса: SCHED_FIFO 
Текущий приоритет текущего процесса: 100 
Квант процессорного времени при циклическом планировании: 0.08 сек

Проиллюстрируем теперь ситуацию с инверсией приоритетов (см. листинг 6.7).

/* * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Программа моделирует ситуацию инверсии приоритетов. 	*/
/* Идея состоит в том, что имеется три потока 	*/
/* управления	 с низким, средним 	*/
/* и высоким приоритетами.		*/
/* Поток с низким приоритетом захватывает семафор, 	*/
/* когда на него никто больше не претендует, 	*/
/* но не может освободить его, 	*/
/* потому что его вытесняет с процессора 	*/ 
/* поток со средним приоритетом. 	*/
/* В это время поток с высоким приоритетом хочет 	*/
/* захватить тот же семафор, 	*/
/* но он занят и неизвестно когда освободится... 	*/
/* * * * * * * * * * * * * * * * * * * * * * * * * * */

#include <stdio.h>
#include <pthread.h>
#include <sched.h>
#include <semaphore.h>
#include <assert.h>

static sem_t sem_mi; 	/* Семафор для потока со средним 	*/
								/* приоритетом 	*/
static sem_t sem_hi; 	/* Семафор для потока с высоким 	*/
								/* приоритетом 	*/

static double s = 0;

/* * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Стартовая функция потока с высоким приоритетом 	*/
/* * * * * * * * * * * * * * * * * * * * * * * * * * */
void *start_hi (void *dummy) {
	printf ("Поток с высоким приоритетом перед захватом "
				"семафора\n");
	assert (sem_wait (sem_hi) == 0);
	printf ("Поток с высоким приоритетом после захвата "
				"семафора\n");
	assert (sem_post (sem_hi) == 0);

	return (NULL);
}

/* * * * * * * * * * * * * * * * * * * * * * * * * */
/* Стартовая функция потока со средним приоритетом */
/* * * * * * * * * * * * * * * * * * * * * * * * * */
void *start_mi (void *dummy) {
	int i;
	double d = 1;

	printf ("Поток со средним приоритетом перед захватом "
				"семафора\n");
	assert (sem_wait (sem_mi) == 0);
	/* Займем процессор вычислениями */
	for (i = 1; i < 100000000; i++) {
		s += d/i;
		d = -d;
	}
	printf ("Поток со средним приоритетом перед "
				"освобождением семафора\n");
	assert (sem_post (sem_mi) == 0);

	return (s);
}

/* * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Стартовая функция потока с низким приоритетом 	*/
/* * * * * * * * * * * * * * * * * * * * * * * * * * */
int main (void) {
	pthread_attr_t attrob; 		/* Атрибутный объект 	*/
											/* создаваемых потоков 	*/
	struct sched_param shdprm; 	/* Значения параметров 	*/
											/* планирования 	*/
	int shdplc; 						/* Политика планирования 	*/
	pthread_t pt_mi; 				/* Идентификатор потока 	*/
											/* со средним приоритетом 	*/
	pthread_t pt_hi; 				/* Идентификатор потока 	*/
											/* с высоким приоритетом 	*/

		/* Создадим два семафора в захваченном состоянии */
		assert (sem_init (sem_mi, 0, 0) == 0);
		assert (sem_init (sem_hi, 0, 0) == 0);
	

	/* Установим политику планирования и сделаем 	*/
	/* текущий поток управления низкоприоритетным 	*/
	shdprm.sched_priority = sched_get_priority_max 
		(SCHED_FIFO) – 31;
	assert (pthread_setschedparam (pthread_self (), 
		SCHED_FIFO, shdprm) == 0);

	/* Инициализируем атрибутный объект 	*/
	/* для создаваемых потоков управления 	*/
	assert (pthread_attr_init (attrob) == 0);

	/* Установим атрибуты планирования */
	assert (pthread_attr_setinheritsched (attrob, 
		PTHREAD_EXPLICIT_SCHED) == 0);
	assert (pthread_attr_setschedpolicy (attrob, 
		SCHED_FIFO) == 0);
	shdprm.sched_priority += 15;
	assert (pthread_attr_setschedparam 
		(attrob, shdprm) == 0);

	/* Создадим поток управления со средним приоритетом */
	assert (pthread_create (pt_mi, attrob, 
		start_mi, NULL) == 0);

	/* Подправим атрибутный объект и создадим */
	/* поток управления с высоким приоритетом */
	shdprm.sched_priority += 15;
	assert (pthread_attr_setschedparam 
		(attrob, shdprm) == 0);
	assert (pthread_create (pt_hi, attrob, 
		start_hi, NULL) == 0);

	/* Опросим параметры планирования потоков управления */
	assert (pthread_getschedparam (pthread_self (), 
		shdplc, shdprm) == 0);
	assert (shdplc == SCHED_FIFO);
	printf ("Низкий приоритет: %d\n", 
				shdprm.sched_priority);
	assert (pthread_getschedparam 
		(pt_mi, shdplc, shdprm) == 0);
	assert (shdplc == SCHED_FIFO);
	printf (quot;Средний приоритет: %d\n", 
		shdprm.sched_priority);
	assert (pthread_getschedparam 
		(pt_hi, shdplc, shdprm) == 0);
	assert (shdplc == SCHED_FIFO);
	printf ("Высокий приоритет: %d\n", shdprm.sched_priority);

	/* Создадим ситуацию инверсии приоритетов */
	printf ("Поток с низким приоритетом\n" 
				"перед освобождением семафора для потока " 
				"со средним приоритетом\n");
	assert (sem_post (sem_mi) == 0);

	printf ("Поток с низким приоритетом\n"
				"перед освобождением семафора для потока "
				"с высоким приоритетом\n");
	assert (sem_post (sem_hi) == 0);

	(void) pthread_join (pt_mi, NULL);
	(void) pthread_join (pt_hi, NULL);

	assert (sem_destroy (sem_mi) == 0);
	assert (sem_destroy (sem_hi) == 0);

	return 0;
}

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

Из технических деталей обратим внимание на использование значения PTHREAD_EXPLICIT_SCHED аргумента inheritsched функции pthread_attr_setinheritsched(). Оно предписывает извлекать характеристики планирования создаваемых потоков управления из атрибутного объекта, а не наследовать их у создающего потока. В данном случае это важно, так как потоки управления необходимо создавать с разными приоритетами.

Возможные результаты выполнения приведенной программы под управлением операционной системы реального времени oc2000 показаны на листинге 6.8.

Поток со средним приоритетом перед захватом семафора
Поток с высоким приоритетом перед захватом семафора
Низкий приоритет: 224
Средний приоритет: 239
Высокий приоритет: 254
Поток с низким приоритетом
перед освобождением семафора для потока со средним приоритетом
Поток со средним приоритетом перед освобождением семафора
Поток с низким приоритетом
перед освобождением семафора для потока с высоким приоритетом
Поток с высоким приоритетом после захвата семафора