Сформулируйте закон Мэрфи

если есть вероятность того, что какая-нибудь неприятность может случиться, то она обязательно произойдёт

Следствия

• Все не так легко, как кажется.

• Всякая работа требует больше времени, чем вы думаете.

• Из всех неприятностей произойдет именно та, ущерб от которой больше.

• Если четыре причины возможных неприятностей заранее устранимы, то всегда найдется пятая.

• Предоставленные самим себе события имеют тенденцию развиваться от плохого к худшему.

• Как только вы принимаетесь делать какую-то работу, находится другая, которую надо сделать еще раньше.

• Всякое решение плодит новые проблемы

57. Какие проявления закона Мэрфи в системах реального времени вы знаете?

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

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

Если такое ПО - разработанное, отлаженное и безупречно работающее на одной программной

платформе, по каким-то причинам (например, в связи с прекращением поддержки ОС со стороны

разработчика) переносится на другую платформу, в которой реализовано поведение использованного в программе API, отличное от исходной платформы, предсказуемость нарушается и при эксплуатации ПО возможно появление ошибок. В лучшем случае это будут легко выявляемые ошибки без критических последствий. Однако многолетняя практика эксплуатации ПО РВ показывает, что редко возникающие трудно обнаруживаемые программные ошибки в полном соответствии с законом Мёрфи проявляются в самый неподходящий момент и нередко приводят к катастрофическим по материальному ущербу и/или человеческим жертвам последствиям. Поэтому если возникают какие-то неясности для потенциально мобильного ПО в соответствии реализаций API друг другу и/или стандартам, эти неясности должны быть разрешены и устранены в возможно короткое время.

58. Когда вытесняющий на основе приоритетов планировщик принимает решения?

Если к концу заданного интервала времени процесс все еще работает.

Напротив, алгоритмы планирования с переключениями, называемого также

приоритетным планированием, выбирают процесс и позволяют ему работать некоторое

максимально возможное время. Если к концу заданного интервала времени процесс все еще

работает, он приостанавливается и управление переходит к другому процессу.

Приоритетное планирование требует прерываний по таймеру, происходящих в конце

отведенного периода времени (решения планирования могут, например, приниматься при

каждом прерывании по таймеру, или при каждом k-ом прерывании), чтобы передать

управление планировщику.

59. Какие алгоритмы диспетчеризации/планирования потоков доступны в ОС Neutrino?

В операционной системе QNX6 поддерживается несколько дисциплин планирования потоков: FIFO, карусельная (циклическая, round-robin, RR) и спорадическая**. Этот атрибут потока будет учитыватьсятолько, если микроядру приходится выбирать между потоками с одинаковым уровнем приоритета. Дисциплины планирования будут описаны дальше.

Дисциплина планирования FIFO

Если потоку задана дисциплина планирования FIFO (First In First Out, первый на входе, первый на выходе), то он может выполняться сколь угодно долго. Управление будет передано другому потоку только если поток будет вытеснен более приоритетным потоком, поток заблокируется или добровольно отдаст управление. При использовании этой дисциплины планирования, поток, который выполняет длительные математические вычисления, может полностью захватить процессор (т.е. не позволит выполняться потокам с тем же и более низким приоритетом).

Карусельная дисциплина планирования

Эта дисциплина планирования полностью аналогичная FIFO, за исключением того, что поток не выполняется «бесконечно», а работает только на протяжении определённого кванта времени (timeslice). По истечении кванта времени микроядро ставит процесс в конец очереди потоков, готовых к выполнению, и управление передаётся следующему потоку (на том же уровне приоритета). Если же на этом уровне приоритета нет других потоков в состоянии READY, то потоку выделяется ещё один квант времени.

Квант времени, который выделяется потокам с карусельной дисциплиной диспетчеризации для работы, может быть определён при помощи функции sched_rr_get_interval(). На самом деле квант времени (timeslice) ровно в четыре раза больше тактового интервала (ticksize). В свою очередь, тактовый интервал равен 1мс в системах с процессором 40МГц и выше и 10мс в системах с более медленным процессором***. Получается, что в привычных нам x86 компьютерах и ноутбуках квант времени равен 4мс.

Спорадическая дисциплина планирования

Как и в FIFO планировании, поток, для которого применяется спорадическое планирование, выполняется до тех пор, пока он не блокируется или не будет вытеснен потоком с более высоким приоритетом. Кроме того, так же как и в адаптивном планировании, поток, для которого применяется спорадическое планирование, получает пониженный приоритет. Однако спорадическое планирование даёт значительно более точное управление потоком.

60. В чём разница между дисциплинами планирования RR и FIFO?

Планирование по принципу FIFO (first-in-first-out)

Принцип FIFO, “первый пришедший обслуживается первым”, является наиболее простой дисциплиной планирования. ЦП предоставляется процессам в порядке их прихода в очередь готовности. После того, как процесс получает ЦП в свое распоряжение, он выполняется до завершения, т.е. это дисциплина планирования без переключения, поэтому ее не рекомендуют использовать в системах с разделением времени. Как правило, принцип FIFO редко используется самостоятельно в качестве основной дисциплины обслуживания, чаще он комбинируется с другими дисциплинами, например, диспетчирование процессов может выполняться согласно их приоритетам, однако процессы с одинаковыми приоритетами диспетчируются по принципу FIFO.

Циклическое планирование round robin (RR)

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

Классификация алгоритмов планирования задач в СРВ

Выделяют 2 класса АП:

1. Алгоритмы со статическим расписанием (другие названия - off-line, static, clock-driven) расписание запуска задач составляется заранее, до старта системы. Во время работы системы планировщик лишь следует этому расписанию.

2. Алгоритмы с динамическим расписанием (другие названия - on-line) расписание запуска задач составляется в ходе функционирования системы.

При этом АП второго типа, в свою очередь, подразделяются на:

1. Алгоритмы со статическими приоритетами (приоритеты задач не изменяются с течением времени)

2. Алгоритмы с динамическим приоритетами (разные работы одной и той же задачи могут иметь разный приоритет)

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

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

62. Какие алгоритмы планирования со статическими (фиксированными) приоритетами вы знаете?

Rate-monotonic (RM).

Метод назначает статические приоритеты задачам основываясь на их периодах. В этом методе приоритеты определяются следующим образом: задача с самым маленьким периодом получает самый высокий приоритет.

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

Исходный RM подход имеет ряд ограничений:

· Все задачи должны быть независимы друг от друга, т.е. между ними нет ни взаимодействия, ни общих ресурсов.

· Все задачи должны быть периодическими.

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

· Время выполнения постоянно.

· Для задач определено время выполнения в худшем случае.

· Все задачи имеют крайний срок, эквивалентный их периоду.

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

Так в протоколе приоритетных границ (Priority Ceiling Protocol) и некоторых других похожих (Stack Resource Protocol) удалось избавиться от ограничения на взаимодействие задач. Также было предложено много методов приведения непериодических задач к периодическим.

Deadline Monotonic (DM).

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

Такой метод расстановки приоритетов будет оптимальным, если выполняются следующие условия:

· множество задач – фиксированное множество жёстких задач;

· задачи периодические или спорадические;

· задачи имеют определённое (известное) время выполнения в худшем случае;

· для задач определён критический момент, то есть время выполнения в худшем случае.

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

63. Каким условиям должна удовлетворять система задач, чтобы к ней можно было применить RMS?

для RM(Rate Monotonic):

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

· Все задачи должны быть периодическими.

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

· Время выполнения постоянно.

· Для задач определено время выполнения в худшем случае.

· Все задачи имеют крайний срок, эквивалентный их периоду.

Для DM(Deadline Monotonic):

· множество задач – фиксированное множество жёстких задач;

· задачи периодические или спорадические;

· задачи имеют определённое (известное) время выполнения в худшем случае;

· для задач определён критический момент, то есть время выполнения в худшем случае.

64. В чём суть RMS?

Статические алгоритмы планирования (RMS, Rate Monotonic Scheduling). Используют приоритетное вытесняющее планирование. Приоритет присваивается каждой задаче до того, как она начала выполняться. Преимущество отдается задачам с самыми короткими периодами выполнения.

65. Фамилии авторов RMA?

Статья «Использование основанного на UML монотонного анализа пропорций для предсказания возможности планирования» (Using UML-Based Rate Monotonic Analysis to Predict Schedulability) написана Хусейном Сейедином (Hossein Saiedian) и Срикришнаном Рагураманом (Srikrishnan Raguraman).

66. Назовите фамилии некоторых учёных, внесших значительный вклад в конкурентное программирование

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

Отметим две основные вехи в развитии конкурентного программирования.

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

