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

Размещено на http://www.allbest.ru/

Современная гуманитарная академия

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

Ильин Игорь Андреевич,

Руководитель к.т.н., доцент

Белянина Наталья Васильевна

Аннотация

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

Ключевые слова: самоорганизующийся поиск, PCI-устройства, алгоритмизация.

Основная часть

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

Одним из первых СП был предложен Джоном Мак-Кэйбом [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 приводится полный алгоритм поиска драйвера (в дальнейшем в статье мы будем на него ссылаться).

поиск алгоритм кэширование самоорганизующий

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

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

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

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

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

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

Таблица 1

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

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

Таблица 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

1. Identifiers for PCI Devices. Microsoft Developer Network. [В Интернете] http://msdn.microsoft.com/en-us/library/ms791082.aspx.

2. MacCabe, John. 1965. Operation Research. 1965. pp. 609-618.

3. Nong Ye, 2003. The handbook of data mining. LEA. 2003. Arizona State University

4. Rivest, Ronald L. 1976. CACM. 1976. pp. 63-67.

5. Кнут, Дональд Э. 2000. Искусство программирования. Москва: Вильямс, 2000. Т. Сортировка и поиск.

Размещено на Allbest.ru