СРВ    

  Практика ~ 
  Тема 01 ~ 
  Тема 02 ~ 
  Тема 03 ~ 
  Тема 04 ~ 
  Тема 05 ~ 
  Тема 06 ~ 
  Тема 07 ~ 
  Тема 08 ~ 
  Тема 09 ~ 
  Тема 10 ~ 
  Тема 11 ~ 
/Студентам/СРВ/Тема 03

Тема 3
Алгоритмы планирования со статическим расписанием

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

Будем рассматривать систему независимых периодических задач {Tj}. Кроме того, будем предполагать, что, вообще говоря, могут иметься еще апериодические и спорадические задачи как некоторые особые случаи.

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

Пример статического расписания. Пусть имеется набор из 4-х задач:

T1[4,1]
T2[5,1.8]
T3[20,1]
T4[20,2]

Гиперпериод данной системы задач равен 20. На протяжении этого периода первая задача должна получить управление 5 раз, вторая - 4, а третья и четвертая - по одному разу. При этом, естественно, должны быть соблюдены все крайние сроки. Расписание для такой системы задач может выглядеть, например, следующим образом:

Время Задача --------------------- 0 T1 1 T3 2 T2 3.8 I
4 T1 5 I 6 T4 8 T2 9.8 T1 10.8 I
12 T2 13.8 T1 14.8 I 16 T1 17 I 18 T2 19.8 I

Здесь I обозначает "задачу" простоя (idle task).

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

Поскольку таймеры, как правило, программируются на генерацию прерывания НЕ через какой-то промежуток времени ОТ НАЧАЛА ОТСЧЕТА ВРЕМЕНИ, а на прерывание через какой-то промежуток времени ОТ ТЕКУЩЕГО МОМЕНТА ВРЕМЕНИ, то есть от момента, когда производится программирование, то с практической точки зрения приведенную таблицу удобнее представить в ином виде, а именно, вместо промежутков времени от начала цикла помещать в нее промежутки времени "относительные", от одного прерывания до другого (в рамках цикла). Соответствующим образом модифицированная таблица для приведенного примера набора задач будет выглядеть следующим образом:

Номер Время Задача --------------------- 0 0.2 T1 1 1 T3 2 1 T2 3 1.8 I 4 0.2 T1 5 1 I 6 1 T4 7 2 T2 8 1.8 T1 9 1 I 10 1.2 T2 11 1.8 T1 12 1 I 13 1.2 T1 14 1 I 15 1 T2 16 1.8 I

Далее приведен пример алгоритм простейшего планировщика, запускающего задачи по статическому расписанию. Алгоритм "учитывает" наличие апериодических задач.


	struct schedule_item  {
		int dt;
		void (*task)(void);
	};
	
	void T1(void)
	{
		// код задачи 1 ...
	}

	void T2(void)
	{
		// код задачи 2 ...
	}
	
	// другие задачи ...
	
	#define NSHED 17
	#define IDLE NULL
	
	struct schedule_item schedule[NSHED] = { 
		{0.2, T1},
		{1, T3},
		..........
		{1.8, IDLE}
	}
	
	int intr_count = 0;
	int cycle_count = 0;
	int sched_entry = 0;
	void (*current_task)(void);
	
	void TimerHandler(void)
	{
		if (SomeAperiodicTaskIsBeingExecuted)
			preempt(ThatAperiodicTask);
		
		current_task = schedule[sched_entry].task;
		intr_count++;
		sched_entry++;
		
		if ( sched_entry == NSCHED) {
			cycle_count++;
			sched_entry = 0;
		};
		
		SetNextDecisionPoint(schedule[sched_entry].dt);
		
		if ( current_task == IDLE )
			execute(SomeAperiodicTask);
		else
			current_task();
	}
	
	void main(void)
	{
		DisableTimer();
		SetTimerHandler(TimerHandler);
		SetNextDecisionPoint(schedule[sched_entry].dt);
		EnableTimer();
	again:	
		HaltCPU();
		goto again;
	}
	

Вот некий реальный пример, написанный для OS DOS с использованием Turbo C. Он, правда, не совсем точно соответствует приведенной выше "модели" кода, но суть примерно такая же - по кажому прерыванию от таймера делаем некие нужные в данный момент действия. Кроме того, в основной программе, в отличие от приведенного "шаблона", происходит опрос клавиатуры плюс еще кое-чего.

... комментарии к "коду" ...

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

Более реалистичной представляется такая ситуация. Допустим, нам известно, что МАКСИМАЛЬНОЕ время работы планировщика (плюс прочие накладные расходы) составляет 0.1 единицу времени. Подчеркнем, что речь идет именно о максимальном времени, потому что совершенно ни из чего не следует, что каждый раз планировщик будет затрачивать строго одинаковое время. Так, даже простейший планировщик, "исходный код" которого приведен выше, содержит ВЕТВЛЕНИЯ, а это значит, что в одних случаях он будет отрабатывать быстрее, а в других - медленнее. Итак, пусть это максимальное время составляет 0.1 единицы. Тогда, при ТОМ ЖЕ расписании (!), набор задач, который бы такой планировщик смог корректно распланировать, выглядел бы, например, таким образом:

T1[ 4, 0.85 ]
T2[ 5, 1.7 ]
T3[ 20, 0.9 ]
T4[ 20, 1.9 ]

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

К преимуществам данного класса алгоритмов относят следующие обстоятельства:

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

К недостаткам - следующие:

Дата последней модификации: 2012-11-03


/Студентам/СРВ/Тема 03

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

Valid HTML 4.0 Strict Valid CSS!