Исправление ошибок

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

К счастью, математики и инженеры разработали так называемые коды с исправ­лением ошибок (Error Correction Codes — ЕСС). Во всех современных контроллерах жестких дисков есть специальные схемы для формирования и использования этих ЕСС-чисел. Большую часть времени пользователь даже не знает о появлении диско­вых ошибок; контроллер диска благодаря ЕСС просто автоматически исправляет ошибки.

"Садовая" модель ЕСС. Для понимания некоего "волшебства" ЕСС требуется не­много терпения. До обсуждения работы ЕСС в контроллере жесткого диска полезно обратиться к более простой для понимания модели. Предположим, что вы хотите защищать 16 бит информации. Выстроим эти единицы и нули, как деревья в саду, в четыре строки и четыре столбца. Для каждой строки и столбца при наличии в них четного числа единиц добавим дополнительный единичный бит; при наличии нечет­ного числа единиц в строке или столбце добавим нулевой бит; наконец, введем пос­ледний бит в месте пересечения дополнительных строки и столбца, поместив в него 1 или 0 так, чтобы сделать нечетным число единиц в нижней строке (рис. 2.9).

При такой организации каждые строка и столбец имеют нечетный паритет. Если искажается любой бит, его можно найти, потому что содержащие его строка и стол­бец больше не имеют нечетного паритета. Можно не только обнаружить ошибочный бит, но и исправить его!

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

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

"Садовая" модель обладает такими замечательными свойствами, но только для однобитных ошибок; поэтому она хорошо показывает сущность ЕСС. Отметим, что для защиты от однобитных ошибок 16 бит данных потребовались дополнительные 9 бит. Эффективность защиты значительно возрастает, если выбрать большее число защищаемых битов.

Предположим, что необходимо защитить от ошибок один сектор информации на жестком диске. Сектор содержит 512 байт или 4096 бит. Такой размер означает, что можно создать "сад", имеющий 64 строки и 64 столбца. Для завершения "сада" по­требуется 129 бит, обеспечивающих защиту от всех однобитных ошибок.

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

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

Реальный ЕСС. Фирмы-производители включают схемы ЕСС в контроллеры же­стких дисков по-разному. Они считаются собственностью фирм, поэтому практичес­ки подробно разобраться в них и понять отличия друг от друга невозможно. По-ви­димому, это одна из причин того, что новый контроллер часто не может считать дан­ные с жесткого диска форматированного другим контроллером. Из-за записи другим способом секторы в накопителе выглядят странными для второго контроллера и он считает жесткий диск неформатированным.

Обычно схемы ЕСС контроллера могут обнаружить и исправить любой набор ошибок во всем секторе из 512 байт (4096 бит) данных, если все ошибки содержатся в одном пакете, длина которого не превышает некоторого конкретного значения. В стандарте фирмы IBM для первого MFM-накопителя в IBM PC/XT исправление га­рантировалось, если длина пакета не превышала II бит. Для этого в конце каждого сектора приходилось хранить всего 4 байта ЕСС. Это же количество байт ЕСС обес­печивает высокую вероятность обнаружения более длинного пакета или группы паке­тов, но такие ошибки исправить нельзя.

Имеется несколько способов борьбы с такими ошибками (по, к сожалению, ни один из них пока не по­лучил распространения в накопителях на жестких дисках для персональных компь­ютеров).

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

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

Что делает DOS при действии ЕСС. Когда контроллер диска пытается считать сектор данных с жесткого диска, могут произойти три события: вычисленный ЕСС соответствует ЕСС на диске; контроллер обнаруживает, что данные не согласуются с ЕСС, но ЕСС определяет, какими должны быть данные (это исправимая ошибка считывания); ошибка в данных столь велика, что ЕСС недостаточно для определе­ния искаженных битов (это неисправимая ошибка).

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

на материнской плате компьютера, а, возможно, от версии DOS и выполняемой при­кладной программы.

После этого контроллер диска посылает данные в компьютер с такими соответ­ствующими сообщениями:

1. "Вот данные. Они считаны без ошибок"

2. "Вот данные. Я не смог считать их, но определил, какими они должны быть"

3. "Вот то, что я считал, но я уверен, что это не то, что требуется"

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

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

Когда DOS получает одно из трех приведенных ранее сообщений, она предпри­нимает одно из двух действий. В случае сообщений или 2 (успешное считывание или ошибка при считывании, которая почти наверняка исправлена ЕСС) DOS про­сто воспринимает данные и без комментариев передает их прикладной программе. Только если контроллер диска не может считать или восстановить данные, DOS со­общает вам (или вашей прикладной программе) о возникшей проблеме. Однако к этому моменту проблема настолько серьезна, что часть данных потеряна.

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

Дата добавления: 2014-01-20