Scheduling

Introduction

In this stage I design a Round Robin scheduling system to design CPU time for the differents tasks.

This task distribution assign a certain time to each task (named Quantum); after that time the schedule algorithm searches another task to assign a new quantum. Also, a task manager is needed; for the moment only exists a task_creation interface.

For a example, you can watch the following link.

Design

For design this Round Robin, we need a data structure that saves a certain state of a task, some logical control for the scheduling process and the capability for change the machine state.

The task struct

A task is defined by the PC register, the SP and the safety-registers (a convention designs x19 to x30 safety registers). Our task struct needs to save this registers in memory with some control and identification information, useful for the scheduling logic.

The scheduling logic

The scheduling logic is called every time a timer interrupt occurs. In this code, we need to update the scheduling data (in our case the Quantum but we can add other variables). After that, we need to control if the current task has run out all the quantum, in that case, we need to search a new task to run and change the execution context

Jumping to a new state - Task switch

For change the context, an assembler entry is needed, because we need to restore the values of all the safety registers and the PC. This entry will be called by the scheduler if a task switch is required.

Implementation

The first step is define a task, that contains the following fields:

typedef struct task{
    struct cpu_context myContext; //Context
    tid tid;                	  //Task IDentifier
    task_info myInfo;             //Some statics
    int quantumLeft;              //Quantum left
    bool preemption_enable;       //True for avoid context switch
    enum state state;             //Actual state of the task (RUN, READY, BLOCKED)
}task;

Once a task is created, we need to create the task. A task is defined by the code/instructions and the arguments/parameters, so the interface:

sys_response init_task(void * fn, void * data);

In addition the task managment, we need some structures and policy for the scheduling process:

• ready Queue : Here the task wait in order to a quantum of CPU.
• next task policy : In this case, the next in the ready queue. The sched_next_rr() search in this queue for the next task to be executed.
• nTask : A counter for design a unique TID to all the new tasks.
• quantumLeft : Remaining quantum for a context switch. In every timer tick, this variable is decremented.
• need replacement : Condition for search the next task. In this case, is the quatum is 0 and the preemption is enabled timerNotify : The timer interrupt routine calls here for execute the schedule logic.

All together

In this point, the OS can run several threads, that share memory (there isn't any restrictions about) and resources (UART). For avoid data-races in the future a synchronization API for lock/unlock resources is needed.