简介

当多个任务需要在一个CPU(单个核心)上面运行时，这时就需要多任务的管理系统了。表面上多任务是同时在共享一个CPU，实际上是分时切换。每个任务控制CPU一段时间。

1-操作系统内核中的多任务管理 - 图1
按照上面这一张图，我们可以看到有四个任务(线程)，同一时间只有一个任务在运行（这里是假设只有单个CPU单核）。那么什么时间运行哪一个任务，这就需要调度算法了。大致可以分为两种类型

协作调度—调度程序在分配给它自己之前，不会占用计算线程的时间。
preemptive —时间片期满后，调度程序选择下一个活动线程。该线程还可以放弃其余的时间片。

下面我们来简单实现一个调度算法。

协作调度

list1.c

#include <stdio.h>
#include <unistd.h>
#define TASK_COUNT 7
struct task {
  void (*func)(void *);
  void *data;
  int index;
};
static struct task tasks[TASK_COUNT];
static void scheduler(void) {
  int i;
  for (i = 0; i < TASK_COUNT; i++) {
    tasks[i].func(&tasks[i]);
  }
}
static void worker(void *data) {
  struct task *self = data;
  printf("data is %s,idnex == %d\n", (char *)self->data, self->index);
}
static struct task *task_create(void (*func)(void *), void *data) {
  static int i = 0;
  tasks[i].func = func;
  tasks[i].data = data;
  tasks[i].index = i;
  return &tasks[i++];
}
int main(void) {
  for (int i = 0; i < TASK_COUNT; i++) {
    task_create(&worker, "test");
  }
  for (;;) {
    scheduler();
    sleep(1);
  }
  return 0;
}

1-操作系统内核中的多任务管理 - 图2 可以看这里是按照顺序执行的，这个是太简单了。下面我们给这个增加一个标志位

list2.c

#include <stdio.h>
#define TASK_COUNT 7
struct task {
  void (*func)(void *);
  void *data;
  int index;
  int activated;
};
static struct task tasks[TASK_COUNT];
struct task_data {
  char *str;
  struct task *next_task;
};
static struct task *task_create(void (*func)(void *), void *data) {
  static int i = 0;
  tasks[i].func = func;
  tasks[i].data = data;
  return &tasks[i++];
}
static int task_activate(struct task *task, void *data) {
  task->data = data;
  task->activated = 1;
  return 0;
}
static int task_run(struct task *task, void *data) {
  task->activated = 0;
  task->func(data);
  return 0;
}
static void scheduler(void) {
  int i;
  int fl = 1;
  while (fl) {
    fl = 0;
    for (i = 0; i < TASK_COUNT; i++) {
      if (tasks[i].activated) {
        fl = 1;
        task_run(&tasks[i], tasks[i].data);
      }
    }
  }
}
static void worker1(void *data) {
   printf("%s\n", (char *)data); 
  }
static void worker2(void *data) {
  struct task_data *task_data;
  task_data = data;
  printf("%s\n", task_data->str);
  task_activate(task_data->next_task, "First activated");
}
int main(void) {
  struct task *t1, *t2;
  struct task_data task_data;
  t1 = task_create(&worker1, "First create");
  t2 = task_create(&worker2, "Second create");
  task_data.next_task = t1;
  task_data.str = "Second activated";
  task_activate(t2, &task_data);
  scheduler();
  return 0;
}

运行的结果

./list2
Second activated
First activated

我们可以观察到，首先执行了t2任务。在t2的任务里面激活了t1任务。然后被执行。不过上面这个只有标志位，显然不太好。我们应该每一个任务都对应一个标志位

list3.c

#include <stdio.h>
#include <stdlib.h>
#define TASK_COUNT 2
struct message {
  void *data;
  struct message *next;
};
struct task {
  void (*func)(void *);
  struct message *first;
};
struct task_data {
  char *str;
  struct task *next_task;
};
static struct task tasks[TASK_COUNT];
static struct task *task_create(void (*func)(void *), void *data) {
  static int i = 0;
  tasks[i].func = func;
  tasks[i].first = NULL;
  return &tasks[i++];
}
static int task_activate(struct task *task, void *data) {
  struct message *msg;
  msg = malloc(sizeof(struct message));
  msg->data = data;
  msg->next = task->first;
  task->first = msg;
  return 0;
}
static int task_run(struct task *task, void *data) {
  struct message *msg = data;
  task->first = msg->next;
  task->func(msg->data);
  free(data);
  return 0;
}
static void scheduler(void) {
  int i;
  int fl = 1;
  struct message *msg;
  while (fl) {
    fl = 0;
    for (i = 0; i < TASK_COUNT; i++) {
      while (tasks[i].first) {
        fl = 1;
        msg = tasks[i].first;
        task_run(&tasks[i], msg);
      }
    }
  }
}
static void worker1(void *data) { printf("%s\n", (char *)data); }
static void worker2(void *data) {
  struct task_data *task_data;
  task_data = data;
  printf("%s\n", task_data->str);
  task_activate(task_data->next_task, "Message 1 to first");
  task_activate(task_data->next_task, "Message 2 to first");
}
int main(void) {
  struct task *t1, *t2;
  struct task_data task_data;
  t1 = task_create(&worker1, "First create");
  t2 = task_create(&worker2, "Second create");
  task_data.next_task = t1;
  task_data.str = "Second activated";
  task_activate(t2, &task_data);
  scheduler();
  return 0;
}

执行结果

./list3.run 
Second activated
Message 2 to first
Message 1 to first

抢占式调度

1-操作系统内核中的多任务管理 - 图3 这就和任务优先级有关了，如果任务1正在执行，但是另外一个需要马上执行的任务2被触发，这时就需要任务2进行抢占。如果需要执行抢占的话，就需要一个调度程序，这个调度程序需要可以执行中断当前正在执行的任务。切换到另外一个任务上面。因此我们需要每一个任务的运行环境的保存备份。比如栈的位置，当前任务所使用的一些临时变量。这些都可以统称为CPU上下文。

CPU上下文结构体

1-操作系统内核中的多任务管理 - 图4 CPU的上下文在程序中被处理为一种数据结构，用于存储处理器寄存器的内部状态。上下文必须允许使处理器进入适当的状态以进行计算线程执行。一个处理器更改为另一个处理器的过程称为上下文切换。Linux 中包含上下文的数据结构为 task_struct。可以参考自己定义一个上下文的结构体。

typedef unsigned int __u32;
/**
arch/arm/include/asm/thread_info.h
*/
struct cpu_context_save {
    __u32    r4;
    __u32    r5;
    __u32    r6;
    __u32    r7;
    __u32    r8;
    __u32    r9;
    __u32    sl;
    __u32    fp;
    __u32    sp;
    __u32    pc;
    __u32    extra[2];        /* Xscale 'acc' register, etc */
};

上下文切换

/***
./arch/xtensa/kernel/entry.S:1699:  
*/
/*切换上下文的宏*/

参考资料

Context Switch Definition