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

Предисловие от издательства
Вступление
Об авторах
Глава 1
Экскурс в компьютерные системы
1.1. Информация – это биты + контекст
1.2. Программы, которые переводятся другими программами в различные формы
1.3. Как происходит компиляция
1.4. Процессоры читают и интерпретируют инструкции, хранящиеся в памяти
1.4.1. Аппаратная организация системы
1.4.2. Выполнение программы hello
1.5. Различные виды кеш-памяти
1.6. Устройства памяти образуют иерархию
1.7. Операционная система управляет работой аппаратных средств
1.7.1. Процессы
1.7.2. Потоки
1.7.3. Виртуальная память
1.7.4. Файлы
1.8. Обмен данными в сетях
1.9. Важные темы
1.9.1. Закон Амдала
1.9.2. Конкуренция и параллелизм
1.9.3. Важность абстракций в компьютерных системах
1.10. Итоги
Библиографические заметки
Решения упражнений
Часть I
Структура программы и ее выполнение
Глава 2
Представление информации и работа с ней
2.1. Хранение информации
2.1.1. Шестнадцатеричная система счисления
2.1.2. Размеры данных
2.1.3. Адресация и порядок следования байтов
2.1.4. Представление строк
2.1.5. Представление программного кода
2.1.6. Введение в булеву алгебру
2.1.7. Битовые операции в С
2.1.8. Логические операции в С
2.1.9. Операции сдвига в С
2.2. Целочисленные представления
2.2.1. Целочисленные типы
2.2.2. Представление целых без знака
2.2.3. Представление в дополнительном коде
2.2.4. Преобразования между числами со знаком и без знака
2.2.5. Числа со знаком и без знака в С
2.2.6. Расширение битового представления числа
2.2.7. Усечение чисел
2.2.8. Советы по приемам работы с числами со знаком и без знака
2.3. Целочисленная арифметика
2.3.1. Сложение целых без знака
2.3.2. Сложение целых в дополнительном коде
2.3.3. Отрицание целых в дополнительном коде
2.3.4. Умножение целых без знака
2.3.5. Умножение целых в дополнительном коде
2.3.6. Умножение на константу
2.3.7. Деление на степень двойки
2.3.8. Заключительные размышления о целочисленной арифметике
2.4. Числа с плавающей точкой
2.4.1. Дробные двоичные числа
2.4.2. Представление значений с плавающей точкой в стандарте IEEE
2.4.3. Примеры чисел
2.4.4. Округление
2.4.5. Операции с плавающей точкой
2.4.6. Значения с плавающей точкой в С
2.5. Итоги
Библиографические заметки
Домашние задания
Правила представления целых чисел на битовом уровне
Правила представления чисел с плавающей точкой на битовом уровне
Решения упражнений
Глава 3
Представление программ на машинном уровне
3.1. Историческая перспектива
3.2. Программный код
3.2.1. Машинный код
3.2.2. Примеры кода
3.2.3. Замечание по форматированию
3.3. Форматы данных
3.4. Доступ к информации
3.4.1. Спецификаторы операндов
3.4.2. Инструкции перемещения данных
3.4.3. Примеры перемещения данных
3.4.4. Вталкивание данных в стек и выталкивание из стека
3.5. Арифметические и логические операции
3.5.1. Загрузка эффективного адреса
3.5.2. Унарные и бинарные операции
3.5.3. Операции сдвига
3.5.4. Обсуждение
3.5.5. Специальные арифметические операции
3.6. Управление
3.6.1. Флаги условий
3.6.2. Доступ к флагам
3.6.3. Инструкции перехода
3.6.4. Кодирование инструкций перехода
3.6.5. Реализация условного ветвления потока управления
3.6.6. Реализация условного ветвления потока данных
3.6.7. Циклы
3.6.8. Оператор switch
3.7. Процедуры
3.7.1. Стек времени выполнения
3.7.2. Передача управления
3.7.3. Передача данных
3.7.4. Локальные переменные на стеке
3.7.5. Локальные переменные в регистрах
3.7.6. Рекурсивные процедуры
3.8. Распределение памяти под массивы и доступ к массивам
3.8.1. Базовые принципы
3.8.2. Арифметика указателей
3.8.3. Вложенные массивы
3.8.4. Массивы фиксированных размеров
3.8.5. Массивы переменных размеров
3.9. Структуры разнородных данных
3.9.1. Структуры
3.9.2. Объединения
3.9.3. Выравнивание
3.10. Комбинирование инструкций управления потоком выполнения и передачи данных в машинном коде
3.10.1. Указатели
3.10.2. Жизнь в реальном мире: использование отладчика GDB
3.10.3. Ссылки на ячейки за границами выделенной памяти и переполнение буфера
3.10.4. Предотвращение атак методом переполнения буфера
3.10.5. Поддержка кадров стека переменного размера
3.11. Вычисления с плавающей точкой
3.11.1. Операции перемещения и преобразования данных
3.11.2. Операции с плавающей точкой в процедурах
3.11.3. Арифметические операции с плавающей точкой
3.11.4. Определение и использование констант с плавающей точкой
3.11.5. Поразрядные логические операции с числами с плавающей точкой
3.11.6. Операции сравнения значений с плавающей точкой
3.11.7. Заключительные замечания об операциях с плавающей точкой
3.12. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 4
Архитектура процессора
4.1. Архитектура системы команд Y86-64
4.1.1. Состояние, видимое программисту
4.1.2. Инструкции Y86-64
4.1.3. Кодирование инструкций
4.1.4. Исключения в архитектуре Y86-64
4.1.5. Программы из инструкций Y86-64
4.1.6. Дополнительные сведения об инструкциях Y86-64
4.2. Логическое проектирование и язык HCL
4.2.1. Логические вентили
4.2.2. Комбинационные цепи и булевы выражения в HCL
4.2.3. Комбинационные цепи для слов и целочисленные выражения в HCL
4.2.4. Принадлежность множеству
4.2.5. Память и синхронизация
4.3. Последовательные реализации Y86-64 (SEQ)
4.3.1. Организация обработки в несколько этапов
4.3.2. Аппаратная реализация последовательной архитектуры SEQ
4.3.3. Синхронизация в последовательной реализации SEQ
4.3.4. Реализация этапов в последовательной версии SEQ
4.4. Общие принципы конвейерной обработки
4.4.1. Вычислительные конвейеры
4.4.2. Подробное описание работы конвейера
4.4.3. Ограничения конвейерной обработки
4.4.4. Конвейерная обработка с обратной связью
4.5. Конвейерные реализации Y86-64
4.5.1. SEQ+: переупорядочение этапов обработки
4.5.2. Добавление конвейерных регистров
4.5.3. Переупорядочение сигналов и изменение их маркировки
4.5.4. Прогнозирование следующего значения PC
4.5.5. Риски конвейерной обработки
4.5.6. Обработка исключений
4.5.7. Реализация этапов в PIPE
4.5.8. Управляющая логика конвейера
4.5.9. Анализ производительности
4.5.10. Незаконченная работа
4.6. Итоги
4.6.1. Имитаторы Y86-64
Библиографические заметки
Домашние задания
Решения упражнений
Глава 5
Оптимизация производительности программ
5.1. Возможности и ограничения оптимизирующих компиляторов
5.2. Выражение производительности программы
5.3. Пример программы
5.4. Устранение неэффективностей в циклах
5.5. Сокращение вызовов процедур
5.6. Устранение избыточных ссылок на память
5.7. Общее описание современных процессоров
5.7.1. Общие принципы функционирования
5.7.2. Производительность функционального блока
5.7.3. Абстрактная модель работы процессора
5.8. Развертывание циклов
5.9. Увеличение степени параллелизма
5.9.1. Несколько аккумуляторов
5.9.2. Переупорядочение операций
5.10. Обобщение результатов оптимизации комбинирующего кода
5.11. Некоторые ограничивающие факторы
5.11.1. Вытеснение регистров
5.11.2. Прогнозирование ветвлений и штрафы за ошибки предсказания
5.12. Понятие производительности памяти
5.12.1. Производительность операций загрузки
5.12.2. Производительность операций сохранения
5.13. Жизнь в реальном мире: методы повышения производительности
5.14. Выявление и устранение узких мест производительности
5.14.1. Профилирование программ
5.14.2. Использование профилировщика при выборе кода для оптимизации
5.15. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 6
Иерархия памяти
6.1. Технологии хранения информации
6.1.1. Память с произвольным доступом
6.1.2. Диски
6.1.3. Твердотельные диски
6.1.4 Тенденции развития технологий хранения
6.2. Локальность
6.2.1. Локальность обращений к данным программы
6.2.2. Локальность выборки инструкций
6.2.3. В заключение о локальности
6.3. Иерархия памяти
6.3.1. Кеширование в иерархии памяти
6.3.2. В заключение об иерархии памяти
6.4. Кеш-память
6.4.1. Обобщенная организация кеш-памяти
6.4.2. Кеш с прямым отображением
6.4.3. Ассоциативные кеши
6.4.4. Полностью ассоциативные кеши
6.4.5. Проблемы с операциями записи
6.4.6. Устройство реальной иерархии кешей
6.4.7. Влияние параметров кеша на производительность
6.5. Разработка программ, эффективно использующих кеш
6.6. Все вместе: влияние кеша на производительность программ
6.6.1. Гора памяти
6.6.2. Переупорядочение циклов для улучшения пространственной локальности
6.6.3. Использование локальности в программах
6.7. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Часть II
Выполнение программ в системе
Глава 7
Связывание
7.1. Драйверы компиляторов
7.2. Статическое связывание
7.3. Объектные файлы
7.4. Перемещаемые объектные файлы
7.5. Идентификаторы и таблицы имен
7.6. Разрешение ссылок
7.6.1. Как компоновщик разрешает ссылки на повторяющиеся имена
7.6.2. Связывание со статическими библиотеками
7.6.3. Как компоновщики разрешают ссылки на статические библиотеки
7.7. Перемещение
7.7.1. Записи перемещения
7.7.2. Перемещение ссылок
7.8. Выполняемые объектные файлы
7.9. Загрузка выполняемых объектных файлов
7.10. Динамическое связывание с разделяемыми библиотеками
7.11. Загрузка и связывание с разделяемыми библиотеками из приложений
7.12. Перемещаемый программный код
7.13. Подмена библиотечных функций
7.13.1. Подмена во время компиляции
7.13.2. Подмена во время компоновки
7.13.3. Подмена во время выполнения
7.14. Инструменты управления объектными файлами
7.15. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 8
Управление исключениями
8.1. Исключения
8.1.1. Обработка исключений
8.1.2. Классы исключений
8.1.3. Исключения в системах Linux/x86-64
8.2. Процессы
8.2.1. Логический поток управления
8.2.2. Конкурентные потоки управления
8.2.3. Изолированное адресное пространство
8.2.4. Пользовательский и привилегированный режимы
8.2.5. Переключение контекста
8.3. Системные вызовы и обработка ошибок
8.4. Управление процессами
8.4.1. Получение идентификатора процесса
8.4.2. Создание и завершение процессов
8.4.3. Утилизация дочерних процессов
8.4.4. Приостановка процессов
8.4.5. Загрузка и запуск программ
8.4.6. Запуск программ с помощью функций fork и execve
8.5. Сигналы
8.5.1. Терминология сигналов
8.5.2. Посылка сигналов
8.5.3. Получение сигналов
8.5.4. Блокировка и разблокировка сигналов
8.5.5. Обработка сигналов
8.5.6. Синхронизация потоков во избежание неприятных ошибок конкурентного выполнения
8.5.7. Явное ожидание сигналов
8.6. Нелокальные переходы
8.7. Инструменты управления процессами
8.8. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 9
Виртуальная память
9.1. Физическая и виртуальная адресация
9.2. Пространства адресов
9.3. Виртуальная память как средство кеширования
9.3.1. Организация кеша DRAM
9.3.2. Таблицы страниц
9.3.3. Попадание в кеш DRAM
9.3.4. Промах кеша DRAM
9.3.5. Размещение страниц
9.3.6. И снова о локальности
9.4. Виртуальная память как средство управления памятью
9.5. Виртуальная память как средство защиты памяти
9.6. Преобразование адресов
9.6.1. Интегрирование кешей и виртуальной памяти
9.6.2. Ускорение трансляции адресов с помощью TLB
9.6.3. Многоуровневые таблицы страниц
9.6.4. Все вместе: сквозное преобразование адресов
9.7. Практический пример: система памяти Intel Core i7/Linux
9.7.1. Преобразование адресов в Core i7
9.7.2. Система виртуальной памяти Linux
9.8. Отображение в память
9.8.1. И снова о разделяемых объектах
9.8.2. И снова о функции fork
9.8.3. И снова о функции execve
9.8.4. Отображение в память на уровне пользователя с помощью функции mmap
9.9. Динамическое распределение памяти
9.9.1. Функции malloc и free
9.9.2. Что дает динамическое распределение памяти
9.9.3. Цели механизмов распределения памяти и требования к ним
9.9.4. Фрагментация
9.9.5. Вопросы реализации
9.9.6. Неявные списки свободных блоков
9.9.7. Размещение распределенных блоков
9.9.8. Разбиение свободных блоков
9.9.9. Увеличение объема динамической памяти
9.9.10. Объединение свободных блоков
9.9.11. Объединение с использованием граничных тегов
9.9.12. Все вместе: реализация простого механизма распределения памяти
9.9.13. Явные списки свободных блоков
9.9.14. Раздельные списки свободных блоков
9.10. Сборка мусора
9.10.1. Основы сборки мусора
9.10.2. Алгоритм сборки мусора Mark&Sweep
9.10.3. Консервативный алгоритм Mark&Sweep для программ на C
9.11. Часто встречающиеся ошибки
9.11.1. Разыменование недопустимых указателей
9.11.2. Чтение неинициализированной области памяти
9.11.3. Переполнение буфера на стеке
9.11.4. Предположение о равенстве размеров указателей и объектов, на которые они указывают
9.11.5. Ошибки занижения или завышения на единицу
9.11.6. Ссылка на указатель вместо объекта
9.11.7. Неправильное понимание арифметики указателей
9.11.8. Ссылки на несуществующие переменные
9.11.9. Ссылка на данные в свободных блоках
9.11.10. Утечки памяти
9.12. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Часть III
Взаимодействие программ
Глава 10
Системный уровень ввода/вывода
10.1. Ввод/вывод в Unix
10.2. Файлы
10.3. Открытие и закрытие файлов
10.4. Чтение и запись файлов
10.5. Надежные чтение и запись с помощью пакета RIO
10.5.1. Функции RIO небуферизованного ввода/вывода
10.5.2. Функции RIO буферизованного ввода
10.6. Чтение метаданных файла
10.7. Чтение содержимого каталога
10.8. Совместное использование файлов
10.9. Переадресация ввода/вывода
10.10. Стандартный ввод/вывод
10.11. Все вместе: какие функции ввода/вывода использовать?
10.12. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 11
Сетевое программирование
11.1. Программная модель клиент–сервер
11.2. Компьютерные сети
11.3. Всемирная сеть интернет
11.3.1. IP-адреса
11.3.2. Доменные имена интернета
11.3.3. Интернет-соединения
11.4. Интерфейс сокетов
11.4.1. Структуры адресов сокетов
11.4.2. Функция socket
11.4.3. Функция connect
11.4.4. Функция bind
11.4.5. Функция listen
11.4.6. Функция accept
11.4.7. Преобразование имен хостов и служб
11.4.8. Вспомогательные функции для интерфейса сокетов
11.4.9. Примеры эхо-клиента и эхо-сервера
11.5. Веб-серверы
11.5.1. Основные сведения о вебе
11.5.2. Веб-контент
11.5.3. Транзакции HTTP
11.5.4. Обслуживание динамического контента
11.6. Все вместе: разработка небольшого веб-сервера TINY
11.7. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Глава 12
Конкурентное программирование
12.1. Конкурентное программирование с процессами
12.1.1. Конкурентный сервер, основанный на процессах
12.1.2. Достоинства и недостатки подхода на основе процессов
12.2. Конкурентное программирование с мультиплексированием ввода/вывода
12.2.1. Конкурентный на основе мультиплексирования ввода/вывода, управляемый событиями
12.2.2. Достоинства и недостатки мультиплексирования ввода/вывода
12.3. Конкурентное программирование с потоками выполнения
12.3.1. Модель выполнения многопоточных программ
12.3.2. Потоки Posix
12.3.3. Создание потоков
12.3.4. Завершение потоков
12.3.5. Утилизация завершившихся потоков
12.3.6. Обособление потоков
12.3.7. Инициализация потоков
12.3.8. Конкурентный многопоточный сервер
12.4. Совместное использование переменных несколькими потоками выполнения
12.4.1. Модель памяти потоков
12.4.2. Особенности хранения переменных в памяти
12.4.3. Совместно используемые переменные
12.5. Синхронизация потоков выполнения с помощью семафоров
12.5.1. Граф выполнения
12.5.2. Семафоры
12.5.3. Использование семафоров для исключительного доступа к ресурсам
12.5.4. Использование семафоров для организации совместного доступа к ресурсам
12.5.5. Все вместе: конкурентный сервер на базе предварительно созданных потоков
12.6. Использование потоков выполнения для организации параллельной обработки
12.7. Другие вопросы конкурентного выполнения
12.7.1. Безопасность в многопоточном окружении
12.7.2. Реентерабельность
12.7.3. Использование библиотечных функций в многопоточных программах
12.7.4. Состояние гонки
12.7.5. Взаимоблокировка (тупиковые ситуации)
12.8. Итоги
Библиографические заметки
Домашние задания
Решения упражнений
Приложение A
Обработка ошибок
A.1. Обработка ошибок в системе Unix
A.2. Функции-обертки обработки ошибок
Библиография
Предметный указатель