1. Podaj definicję systemu operacyjnego. System operacyjny jest programem, który działa pośrednik między użytkownikiem komputera, a sprzętem komputerowym. Zadaniem s. o. jest tworzenie środowiska, w którym użytkownik może wykonywać program w sposób wygodny i wydajny. S. o. musi gwarantować bezbłędną pracę systemu komputerowego. S. o. - program (zbiór programów), który steruje wprowadzaniem i wykonywaniem innych programów; pracą urządzeń we/wy; przydziałem pamięci i administrowaniem danymi; umożliwia wykrywanie błędów w działaniu komputera; umożliwia komunikowanie się operatora z komputerem. S. o. jest programem sterującym - nadzoruje działanie programów użytkownika, przeciwdziała błędom, zapobiega niewłaściwemu użyciu komputera. Zajmuje się obsługiwaniem i kontrolowaniem pracy urządzeń we/wy S. o. - program nieustannie działający w komputerze S. o. jest dystrybutorem zasobów (sprzętowych i programowych) np.: czas procesora System komputerowy składa się z 4 części: sprzęt, system operacyjny, programy użytkowe, użytkownicy Rodzaje s. o.: jednostanowiskowe (MS DOS), sieciowe (MS Windows XX, Novell NetWare, UNIX), rozproszone (Ameba, Choruj, QNX), czasu rzeczywistego (QNX)

2. Buforowanie i spooling. Buforowanie polega na jednoczesnym wykonywaniu obliczeń i operacji we/wy dla danego zadania. Po przeczytaniu danych, kiedy procesor może zacząć je przetwarzać, poleca się urządzeniu wejściowemu natychmiastowe rozpoczęcie czytania następnych danych. W ten sposób zarówno jednostka centralna, jak i urządzenie wejściowe nie pozostają bezczynne. Szybkość pracy procesora i urządzeń we/wy różni się o jeden lub kilka rzędów wielkości, podczas czytania z taśmy procesor pozostaje bezczynny. Buforowanie polega na ładowaniu kolejnych danych wejściowych lub wyprowadzaniu wyników równocześnie z obliczeniami, zysk zależy od stopnia uzależnienia programu od operacji we/wy. Buforowanie danych pozwala procesorowi nieco wyprzedzać urządzenia, lub pozostawać nieco w tyle, a jednocześnie przetwarzać wszystko z pełną prędkością. Spooling - jednoczesna, bezpośrednia praca urządzeń - wprowadzenie pamięci zewnętrznej o bezpośrednim dostępie do danych, zamiast rekurencyjnego, dysk jest wykorzystywany jako bufor. Buforowanie pozwala wykonywać w tym samym czasie operacje we/wy i obliczenia dla tego samego zadania Spooling umożliwia równoczesne wykonywanie operacji we/wy jednego zadania i obliczeń innego, co stanowi jego przewagę nad buforowaniem Wiele zadań przebywających na dysku wymaga wprowadzenia pewnej metody wyboru zadania do wykonania (koncepcja planowania zadań) Spooling wraz z planowaniem zadań wprowadza pojęcie wieloprogramowości.

3. Wieloprogramowość: polega na istnieniu więcej niejednego zadania gotowego do wykonania podczas wykonywania pracy jednego zadania można procesor przełączyć na wykonywanie drugiego poprawia wskaźnik wykorzystania czasu pracy procesora zwiększa wykorzystanie procesora, przez co procesor jest ciągle zajęty - wykonuje określone zadania Problemy pojawiające się wraz z wieloprogramowością szeregowanie zadań przydział pamięci wzajemna ochrona zadań dostęp do zasobów dzielonych komunikacja między zasobami

4. Wielozadaniowość: wieloprogramowość + podział czasu procesora = wielozadaniowość polega na przeplataniu pracy zadań, przy czym użytkownik ma wrażenie, że tylko jego program jest wykonywany procesor wykonuje na przemian wiele różnych zadań, przy czym przełączenia następują tak często, że użytkownicy mogą współdziałać z każdym programem podczas jego wykonania

