OS_concepts_FAQs

HOW DETERMINISM ACHIEVED IN RTOS...??

RTOS is designed for determinism(how quickly it can respond to events) vs GPOS for High performance( how much amount of work done/time)
minimum Interrupt Latency
minimum thread switching Latency


pre-emptible kernel vs non-pre emptible kernel:
in non-preemtive kernel - a high-priority user thread can never preempt a kernel call, but must instead wait for the entire call to
complete – even if the call was invoked by the lowest-priority process
==> unpredictable delays and prevents critical activities from completing on time.

In an RTOS, on the other hand, kernel operations are preemptible. There are stil windows of time in which preemption may
not occur, but in a well-designed RTOS,those intervals are extremely brief. 
Moreover RTOS will impose an upper bound on how long preemption is held off and interrupts disabled; this
allows developers to ascertain worst-case latencies.

Only services with a short execution path should be included in the kernel itself. Any operations that require significant work
(for instance, process loading) must be assigned to external processes or threads. 

In an RTOS the kernel is kept very simple and only very important service requests are kept within the kernel call.
All other service requests are treated as external.All service requests from kernel are associated with a bounded latency
in an RTOS. This ensures highly predictable and quick response from an RTOS.

unbounded dispach latencies...more number of threads to schedule, latencies will get added up!
An RTOS has no such issues because all the process and threads in it has got bounded latencies.


RTOS is mostly a "time triggerred". where as GPOS "event triggerred"
scheduling policy : priority based(to achieve determinism) vs round-robin( to achieve high performance)
Ability to scale up / scale down as per application requirement    
Less memory Management- a simple list based allocator
(no memory fragmentation solutions and virtual memomry ... like slab, slub allocator)
Generally RTOSes are meant for Low-end-Hardware configurations vs GPOS-Highend HW configurations
=======================================================================================================================

MUTEX vs SPINLOCK:

Mutex
 thread tries to lock a mutex and it does not succeed, because the mutex is already locked, it will go to sleep.
 immediately allowing another thread to run. 
 It will continue to sleep until being woken up, which will be the case once the mutex is being unlocked
 by whatever thread was holding the lock before.
 
Disadvantage: 
putting threads to sleep and waking them up again are both rather expensive operations.
they’ll need quite a lot of CPU instructions and thus also take some time.
If now the mutex was only locked for a very short amount of time, the time spent in putting a thread to sleep 
and waking it up again might exceed the time the thread has actually slept by far and it might even exceed 
the time the thread would have wasted by constantly polling on a spinlock

when to use Mutex??
when Lock is held for long time.

Spinlock: 
When a thread tries to lock a spinlock and it does not succeed, it will continuously re-try locking it,
until it finally succeeds; thus it will not allow another thread to take its place.
(however,once the CPU runtime quantum of the current thread has been exceeded, OS will forcefully switch to another thread,).

disadvantages:
polling on a spinlock will constantly waste CPU time.
if the lock is held for a longer amount of time, this will waste a lot more CPU time and it would have been much better 
if the thread was sleeping instead.

when to use spinlocaks??
Using spinlocks on a single-core/single-CPU system makes usually no sense, since as long as the spinlock polling is blocking
the only available CPU core, no other thread can run and since no other thread can run, the lock won’t be unlocked in the
quantum of time allocated for thread spinning...this merely wastes quantum of thread trying for spinlock.

On a multi-core/multi-CPU systems, with plenty of locks that are held for a very short amount of time only, 
the time wasted for constantly putting threads to sleep and waking them up again might decrease runtime performance noticeably. 
When using spinlocks instead, threads get the chance to take advantage of their full runtime quantum 
(always only blocking for a very short time period, but then immediately continue their work), leading to much higher processing throughput.

The Practice
Since very often programmers cannot know in advance if mutexes or spinlocks will be better 
(e.g. because the number of CPU cores of the target architecture is unknown), nor can operating systems know 
if a certain piece of code has been optimized for single-core or multi-core environments,
most systems don’t strictly distinguish between mutexes and spinlocks.
In fact, most modern operating systems have hybrid mutexes and hybrid spinlocks.

hybrid mutexes: 
behaves like a spinlock at first on a multi-core system.
Only if the lock has still not been obtained after a certain amount of time (or retries or any other measuring factor), 
the thread is really put to sleep.

===============================================================================================================================
Q : Difference Binary-semaphore and Mutex ??
A:

Binary semaphores and mutexes are very similar
subtle difference: 
                      Binary semaphores                                    mutexes

                    No priority inheritance mechanism                        Mutexes are binary semaphores that include
                                                                              a priority inheritance mechanism
                                                                              
                                                                              
                    Binary semaphore a better choice                          better choice for implementing
                    for implementing synchronisation                          simple mutual exclusion
                    (between tasks or between tasks and an interrupt) 
                    
                    semaphore can be released by any process                 only process acquired can relaese mutex
                       
Q: what is Mutex purpose??                       
Q:what is priority inheritance ? what is it's role in Mutex objective ?
  
   mutex : like a token to guard a resource.
   When a task wishes to access the resource it must first obtain the token.
   When it has finished with the resource it must 'give' the token back-allowing other tasks to access resource.
   
  scenario: Low-pri-taskA obtains mutex, high-pri-taskC which also require same mutex, got sceduled very next moment. 
  Result :  high-prio-taskC gets blocked for mutex and now chance that a medium-pri-taskB gets oppurtunity to run and finish.
            After taskB ,Low-pri-taskA gets chance to execute and release the mutex. high-pri-taskA gets chance to execute only
            after { Medium-pri-taskB Execution time + time taken by Low-pri-taskA to relese mutex} = Unbounded amount of time,untill
            Medium-pri-taskB finishes.
  
  Affect : Priority Inversion occured b/w Medim-pri-taskB and High-pri-taskC
  can we mitigate the Affect?? : priority inheritance: can't avoid priority inversion but can minimise the affect
  
  Role of priority Inheritance of Mutex - In minimising the Priority Inversion 
        if a high-pri-taskC blocks while attempting to obtain a mutex that is currently held by a 
        low-pri-taskA,then the priority of the taskA holding the mutex is temporarily raised to that of the blocking taskC
        ==> this doesn't allow Medim-pri-taskB to run.
        Now High-pri-taskC will run as soon as Low-pri-taskB releases the Lock( still priority Inversion , but minimised effect)
        
 Q: can we use Mutex in INTR-Handler ??
 A: Interrupt handler should not block waiting for some task to release mutex(if that task obtined mutex), 
    so we cant use mutex in INTR-Handler
    
    
 
