M/G/1 Wachtsysteem met 2 prioriteiten

In deze paragraaf zullen we nog een aspect behandelen dat onder andere in computer systemen, met name bij de processor van een telecommunicatie systeem, veelvuldig toegepast wordt. Het gaat hier om het geven van prioriteit aan bepaalde taken. Het beheerssysteem (operating system) van een processor heeft meestal verschillende wachtrijen, voor elke prioriteit één . Zodra een taak beëindigd is, wordt eerst bij de hoogste prioriteit gekeken of daar nog een taak staat te wachten, daarna naar de lagere prioriteiten.

Men werkt met prioriteiten omdat sommige taken (klanten) meer vertraging kunnen velen dan andere. Verder is het zo dat het geven van prioriteit aan korte taken een gunstig effect heeft op de gemiddelde wachttijd.

Voor wachtsystemen met prioriteiten kunnen we hier niet zelf de resultaten afleiden met een eenvoudig Markov-model. We volstaan daarom met het geven van formules voor de gemiddelde wachttijd. We beperken ons tot een systeem met twee prioriteiten, omdat dat de notatie overzichtelijker maakt. Bovendien kunnen deze resultaten vaak ook toegepast worden in systemen met meer dan twee prioriteiten door respectievelijk alle hogere of alle lagere prioriteiten samen te voegen.

In een systeem met twee prioriteiten is het aankomstproces van klanten van elke prioriteit een Poisson-proces. We gebruiken de volgende notatie:

Voor het nummeren van de prioriteiten gebruiken we de volgende conventie:

De bedieningsduur is voor elke prioriteit een stochastische variabele met zijn eigen kansverdeling. Zo kunnen we ook voor elke prioriteit de bezettingsgraad aangeven.

We definiëren nog twee grootheden die in de uiteindelijke formules van pas komen. Deze zijn:

Hierin is de residutijd voor klanten van prioriteit 1. Dit is de tijd die een willekeurige aankomst van prioriteit 1 nog zou moeten wachten totdat de bediening die aan de gang is voltooid is, gewogen met de kans op wachten. Deze interpretatie van residutijd geldt in het geval dat er alleen klanten van prioriteit 1 zijn. is een som van twee residutijden.

Er zijn twee prioriteitsdisciplines te onderscheiden. De eerste wordt de Head Of Line (HOL TYPE=a) discipline genoemd. Hierbij wordt elke bediening zonder onderbreking voltooid. De tweede is de Preemptive Resume (PR) discipline. In dat geval wordt de bediening van een lagere prioriteit onderbroken bij aankomst van een hogere prioriteit en later weer hervat. Voor de gemiddelde wachttijd gelden de volgende formules:

Head Of Line discipline:

Preemptive Resume:

Het voorbeeld 5.5 liet zien dat een kortere gemiddelde bedieningsduur leidt tot een kortere gemiddelde wachttijd (bij dezelfde of zelfs iets hogere belasting). Toch had Bernard (terecht) bezwaar tegen de conclusie dat dus het opsplitsen van lange pakketten wenselijk was. Er werd geen rekening gehouden met het feit dat een opgesplitst lang pakket vier maal een wachttijd zou kunnen ondervinden en de aanname van een Poisson-aankomstproces, bij optie A, was aanvechtbaar. Daarom stelt Bernard voor om te onderzoeken of het geven van voorrang aan korte pakketten niet tot een vergelijkbaar lage wachttijd leidt.

Gevraagd: Wat is de gemiddelde wachttijd voor berichten indien korte berichten voorrang krijgen?

Uit voorbeeld 5.5 lezen we de volgende gegevens:

Hieruit bepalen we de volgende waarden voor bezettingsgraad per prioriteitsklasse

Voor de residu-tijden vinden we:

Omdat de transmissie van een pakket (van lagere prioriteit) eerst afgemaakt zal worden, voordat een tussentijds aangekomen pakket van hogere prioriteit op de lijn gezet wordt, is hier de HOL TYPE=a prioriteitsdiscipline van toepassing. Invullen in de formules (5.84) levert dan:

De gemiddelde wachttijd wordt verkregen door bovenstaande gemiddelde wachttijden per discipline te wegen met gewichtsfactoren die overeenkomen met het relatieve voorkomen van de twee soorten pakketten. Dan is: