Podręcznik

1. Tryby pracy procesora

Tryby pracy procesora zostaną przedstawione na przykładzie procesorów firmy Intel. Jednak dla wszystkich procesorów klasy PC są one analogiczne.

Rys. 1. Tryby pracy procesora firmy Intel

Na rysunku 1 przedstawiono możliwe tryby pracy procesora firmy Intel. Wiążą się one ściśle ze sposobem adresowania pamięci. Historycznie najstarszy jest tryb rzeczywisty. Jest to tryb pracy pierwszych procesorów Intela. W trybie tym procesor ma do dyspozycji 20 bitową szynę adresową. Należy pamiętać, że rejestry procesora były wtedy 16 bitowe. W celu wygenerowanie adresu 20 bitowego użyto pewnego triku. Do adresowania są wykorzystywane dwa rejestry 16 bitowe (Rys. 2). Jeden z nich (adres przesunięcia) jest traktowany jak zwykły rejestr 16 bitowy. Drugi (rejestr segmentowy) jest traktowany jako rejestr, do którego dopisano (w domyśle) cztery bity na ostatnich, najmniej znaczących, pozycjach. Rejestr ten jest traktowany, jako 20 bitowy, gdzie ostatnie cztery bity są zawsze zerami. Następnie sumator dodaje wartości tych rejestrów generując adres 20 bitowy. Ten sposób adresowania jest charakterystyczny dla pierwszych komputerów działających pod systemem operacyjnym DOS. Pamięć w tym trybie nie jest chroniona w żaden sposób. Każdy program może zapisywać dane w dowolne miejsce pamięci, również tam gdzie rezyduje system operacyjny, powodując w takim przypadku jego zawieszenie. Ponieważ dysponujemy 20 liniami adresowymi, to możliwy do zaadresowania obszar pamięci wynosi 1MB. Na początku wartość ta wydawała się więcej niż wystarczająca. Należy nadmienić, że do dyspozycji programów nie była cała dostępna pamięć, a tylko jej część (do 640kB). W pozostałej, górnej części pamięci przechowywane były różne dane systemowe.

Rys. 2. Sumator do obliczania 20-to bitowego adresu fizycznego (system operacyjny DOS)

Programy jednak stawały się coraz bardziej „zasobożerne”. Szybko okazało się, że pamięci brakuje. W procesorach, począwszy od Intel 386, pojawił się nowy tryb chroniony pracy. Przede wszystkim teraz procesory były 32 bitowe. Procesor mógł bezpośrednio adresować 2^32 = 4,294,967,296 (4GB) pamięci. Jednak pamięć, ze względów które będą wyjaśnione dalej, nie była adresowana bezpośrednio. Stosowano najczęściej technikę segmentacji pamięci połączoną ze stronicowaniem. W tym przypadku pamięć była chroniona przed nieuprawnionym dostępem (stąd nazwa tego trybu). Programy nie mogły już bezkarnie zapisywać danych w obszary zajmowane przez system operacyjny i inne programy. Niebagatelna była też możliwość adresowania aż 4 GB pamięci RAM.

Pojawił się jednak problem, jak obsłużyć stare programy, pracujące w trybie rzeczywistym. Przełączanie procesora pomiędzy pracą w trybie rzeczywistym i chronionym było co prawda możliwe, ale bardzo kłopotliwe. Dlatego powstał tryb wirtualny 8086. Jest to możliwość stworzenia wirtualnego trybu rzeczywistego, koniecznego np. do uruchomienia programu pracującego pod kontrolą systemu DOS, działającego bezpośrednio w trybie chronionym. Nie trzeba było już przełączać się pomiędzy trybami. Co więcej każdy program DOS mógł mieć własne, wirtualne środowisko pracy.

Z chwilą pojawienia się procesorów 64 bitowych wprowadzono odrębny tryb adresowania IA-32e. Jest to rozszerzony tryb chroniony, w którym adresy mogą być 64 bitowe. Ze względów ekonomicznych nie stosuje się adresowania 64 bitowego. W Windows adresy są 47 bitowe, na płytach głównych często wyprowadzanych jest tylko 40 ścieżek adresu. Tym niemniej i tak dostępna przestrzeń adresowa przekracza możliwości konstrukcyjne pamięci RAM. W tym trybie pamięć jest również chroniona. Najczęściej stosuje się stronicowanie pamięci (segmentacja jest wyłączona).

Tryb zarządzania systemem (ang. system management) jest charakterystyczny dla procesorów Intela. Służy on głównie do diagnostyki systemu w ramach interfejsu ACPI (ang. Advanced Configuration and Power Interface). Poniżej wymieniono niektóre sytuacje, gdzie ten tryb pracy może być użyty:

• Obsługa zdarzeń systemowych, takich jak błędy pamięci lub mikroukładu.
• Zarządzanie funkcjami bezpieczeństwa systemu, takimi jak wyłączanie przy wysokiej temperaturze procesora oraz włączanie i wyłączanie wentylatorów.
• Uśpienie systemu i hibernacja, itp.

2. Zarządzanie pamięcią

Procesor ma do dyspozycji pewną liczbę bitów, za pomocą których można adresować pamięć. W procesorach 32 bitowych jest to 32 bity, 64 bitowych – 64 bity itd. Przy użyciu tych bitów może zostać zaadresowany pewien ciągły obszar pamięci. Każdy uruchomiony program ma swoją taką przestrzeń adresową. Pamięć, którą może zaadresować procesor nazywamy logiczną przestrzenią adresową. W komputerze jest zainstalowana pamięć RAM, której rozmiar jest zwykle mniejszy niż możliwy do zaadresowania logiczny obszar pamięci procesora. Obszar adresów dotyczący zainstalowanej pamięci RAM nazywamy fizycznym obszarem adresowym. Programy w zasadzie nigdy nie wykorzystują całego obszaru logicznego, a tylko jego mały fragment. Jednostka zarządzania pamięcią tłumaczy adresy zajętych przez program obszarów w pamięci logicznej na dostępne fizycznie adresy w pamięci RAM (Rys. 3.). W najprostszym przypadku może być to tzw. rejestr przemieszczenia, którego wartość jest dodawana do adresu logicznego.

Rys. 3. Logiczna i fizyczna przestrzeń adresowa

W systemach wielozadaniowych może dojść do sytuacji, w której chcemy uruchomić np. dwa programy jednocześnie, ale zainstalowana pamięć RAM jest zbyt mała. Wtedy, w najprostszym przypadku, możemy wymienić procesy w pamięci (Rys. 4). Metoda ta nie jest już od dawna stosowana ze względu na swoje wady.

Rys. 4. Wymiana dwóch procesów

W przypadku wymiany, proces, który jest aktualnie wykonywany, jest zatrzymywany i wysyłany do pamięci pomocniczej (na dysk twardy). Na jego miejsce wprowadzany jest nowy proces. Każdy z procesów ma przydzielony pewien kwant czasu na swoje działanie. Oczywiście czas ten nie może być krótszy niż czas potrzebny na wysłanie i sprowadzenie procesu do pamięci pomocniczej. Dodatkowym problemem jest to, że zwykle proces, który ma być powtórnie wprowadzony do pamięci, musi znaleźć się dokładnie w tym samym miejscu, w którym był poprzednio. Wymiana procesów trwa długo, nie jest więc to rozwiązanie optymalne.

Zwykle w systemach wielozadaniowych w danej chwili działa wiele procesów. Załóżmy, że mamy sytuację przedstawioną w tabeli 1. W kolejce zadań jest pięć procesów. Każdy z nich zajmuje określoną ilość pamięci i działa przez określony czas.

Tabela 1. Kolejka zadań

W systemie operacyjnym mamy miejsce na umieszczenie w pierwszej chwili trzech pierwszych procesów P1, P2, P3 (Rys. 5). Po 5 jednostkach czasu proces P2 kończy swoje działanie. Na jego miejsce możemy wprowadzić proces P4. Zajmuje on jednak mniej miejsca w pamięci niż proces P2, powstaje więc pewien nieużytek (dziura). Później kończy działanie proces P1. Wprowadzamy proces P5. Również powstaje pewien nieużytek. Po pewnym czasie może się okazać, że jedna trzecia pamięci stanowi nieużytek. Pomięć jest poszatkowana. Jest to tzw. fragmentacja zewnętrzna pamięci.

Rys. 5. Rozmieszczenie procesów w pamięci operacyjnej

Z fragmentacją zewnętrzną można walczyć. Można szukać najbardziej pasujących obszarów pamięci, do których zostanie wprowadzony nowy proces. Stosuje się trzy strategie:

• pierwsze dopasowanie – proces jest wstawiany w pierwszy dostępny obszar, w który się mieści,
• najlepsze dopasowanie – proces jest wstawiany w wolny obszar tak, aby pozostały nieużytek był najmniejszy,
• najgorsze dopasowanie – proces jest wstawiany w wolny obszar tak, aby pozostały nieużytek był największy (z nadzieją, że inny proces się zmieści w tym nieużytku).

Żadna z tych strategii nie rozwiązuje problemu. Żadna nie jest też zdecydowanie lepsza od drugiej. Innym rozwiązaniem mogłoby być upakowanie pamięci. Wszystkie procesy są wtedy przenoszone w inne obszary pamięci, tak aby tworzyły jeden blok. Z pozoru wydaje się to prostym rozwiązaniem, jednak tak nie jest. Często procesu nie da się przenieść w prosty sposób. Z drugiej strony koszt czasowy takiej operacji jest nieakceptowalny. Spowolnienie działania całego systemy byłoby zbyt duże.

2.1. Stronicowanie pamięci

Praktycznym rozwiązaniem problemu przedstawionego w poprzednim rozdziale jest stronicowanie pamięci. W rozwiązaniu tym pamięć logiczna (adresowana przez procesor) jest podzielona na strony (Rys. 6). Z kolei pamięć fizyczna (RAM) jest podzielona na ramki o takim samym rozmiarze. Pewien proces działający w pamięci logicznej zajmuje konkretną liczbę ramek (tu 4). Ramki mogą być umieszczone w dowolnych stronach pamięci RAM. Odwzorowanie stron w ramki jest opisane w tablicy stron. Zwykle każdy proces ma taką swoją tablicę. Indeks (numer komórki) w tablicy stron oznacza numer strony, natomiast zawartość komórki oznacza odpowiadającą stronie ramkę. Więc strona 0 znajduje się w ramce 2, strona 1 w ramce 7 itd. Przy takim odwzorowaniu proces, który ma ciągłą przestrzeń adresową w pamięci logicznej, może być dowolnie porozrzucany do różnych ramek w pamięci RAM. Nie występuje tu fragmentacja zewnętrzna. Natomiast może wystąpić fragmentacja wewnętrzna. Nie można procesowi przydzielić ułamka ramki. Więc jedna ramka może nie być w pełni wykorzystana. Fragmentacja wewnętrzna jest jednak niewielkim problemem w porównaniu z fragmentacją zewnętrzną.

Rys. 6. Model stronicowania pamięci

Stronicowanie powoduje straty czasowe w dostępie do pamięci. Można zauważyć, że tablica stron jest strukturą tworzoną również w pamięci RAM. Każdy dostęp do pamięci powoduje konieczność odwołania się do tej tablicy. Zatem dostęp do pamięci wymaga dwóch odwołań do pamięci. Powoduje to dwukrotne wydłużenie czasu dostępu do pamięci, co w ogromnej większości przypadków jest nieakceptowalne. W celu wyeliminowania tego wydłużenia dostępu do pamięci stosuje się buforowanie najczęściej używanych stron z całej tablicy stron (Rys. 7). Są to tzw. bufory TLB (ang. Transaction Lookaside Buffers). Tablice stron są najczęściej tworzone dla poszczególnych procesów. W momencie wykonywania procesu ładowana jest jego tablica stron. Te strony, do których są odwołania, są zapisywane w rejestrach TLB. Powtórne odwołanie do strony jest realizowane bardzo szybko, jako że kojarzenie stron z buforów TLB zachodzi w jednym takcie zegara. Również dostęp do nich jest niemal natychmiastowy. Wadą tego rozwiązania jest dość duży koszt.
Ponieważ każdy proces ma swoją tablicę stron, jest ich stosunkowo dużo. W systemie 32 bitowym logiczna przestrzeń adresowa wynosi 4 GB. Strony i ramki dla procesów są zazwyczaj 4 kB. Potrzeba zatem milion wpisów w tablicy stron, aby opisać tą przestrzeń. Jeden wpis w tablicy stron zajmuje 4 B. Rozmiar tablicy stron wynosiłby więc 4 MB na proces. To dużo biorąc pod uwagą, że proces zwykle wykorzystuje mały ułamek pełnej logicznej przestrzeni adresowej. Rozwiązaniem tego problemu jest wielopoziomowa tablica stron. W 32 bitowym systemie stosuje się dwupoziomową tablicę stron (Rys. 8). Sama tablica stron jest podzielona na mniejsze fragmenty. Fragmenty te (ich położenie) jest opisywane przez zewnętrzną tablicę stron. Mamy więc dwie struktury w pamięci RAM. Jednak gdy proces wykorzystuje tylko niewielki fragment pamięci, tworzona jest zewnętrzna tablica stron i tylko te elementy tablicy stron, które są wykorzystywane. Daje to dużą oszczędność w zużyciu pamięci. Jednak teraz dostęp do danych wymaga aż trzech dostępów do pamięci. W tym przypadku bufory TLB są już niezbędne. W systemach 64 bitowych tablica stron jest aż pięcio-poziomowa. 

Rys. 7. Sprzęt stronicujący z buforami TLB
 
Rys. 8. Dwupoziomowa tablica stron

2.2. Segmentacja pamięci

Segmentacja pamięci jest metodą alternatywną do stronicowania. Chociaż może ona być używana samodzielnie, to najczęściej jest wykorzystywana w połączeniu ze stronicowaniem. W segmentacji proces jest podzielony na pewne części (segmenty). Każdy segment może mieć różną długość i różne prawa dostępu (Rys. 9). Intuicyjnie wiążą się one z funkcjami segmentów.

Rys. 9. Segmentacja pamięci

Podobnie jak przy stronicowaniu, istnieje tablica segmentów, która je opisuje. Znajdują się w niej adres startowy segmentu, jego rozmiar, prawa dostępu i inne dane. Segmenty mogą być dowolnie porozrzucane po pamięci RAM. Adres w tym przypadku składa się z dwóch elementów: 16 bitowego selektora segmentu i 32 bitowego (bądź 64 bitowego w systemach 64 bitowych) przesunięcia. Sposób tworzenia adresu jest pokazany na rysunku 10. Selektor segmentu wskazuje na odpowiedni element w tablicy segmentów. Tablica ta jest nazywana tablicą deskryptorów.

Rys. 10. Konwersja adresu logicznego na adres liniowy [źródło: Intel® 64 and IA-32 Architectures

Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C]

Z wpisu do tablicy deskryptorów jest pobierany adres bazowy, do którego jest dodawany adres przesunięcia. W ten sposób wyszukiwany jest konkretny adres w pamięci. W architekturze PC istnieją specjalne rejestry segmentowe. Są one związane z segmentami kodu, danych, stosu i innymi pomocniczymi. Każdy rejestr segmentowy zawiera opis jednego segmentu (Rys. 11).

Rys. 11. Model pamięci z użyciem wielu segmentów [źródło: Intel® 64 and IA-32 Architectures

Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C]

2.3. Segmentacja pamięci w połączeniu ze stronicowaniem

W wielu systemach stosuje się połączenie segmentacji pamięci ze stronicowaniem. Takie połączenie dla 32 bitowego systemu klasy PC przedstawione jest na rysunku 12. W tym przypadku adresem logicznym (generowanym przez procesor) jest adres w postaci selektor segmentu, przesunięcie. Następnie każdy segment ma zdefiniowaną swoją, dwupoziomową tablicę stron. Dopiero stronicowanie generuje adres fizyczny w pamięci RAM. W systemach 64 bitowych segmentacja jest wyłączona. Wszystkie rejestry segmentowe mają tak ustawione wartości, że wskazują na całą fizyczną przestrzeń adresową RAM. Do tworzenia adresów fizycznych wykorzystywane jest stronicowanie.

Rys. 12. Segmentacja w połączeniu ze stronicowaniem – tryb 32 bitowy [źródło: Intel® 64 and IA-32 Architectures Software Developer’s Manual Combined Volumes: 1, 2A, 2B, 2C, 3A, 3B and 3C]

3. Ochrona pamięci na poziomie segmentacji i stronicowania

Na poziomie segmentacji i stronicowania realizowana jest ochrona pamięci. W przypadku segmentacji sprawdzane są: rozmiary segmentów – limity adresowania, typy segmentów, poziomy uprzywilejowania. Dla stron sprawdzane są: typy stron, poziomy uprzywilejowania. W przypadku wykrycia próby dostępu poza dozwolony segment lub stronę generowany jest błąd. Istnieje dużo różnych typów segmentów. Do segmentu kodu nie jest np. dozwolony zapis, segment stosu jest do odczytu i zapisu, segmenty danych mogą być tylko do odczytu, do odczytu i zapisu itd. Jeśli chodzi o typy stron to istnieją dwa: strona użytkownika (ang. user mode) i strona superużytkownika (ang. supervisory mode). Strona użytkownika może być tylko do odczytu lub do odczytu i zapisu. Z takiej strony można się odnieść tylko do stron tego samego typu. Strona superużytkownika jest do zapisu i odczytu i można się z niej odnieść do dowolnej strony (Tabela 2).

Tabela 2. Typy stron

W segmentacji zdefiniowanych jest pięć poziomów uprzywilejowania w stronicowaniu dwa. Sposób odwzorowania poziomów uprzywilejowania pomiędzy segmentacją i stronicowaniem, jak również typowe użycie poziomów uprzywilejowanie jest przedstawione na rysunku 13.

Rys. 13. Poziomy uprzywilejowania

4. Pamięć wirtualna

Przy zastosowaniu stronicowania, założeniem jest, że aby program mógł być wykonany musi być całkowicie wczytany do pamięci RAM. W momencie kiedy zastosowana jest pamięć wirtualna, system operacyjny pozwala na wykorzystanie pamięci o większej pojemności od zainstalowanej pamięci RAM. Obszary logicznej przestrzeni adresowej, do których proces często się odwołuje przechowywane są w pamięci RAM. Obszary, do których proces odwołuje się rzadko, przechowywane są na dysku (może to znacznie obniżyć wydajność systemu). Przedłużenie pamięci RAM na dysk twardy nazywane jest pamięcią wirtualną. Należy zaznaczyć, że w żaden sposób nie da się uruchomić programu bezpośrednio z dysku twardego. Jest to związane ze sposobem dostępu do danych na dysku. Możemy z niego odczytać/zapisać klaster jako najmniejszą jednostkę alokacji (zwykle 4 kB). Do uruchomienia programu dostęp do danych musi być bajtowy (czyli musimy mieć możliwość odczytywania/zapisywania poszczególnych bajtów). Aby więc wykonać program zapisany w pamięci wirtualnej (na dysku) musimy ponownie wczytać go do pamięci RAM. Jeśli jednak dany fragment programu nie będzie nigdy wykorzystywany, może w ogóle nie być wczytany do pamięci RAM. Pamięć wirtualna zazwyczaj skonstruowana jest w oparciu o stronicowanie na żądanie (ang. on-demand paging). Ideę tego procesu przedstawiono na rysunku 14.

Rys. 14. Pamięć wirtualna

W logicznej przestrzeni adresowej proces zajmuje pewną liczbę ramek. Przestrzeń ta jest ciągła. Tablica stron (jak w zwykłym stronicowaniu) odwzorowuje ramki na strony w pamięci fizycznej RAM. Z tym, że w tym przypadku w tablicy stron wykorzystywany jest dodatkowy bit, bit poprawności. Bit ten informuje, czy strona jest w pamięci RAM, czy w pamięci pomocniczej, którą tworzy dysk twardy. Dodatkowo, w przypadku pamięci wirtualnej tablica stron przechowuje zazwyczaj dwa bity oznaczane „dirty” – D (do strony był zapis) i „accessed” – A (do strony było odniesienie). Dane w pamięci dyskowej są przechowywane na specjalnie sformatowanej partycji lub w pliku „swap”. System plików na partycjach wymiany jest specjalnie optymalizowany pod kątem szybkości dostępu do danych. Informacje prezentowane dla użytkownika mają w tym przypadku mało istotne znaczenie.

W najprostszym przypadku do pamięci RAM wprowadzane są tylko te strony, które są potrzebne. Jest to tzw. leniwa wymiana. W przypadku, kiedy system operacyjny wykryje brak strony (bit p) wykonywana jest sekwencja poleceń systemowych, która sprowadza się do:

• przechowania stanu przerwanego procesu,
• sprowadzenia brakującej strony do pamięci,
• wznowienia procesu w tym samym miejscu.

Do realizacji pamięci wirtualnej potrzebne jest wsparcie systemu operacyjnego, ale również pewne zaplecze sprzętowe, jak:

• tablica stron,
• pamięć pomocnicza,
• system operacyjny musi umożliwiać wznowienie procesu w miejscu przerwania.

Pamięć wirtualna może mieć bardzo duży wpływ na wydajność całego systemu. Dlatego musi być zaimplementowana bardzo rozważnie. Brak strony wywołuje całą sekwencję zdarzeń związaną z:

1. Obsługą przerwania wywołanego brakiem strony.
2. Czytaniem strony z dysku.
3. Wznowieniem procesu.

Pierwsza i trzecia czynność realizowana jest programowo i sprowadza się zwykle do kilkuset rozkazów. Czas realizacji tych rozkazów to 1 do 100 us. Najbardziej czasochłonne jest czytanie/zapisywanie strony na dysku. Czas dostępu do pamięci RAM mieści się zwykle w zakresie od 10 do 100 ns, natomiast dostęp do pamięci dyskowej trwa ok. 10 ms. Zatem błąd braku strony zwiększa czas dostępu 100 000 razy. Żeby nie dopuścić do wyraźnego spowolnienia systemu błędy braku stron mogą występować bardzo rzadko – 1 brak na kilka milionów odwołań.

Żeby wydajnie zaimplementować pamięć wirtualną trzeba rozwiązać dwa główne problemy:

• zastępowanie stron,
• przydział ramek.

