Motto 1 (wyobraźnia w teorii):
Siłą stojącą za wszystkimi przełomowymi koncepcjami, siłą zmieniającą oblicze świata jest wolna, nieskrępowana wyobraźnia...
A.Einstein Zapiski autobiograficzne, Wyd. Znak, Kraków 1996.

Motto 2 (wyobraźnia w akcji):
Przywodząc analogię rolniczą, możemy powiedzieć, że wieloprocesor jest systemem, w którym trzoda świń (procesów) je ze wspólnego koryta (pamięci dzielonej). Multikomputer to system, w którym każda świnia ma własne, prywatne koryto.
A.S.Tanenbaum Rozproszone systemy operacyjne, PWN, Warszawa 1997, rozdz.6, str.344.

SYSTEMY OPERACYJNE

KOLOKWIUM:

Termin kolokwium: wykład 22.05.2012

Termin poprawkowy: 29.05.2012, godz. 9.15 (ostatni wykład; w przypadku nieobecności w terminie kolokwium zaliczeniowego

warunkiem uczestnictwa w terminie poprawkowym jest jej formalne usprawiedliwienie) – ta sama sala co wykład.

 

WYNIKI KOLOKWIUM

 

Wpisy: 29.05.2012, godz. 9.15 (uwaga, zmiana z 10.30!) – ta sama sala co wykład.

Procedura wpisowa: bardzo proszę osoby z pozytywnymi ocenami o ich wpisanie w indeksy oraz na karty zaliczeń wraz z datą. Unikniemy dzięki temu kolejkowania oraz wzajemnej straty czasu na niepotrzebne formalności – ja tylko podpisuję.

POPRAWA: to samo miejsce, godz. 9.45.

 

WYKŁAD

Wykład kończy się kolokwium zaliczeniowym 
Oceny z kolokwium oraz laboratorium/ćwiczeń są niezależne.

Forma kolokwium jest pisemna. 

Obecność na kolokwium jest obowiązkowa.

 

Ramowy plan wykładu (prawdopodobnie będzie uzupełniany):
1 Podstawowe pojęcia, historia SO.
2 Procesy.
3 Koordynacja procesów.
4 Zarządzanie pamięcią.
5 Pamięć wirtualna.
6 Pamięć pomocnicza.
7 System plików.
8 Ochrona, prawa dostępu.
9 Rozproszone SO.
10 Komunikacja w syst. rozproszonych.
11 Synchronizacja w syst. rozproszonych.
12 Procesy, pamięć i systemy plików w syst. rozproszonych. 

13 Rozwój SO a systemy GRID

14 Perspektywy rozwojowe systemów operacyjnych.

 

Notatki do początkowej części wykładu...

 

LABORATORIUM

 

Szczegółowe kryteria ocen określają indywidualnie prowadzący poszczególne laboratoria. 

Terminy oddawania zadań programistycznych będą ogłoszone w trakcie semestru, po zakończeniu pierwszej części laboratorium, poświęconej systemom Windows i Unix.

Kwestie przepisywania ocen (w przypadku wcześniejszego zaliczenia przedmiotu na innym kierunku/specjalności) rozstrzygają indywidualnie prowadzący odpowiednie zajęcia. 

 

ZASADY OCENIANIA ZADAŃ PROGRAMISTYCZNYCH (sugerowane i niewiążące – prowadzący laboratoria ustalają indywidualne w swoich grupach):

- zadania podlegają zaliczeniu w podanym dniu (określonym przez Prowadzącego). Za zadanie oddane z opóźnieniem o 1 zajęcia można otrzymać max. ocenę 3.5. Zadania spóźnione o więcej nie będą oceniane - wyjątek stanowią jedynie odpowiednio udokumentowane (pisemnie - zwolnieniem lekarskim) przypadki losowe.

- zadania laboratoryjne polegają na symulacji i badaniu własności algorytmów/mechanizmów stosowanych w systemach operacyjnych. W związku z tym podstawą zaliczenia takiego zadania jest nie tylko software ale także znajomość odpowiednich zagadnień, weryfikowana w formie ustnej odpowiedzi. 

