Συντομότερη εργασία Πρώτα (SJF): Προληπτικό, Μη Προληπτικό Παράδειγμα
Ναθάνιελ Μπρουκς
Τι είναι ο Συντομότερος Προγραμματισμός Πρώτης Εργασίας;
Πρώτα η συντομότερη εργασία (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, οι εργασίες τοποθετούνται στην ουρά έτοιμων καθώς έρχονται. Μια διαδικασία με το συντομότερο χρόνο ριπής ξεκινά την εκτέλεση. Εάν φτάσει μια διεργασία με ακόμη μικρότερο χρόνο ριπής, η τρέχουσα διεργασία αφαιρείται ή αποκλείεται από την εκτέλεση και η μικρότερη εργασία εκχωρείται σε κύκλο 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 έχει μικρότερο χρόνο ριπής. Θα συνεχίσει να εκτελείται.
Βήμα 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.
- Ο χρόνος που έχει παρέλθει πρέπει να καταγράφεται, που έχει ως αποτέλεσμα μεγαλύτερο κόστος στον επεξεργαστή.
Σύνοψη
- Ο SJF είναι ένας αλγόριθμος στον οποίο η διεργασία που έχει τον μικρότερο χρόνο εκτέλεσης επιλέγεται για την επόμενη εκτέλεση.
- Ο Προγραμματισμός SJF σχετίζεται με κάθε εργασία ως μονάδα χρόνου προς ολοκλήρωση.
- Αυτή η μέθοδος αλγορίθμου είναι χρήσιμη για επεξεργασία τύπου παρτίδας, όπου η αναμονή για την ολοκλήρωση των εργασιών δεν είναι κρίσιμη.
- Υπάρχουν βασικά δύο τύποι μεθόδων SJF 1) Μη προληπτική SJF και 2) Προληπτική SJF.
- Στον μη προληπτικό προγραμματισμό, μόλις ο κύκλος της CPU εκχωρηθεί στην επεξεργασία, η διαδικασία τον κρατά μέχρι να φτάσει σε κατάσταση αναμονής ή να τερματιστεί.
- Στον Προληπτικό Προγραμματισμό SJF, οι εργασίες τοποθετούνται στην ουρά έτοιμων καθώς έρχονται.
- Παρόλο που ξεκινά μια διαδικασία με σύντομο χρόνο ριπής, η τρέχουσα διεργασία αφαιρείται ή αποκλείεται από την εκτέλεση και η εργασία που είναι μικρότερη εκτελείται 1η.
- Το SJF χρησιμοποιείται συχνά για μακροπρόθεσμο προγραμματισμό.
- Μειώνει τον μέσο χρόνο αναμονής μέσω του αλγόριθμου FIFO (First in First Out).
- Στον προγραμματισμό SJF, ο χρόνος ολοκλήρωσης της εργασίας πρέπει να είναι γνωστός νωρίτερα, αλλά είναι δύσκολο να προβλεφθεί.
- Το SJF δεν μπορεί να εφαρμοστεί για βραχυπρόθεσμο προγραμματισμό CPU. Αυτό συμβαίνει επειδή δεν υπάρχει συγκεκριμένη μέθοδος για την πρόβλεψη της διάρκειας της επερχόμενης έκρηξης της CPU.
