SystemyKolejkowe, Uniwersytet w Białymstoku.konspekty(informatyka), metody modelowania i symulacji
[ Pobierz całość w formacie PDF ]
Systemy kolejkowe
Teori
masowej obsługi
moemy uwaa za rozdział teorii procesów stochastycznych.
Podstawowym celem teorii kolejek jest opracowanie metod umo
liwiaj
cych wyznaczanie
podstawowych wska
ników charakteryzuj
cych proces obsługi i ocen
jako
ci pracy systemu
kolejkowego oraz wybór optymalnej struktury i organizacji obsługi. Przykładem prostego
systemu kolejkowego mo
e by
oczekiwanie na poł
czenie telefoniczne.
Charakterystycznymi poj
ciami zwi
zanymi z teori
kolejek s
:
-
Zgłoszenie
–
danie pełnienia przez system okre
lonej czynno
ci;
-
Obsługa
– spełnienie okre
lonej potrzeby.
-
Stanowiska obsługi (kanały obsługi)
–
rodki, które umo
liwiaj
obsług
zgłosze
np. kasa biletowa.
System kolejkowy
1
Strumie
Strumie
wej
ciowy
wyj
ciowy
Poczekalnia
(kolejka)
obsługi
m
Kanały
obsługi
Rysunek 1 Schemat blokowy systemu kolejkowego
1
Na wejciu pojawia si pewien cig zgłosze (
strumie
wej
ciowy
) wymagajcy
obsługi. Zgłoszenia, które pojawiaj
si
w systemie kierowane s
do obsługi (je
li s
wolne
stanowiska obsługi) lub te
do poczekalni (je
li wszystkie kanały obsługi s
zaj
te), gdzie
czekaj a zwolni si stanowisko obsługi. Na wyjciu pojawia si
strumie
wyj
ciowy
.
Zawiera on obsłu
one zgłoszenia, oraz te, które nie zrezygnowały z obsłu
enia.
1
Bogusław Filipowicz: Modele stochastyczne w badaniach operacyjnych, Wydawnictwa Naukowo-Techniczne,
Warszawa 1996, s. 13
Zachowanie zgłoszenia, które nadeszło w chwili, gdy wszystkie kanały obsługi s
zaj
te pozwala wyró
ni
nam trzy podstawowe grypy systemów kolejkowych:
-
Systemy ze stratami (bez poczekalni)
. Nie posiadaj
poczekalni, zatem zgłoszenie, które
nadeszło do systemu i odmówiono mu obsługi opuszcza system.
-
Systemy bez strat (z poczekalni
e zgłoszenia, które przybyły
do systemu mog opuci go dopiero po obsłueniu. Jeli nie ma wolnych stanowisk
)
. Charakteryzuj
si
tym,
obsługi to zgłoszenie kierowane jest do poczekalni o nieograniczonej pojemno
ci.
-
Mieszane systemy
. Charakterystyczn
cech
takich systemów jest obecno
warunków
porednich, np. ograniczony czas przebywania zgłoszenia w kolejce lub w systemie.
Systemy mo
emy rozró
nia
mi
dzy sob
równie
według liczby kanałów obsługi lub
pojemno
ci poczekalni. S
dwa takie typy:
z ograniczonym
lub
nieograniczonym rozmiarem
,
przy czym przez rozmiar systemu rozumie si
sumaryczn
liczb
kanałów obsługi i miejsc w
poczekalni. Niekiedy długo
kolejki nie jest ograniczona, ale czas oczekiwania jest tak du
y,
e zgłoszenie nie chce zajmowa
miejsca w kolejce lub po uprzednim jego zaj
ciu odchodzi.
S
to
systemy z niecierpliwymi klientami
.
Innym kryterium klasyfikacji systemów kolejkowych mo
e by
np. liczba
ródeł.
Rozró
niamy dwa typy takich systemów:
systemy otwarte
i
systemy zamkni
te
. Systemy
otwarte mog
cych do systemu.
W przypadku systemów zamknitych maksymalna liczba zgłosze do obsługi jest z góry
mie
nieograniczenie wielk
liczb
zgłosze
przychodz
ograniczona i stała w czasie.
Podstawowymi
wielko
ci
charakteryzuj
cymi
system
kolejkowy
s
:
strumie
zgłosze
,
proces obsługi
i
regulamin kolejki
.
Szczegółowo strumie
zgłosze
został omówiony w pierwszym rozdziale.
Proces obsługi okre
la sposób post
powania ze zgłoszeniami od strony kanału obsługi.
Charakteryzuj
go:
-
Czas trwania
obsługi
, czyli czas niezb
dny dla spełnienia przez system wszystkich
wymaga
pochodz
cych od jednego zgłoszenia, zwykle nie jest stały. Przyjmuje si
,
e
czasy obsługi poszczególnych zgłosze
nymi zmiennymi losowymi o
jednakowych rozkładach. Typ rozkładu czasu obsługi okrela nazw odpowiedniej
s
niezale
obsługi, obsługa:
wykładnicza, deterministyczna, Erlanga, dowolna
. Oznacza si
je
odpowiednio
M, D, E
k
, G
.
-
Zdolno
przepustowa systemu
, czyli maksymalna ilo zgłosze, które mog by
jednocze
nie obsługiwane przez system. Je
li system obsługuje tylko po jednym
zgłoszeniu,
to
nazywamy
do
jednokanałowym
(jednoliniowym)
.
W
przypadku
obsługiwania
kilku
zgłosze
jednocze
nie
mówimy
o
systemie
wielokanałowym
(wielodniowym)
.
-
Dost
pno
, która okre
la dost
p zgłosze
do kanałów obsługi. Dotyczy ona systemów
wielokanałowych z kilkoma strumieniami wej
ciowymi. Ka
dy strumie
ma swoj
grup
kanałów obsługi, które obsługuj
pne
dla wszystkich zgłosze. System jest
w pełni dost
pny
, jeli kade zgłoszenie moe by
jego zgłoszenia, ale s
te
stanowiska obsługi dost
obsłu
one przez dowolny kanał obsługi tego systemu. W przeciwnym wypadku mamy do
czynienia z systemem
niepełnodost
pnym
.
ny termin
dyscyplina obsługi
) okre
Regulamin kolejki (cz
sto spotyka si
równowa
la
porz
dek tworzenia kolejki. Podstawowe sposoby to:
-
Dyscyplina
FIFO
(ang.
First-In
,
First-Out
). Kolejka tworzona jest wg kolejno
ci
przybycia zgłosze
. Regulamin ten zwany jest równie
naturalnym
.
-
Dyscyplina
LIFO
(ang.
Last-In
,
First-Out
). Kolejka do obsługi powstaje na zasadzie
tworzenia stosu. Obsługiwane jest zgłoszenie, które ostatnie przybyło do kolejki.
Spotykane jest równie
inne okre
lenie tego regulaminu –
porz
dek odwrotny
.
-
Dyscyplina
RSS
(ang.
Random Selection for Service
). Zgłoszenia obsługiwane s
w sposób losowy, niezale
nie od kolejno
ci przybycia. Wybór ka
dego z przybyłych
zgłosze do obsługi jest jednakowo prawdopodobny.
-
Dyscyplina
RR
(ang.
Round-Robin
). Przewa
nie stosowana jest do opisu systemów
informatycznych. Zgłoszenia obsługiwane s
wg regulaminu FIFO, lecz obsługa jest
przerywana po upływie czasu
Q
zwanego
kwantem
. Jeli zgłoszenie nie zostało do
ko
ca obsłu
one to wraca z powrotem do kolejki z prawdopodobie
stwem
s
lub
opuszcza system z prawdopodobie
stwem 1–
s
.
-
Dyscyplina
PS
(ang.
Processor-Sharing
). Reprezentuje ona graniczny przypadek
Q
regulaminu RR, gdy
Q
Æ
0
i
s
Æ
1, za
iloraz
=
E
(
S
)
jest stały (
S
jest zmienn
1
− s
losow
opisuj
c
czas trwania obsługi zgłoszenia).
-
Priorytetowe szeregowanie
. Zgłoszenia, które maj
wy
szy priorytet obsługiwane s
w pierwszej kolejno
szym priorytetem.
Najwaniejsze znane regulaminy dziel si na
regulaminy bez przerywanej obsługi
–
ci, niezale
nie o liczby czekaj
cych zada
z ni
priorytet wzgl
dny
i
regulaminy z przerywan
obsług
–
priorytet bezwzgl
dny
(absolutny)
. Przy wzgl
dnym priorytecie nowo przybyłe zgłoszenie o wy
szym
priorytecie nie powoduje przerwania obsługi zadania z niszym priorytetem, tylko
czeka a
obsługa zako
czy si
. Zgłoszenia z jednakowym priorytetem mog
by
obsługiwane wg regulaminu FIFO lub LIFO. W przypadku priorytetu absolutnego
nowoprzybyłe zgłoszenie powoduje przerwanie obsługi zgłoszenia z ni
szym od niego
priorytetem. W zale
no
ci czy przerwana obsługa b
dzie kontynuowana, czy zacznie
si
niamy
bezwzgldne priorytety
z doko
czeniem obsługi
,
z obsług
od pocz
tku
i
z utrat
od pocz
tku, czy te
zgłoszenie opu
ci system nieobsłu
one, rozró
zgłoszenia
.
Mo
liwe s
równie
mieszane regulaminy obsługi. Je
li wyst
puje kilka strumieni, to mi
dzy
niektórymi z nich moe by przyjty regulamin z priorytetem wzgldnym, a midzy innymi z
priorytetem bezwzgl
dnym
2
.
2
Por. Bogusław Filipowicz: Modele stochastyczne w badaniach operacyjnych, Wydawnictwa Naukowo-
Techniczne, Warszawa 1996, s. 18 – 19
Por. Walenty Oniszczuk: Metody modelowania, Politechnika Białostocka, Białystok 1995, s. 33
[ Pobierz całość w formacie PDF ]