Курсовая работа Операционные системы НГТУ АВТФ. Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники
 Скачать 3.29 Mb.
|
|
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ КУРСОВАЯ РАБОТА По дисциплине «Операционные Системы» Студент Григорьев Даниил Андреевич группа АИ-02 (фамилия, инициалы) 1. Тема: «Управление вычислительными ресурсами В819» 2. Срок представления работы (проекта) к защите «26» мая 2022г. 3. Содержание пояснительной записки курсовой работы 3.1. Введение в проблему 3.2. Постановка задачи 3.3. Информационный обзор 3.4. Основная часть 3.5. Выводы 3.6. Заключение 4. Перечень графического материала: блок-схемы алгоритмов, входные параметры, структура конечного продукта, временные диаграммы. Руководитель работы ____________________ Коршикова Л.А. (подпись, дата) (инициалы, фамилия) Новосибирск 2022 ОглавлениеТеоретические основы планирования и диспетчеризации 3 1.Введение в предметную область 3 1.2.Диспетчеризация задач 6 2.Раздел 1 8 2.1. Задание. 8 2.2. Исходные данные 8 Таблица последовательностей. 9 2.3. Временные диаграммы использования FIFO и SJF. Таблицы результатов. 10 ДО FIFO 10 ДО SJF 16 16 2.4 Выводы 22 3.Раздел 2 23 3.1. Задание 23 3.2. Исходные данные 23 3.3. Временные диаграммы работы LIFO и SJF. 23 ДО LIFO 23 Таблица 7. Трассировка планировщика для до LIFO. 27 ДО SJF 30 Таблица 8. Трассировка планировщика для до SJF. 34 3.4. Выводы. 36 4.Список источников 37 Теоретические основы планирования и диспетчеризации Введение в предметную область Системное программное обеспечение – комплекс программ, являющийся общим для тех, кто использует технические средства компьютера. Операционная система – комплекс управляющих и обрабатывающих программ, предназначенный для наиболее эффективного использования ресурсов вычислительной системы. Основные функции ОС: Распределение памяти и организация виртуальной памяти. Планирование и диспетчеризация задач в соответствии с заданной стратегией и дисциплиной обслуживания. Организация обмена сообщениями между выполняющимися процессами. Защита одной программы от влияния другой. Функция ОС – управление ресурсами: Планирование ресурса – то есть определение, какому процессу, когда и в каком количестве (если ресурс может выделяться частями) следует выделить данный ресурс; Удовлетворение запросов на ресурсы; Отслеживание состояния и учёт использования ресурса – то есть поддержание оперативной информации о том, занят или свободен ресурс и какая доля ресурса уже распределена; Разрешение конфликтов между процессами. Классификация ОС. Операционные системы могут различаться особенностями реализации внутренних алгоритмов управления основными ресурсами компьютера (процессорами, памятью, устройствами), особенностями использованных методов проектирования, типами аппаратных платформ, областями использования и многими другими свойствами. Ниже приведена классификация ОС по нескольким наиболее основным признакам (рис.1).  Рисунок 1. Классификация ОС ОС не только предоставляет пользователям и программистам удобный интерфейс к аппаратным средствам компьютера, но и является механизмом, распределяющим ресурсы вычислительной системы. К числу основных ресурсов, управление которыми осуществляет ОС, относятся процессоры, основная память, таймеры, наборы данных, диски, накопители на магнитных лентах, принтеры, сетевые устройства и др. Ресурсы разделяются между процессами. Для решения задач управления ресурсами разные ОС используют различные алгоритмы, особенности которых, в конечном счете, и определяют облик ОС. Управление ресурсами включает решение следующих общих, не зависящих от типа ресурса задач: – Планирование ресурса – то есть определение, какому процессу, когда и в каком количестве (если ресурс может выделяться частями) следует выделить данный ресурс; – Удовлетворение запросов на ресурсы; – Отслеживание состояния и учёт использования ресурса – то есть поддержание оперативной информации о том, занят или свободен ресурс и какая доля ресурса уже распределена; – Разрешение конфликтов между процессами. Наиболее важными подсистемами ОС являются подсистемы управления процессами, памятью, файлами и внешними устройствами, а также подсистемы пользовательского интерфейса, защиты данных и администрирования. Подсистема управления процессами Для каждого вновь создаваемого процесса ОС генерирует системные информационные структуры, которые содержат данные о потребностях процесса в ресурсах вычислительной системы, а также о фактически выделенных ему ресурсах. Таким образом, процесс можно также определить как некоторую заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает синхронизацию процессов, а также обеспечивает взаимодействие между процессами. В многозадачной системе процесс может находиться в одном из трёх основных состояний: Выполнение – активное состояние процесса, во время которого процесс обладает всеми необходимыми ресурсами и непосредственно выполняется процессором; Ожидание – пассивное состояние процесса, процесс заблокирован, он не может выполняться по своим внутренним причинам, он ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого процесса, освобождения какого-либо необходимого ему ресурса; Готовность - также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса. В ходе жизненного цикла каждый процесс переходит из одного состояния в другое в соответствии с алгоритмом планирования процессов, реализуемым в данной операционной системе. Общие сведения о планировании заданий. Планирование распределения процессора производится на нескольких уровнях. Один из них - средний уровень планирования - диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирование повторяется, процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки. Диспетчер – программа, которая выбирает задачи из “очереди на выполнение”, переводит их в активное состояние, и передаёт им контроль над центральным процессором. Стратегии планирования Прежде всего следует отметить, что при рассмотрении стратегий планирования, как правило, идет речь о краткосрочном планировании, то есть о диспетчеризации. Стратегия планирования определяет, какие процессы мы планируем на выполнение для того, чтобы достичь поставленной цели. Известно большое количество различных стратегий выбора процесса, которому необходимо предоставить процессор. Среди них, прежде всего, можно назвать следующие стратегии: По возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты; Отдавать предпочтение более коротким процессам; Предоставлять всем пользователям (процессам пользователей) одинаковые услуги, в том числе и одинаковое время ожидания. Оценка эффективности планирования. Существует несколько оценок эффективности планирования. Одной из них является время обращения задания – время прошедшее с момента поступления задания в систему до момента завершения его выполнения.  где, t – время обращения задания, tз – время завершения задания, tп – время поступления задания. Но эта оценка не является универсальной. Более универсальной оценкой, позволяющей сравнить между собой задания любой дисциплины, является взвешенное время обращения.  где, W – взвешенное время обращения, T – действительное время обращения. Для случая когда в систему поступает N заданий, можно произвести оценку по среднему взвешенному времени обращения.  где, Wср – среднее взвешенное время обращения, Wi – взвешенное время обращения i-го задания, N – количество заданий. Диспетчеризация задач Планирование распределения процессора производится на нескольких уровнях. Один из них - средний уровень планирования - диспетчеризация. На этом уровне диспетчер задач (планировщик процессов) выбирает одну задачу из числа готовых к выполнению и предоставляет ей процессор. Каждая задача занимает процессор относительно малое время (как правило, недостаточное для выполнения задачи), затем диспетчирование повторяется, процессор выделяется другой задаче. Диспетчер принимает текущие решения в динамике сложившейся конкретной обстановки. Диспетчер – программа, которая выбирает задачи из “очереди на выполнение”, переводит их в активное состояние, и передаёт им контроль над центральным процессором. Дисциплина обслуживания – это правила, в соответствии с которым из очереди выбирается соответствующее требование и предоставляется ресурс. Приоритет – это преимущественное право на первоочередное обслуживание.  Рисунок 2. Классификация дисциплин обслуживания. Требования к ДО: ДО должны обеспечивать высокий показатель эффективности, при этом время ожидания должно быть равномерно Необходимо, чтобы ДО была минимальна по трудоёмкости Пояснения к рис.2. приведены ниже. Бесприоритетные ДО: выбирают заявки без учёта их важности, а по принципу последовательности поступления. Линейные ДО: характеризуются одинаковым средним временем ожидания независимо от длительности заявки. Циклические ДО: имеются циклические очереди к ресурсу, т.е. очереди использующие принцип квантования ∆t т.е выбранная заявка получает ограниченный квант времени ∆t. В результате этого она может обслуживаться только с учётом определённого требования, она может завершиться полностью, либо заявки не хватит времени ∆t. В случае нехватки времени ∆t обслуживание прерывается, заявка становится в конец очереди и выбирается следующая по порядку Приоритетные ДО: выбирают заявки c учётом их важности. Линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой. Линейная дисциплина обслуживания LIFO (Last In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь последней. Линейная дисциплина обслуживания RAND (Randomize). Случайный выбор заявки из очереди. Циклическая дисциплина обслуживания RR (Round Rotation). Отличается от FIFO лишь временем обслуживания. Каждая заявка получает определённый квант времени (одинаковый для всех) . Дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания. Дисциплина обслуживания с фиксированным приоритетом PRT (PRioriTy). Из очереди заявок на обслуживание выбирается заявка с максимальным приоритетом. В настоящей работе рассматриваются 2 дисциплины обслуживания: линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой. дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания. Раздел 1 2.1. Задание. Вычислительная система располагает оперативной памятью (ОП) V и внешним обьемом памяти Н (НМД). ОП память выделяется перемещаемым разделами, которые исключают влияние фрагментации. Реализуется режим мультипрограммирования: если одновременно выполняется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очередное задание поступает через время ti, для простоты каждое задание состоит из одной задачи и требует обьем ОП - vi, обьем внешней памяти hi, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*hi , после чего начинается счет. Однако закрепленные за каждым заданием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Тi = q*hi + ti. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма: среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание, поступившее первым (правило FIFO); среди заданий в очереди, для которых достаточно свободных ресурсов, выбирается задание с наименьшим ti(правило SJF). Необходимо построить временную диаграмму мультипрограммной работы при использовании каждого из двух алгоритмов. На диаграмме выделить события (моменты поступления заданий, моменты назначения на выполнение, моменты начала счета, моменты завершения) и периоды между событиями. Для каждого периода указать процессорное время на задание, доступную память, доступную дисковую память, степень мультипрограммирования. Провести сравнение двух случаев по средневзвешенному времени обращения. 2.2. Исходные данные Средневзвешенное время обращения:  где,  - время завершения задания, - время поступления задания в систему,M - количество заданий в потоке, который поступает в систему,  — время, потраченное на ввод и работу задания, количество ОП, необходимое задаче,  количество ВП, необходимое задаче,  , — время загрузки задания в систему, — процессорное время, приходящееся на каждую задачу, с учётом коэффициента мультипрограммирования, — время, которое задание провело на процессоре.Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встретиться задания, содержащие одинаковые задачи. Номер задачи Кi для очередного задания определяется по формулам: Xi = [7 * Xi-1 + 417] mod 1000; Ki = [Xi / 7] mod 10, i=1M, Xo = N, где [c] - целая часть числа с, y mod z - остаток от деления y на z, Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) ti=ki . Таблица 1. Набор задач для нормировки вариантов.
Таблица последовательностей. Используя индивидуальный расстановочный код: X0=N=819, были рассчитаны Ki номера задач: X0=N=819 X1=[7*819+417] mod 1000=150 K1=[150/7] mod 10=1 X2=[7*150+417] mod 1000=467 K2=[467/7] mod 10=7 X3=[7*467+417] mod 1000=686 K3=[686/7] mod 10=8 X4=[7*686+417] mod 1000=473 K4=[473/7] mod 10=8 X5=[7*473+417] mod 1000=728 K5=[728/7] mod 10=4 X6=[7*728+417] mod 1000=513 K6=[513/7] mod 10=3 X7=[7*513+417] mod 1000=8 K7=[8/7] mod 10=1 X8=[7*8+417] mod 1000=473 K8=[473/7] mod 10=8 X9=[7*473+417] mod 1000=728 K9=[728/7] mod 10=4 X10=[7*728+417] mod 1000=513 K10=[513/7] mod 10=3 Произведем расчёт  .Для этого воспользуемся формулой  где,  -объём внешней памяти и q=5.          На основе полученных результатов и таблицы 1 (Набор задач для нормировки вариантов) составим таблицу 2. Таблица 2. Характеристики заданий.
|