Алгоритмические языки программирования. Лекция 1

1.

Алгоритмические языки
программирования.
Лектор:
доцент КФТТ И.В.Климов

2.

2

3.

Максимальный
размер
превышать 64 Кбайт.
модуля
не
может
Однако количество модулей не ограничено, что дает
возможность
разрабатывать
весьма
крупные
программы.
Если программа запускается из интегрированной
среды Турбо Паскаля, то часть памяти занимает
сама среда(около 230 Кбайт).
Эту память можно использовать, если компилировать
программу с помощью автономного компилятора
(ТРС.ЕХЕ).
А если и этого окажется недостаточно?
Нужно использовать
механизм оверлеев!
3

4.

4

5.

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

6.

6

7.

Программа
Модули
Главная часть
main
(LA>LB) (размер LA байт)
A
(размер LM байт)
B
(размер LB байт)
Схема работы оверлейной программы
7

8.

ОЗУ
ДИСК
LM
LA
Prog.exe
LB
8
Неоверлейная (обычная) программа

9.

ОЗУ
ДИСК
LM
LA
Оверлейный
буфер
Prog.exe
(main)
A.ovr
B.ovr
Оверлейная программа.
9

10.

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

11.

11

12.

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

13.

Главный недостаток оверлейной структуры:
На каждую загрузку
оверлейного модуля с диска в
оверлейный буфер требуется
дополнительное время
• поэтому оверлейная программа будет в общем
случае исполняться с меньшей скоростью.
13

14.

Оверлеи полезны только в программах DOS,
работающих в реальном режиме.
Работа оверлейных программ обеспечивается с
помощью процедур, и функций модуля OVERLAY.
В программах для Windows и программах,
работающих
в
защищенном
режиме,
необходимость в использовании оверлеев отпадает
для программ Windows памятью управляет сама
оболочка Windows, а для программ, работающих в
защищенном режиме, — администратор выполнения
(RTM.EXE)
эти средства включают
обслуживания оверлеев
в
себя
полный
механизм
14

15.

Новые термины и понятия:
• область
памяти,
размещенная
между сегментом стека и «кучей», в
которую загружаются оверлейные
модули.
• подпрограмма
обеспечивающая
загрузку оверлеев в память
и
выгрузку их на диск
Оверлейная программа.
15

16.

По умолчанию для оверлейного
буфера устанавливается
минимально возможный размер.
• Во время выполнения программы размер
буфера может быть легко увеличен путем
выделения дополнительной памяти из
динамически распределяемой области.
Размер оверлейного буфера
16

17.

Турбо Паскаль управляет оверлеями на уровне модулей
При компиляции программы, имеющей
оверлейную структуру,
наряду с выполняемым файлом (.ЕХЕ),
создается оверлейный файл, с именем,
совпадающим с именем главной
программы, и расширением (.OVR).
• Файл с расширением .ЕХЕ содержит статические (неоверлейные)
части программы.
• Файл с расширением .OVR содержит все оверлейные модули,
которые при выполнении программы будут подгружаться в память
и выгружаться из нее на диск.
17

18.

18

19.

19

20.

Администратор оверлеев Турбо Паскаля
(подсистема
управления
оверлеями)
реализован с помощью стандартного
модуля OVERLAY.
Администратор
оверлеев
использует
усовершенствованные методы управления
буферами.
что обеспечивает оптимальное выполнение
программы в имеющейся области памяти
20

21.

Подсистема управления оверлеями сохраняет в
оверлейном буфере столько оверлеев, сколько
возможно.
• Это позволяет уменьшить количество считываний оверлеев с диска.
• После загрузки оверлея вызов одной из его подпрограмм выполняется так
же быстро, как и обращение к программе, имеющей неоверлейную
структуру.
Когда возникает необходимость выгрузить один
оверлей, чтобы освободить место для другого,
администратор оверлеев сначала пытается
выгрузить те оверлеи, которые не являются
активными.
• Т.е. те, которые в данный момент времени не содержат активных
подпрограмм.
Управление оверлейным буфером
21

22.

Одной из очень важных возможностей
администратора
оверлеев
является
возможность
загружать
оверлейный
файл в дополнительную память при
наличии достаточного пространства.
Для
этой
цели
в
Турбо
Паскале
поддерживается
средство
расширения
памяти EMS (Lotus/Intel/Microsoft Expanded
Memory Specification)
Если оверлейный файл размещен в
памяти EMS, все последующие загрузки
оверлеев осуществляются путем быстрой
передачи информации из одной области
памяти в другую.
22

23.

23

24.

24

25.

В начале всех оверлейных модулей должна
быть размещена директива компилятора
{$О+}.
Процедуры и функции, прямо или косвенно
вызывающие оверлейные подпрограммы,
должны
быть
откомпилированы
с
ключом {$F+}.
В основной программе либо в первых
строках, либо перед каждой процедурой,
вызывающей оверлей, необходимо указать
директиву {$F+}.
25

26.

26

27.

