ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2018
Τμ. Επ. Υπολογιστών
© Πανεπιστήμιο Κρήτης

Διαλέξεις 6:
Κάλεσμα Διαδικασιών, Χρήση και Σώσιμο Καταχωρητών

[Up - Table of Contents]
[Prev - 5. Compare and Branch]
[printer version - PDF]
[7. Linked List - Next]

Βιβλίο: Διαβάστε την §2.8, σελίδες 152 - 163.

Το κάλεσμα διαδικασίας (procedure call) γίνεται μέσω της εντολής jal (jump and link - άλμα και σύνδεση), η δε επιστροφή από διαδικασία (procedure return) γίνεται μέσω της εντολής jr (jump register - άλμα εκεί που δείχνει ένας καταχωρητής), όπως είδαμε στην § 5.1.

6.1   Τίνος Ευθύνη είναι το Σώσιμο των Καταχωρητών:

Οταν διάφορες διαδικασίες χρησιμοποιούν τον ίδιο καταχωρητή γιά διαφορετικούς σκοπούς η καθεμία, σε τρόπο που να καταστρέφεται η προηγούμενη τιμή του καταχωρητή –την οποία όμως δεν θέλουμε να χάσουμε, τότε καποιος πρέπει να "σώσει" (αντιγράψει) την προηγούμενη τιμή σε ασφαλές μέρος (στη μνήμη) και αργότερα να την επαναφέρει στον καταχωρητή. Γιά να ελαχιστοποιηθεί το κόστος αυτής της εργασίας (δηλαδή το πόσο συχνά πρέπει αυτή να γίνεται), οι compilers του MIPS ακολουθούν τις παρακάτω συμβάσεις. (Οι συμβάσεις αυτές είναι αρκούντως συντηρητικές ώστε να επιτρέπουν χωριστή μετάφραση (separate compilation) των διαδικασιών). Εστω ότι μιά διαδικασία Α καλεί μιάν άλλη διαδικασία Β (ή η ενεργοποίηση (instance) Α μιάς αναδρομικής διαδικασίας καλεί την ενεργοποίηση Β του εαυτού της). Θα ονομάζουμε την: Προσωρινοί Καταχωρητές $t0 - $t9 ($8-$15 και $24-$25) – temporary registers: Η τιμή των καταχωρητών αυτών δεν διατηρείται μετά από ένα κάλεσμα διαδικασίας (not preserved across call), δηλαδή η καλούμενη διαδικασία (ή άλλες που τυχόν καλούνται από αυτήν) επιτρέπεται να μεταβάλει την τιμή αυτών των καταχωρητών χωρίς προηγουμένως να σώσει την τιμή που τυχόν είχε μείνει εκεί από την καλούσα διαδικασία, επομένως και χωρίς να επαναφέρει την παλαιά εκείνη τιμή προ της επιστροφής στην καλούσα διαδικασία. Αρα, αν η καλούσα διαδικασία έχει κάτι χρήσιμο μέσα σε έναν τέτοιο καταχωρητή ενώ ετοιμάζεται να καλέσει μιαν άλλη διαδικασία, το οποίο χρήσιμο επιθυμεί να το ξαναβρεί στη θέση του μετά την επιστροφή του καλέσματος, είναι ευθύνη της καλούσας διαδικασίας να σώσει την χρήσιμη τιμή πριν το κάλεσμα ("caller-saved"), και να την επαναφέρει αμέσως μετά από αυτό (δηλ. μετά την επιστροφή του).

Προσωρινές τιμές των οποίων η διάρκεια ζωής (lifetime) δεν περιλαμβάνει καλέσματα διαδικασιών συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, διότι δεν χρειάζεται να σώσουμε τα παλαιά περιεχόμενα (από αυτόν που μας κάλεσε) αυτών των καταχωρητών πριν τους χρησιμοποιήσουμε. Εάν κατά τη διάρκεια ζωής αυτών των τιμών υπήρχαν καλέσματα θυγατρικών διαδικασιών, τότε σε κάθε τέτοιο κάλεσμα θα χρειάζονταν σώσιμο του "προσωρινού" αυτού καταχωρητή, και επαναφορά του μετά την επιστροφή, αφού η καλούμενη διαδικασία θα ήταν ελεύθερη (πιθανόν) να καταστρέψει την εκεί περιεχόμενη τιμή, οπότε και δεν θα συνέφερε η χρήση καταχωρητή τύπου $t· όμως, ακριβώς επειδή δεν υπάρχουν καλέσματα θυγατρικών διαδικασιών κατά τη διάρκεια ζωής αυτής τιμής, γι' αυτό και συμφέρει η τοποθέτησή της σε "προσωρινό" καταχωρητή.

Ένα πόρισμα είναι ότι διαδικασίες-φύλλα (leaf procedures), δηλαδή διαδικασίες που δεν καλούν καμία άλλη διαδικασία μέχρι να επιστρέψουν οι ίδιες (φύλλα στο δένδρο της (δυναμικής) κλήσης διαδικασιών), συμφέρει να βάζουν όλες τις τοπικές τους μεταβλητές και άλλες τιμές σε καταχωρητές αυτού του τύπου, $t. Παρατηρήστε ότι εάν το δένδρο της (δυναμικής) κλήσης διαδικασιών έχει μέσο fan-out μεγαλύτερο του 2, τότε οι διαδικασίες-φύλλα αποτελούν την πλειοψηφία των (δυναμικά) ενεργοποιούμενων διαδικασιών.

Διατηρούμενοι Καταχωρητές $s0 - $s7 ($16-$23) – saved registers: Η τιμή των καταχωρητών αυτών διατηρείται μετά από ένα κάλεσμα διαδικασίας (preserved across call), δηλαδή είναι ευθύνη της καλούμενης διαδικασίας να σώσει την παλαιά τιμή κάθε τέτοιου καταχωρητή πριν την χαλάσει ("callee-saved"), και να την επαναφέρει στη θέση της πριν επιστρέψει στην καλούσα διαδικασία. Αρα, η καλούσα διαδικασία μπορεί να αφήνει χρήσιμες τιμές σε αυτούς τους καταχωρητές, πριν καλέσει άλλες διαδικασίες, και να τις ξαναβρίσκει μετά την επιστροφή από αυτές, χωρίς να χρειάζεται –η καλούσα διαδικασία– να κάνει κάτι ιδιαίτερο γι' αυτό.

Μεταβλητές και τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει δύο ή περισσότερα καλέσματα διαδικασιών, με επανειλημμένη χρήση της παλαιάς τιμής τους μεταξύ των καλεσμάτων, συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές: Γιά κάθε τέτοιο καταχωρητή που χρησιμοποιεί η τρέχουσα διαδικασία αρκεί ένα σώσιμο της τιμής που (πιθανόν) έχει αφήσει εκεί κάποιος πρόγονος (μετά την έναρξη εκτέλεσης της τρέχουσας διαδικασίας και πριν χρησιμοποιηθεί γιά πρώτη φορά ο καταχωρητής), και μία επαναφορά της τιμής του προγόνου μετά το τέλος χρήσης του καταχωρητή και πριν επιστρέψει η τρέχουσα διαδικασία. Αντίθετα, δεν απαιτείται σώσιμο και επαναφορά κάθε φορά που η τρέχουσα διαδικασία καλεί παιδιά της. Έτσι, σε μιά τελική συνολική θεώρηση του όλου δένδρου καλεσμάτων, αν οι καλούμενες διαδικασίες (με τους πιθανούς απογόνους τους) δεν χρησιμοποιούν αυτούς τους καταχωρητές, γλιτώνουμε τα πολλαπλά σωσίματα και επαναφορές (σώζουμε και επαναφέρουμε μόνο μία φορά την τιμή που είχε αφήσει εκεί η διαδικασία που κάλεσε εμάς τους ίδιους).

Τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει ακριβώς ένα κάλεσμα θυγατρικής διαδικασίας κοστίζουν το ίδιο από πλευράς σωσίματος-επαναφοράς καταχωρητών, είτε τοποθετηθούν σε καταχωρητή τύπου $t είτε σε καταχωρητή $s.

6.2   Άλλοι Καταχωρητές:

6.3   Πού Σώζονται οι Καταχωρητές:

Αν οι διαδικασίες δεν ήταν αναδρομικές, δηλαδή αν απαγορεύονταν να καλέσει μιά διαδικασία τον εαυτό της –είτε άμεσα είτε έμμεσα μέσω άλλων που αυτή καλεί– τότε θα αρκούσε μιά συγκεκριμένη περιοχή στη μνήμη γιά κάθε διαδικασία, όπου αυτή να φυλάει τις τιμές των καταχωρητών που πρέπει να σώσει και αργότερα να επαναφέρει. Ομως, οι σημερινές γλώσσες προγραμματισμού επιτρέπουν την αναδρομή, κι έτσι μιά τέτοια λύση δεν θα δούλευε. Δεδομένου ότι τα καλέσματα και οι επιστροφές διαδικασιών λειτουργούν με τρόπο "last in first out" (LIFO), η φυσική δομή δεδομένων γιά δυναμική παραχώρηση και απελευθέρωση μνήμης στις διαδικασίες και από τις διαδικασίες είναι η στοίβα (stack).

Η στοίβα (χρήστη) στον MIPS ξεκινάει από τη διεύθυνση 7f.ff.ff.ff (δεκαεξαδικό), δηλαδή από τη μέση της μνήμης, και μεγαλώνει προς τις μικρότερες διευθύνσεις (προς τη διεύθυνση 0). Ο $sp δείχνει στην τελευταία χρησιμοποιούμενη λέξη της στοίβας. Πριν αποθηκεύσουμε Ν νέες λέξεις στη στοίβα πρέπει να ελαττώσουμε τον $sp κατά 4Ν, πράγμα που ισοδυναμεί με την δήλωση από πλευράς του προγράμματός μας (προς το λειτουργικό σύστημα, σε περίπτωση διακοπής (interrupt)) ότι τώρα η στοίβα μας είναι μεγαλύτερη κατά Ν λέξεις. Η αντίστροφη πράξη (αύξηση του $sp κατά 4Ν –απελευθέρωση μνήμης) πρέπει να γίνει αφού πάρουμε τις αποθηκευμένες λέξεις και δεν τις χρειαζόμαστε άλλο πιά στη στοίβα. Οι τιμές που βρίσκονται αποθηκευμένες στη στοίβα προσπελαύνονται συνήθως μέσω εντολών load και store με διευθυνσιοδότηση σχετικά με τον $sp. Καθώς ο $sp αυξομειώνεται λόγω παραχώρησης/απελευθέρωσης μνήμης, η απόσταση των αποθηκευμένων τιμών στη στοίβα από τον $sp αλλάζει, αλλά παραμένει πάντοτε γνωστή στον compiler/προγραμματιστή (εκτός των περιπτώσεων δυναμικής παραχώρησης μνήμης στη στοίβα –πράγμα σπάνιο στις γλώσσες προγραμματισμού– οπότε και απαιτείται η χρήση του $fp).

6.4   Καθολικές (Global) και Τοπικές (Local) Μεταβλητές:

