strumień wejściowy. Typowe modele matematyczne

24. Przychodzący przepływ popytu

24.1 Struktura QS

Badanie QS rozpoczyna się od analizy napływającego strumienia wymagań. Przychodzący przepływ popytu to zestaw wymagań, które wchodzą do systemu i wymagają obsługi. Napływający przepływ wymagań jest badany w celu ustalenia wzorców tego przepływu i dalszej poprawy jakości usług.

W większości przypadków przepływ przychodzący jest niekontrolowany i zależy od wielu czynników losowych. Liczba żądań przychodzących w jednostce czasu, zmienna losowa. Zmienną losową jest również odstęp czasu między sąsiednimi przychodzącymi żądaniami. Zakłada się jednak, że podana jest średnia liczba żądań otrzymanych na jednostkę czasu oraz średni odstęp czasu między sąsiednimi żądaniami przychodzącymi.

Średnia liczba klientów wchodzących do systemu kolejkowego w jednostce czasu nazywa się intensywność popytu i jest określana przez następującą zależność:

gdzie T - średnia wartość odstępu między nadejściem kolejnych żądań.

Dla wielu rzeczywistych procesów przepływ wymagań jest dość dobrze opisany przez prawo rozkładu Poissona. Taki przepływ nazywa się najprostszy.

Najprostszy przepływ ma następujące ważne właściwości:

Nieruchomość stacjonarna, co wyraża niezmienność reżimu probabilistycznego przepływu w czasie. Oznacza to, że liczba klientów wchodzących do systemu w regularnych odstępach czasu musi być średnio stała. Na przykład liczba wagonów przyjeżdżających do załadunku średnio dziennie powinna być taka sama w różnych okresach czasu, na przykład na początku i na końcu dekady.

bez następstw, która określa wzajemną niezależność otrzymywania takiej lub innej liczby żądań usługi w nienakładających się przedziałach czasowych. Oznacza to, że liczba żądań przychodzących w danym przedziale czasowym nie zależy od liczby żądań obsłużonych w poprzednim przedziale czasowym. Na przykład liczba pojazdów, które przyjechały po materiały dziesiątego dnia miesiąca, nie zależy od liczby pojazdów obsłużonych czwartego lub jakiegokolwiek innego poprzedniego dnia tego miesiąca.

własność zwyczajności, co wyraża praktyczną niemożliwość jednoczesnego otrzymania dwóch lub więcej wymagań (prawdopodobieństwo takiego zdarzenia jest niezmiernie małe w stosunku do rozpatrywanego okresu, gdy ten ostatni dąży do zera).

Ponieważ celem działania dowolnego systemu usługowego jest zaspokojenie wniosków (wymagań) do obsługi, przepływ wniosków (wymagań) jest jednym z podstawowych i najważniejszych pojęć teorii kolejka. Musisz nauczyć się określać ilościowo przychodzący przepływ wymagań, ale w tym celu musisz poznać jego naturę i strukturę.

Prawie każdy przepływ wymagań wchodzących do systemu usługowego jest procesem losowym. Rzeczywiście, jeśli weźmiemy t=0 za początkowy moment, wtedy w wielu przepływach (z wyjątkiem przypadku, gdy wymagania docierają ściśle zgodnie z harmonogramem) jest albo niemożliwe, albo raczej trudne, aby dokładnie przewidzieć moment nadejścia kolejnego wymagania, jak również momenty nadejścia kolejnych wymagań. Na przykład nie da się dokładnie wskazać momentów, kiedy klienci przychodzą do studia, pacjenci do szpitala, telefony przychodzą do centrali, sprzęt w warsztacie itp.

W konsekwencji momenty napływania wniosków, a także odstępy między nimi, są generalnie niezależnymi zmiennymi losowymi. Wówczas proces odbioru wymagań w systemie kolejkowym należy uznać za proces probabilistyczny lub losowy. Oznaczmy ten proces jako X(t). Ta funkcja określa liczbę żądań otrzymanych przez system w danym okresie . Dla każdego ustalonego t funkcja X(t) jest zmienną losową. Rzeczywiście, jeśli wybierzesz przedziały czasowe nawet o tej samej długości, to w tym przypadku nie możesz być pewien, że w każdym z tych przedziałów pojawi się taka sama liczba wymagań.

Przez okres czasu może nie być jednej aplikacji lub może być 1, 2, ... aplikacji. Ale bez względu na to, jak długie przedziały czasowe wybierzemy, liczba wniosków będzie tylko liczbą całkowitą.

Przepływ wymagań można przedstawić jako wykres jednej z implementacji zmiennej losowej funkcji X(t), weź tylko nieujemne wartości całkowite. W tym przypadku wykres (rys. 24.2) jest linią schodkową ze skokami równymi jednej lub kilku jednostkom, w zależności od tego, czy wymagania pojawiają się pojedynczo, czy w grupach. Więc losowy proces X(t), ma następujące cechy.

1. Dla każdego ustalonego t funkcjonować X(t), przyjmuje nieujemne wartości całkowite 0, 1, 2,...,R,... i nie maleje wraz ze wzrostem.

2. Liczba roszczeń otrzymanych w danym okresie , zależy od długości tego przedziału, czyli od wartości t.

3. Implementacje procesów są liniami stopniowanymi, nieco różniącymi się od siebie. Z teorii procesów losowych wiadomo, że proces będzie całkowicie określony z probabilistycznego punktu widzenia, jeśli znane będą wszystkie jego wielowymiarowe prawa dystrybucji:

Jednak znalezienie takiej funkcji w ogólnym przypadku jest bardzo trudnym i czasem nierozwiązywalnym problemem. Dlatego w praktyce starają się wykorzystywać procesy, które mają właściwości, które pozwalają znaleźć prostsze sposoby ich opisu. Te właściwości obejmują:

Stacjonarność (lepsza jednorodność w czasie);

Brak następstw (markowski), czasem mówią o braku pamięci;

Pospolitość.

Wymienione właściwości zostały uwzględnione powyżej w badaniu procesów stacjonarnych i Markowa, więc tutaj przypominamy tylko istotę tych właściwości w kategoriach teorii kolejek.

