% Impala Operating System
%
% Copyright (C) 2009 University of Wroclaw. Department of Computer Science
%    http://www.ii.uni.wroc.pl/
% Copyright (C) 2009 Mateusz Kocielski, Artur Koninski, Pawel Wieczorek
%    http://bitbucket.org/wieczyk/impala/
% All rights reserved.
%
% Redistribution and use in source and binary forms, with or without
% modification, are permitted provided that the following conditions
% are met:
% 1. Redistributions of source code must retain the above copyright
%  notice, this list of conditions and the following disclaimer.
% 2. Redistributions in binary form must reproduce the above copyright
%  notice, this list of conditions and the following disclaimer in the
%  documentation and/or other materials provided with the distribution.
%
% THIS SOFTWARE IS PROVIDED BY AUTHOR AND CONTRIBUTORS ``AS IS'' AND
% ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
% IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
% ARE DISCLAIMED.  IN NO EVENT SHALL AUTHOR OR CONTRIBUTORS BE LIABLE
% FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
% DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
% OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
% HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
% LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
% OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
% SUCH DAMAGE.
%
% $Id$

\section{Wielozadaniowość.}

Zadania procesora są reprezentowane przez wątki (\texttt{thread\_t}). Każdy
z~wątków dostaje kwant czasu na~wykorzystanie procesora, dzięki czemu
użytkownik może odnieść wrażenie, że uruchomione przez niego zadania działają
jednocześnie. Za przydział czasu procesora jest odpowiedzialny program
planisty omówiony w \ref{SCHEDULER}.

Wątek posiada w~sobie między innymi następujące informacje:
\begin{itemize}
 \item kontekst, służący do~zachowywania jego stanu
 \item proces do, którego przynależy wątek
 \item adres procedury wejściowej, od~której rozpoczyna się działanie zadania
 \item adres stosu użytkownika i jego rozmiar
 \item adres stosu alternatywnego i jego rozmiar
 \item przestrzeń adresowa, w której działa to~zadanie (wspólna dla wszystkich
    wątków w obrębie tego samego procesu)
\end{itemize}

Wątki procesora wykonujące kod użytkownika potrzebują dwóch stosów.
Pierwszy stos jest przeznaczony do~standardowego użytku. Stos
alternatywny natomiast jest wykorzystywany wtedy, kiedy procesor wywłaszcza
zadanie
obsługując przerwanie. Wątki wykonujące kod systemu utożsamiają ze~sobą
te~dwa stosy.

Stosy użytkownika są jego prywatnymi stosami, tzn. istniejącymi jedynie
w~jego przestrzeni adresowej, natomiast stosy alternatywne znajdują się
w~przestrzeni jądra, dzięki czemu są zawsze dostępne dla systemu.

Adres procedury wejściowej jest wykorzystywany jeżeli dany wątek nie miał
dotąd ani razu przydzielonego czasu procesora - np. został dopiero utworzony.
W takim przypadku jego działanie rozpoczyna się od~adresu procedury wejściowej,
w~przeciwnym od~adresu zapisanego w~kontekście.

Kontekst procesora zawiera w~sobie takie informacje jak ramka przerwania,
którą zapisuje procesor na~stos alternatywny przy wywłaszczeniu przez
przerwanie oraz pomocniczy schowek na~rejestry procesora.

\subsection{Zmienianie kontekstu procesora.}

Mechanizm zmiany kontekstu procesora jest oparty o~mechanizm obsługi przerwań
przez procesor. Przed rozpoczęciem omawiania mechanizmu zmian kontekstu
wyszczególnimy kilka faktów, związanych z~pracą procesora.
\begin{itemize}
 \item Procesor podczas wywoływania procedury kładzie na~stos adres
       aktualnie wykonywanej instrukcji, tak aby po zakończeniu procedury
       mógł wrócić do~kodu ją wywołującego, zapisane w ten sposób
       adresy na~stosie tworzą ,,ślad wywołań''.
 \item Stos w procesorze jest definiowany przez adres w~rejestrze
       \texttt{esp}, a operacje na~stosie pobierają i~zapisują dane
       pod tym adresem odpowiednio go modyfikując.
\end{itemize}


Pod obsługę zegara systemowego, którego przerwanie jest generowane~z
częstotliwością 100Hz, jest podpięty program planisty, który jeżeli zdecyduje
się zmienić kontekst procesora, tzn. wykonywany przez procesor wątek,
to~przekazuje sterownie do~procedury \texttt{thread\_switch} przekazując jej
deskryptor aktualnie wykonywanego wątku (\texttt{curthread}) oraz wątku
na~jaki ma~nastąpić zmiana.

Wspomniana procedura zapisuje aktualne rejestry procesora do~pomocniczego
schowka w~kontekście w~deskryptorze aktualnie wykonywanego wątku, a~następnie 
wczytuje zachowane wcześniej rejestry ze schowka drugiego wątku.

Ponieważ w~rejestrach procesora są zapisane adresy lokalizujące stos
to powyższa operacja powoduje ,,podmianę'' aktualnie wykonywanego stosu
procesora na ten, jaki był w momencie zapisywania rejestrów drugiego wątku
(to znaczy dokładnie wtedy, kiedy planista uruchomił \texttt{thread\_switch}
podczas pracy drugiego wątku). Ponieważ na~stosie jest zapisany ślad
wywołań, to po podmianie stosu procesor zachowa się dokładnie tak, jak by się
zachował wykonując drugi wątek po~zachowaniu jego rejestrów. Bardzo podobny
mechanizm istnieje w~języku C w~procedurach \texttt{setjmp} i \texttt{longjmp}.
Kończąc po kolei procedury procesor wróci do~tej, którą wywołał procesor
do~obsługi przerwania zegara podczas pracy drugiego wątku, a jej
zakończenie przywróci stan procesora z~zachowanej ramki przerwania,
zawierającej stan drugiego wątku. Ta operacja jest prawidłowa, ponieważ
ramki przerwań są zapisywane na~stosach alternatywnych, które są dostępne
w~przestrzeni jądra.

Jeżeli drugi wątek nie miał dotąd przydzielonego czasu procesora,
to~procedura zmiany kontekstu nie miała okazji zachować jego
rejestrów w~schowku, a procesor zapisać ramkę przerwania na~jego stosie
alternatywnym. W takim wypadku uruchamiana jest procedura
\texttt{thread\_resume}, która ręcznie buduje ramkę stosu, aby oszukać
procesor, że powraca do~obsługi zadania, które wcześniej wywłaszczył.
Jako adres wywłaszczonej instrukcji jest podawana procedura wejściowa.

W schowku na~rejestry procesora jest zapisywany również rejestr kontrolny
procesora \texttt{cr3} zawierający adres katalogu stron, tak więc wczytując
adresy z~tego schowka następuje również podmiana wirtualnej przestrzeni
adresowej użytkownika.

\subsection{Rozwidlanie procesów.}

Jedyną drogą stworzenia nowego procesu w~systemie UNIX jest rozwidlenie
istniejącego procesu. Zgodnie z~semantyką nadaną przez standard nowy proces
dziedziczy po~rodzicu kopię jego deskryptorów plików, przestrzeni adresowej
oraz środowiska.

Jeżeli w~procesie rodzica działało wiele wątków to~nowy zawiera tylko jeden,
który jest kopią wątku zlecającego systemowi zadanie rozwidlenia.

Za~obsługę rozwidlenia odpowiedzialna jest procedura \texttt{proc\_fork}.
Po stworzeniu nowego wątku w~systemie kopiowany jest stos alternatywny
oraz kontekst wątku~wywołującego. Skopiowany stos zawiera ramkę przerwania
z~zachowanym stanem wątku wywołującego, co umożliwia oszukania procesora
w~podobny sposób jak w~procedurze \texttt{thread\_resume} i~uruchomienie
nowy wątek z~pożądanym stanem.

\subsection{Synchronizacja.}

Ważnym elementem implementacji mechanizmów synchronizacji są niepodzielne
instrukcje procesora, tzn takie których nie można wywłaszczyć w~trakcie
ich wykonywania. Instrukcje porównania oraz~zapisu generowane przez kompilator
spełniają tę właściwość. Moduł obsługi platformy
sprzętowej musi dostarczyć jeszcze procedurę \texttt{atomic\_change\_int}
modyfikującą komórkę pamięci i~zwracającą jej starą wartość w~sposób
niepodzielny. Gdyby procedura nie spełniała żądanej własności,
to pomiędzy pobraniem starej wartości, a zapisaniem nowej mogłoby zostać
wykonane wywłaszczenie, podczas którego wartość komórki pamięci została
zmodyfikowana. W takim wypadku wszelkie decyzje podjęte na~podstawie
starej wartości, zwróconej przez procedurę, mogłyby być błędne.

