СП - Краткие ответы на экзаменационные вопросы (1115082), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

Достоинства: простота.

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

Явное выделение блоков переменного размера. Один из методов выделения блоков переменного размера – метод первого подходящего. При выделении блока размера s находится первый блок размера f >= s. Затем этот блок разбивается на два – с размерами s и f-s. Но мы можем и не найти такой фрагмент. Тогда необходимо приостанавливать выполнение программы и искать все использованные фрагменты и перемещать их на дно кучи

Достоинства: эффективное использование памяти, место не тратится попусту.

Недостатки: дольше работает программа.

Неявное выделение/освобождение памяти. Неявно выделяемые блоки памяти также могут быть фиксированного или переменного размера. При неявном динамическом выделении и освобождении блоков памяти, выделяемые блоки обычно имеют следующую структуру: - размер блока (для блоков переменного размера)

- счетчик ссылок, пометка (обычно есть либо одно, либо другое)

- указатели на блоки

- то, что досталось пользователю, заказавшему этот блок

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

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

1. Принципы реализации виртуальных функций.

*****

1. Машинно-независимая оптимизация и машинно-зависимая оптимизация. Примеры оптимизирующих преобразований.

• Машинно-независимые преобразования:

1. Удаление недостижимого кода

if (1) S1; else s2 => s1;

1. Оптимизация линейных участков программы:

1. Удаление бесполезных присваиваний

a=b*c; d=b+c; a=d*c; => d=b+c; a=d*c;

1. Исключение избыточных вычислений:

d=d+b*c; a=d+b*c; c=d+b*c; => t=b*c; d=d+t; a=d+t; c=a;

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

i=2+1; j=6*i+i; => i=3; j=21;

1. Перестановка операций:

a=2*b*3*c; => a=(2*3)*(b*c);

a=(b+c)+(d+c); => a=(b+(c+(d+c)));

1. Арифметические преобразования:

a=b*c+b*d; => a=b*(c+d);

a*1 => a; a*0 => 0; a+0 => a;

1. Оптимизация вычисления логических выражений:

a || b || c || d => a, если a=true;

Но: a || f(b) || g(c) - сохраняется, т.к функции могут иметь побочные

эффекты.

1. Оптимизация передачи параметров в процедуры || функции.

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

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

В С++ есть специальный унификатор register, который ставится для разрешения помещения параметра в регистр.

1. Подстановка кода функции (вместо вызова функции в объектный код – т.к. на вызов функции тратится время).

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

1. Оптимизация циклов.

1. Вынесение инвариантных вычислений из циклов

for (i=1; i<=10; i++) a[i]=b*c*a[i]; => d=b*c; for (i=1; i<=10; i++) a[i]=d*a[i];

1. Замен операций с индуктивными переменными (перменными, образующими арифметическую прогрессию).

- for (i=1; i<=N; i++) a[i]=i*10; =>

=> t=10; i=1; while (i<=N) {a[i]=t; t=t+10; i++;}

- S=10; for (i=1; i<=N; i++) {r=r+f(S); S=S+10; } =>

=> S=10; m=N*10; while (S<=m) {r=r+f(S); S=S+10; }

1. Слияние и развёртывание циклов.

Слияние:

for (i=1; i<=N; i++) for (j=1; j<=M; j++) a[i][j]=0; =>

=> K=m*N; //(остаётся 1 цикл)

for (i=1; i<=k; i++) a[i]=0;

Развёртывание:

for (i=1; i<=3; i++) a[i]=i; => a[1]=1; a[2]=2; a[3]=3;

• Машинно-зависимые преобразования:

1. Распределение регистров процессора.

2. Оптимизация кода для процессора, допускающая распараллеливание вычислений. (В программе надо выделить куски кода, эти куски вычисляются независимо друг от друга => их можно вычислять параллельно по разным процессам.)

a+b+c+d+e+f

1 поток. => ((((a+b)+c)+d)+e)+f (без распараллеливания)

2 потока. => ((a+b)+c)+((d+e)+f)

3 потока. => (a+b)+(c+d)+(e+f)

1. Интегрированная среда разработки (ИСР).

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

Содержит в себе:

• Репозиторий – организованное хранилище информации, появляющейся в течение всего “жизненного цикла” создания программного продукта.

• Специальные автоматические средства разработки образов. Например, языки 4 поколения (4GL), оперирующие образами. Такие средства позволяют осуществлять разделение обработки (создания) программы между несколькими разработчиками.

• Редакторы текстов.

• Средства документирования.

• Средства тестирования и отладки.

• Средства управления.

• Средства реинжениринга (т.е. восстановления структуры программы по коду).

Примеры ИСР – TurboPascal, Delphi, Visual Studio, K-Develop.

Ключевые особенности:

• Интегрированность среды

• Библиотека компонент

• Визуальная технология разработки

• Технология two-ways-tool

• Поддержка работы с базами данных

• «горячие клавиши»

• X-курсор

• Останов с редактированием, пошаговое выполнение, подсветка выполняемой строки

