10. Szeregowanie wieloprocesorowe

i w czasie rzeczywistym

10.1 Szeregowanie wieloprocesorowe

ZiarnistoϾ
Problemy projektowe
Szeregowanie procesów
Szeregowanie w¹tków

10.2 Szeregowanie w czasie rzeczywistym

Informacje wstêpne
Cechy systemów operacyjnych czasu rzeczywistego
Szeregowanie w czasie rzeczywistym
Szeregowanie terminowe
Szeregowanie czêstotliwoœciowe monotoniczne

10.3 Szeregowanie w Linuksie
10.4 Szeregowanie w systemie UNIX SVR4
10.5 Szeregowanie w Windows 2000

Priorytety procesów i w¹tków
Szeregowanie wieloprocesorowe

10.6 Podsumowanie, kluczowe terminy i pytania kontrolne
10.7 Zalecane lektury
10.8 Zadania

W tym rozdziale kontynuujemy omawianie szeregowania procesów. Zaczniemy od zbadania kwestii,

które pojawiaj¹ siê w razie dostêpnoœci wiêcej ni¿ jednego procesora. Przyjrzymy siê kilku zagadnieniom

projektowym, po czym opiszemy szeregowanie procesów w systemie wieloprocesorowym. Nastêpnie

zbadamy nieco inne problemy konstrukcyjne zwi¹zane z wieloprocesorowym szeregowaniem w¹tków.

W drugiej czêœci tego rozdzia³u opiszemy szeregowanie w czasie rzeczywistym. Zaczniemy od omó-

wienia cech procesów czasu rzeczywistego, a nastêpnie poznamy naturê procesu szeregowania.

Omówimy dwa podejœcia do szeregowania w czasie rzeczywistym: szeregowanie terminowe oraz sze-

regowanie czêstotliwoœciowe monotoniczne.

10.1 Szeregowanie wieloprocesorowe

Jeœli system komputerowy zawiera wiêcej ni¿ jeden procesor, pojawia siê kilka nowych kwestii zwi¹zanych

z konstrukcj¹ funkcji szereguj¹cej (ang. scheduling function). Zaczniemy od krótkiego omówienia systemów

wieloprocesorowych, a nastêpnie przyjrzymy siê nieco odmiennym zagadnieniom zwi¹zanym z sze-

regowaniem na poziomie procesu i na poziomie w¹tku.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

404

Systemy wieloprocesorowe mo¿na sklasyfikowaæ nastêpuj¹co:

w System luŸno sprzê¿ony albo rozproszony, inaczej klaster: Zbiór wzglêdnie autonomicz-

nych systemów, w których ka¿dy procesor ma w³asn¹ pamiêæ i kana³y we-wy. Tym typem

konfiguracji zajmiemy siê w rozdziale 13.

w System z procesorami wyspecjalizowanymi: Przyk³adem mo¿e byæ procesor we-wy. W ta-

kim przypadku system zawiera g³ówny, uniwersalny procesor; procesory wyspecjalizowane

s¹ sterowane przez procesor g³ówny i dostarczaj¹ mu swoich us³ug. Kwestie zwi¹zane z pro-

cesorami we-wy omawiamy w rozdziale 11.

w System œciœle sprzê¿ony: Zbiór procesorów, które wspó³dziel¹ pamiêæ g³ówn¹ i dzia³aj¹ pod

zintegrowan¹ kontrol¹ systemu operacyjnego.

W niniejszym rozdziale zajmiemy siê trzeci¹ kategori¹ systemów, a konkretnie – kwestiami zwi¹za-

nymi z szeregowaniem.

ZiarnistoϾ (ang. Granularity)

Dobrym sposobem charakteryzowania systemów wieloprocesorowych i porównywania ich z innymi

architekturami jest rozwa¿enie ziarnistoœci synchronizacji, czyli czêstotliwoœci synchronizacji miêdzy

procesami w systemie. Mo¿emy wyró¿niæ piêæ kategorii paralelizmu, które ró¿ni¹ siê stopniem ziar-

nistoœci. Podsumowano je w tabeli 10.1 zaadaptowanej z [GEHR87] i [WOOD89].

Paralelizm niezale¿ny

W przypadku paralelizmu niezale¿nego (ang. independent parallelism) nie istnieje jawna synchronizacja

miêdzy procesami. Ka¿dy z nich reprezentuje odrêbn¹, niezale¿n¹ aplikacjê lub zadanie. Typowym

przyk³adem zastosowania tego rodzaju paralelizmu jest system z podzia³em czasu. Ka¿dy u¿ytkownik

wykonuje konkretn¹ aplikacjê, tak¹ jak procesor tekstu albo arkusz kalkulacyjny. System wielopro-

cesorowy œwiadczy te same us³ugi co wieloprogramowy system jednoprocesorowy. Poniewa¿ dostêpny

jest wiêcej ni¿ jeden procesor, œredni czas reakcji na dzia³ania u¿ytkowników bêdzie krótszy.

Tabela 10.1 ZiarnistoϾ synchronizacji i procesy.

Aby osi¹gn¹æ podobny wzrost wydajnoœci, mo¿na wyposa¿yæ ka¿dego u¿ytkownika w osobisty kom-

puter lub stacjê robocz¹. Jeœli zachodzi koniecznoœæ wspó³dzielenia plików lub informacji, poszczegól-

ne systemy musz¹ byæ po³¹czone sieci¹ w system rozproszony. Takie podejœcie omówiliœmy w rozdziale 13.

Z drugiej strony pojedynczy, wspó³dzielony system wieloprocesorowy czêsto bywa ekonomiczniejszy

ni¿ system rozproszony, zapewniaj¹c oszczêdnoœci na dyskach i innych urz¹dzeniach peryferyjnych.

Rozmiar ziarna

Opis

Czêstotliwoœæ

synchronizacji

(instrukcje)

Drobne

Paralelizm w jednym strumieniu instrukcji

< 20

Œrednie

Przetwarzanie równoleg³e albo wielozadaniowoœæ

20 – 200

w ramach jednej aplikacji

Grube

Wieloprzetwarzanie wspó³bie¿nych procesów

200 – 2000

w œrodowisku wieloprogramowym

Bardzo grube

Przetwarzanie rozproszone w wielu wêz³ach sieci

2000 – 1M

tworz¹cych jedno œrodowisko obliczeniowe

Niezale¿ne

Wiele niezwi¹zanych ze sob¹ procesów

Nie dotyczy

405

Szeregowanie wieloprocesorowe

Paralelizm grubo- i bardzo gruboziarnisty (ang. Coarse and Very Coarse-Grained

parallelism)

W przypadku paralelizmu grubo- i bardzo gruboziarnistego istnieje synchronizacja miêdzy procesami,

ale na bardzo wysokim poziomie. Tego rodzaju wymagania ³atwo spe³nia zbiór wspó³bie¿nych proce-

sów dzia³aj¹cych w wieloprogramowym systemie jednoprocesorowym, a przeniesienie go do systemu

wieloprocesorowego nie wymaga ¿adnych (albo prawie ¿adnych) zmian w oprogramowaniu u¿yt-

kownika.

Przyk³ad aplikacji, która mo¿e wykorzystaæ obecnoœæ wielu procesorów, podano w [WOODS89].

Autorzy opracowali program, który przyjmuje listê plików wymagaj¹cych rekompilacji w celu zbu-

dowania pewnego programu i ustala, które z tych kompilacji (zwykle wszystkie) mo¿na wykonaæ

jednoczeœnie. Nastêpnie program tworzy jeden proces dla ka¿dej równoleg³ej kompilacji. Autorzy

informuj¹, ¿e w systemie wieloprocesorowym przyspieszenie w rzeczywistoœci jest wiêksze ni¿ to,

które wynika³oby z prostego zsumowania u¿ywanych procesorów, ze wzglêdu na zbie¿noœci w bufo-

rach dyskowych (zagadnienie to omówiono w rozdziale 11) i wspó³dzielenie kodu kompilatora, który

jest ³adowany do pamiêci tylko raz.

Ogólnie rzecz bior¹c, dowolny zbiór wspó³bie¿nych procesów, które musz¹ siê ze sob¹ komunikowaæ lub

synchronizowaæ, mo¿e odnieœæ korzyœci dziêki zastosowaniu architektury wieloprocesorowej. W przypadku

bardzo rzadkich interakcji miêdzy procesami system rozproszony zapewnia dobr¹ obs³ugê. Jeœli jed-

nak interakcje s¹ nieco czêstsze, koszty komunikacji przez sieæ mog¹ uniemo¿liwiæ uzyskanie pe³nego

potencjalnego przyspieszenia. W takim przypadku najefektywniejsz¹ obs³ugê zapewnia organizacja

wieloprocesorowa.

Paralelizm œrednioziarnisty (ang. Madium-Grained parallelism)

W rozdziale 4 dowiedzieliœmy siê, ¿e aplikacjê mo¿na efektywnie zaimplementowaæ jako zbiór w¹t-

ków w obrêbie jednego procesu. W takim przypadku paralelizm aplikacji musi byæ jawnie zdefinio-

wany przez programistê. Zwykle konieczny jest doœæ wysoki stopieñ koordynacji i interakcji miêdzy

w¹tkami aplikacji, co prowadzi do œrednioziarnistej synchronizacji (ang. medium-grain level of synchroni-

zation).
Paralelizm niezale¿ny, gruboziarnisty i bardzo gruboziarnisty mo¿na zrealizowaæ w wieloprogra-

mowym systemie jednoprocesorowym albo systemie wieloprocesorowym bez ¿adnego (albo prawie

¿adnego) wp³ywu na funkcjê szereguj¹c¹. Jeœli jednak mamy do czynienia z w¹tkami, musimy ponow-

nie przyjrzeæ siê tej funkcji. Ró¿ne w¹tki aplikacji wchodz¹ w liczne interakcje, wiêc decyzje o szerego-

waniu jednego w¹tku mog¹ mieæ wp³yw na wydajnoœæ ca³ej aplikacji. Wrócimy do tego zagadnienia

dalej w tym podrozdziale.

Paralelizm drobnoziarnisty (ang. Fine-Grained Parallelism)

Paralelizm drobnoziarnisty reprezentuje du¿o bardziej z³o¿one u¿ycie przetwarzania równoleg³ego

ni¿ w przypadku w¹tków. Choæ wiele osób pracuje nad aplikacjami wysoce równoleg³ymi, jak dotych-

czas jest to bardzo wyspecjalizowana i fragmentaryczna dziedzina, z wieloma ró¿nymi podejœciami.

Dobry opis mo¿na znaleŸæ w [ALMA89].

Problemy projektowe

Szeregowanie w systemie wieloprocesorowym obejmuje trzy powi¹zane ze sob¹ kwestie:

w Przydzielanie procesów procesorom
w U¿ycie wieloprogramowoœci w poszczególnych procesorach
w Rzeczywiste skierowanie procesu do wykonania

Rozwa¿aj¹c te kwestie, nale¿y pamiêtaæ, ¿e przyjêta metoda bêdzie zale¿eæ – ogólnie rzecz bior¹c –

od stopnia ziarnistoœci aplikacji oraz liczby dostêpnych procesorów.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

406

Przydzielanie procesów procesorom

Jeœli za³o¿ymy, ¿e architektura systemu wieloprocesorowego jest jednolita – rozumiemy przez to, ¿e

¿aden procesor nie ma szczególnej fizycznej przewagi, jeœli chodzi o dostêp do pamiêci g³ównej lub

urz¹dzeñ we-wy – to najprostsze podejœcie do szeregowania polega na traktowaniu procesorów jako

puli zasobów i przydzielaniu procesów w zale¿noœci od zapotrzebowania. Powstaje wówczas pyta-

nie, czy przydzielanie powinno odbywaæ siê statycznie, czy dynamicznie?

Jeœli proces jest na sta³e przydzielany jednemu procesorowi, od aktywacji do zakoñczenia, wówczas

prowadzi siê krótkoterminow¹ kolejkê dla ka¿dego procesora z osobna. Metoda ta ma tê zaletê, ¿e

funkcja szereguj¹ca mo¿e dzia³aæ wydajniej, poniewa¿ przydzia³ procesora odbywa siê tylko raz. Po-

nadto sta³y przydzia³ procesora pozwala wykorzystaæ strategiê nazywan¹ szeregowaniem zespo³owym

(ang. gang scheduling), które omawiamy dalej w tym rozdziale.

Wad¹ przydzia³u statycznego jest to, ¿e kiedy jeden procesor jest bezczynny, drugi mo¿e byæ przeci¹-

¿ony. Aby zapobiec takiej sytuacji, mo¿na u¿yæ wspólnej kolejki. Wszystkie procesy trafiaj¹ do glo-

balnej kolejki i s¹ kierowane do wykonania przez dowolny dostêpny procesor. Tak wiêc w ci¹gu

swojego ¿ycia proces mo¿e byæ wykonywany w ró¿nych momentach przez ró¿ne procesory. W przy-

padku œciœle sprzê¿onej architektury ze wspó³dzielon¹ pamiêci¹ informacje kontekstowe o wszystkich

procesach s¹ dostêpne dla wszystkich procesorów, wiêc koszt szeregowania procesu nie zale¿y od

tego, który procesor go wykonuje.
Bez wzglêdu na to, czy procesy s¹ zwi¹zane na sta³e z procesorami, potrzebna jest jakaœ metoda przydzie-

lania procesów procesorom. S¹ dwa podejœcia: nadrzêdny-podrzêdny (ang. master-slave) albo równorzêd-

ny (ang. peer). W architekturze nadrzêdny-podrzêdny kluczowe funkcje j¹dra systemu operacyjnego

s¹ zawsze wykonywane przez jeden procesor. Pozosta³e procesory mog¹ wykonywaæ tylko programy

u¿ytkownika. Procesor nadrzêdny jest odpowiedzialny za szeregowanie zadañ. Kiedy proces jest ak-

tywny, a procesor podrzêdny wymaga obs³ugi (np. wywo³ania we-wy), musi wys³aæ ¿¹danie do proceso-

ra nadrzêdnego i zaczekaæ na jego realizacjê. Ta metoda jest doœæ prosta i wymaga tylko niewielkich

