Теория цифрового компьютера

ТЕОРИЯ ЦИФРОВОГО 

КОМПЬЮТЕРА

А.Б. БАРСКИЙ
В.В. ШИЛОВ

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано в качестве учебного пособия для студентов высших учебных 

заведений, обучающихся по направлениям подготовки 09.03.01 «Информатика 

и вычислительная техника», 09.03.02 «Информационные системы и техно
логии», 38.03.05 «Бизнес-информатика» (квалификация (степень) «бакалавр»)

Москва 

ИД «ФОРУМ» — ИНФРА-М

2019

УДК 004(075.8)
ББК 32.973я73
 
Б26

Барский А.Б.

Б26 
 
Теория цифрового компьютера : учеб. пособие / А.Б. Барский, 

В.В. Шилов. — М. : ИД «ФОРУМ» : ИНФРА-М, 2019. — 304 с. — (Высшее образование: Бакалавриат). — www.dx.doi.org/10.12737/textbook_5a
1e59238818d1.87944346.

ISBN 978-5-8199-0774-0 (ИД «ФОРУМ»)
ISBN 978-5-16-013103-0 (ИНФРА-М, print)
ISBN 978-5-16-105887-9 (ИНФРА-М, online)
Исследованы проблемы типизации и структуризации данных. Введено опре
деление алгоритма, отражающее важное свойство альтернативности. В классической теории алгоритмов выделены положения, обеспечивающие два принципа 
современного цифрового компьютера: программное управление выполнением 
программы и размещение выполняемой программы в памяти наряду с другими данными. Рассмотрены возможные структуры алгоритмов, алгоритмически 
неразрешимые проблемы, сложность алгоритмов, абстрактные модели компьютеров. Изучены логические основы компьютера, способы представления 
и преобразования данных в различных системах счисления и выполнение базовых арифметических и логических операций. Исследованы возможности параллельного выполнения операций. Приведены функции операционной системы 
по обеспечению режимов использования компьютера, системы прерывания, 
многоканального доступа, виртуальной памяти. Дано понятие «теговой» архитектуры, способствующей повышению информационной безопасности. Рассмотрены «фон-Неймановские» и «не-фон-Неймановские» архитектуры.

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

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

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

УДК 004(075.8)
ББК 32.973я73

Р е ц е н з е н т ы:

Л.Г. Гагарина, доктор технических наук, профессор, заведующая 

кафедрой «Информатика и программное обеспечение вычислительных систем» Национального исследовательского университета «Московский институт электронной техники»;

С.А. Инютин, доктор технических наук, профессор, ведущий науч
ный сотрудник 25-го Государственного НИИ Министерства обороны 
Российской Федерации

А в т о р ы:

Аркадий Бенционович Барский, доктор технических наук, профессор кафедры 

«Вычислительные системы и сети» ФГБОУ ВО «Московский государственный 
университет путей сообщения»;

Валерий Владимирович Шилов, кандидат технических наук, заведующий ка
федрой «Проектирование вычислительных комплексов» ФГБОУ ВО «Московский авиационный институт (национальный исследовательский университет)»

ISBN 978-5-8199-0774-0 (ИД «ФОРУМ»)
ISBN 978-5-16-013103-0 (ИНФРА-М, print)
ISBN 978-5-16-105887-9 (ИНФРА-М, online)

© Барский А.Б., Шилов В.В., 2018
© ИД «ФОРУМ», 2018

Памяти 
Всеволода Сергеевича Бурцева

Предисловие

