Применение метода самоорганизующегося файла в алгоритмах поиска драйвера устройства

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

Одним из первых СП был предложен Джоном Мак-Кэйбом [2]. Его метод перемещал успешно найденную запись, не являющуюся первой в таблице, на один порядок вверх, заменяя его место предыдущей. Л. Ривест [4] позже доказал, что при длительной работе метод перестановки использует меньше сравнений, чем ранее используемый метод перемещения найденной записи в начало таблицы.

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

Постановка задачи поиска драйвера

Существует PNP-устройство, представленное в виде PNP-строки, разбитой на блоки [1]. В данной статье будут обсуждаться PCI-устройства, хотя все описанные методы применимы для любых PNP-устройств.

Задача поиска драйвера — найти наиболее вероятный драйвер для заданного устройства, описанного в формате PNP-строки.

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

• 1.    Собственно путь на драйвер в формате абсолютной ссылки на файловый ресурс в нотации ОС Microsoft Windows (C:\DRIVERS\VIDEO\...).

• 2.    Версия драйвера в формате k.l.m.n, где k — главная версия (major version), l — подчиненная версия (minor version), m — вторая главная версия (submajor version), n — вторая подчиненная версия (subminor version).

• 3.    Дата выпуска драйвера (driver_date) в формате mm/dd/yyyy, где mm — полный номер месяца (01, 02, 03 и т.д.), dd — полный номер числа месяца (01, 02, ….12, …31), yyyy — полный номер года (2003, 2004 и т.д.).

• 4.    Дата добавления драйвера в базу драйверов в формате даты выпуска драйвера.

• 5.    Список устройств, поддерживаемых драйвером.

• 6.    Список поддерживаемых драйвером аппаратных платформ.

• 7.    Список поддерживаемых драйвером программных платформ.

Дополнительно драйвер может содержать следующую информацию:

• 1.    Строка класса драйвера — CLASS_STRING . Строковое обозначение класса драйвера ( SYSTEM — системный драйвер; MEDIA — драйвер многофункциональных мультимедиа устройств; NET — драйвер сетевого устройства и др.).

• 2.    Результаты установки драйвера для устройства в рамках разных аппаратных и программных платформ.

Кэшированные таблицы

Рассмотрим наиболее часто используемый метод внутреннего СП — кэширование. Алгоритм описывается следующим образом.

• 1.    Найти в таблице соответствий связку устройства с драйвером.

• 2.    Если связка найдена, вернуть ссылку на драйвер и завершить алгоритм.

• 3.    Если связка не найдена, запустить алгоритм поиска драйвера.

• 4.    Если драйвер найден, добавить в таблицу сопоставления связку устройства и драйвера.

• 5.    Вернуть ссылку на драйвер и завершить алгоритм.

• 6.    Если драйвер не найден, завершить алгоритм с ошибкой.

Ниже на рис. 1 приводится полный алгоритм поиска драйвера (в дальнейшем в статье мы будем на него ссылаться).

• 72          DV.Major Version,

• 73          DV.Minor Version,

• 74          DV.Sub_Major_Version,

• 75          DV.Sub Minor Version,

• 76           MAX(DV.Stamp Date),

DV.InspectionFlag,

• 78          CASE

• 79           WHEN DV.ExpirationDate S NOT MULL

