Process Scheduling:

Basics & Criteria

• The objective of multiprogramming is to have some process running at all times, to
maximize CPU utilization.
• Try to use the time productively.
• Several processes are kept in memory at one time
• Every time one process has to wait, another process can take over use of the CPU.
1. CPU- I/O Burst Cycle
• The success of CPU scheduling depends on an observed
property of processes:
• Process execution consists of a cycle of CPU execution
and I/O wait. Processes alternate between these two
states.
• Process execution begins with a CPU burst. That is
followed by an I/O burst, which is followed by another
CPU burst, then another I/O burst, and so on.
• Eventually, the final CPU burst ends with a system request to
terminate execution
• The durations of CPU bursts have been measured extensively. They tend to have a
frequency curve similar to that shown in the figure.

• The curve is generally characterized as exponential or hyper-exponential, with a large

number of short CPU bursts and a small number of long CPU bursts.
• An I/O-bound program typically has many short CPU bursts.
• A CPU-bound program might have a few long CPU bursts.
• This distribution can be important in the selection of an appropriate CPU-scheduling
algorithm.
 Bursts of CPU usage alternate with periods of waiting for I/O.
(a) A CPU-bound process. (b) An I/O-bound process.

• Having some CPU-bound processes and some I/O-bound processes in memory

together is a better idea than first loading and running all the CPU-bound jobs and
then when they are finished loading and running all the I/O-bound jobs (a careful mix
of processes).
2. CPU Scheduler
• Whenever the CPU becomes idle, the operating system must select one of
the processes in the ready queue to be executed.
• The selection process is carried out by the short-term scheduler, or CPU
scheduler.
• The scheduler selects a process from the processes in memory that are
ready to execute and allocates the CPU to that process
3. Preemptive Scheduling
• CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
• When scheduling takes place only under circumstances 1 and 4, the scheduling scheme
is non-preemptive or cooperative.
• Non-preemptive scheduling: once the CPU has been allocated to a process, the process
keeps the CPU until it releases the CPU either by terminating or by switching to the
waiting state.
• All other scheduling is preemptive
• Consider access to shared data
• Consider preemption while in kernel mode
• Consider interrupts occurring during crucial OS activities
4. Dispatcher
• The dispatcher is the module that gives control of the CPU to the process
selected by the short-term scheduler.
• This function involves the following:
• Switching context
• Switching to user mode
• Jumping to the proper location in the user program to restart that
program
• The dispatcher should be as fast as possible, since it is invoked during
every process switch.
• The time it takes for the dispatcher to stop one process and start another
running is known as the dispatch latency.
Scheduling Criteria
1. CPU utilization:
• keep the CPU as busy as possible.
• Conceptually, CPU utilization can range from 0 to 100 percent.
• In a real system, it should range from 40 percent (for a lightly loaded system) to 90
percent (for a heavily loaded system).
2. Throughput:
• The number of processes that are completed per time unit, called throughput.
• For long processes, this rate may be one process per hour; for short transactions, it
may be ten processes per second.
3. Turnaround time:
• How long it takes to execute a particular process
• The interval from the time of submission of a process to the time of completion is the
turnaround time.
• Turnaround time is the sum of the periods spent
• waiting to get into memory
• waiting in the ready queue
• executing on the CPU, and
• doing I/O.
4. Waiting time:
• It affects only the amount of time that a process spends waiting in the ready queue.
• Waiting time is the sum of the periods spent waiting in the ready queue
5. Response time:
• time from the submission of a request until the first response is produced.
• This measure, called response time, is the time it takes to start responding, not the
time it takes to output the response.
• Scheduling Algorithm Optimization Criteria
• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time
Questions

What is a process scheduler? State the characteristics of a good process scheduler?

OR
What is scheduling? What criteria affect the scheduler's performance?