ΗΥ-225: Οργάνωση Υπολογιστών
Άνοιξη 2021 |
Τμ. Επ. Υπολογιστών © Πανεπιστήμιο Κρήτης |
[Up - Table of Contents] [Prev - 5. Compare and Branch] |
[printer version - PDF] [7. Linked List - Next] |
Βιβλίο: Διαβάστε την §2.8: pp. 98 - 107 στο Αγγλικό βιβλίο, ή σελίδες 152 - 163 στο Ελληνικό.
Οι διαδικασίες (procedures) αποτελούν βασική μονάδα
του δομημένου, αρθρωτού (modular) προγραμματισμού,
και εδώ θα εξετάσουμε τον τρόπο κλήσης και επιστροφής τους,
και περάσματος ορισμάτων και επιστρεφόμενων τιμών στην C στον RISC-V.
Θα ξεκινήσουμε με τη χρήση των καταχωρητών
και τη διατήρηση των περιεχομένων τους,
θα συνεχίσουμε με το πέρασμα ορισμάτων και επιστρεφόμενης τιμής,
και θα τελειώσουμε με τα άλματα κλήσης και επιστροφής
και με ένα συνολικό παράδειγμα.
Σε ένα κάλεσμα διαδικασίας, η αφελής πρακτική θα ήταν και ο γονέας, από υπερβολικό φόβο, να σώζει τις τιμές των καταχωρητών που χρησιμοποιεί στη μνήμη –στη στοίβα, όπως θα πούμε παρακάτω– και το παιδί, από υπερβολική αίσθηση ευθύνης, να προστατεύει την παλαιά τιμή του κάθε καταχωρητή, σώζοντάς την (επίσης στη μνήμη), πριν την "χαλάσει" γιά να βάλει εκεί κάτι δικό του. Προφανώς, είναι διπλός και περιττός κόπος και οι δύο να το κάνουν αυτό –αρκεί να το κάνει μόνον ο ένας από τους δύο –αλλά ποιός από τους δυό; Όπως θα δούμε, μερικές φορές συμφέρει να κάνει το σώσιμο (και επαναφορά) ο ένας, και άλλες φορές ο άλλος. Γιά να δουλέψει σωστά αυτό, και σε συνθήκες χωριστού compilation, ο RISC-V χωρίζει τους καταχωρητές του σε κατηγορίες, όπως στο σχήμα, και ορίζει Συμβάσεις Χρήσης Καταχωρητών, που επιγραμματικά είναι οι εξής:
Προσωρινοί Καταχωρητές - temporary registers: t0 έως και t6, καθώς και όσοι από τους καταχωρητές ορισμάτων, a, δεν χρησιμοποιούνται σαν ορίσματα από την τρέχουσα διαδικασία (7 έως 14 καταχωρητές, συνολικά): Η τιμή των καταχωρητών αυτών δεν διατηρείται μετά από ένα κάλεσμα διαδικασίας (not preserved across call), δηλαδή η καλούμενη διαδικασία (ή άλλες που τυχόν καλούνται από αυτήν) επιτρέπεται να μεταβάλει την τιμή αυτών των καταχωρητών χωρίς προηγουμένως να σώσει την τιμή που τυχόν είχε μείνει εκεί από την καλούσα διαδικασία, επομένως και χωρίς να επαναφέρει την παλαιά εκείνη τιμή προ της επιστροφής στην καλούσα διαδικασία. Αρα, αν η καλούσα διαδικασία έχει κάτι χρήσιμο μέσα σε έναν τέτοιο καταχωρητή ενώ ετοιμάζεται να καλέσει μιαν άλλη διαδικασία, το οποίο χρήσιμο επιθυμεί να το ξαναβρεί στη θέση του μετά την επιστροφή του καλέσματος, είναι ευθύνη της καλούσας διαδικασίας να σώσει την χρήσιμη τιμή πριν το κάλεσμα ("caller-saved") (στη στοίβα στη μνήμη), και να την επαναφέρει (restore) από εκεί αμέσως μετά, δηλαδή μετά την επιστροφή του καλέσματος.
Προσωρινές τιμές των οποίων η διάρκεια ζωής (lifetime) δεν περιλαμβάνει καλέσματα διαδικασιών συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, t, διότι δεν χρειάζεται ούτε να σώσουμε τα παλαιά περιεχόμενα (από αυτόν που μας κάλεσε) πριν τους χρησιμοποιήσουμε (επειδή είναι τύπου t), ούτε να σώσουμε τα νέα περιεχόμενά τους πριν τελειώσει η χρήση τους, αφού κατά τη διάρκεια ζωής τους δεν καλούμε καμία άλλη διαδικασία, άρα δεν κινδυνεύουμε από κανέναν απόγονο να μας χαλάσει το δικό μας περιεχόμενο. Εάν κατά τη διάρκεια ζωής αυτών των τιμών υπήρχαν καλέσματα θυγατρικών διαδικασιών, τότε σε κάθε τέτοιο κάλεσμα θα χρειάζονταν σώσιμο του "προσωρινού" αυτού καταχωρητή, και επαναφορά του μετά την επιστροφή, αφού η καλούμενη διαδικασία θα ήταν ελεύθερη (πιθανόν) να καταστρέψει την εκεί περιεχόμενη τιμή, οπότε και δεν θα συνέφερε η χρήση καταχωρητή τύπου t· όμως, ακριβώς επειδή δεν υπάρχουν καλέσματα θυγατρικών διαδικασιών κατά τη διάρκεια ζωής αυτής της τιμής, γι' αυτό και συμφέρει η τοποθέτησή της σε "προσωρινό" καταχωρητή.
Ένα πόρισμα είναι ότι διαδικασίες-φύλλα (leaf procedures), δηλαδή διαδικασίες που δεν καλούν καμία άλλη διαδικασία μέχρι να επιστρέψουν οι ίδιες (φύλλα στο δένδρο της (δυναμικής) κλήσης διαδικασιών), συμφέρει να βάζουν όλες τις τοπικές τους μεταβλητές και άλλες ενδιάμεσες τιμές σε καταχωρητές αυτού του τύπου, t. Παρατηρήστε ότι εάν το δένδρο της (δυναμικής) κλήσης διαδικασιών έχει μέσο fan-out μεγαλύτερο του 2, τότε οι διαδικασίες-φύλλα αποτελούν την πλειοψηφία των (δυναμικά) ενεργοποιούμενων διαδικασιών.
Διατηρούμενοι Καταχωρητές - saved registers: s0 έως και s11 (12 καταχωρητές, συνολικά): Η τιμή των καταχωρητών αυτών διατηρείται μετά από ένα κάλεσμα διαδικασίας (preserved across call), δηλαδή είναι ευθύνη της καλούμενης διαδικασίας να σώσει την παλαιά τιμή κάθε τέτοιου καταχωρητή πριν την χαλάσει ("callee-saved"), και να την επαναφέρει στη θέση της πριν επιστρέψει στην καλούσα διαδικασία. Αρα, η καλούσα διαδικασία μπορεί να αφήνει χρήσιμες τιμές σε αυτούς τους καταχωρητές, πριν καλέσει άλλες διαδικασίες, και να τις ξαναβρίσκει μετά την επιστροφή από αυτές, χωρίς να χρειάζεται –η καλούσα διαδικασία– να κάνει κάτι ιδιαίτερο γι' αυτό.
Μεταβλητές και τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει δύο ή περισσότερα καλέσματα διαδικασιών, με επανειλημμένη χρήση της παλαιάς τιμής τους μεταξύ των καλεσμάτων, συμφέρει να τοποθετούνται σε τέτοιους καταχωρητές, s: Γιά κάθε καταχωρητή s που χρησιμοποιεί η τρέχουσα διαδικασία, αρκεί ένα σώσιμο της τιμής που (πιθανόν) έχει αφήσει εκεί κάποιος πρόγονος, και μία επαναφορά της τιμής του προγόνου. Το σώσιμο του "προγονικού" περιεχομένου πρέπει να γίνει μετά την έναρξη εκτέλεσης της τρέχουσας διαδικασίας και πριν χρησιμοποιηθεί γιά πρώτη φορά ο καταχωρητής, η δε επαναφορά του προγονικού αυτού περιεχομένου πρέπει να γίνει μετά το τέλος χρήσης του καταχωρητή από την τρέχουσα διαδικασία και πριν αυτή επιστρέψει στον γονέα της. Αντίθετα, δεν απαιτείται σώσιμο και επαναφορά κάθε φορά που η τρέχουσα διαδικασία καλεί παιδιά της –πράγμα που θα χρειάζονταν εάν η μεταβλητή αυτή είχε τοποθετηθεί σε καταχωρητή τύπου t, και γι' αυτό δεν θα συνέφερε εδώ η τοποθέτηση σε t αφού τα καλέσματα παιδιών στη διάρκεια ζωής είναι δύο ή περισσότερα.
Τιμές των οποίων η διάρκεια ζωής (lifetime) περιλαμβάνει ακριβώς ένα κάλεσμα θυγατρικής διαδικασίας κοστίζουν το ίδιο από πλευράς σωσίματος-επαναφοράς καταχωρητών, είτε τοποθετηθούν σε καταχωρητή τύπου t, είτε σε καταχωρητή s.
Η "Στοίβα των Πλαισίων Ενεργοποίησης Διαδικασιών" (Procedure Activation Frame Stack, ή Runtime Stack) –κατά το επίσημο όνομά της– συνήθως (ίσως πάντα) ξεκινάει από τις μεγαλύτερες διευθύνσεις που έχει στη διάθεσή της η διεργασία του χρήστη (user process) (σε αντιδιαστολή με τον πυρήνα του Λειτουργικού Συστήματος - O.S. kernel), και μεγαλώνει (όποτε καλείται νέα διαδικασία) προς τις μικρότερες διευθύνσεις. (Αυτό βοηθά στο να αργήσει να συναντηθεί (ελπίζουμε ποτέ να μην συναντηθεί) με τον "σωρό" (heap), όπου δίνει χώρο η malloc(), και ο οπίος μεγαλώνει από τις μικρές προς τις μεγάλες διευθύνσεις). Στους 32-μπιτους επεξεργαστές, συχνά η στοίβα ξεκινάει από τη διεύθυνση 7F.FF.FF.FF (δεκαεξαδικό), δηλαδή από τη μέση της μνήμης (όπου ο υπόλοιπος μισός χώρος διευθύνσεων συχνά είναι γιά το OS kernel), και μεγαλώνει προς τις μικρότερες διευθύνσεις (προς τη διεύθυνση 0). Ο Stack Pointer (καταχωρητής sp) δείχνει στην τελευταία χρησιμοποιούμενη λέξη της στοίβας. (Στον κανονικό RISC-V, ο sp κρατιέται πάντα ευθυγραμμισμένος σε ακέραια πολλαπλάσια των 16 Bytes (quad words), αλλά εμείς εδώ δεν θα το επιβάλουμε αυτό). Πριν αποθηκεύσουμε Ν νέες 32-μπιτες λέξεις στη στοίβα πρέπει να ελαττώσουμε τον sp κατά 4Ν (το μέγεθος N λέξεων των 4 Bytes καθεμία) (ή κατά 8N αν οι λέξεις είναι 64-μπιτες), πράγμα που ισοδυναμεί με δήλωση από πλευράς του προγράμματός μας (προς το λειτουργικό σύστημα, σε περίπτωση διακοπής (interrupt - page fault)) ότι τώρα η στοίβα μας είναι τώρα μεγαλύτερη κατά Ν λέξεις. Η αντίστροφη πράξη (αύξηση του $sp κατά 4Ν (ή 8N) –απελευθέρωση μνήμης) πρέπει να γίνει αφού πάρουμε τις αποθηκευμένες λέξεις και δεν τις χρειαζόμαστε άλλο πιά στη στοίβα. Οι τιμές που βρίσκονται αποθηκευμένες στη στοίβα προσπελαύνονται συνήθως μέσω εντολών load και store με διευθυνσιοδότηση σχετικά με τον sp. Καθώς ο sp αυξομειώνεται λόγω παραχώρησης/απελευθέρωσης μνήμης, η απόσταση των αποθηκευμένων τιμών στη στοίβα από τον sp αλλάζει, αλλά παραμένει πάντοτε γνωστή στον compiler/προγραμματιστή (εκτός των περιπτώσεων δυναμικής παραχώρησης μνήμης στη στοίβα –πράγμα σπάνιο στις γλώσσες προγραμματισμού– οπότε και απαιτείται η χρήση του fp).
Τοπικές (Local) και Καθολικές (Global) Μεταβλητές:
Οι "καθολικές" και οι "τοπικές" μεταβλητές
είναι έννοιες των γλωσσών προγραμματισμού υψηλού επιπέδου
(HLL - π.χ. C, κλπ).
Γιά τον Assembler δεν υπάρχουν αυτές οι έννοιες,
ενώ η υλοποίηση των εννοιών αυτών σε επίπεδο γλώσσας Assembly
επαφίεται στον προγραμματιστή (ή στον compiler).
Στις HLL, μια καθολική μεταβλητή
αντιστοιχεί πάντα σε μια δεδομένη, σταθερή θέση μνήμης
(ή καταχωρητή, αν και σπανίως αυτές τοποθετούνται σε καταχωρητές),
ανεξαρτήτως του ποιά διαδικασία εκτελείται κάθε στιγμή·
η τιμή μιας καθολικής μεταβλητής
ούτε χρειάζεται να αποθηκευτεί ποτέ στη στοίβα,
ούτε επανατίθεται ποτέ σε παλαιές τιμές της από τη στοίβα.
Αντίθετα, μιά τοπική μεταβλητή
έχει νόημα μόνο όσο είναι ενεργή η διαδικασία στην οποία ανήκει,
και είναι ανύπαρκτη πριν την εκκίνηση της διαδικασίας αυτής
ή μετά τον τερματισμό (επιστροφή) της διαδικασίας·
εάν η διαδικασία επιστρέψει και ξανακαλεστεί,
η παλαιά τιμή της τοπικής μεταβλητής έχει χαθεί.
Επίσης, τοπικές μεταβλητές
με το ίδιο όνομα αλλά σε διαφορετική διαδικασία
(ή σε διαφορετική ενεργοποίηση της ίδιας (αναδρομικής) διαδικασίας!)
είναι διαφορετικές και άσχετες μεταξύ τους!
Συνήθως, οι μεταφραστές (compilers) τοποθετούν την κάθε καθολική μεταβλητή σε μία σταθερή διεύθυνση μνήμης –όχι στη στοίβα· η διεύθυνση αυτή δεν αλλάζει από διαδικασία σε διαδικασία. Αντίθετα, οι τοπικές μεταβλητές αντιστοιχούν σε μιά θέση στη στοίβα, σε δεδομένη απόσταση σχετικά με τον stack-pointer, η οποία θέση υπάρχει μόνον όση ώρα είναι ενεργοποιημένη η αντίστοιχη διαδικασία, και η οποία θέση –σαν απόλυτη διεύθυνση μνήμης– πολύ πιθανόν να αλλάζει από ενεργοποίηση σε ενεργοποίηση της διαδικασίας. Εάν ένα αντίτυπο της μεταβλητής κρατηθεί σε καταχωρητή (ή, όπως η συνηθισμένη βελτιστοποίηση, κρατηθεί μόνο το "αντίτυπο", χωρίς το πρωτότυπο), τότε η διαδικασία αυτή (σε συνεργασία με τις άλλες) έχει την ευθύνη να σώζει το αντίτυπο στη στοίβα και να το επαναφέρει όποτε υπάρχει κίνδυνος μια άλλη διαδικασία να χρησιμοποιήσει τον καταχωρητή αυτό διαφορετικά, όπως αναλύσαμε παραπάνω.
Παρατηρήστε ότι οι παραπάνω έννοιες δεν είναι ίδιες με τις "καθολικές ετικέτες" (global labels) που γιά τον Assembler ορίζονται με την οδηγία ".globl". Οι ετικέτες του Assembler είναι απλά διευθύνσεις μνήμης –είτε δεδομένων, είτε εντολών μέσα σε πρόγραμμα, είτε οτιδήποτε. Καθολική ετικέτα είναι απλώς μια διεύθυνση την οποία ζητάμε από τον Assembler να την τοποθετήσει στον Πίνακα Συμβόλων (Symbol Table), μαζί με το συμβολικό της όνομα, ο οποίος πίνακας περιλαμβάνεται στο αρχείο δυαδικού κώδικα (binary/object code file). Τότε, ο Linker, όταν ξαναβρεί το ίδιο όνομα σε άλλο αρχείο, θεωρεί ότι πρόκειται γιά την ίδια διεύθυνση, και "συνενώνει" τις δύο αναφορές. Με άλλα λόγια, μιά καθολική ετικέτα (σύμβολο) είναι η ίδια και καθολικά ορατή ανάμεσα σε όλα τα συνενούμενα (linked) αρχεία ενός προγράμματος.
Εντός του else{}, απαιτείται ο πολλαπλασιασμός του n (πρώτο όρισμα της δικής μας διαδικασίας, άρα στον καταχωρητή a0) επί την τιμή που επιστρέφει το κάλεσμα του παιδιού. Ο πολλαπλασιασμός αυτός, επομένως, μπορεί να γίνει μόνον μετά την επιστροφή από το κάλεσμα του παιδιού. Όμως, το κάλεσμα ενός παιδιού καταστέφει (εν δυνάμει) τα ορίσματα (και τις τοπικές μεταβλητές) της δικής μας διαδικασίας, άρα θα καταστρέψει (εδώ σίγουρα) (και) τον καταχωρητή a0 (δηλαδή το όρισμά μας n). Άρα πριν το κάλεσμα πρέπει να σώσουμε στη στοίβα, εκτός από τον ra, και τον καταχωρητή a0. Αφού υποθέτουμε 64-μπιτο RISC-V, ο καθένας καταχωρητής πιάνει 8 Bytes στη στοίβα, άρα σύνολο 16 Bytes εδώ, άρα πριν το σώσιμο θα πρέπει να μεγαλώσουμε τη στοίβα κατά 16 Bytes (sp ← sp-16), και μετά την επαναφορά των καταχωρητών από τη στοίβα θα πρέπει να την μειώσουμε κατά τα ίδια 16 Bytes (sp ← sp+16).
Πριν καλέσουμε το παιδί μας, πρέπει να του δώσουμε σαν (πρώτο και μοναδικό) όρισμα το n-1, και αυτό πρέπει να του το δώσουμε, σύμφωνα με τη σύμβαση, στον καταχωρητή a0. Όταν θα επιστρέψει σε εμάς το παιδί μας, θα βρούμε την επιστρεφόμενή του τιμή, fact(n-1), σύμφωνα με τη σύμβαση, πάλι στον καταχωρητή a0. Αντίστοιχα και εμείς οι ίδιοι, πριν επιστρέψουμε στο γονέα μας, πρέπει να βάλουμε στον καταχωρητή a0 την τιμή που επιστρέφουμε (1 στην περίπτωση then, αλλιώς n*fact(n-1) στην περίπτωση else). Θα χρειαστούμε και έναν προσωρινό καταχωρητή –ας χρησιμοποιήσουμε τον t0 (υπενθύμιση: αφού είναι "tmp", δεν χρειάζεται σώσιμο-επαναφορά των τυχόν περιεχομένων του από τους προγόνους). Με αυτές τις σκέψεις, η διαδικασία fact() μεταφράζεται ως εξής σε Assembly του RISC-V:
fact: addi t0, zero, 2 # immediate 2 needed for "if(n<2)" bge a0, t0, elseF # if n<2 false, i.e. if n≥2 goto ELSE addi a0, zero, 1 # THEN: create return-value 1, place in reg. a0 jr ra # return --this is the end of the "then" clause elseF: addi sp, sp, -16 # PUSH1: allocate 16 Bytes on the stack sd ra, 8(sp) # PUSH2: save ra into first allocated word sd a0, 0(sp) # PUSH3: save my argument (n) into second word addi a0, a0, -1 # create argument (n-1) into a0 for my child jal ra, fact # call my child procedure add t0, a0, zero # copy return value from my child into t0 # (because I need to restore my own argument into a0) ld ra, 8(sp) # POP1: restore ra from stack ld a0, 0(sp) # POP2: restore a0 from stack addi sp, sp, 16 # POP3: dealloc the 16 B that I had allocated mul a0, a0, t0 # multiply my own arg a0==n times the return # value from my child that I had copied into t0, and # place the result into a0, as my own return value jr ra # return