воскресенье, 18 августа 2013 г.

PhantomEx: Многозадачность. Потоки уровня ядра.

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

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

Наконец переключение потоков удалось реализовать и отладить, используя алгоритм, предложенный парнем с ником phantom-84 с форума http://osdev.ru. Алгоритм этот чрезвычайно прост и элегантен, а  phantom-84 выражается огромная благодарность за помощь в разъяснении его узких моментов.

Как всегда начнем с теории.


1. Многозадачность в однопроцессорной системе


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

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

Всё дело в том, что на деле в каждый момент времени процессор выполняет какую-то одну программу, периодически переключаясь с выполнения одной программы на другую, причем достаточно быстро, так что создается иллюзия одновременной работы программ. Эта операция называется переключением контекста выполнения. Введем так же и другую терминологию, которую будем использовать.

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

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

По тому как инициируется переключение  задач, разделают несколько видов многозадачности

  1. Кооперативная многозадачность - переключение на новую задачу происходит только после того как текущая задача объявит себя готовой отдать управление новой задаче. Главный недостаток такого типа многозадачности - при сбое в работе текущей задачи рушится вся операционная система. Такой тип многозадачности реализовывался в ранних версиях Linux и FreeBSD, в Windows до 3.x включительно, и в Mac OS до версии X.
  2. Вытесняющая многозадачность - переключение задач происходит по истечении отведенного задаче кванта времени, либо по завершении операций ввода/вывода, либо по возникновению событий в аппаратуре компьютера, либо при поступлении сигналов от одной задачи к другой. Процессор может быть переключен таким образом безо всякого пожелания на то программы, в момент выполнения которой происходит переключение. При такой многозадачности возможно прерывание некорректно работающей задачи без ущерба для работы остальной системы. Такой вид многозадачности реализован во всех популярных ОС.
Мы будем реализовывать вытесняющую многозадачность, с переключением задач по прерыванию системного таймера.

Кроме того, в архитектуре x86 начиная с процессора 80286 существовала аппаратная поддержка переключения задач, работавшая через так называемые дескрипторы состояния задач TSS. В 286-м процессоре однако и многозадачность и защищенный режим использовались крайне редко, как из-за кривоватой реализации, так и из-за ориентированности разработчиков ПО на DOS. Широкое распространение защищенный режим получил в ПК на 32-разрядном 386-м процессоре. А вот аппаратной многозадачности не повезло - её никто толком не использовал, так как существенного выигрыша в производительности она не давала, зато затрудняла переносимость операционной системы с платформы на платформу из-за привязки к архитектуре x86. Большинство разработчиков ОС пошли по пути программной реализации многозадачности в своих системах. Это привело к тому что аппаратная многозадачность, в итоге, была убрана из новой архитектуры x86-64 за ненадобностью, с сохранением некоторых вещей для обратной совместимости с 32-разрядной архитектурой.

Мы так же пойдем по пути программной реализации переключения задач.

2. Очередь задач. Структуры процесса и потока


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

Листинг 68. Кольцевой двусвязный список (list.h)

/*------------------------------------------------
 *
 *         Кольцевой список
 *
 *----------------------------------------------*/

#ifndef     LIST_H
#define     LIST_H

#include    "common.h"


/*------------------------------------------------
 *  Определяем типы данных для организации списка
 *----------------------------------------------*/

typedef    struct    _list_item_t    list_item_t;

/*------------------------------------------------
 *  Тип данных реализующий список
 *----------------------------------------------*/

typedef struct
{
    list_item_t*    first; /* Указатель на первый элемент */
    size_t          count; /* Число элементов в списке */
   
} list_t;

/*------------------------------------------------
 *  Тип-элемент списка
 *----------------------------------------------*/

struct _list_item_t
{
    list_item_t*    prev; /* Предыдущий элемент списка */
    list_item_t*    next; /* Следующий элемент списка */
    list_t*         list; /* Список которому принадлежит
                             данный элемент */

};

/* Инициализация списка */
void list_init(list_t* list);
/* Добавление элемента в список */
void list_add(list_t* list, list_item_t* item);
/* Удаление элемента из списка */
void list_remove(list_item_t* item);

#endif

и реализацию

Листинг 69. Реализация функций работы с кольцевым списком (list.c)

