I den här handledningen ska vi lära oss ett viktigt koncept i CPU Process Scheduling Algorithms. Det viktiga konceptnamnet är först till kvarn som gäller. Detta är den grundläggande algoritmen som varje elev måste lära sig för att förstå alla grunderna i CPU Process Scheduling Algorithms.
Först till kvarn tjänar banar väg för förståelse av andra algoritmer. Denna algoritm kan ha många nackdelar. Men dessa nackdelar skapade mycket nya och effektiva algoritmer. Så, det är vårt ansvar att lära oss om Först till kvarn Process Scheduling Algoritmer för CPU-processer.
Viktiga förkortningar
- CPU - - - > Central Processing Unit
- FCFS - - - > Först till kvarn gäller
- AT - - - > Ankomsttid
- BT - - - > Burst Time
- WT - - - > Väntetid
- TAT - - - > Turn Around Time
- CT - - - > Sluttid
- FIFO - - - > Först in först ut
Först till kvarn
Först till kvarn får CPU Scheduling Algorithm, kort känd som FCFS, är den första algoritmen för CPU Process Scheduling Algorithm. I First Come First Serve Algorithm är det vi gör att tillåta processen att utföras på linjärt sätt.
Detta betyder att vilken process som går in i processen som går in i färdigkön först exekveras först. Detta visar att Först till kvarn-algoritmen följer Först In Först Ut-principen (FIFO).
Först till kvarn-algoritmen kan exekveras i förebyggande och icke förebyggande sätt. Innan vi går in på exempel, låt oss förstå vad som är Pre Emptive och Non Pre Emptive Approach i CPU Process Scheduling.
Pre Emptive Approach
I detta fall av Pre Emptive Process Scheduling tilldelar operativsystemet resurserna till en process under en förutbestämd tidsperiod. Processen övergår från körtillstånd till redoläge eller från vänteläge till redoläge under resursallokering. Denna växling sker eftersom CPU:n kan tilldela andra processer prioritet och ersätta den för närvarande aktiva processen med den högre prioritetsprocessen.
nat vs säng
Icke förebyggande tillvägagångssätt
I det här fallet med icke förebyggande processschemaläggning kan resursen inte dras från en process innan processen har körts färdig. När en pågående process avslutas och övergår till vänteläge, byts resurser.
Konvojeffekt Först till kvarn gäller (FCFS)
Convoy Effect är ett fenomen som förekommer i Scheduling Algorithm som heter First Come First Serve (FCFS). Först till kvarn-först till kvarn-schemaalgoritmen sker på ett icke-förebyggande sätt.
Det icke-förebyggande sättet innebär att om en process eller ett jobb påbörjas, måste operativsystemet slutföra sin process eller jobb. Förrän processen eller jobbet är noll börjar den nya eller nästa processen eller jobbet inte köras. Definitionen av icke-förebyggande schemaläggning i termer av operativsystem innebär att den centrala bearbetningsenheten (CPU) kommer att vara helt dedikerad till slutet av processen eller jobbet som startas först och den nya processen eller jobbet exekveras först efter att den äldre processen har avslutats eller jobb.
Det kan finnas några fall som kan göra att den centrala bearbetningsenheten (CPU) tilldelar för mycket tid. Detta beror på att i Först till kvarn-först till kvarn-schemaläggningsalgoritmen Non Preemptive Approach väljs processerna eller jobben i seriell ordning. På grund av detta tar kortare jobb eller processer bakom de större processerna eller jobben för lång tid att slutföra dess genomförande. På grund av detta är väntetiden, omläggningstiden och slutförandetiden mycket lång.
Så här, eftersom den första processen är stor eller slutförandetiden är för lång, uppstår denna konvojeffekt i Först till kvarn-algoritmen.
Låt oss anta att ett längre jobb tar oändlig tid att slutföra. Sedan måste de återstående processerna vänta på samma oändliga tid. På grund av denna konvojeffekt som skapats av det längre jobbet ökar svälten av väntande processer mycket snabbt. Detta är den största nackdelen med FCFS CPU Process Scheduling.
Egenskaper för FCFS CPU Process Scheduling
Egenskaperna för FCFS CPU Process Scheduling är:
- Implementeringen är enkel.
- Orsakar inga kausaliteter vid användning
- Den antar en icke-förebyggande och förebyggande strategi.
- Den kör varje procedur i den ordning de tas emot.
- Ankomsttid används som urvalskriterium för procedurer.
Fördelar med FCFS CPU Process Scheduling
Fördelarna med FCFS CPU Process Scheduling är:
- För att allokera processer använder den först in först ut-kön.
- FCFS CPU-schemaläggningsprocessen är enkel och enkel att implementera.
- I FCFS-situationen förebyggande schemaläggning finns det ingen chans att processen svälter.
- Eftersom det inte tas hänsyn till processprioritet är det en rättvis algoritm.
Nackdelar med FCFS CPU Process Scheduling
Nackdelarna med FCFS CPU Process Scheduling är:
- FCFS CPU Scheduling Algoritm har lång väntetid
- FCFS CPU-schemaläggning gynnar CPU framför Input- eller Output-operationer
- I FCFS finns det en risk för förekomst av konvojeffekt
- Eftersom FCFS är så rakt på sak är det ofta inte särskilt effektivt. Förlängda väntetider går hand i hand med detta. Alla andra beställningar lämnas inaktiva om CPU:n är upptagen med att bearbeta en tidskrävande beställning.
Problem i algoritmen för schemaläggning av CPU-först till kvarn
bikupa arkitektur
Exempel
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
Icke förebyggande tillvägagångssätt
Låt oss nu lösa det här problemet med hjälp av schemaläggningsalgoritmen som heter Först till kvarn gäller i ett icke förebyggande tillvägagångssätt.
Gantt-diagrammet för ovanstående exempel 1 är:
Linux gratis ipconfig
Turn Around Time = Slutföringstid - Ankomsttid
Väntetid = Vändningstid - Burst Time
Lösning på ovanstående fråga Exempel 1
Ja Nej | Process ID | Ankomst tid | Burst Time | Sluttid | Vändningstid | Väntetid | |
---|---|---|---|---|---|---|---|
1 | P 1 | A | 0 | 9 | 9 | 9 | 0 |
2 | P 2 | B | 1 | 3 | 12 | elva | 8 |
3 | P 3 | C | 1 | 2 | 14 | 13 | elva |
4 | P 4 | D | 1 | 4 | 18 | 17 | 13 |
5 | P 5 | OCH | 2 | 3 | tjugoett | 19 | 16 |
6 | P 6 | F | 3 | 2 | 23 | tjugo | 18 |
Den genomsnittliga slutförandetiden är:
Genomsnittlig CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6
Genomsnittlig CT = 97/6
Genomsnittlig CT = 16,16667
Den genomsnittliga väntetiden är:
Genomsnittlig WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6
Genomsnittlig WT = 66/6
Genomsnittlig WT = 11
Den genomsnittliga omloppstiden är:
Genomsnittlig TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6
t flip flop
Genomsnittlig TAT = 89/6
Genomsnittlig TAT = 14,83334
Så här löses FCFS i Non Pre Emptive Approach.
Låt oss nu förstå hur de kan lösas i Pre Emptive Approach
Pre Emptive Approach
Låt oss nu lösa det här problemet med hjälp av schemaläggningsalgoritmen som heter Först till kvarn i ett förebyggande tillvägagångssätt.
I Pre Emptive Approach söker vi efter den bästa processen som är tillgänglig
Gantt-diagrammet för ovanstående exempel 1 är:
powershell vs bash
Ja Nej | Process ID | Ankomst tid | Burst Time | Sluttid | Vändningstid | Väntetid | |
---|---|---|---|---|---|---|---|
1 | P 1 | A | 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 | femton | 14 | 10 |
5 | P 5 | OCH | 2 | 3 | elva | 9 | 7 |
6 | P 6 | F | 3 | 2 | 5 | 2 | 0 |
nästa → ← föregående För att bli av med problemet med att slösa bort väckningssignalerna föreslog Dijkstra ett tillvägagångssätt som innebär att alla väckningssignaler lagras. Dijkstra säger att istället för att ge väckningssignalerna direkt till konsumenten kan producenten lagra väckningssignalen i en variabel. Alla konsumenter kan läsa den när den behöver göra det. Semafor är de variabler som lagrar hela wake up calls som överförs från producent till konsument. Det är en variabel där läsning, modifiering och uppdatering sker automatiskt i kärnläge. Semaphore kan inte implementeras i användarläget eftersom rastillstånd alltid kan uppstå när två eller flera processer försöker komma åt variabeln samtidigt. Det behöver alltid stöd från operativsystemet för att kunna implementeras. Beroende på efterfrågan på situationen kan Semaphore delas in i två kategorier.
Vi kommer att diskutera var och en i detalj. |