В 1993 г. В.С. Бурцев, главный конструктор многопроцессорных 
вычислительных комплексов «Эльбрус», основал кафедру «Проектирование вычислительных комплексов» в Российском государственном технологическом университете им. К.Э. Циолковского. 
Многопроцессорный вычислительный комплекс (МВК) «Эльбрус» 
явился главным высокопроизводительным средством 1970-х — 
1980-х гг., позволившим решить основные вычислительные 
проблемы того времени — ядерной физики, космических исследований и противоракетной обороны.
В основу обучения по программе бакалавриата был положен 
стандарт ACM/IEEE Computing Curriculum 1991. Теория должна была 
взвешенно сочетаться с практическими навыками, так как бакалавры призваны пополнять инженерный корпус. Всеволод Сергеевич стремился сконцентрировать необходимый объем знаний, 
которым должен обладать пользователь и разработчик передовой 
вычислительной техники.
Авторы настоящей книги активно участвовали в наполнении 
принятой программы учебным материалом. Представлению базовой частицы сформированных знаний посвящено это учебное 
пособие.
Данное пособие содержит три раздела. В первом разделе освещены структуры и типы данных; во втором — рассмотрены основные положения теории алгоритмов, в свете которой обосновываются логические и арифметические начала цифрового компьютера; в третьем — изложены операционные основы цифрового 
компьютера и его операционной системы низшего уровня.
Учебное пособие предназначено для студентов всех курсов, 
включая магистерскую подготовку, для аспирантов и преподавателей информационно-технологических и экономических специальностей, а также предоставляет важный научный материал 
для обоснования и разработки вычислительных средств в составе 
сложных информационных и управляющих систем.

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

Введение

Компьютер (ЭВМ) — всего лишь машина, аппаратура, воспроизводящая некоторые (!) интеллектуальные возможности человека. 
Для того чтобы она могла работать и давать определенные, однозначные результаты и даже для того, чтобы ее вообще можно было 
построить, необходима формализация как всех ее действий, так 
и объектов, над которыми эти действия совершаются. Если вы сказали: «сделай то-то, а может быть — совсем другое, и я не знаю, что 
я тебе для этого сообщаю — число или букву», то для машины это 
будет выглядеть, как для вас — «Поди туда, не знаю куда. Принеси 
то, не знаю что».
Значит, чтобы машина могла действовать, и действовать формально, вы должны формализовать всю информацию для ее действий и выработать этот формализм вместе с ней. Именно тогда 
вы сможете не только правильно решать задачи, но и построить 
машину, которая на аппаратном уровне будет поддерживать предусмотренный формализм.
Что же лежит в основе этого формализма? При здравом рассуждении мы приходим к выводу, что должен быть четко определен 
свод правил трех видов:
1) что, какие объекты воспринимает и обрабатывает компьютер;
2) как он это делает на формальном уровне;
3) как это на принципиальном уровне реализовать аппаратно.
Эти три проблемы и определяют содержание данного курса. 
Прокомментируем их отдельно. Расширяется область применения 
компьютеров. Происходят определенные изменения во времени. 
Можно отметить бурное развитие информационных систем на основе сетевых технологий. С появлением новых задач возрастает актуальность типизации данных. Сейчас мы знаем много задач, каждая 
из которых предполагает характерный вид информации, способ ее 
организации, специфические правила преобразования. Этот вид 
и определяет тип данных.
Типы данных, составляющих базу данных, отличаются от типов 
данных, составляющих программный файл. Составляя матрицу 
и предполагая операции над ней, мы тем самым предполагаем тип 
данных — ее элементов. И этот тип отличен, например, от того типа 
данных, который соответствует графовой или списковой структуре. 
Наконец, нам нужно отличать данные, являющиеся значениями 

