Szeregowanie procesˇw w systemie rozproszonym.pdf

Rok akademicki 2004/2005

POLITECHNIKA WARSZAWSKA

WYDZIAŁ ELEKTRONIKI I TECHNIK INFORMACYJNYCH

INSTYTUT INFORMATYKI

PRACA DYPLOMOWA MAGISTERSKA

Joanna widerska

SZEREGOWANIE PROCESÓW W SYSTEMIE

ROZPROSZONYM

Opiekun pracy:

dr in . J. Wytr bowicz

Ocena..............................................

........................................................

Podpis Przewodnicz cego

Komisji Egzaminu Dyplomowego

Specjalno : Budowa i oprogramowanie komputerów

Data urodzenia: 02.12.1980

Data rozpocz cia studiów: 01.10.1999

yciorys: Urodziłam si 02.12.1980 roku w Siedlcach. W latach 1987 – 1990

ucz szczałam do Szkoły Podstawowej nr 5 w Siedlcach, a nast pnie w latach 1990 –

1995 do Szkoły Podstawowej nr 8 w Siedlcach. W latach 1995 – 1999 kontynuowałam

nauk w I Liceum Ogólnokształc cym imienia Bolesława Prusa w Siedlcach w klasie o

profilu matematyczno-fizycznym z rozszerzon informatyk . W dniu 01.10.1999 r.

rozpocz łam studia na Wydziale Elektroniki i Technik Informacyjnych na

makrokierunku Informatyka, Automatyka i Robotyka, Elektronika i Telekomunikacja.

Od roku 2001 kontynuuj studia na specjalno ci Budowa i oprogramowanie

komputerów w Instytucie Informatyki.

..................................................................

podpis studenta

EGZAMIN DYPLOMOWY

Zło ył egzamin dyplomowy w dniu.........................................................................2005 r.

z wynikiem..........................................................................................................................

Ogólny wynik studiów........................................................................................................

Dodatkowe wnioski i uwagi Komisji.................................................................................

............................................................................................................................................

STRESZCZENIE

Celem pracy było stworzenie mechanizmu przydzielaj cego zadania do w złów

systemu Phoenix. Phoenix jest rozproszonym systemem operacyjnym czasu

rzeczywistego o podwy szonej niezawodno ci. W pracy opisano zało enia projektowe

dla rozwi zania problemu szeregowania zada oraz projekt i implementacj wybranego

algorytmu. Przedstawiono rozwi zania dla szeregowania lokalnego i globalnego.

Zaprezentowano analiz mechanizmów komunikacji mi dzyprocesowej oraz projekt i

implementacj mechanizmu najbardziej odpowiedniego dla systemu czasu

rzeczywistego. W trakcie projektowania du y nacisk poło ono na wybór mechanizmów

maksymalnie prostych a równocze nie zapewniaj cych realizacj zało e

projektowych.

słowa kluczowe: systemy operacyjne, systemy czasu rzeczywistego, systemy

rozproszone, równowa enie obci enia, profilowanie obci enia

Process Scheduler for a Distributed System

The aim of this work was to create a scheduler for the Phoenix system. Phoenix is a

distributed, fault tolerant, real-time, operating system. The thesis describes: scheduling

algorithms, solutions applied in local and global scheduling subsystems, inter process

communication, and the project of scheduler for Phoenix. Efficiency and scalability

were the main objectives for the project.

key words: operating systems, realtime systems, distributed systems, load balancing,

load profiling

Spis rzeczy

1 Wst p ............................................................................................................................ 5

1.1 Cel pracy............................................................................................................6

1.2 Układ pracy........................................................................................................6

2 Odrobina historii ........................................................................................................... 7

2.1. Dzielenie obci enia ......................................................................................... 8

2.1.1. Algorytmy dziel ce obci enie................................................................. 9

2.2. Równowa enie obci enia.............................................................................. 11

2.2.1. Statyczne równowa enie obci enia ...................................................... 12

2.2.2. Dynamiczne równowa enie obci enia.................................................. 13

2.2.3. Przykłady algorytmów równowa cych obci enie............................... 16

2.3. Profilowanie obci enia.................................................................................. 19

3 Zarz dzanie obci eniem w systemie Phoenix, zało enia projektowe....................... 20

3.1. Algorytm szeregowania lokalnego ................................................................. 22

3.1.1. Priorytety ................................................................................................ 22

3.1.2. Round-robin ............................................................................................ 23

3.1.3. EDF ( Earliest Deadline First ) ................................................................ 25

3.2. Algorytm przydzielania zada do procesorów ............................................... 27

3.2.1. Polityka zbierania informacji.................................................................. 27

3.2.2. Polityka przeniesie ................................................................................ 29

3.2.3. Polityka selekcji ...................................................................................... 29

3.2.4. Polityka lokalizacji ................................................................................. 30

4 Protokoły systemowe .................................................................................................. 31

4.1. Mechanizm komunikacji mi dzyprocesowej.................................................. 31

4.1.1. Komunikacja synchroniczna i asynchroniczna....................................... 31

4.1.2. Operacje bez buforowania i z buforowaniem ......................................... 33

4.1.3. Operacje niezawodne i nie gwarantowane.............................................. 35

4.1.4. Miejsca przeznaczenia komunikatów ..................................................... 35

4.1.5. Komunikacja mi dzyprocesowa w systemie Phoenix ............................ 37

4.2. Protokół konfiguracyjno – diagnostyczny ...................................................... 40

4.2.1. Konfiguracja systemu ............................................................................. 40

4.2.2. Diagnostyka ............................................................................................ 42

5 Implementacja............................................................................................................. 44

5.1. Szeregowanie lokalne ..................................................................................... 44

5.2. Komunikacja mi dzyprocesowa ..................................................................... 47

5.2.1. Struktura portu ........................................................................................ 47

5.2.2. Przekazywanie komunikatów ................................................................. 49

5.2.3. Konfiguracja systemu ............................................................................. 51

5.3. Przydzielanie zada do procesorów................................................................ 52

5.3.1. Zadania okresowe ................................................................................... 52

5.3.2. Polityka zbierania informacji.................................................................. 54

5.4. Testowanie ...................................................................................................... 59

5.5. Struktura implementacji.................................................................................. 63

6 Podsumowanie ............................................................................................................ 65

A Sposób instalacji systemu...........................................................................................68

A.1 Opis zawarto ci zał czonego dysku CD-ROM..............................................68

A.2 Sposób instalacji systemu...............................................................................68

A.3 Sposób prezentacji globalnego algorytmu szeregowania...............................69

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: