Mikä on ensin tullutta palvele -menetelmä?
First Come First Serve (FCFS) on käyttöjärjestelmän ajoitusalgoritmi, joka suorittaa jonotetut pyynnöt ja prosessit automaattisesti niiden saapumisjärjestyksessä. Se on helpoin ja yksinkertaisin suorittimen ajoitusalgoritmi. Tämän tyyppisessä algoritmissa prosessorit, jotka pyytävät ensin suorittinta, saavat ensin suorittimen varauksen. Tätä hallitaan FIFO-jonolla. FCFS: n koko muoto on First Come First Serve.
Kun prosessi saapuu valmiiseen jonoon, sen PCB (Process Control Block) linkitetään jonon hännään, ja kun keskusyksikkö vapautuu, se tulisi määrittää prosessille jonon alussa.
Tässä käyttöjärjestelmän opetusohjelmassa opit:
- Mikä on ensin tullutta palvele -menetelmä?
- FCFS-menetelmän ominaisuudet
- Esimerkki FCFS-aikataulutuksesta
- Kuinka FCFS toimii? Lasketaan keskimääräinen odotusaika
- FCFS: n edut
- FCFS: n haitat
FCFS-menetelmän ominaisuudet
- Se tukee ennaltaehkäisevää ja ennalta ehkäisevää ajoitusalgoritmia.
- Työtehtävät toteutetaan aina ensin saapumisjärjestyksessä.
- Se on helppo toteuttaa ja käyttää.
- Tämän menetelmän suorituskyky on huono, ja yleinen odotusaika on melko pitkä.
Esimerkki FCFS-aikataulutuksesta
Todellinen esimerkki FCFS-menetelmästä on elokuvalipun ostaminen lipputiskiltä. Tässä ajoitusalgoritmissa henkilöä palvellaan jonotavan mukaisesti. Ensin jonoon saapuva henkilö ostaa ensin lipun ja sitten seuraavan. Tämä jatkuu, kunnes jonossa viimeinen henkilö ostaa lipun. Tätä algoritmia käyttämällä CPU-prosessi toimii samalla tavalla.
Kuinka FCFS toimii? Lasketaan keskimääräinen odotusaika
Tässä on esimerkki viidestä eri aikaan saapuvasta prosessista. Jokaisella prosessilla on erilainen purskeaika.
| Prosessi | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
FCFS-ajoitusalgoritmia käytettäessä nämä prosessit käsitellään seuraavasti.
Vaihe 0) Prosessi alkaa P4: llä, jonka saapumisaika on 0
Vaihe 1) Aikana = 1, P3 saapuu. P4 on edelleen suorittamassa. Siksi P3 pidetään jonossa.
| Prosessi | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 2) Aikana = 2 saapuu P1, joka pidetään jonossa.
| Prosessi | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 3) Aikana = 3, P4-prosessi suorittaa suorituksensa loppuun.
Vaihe 4) Aikana = 4, jonossa ensimmäinen P3 aloittaa suorituksen.
| Prosessi | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 5) Aikana = 5, P2 saapuu, ja se pidetään jonossa.
| Prosessi | Sarjaaika | Saapumisaika |
| P1 | 6 | 2 |
| P2 | 3 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Vaihe 6) Aikana 11 P3 suorittaa suorituksensa loppuun.
Vaihe 7) Aikana = 11, P1 aloittaa suorituksen. Sen purskeaika on 6. Se suorittaa suorituksen aikavälillä 17
Vaihe 8) Aikana = 17, P5 aloittaa suorituksen. Sen purskeaika on 4. Se suorittaa suorituksen aikaan = 21
Vaihe 9) Aikana = 21, P2 aloittaa suorituksen. Sen purskeaika on 2. Se suorittaa suorituksen aikavälillä 23
Vaihe 10) Laske 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-ajoitusalgoritmin käytön edut / edut:
- CPU: n ajoitusalgoritmin yksinkertaisin muoto
- Helppo ohjelmoida
- Palvellaan saapumisjärjestyksessä
FCFS: n haitat
Tässä on FCFS-ajoitusalgoritmin käytön haittoja / haittoja:
- Se on ei-ennakoiva suorittimen ajoitusalgoritmi, joten sen jälkeen kun prosessi on allokoitu CPU: lle, se ei koskaan vapauta CPU: ta ennen kuin se on suorittanut loppuun.
- Keskimääräinen odotusaika on korkea.
- Lyhyiden prosessien, jotka ovat jonon takana, on odotettava, että edessä oleva pitkä prosessi päättyy.
- Ei ihanteellinen tekniikka ajanjakojärjestelmiin.
- Yksinkertaisuutensa vuoksi FCFS ei ole kovin tehokas.
Yhteenveto:
- Määritelmä: FCFS on käyttöjärjestelmän ajoitusalgoritmi, joka suorittaa jonotetut pyynnöt ja prosessit automaattisesti niiden saapumisjärjestyksessä
- Se tukee ennaltaehkäisevää ja ennakoivaa aikataulutusta
- algoritmi.
- FCFS on lyhenne sanoista First Come First Serve
- Todellinen esimerkki FCFS-menetelmästä on elokuvalipun ostaminen lipputiskiltä.
- Se on yksinkertaisin muoto suorittimen ajoitusalgoritmista
- Se on ei-ennakoiva suorittimen ajoitusalgoritmi, joten sen jälkeen kun prosessi on allokoitu CPU: lle, se ei koskaan vapauta CPU: ta ennen kuin se on suorittanut loppuun.