Operating System concepts

-->



Process:
  • An instance of proramm is called process
  • The current running prorgamm is callled process(A program in Execution.)
Thread:
Threads are not independent of one other like processes as a result threads shares with other threads their code section, data section, OS resources also known as task, such as open files and signals.
In fact, the POSIX 1003.1c standard states that all threads of a multithreaded application must have the same PID.
Process Descriptor:
The process descriptor contains several pointers to other data structures that, in turn, contain pointers to other structures.

Process State:
It consists of an array of flags, each of which describes a possible process state. In the current Linux version, these states are mutually exclusive, and hence exactly one flag of state always is set; the remaining flags are cleared.
The different process state are
  • Task wait
  • Task running
  • Task ready
  • Task Interrupted
  • Task uninterupted
  • Task traced
  • Task end.
Identifying a Process:
  • Ecah process will have an PID
  • There is limit of PIDs ,So Bitmap need to be updated to track which PIDS are free.
  • The page frame related to bitamp are never released from Main Memory.
Process descriptors handling:
Linux packs two different data structures in a single per-process memory area: a small data structure linked to the process descriptor, namely the thread_info structure, and the Kernel Mode process stack. The length of this memory area is usually 8,192 bytes (two page frames).
union thread_union {
struct thread_info thread_info;
unsigned long stack[2048]; /* 1024 for 4KB stacks */
};

Process List:
The Linux maintains the list for processes in circular double linked list.
The lists of TASK_RUNNING processes:
The all running processes are agian maintained in runqueue list.
In modern linux, the runqueue is different.
To improve the performance of sheduler , again the runqueue is split into140 different list based on the properites. Such as enqueue , dequeue etc.
Relationships Among Processes:
  • Real parent -It [P] is created by init processor
  • Parent -It is created by P
  • child -The head of the list containing all children created by P
  • siblings -The pointers to the next and previous elements in the list
Harware abstraction Layer:
HAL can basically be considered to be the driver for the motherboard and allows instructions from higher level computer languages to communicate with lower level components, such as directly with hardware.
The hardware abstraction layer (HAL) is a kernel level driver that provides an interface between the operating system and the system architecture.
A HAL, when implemented well, allows an OS to generalize many of the particulars of a system’s CPU, cache, MMU/TLBs, serial ports, NICs, display device, interrupt controller, memory map, etc., both to allow the OS to focus on “big issues” and to facilitate porting to new hardware configurations.
Usually, few parts of the HAL are written in assembly, as they are closely linked with the underlying processor
Even if the HAL represents an abstraction of the hardware architecture, since it has been mostly used by OS vendors and each OS vendor defines its own HAL, most of the existing HAL is OS dependent. In case of an OS-dependent HAL, the HAL is often called board support package (BSP). In fact, the BSP implements specific support code for a given hardware platform or board, corresponding to a given OS. The BSP includes also a boot loader, which contains a minimal device support to load the OS and device drivers for all the devices on the hardware board.
An comman HAL has list of Api's and categorised into 5 five types.
1)Kernel Hal Api's :
They perfrom context mangement (e.g context creation/deletion /switch) and atomic operations.
2)Interrupt mangement Hal Api's:
They are conventionally called nano kernel. They consist of past interrupt service routine.(user ISR will be in OS interrupt) and interrupt /interrupt vector mangement Api's (e.g interrupt enable/disable etc);
3)I/O Hal Api's :
They perform I/O device configuration/access especially bus abstraction Api's (e.g they access primary and secondary bus based on requirement) and memory amngement Api's (e.g shared memory access)
4)Resource mangment Hal Api's:
They are architecture re(configuration) Api's e.g tracking system resource usage (battery checkup),power mangement(set up cpu speed lower so that power can be saved), real time Api's etc.
5)Interrupt Handling and management
Every interrupt received requires to be routed to the appropriate handlers. For example a timer interrupt used by the RTOS as the system tick needs to routed to handlers which do the time keeping in the RTOS.

Interrupts and Exceptions
Interrupts are asycnoronus to the normal flow of execution.
Excection are synchronous to the normal flow of execution.
Interupts are classified into different categories such as
  • Based on priority
  • Based on masking and non masking
  • Based on vector and non vector locations.
  • Based on Nesting.
  • Based on Triggering pulse ( level , Rising edge , Falling Edge trigger )
  • Based on ISR and Deffered service routine (DSR).
  • Based on the internal or external case.
In Nesting scenario, higher priority interrupts can
interrupt, and be processed before, lower priority interrupts
(e.g ARM supports this features).
When individual vectors are supported, an ISR can be attached directly
to the vector for processing when the interrupt occurs. For single vector support, the software
must determine which interrupt occurred before proceeding to the appropriate ISR.
Note:In most cases, the DSR is executed immediately after the ISR completes. However, if a
thread has locked the scheduler, the DSR is delayed until the thread unlocks it. The priority scheme
is that ISRs have absolute priority over DSRs, and DSRs have absolute priority over threads.

Kernel
The internal part of the OS is often called the kernel
Kernel Components:
  • File Manager
  • Device Driver
  • Memory Manager
  • Scheduler
  • Dispatcher
  • Network manger

Scheduler: Maintains a record of processes that are present, adds new processes, removes completed processes
  • memory area(s) assigned
  • priority
  • state of readiness to execute (ready/wait)
Types: 1) short time Scheduler.
2)Medium time Scheduler.
3)Long Time Scheduler.
Alogrithims: 1)First come first job (FCFS)
2)Shortest job next (SJN)
3)Round robin (RR)
4)Fixed priority pre-emptive scheduling
5)Multilevel queue scheduling
 6)Priority Sheduling
7)bitmap sheduling.
Features: 1) Cpu ultilization
2)Turnaround time
3)Latency
4)Troughput
5)Response time
6)Dead line handling
7)Starvation free.
Scheduler alogrithims Cpu utilization Troughout Turnaround Response Time Deadline handling Starvation free
FIFO Low low high low no Yes
SJF Medium high medium medium no no
Proprity based scheduling Medium low high high yes no
Round robin schduling high medium medium high no yes
Multi queue Scheduling high high medium medium low yes


Dispatcher:
Another component involved in the CPU-scheduling function is the dispatcher. The dispatcher is the module that gives control of the CPU to the process selected by the short-term scheduler. This function involves the following:
  • Switching context
  • Switching to user mode
  • Jumping to the proper location in the user program to restart that program
The dispatcher should be as fast as possible, since it is invoked during every process switch. The time it takes for the dispatcher to stop one process and start another running is known as the dispatch latency
  • Ensures that processes that are ready to run are actually executed
  • Time is divided into small (50 ms) segments called a time slice
  • When the time slice is over, the dispatcher allows scheduler to update process state for each process, then selects the next process to run
Note: Schduler and Dispatcher are exception (interrupts)to the  CPU.

Contents
Deadlock Detection & Avoidance Programming Assignment

Deadlock Definition

 A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause (including itself).
Waiting for an event could be:
  • waiting for access to a critical section
  • waiting for a resource Note that it is usually a non-preemptable (resource). pre-emptable resources can be yanked away and given to another.

Conditions for Deadlock
  • Mutual exclusion: resources cannot be shared.
  • Hold and wait: processes request resources incrementally, and hold on to what they've got.
  • No preemption: resources cannot be forcibly taken from processes.
  • Circular wait: circular chain of waiting, in which each process is waiting for a resource held by the next process in the chain.

Strategies for dealing with Deadlock
  • ignore the problem altogether ie. ostrich algorithm it may occur very infrequently, cost of detection/prevention etc may not be worth it.
  • detection and recovery
  • avoidance by careful resource allocation
  • prevention by structurally negating one of the four necessary conditions.

