Συντομότερη εργασία Πρώτα (SJF): Προληπτικό, Μη Προληπτικό Παράδειγμα
Ναθάνιελ Μπρουκς
⚡ Έξυπνη Σύνοψη
Το Shortest Job First (SJF) είναι ένας αλγόριθμος προγραμματισμού CPU που επιλέγει την επόμενη διεργασία με τον μικρότερο χρόνο εκτέλεσης. Μπορεί να είναι προληπτικός ή μη προληπτικός και μειώνει σημαντικά τον μέσο χρόνο αναμονής για τις διεργασίες.
Τι είναι ο Συντομότερος Προγραμματισμός Πρώτης Εργασίας;
Πρώτα η συντομότερη εργασία (SJF) είναι ένας αλγόριθμος στον οποίο η διεργασία που έχει τον μικρότερο χρόνο εκτέλεσης επιλέγεται για την επόμενη εκτέλεση. Αυτή η μέθοδος προγραμματισμού μπορεί να είναι προληπτική ή μη προληπτική. Μειώνει σημαντικά τον μέσο χρόνο αναμονής για άλλες διεργασίες που περιμένουν να εκτελεστούν. Η πλήρης μορφή του SJF είναι το Shortest Job First.
Υπάρχουν βασικά δύο τύποι μεθόδων SJF:
- Μη προληπτικό SJF
- Προληπτικό SJF
Χαρακτηριστικά Προγραμματισμού SJF
- Συνδέεται με κάθε εργασία ως μονάδα χρόνου προς ολοκλήρωση.
- Αυτή η μέθοδος αλγορίθμου είναι χρήσιμη για επεξεργασία τύπου παρτίδας, όπου η αναμονή για την ολοκλήρωση των εργασιών δεν είναι κρίσιμη.
- Μπορεί να βελτιώσει την απόδοση της διαδικασίας διασφαλίζοντας ότι εκτελούνται πρώτα οι μικρότερες εργασίες, με αποτέλεσμα ενδεχομένως να υπάρχει σύντομος χρόνος παράδοσης.
- Βελτιώνει την απόδοση των εργασιών προσφέροντας συντομότερες εργασίες, οι οποίες θα πρέπει να εκτελούνται πρώτες και οι οποίες έχουν ως επί το πλείστον μικρότερο χρόνο παράδοσης.
Μη προληπτικό SJF
Στον μη προληπτικό χρονοπρογραμματισμό, μόλις ο κύκλος της CPU κατανεμηθεί σε μια διεργασία, η διεργασία τον κρατάει μέχρι να φτάσει σε κατάσταση αναμονής ή να τερματιστεί.
Εξετάστε τις ακόλουθες πέντε διεργασίες, καθεμία από τις οποίες έχει τον δικό της μοναδικό χρόνο έκρηξης και χρόνο άφιξης.
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Βήμα 0) Τη χρονική στιγμή = 0, το P4 φτάνει και ξεκινά την εκτέλεση.
Βήμα 1) Τη χρονική στιγμή = 1, φτάνει η διεργασία P3. Αλλά η P4 χρειάζεται ακόμα 2 μονάδες εκτέλεσης για να ολοκληρωθεί. Θα συνεχίσει την εκτέλεση.
Βήμα 2) Τη στιγμή = 2, η διαδικασία P1 φτάνει και προστίθεται στην ουρά αναμονής. Το P4 θα συνεχίσει την εκτέλεση.
Βήμα 3) Τη στιγμή = 3, η διεργασία P4 θα ολοκληρώσει την εκτέλεσή της. Συγκρίνεται ο χρόνος ριπής των P3 και P1. Η διαδικασία P1 εκτελείται επειδή ο χρόνος ριπής της είναι μικρότερος σε σύγκριση με το P3.
Βήμα 4) Τη στιγμή = 4, η διαδικασία P5 φτάνει και προστίθεται στην ουρά αναμονής. Το P1 θα συνεχίσει την εκτέλεση.
Βήμα 5) Τη στιγμή = 5, η διαδικασία P2 φτάνει και προστίθεται στην ουρά αναμονής. Το P1 θα συνεχίσει την εκτέλεση.
Βήμα 6) Τη στιγμή = 9, η διεργασία P1 θα ολοκληρώσει την εκτέλεσή της. Συγκρίνεται ο χρόνος ριπής των P3, P5 και P2. Η διαδικασία P2 εκτελείται επειδή ο χρόνος ριπής της είναι ο χαμηλότερος.
Βήμα 7) Τη χρονική στιγμή = 10, το P2 εκτελείται και οι P3 και P5 βρίσκονται στην ουρά αναμονής.
Βήμα 8) Τη στιγμή = 11, η διεργασία P2 θα ολοκληρώσει την εκτέλεσή της. Συγκρίνεται ο χρόνος ριπής των P3 και P5. Η διαδικασία P5 εκτελείται επειδή ο χρόνος ριπής της είναι μικρότερος.
Βήμα 9) Τη στιγμή = 15, η διεργασία P5 θα ολοκληρώσει την εκτέλεσή της.
Βήμα 10) Τη στιγμή = 23, η διεργασία P3 θα ολοκληρώσει την εκτέλεσή της.
Βήμα 11) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.
Wait time P4 = 0 - 0 = 0 P1 = 3 - 2 = 1 P2 = 9 - 5 = 4 P5 = 11 - 4 = 7 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2
Προληπτικό SJF
Στον Προληπτικό Προγραμματισμό SJF, οι εργασίες τοποθετούνται στην ουρά ετοιμότητας καθώς έρχονται. Μια διεργασία με τον συντομότερο χρόνο burst ξεκινά την εκτέλεση. Εάν φτάσει μια διεργασία με ακόμη μικρότερο χρόνο burst, η τρέχουσα διεργασία αφαιρείται ή προαποβάλλεται από την εκτέλεση και στην μικρότερη εργασία εκχωρείται ένας κύκλος CPU.
Σκεφτείτε τις ακόλουθες πέντε διαδικασίες:
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Βήμα 0) Τη χρονική στιγμή = 0, το P4 φτάνει και ξεκινά την εκτέλεση.
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Βήμα 1) Τη χρονική στιγμή = 1, φτάνει η διεργασία P3. Αλλά η P4 έχει μικρότερο χρόνο burst. Θα συνεχίσει την εκτέλεση.
Βήμα 2) Τη στιγμή = 2, η διεργασία P1 φθάνει με χρόνο ριπής = 6. Ο χρόνος ριπής είναι μεγαλύτερος από αυτόν του P4. Ως εκ τούτου, το P4 θα συνεχίσει να εκτελείται.
Βήμα 3) Τη στιγμή = 3, η διεργασία P4 θα ολοκληρώσει την εκτέλεσή της. Συγκρίνεται ο χρόνος ριπής των P3 και P1. Η διαδικασία P1 εκτελείται επειδή ο χρόνος ριπής της είναι μικρότερος.
Βήμα 4) Τη στιγμή = 4, θα φτάσει η διαδικασία P5. Συγκρίνεται ο χρόνος ριπής των P3, P5 και P1. Η διαδικασία P5 εκτελείται επειδή ο χρόνος ριπής της είναι ο μικρότερος. Η διαδικασία P1 είναι προκαταρκτική.
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | Απομένουν 5 στα 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Βήμα 5) Τη χρονική στιγμή = 5, θα φτάσει η διεργασία P2. Συγκρίνεται ο χρόνος έκρηξης των P1, P2, P3 και P5. Η διεργασία P2 εκτελείται επειδή ο χρόνος έκρηξης της είναι ο ελάχιστος. Η διεργασία P5 προεκτελείται.
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | Απομένουν 5 στα 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Απομένουν 3 στα 4 | 4 |
Βήμα 6) Τη χρονική στιγμή = 6, το P2 εκτελείται.
Βήμα 7) Τη χρονική στιγμή = 7, η P2 ολοκληρώνει την εκτέλεσή της. Συγκρίνεται ο χρόνος έκρηξης των P1, P3 και P5. Η διεργασία P5 εκτελείται επειδή ο χρόνος έκρηξης της είναι μικρότερος.
| Ουρά διαδικασίας | Ώρα έκρηξης | Ωρα άφιξης |
|---|---|---|
| P1 | Απομένουν 5 στα 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Απομένουν 3 στα 4 | 4 |
Βήμα 8) Τη χρονική στιγμή = 10, η P5 θα ολοκληρώσει την εκτέλεσή της. Ο χρόνος έκρηξης των P1 και P3 συγκρίνεται. Η διεργασία P1 εκτελείται επειδή ο χρόνος έκρηξης της είναι μικρότερος.
Βήμα 9) Τη χρονική στιγμή = 15, η P1 ολοκληρώνει την εκτέλεσή της. Η P3 είναι η μόνη διεργασία που απομένει. Θα ξεκινήσει την εκτέλεση.
Βήμα 10) Τη χρονική στιγμή = 23, το P3 ολοκληρώνει την εκτέλεσή του.
Βήμα 11) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.
Wait time P4 = 0 - 0 = 0 P1 = (3 - 2) + 6 = 7 P2 = 5 - 5 = 0 P5 = 4 - 4 + 2 = 2 P3 = 15 - 1 = 14
Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6
Πλεονεκτήματα του SJF
Ακολουθούν τα οφέλη/πλεονεκτήματα της χρήσης της μεθόδου SJF:
- Το SJF χρησιμοποιείται συχνά για μακροπρόθεσμο προγραμματισμό.
- Μειώνει τον μέσο χρόνο αναμονής σε σχέση με τον αλγόριθμο FIFO (First In First Out).
- Η μέθοδος SJF δίνει τον χαμηλότερο μέσο χρόνο αναμονής για ένα συγκεκριμένο σύνολο διεργασιών.
- Είναι κατάλληλο για εργασίες που εκτελούνται κατά παρτίδες, όπου οι χρόνοι εκτέλεσης είναι γνωστοί εκ των προτέρων.
- Για το σύστημα παρτίδων του μακροπρόθεσμου προγραμματισμού, μπορεί να ληφθεί μια εκτίμηση χρόνου ριπής από την περιγραφή εργασίας.
- Για τον βραχυπρόθεσμο προγραμματισμό, πρέπει να προβλέψουμε την τιμή του επόμενου χρόνου ριπής.
- Είναι πιθανώς βέλτιστο όσον αφορά τον μέσο χρόνο ολοκλήρωσης.
Μειονεκτήματα/Μειονεκτήματα του SJF
Ακολουθούν ορισμένα μειονεκτήματα/μειονεκτήματα του αλγορίθμου SJF:
- Ο χρόνος ολοκλήρωσης της εργασίας πρέπει να είναι γνωστός νωρίτερα, αλλά είναι δύσκολο να προβλεφθεί.
- Συχνά χρησιμοποιείται σε σύστημα παρτίδων για μακροπρόθεσμο προγραμματισμό.
- Το SJF δεν μπορεί να εφαρμοστεί για Προγραμματισμός CPU βραχυπρόθεσμα. Αυτό συμβαίνει επειδή δεν υπάρχει συγκεκριμένη μέθοδος για την πρόβλεψη της διάρκειας της επερχόμενης έκρηξης της CPU.
- Αυτός ο αλγόριθμος μπορεί να προκαλέσει πολύ μεγάλους χρόνους ανάκαμψης ή λιμοκτονία.
- Απαιτεί γνώση της διάρκειας μιας διαδικασίας ή εργασίας.
- Οδηγεί σε λιμοκτονία που δεν μειώνει τον μέσο χρόνο ολοκλήρωσης.
- Είναι δύσκολο να γνωρίζουμε τη διάρκεια του επερχόμενου αιτήματος CPU.
- Ο χρόνος που έχει παρέλθει θα πρέπει να καταγράφεται, γεγονός που έχει ως αποτέλεσμα μεγαλύτερη επιβάρυνση του επεξεργαστή.
