Systemy operacyjne

Forma zajęć

wykład (30 godzin) + laboratorium (30 godzin)

Opis

Celem przedmiotu 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. Następnie omawiana jest koncepcja pliku oraz realizacja systemu plików — warstwy logicznej i fizycznej — wraz z przykładami konkretnych implementacji (CP/M, FAT-12/16/32, ISO 9660, Unix, NTFS). Osobnym zagadnieniem, integralnie związanym z realizacją systemu operacyjnego, jest współbieżności i synchronizacja w sensie koordynacji przepływu sterowania. W kontekście podstawowych problemów synchronizacji, takich jak wzajemne wykluczania 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). Następnie realizowane są zadania, polegające na zastosowaniu omawianych mechanizmów do rozwiązania klasycznych problemów synchronizacji (problem producenta-konsumenta, czytelników i pisarzy, pięciu filozofów, śpiących fryzjeró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.

Sylabus

Autor

• Jerzy Brzeziński
• Dariusz Wawrzyniak

Wymagania wstępne

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

Zawartość

Wykład

• Rola i zadania systemu operacyjnego oraz jego umiejscowienie 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 i zasobu oraz ich opis i identyfikacja
• Zarządzanie procesorem — szeregowanie zadań
• Zarządzanie pamięcią operacyjną — podział pamięci, przydział, zjawisko fragmentacji, segmentacja i stronicowanie
• Realizacja pamięci wirtualnej — obsługa błędu strony, problem wymiany stron i wznawiania rozkazów, implementacja algorytmów wymiany
• Zarządzanie urządzeniami wejścia-wyjścia — podsystem wejścia-wyjścia, sposoby interakcji jednostki centralnej z urządzeniami wejścia-wyjścia, buforowanie i spooling
• Urządzenia dyskowe — funkcjonowanie i parametry dysku, algorytmy sterowania ruchem głowic, macierze dyskowe
• System plików — pojęcie pliku, jego struktury i typu, organizacja logiczna systemu plików, organizacja fizyczna systemu plików, przykłady implementacji
• Ochrona zasobów — domeny ochrony, macierz dostępów i jej implementacja

• Współbieżność — instrukcje atomowe, przeplot i istota synchronizacji
• Poprawność programów współbieżnych — bezpieczeństwo i żywotność
• Wzajemne wykluczanie — algorytmy Dekkera, Dijkstry, Petersona, Lamporta
• Instrukcje atomowe test&set oraz exchange
• Semafory — klasyfikacja i implementacja
• Monitory
• Regiony krytyczne
• Spotkania
• Zakleszczenie — warunki konieczne, zapobieganie, unikanie, detekcja i usuwanie.

Ćwiczenia

• Użytkowanie systemu operacyjnego Unix: poruszanie się w systemie plików, obsługa plików i katalogów, obsługa procesów, potoki i filtry, skrypty powłoki
• Programowanie z wykorzystaniem funkcji systemowych jądra Unixa: tworzenie i dostęp do plików, tworzenie i obsługa procesów, uruchamianie programów, wątki i ich synchronizacja, sygnały, komunikacja strumieniowa za pośrednictwem łączy, mechanizmy grupy IPC

Literatura

Wykład

1. G. Nutt. Operating Systems. A Modern Perspective. wydanie 2, Addison Wesley Longman, Inc., 2002.
2. W. Stallings. Systemy operacyjne. Robomatic, Wrocław, 2004.
3. L. Bic, A. C. Shaw. The Logical Design of Operating Systems. Prentice-Hall, Inc, 1988.
4. A. Silberschatz, J.L. Peterson, G. Gagne. Podstawy systemów operacyjnych. WNT, Warszawa, 2005.
5. A. S. Tanenbaum. Modern Operating Systems. wydanie 2, Prentice-Hall, Inc, 2001.
6. M. J. Bach. Budowa systemu operacyjnego Unix®. WNT, Warszawa, 1995.
7. B. Goodheart, J. Cox. Sekrety magicznego ogrodu. UNIX® System V Wersja 4 od środka. WNT, Warszawa, 2001.
8. U. Vahalia. Jądro systemu UNIX®. Nowe horyzonty. WNT, Warszawa, 2001.
9. D. A. Solomon, M. E. Russinovich. Microsoft Windows® 2000 od środka. Helion, Gliwice, 2003.
10. R. Lowe. Kernel Linux. Przewodnik programisty. Helion, Gliwice, 2004.

Ćwiczenia — użytkowanie

1. C. Sobaniec. System operacyjny Linux — przewodnik użytkownika. Nakom, Poznań, 2002.
2. J. Marczyński. UNIX użytkowanie i administrowanie. wydanie 2, Helion, Gliwice, 2000.
3. P. Silvester. System operacyjny Unix™. WNT, Warszawa, 1990.
4. Z. Królikowski, M. Sajkowski. UNIX dla początkujących i zaawansowanych. Nakom, Poznań, 1996.

Ćwiczenia — programowanie

1. W. R. Stevens. Programowania w środowisku systemu UNIX. WNT, Warszawa, 2002.
2. J. S. Gray. Komunikacja między procesami w Unixie. ReadMe, Warszawa, 1998.
3. M. J. Rochkind. Programowanie w systemie Unix dla zaawansowanych. WNT, Warszawa, 1993.
4. Z. Guźlewski, T. Weiss. Programowanie współbieżne i rozproszone w przykładach i zadaniach. WNT, Warszawa, 1993.
5. R. W. Stevens. Programowanie zastosowań sieciowych w systemie Unix. WNT, Warszawa, 1995.
6. M. Gabassi, B. Dupouy. Przetwarzanie rozproszone w systemie Unix. Lupus, Warszawa, 1995.

Moduły

Wykład

1. Wstęp
   • 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), ochrona pamięci.
2. Procesy i zasoby
   • 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
     10. Użytkownicy
   • 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, użytkownik (końcowy, programista, administrator).
3. Szeregowanie
   • 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
     8. Planowanie przydziału procesora w systemach: Unix, Linux i Windows
   • najważniejsze pojącia i zagadnienia: priorytet procesu, wywłaszczanie, planowanie priorytetowe, planowanie rotacyjne, wykorzystanie procesora, przepustowość, czas oczekiwania, czes reakcji, czas cyklu przetwarzania.
4. Zarządzanie pamięcią
   • Treść wykładu
     1. Pamięć a przestrzeń adresowa
     2. Obraz procesu w pamięci
     3. Problem ochrony i współdzielenia pamięci
     4. Podział i przydział pamięci
     5. Fragmentacja
     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.
5. Pamięć wirtualna
   • 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.
6. Urządzenia wej-wyj
7. Dyski
8. System plików
9. Współbieżność
10. Wzajemne wykluczanie
11. Semafory
12. Monitory i regiony krytyczne
13. Zakleszczenie
14. Ochrona