Χρονοπρογραμματισμός

Question 1

Τι είναι ο Χρονοδρομολογητής ή χρονοπρογραμματιστής;

Answer 1

Χρονοδρομολογητής ή χρονοπρογραμματιστής (scheduler)
είναι το τμήμα του Λ.Σ. το οποίο είναι επιφορτισμένο με την
ευθύνη της απόφασης ποια εκτελέσιμη διεργασία θα εκτελεστεί
πρώτη

Question 2

Ποιές στιγμές είναι κατάλληλες για να γίνει χρονοπρογραμματισμός;

Answer 2

– Δημιουργείται μια νέα διεργασία και πρέπει να αποφασίσουμε αν θα εκτελεστεί αυτή ή η μητρική της
– Όταν μια διεργασία τερματίζεται και υπάρχουν άλλες διεργασίες σε ετοιμότητα
– Όταν μια διεργασία μπλοκάρεται
– Όταν γίνεται κάποια διακοπή Ε/Ε

Question 3

Τι είναι οι προεκτοπιστικοί και μη αλγόριθμοι;

Answer 3

Μη προεκτοπιστικοί (non-preemptive) αλγόριθμοι είναι αυτοί που επιτρέπουν σε μία διεργασία να εκτελείται μέχρι να ολοκληρωθεί ή να παραχωρήσει εθελοντικά τον έλεγχο της CPU. Ενώ οι προεκτοπιστικοί αναστέλλουν την εκτέλεση των διεργασιών μετά από κάποιο διάστημα.

Question 4

Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων
χρονοπρογραμματισμού
για όλα τα συστήματα;

Answer 4

Οι βασικότεροι στόχοι των αλγορίθμων για όλα τα συστήματα είναι:
* Δικαιοσύνη – Να εκχωρείται σε κάθε διεργασία ένα δίκαιο μερίδιο της CPU
* Επιβολή της Πολιτικής – Εφαρμόζεται η καθορισμένη πολιτική; (π.χ. Τήρηση προτεραιοτήτων)
* Ισορροπία – να διατηρούνται απασχολημένα όλα τα τμήματα του συστήματος.

Question 5

Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων χρονοπρογραμματισμού
για τα συστήματα δέσμης;

Answer 5

Οι βασικότεροι στόχοι των αλγορίθμων για τα Συστήματα Δέσμης είναι:
* Διεκπεραιωτική Ικανότητα – μεγιστοποίηση του αριθμού εργασιών
που ολοκληρώνονται ανά ώρα
* Χρόνος Διεκπεραίωσης – να ελαχιστοποιηθεί ο χρόνος ολοκλήρωσης
μια διεργασίας
* Χρήση CPU — να διατηρείται η CPU ενεργός

Question 6

Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων
χρονοπρογραμματισμού
για τα αλληλεπιδραστικά συστήματα;

Answer 6

Οι βασικότεροι στόχοι των αλγορίθμων για τα Αλληλεπιδραστικά Συστήματα είναι:
* Χρόνος Απόκρισης– Να είναι όσο το δυνατόν μικρότερος
* Τήρηση Αναλογιών – Να ικανοποιούνται οι προσδοκίες των χρηστών

Question 7

Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων χρονοπρογραμματισμού για τα συστήματα πραγματικού χρόνου;

Answer 7

• Τήρηση προθεσμιών – να αποφεύγεται απώλεια δεδομένων
• Προβλεψιμότητα – να αποφεύγεται η υποβάθμιση της ποιότητας στα συστήματα πολυμέσων

Question 8

Ποιοι είναι επιγραμματικά οι τρεις (3) τρόποι εξυπηρέτησης στα συστήματα δέσμης;

Answer 8

– Εξυπηρέτηση με βάση τη σειρά άφιξης

– Εξυπηρέτηση με βάση τη μικρότερη διάρκεια

– Εξυπηρέτηση με βάση τη μικρότερη διάρκεια που απομένει

Question 9

Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη σειρά άφιξης;

Answer 9

• First-Come First-Served
• Διεργασίες που μπλοκάρονται όταν πάλι γίνουν έτοιμες για εκτέλεση
  μπαίνουν στο τέλος της ουράς.

Question 10

Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη μικρότερη διάρκεια;

Answer 10

• Προϋποθέτει ότι γνωρίζουμε τη διάρκεια εκτέλεσης των διεργασιών
• Βέλτιστος μέσος χρόνος διεκπεραίωσης αν όλες οι διεργασίες είναι διαθέσιμες ταυτόχρονα

Question 11

Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη μικρότερη διάρκεια που απομένει;

Answer 11

