Embedded System and Firmware Interview Questions Collection

Cache Miss

2011-01-09T01:38:00.003-08:00

3 Kinds of Cache Miss

Compulsory
Capacity
Conflict

Reduce Miss Rate

Larger Block Size — compulsory
Higher Associativity — conflict
Victim Cache — conflict
HW Prefetching Instruction, Data — compulsory
SW Prefetching Data — compulsory
Compiler Optimizations

Reduce Miss Penalty

Read priority over write on miss
Early Restart and CriticalWord First on miss
Non-blocking Caches (Hit Under Miss)
Multi-level Caches

Cache Bus

2011-01-09T01:38:00.001-08:00

Cache Size is 64KB, Block size is 32B and the cache is Two-Way Set Associative. For a 32-bit physical address, give the division between Block Offset, Index and Tag.

Number of Blocks:
64k/32 = 2048
Index:
2 way set associative — 2000/2 = 1000 lines-> 10 bits for index
Block Offset:
32B block -> 5 bits for block offset
Tag:
32-10-5= 17 bits for tag

Snooping vs Snarfing

2011-01-09T01:37:00.003-08:00

Snooping is the process where the individual caches monitor address lines for accesses to memory locations that they have cached. When a write operation is observed to a location that a cache has a copy of, the cache controller invalidates its own copy of the snooped memory location.
Snarfing is where a cache controller watches both address and data in an attempt to update its own copy of a memory location when a second master modifies a location in main memory

Write Back vs Write Through

2011-01-09T01:37:00.001-08:00

Write-Through cache: In this, once the writing is done in the cache memory, the main memory is also updated immediately to maintain the reliability.
Write-Back cache: In this, once the writing is done in the cache memory, a flag bit known as dirty bit is set. It write the data back to the main memory after a period of time or when the data is swapped out of the cache.

The differences between the Write-through and Write-back cache can be based on two factors (i.e Performance and Integrity of Data). The write-through has a better integrity and it will also flush for each writes. The write-back will hold up the write till the same cache line has to be used up for a read. Thus, write-back will proivde good performance, as it save many memory write cycles

Memory Mapped IO vs Port IO

2011-01-09T01:36:00.003-08:00

Memory-mapped I/O (MMIO) and port I/O (also called port-mapped I/O or PMIO) are two complementary methods of performing input/output between the CPU and peripheral devices in a computer.
Memory-mapped I/O (not to be confused with memory-mapped file I/O) uses the same address bus to address both memory and I/O devices, and the CPU instructions used to access the memory are also used for accessing devices. In order to accommodate the I/O devices, areas of the CPU's addressable space must be reserved for I/O. The reservation might be temporary — the Commodore 64 could bank switch between its I/O devices and regular memory — or permanent. Each I/O device monitors the CPU's address bus and responds to any of the CPU's access of device-assigned address space, connecting the data bus to a desirable device's hardware register.
Port-mapped I/O uses a special class of CPU instructions specifically for performing I/O. This is generally found on Intel microprocessors, specifically the IN and OUT instructions which can read and write one to four bytes (outb, outw, outl) to an I/O device. I/O devices have a separate address space from general memory, either accomplished by an extra "I/O" pin on the CPU's physical interface, or anentire bus dedicated to I/O.

DMA

2011-01-09T01:36:00.001-08:00

DMA Advantage

DMA is a hardware device that helps the data transmission between hardware device and memory. Computers that have DMA can transfer data to and from devices with much less CPU overhead than computers without a DMA.

Without DMA, using programmed input/output (PIO) mode for communication with peripheral devices , or load/store instructions in the case of multicore chips(with polled waiting loop or interrupt driven IO), the CPU is typically fully occupied for the entire duration of the read or write operation, and is thus unavailable to perform other work. With DMA, the CPU would initiate the transfer, do other operations while the transfer is in progress, and receive an interrupt from the DMA controller once the operation has been done. This is especially useful in real-time computing applications where not stalling behind concurrent operations is critical. Another and related application area is various forms of stream processing where it is essential to have data processing and transfer in parallel, in order to achieve sufficient throughput.

Single Mode & Burst Mode

Traditional Synchronous DMA moves a byte or word at a time between system memory and a peripheral, handshaking with the I/O port for each transfer. This sort of transfer recognizes that the port may not always be in a ready condition; the handshaking is a hardware mechanism to throttle the transactions.

With this sort of transfer, the program sets up the controller and then carries on, oblivious to the state of the DMA transaction. The hardware moves one byte or word between memory and I/O each time the I/O port signals it is ready for another transaction. On each read indication, the DMA controller asserts Bus Request, waits for a Bus Acknowledge in response, and then takes over the bus for a single cycle. Then, the DMA controller goes idle again, waiting for another ready signal from the port. Thus, the program and DMA cycles share bus cycles, with the controller winning any contest for control of the bus. Sometimes this is called "Cycle Stealing".

Burst Mode DMA, in contrast, generally assumes that the destination and source addresses can take transfers as fast as the controller can generate them. The program sets up the controller, and then (perhaps after a single ready indication from a port occurs), the entire source block is copied to the destination. The DMA controller gains exclusive access to the bus for the duration of the transfer, during which time the program is effectively shut down. Burst mode DMA can transfer data very rapidly indeed.

Reference

http://www.ganssle.com/articles/adma.htm — Good DMA article

RISC vs CISC

2011-01-09T01:35:00.001-08:00

The major difference is that RISC has fewer number of instructions and each of them performs simpler function, has simpler format, and most instructions have the same number of clock cycles, so we can apply pipeline technique to improve performance. On the other hand, CISC processors have a large amount of different, complex instructions, and each of them may require various number of clock cycles and contain various number of bits. RISC processor has better performance, but CISC processor can has code which has much less lines than RISC processor. Moreover, CISC typically requires more hardware resource to support its powerful instructions, therefore also has higher power consumption. For example, CISC may has a dedicated hardware for multiplication, while RISC may combine shift and add instruction to achieve multiplication.

Pipeline

2011-01-09T01:33:00.001-08:00

Multiple Cycle CPU

as its name implies, the multiple cycle cpu requires multiple cycles to execute a single instruction. this means that our cpi will be greater than 1.

the big advantage of the multi-cycle design is that we can use more or less cycles to execute each instruction, depending on the complexity of the instruction. for example, we can take five cycles to execute a load instruction, but we can take just three cycles to execute a branch instruction. the big disadvantage of the multi-cycle design is increased complexity. control is now a finite state machine - before it was just combinational logic.

another important difference between the single-cycle design and the multi-cycle design is the cycle time. in the single cycle processor, the cycle time was determined by the slowest instruction. in the multi-cycle design, the cycle time is determined by the slowest functional unit [memory, registers, alu]. this greatly reduces our cycle time.

Outline

this outline describes all the things that happen on various cycles in our multi-cycle cpu. all the events described in each numbered item take place in one clock cycle.

1) instruction fetch: load ir with instruction at pc, load pc with pc + 4. If its not a branch instruction, pc+4 will be used to fetch instruction in the next clock cycle. If its a branch instruction, taken or non-taken will be resolved after after 2 clock cycles (after ALU). At the 3th cycle, pc+4 or branch address will be selected to fetch the instruction.
2) instruction decode, read registers: parse the instruction, load registers A and B with values from the register file, load aluout with the target address of the branch
3) execute: if executing a load or store, perform the effective address computation and put the result in aluout. for arithmetic instructions, load aluout with the result of the appropriate computation. for a beq instruction, if the result of register A is zero, load pc with the value in aluout. if executing a beq, we are done - return to step 1
4) memory: if executing a load, load mdr with the data at address aluout. if executing a store, write the data in register b into memory at address aluout. if executing an arithmetic instruction, write the value in aluout into the register file. if executing a store or an arithmetic instruction, we are done - return to step 1
5) writeback: if we are here, we are executing a load instruction. write the value in mdr into the register file, and return to step 1

Pipeline Performance

Ideally, for an n stages pipeline, the performance improvement is n times than non-pipeline structure. However, mostly it can not be achieved, because:
1) uneven pipeline stages: we can hardly separate task to stages with the same execution time.
2) hazards: so we can't always let the pipeline full.
3) latch overhead

Reference

http://www.cs.umass.edu/~weems/CmpSci535/Discussion14.html — instruction fetch
http://cseweb.ucsd.edu/~j2lau/cs141/week4.html — pipeline & multiple cycle

Hazards

2011-01-09T01:31:00.001-08:00

A hazard is a potential problem that can cause a pipelined processor to obtain incorrect computing result. There are typically three types of hazards: data hazards, structural hazards, and branching hazards (control hazards).

Data Hazard

Data hazard can happen when a CPU tries to simultaneously execute multiple instructions which exhibit data dependence

RAW - Read After Write

A RAW Data Hazard refers to a situation where we refer to a result that has not yet been calculated, for example:
i1. R2 <- R1 + R3
i2. R4 <- R2 + R3
The first instruction is calculating a value to be saved in register 2, and the second is going to use this value to compute a result for register 4. However, in a pipeline, when we fetch the operands for the 2nd operation, the results from the first will not yet have been saved, and hence we have a data dependency.
We say that there is a data dependency with instruction 2, as it is dependent on the completion of instruction 1.

WAR - Write After Read

