Пратт Т. Языки программирования. Разработка и реализация

Подождите немного. Документ загружается.

Глава 2. Влияние

машинной архитектуры

Как описано в разделе 1.2, ранние языки программирования разрабатывались так,

чтобы написанные на них программы могли эффективно работать на дорогостоя

щих вычислительных машинах. Поэтому программы, написанные на ранних язы

ках (таких как FORTRAN, предназначенный для численных расчетов, или LISP,

работающий со списками), транслировались в эффективный машинный код, даже

если писать их было достаточно сложно. Теперь ситуация изменилась — машины

стали работать гораздо быстрее, их стоимость снизилась, но зато возросла стоимость

работы программиста. В настоящее время приоритетное значение имеет создание

программ, при написании которых меньше вероятность допустить ошибку, даже

если при этом несколько возрастет время их выполнения. Например, определение

пользовательских типов данных в ML, объект класса (class) в С++ и специфика

ция пакета (package) в языке Ada упрощают процесс написания корректно работа

ющих программ, но за это приходится расплачиваться уменьшением скорости вы

полнения. В этой главе мы постараемся ответить на вопрос, как создаются языки

программирования.

При разработке языка программирования учитывается архитектура программ

ного обеспечения, которая, соответственно, оказывает влияние на идеологию соз

даваемого языка. Это влияние определяется:

1) реальным компьютером, на котором будут выполняться написанные на дан

ном языке программы;

2) моделью выполнения, или виртуальным компьютером, который поддержи

вает этот язык на реальном компьютере.

2.1. Структура и принципы

работы компьютера

Компьютер представляет собой интегрированный набор алгоритмов и структур

данных, способный хранить и выполнять программы. Компьютер может быть соз

дан как реальное физическое устройство и состоять из проводов, интегральных

схем, монтажных плат и тому подобных элементов — в таком случае мы говорим о

реальном, или физическом, компьютере, называя его просто компьютер. Но он так

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

компьютере, — тогда он называется программномоделируемым компьютером. Ре

ализация языка программирования осуществляется путем создания транслято

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

на машинном языке, которые уже могут непосредственно выполняться на каком

либо компьютере. Этот компьютер может являться как реальным физическим ком

пьютером, так и виртуальным компьютером, состоящим частично из аппаратуры

и частично из программного обеспечения.

Любой компьютер составляют шесть основных компонентов, функциональность

которых тесно взаимосвязана с основными аспектами языка программирования.

1. Данные. Компьютер должен обрабатывать различные типы простейших эле

ментов данных и структур данных.

2. Элементарные операции. Компьютер должен иметь набор элементарных

операций для работы с данными.

3. Управление последовательностью действий. Компьютер должен обеспечи

вать управление последовательностью выполнения элементарных операций.

4. Доступ к данным. Компьютер должен предоставлять механизмы управле

ния данными, которые необходимы для выполнения любой операции.

5. Управление памятью. Компьютер должен предоставлять механизмы управ

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

6. Операционная среда. Компьютер должен предоставлять механизмы связи с

внешней средой, содержащей программы и данные, подлежащие обработке.

Эти задачи определяют особенности разработки языков программирования. Но

прежде, чем рассматривать их в достаточно сложном контексте языков програм

мирования высокого уровня, следует посмотреть на них в более простом контек

сте реального физического компьютера.

2.1.1. Аппаратные средства компьютера

Архитектура компьютеров весьма разнообразна, но рис. 2.1 иллюстрирует доволь

но типичную, традиционную организацию большинства компьютеров. Оператив

ная память содержит программы и данные, которые подлежат обработке. Эта

обработка выполняется посредством интерпретатора, который по очереди де

кодирует каждую команду на машинном языке и вызывает указанную простей

шую операцию вместе с указанными в качестве операндов входными данными.

Простейшие операции манипулируют данными, расположенными в оперативной

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

или данными между памятью и внешней операционной средой. Давайте более де

тально рассмотрим перечисленные выше шесть основных функциональных осо

