- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Zjednodušená ukázka:
Stáhnout celý tento materiálSpráva diskových zariadení Štruktúra disku
platňa, povrch
stopa, sektor (do 4K), cylinder
Adresa
číslo zariadenia, povrch, stopa a sektor
počet sektorov od 4 do 32
počet stôp je od 20 do 1500 pre povrch
V/V prenosy po sa blokoch
Na disk sa môžeme pozerať ako na trojrozmerné pole blokov
pre číslo bloku b platí b = k + s x ( j + i x t )
kde s - počet sektorov na stopu, t - počet stôp pre cylinder,
i - číslo cylindra, j - číslo povrchu k - číslo sektoru Algoritmy plánovania pohybu ramienka disku Čas, potrebný pre prenos bloku dát, pozostáva z troch zložiek:
čas pre vystavenie ramienka s hlavami,
čas pre nájdenie požadovaného sektoru - to je vlastne čas na otočenie platne
vlastný prenos dát.
V/V operáciu je špecifikovaná parametrami:
druh operácie - vstup alebo výstup,
diskovú adresu - číslo bloku, príslušný modul zo súborového systému preloží na čísla zariadenia, cylindra, povrchu a sektoru.
adresa v pamäti - odkiaľ alebo kam sa budú prenášať dáta.
počet byte-ov, ktoré sa majú preniesť Algoritmy Plánovanie podľa poradia príchodu (FCFS)
obsluhuje požiadavky podľa poradia ich príchodu (First Come, First Served)
obr.12.2
Klady – jednoduchý
Nedostatky – veľa pohybov, strata času
Algoritmus najkratšieho presunuobr.12.3
obsluhuje najskôr z frontu požiadaviek tú požiadavku, ktorá bude požadovať najmenší pohyb vzhľadom na momentálnu pozíciu ramienka.
môže zapríčiniť starváciu niektorých požiadaviek
uprednostňuje stopy, ktoré sú uprostred
dá využiť tak, že na prostredných stopách sa budú umiestňovať bloky, ktoré vyžadujú rýchly a častý prístup Algoritmy Algoritmus výťahu – obr. 12.4
zasa zvýhodnené prostredné stopy,
tam maximálna dĺžka čakania na obsluhu je rovná len počtu stôp.
Algoritmus C-SCAN (circular SCAN) obr.12.5
Algoritmus C-LOOK - obr.12.6
Výber algoritmu pre plánovanie pohybu ramienka
závisí od mnohých faktorov
požiadavky na diskové operácie závisia aj od metódy prideľovania diskového priestoru.
Umiestnenie adresárov a indexových blokov na disku je veľmi dôležité
Umiestnením adresárov na stredných stopách môže ušetriť až polovicu pohybu ramienka
Správa disku Formátovanie disku
Inicializácia systému
inicializačný program (bootstrap program)
inicializuje systém po každej stránke
adresa inicializačného programu musí byť známa
niektoré systémy - do pamäte ROM
väčšina systémov ukladá
do ROM pamätí malú časť inicializačného programu
zvyšok sa ukladá do tzv. inicializačných (boot) blokov na známej adrese na disku
disk, ktorý obsahuje takéto bloky- systémový disk (boot disk).
Správa chybných blokov
Správa diskového priestoru určeného pre výmenu Odolnosť voči chybám(Fault tolerance ) RAID(Redundant Arrays of Inexpensive Disks)
Existujú tieto štandardné RAID špecifikácie:
RAID 0 Non-redundant striped array
RAID 1 Mirrored arrays
RAID 2 Parallel array with ECC
RAID 3 Parallel array with parity
RAID 4 Striped array with parity
RAID 5 Striped array with rotating parity
RAID 1 (mirroring - zrkadlenie)
udržuje kópiu každého disku
plytvanie kapacity, drahé
zvyšuje rýchlosť čítania – číta z oboch diskov naraz
dôležité či obidva disky sú pripojené cez jeden radič – ten môže byť úzkym miestom
ak sú ľ radiče – disk duplexing
Použitie parity - menej drahý prístup
Ak máme k diskov v poli
prvých (k -1) diskov použijeme pre uloženie dát
posledný disk pre uloženie parity
ak sa poškodí ľubovolný z diskov, jeho obsah sa môže obnoviť Systém RAID Parita Základná schéma
pre n bitov b[1] ... b[n]
uložíme paritný bit = 1 ak počet jednotkových bitov je párny
Detekcia
Oprava Príklad ponúknutých riešení pre odolnosť vočí chybám z Windows NT
Zrkadlenie – RAID 1
Striped array with rotating parity - RAID 5
Spolupracujúce procesy Spolupracujúce procesy môžu byť
nezávislé procesy alebo
spolupracujúce procesy.
Príčiny spolupráce
Zdieľanie informácií
Zrýchlenie výpočtov (program je rýchlejší ak sa vykonáva paralelne v niekoľkých podúlohach)
Modularita
Výhoda (editovanie, tlač,kompilácia) Spolupracujúce procesy pomocou správ IPC (Interprocess communication )
IPC poskytuje mechanizmy pre komunikáciu a synchronizáciu činnosti.
Posielanie správ a zdieľaná pamäť nie sú vzájomne sa vylučujúce, môžu sa používať súčasne v rámci jedného procesu a systému
Základná štruktúra systému zasielania správ:
- dve základné operácie : send(message), receive(message);
Procesy P a Q komunikujú cez komunikačné linky.
Správy Linky medzi procesmi sú jednosmerné – proces môže buď posielať alebo dostavať správu
Správa môže mať buď pevnú alebo variabilnú dĺžku.
Pevná dĺžka správy dovoľuje jednoduchú fyzikálnu implementáciu, ale program musí deliť správu na rovnako veľké časti
Variabilná dĺžka správy umožňuje jednoduchšie programovanie, ale fyzikálna implementácia je zložitejšia
Implementácie prepojenia a operácií send a receive: · priama alebo nepriama komunikácia,
· symetrická alebo asymetrická komunikácia,
· automatické alebo explicitné bufrovanie,
· vyslanie kópiou alebo odkazom,
· pevná alebo variabilná dĺžka správy.
Pomenovanie Priama komunikácia
send (P, správa)- zasiela správu procesu P,
receive (Q, správa)- prijíma správu od procesu Q.
Vlastnosti spojenia
nadväzuje automaticky medzi každou dvojicou procesov, ktoré chcú komunikovať,
spojenie sa nadväzuje medzi dvomi procesmi,
medzi každým párom komunikujúcich procesov existuje jedno spojenie,
linka môže byť jednosmerná, ale väčšinou je obojsmerná.
Príklad Producent-Konzument správami Proces-producent je definovaný nasledovne:
repeat
pripraví položku v nextp
send(konzument, nextp)
until false;
Proces-konzument je definovaný nasledovne:
repeat
receive(producent,nextc);
spracuje položku
until false; Typy priamej komunikácie Symetrická - vysielajúci aj prijímajúci proces uvádzajú meno svojho partnera.
Asymetrická - len vysielajúci proces uvádza meno adresáta.
Operácie send a receive majú v tomto prípade tvar:
send (P, správa)- zasiela správu procesu P,
receive (id, správa)- prijíma správu od ľubovolného procesu;
id je premenná, ktorá obsahuje identifikátor procesu, s ktorým bolo nadviazané spojenie. Nepriama komunikácia
vysielanie a príjem správ z mailbox-ov (niekedy označované ako porty ). Sú to abstraktné objekty, do ktorých sa môže vložiť správa alebo vybrať
send (A, správa) - zasiela správu do mailbox-u A,
receive (A, správa) - prijíma správu od mailbox-u A.
Komunikačné spojenie v tomto prípade má nasledovné vlastnosti:
spojenie sa nadväzuje,
len ak procesy majú prístup k zdieľanému mailbox-u,
medzi viacerými procesmi,
medzi každým párom komunikujúcich procesov je viac komunikačných liniek a každá zodpovedá jednému mailbox-u,
linka môže byť jednosmerná alebo obojsmerná. Mailboxy 2 Vlastnosti komunikačného spojenia :
- spojenie sa nadväzuje, len ak procesy majú prístup k zdieľanému mailbox-u,
- spojenie sa nadväzuje medzi viacerými procesmi,
- - medzi každým párom komunikujúcich procesov je viac komunikačných liniek a každá zodpovedá jednému mailbox-u,
- linka môže byť jednosmerná alebo obojsmerná.
Mailboxy 3 Vlastníctvo mailboxov
proces
deklaruje premennú typu mailbox
keď sa ukončí proces, zruší sa aj mailbox
každý proces, ktorý vie meno mailboxu ho môže použiť
systém
vytvorí mailbox
posiela a získava správy z mailbox-u
zruší mailbox
Bufrovanie Komunikačná linka má kapacitu - určuje, aký počet správ sa v nej môže nachádzať, k linke je pripojený front správ.
Tri spôsoby implementácie frontov:
S nulovou kapacitou. Max. dĺžka frontu je 0, t.j. vo fronte nemôže čakať žiadna správa,vysielajúci proces musí počkať, až prijímajúci proces preberie správu. Procesy sa musia zosynchronizovať pri odovzdávaní správy - rendezvous.
S obmedzenou kapacitou. Front má konečnú dĺžku n, t.j. môže v ňom čakať najviac n správ. Ak front nie je plný, prichádzajúca správa sa doň zaradí a vysielajúci proces môže pokračovať vo svojom vykonaní bez čakania. Ak front je plný, vysielajúci proces je zablokovaný, pokiaľ sa uvoľní miesto. Bufrovanie 2 Pri automatickom bufrovaní odosielateľ nevie čí správa bola doručená – potvrdzovanie (ACKNOWLEDGMENT )
Proces P vykoná:
send (Q, správa) - zasiela správu Q
receive (Q, potvrdenie) - prijíma potvrdenie od Q
Proces Q vykoná:
receive (P, správa)- prijíma správu od P
send (P, potvrdenie)- zasiela potvrdenie P Bufrovanie 3 Iné alternatívy
Odosielateľ sa neblokuje nikdy : v prípade bez bufrovania, to znamená stratu správy ak procesy nie sú synchronizované, veľké správy sa kopírujú len raz. send(Q, sprava1) –> receive(P,sprava1)
send(Q, sprava2)
send)Q, sprava3) –> receive(P, sprava3)
Zaslanie správy len ak príde potvrdenie :
send(Q, sprava1) --> receive(P, sprava)
(Proces P čaká)
receive(Q, sprava) opätovný preklad
počas vykonania Spolupráca s užívateľom Dynamické zavádzanie
podprogramy sa nezavádzajú do pamäte, kým nie sú volané; nevyžaduje špeciálnu podporu zo strany operačného systému
Dynamické spojenie
o obrazu programu zahrnutý stub - malý úsek kódu, ktorý ukazuje, ako lokalizovať príslušnú knižničnú procedúru rezidentnú v pamäti, vyžaduje podporu od operačného systému
Prekrývanie (overlay)- (obr.8.2) Logický a fyzický adresný priestor Logické adresy
adresy generované procesorom
Fyzické adresy
adresy, ktoré používa MMU (tie ktoré sa zavádzajú do registra pamäťových adries)
LAP
množina logických adries, ktoré sú generované programom
FAP
množina fyzických adries, ktoré odpovedajú logickým adresám
Memory Management Unit ( MMU) –
mapuje logické adresy na fyzické počas behu programu (obr.8.3) Swapovanie Dočasne odsunutie procesu z pamäte na disk a neskôr opätovne vrátenie do pamäte (obr. 8.4)
Dispečer po spustení naplánovaného procesu kontroluje, či ďalší proces z frontu je v pamäti. Ak nie je a nie je voľné miesto v pamäti, odsúva (swap out) niektorý z procesov v pamäti a prisúva (swap in) požadovaný proces
Príklad:
čas pre swapovanie
proces s veľkosťou 100KB z disku s rýchlosťou 1MB/s. Prenos zaberie:
100/1000 KB za sekundu = 1/10 s = 100 ms
reakčný čas - 8 ms, celkový čas - 108 ms
Swapovanie pokračovanie Čas pre swapovanie je úmerný veľkosti presúvanej pamäte
Swapovanie a odštartované V/V operácie - problém
Sú možné dve riešenia tohoto problému:
- nikdy neodsúvať proces s nedokončenými V/V operáciami.
- vykonávať V/V operácie len cez bufre operačného systému.
väčšina systémov používa nejaký variant swapovania Súvislé prideľovanie pamäte Prideľovanie jedného úseku (obr.8.5).
je najjednoduchšou technikou správy pamäte, všetkým procesom prideľuje ten istý úsek
typická pre monoužívateľské systémy bez paralelného spracovania (CP/M, MS-DOS)
nepoužíva sa už,
Súvislé prideľovanie pamäte pokračovanie Prideľovanie viacerých súvislých úsekov s pevnou dĺžkou – multiprogramovanie
prideľuje sa pri zavadzaní programu
ochrana(obr.8.6).
relokačný register
limitný register
technika, použitá v systéme IBM OS/360, známa pod názvom MFT (Multiprogramming with a Fixed number of Tasks). Súvislé prideľovanie pamäte pokračovanie Prideľovanie súvislých úsekov s premenlivou dĺžkou
rozmery úsekov sa menia dynamicky s veľkosťou vznikajúcich procesov.
Problémy - výber vhodného úseku, vonkajšia fragmentácia, udržovanie informácie o voľných a obsadených úsekoch
Príklad - (obr.8.7, 8.8).
- plánovanie FCFS, RR (q=1) Prideľovanie súvislých úsekov s premenlivou dĺžkou pokračovanie Algoritmy výberu vhodného úseku pre umiestnenie procesu
Prvý vhodný (First-fit)
Najlepšie vyhovujúci (Best-fit)
Najhoršie vyhovujúci (Worst-fit)
Problém fragmentácie - vonkajšia
Striasanie
spojiť dohromady fragmenty do jedného väčšieho bloku, príklad - riešenie situácie z obr.8.8(e) je na obr. 8.9.
rôzne varianty striasania obr.8.10 kde p - index do tabuľky stránok d - posuv v stránke Stránkovanie Princíp
fyzická pamäť rozdelená na časti s pevnou veľkosťou - rámce.
Logický adresný priestor procesu je rozdelený na rovnako veľké bloky, nazvané stránky.
HW podpora pre stránkovanie – obr.8.11
Rozmer stránky
obyčajne mocnina 2 , od 512 bajtov do 8 KB
Ak rozmer FAP= 2m a veľkosť stránky = 2n (bajtov alebo slov), potom
vyššie m-n bity logickej adresy - číslo stránky a
n nižších bitov - posuv v stránke.
Príklad stránkovania pre 32-bitovú pamäť so 4-byte-ovou stránkou Stránkovanie pokračovanie Tabuľka rámcov
Informácie o voľných rámcov obr.8.14
Tabuľka stránok
HW podpora
tabuľka stránok - v sade registrov
tabuľka stránok v pamäti - jej adresa sa nachádza v registri tabuľky stránok (Page-table base register, PTBR), dvojnásobný počet prístupov do pamäte Stránkovanie pokračovanie Asociatívna cache pamäť (Translation Look-aside Buffers - TLB ), počet položiek od 8 do 2048
asociatívne prehľadavanie, hit rate
algoritmy nahradzovania
Pri prepínaní kontextov procesov sa TLB musia vyčistiť
Model stránkovania s TLB je na obr. 8.15.
Ochrana pamäte pri stránkovaní
pomocou bitov, ktoré sú pripojené ku každému rámcu, kontrolujú sa pri každom odkaze (čítanie, zápis)
bit platná/neplatná (valid/invalid) - obr.8.16 Viacúrovňové stránkovanie Viacúrovňové stránkovanie
súčasné systémy - veľmi veľký logický adresný priestor (od 232 po 264) –> extrémne veľká tabuľka stránok .
Napr. pre systém s 32 adresou a stránkou 4 KB
(212 byte-ov), tabuľka stránok - 1 000 000 položiek (232/212) –> pre tabuľku stránok 4 MB pamäte Viacúrovňové stránkovanie pokračovanie Logická adresa :
číslo stránky posuv v stránke
P1 P2 d
10 10 12
kde P1 - index do vonkajšej tabuľky stránok a
P2 - posuv v stránke vonkajšej tabuľky
Príklad: obr.8.17, obr.8.17
Invertovaná tabuľka stránok Tabuľka stránok nie pre každý proces, ale len jedna tabuľka stránok v systéme, ktorá má len jednu položku pre každý rámec fyzickej pamäte. Invertovaná tabuľka stránok pokračovanie Hashovanie na základe PID procesu a čísla jeho rámca pre urýchlenie prehľadavania
Indexy posledne použitých položiek môžu byť v TLB
Invertovaná tabuľka stránok je využitá v systémoch
IBM RISC 6000,
IBM RT a
Hewlett-Packard Spectrum Workstation
Problém
pri zdieľaní stránok – ako odvodiť rovnaký index v tabuľke z rôznych PID a císel rámcov? Zdieľanie stránok Ak kód je reentrantný, môže byť zdieľaný
Reentrantný kód
nemodifikuje sám seba, a tým sa počas vykonania nemení Ochrana pamäte pri stránkovaní Špeciálne bity (HW)
režim prístupu
read, write, execute
valid/invalid – pre zístenie či stránka patrí do adres
Vloženo: 28.05.2009
Velikost: 1,03 MB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2024 unium.cz