przeróbek jednoprocesorowego, wieloprogramowego systemu operacyjnego. Rozwi¹zywanie konflik-

tów jest uproszczone, poniewa¿ jeden procesor ma kontrolê nad wszystkimi zasobami pamiêciowymi

i we-wy. Dwie wady takiego podejœcia to: (1) awaria procesora nadrzêdnego za³amuje ca³y system; (2)

procesor nadrzêdny mo¿e siê staæ „w¹skim gard³em”.
W architekturze równorzêdnej system operacyjny mo¿e dzia³aæ na dowolnym procesorze, a ka¿dy

procesor przeprowadza samoszeregowanie (ang. self-scheduling) z puli dostêpnych procesów. System

operacyjny musi zagwarantowaæ, ¿e dwa procesory nie wybior¹ tego samego procesu i ¿e procesy nie

wypadn¹ z kolejki. Trzeba stosowaæ techniki rozwi¹zywania konfliktów i synchronizowania ¿¹dañ

dostêpu do zasobów.
Oczywiœcie, miêdzy tymi dwoma skrajnoœciami mieœci siê szerokie spektrum metod poœrednich. Przetwa-

rzaniem kodu j¹dra mo¿e zajmowaæ siê podzbiór procesorów, a nie tylko jeden. Inn¹ metod¹ jest rozró¿-

nianie potrzeb procesów j¹dra i innych procesów na podstawie priorytetów i historii wykonywania.

U¿ycie wieloprogramowoœci w poszczególnych procesorach

Kiedy proces jest statycznie przydzielany procesorowi na ca³y czas swojego dzia³ania, powstaje nowe

pytanie: czy ten procesor powinien dzia³aæ wieloprogramowo? Czytelnik mo¿e pocz¹tkowo zasta-

nawiaæ siê nad zasadnoœci¹ tego pytania; wi¹zanie procesora z jednym procesem, który mo¿e czêsto

siê blokowaæ w oczekiwaniu na we-wy albo ze wzglêdu na kwestie wspó³bie¿noœci i synchronizacji,

wydaje siê wyj¹tkowym marnotrawstwem.

W tradycyjnym systemie wieloprocesorowym, w którym mamy do czynienia z synchronizacj¹ gru-

boziarnist¹ lub niezale¿n¹ (patrz tabela 10.1), nie ulega w¹tpliwoœci, ¿e ka¿dy procesor powinien

móc prze³¹czaæ siê miêdzy procesami, aby osi¹gn¹æ wysoki stopieñ wykorzystania, a w konsekwencji

wiêksz¹ wydajnoœæ. Jednak¿e w przypadku aplikacji œrednioziarnistych dzia³aj¹cych w systemie z du¿¹

liczb¹ procesorów sytuacja jest mniej jasna. Kiedy dostêpnych jest wiele procesorów, nie jest ju¿ tak

istotne, aby ka¿dy procesor by³ jak najbardziej zajêty. Bardziej interesuje nas uzyskanie jak najlepszej

œredniej wydajnoœci aplikacji. Aplikacja, która sk³ada siê z kilku w¹tków, czêsto dzia³a ma³o wydajnie,

jeœli wszystkie jej w¹tki nie mog¹ wykonywaæ siê jednoczeœnie.

407

Szeregowanie wieloprocesorowe

Kierowanie procesów do wykonania

Ostatni¹ kwesti¹ projektow¹ zwi¹zan¹ z szeregowaniem wieloprocesorowym jest rzeczywisty wybór

procesu, który bêdzie wykonywany. Wiemy ju¿, ¿e w wieloprogramowym systemie jednoprocesorowym

mo¿na uzyskaæ wzrost wydajnoœci, stosuj¹c priorytety albo zaawansowane algorytmy szeregowania,

oparte na historii u¿ycia – zamiast prostej strategii „kto pierwszy, ten lepszy”. W przypadku systemów

wieloprocesorowych takie komplikacje mog¹ siê okazaæ niepotrzebne, a nawet szkodliwe, i niewykluczo-

ne, ¿e prostsza metoda z mniejszymi kosztami dodatkowymi bêdzie bardziej efektywna. W przypadku

szeregowania w¹tków w grê wchodz¹ nowe kwestie, które bywaj¹ wa¿niejsze od priorytetów czy historii

wykonywania. Zajmiemy siê kolejno ka¿dym z tych zagadnieñ.

Szeregowanie procesów (ang. Process scheduling)

W wiêkszoœci tradycyjnych systemów wieloprocesorowych procesy nie s¹ na sta³e zwi¹zane z proceso-

rami. Jedna kolejka obs³uguje wszystkie procesory, a jeœli u¿ywany jest jakiœ mechanizm priorytetowy,

istnieje wiele kolejek o zró¿nicowanym priorytecie, które kieruj¹ wszystkie procesy do wspólnej puli

procesorów. Tak czy inaczej, taki system reprezentuje architekturê kolejkowania wieloserwerowego.

Rozwa¿my przypadek systemu dwuprocesorowego, w którym szybkoœæ przetwarzania ka¿dego proce-

sora jest o po³owê mniejsza ni¿ procesora w systemie jednoprocesorowym. W [SAUE81] zamieszczono

analizê kolejkowania, która porównuje szeregowanie „kto pierwszy, ten lepszy” (FCFS) z metod¹

cykliczn¹ (RR) i „najkrótszy pozosta³y czas” (SRT). Badania dotycz¹ czasu obs³ugi procesu, czyli

iloœci czasu procesora wymaganej na wykonanie ca³ego zadania albo wykorzystywanej za ka¿dym

razem, kiedy proces jest gotowy do u¿ycia procesora. W przypadku szeregowania cyklicznego zak³ada

siê, ¿e kwant czasu jest d³ugi w porównaniu do czasu prze³¹czania kontekstu i krótki w porównaniu do

œredniego czasu obs³ugi. Wyniki zale¿¹ od obserwowanej zmiennoœci czasów obs³ugi. Popularn¹

miar¹ zmiennoœci jest wspó³czynnik wariacji, C

s

1

. WartoϾ C

s

 = 0 odpowiada przypadkowi, w którym:

czasy obs³ugi wszystkich procesów s¹ jednakowe. W miarê wzrostu wartoœci C

s

zwiêksza siê zmiennoœæ;

im wiêksza wartoœæ C

s

, tym wiêksze zró¿nicowanie obserwowanych czasów obs³ugi. W dystrybucji

czasów obs³ugi wartoœci C

s

wiêksze ni¿ 5 nie s¹ niczym niezwyk³ym.

Rysunek 10.1a porównuje przepustowoœæ szeregowania cyklicznego i FCFS jako funkcjê C

s

. Warto

zauwa¿yæ, ¿e ró¿nica miêdzy tymi algorytmami szeregowania jest znacznie mniejsza w przypadku

systemu dwuprocesorowego. Jeœli mamy do dyspozycji dwa procesory, to w przypadku szeregowania

FCFS proces o d³ugim czasie obs³ugi ma znacznie mniejszy wp³yw na system; pozosta³e procesy

mog¹ korzystaæ z drugiego procesora. Podobne wyniki s¹ pokazane na rysunku 10.1b.
W [SAUE81] powtórzono tê analizê, dokonuj¹c szeregu za³o¿eñ dotycz¹cych stopnia wieloprogra-

mowoœci, stosunku procesów powi¹zanych z we-wy do procesów powi¹zanych z procesorem oraz

wykorzystania priorytetów. Ogólny wniosek jest taki, ¿e re¿im szeregowania ma du¿o mniejsze znacze-

nie, jeœli zamiast jednego procesora u¿ywa siê dwóch. Wydaje siê oczywiste, ¿e wniosek ten staje siê

coraz bardziej uzasadniony w miarê zwiêkszania liczby procesorów. Zatem w systemie wieloprocesoro-

wym mo¿e wystarczyæ prosty re¿im FCFS albo zastosowanie FCFS w ramach metody ze statycznymi

priorytetami.

1

WartoϾ C

s

liczy siê jako ó

s

/T

s

, gdzie ó

s

to odchylenie standardowe czasu obs³ugi, a T

s

to œredni czas obs³ugi.

Dok³adniejsze wyjaœnienie wartoœci C

s

mo¿na znaleŸæ w dokumencie Queuing Analysis pod adresem William-

Stallings.com/StudentSupport.html.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

408

Rysunek 10.1 Porównanie wydajnoœci szeregowania w systemie z jednym i dwoma procesorami.

Szeregowanie w¹tków (ang. Thread scheduling)

Jak wiemy, w przypadku w¹tków pojêcie wykonywania jest oddzielone od reszty definicji procesu.

Aplikacjê mo¿na zrealizowaæ jako zbiór w¹tków, które wspó³pracuj¹ i wykonuj¹ siê wspó³bie¿nie w tej

samej przestrzeni adresowej.
W systemie jednoprocesorowym w¹tków u¿ywa siê do strukturyzowania programów i do przeplatania

operacji we-wy z przetwarzaniem. Prze³¹czanie w¹tków zajmuje znacznie mniej czasu ni¿ prze³¹czanie

409

Szeregowanie wieloprocesorowe

procesów, wiêc korzyœci te mo¿na osi¹gn¹æ niskim kosztem. Jednak¿e pe³na moc w¹tków przejawia

siê dopiero w systemie wieloprocesorowym. W takim œrodowisku w¹tki pozwalaj¹ wykorzystaæ rzeczywi-

sty paralelizm aplikacji. Jeœli ró¿ne w¹tki aplikacji wykonuj¹ siê jednoczeœnie na ró¿nych procesorach,

wzrost wydajnoœci bywa ogromny. Mo¿na jednak wykazaæ, ¿e w aplikacjach wymagaj¹cych licznych

interakcji miêdzy w¹tkami (paralelizm œrednioziarnisty), drobne ró¿nice w zarz¹dzaniu w¹tkami i ich

szeregowaniu mog¹ mieæ znaczny wp³yw na wydajnoœæ [ANDE89]. Szeregowanie w¹tków w systemach

wieloprocesorowych jest obecnie przedmiotem badañ; tutaj przedyskutujemy kluczowe kwestie i naj-

wa¿niejsze metody.
Wœród wielu propozycji szeregowania w¹tków i przydzia³u procesorów w systemach wieloproceso-

rowych wyró¿niaj¹ siê cztery ogólne podejœcia:

w Wspó³dzielenie obci¹¿enia (ang. Load sharing): Procesy nie s¹ przydzielane konkretnemu

procesorowi. Prowadzi siê globaln¹ kolejkê gotowych w¹tków, a ka¿dy procesor, kiedy jest

bezczynny, wybiera w¹tek z tej kolejki. Terminu wspó³dzielenie obci¹¿enia (ang. load sharing) u¿ywa

siê, aby odró¿niæ tê strategiê od metod równowa¿enia obci¹¿enia (ang. load balancing), w któ-

rych zadania przydziela siê na bardziej sta³ych zasadach (patrz np. [FEIT90a])

2

.

w Szeregowanie zespo³owe (ang. Gang scheduling): Zbiór powi¹zanych procesów jest jednoczeœnie

kierowany do wykonania przez zbiór procesorów, na zasadzie „jeden do jednego”.

w Rezerwacja procesorów (ang. Dedicated processor assignment): Przeciwieñstwo wspó³dzielenia

obci¹¿enia zapewnia niejawne szeregowanie zdefiniowane przez przydzia³ w¹tków procesorom.

Ka¿demu programowi przydziela siê na czas wykonywania liczbê procesorów równ¹ liczbie

w¹tków w programie. Kiedy program zakoñczy pracê, procesory wracaj¹ do ogólnej puli i mog¹

zostaæ przydzielone innemu programowi.

w Szeregowanie dynamiczne (ang. Dynamic scheduling): Liczba w¹tków w procesie mo¿e siê

zmieniaæ w czasie wykonywania.

Wspó³dzielenie obci¹¿enia

Wspó³dzielenie obci¹¿enia (ang. load sharing) to prawdopodobnie najprostsza metoda, przeniesiona

bez wiêkszych zmian ze œrodowiska jednoprocesorowego. Ma kilka zalet:

w Obci¹¿enie rozk³ada siê równo na wszystkie procesory, dziêki czemu ¿aden procesor nie

pozostaje bezczynny, kiedy jest praca do wykonania.

w Nie trzeba u¿ywaæ centralnego mened¿era szeregowania; kiedy procesor jest dostêpny, proce-

dura szereguj¹ca systemu operacyjnego wykonuje siê na tym procesorze, aby wybraæ nastêpny

w¹tek.

w Globaln¹ kolejkê mo¿na zorganizowaæ i obs³ugiwaæ z wykorzystaniem dowolnej spoœród

metod omówionych w rozdziale 9, w tym metod opartych na priorytetach oraz metod

uwzglêdniaj¹cych historiê wykonywania albo przewidywane czasy przetwarzania.
[LEUT90] analizuje trzy ró¿ne wersje wspó³dzielenia obci¹¿enia:

w Kto pierwszy, ten lepszy (FCFS): Kiedy przybywa zadanie, ka¿dy z jego w¹tków jest kolejno

umieszczany na koñcu wspó³dzielonej kolejki. Kiedy procesor jest bezczynny, wybiera na-

stêpny gotowy w¹tek i wykonuje go do chwili zakoñczenia lub zablokowania.

w Najpierw najmniejsza liczba w¹tków: Wspó³dzielona kolejka gotowych w¹tków jest zorga-

nizowana na zasadzie priorytetowej, przy czym najwy¿szy priorytet otrzymuj¹ w¹tki zadañ

o najmniejszej liczbie nieprzydzielonych w¹tków. Zadania o jednakowym priorytecie s¹ szere-

gowane wed³ug kolejnoœci przybycia. Podobnie jak w przypadku FCFS, przydzielony w¹tek

jest wykonywany do chwili zakoñczenia lub zablokowania.

w Najpierw najmniejsza liczba w¹tków, z wyw³aszczaniem: Najwy¿szy priorytet otrzymuj¹

w¹tki zadañ o najmniejszej liczbie nieprzydzielonych w¹tków. Nowe zadanie z mniejsz¹

liczb¹ w¹tków ni¿ wykonywane zadanie wyw³aszcza w¹tki nale¿¹ce do przydzielonego zadania.

2

W literaturze przedmiotu tê metodê okreœla siê czasem mianem samoszeregowania, poniewa¿ ka¿dy procesor szereguje siê

bez uwzglêdniania innych procesorów. Termin samoszeregowanie bywa jednak równie¿ u¿ywany na oznaczenie progra-

mów napisanych w jêzyku, który pozwala programiœcie na okreœlenie szeregowania (patrz np. [FOST91]).

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

410

Na podstawie przeprowadzonej symulacji autorzy doszli do wniosku, ¿e dla szerokiej gamy zadañ o zró¿nico-

wanej charakterystyce szeregowanie FCFS przewy¿sza pozosta³e dwie strategie z powy¿szej listy. Co

wiêcej, autorzy odkryli, ¿e pewne odmiany szeregowania zespo³owego (omówionego w nastêpnym

podrozdziale) s¹ zwykle wydajniejsze od wspó³dzielenia obci¹¿enia.

Wspó³dzielenie obci¹¿enia ma kilka wad:
w Centralna kolejka zajmuje obszar pamiêci, z którego trzeba korzystaæ w sposób wymuszaj¹cy

wzajemne wykluczanie. Kiedy wiele procesorów jednoczeœnie szuka pracy, kolejka ta mo¿e

staæ siê w¹skim gard³em. Jeœli liczba procesorów jest niewielka, problem prawdopodobnie

nie bêdzie odczuwalny. Jeœli jednak system sk³ada siê z dziesi¹tek albo setek procesorów,

ryzyko w¹skiego gard³a staje siê realne.

w Wyw³aszczone w¹tki rzadko wznawiaj¹ dzia³anie na tym samym procesorze. Jeœli ka¿dy pro-

cesor jest wyposa¿ony w lokaln¹ pamiêæ podrêczn¹, buforowanie staje siê mniej efektywne.

w Jeœli wszystkie w¹tki traktuje siê jako wspóln¹ pulê, jest ma³o prawdopodobne, ¿e wszystkie

w¹tki jednego programu jednoczeœnie uzyskaj¹ dostêp do procesorów. Jeœli w¹tki programu

wymagaj¹ wysokiego stopnia koordynacji, koniecznoœæ prze³¹czania procesów mo¿e znacznie

obni¿yæ wydajnoœæ.

Pomimo tych potencjalnych wad wspó³dzielenie obci¹¿enia jest najczêœciej u¿ywan¹ metod¹ we wspó³-

czesnych systemach wieloprocesorowych.
Udoskonalon¹ technikê wspó³dzielenia obci¹¿enia zastosowano w systemie operacyjnym Mach

[BLAC90, WEND89]. System operacyjny prowadzi lokaln¹ kolejkê wykonywania dla ka¿dego pro-

cesora i wspó³dzielon¹, globaln¹ kolejkê wykonywania. Lokalna kolejka jest u¿ywana przez w¹tki,

które zosta³y tymczasowo powi¹zane z konkretnym procesorem. Procesor bada najpierw lokaln¹

kolejkê i daje w¹tkom powi¹zanym bezwzglêdne pierwszeñstwo przed w¹tkami niepowi¹zanymi.

Przyk³adem zastosowania w¹tków powi¹zanych jest rezerwowanie jednego lub kilku procesorów dla

dzia³aj¹cych procesów bêd¹cych czêœci¹ systemu operacyjnego. Inny przyk³ad to podzia³ w¹tków

konkretnej aplikacji miêdzy kilka procesorów; przy pomocy dodatkowego oprogramowania mo¿na

w ten sposób zrealizowaæ szeregowanie zespo³owe, które omawiamy poni¿ej.

Szeregowanie grupowe (ang. Gang scheduling)

Idea jednoczesnego przydzielania zbioru procesów zbiorowi procesorów poprzedza koncepcjê w¹tków.

[JONE80] okreœla to mianem szeregowania grupowego i przytacza nastêpuj¹ce korzyœci:

w Jeœli blisko powi¹zane procesy wykonuj¹ siê równolegle, rzadziej wystêpuj¹ blokady spowo-

dowane koniecznoœci¹ synchronizacji i nie trzeba tak czêsto prze³¹czaæ procesów, wskutek

czego wzrasta wydajnoϾ.

w Mo¿na zmniejszyæ dodatkowe koszty szeregowania, poniewa¿ jedna decyzja jednoczeœnie

wp³ywa na kilka procesorów i procesów.

W systemie wieloprocesorowym Cm* u¿ywa siê terminu wspó³szeregowanie (ang. coscheduling) [GEHR87].

Wspó³szeregowanie polega na szeregowaniu powi¹zanych zbiorów zadañ, nazywanych zestawami

zadañ. Poszczególne elementy zestawu zadañ s¹ zwykle niewielkie, a wiêc zbli¿one do idei w¹tku.

Termin szeregowanie zespo³owe (ang. gang scheduling) oznacza jednoczesne szeregowanie w¹tków two-

rz¹cych jeden proces [FEIT90b]. Jest to niezbêdne w œrednio- i drobnoziarnistych aplikacjach rów-

noleg³ych, których wydajnoœæ znacznie spada, jeœli dowolna czêœæ aplikacji nie dzia³a, kiedy inne s¹

gotowe do wykonania. Szeregowanie zespo³owe jest zreszt¹ korzystne we wszystkich aplikacjach rów-

noleg³ych, nawet tych mniej wra¿liwych na kwestie wydajnoœciowe. Powszechnie uznaje siê potrzebê

szeregowania zespo³owego, a jego implementacje s¹ dostêpne w licznych wieloprocesorowych syste-

mach operacyjnych.
Szeregowanie zespo³owe zwiêksza wydajnoœæ pojedynczej aplikacji miêdzy innymi dlatego, ¿e mini-

malizuje prze³¹czanie procesów. Przypuœæmy, ¿e jeden z w¹tków procesu wykonuje siê i osi¹ga punkt,

w którym musi zsynchronizowaæ siê z innym w¹tkiem tego samego procesu. Jeœli tamten w¹tek nie dzia-

³a, ale znajduje siê w kolejce gotowych w¹tków, pierwszy w¹tek pozostaje zawieszony a¿ do momentu,

411

Szeregowanie wieloprocesorowe

w którym jeden z pozosta³ych procesorów bêdzie móg³ prze³¹czyæ proces i zacz¹æ wykonywaæ po-

trzebny w¹tek. W aplikacji ze œcis³¹ koordynacj¹ miêdzy w¹tkami takie prze³¹czenia bardzo obni¿aj¹

wydajnoœæ. Jednoczesne szeregowanie wspó³pracuj¹cych w¹tków mo¿e równie¿ zaoszczêdziæ czas

poœwiêcany na alokacjê zasobów. Np. kilka w¹tków szeregowanych zespo³owo mo¿e uzyskaæ dostêp

do pliku bez dodatkowych kosztów blokowania podczas operacji wyszukiwania albo zapisu/odczytu.
U¿ycie szeregowania zespo³owego wymaga przydzielania procesorów. Oto jedna z mo¿liwoœci: za-

³ó¿my, ¿e mamy N procesorów i M aplikacji, z których ka¿da sk³ada siê z N lub mniejszej liczby

w¹tków. W takim przypadku ka¿dej aplikacji mo¿na przydzieliæ 1/M dostêpnego czasu na N proceso-

rach, u¿ywaj¹c ciêcia czasu (ang. time slicing). [FEIT90a] zauwa¿a, ¿e taka strategia mo¿e byæ nieefektywna.

Przypuœæmy, ¿e mamy dwie aplikacje, jedn¹ z czterema w¹tkami, a drug¹ z jednym. U¿ycie jednolitego

przydzia³u czasu marnotrawi 37,5% zasobów obliczeniowych, poniewa¿ kiedy dzia³a aplikacja jed-

now¹tkowa, trzy procesory s¹ bezczynne. Jeœli w systemie dzia³a kilka aplikacji jednow¹tkowych,

mo¿na upakowaæ je razem, aby zwiêkszyæ stopieñ wykorzystania procesora. Jeœli taka opcja jest niedo-

stêpna, zamiast szeregowania jednolitego mo¿na u¿yæ szeregowania wa¿onego wed³ug liczby w¹tków.

Zatem aplikacja czterow¹tkowa mo¿e otrzymaæ 4/5 czasu, a aplikacja jednow¹tkowa – tylko 1/5 czasu,

przez co marnotrawstwo czasu procesora zmniejszy siê do poziomu 15%.

Rezerwacja procesorów (ang. Dedicated processor assignment)

Skrajn¹ form¹ szeregowania zespo³owego, zasugerowan¹ w [TUCK89], jest zarezerwowanie grupy

procesorów na wy³¹czny u¿ytek aplikacji przez ca³y czas jej trwania. Kiedy aplikacja zostanie skiero-

wana do wykonania, ka¿demu z jej w¹tków przydziela siê procesor, który pozostaje zarezerwowany

dla tego w¹tku a¿ do chwili ukoñczenia aplikacji.

Takie podejœcie wydaje siê bardzo rozrzutne, jeœli chodzi o czas procesora. Jeœli w¹tek aplikacji zablokuje

siê w oczekiwaniu na we-wy albo na synchronizacjê z innym w¹tkiem, wówczas procesor tego w¹tku

pozostaje bezczynny: nie ma wieloprogramowania procesorów. Mo¿na jednak wysun¹æ dwa argu-

menty w obronie tej strategii:

1. W systemie o wysokim stopniu paralelizmu, z dziesi¹tkami lub setkami procesorów, z któ-

rych ka¿dy reprezentuje ma³y u³amek kosztu systemu, wykorzystanie procesora nie jest tak

istotne jak metryki dotycz¹ce efektywnoœci czy wydajnoœci.

2. Ca³kowity brak prze³¹czania procesów podczas ¿ycia programu powinien doprowadziæ do

znacznego przyspieszenia tego programu.

Zarówno [TUCK89], jak i [ZAHO90] przytaczaj¹ analizy, które potwierdzaj¹ prawdziwoœæ drugiego

stwierdzenia. Autorzy wykonywali dwie aplikacje, mno¿enie macierzy i szybk¹ transformacjê Fo-

uriera (FFT), w systemie z szesnastoma procesorami. Ka¿da aplikacja dzieli swój problem na kilka

zadañ, odwzorowuj¹c je na w¹tki wykonawcze. Programy s¹ napisane w taki sposób, aby liczba u¿y-

wanych w¹tków mog³a siê zmieniaæ. Zasadniczo polega na tym, ¿e aplikacja definiuje i kolejkuje

pewn¹ liczbê zadañ. Zadania s¹ pobierane z kolejki i odwzorowywane na dostêpne w¹tki przez apli-

kacjê. Jeœli jest mniej w¹tków ni¿ zadañ, pozosta³e zadania pozostaj¹ w kolejce i s¹ przejmowane

przez w¹tki w miarê koñczenia przydzielonych zadañ. Oczywiœcie, nie wszystkim aplikacjom mo¿na

nadaæ tak¹ strukturê, ale sprawdza siê ona w wielu problemach liczbowych i niektórych innych apli-

kacjach.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

412

Rysunek 10.3 Przyspieszenie aplikacji jako funkcja liczby procesów [TUCK89].

Rysunek 10.3 przedstawia przyspieszenie aplikacji w miarê, jak liczba w¹tków wykonuj¹cych zadania

ka¿dej aplikacji zmienia siê w zakresie od 1 do 24. Widzimy na przyk³ad, ¿e kiedy obie aplikacje

zostan¹ jednoczeœnie uruchomione z 24 w¹tkami w ka¿dej, uzyskane przyspieszenie – w porówna-

niu z u¿yciem jednego w¹tku dla ka¿dej aplikacji – wynosi 2,8 w przypadku mno¿enia macierzy i 2,4

– w przypadku FFT. Rysunek pokazuje, ¿e przyspieszenie obu aplikacji znacznie siê pogarsza, kiedy

liczba w¹tków w ka¿dej z nich przekracza 8, a wiêc ca³kowita liczba procesów w systemie przewy¿sza

liczbê procesorów. Co wiêcej, im wiêksza liczba w¹tków, tym gorsza wydajnoœæ, poniewa¿ zwiêksza

siê czêstotliwoœæ wyw³aszczania i wznawiania w¹tków. Nadmierne wyw³aszczanie prowadzi do spadku

wydajnoœci, którego Ÿród³em jest m.in. czas oczekiwania na opuszczenie sekcji krytycznej przez za-

wieszony w¹tek, czas zmarnowany na prze³¹czanie procesów i nieefektywne dzia³anie pamiêci pod-

rêcznej.
Autorzy dochodz¹ do wniosku, ¿e efektywn¹ strategi¹ jest ograniczenie liczby aktywnych w¹tków

do liczby procesorów w systemie. Jeœli wiêkszoœæ aplikacji albo ma jeden w¹tek, albo mo¿e u¿ywaæ

struktury z kolejk¹ zadañ, taka strategia zapewni efektywne i rozs¹dne u¿ycie zasobów procesorowych.

Zarówno rezerwacja procesorów, jak i szeregowanie zespo³owe próbuj¹ uporaæ siê z problemem szere-

gowania, podnosz¹c kwestiê alokacji procesorów. Mo¿na zauwa¿yæ, ¿e alokacja procesorów w systemie

wieloprocesorowym bardziej przypomina alokacjê pamiêci ni¿ szeregowanie w systemie jednoproce-

sorowym. Pytanie, ile procesorów przydzieliæ programowi w danym czasie, przypomina kwestiê przy-

dzia³u liczby stron pamiêci procesowi. [GEHR87] proponuje termin zbiór roboczy aktywnoœci (ang. acti-

vity working set), analogiczny do zbioru roboczego pamiêci wirtualnej, na oznaczenie minimalnej

liczby aktywnoœci (w¹tków), które musz¹ byæ jednoczeœnie wykonywane przez procesory, aby aplikacja

czyni³a zadowalaj¹ce postêpy. Podobnie jak w przypadku metod zarz¹dzania pamiêci¹, niemo¿noœæ

przydzielenia wszystkich elementów zbioru roboczego aktywnoœci mo¿e prowadziæ do szamotania

