Λειτουργικά Συστήματα (ΗΥ-345)
Χειμερινό Εξάμηνο 2011
Ασκηση 4η



Παράδοση: 16/12

Χρονοπρογραμματισμός Διεργασιών στο Minix με τον Αλγόριθμο Πολλαπλών Ουρών


Ο σκοπός αυτής της άσκησης είναι να εξοικειωθείτε με τις έννοιες και την υλοποίηση του χρονοπρογραμματισμού διεργασιών. Για το σκοπό αυτό θα αλλάξετε και θα επεκτείνετε τον κυκλικό (round-robin) αλγόριθμο χρονοπρογραμματισμού διεργασιών του ΜΙΝΙΧ στον αλγόριθμο πολλαπλών ουρών (multiple feedback queue scheduling algorithm), ο οποίος δίνει προτεραιότητα σε σύντομες διεργασίες και σε διεργασίες που κάνουν συχνά block για Είσοδο/Έξοδο (αλληλεπιδραστικές διεργασίες) έναντι των υπολογιστικά φραγμένων διεργασιών.

Χρονοπρογραμματισμός διεργασιών στο Minix

Ο χρονοπρογραμματιστής του ΜΙΝΙΧ διατηρεί τρεις ουρές : TASK_Q, SERVER_Q και USER_Q. Η TASK_Q έχει την υψηλότερη προτεραιότητα, ενώ η USER_Q έχει την χαμηλότερη. Τα tasks στην ουρά TASK_Q και οι servers στην ουρά SERVER_Q είναι non-preemptable, ενώ οι διεργασίες στην ουρά USER_Q χρονοπρογραμματίζονται χρησιμοποιώντας ένα κυκλικό αλγόριθμο (round - robin) με κβάντο χρόνου ίσο με SCHED_RATE (αρχείο kernel/clock.c, γραμμή 80). Συνεπώς μια διεργασία χρήστη θα χρονοπρογραμματιστεί μόνο εάν δεν υπάρχουν διεργασίες TASK και SERVER.

Ο χρονοπρογραμματιστής δουλεύει κανονικά όπως παρακάτω : Μία διεργασία μπλοκάρει όταν κάνει I/O. Στο ΜΙΝΙΧ αυτό γίνεται όταν μία διεργασία στέλνει (SEND) ή λαμβάνει (RECEIVE) ένα μήνυμα. Έτσι οι διαδικασίες mini_send και mini_rec στο αρχείο proc.c (οι οποίες είναι υπεύθυνες για όλο το πέρασμα μηνυμάτων στο ΜΙΝΙΧ) καλούν τις συναρτήσεις ready() και unready(). Η συνάρτηση unready() μετακινεί μια διεργασία από το ready ή running state σε blocked state. Αντίθετα η συνάρτηση ready() μετακινεί μια διεργασία από το blocked state σε ready state.

Ο χρονοπρογραμματιστής επίσης ενεργοποιείται σε μία διακοπή ρολογιού (clock interrupt). Εξήντα φορές το δευτερόλεπτο, δημιουργείται ένα hardware interrupt από το ρολόι του συστήματος, και καλείται η συνάρτηση clock_handler() που περιέχεται στο αρχείο clock.c. Αν υπάρχει δουλειά χρονοπρογραμματισμού, η clock_handler() στέλνει ένα μήνυμα (μέσω της κλήσης του "interrupt (CLOCK)", γραμμή 530) στο task του ρολογιού (περιέχεται στο αρχείο clock.c), το οποίο καλεί την do_clocktick(). Αυτή η συνάρτηση καλεί τον χρονοπρογραμματιστή (lock_sched()).

Η συνάρτηση pick_proc() επιλέγει την επόμενη διεργασία που πρέπει να τρέξει, άρα αυτή η συνάρτηση επιλέγει την κατάλληλη ουρά. Επίσης αυτή η συνάρτηση θέτει τον proc_ptr, που διαβάζεται από τον interrupt handler και τον κώδικα του context-switch. Η συνάρτηση lock_sched() καλείται μόνο από την do_clocktick() και μόνο όταν η διεργασία που τρέχει τη στιγμή αυτή έχει εξαντλήσει το κβάντο χρόνου που της διατέθηκε. Αν μία διεργασία μπλοκάρει πριν χρησιμοποιήσει όλο το κβάντο χρόνου της, καλείται η συνάρτηση unready().

