Λειτουργικά Συστήματα (ΗΥ-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
θα διαβάζει αυτές τις τιμές και θα επιστρέφει τα αντίστοιχα αποτελέσματα.
Συγκεκριμένα:
- Η
set_lst_parameters(int pid, int remaining_computation_time, time_t deadline)
δηλώνει στο σύστημα ότι ο υπολοιπόμενος computation χρόνος που έχει ακόμα η διεργασία με το συγκεκριμένο pid
που δίδεται ως όρισμα, είναι ίσος με remaining_computation_time και
o χρόνος περάτωσης της είναι ίσος με deadline. Μόλις βρείτε τη σωστή διεργασία (τρέχουσα
διεργασία αν το πρώτο όρισμα είναι -1 ή διεργασία με pid=pid), ο kernel θα πρέπει να θέτει στα πεδία
remaining_computation_time
και deadline
τις αντίστοιχες τιμές από το δεύτερο και
τρίτο όρισμα του system call.
- Η
get_lst_parameters(int pid, struct lst_params *lst_arguments)
θα επιστρέφει μέσω του
pointer lst_arguments τις τιμές των παραμέτρων remaining_computation_time και deadline για την διεργασία με
το συγκεκριμένο pid που δίδεται ως όρισμα. Για αυτό το struct θα πρέπει να δεσμεύει μνήμη το user-level
πρόγραμμα πριν καλέσει το system call. Στη συνέχεια, ο kernel θα πρέπει να το γεμίζει με όλες τις πληροφορίες
που χρειάζονται για την διεργασία που ζητήθηκε και θα επιστρέφει αυτές τις πληροφορίες
(by reference) στο user-level πρόγραμμα που κάλεσε το system call. Αν αυτό το δεύτερο όρισμα είναι NULL,
τότε το system call θα πρέπει να επιστρέφει το error value EINVAL. Όπως επίσης αν συμβεί οποιοδήποτε άλλο
λάθος (π.χ. αν ο kernel δεν μπορεί να αντιγράψει τις ζητούμενες πληροφορίες σε user space), θα επιστρέφεται
το ίδιο error value. Στην συνάρτηση αυτή θα πρέπει επίσης να ανανεώνετε την μεταβλητή remaining_computation_time
πρίν η συνάρτηση επιστρέψει την τιμή της. Αυτό σημαίνει ότι θα πρέπει να αφαιρείτε κάθε φορά από το αρχίκο
remaining_computation_time value τον μέχρι στιγμής χρόνο εκτέλεσης (user+system time).
Αν όλα πάνε καλά και το system call τρέξει επιτυχώς, αυτό θα πρέπει να επιστρέφει 0.
Αντίστοιχα, το user-level πρόγραμμα που χρησιμοποιεί το system call θα πρέπει να ελέγχει την επιστρεφόμενη
τιμή για ενδεχόμενο λάθους. Αν το return value του system call είναι 0 (success), τότε τα πραγματικά
αποτελέσματα θα επιστραφούν μέσω του lst_arguments
.
Σημειώσεις:
- Για να δείτε πως μπορείτε να βρείτε την τρέχουσα ώρα του συστήματος (π.χ. να διαβάσετε την μεταβλητή
xtime του kernel) μπορείτε να δείτε το αρχείο linux-2.6.38.1/include/linux/time.h π.χ. για συναρτήσεις που
μπορούν να επιστρέψουν την τιμή που ψάχνετε. Επίσης μπορείτε να κοιτάξετε παρόμοια system calls (όπως
το gettimeofday()) που διαβάζουν την τρέχουσα ώρα του συστήματος.
- Κατά την κλήση των συναρτήσεων αυτών αν το
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.
- Τα πεδία αυτά θα πρέπει να αρχικοποιούνται με -1 (στο αρχείο linux-2.6.38.1/include/linux/init_task.h
). Έτσι, αν για κάποια διεργασία δεν έχει καλεστεί το system call
set_lst_parameters
, οι
τιμές που θα έχουν τα παραπάνω πεδία θα πρέπει να είναι -1, που σημαίνει οτι δεν υπάρχει κάποιο όριο για την
εκτέλεσή τους.
- Στην
set_lst_parameters
, αν το δεύτερο όρισμα remaining_computation_time
είναι
μεγαλύτερο από το τρίτο όρισμα deadline
, τότε το system call θα πρέπει να επιστρέφει με το error
value EINVAL, καθώς αυτό δεν είναι αποδεκτό. Αν όλα τα πάνε καλά και το system call τρέξει επιτυχώς, αυτό θα
πρέπει να επιστρέφει 0. Το user-level πρόγραμμα που χρησιμοποιεί το system call θα πρέπει να ελέγχει την
επιστρεφόμενη τιμή για ενδεχόμενο λάθους.
- 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.
- θα πρέπει να ορίσετε το
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:
- Ο Linux kernel αποθηκεύει τις αναλυτικές πληροφορίες για όλες τις τρέχουσες διεργασίες σε μία doubly
linked list από
task_struct
structs. Μπορείτε να χρησιμοποιήσετε το macro for_each_process()
για να προσπελάσετε όλες τις διεργασίες του συστήματος (task_struct
) που είναι σε
αυτήν τη λίστα, μια προς μια. Το struct task_struct
ορίζεται στο αρχείο linux-2.6.38.1/
include/linux/sched.h. Εκεί μπορείτε να βρείτε όλες τις πληροφορίες για κάθε διεργασία: το pid, το όνομα
της διεργασίας, το χρόνο που ξεκίνησε η εκτέλεση της, και τα user, system time κάθε διεργασίας.
- Για να βρείτε την τρέχουσα διεργασία κοιτάξτε στο αρχείο linux-2.6.38.1/arch/x86/include/asm/current.h .
Εκεί υπάρχει το inline function current που επιστρέφει το
task_struct
entry της
τρέχουσας διεργασίας.
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:
//either macro
#define dummy_sys(arg1) syscall(341, arg1)
//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.
Τι πρέπει να παραδώσετε:
Αφού κάνετε αυτήν την άσκηση θα πρέπει να παραδώσετε τα παρακάτω:
- Το καινούργιο kernel image, δηλαδή το αρχείο linux-2.6.38.1/arch/x86/boot/bzImage.
- Όλα τα αρχεία που τροποποιήσατε ή δημιουργήσατε στον source code του Linux kernel 2.6.38.1 για να
υλοποιήσετε τα system calls. Δηλαδή όλα τα αρχεία .c, .h, Makefile κτλ που κάνατε κάποια αλλαγή, ή
δημιουργήσατε εσείς. Μην παραδώσετε αρχεία που δεν χρειάστηκε να τα τροποποιήσετε για την υλοποίησή σας.
- Τον source code από όλα τα test προγράμματα που γράψατε και τρέξατε μέσα στο guest Linux OS για να
δοκιμάσετε τα system calls που υλοποιήσατε. Και επίσης ότι header files χρησιμοποιήσατε για type και function
definitions (π.χ. το
unist.h
). Δηλαδή τα αρχεία .c, .h και Makefile και ότι άλλο αρχείο
δημιουργήσατε στο guest OS για να δοκιμάσετε τα system calls (εκτός από τα executables).
- Ένα README file στο οποίο να περιγράφετε συνοπτικά (αλλά περιεκτικά και ξεκάθαρα) όλα τα βήματα που
ακολουθήσατε για την δημιουργία των καινούργιων system calls. Επίσης πρέπει να σχολιάσετε τι παρατηρήσατε από
τα test προγράμματα που τρέξατε. Αν έχετε κάνει κάτι διαφορετικό ή παραπάνω από όσα αναφέρουμε στην εκφώνηση
της άσκησης σε οποιοδήποτε βήμα μπορείτε επίσης να το αναφέρετε στο README. Καλό θα ήταν το README να είναι
από 20 μέχρι 30 γραμμές.
Μπορείτε να φτιάξετε έναν κατάλογο με τα τροποποιημένα source code αρχεία του kernel (αν θέλετε θα είναι καλό
να κρατήσετε την δομή καταλόγων που υπάρχει στον linux kernel), έναν κατάλογο με τα test προγράμματα και header
files από το guest OS, και τέλος να τους μεταφέρετε σε ένα κατάλογο μαζί το bzImage και το README file για να
παραδώσετε την άσκηση με τον γνωστό τρόπο.
Προσοχή:
- ΔΕΝ χρειάζεται να παραδώσετε το disk image (hy345-linux.img) ακόμα και αν αυτό έχει τροποποιηθεί
(όντως, το disk image μπορεί να αλλάξει όσο χρησιμοποιείτε το guest OS, σαν ένας κανονικός δίσκος, αλλά δεν
χρειάζεται να το παραδώσετε).
- ΔΕΝ χρειάζεται επίσης να παραδώσετε κάποιο αρχείο με ολόκληρο τον source code του Linux kernel,
πρέπει να σημειώσετε και να παραδώσετε μόνο τα αρχεία που τροποποιήσατε ή δημιουργήσατε. To kernel image
(bzImage), τα header files, και τα test προγράμματα που θα παραδώσετε θα πρέπει να είναι αρκετά ώστε η άσκησή
σας να μπορεί να τρέξει με το αρχικό disk image και το QEMU, έτσι ώστε να φαίνετε η σωστή υλοποίηση του
ζητούμενου system call.
Παρατηρήσεις:
- Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα
μηδενιστούν. Συμπεριλάβετε το όνομα σας και το λογαριασμό σας (account) σε όλα τα αρχεία.
- Γράψτε ένα αρχείο
README
, το πολύ 30 γραμμών, με επεξηγήσεις για τον τρόπο υλοποίησης των
system calls.
- Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε πληκτρολογώντας make all να γίνεται η μεταγλώττιση
(compilation) των προγραμμάτων που χρησιμοποιούν τα system calls και να παράγονται τα εκτελέσιμα αρχεία.
Επίσης πληκτρολογώντας make clean να καθαρίζονται όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που
χρειάζονται για τη μεταγλώττιση.
- Τοποθετήστε σε ένα κατάλογο όλα τα αρχεία προς παράδοση για την άσκηση 3. Παραδώστε τα παραπάνω αρχεία
χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε turnin assignment_3@hy345 directory_name
από τον κατάλογο που περιέχει τον κατάλογο directory_name με τα αρχέια της άσκησης).
- Σε πολλές περιπτώσεις τα ονόματα των αρχείων είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας
βολεύουν.