Przepływ zapotrzebowań nazywamy stacjonarnym lub jednorodnym w czasie, jeśli prawdopodobieństwo otrzymania określonej liczby zapotrzebowań w określonym przedziale czasu zależy tylko od długości przedziału, a nie od jego położenia w czasie (innymi słowy, nie zależy pochodzenia). Zatem dla przepływu stacjonarnego prawdopodobieństwo, że w przedziale zrobi dokładnie R wymagania są równe prawdopodobieństwu otrzymania R wymagania dotyczące przedziału [a, +t] , gdzie a>0, tj.

Oznacza to, że probabilistyczne charakterystyki przepływu (parametry prawa rozdziału) nie powinny zmieniać się w czasie.

Wiele rzeczywistych przepływów popytu ma właściwość stacjonarności, gdy patrzy się na nie w krótkich okresach. Do takich przepływów należą: przepływ połączeń do centrali w określonych odstępach czasu, przepływ klientów do sklepu, przepływ sprzętu radiowego wymagającego naprawy, natężenie ruchu pasażerskiego itp. Jednak niektóre z wymienionych przepływów zmieniają się w trakcie w dzień (prawdopodobieństwo połączeń w nocy krócej niż w ciągu dnia, godziny szczytu w komunikacji miejskiej).

W niektórych przepływach liczba żądań, które weszły do ​​systemu po dowolnym momencie nie zależy od liczby wcześniej otrzymanych żądań i momentów ich nadejścia, tj. odstępy między nadejściem żądań są uważane za wartości niezależne i nie ma między nimi związku. Przyszły stan systemu nie zależy od jego stanu przeszłego. Przepływ z tą właściwością nazywany jest przepływem bez następstw lub przepływem Markowa. Właściwość braku następstw (brak pamięci) jest nieodłącznym elementem wielu rzeczywistych wątków. Na przykład przepływ połączeń do centrali jest przepływem bez skutków ubocznych, ponieważ z reguły następne połączenie przychodzi niezależnie od tego, kiedy i ile połączeń zostało wykonanych do tego momentu.

W wielu przypadkach charakter przepływu wymagań jest taki, że jednoczesne pojawienie się dwóch lub jeszcze wymagania są niemożliwe lub prawie niemożliwe. Strumień o tej właściwości nazywany jest zwykłym strumieniem.

Jeśli R R >2 (h) -prawdopodobieństwo wystąpienia w przedziale h więcej niż jedno wymaganie, to dla zwykłego przepływu powinno to być:

,

tj. zwyczajność przepływu wymaga, aby prawdopodobieństwo wystąpienia więcej niż jednego wymagania w krótkim okresie czasu h byłaby nieskończenie małą ilością wyższego rzędu niż h. W niektórych przepływach rzeczywistych własność ta jest oczywista, podczas gdy w innych przyjmujemy ją z dość dobrym przybliżeniem do rzeczywistości. Klasycznymi przykładami takiego przepływu są przepływ połączeń do centrali oraz przepływ klientów w studio.

Przepływ żądania, który ma te trzy właściwości, nazywany jest najprostszym. Można wykazać, że każdy prosty przepływ jest opisany przez proces Poissona. W tym celu przypominamy definicję procesu Poissona przyjętą w teorii funkcji losowych.

losowy proces X(t) (0≤ t<∞) wartości całkowite nazywamy procesem Poissona, jeśli jest to proces z niezależnymi przyrostami lub jeśli jakikolwiek przyrost procesu w przedziale czasu h jest rozłożony zgodnie z prawem Poissona z parametrem λ h, gdzie λ>0 tych.

W szczególności, jeśli t=0, X(0)=0, to (3) zostaje przepisane w następujący sposób:

(4)

Tutaj V r (h) oznacza prawdopodobieństwo, że interesujące nas zdarzenie wystąpi dokładnie R raz na jakiś czas h(z punktu widzenia teorii kolejkowania) V r (h) określa prawdopodobieństwo, że przez pewien czas h wejdzie dokładnie do systemu serwisowego R wymagania).

Znaczenie parametru Xłatwo jest dowiedzieć się, czy znajdziesz matematyczne oczekiwanie procesu Poissona: M [X(t)]=M. Na t=1 dostajemy M[X(1)]=1. W związku z tym istnieje średnia liczba aplikacji na jednostkę czasu. Dlatego wartość λ często określana jako intensywność lub gęstość strumienia.

Z definicji procesu Poissona wynikają bezpośrednio trzy właściwości, identyczne z powyższymi:

1) Niezależność przyrostów. W niezależności przyrostów dla procesu Poissona nie ma następstw - proces jest markowski.

2) Jednolitość w czasie. Oznacza to, że prawdopodobieństwa… V r (h) nie zależą od momentu początkowego t rozważany przedział , ale zależą tylko od długości interwału h:

3) Zwyczajność. Zwyczajność procesu Poissona oznacza, że ​​praktycznie niemożliwe jest, aby grupa wymagań dotarła w tym samym momencie.

Zatem jednoczesne otrzymanie dwóch lub więcej roszczeń w małym przedziale czasowym h jest mało prawdopodobne, zatem

co wskazuje na zwyczajność procesu Poissona.

W ten sposób ustaliliśmy, że przepływ opisany przez proces Poissona jest najprostszy. Jednak prawdziwe jest również odwrotne założenie, że najprostszy przepływ opisuje proces Poissona. W rezultacie najprostszy przepływ jest często nazywany również przepływem Poissona. Proces Poissona w teorii kolejkowania zajmuje szczególne miejsce, podobnie jak w teorii prawdopodobieństwa, obok innych praw dystrybucji, które zajmuje normalne prawo. I nie chodzi o to, że najprościej jest to opisane matematycznie, ale o to, że jest najczęstsze. Przepływ Poissona jest przepływem granicznym (przepływ asymptotyczny, gdy łączy się duża liczba innych przepływów).

Definicja 6.1. Strumień wejściowy nazywamy najprostszym, jeśli:

