Resource - allocation Graph
> A set of vertices and a set edges E.

- V is partition into two types:
P={P1,P2,...Pm}, the set consisting all the processes in the system.
R= {R1,R2,...,Rm}, the set consisting of all resources types in th system.
>request edge-directed edge P1->R1
>assignment edge-directed- directed edge R1 ->P1

Resource allocation graph (cont.)

> Process



>resource type with 4 instances

>P1 is request an instance of R1

>P1 is holding an instance of R1


Example of Resource allocation Graph

process 1 request instances of resource 1
resource 1 is holding an instances of process 2
process 2 request instance of resource 3

resource 3 is holding an instance of process 3
resource 2 request instances of process 1 and process
resource 4 is a resource type with 4 instances.

Resource allocation graph With deadlock




















Resource allocation graph with a cycle but no deadlock

Deadlock Characterization
>mutual exclusion
>Hold and Wait
>No preemption
>Circular wait

2.Methods for handling deadlocks
>Ensure that the system will never enter a deadlock state.
>Alow the system to enter a dealock state and then recover.
>Ignore the problem and pretend that dealocks never occur in the system; used by most opearting systems, including unix.

3.Deadlock Prevention
>Mutual Exclusion- Not required for sharable resources;
must hold for nonshareable resources.
>Hold and Wait- must guarantee that whenever a process request a resource, it does not hold any other resources.
-require process to request and be allocated all its resource before it begins execution, or allow process to request a resource only when the process has none.
- low resource utilization: starvation possible.

>No Preemption
if a process that is holding some resoureces requests
another resource that cannot be immediately allocated to it,
then all resources currently being held are released
- preemted resources are added to the list of resources for which the process is waiting.
process will be restarted only when it can regain its old resources, as well as the new
ones that it is requesting
>Circular wait- impose a total ordering of all resource types, and require that each process requests resources in an incresing order of enumeration..,

4.Deadlock Detection

Detection with One Resource of Each Type (1)

•Note the resource ownership and requests
•A cycle can be found within the graph, denoting deadlock

Detection with One Resource of Each Type (2)

Data structures needed by deadlock detection algorithm

Deadlock

5.Deadlock Recovery



•Deadlock must be untangled once detected, so the system returns to normal quickly
•All recovery methods have at least one victim
•Recovery Methods:
–Terminate every job that’s active in the system and restart them from the beginning
–Terminate only the jobs involved in the deadlock and ask their users to resubmit them
–Identify jobs involved in deadlock and terminate them one at a time


–Jobs that keep a record (snapshot) of their progress can be interrupted
–Select a nondeadlocked job, preempt its resources, allocate them to a deadlocked process
–Stop new jobs from entering system, which allows nondeadlocked jobs to run to completion so they’ll release their resources (no victim)



•Select the victim that will have the least-negative effect on the system
•Factors to be considered to select a victim:
–Priority of job under consideration: high-priority jobs are usually untouched
–CPU time used by job: jobs close to completion are usually left alone
–Number of other jobs that would be affected if this job were selected as the victim
–Jobs that are modifying data shouldn’t be selected for termination


-By flushing one or more process that involved in deadlock until there is no deadlock

thread Scheduling

Process/Thread structure

Fundamental schedulable entity in the system
Represented by ETHREAD that includes a KTHREAD
Queued to the process (both E and K thread)
IRP list
Impersonation Access Token
Unique thread ID
Associated User-mode Thread Environment Block (TEB)
User-mode stack
Kernel-mode stack
Processor Control Block (in KTHREAD) for cpu state when not running

SUBSTANTIAL INFORMATION ABOUT THREAD OF AT LEAST THREE OS
=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.
=Windows 2000Implements the one-to-one mappingEach thread contains
A thread ID
Register set
Separate user and kernel stacks for user and kernel modes
Private data storage area used by various run-time libraries and dynamic link libraries (DDLs)
The latter three are known as the context of the thread and are architecture-specific to HW
=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)

Different cpu scheduling algorithms



CPU Scheduling of Batch Processes
-Submitted with a good estimate of their resource needs, via job control statements
-Upper limits the OS is expected to enforce
-Generally expected that the OS will give preferential treatment to processes with lower resource needs.
-Resource estimates may also include the specification of an initial priority for a job

For batch processesscheduling occurs at 2 levels:Long-term and short term
Job Scheduling (long term)

-Job scheduling involves deciding which job (job step) to admit into the system as a process. A job is a program which has been submitted to the system, but which has not been loaded into memory.
-Initial resource estimates play an important role of scheduling at the job level. A job can not be loaded until sufficient resources are available.

A “Job”

1) typically consists of multiple steps

2) Job control statements provide information about the resource needs of each step. Including program to execute, maximum memory requirements, and cpu time limits, and user information

3) Waiting jobs are stored in one or more job queues, ordered by priority or class, which is determined by their announced resource needs.

4) System processes called initiators, examine the job queues and selects jobs when the system is ready for more work.

5) Jobs are admitted only when sufficient resources are available to begin the first “step”. Also each additional step is admitted only when resources are available.

6) Once a step has been admitted, it holds all of its resources until it is complete. A timer is set to ensure that it does not exceed its planned processor time.

Short term scheduling

-When the processor (CPU) is available, a process from the ready queue(s) is selected according to some type of algorithm.
-The process is then given control of the CPU and continues running until:

-The process terminates
-The process voluntarily suspends itself (sleep)
-The process requests an I/O transfer or other service for which it must wait
-The process is stopped because it has exceeded its processor time quantum (maximum CPU time for the entire job, or step!)
-IF preemption is allowed: a higher priority process becomes ready. (preemption is usually not used in a batch environment.)