A WAR Data Hazard represents a problem with concurrent execution, for example:
i1. R4 <- R1 + R3
i2. R3 <- R1 + R2
If we are in a situation that there is a chance that i2 may be completed before i1 (i.e. with concurrent execution) we must ensure that we do not store the result of register 3 before i1 has had a chance to fetch the operands.

WAW - Write After Write

A WAW Data Hazard is another situation which may occur in a concurrent execution environment, for example:
i1. R2 <- R1 + R2
i2. R2 <- R4 + R7
We must delay the WB (Write Back) of i2 until the execution of i1.

Solutions

1) data forwarding: some data hazards can't be solved by it. Ex. lw instruction in MIPS architecture
2) pipeline stall: Ex. for lw instruction
3) instruction scheduling: Compiler should do that. Ex.

lw R1, 1000(R2)
lw R3, 2000(R2)
add R4, R1, R3
lw R1, 3000(R2)
add R6, R4, R1
sw R6, 1000(R2)

change to

lw R1, 1000(R2)
lw R3, 2000(R2)
lw Rn, 3000(R2) // swap "lw" and "add"
add R4, R1, R3
add R6, R4, Rn
sw R6, 1000(R2)

Structural Hazard

A structural hazard occurs when a part of the processor's hardware is needed by two or more instructions at the same time. A structural hazard might occur, for instance, if a program were to execute a branch instruction followed by a computation instruction. Because they are executed in parallel, and because branching is typically slow (requiring a comparison, program counter-related computation, and writing to registers), it is quite possible (depending on architecture) that the computation instruction and the branch instruction will both require the ALU (arithmetic logic unit) at the same time.

Branch Harzard

Branching hazards (also known as control hazards) occur when the processor is told to branch - i.e., if a certain condition is true, then jump from one part of the instruction stream to another - not necessarily to the next instruction sequentially. In such a case, the processor cannot tell in advance whether it should process the next instruction (when it may instead have to move to a distant instruction).
This can result in the processor doing unwanted actions.
1) stall pipeline: until we know its taken or non-taken
2) predict taken or non-taken: and fill the pipeline with associated instruction. Compiler uses like taken and unlikely taken to denote the branch instruction, and if its found not the case, CPU cancel or nullify the delayed slot instruction.
3) delayed branch: Fill instruction that will be valid no matter branch is taken or non-taken into pipeline. Compiler should do that.
4) hardware branch predictor: Its dynamic branch prediction. static branch prediction is done by compiler.

Reference

http://en.wikipedia.org/wiki/Hazard_(computer_architecture)

Harvard Vs Von Neuman

2011-01-09T01:30:00.000-08:00

Difference

With a Harvard architecture, there are two separate memory space, one for instruction and one for data. We can increase the throughput because when we are executing one instruction, we can be fetching the next instruction. Other advantage is that, we can have different width on instruction bus and data bus.

Reference

http://www.pictutorials.com/Harvard_vs_Von_Nuemann_Architecture.htm

Reentrant Function

2011-01-09T01:26:00.001-08:00

Definition

A reentrant function is one that can be used by more than one task concurrently without fear of data corruption. Conversely, a non-reentrant function is one that cannot be shared by more than one task unless mutual exclusion to the function is ensured either by using a semaphore or by disabling interrupts during critical sections of code. A reentrant function can be interrupted at any time and resumed at a later time without loss of data. Reentrant functions either use local variables or protect their data when global variables are used.

A reentrant function:
1) Does not hold static data over successive calls
2) Does not return a pointer to static data; all data is provided by the caller of the function
3) Uses local data or ensures protection of global data by making a local copy of it
4) Must not call any non-reentrant functions

Floating Point Reentrant for Keil C51 C compiler

Floating point operations the compiler generates code for (+ - * /) are fully reentrant. But only a few functions in math.h are reentrant.

Those that are not reentrant must be protected from interrupts. One way this can be accomplished is to put a wrapper that disables and re-enables interrupts around the floating point math calls. For example:

#pragma disable // Disable Interrupts for this function

float ISR_sin (float x)

{

return (sin(x));

}

Examples

void func(int* x, int* y)

{

int tmp;

tmp=*x;

*x=*y;

*y=tmp;

}

the above is reentrant or not?
Reentrant

Non-Reentrant to Reentrant

Non-reentrant version

char* FileName(char *name)

{

static char fname[13];

sprintf(fname, "%s", name); // can't write fname = name

return fname;

}

Reentrant versions

char* FileName1(char *name, char *fname_buf) // use thread's own buffer

{

sprintf(fname_buf, "%s", name); // can write fname_buf = name

return fname_buf;

}

char* FileName2(char *name)

