Friday, July 9, 2010

Embedded Systems Questions for Interview

Embedded Systems Questions for Interview
 
1) What is a 'volatile' variable?
 
Volatile is a keyword to specify the compiler that this variable value can change any time, so compiler should always read its value from it's address, and not to use temporary registers to store its value and use in later part of the code.
 
 
This is specially important to handle the memory mapped registers which are mapped as some variables or structures in embedded systems, such as hardward status registers etc, whose value can be changed anytime, depending on the hardware state.
 
Examples of volatile variables are,
 
  • Hardware registers in peripherals (for example, status registers)
  • Non-automatic variables referenced within an interrupt service routine
  • Variables shared by multiple tasks in a multi-threaded application
 
Can a volatile be constant? like
volatile const a;
 
Yes it can be, it means that, it can be changes by hardware state chage, but its read only register in hardware, so code should not try to modify it.
 
Can a pointer be volatile ? Explain.
Yes, although this is not very common. An example is when an interrupt service routine modifies a pointer to a buffer
 
What's wrong with the following function?
 
int square(volatile int *ptr)
{
    return *ptr * *ptr;
}
 
This one is wicked. The intent of the code is to return the square of the value pointed to by *ptr . However, since *ptr points to a volatile parameter, the compiler will generate code that looks something like this:
 
int square(volatile int *ptr)
{
    int a,b;
    a = *ptr;
    b = *ptr;
    return a * b;
}
Because it's possible for the value of *ptr to change unexpectedly, it is possible for a and b to be different. Consequently, this code could return a number that is not a square! The correct way to code this is:
 
long square(volatile int *ptr)
{
    int a;
    a = *ptr;
    return a * a;
}
 
2) What is a 'const' variable?
 
In simple terms 'const' means 'read only'. Its value is not changed by any part of the code executed. So compiler can optimize by taking this info, and also it will give warning when user try to change the value of this variable by mistake.
 
If the candidate gets the answer correct, I'll ask him these supplemental questions:
What do the following declarations mean?
 
const int a;
int const a;
const int *a;
int * const a;
int const * a const;
 
The first two mean the same thing, namely a is a const (read-only) integer. The third means a is a pointer to a const integer (that is, the integer isn't modifiable, but the pointer is). The fourth declares a to be a const pointer to an integer (that is, the integer pointed to by a is modifiable, but the pointer is not). The final declaration declares a to be a const pointer to a const integer (that is, neither the integer pointed to by a, nor the pointer itself may be modified). If the candidate correctly answers these questions, I'll be impressed.
 
Even thouugh any program can be written without this keyword, it's good to use this, since it will help the one who is reading the program to understand the code easily by the information that the variable's value wont get changed. So using const keyword will help reducing the bugs in the code.
 
 
3) Which is the best way to write Loops?
The best way is to write count down loops and compiler can generate better machine code for it than the count up loops. In count down at loop termination, it needs to generate one instructions (SUBS), which subtracts as well as check the zero flag, but in count up case it has to add and compare with a constant, which takes two instructions.
 
 
4) What is loop unrolling? 
 
Small loops can be unrolled for higher performance, with the disadvantage of increased codesize. When a loop is unrolled, a loop counter needs to be updated less often and fewer branches are executed. If the loop iterates only a few times, it can be fully unrolled, so that the loop overhead completely disappears.
 
int CountBitOne(uint n)
{     
  int bits = 0;
    while (n != 0)
    {
        if (n & 1) bits++;
        n >> = 1;
    }
  return bits;
}
 
int CountBitOne(uint n)
{
   int bits = 0;
    while (n != 0)
    {
    if (n & 1) bits++;
    if (n & 2) bits++;
    if (n & 4) bits++;
    if (n & 8) bits++;
    n >> = 4;
    }
  return bits;
}
5) How are local and Global variables are allocated by compiler.
 
Normally, cpu registers are allocated for local variables, but if the address of that local variable is used by some code, then it wont allocate register but access from memory, thus result in un-optimized code. Gobal variables always use memory, so access is slower, so always use global only when it is absolutely neccessary.
 
6) Which is better a char, short or int type for optimization?
 
Where possible, it is best to avoid using char and short as local variables. For the types char and short the compiler needs to reduce the size of the local variable to 8 or 16 bits after each assignment. This is called sign-extending for signed variables and zeroextending for unsigned variables. It is implemented by shifting the register left by 24 or 16 bits, followed by a signed or unsigned shift right by the same amount, taking two instructions (zero-extension of an unsigned char takes one instruction).
 
