FCFS-ajoitusalgoritmi: Mikä on, esimerkkiohjelma
Nathaniel Brooks
⚡ Älykäs yhteenveto
Ensimmäiseksi tullutta palvelemme -ajoitus suorittaa prosessit täsmälleen siinä järjestyksessä, että ne saapuvat valmiusjonoon. Se käyttää yksinkertaista, ei-preemptiivistä FIFO-lähestymistapaa, mikä tekee siitä käyttöjärjestelmälle helpoimman toteutettavan suorittimen ajoitusalgoritmin.
Mikä on ensin tullutta palvelee -menetelmä?
Ensin tullutta palvella (FCFS) on käyttöjärjestelmän ajoitusalgoritmi, joka suorittaa jonossa olevat pyynnöt ja prosessit automaattisesti niiden saapumisjärjestyksessä. Se on helpoin ja yksinkertaisin suorittimen ajoitusalgoritmi. Tällaisessa algoritmissa prosessi, joka pyytää suoritinta ensimmäisenä, saa suorittimen allokoinnin ensin. Tätä hallitaan FIFO-jonolla. FCFS:n täydellinen muoto on First Come First Serve.
Kun prosessi siirtyy valmiusjonoon, sen piirilevy (PCB, Process Control Block) linkitetään jonon häntään. Joten kun CPU vapautuu, se osoitetaan jonon alussa olevalle prosessille.
FCFS-menetelmän ominaisuudet
Ensin tullutta palvelemme -menetelmän pääominaisuudet on lueteltu alla:
- On ei-ennaltaehkäisevä ajoitusalgoritmi, joten prosessi pitää suorittimen käytettävissä, kunnes se on suorittanut purskeaikansa loppuun.
- Työt tehdään aina saapumisjärjestyksessä.
- Se on helppo toteuttaa ja käyttää.
- Tämän menetelmän suorituskyky on heikko, ja yleinen odotusaika on melko pitkä.
Esimerkki FCFS-ajoituksesta
Käytännön esimerkki FCFS-menetelmästä on elokuvalipun ostaminen lipputiskiltä. Tässä ajoitusalgoritmissa henkilöä palvellaan jonotusjärjestyksen mukaisesti. Jonossa ensimmäisenä saapuva henkilö ostaa lipun ensin ja sitten seuraava. Tämä jatkuu, kunnes jonossa viimeinen henkilö ostaa lipun. Tätä algoritmia käytettäessä CPU-prosessi toimii samalla tavalla.
Kuinka FCFS toimii? Keskimääräisen odotusajan laskeminen
Ymmärtääksemme, miten algoritmi aikatauluttaa prosesseja, tässä on esimerkki viidestä eri aikoina saapuvasta prosessista. Jokaisella prosessilla on eri purskeaika.
| Käsitellä asiaa | Räjähdysaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
FCFS-ajoitusalgoritmia käyttämällä näitä prosesseja käsitellään seuraavasti.
Vaihe 1) Prosessi alkaa P4:stä, jonka saapumisaika on 0.
Vaihe 2) Aika = 1, P3 saapuu. P4 on edelleen käynnissä. Siksi P3 pidetään jonossa.
Vaihe 3) Ajanhetkellä 2 P1 saapuu ja pidetään jonossa.
Vaihe 4) Ajanhetkellä 3 P4-prosessi suorittaa suorituksensa loppuun.
Vaihe 5) Ajankohtana = 4, P3, joka on ensimmäinen jonossa, aloittaa suorituksen.
Vaihe 6) Ajanhetkellä 5 P2 saapuu ja pidetään jonossa.
Vaihe 7) Ajanhetkellä 11 P3 suorittaa suorituksensa loppuun.
Vaihe 8) Ajanhetkellä 11 P1 aloittaa suorituksen. Sen purskeaika on 6, joten se suorittaa suorituksen loppuun aikavälissä 17.
Vaihe 9) Ajanhetkellä 17 P5 aloittaa suorituksen. Sen purskeaika on 4, joten se suorittaa suorituksen loppuun ajanhetkellä 21.
Vaihe 10) Ajanhetkellä 21 P2 aloittaa suorituksen. Sen purskeaika on 2, joten se suorittaa suorituksen loppuun aikavälissä 23.
Vaihe 11) Lasketaanpa nyt keskimääräinen odotusaika yllä olevalle esimerkille.
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
Keskimääräinen odotusaika = (0 + 2 + 9 + 13 + 16) / 5 = 40 / 5 = 8
FCFS:n edut
Tässä ovat FCFS-ajoitusalgoritmin käytön edut ja hyödyt:
- Se on yksinkertaisin muoto CPU-aikataulutusalgoritmi.
- Se on helppo ohjelmoida.
- Se noudattaa suoraviivaista saapumisjärjestystä.
FCFS:n haitat
Tässä ovat FCFS-ajoitusalgoritmin käytön haitat ja haitat:
- Se on ei-preemptiivinen CPU-ajoitusalgoritmi, joten kun prosessi on allokoitu CPU:lle, se ei koskaan vapauta CPU:ta ennen kuin se on suorittanut sen loppuun.
- Keskimääräinen odotusaika on korkea.
- Jonon takana olevat lyhyet prosessit joutuvat odottamaan jonon kärjessä olevan pitkän prosessin valmistumista.
- Se ei ole ihanteellinen tekniikka aikajakojärjestelmille.
- Yksinkertaisuuden vuoksi FCFS ei ole kovin tehokas.