Q: Re-entrant code ?? 

need :  single threaded process : -> single flow of control => code need not be re-entrant.
        Multi threaded process : ->  same Functions and resources accessed by several threads concurrently.
                                     re-entrant Fn : protects the resource integrity.
  
  
            
  Kernel-Memory Allocation:
  32bit ===> 2^32 = 4GB virtual Memory space.
  kernel is limited to 1GB-Virtual and Physical Memory
  The kernel's memory is not pageable. 
  The kernel usually wants physically contiguous memory
  Often, the kernel must allocate the memory without sleeping
  
  
  void * kmalloc(size_t size, int flags); ==>  allocates contiguous memory in physical memory as well as virtual memory
  flag :
  GFP_KERNEL => kmalloc can put current process in sleep state if memory is low.
                used in process context code when it is safe to sleep.
  GFP_ATOMIC:- ensures that current process is not put to sleep if memory is low.
               This is the flag to use in interrupt handlers, bottom halves and other situations where you cannot sleep.
  GFP_USER:-	This is a normal allocation and might block. This flag is used to allocate memory for user-space processes.


  kmalloc return the virtual address of first page allocated. On error it returns NULL.  
  
  when to use kmalloc:
  many hardware devices cannot address virtual memory. Therefore, in order for them to be able to access a block of memory,
  the block must exist as a physically contiguous chunk of memory
  Another benifit: a physically contiguous block of memory can use a single large page mapping.
                  This minimizes the translation lookaside buffer (TLB) overhead of addressing the memory
  
  
  void kfree(const void *ptr)
  calling kfree() on a block of memory that already has been freed or on a pointer that is not an address returned from kmalloc() 
  is a bug, and it can result in memory corruption. 
  
  Calling kfree() on NULL is checked for explicitly and is safe, although it is not necessarily a sensible idea
  
  
  When to use Kmalloc :-If memory required in driver needs to be contiguous in physical memory 
                        then we have to use kmalloc for allocation of memory.

void * vmalloc(undigned long size)
vmalloc allocates contigous memory in virtual memory but it doesn't guarantee that
        memory allocated in physical memory will be contiguous.
Upon successful allocation of memory it return virtual address of first byte of allocated memory block.
On failure it returns NULL.        
void *vfree(const void *ptr);

When to use vmalloc?
When you are sure that memory required will never needs to interact with hardware in future 
or we can if you required memory only for software purpose then we should use vmalloc for allocating memory.
If you are allocating memory that only software accesses, such as data associated with a user process, there is no need for the memory to be physically contiguous.


  Kmalloc or vmalloc ??                      
  it is often hard to find physically contiguous blocks of memory, especially for large allocations.
  Allocating memory that is only virtually contiguous has a much larger chance of success. 
  If you do not need physically contiguous memory, use vmalloc():  
  Nonetheless, few allocations in the kernel use vmalloc(). Most choose to use kmalloc(), even if it's not needed,
  partly for historical and partly for performance reasons. 
  Because the TLB overhead for physically contiguous pages is reduced greatly,
  the performance gains often are well appreciated. 
  Despite this, if you need to allocate tens of megabytes of memory in the kernel, vmalloc() is your best option. 
  
  Kmalloc                                                                           Vmalloc
  1)contiguous physical memory & contiguous virtual memory   2) not guarenteed contiguous physical memory but contiguous virtual memory 
  2)use for memory accessible by H/w                         2) for allocating buffers only for S/w usage
  3) performance is high : no TLB overhead                   3) TLB overhead : so dont use if high performance required while acessing mem allocated



Rules while Allocating memory in kernel:
Decide whether you can sleep (that is, whether the call to kmalloc() can block).
If you are in an interrupt handler, in a bottom half, or if you hold a lock, you cannot.
If you are in process context and do not hold a lock, you probably can. 
specify GFP_KERNEL. / specify GFP_ATOMIC accordingly
If you need DMA-capable memory : specify GFP_DMA. 
Always check for and handle a NULL return value from kmalloc()
Do not leak memory; make sure you call kfree() somewhere. 
Ensure you never access a block of memory after you free it. 





Kernel stack:
Unlike user-space processes, code executing in the kernel has neither a large nor a dynamically growing stack.
the kernel has a small fixed-size stack - 8KB typical  --- 4KB for recent versions
Never allocate large memory on kernel stack.


#define BUF_LEN	2048

void rabbit_function(void)
{
    char buf[BUF_LEN];
    /* ...  */
}

Instead, the following is preferred:

#define BUF_LEN	2048

void rabbit_function(void)
{
    char *buf;

    buf = kmalloc(BUF_LEN, GFP_KERNEL);
    if (!buf)
        /* error! */

/* ... */
}
In the kernel, however, you should use dynamic memory any time the allocation size is larger than a handful of bytes or so

Does each process have its own kernel stack ?
Not just each process - each thread has its own kernel stack (and, in fact, its own user stack as well). 
Remember the only difference between processes and threads (to Linux) is the fact that multiple threads
can share an address space (forming a process).

There is just one kernel memory. In it each process has
> > it's own task_struct + kernel stack (by default 8K). There  is no
special address mapping for these, nor are they allocated from a special area. 

The current design is :
the kernel stack space of process and its thread_info structure are located together (at two ends because stack grows down).
This is because it offers a key benefit in terms of efficiency: the kernel can easily obtain the address of the thread_info 
structure of the process currently running on a CPU from the value of its kernel ESP register.

task's kernel-stack to store a strcture thread_info
thread_info and task-struct contain pointers to each other


Switching b/w kernel stacks of processes:
When a context of some process is entered, esp is pointed to the top of
 it's stack. That's exactly all it takes to exchange stacks. 
  The scheduler saves most of the registers onto the stack,
