Классические алгоритмы, доминирующие в операционных системах

задняя часть Операционная система

В этой статье вы разберетесь, какие алгоритмы появились в операционной системе.

Алгоритмы управления процессами и потоками

В планировании процессов и потоков было много алгоритмов.Когда компьютер представляет собой мультипрограммную систему, часто существует множество процессов или потоков, конкурирующих за квоты процессорного времени в одно и то же время.. Итак, как выбрать правильный процесс/поток для запуска — это искусство. Это происходит, когда два или более процессов/потоков находятся в состоянии готовности. Если доступен только один ЦП, то он должен выбрать, какой процесс/поток может выполняться следующим. Есть операционная система под названием调度程序(scheduler)Роль существует, она делает это, алгоритм, используемый планировщиком, называется调度算法(scheduling algorithm).

Классификация алгоритмов планирования

Для разных сред операционных систем также существуют разные классификации алгоритмов.Операционные системы в основном делятся на следующие категории:

  • пакетная операционная система
  • интерактивная операционная система
  • операционная система реального времени

Давайте рассмотрим алгоритмы в этих операционных системах отдельно.

Алгоритмы в пакетных операционных системах

Цели дизайна

批处理系统Широко используется в сферах бизнеса, таких как обработка платежной ведомости, инвентаризации, квитанций по счетам, расходов по счетам, расчетов процентов, обработки претензий и других периодических работ. В периодической системе обычно выбирают использование非抢占式算法или周期性比较长из抢占式算法. Такой подход снижает количество переключений между потоками и, таким образом, повышает производительность.

существует交互式用户环境, потому что для удобства пользователя это не будет занимать процесс в течение длительного времени, поэтому необходимо抢占式算法. Также возможно исключить все остальные процессы на неопределенный срок из-за ошибки в одном процессе. Чтобы избежать этой ситуации, также необходимо упреждение.

существует实时系统, упреждающий не нужен, потому что процесс знает, что он может долго не запускаться, и обычно быстро заканчивает свою работу и зависает.

ключевой индикатор

обычно имеют三个指标Для измерения рабочего состояния системы:Пропускная способность, время обработки и загрузка ЦП

  • 吞吐量(throughout)количество заданий, выполняемых системой в час. Учитывая все обстоятельства, 50 заданий в час лучше, чем 40 заданий в час.
  • 周转时间(Turnaround time)— это среднее время, которое относится к среднему времени от отправки пакета до момента завершения задания. Эти данные измеряют среднее время ожидания пользователями результатов. Чем меньше время оборота, тем лучше.
  • CPU 利用率(CPU utilization)Обычно в качестве метрики в пакетных системах. Тем не менее, загрузка ЦП не является хорошей метрикой, действительно ценной метрикой является то, сколько заданий система может выполнять в час (пропускная способность) и сколько времени требуется для выполнения заданий (время выполнения).

Рассмотрим алгоритм пакетной обработки.

Первый пришел первый обслужен

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

Сила этого алгоритма в том, что易于理解и编程, в этом алгоритме односвязный список записывает все готовые процессы. Чтобы выбрать процесс для запуска, просто удалите процесс из головы очереди; чтобы добавить новое задание или заблокировать процесс, просто добавьте задание или процесс в конец очереди. Это очень простая реализация.

Однако у принципа «первым пришел - первым обслужен» есть и недостаток, то есть нет отношения приоритетов.Представьте, если в очереди стоят 100 процессов ввода-вывода, а 101-й процесс интенсивно использует ЦП, разве ему не нужно ждать? for 100 Процесс ввода-вывода будет ожидать только запуска процесса, интенсивно использующего ЦП, после запуска, что на практике невозможно, поэтому необходимо появление приоритетных или вытесняющих процессов, чтобы определить приоритет важных процессов для запуска.

сначала самая короткая работа

Второй алгоритм планирования в пакетной обработке:最短作业优先(Shortest Job First)Предположим, что время выполнения известно. Например, страховая компания должна выполнять одинаковую работу каждый день, поэтому люди могут предсказать, сколько времени потребуется, чтобы справиться с партией домашних заданий по 1000 требований. Когда во входной очереди находится несколько одинаково важных заданий, планировщик должен использовать алгоритм задания с кратчайшим приоритетом.

Как показано на рисунке а выше, имеется 4 задания A, B, C, D со временем выполнения 8, 4, 4 и 4 минуты соответственно. Работая в порядке, показанном на диаграмме, время оборота для A составляет 8 минут, B — 12 минут, C — 16 минут, D — 20 минут, а среднее время — 14 минут.

Теперь рассмотрим запуск 4 заданий с использованием алгоритма «Сначала самое короткое задание», как показано на рис. b выше. Текущее время обработки составляет 4, 8, 12, 20, а среднее значение составляет 11 минут, что может доказать, что самое короткое задание сначала является оптимальным. Рассмотрим случай 4 заданий со временем выполнения a, b, c, d. Первая работа заканчивается в момент времени а, вторая — в момент времени а + b и так далее. Среднее время оборота составляет (4a + 3b + 2c + d) / 4 . Очевидно, что a оказывает наибольшее влияние на среднее значение, поэтому a должна быть самой короткой первой работой, за которой следует b, затем c и, наконец, d. Это может повлиять только на собственное время выполнения.

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

Кратчайшее оставшееся время сначала

Упреждающая версия кратчайшего задания сначала называется最短剩余时间优先(Shortest Remaining Time Next)алгоритм. Используя этот алгоритм, планировщик всегда выбирает процесс с наименьшим оставшимся временем выполнения для запуска. Когда поступает новое задание, все его время сравнивается с оставшимся временем текущего процесса. Если новый процесс занимает меньше времени, чем текущий процесс, текущий процесс приостанавливается и запускается новый процесс. Таким образом, краткосрочные рабочие места могут быть хорошо обслужены.

Планирование в интерактивных системах

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

круговое планирование

Один из старейших, простейших, честных и широко используемых алгоритмов —轮询算法(round-robin). Каждому процессу назначается период времени, называемый时间片(quantum), процесс может выполняться в течение этого интервала времени. Если процесс блокируется или завершается до окончания кванта времени, процессор немедленно переключается. Алгоритм опроса относительно прост в реализации. Что делает планировщик, так это поддерживает список запущенных процессов, как на рисунке ниже, и когда у процесса заканчиваются кванты времени, он перемещается в конец очереди, как b на рисунке ниже.

Единственным интересным аспектом циклического планирования временных интервалов является длина временного интервала. Переключение с одного процесса на другой требует некоторого времени на административную обработку, включая сохранение значений регистров и карт памяти, обновление различных таблиц и списков, очистку и перезагрузку кэшей памяти и так далее. Этот переключатель называется进程间切换(process switch)и上下文切换(context switch).

приоритетное планирование

Круговое планирование предполагает, что все процессы одинаково важны. Но это может быть не так. Например, иерархия в университете начинается с деканов, затем профессоров, секретарей, вспомогательного персонала и, наконец, студентов. Это достигается за счет учета внешней ситуации.优先级调度(priority scheduling)

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

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

Очень удобно разделить группу процессов на несколько классов по приоритету, и использовать приоритетное планирование среди каждого класса, а внутри каждого типа процесса использовать циклическое планирование. Ниже показана система из четырех классов приоритета.

Алгоритм его планирования в основном описывается следующим образом: имеются запущенные процессы с приоритетом выше 4-х типов, сначала каждый процесс будет выполняться в течение кванта времени по методу циклического перебора, а процессы с более низким приоритетом будут игнорироваться на этом этапе. время. Если процесс четвертого типа пуст, процесс третьего типа запускается в режиме опроса. Если процессы типа 4 и типа 3 пусты, запустите процесс типа 2 в циклическом режиме. Если приоритет не отрегулирован, низкоприоритетный процесс склонен к голоданию.

сначала самый короткий процесс

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

Один из способов состоит в том, чтобы строить предположения на основе прошлого поведения процесса и выполнять процесс с наименьшим расчетным временем выполнения. Предположим, что расчетное время выполнения каждой команды на каждом терминале равноT0, теперь предположим, что время его следующего выполнения измеряется какT1, расчетное время может быть улучшено путем взвешивания двух значений, т.е.aT0+ (1- 1)T1. Выбирая значение a, вы можете решить, следует ли как можно скорее забыть о старых средах выполнения или запомнить их надолго. Когда a = 1/2, можно получить следующую последовательность

Видно, что после трех раундов доля T0 в новой оценке снизилась до 1/8.

Этот метод получения следующей оценки путем взятия средневзвешенного значения текущего измерения и предыдущей оценки иногда называют老化(aging). Этот метод использует много случаев, когда прогнозируемое значение основано на текущем значении.

Гарантированное планирование

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

расписание лотереи

Обещать пользователям, а затем выполнить это обещание — это хорошо, но это трудно выполнить. Но есть алгоритм, который может и давать прогнозы, и иметь более простую реализацию, а именно彩票调度(lottery scheduling)алгоритм.

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

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

Лотерейный билет можно понимать как бафф, этот бафф с вероятностью 15% позволяет сгенерировать速度之靴Эффект.

Справедливое распределение по расписанию

До сих пор мы предполагали, что сами процессы планируются независимо от того, кто ими владеет. В результате, если пользователь 1 запустит 9 процессов, а пользователь 2 запустит процесс, используя циклический алгоритм или алгоритм планирования с равным приоритетом, то пользователь 1 получит 90% процессорного времени, а пользователь 2 получит 10% процессорного времени. время.

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

Планирование в системах реального времени

实时系统(real-time)Критические по времени системы. Системы реального времени можно разделить на две категории:硬实时(hard real time)и软实时(soft real time)Система, первое означает, что должен быть соблюден абсолютный крайний срок; второе означает, что, хотя случайный срок не может быть пропущен, с ним можно мириться. В обоих случаях режим реального времени достигается за счет разделения программы на набор процессов, где поведение каждого процесса предсказуемо и известно заранее. Эти процессы, как правило, недолговечны и очень быстро завершаются. При обнаружении внешнего сигнала задача планировщика состоит в том, чтобы запланировать процессы так, чтобы уложиться во все сроки.

События в системе реального времени можно дополнительно классифицировать на周期性(以规则的时间间隔发生)событие или非周期性(发生时间不可预知)событие. Системе может потребоваться реагировать на несколько периодических потоков событий, и в зависимости от того, сколько времени требуется для обработки каждого события, она может быть даже не в состоянии обработать их все. Например, если есть m периодических событий, событие i происходит в период Pi и требует Ci секунд процессорного времени для обработки одного события, то нагрузка может быть обработана, если

Только системы реального времени, которые удовлетворяют этому условию, называются可调度的, что означает, что это действительно может быть реализовано. Процесс, не прошедший этот тест, не может быть запланирован, поскольку сумма времени ЦП, требуемого этими процессами, больше, чем время, которое может предоставить ЦП.

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

Политики и механизмы планирования

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

Решение проблемы заключается в调度机制(scheduling mechanism)и调度策略(scheduling policy)Отдельно, это долгосрочный последовательный принцип. Это также означает, что алгоритм планирования каким-то образом параметризован, но параметры могут быть заполнены пользовательским процессом. Давайте сначала рассмотрим пример с базой данных. Предположим, что ядро ​​использует алгоритм планирования приоритетов и предоставляет системный вызов, позволяющий процессам устанавливать приоритеты. Таким образом, хотя сам родительский процесс не участвует в планировании, он может управлять деталями планирования дочерних процессов. Механизм планирования находится в ядре, а политика планирования определяется пользовательским процессом.Разделение политики планирования и механизма является ключевой идеей.

