RESOURCE ALLOCATION GRAPH

RESOURCE ALLOCATION GRAPH (RAG'S) are directed labeled graphs used to represent, from the point of view if DEADLOCKS, the current state of a system.

RESOURCE ALLOCATION GRAPHS:

PROCESS

REQUEST TYPE w/ 4 INSTANCE

Pi REQUEST INSTANCE of Rj

Rj

Pi is HOLDING AN INSTANCE OF Rj

Rj

EXAMPLE of RESOURCE ALLOCATION GRAPH

RESOURCE ALLOCATION GRAPH w/ DEADLOCK

If graph contains a cycle then it has a DEADLOCK

-if only one instance per resource type,then DEADLOCK

-if several instances per resource type, possibly of DEADLOCK

RESOURCE ALLOCATION GRAPH w/ a CYCLE BUT NO DEADLOCK

If graph contains no cycle no DEADLOCK

DEADLOCK CHARACTERIZATION

• Mutual exclusion: only one process at a time can use a resource.
• Hold and wait: a process holding at least one resource is waiting to acquire additional resources held by other processes.
• No preemption: a resource can be released only voluntarily by the process holding it, after that process has completed its task.
• Circular wait: there exists a set {P0, P1, …, P0} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by
  P2, …, Pn–1 is waiting for a resource that is held by Pn, and P0 is waiting for a resource that is held by P0.

METHODS FOR HANDLING DEADLOCKS

• Ensure that the system will never enter a deadlock state.
• Allow the system to enter a deadlock state and then recover.
• Ignore the problem and pretend that deadlocks never occur in the system; used by most operating systems, including UNIX.

DEADLOCK PREVENTION

• deadlock requires the following conditions:

-mutual exclusion:

-resources not sharable

-hold and wait:

-process must be holding one resource while requesting another

-circular wait:

-at least 2 processes must be blocked on each other

• eliminate mutual exclusion:

-not possible in most cases
-spooling makes I/O devices sharable

• eliminate hold-and-wait

-request all resources at once
-release all resources before a new request
-release all resources if current request blocks

• eliminate circular wait

-order all resources: SEQ(Ri) ? SEQ(Rj)
-process must request in ascending order

DEADLOCK DETECTION

• graph reduction

-repeat:

-select unblocked process p
-remove p and all request and allocation edges

• deadlock? graph not completely reducible
• all reduction sequences lead to the same result

DEADLOCK RECOVERY

• process termination

-kill all processes involved in deadlock
-kill one at a time; in what order:

-by priority: consistent with scheduling
-by cost of restart: length of recomputation
-by impact on other processes: CS, producer/cons.

• resource preemption

-direct: temporarily remove resource (e.g. memory)
-indirect: rollback to earlier checkpoint

MULTIPROCESSOR SCHEDULER

• Will consider only shared memory multiprocessor .
• Salient features:

One or more caches: cache affinity is important
Semaphores/locks typically implemented as spin-locks: preemption

during critical sections

REAL TIME SCHEDULING

Correctness of the system may depend not only on the logical result of the computation but also
on the time when these results are produced.

Example:

• Tasks attempt to control events or to react to events
  that take place in the outside world
• These external events occur in real time and
  processing must be able to keep up
• Processing must happen in a timely fashion,
  • neither too late, nor too early

SUBSTANTIAL INFORMATION OF THREE OPERATING SYSTEM

WINDOWS XP THREAD

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)

LINUX

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 a9process)
  
• Clone() allow various levels of sharing between nothing.

Linux PCB contains pointers to other DS where the process data (open files, page tables…) is stored

• Fork – a new process is created along with a copy of all the associated data structure of the parent process
• Clone – a new process that points to the data structures of the parent process is created

WINDOWS SERVER 2008

Windows Server codename "Longhorn" operating systems.

Kernel improvements are significant because the kernel provides

• low-level operating system functions,
• including thread scheduling,
• interrupt and exception dispatching,
• multiprocessor synchronization, and
• a set of routines and basic objects that the rest of the operating system uses to implement higher-level constructs.

SCHEDULING ALGORITHMS

• First-come, first-served (FCFS) scheduling
• Shortest-job first (SJF) scheduling
• Priority scheduling
• Round-robin scheduling
• Multilevel queue scheduling
• Multilevel feedback queue scheduling

First-come, First-served (FCFS) scheduling is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes.

Shortest-job-first (SJF) scheduling is provably optimal, providing the shortest average waiting time. Implementing SJF scheduling is difficult because predicting the length of the next CPU burst is difficult. The SJF algorithm is a special case of the general

priority-scheduling algorithm, which simply allocates the CPU to the highest-priority process. Both priority and SJF scheduling may suffer from starvation. Aging is a technique to prevent starvation.

Round-robin (RR) scheduling is more appropriate for a time-shared (interactive) system. RR scheduling allocates the CPU to the first process in the ready queue for q time units, where q is the time quantum. After q time units, if the process has not relinquished the CPU, it is preempted and the process is put at the tail of the ready queue. The major problem is the selection of the time quantum. If the quantum is too large, RR scheduling degenerates to FCFS scheduling; if the quantum is too small, scheduling overhead in the form of context-switch time becomes excessive.The FCFS algorithm is nonpreemptive, the RR algorithm is preemptive. The SJF and priority algorithms may be either preemptive or nonpreemptive.

Multilevel queue algorithms allow different algorithms to be used for various classes of processes. The most common is a foreground interactive queue which uses RR scheduling, and a background batch queue, which uses FCFS scheduling

Multilevel feedback queues allow processes to move from one queue to another.Because such a wide variety of scheduling algorithms are available, we need methods to select among them. Analytic methods use mathematical analysis to determine the performance of an algorithm. Simulation methods determine performance by imitating the scheduling algorithm on a “representative” sample of processes, and computing the resulting performance.