面试题：C语言实现实时操作系统任务调度的时间管理

Question

实时操作系统的任务调度依赖精准的时间管理。请描述如何用C语言实现一个时间片轮转调度算法，并且能处理任务的动态优先级变化。要求详细说明数据结构的设计，以及如何在不同任务的上下文切换过程中准确维护时间信息，确保每个任务都能按照预定的时间片执行，并且能响应优先级的改变及时调整调度顺序。

Answer 1

数据结构设计

1. 任务控制块（TCB）：

   typedef struct TaskControlBlock {
       int taskId;
       int priority;
       int timeSlice;
       int remainingTime;
       void (*taskFunction)();
       struct TaskControlBlock *next;
   } TCB;
   

   • taskId：任务的唯一标识符。
   • priority：任务的优先级，数值越大优先级越高。
   • timeSlice：任务分配的时间片。
   • remainingTime：任务剩余的时间片。
   • taskFunction：任务对应的函数指针。
   • next：指向下一个任务控制块的指针，用于链表结构。
2. 就绪队列：使用链表来管理处于就绪状态的任务。

   TCB *readyQueueHead = NULL;
   TCB *readyQueueTail = NULL;
   

时间片轮转调度算法实现

1. 添加任务到就绪队列：

   void addTaskToQueue(int id, int prio, int slice, void (*func)()) {
       TCB *newTask = (TCB *)malloc(sizeof(TCB));
       newTask->taskId = id;
       newTask->priority = prio;
       newTask->timeSlice = slice;
       newTask->remainingTime = slice;
       newTask->taskFunction = func;
       newTask->next = NULL;
       if (readyQueueHead == NULL) {
           readyQueueHead = newTask;
           readyQueueTail = newTask;
       } else {
           readyQueueTail->next = newTask;
           readyQueueTail = newTask;
       }
   }
   

2. 调度函数：

   void scheduler() {
       while (readyQueueHead != NULL) {
           TCB *currentTask = readyQueueHead;
           // 执行任务直到时间片用完或任务结束
           while (currentTask->remainingTime > 0) {
               currentTask->taskFunction();
               currentTask->remainingTime--;
           }
           // 任务时间片用完，重置时间片
           currentTask->remainingTime = currentTask->timeSlice;
           // 将任务移到队列尾部
           if (readyQueueHead == readyQueueTail) {
               readyQueueHead = NULL;
               readyQueueTail = NULL;
           } else {
               readyQueueHead = currentTask->next;
               readyQueueTail->next = currentTask;
               readyQueueTail = currentTask;
               readyQueueTail->next = NULL;
           }
           // 检查并调整优先级
           TCB *prev = NULL;
           TCB *curr = readyQueueHead;
           while (curr != NULL && curr->priority <= currentTask->priority) {
               prev = curr;
               curr = curr->next;
           }
           if (prev == NULL) {
               currentTask->next = readyQueueHead;
               readyQueueHead = currentTask;
           } else {
               prev->next = currentTask;
               currentTask->next = curr;
           }
       }
   }
   

上下文切换与时间信息维护

1. 上下文切换：在实际的操作系统中，上下文切换涉及保存和恢复CPU寄存器等操作。在C语言模拟中，当调度函数选择新任务执行时，即发生了上下文切换。
   • 对于每个任务，当时间片用完，任务被移到就绪队列尾部，这期间没有丢失时间信息，因为每次时间片用完都重置了remainingTime。
2. 优先级改变处理：
   • 在调度函数中，当一个任务执行完它的时间片后，将其重新插入到就绪队列合适位置，以反映其优先级。通过遍历就绪队列，找到合适的插入位置，确保高优先级任务在队列前面，从而能及时被调度执行。

示例任务函数

void task1() {
    // 实际任务代码
    printf("Task 1 is running.\n");
}

主函数调用示例

int main() {
    addTaskToQueue(1, 3, 5, task1);
    // 添加更多任务
    scheduler();
    return 0;
}

以上代码通过设计合适的数据结构和调度算法，实现了时间片轮转调度并能处理任务的动态优先级变化，同时在上下文切换过程中维护了准确的时间信息。实际应用中，还需考虑中断处理、资源管理等更多操作系统相关的复杂因素。