CareerCup

1. DMA controller.
Its a piece of intelligent hardware that helps transfer of chunk of data from/to a device/memory. This allows the CPU to do other job during the transfer. This is the theoretical answer one can give but in reality there can be many specifics associated with a DMA controller and associated transfer.

2. Cache coherency.- MESI /MSI protocol
MESI - Cache Coherency protocol used in x86 processors. M- Modified, E - Exclusive, S - Shared , I - Invalid
MSI - Message Signalled Interrupt - Again specific to x86 (latest processors). Doing a mem write in a specific memory mapped region, cause a x86 interrupt


3. Cache coherency mechanism.
MESI protocol is used to maitain cache coherency between processors and memory controllers

4. Interrupt handler.
A function registered to service a interrupt of a device

5. what happens when function1 calls function2 with it.(like where does the linkage register stuff get stored..and resume execution)
This is again processor specific stuff. On a x86 processor, its based on "ebp" register which holds the linkage across stack frames. The return address of the function will be the next address to "ebp" in the current stack frame.
In other processors the concept remains same but the designated registers differ. This is defined in ABI (Architecture Binary Interface) of the processor

6.Can u have reentrant code inside interrupt handler. (NO)
Yes. Interrupt code should be re-entrant coz the interrupt can be nested. This can be achieved using spin_lock_irqsave if you access global variables within the handler

7.What will happen/can u have printf/printk inside an interrrupt hancler (i think he wanted me to say no.. but I did not know the reason)
You can have printks in interrupt handlers but you will loose interrupts and the purpose of debugging is lost.

8.context switch.. when do u need it.
When a current executable moves from "running" state to any state other than running like pending, sleeping state, we need a context switch to run the other thread/process/executable which is in ready-to-run state

9.what does a interrupt handler take in as input... and what does it return.( it does not accept or return anything)
Interrupt handler does not return anything


10. what is the difference between ISR and interrupt handler.(Both are the same)
Both are same

11.how to search a book in one million books.
Its more of one's opinion rather than a one specific answer

12.How to check whether a linked list is circular.
As others mentioned, have two pointers moving faster and one pointer moving one after other. If the slow pointer meets any of the faster pointer, then the list is circular. If the list is not circular, either the fast or slow pointer will hit a NULL and we can use that as a condition to exit the function

DMA Controller:

Without DMA, the CPU is fully occupied with read and write operations. With DMA, CPU initiates transfer and handles other operations. CPU will be interrupted by DMA controller when the transfer is completed.

MSI Protocol: This is a cache coherency model where every cache block can be in either state Modified or Shared or Invalid.

If the cache block is modified, it can't be evicted with writing the data to the backing store(Memory Resource).

If the cache block is Shared, it is not modified and can be evicted without writing the block to the backing store.

If the cache is in invalid state, it must be fetched from the backing store to cache.

This problem occurs, if you have a shared memory resource and multiple CPUs each having a separate cache. Let us say the two CPUs, X and Y, having caches Xx and Yy. If X has same block of memory in its cache Xx and updates it. Y's cache would be containing stale data.

Cache coherency is used to maintain the integrity of data between cache and memory resources.

Interrupt Handler: Is a routine that gets executed by kernel for every interrupt. It can be called Interrupt Service Routine(ISR). Each device that generates interrupts will have a associated interrupt handler. For example, one routine handles the interrupts from keyboard, and other routine handles interrupts from the system timer.

How to check whether a linked list is circular -

O(n) solution:
Have 2 pointers A & B at the head of the linked list. Make pointer A traverse the list one node at a time. Make the second pointer B traverse the list 2 nodes at a time. Check if A & B point to the same location after every iteration of A & B. If they point to the same location, the list is circular.

1) Remember the starting location.
2) Traverse the list following the pointer chain. Eventually either one of 2 things
will happen: the ->next pointer will point to the starting location , or it will be null. In the 1st case the list is circular. The problem is contrived.
You should never have to do this in code you control (DUH, JUST LOOK AT THE SOURCE CODE). If the list is "enemy territory" ie. you do not know anything about its design e.g. you are messing with a list in the os w/o knowing the necessary locks you need to hold for safe traversal, it is unsafe to traverse it as it can get modified while you do and you may crash. Your safest bet is to reverse the rules based on observing code, ie learn from docs, co-workers, docs...

another note on circular lists: these tend to be double linked. Since there is no apparent end to append to, both adding and deleting list members tend to happen at random locations. This is much easier to do if there are both ->flink-s and ->blink-s.

7) You are not allowed to block inside an interrupt handler. Printf-s (io generally) may block. This is because interrupt handlers can not be scheduled. They typically steal their cycles and stack (os dependent) from the process that happens to be running on the interrupted cpu. Only kernel threads (processes) can be scheduled.
Repeat after me: interrupts are not running in process context, hence they are not schedulable. Hence they are not allowed to block.

11) The problem as stated is incomplrehensible to me. Perhaps: you have 1 million books. 2 of them are duplicates. Find the duplicate in a reasonably efficient way.

Hint: compute a hash of each book, and compare hashes instead of complete book texts. whatever your problem is, this will make it easier. :-)

To Sunny Paglaa....

How dumb one can get??? if you dont find a NULL how does your program stop?????