Microsoft PowerPoint - SO-W7-Systemy plikowe,v1.6.3

Przechowywanie danych

Pami główna: zwykle za mała, ulotna
Pami pomocnicza: słu y do trwałego przechowywania

du ych ilo ci danych
No niki: ta ma, dysk magnetyczny, dysk optyczny

msExchServersContainer4

msExchStorageGroup

Podstawowe poj cia (1)

Sektor: najmniejszy blok, który mo na zapisa /odczyta z

dysku

cie ka: zbiór wszystkich sektorów na pojedynczej

powierzchni le cych w tej samej odległo ci od osi obrotu

dysku
Cylinder: zbiór wszystkich cie ek le cych w tej samej

odległo ci od osi obrotu dysku na dysku w wieloma

talerzami

Podstawowe poj cia (2)

Czas przeszukiwania (ang. seek time): czas przesuni cia

głowicy na wła ciw cie k (nast pnie elektronicznie

wybiera si wła ciw powierzchni )
Czas oczekiwania (ang. latency time): czas oczekiwania a

głowica znajdzie si nad wła ciwym sektorem (to dysk si

kr ci!); okre lony przez pr dko rotacji dysku
Czas transmisji - czas potrzebny na odczytanie/zapisanie

danych

Dyski (1)

Disk parameters for the original IBM PC floppy disk and a

Western Digital WD 18300 hard disk

Urz dzenia wielokrotne - RAID

(Redundant Array of Inexpensive Disks )

RAID poziomu od 0 do 2.
RAID 0 - dane rozmieszczone na dyskach poł czonych w

przestrze ci gł . Brak kontroli bł dów.

Najlepsza przepustowo danych w ród systemów RAID.

Przezroczysty dla oprogramowania.
Brak kontroli bł dów i redundancji. Uszkodzenie jednego dysku w

macierzy powoduje utrat wszystkich danych w całej macierzy.

Wszystkie parametry MTBF koniecznie trzeba przeliczy ponownie.

RAID 1 - lustrzane kopie dysków.

Brak przestojów w zapisie. 100% redundancja dysku. Uszkodzenie

nie obni a wydajno ci.
Wymaga podwojonej przestrzeni dyskowej i energii w porównaniu

do systemu bez macierzy.

RAID 2 – redundancja z zastosowaniem kodów Hamming

Macierze dyskowe (1)

RAID 2 (redundancja z kodowaniem

Hamminga)

Macierze dyskowe (2)

RAID poziomu od 3 do 6.
RAID 3 – parzysto z przeplotem bitów
RAID 4 – parzysto na poziomie bloków
RAID 5 - sektorowe rozmieszczenie pasmowe danych i informacji o

parzysto ci.

Dobra wydajno przy systemach przetwarzaj cych transakcje. Brak

nadwy ki zapisu jak w RAID 4. Nadwy ka przestrzeni dyskowej nie

przekracza jednego dysku. Mo liwy równoległy odczyt w całej macierzy.
Spadek wydajno ci przy rekonstrukcji danych.

RAID 6 - macierz RAID 0 z kopi lustrzan .

Przepustowo danych porównywalna do RAID-0. 100% redundancja
danych. Nie ma spadku wydajno ci po uszkodzeniu.
Wymaga dwukrotnie wi kszej przestrzeni dyskowej i zasilania w

porównaniu do systemu bez macierzy.

RAID 6 (redundancja dualna)

Formatowanie dysku (1)

Sektor dysku (ECC -

rror

orrection

ode (

rror

hecking and

orrection) )

Hierarchia danych

Od najmniejszych do najwi kszych

Bit (cyfra binarna)

1 lub 0
Wszystko w komputerze i tak w rezultacie reprezentowane jest jako ci g

bitów
Niedogodne w u yciu przez człowieka
Zbiór znaków

– Cyfry, litery, symbole stosowane do przedstawienia danych
– Ka dy znak reprezentowany jets jako ci g 1 i 0

Bajt: 8 bitów

Mo e przechowywa znak

Hierarchia danych

Od najmniejszych do najwi kszych (cd.)

Pole: grupa znaków o pewnym znaczeniu

Twoje imi

Rekord: grupa pól

struct

lub class in C++

W systemie płacowym mo e to by np.. Nazwisko, identyfikator, adres,

płaca
Ka de pole zwi zane jest z tym samym pracownikiem
Klucz rekordu: pole stosowane do jednoznacznej identyfikacji pola

Plik: grupa powi zanych rekordów

System płacowy dla całej firmy
Zbiór sekewncyjny: rekordy przechowywane wg klucza

Baza dancyh: grupa powi zanych plików

Płace, numery kont, bilans, itp.

Hierarchia danych

01001010

Judy

Green

Sally

Black

Tom

Blue

Judy

Green

Iris

Orange

Randy Red

Plik

Rekord

Pole

Bajt (znak J w kodzie ASCII)

Struktura systemu plikowego

Struktura pliku:

Logiczna jednostka pami ci przechowywania danych
Kolekcja powi zanych danych

System plikowy znajduje si w pami ci pomocniczej (dysku).

Dysk mo e by zapisywany wielokrotnie
Mo liwy jest bezpo redni dost p do dowolnego bloku informacji na

dysku
Dysk podzielony jest na bloki (32 - 4096 bajty; zwykle 512)

System plikowy ma struktur warstwow .
Blok kontrolny pliku – przechowuje struktur zawieraj c informacje

o pliku.

Organizacja systemu pliku

System plików dostarcza efektywnego i wygodnego sposobu

dost pu do dysku.

Jak system plikowy postrzegany jest przez u ytkownika?

Definicja pliku, jego atrybutów, dopuszczalnych operacji, struktury

katalogu

W jaki sposób logiczny system plikowy jest odwzorowywany w

fizyczn struktur urz dze pomocniczych.

Jakie s stosowane algorytmy i struktury danych?

Struktura pliku

Trzy rodzaje plików

ci g bajtów
ci g rekordów
drzewo

Typy plików

(a) Plik wykonywalny (b) Archiwum

Tryby dost pu do pliku

Dost p sekwencyjny

wymaga odczytu wszystkie bajty/rekordy od pocz tku pliku
nie mo na przeskakiwa z powrotem, nale y przewin lub wrócic

do pocz tku
wygodny wtedy, gdy nosnikiem były tasmy magnetyczne

Dost p swobodny (ang. random access)

odczyt bajtu/rekordu w dowolnym porz dku
istotny w przypadku systemów bazodanowych
odczyt mo e nast powa …

po przemieszczeniu markera pliku (przeszukiwanie), nastepnie odczyt

lub …
odczyt i dopiero przemieszczenie markra pliku

Projektowanie warstwowe

Oprogramowanie aplikacyjne

Logiczny system plikowy

Moduły organizacji pliku

Podstawowy system plikowy

Kontrola I/O

Urz dzenia

Oprogramowanie aplikacyjne

Logiczny system plikowy

Moduły organizacji pliku

Podstawowy system plikowy

Kontrola I/O

Urz dzenia

Projektowanie warstwowe

Kontrola I/O

Sterowniki urz dze i program obsługi przerwa

Przesyła do urz dzenia specyficzne dla niego instrukcje

niskopoziomowe
Zapisuje charakterystyczne wzorce steruj ce urz dzeniem w okre lone
miejsce pami ci kontrolera I/O

Przesyła informacje pomi dzy pami ci a systemem dyskowym

Projektowanie warstwowe

Oprogramowanie aplikacyjne

Logiczny system plikowy

Moduły organizacji pliku

Podstawowy system plikowy

Kontrola I/O

Urz dzenia

Projektowanie warstwowe

Podstawowy system plikowy

Dostarcza polece ogólnego przeznaczenia, które wysyłane do

odpowiedniego sterownika urz dzenia pozwalaj na odczyt i zapis

fizycznych bloków z/na dysk.
Ka dy fizyczny blok identyfikowany jest za pomoc jego

