System plików
Short Description
Download System plików...
Description
System plików warstwa logiczna - warstwa fizyczna przykłady implementacji -
-
Systemy operacyjne
Wykład 6
1
System plików — warstwa logiczna • • • •
Pojęcie pliku. Typy i struktury plików. Metody dostępu do plików. Interfejs dostępu do plików w systemach uniksopodobnych. • Organizacja logiczna systemu plików: – strefy, – katalogi. • Logiczna struktura katalogów.
Systemy operacyjne
Wykład 6
2/94
Pojęcie pliku • Plik jest abstrakcyjnym obrazem informacji gromadzonej i udostępnianej przez system komputerowy. • Plik jest podstawową jednostką logiczną magazynowania informacji w systemie komputerowym, widoczną dla użytkownika. • Plik jest nazwanym zbiorem powiązanych ze sobą informacji, zapisanym w pamięci pomocniczej.
Systemy operacyjne
Wykład 6
3/94
Zadania systemu operacyjnego • Zadaniem systemu operacyjnego w odniesieniu do plików jest zapewnienie odwzorowania pomiędzy abstrakcyjnym obrazem informacji a jego reprezentacją na urządzeniu fizycznym. • Wyszczególnienie zadań: – identyfikacja pliku (hierarchiczna struktura katalogów), – udostępnienie interfejsu operacji plikowych (API), – realizacja operacji dostępu do plików i katalogów z zapewnieniem bezpieczeństwa (synchronizacja i autoryzacja dostępu), spójności i efektywności. Systemy operacyjne
Wykład 6
4/94
Atrybuty pliku • Nazwa — ciąg znaków służących użytkownikowi do identyfikacji pliku. • Typ — informacja służąca do rozpoznania rodzaju zawartości pliku i tym samym sposobu interpretacji. • Lokalizacja — informacja służąca do odnalezienia pliku w systemie komputerowym (urządzenie i położenie pliku w tym urządzeniu). • Rozmiar — bieżący rozmiar pliku w ustalonych jednostkach (bajtach, słowach, blokach itp.). • Ochrona — informacje umożliwiające kontrolę dostępu. • Czasy dostępów — daty i czasy wykonywania pewnych operacji na pliku, typu odczyt, modyfikacja, utworzenie. Systemy operacyjne
Wykład 6
5/94
Typy plików • Typ pliku określa rodzaj informacji przechowywanej w pliku i tym samym sposób interpretacji jego zawartości, np. program binarny, wynik kompilacji, kod źródłowy, makrodefinicja (plik wsadowy, skrypt powłoki itp.), tekst, biblioteka programisty, grafika, dane aplikacji. • Informacja o typie pliku może być przechowywana w strukturach wewnętrznych systemu plików, w zawartości samego pliku, w katalogach lub w nazwie pliku. • Typ pliku może być rozpoznawany przez system operacyjny, ale może to być również tylko informacja interpretowana przez użytkownika lub aplikację. Systemy operacyjne
Wykład 6
6/94
Struktura pliku • Struktura logiczna: – określa organizację informacji wewnątrz pliku, – może być definiowana i rozpoznawana na poziomie jądra systemu operacyjnego lub na poziomie aplikacji. • Struktura fizyczna: – określa sposób przechowywania informacji, – narzucana jest przez urządzanie, na którym plik jest składowany.
Systemy operacyjne
Wykład 6
7/94
Odwzorowanie obrazu logicznego w fizyczny nośnik fizyczny (dysk)
plik rekord logiczny
Systemy operacyjne
rekord logiczny
Wykład 6
rekord logiczny
obszar niewykorzystany 8/94
Metody dostępu do plików • Metody dostępu określają sposób identyfikacji odczytywanego lub zapisywanego fragmentu pliku. • Użycie określonej metody wynika z charakteru przetwarzania oraz struktury pliku. • Dostępność określonej metody może być ograniczona ze względu na własności urządzenia oraz sposób organizacji lub implementacji systemu plików (zwłaszcza atrybutu lokalizacja). Systemy operacyjne
Wykład 6
9/94
Wyszczególnienie metod dostępu • Dostęp sekwencyjny (sequential access) — informacje w pliku przetwarzane są rekord po rekordzie, tzn. po wykonaniu operacji na określonym rekordzie system przygotowuje się do wykonania operacji na kolejnym rekordzie w pliku. • Dostęp bezpośredni (swobodny, direct access) — lokalizacja rekordu do przetwarzania podawana jest jako parametr odpowiedniej operacji. • Dostęp indeksowy — rekord, na którym ma być wykonana operacja identyfikowany jest przez klucz, odwzorowywany na konkretny rekord w pliku stowarzyszonym poprzez plik indeksowy. Systemy operacyjne
Wykład 6
10/94
Przykład pliku indeksowego klucz Iksiński
Igrekowska Maria, mgr
Igrekowska
Zetowski Jerzy, dr
• • •
• • •
Zetowski
Iksiński Wojciech, prof.
plik indeksowy Systemy operacyjne
plik stowarzyszony Wykład 6
11/94
Podstawowe operacje na plikach • Tworzenie pliku — konieczne jest określenie podstawowych atrybutów pliku, znalezienie miejsca na ten plik w systemie komputerowym oraz jego zaewidencjonowanie (utworzenie wpisu katalogowego). • Zapis do pliku — konieczne jest określenie, co ma być zapisane i gdzie ma być zapisane (w którym pliku i w jakim miejscu tego pliku, zależnie od sposobu dostępu). • Odczyt z pliku — konieczne jest określenie, co ma być odczytane (z którego pliku i z jakiego miejsca tego pliku, zależnie od sposobu dostępu) i gdzie mają być umieszczone odczytane dane. • Usuwanie informacji z pliku — należy określić jaki fragment pliku (i którego pliku) ma być usunięty. Najczęściej możliwe jest tylko skracanie pliku, czyli usuwanie jego końcowej zawartości lub całej jego zawartości. • Usuwanie pliku — należy określić plik do usunięcia. Usuwana jest zawartość oraz wpis ewidencyjny pliku. • Dodatkowe operacje na plikach, wykonywane w celu uzyskania dostępu do zawartości pliku: – otwieranie, – zamykanie, – przesuwanie wskaźnika bieżącej pozycji. Systemy operacyjne
Wykład 6
12/94
Interfejs dostępu do pliku w systemach UNIX i podobnych • • • • •
Tworzenie pliku — funkcja creat. Usuwanie dowiązania do pliku — funkcja unlink. Odczyt z pliku — funkcja read. Zapis do pliku — funkcja write. Skracanie pliku (usuwanie końcowej zawartości, obcinanie) — funkcja truncate. • Przesunięcie wskaźnika bieżącej pozycji — funkcja lseek. • Otwieranie pliku — funkcja open. • Zamykanie otwartego pliku — funkcja close. Systemy operacyjne
Wykład 6
13/94
Systemy uniksopodobne — tworzenie pliku • Funkcja systemowa: creat. • Parametry: – nazwa pliku (ścieżka), – prawa dostępu. • Wartość zwrotna: deskryptor pliku lub -1 w przypadku błędu. • Uwaga: funkcja tworzy plik i otwiera go do zapisu.
Systemy operacyjne
Wykład 6
14/94
Systemy uniksopodobne — otwieranie pliku • Funkcja systemowa: open. • Parametry: – nazwa pliku (ścieżka), – tryb otwarcia (do zapisu, do odczytu itp.). • Wartość zwrotna: deskryptor pliku lub -1 w przypadku błędu. • Wersja 3-argumentowa funkcji umożliwia również tworzenie pliku.
Systemy operacyjne
Wykład 6
15/94
Systemy uniksopodobne — zamykanie deskryptora pliku • Funkcja systemowa: close. • Parametry: – deskryptor. • Wartość zwrotna: 0 w przypadku poprawnego zakończenia lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
16/94
Systemy uniksopodobne — usuwanie dowiązania do pliku • Funkcja systemowa: unlink. • Parametry: – nazwa pliku (ścieżka). • Wartość zwrotna: 0 w przypadku poprawnego zakończenia lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
17/94
Systemy uniksopodobne — skracanie pliku • Funkcja systemowa: truncate. • Parametry: – nazwa pliku (ścieżka) lub deskryptor. – wielkość w bajtach do jakiej ma nastąpić skrócenie (docelowa wielkość pliku). • Wartość zwrotna: 0 w przypadku poprawnego zakończenia lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
18/94
Systemy uniksopodobne — odczyt zawartości pliku • Funkcja systemowa: read. • Parametry: – deskryptor pliku, – adres w pamięci, pod którym zostaną zapisane dane odczytane z pliku, – liczba odczytywanych bajtów. • Wartość zwrotna: liczba rzeczywiście odczytanych bajtów lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
19/94
Systemy uniksopodobne — zapis zawartości pliku • Funkcja systemowa: write. • Parametry: – deskryptor pliku, – adres w pamięci, spod którego zostaną pobrane dane do zapisu, – liczba zapisywanych bajtów. • Wartość zwrotna: liczba rzeczywiście zapisanych bajtów lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
20/94
Przykład realizacji operacji odczytu w systemach uniksopodobnych read(d, buf, 8)
read(d, buf, 11)
read(d, buf, 6) bufor w pamięci Systemy operacyjne
plik Wykład 6
21/94
Przykład realizacji operacji zapisu w systemach uniksopodobnych write(d, buf, 8)
write(d, buf, 11)
write(d, buf, 6) bufor w pamięci Systemy operacyjne
plik Wykład 6
22/94
Systemy uniksopodobne — zmiana wskazania bieżącej pozycji • Funkcja systemowa: lseek. • Parametry: – deskryptor pliku, – wielkość przesunięcia w bajtach, – punkt odniesienia (początek pliku, bieżąca pozycja, lub koniec pliku). • Wartość zwrotna: położenie wskaźnika po przesunięciu lub -1 w przypadku błędu.
Systemy operacyjne
Wykład 6
23/94
Zmiana wskazania bieżącej pozycji - odczyt read(d, buf, 8)
lseek(d, 11, SEEK_CUR)
read(d, buf, 6) bufor w pamięci Systemy operacyjne
plik Wykład 6
24/94
Zmiana wskazania bieżącej pozycji - zapis write(d, buf, 8)
lseek(d, 11, SEEK_CUR)
write(d, buf, 6) bufor w pamięci Systemy operacyjne
plik Wykład 6
25/94
Organizacja logiczna systemu plików
• Podział na strefy (wolumeny, woluminy, tomy, partycje): – strefa obejmuje część dysku, jeden lub kilka dysków, – strefa zawiera pliki i katalogi. • Organizacja katalogów: – katalog jest tablicą kojarzącą nazwy plików z wpisami katalogowymi, obejmującymi inne atrybuty plików, – katalogi mogą być jedno- lub wielopoziomowe, – katalogi wielopoziomowe zorganizowane mogą być w różne struktury logiczne (drzewo, graf acykliczny, dowolny graf). • Pliki identyfikowane są przez nazwy, znajdujące się w katalogach. Systemy operacyjne
Wykład 6
26/94
Organizacja logiczna systemu plików – ilustracja
katalog
katalog
katalog
plik
plik
plik
strefa/partycja/wolumen plik
plik
plik
strefa/partycja/wolumen Systemy operacyjne
Wykład 6
27/94
katalog urządzenia dysk 1
katalog urządzenia
Systemy operacyjne
pliki dysk 2
strefa B
katalog urządzenia
strefa
pliki dysk
strefa A
Podział na strefy
pliki
Wykład 6
28/94
Operacje na katalogu • Tworzenie katalogu. • Usuwanie katalogu. • Tworzenie wpisu katalogowego — gdy tworzony jest plik, jego nazwa alternatywna, podkatalog itp. • Usuwanie wpisu katalogowego. • Przemianowanie pliku (zmiana nazwy). • Odnajdowanie wpisu katalogowego. • Tworzenie wykazu wpisów katalogowych (listing zawartości). Systemy operacyjne
Wykład 6
29/94
Struktura logiczna katalogów • Struktura jednopoziomowa — wpisy katalogowe poszczególnych plików znajdują się w tym samym katalogu (na tym samym poziomie). • Struktura dwupoziomowa — wpisy katalogowe plików znajdują się w różnych katalogach, ale katalogi nie mogą zawierać innych katalogów. • Struktura drzewiasta — w katalogach można tworzyć podkatalogi oraz pliki. • Graf acykliczny — podkatalog (lub plik) może być umieszczony w wielu katalogach. • Graf ogólny — dopuszcza się cykl w powiązaniach pomiędzy katalogami Systemy operacyjne
Wykład 6
30/94
Struktura jednopoziomowa
prg.c
Systemy operacyjne
test.txt
f.lst
Wykład 6
sample.h
31/94
Struktura dwupoziomowa jacek
prg.c
Systemy operacyjne
anna
test.txt
prg.c
Wykład 6
sample.h
32/94
Struktura drzewiasta jacek
programy
prg.c
prog.c
Systemy operacyjne
anna
teksty
programy
abc.doc
Wykład 6
prg.c
s.txt
sample.h
33/94
Graf acykliczny jacek
teksty
plik.txt
Systemy operacyjne
anna
jacek
prg1.c
prg.c
Wykład 6
readme
sample.h
34/94
Graf ogólny teksty
pisma
plik.txt
Systemy operacyjne
poczta
list2.txt
s.doc
list1.txt
Wykład 6
35/94
System plików – warstwa fizyczna
• • • • • •
Przydział miejsca na dysku Zarządzanie wolną przestrzenią Implementacja katalogu Przechowywanie podręczne Integralność systemu plików Semantyka spójności
Systemy operacyjne
Wykład 6
36/94
Organizacja fizyczna systemu plików • Przydział miejsca na dysku: – przydział ciągły, przydział listowy, przydział indeksowy, • Zarządzanie wolną przestrzenią: – wektor bitowy, lista powiązana, grupowanie, zliczanie. • Implementacja katalogu: – lista liniowa, tablica haszowa, struktura indeksowa.
Systemy operacyjne
Wykład 6
37/94
Przydział miejsca na dysku • Przydział ciągły (contiguous allocation) — cały plik zajmuje ciąg kolejnych bloków. • Przydział listowy (łańcuchowy, linked allocation, chained allocation) — bloki pliku tworzą listę powiązaną. • Przydział indeksowy (indexed allocation) — bloki z danymi wskazywane są przez bloki indeksowe, które mogą być zorganizowane w: – schemat listowy, – schemat wielopoziomowy, – schemat kombinowany. Systemy operacyjne
Wykład 6
38/94
Przydział ciągły
Katalog: 1
7
8
14
15
21
22
28
29
35
Systemy operacyjne
blok początkowy: 1 rozmiar: 10 bloków blok początkowy: 13 rozmiar: 11 bloków blok początkowy: 27 rozmiar: 9 bloków
Wykład 6
39/94
Przydział ciągły — właściwości • Efektywność dostępu (niewielkie ruchy głowic dysk.). • Łatwa lokalizacja bloków pliku zarówno przy dostępie sekwencyjnym jak i bezpośrednim. • Problem fragmentacji zewnętrznej — po usuniętych plikach pozostają dziury, które trudno połączyć w jeden większy blok. • Problem rozszerzania pliku: – pliku nie da się rozszerzyć, – będzie go trzeba przenieść w nowe miejsce (znaleźć większą dziurę), – będzie trzeba z góry zarezerwować więcej miejsca w przestrzeni dyskowej. Systemy operacyjne
Wykład 6
40/94
Przydział listowy (łańcuchowy)
Katalog: 1
7
8
14
15
21
22
28
29
35
Systemy operacyjne
blok początkowy: 1 blok końcowy: 8 blok początkowy: 22 blok końcowy: 14 blok początkowy: 7 blok końcowy: 4
Wykład 6
41/94
Przydział listowy — właściwości • • • •
Nie ma problemu fragmentacji zewnętrznej. Łatwa realizacja dostępu sekwencyjnego. Problem realizacji dostępu bezpośredniego. Konieczność pamiętania wewnątrz bloku wskaźnika do bloku następnego. • Zawodność — utrata jednego bloku pociąga za sobą stratę wszystkich następnych.
Systemy operacyjne
Wykład 6
42/94
Tablica alokacji plików — FAT (File Allocation Table) • FAT jest dodatkową strukturą (tablicą) umieszczoną w odpowiednim obszarze na dysku. • Każdy element tablicy FAT odpowiada dokładnie jednej jednostce alokacji (blokowi) z przestrzeni bloków plikowych i indeksowany jest numerem bloku. • Element tablicy FAT zawiera indeks następnego bloku przydzielonego danemu plikowi lub pewną wartość specjalną oznaczającą wolną pozycję lub ostatnią pozycję danego pliku. Systemy operacyjne
Wykład 6
43/94
Struktura tablicy alokacji plików 1 2
3
3 28 4 # 5 6
1
7
8
14
15
21
7 35 8 #
22
28
…
29
35
Systemy operacyjne
27
8 28 27
Wykład 6
Katalog: blok początkowy: 1 blok końcowy: 8 blok początkowy: 22 blok końcowy: 14 blok początkowy: 7 blok końcowy: 4
44/94
Przydział indeksowy
Katalog: 1
7
8
14
15
21
22
28
29
35
Systemy operacyjne
blok indeksowy: 4 rozmiar: 4 bloki blok początkowy: 23 rozmiar: 3 bloki blok początkowy: 7 rozmiar: 4 bloki
Wykład 6
45/94
Struktura bloku indeksowego • Schemat listowy — w ostatnim elemencie bloku indeksowego znajduje się wskaźnik do następnego bloku indeksowego tego pliku. • Schemat wielopoziomowy — blok indeksowy pierwszego poziomu zawiera wskaźnik do bloków drugiego poziomu itd. • Schemat kombinowany — zastosowanie do pewnej liczby bloków indeksu pierwszego poziomu, dla następnych bloków indeksu dwupoziomowego itp. Systemy operacyjne
Wykład 6
46/94
Struktura bloku indeksowego — schemat listowy …
…
Systemy operacyjne
…
…
blok danych
Wykład 6
…
blok indeksowy
47/94
Struktura bloku indeksowego — indeks wielopoziomowy
…
…
…
blok danych blok indeksowy
…
…
Systemy operacyjne
Wykład 6
48/94
Struktura bloku indeksowego — schemat kombinowany …
…
…
… …
blok danych blok indeksowy
…
…
Systemy operacyjne
Wykład 6
49/94
Przydział indeksowy — właściwości
• Stosunkowo szybka lokalizacja dowolnego bloku pliku. • Łatwa realizacja dostępu bezpośredniego. • Brak problemu fragmentacji zewnętrznej. • Konieczność przeznaczenie pewnej części przestrzeni dyskowej na bloki indeksowe. • Zawodność: utrata bloku indeksowego oznacza utratę sporej części pliku lub nawet całej zawartości. Systemy operacyjne
Wykład 6
50/94
Zarządzanie wolną przestrzenią • Wektor bitowy — każdy bit odpowiada jednemu blokowi, wartość 1 oznacza wolny blok. • Lista powiązana — każdy wolny blok zawiera indeks następnego wolnego bloku. • Grupowanie — niektóre wolne bloki zapełnione są w całości indeksami innych wolnych bloków, ostatni indeks wskazuje na kolejny blok zapełniony w całości indeksami. • Zliczanie — wykaz wolnych bloków obejmuje indeks pierwszego wolnego bloku oraz liczbę wolnych bloków znajdujących się za nim, stanowiących ciągły obszar. Systemy operacyjne
Wykład 6
51/94
Zarządzanie wolną przestrzenią — wektor bitowy wektor bitowy w superbloku 00100000001100001010001111000111100
Systemy operacyjne
1
7
8
14
15
21
22
28
29
35
Wykład 6
52/94
Zarządzanie wolną przestrzenią — lista powiązana indeks pierwszego wolnego bloku
Systemy operacyjne
1
7
8
14
15
21
22
28
29
35
Wykład 6
53/94
Zarządzanie wolną przestrzenią — grupowanie indeks bloku pierwszej grupy wolnych bloków 11 12 17
Systemy operacyjne
1
7
8
14
15
21
22
28
29
35
Wykład 6
19 23 24 25 30 31
54/94
Zarządzanie wolną przestrzenią — zliczanie Wykaz wolnych obszarów:
3, 11 12, 17 19, 23 24, 25 26, 30 31, 32 33
Systemy operacyjne
1
7
8
14
15
21
22
28
29
35
Wykład 6
55/94
Implementacja katalogu — lista liniowa • Katalog składa się z ciągu wpisów katalogowych ogólnej postaci: nazwa pliku
inne atrybuty
• Lokalizacja wpisu polega na przeszukiwaniu liniowym (sprawdzane są kolejne pozycje, począwszy od pierwszej). • Lokalizacją wpisu można przyspieszyć poprzez posortowanie wg. nazwy, jednak utrzymanie takiej struktury jest kosztowne.
Systemy operacyjne
Wykład 6
56/94
Implementacja katalogu — tablica haszowa • Wpisy ułożone są na pozycjach odpowiadających wartościom funkcji haszującej. • Funkcja haszująca odwzorowuje nazwę pliku na wartość z określonego przedziału, traktowaną jako indeks wpisu. • Ta sama funkcja haszująca wykorzystywana jest do lokalizacji wpisu. • W katalogu mogą być potrzebne dodatkowe struktury pomocne przy usuwaniu konfliktów.
Systemy operacyjne
Wykład 6
57/94
Implementacja katalogu — struktura indeksowa • Wpisy katalogowe powiązane są w strukturę drzewiastą przyspieszającą wyszukiwanie (np. drzewo binarne, B–drzewo, B±drzewo). • Lokalizacja wpisu polega na przejściu drzewa zgodnie z zasadami jego budowy. • Struktura drzewa jest zoptymalizowana w taki sposób, żeby minimalizować liczbę operacji dyskowych podczas przeszukiwania.
Systemy operacyjne
Wykład 6
58/94
Przechowywanie podręczne w systemie plików Logiczny system plików Organizacja fizyczna systemu plików
Bufor pamięci podręcznej Moduł sterujący
Systemy operacyjne
Wykład 6
59/94
Zasady przechowywania podręcznego • Zawartość aktualnie wykorzystywanych bloków dyskowych utrzymywana jest w podręcznej pamięci buforowej. • Obsługa żądania odczytu bloku polega najpierw na sprawdzeniu czy dany blok znajduje się w podręcznej pamięci buforowej, a później ewentualnie sprowadzenia z dysku. • Żądany fragment kopiowany jest z podręcznej pamięci buforowej w odpowiednie miejsce w przestrzeni adresowej procesu. • Obsługa żądania zapisu oznacza transfer danych do podręcznej pamięci buforowej. Systemy operacyjne
Wykład 6
60/94
Przechowywanie podręczne w realizacji operacji odczytu 1. Znajdź adres bloku dyskowego, zawierającego fragment pliku, którego odczytu zażądano. 2. Przekopiuj zawartość tego bloku do bufora w pamięci podręcznej systemu plików (jeśli ten blok się tam jeszcze nie znajduje). 3. Przekopiuj żądany fragment z bufora do przestrzeni adresowej procesu.
Systemy operacyjne
Wykład 6
61/94
Przechowywanie podręczne w realizacji operacji zapisu 1. Znajdź adres bloku dyskowego, zawierającego fragment pliku, którego zapisu zażądano. 2. Przekopiuj zawartość tego bloku do bufora w pamięci podręcznej systemu plików (jeśli ten blok się tam jeszcze nie znajduje). 3. Przekopiuj żądany fragment z przestrzeni adresowej procesu do bufora. 4. Zapisz na dysk uaktualniony blok z bufora (albo w trybie natychmiastowym albo z opóźnieniem). Systemy operacyjne
Wykład 6
62/94
Integralność systemu plików • W wyniku awarii systemu zawartość podręcznej pamięci buforowej może nie zostać zapisana na dysku lub może zostać zapisana tylko częściowo. • Skutkiem w/w awarii może być pozostawienie systemu plików w stanie niespójnym. • Większość systemów operacyjnych dostarcza odpowiednie narzędzie do sprawdzania integralności systemu plików, uruchamiane w ramach restartu systemu po awarii.
Systemy operacyjne
Wykład 6
63/94
Przejawy braku integralności systemu plików • Brak bloku zarówno w wykazie bloków zaalokowanych jak i bloków wolnych. • Obecność bloku zarówno w wykazie bloków zaalokowanych jak i bloków wolnych. • Wielokrotne powtórzenie się bloku w wykazie bloków wolnych (duplikacja wolnego bloku). • Wielokrotne powtórzenie się bloku w wykazie bloków zaalokowanych (duplikacja zaalokowanego bloku). • Niespójność informacji we wpisach katalogowych (np. niezgodność licznika dowiązań w systemie UNIX). Systemy operacyjne
Wykład 6
64/94
Semantyka spójności • Semantyka spójności określa sposób postrzegania zmian zawartości pliku, dokonywanych przez współbieżnie działające procesy. • Przykłady semantyki spójności: – semantyka spójności systemu UNIX — wynik operacji zapisu jest natychmiast widoczny dla innych procesów, – semantyka sesji — zmiany w pliku stają się widoczne tylko dla procesów, otwierających ten plik po zamknięciu sesji, w której był zapis, – semantyka stałych plików dzielonych — współdzielony plik może być tylko czytany. Systemy operacyjne
Wykład 6
65/94
Synchronizacja dostępu do plików • Współbieżny dostęp do zawartości pliku można synchronizować na poziomie całego pliku lub poszczególnych jego fragmentów (zajmowanie rekordów). • Najczęściej dopuszcza się dwa rodzaje blokad: – blokada współdzielona (shared lock, read lock), – blokada wyłączna (exclusive lock, write lock). Systemy operacyjne
Wykład 6
66/94
Synchronizacja dostępu do plików — zgodność blokad
współdziel. wyłączona
Systemy operacyjne
współdziel.
wyłączona
zgodne
wykluczone
wykluczone wykluczone
Wykład 6
67/94
System plików – przykłady implementacji
• • • •
Systemy operacyjne
MS DOS ISO 9660 UNIX NTFS
Wykład 6
68/94
Przykłady implementacji systemu plików • DOS — wpis katalogowy zawiera indeks pierwszej jednostki alokacji, a pozostałe jednostki wynikają z tablicy FAT. • ISO 9660 (CD ROM) — bloki zorganizowane są wg. zasady przydziału ciągłego, wpis katalogowy zawiera indeks pierwszej jednostki alokacji oraz rozmiar pliku, wpisy katalogowe są posortowane alfabetycznie. • UNIX — plik opisany jest przez i-węzeł, wpis katalogowy zawiera indeks i-węzła, który z kolei zawiera indeks (kombinowany) jednostek alokacji. • NTFS — plik identyfikowany jest przez referencję, która jest indeksem rekordu w tablicy MFT, rekord zawiera atrybuty pliku (w szczególności dane) lub odnośniki do bloków z atrybutami. Systemy operacyjne
Wykład 6
69/94
MS DOS — informacje ogólne • Katalog zawiera 32-bajtowe wpisy, obejmujące podstawowe atrybuty pliku (nazwa, typ, rozmiar itp.). • Katalogi tworzą strukturę wielopoziomową. • Dane znajdują się w blokach (jednostkach alokacji) o ustalonym rozmiarze. • Bloki identyfikowane są z pośrednictwem tablicy FAT, a indeks pierwszego bloku znajduje się we wpisie katalogowym. • Wolne bloki identyfikowane są poprzez specjalny kod, wpisany na odpowiadających im pozycjach w tablicy FAT. Systemy operacyjne
Wykład 6
70/94
MS DOS — format partycji blok nadrzędny
tablica FAT kopia tablicy FAT katalog główny
bloki danych i podkatalogów
Systemy operacyjne
Wykład 6
71/94
MS DOS — struktura wpisu katalogowego
nazwa pliku (8 bajtów)
typ (3 bajty) flagi (1 bajt)
czas data ostatniego zapisu (4 bajty)
numer pierwszego bloku (2 bajty)
FAT 12 FAT 16 Systemy operacyjne
rozmiar w bajtach (4 bajty)
Wykład 6
72/94
MS Windows 98 — struktura wpisu katalogowego nazwa pliku (8 bajtów)
typ (3 bajty) czas data utworzenia pliku (4 bajty) flagi (1 bajt)
FAT 32
Systemy operacyjne
data ostatniego dostępu
Wykład 6
czas data ostatniego zapisu (4 bajty) bardziej znaczące 16 bitów numeru pierwszego bloku (2 bajty)
rozmiar w bajtach (4 bajty)
mniej znaczące 16 bitów numeru pierwszego bloku (2 bajty) 73/94
ISO 9660 — informacje ogólne • Dane na płycie CD nie są rozkładane w cylindrach, lecz tworzą układ spiralny. • Spirala dzielona jest na bloki logiczne (sektory) o rozmiarze 2352 bajtów (w tym preambuły, kody korekcyjne itp.), z czego na dane pozostaje 2048 bajtów. • Binarne pola numeryczne są reprezentowane podwójnie: zgodnie z uporządkowaniem grubokońcówkowym oraz cienkokońcówkowym. • Maksymalny poziom zagnieżdżeń katalogów — 8. Systemy operacyjne
Wykład 6
74/94
ISO 9660 — format partycji 16 bloków do dowolnego wykorzystania deskryptor głównego wolumenu wpis katalogowy korzenia drzewa katalogów
bloki danych i katalogów
Systemy operacyjne
Wykład 6
75/94
ISO 9660 — struktura wpisu katalogowego
lokalizacja pierwszego bloku (8 bajtów)
rozmiar (8 bajtów)
data i czas (7 bajtów)
flagi (1 bajt)
wielkość rozszerzenia atrybutów (1 bajt) wielkość wpisu katalogowego w bajtach (1 bajt)
Systemy operacyjne
nr CD z nazwa lokalizacją (4 – 15 (4 bajty) bajtów)
długość nazwy (1 bajt) rozszerzenia
Wykład 6
76/94
UNIX — informacje ogólne • Z każdym plikiem związany jest i-węzeł, który przechowuje wszystkie atrybuty pliku z wyjątkiem nazwy. • Nazwa znajduje się w katalogu obok numeru i-węzła danego pliku. • Katalogi tworzą strukturę wielopoziomową (katalog zawiera wpis specyfikujący inny katalog). • Dane (zawartość pliku) znajdują się w blokach (jednostkach alokacji) o ustalonym rozmiarze. • Bloki danych identyfikowane są za pośrednictwem indeksu kombinowanego. • Wolne bloki zorganizowane są zgodnie z zasadą grupowania. Systemy operacyjne
Wykład 6
77/94
UNIX — format partycji blok nadrzędny tablica i-węzłów
bloki danych
Systemy operacyjne
Wykład 6
78/94
…
…
Atrybuty: id właściciela i grupy typ pliku prawa dostępu czasy dostępu licznik dowiązań rozmiar w bajtach
…
UNIX — fizyczna struktura pliku
… … … Systemy operacyjne
Wykład 6
… 79/94
UNIX — struktura wpisu katalogowego
nazwa pliku (14 bajtów)
numer i-wezła (2 bajty)
Systemy operacyjne
Wykład 6
80/94
NTFS — informacje ogólne • Plik jest zbiorem atrybutów, obejmującym w szczególności atrybut dane. • Każdy plik ma swój wpis (rekord) w głównej tablicy plików (MFT), a indeks w tej tablicy jest składnikiem identyfikatora wewnętrznego (referencji pliku). • Tablica MFT sama jest plikiem, podobnie jak każdy inny obiekt w obrębie systemu plików. • Wolne bloki identyfikowane są przez wektor bitowy, przechowywany w jednym z plików.
Systemy operacyjne
Wykład 6
81/94
NTFS — format partycji blok nadrzędny MFT strefa MFT bloki danych kopia 16 pierwszych rekordów MFT bloki danych
Systemy operacyjne
Wykład 6
82/94
NTFS — struktura rekordu MFT • Rekord MFT ma ustalony rozmiar 1KB – 4KB. • Rekord MFT składa się z nagłówka rekordu i tabeli atrybutów. • Atrybut składa się z nagłówka atrybutu oraz wartości. • Wartość znajduje się albo nagłówek bezpośrednio w rekordzie rekordu MFT MFT (atrybut rezydentny), nagłówek wartość atrybutu atrybutu albo w bloku danych. wartość atrybutu
…
nagłówek atrybutu
Systemy operacyjne
Wykład 6
83/94
NTFS — zawartość nagłówka rekordu • Magiczna liczba — wartość używana do sprawdzania poprawności. • Numer sekwencyjny — wartość zwiększana o 1 za każdym razem, gdy rekord używany jest dla nowego pliku. • Liczba odniesień do pliku. • Liczba wykorzystywanych bajtów przez rekord. • Identyfikator rekordu bazowego (referencja) w przypadku rekordu rozszerzeń.
Systemy operacyjne
Wykład 6
84/94
NTFS — zawartość nagłówka atrybutu • Identyfikator atrybutu (typ i opcjonalna nazwa). • Długość wartości atrybutu w bajtach. • Lokalizacja wartości atrybutu. • Flagi.
Systemy operacyjne
Wykład 6
85/94
NTFS — wybrane atrybuty pliku • Informacje standardowe ($STANDARD_INFORMATION). • Nazwa pliku ($FILE_NAME). • Dane ($DATA). • Korzeń indeksu ($INDEX_ROOT). • Alokacja indeksu ($INDEX_ALLOCATION). • Mapa bitowa indeksu ($BITMAP). • Lista atrybutów ($ATTRIBUTE_LIST).
Systemy operacyjne
Wykład 6
86/94
NTFS — identyfikacja rekordu MFT • Rekord MFT i tym samym plik identyfikowany jest wewnętrznie przez 64-bitową referencję. • 48 mniej znaczących bitów referencji jest numerem rekordu w tablicy MFT. • 16 bardziej znaczących bitów referencji jest numerem sekwencyjnym zwiększanym o 1 po każdym przydzieleniu rekordu do nowo utworzonego pliku, co zapobiega błędnym odwołaniom do plików z użyciem zdezaktualizowanych referencji. numer sekwencyjny Systemy operacyjne
numer rekordu MFT Wykład 6
87/94
NTFS — rekord bazowy • Jeśli lista atrybutów pliku nie mieści się w jednym rekordzie MFT, do pliku przydzielane są dodatkowe rekordy. • Pierwszy rekord MFT nazywany jest bazowym (lub podstawowym). • Dodatkowe rekordy MFT danego pliku określane są jako rekordy rozszerzeń. • Identyfikacja atrybutów, umieszczonych w rekordach rozszerzeń, znajduje się w atrybucie lista atrybutów, znajdującym się w rekordzie bazowym. Systemy operacyjne
Wykład 6
88/94
Implementacja atrybutu dane nagłówek rekordu MFT
nagłówek rekordu MFT
nagłówek informacje info. std. standard.
nagłówek informacje info. std. standard.
nagłówek nazwy
nazwa pliku
nagłówek nazwy
nagłówek danych
dane
mały plik
nazwa pliku
nagłówek informacje danych o blokach
duży plik
zakres bloków objętych opisem
nagłówek listy przebiegów opis przebiegu 1 opis przebiegu 2 . . .
indeks pierwszego bloku i liczba bloków w przebiegu Systemy operacyjne
Wykład 6
opis przebiegu n 89/94
Implementacja atrybutu dane nagłówek rekordu MFT nagłówek informacje info. std. standard.
nagłówek nazwy nagłówek listy atryb.
nazwa pliku id atryb. dane
id atryb. dane
nagłówek informacje danych o blokach
bardzo duży plik (pofragmentowany) Systemy operacyjne
nagłówek rekordu MFT
nagłówek listy przebiegów
nagłówek informacje info. std. standard.
opis przeb. k+1
nagłówek rekordu MFT nagłówek informacje info. std. standard.
. . .
opis przeb. m
nagłówek listy przebiegów
nagłówek listy przebiegów
opis przebiegu 1
opis przeb. m+1
. . .
. . .
opis przebiegu k
opis przeb. n
Wykład 6
90/94
NTFS — katalogi • Katalog zawiera sekwencję wpisów (rekordów), z których każdy odpowiada jednemu plikowi i obejmuje jego następujące atrybuty: – referencja pliku, – nazwa (wraz z długością), – rozmiar, – czasy dostępów. • Implementacja dużych katalogów oparta jest na strukturze indeksowej (B±drzewo).
Systemy operacyjne
Wykład 6
91/94
Implementacja katalogu nazwa referencja rozmiar czasy
nagłówek rekordu MFT nagłówek informacje info. std. standard.
nagłówek nazwa nazwy katalogu
wpis 1
nagłówek korzenia
wpis 2
korzeń indeksu
wpis 3
mały katalog
. . .
wpis n Systemy operacyjne
Wykład 6
92/94
Implementacja katalogu nagłówek informacje info. std. standard. nagłówek nazwa nazwy katalogu nagłówek korzenia
korzeń indeksu
nagłówek alok. ind.
alokacja indeksu
nagłówek mapa bit. mapy bit. indeksu
duży katalog nazwa wraz z długością Systemy operacyjne
nazwa wraz z długością
VCN 0
nazwa 1
VCN 00
wpis 1
nazwa 01
wpis 2
VCN 01
wpis 3
nazwa 02
wpis 4
VCN 02
wpis 5
. . .
VCN 1 nazwa 2
…
. . .
VCN 2 nazwa 3 . . .
VCN 10
wpis k
nazwa 11
wpis k+1
VCN 11
wpis k+2
. . nazwa referencja .
VCN n Wykład 6
…
nagłówek rekordu MFT
rozmiar czasy
. . .
93/94
NTFS — wybrane pliki metadanych • • • • • • •
$MFT — główna tablica plików $MTFMIRR — kopia MFT $LOGFILE — plik dziennika $VOLUME — plik wolumenu $DEFATTR — definicja atrybutów plików $ — katalog główny (korzeń drzewa) $BITMAP — wektor bitowy (informacja o wolnych/zajętych blokach)
Systemy operacyjne
Wykład 6
94/94
View more...
Comments