Алгоритмы управления памятью

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

В операционной системе есть два метода управления памятью, один из них位图, один链表.

Существует несколько вариантов подхода при использовании связанных списков для управления памятью.

При хранении процессов и свободных областей в связном списке в порядке адресов существует несколько алгоритмов выделения памяти для создаваемого процесса (или выгружаемого с диска). Начнем с того, что предположим, что диспетчер памяти знает, сколько памяти должно быть выделено, самый простой алгоритм — использовать首次适配(first fit). Диспетчер памяти просматривает список сегментов, пока не найдет достаточно большую свободную область. Если размер свободной области не совпадает с размером выделяемого пространства, свободная область делится на две части, одна часть используется процессом, а другая часть генерирует новую свободную область. Алгоритм первого подбора является быстрым алгоритмом, потому что он ищет в связанном списке как можно больше.

Небольшой вариант первой подгонки下次适配(next fit). Он работает так же, как и первое совпадение, с той лишь разницей, что следующая подгонка будет записывать текущую позицию каждый раз, когда находит подходящую свободную область, так что в следующий раз, когда вы найдете свободную область, она начнется с того места, где она закончилась. поиск в последний раз вместо того, чтобы начинать каждый раз с начала, как это делает алгоритм первого совпадения.Bays(1997)доказалПроизводительность следующего алгоритма сопоставления немного ниже, чем у первого алгоритма сопоставления..

Еще одним известным и широко используемым алгоритмом является最佳适配(best fit). Наилучшее соответствие будет выполнять поиск по всему связанному списку от начала до конца, чтобы найти наименьшую свободную область, которая может вместить процесс. Алгоритм наилучшего соответствия попытается найти свободную область, наиболее близкую к фактической потребности, чтобы наилучшим образом соответствовать запросу и доступной свободной области, вместо того, чтобы разбивать большую свободную область по одной, которая может быть использована позже. Например, сейчас нам нужен блок размером 2, тогда первый алгоритм сопоставления выделит блок в свободной области позиции 5, а алгоритм наилучшего соответствия выделит блок в свободной области позиции 18, следующее

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

Наиболее подходящая свободная область будет разделена на множество очень маленьких буферов. Чтобы избежать этой проблемы, рассмотрите возможность использования最差适配(worst fit)алгоритм. То есть всегда выделяйте наибольшую область памяти (так что теперь вы понимаете, почему алгоритм наилучшего соответствия разделяет множество небольших буферов), увеличивая вновь выделенную свободную область, чтобы ее можно было продолжать использовать. Программы моделирования показывают, что алгоритм наихудшего соответствия также не является хорошей идеей.

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

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

Другой алгоритм распределения快速适配(quick fit)Алгоритм, поддерживающий отдельные связанные списки для свободных областей обычных размеров. Например, есть таблица из n элементов, первый элемент таблицы является указателем на заголовок связанного списка свободной области размером 4 КБ, второй элемент является указателем на заголовок связанного списка свободной области размера размером 8 КБ, а третий элемент — указатель на начало связанного списка свободной области размером 12 КБ и так далее. Например, такая свободная область, как 21 КБ, может быть помещена в связанный список размером 20 КБ или может быть помещена в связанный список свободной области со специальным размером хранилища.

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

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

Алгоритмов замены страниц много, давайте познакомимся с ними вместе

Когда происходит ошибка страницы, операционная система выбирает страницу для замены, чтобы освободить место для новой страницы. Если выгружаемая страница находится в памяти已经被修改, то его необходимо записать на диск, чтобы сделать копию диска保持最新状态. Если страница не изменялась и копия на диске актуальна, то不需要переписать. Затем просто используйте загруженную страницу, чтобы закрыть страницу, которую необходимо удалить.

Когда происходит сбой страницы, хотя страница может быть выбрана для замены случайным образом, если каждый раз выбирается редко используемая страница, производительность системы улучшится. Если часто используемая страница выгружена, то эта страница может повторно использоваться через короткое время, что может привести к дополнительным потерям производительности. Их много на тему о странице页面置换算法(page replacement algorithms), которые были доказаны теоретически и практически.

Теперь давайте обсудим, какие существуют алгоритмы замены страниц.

оптимальный алгоритм замены страницы

Алгоритм оптимальной замены страницы легко описать, но трудно реализовать на практике. Это работает следующим образом: когда происходит ошибка страницы, на одну из этих страниц будет ссылаться следующая инструкция (страница, содержащая инструкцию). Другие страницы не могут быть доступны до 10, 100 или 1000 инструкций. Каждая страница может быть помечена количеством инструкций, которые необходимо выполнить перед первым доступом к странице.

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

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

Алгоритм замены страницы в последнее время не использовался

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

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

Если аппаратное обеспечение не имеет этих битов, то операционная система缺页中断и时钟中断механизм имитации. При запуске процесса пометить все его страницы как不在内存;После доступа к любой странице будет запущено прерывание по ошибке страницы, в это время операционная система может установитьR 位(在它的内部表中), измените запись таблицы страниц, чтобы она указывала на правильную страницу, и установите для нее значениеREAD ONLYрежиме, а затем перезапускает инструкцию, вызвавшую прерывание из-за ошибки страницы. Если впоследствии страница модифицируется, возникает другое исключение ошибки страницы. Это позволяет операционной системе установить бит M и установить режим страницы наREAD/WRITE.

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