Υλοποίηση του αλγορίθμου πολλαπλών ουρών

Σε αυτή την άσκηση θα αλλάξετε τον αλγόριθμο χρονοπρογραμματισμού του Minix για την ουρά USER_Q, από round-robin στον αλγόριθμο πολλαπλών ουρών, ο οποίος θα δίνει προτεραιότητα στις σύντομες διεργασίες και στις διεργασίες που μπλοκάρουν σύχνα για Είσοδο/Έξοδο.
Αυτό θα γινέι ως εξής:
  1. Για καθε διεργασία θα προσθέσετε ενα καινούργιο πεδίο με όνομα priority, που αντιστοιχεί στη προτεραιότητα της διεργασίας. Θα υπάρχουν 5 δυνατές τίμες για αυτό το πεδίο, από 0 (υψηλότερη προτεραιότητα) μέχρι 4 (χαμηλότερη προτεραιότητα).
  2. Αντί για μία ουρά USER_Q θα υπάρχουν 5 ουρές, από USER_Q0 μέχρι USER_Q4 (μία για κάθε προτεραιότητα).
  3. Κάθε νέα διεργασία θα έχει προτεραιότητα 0 (υψηλότερη) και θα προστίθεται στο τέλος της ουράς USER_Q0.
  4. Ο χρονοπρογραμματιστής επιλέγει την επόμενη διεργασία που θα τρέξει από την ουρά USER_Q0 με round-robin σειρά. Αν η ουρά USER_Q0 είναι άδεια, τότε μόνο επιλέγει την επόμενη διεργασία που θα τρέξει από την ουρά USER_Q1, κτλ. Οπότε για να επιλεγεί μια διεργασία με προτεραιότητα 4 από την ουρά USER_Q4 για να τρέξει, θα πρέπει να μην υπάρχουν διεργασίες στις ουρές USER_Q1 - USER_Q3. Από την ουρά υψηλότερης προτεραιότητας που δεν είναι άδεια, ο χρονοπρογραμματιστής επιλέγει με round robin τρόπο την επόμενη διεργασία.
  5. Αν μία διεργασία τελειώσει την εκτέλεση της, αφαιρείται από την αντίστοιχη ουρά (μπορούμε να βρούμε την ουρά με βάση την προτεραιότητα της διεργασίας).
  6. Αν μία διεργασία μπλοκάρει πριν χρησιμοποιήσει όλο το κβάντο χρόνου της (με την συνάρτηση unready()), τότε αφαιρείται από την αντίστοιχη ουρά και η προτεραιότητά της αλλάζει σε 0 (υψηλότερη). Όταν αυτή η διεργασία γίνει ξανά ready, θα μπεί στην ουρά USER_Q0 (με την υψηλότερη προτεραιότητα).
  7. Αν μία διεργασία χρησιμοποιήσει όλο το κβάντο της τότε σταματάει η εκτέλεση της, μειώνετε η προτεραιότητα της στο αμέσως επόμενο επίπεδο (δηλαδή η τιμή του priority αυξάνετε κατά ένα), εκτός αν έχει φτάσει στο κατώτερο επίπεδο (priority 4), και η διεργασία τοποθετείται στο τέλος της επόμενη ουράς (με την αμέσως χαμηλότερη προτεραιότητα, όπως εξηγήσαμε).
  8. Αυτό συνεχίζετε για κάθε διεργασία μέχρι αυτή να τερματίσει ή να φτάσει στο χαμηλότερο επίπεδο προτεραιότητας. Εκτός αν γίνει unready, οπότε θα βρεθεί ξανά στην ουρά υψηλότερης προτεραιότητας.