{

char *fname_buf = (char*)malloc(13); // malloc will allocate memory every call

sprintf(fname_buf, "%s", name); // can write fname_buf = name

return fname_buf;

}

The first one better, because second requires free() to release memory, and takes longer time to allocate memory.

Inter Process Communication

2011-01-09T01:24:00.001-08:00

Advantages of process cooperation

Information sharing
Computation speed-up
Modularity
Convenience

Disadvantage of process cooperation

Data corruption, deadlocks, increased complexity
Requires processes to synchronize their processing

Event Flags

http://www.ecoscentric.com/ecospro/doc.cgi/html/ref/kernel-flags.html

Shared Memory

If threads are in different process, we need to request a segment of shared memory from kernel, and processes communicate through this shared memory by reading and writing data on it.
If threads are in the same process, there are several types of shared memory:
1) Shared global variable: global variables within source code of multiple threads.
2) Shared private data: private variables whose address are given to other threads.
3) Static variable: all static variables within a shared function will become shared data. All functions which are called in a shared function are also shared functions.
With shared memory, synchronization should be achieved by processes/threads themselves to avoid data corruption.

Message Passing

In message passing, there is no shared memory between processes. Using kernel function, kernel will copy data from the source process to kernel space, and then copy the data from kernel space to destination process. There are basically two operations,send(pid, message) and receive(pid, message). Synchronization and data protection are handled by kernel.

Blocking & Non-Blocking

Blocking Send — sender blocked until message received by mailbox or process
Nonblocking Send — sender resumes operation immediately after sending
Blocking Receive — receiver blocks until a message is available
Nonblocking Receive — receiver returns immediately with either a valid or null message.

Buffering

All messaging system require framework to temporarily buffer messages. These queues are implemented in one of three ways:

Zero Capacity — No messages may be queued within the link, requires sender to block until receives retrieves message.
Bounded Capacity — Link has finite number of message buffers. If no buffers are available(buffer is full) then sender must block until one is freed up.
Unbounded Capacity — Link has unlimited buffer space, consequently send never needs to block. It can be approximated by linked list, while it still has a boundary (when heap section is full).

Polled Waiting vs Interrupt Driven

2011-01-09T01:22:00.001-08:00

Real-time systems are said to be “event-driven”, meaning that a primary function of the system is to respond to “events” that occur in the system’s environment. How does the program detect an event happening? There are two fundamental approaches:

Polled Waiting

The program begins with some initialization and then enters an infinite loop that tests each possible event to which the system must respond. For each event that is set, the program invokes the appropriate servicing function.

int main (void)

    sys_init();

    while (TRUE)

        if (event_1)

            service_event_1();

        if (event_2)

            service_event_2();

        // ........

        if (event_n)

            service_event_n();

When to use

Fast device: for devices which input or output data in very fast speed, it won't execute useless loops for many times, so won't introduce much overhead. However, if we use interrupt driven IO, the overall overhead generated by dealing with interrupts may be very high.
Periodic device: we can let the task which run the polled waiting loop sleep for a period of time, and wake up it when the data is about ready.

Disadvantage

The response time to an event varies widely depending on where in the loop the program is when the event occurs. For example, if event_1 occurs immediately before the if (event_1) statement is executed, the response time is very short. However if it occurs immediately after the test, the program must go through the entire loop before servicing event_1.
For slow device, introduce huge overhead because of busy waiting.
All events are treated as having equal priority (If all event are tested in the same process).
As new features, hence new events are added to the system, the loop gets longer and so does the response time.
The response time is also a function of how many events happen to be set at the same time and consequently get serviced in the same pass through the loop.

Interrupt Driven

When to use

Slow and Non-periodic device: for this kind of device, interrupt driven IO can achieve much higher performance than polled waiting.
Device requires guaranteed short latency: since polled waiting IO introduce various latency.

Disadvantage

It has large overhead/byte, therefore low transfer rate when transmits one or few bytes of data per interrupt. It needs to 1. push program counter, flag register. 2. read interrupt type code, access interrupt vector table, load address of ISR. 3. after that, it might need to push values of all register that will be used in the ISR. 4. when the ISR return, CPU need to restore it previous status by popping values from stack to registers.
According to the above reason, for device which has high speed, the overhead introduced by interrupt driven IO will be significant.
Increase complexity, and introduce problem of synchronization.

Reference

http://0rz.tw/iRpLY

Multi Tasking or Multi Thread

2011-01-09T01:19:00.000-08:00

In embedded system, process and thread are often called task. The only reason for multitasking is because most tasks spend most of their execution time on waiting for an event or timeout happen. If we can run other pieces of codes when waiting for an event, performance must increase a lots. The benefit of multitasking is (1) avoid long response time due to waiting for event, (2) better utilize resource, keep them all busy. The following shows typical task code:

