Волею судеб мне довелось разбираться с организацией многозадачности, точнее псевдо-многозадачности, поскольку задачи делят время на одном ядре процессора. Я уже несколько раз встречала на хабре статьи по данной теме, и мне показалось, что данная тема сообществу интересна, поэтому я позволю себе внести свою скромную лепту в освещение данного вопроса.
Сначала я попытаюсь рассказать о типах многозадачности (кооперативной и вытесняющей). Затем перейду к принципам планирования для вытесняющей многозадачности. Рассказ рассчитан скорее на начинающего читателя, который хочет разобраться, как работает многозадачность на уровне ядра ОС. Но поскольку все будет сопровождаться примерами, которые можно скомпилировать, запустить, и с которыми при желании можно поиграться, то, возможно, статья заинтересует и тех, кто уже знаком с теорией, но никогда не пробовал планировщик “на вкус”. Кому лень читать, может сразу перейти к изучению кода, поскольку код примеров будет взят из нашего проекта.
Ну, и многопоточные котики для привлечения внимания.


 

Введение

Сперва определимся, что означает термин “многозадачность”. Вот определение из русской Википедии:

Многозада́чность (англ. multitasking) — свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов.

Английская дает, на мой взгляд, менее понятное, но более развернутое определение:

In computing, multitasking is a method where multiple tasks, also known as processes, are performed during the same period of time. The tasks share common processing resources, such as a CPU and main memory. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for that task. Multitasking solves the problem by scheduling which task may be the one running at any given time, and when another waiting task gets a turn. The act of reassigning a CPU from one task to another one is called a context switch.

В нем вводится понятие разделение ресурсов (resources sharing) и, собственно, планирование (scheduling). Именно о планировании (в первую очередь, процессорного времени) и пойдет речь в данной статье. В обоих определениях речь идет о планировании процессов, но я буду рассказывать о планировании на основе потоков.

Таким образом, нам необходимо ввести еще одно понятие, назовем его поток исполнения — это набор инструкций с определенным порядком следования, которые выполняет процессор во время работы программы.
Поскольку речь идет о многозадачности, то естественно в системе может быть несколько этих самых вычислительных потоков. Поток, инструкции которого процессор выполняет в данный момент времени, называется активным. Поскольку на одном процессорном ядре может в один момент времени выполняться только одна инструкция, то активным может быть только один вычислительный поток. Процесс выбора активного вычислительного потока называется планированием (scheduling). В свою очередь, модуль, который отвечает за данный выбор принято называть планировщиком (scheduler).

Существует много различных методов планирования. Большинство из них можно отнести к двум основным типам:

• невытесняющие (кооперативные) — планировщик не может забрать время у вычислительного потока, пока тот сам его не отдаст
• вытесняющие — планировщик по истечении кванта времени выбирает следующий активный вычислительный поток, сам вычислительный поток также может отдать предназначенный для него остаток кванта времени

Давайте начнем разбираться с невытесняющего метода планирования, так как его очень просто можно реализовать.
 

Невытесняющий планировщик

Рассматриваемый невытесняющий планировщик очень простой, данный материал дан для начинающих, чтобы было проще разобраться в многозадачности. Тот, кто имеет представление, хотя бы теоретическое, может сразу перейти к разделу “Вытесняющий планировщик”.
 

Простейший невытесняющий планировщик

Представим, что у нас есть несколько задач, достаточно коротких по времени, и мы можем их вызывать поочередно. Задачу оформим как обычную функцию с некоторым набором параметров. Планировщик будет оперировать массивом структур на эти функции. Он будет проходиться по этому массиву и вызывать функции-задачи с заданными параметрами. Функция, выполнив необходимые действия для задачи, вернет управление в основной цикл планировщика.
 

#include <stdio.h>

#define TASK_COUNT 2

struct task {
 void (*func)(void *);
 void *data;
};

static struct task tasks[TASK_COUNT];

static void scheduler(void) {
 int i;
 for (i = 0; i < TASK_COUNT; i++) {
 tasks[i].func(tasks[i].data);
 }
}

static void worker(void *data) {
 printf("%s\n", (char *) data);
}

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++];
}


int main(void) {
 task_create(&worker, "First");
 task_create(&worker, "Second");

 scheduler();

 return 0;
}

 

Результаты вывода:

First
Second
 

График занятости процессора:

 

Невытесняющий планировщик на основе событий

Понятно, что описанный выше пример слишком уж примитивен. Давайте введем еще возможность активировать определенную задачу. Для этого в структуру описания задачи нужно добавить флаг, указывающий на то, активна задача или нет. Конечно, еще понадобится небольшое API для управления активизацией.
 

#include <stdio.h>

#define TASK_COUNT 2

struct task {
 void (*func)(void *);
 void *data;
 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;
}

 

Результаты вывода:

Second activated
First activated
 

График занятости процессора

 

Невытесняющий планировщик на основе очереди сообщений

Проблемы предыдущего метода очевидны: если кто-то захочет два раза активировать некую задачу, пока задача не обработана, то у него это не получится. Информация о второй активации просто потеряется. Эту проблему можно частично решить с помощью очереди сообщений. Добавим вместо флажков массив, в котором хранятся очереди сообщений для каждого потока.
 

#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;
}

 

Результаты работы:

Second activated
Message 2 to first
Message 1 to first
 

График занятости процессора

 

Невытесняющий планировщик с сохранением порядка вызовов

Еще одна проблема у предыдущих примеров в том, что не сохраняется порядок активизации задач. По сути дела, каждой задачи присвоен свой приоритет, это не всегда хорошо. Для решения этой проблемы можно создать одну очередь сообщений и диспетчер, который будет ее разбирать.
 

#include <stdio.h>
#include <stdlib.h>

#define TASK_COUNT 2

struct task {
 void (*func)(void *);
 void *data;
 struct task *next;
};

static struct task *first = NULL, *last = NULL;

static struct task *task_create(void (*func)(void *), void *data) {
 struct task *task;

 task = malloc(sizeof(struct task));
 task->func = func;
 task->data = data;
 task->next = NULL;

 if (last) {
 last->next = task;
 } else {
 first = task;
 }

 last = task;

 return task;
}

static int task_run(struct task *task, void *data) {

 task->func(data);

 free(task);

 return 0;
}

static struct task *task_get_next(void) {
 struct task *task = first;

 if (!first) {
 return task;
 }

 first = first->next;
 if (first == NULL) {
 last = NULL;
 }

 return task;
}

static void scheduler(void) {
 struct task *task;

 while ((task = task_get_next())) {
 task_run(task, task->data);
 }
}

static void worker2(void *data) {
 printf("%s\n", (char *) data);
}

static void worker1(void *data) {
 printf("%s\n", (char *) data);

 task_create(worker2, "Second create");
 task_create(worker2, "Second create again");
}


int main(void) {
 struct task *t1;

 t1 = task_create(&worker1, "First create");

 scheduler();

 return 0;
}

 

Результаты работы:

First create
Second create
Second create again
 

График занятости процессора

Прежде чем перейти к вытесняющему планировщику, хочу добавить, что невытесняющий планировщик используется в реальных системах, поскольку затраты на переключение задач минимальные. Правда этот подход требует большого внимания со стороны программиста, он должен самостоятельно следить за тем, чтобы задачи не зациклились во время исполнения.