1) prawdopodobieństwo pojawienia się tej lub innej liczby aplikacji w przedziale czasowym zależy tylko od czasu jego trwania i nie zależy od jego położenia na osi czasu (stacjonarność przepływu wejściowego), ponadto aplikacje przychodzą pojedynczo (wejście zwykłe przepływ) i niezależnie od siebie (brak efektu wtórnego w strumieniu wejściowym);

2) prawdopodobieństwo oddzielnego zdarzenia losowego (pojawienia się aplikacji) w krótkim przedziale czasu jest proporcjonalne do nieskończenie małego wyższego rzędu małości w porównaniu z np. gdzie jest

3) prawdopodobieństwo realizacji dwóch lub więcej zdarzeń losowych (pojawienia się dwóch lub więcej wniosków) w krótkim odstępie czasu to wartość

Brak następstw w definicji najprostszego strumienia wejściowego oznacza, że ​​dla dowolnych nienakładających się przedziałów czasowych liczba roszczeń napływających w jednym z tych przedziałów nie zależy od liczby roszczeń napływających w innych przedziałach.

Pomimo faktu, że strumienie wejściowe i wyjściowe wielu prawdziwe systemy usługi nie w pełni spełniają definicję najprostszego przepływu, pojęcie najprostszego przepływu jest szeroko stosowane w teorii kolejkowania. Ta okoliczność związana jest nie tylko z faktem, że w praktyce często spotyka się najprostsze przepływy, ale także z tym, że najprostszym przepływem jest suma nieograniczonej liczby stacjonarnych przepływów zwykłych z niemal każdym następstwem. W związku z tym rozważmy główne właściwości najprostszego przepływu.

Twierdzenie 6.1. Dyskretna zmienna losowa, która przyjmuje wartości i charakteryzuje dla najprostszego przepływu wejściowego liczbę klientów wchodzących do systemu kolejkowego w przedziale czasu trwania t, rozkładana jest zgodnie z prawem Poissona z parametrem

Rozważmy skalarny proces losowy ze stanami dyskretnymi (czyli dla dowolnego ustalonego momentu czasu jego przekrój) jest dyskretną zmienną losową ze zbiorem możliwych wartości.Niech jego bycie w stanie oznacza, że ​​w usłudze jest k żądań system.

Zgodnie z warunkami twierdzenia i definicją najprostszego przepływu, proces losowy jest procesem jednorodnym Markowa ze stanami dyskretnymi, a dla dowolnych liczb całkowitych nieujemnych i oraz j, gęstość prawdopodobieństwa przejścia systemu kolejkowego od stanu , do stanu w dowolnym momencie jest określona przez równość

Dlatego w tym przypadku układ równań Kołmogorowa ma następującą postać:

gdzie jest prawdopodobieństwo, że w przedziale czasu trwania t badany system kolejkowy otrzyma pewną liczbę żądań. A ponieważ wynika to z definicji 6.1 najprostszego przepływu żądań, które

wtedy dochodzimy do problemów Cauchy'ego w odniesieniu do funkcji

i funkcje

Rozwiązując kolejno zadania Cauchy'ego (6.3), (6.4), w przypadku najprostszego przepływu wejściowego, znajdujemy prawdopodobieństwo, że liczba klientów w przedziale czasu o czasie trwania t będzie równa

Zależności (6.5) oznaczają, że zmienna losowa ma rozkład zgodnie z prawem Poissona z parametrem

Wniosek 6.1. Jeżeli strumień wejściowy jest najprostszy, to średnia liczba żądań wchodzących do systemu kolejkowego w przedziale czasu trwania t jest równa

Aby określić średnią liczbę wniosków, musisz znaleźć matematyczne oczekiwanie zmiennej losowej. A ponieważ zgodnie z (6.5), rozkład jest zgodny z prawem Poissona z parametrem wtedy

Zgodnie z udowodnionym wnioskiem, parametr Λ jest średnią liczbą zgłoszeń przychodzących w jednostce czasu. Dlatego nazywa się to intensywnością lub gęstością najprostszego przepływu.

Wniosek 6.2. Jeżeli wejściowy przepływ żądań jest najprostszy, to wariancja skalarnej zmiennej losowej charakteryzująca rozrzut liczby żądań wchodzących do systemu kolejkowego w przedziale czasu trwania t, w stosunku do ich wartości średniej, jest równa

M Jeżeli strumień wejściowy jest najprostszy, to zgodnie z (6.5) zmienna losowa jest rozkładana zgodnie z prawem Poissona z parametrem Dlatego,

Zwróćmy uwagę, że zgodnie z (6.6) i (6.7) zmienna losowa o rozkładzie zgodnie z prawem Poissona ma to samo oczekiwanie i wariancję.

Przykład 6.1. Biuro obsługi otrzymuje średnio 12 zamówień na godzinę. Uznając przepływ zamówień za najprostszy, określamy prawdopodobieństwo, że: a) w ciągu 1 minuty nie wpłynie żadne zamówienie; b) w ciągu 10 minut wpłyną nie więcej niż trzy zamówienia.

Ponieważ przepływ zleceń jest najprostszy i intensywność, to zgodnie z (6.5) mamy:

Zgodnie z definicją 6.1 najprostszego przepływu, zmienną losową jest długość odstępu czasu pomiędzy dwoma kolejno przychodzącymi zapytaniami.Do budowy modeli matematycznych systemów kolejkowych niezbędna jest znajomość dystrybuanty zmiennej losowej lub jej rozkładu gęstość (prawdopodobieństwa)

Twierdzenie 6.2. W przypadku najprostszego strumienia wejściowego o natężeniu A, czas trwania odstępu czasu między dwoma kolejnymi żądaniami ma rozkład wykładniczy z parametrem A.

Wejściowy strumień informacji

Wejściowy strumień informacji to sekwencja dokumentów i danych wchodzących do systemu informatycznego.

Zobacz też: Zawartość

• - urządzenie na wejściu systemu, które konwertuje sygnały wejściowe w celu skoordynowania działania systemu ze źródłem zewnętrznym. uderzenie...

  Duży encyklopedyczny słownik politechniczny