• Προεκτοπιστική έκδοση του προηγούμενου αλγορίθμου
• Προϋποθέτει ότι γνωρίζουμε τη διάρκεια εκτέλεσης των διεργασιών
• Γίνεται έλεγχος κάθε φορά που προστίθεται μια νέα διεργασία

Question 12

Ποια είναι επιγραμματικά τα τρία (3) επίπεδα του Χρονοπρογραμματιστή Τριών Επιπέδων;

Answer 12

• Χρονοπρογραμματιστής Αποδοχής
• Χρονοπρογραμματιστής Μνήμης
• Χρονοπρογραμματιστής CPU

Question 13

Ποια είναι η λειτουργία του Χρονοπρογραμματιστή Αποδοχής;

Answer 13

Χρονοπρογραμματιστής Αποδοχής: Αποφασίζει ποιες εργασίες θα
γίνουν αποδεκτές από το σύστημα (π.χ. Ορθή αναλογία υπολογιστικά
φραγμένων και Ε/Ε φραγμένων)

Question 14

Ποια είναι η λειτουργία του Χρονοπρογραμματιστή Μνήμης;

Answer 14

Χρονοπρογραμματιστής Μνήμης (αποφασίζει ποιες θα μείνουν στη
μνήμη και ποιες θα αποθηκευθούν στο δίσκο) – Οι διεργασίες που
βρίσκονται ταυτόχρονα στη μνήμη καθορίζουν το βαθμό
πολυπρογραμματισμού.
– Για να πάρει τις αποφάσεις του ο χρονοπρογραμματιστής Μνήμης,
χρησιμοποιεί τα παρακάτω κριτήρια:
» Πόσος χρόνος πέρασε από τη στιγμή που η διεργασία μεταφέρθηκε στο
δίσκο/μνήμη ;
» Πόσο χρόνο CPU είχε στη διάθεση της η διεργασία ;
» Ποιο είναι το μέγεθος της διεργασίας ;
» Πόσο σημαντική είναι η διεργασία ;

Question 15

Ποια είναι η λειτουργία του Χρονοπρογραμματιστή CPU;

Answer 15

Χρονοπρογραμματιστής CPU – Αξιοποιείται οποιοσδήποτε
προεκτοπιστικός ή μή αλγόριθμος, συμπεριλαμβανομένων αυτών που
είδαμε

Question 16

Αναφέρετε επιγραμματικά τους τρεις (3) τρόπους χρονοδρομολόγησης διεργασιών στα Αλληλεπιδραστικά συστήματα

Answer 16

1) Χρονοδρομολόγηση Εξυπηρέτησης εκ Περιτροπής
2) Χρονοδρομολόγηση με βάση τη Προτεραιότητα
3) Πολλαπλές ουρές

Question 17

Περιγράψτε την Χρονοδρομολόγηση Εξυπηρέτησης εκ Περιτροπής

Answer 17

Σύμφωνα με τον αλγόριθμο εξυπηρέτησης εκ περιτροπής (round robin scheduling), σε κάθε διεργασία εκχωρείται χρονικό διάστημα - κβάντο (quantum) στα όρια του οποίου επιτρέπεται η εκτέλεσή της.
Αν η διεργασία δεν ολοκληρωθεί μέχρι το τέλος του χρονικού αυτού διαστήματος, τότε η CPU προεκχωρείται σε άλλη διεργασία, δηλαδή λαμβάνει χώρα εναλλαγή διεργασιών (process switch) ή μεταγωγή
περιβάλλοντος (context switch).
Αν η διεργασία ολοκληρωθεί πριν το τέλος του
χρονικού διαστήματος που της είχε ανατεθεί, τότε ο αλγόριθμος χρονοδρομολόγησης παραχωρεί την CPU στην επόμενη στην ουρά διεργασία.
Σημαντική παράμετρο αποτελεί η επιλογή του μεγέθους του κβάντου χρόνου, αφού η εναλλαγή διεργασιών μπορεί να προκαλέσει σημαντική καθυστέρηση.
Τυπική τιμή κβάντου 70 msec

Question 18

Περιγράψτε την Χρονοδρομολόγηση Εξυπηρέτησης με βάση την προτεραιότητα

Answer 18

