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