Computing Performance of Symmetric Multi-Processing Scheduling

You might have noticed that when you do a transaction in a bank, you usually see a single line being served by 2 or more tellers. You must have perceived that this technique of lining up customers is better than when each teller has its own line. This will lessen the chance of you being stuck for a long time when the guy before you takes a long time to complete transaction.

In computer systems, you can view the customers as tasks to be executed by 2 or more processors. Each processor will pick from a common line, a task that it will execute. In this article, we will analyze the performance of symmetric multiprocessing using continuous markov chain analysis. We will also be using the tool available from www.extremecomputing.org to help us compute the probabilities.

In order to simplify the calculation, let us assume we have 2 tellers and a single queue. Customers arrive at a rate of 2 customers per minute. If a customer arrives and sees that a teller is available, it will go to that teller. If a customer arrives and sees that 2 tellers are available, then the customer has the liberty to pick a teller. In this situation, the customer arrival rate can be seen to be half that of the original arrival rate. When a customer sees that there are 2 customers being served and one customer waiting, that customer will go to another branch. We say that the buffer length of this system is 3.

Markov State Diagram

The next step in the analysis is to draw the markov state diagram of this system. We can represent each state using 3 numbers. The first number is the number of persons waiting to be served. The second number take a value of 1 or 0. A 1 means that teller 1 is serving a customer, a 0 means that teller 1 is idle. The same is true with the third number, which now applies to teller 2. Each teller can service a customer in 20 seconds, which means each of them can process 3 customers per minute.
The state diagram of this system is shown below:

markov_commonline.png

You can see that the arrows from state 000 to 010 or 001 are colored orange. This stands for an arrival rate of 1 customer per minute. You might be wondering why this is half of the 2 customers per minute arrival rate. The reason is because at the initial state, the system can immediately service 2 customers arriving within a minute. This effectively cuts the arrival rate by half. However, when only one teller is available, the system will see the arrival rate to be 2 customers per minute.

Blue arrows stand for 2 customers per minute. Red arrows stand for 3 customers per minute. The state transition table is shown below:

markov_commonlinestate_transition_table.png

Using the extremecomputing.org Continuous Markov Chain solver, we get:

markov_commonlineresult.png

We can compute for the throughput of this system by computing the throughput of each teller and adding them:

\displaystyle U_{\text{Teller 1}} = 1- P000 - P001
\displaystyle =1- (0.509433962264 + 0.169811320755)
\displaystyle = 0.3207547

Multiplying this with the number of customers per minute gives the throughput of teller 1:

\displaystyle X_{\text{Teller 1}} =  0.3207547 \cdot 2
\displaystyle =  0.6415094

Since the system is symmetric, the total throughput is just twice the throughput of teller 1, which is 1.283019 customers per minute.

In the next 2 articles, we are going to compute the performance when

  • Each teller will have its own queue and each customer will choose a line at random
  • Each teller will have its own queue and each customer will chose the shortest line

We will then compare the performance of these three queueing disciplines and see which of them is better in terms of throughput and customer waiting time.

Advertisements

Published by

Bobby Corpus

Is an IT Architect.