Systemy operacyjne

Opis

• Jerzy Brzeziński — Politechnika Poznańska
• Dariusz Wawrzyniak — Politechnika Poznańska

• Wstęp do programowania
• Umiejętność programowania w języku C
• Elementarna wiedza z zakresu architektury komputerów

• Pierwsze dwa moduły (4 godz.) są ogólnym wprowadzeniem, obejmującym takie zagadnienia jak:
• rola i zadania systemu operacyjnego,
• umiejscowienie systemu operacyjnego (w szczególności jądra) w strukturze oprogramowania systemu komputerowego,
• klasyfikacja systemów operacyjnych,
• ogólna zasada działania systemu operacyjnego (sposób przekazywania sterowania do programu jądra),
• koncepcja procesu, zasobu i wątku.
• Kolejne dwa moduły (4 godz.) dotyczą planowania przydziału procesora, czyli szeregowania zadań. Pierwszy z modułów rozpoczyna się od omówienia ogólnej koncepcji planowania. Następnie przedstawione są algorytmy planowania z wywłaszczaniem i bez wywłaszczeń oraz kryteria ich oceny. Poruszany jest też problem szeregowania procesów ograniczonych wejściem-wyjściem. Krótko przedyskutowane są również zagadnienia implementacyjne. Drugi moduł prezentuje rozwiązania w zakresie szeregowania zadań (procesów lub wątków) we współczesnych systemach operacyjnych, czyli tradycyjnym systemie UNIX, systemie Linux oraz systemie Windows.
• W kolejnych dwóch modułach (5 godz.) omawiane są zagadnienia zarządzania pamięcią. Pierwszy z modułów koncentruje się na zarządzaniu pamięcią operacyjną, obejmującym: podział pamięci, przydział pamięci oraz transformację adresów, w szczególności w systemie pamięci stronicowanej i segmentowanej. Przy tej okazji omawiane jest zjawisko fragmentacji wewnętrznej i zewnętrznej, a także poruszany jest problem ochrony oraz współdzielenia pamięci. Kilka slajdów poświęcono również tworzeniu obrazu procesu w pamięci. Drugi moduł dotyczy realizacji pamięci wirtualnej. Omawiane jest zjawisko błędu strony, jego obsługa i podstawowe problemy z tym związane, tj. problem wymiany stron i problem wznawiania rozkazów. Większa część modułu poświęcona jest algorytmom wymiany — ich klasyfikacji, działaniu, zastosowaniom oraz zagadnieniom implementacyjnym.
• Siódmy moduł dotyczy zarządzania urządzeniami wejścia-wyjścia. Moduł rozpoczyna się od przedstawienia klasyfikacji urządzeń wejścia-wyjścia według różnych kryteriów. Następnie omawiana jest struktura mechanizmu obsługi urządzeń wejścia-wyjścia oraz sposoby interakcji jednostki centralnej z takimi urządzeniami. Poruszane są również zagadnienia poprawy efektywności pracy urządzeń poprzez buforowanie i spooling. Na końcu pojawia się wzmianka o tzw. wirtualnym wejściu-wyjściu, które jest wprowadzeniem do następnego bloku modułów, obejmującego system plików.
• W następnych trzech modułach (6 godz.) omawiany jest system plików. Pierwszy moduł dotyczy ujęcia systemu plików od strony logicznej, czyli abstrakcyjnego obrazu informacji, przechowywanej i udostępnianej przez system. W zakresie tym mieści się: pojęcie pliku, pojęcie struktury i typu pliku, organizacja logiczna systemu plików (strefy, katalogi), metody dostępu do pliku oraz interfejs operacji plikowych. W drugim module omawiana jest organizacja fizyczna systemu plików, obejmująca przydział bloków dyskowych, zarządzanie wolną przestrzenią oraz implementację katalogu. W module tym poruszane są również zagadnienia przechowywania podręcznego i wynikające stąd ryzyko utraty integralności oraz kwestie synchronizacji współbieżnego dostępu do pliku. Ostatni moduł prezentuje wybrane przykłady konkretnych implementacji systemu plików: CP/M, DOS, ISO 9660, UNIX, NTFS.
• Kolejne dwa moduły (5 godz.) poruszają zagadnienia przetwarzania współbieżnego i synchronizacji procesów. Pierwszy z modułów omawia te zagadnienia na poziomie architektury, bez istotnego wsparcia ze strony systemu operacyjnego (poza realizacją koncepcji procesu). W zakresie tego modułu mieszczą się więc takie zagadnienia, jak: pojęcie instrukcji atomowej oraz przeplotu, istota synchronizacji oraz poprawność programów współbieżnych (bezpieczeństwo i żywotność). Pojęcia te ilustrowane są przykładowymi rozwiązaniami problemu wzajemnego wykluczania, obejmującymi algorytm Petersona, algorytm Lamporta oraz rozwiązania opierające się na instrukcjach atomowych test&set i exchange. Drugi z modułów obejmuje mechanizmy synchronizacji wspierane przez system operacyjny lub język programowania wysokiego poziomu:
• semafory — ich klasyfikację i implementację,
• mechanizmy standardu POSIX — rygle i zmienne warunkowe,
• monitory i regiony krytyczne.
• 
  

