CS 43 Operating System - Chapter 5: Process Management

Process Management:

• Deadlock

• Livelock

• Starvation

Deadlock

• A problem occurring when the resources needed by some jobs to finish

  execution are held by other jobs, which, in turn, are waiting for other resources to become available. Also called deadly embrace.

Livelock

• A locked system whereby two (or more) processes continually block the

  forward progress of the others without making any forward progress themselves. It is similar to a deadlock except that neither process is blocked or obviously waiting; both are in a continuous state of change.

Starvation

• The result of conservative allocation of resources in which a single job is prevented from execution because it’s kept waiting for resources that never become available.

7 Cases of Deadlock:

• Case 1: Deadlocks on File Requests

• Case 2: Deadlocks in Databases: Locking

• Case 3: Deadlocks in Dedicated Device Allocation

• Case 4: Deadlocks in Multiple Device Allocation

• Case 5: Deadlocks in Spooling

• Case 6: Deadlocks in a Network

• Case 7: Deadlocks in Disk Sharing

Conditions for Deadlock:

• Mutual Exclusion

• Resource Holding/Hold and Wait

• No preemption

• Circular Wait

Mutual Exclusion

• One of four conditions for deadlock in which only one process is

  allowed to have access to a resource.

Resource Holding

• One of four conditions for deadlock in which each process refuses to

  relinquish the resources it holds until its execution is completed even though it isn’t using them because it’s waiting for other resources.

No preemption

• One of four conditions for deadlock in which a process is allowed to

  hold on to resources while it is waiting for other resources to finish execution.

  prevention: a design strategy for an operating system where resources are mana

Circular Wait

• one of four conditions for deadlock through which each process

  involved is waiting for a resource being held by another; each process is blocked and can’t continue, resulting in deadlock

Locking

• A technique used to guarantee the integrity of the data in a database through

  which the user locks out all other users while working with the database.

Process Synchronization

• (1) The need for algorithms to resolve conflicts between processors in a multiprocessing environment; or (2) the need to ensure that events occur in the proper order even if they are carried out by several processes.

Strategies for Handling Deadlocks:

• Prevention

• Avoidance

• Detection

• Recovery

Prevention

• A design strategy for an operating system where resources are managed in

  such a way that some of the necessary conditions for deadlock do not hold.

Avoidance

• The dynamic strategy of deadlock avoidance that attempts to ensure that

  resources are never allocated in such a way as to place a system in an unsafe state.

Detection

• The process of examining the state of an operating system to determine

  whether a deadlock exists.

Unsafe State

• A situation in which the system has too few available resources to guarantee the completion of at least one job running on the system. It can lead to deadlock

Spooling

• A technique developed to speed I/O by collecting in a disk file either input

  received from slow input devices or output going to slow output devices, such as printers.

Race

• A synchronization problem between two processes vying for the same resource.

Safe State

• The situation in which the system has enough available resources to

  guarantee the completion of at least one job running on the system.

Recovery

• The steps that must be taken, when deadlock is detected, by breaking the

  circle of waiting processes.

Victim

• An expendable job that is selected for removal from a deadlocked system to

  provide more resources to the waiting jobs and resolve the deadlock.

On removal:

- It requires that the job be restarted from the beginning or from a convenient midpoint

Principles of Banker’s Algorithm:

• The Banker’s Algorithm is based on a bank with a fixed amount

  of capital that operates on the following principles:

• No customer will be granted a loan exceeding the bank’s total capital.

• All customers will be given a maximum credit limit when opening an account

• No customer will be allowed to borrow over the limit.

• The sum of all loans won’t exceed the bank’s total capital.

Recovery Algorithms:

• First method

• Second method

• Third method

• Fourth method

• Fifth method

• Sixth method

First method

- Simplest recovery method, drastic, it terminates every job that is active in the system and restart from the beginning

Second method

- Terminates only the jobs involved in the deadlock and ask their users to resubmit them

Third method

- Identify which jobs are, terminate them one at a time

Fourth method

- Only if the job keeps a record, a snapshot

Fifth method

- Selects a non-deadlocked job, preempts the resources it's holding, allocates them to a deadlocked process

Sixth method

- Stops new jobs, allow non-deadlocked jobs to run to completion

Factors to consider Victim that will have least-negative effect on the system:

• The priority of the job under consideration
  

• CPU Time used by the job
  

• The number of other jobs that would be affected if this job were selected as the victim