then it saves the stack pointer in the task_struct of the
current thread and loads the stack pointer of the next
thread to be executed. Then it simply proceeds restoring
registers from the stack.

Since registers are saved both when a thread is interrupted (or enters kernel mode through a system call or an exception)
and also by the scheduler, there will actually be two sets of registers on the stack of each thread not currently
executing on a CPU.


OK, lets say there are 20 processes running in the system. Then the
> kernel must allocate 20 * 8K = 160K just for the stacks of these
> processes. All of these 160K always occupy the kernel (kernel memory
> is never swapped out). When a process actives, ESP would switch to
> point to the corresponding stack (of that process). 

Kernel-stack for Interrupts??
Depending on architecture and kernel version, the handler may
use either the kernel stack of the interrupted thread or a
special interrupt stack.

If a local variable is declared in an ISR, where it will be stored?
It will be stored in ISR stack(IRQSTACKSIZE). The ISR runs on a separate interrupt stack only if the hardware supports it. 
Otherwise, the ISR stack frames are pushed onto the stack of the interrupted thread.
As interrupts comes per cpu, therefore ISR stack has to be per cpu.



System calls:
glibc provides wrapper code which abstracts you away from the underlying code which arranges the arguments
you’ve passed and enters the kernel.

The Linux kernel includes a file which lists each system call in a table.
There are a few scripts which run at compile time which take syscalltable and generate the syscalls_32.h file from it.
this header file provides syscall numbers, which can be used by user programs.



The Linux kernel sets aside a specific software interrupt number that can be used by user space programs to enter the kernel
The Linux kernel registers an interrupt handler for the interrupt number: 128 (0x80)
The userland program is expected to put the system call number in the eax register.
The arguments for the syscall itself are to be placed in the remaining general purpose registers.
system-call service Function indexed using syscall number in system call table.

return address and the CPU flags which encode the privilege level (and other stuff),
and more are all saved on the program stack before ia32_syscall executes.

After system call service is Executed..kernel just needs to copy these values from the program stack back into the registers where they belong and execution will resume back in userland.
this is done using iret instruction.


Fast system calls:










SCHEDULER:

From a high level, the scheduler is simply a grouping of functions that operate on given data structures.--kernel/sched.c 
A task/process/thread in the scheduler is a collection of data structures and flow of control.


a process has been initialized and placed on a run queue:

struct task_struct *p;

p->state = TASK_RUNNING ; =====> task is in run-Q

In Linux, the run queue is composed of two priority arrays:

    Active.: Stores processes that have not yet used up their timeslice

    Expired.: Stores processes that have used up their timeslice.

From a high level, the scheduler’s job in Linux is to take the highest priority active processes, 
let them use the CPU to execute, 
and place them in the expired array when they use up their timeslice.

 at some time, this process should have access to the CPU to execute.
 The two functions that are responsible for passing CPU control to different processes are schedule() and scheduler_tick()
schedule(): how the Linux kernel decides which process to execute next
scheduler_tick() : how the kernel determines which processes need to yield the CPU ??

When a timer event occurs,the current process is put on hold and the Linux kernel itself takes control of the CPU.
scheduler_tick() is a system timer isr that the kernel calls and marks processes as needing rescheduling / not needed.
When the timer event finishes, the Linux kernel normally passes control back to the process that was put on hold. However, when the held process has been marked as needing rescheduling, the kernel calls schedule() to choose which process to activate instead of the process that was executing before the kernel took control. The process that was executing before the kernel took control is called the current process.

Example:

Process A has control of the CPU and is executing.

The system timer scheduler_tick() goes off, takes control of the CPU from A, and marks A as needing rescheduling.
The Linux kernel calls schedule(), which chooses Process B and the control of the CPU is given to B.

Process B executes for a while and then voluntarily yields the CPU.
This commonly occurs when a process waits on some resource.
B calls schedule(), which chooses Process C to execute next.

Process C executes until scheduler_tick() occurs, which does not mark C as needing rescheduling.
This results in schedule() not being called and C regains control of the CPU.

The system timer scheduler_tick() goes off, takes control of the CPU from C, and marks C as needing rescheduling
The Linux kernel calls schedule(), which chooses Process A and the control of the CPU is given to A.


PROCESS states in KERNEL-SPACE:
----------------------------------

p->state = RUNNING : run-Q => ready state==> ready to run in run-Q / running on cpu.
yielding the processor:
calling schedule();==> when p->state = RUNNING,merely moves process to run-Q. this will execute again when scheduler chooses it.

sceduler can't choose to execute a process , if it is sleeping / waiting on an Event.:
SLEEPING in the kernel:
If procesing is waiting on some resource , It blocks by calling schedule().
set_current_state(TASK_INTERRUPTIBLE); or set_current_state(TASK_UNINTERRUPTIBLE);
schedule();
Interruptible and Uninterruptible Sleep:
Interruptible sleep is the preferred way of sleeping, unless there is a situation in which signals cannot be handled at all,
such as device I/O. 
p-> state = TASK_INTERRUPTIBLE  : can be wokenup by signals or by calling wake_up_process()from other process kernel code.
p-> state = TASK_UNINTERRUPTIBLE : can be wokenup only by wake_up_process() call.

########################################################################################################


SLEEPING in Kernel -Detailed Explaination:
--------------------------------------------
Typical scenario for blocking on event / sleeping:

A --> processing list items 
B---> adding items to list
To access-List : lock should be aquired.

Process A:
1  spin_lock(&list_lock);               
2  if(list_empty(&list_head)) {
3      spin_unlock(&list_lock);
4      set_current_state(TASK_INTERRUPTIBLE);
5      schedule();
6      spin_lock(&list_lock);
7  }
8
9  /* Rest of the code ... */
10 spin_unlock(&list_lock);
==========>
LOCK , listEmpty-Check
if Empty - UNLOCK , SLEEP .
when wokeup by B --> LOCK , process list-item , UNLOCK
here A-> is marked as RUNNING by wake_up_process call of B.
and is sceduled only when A get it's time slot allocated.



Process B:
100  spin_lock(&list_lock);
101  list_add_tail(&list_head, new_node);
102  spin_unlock(&list_lock);
103  wake_up_process(processa_task);

LOCK ,Add-listItem, UNLOCK, WAKEUP--> marks A - RUNNING., do other work, time-slotExp-> relinquish CPU 


Lost Wake-Up Problem:
------------------------
Race condition: After  LOCK and before SLEEP if processA time-slot Expires.
                process-B scheduled , adds item, and Wakesup-A, does some other work,after-timeslot expires moved out of cpu.
                process-A sceduled , SLEEPs...woken up only when B-sceduled Again,Adds-listItem,wakes-up A.
                processA --lost one Wakeup : common problem in kernel.

solution:
-----------
Process A:

1  set_current_state(TASK_INTERRUPTIBLE);
2  spin_lock(&list_lock);
3  if(list_empty(&list_head)) {
4         spin_unlock(&list_lock);
5         schedule();
6         spin_lock(&list_lock);
7  }
8  set_current_state(TASK_RUNNING);
9
10 /* Rest of the code ... */
11 spin_unlock(&list_lock);
====> 
A----> MARK as INTERRUPTIBLE , LOCK, check-ListEmpty, if Empty UNLOCK and yield CPU.

if processA -loses cpu before schedule()---> process B adds Item and wake_up_process(A)- marks A as RUNNING.,
B executed for some time and loses cpu.
now  when A  runs -->schedule() call merily causes A to yields CPU.==> A wont sleep.
hence..when A gets chance to run based on scheduler Algorithm , it processes ListItem.



Example code in kernel: 


4253  /* Wait for kthread_stop */
4254  set_current_state(TASK_INTERRUPTIBLE);
4255  while (!kthread_should_stop()) {
4256          schedule();
4257          set_current_state(TASK_INTERRUPTIBLE);
4258  }
4259  __set_current_state(TASK_RUNNING);
4260 return 0;

The thread cannot exit until the kthread_should_stop() function return TRUE.
while waiting for the function to return 0 : thread sleeps 
it keeps checking untill the Fn to return TRUE.,,whenever woken-up by other thread.
kthread_should_stop condition is made only after the state is TASK_INTERRUPTIBLE. 
Hence, the wake-up received after the condition check but before the call to schedule() function is not lost. 


Wait queues:  higher-level mechanism used to put processes to sleep and wake them up

wait_queue_head_t my_event;
init_waitqueue_head(&my_event);
(or)
DECLARE_WAIT_QUEUE_HEAD(my_event);

Wait:
     wait_event(&my_event, (event_present == 1) );   -------------------->  UNINTERRUPTIBLE sleep
    wait_event_interruptible(&my_event, (event_present == 1) ); --------->  INTERRUPTIBLE sleep

Wakeup:    
    wake_up(&my_event);: wakes up only one process from the wait queue.
    wake_up_all(&my_event);: wakes up all the processes on the wait queue.
    wake_up_interruptible(&my_event);: wakes up only one process from the wait queue that is in interruptible sleep. 
    
Example:
291 static int smbiod(void *unused)
292 {
299     for (;;) {
300             struct smb_sb_info *server;
301             struct list_head *pos, *n;
302
303             /* FIXME: Use poll? */
304             wait_event_interruptible(smbiod_wait,
305                     test_bit(SMBIOD_DATA_READY,
                                 &smbiod_flags));
...
...             /* Some processing */
312
313             clear_bit(SMBIOD_DATA_READY,
                          &smbiod_flags);
                     
...             /* Code to perform the requested I/O */
...
...
337     }
338
339     VERBOSE("SMB Kernel thread exiting (%d)...\n", current->pid);
340     module_put_and_exit(0);
341 }
342


Thundering Herd Problem:  arises due to the use of the wake_up_all function

scenario :  set of processes are sleeping on a wait queue, wanting to acquire a lock.
            Once the process that has acquired the lock is done with it,
            it releases the lock and wakes up all the processes sleeping on the wait queue.
            All the processes try to grab the lock. Eventually, only one of these acquires the lock
            and the rest go back to sleep.
penalty : It consumes valuable CPU cycles and incurs context-switching overheads

Q: If we already know that only one process is going to resume while the rest of the processes go back to sleep again,
   why wake them up in the first place?
A: wake_up_all function should be done carefully, only when you know that it is required.
Otherwise, go ahead and use the wake_up function that wakes up only one process at a time. 

Q: when would the wake_up_all function be used? 
A: It is used in scenarios when processes want to take a shared lock on something. 
  For example, processes waiting to read data on a page could all be woken up at the same moment. 
  
Time-Bound Sleep":
schedule_timeout(timeout), a variant of schedule():  puts the process to sleep until timeout jiffies have elapsed.
set_current_state(TASK_INTERRUPTIBLE);
schedule_timeout(20msec);

If execution of your process to be delayed for a given amount of time. 
It may be required to allow the hardware to catch up 
or to carry out an activity after specified time intervals, such as polling a device, flushing data to disk or retransmitting a network request.

1415  set_current_state(TASK_INTERRUPTIBLE);
1416  for (;;) {
1417     schedule_timeout(APM_CHECK_TIMEOUT);
1418     if (exit_kapmd)
1419         break;
1421      * Ok, check all events, check for idle
....      * (and mark us sleeping so as not to
....      * count towards the load average)..
1423      */
1424      set_current_state(TASK_INTERRUPTIBLE);
1425      apm_event_handler();
1426  }

 You also may use a more convenient API, with which you can specify time in milliseconds and seconds:
    msleep(time_in_msec);
    msleep_interruptible(time_in_msec);
    ssleep(time_in_sec); 
These higher-level routines internally convert the time into jiffies,
appropriately change the state of the process and call schedule_timeout(), thus making the process sleep.     


    
                   
                   
                   
  

   
PREEMPTION in linux:   
   
Until kernel version 2.4, only user processes were preemptive, 
i.e., in addition to time quantum expiration, an execution of current process in user mode would be interrupted 
if higher dynamic priority processes entered TASK_RUNNING state .

Toward 2.6 series of the Linux kernel, an ability to interrupt a task executing kernel code was added, 
although with that not all sections of the kernel code can be preempted.