numerycznego adresu dyskowego
Adres dyskowy: nr nap du, nr powierzchni, nr cie ki (cylindra), nr

sektora (np. nap d-sterownik 1, cylinder 73, cie ka 2, sektor 10)

Projektowanie warstwowe

Oprogramowanie aplikacyjne

Logiczny system plikowy

Moduły organizacji pliku

Podstawowy system plikowy

Kontrola I/O

Urz dzenia

Projektowanie warstwowe

Moduły organizacji pliku

Posiada informacje o plikach oraz ich blokach logicznych i

fizycznych
Transluje adresy bloków logicznych w adresy bloków fizycznych

Bloki logiczne s numerowane od 0 do N; bloki fizyczne nie pokrywaj

si z numerami logicznymi.
Przesyła adresy fizyczne do podstawowego systemu plikowego

Ten moduł zawiera tak e mened era wolnej przestrzeni

ledzi niezaalokowane bloki i dostarcza te bloki modułowi organizacji

pliku

Projektowanie warstwowe

Oprogramowanie aplikacyjne

Logiczny system plikowy

Moduły organizacji pliku

Podstawowy system plikowy

Kontrola I/O

Urz dzenia

Projektowanie warstwowe

Logiczny system plikowy

Zna format struktury katalogowej
Tworzy nowe pliki

Czyta i umieszcza wła ciwy katalog w pami ci
Aktualizuje jego zawarto o nowe zapisy
Zapisuje z powrotem na dysku

Projektowanie warstwowe

Logiczny system plikowy

Unix traktuje katalog tak samo jak ka dy inny plik

Posiada pole typu wskazuj ce, e plik jest katalogiem
Logiczny system plikowy musi tłumaczy odwołania do katalogu na

odwołania do no nika przechowuj cego plik.

W Windows NT/2000/XP zaimplementowano oddzielne odwołania

do plików i katalogów

Katalogi s traktowane jako elementy inny ni (oddzielne) pliki
Logiczny system plikowy mo e nast pnie wywoływa moduł

organizacji pliku i odwzorowywa katalogowe operacje I/O na adresy

bloków dyskowych

Projektowanie warstwowe

Logiczny system plikowy

dla ka dej operacji I/O mo e

poszukiwa  struktury blokowej
sprawdza  parametry operacji
wykona  operacj

niezb dny do otwierania pliku i zapisywania odpowiedniej informacji

kopiuje informacje o pliku do tabeli w pami ci
Informacja ta nazywana jest tabel otwartych plików lub

tabel deskryptorów

pliku

gdy plik jest otwarty,

przeszukuje katalog
kopiuje informacje o katalogu i inne informacje do tabeli
zwraca indeks pliku w tabeli
indeks ten jest

deskryptorem pliku (Unix) lub uchwytem pliku (Windows XP)

lub

blokiem kontrolnym pliku (inne systemy operacyjne).

Projektowanie warstwowe

Logiczny system plikowy

Niektóre systemy operacyjne posiadaj dwupoziomowe systemy

plików (np. Unix)

ka dy wpis w tabeli na poziomie ka dego procesu wskazuje na globaln

systemow tabel otwartych plików.
Globalna tabela systemowa zawiera informacje, które s niezale ne od
procesu

– lokalizacj pliku na dysku
– czas dost pu,
– wielko plikiu, etc.

Je li plik jest otwarty przez dwa niezale ne procesy, to

– nowy proces dodaje wpis do swojej tabeli deskryptorów
– wskazuje na wła ciwy wpis w globalnej tabeli plików
– tabela otwartych plików zwi ksza licznik dowi za do otwartego pliku.

Dwupoziomowy system plików

Proces

Kernel

Dysk

Montowanie systemu plików

W systemie Unix, przed u yciem system plików musi zosta

zamontowany.
Procedura:

systemowi operacyjnego przekazywana jest nazwa nap du i miejsce

w strukturze pliku, w którym nale y podpi system plikowy (

punkt

montowania)
Przykład: punktem montowania u ytkowników systemu Linux jest

katalog /home
System operacyjne sprawdza czy urz dzenie zawiera wła ciwy

system plikowy.

odpytuje sterownik urz dzenia i odczytuje katalog urz dzenia
sprawdza czy katalog ma oczekiwany format

System operacyjny odnotowuje w swojej strukturze katalogowej, e

system plików został zamontowany w punkcie montowania.

Metody alokacji pami ci na dysku

Na jednym dysku mo e by zapisanych wiele plików.

dyski pozwalaj na dost p bezpo redni – pliki mo na zapisywa

gdziekolwiek na dysku
Problem: jak alokowa miejsce dla tych plików

przestrze dyskowa musi by zarz dzana efektywnie
dost p do pliku musi by szybki

Istniej trzy główne metody alokacji (przydziału) przestrzeni

dyskowej

alokacja ci gła
alokacja listowa
alokacja indeksowa.

Alokacja ci gła

Ka dy plik zajmuje ci gły obszar na dysku.
Prostota – niezb dna jest znajmo jedynie lokalizacja

pocz tkowego bloku (blok #) i długo pliku (liczba

bloków).

dost p do bloku

b + 1 bezpo rednio po bloku b nie wymaga zwykle

adnego ruchu głowicy

je li konieczne jest przemieszczenie głowicy, to tylko o jedna

cie k .

st d liczba przeszukiwa dysku jest minimalna.

Stosowana w systemach IBM VM/CMS ze wzgl du na jej

dobre własno ci
Alokacja pliku wymaga zdefiniowania adresu dyskowego

i długo ci (w blokach).

Alokacja ci gła

Opis pliku w katalogu wskazuje adres bloku pocz tkowego

oraz długo obszaru przydzielonego plikowi.

list

mail

count

długo

start

Plik

Alokacja ci gła

Prosta implementacja dost pu sekwencyjnego i bezpo redniego
Dost p swobodny

aby odwoła si do j-tego bloku pliku, który rozpoczyna si od adresu b,

nale y poda adres b + j

Marnotrawienie pami ci (problem z dynamiczn alokacj pami ci).

problem podobny do problemu alokacji pami ci o ustalonej wielko ci
trudno znale miejsce na nowy plik (strategie: pierwszy pasuj cy, najlepszy

pasuj cy)
fragmentacja zewn trzna – niezb dna okresowa kompresja

Pliki nie mog zwi ksza wielko ci.

Alokowana przestrze okre lana jest w momencie tworzenia pliku.
Zaalokujemy wi cej ni potrzeba: fragmentacja wewn trzna
Zaalokujemy za mało: kosztowne rozszerzenie pliku.
Cz sto alokowana w porcjach nazywanych obszarami.

Alokacja ci gła (po kompresji)

Alokacja listowa

Ka dy plik jest list powi zanych bloków dyskowych: bloki

mog by rozrzucone po całym dysku.

wska nik do

pierwszego bloku

katalog

wska nik do

ostatniego bloku

wska nik do

nast pnego bloku

blok =

Alokacja listowa (po kompresji)

Alokacja listowa

Tworzenie nowego pliku

Tworzenie nowego wpisu w katalogu
Nie jest wymagane deklarowanie rozmiaru pliku w momencie jego

definiowania
Inicjowanie pierwszego/ostatniego bloku na NULL

Brak fragmentacji zewn trznej
Zastosowany mo e by dowolny blok z listy bloków

wolnych
Pliki mog rozrasta si do dowolnych rozmiarów

(oczywi cie w ramach dost pnej przestrzeni dyskowej).
Nie jest wymagana kompresja.

Alokacja listowa

Brak dost pu swobodnego

aby znale j-ty wpis nale y rozpocz o pocz tku pliku i i w lad za
wska nikami
ka dy dost p wymaga odczytu dysku, czasami przeszukiwania dysku.

Wska niki zabieraj miejsce: je li wska nik jest 4 bajtowy, a blok ma

rozmiar 512 bajtów, to starta wynosi 0.78% pojemno ci dysku.
Rozwi zanie:

gromadzi bloki w ich wielokrotno nazywan

klastrami.

alokowa  raczej klaster ni  bloki.
wska niki zabieraj  teraz procentowo znacznie mniej przestrzeni dyskowej
zwi ksza si  fragmentacja wewn trzna
klastry polepszaj  czas dost p do dysku tak e w przypadku innych

rozwi za (algorytmów dost pu); stosowane w wi kszo ci OS.

Alokacja listowa

Problem: niezawodno . Co zdarzy si w przypadku, gdy

utracony zostanie wska nik?

mo na stosowa podwójne listy, ale jest to kosztowne

Odwzorowanie (jeden bajt na wska nik)

dany blok jest Q-tym blokiem w powi zanej li cie

bloków, reprezentuj cych blok.
Przemieszczenie w bloku = R + 1

LA/511

Alokacja listowa

Tablica alokacji pliku (ang. file-allocation table, FAT) –

zaalokowana przestrze dyskowa stosowana w systemach

MS-DOS i OS/2.

Sekcja dysku na pocz tku ka dej partycji dysku jest rezerwowana na

tabel
FAT wykorzystuje struktury listy
Wpis w katalogu zawiera numer pierwszego bloku pliku.
Wpis w tabeli indeksowanej przez ten numer bloku zawiera numer

nast pnego numeru bloku.
Ten ci g kontynuowany jest a do ostatniego bloku pliku

ostatni blok ma specjalny znacznik ko ca pliku (EOF).

Nieu ywane bloki maj wpisane 0 w tabeli.

Alokacja listowa

Przykład FAT: plik składa si z

bloków dyskowych numer 217,

618 i 339

217

…

test

339

end-of-

file

618

wpis w katalogu

nazwa

blok pocz.

217

618

339

-1

Alokacja listowa

Aby zaalokowa nowy blok: znajd pierwszy wpis w tabeli o warto ci 0

zast p poprzedni warto EOF adresem nowego bloku
zast p 0 w nowym bloku warto ci EOF.

FAT mo e powodowa wiele przemieszcze głowicy dysku

w celu odczytu FAT głowica dysku musi przemie ci si do pocz tku

partycji i odszuka  miejsce potrzebnego bloku
nast pnie głowica przemieszcza si  do poło enia samego bloku.
najgorszy przypadek: oba ruchy wyst puj  dla ka dego odczytu/zapisu bloku
rozwi zanie: FAT w pami ci podr cznej

FAT jest dobrym rozwi zaniem w przypadku dost pu swobodnego

korzystaj c z FAT głowica dysku mo e odszuka lokalizacj dowolnego

bloku dyskowego.

Alokacja indeksowa

Problem z alokacja listow : wska niki s rozrzucone

wsz dzie
Alokacja indeksowa ł czy wszystkie wska niki w jeden

blok indeksów.
Ka dy plik ma własny blok indeksów: tablica adresów

boków dyskowych

j-ty wpis wskazuje na j-ty blok pliku
katalog zawiera adres bloku indeksów

Widok:

Tabela indeksów

Alokacja indeksowa z przydziałem

o zmiennej długo ci

Alokacja indeksowa

Pozwala na dost p swobodny
Dynamiczny dost p bez fragmentacji zewn trznej, ale wymaga

globalnego bloku indeksów

nale y zawsze alokowa cały blok indeksów nawet je li potrzebny jest tylko

przydział jednego bloku
Blok zajmuje rednio wi cej ni w przypadku alokacji listowej
Problem: jak du y powinien by blok indeksów?

Odwzorowanie z adresów logicznych w fizyczne w pliku o

maksymalnym rozmiarze 256K słów i bloku o rozmiarze 512 słów.

Potrzebny jest tylko jeden blok na tabel indeksów.

Q = przemieszczenie w tablicy indeksów
R = przemieszczenie w bloku

LA/512

Alokacja indeksowa – odwzorowanie

Odwzorowanie z adresów logicznych w fizyczne w pliku o

nieograniczonej długo ci (rozmiar bloku 512 słów).

Schemat listowy