• - sygnał drogowy chroniący drogę odrębnego punktu. Jak V. z. można użyć sygnalizacji świetlnej lub semaforów. Semafor wejściowy jest zainstalowany nie bliżej niż 50 m, sygnalizacja świetlna nie jest bliżej niż 15 m od dowcipu strzałki wejściowej ...

  Techniczny słownik kolejowy

• - "... Kontrola wyrobów dostawcy otrzymanych przez konsumenta lub klienta i przeznaczonych do wykorzystania przy produkcji, naprawie lub eksploatacji wyrobów..." Źródło: Zarządzenie Roskartografii z dnia 29.06...

  Oficjalna terminologia

• - kontrola zgodności z danymi paszportowymi wyrobów przemysłowych dostarczanych na budowę...

  Słownik budowlany

• - przepływ materiałów wchodzących do systemu logistycznego z zewnątrz...

  Słowniczek pojęć biznesowych

• - dokument sporządzony w określonej formie i zawierający dane przeznaczone do wprowadzenia do systemu informatycznego. Zobacz też: Treść  ...

  Słownictwo finansowe

• - zestaw komunikatów krążących w systemie, niezbędnych do realizacji procesów zarządczych...

  Wielki Słownik Ekonomiczny

• - zewnętrzny przepływ materiałów wchodzących do tego systemu logistycznego ze środowiska zewnętrznego...

  Wielki Słownik Ekonomiczny

• - urządzenie na wejściu systemu lub urządzenie, które przekształca czynności wejściowe na sygnały, które są wygodne do dalszego przetwarzania, transmisji i rejestracji lub do koordynowania działania systemów z różnymi wejściami -...

  Wielka radziecka encyklopedia

• - ...

  Słownik antonimów

• - INPUT, patrz enter i...

  Słownik wyjaśniający Ożegowa

• - WEJŚCIE, wejście, wejście. przym. do wejścia. Drzwi wejściowe. Bilet wstępu. Wlot...

  Słownik wyjaśniający Uszakowa

• - wejście I przym. początkowy, początkowy, początkowy. II przym. 1. Nadanie prawa do wejścia 1. gdzieś. 2. Służy jako wejście...

  Słownik wyjaśniający Efremovej

• - wejście przym., użyj. komp. często 1. Kiedy mówisz o drzwiach, masz na myśli drzwi zewnętrzne prowadzące do domu z ulicy. Ktoś wyszedł na korytarz i otworzył frontowe drzwi. 2...

  Słownik Dmitrieva

• - Wejście "...

  Rosyjski słownik ortograficzny

• - ...

  Formy słowne

„Wejściowy strumień informacji” w książkach

Przepływ informacji w przyrodzie

autor

Przepływ informacji w przyrodzie

Z książki Antropologia i koncepcje biologii autor Kurczanow Nikołaj Anatolijewicz

Przepływ informacji w przyrodzie Jak przepisana jest informacja genetyczna w komórce DNA? RNA? białko determinuje przepływ informacji w dzikiej przyrodzie. Ten przepływ informacji jest realizowany w zdecydowanej większości żywych systemów. Ma definicję centralnego dogmatu

"VAT naliczony

Z książki Jak poprawnie używać „uproszczenia” autor Kurbangaleeva Oksana Aleksiejewna

VAT „naliczony” Przy zakupie środka trwałego organizacja kupująca płaci jego koszt, w tym podatek od wartości dodanej. Przedsiębiorca stosujący uproszczony system podatkowy nie może jednak zwrócić kwoty podatku „naliczonego” z budżetu. Ta ilość

Zatrzymaj przepływ szkodliwych informacji

Z książki Dlaczego księżniczki gryzą. Jak rozumieć i edukować dziewczyny autor Biddulph Steve

Zatrzymaj przepływ szkodliwych informacji Chociaż nienawidzimy tego przyznawać, my, ludzie, jesteśmy zasadniczo zwierzętami stadnymi. Nieustannie szukamy uznania u innych i nieustannie naśladujemy otaczających nas ludzi, starając się dostosować do jakiejś ogólnie przyjętej normy; w naszych czasach

Napływ informacji z Afryki o różnych formach człowieka kopalnego skłania do świeżego spojrzenia na proces izolowania najstarszych przodków człowieka ze świata zwierzęcego oraz na główne etapy formowania się ludzkości.

Z książki Antyczne cywilizacje autor Bongard-Levin Grigorij Maksimowicz

Przepływ informacji z Afryki o różne formy Skamieniały człowiek każe nam na nowo spojrzeć na proces izolowania najstarszych przodków człowieka ze świata zwierząt oraz na główne etapy formowania się ludzkości. Wyjaśnienie wielu problemów przyczynia się do:

Konwerter wejściowy

Z książki Wielka radziecka encyklopedia (VX) autora TSB

Przepływ informacji dla getint()

Z książki The C Language - A Beginner's Guide autor Prata Stephen

Przepływ informacji dla getint() Jakie wyjście powinna mieć nasza funkcja? Po pierwsze, nie ma wątpliwości, że musiałby zwrócić wartość odczytanej liczby. Oczywiście funkcja scanf() już to robi. Po drugie, co jest bardzo ważne, stworzymy funkcję, która

Świadomość to przepływ energii i informacji

Z książki Mindsight. Nowa nauka o osobistej transformacji przez Siegela Daniela

Świadomość to przepływ energii i informacji Energia to zdolność do wykonywania czynności, takich jak poruszanie kończynami lub formowanie myśli. Fizyka to odkrywa Różne rodzaje. Energię promieniowania odczuwamy siedząc na słońcu, energię kinetyczną podczas spaceru po plaży czy pływania,

Przepływ informacji

Z książki Zbiór opowiadań i powieści autor Lukin Evgeny

Przepływ informacji Natychmiast, gdy tylko Walery Michajłowicz Achlomow pojawił się na progu działu redakcyjnego, stało się jasne, że na spotkaniu planistycznym mocno uderzył go główny.- Wykorzystaj życzliwość mojej postaci! powiedział z cichą furią. - Umysł jest niezrozumiały: in

Rozdział 2 DYPLOMACJA IMPERIALIZMU KULTUROWEGO I SWOBODNY PRZEPŁYW INFORMACJI

Z książki autora