The Linux kernel provides preemptive scheduling under certain conditions.

Through the use of the real-time Linux kernel patch PREEMPT_RT, 
support for full preemption of critical sections, interrupt handlers, and "interrupt disable" code sequences can be supported.

Preemption improves latency, increases responsiveness, and makes Linux more suitable for desktop and real-time applications

Critical sections protected by semaphores can be preempted at any time, 
as every contention will end in a schedule and there can't be any deadlock.

However, critical sections protected by fast spin locks or by hand locks cannot be preempted unless we block the timer IRQ. 
So all spin locks should be IRQ-safe.



Preemption 
----------------

On UP, spin_lock is defined as preempt_disable, and spin_unlock is defined as preempt_enable.
On SMP, they also perform locking.

The nestable preemption markers(preempt_disable and preempt_enable) operate on preempt_count,
 a new integer stored in each task_struct.

preempt_disable effectively is:

++current->preempt_count;
barrier();


and preempt_enable is:

--current->preempt_count;
barrier();
if (unlikey(!current->preempt_count
    && current->need_resched))
    preempt_schedule();



The result is we do not preempt when the count is greater than zero. 

preempt_schedule:  It sets a flag in the current process to signify it was preempted,
calls schedule and, upon return, unsets the flag:

asmlinkage void preempt_schedule(void)
{
    do {
        current->preempt_count += PREEMPT_ACTIVE;
        schedule();
        current->preempt_count -= PREEMPT_ACTIVE;
    } while (current->need_resched);
}



Implicitly locked data vs pre-emption
-----------------------------------------
In non-preemptive kernel:
per-CPU data (data structures unique to each CPU) do not require locking. 
such data is protected by its nature, is considered to be “implicitly locked”.
a task on another CPU cannot mangle the first CPU's data. 

But Implicitly locked data and preemption do not get along.
With preemption, a process on the same CPU can find itself preempted,
and a second process can then trample on the data of the first.

such data can be  protected by the existing SMP locks.

is there any other way to protect such a data without using SMP-locks??

The solution, thankfully, is simple: disable preemption around access to the data. 

For example:

int catface[NR_CPUS];
preempt_disable();
catface[smp_processor_id()] = 1;  /* index catface
                                     by CPU number */
/* operate on catface */
preempt_enable();









Uniprocessor Kernel  VS SMP-symmetric Multi-processor Kernel


If more than one process can access data at the same time, 
mutual exclusion must be introduced to protect this shared data.



race conditions occur when two processes access the same data structure in memory.
causing inconsistent states of data

if such critical sections are short,
Short-term mutual exclusion  :  



On UP systems: this could only occur if one process is preempted by the other.
 To protect critical sections, they are guarded with some sort of preempt_disable/ preempt_enable call to disable preemption,
 so a process can finish the critical section without being interrupted by another process.
 In a non- preemptive kernel, no measures have to be taken at all
In SMP-system : disabling pre-emption won't help as process2 may get sceduled in other cpu.


interrupt handlers that access shared data
interrupt handler code from interrupting a process in a critical section
short-term mutual exclusion with interrupts:
To prevent ,guard a critical section in the process context with some sort of cli/sti(disable/ enable all interrupts) call. 

SMP systems as well, because all other CPUs' interrupts are still active and can execute the interrupt handler code at any time.




processes being held up accessing a shared resource for a longer time. 
For example, once a write system call to a regular file begins, it is guaranteed by the operating system that any other read or write system calls to the same file will be held until the current one completes
long-term mutual exclusion: 

A write system call may require one or more disk I/O operations in order to complete the system call. Disk I/O operations are relatively long operations when compared to the amount of work that the CPU can accomplish during that time.
It would therefore be highly undesirable to inhibit preemption for such long operations, because the CPU would sit idle waiting for the I/O to complete

semaphores are used to solve this problem. This also holds true for SMP systems.

what is MutualExclusion :?

mutual exclusion : 
 we want changes to appear as if they were an atomic operation.
 If we can not update data with an atomic operation,
 we need to make an update uninterruptible and sequentialize it with all other processes
 that could access the data


Most SMP architectures possess some operations that read and change data within a single, uninterruptible step, called atomic operations.  
test and set (TSR)
compare and swap (CAS),
load link/ store conditional instruction pair (LL/SC).

atomic_t counter = ATOMIC_INIT(0); atomic_inc(&counter);   ==.> use such instructions



Spin Locks:

A flag variable indicates if a process is currently in the critical section (lock_var = 1) or if no process is in the critical section (lock_var = 0)
A process spins (busy waits) until the lock is reset, then sets the lock.
Testing and setting of the lock status flag must be done in one step, with an atomic operation. To release the lock, a process resets the lock variable

	
    spin lock can not be acquired recursively  ===> during second call : process spins disabling pre-emption.
     this has two implications: process cant be pre-empted till that time slot expires.
                                as the same process holds lock,no way to unlock,==>deadlock. All the time slots allocated 
                                for that process are wasted in spinning and process never finished.
     
       
 

    process acquired spinlock , ISR interrupts  that process , try to acquire it ===> deadlock.
      if code-spins in ISR: pre-emption disabled and INTRs disabled , so no way any other process being scheduled .
      ===> kernel panic  

SMP case : pr1 holds spinlock , ISR on cpu2 spins : not a problem because pr1 releses after some time.
           pr1 holds spinlock , ISR1 on cpu1 spins ,ISR2 on cpu2 also spins ==> deadlock

    so spin locks can not be used within interrupt handlers:


    A critical section in process context is guarded by spin_lock_irq() :
    irq-safe versions of spin_lock disable all interrupts on the local CPU for the critical section:
     The possibility of a deadlock is therefore eliminated.
      critical sections in interrupt handlers are guarded by the normal spin_lock().

UP : If process1 holds spinlock, ISR is stalled.
     once process1 releases spinlock, ISR runs .

SMP:
While CPU 1 (in process context) is holding the lock, any incoming interrupt requests on CPU 1 are stalled until the lock is released. An interrupt on CPU 2 busy waits on the lock, but it does not deadlock. After CPU 1 releases the lock, CPU 2 (in interrupt context) obtains it, and CPU 1 (now executing the interrupt handler) waits for CPU 2 to release it.