Οι "καθολικές" (global) και οι "τοπικές" (local) μεταβλητές είναι έννοιες των γλωσσών προγραμματισμού υψηλού επιπέδου (HLL - π.χ. C, κλπ). Γιά τον Assembler δεν υπάρχουν αυτές οι έννοιες, ενώ η υλοποίηση των εννοιών αυτών σε επίπεδο γλώσσας Assembly επαφίεται στον προγραμματιστή (ή στον compiler). Στις HLL, μια καθολική μεταβλητή αντιστοιχεί πάντα σε μια δεδομένη, σταθερή θέση μνήμης (ή καταχωρητή), ανεξαρτήτως του ποιά διαδικασία εκτελείται κάθε στιγμή· η τιμή μιας καθολικής μεταβλητής ούτε χρειάζεται να αποθηκευτεί ποτέ στη στοίβα, ούτε επανατίθεται ποτέ σε παλαιές τιμές της από τη στοίβα. Αντίθετα, μιά τοπική μεταβλητή έχει νόημα μόνο όσο είναι ενεργή η διαδικασία στην οποία ανήκει, και είναι ανύπαρκτη πριν την εκκίνηση της διαδικασίας αυτής ή μετά τον τερματισμό (επιστροφή) της διαδικασίας· εάν η διαδικασία επιστρέψει και ξανακαλεστεί, η παλαιά τιμή της τοπικής μεταβλητής έχει χαθεί. Επίσης, τοπικές μεταβλητές με το ίδιο όνομα αλλά σε διαφορετική διαδικασία (ή σε διαφορετική ενεργοποίηση της ίδιας (αναδρομικής) διαδικασίας!) είναι διαφορετικές και άσχετες μεταξύ τους!

Συνήθως, οι μεταφραστές (compilers) τοποθετούν την κάθε καθολική μεταβλητή σε μία σταθερή διεύθυνση μνήμης –όχι στη στοίβα· η διεύθυνση αυτή δεν αλλάζει από διαδικασία σε διαδικασία. Αντίθετα, οι τοπικές μεταβλητές αντιστοιχούν σε μιά θέση στη στοίβα, σε δεδομένη απόσταση σχετικά με τον stack-pointer, η οποία θέση υπάρχει μόνον όση ώρα είναι ενεργοποιημένη η αντίστοιχη διαδικασία, και η οποία θέση –σαν απόλυτη διεύθυνση μνήμης– πολύ πιθανόν να αλλάζει από ενεργοποίηση σε ενεργοποίηση της διαδικασίας. Εάν ένα αντίτυπο της μεταβλητής κρατηθεί σε καταχωρητή (ή, σαν πολύ συνηθισμένη βελτιστοποίηση, κρατηθεί μόνο το "αντίτυπο", χωρίς το πρωτότυπο), τότε η διαδικασία αυτή (σε συνεργασία με τις άλλες) έχει την ευθύνη να σώζει το αντίτυπο στη στοίβα και να το επαναφέρει όποτε υπάρχει κίνδυνος μια άλλη διαδικασία να χρησιμοποιήσει τον καταχωρητή αυτό διαφορετικά, όπως αναλύσαμε παραπάνω.

Παρατηρήστε ότι οι παραπάνω έννοιες δεν είναι ίδιες με τις "καθολικές ετικέτες" (global labels) που γιά τον Assembler ορίζονται με την οδηγία ".globl". Οι ετικέτες του Assembler είναι απλά διευθύνσεις μνήμης –είτε δεδομένων, είτε εντολών μέσα σε πρόγραμμα, είτε οτιδήποτε. Καθολική ετικέτα είναι απλώς μια διεύθυνση την οποία ζητάμε από τον Assembler να την θυμάται, μαζί με το συμβολικό της όνομα, και μετά τη λήξη της "μετάφρασης" από Assembly σε γλώσσα μηχανής του κομματιού προγράμματος όπου την βρήκε, ώστε να μπορούμε να αναφερθούμε σε αυτήν και στον μέλλον –πιθανά μέσα από άλλα αρχεία με άλλα κομμάτια προγράμματος Assembly.


© copyright University of Crete, Greece. Last updated: 25 Feb. 2018 by M. Katevenis.