W pewnym momencie wolne ramki mogą się skończyć. Przyjmijmy, że procesowi przydzielono k ramek pamięci oraz że wszystkie ramki są już zajęte. W takiej sytuacji przy błędzie braku strony musimy wybrać jedną ze stron obecnych w pamięci (stronę-ofiarę). Jeżeli ta strona została zmodyfikowana (D==1), to należy ją dodatkowo zapisać na dysk. Ma to spory wpływ na wydajność systemu, dlatego że w tym przypadku wymagane są dwa dostępy do dysku twardego. Następnie ramka odpowiadająca wybranej stronie jest zwalniana. Nietrywialnym zadaniem jest wybranie ramki-ofiary. Zazwyczaj chcemy, aby strony, do których proces się często odwołuje, przebywały na stale w pamięci. Powstaje tu problem jak określić “częstość odwołań do strony”.  Wybór strony-ofiary jest wykonywany przez algorytm zastępowania stron (ang. page replacement). Istnieje wiele algorytmów zastępowania stron, z których tylko nieliczne mają zastosowanie praktyczne.

Pierwszym jest algorytm optymalny. Mówi on, że należy zastąpić tą stronę, do której nie będziemy się odwoływać przez najdłuższy czas. Algorytm ten, ze względu na konieczność posiadania informacji o przyszłości, jest niemożliwy do zaimplementowania w praktyce. Jest on za to szeroko stosowany do porównywania z innymi algorytmami.

Jednym z najprostszych i najłatwiejszych do zaimplementowania jest algorytm FIFO (ang. First In First Out). Mówi on, że należy zastąpić tą stronę, która została sprowadzona jako pierwsza do pamięci. Sprowadzone strony tworzą kolejkę FIFO. Algorytm ten jest daleki od optymalnego. Strona, która była wprowadzona dawno do systemu może być cały czas potrzebna. Poza tym algorytm ten jest obarczony anomalią Belady'ego - większa liczba ramek niekoniecznie zmniejsza liczbę błędów stron.

Jednym z najbardziej obiecujących jest algorytm LRU (ang. Least Recently Used). W algorytmie tym zastępowana jest strona, która nie była najdłużej używana. Zakłada się, że ta strona nie będzie dalej potrzebna. Algorytm ten nie wykazuje anomalii Belady'ego. Jednak do zaimplementowania tego algorytmu w czystej postaci potrzebna jest pewne zaplecze sprzętowe, umożliwiające określenie liczby odwołań do strony w jednostce czasu. Większość systemów ma tylko bity A oraz D. Dlatego w praktyce stosuje się algorytmy przybliżające metodę LRU.

Jednym z takich algorytmów jest algorytm drugiej szansy. Jego zasada działania jest następująca:

• Jest to modyfikacja algorytmu FIFO.
• W standardowym algorytmie FIFO wybierana jest pierwsza strona z kolejki.
• W algorytmie drugiej szansy sprawdzany jest bit odniesienia A.
• Jeżeli A==0 (brak odniesienia) to strona jest wybierana na ofiarę.
• Jeżeli (A==1) (odniesienie) to: bit A jest ustawiany na zero, strona nie jest usuwana na dysk, strona jest przesunięta na koniec kolejki (otrzymuje drugą szansę).
• Przechodzimy do kolejnej strony w kolejce.

W algorytmie tym możemy też uwzględnić bit D „dirty”. Należy pamiętać, że strona która została zmodyfikowana musi być zaktualizowana w pamięci dyskowej. Operacja taka będzie wymagała dodatkowego czasu. Zapisywanie zmodyfikowanych stron może być realizowane w różny sposób:

• Strona zapisywana w momencie jej zastąpienia
  • mała liczba zapisów na dysk,
  • powolny algorytm - brak strony powoduje konieczność zapisania strony na dysk i wczytania strony z dysku.
• Strony zapisywane periodycznie w tle
  • proces drugoplanowy przegląda strony i zapisuje strony zmodyfikowane (D==1), do których ostatnio nie było odwołań,
  • zapisanie strony powoduje skasowanie bitu D.
  • proces drugoplanowy może zapisywać strony grupami (większa wydajność operacji dyskowych).

System operacyjny może też utrzymywać pewną pulę wolnych ramek.

Drugim ważnym problemem do rozwiązania, przy implementacji pamięci wirtualnej, jest odpowiedni przydział ramek do procesu. Przy stronicowaniu na żądanie w systemie wieloprogramowym zakłada się współistnienie wielu procesów. Strony mogą być przydzielane:

• lokalne - strona-ofiara jest wybrana wyłącznie spośród stron procesu,
• globalne - strona-ofiara jest wybrana spośród stron wszystkich procesów.

Przydział globalny jest bardziej optymalny. Innym problemem jest sposób rozdziału ramek między procesy. Tu można zastosować:

• przydział stałej liczby ramek, np. 100 ramek, 5 procesów, przydział po 20 ramek,
• przydział liczby ramek proporcjonalnie do rozmiaru procesu,
• przydział liczby ramek proporcjonalnie do rozmiaru procesu z uwzględnieniem priorytetów.

Oczywiście trzecia możliwość jest najbardziej optymalna i jest stosowana w praktyce. Powstaje jednak pytanie jaka jest optymalna liczba ramek, która powinna być przypisana do konkretnego procesu? W celu określenia tej optymalnej liczby ramek stosuje się model strefowy. Założeniem jest to, że proces może w różnych etapach swojego działania potrzebować różnej liczby ramek. W praktyce określa się górną i dolną granicę występowania braków stron dla procesu (Rys. 15). Jeśli osiągnięto górną granicę, to liczba braków stron jest zbyt duża i procesowi należy przydzielić więcej ramek. Jeśli osiągnięto dolną granicę, to liczba braków stron jest mała i procesowi można zabrać pewną liczbę ramek. W ten sposób można określić optymalną liczbę ramek dla procesu.

Rys. 15. Model strefowy