These shifts can be avoided by using int and unsigned int for local variables. This is particularly important for calculations which first load data into local variables and then process the data inside the local variables. Even if data is input and output as 8- or 16-bit quantities, it is worth considering processing them as 32bit quantities
 
7) How to reduce function call overhead in ARM based systems
 
  • Try to ensure that small functions take four or fewer arguments. These will not use the stack for argument passing. It will copied into registers.
 
  • If a function needs more than four arguments, try to ensure that it does a significant amount of work, so that the cost of passing the stacked arguments is outweighed.
 
  • Pass pointers to structures instead of passing the structure itself.
 
  • Put related arguments in a structure, and pass a pointer to the structure to functions. This will reduce the number of parameters and increase readability.
 
  • Minimize the number of long long parameters, as these take two argument words. This also applies to doubles if software floating-point is enabled.
 
  • Avoid functions with a parameter that is passed partially in a register and partially on the stack (split-argument). This is not handled efficiently by the current compilers: all register arguments are pushed on the stack.
 
  • Avoid functions with a variable number of parameters. Varargs functions 
 
8) What is a pure function in ARM terminology?
 
 
Pure functions are those which return a result which depends only on their arguments. They can be thought of as mathematical functions: they always return the same result if the arguments are the same. To tell the compiler that a function is pure, use the special declaration keyword __pure.

__pure int square(int x)
{
    return x * x;
}
9) What are inline functions?
 
The ARM compilers support inline functions with the keyword __inline. This results in each call to an inline function being substituted by its body, instead of a normal call. This results in faster code, but it adversely affects code size, particularly if the inline function is large and used often.
 
Preprocessor
 
10) Using the #define statement, how would you declare a manifest constant that returns the number of seconds in a year? Disregard leap years in your answer.
  
#define SECONDS_PER_YEAR
(60 * 60 * 24 * 365)UL
 
The purpose of this question is to test the following:
 
  1. Basic knowledge of the #define syntax (for example, no semi-colon at the end, the need to parenthesize, and so on)
     
  2. An understanding that the pre-processor will evaluate constant expressions for you. Thus, it is clearer, and penalty-free, to spell out how you are calculating the number of seconds in a year, rather than actually doing the calculation yourself
     
  3. A realization that the expression will overflow an integer argument on a 16-bit machinehence the need for the L, telling the compiler to treat the variable as a Long
     
  4. As a bonus, if you modified the expression with a UL (indicating unsigned long), then you are off to a great start. And remember, first impressions count!
 
11) Write the "standard" MIN macro-that is, a macro that takes two arguments and returns the smaller of the two arguments.
 
#define MIN(a,b) ((a)<(b)?(a):(b))
 
The purpose of this question is to test the following:
 
  1. Basic knowledge of the #define directive as used in macros. This is important because until the inline operator becomes part of standard C, macros are the only portable way of generating inline code. Inline code is often necessary in embedded systems in order to achieve the required performance level
     
  2. Knowledge of the ternary conditional operator. This operator exists in C because it allows the compiler to produce more optimal code than an if-then-else sequence. Given that performance is normally an issue in embedded systems, knowledge and use of this construct is important 
      
  3. Understanding of the need to very carefully parenthesize arguments to macros
 
I also use this question to start a discussion on the side effects of macros, for example,

what happens when you write code such as:

least = MIN(*p++, b);
 
In this case, the expression is replaced by,
 
 *ptr is compared with b, then ptr is incremented to point to next integer, suppose *ptr is small, then *ptr is assigned to least, and ptr is incremented again. 
 
So the result will be integer at (ptr + sizeof(int)). 
 
 
12) What is the purpose of the preprocessor directive #error?   
 
Answer to this question does not need to be known, this is normally explained in the appendices, only nerds normally look into the appendices to see the answers for such questions. Normal folks dont be knowing the answer to this unless they happend to see this somewhere else while doing some project.
 
13) Infinite loops often arise in embedded systems. How does you code an infinite loop in C?
 
There are several solutions to this question. One is,
while(1)
{
Other is using for loop, but here things are not pretty clear as to what is going on.
for(;;)
{
}
Even though both serve the same perpose, its always better to know why you are using the first or second. So when you are asked about such questions you must answer with confidence that both are right, and just matter which way you wish to code it, anyways finally compiler would optimize and generate the same code for it. So dont ever say, I was taught to do it this way, and so never thought about the other ways.
 
There is another way of doing it, i.e. by using goto statement, goto is very basic keyword, which is more like an assembly jump instruction, if one finds more confortable with goto then possibly he works closely with assembly language, or with FORATN.
 
loop:
 ...
 ...
goto loop;
 
 
14) Data declarations
 
a) int a; 
An integer
 
b) int *a; 
A pointer to an integer
 