void task (void *data)

    init_task();

    while (TRUE)

        Wait for message at task mailbox();

        // go to pending(blocked) queue if message is not ready

        switch (message.type)

            case MESSAGE_TYPE_X:

            // ...

            break;

            case MESSAGE_TYPE_Y:

            // ...

            break;

It is similar to code of polled waiting, but they are different things. After initialization, it runs a infinite loop which is to wait for a specific event or message, and then processes the message. In a typical embedded system, tasks are viewed as backgroundprocedures, and the ISR that provides the message are viewed as foreground procedures.

How does it work

Semaphore

When the task tries to obtain message data, it calls Wait() on a semaphore. If message has not been ready, the task is blocked. When the corresponding ISR generates the message, the ISR calls Signal() on this semaphore, and wake up the task. The task can then process the data.

System call

When the task tries to obtain message data, it call the system call Block() if the data has not been ready, so CPU will execute other tasks. When the corresponding ISR generates the message, the ISR first calls a system call to change the status of this task from pending to ready, and then calls a system call to execute the CPU scheduler. After that, the scheduler might (or might not, may depend on the priority) wake up the task to process the data.

OS concept - Synchronization

2011-01-09T01:15:00.000-08:00

Synchronization is an important concept in Operating System. Producer/Consumer and Reader/Writer are two examples of synchronization problems. The following is the sample codes for them.

Producer and Consumer

int buf[N], in = 0, out = 0;

sem filledslots = 0, emptyslots = N, mutex = 1;

Producer()

    wait(emptyslots);   //synchronization start

    wait(mutex);        //critical section start

    Produce(buf[in]);

    in = (in + 1) % N;

    signal(mutex);      //critical section end

    signal(filledslots);//synchronization end

Consumer()

    wait(filledslots);  //synchronization start

    wait(mutex);        //critical section start

    Consume(buf[out]);

    out = (out + 1) % N;

    signal(mutex);      //critical section end

    signal(emptyslots); //synchronization end

Reader and Writer

int n = 0;

sem mutex = 1, RW = 1;

Reader()

    wait(mutex);   // lock reader

    n++;

    if (n == 1)

        wait(RW);  // lock first reader when there is a writer

    signal(mutex);

    Read();

    wait(mutex);

    if (n == 1)

        signal(RW);

    n--;

    signal(mutex);

Writer()

    wait(RW);      // wait if at least one reader is reading

    Write();

    signal(RW);

Interrupt Vector Table

2011-01-09T01:01:00.000-08:00

When the system is booted up or reseted, the interrupt is disabled because interrupt mechanism is not initialized.
Therefore, after booting up, one important task is to initialize interrupt mechanism. For all system, we need to setup ISR's address.
Typically, ISR's addresses are stored in interrupt vector table, and each device is assigned a specific number as the index to the interrupt vector table for accessing their corresponding ISR (however, some architectures are slightly different, such as ARM).
The number assigned to each device are system dependent (ex. for lpc2103… not processor dependent).
Interrupt vector table (its address, and so on) is processor dependent.

ISR

2011-01-09T00:59:00.000-08:00

You must be asked questions about ISR in every firmware or embedded system interview!

Interrupt Service Routine

http://book.opensourceproject.org.cn/embedded/oreillyembed/opensource/0596009836/id-i_0596009836_chp_8_sect_3.html
A single ISR (single interrupt) may be triggered by multiple source, then the ISR must include a condition test to determine which source causes this interrupt. Moreover, if multiple source trigger the interrupt at the same time, the ISR must detect it, or it will result in interrupt missing.

Difference between ISR and normal function

1) ISR has no parameter
2) ISR has no return value
3) ISR is asynchronous to instruction flow
4) ISR is triggered by hardware event
5) ISR can't call blocking function or non-reentrant function, such as printf()
6) ISR should be as short as possible, shouldn't call function which require long time to execute, such as printf(), floating point function…
7) ISR can't be blocked, can't wait on semephor, but can signal

Debugging ISR

http://www.ganssle.com/articles/dbg-isr1.htm — ISR debugging 1
http://www.ganssle.com/articles/dbg-isr2.htm — ISR debugging 2

Little Endian & Big Endian

2011-01-09T00:58:00.000-08:00

Little Endian and Big Endian is an important concept in Embedded System and Firmware field. People who don't understand it will not be hired; people who clearly understands it and answer this kind of questions well can impress the interviewers.

Different machines (CPU + OS) might use different Endianness. For example, Linux and Windows on x86 is Little Endian, but Linux on MIPS is Big Endian.

In the following article, we use the integer 0x12345678 to illustrate the definitions of Little/Big Endian.