• 80             THEN CONVERT(datetime, DV.ExpirationDate, 103:

• 81            ELSE NULL

• 82           END,

• 83          CAST(CASE WHEN DV.ExpirationDate IS NOT NULL THEN 1 ELSE 0 END AS bit)

• 84    FROM dbo.av driverOSVersion DV

• 85    WHERE Device ID - ©device id

• 86     AND Subsystem_ID - ©subsystem_id

• 87     AND Version = ©version

• 88    GROUP BY DV.DriverPath ID, DV.Major Version, DV.Minor Version, DV.                xr

Sub_Major_Version, DV.Sub_Minor_Version,

• 89            DV.InspectionFlag, DV.ExpirationDate

• 90    UNION ALL

• 91    SELECT DISTINCT DV.DriverPath_ID,

• 92               2,

• 93            MAX (DV.Driver Date.',

• 94          DV.Major_Version,

• 95          DV.Minor Version,

• 96          DV.Sub Major Version,

• 97          DV.Sub_Minor_Version,

• 98           MAX(DV.Stamp Date),

• 99          DV.InspectionFlag,

100           CASE

101           WHEN DV.ExpirationDate IS NOT NULL

102             THEN CONVERT(datetime, DV.ExpirationDate, 103;

103            ELSE NULL

104            END,

105          CAST(CASE WHEN DV.ExpirationDate IS NOT NULL THEN 1 ELSE 0 END AS bit)

106 FROM dbo.av_driverOSVersion DV

107 WHERE Device ID - ©device id

108     AND Subclass ID = ©subclass id

109     AND Version ©version

111            DV.InspectionFlag, DV.ExpirationDate

112 UNION ALL

113 SELECT DISTINCT DV.DriverPath_ID,

114               3,

117          DV.Minor_Version,

120          MAX(DV.Stamp_Date),

121          DV.InspectionFlag,

122           CASE

123           WHEN DV.ExpirationDate IS NOT NULL

124             THEN CONVERT(datetime, DV.ExpirationDate, 103)

125            ELSE NULL

126           END,

127          CAST(CASE WHEN DV.ExpirationDate IS NOT NULL THEN 1 ELSE 0 END AS bit)

129   WHERE Device_ID @device_id

130 AND Version = ©version

Sub_Major_Version, DV.Sub_Minor_Version,

132            DV.InspectionFlag, DV.ExpirationDate

133 UNION ALL

134 SELECT DISTINCT DV.DriverPath_ID,

135               4,

137           DV.Major_Version,

140          DV.Sub_Minor_Version,

142          DV.InspectionFlag,

143           CASE

WHEN DV.ExpirationDate S NOT MULL

THEN CONVERT(datetime, DV.ExpirationDate, 103} ELSE NULL

END,

CAST(CASE WHEN DV.ExpirationDate IS NOT NULL THEN 1 ELSE 0 END AS bit) FROM dbo.av_driverOSVersion DV WHERE Device ID IS NULL

AND Subsystem ID IS NULL

AND Subclass_ID @subclass_id

AND Version = ^version

Sub_Major_Version, DV.Sub_Minor_Version,

DV.InspectionFlag, DV.ExpirationDate

— Посмотрим, сколько нашли драйверов SELECT Sent - COUNT(DISTINCT Path_IDj FROM @drivers

PRINT ’Всего найдено драйверов: * + CONVERT(char, ©ent:

IF @cnt = 0

BEGIN

PRINT ’Для указанного устройства драйверов не найдено!’ GOTO ERROR

END

IF 9cnt = 1

JOIN ©drivers D ON D.Path_ID = DF.DriverPath_ID

PRINT ’Найден драйвер по поиску. ID: 1 * CONVERT(char, ©d_id! GOTO SUCCESS

END

— 0. Приоритет (Поле Priority)

IF (SELECT COUNT(DISTINCT Priority) FROM ©drivers: 1 BEGIN

DELETE ©drivers FROM ©drivers D JOIN (SELECT MIN(Priority) AS Priority

FROM ©drivers: MD ON D.Priority ! = MD.Priority END

IF (SELECT COUNT(DISTINCT Path_ID) FROM ©drivers = 1 BEGIN

FROM v_driverlnfo DF

JOIN ©drivers D ON D.Path_ID ^ DF.DriverPath_ID

PRINT ’Найден драйвер по фильтру приоритетов. ID: * + CONVERT(char, @d_id: GOTO SUCCESS

END

— 1. Аппаратная ллафторма

IF (SELECT COUNT(DISTINCT Path_ID) FROM ©drivers) - 1 BEGIN

JOIN ©drivers D ON D.Path_ID - DF.DriverPath_ID

PRINT ’Найден драйвер по фильтру аппаратной платформы. ID: * - CONVERT(char, ©W d id)

GOTO SUCCESS

END

— 2. Дата драйвера

DELETE ©drivers FROM ©drivers DI JOIN 'SELECT MAX(Driver_Date: AS Driver_Date

Рис. 1. Полный алгоритм поиска драйвера

Алгоритм представляет собой последовательный поиск во временной таблице с применением ранжирования. Задача самоорганизации реализуется в двух операторах. Первый (строки 15—34) проверяет наличие результатов поиска драйвера в таблице соответствия. Если драйвер найден, алгоритм завершает свою работу. В ином случае запускается процедура поиска драйвера. Если драйвер найден, в таблицу соответствия добавляется новая запись с информацией об устройстве и найденном для него драйвере; а также добавляется версия операционной системы (ОС), характеризующая программную платформу, для которой был найден драйвер. Указанный алгоритм имеет один существенный недостаток — при появлении нового драйвера он не будет найден при поиске, т.к. в таблице сопоставления уже существует связка устройства с драйвером. Решением этой проблемы является применение метода внешней самоорганизации, когда в таблицу сопоставления добавляется запись на этапе регистрации драйвера в БД. На рис. 2 показан алгоритм добавления нового драйвера в таблицу.

• —    Добавим только те устройства, для которых нет сопоставления с 0path_id с указанной версией ОС INSERT INTO dbo.DeviceDriver

(PCIDevice_ID, Path_ID, [Version], Priority, Driver_Date, MJ_Version, MN_Version, SMJ_Version, SMN_Version) SELECT PCIDevice_ID, 0path_id, [Version] , MIN(Priority) AS Priority, Driver_Date, MJ_Version, nN_Version, SMJ_Version, SMN_Version FROM @devices D WHERE NOT EXISTS (SELECT DD.Path_ID FROM dbo.DeviceDriver DD WHERE D.PCIDevice_ID = DD.PCIDevice_ID AND D.[Version] = DD.[Version]) GROUP BY PCIDevice_ID, [Version], Driver_Date, MJ_Version, MN_Version, SMJ_Version, SMN_Version

• —    Обновим драйвера для устройств, у которых существует сопоставление с драйверов с указанной версией, — но с меньшим рангом UPDATE dbo.DeviceDriver

SET Path_ID = CASE WHEN DD.Priority < D.Priority THEN 0path_id

ELSE CASE WHEN DD.Driver_Date < D.Driver_Date THEN 0path_id

ELSE CASE WHEN DD.SMN_Version < D.SMN_Version THEN 0path_id

ELSE CASE WHEN DD.SMJ_Version < D.SMJ_Version THEN 0path_id

ELSE CASE WHEN DD.MN_Version < D.MN_Version THEN 0path_id

ELSE CASE WHEN DD.MJ_Version < D.MJ_Version THEN 0path_id ELSE DD.Path_ID END

END

END

END

END END

FROM dbo.DeviceDriver DD

JOIN 0devices D ON D.PCIDevice_ID = DD.PCIDevice_ID AND D.[Version] = DD.[Version]

Рис. 2. Алгоритм добавления нового драйвера в таблицу

В операторе INSERT в таблицу сопоставления ( DeviceDriver ) добавляются лишь те устройства, которых нет в таблице с указанной версией ОС. При обновлении (оператор UPDATE ) производится сравнение поочередное сравнение двух строк — информация с существующим сопоставленным драйвером с информацией о вновь найденном драйвере для устройства. Как и в алгоритме поиска драйвера сначала сравниваются ранги. Если устройство было найдено для драйвера по критерию с более высоким рангом, то происходит замена ранее сопоставленного драйвера на найденный. Такие же действия последовательно осуществляются для даты драйвера и его версии.

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

Избыточные данные

Зачастую для ускорения времени выполнения алгоритма приходятся добавлять избыточную информацию. Подобный механизм реализован в алгоритме, показанном на рис. 1. В нем формируется временная таблица результатов поиска по критериям PNP-строк. При этом в таблицу добавляется информация о версии, дате создания и дате регистрации драйвера. Это обеспечивает возможность работы с данными в оперативной памяти, не используя постоянные таблицы, находящиеся в файловой системе. Однако эта информация касается лишь драйвера и не имеет в сущности отношения к устройству. Единственное, что объединяет драйвер и устройство – это PNP-строка. Но есть еще одна сущность, существующая только для драйверов, хотя может быть применена и для устройств. Это строка класса драйвера. В стандарте PCI устройство обладает, так называемым, классом, — кодированным описанием типа устройства (см. табл. 1).

Таблица 1

Список некоторых классов PCI-устройства

Base devices
Mass storage controllers
Network controllers
Display controllers
Multimedia controllers
Memory controllers
Bridge devices
Simple communications controllers
Base system peripherals
Input devices
Docking stations	A
Processors	B
Serial bus controllers	C

В табл. 2 перечислены некоторые классы драйверов.

Таблица 2

Список некоторых классов драйверов

DISPLAY

HDC

MEDIA

MODEM

MULTIFUNCTION

MULTIPORTSERIAL

NET

PCMCIA

PORTS

SCSIADAPTER

SDHOST

SYSTEM

USB

Сравнив эти таблицы, можно увидеть соответствия. Например, класс устройства Display controllers сопоставим с классом драйвера DISPLAY ; Network controllers — NET; Base devices, Mass storage controllers, Bridge devices — SYSTEM; и так далее. Эту закономерность можно применить в алгоритме СП.

На рис. 3 показаны изменения обсуждаемого алгоритма (отмечены красной чертой). В блок входных параметров добавлена переменная @class_string , содержащая значение класса драйвера, но уже для устройства. Во временную таблицу добавляется информация по классу найденного драйвера. На рис. 4 показаны действия по удалению драйверов, не подходящих под критерии поиска по классу драйвера.

В

A CREATE PROCEDURE [dbo] [d_FindDriver_4]

0device_id int, 0 s ub s уs t em_ i ci i nt 0 s ub с 1as s_ i cl i n t, 0os id int.

0р1at fоrm_id int

ID	устройства из	kr im. db о . Devic е
ID	подсистемы из	krim.dbo.SubSystem
ID	подкласса из	krim.dbo.Subclass
ID	операционной	системы

Версия операционной системы

ID аппаратной платформы

0class string varchar(2Ui

2 0

2 1

2 3

2 4

2 5

2 6

2 7

2 9

3 0

3 1

3 2

3 3

3 4

3 5

3 6

3 7

3 8

3 9

0d_id int. OUTPUT)

AS

BEGIN

SET NOCOUNT ON

Строка класса драйвера

ID записи в. krim. dbo.DriverInfо (ID драйвера в. *.inf)

DECLARE 0cnt int

— Определим таблицу найденных драйверов.

DECLARE 0drivers TABLE

(Path_ID int, Priority int, Class_String varchar(20), Driver_Date datetime, MJ_Version int, HN_Version int, SMJ_Version int, SHN_Version int, Date datetime Inspection_Flag int, Expiration_Date datetime, Expiration_Flag bit)

INSERT INTO 0drivers

(Path_ID, Priority, Class_String, Driver_Date, MJ_Version, MN_Version, Date, Inspection_Flag, Expiration_Date, Expiration_Flag)

S E L EСT DV.DriverPath ID,

Самый высокий приоритет присваивает драйверам, найденным по

Class String,

MAX(DV. Driver_Date),

DV.M1nor _Ve r s i оn,

DV.Sub_Major_Version,

DV. Sub_Minor_Version,

MAX(DV. Stamp_Date) , DV.InspectionFlag,

CASE

WHEN DV.ExpirationDate IS MOT NULL

THEN CONVE RT (dat et line, DV. E xp 1 rat 1 оnDate, 10 3 )

ELSE NULL

END,

Рис. 3. Изменения алгоритма

SMJ Version, SHN Version,

полному совпадению

162	— Отсечение no Class_String
163![ 164!	] DELETE FROM 0 drivers
165 166!	WHERE Class_String != 0ciass_string
167![ 168	] SELECT @cnt = COUNT(DISTINCT Path_ID) FROM 0drivers
169	PRINT 'Всего найдено драйверов: 1 + CONVERT(char, 0cnt

171![ 172! 173	] IF 0cnt = 0 GOTO ERROR
174![	] IF 0cnt = 1
175![	1 BEGIN

176!я SELECT 0d_id = MAX DF ID

177! FROM v_driverInfo DF

178! - JOIN 0drivers D ON D Path_ID DF DriverPath_ID

179!

180! PRINT 'Найден драйвер по фильтру Class_String. ID: 1 + CONVERT(char, 0d_id

181! GOTO SUCCESS

182! - END

183!

Рис. 4. Алгоритм удаления драйверов

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

Алгоритм с обратной связью

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

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

• 1.    В процессе поиска выбирать только те драйвера, для которых, либо существует информация об успешной установке на данной версии ОС, либо эта информация отсутствует. Т.е. производить исключение всех драйверов, для которых указано, что для заданной ОС установка прошла неудачно.

• 2.    После процедуры установки драйвера сохранить информацию о результате установки, чтобы использовать ее в следующих запусках алгоритма.

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

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

• - - Исключим драйвера с результатом неудачной установки и

• - - те, чья дата цифровой подписи на момент поиска истекла.

• - - При этом надо учитывать, что под исключени по дате

• - - подпадают лишь те драйвера, которые имеют цифровую подпись, -- т.е. значение даты не пустое DELETE

FROM @drivers

WHERE InspectionFlag != 1 — факт неудачной установки

OR (ExpirationFlag = 1 AND ExpirationDate > GETDATE())

Рис. 5. Изменения в алгоритме

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

Разработанный в 60-е годы прошлого века метод перестановок развился от алгоритмов Мак-Кейба и Ривеста до моделей кэшированных таблиц и систем с обратной связью. На современном этапе развития идеи самоорганизующихся алгоритмов базируются на принципах ранжирования и упомянутой ранее обратной связи. Также все более широкое применение находят эволюционные алгоритмы, идеи нечеткой логики и нейронные сети [4]. Стоит отметить одну из первых сетей с применением самоорганизации, — нейронную сеть с обратным распространением ошибки. Основная идея состоит в распространении сигналов ошибки от выходов сети к её входам, в направлении, обратном прямому распространению сигналов в обычном режиме работы. Впервые подобный метод был описан Полем Дж. Вербосом в 1974 г., и далее развит Дэвидом И. Румельхартом и Рональдом Дж. Вильямсом в 1986 г.

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