Tämä materiaali syntyi kerratessani TKK:n Käyttöjärjestelmät kurssin tenttiin. Materiaalissa
on varmasti monenelaisia puutteita ja virheitä, mutta ainakin minä pärjäsin näillä tiedoilla
kohtuullisen hyvin. Yksinään tällä materiaalilla tuskin pääsee tentistä läpi.
Abstrahoi laitteiston - toimii sovelluksen ja raudan välissä
Hallitsee resursseja, optimoi laitteiston käyttöä
Palvelee sovellusohjelmoijaa
Huolehtii sovellusten suorituttamisesta prosessorissa
Käyttöliittymä
Virhetilanteiden hallinta ja niistä toipuminen
2. Prosessit ja säikeet
Rinnakkaisuus (monta prosessoria) vs. psedo-rinnakkaisuus (prosesseja vaihdetaan monta kertaa sekunnissa)
Prosessi = ajettava ohjelma, prosessin oma program counter (PC), rekisterit ja muuttujat
(Ohjelma koostuu käskyistä ja datasta ajokelpoisessa tiedostossa.
Prosessi on ympäristö, jossa ohjelma suoritetaan.)
Prosessien vaihtoväli ei ole kiinteä ja samojen prosessien uudelleen suorittaminen ei tuota välttämättä samaa aikaa.
Prosessin ja ohjelman ero
Leipuriesimerkki: kakkuresepti on ohjelma, leipuri on prosessori (CPU) ja kakun ainekset muodostavat ohjelman syötteen. Prosessiin kuuluu reseptin lukeminen, ainesten sekoittaminen ja kakun paistaminen. Jos leipominen joudutaan keskeyttämään, merkataan keskeytyskohta, tehdään jotain muuta ja palataan jatkamaan keskeytyskohdasta eteenpäin.
Prosessityypit
Daemon eli taustaprosessi on käyttöjärjestelmän prosessi, joka pyörii taustalla ja hoitaa esimerkiksi web-palvelinta tai tulostusta. Taustaprosessit käynnistetään usein käyttöjärjestelmän käynnistyessä.
Tavallinen käyttäjän käynnistämä prosessi
Eräajoprosessi - vain mainframe-järjestelmissä
Prosessien päättyminen
Normal exit (vapaaehtoinen)
Error exit (vapaaehtoinen)
Fatal error (ei-vapaaehtoinen), esim. nollalla jakaminen tai muu bugi
Killed by another process (ei-vapaaehtoinen)
Prosessien tilamalli
Aktiivinen prosessi siirtyy odotustilaan jonkin ulkoisen syyn takia (esim. oheislaitteelta tai toiselta prosessilta tarvittavan datan odotus); käyttöjärjestelmän vuorottajaohjelma (engl. "scheduler") valitsee sen tilalle uuden aktiivisen prosessin valmiustilassa olevien prosessien joukosta.
Odotuksen syy poistuu (esim. tiedonsiirto oheislaitteelta valmistuu) ja prosessi siirtyy valmiustilaan.
Valmiustilassa oleva prosessi saa vuorottajalta suoritusvuoron.
Aktiivinen prosessi siirtyy valmiustilaan, kun sille annettu aikaviipale loppuu. Vuorottaja valitsee uuden aktiivisen prosessin valmiustilassa olevien joukosta.
Jokaisella prosessilla on taulussa oma prosessielementti (PCB, Process Control Block), jossa on kaikki se tieto, mikä tarvitaan siirryttäessä Running-tilasta Ready- tai Blocked-tilaan ja takaisin. Elementin osat:
prosessin ID
prosessin tilatieto
PC
pino-osoittimen (pino = tilaa prosessin keskeytyneiden ympäristöjen tallennusta varten),
skedulointi-informaatiota (priorisointi)
muistinhallinnan informaatiota
tiedot varatuista resursseista (muisti, laitteet, avoimet tiedostot)
Muita:
Käytetty CPU-aika
Käyttäjän ID
Työhakemisto
Prosessin alkamisajankohta
Prosessien ja säikeiden eroja
Säikeille annetaan suoritusaikaa samaan tapaan kuin prosesseillekin, paitsi että aikajako suoritetaan ohjelman saaman ajan puitteissa ja säikeet priorisoidaan ohjelmallisesti.
Prosessin osat
Osoiteavaruus
Globaalit muuttujat
Avoimet tiedostot
Lapsiprosessit
Hälytykset
Signaalit ja signaalinkäsittelijät
Kirjanpito / tilinpito
Säikeen osat
PC - ohjelmalaskuri
Rekisterit
Pino
Tila
Semaforit ja niiden operaatiot
Semafori pitää yllä kokonaislukumuuttujaa (>= 0), joka kertoo kullakin hetkellä jäljellä olevien lupien määrän
Metodit
Alkuarvon asettaminen
WAIT(S) tai P(S) (hollanninkielinen lyhenne - proberen = testaa )
SIGNAL(S) tai V(S) (hollanninkielinen lyhenne - verhogen = kasvata )
Virheherkkyytensä takia semaforeja käytetään varsin vähän korkean tason ohjelmoinnissa. Käyttöjärjestelmätasolla ne sen sijaan ovat yleisesti käytössä.
Monitorit
Mikä oleellinen ero on semaforeihin kohdistuvien P/V-operaatioiden ja monitorissa käytettävien wait/signal-operaatioiden välillä?
P ei pysäytä prosessia, jos semafori on auki - wait pysäyttää aina prosessin . V kasvattaa laskuria, vaikka semaforissa ei ketään olisikaan, signal tyhjään jonoon ei aiheuta mitään tilamuutoksia.
Rinnakkaisuuden ongelmia
Esimerkkinä käytetty paikanvarausjärjestelmää.
Poissulkemisongelma, yhteisten tietorakenteiden päivitys
kaksi samanaikaista kyselijää päättää varata saman paikan
Synkronointi, tahdistaminen
paikanvarausjärjestelmä herää kyselijän tiedusteluun ja vastaa; kyselijä herää vastaukseen ja rupeaa miettimään
Lukkiutuminen, prosessit odottavat ristiin toisiansa
kaksi rinnakkaista ryhmävarausta etenee varaus kerrallaan, mutta paikkoja ei olekaan riittävästi molemmille (kummallekin tehtiin - toisistaan riippumatta - alkutarkistus, jonka perusteella paikkoja oli kummallekin - erikseen - riittävästi).
Nälkiintyminen, prosessi ei etene (prioriteetti alhainen)
kyseessä on paikanvaraus käsittämättömän suosittuun musiikkitapahtumaan; varaus alkaa klo 9.00 eikä kaikkia kyselyjä voida käsitellä rinnakkain, odottavia kyselyjä valitaan satunnaisesti (vrt suuri joukko samanaikaisia soittoyrityksiä tavanomaiseen puhelimeen), huonolla onnella jokin kysely pääsee perille vasta paikkojen loputtua.
3. Lukkiintumiset (deadlocks)
Perusmenetelmät
Lukkiintumisen laukaiseminen
Lopetetaan prosessi tai prosesseja. Lukkiutuminen on havaittava - yleensä ylläpitäjän vastuulla, koska ohjelmallisesti vaikeaa.
Lukkiintumisen välttäminen
Prosessin vaatimien resurssien määrä tiedettävä. Varataan kaikki tarvittavat resurssit heti alussa. Resurssien tuhlausta.
Lukkiintumisen estäminen
Varmistetaan, että joku lukkiintumisen ehdoista ei päde.
4. Muistinhallinta
5. I/O
ei niin tärkeä
Termejä
selitykset tähän
Ajuri (driver)
Tiedosto (file)
Hakemisto (directory)
Mount-toiminto (mounting)
RAID
Keskeytys (interrupt)
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.
6. Tiedostojärjestelmät
nice-to-know
7.4. Skedulointi
Algoritmeja
FIFO
Hyvää: periaatteelinen reiluus, yksinkertainen toteutus
Huonoa: ei tuota optimaalista tulosta, suoritussidonnaiset säikeet viivyttävät tarpeettomasti siirrännäissidonnaisia
Kiinteä prioriteetti
Kokonaissuoritustehon ja vasteaikojen minimoimiseksi siirrännäissidonnaisilla prosesseilla korkeampi prioriteetti.
Hyvää: yksinkertainen, mahdollistaa tärkeysjärjestyksn määrittämisen
Huonoa: alhaisen prioriteetin säikeet voivat nälkiintyä, koska korkeamman prioriteetin säikeet menevät aina ohi.
Vaihteleva prioriteetti
Toimii kuten edellä, mutta prioriteetti voi vaihdella jonkin algoritmin mukaisesti. Esim. I/O-sidonnaisten säikeiden prioriteettia voidaan nostaa. Poistaa nälkiintymisongelman - mikäli säie ei saa aikaa, nostetaan prioriteettia.
Kiertovuorottelu (round robin)
Kaikille säikeille vuorotellen yhtä suuri aikaviipale.
Tavallinen yhdistelmä:
Käyttöjärjestelmän säikeillä kiinteät, yleensä korkeat, prioriteetit
Käyttäjän säikeillä muuttuva prioriteetti (round robin saman prioriteetin omaavien kesken)
Reaali-aikavuorotusmenetelmiä
Rate monotonic scheduling (RMS)
Staattinen algoritmi periodisille prosesseille.
Suorittava prosessi valitaan prioriteetin mukaan. Prioriteetti lasketaan prosessin toistuvuuden perusteella.
CPU:n käyttöasteen pitää olla <= N(2^(1/N)-1), missä N on prosessien lukumäärä
Earliest deadline first
Seuraavaksi ajettava prosessi valitaan aikaisimman DL:n mukaan.
Dynaaminen algoritmi, joka ei edellytä prosessien perioidisuutta.
Voidaan hyödyntää CPU:n 100% käyttöasteella.
8.3. Hajautetut järjestelmät
"pienempi aihe"
10.1.-10.2. UNIX
Yleisiä huomioita UNIXista
Yliopistollinen ohjelmankehitysympäristö
Monta variaatiota, pitkä ja monimutkainen historia
Prosessien hierarkisuus l. kaikilla prosesseilla yksi äitiprosessi (pl. init, joka on juuri) ja nolla tai useampia lapsiprosesseja.
11.1.-11.3. Windows
Yleisiä huomioita Windowsista
Kaupallinen ympäristö sovelluksille
Myrskyisä historia
Varsinaisia hierarkisia prosesseja ei ole olemassa. Uutta prosessia luotaessa äitiprosessi saa kahvan (handle), jolla voi kontrolloida lapsiprosessia, mutta tämän kahvan voi siirtää myös jollekin toiselle prosessille.
12. Arkkitehtuuri
Erilaisia käyttöjärjestelmätyyppejä
Monoliittinen
Toiminnallisuus ytimessä
yhtenäinen ydin
ytimen ulkopuolella varusohjelmia ja kirjastoja (käyttäjärajapinta)
Huono tapa tehdä käyttis (Rakenne, jossa ei ole rakennetta)
Perinteiden painolasti
Vaikea konfiguroida ja kehittää
Ei moduleita tai paketteja - kaikki näkyy kaikille
Kerrostettu
Kerroksien tulisi kommunikoida keskenään aina kerros kerrokselta, eikä suoraan esim. kerrokselta 7 suoraan alimmalle tasolle.
7
System call handler
6
File system 1, File system 2,...
5
Virtual memory
4
Driver 1, Driver 2,..., Driver n
3
Threads, Thread scheduling, Thread synronization
2
Interrupt handling, context switching, MMU
1
Hide the low-level harware
Virtuaalikone
Tarjotaan käyttäjälle raaka (virtuaalinen) kone, joka on täydellinen kopio varsinaisesta raudasta (sis. mm. käyttäjä/kernel-moodit, I/O, keskeytykset).
Käyttäjällä mahdollisuus ajaa haluamaansa kontrolliohjelmaa
Järjestelmän sydämessä virtuaalikonemonitori
Esim. virtuaalinen 8086 moodi Pentiumissa, Java Virtual Machine
Mikrokernel
Ydin tarjoaa vain välttämättömimmät palvelut ts. mahdollisimman suuri osa palveluista on ytimen ulkopuolella
Soveltuu hyvin hajautettuihin ja sulautettuihin järjestelmiin
Luotettava, hyvä konfiguroitavuus, tasapainoisuus, skaalautuvuus