mk4

Question 1

a) [2 p] Miksi SCAN on parempi kuin FIFO?

Answer 1

fifo ei ota huomioon levyn tilaa, tasapuolinen

SCAN Suosiikeskiurilleosuvia pyyntöjä ja uusia töitä

Question 2

Miksi C-SCAN (Circular SCAN) on parempi kuin SCAN?

Answer 2

ylhäältä tai alhaalta ja takas. odotus ei niin paha jos tulee huonoon aikaan

Question 3

Minkä (C-SCAN) ongelman Linuxin Deadline Scheduler ratkaisee? Kuinka se sen tekee?

Answer 3

C-SCAN favor latest arriving jobs, and old jobs may have to wait a long time until the elevator moves to their
tracks. The Deadline Scheduler keeps read and write tasks also in additional queues which get higher priority
if waiting times become too large. A job which has been waiting too long will get a high priority even at the
cost of overall system performance.

Question 4

b) [1 p] Miten RAID 5 ratkaisu toimii pääpiirteissään?

Answer 4

disc jaetaan blockeihin, 1 tasolla parity block. Minkään discin katoaminen ei aiheuta datan katoamista.

RAID
tiedostot jaettu useammalle levylle, lohkon tavut jaettu useammalle levylle, vaikka levy hajoaa, sillä ollut tieto voidaan toivottavasti luodauudelleen muiden levyjen perusteella,huolehtii pariteetista

Question 5

Miten (suhteellisen pieni) tieto kirjoitetaan RAID 5 järjestelmässä?

Answer 5

kirjoituksessa yhteen lohkoon muut saman stripe’n lohkot pitääensin lukea pariteettilohkonlaskemista vartenFtai sitten lue ensin vanha lohko ja laske siitäukirjoituksessa pitääaina kirjoittaa myös pariteettilohkoujonotusaika vähenee, siirtonopeus kasvaa, pariteettilohko vuorotellen eri levyile

Question 6

Minkä hissi-algoritmin (SCAN) ongelman C-SCAN ratkaisee? Kuinka se sen tekee?

Answer 6

aloittaa aina ylhäältä tai alhaalta. Ei joudu odottamaan, vähentää maksimiviivettä
SCAN favors jobs using innermost/ outermost tracks. C-SCAN treats all tracks equally by servicing requests
going to one direction only.

Question 7

Minkä C-SCAN ongelman N-STEP-SCAN vuoronantaja ratkaisee? Kuinka se sen tekee?

Answer 7

Track requests in C-SCAN can be significantly delayed, if there are lots of new requests coming in between
current track and the requested track. N-STEP-SCAN alleviates this problem by servicing tracks in size N
batches. Now any request may be delayed by at most N-1 new requests arriving after it. However, the overall
system performance will suffer due to servicing only one batch of requests at a time

Question 8

Minkä C-SCAN ongelman Linuxin Anticipatory I/ O Scheduler ratkaisee? Kuinka se sen tekee?

Answer 8

Often one disk request is immediately followed by another one close to it, but normal C-SCAN algorithm may
have already advanced pass that area on disk. The Anticipatory I/O Scheduler will always wait for a while just
in case the next request would be on the same area. If it is, then it will be serviced next. If it is not, then we
have waited in vain at the cost of overall system performance.

Question 9

Minkä C-SCAN ongelman Linuxin Deadline Scheduler ratkaisee? Kuinka se sen tekee?

Answer 9

C-SCAN favor latest arriving jobs, and old jobs may have to wait a long time until the elevator moves to their
tracks. The Deadline Scheduler keeps read and write tasks also in additional queues which get higher priority
if waiting times become too large. A job which has been waiting too long will get a high priority even at the
cost of overall system performance.

Question 10

Levyvälimuistin seuraavaksi muistista poistettavan lohkon valinnan voi tehdä Frequency Based
Replacement (FBR) algoritmilla. Siinä levyvälimuistissa olevat lohkot pidetään LRU-pinossa, joka on jaettu
kahteen osaan: uudet lohkot (New Section) ja vanhat lohkot (Old Section). Kehittyneemmässä muodossa
LRU-pinossa on myös keskiosa (Middle Section). Minkä alkuperäisen algoritmin ongelman LRU-pinon
keskiosan tuominen mukaan ratkaisee ja kuinka FBR algoritmi nyt toimii?

Answer 10

Each block has a reference count C. The original FBR works so that
(i) reference to a block in New Section will not increment C (but moves the block to top of the LRU stack),
(ii) reference to block in Old Section will increment C (and moves the block to top of the LRU stack),
(iii) the block to be replaced is the one with smallest reference count in the Old Section.
In practice the block to be replaced is then often (and unfortunately) the one that most recently moved to
the Old Section, because it has not have had time to be referenced again.
The modified FBR work so that the blocks in Middle Section are safe for replacement, just in case they are
relatively new blocks and have not yet had time to be used again. Otherwise a reference to the Middle
Section behaves the same way as a reference to the Old Section.

Question 11

