- •1. Структурная схема микропроцессора (на примере i8086). Назначение регистров.
- •3. Организация основной памяти.
- •3. Структура и характеристики оперативной памяти
- •4. Модель osi
- •5. Стек протоколов tcp/ip
- •6. Классификация компьютерных сетей
- •7. Данные и модели данных
- •8. Модель данных «сущность-связь»
- •Ограничения целостности
- •9. Реляционная модель данных
- •10. Основные направления исследования в области ии
- •11. Метод резолюции в лппп.
- •12. Продукционная модель
- •13. Основные парадигмы языков программирования.
- •14. Основные понятия ооп: инкапсуляция, наследование, полиморфизм
- •1. Инкапсуляция
- •2. Полиморфизм
- •3. Наследование
- •15. Понятие алгоритма.
- •16. Понятие о временной и емкостной сложности алгоритма
- •17. Машина Тьюринга: детерминированная и недетерминированная
- •18. Понятие формального языка и формальной грамматики
- •19. Основные понятия теории графов.
- •20. Понятие количества информации и энтропии. Теорема Шеннона.
- •21. Деревья в теории графов.
- •22. Модели линейного программирования (постановка задачи, математическая модель, решение графическим методом).
- •23. Двойственность в задачах линейного программирования.
- •25. Элементы теории игр.
- •2. Подпрограммы. Процедуры и функции
- •3. Массивы
- •4. Записи
- •5. Работа с Динамическими данными
- •6. Динамические структуры данных. Линейные списки.
- •7. Динамические структуры данных: двоичные деревья
- •8. Работа с файлами
- •9.Операции целочисленной арифметики
- •10. Системы счисления. Перевод чисел из одной системы счисления в другую
- •11. Язык sql. Назначение и основные команды.
- •Манипулирование данными
- •Простые запросы
- •12. Алгоритмы внутренней сортировки.
- •13. Алгоритмы внешней сортировки
- •14. Нахождение кратчайших путей в графе
- •15. Поиск в ширину
- •16. Поиск остова и минимального остова.
- •17. Линейная модель работы информационно-поисковой системы.
- •18. Хеширование
- •Основные достоинства в-дерева
- •20. Логические вопросно-ответные системы:выполнение запросов различных типов.
- •21. Поиск в семантической сети.
- •22. Принципы динамического программирования. Иллюстрация на примере.
- •23. Адресация в Интернете
- •Доменные имена
- •Общий вид формата url-адреса
- •Как работает dns-сервер
- •24. Основные сервисы в сети Интернет.
- •Word Wide Web (www) - "Всемирная паутина"
- •Поиск информации в сети
- •VoIp сервис
- •Мессенджеры
- •25. Использование html. Структура Web(html) страницы.
3. Организация основной памяти.
Минимальной адресуемой единицей основной памяти ПЭВМ является байт, состоящий из 8 бит. Доступ к байтам основной памяти осуществляется по номерам (номер байта является ого физическим адресом в устройстве памяти).
Для адресации основной памяти в микропроцессоре i8086 предусматриваются 20-битовые адреса, что позволяет работать с основной памятью до 1 Мбайта.
Физический адрес формируется из 16-битового смещения и содержимого 16-битового сегментного регистра, сдвинутого влево на 4 бита (см. рис. 2).
Для размещения программ и данных в основной памяти выделяются специальные области - сегменты. Адреса этих областей хранятся в специальных сегментных регистрах.
Каждый из четырех сегментных регистров используется для хранения адреса определенного сегмента (см. рис. 3):
♦ сегмента кодов, т. е. области программ;
♦ сегмента данных, т. е. области размещения данных;
♦ дополнительного сегмента данных, используемого некоторыми командами;
♦ сегмента стека, т.е. области размещения стека.
Стек представляет собой специальным образом организованную область памяти, допускающую последовательную запись элементов данных длиной 2 байта (слово) и чтение их в порядке, обратном порядку записи. Для хранения адреса последнего слова, занесенного в стек, служит регистр-указатель стека SР (см. рис. 4, где а - текущее состояние стека, б - запись X, в - чтение X).
Стек используется для временного хранения данных и адресов, например при вызове подпрограмм, когда в стек заносится адрес возврата и значения параметров, передаваемых в подпрограмму.
Формат команд микропроцессора 8086 позволяет указывать в команде только один операнд, размещенный в основной памяти, т. е. одной командой нельзя, например, сложить содержимое двух ячеек памяти,
Принципиально допускается 8 способов задания смещения (исполнительного адреса) операндов, размещенных в основной памяти:
SI + <индексное смещение>
DI + <индексное смещение>
BP + <индексное смещение>
BХ + <индексное смещение>
BP + SI + < индексное смещение>
BP + DI +< индексное смещение>
BX + SI + <индексное смещение>
BX + DI + <индексное смещение>
Во всех случаях исполнительный адрес операнда определяется как сумма содержимого указанных регистров и индексного смещения, представляющего собой некоторое число (одно- или двухбайтовое).
3. Структура и характеристики оперативной памяти
Память ЭВМ состоит из огромного числа элементов памяти, каждый из которых может находиться в одном из двух состояний, кодируемых двоичной цифрой 0 или 1. Элементы памяти (точнее, биты кодирующие состояния элементов памяти) группируются в более крупные единицы хранения информации – байты, слова, двойные слова. Вне зависимости от модели ЭВМ длина байта информации фиксирована и составляет 8 бит (двоичных разрядов).
Однако длина машинного слова в различных моделях ЭВМ (в процессорах ЭВМ) различна (8 бит, 16 бит, 32, 64, 128) и зависит от соответствующей характеристики шины данных.
Модули памяти (хранилище информации) различного типа объединяясь с соответствующими блоками управления, образуют класс запоминающих устройств (ЗУ).
Современные компьютеры имеют много разнообразных запоминающих устройств, которые сильно отличаются между собой по назначению, временным характеристикам, объёму хранимой информации и стоимости хранения одинакового объёма информации. Различают два основных вида памяти — внутреннюю и внешнюю.
В состав внутренней памяти входят оперативная память, кэш-память и специальная память.
Оперативная память (ОЗУ, англ. RAM, Random Access Memory — память с произвольным доступом) — это быстрое запоминающее устройство не очень большого объёма, непосредственно связанное с процессором и предназначенное для записи, считывания и хранения выполняемых программ и данных, обрабатываемых этими программами.
Оперативная память используется только для временного хранения данных и программ, так как, когда машина выключается, все, что находилось в ОЗУ, пропадает. Доступ к элементам оперативной памяти прямой — это означает, что каждый байт памяти имеет свой индивидуальный адрес.
Из микросхем, памяти (RAM – Random Access Memory, память с произвольным доступом) используются два основных типа: статическая (SRAM – Static RAM) и динамическая (DRAM – Dynamic RAM).
Статическое распределение памяти основано на выделении ячеек ОП для массивов в процессе анализа и составления программы, т.е. до начала решения задачи и при выполнении программы базисные адреса сохраняют постоянные значения. При статическом распределении ячеек памяти в массивах память используется неэффективно, так как в процессе решения задачи количество слов в массиве в большинстве случаев меньше длины массива ячеек с базовым адресом Аб. Поэтому такой способ применяют лишь в простейших системах программирования на небольших ЭВМ.
Динамическое распределение памяти основано на выделении ячеек памяти для массивов с учетом их длин в порядке их появления в процессе ре шения задачи на ЭВМ. Оно используется для экономии ячеек памяти в пределах одной программы и при мультипрограммной работе ЭВМ для распределения памяти между программами.
Кэш (англ. cache), или сверхоперативная память — очень быстрое ЗУ небольшого объёма, которое используется при обмене данными между микропроцессором и оперативной памятью для компенсации разницы в скорости обработки информации процессором и несколько менее быстродействующей оперативной памятью.
Кэш-памятью управляет специальное устройство — контроллер.
В кэш-память из оперативной переписываются данные, к которым обращается процессор (при первом обращении), и из кэша производится выборка этих данных при последующих обращениях. Так как скорость работы кэша выше оперативной, процесс вычислений ускоряется. Обычно перепись производится блоками, сразу по несколько слов. Если есть запрос к слову, которое есть в кэше, то считывание производится из кэша и операция завершается (кэш-попадание). Если запрашиваемого данного нет в кэше ("промах" кэша), оно считывается в кэш и передается в процессор. При этом возможно вытеснение из кэша данных, размещенных в нем ранее. При записи в кэш используются различные стратегии обновления основной памяти.
К устройствам специальной памяти относятся постоянная память (ROM), перепрограммируемая постоянная память (Flash Memory), память CMOS RAM, питаемая от батарейки, видеопамять и некоторые другие виды памяти.
Постоянная память (ПЗУ, англ. ROM, Read Only Memory — память только для чтения) — энергонезависимая память, используется для хранения данных, которые никогда не потребуют изменения. Содержание памяти специальным образом "зашивается" в устройстве при его изготовлении для постоянного хранения. Из ПЗУ можно только читать.
Перепрограммируемая постоянная память (Flash Memory) — энергонезависимая память, допускающая многократную перезапись своего содержимого с дискеты.
Прежде всего в постоянную память записывают программу управления работой самого процессора. В ПЗУ находятся программы управления дисплеем, клавиатурой, принтером, внешней памятью, программы запуска и остановки компьютера, тестирования устройств.
Важнейшая микросхема постоянной или Flash-памяти — модуль BIOS. Роль BIOS двоякая: с одной стороны это неотъемлемый элемент аппаратуры, а с другой строны — важный модуль любой операционной системы.
BIOS (Basic Input/Output System — базовая система ввода-вывода) — совокупность программ, предназначенных для автоматического
Адресация информации и обработка адресов
Для расширения операционных возможностей и увеличения производительности процессора применяются различные способы адресации информации, отличающиеся порядком использования и обработки адресного поля в команде (ПА), посредством которого организуется доступ к информации, хранящейся в оперативной памяти (ОП) или ПЗУ ЭВМ.
Непосредственная адресация
В коде команды (в коде одного или нескольких адресов) размещается непосредственный операнд, если число значащих цифр операнда не превышает длины адресной части команды. Такая адресация используется для хранения различного рода констант и находит широкое применении в универсальных ЭВМ в целях экономии ячеек ОП и уменьшения времени выполнения команды.
Прямая адресация
Исполнительный адрес – адрес ячейки ОП, в которой храниться адресуемое слово, совпадает с адресной частью команды. Этот метод используется в ЭВМ в комбинации с другими методами адресации.
Рассмотренные методы адресации обеспечивают адресацию переменных и констант.
Относительная адресация
При динамическом распределении памяти базовые адреса массивов изменяются в процессе выполнения программы, в результате адреса не могут быть зафиксированы в программе. Для обеспечения динамического распределения памяти используют способ относительной адресации. Относительный адрес (рис.5) состоит из двух полей: B, указывающего базовый адрес Аб массива D. Поле D представляющего собой относительный адрес Aотн. Поле D принято называть смещением D операнда относительно начала массива. Исполнительный адрес вычисляется по формуле Аисп=(B)+D. Для хранения базовых адресов в целях повышения быстродействия ЭВМ используют так называемые базовые регистры СОЗУ.
Рис. 5.
Рис. 6.
При формировании Аисп на суммирование в сумматоре затрачивается некоторое время. В целях уменьшения этого времени используют так называемый метод совмещения. В этом случае в базовом регистре B (рис.6) содержаться старшие разряды, а в поле D записывают младшие разряды исполнительного адреса Аисп, которые выдаются непосредственно в регистр адреса оперативной памяти (РОАП). При совмещении, очевидно, базовый адрес Аб не может принимать значение адреса любой ячейки ОП, а только тех адресов, которые содержат в младших разрядах нули, соответствующие количеству разрядов поля D.
Организация виртуальной памяти
Обычно при решении задач на ЭВМ только часть информации размещается во внутренней памяти, а остальная храниться во внешней памяти. Таким образом, программист имеет дело с многоуровневой памятью и, планируя процесс решения задачи, включает в программу операции, вызывающие обмен информацией между различными ЗУ. Даже при наличии систем автоматизации программирования и хорошо организованных систем управления данными, программирование задач для ЭВМ с многоуровневой памятью отличается сложностью и требует от исполнителей высокой квалификации. Особенно сложны процедуры обмена информацией между уровнями памяти, необходимые для организации мультипрограммной работы ЭВМ в режиме разделения времени. В связи с этим, в современных ЭВМ осуществляется автоматическое (не предусмотренное программой) планирование передач информации в многоуровневой памяти, основанное на построении виртуальной (воображаемой, кажущейся, фиктивной) одноуровневой памяти.
Под виртуальной памятью понимается совокупность ячеек всех ОЗУ и ВЗУ, имеющих сквозную нумерацию 0, 1, 2, 3, … (Q-1). Программирование процессов решения задач производится в терминах математических (виртуальных) адресов 0, 1, 2, 3, … (Q-1). При этом команды ссылаются на математические адреса в предположении, что слово, идентифицированное любым математическим адресом, является доступным для процессора. Таким образом, для программиста создается одноуровневая память емкостью - Q слов. В физическом отношении виртуальная память – это совокупность оперативных и внешних ЗУ, охваченных средствами преобразования математических адресов в физические (действительные) адреса ячеек и автоматизации перемещения информации между устройствами памяти.
Страничная адресация памяти
Механизмы виртуальной страничной памяти реализуются путем разбиения памяти и виртуальной и физической на одинаковые страницы, размером 2-4 Кбайта. Адрес разделяется на две части в соответствии с принятой длиной страницы: номер страницы (P) и адрес внутри страницы - сдвиг, смещение (A).
Аппаратно трансляция адресов производится при помощи таблицы страниц, хранящейся в отдельной памяти. Каждой странице виртуальной памяти соответствует строка в таблице страниц, объем которой соответствует числу страниц виртуальной памяти. В i строке таблицы хранится: N страницы (блока) физической памяти, которая соответствует данной виртуальной, статус доступа (чтение, запись), признак записи. Трансляция адресов: реальный, физический адрес получается добавлением к старшей части физического адреса, полученного из таблице страниц, адреса внутри страницы (смещения).
Процессы преобразования адресов и перемещения информации наиболее просто реализуется при страничной адресации памяти. Метод страничной адресации состоит в том, что виртуальная память (как множество адресов) разделяется на страницы емкостью 2К (обычно 220-240 байт = 2-4 Кб) соседних адресов. Так, к странице с адресом 0 относятся адреса: 0, 1, 2, …, (2К-1), к странице с адресом 2К относят следующие адреса: 2К, 2К+1, 2К+2, … 2К+1-1 и так далее. В результате адрес виртуального слова будет состоять из двух полей: P- Указывающих адрес страницы, и А – адрес слова в странице Р (рис. 8).
виртуальный адрес, б) физический адрес
Рис. 8. Адреса при страничной адресации.
В процессе решения задачи страницы перемещаются между ОЗУ и ВЗУ. Если вычислительный процесс распределяется на страницу P, то она вызывается в ОЗУ. Когда надобность в информации, размещенной на странице P, отпадает, то она удаляется из ОЗУ в виртуальную память, освобождая место для других страниц. В результате перемещения граница P может быть помещена на любом сегменте S ОП.
Сегментация памяти
Другой подход к организации памяти опирается на тот факт, что программы обычно разделяются на отдельные области-сегменты. Каждый сегмент представляет собой отдельную логическую единицу информации, содержащую совокупность данных или программ и расположенную в адресном пространстве пользователя. Сегменты создаются пользователями, которые могут обращаться к ним по символическому имени. В каждом сегменте устанавливается своя собственная нумерация слов, начиная с нуля.
Обычно в подобных системах обмен информацией между пользователями строится на базе сегментов. Поэтому сегменты являются отдельными логическими единицами информации, которые необходимо защищать, и именно на этом уровне вводятся различные режимы доступа к сегментам. Можно выделить два основных типа сегментов: программные сегменты и сегменты данных (сегменты стека являются частным случаем сегментов данных). Поскольку общие программы должны обладать свойством повторной входимости, то из программных сегментов допускается только выборка команд и чтение констант. Запись в программные сегменты может рассматриваться как незаконная и запрещаться системой. Выборка команд из сегментов данных также может считаться незаконной, и любой сегмент данных может быть защищен от обращений по записи или по чтению.
В системах с сегментацией памяти каждое слово в адресном пространстве пользователя определяется виртуальным адресом, состоящим из двух частей: старшие разряды адреса рассматриваются как номер сегмента, а младшие – как номер слова внутри сегмента.
Как и в случае страничной организации, необходимо обеспечить преобразование виртуального адреса в реальный физический адрес основной памяти. С этой целью для каждого пользователя операционная система должна сформировать таблицу сегментов. Каждый элемент таблицы сегментов содержит описатель (дескриптор) сегмента (поля базы, границы и индикаторов режима доступа). При отсутствии страничной организации поле базы определяет адрес начала сегмента в основной памяти, а граница длину сегмента. При наличии страничной организации поле базы определяет адрес начала таблицы страниц данного сегмента, а граница – число страниц в сегменте.