16-03-2011, 03:49 PM
Presented By:-
Rajkiran swain
[attachment=10330]
CPU SCHEDULING
Introduction
Multiprogramming A number of programs can be in memory at the same time. Allows overlap of CPU and I/O.
Jobs (batch) are programs that run without user interaction.
User (time shared) are programs that may have user interaction.
Process is the common name for both.
CPU - I/O burst cycle Characterizes process execution, which alternates, between CPU and I/O activity. CPU times are generally much shorter than I/O times.
Preemptive Scheduling An interrupt causes currently running process to give up the CPU and be replaced by another process.
Process state
A process is a program at the time of execution.
Process is the more than program code
It includes the program counter.
The process stack
The counter of process register
Schedulers
Scheduler: a module in OS to execute scheduling decisions.
Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue.
Medium term schedulers-if the process request an i/o in the middle of the execution,then the process removed from main memory and loaded into waiting queue.
Short-term (or CPU scheduler) – selects which process should be executed next and allocates CPU
Scheduling methodology
So many CPU scheduling algorithms available.
Different CPU scheduling algorithms have different properties.
In choosing which algorithm to use in a particular situation.we must consider the properties of various algorithms.
Through put-how many jobs are completed by the CPU with in time period.
Turn around time-the time interval between the submission of process and time of completion is the turn around time.
Waiting time-it is the sum of the periods spent waiting by a process in the ready queue.
CPU scheduling algorithms
CPU scheduling algorithms decides which of processes in the ready queue is to be allocated the CPU.
There are many different CPU scheduling algorithms.
1-first come first served scheduling
FCFS) 2-shorest job first scheduling
SJF) 3-shortest remaining time first(SRTF)
4-round robin scheduling algorithm
RR)SRTF - Shortest Remaining Time First
Preemptive version of SJF
Ready queue ordered on length of time till completion (shortest first)
Arriving jobs inserted at proper position
Dispatcher selects shortest job and runs to completion or until a job with a shorter remaining time arrives in the system.
Performance Evaluation
• Deterministic Modeling (vs. Probabilistic) Look at behavior of algorithm on a particular workload, and compute various performance criteria
Example:
workload - Job 1: 24 units
Job 2: 3 units
Job 3: 3 units
• Gantt chart for FCFS:
| Job 1 | Job 2 | Job 3 |
0 24 27 30
Total waiting time: 0 + 24 + 27 = 51
Average waiting time: 51/3 = 17
Total turnaround time: 24 + 27 + 30 = 81
Average turnaround time: 81/3 = 9
