Размещение в памяти и выполнение программы. Тема 4 презентация

4.1 Загрузчик
= (loader) = программа, которая помещает программы в память и готовит их к выполнению

4.1.1 Общая схема загрузки
(вариант 1: один модуль)

4.1.1 Общая схема загрузки
(вариант 2: несколько модулей)

4.1.2 Загрузчик:
функции
распределение ОП (ОЗУ)
связывание модулей
перемещение программы
загрузка программ в ОП (ОЗУ)
запуск на выполнение

4.1.2.1 Загрузчик :
1. распределение памяти
= выделение в памяти места для программ

4.1.2.1 Загрузчик :
1. распределение памяти
при загрузке по фиксированным адресам

4.1.2.1 Загрузчик :
1. распределение памяти
= Слева и справа: подпрограмма SQRT размещена с адреса 0100
= Слева: оттранслированная программа 1-го пользователя размещена с адреса 1200 ? между модулями с памяти свободный участок памяти
= Справа: оттранслированная программа 2-го пользователя размещена с адреса 056F ? перекрытие памяти !!!

4.1.2.1 Загрузчик :
1. распределение памяти
этот процесс необходимо автоматизировать

Загрузчик:
2. связывание
= связывание двух или более отдельных оттранслированных программ
= разрешение символических ссылок между объектными программами
= машинно-зависимое свойство загрузчика

Загрузчик:
2. связывание

4.1.2.2 Загрузчик:
2. связывание
необходим механизм вызова подпрограмм
Пометка символов как внешних
(обращение к ним в этой программе, а их определения – в других)
Пометка символов как внутренних
(их определения в этой программе, а обращение к ним – в других)

4.1.2.2 Загрузчик:
2. связывание
Выделение регистров для хранения адреса вызываемой подпрограммы
Осуществление возврата в вызывающую программу
+ . . . настройка передаваемых параметров
= машинно-зависимое свойство загрузчика

4.1.2.3 Загрузчик:
3. перемещение
= модификация объектной программы так, чтобы она могла загружаться с адреса, отличного от первоначального
= настройка всех величин в программе, зависящих от физических адресов (адресные константы) в соответствии с адресом выделенной для программы области памяти

4.1.2.3 Загрузчик:
3. перемещение

4.1.2.3 Загрузчик:
3. перемещение
Если внутри модулей имеются адресные константы, которые вычисляются от начала модуля, то адреса будут корректироваться относительно «базы»

4.1.2.3 Загрузчик:
3. перемещение
= перемещающие загрузчики (relocationg loader) или относительные загрузчики (relative loader) = загрузчики, обеспечивающие перемещение программ

4.1.2.4 Загрузчик:
4. загрузка
= физическое помещение машинных команд и данных в память

4.1.2.4 Загрузчик:
5. запуск на выполнение
= передача управления первой команде машинной программы , помещенной в ОЗУ

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

4.1.3 Схемы загрузки
= Сегмент = информация, рассматриваемая как единое целое, независимо от того, идет ли речь о программе или о данных
обычно сегментом является отдельная исходная или объектная программа

4.1.3 Схемы загрузки
в ассемблерах и некоторых языках программирования можно задать исходную программу, состоящую из нескольких программных сегментов и сегментов данных

4.1.3 Схемы загрузки
Загрузчик типа «компиляция - выполнение»
Абсолютный загрузчик
Настраивающий загрузчик
Непосредственно связывающий загрузчик

4.1.3 Схемы загрузки
Объединитель
Связывающий загрузчик
Перекрывающий загрузчик
Динамический объединитель

4.1.3.1 Загрузчик типа «компиляция - выполнение»

4.1.3.1 Загрузчик типа «компиляция - выполнение»
компилятор (Ассемблер), работая в одной части ОЗУ, помещает машинные команды и данные по мере трансляции непосредственно в выделенные для них ячейки памяти

4.1.3.1 Загрузчик типа «компиляция - выполнение»
«загрузчик» состоит из одной команды, которая передает управление первой команде, подлежащей выполнению скомпилированной программы

4.1.3.1 Загрузчик типа «компиляция - выполнение»
Недостатки:
некоторая часть памяти не может быть использована, так как занятая транслятором память недоступна для объектной программы.

4.1.3.1 Загрузчик типа «компиляция - выполнение»
Недостатки:
при каждом новом сеансе работы с программой приходится заново транслировать (ассемблировать) программу пользователя

4.1.3.1 Загрузчик типа «компиляция - выполнение»
Недостатки:
затруднительно организовать совместную работу нескольких сегментов программы, если исходные программы написаны на разных языках

4.1.3.1 Загрузчик типа «компиляция - выполнение»
Реализация функций:
распределение – программист
связывание – программист
перемещение – транслятор
загрузка – транслятор
запуск на выполнение – «загрузчик»

