Example of a Resource Allocation Graph

• no cycle IMPLIES no deadlock
• deadlock IMPLIES cycle (necessary condition)
• cycle IMPLIES maybe deadlock (but not sufficient condition)
  single instance resource AND cycle IMPLIES deadlock
• (necessary and sufficient
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  

Resource-Allocation Graph

A set of vertices V and a set of edges E.

• V is partitioned into two types:
  P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
  R = {R1, R2, …, Rm}, the set consisting of all resource types in the system.


• request edge – directed edge P1 => Rj
  


• assignment edge – directed edge Rj => Pi
  

DEADLOCK RECOVERY

• Abort all deadlock processes and release resource - too drastic - will lead to loss of work
  
• Abort one process at a time - releasing resources until no deadlock How do we determine which process to abort first ? - priority ordering, process which has done least work
  
• Selectively restart processes -from a previous checkpoint i.e. before it claimed any resources difficult to achieve - sometimes impossible
  

DEADLOCK DETECTION

• The system may enter a Deadlock state
• the system needs:

-An algorithm that periodically whether a deadlock has occured in the system

-a procedure to recover

• TWO Algorithm

-one instance per resource type.

-multiple instances per resource type

DEADLOCK PREVENTION

Attacking Mutual condition

• never grant exclusive access. but this may not be possible for several resources.

Attacking pre-emption

• 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.

Methods for Handling Deadlocks

Deadlock Prevention.

• Disallow one of the four necessary conditions for deadlock.

Deadlock Avoidance.

• Do not grant a resource request if this allocation have the potential to lead to a deadlock.

Deadlock Detection.

• Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it.
  

Ignore the problem...

• Makes sense if the likelihood is very low

Deadlock Characterization

Necessary conditions:
1) Mutual exclusion:
• at least one shared resource is held
2) Hold and wait:
• a process must be holding at least one resource and
waiting for another
3) No preemption:
• cannot steal a resource away from a process
4) Circular wait:
• E.g., A is waiting for B who is waiting for C who is
waiting for A.

REAL-TIME SCHEDULING

To support multiprogramming
• Large numbers of independent processes
• Simplified administration
• E.g. CDF wolves, compute servers

• To support parallel programming
• “job” consists of multiple cooperating/communicating threads and/or processes
• Not independent!

THREAD SCHEDULING

part of the OS (usually) that is responsible for sharing the available CPUs out between the various threads. How exactly the scheduler works depends on the individual platform, but various modern operating systems (notably Windows and Linux) use largely similar techniques that we'll describe here. We'll also mention some key varitions between the platforms.

Across platforms, thread scheduling1 tends to be based on at least the following criteria:

• a priority, or in fact usually multiple "priority" settings that we'll discuss below;
  
• a quantum, or number of allocated timeslices of CPU, which essentially determines the amount of CPU time a thread is allotted before it is forced to yield the CPU to another thread of the same or lower priority (the system will keep track of the remaining quantum at any given time, plus its default quantum, which could depend on thread type and/or system configuration);
  
• a state, notably "runnable" vs "waiting";
  
• metrics about the behaviour of threads, such as recent CPU usage or the time since it last ran (i.e. had a share of CPU), or the fact that it has "just received an event it was waiting for".

Different cpu scheduling algorithms

First Come, First Served (FCFS)

>> Non-preemptive
>> Treats ready queue as FIFO.
>> Simple, but typically long/varying waiting time.

Shortest Job First (SJF)

>> Give CPU to the process with the shortest next burst
>> If equal, use FCFS
>> Better name: shortest next cpu burst first

Priority Scheduling Algorithms
>> Priority associated with each process
>> CPU allocated to the process with highest priority
>> If equal, use FCFS
=> Internal Priority (time limits, mem requirements, number of open files)
=>External Priority (Critera outside the OS. Choice related to computer usage)

Round-Robin (RR)

>> FCFS with Preemption
>> Time quantum (or time slice)
>> Ready Queue treated as circular queue

THREADS of OPERATING SYSTEM

Linux Threads

[ ] >Linux refers to them as tasks rather than threads

[ ] >Thread creation is done through clone() system call

[ ] >Clone() allows a child task to share the address space of the parent task (process)

Windows XP Threads


[ ]>Implements the one-to-one mapping

[ ]>Each thread contains
[ ]>A thread id
{}Register set
{}Separate user and kernel stacks
{}Private data storage area

[ ]>The register set, stacks, and private storage area are known as the context of the threads

[ ]>The primary data structures of a thread include:
{}ETHREAD (executive thread block)
{}KTHREAD (kernel thread block)
{}TEB (thread environment block)

Java Thread

• Java thread are managed by the JVM

• Java thread may created by:

> Extending thread class

> Implementing the Runnable inteface

• In Java, each thread is represented by an object of class java.lang.Thread, which handles the necessary bookkeeping and provides methods for controlling the thread