Sometimes it is wanted to allow spin locks to be nested. 

a nesting counter and a variable indicating which CPU holds the lock

the lock is held, the lock function checks if the current CPU is the one holding the lock. In this case, the nesting counter is incremented and it exits from the spin loop.
The unlock function decrements the nesting counter. The lock is released when the unlock function has been called the same number of times the lock function was called before. This kind of spin lock is called a recursive lock.


adaptive locks.:
 When one thread attempts to acquire one of these that is held by another thread, it checks to see if the second thread is active on a processor. If it is, the first thread spins. If the second thread is blocked, the first thread blocks as well.



Using mutexes instead of spin locks is productive, if the critical section takes longer than a context switch. Else, the overhead of blocking compared to busy waiting for a lock to be released is worse. On the pro side, mutexes imply a kind of fairness, while processes could starve on heavily contended spin locks. Mutexes can not be used in interrupts, because it is generally not allowed to block in interrupt context.

Mutex:/Binary-semaphore:
semaphores (initialized with a counter value of 1) can also be used for protecting critical sections. For performance reasons, semaphores used for this kind of work are often realized as a separate primitive, called mutex, that replaces the counter with a simple lock status flag.

surprise !!!!!!
A semaphore is a complex shared data structure itself, and must therefore be protected by an own spin lock.










##########################################################################################################
http://duartes.org/gustavo/blog/post/anatomy-of-a-program-in-memory/
Anatomy of a Program:

KERNEL SPACE :  1GB -- 0xFFFF|FFFF to ox0000|0000
==> doesn't mean that this much of memory available , that portion of address space available
    to  map to available physical memory .
In Linux, kernel space is constantly present and maps the same physical memory in all processes.
Kernel code and data are always addressable, ready to handle interrupts or system calls at any time.

USER SPACE : 3GB ---
 For a given process:
     some virtual addresses are mapped to physical memory. others are not.
      The mapped distinct bands in the address space correspond to memory segments like the heap, stack,...etc.
      starting virtual addresses for the segments are randomised  by adding offsets to their starting addresses.--For security.
      if they are same for all the processes, as in olden days-- security exploitation.
      user-space of process changes whenever a process switch happens:
      For each process there is distinct bands of address segments which map to different Physical pages.


Linux processes are implemented in the kernel as instances of task_struct, the process descriptor.
The mm field in task_struct points to the memory descriptor, mm_struct,: summary of a program’s memory.
 = the set of virtual memory areas and the page tables.
 
 
 struct vm_area_struct
 Each virtual memory area (VMA) is a contiguous range of virtual addresses
 vm_start --> first address within VMA.
 vm_end ----> first address after VMA.
 flags ----> Access permissions of Area.
 vm_file ---->  file is being mapped by the area, if any ( A VMA that does not map a file is anonymous.)
  VMAs do not care which segment they are in.
  
  Assignment:
   A program’s VMAs are stored in its memory descriptor both as a linked list in the mmap field,
   ordered by starting virtual address, and as a red-black tree rooted at the mm_rb field.
   The red-black tree allows the kernel to search quickly for the memory area covering a given virtual address.
   When you read file /proc/pid_of_process/maps, the kernel is simply going through the linked list of VMAs
   for the process and printing each one.
   : read the VMAs of currently(?)running process and display in proc.
   
   The 4GB virtual address space is divided into pages of size 4KB.
   The size of a VMA must be a multiple of page size.
   The processor consults page tables to translate a virtual address into a physical memory address. 
   To each virtual page there corresponds one page table entry (PTE) in the page tables,
   Each process has its own set of page tables; 
   whenever a process switch occurs, page tables for user space are switched as well.
   
   typical page size = 4KB ---> 12-bit offset field in address
   virtual-pages --> 20 bits : 1G pages ==> 1MB PTEs 
   each PTE 4 bytes ==> 4MB memory (1k-pages per process)
   If 100-processes==> 400MB  (100-pages per system)
   
   we cant keep some of them in Disk ==> because 
   if  pageFrame not in mem : we can get it from disk via PTE.
   if PTE is not in memory : no way to get it from Disk.
   
   solution : Another level of indirection : level-1-page table Always in memory , level-2 resides in disk.
   only first-level table needs to be reside always in memory
   
   Linux case : 3-level-page-table   PGD(page global directory)---> PMD(page Middle directory)--> PTE
   calculation:  
   
   Linux maintains the concept of a three-level page table in the architecture independent code
   even if the underlying architecture does not support it.
   Architectures that manage their Memory Management Unit (MMU) differently are expected to emulate the three-level page tables.
   For example, on the x86 without PAE enabled, only two page table levels are available. 
   (PMD) is defined to be of size 1 and “folds back” directly onto the (PGD) which is optimised out at compile time.
   
   
   during context switch:
   pointer to the current page tables is swapped
   
   
   
   Up to version 2.6.10, the Linux paging model consisted of three paging levels.
   Starting with version 2.6.11, a four-level paging mode
   PGD : page global directory
   PUD : page upper directory
   PMD : page middle directory
   PTE : page table entry
   
   
   
   
     
   
   
   assignment: Walk through ing page tables of a process in Linux ??
   
   
   
   
   
   
   
   
   
   
   
    
    ptr-to-(struct mm_struct) -->pgd_t * pgd ===> pointer to a process’ page tables.
      ?? which page-table?? where it resides?? level-1-page-table?? is level-1-page table common for all processes??
   
   PTE : Base-addr of physical-page , P,
   P ->present: 
   R/W
   U/S
   D -> Dirty    : page had a write   --sticky-flag (i.e set by cpu ,cleared by kernel)
   A -> Accessed : page accessed Read or Write-- sticky-flag (i.e set by cpu ,cleared by kernel)
   
   
   Physical memory is managed with the buddy memory allocation technique:
   
   struct page {  :
   Each physical page in the system has a struct page associated with it to keep track of 
   whatever it is we are using the page for at the moment 
   
   Each segment in program area represented by vm_area_struct
   vm_area_struct : has several virtual pages which are mapped to Physical page frames via Page tables
   
   
   
   
   
tasks in linux:
To the Linux kernel, there is no concept of a thread. Linux implements all threads as standard tasks. 
The Linux kernel does not provide any special scheduling semantics or data structures to represent threads. 
Instead, a thread is merely a process that shares certain resources with other processes.
In  Windows or Sun Solaris have  explicit kernel support for threads.

Threads are created like normal tasks, with the exception that the clone() system call is passed flags corresponding to specific resources to be shared:
clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0); //thread created with these resources shared with parent.
 normal fork() ==> implemented as clone(SIGCHLD, 0); // regular process created.