4.1.3.2 Общая схема загрузки
(вариант 3)
(программы могут быть на разных языках)

4.1.3.2 Общая схема загрузки
(вариант 3)
можно организовать хранение результатов трансляции на некотором внешнем носителе, с тем чтобы загрузить их в память тогда, когда понадобится выполнить полученную программу
при этом скомпилированная программа может быть загружена в ту же область памяти, которую раньше занимал транслятор (? трансляция уже будет завершена)

Общая схема загрузки
использование объектной программы как промежуточных данных приводит к включению в СП загрузчика
входные данные загрузчика: объектная программа (скомпилированные машинные команды, данные и другая информация)
выходные данные загрузчика: машинные команды и данные в форме, готовой для выполнения ЭВМ, помещенные в ОЗУ

4.1.3.2 Общая схема загрузки
(вариант 3)
Преимущества:
загрузчик занимает меньше памяти, чем транслятор ? у пользователя оказывается большее количество доступной памяти
при повторном выполнении программы нет необходимости в перекомпилировании

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

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

4.1.3.3 Абсолютный загрузчик

4.1.3.3 Абсолютный загрузчик
транслятор выводит результаты трансляции исходной программы почти в такой же форме, как при использовании схемы «компиляция-выполнение»
но результаты трансляции выводятся в файл объектной программы, а не в ОП

4.1.3.3 Абсолютный загрузчик
загрузчик считывает текст программы на машинном языке и помещает его в ОП по адресу, заданную транслятором

4.1.3.3 Абсолютный загрузчик
Преимущества:
обеспечивает большее количество ОП, доступной пользователю (? во время загрузки транслятор уже не находится в памяти)
простота реализации

4.1.3.3 Абсолютный загрузчик
Недостатки:
программист должен указать транслятору адрес загрузки готовой программы
если имеется ряд подпрограмм, программист должен помнить абсолютный адрес каждой из них и использовать эти адреса в явном виде для связывания подпрограмм

4.1.3.3 Абсолютный загрузчик
Реализация функций:
распределение – программист
связывание – программист
перемещение – транслятор
загрузка – загрузчик
запуск на выполнение – загрузчик

4.1.3.3 Абсолютный загрузчик
Не подходит:
для многозадачных ОС
для использования в библиотеках стандартных подпрограмм

4.1.3.3 Абсолютный загрузчик
Домашнее задание:
Записать алгоритм работы абсолютного загрузчика
Бек Л. Введение в системное программирование. М.: Мир, 1988

4.1.3.4 Настраивающий загрузчик
Назначение:
избежать необходимости повторной трансляции всех подпрограмм при внесении изменения в одну из них
освободить программиста от задач распределения памяти и осуществления связи подпрограмм

4.1.3.4 Настраивающий загрузчик
Пример:
загрузчик подпрограмм в двоично-символической форме (BSS-загрузчик)
допускает наличие в программе нескольких программных сегментов и только одного сегмента данных (общего сегмента)

4.1.3.4 Настраивающий загрузчик
транслятор компилирует каждый программный сегмент независимо и передает загрузчику текст и информацию о перемещениях и перекрестных ссылках между сегментами

4.1.3.4 Настраивающий загрузчик
Выходные данные транслятора:
вектор переходов
объектная программа
индикаторы переместимости
+
общая длина программы
длина вектора переходов

4.1.3.4 Настраивающий загрузчик
Вектор переходов:
= информация обо всех других программах, к которым в данной программе имеются обращения
записывается перед текстом объектной программы

4.1.3.4 Настраивающий загрузчик
индикаторы (биты) переместимости =
разряд перемещения:
= информация о ячейках, содержимое которых зависит от расположения программы в памяти (они должны быть изменены при необходимости загрузки программы в произвольное место памяти)

4.1.3.4 Настраивающий загрузчик

4.1.3.4 Настраивающий загрузчик
Пример:
Пусть подпрограмма B является первой по порядку вызываемой подпрограммой программы A
1. Работа транслятора:
первая ячейка вектора переходов содержит символическое имя B

4.1.3.4 Настраивающий загрузчик
команда (оператор/ инструкция), содержащее вызов подпрограммы B, транслируется в команду перехода, указывающую адрес элемента вектора переходов, связанного с подпрограммой B

4.1.3.4 Настраивающий загрузчик
2. Работа загрузчика:
1. загружает в память объектную программу A и вектор переходов
2. загружает в память каждую подпрограмму из вектора переходов (B), используя информацию о длине программы A

4.1.3.4 Настраивающий загрузчик
2. Работа загрузчика:
3. в каждый элемент вектора переходов помещает команду перехода к соответствующей подпрограмме

