FCFS-ajoitusalgoritmi: Mikä on, esimerkkiohjelma
Nathaniel Brooks
Mikä on ensin tullutta palvelee -menetelmä?
Ensin tullutta palvella (FCFS) on käyttöjärjestelmän ajoitusalgoritmi, joka suorittaa automaattisesti jonossa olevat pyynnöt ja prosessit niiden saapumisjärjestyksessä. Se on helpoin ja yksinkertaisin suorittimen ajoitusalgoritmi. Tämän tyyppisessä algoritmissa prosessit, jotka ensin pyytävät CPU:ta, saavat ensin suorittimen allokoinnin. Tätä hallitaan FIFO-jonon avulla. FCFS:n täysi muoto on First Come First Serve.
Prosessin tullessa valmiusjonoon, sen PCB (Process Control Block) linkitetään jonon päähän ja kun CPU vapautuu, se tulee osoittaa prosessille jonon alussa.
FCFS-menetelmän ominaisuudet
- Se tukee ennaltaehkäisevää ja ennaltaehkäisevää aikataulutusalgoritmia.
- 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-aikataulutuksesta
Tosielämän esimerkki FCFS-menetelmästä on elokuvalipun ostaminen lipputiskiltä. Tässä aikataulutusalgoritmissa henkilöä palvellaan jonotavan mukaisesti. Ensimmäisenä jonoon saapuva ostaa ensin lipun ja sitten seuraavan. Tämä jatkuu, kunnes viimeinen jonossa oleva ostaa lipun. Tätä algoritmia käyttämällä CPU-prosessi toimii samalla tavalla.
Kuinka FCFS toimii? Keskimääräisen odotusajan laskeminen
Tässä on esimerkki viidestä prosessista, jotka saapuvat eri aikoina. Jokaisella prosessilla on erilainen 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:llä, jonka saapumisaika on 0
Vaihe 2) Aika = 1, P3 saapuu. P4 on edelleen käynnissä. Siksi P3 pidetään jonossa.
| Käsitellä asiaa | Räjähdysaika | Saapumisaika |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 3) Ajankohtana = 2 saapuu P1, joka pidetään jonossa.
| Käsitellä asiaa | Räjähdysaika | Saapumisaika |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 4) Ajankohtana = 3, P4-prosessi suorittaa suorituksensa loppuun.
Vaihe 5) Ajankohtana = 4, P3, joka on ensimmäinen jonossa, aloittaa suorituksen.
| Käsitellä asiaa | Räjähdysaika | Saapumisaika |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 6) Ajankohtana =5 P2 saapuu ja sitä pidetään jonossa.
| Käsitellä asiaa | Räjähdysaika | Saapumisaika |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 7) Aikana 11 P3 suorittaa suorituksensa loppuun.
Vaihe 8) Aika = 11, P1 aloittaa suorituksen. Sen purskeaika on 6. Se suorittaa suorituksen aikavälillä 17
Vaihe 9) Aika = 17, P5 aloittaa suorituksen. Sen purskeaika on 4. Se suorittaa suorituksen ajan = 21
Vaihe 10) Aika = 21, P2 aloittaa suorituksen. Sen purskeaika on 2. Se suorittaa suorituksen aikavälillä 23
Vaihe 11) Lasketaan keskimääräinen odotusaika yllä olevalle esimerkille.
Waiting time = Start time - Arrival time
P4 = 0-0 = 0
P3 = 3-1 = 2
PI = 11-2 = 9
P5 = 17-4 = 13
P2 = 21-5 = 16
Keskimääräinen odotusaika
= 40 / 5 = 8
FCFS:n edut
Tässä on FCFS-aikataulutusalgoritmin käytön edut/edut:
- Yksinkertaisin muoto a CPU-aikataulutusalgoritmi
- Helppo ohjelmoida
- Palvellaan saapumisjärjestyksessä
FCFS:n haitat
Tässä on FCFS-aikataulutusalgoritmin käytön haittoja/haittoja:
- Se on ei-ennaltaehkäisevä suorittimen ajoitusalgoritmi, joten sen jälkeen kun prosessi on allokoitu CPU:lle, se ei koskaan vapauta suoritinta ennen kuin se on suorittanut loppuun.
- Keskimääräinen odotusaika on korkea.
- Lyhyiden prosessien, jotka ovat jonon takana, on odotettava pitkän prosessin päättymistä.
- Ei ihanteellinen tekniikka aikajakojärjestelmille.
- Yksinkertaisuuden vuoksi FCFS ei ole kovin tehokas.
Yhteenveto
- Määritelmä: FCFS on käyttöjärjestelmän ajoitusalgoritmi, joka suorittaa automaattisesti jonossa olevat pyynnöt ja prosessit niiden saapumisjärjestyksessä
- Se tukee ennaltaehkäisevää ja ennaltaehkäisevää ajoitusta
- algoritmi.
- FCFS on lyhenne sanoista First Come First Serve
- Tosielämän esimerkki FCFS-menetelmästä on elokuvalipun ostaminen lipputiskiltä.
- Se on suorittimen ajoitusalgoritmin yksinkertaisin muoto
- Se on ei-ennaltaehkäisevä suorittimen ajoitusalgoritmi, joten sen jälkeen kun prosessi on allokoitu CPU:lle, se ei koskaan vapauta suoritinta ennen kuin se on suorittanut loppuun.