Директива компилятора
{$О Имя_Модуля}
используется в программе для указания того,
какой из модулей будет оверлейным.
• Эта директива должна размещаться за оператором
USES программы, в котором перед именами всех других
оверлейных
модулей
должно
указываться
имя
стандартного модуля Overlay.
Оформление оверлеев
27

28.

Пример:
PROGRAM Overlay;
{Все программы должны иметь дальний тип вызова}
{$F+}
{Порядок подключения оверлейных модулей должен быть таким}
USES Crt, Overlay, Init_Ovr, Ovr_1,0vr_2;
{Указание компилятору, какие модули являются оверлейными}
{$О Ovr_1}
{$0 Ovr_2}
Оформление оверлеев
28

29.

Если попытаться использовать в качестве
оверлейного модуль, при компиляции которого не
была указана директива {$О+}, компилятор
выдаст сообщение об ошибке.
Из всех стандартных модулей оверлейным может
быть только модуль Dos.
Другие
стандартные
модули
не
могут
использоваться в качестве оверлейных.
Не могут быть оверлейными модули, которые
содержат обработку прерываний
Программы, содержащие оверлейные модули,
должны компилироваться на диск
Если попытаться выполнить компиляцию таких
программ в память, то компилятор выдаст
сообщение об ошибке.
29

30.

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

31.

31

32.

1
2
3
• Выделить главную часть программы и разбить оставшуюся
часть на несколько модулей.
• Продумать
состав
модулей
таким
образом,
чтобы
минимизировать количество их перезагрузок в буфер в
процессе исполнения программы.
• В главной части программы необходимо указать с помощью
директив компилятора
вида {$0 <имя> } те модули,
которые будут оверлейными.
• Учтите, что из всех стандартных библиотечных модулей
только один модуль DOS может быть оверлейным,
остальные модули не могут объявляться оверлейными.
• Необходимо предусмотреть перед первым по логике работы
программы обращением к какому-либо оверлейному
модулю
вызов
процедуры
инициализации
оверлея
OVRINIT.
• Здесь же, если это необходимо, следует установить размер
оверлейного буфера и указать возможность использования
расширенной памяти.
32

33.

4
5
6
• В начале главной программы и каждого оверлейного
модуля необходимо поместить директивы компилятора
{$O+ } и {$F+}.
• Или установить опции OPTIONS/COMPILE /FORCE FAR
CALLS и OPTIONS/COMPILE/OVERLAYS ALLOWED в
состояние ОN
• Откомпилировать
диск.
программу
на
•Программа готова к
работе
33

34.

Процедуры и функции модуля Overlay
Подпрограмма
Описание
OvrClearBuf
Очищает оверлейный буфер
OvrGetBuf
Возвращает текущий размер оверлейного буфера
OvrGetRetry
Возвращает текущий размер области испытаний - последнее
значение, установленное OvrSetRetry; По умолчанию – 0.
OvtInit
Инициализирует подсистему управления оверлеями и открывает
оверлейный файл
OvrInitEMS
Загружает оверлейный файл в память EMS, если это возможно.
OvrSetBuf
Устанавливает размер оверлейного буфера
OvrSetRetry
Задает размер области испытаний в оверлейном буфере
34

35.

Инициализация
оверлеев
Инициализация администратора оверлеев.
Анализ результатов инициализации.
Использование расширенной памяти.

36.

Процедура OvrInit(OvrFileName : STRING);
инициализирует администратор оверлеев и
открывает указанный оверлейный файл (.OVR).
Процедура OvrInit является обязательной для
всех программ, использующих оверлеи, и должна
выполняться перед первым обращением к любой
оверлейной подпрограмме.
• Обычно одного вызова этой процедуры достаточно, если при
этом не производить контроль ошибок инициализации.
Инициализация администратора оверлеев
36

37.

Условие:
• Пусть файл с главной частью программы называется MAIN.РАS;
• В программе используются два оверлейных модуля;
• Разместим их в файлы UNITA.PAS и UNITB.PAS.
Файл
MAIN.РАS
PROGRAM OverlayDemo;
($F+,O+}
Uses Over1ay, UnitA, UnitB;
{$O UnitA}
{$O UnitB}
BEGIN
OvrInit ('MAIN.OVR');
SubA
END.
37

38.

Файл
UNITA.PAS
UNIT UnitA;
{$F+,0+}
INTERFACE
Uses UnitB;
Procedure SubA;
IMPLEMENTATION
PROCEDURE SubA;
const
st = 'Работает модуль'
BEGIN
writeln (st, 'A');
SubB (st)
END;
END.
38

39.

Файл
UNITB.PAS
UNIT UnitB;
{$F+,0+}
INTERFACE
Procedure SubB (s : string);
IMPLEMENTATION
PROCEDURE SubB ;
BEGIN
writeln (s, 'B');
SubB (st)
END;
END.
39

40.

Хотя использование кода инициализации и
допускается в оверлейных модулях,
1. Код инициализации, даже если он выполняется только один раз,
является частью оверлея и будет занимать пространство в
оверлейном буфере при каждой загрузке оверлея.
2. Если
большое
число
оверлейных
модулей
содержит
код
инициализации, каждый из них при загрузке программы придется
считывать в память.
Инициализация администратора оверлеев
40

