Skip to content

giannisvrn/priority-scheduling-xv6

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Υλοποίηση priority based scheduler:
Για την υλοποίηση του priority based scheduler έπρεπε πρώτα να δημιουργήσουμε το setpriority syscall.
Την συνάρτηση int setpriority(int num) την έχω υλοποιήσει στο kernel/proc.c όπου απλά το πεδίο priority του myproc(δηλαδή του proc που κάλεσαι την setpriority) παίρνει την τιμή num(εάν το num δεν έχει επιτρεπτή τιμή επιστρέφει -1).Στο ιδιο αρχείο, στην υλοποίηση της allocproc έχω προσθέσει την εντολή p->priority = 10; για να αρχικοποιεί την προτεραίοτητα των διεργασιών σε 10.
Στην συνέχεια έχω δηλώσει την συνάρτηση setpriority στο defs.h. Στο αρχείο syscall.c και στο syscall.h δηλώνουμε το syscall.
Έπειτα στο sysproc.c υλοποιούμε το syscall, όπου απλά καλούμε την συνάρτηση αφού πρώτα πάρουμε το όρισμα.
Στο usys.pl ορίζουμε την assembly που καλεί το syscall και στο user.h δηλώνουμε το syscall.
Στην συνέχεια θα ασχοληθούμε με την υλοποίηση του scheduler. Στην συνάρτηση αυτή ορίζουμε μια επιπλέον μεταβλητή τύπου struct proc *, στην οποία θα καταχωρήσουμε την διεργασία με την μικρότερη προτεραιότητα(αρχικά αρχικοποιείται με 0).Έπειτα για κάθε διεργασία που είναι σε state RUNNABLE ελέγχουμε για αρχή εάν το p_prio είναι κενό και άρα καταχωρούμε την διεργασία, διαφορετικά τοποθετούμε την διεργασία μόνο εάν έχει μικρότερη προτεραιότητα από την ήδη υπάρχουσα(έτσι υλοποίεται και round robin αλγόριθμος σε περίπτωση διεργασιών με ίση προτεραιότητα).Αφού ελέγξουμε όλες τις διεργασίες, θα τρέξουμε την διεργασία με την μικρότερη προτεραίοτητα( εάν υπήρχε κάποια διεργασία που ηταν σε state RUNNABLE, και αν αυτή η διεργασία που επιλέξαμε είναι ακόμα σε state RUNNABLE).
Για την δοκιμή του καινούριου scheduler είχα δημιουργήσει ένα user level πρόγραμμα το οποίο έλεγχε την σειρά των διεργασιών με την οποία τελειώναν ανάλογα με την προτεραιότητα τους, όμως υπάρχει και ήδη υλοποιημένο το πρόγραμμα priotest.c 
Μία τυχαία εκτέλεση αυτού του προγράμματος είναι η εξής :

