Что такое стеки в DRAM (что происходит во время рекурсии)?

Question

Я просто хочу лучше понять, что такое стек в адресном пространстве (т. Е. У вас есть код / ​​текст, куча, данные и стек)

В основном я понимаю, что стек содержитлокальные переменные, но в чем же разница между тем, что содержат данные, и тем, что содержит стек?также не переменные данных?

Если у программы есть рекурсивный вызов функции a (), означает ли это, что для каждого уровня рекурсии существует новый стек?

Answer 1

Стек обычно отличается от данных только тем, как он используется и управляется.В то время как сами нелокальные переменные обычно имеют известную конкретную ячейку памяти, вещи в стеке находятся относительно регистра (указатель стека или базовый указатель или что-то подобное).

Стек обычно содержит локальные переменные, переданные параметрыи управляющая информация для управления самим стеком.

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

Имейте в виду, что все это, конечно, зависит от архитектуры.Мое описание выше является распространенным случаем, но есть архитектуры, в которых стеки выполняются по-разному, такие как SPARC, System z и RCA1802.

Более подробную информацию можно найти здесь (как работают кадры)и здесь (странные стеки).

Answer 2

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

Чтобы понять стек, вы должны сначала понять, что такое стек.Это похоже на стопку лотков, свойства, которые делают ее стопкой:

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

Акт сохранения чего-либо в стеке называется PUSH, а удаление - POP.Скажем, я делаю следующее для пустого стека:

PUSH A
PUSH B
PUSH C

Тогда в стеке будет

C - Top
B
A

Теперь, если я выполню POP (обратите внимание, что здесь нет операнда), он будетвозвратите C, и стек будет содержать

B -- top of stack
A

Таким образом, стек в процессорах является лишь аппаратной реализацией вышеуказанного алгоритма.

Регистр содержит адрес вершины стека, называемый точка стека ISA (архитектура набора инструкций) предоставляет инструкции PUSH и POP для доступа к переменным стека, как я показал выше.

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

foo(){
    int a;   
    int b;    // both registers containing a and b are PUSHed here on the stack 
    c = bar(); // pop the stack to get value of c 
    print c
}

bar(){
   int z; // local variables pushed on top of the stack
   z = ... 
   return z; // pop all local variables of bar(), then push z on the stack 
}

Надеюсь, вышесказанное поможет.

Answer 3

Следующая программа должна помочь вам понять, что происходит. Вы увидите примеры указателей text, bss, heap и stack. Текст - это обычно исполняемый код, bss - статические / глобальные переменные, куча - динамически выделяемая память, стек содержит локальные переменные.

#include <stdlib.h>
#include <stdio.h>

#define TESTS 10
int numfeed = 0;
int numdead = 0;

recurse(int x)
{
  u_int pattern=0xfeedface;
  u_int *otherpattern = malloc(4);
  *otherpattern = 0xdeadbeef;

  printf("Feedface %d is at %p\n",x,&pattern);
  printf("deadbeef %d is at %p\n",x,otherpattern);

  if (--x == 0)
  {
    int *off;

    for(off = &pattern;numfeed<TESTS;off++)
    {
      if (*off == 0xfeedface)
        printf("Found feedface #%d at %p\n", ++numfeed, off);
      if (*off == 0xdeadbeef)
        printf("Found deadbeef #%d at %p -- WHAT?!?!!?!?\n", ++numdead, off);
    }
  }
  else
  {
    recurse(x);
  }
  // Not freeing otherpattern intentionally.
}


main()
{
  u_int *otherpattern = malloc(4);
  *otherpattern = 0xdeadbeef;
  int *off;

  recurse(TESTS);

  for(off = otherpattern+1;numdead<TESTS;off++)
  {
    if (*off == 0xfeedface)
      printf("Found feedface #%d at %p -- WHAT?!?!!!?!?\n", ++numfeed, off);
    if (*off == 0xdeadbeef)
      printf("Found deadbeef #%d at %p\n", 1+TESTS-(++numdead), off);
  }

  printf("numfeed is at %p\n",&numfeed);
  printf("recurse is at %p\n",&recurse);
}