2006 09 Wielozadaniowość w systemach operacyjnych [Inzynieria Oprogramowania]

Inżynieria

oprogramowania

www.sdjournal.org

Software Developer’s Journal 9/2006

Wielozadaniowość

w systemach operacyjnych

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

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

;

}

;

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

;

idt_table

[

pos

]

flags

;

idt_table

[

pos

]

offset15_0

offset

0xFFFF

;

idt_table

[

pos

]

offset31_16

(

offset

)

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

;

unsigned

long

;

unsigned

long

;

unsigned

long

;

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

;

unsigned

long

flags

;

unsigned

long

esp

;

unsigned

long

;

}

;

Listing 4.

Niskopoziomowa procedura obsługi

low_int_controller

pushal

pushl

movl

KERNEL_DS

, %

eax

movw

, %

movw

, %

movw

, %

movw

, %

movw

, %

call

high_level_handler

popl

popal

addl

$8, %

esp

iretl

.global

interrupt_X

pushl

jmp

__low_int_controller

Wielozadaniowość w systemach operacyjnych

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

nIrq

;

cached_irq_mask

mask

;

(

nIrq

)

outb

(

cached_A1

, 0xA1

);

else

outb

(

cached_21

, 0x21

);

}

void

enableIrqOnChip

(

uint32

nIrq

)

{

uint32

mask

(

nIrq

);

cached_irq_mask

mask

;

(

nIrq

)

outb

(

cached_A1

, 0xA1

);

else

outb

(

cached_21

, 0x21

);

}

__inline__

void

irqFlushAndAck

(

sint32

irq

)

{

(

irq

)

{

outb

(

0x60

irq

)

, 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

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

)

0xff,

GEN0_COUNTER

);

}

Listing 7.

Struktura reprezentująca segment stanu

zadania (ang. Task State Segment)

struct

TSS

{

uint16

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

empty5

;

uint16

empty6

;

uint16

empty7

;

uint16

empty8

;

uint16

empty9

;

uint16

empty10

;

uint16

ldt

empty11

;

uint16

trapflag

;

uint16

iomapbase

;

uint8

io_map

[

8192

];

}

;

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()

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

(

semaphore

sem

)

{

sem

;

while

sem

)

nij

;

}

void

(

semaphore

sem

)

{

sem

;

sem

)

obud

tek

wstrzymany

semaforze

;

}

boolean

(

semaphore

sem

)

{

sem

)

{

sem

;

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/