Τι είναι η μέθοδος First Come First Serve;
Το First Come First Serve (FCFS) είναι ένας αλγόριθμος προγραμματισμού λειτουργικού συστήματος που εκτελεί αυτόματα αιτήματα και διαδικασίες στην ουρά κατά την άφιξή τους. Είναι ο ευκολότερος και απλούστερος αλγόριθμος προγραμματισμού CPU. Σε αυτόν τον τύπο αλγορίθμου, οι διαδικασίες που ζητούν πρώτα τη CPU λαμβάνουν πρώτα την κατανομή της CPU. Αυτό γίνεται με μια ουρά FIFO. Η πλήρης μορφή του FCFS είναι το First Come First Serve.
Καθώς η διαδικασία εισέρχεται στην έτοιμη ουρά, το PCB του (Process Control Block) συνδέεται με την ουρά της ουράς και, όταν η CPU είναι ελεύθερη, θα πρέπει να εκχωρηθεί στη διαδικασία στην αρχή της ουράς.
Σε αυτό το σεμινάριο λειτουργικού συστήματος, θα μάθετε:
- Τι είναι η μέθοδος First Come First Serve;
- Χαρακτηριστικά της μεθόδου FCFS
- Παράδειγμα προγραμματισμού FCFS
- Πώς λειτουργεί το FCFS; Υπολογισμός του μέσου χρόνου αναμονής
- Πλεονεκτήματα του FCFS
- Μειονεκτήματα του FCFS
Χαρακτηριστικά της μεθόδου FCFS
- Υποστηρίζει μη προληπτικό και προληπτικό αλγόριθμο προγραμματισμού.
- Οι εργασίες εκτελούνται πάντα βάσει προτεραιότητας.
- Είναι εύκολο να εφαρμοστεί και να χρησιμοποιηθεί.
- Αυτή η μέθοδος έχει χαμηλή απόδοση και ο γενικός χρόνος αναμονής είναι αρκετά υψηλός.
Παράδειγμα προγραμματισμού FCFS
Ένα πραγματικό παράδειγμα της μεθόδου FCFS είναι η αγορά εισιτηρίου ταινίας στον πάγκο εισιτηρίων. Σε αυτόν τον αλγόριθμο προγραμματισμού, ένα άτομο εξυπηρετείται σύμφωνα με τον τρόπο ουράς. Το άτομο που φτάνει πρώτη στην ουρά αγοράζει πρώτα το εισιτήριο και μετά το επόμενο. Αυτό θα συνεχιστεί έως ότου το τελευταίο άτομο στην ουρά αγοράσει το εισιτήριο. Χρησιμοποιώντας αυτόν τον αλγόριθμο, η διαδικασία της CPU λειτουργεί με παρόμοιο τρόπο.
Πώς λειτουργεί το FCFS; Υπολογισμός του μέσου χρόνου αναμονής
Ακολουθεί ένα παράδειγμα πέντε διαδικασιών που φθάνουν σε διαφορετικές ώρες. Κάθε διαδικασία έχει διαφορετικό χρόνο έκρηξης.
| Επεξεργάζομαι, διαδικασία | Χρόνος έκρηξης | Ωρα άφιξης |
| Ρ1 | 6 | 2 |
| Ρ2 | 3 | 5 |
| Ρ3 | 8 | 1 |
| Ρ4 | 3 | 0 |
| Ρ5 | 4 | 4 |
Χρησιμοποιώντας τον αλγόριθμο προγραμματισμού FCFS, αυτές οι διαδικασίες αντιμετωπίζονται ως εξής.
Βήμα 0) Η διαδικασία ξεκινά με το P4 που έχει ώρα άφιξης 0
Βήμα 1) Τη στιγμή = 1, φτάνει το P3. Το P4 εξακολουθεί να εκτελείται. Ως εκ τούτου, το P3 διατηρείται σε ουρά.
| Επεξεργάζομαι, διαδικασία | Χρόνος έκρηξης | Ωρα άφιξης |
| Ρ1 | 6 | 2 |
| Ρ2 | 3 | 5 |
| Ρ3 | 8 | 1 |
| Ρ4 | 3 | 0 |
| Ρ5 | 4 | 4 |
Βήμα 2) Τη στιγμή = 2, φτάνει το P1 το οποίο διατηρείται στην ουρά.
| Επεξεργάζομαι, διαδικασία | Χρόνος έκρηξης | Ωρα άφιξης |
| Ρ1 | 6 | 2 |
| Ρ2 | 3 | 5 |
| Ρ3 | 8 | 1 |
| Ρ4 | 3 | 0 |
| Ρ5 | 4 | 4 |
Βήμα 3) Τη στιγμή = 3, η διαδικασία P4 ολοκληρώνει την εκτέλεσή της.
Βήμα 4) Τη στιγμή = 4, το P3, το οποίο είναι πρώτο στην ουρά, ξεκινά την εκτέλεση.
| Επεξεργάζομαι, διαδικασία | Χρόνος έκρηξης | Ωρα άφιξης |
| Ρ1 | 6 | 2 |
| Ρ2 | 3 | 5 |
| Ρ3 | 8 | 1 |
| Ρ4 | 3 | 0 |
| Ρ5 | 4 | 4 |
Βήμα 5) Τη στιγμή = 5, φτάνει το P2 και διατηρείται σε ουρά.
| Επεξεργάζομαι, διαδικασία | Χρόνος έκρηξης | Ωρα άφιξης |
| Ρ1 | 6 | 2 |
| Ρ2 | 3 | 5 |
| Ρ3 | 8 | 1 |
| Ρ4 | 3 | 0 |
| Ρ5 | 4 | 4 |
Βήμα 6) Τη στιγμή 11, το P3 ολοκληρώνει την εκτέλεση του.
Βήμα 7) Τη στιγμή = 11, το P1 ξεκινά την εκτέλεση. Έχει χρόνο έκρηξης 6. Ολοκληρώνει την εκτέλεση στο χρονικό διάστημα 17
Βήμα 8) Τη στιγμή = 17, το P5 ξεκινά την εκτέλεση. Έχει χρόνο έκρηξης 4. Ολοκληρώνει την εκτέλεση στο χρόνο = 21
Βήμα 9) Τη στιγμή = 21, το P2 ξεκινά την εκτέλεση. Έχει χρόνο έκρηξης 2. Ολοκληρώνει την εκτέλεση στο χρονικό διάστημα 23
Βήμα 10) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5 = 17-4 = 13
P2 = 21-5 = 16
Μέσος χρόνος αναμονής
= 40/5 = 8
Πλεονεκτήματα του FCFS
Εδώ είναι τα πλεονεκτήματα / οφέλη από τη χρήση αλγορίθμου προγραμματισμού FCFS:
- Η απλούστερη μορφή ενός αλγορίθμου προγραμματισμού CPU
- Εύκολο στον προγραμματισμό
- ΠΡΩΤΟΣ έρχεται πρώτος εξυπηρετείται
Μειονεκτήματα του FCFS
Εδώ είναι τα μειονεκτήματα / μειονεκτήματα της χρήσης αλγορίθμου προγραμματισμού FCFS:
- Είναι ένας αλγόριθμος προγραμματισμού μη προληπτικών CPU, οπότε αφού η διαδικασία εκχωρηθεί στην CPU, δεν θα κυκλοφορήσει ποτέ τον επεξεργαστή μέχρι να ολοκληρωθεί η εκτέλεση.
- Ο μέσος χρόνος αναμονής είναι υψηλός.
- Οι σύντομες διαδικασίες που βρίσκονται στο πίσω μέρος της ουράς πρέπει να περιμένουν να ολοκληρωθεί η μακρά διαδικασία στο μπροστινό μέρος.
- Δεν είναι μια ιδανική τεχνική για συστήματα κατανομής χρόνου.
- Λόγω της απλότητάς του, το FCFS δεν είναι πολύ αποτελεσματικό.
Περίληψη:
- Ορισμός: Το FCFS είναι ένας αλγόριθμος προγραμματισμού λειτουργικού συστήματος που εκτελεί αυτόματα αιτήματα και διαδικασίες στην ουρά με τη σειρά άφιξής τους
- Υποστηρίζει μη προληπτικό και προληπτικό προγραμματισμό
- αλγόριθμος.
- Το FCFS σημαίνει First Come First Serve
- Ένα πραγματικό παράδειγμα της μεθόδου FCFS είναι η αγορά εισιτηρίου ταινίας στον πάγκο εισιτηρίων.
- Είναι η απλούστερη μορφή ενός αλγορίθμου προγραμματισμού CPU
- Είναι ένας αλγόριθμος προγραμματισμού μη προληπτικών CPU, οπότε αφού η διαδικασία εκχωρηθεί στην CPU, δεν θα κυκλοφορήσει ποτέ τον επεξεργαστή μέχρι να ολοκληρωθεί η εκτέλεση.