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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

Применение метода самоорганизующегося файла в алгоритмах
поиска драйвера устройства
Ильин Игорь Андреевич,
Современная гуманитарная академия.
Руководитель — к.т.н., доцент Белянина Наталья Васильевна
Приводится краткая характеристика метода самоорганизующегося поиска, описываются первые подобные алгоритмы- на примере поиска драйверов РС1-устройств рассматриваются методы модификации исходного множества поиска, внесения избыточных данных- алгоритм с обратной связью.
Ключевые слова: самоорганизующийся поиск, РС1-устройства, алгоритмизация.
В отличие от классических методов поиска в среде неупорядоченных данных, самоорганизующийся поиск (СП) основывается на том предположении, что множество поиска постоянно изменяется особым образом, уменьшая тем самым частоту обращений к каждой записи. Суть самоорганизации заключается в том, что при каждом последующем выполнении алгоритма время его работы уменьшается.
Одним из первых СП был предложен Джоном Мак-Кэйбом [2]. Его метод перемещал успешно найденную запись, не являющуюся первой в таблице, на один порядок вверх, заменяя его место предыдущей. Л. Ривест [4] позже доказал, что при длительной работе метод перестановки использует меньше сравнений, чем ранее используемый метод перемещения найденной записи в начало таблицы.
Как видно из описанного метода перестановки Мак-Кэйба, принцип самоорганизации заключается в изменении исходного множества поиска в зависимости от результатов работы алгоритма. При этом сама процедура модификации множества поиска реализована в самом алгоритме. Аналогично задачам сортировки [5] будем различать методы изменения множества на внутренние, где изменения происходят внутри алгоритма поиска, и внешние — изменение множества поиска осуществляется другими алгоритмами, а алгоритм поиска лишь использует ранее обработанное множество.
Постановка задачи поиска драйвера
Существует РКР-устройство, представленное в виде РКР-строки, разбитой на блоки [1]. В данной статье будут обсуждаться РС1-устройства, хотя все описанные методы применимы для любых РКР-устройств.
Задача поиска драйвера — найти наиболее вероятный драйвер для заданного устройства, описанного в формате РКР-строки.
При этом существует база драйверов, состоящая из нескольких таблиц и логически представленная следующими сущностями.
1. Собственно путь на драйвер в формате абсолютной ссылки на файловый ресурс в нотации ОС Microsoft Windows (C: DRIVERSVIDEO…).
2. Версия драйвера в формате k.l.m. n, где k — главная версия (major version), l — подчиненная версия (minor version), m — вторая главная версия (submajor version), n — вторая подчиненная версия (subminor version).
3. Дата выпуска драйвера (driver_date) в формате mm/dd/yyyy, где mm — полный номер месяца (0І, 02, 0З и т. д.), dd — полный номер числа месяца (0І, 02, ,… І2, … ЗІ), yyyy — полный номер года (200З, 2004 и т. д.).
4. Дата добавления драйвера в базу драйверов в формате даты выпуска драйвера.
5. Список устройств, поддерживаемых драйвером.
6. Список поддерживаемых драйвером аппаратных платформ.
7. Список поддерживаемых драйвером программных платформ.
Дополнительно драйвер может содержать следующую информацию:
1. Строка класса драйвера — CLASSSTRING. Строковое обозначение класса драйвера (SYSTEM — системный драйвер- MEDIA — драйвер многофункциональных мультимедиа устройств- NET — драйвер сетевого устройства и др.).
2. Результаты установки драйвера для устройства в рамках разных аппаратных и программных платформ.
Кэшированные таблицы
Рассмотрим наиболее часто используемый метод внутреннего СП — кэширование. Алгоритм описывается следующим образом.
1. Найти в таблице соответствий связку устройства с драйвером.
2. Если связка найдена, вернуть ссылку на драйвер и завершить алгоритм.
3. Если связка не найдена, запустить алгоритм поиска драйвера.
4. Если драйвер найден, добавить в таблицу сопоставления связку устройства и
драйвера.
5. Вернуть ссылку на драйвер и завершить алгоритм.
6. Если драйвер не найден, завершить алгоритм с ошибкой.
Ниже на рис. 1 приводится полный алгоритм поиска драйвера (в дальнейшем в статье мы будем на него ссылаться).
1 CREATE PROCEDURE (dbo). d FindDriver 4]
2 Sdevice id int, — ID устройства из krim. dbo. Device
3 0subsystem_id int, -- ID подсистемы из krim. dbo. SubSystem
4subclass id int, — ID подкласса из krim. dbo. Subclass
5 0os id int, — ID операционной системы
6 Sversion int, — Версия операционной системы
Splatform id int, -- ID аппаратной платформы
@d_id int OUTPUT) — ID записи в krim. dbo. Driverlnfo (ID драйвера в *. inf)
9 AS
10 BEGIN
11 SET NOCOUNT ON
12
13 DECLARE gent int
14
15 — Проверка наличия сопоставления
16 IF SELECT COUNT (*)
17 FROM dbo. DeviceDriver DD
18 JOIN dbo. v_pciDevice D ON D. ID ¦ DD. PCIDevice_ID
19 WHERE D. Device ID Sdevice id
20 AND D. Subsystem ID ¦ Ssubsystem id
21 AND D. Subclass_ID — 8subclass_id
22 AND DD. Version! 1 Aversion) & gt- 0
23 BEGIN
24 SELECT @d_id — MAX (DF. ID)
25 FROM dbo. v driverlnfo DF
26 JOIN dbo. DeviceDriver DD ON DF. DriverPath ID DD. Path__ID
27 JOIN dbo. v_pciDevice D ON D. ID DD. PCIDevice_ID
28 WHERE D. Device ID — (c)device id
29 AND D. Subsystem ID Ssubsystem id
30 AND D. Subclass_ID 8subclass_id
31 AND DD. Version] ¦ Aversion
32
33 PRINT '-Найден драйвер по сопоставлению ID: * + CONVERT (char, @d_id)
34 GOTO SUCCESS
35 END
36
37 — Определим таблицу найденных драйверов
38 DECLAREdrivers TABLE
39 (Path_ID int, Priority int, Driver_Date datetime,
MJ Version int, MN_Version int, SMJ_Version int, SMN_Version int, Date *
datetime,
41 Inspection_Flag int, Expiration_Date datetime, Expiration_Flag bit)
42
43 INSERT INTO ^drivers
Path_ID, Priority, Driver_Date, MJ_Version, MN_Version, SMJ_Version,
SMN Version,
45 Date, Inspection Flag, Expiration_Date, Expiration_Flag)
4 6 SELECT DV. DriverPath_ID,
0, -- Самый высокий приоритет присваивает драйверам, найденным по полному* совпадению
48 МАХ (DV. Driver_Date),
49 DV. Major Version,
50 DV. Minor Version,
51 DV. Sub_Major_Version,
52 DV. Sub Minor Version,
53 MAX (DV. Stamp Date),
54 DV. InspectionFlag,
55 CASE
56 WHEN DV. ExpirationDate IS NOT NULL
57 THEN CONVERT (datetime, DV. ExpirationDate, 103)
58 ELSE NULL
59 END,
60 CAST (CASE WHEN DV. ExpirationDate IS NOT NULL THEN 1 ELSE 0 END AS bit)
61 FROM dbo. av driverOSVersion DV
62 WHERE Device ID = Sdevice id
63 AND Subsystem_ID @subsystem_id
64 AND Subclass ID = § subclass__id
65 AND Version = Sversion
66 GROUP BY DV. DriverPath_ID, DV. Major_Version, DV. Minor_Version, DV. *
Sub Major Version, DV. Sub Minor Version,
67 DV. InspectionFlag, DV. ExpirationDate
68 UNION ALL
69 SELECT DISTINCT DV. DriverPath_ID,
70 1,
71 MAX (DV. Driver Date),
72 DV. Major Version,
DV. Minor Version,
74 DV. Sub_Major_Version,
75 DV. Sub Minor Version,
76 MAX IDV. Stamp Date),
DV. InspectionFlag,
78 CASE
79 WHEN DV. ExpirationDate IS NOT NULL
80 THEN CONVERT (datetime, DV. ExpirationDate, 103)
81 ELSE NULL
82 END,
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 0device id
86 AND Subsystem_ID = (c)subsystem_id
87 AND Version Aversion
88 GROUP BY DV. DriverPath ID, DV. Major Version, DV. Minor_Version, DV.
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 (c)device id
108 AND Subclass ID (c)subclass id
109 AND Version = (c)version
110 GROUP BY DV. DriverPath ID, DV. Major Version, DV. Minor_Version, DV.
Sub Major Version, DV. Sub Minor Version,
111 DV. InspectionFlag, DV. ExpirationDate
112 UNION ALL
113 SELECT DISTINCT DV. DriverPath_ID,
114 3,
115 MAX (DV. Driver Date),
116 DV. Major Version,
117 DV. Minor_Version,
118 DV. Sub Major Version,
119 DV. Sub 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)
128 FROM dbo. av driverOSVersion DV
129 WHERE Device_ID 0device_id
130 AND Version — (c)version
131 GROUP BY DV. DriverPath ID, DV. Major Version, DV. Minor_Version, DV. X
Sub_Major_Version, DV. Sub_Minor_Version,
132 DV. InspectionFlag, DV. ExpirationDate
133 UNION ALL
134 SELECT DISTINCT DV. DriverPath_ID,
135 4 ,
136 MAX (DV. Driver Date),
137 DV. Major_Version,
138 DV. Minor Version,
139 DV. Sub Major Version,
140 DV. Sub_Minor_Version,
141 MAX (DV. Stamp Date),
142 DV. InspectionFlag,
143 CASE
144 WHEN DV. ExpirationDate IS НОТ NULL
145 THEN CONVERT (datetime, DV. ExpirationDate, 103)
146 ELSE NULL
147 END,
148 CAST (CASE WHEN DV. ExpirationDate IS NOT HULL THEN 1 ELSE 0 END AS bit)
149 FROM dbo. av_driverOSVersion DV
150 WHERE Device ID IS NULL
151 AND Subsystem ID IS NULL
152 AND Subclass_ID (c)subclass_id
153 AND Version (c)version
154 GROUP BY DV. DriverPath ID, DV. Major Version, DV. Minor_Version, DV. *
Sub_Major_Version, DV. Sub_Minor_Version,
155 DV. InspectionFlag, DV. ExpirationDate
156..
157 — Посмотрим# сколько нашли драйверов
158 SELECT (c)cnt COUNT DISTINCT Path_ID
159 FROM (c)drivers
160 PRINT '-Всего найдено драйверов: '- + CONVERT (char, (c)cnt)
161
162 IF (c)cnt — 0
163 BEGIN
164 PRINT '-Для указанного устройства драйверов не найдено!'-
165 GOTO ERROR
166 END
167
168 IF (c)cnt = 1
169 BEGIN
170 SELECT (c)d id MAX (DF. ID)
171 FROM v driver Info DF
172 JOIN (c)drivers D ON D. Path_ID DF. DriverPath_ID
173
174 PRINT '-Найден драйвер no поиску. ID: '- + CONVERT (char, (c)d_id)
175 GOTO SUCCESS
176 END
177
178 — 0. Приоритет (Поле Priority)
179 IF (SELECT COUNT (DISTINCT Priority) FROM (c)drivers) & gt- 1
180 BEGIN
181 DELETE (c)drivers
182 FROM (c)drivers D
183 JOIN SELECT MIN (Priority& gt- AS Priority
184 FROM (c)drivers) MD ON D. Priority ≠ MD. Priority
185 END
186
187 IF (SELECT COUNT (DISTINCT Path_ID) FROM (c)drivers) 1
188 BEGIN
189 SELECT (c)d id MAX DF. ID
190 FROM v_driverInfo DF
191 JOIN (c)drivers D ON D. Path_ID DF. DriverPath_ID
192
193 PRINT '-Найден драйвер по фильтру приоритетов. ID: '- + CONVERT (char, (c)d_id)
194 GOTO SUCCESS
195 END
196
197 — 1. Аппаратная плафторма
198 DELETE (c)drivers
199 FROM (c)drivers D
200 JOIN v driverPlatform DP ON DP. ID D. ID
201 WHERE DP. Platform_ID !& gt- (c)platform_id
202
203 IF (SELECT COUNT (DISTINCT Path_ID) FROM (c)drivers) — 1
204 BEGIN
205 SELECT (c)d_id MAX (DF. ID)
206 FROM v driverlnfo DF
207 JOIN (c)drivers D ON D. Path_ID = DF. DriverPath ID
208
PRINT '-Найден драйвер по фильтру аппаратной платформы. ID: '- + CONVERT (char, (c)tf d id)
210 GOTO SUCCESS
211 END
212
213 — 2. Дата драйвера
214 DELETE (c)drivers
215 FROM (c)drivers D1
216 JOIN (SELECT MAX (Driver Date) AS Driver Date
Г'-тп 1& lt-) ш 83
217 FROM Sdrivers) D2 ON D1. Driver_Date ≠ D2. Driver _Date
218
219
220 IF: SELECT COUNT (DISTINCT Path ID FROM edrivers) 1
221 BEGIN
222 SELECT Sd_id MAX DF. ID
223 FROM v driverlnfo DF
224 JOIN Sdrivers D ON D. Path_ID DF. DriverPath_ID
225
226 PRINT '-Найден драйвер по фильтру даты драйвера. ID: '- + CONVERT і char, 8d_id
227 GOTO SUCCESS
228 END
229
230 — 4. Версия драйвера
231 DELETE Sdrivers
232 FROMdrivers D
233 JOIN (SELECT Dl. Path ID
234 FROM Sdrivers D1
235 JOIN (SELECT MAX (MJ Version) AS MJ Version,
236 MAX MN Version) AS MN Version,
237 MAX (SMJ Version) AS SMJ Version,
238 MAX: SMN Version) AS SMN Version
239 FROM Sdrivers) D2 ON Dl. MJ Version D2. MJ Version
240 AND Dl. MN Version — D2. MN Version
241 AND Dl. SMJ Version = D2. SMJ Version
242 AND Dl. SMN Version = D2. SMN_Version) DO ON D.
Path_ID DO. Path_ID
243
244
245 IF (SELECT COUNT (DISTINCT Path ID) FROM Sdrivers) — 1
246 BEGIN
247 SELECT ed id = MAX (DF. ID)
248 FROM v driverlnfo DF
249 JOIN Sdrivers D ON D. Path_ID DF. DriverPath_ID
250
251 PRINT '-Найден драйвер по фильтру версии драйвера. ID: '- + CONVERT (char# Sd_
252 GOTO SUCCESS
253 END
254
255 — 5. Дата регистрации драйвера
256 DELETE Sdrivers
257 FROM Sdrivers D1
258 JOIN (SELECT MAX (Date) AS Date
259 FROM edrivers) D2 ON Dl. Date ≠ D2. Date
260
261 IF (SELECT COUNT (DISTINCT Path ID) FROM Sdrivers) — 1
262 BEGIN
263 SELECT @d_id — MAX (DF. ID)
264 FROM v driverlnfo DF
265 JOIN Sdrivers D ON D. Path_ID — DF. DriverPath_ID
266
267 PRINT '-Найден драйвер по фильтру даты регистрации драйвера. ID: '- ¦ CONVERT
(char# Sd id)
268 GOTO SUCCESS
269 END
270
271 GOTO ERROR
272
273 SUCCESS:
274 — Добавляем ссылку на найденный дравер
275 INSERT INTO dbo. DeviceDriver DriverPath ID, PCIDevice ID, [Version])
276 SELECT DISTINCT Path ID,
277 P. ID,
278 Sversion
279 FROM dbo. v pciDevice P#
280 Sdrivers D
281 WHERE P. Device ID «Sdevice id
282 AND P. Subsystem ID — Ssubsystem id AND P. Subclass ID Ssubclass id
283
284 RETURN 0
285
286 ERROR:
287 RETURN -1
288 END
289
Рис. 1. Полный алгоритм поиска драйвера
Алгоритм представляет собой последовательный поиск во временной таблице с применением ранжирования. Задача самоорганизации реализуется в двух операторах. Первый (строки 15−34) проверяет наличие результатов поиска драйвера в таблице соответствия. Если драйвер найден, алгоритм завершает свою работу. В ином случае запускается процедура поиска драйвера. Если драйвер найден, в таблицу соответствия добавляется новая запись с информацией об
устройстве и найденном для него драйвере- а также добавляется версия операционной системы (ОС), характеризующая программную платформу, для которой был найден драйвер. Указанный алгоритм имеет один существенный недостаток — при появлении нового драйвера он не будет найден при поиске, т. к. в таблице сопоставления уже существует связка устройства с драйвером. Решением этой проблемы является применение метода внешней самоорганизации, когда в таблицу сопоставления добавляется запись на этапе регистрации драйвера в БД. На рис. 2 показан алгоритм добавления нового драйвера в таблицу.
— Добавим только те устройства, для которых нет сопоставления с 0path_id с указанной версией ОС INSERT INTO dbo. DeviceDriver
(PCIDevice_ID, Path_ID, [Version], Priority, Driver_Date, MJ_Version, MTJ_Version, SMJ_Version, SMN_Versioni SELECT PCIDevice_ID,
0path_id,
[Version],
MIN (Priority) AS Priority,
Dr iver_Date, r HJ_Version,
MN_Version,
SMJ_Version,
SMN_Version FROM 0devices 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 & lt- D. Priority THEN 0path_id
ELSE CASE WHEN DD. Driver_Date & lt- D. Driver_Date THEN Gpath_id
ELSE CASE WHEN DD. SMN_Version & lt- D. SMN_Version THEN 0path_id
ELSE CASE WHEN DD. SMJ_Version & lt- D. SHJ_Version THEN 0path_id
ELSE CASE WHEN DD. MN_Version & lt- D. MN_Version THEN 0path_id
ELSE CASE WHEN DD. M<-J_Version & lt- D. MJ_Version THEN 0path_id ELSE DD. Path_ID END
END
END
END
END
END
FROM dbo. DeviceDriver DD
JOIN Qdevices D ON D. PCIDevice_ID = DD. PCIDevice_ID AND D. Version] = DD. Version]
Рис. 2. Алгоритм добавления нового драйвера в таблицу
В операторе INSERT в таблицу сопоставления (DeviceDriver) добавляются лишь те устройства, которых нет в таблице с указанной версией ОС. При обновлении (оператор UPDATE) производится сравнение поочередное сравнение двух строк — информация с существующим сопоставленным драйвером с информацией о вновь найденном драйвере для устройства. Как и в алгоритме поиска драйвера сначала сравниваются ранги. Если устройство было найдено для драйвера по критерию с более высоким рангом, то происходит замена ранее сопоставленного драйвера на найденный. Такие же действия последовательно осуществляются для даты драйвера и его версии. Этот механизм гарантирует, что при каждой новой регистрации драйвера с устройствами будут сопоставлены наиболее подходящие.
Избыточные данные
Зачастую для ускорения времени выполнения алгоритма приходятся добавлять избыточную информацию. Подобный механизм реализован в алгоритме, показанном на рис. 1. В нем формируется временная таблица результатов поиска по критериям РКР-строк. При этом в таблицу добавляется информация о версии, дате создания и дате регистрации драйвера. Это обеспечивает возможность работы с данными в оперативной памяти, не используя постоянные таблицы, находящиеся в файловой системе. Однако эта информация касается лишь драйвера и не имеет в сущности отношения к устройству. Единственное, что объединяет драйвер и устройство -это РКР-строка. Но есть еще одна сущность, существующая только для драйверов, хотя может быть применена и для устройств. Это строка класса драйвера. В стандарте РС1 устройство обладает, так называемым, классом, — кодированным описанием типа устройства (см. табл. 1).
Таблица 1
Список некоторых классов PCI-устройства
Base devices 0
Mass storage controllers 1
Network controllers 2
Display controllers 3
Multimedia controllers 4
Memory controllers 5
Bridge devices 6
Simple communications controllers 7
Base system peripherals 8
Input devices 9
Docking stations 0A
Processors 0B
Serial bus controllers 0C
В табл. 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 Fincffirivsr 4] (
@device_id int, 0subsystem id int, 0subclass_id int, 0os_id int, 0version int, 0platform_id int,
ID устройства из krim. dbo. Device ID подсистемы из krim. dbo. SubSystem ID подкласса из krim. dbo. Subclass ID операционной системы Версия операционной системы ID аппаратной платформы 0class_str ing varchar (20), — - Строка класса драйвера
0d_id int OUTPUT) — ID записи в krim. dbo. Dr iverlnf о (ID драйвера в *. inf)
AS
BEGIN
SET NOCOUNT ОЫ
DECLARE 0cnt int
— Определим таблицу найденных драйверов DECLARE 0drivers TABLE
(Path_ID int. Priority int, Class_String varchar (20), Driver_Date datetime,
MJ_Version int, MN_Version int, SMJ_Version int, SMN_Version int, Date datetime,
Inspection_Flag int, Expiration_Date datetime, Expiration_Flag bit)
INSERT INTO 0 drivers
(Path ID, Priority, Class String, Driver Date, HJ Version. MN Version, SMJ Version, SMN Version, Date, Inspection_Flag, Expiration_Date, Expiration_Flag)
SELECT DV. DriverPath_ID,
0, — Самый высокий приоритет присваивает драйверам, найденным по полному совпадению Class String .г ИАХ (DV.D г ive r_Dat e) ,
DV. Hajor_Version,
DV. Hinor_Version,
DV. Sub_Hajor_Version.r DV. Sub Minor Version,
ИAX (DV. Stamp_Date) ,
DV. InspectionFlag,
CASE
WHEN DV. ExpirationDate IS NOT NULL 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
Рис. З. Изменения алгоритма
Г'-тп -11 из 83
161|
1621 — Отсечение по Class String
163І 3 DELETE
1Є4І FROM Sdrivers
165І - WHERE Class String ≠ Sclass string
166І
167! 3 SELECT Sent = COUNT (DISTINCT Path IDi
1681 — FROII Bdrivers
169! PRINT '-Всего найдено драйверов: 1 + CONVERT (char, Sent
170!
171! 3 IF Sent 0
1721 — GOTO ERROR
173!
174І з IF Sent 1
175І э BEGIN
176І з SELECT @d id = MX (DF ID
177І FROM v driver Infg DF
17 S1 — JOIN Sdrivers D ON D Path ID DF DriverPath ID
179!
18 0! PRINT '-Найден драйвер по фильтру Class String. ID: '- + CONVERT (char, 0d_id
181! GOTO SUCCESS
1821 — END
183!
Рис. 4. Алгоритм удаления драйверов
Стоит отметить, что соответствие устройства и класса драйвера является однозначным, т. е. у одного устройства может быть только одно значение класса драйвера. Механизм добавления соответствия может быть реализован аналогично механизму кэширования результатов поиска.
Алгоритм с обратной связью
Задачей любого алгоритма является выполнение определенных действий и возвращение результата. Для алгоритмов поиска драйверов этим результатом является значение идентификатора записи в таблице драйверов. Однако общая цель — это найти для устройства драйвер, который бы впоследствии успешно установился в ОС.
В описанных выше алгоритмах поиск драйвера производится без учета информации о факте установки драйвера в ОС. Однако если сохранить информацию об успешной, либо, наоборот, о неудачной установке драйвера, то появится возможность использовать эту информацию при поиске. Общий принцип можно описать следующим образом.
1. В процессе поиска выбирать только те драйвера, для которых, либо существует информация об успешной установке на данной версии ОС, либо эта информация отсутствует. Т. е. производить исключение всех драйверов, для которых указано, что для заданной ОС установка прошла неудачно.
2. После процедуры установки драйвера сохранить информацию о результате установки, чтобы использовать ее в следующих запусках алгоритма.
Если драйвер имеет цифровую подпись, то по правилам сертификации драйверов, период жизни подписи ограничен. А значит, ограничен и период жизни драйвера. Наличие подписи у драйвера говорит о гарантии производителя ОС, что в течение всего срока подписи драйвер будет успешно работать. Соответственно в процессе поиска драйверов дополнительно стоит учитывать информацию о дате истечения срока цифровой подписи драйвера.
Указанный алгоритм учитывает эту специфику, сохраняя во временную таблицу результат установки драйвера и дату истечения срока подписи. Добавление фильтра по этим полям позволит увеличить вероятность успешной установки драйвера. Изменения в алгоритме показаны рис. 5.
— Исключим драйвера с результатом неудачной установки и
— те, чья дата цифровой подписи на момент поиска истекла.
— При этом надо учитывать, что под исключени по дате
— подпадают лишь те драйвера, которые имеют цифровую подпись,
WHERE InspectionFlag ≠ 1 -- факт неудачной установки OR Exp irat. ionF lag = 1 AND ExpirationDate & gt- GETDATE [))
Рис. 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. Т. Сортировка и поиск.

ПоказатьСвернуть
Заполнить форму текущей работой