Wprowadzenie
Powiedzieć z czego się składa czas odczytu/zapisu z dysku. Przeanalizować dokładnie treść zadania i zastanowić się jaki wpływ na czas dostępu do dysku ma każdy z wymienionych parametrów liczbowych.
Ćwiczenie 1
Dyskietka zawiera 40 ścieżek. Czas przesuwu głowicy o jedną ścieżkę wynosi 6 ms. W zwykłym trybie zapisu dwa kolejne (w sensie logicznym) bloki pliku alokowane są w średniej odległości 13 ścieżek. W trybie klastrowania odległość ta może zostać zmniejszona do średnio 2 ścieżek. Ile czasu potrzeba w obu przypadkach na przeczytanie pliku złożonego ze 100 bloków, jeżeli czas rotacji dyskietki wynosi 200 ms, a ścieżka składa się z 8 bloków?
Rozwiązanie
Czas odczytu jednego bloku (gdy głowica jest już na początku sektora): 200 ms/8 = 25 ms
W zwykłym trybie zapisu:
Czas transmisji jednego bloku: 13 * 6 + 1/2 * 200 + 25 = 203 ms
Czas transmisji 100 bloków: 100 * 203 = 20300 ms
W trybie klastrowania:
Czas transmisji jednego bloku: 2 * 6 + 1/2 * 200 + 25 = 137 ms
Czas transmisji 100 bloków: 100 * 137 = 13700 ms
Ćwiczenie 2
Rozważmy dysk o jednej powierzchni zawierającej 100 ścieżek po 100 bloków każda. Rozmiar bloku wynosi 500 B. Dysk obraca się z prędkością 3000 obr/min. Czas przesuwu głowicy o 1 ścieżkę wynosi 10 ms.
Na dysku umieszczono plik o wielkości 100 000 B, stosując organizację liniową łączoną. Załóżmy, że plik ten został rozmieszczony na ścieżkach 0, 1, 2, 3, 4 w porcjach po 25 bloków. W obrębie każdej ścieżki kolejność logiczna bajtów odpowiada kolejności fizycznej bloków.
---------------------------------
| | |///////| |
---------------------------------
|///////| | |///////|
---------------------------------
| |///////|///////| |
---------------------------------
|///////| | |///////|
---------------------------------
| |///////| | |
---------------------------------
Zakładając, że bloki są rozdzielone odstępami w taki sposób, że procesor po potwierdzeniu przesłania bloku zdąży wysłać na czas żądanie transmisji następnego (fizycznie) bloku, obliczyć czas potrzebny do odczytania całego pliku od początku do końca. Wielkość bufora pamięci odpowiada wielkości bloku na dysku. W chwili początkowej głowica jest w pozycji (0, 0).
Jakie rozmieszczenie plików zagwarantowałoby najkrótszy czas realizacji tej operacji przy tym samym adresie początkowym? Ile czasu zajęłaby ta operacja w przypadku organizacji ciągłej przy tym samym adresie początkowym?
Rozwiązanie
--------------------------
| 3 | 4 | 1 | 2 |
--------------------------
| 5 | 6 | 7 | 8 |
--------------------------
--------------------------
| | | 1 | 2 |
--------------------------
| 3 | 4 | 5 | 6 |
--------------------------
| 7 | 8 | | |
--------------------------
Ćwiczenie 3
Ruchoma głowica dysku o 200 ścieżkach (0 .. 199) obsługuje żądanie do ścieżki 143, a poprzednio zakończyła obsługę żądania do ścieżki 159. W kolejce czekają żądania (w kolejności przybycia):
86, 147, 91, 177, 94, 150, 102, 175, 130
Jaki ruch wykona głowica podczas obsługi tych żądań zgodnie z następującymi algorytmami szeregowania:
Rozwiązanie
Wprowadzenie
Opowiedzieć krótko o podstawowych RAID-ach, jakby było mało czasu, to tylko o tym, którego dotyczy zadanie, czyli Level 4.
Ćwiczenie 4
Macierz dyskowa RAID (L.4) składa się z 5 identycznych napędów dyskowych, z których 4 są przeznaczone na zapisywanie danych, natomiast piąty (redundant disk) na zapamiętywanie informacji kontrolnej pozwalającej na odzyskanie danych w przypadku awarii któregoś z napędów.
Z punktu widzenia użytkownika bloki dyskowe macierzy widziane są tak jakby były jednym dyskiem o czterokrotnie wiekszej pojemności i rozmieszczone są na dyskach w następujący sposób:
| dysk0 | dysk1 | dysk2 | dysk3 | dysk4 |
| bl.0 | bl.1 | bl.2 | bl.3 | P(0-3) |
| bl.4 | bl.5 | bl.6 | bl.7 | P(4-7) |
| bl.8 | bl.9 | bl.10 | bl.11 | P(8-11) |
| bl.12 | bl.13 | bl.14 | bl.15 | P(12-15) |
| .... | .... | .... | .... | .... |
gdzie bl.i oznacza kolejny blok danych natomiast P(k-l) oznacza bloki bitów kontrolnych odnoszących się do bloków od k do l (każdy bit bloku kontrolnego jest bitem parzystości dla ciągu odpowiednich bitów bloków danych).
Ile i jakich operacji dyskowych musi wykonać system przy zapisie bloku danych? Odpowiedź szczegółowo uzasadnij, podając jakie to operacje i dlaczego akurat takie są wymagane. Zakładamy, że blok logiczny jest równy blokowi fizycznemu.
Rozwiązanie
Cztery operacje: 2 operacje odczytu (zamazywanego bloku i bloku parzystości) oraz dwie operacje zapisu (nowego bloku i zaktualizowanego bloku parzystości). Tak jest przy programowej realizacji RAIDa. Przy sprzętowej system musi wykonać jeden zapis, a resztą zajmuje się macierz RAID. Ona wykonuje 2 odczyty i 2 zapisy, w czasie 1 odczytu i 1 zapisu (przy założeniu, że szyna pozwala na równoczesne odczytywanie bloków z różnych dysków).
Wprowadzenie
Zadanie jest pretekstem do porozmawiania o korzyściach z buforowania oraz kompromisie między czasem a pamięcią.
Ćwiczenie 5
Pewien system liczący ma realizować następujący proces przetwarzania danych:
loop
wczytaj rekord wejściowy;
przetwórz rekord;
wypisz rekord wynikowy;
end loop
Nośnikiem danych wejściowych i wynikowych są taśmy magnetyczne. Parametry jednostek taśmowych są następujące:
Długość wszystkich rekordów logicznych (wejściowych i wynikowych) jest jednakowa i wynosi 320B, natomiast współczynnik zblokowania (liczba rekordów logicznych przypadających na jeden rekord fizyczny) jest ustalany przez programistę. Obszar pamięci operacyjnej przeznaczonej na bufory wynosi 9600 B. Rekordy mogą być przetwarzane "na miejscu", bez użycia dodatkowej pamięci. Zakładamy, że czas procesora potrzebny do przetworzenia pojedynczego rekordu jest stały i równy 1 ms. Zakładamy również, że operację wejścia-wyjścia można zainicjować dopiero w momencie, gdy bufor jest gotów do transmisji.
Wskazać optymalną ze względu na przepustowość implementację programu realizującego powyższy proces, gdy system ma:
W obu przypadkach podać przepustowość (w rekordach/ms), współczynnik zblokowania, podział pamięci i sposób jej wykorzystania, etapy przetwarzania wykonywane współbieżnie.
Rozwiązanie
Niech współczynnik zblokowania wynosi k. Wtedy czas pojedynczej operacji wynosi t + k*s/m, gdzie t - czas dostępu sekwencyjnego, s - długość rekordu, m - prędkość transmisji.
Zatem czas operacji wejścia-wyjścia w przeliczeniu na 1 rekord wynosi t = (1 + ta/k). Ponieważ M = 9600 B, więc 1 <= k <= 30.
Przy ustalonym k maksymalną przepustowość można uzyskać zapewniając maksymalną równoległość trzech operacji: wczytywania, przetwarzania i wypisywania.
Warianty równoległości (w każdym wariancie należy rozpocząć od rozrysowania na trzech rówoległych osiach, odpowiadających trzem operacjom, przebiegu operacji w czasie):
Wartości maksymalne otrzymujemy odpowiednio dla:
| ©Janina Mincer-Daszkiewicz |