Лекции по "Системному программированию"

21. Планирование и диспетчеризация.  Алгоритмы планирования.

Задачи алгоритмов планирования:

- справедливость - каждому процессу предоставляется  справедливая доля процессорного  времени. Сопоставимые процессы  получают сопоставимое обслуживание;

- принудительное  применение политики планирования;

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

Для систем пакетной обработки данных:

- пропускная  способность - количество задач,  выполененных в единицу времени;

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

Стоит заметить, что алгоритм, увеличивающий пропускную способность, необязательно минимизирует оборотное время.

Для интерактивных  систем:

- задача  минимизации времени отклика  - время между получением команды  и получением результата;

- достижение  соразмерности - задачи должны  исполняться такое время, какое  от них ожидает пользователь.

Для систем реального времени (мультимедийные системы):

- жесткие  сроки выполнения некоторых операций  с целью предотвращения потери  данных;

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

Алгоритмы планирования.

Для систем пакетной обработки данных:

- FIFO (First In First Out) - задачи поступают на выполнение по мере поступления в систему. Алгоритм легок для понимания и программирования. Не выполняется задача баланса использования системы;

- «кратчайшая задача – первая» - если в очереди одновременно есть несколько задач, на исполнение выбирается самая короткая. Такой алгоритм минимизирует оборотное время. Версией этого алгоритма с переключением является алгоритм "наименьшее оставшееся время выполнения".

Для интерактивных систем:

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

В циклическом  алгоритме планирования есть важное допущение о том, что все процессы равнозначны. Принимая во внимание все  факторы, появляется необходимость  приоритетного планирования. Каждому  процессу присваивается определенный приоритет, и к выполнению принимается  процесс с наивысшим приоритетом. Чтобы предотвратить бесконечную  работу высокоприоритетных процессов, блокировщик может, например, с каждым тактом часов уменьшать приоритет текущего процесса, пока не произойдет переключение. Приоритеты могут присваиваться статически и динамически. Аналогом статического выделения приоритета могут служить воинские звания. В некоторых ОС существует специальная команда nice, которая позволяет программисту добровольно понизит приоритет процесса. ОС может динамически назначать приоритеты для достижения своих целей. Например, разумно давать высокий приоритет процессам, ограниченным возможностями устройств ввода/вывода. Поскольку большинство времени такие процессы ожидают прерывания, логично предоставить им процессор как только он потребуется, чтобы инициировать новую операцию ввода/вывода и заблокировать данный процесс. Простейшие алгоритмы обслуживания таких процессов состоит в установке приоритета = 1/f, где f - часть использованного в последний раз кванта времени.

Часто бывает удобно сгруппировать процессы в  классы по приоритетам и использовать приоритетное планирование среди классов  и циклическое планирование внутри класса. Процесс из нижнего класса получит управление только тогда, когда  очередь верхнего класса пуста. Поскольку  каждое переключение между процессами занимает значительную часть времени, логично выделять процессам, ограниченным возможностями процессора, больший  квант времени, что может привести к ухудшению времени отклика. Чтобы исправить этот недостаток, процессам из разных классов выдавались разные кванты времени. Например, процессам  первого класса выдвался 1 квант, второго - 2 и т.д. Если процесс использовал все отведенное ему время, на следующий раз ему уменьшали приоритет и увеличивали время работы. Если процесс одно время работает как вычислительный, то есть использует все отведенное ему время, а в другие моменты становится интерактивным, то, для увеличения его приоритета, отслеживается приход специального сигнала.

Лотерейное  планирование

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

 

22. Управление памятью. Однозадачные  системы. Многозадачность с фиксированными  разделами.

Часть ОС, которая  занимается управлением, распределением, очисткой памяти называется менеджером памяти. Менеджеры памяти делятся  на 2 типа:

- не перемещают  процессы между оперативной памятью  и диском;

- перемещают  процессы между оперативной памятью  и диском:

‡ перемещают процессы целиком (swapping);

‡ перемещают процессы постранично (paging).

Однозадачные  системы без подкачки на диск

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

- первая  схема использовалась в ранний компьютерах фоннеймоновской архитектуры;

 

 

 

 

 

 

- вторая  схема используется до сих  пор в простейших контроллерах;

 

 

 

 

 

 

- треться схема использовалась в ранних компьютерах на основе ОС DOS. Используется до сих пор в сложных контроллерах.

 

 

 

 

 

Многозадачность с фиксированными разделами

Большинство современныз систем поддерживают псевдопараллельную работу нескольких процессов. Самый легкий способ достижения многозадачности - это разделение памяти на N возможно неравных частей. Когда задание поступает в память, его располагают во входной очереди к наименьшему разделу, способному вместить его. Поскольку размер разделов фиксирован, все пространство раздела, не используемое процессом, пропадает.

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

23. Управление памятью. Настройка  адресов и защита.

Настройка адресов  и защита

Допустим, первая команда программы представляет собой вызов процедуры по абсолютному  адресу 100 внутри двоичного файла. Если программа загрузится в раздел 1, то команда обратится к абсолютному  адресу 100, находящемуся внутри ОС, а  правильная процедура находится  по адресу 100к + 100. Эта проблема известна как проблема перемещения программ в памяти или настройка адресов.

Одним из возможных  решений является модификация команд при загрузке программ в памяти. К каждому адресу будет добавляться  абсолютный адрес раздела. Для выполнения такой настройки компоновщик  должен присоеденить к программе список слов, которые являются адресами и подлежат модификации. Настройка адресов во время загрузки не решает проблему защиты. Вредоносная программа может создать новую команду с абсолютным адресом и перейти в другой раздел. Не существует стандартных средств, способных запретить программе обращения к любому слову в памяти. В качестве решения IBM разделила память на блоки по 2кб и назначила каждому блоку 4-битовый защитный код. Регистр PSW (Programm Status/Security Word) содержит 4-битовый ключ. Аппаратура перехватывает все попытки обратиться к любой части памяти, чей защитный код отличался от значения регистра PSW работающего процесса.

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

24. Управление памятью. Многозадачность  с динамическими разделами. Основная  подкачка.

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

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

25. Управление памятью с помощью  битовых массивов 

При таком  методе управления, ОС разбивает память на единичные блоки, и каждому  блоку соответствует один бит  в так называемом битовом массиве  либо битовой карте. Занятому под  процесс блоку соответствует  единица, свободному - нуль. Битовая  карта является достаточно простым  способом отслеживания распределения  памяти. Однако, поиск серии заданной длины является достаточно медленной операцией, посколькю искомая последовательность может пересекать границы слов. При выборе маленького размера единичного блока, битовая карта может занимать значительный объем памяти. При выборе большого блока могут возникнуть значительные потери из-за частичного использования последнего блока серии.

26. Управление памятью с помощью  связанных списков. Алгоритмы  предоставления памяти.

правление памятью  с помощью связных списков

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

- атрибута  занятости - P - занят (process), H - свободен, дыра (hole);

- адреса  начала фрагмента;

- длины фрагмента;

- указателя на следующую запись.

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

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

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

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

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

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

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

27. 28. Виртуальная память. Страничная  организация памяти. Основные проблемы.