Особенности операций с внешней памятью

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: