Informatyka MIMUW

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.

Laboratorium

• Pierwszy moduł zajęć laboratoryjnych (4 godz.) poświęcono:
  • instalacji systemu operacyjnego Linux wraz z odpowiednim przygotowaniem partycji dysku oraz konfiguracją mechanizmu ładowania (dual boot),
  • podstawom poruszania się w środowisku systemu Linux i uruchamiania programów w C. Obejmuje to również korzystanie z pomocy systemowej (man), obsługę procesów, plików i katalogów, sygnałów, wywoływanie funkcji systemowych z programu w C.

• Drugi moduł (12 godz.) obejmuje wieloprocesowe i wielowątkowe programowanie współbieżne, z użyciem różnych mechanizmów synchronizacji. Celem jest nabycie przez studentów umiejętności praktycznego rozwiązywania problemów synchronizacji procesów i korzystania z funkcji systemowych. Kolejne zajęcia dotyczą następujących zagadnień:
  • obsługa procesów - tworzenie procesów, uruchamianie procesów (fork, exec, wait),
  • komunikacja strumieniowa za pośrednictwem łączy nienazwanych - tworzenie potoków i zasady ich użycia w komunikacji między procesami (pipe),
  • mechanizmy IPC - semafory (semget, semop, semctl),
  • mechanizmy IPC - segmenty pamięci dzielonej (shmget, shmat, shmdt, shmctl),
  • obsługa 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),
  • obsługa sygnałów - wysyłanie sygnałów, instalowanie procedury obsługi sygnału, sygnały jako mechanizm komunikacji między procesami.

• Trzeci moduł (6 godz.) obejmuje zagadnienia z zakresu administrowania systemami operacyjnymi, w tym:
  • pisanie skryptów interpretatora poleceń — zmienne lokalne i środowiskowe, tworzenie skryptów i przekazywanie parametrów, konstrukcje strukturalne w skryptach (pętle i instrukcje warunkowe),
  • analiza budowy interpretatora poleceń,
  • śledzenie dzienników systemowych, administrowanie przestrzenią dyskową i systemami plików, zarządzanie kontami użytkowników,
  • tworzenie pakietów z oprogramowania (rpm).

• Czwarty moduł (8 godz.) dotyczy zagadnień z zakresu budowy i programowania systemów operacyjnych:
  • konfiguracja i kompilacja jądra,
  • pisanie modułów,
  • pisanie podprogramów obsługi urządzeń,
  • system plików proc, pisanie funkcji systemowych.

Literatura podstawowa

1. A. Silberschatz, P. Galvin, G. Gagne, Podstawy systemów operacyjnych, WNT, 2006.
2. D.P. Bovet, M. Ceasti, Linux Kernel, O'Reilly, November 2005.
3. R. Love, Linux Kernel Development, Novell Press, 2005.
4. D. A. Solomon, M. E. Russinovich, Microsoft Windows 2000 od środka. Helion, 2003.
5. M. Ben-Ari, Podstawy programowania współbieżnego i rozproszonego, WNT, 1996.
6. Z. Gruźlewski, Z. Weiss, Programowanie współbieżne i rozproszone w przykładach i zadaniach, WNT, 1993.
7. W. Richard Stevens, Programowanie w środowisku systemu UNIX, WNT, 2002.
8. M. Rochkind, Programowanie w systemie Unix dla zaawansowanych, WNT, 1993.
9. E. Nemeth, G. Snyder, S. Seebass, T.R. Hein, Przewodnik administratora systemu Unix, WNT, 1998.

Literatura uzupełniająca

1. W. Stallings, Operating Systems: Internals and Design Principles, Prentice-Hall, 2002.
2. A. Tanenbaum, Modern Operating Systems, Prentice-Hall, 2001.
3. U. Vahalia, Jądro systemu UNIX. Nowe horyzonty, WNT, 2001.
4. B. Goodheart, J. Cox, Sekrety magicznego ogrodu., WNT, 2001.
5. A. Rubini, J. Corbet, G. Kroah-Hartman, Linux Device Drivers, O'Reilly, 2005.

Moduły

Wykłady - Slajdy

Slajdy w formacie PDF