• Ostatnie dwa moduły (4 godz.) poświęcono zakleszczeniu — opisaniu samego zjawiska (pierwszy moduł) i omówieniu metod przeciwdziałania (drugi moduł). Przedstawione zostały: warunki konieczne zakleszczenia w kontekście zasobów odzyskiwalnych i nieodzyskiwalnych, definicja zakleszczenia, opis stanu systemu na potrzeby analizy zakleszczenia — graf przydziału i graf oczekiwania oraz ich specyficzne własności. Jeżeli chodzi o przeciwdziałanie, omówione zostały następujące podejścia: zapobieganie zakleszczeniom, unikanie zakleszczeń (w tym algorytm bankiera), detekcja stanu zakleszczenia i krótko zasady usuwania.

Laboratoria

• Pierwszy moduł zajęć laboratoryjnych (1 godz.) poświęcono instalacji systemu operacyjnego Linux wraz z odpowiednim przygotowaniem partycji dysku oraz konfiguracją mechanizmu ładowania (dual boot).
• Pierwsza z zasadniczych części zajęć (12 godz.) dotyczy użytkowania uniksopodobnego systemu operacyjnego. Celem tej części jest opanowanie umiejętności użytkowania systemu poprzez wydawanie poleceń na konsoli jako alternatywy dla intuicyjnego graficznego interfejsu użytkownika. Zaletą takiego podejścia jest możliwość automatyzacji pewnych zadań w trybie wsadowym, dlatego większą część czasu poświęcono na przetwarzanie potokowe oraz tworzenie skryptów powłoki. Poszczególne zajęcia obejmują:
• poruszanie się w systemie — logowanie, pomoc systemowa (man), programy pomocnicze (whatis, whereis, apropos),
• obsługę plików i katalogów — identyfikacja plików w drzewie katalogów (pwd, ls, cd), kopiowanie i usuwanie plików (mv, rm, cp, ln), lokalizowanie plików (find, locate), tworzenie i usuwanie katalogów (mkdir, rmdir),
• obsługę procesów — tworzenie wykazu procesów (ps, pstree, pgrep), zmiana priorytetu (nice, renice), przekazywanie sygnałów (kill), obsługa procesów pierwszo- i drugoplanowych (&, fg, bg),
• potoki i filtry — przekierowanie strumieni standardowych, potoki z użyciem filtrów: cat, head, tail, grep, wc, tr, cut, sort, uniq,
• skrypty powłoki — zmienne lokalne i środowiskowe powłoki, tworzenie skryptów i przekazywanie parametrów, konstrukcje strukturalne w skyptach (pętle i instrukcje warunkowe).
• Druga część (17 godz.) dotyczy dostępu do usług jądra uniksopodobnego systemu operacyjnego w programie niskopoziomowym. Celem zajęć jest poznanie zasad korzystania z interfejsu jądra dla programów aplikacyjnych (API) w języku C oraz nabycie umiejętności użycia wybranych funkcji jądra w zakresie:
• obsługi plików — tworzenie i dostęp do plików (creat, open, close, read, write),
• obsługi procesów — tworzenie procesów, uruchamianie programów (fork, exec, exit, wait),
• komunikacji strumieniowej za pośrednictwem łączy — tworzenie potoków i zasady ich użycia w komunikacji między procesami (pipe),
• obsługi wątków — tworzenie i synchronizacja wątków (pthread_create, pthread_exit, pthread_join, pthread_mutex_lock, pthread_mutex_unlock, pthread_mutex_trylock, pthread_cond_wait, pthread_cond_signal, pthread_cond_broadcast),
• mechanizmów grupy IPC:
• kolejek komunikatów (msgget, msgsnd, msgrcv, msgctl),
• pamięci współdzielonej (shmget, shmat, shmdt, shmctl),
• semaforów (semget, semop, semctl).