Deadlock Prevention

 Difference from avoidance is that here, the system itself is build in such a way that there are no deadlocks.
Make sure atleast one of the 4 deadlock conditions is never satisfied.
This may however be even more conservative than deadlock avoidance strategy.
  • Attacking Mutex condition
    • never grant exclusive access. but this may not be possible for several resources.
  • Attacking preemption
    • not something you want to do.
  • Attacking hold and wait condition
    • make a process hold at the most 1 resource at a time.
    • make all the requests at the beginning. All or nothing policy. If you feel, retry. eg. 2-phase locking
  • Attacking circular wait
    • Order all the resources.
    • Make sure that the requests are issued in the correct order so that there are no cycles present in the resource graph.

      Resources numbered 1 ... n. Resources can be requested only in increasing order. ie. you cannot request a resource whose no is less than any you may be holding.

    Deadlock Avoidance

     Avoid actions that may lead to a deadlock.
    Think of it as a state machine moving from 1 state to another as each instruction is executed.

    Safe State

    Safe state is one where
    • It is not a deadlocked state
    • There is some sequence by which all requests can be satisfied.
    To avoid deadlocks, we try to make only those transitions that will take you from one safe state to another. We avoid transitions to unsafe state (a state that is not deadlocked, and is not safe) 
     eg.
Total # of instances of resource = 12 
(Max, Allocated, Still Needs)
P0 (10, 5, 5) P1 (4, 2, 2) P2 (9, 2, 7)     Free = 3    - Safe
The sequence  is a reducible sequence
the first state is safe.

What if P2 requests 1 more and is allocated 1 more instance?
- results in Unsafe state

So do not allow P2's request to be satisfied.

    Banker's Algorithm for Deadlock Avoidance

     When a request is made, check to see if after the request is satisfied, there is a (atleast one!) sequence of moves that can satisfy all the requests. ie. the new state is safe. If so, satisfy the request, else make the request wait.

    How do you find if a state is safe

    
    n process and m resources
    Max[n * m]
    Allocated[n * m]
    Still_Needs[n * m]
    Available[m]
    Temp[m]
    Done[n]

while () {
   Temp[j]=Available[j] for all j
   Find an i such that 
       a) Done[i] = False
       b) Still_Needs[i,j] <= Temp[j]
   if so {
       Temp[j] += Allocated[i,j] for all j
       Done[i] = TRUE}
   }
   else if Done[i] = TRUE for all i then state is safe
   else state is unsafe
}

    Detection and Recovery

     Is there a deadlock currently?
    One resource of each type (1 printer, 1 plotter, 1 terminal etc.)
    • check if there is a cycle in the resource graph. for each node N in the graph do DFS (depth first search) of the graph with N as the root In the DFS if you come back to a node already traversed, then there is a cycle. }
    Multiple resources of each type
    • m resources, n processes
    • Max resources in existence = [E1, E2, E3, .... Em]
    • Current Allocation = C1-n,1-m
    • Resources currently Available = [A1, A2, ... Am]
    • Request matrix = R1-n,1-m
    • Invariant = Sum(Cij) + Aj = Ej
    • Define A <= B for 2 vectors, A and B, if Ai <= Bi for all i
    • Overview of deadlock detection algorithm,

      Check R matrix, and find a row i such at Ri < A.
      If such a process is found, add Ci to A and remove process i from the system.
      Keep doing this till either you have removed all processes, or you cannot remove any other process.
      Whatever is remaining is deadlocked.


      Basic idea, is that there is atleast 1 execution which will undeadlock the system

    Recovery
    • through preemption
    • rollback
      • keep checkpointing periodically
      • when a deadlock is detected, see which resource is needed.
      • Take away the resource from the process currently having it.
      • Later on, you can restart this process from a check pointed state where it may need to reacquire the resource.
    • killing processes
      • where possible, kill a process that can be rerun from the beginning without illeffects
Subscribe to: Posts (Atom)