(one
maze of 2001)ReTMiK - the Real-Time Micro-mouse Kernel
(Hey! Malta do Micro-Rato 2004 - Vejam aqui o novo PicMiK para os ratos baseados no PIC16F876)
This webpage has been promised for years... Here it is, in a minimal configuration ;-). As people say, better late than never (which, curiously, is just the opposite of what real-time systems are about!!!)
Note: This webpage is in english to allow this experience (which is no big deal but I enjoyed it!) to reach a larger audience. If time permits, which probably means many years(!), I'll translate it into portuguese. Feel free to use whatever is available below but keep a reference to its source ;-).
What is ReTMiK about? (a bit of history)
ReTMiK was designed by me (in my old days!) to help students competing in the UA Micro-Rato (micro-mouse) contest. This has been running annually since Dec 1995 (actually there was no 96 edition, the 2nd one was in Mar 1997). It is still running and despite being created with our students (DET) in mind it soon became a national event that gathers robotics enthusiasts from all over the country.
In that contest, teams of 2 or 3 students have to build and program a small autonomous mobile robot capable of finding its way in a maze, running together with other 2 contesting robots. The target is signaled by an IR beacon. In it's current version, the contest rules also request the robot to come back to the starting position without any aid.
(one
maze of 2001)
The robots typically have to exhibit several basic behaviors which have different timing requirements, from a relatively fast obstacle avoidance and wall following to a medium rate beacon following and a slow rate battery check. Moreover, the robots need a relatively accurate notion of time because they must stop by themselves before the 4 minutes time limit.
Nothing more natural, I recon :), than using a multi-tasking kernel to sustain the robot behaviors, preferrably a real-time kernel to allow precise timing and accurate handling of the multi-rate tasks. Thus, in late 1997, after the 2nd ed., I decided to do such a kernel and make it available to the contestants on the platform that was more popular at the time, the Kit188 board (a minimal system based on the 80C188).
(the
Kit188 board)
One of the challenges was that students were very much electronics oriented and had never heard of real-time kernels before. Actually, their contact with small multi-tasking kernels for control applications was minimal if any! Therefore, the kernel had to be easy to use. It also had to be small, not only to fit in the memory (32KB RAM) and still leave enough room for more or less complex applications but also to avoiding increasing the code download time, which is always a pain when developing programs for small embedded platforms.
The options taken to design the kernel were oriented towards simplicity of writing and of using and minimal services with hooks for later improvements. Within a couple of weeks the heart was done and with some more touches, the kernel was ready for distribution by the end ot 97, just in time for the 1998 edition.
No particular publicity was done. The kernel together with a sample application, a short description of the API, and a makefile was mafe available in the contest website, together with other SW tools and info. Surprinsingly (for me!), 4 teams used it and a couple more tried to but gave up. Among 23 teams that showed up, the winner (Bulldozer) and the 3rd (Herbie) were using ReTMiK ! Not bad for a start.
(Bulldozer-v98)
(Herbie)
Also in 1998, ReTMiK was used to control the robot RUA-v3 that was developed by an UA students team to participate in a french competition. It was the largest robot controlled with ReTMiK, 18Kg, 2 powerful DC motors, it had to track a line with varying color with respect to the background, follow a beacon in certain parts of the path and catch and select billiard balls of different colors, placed in the way. Sounds more than what it was... All of it was done with 6 tasks. As a curiosity, the less critical one, for ball selection, was missing deadlines now and then, but the respective subsystem always worked ok!
The rest of the story is not particularly interesting. in 1999 it was used by 4 teams again, in 2000 by 2 teams and from then on, only by the robot Bulldozer that participated every edition from 1998 to 2003, won the contest for 2 times and was always in the first 4. A good reason for this abandon was the introduction of more efficient platforms based on other microcontrollers, my lack of time for porting it, and lack of publicity. Looking back, it was obviously worth and fun doing ReTMiK. Those that used it enjoyed the simplicity of setting up periodic behaviors. And, you know, there's nothing like doing one to learn about many crucial issues from preemption to reentrancy, sync and communication mechanisms, time management, memory management, etc... At this moment, it is also a good teaching aid, in my real-time systems course.
Technical info
ReTMiK is a minimal real-time kernel that spawns C functions into independent tasks. It was fully written in C (Turbo C 2.0) for an 80C188-based minimal platform, with 64KB EPROM (containing a monitor) plus 32KB of RAM, bus expansion and an USART. This kernel version (ReTMiKv1) includes task creation and periodic triggering, time management and dynamic memory management. No mutexes are supported, critical regions need interrupt disabling. Communication among tasks is carried out via global variables. Most of the kernel, as well as common tasks, are preemptible. The tasks' code is also reentrant and tasks may self-suspend. The total footprint is lower than 2.7KB for 6 tasks.
From the real-time point of view, it uses Rate-Monotonic scheduling. It is easy to change the scheduler to any other criterion but requires recompiling the kernel. The time management is carried out by means of a tick timer. For the 188 platform, which has a 10MHz crystal, the tick should be higher than 2ms, but 10ms is recommended for a worst-case overhead with 6 tasks close to 10%. All time attributes of tasks are integer multiples of the tick.
A more complete version (ReTMiK v2.0), has been developed by students Bruno Gravato and Bruno Pereira in my real-time systems course in 2003. This version includes several new features such as task groups (and all group management functions), two scheduling algorithms (Deadline-Monotonic and Earliest-Deadline First), preemption inhibition for access to critical regions without disabling interrupts, and dynamic task creation and deletion.
There is also an elementary PC-based version (ReTMiK-PC) that runs from DOS or Windows(DOS window). Check below.
Documentation
