Технология программирования. 1. Устройство компьютера. Оперативная память, процессор
 Скачать 478.73 Kb.
|
|
01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 1/69 Московский финансово-промышленный университет «Синергия» ВВЕДЕНИЕ 4 Том Сойер рисует на заборе 4 Сид выполняет команды 5 Тема 1. Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек 7 1.1. Устройство компьютера 7 1.2. Оперативная память 8 1.3. Процессор 9 1.4. Алгоритм работы компьютера 11 1.5. Аппаратный стек 12 1.6. Команды вызова подпрограммы и возврата 13 Тема 2. Языки программирования 13 2.1. Первые языки программирования 14 2.2. Области применения языков программирования 17 2.3. Парадигмы программирования 18 2.4. Состав языка программирования 19 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 2/69 2.5. Стандартизация языков программирования 20 2.6. Среда проектирования 21 2.7. Трансляторы 21 2.8. Процесс трансляции 22 Тема 3. Общее понятие алгоритма. Управляющие конструкции алгоритмического языка. 24 3.1. Общее понятие алгоритма 25 3.2. Управляющие конструкции алгоритмического языка 26 3.3. Язык схем 29 3.4. Основные структуры алгоритмов 32 3.5. Понятие переменной 36 Тема 4. Типы переменных. Целые и вещественные переменные, представление целых и вещественных чисел в компьютере 39 4.1. Типы переменных 40 4.2. Целочисленные переменные 40 4.3. Вещественные переменные 42 4.4. Символьные переменные 45 4.5. Логические переменные и выражения 47 4.6. Массивы 49 4.7. Текстовые строки 51 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 3/69 1. ВВЕДЕНИЕ 1.1. Том Сойер рисует на заборе «Том появился на тротуаре с ведром извёстки и длинной кистью в руках. Он оглядел забор, и всякая радость отлетела от него, а дух погрузился в глубочайшую тоску. Тридцать ярдов дощатого забора в девять футов вышиной! Жизнь показалась ему пустой, а существование – тяжким бременем». Марк Твен, «Приключения Тома Сойера» Память компьютера похожа на длинный-предлинный забор, правда, покрашенный совсем не так, как хотелось бы тетушке Полли. Представим себе, что Том со своими дружками покрыли известкой не все доски забора, а, скажем, только первую, вторую, четвертую, седьмую... и т.д.: 1 1 0 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 0 0 Поступая так, Том Сойер и его команда, конечно же, не подозревали, что полосатый забор можно рассматривать как двоичный код, в котором единице соответствует светлая, а нулю – темная, непокрашенная доска. Каждая доска может быть только в двух состояниях, следовательно, она способна нести один бит информации. Число различных состояний двух идущих подряд досок уже равно четырем, поскольку каждому из двух состояний первой доски соответствуют два состояния второй. Легко понять, что восемь идущих подряд досок можно выкрасить 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 ´ 2 = 2 8 = 256 способами. Иными словами, в восьми битах можно уместить 256 разных чисел (от 0 до 255, например), а этого вполне достаточно, чтобы закодировать любую букву. Поскольку «забор» в нашем примере 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 4/69 состоит из 24 досок (цифр), он пригоден для того, чтобы закодировать сразу три буквы. Какие же буквы показаны на заборе? Ответ на этот вопрос зависит от договоренности: какому числу соответствует та или иная буква. Первое число (11010010) на заборе равно (в привычном нам десятичном представлении) 210, второе (11001110) – это 206, третье (11001100) равно 204. И вся эта тройка соответствует в операционной системе Windows, скорее всего установленной у вас на компьютере, слову «ТОМ». 1.2. Сид выполняет команды Цифра 8 возникла в нашем шуточном примере не случайно. Ведь восемь битов (досок в заборе тетушки Полли) составляют байт – ячейку памяти минимального размера, к которой имеет доступ компьютер. Можно сказать, что память компьютера состоит из последовательности идущих друг за другом ячеек – байтов. В этих ячейках хранятся нули и единицы, которые могут быть чем угодно: буквами, цифрами или выполняемыми компьютером командами. Представим себе, что компьютерная программа написана на заборе, а роль процессора играет образцовый брат Тома – Сид. Том сидит на бочке и жует яблоко, а Сид отправляется к тому месту забора, где записана первая команда. Стоит еще раз подчеркнуть: в памяти компьютера, как и на заборе, хранятся последовательности нулей и единиц. Поэтому нужно заранее знать, с какой ячейки (байта) начинается программа, чтобы не перепутать команды процессора и данные. Итак, предположим, что команда начинается с 31-го байта, то есть с 241-й доски забора. Подойдя к ней, Сид ищет число, там записанное, в специальной справочной таблице, которую вынужден носить с 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 5/69 собой. Из этой таблицы он узнает, что делать дальше. Может, например, оказаться, что прочитанный Сидом байт – лишь часть команды процессора, и чтобы выполнить ее, необходимо знать содержимое нескольких следующих ячеек. Команды, выполняемые Сидом, весьма разнообразны. Простейшая команда просто велит ему перейти к другой ячейке. Если ее номер равен 20, Сиду нужно будет сделать несколько шагов к началу забора, а если это 10000-й байт – ему придется мчаться к самому его концу. Команда перехода может быть условной, например, Сид перейдет к ячейке 20 лишь в том случае, если число, хранящееся в пятнадцатом байте, больше нуля. Представим себе, что перед выполнением программы в пятнадцатой ячейке хранится число 10. Раз оно больше нуля, Сид перейдет к двадцатому байту, выполнит команды, записанные в ячейках с номерами 21¸30, и, если содержимое 15-й ячейки не изменилось, 31- й байт вновь отошлет его назад, и так он будет крутиться, пока хватит сил. Если же команды, хранящиеся в байтах 21¸30, после многих пробежек Сида запишут нуль в ячейку 15, тот вместо двадцатого байта перейдет к следующей команде, начало которой хранится в ячейке 32. Иными словами, Сид будет выполнять команды последовательно, одну за другой, пока ему не прикажут перейти к иной ячейке, и после очередной пробежки вдоль забора он снова начнет выполнять команды последовательно. И так будет продолжаться до тех пор, пока он не наткнется на команду «Стоп». Впрочем, еще раньше он может встретить число, которого нет в его таблице, или же предписание перейти к 1000000-й доске забора, в то время как в нем их всего 100000. И тогда Сид застынет в недоумении или побежит жаловаться Тому. А когда такое случается с настоящим компьютером, на экране возникает сообщение: «Программа выполнила недопустимую операцию и будет закрыта». 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 6/69 Тема 1. Устройство компьютера. Оперативная память, процессор, регистры процессора. Аппаратный стек 1.1. Устройство компьютера Компьютер - это универсальный исполнитель, который умеет управлять другими исполнителями и обладает собственной внутренней памятью. Запись алгоритма для компьютера называется программой. Все современные компьютеры построены по так называемой фон-Неймановской архитектуре: программа хранится в памяти компьютера, так же как и данные. Компьютер построен из следующих составных частей: · процессор - это основа любого компьютера, его мозг. Процессор производит все вычисления и отдает команды всем остальным компонентам компьютера; · оперативная память также является обязательной составной частью любого компьютера. Оперативная память (RAM - Random Access Memory) хранит как программу, так и данные (т.е. значения переменных). Часть памяти может быть защищена от записи и хранится в специальной микросхеме (ПЗУ - постоянное запоминающее устройство или ROM - Read Only Memory). Обычно в ПЗУ лежит программа первоначальной загрузки и базовая система ввода-вывода (BIOS); · шина - это канал передачи команд и данных между всеми составными частями компьютера. В компьютере могут быть одна или несколько шин. Все устройства подключаются к шине параллельно, т.е. порядок подключения не важен, а количество проводов не зависит от количества подключенных устройств. Порядок передачи команд и данных определяется протоколом работы шины, т.е. четко описанным набором соглашений, принятым, как правило, в виде 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 7/69 международного стандарта. Каждое устройство подключается к шине с помощью контроллера, который осуществляет перевод с языка сигналов, передаваемых по шине, на язык команд конкретного устройства; · внешние устройства подключаются к шине компьютера. Наиболее распространенные внешние устройства - это жесткий диск, клавиатура, монитор, сетевая карта, модем и т.п. Ни одно из них не является обязательным, как показывает пример компьютера, управляющего автомобильным двигателем со впрыском топлива. Но какие-то внешние устройства всегда присутствуют, поскольку через них осуществляется связь компьютера с внешним миром. Рассмотрим каждую из составляющих частей компьютера более подробно. 1.2. Оперативная память Элементарной единицей памяти всех современных компьютеров является байт, состоящий из восьми двоичных разрядов. Каждый байт имеет свой адрес. Память, с логической точки зрения, можно рассматривать как массив байтов: можно прочесть или записать байт с заданным адресом. Содержимое байта трактуется либо как неотрицательное целое число в диапазоне от 0 до255, либо как число со знаком в диапазоне от -128 до 127. Однако физически при работе с памятью по шине передаются не отдельные байты, а машинные слова. В 32-разрядной архитектуре машинное слово — это четыре подряд идущих байта, при этом адрес младшего байта кратен четырем. (В 64-разрядной архитектуре машинное слово состоит из восьми байтов.) Машинное слово — это наиболее естественный элемент данных для процессора. Машинное слово содержит целое число, которое можно рассматривать либо как беззнаковое в диапазоне от 0 до 2 32 - 1, либо как знаковое в 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 8/69 диапазоне от -2 31 до 2 31 - 1. Адрес памяти также представляет собой машинное слово. Принято нумеровать биты внутри машинного слова (как и внутри байта) справа налево, начиная с нуля и кончая 31. Младший бит имеет нулевой номер, старший, или знаковый, бит — номер 31 . Младшие биты числа находятся в младших битах машинного слова. Существуют два способа нумеровать байты внутри машинного слова. В соответствии с этим все процессоры разделяются на два типа: · Big Endian - байты внутри машинного слова нумеруются слева направо. Таковы процессоры Motorola, Power PC. Байты в архитектуре Big Endian удобно представлять записанными слева направо. При этом старшие биты целого числа располагаются в байте с младшим адресом. · Little Endian - байты внутри машинного слова нумеруются справа налево. Таковы процессоры Intel 80x86, Alpha, VAX и др. Байты в архитектуре Little Endian следует представлять записанными справа налево. При этом старшие биты целого числа располагаются в байте со старшим адресом. Архитектура Big Endian была популярна в середине XX века. К концу 70-х годов программисты осознали, что Little Endian-архитектура гораздо удобнее. Например, один из аргументов в пользу Little Endian заключается в том, что целое число, занимающее машинное слово с адресом n, и байт с тем же адресом содержат одно и то же значение (конечно, если оно не превышает 255). В случае Big Endian это не так: например, если целое число с адресом n содержит число 17, то байт с адресом n содержит 0; или если целое число содержит отрицательное значение -77, то байт с адресом n содержит отрицательное значение -1. При небрежном программировании это порождает массу ошибок. Поэтому большинство современных процессоров построены по архитектуре Little Endian. 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 9/69 Тем не менее многие компьютерные протоколы ориентируются на Big Endian, поскольку они были приняты достаточно давно. Например, все протоколы сети Internet передают данные в формате Big Endian, т.к. они были разработаны в 70-х годах XX века. На машинах с архитектурой Little Endian приходится переставлять байты внутри слова перед отправкой IP-пакета в сеть или при получении IP-пакета из сети. 1.3. Процессор Процессор является основой любого компьютера. Это большая микросхема, содержащая внутри себя сотни тысяч или даже миллионы элементов. Современные процессоры чрезвычайно сложны и могут содержать несколько уровней построения и описания. Так, можно различать внешние команды процессора в том виде, в котором они используются в программах и записываются в оперативной памяти, и внутренний микрокод, применяемый для реализации внешних команд. Процессор может содержать внутри себя устройства, предназначенные для ускорения работы, — конвейер команд, устройство опережающей выборки из памяти, кеш- память и т.п. Рассмотрим лишь самые общие принципы построения и работы процессора, которые одинаковы как для примитивных, так и для самых современных процессоров. Любой процессор имеет устройство, выполняющее команды, и собственную внутреннюю память, реализованную внутри микросхемы процессора. Она называется регистрами процессора. Имеется 3 типа регистров: · общие регистры хранят целые числа или адреса. Размер общего регистра совпадает с размером машинного слова и в 32-разрядной архитектуре равен четырем байтам. Число общих регистров и их назначение зависит от конкретного процессора. В большинстве 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 10/69 Ассемблеров к ним можно обращаться по именам R0, R1, R2, ...Среди общих регистров имеются регистры специального назначения: указатель стека SP (Stack Pointer), счетчик команд PC (Program Counter) и др.; · регистр флагов содержит биты, которые устанавливаются в единицу или в ноль в зависимости от результата выполнения последней команды. Так, бит Z устанавливается в единицу, если результат равен нулю (Zero), бит N — если результат отрицательный (Negative), бит V — если произошло переполнение (oVerflow), бит С - если произошел перенос единицы из старшего или младшего разряда (Carry), например, при сложении двух целых чисел или при сдвиге. Значения битов в регистре флагов используются в командах условных переходов; · плавающие регистры содержат вещественные числа. В простых процессорах аппаратная поддержка арифметики вещественных чисел может отсутствовать. В этом случае плавающих регистров нет, а операции с вещественными числами реализуются программным путем. Команды, или инструкции, процессора состоят из кода операции и операндов. Команда может вообще не иметь операндов или иметь один, два, три операнда. Команды с числом операндов большим трех встречаются лишь в процессорах специального назначения (служащих, например, для обработки сигналов) и в обычных архитектурах не используются. Чаще всего применяются двухадресные и трехадресные архитектуры: к двухадресным относятся, к примеру, все процессоры серии Intel 80x86, к трехадресным — серии Motorola 68000. В двухадресной архитектуре команда сложения выглядит следующим образом: add X, Y что означает 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 11/69 X = X + Y, т.е. один из аргументов команды является одновременно и ее результатом. Этот аргумент называется получателем (destination). Аргумент, который не меняется в результате выполнения команды, называется источником (source). Среди программистов нет единого мнения о том, в каком порядке записывать аргументы при использовании Ассемблера, т.е. в символической записи машинных команд. Например, в Ассемблере "masm" фирмы IBM для процессоров Intel 80x86 получатель всегда записывается первым, а источник вторым. Ассемблер "masm" используется в операционных системах MS DOS и Windows. В Ассемблере "as", который входит в состав компилятора "gcc" и используется в системах типа Unix (Linux и т.п.), получатель всегда является последним аргументом. Та же команда сложения записывается в "as" как add Y, X что означает сложить Y и X и результат записать в X. В трехадресной архитектуре команда сложения имеет 3 операнда: add X, Y, Z Получателем в трехадресной архитектуре обычно является третий аргумент, т.е. в данном случае сумма X+Y записывается в Z. Операндами команды могут быть регистры или элементы памяти. В действительности, конечно, процессор всегда сначала копирует слово из памяти в регистр, который может быть либо явно указан в команде, либо использоваться неявно. Операция всегда выполняется с содержимым регистров. После этого результат может быть записан в память либо оставлен в регистре. Например, при выполнении команды увеличения целого числа на единицу int X 01.02.2021 Московский финансово-промышленный университет «Синергия» e-biblio.ru/book/bib/01_informatika/ProgBK/Book_teria_prog.html#_Toc241999345 12/69 в случае, когда операнд X является словом оперативной памяти, содержимое слова X сначала неявно копируется во внутренний регистр процессора, затем выполняется его увеличение на единицу, и после этого увеличенное значение записывается обратно в память. Имеется несколько способов задания операнда, находящегося в оперативной памяти, они называются режимами адресации. Это · |