vfork() is implemented as clone(CLONE_VFORK | CLONE_VM | SIGCHLD, 0); // create a child process and block parent

vfork() differs from fork in that the calling thread is suspended until the child terminates 
(either normally, by calling _exit, or abnormally, after delivery of a fatal signal),or it makes a call to execve.
It should not call exit() -- Why ???
Until that point, the child shares all memory with its parent,including the stack.
As with fork,the child process created by vfork() inherits copies of various of the caller's process attributes 
(e.g., file descriptors, signal dispositions, and current working directory); 
the vfork() call differs only in the treatment of the virtual address space

Why- vfork ??
Under Linux, fork(2) is implemented using copy-on-write pages, so the only penalty incurred by fork(2)
is the time and memory required to duplicate the parent's page tables,and to create a unique task structure for the child.
However, in the bad old days a fork(2) would require making a complete copy of the caller's data space, 
often needlessly, since usually immediately afterward an exec(3) is done.
Thus, for greater efficiency, BSD introduced the vfork() system call, which did not fully copy the address space
of the parent process, but borrowed the parent's memory and thread of control until a call to execve(2) or an exit occurred. 
The parent process was suspended while the child was using its resources.
The use of vfork() was tricky: for example, not modifying data in the parent process depended on knowing 
which variables were held in a register.  

         
Analysis:
Initially vfork():  when there was no copy on write.==> to avoid duplication of Entire parent process memory



Kernel thread(kernel-spae-process) VS user-space process:
kernel threads: standard processes that exist solely in kernel-space., schedulable and preemptable like user-processes
kernel threads do not have an address space (in fact, their mm pointer is NULL).
a kernel thread can be created only by another kernel thread.via interface : int kernel_thread(int (*fn)(void *), void * arg, unsigned long flags)
pid_t kernel_thread(int (*fn)(void *), void *arg, unsigned long flags)
{
        return do_fork(flags|CLONE_VM|CLONE_UNTRACED, (unsigned long)fn,
                (unsigned long)arg, NULL, NULL);
}
 created via the usual clone() system call
kthread function usually implements a loop in which the kernel thread wakes up as needed, performs its duties, and then returns to sleep.
 
 kthread_create/kthread_run :   in kernel/kthread.c 
 
 
task_struct :
task_struct structure is allocated via the slab allocator to provide object reuse and cache coloring 
 Prior to the 2.6 kernel series, struct task_struct was stored at the end of the kernel stack of each process.
 This allowed architectures with few registers, such as x86, to calculate the location of the task structure via the stack pointer without using an extra register to store the location.
 from 2.6:
 a new structure, struct thread_info, was created that again lives at the bottom of the stack.
 struct thread_info {
    struct task_struct  *task;
    struct exec_domain  *exec_domain;
    unsigned long     flags;
    unsigned long     status;
    __u32         cpu;
    __s32         preempt_count;
    mm_segment_t     addr_limit;
    struct restart_block restart_block;
    unsigned long     previous_esp;
    __u8         supervisor_stack[0];
};

 
 
 
 


      
   
   
   
   
   
   
  
  
  
  
 
 
 




                
                
                
                














  
  ###################################################################################
               
     get_current() and get_thread_info()     : below is random info collected about the.
     rearrange it when time available.
     seems they are architecture dependent.
     so it is tough to find base of kernel stack.
     explore bit more.
  #####################################################################################
  #define current get_current()
static __always_inline struct task_struct *get_current(void)
{
        return this_cpu_read_stable(current_task);
}

extern struct task_struct *current_set[NR_CPUS];
/*
 *	On a single processor system this comes out as current_set[0] when cpp
 *	has finished with it, which gcc will optimise away.
 */

struct thread_info *thread = current_thread_info();

get_current() and get_thread_info() both of which are actually
 * per-thread variables implemented as per-cpu variables and thus
 * stable for the duration of the respective task

vi arch/x86/include/asm/current.h +1


kernel code that deals with processes works directly with struct task_struct. Consequently, it is very useful to be able to quickly look up the process descriptor of the currently executing task, which is done via the current macro. This macro must be separately implemented by each architecture. Some architectures save a pointer to the task_struct structure of the currently running process in a register, allowing for efficient access. Other architectures, such as x86 (which has few registers to waste), make use of the fact that struct thread_info is stored on the kernel stack to calculate the location of thread_info and subsequently the task_struct.


On x86, current is calculated by masking out the 13 least significant bits of the stack pointer to obtain the thread_info structure. This is done by the current_thread_info() function. The assembly is shown here:

movl $-8192, %eax
andl %esp, %eax


This assumes that the stack size is 8KB. When 4KB stacks are enabled, 4096 is used in lieu of 8192.

Finally, current dereferences the task member of thread_info to return the task_struct:

current_thread_info()->task;