5. Przerwanie, wektor przerwań, blokowanie przerwań (maskowanie). Procesor po otrzymaniu sygnału przerwania wstrzymuje swą bieżącą pracę i natychmiast pobiera zawartość ustalonego miejsca pamięci. Miejsce to zawiera na ogół adres startowy procedury obsługującej dane przerwanie. Procedura obsługi przerwania przesyła dane z lokalnego bufora sterownika urządzenia do pamięci głównej. Po zakończeniu przesyłania danych procesor jest gotowy do wznowienia przerwanych obliczeń. Przerwanie musi przekazywać sterowanie do procedury obsługi przerwania. W tym celu rezerwuje się ciąg komórek na początku pamięci głównej aby przechowywać tam adres procedur obsługi przerwań pochodzących od różnych urządzeń. Tablica ta zwana jest wektorem przerwań, jest indeksowana jednoznacznym numerem urządzenia, w który jest zaopatrzone żądanie przerwania Przerwanie o wyższym priorytecie będzie obsłużone nawet wtedy, gdy jest aktywne jakieś przerwanie o niższym priorytecie, natomiast przerwania tego samego poziomu ulegają maskowaniu, tj. selektywnemu wyłączaniu (uniknie się w ten sposób utraty przerwań lub występowania przerwań nieoczekiwanych) Tablica stanów urządzeń służy do: odnotowania wielu zgłoszeń żądania obsługi przez urządzenie we/wy określa stan urządzenia

6. Obsługa urządzeń w oparciu o DMA Szybkie urządzenia we/wy korzystają z bezpośredniego dostępu do pamięci operacyjnej. Po określeniu buforów, wskaźników i liczników sterownik danego urządzenia przesyła bezpośrednio (bez ingerencji procesora) cały blok danych między własnym buforem, a pamięcią. Zasadnicze działanie jednostki centralnej pozostaje niezmienione. Program użytkownika lub sam s. o. może zażądać przesłania danych. S. o. wybiera bufor z kolejki buforów do przesłania. Następnie odpowiednie obszary źródła i miejsca przeznaczenia umieszcza się w rejestrach sterownika DMA. Po tym zabiegu sterownik DMA dostaje informacje, że należy zainicjować operację we/wy. PO jej zakończeniu sterownik DMA wysyła przerwanie do procesora. W celu obsługi transmisji blokowych (np. z dysku) wprowadzono bezpośredni dostęp do pamięci, po zakończeniu transmisji danych jest generowane przerwanie mówiące o przesłaniu całego bloku danych.

7. Prosty monitor. Potrzebna była procedura automatycznego przekazywania sterowania od jednego zadania do następnego. W tym celu ułożono mały program, zwany monitorem rezydującym. Monitor rezydujący stale przebywa w pamięci operacyjnej komputera. Na początku (po włączeniu komputera) wywoływano monitor rezydujący, który przekazywał sterowanie do programu. Gdy program kończył działanie wtedy zwracał sterowanie do monitora, a ten wyznaczał kolejny program. W ten sposób monitor rezydujący zapewniał automatyczne przechodzenie od jednego programu do drugiego i od jednego zadania do następnego. Wprowadzenie metody automatycznego porządkowania zadań stało się podstawą zbudowania pierwszych systemów operacyjnych. Wyeliminowano: czas przestoju procesora podczas przekładania taśmy określanie przez operatora poprawności zakończenia lub błędu programu Rozmieszczenie monitora w pamięci: program ładujący monitor porządkowanie zadań interpretator kart sterujących obszar programu użytkownika

8. Pułapka. Pułapka (wyjątek) jest rodzajem przerwania generowanego przez oprogramowanie, a powodowanym przez błąd, albo przez specjalne zamówienia pochodzące z programu użytkownika, które wymagają obsłużenia przez s. o. Po wystąpieniu pułapki sprzęt zmienia swój system pracy z 1 (użytkownika) na 0 (monitora) Mechanizm pułapek: służy do obsługi błędów wykrytych przez sprzęt np. wykonanie niedozwolonego rozkazu, próba dostępu do zabronionego obszaru pamięci podobny jest do systemu przerwań wygenerowanie pułapki wymaga interwencji s. o.

9. Dualny tryb pracy Za każdym razem po wystąpieniu pułapki lub przerwania, sprzęt zmienia swój tryb pracy z trybu użytkownika na tryb monitora. Dualny tryb pracy pozwala na: ochronę s. o. przed nieodpowiedzialnym użytkownikiem wyróżnianie potencjalnie niebezpiecznych rozkazów tzw. rozkazów uprzywilejowanych próba wykonania przez użytkownika rozkazu uprzywilejowanego generuje pułapkę pułapki i przerwania wykonuje się w trybie monitora Bit trybu (jego stan) wskazuje na bieżący tryb pracy: monitor (0) lub użytkownik (1). Za pomocą bitu trybu można odróżnić działania wykonywane na zamówienie s. o. od działań wykonywanych na zamówienie użytkownika nie wszystkie błędy są wykrywanie przez sprzęt ochronie musi podlegać obszar systemu operacyjnego oraz programy użytkowników, na co pozwala dualny tryb pracy

10. Rejestr bazowy, rejestr graniczny. rejestr bazowy - przechowuje najmniejszy dopuszczalny adres fizyczny pamięci rejestr graniczny - zawiera rozmiar obszaru pamięci np. jeżeli rb=300040, a rg=120900, to w programie mogą wystąpić odniesienia do wszystkich adresów od 300040 do 420940

11. Składowe systemu operacyjnego. a) zarządzanie procesami, s. o. musi zapewnić: tworzenie i usuwanie procesów użytkowych i systemowych wstrzymywanie i wznawianie procesów mechanizm synchronizacji procesów mechanizm komunikacji procesów mechanizm obsługi blokad b) zarządzanie pamięcią operacyjną: ewidencja aktualnie zajętych części pamięci wraz z informacją, kto ją wykorzystuje wybieranie procesów, które mogą być załadowanie do zwolnionych obszarów pamięci przydzielanie i zwalnianie obszarów pamięci stosownie do potrzeb c) zarządzanie pamięcią pomocniczą zarządzanie obszarami wolnymi przydzielanie pamięci planowanie przydziałów pamięci dyskowej d) zarządzanie systemami we/wy system buforowy ogólny interfejs do programów obsługi urządzeń we/wy e) zarządzanie plikami tworzenie i usuwanie plików tworzenie i usuwanie katalogów operacje manipulowania plikami i katalogami odwzorowanie plików w obszary pamięci pomocniczej składowanie plików f) system ochrony g) praca sieciowa h) interpretator komend

12. Usługi systemu operacyjnego. a) wykonanie programu System powinien móc załadować program do pamięci i rozpocząć jego wykonywanie. Program powinien móc zakończyć swą pracę normalnie lub z przyczyn wyjątkowych b) operacje we/wy Program użytkownika nie może wykonywać operacji we/wy bezpośrednio, więc środki do realizacji tych czynności musi mieć s. o. c) manipulowanie systemem plików Programy muszą zapisywać i odczytywać pliki. Jest im również potrzebna możliwość tworzenia i usuwania plików przy użyciu ich nazw d) komunikacja Może przebiegać za pomocą pamięci dzielonej lub przy użyciu mniej ogólnej techniki przekazywania komunikatów, w której pakiety informacji są przenoszone między procesami za pośrednictwem s. o. e) wykrywanie błędów S. o. powinien być nieustannie powiadamiany o występowaniu błędów. Na wszystkie rodzaje błędów s. o. powinien odpowiednio reagować, gwarantując poprawność i spójność obliczeń f) przydział zasobów Jeżeli wielu użytkowników i wiele zadań pracuje w tym samym czasie, to każdemu z nich muszą być przydzielone zasoby. S. o. zarządza różnego rodzaju zasobami. g) rozliczanie Przechowywanie danych o tym, którzy użytkownicy, w jakim stopniu korzystają z poszczególnych zasobów komputera. Przechowywanie takich rekordów może służyć do rozliczania lub gromadzenia informacji w celach statystycznych h) ochrona Obejmuje sprawdzanie poprawności wszystkich parametrów przekazywanych w wywołaniach systemowych i gwarantuje nadzór nad dostępem do wszystkich zasobów systemu. Zabezpiecza przed niepożądanymi czynnikami zewnętrznymi.

13. Funkcje systemowe. Funkcje systemowe tworzą interfejs między wykonywanym programem, a s. o. Można z nich korzystać za pomocą instrukcji w języku asemblera. Można je podzielić na 5 podstawowych kategorii: a) nadzorowanie procesów: zakończenie, zaniechanie załadowaniem wykonanie utworzenie procesu, zakończenie procesu pobieranie atrybutów procesu, określenie atrybutów czekanie czasowe oczekiwanie na zadanie, sygnalizacja zadania przydział i zwalnianie pamięci b) operacje na plikach: utworzenie pliku, usunięcie pliku otwarcie, zamknięcie czytanie, pisanie, zmiana położenia pobranie atrybutów pliku, określenie atrybutów pliku c) operacje na urządzeniach: zamówienie urządzenia, zwolnienie urządzenia czytanie, pisanie, zmiana połączenia pobieranie i określanie atrybutów urządzenia logiczne przyłączenie lub odłączenie urządzenia d) utrzymywanie operacji pobieranie daty lub czasu, określanie daty lub czasu pobieranie, określanie danych systemowych pobieranie, określanie atrybutów procesu, pliku lub urządzenia e) komunikacja utworzeni, usunięcie połączenia komunikacyjnego nadawanie, odbieranie komunikatów przekazywanie informacji o stanie

