po polsku
Do spisu tre¶ci tematu 3
3.3.1 Szeregowanie procesów
Spis tre¶ci
Wprowadzenie
Struktury i zmienne
Algorytm szeregowania
Implementacja
Szeregowanie a wieloprocesorowo¶æ
FSQ, czyli "Frequently Scheduled Questions"
Bibliografia
Wprowadzenie
Autor ninejszego opracowania staje przed trudnym zadaniem. W Projekcie
Linux, zesz³oroczej pracy starszych kolegów, rozdzia³ Sposoby
szeregowania procesów dosyæ obszernie wyja¶nia mechanizm szeregowania
procesów w Linuxie. Na szczê¶cie nie wyczerpuje ca³kowicie tematu, a tak¿e
zawiera klika b³êdów i nie¶cis³o¶ci. Dlatego autor stara³ siê nie powtarzaæ
ju¿ opisanych rzeczy, a raczej wyja¶niæ kwestie mog±ce budziæ w±tpliwo¶ci
oraz opisaæ szczegó³y implementacji odsy³aj±c do komentarzy w kodzie j±dra
Linuxa.
Opis powsta³ przede wszystkim na bazie analizy ¼róde³ j±dra Linuxa w
wersji 2.0.32. W czê¶ci dotycz±cej szeregowania procesów, w stosunku
do wersji 2.0.0 (opisanej we wspomnianym rozdziale Projektu Linux), dokonano
niewielu zmian - poprawiono klika drobnych b³êdów.
Zacznijmy od wyja¶nienia kilku kluczowych pojêæ, struktur i zmiennych
zwi±zanych z szeregowaniem procesów.
Struktury i zmienne
Tablica task[] (tablica
procesów)
J±dro Linuxa, podobnie jak i j±dra innych systemów unixopodobnych, informacje
o procesach utrzymuje w statycznej tablicy: Jest zdefiniowana w kernel/sched.c
(plik ten zawiera wiêkszo¶æ funkcji i zmiennych zwi±zanych z szeregowaniem
procesów). Rozmiar tablicy okre¶lony jest przez sta³± NR_TASKS,
której warto¶æ standardowo równa siê 512. System nak³ada pewne
ograniczenia na maksymaln± liczbê procesów dla u¿ytkowników oraz dba o
to, aby pozosta³y wolne miejsca w tablicy dla procesów nadzorcy systemu.
Szczegó³y zapewne mo¿na znale¼æ w czê¶ci po¶wiêconej funkcji fork().
Z punktu widzenia modu³u szereguj±cego procesy, wa¿niejsza jest kolejka
procesów gotowych.
Zmienna init_task (proces
idle i kolejka procesów gotowych)
Zmienna ta ma dwojakie znaczenie. Po pierwsze, zawiera informacje o
procesie o identyfikatorze równym 0. Jest to specjalny proces, pierwszy
jaki powstaje w systemie. Tworzony jest w "sztuczny" sposób,
bez udzia³u fork(). Opis procesu
0 w Projekcie Linux mija siê w kilku kwestiach z prawd±. Fakty dotycz±ce
tego procesu s± nastêpuj±ce:
Nosi nazwê swapper (³atwo siê o tym przekonaæ u¿ywaj±c kombinacji
CTRL-Scroll lock w konsoli), która mo¿e sugerowaæ, ¿e jest to tzw.
proces wymiany. Wbrew nazwie w Linuxie nie ma on ¿adnego zwi±zku z pamiêci±
wirtualn± - realizuje on algorytm "nudzenia" siê procesora, opisany
poni¿ej. Nie jest to równie¿ proces tzw. proces
init (proces init to jedyny bezpo¶redni potomek tego procesu,
o pid równym zawsze 1 - kod jego znajduje siê poza j±drem w pliku /sbin/init).
Aby unikn±æ nieporozumieñ proces ten bêdzie nazywany procesem idle.
Inicjalizowany jest warto¶ciami zdefiniowanymi w makrodefinicji INIT_TASK.
Nie jest ¿adnym pseudoprocesem - na samym pocz±tku dokonuje inicjalizacji
wielu struktur systemowych, nastêpnie tworzy proces init za pomoc±
funkcji clone(), po czym wykonuje
nieskoñczon± pêtlê (patrz algorytm idle).
Ca³y czas znajduje siê w stanie TASK_RUNNING (ale i tak warto¶æ
pola state dla tego procesu nigdy nie jest u¿ywana).
Nigdy nie ginie, jego struktura znajduje siê w zerowym elemencie tablicy
procesów.
Ma najni¿szy priorytet w systemie - zostanie wybrany wtedy i tylko
wtedy gdy nie ma innych procesów gotowych.
Po drugie, zmienna init_task jest pocz±tkiem (i jednocze¶nie
koñcem) dwukierunkowej listy cyklicznej, w której znajduj± siê procesy
gotowe do wykonania. Dalej lista ta bêdzie nazywana kolejk± procesów
gotowych.
Struktura task_struct
Jest to struktura zwi±zana z ka¿dym z istniej±cych w systemie procesów.
Pola wykorzystywane przez kod modu³u szeregowania to:
volatile long state - okre¶la stan procesu. I tu uwaga:
to, ¿e pole state zawiera okre¶lon± warto¶æ nie musi koniecznie oznaczaæ,
¿e proces ju¿ znajduje siê w danym stanie, ale ¿e mo¿e siê w takim stanie
dopiero znale¼æ. W Linuxie zdefiniowane s± nastêpuj±ce stany:
TASK_RUNNING - proces siê wykonuje b±d¼ jest gotowy do wykonania
TASK_INTERRUPTIBLE - proces jest lub mo¿e zostaæ u¶piony w stanie
przerywalnym, czyli ¿e zostanie wznowiony po nadej¶ciu sygna³u lub po up³ywie
czasu budzenia. Ostatnie oznacza, ¿e proces mo¿e zostaæ u¶piony na pewien
zadany czas (mo¿liwo¶æ czêsto u¿ywana przez sterowniki urz±dzeñ).
TASK_UNINTERRUPTIBLE - proces jest lub zostanie u¶piony w stanie
nieprzerywalnym (np. w oczekiwaniu na i-wêze³). Proces taki mo¿e zostaæ
wznowiony jedynie na skutek wywo³ania funkcji wake_up()
- ¶ci¶lej jego stan zostanie zmieniony na TASK_RUNNING.
TASK_ZOMBIE - proces wykona³ funkcjê exit().
Zostanie usuniêty z tablicy procesów.
TASK_STOPPED - proces jest lub zostanie wstrzymany. Mo¿e zostaæ
wznowiony jedynie na skutek otrzymania sygna³u SIGCONT.
TASK_SWAPPING - nie jest wykorzystywany - ¿aden z procesów
nie znajdzie siê w tym stanie (ciekawostka: nie wiadomo czemu jest sprawdzany
w funkcji count_active_tasks()).
Stany procesów opisano w Projekcie
Linux. Nie wspomina siê tam jednak, ¿e to w³a¶nie modu³ szeregowania
(i tylko on) odpowiedzialny jest za faktyczne usuniêcie procesu z kolejki
procesów gotowych. Szczegó³y w opisie algorytmu poni¿ej.
Zwracam uwagê na u¿ycie volatile - pole state czêsto
odczytywane jest przy w³±czonych przerwaniach, w wyniku których
mo¿e doj¶æ do jego modyfikacji (przypominam, ¿e volatile zmusza
kompilator do bezpo¶redniego siêgania do komórki pamiêci przy ka¿dym odwo³aniu).
long priority - warto¶æ kwantu czasu (w tykniêciach)
jaki proces otrzymuje jednorazowo na dzia³anie. Dopuszczalne warto¶ci zamykaj±
siê w przedziale [1, 2*DEF_PRIORITY] (dla Intela DEF_PRIORITY
= 20). Wy¿sza warto¶æ oznacza wy¿szy priorytet. Opis w Projekcie Linux
podaje nieprawdê, ¿e jest odwrotnie, oraz ¿e priority mo¿e mieæ
warto¶æ 0. Warto¶æ priority w Linuxie jest odwzorowaniem tzw.
warto¶ci nice procesu. Mo¿e byæ modyfikowana i odczytywana funkcjami
nice(), setpriority()
oraz getpriority().
long counter - czas jaki pozosta³ procesowi na dzia³anie,
czyli nim system spróbuje go wyw³aszczyæ (patrz ni¿ej). Nazywany równie¿
dynamicznym priorytetem. Czas jest wyra¿ony w tykniêciach zegara. Dla Intela
1 tykniêcie równa siê 10 milisekundom. Mo¿liwe warto¶ci counter
nale¿± do przedzia³u [0, 4*DEF_PRIORITY) - czyli w przypadku Intela:
0 <= counter < 80. Dlaczego? Odpowied¼ poni¿ej.
unsigned long timeout - "godzina" (wyra¿ona
w systemowych jednostkach, patrz jiffies),
o której proces zostanie obudzony i wstawiony do kolejki procesów gotowych.
Odpowiedzialna za u¶pienie procesu jest funkcja schedule().
unsigned long policy - okre¶la tryb szeregowania dla
procesu. Dostêpne tryby to: SCHED_OTHED, SCHED_RR,
SCHED_FIFO.
unsigned long rt_priority - priorytet realtime
procesu. Dla procesów szeregowanych standardow± metod± SCHED_OTHER
wynosi 0, w pozosta³ych trybach musi byæ w przedzale [1,99]. Wy¿sza warto¶æ
- wy¿szy priorytet.
struct task_struct *next_run, *prev_run - dowi±zania
do nastêpnego i poprzedniego procesu w kolejce procesów gotowych.
Struktura zawiera jeszcze kilka pól zwi±zanych z czasem i tzw. zegarami
interwa³owymi, które s± opisane tutaj.
Zmienna current
Wskazuje na task_struct bie¿±cego procesu. W rzeczywisto¶ci
jest to makrodefinicja zwracaj±ca wska¼nik na task_struct bie¿±cego
procesu na "bie¿±cym" procesorze (wskazuje na odpowiedni element
tablicy current_set[],
która zawiera wska¼niki na bie¿±ce procesy dla ka¿dego z procesorów systemu.
O tym jak wygl±da szeregowanie na architekturach wieloprocesorowych mo¿na
przeczytaæ poni¿ej).
Zmienna need_resched
Flaga wskazuj±ca czy ma byæ wywo³ane schedule().
Istnienie takiej zmiennej podyktowane jest niemo¿no¶ci± wywo³ania funkcji
schedule() bezpo¶rednio z
procedury obs³ugi przerwania sprzêtowego (wynika to z choæby z implementacji,
a tak¿e z tego, ¿e wybór procesu mo¿e trwaæ za d³ugo, aby dzia³o siê to
w procedurze obs³ugi przerwania).
Zmienna jiffies
Jest to licznik czasu systemowego. Standardowo zwiêkszany o 1 jest co
10ms (warto¶æ standardowa dla Linuxa/i386, dla Linuxa/AXP jest to 1ms).
Algorytm szeregowania
Dostêpne tryby
szeregowania oraz dzia³anie algorytmu
zosta³y bardzo dobrze (i zgodnie z prawd±) opisane w Projekcie
Linux. Trudno w³a¶ciwie tu co¶ dodaæ - algorytm szeregowania zaimplementowany
w Linuxie jest rzeczywi¶cie bardzo prosty.
Najwa¿niejsze jego cechy to:
Zapewnia, ¿e proces nie zostanie zag³odzony - odnosi siê to do standardowego
trybu szeregowania (SCHED_OTHER). W przypadku trybów SCHED_RR
oraz SCHED_FIFO je¶li jest choæ jeden gotowy proces realtime nigdy
nie zostanie wznowiony proces o ni¿szym priorytecie, w szczególno¶ci ¿aden
z procesów szergowanych standardowo.
Jest ma³o wytrzyma³y na du¿e obci±¿enie systemu, co objawia siê spowolnieniem
reakcji systemu. Ka¿dy kto kompilowa³ j±dro i próbowa³ co¶ pisaæ, prawdopodobnie
odczu³, ¿e system siê zatyka. Wynika to z st±d, i¿ Linuxowy scheduler nie
przewiduje obni¿enia priorytetu zach³annego procesu wykonuj±cego du¿o obliczeñ
(tzw. compute-bound task). Procesy interaktywne (tzw. transput-bound
tasks) mia³yby dziêki temu wiêksze szanse otrzymaæ procesor.
Schemat algorytmu
schedule()
{
if (czekaj± wolne procedury obs³ugi przerwañ)
wykonaj je;
wywo³aj listê funkcji w kolejce tq_scheduler;
if (bie¿±cy proces szeregowany jest w SCHED_RR i wykorzysta³ swój kwant czasu)
przydziel mu nowy kwant i przesuñ na koniec kolejki procesów gotowych;
if (bie¿±cy ma zostaæ u¶piony, ale mo¿e odbieraæ sygna³y)
if (otrzyma³ nieblokowany sygna³ || min±³ jego czas budzenia)
zmieñ jego stan na gotowy;
else
usuñ go z kolejki procesów gotowych;
for (ka¿dy proces z kolejki procesów gotowych)
wybierz proces o najwy¿szym priorytecie (warto¶ci goodness);
if (najwy¿szy priorytet = 0)
for (ka¿dy proces)
zmodyfikuj jego warto¶æ counter (dynamiczny priorytet);
else
if (brak procesu do wykonania)
wybierz proces idle;
if (wybrany zosta³ inny proces ni¿ bie¿±cy)
{
ustaw ewentualny czas budzenia dla bie¿±cego procesu;
wznów dzia³anie wybranego procesu;
}
if (wznowiony proces mia³ ustawiony budzik i obudzi³ siê przed czasem)
wy³±cz budzik;
}
Szczegó³owe wyja¶nienie znajduje siê w komentarzach funkcji schedule(),
która realizuje wy¿ej opisany algorytm.
Warto¶æ goodness
Okre¶la na ile "dobry" jest dany proces, aby przydzieliæ mu
procesor. Im wiêksza warto¶æ tym lepsza. Równa siê odpowiednio:
1000+rt_priority: gdy proces szeregowany jest w jednym z trybów
realtime
counter: gdy proces szeregowany jest standardowo
counter+1: jw, gdy proces jest procesem bie¿±cym
Algorytm idle
Proces 0 wykonuje nieskoñczon± pêtlê, tzw. idle-loop. Implementacja
pêtli jest zale¿na od architektury. W przypadku Intela, pocz±tkowo wykonuje
aktywne czekanie. Je¶li przez okre¶lony czas (HARD_IDLE_TIMEOUT tykniêæ
zegara) nie pojawi siê ¿±danie przeszeregowania procesów (flaga need_resched)zatrzymuje
dzia³anie procesora. Opó¼nienie ma na celu unikniêcie sytuacji, kiedy natychmiast
po zatrzymaniu procesora trzeba go ponownie uruchomiæ.
Patrz opis funkcji sys_idle(),
hard_idle().
Implementacja
Wiêkszo¶æ funkcji zwi±zanych z szeregowaniem znajduje siê w pliku kernel/sched.c.
Czê¶æ w kernel/sys.c, include/linux/sched.h,
include/asm-i386/system.h, arch/i386/kernel/process.c,
arch/i386/kernel/entry.S. Poni¿ej
ma³y przewodnik po funkcjach.
Najwa¿niejsze z nich to: schedule(),
goodness(), update_process_times().
Funkcje pomocnicze: add_to_runqueue(),
del_from_runqueue(),
move_last_runqueue(),
wake_up_process(),
process_timeout().
Makrodefinicja dokonuj±ca prze³±czenia kontekstu (w asemblerze, zale¿na
od architektury): switch_to().
Funkcja inicjalizuj±ca scheduler: sched_init()
Funkcje umo¿liwiaj±ce modyfikacjê i sprawdzenie parametrów szeregowania:
sys_sched_setscheduler(),
sys_sched_getscheduler(),
sys_sched_setparam(),
sys_nice(), sys_setpriority(),
sys_getpriority()
Inne funkcje zwi±zane z szeregowaniem:
sys_sched_get_priority_max(),
sys_sched_get_priority_min(),
sys_sched_rr_get_interval(),
sys_sched_yield().
W pliku kernel/sched.c, oprócz
funkcji zwi±zanych ze schedulerem i czasem, znajduje siê te¿ kilka innych:
show_state() oraz rodzina
funkcji sys_getXid().
Procedura powrotu z trybu j±dra, gdzie m.in. mo¿e doj¶æ do wywo³ania
schedule() to: ret_from_sys_call.
Szeregowanie a wieloprocesorowo¶æ
W j±drze SMP Linuxa (SMP - Symmetric MultiProcessor), które wykorzystuje
wieloprocesorowo¶æ niektórych platform, ró¿nice dotycz±ce algorytmu szeregowania
procesów s± minimalne. Fakty s± nastêpuj±ce:
Prostotê implementacji wsparcia wieloprocesorowo¶ci w Linuxie zapewnia
pojedyncza blokada j±dra. Blokada ta polega na tym, ¿e tylko
jeden procesor mo¿e przej¶æ do trybu j±dra. Jest to tzw. Coarse
Grained Locking.
W architekturach opartych na procesorach Intela wszelkie standardowe
przerwania, w szczególno¶ci przerwanie zegarowe, docieraj± tylko do procesora
o numerze 0 (tzw. bootcpu). Mo¿e to byæ powodem problemów, gdy¿
mo¿e prowadziæ do zablokowania systemu, np. w sytuacji gdy procesor inny
ni¿ bootcpu znajduje siê w trybie j±dra, a bootcpu otrzyma
przerwanie (dok³adnie to opisano w komentarzu do funkcji allow_interrupts()).
Do komunikacji miêdzy procesorami s³u¿± tzw. przerwania IPI
(Interprocessor Interrupt). Dla Intela jest to przerwanie
IRQ13, przy czym dla komunikacji zwiazanej z szeregowaniem zarezerwowano
przerwanie IRQ16.
Ka¿dy z procesorów sam, gdy wejdzie do j±dra, mo¿e wykonaæ schedule().
Jeden z procesorów dokonuje odliczania czasu zu¿ytego przez procesy
na wszystkich procesorach (na Intelu jest to bootcpu, gdy¿ tylko
on jest przerywany). W razie potrzeby, korzystaj±c z IPI powiadamia inny
procesor, o konieczno¶ci przeszeregowania procesu (normalnie wystarczy
ustawienie flagi need_resched). Wtedy taki procesor otrzyma przerwanie
i zawiesi siê w oczekiwaniu na zdjêcie blokady z j±dra. Gdy uda mu siê
przej±æ j±dro, bêdzie móg³ sam wywo³aæ schedule().
Ka¿dy z procesorów, wykonuj±c schedule(),
mo¿e wybraæ proces sam dla siebie - nie mo¿e zmusiæ innego procesorora
do wykonywania jakiego¶ procesu.
W strukturze task_struct dodano nastêpuj±ce pola:
int processor - zawiera numer procesora, przez który
proces w³a¶nie w danej chwili jest wykonywany, wpp wypadku równa
siê sta³ej NO_PROC_ID (równej 0xFF).
int last_processor - numer procesora, na którym proces
ostatnio dzia³a³ dany proces.
int lock_depth - lokalny licznik wywo³añ funkcji systemowych
przez dany proces. Licznik ten jest inkrementowany, gdy proces wywo³uje
funkcjê j±dra oraz w procedurze obs³ugi przerwania (tak¿e IPI). Jego istnienie
zwi±zane jest z blokad± j±dra. Np. w sytuacji, kiedy dochodzi do prze³±czenia
kontekstu z procesu dzia³aj±cego w trybie j±dra na proces w trybie u¿ytkownika,
nale¿y zwolniæ blokadê j±dra. Patrz switch_to().
Pozosta³e ró¿nice to:
Tworzonych jest tyle kopii procesu 0 ile jest procesorów w systemie
- ka¿dy z procesorów, b±d¼ ich czê¶æ mo¿e siê przecie¿ niezale¿nie "nudziæ".
S± to prawdziwe klony - wszystkie maj± identyfikator (pid) równy
0. Ma to miejsce w smp_init().
W tablicy current_set[] przechowywane
s± wska¼niki na procesych wykonywane na poszczególnych procesorach.
Dziêki wspomnianej makrodefinicji current
fragmenty kodu, odwo³uj±ce siê do struktury bie¿±cego procesu, dla których
wieloprocesorowo¶æ jest przezroczysta (a takich jest wiekszo¶æ), mog³y
pozostaæ bez zmian.
Wykonywanie pêtli idle musi nast±piæ poza j±drem (z uwagi na
blokadê). Ale jednocze¶nie pojawia siê problem - co bêdzie je¶li pojawi
siê np. jeden nowy proces, a nudzi siê kilka procesorów? Je¶li wszystkie
z nich bêd± próbowa³y wykonaæ schedule(),
wszystkie zostan± zablokowane, po czym po kolei bêd± wchodziæ do j±dra,
najprawdopodobniej niepotrzebnie, blokuj±c innym dostêp do niego. W tym
celu wprowadzono globaln± zmienn± smp_process_available -
jest to licznik gotowych, ale nie wykonywanych w danej chwili procesów.
Licznik ten jest modyfikowany w sekcji krytycznej chronionej semaforem
binarnym. Semafor ten jest bitem, ustawianym i odczytywanym przy pomocy
atomowej instrukcji typu TEST_AND_SET. Procesor, który wejdzie
do sekcji krytycznej, sprawdza warto¶æ licznika, je¶li wiêkszy od zera,
dekrementuje go, po czym wykonuje schedule(),
wpp kontynuuje wykonywanie pêtli idle. Patrz funkcje sys_idle(),
cpu_idle() w wersji
SMP.
Funkcja goodness() stara
siê zapobiegaæ migracji procesów miêdzy procesorami. Mo¿e to siê op³acaæ
ze wzglêdów sprzêtowych (ka¿dy z procesorów mo¿e mieæ w³asn± pamiêæ podrêczn±
drugiego poziomu). Realizuje to w ten sposób, ¿e dodaje do zwracanej warto¶ci
(je¶li > 0) sta³± PROC_CHANGE_PENALTY = 20 w przypadku, gdy
proces, dla którego oblicza warto¶æ goodness, poprzednio dzia³a³
na tym samym procesorze (czyli tym samym, który wykonuje schedule()).
Funkcja add_to_runqueue(),
po dodaniu procesu do kolejki procesów gotowych inkrementuje licznik smp_process_available,
po czym sprawdza czy który¶ z procesorów nie wykonuje pêtli idle i je¶li
tak, powiadamia go, ¿e pojawi³ siê nowy proces gotowy do wykonania.
Funkcja update_process_times()
odlicza czas zu¿yty przez procesy dzia³aj±ce na wszystkich procesorach.
Realizacjê wieloprocesorowo¶ci w j±drze w wersji 2.1.x, znajduj±cej siê
jeszcze w stadium alpha, zaimplementowano od nowa, wprowadzaj±c niezale¿ne
blokady dla poszczególnych czê¶ci j±dra (tzw. fine grained locking).
Zwiêksza to oczywi¶cie wydajno¶æ systemu, komplikuje jednak znacznie jego
implementacjê.
FSQ
czyli "Frequently scheduled questions"
W trakcie zajêæ z przedmiotu "Systemy operacyjne", jak i podczas
naszych "burz mózgów" pojawia³o siê sporo pytañ, które pozosta³y
bez odpowiedzi, b±d¼ te¿ skoñczy³o siê na spekulacjach i przypuszczeniach.
Pytania i odpowiedzi na nie, znalezione u samych ¼róde³, zamieszczone s±
poni¿ej.
Do jakiego przedzia³u nale¿± warto¶ci
pola counter?
Najwy¿szy mo¿liwy priorytet to 40. Wobec tego, proces taki otrzyma
na dzia³anie kwant czasu równy 40 "tykniêciom" zegara (400ms).
Za³ó¿my, ¿e natychmiast, nim licznik counter zostanie mu zmniejszony,
odda procesor i na d³ugo za¶nie (np. wywo³a funkcjê pause()).
Nastêpnie, zgodnie z algorytm szeregowania, proces zostanie "postarzany",
czyli kolejno bêdzie przyjmowa³ warto¶ci: 40+20=60, 40+30=70, 40+35=75.
Z prostych obliczeñ (suma nieskoñczonego ci±gu geometrycznego) wynika,
¿e warto¶æ ta d±¿y do 80, nigdy jej nie osi±gaj±c.
Co to s± "bottom halves" ?
S± tzw. wolne procedury obs³ugi przerwañ. Wykonanie funkcji zwi±zanych
z niektórymi przerwaniami mog³oby trwaæ zbyt d³ugo, aby wykonywa³y siê
w kontek¶cie przerwania. Dlatego wprowadzono mechanizm "dolnych po³ówek"
obs³ugi przerwañ w celu zminimalizowania czasu spêdzanego w przerwaniu
- procedura jego obs³ugi dzielona jest na dwie czê¶ci, pierwsza robi to
co jest niezbêdne oraz zaznacza konieczno¶æ wykonania drugiej, poza przerwaniem.
S³u¿y do tego makro mark_bh().
Funkcje bottom half wywo³ywane s± w do_bottom_half(),
które z kolei jest wywo³ywane przy wyj¶ciu z j±dra w ret_from_sys_call
oraz w schedule().
Przewidziano 32 funkcje bottom half - umieszczane s± w tablicy bh_base[].
Definicje dla poszczególnych przerwañ znajduj± siê w pliku linux/interrupt.h.
Tam te¿ znajduj± siê makra init_bh(),
mark_bh(), enable_bh(),
disable_bh().
Przyk³adem wykorzystania opisywanego mechanizmu s± funkcje do_timer()
oraz timer_bh(), odpowiedzialne
za czas systemowy.
Czy w schedule() proces mo¿e byæ wyw³aszczony przez inny proces?
Nie. Proces znajduj±cy siê w trybie j±dra nie mo¿e byæ wyw³aszczony
przez inny proces. Chwilowo wyw³aszczyæ proces w trybie j±dra mo¿e, oczywi¶cie,
przerwanie sprzêtowe (które, z kolei mo¿e byæ wyw³aszczone przez przerwanie
o wy¿szym priorytecie). Po skoñczeniu jego obs³ugi sterowanie wróci do
przerwanego procesu. Innymi s³owy, j±dro jest sekcj± krytyczn± dla procesów
u¿ytkownika.
Kiedy i gdzie proces jest wyw³aszczany?
Wtedy gdy wykorzysta przydzielony mu kwant czasu. Odpowiedzialna za
stwierdzenie tego faktu jest funkcja update_process_times(),
wykonuj±ca siê jako "bottom half" przerwania zegarowego. Je¶li
proces wykorzysta swój kwant czasu, ustawiana jest flaga need_resched.
Bêdzie sprawdzona w procedurze powrotu z wywo³ania systemowego (ta sama
procedura wykonywana jest tak¿e przy powrocie z procedury obs³ugi przerwania).
Je¶li wyw³aszczenie nast±pi poza j±drem - proces zostanie wstrzymany dok³adnie
tam, gdzie go przerwanie zasta³o. Je¶li przerwanie wyst±pi³o w momencie
gdy proces przebywa w trybie j±dra, to w ret_from_sys_call
proces zostanie zmuszony do wej¶cia do schedule()
i zostanie wstrzymany w miejscu wywo³ania switch_to().
Czemu niektóre funkcje j±dra maj± w nazwie prefiks sys_?
S± to funkcje dostêpne s± poza j±drem dla programów u¿ytkownika - widziane
s± bez prefiksu. Oczywi¶cie, samo dodanie sys_ nie wystarcza aby funkcja
by³a widziana poza j±drem.
A co zmienna XXX oznacza i gdzie jest zdefiniowana?
W znalezieniu odpowiedzi na tego typu pytania bardzo mo¿e pomóc skrypt
grepr, bez którego opis ten nie mia³by szans powstaæ.
Bibliografia
Pliki ¼ród³owe j±dra Linuxa 2.0.32
Man pages: nice (2), setpriority (2), getpriority (2), sched_setscheduler (2),
sched_getscheduler (2), sched_getparam (2), sched_setparam (2), sched_get_priority_max (2),
sched_get_priority_min (2), sched_rr_get_interval (2), sched_yield (2),
idle (2)
Krzysztof Arciszewski, Krzysztof Sobusiak Projekt-Linux,
rozdzia³ Sposoby
szeregowania procesów
David A. Rusling Linux Documentation Project - The Linux Kernel,
rozdzia³ Scheduling
Michael K. Johnson The Linux Kernel Hacker's Guide, rozdzia³
The Linux scheduler
Alan Cox An implementation Of Multiprocessor Linux
Markus Kuhn POSIX.1b Compatibility and Real-Time Support
Maurice J. Bach Budowa systemu operacyjnego UNIX, wyd. II, WNT
1995
Berny Goodheart, James Cox The Magic Garden Explained, PRENTICE
HALL 1994
Autor: Grzegorz Ca³kowski
zanotowane.pldoc.pisz.plpdf.pisz.plpajaa1981.pev.pl