Operating Systems 2022/23 fall

Teine kodutöö

Kirjutada graafilise kasutajaliidesega simulaator mäluhõivamisalgoritmide töö visualiseerimiseks.

• Protsesside konfiguratsiooni kirjeldab muster kujul 1,10;6,6;3,7;2,4;1,6;5,2;1,4;5,2;3,1.
  • Mustris on semikoolonitega eraldatud protsessid, iga protsessi kohta komaga eraldatud mälumaht (esimene positiivne täisarv) ja kestus sammudes (teine positiivne täisarv).
  • Kokku on kuni 10 protsessi.
• Kasutaja saab valida 3 olemasoleva testmustri vahel.
• Kasutajal peab olema võimalus sisestada oma testmuster.
  • Testmustrit peab saama kasutada korduvalt erinevate algoritmide proovimiseks, ilma et seda peaks uuesti sisestama.
• Mälumaht on 50 ühikut ning algul on kogu mälu vaba.
• Eeldame, et protsessid töötavad paralleelselt (pole mäluhalduse asi, kuidas nad oma sammude jooksul töö tehtud saavad - on ainult oluline, mis ajahetkedel mälu vabastatud saab).
• Ajaühikuks on üks samm.
  • Samm on aeg, mille jooksul olemasolevad protsessid teevad oma tööd ning mille lõpuks võivad oma töö lõpetada ja mälu vabastada.
  • Enne uue sammu täitmist võetakse järjekorrast järgmine saabuv uus protsess, antakse talle tema soovitud mälu ühe terve tükina ja käivitatakse ka see protsess taustal.
  • Seega on protsesside saabumise ajahetked sisuliselt 0,1,2,3,...
• Igal sammul lõpetatakse kõigepealt sel sammul lõppema pidavad protsessid ja alles siis tuuakse sisse järgmiseks sammuks mälu hõivav protsess.
• Kui mõni protsess mällu ära ei mahu, siis sellest tuleb teada anda ja selle juures algoritmi töö lõpetada.
• Algoritmidel loendame tükke kõigil juhtudel algusest ehk väiksema numbriga mälutükkide poolt.
• Algoritmides võetakse valitud tükist kasutusele alati alguse ots (tüki lõpust võib vaba ruumi üle jääda).
• Programmis peavad olema realiseeritud kõik järgmised algoritmid:
  1. first-fit (kasutada esimest sobivat vaba tükki)
  2. last-fit (kasutada viimast sobivat vaba tükki)
  3. best-fit (kasutada väikseimat piisava suurusega vaba tükki, mitme võrdse puhul neist esimest)
  4. worst-fit (kasutada kõige suuremat sobivat tükki, mitme võrdse puhul neist esimest)
  5. random-fit (kasutada juhuslikult valitud tükki)
• Iga algoritmi töö tulemusel peab saama näha iga sammu järel mälu vabade ja hõivatud mälualade visuaalset kujutist ning märki sellest, kui protsess ei mahtunud ära.
  • Ei pea simuleerima tekkinud protsesside töö lõppemiseni, piisab ainult hõivamise sammude simuleerimisest.
• Eeldame mälu dünaamilist tükeldust, mitte fikseeritud suurusega tükke.
• Protsesside nimesid/numbreid peab pildilt näha olema.
• Vastata lisaks järgmisele küsimusele:
  • Kas meie ülesande tingimustel esineb a) sisemist fragmenteerumist ja b) välist fragmenteerumist? Miks?

Hindamisel võtavad punkte maha:

• mõnede algoritmide realiseeriminata jätmine
• vead algoritmide realisatsioonis, näiteks vale tüki valimine, järjestikuse vaba ruumi "kokku kleepimata" jätmine, protsesside eluigade valesti arvestamine
• programm ei anna adekvaatselt teada, et mingil sammul enne töö lõppu polnud võimalik mälu anda
• protsesside algushetkede edasi lükkamine või tulevikust varasemaks toomine
• kasutajaliidese võimetus spetsifitseeritud kujul sisendit ühe sõnena vastu võtta ja parsida
• kasutajaliidese arusaamatus või mittetoimimine

Programmeerimiskeel ja -raamistik on vabad.

Tähtaeg: 16.11.2022 (pikendatud kuni 24.nov)

Näitemustrile 1,8;35,4;3,6;4,2;1,4;3,3;1,2;5,1;50,1 vastavad näidisväljundid (random-fit peaks erinevatel käivitamistel erinevaid tulemusi andma):

Siin on aga näitemustrile 1,8;7,4;10,6;25,2;1,4;13,3;6,2;8,1;50,1 vastavad näidisväljundid (random-fit peaks vahel ka veaga lõpetama):