SIMPL

Context Switching and IPC Performance Comparison between uClinux and Linux on the ARM9 based Process
By Linux Devices
2005-01-26

Article Rating:starstarstarstarstar / 0

Rate This Article: Add This Article To:
Poor Best


Foreword: This whitepaper presents research comparing uClinux with Linux, on an ARM9 processor, in terms of context switching speeds and IPC (inter-process communication) speed. The research was done by Samsung while developing the Linux-based Miniket multi-function diskless camcorder.

The results may surprise you!


Abstract

uClinux is a derivation of Linux kernel intended for MMU-less processors. It provides a single shared address space for all processes while the Linux kernel provides a separate virtual address space for each process using hardware MMU (memory management unit). In this paper, we implemented Linux and uClinux kernels on the same ARM9 platform and compared the performance. The ARM9 processor features virtually indexed caches and a TLB without address space tag. Therefore Linux should flush entire cache and TLB on each context switch which is very costly. uClinux, however, contents of caches and a TLB are valid even after context- switch because the same address space is shared among all processes. We observed an order of magnitude reduction of the context switching overheads on uClinux. As a result, IPC (Inter Process Communication) performance is also better on uClinux.

1. INTRODUCTION

Context switching is the series of procedures to switch the control of CPU from current process to a certain process. While the context switching, the operating system saves the context of current process and restores the context of the next process which is decided by some certain scheduling policy.

The context switching time of an operating system which supports the virtual address space, vary to the algorithms of cache of the architecture. Cache architecture can be split by the addressing scheme as virtual cache and physical cache.[1] The virtual cache stores the location of a certain context with virtual address and the physical cache stores with physical address. The access time for the virtual cache could be better for the simplicity of comparison with the context of cache which needs no address conversion. However, for context switching, the whole context of the virtual cache must be flushed and invalidated because of the meaningless after the switching. For example, ARM9 architecture has virtual address based cache and after the context switching the whole memory access makes cache miss at every each first access time which makes heavy load.

The uClinux [2] is designed for MMU-less architectures at first. On uClinux, one singular address space is shared by the whole processes which had its own virtual address space while on Linux. It makes difficult to support memory protection and vast address space but the load for context switching and communication can be much smaller while supporting the whole compatibility with Linux API except for fork() which is replaced by vfork() in uClinux.

In this paper, we analyzed the virtual addressing cache architecture of the ARM9 which is mostly used platform for embedded systems, and compared the expense of time of context switching for uClinux and Linux on the same platform.

The cache and TLB architecture is described at the chapter 2 and the implementation issues for uClinux and Linux is described at the chapter 3. The benchmark environment and the program are described at the chapter 4 and the benchmark result is described at the chapter 5. The previous works summarized at the chapter 6.

2. STRUCTURAL ANALYSIS

The structure of the cache and TLB (Translation Look-aside Buffer) of the MMU based ARM processor is as Fig.1. [8]

ARM architecture is designed as the harvard architecture. CPU outputs the virtual address(VA) and if the matching data is in the I(instruction) or D(data) cache return the context by cache-hit. If it is not in the cache, the TLB is used for matching the VA with the physical address(PA) and the cache-line is filled from the memory.


Fig. 1. The Cache and TLB architecture diagram of ARM processor


Fig.2 shows the detailed cache structure of ARM9 processor [6][7]. The "Index" part from the 32bits virtual address which is made by CPU used for indexing of the "Tag" table and if the indexed entry's tag information matches the tag information from the virtual address, the data from cache-line is accessed. In the Fig.2, the cache index and the tag itself are based on the virtual address. Thus, while process context switching time, the whole current cache context and TLB is invalidated if it is set by the WT(Write-Through) cache policy, even need to be flushed into the real memory if WB(Write-Back) cache policy is used.

For flushing the cache, about 1k ~ 18k CPU cycle is needed depend on the cache size and the side operations which is needed to fill-up the cache-line and TLB takes up to about 54k CPU cycle. For 200MHz ARM9 processor, it is about 270µs time, [3] and is a heavy burden for many real-time applications which needs under several tens of µs response delay.


Fig. 2. The detailed cache architecture diagram based on virtual address. (ARM926EJ-S)


3. IMPLEMENTATION