c) int **a; 
A pointer to a pointer to an integer
 
d) int a[10]; 
An array of 10 integers
 
e) int *a[10]; 
An array of 10 pointers to integers
 
f) int (*a)[10]; 
A pointer to an array of 10 integers
 
g) int (*a)(int); 
A pointer to a function a that takes an integer argument and returns an integer
 
h) int (*a[10])(int); 
An array of 10 pointers to functions that take an integer argument and return an integer
 
People often claim that a couple of these are the sorts of thing that one looks up in textbooks and I agree. While writing this article, I consulted textbooks to ensure the syntax was correct. However, I expect to be asked this question (or something close to it) when I'm being interviewed. Consequently, I make sure I know the answers, at least for the few hours of the interview. Candidates who don't know all the answers (or at least most of them) are simply unprepared for the interview. If they can't be prepared for the interview, what will they be prepared for? 
 
 
15) What are the uses of the keyword static?
 
This simple question is rarely answered completely. Static has three distinct uses in C:
 
  • A variable declared static within the body of a function maintains its value between function invocations

  • A variable declared static within a module, (but outside the body of a function) is accessible by all functions within that module. It is not accessible by functions within any other module. That is, it is a localized global.
      
  • Functions declared static within a module may only be called by other functions within that module. That is, the scope of the function is localized to the module within which it is declared
 
Most candidates get the first part correct. A reasonable number get the second part correct, while a pitiful number understand the third answer. This is a serious weakness in a candidate, since he obviously doesn't understand the importance and benefits of localizing the scope of both data and code.
 
 
16) Bit manipulation : Embedded systems always require the user to manipulate bits in registers or variables. Given an integer variable a, write two code fragments. The first should set bit 3 of a. The second should clear bit 3 of a. In both cases, the remaining bits should be unmodified.
 
These are the three basic responses to this question:
 
  1. No idea. The interviewee cannot have done any embedded systems work
     
  2. Use bit fields. Bit fields are right up there with trigraphs as the most brain-dead portion of C. Bit fields are inherently non-portable across compilers, and as such guarantee that your code is not reusable. The moral: never let a non-embedded person anywhere near a real piece of hardware
     
  3. Use #defines and bit masks. This is a highly portable method and is the one that should be used.
     
My optimal solution to this problem would be:
 
 
#define BIT3 (0x1 << 3)
static int a;
 
void set_bit3(void) {
    a |= BIT3;
}
 
void clear_bit3(void) {
    a &= ~BIT3;
}
 
Some people prefer to define a mask together with manifest constants for the set and clear values. This is also acceptable. The element that I'm looking for is the use of manifest constants, together with the |= and &= ~ constructs 
 
17) Accessing fixed memory locations
 
Embedded systems are often characterized by requiring the programmer to access a specific memory location. On a certain project it is required to set an integer variable at the absolute address 0x67a9 to the value 0xaa55. The compiler is a pure ANSI compiler. Write code to accomplish this task.
 
This problem tests whether you know that it is legal to typecast an integer to a pointer in order to access an absolute location. The exact syntax varies depending upon one's style. However, I would typically be looking for something like this:
 
int *ptr;
ptr = (int *)0x67a9;
*ptr = 0xaa55;
 
A more obscure approach is:
*(int * const)(0x67a9) = 0xaa55;
 
Even if your taste runs more to the second solution, I suggest the first solution when you are in an interview situation.
 
 
18) Interrupts and ISR
Interrupts are an important part of embedded systems. Consequently, many compiler vendors offer an extension to standard C to support interrupts. Typically, this new keyword is __interrupt. The following code uses __interrupt to define an interrupt service routine (ISR). Comment on the code.
 
__interrupt double compute_area (double radius)
{
    double area = PI * radius * radius;
    printf("\nArea = %f", area);
    return area;
}
 
This function has so much wrong with it, it's hard to know where to start:
 
  1. ISRs cannot return a value. If you don't understand this, you aren't hired
  2. ISRs cannot be passed parameters. See the first item for your employment prospects if you missed this
  3. On many processors/compilers, floating-point operations are not necessarily re-entrant. In some cases one needs to stack additional registers. In other cases, one simply cannot do floating point in an ISR. Furthermore, given that a general rule of thumb is that ISRs should be short and sweet, one wonders about the wisdom of doing floating-point math here
  4. In a vein similar to the third point, printf() often has problems with reentrancy and performance.
 
If you missed points three and four, I wouldn't be too hard on you. Needless to say, if you got these last two points, your employment prospects are looking better and better.
 
Code examples
19) What does the following code output and why?

void foo(void)
{
    unsigned int a = 6;
    int b = -20;
    (a+b > 6) ? puts("> 6") :puts("<= 6");
}

This question tests whether you understand the integer promotion rules in C-an area that I find is very poorly understood by many developers. Anyway, the answer is that this outputs "> 6." The reason for this is that expressions involving signed and unsigned types have all operands promoted to unsigned types. Thus comes a very large positive integer and the expression evaluates to greater than 6. This is a very important point in embedded systems where unsigned data types should be used frequently. If you get this one wrong, you are perilously close to not getting the job. 
 
 
20) Comment on the following code fragment.
unsigned int zero = 0;
unsigned int compzero = 0xFFFF;
/*1's complement of zero */

On machines where an int is not 16 bits, this will be incorrect.
 
It should be coded: unsigned int compzero = ~0;
 
This question really gets to whether the candidate understands the importance of word length on a computer. In my experience, good embedded programmers are critically aware of the underlying hardware and its limitations, whereas computer programmers tend to dismiss the hardware as a necessary annoyance.

By this stage, candidates are either completely demoralized-or they're on a roll and having a good time. If it's obvious that the candidate isn't very good, then the test is terminated at this point. However, if the candidate is doing well, then I throw in these supplemental questions.
These questions are hard, and I expect that only the very best candidates will do well on them. In posing these questions, I'm looking more at the way the candidate tackles the problems, rather than the answers. Anyway, have fun...
 

Dynamic memory allocation

21) Although not as common as in non-embedded computers, embedded systems do still dynamically allocate memory from the heap. What are the problems with dynamic memory allocation in embedded systems?
Here, I expect the user to mention memory fragmentation, problems with garbage collection, variable execution time, and so on. This topic has been covered extensively in ESP , mainly by P.J. Plauger. His explanations are far more insightful than anything I could offer here, so go and read those back issues! Having lulled the candidate into a sense of false security, I then offer up
this tidbit:
What does the following code fragment output and why?

char *ptr;
if ((ptr = (char *)malloc(0)) == NULL)
    puts("Got a valid pointer");
else
    puts("Got a null pointer");

This is a fun question. I stumbled across this only recently when a colleague of mine advertently passed a value of 0 to malloc and got back a valid pointer! That is, the above code will output "Got a valid pointer." I use this to start a discussion on whether the interviewee thinks this is the correct thing for the library routine to do. Getting the right answer here is not nearly as important as the way you approach the problem and the rationale for your decision.
 
 
22. Typedef is frequently used in C to declare synonyms for pre-existing data types. It is also possible to use the preprocessor to do something similar. For instance, consider the following code fragment:
#define dPS struct s *
typedef struct s * tPS;


The intent in both cases is to define dPS and tPS to be pointers to structure s. Which method, if any, is preferred and why?
 
This is a very subtle question, and anyone who gets it right (for the right reason) is to be congratulated or condemned ("get a life" springs to mind). The answer is the typedef is preferred. Consider the declarations:
dPS p1,p2;
tPS p3,p4;
The first expands to:
struct s * p1, p2;

which defines p1 to be a pointer to the structure and p2 to be an actual structure, which is probably not what you wanted. The second example correctly defines p3 and p4 to be pointers.

 
Obscure syntax
23. C allows some appalling constructs. Is this construct legal, and if so what does this code do?

int a = 5, b = 7, c;
c = a+++b;
This question is intended to be a lighthearted end to the quiz, as, believe it or not, this is perfectly legal syntax. The question is how does the compiler treat it? Those poor compiler writers actually debated this issue, and came up with the "maximum munch" rule, which stipulates that the compiler should bite off as big (and legal) a chunk as it can. Hence, this code is treated as:
c = a++ + b;
Thus, after this code is executed, a = 6, b = 7, and c = 12.
If you knew the answer, or guessed correctly, well done. If you didn't know the answer then I wouldn't consider this to be a problem. I find the greatest benefit of this question is that it is good for stimulating questions on coding styles, the value of code reviews, and the benefits of using lint.

3 comments:

  1. In Question no: 23,
    if it were to be a+++++b, then it would evaluate to a++ ++ +b, which is an invalid expression as second ++ needs an Lvalue, which does not present. So give error.

    ReplyDelete
  2. something seems to be wrong with the code in question 21.

    char *ptr;
    if ((ptr = (char *)malloc(0)) == NULL)
    puts("Got a valid pointer");
    else
    puts("Got a null pointer");

    The check should be != NULL instead of == NULL.

    Please confirm.

    ReplyDelete
  3. @Sid,

    Yes, you are right, let me correct it soon.
    Hope the explanation is clear, and good that you pointed it out.
    Thanks
    Prasad

    ReplyDelete