Заранее извиняюсь за наивность этого вопроса. Мне 50 лет, и я впервые пытаюсь правильно понять компьютеры. Так что здесь идет.
Я пытался понять, как типы данных и переменные обрабатываются компилятором (в очень общем смысле, я знаю, что это много). Мне не хватает чего-то в моем понимании взаимосвязи между хранилищем в «стеке» и типами значений, а также хранилищем в «куче» и ссылочных типах (кавычки означают, что я понимаю, что эти термины являются абстракциями, а не слишком буквально понимать в таком упрощенном контексте, как я формулирую этот вопрос). В любом случае, моя упрощенная идея заключается в том, что такие типы, как булевы и целые числа, помещаются в «стек», потому что они могут, потому что они являются известными сущностями с точки зрения пространства хранения, и их область действия легко контролируется соответствующим образом.
Но что я не понимаю, так это то, как переменные в стеке затем считываются приложением - если я объявляю и присваиваю x
целое число, скажем x = 3
, и хранилище резервируется в стеке, а затем его значение 3
сохраняется там, а затем в ту же функцию, которую я объявляю и назначаю, y
как, скажем 4
, а затем, после чего я использую x
в другом выражении (скажем z = 5 + x
), как программа может читать x
, чтобы оценить, z
когда она нижеy
в стеке? Я явно что-то упускаю. Дело в том, что расположение в стеке зависит только от времени жизни / области видимости переменной и что весь стек фактически доступен для программы все время? Если это так, означает ли это, что существует какой-то другой индекс, который содержит адреса только переменных в стеке, чтобы можно было получать значения? Но потом я подумал, что весь смысл стека в том, что значения хранятся в том же месте, что и адрес переменной? На мой взгляд, кажется, что если есть другой индекс, то мы говорим о чем-то более похожем на кучу? Я явно очень смущен, и я просто надеюсь, что есть простой ответ на мой упрощенный вопрос.
Спасибо за чтение этого далеко.
источник
Ответы:
Хранение локальных переменных в стеке - это деталь реализации - в основном, оптимизация. Вы можете думать об этом таким образом. При входе в функцию место для всех локальных переменных выделяется где-то. После этого вы можете получить доступ ко всем переменным, поскольку вы как-то знаете их местоположение (это часть процесса распределения). При выходе из функции пространство освобождается.
Стек является одним из способов реализации этого процесса - вы можете думать о нем как о «быстрой куче», которая имеет ограниченный размер и поэтому подходит только для небольших переменных. В качестве дополнительной оптимизации все локальные переменные хранятся в одном блоке. Поскольку каждая локальная переменная имеет известный размер, вы знаете смещение каждой переменной в блоке, и именно так вы получаете к ней доступ. Это в отличие от переменных, размещенных в куче, чьи адреса сами хранятся в других переменных.
Вы можете думать, что стек очень похож на классическую структуру данных стека, с одним принципиальным отличием: вам разрешен доступ к элементам ниже вершины стека. Действительно, вы можете получить доступ к му элементу сверху. Вот как вы можете получить доступ ко всем вашим локальным переменным с помощью нажатия и выталкивания. Единственное нажатие делается при входе в функцию, и единственное нажатие при выходе из функции.k
Наконец, позвольте мне упомянуть, что на практике некоторые локальные переменные хранятся в регистрах. Это связано с тем, что доступ к регистрам быстрее, чем доступ к стеку. Это еще один способ реализации пространства для локальных переменных. Еще раз, мы точно знаем, где хранится переменная (на этот раз не через смещение, а через имя регистра), и этот тип хранения подходит только для небольших данных.
источник
Наличие
y
в стеке физически не препятствуетx
доступу, что, как вы указали, отличает компьютерные стеки от других стеков.Когда программа компилируется, позиции переменных в стеке также предопределены (в контексте функции). В вашем примере, если стек содержит
x
сy
«сверху» это, то программа знает заранее , чтоx
будет 1 пункт ниже верхней части стека в то время как внутри функции. Поскольку компьютерное оборудование может явно запрашивать 1 элемент ниже вершины стека, компьютер может получитьx
даже то, чтоy
также существует.Да. Когда вы выходите из функции, указатель стека возвращается к своей предыдущей позиции, эффективно стирая
x
иy
, но технически они будут существовать до тех пор, пока память не будет использована для чего-то другого. Кроме того, если ваша функция вызывает другую функцию,x
иy
она все еще будет там, и к ней можно получить доступ, преднамеренно зайдя слишком далеко в стек.источник
Чтобы представить конкретный пример того, как компилятор управляет стеком и как осуществляется доступ к значениям в стеке, мы можем взглянуть на визуальные изображения, а также код, сгенерированный
GCC
в среде Linux с целевой архитектурой i386.1. Стек кадров
Как вы знаете, стек - это место в адресном пространстве запущенного процесса, которое используется функциями или процедурами , в том смысле, что пространство выделяется в стеке для переменных, объявленных локально, а также для аргументов, передаваемых функции ( пространство для переменных, объявленных вне какой-либо функции (т. е. глобальных переменных), выделяется в другой области в виртуальной памяти). Пространство, выделенное для всех данных функции, ссылается на кадр стека . Вот визуальное описание нескольких кадров стека (из « Компьютерные системы: взгляд программиста» ):
2. Управление кадрами стека и переменное местоположение
Для того чтобы значения, записанные в стек внутри определенного стекового фрейма, управлялись компилятором и читались программой, должен существовать некоторый метод для вычисления позиций этих значений и извлечения их адреса памяти. Регистры в ЦП, называемые указателем стека, и базовый указатель помогают в этом.
Базовый указатель,
ebp
по соглашению, содержит адрес памяти дна, или основания, стека. Позиции всех значений в кадре стека могут быть рассчитаны с использованием адреса в базовом указателе в качестве ссылки. Это изображено на рисунке выше:%ebp + 4
адрес памяти хранится в базовом указателе плюс 4, например.3. Сгенерированный компилятором код
Давайте используем простой пример программы, написанной на C, чтобы увидеть, как это работает:
Давайте рассмотрим текст на ассемблере, созданный GCC, для этого исходного текста на языке C (для ясности я немного его очистил):
То , что мы наблюдаем , что переменные х, у и г расположены по адресам
%ebp - 12
,%ebp -8
и%ebp - 4
, соответственно. Другими словами, расположение переменных в кадре стекаmain()
рассчитывается с использованием адреса памяти, сохраненного в регистре ЦП%ebp
.4. Данные в памяти за указателем стека находятся вне области видимости
Стек - это область в виртуальной памяти, использование которой управляется компилятором. Компилятор генерирует код таким образом, что на значения вне указателя стека (значения вне вершины стека) никогда не ссылаются. Когда вызывается функция, положение указателя стека изменяется, чтобы создать пространство в стеке, которое, как говорится, не выходит за пределы.
Когда функции вызываются и возвращаются, указатель стека уменьшается и увеличивается. Данные, записанные в стек, не исчезают после того, как они выходят за пределы области видимости, но компилятор не генерирует инструкции, ссылающиеся на эти данные, поскольку у компилятора нет способа вычислить адреса этих данных с использованием
%ebp
или%esp
.5. Резюме
Код, который может быть непосредственно выполнен процессором, генерируется компилятором. Компилятор управляет стеком, кадрами стека для функций и регистрами ЦП. Одна из стратегий, используемая GCC для отслеживания расположения переменных в кадрах стека в коде, предназначенном для выполнения на архитектуре i386, заключается в использовании адреса памяти в базовом указателе кадра стека
%ebp
в качестве ссылки и записи значений переменных в расположения в кадрах стека по смещению по адресу в%ebp
.источник
Существует два специальных регистра: ESP (указатель стека) и EBP (базовый указатель). Когда процедура вызывается, первые две операции обычно
Первая операция сохраняет значение EBP в стеке, а вторая операция загружает значение указателя стека в базовый указатель (для доступа к локальным переменным). Таким образом, EBP указывает на то же место, что и ESP.
Ассемблер переводит имена переменных в смещения EBP. Например, если у вас есть две локальные переменные
x,y
, и у вас есть что-то вродетогда это может быть переведено в нечто вроде
Значения смещения 6 и 14 вычисляются во время компиляции.
Это примерно как это работает. Обратитесь к книге компилятора для деталей.
источник
Вы сбиты с толку, потому что к локальным переменным, хранящимся в стеке, нельзя обратиться с помощью правила доступа к стеку: First In Last Out или просто FILO .
Дело в том, что правило FILO применяется к последовательностям вызовов функций и стековым фреймам , а не к локальным переменным.
Что такое кадр стека?
Когда вы вводите функцию, ей выделяется некоторый объем памяти в стеке, который называется стековым фреймом. Локальные переменные функции хранятся в кадре стека. Вы можете представить, что размер стекового фрейма варьируется от функции к функции, поскольку каждая функция имеет разные числа и размеры локальных переменных.
То, как локальные переменные хранятся в кадре стека, не имеет ничего общего с FILO. (Даже порядок появления ваших локальных переменных в вашем исходном коде не гарантирует, что локальные переменные будут храниться в этом порядке.) Как вы правильно поняли в своем вопросе, «существует некоторый другой индекс, который содержит адреса только переменных в стеке, чтобы разрешить получение значений ". Адреса локальных переменных обычно рассчитываются с использованием базового адреса , такого как граничный адрес кадра стека, и значений смещения, характерных для каждой локальной переменной.
Итак, когда появляется это поведение FILO?
Что произойдет, если вы вызовете другую функцию? Функция вызываемого должна иметь свой собственный кадр стека, и именно этот кадр стека помещается в стек . То есть кадр стека функции вызывающей стороны размещается поверх стека кадра функции вызывающей стороны. И если эта вызываемая функция вызывает другую функцию, то ее кадр стека снова будет помещен на вершину стека.
Что произойдет, если функция вернется? Когда функция вызываемого абонента возвращается к функции вызывающего абонента, кадр стека функции вызываемого абонента извлекается из стека, освобождая место для будущего использования.
Итак, из вашего вопроса:
Вы совершенно правы здесь, потому что значения локальной переменной в кадре стека на самом деле не стираются при возврате функции. Значение просто остается там, хотя место в памяти, где оно хранится, не принадлежит ни одному из стековых фреймов функции. Значение стирается, когда какая-то другая функция получает свой кадр стека, который включает в себя местоположение, и записывает поверх некоторого другого значения в эту ячейку памяти.
Тогда что отличает стек от кучи?
Стек и куча одинаковы в том смысле, что оба они относятся к некоторому пространству в памяти. Поскольку мы можем получить доступ к любому месту в памяти по его адресу, вы можете получить доступ к любому месту в стеке или куче.
Разница заключается в обещании компьютерной системы о том, как она будет их использовать. Как вы сказали, куча для ссылочного типа. Поскольку значения в куче не имеют никакого отношения к какому-либо конкретному кадру стека, область действия значения не привязана ни к какой функции. Однако локальная переменная находится в области действия функции, и хотя вы можете получить доступ к любому значению локальной переменной, которое находится вне фрейма стека текущей функции, система попытается убедиться, что такого рода поведение не происходит, используя стеки кадров. Это дает нам некоторую иллюзию, что локальная переменная ограничена определенной функцией.
источник
Есть много способов реализовать локальные переменные с помощью языковой системы времени исполнения. Использование стека является распространенным эффективным решением, используемым во многих практических случаях.
Интуитивно понятно, что указатель стека
sp
хранится во время выполнения (по фиксированному адресу или в регистре - это действительно имеет значение). Предположим, что каждое «нажатие» увеличивает указатель стека.Во время компиляции компилятор определяет адрес каждой переменной как
sp - K
гдеK
константа, которая зависит только от области действия переменной (следовательно, может быть вычислена во время компиляции).Обратите внимание, что мы используем слово «стек» в широком смысле. Доступ к этому стеку осуществляется не только с помощью операций push / pop / top, но и с помощью
sp - K
.Например, рассмотрим этот псевдокод:
Когда процедура вызывается, аргументы
x,y
могут быть переданы в стек. Для простоты предположим, что условием является то, что вызывающий абонентx
сначала нажимаетy
.Тогда компилятор в точке (1) может найти
x
вsp - 2
иy
вsp - 1
.В точке (2) новая переменная вводится в область видимости. Компилятор генерирует код, который суммирует
x+y
, то есть то, на что указываетsp - 2
иsp - 1
, и помещает результат суммы в стек.В точке (3)
z
печатается. Компилятор знает, что это последняя переменная в области видимости, поэтому на нее указываетsp - 1
. Это больше не такy
, какsp
изменилось. Тем не менее, для печатиy
компилятор знает, что он может найти его в этой области вsp - 2
. Точно так жеx
сейчас находится наsp - 3
.В точке (4) мы выходим из прицела.
z
выскочил, иy
снова находится по адресуsp - 1
, иx
находится вsp - 2
.Когда мы вернемся, либо
f
либо вызывающая сторона выскакиваетx,y
из стека.Итак, вычисления
K
для компилятора - это подсчет, сколько переменных находится в области видимости, примерно. В реальном мире это на самом деле более сложно, поскольку не все переменные имеют одинаковый размер, поэтому вычислениеK
немного сложнее. Иногда в стеке также содержится адрес возвратаf
, поэтому его тожеK
нужно «пропустить». Но это технические детали.Обратите внимание, что в некоторых языках программирования вещи могут стать еще более сложными, если необходимо обрабатывать более сложные функции. Например, вложенные процедуры требуют очень тщательного анализа, поскольку
K
теперь приходится «пропускать» многие адреса возврата, особенно если вложенная процедура является рекурсивной. Закрывающие / лямбда-функции / анонимные функции также требуют некоторой осторожности для обработки «захваченных» переменных. Тем не менее, приведенный выше пример должен проиллюстрировать основную идею.источник
Самая простая идея - думать о переменных как об именах фиксированных адресов в памяти. Действительно, некоторые ассемблеры отображают машинный код таким образом («сохранить значение 5 в адресе
i
», гдеi
имя переменной).Некоторые из этих адресов являются «абсолютными», как глобальные переменные, некоторые являются «относительными», как локальные переменные. Переменные (то есть адреса) в функциях относительно некоторого места в «стеке», которое различно для каждого вызова функции; таким образом, одно и то же имя может ссылаться на разные реальные объекты, а циклические вызовы одной и той же функции являются независимыми вызовами, работающими с независимой памятью.
источник
Элементы данных, которые могут помещаться в стек, помещаются в стек - да! Это премиум пространство. Кроме того, после того, как мы поместили
x
в стек, а затемy
в стек, в идеале мы не можем получить доступ,x
покаy
он не будет. Нам нужно, чтобыy
получить доступ кx
. Вы правильно поняли.Стек не переменных, а
frames
То, где вы ошиблись, касается самого стека. В стеке это не элементы данных, которые непосредственно передаются. Скорее, в стек помещается то, что называется
stack-frame
. Этот стековый фрейм содержит элементы данных. Хотя вы не можете получить доступ к кадрам глубоко внутри стека, вы можете получить доступ к верхнему кадру и всем элементам данных, содержащимся в нем.Допустим, наши элементы данных объединены в два стековых фрейма
frame-x
иframe-y
. Мы толкали их один за другим. Теперь, пока вы находитесьframe-y
на вершинеframe-x
, вы не можете идеально получить доступ к любому элементу данных внутриframe-x
. Толькоframe-y
видно. НО, учитывая, чтоframe-y
это видно, вы можете получить доступ ко всем элементам данных, связанных в нем. Весь кадр виден, обнажая все элементы данных, содержащиеся в нем.Конец ответа. Больше (разглагольствовать) на этих кадрах
Во время компиляции составляется список всех функций в программе. Затем для каждой функции составляется список стековых элементов данных. Затем для каждой функции
stack-frame-template
производится. Этот шаблон представляет собой структуру данных, которая содержит все выбранные переменные, пространство для входных данных функции, выходных данных и т. Д. Теперь во время выполнения, всякий раз, когда вызывается функция, ее копияtemplate
помещается в стек вместе со всеми входными и промежуточными переменными. , Когда эта функция вызывает какую-то другую функцию, то свежая копия этой функцииstack-frame
помещается в стек. Теперь, пока эта функция работает, элементы данных этой функции сохраняются. Как только эта функция заканчивается, ее стековый фрейм выталкивается. В настоящее времяэтот стековый фрейм активен, и эта функция может получить доступ ко всем его переменным.Обратите внимание, что структура и состав стекового фрейма варьируется от языка программирования к языку программирования. Даже внутри языка могут быть тонкие различия в разных реализациях.
Спасибо за рассмотрение CS. Я сейчас программист, беру уроки игры на фортепиано :)
источник