5. Przerwania

Uproszczona architektura systemu komputerowego klasy PC jest przedstawiona na rysunku 16. Składa się na nią procesor, pamięć główna, system magistral oraz sporo urządzeń wejścia-wyjścia. Sterowanie jest zrealizowane z wykorzystaniem chipsetu płyty głównej. Do urządzeń wejścia-wyjścia można zaliczyć skaner, drukarkę, ale również mysz, klawiaturę, dołączoną do systemu kartę sieciową, czy graficzną, dyski twarde. Bardzo ważna jest możliwość szybkiej komunikacji z tymi urządzeniami.

Rys. 16. Uproszczona architektura PC

Warte zauważenia jest to, że urządzenia wejścia-wyjścia wymagają szybkiej obsługi ze strony CPU w losowym czasie, nawet jeśli w danej chwili CPU wykonuje inne zadania (programy). Potrzebny jest jakiś mechanizm „zwrócenia uwagi na dane urządzenie”. Przerwania właśnie to umożliwiają. Na rysunku 17 jest przedstawiona idea systemu przerwań. Program jest wykonywany przez procesor w sposób sekwencyjny. W pewnym losowym czasie urządzenie zgłasza chęć obsługi poprzez przerwanie. Program jest przerywany z zapamiętaniem miejsca przerwania. Następnie wykonywana jest procedura obsługi urządzenia. Po jej zakończeniu następuje powrót do wykonywania przerwanego programu. W ten sposób można efektywnie obsługiwać urządzenia, które żądają obsługi w losowym czasie. Nie trzeba cały czas sprawdzać, czy wymagają obsługi, ponieważ same sygnalizują ten fakt. W niektórych systemach przerwanie może być przerwane przez inne przerwanie o wyższym priorytecie. Mówimy wtedy o zagnieżdżonej obsłudze przerwań.

Rys. 17. Obsługa przerwań

Podsumowując, przerwanie to wymuszona zmiana normalnego biegu programu. Zachodzi ono podobnie do zmiany kontekstu (wykonywanego aktualnie procesu):

• sprzęt zapisuje na stosie potrzebne informacje dotyczące przerywanego programu,
• dostarczany jest numer przerwania,
• numer przerwania jest skojarzony z programem jego obsługi,
• uruchamiany jest program obsługi przerwania,
• po obsłudze przerwania jest wznawiany zatrzymany wcześniej program.

Istnieje wiele sytuacji powodujących przerwania. W ten sposób są obsługiwane nie tylko urządzenia wejścia-wyjścia, ale również inne zdarzenia. Stąd też przerwania można podzielić na klasy związane ze zdarzeniami, które je powodują. Poniżej wymienione są najważniejsze klasy przerwań:

1. I/O – urządzenia wejścia/wyjścia.
2. Sytuacje wyjątkowe, uszkodzenia sprzętu.
3. Programowe – dzielenia przez zero, przepełnienie arytmetyczne.
4. Zegarowe – generowane przez wewnętrzny zegar.

Przerwania są obsługiwane nieco odmiennie w zależności od konstrukcji systemu komputerowego i klasy przerwania. Tu skupimy się głównie na przerwaniach związanych z urządzeniami wejścia/wyjścia. Idea obsługi wszystkich przerwań pozostaje taka sama.

Początkowo w systemach klasy PC istniały tylko dwie możliwości zasygnalizowania przerwania sprzętowego. Należało doprowadzić sygnał do pinu ~INT, bądź ~NMI procesora. Ta druga opcja obsługiwała tzw. przerwania niemaskowalne, związane z obsługą błędów w pamięci. Przerwanie to ma najwyższy priorytet i zawsze powoduje wstrzymanie pracy systemu komputerowego z jednoczesnym wystawieniem odpowiedniego komunikatu. Przerwania doprowadzane do pinu ~INT, to typowe przerwania zgłaszane przez sprzęt. Są one zwane też przerwaniami maskowalnymi ze względu na możliwość ich zablokowania (zamaskowania). W najwcześniejszych komputerach PC obsługą przerwań zajmował się dedykowany układ 8259. Trochę później stosowano dwa takie układy połączone kaskadowo w celu zwiększenia liczby dostępnych przerwań (Rys. 18).

Rys. 18. Kaskadowe połączenie dwóch układów 8259A obsługujących przerwania sprzętowe

Przerwania obsługiwane w ten sposób oznaczano symbolem IRQx, gdzie x oznacza numer przerwania. Ponieważ układ 8259 obsługuje 8 przerwań, przez połączenie dwóch takich układów uzyskano możliwość doprowadzenia 15 przerwań (jedno doprowadzenie jest wykorzystane do połączenia układów). Sposób obsługi przerwania jest przedstawiony na rysunku 19. Urządzenia zgłaszające przerwania są połączone z wyprowadzeniami układu 8259. Urządzenie jest identyfikowane przez numer przerwania.

Rys. 19. Schemat ideowy układu 8259A do obsługi przerwań sprzętowych

Wystawienie aktywnego sygnału na wejście układu 8259 jest równoważne ze zgłoszeniem przerwania. Przerwania są obsługiwane w kolejności: im niższy numer przerwania, tym wyższy priorytet. Przerwanie o najwyższym priorytecie dopuszczane jest do obsługi. Każde przerwanie może być zablokowane przez ustawienie odpowiedniej flagi w rejestrze maskującym. Jeśli przerwanie jest dopuszczone do obsługi, układ 8259 wysyła sygnał na pin ~INT procesora i po otrzymaniu zezwolenia na przerwanie (pin ~INTA) generowana jest liczba identyfikująca przerwanie. Następuje, nadzorowany przez system operacyjny, skok do obsługi przerwania. Obecnie nie stosuje się już układów 8259. Jednak, w celu zachowania kompatybilności, do chwili obecnej istnieje możliwość wykorzystywania przerwań w ten sposób. Działanie układów 8259 jest emulowane przez chipset płyty głównej.