Contrast this approach with that taken by PowerPC (IBM's modern RISC-based microprocessor), which stores the current task_struct in a register. Thus, current on PPC merely returns the value stored in the register r2. PPC can take this approach because, unlike x86, it has plenty of registers. Because accessing the process descriptor is a common and important job, the PPC kernel developers deem using a register worthy for the task.



 LogicalAddress VS LinearAddress VS physicalAddress :
 ----------------------------------------------------------
 
Logical Address : is the address which is included in the machine language instructions 
                  to specify the address of an operand or of an instruction.
                  It is X86 term : X86 Arch forces program to be devided into segments
		  logical address = Segment Address + offset
		  
Linear address : Virtual Address (0 - 4GB)		  
Physical Address: Address of memory location

MMU H/W : segmentation unit + paging unit 
logical Address --> segmentation unit --->Linear Adddrees ---> paging Unit ---> physical Address

Segmentation VS Paging:
----------------------
Segmentation : 
encourages programmers to split their applications into logically related entities,
such as subroutines or global and local data area. ==> code, local data, global data ...for each process seperately.

logical address used in Instr = (segBase addr ,offset) ==>segmentation unit ==> linear address = segBase + offset
Segmentation assigns different linear address space to each process.
==> Entire Linear addresss space(4GB) is divided b/w all the processes.

Details About segmentation (Hard ware feature of X86):
-----------------------------------------------
logical address = (segBase addr / segment selector ,offset)

segment selector  ==> ( index , TI, RPL)
index -> segment index
TI --> Table indicator: wether segment descriptor is in  GDT/LDT ??
RPL --> Requestor privilege level :
when accessing code segments ,specifies the Current Privilege Level(CPL) of the CPU when the corresponding Segment selector is loaded into cs reg.
when accessing data segments , It can be used to selectively weaken processor privelege levels.

how many privilige levels in x86 processor?? how many used in linux ?
there are 4 privilege levels in x86 -> level 0(high),1,2,3(low).
linux uses only levels 0 and 3, which are respectively called Kernel Mode and User Mode.
Note : cs register has 2-bit field that specifies the Current Privilege Level (CPL) of the CPU


Each segment is represented by an 8-byte Segment Descriptor that describes the segment characteristics.
Segment Descriptors are stored either in the Global Descriptor Table (GDT ) or in the Local Descriptor Table(LDT).
GDT and LDT are in Main Memory.
Usually only one GDT is defined, while each process is permitted to have its own LDT 
if it needs to create additional segments besides those stored in the GDT.
registers gdtr and ldtr holds address and size of GDT and  currently used LDT.

1)when segment selector is stored in segmentation register (cs/ds/ss/es/fs/gs)
TI field of the Segment Selector to determine wether GDT/LDT stores the Segment Descriptor. 
2) base address of GDT/LDT is obtained from GDTR/LDTR resp.
3)compute address of the Segment Descriptor from the index field of the Segment Selector and GDTR/LDTR content
4)compute : linear address = Base field of the Segment Descriptor + offset of logical address 
Note : there is a Non-programmable register which holds previous segment descriptor.
       because of this steps 1,2,3 needs to be performed only when segmentation register is changed.




Paging :
 maps the same linear address space into different physical address spaces.

does Linux uses Segmentation or Paging ? why ?
=> Linux prefers paging to Segmentation .
   It also uses Segmentation in very limited way i.e only when necessary by X86 Arch
   
   why linux prefers paging?
   1)Memory management is simpler when all processes use the same segment register values that is,
   when they share the same set of linear addresses
   2) for portability : most of RISC archs doesn't support Segmentation.
   
   how linux uses segmentation?
   In linux All processes running in usermode use same segments for code and data.
   similarly all processes running  in kernel mode use same segments for code and data.
   there are  four main segment descriptors used in Linux=> for usercode,userdata,kernelcode,kerneldata.
    +  Task State Segment (TSS), different for each processor in the system
   where as The maximum number of Segment Descriptors that can be stored in the GDT is 8,191 in X86 processor.
   
Segmentation in Linux:
------------------------
linear addresses associated with all segments starts at 0 and reach the addressing limit of 232 -1.
==> all processes, either in User Mode or in Kernel Mode, may use the same logical addresses

all segments start at 0x00000000  in Linux ==> logical addresses coincide with linear addresses;
that is, Offset field of a logical address always coincides with the value of the corresponding linear address.

Current Privilege Level(CPL) of the CPU indicates whether the processor is in User or Kernel Mode .
It is specified by the RPL field of the Segment Selector stored in the cs register.
when CPL is changed ( b/w user and kernel modes)
ds register must be updated with segment selector of user/kernel data correspondingly.
ss register must be updated with usermode  stack inside the user data segment or kernel mode stack inside kernel data segment.

GDT and LDT in Linux:
-----------------------
 in multiprocessor systems there is one GDT for every CPU in the system.
  All GDTs are stored in the cpu_gdt_table array in main memory.
 the addresses and sizes of the GDTs are stored in the cpu_gdt_descr array in main memory.
 
 
PAGING in Linux: ( H/W feature):
------------------
For the sake of efficiency, linear addresses are grouped in fixed-length intervals called pages ;
contiguous linear addresses within a page are mapped into contiguous physical addresses
The paging unit thinks of all RAM as partitioned into fixed-length page frames/physical pages.

"page" to refer both to a set of linear addresses and to the data contained in this group of addresses.
"page frame" refers to storage area. VS page: just block of data which may be stored in page frame.
size of page = size of page frame.

The data structures that map linear to physical addresses are called page tables ; 
they are stored in main memory and must be properly initialized by the kernel before enabling the paging unit.
paging is enabled by setting the PG flag of a control register named cr0 .
When PG = 0, linear addresses are interpreted as physical addresses.
When PG = 1, linear addresses are translated into physical addresses.

paging unit of Intel processors handles 4 KB pages.

32 bit Linear adddress : (Directory-10bits , table-10bits , offset-12bits )




##################################################################################################################

semaphores :

phrases :named semaphores , unnamed semaphores, synchronisation,sem_init vs sem_open,
reference: http://www.linuxdevcenter.com/pub/a/linux/2007/05/24/semaphores-in-linux.html


semaphore :  counters that indicate the status of a resource. the counter is protected by kernel
counter > 0 ==> resource is available
counter <=0 ===> resource is being used by others

the older Unix-based systems uses the System V version and the current Linux-based systems use the POSIX version
 However, the general behavior and technology of semaphores does not change irrespective of the version used
 
 System V Semaphores:
The interface and usage of System V semaphores is cluttered with unnecessary complications 
 
 
semaphore must be in a region of shared memory, even if you're accessing it from related processes
such as a parent and its child.


############################################################################################################

Problems arising in multithreading :   deadlocks, race conditions, incorrect behavior of threads
solutions provided by OS to solve them : Mutex, semaphores, signals and barriers

###########################################################################################################










   
   
   
   
   
   .