Dead Lock, Resource Allocation Graph & Safe State [PART 1]

Dead Lock

Dead lock is a situation where no process can continue due non availability of resources.

Resource allocation graph

R1 &R2  are non sharable resources

Here P1 needs R1 &R2 at the same time.But  since R2 is assigned to P2  is not possible.

Here P2 needs R1 &R2 at the same time. But  since R1 is assigned to P1 it  is not possible

So  circular wait and  hence deadlock occurs.

Resource allocation graph without dead lock

Conditions for deadlock

·        Deadlock happens if following 4 conditions occur simultanesoly

1.No mutual exclusion

2.Hold and wait

3.No preemptopn

4.circular wait

Dead lock handling

1.Dead lock prevention

      2. Dead Lock Detection

      3.Dead lock Avoidance

       4,Recovery from dead lock

Dead lock prevention

Avoid all the 4 conditions(at least one) above mentioned

.Mutual exclusion :Mutual exclusion must hold for sharable(if there is problem if accessed) resources.

Eg:Printer (a printer) can not be shared while printing a particular document.(jobs are spooled here)

Read only files (intrinsically non-sharable means data can’t be written) can be shared without any problem.

Hold and wait

 To avoid it

1.      When process  request  one  resource ,it does not hold any other resource ( to implement it all process request all other resources  before starting execution)

Eg:requests dvd,h.disk and printer(then it does not request for further resources)

Copies files from DVD to Disk,then prints,hods printer until last.

2.      An alternate protocol allows a process to request resources only when it has none.(tempraily release the present ones,and again request)

Eg  Requests dvd  and Disk ,uses (reads) DVD,releases DVD and H disk.

      Requests H disk and printer disk file is copied to printer.

No Preemption

To avoid it

1st method

·       If a process holding some resources and requests another resource that can be immediately allocated  the process must wait.

·       Then releases all the resources and these resources are added

to the list of  resources for which the process is waiting

·       The process will be restarted  only when it regains its old resources as well as new ones that it is requesting.

  2^nd method

·       If a process requests some resources, check whether they are available ,if  available  allocate them

·       If they are not available check whether they are allocated to some other process that is waiting for additional resources , preempt the allocated resources  from the process waiting for additional resources and allocate them to requesting process.

·       If resources are neither available nor held by a waiting process

The requesting process must wait.(At this time it’s resources  can be  preempted( since it is waiting)  ,if another process request them)

·       A process can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted  while it was waiting.

Circular  Wait

  To avoid it

·       Assign a resource or resource type a number; F:R->N

N is natural nos

Eg.

R1=1

R2=2

·       Each process can request any number of  a resource type  say  Ri

After that the process can request  instances of resource type

If F[Rj] >F[Ri].

Eg:

     1.P1 requests R1

 2. Then holds it .

3.Then p1 requests for R2 (it’s ok since F(R2)=2  >F(R1)=1)

      1.P2 requests R2

Then holds it .

3.Then p2 requests for R1 (it’s not ok since F(R1)=1  is not  >F(R2))

So circular wait will not occur.(p2….>R1 not possible)

Dead lock avoidance

·       In general, request  restrictions employed in deadlock prevention methods  leads poor device resource utilization. And leads to less through put.

·       If we  have the information how additional resources are going to be requested and released, if situation permits we can avoid  deadlock keeping the resource utilization  as maximum as possible.

For eg

 If  process p1 needs tape drive  and then one printer

 If  process p2 needs one printer(released in time for p1) then tape drive(by that time tape drive should be released by p1)

We can avoid dead lock.

Safe state

 A state is said to be safe the system can allocate resources to each process  in some order and still avoid a deadlock.

Dead Lock, Resource Allocation Graph & Safe State [PART 2]

Concurrent  co-operating processes.

·        Processes are concurrent if they exist at the same time.concurrent process can function completely indepently to one another. 

Need for interprocess  synchronization

·        If different processes are  dealing  with commonly shared variables

              Synchronization should be there.

            Eg:Let P1 and P2 be two processes works one sane commly shared variable’lines entered’

Ø P1 increments  ‘lines entered’

Ø  P2 increments ‘lines entered’

If both simultaneously tries to access  ‘linesentered’ there can be problems.

