Pull to refresh

Алгоритм упорядочения логических томов в среде ОС Windows

Reading time 9 min
Views 7.3K
Код-прототип на JavaScript уверенно обгоняет по скорости базовую системную утилиту DISKPART.EXE при решении задачи упорядочения логических томов.

Описан алгоритм, реализация которого в прототип-коде на JavaScript уверенно опережает по времени решения задачи опорную системную утилиту DISKPART.EXE. Описаны принципы на которых базируется алгоритм. Дано возможное объяснение, но не доказательство, тому, почему DISKPART.EXE решает задачу медленней, чем JavaScript код. Приводятся состязательные результаты в среде Windows различных изданий, включая Windows 10 RTM TH1. Описывается как изменения, вносимые в различных изданиях Windows 10 вынуждали несколько раз переделывать алгоритм с целью повышения его надежности, хотя и ценой некоторой потери скорости.

Вступление


Логические тома лежат в основе любой ОС. До тех пор, пока нет логических томов, систему просто негде размещать. Подготовка логического тома включает выделение пространства на физическом устройстве хранения данных (то есть создание тома данных, Storage#Volume, зачастую не совсем правильно именуемого Разделом, Partition), а затем создание файловой системы, внутри которой и размещаются компоненты любой ОС. Ниже излагается алгоритм решения задачи упорядочения логических том применительно к ОС Windows, но в полном описании алгоритма, размещенном на GitHub, производится сравнение с другими ОС.

Принципы, на которых базируется описываемый алгоритм


В основу описываемого алгоритма в качестве основных, заложены два принципа:

1. Использование «естественной сортировки» по уникальному, «генетическому» свойству, приобретаемому объектами-детьми от объектов-родителей.

2. Вычисление «адреса» объекта, носителя детальной информации об объекте, отстоящем от родителя на один уровень, на основе «генетического кода» родительского объекта.

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

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

Идентификация устройств хранения данных производителями оборудования и операционными системами


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

Производители оборудования (Manufactures), наделяют свои изделия уникальным, не уничтожимым и существующим с момента выпуска на все время жизни, идентификатором. Идентификатор, называемый в системе «PnPDeviceID», представляется достаточно длинной текстовой строкой, разбитой на подгруппы символом "&". Подгруппы содержат имя производителя, наименование конкретного изделия, номер версии, класс изделия и другое.

Как только любое из устройств хранения данных впервые было опознано конкретной операционной системой, соответствующее устройство (за одним исключением), приобретает еще один уникальный, существенно более короткий и строго формализованный идентификатор, называемый GUID. Длина GUID составляет 42 ASCII-символа из которых 6 символов являются служебными. В связи с этим значимыми являются лишь 32 16-ричных символа, немедленно превращаемых системой в 8-ми байтное число, QWORD, по определенному алгоритму. Эти восьми-байтные числа с использованием системного алгоритма хеширования используются далее для «прямого доступа» к соответствующим объектам и для упорядочения объектов, путем создания перечислений.

Исключение. Как минимум одним из устройств хранения данных, которому не присваивается GUID, является класс устройств с обобщенным именем «DVD-ROM», обслуживаемый в среде ОС Windows любых изданий и редакций драйвером «cdrom», HKLM\SYSTEM\CurrentControlClass\Services\cdrom\Enum.

Для таких устройств присвоенный ОС идентификатор PnPDeviceID является единственным идентификатором устройства в системе.

Разрешение коллизий в среде ОС Windows


ОС Windows поступает точно так же, нянечки в родильных домах, привязывая некую бирку к руке новорожденного: ОС приписывает к идентификатору от производителя еще и «бирку с номером» на тот случай, если ОС придется опознавать и присваивать PnPDeviceID еще одному аналогичному устройству от того же производителя. Эта «бирка с номером" приписывается через стандартный разделитель "&" последней. Тем самым гарантируется, что в системе никогда не возникнет двух устройств с абсолютно одинаковыми PnPDeviceID.

PnPDeviceID создается абсолютно для всех устройств хранения данных, впервые опознанных системой. Но для всех устройств, отличных от «DVD-ROM», как уже было сказано выше, система создает еще и GUID. Как же в этом случае различаются GUID для двух устройств с абсолютно одинаковыми идентификаторами от производителя, куда вешается «бирка с номером» в GUID? «бирка с номером» это последние два 16-ричных символа первого поля GUID. Более детальное пояснение будет дано ниже при сравнении отчетов программы в среде 8.1 и Windows 10 RTM TH1.

Дополнительные уникальные свойства устройств хранения данных


Применительно к логическим томам:

Серийный номер тома, SerialNumber. Присваивается ОС абсолютно всем устройствам логическим томам, включая даже виртуальные «DVD-ROM». Серийный номер представляется 8 16-тиричными символами. В этом поле возможны коллизии, от которых невозможно избавиться, и система не пытается это сделать, поскольку нет в том необходимости. Серийный номер «00000000» приобретают все логические тома, которые были полностью зашифрованы (Encrypted) тем или иным способом, и система не может прочитать серийный номер тома до тех пор, пока том не будет смонтирован с указанием кода декодирования. Таким образом 8 нулей в поле SerialNumber логического тома уверенно свидетельствуют о том, что этот том зашифрован.

Применительно к устройствам хранения данных:

Серийный номер устройства, SerialNumber. Присваивается производителем устройства. 8 16-ричных символов. Хранится в системе даже для устройств, единственный логический том на которых был тем или иным способом зашифрован.

Подпись диска, Signature. Присваивается производителем устройства. 8 16-ричных символов.
Все ОС блокируют отображение в системе подписи диска в том случае, если на диске размещены Gpt-форматированные разделы. Это несомненно системный трюк, позволяющий без использования низкоуровневых операций ввода-вывода для диска, по наличию или отсутствию подписи диска определить Стиль (Style) форматирования разделов на диске: Mbr/Gpt. Очень изящно это демонстрируется в свойствах диска, хранимых в HKLM\HARDWARE\DESCRIPTION\System\MultifunctionAdapter\0\DiskController\0\DiskPeripheral, где хранится свойство «Identifier»=«9cb5ff90-00000000-A». 8 нулей, несомненно специально записанных ОС на место реальной подписи диска, свидетельствуют о том, что разделы на диске имеют стиль форматирования Gpt.

Результаты выполнения под управлением разных версий Windows


Windows 10 RTM TH1 Build 10240
N
EnumDevicesAndVolumes.wsf
DISKPART.EXE
1
2.140
6.235
2
1.452
2.936
3
2.530
2.953
4
2.541
2.867
5
1.448
2.905


Windows 8.1 Build 9600
N
EnumDevicesAndVolumes.wsf
DISKPART.EXE
1
1.243
5.274
2
1.222
2.558
3
1.218
1.289
4
1.200
1.379
5
1.379
1.425


Windows 7 SP1 Build 7601
N
EnumDevicesAndVolumes.wsf
DISKPART.EXE
1
1.406
11.913
2
1.319
2.130
3
1.338
2.662
4
1.310
2.788
5
1.287
2.698


Небольшой по размеру JavaScript код, WhoIsFaster.js, последовательно запускал на выполнение (WShell.Exec) командные строки, соответствующие исполнению EnumDevicesAndVolumes.wsf и DISKPART.EXE. В ходе исполнение той и другой программы считывались строки, выводимые программами на StdOut и считанные строки, буферизовались с целью предельно точно измерить процессорное время исполнения кода. Замеры производились с точностью до миллисекунды и в таблицах всюду фигурируют секунды и миллисекунды.

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

Аппаратная платформа


Thinkpad R500, 2.4Gz, 8 Gb RAM, ATI Mobility Radeon HD 3400, 1650x1080, два внутренних диска. Первый, основной, четыре раздела. Второй, два раздела.

Прикладные программы, установленные в различных версиях Windows



Windows 7 Enterprise Evaluation. Установлены лишь Total Commander и Free Javascript Editor. Эти же программы установлены и в других системах.

Windows 8.1: MS Office 2013, Acronis True Image 2015, Acronis Disk Director 12, пара программ от AOMEI для создания бэкапов и для обслуживания разделов. Перечислены лишь те из прикладных программ, которые запускают собственные драйвер-фильтры, создающие перечисления в HKLM\SYSTEM\CurrentControlSet\Services.

Windows 10: начиная с Technical Preview Build 10049, когда стало возможным обновление Windows 8.1 без потери установленных прикладных программ и их настроек, актуальная на тот момент версия 8.1 была обновлена. В дальнейшем Windows 10 претерпевала обновления всеми официально выпускаемыми сборками и поэтому состав прикладного софта в средах 9600 и 10240, полностью совпадает.

Интерпретация результатов


Соревновательные результаты в средах всех трех изданий Windows достаточно близки. Можно лишь отметить, что в среде Windows 10 на скорость работы кода-прототипа в большей степени влияют параллельно запущенные браузеры с большим числом открытых страниц, MS Office 2013 Word, автоматически запускающий сервис синхронизации с OneDrive, чем в предыдущих изданиях. Поэтому «соревнования» всегда проводились в равных условиях, сразу после запуска Windows.

Чем можно объяснить ощутимо меньшую скорость работы DISKPART.EXE в сравнении с интерпретируемым кодом EnumDevicesAndVolumes.wsf в среде Windows 8.1? Есть лишь одно, бездоказательное объяснение. Как уже было упомянуто, для всех устройств хранения данных и созданных на них томах данных и логических томах, система использует QWORD-ключи (8 байт) для работы с хеш-таблицами.

Описываемый алгоритм использует для тех же целей лишь поле Field 1 GUID, превращаемого системой в QWORD. Не хватает знаний и данных для оценки зависимости скорости доступа к системной хеш-таблице, но представляется, что эта зависимость нелинейная и в лучшем случае обратно пропорциональна N*log(N), где N – длина ключа в битах или байтах. Таким образом именно короткие ключи, используемые описываемым алгоритмом, могут объяснить отставание DISKPART.EXE.

До появления Windows 10 RTM TH1 Build 10240, соревновательные результаты в среде различных сборок лишь незначительно отличались от аналогичных в среде 8.1. Однако в среде сборки 10240 был принципиально изменен алгоритм перечисления ключей
HKU\SID\Software\Microsoft\Windows\CurrentVersion\Explorer\MountPoints2\CPC\Volume: если начиная с 7601 и заканчивая 10166 «дети ходили семьями», то есть все логические тома, созданные на одном и том же физическом диске, строго следовали один за другим в порядке возрастания смещения от начала диска, то в среде 10240 было впервые внедрено «естественное» упорядочение логических томов в котором тома перечисляются строго в порядке их монтирования в системе. Это изменение должно было ускорить работу системы с логическими томами. DISKPART.EXE, как представляется, еще не пользуется этим перечислением и все также выталкивает в первые ряды устройства, обслуживаемые драйвером cdrom.

Визуальное представление результатов решения задачи



Рисунок 1

Именно этот вывод информации о логических томах программой DISKPART.EXE и явился «задачей для подражания» и создания быстрого алгоритма решения. Размещенные ниже рисуноки 2 и 3 представляют один из многих отчетов, создаваемых EnumDevicesAndVolumes.wsf. Это самые короткие из всех отчетов, создаваемых EnumDevicesAndVolumes.wsf. Тем не менее даже этот отчет содержит больше информации, чем приведенный выше отчет DISKPART и не содержит бессмысленной информации, как в столбце Status: естественно, что все тома здоровы, а иначе бы пришлось заниматься их лечением, а не соревнованиями в скорости решения задачи.


Рисунок 2


Рисунок 3

Рисунок 2 представляет краткий отчет EnumDevicesAndVolumes.wsf в среде Windows 8.1, а очень похожий рисунок 3 представляет аналогичный отчет в среде Windows 10 RTM TH1. Разница обнаруживается лишь в значениях полей F1: обратите внимание на «714ce4NN» и Вы заметите, что лишь последние два символа обеспечивают различие DevGUID.F1 для разных Mbr-форматированных дисков, SD-карты и разделов первого из двух Gpt-форматированных VHD. Более того, такой же формат имеют и разные VolGUID.F1, соответствующие разделам на Mbr-форматированных дисках. Но вот в среде Windows 10, где, как уже упоминалось, были изменены алгоритмы создания VolumeGUID, «714ce4NN» приписан лишь двум томам, одному на первом диске, метка System Reserved и одному на втором диске, метка TOSH-MK1646GSX. Более детальный анализ выявления «генетического родства» различных GUID, JS-скрипт EnumDevicesAndVolumes.wsf представляет в специально создаваемом отчете, создаваемом методом ShowResemblanse().

Заключительные замечания к первой части публикации


Объясню использование «Windows Registry» вместо «Системный Реестр» тем, что в моем представлении русское слово «реестр» аналогично «амбарной книге» и именует «плоский файл», а никак не иерархическую базу данных, коей является Windows Registry.

Почему «код-прототип»? Изначально в подражание DISKPART.EXE планировалось написать FAD-код, «Fast And Dirty», но жизнь и Microsoft сначала вынудили убрать слово Fast, ну а потом уже я сам решил сделать код почище и пригодным для быстрого переписывания на C, C++, C#. Но все же код остается ПРОТОТИПОМ в том смысле, что не обеспечивает никакого функционала применительно к объектам, размещенным кодом в трех коллекциях.

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

Впрочем желающие могут не дожидаясь второй части посмотреть и выкачать EnumDevicesAndVolumes.wsf, WhoIsFaster.js по ссылке:

https://github.com/sysprg-46/EnumerateDevicesAndVolumesWin/tree/master

Там же размещены и полные описания на русском в формате DOCX и PDF, а также снимками экрана представлены «длительные» соревновательные циклы, по 10-15 прогонов в средах Windows 7, Windows 8.1 и Windows 10.
Tags:
Hubs:
+8
Comments 3
Comments Comments 3

Articles