mk3 Flashcards
Minkä ongelman Shortest process next (SPN) vuoronantomenetelmä tarkalleen ottaen ratkaisee?
SPN ratkaisee FCFS -vuoronnuksen ongelman pitkästä keskimääräisestä vasteajasta. Se myös ratkaisee ongelman, jossa I/O-painotteiset prosessit joutuvat odottamaan kohtuuttoman kauan suoritinpainotteisten prosessien takana: : I/O-painotteisella prosessilla arvioitu suoritinrupeama on lyhyempi, koska se kutsuu usein I/O:ta. Tällöin se siirretään odottaa-jonoon ja I/O:n valmistuttua valmis suoritukseen jonoon, lyhyen suoritinrupeamansa takia tyypillisesti kärkisijoille jonossa
SPN. Kuinka se toimii pääpiirteittäin?
SPN:ssä valmis suoritukseen -jonosta valitaan se prosessi suoritukseen, jonka arvioitu suoritinrupeama (CPU-burst) on pienin. Suoritinrupeama on se aika, jonka prosessi on suorittimella kerrallaan. Estimaatti perustuu aiempiin suoritusaikoihin
SPN. Millä tavoin se on parempi kuin FIFO ja miksi?
SPN on todistettavasti optimaalinen keskimääräisen vasteajan kannalta. Koska vähiten suorittimella aikaa kuluttava valitaan ensin, muut jonossa olevat joutuvat odottamaan pienemmän aikaa. Jos järjestys olisi mikä tahansa muu, olisi edellä jonossa pisempään aikaa tarvitseva prosessi, ja siten jokainen sen takana oleva prosessi joutuu odottamaan kauemmin.
SPN. Miten tiedetään, mikä on ”shortest process”, jos sitä tietoa ei ole etukäteen annettu?
SPN:ssä valmis suoritukseen -jonosta valitaan se prosessi suoritukseen, jonka arvioitu suoritinrupeama (CPU-burst) on pienin. Suoritinrupeama on se aika, jonka prosessi on suorittimella kerrallaan. Estimaatti perustuu aiempiin suoritusaikoihin
b) [1 p] Minkä ongelman Fair Share vuoronantomenetelmä ratkaisee? FSS
käsittelee käyttäjän prosesseja ryhmänä. Tarjoaa reilun pääsyn resursseihin, jotta kukaan ei saa monopoliasemaa ja kukaan ei näänny
Fair share. Mitä tietoja sitä varten tarvitsee kerätä järjestelmästä?
pidettävä kirjaa paljon ryhmä saanut CPU aikaa
c) [2 p] Mihin ongelmaan Rate Monotonic Scheduling vuoronantomenetelmä on vastaus?
RTOS real time opetatings systemseissä. Prioriteettien mukaan, priot job kestosyklin mukaan. Määräaikojen saavutus etukäteen määrätyssä ajassa. Kun asiat täytyy tehdä riittävän nopeasti toiminnan kannalta. Paljon käyttänyt suoritinaikaa, kenen arvioitu suoritinrupeama pienin
Rate Monitonic scheduling. Minkälaiseen laskentaympäristöön se on tarkoitettu?
Milloin sitä voi käyttää?
Kuinka se toimii?
Oikea-aikaisuusjärjestelmiin. Prioritettit määrätään työn kestosyklin mukaan, lyhyempi syksin kerto saa korkeamman prioriteetin. Paljon käyttänyt suoritinaikaa, kenen arvioitu suoritinrupeama pienin
Selitä, mikä on prioriteetin kääntymisongelma? (Kuinka on mahdollista, että korkeamman prioriteetin työ voi joutua odottamaan pitkän aikaa alemman prioriteetin työtä, vaikka käytössä on prioriteettiin perustuva keskeyttävä vuoronantomenetelmä?)Anna prioriteetin kääntymisongelmalle yksi ratkaisumenetelmä.
korkeamman prioriteetin työ joutuu odottamaan alemman prioriteetin työtä.
Anna esimerkki tilanteesta, jossa aikaviipalevuoronannon (Round Robin) aikaviipaleen pituus on liian lyhyt.
Perustele
Too short quantum causes too many process/context switches and reduces CPU efficiency. Aikaviipale on lyhyempi kun interaction
Tosiaikajärjestelmien vuoronanto perustuu usein takaraja (deadline) vuoronantoon. Siinä kunkin tehtävän
prioriteetti määräytyy sen mukaan, kuinka lähellä suorituksen valmistumisen takaraja on ja mikä on tehtävän
CPU-ajan tarve. Rate Monotonic Scheduling (RMS) vuoronantomenetelmä ei kuitenkaan tarvitse
vuoronantohetkellä tietoa tehtävien CPU-aikojen tarpeesta tai suorituksen valmistumisien takarajoista, mutta
silti kaikki työt valmistuvat ajoissa.
Milloin RMS vuoronantomenetelmää voi käyttää ja kuinka se pääpiirteissään toimii?
Oikea-aikaisuusjärjestelmiin. Prioritettit määrätään työn kestosyklin mukaan, lyhyempi syksin kerto saa korkeamman prioriteetin. Paljon käyttänyt suoritinaikaa, kenen arvioitu suoritinrupeama pienin
Tosiaikajärjestelmän tulee pystyä samanaikaisesti l
RMS takaa että kaikki vuorotetaan ajallaan. Koska tulee <1 kun yksi prosessi?
kaikkien tarvittujen aikojen arvot alle x
0.5/5
1/25 = 40 ms joka kehykselle
Millä perusteella tavanomaisessa järjestelmässä Shortest Job First (SJF)
vuoronantomenetelmä olisi parempi kuin First Come First Selved (FCFSX
odotusaika keskimäär kaikilla lyh?
SPN (Shortest Process Next) antaa usein paremman keskimääräisen vasteajan kuinFIFO(First-In-First-Out) taiRR (Round Robin). [1 p] Mihin SPN:n vuoronanto täsmälleen ottaen perustuu? Jos em. tietoa ei täsmälleen ole saatavissa, kuinka se voidaan estimoida?Mihin estimaatti perustuu?
lyhin sykli korkea prioriteetti
FS (Feedback Scheduling) on RR:n variantti. Minkä RR:n ongelman se ratkaisee ja kuinka se sen tekee?
F eedback If we have no indication of the relative length of various processes, then
none of SPN, SRT, and HRRN can be used. Another way of establishing a preference
for shorter jobs is to penalize jobs that have been running longer. In other words, if
we cannot focus on the time remaining to execute, let us focus on the time spent in
execution s. Prosessi blokkautuu, palauttaa jonon?
Moniprosessorijärjestelmien vuoronanto. Joukkoskedulointi (GS, gang scheduling)[2 p] Kuinka GS toimii (RR:n varianttina)?
joukon prosesseita vuorottaminen samanaikaisesti. Vähemmän odottelua synkronoinnin takia, vähemmän prosessin vaihtoja.
Missä tilanteessa RMS:ää (Rate Monotonic Scheduling) voi käyttää?Miten se toimii?
Multitask vuoronanto ongelmiin. työn syklin keston mukaan määräytyy prioriteetti, lyhyempi saa korkeamman prion. Paljon käyttänyt suoritinaikaa, kenen arvioitu suoritinrupeama pienin
Miksi RMS on parempi kuin reaaliaikajärjestelmissä yleinen deadline-vuoronanto?
RMS takaa että kaikki deadlinet saavutetaan
Minkä ongelman Fair Share Scheduling (FSS) vuoronantomenetelmä ratkaisee ja kuinka FSS pääpiirteissään
toimii?
käsittelee käyttäjän prosesseja ryhmänä. Tarjoaa reilun pääsyn resursseihin, jotta kukaan ei saa monopoliasemaa ja kukaan ei näänny
a) [2 p] Miten Highest Response Ratio Next (HRRN) vuoronantomenetelmä toimii?
Mitä tietoja se käyttää päätöksenteossa ja mistä tiedot saadaan?
For each process you compute the response ratio R = (W+S)/S, where W is waiting time so far in RR queue,
and S is expected execution time. Next process to run is the one with highest R.
What data does it use in decision making and how is that data obtained?
See W and S above. You save the time when each process arrives to RR queue, and compute W from that.
You are either given S from the user, or you estimate it with biased average based on previous estimate and
previous actual execution time. First time you just use some estimate, e.g., 1 msec.
What types of jobs does it prefer and why?
It prefers I/O-bound jobs (or other jobs with short CPU time), because the RR increases faster when S is
smaller. I/ O-bounds jobs have typically short execution bursts before waiting for next I/ O to complete.
Fair Share vuoronantomenetelmä yrittää antaa eri käyttäjille suunnilleen saman verran suoritinaikaa
riippumatta siitä, kuinka monta prosessia heillä on suoritettavana.
Kuinka Fair Share vuoronantomenetelmä pääpiirteissään toimii?
Each process has a base priority B. Time slices are interrupted every now and then (e.g., 60 times), and each
time a counter is incremented for the running process (P) and for the user whose process it is (U). At next
scheduling time the priority for each process is computed so that the priority becomes weaker for recent
high P or U counter value. This way, a process belonging to another user is likely scheduled next. And when a
process belonging to this user is scheduled next time, it will likely be not the same one as before.
Tosiaikajärjestelmässä työ A toistuu 50 ms välein, työ B toistuu 20 ms välein ja työ C 100 ms välein.
Missä tilanteessa tämän järjestelmän vuoronantomenetelmänä voidaan käyttää pelkkiä prioriteetteja?
Miten prioriteetit tässä esimerkissä määräytyvät? Kellä on korkein prioriteetti ja miksi?
You can use Rate Monotonic Scheduling (RMS) if the overall utilization for all periodic tasks is below certain
limit, which is dependent on the number of periodic tasks. For example, if A tasks have cpu-time 10 ms (and
utilization 20%), B tasks 5 ms (25%), and C tasks 10 ms (10%), then the overall utilization is 55%, which is
below the limit for 3 tasks
RMS can now be used with higher priorities for those tasks with shorter periods (and highest execution rate).
So, tasks B have highest priority (and highest execution rate 50 times/ sec) and tasks C the lowest priority
(and lowest execution rate 10 time/sec).
Mainitse joku moniprosessorijärjestelmään sopiva vuoronantomenetelmä, joka ei sovi yhden
suorittimen ympäristöön eikä tosiaikajärjestelmiin. Perustele, miksi ei. Kerro myös pääpiirteissään, miten se
toimii.
Gang scheduling tries to schedule all threads belonging to the same process at the same time on different
cores (processors). This allows all threads to advance at the same pace, and no they would need to wait for
other threads to complete their subtasks at synchronization points. This is not suitable for uniprocessor
systems, because there is only once core (processor) to run on. It is not suitable in real time systems,
because it does not take into consideration the deadlines.
