Системное программное обеспечение

Каждой задаче выделяется только квант процессорного времени, ни одна задача не занимает процессор надолго, и время ответа оказывается приемлемым.

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

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

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

ане та, которая "выгодна" системе;

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

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

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

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

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

Это время называется временем реакции системы, а соответствующее свойство системы – реактивностью.

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

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

Литература

Основная:

1.Молчанов А.Ю. Системное программное обеспечение. Учебник для вузов. —

СПб.: Питер, 2003. — 396 с.

2.Молчанов А.Ю. Системное программное обеспечение. Лабораторный практикум.- СПб.: Питер, 2005.- 284 с.

3.Юров В.И. Assembler. Учебник для вузов. 2-е издание - СПб.: Питер.- 2004.-

637с.

4.Компаниец Р.И., Маньков Е.В., Филатов Н.Е. Системное программирование: Основы построения трансляторов + FD.- М.: КОРОНА принт.- 2004.- 255 с.

5.Фельдман Ф.К. Системное программирование на персональном компьютере.- 2004.- 512

6.Ахо А.,Сети Р., Ульман Дж. Компиляторы: принципы, технологии и инструменты: Пер. с англ. — М.: Издательский дом «Вильямс», 2003. — 768 с.

7.Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение. — СПб.:

Питер, 2002. — 734 с.

8.Олифер В.Г., Олифер Н.А. Сетевые операционные системы. СПб.: Питер, 2002. — 544

Дополнительная:

1.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2001. – Ч. 1. – 96 с.

2.Малявко А.А. Теория формальных языков: Учеб. пособие: В 3 ч. – Новосибирск: Изд-во НГТУ, 2002. – Ч. 2. – 96 с.

3.Ф.Льюис, Д. Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. М., Мир, 1979.

4.Л. Бек. Введение в системное программирование. М.,Мир, 1988.

5.В.Е.Котов, В.К.Сабельфельд. Теория схем программ. -М.: Наука, 1978

6.Автоматное управление асинхронными процессами в ЭВМ и дискретных системах /Под ред. В.И.Варшавского. -М.:Наука.

7.Питерсон Дж. Теория сетей Петри и моделирование систем.- М.: Наука. 1984.

8.Минский М. Вычисления и автоматы. - М.: Мир.- 1971.

9.Котов В.Е. Сети Петри. - М.: Наука. - 1984.-

10.Ахо А.,Хопкрофт Дж., Ульман Дж.Построение и анализ вычислительных алгоритмов. - М.: Мир. -1979.

11.Питерсон Дж. Теория сетей Петри и моделирование систем: Пер. с англ. –

М.: Мир, 1984. – 264 с.

Лекция 3 Управление памятью.

План

1.Иерархия памяти

2.Мультипрограммные системы с реальной памятью.

3.Виртуальная память

1.Иерархия памяти

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

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

Рассмотрим иерархическую организацию памяти

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

Система с несколькими уровнями иерархии памяти должна обеспечивать

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

Функции для управления памятью

Управление памятью можно представлять, как отображение информации в память посредством трех функций13 .

•Именующей функции f1, однозначно отображающей данное пользователем имя в идентификатор информации, к которой это имя относится.

•Функции памяти f2, отображающей однозначно определенные идентификаторы в истинные адреса памяти, в которых они находятся.

•Функции содержимого f3 ,отображающей каждый адрес памяти в значение, которое по этому адресу находится.

Имена, заданные	f1	Однозначные	f2	Ячейки	f3
Значения
пользователем	идентификаторы			памяти

Результат каждого из этих трех отображений зависит от времени. Это значит, что он может меняться в продолжение всего времени обработки задания системой, Например, результат отображения f1 не устанавливается до тех пор, пока задание не будет связано с системными модулями и файлами, которые в нем упоминаются. Результат отображения f2 может быть зафиксирован после загрузки задания. Однако при некоторых стратегиях распределения памяти отображение f2 меняется в течение всего времени, пока задание находится в оперативной памяти. Ясно, что результат отображения f3 меняется каждый раз, когда выполняется команда записи в память.

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

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

