kinds of resource-allocation graph

example of resource allocation graph

resource allocation graph with a deadlock

resource-allocation graph with a cycle but no deadlock

resource-allocation graph for deadlock avoidance

unsafe state in resource-allocation graph

Example of Resource-Allocation Graph

RESOURCE-ALLOCATION GRAPH

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

• V is partinioned 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
  
  

- You will know if theres a deadlock base on allocation graph if the graph contains a cycle and if only one instance per resource type, and if several instances per resource type theres a posibility of deadlock.

Substantial Information About Threads in Different Operating System

n

Windows X.P Threads

· Implements the one-to-one mapping, kernel-level

· 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 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 Scheuling Algorithms

1. First-Come, First-Served (FCFS) Scheduling

• Ready queue is a FIFO queue

• Example Process Burst Time

P1 24

P2 3

P3 3

• Arrival order: P1 , P2 , P3

– The Gantt Chart for the schedule is:

– Waiting time for P1 = 0; P2 = 24; P3 = 27

• Average waiting time: (0 + 24 + 27)/3 = 17

• Arrival Order: P2 , P3 , P1 .

– The Gantt chart for the schedule is:

– Waiting time for P1 = 6; P2 = 0; P3 = 3

• Average waiting time: (6 + 0 + 3)/3 = 3

• Much better than previous case.

• Convoy effect: I/O-bound (short CPU-bursts) wait for CPU-bound (long CPU-bursts)

• Non-preemptive

2. Shortest Job First (SJF) Scheduling

• Each process knows the length of its next CPU burst

– Use these lengths to schedule the process with the shortest time.

• Two schemes:

– Non-preemptive – once CPU given to the process it cannot be preempted until completes its CPU burst.

– Preemptive – if a new process arrives with CPU burst length less than remaining time of current executing process, preempt.

• Shortest-Remaining-Time-First (SRTF).

• SJF is optimal – gives minimum average

waiting time for a given set of processes.

Example of Non-Preemptive SJF

Example of Preemptive SJF

3. Round Robin (RR)

• Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.

• If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.

• Performance

– q large Þ FIFO

- q small Þ q must be large

Example: RR with Time Quantum = 20

4. Multilevel Queue Scheduling

• Ready queue is partitioned into separate queues

– According to process properties and scheduling needs

– Foreground (interactive) and background (batch)

• Processes are permanently assigned to one queue

• Each queue has its own scheduling algorithm,
foreground – RR, background – FCFS

• Scheduling must be done between the queues.

– Fixed priority scheduling; i.e., serve all from higher-priority then from lower-priority. Possibility of starvation.

– Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; eg., 80% to foreground in RR 20% to background in FCFS

5. Multiple-Processor Scheduling

• Homogeneous processors within a multiprocessor

– Separate vs. common ready queue

– Load sharing

• Symmetric Multiprocessing (SMP) – each processor makes its own scheduling decisions

– Access and update a common data structure

– Must ensure two processors do not choose the same process

• Asymmetric multiprocessing – only the master process accesses the system data structures

6. Real-Time Scheduling

• Hard real-time systems – required to complete a critical task within a guaranteed amount of time

– A process is submitted with a statement of the amount of time in which it needs to complete or perform I/O. The scheduler uses the statement to admit (and guarantee) or reject the process

– Resource reservation – requires the scheduler knows exactly how long each type of OS functions takes to perform

– Hard real-time systems are composed of special-purpose SW running on HW dedicated to their critical process, and lack the full functionality of modern computers and OS

• Soft real-time computing – requires that critical processes receive priority over less fortunate ones.

– Ex. Multimedia, high-speed interactive graphics…

• Related scheduling issues for soft real-time computing

– Priority scheduling – real-time processes have the highest priority

• The priority of real-time process must not degrade over time

– Small dispatch latency

• May be long because many OS wait either for a system call to complete or for an I/O block to take place before a context switch

• Preemption point

• Make the entire kernel preemptible (ex. Solaris 2)