Little Endian

"Little Endian" means that the Low Significant Byte of a data is stored in memory at the lowest address, and the High Significant Byte at the highest address.

mem addr	data
0x4000	0x78
0x4001	0x56
0x4002	0x34
0x4003	0x12

Big Endian

"Big Endian" means that the High Significant Byte of a data is stored in memory at the lowest address, and the Low Significant Byte at the highest address.

mem addr	data
0x4000	0x12
0x4001	0x34
0x4002	0x56
0x4003	0x78

The advantage of Big Endian is that you can always determine whether a number is positive of negative by looking at the byte at offset zero, you don't need to know how long the number is, nor to skip over any bytes to find the byte containing the sign information. Also, when you print a number, you can print it from lowest bytes to highest bytes, and that is more easy and efficient.

Write a program to check the Endianness (Little or Small) on your machine

union {   // please make sure you understand "union"
    unsigned int i;    
    unsigned char c;
} u;
int main()
{
    u.i = 1;
    if(u.c == 1)
        printf("little edian\n");
    else 
        printf("big endian\n");

Interrupt

2011-01-09T00:55:00.000-08:00

What is Interrupt

Hardware Interrupt — A hardware interrupt is a signal which can tell the CPU that something happen in hardware device, and should be immediately responded. A interrupt causes the processor to save its state of execution and begin execution of an interrupt service routine.

Software Interrupt — Software interrupt is an instruction which cause a context switch to an interrupt handler similar to a hardware interrupt. Usually it is an interrupt generated within a processor by executing an instruction. Software interrupts are often used to implement system calls.

Interrupt Latency

when an interrupt fires, the microprocessor executes an interrupt service routine (ISR). The amount of time that elapses between a device interrupt request and the first instruction of the corresponding ISR is known as interrupt latency.

Reduce Interrupt Latency

We should make all ISR as short as possible, because other ISR that has lower priority will be blocked by it.
If we disable interrupt in an ISR or process for protecting critical sections, we should enable it as early as possible. Once we finish the task which is non-reentrant in an ISR, its time to enable interrupt.
We can also reenable all ISR before the current ISR finish its non-reentrant task. Therefore, the current ISR won't degrade the latency of other ISR. However, we need to prevent interrupt overrun by setting up the corresponding mask bit or using a static to notify the ISR is currently triggered. Notice that preventing interrupt overrun means that some interrupts will miss.
Use inline assembly language to replace some lines of ISR code in C, and reduce some overhead introduced by C.

http://en.wikipedia.org/wiki/Interrupt

Interrupt vs Exception

The definitions are different everywhere. Here are some reasonable conclusions I made:

Interrupt includes hardware interrupt and software interrupt; Exception includes trap, fault, and abort.
Hardware interrupt is asynchronous, and others (exceptions and software interrupt) are synchronous to instructions.
Software interrupt are used to implement system call. In intel processor, we use INT instruction. In MIPS we use syscall.

Ex. Fork() System Call — Intel x86 & Linux

__asm__ (

"movl $2, %%eax\n\t" // move 2 into eax, 2 is the number for fork() system call

"int $0x80\n\t" // int 0x80 execute a software interrupt that deal with system call

:"=a" (chPid) // return value of Fork()

);

Ex. Open() System Call — MIPS

Void open (char *file_name) {

asm {

load OpenSystemCallNum, r8

move filename, r9

syscall // when syscall is executed, CPU load PC with address stored in interrupt vector table

} // using OpenSystemCallNum as the table index, and jump to the associated ISR

}

Software interrupt and trap are sometime considered as the same thing. That's why some definitions say system call is trap.

IRQ & FIQ (ARM based CPU)

"IRQ is serviced at a normal priority level and FIQ is serviced at high priority level."

FIQ is the fast interrupt i.e. the latency time taken is less because in the FIQ mode (in case of ARM architecture where these modes are encountered) the mode has an additional set of 7 general purpose registers which means in case of the banked registers there is no need to store these registers into stack when the interrupt occurs.

That means only r0 to r7 need to be stored while moving from User mode to FIQ mode whereas while moving from User mode to IRQ mode r0 to r12 needs to be stored.

Reference

http://www.cs.fsu.edu/~xyuan/cop4610/lecture_2_concurrency.ppt

String (2)

2011-01-09T00:12:00.000-08:00

Return the 1st non-repeated character: Ex."aaaaaaak47" return 'k'
char find_first_nonrepeat(char *str)  
{
    char *c1 = str;
    char pre_c = *c1;
 
    while (*c1 != '\0' && *c1 == pre_c)
    {       
        pre_c = *c1; // If the same as previous char,
        c1++;        // add c1 by 1 and go to next char
    }

    if (*c1 == '\0') // Be careful the special case!
        return 0;    // => all chars are the same
    else
        return *c1; // This is to return a char, not pointer                     
}

Convert an Integer to a String
char* num2str(int num, char *str)
{
    char *c, *c2;
    for (c = str; num; num/=10, c++)
        *c = num % 10 + '0';
    *c = '\0';
    c2 = c - 1;
    c = str;        // After that we need to reverse the string,
                    // since string c starts from lower digit.
    while (c < c2) {// It is a different way to reverse a string
        *c ^= *c2;    
        *c2 ^= *c;
        *c++ ^= *c2--;
    }
    return str;
}

Compare 2 strings. If equal return 1, else return 0
int Same(char *s1, char *s2)
{
    char *c1, *c2;
    c1 = s1;
    c2 = s2;
    while (*c1 != '\0' && *c2 != '\0' && *c1 == *c2) {
        c1++;
        c2++;
    }
    if (*c1 == '\0' && *c2 == '\0')
        return 1;  // If while loop goes to the end => equal
    else
        return 0;
}

Linked List (4)

2011-01-09T00:00:00.000-08:00

Find the middle item in a Linked List

int find_middle(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next; // p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;// when p1 to the end, p2 points to middle
    }
 
    return p2;
}

