Выталкивание дольше всего не использовавшейся страницы. Алгоритм LRU

Одним из приближений к алгоритму OPT является алгоритм, исходящий из эвристического правила, что недавнее прошлое - хороший ориентир для прогнозирования ближайшего будущего.

Ключевое отличие между FIFO и оптимальным алгоритмом заключается в том, что один смотрит назад, а другой вперед. Если использовать прошлое для аппроксимации будущего, имеет смысл замещать страницу, которая не использовалась в течение самого долгого времени. Такой подход называется least recently used алгоритм ( LRU ). Работа алгоритма проиллюстрирована на рис. рис. 10.2. Сравнивая рис. 10.1 b и 10.2, можно увидеть, что использование LRU алгоритма позволяет сократить количество страничных нарушений.

Рис. 10.2.Пример работы алгоритма LRU

LRU - хороший, но труднореализуемый алгоритм. Необходимо иметь связанный список всех страниц в памяти, в начале которого будут хранится недавно использованные страницы. Причем этот список должен обновляться при каждом обращении к памяти. Много времени нужно и на поиск страниц в таком списке.

1. Описать алгоритм вытеснения из кэша NFU.

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

Программная реализация алгоритма, близкого к LRU, - алгоритм NFU(Not Frequently Used).

Для него требуются программные счетчики, по одному на каждую страницу, которые сначала равны нулю. При каждом прерывании по времени (а не после каждой инструкции) операционная система сканирует все страницы в памяти и у каждой страницы с установленным флагом обращения увеличивает на единицу значение счетчика, а флаг обращения сбрасывает.

Таким образом, кандидатом на освобождение оказывается страница с наименьшим значением счетчика, как страница, к которой реже всего обращались. Главный недостаток алгоритма NFU состоит в том, что он ничего не забывает. Например, страница, к которой очень часто обращались в течение некоторого времени, а потом обращаться перестали, все равно не будет удалена из памяти, потому что ее счетчик содержит большую величину. Например, в многопроходных компиляторах страницы, которые активно использовались во время первого прохода, могут надолго сохранить большие значения счетчика, мешая загрузке полезных в дальнейшем страниц.

К счастью, возможна небольшая модификация алгоритма, которая позволяет ему "забывать". Достаточно, чтобы при каждом прерывании по времени содержимое счетчика сдвигалось вправо на 1 бит, а уже затем производилось бы его увеличение для страниц с установленным флагом обращения.

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

Лекция №6. Сети

1. Понятие и основные признаки локальной вычислительной сети.

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

Отличительные признаки ЛВС:

n Высокая скорость передачи информации, большая пропускная способность сети.

n Низкий уровень ошибок передачи (или, что тоже самое, высококачественные каналы связи).

n Эффективный, быстродействующий механизм управления обменом по сети.

n Заранее четко ограниченное количество компьютеров, подключаемых к сети.

2. Определения: абонент сети, сервер, клиент.

Абонент (узел, хост, станция) — это устройство, подключенное к сети и активно участвующее в информационном обмене.

Сервером называется абонент (узел) сети, который предоставляет свои ресурсы другим абонентам.

Клиентом называется абонент сети, который использует сетевые ресурсы.

3. Перечислить основные факторы, влияющие на работоспособность сети.

Исправность абонентов сети

Исправность сетевого оборудования

Целостность кабеля сети

Ограничение длины кабеля

4. Перечислить базовые топологии сети.

Под топологией (компоновкой, конфигурацией, структурой) компьютерной сети обычно понимается физическое расположение компьютеров сети друг относительно друга и способ соединения их линиями связи.

Существует три базовые топологии сети:

n Шина,

n Звезда,

n Кольцо.

5. Перечислить производные топологии сети.

Активное/пассивное дерево

Звездно-шинная топология (star-bus)

Звездно-кольцевая топология (star-ring)

Сеточная топология (полная/частичная)

6. Назначение терминаторов.

Казалось бы, при обрыве кабеля получаются две вполне работоспособные шины. Однако надо учитывать, что из-за особенностей распространения электрических сигналов по длинным линиям связи необходимо предусматривать включение на концах шины специальных согласующих устройств, терминаторов. Без включения терминаторов сигнал отражается от конца линии и искажается так, что связь по сети становится невозможной. В случае разрыва или повреждения кабеля нарушается согласование линии связи, и прекращается обмен даже между теми компьютерами, которые остались соединенными между собой.

7. Назначение повторителей.