Λεπτομέρειες Υλοποίησης:

  1. Για κάθε διεργασία θα χρειαστεί να κρατάτε την προτεραιότητά της (πεδίο priority), που υποδυκνύει και σε ποιά ουρά βρίσκετε ή πρέπει να εισαχθεί η διεργασία.
  2. Σε κάθε ουρά USER_Q0 - USER_Q4 θα έχετε στην αρχή την επόμενη διεργασία από την ουρά που πρέπει να εκτελεστεί (ή εκτελείται την συγκεκριμένη χρονική στιγμή) και στο τέλος την διεργασία που είτε έτρεξε πιο πρόσφατα είτε προστέθηκε πιο πρόσφατα στην ουρά.
  3. Μία διεργασία μπορεί να σταματήσει να τρέχει για δυο λόγους: αν μπλοκάρει (unredy) ή αν τελειώσει το κβάντο της. Στην πρώτη περίπτωση της δίνουμε την υψηλότερη προτεραιότητα για την επόμενη εκτέλεσή της, ενώ στην δεύτερη περίπτωση μειώνουμε την προτεραιότητά της κατά ένα. Με αυτό τον τρόπο εξασφαλίζουμε ότι οι διεργασίες που κάνουν είσοδο/έξοδο έχουν υψηλότερη προτεραιότητα από της διεργασίες που χρησιμοποιούν για μεγάλα χρονικά διαστήματα την CPU.
Τα αρχεία που χρειάζεται να διαβάσετε ή/και να αλλάξετε για να υλοποιήσετε τα ζητούμενα της άσκησης φαίνονται στον παρακάτω πίνακα:


clock.c Το task του ρολογιού. Καλεί τον χρονοπρογραμματιστή (lock_sched()) κάθε 6 clock ticks.
proc.c Περιέχει τον κώδικα του χρονοπρογραμματιστή (sched(), pic_proc(), ready(), unready()).
proc.h Ο Πίνακας διεργασιών του ΜΙΝΙΧ.
system.c Αρχικοποίηση διεργασίας

Υλοποποίηση system call getpriority

Παρόμοια με την προηγούμενη άσκηση, δημιουργήστε ένα καινούργιο system call getpriority() το οποίο θα επιστρέφει το priority της τρέχουσας διεργασίας. Το system call αυτό θα πρέπει να φτάνει στο επίπεδο του πυρήνα, να εντοπίζει στον process table το pid της τρέχουσας διεργασίας, να βρίσκει το πεδίο priority για αυτήν την διεργασία και να το επιστρέφει στον χρήστη.

Έλεγχος των αλλαγών

Για να μπορέσετε να δοκιμάσετε αν τρέχουν σωστά οι αλλαγές που κάνατε στον χρονοπρογραμματιστή του ΜΙΝΙΧ θα χρειαστεί να τρέξετε τα test προγράμματα primes.c και mulod.c τα οποία δίνονται παρακάτω και να δείτε τις διαφορές που έχει ο δικός σας χρονοπρογραμμάτιστης από τον αρχικό χρονοπρογραμματιστή του Minix. Μπροείτε να κατεβάσετε από εδώ τα δύο test προγράμματα:
primes.c
mulod.c

Το πρόγραμμα primes.c κάνει πολλούς υπολογισμούς προσπαθώντας να βρει πρώτους αριθμούς, ενώ το πρόγραμμα mulod.c διαβάζει αρχεία από το δίσκο και τα γράφει στο /dev/null. Για να δείτε τις διαφορές σας προτείνουμε να τρέξετε από 1 μέχρι 5 φόρες στο background το πρόγραμμα primes (./primes &) και στη συνέχεια να τρέξετε την εντολή “time ./mulod” που θα σας δώσει το πραγματικό χρόνο που έτρεξε το πρόγραμμά αυτό (π.χ. 4.00 real 3.71 user 0.58 sys). Δοκιμάστε τη μέτρηση αυτή αρκετές φόρες και για διαφορετικό αριθμό από ταυτόχρονα primes προγράμματα και δώστε στην αναφορά σας ένα μέσο αποτέλεσμα (π.χ. Το μέσο πραγματικό χρόνο από 10 διαφορετικές δοκιμές του time ./mulod με 5 ταυτόχρονες εκτελέσεις της ./prime) για τον αρχικό αλγόριθμο χρονοπρογραμματισμού του Minix και για τον δικό σας αλγόριθμο χρονοπρογραμματισμού με πολλαπλές ουρές.