ROZDZIAŁ 2 DYPLOMACJA IMPERIALIZMU KULTUROWEGO I SWOBODNY PRZEPŁYW INFORMACJI Od ćwierćwiecza jedna doktryna – idea, że ​​żadne bariery nie powinny uniemożliwiać przepływu informacji między krajami – zdominowała międzynarodowe myślenie o komunikacji i

Przepływ informacji i Twoja osobista filozofia

Z książki Myśl i rób! autor Baranowski Siergiej Waleriewicz

Przepływ informacji i Twoja osobista filozofia Nasz wiek jest dobry choćby dlatego, że zawiera dużo informacji. Sam Internet otwiera przed nami setki nowych drzwi. Nie słuchaj tych, którzy nazywają Sieć śmieciami! Internet to nie wysypisko śmieci, ale kiepsko uporządkowana biblioteka. Dziesiątki tysięcy różnorodnych

autor Gosstandart Rosji

Z książki OPROGRAMOWANIE SYSTEMÓW WBUDOWANYCH. Ogólne wymagania do opracowania i dokumentacji autor Gosstandart Rosji

5.1 Przepływ informacji między procesami cyklu życia systemu i oprogramowania

Z książki OPROGRAMOWANIE SYSTEMÓW WBUDOWANYCH. Ogólne wymagania dotyczące rozwoju i dokumentacji autor Gosstandart Rosji

5.1 Przepływ informacji między procesami koło życia systemy i oprogramowanie 5.1.1 Przepływ informacji z procesów systemowych do procesów oprogramowania Proces oceny bezpieczeństwa systemu powinien identyfikować możliwe sytuacje awaryjne systemu i ustalać ich kategorie,

12.37 Przewodnik po informacjach dotyczących wejścia/wyjścia oprogramowania

Z książki OPROGRAMOWANIE SYSTEMÓW WBUDOWANYCH. Ogólne wymagania dotyczące rozwoju i dokumentacji autor Gosstandart Rosji

12.37 Oprogramowanie Informacje wejścia/wyjścia Podręcznik informacji wejścia/wyjścia Oprogramowanie wyjaśnia użytkownikowi, jak prezentować, wprowadzać informacje wejściowe i jak interpretować informacje wyjściowe, w jakim trybie (wsadowym lub interaktywnym) działa system

Elementy teorii kolejkowania

§ 1. Wstęp

Teoria kolejkowania jest inaczej nazywana teorią kolejkowania. Rzeczywiście, teoria kolejek w dużej mierze poświęcona jest badaniu kolejek, które powstają w różnych systemach.

Główną cechą systemów kolejkowych są następujące zmienne losowe:

średni czas, jaki klient spędza w kolejce;

procent czasu bezczynności systemu (z powodu braku klientów).

O funkcjonalności systemów kolejkowych decydują następujące czynniki:

dystrybucja momentów dystrybucji klientów;

dystrybucja czasu trwania usługi;

konfiguracja systemu obsługi (usługa szeregowa, równoległa lub równoległa-szeregowa);

dyscyplina w kolejce (obsługa w kolejności przyjazdu, obsługa w odwrotnej kolejności, losowy dobór klientów);

pojemność bloku oczekującego (ograniczona lub nieograniczona);

moc lub moc źródła zapotrzebowania (ograniczona i nieograniczona);

inne cechy systemu (zdolność klientów do przechodzenia z jednej kolejki do drugiej, niezerowe prawdopodobieństwo awarii itp.).

Główne czynniki to dwa pierwsze.

Każdy system kolejkowy składa się z następujących głównych elementów:

przychodzący przepływ klientów;

urządzenie serwisowe;

dyscyplina w zgodzie.

§ 2 . Strumień wejściowy klienta

Rozważ ciągi zmiennych losowych

Udawajmy, że t o = 0 to początkowy moment działania systemu; t 1 = t o + τ 1 , t 2 = t 1 + τ 2 , …, t k = t k -1 + τ k , …., gdzie τ k są niezależnymi zmiennymi losowymi o rozkładzie wykładniczym z parametrem λ.

W tutaj t 1 - moment przybycia pierwszego klienta, τ 1 - odstęp czasu między uruchomieniem systemu a przybyciem pierwszego klienta, τ 2 - odstęp czasu między przybyciem pierwszego i drugiego klienta itp.

Podciąg
, zdefiniowany w powyższy sposób nosi nazwę najprostszy (Poissona) pływ. Stała nazywany jest parametrem najprostszego przepływu.

Właściwości prostego strumienia

1. Przesunięcie przepływu o T

Niech będzie prosty przepływ
z parametrem λ.

Przesuwając przepływ o T, dostajemy strumień
, który będzie również najprostszym przepływem o tym samym parametrze λ. Na przykład, jeśli T jest pomiędzy oraz , wtedy nowy strumień wygląda tak:

, ….

2. Scalanie dwóch wątków

P
Niech będą dwa niezależne przepływy elementarne

Z
parametry λ (1) , λ (2) odpowiednio. Powiemy, że przepływ powstał w wyniku połączenia dwóch przepływów, jeśli zbiór ( t k) jest sumą zbiorów ( t k (1) }, {t k ( 2) ) oraz elementy zestawu ( t k) są posortowane w porządku rosnącym.

P
odpływ wynikający z połączenia dwóch niezależnych najprostszych przepływów jest również najprostszym przepływem o parametrze λ = λ(1) + λ(2) , gdzie λ(j)– parametr przepływu

3. Dzielenie najprostszego strumienia

Niech będzie prosty przepływ z parametrem λ,

oraz ciąg niezależnych zmiennych losowych
, przyjmując dwie wartości:

P(ξ i = 1) = p, P(ξ i = 0) = q, p  0, q  0, p + q = 1.

Takie zmienne losowe nazywamy Bernoulli(z parametrem p). Procedura podziału przepływu ( t k) wygląda następująco: liczba t ja odnieś się do pierwszego przepływu, jeśli ξ i= 1; jeśli i= 0, to liczba t ja odnoszą się do drugiego strumienia. Taką operację nazywamy dzieleniem strumienia na dwa Bernoulli(z parametrem p).

