Semaphores are extremely useful to any OS. We will add them to TinyOS so that you can see how they are implemented.
Here’s a quick list of the changes we need to make to TinyOS to support semaphores.
Using lists will be much flexible. They allowing us to add and remove taskblocks as needed we can move tasks back and forth between a free list, run list, and wait lists. We will use the array of task block to allocate the blocks statically but we will manage them using three types of lists.
The free list will hold all the task blocks at first. Then when the user calls CreateTask we will take one block from the free list, initialize it, and added it to the runlist.
We’ll add next and previous pointers the TaskBlock so we can keep them in lists.
typedef struct _TaskBlock
{
int stackPointer; // Task's stack pointer. Where the context is saved.
Int32U id;
int delayCount; // Delay count. Task is delayed if count > 0.
struct _TaskBlock *next;
struct _TaskBlock *previous;
} TaskBlock;
We will use event blocks to hold our semaphores and manage the list of tasks waiting to acquire the semaphore.
typedef struct _EventBlock
{
int count;
TaskBlock* waitListHead; // First task in wait list
TaskBlock* waitListTail; // Last task in wait list
struct _EventBlock *next; // Next event block for use in free list
} EventBlock;
We need some globals to keep track of the list of task blocks and event blocks. The pointer taskBlockFreeList will point to the list of all the free task blocks. The pointer eventBlockFreeList will point to the list of all the free event blocks. The runList will hold the list of all runnable tasks.
TaskBlock* runList;
TaskBlock* taskBlockFreeList;
EventBlock* eventBlockFreeList;
We’ll initialize the block lists in the InitOS function. We do this by going through the arrays we used to allocate the blocks and add each block as we go to the appropriate list.
After we have set up the task block and event block free lists we’ll go ahead and create the idle task. That way the user does not have to do it and we can be sure it has been created.
void OSInit(void)
{
OSStarted = FALSE;
runList = NULL;
nextTask = 0;
//
// Add all the TaskBlocks to the task block free list
//
taskBlockFreeList = &taskBlocks[0];
struct _TaskBlock* currentTB = taskBlockFreeList;
currentTB->previous = NULL;
for(int i = 1; i < NUMBER_OF_TASKS; i++)
{
currentTB->next = &taskBlocks[i];
taskBlocks[i].previous = currentTB;
currentTB = &taskBlocks[i];
}
currentTB->next = NULL;
//
// Add all the EventBlocks to the event block free list
//
eventBlockFreeList = &eventBlocks[0];
EventBlock* currentEB = eventBlockFreeList;
for(int i = 1; i < NUMBER_OF_TASKS; i++)
{
currentEB->waitListHead = 0;
currentEB->waitListTail = 0;
currentEB->next = &eventBlocks[i];
currentEB = &eventBlocks[i];
}
currentEB->next = NULL;
// Create the idle task
IDLE_TASK = OSCreateTask(0, stackIdle, OSIdleTask);
}
We have to change the way CreateTask works since now the task blocks are manage with lists. The first thing to do is check the list of free task block and pop one off if there are any free blocks.
Once we have a task block we initialize it the task’s data. Then we push it onto the runlist.
If we’re out of task blocks then we have a problem so we just bail and call OSError which will print the error message and stop the OS.
TaskBlock* OSCreateTask(int id, int* stack, void* task_address)
{
if (taskBlockFreeList != 0)
{
// Take a task block from the free list and initialize it
TaskBlock* newTask = taskBlockFreeList;
taskBlockFreeList = newTask->next;
// Initialize the task data
newTask->stackPointer = InitializeStack(stack, task_address);
newTask->delayCount = 0;
newTask->id = id;
// Push the next task to the front of the run list
newTask->next = runList;
newTask->previous = 0;
if (runList != NULL)
{
runList->previous = newTask;
}
runList = newTask;
return newTask;
}
else
{
OSError("CreateTask can't create new task. No more free task blocks.\n");
return 0;
}
}
Next is to make a small change to the scheduler so that it will use the run list instead of the array of tasks. With this change the OS should work and behave the same as when we used an array for the task blocks.
void _OSScheduler(void)
{
CPU_SR cpu_sr = 0;
ENTER_CRITICAL();
//printString("Scheduler\n");
// Save the current stack pointer for the current task.
currentTask->stackPointer = currentSP;
// Start with the nextTask
TaskBlock* blockPtr = nextTask;
// Loop through the run list of task blocks to find the next task to run
while(1)
{
// If we are at the end then start over
if (blockPtr == 0)
{
blockPtr = runList;
}
// If the task is not the idle task and is not delayed then
// it is runnable. We have found our task and can stop looking.
if (blockPtr != IDLE_TASK && blockPtr->delayCount == 0)
{
break;
}
// Move to the next task in the list
blockPtr = blockPtr->next;
// If we loop around back to where we started and have not found
// a runnable task then stop looking and run the idle task.
if (blockPtr == nextTask)
{
blockPtr = IDLE_TASK;
break;
}
}
// Set current task
currentTask = blockPtr;
currentSP = currentTask->stackPointer;
// Set next task so we will know late even if the currentTask
// gets block and moves to a wait list.
nextTask = currentTask->next;
EXIT_CRITICAL();
}
We will need several helper functions for working with the different lists.
Removes the current task from the runList and return it.
TaskBlock* _OSRemoveCurrentTaskFromRunList(void)
{
TaskBlock* task = currentTask;
if (runList == task)
{
runList = task->next;
}
if (task->previous != 0)
{
task->previous->next = task->next;
}
if (task->next != 0)
{
task->next->previous = task->previous;
}
return task;
}
Adds a task to the front of the runList.
void _OSAddTaskToRunList(TaskBlock* task)
{
task->next = runList;
task->previous = 0;
// Assertion: runList always has at least one task, the idle task.
runList->previous = task;
runList = task;
}
Adds a task to the tail of an event’s wait list.
void _OSAddTaskToEventWaitList(EventBlock* eventBlock, TaskBlock* task)
{
task->next = 0;
task->previous = 0;
if (eventBlock->waitListHead == 0)
{
eventBlock->waitListHead = task;
eventBlock->waitListTail = task;
}
else
{
eventBlock->waitListTail->next = task;
eventBlock->waitListTail = task;
}
}
Push free eventBlock on to the EventBlock free list
void _OSAddEventBlockToFreeList(EventBlock* eventBlock)
{
eventBlock->next = eventBlockFreeList;
eventBlockFreeList = eventBlock;
}