ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ

Ξεκίνησε από landreou, 12 Φεβ 2013, 08:30:58 ΠΜ

« προηγούμενο - επόμενο »

landreou

Γεια στους φίλους του ΣτΠ.
Το σχολικό βιβλίο αναφέρει

Η έννοια της στοίβας είναι πολύ χρήσιμη στο ίδιο το λογισμικό των γλωσσών προγραμματισμού. Όταν μία διαδικασία ή συνάρτηση καλείται από το κύριο πρόγραμμα, τότε η αμέσως επόμενη διεύθυνση του κύριου προγράμματος, που ονομάζεται διεύθυνση επιστροφής (return address), αποθηκεύεται από το μεταφραστή σε μία στοίβα που ονομάζεται στοίβα χρόνου εκτέλεσης (execution time stack). Μετά την εκτέλεση της διαδικασίας ή της συνάρτησης η διεύθυνση επιστροφής απωθείται από τη στοίβα και έτσι ο έλεγχος του προγράμματος μεταφέρεται και πάλι στο κύριο πρόγραμμα. Η τεχνική αυτή εφαρμόζεται και γενικότερα, δηλαδή οποτεδήποτε μία διαδικασία ή συνάρτηση καλεί μία διαδικασία ή συνάρτηση. Για παράδειγμα, έστω ότι μία διαδικασία a καλεί τη διαδικασία b, που με τη σειρά της καλεί τη διαδικασία c κοκ. Στην περίπτωση αυτή ο διευθύνσεις επιστροφής εμφανίζονται στη στοίβα με σειρά c, b, a. Μετά την εκτέλεση κάθε διαδικασίας, η διεύθυνση επιστροφής απωθείται από τη στοίβα και ο έλεγχος μεταβιβάζεται στη διεύθυνση αυτή. Το παράδειγμα αυτό δείχνει μία από τις πολλές χρησιμότητες της LIFO ιδιότητας της στοίβας.

Μπορεί να μου εξηγήσει κανποιος το παράδειγμα που δίνει ;

beronc

Θα το πώ όσο πιο απλά και χοντρικά γίνεται.
Κάθε φορά που καλείται ένα υποπρόγραμμα, ο έλεγχος και η εκτέλεση του προγράμματος παραδίδεται στο υποπρόγραμμα (οι τιμές που έχουν οι μεταβλητές, οι διευθύνσεις μνήμης που έχουν καταλάβει, η γραμμή στην οποία έχει φτάσει η εκτέλεση κ.ο.κ.)
Για να αρχίσει το υποπρόγραμμα να εκτελεστεί,, όλα αυτά που έχουν γίνει πρέπει να "φύγουν" από τη μέση. Έτσι, μπαίνουν σε μια λανθάνουσα μνήμη, που έχει μια διεύθυνση.
Το υποπρόγραμμα, αφού εκτελεστεί, πρέπει να δει που θα παραδώσει τα αποτελέσματά του. Έτσι, χρειάζεται μια διεύθυνση στη λανθάνουσα μνήμη που θα πάει να παραδώσει τα αποτελέσματά του. Αυτή η διεύθυνση είναι που κρατιέται σε μια στοίβα. Και αυτό γιατί? Γιατί ένα υποπρόγραμμα μπορεί να καλεί ένα άλλο υποπρόγραμμα. Σε αυτή την περίπτωση και το υποπρόγραμμα θα πρέπει να αποθηκευτεί σε μια δευτερευουσα μνήμη και ο έλεγχος να περάσει στο επόμενο υποπρόγραμμα. Με αυτό το τρόπο όμως, η εκτέλεση του προγράμματος, οι προηγούμενες μεταβλητές κλπ θα μπορούσαν να χαθούν.
Για να στο δώσω ΠΟΛΥ ΧΟΝΤΡΙΚΑ να το καταλάβεις σχηματικά:
Ας υποθέσουμε ότι παίρνουμε μια «φωτογραφία» της μνήμς τη στιγμή που εκτελείται ένα πρόγραμμα
ΔΙΑΒΑΣΕ χ,ψ,ζ
ΚΥΡΙΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΗΝΗΜΗΣ
1                                           χ
2                                           ψ
3                                           ζ
4   
5   
6   
ΔΕΥΤΕΡΕΥΟΥΣΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΝΗΜΗΣ
6   
5   
4   
3   
2   
1   

ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ
ΣΤΟΙΒΑ ΔΙΕΥΘΥΝΣΕΩΝ





