Transcript Computer Basics

INTRO TO PROCESS
SCHEDULING
Module 2.4
COP4600 – Operating Systems
Richard Newman
NEED FOR PROCESS SCHEDULING
Recall process behavior...
Figure 2-39. Bursts of CPU usage alternate with periods of waiting for I/O. (a) A
CPU-bound process. (b) An I/O-bound process.
For good resource utilization, want to overlap I/O of on process with CPU burst
of another process
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
MULTIPROGRAMMING
For good resource utilization, want to overlap I/O of on process with CPU burst
of another process
QUICK AND DIRTY MODEL
Assume jobs independent
• Probability of p a process is doing I/O
• Degree of multiprogramming is n (# processes)
• Probability of pn all n processes are doing I/O
• Probability that CPU is idle is pn
• CPU utilization is 1 - pn
MODELING MULTIPROGRAMMING
Figure 2-6. CPU utilization as a function of the number of
processes in memory.
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
QUICK AND DIRTY MODEL
Are we overestimating or underestimating CPU utilization?
THREE LEVEL SCHEDULING
Who gets
Short-term
CPU
next?
Do we have
room for
another?
Processes
in RAM
contending
for CPU
Long-term
Is RAM
Medium-term
over-subscribed?
Figure 2-25. Three-level scheduling.
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
THREE TYPES OF SCHEDULER
Long-term (admission) scheduler:
• Has list of jobs waiting to be scheduled
• Decides whether to run a job on system
Medium-term (memory) scheduler:
• Has set of currently running jobs and set of jobs
that have been swapped out of memory
• Decides whether to swap a job in or out
Short-term (CPU) scheduler:
• Has set of currently ready/running processes
• Decides which ready process to run next
THREE LEVEL SCHEDULING
Main goal for long-term (admission) scheduler:
• Get good mix of jobs in RAM
Main goal for medium-term (memory) scheduler:
• Prevent thrashing (more on this later)
Main goals for short-term (CPU) scheduler:
• Be efficient and fair
All share goals of:
Maximizing resource utilization
Giving best service to clients
Enforcing system policies
ADMISSION SCHEDULER
Goal:
• Get good mix of jobs in RAM
• Need to predict job needs and behavior
• User-supplied (in job control information)
• Learned (same job run many times)
Constraints:
• Memory – is there room to run the job?
• CPU cycles – what is CPU utilization?
• Other resources – does job need devices?
More on these in memory management…
MEMORY SCHEDULER
Goal:
• Prevent thrashing (memory oversubscribed)
• Deals with demand paging/segmentation
systems
• Detects problem by I/O vs. CPU utilization
Constraints:
• Memory allocations to processes
More on these in memory management…
CPU SCHEDULER
Goals:
• Depend on type of system
Information
• Externally provided info (e.g., priority)
• History of process kept by system
Constraints:
• Any ready process may be selected
• But CPU scheduler runs often, so must be fast!
WHEN TO SCHEDULE CPU
CPU scheduling is absolutely required:
1. When a process exits.
2. When a process blocks on I/O, or a semaphore.
i.e. - when the running process can no longer run!
CPU scheduling usually done (though not absolutely required):
1. When a new process is created.
2. When an I/O interrupt occurs.
3. When a clock interrupt occurs.
i.e., when another process has higher priority
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
CATEGORIES OF SCHEDULING
ALGORITHMS
By job type, hence goals
1. Batch
2. Interactive
3. Real time
By when run
1. Non-Preemptive
2. Preemptive
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
SCHEDULING ALGORITHM GOALS
Figure 2-40. Some goals of the scheduling algorithm under
different circumstances.
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
SCHEDULING DECISION CRITERIA
Criteria for deciding which process to choose:
• How long has it been since the process was
swapped in or out?
• How much CPU time has the process had
recently?
• How big is the process? (Small ones do not get in
the way.)
• How important is the process?
Tanenbaum & Bos, Modern Operating Systems:4th ed., (c) 2013 Prentice-Hall, Inc. All rights reserved.
SCHEDULING ALGORITHM MEASURES
Turn-around time = Finish time – arrival time
includes time spent waiting for CPU
Mean Turn-around Time (MTT)
Average TT over all jobs
Fairness – various measures, including maximum
difference in fraction of time each job got CPU over
some period
Makespan = Finish time of last job – start time for set
of jobs
Used for multiprocessor scheduling
Realtime deadlines met – (prob) for RTS systems
TURN-AROUND TIME
CPU time
A
A takes 9 units of time if run by itself
B
B takes 4 units of time if run by itself
Arrival time
C
C takes 3 units of time if run by itself
A arrives at time 0
A
B arrives at time 1
B
C arrives at time 2
C
Schedule
A arrives at time 0
A gets CPU
A
A finishes at time 9
Now B or C can run
A running
B waiting
B
C waiting
C
C arrives at time 2
C must wait
B arrives at time 1
B must wait
B running
C runs
C finishes at time 12
Now B can run
B finishes at time 16
All done!
MTT= (9+15+10)/3= 34/3
TT(A) =
9–0= 9
TT(B) = 16 – 1 = 15
TT(C) = 12 – 2 = 10
SCHEDULING ALGORITHMS
Non-preemptive algorithms:
Running job must give up CPU/system voluntarily
(system retains right/ability to terminate)
First-Come First-Serve (FCFS):
• Jobs run in order of arrival
Shortest Job First (SJF):
• Ready job that will finish first is run first
Priority
• Ready job with highest priority is run first
Optimal (Crystal Ball)
• Uses future knowledge of arrivals to optimize
SCHEDULING ALGORITHMS
Preemptive algorithms:
Running job may be forced to give up
CPU/system involuntarily
Round Robin (RR):
• Jobs run in order of arrival, with maximum
quantum (go to end of queue if preempted)
Shortest Remaining Time First (SRTF):
• Ready job that will finish first is run first
Preemptive Priority:
• Ready job with highest priority is run first
CTSS:
• Attempts to approximate SRTF
SUMMARY
•
Need for scheduling
• Keep resources utilized, meet timing goals, etc.
• Three-level scheduling
• Long-term admission scheduler
• Medium-term memory scheduler
• Short-term CPU scheduler
• Scheduling algorithm types & goals
• By job type: batch, interactive, real-time
• By when run: preemptive, non-preemptive
• Schedule metrics