Mastering Task Scheduling in C: A Comprehensive Step-by-Step Guide

Task scheduling plays a pivotal role not only in operating systems but also in applications that require precise timing and responsiveness, such as robotics and embedded systems. Effective task scheduling is vital for managing resources and optimizing system performance. In this article, we'll delve into a C programming example to gain practical insights into task scheduling. We'll examine how tasks of varying importance and durations are strategically organized, added to a queue, and executed, ensuring that critical tasks meet their deadlines in a well-structured manner.

Crafting Task Scheduling in C Programming

Explore our comprehensive guide on creating a task scheduler simulation in C! This resource offers step-by-step insights into task scheduling principles, making it ideal for students seeking help with their C assignments. Discover how tasks with various priorities and execution times are managed, ordered, and executed efficiently in this practical example. Gain a deeper understanding of the fundamental concepts that drive real-time systems and operating systems, preparing you for more advanced programming challenges.

Includes and Function Pointer

```c # include < stdio.h> # include < stdio.h> # include < unistd.h> # include < stdlib.h> # include < string.h> # include < stdint.h> # include < sys/time.h> ```

This section includes necessary C standard libraries and header files required for the code.

Function Pointer and Linked List Node

```c typedef void (*FunctionPointer)(int, int, struct timeval); typedef struct fcnNode { FunctionPointer fcnPtr; int priority; int execTime; struct timeval start; struct fcnNode *nextNode; } fcnNode; ```

Here, we define a function pointer type `FunctionPointer` that can point to functions taking three arguments (priority, execution time, and start time) and returning `void`. We also define a struct `fcnNode` to represent a node in a linked list. Each node holds a function pointer, priority, execution time, start time, and a pointer to the next node.

Task Functions

```c void T1(int, int, struct timeval); void T2(int, int, struct timeval); void T3(int, int, struct timeval); ```

These are three functions representing tasks T1, T2, and T3. Each function takes priority, execution time, and start time as arguments and performs a task simulation.

Queue-related Functions

```c void addFunPointer(fcnNode **headerNode, FunctionPointer funPtr, int a1, int a2); void runFunctionQueue(fcnNode **headerNode); ```

These functions are used to manage the task queue. `addFunPointer` adds a new node with function pointer, priority, and execution time to the linked list. `runFunctionQueue` runs tasks from the linked list in priority order.

`main` Function

```c int main() { // ... } ```

The `main` function is the entry point of the program. It initializes variables, sets priorities for tasks, generates random values, orders the tasks, inserts them into the queue, and runs them.

Detailed Block Discussion

Variable Declarations

```c struct timeval start; int iter, i, j, sel; int tsk, tasks[3], sorted[3], prio[3]; FunctionPointer taskPtrs[3] = {&T1, &T2, &T3}; int execTimes[3] = {15, 10, 25}; fcnNode *headerNode = NULL; ```

• `start`: A `struct timeval` variable to store time information.
• Various integer variables for iteration control and task ordering.
• `tsk`: Temporary variable to hold a task during ordering.
• `tasks`: An array to hold task indices.
• `sorted`: An array to store task indices after sorting.
• `prio`: An array to store priorities for the tasks.
• `taskPtrs`: An array of function pointers pointing to the task functions.
• `execTimes`: An array to store execution times for the tasks.
• `headerNode`: A pointer to the head of the linked list representing the task queue.

Task Priorities

```c prio[1] = 30; prio[2] = 20; prio[0] = 10; ```

Here, task priorities are set for T1, T2, and T3. The priorities determine the order in which tasks will be executed.

Random Seed

```c gettimeofday(&start, NULL); srand(start.tv_usec); ```

This code obtains the current time and uses it to seed the random number generator.

Main Loop

```c for (iter = 0; iter < 40; iter++) { printf("Cycle %d\n", iter); for (i = 0; i < 3; i++) tasks[i] = i; } ```

This loop simulates 40 cycles of task scheduling and execution.

Task Ordering

