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

Обновлено: 06.07.2024

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

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

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

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

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

Строение жесткого диска и параметры планирования

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

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

Рис. 13.2.Схема жесткого диска

При планировании использования жесткого диска естественным параметром планирования является время, которое потребуется для выполнения очередного запроса. Время, необходимое для чтения или записи определенного сектора на определенной дорожке определенного цилиндра, можно разделить на две составляющие: время обмена информацией между магнитной головкой и компьютером, которое обычно не зависит от положения данных и определяется скоростью их передачи (transfer speed), и время, необходимое для позиционирования головки над заданным сектором, – время позиционирования (positioning time). Время позиционирования, в свою очередь, состоит из времени, необходимого для перемещения головок на нужный цилиндр, – времени поиска (seek time) и времени, которое требуется для того, чтобы нужный сектор довернулся под головку, – задержки на вращение (rotational latency). Времена поиска пропорциональны разнице между номерами цилиндров предыдущего и планируемого запросов, и их легко сравнивать. Задержка на вращение определяется довольно сложными соотношениями между номерами цилиндров и секторов предыдущего и планируемого запросов и скоростями вращения диска и перемещения головок. Без знания соотношения этих скоростей сравнение становится невозможным. Поэтому естественно, что набор параметров планирования сокращается до времени поиска различных запросов, определяемого текущим положением головки и номерами требуемых цилиндров, а разницей в задержках на вращение пренебрегают.

Строение жесткого диска и параметры планирования

Алгоритм First Come First Served (FCFS)

Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно длительному общему времени обслуживания запросов. Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63-м цилиндре. Тогда положение головок будет меняться следующим образом:

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

Алгоритм Short Seek Time First (SSTF)

Как мы убедились, достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко отстоящих. Алгоритм Short Seek Time First (SSTF) – короткое время поиска первым – как раз и исходит из этой позиции. Для очередного обслуживания будем выбирать запрос, данные для которого лежат наиболее близко к текущему положению магнитных головок. Естественно, что при наличии равноудаленных запросов решение о выборе между ними может приниматься исходя из различных соображений, например по алгоритму FCFS . Для предыдущего примера алгоритм даст такую последовательность положений головок:

и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож на алгоритм SJF планирования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянно группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.

Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Очевидно, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67-го цилиндра в промежуток между запросами 7-го и 84-го цилиндров, мы уменьшим общее время обслуживания. Это наблюдение приводит нас к идее целого семейства других алгоритмов – алгоритмов сканирования.

Алгоритмы сканирования (SCAN, C-SCAN, LOOK, C-LOOK)

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

и всего головки переместятся на 147 цилиндров.

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

и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила название LOOK .