булевой функции, от данных, являющихся значениями тригонометрической функции, и т.д.
Каковы же цели этого различия? Отметим главные.
Первая из них — предусмотреть на уровне аппаратуры операции для обработки данных определенных типов, или, как говорят, обеспечить аппаратную поддержку обработки данных определенных типов, т.е. ускорить и облегчить эту обработку исходя 
из специфики данных. Например, если компьютер предназначен 
для обработки базы данных, то основной тип данных, которыми 
он оперирует, — записи. Записи образуют массивы. Значит, если 
на уровне аппаратуры продумать обработку этих типов, введя на 
основе реляционного исчисления специальные команды, можно 
повысить оперативность ответов на запросы к базе данных, ее изменение и дополнение. Тем самым мы повысим эффективность 
применяемых вычислительных средств.
Вторая важная цель типизации — типовый контроль данных. 
Каждый тип данных предполагает ограничение на операции, допустимые над данными этого типа. Это делает возможным создание различных видов контроля обработки данных, включая контекстную защиту данных.
Появление новых задач, развитие алгоритмических языков 
и трансляторов, требования к удобству программирования привели к возможности конструирования новых типов данных по желанию пользователя. Это позволяет структурировать программу 
и ее данные, повышает эффективность трансляции.
Отметим важный факт: типизация данных распространяется на 
абстрактный уровень. Абстрактные типы данных позволяют обеспечивать машинную независимость. Это означает, что можно проектировать модели данных до того, как вы выбрали компьютер для 
разрабатываемой системы.
Проблема, заключающаяся в том, как обрабатывать данные, породила важный раздел информатики — теорию алгоритмов.
Представленная в книге теория алгоритмов лишена надуманности. Объекты исследования выверены в соответствии с тем, что 
получило жизнь, т.е., что на деле реализовано в современном цифровом компьютере с учетом решаемых им задач. Прежде всего, это 
касается самого определения алгоритма, которое кратко может быть 
сформулировано следующим образом. 
Алгоритм — целенаправленная совокупность предписаний, 
обеспечивающая выбор альтернативной последовательности действий, ведущих к результату.
Для компьютерных алгоритмов целенаправленная совокупность 
предписаний — это программа на алгоритмическом языке. Альтер

нативная последовательность действий складывается в процессе 
выполнения программы с помощью «машинного» языка в зависимости от исходных и оперативных данных.
Таким образом, данное определение связывает статику описания алгоритма с динамикой его выполнения. Оно отображает 
такое важное свойство алгоритма, как альтернативность.
Альтернативность алгоритмов и кажущаяся непредсказуемость 
их действий породили интересную проблему, обсуждавшуюся на 
рубеже 1950–1960-х гг.: «Может ли машина мыслить?» «Может! — 
отвечаем мы, — если реализует алгоритм мышления». Эта же особенность алгоритмов определила важную задачу минимизации количества и времени выполнения условных переходов в программах 
высокопроизводительных вычислительных систем в наши дни.
Наряду с разбором базовых структур алгоритмов особое внимание в последние десятилетия стали уделять их реализуемости. 
Здесь отметим два аспекта: алгоритмическую разрешимость и сложность. Существуют алгоритмически неразрешимые задачи, что необходимо учитывать в практической деятельности, а исследование 
сложности алгоритмов приводит к обескураживающим выводам 
о допустимых границах используемых данных. Например, получившие законное признание как объективно существующие, а не 
как результат неудачного поиска алгоритма, методы решения задач, 
основанные на переборе, приводят к фантастическим оценкам времени их решения на самых современных компьютерах даже при 
небольших значениях основного параметра. Для многих простой 
расчет сложности как времени перебора явился неожиданным. 
Поэтому, выбирая значения параметров, таких как размерность задачи, следует задавать себе вопрос: а не собираюсь ли я сымитировать решение алгоритмически неразрешимой проблемы?
Важным в современной теории алгоритмов является раздел о существующих стратегиях решения задач. Здесь следует обратить 
внимание на две часто применяемые схемы решения задач высокой сложности: метод динамического программирования и метод 
«ветвей и границ».
Название «метод» эти стратегии носят скорее традиционно, 
тем более что применение нейросетевых технологий обработки информации затрагивает широкий пласт проблем вычислительной 
математики, решаемых методами искусственного интеллекта. Это 
направление возникло именно на пути поиска методов вычислений минимальной сложности, адекватных мозговым процессам 
и способных обеспечить сверхвысокую реальную (эквивалентную) 
производительность компьютеров, вычислительных комплексов 

