47. Algorytmy szeregowania zadań
        

        Algorytm szergowania tzw. planista lub z ang. scheduler odpowiada 
za przydzielenie

dostępu do procesora dla poszczególnych 
          procesów, dodatkowo musi uwzględniać priorytety, gotowość do 

działania oraz
przeciwdziałać zagłodeniu procesu (czyli 

        niedopuścić żeby dany proces nigdy nie był wykonany)
        W systemach operacyjnych czasu rzeczywistego najważniejsze aby dany 

proces skończył
się przed zaplanowanym dla nie go czasem.

        Rozróżniamy dwa rodzaje planistów: krótkoterminowy który wybiera 
procesy spośród

gotowych do wykonania (musi być bardzo szybki)
        oraz długoterminowy który wybiera zadania z pamięci masowej i 

ładuje do pamięci
operacyjnej.

        Obecne systemy oparte są o wielozadaniowość z wywłaszczeniem
        * FIFO - algorytm powszechnie stosowany, jeden z prostszych w 

realizacji, dający
dobre

        efekty w systemach ogólnego przeznaczenia; zadanie wykonuje się aż 
nie zostanie

        wywłaszczone przez siebie lub inne zadanie o wyższym priorytecie;
        * Planowanie rotacyjne (round-robin) - każde z zadań otrzymuje 

kwant czasu; po
        spożytkowaniu swojego kwantu zostaje wywłaszczone i ustawione na 

końcu kolejki;
        * Planowanie sporadyczne - zadania otrzymują tak zwany "budżet 

czasu"; ten algorytm
        pomaga pogodzić wykluczające się reguły dotyczące szeregowania 

zadań okresowych i
        nieokresowych; wciąż nie jest implementowany przez wiele systemów, 

jednak znalazł
się w

        standardzie POSIX;
        Mniej powszechne

        Trzy wymienione wyżej algorytmy są stosowane najczęściej. Jednak 
lista algorytmów

        szeregowania jest bardzo długa i znajdują się na niej między innymi 
jeszcze takie

algorytmy
        jak:

        * FCFS (first come, first start) - Bardzo podobny do kolejki FIFO - 
Pierwszy

przyjdzie,
        pierwszy wykonany. Algorytm ten dokonuje najsprawiedliwszego 

przydziału czasu
(każdemu

        według potrzeb), jednak powoduje bardzo słabą interakcyjność 
systemu - pojedynczy

długi
        proces całkowicie blokuje system na czas swojego wykonania, gdyż 

nie ma priorytetów
        zgodnie z którymi mógłby zostać wywłaszczony. Algorytm ten stosuje 

się jednak z
        powodzeniem w systemach wsadowych, gdzie operator ładuje zadania do 

wykonania, a one
        wykonują się do skutku.

        * SJF (shortest job first) - Najpierw najkrótsze zadanie. Jest 
algorytmem

optymalnym ze
        względu na najkrótszy średni czas oczekiwania. W wersji z 

wywłaszczaniem, stosowana
jest

        metoda: najpierw najkrótszy czas pracy pozostałej do wykonania. 
Problemem tego

algorytmu
        jest głodzenie długich procesów - może się zdarzyć, że cały czas 

będą nadchodzić
krótsze

        procesy, a wtedy proces dłuższy nigdy nie zostanie wykonany.

48. Model sekcji krytycznej i warunki jego poprawnego funkcjonowania.

        * Sekcja krytyczna to ciąg operacji na pewnym zasobie 
współdzielonym (zazwyczaj

pamięci) który musi być
        wykonany tylko przez jeden proces z potencjalnie wielu innch. 

Proces przed
wejściem do SK musi przejść przez sekcje

        wejściową, gdy takowy już jest w SK wówczas inne w sekcji 
wejściowej nie

mogą jej przejść i są wstrzymywane do chwili
        przejścia procesu z SK do sekcji wyjściowej (która powiadamia ich o 

opuszczeniu),
wtedy jeden z procesów z sekcji wejściowej zostanie wpuszczony do SK.

          
        * Sekcji krytycznej musi spełniać kilka warunków aby działać 

dobrze:  
         + wzajemne wykluczenie - tylko jeden proces może przebywać i 

wykonywać sekcje
krytyczną

         + warunek postępu - (ograniczona liczba wejść) tylko procesy w 
sekcji wejściowej

mogą kandydować do wejścia w sekcje krytyczną
         + ograniczone czekanie - każdy proces aplikujący do sekcji 

krytycznej musi kiedyś
do niej wejść (chyba, że sam zrezygnuje) 

         
        * Przykładowy algorytm 

         + algorytm piekarniczy, każdy z procesów jest numerowny nazwijmy 
ten numer p,

dodatkowo wejścia do sekcji krytycznej są także numerowane nazwijmy je k 
           wejść może proces o najniższym parze numerów (p, k) jeżeli 

sekcja jest wolna. A
dlaczego para? Poniważ możliwe, że dwa procesy dostaną ten sam

           numer k (a identyfikator p jest zawsze unikalny). Więc dlaczego 
numery k skoro

wystarczą p? Nie każdy z procesów p będzie aplikował do sekcji 
           krytycznej.

        * Znane sposoby realizacji sekcji krytycznej:
         + semafory (binarny, liczbowy)

          + mutexy
         + moniotry (wysoko poziomowe mechanizmy jezyków programowania)

49. Stronicowanie i stronicowanie na żądanie – wsparcie sprzętowe, korzyści

wynikające ze stosowania tych technologii.

        * Stronicowanie jest jednym ze sposobów rozwiązania problemu 
zewnętrznej

fragmentacji polegającym na dopuszczeniu nieciągłości 
          logicznej przestrzeni adresowej procesu. Zostało użyte przez 

polskiego inżyniera
Jacka Karpińskiego w architekturze komputera K-202.

          Podstawowa metoda stronicowania:
         • Pamięć fizyczna dzielona jest na bloki stałej długości zwane 

ramkami.
         • Pamięć logiczna dzielona jest na bloki stałej długości zwane 

stronami.
         • Rozmiary stron i ramek są identyczne.

         • Przy wykonywaniu procesu, strony z pamięci pomocniczej 
wprowadzane są w dowolne

ramki pamięci operacyjnej.
         W systemach komputerowych podział pamięci na mniejsze obszary o 

ustalonej lub
zmiennej wielkości przydzielanie tym blokom adresów fizycznych lub 

logicznych.
         Historia. Stronicowanie pamięci fizycznej wykonywane było z powodu 

ograniczenia
przestrzeni adresowej procesora (stronicowanie fizyczne).

        * Stronicowanie na żądanie (angielskie demand paging), popularny 
algorytm

stronicowania, opóźniający sprowadzanie stron z dysku do chwili, 
          gdy zabraknie ich w wykonywanym procesie (czyli strona 

sprowadzana jest z dysku
do pamięci wtedy gdy jest potrzebna); 

          rzadko stosowany w postaci czystej