Funkcjonowanie omawianych mechanizmów ilustrowane jest krótkimi przykładami programów. Niektóre z nich mają charakter praktyczny, inne mają tylko demonstrować sposób i skutki użycia określonej funkcji lub mechanizmu.

Literatura

Literatura podstawowa

1. A. Silberschatz, J.L. Peterson, G. Gagne, Podstawy systemów operacyjnych. WNT, Warszawa 2005.
2. G. Nutt, Operating Systems. A Modern Perspective. wydanie 2, Addison Wesley Longman, Inc., 2002.
3. W. Stallings, Systemy operacyjne. Robomatic, Wrocław 2004.
4. A. S. Tanenbaum, Modern Operating Systems. wydanie 2, Prentice-Hall Inc., 2001.
5. C. Sobaniec, System operacyjny Linux — przewodnik użytkownika. Nakom, Poznań 2002.
6. J. Marczyński, UNIX użytkowanie i administrowanie. wydanie 2, Helion, Gliwice 2000.
7. W. R. Stevens, Programowania w środowisku systemu UNIX. WNT, Warszawa 2002.
8. J. S. Gray, Komunikacja między procesami w Unixie. ReadMe, Warszawa 1998.
9. M. J. Rochkind, Programowanie w systemie Unix dla zaawansowanych. WNT, Warszawa 1993.

1. L. Bic, A. C. Shaw, The Logical Design of Operating Systems. Prentice-Hall Inc., 1988.
2. M. J. Bach, Budowa systemu operacyjnego Unix®. WNT, Warszawa 1995.
3. B. Goodheart, J. Cox, Sekrety magicznego ogrodu. UNIX® System V Wersja 4 od środka. WNT, Warszawa 2001.
4. U. Vahalia, Jądro systemu UNIX®. Nowe horyzonty. WNT, Warszawa 2001.
5. D. A. Solomon, M. E. Russinovich, Microsoft Windows® 2000 od środka. Helion, Gliwice 2003.
6. R. Lowe, Kernel Linux. Przewodnik programisty. Helion, Gliwice 2004.
7. P. Silvester, System operacyjny Unix™. WNT, Warszawa 1990.
8. Z. Królikowski, M. Sajkowski, UNIX dla początkujących i zaawansowanych. Nakom, Poznań 1996.
9. Z. Guźlewski, T. Weiss. Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT, Warszawa 1993.
10. R. W. Stevens, Programowanie zastosowań sieciowych w systemie Unix. WNT, Warszawa 1995.
11. M. Gabassi, B. Dupouy, Przetwarzanie rozproszone w systemie Unix. Lupus, Warszawa 1995.

1. Wstęp (2 godz.)
• Treść wykładu
1. Definicja systemu operacyjnego
2. Miejsce systemu operacyjnego w organizacji oprogramowania komputera
3. Ogólna struktura systemu operacyjnego
4. Zadania systemu operacyjnego
5. Klasyfikacja systemów operacyjnych
6. Zasada działania systemu operacyjnego
• Najważniejsze pojęcia i zagadnienia: wielowarstwowa organizacja oprogramowania komputera, system operacyjny (wsadowy, interaktywny, wielozadaniowy), jądro systemu operacyjnego, cykl rozkazowy, przerwanie (zewnętrzne, programowe, diagnostyczne), pierścienie ochrony, ochrona pamięci.
2. Procesy, zasoby i wątki (2 godz.)
• Treść wykładu
1. Koncepcja procesu i zasobu
2. Zarządca procesów i zarządca zasobu
3. Struktury danych na potrzeby zarządzania procesami i zasobami
4. Klasyfikacja zasobów
5. Stany procesu i cykl zmian stanów
6. Kolejki procesów
7. Przełączanie kontesktu
8. Planiści: krótkoterminowy, śrdednioterminowy i długoterminowy
9. Wątki
• Najważniejsze pojęcia i zagadnienia: proces, kontekst procesu, deskryptor procesu, zarządca procesów, stan procesu, kolejka procesów, planista, zasób (odzyskiwalny, nieodzyskiwalny, wywłaszczalny, niewywłaszczalny), deskryptor zasobu, zarządca zasobu, wątek.
3. Planowanie przydziału procesora (2 godz.)
   
• Treść wykładu
1. Ogólna koncepcja planowania przydziału procesora
2. Komponenty jądra na potrzeby planowania przydziału procesora
3. Planowanie wywłaszczające i niewywłaszczające
4. Funkcja priorytetu i jej parametry
5. Kryteria oceny algorytmów planowania przydziału procesora
6. Przykłady algorytmów planowania przydziału procesora
7. Implementacja algorytmów planowania
• Najważniejsze pojęcia i zagadnienia: priorytet procesu, wywłaszczanie, planowanie priorytetowe, planowanie rotacyjne, wykorzystanie procesora, przepustowość, czas oczekiwania, czes reakcji (odpowiedzi), czas cyklu przetwarzania.
4. Przykłady implementacji planowania przydziału procesora (2 godz.)
• Treść wykładu
1. Planowanie przydziału procesora w tradycyjnym systemie Unix
2. Planowanie przydziału procesora w systemie Linux
3. Planowanie przydziału procesora w systemie Windows
• Najważniejsze pojęcia i zagadnienia: przeliczanie priorytetów, struktury danych do obsługi kolejki procesów gotowych, przeciwdziałanie głodzeniu procesów w dostępie do procesora.
5. Zarządzanie pamięcią operacyjną (2 godz.)
   
• Treść wykładu
1. Pamięć a przestrzeń adresowa
2. Podział i przydział pamięci
3. Fragmentacja
4. Obraz procesu w pamięci
5. Problem ochrony i współdzielenia pamięci
6. Stronicowanie i segmentacja
• Najważniejsze pojęcia i zagadnienia: hierachia pamięci, przestrzeń adresowa, adres logiczny i fizyczny, wiązanie adresu, transformacja adresu, fragmentacja pamięci (zewnętrzna i wewnętrzna), strona pamięci, segment pamięci.
6. Pamięć wirtualna (3 godz.)
   
• Treść wykładu
1. Stronicowanie na żądanie
2. Błąd strony i jego obsługa
3. Problem zastępowania i wznawiania rozkazów
4. Algorytmy wymiany i ich klasyfikacja
5. Anomalia Belady'ego
6. Problemy implementacji algorytmów wymiany
• Najważniejsze pojęcia i zagadnienia: stronicowanie na żądanie, bit poprawności, błąd strony, wymiana stron, problem wznawiania rozkazów, bit modyfikacji, bit odniesienia, algorytm wymiany, zbiór roboczy, wstępne sprowadzanie, efektywność działania systemu pamięci wirtualnej.
7. Urządzenia wejścia-wyjścia (2 godz.)
   
• Treść wykładu
1. Właściwości i klasyfikacja urządzeń wejścia-wyjścia
2. Struktura mechanizmu wejścia-wyjścia
3. Interakcja jednostki centralnej z urządzeniami wejścia-wyjścia
• odpytywanie
• sterowanie przerwaniami
• bezpośredni dostęp do pamięci
4. Buforowanie, spooling i przechowywanie podręczne
5. Wirtualne wejście-wyjście
• Najważniejsze pojęcia i zagadnienia: sterownik, moduł sterujący, odpytywanie, przerwania od urządzeń, bezpośredni dostęp do pamięci, buforowanie, spooling, przechowywanie podręczne.
8. System plików — warstwa logiczna (2 godz.)
   
• Treść wykładu
1. Pojęcie pliku i jego atrybuty
2. Atrybuty plik
3. Logiczny i fizyczny obraz pliku
4. Metody dostępu do pliku
5. Podstawowe operacje na plikach
6. Uniksowy interfejs dostępu do pliku
7. Logiczna organizacja systemu plików
• Najważniejsze pojęcia i zagadnienia: plik, typ pliku, struktura pliku, dostęp sekwencyjny, dostęp bezpośredni, dostęp indeksowy, strefa, katalog.
9. System plików — warstwa fizyczna (2 godz.)
   
