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, jerzy.brzezinski@cs.put.poznan.pl
• Dariusz Wawrzyniak, dariusz.wawrzyniak@cs.put.poznan.pl

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.

Laboratorium

• Użytkowanie uniksopodobnego systemu operacyjnego: 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 jądra uniksopodobnego systemu operacyjnego: 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.

Laboratorium — 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.

Laboratorium — 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 (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), ochrona pamięci.
2. Procesy i zasoby (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
     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 (3 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
     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ą (2 godz.)
   • 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 (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
     7. Zarządzanie pamięcią w systemach Unix, Linux i Windows
   • 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 (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.
7. Urządzenia składowania danych (1 godz.)
   • Treść wykładu
     1. Urządzenia o dostępie sekwencyjnym i bezpośrednim
     2. Budowa i parametry dysku
     3. Czas dostępu do danych na dysku
     4. Metody (algorytmy) planowania dostępu do dysku
     5. Macierze dyskowe
   • Najważniejsze pojęcia i zagadnienia: cylinder, ścieżka, sektor, pozycjonowanie, czas wyszukiwania, opóźnienie obrotowe, algorytm planowania (SSTF, SCAN, LOOK, N-step-SCAN, FSCAN), RAID, paskowanie
8. System plików (4 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
     8. Fizyczna organizacja systemu plików na dysku
        • przydział miejsca na dysku
        • zarządzanie wolną przestrzenią
        • implementacja katalogu
     9. Przechowywanie podręczne w systemie plików
     10. Integralność systemu plików
     11. Semantyka spójności i synchronizacja współbieżnego dostępu do pliku
     12. Przykłady implementacji systemu plików (CP/M, FAT, ISO 9660, Unix, NTFS)
   • Najważniejsze pojęcia i zagadnienia: plik, typ pliku, struktura pliku, dostęp sekwencyjny, dostęp bezpośredni, dostęp indeksowy, strefa, katalog, przydział ciągły, przydział listowy, przydział indeksowy, FAT.
9. Współbieżność (1 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)
   • Najważniejsze pojęcia i zagadnienia: instrukcja atomowa, przeplot, bezpieczeństwo, żywotność, uczciwość, wzajemne wykluczanie (sekcja krytyczna), ograniczone buforowanie.
10. Wzajemne wykluczanie (2 godz.)
    • Treść wykładu
      1. Definicja problemu wzajemnego wykluczania (sekcji krytycznej)
      2. Schemat algorytmu wzajemnego wykluczania
      3. Klasyczne algorytmy wzajemnego wykluczania oparte o zapis/odczyt zmiennych współdzielonych
         • algorytm Dekkera
         • algorytm Dijkstry
         • algorytm Petersona
         • algorytm Lamporta
      4. Rozwiązanie problemu wzajemnego wykluczania w oparciu o instrukcje test&set oraz exchange
    • Najważniejsze pojęcia i zagadnienia: poprawność algorytmu wzajmnego wykluczania (bezpieczeństwo, postęp, ograniczone czekanie), aktywne czekanie, wsparcie sprzętowe w rozwiązaniu problemu wzajemnego wykluczania.
11. Mechanizmy synchronizacji wspierane przez system operacyjny (2 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. Zastosowanie mechanizmów POSIX do rozwiązania głównych problemów synchronizacji procesów
    • Najważniejsze pojęcia i zagadnienia: semafor ogólny, semafor binarny, podnoszenie i opuszczanie semafora, zamek, zmienna warunkowa.
12. Mechanizmy synchronizacji ze wsparciem językowym (1 godz.)
    • Treść wykładu
      1. Monitory (definicja i zasada działania)
      2. Zastosowanie monitorów do rozwiązania problemu ograniczonego buforowania
      3. Regiony krytyczne
      4. Zastosowanie regionów krytycznych do rozwiązania problemu ograniczonego buforowania
      5. Klasyczne problemy synchronizacji procesów
         • problem czytelników i pisarzy
         • problem pięciu filozofów
         • problem śpiących fryzjerów
    • Najważniejsze pojęcia i zagadnienia: monitor, zmienna warunkowa w monitorze, region krytyczny, warunkowy region krytyczny.
13. Zakleszczenie (4 godz.)
    • Treść wykładu
      1. Definicja problemu zakleszczenia
      2. Warunki konieczne wystąpienia zakleszczenia
      3. Graf przydziału zasobów
      4. Rozwiązywanie problemu zakleszczenia
         • zapobieganie zakleszczeniom
         • unikanie zkleszczeń
         • detekcja i likwidacja zakleszczeń
      5. Podejście hybrydowe do rozwiązywania problemu zakleszczenia
    • Najważniejsze pojęcia i zagadnienia: stan osiągalny, zablokowanie procesu, warunki konieczne wystąpienia zakleszczenia, zapobieganie zakleszczeniom, unikanie zakleszczeń, algorytm Bankiera, graf oczekiwania, likwidacja zakleszczenia (usuwanie procesów, wywłaszczanie zasobów)
14. Ochrona zasobów (1 godz.)
    • Treść wykładu
      1. Cel ochrony
      2. Polityka i mechanizm
      3. Domenty ochrony
      4. Macierz dostępu
      5. Implementacja macierzy dostępu
    • Najważniejsze pojęcia i zagadnienia: polityka ochrony, mechanizm ochrony, prawo dostępu, domena ochrony, macierz dostępu, przenoszenie praw dostępu, prawo własności, prawo kontroli, lista kontroli dostępów (ang. access kontrol list), lista uprawnień (capability list), mechanizm zamka i klucza.

Laboratorium

Użytkowanie uniksopodobnego systemu operacyjnego (Linux)

1. Wstęp oraz obsługa plików i katalogów (3 godz.)
   • Treść zajęć laboratoryjnych
     1. Logowanie do systemu
     2. Pomoc systemowa – polecenie man
     3. Programy pomocnicze -- polecenia whatis, whereis, apropos
     4. Znaki specjalne
     5. Struktura katalogów w systemie
     6. Przemieszczanie się po strukturze katalogów – polecenia: pwd, ls, cd
     7. Tworzenie, usuwanie, zmiana nazwy plików – polecenia touch, rm, mv, cp
     8. Tworzenie, usuwanie, zmiana nazwy katalogów – polecenia mkdir, rmdir
     9. Wyszukiwanie plików – polecenia locate, find
     10. Dowiązania – polecenie ln
   • Opanowane umiejętności: logowanie, korzystanie z pomocy systemowej, poruszanie się w systemie plików, kopiowanie, usuwanie i przesuwanie plików, tworzenie i usuwanie katalogów, przeszukiwanie systemu plików.
2. Obsługa procesów w systemie (1 godz.)
   • Treść zajęć laboratoryjnych
     1. Identyfikatory procesów w systemie operacyjnym
     2. Lista procesów w systemie – polecenie ps
     3. Hierarchia procesów w systemie – polecenie pstree
     4. Wyszukiwanie procesów – polecenie pgrep
     5. Priorytety procesów – polecenia nice, renice
     6. Uruchamianie procesów w tle – znak & i polecenia fg, bg
     7. Sygnały i ich obsługa
   • Opanowane umiejętności: wyszukiwanie i identyfikacja procesów, usuwanie (zabijanie) procesów, zmiana priorytetu, uruchamianie procesów pierwszo- i drugoplanowych.
3. Filtry, strumienie standardowe oraz przetwarzanie potokowe (4 godz.)
   • Treść zajęć laboratoryjnych
     1. Strumienie standardowe i ich przekierowywanie
     2. Podstawowe filtry – polecenia cat, head, tail, grep, wc, tr, cut, sort, uniq
     3. Przetwarzanie potokowe z zastosowaniem filtrów systemowych
   • Opanowane umiejętności: uruchamianie procesów z przekierowaniem wejścia lub wyjścia do pliku, łączenie procesów w potoki, zastosowanie podstawowych filtrów
4. Tworzenie skryptów powłoki systemu operacyjnego (4 godz.)
   • Treść zajęć laboratoryjnych
     1. Zmienne środowiskowe oraz ich eksportowanie – polecenia set, env, echo, export
     2. Argumenty wywołania skryptów
     3. Instrukcja warunkowa
     4. Pętle while oraz for
     5. Pobieranie wartości w trakcie wykonywania skryptów
     6. Uruchamianie skryptów z debugowaniem
   • Opanowane umiejętności: tworzenie skryptów w języku powłoki, urchamianie skryptów, przekazywanie i obsługa parametrów.

Programowanie w języku C z wykorzystaniem funkcji jądra uniksopodobnego systemu operacyjnego (Linux)

1. Obsługa systemu plików (2 godz.)
   • Treść zajęć laboratoryjnych
     1. Otwieranie plików i ich deskryptory – funkcja open
     2. Tworzenie plików
     3. Odczyt i zapis do plików – funkcje read, write
     4. Implementacja przykładowych programów obsługi plików
   • Opanowane umiejętności: tworzenie plików oraz dostęp do zawartości plików.
2. Obsługa procesów w systemie (2 godz.)
   • Treść zajęć laboratoryjnych
     1. Procesy macierzyste i potomne
     2. Tworzenie procesów potomnych – funkcja fork, wait
     3. Uruchamianie programów – funkcje exec
     4. Przekierowywanie strumieni standardowych
     5. Implementacja przykładowych programów obsługi procesów
   • Opanowane umiejętności: tworzenie procesów, urchamianie programów w procesach oraz przekierowanie wyników standardowych programów uniksowych do pliku.
3. Obsługa potoków (4 godz.)
   • Treść zajęć laboratoryjnych
     1. Tworzenie potoków nienazwanych – funkcja pipe
     2. Tworzenie potoków nienazwanych – funkcja mkfifo - oraz ich otwieranie
     3. Przykłady przetwarzania potokowego
     4. Implementacja przykładowych programów obsługi potoków
   • Opanowane umiejętności: realizacja komunikacji potokowej (strumieniowej) między lokalnymi procesami.
4. Tworzenie i obsługa wątków (4 godz.)
   • Treść zajęć laboratoryjnych
     1. Tworzenie wątków – funkcja pthread_create
     2. Przekazywanie parametrów do funkcji wątków i pobieranie wyników – funkcaj pthread_join
     3. Synchronizacja wątków – grupa funkcji pthread_mutex i pthread_cond
     4. Implementacja przykładowych programów obsługi wątków
   • Opanowane umiejętności: tworzenie i usuwanie wątków, synchronizacja wątków (wzajemne wykluczanie, usypianie i budzenie).
5. Mechanizmy IPC: kolejki komunikatów (2 godz.)
   • Treść zajęć laboratoryjnych
     1. Tworzenie kolejek komunikatów – funkcja msgget
     2. Wysyłanie i odbieranie komunikatów – funkcje msgsnd, msgrcv
     3. Parametry i usuwanie kolejek komunikatów – funkcja msgctl
     4. Obsługa mechanizmów IPC w konsoli systemu – polecenia ipcs, ipcrm
     5. Implementacja przykładowych programów obsługi kolejek komunikatów
   • Opanowane umiejętności: realizacja przekazywania komunikatów pomiędzy lokalnymi procesami.
6. Mechanizmy IPC: pamięć współdzielona (2 godz.)
   • Treść zajęć laboratoryjnych
     1. Tworzenie i obsługa pamięci współdzielonej – funkcja shmget
     2. Przyłączanie pamięci współdzielonej do procesu – funkcja shmat
     3. Odłączanie pamięci współdzielonej od procesu – funkcja shmdt
     4. Parametry pamięci współdzielonej – funkcja shmctl
     5. Implementacja przykładowych programów obsługi pamięci współdzielonej
   • Opanowane umiejętności: tworzenie i udstępnianie segmentów pamięciu w celu przkazywania danych pomiędzy lokalnymi procesami
7. Mechanizmy IPC: semafory (2 godz.)
   • Treść zajęć laboratoryjnych
     1. Zasada działania semaforów binarnych i uogólnionych
     2. Tworzenie semaforów – funkcja semget
     3. Operacje na semaforach – funkcja semop
     4. Parametry semaforów i ich inicjowanie – funkcja semctl
     5. Przykłady podstawowych problemów synchronizacji
     6. Implementacja przykładowych programów z synchronizacją wykorzystująca semafory
   • Opanowane umiejętności: tworzenie i inicjalizowanie semafrów w celu synchronizacji współbieżnych procesów (między innymi w dostępie do współdzielonej pamięci).