HY-345 Λειτουργικά Συστήματα


ΑΣΚΗΣΗ 4η

Φθινόπωρο 2008

Υλοποίηση Ουρών Προτεραιότητας στο ΜΙΝΙΧ


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

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

Σε αυτή την άσκηση θα αντικαταστήσετε τον κυκλικό αλγόριθμο με ένα Χρονοπρογραμματιστή Προτεραιοτήτων. Αυτό θα γίνει ως εξής : η ουρά USER_Q θα χωριστεί σε τέσσερις λογικές ουρές, κάθε μία από τις οποίες θα αποτελεί μία διαφορετική ουρά προτεραιοτήτων. Κάθε ουρά προτεραιοτήτων θα έχει μία τιμή προτεραιότητας, από 0 η πρώτη (υψηλότερη προτεραιότητα) μέχρι 3 που θα έχει η τέταρτη (χαμηλότερη προτεραιότητα). Όταν ο χρονοπρογραμματιστής του ΜΙΝΙΧ πρέπει να επιλέξει μία διεργασία από την ουρά USER_Q, θα επιλέγει πρώτα αυτήν που θα έχει την υψηλότερη προτεραιότητα, ενώ οι διεργασίες που έχουν χαμηλότερη προτεραιότητα από αυτήν δεν θα τρέχουν.

Οι ουρές TASK_Q και SERVER_Q θα παραμείνουν ίδιες. Προτείνουμε να χρησιμοποιήσετε μια διπλά συνδεδεμένη λίστα ταξινομημένη κατά την κλάση προτεραιότητας για να υλοποιήσετε τις τέσσερις λογικές ουρές.

Για τις διεργασίες που ανήκουν στην ίδια ουρά προτεραιοτήτων, θα χρησιμοποιείται ο κυκλικός αλγόριθμος (round-robin) με κβάντο χρόνου όπως στον παρακάτω πίνακα
(Table 1):

Ουρά

Καθορισμός κβάντου

0

Χρήση του συνηθισμένου κβάντου SCHED_RATE (6 clock ticks, 100ms)

1

Χρήση κβάντου διπλάσιου (x 2) από αυτό της ουράς 0.

2

Χρήση κβάντου τετραπλάσιου (x 4) από αυτό της ουράς 0.

3

Χρήση κβάντου οκταπλάσιου (x 8) από αυτό της ουράς 0.

 

Table 1: Καθορισμός προτεραιοτήτων μέσα στην ίδια ουρά.

Η ουρά προτεραιότητας μιας διεργασίας αλλάζει δυναμικά με τον παρακάτω αλγόριθμο. Κάθε διεργασία ξεκινάει με προτεραιότητα 0 στην ουρά 0. Αν χρησιμοποιήσει όλο το κβάντο χρόνου που της δίνεται, μετακινείται στο τέλος της ουράς 1. Αν δε χρησιμοποιήσει το κβάντο της, τότε μένει στο τέλος της ουράς 0. Το ίδιο συμβαίνει σε όλες τις ουρές, επειδή σε διαφορετική περίπτωση οι διεργασίες στις ουρές 1, 2, και 3 μένουν μπλοκαρισμένες.

Έτσι, σε κάθε ουρά (εκτός της 0) μετακινούμε τις διεργασίες που δεν χρησιμοποίησαν όλο το χρόνο τους (2, 4 και 8 κβάντα αντίστοιχα) στο τέλος της ουράς που βρίσκεται από πάνω (αυτές της 1 στην 0, της 2 στην 1, κ.ο.κ). Αν αντίθετα χρησιμοποίησαν όλο το χρόνο τους, τις μετακινούμε στο τέλος της ουράς που βρίσκεται προς τα κάτω (εκτός από αυτές που είναι ήδη στην ουρά 3).

Όπως ίσως παρατηρείτε στον παραπάνω αλγόριθμο, οι διεργασίες που έχουν πολλούς υπολογισμούς (computation-bound processes) θα καταλήξουν στην ουρά 3 και πιθανόν να μην τρέχουν όσο χρόνο πρέπει. Για να απλοποιήσουμε το πρόβλημα δεν θα ασχοληθούμε το πρόβλημα του starvation.

Ο χρονοπρογραμματιστής (sched() και pick_proc()) δίνει προτεραιότητα σε tasks και servers. Aν δεν υπάρχουν tasks ή servers για να τρέξουν επιλέγει μια διεργασία χρήστη. Ο δικός σας χρονοπρογραμματιστής θα επιλέγει την διεργασία χρήστη από την κατάλληλη ουρά. Το κβάντο σε κάθε ουρά μπορεί να προσoμοιωθεί με το να δίνουμε περισσότερα κβάντα στις διεργασίες που έχουν υψηλή προτεραιότητα, χωρίς να αλλάζουμε το βασικό SCHED_RATE. Έτσι, τα κβάντα χρόνου των ουρών 1, 2 και 3 είναι κατάλληλα κατασκευασμένα ώστε να είναι πολλαπλάσια του βασικού κβάντου των 6 clock ticks, το οποίο σημαίνει ότι ο χρονοπρογραμματιστής σας θα τρέχει κάθε 6 clock ticks.

Τα αρχεία που χρειάζεται να διαβάσετε ή/και να αλλάξετε για να υλοποιήσετε τα ζητούμενα της άσκησης φαίνονται στον παρακάτω πίνακα:

clock.c

Το task του ρολογιού. Καλεί τον χρονοπρογραμματιστή

 

(lock_sched()) κάθε 6 clock ticks.

proc.c

Περιέχει τον κώδικα του χρονοπρογραμματιστή

 

(sched(), pic_proc(), ready(), unready()).

proc.h

Ο Πίνακας διεργασιών του ΜΙΝΙΧ.

const.h

Δηλώσεις του λειτουργικού συστήματος.

 

Table 2: Αρχεία προς αλλαγή.

Ο χρονοπρογραμματιστής δουλεύει κανονικά όπως παρακάτω : Μία διεργασία μπλοκάρει όταν κάνει 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()).

Γενικά όποια συνάρτηση χρησιμοποιεί την ουρά USER_Q χρειάζεται αλλαγές. Αυτό περιλαμβάνει τις συναρτήσεις : pick_proc(), ready(), unready(),sched(), do_clocktick()  και clock_handler(). Οι τέσσερις πρώτες είναι στο αρχείο proc.c και οι δύο τελευταίες είναι στο clock.c. Μην αλλάξετε την σταθερά NQ, στο αρχείο const.h, για να προσθέσετε νέες ουρές - η σταθερά αυτή περιέχει τον αριθμό των ουρών TASK_Q, SERVER_Q και USER_Q (δηλαδή 3) και πρέπει να μείνει η ίδια. Απλά κρατήστε τη μία ουρά χρήστη (user queue) ταξινομημένη κατάλληλα, σαν να υπήρχαν οι τέσσερις λογικές ουρές που περιγράφουμε παραπάνω. Οι διεργασίες δεν βγαίνουν από την ready queue, αλλά αντίθετα η διεργασία που τρέχει κάθε στιγμή βρίσκεται στην κορυφή της ready queue. Οι ουρές είναι συνδεδεμένες λίστες αλλά όχι με δυναμική μνήμη. Αντίθετα είναι απλά δείκτες κορυφής (head pointer) και τέλους (tail pointer) σε πεδία του πίνακα διεργασιών.

Θα χρειαστεί επίσης να προσθέσετε έναν ακέραιο στη δομή του πίνακα διεργασιών (process table) στο αρχείο proc.h που θα αποθηκεύει την προτεραιότητα της διεργασίας και ίσως χρειαστείτε άλλο ένα ακέραιο για να αποθηκεύετε τον αριθμό των κβάντων χρόνου που χρησιμοποίησε κάθε διεργασία.

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

Για να μπορέσετε να δοκιμάσετε αν τρέχουν σωστά οι αλλαγές που κάνατε στον χρονοπρογραμματιστή του ΜΙΝΙΧ (και να εξεταστείτε σε αυτες) θα χρειαστεί να φτιάξετε :

  1. Ένα πρόγραμμα χρήστη που θα τυπώνει περιοδικά (π.χ. κάθε δευτερόλεπτο) την ουρά του χρήστη με τις διεργασίες, τις προτεραιότητες και τα υπόλοιπα κβάντα κάθε μιας. Η εμπειρία της άσκησης 3 με τον πίνακα διεργασιών θα σας φανεί πολύτιμη.
  2. Ένα απλό πρόγραμμα χρήστη που θα δημιουργεί ένα αριθμό από διεργασίες που θα τρέχουν για κάποια ώρα ώστε να μπορείτε να τις παρακολουθείτε μέσα στις ουρές.




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

  1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας και το λογαριασμό σας (account) σε όλα τα αρχεία.
  2. Για δική σας ευκολία (για να ξέρετε σε ποιό σημείο έχετε αλλάξει κώδικα μέσα στα αρχεία του πυρήνα του ΜΙΝΙΧ), χρησιμοποιείστε σχόλια πριν και μετά τις αλλαγές σας και/ή εντολές του τύπου :
    #ifdef ... ή #if ...
    ... νέος κώδικας ...
    #else
    ... παλιός κώδικας ...
    #endif
  3. Γράψτε ένα αρχείο README, το πολύ 30 γραμμών, με επεξηγήσεις για τον τρόπο υλοποίησης των system calls.
  4.  Κατασκευάστε το αρχείο assign4.tar.gz που θα περιέχει τo README και το αρχείο minix.img, το οποίο είναι το image του minix που φορτώνεται από το bochs. Xρησιμοποιείστε την εντολή tar και για συμπίεση το πρόγραμμα gzip). Παραδώστε το παραπάνω αρχείο χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε ~hy345/bin/submit 4 από το directory που περιέχει το αρχείο assign4.tar.gz).
  5. Σε πολλές περιπτώσεις τα ονόματα των αρχείων είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.