Tiedostojen hallinta. Tiedostossa Staff on 10 000 tietuetta ja se on talletettu levymuistiin. Kentän Corp-ID arvot
ovat välillä 1 – 100 000 000. Kentän Union-ID arvot ovat välillä 1 – 1 000 000. Tietueet ovat suuria ja niissä on
useita muitakin kenttiä.
c) [1.5 p] Oletetaan, että Staff on toteutettu indeksoituna peräkkäistiedostona (indexed sequential file). Mitä
tämä käytännössä tarkoittaa? Miksi tiedoston Staff rakenteeksi olisi valittu nimenomaan indeksoitu
peräkkäistiedosto? Missä järjestyksessä tietueet sijaitsevat tiedostossa? Montako indeksiä järjestelmässä
on? Missä indeksit sijaitsevat? Mitä tietoja indekseissä on? Milloin indeksejä käytetään ja miten?
Otaksu tässä, että indeksejä ei ole toteutettu B-puuna.

Answer 11

The file is optimized for two types of most used access patterns: sequential access in (e.g.) Corp-ID order and
random access with given Corp-ID number. All other accesses patterns are rare and they may be slow.
(You can give your answer similarly for sequential access in Union-ID order.)
The records in Staff are stored in ascending Corp-ID order. This allows for fast processing of all records in this
order. There is one index that speeds up random access to locate a record with given Corp-ID value. The
index has 100 entries (square root of 10 000), with links to records starting with Corp-ID values
1, 1 000 000, 2 000 000, etc. The index is located in memory. There is an overflow file for new additions to
Staff, and that is coalesced to the main file every now and then.
The index is used to quickly locate the approximate location of a randomly accessed record (with given Corp-
ID), after which the file is scanned sequentially until the record (with given Corp-ID) is located.

Question 12

Minkä C-SCAN ongelman Linuxin Deadline Scheduler ratkaisee? Kuinka se sen tekee?

Answer 12

C-SCAN favor latest arriving jobs, and old jobs may have to wait a long time until the elevator moves to their
tracks. The Deadline Scheduler keeps read and write tasks also in additional queues which get higher priority
if waiting times become too large. A job which has been waiting too long will get a high priority even at the
cost of overall system performance.

Question 13

Tietueita haetaan yksi kerrallaan levyltä, mutta todellisuudessa pääosa tietueista löytyy
levyvälimuistista. Oletetaan tässä, että yhden tietueen keskimääräinen lukuaika on T.
Kuinka satunnaisen tietueen haku kentän Union-ID mukaan (esim. Union-ID = 456 789) tapahtuu?
Kauanko haku kestää (aikayksikkönä yhden tietueen keskimääräinen lukuaika T)?

Answer 13

You have no idea where that record would be in the file. You need to read Staff one record at a time until
you find the one with Union-ID = 456 789. There are 10 000 records, and so in average you need to read
5 000 records to find the one you were looking for. It will take time 5 000 * T.
(In real life, the file cache would work very well in this case, resulting to smaller average time T to read one
record.)

Question 14

Minkä C-SCAN algoritmiin liittyvän ongelman Linuxin ennakoiva skeduloija
(Anticipatory Scheduler) ratkaisee ja kuinka se sen tekee? Mitä hyötyä siitä on? Mitä haittaa?

Answer 14

C-SCAN favor latest arriving jobs

Question 15

b. [3 p] Indeksoitu tiedosto (indexed file). Mikä on sen rakenne? Montako indeksiä siinä on? Mikä
on indeksin koko? Anna esimerkki, jolloin se olisi järkevin organisaatiotapa tiedostolle? Miksi
läjä (heap) tai indeksoitu sarjallinen tiedosto (indexed serial file) eivät olisi hyviä tiedoston
organisaatiotapoja esimerkkitapauksessasi?

Answer 15

An indexed file is a computer file with an index that allows easy random access to any record given its file key. The key must be such that it uniquely identifies a record. If more than one index is present the other ones are called alternate indexes. The indexes are created with the file and maintained by the system.

Multiple levels of indexing can be used to provide greater efficiency in access

Question 16

SCAN haitat

Answer 16

It causes long waiting time for the cylinders just visited by the head.
It causes the head to move till the end of the disk even if there are no requests to be serviced.

Question 17

levypään vuorotusalgot

Answer 17

Levypään vuorotusalgoritmit

FCFS - First-Come, First-Served
Huono, ei voi juuri optimoida
SSTF (SSF) - Shortest Seek Time First
Yksinkertainen menetelmä, jossa seuraavaksi hauksi otetaan lähin sylinteri, eli jos ollaan sylinterissä 5 ja haettavana on sylinterit 25, 7, 8, ja 15, haetaan sylinteri 8. Ongelmana hakujen kasaantuminen sylinterien keskivaiheille ja tästä seuraa levyn ääripäiden huonompi palvelu. Optimaalinen aika ja reiluus eivät kohtaa.
SCAN - elevator, eli hissialgoritmi
SSTF:ään verrrattuna hissialgoritmissa on lisäksi muistibitti (UP/DOWN), joka pitää kirjaa levypään liikkeen suunnasta. Jos suuntana on UP, haetaan seuraavaksi sylinteri, joka on lähimpänä ja on nykyisen kohdan yläpuolella. Jos yläpuolella ei ole enään haettavia sylintereitä, vaihdetaan muistibitin arvoksi DOWN ja lähdetään alaspäin. Reilu, mutta huonompi vaste juuri ohitetulla kulun alkupään uralla kuin C-SCANilla.
C-SCAN - Circular SCAN
Toimii kuten hissialgoritmi, mutta palvelee vain toiseen suuntaan mentäessä. Reilu, takaa paremman worst case-vasteen kuin SCAN, mutta paluu on hukka-aikaa.