(ang. thrashing) procesora. Dzieje siê tak wtedy, gdy przydzielenie w¹tków, których us³ugi s¹ potrzebne

w danej chwili, powoduje wstrzymanie w¹tków, które bêd¹ potrzebne niebawem. Podobnie, frag-

mentacja procesora oznacza sytuacjê, w której czêœæ procesorów pozostaje nieprzydzielona, poniewa¿

wolnych procesorów jest za ma³o albo s¹ nieodpowiednio zorganizowane, aby sprostaæ wymaga-

niom oczekuj¹cej aplikacji. Szeregowanie zespo³owe i rezerwacja procesorów maj¹ zapobiegaæ takim

problemom.

Szeregowanie dynamiczne (ang. Dynamic scheduling)

W niektórych aplikacjach mo¿liwe by³oby u¿ycie narzêdzi jêzykowych i systemowych, które pozwalaj¹

na dynamiczn¹ zmianê liczby w¹tków w procesie. Dziêki temu system operacyjny móg³by regulowaæ

obci¹¿enie, aby zoptymalizowaæ stopieñ wykorzystania procesora.
[ZAHO90] proponuje rozwi¹zanie, w którym zarówno system operacyjny, jak i aplikacja s¹ zaanga¿o-

wane w podejmowanie decyzji o szeregowaniu. System operacyjny odpowiada za partycjonowanie

413

Szeregowanie w czasie rzeczywistym

procesorów miêdzy zadania. Ka¿de zadanie u¿ywa procesorów znajduj¹cych siê obecnie w jego par-

tycji, aby wykonywaæ pewien podzbiór czynnoœci, mapuj¹c te czynnoœci na w¹tki. Decyzje dotycz¹ce

tego, który podzbiór czynnoœci wykonywaæ, a tak¿e który w¹tek zawiesiæ w razie wyw³aszczenia pro-

cesów, pozostaj¹ w gestii poszczególnych aplikacji (która podejmuje je np. za poœrednictwem zbioru

procedur bibliotecznych). Takie podejœcie nie jest odpowiednie dla wszystkich aplikacji. Jednak¿e

pewne aplikacje mog³yby domyœlnie u¿ywaæ jednego w¹tku, a inne programowa³oby siê tak, aby

korzysta³y z tej szczególnej cechy systemu operacyjnego.

W takiej metodzie zadania systemu operacyjnego zwi¹zane z szeregowaniem ograniczaj¹ siê alokacji

procesorów i przebiegaj¹ zgodnie z opisan¹ ni¿ej procedur¹. Kiedy zadanie ¿¹da jednego lub wielu

procesorów (albo w momencie przybycia, albo ze wzglêdu na zmianê wymagañ):

1. Jeœli s¹ bezczynne procesory, u¿yæ ich do spe³nienia ¿¹dania.
2. W przeciwnym razie, jeœli ¿¹danie zosta³o zg³oszone przez nowo przyby³e zadanie, przydzieliæ

mu jeden procesor, zabieraj¹c go zadaniu, które obecnie dysponuje wiêcej ni¿ jednym procesorem.

3. Jeœli nie mo¿na spe³niæ dowolnej czêœci ¿¹dania, ¿¹danie czeka, a¿ zwolni siê dla niego procesor

albo zadanie wycofa ¿¹danie (np. kiedy dodatkowe procesory przestan¹ byæ potrzebne).

Po zwolnieniu jednego lub wielu procesorów (tak¿e po zakoñczeniu zadania):
4. Przeskanowaæ kolejkê niezrealizowanych ¿¹dañ przydzielenia procesora. Przydzieliæ jeden

procesor ka¿demu zadaniu na liœcie, które obecnie nie ma procesora (tzn. wszystkim oczekuj¹-

cym, nowo przyby³ym zadaniom). Nastêpnie ponownie przeskanowaæ listê, przydzielaj¹c resztê

procesorów na zasadzie „kto pierwszy, ten lepszy”.

Analizy przedstawione w [ZAHO90] i [MAJU88] sugeruj¹, ¿e w aplikacjach, które potrafi¹ wykorzy-

staæ szeregowanie dynamiczne, metoda ta przewy¿sza szeregowanie zespo³owe i rezerwacjê proceso-

rów. Jednak¿e jej koszty dodatkowe mog¹ zanegowaæ pozorny wzrost wydajnoœci. Walory szeregowania

dynamicznego musz¹ zostaæ potwierdzone doœwiadczeniami w rzeczywistych systemach operacyjnych.

10.2 Szeregowanie w czasie rzeczywistym

Informacje wstêpne

Przetwarzanie w czasie rzeczywistym staje siê coraz wa¿niejsz¹ dyscyplin¹. System operacyjny, a zw³asz-

cza mened¿er szeregowania (ang. scheduler), jest prawdopodobnie najwa¿niejszym sk³adnikiem systemu

czasu rzeczywistego. Wœród obecnych zastosowañ systemów czasu rzeczywistego mo¿na wymieniæ

sterowanie eksperymentami laboratoryjnymi, zarz¹dzanie procesami produkcyjnymi, robotykê,

kontrolê ruchu powietrznego, telekomunikacjê oraz wojskowe systemy dowodzenia i kontroli. Sys-

temy nastêpnej generacji bêd¹ obs³ugiwaæ autonomiczne pojazdy terenowe, kontrolery robotów

z elastycznymi przegubami, systemy inteligentnego wytwarzania, stacje kosmiczne i badania podwodne.

Przetwarzanie w czasie rzeczywistym mo¿na zdefiniowaæ jako taki typ przetwarzania, w którym prawi-

d³owe dzia³anie systemu zale¿y nie tylko od logicznych wyników obliczeñ, ale tak¿e od czasu, w jakim

zostan¹ uzyskane te wyniki. Aby zdefiniowaæ system czasu rzeczywistego, mo¿emy okreœliæ, co rozu-

miemy przez proces lub zadanie

3

czasu rzeczywistego. Ogólnie rzecz bior¹c, w systemie czasu rzeczy-

wistego niektóre zadania s¹ zadaniami czasu rzeczywistego i wymagaj¹ mniej lub bardziej pilnej

realizacji. Takie zadania próbuj¹ kontrolowaæ lub reagowaæ na zdarzenia zachodz¹ce w œwiecie

zewnêtrznym. Poniewa¿ zdarzenia te zachodz¹ w „czasie rzeczywistym”, zadanie czasu rzeczywistego

musi nad¹¿aæ za zdarzeniami, które go dotycz¹. Zwykle da siê zatem okreœliæ nieprzekraczalny termin

dla danego zadania, który wyznacza czas jego rozpoczêcia lub zakoñczenia. Zadania te mo¿na skla-

syfikowaæ jako „twarde” lub „miêkkie”. Twarde zadanie czasu rzeczywistego (ang. hard real-time

task) to takie, które musi dotrzymaæ wyznaczonego terminu, bo w przeciwnym razie doprowadzi do

niepo¿¹danych szkód albo krytycznego b³êdu systemu. Miêkkie zadanie czasu rzeczywistego (ang.

soft real-time task) ma wyznaczony termin, którego dotrzymanie jest po¿¹dane, ale nie obowi¹zkowe;

warto je uszeregowaæ i dokoñczyæ nawet po up³ywie terminu.

3

Jak zwykle, terminologia nastrêcza problemów, poniewa¿ w literaturze przedmiotu u¿ywa siê ró¿nych s³ów w ró¿nych

znaczeniach. Czêsto zdarza siê, ¿e dany proces operuje w sposób powtarzalny w ograniczonych czasowo ramach. Znaczy

to, ¿e proces trwa d³ugo i wykonuje pewn¹ powtarzaln¹ funkcjê w reakcji na zdarzenia zachodz¹ce w czasie rzeczywistym.

W tym podrozdziale zadaniem bêdziemy nazywali pojedyncz¹ funkcjê. Mo¿emy zatem uznaæ, ¿e proces przechodzi przez se-

kwencjê zadañ. W dowolnym momencie proces jest zaanga¿owany w jedno zadanie, i w³aœnie to zadanie wymaga uszeregowania.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

414

Inn¹ cech¹ zadañ czasu rzeczywistego jest okresowoœæ lub nieokresowoœæ. Zadanie nieokresowe (ang.

aperiodic task) ma okreœlony termin rozpoczêcia lub zakoñczenia albo limit zarówno czasu rozpoczêcia,

jak i zakoñczenia. W przypadku zadania okresowego (ang. periodic task) wymaganie mo¿e brzmieæ

„raz na okres T” albo „dok³adnie co T jednostek czasu”.

Cechy systemów operacyjnych czasu rzeczywistego

Systemy operacyjne czasu rzeczywistego charakteryzuj¹ siê szczególnymi wymaganiami w piêciu

dziedzinach [MORG92]:

w Determinizm
w ReaktywnoϾ
w Stopieñ kontroli u¿ytkownika
w NiezawodnoϾ
w Czêœciowa odpornoœæ na uszkodzenia

System operacyjny jest deterministyczny w tym sensie, ¿e wykonuje operacje w sta³ych, z góry zdefinio-

wanych czasach albo odstêpach czasu. Kiedy wiele procesorów konkuruje o zasoby i czas procesora, ¿aden

system nie jest ca³kowicie deterministyczny. W systemie operacyjnym czasu rzeczywistego ¿¹dania obs³ugi

zg³aszane przez procesy s¹ podyktowane zewnêtrznymi zdarzeniami i relacjami czasowymi. Stopieñ,

w jakim system operacyjny mo¿e deterministycznie spe³niaæ te ¿¹dania, zale¿y od szybkoœci, z jak¹ reaguje

na przerwania, a tak¿e od tego, czy ma wystarczaj¹c¹ wydajnoœæ, aby obs³u¿yæ wszystkie ¿¹dania w wyma-

ganym czasie.
Przydatn¹ miar¹ zdolnoœci systemu do funkcjonowania w sposób deterministyczny jest maksymal-

ne opóŸnienie od przybycia przerwania sprzêtowego o wysokim priorytecie do rozpoczêcia jego

obs³ugi. W zwyk³ym systemie operacyjnym opóŸnienie to mo¿e wynosiæ od dziesi¹tek do setek milise-

kund, natomiast w systemie czasu rzeczywistego górna granica czêsto wynosi od kilku mikrosekund

do milisekundy.
Pokrewn¹, choæ odrêbn¹ cech¹ jest reaktywnoœæ (ang. responsiveness). Determinizm wi¹¿e siê z tym,

jak d³ugo system operacyjny zwleka z potwierdzeniem przerwania. Reaktywnoœæ dotyczy zaœ tego,

ile czasu – po potwierdzeniu – zajmuje systemowi obs³uga przerwania. Ró¿ne aspekty reaktywno-

œci to:

1. Iloœæ czasu potrzebna na wstêpne obs³u¿enie przerwania i rozpoczêcie wykonywania proce-

dury obs³ugi przerwania. Jeœli wykonanie procedury obs³ugi wymaga prze³¹czenia procesów,

opóŸnienie bêdzie wiêksze ni¿ w przypadku wykonania procedury obs³ugi w kontekœcie bie-

¿¹cego procesu.

2. Iloœæ czasu potrzebna na wykonanie procedury obs³ugi przerwania. Zwykle zale¿y to od plat-

formy sprzêtowej.

3. Wp³yw zagnie¿d¿ania przerwañ (ang. interrupt nesting). Jeœli procedura obs³ugi mo¿e zostaæ

wstrzymana na skutek przybycia nowego przerwania, obs³uga bêdzie opóŸniona.

Determinizm i reaktywnoœæ sk³adaj¹ siê na czas reakcji na zewnêtrzne zdarzenia. Wymagania doty-

cz¹ce czasu reakcji maj¹ kluczowe znaczenie w systemach czasu rzeczywistego, poniewa¿ systemy te

musz¹ funkcjonowaæ w ramach czasowych wyznaczanych przez osoby, urz¹dzenia i przep³ywy danych

istniej¹ce na zewn¹trz systemu.

Stopieñ kontroli u¿ytkownika jest, ogólnie rzecz bior¹c, znacznie wiêkszy w systemie czasu rzeczy-

wistego ni¿ w zwyk³ym systemie operacyjnym. W typowym systemie u¿ytkownik albo w ogóle nie

ma kontroli nad funkcj¹ szeregowania, albo mo¿e podaæ tylko ogólne wskazówki, takie jak przypisanie

u¿ytkowników do wiêcej ni¿ jednej klasy priorytetu. Natomiast w systemie czasu rzeczywistego u¿yt-

kownik musi mieæ szczegó³ow¹ kontrolê nad priorytetem zadañ. U¿ytkownik powinien móc dzieliæ

zadania na twarde i miêkkie oraz okreœlaæ wzglêdne priorytety w obu klasach. System czasu rzeczywistego

mo¿e równie¿ pozwalaæ na okreœlanie, czy wolno stronicowaæ albo wymieniaæ procesy, które procesy

415

Szeregowanie w czasie rzeczywistym

musz¹ zawsze pozostawaæ w pamiêci g³ównej, jakich algorytmów transmisji dyskowej nale¿y u¿yæ,

jakie prawa maj¹ procesy w ró¿nych pasmach priorytetu itd.
Niezawodnoœæ jest zwykle znacznie wa¿niejsza w systemach czasu rzeczywistego ni¿ w zwyk³ych

systemach operacyjnych. Z przejœciow¹ awari¹ w zwyk³ym systemie mo¿na uporaæ siê, po prostu

ponownie uruchamiaj¹c system. Awaria procesora w zwyk³ym systemie wieloprocesorowym mo¿e

obni¿yæ poziom obs³ugi do czasu naprawy lub wymiany uszkodzonego procesora. Ale system czasu

rzeczywistego musi reagowaæ na zdarzenia i kontrolowaæ je w czasie rzeczywistym. Spadek wydajnoœci

mo¿e mieæ katastrofalne konsekwencje, od strat finansowych i powa¿nych uszkodzeñ sprzêtu a¿ do

utraty ¿ycia.

Podobnie jak w innych dziedzinach, ró¿nica miêdzy systemem czasu rzeczywistego a zwyk³ym syste-

mem operacyjnym to kwestia stopnia. Nawet system czasu rzeczywistego musi byæ zaprojektowany

tak, aby radzi³ sobie z ró¿nymi awariami. Czêœciowa odpornoœæ na uszkodzenia to zdolnoœæ systemu

do takiego dzia³ania w razie awarii, które zachowuje jak najwiêcej mocy obliczeniowej i danych. Na

przyk³ad kiedy typowy, tradycyjny system uniksowy wykryje uszkodzenie danych w j¹drze, wtedy wy-

sy³a komunikat o b³êdzie na konsolê, zrzuca zawartoœæ pamiêci na dysk do póŸniejszej analizy i przerywa

dzia³anie. Natomiast system czasu rzeczywistego próbuje albo rozwi¹zaæ problem, albo zminimalizo-

waæ jego wp³yw, nie zaprzestaj¹c pracy. System zwykle powiadamia u¿ytkownika albo proces u¿yt-

kownika, ¿e niezbêdne s¹ czynnoœci naprawcze, a nastêpnie kontynuuje dzia³anie, byæ mo¿e przy

obni¿onym poziomie us³ug. Jeœli konieczne jest zamkniêcie systemu, podejmuje siê próbê zachowania

spójnoœci plików i danych.

Wa¿nym aspektem odpornoœci na uszkodzenia jest stabilnoœæ. System czasu rzeczywistego jest sta-

bilny, jeœli w razie niemo¿noœci dotrzymania terminów wszystkich zadañ realizuje w terminie te

najwa¿niejsze, o najwy¿szym priorytecie, nawet jeœli oznacza to opóŸnienie mniej krytycznych zadañ.
Aby spe³niæ powy¿sze wymagania, wspó³czesne systemy operacyjne czasu rzeczywistego zwykle maj¹

nastêpuj¹ce w³aœciwoœci [STAN89]:

w Szybkie prze³¹czanie procesów lub w¹tków
w Ma³y rozmiar (i zwi¹zana z tym minimalna funkcjonalnoœæ)
w Zdolnoœæ do szybkiego reagowania na zewnêtrzne przerwania
w Wielozadaniowoœæ z narzêdziami komunikacji miêdzyprocesowej takimi jak semafory, sy-

gna³y i zdarzenia

w U¿ycie specjalnych plików sekwencyjnych, które mog¹ szybko gromadziæ dane
w Szeregowanie z wyw³aszczaniem oparte na priorytetach
w Minimalizacja okresów, w których przerwania s¹ wy³¹czone
w Operacje elementarne, które opóŸniaj¹ zadania o sta³y czas i wstrzymuj¹ oraz wznawiaj¹

zadania

w Specjalne alarmy i limity czasu

Sercem systemu czasu rzeczywistego jest mened¿er szeregowania krótkoterminowego. Sprawiedli-

woœæ i minimalizowanie œredniego czasu reakcji nie s¹ w tym przypadku najwa¿niejsze – istotne jest

to, aby wszystkie twarde zadania czasu rzeczywistego koñczy³y siê (lub zaczyna³y) w terminie, i aby

jak najwiêcej miêkkich zadañ czasu rzeczywistego koñczy³o siê (lub zaczyna³o) w terminie.
Wiêkszoœæ wspó³czesnych systemów operacyjnych czasu rzeczywistego nie obs³uguje bezpoœrednio

terminów. Zamiast tego projektuje siê je tak, aby jak najdynamiczniej reagowa³y na zadania czasu

rzeczywistego i – kiedy zbli¿a siê termin – szybko je szeregowa³y. Z takiego punktu widzenia aplikacje

czasu rzeczywistego zwykle wymagaj¹ deterministycznych czasów reakcji w zakresie od kilku milisekund

do mniej ni¿ milisekundy w bardzo ró¿norodnych warunkach; najbardziej zaawansowane aplikacje –

np. w symulatorach samolotów wojskowych – czêsto narzucaj¹ ograniczenia czasowe w zakresie od 10

do 100 mikrosekund [ATLA89].

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

416

Rysunek 10.4 ilustruje spektrum mo¿liwoœci. W mened¿erze wyw³aszczaj¹cym, który u¿ywa prostego

szeregowania cyklicznego, zadanie czasu rzeczywistego zosta³oby dodane do kolejki procesów goto-

wych, w której oczekiwa³oby na nastêpny odcinek czasu, jak pokazano na rysunku 10.4a. W takim

przypadku czas szeregowania by³by zwykle nie do przyjêcia dla aplikacji czasu rzeczywistego. Nato-

miast w mened¿erze niewyw³aszczaj¹cym moglibyœmy u¿yæ szeregowania priorytetowego, nadaj¹c

zadaniom czasu rzeczywistego wy¿szy priorytet. W takim przypadku gotowe zadanie czasu rzeczy-

wistego by³oby szeregowane zaraz po zablokowaniu lub zakoñczeniu bie¿¹cego zadania (rysunek 10.4b).

Mog³oby to doprowadziæ do opóŸnienia rzêdu kilku sekund, gdyby w krytycznym momencie wyko-

nywa³o siê d³ugie zadanie o niskim priorytecie. Takie podejœcie jest równie¿ nie do przyjêcia. Bardziej

obiecuj¹ce wydaje siê po³¹czenie priorytetów z przerwaniami zegarowymi. Punkty wyw³aszczania

wystêpuj¹ w regularnych odstêpach czasu. Kiedy wystêpuje punkt wyw³aszczania, obecnie dzia³aj¹ce

zadanie zostaje wyw³aszczone, jeœli oczekuje zadanie o wy¿szym priorytecie. Wyw³aszczanie dotyczy

tak¿e zadañ bêd¹cych czêœci¹ systemu operacyjnego. Tego rodzaju opóŸnienie mo¿e byæ rzêdu kilku

milisekund (rysunek 10.4c). Choæ to ostatnie podejœcie sprawdza siê w niektórych aplikacjach czasu

rzeczywistego, nie wystarczy w bardziej wymagaj¹cych aplikacjach. W takich przypadkach mo¿na

pos³u¿yæ siê metod¹ nazywan¹ natychmiastowym wyw³aszczaniem: system operacyjny reaguje na

przerwanie niemal natychmiast, chyba ¿e znajduje siê w sekcji krytycznej kodu. OpóŸnienie szerego-

wania zadañ czasu rzeczywistego mo¿na wówczas zmniejszyæ do 100 mikrosekund lub mniej.

417

Szeregowanie w czasie rzeczywistym

Rysunek 10.4 Szeregowanie procesu czasu rzeczywistego.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

418

Szeregowanie w czasie rzeczywistym

Szeregowanie w czasie rzeczywistym (ang. real-time scheduling) to jedna z najaktywniejszych dzie-

dzin badañ w informatyce. W tym podrozdziale przedstawimy ró¿ne podejœcia do szeregowania w czasie

rzeczywistym i przyjrzymy siê dwóm popularnym klasom algorytmów szeregowania.

W przegl¹dzie algorytmów szeregowania w czasie rzeczywistym [RAMA94] zauwa¿ono, ¿e ró¿ne

podejœcia do szeregowania zale¿¹ od: (1) tego, czy system przeprowadza analizê szeregowalnoœci, (2)

jeœli tak, to czy robi to statycznie, czy dynamicznie, i (3) czy sam wynik analizy tworzy harmonogram

lub plan, wed³ug którego zadania s¹ przydzielane procesorowi w czasie wykonywania. W oparciu o te

zale¿noœci autorzy identyfikuj¹ poni¿sze klasy algorytmów:

w Statyczne algorytmy tabelaryczne (ang. Static table-driven scheduling): Te algorytmy przepro-

wadzaj¹ statyczn¹ analizê wykonalnych planów szeregowania. Wynikiem tej analizy jest har-

monogram, który okreœla – w czasie dzia³ania – kiedy zadanie musi zacz¹æ siê wykonywaæ.

w Statyczne algorytmy priorytetowe z wyw³aszczaniem (ang. Static priority-driven preemptive

scheduling): W tym przypadku równie¿ przeprowadza siê statyczn¹ analizê, ale bez tworzenia

harmonogramu. Na podstawie analizy przydziela siê zadaniom priorytety, dziêki czemu

mo¿na u¿yæ tradycyjnego, priorytetowego mened¿era szeregowania z wyw³aszczaniem.

w Dynamiczne algorytmy z planowaniem (ang. Dynamic planning-based schedulling): WykonalnoϾ

ustala siê w czasie dzia³ania (dynamicznie), a nie offline, przed rozpoczêciem wykonywania (sta-

tycznie). Przybywaj¹ce zadanie jest akceptowane tylko wtedy, gdy da siê dotrzymaæ terminu jego

wykonania. Jednym z rezultatów tej analizy wykonalnoœci jest harmonogram czy te¿ plan, który

okreœla, kiedy skierowaæ zadanie do wykonania.

w Dynamiczne algorytmy typu „rób, co w twojej mocy” (ang. best effort): Nie przeprowadza siê

analizy wykonalnoœci. System próbuje dotrzymaæ wszystkich terminów i przerywa ka¿dy

uruchomiony proces, którego termin zosta³ przekroczony.

Statyczne szeregowanie tabelaryczne stosuje siê do zadañ maj¹cych charakter okresowy. Dane wej-

œciowe podlegaj¹ce analizie to okres przybywania, czas wykonywania, okresowy termin koñcowy i wzglêd-

ny priorytet ka¿dego zadania. Mened¿er szeregowania próbuje opracowaæ harmonogram, który spe³ni

wymagania wszystkich zadañ okresowych. Jest to podejœcie przewidywalne, ale nieelastyczne, ponie-

wa¿ ka¿da zmiana wymagañ zadania zmusza do ponownego opracowania harmonogramu. W tej

kategorii algorytmów szeregowania zwykle u¿ywa siê metod takich jak „najpierw najwczeœniejszy

termin” albo innych technik okresowych (o których niebawem bêdzie mowa).

Statyczne szeregowanie priorytetowe z wyw³aszczaniem korzysta z priorytetowych, wyw³aszczaj¹cych

mechanizmów szeregowania u¿ywanych w zwyk³ych systemach wieloprogramowych. W systemach

nie dzia³aj¹cych w czasie rzeczywistym mo¿na ustalaæ priorytety na podstawie ró¿norodnych czyn-

ników. Na przyk³ad w systemie z podzia³em czasu priorytet procesu zmienia siê w zale¿noœci od

tego, czy proces jest powi¹zany z procesorem, czy te¿ z we-wy. W systemie czasu rzeczywistego przy-

pisany priorytet jest zwi¹zany z ramami czasowymi ka¿dego zadania. Przyk³adem takiego podejœcia

jest algorytm czêstotliwoœciowy monotoniczny (opisywany ni¿ej) (ang. rate monotonic algorithm), który

przypisuje zadaniom statyczne priorytety zale¿ne od d³ugoœci ich okresów wykonywania.

W przypadku dynamicznego szeregowania z planowaniem po przybyciu zadania, ale przed rozpoczê-

ciem jego wykonywania, podejmuje siê próbê utworzenia harmonogramu, który obejmuje poprzed-

nio zaplanowane zadania, a tak¿e to nowo przyby³e. Jeœli nowo przyby³e zadanie mo¿na wykonaæ w termi-

nie, zarazem dotrzymuj¹c terminów obecnie zaplanowanych zadañ, harmonogram modyfikuje siê

tak, aby uwzglêdniæ nowe zadanie.

Dynamiczne szeregowanie typu „rób, co w twojej mocy” to metoda u¿ywana w wielu wspó³czesnych,

komercyjnych systemach czasu rzeczywistego. Kiedy przybywa zadanie, system przypisuje mu priory-

tet zale¿ny od charakterystyki zadania. Zwykle u¿ywa siê jakiejœ odmiany szeregowania terminowego,

takiej jak „najpierw najwczeœniejszy termin”. Zadania s¹ z regu³y nieokresowe, wiêc statyczna analiza

szeregowania nie jest mo¿liwa. W przypadku takiego typu szeregowania nie wiadomo, czy uda siê

wykonaæ zadanie w terminie, dopóki nie nadejdzie termin albo zadanie nie dobiegnie koñca. Jest to

najwiêksza wada tego typu szeregowania, natomiast jego zalet¹ jest ³atwoœæ implementacji.

419

Szeregowanie w czasie rzeczywistym

Szeregowanie terminowe (ang. Deadline scheduling)

Wiêkszoœæ wspó³czesnych systemów operacyjnych czasu rzeczywistego projektuje siê z myœl¹ o jak

najszybszym uruchamianiu zadañ czasu rzeczywistego, k³ad¹c nacisk na szybk¹ obs³ugê przerwañ

i przydzielanie zadañ. W rzeczywistoœci nie jest to szczególnie przydatna miara wartoœci systemu

czasu rzeczywistego. W aplikacjach czasu rzeczywistego zwykle chodzi nie tyle o szybkoœæ, co o zakoñ-

czenie (lub rozpoczêcie) zadania w najkorzystniejszym czasie, ani za wczeœnie, ani za póŸno, pomimo

zmiennego popytu na zasoby, sprzecznych wymagañ, obci¹¿eñ zwi¹zanych z przetwarzaniem oraz b³ê-

dów sprzêtu i oprogramowania. Wynika z tego, ¿e priorytety s¹ doœæ prymitywnym narzêdziem i nie

odzwierciedlaj¹ wymogu zakoñczenia (lub rozpoczêcia) zadania w jak najkorzystniejszym czasie.
W ostatnich latach zaproponowano kilka bardziej zaawansowanych metod szeregowania czasu

rzeczywistego. Wszystkie te metody opieraj¹ siê na dodatkowych informacjach o ka¿dym zadaniu.

W najogólniejszej postaci, mo¿na skorzystaæ z nastêpuj¹cych informacji:

w Czas gotowoœci: Czas, w którym proces staje siê gotowy do wykonania. W przypadku zadania

powtarzalnego lub okresowego jest to znana z góry sekwencja czasów. W przypadku zadania

nieokresowego czas gotowoœci mo¿e byæ znany z góry, ale bywa i tak, ¿e system dowiaduje siê

o nim dopiero wtedy, kiedy zadanie jest rzeczywiœcie gotowe.

w Termin rozpoczêcia: Czas, od którego zadanie musi siê rozpocz¹æ.
w Termin zakoñczenia: Czas, w którym zadanie musi zostaæ zakoñczone. Typowe aplikacje

czasu rzeczywistego maj¹ termin rozpoczêcia albo termin zakoñczenia, ale nie oba te terminy.

w Czas przetwarzania: Czas wymagany na wykonanie zadania do koñca. W niektórych przy-

padkach podaje go u¿ytkownik, w innych system operacyjny oblicza œredni¹ wyk³adnicz¹.

Jeszcze w innych systemach szeregowania nie u¿ywa siê tej informacji.

w Wymagania co do zasobów: Zbiór zasobów (innych ni¿ procesor) potrzebnych zadaniu w czasie

wykonywania.

w Priorytet: Mierzy wzglêdn¹ wa¿noœæ zadania. Twarde zadania czasu rzeczywistego mog¹ mieæ

priorytet „bezwzglêdny”, co oznacza za³amanie systemu w razie niedotrzymania terminu.

Jeœli system ma kontynuowaæ pracê bez wzglêdu na okolicznoœci, mo¿na przypisywaæ prio-

rytety zarówno twardym, jak i miêkkim zadaniom czasu rzeczywistego – jako wskazówkê

dla mened¿era szeregowania.

w Struktura podzadania: Zadanie mo¿na podzieliæ na podzadanie obowi¹zkowe i podzadanie

opcjonalne. Tylko zadanie obowi¹zkowe ma nieprzekraczalny termin.

Gdy weŸmie siê pod uwagê terminy, funkcja szeregowania czasu rzeczywistego ma kilka wymiarów:

które zadanie przydzieliæ jako nastêpne i jakiego rodzaju wyw³aszczanie jest dozwolone. Dla danej

strategii wyw³aszczania i przy wykorzystaniu terminów rozpoczêcia albo zakoñczenia mo¿na wykazaæ,

¿e szeregowanie zadañ o najwczeœniejszym terminie minimalizuje odsetek zadañ, które nie zostan¹ wykona-

ne w terminie [BUTT99, HONG89, PANW88]. Dotyczy to zarówno konfiguracji jednoprocesorowych,

jak i wieloprocesorowych.

Tabela 10.2 Profil wykonywania dwóch zadañ okresowych.

Proces

Czas

Czas

Termin

przybycia

wykonywania

zakoñczenia

A (1)

0

10

20

A (2)

20

10

40

A (3)

40

10

60

A (4)

60

10

80

A (5)

80

10

100

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

420

Inna kluczowa kwestia projektowa to wyw³aszczanie (ang. preemption). Jeœli podaje siê terminy rozpo-

czêcia, wówczas niewyw³aszczaj¹cy mened¿er szeregowania ma sens. W takim przypadku to zadanie

czasu rzeczywistego jest odpowiedzialne za zablokowanie siê po wykonaniu swej obowi¹zkowej lub

krytycznej czêœci, umo¿liwiaj¹c dotrzymanie pozosta³ych terminów rozpoczêcia. Pasuje to do wzoru

z rysunku 10.4b. W systemie z terminami zakoñczenia najodpowiedniejsza jest strategia z wyw³aszczaniem

(rysunek 10.4c lub d). Jeœli np. zadanie X dzia³a, a zadanie Y jest gotowe, mog¹ zaistnieæ okolicznoœci,

w których jedyn¹ mo¿liwoœci¹ terminowego dokoñczenia obu zadañ bêdzie wyw³aszczenie zadania

X, wykonanie zadania Y do koñca, a nastêpnie wznowienie i dokoñczenie zadania X.
Jako przyk³ad szeregowania zadañ okresowych z terminami zakoñczenia rozwa¿my system, który

gromadzi i przetwarza dane z dwóch czujników, A i B. Termin gromadzenia danych z czujnika A

musi byæ dotrzymany co 20 ms, a z czujnika B – co 60 ms. Przetworzenie danych z czujnika A, ³¹cznie

z dodatkowymi kosztami pracy systemu operacyjnego, zajmuje 10 ms, a przetworzenie danych z czuj-

nika B – 25 ms. Tabela 10.2 podsumowuje profil wykonywania obu zadañ.
Komputer mo¿e podejmowaæ decyzje o szeregowaniu co 10 ms. Przypuœæmy, ¿e w takich okolicznoœciach

spróbowaliœmy u¿yæ priorytetowej metody szeregowania. Wyniki s¹ pokazane na dwóch pierwszych

diagramach na rysunku 10.5. Jeœli proces A ma wy¿szy priorytet, pierwsza instancja procesu B otrzy-

muje tylko 20 ms czasu przetwarzania, w dwóch odcinkach o d³ugoœci 10 ms, zanim up³ynie jego

termin, a wiêc zawodzi. Jeœli proces B ma wy¿szy priorytet, to proces A nie dotrzyma pierwszego

terminu. Ostatni diagram pokazuje u¿ycie szeregowania z najwczeœniejszym terminem. W czasie

t = 0 przybywaj¹ procesy A1 i B1. Poniewa¿ A1 ma najwczeœniejszy termin, jest kierowany do wykonania

jako pierwszy. Kiedy A1 koñczy dzia³anie, procesor przypada procesowi B1. W czasie t = 20 przybywa

proces A2. Poniewa¿ A2 ma wczeœniejszy termin ni¿ B1, B1 jest przerywany, aby A2 móg³ wykonaæ siê

do koñca. Nastêpnie B1 jest wznawiany w czasie t = 30. W czasie t = 40 przybywa proces A3. Jednak¿e

B1 ma wczeœniejszy termin zakoñczenia, wiêc jest wykonywany nadal i koñczy siê w czasie t = 45.

Nastêpnie proces A3 przejmuje procesor i koñczy siê w czasie t = 55.

W tym przyk³adzie, dziêki faworyzowaniu w ka¿dym punkcie wyw³aszczania zadañ o najwczeœniej-

szym terminie, uda³o siê spe³niæ wszystkie wymagania systemowe. Poniewa¿ zadania s¹ okresowe i

przewidywalne, pos³u¿ono siê statycznym szeregowaniem tabelarycznym.

.

.

.

.

.

.

.

.

.

.

.

.

B (1)

0

25

50

B (2)

50

25

100

.

.

.

.

.

.

.

.

.

.

.

.

421

Szeregowanie w czasie rzeczywistym

Rysunek 10.5 Statyczne szeregowanie tabelaryczne.

Teraz rozwa¿my metodê obs³ugi zadañ nieokresowych z terminami rozpoczêcia. Górna czêœæ rysunku

10.6 pokazuje czasy przybycia i terminy rozpoczêcia w przyk³adzie sk³adaj¹cym siê z piêciu zadañ, z któ-

rych ka¿de ma czas przetwarzania równy 20 ms. Tabela 10.5 przedstawia profil wykonywania tych piêciu

zadañ.

Najproœciej jest zawsze kierowaæ do wykonania gotowe zadanie o najwczeœniejszym terminie i po-

zwalaæ mu dzia³aæ a¿ do koñca. Jeœli u¿yjemy takiej metody w przyk³adzie z rysunku 10.6, to zadanie

B nie zostanie skierowane do wykonania, mimo ¿e wymaga natychmiastowej obs³ugi. Jest to ryzyko

nierozerwalnie zwi¹zane z obs³ug¹ zadañ czasu rzeczywistego, zw³aszcza w przypadku terminów roz-

poczêcia. Jeœli termin jest znany z góry, zanim zadanie bêdzie gotowe, mo¿na zastosowaæ ulepszon¹

strategiê, która zwiêksza wydajnoœæ. Strategia ta, okreœlana mianem „najwczeœniejszy termin z niewymu-

szonymi okresami bezczynnoœci”, dzia³a nastêpuj¹co: zawsze kieruje siê do wykonania zadanie o najwcze-

œniejszym terminie i pozwala mu dzia³aæ a¿ do koñca. Zadanie to mo¿e nie byæ gotowe, przez co

procesor czasem pozostaje bezczynny, choæ w systemie s¹ gotowe zadania. Zauwa¿my, ¿e w naszym

przyk³adzie procesor powstrzymuje siê od wykonywania zadania A, mimo ¿e jest to jedyne gotowe

zadanie. W rezultacie, choæ procesor nie jest wykorzystany do maksimum, wszystkie wymagania zo-

staj¹ spe³nione. Wreszcie, dla porównania, przedstawiono strategiê „kto pierwszy, ten lepszy”. W tym

przypadku nie udaje siê dotrzymaæ terminu zadañ B i E.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

422

Rysunek 10.6 Szeregowanie nieokresowych zadañ czasu rzeczywistego z terminami rozpoczêcia.

Tabela 10.3 Profil wykonywania piêciu zadañ nieokresowych.

Szeregowanie czêstotliwoœciowe monotoniczne

Jedn¹ z najbardziej obiecuj¹cych metod rozwi¹zywania konfliktów wielozadaniowego szeregowania

zadañ okresowych jest szeregowanie czêstotliwoœciowe monotoniczne (ang. rate monotonic scheduling,

RMS). Metoda ta zosta³a zaproponowana po raz pierwszy w [LIU73], ale dopiero niedawno zyska³a

na popularnoœci [BRIA99, SHA94]. RMS przypisuje zadaniom priorytety zale¿ne od ich okresów.
Rysunek 10.7 ilustruje stosowne parametry zadañ okresowych. Okres zadania, T, to iloœæ czasu od

przybycia jednej instancji zadania do przybycia nastêpnej instancji. Czêstotliwoœæ zadania (w her-

cach) to po prostu odwrotnoœæ okresu (w sekundach). Na przyk³ad zadanie z okresem 50 ms wystê-

puje z czêstotliwoœci¹ 20 Hz. Zwykle koniec okresu zadania jest zarazem nieprzekraczalnym termi-

nem jego zakoñczenia, choæ niektóre zadania mog¹ mieæ wczeœniejsze terminy. Czas wykonywania

(albo obliczania), C, to iloœæ czasu potrzebna na przetworzenie ka¿dego wyst¹pienia zadania. Jest

oczywiste, ¿e w systemie jednoprocesorowym czas wykonywania nie mo¿e byæ d³u¿szy ni¿ okres

Proces

Czas

Czas

Termin

przybycia

wykonywania

rozpoczêcia

A

10

20

110

B

20

20

20

C

40

20

50

D

50

20

90

E

60

20

70

423

Szeregowanie w czasie rzeczywistym

(musi zachodziæ nierównoœæ C = T). Jeœli zadanie okresowe jest zawsze wykonywane do koñca, to

znaczy ¿adnemu wyst¹pieniu zadania nie trzeba odmawiaæ obs³ugi ze wzglêdu na niedostateczne

zasoby, wówczas wykorzystanie procesora przez to zadanie wynosi U = C/T. Jeœli np. zadanie ma

okres równy 80 ms i czas wykonywania równy 55 ms, to jego wykorzystanie procesora wynosi

55/80 = 0,6875.

Rysunek 10.7 Diagram czasowy zadania okresowego.

W szeregowaniu RMS zadaniem o najwy¿szym priorytecie jest to o najkrótszym okresie, drugie pod

wzglêdem priorytetu jest zadanie drugie pod wzglêdem „krótkoœci” okresu itd. Jeœli jest wiêcej ni¿

jedno zadanie do wykonania, najpierw obs³uguje siê to o najkrótszym okresie. Jeœli sporz¹dzimy

wykres priorytetu zadañ jako funkcji ich czêstotliwoœci, otrzymamy funkcjê rosn¹c¹ monotonicznie

(rysunek 10.8); st¹d nazwa – szeregowanie czêstotliwoœciowe monotoniczne.
Jedn¹ z miar efektywnoœci algorytmu szeregowania okresowego jest to, czy gwarantuje on dotrzymanie

wszystkich twardych terminów. Przypuœæmy, ¿e mamy n zadañ, ka¿de o sta³ym okresie i czasie wyko-

nywania. Aby by³o mo¿liwe dotrzymanie wszystkich terminów, musi zachodziæ nastêpuj¹ca nie-

równoœæ:









+

+

7

&

7

&

Ê

+

Q

Q

7

&

(10.1)

Suma stopni wykorzystania procesora przez poszczególne zadania nie mo¿e przekroczyæ wartoœci 1,

która odpowiada pe³nemu wykorzystaniu procesora. Równanie (10.1) okreœla górn¹ granicê liczby

zadañ, które mog¹ zostaæ uszeregowane przez idealny algorytm szeregowania. W konkretnych algo-

rytmach szeregowania ta granica mo¿e byæ ni¿sza. Mo¿na wykazaæ, ¿e w przypadku RMS obowi¹zuje

nastêpuj¹ca nierównoœæ:









+

+

7

&

7

&





-

Ê

+

Q

Q

Q

Q

7

&

(10.2)

Tabela 10.4 podaje kilka wartoœci tej górnej granicy. W miarê wzrostu liczby zadañ granica szerego-

walnoœci d¹¿y do ln 2 Z 0,693.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

424

Rysunek 10.8 Zbiór zadañ z RMS.

Dla przyk³adu rozwa¿my przypadek trzech zadañ okresowych, gdzie U

i

 = C

i

/T

i

:

w Zadanie P

1

: C

1

= 20; T

1

= 100; U

1

= 0,2

w Zadanie P

2

: C

2

= 40; T

2

= 150; U

2

= 0,267

w Zadanie P

3

: C

3

= 100; T

3

= 350; U

3

= 0,286

Ca³kowite wykorzystanie procesora przez te trzy zadania to 0,2 + 0,267 + 0,268 = 0,753. Górna granica

szeregowalnoœci tych zadañ z wykorzystaniem RMS to:



















=

-

Ê

+

+

7

&

7

&

7

&

Poniewa¿ ca³kowite wykorzystanie procesora przez trzy zadania jest mniejsze ni¿ górna granica RMS

(0,753 < 0,779), wiemy, ¿e w razie u¿ycia RMS wszystkie zadania zostan¹ pomyœlnie uszeregowane.

Mo¿na tak¿e wykazaæ, ¿e górna granica z równania (10.1) obowi¹zuje w przypadku szeregowania

wed³ug najkrótszych okresów. Zatem szeregowanie wed³ug najkrótszych okresów pozwala osi¹gn¹æ