Przepływy otrzymane w wyniku rozdzielenia Bernoulliego najprostszego przepływu są niezależnymi najprostszymi przepływami o parametrach odpowiednio λ (1) = λp, λ (2) = λq.

Zauważ, że dowody tych właściwości najprostszego przepływu można znaleźć w .

H
herez X(t) W dalszej części będziemy określać liczbę klientów w systemie w danej chwili t, tj.

Właściwości procesów Poissona

Przyrost procesu Poissona jest jednorodny.

Oznacz przez X((a,b])= X(b) – X(a) przyrost procesu, który można interpretować jako liczbę klientów wchodzących do systemu w przedziale ( a,b]. Jednorodność oznacza spełnienie warunku:

P( X((a,b]) = k) = P( X((0,b-a]) = k) = P( X(b-a) = k),

tych. rozkład prawdopodobieństwa liczby klientów wchodzących do systemu w przedziale ( a,b], zależy tylko od długości tej przerwy.

Przyrosty procesu Poissona są niezależne.

Rozważ przedział (0, b] i załóżmy, że jest podzielony na nieprzecinające się przedziały (0, b 1 ], (b 1 , b 2 ], , ( b N-1, b N]. Wynajmować b 0 = 0. Wtedy X((b 0 , b 1 ]), X((b 1 , b 2]), , X((b N-1, b N ]) to liczba klientów wchodzących do systemu w odpowiednich okresach czasu. Ilości te są niezależne, tj.

P( X((b 0 , b 1 ]) = i 1 , , X((b N-1, b N]) = i N) =

P( X((b 0 , b 1 ]) = i 1) P( X((b N-1, b N]) = i N).

Dowody na te właściwości można znaleźć w .

Zadania do § 2.

2.1. Istnieją dwie zmienne losowe  1 i  2 . Są niezależne i mają rozkład wykładniczy z parametrami  1 i  2 odpowiednio. Wprowadzamy następującą zmienną losową:  = min(  1 ,  2). Udowodnij, że ta wielkość ma rozkład wykładniczy z parametrem = 1 + 2 .

2.2. Biorąc pod uwagę dwie niezależne zmienne losowe  1 oraz  2 o rozkładzie Poissona z parametrem  1 oraz  2 odpowiednio. Niech zmienna losowa  = 1 + 2 . Wykazać, że ta wielkość ma rozkład Poissona z parametrem  = 1 + 2 .

2.3. Wynajmować  to liczba klientów w sklepach i ma rozkład Poissona z parametrem  . Niech każdy klient z prawdopodobieństwem p dokonuje zakupu w tym sklepie. Wymagane jest wykazanie, że liczba klientów, którzy dokonali zakupu w tym sklepie posiada rozkład Poissona z parametrem p.

2.4. Klienci przychodzą do restauracji według przepływu Poissona ze średnią częstotliwością 20 klientów na godzinę. Restauracja otwiera się o godzinie 11.00.

a) prawdopodobieństwo, że o 11.12 w restauracji będzie 20 klientów, biorąc pod uwagę, że o 11.07 w restauracji było 18 klientów;

b) prawdopodobieństwo, że nowy gość pojawi się w restauracji między 11.28 a 11.30, jeśli wiadomo, że poprzedni gość przybył do restauracji o 11.25.

2.5. Produkty pobierane są z magazynu o pojemności 80 sztuk na stanie, zgodnie z przepływem Poissona w tempie 5 sztuk dziennie.

a) prawdopodobieństwo, że w ciągu pierwszych dwóch dni z magazynu zostanie pobranych 10 sztuk produktów;

b) prawdopodobieństwo, że do końca czwartego dnia w magazynie nie pozostanie ani jedna jednostka towaru.

§

3. Proces śmierci i reprodukcji

Zbudujmy proces śmierci i reprodukcji X(t) „konstruktywnie”.

Rozważ dwie sekwencje i. Pierwsza odpowiada za wprowadzanie klientów do systemu (odtworzenie), a druga za obsługę klientów (śmierć):

Dodatkowo podamy dwie niezależne sekwencje
niezależne zmienne losowe o rozkładzie wykładniczym z parametrem =1.

Proces X(t) jest skonstruowany w następujący sposób. Wynajmować
, gdzie
. Potem na przerwie
proces X(t) zachowa swoją wartość , gdzie
,

.

W tym momencie t 1 wartość procesu X(t) zwiększy się lub zmniejszy o jeden, w zależności od tego, który z dwóch momentów
jest przed:

W ten sposób określiliśmy znaczenie procesu X(t) w punkcie t 1 równy ; potem ewolucja procesu X(t) na interwale
, gdzie
oraz
przestrzega tego samego prawa: X(t) w tej chwili nie zmienia się w tym przedziale t 2

zwiększany o jeden, jeśli
, aw przeciwnym razie zmniejsza się o jeden.

Jeśli
, to wartość procesu X(t) wzrasta o jeden w losowym momencie
.

Tak zbudowany proces
, nazywa się jednorodnym w czasie procesem śmierci i reprodukcji; jego rozkłady są całkowicie określone przez zbiór parametrów, a początkowy rozkład X(0):

Wygodnie jest korzystać z następujących wykres do reprezentowania rozwoju procesu X(t):

Powyższe strzałki odpowiadają dynamice procesu reprodukcji: od i w tym stanie proces przechodzi do ( i+1)-ty stan z intensywnością ; strzałki poniżej odpowiadają dynamice procesu śmierci: z intensywnością proces od i-ty stan idzie do ( i-1)-ty stan.

Zestaw funkcji

opisuje rozkład procesu X(t); poniżej przedstawiamy układ równań, które spełniają te funkcje.

Pamiętaj, że nie każdy zestaw parametrów
reaguje na „niezdegenerowany” proces X(t); faktem jest, że jeśli liczby rosną bardzo szybko w
, to proces X(t) w ostatniej chwili t może „eksplodować”, tj. z dodatnim prawdopodobieństwem przekroczenia dowolnego poziomu i wzrostu do
. W ten sposób np. populacja bakterii w sprzyjające środowisko. Podobnie przebiegają procesy opisujące reakcje chemiczne prowadzące do wybuchu.