So to avoid this p1 and p2 need to communicate(this is known as interprocess synchronization..(when one work other shoud not work).

Critical section

Ø A process is said to be in its critical section when it is accessing shared modifiable data, when a process is in critical section other processes are out side its critical section.

Mutual Exclusion

Ø When  one works other does not.

Mutual Exclusion algorithms

1.Dekkers Algorithm

2.Semaphore

3.test and set

Dekkers algorithm

Algorithm1

 Program version one

 Var processnumber integer

Procedure processone

Begin   

    Begin

        While processnumber=2do;

          Criticalsectionone

          Processnumber=2

         Otherstuffone;

    End

End

Procedure processtwo

Begin

    Begin

        While processnumber=1do;

          Criticalsectiontwo

         Processnumber=1

        Otherstuffone;

    End

End

Begin

processnumber=1

     parbegin

         processone

         processtwo

    parend

End

Advantage: Mutual exclusion is guaranteed.

Disadvantage: First  proceess1 itself should be executed b’cause (processs number=1 initially).

·        Here there was only one synchronization variable processnumber

·        We try to rectify the problem in the next algorithm by bu sing two

Synchronization variables

Algorithm2

 Program version two

 Var p1 inside,p2 inside:boolean

Procedure processone

Begin  

While true do

    Begin

        While p2 inside do;

          P1 inside=true

          criticalsectionone

          p1inside=false

         Otherstuffone;

    End

End

Procedure processtwo

Begin

        While p1 inside do;

          P2 inside=true

          criticalsectionone

          p2inside=false

         Otherstuffone;

    End

End

Begin

 P1inside=false

P2inside=false

     Parbegin

         processone

         processtwo

    parend

End

Disadvantage:If both tries at the same time  both will enter critical section no mutual exclusion.

Algorithm3

Program version three

 Var p1 inside,p2 inside:boolean

Procedure processone

Begin  

While true do

    Begin

       P1wantstoenter=true

        While p2wantstoenter  do;

         Criticalsectionone

          P1wantstoenter=false

         

         Otherstuffone;

    End

End

Procedure processtwo

Begin

       P2wantstoenter=true

        While p1wantstoenter  do;

         Criticalsectionone

          P2wantstoenter=false         

         Otherstuffone;

    End

End

Begin

P1wantstoenter=false

P2wantstoenter=false

     Parbegin

         processone

         processtwo

    parend

End

Dsiadv:If both tries at the same time both waits indefinitely(deadlock happens)\

  To avoid the deadlock in algorithm 3 the delay concept is used .

Program version four

 Var p1 wantstoenter,p2watstoenter:boolean

Procedure processone

Begin  

 While true do

    Begin

         P1wantstoenter=true

              While p2wantstoenter  do

                 Begin

                           P1wantstoenter=false

                           Delay(random few cycles)

                          P1wantstoenter=true

               End

     

           Criticalsectionone

           P1watstoenter=false

           Otherstuffone;

    End

End

Procedure processtwo

Begin  

 While true do

    Begin

         P2wantstoenter=true

              While p1wantstoenter  do

                 Begin

                           P2wantstoenter=false

                           Delay(random few cycles)

                          P2wantstoenter=true

               End

     

           Criticalsectiontwo

           P2watstoenter=false

           Otherstuffone;

    End

End

Begin

P1wantstoenter=false

P2wantstoenter=false

     Parbegin

         processone

         processtwo

    parend

End

.

Advantage

·        :Mutual exclusion is guaranteed and deadlock will not occur.

Disadv

·        Sometimes indefinite delay may occur(especially when simultaneous

Access is attempted random delay generated if same)

·        So we make use of another alogorithm .

·        It makes use of a variable ‘favouved process’

Program dekkers algorithm

 Var  favouredprocess(first,second)

         p1 wantstoenter,p2watstoenter:boolean

Procedure processone

Begin  

 While true do

    Begin

         P1wantstoenter=true

         While p2wantstoenter  do \\when p2wants to enter =true while works  otherwise quits

{                       If favoured process=second then

                 Begin

                           P1wantstoenter=false

                           While favouredprocess=second do;//if so waits

                          P1wantstoenter=true

               End

  }   

           Criticalsectionone

           favouredprocess=second

           p1wantstoenter=false

           Otherstuffone;

    End

End

Procedure processtwo

Begin  

 While true do

    Begin

         P2wantstoenter=true

              While p1wantstoenter  do

{

                        If favoured process=first then

                 Begin

                           P2wantstoenter=false

                           While favouredprocess=first do;

                          P2wantstoenter=true

               End

  }   

           Criticalsectiontwo

           favouredprocess=first

           p2wantstoenter=false

           Otherstufftwo;

    End

End

Begin

P1wantstoenter=false

P2wantstoenter=false

Favoured process=first

     Parbegin

         processone

         processtwo

    parend

End

Semaphore

A semaphore is a protected variable which is used for mutual exclusion .

It can be altered by only two operations

P and S

P(S)

Is S>0 then S=S-1

 Else (wait on S)

V (S)

If (one or more processers are waiting on s)

Then (let one of these processes proceed)

Else s-s+1

Binary semaphore

 .assumes value 0 or 1

Counting semaphore

·        Can assume non negative values.

Program semaphoreexampleone

Procedure processone

Begin  

 While true do

    Begin

         preliminarystuffone=true

              p(active)

          criticalsectionone;

         v(active)

                          otherstuffone;

               End

    

Program semaphoreexampleone

Procedure processtwo

Begin  

 While true do

    Begin

         preliminarystufftwo=true

              p(active)

          criticalsectiontwo;

         v(active)

                          otherstuffone;

               End

Begin

Semaphoreinitialize(active,1)

     Parbegin

         processone

         processtwo

    parend

End

Process P1

Repeat

{

While test &set(lock) do no op;

Test &set(lock)

Critical section

Lock=false

}

Until false

Process P2

Repeat

{

While test &set(lock) do no op;

Test and set(lock)

Critical section

Lock=false

}

Until false

Lock=false

Begin

Process p1

Process p2

End

Test &set sets lock =true by the following technique

Function Test &set (var target :Boolean):Boolean

Begin

Test&set =target

Target =true

End

Operating System

Operating System Structures

(Perspectives)

·       Services provided by OS.

·       Interface by users and programmers

·        How Os disassembles the system to  components and connecting them?.

System Components

1.    Process

A program may contain more than one/many  processes

                      A process is a program in execution./Unit work of a system.

Every instruction execution is part of a process,

Ø Creating and deleting both user and system processes.

Ø Resource management

Ø Process synchronization

Ø Process communication

Ø Dead lock handling

2.    Main memory

Ø Main memory is the repository for data shared by cpu and i/o devices

Ø A program is to be allocated to absolute address(address in main memory) to be executed.

Ø Once program is completed execution memory should be freed , memory space is declared available.

Ø Instructions (lines of a program ) should be in main memory for the  fetching  by the  cpu. 

Ø OS should do the following

                1.Should track which parts of memory are currently being used

          2.Deciding which processes are to be loaded to memory when memory space become available.

          3. Allocating and deallocating memory space as needed.

3.    File management

Ø Files are collection of related information defined by its creator.

Ø Files consists of sequence of bytes and as records meaning defined by its creators. They usually are stored  in secondary storage and sometimes in primary memory.

Ø Os takes care of

ü  Creation &deletion of files

ü Creation &deletion of directories

ü Mapping files to secondary storage device.

ü Backing up of files.

4       I/O system management

Ø The i/o sub system(DMA etc) hides the details of i/o operation from OS

Ø I/o subsystem consists of component that manes buffering, caching  and spooling.

Ø It consists of device diver interface.

5       Secondary storage management

Ø Free space management

Ø Storage allocation

Ø Disk scheduling

6       Networking

Ø  Networking OS should taek care of many processors with individual memory.

Ø Protocols like FTP,NFS(remote login),HTTP

Are used

                                                 

7       Protection System

Ø Protection of resources ,processes from invalid users,other process’s activities etc.

8       Command-Interpreter System

Ø Commands are prewritten programs (user inter face of OS )i.e shell

System Programs

• File management:to create,delete ,copy,rename,print,dump,list and manipulate fules and directories
• Status information:informs system,time,memory usage,cpu usage etc
• File modification:Text editors which are capable of modifying content.
• Programming language support:Complilers,asseblers, and interpreters for common programming languages.
• Prgramloading and execution:Loadersmlinkage editors debuugers etc.
• Communications:emails,meassage passing systems :eg:talk,wall in Linux

System structure

            Resident monitor: Responsible for  editing tam ,flash memory etc.