14. Struktura systemu DOS i UNIX. Warstwowa struktura systemu MS-DOS: (użytkownicy) programy, shell, polecenia, kompilatory, interpretatory, biblioteki systemowe interfejs między funkcjami systemowymi, a jądrem - sygnały - obsługa terminali - np. znakowy we/wy - program obsługi terminali - system plików - wymiana - np. blokowego we/wy - program obsługi dysków i taśm - planowanie przydziału procesora - zastępowanie stron - pamięć wirtualna - stronicowanie na żądanie interfejs między jądrem, a sprzętem - sterowniki terminali - terminale - sterowniki urządzeń - dyski i taśmy - sterowniki pamięci - pamięć operacyjna Struktura systemu UNIX: UNIX składa się z dwóch odrębnych części: jądra i systemowych programów. Jądro dzieli się dalej na ciąg interfejsów i programów obsługi urządzeń

15. Cechy systemu NT. rozszerzalność - pozwala dorównać postępom w technice obliczeniowej. Można dodawać do systemu następne podsystemy środowiskowe bez naruszania egzekutora. System może być uzupełniany podczas działania o nowe systemy plików, nowe rodzaje urządzeń oraz nowe rodzaje sieci. przenośny - daje się przetransportować z jednej architektury sprzętowej na inną ze stosunkowo niewielką ilością zmian. niezawodny - zdolność radzenia sobie z sytuacjami błędnymi, w co wchodzi zdolność systemu operacyjnego do ochrony samego siebie i jego użytkowników przed wadliwym lub złośliwym oprogramowaniem zgodność - na poziomie kodu źródłowego dla aplikacji spełniających standard IDEE 1003.1 (POSIX) (???), można je zatem kompilować do pracy w systemie NT bez zmian i ich kodzie źródłowym wydajność - szybkie przekazywanie komunikatów, system szybko może reagować na zdarzenia zewnętrzne system NT zaprojektowano do wieloprzetwarzania (???) systemowego spełnia wymogi międzynarodowe.

16. Budowa systemu NT. Architekturę systemu NT tworzy warstwowy układ modułów. Głównymi warstwami są: a) działające w trybie chronionym - warstwa abstrakcji sprzętu - (ukrywa różnice sprzętowe przed górnymi warstwami s.o.) eksportuje interfejs maszyny wirtualnej, z którego korzystają: jądro, egzekutor i moduły sterujące urządzeń. Jedną z zalet takiego podejścia jest to, że wystarczy aby każdy moduł sterujący występował tylko w jednej wersji, może on działać na wszystkich rodzajach sprzętu bez przenoszenia kodu modułu sterującego. Warstwa MAL (???) umożliwia także przetwarzanie symetryczne - jądro - stanowi podstawę egzekutora i podsystemów. Strony jądra nigdy nie są usuwane z pamięci operacyjnej. Jądro ma cztery główne obowiązki: planować procesy, obsługiwać przerwania i sytuacje wyjątkowe, synchronizować na niskim poziomie procesor, podejmować działania naprawcze po awarii zasilania. Jądro jest zorientowane obiektowo. Przez typ obiektu rozumie się zdefiniowany w systemie NT typ danych, który ma zbiór atrybutów (wartości danych) i zbiór metod (funkcji lub procedur). Reprezentant danego typu obiektowego nazywa się obiektem. Jądro wykonuje swoje zadania posługując się zbiorem obiektów jądrowych: obiekty ekspedytora - nadzorują one deklarowanie procesów do procesora oraz synchronizację w systemie. Przykładami obiektów tego zbioru są zdarzenia, zamki, semafory, wątki, czasomierze obiekty sterujące - są to asynchroniczne wywołania procedur, przerwania, sygnały dotyczące zasilania i jego stanu oraz procesy i obiekty profilujące - egzekutor - wykonuje zbiór usług, z których mogą korzystać wszystkie podsystemy środowiskowe. Usługi te można podzielić na grupy: zarządcę obiektów, zarządcę pamięci wirtualnej, zarządcę procesów, udogodnienie lokalnych wywołań procedur, zarządcę we/wy oraz monitor odwołań b) działających w trybie użytkownika duży zbiór podsystemów

17. Definicja procesu. program, który jest załadowany do pamięci operacyjnej i wykonywany w niej. jednostka pracy w systemie. W takim ujęci system składa się ze zbioru procesów, z których część to procesy systemowe (wykonują kod systemu), pozostałe są procesami użytkowymi(wykonują kod określony prze użytkownika) element aktywny (program - pasywny) S. o. musi zapewniać: tworzenie i usuwanie procesów użytkowych i systemowych wstrzymywanie i wznawianie procesów mechanizmy synchronizacji procesów mechanizmy komunikacji procesów mechanizmy obsługi blokad