```c // If only one task is left, use it as the last task if (i == 1) sorted[2] = tasks[0]; else { // Select a task at random sel = rand() % i; // Remove it from the task array tsk = tasks[sel]; for (j = sel; j < i - 1; j++) tasks[j] = tasks[j + 1]; // Save the selected task in the randomly sorted array sorted[3 - i] = tsk; } } ```

This code initializes the `tasks` array with the indices of the tasks (0, 1, and 2) and then randomly orders them using the Fisher-Yates shuffle algorithm.

Insertion into Queue

```c headerNode = NULL; for (i = 0; i < 3; i++) addFunPointer(&headerNode, taskPtrs[sorted[i]], prio[sorted[i]], execTimes[sorted[i]]); ```

This code sets the `headerNode` to `NULL` and then inserts tasks into the queue according to their sorted order, using the `addFunPointer` function.

Record Start Times

```c gettimeofday(&start, NULL); for (fcnNode *currentNode = headerNode; currentNode != NULL; currentNode = currentNode->nextNode) currentNode->start = start; ```

This code records the start time for each task in the linked list by iterating through the list and updating the `start` field of each node.

Execution of Tasks

```c runFunctionQueue(&headerNode); ```

This code runs the tasks in the queue using the `runFunctionQueue` function. Each task is executed in priority order.

Task Functions

```c void T1(int priority, int execTime, struct timeval start) { unsigned deadline = 60; struct timeval tv; // Print a message indicating the start of Task 1 printf("Task 1 starting ... "); // Sleep for the specified execution time (in milliseconds) usleep(execTime * 1000); // Get the current time gettimeofday(&tv, NULL); // Calculate the time taken for execution in milliseconds double time_taken = (tv.tv_sec - start.tv_sec) * 1000 + (tv.tv_usec - start.tv_usec) / 1000; // Check if the task met its deadline or exceeded it if (time_taken > deadline) printf("deadline exceeded\n"); else printf("deadline met!\n"); } ``

These functions represent the tasks. They perform a simulation, including sleeping for the specified execution time and checking if the deadline is met.

`addFunPointer` Function

```c void addFunPointer(fcnNode **headerNode, FunctionPointer funPtr, int a1, int a2) { // Create a new node for the task fcnNode *node = malloc(sizeof(fcnNode)); fcnNode *currentNode, *prevNode; // Fill in the fields of the new node node->fcnPtr = funPtr; node->priority = a1; node->execTime = a2; node->nextNode = NULL; // If it's the first node, set it as the header if (*headerNode == NULL) *headerNode = node; else { currentNode = *headerNode; prevNode = NULL; // Find the position with smaller priority to insert the new node while (currentNode != NULL && currentNode->priority >= a1) { prevNode = currentNode; currentNode = currentNode->nextNode; } // Insert the new node node->nextNode = currentNode; if (prevNode == NULL) *headerNode = node; else prevNode->nextNode = node; } } ```

This function adds a new node to the linked list representing the task queue. It inserts the node in priority order.

`runFunctionQueue` Function

```c void runFunctionQueue(fcnNode **headerNode) { fcnNode *currentNode = *headerNode, *prevNode; // Traverse all nodes in the task queue while (currentNode != NULL) { // Get the function pointer for the current task FunctionPointer fun = currentNode->fcnPtr; // Execute the task function with its priority, execution time, and start time fun(currentNode->priority, currentNode->execTime, currentNode->start); // Save the current node as the previous node prevNode = currentNode; // Move to the next node in the queue currentNode = currentNode->nextNode; // Free the previous node to release memory free(prevNode); } } ```

This function runs tasks from the linked list in priority order. It iterates through the list, executes each task, and frees the memory of the completed tasks.

Conclusion

In conclusion, this code offers valuable hands-on experience in task scheduling, a fundamental concept in real-time systems and operating systems. By analyzing this example, you can gain a deeper understanding of how task priorities impact execution order and how careful scheduling can ensure that critical tasks consistently meet their deadlines. Exploring such practical implementations can be instrumental in building more robust and responsive software systems, making it a valuable resource for both learning and development projects.