wiêkszy stopieñ wykorzystania procesora i wykonaæ wiêcej zadañ periodycznych. Mimo to szerego-

wania RMS u¿ywa siê powszechnie w aplikacjach przemys³owych. [SHA91] wyjaœnia to nastêpuj¹co:

1. Ró¿nica wydajnoœci w praktyce jest niewielka. Górna granica z równania (10.2) jest konser-

watywna, a w praktyce osi¹ga siê czêsto nawet 90-procentowy stopieñ wykorzystania.

2. Wiêkszoœæ systemów czasu rzeczywistego ma tak¿e miêkkie komponenty czasu rzeczywistego,

s³u¿¹ce np. do prezentacji niekrytycznych danych albo autotestowania, które mog¹ siê wyko-

nywaæ na ni¿szych poziomach priorytetu, aby zaabsorbowaæ czas procesora niewykorzystany

przez szeregowanie RMS twardych zadañ czasu rzeczywistego (ang. hard real-time tasks).

3. RMS zapewnia lepsz¹ stabilnoœæ. Kiedy system nie mo¿e dotrzymaæ wszystkich terminów

ze wzglêdu na przeci¹¿enie lub przejœciowe b³êdy, trzeba zagwarantowaæ dotrzymanie terminów

najwa¿niejszych zadañ, pod warunkiem, ¿e ten zbiór zadañ jest szeregowalny. W podejœciu

ze statycznym przypisywaniem priorytetów wystarczy zapewniæ, ¿e najwa¿niejsze zadania

maj¹ wzglêdnie wysokie priorytety. Da siê to zrobiæ w RMS, projektuj¹c najwa¿niejsze zadania

tak, aby mia³y krótkie okresy, albo modyfikuj¹c priorytety RMS pod k¹tem najwa¿niejszych

zadañ. W przypadku szeregowania wed³ug najkrótszych terminów priorytet zadania zmienia

siê w kolejnych okresach. Z tego powodu trudniej zagwarantowaæ, ¿e najwa¿niejsze zadania

zostan¹ wykonane w terminie.

425

Szeregowanie w Linuksie

Tabela 10.4 Wartoœæ górnej granicy RMS.

n

n(2

1/n

– 1)

1

1,0

2

0,828

3

0,779

4

0,756

5

0,743

6

0,734

.

.

.

.

.

.

'

ln 2 Z 0,693

10.3 Szeregowanie w Linuksie

Linux rozszerza tradycyjne szeregowanie uniksowe opisane w podrozdziale 9.3 o dwie klasy szeregowania

przeznaczone do miêkkiego przetwarzania w czasie rzeczywistym. Trzy klasy szeregowania w Linuksie to:

w SCHED_FIFO: W¹tki czasu rzeczywistego, pierwszy na wejœciu – pierwszy na wyjœciu
w SCHED_RR: W¹tki czasu rzeczywistego, szeregowanie cykliczne
w SCHED_OTHER: Inne w¹tki, nie wykonywane w czasie rzeczywistym

W ka¿dej klasie mo¿na u¿ywaæ wielu priorytetów, przy czym priorytety w klasach czasu rzeczywistego

s¹ wy¿sze ni¿ w klasie SCHED_OTHER. W przypadku w¹tków FIFO obowi¹zuj¹ nastêpuj¹ce regu³y:

1. System nie przerywa wykonuj¹cego siê w¹tku FIFO, z wyj¹tkiem poni¿szych przypadków:

a. Inny w¹tek FIFO o wy¿szym priorytecie staje siê gotowy.
b. Wykonuj¹cy siê w¹tek FIFO blokuje siê w oczekiwaniu na zdarzenie, np we-wy.
c. Wykonuj¹cy siê w¹tek FIFO dobrowolnie odstêpuje procesor po wywo³aniu funkcji pier-

wotnej sched_yield.

2. Kiedy wykonuj¹cy siê w¹tek FIFO zostanie przerwany, jest umieszczany w kolejce zwi¹zanej

ze swoim priorytetem.

3. Kiedy w¹tek FIFO staje siê gotowy i ma wy¿szy priorytet ni¿ obecnie wykonuj¹cy siê w¹tek,

wówczas wykonuj¹cy siê w¹tek zostaje wyw³aszczony i wykonuje siê gotowy w¹tek FIFO o naj-

wy¿szym priorytecie. Jeœli wiêcej ni¿ jeden w¹tek ma ten najwy¿szy priorytet, wybiera siê

w¹tek, który czeka³ najd³u¿ej.

Strategia SCHED_RR przypomina strategiê FIFO, ale z ka¿dym w¹tkiem zwi¹zany jest limit czasu.

Kiedy w¹tek SCHED_RR wyczerpie swój limit czasu wykonywania, wstrzymuje siê go i wybiera

w¹tek czasu rzeczywistego o równym lub wy¿szym priorytecie.
Rysunek 10.9, zaczerpniêty z [COMP98], ilustruje ró¿nicê miêdzy szeregowaniem FIFO a RR.

Przypuœæmy, ¿e program ma cztery w¹tki z trzema wzglêdnymi priorytetami przypisanymi jak na rysunku

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

426

10.9a. Za³ó¿my, ¿e wszystkie oczekuj¹ce w¹tki s¹ gotowe do wykonania, kiedy bie¿¹cy w¹tek siê koñ-

czy, i ¿e ¿aden w¹tek o wy¿szym priorytecie nie uaktywnia siê podczas wykonywania w¹tku. Rysunek

10.9b pokazuje przep³yw, w którym wszystkie w¹tki nale¿¹ do klasy SCHED_FIFO. W¹tek D wykonuje

siê, a¿ przejdzie w stan oczekiwania albo dobiegnie koñca. Nastêpnie, choæ w¹tki B i C maj¹ ten sam

priorytet, uruchamia siê w¹tek B, poniewa¿ czeka³ d³u¿ej ni¿ w¹tek C. W¹tek B wykonuje siê, a¿ przej-

dzie w stan oczekiwania albo dobiegnie koñca; nastêpnie w¹tek C wykonuje siê, a¿ przejdzie w stan

oczekiwania albo dobiegnie koñca. Wreszcie wykonuje siê w¹tek A.

Rysunek 10.9 pokazuje przyk³adowy przep³yw, w którym wszystkie procesy nale¿¹ do klasy SCHED_RR.

W¹tek D wykonuje siê, a¿ przejdzie w stan oczekiwania albo dobiegnie koñca. Nastêpnie w¹tki B i C

wykonuj¹ siê przemiennie, poniewa¿ maj¹ ten sam priorytet. Wreszcie wykonuje siê w¹tek A.

Rysunek 10.9 Przyk³ad szeregowania w Linuksie.

Ostatnia klasa szeregowania to SCHED_OTHER. W¹tek tej klasy mo¿e siê wykonywaæ tylko wtedy,

gdy nie ma do wykonania ¿adnych zadañ czasu rzeczywistego. W klasie SCHED_OTHER u¿ywa siê

tradycyjnego uniksowego algorytmu szeregowania opisanego w podrozdziale 9.3.

10.4 Szeregowanie w systemie Unix SVR4

Algorytm szeregowania u¿ywany w systemie UNIX SVR4 to gruntownie zmodyfikowana wersja algo-

rytmu szeregowania u¿ywanego w starszych systemach uniksowych (opisanego w podrozdziale 9.3).

Nowy algorytm daje najwy¿szy port procesom czasu rzeczywistego, œredni priorytet – procesom dzia³a-

j¹cym w trybie j¹dra, a najni¿szy priorytet – procesom dzia³aj¹cym w trybie u¿ytkownika, nazywanym

procesami z podzia³em czasu.

Dwie najwa¿niejsze modyfikacje zaimplementowane w SVR4 to:

1. Dodanie wyw³aszczaj¹cego mened¿era szeregowania ze statycznymi priorytetami i wprowa-

dzenie zbioru 160 poziomów priorytetu podzielonych na trzy klasy priorytetu.

2. Wstawianie punktów wyw³aszczania (ang. preemptive points). Poniewa¿ podstawowe j¹dro jest

niewyw³aszczalne, jedyne, co mo¿na zrobiæ, to podzieliæ je na etapy przetwarzania, które

musz¹ zostaæ dokoñczone bez przerywania. Pomiêdzy etapami przetwarzania zidentyfiko-

wano bezpieczne miejsca, zwane punktami wyw³aszczania, w których j¹dro mo¿e przerwaæ

przetwarzanie i uszeregowaæ nowy proces. Bezpieczne miejsce definiuje siê jak obszar kodu,

w którym wszystkie struktury danych j¹dra s¹ albo zaktualizowane i spójne, albo zablokowane

przez semafor.

Rysunek 10.10 ilustruje 160 poziomów priorytetu zdefiniowanych w SVR4. Ka¿dy proces nale¿y

do jednej z trzech klas priorytetu i otrzymuje pewien poziom priorytetu w tej klasie. Oto

dostêpne klasy:

w Czas rzeczywisty (159-100): Procesy o takich priorytetach s¹ zawsze wybierane przed proce-

sami j¹dra albo procesami z podzia³em czasu. Ponadto procesy czasu rzeczywistego mog¹

u¿ywaæ punktów wyw³aszczania, aby wyw³aszczaæ procesy j¹dra i procesy u¿ytkownika.

427

Szeregowanie w systemie Unix SVR4

w J¹dro (99-60): Procesy o takich priorytetach s¹ zawsze wybierane przed procesami z podzia³em

czasu, ale musz¹ ustêpowaæ pierwszeñstwa procesom czasu rzeczywistego.

w Podzia³ czasu (59-0): Procesy o najni¿szym priorytecie, przeznaczone dla procesów u¿yt-

kownika innych ni¿ procesy czasu rzeczywistego.

Rysunek 10.11 przedstawia implementacjê szeregowania w SVR4. Z ka¿dym poziomem priorytetu

zwi¹zana jest kolejka dyspozycyjna (ang. dispatch queue), a procesy o danym priorytecie s¹ wykonywane

cyklicznie. Bitmapowy wektor, dqactmap, zawiera jeden bit na ka¿dy poziom priorytetu; bit ten jest

ustawiany na 1 dla ka¿dego poziomu priorytetu, którego kolejka nie jest pusta. Kiedy dzia³aj¹cy proces

opuszcza stan dzia³ania – ze wzglêdu na blokadê, up³yw limitu czasu albo wyw³aszczenie – dyspozytor

sprawdza wektor dqactmap i kieruje do wykonania gotowy proces z niepustej kolejki o najwy¿szym

priorytecie. Ponadto, po dotarciu do jednego ze zdefiniowanych punktów wyw³aszczania, j¹dro sprawdza

znacznik o nazwie kprunrun. Jeœli znacznik jest ustawiony, oznacza to, ¿e przynajmniej jeden proces

czasu rzeczywistego znajduje siê w stanie gotowoœci, i j¹dro wyw³aszcza bie¿¹cy proces, jeœli ma on

ni¿szy priorytet ni¿ gotowy proces czasu rzeczywistego o najwy¿szym priorytecie.

Rysunek 10.10 Klasy priorytetu w systemie SVR4.

Rysunek 10.11 Kolejki dyspozycyjne w systemie SVR4.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

428

W klasie z podzia³em czasu priorytet procesu jest zmienny. Mened¿er szeregowania zmniejsza prio-

rytet procesu, kiedy ten zu¿ywa kwant czasu, i zwiêksza jego priorytet, kiedy proces blokuje siê w ocze-

kiwaniu na zdarzenie lub zasób. Kwant czasu przydzielany procesowi z podzia³em czasu zale¿y od

priorytetu procesu i wynosi od 100 ms w przypadku priorytetu 0 do 10 ms w przypadku priorytetu

59. Ka¿dy proces czasu rzeczywistego ma sta³y priorytet i sta³y kwant czasu.

10.5 Szeregowanie w Windows 2000

System Windows 2000 (W2K) zaprojektowano tak, aby jak najlepiej reagowa³ na potrzeby u¿yt-

kownika w wysoce interaktywnym œrodowisku albo w roli serwera. W W2K zastosowano szeregowanie

z wyw³aszczaniem i elastycznym systemem poziomów priorytetu. Na ka¿dym poziomie u¿ywa siê

szeregowania cyklicznego, a na niektórych poziomach dynamicznie zmienia siê priorytety w zale¿-

noœci od bie¿¹cej aktywnoœci w¹tku.

Priorytety procesów i w¹tków

Priorytety w W2K dziel¹ siê na dwa pasma, czy te¿ klasy: pasmo czasu rzeczywistego i pasmo zmiennych

priorytetów. Ka¿de z tych pasm sk³ada siê z 16 poziomów priorytetu. W¹tki wymagaj¹ce natychmia-

stowej obs³ugi znajduj¹ siê w klasie czasu rzeczywistego, która obejmuje funkcje takie jak zadania

komunikacyjne i zadania czasu rzeczywistego.
Ogólnie rzecz bior¹c, poniewa¿ W2K u¿ywa priorytetowego, wyw³aszczaj¹cego mened¿era szeregowa-

nia, w¹tki z priorytetami czasu rzeczywistego maj¹ pierwszeñstwo przed innymi w¹tkami. W systemie

jednoprocesorowym, kiedy gotowy staje siê w¹tek, którego priorytet jest wy¿szy ni¿ obecnie wyko-

nuj¹cego siê w¹tku, w¹tek o ni¿szym priorytecie zostaje wyw³aszczony i procesor przydziela siê w¹tkowi

o wy¿szym priorytecie.
Priorytety s¹ obs³ugiwane nieco inaczej w ka¿dej klasie (patrz rysunek 10.12). W klasie czasu rzeczywiste-

go wszystkie w¹tki maj¹ sta³y priorytet, który nigdy siê nie zmienia. Wszystkie aktywne w¹tki o danym

priorytecie znajduj¹ siê w cyklicznej kolejce. W klasie zmiennych priorytetów priorytet w¹tku zaczyna

siê od pewnej wstêpnie przypisanej wartoœci, a póŸniej mo¿e wzrastaæ lub maleæ w czasie ¿ycia w¹tku. Na

ka¿dym poziomie priorytetu jest wiêc kolejka FIFO, ale proces mo¿e przejœæ do innej kolejki w klasie