18. RAID (redundant array of inexpensive disks)(nadmiarowa tablica niezależnych wątków) - bitowy - blokowy RAID - zwiększa wydajność, polepsza niezawodność w skutek pamiętania nadmiarowych danych; metoda paskowania dysków przeplot - grupa dysków traktowana jako jedna jednostka pamięci 0 - przeplot blokowy, duża wydajność, duża awaryjność, implementowany jako rozszerzenie systemu operacyjnego 1 - mirroring (odbicie lustrzane), dane zapisuje się jednocześnie na dwóch zestawach dysków, dobre bezpieczeństwo. Wykonuje się kopie każdego dysku. Rozwiązanie to jest drogie ponieważ do pamiętania tej samej ilości danych stosuje się dwukrotnie więcej dysków, jednak zapewnia to dwukrotnie szybsze czytanie 2 - przeplot bitowy, bajty dzieli się na grupy bitów i rozdziela się pomiędzy dyski, duża wydajność, trudno rozbudowywalne 3 - pełny przeplot (0) i jeden dysk nadmiarowy (sum kontrolnych) 4 - jak (3), ale z przeplotem bitowym 5 - jak (3), ale informacja o parzystości jest dzielona między dyski, zmniejsza narzut przy zapisie, wielka wydajność i łatwość rozbudowy

19. Własności plików FAT i NTFS. FAT: niekompatybilny z FAT32 wspiera długie nazwy (do 255 znaków) praktyczny brak ochrony maksymalny rozmiar pliku/partycji 4 GB NTFS wspiera długie nazwy (do 255 znaków) pozwala na implementację polityki ochrony maksymalny rozmiar partycji: teoretycznie - 16 EB (exabajt), aktualnie 2 TB (terabajt) maksymalny rozmiar pliku 4 - 64 GB (zależy od sprzętu) zalecany minimalny rozmiar partycji 50 MB możliwość kompresji Porównanie FAT i NTFS: FAT jest bardziej wydajny dla małych partycji (do 400 MB) partycje powyżej 400 MB zaleca się robić w oparciu o NTFS możliwość jednostronnej konwersji

20. Przekazanie, a przesłanie komunikatu. wysłanie - komunikat ląduje w kolejce komunikatów odpowiedniego wątku przekazanie - komunikaty są bezpośrednio przekazywane procedurze obsługi danego okna

21. SendMessage(), PostMessage(), GetMessage(), PickMessage(). PostMessage - przekazanie komunikatu w trybie pocztowym. Procedury pocztowe są asynchroniczne, Zwracają one sterowanie natychmiast i wywołujący je wątek nie jest zorientowany, kiedy naprawdę komunikat zostaje doręczony. SendMessage - procedury typu send… są synchroniczne - blokują nadawcę do czasu doręczenia i przetworzenia komunikatu. GetMessage - wywoływana w celu obsługiwania zadań w anonsowanych w jej kolejce wejściowej.

22. Praca pośrednia. wprowadzenie na wyjściu jednostki centralnej taśmy magnetycznej zamiast wolniejszych kart perforowanych wprowadzenie przetwarzania selektywnego - zastosowanie oddzielnego komputera do przegrywania na/z taśmy (pierwsze systemy wielokomputerowe) zysk spowodowany zastosowaniem wielu czytników taśm na wejściu lub wyjściu wymuszenie modułowości monitora rezydującego Zasadniczą zaletą pracy pośredniej było to, że komputer główny nie był już ograniczony przez prędkość czytników kart i drukarek wierszowych, ale jedynie przez prędkość o wiele szybszych jednostek taśm magnetycznych

No udało się….. jak jest (???), to nie jestem pewien, bo nie mogłem na 100% rozczytać

Zaawansowane systemy równoległe:

O zwiększonej przepustowości

O zwiększonej niezawodności

• łagodna degradacja (graceful degradation)

• miękki upadek (fail-soft systems)

Symetryczna wieloprocesorowość (SMP)

• Każdy z procesorów wykonuje identyczną kopię systemu operacyjnego.

• Wiele procesów może być uruchomione naraz bez utraty wydajności.

• Większość współczesnych systemów operacyjnych wspiera SMP.

Asymetryczna wieloprocesorowość

• Każdemu procesorowi przydzielane jest specyficzne zadanie, nadrzędny procesor zarządza i przydziela prace procesorom podporządkowanym.

• Typowe dla bardzo dużych systemów.

Klastry pozwalają dwu lub większej liczbie systemom współdzielić pamięć.

Zapewniają zwiększenie niezawodności.

Asymmetric clustering: jeden z serwerów wykonuje aplikację podczas gdy inne stanowią „gorącą” rezerwę.

