logo

Ensin tulee ensin Palvele CPU-prosessien ajoitus käyttöjärjestelmissä

Tässä opetusohjelmassa opimme tärkeän käsitteen suorittimen prosessien ajoitusalgoritmeista. Tärkeä konseptin nimi on First Come First Serve. Tämä on perusalgoritmi, joka jokaisen opiskelijan on opittava ymmärtämään prosessoriprosessien ajoitusalgoritmien kaikki perusteet.

First Come First Serve tasoittaa tietä muiden algoritmien ymmärtämiselle. Tällä algoritmilla voi olla monia haittoja. Mutta nämä haitat loivat hyvin uusia ja tehokkaita algoritmeja. Joten meidän vastuullamme on oppia ensin tullutta palvella ensin -suorittimen prosessien ajoitusalgoritmeista.

Tärkeitä lyhenteitä

  1. CPU - - - > Keskusyksikkö
  2. FCFS - - - > Ensin tullut ensin -palvelu
  3. AT - - - > Saapumisaika
  4. BT - - - > Sarjakuvausaika
  5. WT - - - > Odotusaika
  6. TAT - - - > Kääntymisaika
  7. CT - - - > Valmistumisaika
  8. FIFO - - - > First In First Out

Ensin tullutta palvelee

First Come First Serve CPU Scheduling Algorithm, joka tunnetaan lyhyesti myös nimellä FCFS, on CPU Process Scheduling Algorithmin ensimmäinen algoritmi. First Come First Serve -algoritmissa annamme prosessin suorittaa lineaarisesti.

Tämä tarkoittaa, että se, mikä prosessi tulee valmiiseen jonoon ensin, suoritetaan ensin. Tämä osoittaa, että First In First Out -algoritmi noudattaa FIFO-periaatetta.

First Come First Serve -algoritmi voidaan suorittaa ennaltaehkäisevästi ja ei-ennakoivalla tavalla. Ennen kuin siirrymme esimerkkeihin, ymmärrämme, mikä on ennaltaehkäisevä ja ei-ehkäisevä lähestymistapa suorittimen prosessien ajoituksessa.

Ennaltaehkäisevä lähestymistapa

Tässä ennaltaehkäisevän prosessin ajoituksen tapauksessa käyttöjärjestelmä jakaa resurssit prosessille ennalta määrätyksi ajanjaksoksi. Prosessi siirtyy käynnissä-tilasta valmiustilaan tai odotustilasta valmiustilaan resurssien allokoinnin aikana. Tämä vaihto tapahtuu, koska CPU voi määrittää muiden prosessien etusijalle ja korvata tällä hetkellä aktiivisen prosessin korkeamman prioriteetin prosessilla.

Ei ennaltaehkäisevä lähestymistapa

Tässä Non Emptive Process Scheduling -tapauksessa resurssia ei voida poistaa prosessista ennen kuin prosessi on suoritettu. Kun käynnissä oleva prosessi päättyy ja siirtyy odotustilaan, resurssit vaihdetaan.

Saattuevaikutelma saapumisjärjestyksessä (FCFS)

Convoy Effect on ilmiö, joka esiintyy aikataulutusalgoritmissa nimeltä First Come First Serve (FCFS). First Come First Serve -aikataulutusalgoritmi tapahtuu ei-ennalta ehkäisevästi.

Ei ennaltaehkäisevä tapa tarkoittaa, että jos prosessin tai työn suorittaminen käynnistetään, käyttöjärjestelmän on saatettava prosessi tai työ valmiiksi. Ennen kuin prosessi tai työ on nolla, uusi tai seuraava prosessi tai työ ei aloita suoritustaan. Non Preemptive Scheduling käyttöjärjestelmän määritelmä tarkoittaa, että keskusyksikkö (CPU) on täysin varattu prosessin tai työn loppuun asti, joka aloitettiin ensin ja uusi prosessi tai työ suoritetaan vasta, kun vanha prosessi on päättynyt tai Job.

Saattaa olla muutamia tapauksia, jotka saattavat aiheuttaa sen, että keskusyksikkö (CPU) käyttää liikaa aikaa. Tämä johtuu siitä, että First Come First Serve Scheduling Algorithm Non Preemptive Approach -menetelmässä prosessit tai työt valitaan sarjajärjestyksessä. Tästä johtuen lyhyemmät työt tai prosessit suurempien prosessien tai töiden takana vievät liian paljon aikaa sen suorittamiseen. Tästä johtuen odotusaika, kiertoaika ja valmistumisaika ovat erittäin korkeat.

FCFS-ajoitusalgoritmit käyttöjärjestelmässä (käyttöjärjestelmä)

Joten kun ensimmäinen prosessi on suuri tai valmistumisaika liian pitkä, tämä Saatue-vaikutus First Come First Serve -algoritmissa tapahtuu.

Oletetaan, että Pidempi työ kestää äärettömän ajan. Sitten jäljellä olevien prosessien on odotettava saman äärettömän ajan. Tämän Longer Jobin luoman Convoy Effectin ansiosta odotusprosessien nälkä lisääntyy erittäin nopeasti. Tämä on FCFS CPU Process Schedulingin suurin haitta.

FCFS-suorittimen prosessien ajoituksen ominaisuudet

FCFS CPU Process Schedulingin ominaisuudet ovat:

  1. Toteutus on yksinkertaista.
  2. Ei aiheuta kausaliteettia käytön aikana
  3. Se noudattaa ennaltaehkäisevää ja ennaltaehkäisevää strategiaa.
  4. Se suorittaa jokaisen toimenpiteen niiden vastaanottamisjärjestyksessä.
  5. Menettelyjen valintakriteerinä käytetään saapumisaikaa.

