Архитектура компьютера - Таненбаум Э

Сюзанне, Барбаре, Марвину, Брэму и памяти моей дорогой я

Об авторе

Эндрю С. Таненбаум получил степень бакалавра естественных наук в Массачусетском технологическом институте и степень доктора в Университете Калифорнии в Беркли. В настоящее времяявляется профессором Амстердамского университета в Нидерландах, где возглавляет группу разработчиков компьютерных систем. Он также возглавляет факультет вычислительной техники (межвузовскую аспирантуру, в которой исследуются и разрабатываются системы параллельной обработки, распределенные системы и системы формирования изображения). Тем не менее он всеми силами старается не превратиться в бюрократа.

Впрошлом он занимался компиляторами, операционными системами, сетями

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

Профессор Таненбаум разрабатывает программное обеспечение. Он является главным разработчиком пакета «Amsterdam Compiler Kit» (набора инструментальных средств для написания портативных компиляторов), а также разработчиком системы MINIX (клона UNIX для студенческих лабораторий программирования). Вместе со своими учениками и программистами он участвовал в разработке системы Amoeba (это распределенная система с высокой производительностью на основе микроядра). Системы MINIX и Amoeba находятся в свободном доступе в Интернете.

Его аспиранты достигли больших высот после получения ученых степеней. Он очень гордится ими.

Профессор Таненбаум — член Ассоциации по вычислительной технике, член Института инженеров по электротехнике и электронике (IEEE), член Королевской голландской академии науки и искусства. В 1994 году получил премию от Ассоциации по вычислительной технике как выдающийся педагог. В 1997 году награжден премией от Специальной группы по образованию в области вычислительной техники (Ассоциации по вычислительной технике) за вклад в образование в области вычислительной техники. Его имя включено в справочник «Кто есть кто» («Who's Who in the World»). Его домашнюю страничку в Интернете можно найти по адресу http://www.cs.vu.nl/~ast/.

Предисловие

В основе первых трех изданий книги лежит идея о том, что компьютер можно рассматривать как иерархию уровней, каждый из которых выполняет какую-либо определенную функцию. Это фундаментальное утверждение сейчас столь же правомерно, как и в момент выхода в свет первого издания, поэтому мы по-прежнему берем его за основу, на этот раз уже в четвертом издании. Как и в первых трех изданиях, в этой книге мы подробно описываем цифровой логический уровень, уровень архитектуры команд, уровень операционной системы и уровень языка ассемблера (хотя мы изменили некоторые названия, чтобы следовать современным установившимся обычаям).

В целом структура книги осталась прежней, но в четвертое издание внесены некоторые изменения, что объясняется стремительным развитием компьютерной промышленности. Например, все программы, которые в предыдущих изданиях были написаны на языке Pascal, в четвертом издании переписаны на язык Java, чтобы продемонстрировать популярность языка Java в настоящее время. Кроме того, в качестве примеров в книге рассматриваются более современные машины (Intel Pentium II, Sun UltraSPARC II и Sun picojava II).

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

С годами книга увеличилась в объеме (хотя не так сильно, как другие популярные компьютерные издания). Это неизбежно, поскольку происходит постоянное развитие и о предмете становится известно все больше и больше. Поэтому если книга используется в целях обучения, нужно иметь в виду, что этот курс может занять более длительное время, чем раньше. Возможный вариант — изучать первые три главы, часть четвертой главы (до раздела о разработке микроархитектурного уровня включительно) и пятую главу в качестве минимума, а оставшееся время на ваше усмотрение потратить на шестую, седьмую, восьмую главы и вторую часть четвертой главы.

В четвертое издание внесены следующие изменения В главе 1 по-прежнему излагается история развития архитектуры компьютеров, но мы расширили ряд рассматриваемых машин. В главе вводятся три основных примера: Pentium II, UltraSPARC II и picojava II.

Материал второй главы обновлен и переработан. В ней мы рассматриваем современные устройства ввода-вывода: диски RAID, CD-R, DVD, цветные принтеры и т. п.

16 Предисловие

Глава 3 (цифровой логический уровень) претерпела некоторые изменения — теперь в ней рассматриваются компьютерные шины и современные устройства ввода-вывода. Главное изменение — это новый материал о шинах (в частности, PCI и USB). Три новых примера описываются на уровне микросхем.

Глава 4 (теперь она называется «Микроархитектурный уровень») была полностью переписана. Идея использовать пример микропрограммируемой машины для демонстрации работы тракта данных была сохранена, но в качестве примера взят сокращенный вариантJVM. В соответствии с этим была изменена микроархитектура. В главе продемонстрированы возможные компромиссы с точки зрения стоимости и производительности. В последнем примере, Mic-4, используется конвейер из семи стадий. Этот пример наглядно демонстрирует основные принципы работы современных компьютеров (например, Pentium II). К главе добавлен новый раздел о способах увеличения производительности, в котором рассматриваются новые технологии (кэширование, прогнозирование переходов, исполнение с изменением последовательности, спекулятивное выполнение и предикация). Новые примеры машин рассматриваются на микроархитектурном уровне.

В главе 5 (теперь она называется «Уровень архитектуры команд») рассказывается о так называемом машинном языке. В качестве основных примеров здесь используются Pentium II, UltraSPARC II и JVM.

Глава 6 (уровень операционной системы) содержит примеры операционных систем для Pentium II (Windows NT) и UltraSPARC II (UNIX). Первая операционная система сравнительно новая. Она содержит множество особенностей, которые стоит изучить. Система UNIX все еще используется во многих университетах и компаниях, и, кроме того, она довольно проста, поэтому тоже заслуживает нашеговнимания.

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

Глава 8 (архитектура компьютеров параллельного действия) полностью изменена. В ней подробно описываются мультипроцессоры (UMA, NUMA и СОМА) и мультикомпьютеры (МРР и COW).

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

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

Существует web-сайт этой книги. В Интернете имеются файлы PostScript для всех иллюстраций. Их можно получить и распечатать. Кроме того, там можно найти симулятор и другие инструментальные программные средства. Универсальный адрес ресурса: http://www.cs.vu.nl/~ast/sco4/

Симулятор и программные средства написаны Реем Онтко (Ray Ontko). Автор выражает признательность Рею за эти чрезвычайно полезные программы.

Автор искренне благодарит всех, кто читал рукопись данной книги и высказал ценные замечания и предложения или оказал какую-либо помощь, в частности Генри Бола (Henri Bal), Алана Чарльзуорта (Alan Charlesworth), Куроша Гарахор-

Предисловие 17

лоо (Koorosh Gharachorloo), Маркуса Гонкалвеса (Marcus Goncalves), Карена Панетту Ленц (Karen Panetta Lentz), Тимоти Мэттсона (Timothy Mattson), Гарлана Мак-Гана (Harlan McGhan), Майлза Мердокка (Miles Murdocca), Кэвина Нормойла (Kevin Normoyle), Майка О'Коннора (Mike O'Connor), Митсунори Огихара (Mitsunori Ogihara), Рея Онтко (Ray Ontko), Аске Плаата (Aske Plaat), Вильяма Потвина (William Potvin II), Нагарайана Прабхакарана (Nagarajan Prabhakaran), Джеймса Г. Пагсли (James H. Pugsley), Рональда Н. Шредера (RonaldN. Schroeder), Райана Шумейкера (Ryan Shoemaker), Чарльза Силио-мл. (Charles Silio,Jr.) и Дейла Скрина (Dale Skrien). Мои ученики Адриаан Бон (Adriaan Bon), Лаура де Вриес (Laura de Vries), Дольф Лот (Dolf Loth), Гуидо ван Нордент (Guido van't Noordende) помогали мне в работе над текстом, за что им большое спасибо.

Особую благодарность выражаю Джиму Гудману Qim Goodman) за его вклад в создание этой книги (в частности, четвертой и пятой глав). Идея использовать JVM принадлежит именно ему, и микроархитектура для реализации JVM тоже его. Он же предложил множество новаторских идей. Книга значительно улучшилась благодаря его содействию.

Наконец, я хотел бы поблагодарить Сюзанну за терпеливое отношение ко мне, несмотря на то, что я долгие часы проводил за своим Pentium'oM. С моей точки зрения, Pentium — более усовершенствованная машина, чем мой старый IBM-386, но с ее точки зрения никакой разницы нет. Я также хочу поблагодарить Барбару и Марвина за то, что они такие замечательные дети, а также Брэма за то, что он вел себя тихо, когда я писал эту книгу.

ЭндрюС.Таненбаум

5 6 8 0 6 9

Барнаульский Государственный Педагогический университет Научная библиотека

Глава 1

Предисловие

Цифровойкомпьютер —этомашина,котораяможетрешатьзадачи,выполняядан- ные ей команды. Последовательность команд, описывающих решение определенной задачи, называется программой. Электронные схемы каждого компьютера могут распознавать и выполнять ограниченный набор простых команд. Все программы перед выполнением должны быть превращены в последовательность таких команд, которые обычно не сложнее чем:

•сложить 2 числа;

•проверить, не является ли число нулем;

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

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

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

Так мы и назвали эту книгу. В следующем разделе мы расскажем, что понимаем под этим термином. Затем мы расскажем об истории развития этой проблемы и положении дел в настоящий момент, а также рассмотрим некоторые важные примеры.

Многоуровневая компьютерная организация

Как мы уже сказали, существует огромная разница между тем, что удобно для людей, и тем, что удобно для компьютеров. Люди хотят сделать X, но компьютеры могут сделать только Y. Из-за этого возникают проблемы. Цель данной книги — объяснить, как можно решать эти проблемы.

Многоуровневая компьютерная организация

19

Языки, уровни и виртуальные машины

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

Первый способ выполнения программы, написанной на языке Я 1, — замена каждой команды на эквивалентный набор команд в языке Я 0. В этом случае компьютер выполняет новую программу, написанную на языке Я 0, вместо старой программы, написанной на Я 1. Эта технология называется трансляцией.

Второй способ — написание программы на языке Я 0, которая берет программы, написанные на языке Я 1, в качестве входных данных, рассматривает каждую команду по очереди и сразу выполняет эквивалентный набор команд языка Я 0. Эта технология не требует составления новой программы на Я 0. Она называется интерпретацией, а программа, которая осуществляет интерпретацию, называется

интерпретатором.

Трансляция и интерпретация сходны. При применении обоих методов компьютер в конечном итоге выполняет набор команд на языке Я 0, эквивалентных командам Я 1. Различие лишь в том, что при трансляции вся программа Я 1 переделывается в программу Я 0, программа Я 1 отбрасывается, а новая программа на Я 0 загружается в память компьютера и затем выполняется.

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

Обычно гораздо проще представить себе существование гипотетического компьютера или виртуальной машины, для которой машинным языком является язык Я 1, чем думать о трансляции и интерпретации. Назовем такую виртуальную машину М 1, а виртуальную машину с языком Я 0 — М 0. Если бы такую машину М 1 можно было бы сконструировать без больших денежных затрат, язык Я 0, да и машина, которая выполняет программы на языке Я 0, были бы не нужны. Можно было бы просто писать программы на языке Я 1, а компьютер сразу бы их выполнял. Даже если виртуальная машина слишком дорога или ее очень трудно сконструировать, люди все же могут писать программы для нее. Эти программы могут транслироваться или интерпретироваться программой, написанной на языке Я 0, которая сама могла бы выполняться фактически существующим компьютером. Другими словами, можно писать программы для виртуальных машин, как будто они действительно существуют.

Чтобы трансляция и интерпретация были целесообразными, языки Я 0 и Я 1 не должны сильно различаться. Это значит, что язык Я 1 хотя и лучше, чем Я 0, но все же далек от идеала. Возможно, это несколько обескураживает в свете первоначальной цели создания языка Я 1 — освободить программиста от бремени написа-

20	Глава 1. Предисловие

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

Очевидное решение этой проблемы — создание еще одного набора команд, которые в большей степени ориентированы на человека и в меньшей степени на компьютер, чем Я 1. Этот третий набор команд также формирует язык, который мы будем называть Я 2, а соответствующую виртуальную машину — М 2. Человек может писать программы на языке Я 2, как будто виртуальная машина с машинным

ЯЗЫКОМЯ2действительносуществует.ТакиепрограммымогутилитранслироватьсянаязыкЯ1,иливыполнятьсяинтерпретатором,написаннымнаязыкеЯ1.

Изобретение целого ряда языков, каждый из которых более удобен для человека, чем предыдущий, может продолжаться до тех пор, пока мы не дойдем до подходящего нам языка. Каждый такой язык использует своего предшественника как основу, поэтому мы можем рассматривать компьютер в виде ряда уровней, как показано на рис. 1.1. Язык, находящийся в самом низу иерархической структуры — самый примитивный, а находящийся на самом верху — самый сложный.

			Программы на языке Я 1 либо
			интерпретируются программой-
	Уровень п	Виртуальная машина М л	интерпретатором, работающей
		с машинным языком Я п	на машинеболеенизкогоуровня,
			либо транслируются на машинный
			языкмашиныболеенизкогоуровня
	Уровень 3	Виртуальная машина М 3
		с машинным языком Я 3
			Программы на языке Я 1 либо
			интерпретируются программами-
	Уровень 2	Виртуальная машина М 2	интерпретаторами, работающими
			на машине М 1 или М 0, либо
		с машинным языком Я 2
			транслируются на Я 1 или Я О
			Программы на языке Я 1 либо
		Виртуальная машина М 1	интерпретируются программой-
	Уровень 1		интеопретатором, работающей
		с машинным языком Я 1	на кашине М 0, либо
			транслируются на Я О
			Программы Я 0 непосредственно
	УровеньО	Виртуальная машинаМО	выполняются электронными схемами
		с машинным языком Я О

Рис. 1.1. Многоуровневаямашина