Symmetric clustering: wszystkie N hostów wykonują aplikację.

Systemy czasu rzeczywistego mogą być dwóch typów:

• Hard real-time - systemy z twardymi ograniczeniami;

• Soft real-time - systemy z łagodnymi ograniczeniami czasowymi.

• Twarde ograniczenia czasowe (hard real-time):

• Brak pamięci pomocniczej, dane przechowywane w pamięci o krótkim czasie przechowywania lub w pamięciach typu ROM (read-only memory)

• Nie są wspierane przez systemy operacyjne ogólnego przeznaczenia ze względu na stosowany tam podział czasu.

• Łagodne ograniczenia czasowe (soft real-time)

• Ograniczona stosowalność w sterowaniu robotami przemysłowymi

• Użyteczne w takich aplikacjach jak: multimedia, wirtualna rzeczywistość (virtual reality), wymagają pewnych zaawansowanych cech systemu operacyjnego.

Maksymalne wykorzystanie procesora osiąga się przez wieloprogramowość

Wykonanie procesu składa się z następujących po sobie cykli działania procesora i oczekiwania na urządzenia zewnętrzne (CPU-I/O grupa cykli)

Rozkład czasów faz procesora

Wybiera jeden proces spośród przebywających w pamięci procesów gotowych do wykonania i przydziela mu procesor.

• Planowanie w warunkach 1 i 4 nazywa się niewywłaszczeniowym (nonpreemptive).

• Wszystkie pozostałe sytuacje bazują na wywłaszczeniowym schemacie planowania (preemptive).

• Program koordynujący (ekspedytor, dyspozytor ang. dispatcher) jest modułem SO, który przekazuje sterowanie procesora do procesu wybranego przez planistę krótkoterminowego; Do jego obowiązków należy:

• przełączanie kontekstu

• przełączanie do trybu użytkownika

• uruchomienie programu użytkownika od odpowiedniego adresu w celu wznowienia działania programu

• Opóźnienie ekspedycji (ang. Dispatch latency) - czas od momentu zatrzymania jednego procesu i uruchomienia następnego.

• Wykorzystanie procesora - dąży się do tego, aby procesor był nieustannie zajęty pracą

• Przepustowość (ang. throughput) - liczba procesów kończonych w jednostce czasu

• Czas cyklu przetwarzania (Turnaround time) - czas upływający między chwilą powołania procesu w systemie a chwilą zakończenia procesu

• Czas oczekiwania - czas oczekiwania w kolejce procesów gotowych do wykonania

• Czas odpowiedzi - czas upływający między przedłożeniem zamówienia a pojawieniem się pierwszej odpowiedzi, kryterium ważne w systemach interaktywnych.

Planowanie metodą „pierwszy nadszedł - pierwszy obsłużony” (FCFS)

Proces Czas trwania fazy procesora

P₁ 24

P₂ 3

P₃ 3

Procesy nadchodzą w następującym porządku: P₁ , P₂ , P₃

Czas oczekiwania dla P₁ = 0; P₂ = 24; P₃ = 27

Średni czas oczekiwania: (0 + 24 + 27)/3 = 17

Załóżmy, że procesy nadchodzą w kolejności P₂ , P₃ , P₁ .

Diagram Gantta:

Czas oczekiwania dla P₁ = 6; P₂ = 0_; P₃ = 3

Średni czas oczekiwania: (6 + 0 + 3)/3 = 3

Dużo lepiej niż poprzednio.

Możemy mieć tu do czynienia z efektem konwoju, procesy czekają na zwolnienie procesora przez jeden „wielki” proces

Planowanie metodą „najpierw najkrótsze zadanie” (Shortest-Job-First - SJF)

• Z każdym procesem wiąże się długość najbliższej fazy procesora. Procesor zostaje przydzielony procesowi mającemu najkrótszą następną fazę CPU.

• Możliwe dwa schematy postępowania:

• niewywłaszczeniowy - jeżeli procesor został przydzielony procesowi proces nie może być wywłaszczony dopóki nie zakończy swojej fazy procesora.

• wywłaszczeniowy - jeżeli pojawi się nowy proces mający krótszą fazę procesora niż pozostały czas fazy bieżąco wykonywanego procesu - następuje wywłaszczenie tego procesu. Schemat ten nazywany jest Shortest-Remaining-Time-First (SRTF).

Można udowodnić, że SJF jest optymalny - tzn. daje minimalny średni czas oczekiwania dla danego zbioru procesów.

Przykład - niewywłaszczeniowy algorytm SJF

Proces Czas przybycia Czas trwania fazy CPU

P₁ 0.0 7

P₂ 2.0 4

P₃ 4.0 1

P₄ 5.0 4

SJF (bez wywłaszczenia)

Średni czas oczekiwania = (0 + 6 + 3 + 7)/4 = 4

Przykład - wywłaszczeniowy
algorytm SJF

Proces Czas przybycia Czas trwania fazy

P₁ 0.0 7

P₂ 2.0 4

P₃ 4.0 1

P₄ 5.0 4

SJF (wywłaszczeniowy)

Średni czas oczekiwania = (9 + 1 + 0 +2)/4 = 3

Planowanie na podstawie priorytetu

• Każdemu procesowi przypisujemy priorytet (pewną liczbę całkowitą)

• Procesor przydziela się temu procesowi, który ma najwyższy priorytet (mniejsza liczba Ⴚ wyższy priorytet).

• Wywłaszczeniowe

• Niewywłaszczeniowe

• Zauważmy, że SJF jest algorytmem priorytetowym, w którym priorytet (p) jest odwrotnością następnej (przewidywanej) fazy procesora.

• Problem Ⴚ nieskończone wstrzymywanie procesów - procesy o niskich priorytetach mogą oczekiwać w nieskończoność

Rozwiązanie Ⴚ Wprowadzenie starzenia się procesów - stopniowe podwyższanie priorytetów procesów długo oczekujących w systemie.

Planowanie rotacyjne - ang. Round Robin (RR)

• Każdy proces otrzymuje niewielką jednostkę czasu procesora (kwant czasu), zwykle 10-100 milisekund. Po upływie tego czasu proces jest wywłaszczany i umieszczany na końcu kolejki procesów gotowych.

• Jeżeli mamy n procesów w kolejce procesów gotowych i kwant czasu jest równy q, to każdy proces otrzymuje 1/n czasu procesora porcjami, których wielkość nie przekracza q jednostek czasu. Żaden z procesów nie oczekuje dłużej niż (n-1)q jednostek czasu.

• Wydajność

• q bardzo duże პ FCFS

q małe პ q musi być odpowiednio duże w odniesieniu do czasu przełączania kontekstu.

Przykład algorytmu RR (q = 20)

Proces Czas fazy CPU

P₁ 53

P₂ 17

P₃ 68

P₄ 24

Diagram Gantta:

Zwykle, większa wartość średniego czasu przetwarzania niż w SJF, lecz lepszy czas odpowiedzi.

Wielopoziomowe kolejki

• Kolejka procesów gotowych jest rozdzielona na osobne kolejki:
  procesów pierwszoplanowych (interactive) i procesów drugoplanowych (wsadowych - batch)

• Każda kolejka ma własny algorytm planowania,
  procesów pierwszoplanowych - RR, procesów drugoplanowych - FCFS

• Musi istnieć planowanie między kolejkami.

• Stałopriorytetowe planowanie wywłaszczające; (np., kolejka pierwszoplanowa może mieć absolutny priorytet nad kolejką procesów wsadowych). Możliwość blokowania.

• Operowanie przedziałami czasu (Time slice) - każda kolejka dostaje pewną porcję czasu procesora w którym może planować przydział dla swoich procesów; na przykład, 80% dla pierwszoplanowych - RR

• 20% wsadowe - FCFS

• Proces może być przemieszczany między różnymi kolejkami; pewien sposób implementacji „starzenia się” procesów.

• Planista wielopoziomowych kolejek ze sprzężeniem zwrotnym jest określony za pomocą następujących parametrów:

• Liczba kolejek

• Algorytm planowania dla każdej kolejki

• Metoda używana do decydowania o awansowaniu procesu do kolejki o wyższym priorytecie

• Metoda dymisjonowania procesu do kolejki o niższym priorytecie

Metoda określająca kolejkę, do której trafia proces potrzebujący obsługi

Trzy kolejki:

Q₀ - kwant czasu 8 ms

Q₁ - kwant czasu 16 ms

Q₂ - FCFS

Planowanie

Nowy proces otwiera kolejkę Q₀ i jest obsługiwany na zasadzie FCFS. Kiedy proces uzyskuje CPU, zadanie wykonuje się przez 8 ms. Jeżeli nie zostanie zakończone jest przenoszone do kolejki Q₁.

Kolejka Q₁ jest obsługiwana na zasadzie FCFS i proces otrzymuje 16 ms. Jeżeli i teraz nie zostanie zakończony, jest wywłaszczany i przenoszony do kolejki Q₂.

Przykład działania algorytmu bankiera

5 procesów P₀ - P₄; 3 typy zasobów: A (10 egzemplarzy), B (5 egzemplarzy), C (7 egzemplarzy).

Migawkowy stan systemu w momencie T₀:

Przydział Max Dostępne

A B C A B C A B C

P₀ 0 1 0 7 5 3 3 3 2

P₁ 2 0 0 3 2 2

P₂ 3 0 2 9 0 2

P₃ 2 1 1 2 2 2

P₄ 0 0 2 4 3 3

Zawartość macierzy Potrzebne jest określona jako: Max - Przydzielone.

Potrzebne

A B C

P₀ 7 4 3

P₁ 1 2 2

P₂ 6 0 0

P₃ 0 1 1

P₄ 4 3 1

System jest obecnie w stanie bezpiecznym. Istnieje sekwencja < P₁, P₃, P₄, P₂, P₀> spełniająca kryterium bezpieczeństwa.

Sprawdzamy czy Zamówienia Ⴃ Dostępne (to jest, (1,0,2) Ⴃ (3,3,2) პ spełnione. Zamówienie zrealizowane, otrzymujemy:

Przydzielone Potrzebne Dostępne

A B C A B C A B C

P₀ 0 1 0 7 4 3 2 3 0

P₁ 3 0 2 0 2 0

P₂ 3 0 1 6 0 0

P₃ 2 1 1 0 1 1

P₄ 0 0 2 4 3 1

• Wykonujemy algorytm bezpieczeństwa i znajdujemy, że <P₁, P₃, P₄, P₀, P₂> spełnia wymagania bezpieczeństwa.

• Czy zamówienie (3,3,0) dla P₄ może zostać spełnione?

• Czy zamówienie (0,2,0) dla P₀ może zostać spełnione?

• Pięć procesów P₀ - P₄; trzy typy zasobów
  A (7 egzemplarzy), B (2 egzemplarzy)
  oraz C (6 egzemplarzy).

• Moment T₀:

Przydzielone Zamówienia Dostępne

A B C A B C A B C

P₀ 0 1 0 0 0 0 0 0 0

P₁ 2 0 0 2 0 2

P₂ 3 0 3 0 0 0

P₃ 2 1 1 1 0 0

P₄ 0 0 2 0 0 2

Sekwencja <P₀, P₂, P₃, P₁, P₄> daje Finish[i] = true dla wszystkich i.

P₂ zamawia dodatkowy zasób typu C.

Zamówienia

A B C

P₀ 0 0 0

P₁ 2 0 1

P₂ 0 0 1

P₃ 1 0 0

P₄ 0 0 2

Stan systemu?

Można zwolnić zasoby P₀, lecz nie wystarcza to do zaspokojenia zapotrzebowania procesów.

Istnieje blokada, obejmująca P₁, P₂, P₃, i P₄.

Problem dynamicznego przydziału pamięci

Jak na podstawie listy wolnych obszarów (dziur) zrealizować zamówienie
na obszar o rozmiarze n. Strategie wyboru:

• Pierwsza pasująca: Przydziela się pierwszą „dziurę” o wystarczającej wielkości.

• Najlepiej pasująca: Przydziela się najmniejszą z dostatecznie dużych „dziur”; niezbędne jest przeszukanie całej listy, chyba że jest ona uporządkowana wg rozmiaru.

Najgorzej pasująca: Przydziela się największą „dziurę”; niezbędne jest przeszukanie całej listy. Strategia taka pozostawia po przydziale największą dziurę.

Symulacje wykazały, że strategie pierwsza pasująca i najlepiej pasująca są lepsze niż wybór największej „dziury” pod względem czasu, jak i wykorzystania pamięci.

• Fragmentacja zewnętrzna - suma wolnych obszarów w pamięci wystarcza na spełnienie zamówienia, ale nie stanowi spójnego obszaru.

• Fragmentacja wewnętrzna - przydzielona pamięć może być niewiele większa niż zamawiana; ta dodatkowa pamięć znajduje się wewnątrz jednostki przydziału i nie będzie wykorzystana.

• Zmniejszenie fragmentacji przez upakowanie

• Przemieszczanie zawartości pamięci w taki sposób aby scalić wszystkie wolne obszary pamięci w jeden blok.

• Możliwość upakowania daje tylko dynamiczne przemieszczanie adresów, wykonywane podczas działania procesu.

• Problem transmisji WE/WY

• Zablokowanie procesu w pamięci, gdy wykonał zamówienie na operację WE/WY.

Realizacja operacji WE/WY jedynie do buforów SO.

16

0

rb=30040

rg=120900

420940

300040

monitor

zadanie 1

zadanie 2

zadanie …

zadanie n

program obsługi urządzeń w pamięci ROM BIOS

programy obsługi urządzeń z poziomu MS-DOS

rezydujące programy systemowe

programy użytkownika

---