Стандартные процедуры и функции для работы с файлами
Работа с файлами производится посредством следующих стандартных процедур:
Assign(var F: file; name : string); - связывает имя файловой переменнойFв программе с именем внешнего файла на диске name. Здесь name - выражение строкового типа вида
'диск:\имя_каталога\имя_подкоталога\...\имя_файла'
Если в параметре name имена диска и подкаталога не указаны, то выбирается текущий диск и текущий каталог. Если вместо name указать '' (без пробела), то файл F оказывается связанным со стандартным файлом ввода Input или со стандартным файлом вывода Output (в зависимости от того, как он будет открыт - для чтения или для записи). После выполнения процедуры Assign все действия над переменной F будут эквивалентны действиям над файлом, определяемым спецификацией name. Процедуру Assign необходимо использовать до начала работы с файлом (до его открытия процедурой reset или rewrite);
Reset(var F : file); - открывает файл F для чтения. При этом указатель файла устанавливается на первый элемент файла и Eof(F) = False.
Если файл пустой, то Eof(F) = True;
Rewrite(var F : file); - открывает новый файл F для записи. При этом уничтожается вся информация в F и Eof(F) = True;
Read(var F: file; var x1, x2, ..., xn); - считывает в переменную x1 один элемент файла F (или несколько элементов в переменные x1, x2, ..., xn), начиная чтение с элемента, на который указывает текущий указатель. Если F опущено, то подразумевается стандартный файл Input. Read выполним только в случае, если Eof(F) = false;
Write(var F : file; var x1, x2, ..., xn); -записывает одно (x1) или более (x1, x2, ..., xn) значений переменных в файл F, начиная с той позиции, на которую установлен указатель. Если F опущено, то подразумевается стандартный файл Output. Write выполним только в случае, если Eof(F) = True;
Close(var F : file) - закрывает файл F;
Seek(var F : file; n : longint); - позволяет осуществить прямой доступ к элементам файла F. Здесь n - целая положительная константа, соответствующая порядковому номеру элемента в файле. Процедура Seek не выполняет операцию чтения или записи элемента файла. Она лишь перемещает указатель файла к элементу с номером n. При этом первый элемент файла имеет номер n = 0, второй - n = 1 и т.д.;
Стандартные функции FilePos(var F : file): longint и FileSize(var F : file): longint позволяют определить соответственно текущее положение указателя (номер элемента) и размер (число элементов) файла F.
Лекция №9 Динамические структуры данных.
ДИНАМИЧЕСКАЯ ПАМЯТЬ
Все переменные, объявленные в программе, размещаются в одной непрерывной области оперативной памяти, которая называется сегментом данных. Длина сегмента данных определяется архитектурой микропроцессоров 80x86 и составляет 65536 байт, что может вызвать известные затруднения при обработке больших массивов данных. С другой стороны, объем памяти ПК (обычно не менее 640 Кбайт) достаточен для успешного решения задач с большой размерностью данных. Выходом из положения может служить использование так называемой динамической памяти.
Динамическая память - это оперативная память ПК, предоставляемая программе при ее работе, за вычетом сегмента данных (64 Кбайт), стека (обычно 16 Кбайт) и собственно тела программы. Размер динамической памяти можно варьировать в широких пределах (см. прил.1). По умолчанию этот размер определяется всей доступней памятью ПК и, как правило, составляет не менее 200...300 Кбайт.
Динамическая память - это фактически единственная возможность обработки массивов данных большой размерности. Многие практические задачи трудно или невозможно решить без использования динамической памяти. Такая необходимость возникает, например, при разработке систем автоматизированного проектирования (САПР): размерность математических моделей, используемых в САПР, может значительно отличаться в разных проектах; статическое (т.е. на этапе разработки САПР) распределение памяти в этом случае, как правило, невозможно. Наконец, динамическая память широко используется для временного запоминания данных при работе с графическими и звуковыми средствами ПК.
Динамическое размещение данных означает использование динамической памяти непосредственно при работе программы. В отличие от этого статическое размещение осуществляется компилятором Турбо Паскаля в процессе компиляции программы. При динамическом размещении заранее не известны ни тип, ни количество размещаемых данных, к ним нельзя обращаться по именам, как к статическим переменным.
АДРЕСА И УКАЗАТЕЛИ
Оперативная память ПК представляет собой совокупность элементарных ячеек для хранения информации - байтов, каждый из которых имеет собственный номер. Эти номера называются адресами, они позволяют обращаться к любому байту памяти.
Турбо Паскаль предоставляет в распоряжение программиста гибкое средство управления динамической памятью - так называемые указатели. Указатель - это переменная, которая в качестве своего значения содержит адрес байта памяти.
В ПК адреса задаются совокупностью двух шестнадцатиразрядных слов, которые называются сегментом и смещением. Сегмент - это участок памяти, имеющий длину 65536 байт (64 Кбайт) и начинающийся с физического адреса, кратного 16 (т.е. О, 16, 32, 48 и т.д.). Смещение указывает, сколько байт от начала сегмента необходимо пропустить, чтобы обратиться к нужному адресу.
Адресное пространство ПК составляет 1 Мбайт (речь идет о так называемой стандартной памяти ПК; на современных компьютерах с процессорами 80386 и выше адресное пространство составляет 4 Гбайт, однако в Турбо Паскале нет средств, поддерживающих работу с дополнительной памятью; при использовании среды Borland Pascal with Objects 7.0 такая возможность имеется). Для адресации в пределах 1 Мбайта нужно 20 двоичных разрядов, которые получаются из двух шестнадцатиразрядных слов (сегмента и смещения) следующим образом: содержимое сегмента смещается влево на 4 разряда, освободившиеся правые разряды заполняются нулями, результат складывается с содержимым смещения.
Фрагмент памяти в 16 байт называется параграфом, поэтому можно сказать, что сегмент адресует память с точностью до параграфа, а смещение - с точностью до байта. Каждому сегменту соответствует непрерывная и отдельно адресуемая область памяти. Сегменты могут следовать в памяти один за другим без промежутков или с некоторым интервалом, или, наконец, перекрывать друг друга.
Таким образом, по своей внутренней структуре любой указатель представляет собой совокупность двух слов (данных типа WORD), трактуемых как сегмент и смещение. С помощью указателей можно размещать в динамической памяти любой из известных в Турбо Паскале типов данных. Лишь некоторые из них (BYTE, CHAR, SHORTINT, BOOLEAN) занимают во внутреннем представлении один байт, остальные - несколько смежных. Поэтому на самом деле указатель адресует лишь первый байт данных.
ОБЪЯВЛЕНИЕ УКАЗАТЕЛЕЙ
Как правило, в Турбо Паскале указатель связывается с некоторым типом данных. Такие указатели будем называть типизированными. Для объявления типизированного указателя используется значок ^, который помещается перед соответствующим типом, например:
var
P1 :^Integer;
р2 :^Real;
type
PerconPointer = ^PerconRecord;
PerconRecord = record
Name : String;
Job : String;
Next : PerconPointer
end;
Обратите внимание: при объявлении типа PerconPointer мы сослались на тип PerconRecord, который предварительно в программе объявлен не был. Как уже отмечалось, в Турбо Паскале последовательно проводится в жизнь принцип, в соответствии с которым перед использованием какого-либо идентификатора он должен быть описан. Исключение сделано только для указателей, которые могут ссылаться на еще не объявленный тип данных. Это исключение сделано не случайно. Динамическая память дает возможность реализовать широко используемую в некоторых программах организацию данных в виде списков. Каждый элемент списка имеет в своем составе указатель на соседний элемент, что обеспечивает возможность просмотра и коррекции списка. Если бы в Турбо Паскале не было этого исключения, реализация списков была бы значительно затруднена.
В Турбо Паскале можно объявлять указатель и не связывать его при этом с каким-либо конкретным типом данных. Для этого служит стандартный тип POINTER, например:
var
р: pointer;
Указатели такого рода будем называть нетипизированными. Поскольку нетипизированные указатели не связаны с конкретным типом, с их помощью удобно динамически размещать данные, структура и тип которых меняются в ходе работы программы.
Как уже говорилось, значениями указателей являются адреса переменных в памяти, поэтому следовало бы ожидать, что значение одного указателя можно передавать другому. На самом деле это не совсем так. В Турбо Паскале можно передавать значения только между указателями, связанными с одним и тем же типом данных. Если, например,
var
p1,p2: ^integer;
р3 : ^Rеа1;
рр : pointer;
то присваивание
p1 := р2;
вполне допустимо, в то время как
р1 := р3;
запрещено, поскольку Р1 и Р3 указывают на разные типы данных. Это ограничение, однако, не распространяется на нетипизированные указатели, поэтому мы могли бы записать
pp := p3;
p1 := pp;
и тем самым достичь нужного результата.
Читатель вправе задать вопрос, стоило ли вводить ограничения и тут же давать средства для их обхода. Все дело в том, что любое ограничение, с одной стороны, вводится для повышения надежности программ, а с другой - уменьшает мощность языка, делает его менее пригодным для каких-то применений. В Турбо Паскале немногочисленные исключения в отношении типов данных придают языку необходимую гибкость, но их использование требует от программиста дополнительных усилий и таким образом свидетельствует о вполне осознанном действии.
ВЫДЕЛЕНИЕ И ОСВОБОЖДЕНИЕ ДИНАМИЧЕСКОЙ ПАМЯТИ
Вся динамическая память в Турбо Паскале рассматривается как сплошной массив байтов, который называется кучей. Физически куча располагается в старших адресах сразу за областью памяти, которую занимает тело программы.
Начало кучи хранится в стандартной переменной HEAPORG, конец - в временной HEAPEND. Текущую границу незанятой динамической памяти указывает указатель HEAPPTR.
Память под любую динамически размещаемую переменную выделяется процедурой NEW. Параметром обращения к этой процедуре является типизированный указатель. В результате обращения указатель приобретает значение, соответствующее динамическому адресу, начиная с которого можно разместить данные, например:
var
i, j :^Integer;
r : ^Real;
begin
New(i) ;
.......
end.
После выполнения этого фрагмента указатель / приобретет значение, которое перед этим имел указатель кучи HEAPPTR, а сам HEAPPTR увеличит свое значение на 2, так как длина внутреннего представления типа INTEGER, с которым связан указатель I, составляет 2 байта (на самом деле это не совсем так: память под любую переменную выделяется порциями, кратными 8 байтам - см. п.6.7). Оператор
new(r);
вызовет еще раз смещение указателя HEAPPTR, но теперь уже на 6 байт, потому что такова длина внутреннего представления типа REAL. Аналогичным образом выделяется память и для переменной любого другого типа.
После того как указатель приобрел некоторое значение, т.е. стал указывать на конкретный физический байт памяти, по этому адресу можно разместить любое значение соответствующего типа. Для этого сразу за указателем без каких-либо пробелов ставится значок ^, например:
i^ := 2; {B область памяти i помещено значение 2}
r^ := 2*pi; {В область памяти r помещено значение 6.28}
Таким образом, значение, на которое указывает указатель, т.е. собственно данные, размещенные в куче, обозначаются значком ^, который ставится сразу за указателем. Если за указателем нет значка ^, то имеется в виду адрес, по которому размещены данные. Имеет смысл еще раз задуматься над только что сказанным: значением любого указателя является адрес, а чтобы указать, что речь идет не об адресе, а о тех данных, которые размещены по этому адресу, за указателем ставится ^.
Динамически размещенные данные можно использовать в любом месте программы, где это допустимо для констант и переменных соответствующего типа, например:
r^ := sqr(r^) + i^ - 17;
Разумеется, совершенно недопустим оператор
r := sqr(r^) + i^ - 17;
так как указателю R нельзя присвоить значение вещественного выражения. Точно так же недопустим оператор
r^ := sqr(r) ;
поскольку значением указателя R является адрес, и его (в отличие от того значения, которое размещено по этому адресу) нельзя возводить в квадрат. Ошибочным будет и такое присваивание:
r^:=i;
так как вещественным данным, на которые указывает R, нельзя присвоить значение указателя (адрес).
Динамическую память можно не только забирать из кучи, но и возвращать обратно. Для этого используется процедура DISPOSE. Например, операторы
dispose (r) ;
dispose (i) ;
вернут в кучу 8 байт, которые ранее были выделены указателям I и R (см. выше).
Отметим, что процедура DISPOSE(PTR) не изменяет значения указателя PTR, а лишь возвращает в кучу память, ранее связанную с этим указателем. Однако повторное применение процедуры к свободному указателю приведет к возникновению ошибки периода исполнения. Освободившийся указатель программист может пометить зарезервированным словом NIL. Помечен ли какой-либо указатель или нет, можно проверить следующим образом:
const
p:^Real = NIL;
begin
.......
if p = NIL then
new(p);
.......
dispose(p);
p := NIL;
.......
end.
Никакие другие операции сравнения над указателями не разрешены.
Приведенный выше фрагмент иллюстрирует предпочтительный способ объявления указателя в виде типизированной константы (см. гл. 7) с одновременным присвоением ему значения NIL. Следует учесть, что начальное значение указателя (при его объявлении в разделе переменных) может быть произвольным. Использование указателей, которым не присвоено значение процедурой NEW или другим способом, не контролируется системой и может привести к непредсказуемым результатам.
Чередование обращений к процедурам NEW и DISPOSE обычно приводит к «ячеистой» структуре памяти. Дело в том, что все операции с кучей выполняются под управлением особой подпрограммы, которая называется администратором кучи. Она автоматически пристыковывается к Вашей программе компоновщиком Турбо Паскаля и ведет учет всех свободных фрагментов в куче. При очередном обращении к процедуре NEW эта подпрограмма отыскивает наименьший свободный фрагмент, в котором еще может разместиться требуемая переменная. Адрес начала найденного фрагмента возвращается в указателе, а сам фрагмент или его часть нужной длины помечается как занятая часть кучи.
Другая возможность состоит в освобождении целого фрагмента кучи. С этой целью перед началом выделения динамической памяти текущее значение указателя HEAPPTR запоминается в переменной-указателе с помощью процедуры MARK. Теперь можно в любой момент освободить фрагмент кучи, начиная от того адреса, который запомнила процедура MARK, и до конца динамической памяти. Для этого используется процедура RELEASE. Например:
var
p,p1,p2,р3,р4,р5 : ^Integer;
begin
new(p1);
new(p2) ;
mark(p); .
new(p3);
new(p4);
new(p5)
......
release(p);
end.
В этом примере процедурой MARK(P) в указатель Р было помещено текущее значение HEAPPTR, однако память под переменную не резервировалась. Обращение RELEASE(P) освободило динамическую память от помеченного места до конца кучи. Следует учесть, что вызов RELEASE уничтожает список свободных фрагментов в куче, созданных до этого процедурой DISPOSE, поэтому совместное использование обоих механизмов освобождения памяти в рамках одной программы не рекомендуется.
Как уже отмечалось, параметром процедуры NEW может быть только типизированный указатель. Для работы с нетипизированными указателями используются процедуры:
GETMEM (P, SIZE) - резервирование памяти;
FREEMEM(P, SIZE) - освобождение памяти.
Здесь Р - нетипизированный указатель;
SIZE - размер в байтах требуемой или освобождаемой части кучи.
За одно обращение к куче процедурой GETMEM можно зарезервировать до 65521 байта динамической памяти.
Использование процедур GETMEM-FREEMEM, как и вообще вся работа с динамической памятью, требует особой осторожности и тщательного соблюдения простого правила: освобождать нужно ровно столько памяти, сколько ее было зарезервировано, и именно с того адреса, с которого она была зарезервирована.
Нетрудно обнаружить, что наличие нетипизированных указателей в Турбо Паскале I в стандартном Паскале их нет) открывает широкие возможности неявного преобразования типов. К сожалению, трудно обнаруживаемые ошибки в программе, связанные с некорректно используемыми обращениями к процедурам NEW и DISPOSE, также могут привести к нежелательному преобразованию типов. В самом деле, пусть имеется программа:
var
i,j :^Integer;
r :^Real;
begin
new(i); {i := HeapOrg; HeapPtr:= HeapOrg + 2}
j := i; {j := HeapOrg}
j^ := 2;
dispose(i); {HeapPtr := HeapOrg}
new(r); {r := HeapOrg; HeapPtr:= HeapOrg + 6}
r^ := pi;
WriteLn(j^)
end.
Что будет выведено на экран дисплея? Чтобы ответить на этот вопрос, проследим за значениями указателя HEAPPTR. Перед исполнением программы этот указатель имел значение адреса начала кучи HEAPORG, которое и было передано указателю I, азатем и J. После выполнения DISPOSE(I) указатель кучи вновь приобрел значение HEAPORG, этот адрес передан указателю R в процедуре NEW(R). После того как по адресу R разместилось вещественное число pi=3.14159, первые 2 байта кучи оказались заняты под часть внутреннего представления этого числа. В то же время J все еще сохраняет адрес HEAPORG, поэтому оператор WRITELN(J^) будет рассматривать 2 байта числа pi как внутреннее представление целого числа (ведь J - это указатель на тип INTEGER) и выведет 8578.
ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ
Посмотрим, как можно использовать динамическую память для размещения крупных массивов данных. Пусть, например, требуется обеспечить доступ к элементам прямоугольной матрицы 100x200 типа EXTENDED. Для размещения такого массива требуется память 200000 байт (100*200*10).
Казалось бы, эту проблему можно решить следующим образом:
var
i,j : Integer;
PtrArr : array [1..100, 1...200] of ^Real;
begin
for i := 1 to 100 do
for j := 1 to 200 do
new(PtrArr[i,j]);
.......
end.
Теперь к любому элементу вновь созданного динамического массива можно обратиться по адресу, например:
PtrArr[1,1]^ := 0;
if PtrArr[i,j*2]^ > 1 then ......
Вспомним, однако, что длина внутреннего представления указателя составляет 4 байта, поэтому для размещения массива PTRARR потребуется 100*200*4 = 80000 байт, что превышает размер сегмента данных (65536 байт), доступный, как уже отмечалось, программе для статического размещения данных.
Выходом из положения могла бы послужить адресная арифметика, т.е. арифметика над указателями, потому что в этом случае можно было бы отказаться от создания массива указателей PTRARR. и вычислять адрес любого элемента прямоугольной матрицы непосредственно перед обращением к нему. Однако в Турбо Паскале над указателями не определены никакие операции, кроме операций присвоения и отношения.
Тем не менее, решить указанную задачу все-таки можно. Как мы уже знаем, любой указатель состоит из двух слов типа WORD, в которых хранятся сегмент и смещение. В Турбо Паскале определены две встроенные функции типа WORD, позволяющие получить содержимое этих слов:
SEG(X) - возвращает сегментную часть адреса;
OFS(X) - возвращает смещение.
Аргументом X при обращении к этим функциям может служить любая переменная, з том числе и та, на которую указывает указатель. Например, если имеем
var
р : ^Real;
begin
......
new(p);
р^ := 3.14;
.......
end.
то функция SEG(P) вернет сегментную часть адреса, по которому располагается 4-байтный указатель Р, в то время как SEG(P^) - сегмент 6-байтного участка кучи, в котором хранится число 3.14 .
С другой стороны, с помощью встроенной функции
PTR(SEG,OFS: WORD): POINTER
можно создать значение указателя, совместимое с указателями любого типа. Таким образом возможна такая последовательность действий. Вначале процедурой GETMEM из кучи забираются несколько фрагментов подходящей длины (напомню, что за одно обращение к процедуре можно зарезервировать не более 65521 байт динамической памяти). Для рассматриваемого примера удобно резервировать фрагменты такой длины, чтобы в них могли, например, разместиться строки прямоугольной матрицы, т.е. 100 * 10 = 2000 байт. Начало каждого фрагмента, т.е. фактически начало размещения в памяти каждой строки, запоминается в массиве PTRSTR, состоящем из 100 указателей, теперь для доступа к любому элементу строки нужно вычислить смещение этого элемента от начала строки и сформировать соответствующий указатель:
var
i,j:Integer;
PtrStr : array [1..100] of pointer;
const
SizeOfReal = 6;
begin
for i := 1 to 100 do
GetMem (PtrStr [i] , SizeOfReal*200) ;
.......
{Обращение к элементу матрицы [i,j]}
pr := ptr(seg(PtrStr[i]^),
ofs(PtrStr[i]^)+(j-1)*SizeOfReal);
if рr^ > 1 then
.......
end.
Поскольку оператор вычисления адреса PR := PTR... будет, судя по всему, использоваться в программе неоднократно, полезно ввести вспомогательную функцию GETR, возвращающую значение элемента матрицы, и процедуру PUTR, устанавливающую новое значение элемента. Каждая из них, в свою очередь, обращается к функции ADDRR для вычисления адреса. В примере приводится программа, создающая в памяти матрицу из NxM случайных чисел и вычисляющая их среднее значение.
const
SizeOfReal = 6; {Длина переменной типа REAL}
N = 100; {Количество столбцов}
М = 200; {Количество строк}
var
i,j : Integer;
PtrStr: array [1..N] of pointer;.
s : Real ;
type
RealPoint =^Real;
{-------------------}
Function AddrR(i,j: word): RealPoint;
{По сегменту i и смещению j выдает адрес вещественной переменной}
begin
AddrR := ptr(seg (PtrStr [i]^),
ofs{ PtrStr [i]^) + (j -1) * SizeOfReal)
end {AddrR} ;
{-------------------}
Function GetR(i,j: Integer): Real;
{Выдает значение вещественной переменной по сегменту i и смещению j ее адреса}
begin
GetR := AddrR(i,j)^
end {GetR};
{-------------------}
Procepure PutR(i,j : Integer; x: Real);
{Помещает в переменную, адрес которой имеет сегмент i и смещение j, вещественное значение x}
begin
AddrR ( i , j )^ : = x
end {PutR};
{-------------------}
begin {Main}
for i :=1 to N do
begin
GetMem (PtrStr [i] , M*SizeOfReal) ;
for j := 1 to M do PutR(i, j, Random)
end;
S := 0;
for i := 1 to N do
for j := 1 to M do
s := s +GetR(i,j);
WriteLn(s/(N * М) :12:10)
end {Main} .
В рассмотренном примере предполагается, что каждая строка размещается в куче, начиная с границы параграфа, и смещение для каждого указателя PTRSTR равно нулю. В действительности при последовательных обращениях к процедуре GETMEM начало очередного фрагмента следует сразу за концом предыдущего и может не попасть на границу сегмента. В результате, при размещении фрагментов максимальной длины (65521 байт) может возникнуть переполнение при вычислении смещения последнего байта.
ИСПОЛЬЗОВАНИЕ УКАЗАТЕЛЕЙ ДЛЯ ОРГАНИЗАЦИИ СВЯЗАННЫХ СПИСКОВ
Чаще всего указатели используются для ссылки на записи, тем самым достигается значительная экономия памяти. Если же сама запись содержит в себе поле-указатель, указывающий на следующую за ней запись, то это позволяет образовать связанные списки — структуру, в которой отдельные записи последовательно связаны друг с другом. В приведенном ниже примере используются записи, в которых наряду с данными об объекте имеется указатель на следующую запись, благодаря чему получается связанный список.
Одно из полей каждого объекта связанного списка имеет тип указатель и указывает на очередной объект в списке. Указатель на первый объект содержится в переменной First, а последний объект имеет указатель на Nil.
ПРОЦЕДУРЫ И ФУНКЦИИ ДЛЯ РАБОТЫ С ДИНАМИЧЕСКОЙ ПАМЯТЬЮ
Ниже приводится описание как уже рассмотренных процедур и функций, так и некоторых других, которые могут оказаться полезными при обращении к динамической памяти.
Функция ADDR. Возвращает результат типа POINTER, в котором содержится адрес аргумента. Обращение:
ADDR ( X )
Здесь Х- любой объект программы (имя любой переменной, процедуры, функции). Возвращаемый адрес совместим с указателем любого типа. Отметим, что аналогичный результат возвращает операция @ .
Функция CSEG. Возвращает значение, хранящееся в регистре CS микропроцессора в начале работы программы в регистре CS содержится сегмент начала кода программы). Обращение:
CSEG
Результат возвращается в слове типа WORD.
Процедура DISPOSE. Возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за типизированным указателем. Обращение:
DISPOSE(TP)
Здесь ТР - типизированный указатель. При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения. При освобождении динамических объектов можно указывать вторым параметром обращения к DISPOSE имя деструктора (подробнее см. гл.10).
Функция DSEG. Возвращает значение, хранящееся в регистре DS микропроцессора (в начале работы программы в регистре DS содержится сегмент начала данных программы). Обращение:
DSEG
Результат возвращается в слове типа WORD.
Процедура FREEMEM. Возвращает в кучу фрагмент динамической памяти, который ранее был зарезервирован за нетипизированным указателем. Обращение:
FREEMEM ( Р, SIZE )
Здесь Р - нетипизированный указатель;
SIZE - длина в байтах освобождаемого фрагмента.
При повторном использовании процедуры применительно к уже освобожденному фрагменту возникает ошибка периода исполнения.
Процедура GETMEM. Резервирует за нетипизированным указателем фрагмент динамической памяти требуемого размера. Обращение:
GETMEM ( Р, SIZE )
За одно обращение к процедуре можно зарезервировать не более 65521 байтов динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
Процедура MARK. Запоминает текущее значение указателя кучи HEAPPTR. Обращение:
MARK ( PTR )
Здесь PTR - указатель любого типа, в котором будет возвращено текущее значение HEAPPTR. Используется совместно с процедурой RELEASE для освобождения части кучи.
Функция MAXAVAIL. Возвращает размер в байтах наибольшего непрерывного участка кучи. Обращение:
MAXAVAIL
Результат имеет тип LONGINT. За один вызов процедуры NEW или GETMEM нельзя зарезервировать памяти больше, чем значение, возвращаемое этой функцией.
Функция MEMAVAIL. Возвращает размер в байтах общего свободного пространства кучи. Обращение:
MEMAVAIL
Результат имеет тип LONGINT.
Процедура NEW. Резервирует фрагмент кучи для размещения переменной. Обращение:
NEW ( ТР )
Здесь ТР - типизированный указатель.
За одно обращение к процедуре можно зарезервировать не более 65521 байта динамической памяти. Если нет свободной памяти требуемого размера, возникает ошибка периода исполнения. Если память не фрагментирована, последовательные обращения к процедуре будут резервировать последовательные участки памяти, так что начало следующего будет располагаться сразу за концом предыдущего.
Процедура NEW может вызываться как функция. В этом случае параметром обращения к ней является тип переменной, размещаемой в куче, а функция NEW возвращает значение типа указатель. Например:
type
PInt =^Integer;
var
p: Pint;
begin
p := New(PInt);
......
end.
При размещении в динамической памяти объекта разрешается в качестве второго параметра обращения к NEW указывать имя конструктора (см. гл.10).
Функция OFS. Возвращает значение типа WORD, содержащее смещение адреса указанного объекта. Вызов:
OFS ( X )
Здесь Х- выражение любого типа или имя процедуры.
Функция PTR. Возвращает значение типа POINTER по заданному сегменту SEG и смещению OFS. Вызов:
PTR ( SEG, OFS )
Здесь SEG - выражение типа WORD, содержащее сегмент;
OFS - выражение типа WORD, содержащее смещение.
Значение, возвращаемое функцией, совместимо с указателем любого типа.
Процедура RELEASE. Освобождает участок кучи. Обращение:
RELEASE ( PTR )
Здесь PTR - указатель любого типа, в котором предварительно было сохранено процедурой MARK значение указателя кучи. Освобождается участок кучи от адреса, хранящегося в PTR, до конца кучи. Одновременно уничтожается список всех свободных фрагментов, которые, возможно, были созданы процедурами DISPOSE или FREEMEM.
Функция SEG. Возвращает значение типа WORD, содержащее сегмент адреса указанного объекта. Вызов:
SEG ( X )
Здесь X - выражение любого типа или имя процедуры.
Функция SIZEOF. Возвращает длину в байтах внутреннего представления указанного объекта. Вызов:
SIZEOF ( X )
Здесь X - имя переменной, функции или типа. Например, везде в программе из примера вместо константы SIZEOFREAL можно было бы использовать обращение SIZEOF(REAL).
Лекция №10 Способы конструирования программ. Модульные программы.
Способы конструирования программ.
Каскадная модель.
Основной характеристикой каскадной модели является разбиение всей разработки на этапы, причем переход с одного этапа на следующий происходит только после того, как будет полностью завершена работа на текущем (рис. 1). Каждый этап завершается выпуском полного комплекта документации, достаточной для того, чтобы разработка могла быть продолжена другой командой разработчиков.
Положительные стороны применения каскадного подхода заключаются в следующем:
на каждом этапе формируется законченный набор проектной документации, отвечающий критериям полноты и согласованности;
выполняемые в логичной последовательности этапы работ позволяют планировать сроки завершения всех работ и соответствующие затраты.
Каскадный подход хорошо зарекомендовал себя при построении ПС, для которых в самом начале разработки можно достаточно точно и полно сформулировать все требования, с тем чтобы предоставить разработчикам свободу реализовать их как можно лучше с технической точки зрения. В эту категорию попадают сложные расчетные системы, системы реального времени и другие подобные задачи. Однако, в процессе использования этого подхода обнаружился ряд его недостатков, вызванных прежде всего тем, что реальный процесс создания ПО никогда полностью не укладывался в такую жесткую схему. В процессе создания ПО постоянно возникала потребность в возврате к предыдущим этапам и уточнении или пересмотре ранее принятых решений. В результате реальный процесс создания ПО принимал следующий вид (рис. 2.):
Рис. 1. - Каскадная схема
Рисунок 2. - Реальный процесс разработки
Основным недостатком каскадного подхода является существенное запаздывание с получением результатов. Согласование результатов с пользователями производится только в точках, планируемых после завершения каждого этапа работ, требования к ПС «заморожены» в виде технического задания на все время ее создания. Таким образом, пользователи могут внести свои замечания только после того, как работа над системой будет полностью завершена. В случае неточного изложения требований или их изменения в течение длительного периода создания ПО, пользователи получают систему, не удовлетворяющую их потребностям. Модели (как функциональные, так и информационные) автоматизируемого объекта могут устареть одновременно с их утверждением.
Спиральная модель.
Для преодоления проблем, которые возникали при каскадном подходе была предложена спиральная модель ЖЦ (рис. 3.), делающая упор на начальные этапы ЖЦ: анализ и проектирование. На этих этапах реализуемость технических решений проверяется путем создания прототипов. Каждый виток спирали соответствует созданию фрагмента или версии ПО, на нем уточняются цели и характеристики проекта, определяется его качество и планируются работы следующего витка спирали. Таким образом, углубляются и последовательно конкретизируются детали проекта, и в результате выбирается обоснованный вариант, который доводится до реализации.
Разработка итерациями отражает объективно существующий спиральный цикл создания системы. Неполное завершение работ на каждом этапе позволяет переходить на следующий этап, не дожидаясь полного завершения работы на текущем. При итеративном способе разработки недостающую работу можно будет выполнить на следующей итерации. Главная же задача - как можно быстрее показать пользователям системы работоспособный продукт, тем самым, активизируя процесс уточнения и дополнения требований.
Основная проблема спирального цикла - определение момента перехода на следующий этап. Для ее решения необходимо ввести временные ограничения на каждый из этапов жизненного цикла. Переход осуществляется в соответствии с планом, даже если не вся запланированная работа закончена. План составляется на основе статистических данных, полученных в предыдущих проектах, и личного опыта разработчиков.
Основным нормативным документом, регламентирующим ЖЦ ПО, является международный стандарт ISO/IEC 12207 (ISO - International Organization of Standardization - Международная организация по стандартизации, IEC - International Electrotechnical Commission - Международная комиссия по электротехнике). Он определяет структуру ЖЦ, содержащую процессы, действия и задачи, которые должны быть выполнены во время создания ПО.
Рисунок 3. - Спиральная модель ЖЦ
Структура ЖЦ ПО по стандарту ISO/IEC 12207 базируется на трех группах процессов:
основные процессы ЖЦ ПО (приобретение, поставка, разработка, эксплуатация, сопровождение);
вспомогательные процессы, обеспечивающие выполнение основных процессов (документирование, управление конфигурацией, обеспечение качества, верификация, аттестация, оценка, аудит, решение проблем);
организационные процессы (управление проектами, создание инфраструктуры проекта, определение, оценка и улучшение самого ЖЦ, обучение).
Модульное программирование.
Приступая к разработке каждой программы ПС, следует иметь в виду, что она, как правило, является большой системой, поэтому мы должны принять меры для ее упрощения. Для этого такую программу разрабатывают по частям, которые называются программными модулями. А сам такой метод разработки программ называют модульным программированием. Программный модуль это любой фрагмент описания процесса, оформляемый как самостоятельный программный продукт, пригодный для использования в описаниях процесса. Это означает, что каждый программный модуль программируется, компилируется и отлаживается отдельно от других модулей программы, и тем самым, физически разделен с другими модулями программы. Более того, каждый разработанный программный модуль может включаться в состав разных программ, если выполнены условия его использования, декларированные в документации по этому модулю. Таким образом, программный модуль может рассматриваться и как средство борьбы со сложностью программ, и как средство борьбы с дублированием в программировании (т.е. как средство накопления и многократного использования программистских знаний).
Модульное программирование является воплощением в процессе разработки программ обоих общих методов борьбы со сложностью и обеспечение независимости компонент системы, и использование иерархических структур. Для воплощения первого метода формулируются определенные требования, которым должен удовлетворять программный модуль, т.е. выявляются основные характеристики «хорошего» программного модуля. Для воплощения второго метода используют древовидные модульные структуры программ (включая деревья со сросшимися ветвями).
Основные характеристики программного модуля.
Не всякий программный модуль способствует упрощению программы. Выделить хороший с этой точки зрения модуль является серьезной творческой задачей. Для оценки приемлемости выделенного модуля используются некоторые критерии. Так, Хольт предложил следующие два общих таких критерия:
хороший модуль снаружи проще, чем внутри;
хороший модуль проще использовать, чем построить.
Майерс предлагает для оценки приемлемости программного модуля использовать более конструктивные его характеристики:
размер модуля,
прочность модуля,
сцепление с другими модулями,
рутинность модуля (независимость от предыстории обращений к нему).
Размер модуля измеряется числом содержащихся в нем операторов или строк. Модуль не должен быть слишком маленьким или слишком большим. Маленькие модули приводят к громоздкой модульной структуре программы и могут не окупать накладных расходов, связанных с их оформлением. Большие модули неудобны для изучения и изменений, они могут существенно увеличить суммарное время повторных трансляций программы при отладке программы. Обычно рекомендуются программные модули размером от нескольких десятков до нескольких сотен операторов.
Прочность модуля это мера его внутренних связей. Чем выше прочность модуля, тем больше связей он может спрятать от внешней
по отношению к нему части программы и, следовательно, тем больший вклад в упрощение программы он может внести. Для оценки степени прочности модуля Майерс предлагает упорядоченный по степени прочности набор из семи классов модулей. Самой слабой степенью прочности обладает модуль, прочный по совпадению. Это такой модуль, между элементами которого нет осмысленных связей. Такой модуль может быть выделен, например, при обнаружении в разных местах программы повторения одной и той же последовательности операторов, которая и оформляется в отдельный модуль. Необходимость изменения этой последовательности в одном из контекстов может привести к изменению этого модуля, что может сделать его использование в других контекстах ошибочным. Такой класс программных модулей не рекомендуется для использования. Вообще говоря, предложенная Майерсом упорядоченность по степени прочности классов модулей не бесспорна. Однако, это не очень существенно, так как только два высших по прочности класса модулей рекомендуются для использования. Эти классы мы и рассмотрим подробнее.
Функционально прочный модуль это модуль, выполняющий (реализующий) одну какую-либо определенную функцию. При реализации этой функции такой модуль может использовать и другие модули. Такой класс программных модулей рекомендуется для использования.
Информационно прочный модуль это модуль, выполняющий (реализующий) несколько операций (функций) над одной и той же структурой данных (информационным объектом), которая считается неизвестной вне этого модуля. Для каждой из этих операций в таком модуле имеется свой вход со своей формой обращения к нему. Такой класс следует рассматривать как класс программных модулей с высшей степенью прочности. Информационно прочный модуль может реализовывать, например, абстрактный тип данных.
В модульных языках программирования как минимум имеются средства для задания функционально прочных модулей (например, модуль типа FUNCTION в языке ФОРТРАН). Средства же для задания информационно прочных модулей в ранних языках программирования отсутствовали. Эти средства появились только в более поздних языках. Так в языке программирования Ада средством задания информационно прочного модуля является пакет.
Сцепление модуля это мера его зависимости по данным от других модулей. Характеризуется способом передачи данных. Чем слабее сцепление модуля с другими модулями, тем сильнее его независимость от других модулей. Для оценки степени сцепления Майерс предлагает упорядоченный набор из шести видов сцепления модулей. Худшим видом сцепления модулей является сцепление по содержимому. Таким является сцепление двух модулей, когда один из них имеет прямые ссылки на содержимое другого модуля (например, на константу, содержащуюся в другом модуле). Такое сцепление модулей недопустимо. Не рекомендуется использовать также сцепление по общей области это такое сцепление модулей, когда несколько модулей используют одну и ту же область памяти. Такой вид сцепления модулей реализуется, например, при программировании на языке ФОРТРАН с использованием блоков COMMON. Единственным видом сцепления модулей, который рекомендуется для использования современной технологией программирования, является параметрическое сцепление (сцепление по данным по Майерсу это случай, когда данные передаются модулю либо при обращении к нему как значения его параметров, либо как результат его обращения к другому модулю для вычисления некоторой функции. Такой вид сцепления модулей реализуется на языках программирования при использовании обращений к процедурам (функциям).
Рутинность модуля это его независимость от предыстории обращений к нему. Модуль будем называть рутинным, если результат (эффект) обращения к нему зависит только от значений его параметров (и не зависит от предыстории обращений к нему). Модуль будем называть зависящим от предыстории, если результат (эффект) обращения к нему зависит от внутреннего состояния этого модуля, изменяемого в результате предыдущих обращений к нему. Майерс не рекомендует использовать зависящие от предыстории (непредсказуемые) модули, так как они провоцируют появление в программах хитрых (неуловимых) ошибок. Однако такая рекомендация является неконструктивной, так как во многих случаях именно зависящий от предыстории модуль является лучшей реализаций информационно прочного модуля. Поэтому более приемлема следующая (более осторожная) рекомендация:
всегда следует использовать рутинный модуль, если это не приводит к плохим (не рекомендуемым) сцеплениям модулей;
зависящие от предыстории модули следует использовать только в случае, когда это необходимо для обеспечения параметрического сцепления;
в спецификации зависящего от предыстории модуля должна быть четко сформулирована эта зависимость таким образом, чтобы было возможно прогнозировать поведение (эффект выполнения) данного модуля при разных последующих обращениях к нему.
В связи с последней рекомендацией может быть полезным определение внешнего представления (ориентированного на информирование человека) состояний зависящего от предыстории модуля. В этом случае эффект выполнения каждой функции (операции), реализуемой этим модулем, следует описывать в терминах этого внешнего представления, что существенно упростит прогнозирование поведения данного модуля.
Лекция №11 Основы доказательства правильности.
Понятие правильной программы.
Под «программой» часто понимают правильную программу, т.е. программу, не содержащую ошибок. Однако, понятие ошибки в программе трактуется в среде программистов неоднозначно. Согласно Майерсу будем считать, что в программе имеется ошибка, если она не выполняет того, что разумно ожидать от нее пользователю. «Разумное ожидание» пользователя формируется на основании документации по применению этой программы. Следовательно, понятие ошибки в программе является существенно не формальным. В ПС программы и документация взаимно увязаны, образуют некоторую целостность. Поэтому правильнее говорить об ошибке не в программе, а в ПС в целом: будем считать, что в ПС имеется ошибка (software error), если оно не выполняет того, что разумно ожидать от него пользователю. В частности, разновидностью ошибки в ПС является несогласованность между программами ПС и документацией по их применению. Выделяется в отдельное понятие частный случай ошибки в ПС, когда программа не соответствует своей функциональной спецификации (описанию, разрабатываемому на этапе, предшествующему непосредственному программированию). Такая ошибка в указанной работе называется дефектом программы. Однако выделение такой разновидности ошибки в отдельное понятие вряд ли оправданно, так как причиной ошибки может оказаться сама функциональная спецификация, а не программа.
Так как задание на ПС обычно формулируется не формально, а также из-за того, что понятия ошибки в ПС не формализовано, то нельзя доказать формальными методами (математически) правильность ПС. Нельзя показать правильность ПС и тестированием, тестирование может лишь продемонстрировать наличие в ПС ошибки. Поэтому понятие правильной ПС неконструктивно в том смысле, что после окончания работы над созданием ПС мы не сможем убедиться, что достигли цели.
Надежность программного средства.
Альтернативой правильного ПС является надежное ПС. Надежность (reliability) ПС это его способность безотказно выполнять определенные функции при заданных условиях в течение заданного периода времени с достаточно большой вероятностью. При этом под отказом в ПС понимают проявление в нем ошибки. Таким образом, надежное ПС не исключает наличия в нем ошибок важно лишь, чтобы эти ошибки при практическом применении этого ПС в заданных условиях проявлялись достаточно редко. Убедиться, что ПС обладает таким свойством можно при его испытании путем тестирования, а также при практическом применении. Таким образом, фактически мы можем разрабатывать лишь надежные, а не правильные ПС.
ПС может обладать различной степенью надежности. Как измерять эту степень? Так же как в технике, степень надежности можно характеризовать вероятностью работы ПС без отказа в течение определенного периода времени. Однако в силу специфических особенностей ПС определение этой вероятности наталкивается на ряд трудностей по сравнению с решением этой задачи в технике.
При оценке степени надежности ПС следует также учитывать последствия каждого отказа. Некоторые ошибки в ПС могут вызывать лишь некоторые неудобства при его применении, тогда как другие ошибки могут иметь катастрофические последствия, например, угрожать человеческой жизни. Поэтому для оценки надежности ПС иногда используют дополнительные показатели, учитывающие стоимость (вред) для пользователя каждого отказа.
Обеспечение завершенности программного средства.
Завершенность ПС является общим примитивом качества ПС для выражения и функциональности и надежности ПС, причем для функциональности она является единственным примитивом.
Функциональность ПС определяется его функциональной спецификацией. Завершенность ПС как примитив его качества является мерой того, в какой степени эта спецификация реализована в разрабатываемом ПС. Обеспечение этого примитива в полном объеме означает реализацию каждой из функций, определенной в функциональной спецификации, со всеми указанными там деталями и особенностями. Все рассмотренные ранее технологические процессы показывают, как это может быть сделано.
Однако в спецификации качества ПС могут быть определены несколько уровней реализации функциональности ПС: может быть определена некоторая упрощенная (начальная или стартовая) версия, которая должна быть реализована в первую очередь; могут быть также определены и несколько промежуточных версий. В этом случае возникает дополнительная технологическая задача: организация наращивания функциональности ПС. Здесь важно отметить, что разработка упрощенной версии ПС не есть разработка его прототипа. Прототип разрабатывается для того, чтобы лучше понять условия применения будущего ПС, уточнить его внешнее описание. Он рассчитан на избранных пользователей и поэтому может сильно отличаться от требуемого ПС не только выполняемыми функциями, но и особенностями пользовательского интерфейса. Упрощенная же версия разрабатываемого ПС должна быть рассчитана на практически полезное применение любыми пользователями, для которых предназначено это ПС. Поэтому главный принцип обеспечения функциональности такого ПС заключается в том, чтобы с самого начала разрабатывать ПС таким образом, как будто требуется ПС в полном объеме, до тех пор, когда разработчики будут иметь дело непосредственно с теми частями или деталями ПС, реализацию которых можно отложить в соответствии со спецификацией его качества. Тем самым, и внешнее описание и описание архитектуры ПС должно быть разработано в полном объеме. Можно отложить лишь реализацию тех программных подсистем (определенных в архитектуре разрабатываемого ПС), функционирования которых не требуется в начальной версии этого ПС. Реализацию же самих программных подсистем лучше всего производить методом целенаправленной конструктивной реализации, оставляя в начальной версии ПС подходящие имитаторы тех программных модулей, функционирование которых в этой версии не требуется. Допустима также упрощенная реализация некоторых программных модулей, опускающая реализацию некоторых деталей соответствующих функций. Однако такие модули с технологической точки зрения лучше рассматривать как своеобразные их имитаторы (хотя и далеко продвинутые).
Достигнутый при обеспечении функциональности ПС уровень его завершенности на самом деле может быть не таким, как ожидалось, из-за ошибок, оставшихся в этом ПС. Можно лишь говорить, что требуемая завершенность достигнута с некоторой вероятностью, определяемой объемом и качеством проведенного тестирования. Для того чтобы повысить эту вероятность, необходимо продолжить тестирование и отладку ПС. Однако, оценивание такой вероятности является весьма специфической задачей, которая пока еще ждет соответствующих теоретических исследований.
Обеспечение точности программного средства.
Обеспечение этого примитива качества связано с действиями над значениями вещественных типов (точнее говоря, со значениями, представляемыми с некоторой погрешностью). Обеспечить требуемую точность при вычислении значения той или иной функции значит получить это значение с погрешностью, не выходящей за рамки заданных границ. Видами погрешности, методами их оценки и методами достижения требуемой точности (т.н. приближенными вычислениями) занимается вычислительная математика. Здесь мы лишь обратим внимание на некоторую структуру погрешности: погрешность вычисленного значения (полная погрешность) зависит
от погрешности используемого метода вычисления (в которую мы включаем и неточность используемой модели),
от погрешности представления используемых данных (от т.н. неустранимой погрешности),
от погрешности округления (неточности выполнения используемых в методе операций).
Обеспечение автономности программного средства.
Вопрос об автономности программного средства решается путем принятия решения о возможности использования в разрабатываемом ПС какого-либо подходящего базового программного обеспечения. Надежность имеющегося в распоряжении разработчиков базового программного обеспечения для целевого компьютера может не отвечать требованиям к надежности разрабатываемого ПС. Поэтому от использования такого программного обеспечения приходиться отказываться, а его функции в требуемом объеме приходится реализовывать в рамках разрабатываемого ПС. Аналогичное решение приходится принимать при жестких ограничениях на используемые ресурсы (по критерию эффективности ПС). Такое решение может быть принято уже в процессе разработки спецификации качества ПС, иногда – на этапе конструирования ПС.
Обеспечение устойчивости программного средства.
Этот примитив качества ПС обеспечивается с помощью так называемого защитного программирования. Вообще говоря, защитное программирование применяется при программировании модуля для повышения надежности ПС в более широком смысле. Как утверждает Майерс, «защитное программирование основано на важной предпосылке: худшее, что может сделать модуль, – это принять неправильные входные данные и затем вернуть неверный, но правдоподобный результат». Для того, чтобы этого избежать, в текст модуля включают проверки его входных и выходных данных на их корректность в соответствии со спецификацией этого модуля, в частности, должны быть проверены выполнение ограничений на входные и выходные данные и соотношений между ними, указанные в спецификации модуля. В случае отрицательного результата проверки возбуждается соответствующая исключительная ситуация. Для обработки таких ситуаций в конец этого модуля включаются фрагменты второго рода – обработчики соответствующих исключительных ситуаций. Эти обработчики помимо выдачи необходимой диагностической информации, могут принять меры либо по исключению ошибки в данных (например, потребовать их повторного ввода), либо по ослаблению влияния ошибки (например, во избежание поломки устройств, управляемых с помощью данного ПС, при аварийном прекращении выполнения программы осуществляют мягкую их остановку).
Применение защитного программирования модулей приводит к снижению эффективности ПС как по времени, так и по памяти. Поэтому необходимо разумно регулировать степень применения защитного программирования в зависимости от требований к надежности и эффективности ПС, сформулированных в спецификации качества разрабатываемого ПС. Входные данные разрабатываемого модуля могут поступать как непосредственно от пользователя, так и от других модулей. Наиболее употребительным случаем применения защитного программирования является применение его для первой группы данных, что и означает реализацию устойчивости ПС. Это нужно делать всегда, когда в спецификации качества ПС имеется требование об обеспечении устойчивости ПС. Применение защитного программирования для второй группы входных данных означает попытку обнаружить ошибку в других модулях во время выполнения разрабатываемого модуля, а для выходных данных разрабатываемого модуля попытку обнаружить ошибку в самом этом модуле во время его выполнения. По существу, это означает частичное воплощение подхода самообнаружения ошибок для обеспечения надежности ПС. Этот случай защитного программирования применяется крайне редко только в том случае, когда требования к надежности ПС чрезвычайно высоки.