Determine if there is a loop in a Linked List
bool find_loop(node *head)
{
    node *p1, *p2;
    p1 = p2 = head;
 
    while (p1 != NULL && p1->next != NULL) {
        p1 = p1->next->next;// p1 goes 2 steps; p2 goes 1 step
        p2 = p2->next;
        if (p1 == p2) // If there is loop, we must get p1 == p2 
            return true;  // sooner or later
    }
 
    return false;     // If goes out of the while, no loop.
}

Find merge point of two Linked Lists (if there is one)
Node* Find_merge_point(Node *h1, Node *h2)
{
    Node *p1, *p2;
 
    int n = Length1(h1) - Length1(h2); 
    if (n >= 0) {  // make p1 to be longer one 
        p1 = h1;
        p2 = h2;
    }
    else {
        n *= -1;
        p1 = h2;
        p2 = h1;
    }
 
    while (n--)// n is the length diff. between p1 and p2
        p1 = p1->next; // make p1 and p2 "aligned" 
 
    while (p1 != p2 && p1 != NULL && p2 != NULL) {
        p1 = p1->next; // start to check merge point
        p2 = p2->next;
    }
 
    if (p1 == NULL || p2 == NULL) {
        printf("can't find merge point!\n");
        return NULL;
    }
    else
        return p1;
}

Linked List (3)

2011-01-08T23:56:00.000-08:00

Sum up values of all items in a Linked List (items are integers)

int Sum(Node *head)
{
    if (head == NULL)
        return 0;
    else
        return head->data + Sum(head->next);
}

Print all items in a Linked List
void Print1(Node *head)
{
    if (head == NULL) // Special Case! head is null!
        return;
    else {
        printf("%d ", head->data);
        Print1(head->next);
    }
}

Reversely print all items
void Print(Node *head)
{
    if (head == NULL)
        return;
    else {
        Print(head->next);        // Recursively call itself, 
        printf("%d ", head->data);// so last one is printed first.

    }
}

Find the last Mth item: Ex.find the last 2th in 1->4->5->2->9->0->3->Null => 0
Node* Find_Mth_Last(Node **head, int M)
{
    Node *p1, *p2;
    p1 = *head;
 
    while (M >= 0 && p1 != NULL) { // p1 goes to Mth first
        p1 = p1->next;             
        M -= 1;
    }
 
    if (M != -1) {  // if we can find out, M == -1, not M == 0
        printf("can't find Mth, because its shorter than M!");
        return NULL;
    }
 
    p2 = *head;         // p2 points to 1st
    while (p1 != NULL) {// when p1 to the end, p2 points to Mth
        p1 = p1->next;    
        p2 = p2->next;
    }
 
    return p2;
}

Linked List (2)

2011-01-08T23:53:00.000-08:00

Insert an item into a Circular Linked List

int insert_circular(node **head, int data)
{
    node *p1;
    node *new = (node*)malloc(sizeof(node));
    new->value = data;
 
    if (*head == NULL) { 
        *head = new;
        *head->next = *head;   // for circular linked list 
        return new->value;
    } 
 
    p1 = *head;
    while (p1->next != *head) {// find the node before head
        p1 = p1->next;
    }
 
    p1->next = new;            // insert head
    new->next = *head;
    *head = new;
 
    return new->value;
}