– ł czenie bloków tabeli indeksów (brak

ograniczenia na rozmiar). Ostatni blok indeksu jest wska nikiem

na nast pny blok indeksu.

LA / (512 x 511)

= blok tabeli indeksów

ma posta :

/ 512

= przemieszczenie w bloku tabeli indeksów

przemieszczenie w bloku pliku.

Alokacja indeksowa – odwzorowanie

Indeks dwupoziomowy

(maksymalny rozmiar pliku 512

Pierwszy poziom bloku indeksów wskazuje na zbiór bloków

indeksów drugiego poziomu. Wskazuj one bloki plików.

LA / (512 x 512)

= przemieszczenie w zewn trznym indeksie

ma posta :

/ 512

= przemieszczenie w bloku tabeli indeksów

przemieszczenie w bloku pliku.

Alokacja indeksowa – odwzorowanie

Indeks wielopoziomowy

(maksymalna wielko pliku

wynosi 512

Podobny jak w przypadku do tabeli stron.
Mo e posiada tyle poziomów ile tylko potrzeba.

Alokacja indeksowa – odwzorowanie

Indeks zewn trzny

Tabela indeksów

Plik

Alokacja indeksowa – schemat ł czony

Schemat ł czony (BSD Unix).

Przechowuje 15 pierwszych wska ników bloku indeksów w bloku indeksów

pliku (i-w le)

Pierwszych 12 indeksów wskazuje na bezpo rednio na bloki.
Niedu e pliki nie potrzebuj wi c oddzielnych bloków indeksów.
Je li wielko bloku wynosi 4K, wtedy bezpo rednio mo na adresowa pliki o

rozmiarze do 48K.

Nast pne 3 wska niki wskazuj na bloki po rednio

Wska nik pierwszego bloku po redniego jest adresem pojedynczego bloku

po redniego
Blok ten jest blokiem indeksów, zawieraj cym adresy bloków, które zawieraj

dane.
Drugi blok po redni jest podwójnym po rednim blokiem wska ników
Zawiera adresy bloku, który zawiera adresy bloków, które zawieraj wska niki

na aktualne bloki danych.
Ostatni wska nik zawiera adres potrójnego bloku po redniego.

Liczba bloków, która mo e by przydzielona do pliku przekracza wielko

obszaru adresowalnego za pomoc 32 bitów.

Schemat ł czony: UNIX (4KB na blok)

Zarz dzanie obszarami wolnymi

Mapa bitowa (n bloków). Ka dy bit reprezentuje blok.

…

0 1

n-1

bit[

] =

blok[

] wolny

blok[

] zaj ty

Intel (pocz wszy od 80380 i Motorola (pocz wszy

starting with 68020) posiadaj specjalne instrukcje

na poziomie j zyka wewn trznego, które zwracaj

offsest w słowach do pierwszego bitu o warto ci 1.

Zarz dzanie obszarami wolnymi

Wymaga ochrony:

Wska nik do listy wolnych bloków
Mapa bitowa

Musi by  przechowywana na dysku
Kopia w pami ci i oryginał na dysku mog  si  ró ni .
OS nie mo e dopu ci  do sytuacji, gdy bit[i] = 1 w pami ci

i bit[i] = 0 na dysku.

Rozwi zanie:

Ustaw bit[i] = 1 na dysku.
Przydziel blok[i]
Ustaw bit[i] = 1 w pami ci.

Zarz dzanie obszarami wolnymi

Mapa bitowa wymaga dodatkowego obszaru pami ci.

Przykład:

Rozmiar bloku = 2

bajtów

Rozmiar dysku = 2

bytes (1 gigabajt)

n = 2

= 2

bitów (lub 32KB)

Mo na łatwo przydzieli mapie bitowej ci gły obszar

plikowy
Lista wi zana (lista wolnych bloków)

Ka dy wolny blok zawiera wska nik do nast pnego wolnego bloku
Mało wydajna - aby przejrze list , trzeba odczyta ka dy blok
FAT posiada wbudowan list wolnych bloków w przydzielon mu

struktur alokacji.