· 8 years ago · Aug 15, 2018, 08:16 PM
1...work in progress
2
3
4
5Programming Facts
6
7
81. Decrements loops are faster than increment loops
9
10For terminating condition processor has direct instruction to compare to zero
11
12
13
142. ++i executes faster than i+1
15
16The expression ++i requires a single machine instruction such as INR to carry out the increment operation.
17
18In case of i+1, apart from INR, other instructions are required to load the value of i. That is why ++i is faster.
19
20
21
22errno is thread-local; setting it in one thread does not affect its value in any other thread.
23
24
25
26
27
28
29
30Wild Pointer
31
32User space and kernel space
33
34User space refers to all code that runs outside the operating system's kernel
35
36Preemptive multitasking
37
38Permits preemption tasks
39
40
41
42
43
44
45
46
47
48Interview Questions
49OS Fundamentals
50Process and Threads
51
52
53
54Process
55
56Program in execution. A program is a passive entity while a process is an active entity.
57
58
59Multitasking Operating system
60
61
62An operating system on a single-processor machine is multitasking if it can interleave the execution of more than one process, giving the illusion of there being more than one process running at the same time.
63On multiprocessor machines, a multitasking operating system allows processes to actually run in parallel, on different processors.
64A non multitasking operating system, such as DOS, can run only one application at a time.
65
66
67Multitasking operating systems come in two variants: cooperative and preemptive.
68
69
70Preemptive:
71
72
73
74Linux implements preemptive multitasking, where the scheduler decides when one process is to stop running, and a different process is to resume running.
75We call the act of suspending a running process in lieu of another preemption.
76The length of time a process runs before the scheduler preempts it is known as the process’s time-slice.
77
78
79Cooperative:
80
81
82
83In cooperative multitasking, conversely, a process does not stop running until it voluntarily decides to do so.
84We call the act of a process voluntarily suspending itself yielding.
85Ideally, processes yield often, but the operating system is unable to enforce.
86A broken program can run for a longer than optimal time, or even bring down the entire system.
87Due to the shortcomings of this approach, modern operating systems are almost universally preemptively multi tasked.
88
89
90
91
92I/O Bound vs Processor-Bound vs Memory-Bound Processes
93Processor bound Processes
94
95
96
97Processes that continually consume all of their available timeslices are considered processor-bound. Such processes are hungry for CPUtime, and will consume all that the scheduler gives them.
98The simplest trivial example is an infinite loop. Other examples include scientific computations, mathematical calculations, and image processing.
99I/O Bound Process
100
101On the other hand, processes that spend more time blocked waiting for some resource than executing are considered I/O-bound.
102I/O-bound processes are often issuing and waiting for file I/O, blocking on keyboard input, or waiting for the user to move the mouse. Examples of I/O-bound applications include file utilities that do very little except issue system calls asking the kernel to perform I/O, such as cp or mv, and many GUI applications, which spend a great deal of time waiting for user input.
103Memory Bound Process
104
105Memory bound means the rate at which a process progresses is limited by the amount memory available and the speed of that memory access.
106A task that processes large amounts of in memory data, for example multiplying large matrices, is likely to be Memory Bound.
107
108
109Process Priorities
110In Linux, applications are assigned priorities that affect when their processes run, and for how long.
111Unix has historically called these priorities nice values, because the idea behind them was to “be nice†to other processes on the system by lowering a process’ priority, allowing other processes to consume more of the system’s processor time.The nice value dictates when a process runs.
112Linux schedules runnable processes in order of highest to lowest priority: a process with a higher priority runs before a process with a lower priority. The nice value also dictates the size of a process’ time-slice.
113Legal nice values range from –20 to 19 inclusive, with a default value of 0. Somewhat confusingly, the lower a process' nice value, the higher its priority, and the larger its time-slice; conversely, the higher the value, the lower the process' priority, and the smaller its time-slice. Increasing a process’ nice value is therefore “nice†to the rest of the system. The numerical inversion is rather confusing.
114When we say a process has a "high priority" we mean that it is chosen more quickly to run, and can run for longer than lower-priority processes, but such a process will have a lower nice value.
115
116
117There are two variants of the protocol: Original Ceiling Priority Protocol (OCPP) and Immediate Ceiling Priority Protocol (ICPP). The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. Both variants work by temporarily raising the priorities of tasks.[2]
118
119In OCPP, a task X's priority is raised when a higher-priority task Y tries to acquire a resource that X has locked. The task's priority is then raised to the priority ceiling of the resource, ensuring that task X quickly finishes its critical section, unlocking the resource. A task is only allowed to lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks. Otherwise the task becomes blocked, waiting for the resource.[2]
120
121In ICPP, a task's priority is immediately raised when it locks a resource. The task's priority is set to the priority ceiling of the resource, thus no task that may lock the resource is able to get scheduled. This ensures the OCPP property that "A task can only lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks".[2]
122
123
124
125Process
126
127
128
129A running instance of a program is called process.
130Each process in a Linux system is identified by its unique process ID, sometime referred to as pid.
131Every process also has a parent process. Parent process id is also known as ppid.
132
133```
134#include <stdio.h>
135#include <unistd.h>
136
137int main ()
138{
139 printf (“The process ID is %d\nâ€, (int) getpid ());
140 printf (“The parent process ID is %d\nâ€, (int) getppid ());
141 return 0;
142}
143```
144
145First Header | Second Header
146------------ | -------------
147Content from cell 1 | Content from cell 2
148Content in the first column | Content in the second column
149
150You can kill a running process with the kill command. Simply specify on the command line the process ID of the process to be killed.
151The kill command works by sending the process a SIGTERM, or termination, signal. This causes the process to terminate, unless the executing program explicitly handles or masks the SIGTERM signal.
152
153
154As a process executes, it changes state. The state of a process is defined in part by the current activity of that process. A process may be in one of the following states:
155
156• New. The process is being created.
157
158• Running. Instructions are being executed.
159
160• Waiting. The process is waiting for some event to occur (such as an I/O completion or reception of a signal).
161
162• Ready. The process is waiting to be assigned to a processor.
163
164• Terminated. The process has finished execution.
165
166
167
168Process Control Block (PCB)/ Task Control Block
169
170Zombie Process
171
172
173A process that has terminated, but whose parent has not yet called wait(), is known as a zombie process.
174All processes transition to this state when they terminate, but generally they exist as zombies only briefly. Once the parent calls wait(), the process identifier of the zombie process and its entry in the process table are released.
175Orphan Process
176
177
178Now consider what would happen if a parent did not invoke wait() and instead terminated, thereby leaving its child processes as orphans.
179Linux and UNIX address this scenario by assigning the init process as the new parent to orphan processes.
180
181
182
183
184
185
186
187A process is independent if it cannot affect or be affected by the other processes executing in the system. Any process that does not share data with any other process is independent.
188
189
190
191A process is cooperating if it can affect or be affected by the other processes executing in the system.
192
193
194
195Cooperating processes require an inter-process communication (IPC) mechanism that will allow them to exchange data and information.
196
197
198
199There are two fundamental models of inter-process communication:
200
201 1. Shared memory
202
203 2. Message passing.
204
205
206
207
208fork() vs vfork()
209Thread Levels
210There are two broad categories of thread implementation:
211
212User-Level Threads -- Thread Libraries.
213Kernel-level Threads -- System Calls.
214There are merits to both, in fact some OSs allow access to both levels (e.g. Solaris).
215User-Level Threads (ULT)
216In this level, the kernel is not aware of the existence of threads. All thread management is done by the application by using a thread library. Thread switching does not require kernel mode privileges (no mode switch) and scheduling is application specific
217
218
219
220Kernel activity for ULTs:
221
222The kernel is not aware of thread activity but it is still managing process activity.
223When a thread makes a system call, the whole process will be blocked but for the thread library that thread is still in the running state.
224So thread states are independent of process states.
225Advantages:
226
227Thread switching does not involve the kernel -- no mode switching
228Scheduling can be application specific -- choose the best algorithm.
229ULTs can run on any OS -- Only needs a thread library
230Disadvantages:
231
232Most system calls are blocking and the kernel blocks processes -- So all threads within the process will be blocked
233The kernel can only assign processes to processors -- Two threads within the same process cannot run simultaneously on two processors
234Kernel-Level Threads (KLT)
235In this level, All thread management is done by kernel. No thread library but an API (system calls) to the kernel thread facility exists. The kernel maintains context information for the process and the threads, switching between threads requires the kernel Scheduling is performed on a thread basis.
236
237
238Advantages
239
240Kernel can simultaneously schedule many threads of the same process on many processors blocking is done on a thread level
241Kernel routines can be multi-threaded
242Disadvantages:
243
244Thread switching within the same process involves the kernel, e.g if we have 2 mode switches per thread switch this results in a significant slow down.
245Combined ULT/KLT Approaches
246Idea is to combine the best of both approaches
247
248Solaris is an example of an OS that combines both ULT and KLT (Figure 1)
249
250Thread creation done in the user space
251Bulk of scheduling and synchronization of threads done in the user space
252The programmer may adjust the number of KLTs
253Process includes the user's address space, stack, and process control block
254User-level threads (threads library) invisible to the OS are the interface for application parallelism
255Kernel threads the unit that can be dispatched on a processor
256Lightweight processes (LWP) each LWP supports one or more ULTs and maps to exactly one KLT
257
258
259
260
261
262Daemons
263A daemon is a process that runs in the background, not connecting to any controlling terminal.
264Daemons are normally started at boot time, are run as root or some other special user (such as apache or postfix), and handle system-level tasks.
265As a convention, the name of a daemon often ends in d (as in crond and sshd), but this is not required, or even universal.
266A daemon has two general requirements:
267
268 It must run as a child of init,
269
270 It must not be connected to a terminal.
271
272
273In general, a program performs the following steps to become a daemon:
274
275
276Call fork( ). This creates a new process, which will become the daemon.
277In the parent, call exit( ). This ensures that the original parent (the daemon’s grandparent) is satisfied that its child terminated, that the daemon’s parent is no longer running, and that the daemon is not a process group leader. This last point is a requirement for the successful completion of the next step.
278Call setsid( ), giving the daemon a new process group and session, both of which have it as leader. This also ensures that the process has no associated controlling terminal (as the process just created a new session, and will not assign one).
279Change the working directory to the root directory via chdir( ). This is done because the inherited working directory can be anywhere on the filesystem. Daemons tend to run for the duration of the system’s uptime, and you don’t want to keep some random directory open, and thus prevent an administrator from unmounting the filesystem containing that directory.
280Close all file descriptors. You do not want to inherit open file descriptors, and, unaware, hold them open.
281Open file descriptors 0, 1, and 2 (standard in, standard out, and standard error) and redirect them to /dev/null.
282Compiling and Linking
283$ gcc -O2 -g -o p main.c swap.c
284
285
286
2871. C preprocessor translates the C source file into ASCII intermediate file main.i
288
289
290
291 $ cpp [other arguments] main.c /tmp/main.i
292
293
294
2952. C compiler main.i into ASCII assembly file main.s
296
297
298
299 $ cc1 /tmp/main.i main.c -O2 [other arguments] -o /tmp/main.s
300
301
302
3033. Assembler(as) translates main.s into relocatable object file main.o
304
305
306
307 $ as [other arguments] -o /tmp/main.o /tmp/main.s
308
309
310
3114. Linker links all the required object files to create a final executable file
312
313
314
315 $ ld [other arguments] /tmp/main.o -o output
316
317
318
319Static Linking and Dynamic Linking
320RTOS
3211. what is priority inversion, how does it happen in RTOS
322
323
324
325There are two variants of the protocol: Original Ceiling Priority Protocol (OCPP) and Immediate Ceiling Priority Protocol (ICPP). The worst-case behaviour of the two ceiling schemes is identical from a scheduling view point. Both variants work by temporarily raising the priorities of tasks.[2]
326
327In OCPP, a task X's priority is raised when a higher-priority task Y tries to acquire a resource that X has locked. The task's priority is then raised to the priority ceiling of the resource, ensuring that task X quickly finishes its critical section, unlocking the resource. A task is only allowed to lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks. Otherwise the task becomes blocked, waiting for the resource.[2]
328
329In ICPP, a task's priority is immediately raised when it locks a resource. The task's priority is set to the priority ceiling of the resource, thus no task that may lock the resource is able to get scheduled. This ensures the OCPP property that "A task can only lock a resource if its dynamic priority is higher than the priority ceilings of all resources locked by other tasks".[2]
330
331
332
333Misc:
334
335
336
3371. Reentrant vs Thread safe function?
338
339Re-entrant function/code
340A piece of code is said to be re-entrant if it can be executed in parallel by more than one thread. Generally, if a piece of code is using any global symbols (variables or functions with global variables) is said to be non re-entrant.
341
342
343
344Ex. printf function is non re-entrant as it uses global symbols.
345
346
347
348
349static int sum = 0;
350
351int increment(int i)
352
353{
354
355 sum += i;
356
357 return sum;
358
359}
360
361
362
363This code can be made re-entrant with following modification
364
365
366
367
368int increment(int sum, int i)
369
370{
371
372 return sum + i;
373
374}
375
376Thread-safe function
377Thread-safe functions can be invoked simultaneously by multiple threads, even if each invocation references or provides the same data or input, as all access is serialized.
378
379
380Following code is thread-safe, as shared resource is protected by mutex lock. Any number of threads can call this function simultaneously, as access is serialized.
381
382
383
384
385static int sum = 0;
386
387int increment(int i)
388
389{
390
391 mutex_lock(&my_mutex);
392
393 sum += i;
394
395 mutex_unlock(&my_mutex);
396
397 return sum;
398
399}
400
401
402
403If function is using any static/global data then it is said to be Non reentrant function.
404
405
406
4072. Volatile keyword?
408
409
410volatile keyword is used to inform compiler to use data from main memory not from cached
411
412
413
4143. Can a variable be both const and volatile?
415
416--> Yes
417
418
4194. What is NULL pointer and what is its use?
420
421--> Not pointing a valid location
422
423
424
4255. What is void pointer and what is its use?
426
427-->
428
429
4306. What is size of character, integer, integer pointer, character pointer?
431
432
4337. what is virtual function?
434
435
436
437Race condition.
438
439Race conditions are a result of uncontrolled access to shared data.
440Race condition arises when two or more threads tries to access same resource at the same time.
441Mutex:
442
443Mutex stands for mutual exclusion.
444Mutex is used to protect shared resource from simultaneous access from different threads.
445Basically you serialize access to the shared resource.
446
447
448Ex.
449
450 {
451
452 mutex_lock(&my_mutex);
453
454
455
456 ---critical region of code---
457
458
459 mutex_unlock(&my_mutex);
460
461 }
462
463
464
465Semaphore:
466
467
468
469A semaphore is a special type of variable that can be incremented or decremented, but crucial access to the variable is guaranteed to be atomic, even in a multi-threaded program.
470
471
472
473Two types:
474
475
476
4771. Counting semaphore : Counting semaphore is used to protect finite number of resources
478
479
480
4812. Binary semaphore : Binary semaphore as name suggests, takes values either 0 or 1.
482
483
484
485
486
487Native applications[*] can invoke a system call in two different ways:
488
489
490
491
492
493By executing the int $0x80 assembly language instruction; in older versions of the Linux kernel,this was the only way to switch from User Mode to Kernel Mode.·By executing the sysenter assembly language instruction, introduced in the Intel Pentium IImicroprocessors; this instruction is now supported by the Linux 2.6 kernel.
494
495
496
497Hard link vs soft link
498
499
500
501
502
503Memory can be assigned on stack using alloca
504
505Programming Questions
506Bit Manipulation
5071. Write a program to test endianess of storage.
508
509
510
511#include <stdio.h>
512
513int main()
514
515{
516
517 unsigned int i = 1;
518
519 char *c = (char*)&i;
520
521 if (*c)
522
523 printf("Little endian");
524
525 else
526
527 printf("Big endian");
528
529 getchar();
530
531 return 0;
532
533}
534
535
536
5372. Implement strcpy function and show me if there are any limitation of this function. what if the 2 buffers passed to the strcpy function overlaps.
538
5393. Implement memcpy function.
540
541
542
5434. write a function that determines if a given variable is a power of 2 or not
544
5455. write a function that count number bits set in a 32 bit integer number.
546
547int numOfBitsSet(int num)
548
549{
550
551 unsigned int count = 0;
552
553
554
555 while (num)
556
557 {
558
559 num = num & (num-1);
560
561 count++;
562
563 }
564
565 return count;
566
567}
568
569
570
571Structures
5726. Delete a node from an XOR-linked list
573
5748. Finding a path(Maze problem)
575
576
577
578Linkedlist
5797. Find if a linked list is circular or not
580
5819. Deep copy a binary search tree
582
58310. Delete an item in a LinkedList
584
585
586
587Dynamic Programming
588
589
590
591
592JTAG
593
594The connector pins are
595
5961. TDI (Test Data In)
597
5982. TDO (Test Data Out)
599
6003. TCK (Test Clock)
601
6024. TMS (Test Mode Select)
603
6045. TRST (Test Reset) optional
605
606
607
608unsigned int test;
609std::cin >> test;
610while(test --)
611{
612 unsigned int n,k,x;
613 std::cin >> n >> k;
614 unsigned int sum[n];
615 sum[0] = 0;
616 int cnt[k]={};
617 cnt[0] = 1;
618 for(int i = 1; i <= n; i ++)
619 {
620 std::cin >> x;
621 sum[i] = (sum[i-1] + x)%k;
622 cnt[sum[i]] ++;
623 }
624
625 long long res = 0;
626 for(int r = 0; r < k; r ++)
627 res += (cnt[r]*(cnt[r]-1)/2);
628
629 std::cout<< res << std::endl;
630
631}
632insmod vs modprobe
633modprobe is smart, it is aware of module paths and dependencies.
634It instructs insmod to load modules.
635Questions:
636
637 Bit manipulation
638
6391. Count the number of set bits in an integer.
640->
641 int noOfSetBits(int n)
642 {
643 int count =0;
644 while(n)
645 {
646 n = (n & (n-1));
647 count++;
648 }
649 return count;
650 }
651
6522. C program to reverse an 8 bit type
653->
654 #include <stdio.h>
655 #define CHAR_BIT 8
656 int main()
657 {
658 unsigned int v=0x01; // input bits to be reversed
659 unsigned int r = v & 1; // r will be reversed bits of v;
660 first get LSB of v
661 int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
662 printf("%x\n",v);
663 for (v >>= 1; v; v >>= 1)
664 {
665 printf("%x\n",v);
666 r <<= 1;
667 r |= v & 1;
668 s--;
669 printf("%x\n",r);
670 }
671 r <<= s; // shift when v's highest bits are zero
672 }
673
6743. Write a function that determines if a given variable is a power of 2
675 or not
6764. Write a C program to encode bits in a 32-bit number such that,
677 most significant 16 bits should be reversed but lower 16 bits should
678 be untouched.
6795. Write a function which takes the bit number of an integer as argument
680 and toggles it.
681
682
683Array
684
6851. Second was to find maximum sum sub-array of input array.
6862. Search in rotated sorted array
6873. Problem was to create an array from one input array where every element
688 in output array is the next biggest element from that element.
689
690String
691
6921. Reverse a string
6932. Reverse words in a string
6943. Find duplicates in a string
6954. Is palindrome?
6965. Given two strings are anagram
6976. Find the first non-recurring character in a string. i.e. input
698 "abbcdcaea" would return "d"
6997. Return the most frequent character in a string
7008.Write a program to remove duplicates continous characters in a string?
701
702
703
704Linked List
705
7061. Find mid point of a linked list
7072. Delete a node from given linked List
7083. Delete a given linked list
7094. Write code to find a point where two linked lists meet
7105. Merge k sorted linked list
7116. Detect loops in linked list
7127. Reverse a linked list
713
714 Matrix
715
7161. There is a N*M matrix where each row is sorted. Find the kth largest
717 element in matrix?
718
719 Tree
720
7211. Find if a given binary tree is BST.
7222. Given a BST, find k-th largest element with using extra space.
7233. Given a BST, find k-th largest element without using extra space.
7244. Maximum Sum path
725
726 Graph
727
7281. Do the bfs of a graph
7292. Given a graph, find out if it can be colored using 2 colors.
730Different colors for alternate nodes (3 hours) people who passed
731all 10 test cases were shortlisted. (BFS)
732
733
734C++
735
7361. What is the difference between class and object? Does class or object
737 create memory?
7382. Virtual destructor
7393. Virtual inheritance
7404. Pure virtual classes
7415. Pure virtual function
7426. Abstract class
7437. Implement typedef operator (function template can be used to write a
744 generic function.
7458. what is the difference between structures and classes in cpp In cpp \
746 class default access specifier is private, in structure it is public
747
7489. Describe Inheritance
749
750
751C
752
7531. my_sizeof implementation
754-> 1. #define my_sizeof(type) (char*)(&type+1)-(char *)(&type)
755 2. size_t size = (size_t)(1 + ((X*)0));
756
7572. Storage classes in C
758-> auto
759 register
760 static
761 extern
762 typedef (sometimes consider as storage class becuase of syntax used)
763
7643. What does appending 'static' to a global variable/function do?
765-> Limits the scope of that variable/function to that source file only.
766 If in the project we have multiple source files,then you can have same
767 name variable/function in other source file provided the earlier
768 declared one is static.
769
7704. Swap the values of two pointers without a temp variable
771-> *a = *a ^ *b;
772 *b = *a ^ *b;
773 *a = *a ^ *b;
774
7755. Difference between malloc and calloc
776->
777
7786. const pointers and pointers to const*
779->
780
7817. What is static keyword and its different use cases?
782-> 1. static variable inside a function retains it value.
783 2.
784
7858. What is volatile keyword
786->
787
78810. What are dangling pointers?
789-> If a pointer refers to the original memory after it has been freed,
790 it is called a dangling pointer.
791
792 ex.
793 int *ptr = (int *)malloc(SIZE);
794 free(ptr);
795
796 ptr is dangling pointer as it is pointing to same old memory which
797 is already free/Not valid
798
799 ptr = NULL; // Good practice
800
80111. What are Wild Pointers?
802-> Uninitialized pointers are known as wild pointers because they point
803 to some arbitrary memory location and may cause a program to crash.
804
80512. What is the difference between structures and unions?
806 When to use what? Sizes?
807->
808
809
81013. What is free()? how does free know how much memory to de-allocate?
811-> When you call malloc()/calloc(), you specify the amount of memory to
812 allocate.
813 The amount of memory actually used is slightly more than this, and
814 includes extra information that records (at least) how big the block
815 is. You can't (reliably) access that other information and nor should
816 you.When you call free(), it simply looks at the extra information to
817 find out how big the block is.
818
819
820
821Data structure and Algorithm
822
8231. Dijkstra’s Algorithm, pseudo code why Dijkstra’s algo fails when
824 -ve weights are there in the graph.
8252. Find the loop in the graph if it exist and print the
826 nodes of the loop in sorted order.
8273.
8284. Min heap
8295. Binary search
8306. Print sum of all prime numbers within a given range.
8317. Find the degrees between the minute hand and hour hand when a
832 clock is at 3:15
8339. Write code in C that would hash a string and deal with collision
834 resolution by implementing a linked list. Would this code be thread safe?
835
83616.One was to output the decimal number after inverting the binary
837 representation of input number.
838
839
840
841std::map
842
843
844key - value(mapped value) relation
845
846In a map, the key values are generally used to sort and uniquely identify the elements, while the mapped values store the content associated to this key.
847
848Types of key and mapped value may differ
849
850map containers are generally slower than unordered_map containers to access individual elements by their key, but they allow the direct iteration on subsets based on their order.
851
852Maps are typically implemented as binary search trees
853
854
855
856std::unordered_map
857
858
859key - value(mapped value) relation
860
861Types of key and mapped value may differ
862
863the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values,
864
865organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values
866
867
868
869Operating system + RTOS + Computer Architecture
870
871
8721. What is Virtual Memory
8732. Caches
8743. What is Priority inversion (RTOS)
875-> If the High priority task is blocked till the resource got free.
876 which is acquired by low priority task and if any middle priority
877 task becomes ready then it will preempt the low priority task.
878 So middle priority got chance to run evenif high priority ready task
879 is pending.This situation is called priority inversion.
880
881 Solution is to use Priority inheritance.
882 Task acuiring blocking the resource(who got the lock), gets the priority level
883 of highest priority task pending for that resource.
884
8854. What is Reentrancy
8865. Semaphore vs Mutex vs Spinlocks
887
8885. What is spinlock ? why it is a bad idea to use spinlock on uniprocessor
889 system?
890-> On a uniprocessor, it will either immediately acquire the lock or it
891 will spin forever - if the lock is contended, then there will never be
892 an opportunity for the process which currently holds the resource to
893 give it up. Spinlocks are only useful when another process can execute
894 while one is spinning on the lock - which means multiprocessor systems.
895
8966. What is Concurrency and Multi threading?
8977. Watchdog Timer
8988. How post increment works.
8999. Assembly implementation of spinlock?
90010. How does a debugger work?
90111. How do breakpoints in a C program works?
902
90312. How are interrupts handled in RTOS?
904--> Application code execution is interrupted (delayed) during the execution
905 of an ISR, most applications minimize the amount of code in the ISR and
906 rely instead on non ISR code (a “Task†is signaled using semaphore) to
907 complete the processing. This allows the highest priority application
908 code to be executed as quickly as possible, and delayed as little as
909 possible, even in situations with intense interrupt activity.
910
91113. What is atomic programming/non-locking operation?
912
91314. What is trashing? what happens during trashing? what is excessive
914 paging?
91515. big endian vs little endian, how to find
916->
917 #include <stdio.h>
918 int main()
919 {
920 unsigned int i = 1;
921 char *c = (char*)&i;
922 if (*c)
923 printf("Little endian");
924 else
925 printf("Big endian");
926 getchar();
927 return 0;
928 }
929
93016. What is dynamic loading? what is static loading? when to use dynamic
931 loading? What are the advantages? give an example when to use dynamic
932 loading?
93317. What are interrupts and if you have less external interrupt pins on a
934 processor, how to interface multiple interrupts?
93518. Difference between & and &&
93619. Process address space,Memory regions like stack, heap, text, data
937 segments.
938
939
940Design questions
941
942
9431. Design an elevator system
9442. Desing an LRU(Least recently use) system
9453. Are there any problems (from a embedded system point of view) you
946 should prevent and how will you prevent it in your design
9474. Write a program to create circular queue
9485. Design a Stack class (pop,push,top,size,getMin)
9496. Implement strcpy function, what if the 2 buffers passed to the strcpy
950 function overlaps ?
9517. Implement aligned malloc
9528. Implement memcpy function with two void pointers and size
9539. Implement a queue/fifo with push/pop functionality using linked lists
954
955 Brain teasers
956
9571. About seating in an airplane. Probability that last person gets a
958 correct seat.
959--> 1/2
960
961
962public boolean lock()
963{
964 if(!locked) {
965 locked = true;
966 return true;
967 }
968 return false;
969 }
970
971Compiler
972
973
974Assembly Language- Memory Write and Read implementation using Assembly.
975How multiply is implemented?
976
977
9781. How mutex and condition variable works?
979
980A thread obtains a mutex (condition variables always have an associated
981mutex) and tests the condition under the mutex’s protection. No other
982thread should alter any aspect of the condition without holding the mutex.
983If the condition is true, your thread completes its task, releasing the
984mutex when appropriate. If the condition isn’t true, the mutex is released
985for you, and your thread goes to sleep on the condition variable.
986When some other thread changes some aspect of the condition, it calls
987pthread_cond_signal(), waking up one sleeping thread.
988Your thread then reacquires the mutex, reevaluates the condition, and either
989succeeds or goes back to sleep, depending upon the outcome.
990You must reevaluate the condition!
991First,the other thread may not have tested the complete condition before sending
992the wakeup.
993Second, even if the condition was true when the signal was sent, it could
994have changed before your thread got to run.
995Third, condition variables allow for spurious wakeups.
996They are allowed to wakeup for no discernible reason whatsoever!
997
998
999Not all pages are candidates for swapping. Consider kernel code that responds to
1000interrupts or code that manages the page tables and swap logic. These are obvious
1001pages that should never be swapped out and are therefore pinned, or permanently
1002resident in memory.
1003Although kernel pages are not candidates for swapping, user space pages are,
1004but they can be pinned through the mlock (or mlockall) function to lock the page down.
1005This is the purpose behind the user space memory access functions.
1006
1007
10081. Why we need copy_from_user(as kernel already has access to user space
1009 memory)
1010-->If the kernel assumed that an address that a user passed was valid and
1011 accessible, a kernel panic would eventually occur (for example, because
1012 the user page was swapped out, resulting in a page fault in the kernel).
1013This application programming interface (API) ensures that those corner
1014
1015
1016cases are handled properly.
1017
1018
1019
1020
1021
1022
10231. Timer callback
1024
1025
1026
1027
1028
1029
1030
1031
1032CISC
1033
1034RISC
1035
1036Emphasis on hardware
1037
1038Emphasis on software
1039
1040Includes multi-clock
1041
1042
1043complex instructions
1044
1045
1046Single-clock,
1047
1048
1049reduced instruction only
1050
1051
1052Memory-to-memory:
1053
1054
1055"LOAD" and "STORE"
1056
1057
1058incorporated in instructions
1059
1060
1061Register to register:
1062
1063
1064"LOAD" and "STORE"
1065
1066
1067are independent instructions
1068
1069
1070Small code sizes,
1071
1072
1073high cycles per second
1074
1075
1076Low cycles per second,
1077
1078
1079large code sizes
1080
1081
1082Transistors used for storing
1083
1084
1085complex instructions
1086
1087
1088Spends more transistors
1089
1090
1091on memory registers
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101Harvard architecture has separate data and instruction busses, allowing transfers to be performed simultaneously on both busses.
1102
1103
1104Von Neumann architecture has only one bus which is used for both data transfers and instruction fetches, and therefore data transfers and instruction fetches must be scheduled - they can not be performed at the same time.
1105
1106
1107
1108
1109
1110What is ACPI and what does ACPI mean?
1111
1112ACPI allows the operating system to communicate with the computer's BIOS and instruct the BIOS to power down peripherals. For example, when your computer goes into hibernation mode, the operating system is using the ACPI specification to control the power to the internal components.
1113
1114ACPI power states
1115ACPI specifies various modes, referred to as states, that control the power to the components of a PC.
1116
1117The 4 Global states:
1118Working (G0)
1119Sleeping (G1)
1120Soft Off (G2)
1121Mechanical Off (G3).
1122Within these Global states are various different Sleep states: S0, S1, S2, S3, S4 and S5.
1123
1124For example, when you have not moved your mouse or touched a key for a certain period of time the computer's monitor will power-down, this is actually Global state G0 with Sleep state S0.
1125
1126Another example is when your computer is put into hybernate mode, this is actually Global state G1 with Sleep state S4.
1127
1128The Global state G2 (Soft Off) is when the system is powered-down but can be brought back to life by the case's soft power button (usually located at the front of the PC) or other method such as "Wake-on-LAN". When a machine is in this state the case covers should never be removed as there is still residual power to the motherboard.
1129
1130The Global state G3 (Mechanical Off), as its name suggests, is when the system is completely powered-down by using the main power button of the computer's power supply unit (usually a rocker switch on the back). When in this mode, the PC can be disconnected from the power source and any maintenance, repairs or upgrades carried out.
1131
1132
1133
1134Writing a kernel in CUDA
1135
1136
1137
1138
1139As stated previously, CUDA can be taken full advantage of when writing in C. This is good news, since most programmers are very familiar with C. Also stated previously, the main idea of CUDA is to have thousands of threads executing in paralle. What wasn’t stated is that all of these threads are going to be executing the very same function, known as a kernel. Understanding what the kernel is and how it works is critical to your success when writing an application that uses CUDA. The idea is that even though all of the threads of your program are executing the same function, all of the threads will be working with a different dataset. Each thread will know it’s own ID, and based off it’s ID, it will determine which pieces of data to work on. Don’t worry, flow control like ‘if, for, while, do, etc.’ are all supported.
1140
1141
1142
1143
1144
1145
1146
1147CUDA
1148
1149The CUDA programming model is a heterogeneous model in which both the
1150CPU and GPU are used.
1151
1152In CUDA,
1153 host refers to the CPU and its memory
1154 device refers to the GPU and its memory
1155
1156Code run on the host can manage memory on both the host and device, and also launches kernels which are functions executed on the device.
1157
1158These kernels are executed by many GPU threads in parallel.
1159
1160
1161Given the heterogeneous nature of the CUDA programming model, a typical sequence of operations for a CUDA C program is:
1162
1163Declare and allocate host and device memory.
1164Initialize host data.
1165Transfer data from the host to the device.
1166Execute one or more kernels.
1167Transfer results from the device to the host.
1168
1169How to process an image in CUDA? How to map to threads? Is it memory-bound or compute-bound?
1170Describe how to implement the interface to ensure a certain
1171 block of code in a simple compiler is executed every so often(time dependent)
1172Write a version of the C function tail
11731. Explain the stack and heap areas in the process address space.
11742. Implement strncmp library function, bug free.
11753. How does the linux file system implement the access control.
11764. Webserver, incoming request. compare the following three approaches, pros and cons
1177 1) one request, fork one process to response 2) process pool 3) producer and consumer.