Insert an item into a Double Linked List
int insert_double(node** head, int num) 
{
 
        node *p0, *p1, *p2;
    p2 = (node*)malloc(sizeof(node));
    p2 -> data = num;         
    if (*head == null) {
        *head = p2;
        p2->prev = null;
        return num;
    }
    p1 = *head;
    while (p1 != NULL && p1->data > num) {
        p0 = p1;
        p1 = p1->next;
    }
    if (p1 == *head) {    // Special Case!
        p2->next = p1;
        p2->prev = NULL;
        *head = p2;
    }
    else {
        p0->next = p2;
        p2->prev = p0;
        p2->next = p1;
        if (p1 != NULL)
            p1->prev = p2;
    }
 
    return num;
}

Delete an item in a Linked List
Node* Remove(Node *head, int value)
{
    Node *p0, *p1, *temp;
    p1 = head;
 
    while (p1 != NULL && p1->data != value) {
        p0 = p1;
        p1 = p1->next;
    }
 
    if (p1 == NULL) {               // Special Case! can't find
        printf("can't find item\n");
    }
    else if (p1 == head) {       // Special Case! find out at head
        head = head->next;
        free(p1);
    }
    else {                       // otherwise
        p0->next = p1->next;
        free(p1);
    }
 
    return head;
}

Reverse a Linked List: Ex. 1->7->5->3->Null => 3->5->7->1->Null
Node* Reverse(Node* head)
{
    Node *p0, *p1, *temp;
    p0 = NULL;
    p1 = head;
 
    while (p1 != NULL) {// reverse linked list
        temp = p1->next;// you could draw a linked list on paper,
        p1->next = p0;  // to understand why it reverses the list.
        p0 = p1;
        p1 = temp;
    }
 
    return p0;       // if head == NULL, p0 is also NULL
}

Linked List (1)

2011-01-08T23:50:00.000-08:00

Linked List is a very important data structure in Firmware field. Almost all Firmware interviewers will ask at least 1 linked list question! Here are many linked list questions and their example solution. If you cannot understand the example solution in the first glance, you could draw the linked list on a paper to help you understand each line of code.
Before you go for a firmware interview, please make sure you can solve each question within 15 minutes. After practicing all of these questions (or most of them), you should be able to handle all linked list questions in your interview.

Create Linked List

Node* Create()
{
    int input;
    Node *p0, *p1, *head;
    p0 = (Node*)malloc(sizeof(Node)); // create a dummy head
    p1 = p0;
 
    while (scanf("%d", &input)) {
        p1->next = (Node*)malloc(sizeof(Node));
        p1 = p1->next;
        p1->data = input;
    }
 
    p1->next = NULL;             // kill the dummy head now
    head = p0->next;
    free(p0);
 
    return head;
}

Insert an item to the head of a Linked List

int insert(node **head, int data)
{
    node *new;
    new = (node*)malloc(sizeof(node));
 
    new->value = data;
    new->next = *head;
    *head = new;
 
    return new->value;
}

Insert an item into a sorted Linked List: Ex.insert 4 into 1->3->7->8 => 1->3->4->7->8
Node* Insert_Sorted(Node *head, int value)
{
    Node *p0, *p1, *new;
    new = (Node*)malloc(sizeof(Node));
    new->data = value;
 
    p1 = head;
    while (p1 != NULL && p1->data <= value) {
        p0 = p1;
        p1 = p1->next;
    }
 
    if (p1 == head) {   // be careful Special Case! 
        head = new;     // may stop at the head!
        new->next = p1;
    }
    else {              // otherwise
        p0->next = new;
        new->next = p1;
    }    
 
    return head;
}

Dynamic Memory Allocation

2011-01-08T19:10:00.000-08:00

In a software or firmware interview, you may be asked about dynamic memory allocation in different way.

What is dynamically memory allocation?
dynamic memory allocation (heap-based memory allocation) is the allocation of memory storage during the runtime of that program. Dynamically allocated memory exists until it is released either explicitly by the programmer. It is said that this object has a dynamic lifetime.

How to dynamically allocate memory in C?
malloc() provides dynamic memory allocation.

void * malloc ( size_t size )

The type of returned pointer is *void since malloc doesn't know how you are going to use the allocated memory, so you need to cast it before using.

Memory Leak
When you don't need the allocated memory anymore, you must free it by calling free(). If you forgot to do it, the allocated memory will be always reserved and the system cannot use it, it is so called memory leak.

free() releases the allocated memory.

void free ( void *p )

Example
   int *pA ;
        pA = ( int *) malloc (sizeof (int) * 10 ) ; //allocate 10 int ( 40 bytes )
   //use the allocated memory here
   free(pA); //release the memory

Where is the dynamically allocated memory located?
The memory allocated by using malloc will be located in heap section.