Программерам, Специалистам в области RT/Embedded, и т.д (часть1)

[correlator]

Ниже представлены типичные вопросы, задаваемые на интервью потенциальными работодателями - в области embedded и real-time и не только....

Израиль Июль 2005.

Пример 1:

Дана функция
unsigned int GetID()
{
  static unsigned int i = 0;
  return i++;
}

Вопрос:
В чем есть потенциальная проблема если функция вызывается с нескольких тасков ?
и как реализовать функцию полностью реентерабельной (Reentrant function) ?

Ответ:
Первое приближение:
unsigned int GetID()
{
  static unsigned int i = 0;
  enter_critical_Section();
  i++;
  leave_critical_Section();
  return i;
}
* но тут потенциальная проблема (надуманная так как обычно компиляторы создают копию) в строчке return i - там может быть проблема во время возврата значения.

Формально правильный ответ:
Так как переменная i статическая и не находится в стеке тасков может произойти data corruption, поэтому создадим локальную переменную temp (которая будет находится в стеке каждого из тасков).

Конечный Вариант:
unsigned int GetID()
{
  static unsigned int i = 0;
  enter_critical_Section();
  unsigned int temp = i++;
  leave_critical_Section();
  return temp;
}

Пример 2:

Дан буфер размером 64bit в который копируются входные данные (например с помочью DMA).

Вопрос: Как реализовать алгоритм который подсчитает количество выставленный битов?

пример: 01000101 01010010 10000000 10101010 10010100 00001010 0010001 01111001
количество выставленных битов = 23

Ответ:
Есть 3 варианта решения этой задачи

Вариант 1.
Написать рутину которая будет двигать буфер или влево или в право и считать каутером (переменная) по MSB или LSB количество выставленных единичек. Этот вариант оптимален по расходу оперативной памяти, и не очень эффективен по ресурсам CPU.

Вариант 2.
Создается Массив размером 2^64 в который заблаговремено заполняется уже проcчитанными данными (look up table).
Полученный буфер будет играть роль индекса массива а полученное значение из массива это количество выставленный битов.
Этот вариант оптимален по скорости вычисления, но не оптимален по количеству расходуемой памяти.

Вариант 3.
Создать массив размером 2^32 а не на 2^64, и получать из него данные в 2 этапа.
Тесть сначала берутся первые 32бита из буфера и подаются как индекс массива - находится количество включенных битов
Потом подается вторая часть (32бита) - высчитывав количество битов, полученный результат складывается с первым, таким образом мы подсчитали количество битов в 2 этапа при использовании таблицы намного меньшего размера.

Пример 3:

Дана операционная система которая имеет функции аллокации памяти не стандартного типа:

void *spmalloc(unsigned int size);

void spfree(void *ptr,unsigned int size);

В функции free нужен размер буфера.

Вопрос:
Реализовать на основе 2 этих функций стандартный malloc и free (без указания размера буфера).

Реализация:

void *malloc(unsigned int size)
{
    void *ptr = spmalloc(size + sizeof(int));    // резервируем блок нужного размера + место под данные для хранения размера
    memcpy(&ptr[0],&size,sizeof(int));          // прописываем замер блока в начале зарезервированного блока
   return (ptr + sizeof(int));
}

void free(void *block)
{
   void *realblockoffset = block - sizeof(int);
   spfree(realblockoffset, (unsigned int *)realblockoffset + sizeof(int));
}

* надеюсь не где не ошибся  :-[

Пример 4:

Вопрос1:
Чем опасна рекурсия (особенно в embedded/RT аппликациях) ?
Ответ:
Рекурсивный вызов функций может привести к переполнению стека.

Вопрос2:
Какая есть альтернатива ?
Ответ:
Использовать циклы, выходные данные каждой итерации хранить в динамически распределенном ресурсе, например в связанном списке.

Вопрос3:
С какой закономерностью заполняется стек при рекурсивном вызове функций?
Ответ:
С логарифмической Закономерностью.

Продолжение следует :)