бенностей компьютера.

Данные. На схеме (рис. 2.1) изображены три основных компонента, предна

значенные для хранения данных: оперативная память, быстрые регистры и вне

шние файлы. Оперативная память обычно представляет собой линейную после

довательность битов, разделенную на слова фиксированной длины (как правило,

слово содержит 32 или 64 бита) или байты, состоящие из 8 битов (4 или 8 байтов

на одно слово). Быстрые регистры состоят из слов (то есть из последовательно

2.1. Структура и принципы работы компьютера

66 Глава 2. Влияние машинной архитектуры

стей битов длиной в слово) и могут иметь подполя, к которым возможен прямой

доступ. Содержимое регистра может представлять собой данные или адрес в опе

ративной памяти, по которому находятся эти данные или следующая подлежащая

выполнению команда. Кэш (быстродействующая буферная память) обычно рас

положен между быстрыми регистрами и оперативной памятью и является тем ме

ханизмом, который ускоряет доступ к данным, хранящимся в оперативной памя

ти. Внешние файлы хранятся на жестком диске, на дискете или компактдиске. Они

обычно состоят из набора записей, каждая из которых является последовательно

стью битов или байтов.

Рис. 2.1. Организация традиционного компьютера

Компьютер располагает некоторым набором встроенных типов данных, кото

рыми можно манипулировать напрямую при помощи простейших операций. Обыч

ный набор таких типов данных включает целые числа, вещественные числа оди

нарной точности (то есть представленные одним словом), известные как числа с

плавающей точкой, символьные строки фиксированной длины и строки битов

фиксированной длины (эта длина в данном случае равна количеству битов, кото

рые помещаются в одно слово памяти).

Помимо этих очевидных, аппаратно поддерживаемых элементов данных, про

граммы также представляют собой некоторую форму данных. Как и для других

встроенных типов данных, в компьютере должно существовать встроенное пред

ставление для программ, называемое представлением на машинном языке ком

пьютера. Как правило, представление программы на машинном языке состоит из

последовательности ячеек памяти, в каждой из которых содержится одна или бо

лее команд. Каждая команда, в свою очередь, состоит из кода операции и набора

указателей операндов.

Операции. В компьютере должен присутствовать набор встроенных простей

ших операций, которым обычно сопоставлены коды операций, используемые в

командах машинного языка. В типичный набор входят простейшие операции, про

изводящие арифметические действия (сложение, вычитание, умножение и деле

ние) для каждого из встроенных типов численных данных (целочисленных и ве

щественных); простейшие операции для проверки различных свойств элементов

данных (например, для проверки на равенство нулю, определение знака); простей

шие операции для доступа к различным частям элементов данных и их модифика

ции (например, извлечение символа из содержащего его слова или его запись туда,

извлечение адреса какоголибо операнда из некоторой команды или его запись

туда); простейшие операции для управления устройствами ввода и вывода дан

ных и, наконец, простейшие операции для управления последовательностью вы

полнения команд (например, безусловный переход к некоторой команде или воз

врат в некоторую точку программы).

По мере развития традиционных компьютеров (так называемых CISCкомпью

теров, или компьютеров с полным набором команд — complex instructions set com

puters) набор доступных команд все более расширялся и становился более мощ

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

стороны, было обнаружено, что, напротив, увеличить скорость работы компьютера

можно и с меньшим числом простейших команд, так как в этом случае упрощается

внутренняя логика центрального процессора (ЦП). Такие компьютеры называются

RISCкомпьютерами (reduced instruction set computers — компьютеры с сокра

щенным набором команд); мы обсудим их подробнее в разделе 11.3.

Управление последовательностью действий. При выполнении программы на

машинном языке адрес очередной команды, которая должна выполняться, опре

деляется содержимым специального регистра программных адресов (также извест

ного под названием счетчика команд), в котором всегда содержится адрес следую

щей команды. Некоторые простейшие операции могут изменять содержимое этого

регистра, чтобы передать управление в другую часть программы, но в действитель

