Χρονοπρογραμματισμός Flashcards
(23 cards)
Τι είναι ο Χρονοδρομολογητής ή χρονοπρογραμματιστής;
Χρονοδρομολογητής ή χρονοπρογραμματιστής (scheduler)
είναι το τμήμα του Λ.Σ. το οποίο είναι επιφορτισμένο με την
ευθύνη της απόφασης ποια εκτελέσιμη διεργασία θα εκτελεστεί
πρώτη
Ποιές στιγμές είναι κατάλληλες για να γίνει χρονοπρογραμματισμός;
– Δημιουργείται μια νέα διεργασία και πρέπει να αποφασίσουμε αν θα εκτελεστεί αυτή ή η μητρική της
– Όταν μια διεργασία τερματίζεται και υπάρχουν άλλες διεργασίες σε ετοιμότητα
– Όταν μια διεργασία μπλοκάρεται
– Όταν γίνεται κάποια διακοπή Ε/Ε
Τι είναι οι προεκτοπιστικοί και μη αλγόριθμοι;
Μη προεκτοπιστικοί (non-preemptive) αλγόριθμοι είναι αυτοί που επιτρέπουν σε μία διεργασία να εκτελείται μέχρι να ολοκληρωθεί ή να παραχωρήσει εθελοντικά τον έλεγχο της CPU. Ενώ οι προεκτοπιστικοί αναστέλλουν την εκτέλεση των διεργασιών μετά από κάποιο διάστημα.
Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων
χρονοπρογραμματισμού
για όλα τα συστήματα;
Οι βασικότεροι στόχοι των αλγορίθμων για όλα τα συστήματα είναι:
* Δικαιοσύνη – Να εκχωρείται σε κάθε διεργασία ένα δίκαιο μερίδιο της CPU
* Επιβολή της Πολιτικής – Εφαρμόζεται η καθορισμένη πολιτική; (π.χ. Τήρηση προτεραιοτήτων)
* Ισορροπία – να διατηρούνται απασχολημένα όλα τα τμήματα του συστήματος.
Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων χρονοπρογραμματισμού
για τα συστήματα δέσμης;
Οι βασικότεροι στόχοι των αλγορίθμων για τα Συστήματα Δέσμης είναι:
* Διεκπεραιωτική Ικανότητα – μεγιστοποίηση του αριθμού εργασιών
που ολοκληρώνονται ανά ώρα
* Χρόνος Διεκπεραίωσης – να ελαχιστοποιηθεί ο χρόνος ολοκλήρωσης
μια διεργασίας
* Χρήση CPU — να διατηρείται η CPU ενεργός
Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων
χρονοπρογραμματισμού
για τα αλληλεπιδραστικά συστήματα;
Οι βασικότεροι στόχοι των αλγορίθμων για τα Αλληλεπιδραστικά Συστήματα είναι:
* Χρόνος Απόκρισης– Να είναι όσο το δυνατόν μικρότερος
* Τήρηση Αναλογιών – Να ικανοποιούνται οι προσδοκίες των χρηστών
Ποιοι είναι οι βασικότεροι στόχοι των αλγορίθμων χρονοπρογραμματισμού για τα συστήματα πραγματικού χρόνου;
- Τήρηση προθεσμιών – να αποφεύγεται απώλεια δεδομένων
- Προβλεψιμότητα – να αποφεύγεται η υποβάθμιση της ποιότητας στα συστήματα πολυμέσων
Ποιοι είναι επιγραμματικά οι τρεις (3) τρόποι εξυπηρέτησης στα συστήματα δέσμης;
– Εξυπηρέτηση με βάση τη σειρά άφιξης
– Εξυπηρέτηση με βάση τη μικρότερη διάρκεια
– Εξυπηρέτηση με βάση τη μικρότερη διάρκεια που απομένει
Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη σειρά άφιξης;
- First-Come First-Served
- Διεργασίες που μπλοκάρονται όταν πάλι γίνουν έτοιμες για εκτέλεση
μπαίνουν στο τέλος της ουράς.
Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη μικρότερη διάρκεια;
- Προϋποθέτει ότι γνωρίζουμε τη διάρκεια εκτέλεσης των διεργασιών
- Βέλτιστος μέσος χρόνος διεκπεραίωσης αν όλες οι διεργασίες είναι διαθέσιμες ταυτόχρονα
Ποια είναι τα χαρακτηριστικά της εξυπηρέτησης με βάση τη μικρότερη διάρκεια που απομένει;
- Προεκτοπιστική έκδοση του προηγούμενου αλγορίθμου
- Προϋποθέτει ότι γνωρίζουμε τη διάρκεια εκτέλεσης των διεργασιών
- Γίνεται έλεγχος κάθε φορά που προστίθεται μια νέα διεργασία
Ποια είναι επιγραμματικά τα τρία (3) επίπεδα του Χρονοπρογραμματιστή Τριών Επιπέδων;
- Χρονοπρογραμματιστής Αποδοχής
- Χρονοπρογραμματιστής Μνήμης
- Χρονοπρογραμματιστής CPU
Ποια είναι η λειτουργία του Χρονοπρογραμματιστή Αποδοχής;
Χρονοπρογραμματιστής Αποδοχής: Αποφασίζει ποιες εργασίες θα
γίνουν αποδεκτές από το σύστημα (π.χ. Ορθή αναλογία υπολογιστικά
φραγμένων και Ε/Ε φραγμένων)
Ποια είναι η λειτουργία του Χρονοπρογραμματιστή Μνήμης;
Χρονοπρογραμματιστής Μνήμης (αποφασίζει ποιες θα μείνουν στη
μνήμη και ποιες θα αποθηκευθούν στο δίσκο) – Οι διεργασίες που
βρίσκονται ταυτόχρονα στη μνήμη καθορίζουν το βαθμό
πολυπρογραμματισμού.
– Για να πάρει τις αποφάσεις του ο χρονοπρογραμματιστής Μνήμης,
χρησιμοποιεί τα παρακάτω κριτήρια:
» Πόσος χρόνος πέρασε από τη στιγμή που η διεργασία μεταφέρθηκε στο
δίσκο/μνήμη ;
» Πόσο χρόνο CPU είχε στη διάθεση της η διεργασία ;
» Ποιο είναι το μέγεθος της διεργασίας ;
» Πόσο σημαντική είναι η διεργασία ;
Ποια είναι η λειτουργία του Χρονοπρογραμματιστή CPU;
Χρονοπρογραμματιστής CPU – Αξιοποιείται οποιοσδήποτε
προεκτοπιστικός ή μή αλγόριθμος, συμπεριλαμβανομένων αυτών που
είδαμε
Αναφέρετε επιγραμματικά τους τρεις (3) τρόπους χρονοδρομολόγησης διεργασιών στα Αλληλεπιδραστικά συστήματα
1) Χρονοδρομολόγηση Εξυπηρέτησης εκ Περιτροπής
2) Χρονοδρομολόγηση με βάση τη Προτεραιότητα
3) Πολλαπλές ουρές
Περιγράψτε την Χρονοδρομολόγηση Εξυπηρέτησης εκ Περιτροπής
Σύμφωνα με τον αλγόριθμο εξυπηρέτησης εκ περιτροπής (round robin scheduling), σε κάθε διεργασία εκχωρείται χρονικό διάστημα - κβάντο (quantum) στα όρια του οποίου επιτρέπεται η εκτέλεσή της.
Αν η διεργασία δεν ολοκληρωθεί μέχρι το τέλος του χρονικού αυτού διαστήματος, τότε η CPU προεκχωρείται σε άλλη διεργασία, δηλαδή λαμβάνει χώρα εναλλαγή διεργασιών (process switch) ή μεταγωγή
περιβάλλοντος (context switch).
Αν η διεργασία ολοκληρωθεί πριν το τέλος του
χρονικού διαστήματος που της είχε ανατεθεί, τότε ο αλγόριθμος χρονοδρομολόγησης παραχωρεί την CPU στην επόμενη στην ουρά διεργασία.
Σημαντική παράμετρο αποτελεί η επιλογή του μεγέθους του κβάντου χρόνου, αφού η εναλλαγή διεργασιών μπορεί να προκαλέσει σημαντική καθυστέρηση.
Τυπική τιμή κβάντου 70 msec
Περιγράψτε την Χρονοδρομολόγηση Εξυπηρέτησης με βάση την προτεραιότητα
Σε κάθε διεργασία ανατίθεται μία προτεραιότητα και εκτελείται η διεργασία με την υψηλότερη προτεραιότητα. Για την
αποτροπή της επ’ άπειρο εκτέλεσης διεργασιών υψηλής προτεραιότητας ο χρονοδρομολογητής μειώνει την προτεραιότητα της τρέχουσας
διεργασίας σε κάθε διακοπή ρολογιού ή καθορίζεται ένα μέγιστο κβάντο σε κάθε διεργασία, το οποίο καθορίζει τον μέγιστο χρόνο εκτέλεσής της.
Ένας τυπικός αλγόριθμος καλής εξυπηρέτησης αναθέτει προτεραιότητα 1/f , όπου f είναι το μέρος του κβάντου χρόνου που χρησιμοποιήθηκε από τη διεργασία την τελευταία φορά. Συνεπώς αν μια διεργασία είναι φραγμένη λόγω Ε/Ε, τότε δεν έχει νόημα απλά να περιμένει πολύ ώρα στη μνήμη για να αξιοποιήσει τη CPU και να καταναλώνει μνήμη.
Τι είναι το υβριδικό σχήμα;
- Υβριδικό σχήμα περιλαμβάνει την ομαδοποίηση διεργασιών σε κλάσεις
προτεραιοτήτων (priority classes). Χρησιμοποιείται ταυτόχρονα:
– χρονοδρομολόγηση προτεραιοτήτων μεταξύ των κλάσεων
– χρονοδρομολόγηση εξυπηρέτησης εκ περιτροπής μεταξύ των διεργασιών
της ίδιας κλάσης. - Με τον αλγόριθμο αυτό, μπορεί να εμφανισθεί το πρόβλημα της
παρατεταμένης στέρησης πόρων (starvation) της CPU για κάποιες
διεργασίες.
Περιγράψτε τη διαδικασία των πολλαπλών ουρών
- Σε όλους τους αλγορίθμους εναλλαγής διεργασιών,
σημαντική σχεδιαστική παράμετρο αποτελεί η επιλογή του
μεγέθους του κβάντου χρόνου - Διεργασίες με υψηλή απαίτηση σε CPU
= μεγάλο κβάντο
χρόνου - Διεργασίες με υψηλή απαίτηση σε I/O = μικρό κβάντο
χρόνου - Επιλογή μεταξύ πλήθους εναλλαγών έναντι υψηλών χρόνων
απόκρισης. - Μία αποτελεσματική επιλογή είναι η λύση των
πολλαπλών ουρών (multiple queues) - κλάσεων
προτεραιοτήτων:
– οι διεργασίες της ουράς υψηλότερης κλάσης εκτελούνται
για ένα κβάντο χρόνου
– οι διεργασίες της ουράς της επόμενης κλάσης
εκτελούνται για δύο κβάντα χρόνου
– όταν μια διεργασία χρησιμοποιεί όλο το κβάντο χρόνου
που της ανατίθεται, υποβιβάζεται κατά μία κλάση.
Ποια είναι τα πλεονεκτήματα της μεθόδου των πολλαπλών ουρών;
Τα πλεονεκτήματα της μεθόδου αυτής είναι:
– απαιτείται μικρότερος αριθμός εναλλαγών, σε σχέση με
τον αλγόριθμο εξυπηρέτησης εκ περιτροπής
– όσο μια μεγάλη διεργασία βυθίζεται βαθύτερα στις
ουρές προτεραιοτήτων, τόσο ευνοείται η ολοκλήρωση
μικρών διαλογικών διεργασιών.
* Εγγυημένος Χρονοπρογραμματισμός:
– Συγκεκριμένες απαιτήσεις για την απόδοση του
συστήματος
– Απαιτείται να κρατάμε το χρόνο CPU που διατίθεται σε
κάθε διεργασία χρήστη
* Χρονοπρογραμματισμός Δίκαιης Διανομής:
– Λαμβάνεται υπόψη σε ποιόν χρήστη ανήκει η κάθε
διαδικασία
Ποιες είναι οι δυο (2) κατηγορίες συστημάτων πραγματικού χρόνου;
– Συστήματα αυστηρά πραγματικού χρόνου (Hard Real-
time)
– Ήπια συστήματα πραγματικού Χρόνου
Πώς λειτουργούν τα ήπια συστήματα πραγματικού χρόνου;
Η συνήθης τακτική είναι ο χωρισμός του προγράμματος σε
κάποιον αριθμό από διεργασίες που έχουν προβλέψιμη και
γνωστή εκ των προτέρων συμπεριφορά
. Όταν ανιχνεύεται κάποιο εξωτερικό γεγονός ο
χρονοπρογραμματιστής επιλέγει την κατάλληλη διεργασία ώστε
να τηρηθούν οι προθεσμίες.
