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



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

Implementation of system calls for LST algorithm
in the Linux Operating System


Ο Least Slack Time (LST) είναι ένας αλγόριθμος χρονοπρογραμματισμού, που χρησιμοποιείται κυρίως σε embedded συστήματα και αναθέτει προτεραιότητα με βάση το περιθωριο εκτέλεσης(slack time) μίας διεργασίας. Στον αλγόριθμο αυτό πρώτα επιλέγονται για εκτέλεση οι διεργασίες που έχουν τον ελάχιστο slack χρόνο. Ως ελάχιστο slack χρόνο ορίζουμε το χρόνο που πρέπει μία διεργασία να τελειώσει την εκτέλεση (deadline time) μείον τον υπόλοιπο χρόνο υπολογισμού (computation time) της. Για παράδειγμα, ας υποθέσουμε ότι ο υπόλοιπος χρόνος υπολογισμού C είναι 5 sec και το deadline D είναι σε 20 sec από τώρα. Ο slack χρόνος S υπολογίζεται ως: S = D - C = 15 sec. O χρονοπρογραμματιστής θα συγκρίνει αυτό το slack χρόνο με τους slack χρόνους των άλλων διεργασιών του συστήματος και θα εκτελέσει εκείνη με το μικρότερο slack χρόνο. Με αυτό τον τρόπο, αν έρθουν ταυτόχρονα πολλές διεργασίες και αναγκαστικά πρέπει να γίνουν miss κάποια dealdines, θα γίνουν miss με τη καθυστέρηση να παραμένει ομοιόμορφη για όλες τις διεργασίες.

Σε αυτήν την άσκηση θα πρέπει να υλοποιήσετε και να δοκιμάσετε δυο καινούργια system calls, τα οποία θα χρησιμοποιήσετε και στην επόμενη άσκηση του μαθήματος (4η άσκηση). Πιο συγκεκριμένα θα χρειαστεί να προσθέσετε στον πυρήνα (kernel) του λειτουργικού συστήματος Linux τα δύο νέα system calls: set_lst_parameters() και get_lst_parameters(). Έπειτα θα τα δοκιμάσετε χρησιμοποιώντας τον προσομοιωτή (emulator) QEMU (δείτε αναλυτικές οδηγίες εδώ) κάνοντας compile τον Linux kernel με τις αλλαγές σας, θα τρέξετε το Linux με τον καινούργιο kernel στον προσομοιωτή QEMU και, τέλος, εκεί θα γράψετε και θα τρέξετε ένα user-level demo πρόγραμμα που θα χρησιμοποιεί τα καινούργια system calls.

Στόχος της άσκησης είναι να εξοικειωθείτε με τον source code του Linux kernel, με τον τρόπο που είναι δομημένο ένα system call στο Linux, με την μεταγλώττιση του kernel, και με τη χρήση ενός προσομοιωτή.

A. Προσθήκη νέων system calls στον Linux kernel
Η αλλαγή που θα κάνετε στον Linux kernel 2.6.38.1 είναι να προσθέσετε δύο καινούργια system calls (δείτε αναλυτικές οδηγίες εδώ) που θα λέγονται set_lst_parameters και get_lst_parameters. Επίσης, θα πρέπει να προσθέσετε στη δομή task_struct, η οποία αναπαριστά μια διεργασία στον Linux kernel, δύο καινούργια πεδία:
 
int remaining_computation_time;  //υπολοιπόμενος χρόνος υπολογισμών (σε seconds)
time_t deadline;                 //ο χρόνος μέσα στον οποίο η διεργασία πρέπει να έχει τελειώσει (seconds από την 1/1/1970)
 
Η τιμή στα πεδία αυτά θα αλλάζει από το system call set_lst_parameters, ενώ το system call get_lst_parameters θα διαβάζει αυτές τις τιμές και θα επιστρέφει τα αντίστοιχα αποτελέσματα. Συγκεκριμένα: Σημειώσεις:
  1. Για να δείτε πως μπορείτε να βρείτε την τρέχουσα ώρα του συστήματος (π.χ. να διαβάσετε την μεταβλητή xtime του kernel) μπορείτε να δείτε το αρχείο linux-2.6.38.1/include/linux/time.h π.χ. για συναρτήσεις που μπορούν να επιστρέψουν την τιμή που ψάχνετε. Επίσης μπορείτε να κοιτάξετε παρόμοια system calls (όπως το gettimeofday()) που διαβάζουν την τρέχουσα ώρα του συστήματος.
  2. Κατά την κλήση των συναρτήσεων αυτών αν το pid είναι -1, τότε μας ενδιαφέρει η τρέχουσα διεργασία που καλεί το system call. Αν έχει άλλη τιμή, τότε θα πρέπει να βρείτε τη διεργασία που έχει αυτό το pid και έπειτα να αλλάξετε τα παραπάνω τρία πεδία σε αυτήν τη διεργασία. Αν η τιμή του pid είναι αρνητική (αλλά όχι -1), ή αν δεν αντιστοιχεί σε κάποια τρέχουσα διεργασία, τότε το system call θα πρέπει επιστρέφει το error value EINVAL. Το EINVAL και τα υπόλοιπα error values είναι ορισμένα στο linux-2.6.38.1/include/asm-generic/errno-base.h.
  3. Τα πεδία αυτά θα πρέπει να αρχικοποιούνται με -1 (στο αρχείο linux-2.6.38.1/include/linux/init_task.h ). Έτσι, αν για κάποια διεργασία δεν έχει καλεστεί το system call set_lst_parameters, οι τιμές που θα έχουν τα παραπάνω πεδία θα πρέπει να είναι -1, που σημαίνει οτι δεν υπάρχει κάποιο όριο για την εκτέλεσή τους.
  4. Στην set_lst_parameters, αν το δεύτερο όρισμα remaining_computation_time είναι μεγαλύτερο από το τρίτο όρισμα deadline, τότε το system call θα πρέπει να επιστρέφει με το error value EINVAL, καθώς αυτό δεν είναι αποδεκτό. Αν όλα τα πάνε καλά και το system call τρέξει επιτυχώς, αυτό θα πρέπει να επιστρέφει 0. Το user-level πρόγραμμα που χρησιμοποιεί το system call θα πρέπει να ελέγχει την επιστρεφόμενη τιμή για ενδεχόμενο λάθους.
  5. Kάθε φορά που καλούνται τα system calls set_lst_parameters και get_lst_parameters στο επίπεδο του πυρήνα, θα πρέπει να τυπώνετε με την συνάρτηση printk μια γραμμή με το όνομα σας, τον Α.Μ. σας, και το όνομα του system call. Τα μηνύματα που τυπώνετε στον kernel με την συνάρτηση printk μπορείτε να τα βλέπετε όταν έχετε φορτώσει το Linux με το συγκεκριμένο kernel τρέχοντας το dmesg ή κάνοντας cat /var/log/messages. Έτσι, κάθε φορά που καλούνται τα συγκεκριμένα system calls από ένα user-level πρόγραμμα, θα πρέπει με αυτόν τον τρόπο να βλέπουμε το μήνυμα που εκτυπώσατε με το όνομά σας από τον kernel. Με τον ίδιο τρόπο (printk) μπορείτε να εκτυπώνετε ότι άλλα μηνύματα θέλετε από τον kernel (π.χ. ένας απλός τρόπος να κάνετε debugging το system call που φτιάχνετε) και να τα βλέπετε όταν τρέχει ο kernel, αφού καλέσετε το system call, από το dmesg.
  6. θα πρέπει να ορίσετε το struct lst_params στο καινούργιο αρχείο linux-2.6.38.1/include/ lst_params.h που θα δημιουργήσετε. Όπως είπαμε, αυτό το struct θα περιέχει τις πληροφορίες που χρειαζόμαστε για τη διεργασία με το pid που δίνετε στο πρώτο όρισμα των δυο νέων system calls. Αυτές οι πληροφορίες θα είναι οι τιμές για τα πεδία remaining_computation_time και deadline που έχουν δωθεί για αυτή τη διεργασία με το set_lst_parameters() system call. Αναλυτικά, το struct lst_params θα πρέπει να έχει τα παρακάτω πεδία:
      
    	struct lst_params {			// info and times about the process 
    		 int remaining_computation_time;// time limit for this process
    		 time_t deadline;		// process's deadline
    	}
    	 
    Σημειωση: Το pid_t ορίζετε στο linux-2.6.38.1/include/linux/types.h.
