Содержание к диссертации
Общая характеристика работы 5
1. Анализ современных технологий и методов повышения надежности хранения информации на дисковых накопителях
1.1. Основные тенденции технологического и структурного развития систем хранения информации современных ПЭВМ
1.2. Требования к методам повышения надежности хранения информации магнитных дисков
1.3. Канал хранения и передачи информации на магнитных дисковых носителях ПЭВМ
1.3.1. Структурная схема СХИ на магнитных дисках. 16
1.3.2. Этап передачи: Магнитный диск (носитель информации) - считывающий механизм магнитных головок.
1.3.3. Этап передачи: Считывающий механизм магнитных головок - контроллер дискового накопителя.
1.3.4. Этап передачи: Контроллер дискового накопителя - контроллер интерфейса ввода-вывода
1.3.5. Этап передачи: контроллер интерфейса ввода-вывода - контроллер 32 DMA.
1.3.6. Этап передачи: Контроллер DMA - ОЗУ (программы-драйверы 33 дисковой системы).
1.3.7. Этап передачи: драйверы дисковой системы - драйверы файловой 34 системы
1.3.8. Этап передачи: драйверы файловой системы - потребитель информации (программа пользователя).
1.3.9. Результаты анализа структурной схемы СХИ на магнитных дисках. 36
1.4. Выводы по главе 39
2. Разработка и исследование многоуровневой модели канала хранения и передачи информации на дисковых накопителях
2.1. Разработка многоуровневой модели КХПИ. 40
2.2. Исследование и расчет статистики ошибок уровня дисковых операций канала хранения и передачи информации
2.3. Анализ ограничений информационной структуры уровней КХПИ. Рекомендации по выбору длины кодовой группы.
2.4. Выводы по главе 50
3. Методика оценки эффективности разрабатываемых алгоритмов кодирования и исправления ошибок итеративного кода СНХИ.
3.1. Выбор критериев эффективности алгоритмов кодирования и исправления ошибок итеративным кодом СНХИ.
3.2. Исследование особенностей информационных потоков для кодека итеративного кода СНХИ
3.2.1. Особенности операций записи информации на диск
3.2.2. Считывание информации с диска и исправление ошибок декодером СНХИ
3.3. Метод определения численных значений критериев вычислительной сложности алгоритмов кодирования и декодирования двухмерного итеративного кода СНХИ.
3.3.1. Метод оценки сложности алгоритмов с помощью сигнализирующих функций. Машины Тьюринга.
3.3.2. Оценка сложности алгоритмов с помощью аппарата теории сводимости.
3.3.3. Оценка сложности с помощью граф-схем алгоритмов.
3.3.4. Выбор метода оценки вычислительной сложности алгоритмов кодирования и исправления ошибок МНХИ
3.4. Выводы по главе 66
4. Разработка эффективных алгоритмов кодирования и декодирования двухмерного итеративного кода СНХИ.
4.1. Разработка эффективного алгоритма кодирования итеративного кода 68 СНХИ.
4.1.1. Базовый алгоритм кодирования итеративным кодом СНХИ. 68
4.1.2. Алгоритм кодирования итеративным кодом СНХИ, учитывающий возможность частичного обновления информационных разрядов.
4.1.3. Эффективный алгоритм кодирования итеративным кодом СНХИ 75
4.1.4. Реализация алгоритма кодирования итеративным кодом СНХИ, учитывающая разрядность процессора
4.1.5. Результаты разработки эффективного алгоритма кодирования двухмерным итеративным кодом СНХИ.
4.2 Разработка эффективного алгоритма декодировании (исправления ошибок) итеративного кода СНХИ
4.2.1. Стандартный алгоритм исправления ошибок итеративным кодом СНХИ.
4.2.2. Алгоритм исправления ошибок СНХИ, основанный на свойствах укороченного внешнего кода.
4.2.3. Реализация алгоритма исправления ошибок СНХИ, учитывающая разрядность процессора,
4.2.4. Вариант реализации алгоритма исправления ошибок СНХИ, использующий логическое скалярное значение синдрома.
4.2.5. Вариант реализации алгоритма исправления ошибок СНХИ, использующий остаточную информацию для ускорения декодирования
4.2.6. Результаты разработки эффективного алгоритма исправления ошибок двухмерного итеративного кода СНХИ
4.3. Выводы по главе. 91
5. Практическая реализация системы повышения надежности хранения и передачи информации на магнитных дисках.
5.1. Способ внедрения СНХИ в структуру операционной системы. 92
5.2. Способ размещения и декларирования проверочных разрядов на диске.
5.3. Разработка вспомогательных средств СНХИ. 97
5.4. Выбор средств разработки.
5.5. Разработка методики экспериментальной проверки предлагаемого метода повышения надежности магнитных дисков с помощью разрушающих испытаний
5.6. Варианты использования полученных теоретических и практических результатов для создания прочих типов ПО.
5.6.1. Создание отказоустойчивых систем с использованием СНХИ. 102
5.6.2. Системы комплексной защиты информации 105
5.7. Выводы. 110
Заключение 111
Библиография 116
Приложение 1 123
Приложение 2 130
Введение к работе
Актуальность проблемы
Увеличение объемов обрабатываемой информации, а также возросшие требования к надежности хранения и скорости обмена данными в вычислительных системах и комплексах ставят вопрос о необходимости расширения основных функций системы хранения информации (СХИ) такими пунктами, как гарантируемый доступ к данным, масштабируемость и гетерогенность накопителей, динамичность и распределенность структуры. Возможность гарантированного доступа к данным и управления ими является необходимым условием для функционирования всех информационных систем, включая автоматизированные производства и бизнес-процессы, в которых потеря ключевых данных, составляющих базис информационной системы, невосполнима. В процессе создания СХИ необходимо достичь оптимального соотношения производительности, доступности (надежного хранения и отказоустойчивого доступа) и совокупной стоимости системы.
Основным направлением совершенствования аппаратно-программных средств СХИ, используемых в традиционных сферах применения, включая АСУТП, является увеличение емкости накопителей и разработка высокоскоростных интерфейсов обмена данными. К 2005 году типичный накопитель на магнитных дисках имел плотность записи в пределах 50 Гигабит на квадратный дюйм [94,95,97], и этот показатель постоянно увеличивается.
Кроме того, в последнее время популярно применение дисков в качестве носителей информации в бытовых приборах: цифровых фото- и видеокамерах, карманных компьютерах (КПК, PDA), смартфонах и т.д., для которых миниатюрные форм-факторы также обуславливают высокую плотность записи и высшую точность сборки механических узлов.
Увеличение емкости накопителей на магнитных дисках происходит за счет значительного уменьшения площади информационных ячеек и увеличения плотности компоновки. По этой причине, появление дефектов при производстве современных дисковых накопителей и повышенная интенсивность отказов и сбоев в процессе их эксплуатации, происходит вследствие приближения к технологическим барьерам. Основным барьером является парамагнитный эффект [92,98,99,109,112], обусловленный нестабильностью намагниченности магнитных доменов. Кроме того, остаются типичные для магнитных носителей проблемы износа движущихся частей, точности позиционирования магнитных головок, присутствие микрочастиц пыли и влаги, вызывающие непрогнозируемое появление областей с нестабильными характеристиками на носителе. По некоторым оценкам, увеличение плотности записи на магнитные носители при сохранении существующих принципов повышения надежности чтения и записи данных серьезно замедлится, поскольку для сохранения допустимого значения вероятности сбоя в системах с низким соотношением сигнал/шум необходимо увеличивать исправляющую мощность помехоустойчивого кода (ЕСС), которым защищается каждый сектор диска [106,111,112].
Эффективные методы повышения надежности дисковых накопителей используются только в дорогостоящих специализированных СХИ, и имеют существенные ограничения по типу оборудования. Как правило, основное внимание в существующих методах защиты, например, в RAID [102,103], уделяется не повышению надежности хранения информации на отдельных накопителях массива, а обеспечению возможности восстановления данных с поврежденного диска, используя проверочные разряды, распределенные по другим накопителям и последующей горячей замене поврежденного диска.
Поэтому, актуальна разработка и исследование методов повышения надежности хранения информации (МНХИ) для тех случаев, когда применение дополнительной аппаратуры для дублирования не оправдано экономически либо невозможно. В данные рамки укладывается вся вычислительная и бытовая техника, для которой стоимость СХИ не должна превышать 10-30% от стоимости всей системы. Система повышения надежности хранения информации (СНХИ) должна эффективно интегрироваться в существующую иерархическую структуру канала хранения и передачи данных, и с максимальной полнотой использовать обнаруживающую способность существующих (конструкционно заложенных в накопитель) средств контроля целостности информации. Метод защиты должен быть инвариантен к типу диска. Следует заметить, что разрабатываемые МНХИ не противопоставляются существующим методам повышения надежности и отказоустойчивости, в частности, технологиям RAID и SAN/NAS, а могут служить дополнением к этим технологиям, создавая в совокупности многоуровневую систему надежного хранения информации.
Разработка метода защиты является комплексной проблемой, требующей решения ряда задач. В литературе отсутствуют адекватные модели канала хранения и передачи информации (КХПИ), описывающие работу магнитных дисков с точки зрения информационных потоков и анализа статистики ошибок, отсутствует методология выбора помехоустойчивого кода для разных уровней канала, рекомендации по реализации метода защиты для конкретного оборудования. Поэтому актуальной является также и задача анализа и систематизации многочисленных публикаций по данному вопросу.
Целью диссертационной работы является разработка универсального и экономичного метода повышения надежности хранения информации на магнитных дисках, использующего алгебраические коды для парирования дефектов носителя информации и реализующих его эффективных алгоритмов кодирования и исправления ошибок.
Для достижения поставленной цели необходимо решить следующие основные задачи диссертационной работы:
• Разработать и исследовать многоуровневую модель КХПИ, проанализировать статистику ошибок для каждого уровня канала и выделить уровень для эффективной реализации системы повышения надежности хранения информации (СНХИ), использующей алгебраические коды; • Исследовать и обосновать возможность и целесообразность применения двухмерных итеративных кодов для повышения надежности хранения информации на дисках различных типов;
• Разработать систему критериев для оценки эффективности алгоритмов кодирования и исправления ошибок в СНХИ двухмерными итеративными кодами в соответствии с особенностями потоков данных в канале хранения информации на дисковых накопителях;
• Разработать и исследовать метод определения значений критериев;
• Разработать и исследовать универсальный метод и эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов СНХИ в соответствии с выбранной системой критериев;
• Разработать рекомендации по выбору параметров двухмерных итеративных кодов и размещению проверочных разрядов для разных типов МД;
• Разработать рекомендации по программной реализации СНХИ, использующей предложенные алгоритмы кодирования и декодирования итеративных кодов для разных типов дисков.
Объектом исследования является канал хранения и передачи информации на магнитных дисках ЭВМ, в состав которого входят аппаратные и программные блоки, имеющие собственную статистику ошибок, виды дефектов и информационные структуры.
Предметом исследования являются методы повышения надежности хранения информации на магнитных дисках, алгоритмы кодирования и исправления ошибок данных в СНХИ с использованием итеративных кодов и методы анализа вычислительной сложности алгоритмов.
Основные положения, выносимые на защиту:
• Разработанная и исследованная четырехуровневая модель канала хранения информации на дисковых накопителях;
• Разработанный универсальный метод повышения надежности хранения информации на магнитных дисках, использующий кодирование информации двухмерными итеративными кодами;
• Разработанная система критериев и метод оценки вычислительной сложности алгоритмов кодирования и исправления ошибок двухмерными итеративными кодами;
• Разработанные эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов в КХПИ на магнитных дисках, адаптированные к специфике информационных потоков;
• Предложенные рекомендации по программной реализации СНХИ для разных типов дисков и операционных систем.
Научная новизна работы заключается в следующем:
• Предложен и теоретически обоснован универсальный метод повышения надежности хранения информации на основе двухмерных итеративных кодов на магнитных дисках различных видов.
• Разработана и исследована четырехуровневая модель КХПИ на МД.
• Предложена методика оценки эффективности алгоритмов кодирования и декодирования двухмерных итеративных кодов СНХИ, базирующаяся на оценке вычислительной сложности алгоритмов.
• Разработаны эффективные алгоритмы кодирования и декодирования двухмерных итеративных кодов для магнитных дисков.
Практическая ценность работы. 1. Разработанные методы и алгоритмы повышения надежности стандартных дисковых ВЗУ в составе ПЭВМ позволяют реализовать надежную, эффективную и экономичную систему хранения информации на рабочих станциях, ЭВМ общего назначения, интеллектуальных устройствах автоматики и бытовой техники; 2. Предлагаемые МНХИ могут быть применены для оптимизации структуры систем повышения надежности хранения информации и систем комплексной защиты информации, разрабатываемых производителями ПО на различных уровнях операционной системы. Дополнение механизма повышения достоверности данных разработанным программно-аппаратным кодеком итеративного кода СНХИ, позволяет распределить исправляющую способность по уровням КХПИ, снижая затраты ресурсов на исправление ошибок для верхних уровней и повышая надежность СХИ;
3. Построение отказоустойчивых систем по технологии RAID с использованием предложенных алгоритмов кодирования и исправления ошибок итеративными кодами, позволит повысить надежность хранения информации и увеличить быстродействие по сравнению с существующими системами
Публикации. Основные положения и результаты диссертации изложены в 12 статьях, в том числе имеется публикация в журнале из списка ВАК.
Структура и объем работы. Диссертация состоит из введения, 5 глав, заключения, библиографии, включающей 121 наименование, двух приложений, содержащих акты о внедрении результатов работы. Основное содержание работы составляет 122 стр. в том числе 13 таблиц, 23 рисунка.