#include    "list.h"

/*------------------------------------------------
 * Инициализация списка
 *----------------------------------------------*/

void list_init(list_t* list)
{
    list->first = NULL; /* Первого элемента пока нет */
    list->count = 0;    /* В списке нет элементов */
}

/*------------------------------------------------
 *  Добавить элемент в список
 *----------------------------------------------*/

void list_add(list_t* list, list_item_t* item)
{
    /* Если элемент не принадлежит никакому списку */
    if (item->list == NULL)
    {
       
        /* Если в списке есть первый элемент */
        if (list->first)
        {
            /* Помечаем элемент как принадлежащий данному списку */
            item->list = list;
            /* Следующий за ним элемент - это первый элемент */
            item->next = list->first;
            /* Делаем предыдущим элемент идущий перед первым */
            item->prev = list->first->prev;
            /* Наш новый элемент - следующий
               для идущего перед первым */

            item->prev->next = item;
            /* и предыдущий для следующего за ним */
            item->next->prev = item;
        }
        else /* Если список пуст - новый элемент первый в списке */
        {
            item->list = list;  /* Этот элемент в данном списке */
            item->next = item;  /* Он и следующий */
            item->prev = item;  /* и предыдущий для себя самого */
            list->first = item; /* а также первый в списке */
        }

        list->count++; /* Увеличиваем число элементов списка */
    }
}

/*------------------------------------------------
 *  Удалить элемент из списка
 *----------------------------------------------*/

void list_remove(list_item_t* item)
{
    /* Если данный элемент - первый в списке */
    if (item->list->first == item)
    {
        /* Первым будет следующий элемент */
        item->list->first = item->next;
       
        /* Если следующий опять наш элемент, тогда
           он был единственным в списке */

        if (item->list->first == item)
        {
            /* и теперь список пуст */
            item->list->first = NULL;
        }
    }

    /* Предыдущий для данного элемента будет предыдущим
       для следующего  за ним */

    item->next->prev = item->prev;
    /* а следующим за предыдущим будет следующий для удаляемого
       элемента */

    item->prev->next = item->next;

    item->list->count--;
}


подробно пояснять работу списка я не буду, речь идет не об этом, да и данный алгоритм относится к стандартным.

Теперь можно описать структуры процесса и потока

Листинг 70. Структуры процесса и потока (scheduler.h)

#ifndef        SCHEDULER_H
#define        SCHEDULER_H

#include       "common.h"
#include       "list.h"
#include       "memory.h"
/*---------------------------------------------
 * Описатель процесса       
 *-------------------------------------------*/

typedef    struct
{
    list_item_t list_item;     /* Элемент списка */
    physaddr_t  page_dir;      /* Каталог страниц */
    size_t      threads_count; /* Число потоков в этом процессе */
    bool        suspend;       /* Флаг паузы */
    u32int      pid;           /* Идентификатор процесса (PID) */
    char        name[256];     /* Имя процесса */

}__attribute__((packed)) process_t;

/*---------------------------------------------
 *  Описатель потока
 *-------------------------------------------*/

typedef    struct
{
    list_item_t list_item;   /* Элемент списка */
    process_t*  process;     /* Родительский процесс */
    bool        suspend;     /* Флаг паузы */
    size_t      stack_size;  /* Размер стека потока */
    void*       stack;       /* Указатель на блок памяти под стек */
    u32int      esp;         /* Указатель стека */    u32int      entry_point; /* Точка входа в поток */
    u32int      id;          /* Идентификатор потока */

}__attribute__((packed)) thread_t;

В структуры входит поле для помещения потока и процесса в соответствующий список. Смысл остальных полей легко уяснить из комментариев или он будет прояснен по ходу разбора алгоритмов работы с потоками.

3. Планировщик задач - инициализация


Начнем с инициализации планировщика

Листинг 71. Инициализация планировщика (scheduler.c)

#include    "scheduler.h"

/*--------------------------------------------------
 *         
 *------------------------------------------------*/
u32int     next_pid = 0;       /* Следующий идентификатор
                                  процесса (PID) */


u32int     next_thread_id = 0; /* Следующий идентификатор
                                  потока */


list_t     process_list;       /* Список процессов */
list_t     thread_list;        /* Список потоков */

bool       multi_task = false; /* Флаг готовности планировщика */