Когда происходит ошибка страницы, операционная система проверяет все страницы и делит текущее значение на четыре категории в зависимости от их битов R и M:

  • Класс 0: без ссылки на R, без модификации M
  • Категория 1: без ссылки на R, модифицированный M
  • Категория 2: Эталонный R, без модификации M
  • Категория 3: доступ к R, модифицированный M

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

NRU(Not Recently Used)Алгоритм случайным образом удаляет страницу из непустого класса с наименьшим номером. Идея этого алгоритма заключается в том, что лучше удалить измененную, но неиспользуемую страницу в течение одного часа (~ 20 мс), чем неизмененную страницу с большим количеством ссылок.Основное преимущество NRU заключается в том, чтоЛегко понять и эффективно реализовать.

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

Другой менее затратный способ — использоватьFIFO(First-In,First-Out)Алгоритмы, этот тип структуры данных также работает в алгоритмах замены страниц. Связанный список всех страниц в текущей памяти поддерживается операционной системой, самые ранние введенные страницы помещаются в начало списка, а самые последние введенные страницы помещаются в конец списка. Когда происходит ошибка страницы, страница заголовка удаляется, а новая страница добавляется в нижний колонтитул.

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

  • При инициализации страницы нет, поэтому первый раз проверит есть ли страница 1 в связанном списке, если ее нет в связанном списке, то онаMISS, Страница 1 входит в связанный список, а направление FIFO связанного списка показано на рисунке.
  • Аналогично второй раз сначала проверит есть ли страница 2 в связанном списке, если ее нет в связанном списке, то страница 2 входит в связанный список, а статус такойMISS,И так далее.
  • Давайте посмотрим на четвертый раз, связанный список в это время1 2 3, в четвертый раз проверит страницу2Независимо от того, находится ли он в связанном списке, после поиска обнаруживается, что 2 находится в связанном списке, тогда состояниеHIT, и больше не будет ставиться в очередь и извлекаться из очереди, и то же самое верно в пятый раз.
  • Давайте посмотрим на шестой раз, связанный список в это время все еще1 2 3, так как операция ввода связанного списка ранее не выполнялась, страница5Он сначала проверит и обнаружит, что в связанном списке нет страницы 5, затем выполнит операцию входа в связанный список на странице 5, и выполнит операцию выхода из связанного списка на странице 2. Последовательность связанного списка после исполнение такое2 3 5.

Алгоритм замены страницы второго шанса

Страница связанного списка FIFO, о которой мы узнали выше, имеет缺陷, то есть проверки вне цепочки и внутри цепочки выполняться не будут.检查, часто используемые страницы будет легко заменить, чтобы избежать этой проблемы, мы делаем простую модификацию алгоритма: мы проверяем самые старые страницыR 位, если это 0 , то страница самая старая и неиспользуемая, тогда страница будет немедленно заменена. Если бит R равен 1, очистите этот бит, страница будет помещена в конец связанного списка, а время ее загрузки будет изменено, как если бы она была только что добавлена. Тогда продолжайте искать.

Этот алгоритм называется第二次机会(second chance)Алгоритм, как показано ниже, мы видим, что страницы от A до H хранятся в связанном списке, отсортированном по времени, когда они достигают памяти.

a) Страницы, упорядоченные в соответствии с методом «первым пришел — первым обслужен» b) Связанный список страниц, когда прерывание из-за ошибки страницы происходит в момент времени 20, и установлен бит R в A.

Предположим, что исключение page fault происходит в момент времени 20, а самой старой страницей в это время является A, которая прибыла в момент времени 0. Если бит R в A равен 0, то он будет сброшен из памяти или записан обратно на диск (если он был изменен) или просто отброшен (если он не был изменен). С другой стороны, если его бит R уже установлен, поместите A в конец списка и сбросьте его.装入时间является текущим моментом (в 20), а затем очищает бит R. Затем продолжите поиск подходящих страниц, начиная со страницы B.

Поиск второго шанса — это страницы, которые не посещались в течение самого последнего интервала времени. Если все страницы были посещены, алгоритм сводится к простомуFIFO 算法. В частности, предположим, что все страницы на рис. а имеют установленный бит R. ОС последовательно перемещает страницы в конец связанного списка, очищая бит R каждый раз, когда он добавляется в конец. Наконец, алгоритм вернется к странице A. В это время бит R был очищен, тогда страница A будет обработана вне цепочки, поэтому алгоритм может завершиться нормально.

Алгоритм замены страницы часов

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

При возникновении ошибки страницы алгоритм сначала проверяет страницу, на которую указывает указатель, если его бит R равен 0, он удаляет страницу, вставляет новую страницу в эту позицию, а затем перемещает указатель вперед на единицу; Бит R равен 0 1 очищает бит R и переводит стрелки на одну позицию вперед. Этот процесс повторяется до тех пор, пока не будет найдена позиция страницы, где бит R равен 0. Посмотрите, как работает этот алгоритм, и узнайте, почему он называется时钟(clokc)алгоритм.

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

Алгоритм замены страницы, который использовался реже всего, может быть следующим: страницы, которые часто используются в первых нескольких инструкциях и могут использоваться в следующих нескольких инструкциях. И наоборот, страницы, которые не использовались в течение длительного времени, могут не использоваться какое-то время в будущем. Эта идея раскрывает алгоритм, который может быть реализован: когда ошибка страницы прерывается, страница, которая не использовалась дольше всего, заменяется. Эта стратегия называетсяLRU(Least Recently Used), наименее недавно использовавшийся алгоритм замены страниц.

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

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

Эмулировать LRU в программном обеспечении