uClinux is the modified Linux kernel for architectures which has a MPU(Memory Protection Unit) only or even no hardware memory management unit. From 2.0.x to 2.4.x, it is independently designed and developed from Linux kernel. However, from Linux 2.6.0 beta test versions, from the m68knommu architecture, it is merged into the mainstream Linux kernel and separation from conventional Linux kernel and uClinux is not valid. Although uClinux supports the singular addressing space for kernel and application processes, except for fork() and memory remapping only, the whole Linux API is fully compatible and used for many of real-world embedded system development for architectures which has no MMU or even it has, if the single space addressing has advantages.

uClinux is available for architecture which has MPU or even MMU. The ARM MMU supports both page-mapping for 1KB, 4KB, 64KB size and section-mapping for 1MB size. Linux uses 4KB paging-mapping for memory management. For uClinux, 1MB section-mapping can be used for simple virtual to physical mapped single address space. To say again, D and I-cache operation and mapping core of MMU still work but paging mapping for uClinux.

In this paper, ARM926EJ-S core based Samsung S3C24A0 processor reference platform is used for Linux and uClinux 2.6.7. [4]

4. EXPERIMENTAL SETUP

4.1 The benchmark programs

lmbench[5] is the well-known benchmark program for performance testing over UNIX related operating systems. In this paper, "lat_ctx," "lat_fifo" and "bw_fifo" is used with some modifications.

The "lat_ctx" is for measuring the requirement time for context switching. Creating "N" processes and series of "N" pipes, it constructs "pipe-ring" which links all the processes. Each process accesses its own "k" KB independent memory and "token" is passed through the next pipe to the neighbor processes, which makes a series of synchronized context switching and measure the cycle delay time.

The "lat_fifo" is for measuring the requirement time for send and receive a token between 2 processes.

The "bw_pipe" is for measuring the bandwidth of "pipe" to send and receive through it.

To be the exactly same code, while the benchmark, we made modifications on fork and pipe to be vfork and name-pipe (FIFO).


Fig. 3. The FIFO structure of the modified "lat_ctx"


Fig. 3 shows the modified FIFO structure for the "lat_ctx." The parent processes creates FIFO which is sorted with the process numbers(PID). When the child processes are created by the vfork, the child processes open the neighbor FIFOs to be ready for the communication. Each of the all the child processes are blocked when it try to read the "n-1" FIFO and to be "sleep" state waiting for the write of the FIFO. If all the child processes are ready for read the FIFOs, the parent process writes a token to the first FIFO. It makes "wake" the first child process and the context switching is occurred, and the process writes the token to the next child process, and so on. This procedure makes the chain reaction to be context switched in series. If the last child process get the CPU control and write to the last FIFO, the blocked parent process who was waiting for the input of the last FIFO is awaken and completes one cycle of the "pipe-ring."

5. EVALUATION

5.1 The benchmark system

The S3C24A0 process which is used for the benchmark test is based on the ARM926EJ-S core and has 16KB D-Cache and 16KB I-Cache separately. The TLB has the capacity to store 64 entries simultaneously, and the I and D entries are not separated and the all of the caches and TLB is based on the virtual address.

The benchmark test is done on the same S3C24A0 platform and the same release version of kernel (2.6.7) for uClinux and Linux. And the benchmark program which is described at the Chapter 4 is used.

5.2 The benchmark result

The results of "lat_fifo" and "bw_pipe" are shown in the Table 1, which reflects the delayed time and the bandwidths of the FIFO.

The result shows that uClinux has 5 times and 2 times better performance than Linux on the delayed time and the bandwidths. This is from the cache operation of the Linux kernel which invalidates and flushes the whole caches for the context switching. In other hand, uClinux shares the one address space for all the processes include the kernel itself, and get the benefit of cache efficiency.

In other words, the difference of the IPC (Inter-Process Communication) performance can make a big performance improvement on the uClinux system applications which needs frequent processes communication.

TABLE 1 -- THE RESULTS OF THE IPC PERFORMANCE OF LINUX AND UCLINUX
Linux uClinux Ratio
lat_fifo(µs) 160.64 31.74 5.06
bw_pipe(MB/s) 12.58 25.55 2.03

lat_fifo measures the delayed time of FIFO, smaller number is better.
bw_pipe measures the bandwidth of FIFO, bigger number is better.



