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