Scheduler Miniksa dobrze radzi sobie z zarządzaniem procesami intensywnymi obliczeniowo. Priorytet takich procesów (np. primes
z lab. 11) jest szybko obniżany, przez co system nie traci responsywności nawet, gdy dużo obliczeń odbywa się w tle. Tak dobrze nie jest jednak w przypadku procesów IO-intensywnych.
Spójrzmy na czas działania komendy:
# time grep -R /usr/src/kernel/ * real 0m0.050s user 0m0.000s sys 0m0.050s
Teraz obciążymy system 5 procesami:
# grep -R asdfasdf / & 773 # grep -R asdfasdf / & ...
I zobaczymy jak wpływa to na wynik:
# time grep -R /usr/src/kernel/ * real 0m0.366s user 0m0.000s sys 0m0.033s
Widać tu duże spowolnienie. Jest ono odczuwalne w całym systemie. Zauważmy, że czas user
, czyli to ile proces spędził na obliczeniach, jest bliski 0s. Oznacza to, że gdy program grep
dostał już dane z dysku, to wykonał na nich tylko minimalną liczbę operacji - przejrzał bufor w czasie O(n).
Czas sys
reprezentuje czas spędzony w jądrze systemu, na rzecz tego procesu. Więc sam odczyt z dysku zajął około 0.033s i podobnie jak w pierwszym przykładzie, jest on najkosztowniejszą częścią wykonania tego polecenia. Całość zajęła jednak 0.366s. Ten czas jest właśnie odczuwalnym opóźnieniem wykonania procesu.
Dlaczego user + sys != real
? Ponieważ równocześnie wykonywało się jeszcze kilka innych IO-intensywnych procesów. Jądro obsługiwało wiele zapytań naraz i choć ilość pracy potrzebna naszemu procesowi była warta tylko 0.033s, to wykonanie jej zajęło 10 razy dłużej. Potwierdza to komenda top
, gdyż na wydruku faktycznie widać, że kernel zajmuje 80-90% czasu procesora.
Niestety scheduler śledzi tylko to ile pracy wykonuje sam proces, nie biorąc pod uwagę ile pracy przysparza on innym procesom - a w szczególności jądru. W efekcie, po uruchomieniu kilku IO-intensywnych procesów responsywność systemu gwałtownie spada.
Celem niniejszego zadania jest poprawienie tego problemu, czyli sprawienie, aby w drugim przypadku komenda grep -R /usr/src/kernel/*
wykonała się równie szybko jak w pierwszym.
Należy zmodyfikować domyślny serwer sched
tak by ograniczał wykonywanie procesów zużywających dużo czasu systemowego. Nie wystarczy jednak obniżyć priorytet takich procesów. Przez większość czasu nie ma ich bowiem w kolejce procesów gotowych, ponieważ są zablokowane na opracjach IO. Zamiast tego, należy przyznawać im mniej kwantów czasu wykonania, aby blokowały się zanim zdążą zlecić operacje IO.
W tym celu scheduler powinien dla każdego procesu przechowywać pulę żetonów pozwalających mu na dostęp do systemu. Następnie, za każdym razem gdy proces wyczerpie kwant czasu, należy obliczyć czas sys
zużyty od ostatniego sprawdzenia i odjąć jego wartość z puli żetonów. Może ona przy tym stać się ujemna, ale jest to akceptowalne, gdyż nie mamy kontroli na tym ile jądru zajmie dana operacja IO. Nowy kwant przydzielamy tylko, gdy pula jest dodatnia.
Przez żeton będziemy rozumieli jednostkę, w której naliczany jest czas sys
. Jest to tak zwany tik. Przechowuje się go w zmiennej clock_t
typu int
. Naliczanie tików odbywa się w /usr/src/kernel/clock.c
, w tempie ok. 60/s.
Uzyskanie dobrej responsywności systemu będzie zależało od polityki uzupełniania puli żetonów przypisanych procesom. Chcemy, aby nowy proces dostawał pewną wartość na starcie - powiedzmy odpowiednik ok. 0.1s czasu systemu - co da mu przewagę nad procesami działającymi od dawna. Jednocześnie chcemy ograniczyć ilość żetonów jakie zgromadzić może każdy proces, aby zgromadzoną pulą nie był w stanie zdominować innych procesów - tu również ograniczmy się do równowartości 0.1s.
Dalej przydzielanie żetonów będzie odbywało się wedle poniższych reguł:
do_noquantum
) i co 5s (w funkcji balance_queues
)
Dzielenie puli nowych żetonów przez 2 jest potrzebne, gdyż inaczej w systemie byłoby zbyt dużo żetonów. Nowy proces musiałby czekać pomimo tego, że na starcie ma ich sporą pulę. Redukcja liczby przyznawanych żetonów rozwiązuje ten problem, kosztem poważnego zmniejszenia przepustowości całego systemu. W rozwiązaniu produkcyjnym należało by precyzyjnie dobrać (lub dynamicznie zarządzać) tą stałą, ale nam wystarczy by była to liczba 2.
/usr/src/kernel/proc.h
.
/usr/src/servers/sched
. Opis jego działania znajduje się w materiałach do lab. 11. Wszelki zmiany należy opatrzyć
komentarzem w postaci:
/** CHANGED krótki opis zmiany */
make install
w katalogu sched
. Trzeba zbudować nowy obraz jądra.
cd /usr/src/releasetools/ make # wyświetla dostępne opcje make hdboot # buduje jądro
kernel panic
), należy wybrać opcję 6 przy starcie systemu.
sched
(reinstall_sched.sh
):
cd /usr/src/servers/sched/ make make install cd /usr/src/releasetools/ make do-hdboot # pakuje sam obraz pomijając wcześniejsze kroki hdboot reboot
clock()
- zamiast tego można użyć getuptime()
.
fsck
przy starcie). Co prawda wpłynie to negatywnie na działanie systemu, ale w zadaniu nie należy się tym przejmować.
kernel panic
podczas uruchamiania
kernel panic
przy poleceniach:
find / > /dev/null
grep -R size_t / > /dev/null
solab@mimuw.edu.pl
.
Temat listu powinien zawierać napis "SO Zad 4" oraz imię i nazwisko autora rozwiązania.
Do maila dołączona powinna być paczka .tgz
z rozwiązaniem.
Należy ją przygotować w następujacy sposób:
zadanie4_so_numer_indeksu
zadanie4_so_234567/usr/src/servers/sched/scheduler.c
).
W paczce umieszczamy wyłącznie pliki (wszystkie) zmodyfikowane względem maszyny używanej na labach
zadanie4_so_numer_indeksu/TESTY.txt
należy umieścić wyniki testów
pokazujące, że cel zadania został osiągnięty (wystarczy podać czasy działania polecenia
grep
na nieobciążonym i obciążonym systemie wykonane dla oryginalnego i zmienionego
schedulera, ale można też zaproponować własne testy)
zadanie4_so_numer_indeksu/README.txt
zadanie4_so_numer_indeksu/..
i tam pakujemy rozwiązanie poleceniem:
tar czf zadanie4_so_numer_indeksu.tgz zadanie4_so_numer_indeksu>
Ostateczny termin nadsyłania rozwiązań to 16 lutego 2015, godz. 23:59.
W przypadku wątpliwości można zadać pytanie Agacie Janowskiej. Uwaga: uprzedzam, że w tygodniu 7-14 lutego 2015 nie będę miała dostępu do poczty.
Przed zadaniem pytania warto sprawdzić, czy odpowiedź na nie nie pojawiła się już na liście często zadawanych pytań.