В качестве хобби пишу свою ОС. Неспрашивайте зачем, мне это просто доставляет массу удовольствия Решил добавить свопинг, т.е. отгрузку на винт неиспользуемых страниц. С технической реализацией проблем возникнуть недолжно, однако просидев целый день я так и непонял самого главного: собственно какие страницы, и когда нужно отгружать. Ясно что отгружать нужно максимально давно неиспользуемые страницы, но как их определить? Как определить что страница давно не использовалась? В таблице директорий страниц, у каждой страницы есть бит доступа, он устанавливается процессором при обращении к странице, и сбрасывается операционной системой. Когда сбрасывать этот бит? Страниц огромное количество, и у каждого процесса свой каталог страниц... Какую информацию можно извлечь из этого бита? Тоесть какой можно придумать алгоритм для нахождения максимально давно неиспользуемых страниц?
Алгоритмов, на самом деле, множество. Если так уж охота сделать NRU (Not Recently Used), то в рабочем наборе храни дополнительное поле "время последнего обращения" и, в принципе, этого хватит. Алгоритмы выбора количества страниц для свопинга тоже интересные, там тоже можно крепко задуматься. Поэтому, чтобы сильно не напрягаться, имеет смысл прочитать что-нибудь типа A.Tanenbum "Modern Operating System" или хотя бы M.Russinovich, D.Solomon "Inside Windows 2000". Взять их можно в магазине (перевод), в интернет-магазине (оригинал и перевод) или попытать счастья в других местах, типа гугла.
Другой вариант - добавь к каждой странице два поля - и организуй ими двунаправленный список. Страницу, к которой было самое последнее обращение, всегда поднимай в самый верх в этом списке (вытаскивай из, и перецепляй в голову). Тогда в самом хвосте автоматически хранятся самые старые. По сравнению со штампом времени: это медленнее в момент доступа к странице, но быстрее в момент выбора, какие страницы свопить. Много страниц, но используется небольшой их процент - используй список. Мало страниц или очень большой процент из них используется - используй штамп времени. P.S. Под "обращением" конечно же не понимается каждое чтение/запись байта, иначе скорость работы ОС замедлится в N раз :-(
Реализация алгоритма LRU (счетчик, стек): http://www.cs.nyu.edu/courses/spring02/V22.0202-001/lectures/lect14.pd f http://www.cs.nyu.edu/courses/spring02/V22.0202-001/lectures/lect15.pd f
