Гречищев Юрий

Решение проблемы обедающих философов средствами ОСРВ eCos

В области операционных систем существует множество классических проблем, решения которых показывают преимущество тех или иных механизмов синхронизации. Среди них такие задачи, как проблема производителя и потребителя (проблема ограниченного буфера), проблема спящего брадобрея, проблема обедающих философов, проблема читателей и писателей. При разработке операционной системы правильность реализации примитивов синхронизации может проверяться путем решения той или иной задачи средствами ОС.
Рассмотрим решение "проблемы обедающих философов" в ОСРВ eCos. Сама проблема хорошо сформулирована у Таненбаума (книжка "Операционные системы"):
Несколько философов сидят за круглым столом и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужны две вилки, чтобы управиться с яством. Но между каждыми двумя тарелками лежит только одна вилка.

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

Листинг приложения ОСРВ eCos, моделирующий поведение системы:

#include <cyg/kernel/kapi.h>
#include <cyg/infra/cyg_ass.h>
#include <cyg/kernel/diag.h>

// -------------------------------------------------------------------------
// Объявления потоков

#define PHILOSOPHERS 15    // число философов
#define STACKSIZE (2*1024)    // размер стека для потоков

// массив стеков для потоков философов
char thread_stack[PHILOSOPHERS][STACKSIZE];

// массив потоков
cyg_thread thread[PHILOSOPHERS];

cyg_handle_t thread_handle[PHILOSOPHERS];

// массив семафоров (вилок)
cyg_sem_t chopstick[PHILOSOPHERS];

cyg_ucount32 data_index;

// -------------------------------------------------------------------------
// Управление состоянием философа

static char pstate[PHILOSOPHERS+1]; // вектор состояний, показывающий, чем занимается каждый философ

cyg_mutex_t state_mutex; //мютекс для организации взаимоисключения

void change_state(int id, char newstate)
{
cyg_mutex_lock(&state_mutex);    //вход в критическую секцию
 
pstate[id] = newstate;

diag_write_string(pstate); //выводим чем занимается каждый философ
diag_write_char('\n');

cyg_mutex_unlock(&state_mutex);    //выход из критической секции
}

char get_state( int id)
{
char s;
cyg_mutex_lock(&state_mutex);  //вход в критическую секцию
 
s = pstate[id];

cyg_mutex_unlock(&state_mutex);  //выход из критической секции

return s;
}

// -------------------------------------------------------------------------
// Поток, моделирующий поведение философа

void Philosopher( cyg_addrword_t vid )
{
cyg_uint32 id = (cyg_uint32)vid;
cyg_sem_t *first_stick = &chopstick[id];
cyg_sem_t *second_stick = &chopstick[(id+1)%PHILOSOPHERS];
 
CYG_ASSERT( id >= 0 && id < PHILOSOPHERS, "Bad id");

if( id == PHILOSOPHERS-1 )
{
cyg_sem_t *t = first_stick;
first_stick = second_stick;
second_stick = t;
}
 
for(;;)
{
cyg_ucount32 val;
 
static volatile int cycle = 0;
 
// Немного подумаем
cyg_thread_delay((id+cycle++)%12);

// Я голоден, надо попытаться завладеть вилкой
change_state(id,'H');
 
// Берем первую вилку
cyg_semaphore_wait(first_stick);
 
// Берем вторую вилку
cyg_semaphore_wait(second_stick);
 
// Есть обе вилки, можно и поесть...
change_state(id,'E');
 
// Проверяем значения семафоров
cyg_semaphore_peek( first_stick, &val);
CYG_ASSERT( val == 0, "Not got first stick");
cyg_semaphore_peek( second_stick, &val);
CYG_ASSERT( val == 0, "Not got second stick");
CYG_ASSERT( get_state(left_philo) != 'E', "Left neighbour also eating!!");
CYG_ASSERT( get_state(right_philo) != 'E', "Right neighbour also eating!!");
 
cyg_thread_delay((id+cycle++)%6);

// Заканчиваем есть, кладем вилки назад

change_state(id,'T');

cyg_semaphore_post( first_stick );
cyg_semaphore_post( second_stick );

}
}

// -------------------------------------------------------------------------

externC void
cyg_start( void )  // точка входа в программу
{
int i;
 
diag_init();

diag_write_string("Philosophers\n");
diag_write_string("Started\n");

//последний элемент в векторе нулевой для того, чтобы можно было работать с ним как со строкой
pstate[PHILOSOPHERS] = 0;

for( i = 0; i < PHILOSOPHERS; i++ )
{
change_state(i,'T'); // начальное состояние

cyg_thread_create(4, Philosopher, (cyg_addrword_t)i, "philosopher",
(void *)(&thread_stack[i]), STACKSIZE,
&thread_handle[i], &thread[i]);

// переводим потоки в состояние готовности
cyg_thread_resume(thread_handle[i]);

// инициализируем семафоры
cyg_semaphore_init( &chopstick[i], 1);
}
 
// запуск планировщика, начало моделирования
cyg_scheduler_start();

}

---

Функции работы с семафорами в eCos:

Макросы CYG_ASSERT проверяют условия и в случае ошибки выдают соответсвующее сообщение.