Допустим, что к моменту изменения направления движения головки в алгоритме SCAN , т. е. когда головка достигла одного из краев диска, у этого края накопилось большое количество новых запросов, на обслуживание которых будет потрачено достаточно много времени (не забываем, что надо не только перемещать головку, но еще и передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будут ждать обслуживания несправедливо долго. Для сокращения времени ожидания запросов применяется другая модификация алгоритма SCAN – циклическое сканирование. Когда головка достигает одного из краев диска, она без чтения попутных запросов (иногда существенно быстрее, чем при выполнении обычного поиска цилиндра) перемещается на другой край, откуда вновь начинает движение в прежнем направлении. Для этого алгоритма, получившего название C-SCAN , последовательность перемещений будет выглядеть так:

По аналогии с алгоритмом LOOK для алгоритма SCAN можно предложить и алгоритм C-LOOK для алгоритма C-SCAN :

Существуют и другие разновидности алгоритмов сканирования, и совсем другие алгоритмы, но мы на этом закончим, ибо было сказано: "И еще раз говорю: никто не обнимет необъятного".

Заключение

Функционирование любой вычислительной системы обычно сводится к выполнению двух видов работы: обработка информации и операции по осуществлению ее ввода-вывода. С точки зрения операционной системы "обработкой информации" являются только операции , совершаемые процессором над данными, находящимися в памяти на уровне иерархии не ниже чем оперативная память . Все остальное относится к "операциям ввода-вывода", т. е. к обмену информацией с внешними устройствами.

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

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

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

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

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

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

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

Современный жесткий магнитный диск представляет собой набор круглых пластин, находящихся на одной оси, и покрытых с одной или двух сторон специальным магнитным слоем (рис.13.2). Около каждой рабочей поверхности каждой пластины расположены магнитные головки для чтения и записи информации. Эти головки присоединены к специальному рычагу, который может перемещать весь блок головок над поверхностями пластин как единое целое. Поверхности пластин разделены на концентрические кольца, внутри которых собственно и может храниться информация. Набор концентрических колец на всех пластинах для одного положения головок (т.е. все кольца равноудаленные от оси) образует цилиндр. Каждое кольцо внутри цилиндра получило название дорожки (по 1-й или 2-е дорожки на каждую пластину). Все дорожки делятся на равное число секторов. Количество дорожек, цилиндров и секторов может варьироваться от одного жесткого диска к другому в достаточно широких пределах. Как правило, сектор является минимальным объемом информации, которое может быть прочитано с диска за один раз.

Управление хранилищем ОС --- Алгоритм планирования работы дисков

введение:В многопрограммной компьютерной системе каждый процесс может постоянно делать запросы чтения / записи на диск. Иногда процесс отправляет запросы быстрее, чем ответ диска, поэтому нам нужно установить очередь ожидания для каждого дискового устройства и действовать разумно.Планирование диска. В этой статье будут рассмотрены три фактора, влияющих на время чтения и записи на диск, и представлены несколько общих алгоритмов планирования (FCFS, STF, SSF, ES, ESLA, OWES).

1. Основные факторы, влияющие на время чтения и записи диска

Основными факторами, влияющими на время чтения и записи диска, являются время поиска, задержка вращения и время передачи. Общее среднее время доступа Ta можно выразить как: Ta = Ts + Tr + Tt.

1), время поиска Ts : Относится кВремя, необходимое для перемещения головки чтения / записи в требуемое положение дорожки.. Фактическое время поиска зависит от положения головки чтения / записи и расстояния, на которое головка должна переместиться при получении запроса на чтение / запись. Помимо времени, охватывающего n треков, это время также включает время s для активации магнитного плеча, а именно: Ts = m * n + s. В формуле m - постоянная, связанная со скоростью дисковода, около 0,2 мс, а время запуска магнитного рычага составляет около 2 мс.

Среднее время поиска : Поскольку нет способа узнать положение головки чтения / записи и расстояние, на которое головка должна переместиться до получения запроса доступа, мы часто используем концепцию среднего времени поиска. Среднее значение времени поиска зависит от физического размера компонентов дисковода и скорости, с которой головка ускоряется и замедляется. Обычно от 8 мс до 20 мс, и за последние годы не сильно изменился.

2), задержка вращения Tr : Относится кПосле того, как магнитная головка достигнет необходимого положения дорожки, среднее время ожидания поворота требуемого сектора под магнитной головкой. Если в среднем требуемый сектор находится на расстоянии пол-оборота от головы, задержка вращения обычно составляет половину времени вращения. Текущая скорость вращения диска находится в диапазоне от 3500 до 10 000 оборотов в минуту, поэтому диапазон задержки вращения находится в пределах от 3 мс до 8,7 мс. (Возьмем, к примеру, оборот 1 Вт, оборот 1 Вт занимает 6 мс, 1 оборот занимает 3 мс, а его задержка вращения составляет 3 мс)

3) Время передачи Tt : Время, необходимое для чтения или записи данных с диска. Это время зависит от количества байтов, считываемых / записываемых каждый раз b, и скорости вращения диска: Tt = b / (r * N). В формуле r - количество оборотов диска в секунду; N - количество байтов на дорожке.

Хотя здесь приводится формула для среднего времени доступа, среднее значение не имеет большого практического значения. Из-за вышеперечисленных трех факторов время поиска является доминирующим и контролируемым фактором для разработчиков программного обеспечения. Чтобы повысить эффективность чтения и записи диска, необходимо уменьшить время поиска диска, что достигается за счет планирования диска. Алгоритмы планирования работы дисков в основном включают следующие: FCFS, STF, SSF, ES, ESLA, OWES.

