logo

Först till kvarn får CPU-processschemaläggning i operativsystem

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

  1. CPU - - - > Central Processing Unit
  2. FCFS - - - > Först till kvarn gäller
  3. AT - - - > Ankomsttid
  4. BT - - - > Burst Time
  5. WT - - - > Väntetid
  6. TAT - - - > Turn Around Time
  7. CT - - - > Sluttid
  8. 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.

FCFS schemaläggningsalgoritmer i OS (operativsystem)

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:

  1. Implementeringen är enkel.
  2. Orsakar inga kausaliteter vid användning
  3. Den antar en icke-förebyggande och förebyggande strategi.
  4. Den kör varje procedur i den ordning de tas emot.
  5. Ankomsttid används som urvalskriterium för procedurer.

Fördelar med FCFS CPU Process Scheduling

Fördelarna med FCFS CPU Process Scheduling är:

  1. För att allokera processer använder den först in först ut-kön.
  2. FCFS CPU-schemaläggningsprocessen är enkel och enkel att implementera.
  3. I FCFS-situationen förebyggande schemaläggning finns det ingen chans att processen svälter.
  4. 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
FCFS schemaläggningsalgoritmer i OS (operativsystem)

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
FCFS schemaläggningsalgoritmer i OS (operativsystem)
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.

  1. Räknar semafor
  2. Binär semafor eller Mutex

Vi kommer att diskutera var och en i detalj.