FCFS-suorittimen prosessien ajoituksen edut

FCFS CPU Process Schedulingin edut ovat:

  1. Prosessien allokoimiseksi se käyttää First In First Out -jonoa.
  2. FCFS-suorittimen ajoitusprosessi on suoraviivainen ja helppo toteuttaa.
  3. FCFS-tilanteessa ennakoivassa aikataulutuksessa ei ole mahdollisuutta prosessin nälkiintymiseen.
  4. Koska prosessin prioriteettia ei huomioida, se on tasapuolinen algoritmi.

FCFS-suorittimen prosessien ajoituksen haitat

FCFS-suorittimen prosessien ajoituksen haitat ovat:

  • FCFS CPU Scheduling Algorithmilla on pitkä odotusaika
  • FCFS CPU Scheduling suosii CPU:ta tulo- tai lähtötoimintojen sijaan
  • FCFS:ssä on mahdollisuus Convoy Effectin esiintymiseen
  • Koska FCFS on niin suoraviivainen, se ei useinkaan ole kovin tehokas. Pidennetty odotusaika kulkee käsi kädessä tämän kanssa. Kaikki muut tilaukset jätetään käyttämättä, jos CPU käsittelee yhtä aikaa vievää tilausta.

Ongelmat ensiksi tullutta palvelemaan suorittimen ajoitusalgoritmissa

Esimerkki

 S. No Process ID Process Name Arrival Time Burst Time _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1 P 1 A 0 9 2 P 2 B 1 3 3 P 3 C 1 2 4 P 4 D 1 4 5 P 5 E 2 3 6 P 6 F 3 2 

Ei ennaltaehkäisevä lähestymistapa

Ratkaiskaamme nyt tämä ongelma käyttämällä ajoitusalgoritmia nimeltä First Come First Serve in Non Preemptive Approach.

Gantt-kaavio yllä olevalle esimerkille 1 on:

FCFS-ajoitusalgoritmit käyttöjärjestelmässä (käyttöjärjestelmä)

Palautusaika = Valmistumisaika - Saapumisaika

Odotusaika = Kääntymisaika - Sarjakuvausaika

Ratkaisu yllä olevaan kysymykseen Esimerkki 1

Kyllä ei Prosessin tunnus Saapumisaika Burst Time Valmistumisaika Kääntymisaika Odotusaika
1 P 1 A 0 9 9 9 0
2 P 2 B 1 3 12 yksitoista 8
3 P 3 C 1 2 14 13 yksitoista
4 P 4 D 1 4 18 17 13
5 P 5 JA 2 3 kaksikymmentäyksi 19 16
6 P 6 F 3 2 23 kaksikymmentä 18

Keskimääräinen valmistumisaika on:

Keskimääräinen CT = ( 9 + 12 + 14 + 18 + 21 + 23 ) / 6

Keskimääräinen CT = 97/6

Keskimääräinen CT = 16,16667

Keskimääräinen odotusaika on:

Keskimääräinen WT = ( 0 + 8 + 11 + 13 + 16 + 18 ) /6

Keskimääräinen WT = 66/6

Keskimääräinen WT = 11

Keskimääräinen kiertoaika on:

Keskimääräinen TAT = ( 9 + 11 + 13 + 17 + 19 +20 ) / 6

Keskimääräinen TAT = 89/6

Keskimääräinen TAT = 14,83334

Näin FCFS ratkaistaan ​​ennaltaehkäisevässä lähestymistavassa.

Ymmärrämme nyt, kuinka ne voidaan ratkaista ennaltaehkäisevällä lähestymistavalla

ovat malliesimerkkejä

Ennaltaehkäisevä lähestymistapa

Ratkaiskaamme nyt tämä ongelma ennaltaehkäisevässä lähestymistavassa 'First Come First Serve' -nimisen aikataulutusalgoritmin avulla.

Ennakoivassa lähestymistavassa etsimme parasta saatavilla olevaa prosessia

Gantt-kaavio yllä olevalle esimerkille 1 on:

FCFS-ajoitusalgoritmit käyttöjärjestelmässä (käyttöjärjestelmä)
Kyllä ei Prosessin tunnus Saapumisaika Burst Time Valmistumisaika Kääntymisaika Odotusaika
1 P 1 A 0 9 23 23 14
2 P 2 B 1 3 8 7 4
3 P 3 C 1 2 3 2 0
4 P 4 D 1 4 viisitoista 14 10
5 P 5 JA 2 3 yksitoista 9 7
6 P 6 F 3 2 5 2 0
seuraava → ← Ed

Päästäkseen eroon herätyssignaalien tuhlaamisen ongelmasta Dijkstra ehdotti lähestymistapaa, joka sisältää kaikkien herätyskutsujen tallentamisen. Dijkstra toteaa, että sen sijaan, että tuottaja antaisi herätyksen suoraan kuluttajalle, hän voi tallentaa herätyksen muuttujaan. Kuka tahansa kuluttaja voi lukea sen aina tarvittaessa.

Semafori on muuttuja, joka tallentaa kaikki herätyskutsut, jotka siirtyvät tuottajalta kuluttajalle. Se on muuttuja, jonka luku, muokkaaminen ja päivitys tapahtuu automaattisesti ydintilassa.

Semaforia ei voida toteuttaa käyttäjätilassa, koska kilpailutilanne voi aina syntyä, kun kaksi tai useampi prosessi yrittää käyttää muuttujaa samanaikaisesti. Se tarvitsee aina tukea käyttöjärjestelmältä.

Tilanteen kysynnän mukaan Semaphore voidaan jakaa kahteen luokkaan.

  1. Semaforien laskeminen
  2. Binäärinen semafori tai Mutex

Keskustelemme jokaisesta yksityiskohtaisesti.