Моделирование решения функциональной задачи с заданным значением процессорного времени. Практическое занятие 2_1. Занятие 2 Моделирование решения функциональной задачи с заданным значением процессорного времени
 Скачать 212.09 Kb.
|
|
Практическое занятие №2 Моделирование решения функциональной задачи с заданным значением процессорного времени Известно, что операционная система упрощает процесс взаимодействия процессора и его периферии. Центральным элементом каждой операционной системы является ядро. Ядро встроенной ОС управляет задачами, системной памятью и устройствами ввода / вывода. Также существуют особые виды ядер, называемые микроядрами и наноядрами, которые чаще всего используются во встроенных системах . В концепцию ядра входят платформенно-зависимые и платформенно-независимые части, что приводит к разделению ядра на два слоя (см. рис. 1). Разделение ядра таким образом сокращает количество изменений кода в зависимости от аппаратной платформы, что упрощает портирование ОС с одной платформы к другую. При этом не нужно менять платформенно-независимый код, в результате чего требуются минимальные изменения в прикладном программном обеспечении.
Управление задачами реализуется с использованием планировщика, который помещает задачи в список ожидания. Различают три типа планировщиков, которые отличаются концепцией упорядочивания задач: • Планировщик циклического перебора, который подталкивает переключенные задачи в список для выполнения. • Планировщик приоритетов, который вставляет задачи в список по критерию приоритета. • Планировщик с несколькими списками, который перемещает задачи на выполнение на основе приоритетов в конкретный список приоритетов. Алгоритмы планирования Существует достаточно большой набор разнообразных алгоритмов планирования, которые предназначены для достижения различных целей и эффективны для разных классов задач. Многие из них могут использоваться на нескольких уровнях планирования. В этом разделе мы рассмотрим некоторые наиболее употребительные алгоритмы применительно к процессу кратковременного планирования. First-Come, First-Served (FCFS) Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO, сокращение от First In, First Out (первым вошел, первым вышел). Такой алгоритм выбора процесса осуществляет невытесняющее планирование. Процесс, получивший в свое распоряжение процессор, занимает его до истечения текущего CPUburst . После этого для выполнения выбирается новый процесс из начала очереди.
Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p0, p1 и p2, для которых известны времена их очередных CPUburst . Эти времена приведены в таблице 1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPUburst , что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь. Если процессы расположены в очереди процессов, готовых к исполнению, в порядке p0, p1, p2, то картина их выполнения выглядит так, как показано на рис. 4. Первым для выполнения выбирается процесс p0, который получает процессор на все время своего CPUburst , т. е. на 13 единиц времени. После его окончания в состояние исполнение переводится процесс p1, он занимает процессор на 4 единицы времени. И, наконец, возможность работать получает процесс p2. Время ожидания для процесса p0 составляет 0 единиц времени, для процесса p1 – 13 единиц, для процесса p2 – 13 + 4 = 17 единиц. Таким образом, среднее время ожидания в этом случае – (0 + 13 + 17)/3 = 10 единиц времени. Полное время выполнения для процесса p0 составляет 13 единиц времени, для процесса p1 – 13 + 4 = 17 единиц, для процесса p2 – 13 + 4 + 1 = 18 единиц. Среднее полное время выполнения оказывается равным (13 + 17 + 18)/3 = 16 единицам времени.  Рис. 4. Выполнение процессов при порядке p0,p1,p2 Если те же самые процессы расположены в порядке p2, p1, p0, то картина их выполнения будет соответствовать рис.5. Время ожидания для процесса p0 равняется 5 единицам времени, для процесса p1 – 1 единице, для процесса p2 – 0 единиц. Среднее время ожидания составит (5 + 1 + 0)/3 = 2 единицы времени. Это в 5 (!) раз меньше, чем в предыдущем случае. Полное время выполнения для процесса p0 получается равным 18 единицам времени, для процесса p1 – 5 единицам, для процесса p2 – 1 единице. Среднее полное время выполнения составляет (18 + 5 + 1)/3 = 8 единиц времени, что почти в 2 раза меньше, чем при первой расстановке процессов.  Рис. 5. Выполнение процессов при порядке p2, p1, p0 Как мы видим, среднее время ожидания и среднее полное время выполнения для этого алгоритма существенно зависят от порядка расположения процессов в очереди. Если у нас есть процесс с длительным CPUburst , то короткие процессы, перешедшие в состояние готовность после длительного процесса, будут очень долго ждать начала выполнения. Поэтому алгоритм FCFS практически неприменим для систем разделения времени – слишком большим получается среднее время отклика в интерактивных процессах. Round Robin (RR) Модификацией алгоритма FCFS является алгоритм, получивший название RoundRobin (RoundRobin – это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см.рис. 6.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.  Рис. 6. Процессы на карусели Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта. Время непрерывного использования процессора, необходимое процессу (остаток текущего CPUburst ), меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение поступает новый процесс из начала очереди, и таймер начинает отсчет кванта заново. Продолжительность остатка текущего CPUburst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов, готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале. Задание к практическому занятию Провести моделирование задания из практического занятия №1 при условии, что каждой задаче (сортировки с параметрами) выделено достаточное для ее выполнения процессорное время в операционной системе MS Windows Разработать алгоритм переключения выполнения задач Привести и описать структурную схему программного комплекса, необходимого для выполнения заданий 1,2 Разработать программное обеспечение программного комплекса Провести тестирование программного комплекса По результатам тестирования провести анализ временных характеристик. Отчет по практическому занятию должен содержать Структурную схему программного комплекса Математическое ожидание и дисперсию временных характеристик Выводы по применению. | ||||||||||||||||||