Procesy X(t), dla których wszyscy
, należą do tzw czyste procesy hodowlane. Procesy, dla których
, nazywa procesy czystej śmierci.

Poniższy lemat podaje konieczne i wystarczające warunki dotyczące parametrów:
, które gwarantują skończoność procesu czystej reprodukcji
z parametrami.

Lemat. Niech proces czystej reprodukcji z parametrami. Następnie dla skończoności procesu konieczne i wystarczające jest rozbieżność szeregu

Wynajmować X(t) proces śmierci i reprodukcji o tych samych parametrach proces , a także parametry
. To oczywiste, że

P( X(t)  )  P( X + (t)  ) .

Dlatego otrzymujemy wniosek z lematu.

Konsekwencja. Jeżeli dla dowolnego procesu śmierci reprodukcji X(t) warunek
, to dla każdego
sprawiedliwy P( X(t)  ) = 1, tj. proces jest zakończony.

Dowód lematu można znaleźć w .

Zadania do § 3

3.1. Rozważ proces śmierci i reprodukcji, dla którego

Wymagane jest narysowanie diagramu odpowiadającego temu procesowi.

3.2. Pozwól klientom, którzy chcą uzyskać pomoc telefoniczną, sformułują najprostszy przepływ z parametrem . Niech każda rozmowa trwa - orientacyjny czas. Wynajmować X(t) to liczba klientów w systemie w czasie t. Narysuj schemat odpowiadający procesowi X(t).

3.3. Niech w warunkach problemu 3.2

telefon ma pamięć dla jednego klienta: jeśli klient dzwoni i telefon jest zajęty, ale pamięć telefonu jest wolna, to urządzenie proponuje rozłączyć się i czekać na połączenie. Gdy telefon jest wolny, zadzwoni dzwonek;

jest centrala automatyczna i dwa telefony, każdy telefon ma swojego operatora: jeżeli w czasie rozmowy klienta jest telefon wolny, centrala automatycznie kieruje klienta na ten telefon;

przełącznik (patrz punkt 2)) ma pamięć dla jednego klienta;

każdy telefon (patrz punkt 2)) posiada pamięć dla jednego klienta.

Dla wszystkich powyższych przypadków narysuj diagram odpowiadający procesowi X(t).

3.4. Określ, czy końcowe procesy czystej reprodukcji mają następujące współczynniki reprodukcji:

a)  k =k +  ,  >0,  >0, k= 0, 1, ...

b)  0 = 1,  k +1 = (k+1) k , k = 0, 1, ...

w)  k =  k , k = 0, 1, ...  > 0.

§ 4. Równania różniczkowe odpowiadające procesowi śmierci i reprodukcji”

Udawajmy, że X(t) to proces śmierci i reprodukcji z cechami i. Niech dla niektórych liczb skończonych A oraz B są nierówności  i  A + Bi, i= 0, 1, ...Ten warunek gwarantuje zakończenie procesu X(t). Jednocześnie zgadzamy się, że górna strzałka po lewej stronie dotyczy każdego stanu (nawet do stanu 0), podczas gdy wskaźnik urodzeń λ może być równy zero (na przykład λ –1 = = 0); z każdego stanu znajduje się dolna strzałka po lewej stronie i intensywność śmierci μ może również wynosić zero (na przykład λ –1 = 0). Rozszerzenie definicji diagramu w ten sposób nie zmienia istoty sprawy, jednak przyda się w dalszym toku rozumowania. Rozważ diagram odpowiadający naszemu procesowi X(t):

Oznacz, jak poprzednio, przez

P k (t) = P(X(t) = k), k = 0,1,…,

prawdopodobieństwo, że w danym momencie t liczba klientów X(t) będzie równe k.

Twierdzenie 1.CharakterystykaprocesX(t), zdefiniowany powyżej, spełnia następujący układ równań różniczkowych:

gdzie k = 0,1,…, i warunki początkowe

Nie jest nie na miejscu wyjaśnić, że pierwsza linijka (kiedy k= 0) układ równań (1) ma postać

Dowód. Oznacz przez P k ( t +Δ) = P(X(t+ Δ) = k).

Wykorzystajmy definicję pochodnej funkcji jednej zmiennej:

.

Rozważ następujące wydarzenia:

A 0 (t, Δ) = (na przedziale [ t, t+Δ] proces X(t) nie wykonał ani jednego skoku);

A 1 (t, Δ) = (na przedziale [ t, t+Δ] proces X(t) wykonał dokładnie jeden skok);

A 2 (t, Δ) = (na przedziale [ t, t+Δ] proces X(t) wykonał dwa lub więcej skoków).

Wtedy oczywiste jest, że

Oznacz dalej przez

; poprzez
trzy wykładnicze zmienne losowe z parametrami
. Niech wszystkie te wielkości będą niezależne. Wtedy prawda Wtedy oczywiste jest, że tryb stacjonarny (stały). P k (t) = P(w systemie w tej chwili) t usytuowany k klientów).

Znajdź rozwiązanie układu równań różniczkowych oraz prawdopodobieństwa stacjonarne.

4.2. Dla procesów śmierci i reprodukcji z zadania 3.3 wypisz równania różniczkowe dotyczące prawdopodobieństw P k (t) = P(w systemie w tej chwili) t usytuowany k klientów).

Znajdź stacjonarne prawdopodobieństwa.

Głównym zadaniem TSMO jest ustalenie zależności między charakterem przepływu aplikacji na wejściu do QS, wydajnością jednego kanału, liczbą kanałów i wydajnością usług.

Jako kryterium wydajności można stosować różne funkcje i wielkości:

• średni czas przestoju systemu;
• średni czas oczekiwania w kolejce;
• prawo rozkładu czasu oczekiwania na żądanie w kolejce;
• średni % wniosków odrzuconych; itp.

