How is stack and heap are assigned to each processes

heapmemoryoperating systemsrecursionstack

How multiples processes are stored in the main memory , i understand every process will be divided into the equal size pages and will be stored in the frames of main memory. if whole main memory is divided into the pages then how are stack area, heap area, code section given to the process?

my understanding is there is common stack area and heap area.

next question is :- when a method executes it is allocated in the stack area and a activation record is pushed into the stack.

I am also considering here contex switching.
eg: 

---------------
| process: p1 |
---------------
fun(int a)
{
if (a=0)
return 0;

fun(a--);
}

main()
{
 fun(5);
}

---------------
| process: p2 |
---------------

NoFun(int a)
{
if (a=0);
return 0;

NoFun(a--);
}
main()
{
 fun(3)
}

now processes p1 and p2 will be loaded into the main memory , now assume p1 started its execution so its first method main will be called and its activation records will be pushed into the stack now main calls fun() method and it started executing and after sometime this process gets preempted and context switch takes place (stack pointer of p1 will save the address of p1.fun(3) ) . so calls will look something like this.:-

p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3)

so main is in the bottom of stack and fun(3) is in the top of the stack , now p2 gets chance for the execution so, main method of process p2 will get executed and will be pushed on the top of the stack i.e on the top of activation record of fun(3). so now it will look like this

p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3) -> p2.main()

its time for p2 to get preempted, P1 again gets CPU and starts execution now p1 resumes back its context and go to the address of stack pointer and starts execution of remaining code.

so after execution of p1 , stack will look like this:-

p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3) -> p2.main() ->p1.fun(2) ->fun(1)-> fun(0)

now p1 will start popping records:-

p1.fun(0) is popped out .
p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3) -> p2.main() ->p1.fun(2) ->fun(1)

p1.fun(1) is popped out .
p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3) -> p2.main() ->p1.fun(2)

p1.fun(2) is popped out .
p1.main() -> p1.fun(5) -> p1.fun(4) -> p1.fun(3) -> p2.main()

now p1 is in the CPU and it wont be able to execute it beacause stack top is of process 2.

I know my understanding is wrong, please correct me and give some refrences.

Best Answer

What you're fundamentally missing is that P1 and P2 each get their own stack. So the resulting pictures are much cleaner than you are imagining.

You have two stacks, one for P1 and one for P2. They are completely separated. All activation frames for P1 go on P1's stack, and all activation frames for P2 go on P2's stack. They operate completely independently, and on a multi-cpu processor, can even operate concurrently.

A single processor (whether on a multi-cpu processor or not) can alternate between P1 and P2. When a processor stops running P1 and starts running P2, this one form of the context switch. The state of P1 is saved, and the state P2 is loaded. This save/restore operation will effectively switch stacks by updating the CPU registers that refer to the stack.

Other terms you might want to differentiate:

A process usually reflects an address space. An address space is like memory as an array. It gets more complicated than this because of memory that is shared between processes (each other) and the kernel, and various protection mechanisms; however, conceptually, you can think of an address space as a big array of bytes starting at index 0. Each process is given its own address space, which allows each process to have its own stack and heap independent of the other processes, without worry of conflicting indexes (i.e. of conflicting addresses).

Now, a single process can also run multiple threads. Your thought exercise involving P1 and P2 could be also be replicated using T1 and T2, two threads in one process. With multiple threads in one process, the threads are all sharing the same address space, though T1 and T2 still each have their own stack. T1, the process's first thread, will start at main, but T2 will start wherever directed to do so (by T1 firing up a new thread, T2, so T2 is unlikely to start at main). Otherwise the scenarios are very similar between P1, P2 and T1, T2.

Note that a context switch between P1 and P2 involves also changing the address space (more cpu registers that here refer to the address space), whereas between T1 and T2 only the stack state needs to be switched and not the address space. T1 and T2 will also share a common heap (though may each be directed toward different areas of that heap for their allocations) whereas P1 and P2 will have independent heaps (though they still may establish some shared memory).

Address spaces are supported by cpu hardware feature called virtual memory. This enables separate address spaces, and protects one process from potentially erratic behaviors of another, in that one process is prevented from touching the memory of another (modulo debuggers, etc..).

You might also find interesting: http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/

Fundamentally, the cpu has registers that refer to the context of its current execution state. These registers in some way define, among other things:

  • the address space (out of which the stack(s) and heap are allocated)
  • the stack (and thus the existing activation frames, and where new ones go)
  • the instruction pointer, which identifies the current instruction stream

A context switch saves and restores these things. By saving the current context, that thread (of a process) context is suspended for later resumption. By restoring some other context, that other thread (of a process) is resumed.

Note that not all of the context needs to be saved every time, for example, the address space is probably already saved for the process, so it just needs to be reloaded on resumption instead of both save and reloaded. However, the stack and instruction pointer move during execution, of course, so these do need to be saved so they can be restored later.

When multiple CPUs are present and concurrently executing, they each have their own full notion of context, of referring to address space, activation stack and instruction stream using their own registers.

It is then up to the operating system and managing run-times to properly allocate new stack within a process when a new thread is requested, or to allocate a new address space when a new process is requested.

Related Topic