The context switching delayed time is showed in the Fig. 4. The context switching time of uClinux and Linux varies from its own data access size (0KB, 1KB, 16KB) and the number of processes. When the access data size is 0KB, uClinux switches 4.5 times faster for 16 processes and 9.7 times for two processes.

For all cases of Linux settings, the context switching time is almost flat independently with the increase of number of processes. It shows the almost fixed cache miss burden which comes from the invalidation of the whole caches while the context switching. uClinux shows much smaller delayed time for context switching while the number of processes are small and increase depend on the number of processes. This comes from the decrease of the cache hit ratio of I-cache and D-cache, when the number of processes is increased. Especially when the process own data access size grows up to 16KB, the context switching time for both of uClinux and Linux almost same which comes from the hardware cache size of S3C24A0 which has 16KB I and D caches and the benefit from cache set off.


Fig. 4. The context switching time measured by "lat_ctx." is shown. Each process has its own 0KB, 1KB or 16KB data access contents and the number of processes varies. The dot over the line "x" represents the value of Linux and "o" for the value of uClinux.


The magnified graph for own access data size 0KB is shown at Fig. 5. For Linux, all the caches are invalidated and flushed whenever switching the context and the cache-line is filled from the beginning. Thus, almost fixed cache-miss time load is needed irrelative to the number of processes. In uClinux case, the possibility of cache hit occurrence is much stronger. However the delayed time increase while the number of process increase which makes increase the possibility of cache-miss because of the limited hardware cache capacity.


Fig. 5. The context switching time measured by "lat_ctx." Each process has no its own data access storages. (size = 0KB)


The total gage R&R study on the benchmark system shows 0.25% contribution of VarComp and 5.03%SV.

6. RELATED WORK

Although we are not aware of any previous systematic study of the uClinux and Linux performance, many of extensions to operating systems performance improvement was introduced include real-time, sharing domain and overall performance.

In particular, many different real-time scheduling algorithms introduced and have been implemented in the FreeBSD, Linux, or Solaris kernels and so on.[11] And some of different approaches for reducing the OS latency is used by systems, such as RTLinux, RTAI, and KURT and so on.

Another focus on the kernel performance has been on the overall performance optimization issues on general purpose or overall throughput which could be an issue on enterprise servers. [9][10]

The FASS(Fast Address-Space Switching for ARM Linux Kernels) is one of the a few studies on embedded systems.[3] The project aims to utilize some of the features of the Memory Management Unit in the StrongARM architecture to improve the performance of context switches under ARM Linux Kernel, although it is known to be unstable as it should be: TLB sharing does not always work. It is based on using domain tags as address-space identifiers and delaying cache flushes until a clash of mappings is detected. And they implemented TLB entries for shared pages even though the TLBs of the ARM are quite small and a potential bottleneck.

7. CONCLUSION

In this paper, we compared the context switching time and IPC performance of uClinux and Linux on the same hardware platform with ARM9 core, which is the mostly used Linux embedded system platform.

With the series of benchmark programs, uClinux showed much improved performance of context switching delay and IPC than Linux. This comes from the virtual address usage for cache architecture and the virtual address space support of Linux kernel which needs invalidation of the whole caches which makes a fixed amount of cache-miss load whenever switching the contexts of processes. uClinux which supports singular address space boosts the efficiency of cache even if context switching occurs and dramatically reduced the required delay. uClinux showed much better performance on the IPC performance also.

The uClinux will show significant benefits on a sort of applications which needs high context switching rates and significant sharing like IPC as the time critical embedded systems does.

REFERENCES

[1] Steve Furber. "ARM System-on-Chip Architecture". Addison-Wesley, 2000.

[2] uClinux developer forum.

[3] Adam Wiggins et el. "Implementations of Fast Address-Space Switching and TLB Sharing on the StrongARM Processor", in the Proceedings of the 8th Australia-Pacific Computer Systems Architecture Conference, Aizu-Wakmatsu City, Japan, September 2003.

[4] HyokSung Choi. "uClinux/ARM 2.6 Project"

[5] McVoy, L., Staelin, C. "lmbench: Portable tools for performance analysis". In: Proceedings of the 1996 USENIX Technical Conference, San Diego, CA, U.S. (2996)

[6] Samsung S3C24A0 Product Datasheet.