Η αμέσως επόμενη εντολή είναι
ω <-- κανω_κατι (α,β,γ)
Αφού η εντολή αυτή χρησιμοποιεί μια συνάρτηση, αυτό σημαίνει ότι ο έλεγχος της εκτέλεσης του προγράμματος πρέπει να φύγει από το κυρίως πρόγραμμα και να παραδοθεί στη συνάρτηση. Άρα, το κυρίως πρόγραμμα πρέπει να μας «αδειάσει τη γωνιά». Μεταφέρεται λοιπόν σε μια δευτερεύουσα μνήμη.
ΣΥΝΑΡΤΗΣΗ κάνω_κατι(χ,ψ,ζ):ΑΚΕΡΑΙΑ
...
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
ΚΥΡΙΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΗΝΗΜΗΣ
1                                        χ (συναρτησης κανω_κάτι)
2                                        ψ (συναρτησης  κανω_κάτι)
3                                        ζ(συναρτησης  κανω_κάτι)
4   
5   
6   
ΔΕΥΤΕΡΕΥΟΥΣΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΝΗΜΗΣ
6   
5   
4   
3   
2   
1   χ,ψ,ζ (του κυρίως προγράμαμτος)

ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ
ΣΤΟΙΒΑ ΔΙΕΥΘΥΝΣΕΩΝ



1

Ας υποθέσουμε τώρα, ότι η συνάρτηση κανω_κατι, καλεί και μια άλλη συνάρτηση στο εσωτερικό της
ΣΥΝΑΡΤΗΣΗ Κανω_κατι (χ,ψ,ζ):ΑΚΕΡΑΙΑ
...
Temp <-- κατι_άλλο (χ,ψ,ζ)
...
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ

ΣΥΝΑΡΤΗΣΗ κατι_αλλο (χ,ψ,ζ):ΑΚΕΡΑΙΑ
...
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
ΚΥΡΙΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΗΝΗΜΗΣ
1                                         χ (συναρτησης κάτι_άλλο)
2                                        ψ (συναρτησης  κάτι_άλλο)
3                                         ζ(συναρτησης  κάτι_άλλο)
4   
5   
6   
ΔΕΥΤΕΡΕΥΟΥΣΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΝΗΜΗΣ
6   
5   
4   
3   
2   χ,ψ,ζ ((συναρτησης κανω_κάτι)
1   χ,ψ,ζ (του κυρίως προγράμαμτος)

ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ
ΣΤΟΙΒΑ ΔΙΕΥΘΥΝΣΕΩΝ


2
1


Επιτέλους, τελειώνει και η εκτέλεση της συνάρτησης κατι_άλλο ...
Τώρα, πρέπει να γυρίσει τα αποτελέσματα πίσω. Ναι, αλλά που?
Ε! αυτό το δείχνει η στοίβα χρόνου εκτέλεσης. Που του λέει.
«τα αποτελέσματά σου, θα τα γυρίσεις στις μεταβλητές χ,ψ,ζ της συνάρτησης κανω_κάτι, που τα έχω αποθηκεύσει στη θέση 2»
Παει λοιπον στη θέση 2 και εκχωρεί τιε τιμές και ανακαλεί τη φάση (σε ποια εντολή είχα μείνει), τις μεταβλητές και τις εντολές της συνάρτησης κανω_κατι. Δηλαδή:
ΤΕΛΟΣ_ΣΥΝΑΡΤΗΣΗΣ
ΚΥΡΙΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΗΝΗΜΗΣ
1                                        χ (συναρτησης κανω_κάτι)
2                                        ψ (συναρτησης  κανω_κάτι)
3                                        ζ(συναρτησης  κανω_κάτι)
4   
5   
6   
ΔΕΥΤΕΡΕΥΟΥΣΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΝΗΜΗΣ
6   
5   
4   
3   
2   
1   χ,ψ,ζ(του κυρίως προγράμαμτος)

ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ
ΣΤΟΙΒΑ ΔΙΕΥΘΥΝΣΕΩΝ



1

Αφού τελειώσει και η εκτέλεση της συναρτησης κανω_κατι πρέπει να τα γυρίσει στο κυρίως πρόγραμμα. Που όμως? Ρωτάει τη στοιβα χρονου εκτέλεσης και του λεέι ότι πρέπει να τα γυρίσει στις μεταβλητές που βρίσκονται στη δευτερεύουσα μνήμη στη θέση 1
Ανακαλεί λοιπόν πάλι ότι πρέπει από αυτή τη θέση και συνεχίζει την εκτέλεση του το κυρίως πρόγραμμα.
ΚΥΡΙΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΗΝΗΜΗΣ
1                                      χ
2                                      ψ
3                                      ζ
4   
5   
6   
ΔΕΥΤΕΡΕΥΟΥΣΑ ΜΝΗΜΗ
ΔΙΕΥΘΥΝΣΗ ΜΝΗΜΗΣ   ΠΕΡΙΕΧΟΜΕΝΟ ΜΝΗΜΗΣ
6   
5   
4   
3   
2   
1   

ΣΤΟΙΒΑ ΧΡΟΝΟΥ ΕΚΤΕΛΕΣΗΣ
ΣΤΟΙΒΑ ΔΙΕΥΘΥΝΣΕΩΝ





Χοντρικά, κάτι τέτοιο γίνεται. Βλέπεις ότι έτσι όπως εκτελείται το πρόγραμμα οι διευθύνσεις γεμίζουν σαν στοίβα και όπως επιστρέφουν τα υποπρογράμαμτα τα αποτελέσματά τους, αδειάζει σαν στοίβα. Γι'αυτό ονομάζεται στοιβα χρόνου εκτέλεσης.

Αν κάποιος μπορεί να το εξηγήσει λίγο καλύτερα, ειναι υπερβολικά ευπρόσδεκτος  :)