- oddawanie zadań "na maila" jest wykluczone.

 

Zadanie 1  

Program ma symulować działanie algorytmów planowania dostępu do procesora dla zgłaszających się procesów. 
Zbadać średni czas oczekiwania procesów dla różnych algorytmów planowania: 
-
FCFS 
-
SJF (z wywłaszczaniem i bez) 
-
rotacyjnego (z możliwością wyboru kwantu czasu) 
Należy samodzielnie sformułować założenia symulacji. 
Wskazówki: 
- algorytmy najlepiej sprawdzać dla tych samych danych testowych (tj. tych samych ciągów testowych zgłaszających się procesów) 
- ciągów testowych powinno być więcej (20? 50?); wynikiem będą wartości średnie. 
- w każdym ciągu będzie N procesów o losowych długościach fazy procesora (rozkład długości faz dobrać tak, by odpowiadał sytuacji w rzeczywistym systemie, w którym nie jest równomierny), zgłaszających się w losowych momentach (dobrać parametry tak, by mogła powstać kolejka procesów oczekujących na przydział procesora).
- możliwa reprezentacja procesu: rekord (numer, dł.fazy procesora, moment zgłoszenia się, czas oczekiwania /początkowo równy 0/...) 
Uzyskane wyniki należy wytłumaczyć i być gotowym na wyciągnięcie z nich wniosków... :) 
Mile widziana możliwość sterowania parametrami symulacji. 
Przy zaliczeniu należy być przygotowanym na ew. pytania dotyczące materiału omówionego na wykładzie i związanego z tematem zadania...

 

Zadanie 2  

Symulacja algorytmów planowania dostępu do dysku.
* 'Dysk' to w naszym przypadku liniowo uporządkowany ciąg bloków o nr od 1 do MAX.
* Kryterium oceny algorytmów będzie suma przemieszczeń głowicy dysku, jak wiadomo proporcjonalna do czasu realizacji zleceń. 
* 1.Sprawdzić algorytmy
FCFS, SSTF, SCAN i C-SCAN.
* 2.Następnie założyć, że w systemie istnieją także aplikacje real-time, które musza być obsłużone za pomocą EDF i/lub FD-SCAN. Jak wpływa to na wyniki?
UWAGA!
Sformułowanie nie wymienionych powyżej warunków symulacji należy do Państwa. Mam na myśli:
-wielkość 'dysku' (ilość bloków)
-liczba i sposób generowania zgłoszeń (pełna kolejka od początku? zgłoszenia w trakcie? rozkład zgłoszeń- równomierny, inny?) 
-sposób uwzględnienia obsługi zgłoszeń real-time
-pozostałe... >>> mile widziana umiejętność uzasadnienia przyjętego rozwiązania.

 

Zadanie 3

Badanie algorytmów zastępowania stron. 

Należy samodzielnie sformułować założenia symulacji: 

- rozmiar pamięci wirtualnej (ilość stron). 

- rozmiar pamięci fizycznej (ilość ramek). 

- długość (powinna być znaczna - min. 1000) i sposób generowania ciągu odwołań do stron (koniecznie uwzględnić zasadę lokalności odwołań).

Działanie programu: 

- wygenerować losowy ciąg n odwołań do stron 

- dla wygenerowanego ciągu podać liczbę błędów strony dla różnych algorytmów zastępowania stron: 

1. FIFO (usuwamy stronę najdłużej przebywającą w pamięci fizycznej) 

2. OPT (optymalny - usuwamy stronę, która nie będzie najdłużej używana) 

3. LRU (usuwamy stronę, do której najdłużej nie nastąpiło odwołanie) 

4. aproksymowany LRU (wiadomo) 

5. RAND (usuwamy losowo wybraną stronę) 

- symulacje przeprowadzić (na tym samym ciągu testowym) dla różnej liczby ramek (np. kilku (3, 5, 10?)  wartości podanych przez użytkownika)

Zakres materiału: wszystko o pamięci wirtualnej (z wykładu).

 

Zadanie 4  

Postępująca komplikacja zad. 4. Założyć, że:

