In deze tutorial gaan we een belangrijk concept leren in CPU Process Scheduling Algorithms. De belangrijke conceptnaam is First Come First Serve. Dit is het basisalgoritme dat elke student moet leren om alle basisprincipes van CPU-procesplanningsalgoritmen te begrijpen.
Wie het eerst komt, het eerst maalt, maakt de weg vrij voor het begrijpen van andere algoritmen. Dit algoritme kan veel nadelen hebben. Maar deze nadelen creëerden zeer nieuwe en efficiënte algoritmen. Het is dus onze verantwoordelijkheid om meer te weten te komen over wie het eerst komt, het eerst maalt CPU-procesplanningsalgoritmen.
gratis versus gratis
Belangrijke afkortingen
- CPU - - - > Centrale verwerkingseenheid
- FCFS - - - > Wie het eerst komt, het eerst maalt
- AT - - - > Aankomsttijd
- BT - - - > Bursttijd
- WT - - - > Wachttijd
- TAT - - - > Doorlooptijd
- CT - - - > Voltooiingstijd
- FIFO - - - > Eerst in, eerst uit
Wie het eerst komt, het eerst maalt
Wie het eerst komt, het eerst maalt, is het CPU-planningsalgoritme, kortweg FCFS genoemd, en is het eerste algoritme van het CPU-procesplanningsalgoritme. Bij het First Come First Serve-algoritme zorgen we ervoor dat het proces lineair wordt uitgevoerd.
Dit betekent dat het proces dat het eerst in de wachtrij komt, als eerste wordt uitgevoerd. Dit laat zien dat het First Come First Serve-algoritme het First In First Out (FIFO)-principe volgt.
Het First Come First Serve-algoritme kan op pre-emptieve en niet-pre-emptieve wijze worden uitgevoerd. Voordat we op de voorbeelden ingaan, moeten we eerst begrijpen wat een preventieve en niet-preëmptieve benadering is bij CPU-procesplanning.
Preëmptieve aanpak
In dit geval van preventieve procesplanning wijst het besturingssysteem de bronnen toe aan een proces voor een vooraf bepaalde tijdsperiode. Het proces gaat tijdens de toewijzing van middelen over van de actieve status naar de gereedstatus of van de wachtstatus naar de gereedstatus. Deze omschakeling vindt plaats omdat de CPU voorrang kan geven aan andere processen en het momenteel actieve proces kan vervangen door het proces met hogere prioriteit.
Niet-preëmptieve aanpak
In dit geval van niet-preëmptieve procesplanning kan de resource niet uit een proces worden gehaald voordat het proces is voltooid. Wanneer een lopend proces eindigt en overgaat naar de wachtstatus, worden bronnen gewisseld.
Konvooi-effect bij wie het eerst komt, het eerst maalt (FCFS)
Convoy Effect is een fenomeen dat voorkomt in het planningsalgoritme genaamd First Come First Serve (FCFS). Het wie het eerst komt, het eerst maalt planningsalgoritme vindt plaats op een niet-preventieve manier.
De niet-preventieve manier betekent dat als de uitvoering van een proces of taak wordt gestart, het besturingssysteem het proces of de taak moet voltooien. Totdat het proces of de taak nul is, begint het nieuwe of volgende proces of de volgende taak niet met de uitvoering ervan. De definitie van niet-preëmptieve planning in termen van besturingssysteem betekent dat de Central Processing Unit (CPU) volledig toegewijd zal zijn tot het einde van het proces of de taak die als eerste is gestart en dat het nieuwe proces of de nieuwe taak pas wordt uitgevoerd nadat het oudere proces of de taak is voltooid. functie.
Er kunnen enkele gevallen zijn waarin de Central Processing Unit (CPU) te veel tijd besteedt. Dit komt omdat bij de niet-preëmptieve benadering van het planningsalgoritme 'wie het eerst komt, het eerst maalt', de processen of de taken in seriële volgorde worden gekozen. Hierdoor nemen kortere taken of processen achter de grotere processen of taken te veel tijd in beslag om de uitvoering ervan te voltooien. Hierdoor is de wachttijd, de doorlooptijd en de voltooiingstijd erg hoog.
Dus omdat het eerste proces groot is of de voltooiingstijd te hoog is, treedt dit konvooi-effect in het First Come First Serve-algoritme op.
Laten we aannemen dat het voltooien van een langere taak oneindig veel tijd in beslag neemt. Vervolgens moeten de resterende processen dezelfde oneindige tijd wachten. Als gevolg van dit konvooi-effect dat door de langere baan wordt gecreëerd, neemt de uithongering van de wachtprocessen zeer snel toe. Dit is het grootste nadeel van FCFS CPU-procesplanning.
Kenmerken van FCFS CPU-procesplanning
De kenmerken van FCFS CPU-procesplanning zijn:
- De implementatie is eenvoudig.
- Veroorzaakt geen oorzakelijk verband tijdens het gebruik
- Het hanteert een niet-preëmptieve en preventieve strategie.
- Elke procedure wordt uitgevoerd in de volgorde waarin ze worden ontvangen.
- Aankomsttijd wordt gebruikt als selectiecriterium voor procedures.
Voordelen van FCFS CPU-procesplanning
De voordelen van FCFS CPU-procesplanning zijn:
- Om processen toe te wijzen, wordt gebruik gemaakt van de First In First Out-wachtrij.
- Het FCFS CPU-planningsproces is eenvoudig en eenvoudig te implementeren.
- In de FCFS-situatie met preventieve planning is er geen kans op procesuitval.
- Omdat er geen rekening wordt gehouden met procesprioriteit, is het een billijk algoritme.
Nadelen van FCFS CPU-procesplanning
De nadelen van FCFS CPU-procesplanning zijn:
- FCFS CPU-planningsalgoritme heeft een lange wachttijd
- FCFS CPU-planning geeft de voorkeur aan CPU boven invoer- of uitvoerbewerkingen
- Bij FCFS bestaat de kans op het optreden van het konvooi-effect
- Omdat FCFS zo eenvoudig is, is het vaak niet erg effectief. Langere wachttijden gaan hiermee gepaard. Alle andere bestellingen blijven inactief als de CPU bezig is met het verwerken van een tijdrovende bestelling.
Problemen met het CPU-planningsalgoritme dat het eerst komt, het eerst maalt
lezen uit een csv-bestand in Java
Voorbeeld
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
Niet-preëmptieve aanpak
Laten we dit probleem nu oplossen met behulp van het planningsalgoritme genaamd First Come First Serve in een niet-preëmptieve aanpak.
Gantt-diagram voor het bovenstaande Voorbeeld 1 is:
java mvc
Turn Around Time = Voltooiingstijd - Aankomsttijd
Wachttijd = Doorlooptijd - Bursttijd
Oplossing voor de bovenstaande vraag Voorbeeld 1
Ja nee | Proces-ID | Aankomsttijd | Burst-tijd | Doorlooptijd | Keer de tijd om | Wachttijd | |
---|---|---|---|---|---|---|---|
1 | P1 | A | 0 | 9 | 9 | 9 | 0 |
2 | P2 | B | 1 | 3 | 12 | elf | 8 |
3 | P3 | C | 1 | 2 | 14 | 13 | elf |
4 | P4 | D | 1 | 4 | 18 | 17 | 13 |
5 | P5 | EN | 2 | 3 | eenentwintig | 19 | 16 |
6 | P6 | F | 3 | 2 | 23 | twintig | 18 |
De gemiddelde voltooiingstijd is:
Gemiddelde CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Gemiddelde CT = 97/6
Gemiddelde CT = 16,16667
De gemiddelde wachttijd is:
Gemiddelde WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Gemiddelde WT = 66 / 6
Gemiddelde WT = 11
De gemiddelde doorlooptijd is:
Gemiddelde TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
dijkstra
Gemiddelde TAT = 89 / 6
Gemiddelde TAT = 14,83334
Dit is hoe de FCFS wordt opgelost in de niet-preëmptieve aanpak.
Laten we nu begrijpen hoe ze kunnen worden opgelost met een preventieve aanpak
Preëmptieve aanpak
Laten we dit probleem nu oplossen met behulp van het planningsalgoritme genaamd First Come First Serve in een preventieve aanpak.
Bij Pre Emptive Approach zoeken we naar het beste proces dat beschikbaar is
Gantt-diagram voor het bovenstaande Voorbeeld 1 is:
een array in Java
Ja nee | Proces-ID | Aankomsttijd | Burst-tijd | Doorlooptijd | Keer de tijd om | Wachttijd | |
---|---|---|---|---|---|---|---|
1 | P1 | A | 0 | 9 | 23 | 23 | 14 |
2 | P2 | B | 1 | 3 | 8 | 7 | 4 |
3 | P3 | C | 1 | 2 | 3 | 2 | 0 |
4 | P4 | D | 1 | 4 | vijftien | 14 | 10 |
5 | P5 | EN | 2 | 3 | elf | 9 | 7 |
6 | P6 | F | 3 | 2 | 5 | 2 | 0 |
volgende → ← vorige Om het probleem van het verspillen van de weksignalen op te lossen, stelde Dijkstra een aanpak voor waarbij alle weksignalen worden opgeslagen. Dijkstra stelt dat de producent, in plaats van de wake-up calls rechtstreeks aan de consument te geven, de wake-up call in een variabele kan opslaan. Elke consument kan het lezen wanneer hij dat nodig heeft. Semafoor zijn de variabelen waarin alle wake-up calls zijn opgeslagen die van producent naar consument worden verzonden. Het is een variabele waarop lezen, wijzigen en bijwerken automatisch gebeurt in de kernelmodus. Semafoor kan niet worden geïmplementeerd in de gebruikersmodus, omdat er altijd een race-condition kan ontstaan wanneer twee of meer processen tegelijkertijd toegang proberen te krijgen tot de variabele. Het heeft altijd ondersteuning van het besturingssysteem nodig om te worden geïmplementeerd. Afhankelijk van de vraag van de situatie kan Semaphore in twee categorieën worden verdeeld.
We zullen ze allemaal in detail bespreken. |