Повторители – это устройства, усиливающие электрические сигналы и обеспечивающие сохранение формы и амплитуды сигнала при передаче его на большие расстояния. Описываются протоколами канального уровня модели OSI и могут объединять сети, отличающиеся протоколами лишь на физическом уровне ( с одинаковыми протоколами на канальном и выше уровнях ) и выполняют лишь регенерацию пакетов данных, обеспечивая тем самым электрическую независимость сопрягаемых сетей и защиту сигналов от воздействия помех. Использование повторителей позволяет расширить протяженность одной сети за счет объединения нескольких сегментов сети в единое целое. При установке повторителя создается физический разрыв линии связи, при этом сигнал воспринимается с одной стороны, регенерируется и направляется к другой части линии связи.

8. Назначение концентраторов.

Концентратор (хаб) используется, если в сети участвует больше 2 компьютеров. К нему сходятся все сетевые кабели витой пары в топологии звезда. Сигнал хаба получают все ПК сети, а не только та сетевая карта, которой адресован пакет данных. В настоящее время концентраторы сняты с производства и встречаются редко. Внешне свитч или коммутатор (Switch) практически не отличается от Hub, но коммутатор (Switch) - более интеллектуальное устройство, где есть свой процессор, внутренняя шина и буферная память. Если концентратор просто передает пакеты от одного порта ко всем остальным, то Switch анализирует Mac адреса, откуда и куда отправлен пакет информации и соединяет только эти компьютеры, в то время как остальные каналы остаются свободными. Это позволяет намного увеличить производительность сети, так как уменьшает количество паразитного трафика и обеспечивает большую фактическую скорость передачи данных, особенно в сетях с большим количеством пользователей

9. Назначение маршрутизаторов.

Маршрутизатор - сетевое устройство, которое на основании информации о топологии сети и определённых правил принимает решения о пересылке пакетов между различными сегментами сети. В отличии от коммутатора, маршрутизатор видит все связи подсетей друг с другом, поэтому он может выбрать наилучший маршрут и при наличии нескольких альтернативных маршрутов. Решение о выборе маршрута принимается каждым маршрутизатором, через который проходит сообщение. Если в таблице маршрутизации для адреса нет описанного маршрута, пакет отбрасывается.

10. Преимущества и недостатки топологии «шина».

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

Поскольку центральный абонент отсутствует, разрешение возможных конфликтов в данном случае ложится на сетевое оборудование каждого отдельного абонента. В связи с этим сетевая аппаратура при топологии шина сложнее, чем при других топологиях. Тем не менее из-за широкого распространения сетей с топологией шина (прежде всего наиболее популярной сети Ethernet) стоимость сетевого оборудования не слишком высока.

11. Преимущества и недостатки топологии «звезда».

Звезда — это единственная топология сети с явно выделенным центром, к которому подключаются все остальные абоненты. Обмен информацией идет исключительно через центральный компьютер, на который ложится большая нагрузка, поэтому ничем другим, кроме сети, он, как правило, заниматься не может. Понятно, что сетевое оборудование центрального абонента должно быть существенно более сложным, чем оборудование периферийных абонентов. О равноправии всех абонентов (как в шине) в данном случае говорить не приходится. Обычно центральный компьютер самый мощный, именно на него возлагаются все функции по управлению обменом. Никакие конфликты в сети с топологией звезда в принципе невозможны, так как управление полностью централизовано.

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

Обрыв кабеля или короткое замыкание в нем при топологии звезда нарушает обмен только с одним компьютером, а все остальные компьютеры могут нормально продолжать работу.

Серьезный недостаток топологии звезда состоит в жестком ограничении количества абонентов. Обычно центральный абонент может обслуживать не более 8—16 периферийных абонентов. В этих пределах подключение новых абонентов довольно просто, но за ними оно просто невозможно. В звезде допустимо подключение вместо периферийного еще одного центрального абонента (в результате получается топология из нескольких соединенных между собой звезд).

12. Преимущества и недостатки топологии «кольцо».

На каждой линии связи, как и в случае звезды, работает только один передатчик и один приемник (связь типа точка-точка). Это позволяет отказаться от применения внешних терминаторов.

Важная особенность кольца состоит в том, что каждый компьютер ретранслирует (восстанавливает, усиливает) приходящий к нему сигнал, то есть выступает в роли репитера. Затухание сигнала во всем кольце не имеет никакого значения, важно только затухание между соседними компьютерами кольца. Если предельная длина кабеля, ограниченная затуханием, составляет L_пр, то суммарная длина кольца может достигать NL_пр, где N — количество компьютеров в кольце. Полный размер сети в пределе будет NL_пр/2, так как кольцо придется сложить вдвое. На практике размеры кольцевых сетей достигают десятков километров (например, в сети FDDI). Кольцо в этом отношении существенно превосходит любые другие топологии.

