Компьютерные системы: архитектура и программирование

Рэндал Э. Брайант 
Дэвид Р. О'Халларон

Компьютерные системы:

архитектура и программирование

3-е издание

Computer Systems
A Programmer’s Perspective

Third edition

Randal E. Bryant
Carnegie Mellon University

David R. O’Hallaron
Carnegie Mellon University

Москва, 2022

Компьютерные системы: 
архитектура и программирование

3-е издание

Рэндал Э. Брайант 
университет Карнеги–Меллона

Дэвид Р. О'Халларон
университет Карнеги–Меллона

УДК  004.2
ББК  32.972
Б87

Б87   Рэндал Э. Брайант, Дэвид Р. О'Халларон
Компьютерные системы: архитектура и программирование. 3-е изд. / 
пер. с англ. А. Н. Киселева. – М.: ДМК Пресс, 2022. – 994 с.: ил.

         ISBN 978-5-97060-492-2

В книге описываются стандартные элементы архитектуры, такие как центральный процессор, память, порты ввода-вывода, а также операционная система, компилятор, компоновщик и сетевое окружение. Демонст рируются способы 
представления данных и программ на машинном уровне, приемы оптимизации 
программ, особенности управления потоками выполнения и виртуальной памятью, а также методы сетевого и параллельного программирования. Приведенные в книге примеры для процессоров, совместимых с Intel (x86_64), написаны 
на языке C и выполняются в операционной системе Linux.
Издание адресовано студентам и преподавателям по IT-специальностям, 
а также будет полезно разработчикам, желающим повысить свой профессиональный уровень и писать программы, эффективно использующие возможности компьютерной архитектуры.

Authorized translation from the English language edition, entitled Computer Systems: 
A Programmer’s Perspective, 3rd Edition, by Randal E. Bryant and David R. O’Hallaron, published 
by Pearson Education, Inc, publishing as Pearson, Copyright © 2016.

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

ISBN 978-0-13-409266-9 (англ.) 
 Copyright © 2016, 2011, and 2003 by  
 Randal E. Bryant and David R. O'Hallaron, 2021
ISBN 978-5-97060-492-2 (рус.) 
 © Оформление, перевод на русский язык, 

   издание, ДМК Пресс, 2022

Cтудентам и преподавателям курса 15-213  
университета Карнеги–Меллона, вдохновившим  
нас на переработку и уточнение этого издания

Оглавление

Предисловие от издательства ..................................................................... 17
Вступление .................................................................................................... 18
Об авторах ..................................................................................................... 34

Глава 1. Экскурс в компьютерные системы ............................................... 36

1.1. Информация – это биты + контекст ..........................................................38
1.2. Программы, которые переводятся другими программами  
в различные формы ...................................................................................39

1.3. Как происходит компиляция ....................................................................41
1.4. Процессоры читают и интерпретируют инструкции, хранящиеся 
в памяти ......................................................................................................42
1.4.1. Аппаратная организация системы ..............................................................42
1.4.2. Выполнение программы hello .....................................................................44

1.5. Различные виды кеш-памяти ...................................................................46
1.6. Устройства памяти образуют иерархию ...................................................47
1.7. Операционная система управляет работой аппаратных средств ...........48

1.7.1. Процессы .......................................................................................................49
1.7.2. Потоки ............................................................................................................50
1.7.3. Виртуальная память ......................................................................................51
1.7.4. Файлы .............................................................................................................53

1.8. Обмен данными в сетях .............................................................................53
1.9. Важные темы ..............................................................................................55

1.9.1. Закон Амдала ................................................................................................56
1.9.2. Конкуренция и параллелизм .......................................................................57
1.9.3. Важность абстракций в компьютерных системах ......................................60

1.10. Итоги .........................................................................................................61

Библиографические заметки.................................................................................61
Решения упражнений ............................................................................................61

Часть I  
Структура программы и ее выполнение ................................................... 63

Глава 2. Представление информации и работа с ней ............................... 64

2.1. Хранение информации ..............................................................................68

2.1.1. Шестнадцатеричная система счисления .....................................................68
2.1.2. Размеры данных ...........................................................................................71
2.1.3. Адресация и порядок следования байтов ...................................................74
2.1.4. Представление строк ....................................................................................80
2.1.5. Представление программного кода ............................................................81
2.1.6. Введение в булеву алгебру ...........................................................................82
2.1.7. Битовые операции в С ..................................................................................85
2.1.8. Логические операции в С .............................................................................87

Оглавление  7

2.1.9. Операции сдвига в С .....................................................................................88

2.2. Целочисленные представления ................................................................90

2.2.1. Целочисленные типы ...................................................................................91
2.2.2. Представление целых без знака ..................................................................92
2.2.3. Представление в дополнительном коде ......................................................94
2.2.4. Преобразования между числами со знаком и без знака ............................99
2.2.5. Числа со знаком и без знака в С .................................................................104
2.2.6. Расширение битового представления числа ............................................106
2.2.7. Усечение чисел ............................................................................................109
2.2.8. Советы по приемам работы с числами со знаком и без знака ................111

2.3. Целочисленная арифметика ...................................................................113

2.3.1. Сложение целых без знака .........................................................................113
2.3.2. Сложение целых в дополнительном коде .................................................118
2.3.3. Отрицание целых в дополнительном коде ...............................................123
2.3.4. Умножение целых без знака ......................................................................124
2.3.5. Умножение целых в дополнительном коде ..............................................124
2.3.6. Умножение на константу............................................................................128
2.3.7. Деление на степень двойки ........................................................................130
2.3.8. Заключительные размышления о целочисленной арифметике .............134

2.4. Числа с плавающей точкой ......................................................................135

2.4.1. Дробные двоичные числа ...........................................................................136
2.4.2. Представление значений с плавающей точкой в стандарте IEEE ...........139
2.4.3. Примеры чисел ...........................................................................................141
2.4.4. Округление ..................................................................................................146
2.4.5. Операции с плавающей точкой .................................................................148
2.4.6. Значения с плавающей точкой в С ............................................................150

2.5. Итоги .........................................................................................................151

Библиографические заметки...............................................................................152
Домашние задания ...............................................................................................153
Правила представления целых чисел на битовом уровне ................................154
Правила представления чисел с плавающей точкой на битовом уровне ........165
Решения упражнений ..........................................................................................167

Глава 3. Представление программ на машинном уровне .......................184

3.1. Историческая перспектива .....................................................................187
3.2. Программный код ....................................................................................190

3.2.1. Машинный код ............................................................................................190
3.2.2. Примеры кода .............................................................................................192
3.2.3. Замечание по форматированию ................................................................195

3.3. Форматы данных ......................................................................................197
3.4. Доступ к информации .............................................................................198

3.4.1. Спецификаторы операндов .......................................................................200
3.4.2. Инструкции перемещения данных ...........................................................201
3.4.3. Примеры перемещения данных ................................................................205
3.4.4. Вталкивание данных в стек и выталкивание из стека .............................208

3.5. Арифметические и логические операции ..............................................209

 Оглавление

3.5.1. Загрузка эффективного адреса ..................................................................210
3.5.2. Унарные и бинарные операции .................................................................212
3.5.3. Операции сдвига .........................................................................................212
3.5.4. Обсуждение .................................................................................................213
3.5.5. Специальные арифметические операции ................................................215

3.6. Управление ...............................................................................................218

3.6.1. Флаги условий .............................................................................................218
3.6.2. Доступ к флагам ..........................................................................................219
3.6.3. Инструкции перехода .................................................................................222
3.6.4. Кодирование инструкций перехода ..........................................................223
3.6.5. Реализация условного ветвления потока управления .............................225
3.6.6. Реализация условного ветвления потока данных ....................................229
3.6.7. Циклы ...........................................................................................................235
3.6.8. Оператор switch ..........................................................................................245

3.7. Процедуры ................................................................................................250

3.7.1. Стек времени выполнения .........................................................................251
3.7.2. Передача управления ..................................................................................252
3.7.3. Передача данных .........................................................................................256
3.7.4. Локальные переменные на стеке ...............................................................258
3.7.5. Локальные переменные в регистрах .........................................................260
3.7.6. Рекурсивные процедуры ............................................................................262

3.8. Распределение памяти под массивы и доступ к массивам ...................264

3.8.1. Базовые принципы .....................................................................................264
3.8.2. Арифметика указателей .............................................................................266
3.8.3. Вложенные массивы ...................................................................................267
3.8.4. Массивы фиксированных размеров ..........................................................268
3.8.5. Массивы переменных размеров ................................................................271

3.9. Структуры разнородных данных ............................................................273

3.9.1. Структуры ....................................................................................................273
3.9.2. Объединения ...............................................................................................276
3.9.3. Выравнивание .............................................................................................279

3.10. Комбинирование инструкций управления потоком выполнения 
и передачи данных в машинном коде ....................................................282
3.10.1. Указатели ...................................................................................................283
3.10.2. Жизнь в реальном мире: использование отладчика GDB......................284
3.10.3. Ссылки на ячейки за границами выделенной памяти  
и переполнение буфера ..............................................................................286

3.10.4. Предотвращение атак методом переполнения буфера .........................290
3.10.5. Поддержка кадров стека переменного размера .....................................295

3.11. Вычисления с плавающей точкой .........................................................298

3.11.1. Операции перемещения и преобразования данных .............................300
3.11.2. Операции с плавающей точкой в процедурах ........................................305
3.11.3. Арифметические операции с плавающей точкой ..................................305
3.11.4. Определение и использование констант с плавающей точкой .............307
3.11.5. Поразрядные логические операции с числами с плавающей точкой ...308
3.11.6. Операции сравнения значений с плавающей точкой ............................309

Оглавление  9

3.11.7. Заключительные замечания об операциях с плавающей точкой ..........312

3.12. Итоги .......................................................................................................312

Библиографические заметки...............................................................................313
Домашние задания ...............................................................................................314
Решения упражнений ..........................................................................................325

Глава 4. Архитектура процессора ..............................................................349