В книге «Философские принципы операционных систем» среди трех факторов, влияющих на операции дискового ввода-вывода, время поиска, задержку вращения и передачу данных, преобладает трудоемкий поиск, поэтому улучшите чтение и запись на диск. Эффективность требует сокращения времени поиска, и соответствующие алгоритмы планирования диска также разработаны для сокращения времени поиска.
Исходный текст выглядит следующим образом. На время чтения и записи на диск влияют три фактора: время поиска, задержка вращения и время передачи данных. Среди этих трех первые два - это механическое движение, а передача данных - в основном электронное движение. Очевидно, что скорость механического движения намного ниже скорости электронного. Для первых двух частей с механическим движением время поиска больше. Следовательно, среди трех вышеперечисленных факторов время поиска преобладает. Чтобы повысить эффективность чтения и записи диска, необходимо уменьшить время поиска диска, что достигается за счет планирования диска.
Но я лично считаю, что три важных момента - это только один аспект. Основная причина заключается в том, что среди этих трех факторов мы, разработчики программного обеспечения, можем контролировать только время поиска. . Поскольку задержка вращения зависит от скорости вращения дисковода, она достигла своего верхнего предела при условии обеспечения точности позиционирования.Это может быть оптимизировано только производителем оборудования. Точно так же время передачи зависит от скорости вращения и пропускной способности пути. Следовательно, часть, которую разработчики программного обеспечения могут оптимизировать, - это общее время поиска.

Во-вторых, алгоритм планирования диска

2.1. В порядке очереди FCFS

FCFS (первый пришел, первый обслужил):ЭтоЕстественно честная стратегия планирования. Первым пришел - первым пришел, непривилегированный пользователь. Алгоритм FCFS выполняет планирование в соответствии с порядком, в котором процесс запрашивает доступ к диску. Это самый простой алгоритм планирования, как показано на рисунке 1.

Рис. 1. Принципиальная схема алгоритма «первым пришел - первым обслужен»

Например:, Последовательность запросов в очереди запросов на диск - 55, 58, 39, 18, 90, 160, 150, 38, 184, а начальное положение магнитной головки - 100 дорожек. Процесс перемещения магнитной головки с использованием алгоритма FCFS показан на рисунке 1. Голова переместилась (45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146) = 498 треков, а средняя длина поиска = 498/9 = 55,3.

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

2.2. Краткие задачи отдают приоритет STF

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

2.3, приоритет короткого поиска SSF

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

Также, используя пример на рисунке 1, последовательность запросов в очереди запросов к диску составляет 55, 58, 39, 18, 90, 160, 150, 38, 184, начальное положение магнитной головки - 100 дорожек, а последовательность доступа магнитной головки с использованием алгоритма SSTF: 90, 58, 55, 39, 38, 18, 150, 160, 184. Процесс перемещения показан на рисунке 2. Голова переместилась (10 + 32 + 3 + 16 + 1 + 20 + 132 + 10 + 24) = всего 248 треков, а средняя длина поиска = 248/9 = 27,5.

Рисунок 2. Принципиальная схема алгоритма планирования SSF.

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

Рис. 3. Схематическая диаграмма алгоритма планирования SSF с качанием влево и вправо.

2.4, планирование лифта ES

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

Рисунок 4. Принципиальная схема алгоритма планирования ES.

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

2.5, заранее проверьте расписание лифта ESLA

Заранее проверьте расписание лифта ESLA (планирование лифта с опережением) .Если все запросы в одном направлении удовлетворяются, немедленно будет выполнено обратное без сканирования до конца. Этот алгоритм заключается в том, что каждый раз, когда вы двигаетесь в определенном направлении, вы должны убедиться, что в этом направлении все еще есть неудовлетворенные запросы. В противном случае немедленно измените направление на противоположное, чтобы повысить эффективность. Как показано на рисунке 5:

Рисунок 5. Принципиальная схема алгоритма планирования ESLA.

2.6 Односторонняя отправка лифта OWES

Планирование одностороннего лифта (OWES). Предварительное усовершенствование метода лифта - это планирование лифта в одном направлении, то есть сканирование только в одном направлении. Когда в этом направлении не осталось запросов, вернитесь к дорожке 0 и снова выполните то же сканирование. Если дисковый запрос такой же, как на рисунке 5, общее количество поисков с использованием одностороннего планирования лифта составляет: 1 + 4 + 16 + 8 = 29, что экономит 23 дорожки времени поиска по сравнению с методом лифта заранее.

Рисунок 6. Принципиальная схема алгоритма планирования OWES.

2.7, альтернативная нумерация дисков-уменьшить задержку вращения

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

Рисунок 7. Принципиальная схема альтернативной нумерации дисков.

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

Читайте также: