A scheduling mechanism for lock-free operation of a lightweight process library for SMP computers

We have designed and implemented a lightweight process (thread) library called “Lesser Bear” for SMP computers. Lesser Bear has high portability and thread-level parallelism. Lesser Bear executes threads in parallel by creating UNIX processes as virtual processors and a memory mapped file as a huge shared-memory space. To schedule threads in parallel, the shared-memory space has been divided into working spaces for each virtual processor and a ready queue has been distributed. But the preview version of Lesser Bear sometimes requires a lock operation for dequeueing. We therefore proposed a scheduling mechanism that does not require a lock operation. To achieve this, each divided space forms a rotatory topology through the queue, and we use a lock-free algorithm for the queue operation. This mechanism is applied to Lesser Bear and evaluated by experimental results