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ä
- CPU - - - > Keskusyksikkö
- FCFS - - - > Ensin tullut ensin -palvelu
- AT - - - > Saapumisaika
- BT - - - > Sarjakuvausaika
- WT - - - > Odotusaika
- TAT - - - > Kääntymisaika
- CT - - - > Valmistumisaika
- 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.
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:
- Toteutus on yksinkertaista.
- Ei aiheuta kausaliteettia käytön aikana
- Se noudattaa ennaltaehkäisevää ja ennaltaehkäisevää strategiaa.
- Se suorittaa jokaisen toimenpiteen niiden vastaanottamisjärjestyksessä.
- Menettelyjen valintakriteerinä käytetään saapumisaikaa.
FCFS-suorittimen prosessien ajoituksen edut
FCFS CPU Process Schedulingin edut ovat:
- Prosessien allokoimiseksi se käyttää First In First Out -jonoa.
- FCFS-suorittimen ajoitusprosessi on suoraviivainen ja helppo toteuttaa.
- FCFS-tilanteessa ennakoivassa aikataulutuksessa ei ole mahdollisuutta prosessin nälkiintymiseen.
- 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:
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:
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.
Keskustelemme jokaisesta yksityiskohtaisesti. |