Wybór kryterium zależy od rodzaju systemu. Na przykład, dla systemów z awariami główną cechą jest absolut wydajność WOR; mniej ważnymi kryteriami są liczba zajętych kanałów, średni względny czas bezczynności jednego kanału i systemu jako całości. Dla systemów bezstratnych(z nieograniczonym oczekiwaniem) najważniejsze to średni czas bezczynności w kolejce, średnia liczba żądań w kolejce, średni czas przebywania żądań w systemie, współczynnik bezczynności i współczynnik obciążenia systemu obsługującego.

Nowoczesne TSMO to zestaw metod analitycznych do badania wymienionych typów QS. W dalszej części, ze wszystkich dość skomplikowanych i interesujących metod rozwiązywania problemów kolejkowych, zostaną przedstawione metody opisane w klasie procesów Markowa typu „śmierć i reprodukcja”. Wynika to z faktu, że metody te są najczęściej wykorzystywane w praktyce obliczeń inżynierskich.

2. Matematyczne modele przepływów zdarzeń.

2.1. Strumienie regularne i losowe.

Jednym z centralnych pytań organizacji QS jest wyjaśnienie prawidłowości, które rządzą momentami, w których wymagania serwisowe wchodzą do systemu. Rozważ najczęściej używane modele matematyczne strumienie wejściowe.

Definicja: Przepływ wymagań nazywany jest jednorodnym, jeśli spełnia następujące warunki:

1. wszystkie zastosowania przepływu są równe pod względem obsługi;

zamiast wymagań (zdarzeń) przepływu, które z natury mogą być różne, tylko w momencie ich przybycia.

Definicja: Strumień jest nazywany regularnym, jeśli zdarzenia w strumieniu następują po sobie w ściśle określonych odstępach czasu.

Funkcjonować f (x) gęstości rozkładu prawdopodobieństwa zmiennej losowej T - odstęp czasu między zdarzeniami ma postać:

Gdzie - funkcja delta, M t - oczekiwanie matematyczne i M t \u003d T, wariancja Dm = 0 oraz intensywność występowania zdarzeń w przepływie \u003d 1 / M t \u003d 1 / T.

Definicja: Przepływ nazywa się losowy jeśli jego zdarzenia mają miejsce w losowych momentach.

Przepływ losowy można opisać jako losowy wektor, który, jak wiadomo, może być jednoznacznie określony przez prawo rozkładu na dwa sposoby:

Gdzie, zi- wartości Ti(i=1,n),W takim przypadku momenty wystąpienia zdarzeń można obliczyć w następujący sposób

t 1 \u003d t 0 +z1

t 2 \u003d t 1 +z2

………,

gdzie, t 0 - moment początku przepływu.

2.2. Najprostszy przepływ Poissona.

Do rozwiązania dużej liczby problemów aplikacyjnych wystarczy zastosować modele matematyczne przepływów jednorodnych, które spełniają wymagania stacjonarności, bez skutków ubocznych i zwyczajności.

Definicja: Przepływ uważa się za stacjonarny, jeśli prawdopodobieństwo wystąpienia nzdarzenia w przedziale czasu (t,t + T) zależą od ich położenia na osi czasu t.

Definicja: Strumień zdarzeń nazywamy zwykłymi, jeśli prawdopodobieństwo wystąpienia dwóch lub więcej zdarzeń w elementarnym przedziale czasu D tjest nieskończenie małą wartością w porównaniu z prawdopodobieństwem wystąpienia jednego zdarzenia w tym przedziale, tj. w n=2,3,…

Definicja: Strumień wydarzeń nazywa się przepływ bez konsekwencji, jeśli dla dowolnych nienakładających się przedziałów czasowych liczba zdarzeń przypadających na jeden z nich nie zależy od liczby zdarzeń przypadających na drugi.

Definicja: Jeżeli przepływ spełnia wymogi stacjonarności, zwyczajności i bez konsekwencji, nazywa się to najprostszy, przepływ Poissona.

Udowodniono, że dla najprostszego przepływu liczba nzdarzenia przypadające na dowolny przedział zdystrybuowane zgodnie z prawem Poissona:

(1)

Prawdopodobieństwo, że żadne zdarzenie nie wystąpi w przedziale czasu z jest równe:

(2)

wtedy prawdopodobieństwo zdarzenia przeciwnego wynosi:

gdzie z definicji P(T jest funkcją rozkładu prawdopodobieństwa T.Stąd otrzymujemy, że zmienna losowa T ma rozkład zgodnie z prawem wykładniczym:

(3)

parametr nazywa się gęstością strumienia. Ponadto,

Po raz pierwszy opis najprostszego modelu przepływu pojawił się w pracach wybitnych fizyków początku wieku - A. Einsteina i Yu Smoluchowskiego, poświęconych ruchom Browna.

2.3. Własności najprostszego przepływu Poissona.

Istnieją dwie właściwości najprostszego przepływu, które można wykorzystać w rozwiązywaniu praktycznych problemów.

2.3.1. Wprowadzamy ilość a= X. Zgodnie z własnościami rozkładu Poissona dlato zwykle jest normalne. Dlatego dla dużego a, aby obliczyć P(X(a) jest mniejsze lub równe n), gdzie X(a) jest zmienną losową Poissona z oczekiwaniem a, możesz użyć następującej przybliżonej równości:

2.3.2. Kolejna własność najprostszego przepływu jest związana z następującym twierdzeniem:

Twierdzenie: Przy wykładniczym rozkładzie odstępu czasu między wymaganiami T, niezależnie od tego, jak długo trwał, pozostała jego część ma to samo prawo rozkładu.

Dowód: niech T będzie rozłożony zgodnie z prawem wykładniczym: Załóżmy, że przedział a trwa już jakiś czas a< T. Znajdźmy warunkowe prawo rozkładu pozostałej części przedziału T 1 = T-a

Fa(x)=P(T-a x)

Zgodnie z twierdzeniem o mnożeniu prawdopodobieństwa:

P((T>a)(T-a z) P(T-a a)=P(T>a) Fa(z).

Stąd,

jest równoważne zdarzeniu a , dla którego P(a ; z drugiej strony

P(T>a)=1-F(a), czyli

Fa(x)=(F(z+a)-F(a))/(1-F(a))

Stąd biorąc pod uwagę (3):

Ta właściwość ma tylko jeden rodzaj przepływu - najprostszy Poisson.