Scribd
Upload
5 views

chap9

The document discusses uniprocessor scheduling, outlining the goals of scheduling such as quick response time and processor efficiency. It details various types of scheduling including long-term, medium-term, and short-term, along with their respective criteria and decision modes. Additionally, it covers different scheduling algorithms like First-Come-First-Served, Round-Robin, and Shortest Process Next, highlighting their advantages and disadvantages.

Uploaded by

matchbox668
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views

chap9

The document discusses uniprocessor scheduling, outlining the goals of scheduling such as quick response time and processor efficiency. It details various types of scheduling including long-term, medium-term, and short-term, along with their respective criteria and decision modes. Additionally, it covers different scheduling algorithms like First-Come-First-Served, Round-Robin, and Shortest Process Next, highlighting their advantages and disadvantages.

Uploaded by

matchbox668
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 24

Uniprocessor Scheduling

Chapter 9
Goals of Scheduling

Quick response time


Fast throughput
Processor efficiency
Type of Scheduling

 Long-term
 performed when new process is created
 Medium-term
 swapping
 Short-term
 decision as to which ready process will be executed
by the processor
 I/O
 decision as to which process’s pending I/O request
shall be handled by available I/O device
Scheduling and Process
State Transition

New

Long-term Long-term
scheduling scheduling

Ready,
Ready Running Exit
suspend
Medium-term Short-term
scheduling
scheduling

Blocked,
Blocked
suspend
Medium-term
scheduling
Queuing Diagram for
Scheduling
Long-term Time-out
scheduling
Batch Short-term
Ready Queue Release
jobs scheduling
Processor

Medium-term
scheduling
Interactive Ready, Suspend Queue
users

Medium-term
scheduling
Blocked, Suspend Queue

Blocked Queue
Event Wait
Event
Occurs
Long-Term Scheduling

Determines which programs are admitted


to the system for processing
Controls the degree of multiprogramming
More processes, smaller percentage of
time each process is executed
Medium-Term Scheduling

Swapping
Based on the need to manage
multiprogramming (it is hard to foresee
the CPU and memory requirements of
processes in the long-term scheduling
phase).
Short-Term Scheduling

Performed by the dispatcher


Invoked when an event occurs, e.g.
 clock interrupt
 I/O interrupt
 operating system call
 signal (e.g., when software events occur)
Short-Tem Scheduling
Criteria

 User-oriented
 Response Time
o Elapsed time between the submission of a request until
there is output.
 System-oriented
 effective and efficient utilization of the processor
 Performance-related
 response time and throughput
 Not performance related
 predictability (e.g., fairness, no starvation)
Priorities

Scheduler will always choose a process of


higher priority over one of lower priority
Have multiple ready queues to represent
each level of priority
Lower-priority may suffer starvation
 allow a process to change its priority based
on its age or execution history
Priority Queuing
RQ0 Release
Dispatch
Processor

RQ1

.
Admit .
.
RQn

Preemption

Event Wait
Event
occurs Blocked Queue
Decision Mode

 Nonpreemptive
 Once a process is in the running state, it will
continue until it terminates or blocks itself for
I/O
 Preemptive
 Currently running process may be interrupted
and moved to the Ready state by the
operating system
 Allows for better service since no process can
monopolize the processor for very long
An Example

Arrival Service
Process Time Time

1 0 3

2 2 6

3 4 4

4 6 5

5 8 2
First-Come-First-Served
(FCFS)
0 5 10 15 20

1
2
3
4
5

Each process joins the Ready queue


When the current process ceases to
execute, the oldest process in the Ready
queue is selected
First-Come-First-Served
(FCFS)

A short process may have to wait a very


long time before it can execute
Favors CPU-bound processes
 I/O processes have to wait until CPU-bound
process completes
Round-Robin
0 5 10 15 20

1
2
3
4
5

Uses preemption based on a clock


An amount of time is determined that
allows each process to use the
processor for that length of time
Shortest Process Next
0 5 10 15 20

1
2
3
4
5
Nonpreemptive policy
Process with shortest expected
processing time is selected next
Short process jumps ahead of longer
processes
Shortest Process Next

Predictability of longer processes is


reduced
If estimated time for process not correct,
the operating system may abort it
Possibility of starvation for longer
processes
Shortest Remaining Time
0 5 10 15 20

1
2
3
4
5

Preemptive version of shortest process


next policy
Must be able to estimate remaining
processing time
Highest Response Ratio
Next (HRRN)
0 5 10 15 20

1
2
3
4
5

 Choose next process with the highest ratio of:


time spent waiting + expected service time
expected service time
Feedback
0 5 10 15 20

1
2
3
4
5
 Penalize jobs that have been running longer
 Can be used when we don’t know the remaining
time a process needs to execute
 Implemented in UNIX (see later)
Fair-Share Scheduling

User’s application runs as a collection of


processes (threads)
User is concerned about the performance
of the application
Need to make scheduling decisions based
on groups of processes
For each process, there must be an a
priori upper limit on the waiting time
UNIX Scheduling
 Priorities are recomputed once per second
 Base priority divides all threads into fixed bands
of priority levels
 Adjustment factor used to keep process in its
assigned band
P(i) = Base + CPU(i)/2 + nice
 i – i-th interval
 CPU(i) – CPU utilization by the thread thus far
 nice – user controllable factor (rare)
 P – priority: lower values mean higher priority
Feedback

Process is demoted to the next lower-


priority queue each time it returns to the
ready queue
Longer processes drift downward
To avoid starvation, CPU time slices for
lower-priority processes are longer

You might also like