I denne tutorial skal vi lære et vigtigt koncept i CPU Process Scheduling Algoritmer. Det vigtige konceptnavn er først til mølle. Dette er den grundlæggende algoritme, som hver elev skal lære for at forstå alt det grundlæggende i CPU Process Scheduling Algorithms.
First Come First Serve baner vejen for forståelse af andre algoritmer. Denne algoritme kan have mange ulemper. Men disse ulemper skabte meget nye og effektive algoritmer. Så det er vores ansvar at lære om først-til-mølle-processor-procesplanlægningsalgoritmer.
Vigtige forkortelser
- CPU - - - > Central Processing Unit
- FCFS - - - > Først til mølle
- AT - - - > Ankomsttid
- BT - - - > Burst Time
- WT - - - > Ventetid
- TAT - - - > Turn Around Time
- CT - - - > Afslutningstid
- FIFO - - - > First In First Out
Først til mølle
Først til mølle CPU-planlægningsalgoritme kort kendt som FCFS er den første algoritme for CPU-procesplanlægningsalgoritme. I First Come First Serve Algorithm, hvad vi gør, er at tillade processen at udføre på lineær måde.
Dette betyder, at den proces, der går ind i processen, der kommer ind i klarkøen først, udføres først. Dette viser, at først til mølle-algoritmen følger First In First Out-princippet (FIFO).
Først til mølle-algoritmen kan udføres på præemptiv og ikke præemptiv måde. Inden vi går ind i eksempler, lad os forstå, hvad der er præemptiv og ikke præemptiv tilgang i CPU-procesplanlægning.
Præ-emptive tilgang
I dette tilfælde af Pre Emptive Process Scheduling tildeler OS ressourcerne til en proces i en forudbestemt periode. Processen går over fra kørende tilstand til klar tilstand eller fra ventetilstand til klar tilstand under ressourceallokering. Dette skift sker, fordi CPU'en kan tildele andre processer forrang og erstatte den aktuelt aktive proces med den højere prioritetsproces.
Ikke præemptiv tilgang
I dette tilfælde af Non Pre Emptive Process Scheduling kan ressourcen ikke trækkes tilbage fra en proces, før processen er færdig med at køre. Når en kørende proces afsluttes og går over til ventetilstand, skiftes ressourcer.
Konvojeffekt efter først til mølle (FCFS)
Convoy Effect er et fænomen, der forekommer i planlægningsalgoritmen kaldet First Come First Serve (FCFS). Først-til-mølle-planlægningsalgoritmen opstår på en ikke-præventiv måde.
Den ikke-forebyggende måde betyder, at hvis en proces eller opgave startes, skal operativsystemet fuldføre sin proces eller opgave. Indtil processen eller jobbet er nul, starter den nye eller næste proces eller opgave ikke sin udførelse. Definitionen af ikke-forebyggende planlægning med hensyn til operativsystem betyder, at den centrale behandlingsenhed (CPU) vil være fuldstændig dedikeret til slutningen af processen eller jobbet, der først blev startet, og den nye proces eller job udføres først efter afslutning af den ældre proces eller job.
Der kan være nogle få tilfælde, som kan få den centrale behandlingsenhed (CPU) til at bruge for meget tid. Dette skyldes, at i først-til-mølle-planlægningsalgoritmen Non Preemptive Approach, er processerne eller jobs valgt i seriel rækkefølge. På grund af dette tager kortere opgaver eller processer bag de større processer eller opgaver for lang tid at fuldføre deres udførelse. På grund af dette er ventetiden, omløbstiden og færdiggørelsestiden meget høj.
abstrakte metoder
Så her, da den første proces er stor eller færdiggørelsestiden er for høj, så opstår denne konvoj-effekt i først til mølle-algoritmen.
Lad os antage, at et længere job tager uendelig tid at fuldføre. Derefter skal de resterende processer vente i den samme uendelige tid. På grund af denne konvojeffekt, skabt af det længere job, stiger sulten i venteprocesserne meget hurtigt. Dette er den største ulempe ved FCFS CPU Process Scheduling.
Karakteristika for FCFS CPU Process Scheduling
Karakteristikaene ved FCFS CPU Process Scheduling er:
- Implementeringen er enkel.
- Forårsager ingen årsagssammenhænge under brug
- Det vedtager en ikke-forebyggende og forebyggende strategi.
- Den kører hver procedure i den rækkefølge, de modtages.
- Ankomsttid bruges som udvælgelseskriterium for procedurer.
Fordele ved FCFS CPU Process Scheduling
Fordelene ved FCFS CPU Process Scheduling er:
- For at allokere processer bruger den First In First Out-køen.
- FCFS CPU-planlægningsprocessen er ligetil og nem at implementere.
- I FCFS-situationen med forebyggende planlægning er der ingen chance for, at processen sulter.
- Da der ikke tages hensyn til procesprioritet, er det en retfærdig algoritme.
Ulemper ved FCFS CPU Process Scheduling
Ulemperne ved FCFS CPU Process Scheduling er:
- FCFS CPU-planlægningsalgoritme har lang ventetid
- FCFS CPU-planlægning favoriserer CPU frem for input- eller outputoperationer
- I FCFS er der en chance for forekomst af konvojeffekt
- Fordi FCFS er så ligetil, er det ofte ikke særlig effektivt. Det går hånd i hånd med forlængede ventetider. Alle andre ordrer efterlades inaktive, hvis CPU'en er optaget af at behandle en tidskrævende ordre.
Problemer med først til mølle CPU-planlægningsalgoritmen
Eksempel
S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2
Ikke præemptiv tilgang
Lad os nu løse dette problem ved hjælp af planlægningsalgoritmen kaldet først til mølle i en ikke-forebyggende tilgang.
Gantt-diagrammet for ovenstående eksempel 1 er:
sortering tuples python
Turn Around Time = Gennemførelsestid - Ankomsttid
Ventetid = Omløbstid - Burst Time
Løsning på ovenstående spørgsmål Eksempel 1
| Ja Nej | Proces ID | Ankomsttid | Burst Time | Afslutningstid | Vendetid | Ventetid | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | EN | 0 | 9 | 9 | 9 | 0 |
| 2 | P 2 | B | 1 | 3 | 12 | elleve | 8 |
| 3 | P 3 | C | 1 | 2 | 14 | 13 | elleve |
| 4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
| 5 | P 5 | OG | 2 | 3 | enogtyve | 19 | 16 |
| 6 | P 6 | F | 3 | 2 | 23 | tyve | 18 |
Den gennemsnitlige færdiggørelsestid er:
Gennemsnitlig CT = (9 + 12 + 14 + 18 + 21 + 23) / 6
Gennemsnitlig CT = 97/6
Gennemsnitlig CT = 16,16667
Den gennemsnitlige ventetid er:
Gennemsnitlig WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Gennemsnitlig WT = 66/6
Gennemsnitlig WT = 11
Den gennemsnitlige omløbstid er:
Gennemsnitlig TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
Gennemsnitlig TAT = 89/6
Gennemsnitlig TAT = 14,83334
Sådan løses FCFS i Non Pre Emptive Approach.
Lad os nu forstå, hvordan de kan løses i Pre Emptive Approach
Præemptive tilgang
Lad os nu løse dette problem ved hjælp af planlægningsalgoritmen kaldet først til mølle i en præ-emptive tilgang.
I Pre Emptive Approach søger vi efter den bedste proces, der er tilgængelig
prøv catch block i java
Gantt-diagrammet for ovenstående eksempel 1 er:
| Ja Nej | Proces ID | Ankomsttid | Burst Time | Afslutningstid | Vendetid | Ventetid | |
|---|---|---|---|---|---|---|---|
| 1 | P 1 | EN | 0 | 9 | 23 | 23 | 14 |
| 2 | P 2 | B | 1 | 3 | 8 | 7 | 4 |
| 3 | P 3 | C | 1 | 2 | 3 | 2 | 0 |
| 4 | P 4 | D | 1 | 4 | femten | 14 | 10 |
| 5 | P 5 | OG | 2 | 3 | elleve | 9 | 7 |
| 6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
| næste → ← forrige For at slippe af med problemet med at spilde vækkesignalerne foreslog Dijkstra en tilgang, der involverer at gemme alle vækkeopkaldene. Dijkstra anfører, at i stedet for at give wake-up calls direkte til forbrugeren, kan producenten gemme wake-up calls i en variabel. Enhver af forbrugerne kan læse den, når den har brug for det. Semafor er de variable, der gemmer hele wake up calls, der overføres fra producent til forbruger. Det er en variabel, hvor læsning, ændring og opdatering sker automatisk i kernetilstand. Semafor kan ikke implementeres i brugertilstand, fordi racetilstand altid kan opstå, når to eller flere processer forsøger at få adgang til variablen samtidigt. Det har altid brug for support fra operativsystemet for at blive implementeret. I henhold til situationens efterspørgsel kan Semaphore opdeles i to kategorier.
Vi vil diskutere hver enkelt i detaljer. |