dpa2006

ας μου επιτραπεί να αναφέρω για βιβλιογραφικούς λόγους και τις αναφορές από Wikipedia:



Στοίβα κλήσεων
Call stack

Computer science (abbreviated CS or CompSci) is the scientific and practical approach to computation and its applications. It is the systematic study of the feasibility, structure, expression, and mechanization of the methodical processes (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information, whether such information is encoded in bits and bytes in a computer memory or transcribed engines and protein structures in a human cell.source:http://en.wikipedia.org/wiki/Computer_science

bugman

Πρόσθετη πληροφορία:
Αυτή η στοίβα Execution Time Stack χρησιμοποιείται εκτός από αποθήκευση τιμών του PC (Program Counter, μετρητή προγράμματος γλώσσας μηχανής)  και για αποθήκευση τοπικών μεταβλητών. Αυτές οι μεταβλητές στη C λέγονται auto και εκτός από μερικές από αυτές που μπορεί να έχουν χώρο αποθήκευσης στους καταχωρητές του επεξεργαστή, παίρνουν κατά την εκτέλεση χώρο στη στοίβα επιστροφών. Η εκχώρηση γίνεται με αλλαγή κατά ένα συγκεκριμένο βήμα (offset) του stack pointer (του δείκτη της στοίβας).

Περί της ελληνικής μετάφρασης του όρου:
Γιατί όμως την Execution Time Stack την λένε έτσι οι άγγλοι/αμερικάνοι? Γιατί ένα πρόγραμμα μπορεί να κάθεται ως αρχείο, άρα να μην εκτελείται, ή να εκτελείται! Όταν εκτελείται τότε είναι στο Execution Time, ή περίοδο εκτέλεσης. Η στοίβα αυτή λοιπόν ελληνικά θα έπρεπε να λέγεται Στοίβα κατά την Εκτέλεση, ή πιο απλά Στοίβα Εκτέλεσης (απ´ευθείας στην γενική). (Ελληνικά Execution Time σημαίνει Διάστημα Εκτέλεσης, ή Περίοδος Εκτέλεσης).

Συμπλήρωμα:
Σύνδεσμος περί αυτόματων μεταβλητών (αναφέρει και το Stack Frame, το πλαίσιο στη στοίβα, δηλαδή μια συνεχή σειρά θέσεων όπου μπαίνουν οι τιμές για τις αυτόματες μεταβλήτες, και διαγράφεται στο τέλος της εκτέλεσης ρουτίνας-συνάρτησης, με μια κίνηση, με την αλλαγή της τιμής του δείκτη της στοίβας ή stack pointer).
https://en.wikipedia.org/wiki/Automatic_variable