Как найти среднее время поиска в алгоритмах планирования диска?Я ищу формулу среднего времени поиска, используемую в алгоритмах планирования диска.
Первый шаг - определить географию самого устройства.Это сложно.Современные жесткие диски не могут быть определены старым триплетом «цилиндры, головки, секторы», количество секторов на дорожке различно для разных дорожек (больше секторов на внешних дорожках, где длина окружности больше, меньше секторов на внутренних дорожках, где длина окружности равнаменьше), и вся информация, которую вы можете получить о накопителе (от самого устройства, или от любой прошивки или API ОС), является ложью, чтобы осчастливить устаревшее программное обеспечение.
Чтобы обойти это, вам нужноприбегнуть к «тактике бенчмаркинга».В частности, считайте из сектора 0 LBA, затем из сектора 1 LBA и измерьте время, которое потребовалось (чтобы установить предположение «время, необходимое для обоих секторов на одной дорожке»), затем прочитайте из сектора 0 LBA, затем сектор N LBA в цикле (с N, начинающимся с 2 и увеличивающимся), измеряя время, которое требуется, и сравнивая его с предыдущим значением и ища большее увеличение времени, которое указывает, что вы нашли границу между «дорожкой 0» и «дорожкой 1».Затем повторите это (начиная с первого сектора в «дорожке 1»), чтобы найти границу между «дорожкой 1» и «дорожкой 2»;и продолжайте повторять это, чтобы построить массив «сколько секторов на каждой дорожке».Обратите внимание, что это не так просто - есть различные подводные камни (например, большие физические сектора, чем логические сектора, секторы, чередующиеся на дорожке, неправильная замена блоков, внутренние кэши, встроенные в дисковод и т. Д.), Которые необходимо учитывать.Конечно, это займет слишком много времени (например, вы не хотите делать это для каждого диска каждый раз при загрузке ОС), поэтому вам нужно получить идентификацию жесткого диска (производителя и номер модели) и сохранить автоматическигде-то обнаружил геометрию, так что вы можете пропустить автоопределение, если геометрия для этой модели диска была ранее сохранена.
Следующим шагом будет использование информации о реальной геометрии (а не фиктивной геометрии)в сочетании с более «тактикой бенчмаркинга» для определения характеристик производительности.В идеале вы должны пытаться найти константы для формулы типа expected_time = sector_read_time + rotational_latency + distance_between_tracks * head_travel_time + head_settle_time, что можно сделать следующим образом:
- измерить время для чтения из первого сектора в первой дорожке, а затем из сектора N в первой дорожке;для каждого значения N (для каждого сектора в первой дорожке) и найдите минимальное время, которое оно может занять, разделите его на 2 и назовите его
sector_read_time. - измерьте время для чтения из первого сектора в первой дорожкезатем сектор N в первой дорожке;для каждого значения N (для каждого сектора в первой дорожке) и найдите максимальное время, которое оно может занять, разделите его на число секторов в первой дорожке и назовите его
rotational_latency. - измерение временичитать с первого сектора на дорожке N, затем с первого сектора на дорожке N + 1, где N находится в диапазоне от 0 до «max_track - 1», и определить среднее значение, назвать его
time0 - измерить время для чтенияот первого сектора на дорожке N, затем на первый сектор на дорожке N + 2, где N находится в диапазоне от 0 до «max_track - 1», и определите среднее значение и назовите его
time1 - , предположим
head_travel_time = time1 - time0 - предположим,
head_settle_time = time0 - head_travel_time - sector_read_time
Обратите внимание, что с этим тоже есть различные подводные камни (как и раньше), и (если вы обходите их) лучшее, на что вы можете надеяться, это общая оценка(и не является точным предиктором).
Конечно, это также будет чрезмерно занимать много времени, и если вы сохраняете где-то автоматически обнаруженную геометрию, было бы неплохо также сохранить автоматически обнаруженноеэксплуатационные характеристики в гоэто же место;так что вы можете пропустить все автоопределение, если вся информация для этой модели диска была ранее сохранена.
Обратите внимание, что все вышеперечисленное предполагает «автономный вращающийся жесткий диск без кэширования и без гибридного / флэш-слоя» и будет совершенно бесполезным во многих случаях.В некоторых других случаях (SSD, CD / DVD) вам понадобятся разные методы для автоматического определения их геометрии и / или характеристик.Кроме того, существуют такие вещи, как RAID и виртуализация, которые еще более усложняют ситуацию.
В основном; слишком много хлопот на практике .
Вместо этого;просто предположите, что cost = abs(previous_LBA_sector_number - next_LBA_sector_number) и / или позвольте жесткому диску самому отсортировать оптимальный порядок (например, используя Native Command Queuing - см. https://en.wikipedia.org/wiki/Native_Command_Queuing).