· 8 years ago · Aug 18, 2018, 08:56 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
259The ptrace() system call provides a means by which one process (the "tracer") may observe and control the execution of another process (the "tracee"), and examine and change the tracee's memory and
260registers. It is primarily used to implement breakpoint debugging and system call tracing.
261
262
263Daemons
264A daemon is a process that runs in the background, not connecting to any controlling terminal.
265Daemons 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.
266As a convention, the name of a daemon often ends in d (as in crond and sshd), but this is not required, or even universal.
267A daemon has two general requirements:
268
269 It must run as a child of init,
270
271 It must not be connected to a terminal.
272
273
274In general, a program performs the following steps to become a daemon:
275
276
277Call fork( ). This creates a new process, which will become the daemon.
278In 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.
279Call 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).
280Change 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.
281Close all file descriptors. You do not want to inherit open file descriptors, and, unaware, hold them open.
282Open file descriptors 0, 1, and 2 (standard in, standard out, and standard error) and redirect them to /dev/null.
283Compiling and Linking
284$ gcc -O2 -g -o p main.c swap.c
285
286
287
2881. C preprocessor translates the C source file into ASCII intermediate file main.i
289
290
291
292 $ cpp [other arguments] main.c /tmp/main.i
293
294
295
2962. C compiler main.i into ASCII assembly file main.s
297
298
299
300 $ cc1 /tmp/main.i main.c -O2 [other arguments] -o /tmp/main.s
301
302
303
3043. Assembler(as) translates main.s into relocatable object file main.o
305
306
307
308 $ as [other arguments] -o /tmp/main.o /tmp/main.s
309
310
311
3124. Linker links all the required object files to create a final executable file
313
314
315
316 $ ld [other arguments] /tmp/main.o -o output
317
318
319
320Static Linking and Dynamic Linking
321RTOS
3221. what is priority inversion, how does it happen in RTOS
323
324
325
326There 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]
327
328In 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]
329
330In 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]
331
332
333
334Misc:
335
336
337
3381. Reentrant vs Thread safe function?
339
340Re-entrant function/code
341-> It can be interrupted at any point during its execution and then safely called again ("re-entered") before its previous invocations complete execution.
342
343-> Re-entrance is something which is associated with a function whose first execution gets interrupted by second call to it (from within the same thread) and this first execution resumes when the second execution completes. This is not the case with threads which can keep on stepping onto another thread’s toes multiple times. So if a function is re-entrant then it does not guarantee that its thread safe.
344
345Ex. printf function is non re-entrant as it uses global symbols.
346
347static int sum = 0;
348int increment(int i)
349{
350 sum += i;
351 return sum;
352}
353
354This code can be made re-entrant with following modification
355
356int increment(int sum, int i)
357{
358 return sum + i;
359}
360
361Thread-safe function
362Thread-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.
363
364
365Following 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.
366
367static int sum = 0;
368
369int increment(int i)
370{
371 mutex_lock(&my_mutex);
372 sum += i;
373 mutex_unlock(&my_mutex);
374 return sum;
375}
376
377
378
379If function is using any static/global data then it is said to be Non reentrant function.
380
381
382
3832. Volatile keyword?
384
385
386volatile keyword is used to inform compiler to use data from main memory not from cached
387
388
389
3903. Can a variable be both const and volatile?
391
392--> Yes
393
394
3954. What is NULL pointer and what is its use?
396
397--> Not pointing a valid location
398
399
400
4015. What is void pointer and what is its use?
402
403-->
404
405
4066. What is size of character, integer, integer pointer, character pointer?
407
408
4097. what is virtual function?
410
411
412
413Race condition.
414
415Race conditions are a result of uncontrolled access to shared data.
416Race condition arises when two or more threads tries to access same resource at the same time.
417Mutex:
418
419Mutex stands for mutual exclusion.
420Mutex is used to protect shared resource from simultaneous access from different threads.
421Basically you serialize access to the shared resource.
422
423
424Ex.
425
426 {
427
428 mutex_lock(&my_mutex);
429
430
431
432 ---critical region of code---
433
434
435 mutex_unlock(&my_mutex);
436
437 }
438
439
440
441Semaphore:
442
443
444
445A 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.
446
447
448
449Two types:
450
451
452
4531. Counting semaphore : Counting semaphore is used to protect finite number of resources
454
455
456
4572. Binary semaphore : Binary semaphore as name suggests, takes values either 0 or 1.
458
459
460
461
462
463Native applications[*] can invoke a system call in two different ways:
464
465
466
467
468
469By 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.
470
471
472
473Hard link vs soft link
474
475
476
477
478
479Memory can be assigned on stack using alloca
480
481Programming Questions
482Bit Manipulation
4831. Write a program to test endianess of storage.
484
485
486
487#include <stdio.h>
488
489int main()
490
491{
492
493 unsigned int i = 1;
494
495 char *c = (char*)&i;
496
497 if (*c)
498
499 printf("Little endian");
500
501 else
502
503 printf("Big endian");
504
505 getchar();
506
507 return 0;
508
509}
510
511
512
5132. 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.
514
5153. Implement memcpy function.
516
517
518
5194. write a function that determines if a given variable is a power of 2 or not
520
5215. write a function that count number bits set in a 32 bit integer number.
522
523int numOfBitsSet(int num)
524
525{
526
527 unsigned int count = 0;
528
529
530
531 while (num)
532
533 {
534
535 num = num & (num-1);
536
537 count++;
538
539 }
540
541 return count;
542
543}
544
545
546
547Structures
5486. Delete a node from an XOR-linked list
549
5508. Finding a path(Maze problem)
551
552
553
554Linkedlist
5557. Find if a linked list is circular or not
556
5579. Deep copy a binary search tree
558
55910. Delete an item in a LinkedList
560
561
562
563Dynamic Programming
564
565
566
567
568JTAG
569
570The connector pins are
571
5721. TDI (Test Data In)
573
5742. TDO (Test Data Out)
575
5763. TCK (Test Clock)
577
5784. TMS (Test Mode Select)
579
5805. TRST (Test Reset) optional
581
582
583
584unsigned int test;
585std::cin >> test;
586while(test --)
587{
588 unsigned int n,k,x;
589 std::cin >> n >> k;
590 unsigned int sum[n];
591 sum[0] = 0;
592 int cnt[k]={};
593 cnt[0] = 1;
594 for(int i = 1; i <= n; i ++)
595 {
596 std::cin >> x;
597 sum[i] = (sum[i-1] + x)%k;
598 cnt[sum[i]] ++;
599 }
600
601 long long res = 0;
602 for(int r = 0; r < k; r ++)
603 res += (cnt[r]*(cnt[r]-1)/2);
604
605 std::cout<< res << std::endl;
606
607}
608insmod vs modprobe
609modprobe is smart, it is aware of module paths and dependencies.
610It instructs insmod to load modules.
611Questions:
612
613 Bit manipulation
614
6151. Count the number of set bits in an integer.
616->
617 int noOfSetBits(int n)
618 {
619 int count =0;
620 while(n)
621 {
622 n = (n & (n-1));
623 count++;
624 }
625 return count;
626 }
627
6282. C program to reverse an 8 bit type
629->
630 #include <stdio.h>
631 #define CHAR_BIT 8
632 int main()
633 {
634 unsigned int v=0x01; // input bits to be reversed
635 unsigned int r = v & 1; // r will be reversed bits of v;
636 first get LSB of v
637 int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end
638 printf("%x\n",v);
639 for (v >>= 1; v; v >>= 1)
640 {
641 printf("%x\n",v);
642 r <<= 1;
643 r |= v & 1;
644 s--;
645 printf("%x\n",r);
646 }
647 r <<= s; // shift when v's highest bits are zero
648 }
649
6503. Write a function that determines if a given variable is a power of 2
651 or not
6524. Write a C program to encode bits in a 32-bit number such that,
653 most significant 16 bits should be reversed but lower 16 bits should
654 be untouched.
6555. Write a function which takes the bit number of an integer as argument
656 and toggles it.
657
658
659Array
660
6611. Second was to find maximum sum sub-array of input array.
6622. Search in rotated sorted array
6633. Problem was to create an array from one input array where every element
664 in output array is the next biggest element from that element.
665
666String
667
6681. Reverse a string
6692. Reverse words in a string
6703. Find duplicates in a string
6714. Is palindrome?
6725. Given two strings are anagram
6736. Find the first non-recurring character in a string. i.e. input
674 "abbcdcaea" would return "d"
6757. Return the most frequent character in a string
6768.Write a program to remove duplicates continous characters in a string?
677
678
679
680Linked List
681
6821. Find mid point of a linked list
6832. Delete a node from given linked List
6843. Delete a given linked list
6854. Write code to find a point where two linked lists meet
6865. Merge k sorted linked list
6876. Detect loops in linked list
6887. Reverse a linked list
689
690 Matrix
691
6921. There is a N*M matrix where each row is sorted. Find the kth largest
693 element in matrix?
694
695 Tree
696
6971. Find if a given binary tree is BST.
6982. Given a BST, find k-th largest element with using extra space.
6993. Given a BST, find k-th largest element without using extra space.
7004. Maximum Sum path
701
702 Graph
703
7041. Do the bfs of a graph
7052. Given a graph, find out if it can be colored using 2 colors.
706Different colors for alternate nodes (3 hours) people who passed
707all 10 test cases were shortlisted. (BFS)
708
709
710C++
711
7121. What is the difference between class and object? Does class or object
713 create memory?
7142. Virtual destructor
7153. Virtual inheritance
7164. Pure virtual classes
7175. Pure virtual function
7186. Abstract class
7197. Implement typedef operator (function template can be used to write a
720 generic function.
7218. what is the difference between structures and classes in cpp In cpp \
722 class default access specifier is private, in structure it is public
723
7249. Describe Inheritance
725
726
727C
728
7291. my_sizeof implementation
730-> 1. #define my_sizeof(type) (char*)(&type+1)-(char *)(&type)
731 2. size_t size = (size_t)(1 + ((X*)0));
732
7332. Storage classes in C
734-> auto
735 register
736 static
737 extern
738 typedef (sometimes consider as storage class becuase of syntax used)
739
7403. What does appending 'static' to a global variable/function do?
741-> Limits the scope of that variable/function to that source file only.
742 If in the project we have multiple source files,then you can have same
743 name variable/function in other source file provided the earlier
744 declared one is static.
745
7464. Swap the values of two pointers without a temp variable
747-> *a = *a ^ *b;
748 *b = *a ^ *b;
749 *a = *a ^ *b;
750
7515. Difference between malloc and calloc
752->
753
7546. const pointers and pointers to const*
755->
756
7577. What is static keyword and its different use cases?
758-> 1. static variable inside a function retains it value.
759 2.
760
7618. What is volatile keyword
762->
763
76410. What are dangling pointers?
765-> If a pointer refers to the original memory after it has been freed,
766 it is called a dangling pointer.
767
768 ex.
769 int *ptr = (int *)malloc(SIZE);
770 free(ptr);
771
772 ptr is dangling pointer as it is pointing to same old memory which
773 is already free/Not valid
774
775 ptr = NULL; // Good practice
776
77711. What are Wild Pointers?
778-> Uninitialized pointers are known as wild pointers because they point
779 to some arbitrary memory location and may cause a program to crash.
780
78112. What is the difference between structures and unions?
782 When to use what? Sizes?
783->
784
785
78613. What is free()? how does free know how much memory to de-allocate?
787-> When you call malloc()/calloc(), you specify the amount of memory to
788 allocate.
789 The amount of memory actually used is slightly more than this, and
790 includes extra information that records (at least) how big the block
791 is. You can't (reliably) access that other information and nor should
792 you.When you call free(), it simply looks at the extra information to
793 find out how big the block is.
794
795
796
797Data structure and Algorithm
798
7991. Dijkstra’s Algorithm, pseudo code why Dijkstra’s algo fails when
800 -ve weights are there in the graph.
8012. Find the loop in the graph if it exist and print the
802 nodes of the loop in sorted order.
8033.
8044. Min heap
8055. Binary search
8066. Print sum of all prime numbers within a given range.
8077. Find the degrees between the minute hand and hour hand when a
808 clock is at 3:15
8099. Write code in C that would hash a string and deal with collision
810 resolution by implementing a linked list. Would this code be thread safe?
811
81216.One was to output the decimal number after inverting the binary
813 representation of input number.
814
815
816
817std::map
818
819
820key - value(mapped value) relation
821
822In 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.
823
824Types of key and mapped value may differ
825
826map 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.
827
828Maps are typically implemented as binary search trees
829
830
831
832std::unordered_map
833
834
835key - value(mapped value) relation
836
837Types of key and mapped value may differ
838
839the elements in the unordered_map are not sorted in any particular order with respect to either their key or mapped values,
840
841organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values
842
843
844
845Operating system + RTOS + Computer Architecture
846
847
8481. What is Virtual Memory
8492. Caches
8503. What is Priority inversion (RTOS)
851-> If the High priority task is blocked till the resource got free.
852 which is acquired by low priority task and if any middle priority
853 task becomes ready then it will preempt the low priority task.
854 So middle priority got chance to run evenif high priority ready task
855 is pending.This situation is called priority inversion.
856
857 Solution is to use Priority inheritance.
858 Task acuiring blocking the resource(who got the lock), gets the priority level
859 of highest priority task pending for that resource.
860
8614. What is Reentrancy
8625. Semaphore vs Mutex vs Spinlocks
863
8645. What is spinlock ? why it is a bad idea to use spinlock on uniprocessor
865 system?
866-> On a uniprocessor, it will either immediately acquire the lock or it
867 will spin forever - if the lock is contended, then there will never be
868 an opportunity for the process which currently holds the resource to
869 give it up. Spinlocks are only useful when another process can execute
870 while one is spinning on the lock - which means multiprocessor systems.
871
8726. What is Concurrency and Multi threading?
8737. Watchdog Timer
8748. How post increment works.
8759. Assembly implementation of spinlock?
87610. How does a debugger work?
87711. How do breakpoints in a C program works?
878
87912. How are interrupts handled in RTOS?
880--> Application code execution is interrupted (delayed) during the execution
881 of an ISR, most applications minimize the amount of code in the ISR and
882 rely instead on non ISR code (a “Task†is signaled using semaphore) to
883 complete the processing. This allows the highest priority application
884 code to be executed as quickly as possible, and delayed as little as
885 possible, even in situations with intense interrupt activity.
886
88713. What is atomic programming/non-locking operation?
888
88914. What is trashing? what happens during trashing? what is excessive
890 paging?
89115. big endian vs little endian, how to find
892->
893 #include <stdio.h>
894 int main()
895 {
896 unsigned int i = 1;
897 char *c = (char*)&i;
898 if (*c)
899 printf("Little endian");
900 else
901 printf("Big endian");
902 getchar();
903 return 0;
904 }
905
90616. What is dynamic loading? what is static loading? when to use dynamic
907 loading? What are the advantages? give an example when to use dynamic
908 loading?
90917. What are interrupts and if you have less external interrupt pins on a
910 processor, how to interface multiple interrupts?
91118. Difference between & and &&
91219. Process address space,Memory regions like stack, heap, text, data
913 segments.
914
915
916Design questions
917
918
9191. Design an elevator system
9202. Desing an LRU(Least recently use) system
9213. Are there any problems (from a embedded system point of view) you
922 should prevent and how will you prevent it in your design
9234. Write a program to create circular queue
9245. Design a Stack class (pop,push,top,size,getMin)
9256. Implement strcpy function, what if the 2 buffers passed to the strcpy
926 function overlaps ?
9277. Implement aligned malloc
9288. Implement memcpy function with two void pointers and size
9299. Implement a queue/fifo with push/pop functionality using linked lists
930
931 Brain teasers
932
9331. About seating in an airplane. Probability that last person gets a
934 correct seat.
935--> 1/2
936
937
938public boolean lock()
939{
940 if(!locked) {
941 locked = true;
942 return true;
943 }
944 return false;
945 }
946
947Compiler
948
949
950Assembly Language- Memory Write and Read implementation using Assembly.
951How multiply is implemented?
952
953
9541. How mutex and condition variable works?
955
956A thread obtains a mutex (condition variables always have an associated
957mutex) and tests the condition under the mutex’s protection. No other
958thread should alter any aspect of the condition without holding the mutex.
959If the condition is true, your thread completes its task, releasing the
960mutex when appropriate. If the condition isn’t true, the mutex is released
961for you, and your thread goes to sleep on the condition variable.
962When some other thread changes some aspect of the condition, it calls
963pthread_cond_signal(), waking up one sleeping thread.
964Your thread then reacquires the mutex, reevaluates the condition, and either
965succeeds or goes back to sleep, depending upon the outcome.
966You must reevaluate the condition!
967First,the other thread may not have tested the complete condition before sending
968the wakeup.
969Second, even if the condition was true when the signal was sent, it could
970have changed before your thread got to run.
971Third, condition variables allow for spurious wakeups.
972They are allowed to wakeup for no discernible reason whatsoever!
973
974
975Not all pages are candidates for swapping. Consider kernel code that responds to
976interrupts or code that manages the page tables and swap logic. These are obvious
977pages that should never be swapped out and are therefore pinned, or permanently
978resident in memory.
979Although kernel pages are not candidates for swapping, user space pages are,
980but they can be pinned through the mlock (or mlockall) function to lock the page down.
981This is the purpose behind the user space memory access functions.
982
983
9841. Why we need copy_from_user(as kernel already has access to user space
985 memory)
986-->If the kernel assumed that an address that a user passed was valid and
987 accessible, a kernel panic would eventually occur (for example, because
988 the user page was swapped out, resulting in a page fault in the kernel).
989This application programming interface (API) ensures that those corner
990
991
992cases are handled properly.
993
994
995
996
997
998
9991. Timer callback
1000
1001
1002
1003
1004
1005
1006
1007
1008CISC
1009
1010RISC
1011
1012Emphasis on hardware
1013
1014Emphasis on software
1015
1016Includes multi-clock
1017
1018
1019complex instructions
1020
1021
1022Single-clock,
1023
1024
1025reduced instruction only
1026
1027
1028Memory-to-memory:
1029
1030
1031"LOAD" and "STORE"
1032
1033
1034incorporated in instructions
1035
1036
1037Register to register:
1038
1039
1040"LOAD" and "STORE"
1041
1042
1043are independent instructions
1044
1045
1046Small code sizes,
1047
1048
1049high cycles per second
1050
1051
1052Low cycles per second,
1053
1054
1055large code sizes
1056
1057
1058Transistors used for storing
1059
1060
1061complex instructions
1062
1063
1064Spends more transistors
1065
1066
1067on memory registers
1068
1069
1070
1071Harvard architecture has separate data and instruction busses, allowing transfers to be performed simultaneously on both busses.
1072
1073
1074Von 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.
1075
1076
1077
1078
1079
1080What is ACPI and what does ACPI mean?
1081
1082ACPI 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.
1083
1084ACPI power states
1085ACPI specifies various modes, referred to as states, that control the power to the components of a PC.
1086
1087The 4 Global states:
1088Working (G0)
1089Sleeping (G1)
1090Soft Off (G2)
1091Mechanical Off (G3).
1092Within these Global states are various different Sleep states: S0, S1, S2, S3, S4 and S5.
1093
1094For 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.
1095
1096Another example is when your computer is put into hybernate mode, this is actually Global state G1 with Sleep state S4.
1097
1098The 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.
1099
1100The 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.
1101
1102
1103
1104Writing a kernel in CUDA
1105
1106
1107
1108
1109As 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.
1110
1111
1112
1113
1114
1115
1116
1117CUDA
1118
1119The CUDA programming model is a heterogeneous model in which both the
1120CPU and GPU are used.
1121
1122In CUDA,
1123 host refers to the CPU and its memory
1124 device refers to the GPU and its memory
1125
1126Code run on the host can manage memory on both the host and device, and also launches kernels which are functions executed on the device.
1127
1128These kernels are executed by many GPU threads in parallel.
1129
1130
1131Given the heterogeneous nature of the CUDA programming model, a typical sequence of operations for a CUDA C program is:
1132
1133Declare and allocate host and device memory.
1134Initialize host data.
1135Transfer data from the host to the device.
1136Execute one or more kernels.
1137Transfer results from the device to the host.
1138
1139How to process an image in CUDA? How to map to threads? Is it memory-bound or compute-bound?
1140Describe how to implement the interface to ensure a certain
1141 block of code in a simple compiler is executed every so often(time dependent)
1142Write a version of the C function tail
11431. Explain the stack and heap areas in the process address space.
11442. Implement strncmp library function, bug free.
11453. How does the linux file system implement the access control.
11464. Webserver, incoming request. compare the following three approaches, pros and cons
1147 1) one request, fork one process to response 2) process pool 3) producer and consumer.