Σε κάθε διεργασία ανατίθεται μία προτεραιότητα και εκτελείται η διεργασία με την υψηλότερη προτεραιότητα. Για την
αποτροπή της επ’ άπειρο εκτέλεσης διεργασιών υψηλής προτεραιότητας ο χρονοδρομολογητής μειώνει την προτεραιότητα της τρέχουσας
διεργασίας σε κάθε διακοπή ρολογιού ή καθορίζεται ένα μέγιστο κβάντο σε κάθε διεργασία, το οποίο καθορίζει τον μέγιστο χρόνο εκτέλεσής της.
Ένας τυπικός αλγόριθμος καλής εξυπηρέτησης αναθέτει προτεραιότητα 1/f , όπου f είναι το μέρος του κβάντου χρόνου που χρησιμοποιήθηκε από τη διεργασία την τελευταία φορά. Συνεπώς αν μια διεργασία είναι φραγμένη λόγω Ε/Ε, τότε δεν έχει νόημα απλά να περιμένει πολύ ώρα στη μνήμη για να αξιοποιήσει τη CPU και να καταναλώνει μνήμη.

Question 19

Τι είναι το υβριδικό σχήμα;

Answer 19

• Υβριδικό σχήμα περιλαμβάνει την ομαδοποίηση διεργασιών σε κλάσεις
  προτεραιοτήτων (priority classes). Χρησιμοποιείται ταυτόχρονα:
  – χρονοδρομολόγηση προτεραιοτήτων μεταξύ των κλάσεων
  – χρονοδρομολόγηση εξυπηρέτησης εκ περιτροπής μεταξύ των διεργασιών
  της ίδιας κλάσης.
• Με τον αλγόριθμο αυτό, μπορεί να εμφανισθεί το πρόβλημα της
  παρατεταμένης στέρησης πόρων (starvation) της CPU για κάποιες
  διεργασίες.

Question 20

Περιγράψτε τη διαδικασία των πολλαπλών ουρών

Answer 20

• Σε όλους τους αλγορίθμους εναλλαγής διεργασιών,
  σημαντική σχεδιαστική παράμετρο αποτελεί η επιλογή του
  μεγέθους του κβάντου χρόνου
• Διεργασίες με υψηλή απαίτηση σε CPU
  = μεγάλο κβάντο
  χρόνου
• Διεργασίες με υψηλή απαίτηση σε I/O = μικρό κβάντο
  χρόνου
• Επιλογή μεταξύ πλήθους εναλλαγών έναντι υψηλών χρόνων
  απόκρισης.
• Μία αποτελεσματική επιλογή είναι η λύση των
  πολλαπλών ουρών (multiple queues) - κλάσεων
  προτεραιοτήτων:
  – οι διεργασίες της ουράς υψηλότερης κλάσης εκτελούνται
  για ένα κβάντο χρόνου
  – οι διεργασίες της ουράς της επόμενης κλάσης
  εκτελούνται για δύο κβάντα χρόνου
  – όταν μια διεργασία χρησιμοποιεί όλο το κβάντο χρόνου
  που της ανατίθεται, υποβιβάζεται κατά μία κλάση.

Question 21

Ποια είναι τα πλεονεκτήματα της μεθόδου των πολλαπλών ουρών;

Answer 21

Τα πλεονεκτήματα της μεθόδου αυτής είναι:
– απαιτείται μικρότερος αριθμός εναλλαγών, σε σχέση με
τον αλγόριθμο εξυπηρέτησης εκ περιτροπής
– όσο μια μεγάλη διεργασία βυθίζεται βαθύτερα στις
ουρές προτεραιοτήτων, τόσο ευνοείται η ολοκλήρωση
μικρών διαλογικών διεργασιών.
* Εγγυημένος Χρονοπρογραμματισμός:
– Συγκεκριμένες απαιτήσεις για την απόδοση του
συστήματος

– Απαιτείται να κρατάμε το χρόνο CPU που διατίθεται σε
κάθε διεργασία χρήστη
* Χρονοπρογραμματισμός Δίκαιης Διανομής:
– Λαμβάνεται υπόψη σε ποιόν χρήστη ανήκει η κάθε
διαδικασία

Question 22

Ποιες είναι οι δυο (2) κατηγορίες συστημάτων πραγματικού χρόνου;

Answer 22

– Συστήματα αυστηρά πραγματικού χρόνου (Hard Real-
time)
– Ήπια συστήματα πραγματικού Χρόνου

Question 23

Πώς λειτουργούν τα ήπια συστήματα πραγματικού χρόνου;

Answer 23

Η συνήθης τακτική είναι ο χωρισμός του προγράμματος σε
κάποιον αριθμό από διεργασίες που έχουν προβλέψιμη και
γνωστή εκ των προτέρων συμπεριφορά
. Όταν ανιχνεύεται κάποιο εξωτερικό γεγονός ο
χρονοπρογραμματιστής επιλέγει την κατάλληλη διεργασία ώστε
να τηρηθούν οι προθεσμίες.