process_t* kernel_proc = 0;    /* Описатель процесса ядра */
thread_t*  kernel_thread = 0;  /* Описатель потока ядра */

process_t* current_proc;       /* Текущий процесс */
thread_t*  current_thread;     /* Текущий поток */

/*--------------------------------------------------
 *  Инициализация планировщика задач
 *------------------------------------------------*/

void init_task_manager(void)
{
    /* Читаем текущий указатель стека */
    u32int    esp = 0;
    asm volatile ("mov %%esp, %0":"=a"(esp));       

    /* Выключаем прерывания и инициализируем списки задач */
    asm volatile ("cli");

    list_init(&process_list);
    list_init(&thread_list);

    /* Создаем процесс ядра */    /* Выделяем память под описатель процесса и обнуляем её */
    kernel_proc = (process_t*) kmalloc(sizeof(process_t));

    memset(kernel_proc, 0, sizeof(process_t));

    /* Инициализируем процесс */
    kernel_proc->pid = next_pid++;
    kernel_proc->page_dir = get_kernel_dir();
    kernel_proc->list_item.list = NULL;
    kernel_proc->threads_count = 1;
    strcpy(kernel_proc->name, "Kernel");
    kernel_proc->suspend = false;

    list_add(&process_list, &kernel_proc->list_item);

    /* Создаем главный поток ядра */
    kernel_thread = (thread_t*) kmalloc(sizeof(thread_t));

    memset(kernel_thread, 0, sizeof(thread_t));

    kernel_thread->process = kernel_proc;
    kernel_thread->list_item.list = NULL;
    kernel_thread->id = next_thread_id++;
    kernel_thread->stack_size = 0x4000;
    kernel_thread->suspend = false;
    kernel_thread->esp = esp;
   
    list_add(&thread_list, &kernel_thread->list_item);

    /* Делаем процесс и поток ядра текущими */
    current_proc = kernel_proc;
    current_thread = kernel_thread;
   
    /* Взводим флаг готовности планировщика */
    multi_task = true;
   
    /* Снова включаем прерывания */
    asm volatile ("sti");
}

Здесь выполняется создание процесса и потока ядра, причем мы применяем новые функции динамического выделения памяти в куче. Инициализируем описатель потока и процесса ядра и ставим их в очередь на выполнение. Объявляем их текущими процессом и потоком и взводим флаг готовности планировщика.

4. Переключение через стек задачи


На переключении задач остановимся подробнее, изложу суть алгоритма, предложенного phantom-84

Для того чтобы понять как происходит переключение задач, рассмотрим сначала вызов подпрограммы в языке C. Согласно декларации принятой в этом языке, перед вызовом в стек проталкиваются передаваемые в подпрограмму параметры, в обратном порядке начиная с последнего. Потом выполняется инструкция call передающая управление подпрограмме и (внимание!!!) - помещающая в стек адрес возврата, то есть адрес по которому будет произведена передача управления после завершения подпрограммы.   Далее, уже в самой подпрограмме в стек проталкивается регистр EBP, а затем ему присваивается значение текущее значение указателя стека ESP, для облегчения доступа к переданным параметрам внутри подпрограммы.

При завершении подпрограммы из стека выталкивается регистр EBP и выполняется инструкция ret, выталкивающая из стека адрес возврата и загружающая его в регистр EIP - счетчик команд.

Все сказанное можно проиллюстрировать следующим ассемблерным кодом

          /* Передача параметров через стек */
          push param_n
          .
          .
          .
          push param_2
          push param_1

          call sub_proc   /* Здесь в стек помещается адрес возврата */
          .
          .
          .

sub_proc:

          push %ebp
          mov  %esp, %ebp
                 .
                 .
          /* Здесь мы выполняем какие-то действия */
                 .
                 .
                 .
          pop  %ebp
          ret             /* Здесь из стека выталкивается адрес
                             возврата */

Этот код отражает схему вызова любой  функции на языке C.

Я специально выделил красным особо важную часть текста, именно в ней заключен весь смысл алгоритма переключения задач. Представим себе, что у нас есть некая функция, которая периодически (по прерыванию таймера, например) вызывается и выполняет переключение задач. 

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

Все сказанное в самом простом случае иллюстрируется следующей схемой изменения состояния стека в процессе переключения задач



От обычного вызова подпрограммы эта схема отличается только тем, что вызываемая подпрограмма "предательски" подменяет процессору стек, и он как ни в чем не бывало идет выполнять код другого потока. И наша задача при создании нового потока сводится к правильному формированию для него стекового кадра.

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



Теперь приступим непосредственно к реализации, рассмотрим функцию переключения задач. ESP при этом должен указывать на значение EFLAGS помещенное в стек.

Листинг 72. Функция переключения задач (scheduler.c)

/*-----------------------------------------------
 *  Переключение задач
 *---------------------------------------------*/

void switch_task(void)
{
    /* Если планировщик готов к работе */
    if (multi_task)
    {
       /* Проталкиваем флаги в стек и выключаем прерывания */
       asm volatile ("pushf; cli");

       /* Запоминаем указатель стека в структуре текущей задачи */
       asm volatile ("mov %%esp, %0":"=a"(current_thread->esp));

       /* Берем новую задачу из очереди */
       current_thread = (thread_t*) current_thread->list_item.next;
      
       /* Задаем новый каталог страниц (для процессов) */
       asm volatile ("mov %0, %%cr3"::"a"(current_proc->page_dir));
       /* Переключаемся на стек новой задачи */
       asm volatile ("mov %0, %%esp"::"a"(current_thread->esp));

       /* Выталкиваем флаги из стека, тем самым неявно
          разрешая прерывания */

       asm volatile ("popf");
    }
}

Как видим всё предельно просто: проталкиваем регистр флагов в стек, выключаем прерывания, чтобы процесс переключения не был прерван на полпути, запоминаем в структуре текущей задачи указатель стека процессора. Затем берем из кольцевой очереди описатель следующей задачи, делаем текущей её, и загружаем в ESP указатель стека, сохраненный в структуре новой задачи.

Теперь выталкиваем из стека регистр флагов - его значение либо протолкнул туда планировщик при предыдущем переключении, либо мы вручную поместили его при создании задачи на нужное место в её стеке. Регистр EBP функция переключения вытолкнет сама, сам же она вытолкнет из стека и адрес возврата, который будет равен адресу инструкции в новой задаче.

Осталось рассмотреть как же мы должны создавать новый поток

Листинг 73. Создание нового потока (scheduler.c)

/*--------------------------------------------------
 *        Создание потока
 *------------------------------------------------*/
thread_t* thread_create(process_t* proc,   /* Родительский процесс */
                        void* entry_point, /* Точка входа в поток */
                        size_t stack_size, /* Размер стека потока */
                        bool kernel,       /* Поток ядра */
                        bool suspend)      /* Поток приостановлен */
{
    void*    stack = NULL;
    u32int   eflags;
    
       /* Получаем регистр флагов */
    asm volatile ("pushf; pop %0":"=r"(eflags));
    /* Выключаем прерывания */
    asm volatile ("cli");

    /* Создаем описатель нового потока */
    thread_t* tmp_thread = (thread_t*) kmalloc(sizeof(thread_t));

    /* Очищаем память структуры описателя */
    memset(tmp_thread, 0, sizeof(thread_t));

    /* Инициализируем новый поток  */
    tmp_thread->id = next_thread_id++;
    tmp_thread->list_item.list = NULL;
    tmp_thread->process = proc;
    tmp_thread->stack_size = stack_size;
    tmp_thread->suspend = suspend;/* */
    tmp_thread->entry_point = (u32int) entry_point;

    /* Создаем стек нового потока */
    stack = kmalloc(stack_size);
   
    /* Сохраняем указатель на память стека */
    tmp_thread->stack = stack;
    /* Устанавливаем значние ESP
       в структуре потока - он должен указывать на значение
       регистра флагов, которое мы поместим в стек */

    tmp_thread->esp = (u32int) stack + stack_size - 12;

    /* Добавляем поток в очередь */
    list_add(&thread_list, &tmp_thread->list_item);

    /* Увеличиваем число потоков родительского процесса */
    proc->threads_count++;

    /* Формируем стек задачи */

    /* Создаем указатель на память отведенную под стек */
    u32int* esp = (u32int*) (stack + stack_size);

    /* Помещаем в стек точку входа в поток и
       значение регистра флагов */

    esp[-1] = (u32int) entry_point;
    esp[-3] = eflags | (1 << 9); /* Взводим флаг IF */

    /* Включаем прерывания */
    asm volatile ("sti");

    /* Возвращаем указатель на структуру потока */
    return tmp_thread;
}

Теперь протестируем всё что мы написали. Для этого приведу снова полный текст файла main.c, так как его придется подвергнуть существенной модификации - добавить задачи: функции task01() и task02(). Те кто знаком с системным программированием под Windows или Linux, знают что такие функции называются функциями потоков. Нам нужет маленький тест, поэтому эти функции будут выводить текстовое сообщение на экран и зацикливаться. Большего пока наша система не может обеспечить, но поверьте - нами реализована настоящая многозадачность, хоть в этом можно убедиться окончательно только оттрассировав ядро в отладчике (так я тоже убеждался в корректности работы планировщика, а уж потом нагрузил задачи более сложными действиями). Кроме того нам нужна функция получения указателя на текущий процесс, её надо добавить в планировщик

Листинг 74. Получение текущего процесса (scheduler.c)

/*------------------------------------------------
 *   Получить указатель на текущий процесс
 *----------------------------------------------*/

process_t* get_current_proc(void)
{
    return current_proc;
}


Листинг 75. Проверка планировщика задач (main.c)

#include    "main.h"

/*-----------------------------------------------
//    Задача #1
//---------------------------------------------*/

void task01(void)
{
    print_text("I'm thread #1\n");
   
    while (1);
}

/*-----------------------------------------------
//    Задача #2
//---------------------------------------------*/

void task02(void)
{
    print_text("I'm thread #2\n");
   
    while (1);
}

/* Указатели на структуры потоков */
thread_t* thread01;
thread_t* thread02;

/*-----------------------------------------------
//    Точка входа в ядро
//---------------------------------------------*/

int main(multiboot_header_t* mboot, u32int init_esp)
{
  u32int vir_addr = 0;
  u32int phys_addr = 0;
  int i = 0; 
 
  print_text("Hello from myOSkernel!!!\n\n");
 
  print_text("hex value: ");
  print_hex_value(1000);
  print_text("\n");
 
  print_text("dec value: ");
  print_dec_value(589);
  print_text("\n\n");
 
  print_text("0 1 2 3 4 5 6 7 8 9 A B C D E F\n");
 
  for (i = 0; i < 16; i++)
  {
    set_bkground_color(i);
    print_text("  ");
  }
 
  print_text("\n");
 
  init_descriptor_tables();
 
  print_text("\n\n"); 
 
  set_bkground_color(BLACK);  
   
  check_memory_map((memory_map_entry_t*) mboot->mmap_addr,
                    mboot->mmap_length);
 
  print_text("\n");
 
  init_memory_manager(init_esp);   
 
  init_timer(BASE_FREQ);
  asm volatile ("sti");
   
  /* Инициализируем планировщик */
  init_task_manager();
 
  /* Получаем указатель на текущий процесс */
  process_t* proc = get_current_proc();
 
  /* Создаем два потока */
  thread01 = thread_create(proc,
               &task01,
               0x4000,
               true,
               false);


  thread02 = thread_create(proc,
               &task02,
               0x4000,
               true,
               false);
     
  return 0;
}

Кроме того, необходимо изменить код обработчика прерывания IRQ0 от системного таймера

Листинг 76. Переключение задач по таймеру (timer.c)


#include    "timer.h"
#include    "isr.h"
#include    "text_framebuffer.h"
#include    "scheduler.h"


/*-----------------------------------------------------
//   
//---------------------------------------------------*/

static void timer_callback(registers_t regs)
{
    switch_task();
}

Собираем ядро и запускаем виртуальную машину


Вуаля! Только что мы запустили два потока, которые вывели текст на экран и молотят бесконечный цикл. Было бы неплохо вывести на экран счетчики индивидуальные для каждого потока, но это пока затруднительно, так как функции работы с видеобуфером у нас не расчитаны на многозадачность, и вместо картинки работы потоков мы получим белеберду на экране.

К этому вопросу мы обязательно вернемся ещё, я допустим уже реализовал это )


в своей версии ядра, реализуем и мы. Нам предстоит ещё много работы...

Заключение


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