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

PhantomEx: Примитивы синхронизации. Мьютексы.

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

Речь идет о том, что в каждом потоке, хоть и однократно, вызывается функция выделения памяти

/* Создаем виртуальный экран в потоке #1 */
vs01 = (vscreen_t*) get_vscreen();
.
.
.
/* Создаем виртуальный экран в потоке #2 */
vs02 = (vscreen_t*) get_vscreen();

Эти функции содержат внутри выделение памяти в куче ядра. Куча ядра у нас одна единственная, все структуры управляющие физической и виртуальной памятью  - в одном экземпляре. Что произойдет если момент переключения задачи - ведь он происходит по прерыванию - совпадет с работой функции kmalloc(...)? Ничего хорошего - структуры управления кучей будут перехвачены другим потоком, и он безнадежно испортит их, что приведет к неверной работе другого потока да и системы в целом.

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




1. Семафоры, мьютексы и критические секции.


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

  1. Критические секция - объект синхронизации, позволяющий предотвратить выполнение некоторого набора операций, например доступа к данным, нескольким потокам одновременно. Критическая секция принадлежит процессу и служит для синхронизации его потоков.
  2. Мьютекс - выполняет ту же функцию, что и критическая секция, но является объектом ядра и может обеспечивать синхронизацию между процессами.
  3. Семафор - объект позволяющий войти в данный участок кода не более чем n потокам. Семафоры используются при передаче данных через разделяемую память.
Наша задача обеспечить синхронизированный доступ к управляющим структурам менеджера памяти, при выделении памяти внутри потоков. Для этой цели будем использовать мьютексы.

Создадим модуль для работы с объектами синхронизации

Листинг 91. Модуль синхронизации (sync.h)

/*----------------------------------------------------------------
 *
 *         Примитивы синхронизации
 *
 *--------------------------------------------------------------*/

#ifndef     SYNC_H
#define     SYNC_H

#include    "common.h"

/* Тип-мьютекс - логический тип */
typedef        bool    mutex_t;

/* Захватить мьютекс */
bool mutex_get(mutex_t* mutex, bool wait);
/* Освободить мьютекс */
void mutex_release(mutex_t* mutex);

#endif

Листинг 92. Модуль синхронизации (sync.c)

#include    "sync.h"

/*----------------------------------------------------------------
 *   Захват мьютекса
 *--------------------------------------------------------------*/

bool mutex_get(mutex_t* mutex, bool wait)
{
    bool old_value = true; /* Флаг, с которым мы обменяем значение мьютекса */

    do
    {
        /*  Выполняем присвоение true выбранному мьютекса, с помощью */
        /*  АТОМАРНОЙ операции обмена значениями переменных */
        asm volatile ("xchg (,%1,), %0":"=a"(old_value):"b"(mutex), "a"(old_value));

    } while (old_value && wait); /* Гоняем цикл, пока не сброшено old_value */

    return !old_value;
}

/*----------------------------------------------------------------
 *   Освобождение мьютекса
 *--------------------------------------------------------------*/

void mutex_release(mutex_t* mutex)
{
    *mutex = false;
}

Итак, для выполнения блокировки доступа к определенному участку кода, мы создадим переменную типа mutex_t и присвоим ей значение false. Прежде чем выполнять критический участок кода, произведем захват мьютекса, выполним критичный к порядку доступа код, а затем освободим мьютекс

mutex_t test_mutex = false;
.
.
.
/*  Захватываем мьютекс */
mutex_get(&test_mutex, true);
.
.
/* Тут выполняем критический код */
.
.
/* Освобождаем мьютекс */
mutex_release(&mutex);


Что происходит при захвате мьютекса? Переменной типа мьютекс просто присваивается значение true, но выполняется это так, чтобы процесс присваивания не был прерван при переключении задач. Для этого используется атомарная операция обмена значений переменных/регистров. В случае когда мьютекс свободен, его старое значение - false, и оно сбрасывает флаг old_value, тем самым сразу обеспечивая выход из цикла и передачу управления на защищаемый код.

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

Как видим, это довольно просто. Применим созданный нами код на практике.

2. Синхронизация доступа к физической памяти и куче ядра


Немного изменим код нашего менеджера памяти

Листинг 93. Структура описания кучи (memory.h)

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

typedef struct
{
    memory_block_t* blocks;           
    void*           start;           
    void*           end;           
    size_t          size;          
    size_t          count;         
    mutex_t         heap_mutex; /* Мьютекс для синхронизации доступа */

}__attribute__((packed)) heap_t;

Листинг 94. Модификация функций управления памятью (memory.c)

mutex_t       phys_memory_mutex; /* Мьютекс для синхронизации доступа
                                    к физической памяти */

/*----------------------------------------------------------------
//        Выделение страниц физической памяти
//--------------------------------------------------------------*/

physaddr_t alloc_phys_pages(size_t count)
{
    physaddr_t result = -1;
    physmemory_pages_block_t* tmp_block;

    mutex_get(&phys_memory_mutex, true);
    .
    .
    /* Выполняем действия по выделению физической памяти */
    .
    .
    mutex_release(&phys_memory_mutex);

    return result;
}

/*----------------------------------------------------------------
//        Освобождение страниц физической памяти
//--------------------------------------------------------------*/

void free_phys_pages(physaddr_t base, size_t count)
{
    physmemory_pages_block_t* tmp_block;

    mutex_get(&phys_memory_mutex, true);
    .
    .
    /* Действия по освобождению физической памяти */
    .
    .
    mutex_release(&phys_memory_mutex);
}
.
.
.
/*----------------------------------------------------------------
 *        Выделение памяти в куче
 *--------------------------------------------------------------*/

void* kmalloc_common(size_t size, bool align)
{
    void*    vaddr = kheap.start;
    int      i = 0;

    mutex_get(&kheap.heap_mutex, true);
    .
    .
    /* Выделение памяти в куче */
    .
    .
    mutex_release(&kheap.heap_mutex);

    return vaddr;
}

/*----------------------------------------------------------------
 *        Освобождение памяти
 *--------------------------------------------------------------*/

void kfree(void* vaddr)
{
    int    i = 0;
    int    block_idx = 0;

    mutex_get(&kheap.heap_mutex, true);
    .
    .
    /* Освобождение памяти в куче */
    .
    .
    mutex_release(&kheap.heap_mutex);
}

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

Кроме менеджера памяти у нас есть ещё общая динамические структура - списки потоков и процессов в очереди на выполнение. Добавим синхронизацию в функции управления списками

Листинг 95. Синхронизация списков (list.h)

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

typedef struct
{
    list_item_t*    first;
    size_t          count;
    mutex_t         mutex; /* Мьютекс для синхронизации доступа к списку */

} list_t;


Листинг 96. Синхронизация списков (list.c)

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

void list_init(list_t* list)
{
    list->first = NULL;
    list->count = 0;
    list->mutex = false;
}

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

void list_add(list_t* list, list_item_t* item)
{
    if (item->list == NULL)
    {
        mutex_get(&(list->mutex), true);

        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++;
        mutex_release(&(list->mutex));
    }
}

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

void list_remove(list_item_t* item)
{
    mutex_get(&(item->list->mutex), true);

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

    mutex_release(&(item->list->mutex));
}

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

После внесения всех изменений в код, проверим что же у нас получилось


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

Заключение


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