Child pid 19, small, with priority 2 finished. Useless sum: 448743748
Child pid 38, small, with priority 2 finished. Useless sum: 448743748
Child pid 20, small, with priority 3 finished. Useless sum: 448743748
Child pid 39, small, with priority 3 finished. Useless sum: 448743748
Child pid 21, small, with priority 4 finished. Useless sum: 448743748
Child pid 40, small, with priority 4 finished. Useless sum: 448743748
Child pid 22, small, with priority 5 finished. Useless sum: 448743748
Child pid 41, small, with priority 5 finished. Useless sum: 448743748
Child pid 23, small, with priority 6 finished. Useless sum: 448743748
Child pid 42, small, with priority 6 finished. Useless sum: 448743748
Child pid 24, small, with priority 7 finished. Useless sum: 448743748
Child pid 43, small, with priority 7 finished. Useless sum: 448743748
Child pid 44, small, with priority 8 finished. Useless sum: 448743748
Child pid 25, small, with priority 8 finished. Useless sum: 448743748
Child pid 26, small, with priority 9 finished. Useless sum: 448743748
Child pid 45, small, with priority 9 finished. Useless sum: 448743748
Child pid 8, small, with priority 10 finished. Useless sum: 448743748
Child pid 27, small, with priority 10 finished. Useless sum: 448743748
Child pid 46, small, with priority 10 finished. Useless sum: 448743748
Child pid 28, small, with priority 11 finished. Useless sum: 448743748
Child pid 9, small, with priority 11 finished. Useless sum: 448743748
Child pid 47, small, with priority 11 finished. Useless sum: 448743748
Child pid 10, small, with priority 12 finished. Useless sum: 448743748
Child pid 29, small, with priority 12 finished. Useless sum: 448743748
Child pid 11, small, with priority 13 finished. Useless sum: 448743748
Child pid 12, small, with priority 14 finished. Useless sum: 448743748
Child pid 30, small, with priority 13 finished. Useless sum: 448743748
Child pid 31, small, with priority 14 finished. Useless sum: 448743748
Child pid 32, small, with priority 15 finished. Useless sum: 448743748
Child pid 13, small, with priority 15 finished. Useless sum: 448743748
Child pid 14, small, with priority 16 finished. Useless sum: 448743748
Child pid 33, small, with priority 16 finished. Useless sum: 448743748
Child pid 15, small, with priority 17 finished. Useless sum: 448743748
Child pid 34, small, with priority 17 finished. Useless sum: 448743748
Child pid 5, large, with priority 16 finished. Useless sum: 1818368003
Child pid 16, small, with priority 18 finished. Useless sum: 448743748
Child pid 35, small, with priority 18 finished. Useless sum: 448743748
Child pid 17, small, with priority 19 finished. Useless sum: 448743748
Child pid 6, large, with priority 17 finished. Useless sum: 1818368003
Child pid 36, small, with priority 19 finished. Useless sum: 448743748
Child pid 7, large, with priority 18 finished. Useless sum: 1818368003
Child pid 18, small, with priority 20 finished. Useless sum: 448743748
Child pid 37, small, with priority 20 finished. Useless sum: 448743748
Child pid 4, large, with priority 20 finished. Useless sum: 1818368003

Τα ίδια βήματα με την υλοποίηση του syscall setpriority ακολούθησα για την υλοποίηση του syscall getpinfo.
Η υλοποίηση του sys_getpinfo αποτελείται από την κλήση της getpinfo και την χρήση της copyout για την αντιγραφή δεδομένων από kernel σε user space.
Επίσης χρειάστηκε να δημιουργήσουμε ένα καινούριο αρχείο το pstat.h το οποίο περίεχει την δήλωση του struct pstat.
Για να μπορέσουμε να έχουμε ως πεδίο μια μεταβλητή τύπου enum procstate, έπρεπε να προσθέσουμε την δήλωση του enum procstate στο αρχείο user/user.h
Η συνάρτηση getpinfo έχει υλοποιηθεί στο αρχείο kernel/proc.c. Αρχικά αρχικοποιούμε τον αριθμό των μη UNUSED processes σε 0. Στην συνέχεια ελέγχουμε όλες τις διεργασίες και αν είναι ενεργές(δηλαδή μη UNUSED) προσθέτουμε στην pst μεταβλητή μας τα πεδία που χρειαζόμαστε.
Για την υλοποίηση της ps έχουμε δημιουργήσει ένα καινούριο πρόγραμμα user/ps.c στο οποίο(αρχικά αλλάζουμε το priority του ps σε 15 για να δούμε ότι δουλεύει και αυτό σωστά) καλούμε την getpinfo, και μέσω του pst εκτυπώνουμε τα δεδόμενα που έχουμε.
Μία τυχαία εκτέλεσή του είναι η παρακάτω:

  PID  PPID  PRIORITY    NAME    SIZE       STATE 
   1    -1       10        init      16384     SLEEPING
   2    1       10        sh      20480     SLEEPING
   3    2       15        ps      16384     RUNNING

Τέλος όταν τρέχουμε την εντολή usertests μας επιστρέφει στο τέλος:
ALL TESTS PASSED

About

No description, website, or topics provided.

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Contributors 38