Editing Prefetch input queue (section)

==Performance evaluation based on queuing theory==
It was [[Agner Krarup Erlang|A.K Erlang]] (1878-1929) who first conceived of a queue as a solution to congestion in telephone traffic. Different [[Queueing models|queueing model]]s are proposed in order to approximately simulate the real time queuing systems so that those can be analysed mathematically for different performance specifications.

Queuing models can be represented using [[Kendall's notation]]:

:A1/A2/A3/A4

where:

* A1 is the distribution of time between two arrivals
* A2 is the service time distribution
* A3 is the total number of servers
* A4 is the capacity of system

# '''M/M/1 Model''' (Single Queue Single Server/ [[Markov process|Markovian]]): In this model, elements of queue are served on a first-come, first-served basis. Given the mean arrival and service rates, then actual rates vary around these average values randomly and hence have to be determined using a [[Cumulative distribution function|cumulative probability distribution function]].<ref>{{cite book|last=Hayes|first=John|title=Computer Architecture and Organization|year=1998|publisher=McGraw-Hill|edition=Second}}</ref>
# '''M/M/r Model''': This model is a generalization of the basic M/M/1 model where multiple servers operate in parallel. This kind of model can also model scenarios with impatient users who leave the queue immediately if they are not receiving service. This can also be modeled using a [[Bernoulli process]] having only two states, success and failure. The best example of this model is our regular land-line telephone systems.<ref>{{cite book|last=Feller|first=William|title=An Introduction to Probability theory and its applications|year=1968|publisher=John Wiley and Sons|edition=Second}}</ref>
# '''M/G/1 Model''' (Takacs' finite input Model) :  This model is used to analyze advanced cases. Here the service time distribution is no longer a [[Markov process]]. This model considers the case of more than one failed machine being repaired by single repairman. Service time for any user is going to increase in this case.<ref>{{cite book|last=Papoulis|first=Athanasios|title=Probability, Random Variables and Stochastic Processes|year=2008|publisher=McGraw-Hill|pages=784 to 800|edition=Fourth|author2=S.Unnikrishna Pillai}}</ref>

Generally in applications like prefetch input queue, M/M/1 Model is popularly used because of limited use of queue features. In this model in accordance with microprocessors, the user takes the role of the execution unit and server is the bus interface unit.