Между языком и виртуальной машиной существует важная зависимость. У каждой машины есть какой-то определенный машинный язык, состоящий из всех команд, которые эта машина может выполнять. В сущности, машина определяет язык. Сходным образом язык определяет машину, которая может выполнять все программы, написанные на этом языке. Машину, задающуюся определенным языком, очень сложно и дорого сконструировать из электронных схем, но мы можем представитьсебе такую машину. Компьютерс машинным языком C++ или COBOL был бы слишком сложным, но его можно было бы сконструировать, если учиты-

Многоуровневая компьютерная организация

21

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

Компьютер с п уровнями можно рассматривать как п разных виртуальных машин, у каждой из которыхесть свой машинныйязык. Термины «уровень» и «виртуальная машина» мы будем использовать как синонимы. Только программы, написанные на Я 0, могут выполняться компьютером без применения трансляции и интерпретации. Программы, написанные на Я 1, Я 2,..., Я п, должны проходить через интерпретатор более низкого уровня или транслироваться на язык, соответствующий более низкому уровню.

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

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

Современные многоуровневые машины

Большинство современных компьютеров состоит из двух и более уровней. Существуют машины даже с шестью уровнями (рис. 1.2). Уровень 0 — аппаратное обеспечение машины. Его электронные схемы выполняют программы, написанные на языке уровня 1. Ради полноты нужно упомянуть о существовании еще одного уровня, расположенного ниже уровня 0. Этот уровень не показан на рис. 1.2, так как он попадает в сферу электронной техники и, следовательно, не рассматривается в этой книге. Он называется уровнем физических устройств. На этом уровне находятся транзисторы, которые являются примитивами для разработчиков компьютеров. Объяснять, как работают транзисторы, — задача физики.

На самом нижнем уровне, цифровом логическом уровне, объекты называются вентилями. Хотя вентили состоят из аналоговых компонентов, таких как транзисторы, они могут быть точно смоделированы как цифровые средства. У каждого вентиля есть одно или несколько цифровых входных данных (сигналов, представляющих 0 или 1). Вентиль вычисляет простые функции этих сигналов, такие как И или ИЛИ. Каждый вентиль формируется из нескольких транзисторов. Несколько вентилей формируют 1 бит памяти, который может содержать 0 или 1. Биты памяти, объединенные в группы, например, по 16,32 или 64,формируютрегистры. Каждый регистр может содержать одно двоичное число до определенного предела. Из вентилей также может состоять сам компьютер. Подробно вентили и цифровой логический уровень мы рассмотрим в главе 3.

22 Глава 1. Предисловие

Уровень 5	Языквысокогоуровня
	Трансляций (компилятор)
Уровень 4	Уровеньязыкаассемблера
	Трансляция (ассемблер)
Уровень 3	Уровень операционной системы
	Трансляция (ассемблер)
Уровень 2	Уровень архитектуры команд
	Интерпретация (микропрограмма)
	или непосредственное выполнение
Уровень 1	Микроархитектурный уровень
	Аппаратное обеспечение
УровеньО	Цифровой логический уровень

Рис. 1.2. Компьютер с шестью уровнями. Способ поддержки каждого уровня указан под ним. Вскобкахуказываетсяназваниеподдерживающейпрограммы

Следующий уровень — микроархитектурный уровень. На этом уровне можно видеть совокупности 8 или 32 регистров, которые формируют локальную память и схему, называемую АЛУ (арифметико-логическое устройство). АЛУ выполняет простые арифметические операции. Регистры вместе с АЛУ формируют тракт данных, по которому поступают данные. Основная операция тракта данных состоит в следующем. Выбирается один или два регистра, АЛУ производит над ними какую-либо операцию, например сложения, а результат помещается в один из этих регистров.

На некоторых машинах работа тракта данных контролируется особой программой, которая называется микропрограммой. На других машинах тракт данных контролируется аппаратными средствами. В предыдущих изданиях книги мы назвали этот уровень «уровнем микропрограммирования», потому что раньше он почти всегда был интерпретатором программного обеспечения. Поскольку сейчас тракт данных обычно контролируется аппаратным обеспечением, мы изменили название, чтобы точнее отразить смысл.

На машинах, где тракт данных контролируется программным обеспечением, микропрограмма — это интерпретатор для команд на уровне 2. Микропрограмма вызывает команды из памяти и выполняет их одну за другой, используя при этом тракт данных. Например, для того чтобы выполнить команду ADD, эта команда вызывается из памяти, ее операнды помещаются в регистры, АЛУ вычисляет сумму, а затем результат переправляется обратно. На компьютере с аппаратным контролем тракта данных происходит такая же процедура, но при этом нет программы, которая контролирует интерпретацию команд уровня 2.