1984 год. Фирма British Semiconductor Manufacturer INMOS разрабатывает язык Occam - "язык ассемблера" для вычислительных систем, построенных из множества параллельно работающих специальных микропроцессоров - транспьютеров. Язык назван в честь средневекового английского философа-схоласта и логика Уильяма Оккама (1285-1349) и основан на математической теории Ч.А.Р.Хоара. Основное понятие языка - процесс. Процессы могут выполняться как последовательно, так и параллельно и взаимодействуют с помощью каналов.

Per Brinch Hansen (из ответов 2011года)

67. Что такое утилизация задачи, системы задач?

Назовем систему работающих на процессоре задач управляемой, если время всех откликов меньше жестких директивных сроков. Управляемость системы означает, что можно построить расписание задач, в котором все ограничения выполнены. При определенных условиях для проверки управляемости набора задач можно использовать лимиты утилизации. Утилизация U_i периодической задачи τ_i - это отношение наихудшего времени выполнения C_i задачи к периоду T_i: U_i=C_i/T_i. Сумма утилизаций U_total=∑_iU_i называется полной утилизацией для множества задач.

68. Каких учёных, основоположников конкурентного программирования, вы знаете?

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

Per Brinch Hansen (из ответов 2011года)

69. Кто является автором примитива синхронизации Семафор?

Э́дсгер Ви́бе Де́йкстра

в 1960-х гг. – участвовал в создании первой операционной системы, построенной в виде множества параллельно исполняющихся взаимодействующих процессов. Именно в процессе этой работы появились понятия синхронизации процессов, идея семафора, а также была четко осознана необходимость в структуризации процесса программирования и самих программ. В 1970-е гг. вместе с Чарльзом Хоаром и Никлаусом Виртом разработал основные положения методологии разработки программ – структурного программирования.

70. Какая книга Хоара издана на русском языке?

Хоар Ч., Взаимодействующие последовательные процессы. М: Мир, 1989

Книга известного системного программиста и теоретика информатики (Великобритания), последовательно излагающая теорию взаимодействующих процессов; эта тематика тесно связана с такими реальными понятиями, как операционные системы, мультипроцес­сорные комплексы и сети ЭВМ. Автор рассматривает параллелизм в языках высокого уровня АДА, Симула 67, Паскаль.

71. Достаточное условие планируемости по RMS. Что оно означает?

Для систем с произвольными соотношениями между периодами задач имеет место следующая теорема (критерий проверки планируемости системы алгоритмом RMS):

Теорема.

Система {Tj} n независимых вытесняемых периодических задач с периодами, равными относительным крайним срокам, планируется на одном процессоре _если_ коэффициент использования процессорного времени этой системы не превышает величины URM = n(21/n - 1).

Это условие является достаточным, но не необходимым.

72. В чём суть DMS?

DMS - способ назначения приоритетов в планировщике (deadline monotonic scheduling). В этом алгоритме приоритеты назначаются по немного другому правилу: чем меньше относительный крайний срок задачи, тем выше ее приоритет.

73. В каком смысле онлайновые алгоритмы планирования, основанные на вытеснении с учётом приоритетов, являются жадными?

Приоритет имеет обмен, для которого потребуется наименьшее время. «Жадный» алгоритм на каждом шаге пытается получить максимальный эффект.

На процессорном уровне диспетчеризация происходит по принципу "самое раннее из срочных заданий выполняется первым".

74. Что означает понятие оптимальности алгоритма планирования?

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

75. Для какого класса алгоритмов планирования RMA является оптимальным?

RMA оптимален для алгоритмов со статическими приоритетами и для него надо чтоб конец периода таска совпадал с дедлайном.

Частотно-монотонная теория диспетчеризации - частный случай теории диспетчеризации с равномерным распределением критических сроков обслуживания, в которой пределы (критические сроки обслуживания) могут быть короче, чем периоды. (Для ситуации, в которой пределы длиннее, чем периоды, в настоящее время успешной теории не существует.) Для ситуации, в которой приоритеты основаны на пределах таким образом, что задачи с самым коротким критическим сроком выполнения получают самый высокий приоритет (диспетчеризация с равномерным распределением критических сроков обслуживания(deadline-monotonic scheduling)), достаточное и необходимое условие было доказано [14].

76. При каких условиях RMS и DMS совпадают?

Когда относительный deadline совпадает с периодом

77. Какой deadline используется при назначении приоритетов задачам по DMA?

Если deadline не равен периоду, то приоритеты назначаются обратно пропорционально величине относительного deadline

78. Какие алгоритмы планирования на основе динамических приоритетов вы знаете?

EDF, LST