FCFS algoritam raspoređivanja: što je, primjer programa

By: Nathaniel Brooks Nathaniel Brooks
Hours Ažurirano

⚡ Pametni sažetak

Raspoređivanje po principu "prvi dođe, prvi poslužen" pokreće procese točnim redoslijedom kojim stignu u red čekanja, koristeći jednostavan nepreemptivni FIFO pristup koji ga čini najlakšim algoritmom raspoređivanja CPU-a za operativni sustav za implementaciju.

  • 🔄 Definicija: FCFS dodjeljuje CPU procesu koji ga prvi zatraži, upravljajući redom čekanja kao strukturom prvi ušao, prvi izašao (FIFO).
  • ️ Priroda: FCFS nije preemptivni, pa pokrenuti proces zadržava CPU dok ne završi cijelo vrijeme izvršavanja.
  • 🎟️ Analogija: Poput reda za blagajnu, proces koji prvi stigne prvi se poslužuje, a kasniji dolasci čekaju svoj red.
  • 📊 Proračun: Prosječno vrijeme čekanja određuje se prema podređenomtracmjerenjem vremena dolaska svakog procesa od njegovog vremena početka, a zatim usrednjavanjem za sve procese.
  • ???? Učinak konvoja: Jedan dugi proces na početku prisiljava kraće poslove na čekanje, što povećava prosječno vrijeme čekanja i šteti performansama.
  • 🤖 Kut umjetne inteligencije: Strojno učenje predviđa vrijeme neprekidnog rada kako bi se poboljšalo raspoređivanje, a Copilot pomaže u brzom pisanju i testiranju FCFS koda.
Pročitaj više

FCFS algoritam za raspoređivanje u Operating sustav

Što je metoda "prvi dođe prvi posluži"?

Prvi dođe prvi posluži (FCFS) je algoritam za raspoređivanje operacijskog sustava koji automatski izvršava zahtjeve i procese u redu čekanja prema redoslijedu njihovog dolaska. To je najlakši i najjednostavniji algoritam za raspoređivanje CPU-a. U ovoj vrsti algoritma, proces koji prvi zatraži CPU prvi dobiva alokaciju CPU-a. To se upravlja FIFO redom čekanja. Puni oblik FCFS-a je First Come First Service (Prvi dođe, prvi poslužen).

Kako proces ulazi u red čekanja, njegov PCB (blok upravljanja procesom) povezan je s repom reda. Dakle, kada se CPU oslobodi, dodjeljuje se procesu na početku reda.

Karakteristike FCFS metode

Glavne karakteristike metode "tko prvi dođe, prvi melje" navedene su u nastavku:

  • To je nepreventivno algoritam raspoređivanja, tako da proces zadržava CPU dok ne završi svoje vrijeme burst-a.
  • Poslovi se uvijek izvršavaju po načelu tko prvi dođe, prvi poslužen.
  • Jednostavan je za implementaciju i korištenje.
  • Ova metoda ima lošu izvedbu, a općenito vrijeme čekanja je prilično dugo.

Primjer FCFS rasporeda

Primjer FCFS metode iz stvarnog života je kupnja kino ulaznice na blagajni. U ovom algoritmu raspoređivanja, osoba se poslužuje prema redoslijedu čekanja u redu. Osoba koja prva stigne u red prva kupuje ulaznicu, a zatim sljedeća. To se nastavlja sve dok posljednja osoba u redu ne kupi ulaznicu. Korištenjem ovog algoritma, CPU proces radi na sličan način.

Kako radi FCFS? Izračunavanje prosječnog vremena čekanja

Kako bismo razumjeli kako algoritam raspoređuje procese, evo primjera pet procesa koji dolaze u različito vrijeme. Svaki proces ima različito vrijeme naleta.

Proces Vrijeme praska Vrijeme dolaska
P1 6 2
P2 2 5
P3 8 1
P4 3 0
P5 4 4

Korištenjem FCFS algoritma za raspoređivanje, ovim se procesima rukuje na sljedeći način.

Korak 1) Proces počinje s P4, koji ima vrijeme dolaska 0.

Primjer FCFS rasporeda korak 1

Korak 2) U vrijeme=1, stiže P3. P4 se još uvijek izvršava. Stoga se P3 drži u redu čekanja.

Primjer FCFS rasporeda korak 2

Korak 3) U vremenu = 2, P1 stiže i ostaje u redu čekanja.

Primjer FCFS rasporeda korak 3

Korak 4) U vremenu = 3, proces P4 završava svoje izvršavanje.

Primjer FCFS rasporeda korak 4

POVEZANI ČLANCI

