РГР по теме Операционные системы. Захаров_А_Е_АВТ_109_РГР_ОС. Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники

• Название: Новосибирский государственный технический университет факультет автоматики и вычислительной техники кафедра вычислительной техники
• Анкор: РГР по теме Операционные системы
• Дата: 22.05.2023
• Размер: 3.46 Mb.
• Имя файла: Захаров_А_Е_АВТ_109_РГР_ОС.docx
• Тип: Документы; #1152001
• страница: 1 из 3

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО

ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ


РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА

По дисциплине «Операционные Системы»


Студент: Захаров Александр Евгеньевич

Группа: АВТ-109
Вариант: 135

Срок представления работы (проекта) к защите « » 2023 г.

Руководитель работы ____________________ Коршикова Л.А. (подпись, дата) (инициалы, фамилия)

Новосибирск 2023

Оглавление

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ 1

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 1

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 1

КАФЕДРА ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ 1

1

Теоретические основы планирования и диспетчеризации 4

1.1.Планирование 4

1.2.Диспетчеризация задач 5

2.Раздел 1 8

2.1. Задание. 8

2.2.Исходные данные 8

Таблица последовательностей. 9

2.3. Временные диаграммы использования FIFO и SJF. Таблицы результатов. 10

ДО FIFO 10

ДО SJF 14

14

2.4 Выводы 17

3.Раздел 2 18

3.1. Задание 18

Диспетчер использует метод разделения времени в сочетании с приоритетами. 18

3.2. Исходные данные 18

3.3. Временные диаграммы работы LIFO и PRT. 18

ДО LIFO 18

Таблица 7. Трассировка планировщика для до LIFO. 19

ДО PRT 21

Таблица 8. Трассировка планировщика для до PRT. 21

3.4Выводы. 23

1. Теоретические основы планирования и диспетчеризации 3

1.1. Планирование 3

1.2. Диспетчеризация задач 4

2. Раздел 1 7

2.1. Задание. 7

2.2. Исходные данные 7

Таблица последовательностей. 8

2.3. Временные диаграммы использования FIFO и SJF. Таблицы результатов. 9

ДО FIFO 9

ДО SJF 13

2.4. Выводы 16

3. Раздел 2 17

3.1. Задание 17

Диспетчер использует метод разделения времени в сочетании с приоритетами. 17

3.2. Исходные данные 17

3.3. Временные диаграммы работы LIFO и PRT. 17

ДО LIFO 17

Таблица 7. Трассировка планировщика для до LIFO. 18

ДО PRT 20

Таблица 8. Трассировка планировщика для до PRT. 20

3.4. Выводы. 22

Теоретические основы планирования и диспетчеризации

1. 
   Планирование
   

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

В мультипрограммной системе поток (процесс, если операционная система работает только с процессами) может находиться в одном из трех основных состояний:

1. 
   выполнение – активное состояние потока, во время которого поток обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;
   
2. 
   ожидание – пассивное состояние потока, находясь в котором, поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например, завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);
   
3. 
   готовность – также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые ресурсы, готов выполняться, но процессор занят выполнением другого потока).
   

Функцией службы управления процессом является распределение аппаратных ресурсов. У нее есть две основные составляющие:

• 
  планировщик заданий
  
• 
  планировщик задач (процессов)
  

Объектами работы планировщика заданий являются задания, а планировщик задач управляет процессами.

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

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

Дисциплины обслуживания.

Термин «дисциплина обслуживания» означает некое правило обслуживания, в том числе и учет каких-либо приоритетов при обслуживании. Например, дисциплина «пришедший последним обслуживается первым» определяет обслуживание в порядке, обратном очередности поступления соответствующих запросов.

В данной работе рассматриваются 2 дисциплины обслуживания:

Линейная ДО FIFO (First Input First Output).
Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.

ДО с фиксированным приоритетом SJF (Short Job First)
Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.

Оценка эффективности планирования.

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

где, t ­­– время обращения задания, t_з – время завершения задания, t_п – время поступления задания.

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

где, W – взвешенное время обращения, T – действительное время обращения.

Для случая, когда в систему поступает N заданий, можно произвести оценку по среднему взвешенному времени обращения.

где, W_ср – среднее взвешенное время обращения, W_i – взвешенное время обращения i-го задания, N – количество заданий.

2. 
   Диспетчеризация задач
   

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

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

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

При реализации приоритетного обслуживания отдельным задачам предоставляется преимущественное право попасть в состояние исполнения.

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

Диспетчер — это еще один компонент системы планирования. Это модуль, который передает управление процессором тому процессу, который был выбран на уровне кратковременного планирования .

Дисциплина обслуживания – это правила, в соответствии с которым из очереди выбирается соответствующее требование и предоставляется ресурс.

Требования к дисциплинам обслуживания:

1) ДО должны обеспечивать показатель эффективности обслуживания, то есть время ожидания должно быть равномерным;

2) Трудоемкость ДО должна быть минимальной.

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

Линейные ДО: характеризуются одинаковым средним временем ожидания независимо от длительности заявки.