Хотя приведенный выше алгоритм LRU в принципе достижим,Но немногие машины могут иметь такое специальное оборудование.. Выше приведена аппаратная реализация, поэтому теперь рассмотрите возможность использования软件реализовать ЛРУ. Возможное решениеNFU(Not Frequently Used，最不常用)алгоритм. Для этого требуется программный счетчик, связанный с каждой страницей, который при инициализации равен 0. При каждом тактовом прерывании операционная система просматривает все страницы в памяти, добавляя бит R каждой страницы (0 или 1) к своему счетчику. Этот счетчик обычно отслеживает, как часто осуществляется доступ к каждой странице. Когда возникает исключительная ситуация ошибки страницы, заменяется страница с наименьшим значением счетчика.

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

К счастью, для того, чтобы заставить NFU эмулировать LRU, требуется всего лишь простая модификация, которая состоит из двух шагов.

  • Во-первых, счетчик сдвигается вправо на один бит перед добавлением бита R;
  • На втором этапе бит R добавляется к самому левому биту вместо самого правого бита.

Модифицированный алгоритм называется老化(aging)Алгоритм, рисунок ниже объясняет, как работает алгоритм старения.

Мы предполагаем, что в первом тактовом цикле биты R страниц 0–5 равны 1, 0, 1, 0, 1, 1, последовательно (то есть страница 0 равна 1, страница 1 равна 0, страница 2 равна 1, и так далее). Это,Между 0 тактовыми циклами и 1 тактовым циклом ссылаются на 0, 2, 4, 5., тем самым установив их бит R в 1 , а остальные в 0 . После того, как соответствующие шесть счетчиков сдвинуты вправо, бит R добавляется к左侧, как на рисунке выше. Остальные четыре столбца показывают шесть изменений счетчика за следующие четыре такта.

Когда возникает исключение ошибки страницы,置换（就是移除）Страница с наименьшим значением счетчика. Если к странице не обращались в предыдущие 4 такта, то ее счетчик должен иметь четыре последовательных 0, поэтому его значение должно быть выше, чем у страницы, к которой не обращались в предыдущие 3 такта.Счетчик мал .

Между этим алгоритмом и алгоритмом LRU есть два важных отличия: взгляните наe, третья и пятая колонки

Ни к одной из них не обращались в течение двух тактов, и к обеим страницам обращались в предыдущем такте. Согласно алгоритму LRU, если требуется замена, следует выбрать одну из этих двух страниц. Так вот вопрос, что мне выбрать? Теперь проблема в том, что мы не знаем, к какой из этих страниц обращались позже, начиная с такта 1 и заканчивая тактом 2. Поскольку за такт записывается только один бит, невозможно отличить, к какой странице обращались раньше, а к какой последней за такт. Итак, что мы можем сделать, это заменить页面3,Поскольку к странице 3 никогда не обращались в циклах 0–1, а к странице 5 обращались.

Второе различие между LRU и до устаревания заключается в том, что во время устаревания счетчик имеет ограниченное количество битов (8 в данном примере), что ограничивает историю записей доступа. Если счетчики обеих страниц равны 0, то мы можем выбрать любую для замены. На самом деле возможно, что к одной из страниц обращались 9 тактов назад, а к другой 1000 тактов назад, но мы этого не видим. На практике, если период синхронизации составляет 20 мс, обычно достаточно 8 бит. Поэтому мы часто берем 20 мс в качестве примера.

Алгоритм замены страницы рабочего набора

В простейшей системе подкачки, когда процесс только запускается, в памяти нет страниц. В этот момент, если ЦП пытается сопоставить первую инструкцию, он получает исключение ошибки страницы, в результате чего операционная система загружает страницу, содержащую первую инструкцию. другие ошибки, такие как全局变量и堆栈Возникающее в результате исключение ошибки страницы обычно следует немедленно. Через некоторое время большая часть страниц, необходимых процессу, находится в памяти, и в этот момент процесс начинает работать с меньшим количеством исключений ошибок страниц. Эта стратегия называется请求调页(demand paging), так как страницы загружаются по запросу, а не предварительно загружаются.

Чтение всех страниц в большом адресном пространстве приведет к множеству ошибок страниц и, следовательно, к нехватке памяти для размещения этих страниц. Однако, к счастью, большинство процессов работают иначе, все они начинаются с局部性方式(locality of reference)к доступу, что означает, что на любом этапе выполнения программа обращается только к небольшому их подмножеству.

Набор страниц, которые процесс использует в данный момент, называется его工作集(working set), если весь рабочий набор находится в памяти, то процесс не будет генерировать много ошибок страниц перед переходом к следующей фазе выполнения (например, к следующему проходу компилятора).Если памяти слишком мало для хранения всего рабочего набора, во время выполнения процесса будет генерироваться большое количество ошибок страниц, что приведет к снижению скорости выполнения.. Потому что выполнение инструкции обычно занимает всего несколько наносекунд, а чтение страницы с диска обычно занимает десять миллисекунд. Если бы программа могла выполнять только одну или две инструкции каждые 10 мс, ее выполнение заняло бы много времени. Если прерывание генерируется только при выполнении нескольких инструкций, то программа называется сгенерированной.颠簸(thrashing).

В многопрограммной системе принято перемещать процессы на диск (т. е. удалять все страницы из памяти), что дает другим процессам возможность занять центральный процессор. Один вопрос: что, если процесс захочет перезагрузить страницы, которые ранее были возвращены на диск, обратно в память? С технической точки зрения ничего делать не нужно, процесс будет генерировать ошибки страниц до тех пор, пока его工作集вспоминается в памяти. Затем 20, 100 или даже 1000 ошибок страницы каждый раз, когда загружается процесс, что, очевидно, слишком медленно, и значительное количество времени процессора тратится впустую, поскольку процессору требуется несколько миллисекунд для обработки ошибки страницы.

