Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Алгоритмы замещения страниц

Читайте также:
  1. B) созылмалыгастритте 1 страница
  2. B) созылмалыгастритте 1 страница
  3. B) созылмалыгастритте 2 страница
  4. B) созылмалыгастритте 2 страница
  5. B) созылмалыгастритте 3 страница
  6. B) созылмалыгастритте 3 страница
  7. B) созылмалыгастритте 4 страница
  8. B) созылмалыгастритте 4 страница
  9. C) Происходит разрыв страницы.
  10. C) Происходит разрыв страницы.

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

Но этот алгоритм не осуществим, т.к. нельзя знать какую страницу, когда запросят. Можно лишь набрать статистику использования.

46) FIFO (акроним First In, First Out — «первым пришёл — первым ушёл») — способ организации и манипулирования данными относительно времени и приоритетов. Это выражение описывает принцип технической обработки очереди или обслуживания конфликтных требований путём упорядочения процесса по принципу: «первым пришёл — первым обслужен» (ПППО). Тот, кто приходит первым, тот и обслуживается первым, пришедший следующим ждёт, пока обслуживание первого не будет закончено, и так далее.

Этот принцип аналогичен поведению лиц, стоящих в очереди, когда люди получают обслуживание в том порядке, в котором они занимали очередь. То же самое происходит, например, на нерегулируемом перекрёстке, когда водители ожидают своей очереди на продолжение движения (в американских ПДД нет правила «помеха справа», приоритет определяется по принципу FIFO). ПППО также используется как сокращённое название для алгоритма FIFO планирования работы операционной системы, по которому процессорное время выделяется каждому процессу в порядке их поступления на обслуживание. В более широком смысле, абстракция LIFO или Last-In-First-Out («последним пришёл — первым ушёл») является противоположностью абстракции FIFO. Разница, возможно, станет яснее, если принять во внимание реже используемый синоним FILO, означающий First-In-Last-Out («первым пришёл — последним ушёл»). В сущности, обе абстракции являются конкретными случаями более общего понятия работы со списком. Разница не в списке (данных), а в правиле доступа к содержимому. В первом случае добавление делается к одному концу списка, а снятие с другого, во втором случае добавление и снятие делается на одном конце.

47) LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.

Для реализации этого метода нам понадобятся две структуры данных:

  1. Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
  2. Очередь с приоритетами timeQueue. Структура, которая поддерживает следующие операции:



Дата добавления: 2014-12-19; просмотров: 53 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав