?

Log in

No account? Create an account
Blog с претензиями на...
-===-
Свежие записи 

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

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


Пример 5:

Даны 2 структуры данных.

1. Связный список (Linked List).
2. Статически распределённый массив.

Вопрос1:
В каком случае эффективней использовать Linked List, а в каком статический массив ?
Ответ:
Список эффективно использовать когда количество данных заранее не известно - таким образом экономится память.
Массив эффективен при известном количестве данных, операции копирования и т.д более эффективны по времени выполнения.

Вопрос2:
Почему в RT системах лучше избегать использование связанных списков и подобных типов данных ?
Ответ:
Массивное использование списков вызывают дефрагментацию в memory heap - тем самым приводит не эффективному распределению динамической памяти.


Пример 6:


Реализован механизм (без применения механизмов операционной системы) доступа двух тасков к Shared Memory.
Доступ к Access регистру атамарен.
При чтении в регистр значение х, при записи у.
При чтении - пишущий поток ждет, и наоборот...

Вопрос:
В чем принципиальная проблема в такой реализации?

Ответ:
Основная проблема такого подхода: ждущий таск всегда ожидая своей очереди на операцию постоянно делает опрос (polling) access регистра - что приводит к повышенной загруженности процессора.
(Реализация с помощью семафора решает проблему).



Пример 7:
Даны 2 класса:

class A
{
  protected:
  char * temp;
  public:
  A()                                         
// конструктор класса A
  {
    temp = (char *)malloc(50);
  }

  ~A()                                    
// деструктор класса A
   {
      free(temp);
   }
};

class B : public A                    
// B наследует A
{
  protected:
  char * temp2;
  public:
  B()                                         
// конструктор класса A
  {
    temp2 = (char *)malloc(50);
  }

  ~B()                                    
// деструктор класса A
   {
      free(temp2);
   }
};



Далее идет программа где используются данные классы:

void main()
{
 A *Ainst = new B;            
// Аля полиформизм
  ......
  ......                                 
// произвольное тело программы
  ......
 delete Ainst ;                    
// Удаления Ainst
}

Вопрос:
Какая проблема возникает при запуске этого кода ?

Ответ:
При запуске данной программы возникает Memory Leak (Утечка памяти) так как не вызывается деструктор класса B (в строчке
Удаления Ainst).
Решение проблемы: деструктор класса A должен быть виртуальным.



Пример 8:
Дана операционная система Windows CE (ранние версии). В данной операционной системе не реализована функция:

WaitForMultipleObjects(DWORD nCount, CONST HANDLE *lpHandles, BOOL bWaitAll, DWORD dwMilliseconds);

Вопрос:
Как реализовать эту функцию с помощью WaitForSingleObject(...) ?

Ответ:
Для реализации надо открывать Thread на каждый отдельно ожидаемый Event. Пример
реализации Thread'a:

void WaitTread(HANDLE *Handle)
{
   WaitForSingleObject(Handle,INFINITE);
   SetEvent(CommonEvent);
  
// тут нужна критическая сессия для зашиты Source
    Source = Handle;
}

В основном потоке ожидается CommonEvent и по глобальной переменной Source индифицируется какой именно из ожидаемых Event'ов был выловлен.
Подобная реализация сделана в Windows NT.


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

Посмотрел на ночь глядя фильм Изабель Куаксет 
Фильм хороший - редко удается увидеть такое кино. Не слишком сладкое и реалистично правдивое.
Кино и для мозгов и для души. Чипсы под него конечно не поешь, зато поплакать можно!
Ниже представлены типичные вопросы, задаваемые на интервью потенциальными работодателями - в области 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:
С какой закономерностью заполняется стек при рекурсивном вызове функций?
Ответ:
С логарифмической Закономерностью.

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

11-июл-2005 10:19 pm - Начало...
"Сначала сотворил Бог небо и землю. Потом светила. Потом он каждый день что-нибудь творил — и всякий раз убеждался, «что это хорошо»"
Сегодня вечером, где-то около 22:20, захотелось мне завести собственный Livejournal.
Стянул и установил Semagic, поправил личные данные.
В общем, теперь буду изредка писать сюда что-то личное, скучное и не особо интересное.
This page was loaded дек 12 2017, 10:22 am GMT.