Najprostszym mechanizmem synchronizacji są wirujące zamki, wykorzystujące
wprost niepodzielne instrukcje procesora. Taki zamek jest opisywany przez
jedną komórkę pamięci przyjmującą wartość \texttt{SPINLOCK\_LOCK}
lub~\texttt{SPINLOCK\_UNLOCK} odpowiednio do~stanu blokady. 

Operacja zamknięcia używa wspomnianej wcześniej procedury aby ustawić
stan blokady na~\texttt{SPINLOCK\_LOCK}. Jeżeli stara wartość komórki
pamięci była równa \texttt{SPINLOCK\_UNLOCK} to~z~niepodzielności użytej procedury
wynika, że nikt inny nie mógł odczytać ani zmodyfikować jej wartości i~udało
się pomyślnie zmienić stan blokady.
Jeżeli stara wartość komórki pamięci była równa \texttt{SPINLOCK\_LOCK},
to również z~niepodzielności tej procedury wynika, to że blokada została
zamknięta przez kogoś innego. W takim~wypadku procedura zamknięcia zamka
kręci się w~miejscu (wiruje), dopóki nie uda się jej zamknąć blokady.

Ten sposób synchronizacji nie zapewnia, że wątki nie będą głodzone (oczekiwać
w~nieskończoność), dodatkowo oczekiwanie na~zwolnienie blokady jest aktywne
co marnuje czas pracy procesora.

Innym rodzajem blokady są zamki \texttt{mutex\_t} (\emph{mutual exclude}),
których klienci są usypiani na~czas założonej blokady. Zamki wewnętrznie
używają kolejki FIFO do~kontrolowania kolejności budzenia wątków, chcących
wejść do chronionej sekcji krytycznej - ta strategia eliminuje problem
głodzenia. Wewnętrzna struktura danych tej blokady jest chroniona za~pomocą
wirujących zamków. Idea tych zamków odróżnia je od semaforów tym, że z~tą
blokadą jest związana informacja o właścicielu, tzn wątku który zamknął
blokadę - w przeciwieństwie do semaforów jedynie on ma prawo do~odblokowania.

\label{pthread_condvar}
Zmienna warunkowa jest~mechanizmem ściśle powiązanym z~mechanizmem blokad.
Jej zadanie to umożliwienie biernego oczekiwania na~zdarzenie.
Jest on sprzężony z~wybraną blokadą w~celu wykonywania niepodzielnej operacji
jej zwolnienia oraz uśpienia wątku.

Mechanizm jest standardowo wykorzystywany do~implementacji kolejek, sama
blokada może jedynie chronić sekcje krytyczne procedur wysłania i odebrania
wiadomości do kolejki, lecz uniemożliwia oczekiwanie w~przypadku braku
wiadomości do odebrania. Mechanizm wykorzystuje się tak, że gdy nie ma
wiadomości do~odebrania to klient jest usypiany, a blokada zwalniana.
Dzięki niepodzielności nie jest możliwa sytuacja, w~której pomiędzy uśpieniem
a zwolnieniem blokady ktoś dostarczy wiadomość do kolejki.

Dostarczenie zdarzenia budzącego jest możliwe do~jednego wątku lub
do~wszystkich naraz,  może je dostarczyć jedynie właściciel blokady sprzężonej
z~zmienną warunkową. Zdarzenie jest dostarczane przy wyjściu z~sekcji
krytycznej przez klienta je zgłaszającego. Budzony wątek dostaje od~razu
zamknięty zamek, dzięki czemu powraca on do~swojej sekcji krytycznej.

Nasza implementacja zamków \texttt{mutex\_t} zawiera w~sobie mechanizm
zmiennej warunkowej.

\subsection{Biblioteka wątków użytkownika.}

Istnieją trzy modele realizacji wątków po stronie użytkownika:
\begin{itemize}
 \item M:1 -
wiele wątków użytkownika jest zarządzanych przez niego samego, a jądro
systemu operacyjnego widzi wszystkie jako jeden wątek
    (nie wie o ich istnieniu).

 \item M:N -
