STACK AREA IN MAIN MEMORY

Computer architecture topics
Post Reply
User avatar
Face
Major
Major
Posts: 727
Joined: Thu Feb 18, 2010 5:06 pm
Location: SRI LANKA.KANDY.

STACK AREA IN MAIN MEMORY

Post by Face » Tue Apr 06, 2010 5:02 pm

What is stack area in Main memory..??
For what it use for...?

I have heard some little about facts about that & about some stack operator ex-PUSH,POP...
But I don't have a clear idea about that.please give me some learning materials to study about that.(web links..or pdf)
if any one can explain it for me it is really helpful because In here you post your ideas in simple English & in clear basic core of the questions..

(that's why I love EXPERTCORE & got addict in reading your site. ;) )
User avatar
Neo
Site Admin
Site Admin
Posts: 2642
Joined: Wed Jul 15, 2009 2:07 am
Location: Colombo

Re: STACK AREA IN MAIN MEMORY

Post by Neo » Tue Apr 06, 2010 7:38 pm

First, ROBOT.LK is not only ours, it is yours too. We are a small community and we share knowledge.

In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds to the top of the list, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the list, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty list.

A stack is a restricted data structure, because only a small number of operations are performed on it. The nature of the pop and push operations also means that stack elements have a natural order. Elements are removed from the stack in the reverse order to the order of their addition: therefore, the lower elements are typically those that have been in the list the longest.
stack.png
stack.png (2.1 KiB) Viewed 8213 times
Stacks are used everywhere in computers from hardware-OS to programming.

Software stacks
Examples of stack usage in software are as below.
  • In compilers and linkers, stacks are used in almost all stages ( lexical analysis, preprocessing, parsing, semantic analysis, code generation, and code optimization).
  • In Operating Systems, stacks are used to handle several tasks including register backup/restore in context switching.
Hardware stacks
  • Stack in main memory
    Most CPUs have registers that can be used as stack pointers. Processor families like the x86, Z80, 6502, and many others have special instructions that implicitly use a dedicated (hardware) stack pointer to conserve opcode space. Some processors, like the PDP-11 and the 68000, also have special addressing modes for implementation of stacks, typically with a semi-dedicated stack pointer as well (such as A7 in the 68000). However, in most processors, several different registers may be used as additional stack pointers as needed (whether updated via addressing modes or via add/sub instructions).
    [edit]
  • Stack in registers or dedicated memory
    The x87 floating point architecture is an example of a set of registers organised as a stack where direct access to individual registers (relative the current top) is also possible. As with stack-based machines in general, having the top-of-stack as an implicit argument allows for a small machine code footprint with a good usage of bus bandwidth and code caches, but it also prevents some types of optimizations possible on processors permitting random access to the register file for all (two or three) operands. A stack structure also makes superscalar implementations with register renaming (for speculative execution) somewhat more complex to implement, although it is still feasible, as exemplified by modern x87 implementations.
Example:
I'll tell you a scenario where you can understand the use of stack data structure in computer software and hardware.

In multi-tasking, the Kernal decide to switch between processes (applications). This is called context switching. At a time where we switch from process1 to process2, we need to do following steps.
  1. Backup all CPU registers of process1
  2. Restore previous state (registers) of process2
  3. Give control to process2
Each process (application), resides in memory as block (called PCB - Process control block) and we can identify 3 different parts. Code, Data and Stack. Code contains the source code that needs to be executed, data to store variables and constants and stack part is used to store CPU registers that need backup[1]/restore[2] at a time of context switching.

Not only in process to process context switching, we also use the same procedure when we call a function. Say your program has a function called func1. When you call it from the main routine, we first backup the registers that belongs to main routine and restore the ones from func1 and give the control to func1.
When func1 execution is completed, then we backup the registers of func1, restore the ones from main routine and give control back to main routine.

These are just a few examples of many uses of Stack data structure.

Is it clear now?
User avatar
Face
Major
Major
Posts: 727
Joined: Thu Feb 18, 2010 5:06 pm
Location: SRI LANKA.KANDY.

Re: STACK AREA IN MAIN MEMORY

Post by Face » Tue Apr 06, 2010 7:51 pm

can you explain these things in your post BRO please..because i don't understand these few statements.
In computer science, a stack is a last in, first out (LIFO)
that stack elements have a natural order
Elements are removed from the stack in the reverse order
stack pointers
???????

YEP....EXPERTCORE IS OURS IT MEANS ALL OF US...
User avatar
Neo
Site Admin
Site Admin
Posts: 2642
Joined: Wed Jul 15, 2009 2:07 am
Location: Colombo

Re: STACK AREA IN MAIN MEMORY

Post by Neo » Tue Apr 06, 2010 8:20 pm

In computer science, a stack is a last in, first out (LIFO)
This is how the STACK data structure is defined in computer science.

Say you have elements A, B, C... E and you are going to put them in to a an object with one side closed in order of A, B, C, D and finally E. So you can see A is on the bottom and E is on top. You can't take A out. If you need to get A out, first you need to take out E, then D, after that E and so on until you reach 'A'. In other words, you can only access the top most element (or last input). That's why we call the Stack a Last In, First out style (LIFO) data structure.
1.gif
1.gif (1.96 KiB) Viewed 8207 times
that stack elements have a natural order
Explanation is also below that if you read carefully. Here, the access to last input is only possible in a stack. When we put an element we call that operation "PUSH". When we need to take one out we call "POP. Let's get an example from nature.
PUSH and POP are the only two operations permit to call on a Stack.

Say there are few heavy iron disks (you are only able to hold one at a time) and you store all disks on top of the other. Now, think whether you can take a middle disk? You can't because, you will have to lift few disks at ones. This is not possible as you can only lift one at a time. So the procedure is, you take the top one out, then the other one and do the operation until you reach the middle disk you want. Is that right. This is called the natural order in stack (a practical reality that you can find in the nature).
Elements are removed from the stack in the reverse order
Again consider my heavy iron disk example. You can't lift more than that, so you have to take each one from top until you reach the element you want.

Say the iron disks are numbered from A to E.
You call following operations.
PUSH ( A )
PUSH ( B )
PUSH ( C )
PUSH ( D )
PUSH ( E )

You get the elements as in the following picture.
1.gif
1.gif (1.96 KiB) Viewed 8207 times
Now you need to take C out. You need to call as below.

POP (this will give you E)
POP (this will give you D)
POP (this will give you C.. Here comes what you wanted)

stack pointers
On the above image, see there is an arrow with label "Top" that is pointing to the top most element. In a stack, we always point at the top most element as all operations are restricted to that. This pointer is called the Stack pointer.
In that image, stack pointer is pointing to element 'E'. However if you call POP, then then E will be poped out and the stack pointer will be pointed to element 'D'.

Read more on "Stacks" which is taught as the first lesson under Data Structures & Algorithms.
User avatar
Face
Major
Major
Posts: 727
Joined: Thu Feb 18, 2010 5:06 pm
Location: SRI LANKA.KANDY.

Re: STACK AREA IN MAIN MEMORY

Post by Face » Tue Apr 06, 2010 8:25 pm

thanks BRO..

got CRISTAL CLEAR picture..!!!!!
Post Reply

Return to “Computer Architecture”