ности этот регистр используется только интерпретатором, который и управляет

последовательностью выполнения операций.

Интерпретатор играет центральную роль в работе компьютера. Обычно он вы

полняет простой циклический алгоритм, схематично представленный на рис. 2.2.

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

команды из регистра программных адресов (и увеличивает значение этого регист

ра, присваивая ему адрес следующей команды), выбирает указанную команду из

памяти, декодирует ее, разбивая на код операции и набор указателей операндов,

при необходимости выбирает из памяти указанные операнды и вызывает указан

ную операцию с указанными операндами в качестве аргументов. Простейшие опе

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

вводавывода и модифицировать последовательность выполнения операций пу

тем изменения содержимого регистра программных адресов. После выполнения

2.1. Структура и принципы работы компьютера

68 Глава 2. Влияние машинной архитектуры

указанной операции интерпретатор просто возвращается к началу цикла и снова

повторяет все описанные действия.

Рис. 2.2. Алгоритм интерпретации и выполнения программы

Доступ к данным. В любой машинной команде помимо кода операции должны

быть указаны те операнды, к которым эта операция будет применена. Обычно опе

ранд содержится в оперативной памяти или в рабочем регистре. Компьютер дол

жен обладать средствами для указания операндов и для извлечения значения

операнда, находящегося по заданному указателем адресу. Аналогично результат

выполнения простейшей операции должен сохраняться в некотором определен

ном месте памяти. Описанные средства мы называем средствами управления до

ступом к данным. Традиционная схема заключается в том, что областям памяти

ставятся в соответствие некоторые целочисленные значения, которые играют роль

адресов этих областей, а специальные операции извлекают по заданному адресу