Циклические ДО: Имеются циклические очереди к ресурсу, т.е. очереди, использующие принцип квантования ∆t, то есть выбранная заявка получает ограниченный квант времени ∆t. В результате этого она может обслуживаться только с учётом определённого требования, она может завершиться полностью, либо заявки не хватит времени ∆t. В случае нехватки времени ∆t обслуживание прерывается, заявка становится в конец очереди и выбирается следующая по порядку.

Бесприоритетные ДО: выбирают заявки без учёта их важности, а по принципу последовательности поступления.

Приоритетные ДО:

1. Линейная дисциплина обслуживания FIFO (First In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь первой.

2. Линейная дисциплина обслуживания LIFO (Last In – First Out). Из очереди заявок на обслуживание выбирается заявка, поступившая в очередь последней.

3. Линейная дисциплина обслуживания RAND (Randomize). Случайный выбор заявки из очереди.

4. Циклическая дисциплина обслуживания RR (Round Rotation). Отличается от FIFO лишь временем обслуживания, так как каждая заявка получает определённый квант времени.

5. Дисциплина обслуживания с фиксированным приоритетом SJF (Short Job First). Из очереди заявок на обслуживание выбирается заявка с минимальным временем обслуживания.

6. Дисциплина обслуживания с фиксированным приоритетом PRT (PRioriTy). Из очереди заявок на обслуживание выбирается заявка с максимальным приоритетом.

Приоритетные ДОвыбирают заявки c учётом их важности.

2. 
   Раздел 1
   

2.1. Задание.
Вычислительная система располагает оперативной памятью (ОП) V и внешним обьемом памяти Н (НМД). ОП память выделяется переме­щаемым разделами, которые исключают влияние фрагментации. Реали­зуется режим мультипрограммирования: если одновременно выполня­ется несколько задач, то процессорное время распределяется между ними равномерно. В систему поступает поток из М заданий, очеред­ное задание поступает через время t_i, для простоты каждое задание состоит из одной задачи и требует обьем ОП - v_i, обьем внешней памяти h_i, процессорное время. Каждое задание использует свою внешнюю память только для ввода данных в течение времени q*h_i , после чего начинается счет. Однако закрепленные за каждым зада­нием носители освобождаются только после завершения задания. Предположим, возможно параллельное использование внешней памяти заданиями без задержки друг друга. Если бы задания выполнялись по одному, то на каждое задание было бы затрачено время Т_i = q*h_i + t_i. Вновь поступившие задания помещаются в очередь. Для выбора заданий из очереди на выполнение используются два алгоритма:

1. 
   среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание, поступившее первым (правило FIFO);
   
2. 
   среди заданий в очереди, для которых достаточно свободных ре­сурсов, выбирается задание с наименьшим t_i(правило SJF).
   

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

2. 
   Исходные данные
   

Средневзвешенное время обращения:



где - время завершения задания,

- время поступления задания в систему.

Для нормирования различных вариантов последовательностей заданий используется набор из 10 типов задач (см. таблицу 1). Каждое задание включает одну из этих 10 задач. В одном потоке заданий могут встретиться задания, содержащие одинаковые задачи. Номер задачи К_i для очередного задания определяется по формулам:

X_i = [7 * X_i-1 + 417] mod 1000;

K_i = [X_i / 7] mod 10, i=1M, Xo = N,

где

[c] - целая часть числа с,

y mod z - остаток от деления y на z,

Xo = N = 135

Значение используемых параметров: V=16, H=12, q=5, M=10, последовательность периодов времени (интервал поступления заданий) t_i=k_i .
Таблица 1. Набор задач для нормировки вариантов.

K	0	1	2	3	4	5	6	7	8	9
v	6	3	2	4	3	5	7	9	4	1
h	2	4	3	1	2	0	4	1	6	3
τ	60	90	20	10	60	30	70	30	40	20

Таблица последовательностей.

Используя индивидуальный расстановочный код: X0=N=873, были рассчитаны K_i номера

задач:

X0=N=135

X1=[7*135+417] mod 1000=620

K1=[620/7] mod 10=8

X2=[7*620+417] mod 1000=757

K2=[757/7] mod 10=8

X3=[7*757+417] mod 1000=716

K3=[716/7] mod 10=2

X4=[7*716+417] mod 1000=429

K4=[429/7] mod 10=1

X5=[7*729+417] mod 1000=420

K5=[420/7] mod 10=0

X6=[7*420+417] mod 1000=357

K6=[357/7] mod 10=1

X7=[7*357+417] mod 1000=916

K7=[916/7] mod 10=0

X8=[7*916+417] mod 1000=829

K8=[829/7] mod 10=8

X9=[7*829+417] mod 1000=220

K9=[220/7] mod 10=1

X10=[7*220+417] mod 1000=957

K10=[957/7] mod 10=6

Таблица 2. Характеристики заданий.

№	Xi	Ki	vi	hi	τ i	ti	q*hi	Тi
1	620	8	4	6	40	8	30	70
2	757	8	4	6	40	8	30	70
3	716	2	2	3	20	2	15	35
4	429	1	3	4	90	1	20	110
5	420	0	6	2	60	0	10	70
6	357	1	3	4	90	1	20	110
7	916	0	6	2	60	0	10	70
8	829	8	4	6	40	8	30	70
9	220	1	3	4	90	1	20	110
10	957	6	7	4	70	6	20	90