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

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

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

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

аспирант, ведущий программист

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

кандидат технических наук, доцент

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

Поиск в больших массивах данных, когда имеется индексированная информация о некоторых сущностях, основан на двух основных составляющих: ранжирование и фильтрация.

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

В данной статье описан третий механизм обработки результирующей выборки - механизм правил замены.

На примере алгоритма автоматического поиска драйверов устройств показаны преимущества использования правил замены, а также предложены варианты реализации на основе искусственного языка с конструкциями if-else и подмножества структурированного языка разметки XML.

Механизмы поиска. Рассмотрим механизм поиска драйверов.

Каждый драйвер характерезуется информацией по устройствам, для которых драйвер создан. Информация об устройстве представлена в виде строки, разбитой на блоки. Формат этой строки определен стандартом Plug and Play, разработанным группой компаний в главе с Intel в 1992 году [2].

Общий механизм поиска драйвера выглядит следующим образом:

1. Создается база драйверов, куда в полуавтоматическом режиме добавляется информация о драйверах. Это позволяет использовать иструменты поиска, реализованные в базе данных (БД).

2. На вход функции поиска подается PNP-строка устройства, для которого необходимо найти драйвер.

3. На выходе возвращается выборка (набор) идентификаторов драйверов в БД, попавших под критерии поиска.

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

1. PNP-строка - строковое описание устройства, поддерживаемое драйвером [3]. Пример - PCI\VEN_1002&DEV_7145&REV_00, где PCI - это перечислитель устройства, VEN_1002 - префик производителя устройства и идентификатор производителя устройства, DEV - префик устройства и его идентификатор, REV - префик версии устройства и его идентификатор. Также в строке могут встречаться CC - префик класса и подкласса устройства, SUBSYS - префикс подсистемы и поставщика подсистемы устройства.

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

3. Дата драйвера - аналогично версии драйвера, дата также производит отсечение однотипных драйверов, возвращая драйвер с самой последней датой.

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

5. Аппаратная платформа - для разных аппаратных платформ существуют разные драйвера. Драйвер для платформы X86 не подойдет для платформы X64 и наоборот.

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

1. Поиск драйвера осуществляется на основе гибкого сопоставления PNP-строки устройства с PNP-строкой драйвера. Под гибким сопоставлением понимается итеративное отсечение блоков PNP-строки с последующим сравнением со строкой драйвера.

2. Выбираются драйвера только для указанной аппаратной платформы

3. Выбираются драйвера только для указанной программной платформы

4. Выбираются драйвера с максимальной версией

5. Выбираются драйвера с максимальной датой.

Гибкий поиск драйвера - это механизм, предложенный компанией Microsoft в 1995 году. Что понимается под этим поиском?

Как уже было описано выше, каждая PNP-строка разделена на блоки - блок производителя микросхемы (VEN), блок устройства (DEV), блок производителя платы (SUBSYS), блок класса устройства (CC), блок версии устройства (REV). Драйвера часто описываются не полной PNP-строкой, а лишь ее частью. Например, VEN_1002&CC_0300. Что означает, что данный драйвер подоходит для всех устройство производителя 1002 с классом 0300.

При сопоставлении мы можем говорить о, так называемых, шаблонах сопоставления, или в терминологии Microsoft, совместимых идентификаторах (Compatible Ids) [5]:

o Шаблон полного совпадения PCI\VEN_%&DEV_%&SUBSYS%&CC_%&REV_%

o Шаблон без версии - PCI\VEN_%&DEV_%&SUBSYS%&CC_%

o Шаблон без подсистемы и версии - PCI\VEN_%&DEV_%& CC_%

o Шаблон без подсистемы, класса и версии - PCI\VEN_%&DEV_%

o Шаблоны по производителю: VEN_%&CC_%; VEN_%

Становится очевидно, что для одного устройства могут быть найдены несколько драйверов.

Как раз на этом этапе применяется механизм ранжирования, где шаблону полного совпадения присваиваетя наивысший ранг, т.к. драйвера, найденные по этому шаблону, наиболее близко подоходят к устройству. Далее, в порядке убывания шаблонов, каждому из них присваивается ранг на порядок ниже предыдущего ранга. Т.е. для шаблона без версии ранг будет присвоен 1, т.к. шаблону полного совпадения присваивается ранг 0.

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

Следущий этап - это фильтрация, согласно правилам поиска.

Исключаеются драйвера, неподходящие под аппаратную и программную платформы.

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

Далее исключаются драйвера, чьи даты не совпадают с датой драйвера из выборки с максимальной датой.

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

Если после прохождения всех этапов поиска в результирующей выборке остается несколько результатов, то выбирается первый из набора.

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

Как показывает опыт, в некоторых случаях успешно найденный драйвер приводит к сбоям в системе, хотя все правила поиска были соблюдены.

Другой вариант - это проблемы с, так называемыми, многокомпонентыми устройствами, которым необходим драйвер шины и драйвер устройства.

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

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

Формирование правил - процесс ручной, однако может быть автоматизирован, посредством языка правил.

Приведем возможные варианты:

? Для одного, либо нескольких устройств заменить драйвер А на драйвер Б. При этом драйвер А должен входить в результирующую выборку, а драйвер Б может быть пустым (т.е. правило замены вырождается в правило исключения).

? Для одного, либо нескольких устройств добавить драйвер А для драйвера Б. При этом драйвер А должен входить в результирующую выборку, а драйвер Б не может быть пустым.

Реализация правил может быть различной.

Вариант с конструкциями вида if-for-use показан на рисунке 1.

Опишем работу правил на примере первой конструкции.

Если имеются четрые устройства

PCI\VEN_8086&DEV_2570&SUBSYS_25708086&CC_0600,

PCI\VEN_8086&DEV_2571&CC_0604,

PCI\VEN_8086&DEV_244E&CC_0604,

PCI\VEN_8086&DEV_24D0&CC_0601,

то драйвер PCI\VEN_8086&DEV_24D5&SUBSYS_E0028086&CC_0401 из результирующей выборки заменить на драйвер из каталога AUDIO\Adi\SoundMAX.

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

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

Рис. 1.

Другой подход к реализации языка правил - это использование расширенного языка разметки XML [6].

Основными преимуществами реализации правил на языке XML являются следующие:

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

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

? Большинство современных СУБД имеют встроенные механизмы работы с XML-подобными структурами.

? Интепретаторы XML-данных работают во много раз быстрее интерпретаторов строковых данных.

? Язык XML по своей структуре предполагает расширение. Соответственно правила можно бесконечно много расширять, добавляя новый функционал.

Приведем пример, описанного выше правила, только с использованием XML (рисунок 2).

Рис. 2.

Символы-разделители PNP-блоков (&) заменены на вертикальную черту (|), т.к. символ & является зарезервированным в стандарте языка XML.

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

Однако эти нововведения не коснулись алгоритмов поиска драйверов. Использующиеся сейчас алгоритмы (в частности алгоритмы, реализованные в PNP Manager операционной системы Windows) в момент времени работают лишь с одним устройством и не учитывают специфики работы этого устройства вместе с другими устройствами системной платы.

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

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

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

Литература

1. Nong Ye, “The hand book of Data mining”, Mahwah, New Jersey, 2003.

2. http://en.wikipedia.org/wiki/Plug-And-Play

3. http://en.wikipedia.org/wiki/Peripheral_Component_Interconnect

4. http://en.wikipedia.org/wiki/PCI_Configuration_Space

5. http://msdn2.microsoft.com/en-us/library/ms791082.aspx

6. http:// http://www.w3.org/XML/.

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