}
Relocatie bij statische partitionering komt e bep proces altijd in zelfde blok → simpele relocating loader (bij 1e keer inladen alle relatieve geh-verwijzingen vervangen door absolute) anders: HW support nodig → dynamic runtime loading (alle adressen relatief: optellen met basisregister, vergelijken met grenzen)
7.3
Pagineren
proces opdelen in pagina’s, geh opdelen in pageframes (zelfde grootte) ⇒ geen externe fragm, enkel interne bij laatste pagina v proces page table vr elk proces → nt alle pages mtn op1volgend z: logisch adres = pagenr + offset in page 216 vb: 16bit adren , page=1kB=1024B → 1024 = 64 pages, pagenr = 2 log 64 = 6 1e bits = k, rest = offset rel adres 1052 = (000001)(0111011110): page 1, offset=478 ⇒ fysiek adres = k x 1024 + offset
2
7.4
Segmentering
prog opdelen in segmenten, nt alle segmen zelfde lengte ⇒ gn interne fragm, minimum externe adres = # bits vr segment nr, rest=offset binnen segment, te vermenigvuldigen met basenr segment
Hoofdstuk 8: Virtueel geheugen 8.1
HW & besturingsstructuren
segmentatie & paginering → nt voll progr in geh, enkel residente set ⇒ progr k groter zijn dan effectief geh → programmeur gebruikt virtueel geh logisch adr nt in geh → interrupt → blocked dr OS → OS haalt processtuk binnen in RAM (I/O request + ander proces activeren + I/O interrupt indien processtuk binnengeh + ready) mogelijk nadeel: trashing (veel swappen) → vermijden 8.1.1
Paginering
1.
HW onderst bij paginatie: P-bit = present, M-bit = modified
(a)
2.
(b)
probl: paginatietabellen k hl groot w → ook pagineren vb (fig b): adren v 32bits, pagegrootte v 212 bytes → 220 pages → page table met 220 Page Table Entries (PTE’s), 4b per PTE = 4MB → in viruteel geh plaatsen en pagetable maken die verwijst naar je user page table = 4kb adres vertaling: 1e 10bits is pagina in 1e page table, 2e 10bits = voor user page table Ge¨ınverteerde page table: pagenr (n bits) vertaald naar hashtabel die verwijzing bevat (adres v m bits, n>m) naar ge¨ınverteerde pagetable die de pagetableingangen bevat. Hashtabel bevat 1 item/werkelijke geh-pageframe, nt per virtueel “ge¨ınverteerd” omdat geordend op framenr ipv virtueel pagenr
3
4.
Chain = koppeling naar ander item als andere hash nr zelfde wijst: overloop Translation Lookaside Buffer TLB ∼ cache: bevat PTE’s die meest recent zijn gebruikt, bij TLB hit vlugger pagenr gevonden, bij TLB miss opzoeken in pagetable, als P-bit op 1, gevonden & toevoegen aan TLD, als P=0 ophalen & P=1 zetten Paginagrootte: • grote paginagrootte: effici¨entere overdr8 mr meer page faults • kleine: minder interne fragm mr groot # pages → deel v pagetable op HDD nieuwe progr-technen leiden tt mr pagefaults (overtreden lokaliteitsprincipe) - vb OO, multithreading
8.1.2
Segmentering
3.
Voordelen: • • • •
gemakkelijker omgaan met groeiende gegevensstructuren onafhankelijke compilatie van programma’s gemakkelijk delen v segmenten door verschillende processen gemakkelijker toegangsbeheer
Per proces e segmenttabel, elk STE = beginadres + lengte (als controle) v segment 8.1.3
Comb paginering & segmentering
voordeel segmentatie = logisch opdelen programma in dynamische segmenten voordeel paginering = interne fragm ↓ 1st segment zoeken → juist page table daaruit → uit page table juist frame → + offset = fysiek adres virt adres: segm # k page # k positie 8.1.4
aspecten ontwerp OS bij segmentering & paginering
doel: goede performantie dr optreden v paginafouten ↓ + OS beslist welke pagina’s uitgewisseld w Andere aspecten die prestatie van systeem beinvloeden: grootte van RAM + snelheid RAM/HD + omvang/aantal/gedrag processen ⇒ optimale strategie 8.2
BS-software
8.2.1
Strategie bij vervanging
welke page uit RAM? page zoeken die langst nt gebruikt zal w - vergrendelde frames mogelijk • • • •
optimaal: pagina vervangen die langst nt nodig is → onmogelijk FIFO → vaak minder optimaal LRU → veel overhead dr tijd bijhouden clock: extra Use bit per frame, als frame i buffer komt w U=1 geset & wijzer wijst nr volgend frame. Als vervanging nodig, wijzer gaat rond & kijkt of U=0, als wijzer e frame passeert w U veranderd. Als de wijzer e frame vindt met U=0 w dit geswapt.
4
Verfijning klokstrategy: extra Modified bit, 1st ongewijzigde (M=0) frames vervangen. Algoritme: •
•
buffer doorzoeken vanaf huidige positie v wijzer, U w nt gewijzigd bij deze rondgang, 1e frame met U=0 & M=0 w geswapt. mislukt stap 1, doorzoek ng eens mr zoek frame met U=1 en M=0, bij deze rondgang w U=0 geset mislukt stap 2, alle U=0, stap 1 herhalen & indien nodig stap 2
8.2.2
Beheer residente set
•
hoeveel pagina’s toewijzen a/e actief proces? welke pagina’s in aanmerking vr vervanging? 1.
2.
8.2.3
Grootte RS: als # pages/proces <→ # processen hoog, minder swapping MAAR # pagefaults groot Fixed allocation: vast # pages/proces ↔ Variabel allocation Vervangingsbereik: Local scope (vervang pages v zelfde proces) ↔ Global scope (kiezen uit alle onvergrendelde pages, nt mogelijk met Fixed allocation) • Fixed alloc + Local scope: te weinig pagina’s/proces → veel paginafouten & te vl pagina’s/per proces → veel swapping • Variabel alloc + Global scope: pagina’s k afgenomen w v andere processen • Variabel alloc + Local scope (a) wijs # pagina’s toe a proces bij laden in geheugen (b) selecteer bij paginafouten e pagina uit residente set v proces (c) evalueer af en toe de toewijzing & verhoog/verlaag residente set Opkuisstrategie
wnnr moet gewijzigde pagina w weggeschreven? 2 strategie¨en: • •
Demand cleaning: wegschrijven wnnr geselect vr vervanging → neg: w8en op 2 paginaoverdr8en Precleaning: versch pages samen in 1x wegschrijven → neg: te veel pagina’s wegschrijven die evt ng gewijzigd zullen w vr ze vervangen w
8.2.4
Toezicht op procesbelasting
nivo v multiprogr = # processen aanw in geh als # ↑→ betere benutting processor als te veel ↑→ veel processen geblocked, omvang RS/proces ontoereikend → Trashing Oplossingsstrategie¨en: •
voer enkel processen uit met voldoende grote RS 5
• •
houd bezettingsgraad v paging apparaat op 50% bepaal # processen adhv snelheid v wijzer bij cirkelvormige buffer, als trage snelheid, 2 oorzaken mogelijk: weinig pagefaults OF veel ongebruikte residente pages ⇒ nivo v multiprogrammeren↑
Welke processen opschorten? • • • • • •
proces met laagste prioriteit (∼afh v gebruiker) proces dat paginafout veroorzaakt (∼proces w toch al geblokkeerd) laatst geactiveerd proces (∼minder pages al aanwezig) proces met kleinste RS (∼kleine moeite om opnieuw in te laden) grootste proces (∼veel vrije frames beschikbaar) proces met grootste resterende uitvoeringstijd (∼SPN)
Deel IV Scheduling Hoofdstuk 9: Scheduling bij 1 processor Scheduling = inroosteren, doel: w8rijvertragingen ↓ + prestaties maximaliseren 9.1
Soorten scheduling
• • •
Long Term: bij exit v proces & als processor te weinig actief (nieuwe processen toevoegen) Middle Term: bij oneffici¨ente geh-alloc, klok/IO-interrupts, system calls & signals (swapping) Short Term (dispatcher, volgend proces vr uitvoering selecteren): criteria:
User oriented
kwantitatief (prestaties) turn-around time response time deadlines
System oriented
9.2
throughput processorgebruik
kwalitatief voorspelbaarh (variantie op response& turn-around tijden) fairness prioriteiten respecten gebruik systeem resources balanceren
Algoritmen voor Scheduling
selectieftie : bep welk proces als volgende de processor krijgt, gebaseerd op prioriteit, vereiste systeembronnen & uitvoeringskenmerken v/e proces: • • • • •
w = wait time (tijd die al w8end is doorgebr8) e = execution time (tijd al uitgevoerd) s = service time (totale bedieningstijd v/e proces, incl e) turnaround time = totale tijd in systeem = s+w normalized turnaround time = turnaroundtime servicetime
beslissing: op welk moment uitvoeren: 6
• •
nt-pre¨emptief: bij einde of blokkering v proces pre¨emptief: bij nieuw proces, bij interrupt of periodiek (klokinterrupt)
9.2.1
First Come First Served - FCFS
nadelen: • •
slecht vr korte processen: als net na lang proces, mtn ze vl langer w8n dan ze mtn uitgevoerd w neiging om processorgebonden processen voorrang te geven op I/O gebonden processen (k leiden tt ineffici¨ent processorgebruik en I/O gebruik): bij uitvoer processorgebonden moeten alle IO’s wachten → IOapparaten k ondertss ook werk verrichten w het processorgebonden proces geblokkeerd, krijgen alle IO’s kort de processor en heeft de processor vlug gn werk meer
FCFS vaak gebruikt met prioriteiten 9.2.2
Round Robin - RR
Klokinterrupt met periodieke intervallen (‘q’) + FCFS ⇒ pre¨emptieve onderbreking, gedrag afh v grootte q: • •
‘q’ >: neigt naar FCFS ‘q’ <: veel overhead dr vl wisseling processen
⇒ ‘q’ iets groter dan doorsnee interactie nemen voordelen: werkt goed bij timesharing & transactieverwerking nadelen: oneerlijk bij mengeling IO - & processorgebonden jobs (∼ slechtere prestatie IOgeb): IO korte tijd processor nodig, daarna w8en op IO, processorgebonden gebruikt grootste deel timeslice en kmt direct trug in ‘gereed’ ⇒ Virtual RR - VRR: bijkomende FCFS-w8rij wrin processen kmn die v IO-afhandeling kmn, deze krijgen voorrang op w8rij ‘gereed’, mr krijgen mr processor vr q − ti jd die ze al processor hadden. 9.2.3
Shortest Proces Next - SPN
nt-pre¨emptief, w8rij ‘gereed’ altijd sorteren dat 1e proces altijd kortste is, langere antw-tijd vr processorgebonden jobs probleem: tijd schatten? • • •
batch-taken: door programmeur productie-omgeving = vaak zelfde jobs: statistieken interactieve processen: gemiddelde bijhouden v elke burst v elk proces: Tn n−1 T1 + T2 + ... + Tn → Sn+1 = + Sn → Sn+1 = α Tn + (1 − α)Sn n n n α = 0.8 → recente observaties belangrijk α = 0.2 → alle observaties belangrijk
Sn+1 =
0<α<1
7
9.2.4
Shortest Remaining Time - SRT
pre¨emptieve versie SPN: onderbr als korter proces toekomt in w8rij, ook schatting service time nodig & starvation v langere processen mog • • •
tov FCFS: gn bevoordeling v langere processen tov RR: gn extra interrupts tov SPN: beter omlooptijden (∼kortere taak krijgt voorrang)
9.2.5
Highest Response Ratio Next - HRRN
• • •
normalized turnaround time (NTT) zo klein mogelijk houden vr elk proces → proces met hoogste te verw8en NTT, nt pre¨emptief ook schatting v service time nodig + starvation langere processen mogelijk houdt rekening met levensduur proces & kortere processen licht bevoordeeld
9.2.6
Multilevel Feedback - FB
processen straffen die al langer w uitgevoerd dr ze naar w8rij met lagere prioriteit te vrplaatsen na time slice ‘q’, overal RR behalve laatste w8rij = FCFS variant: ‘q’ = 2i voor w8rij i 9.3
Prestatievergelijking
Factoren die prestaties be¨ınvloeden: • • • •
waarschijnlijkheidsverdeling v bedieningstijden effici¨entie v mechanisme vr scheduling & contextwisseling vorm v I/O aanvragen prestaties v I/O subsysteem
Wachtrijanalyse: als aankomsttijden Poisson-verdeling vertonen EN bedieningstijden exponentieel 1 NT T = 1−ρ , ρ=bezettingsgraad processor verdeeld z ⇒ servicetime praktisch: prioriteiten onafh v verw8e bedieningstijden - vb: RR, FCFS
8
Hoofdstuk 10: Scheduling bij multiprocessing en realtime 10.1
Scheduling bij meerdere processors
clusters (loosely coupled), functional dedicated processors (hfd- & IO-processors) OF thightly coupled (meerdere processors met zelfde RAM, IO, ...) Granulariteit: freq v synchronisatie tss processen in systeem: • • • •
onafh parallelliteit: systeem met timesharing grof gegranuleerde parallelliteit: verz gelijktijdige toepassingen gemiddeld gegranuleerde parallelliteit: verz threads binnen 1 proces (aanpassen scheduling algoritme nodig) fijn gegranuleerde parallelliteit: parallelliteit binnen 1 machine-instructie
Ontwerpaspecten: •
•
•
Toewijzing processen aan processors: – statisch: proces permanent toegewezen aan zelfde processor, 1 korte termijn w8rij/processor voordelen: minder overhead vr scheduler & groepscheduling/gangscheduling nadelen: performantie (lege wachtrij bij ene, overvolle bij andere processor) – dynamisch: 1 KT-w8rij vr hele systeem, proces op willek processor variant: dynamic load balancing (threads verplaatsen nr andere queue) – master/slave: master beheert kernelfties & is verantw vr scheduling nadelen: kritische fout bij master legt systeem plat & master k bottleneck w – peer oriented: elke processor = gelijkwaardig & elke processor voert scheduling uit vr bep processen → voorkomen dat 2 processoren zelfde proces kiezen Gebruik v multiprogrammering vr individuele processoren - bij toepassingen met grove granulariteit: multiprogrammering = OK - bij toepassingen met gemiddelde granulariteit: multiprogrammering = OK/NOK (als vl processors beschikbr, nt alle processors bezighouden mr zorgen vr beste gem prestaties vr de toep, toep met threads k mr goed werken als alle threads beschikbr z vr gelijktijdige uitvoering) Toedeling v processen: FCFS, RR, HRRN,...?
Scheduling v processen Bij multiprocessors is keuze schedulingsalgoritme nt zo belangrijk, vb FCFS, lang proces op ene processor → korte nemen andere processor Scheduling v threads voordelen van threads: • • •
beter structureren v programma’s gelijktijdige I/O & verwerking benutten echte parallelliteit i/e toepassing
opm: kleine verschen in beheer & scheduling k significante invloed h op prestaties aanpakken: •
load sharing: 1 w8rij (↔ load balancing: werk mr permanent toegewezen a processor) – voordelen: ∗ werklast gelijkmatig verdeeld ∗ gn gecentraliseerde scheduler nodig ∗ w8rij k op versch manieren w opgebouwd – nadelen:
9
∗
•
•
•
centrale w8rij: → mutual exclusion (slechts 1 processor i/d w8rij) nodig, problematisch bij groot # processoren ∗ pre¨emptief onderbr thread wss nt verder uitgevoerd op zelfde processor (→ problemen met cache-on-processor) ∗ wss nt alle threads v 1 proces gelijk behandeld, probleem als dit nodig is ondanks nadelen meest gebruikte techniek – versch versies: ∗ FCFS: (beste) ∗ laagste # threads 1st: ‘gereed’ = w8rij met prioriteit, prioriteit v processen = processen met minst # ingeroosterde threads hoogste prioriteit ∗ pre¨emptief laagste # threads 1st groepsscheduling/gangscheduling: groep gerelateerde threads ingeroosterd om gelijktijdig te w uitgevoerd dr # processoren voordelen: – # blokkeringen dr synchrtie rel klein (samen uitvoeren v units mt hoge interactiegrd) – schedulingoverhead relatief laag (1 beslissing invloed op meerdere processoren) processortoewijzing mogelijk: stel 1 proces met 4 threads & 1 proces met 1 thread. Als elk proces e processor krijgt, verspilling van 2e processor want mr 1 thread. Geef 1e proces 4/5 v/d tijd en 2e proces 1/5 → minder verspilling vaste processortoewijzing (extreme vorm groepsscheduling): reserveren v/e groep processors vr 1 toep vr ganse levensduur, 1 processor/thread → bij IO processor ongebruikt & gn multiprogrammering, MAAR: – processortijd nt belangrijk bij groot # processoren – snellere uitvoering v programma dr vermijden proceswisselingen ⇒ # threads ≤ # processoren houden dynamische scheduling: veronderstel mechanismes om # threads per job dynamisch a/t passen (afh v # beschikb processoren) Listing 2: algoritme1 process . request processors ( int aantal ) { i f ( ongebruikte processors ) assign processors else 1 . zoek p r o c e s met m e e r d e r e p r o c e s s o r e n aan t o e g e k e n d 2 . neem e r e e n t j e van a f 3 . ken p r o c e s s o r t o e aan h e t nieuw e p r o c e s else wacht efkes in queue } Listing 3: algoritme2 process . release processors ( int aantal ) { 1 . g e e f 1 p r o c e s s o r aan a l l e p r o c e s s e n i n queue 2 . g e e f r e s t van v r i j e p r o c e s s o r s op b a s i s v FCFS }
10
10.2
Realtime scheduling
• •
hard realtime task: schade indien begin of einde v taak nt vr deadline soft realtime task: toch ng zinvol om taak na deadline uit te voeren
Kenmerken realtime BS: •
•
• • •
Determinisme: taken op bep tijd/periodisch uitvoeren (∼ vertraging vraleer e interrupt w bevestigd dr OS) 1. snel k reageren op events (∼ interrupts) 2. voldoende capaciteit om verzoeken af te handelen binnen tijdinterval Responsiviness (∼ tijd nodig om interrupt af te handelen) 1. tijd om interrupt af te handelen 2. tijd om interrupt service routine (ISR) uit te voeren 3. invloed v nesten van interrupts User influence: opgeven prioriteit aan taken, welke processen zkr in RAM mtn blijven,... Reliability: verlies k prestaties↓ of rampzalige gevolgen h Fail-soft werking - stabiliteit: fouten opvangen zonder werking fundamenteel te hinderen
⇒ KT Scheduler zeer belangrijk! Mogelijke schedulingstrategie¨en: • •
pre¨emptieve scheduler met RR: realtime proces 8raan queue prioriteitsgestuurde, nt pre¨emptieve scheduler: RT proces 1e in queue – prior-gestde pre¨emptieve - met onderbrekingspunten: w8n op volgend OP – onmiddellijke pre¨emptieve scheduler met RR: onmiddellijk onderbreken
Deadline Scheduling: beschikbare info vr taak: • • • • • •
tijdstip ‘ready’ (vral bij periodieke taken) begindeadline/einddeadline (mstal 1 v/d 2) verwerkingstijd (soms gekend, anders berekend gemiddelde) resource requirements prioriteiten (hard RT tasks (absolute prior, faling bij missen) ↔ soft RT tasks) subtaskstructuur (verplichte subtask (harde prior) ↔ facultatieve)
Frequentie Scheduling (Rate Monotonic Scheduling - RMS): prioriteit toekennen obv freq v taak • • • •
periode = T = tijdsinterval tss aankomst v 2 instanties v taak (s) frequentie = T1 (Hz) verwerkingstijd = C = tijd nodig om taak te voltooien bezettingsgraad = U = C/T
⇒ hoogste prioriteit = taak met laagste T - hoogste freq → grafiek v prioriteit ifv freq = monotoon stijgende ftie Om alle deadlines (bij freq-scheduling) te halen moet gelden: ∑ni=1 CTii ≤ 1 1
bij RMS moet gelden: ∑ni=1 CTii ≤ n(2 n − 1) Prioriteitsinversie: probleem als taak met hogere prioriteit mt w8n op taak met lagere, vb Marslander Pathfinder (in dalende prioriteit): • • •
T1 : periodiek controleren toestand SW T2 : beeldgegevens verwerken T3 : tests uitvoeren ivm toestand apparatuur
11
Oplossing: prioriteit wisselt zodra taak met hoge prior blokeert dr resource
Deel V Invoer/uitvoer en bestand Hoofdstuk 11: I/O-beheer & schijfscheduling 11.1
I/O-apparaten
• • •
human-readable: muis, printer, scherm, keyboard, ... machine-readable: HD, RAM, sensors, controllers, ... communication: modems, digitale datalijnen, ...
Verschilpunten: gegevenssnelheid, toepassing, complexiteit v besturing, eenheid v overdr8 (stroom v bytes of per blok), weergave v gegevens & foutcondities. 11.2
Organisatie v/d I/O-functie
• •
Geprogrammeerde IO: CPU geeft IO-opdr8 & w8 actief op voltooiing ervan Interruptgestuurde IO: IO-opdr8 aan IO-module & gaat verder met iets anders tt interrupt, gegevens dr CPU in geh gezet Directe geheugentoegang (DMA): module zet gegevens direct in geh + interrupt
•
(c)
(d)
(e)
12
Evolutie I/O-functie: • processor directe controle over device • toevoegen v I/O module (voorzien v interfaces) – geprogrammeerde I/O – interruptgestuurde I/O – directe geheugentoegang • toevoegen v processor aan I/O module (met I/O specifieke instructieset) • toevoegen v geheugen aan I/O module ⇒ loskoppelen IO-fties → prestaties CPU↑ DMA: kan cpu nabootsen & controle overnemen, draagt gehele blok over nr cpu (als cpu bus nt nodig hft ofwel Cycle stealing) - configuraties: • CPU, IO, DMA, HDD, ... allemaal op zelfde bus → oneffici¨ent, 2 systeemcycli/woordoverdr8 • DMA & IO-functies ge¨ıntegreerd in 1 → minder systeemcycli • via DMA naar IO-bus → uniforme interface 11.3
Aandachtspunten vr het BS-ontwerp
ontwerpdoelstellingen: • effici¨entie: IO-apparaten traag i vgl met RAM & processor • generaliteit: verbergen v bijzonderheden v IO-apparaten in low level routines (hi¨erarchische structuur v OS → uniforme benadering v IO op hogere nivo’s)
Figuur 1: Logische structuur IO-functie • • • •
Logische IO: simpele functies voor gebruikers Apparaat IO: omzetten naar juiste reeks instructies Scheduling & besturing: het feitelijk plaatsen in w8rijen + inroosteren bij IO met opslag dat bestandssysteem ondersteunt: directorybeheer, bestandsbeheer & fysieke indeling 13
11.4
I/O-buffering
als inlezen gegevens & w8en erop: oneffici¨ent (progr onderbroken) & mogelijk swapping probleem: • •
ingelezen data moeten in RAM blijven tt na gegevensoverdr8 deadlock mogelijk: leesopdr8 gegeven (w8en op data) → proces uitswappen → IO geblokkeerd
Oplossing: bufferen → blokgerichte apparaten (schijfgeh, tapes, ...) & stroomgerichte - (printers) • • • •
geen buffer: uitvoeringstijd (UT) per blok = T (tijd vr invoeren blok) + C (consumptie blok) enkelvoudige buffer (∼ volgende te verw8en blok op voorhand inlezen): UT/blok = max(C,T) + M (tijd vr verplaatsen blok) dubbele buffer (∼ invoeren + verplaatsen tegelijkertijd): UT/blok = max(C,T) cirkelvormige buffer: opvangen IO bursts
11.5
Schijfscheduling
RAM & processor snelheden >>> snelheden IO-apparaat
Figuur 2: parameters voor schijfprestatie • • • •
seek time = Ts = opstarttijd + reistijd + bevestigingstijd = +-5 a´ 10s rotatietijd r: stel 15000 rpm → rotatievertraging gem 2ms b met b = # bytes, N = # bytes per spoor, r = toeren/SECONDE data transfer time = T = rN 1 b totale gem toegangstijd = Ta = Ts + 2R + rN
Strategi¨en voor scheduling v schijf 1. 2. 3. 4. 5. 6.
FIFO: voordelen: eerlijk, goed gedrag bij beperkt # processen & geclusterde aanvragen nadelen: slecht gedrag bij groot # processen met ongeclusterde aanvragen Prioriteit gebaseerd: voordelen: snelle antw-tijd vr interactieve jobs nadelen: omzeilen dr langere processen op te delen in kleinere jobs LIFO: voordelen: snelle verplaatsing v sequenti¨ele bestanden nadelen: starvation mogelijk Shortest Service Time First - SSTF: kies spoor met kleinste verplaatsing voordelen: zeer effici¨ent ↔ nadelen: deadlock mogelijk SCAN = ‘liftalgoritme’: doorloop requests in 1 richting voordelen: redelijk effici¨ent ↔ nadelen: vrdeel vr recent doorkruist gebied C-SCAN: requests in 1 richting doorlopen voordeel: eerlijk ↔ nadeel: minder effici¨ent
probleem: arm k blijven plakken bij gebieden ⇒ • •
N-step-SCAN: cre¨eren v meerdere w8rijen, elke w8rij N elemen & elke deelrij met SCAN aflopen FSCAN: 2 w8rijen, bij begin SCAN 1 w8rij leeg, nieuwe requests in 2e
14
11.6
Redundant Array of Independent Disks - RAID
doel: versch IO-aanvragen parallelliseren & mogelijke fouten verminderen. Eigschen : • • •
set v fysieke schijfstations die dr OS w behandeld als 1 logisch station gegevens verdeeld over fysieke schijven v array redundante capaciteit gebruikt vr opslaan pariteitsgegevens
1.
RAID 0: gn redundantie. Voordelen: • gelijktijdig afhandelen v I/O requests indien op verschillende schijven • wssheid dat opeenvolgende strips w geladen groot (→ horizontaal) vereisten: grote overdr8scapaciteit (dr controllerbussen, I/O bussen, adaptors, ...) & aanvragen typisch > lengte v 1 strip RAID 1: gespiegeld. Voordelen: • read-request kan afgehandeld worden dr 2 schijven • gegevens k parallel bijgewerkt w bij write-request • recovery gemakkelijk dr duplicatie Nadelen: • kosten → dubbele schijfruimte → enkel essenti¨ele bestanden dupliceren • slechtere performantie indien meer schrijfbewerkingen RAID 2: redundantie met hamming code (gebruiken bij grote kans op fouten) aanpak: zeer kleine strips (∼1 byte / 1 woord) → parallelle overdr8 gegevens & hamming code: correctie 1bit fouten, detectie 2bit fouten nadelen: ng steeds veel redundantie (nl log(# schijven)) RAID 3: pariteit via verweven bits X 4(i) = X 3(i) ⊕ X 2(i) ⊕ X 1(i) ⊕ X 0(i) voordelen: herstel na crash 1 schijf & zr klein strips → parallele overdr8 v gegevens schrijfstraf: X 40 (i) = X 4(i) ⊕ X 1(i) ⊕ X 10 (i) RAID 4: pariteit op blokniveau, ook schrijfstraf voordelen: rel grote blokken → parallelle afhandeling IO-requests nadelen: pariteitsschijf betrokken bij elke schrijfopdracht (bottleneck) RAID 5: oplossing vr bottleneck bij RAID 4 nl gedistribueerde pariteit op blokniveau RAID 6: 2voudige redundantie voordelen: hoge reliability (2 schijven mogen tegelijk kapot gaan) nadelen: lagere performantie bij schrijfopdrachten
2.
3.
4.
5.
6. 7.
Hoofdstuk 12: Bestandsbeheer - File Systems 11.1
User Interface
11.1.1 File Concept •
• • •
logische kijk op informatie-opslag – bestand = benoemde collectie v gerelateerde info – text, afbeelding, binaire data, executable, ... Bestand-attributen: naam (symbolisch, lengte, case sensitive?), type, locatie, grootte, bescherming, tijd & datum v laatste gebruik/aanpassing/aanmaak bestand = abstract data type (ADT) Bestand-operaties: 15
create: ruimte alloceren, entry in dir vr file → pointer nr FCB → pointer nr attributen write read(Name, Buffer): bestand zoeken in dir, lezen vanaf huidige positie (pointer) & pointer verplaatsen – reposition – delete – truncate: alles i/d file wissen mr file zelf blijft met zn attributen bestaan – rest: append, copy, read attributes, write attributes Bijna alle operaties h mt read/write te maken FCB = File Control Block (inode in Linux): bij lezen/schrijven altijd gewijzigd Open File Table = tabel v alle FCB’s v geopende files in RAM ⇒ als file.close(): kijken hoeveel processen die file gebruiken, als 0 file sluiten, anders # refies -1 extra: – (deel v) bestand ‘locken’ – memory-mapped file: deel v virtueel geh verbonden met file → aanspreken als primair geh Bestandtypes: – support dr OS? afh v grootte OS – type deel v naam (extensie, Win), in DIR-entry (Apple) of door ‘magic number’ in file attrib (Unix/linux) – type afh v cre¨erder programma – type geeft interne structuur weer (vb .txt: lijnen text, .src: main + methodes, ...) – minstens 2 types: executables & andere Interne bestandsstructuur: – Schijf = vaste blok-lengte, 1 blok = enkele sectors = cluster – Bestand = sequentie v ‘records’, variabele lengte, 1 file/blok, gn nieuwe file beginnen in rest v/e blok gemiddeld 1/2 v/e blok per file ‘verloren’ – Interne fragmentatie want recordlengte 6= bloklengte Toegangsmethodes: – Sequenti¨ele toegang: in volgorde (vb compiler), read/write next, reset (positie trug op begin), skip N records → cf Tape – Directe toegang: willekeurig (database toegang), read/write n, reposition n, read/write next → cf Schijf verschillen: OS ofwel 1 v/d 2 of beide, gedefinieerd in bestand bij creatie sequentieel simuleren met direct acces, maar omgekeerd? – Andere toegangsmethoden: meestal bovenop Direct Access Partities: verzameling opeenvolgende cilinders: verdeling v schijf of versch schijven samenbrengen als 1 ⇒ partitie = logische schijf, met zijn eigen Virtual Table of Contents (VTOC) Directories: – effici¨entie: bestand vlug terugvinden – verschillende bestanden met zelfde naam nodig & 1 file versch namen (afh v users) – groeperen v bestanden volgens eigenschen – dir = symbooltabel: namen v entries v onderliggende dir’s/bestanden – operaties: zoeken nr bestand (pattern,wildcards, ...), bestand aanmaken/verwijderen, directorylijst weergeven, bestand hernoemen, bestandssysteem doorlopen (vb vr backup) – structuur: – – –
• • •
•
•
•
• •
16
∗ ∗ ∗
∗
∗
– –
–
Single level: simpel maar naamgeving - & groepering problen Two-level: versch namen vr versch users maar gn groepering & wat met systeembestanden? Boom structuur: padnamen (abs (v begin) of relatief (v huidige positie)), directory = speciaal soort bestand (dir=0, file=1), groepering, bestanden delen mogelijk MAAR directory verwijderen: enkel als leeg ofwel voll subtak A-cyclische grafe: meer links tss mappen dan in gwne boom dr: - pointer naar bestand/pad, symbolisch = soft link - hard link: directory entry kopi¨eren (gn verschil tss beide, consistentie bewaren) voordelen: gn 2x opslag v zelfde bestand/dir, bij wijzigen dr ene, wijziging ook bij andere, symbolische k verwijzen nr ander volume, versch namen vr zelfde bestand mog nadelen: hangende pointers bij deleten (→ referenties tellen), markeren bij traversen, harde - k nt verwijzen nr ander volume, symbolische: als file hernoemd - nt aangepast → xtra bit: soft link = 1, harde = 0 (soft link nr dir: 10, nr bestand: 11) Acyclisch houden? - Unix: symbolische links gn restrictie, harde enkele naar files - anders: cyclus detectie (tijdrovend!) Algemene grafe: cyclussen toegestaan, bij doorlopen syst markeren of ∞ lus & bij verwijdering garbage collection (ref tellen)
Bestandssysteem mounten: als je mount op plaats waar onderliggende dirs ng aanw zijn → deze nt meer toegankelijk Bestanden delen: best wel als meerdere gebruikers, dmv bep bescherming consistentie: bestandssessies open/close: veranderingen zichtbr na close // Unix: veranderingen zichtbr vr andere processen met zelfde bestand open Bescherming: Toegangstypes: 1 user gn probl, meerdere users: enkel eigen files, toegang tt alle files of gecontroleerde toegang tt alle files ∗ toegang = functie v gebruiker (per gebruiker opgeven) → flexibel mr neemt vl ruimte & wat met nieuwe gebruikers ∗ toegang cf linux: Owner, Group, Others ∗ toegang dmv passwoord (pw vr lezen, pw vr schrijven, pw voor uitvoeren → vl pw’s!
11.2
Implementatie
•
Bestandssysteem structuur: – applicatie vraagt bep instructie (Read(...)) – LFS zet om naar correcte instructie voor FS (Read(..., Record xx)) – FOM berekent juiste blok wr bestand staat – BFS checkt of in schijfcache & berekent cilinder/spoor/sector 17
•
•
• •
•
•
•
Structuren op schijf: – Boot Control Block – Partition Control Block = superblock (details v partitie) – Directories (∼ alle bestanden) – File Control Block (=iNode): rechten, data creatie/wijziging, eigenaar, groep, grootte, ... – Data blocks v bestanden Structuren in geheugen: – Partitie tabel (gemounte partities) – Directory structuren – Open File Table – Open File Table per proces – Deel v/d data blocks v bestanden/directories Virtuele File Systems: 1 bestandssysteem dat meerdere FS’s omvat Directory implementatie: – Lineaire lijst: simpel te progren mr tijdrovend doorzoeken – Hashtabel: vlug zoeken maar botsingen & vaste grootte Continue allocatie: alle blocks 8r elkr – Direct Access mog: block i = beginblock+i-1 – op1volgende blocks in zelfde cilinder – plek zoeken: first fit/best fit/next fit? – externe fragmentatie → samenpakken (tijdrovend) – hoevl plaats voorzien? groeien? (overschatting ofwel plek tekort) – variant: continue + extend Gelinkte allocatie: per block bijhouden wat volgende is, laatste wijst nr null – nieuwe file: begin & einde wijzen naar null – gn externe fragmentatie – gn pre-allocatie – bestand k groeien – enkele sequenti¨ele toegang – overhead vr pointer – bestand = gefragmenteerd – betrouwbaarh: block weg → dubbel gelinkte lijst (meer overhead) – File Allocation Table - FAT: alle pointers in 1 tabel in RAM ⇒ Direct acces mogelijk, reliability → 2x op schijf Ge¨ındexeerde allocatie: block met index naar alle blocks in volgorde – nieuw bestand: indexblock maken (leeg) – gn externe fragmentatie – sequenti¨ele & directe toegang (indexblock in RAM) – bestand k groeien 18
– – – –
•
overhead vr indexblock grootte indexblock: klein (all1 kleine bestanden) ↔ groot (mr verspilling) structuur index block (als meerdere indexen): linked, multilevel of combinatie vb Unix: directe verwijzing nr 12 blocks + Indirect block (index) + dubbel indirect block (dubbele index) + triple Vrije ruimte management: – Bit vector: 1bit/block extra (1=vrij/0=alloc), OK als in RAM – Linked List: n blocks nodig, n lees-operaties! – Groepering & tellen: 1e block + # blocks er8r ook vrij
19