wątki użytkownika są łączone w~grupy, które są widziane jako pojedyncze
wątki dla jądra.

 \item 1:1 -
każdy wątek użytkownika jest widziany przez jądro.

\end{itemize}

W naszym systemie wybraliśmy trzeci model. 
Do zarządzania wątkami dostarczone są odpowiednie wywołania systemowe
pozwalające tworzyć nowe wątki, oczekiwać na~ich zakończenie oraz~zarządzać
blokadami.

Identyfikatorami wątków jakimi posługuje się biblioteka są adresy
deskryptorów wątków w~jądrze, ponieważ jądro nie może ufać dostarczonym
adresom od użytkownika (podczas wskazywania identyfikatorem, którego wątku
tyczy się dana operacja) każdy proces posiada listę swoich wątków. Identyfikator
wątku jest weryfikowany poprzez test bycia obecnym na~tej liście.

Blokadami tworzonymi przez użytkownika są blokady \texttt{mutex\_t} w~jądrze
systemu. Pomysł z~identyfikatorami i~badaniem ich poprawności jest ten sam,
co wyżej omówiony.

Standard \emph{POSIX Threads} definiuje procedury i semantykę wątków
użytkownika. W naszym systemie zaimplementowaliśmy podzbiór tego standardu
pozwalający na~prostym zarządzaniu wątkami, tworzeniu blokad oraz zmiennych
warunkowych.

Wewnętrzne struktury biblioteki są chronione przez wirujące zamki.

\subsection{Szeregowanie zadań.} \label{SCHEDULER}

Zaimplementowany w systemie algorytm szeregowania zadań został oparty na
algorytmach planistów zastosowanych w systemach 4.3BSD oraz SVR4. Dokładny 
opis tych
algorytmów znajduje się w~\cite{unixjadro}. 

Omówimy tutaj jedynie ogólny zarys planisty oraz różnice w stosunku do pierwowzoru. 
Planista przydziela procesom priorytet na podstawie ich ostatniego zachowania w systemie 
(tzn. zużycia czasu procesora oraz innych statystyk) oraz poziomu uprzejmości (nice).
Priorytet jest liczbą z~zakresu od~$0$ do~$127$, procesy o~mniejszej wartości
priorytetu są traktowane jako ważniejsze, można więc rozumieć tę wartość jako
karę nakładaną na~proces. Wszystkie wątki w ramach procesu traktowane są
jednakowo i~wszystkie posiadają priorytet równy priorytetowi procesu. Przestrzeń
priorytetów podzielona jest na~$32$ grupy po~$4$ wartości w każdej grupie,
kolejka $Q_i$ odpowiada za~zbiór priorytetów $i,i+1,i+2,i+3$.
Procesy przynależą do odpowiednich kolejek, za rozsiewanie ich odpowiada
okresowo (co \texttt{SCHED\_RESCHEDULE} kwantów czasu) uruchamiana funkcja 
\texttt{\_\_resched}, która dokonuje podziału na podstawie listy \texttt{run\_queue}, 
w której znajdują się wątki gotowe do uruchomienia, po~wykonaniu tej funkcji 
następuje wybranie niepustej
kolejki zawierającej najniższe priorytety i~w ramach tej kolejki planista
realizuje podejście zwane algorytmem karuzelowym. Algorytm karuzelowy jest
prostym sposobem szeregowania zadań polegającym na organizacji procesów w listę
cykliczną, a następnie przydzielanie każdemu z wątków kolejno jednakowego kwantu
czasu. Procesy znajdujące się poza tą kolejką nie są
brane pod uwagę aż do~następnego wywołania funkcji \texttt{\_\_resched}, która
realizuje także uaktualnianie priorytetu procesów wg. wzoru:
\[ \mbox{priorytet} = 2\cdot\mbox{poziom\_uprzejmości} 
    + \mbox{wykorzystanie\_procesora}/2 \]
Wszystkie opisywane przez wzór wartości przechowywane są w bloku kontrolnym
procesu.
 Algorytm umożliwia preferowanie pewnych zadań przez użytkownika systemu za~pomocą poziomu
uprzejmości, oraz uwzględnia wykorzystanie procesora przez poszczególne procesy, co umożliwia
wybór zadań interakcyjnych (tj. edytory tekstu) przed zadaniami obliczeniowymi
(tj. kompilatory). 
