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



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


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

Περιγραφή

Ο χρονοπρογραμματιστής του Μinix διατηρεί τρεις ουρές διεργασιών: TASK_Q, SERVER_Q και USER_Q. Η TASK_Q έχει την υψηλότερη προτεραιότητα, ενώ η USER_Q έχει την χαμηλότερη. Τα tasks στην ουρά TASK_Q και οι servers στην ουρά SERVER_Q είναι non-preemptive, ενώ οι διεργασίες στην ουρά USER_Q χρονοπρογραμματίζονται χρησιμοποιώντας ένα κυκλικό αλγόριθμο (round-robin).

Σε αυτή την άσκηση θα αλλάξετε τον κυκλικό αλγόριθμο για τις διεργασίες του χρήστη (USER_Q) σε έναν αλγόριθμο χρονοπρογραμματισμού με λοταρία. Για να το πετύχετε αυτό θα πρέπει να ακολουθήσετε τα εξής βήματα:
  1. Να υλοποιήσετε το system call set_lottery_tickets το οποίο περιφγράφεται παρακάτω
  2. Να τροποποιήσετε την δημιουργία και διαγραφή των διεργασιών έτσι ώστε να ενημερώνουν τον συνολικό αριθμό των tickets που έχουν ανατεθεί
  3. Να τροποποιήσετε την συνάρτηση fork έτσι ώστε να αποτυγχάνει αν το σύστημα δεν έχει τον κατάλληλο αριθμό από tickets να αναθέσει
  4. Να υλοποιήσετε την παραλλαγή του αλγορίθμου lottery scheduling που περιγράφεται παρακάτω
Οι ουρές TASK_Q και SERVER_Q θα παραμείνουν ίδιες.

Σχετικά με το system call set_lottery_tickets( PID, tickets )

Το system call set_lottery_tickets( PID, tickets ) πρέπει να αναθέτει ένα συνολικό ποσό από tickets σε μια διεργασία, όχι να προσθέτει το ποσό αυτό στον αριθμό τον tickets που είναι ήδη assigned στην διεργασία. Για παράδειγμα αν η διεργασία με pid 4 έχει 20 tickets και κάνουμε αυτή την κλήση set_lottery_tickets( 4, 10 ), η διεργασία 4 πρέπει να καταλήξει να έχει 10 tickets.

Επίσης, το sytem call set_lottery_tickets( PID, tickets ) πρέπει να επιστρέφει τον αριθμό των tickets που έχουν ανατέθηκαν στη διεργασία, ακόμα και αν είναι λιγότερα από αυτά που ζητήσαμε με το όρισμα tickets (επειδή το σύστημα δεν είχε άλλα να δώσει). Ας υποθέσουμε ότι η διεργασία 4 έχει 10 tickets, και ο μέγιστος αριθμός των tickets έχει ήδη ανατεθεί. Τότε η set_lottery_tickets( 4, 10 ) πρέπει να επιστρέψει 10, επειδή 10 tickets μπορούν να ανατεθούν στην διεργασία 4 (αφού η διεργασία 4 έχει ήδη 10 δεσμευμένα για αυτήν). Παρόλα αυτά η fork() πρέπει να επιστρέψει -1 αφού δεν υπάρχουν επιπρόσθετα tickets στο σύστημα για μια νέα διεργασία.

Προσοχή με το πως ονομάζετε τις παραμέτρους στις συναρτήσεις σας. Π.χ. το pid είναι ορισμένο στο /usr/src/mm/param.h και το PID είναι ορισμένο στο /usr/minix/com.h

Δημιουργία και Διαγραφή διεργασιών

Πρέπει να τροποποιήσετε την δημιουργία (fork) και τη διαγραφή (kill, exit) μιας διεργασίας έτσι ώστε να λαμβάνουν υπόψιν τους τον αριθμό των tickets που έχουν ανατεθεί από το σύστημα. Αν συνεχώς υπολογίζετε τον αριθμό των tickets που έχουν ανατεθεί αντί να κρατάτε κάποια global variable, δεν θα πρέπει να ανησυχείτε για τη διαγραφή των διεργασιών. Στην αντίθετη περίπτωση, όταν μία διεργασία πεθαίνει θα πρέπει να αφαιρούνται τα tickets της από τον αριθμό των ανατιθέμενων tickets.

Σχετικά με την δημιουργία των διεργασιών πρέπει να γίνονται 2 πράγματα. Πρώτον, πρέπει να αποφασίσετε αν η fork θα αποτύχει βασιζόμενοι στον αριθμό των tickets που έχουν ανατεθεί απ' το σύστημα. Αν δεν υπάρχουν tickets προς ανάθεση, η fork πρέπει να επιστρέφει -1. Θα πρέπει να γίνεται αυτός ο έλεγχος πριν δεσμευτεί μνήμη για τη νέα διεργασία. Δεύτερον, πρέπει να αρχικοποιήσετε τον αριθμό των tickets για μία καινούργια διεργασία να είναι 1. Αυτό μπορείτε να το κάνετε στο σημείο που η fork() αρχικοποιεί το child pid. (Αν ανησυχείτε για το πως θα αρχικοποιήσετε τον αριθμό των tickets για την init, θυμηθείτε ότι η init δεν είναι αποτέλεσμα μιας fork(), μιας και είναι η πρώτη (initial) user διεργασία. Hint: Κοιτάξτε στο /usr/src/kernel/main.c)

Αλγόριθμος χρονοπρογραμματισμού με Λοταρία

Ο αλγόριθμος χρονοπρογραμματισμού που θα υλοποιήσετε είναι μια παραλαγή του lottery sceduling algorithm που περιγράφεται στο βιβλίο σας, στην σελίδα 194 (K.2§5.3). Ο αλγόριθμος που πρέπει να υλοποιήσετε εσείς περιγράφεται εδώ:

Υποθέστε ότι έχουμε την ακόλουθη ουρά με τα ready processes, όπου ο bold αριθμός στην κορυφή είναι το pid και ο μπλε αριθμός κάτω έιναι ο αριθμός των tickets που έχει μια διεργασία:



Για να χρονοπρογραμματιστεί η επόμενη διεργασία χρησιμοποιώντας lottery scheduling, πρέπει πρώτα να επιλέξουμε έναν τυχαίο αριθμό. Σε αυτό το παράδειγμα ο συνολικός αριθμός εισιτηρίων που έχουν ανατεθεί στις ready διεργασίες είναι 36. Επομένως επιλέγουμε έναν τυχαίο αριθμό ανάμεσα στο 1 και το 36. Ξεκινώντας από την αρχή της ουράς, συναθροίζουμε τον αριθμό των tickets που έχουν ανατεθεί σε κάθε process μέχρι ο αριθμός αυτός να είναι μεγαλύτερος ή ίσος από τον τυχαίο αριθμό που έχουμε επιλέξει.

Έστω ότι ο τυχαίος μας αριθμός είναι ο 14. Μετράμε τα tickets ένα ένα από κάθε διεργασία στην ουρά μέχρι το άθροισμα να είναι μεγαλύτερο ή ίσο με το 12. Δηλαδή αθροίζουμε τα tickets των 1, 4 ,7 και 12 αφού προκύπτει η τιμή 1 + 1 + 10 + 4 >= 14. Αφού η τιμή έγινε μεγαλύτερη ή ίση του τυχαίου αριθμού μας όταν φτάσαμε την διεργασία με pid 12, επιλέγουμε την process 12 σαν επόμενη για να τρέξει.

Τώρα έστω ότι πρέπει να πάρουμε μια νέα απόφαση χρονοπρογραμματισμού και ο τυχαίος αριθμός μας είναι ο 4. Χρησιμοποιώντας την υλοποίηση που περιγράψαμε παραπάνω η διεργασία 7 θα επιλεγόταν σαν επόμενη για να τρέξει. Η ακόλουθη εικόνα παρέχει το εύρος των αριθμών που επιτρέπουν σε μια συγκεκριμένη διαδικασία να τρέξει:



Για παράδειγμα, η διεργασία 12 θα τρέξει όποτε ο τυχαίος αριθμός μας είναι ανάμεσα στο 13 και το 16. Η διεργασία 4 θα τρέξει μόνο όταν ο τυχαίος αριθμός είναι ίσος με 2.

Ανάθεση των tickets

Όταν παίρνετε την απόφαση για το αν περισσότερα tickets πρέπει να ανατεθούν σε κάποια διεργασία, πρέπει να γίνεται σύγκριση μεταξύ μίας μεταβλητής num_assigned με μια σταθερά (constant) MAX_TICKETS την οποία θα πρέπει να ορίσετε 256. Η num_assigned πρέπει να περιέχει τον αριθμό των εισιτηρίων για όλες τις user διεργασίες (ανεξαρτήτως κατάστασης: ready ή wait state). Επίσης, η σταθερά MAX_TICKETS θα πρέπει να γίνει define σε κατάλληλο μέρος έτσι ώστε και ο kernel και οι servers (MM,FS) να έχουν πρόσβαση σε αυτή τη σταθερά.

lottery scheduling

Ο χρονοπρογραμματισμός πρέπει να εφαρμόζεται μόνο σε user διεργασίες που είναι σε ready state. Όταν επιλέγεται ένας νέος αριθμός πρέπει να είναι μεταξύ του 1 και του max, όπου max ο συνολικός αριθμός των tickets που έχουν ανατεθεί σε ready διεργασίες. Δεν πρέπει να περιλαμβάνεται ο αριθμός των tickets από διεργασίες που είναι σε wait ή σε non-ready state στον υπολογισμό του max.

Υπολογισμός των συνολικών ανατιθέμενων tickets

Θα χρειαστείτε να υπολογίσετε πόσα tickets έχουν ανατεθεί σε πολλά μέρη αυτής της άσκησης. Θα ήταν χρήσιμο να υλοποιήσετε ένα system call get_total_tickets με τον ίδιο τρόπο όπως το set_lottery_tickets, που θα επιστρέφει τον συνολικό αριθμό των tickets που έχουν ανατεθεί από το σύστημα. Ωστόσο θα πρέπει να προσέξετε τι διεργασίες να συμπεριλάβετε. Όταν θέλετε να καθορίσετε αν η fork() θα αποτύχει, πρέπει να υπολογίσετε τον αριθμό των tickets για όλες τις user διεργασίες (ακόμα και για αυτές που δεν είναι σε ready state). Όταν κάνετε lottery scheduling, θα πρέπει να υπολογίσετε τον αριθμό των tickets για τις ready διεργασίες μόνο. Η υλοποίηση αυτού του system call δεν αποτελεί κομμάτι της άσκησης και δεν θα βαθμολογηθείτε για αυτό.

Looping στις διεργασίες

Όταν θα πρέπει να ψάξετε για ένα process pid, να μετρήσετε tickets, κτλ., θα πρέπει να διατρέξετε μία μία τις διεργασίες. Για να το κάνετε αυτό θα χρειαστεί να χρησιμοποιήσετε pointers. Για να κάνετε loop στις ready διεργασίες, μπορείτε να χρησιμοποιήσετε το rdy_head[USER_Q] και το attribute p_nextready. Μπορείτε να δείτε τα αρχεία proc.h και proc.c για περισσότερες λεπτομέρειες.

Για να τεστάρετε την set_lottery_tickets, το αν η fork() αποτυγχάνει όταν ο μέγιστος αριθμός εισιτηρίων έχει γίνει assigned και για να σιγουρευτείτε ότι τα tickets ανακτώνται από το σύστημα όταν μια διεργασία πεθαίνει μπορείτε να χρησιμοποιήσετε το παρακάτω test πρόγραμμα: test.c

Hints

  1. Στην άσκηση αυτή θα σας βοηθήσει πολύ η εντολή του UNIX grep. Επίσης, αν χρησιμοποιείτε τον vim editor, θα σας φανεί πολύ χρήσιμο και το πρόγραμμα ctags. Χρησιμοποιήστε την εντολή man από το shell για να μάθετε πως ακριβώς λειτουργεί κάθε εντολή.
  2. Για δική σας ευκολία (για να ξέρετε σε ποιό σημείο έχετε αλλάξει κώδικα μέσα στα αρχεία του Μinix), χρησιμοποιείστε σχόλια πριν και μετά τις αλλαγές σας και/ή εντολές του τύπου :
    #ifdef ... ή #if ...
    ... νέος κώδικας ...
    #else
    ... παλιός κώδικας ...
    #endif
  3. Μερικά από τα αρχεία στα οποία ίσως χρειαστεί να επέμβετε ή ακόμα και να δημιουργήσετε οι ίδιοι είναι τα παρακάτω:
    /src/kernel/const.h
    /src/kernel/proc.c
    /src/kernel/proc.h
    /src/kernel/main.c
    /src/kernel/system.c

Σημείωση

Επειδή πολλές φορές το ΜΙΝΙΧ μπορεί να μην τερματίζει κανονικά φροντίστε να σκοτώνετε τις διεργασίες που μένουν. Η εντολή ps -u $user θα σας δείξει όλες τις διεργασίες σας που τρέχουν στο συγκεκριμένο μηχάνημα. Αν κάποιες από αυτές αναφέρονται στην εντολή 'minix' τότε τερματίστε τις με την εντολή kill -9 pid_number όπου pid_number είναι το PID της διεργασίας που τρέχει το Minix. Για παράδειγμα:

> ps -u $user
PID TTY TIME CMD
3010 pts/15 0:01 tcsh
3855 pts/15 0:04 minix
3922 pts/17 0:01 tcsh
> kill -9 3855

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

  1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας, τον αριθμό μητρώου σας, και το username σας σε όλα τα αρχεία. Μην παραδώσετε εκτυπώσεις των προγραμμάτων.
  2. Γράψτε ένα αρχείο README, το πολύ 30 γραμμών, με επεξηγήσεις για τον τρόπο υλοποίησης των system calls.
  3. Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε πληκτρολογώντας make all να γίνεται η μεταγλώττιση (compilation) του προγράμματος και να παράγεται το εκτελέσιμο αρχείο. Επίσης πληκτρολογώντας make clean να καθαρίζονται όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που χρειάζονται για τη μεταγλώττιση.
  4. Σε πολλές περιπτώσεις τα ονόματα των αρχείων είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.