Wiki

Clone wiki

roseline / GO-RealTime

#GO-RealTime: A Lightweight Multiprocessor Real-Time Programming Framework#

##Architecture##

The system model of GO-RealTime consists of three objects: worker, goroutine and task, as shown in Figure 1. A worker is a thread created by GO RealTime. Because thread and processor are invisible in original GO, GO-RealTime uses 'worker' to describe the physical resource. It can control its running budget on processor through resource APIs, using Linux RT thread schedulers such as Constant Bandwidth Server (CBS), FIFO and Round-Robin (RR) schedulers. If a worker is not set to any Linux RT scheduler, the thread is non-RT and scheduled by Linux Completely Fair Scheduler (CFS). A GO-RealTime program creates a group of workers. The number Nworker is usually equal to the number of cores Ncore to maximize parallelism.

Goroutine is unit of concurrency in Go RealTime. A RT goroutine is created by announcing SetRT (task id, new worker or not) before go. The integer argument task id associates the goroutine with a task. The boolean argument new worker or not indicates whether to create a new thread to run this RT goroutine. A group of workers shares some runnable queues of goroutines. N queue , the number of queues, is decided by many factors, such as task features, scheduling algorithms and system overhead. The scheduling algorithm is global if Nqueue=1, partitioned if Nqueue=Nworker and clustered if Nqueue is in between. Priority queues are used to sort goroutines by a key. EDF uses deadline as key, LLF uses laxity, and typical non-RT scheduler uses running time related key for fairness. Go RealTime implement only RT scheduler. When a worker become idle, it fetches the first goroutine in the runnable queue. The scheduler is preemptive: if a goroutine g0 becomes runnable and its priority is higher than a running one g1, the scheduler switches off g1 and let g0 run.

Task is the object to describe a program (serial or parallel) with RT requirement. It has a member TimingSpec indicating starting time tstart , running budget trun, deadline tddl and period tp. tstart is an absolute time. t run is a duration. tddl and tp are relative time. The utilization of a task is calculated by μtask = trun/tp. μ may be larger than 1 for parallel task. A serial task is trivially executed by a goroutine. A parallel task is decomposed into serials sub-tasks described by DAG model, executed by a group of goroutines. The number of goroutines Ngo is an adjustable parameter controlled by scheduler. A subtask is runnbale if all its predecessors are done. Runnable sub-tasks are stored in a pool protected by a spin lock. When a goroutine is idle, it fetches a sub-task to execute in the pool of its associated task. Considering the deterministic dependency of all sub-tasks, no preemption happens among sub-tasks. Therefore they are implemented simply as function calls. Different tasks are executed by different group of goroutines, thus they are able to preempt each other.

system_model.png

Figure 1. System Model of Go RealTime. Worker is the abstraction of thread with a processor resource reservation. It is scheduled using Linux scheduler. Goroutines are sorted in a few runnable queues. Workers fetch the head goroutine in queue to execute. A parallel task is decomposed into DAG of sub-tasks. Goroutines fetch sub-task from a runnable pool to execute them.

Updated