Opisany powyżej sposób obsługi przerwań jest ściśle związany z podstawową magistralą systemową obsługującą urządzenia I/O. W tym przypadku była to magistrala ISA. Następną magistralą systemową, która była szeroko wykorzystywana i jest niekiedy wykorzystywana we współczesnych komputerach, jest magistrala PCI. Wraz z pojawieniem się tej magistrali zmienił się nieco sposób obsługi przerwań. Przerwania obsługiwane przez magistralę PCI nazwano ~INTA, ~INTB, ~INTC, ~INTD. Są to linie, poprzez które można zgłaszać przerwania. Jednak sposób obsługi przerwań się nie zmienił. Nowe przerwania są tłumaczone przez specjalnie dodany router przerwań na stare ~IRQx, które są nieprzydzielone (Rys.20). W tym czasie zaczynało już brakować wolnych przerwań. Co prawda linie przerwań ~IRQ mogą być dzielone pomiędzy dwa lub więcej urządzeń, ale wtedy wykrywanie, które urządzenie zgłasza przerwanie spada na oprogramowanie. Nie zawsze dzielenie przerwań działało poprawnie.

Rys. 20. Schemat przydziału 16 linii przerwań PC

Począwszy od procesora Pentium 4, pojawiła się nowa metoda obsługi przerwań. Zastosowano zaawansowany kontroler obsługi przerwań (APIC – ang. Advanced Programable Interrupt Controller). W założeniu miał on umożliwić obsługę systemów wieloprocesorowych i później z procesorami wielordzeniowymi, gdzie różne procesory, czy rdzenie mogą obsłużyć przerwanie (Rys.21).

Rys. 21. Zaawansowany kontroler obsługi przerwań

W systemie z APIC obsługa przerwań jest realizowana przez I/O APIC znajdujący się na chipsecie. Do tego układu podłączone są urządzenia. Każdy procesor/rdzeń ma wbudowany układ „local APIC”. Układy „local APIC” są połączone specjalną magistralą z I/O APIC. I/O APIC rozdziela przerwania na poszczególne procesory/rdzenie. W systemie jednoprocesorowym APIC może symulować działanie „starego” układu obsługi przerwań (2x8259). Wraz z APIC dodano możliwość obsługi ośmiu dodatkowych przerwań. W sumie jest ich 24 (~IRQ0 do ~IRQ24). Mogło by się wydawać, że to duża liczba. Jednak liczba urządzeń wymagająca przerwań też znacznie się zwiększyła. Nadal pozostał do rozwiązania problem małej liczby przerwań.

Większość numerów przerwań jest przyporządkowywana automatycznie w trakcie startu systemu operacyjnego. Należy zaznaczyć, że przyporządkowanie przerwań jest zależne od sprzętu. Może być też ustanowione przez konfigurację sprzętową, czasem  jest ustawiane ręcznie, czasem programowo. Magistrala PCI ustawia przerwania w czasie startu systemu. Niektóre przerwania są stale przyporządkowane – związane z architekturą systemu (IRQ0: timer, IRQ2: kaskada do 8259A). Dwa urządzenia, które nie używają przerwania w tym samym czasie mogą je dzielić, nawet jeśli nie obsługują dzielenia przerwań.

6. Sytuacje wyjątkowe

Inną klasą zdarzeń, która jest obsługiwana w sposób bardzo podobny do przerwań są sytuacje wyjątkowe. Jak sama nazwa wskazuje, sytuacje wyjątkowe wskazują wystąpienie pewnego zdarzenia w systemie, które musi być obsłużone. Mogą to być sytuacje krytyczne, np. błąd sprzętowy, ale również częste i normalne sytuacje podczas pracy komputera, jak np. błąd braku strony, przy stosowaniu pamięci wirtualnej. Generalnie rozróżniamy następujące typy sytuacji wyjątkowych:

• Wykryte na etapie wykonywania instrukcji przez procesor (dzielenie przez zero, page fault, general protection …).
• Generowane przez oprogramowanie (INTO - call to interrupt if overflow, INT 3 - breakpoint, INT n).
• Błędy sprzętowe (ang. machine check exceptions).

Inną klasyfikację sytuacji wyjątkowych można podać ze względu na sposób ich obsługi:

• Błędy (ang. Faults) – wznowienie działania programu następuje przez ponowienie wykonania instrukcji generującej sytuację wyjątkową.
• Pułapki (ang. Traps) – w tym przypadku wznowienie wykonywania programu następuje od instrukcji następnej po tej wywołującej sytuację wyjątkową.
• Porzucenia (ang. Aborts) – są nastawione na usługę poważnych błędów, w tym przypadku następuje zatrzymanie działania systemu, a na ekranie powinniśmy zobaczyć, co spowodowało błąd.

7. Obsługa przerwań i sytuacji wyjątkowych, wektor przerwań

Przerwania sprzętowe i sytuacje wyjątkowe są obsługiwane poprzez tablicę przerwań IDT (ang. Interrupt Descriptor Table) (Rys.22). Tablica ta zawiera indeksowane komórki (0-255), które opisują sposób obsługi konkretnych przerwań. Indeks do tej tablicy nazywany jest wektorem przerwań. Przerwania sprzętowe mają indeksy powyżej 32. Indeksy poniżej 32 są zarezerwowane dla przerwań niemaskowalnych i sytuacji wyjątkowych. Numery przerwań maskowalnych są przyporządkowywane według potrzeb. Tablica wektorów przerwań w trybie chronionym procesora jest przedstawiona w tabeli 3.

Rys. 22. Tablica przerwań

Tabela 3. Tablica wektorów przerwań w trybie chronionym procesora

Wykonanie (obsługa) przerwania zachodzi w następujący sposób. Każde przerwanie musi być obsłużone przez specjalny program. Tablica Interrupt Descriptor Table (IDT) zawiera deskryptory tych programów (określone przez numer przerwania). Sprzęt lokalizuje odpowiedni deskryptor. Zachodzi zmiana kontekstu, licznik programów, wskaźnik stosu, stan CPU i pamięci dla przerywanego programu są odkładane na stosie. Uruchamiany jest program obsługi przerwania.

8. Przerwania zgłaszane komunikatem

Już magistrala PCI (standard PCI 2.2) umożliwiała alternatywną metodę zgłaszania przerwań. Zamiast wystawiania sygnału na odpowiedni pin układu, przerwania są zgłaszane w pełni programowo. Są to przerwania zgłaszane komunikatem MSI (ang. Message Signaled Interrupts). Metoda ta polega na zapisie odpowiedniego słowa w przestrzeni adresowej magistrali PCI (czyli trzeba wpisać odpowiednią informację do przeznaczonego do tego celu rejestru). Metoda ta jest bardzo wygodna. Przede wszystkim znika ograniczenie liczby przerwań do 255 (liczba wpisów w tablicy przerwań). Poza tym każdy blok funkcjonalny urządzenia PCI może mieć własny sygnał przerwania, czyli możemy przeznaczyć wiele przerwań dla jednego urządzenia. W tym przypadku nie jest konieczne dzielenie przerwań.

W momencie wprowadzenia magistrali PCI Express (PCI 3.0) przerwania zgłaszane komunikatem stały się niejako standardem. System został też rozszerzony (teraz nazywa się MSI-X). W przypadku PCI 2.2 komunikat składa się z adresu i 16-bitowej wartości. W przypadku PCI 3.0 komunikat składa się z adresu i 32-bitowej wartości. Zakres możliwych do przydzielenia przerwań jest bardzo duży (pojedyncze urządzenie MSI-X może użyć maksymalnie 2048 MSI),  przerwania przydzielane są od 0xFFFFFFFE (4294967294) przez 0xFFFFFFFD, …C, …B itd.).

9. Przestrzeń adresowa I/O

Przestrzeń adresowa wejścia-wyjścia I/O (tzw. porty) tworzy zupełnie odmienną przestrzeń adresową niż pamięć RAM. Porty umożliwiają komunikację pomiędzy oprogramowaniem i sprzętem (urządzenia I/O). Porty umożliwiają transmisję danych, a także sterowanie stanem urządzeń. Mogą być jednokierunkowe bądź dwukierunkowe. Dwa urządzenia nie mogą wykorzystywać tych samych portów. Porty są ściśle związane z architekturą systemu komputerowego. W przypadku architektury PC zazwyczaj mamy do dyspozycji 0000-FFFF (65535) portów I/O, z czego porty 00-FF są wykorzystywane przez płytę główną, a 100H-FFFF przez urządzenia. Przykładowo dla karty sieciowej przyporządkowanie przerwań i adresów I/O może wyglądać następująco:

• IRQ 09
• Adres we/wy 9800-987F
• Zakres pamięci E000 000 – E000 007F (32-bit)

lub

• Zakres pamięci 0000 0000 E000 000 – 0000 0000 E000 007F (64-bit)

Warto zwrócić uwagę na zakres pamięci. Są to adresy w przestrzeni pamięci RAM, a jednak odnoszą się do portów urządzenia. Jest to możliwe dzięki mapowaniu portów I/O (ang. memory-mapped I/O) na adresy pamięci RAM (Rys. 23). W tym przypadku program może zapisywać do pamięci urządzenia dane w taki sam sposób jak do pamięci operacyjnej. Jeśli mapowanie nie jest stosowane, jedynym sposobem dostępu do pamięci urządzenia jest użycie specjalnych instrukcji: IN, OUT, INS, OUTS.

Rys. 23. Przestrzeń adresowa I/O

10. Bezpośredni dostęp do pamięci (DMA)

Użycie portów do komunikacji z urządzeniem, czyli programowanego wejścia/wyjścia (PIO) powoduje duże wykorzystanie procesora. Istnieje inna metoda, która pozwala transferować znaczne ilości danych pomiędzy urządzeniem i pamięcią RAM ze znikomym wykorzystaniem procesora. Jest to właśnie bezpośredni dostęp do pamięci (DMA – ang. Direct Memory Access) (Rys.24).

Rys. 24. Idea DMA

W rozwiązaniu tym jest wykorzystywany specjalny kontroler DMA, który organizuje transfer danych pomiędzy urządzeniem i pamięcią bez udziału procesora. Podczas transferu danych procesor jest jednak odcięty od pamięci RAM. Historycznie kontroler DMA był montowany na płycie głównej.  Jest to tzw. standardowe DMA („third party”). Rozwiązanie to jest przestarzałe (związane z magistralą ISA) i obecnie w zasadzie nie jest wykorzystywane. Obecne urządzenia (szczególnie dyski twarde, karty graficzne) mają wbudowane kontrolery DMA. Wykorzystują one tzw. bus mastering („first party” DMA). Urządzenie peryferyjne wykonujące transfer DMA przejmuje kontrolę nad magistralą systemową (PCI, PCI Express). Jest ono wtedy jedynym sterownikiem kontrolującym magistralę (bus mastering). Następnie układ DMA urządzenia zostaje odpowiednio zaprogramowany (podawane są informacje: odczyt czy zapis, adres urządzenia I/O, adres początkowy pamięci do odczytu lub zapisu, liczba słów do transmisji) i jest realizowany transfer danych. Po przesłaniu danych urządzenie zwalnia magistralę.