- w systemie działa pewna ilość (rzędu ~10) procesów.

- każdy korzysta z własnego zbioru stron (zas. lokalności wciąż obowiązuje).

- globalny ciąg odwołań jest wynikiem połączenia sekwencji odwołań generowanych przez poszczególne procesy (każdy generuje ich wiele, nie jedną)

- każdemu system przydziela określoną liczbę ramek. na podstawie następujących metod:

1. Przydział proporcjonalny

2. Przydział równy

3. Sterowanie częstością błędów strony

4. Model strefowy.

- zastępowanie stron odbywa się zgodnie z LRU.

Jak strategie przydziału ramek wpływają na wyniki (ilość błędów strony - globalnie, dla każdego procesu)? 

Program powinien wypisywać na ekranie przyjęte założenia symulacji. Mile widziana możliwość ich zmiany przez użytkownika.

Wnioski?

Zakres materiału: jak w zad 3.

 

Zadanie 5  

Symulacja rozproszonego alg. równoważącego obciążenie procesorów.
W systemie pracuje N identycznych procesorów. Na każdym z nich pojawiają się nowe zadania (procesy), z RÓŻNĄ częstotliwością i RÓŻNYMI wymaganiami (każdy proces wymaga określonego, różnego,  udziału w mocy obl. procesora - np ~3%). Zasymulować nast. strategie przydziału:

Na procesorze x pojawia sie zadanie. Nastepnie:

1. x pyta losowo wybr. procesor y o aktualne obciążenie. Jeśli jest mniejsze od progu p, proces jest tam wysyłany. Jeśli nie, losujemy i pytamy następny, próbując co najwyżej z razy. Jeśli wszystkie wylosowane są obciążone powyżej p, proces wykonuje się na x. 

2.Jesli obciążenie x przekracza wartość progową p, proces zostaje wysłany na losowo wybrany procesor y o obciążeniu mniejszym od p (jeśli wylosowany y ma obc.>p, losowanie powtarza się do skutku). Jeśli nie przekracza - proces wykonuje się na x.

3.Jak w pkt 2, z tym że procesory o obciążeniu mniejszym od minimalnego progu r pytają losowo wybrane procesory i jesli obc. zapytanego jest większe od p, pytający przejmuje część jego zadań (założyć jaką).

Przeprowadzić symulację strategii 1-3 dla N=ok.50-100 i długiej serii zadań do wykonania (parametry dobrać samodzielnie, tak by całość zadziałała:). W każdym przypadku podać jako wynik:
A. Średnie obciążenie procesorów (zdecydować, rozsądnie, jak będzie obliczane).
B. Średnie odchylenie od wartości z pkt A.
C. Ilość zapytań o obciążenie oraz migracji (przemieszczeń) procesów.

Użytkownik powinien mieć możliwość podania (zmiany) wartości p,r,z,N.

Szczegóły: wykład lub "Rozpr. Syst. Operacyjne, AS. Tannenbaum" (rozdz. 4.3.4, str. 252).
Teoria: Przydział procesorów w syst. rozproszonych (z wykładu).

 

Zadanie X  

Obowiązuje w grupie mgr P.Stelmacha: ZADANIE

 

Literatura:
Systemy operacyjne:
1. A. Silbershatz, J.L. Peterson, P.B. Galvin, Podstawy systemów operacyjnych, WNT 1993.
2. A.S. Tannenbaum, Rozproszone systemy operacyjne, Wyd. Nauk. PWN, 1997.
3. A.M. Lister, R.D. Eager, Wprowadzenie do systemów operacyjnych, WNT, 1994.
Syst. operacyjne na przykładzie UNIX (materiały uzupełniające):
4. W.R. Stevens, Programowanie zastosowań sieciowych w systemie UNIX, WNT, 1995.
5. Gabassi, Przetwarzanie rozproszone w systemie UNIX, Wyd. Lupus.
6. M.J Bach, Budowa systemu operacyjnego UNIX, WNT, 1995.

 

MATERIAŁY

 

The Locality Principle

Internet-Scale OS

Singularity Project