[7] ARM926EJ-S Technical Reference Manual.

[8] ARM Architecture Reference Manual. ARM LTD.

[9] Duc Vianney, Sandra Johnson, Bill Hartner. "Linux Kernel Performance Measurement and Evaluation" LinuxWorld / San Francisco. Aug. 2002.

[10] Sandra K. Johnson, William H. Hartner, William C. Brantley. "Improving Linux kernel performance and scalability". LTC. Jan 2003

[11] Luca Abeni, Ashvin Goel, Charles Krasic, Jim Snow, Jonathan Walpole. "A Measurement-Based Analysis of the Real-Time Performance of Linux". Proceedings of the 8th IEEE Real-Time and Embedded Technology and Applications Symposium, 2002.


http://www.linuxfordevices.com/c/a/Linux-For-Devices-Articles/Context-Switching-and-IPC-Performance-Comparison-between-uClinux-and-Linux-on-the-ARM9-based-Process/

http://www.icanprogram.com/01dr/lesson1/simpl.html



SIMPL Refresher
Course content Enter chat room Send email
to mailing list Check calendar

JUST A REMINDER: for those of you who have not yet received your confirmation that you have been
subscribed to the mailing list please contact us by email immediately.

In memory of Linda. Worldwide Cancer sites here. Canadian Cancer donations here.



Hint:
All of these lessons are designed to be worked on offline. For those of you with dialup Internet access you might find it helpful to print off the page for each lesson and work from the printout.



SIMPL toolbox

What exactly is SIMPL?

SIMPL is really two things.

First of all SIMPL represents a very good paradigm for designing software. It promotes encapsulation of complexity and ready extendability ... both good things in a software package.

SIMPL is also an LGPL'd open source library that you can link to (dynamically or statically) that enables you to write software that readily exchanges Send/Receive/Reply (QNX ) style messages.

OK what does it really do?

It is a library. Once you have it installed you can write your code using a rich (yet simple) set of functions for Interprocess Communication (IPC). These functions include:

name_attach()
name_locate()
Send()
Receive()
Reply()

and a few lesser used ones.

So as you can see the SIMPL library API is very clean indeed.

How does it work?


In SIMPL vocabulary we speak of Linux processes as being of one of two types:

* senders
* receivers

As you can see in the figure above there are several elements associated with a SIMPL message pass.

The first of these is the container for the bytes in the message itself. That is contained within a shared memory area allocated by the sender process. Actually there are two areas: one for the outgoing message and one for the reply message.

To help with process blocking (more on that later) and synchronization a slotID is exchanged on a named pipe or fifo prior to each message pass.

A typical message exchange between a sender and a receiver would go something like this:

1. SIMPL receiver process starts up and does a name_attach() to register its SIMPL name
2. SIMPL receiver then does some initialization and drops into a Receive blocked state by calling the Receive() function
3. SIMPL sender process starts up and does a name_attach() to register its unique SIMPL name
4. sender then does a name_locate() to connect to the receiver's fifo
5. sender composes a message and drops it into the outgoing shared memory area
6. sender places its slotID onto the receiver's fifo and drops into a Send blocked state by calling the Send() function
7. receiver wakes up and retrieves the slotID from the fifo and then connects to the shared memory area and retrieves the actual message contents
8. receiver processes the message and composes a reply which is then placed directly into the sender's reply shared memory area
9. receiver places its slotID onto the sender's fifo and drops back into Receive blocked state by calling the Receive() function
10. sender wakes up and retrieves the reply

Before I lose you all in the details let's illustrate these things by way of some examples.


The first step: getting the SIMPL tools and installing them on your system

Before you begin you will need to decide where your SIMPL source tree will exist and make a couple of environment variables accordingly.

Hint on environment variables:
If you have never heard of environment variables please look them up in your Linux reference material. The two environment variables that SIMPL uses must be set up so as to be always available after a login ... in much the same way as the Linux PATH enviroment variable is. Typically this involves adding some "export" commands into one of the shell initialization files on your system. $HOME/.bash_profile, $HOME/.bashrc, $HOME/.profile or /etc/profile are some examples of shell initialization files.

If you don't know which "dot file" to use for your Linux distribution try the following experiment. Add in an "echo hi" line to one of the "dot" files. Logout and back into your system (if you are a GUI person open a text console window also). If you see your "hi" then that is the file in which to add the export lines below.

You can elect to place your SIMPL source anywhere you please as long as the subdirectory is called "simpl". Suppose you decided to place all the SIMPL source at:

/home/simpl

then you would need to create an environment variable called SIMPL_HOME which pointed to this directory. ie. in your local .bashrc (or other suitable hidden file) you would add the following line:

export SIMPL_HOME=/home/simpl

The SIMPL library will also need to access a various fifos involved in the SIMPL message exchange. You will need to create a directory to hold the inodes for the various fifo's used by the SIMPL environment. Once again you can place this directory anywhere you please ... no requirement to call this subdirectory fifo. Suppose that you elect to place this "fifo" directory at:

/home/simpl/fifo

then you would need to create a second environment variable called FIFO_PATH which points to this directory. ie.

export FIFO_PATH=/home/simpl/fifo

Note:

The SIMPL source tree has been carefully designed not to "pollute" your system. All SIMPL related files will exist under one of these two directories above.

You are now ready to go online and grab the latest version of SIMPL source code from the SIMPL Open Source project website.

main SIMPL home page

or

sourceforge SIMPL site

Note:

The SIMPL project is a dynamic Open Source project and releases are made regularly. It is also quite stable.

It is important that you pickup the latest release to capture all the bug fixes that have been done. When in doubt which version to use the Sourceforge site always only contains the latest release.

Once you have downloaded the latest tarball you need to place it at the subdirectory immediately above the SIMPL_HOME. ie.

cd $SIMPL_HOME
cd ..


then you can undo your tarball by typing

tar -zxvf whateveryourSIMPLtarballnameis

At this point you should have a whole bunch of source code sitting at SIMPL_HOME.


The next step: building the SIMPL libraries

After installing all the source on your system the next step is to build all this source code into the SIMPL libraries.

To do this you will need to:

cd $SIMPL_HOME/scripts
./buildsimpl

This should cause the SIMPL source to completely build and install itself.

Note:

The SIMPL source tree has some Tcl/Tk hooks built into it. If you do not have Tcl/Tk installed on your Linux system you will need to do this now as we will be using Tcl/Tk in a later lesson as our GUI language.



Making sure that the SIMPL tools work

One of the subdirectories under the SIMPL_HOME tree is called benchmarks. Some SIMPL executables were build here. They can be used to "time" the SIMPL message passing on your system.

We will be using them here to verify that you have SIMPL installed and the environment variables correctly defined.

The buildsimpl script should have caused two executables to be built.

* $SIMPL_HOME/benchmarks/bin/receiver
* $SIMPL_HOME/benchmarks/bin/sender

To run this benchmark test you will need to open 2 text consoles on your system and point each to the

$SIMPL_HOME/benchmarks/bin

directory.

On console 1: logged onto $SIMPL_HOME/benchmarks/bin type

receiver -n BOBR

where BOBR - is an arbitrary SIMPL name you have chosen for this receiver.


On console 2: logged onto $SIMPL_HOME/benchmarks/bin type

sender -n BOBS -r BOBR -t 100000 -s 1024

where -n BOBS - is the SIMPL name for the sender
-r BOBR - is SIMPL name used for the receiver above
-t 100000 - means send 100000 messages before displaying timing
-s 1024 - says make each message 1024 bytes in length (same size for replies)

When you hit enter on console 2 the sender locates receiver and then marks the time. It then procedes to send 100000 1k messages to the receiver each time blocking for the same size reply.


If you see seg faults in the above:
This is a clear indication that you do not have your environment variables (in particular FIFO_PATH) defined in such a way that they are set for each login. ie. if you were to type "echo $FIFO_PATH" nothing would show up.

SIMPL uses these two environment variables both at build time (SIMPL_HOME) and at run time (FIFO_PATH) so it is very important that you export both of these environment variables so that they are always set.


When this preset number of messages have been exchanged the sender calculates and reports the total elapsed time in msec.

You have asked your system to do a substantial piece of work here. Depending on your processor type and speed this may take several tens of seconds to complete.

Once you have the number you can easily compute the number of SIMPL messages per second that your system is capable of exchanging.


Congratulations! You have successfully installed SIMPL on your system!

It might be nice to share your benchmark results with the mailing list.

For those of you who are interested in such things SIMPL's benchmarks are within an order of magnitude of QNX on the same hardware. ie. QNX will exchange messages about 10 times faster than SIMPL under Linux. With modern computing hardware the SIMPL message passing speed is more than adequate for most applications, however. Besides SIMPL is Open Source and you can't beat its price point.

Because SIMPL does not use the TCP/IP stack for local message passing it will be significantly faster at passing messages between Linux processes on the same box.


The concept of a software IC

Computer hardware is complex.

So is computer software.

It is instructive to examine how the hardware designs have evolved to handle this complexity.

It wasn't that many years ago when electronic circuits were built up of discrete components (transistors, resistors, capacitors etc.).

As complexity of electronic circuits increased it became impossible for hardware engineers to manage this complexity. Enter the integrated circuit (IC). What this did for the hardware engineer was to take functionality which would have previously been provided by a custom circuit board with discrete components and replace it by a silicon chip with well defined behavior characteristics and pin outs. This innovation is what has allowed the hardware engineers to make the spectacular progress we have witnessed in the past 25 years.

Software never had that equivalent encapsulating technology. Object Oriented Programming (OOP) languages such as C++ or JAVA attempt to attack the software complexity problem at the programming language level. For some classes of problems such as GUI design they have been successful. Unfortunately for whole other classes of problems all they have succeeding in accomplishing is a shift of complexity to another location: namely the source code.

Fortunately, modern multitasking languages provide us with a ready analog to the hardware integrated circuit: namely a process running in a protected mode. All of us have used processes on the Linux box already without giving them much thought. If one of those processes encounters a fatal error it rarely brings down the whole machine. If for some reason we do something that sends one of those processes into a locked state it rarely hangs the whole rest of the machine.

This protection from error propogation is a very desirable feature to have in a software IC.

So the process can act as our container for our complex algorithms in much the same way as the silcon chip inside the plastic case does for the hardware IC.

It wouldn't do us much good, however if we didn't have a simple and flexible way to expose this algorithm to interation from the outside world: ie. the analogy to the pins on the hardwareIC.

Fortunately with SIMPL messaging we have exactly such a tool.

With SIMPL and a basic language such as C we are going to see that we can achieve something remarkably close to a software IC without having to resort to an OOP language and unreadable source code.

First we need to understand a little more about how SIMPL works.

The SIMPL "sandbox"

SIMPL maintains a kind of "phone book" to keep information about all running SIMPL processes.

This "phone book" is kept as a set of special files in the directory you named:

$FIFO_PATH

There are several utilities that come with the SIMPL package for viewing and manipulating this fifo directory.

The first of these is affectionately called "the hammer" by some folks:

cd $FIFO_PATH
rm *

If you are careful when you run the "hammer" it will ensure that your SIMPL sandbox is clean. It will not, however, insure that any rogue processes you had running were terminated properly.

For that you will need to run another pair of utilities before invoking the "hammer".

The first of these utilities is the slot viewer:

$SIMPL_HOME/bin/fcshow

If you run this it will show all the SIMPL names currently registered along with the pid they are associated with.

Try rerunning the benchmark test from lesson #1 and while the timing is taking place, change to another console and run fcshow.

Finally if you have a need to kill a rogue SIMPL process by its SIMPL name then there is a utility called:

$SIMPL_HOME/bin/fcslay

which you use as

fcslay

Once again give this a try by starting up the receiver above and from another console typing

fcslay BOBR

Download the softwareIC code from the SIMPL project

The SIMPL project contains a set of very basic software ICs in the form of a tarball which can be downloaded from the SIMPL website.

Go ahead download this tarball.

You'll want to install it at exactly the same place that you installed the SIMPL toolset. Not to worry, the softwareIC tarball will safely install all its code at:

$SIMPL_HOME/softwareICs


Before we go forward let's make sure that this code all compiles.

cd $SIMPL_HOME/softwareICs
make install



Makefile refresher:
If you need a refresher on Makefiles click here to view an excerpt from the iCanProgram Introduction to Linux Programming course.

If you take a look at the softwareICs directory above you will see several subdirectories. Each of these represents a different softwareIC. You are welcome to read up more on some of the more complex softwareICs such as the agency by perusing the documentation on the SIMPL website.


Copyright of iCanProgram Inc. 2003