========================== Adding Semaphores Part One ========================== Semaphores are extremely useful to any OS. We will add them to TinyOS so that you can see how they are implemented. Outline of changes to TinyOS ============================ Here's a quick list of the changes we need to make to TinyOS to support semaphores. * Add next pointer to TaskBlock for use in implementing the lists * Add EventBlock structure with next pointer * Add pointers to track the run list, free TaskBlocks list and free EventBlocks list * Pre allocate a fixed number of TaskBlocks * Pre allocate a fixed number of EventBlocks * In OSInit add all the tasks blocks to the free task blocks list * In OSInit add all the event blocks to the free event blocks list * In CreateTask, pop a task block off the free list, initialize it, push it on to the run list * Update the scheduler to walk the run list instead of an array. * Add CreateSemphore, Post, and Pend functions Using Lists =========== 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. TaskBlock Change ================ We'll add next and previous pointers the TaskBlock so we can keep them in lists. .. code-block:: c 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; EventBlock ========== We will use event blocks to hold our semaphores and manage the list of tasks waiting to acquire the semaphore. .. code-block:: c 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; Block Lists =========== 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. .. code-block:: c TaskBlock* runList; TaskBlock* taskBlockFreeList; EventBlock* eventBlockFreeList; Initializing Lists ================== 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. .. code-block:: c 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); } Change to CreateTask ==================== 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. .. code-block:: c 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; } } Change to the Scheduler ======================= 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. .. code-block:: c 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(); } List Helper Functions ===================== We will need several helper functions for working with the different lists. Remove Current Task From Run List --------------------------------- Removes the current task from the runList and return it. .. code-block:: c 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; } Add Task To Run List -------------------- Adds a task to the front of the runList. .. code-block:: c 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; } Add Task To Event Wait List --------------------------- Adds a task to the tail of an event's wait list. .. code-block:: c 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; } } Add EventBlock To Free List --------------------------- Push free eventBlock on to the EventBlock free list .. code-block:: c void _OSAddEventBlockToFreeList(EventBlock* eventBlock) { eventBlock->next = eventBlockFreeList; eventBlockFreeList = eventBlock; }