Четко выделенного центра при кольцевой топологии нет, все компьютеры могут быть одинаковыми и равноправными. Однако довольно часто в кольце выделяется специальный абонент, который управляет обменом или контролирует его. Понятно, что наличие такого единственного управляющего абонента снижает надежность сети, так как выход его из строя сразу же парализует весь обмен.

Точно так же обрыв или короткое замыкание в любом из кабелей кольца делает работу всей сети невозможной. Из трех рассмотренных топологий кольцо наиболее уязвимо к повреждениям кабеля, поэтому в случае топологии кольца обычно предусматривают прокладку двух (или более) параллельных линий связи, одна из которых находится в резерве.

13. Описать структуру сетевого пакета.

Сетевой пакет - блок данных, передаваемый на сетевом уровне между абонентом-отправителем и абонентом-получателем.

От размера пакета зависят:

n время доступа к сети,

n накладные расходы,

n вероятность повторной передачи пакета при ошибке.

Обычно пакет содержит следующие основные поля:

n Преамбула,

n Сетевой адрес абонента-получателя,

n Сетевой адрес абонента-отправителя,

n Служебная информация (тип пакета, номер, маршрут),

n Данные,

n Контрольная сумма,

n Стоповая комбинация.

14. Взаимодействие абонентов сети: метод дейтаграмм.

Метод дейтаграмм – это простейший метод, в котором каждый пакет рассматривается как самостоятельный объект

Пакет при этом методе передается без установления логического канала, то есть без предварительного обмена служебными пакетами для выяснения готовности приемника, а также без ликвидации логического канала, то есть без пакета подтверждения окончания передачи. Дойдет пакет до приемника или нет – неизвестно (проверка факта получения переносится на более высокие уровни).

Метод дейтаграмм предъявляет повышенные требования к аппаратуре (так как приемник всегда должен быть готов к приему пакета). Достоинства метода в том, что передатчик и приемник работают независимо друг от друга, к тому же пакеты могут накапливаться в буфере и затем передаваться вместе, можно также использовать широковещательную передачу, то есть адресовать пакет всем абонентам одновременно. Недостатки метода – это возможность потери пакетов, а также бесполезной загрузки сети пакетами в случае отсутствия или неготовности приемника.

15. Взаимодействие абонентов сети: метод с логическим соединением.

Метод с логическим соединением разработан позднее, чем метод дейтаграмм, и отличается усложненным порядком взаимодействия.

При этом методе пакет передается только после того, как будет установлено логическое соединение (канал) между приемником и передатчиком. Каждому информационному пакету сопутствует один или несколько служебных пакетов (установка соединения, подтверждение получения, запрос повторной передачи, разрыв соединения). Логический канал может устанавливаться на время передачи одного или нескольких пакетов.

16. Что такое инкапсуляция/декапсуляция пакетов?

При реальном обмене по сети применяются многоуровневые протоколы, каждый из уровней которых предполагает свою структуру пакета. Все пакеты более высоких уровней последовательно вкладываются отправителем в поле данных передаваемого пакета.

Такой процесс последовательной упаковки данных для передачи называется инкапсуляцией пакетов.

Обратный процесс последовательной распаковки данных приемником называется декапсуляцией пакетов.

17. Перечислить уровни эталонной модели ISO/OSI.

Все сетевые функции
в модели разделены
на 7 уровней:

7. Прикладной

6. Представительский

5. Сеансовый

4. Транспортный

3. Сетевой

2. Канальный

1. Физический

18. Принцип функционирования эталонной модели ISO/OSI.

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

Цель нижестоящего уровня – предоставление услуг вышестоящему уровню, причем вышестоящему уровню не важны детали выполнения этих услуг. Нижестоящие уровни выполняют более простые и конкретные функции.

Каждый уровень отправителя взаимодействует с таким же уровнем получателя.

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

19. На каком уровне модели ISO/OSI функционируют концентраторы и почему?

Уровень 1 – физический. Этот уровень связан с работой hardware. На нем определяются физические аспекты передачи информации по линиям связи, такие как: напряжения, частоты, природа передающей среды, способ передачи двоичной информации по физическому носителю, вплоть до размеров и формы используемых разъемов. В компьютерах за поддержку физического уровня обычно отвечает сетевой адаптер.

20. На каком уровне модели ISO/OSI функционируют маршрутизаторы и почему?

Уровень 3 – сетевой. Сетевой уровень несет ответственность за доставку информации от узла-отправителя к узлу-получателю. На этом уровне частично решаются вопросы адресации, осуществляется выбор маршрутов следования пакетов данных, решаются вопросы стыковки сетей, а также управление скоростью передачи информации для предотвращения перегрузок в сети.