RESOURCE ALLOCATION GRAPH

RESOURCE ALLOCATION GRAPH

1) A RESOURCE ALLOCATION GRAPH

--resource 2 holding an instance of process 2 and process 1

--process 1 request instances of resource 1 and process 2 request instance of resource 3.

--resource 1 is holding an instance of process 2

--resource 3 is holding an instance of process 3

--and resource 4 is a resource type with 3 instances.


2)RESOURCE ALLOCATION GRAPH WITH A DEADLOCK

--resourse 2 is holding an instances of process 1 and process 2

--process 1 request instance 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

--process 3 request instance of resource 2

--and resource 4 is a resource type with a 3 intances

3) RESOURCE ALLOCATION GRAPH WITH A CYCLE BUT NO DEADLOCK

--process 1 request instances of resource 1

--resource 1 is holding an instance of process 2 and process 3

--process 3 is request instance of resource 2

--and resource 2 request instance of process 4

4) RESOURCE ALLOCATION GRAPH FOR DEADLOCK AVOIDANCE



--resource 1 is holding an instance of process 1

--process 2 request an instance of resource 1

--process 1 and process 2 request instance of resource 2

5) UNSAFE STATE IN RESOURCE ALLOCATION GRAPH

--resource 1 is holding an instance of process 1

--process 2 request an instance of resource 1

--process 1 request instance of resource 2

--resource 2 is holding an instance of process 2

RESOURCE ALLOCATION GRAPH

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.
--requests edge-directed edge P1->R1
--assignment edge-directed edge R1->P1





how would you know if there's a deadlock based on the resource allocation graph?

-if the graph contains no cycle=>no deadlock
-if the graph contains a cycle-
---if only one instance per resource type,then deadlock.
---if several instance per resource type.possibility of deadlock.

DEADLOCK

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
Successively withdraw resources from a process and give to another process until deadlock is broken. How to choose which processes and which resources ?
1.Complex decisions due to the large number of processes present within a system
2.Difficult to automate
3.Use Operator to resolve conflicts - BUT this requires the operator to have skill and understanding of what processes are actually doing

DEADLOCK

DEADLOCK DETECTION-

The system may enter a deadlock state.
The system needs:
-an algorithm that periodically determines whether a deadlock has occured in the system.
-a procedure to recover from a deadlock.

TWO algorithms:
-One instance per resource type.
-Multiple instances per resource type.

DEADLOCK

Deadlock prevention
• Attack mutual exclusion– we always want to minimize the number ofnon-sharable resources, but it is notusually possible to eliminate all of them.
• Attack the no preemption condition– cannot usually take a resource away froma process.
• Attack hold and wait
– require each process to request and beallocated all resources before it beginsexecuting
– before requesting a new resource releaseall locks on other resources and reacquire
– Problems: low resource utilization,starvation
• Attack circular wait.
– This is where most of the effort ofdeadlock prevention is focused.
– Design a hierarchy of lock acquisition suchthat there are no cycles.
– A great idea in theory, but difficult toimplement in practice because theunderlying code does not usually follow anacyclic hierarchy.

DEADLOCK

Methods for Handling Deadlock
• Prevent– write code such that the necessary conditions cannever hold simultaneously
• Avoid– dynamically ensure that a deadlock state is notreachable.
• Detect and recover– allow deadlock but provide mechanisms to detectit and recover (e.g., kill a process)
• Ignore (ostrich approach)– pretend they cannot occur and reboot if they do.

DEADLOCK

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 andwaiting 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 iswaiting for A.

REAL-TIME SCHEDULING

REAL-TIME SCHEDULING

--Static table-driven approach
For periodic tasks.
Input for analysis consists of : periodic arrival time, execution time, ending time, priorities.
Inflexible to dynamic changes.
General policy: earliest deadline first.

--Static priority-driven preemptive scheduling
For use with non-RT systems: Priority based preemptive scheduling.
Priority assignment based on real-time constraints.
Example: Rate monotonic algorithm

--Dynamic planning-based scheduling
After the task arrives before execution begins, a schedule is prepared that includes the new as well as the existing tasks.
If the new one can go without affecting the existing schedules than nothing is revised.
Else schedules are revised to accommodate the new task.
Remember that sometimes new tasks may be rejected if deadlines cannot be met.

--Dynamic best-effort scheduling: yused in most commercial RTs of today ytasks are aperiodic, no static scheduling is possible ysome short-term scheduling such as shortest deadline first is used. yUntil the task completes we do not know whether it has met the deadline.

REAL-TIME SCHEDULING

MULTI-PROCESSOR SCHEDULING

• Why use a multiprocessor?

-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!

• Given a set of runnable threads, and a set of CPUs, assign threads to CPUs

• Same considerations as uniprocessorscheduling

• Fairness, efficiency, throughput, response time…

• But also new considerations

-- Ready queue implementation

--Load balancing

-- Processor affinity

THREAD SCHEDULING

Thread Scheduling

In our introduction to how threads work, we introduced the thread scheduler, 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.
Note that we'll continue to talk about a single thread scheduler. On multiprocessor systems, there is generally some kind of scheduler per processor, which then need to be coordinated in some way. (On some systems, switching on different processors is staggered to avoid contention on shared scheduling tables.) Unless otherwise specified, we'll use the term thread scheduler to refer to this overall system of coordinated per-CPU schedulers.

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";
.a 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".
Most systems use what we might dub priority-based round-robin scheduling to some extent. The general principles are:
a thread of higher priority (which is a function of base and local priorities) will preempt a thread of lower priority;
otherwise, threads of equal priority will essentially take turns at getting an allocated slice or quantum of CPU;
there are a few extra "tweaks" to make things work.

States

Depending on the system, there are various states that a thread can be in. Probably the two most interesting are:
runnable, which essentially means "ready to consume CPU"; being runnable is generally the minimum requirement for a thread to actually be scheduled on to a CPU;
waiting, meaning that the thread currently cannot continue as it is waiting for a resource such as a lock or I/O, for memory to be paged in, for a signal from another thread, or simply for a period of time to elapse (sleep).
Other states include terminated, which means the thread's code has finished running but not all of the thread's resources have been cleared up, and a new state, in which the thread has been created, but not all resources necessary for it to be runnable have been created. Internally, the OS may distinguish between various different types of wait states2 (for example "waiting for a signal" vs "waiting for the stack to be paged in"), but this level of granularity is generally not available or so important to Java programs. (On the other hand, Java generally exposes to the programmer things the JVM can reasonly know about, for example, if a thread is waiting to acquire the lock on a Java object— roughly speaking, "entering a synchronized

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
Round-Robin (RR)
-FCFS with Preemption
-Time quantum (or time slice)
-Ready Queue treated as circular queue
Shortest Remaining Time (SRT)
-Preemptive version of shortest process next policy
-Must estimate processing time