4.1.3.4 Настраивающий загрузчик
2. Работа загрузчика:
?вызов подпрограммы B приведет к выполнению команды перехода к первой ячейке вектора переходов, в которой будет находиться команда перехода к вызываемой подпрограмме B

4.1.3.4 Настраивающий загрузчик
используется:
в ЭВМ с фиксированным (единым) форматом команд и непосредственной адресацией (адрес операнда явно указывается в команде, базовые регистры не используются)

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

4.1.3.4 Настраивающий загрузчик
Решение проблемы перемещения:
1. Работа транслятора:
с каждой командой или полем адреса связывает специальный двоичный разряд

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

4.1.3.4 Настраивающий загрузчик
Решение проблемы перемещения:
2. Работа загрузчика:
используя значения битов переместимости, изменяет содержимое полей адреса в соответствии с начальным адресом программы

4.1.3.4 Настраивающий загрузчик
BSS-загрузчик автоматически выполняет все 5 функций загрузчика, при этом:
для распределения – информация о длине программы
для перемещения – биты переместимости

4.1.3.4 Настраивающий загрузчик
Недостатки:
вектор переходов не вполне удобен для загрузки и сохранения внешних данных (расположенных в другом программном сегменте)
вектор переходов увеличивает размер объектной программы

4.1.3.4 Настраивающий загрузчик
Недостатки:
работает с программными сегментами, но не облегчает доступ к сегментам данных, которые могут совместно использоваться несколькими подпрограммами

4.1.3.4 Настраивающий загрузчик
Устранение недостатка 3:
использовать общий сегмент данных
расширения поля битов переместимости до двух разрядов:
01 - перемещение по отношению к программному сегменту

4.1.3.4 Настраивающий загрузчик
10 - перемещение по отношению к адресу общего сегмента данных
00 или 11 – при перемещении не требуется модификация

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

4.1.3.5 Непосредственно связывающий загрузчик
Преимущество:
допускает использование большого числа программных сегментов и сегментов данных
? обеспечивает гибкие перекрестные обращения между сегментами и возможности доступа
? допускает независимую трансляцию программ

4.1.3.5 Непосредственно связывающий загрузчик
Транслятор должен передать загрузчику:
длину каждого сегмента программы или данных
словарь внешних символов (ESD)
объектные коды оттранслированной программы (TXT)

4.1.3.5 Непосредственно связывающий загрузчик
словарь перемещаемых символов (RLD)
адрес, с которого должно начинаться выполнение программы, если она не вызывается другой программой, а является «главной»

4.1.3.5 Непосредственно связывающий загрузчик
Словарь внешних символов (ESD) :
список всех символов сегмента, к которым возможно обращение из других сегментов, и их относительные адреса внутри сегмента
список всех символов, не определенных в сегменте, к которым есть обращения внутри сегмента

4.1.3.5 Непосредственно связывающий загрузчик
Словарь внешних символов (ESD) :
для программ, к которым возможно обращение извне:
тип («определение сегмента»)
относительный адрес
длина (в байтах)

4.1.3.5 Непосредственно связывающий загрузчик
Словарь внешних символов (ESD) :
для локальных имен:
тип («местное определение»)
относительный адрес

4.1.3.5 Непосредственно связывающий загрузчик
Словарь внешних символов (ESD) :
для внешних имен:
тип («внешняя ссылка»)

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

4.1.3.5 Непосредственно связывающий загрузчик
Словарь перемещаемых символов (RLD):
информация о расположении адресных констант в сегменте и описание того, каким образом должны изменяться их значения

4.1.3.5 Непосредственно связывающий загрузчик
Словарь перемещаемых символов (RLD):
адрес каждой константы, которая должна изменяться при перемещении программы
указание на символ, значение которого определяет величину изменения константы
операцию, с помощью которой вносится изменение (+ / -)

4.1.3.5 Непосредственно связывающий загрузчик
Словарь перемещаемых символов (RLD):
процесс корректировки адресных констант для внутренних символов, называют перемещением
процесс определения содержимого адресных констант для внешних символов называют связыванием

4.1.3.5 Непосредственно связывающий загрузчик
Словарь перемещаемых символов (RLD):
используется в обоих случаях
? его называют словарь перемещения и связывания

4.1.3.5 Непосредственно связывающий загрузчик
Работа загрузчика в 2 просмотра:
назначение адресов внешним ссылкам
фактические связывание, перемещение и загрузка

4.1.3.5 Непосредственно связывающий загрузчик
Реализация функций:
распределение – загрузчик
связывание – загрузчик
перемещение – загрузчик
загрузка – загрузчик
запуск на выполнение – загрузчик

4.1.3.5 Непосредственно связывающий загрузчик
Недостатки:
необходимость при каждом выполнении программы повторно выполнять все функции загрузчика для всех необходимых подпрограмм таких подпрограмм могут быть десятки и сотни ? процесс загрузки приводит к затратам времени

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

4.1.3.6 Общая схема загрузки
(вариант 4)

4.1.3.6 Общая схема загрузки
(вариант 4)
Для устранения этих недостатков:
выполнения загрузки с помощью двух самостоятельных программ:
объединителя
загрузчика модуля

4.1.3.7 Объединитель
1. Объединитель:
= программа, которая выполняет те же самые функции, что и непосредственно связывающий загрузчик по объединению подпрограмм, но настроенный и связанный текст помещает не в ОП, а файл загрузочного модуля

4.1.3.7 Объединитель
= загрузочный модуль = имеет формат, допускающий загрузку программы в ОП для выполнения

4.1.3.7 Объединитель
2. Загрузчик модуля:
= реализует функции:
загрузки
запуска
= это может быть настраивающий (перемещающий) загрузчик

4.1.3.7 Объединитель
Два основных класса:
построитель образа памяти
редактор связей

4.1.3.6 Объединитель: построитель образа памяти
простейший тип объединителя
вырабатывает загрузочный модуль, похожий на файл, создаваемый абсолютным загрузчиком
? привязка программы к конкретным адресам памяти выполняется в процессе объединения подпрограмм

4.1.3.7 Объединитель: построитель образа памяти
загрузочный модуль такого типа выглядит как моментальная фотография (образ памяти), его называют модулем образа памяти, а объединитель - построитель образа памяти

4.1.3.7 Объединитель: построитель образа памяти
Преимущества:
относительно прост
обеспечивает высокое быстродействие

4.1.3.7 Объединитель: построитель образа памяти
Реализация функций:
распределение – объединитель
связывание – объединитель
перемещение – объединитель
загрузка – загрузчик
запуск на выполнение – загрузчик

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

4.1.3.8 Связывающий загрузчик = редактор связей
? загрузчик модуля должен также выполнять функции распределения памяти и перемещения

4.1.3.8 Связывающий загрузчик = редактор связей
Преимущества:
обеспечивает большую гибкость при распределении, памяти и загрузке, чем построитель образа памяти
Недостаток:
более сложен, чем построитель образа памяти

4.1.3.8 Связывающий загрузчик = редактор связей
Реализация функций:
распределение – загрузчик
связывание – объединитель
перемещение – загрузчик
загрузка – загрузчик
запуск на выполнение – загрузчик

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

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

4.1.3.9 Динамическая загрузка
существуют аппаратные методы для решения этой задачи (страничная организация и сегментация)
рассмотрим традиционную схему динамической загрузки с последовательным использованием объединителя и загрузчика

4.1.3.10 Перекрывающий загрузчик
обычно разные подпрограммы одной программы требуются в разное время (например, фазы анализа и генерации кода в компиляторе взаимно исключают друг друга)

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

4.1.3.10 Перекрывающий загрузчик
Пример:
A вызывает B,D
B вызывает C,E
D вызывает E
C,E не вызывают
? всего 100К

4.1.3.10 Перекрывающий загрузчик
Пример:
никогда
не выполняются
одновременно:
В и D
С и Е

4.1.3.10 Перекрывающий загрузчик
Как уменьшить требуемое количество памяти?
? загрузить в память только те процедуры, которые в действительности могут быть использованы в некоторый конкретный момент времени

4.1.3.10 Перекрывающий загрузчик
? всего 70К (определено по самой длинной ветви структуры с перекрытием)

4.1.3.10 Перекрывающий загрузчик
распределение памяти
для всех подпрограмм
в структуре с перекрытием
Необходимо: загрузчик
модуля загружает различные
подпрограммы по мере
необходимости

4.1.3.10 Перекрывающий загрузчик
= супервизор перекрытий =
та часть загрузчика, которая принимает запросы и загружает необходимые подпрограммы

4.1.3.10 Перекрывающий загрузчик
Реализация функций:
распределение – загрузчик
связывание – объединитель
перемещение – загрузчик
загрузка – загрузчик
запуск на выполнение – загрузчик

4.1.3.11 Динамический объединитель
Недостатки схем 1-7:
если к некоторой подпрограмме имеется обращение, а она не используется при выполнении программы, загрузчик все равно выполняет работу по связыванию этой подпрограммы с основной программой

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

4.1.3.11 Динамический объединитель
Для устранения недостатков:
динамическое связывание =
= механизм, с помощью которого загрузка и связывание по внешним ссылкам откладываются до выполнения программы

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

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

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

4.1.3.11 Динамический объединитель
Недостаток:
дополнительные затраты и сложности, связанных с переносом большей части процесса связывания на время выполнения программы

4.1.3.11 Динамический объединитель
Реализация функций:
распределение – загрузчик
связывание – загрузчик
перемещение – загрузчик
загрузка – загрузчик
запуск на выполнение – загрузчик