1. Основные функции редактора текста в рамках ИСР. Примеры его интегрированности с другими компонентами ИСР.

1. Подготовка текста программы.

2. Многооконный интерфейс с поддержкой “буксировки” текста мышкой (функция drag & drop – перенос фрагмента мышкой).

3. Интеграция с компилятором.

1. Визуализация текста в выделении лексем.

2. Дополнение кода (интерактивная подсказка).

Например,

a. ………… (А – класс) - после выполнения такой команды получим список, что входит в “a”.

f (………… - дополнение кода или интерактивная подсказка.

1. Шаблоны кода – часто используемые фрагменты программы.

2. Всплывающие подсказки.

3. Выделение места, в котором при компиляции обнаружена ошибка.

1. Интеграция с отладчиком.

1. Отображение контрольных точек останова при отладке.

2. Отображение текущего значения объекта при наведении курсора на идентификатор.

1. Отладчики, их возможности. Примеры интегрированности отладчика с другими компонентами ИСР.

• Пошаговое выполнение программы (шаг = строка, с трассировкой внутри вызываемой функции или без нее)

• Выполнение программы до строки, в которой в редакторе стоит курсор

• Выделение выполняемой строки в данный момент

• Приостановка выполнения программы

• Можно запросить значение переменной

• Можно заказать вычисление некоторого выражения

• Можно изменить значение переменной и продолжить выполнение программы

• Расставить/снять точки останова, которые визуализируются в текстовом редакторе

• Вся информация должна выдаваться в терминах исходной программы

1. Редактор внешних связей, его назначение и принципы работы. Загрузчик.

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

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

• Должен связать объектные файлы, порожденные компилятором, и библиотечные файлы, входящие в состав системы программирования (для статически связываемых библиотек)

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

1. Библиотеки. Основные типы библиотек.

   1. Библиотеки функций - определяют возможности СП в целом, чем больше функций, тем лучше. Подразделяются на 2 класса:

- библиотеки для языков программирования

- библиотеки для решения задач какой-то проблемной области

Библиотеки функций представляют собой библиотеки откомпилированных объектных модулей.

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

- конкретные классы

- абстрактные классы

- шаблоны классов

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

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

Библиотеки классов компилируются вместе с программой.

1. Библиотеки компонент – готовые откомпилированные программные модули.

В настоящее время используются следующие технологии:

• CORBA – исполняемые программные компоненты из сети. Существует её реализация для большинства систем. Технология не зависит от используемого языка.

• СОМ – исполняемые программные компоненты, размещённые локально (на компьютере пользователя). Модифицированные версии СОМ – DCOM, ActivX.

• Java Beans – исполняемые программные компоненты на языке Java.

Нельзя путать библиотеки с пакетами прикладных программ!

Пакеты прикладных программ (ППП) – специальным образом организованные программные комплексы, используемые для определённой области деятельности.

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

Для подключения статических библиотек включаются файлы, на уровне редактора связей подключаются конкретные тела.

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

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

- несколько программ могут использовать код одной библиотеки

- нет необходимости перекомпилировать свои программы при изменении текста программы в библиотеке.

В виде динамических библиотек оформлены системные функции, например, API.

1. Критерии проектирования стандартных библиотек.

1. Общезначимость содержимого

2. Эффективность

3. Безопасность – не должны допускать провоцирование ошибок, а, наоборот, предотвращать их

4. Завершённость

5. Сочетаемость с базовыми типами данных

6. Возможность служить фундаментом для других библиотек

1. Стандартная библиотека С++.

Обеспечивает:

1. поддержку свойств языка

- управление памятью – new/delete.

- предоставление информации о типах во время выполнения программы.

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

1. предоставление информации о зависящих от реализации аспектах языка.

2. предоставление общеупотребительных функций.

3. предоставление некоторых нетривиальных и машинно-зависимых средств (например, ввод/вывод, сортировка при работе со списком)

Имена локализованы в пространстве имён std – т.е. можно использовать эти имена, и это не будет приводить к конфликту.

При записи <cstdio> буква “c” обозначает, что файл подключается именно из стандартной библиотеки С.

1. Стандартная библиотека шаблонов STL: контейнеры, итераторы, алгоритмы, аллокаторы.

Контейнеры.

Контейнер – шаблонный класс для хранения объектов какого-либо одного и того же типа. Контейнеры бывают различных типов. Например, в классе vector определяется динамический массив, queue – очередь, list – линейный список. Помимо таких базовых контейнеров, в библиотеке стандартных шаблонов определены и ассоциативные контейнеры, которые позволяют получать хранящиеся в них значения. Например, в классе map определён ассоциативный список, доступ к элементам которого осуществляется с помощью уникальных ключей. Т.е. в таком списке элемент – это пара «значение-ключ».

Контейнеры STL:

Vector <T> – динамический массив.

List <T> – линейный список.

Stack <T> – стек.

Queue <T> – очередь.

Deque <T> – двусторонняя очередь.

Характеристики

Список файлов ответов (шпаргалок)