Главная » Java, Структуры данных и алгоритмы » Стеки в виртуальной машине Java

0

После написания Java-программы компилятор переводит ее в байт-коды, которые можно обозначить как машинные команды четко описанной модели- т- виртуальной машины, Java, Определение виртуальной машины

Java является ключевым в. определении самого < языка Java j Благодаря тому, что’при компиляции Java-код преобразуется в байтгкоды виртуальной машины Java, а не в команды какого-либо конкретногр процессора, Java-nporpaMMa может далее выполняться на любом компьютере, включая рабочии станции UNIX, способном к эмуляции виртуальной машины Java. Следует отметить;, что стековая структура данных является основой определения виртуальной машины Java.

Java-стек методов

Стеки имеют важное значение для исполняющей среды Java-npo- грамм. Текущая Java-nporpaMMa (более точно — выполняющийся подпроцесс Java) имеет собственный стек, называемый Java-стек методов, или просто Java-стек, который используется для наблюдения за локальными переменными и прочей информацией, необходимой для выполнения методов по мере обращения к ним в ходе выполнения программы (см. рис. 4.3).

В частности, во время выполнения Java-программы виртуальная машина использует стек, элементами которого являются дескрипторы текущих (то есть выполняющихся) методов. Данные дескрипторы называют фреймами. Фрейм-обращение к некоторому методу «cool» содержит текущие значения локальных переменных и параметры метода cool, а также информацию о методе, который вызывает cool, и возвращаемом в этот метод значении.

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

Java-стек осуществляет передачу параметров методам. Следует отметить, что Java использует протокол передачи параметров «вызов по значению». Это означает, что текущим значением переменной (илй выражения) является то, что передается в качестве аргумента вызванному методу.

- Если переменная х относится к базовому типу данных, например, int или float, текущее значение х представляет собой число, связанное с х. Если такая переменная передается в метод, ее значение присваивается локальной переменной во фрейме вызванного метода (подобная операция присваивания значения показана на рис. 4.3). Обратите внимание, что при изменении вызываемым методом значения данной локальной переменной значение переменной в вызывающем методе не меняется.

Рис. 4.3. Пример Java-стека. Метод fool вызывается методом cool, который ранее был вызван методом main. Обратите внимание на значения счетчика программы, параметров и локальных переменных, записанных в стековых фреймах. После завершения метода fool возобновляется обращение к методу cool, начиная с команды 217, которая была получена путем увеличения на 1 значения счетчика программы, записанного в стековом фрейме

Что касается переменной х, которая вызывает объект, то ее текущим значением является адрес ячейки памяти объекта х (место хранения адреса в памяти будет рассмотрено в п. 4.2.3). Таким образом, когда объект х передается в качестве параметра в метод, в сущности передается адрес ячейки памяти. После того как этот адрес присваивается локальной переменной у в вызванном методе, последняя обращается к тому же объекту, что и х. Поэтому, если вызванный метод изменяет внутреннее состояние этого объекта, то одновременно изменяется внутреннее состояние объекта, к которому обращается х (один и тот же объект). Тем не менее, если э ходе программа У становится ссылкой другого объекта, х остается без изменений — переменная продолжает относиться к первоначальному объекту.

Таким образом, виртуальная машина Java использует Java-стек методов для выполнения обращений к методам и передачи параметров. Стеки методов не являются отличительной особенностью Java. Они используются в исполняющих системах большинства современных языков программирования, в том числе С и С++.

Рекурсия                                                                   \

Одно из преимуществ использования стека для обращения к методу состоит в возможности использования рекурсии, то есть метод может вызывать сам себя в виде подпрограммы. Например, рекурсию можно использовать для вычисления классического факториального многочлена п\= п(п – 1 )(п- 2)…1, как показано во фрагменте кода 4.7.

public static long factorial(long n) { if (n <= 1)

return 1; else

return n*factorial(n-1);

}

Фрагмент кода 4.7. Рекурсивный метод factorial’

Метод factorial рекурсивно вызывает сам себя для вычисления факториала п- 1. Когда рекурсивное обращение прекращается, метод возвращает (п – 1)!, которое затем умножается на п для вычисления п\. Далее рекурсивное обращение вызывается для вычисления факториала (п – 2) и так далее. Цепочка рекурсивных обращений и, следовательно, Java-ereKa продолжается до п, так как при обращении к factorial 1) метод немедленно возвращает 1 и рекурсивного обращения не происходит. Благодаря Java-стеку виртуальной машины метод factorial может одновременно существовать в нескольких активных фреймах (в зависимости от п). В каждом фрейме хранится значение параметра п, а также возвращаемое методом значение.

Данный пример демонстрирует такое важное свойство рекурсивного метода, как условие прекращения. Данное свойство в методе factorial выразим, записав нерекурсивные команды в случае п < 1. Рекурсивное обращение всегда выполняется при меньшем значении параметра (п – 1), чем заданный (п), таким образом на определенном этапе («у основания» рекурсии) выполняется нерекурсивная часть программы, которая возвращает 1. Проектирование рекурсивного метода должно гарантировать его прекращение на определенном этапе (например, определяя рекурсивные

обращения для «малых» значений, и нерекурсивные — к «наименьшим» значениям). Следует отметить, что бесконечней рекурсивный метод не будет выполняться вечно. На определенном этапе будет использована вся выделенная для Java-стека память, что приведет к возникновению ошибки нехватки памяти. Однако при правильном использовании рекурсии стек методов может реализовывать рекурсивные методы. Использование рекурсии может быть очень полезным, так как зачастую она позволяет создавать простые и эффективные программы для решения достаточно сложных задач.

Стек операндов

Существует еще один способ использования стеков виртуальной машиной Java. Стек операндов используется для вычисления арифметических выражений, например, ((а + b)*(c + d))/e. Простая операция с двумя операндами, например, а + Ь, вычисляется следующим образом: а добавляется в стек операндов, затем b добавляется в этот стек, после чего вызывается команда, которая извлекает эти два значения из стека операндов, выполняет бинарную операцию и добавляет результат тоже в стек операндов. Подобным образом для добавления и извлечения элементов из памяти в стеке операндов используются методы pop и push.

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

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии