MIMINF:Systemy operacyjne
Wykład (30 godzin) + ćwiczenia (30 godzin) + laboratorium (30 godzin)
Opis
Celem zajęć jest przedstawienie roli i zadań systemu operacyjnego w oprogramowaniu komputera oraz omówienie zagadnień realizacji — algorytmów, struktur danych i ich implementacji. Prezentowane są techniki zarządzania podstawowymi zasobami sprzętowymi komputera — procesorem, pamięcią operacyjną oraz wirtualną i urządzeniami wejścia-wyjścia — oraz ich wpływ na efektywność funkcjonowania systemu jako całości. W kontekście zarządzania zasobami wprowadzana jest również koncepcja procesu oraz wątku. Omawiana jest koncepcja pliku oraz realizacja systemu plików — warstwy logicznej i fizycznej — wraz z przykładami konkretnych implementacji. Osobnym zagadnieniem, integralnie związanym z realizacją systemu operacyjnego, jest współbieżność i synchronizacja. W kontekście podstawowych problemów synchronizacji, takich jak wzajemne wykluczanie oraz ograniczone buforowanie, omawiane są podejścia do synchronizacji procesów, bazujące na współdzielonych zmiennych, podejścia wspierane przez system operacyjny — semafory, oraz podejścia wymagające wsparcia w konstrukcjach programowych języków wysokopoziomowych — monitory, regiony krytyczne i spotkania (ang. rendezvous). Ilustruje się zastosowanie omawianych mechanizmów do rozwiązywania klasycznych problemów synchronizacji (problem producenta-konsumenta, czytelników i pisarzy, pięciu filozofów itp.). Omawiany jest również problem wynikający z dostępu współbieżnych procesów do zasobów — zakleszczenie oraz podejścia do rozwiązywania tego problemu. Ważnym elementem zajęć jest ilustracja omawianych zagadnień na przykładzie współczesnych systemów operacyjnych.
Laboratorium jest poświęcone aspektom praktycznym korzystania z systemów operacyjnych, administrowania systemami, tworzenia pakietów z oprogramowaniem, rekompilowania i konfigurowania jądra systemu operacyjnego, a także robienia zmian w jądrze. Ponadto studenci nabywają umiejętność programowania współbieżnego z zastosowaniem wielowątkowości i różnych mechanizmów synchronizacji procesów.
Sylabus
Autorzy
- Janina Mincer Daszkiewicz
Wymagania wstępne
- Wstęp do programowania
- Architektura systemów komputerowych
- Język programowania C
Zawartość
Wykład
- Pierwsze dwa moduły (4 godz.) stanowią ogólne wprowadzenie, obejmujące 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,
- koncepcja stanu procesu, przejść między stanami, kontekstu, trybu pracy procesora, wsparcia sprzętowego dla systemów operacyjnych.
- Kolejne dwa moduły (6 godz.) dotyczą zagadnień przetwarzania współbieżnego i synchronizacji procesów. W pierwszym z modułów zagadnienia te są omawiane 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,
- monitory i regiony krytyczne.
Przykłady zastosowania wymienionych mechanizmów pokazuje się w rozwiązaniach klasycznych problemów synchronizacji: producenta i konsumenta, czytelników i pisarzy, pięciu filozofów.
- 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 dyskutowane są również zagadnienia implementacyjne. Drugi moduł dotyczy rozwiązań w zakresie szeregowania zadań (procesów lub wątków) we współczesnych systemach operacyjnych.
- Następny moduł (3 godz.) poświęcono zakleszczeniu — opisaniu samego zjawiska i omówieniu metod przeciwdziałania. Przedstawiane są: 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, to omawiane są następujące podejścia: zapobieganie zakleszczeniom, unikanie zakleszczeń (w tym algorytm bankiera), detekcja stanu zakleszczenia i krótko zasady usuwania.
- W kolejnych dwóch modułach (5 godz.) omawiane są zagadnienia zarządzania pamięcią. Pierwszy z modułów dotyczy głównie zarządzania pamięcią operacyjną i obejmuje: podział pamięci, przydział pamięci oraz translację 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. Mowa jest również o obrazie procesu tworzonym przez kompilator oraz przestrzeni adresowej procesu. 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. Część modułu poświęcona jest algorytmom wymiany — ich klasyfikacji, działaniu, zastosowaniom oraz zagadnieniom implementacyjnym. Omawiane są także przykładowe realizacje pamięci wirtualnej we współczesnych systemach operacyjnych, w tym stosowane struktury danych, mechanizm tworzenia procesu, współdzielenie przez procesy struktur danych i przestrzeni adresowej.
- 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ł obejmuje prezentację wybranych przykładów konkretnych implementacji systemu plików.
- Ostatni 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.
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ą:
o poruszanie się w systemie — logowanie, pomoc systemowa (man), programy pomocnicze (whatis, whereis, apropos),
o 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),
o 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),
o potoki i filtry — przekierowanie strumieni standardowych, potoki z użyciem filtrów: cat, head, tail, grep, wc, tr, cut, sort, uniq,
o 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:
o obsługi plików — tworzenie i dostęp do plików (creat, open, close, read, write),
o obsługi procesów — tworzenie procesów, uruchamianie programów (fork, exec, exit, wait),
o komunikacji strumieniowej za pośrednictwem łączy — tworzenie potoków i zasady ich użycia w komunikacji między procesami (pipe),
o 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),
o 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
- A. Silberschatz, P. Galvin, Podstawy systemów operacyjnych (wydanie trzecie, rozszerzone), WNT, 2000.
- G. Coulouris, J. Dollimore, T. Kindberg, Systemy rozproszone, podstawy i projektowanie, WNT, 1998.
