CMI2011-A-08

Question

In programming languages like C, C++, Python $\dots$ the memory used by a program is typically separated into two parts, the stack and the heap. Consider the following statements:

1. A stack is efficient for managing nested function calls.
2. Stack space is limited while heap space is not.
3. The stack cannot be used for persistent data structures.

Then:

• A. $1$ and $2$ are true but $3$ is false.
• B. $1$ and $3$ are true but $2$ is false.
• C. $2$ and $3$ are true but $1$ is false.
• D. All three statements are true.

Comments

Persistent data structures are those data structures that always preserves the previous version of itself when it is modified. But since Stack data structure after computation gets popped, they are not persistent. Hence stack cannot be used for the persistent data structures.

Answer 1

Option (B) 1 and 3 are true but 2 is false. 

2 is FALSE because Size of heap and stack both are limited by the available main memory. Usually the OS also restricts the maximum memory a process can use. 

1. is TRUE because stack facilitates creation of memory for function calls and free them on function return - just a change of stack pointer is needed. 

3. is TRUE because the stack variables are cleared on function return. Usually persistent data structures refer to those which survive program exits but even for static variables which should live until program finishes, stack cannot be used. 

Comments

@Arjun sir, please verify this. 

---

But why 1 and 3 are true?

---

@arjun sir,

1) Example of 1 is recursion, stack is LIFO. Hence its efficient.

3) Example of 3 is static variable, Value is persistent in different function call. If i allocate memory in stack then it will deleted in after the function completion.

---

the concept of deletion doesn't work. Usually when the function returns, the stack pointer is moved to its original position when entering the function. For example

void solve(int x) {
  int y = x+x;
}

int main() {
  solve(5);
}

will be translated into (assuming an unoptimizing compiler)

solve:
  push ebp
  mov ebp, esp
  sub esp, 8
  mov eax, [ebp+8]
  mov [ebp-4], eax
  mov eax, [ebp-4]
  add eax, eax
  mov [ebp-8], eax
  add esp, 8
  leave
  ret

main:
  push ebp
  mov ebp, esp
  push 5
  call solve
  add esp, 4
  leave
  ret

So, when solve is executed, the stack looks like

+---------+     <-- main's frame
|   ebp   |
+---------+     <-- ebp points here
|    5    |
+---------+
|  ret0   |     <-- address of 'add esp, 4' in main
+---------+     <-- solve's frame
|   ebp   |     <-- saved ebp
+---------+     <-- ebp now points here
|    5    |     ;   argument copied into [ebp-4]
+---------+
|    10   |     ;   [ebp-8]
+---------+     <-- esp points here before returning from solve

After the control returns to main at add esp, 4 instruction, the stack looks like this

+---------+     <-- main's frame
|   ebp   |
+---------+     <-- ebp points here
|    5    |
+---------+     <-- esp points here
|  ret0   |
+---------+
|   ebp   |
+---------+
|    5    |
+---------+
|    10   |
+---------+

So, we can see that the value is not really 'deleted'. It may be overwritten if any function call uses those stack locations

Answer 2

In the case of recursion stack is the best storage allocation technique also in nested fuction sometimes it is also called as the recursion.

When we see activatio records of any process inside the memory we found there are severalparts

In activation records::

.exe file (machine code)

Static and global variable storage allocation spaces.

Heap (Increase upwards and inversely propotional to stack size and opposite to stack)

Stack(For recursion and bound to fresh allocation)

So statement two will be wrong.

Third statement is that Stack is not primitive data structure.

Answer 3

Ans = (B). Statement 2 is false. As both the stack and heap are finite. One can move the 'Program Break' (brk) to increase or decrease the heap memory (malloc shifts the brk)