zmiennych priorytetów. Jednak¿e w¹tek o priorytecie 15 nie mo¿e zostaæ promowany do poziomu

16 ani ¿adnego innego poziomu w klasie czasu rzeczywistego.

429

Szeregowanie w Windows 2000

Rysunek 10.12 Priorytety w¹tków w Windows NT.

Pocz¹tkowy priorytet w¹tku w klasie zmiennych priorytetów zale¿y od dwóch wielkoœci: bazowego

priorytetu procesu i bazowego priorytetu w¹tku. Jednym z atrybutów obiektu procesu jest bazowy

priorytet procesu, który mo¿e przybieraæ wartoœci od 0 do 15. Ka¿dy obiekt w¹tku zwi¹zany z obiektem

procesu ma atrybut bazowego priorytetu w¹tku, który okreœla priorytet w¹tku wzglêdem priorytetu proce-

su. Bazowy priorytet w¹tku mo¿e byæ równy priorytetowi procesu albo ró¿niæ siê od niego o dwa poziomy

w górê lub w dó³. Jeœli wiêc proces ma bazowy priorytet 4, a jeden z jego w¹tków – bazowy priorytet –1, to

pocz¹tkowy priorytet tego w¹tku wynosi 3.
Po uaktywnieniu w¹tku w klasie zmiennych priorytetów jego rzeczywisty priorytet, nazywany dyna-

micznym priorytetem w¹tku, mo¿e oscylowaæ w podanych granicach. Priorytet dynamiczny w¹tku

nigdy nie mo¿e spaœæ poni¿ej dolnego zakresu bazowego priorytetu i nigdy nie mo¿e przekroczyæ

15. Rysunek 10.13 przedstawia przyk³ad. Obiekt procesu ma atrybut priorytetu bazowego równy 4.

Ka¿dyt obiekt w¹tku zwi¹zany z tym obiektem procesu musi mieæ pocz¹tkowy priorytet w zakresie

od 2 do 6. Dynamiczny priorytet ka¿dego w¹tku mo¿e oscylowaæ w zakresie od 2 do 15. Jeœli w¹tek

zostanie przerwany po wyczerpaniu bie¿¹cego kwantu czasu, mechanizm wykonawczy W2K obni¿a

jego priorytet. Jeœli w¹tek zostanie przerwany w oczekiwaniu na zdarzenie we-wy, mechanizm wyko-

nawczy W2K podwy¿sza jego priorytet. Zatem procesy powi¹zane z procesorem d¹¿¹ do ni¿szych

priorytetów, a procesy powi¹zane z we-wy – do wy¿szych. W przypadku w¹tków powi¹zanych z we-wy

mechanizm wykonawczy bardziej podnosi priorytet podczas operacji interaktywnych (np. oczeki-

wania na klawiaturê lub ekran) ni¿ podczas innych operacji we-wy (np. dostêpu do dysku). Zatem

w¹tki interaktywne zwykle maj¹ najwy¿szy priorytet w klasie zmiennych priorytetów.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

430

Rysunek 10.13 Przyk³ad zale¿noœci miêdzy priorytetami w Windows NT.

Szeregowanie wieloprocesorowe (ang. Multiprocessor scheduling)

Kiedy W2K wykonuje siê na jednym procesorze, w¹tek o najwy¿szym priorytecie jest zawsze aktywny,

chyba ¿e czeka na zdarzenie. Jeœli jest wiêcej ni¿ jeden w¹tek o najwy¿szym priorytecie, procesor jest

wspó³dzielony, metod¹ cykliczn¹, przez wszystkie w¹tki o tym priorytecie. W systemie wieloproce-

sorowym z N procesorami, zawsze aktywnych jest (N – 1) w¹tków o najwy¿szym priorytecie, dzia³aj¹c

wy³¹cznie na (N – 1) dodatkowych procesorach. Pozosta³e w¹tki, te o ni¿szym priorytecie, wspó³dziel¹

jeden pozosta³y procesor. Jeœli w systemie s¹ np. trzy procesory, dwa w¹tki o najwy¿szym priorytecie

dzia³aj¹ na dwóch procesorach, a wszystkie inne w¹tki dzia³aj¹ na pozosta³ym procesorze.

Na powy¿szy re¿im szeregowania ma wp³yw przypisany w¹tkowi atrybut powinowactwa z proceso-

rami. Jeœli w¹tek jest gotowy do wykonywania, ale dostêpne procesory nie znajduj¹ siê w jego zbiorze

powinowactwa (ang. affinity set), w¹tek jest zmuszony czekaæ, a mechanizm wykonawczy wybiera kolejny

dostêpny w¹tek.

10.6 Podsumowanie, kluczowe terminy i pytania kontrolne

W œciœle sprzê¿onym systemie wieloprocesorowym procesory maj¹ dostêp do tej samej pamiêci g³ównej.

Taka konfiguracja komplikuje strukturê szeregowania. Na przyk³ad dany proces mo¿e byæ przypisany

na sta³e do jednego procesora albo kierowany do innego procesora za ka¿dym razem, kiedy wchodzi

w stan gotowoœci. Badania nad wydajnoœci¹ sugeruj¹, ¿e ró¿nice miêdzy ró¿nymi algorytmami szere-

gowania maj¹ mniejsze znaczenie w systemie wieloprocesorowym.
Termin „czas rzeczywisty” charakteryzuje proces lub zadanie, które jest wykonywane w po³¹czeniu

z pewnym procesem, funkcj¹ lub zbiorem zdarzeñ istniej¹cym na zewn¹trz systemu komputerowego,

i które musi dotrzymywaæ jednego lub wielu terminów, aby efektywnie i prawid³owo wspó³dzia³aæ ze œro-

dowiskiem zewnêtrznym. System operacyjny czasu rzeczywistego to taki, który potrafi zarz¹dzaæ proce-

sami czasu rzeczywistego. W takim kontekœcie tradycyjne kryteria dotycz¹ce algorytmów szeregowania

431

Zalecane lektury

nie maj¹ zastosowania. Kluczowym czynnikiem jest dotrzymywanie terminów, wiêc odpowiednie

s¹ algorytmy, które intensywnie korzystaj¹ z wyw³aszczania i potrafi¹ reagowaæ na wzglêdne terminy.

Kluczowe terminy

Czêœciowa odpornoœæ na uszkodzenia (ang. Fail-soft operation)
Deterministyczny system operacyjny (ang. Deterministic operating system)
Miêkkie zadanie czasu rzeczywistego (ang. Soft real-time task)

ReaktywnoϾ (ang. Responsiveness)
System operacyjny czasu rzeczywistego (ang. Real-time operating system)
Szeregowanie czêstotliwoœciowe monotoniczne (ang. Rate monotonic scheduling)

Szeregowanie terminowe (ang. Deadline scheduling)
Szeregowanie w czasie rzeczywistym (ang. Real-time scheduling)
Szeregowanie w¹tków (ang. Thread scheduling)

Szeregowanie zespo³owe (ang. Gang scheduling)
Twarde zadanie czasu rzeczywistego (ang. Hard real-time task)
Wspó³dzielenie obci¹¿enia (ang. Load sharing)

Zadanie nieokresowe (ang. Aperiodic task)
Zadanie periodyczne (ang. Periodic task)
ZiarnistoϾ (ang. Granulatrity)

Pytania kontrolne

10.1 Wymieñ i krótko zdefiniuj piêæ ró¿nych kategorii ziarnistoœci synchronizacji.
10.2 Wymieñ i krótko zdefiniuj cztery techniki szeregowania w¹tków.
10.3 Wymieñ i krótko zdefiniuj trzy odmiany wspó³dzielenia obci¹¿enia.
10.4 Jaka jest ró¿nica miêdzy twardymi a miêkkimi zadaniami czasu rzeczywistego?
10.5 Jaka jest ró¿nica miêdzy okresowymi a nieokresowymi zadaniami czasu rzeczywistego?
10.6 Wymieñ i krótko zdefiniuj piêæ ogólnych kategorii wymagañ stawianych systemom opera-

cyjnym czasu rzeczywistego.

10.7 Wymieñ i krótko zdefiniuj cztery klasy algorytmów szeregowania w czasie rzeczywistym.
10.8 Jakie informacje o zadaniu mog¹ byæ przydatne podczas szeregowania w czasie rzeczywi-

stym?

10.7 Zalecane lektury

[WEND89] to interesuj¹ce omówienie metod szeregowania wieloprocesorowego. Poni¿szy zbiór

pozycji zawiera wa¿ne artyku³y na temat szeregowania i systemów operacyjnych czasu rzeczywiste-

go: [KRIS94], [STAN93], [LEE93] i [TILB91]. [ZEAD97] analizuje wydajnoϾ szeregowania w czasie

rzeczywistym w systemie SVR4.
KRIS94 Krishna, C., i Lee, Y., ed. „Special Issue on Real-Time Systems”. Proceedings of the IEEE, styczeñ 1994.

LEE93 Lee, Y. i Krishna, C., ed. Readings in Real-Time Systems. Los Alamitos, CA: IEEE Computer

Society Press, 1993.

Rozdzia³ 10: Szeregowanie wieloprocesorowe i w czasie rzeczywistym

432

STAN93 Stankovic, J. I Ramamritham, K., eds. Advances in Real-Time Systems. Los Alamitos, CA: IEEE

Computer Society Press, 1993.
TILB91 Tilborg, A. i Koob, G., eds. Foundations of Real-Time Computing: Scheduling and Resource Manage-

ment. Boston: Kluwer Academic Publishers, 1991.
WEND89 Wendorf, J., Wendorf, R. i Tokuda, H. „Scheduling Operating System Processing on Small-

Scale Microprocessors”. Proceedings, 22nd Annual Hawaii International Conference on System Science, styczeñ

1989.
ZEAD97 Zeadally, S. „An Evaluation of the Real-Time Performance of SVR4.0 and SVR4.2”. Opera-

ting Systems Review, styczeñ 1997.

10.8 Zadania

10.1 Rozwa¿ zbiór trzech zadañ okresowych z profilem wykonywania przedstawionym w tabeli

10.5. Opracuj dla tego zbioru zadañ diagramy szeregowania podobne do tych z rysunku 10.5.

Tabela 10.5 Profil wykonywania dla zadania 10.1.

10.2 Rozwa¿ zbiór piêciu zadañ nieokresowych z profilem wykonywania przedstawionym w tabeli

10.6. Opracuj dla tego zbioru zadañ diagramy szeregowania podobne do tych z rysunku 10.6.

Tabela 10.6 Profil wykonywania dla zadania 10.2.

Proces

Czas

Czas

Termin

przybycia

wykonywania

zakoñczenia

A(1)

0

10

20

A(2)

20

10

40

.

.

.

.

.

.

.

.

.

.

.

.

B(1)

0

10

50

B(2)

50

10

100

.

.

.

.

.

.

.

.

.

.

.

.

C(1)

0

15

50

C(2)

50

15

100

.

.

.

.

.

.

.

.

.

.

.

.

Proces

Czas

Czas

Termin

przybycia

wykonywania

rozpoczêcia

A

10

20

100

B

20

20

30

C

40

20

60

D

50

20

80

E

60

20

70

433

Zadania

10.3 To zadanie pokazuje, ¿e choæ w szeregowaniu czêstotliwoœciowym monotonicznym spe³-

nienie równania (10.2) jest warunkiem wystarczaj¹cym do poprawnego szeregowania, nie

jest to warunek konieczny (to znaczy czasem poprawne szeregowanie jest mo¿liwe, mimo ¿e

równanie (10.2) nie jest spe³nione).

a. Rozwa¿ zbiór zadañ zawieraj¹cy poni¿sze niezale¿ne zadania okresowe:

w Zadanie P

1

: C

1

= 20; T

1

= 100

w Zadanie P

2

: C

2

= 30; T

2

= 145

Czy mo¿na poprawnie uszeregowaæ te zadania, u¿ywaj¹c szeregowania czêstotoliwoœciowe-

go monotonicznego?

b. Dodaj teraz do zbioru nastêpuj¹ce zadanie:

w Zadanie P

3

: C

3

= 68; T

3

= 150

Czy równanie (10.2) jest spe³nione?

c. Przypuœæmy, ¿e pierwsze instancje tych trzech zadañ przybywaj¹ w czasie t = 0. Za³ó¿my, ¿e

pierwsze terminy ka¿dego zadania s¹ nastêpuj¹ce:

D

1

= 100; D

2

= 145; D

3

= 150

Czy da siê dotrzymaæ wszystkich terminów, u¿ywaj¹c szeregowania czêstotoliwoœciowego

monotonicznego? Jak bêdzie z terminami przysz³ych powtórzeñ ka¿dego zadania?

10.4 Do systemu z oœmioma procesorami pod³¹czonych jest 20 stacji taœm. Do systemu trafia

wiele zadañ, a ukoñczenie ka¿dego z nich wymaga u¿ycia najwy¿ej czterech stacji taœm. Za³ó¿,

¿e ka¿de zadanie zaczyna pracê z trzema stacjami taœm i dzia³a tak przez d³ugi czas, korzysta-

j¹c przez chwilê z czwartej stacji tu¿ przed zakoñczeniem pracy. Za³ó¿ te¿, ¿e liczba tych

zadañ jest nieskoñczona.

a. Za³ó¿, ¿e mened¿er szeregowania w systemie operacyjnym nie uruchomi zadania, dopóki

nie bêd¹ dostêpne cztery stacje taœm. Kiedy zadanie zostaje uruchomione, przydziela mu siê

cztery stacje taœm, które zostaj¹ zwolnione dopiero po zakoñczeniu zadania. Jaka jest maksy-

malna liczba wykonywanych jednoczeœnie zadañ? Jaka jest maksymalna i minimalna liczba

taœm, które mog¹ pozostawaæ bezczynne w wyniku takiej strategii?

b. Zasugeruj alternatywn¹ strategiê, która poprawi wykorzystanie stacji taœm, a jednoczeœnie

pozwoli unikn¹æ zakleszczenia systemu. Jaka jest maksymalna liczba wykonywanych jedno-

czeœnie zadañ? Jakie s¹ granice liczby bezczynnych stacji taœm?