Лекция 2 (1121242)
Текст из файла
Задачи построения расписаний и их классификация
[Теория расписаний и вычислительные машины. Под ред. Э.Г. Коффмана. М.: Наука, 1984. 334 с.].
Модель в рамках которой могут быть сформулированы многие задачи построения расписаний задается:
-
моделью ресурсов
-
моделью системы заданий (работ)
-
моделью вычислений
-
мерой оценки расписаний
-
ограничениями на корректность расписания
Ресурсы.
В большинстве моделей ресурсы состоят просто из набора процессоров P.
В наиболее общей модели еще имеется набор дополнительных типов ресурсов R, некоторое подмножество которых используется на протяжении всего времени выполнения задания на некотором процессоре. Общее количество ресурса типа Ri задается целым положительным числом.
В ряде задач рассматривается среда обмена.
Система работ определена через T, 
, [τji], {Rj}, где:
-
T={T1,T2,…,Tn} - набор работ подлежащих планированию;
-
![]()
- заданное на T отношение частичного порядка. Если работы связаны отношением Ti![]()
Tj ,то работа Ti должна быть завершена раньше, чем начнется выполнение работы Tj. -
[τji] – матрица времен выполнения работ на процессорах, элемент которой τji задает время выполнения работы j на процессоре i;
-
R={R1(Tj),…, Rs(Tj)} – набор, i-ая компонента которого задает количество ресурса типа Ri необходимое для выполнения задания Tj.
Расписание может задаваться одним из трех способов:
-
Временная диаграмма – для каждой работы задано время начала выполнения s’(Tj) и процессор на котором она выполняется.
-
Привязка работ к процессорам и порядковый номер выполнения задания на процессоре.
-
Привязка работ к процессорам и приоритет работы. Частным случаем являются списочные расписания: существует единый упорядоченный список работ и не задается привязка работ к процессорам.
Задачи построения расписаний можно разделить на классы в соответствии со следующими характеристиками:
-
Тип процессоров.
-
Тип отношения частичного порядка на множестве работ.
-
Времена выполнения работ.
-
Способ задания директивных интервалов работ.
-
Модель вычислений.
-
Мера оценки эффективности расписания.
Тип процессоров:
-
процессоры одинаковые по производительности и по функциональным возможностям;
-
процессоры разные по производительности и одинаковые по функциональным возможностям;
-
процессоры разные по производительности и по функциональным возможностям.
Тип отношения частичного порядка на множестве работ:
-
пустое,
-
лес,
-
произвольное.
Времена выполнения работ:
-
различными,
-
равными,
-
равными 1 или 2.
Директивные интервалы работ:
-
f- общий директивный интервал для всей системы работ,
-
[sj,fj) – индивидуальные директивные интервалы для каждой работы,
-
[0,fj) – индивидуальные директивные интервалы с общей левой границей,
-
rj – требуемая частота выполнения работы.
Модель вычислений:
-
дисциплина обслуживания работ,
-
учитываемые временные задержки.
Дисциплина обслуживания работ:
-
без прерываний – работа не может быть прервана до полного завершения,
-
с прерываниями – разрешается прерывать работу и запускать ее в последующем. При этом предполагается, что общее время требуемое для выполнения работы остается неизменным.
Временные задержки:
-
учитываются временные задержки начала выполнения работ, определяемые лишь отношением частичного порядка в расписании и ограниченным числом процессоров;
-
учитываются временные задержки начала выполнения работ, связанные с получением доступа к разделяемым ресурсам (каналам обмена, общей памяти….) и работой системного программного обеспечения. В этом случае получение точного значения времени выполнения расписания возможно лишь с использованием имитационных моделей.
Мера оценки эффективности расписания:
-
время выполнения расписания,
-
число используемых процессоров для выполнения множества работ за время не превышающее заданные директивный срок,
-
максимальное число совместимых работ (для задач в которых задаются индивидуальные директивные сроки работ),
-
критерии, основанные на использовании функций штрафа за нарушение директивных сроков работ (используются при построении расписаний для систем мягкого реального времени).
Функции штрафа определены для работ i= <s'i, si, fi, ti> и имеют вид Fi = Fi(s', s, f, t), где
-
s' – время старта работы;
-
[s, f) – директивный интервал работы;
-
t – время выполнения работы.
В таблице:
-
f' = s' + t – время завершения работы;
-
c1, c2 - константы, не зависящие от конкретной работы.
| Название штрафной функции | Математическое представление: Fi = |
| Отставание [1,2,3,11,13,14,15] | max{0, f'i – fi} |
| Смещение [1,2,4,5,6,11,13,14] | f'i – fi |
| Завершение [2, 4,5,6,7,14] | f'i |
| Дискретное запаздывание [1,4,15] | 1, если f'i > fi, иначе 0 |
| Отклонение [5] | |fi' – fi| |
| Опережение [5,13] | max{0, fi – fi'} |
| Непопадание [7] | 0, если (si', fi') (si, fi), иначе 1 |
| Простых элементов [8,9] | U * (U + 1) / 2, где U = max(fi' – fi,0) + max(si' – si,0) |
| Красильщика [11] | fi' + consti |
| Длительность [13] | fi' – si' |
| «Жесткие сроки» [12] | -c1, если fi' ≤ fi, иначе c2(fi'/fi – 1) |
| Крепкие сроки [12] | -c1, если fi' ≤ fi, иначе c2 |
| Мягкие сроки [12] | -c1, если fi' ≤ fi, иначе (c2-c1)fi'/fi – c2 |
| Неубывающая кусочно-неперывная (общий вид) [15] | 0, если fi' ≤ fi, иначе E = φ, где φ > 0, φ – неубывающая кусочно-непрерывная функция |
| Ступенчатая [15] | 0, если fi' ≤ fi, иначе ai, где ai > 0, ai – некоторая константа для i-й работы |
| Длительность прохождения (Flow time) [16, 17] | f'i – si |
| Функция специального вида (1) [1] | φ(fi') + αi, где φ(fi') не убывает в полуинтрвале (0, f], α1 ≥ α2 ≥ … ≥ αn |
| Функция специального вида (2) [1] | αi * φ(fi'), где φ(fi') не убывает в полуинтрвале (0, f], α1 ≥ α2 ≥ … ≥ αn |
| Функция специального вида (3) [1] | φ(fi' + αi), где φ(fi') не убывает в полуинтрвале (0, f], α1 ≥ α2 ≥ … ≥ αn |
| Функция специального вида (4) [1] | aiui(fi'), ui(fi') = 0, если fi' ≤ f, иначе ui(fi') = 1; ai > 0 |
| Произвольная неубывающая [1] | Произвольная неубывающая функция |
Критерии оценки качества расписаний построенные на основе функций штрафа.
| Название критерия | Математическое представление |
| Максимум [1,4,5,6,11,13,14,15] | max Fi, i = 1..n |
| Взвешенный максимум [2,14] | max wiFi, I = 1..n |
| Сумма [9,10,13,14,15,16] |
|
| Взвешенная сумма [8,10,11] |
|
| Средняя сумма [13] |
|
| Взвешенная средняя сумма [14] |
|
Задача построения расписания обменов по шине с централизованным управлением (на примере стандарта MIL-STD 1533В)
Основное сообщение (передача данных от оконечного устройства оконечному устройству).
Рис.1.1. Пример формата одиночного сообщения.
Контроллер должен без паузы передать команду обмена данными с адресом оконечного устройства А на прием данных и команду обмена данными с адресом оконечного устройства Б на передачу данных. Оконечное устройство Б после установления факта достоверности принятой команды должно передать без пауз ответное слово и указанное в команде количество слов данных. Оконечное устройство А после установления факта достоверности адресованной ему информации должно передать ответное слово.
Шина в данной системе может рассматриваться как одноприборное устройство, обслуживающее исходно заданный набор работ без прерываний.
Дано:
-
Множество работ, которые должны выполняться на системе
![]()
. Для каждой работы заданы ![]()
- время выполнения, ![]()
- директивный интервал выполнения и выполняется условие ![]()
; -
Дополнительные ограничения
![]()
на корректность расписания ![]()
; -
Вектор значений технологических требований
![]()
.
Расписание выполнения работ, которое представляет собой упорядоченное множество
Здесь k - порядковый номер j-ой работы в расписании,
Характеристики
Тип файла документ
Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.
Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.
Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
