Multi-Threading

• refer to this pthread program to print even and odd numbers in different threads.

http://dhinu-programs.blogspot.in/2016/05/pthread.html

•  Good article about user space threads and kerneal space threads

http://www.evanjones.ca/software/threading.html

• Difference between mutex and semaphore
• http://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex
• Posix Semaphores
• http://www.csc.villanova.edu/~mdamian/threads/posixsem.html
• System V semaphores between different process.
• https://www.classes.cs.uchicago.edu/archive/2010/fall/51081-1/LabFAQ/lab7/Semaphores.html
• Classical synchronization problems
• http://nob.cs.ucdavis.edu/classes/ecs150-2008-02/handouts/sync/sync-problems.html
• producer consumer problem example
• http://www.dailyfreecode.com/code/solve-producer-consumer-problem-thread-2114.aspx
• Readers Writers problem example
• https://en.wikipedia.org/wiki/Readers%E2%80%93writers_problem
• Mutexes between multiple process
• https://linux.die.net/man/3/pthread_mutexattr_setpshared
• Joinable and detached threads - The thread attributes that the system should store for a joinable thread.
• http://www.domaigne.com/blog/computing/joinable-and-detached-threads/

GPS related

• Assistace data
• reference time
• ref position
• ionospheric model
• UTC model
• acquisition assistance

Client-server

• Designing servers

  There are a number of different ways to design servers. These models are discussed in detail in a book by Douglas E. Comer and David L. Stevens entiteld Internetworking with TCP/IP Volume III:Client Server Programming and Applications published by Prentice Hall in 1996. These are summarized here.
  Concurrent, connection oriented servers
  
  The typical server in the Internet domain creates a stream socket and forks off a process to handle each new connection that it receives. This model is appropriate for services which will do a good deal of reading and writing over an extended period of time, such as a telnet server or an ftp server. This model has relatively high overhead, because forking off a new process is a time consuming operation, and because a stream socket which uses the TCP protocol has high kernel overhead, not only in establishing the connection but also in transmitting information. However, once the connection has been established, data transmission is reliable in both directions.
  Iterative, connectionless servers
  
  Servers which provide only a single message to the client often do not involve forking, and often use a datagram socket rather than a stream socket. Examples include a finger daemon or a timeofday server or an echo server (a server which merely echoes a message sent by the client). These servers handle each message as it receives them in the same process. There is much less overhead with this type of server, but the communication is unreliable. A request or a reply may get lost in the Internet, and there is no built-in mechanism to detect and handle this.
  Single Process concurrent servers
  
  A server which needs the capability of handling several clients simultaneous, but where each connection is I/O dominated (i.e. the server spends most of its time blocked waiting for a message from the client) is a candidate for a single process, concurrent server. In this model, one process maintains a number of open connections, and listens at each for a message. Whenever it gets a message from a client, it replies quickly and then listens for the next one. This type of service can be done
  
  with the select system call.
• http://www.linuxhowtos.org/C_C++/socket.htm
• reference link 
• www.ibm.com/developerworks/linux/tutorials/l-sock/
• Program
• http://dhinu-programs.blogspot.in/2016/05/socket-server.html
• http://dhinu-programs.blogspot.in/2016/05/socket-client.html

C++

• Default arguments in virtual functions - Always the default argument mentioned in the base class function declaration is used. The default arguments are not part of class signature. Default arguments is added to the function call at compile time. But the function call resolution is made at run time.
• Why virtual destructor is used.
• Difference between static and dynamic casting. Dynamic cast will give a compile error if the class is not polymorphic.
• https://www.learncpp.com/cpp-tutorial/12-9-dynamic-casting/
• Keyword 'auto' - This is good while creating iterators to avoid the long initializations
• https://www.geeksforgeeks.org/type-inference-in-c-auto-and-decltype/
• Good link for c++ reference
• http://www.geeksforgeeks.org/c-plus-plus/#CvsC++
• Name Mangling and extern “C” in C++
• http://www.geeksforgeeks.org/extern-c-in-c/
• const functions in c++
• http://geeksquiz.com/const-member-functions-c/
• static const in c++
• abstract data types?
• Operator overloading
• we can restrict dynamic allocation of objects of a class by declaring a private new and new[] operators.
• Operators which cannot be overloaded
• . operator, -> operator, ?: operator, :: operator
• Conversion operators
• http://quiz.geeksforgeeks.org/c-plus-plus/operator-overloading/
• const functions in c++
• http://quiz.geeksforgeeks.org/const-member-functions-c/
• Smart pointer in c++
• http://dhinu-programs.blogspot.in/2016/12/smart-pointer-c.html
• Virtual functions
• http://blog.httrack.com/blog/2014/05/09/a-basic-glance-at-the-virtual-table/
• http://www.studytonight.com/cpp/virtual-functions.php
• Virtual Classes
• http://www.geeksforgeeks.org/multiple-inheritance-in-c/#disqus_thread
• Constructors
• Constructors and array of objects with new
• If One class
• http://stackoverflow.com/questions/8312054/constructors-and-array-of-object-in-c
• int *n = new int[3]{1,2,3};
• A *a = new A[3]{{1,2},{3,4},{5,6} // This invokes constructor with 2 arguments for 3 objects.
• Copy constructor argument should be constant
• http://quiz.geeksforgeeks.org/c-constructors-question-17/
• Conversion constructor
• http://quiz.geeksforgeeks.org/c-constructors-question-16/
•  The 'explicit' keyword
• http://en.cppreference.com/w/cpp/language/explicit
• http://www.geeksforgeeks.org/g-fact-93/
• Constructors cannot be virtual and can be private
• http://quiz.geeksforgeeks.org/c-constructors-question-14/
• Templates
• Template specialization
• Passing non type arguments to templates
• The string class dynamically increases or decreases the memory for characters.
• http://www.cplusplus.com/reference/string/string/capacity/ 
• Conversion operators
• http://www.geeksforgeeks.org/advanced-c-conversion-operators/
• Anatomy of assignment operator - good
• http://www.icu-project.org/docs/papers/cpp_report/the_anatomy_of_the_assignment_operator.html
• 
  

program, assembly, simple1.c

simple1.c

int add(int i, int j);

int main()
{
    int i, j;
    i++;
    j = 10;
    j = i;
    j = add(i,j);
    return 0;
}

int add(int i, int j)
{
    int result;
    result = i+j;
    return result;
}

simple1.s

    .file    "simple1.c"
    .text
    .globl    main
    .type    main, @function
main:
.LFB0:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    subq    $16, %rsp
    addl    $1, -8(%rbp)
    movl    $10, -4(%rbp)
    movl    -8(%rbp), %eax
    movl    %eax, -4(%rbp)
    movl    -4(%rbp), %edx
    movl    -8(%rbp), %eax
    movl    %edx, %esi
    movl    %eax, %edi
    call    add
    movl    %eax, -4(%rbp)
    movl    $0, %eax
    leave
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size    main, .-main
    .globl    add
    .type    add, @function
add:
.LFB1:
    .cfi_startproc
    pushq    %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    movl    %edi, -20(%rbp)
    movl    %esi, -24(%rbp)
    movl    -24(%rbp), %eax
    movl    -20(%rbp), %edx
    addl    %edx, %eax
    movl    %eax, -4(%rbp)
    movl    -4(%rbp), %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE1:
    .size    add, .-add
    .ident    "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

nm simple1.o

0000000000000032 T add
0000000000000000 T main

proram, assembly, simple.c

Simple.c

int main()
{
    int i, j;
    i++;
    j = 10;
    j = i;

    return 0;
}

Simple.s

   .file   "simple.c"
    .text
    .globl  main
    .type   main, @function
main:
.LFB0:
    .cfi_startproc
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
    movq    %rsp, %rbp
    .cfi_def_cfa_register 6
    addl    $1, -8(%rbp)
    movl    $10, -4(%rbp)
    movl    -8(%rbp), %eax
    movl    %eax, -4(%rbp)
    movl    $0, %eax
    popq    %rbp
    .cfi_def_cfa 7, 8
    ret
    .cfi_endproc
.LFE0:
    .size   main, .-main
    .ident  "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4"
    .section    .note.GNU-stack,"",@progbits

nm simple.o

0000000000000000 T main

Kernel Synchronization

• critical regions: Code paths that access and manipulate shared data are called critical regions
• atomic operation: operations complete without interruption as if the entire critical region were one indivisible instruction
• Race condition: it is the condition when two threads of execution to be simultaneously executing within the same critical region.
• If the critical region is a very minimal instruction, making the execution as atomic operation will avoid the race condition. For eg, i++ will be performed by 3 or 4 instructions in assembly language. This can be made as an atomic operation for synchronization.
• The kernel provides two sets of interfaces for atomic operations—one that operates on integers and another that operates on individual bits.These interfaces are implemented on every architecture that Linux supports. Most architectures contain instructions that provide atomic versions of simple arithmetic operations. Other architectures, lacking direct atomic operations, provide an operation to lock the memory bus for a single operation, thus guaranteeing that another memory-affecting operation cannot occur simultaneously.
• Generally, a few instructions can be made atomic by the processor. When a huge instructions are to be synchronized, a locking mechanism is required. In this case only the locking operation will be atomic.
• Locking mechanisms can be different that when a thread finds that a critical region is locked, it can busy wait(eg, spin lock) or sleep.
• On the popular x86 architecture, locks are implemented using such an instruction called compare and exchange.
• Causes of concurrency in user space programs.
• true concurrency occurs because of multi processors.
• pseudo-concurrency occurs because of preemption(or yielding) or receiving of signals in a user space program.
• Causes of concurrency in kernel space programs.
• Interrupts— An interrupt can occur asynchronously at almost any time, interrupting the currently executing code.
• Softirqs and tasklets— The kernel can raise or schedule a softirq or tasklet at almost any time, interrupting the currently executing code.
• Kernel preemption— Because the kernel is preemptive, one task in the kernel can preempt another.
• Sleeping and synchronization with user-space— A task in the kernel can sleep and thus invoke the scheduler, resulting in the running of a new process.
• Symmetrical multiprocessing— Two or more processors can execute kernel code at exactly the same time.
• The term lock contention, or simply contention, describes a lock currently in use but that another thread is trying to acquire.
• spin lock:
• A spin lock is a lock that can be held by at most one thread of execution.
• If a thread of execution attempts to acquire a spin lock while it is already held, which is called contended, the thread busy loops—spins—waiting for the lock to become available.
• It is not wise to hold a spin lock for a long time.This is the nature of the spin lock: a lightweight single-holder lock that should be held for short durations.
• Making the process to sleep if the lock is already contended incurs a bit of overhead—most notably the two context switches required to switch out of and back into the blocking thread, which is certainly a lot more code than the handful of lines used to implement a spin lock.Therefore, it is wise to hold spin locks for less than the duration of two context switches.
• On uniprocessor machines, the locks compile away and do not exist; they simply act as markers to disable and enable kernel preemption. If kernel preempt is turned off, the locks compile away entirely.
• Spin locks can be used in interrupt handlers, whereas semaphores cannot be used because they sleep.
• If a lock is used in an interrupt handler, you must also disable local interrupts (interrupt requests on the current processor) before obtaining the lock. Otherwise, it is possible for an interrupt handler to interrupt kernel code while the lock is held and attempt to reacquire the lock.The interrupt handler spins, waiting for the lock to become
  available.The lock holder, however, does not run until the interrupt handler completes. This is an example of the double-acquire deadlock. Note that you need to disable interrupts only on the current processor. If an interrupt occurs on a different processor, and it spins on the same lock, it does not prevent the lock holder (which is on a different processor) from eventually releasing the lock.
• Because a bottom half might preempt process context code, if data is shared between a bottom-half process context, you must protect the data in process context with both a lock and the disabling of bottom halves. Likewise, because an interrupt handler might preempt a bottom half, if data is shared between an interrupt handler and a bottom half, you must both obtain the appropriate lock and disable interrupts
• reader-writer spin lock
•  

Kernel Stack

• https://www.kernel.org/doc/Documentation/x86/kernel-stacks

• Like all other architectures, x86_64 has a kernel stack for every
  active thread.  These thread stacks are THREAD_SIZE (2*PAGE_SIZE) big.
  These stacks contain useful data as long as a thread is alive or a
  zombie.

• While the thread is in user space the kernel stack is empty
  except for the thread_info structure at the bottom.
  

• 
  

General Scraps

• Processor priority in Linux
• The first is the nice value, a number from -20 to +19 with a default of 0. Larger nice values correspond to a lower priorityyou are being nice to the other processes on the system. Processes with a lower nice value (higher priority) run before processes with a higher nice value (lower priority). The nice value also helps determine how long a timeslice the process receives. A process with a nice value of -20 receives the maximum possible timeslice, whereas a process with a nice value of 19 receives the minimum possible timeslice. Nice values are the standard priority range used in all Unix systems.
• The second range is the real-time priority. The values are configurable, but by default range from 0 to 99. All real-time processes are at a higher priority than normal processes.
• Real Time values + nice value together.
• Real Time process command
• http://linux.die.net/man/1/chrt
• http://unix.stackexchange.com/questions/154867/real-time-processes-scheduling-in-linux
• The chrt command
• To set scheduling policy to SCHED_FIFO, enter:

  chrt -f -p [1..99] {pid}
  

  To set scheduling policy to SCHED_RR, enter:

  chrt -r -p [1..99] {pid}

• asmlinkage keyworkd in system call

• system call is reentrant

• Seeing assembly and register values in GDB and description about assembly code

                  https://www.recurse.com/blog/7-understanding-c-by-learning-assembly

• re-entrant and thread safe functions.
• https://www.ibm.com/support/knowledgecenter/ssw_aix_61/com.ibm.aix.genprogc/writing_reentrant_thread_safe_code.htm
• Variadic functions and variadic macro funtions
• Volatile type specifier - http://www.geeksforgeeks.org/understanding-volatile-qualifier-in-c/

Process Scheduling

• Multitasking operating systems come in two flavors: cooperative multitasking and preemptive multitasking
• preemptive multitasking
• The act of involuntarily suspending a running process is called preemption.
• Linux, like all Unix variants and most modern operating systems, provides preemptive multitasking.
• The time a process runs before it is preempted is predetermined, and it is called the timeslice of the process.

• cooperative multitasking
• The process does not stop running until it voluntary decides to do so.
• The act of a process voluntarily suspending itself is called yielding.

• I/O-Bound Versus Processor-Bound Processes
• runqueues
• 
  

Process Management

Process:

• Process states are

1. TASK_RUNNING 
2. TASK_INTERRUPTIBLE
3. TASK_UNINTERRUPTIBLE 
4. TASK_ZOMBIE
5. TASK_STOPPED

http://www.makelinux.net/books/lkd2/?u=ch09lev1sec1

• Normal program execution occurs in user-space. When a program executes a system call (see Chapter 5, "System Calls") or triggers an exception, it enters kernel-space. At this point, the kernel is said to be "executing on behalf of the process" and is in process context.

• The system call for fork() is clone().
• The kernel stores the list of processes in a circular doubly linked list called the task list.
• The process descriptor contains the data that describes the executing program—open files, the process’s address space, pending signals, the process’s state, and much more
• In linux, a thread is merely a process that shares certain resources with other processes.

Kernel Threads:

• The significant difference between kernel threads and normal processes is that kernel threads do not have an address space.
• They operate only in kernel-space and do not context switch into user-space.
• Kernel threads, however, are schedulable and preemptable, the same as normal processes.
• You can see the kernel threads on your Linux system by running the command ps -ef

Process family tree:

• All processes are descendents of the init process, whose PID is one. The kernel starts init in the last step of the boot process. The init process, in turn, reads the system initscripts and executes more programs, eventually completing the boot process.
• Every process on the system has exactly one parent. Likewise, every process has zero or more children. Processes that are all direct children of the same parent are called siblings. The relationship between processes is stored in the process descriptor. Each task_struct has a pointer to the parent's task_struct, named parent, and a list of children, named children.
• The init task's process descriptor is statically allocated as init_task. 

Process creation:

• The first, fork(), creates a child process that is a copy of the current task. It differs from the parent only in its PID (which is unique), its PPID (parent’s PID, which is set to the original process), and certain resources and statistics, such as pending signals, which are not inherited.

• copy-on-write
• The page tables of the process address space is not copied until a write operation.
• This is because in most of the cases, the fork() is followed by an exec() which will create a new address space after fork().
• By copy-on -write technique, the only thing which happens during fork() is to create a new process descriptor for the child process.

• fork - steps in forking
1. creates a new kernel stack, thread_info structure, and task_struct for the new process. The new values are identical to those of the current task. At this point, the child and parent process descriptors are identical.
2. It then checks that the new child will not exceed the resource limits on the number of processes for the current user.
3. Now the child needs to differentiate itself from its parent. Various members of the process descriptor are cleared or set to initial values
4. Next, the child's state is set to TASK_UNINTERRUPTIBLE, to ensure that it does not yet run.
5. Next, it calls get_pid() to assign an available PID to the new task.
6. Next, open files, filesystem information, signal handlers, process address space, and namespace are either shared or duplicated.
7. Next, the remaining timeslice between the parent and its child is split between the two.
8. Finally, the PID of the new child is returned to the caller.

Process Termination:

• Generally it occurs when the process calls the exit() system call, either explicitly when it is ready to terminate or implicitly on return from the main subroutine of any program. (That is, the C compiler places a call to exit() after main() returns.)
• A process can also terminate involuntarily.This occurs when the process receives a signal or exception it cannot handle or ignore.
• If the parent process exits before child, reparent a task's children on exit to either another process in the current thread group or, if that fails, the init process.

Data Structures

Time and Space complexities

http://stackoverflow.com/questions/18686121/differences-between-time-complexity-and-space-complexity

Sorting Methods

http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html

https://www.hackerearth.com/notes/sorting-code-monk/

http://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

1. Bubble sort
2. Modified Bubble sort
3. Selection sort
4. Insertion sort
5. Heap sort
6. Merge sort - Program
7. Quick sort

Linked Lists

http://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

Stack

http://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

Graph

http://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

Tree

http://www.tutorialspoint.com/data_structures_algorithms/quick_sort_algorithm.htm

AVL Tree

http://www.geeksforgeeks.org/avl-tree-set-1-insertion/

Important linux commands

1. ulimit command is used to set and view the system resource(eg: stack size) for any process.
2. You can examine binary images using the nm and objdump commands to display symbols, their addresses, segments, and so on.
3. To check the info about the ports that are being used in a system, use netstat command

• http://www.cyberciti.biz/faq/what-process-has-open-linux-port/

Process Address Space

1. Process Address Space and how each section of address space is growing: http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
2. In Linux, if you request a large block of memory via malloc(), the C library will create an anonymous mapping instead of using heap memory. ‘Large’ means larger than MMAP_THRESHOLD bytes, 128 kB by default and adjustable via mallopt().
3. ulimit command is used to set and view the system resource(eg: stack size) for any process.
4. You can examine binary images using the nm and objdump commands to display symbols, their addresses, segments, and so on.

Things TODO for learning

1. Check how to compile with shared lib and basics of Makefile writing
2. How mmap works and why it is needed?
3. Learn where graphs are used
4. compiler optimization
5. why memory mapping
6. what is namespce
7. what is spinlocks.
8. How to create a deamon. Difference b/w a process and a deamon.
9. Mutex
10. Process stack and thread stack - what is shared and what is not
11. Where is ISR - on kernel stack?
12. How scheduler is running? is it a kernel process
13. C++
14. socket program, client -server
15. where is shared memory residing
16. compiler design
17. x86 addressing modes and basic operations. For example, how a value is assigned to a memory location.
18. User space mechanisms corresponding to the kernel space.
19. x86 resisters
20. check the register variable use
21. how to access the processor register in c program.
22. How to do timer, counters and handle signals.
23. basics of shell scripting.
24. Check supl, control plane specs
25. why volatile keyword
26. EXTERN C
27. where pointer type info is stored 
28.  Check assembly for function, static variable, register variable and all
29. Check the c++ symbols
30. x86 addressing mode
31. How an array is passed to a function
32. Serial communication
33. Inline functions
34.  Macro function
35. Order of precedence in C
36. Order of precedence in C++
37. Advantage of oops over structured programming.
38. How message queues will be notified when something is available in the queue.
39. signal, gdb, gdbserver, coredump, gdb with coredump, macro functions, return value of arithmetic operations involving two different datatypes.