Поэтому многие системы подкачки пытаются отслеживать рабочий набор процесса и обеспечивать, чтобы эти рабочие наборы загружались в память во время выполнения процесса. Этот метод называется工作集模式(working set model). Он предназначен для уменьшения количества ошибок страниц. Процесс первой загрузки страниц рабочего набора перед запуском процесса называется预先调页(prepaging), рабочий набор меняется со временем.

Согласно исследованиям, большинство программ не имеют равномерный доступ к адресному пространству, а доступ часто сосредоточен на небольшом количестве страниц. Доступ к памяти может извлекать команду, извлекать данные или сохранять данные. В любой момент времени t существует множество, содержащее все страницы, к которым обращались при последних k обращениях к памяти. эта коллекцияw(k,t)является рабочим набором. Поскольку последнее k = 1 посещение обязательно посетит страницу, посещенную последним k > 1 посещением, поэтомуw(k,t)является монотонно убывающей функцией от k. По мере увеличения kw(k,t)Оно не будет бесконечно большим, потому что программа не может получить доступ к большему количеству страниц, чем максимальное количество страниц, которое может быть размещено.

На самом деле большинство приложений имеют произвольный доступ только к небольшому набору страниц, но этот набор медленно меняется со временем, так почему кривая сначала растет быстро и медленно, когда k велико. Для реализации модели рабочего множества операционная система должна отслеживатьКакие страницы входят в рабочий набор. Общее количество процессорного времени, которое процесс фактически использовал с момента начала выполнения, часто называют当前实际运行时间. Рабочий набор процесса можно назвать набором страниц, к которым он обращался за последние t секунд фактического выполнения.

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

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

Алгоритм работает следующим образом, предполагая, что оборудование хочет установить биты R и M. Аналогичным образом, во время каждого тактового цикла периодическое прерывание тактового генератора приводит к очистке программного обеспечения.Referenced(引用)немного. При каждом исключении ошибки страницы таблица страниц сканируется, чтобы найти подходящую страницу для замены.

По мере обработки каждой записи таблицы страниц необходимо проверять бит R. Если бит R равен 1, то текущее время записывается в запись таблицы страниц.上次使用时间Домен, что означает, что страница используется, когда возникает исключение ошибки страницы. Поскольку к странице обращались в текущем такте, она должна появиться в рабочем наборе, а не быть удаленной (при условии, что t охватывает несколько тактов).

Если бит R равен 0, то эта страница не была доступна в текущем тактовом цикле и должна быть объектом, подлежащим удалению. Чтобы узнать, следует ли его удалить, вычисляется его возраст (текущее виртуальное время — время последнего использования) и сравнивается с t. Если возраст больше t, страница больше не входит в рабочий набор, и для ее замены используется новая страница. Затем продолжите сканирование и обновите оставшиеся записи.

Однако если бит R равен 0, а возраст меньше или равен t, то страница должна быть в рабочем наборе. В это время страница будет временно сохранена, но запомнена生存时间最长（即上次使用时间的最小值）страница. Если просканирована вся таблица страниц и не найдено ни одной подходящей для замены страницы, значит все страницы находятся в рабочем наборе. В этом случае при обнаружении одной или нескольких страниц с R = 0 самая долгоживущая страница удаляется. В худшем случае за текущий такт были осуществлены обращения ко всем страницам (т. е. все имеют R = 1), поэтому случайным образом выбирается страница для исключения, а если она есть, то лучше выбрать ту, которой нет. доступ. , то есть чистая страница.

Алгоритм замены страницы часов рабочего набора

Когда происходит ошибка страницы, необходимо просмотреть всю таблицу страниц, чтобы определить страницы, которые необходимо удалить, поэтому базовый алгоритм рабочего набора требует много времени. Улучшение базового алгоритма рабочего набора основано на алгоритме часов, но с использованием информации о рабочем наборе такой алгоритм называетсяWSClock(工作集时钟). Благодаря простоте реализации и высокой производительности он широко используется на практике.

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

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

Как и в алгоритме часов, при каждом исключении сбоя страницы сначала проверяется страница, на которую указывает указатель. Если бит R установлен в 1, страница использовалась в текущем тактовом цикле, то страница не подлежит вытеснению. Затем установите позицию R страницы на 0, наведите указатель на следующую страницу и повторите алгоритм. См. рисунок b для сериализованного состояния этого события.

Теперь рассмотрим, что происходит, когда страница, на которую указывает указатель R = 0, см. рис. c, если возраст страницы больше t и к странице обращаются, то страница не находится в рабочем множестве, и будет копия страницы. Примените перезагрузку новой страницы и поместите в нее новую страницу, как показано на рисунке d. С другой стороны, если страница была изменена, ее нельзя перераспределить, поскольку на диске нет действительной копии страницы. Во избежание переключения процесса, вызванного планированием операции записи на диск, указатель продолжает двигаться вперед, а алгоритм продолжает работать на следующей странице. В конце концов, можно иметь старую немодифицированную страницу, которую можно использовать немедленно.

В принципе, все страницы могут быть磁盘I/OЗапланировано в течение определенного такта. Чтобы уменьшить блокировку диска, необходимо установить ограничение, т. е. разрешена обратная запись не более n страниц. После достижения этого предела новые операции записи не могут быть запланированы.

Тогда возникает проблема, указатель будет возвращаться в начало координат по кругу, если он вернется в начало координат, что будет с его начальной точкой? Здесь есть два случая:

  • Запланирована хотя бы одна операция записи
  • Операции записи не запланированы

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

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

Резюме алгоритма замены страницы

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

