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



Χρονοπρογραμματισμός Διεργασιών στο ΜΙΝΙΧ


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

Περιγραφή

Ο χρονοπρογραμματιστής του ΜΙΝΙΧ διατηρεί τρεις ουρές : 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 από το ρολόι του συστήματος, και καλείται η συνάρτηση p;lock_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().

Σε αυτή την άσκηση θα αλλάξετε το χρονοπρογραμματιση έτσι ώστε να δίνει προτεραιότητα στις διεργασίες που μπλοκάρουν σύχνα για Είσοδο/Έξοδο.
Αυτό θα γινέι ως εξής:
  1. Χωρίζουμε το χρόνο σε διαστήματα των 5 δευτερολέπτων.
  2. Σε κάθε διάστημα κρατάμε τον αριθμό των clock ticks για τα οποία έτρεξε η διέργασία αυτή.
  3. Η επόμενη διεργασία που θα διαλέξει ο χρονοπρογραμματιστής μας θα είναι αυτή που έτρεξε τα λιγότερα clock ticks κατά το τρέχον διαστημα.

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

  1. Θα χρειαστεί να ορίσετε μια μεταβλητή που θα κρατάει το τρέχον διάστημα, καθώς και μια που θα κρατάει το δευτερόλεπτο στο οποίο ξεκίνησε το διάστημα αυτό. Το τρέχον δευτερόλεπτο μπορείτε να το πάρετε συνδυάζοντας τις τιμές boot_time και realtime από το αρχείο clock.c ως: time_t secnow = boot_time + realtime/HZ
  2. Για κάθε διεργασία θα χρειαστεί να κρατάτε τον αριθμό του διαστήματος που έτρεξε για τελευταία φορα και τον αριθμό των clock ticks που κατανάλωσε στο διάστημα αυτό. (δείτε τη συνάρτηση clock_handler στο αρχείο clock.c για να δείτε πως μπορείτε να πάρετε τα clockticks που κατανάλωσε μια διεργασία).
  3. Προτείνουμε να υλοποιήσετε μία ταξινόμηση της USER_Q, έτσι ώστε η διεργασία που κατανάλωσε τα λιγότερα clock ticks στο τρέχον διάστημα να είναι πρώτη στη λίστα, άρα και αυτή που θα επιλεγεί για να τρέξει από τον χρονοπρογραμματιστή. Η ταξινόμηση θα γίνετε κάθε φορά που θα καλούνται οι συναρτήσεις sched() και ready(). Δηλαδή, κάθε φορά που η τρέχουσα διεργασία τελείωσε το κβαντο της και ο χρονοπρογραμματιστης ετοιμάζετε να διαλέξει την επόμενη διεργασία και κάθε φορά που μία διεργασία περνάει από τη κατάσταση unready σε ready.
Τα αρχεία που χρειάζεται να διαβάσετε ή/και να αλλάξετε για να υλοποιήσετε τα ζητούμενα της άσκησης φαίνονται στον παρακάτω πίνακα:


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

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

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

  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. Σε πολλές περιπτώσεις τα ονόματα των αρχείων είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.