Эволюция видов организации памяти

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

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

2.Мультипрограммные системы с реальной памятью.

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

Очередь заданий для раздела 1				Операционная система
X1	Y1	Z1		Раздел 1
Очередь заданий для раздела 2				Раздел 2
X2	Y2	Z2

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

Очередь заданий

X	Y	Z	Операционная система

Раздел 1

Задания могут перемещаться в любой свободный раздел, размер которого это допускает

Раздел 2

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

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

Задание

Х 40К

Операционная система

Задание Y 60K

Задание Х 40К

Задание Y 60K

Свободно

Рис 11. Начальное распределение разделов при мультипрограммировании с переменными разделами

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

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

•стратегия первого подходящего, когда задание размещается в первом подходящем по размеру участке;

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

3.Виртуальная память

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

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

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

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

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

Сегментация

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

Как уже указывалось, в системе с сегментацией каждый адрес представляет пару [s,d]: s - имя сегмента и d - смещение. Каждой программе соответствует всегда присутствующая в памяти таблица сегментов, в которой каждому сегменту данного процесса соответствует одна запись. С помощью этой таблицы система отображает программные адреса в истинные адреса ОП. Адрес таблицы хранится в аппаратном регистре, называемом регистром таблицы сегментов.

Регистр таблицы сегментов

		s	d	+		d
+

Слово Граница

Признак Биты защиты Граница База s-тая

строка

таблицы

сегментов

Рис. 12 Вычисление адреса при сегментации

f3(слово)= f3(f3(f3(регистр таблицы сегментов)+s)+d)

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

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

Если в какой-то момент система пожелает переключить свое внимание на другой процесс, она просто заменят содержимое регистра таблицы сегментов на адрес другой таблицы сегментов, после чего ссылки вида [s,d] интерпретируются в соответствии с новой таблицей.

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

Страничная организация памяти

Страничная организация памяти (paging) - это такой способ управления памятью, при котором пространство адресов памяти разбивается на блоки фиксированной длины, называемыми физическими страницами.(page frame) . В этом случае адреса образуются подобно тому, как это делалось при сегментации пространства программных адресов. Каждый адрес представляет собой пару [p,d], где р - имя страницы, а d - смещение относительно начала страницы.

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

-признак, показывающий находится ли данная страница в ОП;

-указатель местоположения страницы (в ОП или вспомогательной

памяти);

-биты защиты для контроля способа доступа.

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

Регистр таблицы страниц

Страница

		р	d	+	d
+

Слово

Признак Биты защиты Указатель местоположения страницы

р-

тая

строка

таблицы

страниц

Рис.13 Вычисление адреса при страничной организации памяти f3(слово)= f3(f3(f3(регистр таблицы страниц)+p)+d)

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

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

прерыванием из-за отсутствия страницы.. Биты защиты гарантируют, что

данная страница будет использоваться в соотвтетствии с разрешенным для нее доступом, например, для чтения или для записи.

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

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

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

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

Комбинированная сегментно-страничная организация памяти

Сегментно-страничная организация (paging/segmentation) состоит в том,

что память разбивается на страницы для каждого сегмента по его собственной таблице страниц. Адреса при этом состоят их трех компонент [s,p,d], где s- номер сегмента, и вход в таблицу сегментов осуществляется через регистр таблицы сегментов, в которой s-тая запись содержит базовый адрес и границу таблицы страниц для этого сегмента; p - определяет запись в таблице страниц, которая указывает на p-тую страницу сегмента s; d- смещение, которое необходимо прибавить к базовому адресу страницы, чтобы добраться до искомого слова. Таким образом, адрес [s,p,d] может означать d-е слово p-той страницы s-того сегмента того задания, которое определяется содержимым регистра таблицы сегментов.

На такую трехкомпонентную ссылку требуется три цикла обращения к памяти, но если использовать, так называемый аппарат ассоциативных регистров,представляющих собой группу ячеек памяти с быстрым доступом, можно добиться того, чтобы время обращения к памяти оставалось в разумных пределах. Служат ассоциативные регистры для того, чтобы сопоставить комбинациям [s,p] физические места страниц.

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