null

О стеке и куче в контексте мира Java

Повествую про то, как разобраться в 'структуре памяти' Java и иметь представление что такое стек и куча, для чего они нужны и т.п. Многие слышали о том, что есть некий стек в котором живут примитивные типы и работает он по LIFO, а есть ещё какая-то куча и в ней находятся объекты. Такое понимание этих понятий является очень поверхностным и неправильным и сейчас попытаемся расширить их.

Для начала рассмотрим стек. Короткая цитата с википедии:

 

Стек - абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO.

Хорошим примером стека можно назвать стопку тарелок. К ней будет применимо две операции, положить новую тарелку наверх стопки, либо же взять верхнюю тарелку, собственно этими двумя операциями и организуется принцип LIFO (Last In - First Out).

Картинки по запросу стек программирование

 

Сказанное выше, безусловно, полезно и необходимо знать, но лишь описывает стек как структуру данных, и никак не говорит о том, зачем он нужен в контексте мира Java. Чтобы ответить на этот вопрос, нужно помнить, что байт-код, исполняется (читай интерпретируется) на JVM, которая де-факто также является процессором, только 'виртуальным', исполняющим команды. Конечно, внутри виртуальная машина построенно далеко не точно также как компьютеры работающие на принципах Фон Неймана. Однако и там, есть общие черты. Поэтому стек мы будем рассматривать на примере простенькой ЭВМ.

 

Выше крупноблочно структура этой базовой ЭВМ, которую мы будем рассматривать. Имеется процессор, с двумя блоками: АЛУ - арифметико-логическое устройство ( непосредственно производит операции над данными) и УУ - управляющее устройство (управляет потоком исполнения команд). Основное что нужно понять из этой схемы, что существует память, которая разбита на ячейки фиксированного размера, каждая из которых имеет свой адрес. В любой ячейке могут храниться, как команды, являющиеся частью программы, так и данные. Первое от второго никак не отличимо. Поэтому содержимое ячейки может одновременно являться как кодом, так и данными в зависимости от интерпретации.

Теперь взглянем на то, что из себя представляет выполняющаяся программа. 

 

В схеме выше были добавлены, СК - счетик команд, А - аккумулятор и РК - регистр команд. С такими кмпонентами можно и кашу сварить программу исполнить. Процесс выполнения программы будет заключаться в установке в счётчик команд, адреса с которого будет начинаться код, выполняемой программы. После запуска процессор начинает читать из памяти последовательно, начиная с адреса указанного в СК, и пытаться с помощью устройства управления разобрать считанную команду и произвести манипуляции с аккумулятором с помощью АЛУ. Красная линия показывает, так 'называемый поток исполнения', т.е. то, в каком порядке исполняются команды. Если же добавить в процессор ещё пару ячеек встроенной памяти и назвать их регистром данных (РД), регистром адреса (РА), тогда появится возможность работать с памятью ещё и как с набором данных, а не команд. 

 

Следовательно, команды и данные никак не отличаются с точки зрения аппаратуры, разделение на эти понятия создаёт тот кто пишет программу, и разбивает программу на необходимые для её работы логические блоки: команд и данных.

 

Окей. А как это вообще связано со стеком?

Чтобы понять, зачем нужен стек, надо по-хорошему осознать, как на таком машинном уровне организуются подпрограммы/процедуры. Описанное выше позволяет писать линейные программы, просто набор последовательных инструкций. Например что-нибудь такое:

b = a + 3;
c = a + b * 2;
c++;

Если добавить в систему команд процессора, команды, которые позволяют изменить значение СК, а ещё лучше сразу сделать команды, которые меняют или не меняют его в зависимости от какого-нибудь условия, то мы получим возможность реализовать ветвления, циклы и даже подпрограммы в нашей ЭВМ.

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

 

 

Здесь появляется проблема. Мы просто так тратим память, когда можно было написать эти X команд один раз и пользоваться ими. И в этот момент, мы изобрели то, что уже давным-давно существует в высокоуровневых языках программирования и называется функциями/процедурами/подпрограммами.

Окей, все знают что такое функции/процедуры, но как сделать такую, если мы пишем на ассемблере?

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

 

 

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

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

И здесь на помощь нам приходит стек!

Похожее изображение

 

 

Идея на самом деле простая. Давайте просто в общей памяти или в какой-нибудь отдельной выделим кусок и назовём его стек. Через него будем передавать адреса возврата, аргументы для подпрограмм. В систему команд добавим, команды push и pop. А команда JSR/CALL, будет писать не в первую ячейку подпрограммы, а делать push адреса возврата на стек. Для того, чтобы возвращаться из подпрограмм введём команду RET, которая будет брать с вершины стека значение и менять на него значение СК.

 

В коде выше основная программа вызывает подпрограмму A, а в ней вызывается подпрограмма B. Во время выполнения подпрограммы B, стек будет иметь следующий вид:

 

Как можно заметить, при каждом вызове процедуры в стек записывается адрес возврата. Следовательно, даже если подпрограмма будет рекурсивная, то адрес возврата не перезапишется, а положится новый на стек, а старый останется и будет ждать своего звездного часа, пока не выполнится команда RET. Также в стек кладут и аргументы функций.

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

 

Хорошо, теперь должно быть понятно зачем нужен стек, какие проблемы он решает и что в нём хранится. 

Теперь пару слов о куче. Вернёмся в мир Java и рассмотрим следующую функцию:

vod doSomething(int a , int b) {
  int age = a + b;
  String name = "Vasya";
  Cat cat = new Cat(name, age);
}

 

Как известно в куче хранятся объекты. Но что это значит? Куда они в момент создания объекта попадут неизвестно, а в командах как можно догадаться адреса с которыми нужно работать должны быть заданы заранее, в момент компиляции. Следовательно, даже если объекты хранятся в той самой магической куче, это не отменяет того, что где-то (на самом деле в стеке) должен храниться адрес этого самого объекта.

 

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

Надеюсь, что после всего вышесказанного стало немного понятнее, что есть стек, что есть куча, что в них хранится и зачем они нужны. Хочу также обратить внимание, что внутри JVM организация стека отличается от описанного выше, но функции он несёт такие же.

На этом, пожалуй, откланяюсь.