Фундаментальные алгоритмы и структуры данных в Delphi

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

Виртуальная память и страничная организация памяти

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

При запуске приложения под управлением современной 32-разрядной операционной системы ему для кода и данных предоставляется блок виртуальной памяти, размером 4 Гб. Очевидно, что операционная система не дает физически эти 4 Гб из оперативной памяти (ОЗУ); понятно, что далеко не каждый может себе позволить выделить лишние 4 Гб ОЗУ под каждое приложение. Фактически предоставляется пространство логических адресов, по которым, теоретически, может храниться до 4 Гб данных. Это и есть виртуальная память. На самом деле ее нет, но если мы все делаем правильно, операционная система может предоставить нам физические участки памяти, если возникнет такая необходимость.

Виртуальная память разбита на страницы. В системах Win32 с процессорами Pentium размер одной страницы составляет 4 Кб. Следовательно, Win32 разбивает блок памяти объемом 4 Гб на страницы по 4 Кб. При этом в каждой странице содержится небольшой объем служебной информации о самой странице. (память в операционной системе Linux работает примерно таким же образом.) Здесь содержатся данные о том, занята страница или нет. Занятая страница - это страница, в которой приложение хранит данные, будь то код или реальные данные. Если страница не занята, ее нет вообще. Любая попытка сослаться на нее вызовет ошибку доступа.

Далее, в служебную информацию входит ссылка на таблицу перевода страниц. В типовой системе с 256 Мб памяти (через несколько лет эта фраза, наверное, будет вызывать смех) доступно только 65536 физических страниц. Таблица трансляции страниц связывает отдельную виртуальную страницу памяти приложения с реальной страницей, доступной в ОЗУ. Таким образом, при попытке доступа приложения к определенному адресу операционная система выполняет трансляцию виртуального адреса в физический адрес ОЗУ.

Если в системе Win32 запущено несколько приложений, неизбежно будут возникать моменты, когда все физические страницы ОЗУ заняты, а одному из приложений требуется занять новую страницу. Но это невозможно, поскольку свободных страниц нет. В таком случае операционная система записывает физическую страницу на жесткий диск (этот процесс называется подкачкой или свопингом (swapping)) и отмечает в таблице трансляции, что страница была записана на диск, после чего физическая страница помечается как занятая приложением.

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

Все описанное выше в 32-разрядной операционной системе происходит постоянно. Физические страницы записываются на диск и считываются с диска. При этом изменяются таблицы трансляции страниц. В большинстве случаев простой пользователь ничего не замечает, за исключением одной ситуация. И эта ситуация называется пробуксовка (thrashing).

Пробуксовка