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

Φροντιστήριο: 28/11/2014
Παράδοση: 12/12/2014

Implementation of the Least Slack Time scheduling algorithm for Linux

Σε αυτή την άσκηση του θα εξοικειωθείτε με τον scheduler του λειτουργικού συστήματος Linux Συγκεκριμένα θα τροποποιήσετε τον scheduler αυτόν έτσι ώστε να επιλέγει διεργασίες για εκτέλεση σύμφωνα με το Least Slack Time αλγόριθμο. Για να δηλώνετε ένα όριο (deadline) στον χρόνο εκτέλεσης καθώς και τον υπολειπόμενο χρόνο υπολογισμών (remaining_computation_time μίας διεργασίας θα χρησιμοποιήσετε το system call set_lst_parameters που δημιουργήσατε στην προηγούμενη άσκηση. Τέλος θα χρειαστεί να δοκιμάσετε τις αλλαγές σας στον scheduler με ένα demo πρόγραμμα.

1. Τροποποιήσεις στον Linux scheduler
Όπως και στην προηγούμενη άσκηση, θα χρησιμοποιήσετε τον emulator qemu με το ίδιο disk image που σας δόθηκε για να ξεκινήσετε το λειτουργικό σύστημα. Δείτε ξανά τις οδηγίες εδώ για τον emulator qemu, το compilation του Linux kernel με τις δικές σας αλλαγές, και πως να κάνετε boot με το image του καινούργιου kernel image που δημιουργήσατε. Επίσης, θα ξεκινήσετε την υλοποίηση αυτής της άσκησης από τον αλλαγμένο κώδικα του Linux kernel που έχετε από την 3η άσκηση (π.χ., από ένα αντίγραφο του κώδικα της 3ης άσκησης).

Ο κώδικας του Linux scheduler βρίσκεται στο αρχείο linux-source-2.6.38.1/kernel/sched.c. Μπορείτε να διαβάσετε περισσότερα για τον Linux scheduler εδώ. Η βασική συνάρτηση του Linux scheduler είναι η συνάρτηση schedule(). Αυτήν την συνάρτηση θα πρέπει να την τροποποιήσετε ως εξής:

1. Για κάθε μια διεργασία που είναι έτοιμη για εκτέλεση και υποψήφια για να γίνει η επόμενη διεργασία που θα εκτελεστεί, θα πρέπει αρχικά να ελέγχετε αν έχει οριστεί, για την διεργασία αυτή, όριο για τον χρόνο περάτωσης (deadline!=-1) καθώς και υπολειπόμενος χρόνος υπολογισμών (remaining_computation_time!=-1). Αν δεν ισχύουν τα ανωτέρω τότε η διεργασία θα παραμένει υποψήφια για να επιλεγεί για εκτέλεση. Αλλιώς:
2. Ο scheduler θα υπολογίζει το slack time από τον τύπο: slack_j = deadline – (remaining_computation_time – elapsed_runtime) – t_j, όπου elapsed_runtime=utime+stime για κάθε διεργασία και θα επιλέγει να τρέξει αυτή με το μικρότερο slack time.
   Προσοχή: ο τύπος του deadline είναι time_t ενώ ο τύπος του remaining_computation_time είναι int.
3. Αν το slack time είναι μικρότερο ή ίσο του μηδέν ή το deadline έχει λήξει τότε η διεργασία αυτή δεν θα θεωρείτε υποψήφια για να επιλεγεί για εκτέλεση στην συνάρτηση schedule() και θα επιλεγεί μία άλλη διεργασία. Αν δεν υπάρχει καμία άλλη διεργασία έτοιμη για εκτέλεση τότε καμία διεργασία δεν θα πρέπει να εκτελεστεί στον επεξεργαστή. Έτσι, οι διεργασίες που έχουν slack time μικρότερο ή ίσο του μηδέν ή έχει λήξει το deadline τους δεν θα πρέπει να εκτελούνται ούτε όταν δεν υπάρχουν άλλες διεργασίες έτοιμες για εκτέλεση (θα είναι σαν ο Linux scheduler να μην έχει καμία runnable διεργασία).

2. Δοκιμή του νέου scheduler
Θα πρέπει να φτιάξετε ένα demo πρόγραμμα που να δείχνει ότι οι αλλαγές που κάνατε στον Linux scheduler δουλεύουν σωστά. Συγκεκριμένα, το πρόγραμμα θα έχει την δυνατότητα να δέχεται ένα όρισμα κ από command line το οποίο κ θα πρέπει να είναι ακέραιος αριθμός με τιμές από 2 μέχρι 10. Σε περίπτωση που δεν δοθεί όρισμα, η default τιμή για το κ θα είναι το 2. Έπειτα, Θα θα δημιουργεί κ θυγατρικές διεργασίες και για κάθε μία i από αυτές, η πατρική διεργασία θα θέτει με το system call set_lst_parameters το το υπολειπόμενο χρόνο (remaining computation time) ίσο με i sec και το deadline του ίσο με gettimeofday+100 sec. Επιπρόσθετα κάθε θυγατρική διεργασία θα κοιμάται για i seconds και έπειτα θα τυπώνει το νούμερο i. Δικαιολογήστε στο README σας την έξοδο του προγράμματος.

Εκτός από αυτό το demo πρόγραμμα, μπορείτε να φτιάξετε και να παραδώσετε όσα περισσότερα θέλετε ώστε να βεβαιωθείτε ότι oι αλλαγές στον Linux scheduler δουλεύουν σωστά.

Τι πρέπει να παραδώσετε
θα πρέπει να παραδώσετε τα παρακάτω αρχεία:

1. Το καινούργιο kernel image, δηλαδή το αρχείο linux-2.6.38.1/arch/x86/boot/bzImage.
2. Όλα τα αρχεία που τροποποιήσατε ή δημιουργήσατε στον source code του Linux kernel 2.6.38.1 για να υλοποιήσετε τα system calls στην 3η άσκηση και τις αλλαγές στον scheduler στην 4η άσκηση. Δηλαδή όλα τα αρχεία .c, .h, Makefile κτλ που κάνατε κάποια αλλαγή, ή δημιουργήσατε εσείς στις ασκήσεις 3 και 4. Μην παραδώσετε αρχεία που δεν χρειάστηκε να τα τροποποιήσετε για την υλοποίησή σας.
3. Τον source code από όλα τα test προγράμματα που γράψατε και τρέξατε μέσα στο guest Linux OS για να δοκιμάσετε τις αλλαγές που υλοποιήσατε στον scheduler για την άσκηση 4 χρησιμοποιώντας τα system calls της άσκησης 3. Και επίσης ότι header files χρησιμοποιήσατε. Δηλαδή τα αρχεία .c, .h και Makefile και ότι άλλο αρχείο δημιουργήσατε στο guest OS για να δοκιμάσετε τις αλλαγές σας (εκτός από τα executables).
4. Ένα README file στο οποίο να περιγράφετε συνοπτικά (αλλά περιεκτικά και ξεκάθαρα) όλα τα βήματα που ακολουθήσατε για την υλοποίηση της άσκησης. Επίσης πρέπει να σχολιάσετε τι παρατηρήσατε από τα test προγράμματα που τρέξατε. Αν έχετε κάνει κάτι διαφορετικό ή παραπάνω από όσα αναφέρουμε στην εκφώνηση της άσκησης μπορείτε επίσης να το αναφέρετε στο README. Καλό θα ήταν το README να είναι από 20 μέχρι 30 γραμμές.

Προσοχή: δεν χρειάζεται να παραδώσετε το disk image (hy345-linux.img) ακόμα και αν αυτό έχει τροποποιηθεί