FCFS Scheduling Algorithm: What is, Παράδειγμα προγράμματος

Τι είναι η μέθοδος First Come First Serve;

First Come First Serve (FCFS) είναι ένας αλγόριθμος προγραμματισμού λειτουργικού συστήματος που εκτελεί αυτόματα αιτήματα και διεργασίες σε ουρά κατά σειρά άφιξης τους. Είναι ο ευκολότερος και απλούστερος αλγόριθμος προγραμματισμού CPU. Σε αυτόν τον τύπο αλγορίθμου, οι διεργασίες που ζητούν πρώτα από την CPU λαμβάνουν πρώτα την κατανομή της CPU. Αυτή η διαχείριση γίνεται με μια ουρά FIFO. Η πλήρης μορφή του FCFS είναι First Come First Serve.

Καθώς η διεργασία εισέρχεται στην ουρά ετοιμότητας, το PCB της (Μπλοκ Ελέγχου Διαδικασίας) συνδέεται με την ουρά της ουράς και, όταν η CPU απελευθερωθεί, θα πρέπει να αντιστοιχιστεί στη διεργασία στην αρχή της ουράς.

Χαρακτηριστικά της μεθόδου FCFS

Υποστηρίζει αλγόριθμο μη προληπτικού και προληπτικού προγραμματισμού.
Οι εργασίες εκτελούνται πάντα με σειρά προτεραιότητας.
Είναι εύκολο να εφαρμοστεί και να χρησιμοποιηθεί.
Αυτή η μέθοδος είναι χαμηλής απόδοσης και ο γενικός χρόνος αναμονής είναι αρκετά υψηλός.

Παράδειγμα προγραμματισμού FCFS

Ένα πραγματικό παράδειγμα της μεθόδου FCFS είναι η αγορά ενός εισιτηρίου κινηματογράφου στο γκισέ εισιτηρίων. Σε αυτόν τον αλγόριθμο προγραμματισμού, ένα άτομο εξυπηρετείται σύμφωνα με τον τρόπο ουράς. Αυτός που φτάνει πρώτος στην ουρά αγοράζει πρώτα το εισιτήριο και μετά το επόμενο. Αυτό θα συνεχιστεί έως ότου το τελευταίο άτομο στην ουρά αγοράσει το εισιτήριο. Χρησιμοποιώντας αυτόν τον αλγόριθμο, η διαδικασία της CPU λειτουργεί με παρόμοιο τρόπο.

Πώς λειτουργεί το FCFS; Υπολογισμός μέσου χρόνου αναμονής

Ακολουθεί ένα παράδειγμα πέντε διεργασιών που φτάνουν σε διαφορετικές χρονικές στιγμές. Κάθε διαδικασία έχει διαφορετικό χρόνο ριπής.

Διαδικασία	Ώρα έκρηξης	Ωρα άφιξης
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Χρησιμοποιώντας τον αλγόριθμο προγραμματισμού FCFS, αυτές οι διεργασίες αντιμετωπίζονται ως εξής.

Βήμα 1) Η διαδικασία ξεκινά με το P4 που έχει χρόνο άφιξης 0

Βήμα 2) Την ώρα=1, φτάνει το P3. Το P4 εκτελείται ακόμα. Ως εκ τούτου, το P3 διατηρείται σε μια ουρά.

Διαδικασία	Ώρα έκρηξης	Ωρα άφιξης
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Βήμα 3) Τη στιγμή= 2, φτάνει το P1 που διατηρείται στην ουρά.

Διαδικασία	Ώρα έκρηξης	Ωρα άφιξης
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Βήμα 4) Τη στιγμή=3, η διαδικασία P4 ολοκληρώνει την εκτέλεσή της.

Βήμα 5) Στο time=4, το P3, το οποίο είναι πρώτο στην ουρά, ξεκινά την εκτέλεση.

Διαδικασία	Ώρα έκρηξης	Ωρα άφιξης
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Βήμα 6) Τη στιγμή =5, φτάνει το P2 και διατηρείται σε ουρά.

Διαδικασία	Ώρα έκρηξης	Ωρα άφιξης
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Βήμα 7) Τη στιγμή 11, το P3 ολοκληρώνει την εκτέλεσή του.

Βήμα 8) Τη στιγμή=11, το P1 ξεκινά την εκτέλεση. Έχει χρόνο ριπής 6. Ολοκληρώνει την εκτέλεση στο χρονικό διάστημα 17

Βήμα 9) Την ώρα=17, το P5 ξεκινά την εκτέλεση. Έχει χρόνο ριπής 4. Ολοκληρώνει την εκτέλεση στο χρόνο=21

Βήμα 10) Τη στιγμή=21, το P2 ξεκινά την εκτέλεση. Έχει χρόνο ριπής 2. Ολοκληρώνει την εκτέλεση στο χρονικό διάστημα 23

Βήμα 11) Ας υπολογίσουμε τον μέσο χρόνο αναμονής για το παραπάνω παράδειγμα.

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, δεν θα απελευθερώσει ποτέ τη CPU μέχρι να ολοκληρωθεί η εκτέλεση.
Ο μέσος χρόνος αναμονής είναι υψηλός.
Οι σύντομες διεργασίες που βρίσκονται στο πίσω μέρος της ουράς πρέπει να περιμένουν να ολοκληρωθεί η μεγάλη διαδικασία στο μπροστινό μέρος.
Δεν είναι ιδανική τεχνική για συστήματα χρονομερισμού.
Λόγω της απλότητάς του, το FCFS δεν είναι πολύ αποτελεσματικό.

Σύνοψη

Ορισμός: Το FCFS είναι ένας αλγόριθμος προγραμματισμού του λειτουργικού συστήματος που εκτελεί αυτόματα αιτήματα και διεργασίες που βρίσκονται στην ουρά με τη σειρά της άφιξής τους
Υποστηρίζει μη προληπτικό και προληπτικό προγραμματισμό
αλγόριθμος.
Το FCFS σημαίνει First Come First Serve
Ένα πραγματικό παράδειγμα της μεθόδου FCFS είναι η αγορά ενός εισιτηρίου κινηματογράφου στο γκισέ εισιτηρίων.
Είναι η απλούστερη μορφή ενός αλγορίθμου προγραμματισμού CPU
Είναι ένας μη προληπτικός αλγόριθμος προγραμματισμού CPU, επομένως αφού η διαδικασία έχει εκχωρηθεί στην CPU, δεν θα απελευθερώσει ποτέ τη CPU μέχρι να ολοκληρωθεί η εκτέλεση.