Доступ к определенному адресу в памяти

Question

Почему мы можем получить доступ к определенному месту в нашей памяти в O (1)?

Answer 1

Быстрый ответ: Вы не можете!

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

Как только вы попадаете в ЦП, доступ к памяти сильно отличается. Существует несколько кешей, несколько ядер с кешами и, возможно, другие процессоры с кешами. Хотя доступ к основной памяти может быть выполнен напрямую, он медленный, поэтому у нас есть все эти кеши. Но теперь это означает, что внутри процессора память не доступна напрямую.

Когда процессору требуется доступ к памяти, он переходит в режим поиска. Он также имеет систему блокировки для правильного распределения памяти между кешами. Для доступа к разным адресам потребуется разное время, в зависимости от того, читаете ли вы или пишете, и где находится самый последний кэш этой памяти. Это то, что известно как NUMA (неравномерный доступ к памяти). Хотя сложность времени здесь, вероятно, ограничена константой (так что, возможно, / technicall O (1)), это, вероятно, не то, о чем большинство людей думают как постоянное время.

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

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

Answer 2

Память в современных компьютерных системах - это произвольный доступ, поэтому, если вы знаете адрес памяти, к которому вам нужен доступ, компьютер может напрямую перейти в эту ячейку памяти и выполнить чтение / запись в эту папку.

Это противоречит некоторым [старым] системам, таким как память на магнитной ленте, где лента должна была быть физически помещена в буфер, чтобы получить доступ к определенным областям, таким образом, более удаленные места требуют более длительного доступа.

Не уверен, что вы подразумеваете под выделением в O (1), поскольку выделение памяти обычно не равно O (1) при работе с типичной кучей на повседневных компьютерах.

Answer 3

Почему вы можете получить доступ в O (1)? Потому что доступ к памяти осуществляется по адресу. Если вы знаете адрес, к которому хотите получить доступ, то аппаратное обеспечение может напрямую перейти к нему и извлечь все, что есть в одной операции.

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

Хотя, если вы хотите принять чрезвычайно упрощенное представление о распределении как о «возврате адреса первого байта доступной памяти», то легко понять, почему это может быть операция O (1). Системе просто нужно вернуть адрес последнего выделенного байта + 1, поэтому, пока она отслеживает, какой последний выделенный байт находится после каждого выделения, и до тех пор, пока вы предполагаете неограниченное пространство памяти, вычисление следующего свободного адреса всегда O (1).

Answer 4

Это зависит от используемой вычислительной модели: в модели машины Тьюринга ни одна из операций не является O (1), в модели произвольного доступа доступ является O (1), что, как и в случае большинства современных аппаратное обеспечение с использованием оперативной памяти делает эту модель полезной. Я предполагаю, что вы используете модель, которая для простоты также допускает распределение O (1) в качестве близкого приближения к большинству современных реализаций на машине, которая находится под небольшой нагрузкой на использование памяти.