алгоритм Примечания
оптимальный алгоритм Недостижимо, но может быть использовано в качестве эталона
Алгоритм NRU (не недавно использовавшийся) Аналогично алгоритму LRU
Алгоритм FIFO (First In First Out) Можно отбросить важные страницы
алгоритм второго шанса Большое улучшение по сравнению с FIFO
тактовый алгоритм фактическое использование
Алгоритм LRU (наименее новый) Отлично, но труднодостижимо
Алгоритм NFU (наименее часто потребляемый) очень похоже на LRU
Алгоритм старения Эффективный алгоритм приближенного LRU
алгоритм рабочего набора Это дорого реализовать
Алгоритм рабочего набора часов более эффективный алгоритм

  • 最优算法Заменяет последнюю страницу, к которой нужно получить доступ, на текущей странице. К сожалению, невозможно определить, какая страница была посещена последней.因此实际上该算法不能使用. Однако его можно использовать в качестве эталона, по которому оцениваются другие алгоритмы.

  • NRUАлгоритм классифицирует атмосферу страницы по четырем категориям в соответствии с состоянием бита R и бита M. Страница выбирается случайным образом из категории с наименьшим номером. Алгоритм NRU прост в реализации, но его производительность не очень высока. Существуют лучшие алгоритмы.

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

  • 第二次机会Алгоритм представляет собой модификацию FIFO, которая проверяет, используется ли страница, прежде чем удалить ее. Если страница используется, она зарезервирована. Это улучшение значительно повышает производительность.

  • 时钟Алгоритмы — это еще одна форма реализации алгоритмов второго шанса.Алгоритм часов имеет производительность, аналогичную алгоритму второго шанса, но для его выполнения требуется меньше времени.

  • LRUАлгоритм очень хороший алгоритм, но не特殊的硬件(TLB)сложно осознать. Без аппаратного обеспечения алгоритм LRU не может быть использован.

  • NFUАлгоритм является приближением к LRU, и его производительность не очень высока.

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

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

Короче,Лучшими алгоритмами являются алгоритм старения и алгоритм WSClock.. Они основаны на алгоритмах LRU и рабочих наборов соответственно. Все они имеют хорошую производительность и могут быть эффективно реализованы. Существует несколько других хороших алгоритмов, но эти два, вероятно, наиболее важны на практике.

Алгоритмы в файловых системах

Файловая система будет использовать этот алгоритм в процессе резервного копирования.Резервное копирование файлов делится наЛогические и физические дампы

Физический дамп и логический дамп

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

逻辑转储(logical dump)Начиная с одного или нескольких указанных каталогов, рекурсивно создавать дамп файлов и каталогов, которые изменились с указанной даты. Таким образом, в логическом дампе есть ряд тщательно идентифицированных каталогов и файлов на диске дампа, что позволяет легко восстанавливать определенные файлы или каталоги по запросу.

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

Файловая система для дампа, где прямоугольники представляют目录, кружок представляет文件. Таблица элементов, выделенная желтым цветом, была изменена с момента последнего дампа. Каждый каталог и файл помечаются своим номером инода.

Этот алгоритм выводит все каталоги, расположенные на измененных путях к файлам или каталогам (включая неизмененные каталоги) по двум причинам. Во-первых, это возможность восстанавливать сброшенные файлы в разных файловых системах компьютера. Таким образом, созданную и восстановленную программу можно использовать между двумя компьютерами.传输整个文件系统. Вторая причина заключается в том, чтобы иметь возможность делать один файл增量恢复.

Алгоритм логического дампа должен поддерживать проиндексированный индексный дескриптор.位图(bitmap), каждый индекс содержит несколько битов. Эти биты в растровом изображении устанавливаются или очищаются по мере выполнения алгоритма. Выполнение алгоритма разбито на четыре этапа. Первый этап из起始目录（本例为根目录）Начните проверять все записи каталога в нем. Для каждого измененного файла алгоритм отметит его индекс в растровом изображении. Алгоритм также помечает и рекурсивно проверяет каждый каталог (независимо от того, был ли он изменен).

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

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

Обратите внимание, что каталоги с номерами инодов 10, 11, 14, 27, 29 и 30 не отмечены из-за того, что они содержат.没有修改. Они тоже не сваливают. И наоборот, сами каталоги с номерами инодов 5 и 6 выгружаются, даже если они не были изменены, потому что эта информация нужна для восстановления изменений дня на новой машине. Для повышения эффективности алгоритма двухэтапный обход дерева каталогов может быть объединен в один.

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

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

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

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

Несмотря на простоту логического хранения, есть некоторые каверзные вопросы. Во-первых, поскольку список свободных блоков не является файлом, его необходимо воссоздать с нуля после восстановления всех файлов из дампа.

Другой вопрос касается链接. Если файл связывает два или более каталогов и файл можно восстановить только один раз, то все каталоги, которые указывают на файл, должны быть восстановлены.

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

Наконец, независимо от того, к какому каталогу он принадлежит,специальные файлы, именованные каналы и подобные файлыНи то, ни другое не должно быть сброшено.

Алгоритмы ввода/вывода

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

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

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

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

Если драйвер диска получает по одному запросу за раз и выполняет запросы в том порядке, в котором они были получены, этот метод обработки先来先服务(First-Come, First-served, FCFS), таким образом сложно оптимизировать время поиска. Поскольку каждый раз будет обрабатываться по порядку, независимо от порядка, возможно, что после этого чтения вам нужно будет подождать, пока диск повернется в течение недели, прежде чем продолжить чтение, в то время как другие цилиндры могут быть прочитаны немедленно. в этом случае каждый запрос также будет поставлен в очередь.

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

Улучшение алгоритма «первым пришел – первым обслужено» заключается в использовании最短路径优先(SSF)алгоритм, который описан ниже.

