Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Управление памятью
Уровни памяти:
- регистровая;
- кеш;
- ОЗУ, ОП;
- внешние устройства.
Виртуальная память (ВП)
Виртуальная память может быть реализована для любого из этих уровней. При реализации виртуальной памяти пользователю предоставляются обычные средства ОЗУ, а именно:
- последовательный вид доступа;
- непосредственная адресация;
- время доступа сравнимое со временем доступа реальной ОЗУ.
Новые свойства виртуальной памяти:
-- очень большой объём адресного пространства, получаемый в монопольное распоряжение программиста;
-- степень виртуальности может быть разной.
Основные понятия и концепции виртуальной памяти
Физическая память – это среда хранения из элементов, адресуемых в соответствии с физическими возможностями памяти и принятым способом адресации.
Множество адресов, упорядоченных по некоторому признаку, называют адресным пространством.
Механизм физической адресации элементов памяти, есть основа более сложного механизма доступа, реализуемого программно-аппаратными методами. Основная задача диспетчера виртуальной памяти заключается в отображении линейного пространства адресов виртуальной памяти на часть адресного пространства физической памяти.
Построение механизма виртуальной памяти основано на решении четырёх задач:
Задача размещения: заключается в выборе страницы (сегмента) в ОЗУ, куда будут отображаться страницы (сегменты) виртуальной памяти. Фактически, это означает, что необходимо произвести преобразование виртуальных адресов в физические, и наоборот.
Задача преобразования: преобразует адрес виртуальный в адрес оперативный и наоборот.
Задача перемещения: в архивной среде выбирается такая информация, которая принадлежит отображаемым виртуальным страницам, и она передаётся в страницы (сегменты) ОЗУ, найденные в результате решения задачи размещения.
Задача замещения: заключается в выборе кандидата на перераспределение.
Итак, ОС содержит 2 таблицы, описывающие состояние страниц и сегментов:
1) PMT (Page Map Table) – это карта памяти определяет положение сегмента в ОП;
2) Таблица страничных кадров (ТСК) – следит за состоянием страниц (занята/свободна/изменена).
Когда возникает прерывание, таблица рассматривается в поисках свободного страничного кадра. Если он найден, то требуемая страница может быть загружена немедленно. Иначе, страница, находящаяся в памяти, должна быть вытолкнута, чтобы освободить место для той страницы, которую надо загрузить. Если выталкиваемая страница с момента загрузки была модифицирована, то её новая версия должна быть переписана во внешнюю память. Если нет, то она может быть просто уничтожена. Все эти операции делает программа страничных прерываний, при этом она осуществляет динамичное преобразование адресов и обрабатывает страничные прерывания.
Часть алгоритма этой программы реализуется аппаратным способом, а вторая часть – программным способом.
Эта программа требует по крайней мере одной операции ввода-вывода, поэтому для её работы требуется гораздо больше времени, чем у всех остальных обработчиков прерываний. Однако закрывать прерывания нежелательно. Во время страничного обмена надо дать возможность работать процессору, поэтому при прерывании по отсутствию страниц, сначала определяется, какое действие надо выполнить и сохранить информацию о состоянии прерванного процесса. Затем в течение оставшегося времени разрешается функционирование системы прерываний.
Procedure PAGEFAULT {реализована как часть ОС}
<сохранить состояние процесса из рабочей области прерываний>;
<пометить этот процесс как блокированный (blocked)>;
if <имеется свободный страничный кадр> then
begin
<выбрать свободный страничный кадр>;
<пометить выбранный кадр в таблице страничных кадров как 'занятый'>;
<разрешить все прерывания>
end
else
begin
<выбрать страницу для выталкивания>;
<пометить выбранный кадр в таблице страничных кадров как 'занятый'>;
<разрешить все прерывания>;
if <выбранная страница была модифицирована> then
begin
<обновить PMT и таблицу страничных кадров>;
<выдать запрос на ввод-вывод>;
<ждать завершения операции записи>;
end
end;
<выдать запрос на ввод-вывод для чтения страниц в выбранный страничный кадр>;
<ожидать завершения операции чтения>;
<обновить PMT и таблицу страничных кадров>;
<восстановить состояние пользовательского процесса, пометив процесс, как “ready”>
end.
Кэш файловой системы.
Кэш — промежуточный буфер с быстрым доступом, содержащий информацию, которая может быть запрошена с наибольшей вероятностью. Доступ к данным в кэше идёт быстрее, чем выборка исходных данных из оперативной (ОЗУ) и быстрее внешней (жёсткий диск или твердотельный накопитель) памяти, за счёт чего уменьшается среднее время доступа и увеличивается общая производительность компьютерной системы. Прямой доступ к данным, хранящимся в кэше, программным путем невозможен.
Кэш состоит из набора записей. Каждая запись ассоциирована с элементом данных или блоком данных (небольшой части данных), которая является копией элемента данных в основной памяти. Каждая запись имеет идентификатор, определяющий соответствие между элементами данных в кэше и их копиями в основной памяти.
Когда клиент кэша (ЦПУ, веб-браузер, операционная система) обращается к данным, прежде всего исследуется кэш. Если в кэше найдена запись с идентификатором, совпадающим с идентификатором затребованного элемента данных, то используются элементы данных в кэше. Такой случай называется попаданием кэша. Если в кэше не найдена запись, содержащая затребованный элемент данных, то он читается из основной памяти в кэш, и становится доступным для последующих обращений. Такой случай называется промахом кэша. Процент обращений к кэшу, когда в нём найден результат, называется уровнем попаданий или коэффициентом попаданий в кэш.
Например, веб-браузер проверяет локальный кэш на диске на наличие локальной копии веб-страницы, соответствующей запрошенному URL. В этом примере URL — это идентификатор, а содержимое веб-страницы — это элементы данных.
Если кэш ограничен в объёме, то при промахе может быть принято решение отбросить некоторую запись для освобождения пространства. Для выбора отбрасываемой записи используются разные алгоритмы вытеснения.
При модификации элементов данных в кэше выполняется их обновление в основной памяти. Задержка во времени между модификацией данных в кэше и обновлением основной памяти управляется так называемой политикой записи.
В кэше с немедленной записью каждое изменение вызывает синхронное обновление данных в основной памяти.
В кэше с отложенной записью (или обратной записью) обновление происходит в случае вытеснения элемента данных, периодически или по запросу клиента. Для отслеживания модифицированных элементов данных записи кэша хранят признак модификации .
Промах в кэше с отложенной записью может потребовать два обращения к основной памяти: первое для записи заменяемых данных из кэша, второе для чтения необходимого элемента данных.
Достижение оптимальной производительности.
Запишите баланс мощностей для заданной схемы.
-E1*I1+I2*E2+UJ*J = (I12)*R1+(I32)*R3+(I52)*R5+(J2)*R4
П Р О Ц Е Д У Р Ы И Ф У Н К Ц И И
Алгоритм решения задачи проектируется путем декомпозиции всей за-
дачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подп-
рограмм.
Подпрограмма - это последовательность операторов, которые опреде-
лены и записаны только в одном месте программы, однако их можно
вызвать для выполнения из одной или нескольких точек программы. Каж-
дая подпрограмма определяется уникальным именем. В языке ПАСКАЛЬ су-
ществуют два типа подпрограмм - процедуры и функции.
Процедура и функция - это именованная последовательность описаний
и операторов. При использовании процедур или функций ПАСКАЛЬ - прог-
рамма должна содержать текст процедуры или функции и обращение к про-
цедуре или функции. Тексты процедур и функций помещаются в раздел
описаний процедур и функций.
Процедура может содержать такие - же разделы описаний, что и ПАС-
КАЛЬ - программа, а именно: разделы описания модулей, меток, конс-
тант, типов, переменных, процедур и функций.
ПЕРЕДАЧА ИМЕН ПРОЦЕДУР И ФУНКЦИЙ В КАЧЕСТВЕ ПАРАМЕТРОВ. Во многих
задачах, особенно в задачах вычислительной математики, необходимо пе-
редавать имена процедур и функций в качестве параметров. Для этого в
TURBO PASCAL введен новый тип данных - процедурный или функциональ-
ный, в зависимости от того, что описывается.
Описание процедурных и функциональных типов производится в разделе
описания типов:
type
FuncType = Function(z: Real): Real;
ProcType = Procedure (a,b: Real; var x,y: Real);
Функциональный и процедурный тип определяется как заголовок проце-
дуры и функции со списком формальных параметров, но без имени. Можно
определить функциональный или процедурный тип без параметров, напри-
мер:
type
Proc = Procedure;
После объявления процедурного или функционального типа его можно
использовать для описания формальных параметров - имен процедур и
функций.
Кроме того, необходимо написать те реальные процедуры или функции,
имена которых будут передаваться как фактические параметры. Эти про-
цедуры и функции должны компилироваться в режиме дальней адресации с
ключом {$F+}.
Пример. Составить программу для вычисления определенного интеграла
tk
2t
I= S--------------- dt
sqrt(1-sin2t)
tn
по методу Симпсона. Вычисление подинтегральной функции реализовать с
помощью функции, имя которой передается как параметр. Значение опре-
деленного интеграла по формуле Симпсона вычисляется по формуле:
ISimps=2*h/3*(0.5*F(A)+2*F(A+h)+F(A+2*h)+2*F(A+3*h)+...
+2*F(B-h)+0.5*F(B))
где A и B - нижняя и верхняя границы интервала интегрирования,
N - число разбиений интервала интегрирования,
h=(B-A)/N, причем N должно быть четным.
Program INTEGRAL;
type
Func= function(x: Real): Real;
var
I,TN,TK:Real;
N:Integer;
{$F+}
Function Q(t: Real): Real;
begin
Q:=2*t/Sqrt(1-Sin(2*t));
end;
{$F-}
Procedure Simps(F:Func; a,b:Real; N:Integer; var INT:Real);
var
sum, h: Real;
j:Integer;
begin
if Odd(N) then N:=N+1;
h:=(b-a)/N;
sum:=0.5*(F(a)+F(b));
for j:=1 to N-1 do
sum:=sum+(j mod 2+1)*F(a+j*h);
INT:=2*h*sum/3
end;
begin
WriteLn(' ВВЕДИ TN,TK,N');
Read(TN,TK,N);
Simps(Q,TN,TK,N,I);
WriteLn('I=',I:8:3)
end.
Элементарные (базовые) и комбинированные операции в пространстве.
По аналогии с вариантом для плоскости для унификации матричных операций введем дополнительную координату, т.е. будем представлять координаты (x, y, z) точек объектов пространства в виде (x, y, z, 1). Данная форма является частным случаем более общего представления, используемого в проективной геометрии - (x, y, z, h). Рабочее трехмерное пространство представляет собой пространство проективной геометрии при H = const, поэтому перед началом работы необходимо определить величину H. Для упрощения дальнейших вычислений выбирается H = 1. Преобразования в подобной системе координат возможны только в том случае, если все координаты имеют одинаковую размерность, т.е. пространство является однородным, поэтому такая система координат называется системой однородных координат. Обобщая двумерную матрицу преобразований на трехмерный случай, получим:
Четыре подматрицы Т11, T21, T12, T22 определяют следующие виды преобразований в трехмерном пространстве:
1) Т11 определяет линейные преобразования частичного масштабирования, вращения и линейной трансформации;
2) Т21 определяет преобразование переноса геометрических объектов;
3) Т12 отвечает за построение перспективы;
4) Т22 отвечает за глобальный масштаб изображения.
Результатом воздействия матрицы преобразований Т на трехмерный геометрический объект (X Y Z 1) является новый геометрический объект, который, в общем случае, может иметь следующий вид:
(X' Y' Z' H') = (X Y Z 1) × T.
Чтобы новый объект располагался в том же пространстве, что и исходный, необходимо выполнить операцию нормализации:
(X' Y' Z' H') norm⇒ ( X'/H' Y'/H' Z'/H' 1) = (X* Y* Z* 1)
Таким образом, полное преобразование в трехмерном пространстве получается путем умножения матрицы координат исходного объекта на матрицу преобразований Т с последующей ее нормализацией. При помощи матрицы Т можно осуществить операции переноса, масштабирования, отображения, вращения, линейной трансформации и построение различного вида перспектив. Часть из этих операций может быть совмещена, а другие операции должны выполняться последовательно, например, трансформация и вращение. Возможность совмещения операций определяется отсутствием в их матрицах преобразований общих элементов. Например, операции переноса и вращения определяются элементами различных подматриц (соответственно Т11 и Т21), то есть ненулевые элементы не перекрываются, поэтому их
Перенос в трехмерном пространстве. Операция переноса реализуется при помощи следующей матрицы:
Масштабирование по осям координат. Диагональные элементы подматрицы Т11 позволяют произвести частичное масштабирование по координатным осям x, y, z.
(X Y Z 1 ) ×= (aX eY jZ 1)
Примечание. Обратите внимание на то, что коэффициенты частичного масштабирования a, e, j определяют увеличение размеров геометрических объектов, а коэффициент общего масштаба s определяет уменьшение размеров.
Вращение вокруг осей координат. Вращение вокруг осей координат в пространстве описывается по аналогии с вращением в плоскости вокруг начала системы координат (см. предыдущую тему). Пространственное вращение вокруг оси OZ совпадает с вращением вокруг начала системы координат в плоскости XOY (вариант, рассмотренный в предыдущей теме). Пространственное вращение вокруг оси OX будет соответствовать вращению вокруг начала системы координат в плоскости YOZ, а вокруг оси OY - в плоскости XOZ. С математической точки зрения вращение вокруг одной из координатных осей имеет место при равенстве определителя матрицы Т11 единице (det T11 = 1). Таким образом, для случая вращения вокруг оси OX матрица преобразований имеет вид:
а матрицы, описывающие повороты вокруг осей OY, OZ будут выгля-
деть следующим образом:
Примечание. Так как вращение описывается при помощи матричной операции умножения, которая не является коммутативной, то порядок вращения графического объекта будет влиять на конечный результат.
Отображения в пространстве. Зеркальные отображения реализуются для отображения относительно координатных плоскостей. Для отображения без изменения масштаба необходимо, чтобы диагональные элементы матрицы Т11 были по модулю равны единице, а определитель равнялся минус единице.
Аналогично определяется матрица для зеркального отображения относительно плоскостей XOZ, YOZ. Отображение относительно произвольных плоскостей можно получить при помощи комбинации операций переноса, вращения и отображения.
Для выполнения данной последовательности шагов, включающей прямые и обратные преобразования, используются операции преобразования, которое называется преобразованием конгруэнтности. Преобразование конгруэнтности - последовательность прямых и обратных преобразований:
T=A×B×C×…×X×…×CТ×BТ×AТ или T=AТ×BТ×CТ×…×X×…×C×B×A
Пространственная линейная трансформация. Недиагональныеэлементы матрицы Т11 определяют линейную трансформацию геометрического объекта в трехмерном пространстве. Например:
Внешняя сортировка.
При ВС требуется работать с данными, расположенными на внешних устройствах последовательного доступа. Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один компонент последовательности данных, что является существенным ограничением по сравнению с сортировкой массивов, где всегда доступен каждый элемент.
В основе большинства методов ВС лежит процедура слияния. Слияние означает объединение двух упорядоченных наборов данных в 1 упорядоченную последовательность с помощью повторяющегося выбора доступных в данный момент элементов.
В процессе слияния поочередно сравниваются ключи в парах, доступных в текущий момент записей из исходных наборов данных.
Запись с меньшим набором ключа помещается в результирующий набор данных и исключается из исходного файла. Действия повторяются, пока не будет исчерпан один из исходных наборов данных. Затем оставшиеся в другом наборе данные пересылаются в результирующий файл без изменения порядка следования.
Покажем реализацию процедуры слияния для двух упорядоченных массивов
A[1..n] , B[1..m] в результирующий набор данных C[1.. n+m]
i, j, k – элементы в соответствующих массивах. Схема процедуры слияния:
Пример слияния на наборах А=(3,8,17) и В=(4,17,21,30)
|
i |
A |
j |
B |
k |
C |
|
1 |
3,8,17 |
1 |
4,17,21,30 |
1 |
3 |
|
2 |
8,17 |
1 |
4,17,21,30 |
2 |
3,4 |
|
3 |
8,17 |
2 |
17,21,30 |
3 |
3,4,8 |
|
4 |
17 |
2 |
17,21,30 |
4 |
3,4,8,17 |
|
5 |
- |
2 |
17,21,30 |
5 |
3,4,8,17,17 |
|
6 |
3 |
21,30 |
6 |
3,4,8,17,17,21 |
|
|
7 |
4 |
30 |
7 |
3,4,8,17,17,21,30 |
|
|
8 |
5 |
Прямое слияние.
Алгоритм прямого слияния – простейший алгоритм внешней сортировки, основанный на процедуре слияния последовательностей, называемых серией и представляющих собой упорядоченные подпоследовательности из записей файлов.
Серия – несколько последовательно расположенных записей файла, упорядоченных по ключам.
Количество записей в серии называется ее длиной.
Последняя серия может иметь длину меньшую, чем остальные серии файлов.
Суть алгоритма прямого слияния заключается в след.
В исходном состоянии все n записей делятся на 2 файла t1, t2. считается, что каждый из этих файлов состоит из серии длины t.
1. соответствующие серии файлов t1, t2 сливаются попарно и поочередно записываются в файлы g1, g2, организованные в виде серий удвоенной длины относительно t1, t2
После этого t1, t2 делаются пустыми.
2. Соответствие серии файлов g1, g2, попарно сливаются и поочередно записываются в t1, t2, организованные в виде серий удвоенной длины относительно g1, g2. После этого g1, g2 делаются пустыми.
3. Шаги 1 и 2 повторяются до тех пор, пока 1 из 2 файлов в любой паре не станет пустым, тогда другой файл этой пары будет содержать единственную серию длины n, т.е. отсортированный исходный файл.
Следует обратить внимание на необходимость копирования последней серии, которая может остаться без пары.
На каждом проходе (шаг 1 или 2) выполняется слияние серий с получением новых серий удвоенной длины и одновременно разделение исходного набора данных на 2 файла.
После выполнения i проходов получаем 2 файла состоящих из серий 2^i
Окончание процесса происходит при выполнении условия:
2^i>=n
Следовательно, процесс сортировки прямым слиянием требует порядка log2n проходов.
А методы прямой сортировки требуют не меньше n проходов. Отсюда заметна более высокая скорость сортировки слияния даже по сравнению с прямыми методами сортировки.
Но, для сортировки массивов процедура слияния не используется, т.к. здесь требуется 2n ячеек памяти.
Из-за необходимости использования удвоенного объёма памяти, по сравнению с исходным файлом, для внутренней сортировки алгоритм используется редко.
Пример.
Исходная последовательность ключей:
47,55,12,42,94,18,6,40,32,51,86
T1: 47 |12 |94 |6 |32 |86
T2: 55|42|6,40|86
G1: 47,55|18,94|32,51
G2: 12,42|6,40|86
T1: 12,42,47,55|32,51,86
T2:6,18,40,94
G1: 6,12,18,40,42,47,55,94
G2: 32,51,86
T1: 6,12,18,32,40,42,47,51,55,86,94
T2: -
Естественное слияние;
В случае прямого слияния частичная упорядоченность сортируемых данных не дает никакого преимущества. Это объясняется тем, что на каждом проходе сливаются серии фиксированной длины. При естественном слиянии (ЕС) длина серий не ограничивается, а определяется количеством элементов в уже упорядоченных подпоследовательностях выделяемых на каждом проходе.
ЕС начинается с образования 2-х файлов t1, t2. Для этого поочередно считываются записи ai исходной последовательности (неупорядоченной) т.о., что если значения ключей соседних записей удовлетворяют условию f(ai)<=f(ai+1) (1), то они записываются в один файл. Как только встречаются f(ai)>f(ai+1) (2), то записи ai+1 копируются в другой файл. Процедура повторяется до тех пор, пока все записи исходной последовательности не будут распределены по файлам.
На некотором проходе алгоритма выполняется слияние пар серий из 2-х файлов аналогично прямому слиянию с записью результатов в другую пару файлов. Но в отличие от прямого слияния длины сливаемых серий здесь не фиксированы, а определяются с помощью условия, рассматриваемого выше. Пока выполняется условие (1) считается, что записи входят в одну серию, если (2), то начинается новая серия. Такие проходы выполняются до тех пор , пока один файл из какой-либо пары не станет пустым.
Замечание: при использовании для сортировки ЕС алгоритмов подобного прямому слиянию возможна потеря данных. Это объясняется тем, что для ПС количество серий в паре файлов м. отличаться не оболе чем на 1.
Процесс слияния завершается после выбора всех пар, а последовательная серия, которая осталась без пары – копируется. Для ЕС количество серий в копируемых файлах моет отличаться более чем на 1. если при этом завершить проход копированием только одной непарной серии, то данные, оставшиеся в других непарных сериях м. б. потеряны.
Чтобы избежать возможной потери данных каждый проход должен завершаться копированием всех непарных серий в поочередно формируемые файлы:
Вычислительная сложность в сортировке ЕС в худшем случае оценивается аналогично прямому слиянию, но дает заметно лучший результат.
Пример.
47,55|12,42,94|18|06,40|32,51,86
T1: 47,55|18,32,51,86
T2: 12,42,94|06,40
G1: 12,42,47,55,94
G2: 6,18,32,40,51,86
T1:6,12,18,32,40,42,47,51,55,86,94
T2: -