Hints: B. Δοκιμή του νέου system call
Στο τελευταίο βήμα της άσκησης θα πρέπει να δοκιμάσετε τα καινούργια system calls. Αφού έχετε κάνει compile με επιτυχία τον kernel με τα system calls που φτιάξατε, και έχετε ξεκινήσει τον QEMU με τον καινούργιο Linux kernel, θα πρέπει να γράψετε κάποια test προγράμματα που να χρησιμοποιούν τα set_lst_parameters και get_lst_parameters στο guest Linux OS. Συνήθως ένα system call καλείται μέσω κάποιας συνάρτησης που τρέχει σε user level και υπάρχει σε κάποια βιβλιοθήκη (π.χ. libc). Στην συνέχεια, αυτή η user- level συνάρτηση καλεί το macro syscall με το system call number του συγκεκριμένου system call για να μεταβιβάσει τον έλεγχο στον kernel (trap) και εκεί να τρέξει αυτό το system call. Αν δεν έχει υλοποιηθεί αυτή η συνάρτηση σε κάποια user-level library (θα πρέπει αυτό να γίνει μέσα στο guest Linux OS) ένα test προγράμμα μπορεί να τρέχει κατευθείαν το syscall macro με το system call number που έχει οριστεί για το system call στον αλλαγμένο kernel. Για παράδειγμα, το παρακάτω test πρόγραμμα καλεί το dummy_test system call με το system call number 341, δίνοντας σαν όρισμα τον αριθμό 42. Μπορείτε να κάνετε compile το test πρόγραμμα κανονικά με τον gcc.
 
#include <stdio.h>
#include <unistd.h>
#include <errno.h>

#define __NR_dummy_sys 341

int main()
{
  printf("Trap to kernel level\n");
  syscall(__NR_dummy_sys, 42);
  //you should check return value for errors
  printf("Back to user level\n");
}
Εσείς θα πρέπει, είτε να κάνετε define δύο macros για τα set_lst_parameters και get_lst_parameters, ώστε τα syscalls να μοιάζουν με function calls, είτε να φτιάξετε δύο wrapper functions set_lst_parameters και get_lst_parameters (με τα ορίσματα που δέχονται αυτά τα system calls) που να καλούν εσωτερικά το αντίστοιχο syscall. Έτσι θα καλείτε το set_lst_parameters ή get_lst_parameters macro ή wrapper function αντί για το syscall μέσα στο πρόγραμμά σας, σύμφωνα με το function prototype που ορίσαμε. Για παράδειγμα, για το dummy_sys:
  1. 
    	//either macro
    	#define dummy_sys(arg1) syscall(341, arg1)
    	
  2. 
    	//or wrapper function
    	long dummy_sys(int arg1) {
    		syscall(341, arg1);
    	}

//and in the test program we just call:
dummy_sys(42);
Αν έχετε header files με definitions για νέους τύπους και structs, πρέπει επίσης να τα κάνετε include στο demo πρόγραμμα (θα χρειαστεί να τα μεταφέρετε στο guest OS και ίσως χρειαστεί να δώσετε το path με αυτά με τα header files στον gcc). Για το get_lst_parameters σας προτείνουμε να προσθέσετε τα definitions για τo struct lst_params, μαζί με τα macros ή inline wrapper functions των set_lst_parameters και get_lst_parameters, στο unistd.h header file που υπάρχει στο guest OS, και το οποίο θα κάνετε include στο demo πρόγραμμα.

Demo program: Θα φτιάξετε ένα πρόγραμμα το οποίο θα καλεί αρχικά το set_lst_parameters για την τρέχουσα διεργασία με κάποιες τιμές για τα πεδία remaining_computation_time και deadline, και έπειτα θα καλεί το get_lst_parameters και θα τυπώνει όλα τα πεδία του struct lst_params για την τρέχουσα διεργασία. Έπειτα θα κάνετε ένα εκατομμύριο πολλαπλασιασμούς και θα καλείτε ξανά το get_lst_parameters τυπώνοντας τα ίδια πεδία. Τέλος, θα κάνετε ένα sleep για 5 δευτερόλεπτα (sleep(5)) και θα τυπώσετε ξανά τα πεδία του lst_params για την τρέχουσα διεργασία, αφού τρέξετε ξανά το get_lst_parameters system call.

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

Προσοχή:

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

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