4.1. Архитектура системы команд Y86-64 .....................................................352

4.1.1. Состояние, видимое программисту ..........................................................352
4.1.2. Инструкции Y86-64 .....................................................................................353
4.1.3. Кодирование инструкций ..........................................................................355
4.1.4. Исключения в архитектуре Y86-64 ............................................................360
4.1.5. Программы из инструкций Y86-64 ............................................................361
4.1.6. Дополнительные сведения об инструкциях Y86-64 .................................366

4.2. Логическое проектирование и язык HCL ...............................................368

4.2.1. Логические вентили ...................................................................................368
4.2.2. Комбинационные цепи и булевы выражения в HCL ................................369
4.2.3. Комбинационные цепи для слов и целочисленные выражения в HCL ...371
4.2.4. Принадлежность множеству ......................................................................375
4.2.5. Память и синхронизация ...........................................................................375

4.3. Последовательные реализации Y86-64 (SEQ) ........................................378

4.3.1. Организация обработки в несколько этапов ............................................378
4.3.2. Аппаратная реализация последовательной архитектуры SEQ ...............387
4.3.3. Синхронизация в последовательной реализации SEQ ............................391
4.3.4. Реализация этапов в последовательной версии SEQ ...............................394

4.4. Общие принципы конвейерной обработки ...........................................402

4.4.1. Вычислительные конвейеры ......................................................................402
4.4.2. Подробное описание работы конвейера ...................................................404
4.4.3. Ограничения конвейерной обработки ......................................................406
4.4.4. Конвейерная обработка с обратной связью ..............................................408

4.5. Конвейерные реализации Y86-64 ...........................................................409

4.5.1. SEQ+: переупорядочение этапов обработки .............................................409
4.5.2. Добавление конвейерных регистров .........................................................411
4.5.3. Переупорядочение сигналов и изменение их маркировки .....................415
4.5.4. Прогнозирование следующего значения PC ............................................416
4.5.5. Риски конвейерной обработки ..................................................................418
4.5.6. Обработка исключений ..............................................................................431
4.5.7. Реализация этапов в PIPE ...........................................................................434
4.5.8. Управляющая логика конвейера ................................................................441
4.5.9. Анализ производительности .....................................................................451
4.5.10. Незаконченная работа ..............................................................................454

4.6. Итоги .........................................................................................................457

4.6.1. Имитаторы Y86-64 ......................................................................................458
Библиографические заметки...............................................................................458
Домашние задания ...............................................................................................459
Решения упражнений ..........................................................................................465

 Оглавление

Глава 5. Оптимизация производительности программ ..........................478

5.1. Возможности и ограничения оптимизирующих компиляторов ..........481
5.2. Выражение производительности программы .......................................484
5.3. Пример программы .................................................................................486
5.4. Устранение неэффективностей в циклах ...............................................490
5.5. Сокращение вызовов процедур ..............................................................493
5.6. Устранение избыточных ссылок на память ...........................................495
5.7. Общее описание современных процессоров .........................................498

5.7.1. Общие принципы функционирования ......................................................498
5.7.2. Производительность функционального блока .........................................502
5.7.3. Абстрактная модель работы процессора ...................................................504

5.8. Развертывание циклов ............................................................................510
5.9. Увеличение степени параллелизма ........................................................514

5.9.1. Несколько аккумуляторов ..........................................................................515
5.9.2. Переупорядочение операций ........................................................520

5.10. Обобщение результатов оптимизации комбинирующего кода .........524
5.11. Некоторые ограничивающие факторы.................................................525

5.11.1. Вытеснение регистров ..............................................................................525
5.11.2. Прогнозирование ветвлений и штрафы за ошибки предсказания .......526

5.12. Понятие производительности памяти .................................................530

5.12.1. Производительность операций загрузки ................................................530
5.12.2. Производительность операций сохранения ...........................................531

5.13. Жизнь в реальном мире: методы повышения производительности .537
5.14. Выявление и устранение узких мест производительности ................538

5.14.1. Профилирование программ .....................................................................538
5.14.2. Использование профилировщика при выборе кода для оптимизации 540

5.15. Итоги .......................................................................................................544

Библиографические заметки...............................................................................545
Домашние задания ...............................................................................................545
Решения упражнений ..........................................................................................548

Глава 6. Иерархия памяти ..........................................................................553

6.1. Технологии хранения информации ........................................................554

6.1.1. Память с произвольным доступом ............................................................554
6.1.2. Диски ...........................................................................................................562
6.1.3. Твердотельные диски .................................................................................572
6.1.4 Тенденции развития технологий хранения ...............................................574

6.2. Локальность ..............................................................................................577

6.2.1. Локальность обращений к данным программы .......................................577
6.2.2. Локальность выборки инструкций ............................................................579
6.2.3. В заключение о локальности ......................................................................579

6.3. Иерархия памяти .....................................................................................581

6.3.1. Кеширование в иерархии памяти..............................................................582
6.3.2. В заключение об иерархии памяти ...........................................................585

6.4. Кеш-память ..............................................................................................586