ΗΥ-225: Οργάνωση Υπολογιστών Άνοιξη 2007

Τμ. Επ. Υπολογιστών © Πανεπιστήμιο Κρήτης

Άσκηση 7:
Πρόγραμμα Συνδεδεμένης Λίστας και Διαδικασιών

Προθεσμία έως Δευτέρα 23 Απριλίου 2007, ώρα 23:59 (βδομάδα 5)

Υπενθύμιση Διαγωνισμού Προόδου: Σάββατο, 12 Μαΐου 2007, ώρα 2:00 - 4:00 μ.μ.
(Ο βαθμός της εξέτασης Προόδου αποτελεί το 20% του βαθμού μαθήματος, οιασδήποτε περιόδου)

[Up - Table of Contents] [Prev - 6. Procedure Call]

[printer version - PDF] [8. Verilog Intro. 1 - Next]

7.1   Δομές Δεδομένων (Data Structures):

Σε αυτή την άσκηση θα χρησιμοποιήσουμε μία δομή δεδομένων (structure) που θα αποτελεί ένα κόμβο μιάς συνδεδεμένης λίστας (linked list). Κάθε κόμβος (δομή δεδομένων) μας θα αποτελείται από δύο λέξεις (των 32 bits καθεμία): έναν ακέραιο "data" που θα περιέχει την "πληροφορία χρήστη", κι έναν δείκτη σύνδεσης (pointer) "nxtPtr" που θα περιέχει τη διεύθυνση του επόμενου κόμβου στη λίστα (στον τελευταίο κόμβο της λίστας, nxtPtr=0). Τα δύο στοιχεία (λέξεις) της δομής μας θα βρίσκονται σε διαδοχικές θέσεις (λέξεις) της μνήμης. Επομένως, κάθε δομή (κόμβος) μας θα έχει μέγεθος 2x4=8 bytes. Διεύθυνση μιάς δομής είναι η διεύθυνση του πρώτου στοιχείου της, δηλαδή του στοιχείου με "μηδενικό offset", που γιά μας είναι το "data". Άρα, το δεύτερο στοιχείο της δομής μας, ο "nxtPtr", βρίσκεται στη διεύθυνση που προκύπτει προσθέτοντας 4x1=4 στη διεύθυνση της δομής (κόμβου).

7.2   Δυναμική Εκχώρηση Μνήμης (Dynamic Memory Allocation):

Το πρόγραμμά σας θα ζητάει και θα παίρνει δομές (κόμβους) από το λειτουργικό σύστημα "δυναμικά", την ώρα που τρέχει (σε run-time). Γιά το σκοπό αυτό θα χρησιμοποιήστε το κάλεσμα συστήματος (system call) "sbrk" (set break). Το κάλεσμα αυτό "σπρώχνει" πιό πέρα (προς αύξουσες διευθύνσεις μνήμης) το σημείο "break", το όριο δηλαδή πριν από το οποίο οι διευθύνσεις μνήμης που γεννά το πρόγραμμα είναι νόμιμες, ενώ μετά από το οποίο (και μέχρι την αρχή της στοίβας) οι διευθύνσεις είναι παράνομες και τυχόν χρήση τους προκαλεί το γνωστό από την C "segmentation violation - core dumped". Το κάλεσμα συστήματος "sbrk" περιγράφεται στις σελίδες 112-113 του βιβλίου (Β' τόμος Ελληνικής έκδοσης), και λειτουργεί κατ' αναλογία με τα άλλα καλέσματα συστήματος (εκτύπωσης και ανάγνωσης) που χρησιμοποιήσατε σε προηγούμενες ασκήσεις. Πριν το καλέσετε, θέτετε τον καταχωρητή $a0 ($4) να περιέχει το πλήθος των νέων bytes που επιθυμείτε (ένας αριθμός). Μετά την επιστροφή του, ο καταχωρητής $v0 ($2) περιέχει τη διεύθυνση του νέου block μνήμης, του ζητηθέντος μεγέθους, που το σύστημα δίνει στο πρόγραμμά σας (έναν pointer). Η επιστρεφόμενη διεύθυνση μνήμης είναι πάντα διάφορη του μηδενός (εκτός --πιθανότατα-- όταν γεμίσει όλη η μνήμη, αλλά δεν χρειάζεται εσείς εδώ να ελέγχετε κάτι τέτοιο), και είναι πάντα ευθυγραμμισμένη σε όρια λέξεων (πολλαπλάσιο του 4) (τουλάχιστο στη δική μας περίπτωση, που ζητάμε πάντα blocks μεγέθους πολλαπλάσιου του 4, αλλά --πιστεύω-- και σε κάθε περίπτωση).

Άσκηση 7.3:   Κατασκευή και Σάρωση Συνδεδεμένης Λίστας

Γράψτε και τρέξτε στον SPIM, σε Assembly του MIPS, ένα πρόγραμμα που πρώτα θα κατασκευάζει και θα γεμίζει με θετικούς ακέραιους αριθμούς μία συνδεδεμένη λίστα (linked list), και στη συνέχεια θα την σαρώνει επαναληπτικά, τυπώνοντας κάθε φορά ένα διαφορετικό υποσύνολο των στοιχείων της --συγκεκριμένα: όσα στοιχεία της είναι μεγαλύτερα από δοθείσα τιμή. Το πρόγραμμά σας θα κρατάει στον καταχωρητή $s0 (δηλαδή τον $16) τον pointer στην αρχή (στον πρώτο κόμβο) της λίστας, και θα αποτελείται από δύο κομμάτια:

7.3(a): Κατασκευή της Λίστας. Χρησιμοποιήστε τον καταχωρητή $s1 ($17) σαν pointer στην ουρά (στον τελευταίο κόμβο) της λίστας. Γιά διευκόλυνση του βρόχου κατασκευής της λίστας (επειδή η εισαγωγή σε κενή λίστα διαφέρει από την εισαγωγή σε μη κενή λίστα), αρχικοποιήστε τη λίστα να περιέχει ένα αδιάφορο ("dummy") κόμβο: ένα κόμβο με data=0 (αφού όλοι οι κόμβοι θα περιέχουν θετικούς αριθμούς, και αφού θα τυπώνουμε μόνο τις τιμές που θα είναι μεγαλύτερες από δοθέντα μη αρνητικό αριθμό, ο κόμβος αυτός ποτέ δεν θα τυπώνεται, κι έτσι θα είναι σαν να μην υπάρχει). Η αρχικοποίηση γίνεται ζητώντας και παίρνοντας ένα κόμβο από το λειτουργικό σύστημα, γράφοντας data=0 και nxtPtr=0 (τελευταίος κόμβος) σε αυτόν, και κάνοντας τους $s0 και $s1 να δείχνουν σε αυτόν τον κόμβο (να περιέχουν τη διεύθυνσή του). Μετά, μπείτε στο βρόχο ανάγνωσης στοιχείων και κατασκευής της λίστας. Σε κάθε ανακύκλωση αυτού του βρόχου:

• Διαβάζουμε έναν ακέραιο αριθμό από την κονσόλα.
• Εάν ο αριθμός αυτός είναι μηδέν, βγαίνουμε από το βρόχο.
• Ζητάμε έναν νέο κόμβο από το λειτουργικό σύστημα (memory allocation).
• Τοποθετούμε τον αριθμό που διαβάσαμε στο πεδίο "data" του κόμβου.
• Συνδέουμε το νέο κόμβο στην ουρά της λίστας.

7.3(b): Σάρωση της Λίστας. Το δεύτερο μέρος του προγράμματος θα διαβάζει έναν μη αρνητικό αριθμό, και θα τυπώνει, με τη σειρά από την αρχή μέχρι το τέλος, όσα στοιχεία της λίστας είναι μεγαλύτερα από αυτόν τον αριθμό. Μην χρησιμοποιήστε τον pointer στον τελευταίο κόμβο της λίστας (από την παλιά τιμή του καταχωρητή $s1 ($17)) γιά να βρίσκετε πού τελειώνει η λίστα --χρησιμοποιήστε τον nxtPtr κάθε κόμβου γιά να ξέρετε αν υπάρχει ή όχι επόμενος κόμβος στη λίστα. Το μέρος αυτό του προγράμματος κάνει τα εξής:

• Διαβάζει έναν ακέραιο αριθμό από την κονσόλα και τον φυλάει στον καταχωρητή $s1 ($17) (υποτίθεται ότι αυτός είναι μη αρνητικός αριθμός, αλλά δεν χρειάζεται εσείς να το ελέγχετε).
• Αρχικοποιεί τον καταχωρητή $s2 ($18) σαν δείκτη (pointer) σάρωσης, να δείχνει στον πρώτο κόμβο της λίστας (τον ξέρουμε από τον $s0 ($16)).
• Μπαίνει σ' ένα βρόχο, σε κάθε ανακύκλωση του οποίου:
  1. ελέγχει αν τα "data" του κόμβου όπου δείχνει ο $s2 ($18) είναι ή όχι μεγαλύτερα από τον $s1 ($17),
  2. αν είναι μεγαλύτερα τα τυπώνει,
  3. ελέγχει αν υπάρχει ή όχι επόμενος κόμβος στη λίστα,
  4. αν δεν υπάρχει βγαίνει από το βρόγχο,
  5. αν υπάρχει, προχωρεί τον $s2 ($18) να δείξει σε αυτόν τον επόμενο κόμβο και επιστρέφει στην αρχή του βρόχου.
• Μετά την έξοδο του βρόχου, επιστρέφει (πάντα) στην αρχή του δεύτερου μέρους του προγράμματος, γιά να ζητήσει μιά νέα τιμή και να ξανατυπώσει τα μεγαλύτερα από αυτή στοιχεία.

7.3(c): Χρήση υπορουτινών.

• Μετατρέψτε το βήμα 7.3(a)(1) σε μια υπορουτίνα "read_int" η οποία δεν παίρνει καμία παράμετρο εισόδου, διαβάζει έναν ακέραιο αριθμό, και επιστρέφει τον αριθμό που διάβασε.
• Μετατρέψτε το βήμα 7.3(a)(3) σε μια υπορουτίνα "node_alloc" η οποία δεν παίρνει καμία παράμετρο εισόδου, ζητάει από το σύστημα να δεσμέυσει ένα κόμβο για τη λίστα, και επιστρέφει τη διεύθυνση της μνήμης που έχει δεσμευθεί, ώστε το πρόγραμμα που καλεί τη node_alloc να εισάγει τον κόμβο στη λίστα.
• Αλλάξτε το πρόγραμμα του 7.3(b) ώστε να χρησιμοποιεί τις ρουτίνες read_int και node_alloc. Στη χρήση καταχωρητών από τις read_int και node_alloc, όπως και το πρόγραμμα σας που τις καλεί πρέπει να τηρήσετε τις συμβάσεις χρήσης καταχωτητών. Οι read_int και node_alloc είναι αρκετά απλές και δεν είναι απαραίτητο να έχουν τοπικές μεταβλητές που να αποθηκεύονται στη στοίβα, ωστόσο θα πρέπει να έχουν η καθε μία το δικό της stack frame, π.χ. για την αποθήκευση της διεύθυνσης επιστροφής.
• Γράψτε μια υπορουτίνα print_node που κάνει ότι περιγράφουν τα βήματα 7.3(b)(3i) και 7.3(b)(3ii). Η υπορουτίνα θα πέρνει ως είσοδο τη διεύθυνση ενός κόμβου και δεν θα επιστρέφει τίποτε.
• Γράψτε μια υπορουτίνα search_list που υλοποιεί όλο το βήμα 7.3(b)(3). H ρουτίνα θα πέρνει ως πρώτη είσοδο τη διεύθυνση του πρώτου κόμβου τις λίστας (δείκτης σάρωσης) και σαν δεύτερη είσοδο την τιμή για την οποία πρέπει να ψάξει. Στη συνέχεια θα υλοποιεί τα βήματα (i,ii,iii,iv,v) χρησιμοποιώντας τη συνάρτηση print_node για τα βήματα (i,ii).
• Αλλάξτε το πρόγραμμα σας του μέρους 7.3(b) ώστε να καλεί την search_list (η οποία θα καλεί την print_node). Και πάλι πρέπει να χρησιμοποιήσετε τις συμβάσεις χρήσεις των καταχωρητών μεταξύ των ρουτινών και του προγράμματος που τις καλεί. Επίσης η κάθε ρουτίνα θα πρέπει να έχει το δικό της stack frame.
• Τελικά το συνολικό πρόγραμμα σας θα πρέπει να έχει μια main που αποτελείται απο δύο μέρη: Το πρώτο μέρος της θα υλοποιεί το 7.3(a) με χρήση της node_alloc και read_int, ενώ το δεύτερο θα υλοποιεί το 7.3(b) με χρήση των read_int, search_list, και print_node.

Τρόπος Παράδοσης: Παραδώστε ηλεκτρονικά τον κώδικά σας, "ask7.s", κι ένα στιγμιότυπο της εκτέλεσής του στον SPIM, "ask7.jpg". Επίσης, θα εξεταστείτε προφορικά σε αυτή την άσκηση. Βάλτε τα δύο παραπάνω αρχεία στο αρχείο "ask7.zip", και στη συνέχεια εκτελέστε, από το directory όπου βρίσκεται αυτό το αρχείο: "~hy225/bin/submit 7", δηλαδή συνολικά:

        zip ask7.zip   ask7.s ask7.jpg
        ~hy225/bin/submit 7 

---

[Up - Table of Contents] [Prev - 6. Procedure Call]

[printer version - PDF] [8. Verilog Intro. 1 - Next]

---

Up to the Home Page of CS-225

© copyright University of Crete, Greece. Last updated: 29 Mar. 2007, by M. Katevenis.