Generation and Solution of Markov Chains Using MOS

GenerationandSolutionofMarkovChainsUsingMOSESGunterBolchandStefanGreinerMay1994TR-I4-11-94GenerationandSolutionofMarkovChainsUsingMOSESGunterBolchStefanGreinerHermannJungRaimundZimmerUniversityErlangen-NuernbergInstituteformathematicalmachinesanddataprocessingIVMartensstrasse1D{[e-mail]-I4-11-94AbstractInthispapertheMarkovanalyzerMOSES(MOdelling,SpecicationandEvaluationSystem)andthemodeldescriptionlanguageMOSLANG{bothdevelopedattheInstituteforOperatingSystemsattheUniversityofErlangen{Nuernberg{aredescribedusingtwoexamples.Toevaluatetheperformanceofacomputersystemthesystemhastobespecied.InthispaperthemodeldescriptionlanguageMOSLANGisintroducedandappliedtosomeexamples.ThecoreofMOSLANGconsistsofconstructssuitableforthespecicationofthepossiblestatesofthesystemandofRULEconstructswhichmodelthestatetransitions.ThisspecicationmethodismuchmorecompactthanothercomparablemethodsandenablestheusertospecifylargesystemswhenhehasbecomefamiliarwithMOSLANG.TheMarkovanalyzerMOSESsupportstheinputofMOSLANGandsubsequentlycreatestheMarkoviansystemofequationsautomatically.Forsolvingthissystemofequationsvedierentmethodsareprovided.MOSEScalculatesthestateprobabilitiesandderivesfromthemtheperformancemeasureswhicharespeciedusingMOSLANG.MOSEShasbeenusedtosolvemanydierentproblems,amongothersforanalyzingandcomparingdierentmultiprocessorversionsoftheoperatingsystemUNIX.MOSESisimplementedintheprogramminglanguageCandrunsonallUNIXsystems.1IntroductionIntodayssystemsperformanceevaluationisveryimportantbecauseofthegrowingsystemcomplexityandshouldthereforegohandbyhandwiththedevelopementoftherealsystem.Thereforemeasurementontherealsystemisveryoftennotpossibleandoneneedsamodelofthesystem.InthispaperwewillconcentrateonqueueingmodelsbutthedescriptionlanguageMOSLANGisnotonlyrestrictedtothistypeofmodel.Queueingmodelsareverywellsuitedfortheperformanceevaluationofcomputersystemsbecausetheyareeasytounderstandanddescribethesysteminaverycompactmanner.Forthelimitedclassofproductformqueueingnetworks(PFQN’s)thereexistecientalgorithms(e.g.MeanValueAnalysis,SCAT,Convolution)todeterminethedesiredperformancemeasuresofthesystem.ButalotsofqueueingnetworksdonotfulltherequirementsofPFQN’s.Thesenetworksarecallednonproductformqueueingnetworks(NPFQN’s)andareanalyzedbyapproximatealgorithms.Ifthesealgorithmsarenotexactenoughornotapplicabletoaparticularproblematall{thiscanbethecasewhenratesarenonexponentiallydistributedorblockingisinvolved{thenonenormallyusessimulationwithitswellknowndisadvantagesorMarkoviananalysis.Althoughthestatespaceforsimplesystemscanbeverylargeandgrowsexponentiallyinthesystemcomplexity,Markovanalysisbecomesmoreandmoreimportantbecausenewmathematicalmethodsfor1solvinglargeequationsystemsandincreasingcomputationalpowerenablesscientiststogetsteadystateandtransientperformancemeasuresinanacceptabletimecomparedtosimulation.TheproblemwiththismodelsisthatitisnearlyimpossibletoconstructtheMarkovmodelforacomplexsystembyhand.OnepossibilityforsolvingthisproblemisbymodelingthesystemviastochasticPetrinets.Theseoeramuchhighermodelingpowerthanqueueingnetworks.AveryfamoustoolfordealingwithPetrinetsisSPNP(developedatDukeUniversity)whichconvertsthespecicationofaPetrinetintoaMarkovchainandsolvestheunderlyingequationsystem.Inthispaperanothermethodischoosentospecifyasystem.WiththehelpofanewlanguagecalledMOSLANGthestatespaceoftheMarkovchaincanbedescribedinacompactmanner.ThecoreofMOSLANGconsistsofconstructswhichallowthespecicationofthepossiblestatesofthesystemandthetransitionsbetweenthestates.Thisspecicationmethodallowesaverycompactspecicationofthesystemcomparedtoothermethodsandenablestheexperiencedusertospecifylargesystemsveryfast.TheMarkovanalyzerMOSESfacilitatestheinputofMOSLANGandcreatestheMarkoviansystemofequationspQ=0automatically.HerepisthevectorofthestateprobabilitiesandQisthematrixwhichcontainsthetransitionratesbetweenthedierentstatesoftheMarkovchain.Qiscreatedinaparameterizedform.ThereforethesystemcanbeanalyzedwithdierentparameterswithoutchangingtheMarkoviansystemeachtime.Solvingthissystemprovidesthestateprobabilities.Forthispurposevemethodesaresupported.WiththestateprobabilitiesitispossibletocomputeallspeciedmeasuresautomaticallyusingMOSES.InthenexttwosectionswewilldescribethemaincharactristicsofMOSLANGandshowhowtousethistoolbyspecifyingtwosystems{asimplefaulttolerantmultiprocessorsystemandthemodelofafaulttolerantUNIXoperatingsystem.2GenerationandsolutionofMarkovchainsWiththespecicationlanguageMOSLANGitispossibletodescribetheMarkoviansysteminaverycompactmanner.Outofthisdescriptionthestatespaceistgeneratedandtheunderlyingsetofequationsissolved.Thisisdoneinseveralsteps.2.1GeneraldescriptionWiththehelpofthedescriptionlanguageMOSLANGthesystemisdescribed.Outofthisdescriptionthestatediagramisgenerated.Thisstatediagramconsistsofstableandunstablesatates.AstateiscalledunstableiftheMarkovprocessdoesnotstayinthatstatebutchangesimmediatelyinanotherstate.Immediatetransitionsareindicatedbytherate-1.0.To