52
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 9/2006
Wielozadaniowość
w systemach operacyjnych
W
tej części kursu omówimy ostatnie z klu-
czowych zagadnień systemów operacyj-
nych, czyli wieloprocesowość (ang. mul-
titasking). Jednak, aby móc sprawnie zaimplemen-
tować ten moduł w naszym systemie, musimy przy-
bliżyć również istotę przerwań w trybie chronionym
oraz funkcję i sposób zarządzania zegarem syste-
mowym. Następnie omówimy dość szczegółowo pro-
blem wielozadaniowości i synchronizacji międzypro-
cesowej. Teraz trochę wstępu do tematu. Tak więc
zarządzanie procesami, które jest podstawowym za-
daniem każdego nowoczesnego systemu operacyj-
nego, obejmuje:
• alokowanie zasobów dla procesów;
• organizację wymiany informacji między procesa-
mi;
• zabezpieczanie zasobów procesów przed niepo-
żądanym wpływem innych procesów;
• synchronizację współpracy procesów.
Równoległe przetwarzanie wielu programów w sys-
temach jednoprocesorowych wymaga skoordy-
nowanego w czasie przeplatania procesów. Sy-
tuacja komplikuje się jeszcze bardziej w maszy-
nach wieloprocesorowych, gdyż oprócz przepla-
tania muszą one umożliwiać równoczesne prze-
twarzanie kilku procesów.
Przeplatanie oraz równoczesne przetwarza-
nie procesów są pojęciami z dziedziny współ-
bieżności i stanowią poważne wyzwanie dla osób
programujących zarówno aplikacje, jak i systemy
operacyjne. W wielu współczesnych systemach
operacyjnych zagadnienie zarządzania procesa-
mi komplikuje się wskutek wprowadzenia poję-
cia wątku.
W systemach wielowątkowych proces pozo-
staje obiektem wyróżnionym przez cechy wła-
sności zasobów, natomiast wątki działające w ra-
mach procesu są współbieżnymi potokami wyko-
nywanych rozkazów.
Przerwania w trybie chronionym
Przerwania są wykorzystywane do wielu celów. Mo-
żemy je podzielić na trzy grupy:
• przerwania wyjątków procesora;
• przerwania sprzętowe;
• przerwania programowe.
Aby móc korzystać w jakikolwiek sposób z przerwań
w trybie chronionym niezbędne będzie stworzenie
i załadowanie Tablicy Deskryptorów Przerwań (ang.
Interrupts Descriptor Table, IDT). Tablica ta składa
się z 256 wpisów, z których każdy ma rozmiar 64 bi-
tów. Struktura opisująca pojedynczy deskryptor wraz
z definicjami flag znajduje się na Listingu 1.
Tak samo jak w przypadku GDT, sama tablica
IDT jest opisana specjalnym 48-bitowym deskrypto-
rem. Jego pierwsze 16 bitów określa rozmiar tablicy
minus 1bajt. Zaraz za tym znajduje się 32-bitowy, fi-
zyczny adres IDT w pamięci RAM. Listing 2 przed-
stawia funkcję ustawiającą adres podprogramu ob-
sługi przerwania w Tablicy Deskryptorów Przerwań.
Podprogramy obsługi przerwań dzielimy na pod-
programy nisko i wysoko poziomowe (ang. low-level
& high-level interrupt handlers). Niskopoziomowe ob-
sługują operacje ściśle powiązane z jądrem. Do ich
zadania należy:
• zapamiętanie kontekstu procesu, który został
przerwany;
• wywołanie wysokopoziomowego podprogramu
obsługi przerwania;
• przywrócenie poprzedniego stanu kontekstu;
• powrót do przerwanego zadania.
Do podprogramów wysokopoziomowych należą np.
funkcje sterowników urządzeń w przypadku prze-
rwań sprzętowych.
Kontekst przerwania
Rejestry odkładane na stos przez niskopoziomowy
podprogram obsługi przerwania stanowią kontekst
przerwania, lub też inaczej jego ramkę (ang. interrupt
Grzegorz Pełechaty
Autor jest programistą oraz zagorzałym zwolennikiem
oprogramowania Open Source. Jako specjalista w
dziedzinie systemów operacyjnych czasu rzeczywiste-
go przyczynia się nieugięcie do ich dalszego rozwoju.
W chwili obecnej pracuje w organizacji netcore labs,
projektując sieciowy system operacyjny Netcore, prze-
znaczony na architekturę IA386p+ (strona domowa pro-
jektu: http://netcorelabs.org).
Kontakt z autorem: reqst@o2.pl
Na kurs składają się
następujące części
• SDJ nr 7/2006 „Jądro systemu operacyjnego”;
• SDJ nr 8/2006 „Zarządzanie pamięcią w systemach
operacyjnych”.
Wielozadaniowość w systemach operacyjnych
53
www.sdjournal.org
Software Developer’s Journal 9/2006
context/interrupt frame). Dla architektury IA386p+ można ją
przedstawić w sposób ukazany na Listingu 3. Aby uzyskać ta-
ką postać ramki, należy posłużyć się niskopoziomową proce-
durą obsługi przerwania z Listingu 4.
Przerwania sprzętowe
Aby móc kontrolować stan danego urządzenia za pomocą
przerwań musimy najpierw zaprogramować Programowalny
Kontroler Przerwań (ang. Programmable Interrupts Controller,
PIC). Jest to chipset 8259A zlokalizowany na płycie głównej,
który w maksymalnym uproszczeniu może być postrzegany
jako pomost pomiędzy IDT, a fizycznymi urządzeniami.
Listing 5 zawiera zestaw funkcji niezbędnych do prawidło-
wego zaprogramowania i zarządzania tym urządzeniem. Spo-
sób obsługi przerwań sprzętowych przebiega następująco:
• procesor otrzymuje sygnał wywołania przerwania od kon-
trolera PIC;
• odszukiwany jest adres punktu wejścia przerwania w IDT;
• uruchamiany jest podprogram obsługi przerwania, który
kończy się zasygnalizowaniem kontrolerowi , że przerwa-
nie jest już wolne i może zostać wywołane kolejny raz.
Standardowy kontroler PIC obsługuje 16 przerwań, kolejno po
8 na chipsetach 8259A-1 i 8259A-2. Każda linia IRQ ma swoje
odwzorowanie w przestrzeni przerwań IDT. Linia 0 jest zma-
powana na przerwanie 32, linia 1 na przerwanie 33 itp.
Obsługa zegara systemowego
Ostatnim elementem niezbędnym do implementacji wieloza-
daniowości z wywłaszczeniem (ang. preemptive multitasking)
jest obsługa zegara systemowego, czyli chipsetu 8253. Chip-
set ten jest w stanie wywoływać periodycznie przerwanie
IRQ0. Jako podprogram obsługi tego przerwania najczęściej
podpina się funkcje związane ze zmianą zadań. Listing 6 za-
wiera kod obsługi tego chipsetu.
Wielozadaniowść,
czyli współdzielenie czasu procesora
Wielozadaniowość jest dość obszerną dziedziną z kategorii
systemów operacyjnych, dlatego najpierw przybliżę kilka klu-
czowych pojęć związanych z tym zagadnieniem.
Podstawowym ogniwem tego podsystemu jest proces,
czyli egzemplarz programu. Pierwotnie łączył on w sobie
określone środowisko pracy (ang. enviroment) oraz stan se-
sji. W nowoczesnych systemach wielkowątkowych wprowa-
dzono pojęcie wątku, którego zadaniem jest przetrzymywa-
nie stanu sesji, a korzysta on ze środowiska zdefiniowanego
w procesie macierzystym. Tak więc dla jednego programu ist-
nieje jeden proces z dowolną liczbą wątków, które reprezen-
tują jego sesje. Działanie te jest transparentne jedynie na po-
ziomie współdzielenia kodu. Stan sesji, inaczej kontekst pro-
cesu to zestaw wszystkich rejestrów modyfikowanylnych ze-
wnętrznie lub wewnętrznie przez proces. Kolejnym pojęciem
jest nadzorca (ang. scheduler), czyli moduł szeregujący pro-
cesy i przydzielający im określony czas procesora w zależno-
ści od priorytetu oraz wymogów programu. Minimalny zestaw
funkcji, jakie musi spełniać moduł zarządzania procesami to:
• tworzenie i usuwanie procesu w systemie;
• przydzielanie czasu procesora procesom.
Tworzenie procesu
Tworzenie procesu może przebiegać na wiele sposobów, wy-
różniamy tutaj pewne etapy, z których składa się ta procedura:
• tworzenie nowej przestrzeni adresowej;
• tworzenie i inicjowanie bloku kontrolnego procesu (ang.
control-block);
• inicjacja kontekstu procesu;
• umieszczanie procesu w kolejce szeregowania.
Pierwszy etap nie jest niezbędny. Nowy proces może bez pro-
blemów pracować w przestrzeni adresowej jądra. Jednak na-
leży uwzględnić w takim wypadku problem bezpieczeństwa.
Dzielenie przestrzeni adresowej wiąże się z podzieleniem
praw dostępu do pamięci maksymalnie na dwie grupy: przywi-
leje procesów jądra oraz użytkowania. Procesy jądra mają za-
tem dostęp do całej przestrzeni adresowej, a procesy użytkow-
nika jedynie do pamięci zmapowanej z tym samym poziomem
uprzywilejowania co ich własny. Ze strony jądra sytuacja ta nie
jest aż tak destruktywna w skutkach, niestety dla zwykłych pro-
cesów użytkownika takie rozwiązanie jest niedopuszczalne
i może być powodem późniejszych błędów nadpisywania stron,
bądź też nieuprzywilejowanego dostępu do prywatnych danych
Słowniczek
• proces – to jedno z najbardziej podstawowych pojęć w informa-
tyce. Z definicji jest to egzemplarz wykonywanego programu.
Należy odróżnić jednak proces od wątku – każdy proces po-
siada własną przestrzeń adresową, natomiast wątki posiadają
wspólną sekcję danych;
• wątek (ang. thread) – obiekt reprezentujący pojedynczą sesję
danego programu;
• nadzorca (ang. scheduler) – algorytm przydzielający czas pro-
cesora pomiędzy zadania;
• kontekst zadania – kopia modyfikowalnych rejestrów proceso-
ra przydzielona konkretnemu zadaniu.
Listing 1.
Definicje flag oraz struktura pojedynczego
deskryptora IDT
#define IDT_PRESENT 0x8000
#define IDT_TRAP 0x0700
#define IDT_INT 0x0600
#define IDT_TASK 0x0500
#define IDT_32 0x0800
#define IDT_DPL0 0x0000
#define IDT_DPL1 0x2000
#define IDT_DPL2 0x4000
#define IDT_DPL3 0x6000
struct
idt_desc
{
unsigned
short
offset15_0
;
unsigned
short
segment
;
unsigned
short
flags
;
unsigned
short
offset31_16
;
}
;
54
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 9/2006
programu. Z tych właśnie przyczyn rozwiązanie te zostało po-
rzucone na rzecz oddzielnych przestrzeni adresowych dla każ-
dego procesu z osobna. Oczywistą zaletą takiego podejścia
jest ochrona danych procesów. Poziomów uprzywilejowania
jest tyle ile obecnie działających procesów, co oznacza, że ża-
den proces nie może korzystać z pamięci innego bez jego zgo-
dy, mowa tutaj o pamięci dzielonej (ang. shared memory).
Etap drugi polega na zaalokowaniu specjalnego bloku pa-
mięci, w którym przechowywane będą informacje na temat
procesu. Do informacji tych możemy zaliczyć min. wskaźnik
do stosu, aktualny stan procesu (np. aktywny, gotowy, śpią-
cy, nieżywy), wskaźnik do struktury reprezentującej prze-
strzeń adresową, który przy sporym uproszczeniu może być
wskaźnikiem do katalogu stron pamięci. Możemy tutaj do-
dać jeszcze kontekst procesu, jednak typowym rozwiązaniem
jest utrzymywanie kontekstu na wierzchu stosu. Opcjonalnie
do danych zawartych w bloku kontrolnym możemy zaliczyć
priorytet procesu, który jest informacją dla nadzorcy, jak spo-
ry okres czasu procesora ma być przydzielony danemu proce-
sowi. Jest to jednak element zależny od rozwiązania kwestii
sposobu szeregowania procesów.
Kolejnym etapem procedury tworzenia nowego procesu
jest inicjacja kontekstu. W tym miejscu musimy pamiętać, że
wiele zależy od architektury pod jaką piszemy nasz system.
Listing 7 przedstawia kontekst procesorów IA386p+, który
określany jest mianem TSS (ang. Task State Segment).
Struktura ta przechowywana jest w oddzielnym segmencie,
którego rozmiar jest równy rozmiarowi kontekstu. Teraz omów-
my dokładniej zawartość TSS. Pole previous przechowuje se-
lektor zadania, które było wykonane przed obecnym, esp0 za-
wiera wskaźnik do stosu w DPL0, a ss0 przetrzymuje selektor
segmentu tego stosu. Każdy poziom uprzywilejowania ma swój
własny stos w obrębie danego procesu. Analogiczne przezna-
czenie mają pola esp1,ss1, esp2, ss2 z wyjątkiem, że ich zawar-
tość odnosi się kolejno do DPL1 i DPL2. Późniejsze pola to flagi
i rejestry ogólnego przeznaczenia wraz z rejestrem cr3, zawie-
rającym adres katalogu stron pamięci. Pole iomapbase powin-
no zawierać przesunięcie mapy przestrzeni IO względem po-
czątku segmentu TSS. Mapa ta zawiera informacje o tym, które
porty mogą zostać użyte przez dany proces. To tyle, jeżeli cho-
dzi o sprzętowy sposób zmiany zadań. Teraz należy zauważyć,
że istnieje alternatywne rozwiązanie dla segmentów stanu za-
dania. Mowa tutaj o programowym przełączaniu stosów. Z in-
formacji zawartych w rozdziale Przerwania w trybie chronionym
dowiedzieliście się, że przed wywołaniem podprogramu obsłu-
gi przerwania , rejestry są zapamiętywane na stosie, aby potem
móc wrócić do poprzedniego stanu procesu. Można sprytnie to
wykorzystać i zaimplementować inny sposób zmiany kontekstu
oparty właśnie o ten fakt. Polega on na zmianie adresu stosu
jednego procesu na inny zaraz przed przywracaniem rejestrów
Listing 2.
Implementacja obsługi IDT
static
void
_set_gate
(
int
pos
,
unsigned
short
segment
,
unsigned
long
offset
,
unsigned
short
flags
)
{
idt_table
[
pos
]
.
segment
=
segment
;
idt_table
[
pos
]
.
flags
=
flags
;
idt_table
[
pos
]
.
offset15_0
=
offset
&
0xFFFF
;
idt_table
[
pos
]
.
offset31_16
=
(
offset
>>
16
)
&
0xFFFFFF
;
}
void
idt_setIntrGate
(
int
intNumber
,
void
*
offset
)
{
_set_gate
(
intNumber
,
KERNEL_CS
,
(
uint32
)
offset
,
IDT_PRESENT
|
IDT_32
|
IDT_INT
|
IDT_DPL3
);
}
Listing 3.
Ramka przerwania wygenerowana przez
procedurę z Listingu 4
struct
intr_frame
{
unsigned
long
ds
;
unsigned
long
es
;
unsigned
long
fs
;
unsigned
long
gs
;
unsigned
long
edi
;
unsigned
long
esi
;
unsigned
long
ebp
;
unsigned
long
old_esp
;
unsigned
long
ebx
;
unsigned
long
edx
;
unsigned
long
ecx
;
unsigned
long
eax
;
unsigned
long
intr_index
;
unsigned
long
intr_ecode
;
unsigned
long
eip
;
unsigned
long
cs
;
unsigned
long
flags
;
unsigned
long
esp
;
unsigned
long
ss
;
}
;
Listing 4.
Niskopoziomowa procedura obsługi
low_int_controller
:
pushal
pushl
%
gs
pushl
%
fs
pushl
%
es
pushl
%
ds
movl
$
KERNEL_DS
, %
eax
movw
%
ax
, %
es
movw
%
ax
, %
ds
movw
%
ax
, %
fs
movw
%
ax
, %
gs
movw
%
ax
, %
ss
call
high_level_handler
popl
%
ds
popl
%
es
popl
%
fs
popl
%
gs
popal
addl
$8, %
esp
iretl
.global
interrupt_X
interrupt_X
:
pushl
$0
pushl
$
X
jmp
__low_int_controller
Wielozadaniowość w systemach operacyjnych
55
www.sdjournal.org
Software Developer’s Journal 9/2006
Listing 5.
Podporgram obsługi chipsetu 8259A
w celu powrócenia do procesu. Algorytm ten zapiszemy w po-
staci kilku punktów:
• wywołanie przerwania (sygnał INT);
• umieszczenie rejestrów(kontekstu zadania) na stosie;
• wywołanie podprogramu obsługi przerwania wysokiego
poziomu;
• zmiana stosu;
• przywrócenie rejestrów z nowego stosu;
• powrót (instrukcja IRET).
Omówimy teraz wady i zalety tej implementacji. Niepodważal-
nym argumentem opowiadającym się za tym rozwiązaniem jest
brak konieczności tworzenia segmentów TSS dla każdego pro-
cesu. Zatem możemy stworzyć teoretycznie dowolną ilość pro-
cesów, nieograniczając się do rozmiaru GDT. W przypadku,
kiedy wprowadzamy zróżnicowanie w poziomie uprzywilejowa-
nia procesów (np. DPL0 i DPL3) należy stworzyć przynajmniej
jeden segment TSS w celu modyfikacji rejestrów SS0 i ESP0.
Kolejną zaletą jest zwiększenie przenośności kodu. W większo-
ści architektur zmiany zadań odbywają się właśnie za pomocą
obsługi przerwań. Możemy jeszcze zauważyć prostotę działa-
nia tego rozwiązania. Programowe przełączanie stosów ma
jeszcze wiele mniej istotnych zalet, które zauważycie podczas
implementacji. Jeżeli chodzi o wady to szczególnie zauważalne
są: konieczność przetrzymywania kontekstu zadania na stosie
oraz konieczność stworzenia minimum jednego segmentu TSS
w celu wprowadzenia różnych poziomów uprzywilejowania.
Przydzielanie czasu procesora
Pożądane zachowanie modułu przydzielania czasu zależy od
potrzeb programów uruchamianych w systemie. W niektórych
uruchamia się procesy z krytycznymi więzami czasowymi,
programy czasu rzeczywistego, w innych przede wszystkim
procesy z podziałem czasu, a jeszcze w innych oba typy pro-
cesów. Omówimy teraz tylko kilka z ciekawszych rozwiązań.
Szeregowanie karuzelowe
Podstawowym i najprostszym w implementacji jest algorytm
karuzelowy (ang. Round-robin). Nie uwzględnia on prioryte-
tów, a każdemu procesowi przydziela stały, taki sam fragment
czasu procesora (ang. time slice). Procesy są równorzęd-
ne pod względem wartości, żaden nie jest mniej lub bardziej
ważny od drugiego, dlatego też są one wykonywane po ko-
lei. Rozwiązanie to jest często stosowane w systemach wbu-
dowanych, gdzie ilość procesów nie jest duża. Istnieje również
static
uint32
cached_irq_mask
;
#define __byte(x,y) (((uint8 *)&(y))[x])
#define cached_21 (__byte(0,cached_irq_mask))
#define cached_A1 (__byte(1,cached_irq_mask))
void
disableIrqOnChip
(
uint32
nIrq
)
{
uint32
mask
=
1
<<
nIrq
;
cached_irq_mask
|=
mask
;
if
(
nIrq
&
8
)
outb
(
cached_A1
, 0xA1
);
else
outb
(
cached_21
, 0x21
);
}
void
enableIrqOnChip
(
uint32
nIrq
)
{
uint32
mask
=
~
(
1
<<
nIrq
);
cached_irq_mask
&=
mask
;
if
(
nIrq
&
8
)
outb
(
cached_A1
, 0xA1
);
else
outb
(
cached_21
, 0x21
);
}
__inline__
void
irqFlushAndAck
(
sint32
irq
)
{
if
(
irq
>=
8
)
{
outb
(
0x60
+(
irq
&
7
)
, 0xA0
);
outb
(
0x62, 0x20
);
}
else
{
outb
(
0x60
+
irq
, 0x20
);
}
}
void
irqChipsetInit
(
void
)
{
cached_irq_mask
=
0xffff
;
/* maskujemy przerwania na chipsecie 8259A-1 */
outb
(
0xff, 0x21
);
/* maskujemy przerwania na chipsecie 8259A-2 */
outb
(
0xff, 0xA1
);
/* ICW1: wybieramy inicjalizacje chipu 8259A-1 */
outb
(
0x11, 0x20
);
/* ICW2: 8259A-1 IR0-7 mapowane na 0x20-0x27 */
outb
(
0x20, 0x21
);
/* kaskada z 8259A-2 na IRQ2 */
outb
(
0x04, 0x21
);
/* 8259A-1 nie ma automatycznego EOI */
outb
(
0x01, 0x21
);
/* ICW1: wybieramy inicjalizacje chipu 8259A-2 */
outb
(
0x11, 0xA0
);
/* ICW2: 8259A-2 IR0-7 mapowane na 0x28-0x2f */
outb
(
0x28, 0xA1
);
/* 8259A-2 jest podrzędne do 8259A-1 na IRQ2 */
outb
(
0x02, 0xA1
);
/* 8259A-2 nie ma automatycznego EOI */
outb
(
0x01, 0xA1
);
/* odblokuj przerwania na 8259A-1 */
outb
(
cached_21
, 0x21
);
/* odblokuj przerwania na 8259A-2 */
outb
(
cached_A1
, 0xA1
);
}
Literatura
• [1] Piotr Metzger, Michał Siemieniacki, Anatomia PC wydanie
IX, Helion 2004;
• [2] Uresh Vahalia, Jądro systemu Unix – nowe horyzonty, Wy-
dawnictwa Naukowo-Techniczne Warszawa 2001;
• [3] William Stallings, Operating Systems. Internals and Design
Principles, Prentice Hall, Inc. 2003
56
Inżynieria
oprogramowania
www.sdjournal.org
Software Developer’s Journal 9/2006
drugie zastosowanie tego mechanizmu. W bardziej zaawan-
sowanych algorytmach przydziału czasu procesora podczas
iteracji kolejek procesów o tym samym priorytecie dobrym
rozwiązaniem jest użycie właśnie algorytmu karuzelowego.
Podstawowym mankamentem tego sposobu przydziału czasu
jest duże zużycie procesora spowodowane brakiem prioryte-
tów wykonywanych zadań.
Szeregowanie ze sprawiedliwym udziałem
Szeregowanie ze sprawiedliwym udziałem (ang. fair-share sche-
duler) przydziela ustaloną część zasobów CPU każdej z grup
udziałowców. Grupa taka może składać się z pojedynczego pro-
cesu, wszystkich procesów danego użytkownika, wszystkich pro-
cesów sesji rejestracyjnej itd. Nadzorca może wybierać sposób
rozdziału czasu procesora między grupy. Jądro monitoruje wyko-
rzystanie procesora, żeby wymusić stosowanie wybranego spo-
sobu przydziału. Jeśli któraś z grup nie zużyje przydzielonej jej
części, pozostałą częścią zazwyczaj obdziela się pozostałe gru-
py proporcjonalnie do ich początkowych udziałów. Podejście to
gwarantuje każdej grupie przewidywalny czas pracy procesora
niezależnie od całkowitego obciążenia systemu. Jest to przydat-
ne zwłaszcza w środowiskach, w których czas obliczeń jest za-
sobem płatnym, bo wtedy zasoby można przydzielać użytkowni-
kom po określonej cenie. Może on być stosowany do zapewnie-
nia, że krytyczne aplikacje w systemie z podziałem czasu będą
zawsze miały potrzebne zasoby.
Szeregowanie sterowane terminami ostatecznymi
Wiele programów czasu rzeczywistego musi reagować na
zdarzenia przed upływem określonego czasu. Przykłado-
wo serwer multimedialny może przesyłać klientowi ramki wi-
deo co 33 milisekundy. Jeśli odczytuje on dane z dysku, mo-
że ustawić termin ostateczny, przed upływem którego odczyt
musi się zakończyć. Jeśli termin ten zostanie przekroczony,
ramka będzie opóźniona. Terminy ostateczne mogą dotyczyć
operacji wejścia-wyjścia lub obliczeń. Ten drugi przypadek
stosuje się w sytuacji, gdy proces wie, ile czasu procesora bę-
dzie potrzebował przed upływem konkretnego terminu osta-
tecznego. Tego typu aplikacje dobrze jest szeregować za po-
mocą algorytmów sterowanych terminami ostatecznymi (ang.
deadline-driven scheduling). Podstawową zasadą jest dyna-
miczna zmiana priorytetów: ich zwiększenie wraz ze zbliża-
niem się ostatecznego terminu realizacji zlecenia. Taki sposób
szeregowania definiuje cztery poziomy priorytetów:
• sztywne czasu rzeczywistego dla terminów, które muszą
być dotrzymane;
• elastyczne czasu rzeczywistego dla terminów, które powinny
być dotrzymane z sensownym prawdopodobieństwem, ale
opóźnienia można od czasu do czasu tolerować;
• z podziałem czasu bez konkretnych terminów, ale ze spo-
dziewanym sensownym czasem reakcji;
• zadania wsadowe, których terminy zakończenia są poda-
wane w godzinach, a nie w milisekundach.
System szereguje procesy w kolejności poziomów ich prioryte-
tów tak, że na przykład elastyczne procesy czasu rzeczywiste-
go mogą zostać wybrane tylko wtedy, gdy nie ma gotowego do
wykonania sztywnego procesu czasu rzeczywistego. W ramach
klas 1, 2 i 4 procesy są szeregowane w kolejności swoich termi-
nów ostatecznych. Proces z najwcześniejszym terminem osta-
tecznym jest wybierany jako pierwszy. Procesy z tych klas wyko-
nują się aż do ich zakończenia lub wstrzymania, chyba że pojawi
się gotowy proces wyższej klasy lub tej samej klasy z wcześniej-
szym terminem ostatecznym. Szeregowanie sterowane termina-
mi ostatecznymi jest odpowiednie dla systemów, w których dzia-
łają procesy ze znanymi wymaganiami dotyczącymi czasu reak-
cji. Ten sam schemat priorytetów można stosować do szerego-
wania żądań dyskowych operacji wejścia-wyjścia itd.
Synchronizacja międzyprocesowa
Synchronizacja jest ściśle powiązana z zagadnieniem wie-
lozadaniowości, dlatego więc musimy przynajmniej w ma-
łym stopniu poruszyć tę problematykę. Posłużę się pro-
stym przykładem aby wyjaśnić główny powód dla którego
Listing 6.
Funkcje obsługi zegara systemowego
#define GEN0_COUNTER 0x40
#define CLOCK_TICK_RATE 1193180
#define TIME (CLOCK_TICK_RATE / HZ)
void
systemTimerInit
(
void
)
{
outb
(
0x34, 0x43
);
outb
(
TIME
&
0xff,
GEN0_COUNTER
);
outb
((
TIME
>>
8
)
&
0xff,
GEN0_COUNTER
);
}
Listing 7.
Struktura reprezentująca segment stanu
zadania (ang. Task State Segment)
struct
TSS
{
uint16
previous
,
empty1
;
uint32
esp0
;
uint16
ss0
,
empty2
;
uint32
esp1
;
uint16
ss1
,
empty3
;
uint16
ss2
,
empty4
;
uint32
esp2
;
uint32
cr3
;
uint32
eip
;
uint32
eflags
;
uint32
eax
;
uint32
ecx
;
uint32
edx
;
uint32
ebx
;
uint32
esp
;
uint32
ebp
;
uint32
esi
;
uint32
edi
;
uint16
es
,
empty5
;
uint16
cs
,
empty6
;
uint16
ss
,
empty7
;
uint16
ds
,
empty8
;
uint16
fs
,
empty9
;
uint16
gs
,
empty10
;
uint16
ldt
,
empty11
;
uint16
trapflag
;
uint16
iomapbase
;
uint8
io_map
[
8192
];
}
;
57
Wielozadaniowość w systemach operacyjnych
www.sdjournal.org
Software Developer’s Journal 9/2006
niezbędne jest zaimplementowanie modułu synchronizacji
w naszym systemie. Wyobraźmy sobie dowolną listę ele-
mentów, w której poszczególne ogniwa połączone są ze so-
bą wskaźnikami w ten sposób, że każdy z elementów za-
wiera adres następnego w liście (next = current->next). Te-
raz załóżmy, że dwa procesy aktualnie korzystają z tej listy.
Jeden z nich, dla uproszczenia nazwijmy go P1, iteruje całą
listę w celu wyświetlenia jej zawartości. A drugi (P2) ma za
zadanie odszukanie jednego elementu i usunięcie go. Te-
raz pomyślmy jakie konsekwencje wynikłyby w momencie,
gdy proces P2 usunie element, na którym zatrzymał się P1.
P2 zakończył z powodzeniem swoje działanie, natomiast P1
chcąc się odwołać do pamięci obecnego elementu otrzy-
małby w najlepszym przypadku błąd strony, a w najgorszym
błędne dane, które spowodowałyby nieprzewidywalne kon-
sekwencje. W takich sytuacjach z pomocą przychodzą nam
różne techniki wykluczające wzajemną interferencję proce-
sów. Sposoby te możemy podzielić na dwie grupy:
• wyłączanie przerwań na czas wykonywania niepodzielne-
go kodu, nazywanego sekcjami krytycznymi (ang. critical
sections);
• użycie muteksów.
Pierwszy sposób jest mało wydajny i gwarantuje niepodziel-
ność sekcji krytycznej jedynie w obrębie danego procesora,
dlatego jest on bezużyteczny w wypadku systemów wielopro-
cesorowych. Zostaje nam więc jedynie użycie muteksów (ang.
mutexes), czyli wszelkiego rodzaju blokad mających na ce-
lu zapewnienie, że dany obszar pamięci będzie wykonywany
maksymalnie N-tą ilość razy niezależnie od środowiska w ja-
kim działa system (np. różna ilość procesorów).
Blokady wirujące
Podstawowym muteksem jest blokada wirująca (ang. spin
lock), która opiera się na prostym algorytmie, który przedsta-
wić można w następujący sposób:
• sprawdź czy zmienna X jest równa 0;
• jeżeli tak, przejdź do kroku 4;
• jeżeli nie, przejdź do kroku 1;
• ustaw ją na 1 i przejdź do sekcji krytycznej;
• po wyjściu z sekcji krytycznej ustaw zmienną X na 0.
Tak jak widać, algorytm ten jest wręcz trywialny, a zarazem
w pełni spełnia nasze potrzeby. Jedynym problemem na ja-
ki możemy natrafić podczas implementacji tego rozwiązania
jest konieczność niepodzielności operacji
testuj _ i _ ustaw()
,
w przeciwnym razie po sprawdzeniu wartości zmiennej inny
proces, po wywłaszczeniu obecnego, również mógłby stwier-
dzić, że zmienna X ma wartość 0, co w konsekwencji do-
prowadziłoby do podwójnego wykonania sekcji krytycznej.
W systemach jednoprocesorowych efekt niepodzielności
można uzyskać poprzez chwilowe wyłączenie przerwań, na-
tomiast w wypadku wieloprocesorów musimy skorzystać ze
specjalnych instrukcji maszynowych, które wykonują dwie
podrzędne operacje w ramach jednej. Są to instrukcje zapro-
jektowane specjalnie do synchronizacji.
Semafory
Semafor to zmienna przyjmująca wartości całkowite, na któ-
rej możliwe są dwie operacje:
P()
i
V()
. Operacja
P()
powo-
duje zmniejszenie semafora o jeden i wstrzymuje proces, je-
śli nowa wartość semafora jest mniejsza niż zero. Operacja
V()
zwiększa semafor o jeden. Jeśli jego wartość jest teraz nie
większa niż zero, to jest budzony wątek oczekujący na sema-
forze (jeśli taki jest). Obie te funkcje, funkcja inicjującą
init-
sem()
oraz funkcja
CP()
będąca nieblokującą wersją funkcji
P()
,
przedstawiono na Listingu 8.
Na koniec
Właśnie skończyliście lekturę kursu programowania systemów
operacyjnych. Mam skromną nadzieję, że wiedza, którą zdo-
byliście przyda się każdemu programiście. Podstawowe infor-
macje na temat budowy systemu, pod który piszemy nasze
aplikacje są pomocne przy optymalizacji kodu. Dzięki świado-
mości tego, jakie działania są wykonywane w czasie wywołań
poszczególnych funkcji API, możemy dobrać optymalne algo-
rytmy ich wykorzystania. Jednak przede wszystkim jesteśmy
w stanie napisać własny system operacyjny dla naszych po-
trzeb. Pomimo że elementy opisane we wszystkich częściach
kursu można zaliczyć jedynie do krótkiego wprowadzenia, to
są one dobrym początkiem i zachętą do dalszego pogłębiania
wiedzy z tej dziedziny informatyki. W razie jakichkolwiek pytań
piszcie na adres: reqst@o2.pl. Postaram się w miarę możliwo-
ści odpowiadać na wasze pytania. n
Listing 8.
Przykładowa impelementacja semaforów
void
initsem
(
semaphore
*
sem
,
int
warto
ść
)
{
*
sem
=
warto
ść
;
}
void
P
(
semaphore
*
sem
)
{
*
sem
-=
1
;
while
(*
sem
<
0
)
za
ś
nij
;
}
void
V
(
semaphore
*
sem
)
{
*
sem
+=
1
;
if
(*
sem
=>
0
)
obud
ź
w
ą
tek
wstrzymany
na
semaforze
;
}
boolean
CP
(
semaphore
*
sem
)
{
if
(*
sem
>
0
)
{
*
sem
-=
1
;
return
TRUE
;
}
else
return
FALSE
;
}
W Sieci
• Polski portal poświęcony programowaniu systemów operacyj-
nych http://www.areoos.com/osdevpl
• Ogólnoświatowe forum programistów systemów operacyjnych
http://www.osdev.org
• Portal związany z programowaniem systemów, z wieloma kur-
sami oraz przykładami http://www.osdever.net/