содержимое соответствующих областей памяти (или, наоборот, сохраняют в обла

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

часто задаются простым целочисленным адресом.

Управление памятью. Одним из ведущих принципов организации работы

компьютера является сведение к минимуму времени бездействия каждой из

его составных частей (оперативной памяти, центрального процессора, внешних

устройств). Основная трудность, встречающаяся при попытке реализации этого

принципа, заключается в том, что в ЦП время на выполнение операций обычно

измеряется в наносекундах (например, на выполнение одной типичной операции

в современном процессоре требуется 5–10 нс), получение данных из оперативной

памяти занимает уже несколько микросекунд (что составляет примерно 50–70 нс),

а обращение к внешним источникам требует затрат времени порядка 10–15 мс.

В итоге внутренняя скорость работы микропроцессора отличается от скорости до

ступа к дисковым данным в 1 000 000 раз. Для того чтобы подходящим образом

сбалансировать эти скорости, используются различные средства управления па

мятью.

В простейшем случае (например, в сравнительно дешевом персональном ком

пьютере для домашнего использования) предусмотрены только самые простые

средства управления памятью, встроенные в аппаратную часть компьютера. Про

граммы и данные остаются в памяти в течение всего времени выполнения про

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

однаединственная программа. Хотя процессору и приходится простаивать в ожи

дании доступности необходимых данных, оказывается более выгодно (в отноше

нии цены) не использовать дополнительные аппаратные средства, ускоряющие

выполнение программ.

В операционных системах часто используется мультипрограммирование как

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

ступа к внешним данным и скоростью работы процессора. Этот способ заключает

ся в том, что пока необходимые для выполнения определенной программы данные

считываются с внешних устройств (например, с диска), процессор переходит к вы

полнению какойлибо другой программы. Для того чтобы в памяти могли сосуще

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

практикой стало включение средств для страничной организации памяти (paging)

или динамического перемещения программ непосредственно в аппаратную часть.

Алгоритмы страничной организации памяти позволяют предсказать с опреде

ленной вероятностью, какие программы и данные потребуются в ближайшее вре

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

ность максимально быстрого доступа к ним. Программы выполняются до тех пор,

пока в оперативной памяти имеется правильная страница с необходимыми коман

дами или данными. Если же в какойто момент возникает ошибка изза отсут

ствия страницы (page fault; то есть требуемая команда или данные расположены

на странице, отсутствующей в оперативной памяти), тогда операционная система

извлечет ее из внешнего устройства хранения данных, в то время как процессор

переключится на выполнение другой программы, для которой в оперативной па

мяти имеются необходимые данные и команды.

Для решения проблемы различия между скоростью доступа к основной памяти

и скоростью работы центрального процессора используется кэш — быстродейству

ющая буферная память небольшого объема, которая является промежуточным зве

ном между оперативной памятью и центральным процессором (см. рис. 2.1). Вме

2.1. Структура и принципы работы компьютера

70 Глава 2. Влияние машинной архитектуры

стимость кэша невелика: от 1 Кбайт (Кбайт — стандартное обозначение для 1024,

или 2

, байт) до 512 Кбайт. В нем содержатся данные и инструкции, которые толь

ко что были использованы центральным процессором и, следовательно, с большой

вероятностью понадобятся в ближайшем будущем. Данные, расположенные в кэше,

незамедлительно становятся доступными для процессора, как только в них возни

кает необходимость; если данные в кэше подвергаются изменениям в результате

выполнения программы, то эти измененные данные записываются в оперативную

память и скорость доступа к ним уменьшается. Если данные с указанным адресом

не содержатся в кэше, то на аппаратном уровне извлекается блок данных, содер

жащий данные с требуемым адресом вместе с данными, содержащимися в несколь

ких последующих адресах, которые с наибольшей вероятностью потребуются про

цессору в ближайшее время.

Кэш позволяет компьютеру работать так, как если бы скорость оперативной

памяти была такой же, как скорость центрального процессора. Даже такой неболь

шой объем кэша, как 32 Кбайт, позволяет увеличить эффективность работы про

цессора до 95 %, то есть почти до такого уровня, как если бы скорость оперативной

памяти совпадала со скоростью центрального процессора.

Операционная среда. Операционная среда компьютера обычно состоит из на

бора внешних запоминающих устройств и устройств вводавывода. Эти устрой

ства являются средством связи компьютера с внешним миром, и любое общение

с компьютером возможно лишь через его операционную среду. Между различны

ми типами внешних устройств, составляющих его операционную среду, существу

ют аппаратные различия, обусловленные различным их назначением или скоро

стью доступа к ним. Например, существуют быстрые запоминающие устройства

(расширенная память), устройства хранения со средней скоростью доступа (гиб

кие диски и компактдиски), медленные запоминающие устройства (ленты), а так

же устройства вводавывода (устройства чтения данных, принтеры, мониторы, ли

нии передачи данных).

Альтернативная архитектура компьютера. Аппаратная часть компьютера мо

жет быть организована различными способами. Описанную выше архитектуру

обычно называют архитектурой фон Неймана. Но существуют и другие варианты.

Архитектура фон Неймана. Компьютер фон Неймана называется так в честь

математика Джона фон Неймана. Основные принципы устройства этого компью

тера были разработаны им в начале 1940х гг. как часть проекта создания одной из

первых электронновычислительных машин ENIAC. В варианте фон Неймана ком

пьютер состоял из небольшого центрального процессора (ЦП), который выполнял

простейшие операции, осуществлял управление последовательностью действий и

включал в себя регистры для хранения результатов простейших операций; также

имелась оперативная память и была предусмотрена возможность получения, хра

нения и обмена данными в форме слов между ЦП и оперативной памятью. До сих

пор большинство компьютеров создается на основе этой модели, хотя для улучше

ния качества работы были сделаны такие дополнения, как кэш, виртуальная па

мять и увеличение количества регистров ЦП.

Мультипроцессоры. Как уже было сказано, основная проблема компьютера фон

Неймана заключается в большой несбалансированности скоростей доступа к дан

ным, хранящимся на внешних запоминающих устройствах, и в быстрых регистрах

центрального процессора. Альтернативный путь решения этой проблемы заклю

чается в использовании нескольких ЦП в одной системе. Такие мультипроцессор

ные системы применяются уже более 30 лет. Объединение нескольких сравнительно

недорогих процессоров с общей оперативной памятью, запоминающими устрой

ствами и аппаратурой вводавывода позволяет организовать достаточно эффек

тивную систему. Производительность этой системы возрастает за счет того, что

каждый из этих процессоров выполняет какуюто определенную программу, та

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

По большей части эти усовершенствования не оказывают влияния на разра

ботку языков программирования, так как каждый процессор работает только с од

ной программой, независимой от других. Тем не менее развитие языков програм

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

систем, в которых программы, выполняемые на нескольких компьютерах, могут

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

ютерной архитектуры, которые несколько отличаются от неймановской, в разде

ле 11.3.2, а также рассмотрим, как эти изменения архитектуры влияют на разра

ботку языков программирования и их трансляцию.

Состояния компьютера. Понимание статической организации компьютера

в терминах данных, операций, управляющих структур и т. п. представляет только

часть общей картины. Для полного понимания необходимо также ясно представ

лять себе динамику работы компьютера во время выполнения программы. То есть

нужно знать, каково содержимое различных компонентов памяти в начале выпол

нения, какова последовательность выполнения различных операций, как различ

ные элементы данных изменяются в процессе выполнения программы и каков ко

нечный результат работы программы.

Для наблюдения за динамикой работы компьютера удобно использовать поня

тие состояние компьютера. Рассмотрим процесс выполнения программы как по

следовательное прохождение компьютера через ряд состояний. Каждое состояние

характеризуется содержимым оперативной памяти, регистров и внешней памяти

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

состояние этих областей памяти определяет соответственно исходное состояние

компьютера. Каждый шаг при выполнении программы преобразует существую

щее состояние компьютера в некоторое новое состояние посредством изменения

содержимого одной или нескольких указанных областей памяти. Это преобразо

вание называется сменой состояний. Когда выполнение программы заканчивает

ся, окончательное содержимое этих областей памяти определяет конечное состоя

ние компьютера. Таким образом, выполнение программы можно рассматривать как

процесс последовательной смены состояний компьютера.

2.1.2. Программно!аппаратный компьютер

Ранее мы определили компьютер как интегрированный набор алгоритмов и струк

тур данных, способный хранить и выполнять программы. Программы, выполняе

мые какимлибо компьютером, конечно, написаны на машинном языке этого

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

с простыми форматами команд и операциями типа «сложить два числа» и «загру

2.1. Структура и принципы работы компьютера

72 Глава 2. Влияние машинной архитектуры

зить в регистр содержимое области памяти». Но в действительности машинный

язык не должен быть непременно языком низкого уровня. Можно выбрать любой

язык (например, FORTRAN или ML) и точно определить набор структур данных

и алгоритмов, которые задают правила выполнения любой программы, написан

ной на этом языке. Тогда для организованного таким образом компьютера ма

шинным языком будет выбранный язык программирования. Каждая программа

определяет исходное состояние компьютера, а правила выполнения программы

определяют последовательность смены состояний, через которые пройдет компь

ютер в процессе ее выполнения. Результат выполнения программы определяется

конечным состоянием компьютера, когда выполнение программы закончится (если

это вообще произойдет).

Имея точное определение того, что такое компьютер, всегда можно сконструи

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

самым выбранным языком программирования. Это утверждение остается в силе

даже для таких языков высокого уровня, как C, Ada и др. (например, компьютер

B5500 фирмы Burroughs, упомянутый в разделе 1.2.1). Это утверждение основы

вается на важном основополагающем принципе компьютерного конструирования:

любой точно определенный алгоритм или структура данных могут быть реализо

ваны в аппаратуре. Поскольку компьютер — это просто набор алгоритмов и струк

тур данных, то можно предположить, что его аппаратная реализация возможна

независимо от сложности компьютера или используемого машинного языка.

На практике в качестве машинных языков обычно используются языки низ

кого уровня из тех соображений, что в противном случае (если взять, например,

в качестве машинного язык C или Ada) компьютер был бы гораздо сложнее устро

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

в большинстве случаев оказался бы гораздо менее гибким средством решения за

дач программирования, чем компьютер с машинным языком низкого уровня. Ап

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

неструктурированной оперативной памятью и набором регистров может быть срав

нительно эффективно запрограммирован под любой тип из достаточно широкого

класса компьютеров. Об этом пойдет речь в следующих разделах. Иногда создают

ся компьютеры с машинными языками высокого уровня, но обычно предпочита

ют другие (не аппаратные) способы реализации этих языков.

Обычной альтернативой строго аппаратной реализации компьютера является

программноаппаратный компьютер, который моделируется микропрограммой,

выполняемой на специальном микропрограммируемом компьютере. Машинный

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

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

и быстрыми регистрами, непосредственно между самими регистрами и из одних

регистров в другие через такие обрабатывающие устройства, как сумматоры и ум

ножители. На основе этого простого набора команд создается специальная ми

кропрограмма, которая определяет цикл интерпретации и простейшие операции

желаемого компьютера. Эта микропрограмма моделирует операцию желаемого ком

пьютера на микропрограммируемом хосткомпьютере. Обычно эта микропрограм

ма размещается в специально отведенной для нее памяти, доступной только для

чтения, на хосткомпьютере и выполняется на нем с большой скоростью. Концеп

ция микропрограммного моделирования, по существу, аналогична технологии мо

делирования при помощи программного обеспечения, которое мы будем обсуж

дать в следующем разделе. Различие заключается в том, что хосткомпьютер в этом

случае специально конструируется для микропрограммирования и способен обес

печить скорость выполнения программ на моделируемом компьютере, сравнимую

со скоростью работы соответствующей аппаратной реализации.

Микропрограммируемое моделирование компьютера иногда называется эму

ляцией. Получившийся в результате компьютер называется виртуальным компью

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

не существовал.

2.1.3. Трансляторы и виртуальная архитектура

Теоретически возможно создать аппаратный или программноаппаратный компь

ютер, на котором непосредственно выполнялись бы программы, написанные на

любом избранном языке программирования. Таким образом получился бы компь

ютер с соответствующим машинным языком, например С, Prolog, LISP и т. д. Но

создание такого компьютера было бы в большинстве случаев экономически невы

годно. Практические соображения в отношении быстродействия, гибкости и сто

имости говорят в пользу создания компьютеров с машинными языками достаточ

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

языках высокого уровня, далеко отстоящих от машинного языка. Поэтому возни

кает вопрос: как организовать выполнение программ (написанных на языках вы

сокого уровня) на конкретном, имеющемся в распоряжении программиста компь

ютере, независимо от машинного языка.

Для этой задачи существует два основных решения.

1. Трансляция (компиляция). Можно сконструировать транслятор, который

будет переводить программы, написанные на языках высокого уровня, в эк

вивалентные программы на машинном языке используемого компьютера.

Затем интерпретатор и простейшие операции, встроенные в аппаратную

часть компьютера, непосредственно выполняют оттранслированную в ма

шинный код программу. Общий термин транслятор используется для обо

значения любого языкового процессора, который воспринимает программы

на некотором исходном языке в качестве входных данных (этот исходный

язык может быть как высокого, так и низкого уровня), а на выходе выдает

эквивалентные по своей функциональности программы, но уже на другом,

так называемом объектном языке (который также может быть произвольно

го уровня). Существуют термины для обозначения некоторых специальных

типов трансляторов:

Ê Ассемблер — это транслятор, у которого объектный язык представляет

собой некую разновидность машинного языка какоголибо реального

компьютера, а исходный язык, называемый языком ассемблера, или просто

ассемблером, — это, как правило, символическое представление объект

ного машинного кода. В большинстве случаев каждая инструкция на ис

ходном языке переводится в одну команду на объектном языке.

2.1. Структура и принципы работы компьютера