Dacav's corner

ZOMG! Pieces of bytes all around the website!

A scheduler

Actually there's no such a scheduler yet, but the story is someway interesting though. Let's start from the beginning... I'll keep it short.

NxOS

NxOS is a small operating system for Lego Mindstorms developed by David Anderson. I worked on it during my thesis time. I'm not going to talk about it in this page. The point is that NxOS's scheduler works as a simple application supporting a context change mechanism, which emulates a multithreading environment.

Ever since I was working on it, me and my collegues found the lack of this feature pretty annoying. In this very moment (Jan 25, 2k10) I'm working on it as a project for a university exam, so that I'm killing two birds with one stone.

Scheduling mechanism

Have you ever heard about O(1) schedulers? In order to optimize a scheduling algorithm you can try to make task selection as fast as possible.

My poor ARM7 platform does not support the mighty CLZ instruction, therefore I had three alternatives:

• Implement a bitmap system without a dedicate instruction;
• Implement a binary heap system;
• Both.

Well, my choice was Both.

Initially I followed the bitmap approach, which was pretty trivial. By directly using ARM Assembly it can be implemented in an optimized way. This also produces a very short executable binary, but technically speaking its performance evaluation is still O(n) in extraction, since every bit of the binary word must be checked.

On the other hand a Binary Heap implementation is more complicated on the algorithmical point of view, but gives better performances: O(log n) on both insertion and extraction.

What is this page about

Ok, you may probably find smarter pieces of code in the Internet, but here I provide you with a funny ARM Assembly implementation of the heapify algorithm.

This badly packaged tarball comes with:

dacav@mithril$ tree heap
heap
├── arm_heapify
│   ├── heap.c
│   ├── heap.h
│   ├── heapify.S
│   ├── main.c
│   └── Makefile
└── c_heapify
    └── heap.c

2 directories, 6 files
dacav@mithril$ 

• heap/c_heapify/heap.c is an horrible C implementation of the structure, just to show how it works. It doesn't care about checking if the structure is full or empty, and it doesn't provide a freeing mechanism.
• The heap/arm_heapify/ directory contains a copy of the same file (heap.c) purged from part of the functions, which are implemented as assembly routines into heapify.S.

You may use this stuff as example and write a good implementation of the C part, which takes care of corner cases (like vectors size etc) and calls the assembly routines in order to get the heapification algorithm in an optimized way.

Note

This kind of functionality has been inserted in LibDacav.

Licensing

GNU GPL v.3.

This site is consistent with W3C standards. If it doesn't work bad for you. Get a decent browser.
Also CSS won't validate: it seems the validator is still incomplete for what concerns CSS3.