Aikataulutusalgoritmit ovat välttämättömiä käyttöjärjestelmissä hallita prosessin toteutusta tehokkaasti. Ne määrittävät järjestyksessä, missä prosesseissa CPU aika, vaikutus järjestelmän suorituskykyä ja reagointikykyä. Tässä artikkelissa vertaillaan kolmea yhteistä algoritmia: First-Come, First-Served (FRS), Shortest Job First (SJF), ja Round Robin, jossa on laskelmat havainnollistaa niiden eroja.

Ensisijainen, ensimmäinen sarja (Finst-Served, FCFS)

FCFS aikataulut prosessit järjestyksessä ne saapuvat. Se on yksinkertainen, mutta voi johtaa pitkiä odotusaikoja lyhyempiä prosesseja, kutsutaan "konvoy vaikutus."

Esimerkki: Prosessit, joissa murtumis kertaa 5, 3 ja 8 saapuvat peräkkäin. Gantt-kaaviossa esitetään suoritusjärjestys ja laskelmat odotus- ja käänneaikoihin.

Laskelmat:

  • Prosessi 1: Odotusaika = 0, kierrosaika = 5
  • Prosessi 2: Odotusaika = 5, kierrosaika = 8
  • Prosessi 3: Odotusaika = 8, kierrosaika = 16

Lyhin työ ensin (SJF)

SJF valitsee prosessin seuraavaksi pienimmällä murtoajalla. Se minimoi keskimääräisen odotusajan, mutta vaatii etukäteen tietoa prosessin kestoista.

SJF:n aikataulut ovat samat kuin 3, 5 ja 8 yksikköä, mikä johtaa erilaisiin odotusaikoihin.

Laskelmat:

  • Prosessi 2: Odotusaika = 0, kierrosaika = 3
  • Prosessi 1: Odotusaika = 3, kierrosaika = 8
  • Prosessi 3: Odotusaika = 8, kierrosaika = 16

Round Robin Scheduling

Round Robin määrittää kullekin prosessille kiinteän aikasiivun tai kvantin. Prosessit kierretään loppuun asti, mikä edistää oikeudenmukaisuutta ja reagointikykyä.

Jos parametri on 2 yksikköä, prosessit on suunniteltu jaksoiksi, ja laskelmat perustuvat kokonaistoteutusaikaan ja odotusaikaan.

Esimerkkilaskelmat prosessin suoritus- ja odotusajoista ovat seuraavat:

  • Prosessi 1: Odotusaika = 4, kierrosaika = 9
  • Prosessi 2: Odotusaika = 2, kierrosaika = 5
  • Prosessi 3: Odotusaika = 8, kierrosaika = 16