Если мы обращаемся к дорожке № 6, запросы на 11, 2, 4, 14, 8, 15, 3 происходят одновременно, если мы принимаем принцип «первым пришел — первым обслужен», как показано на следующем рисунке.

Мы можем рассчитать количество дисков, охватываемых плечом диска, как 5 + 9 + 2 + 10 + 6 + 7 + 12 = 51, что эквивалентно охвату дисков 51. Если мы сначала используем кратчайший путь, давайте вычислим составные диски.

Количество объединенных дисков равно 4 + 1 + 1 + 4 + 3 + 3 + 1 = 17, что экономит вдвое больше времени по сравнению с 51.

Однако алгоритм поиска кратчайшего пути не идеален, и с этим алгоритмом все еще есть проблемы, т.е.优先级проблема,

Вот прототип для справки, которым является лифт в нашей повседневной жизни.电梯算法(elevator algorithm)планирование для достижения противоречивых целей координации эффективности и справедливости. Лифт, как правило, продолжает двигаться в одном направлении до тех пор, пока в этом направлении не будет запроса, а затем меняет направление.

Алгоритм лифта должен поддерживать二进制位, который является текущим битом направления:UP(向上)илиDOWN(向下). Когда запрос обрабатывается, драйвер диска или лифта проверяет этот бит, и, если бит находится в состоянии UP, рычаг диска или модуль лифта переходит к следующему более высокому или незавершенному запросу. Если в старших битах нет невыполненных запросов, выбирается противоположное направление. Когда бит направленияDOWN, также есть запрос младшего разряда, и рычаг диска поворачивается в эту точку. Если его нет, то он просто останавливается и ждет.

Давайте возьмем пример для описания алгоритма лифта, Например, порядок, в котором обслуживается каждый цилиндр, 4, 7, 10, 14, 9, 6, 3, 1, тогда его блок-схема выглядит следующим образом.

Таким образом, количество досок, которые должен пересечь алгоритм лифта, равно 3 + 3 + 4 + 5 + 3 + 3 + 1 = 22.

Алгоритм лифта обычно уступает алгоритму SSF.

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

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

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

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

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

Алгоритмы в тупике

В стратегии обработки взаимоблокировок одним из пунктов является игнорирование влияния взаимоблокировки (stunned), возникла проблема, называемая鸵鸟算法из

Самое простое решение — использовать鸵鸟算法(ostrich algorithm), пряча голову в песок и делая вид, что проблемы вообще не было. Реакция на этот вопрос у всех разная. Математики считают тупиковые ситуации неприемлемыми, и их необходимо предотвращать с помощью эффективных стратегий. Инженеры хотят знать, как часто возникают проблемы, сколько раз происходит сбой системы по другим причинам и каковы серьезные последствия взаимоблокировок. Большинство инженеров не будут исправлять тупиковые ситуации, если они случаются нечасто и часто из-за аппаратных сбоев, ошибок компилятора и других проблем ОС, вызывающих сбой системы.

Появились некоторые алгоритмы обнаружения взаимоблокировок

Метод обнаружения взаимоблокировок для нескольких ресурсов каждого типа

Если существует несколько идентичных ресурсов, для обнаружения взаимоблокировок требуется другой метод. Взаимоблокировки в n процессах из P1 -> Pn можно обнаружить, построив матрицу.

Теперь мы предлагаем матричный алгоритм для обнаружения взаимоблокировок в n процессах от P1 до Pn. Предполагая, что тип ресурса равен m, E1 представляет ресурс типа 1, E2 представляет ресурс типа 2, а Ei представляет ресурс типа i (1 现有资源向量(existing resource vector), представляющее общее количество существующих ресурсов каждого типа.

Теперь нам нужно построить два массива: C означает当前分配矩阵(current allocation matrix), R означает, что请求矩阵(request matrix). Ci представляет количество ресурсов каждого типа, принадлежащих Pi. Таким образом, Cij представляет количество ресурсов j, которыми владеет Pi. Rij представляет количество ресурса j, которое Pi необходимо получить.

В общем случае количество выделенных ресурсов j складывается вместе с количеством всех доступных ресурсов = общему количеству ресурсов этого типа.

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

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

  • Проверка всякий раз, когда есть запрос на ресурс, потребляет дорогое процессорное время.
  • Проверять каждые k минут или когда загрузка ЦП падает ниже определенного порога. Из соображений эффективности ЦП, если заблокированный процесс достигает определенного числа, не многие процессы могут работать, поэтому ЦП будет часто простаивать.

Существуют также алгоритмы предотвращения взаимоблокировок.

Алгоритм банкира

Алгоритм Бэнкера — это алгоритм планирования, предложенный Дейкстрой в 1965 году, который сам по себе является алгоритмом планирования взаимоблокировок. Его модель основана на банкире в городе, который обещает определенное количество кредитных линий клиентам в городе. Все, что нужно сделать алгоритму, — это определить, перейдет ли запрос в небезопасное состояние. Если это так, отклоните запрос и примите запрос, если система после запроса находится в безопасности.

Например, в приведенном ниже примере банкир предоставляет в общей сложности 15 единиц кредитных линий для всех городских жителей, и одна единица представляет собой 1 тысячу долларов США, как показано ниже.

Городские жители любят заниматься бизнесом, поэтому будут привлекать кредиты.Максимальная сумма кредита, которую может занять каждый человек, разная.В определенный момент сумма кредита A/B/C/D выглядит следующим образом

Сумма общей суммы кредита каждого вышеперечисленного человека составляет 13, и она сразу же будет близка к 15. Банкир может ссудить только A и C и может перетащить B и D. Следовательно, A и C могут быть завершены первыми, и сумма кредита может быть выпущена.Познакомьтесь с кредитами других жителей. Это安全статус.

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

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

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

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

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

Категории