и компьютерных сетей в составе сложных информационных 
и управляющих систем.
С учетом уточненного определения теория алгоритмов предоставила достаточное обоснование двух известных принципов цифрового компьютера (двух принципов ЭВМ): программное управление 
выполнением программы (1) и хранимая в памяти программа (2).
Первый принцип превращает компьютер в устройство универсальное, в отличие от многочисленных известных в докомпьютерную эпоху механических, релейных и электронных вычислительных машин, решающих задачи одного типа или класса. Второй 
же принцип позволяет устройству управления компьютера «видеть» 
всю программу и оперативно переключать счетчик команд на требуемые участки программы в соответствии со свойством альтернативности реализуемого алгоритма.
Но не это главное. Переход по адресу не столь оперативно 
можно, например, проводить и на машине Бебиджа механическим 
способом, на основе перфокарт. Дело в том, что при размещении 
программы в памяти во время выполнения она становится неотъемлемой частью данных и наравне с ними может динамически 
подвергаться изменению. Это позволяет проводить модификацию 
или переадресацию команд для повторного выполнения (преимущественно в цикле) операций над новыми данными. Такая переадресация с помощью констант широко использовалась программистами 1950-х — 1960-х гг. Это доставляло много трудностей при 
отладке программ. Ведь для повторного выполнения программы 
все ее команды должны быть восстановлены. И ничего: решили же 
впервые в Советском Союзе задачу противоракетной обороны на 
замечательной для того времени ЭВМ М-40, созданной под руководством академика С.А. Лебедева!
В следующем поколении, к которому относится ЭВМ БЭСМ–6, 
также первоначально планировавшаяся для противоракетной 
обороны, индексация выполнялась с помощью специальных индексных регистров-модификаторов. Утвердившаяся практика применения таких регистров обеспечила оперативную повторную входимость процедур и программ.
Таким образом, незаметно перейдя от теории алгоритмов к современному компьютеру, необходимо последовательно проследить 
способы представления данных в компьютере, принципы выполнения базовых операций, элементарные функции операционной 
системы, режимы функционирования компьютера и его взаимодействие с пользователем.

При изучении начал компьютера нельзя миновать такую важную 
проблему, как достижение высокой (сверхвысокой!) производительности. Это, прежде всего, приводит к применению методов 
распараллеливания на всех этапах выполнения команд и операций. 
На принципиальном уровне в книге представлена архитектура data 
flow, идеально способствующая распараллеливанию программ. 
Также рассмотрена «компромиссная» модель, определяющая практические возможности высокоэффективного распараллеливания 
по данной технологии.

Раздел I
ТИПЫ И СТРУКТУРЫ ДАННЫХ

Глава 1
ТИПЫ ДАННЫХ

1.1. ПОНЯТИЕ ТИПА

— Вопрос мой прост и краток, —
Промолвил Носорог, —
Что лучше — сорок пяток
Или пяток сорок?
А.А. Милн, «Винни-Пух 
и Все-Все-Все» (пер. Б. Заходера)

Если нас попросят сложить пять яблок и семь яблок, то, скорее 
всего (при условии, что мы уже закончили первый класс...), эта 
операция не вызовет никаких затруднений. При этом вопрос будет, 
вероятно, сформулирован следующим образом: «Сколько будет 
всего яблок, если у одного человека их пять, а у другого — семь?»
Ответ на следующий вопрос: «Сколько будет, если сложить 
5 яблок и 7 груш?» — уже не столь очевиден. Сколько чего? Но здесь 
мы все-таки видим что-то общее между складываемыми объектами, 
в частности, и яблоки, и груши — это фрукты. Значит, вопрос мог 
бы звучать так: «Сколько всего фруктов будет, если взять пять 
яблок и семь груш?» 
Предложение сложить пять яблок и, скажем, семь стульев уже 
не вполне понятно с точки зрения житейской логики. Но и здесь 
можно вести речь об общем количестве, например, неодушевленных материальных объектов. Даже если заменить стулья слонами или крокодилами, то все равно между яблоками и ними есть 
нечто общее, позволяющее подсчитать их общее количество — хотя 
бы как биологических объектов.
А вот если нас попросят произвести такое действие: сложить пять 
яблок и семь минут, — то мы, скорее всего, скажем: абсурд, этого 
сделать нельзя. Что должно получиться в сумме? При этом мы понимаем (или хотя бы чувствуем), что дело, вероятно, в том, что они 
являются объектами разной природы, обладающими разными — и, 
более того, совершенно не похожими — свойствами. Значит, яблоки