Алгоритм поиска и алгоритм замещения данных в кэше непосредственно зависят от того, каким образом основная память отображается на кэш-память. Принцип прозрачности требует, чтобы правило отображения основной памяти на кэш-память не зависело от работы программ и пользователей, При кэшировании данных из оперативной памяти широко используются две основные схемы отображения: случайное отображение и детерминированное отображение.
При случайном отображении элемент оперативной памяти в общем случае может быть размещен в произвольном месте кэш-памяти. Для того чтобы в дальнейшем можно было найти нужные данные в кэше, они помещаются туда вместе со своим адресом, то есть тем адресом, который данные имеют в оперативной памяти. При каждом запросе к оперативной памяти выполняется поиск в кэше, причем критерием поиска выступает адрес оперативной памяти из запроса. Очевидная схема простого перебора для поиска нужных данных в случае кэша оказывается непригодной из-за недопустимо больших временных затрат.
Для кэшей со случайным отображением используется так называемый ассоциативный поиск, при котором сравнение выполняется не последовательно с каждой записью кэша, а параллельно со всеми его записями (рис. 5.26). Признак, по которому выполняется сравнение, называется тегом (tag). В данном случае тегом является адрес данных в оперативной памяти. Электронная реализация такой схемы приводит к удорожанию памяти, причем стоимость существенно возрастает с увеличением объема запоминающего устройства. Поэтому ассоциативная кэш-память используется в тех случаях, когда для обеспечения высокого процента попадания достаточно небольшого объема памяти.
В кэшах, построенных на основе случайного отображения, вытеснение старых данных происходит только о том случае, когда вся кэш-память заполнена и нет свободного места. Выбор данных на выгрузку осуществляется среди всех записей кэша. Обычно этот выбор основывается на тех же приемах, что и в алгоритмах замещения страниц, например выгрузка данных, к которым дольше всего не было обращений, или данных, к которым было меньше всего обращений. Второй, детерминированный способ отображения предполагает, что любой элемент основной памяти всегда отображается в одно и то же место кэш-памяти. В этом случае кэш-память разделена на строки, каждая из которых предназначена для хранения одной записи об одном элементе данных и имеет свой номер. Между номерами строк кэш-памяти и адресами оперативной памяти устанавливается соответствие «один ко многим»: одному номеру строки соответствует несколько (обычно достаточно много) адресов оперативной памяти.
В качестве отображающей функции может использоваться простое выделение нескольких разрядов из адреса оперативной памяти, которые интерпретируются как номер строки кэш-памяти (такое отображение называется прямым). Например, пусть в кэш-памяти может храниться 1024 записи, то есть кэш имеет 1024 строки, пронумерованные от 0 до 1023. Тогда любой адрес оперативной памяти может быть отображен на адрес кэш-памяти простым отделением 10 двоичных разрядов.
В действительности запись в кэше обычно содержит несколько элементов данных.
При поиске данных в кэше используется быстрый прямой доступ к записи по номеру строки, полученному путем обработки адреса оперативной памяти из запроса. Однако поскольку в найденной строке могут находиться данные из любой ячейки оперативной памяти, младшие разряды адреса которой совпадают с номером строки, необходимо выполнить дополнительную проверку. Для этих целей каждая строка кэш-памяти дополняется тегом, содержащим старшую часть адреса данных в оперативной памяти. При совпадении тега с соответствующей частью адреса из запроса констатируется кэш-попадание.Если же произошел кэш-промах, то данные считываются из оперативной памяти и копируются в кэш. Если строка кэш-памяти, в которую должен быть скопирован элемент данных из оперативной памяти, содержит другие данные, то последние вытесняются из кэша. Заметим, что процесс замещения данных в кэш-памяти на основе прямого отображения существенно отличается от процесса замещения данных в кэш-памяти со случайным отображением. Во-первых, вытеснение данных происходит не только в случае отсутствия свободного места в кэше, во-вторых, никакого выбора данных на замещение не существует.
Во многих современных процессорах кэш-память строится на основе сочетания этих двух подходов, что позволяет найти компромисс между сравнительно низкой стоимостью кэша с прямым отображением и интеллектуальностью алгоритмов замещения в кэше со случайным отображением. При смешанном подходе произвольный адрес оперативной памяти отображается не на один адрес кэш-памяти (как это характерно для прямого отображения) и не на любой адрес кэшпамяти (как это делается при случайном отображении), а на некоторую группу адресов. Все группы пронумерованы. Поиск в кэше осуществляется вначале по номеру группы, полученному из адреса оперативной памяти из запроса, а затем в пределах группы путем ассоциативного просмотра всех записей в группе на предмет совпадения старших частей адресов оперативной памяти. При промахе данные копируются по любому свободному адресу из однозначно заданной группы. Если свободных адресов в группе нет, то выполняется вытеснение данных. Поскольку кандидатов на выгрузку несколько — все записи из данной группы — алгоритм замещения может учесть интенсивность обращений к данным и тем самым повысить вероятность попаданий в будущем. Таким образом, в данном способе комбинируется прямое отображение на группу и случайное отображение в пределах группы.
СОДЕРЖАНИЕ
СОДЕРЖАНИЕ.. 3
ВВЕДЕНИЕ.. 5
1. ОБЩИЕ ПРИНЦИПЫ ПОСТРОЕНИЯ СЕТЕЙ.. 7
1.1. Функциональные возможности сетей. 7
1.2. Структурная организация компьютерной сети. 10
1.2.1. Сети разного масштаба. 10
1.2.2. Среды передачи данных. 10
1.2.3. Режимы передачи данных. 11
1.2.4. Способы коммутации. 12
1.2.5. Виртуальные каналы.. 13
2. АНАЛОГОВЫЕ КАНАЛЫ ПЕРЕДАЧИ ДАННЫХ.. 14
2.1. Аналоговая модуляция. 14
2.2. Модемы.. 15
2.3. Протоколы, поддерживаемые модемами. 16
2.4. Режимы передачи. 17
2.5. Асинхронная, синхронная, изохронная и плезиохронная передача. 17
3. ЦИФРОВЫЕ КАНАЛЫ ПЕРЕДАЧИ ДАННЫХ.. 19
3.1. Частотное и временное разделение каналов. 19
3.2. Проводные линии связи и их характеристики. 20
3.2.1. Витая пара. 20
3.2.2. Коаксиальный кабель. 22
3.2.3. Волоконно-оптический кабель. 24
3.3. Беспроводные среды передачи данных. 25
3.3.1. Инфракрасные волны.. 25
3.3.2. Радиоволны, сигналы с узкополосным спектром.. 25
3.3.3. Радиоволны, широкополосные сигналы.. 26
3.3.4. Спутниковая связь. 27
3.3.5. Сотовая связь. 28
4. ПЕРЕДАЧА ДАННЫХ И КОДИРОВАНИЕ ИНФОРМАЦИИ.. 30
4.1. Количество информация и энтропия. 30
4.2. Свойства энтропии. 31
4.3. Единицы количества информации. 32
4.4. Кодирование информации. 32
4.5. Логическое кодирование. 35
4.6. Самосинхронизирующиеся коды.. 37
5. КОНТРОЛЬ ПЕРЕДАЧИ ИНФОРМАЦИИ И СЖАТИЕ ДАННЫХ.. 38
5.1. Самовосстанавливающиеся коды.. 38
5.2. Систематические коды.. 39
5.3. Алгоритмы сжатия данных. 39
5.3.1. Алгоритм RLE. 40
5.3.2. Алгоритм Лемпела-Зива. 40
5.3.3. Кодирование Шеннона-Фано. 41
5.3.4. Алгоритм Хаффмана. 41
6. СЕТЕВОЕ ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ.. 43
6.1. Архитектура СПО.. 43
6.2. Основные принципы взаимосвязи открытых систем.. 44
7. МОДЕЛЬ ВЗАИМОДЕЙСТВИЯ ОТКРЫТЫХ СИСТЕМ... 45
7.1. Структура модели OSI. 45
7.2. Протоколы и интерфейсы.. 47
7.3. Уровни модели OSI. 48
7.3.1. Физический уровень. 48
7.3.2. Канальный уровень. 50
7.3.3. Сетевой уровень. 52
7.3.4. Транспортный уровень. 54
7.3.5. Сеансовый уровень. 54
7.3.6. Уровень представления. 55
7.3.7. Прикладной уровень. 55
7.4. Назначение уровней модели OSI. 55
8. ОСНОВНЫЕ ХАРАКТЕРИСТИКИ ЛОКАЛЬНЫХ СЕТЕЙ.. 58
8.1. Сетевые топологии. 58
8.1.1. Шина. 58
8.1.2. Дерево. 59
8.1.3. Звезда с пассивным центром.. 59
8.1.4. Звезда с интеллектуальным центром.. 60
8.1.5. Кольцо. 60
8.1.6. Цепочка. 60
8.1.7. Полносвязная топология. 61
8.1.8. Произвольная (ячеистая) топология. 61
8.2. Методы доступа и их классификация. 62
8.2.1. Метод доступа с контролем несущей и определением коллизий. 63
8.2.2. Маркерные методы доступа. 63
9. ОСНОВНЫЕ ТИПЫ СЕТЕВЫХ УСТРОЙСТВ.. 65
9.1. Сетевые адаптеры.. 65
9.2. Концентраторы.. 66
9.3. Мосты.. 68
9.4. Коммутаторы.. 71
9.5. Брандмауэры.. 73
10. СЕТИ TOKEN RING И FDDI. 76
10.1. Технология Token Ring.. 76
10.1.1. Маркерный метод доступа. 76
10.1.2. Система приоритетного доступа. 80
10.1.3. Оборудование Token Ring. 81
10.2. Технология FDDI. 82
11. ТЕХНОЛОГИЯ ETHERNET.. 84
11.1. Появление и сущность технологии Ethernet. 84
11.2. Форматы кадров Ethernet. 87
11.3. Высокоскоростные технологии локальных сетей. 91
11.3.1. Технология Fast Ethernet 100Мбит/с. 91
11.3.2. Технология Gigabit Ethernet 1000 Мбит/с. 93
11.3.3. Технология 100VG-AnyLAN.. 94
12. ТРЕБОВАНИЯ К СЕТЯМ... 96
12.1. Производительность. 96
12.2. Надежность и безопасность. 99
12.3. Расширяемость и масштабируемость. 100
12.4. Прозрачность. 101
12.5. Поддержка разных видов трафика. 102
12.6. Управляемость. 103
12.7. Совместимость. 104
12.8. Качество обслуживания. 104
СПИСОК ЛИТЕРАТУРЫ... 108
ВВЕДЕНИЕ
Последнее десятилетие XX века можно с большим основанием назвать десятилетием компьютерных сетей. В коммерческих фирмах и государственных учреждениях, учебных заведениях и даже дома все реже можно встретить компьютеры, никаким образом не связанные с другими. Если для предприятий и организаций наиболее важным оказалось развертывание локальных сетей, то домашних пользователей все больше привлекают глобальные сети - Интернет, иногда FIDO.
Два-три десятилетия назад только крупная организация могла позволить себе приобрести хотя бы один компьютер, потому что он стоил сотни тысяч долларов, требовал много места для размещения, и необходим был квалифицированный, а значит, высокооплачиваемый, обслуживающий персонал. Как правило, компьютеры тогда работали в пакетном режиме, пользователь (обычно программист) мог вообще никогда и не увидеть ЭВМ, выполняющую его задачи. Программы записывались на специальных бланках, по которым операторы готовили перфокарты, наконец, программу в виде колоды перфокарт нужно было отдать системному администратору, который ставил задание в очередь и, после его выполнения, отдавал распечатку с результатами.
Такой режим нельзя назвать удобным (хотя именно в таком режиме эффективность работы компьютера максимальна), и лет через десять появились терминалы – устройства, включавшие в себя дисплей и клавиатуру. Терминал подключался к центральному компьютеру кабелем. Первые терминалы были малоинтеллектуальными, их даже называли 'тупыми' (dumb): все, что они умели делать – это сообщить центральному компьютеру, какая клавиша нажата и, приняв от него управляющую команду, отобразить символ на дисплее. (В качестве терминалов поначалу использовали устройства телексной связи – телетайпы, отсюда и небогатый набор их возможностей.) Чуть позже поняли, что если терминал снабдить своим простеньким процессором и оперативной памятью, то самому центральному компьютеру придется меньше заниматься непродуктивной работой.
Также оказалось удобно, если терминал стоит на столе у человека, который им пользуется, даже если этот стол находится не в том же здании, что и центральный компьютер. Так появились модемы, предоставившие терминалам возможность связываться со своими центральными компьютерами по телефонным сетям.
До сих пор информационные и финансовые агентства (например, Reiter и Bloomberg) предоставляют доступ к своей информации именно с помощью терминалов. Именно из решения проблем связи терминалов с центральными компьютерами и выросла вся индустрия сетей передачи данных.
Надо понимать, что на западе до сих пор очень остро стоит проблема 'унаследованных' (inherited) систем: многие крупные организации до сих пор в своей работе используют мэйнфреймы и терминалы, и критическая масса их данных находится именно там. В то же время в России массовая компьютеризация началась в конце 1980-х годов и почти целиком опиралась на IBM PC-совместимые персональные компьютеры. Только в редких крупных организациях необходимость объемных вычислений и/или повышенные требования к надежности приводили к использованию "больших" ЭВМ, таких, как IBM AS/400, различные серверы и рабочие станции фирмы Sun и т.п. Компьютеры же класса IBM System/360 (ЕС ЭВМ), до такой степени распространенные на западе, что фирма Microsoft включила в состав своего пакета серверных приложений BackOffice сервер связи с такими компьютерами (SNA Server), в России практически прекратили существование.
Обычная дорога к сетям для наших организаций и фирм выглядела так: есть несколько IBM PC – совместимых компьютеров. На них вводятся тексты, строятся таблицы, выполняются расчеты. Текстовые файлы, файлы электронных таблиц, рисунков, данные и результаты расчетов постоянно нужно переносить с компьютера на компьютер. Для этого пользуются дискетами. Пока объемы данных невелики, и обрабатывать эти данные можно по очереди, особых проблем не возникает. Однако вскоре появляется желание, например, собрать все данные о продажах в базу данных, и сделать так, чтобы несколько продавцов могли одновременно выписывать счета и фиксировать оплаты товара так, чтобы остальные сразу видели эти новые счета и записи об оплатах. Бегать с дискетой после каждого выписанного счета – нереально. И тут выясняется, что можно приобрести недорогие сетевые карты для каждого из компьютеров, соединить их кабелем, установить специальное сетевое программное обеспечение, и проблема может быть решена. Это путь "от удобства".
Другой путь к сетям лежит "от экономии". Зачем нужно тратить деньги на несколько полноценных компьютеров для машинисток, если можно приобрести один компьютер помощнее, с большим объемом дисковой памяти, несколько машин совсем без жестких дисков, и соединить их в сеть. Тогда более слабые компьютеры смогут пользоваться дисковым пространством более мощного компьютера. Вот и экономия – стоимость нескольких жестких дисков заметно больше стоимости требуемого сетевого оборудования. Наконец, путь "от моды". Когда все знакомые, соседи и конкуренты уже поставили себе локальные сети, то, наверное, в этом есть какой-то смысл. И хотя насущной необходимости пока нет, стоит держаться в русле технического прогресса. Как правило, и в этом случае оказывается, что сеть помогает упростить жизнь и приносит пользу.