• Treść wykładu
1. Fizyczna organizacja systemu plików na dysku
• przydział miejsca na dysku
• zarządzanie wolną przestrzenią
• implementacja katalogu
2. Przechowywanie podręczne w systemie plików
3. Integralność systemu plików
4. Semantyka spójności i synchronizacja współbieżnego dostępu do pliku
• Najważniejsze pojęcia i zagadnienia: przydział ciągły, przydział listowy, przydział indeksowy, FAT, integralność systemu plików.
10. System plików — przykłady implementacji (2 godz.)
• Treść wykładu
1. Systemu plików CP/M
2. Systemu plików FAT
3. Systemu plików ISO 9660
4. Systemu plików Unix
5. Systemu plików NTFS
• Najważniejsze pojęcia i zagadnienia: blok kontrolny pliku FCB, FAT16, FAT32, i-węzeł, główna tablica plików MFT.
11. Współbieżność i synchronizacja procesów (2 godz.)
• Treść wykładu
1. Istota przetwarzania współbieżnego i synchronizacji
2. Poprawność programów współbieżnych
3. Klasyfikacja mechanizmów synchronizacji
• mechanizmy operate na zmiennych współdzielonych
• mechanizmy wspierane przez system operacyjny
• mechanizmy ze wsparciem językowym
4. Główne problemy synchronizacji procesów (wzajemne wykluczanie, ograniczone buforowanie)
5. Definicja problemu wzajemnego wykluczania (sekcji krytycznej)
6. Schemat algorytmu wzajemnego wykluczania
7. Klasyczne algorytmy wzajemnego wykluczania oparte o zapis/odczyt zmiennych współdzielonych
• algorytm Petersona
• algorytm Lamporta
8. Rozwiązanie problemu wzajemnego wykluczania w oparciu o instrukcje test&set oraz exchange
• Najważniejsze pojęcia i zagadnienia: instrukcja atomowa, przeplot, bezpieczeństwo, żywotność, uczciwość, wzajemne wykluczanie (sekcja krytyczna), ograniczone buforowanie, poprawność algorytmu wzajmnego wykluczania (bezpieczeństwo, postęp, ograniczone czekanie), aktywne czekanie, wsparcie sprzętowe w rozwiązaniu problemu wzajemnego wykluczania.
12. Systemowe mechanizmy synchronizacji procesów (3 godz.)
• Treść wykładu
1. Definicja i klasyfikacja semaforów
2. Implementacja semaforów
3. Zastosowanie semaforów do rozwiązania głównych problemów synchronizacji procesów
4. Mechanizmy synchronizacji wątków standardu POSIX
• zamki (rygle, ang. locks, mutex locks)
• zmienne warunkowe (ang. conditionals)
5. Monitory (definicja i zasada działania)
6. Zastosowanie monitorów do rozwiązania problemu ograniczonego buforowania
7. Regiony krytyczne
8. Zastosowanie regionów krytycznych do rozwiązania problemu ograniczonego buforowania
• Najważniejsze pojęcia i zagadnienia: semafor ogólny, semafor binarny, podnoszenie i opuszczanie semafora, zamek, zmienna warunkowa, monitor, zmienna warunkowa w monitorze, region krytyczny, warunkowy region krytyczny.
13. Problem zakleszczenia (2 godz.)
    
• Treść wykładu
1. Definicja problemu zakleszczenia
2. Warunki konieczne wystąpienia zakleszczenia
3. Graf przydziału zasobów i graf oczekiwania oraz ich własności
• Najważniejsze pojęcia i zagadnienia: stan osiągalny, zablokowanie procesu, warunki konieczne wystąpienia zakleszczenia, graf przydziału zasobów, graf oczekiwania.
14. Przeciwdziałanie zakleszczeniu (2 godz.)
    
• Treść wykładu
1. Rozwiązywanie problemu zakleszczenia
• zapobieganie zakleszczeniom
• unikanie zkleszczeń
• detekcja i likwidacja zakleszczeń
2. Podejście hybrydowe do rozwiązywania problemu zakleszczenia
• Najważniejsze pojęcia i zagadnienia: zapobieganie zakleszczeniom, unikanie zakleszczeń, algorytm Bankiera, likwidacja zakleszczenia (usuwanie procesów, wywłaszczanie zasobów)