Μπορείτε να δοκιμάσετε και το αντίστροφο, δηλαδή να τρέξετε αρκετές φορές το πρόγραμμα mulod και να μετρήστε με time ./primes τον χρόνο εκτέλεσης του προγράμματος primes, ανάλογα με τον αριθμό των muload που τρέχουν ταυτόχρονα και ανάλογα με τον αλγόριθμο χρονοπρογραμματισμού που χρησιμοποιέιται.

Επίσης, θα πρέπει να εκτυπώνετε περιοδικά (π.χ. κάθε ένα δευτερόλεπτο) το priority της κάθε διεργασίας για τα test προγράμματα primes και mulod, χρησιμοποιώντας το system call getpriority. Έτσι θα πρέπει να παρατηρήσετε ότι το muload (που μπλοκάρει συχνά για είσοδο/έξοδο) έχει υψηλότερη προτεραιότητα από το primes (που είναι cpu bound). Το mulod θα πρέπει να έχει συνήθως προτεραιότητα 0, ενώ στο primes θα πρέπει να βλέπουμε την προτεραιότητα να πέφτει μέχρι να φτάνει στην χαμηλότερη προτεραιότητα 4. To primes θα πρέπει να τρέχει μόνο όταν το mulod (που βρίσκετε σε ουρά υψηλότερης προτεραιότητας) είναι μπλοκαρισμένο για είσοδο/έξοδο.

Emulators

Για να τρέξετε το minix πάνω από τα linux μηχανήματα θα χρησιμοποιήσετε τον emulator QEMU ή τον emulator bochs. Αυτοί οι emulators είναι εγκατεστημένοι στα linux μηχανήματα που υπάρχουν στα εργαστήρια του τμήματος. Ή μπορείτε να τους εγκαταστήσετε σε δικό σας μηχάνημα. Για να τρέξετε το λειτουργικό σύστημα Μinix με τo QEMU ή το bochs θα πρέπει πρώτα να αντιγράψετε το κατάλληλο αρχέιο με το image του Minix απο την περιοχή του μαθήματος σε ένα δικό σας directory και στη συνέχεια να το φορτώσετε με τον emulator. Έπειτα θα τροποποιήσετε τα κατάλληλα αρχεία στον source κώδικα του minix, ώστε να υλοποιήσετε τον καινούργιο αλγόριθμο χρονοπρογραμματισμού, και θα αρχίσετε ξανά το minix με τις δικές σας αλλαγές ώστε να βεβαιωθείτε οτι δουλεύουν. Για αυτό τον λόγο απαιτείται στην άσκηση να τρέξετε κάποια test προγράμματα. Τέλος, θα παραδώσετε το αρχείο minix.img που είναι το image του δικού σας "τροποποιημένου" minix που θα μπορούμε να φορτόσουμε στον emulator. Περισσότερες και πιο αναλυτικές οδηγίες για το πώς θα τρέχετε το minix χρησιμοποιώντας το QEMU, και πως κάνετε αλλαγές σε αυτό, μπορείτε να βρείτε εδώ . Οι αντίστοιχες οδηγίες για τον emulation bochs είναι εδώ .

Παρατηρήσεις

  1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας και το λογαριασμό σας (account) σε όλα τα αρχεία.
  2. Για δική σας ευκολία (για να ξέρετε σε ποιό σημείο έχετε αλλάξει κώδικα μέσα στα αρχεία του πυρήνα του ΜΙΝΙΧ), χρησιμοποιείστε σχόλια πριν και μετά τις αλλαγές σας και/ή εντολές του τύπου :
    #ifdef ... ή #if ...
    ... νέος κώδικας ...
    #else
    ... παλιός κώδικας ...
    #endif
  3. Γράψτε ένα αρχείο README, στο οποιό θα δίνετε πληροφορίες για την υλοποίηση σας καθώς και τα αποτελέσματα από την ανάλυση του συστήματος που κάνατε με τα προγράμματα primes.c και mulod.c.
  4. Κατασκευάστε τον κατάλογο assign4 που θα περιέχει το README και το minix.img της άσκησης 4. Παραδώστε το παραπάνω αρχείο χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε submit assignment_4@hy345 assign4 από τον κατάλογο που περιέχει τον assign4).
  5. Σε πολλές περιπτώσεις τα ονόματα των αρχείων είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.