41.

Рациональный подход:
• весь
код
инициализации
собрать в оверлейный модуль
инициализации,
• модуль
инициализации
вызывается только один раз
при загрузке программы
• больше программа к нему не
обращается.
41

42.

В модуле Overlay объявлена переменная
OvrResult : INTEGER;
в которой хранится код завершения процедур и
функций модуля.
в том числе и код завершения процедуры OvrInit.
Анализ результатов инициализации
42

43.

Возможные значения переменной OvrResult, а также список
соответствующих им констант:
Значение
Константа
Описание
0
OvrOK
Нормальное завершение
-1
OvrError
Ошибка управления оверлеями
-2
OvrNotFound
Файл .OVR не найден
-3
OvrNoMemory
Не хватает памяти для буфера
-4
OvrIOError
Ошибка при обращении к оверлейному файлу
-5
OvrNoEMSDriver
Драйвер EMS не установлен
-6
OvrNoEMSMemory
Размер EMS-памяти недостаточен
Анализ результатов инициализации
43

44.

Для размещения оверлеев в расширенной памяти
(EMS-памяти), предназначена процедура
OvrInitEMS, не имеющая параметров.
Эта процедура проверяет возможность использования в системе
расширенной памяти, и если это возможно, то оверлейный файл
полностью размещается там.
Процедура OvrInitEMS не является обязательной и не заменяет
процедуру OvrInit. При использовании расширенной памяти
необходимо вызывать обе эти процедуры.
Использование расширенной памяти

45.

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

46.

Управление
оверлейным
буфером
Механизм управления буфером.
Управление механизмом испытаний.

47.

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

48.

Для управления оверлейным буфером
применяется функция OvrGetBuf,
а также процедуры OvrSetBuf и
OvrClearBuf.
Использование этих процедур необходимо в
том случае, когда системные средства
модуля по управлению оверлейным буфером
по каким-либо причинам не устраивают
программиста, и возникает необходимость
самостоятельно управлять конфигурацией и
содержимым буфера.
48

49.

Функция OvrGetBuf: Longint;
• Данная
функция
возвращает
размер
установленного оверлейного буфера в байтах
• В этом ее отличие от специальной переменной
OvrHeapSize модуля System, в которой хранится
не текущий, а начальный размер буфера.
49

50.

Процедура OvrSetBuf(Size : Longint);
• Данная процедура устанавливает новый размер буфера
и должна вызываться после процедур OvrInit и
OvrInitEMS.
• Параметр Size определяет размер буфера в байтах.
Этот размер не должен быть меньше первоначально
установленного и не должен превышать размер
доступной памяти.
50

51.

• Доступный
объем
памяти
определяется разницей значений
переменных MaxAvail, содержащей
размер максимального непрерывного
блока
кучи,
и
OvrHeapSize,
содержащей
начальный
размер
буфера.
• Если значение параметра Size
превышает текущий размер буфера,
то недостающий объем памяти
выделяется из кучи, а если меньше,
то
излишек
помечается
как
свободный и возвращается в кучу.
51

52.

После
вызова
процедуры
необходимо
проверить
переменной OvrResult.
OvrSetBuf
значение
Если ее значение равно OvrError, то это
может быть
причинами:
обусловлено
следующими
в куче с помощью процедур New и GetMem уже
были размещены динамические переменные;
значение Size слишком мало для создания буфера;
не была проведена процедура инициализации.
52

53.

Процедура OvrClearBuf;
• Данная
процедура
выполняет
принудительную очистку оверлейного буфера
(т.е. выгружает все расположенные в нем оверлейные
модули).
• Используется в тех случаях, когда необходимо
освободить динамическую память для
размещения в ней каких-либо переменных.
• Для определения адресов начала и конца
буфера можно использовать специальные
переменные OvrHeapOrg и OvrHeapEnd
модуля System.
53

54.

Оверлейный буфер Турбо Паскаля лучше всего представить в
виде кольцевого буфера.
Оверлеи всегда загружаются в начало
буфера. При этом более "старые" оверлеи
смещаются к его концу.
указатель
конца
Когда
буфер
заполняется,
то
выгружается оверлей в конце буфера, если
он в данный момент не используется, и
выделяется место для новых оверлеев.
Этот
режим
администратором
умолчанию.
используется
оверлеев
по
Однако Турбо Паскаль предоставляет
возможность оптимизировать алгоритм
управления оверлеями.
указатель
начала
Модуль_1
Модуль_N
……….
Модуль_2
……..
Механизм управления буфером

55.

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

56.

56

57.

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

58.

58

59.

Для управления механизмом испытаний
предназначены
функция OvrGetRetry и процедура OvrSetRetry.
Функция OvrGetRetry: Longlnt;
возвращает текущий установленный размер области испытаний.
В начале работы программы размер области испытаний
всегда равен нулю.
Процедура OvrSetRetry(Size: Longlnt);
устанавливает размер Size области испытаний.
Параметр Size определяет размер этой области в конце
буфера.
Данная процедура должна вызываться после процедур
OvrInit и OvrInitEMS.
59

60.

60