EE5903 (RTOS) Assignment 1: Implementing M/M/1 queue using POSIX message queue

Since I spent around 2-4 days in completing this assignment, I thought maybe someone might find this useful in the future. Its not just the code for this problem. I had to learn other features like timers, signals, fork, and (ofcourse) Linux message queue. I had used some of them before but this assignment helped me in understanding them deeper. And I definitely enjoyed doing this assignment.

Disclaimer: Venture in to this blog only if you are interested, else it may be boring.

Problem Definition
Use POSIX Message Queues on Linux
• Producer produces serial numbered messages with exponentially distributed inter-arrival time (avg. 1s)
• Consumer processes messages with an exponentially distributed processing time (avg. 0.8s)
• Producer & consumer log system time and message serial numbers
• Run the system for 300s
Process the logs to compute the following
• Message loss percentage
• Average number of messages in queue
• Average latency (including processing time)
Fraction of time with more than 10 messages in queue

Design
I didn’t do any specific design, but I had some idea on how to develop this step by step. I started by testing the message queue in a sequential program. The function producer puts messages to the queue and consumer takes it in specific intervals. Then I integrated random intervals to make the producers output exponentially distributed using random number generators, then I made it 2 separate processes using fork and later I added signals, etc. The output is stored in to a log file and later that is parsed using another program called log_processor.c. I would like to add the entire development story here, but that would take up the entire space. So, if any of you have any suggestions or queries, drop a comment.

Code
msg_q.c
log_processor.c

Note: I am not able to post code in blog page (so many formatting errors) and I am looking for various options to upload in some site and give the link here. Please let me know if anyone have any suggestions. Also, if anyone want to have a look at the code, please leave a comment.

Individual Code Snippets

• Random numbers

• Fork

fork() is something I always had difficulty in understanding. The idea of same code running in parallel was a bit difficult for me to understand. The key point to remember here is, once the call fork is made, there are 2 instances of the program running and both will run the same code. So, in order to make them both do different things, we have to know which is parent and which is child and that's where the chpid comes in. If the chpid has a value greater than 0, we are in parent process. If it is 0, we are in child. And if it is less than 0, fork failed. simple, right? We can use an if(chpid > 0) condition and call different functions. Also, both are different processes and child or parent doesn't share any memory/variables, the advantage is, you can use for both, disadvantage, have to be careful when you use the variables.

• Signals

• Timers

One important point to remember here is, the function usleep() takes an input in microseconds and in some machines, it will not work for second resolution (for values more than 1000000). It may or may not work for values more than 1 second. Its always better to use values less than 100000 for usleep() and anything above that, split it to 2 and use sleep() and usleep(). The program below, I wrote to test whether it works in my machine. I found it was working, but in the final code, I used both usleep() and sleep().
LOG FILES
I am not putting the entire log files here. Just a small part.

1
302593147
1
2
303410285
0
3
304745777
0
4
305170614
0

Report
Here is the main part of the report I submitted. No fancy stuff, just the facts.

Output of log_processor.out file

Message lost percentage : 0.660066 %
Average Latency : 3.26471 seconds
Average number of messages in queue : 3.06954
Percentage of time with more than 10 msgs in q : 0.331126 %

Explanation

1. Since the producer sends the messages in a blocked state - it waits for the queue to be free, if its full - and also the queue size is almost infinite as compared to the number of messages we send, there is very less chance of a message being lost. However, since we run the simulation for a certain time, at the end of time, there may be some messages which are being processed at the consumer. That is the reason why we see a very small value for the percentage of message loss. If we run the test for a certain number of input messages, there won't be any message loss since the queue won't get full and also since we don't drop a message if the queue is full (blocking call).

2. Average latency is calculated by calculating the individual latencies and taking the average of them.

The implementation is an example of an M/M/1 queuing system.
In theory, the average latency of a message in a system is,
W = 1 / (service rate - arrival rate)
or
W = Waiting Time in Queue + Service Time
W = W.Q + S.T
W = (arrival rate) / (service rate) (service rate - arrival rate) + Service Time (0.8)

Arrival rate = 1/1 = 1 msg/sec
Service rate = 1/0.8 = 1.25 msg/sec

Avg Latency (from theory) = 4sec
Avg Latency (from implementation) = 3.264sec

Since the values are derived by statistical modeling of the system, a small variance will be present. Also, when the test is run for 600 seconds, the values are:

Message lost percentage : 0.34904 %
Average Latency : 4.85368 seconds
Average number of messages in queue : 4.58829
Percentage of time with more than 10 msgs in q : 14.1608 %

The test only will give a value which is approximately the theoretical value.

3. Average number of messages in the queue is calculated by calculating the average of the number of messages in the queue during instants after the producer puts a message in the queue and before consumer takes a message from queue.

Theoretical calculation:
Average number of customers in the system is,
L = arrival rate / (service rate - arrival rate)
L (from theory) = 4
L (from implementation) = 3.06954 ~ 3

In the test with 600sec, the value is around 4.

4. Fraction of time with more than 10 msgs in queue is calculated by finding the number of samples which had a message number greater than 10 and dividing it with the number of samples taken.
Percentage of time with more than 10 msgs in q : 0.331126 %

Details of Test machine
Linux Flavor : Fedora Core 7
Kernel : Ver. 2.6.21-1.3194.fc7
Compiler : gcc Ver. 4.1.2 20070502 (Red Hat 4.1.2-12)
VMware : VMware Server Ver. 2.0.0 Build 116503

Processor : Intel Core 2 T7200 @ 2.00GHz each
RAM : 2.00 GB
Make : Alienware Area-51, m9750

References
http://www.ecst.csuchico.edu/~beej/guide/ipc/mq.html