Korak 5) U trenutku = 4, P3, koji je prvi u redu čekanja, počinje izvršenje.

Primjer FCFS rasporeda korak 5

Korak 6) U vremenu = 5, P2 stiže i ostaje u redu čekanja.

Primjer FCFS rasporeda korak 6

Korak 7) U vremenu = 11, P3 završava svoje izvršavanje.

Primjer FCFS rasporeda korak 7

Korak 8) U vremenu = 11, P1 započinje izvršavanje. Ima vrijeme neprekidnog ciklusa od 6, tako da izvršavanje završava u vremenskom intervalu 17.

Primjer FCFS rasporeda korak 8

Korak 9) U vremenu = 17, P5 započinje izvršavanje. Ima vrijeme neprekidnog izvršavanja od 4, tako da završava izvršavanje u vremenu = 21.

Primjer FCFS rasporeda korak 9

Korak 10) U vremenu = 21, P2 započinje izvršavanje. Ima vrijeme neprekidnog ciklusa od 2, tako da izvršavanje završava u vremenskom intervalu 23.

Primjer FCFS rasporeda korak 10

Korak 11) Sada izračunajmo prosječno vrijeme čekanja za gornji primjer.

Prosječno vrijeme čekanja zakazivanja FCFS-a

Waiting time = Start time - Arrival time

P4 = 0 – 0 = 0

P3 = 3 – 1 = 2

P1 = 11 – 2 = 9

P5 = 17 – 4 = 13

P2 = 21 – 5 = 16

Prosječno vrijeme čekanja = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8

Izračun prosječnog vremena čekanja zakazivanja FCFS-a

Prednosti FCFS-a

Evo prednosti i koristi korištenja FCFS algoritma za raspoređivanje:

  • To je najjednostavniji oblik CPU algoritam raspoređivanja.
  • Lako je programirati.
  • Slijedi jednostavan redoslijed tko prvi dođe, njemu se daje.

Nedostaci FCFS-a

Evo nedostataka i nedostataka korištenja FCFS algoritma za raspoređivanje:

  • To je nepreemptivni algoritam za raspoređivanje CPU-a, tako da nakon što je proces dodijeljen CPU-u, nikada ga neće osloboditi dok ne završi s izvršavanjem.
  • Prosječno vrijeme čekanja je visoko.
  • Kratki procesi na kraju reda moraju čekati da se završi dugi proces na početku.
  • To nije idealna tehnika za sustave dijeljenja vremena.
  • Zbog svoje jednostavnosti, FCFS nije vrlo učinkovit.

Pitanja i odgovori

"Prvi dođe, prvi poslužen" je nepreemptivni algoritam. Nakon što proces dobije CPU, izvršava se dok se ne završi njegov burst, tako da ga raspoređivač ne može prekinuti kako bi pokrenuo novopristigli ili kraći proces.

Efekt konvoja događa se kada nekoliko kratkih procesa čeka iza jednog dugog procesa na početku reda. Ovaj jedan dugi zadatak povećava prosječno vrijeme čekanja i smanjuje ukupni protok CPU-a.

Vrijeme izvršenja jednako je vremenu završetka minus vremenu dolaska za svaki proces. Mjeri ukupno vrijeme koje proces provede u sustavu, od dolaska do završetka izvršavanja na CPU-u.

FCFS poslužuje po nalogu dolaska, Prvo najkraći posao prvo poslužuje najmanji niz za kraće vrijeme čekanja i Razigravanje daje svakom procesu fiksni vremenski odsječak za dijeljenje vremena.

Čisti FCFS ne uzrokuje gladovanje, jer svaki proces na kraju dođe do početka FIFO reda. Međutim, dugi poslovi i dalje mogu značajno odgoditi kratke zbog efekta konvoja.

FCFS se izvršava u vremenu O(n) kada su procesi već poredani po dolasku, budući da je svaki zakazan jednom. Sortiranje nesortiranih dolazaka po vremenu dolaska prvo dodaje korak od O(n log n).

Modeli strojnog učenja predviđaju vrijeme neprekidnog rada procesa i odabiru ili podešavaju pravila raspoređivanja kako bi smanjili prosječno vrijeme čekanja i potrošnju energije. Istraživači primjenjuju ove planere pokretane umjetnom inteligencijom u cloud poslužiteljima i podatkovnim centrima.

Da. GitHub Copilot može generirati FCFS kod u C-u, Java, ili Python s izračunima vremena čekanja i vremena obrade. Uvijek provjerite formule za sortiranje vremena dolaska, razrješavanje neriješenih rezultata i prosjek prije nego što se povjerujete rezultatu.

Sažmite ovu objavu uz: