In this term paper I have discussed about cpu scheduling techniques. Also i have discussed about different cpu scheduling algorithms of Linux, and of Unix. And have done comparisons between Linux and UNIX cpu scheduling methods.
1. INTRODUCTION TO CPU SCHEDULING
CPU scheduling is the basis of multiprogrammed operating systems. By switching the CPU among processes, the operating system can make the computer more productive.
Multiprogramming : A number of programs can be in memory at the same time. Allows overlap of CPU and I/O.Jobs : programs that run without user interaction. User :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.
1.1 The Scheduler
It Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them,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
* Scheduling under 1 and 4 is nonpreemptive
* All other scheduling is preemptive
1.2 The Dispatcher
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:
switching to user mode
jumping to the proper location in the user program to restart that program
Dispatch latency – time it takes for the dispatcher to stop one process and start another running
2. Scheduling Algorithms
2.1 FIRST-COME, FIRST SERVED:
( FCFS) same as FIFO
Simple, fair, but poor performance. Average queueing time may be long.
What are the average queueing and residence times for this scenario?
How do average queueing and residence times depend on ordering of these processes in the queue?
2.2 SHORTEST JOB FIRST:
Optimal for minimizing queueing time, but impossible to implement. Tries to predict the process to schedule based on previous history.
Predicting the time the process will use on its next schedule:
t( n+1 ) = w * t( n ) + ( 1 – w ) * T( n )
2.3 PREEMPTIVE ALGORITHMS:
Yank the CPU away from the currently executing process when a higher priority process is ready.
Can be applied to both Shortest Job First or to Priority scheduling.
On time sharing machines, this type of scheme is required because the CPU must be protected from a run-away low priority process.
Give short jobs a higher priority – perceived response time is thus better.
What are average queueing and residence times? Compare with FCFS.
3.CPU SCHEDULING IN LINUX
Linux pre 2.5
Multilevel Feedback Queue
Linux post 2.6.23
Completely Fair Scheduler
Linux 2.6 O(1) Scheduler
Reducing scheduling algorithm complexity to O(1) from O(n).
Better support for SMP system.
Single runqueue lock
Preemptive: A higher priority process can preempt a running process with lower priority
140 priority levels
The lower the value, higher is the priority
Eg : Priority level 110 will have a higher priority than 130.
Two priority-ordered ‘priority-arrays’ per CPU
‘Active’ array : tasks which have timeslices left
‘Expired’ Array : tasks which have run
Both accessed through pointers from per-CPU runqueue
They are switched via a simple pointer swap
3.1 The Linux 2.6 scheduler runqueue structure
3.2 Scheduling policy
140 Priority levels
1-100 : RT prio ( MAX_RT_PRIO = 100 )
101-140 : User task Prio ( MAX_PRIO = 140 )
Three different scheduling policies
One for normal tasks
Two for Real time tasks
Each task assigned a “Nice” value
PRIO = MAX_RT_PRIO + NICE + 20
Assigned a time slice
Tasks at the same prio are round-robined.
Ensures Priority + Fairness
Priority and interactivity effect on timeslice
Recalculation of priorities
When a task finishes it’s timeslice :
It’s interactivity is estimated
Interactive tasks can be inserted into the ‘Active’ array again.
Else, priority is recalculated
Inserted into the NEW priority level in the ‘Expired’ array.
3.3 Scheduling in Linux
The scheduler selects the next process to be assigned to the CPU based on process priority.
In a high-level C program the “nice” value can be modified using the following functions:
int getpriority(int which, id_t who);
int setpriority(int which, id_t who, int value);
int nice(int incr);
3.4 Linux 2.6 CFS Scheduler
Was merged into the 2.6.23 release.
Uses red-black tree structure instead of multilevel queues.
Tries to run the task with the “gravest need” for CPU time
4. UNIX CPU SCHEDULING
4.1 Process Scheduling in Unix
ô€€ Based on multi-level feedback queues
ô€€ Priorities range from -64 to 63 (lower number means higher
ô€€ Negative numbers reserved for processes waiting in kernel mode
o (that is, just woken up by interrupt handlers)
o (why do they have a higher priority?)
ô€€ Time quantum = 1/10 sec (empirically found to be the longest
quantum that could be used without loss of the desired response
for interactive jobs such as editors)
o short time quantum means better interactive response
o long time quantum means higher overall system throughput since
less context switch overhead and less processor cache flush.
ô€€ Priority dynamically adjusted to reflect
o resource requirement (e.g., blocked awaiting an event)
o resource consumption (e.g., CPU time)
4.2 Unix CPU Scheduler
ô€€ values in the PCB
o p_cpu: an estimate of the recent CPU use
o p_nice: a user/OS settable weighting factor (-20..20) for flexibility;
default = 0; negative increases priority; positive decreases priority
ô€€ process’ priority calculated periodically
priority = base + p_cpu + p_nice
and the process is moved to appropriate ready queue
ô€€ CPU utilization, p_cpu, is incremented each time the system clock
ticks and the process is found to be executing.
ô€€ cpu is adjusted once every second (time decay)
Possible adjustment: divide by 2 (that is, right)
o Motivation: Recent usage penalizes more than past usage
o Precise details differ in different versions (e.g. 4.3 BSD uses current
load (number of ready processes) also in the adjustment formula)
4.3 Scheduling in the 4.2BSD Unix OS
Short term scheduling in UNIX is designed to benefit interactive jobs. Processes are given small CPU time slices by an algorithm that reduces to round robin for CPU-bound jobs, although there is a priority scheme. There’s no preemption of one process by another when running in kernel mode Every process has a scheduling priority associated with it; the lower the numerical priority, the more likely is the process to run. System processes doing disk I/O and other important tasks have negative priorities and cannot be interrupted. Ordinary user processes have positive priorities and thus are less likely to be run than any system process, the lower (more positive) its priority becomes. The reverse is also true (process aging is employed to prevent starvation). Thus there is negative feedback in CPU scheduling, and its difficult for a single process to take CPU all time.
ô€€ Suppose p_nice is 0, clock ticks every 10msec, time quantum is 100msec, and
p_cpu adjustment every sec
ô€€ Suppose initial base value is 4. Initially, p_cpu is 0
ô€€ Initial priority is 4.
ô€€ Suppose scheduler selects this process at some point, and it uses all of its
quantum without blocking. Then, p_cpu will be 10, priority recalculated to 10, as
new base is 0.
ô€€ At the end of a second, p_cpu, as well as priority, becomes 5 (more likely to
ô€€ Suppose again scheduler picks this process, and it blocks (say, for disk read)
after 30 msec. p_cpu is 8
ô€€ Process is now in waiting queue for disk transfer
ô€€ At the end of next second, p_cpu is updated to 4
– New priority = 50 + estimatedUtilization/4
â€¢ Lower priority is better!
– Running process: New estimatedUtilization =
â€¢ Accounts for (hopes) process closer to terminating!
– Sleeping process: new estimatedUtilization =
â€¢ This decays much faster (exponentially)
â€¢ This means CPU bound jobs are pushed to
lower priority queues, in general.
â€¢ 128 priority ranges 0-49 are kernel mode, 50-127 are user mode,32 run queues
– Divide priority by 4 ,Each process:
– Has an entry in its process descriptor for its CPU utilization as well as its priority
â€¢ CPU utilization incremented every tick process is
4.5 Summary of Unix Scheduler
ô€€ Commonly used implementation with multiple priority
ô€€ Priority computed using 3 factors
o PUSER used as a base (changed dynamically)
o CPU utilization (time decayed)
o Value specified at process creation (nice)
ô€€ Processes with short CPU bursts are favored
ô€€ Processes just woken up from blocked states are
favored even more
ô€€ Weighted averaging of CPU utilization
ô€€ Details vary in different versions of Unix
â€¢ Use multilevel queuing
– Desire: good response time for interactive jobs
w/o starving compute-bound jobs
– Uses pre-emption
– Adjusts priority dynamically by moving jobs
Cite This Work
To export a reference to this article please select a referencing stye below:
Related ServicesView all
DMCA / Removal Request
If you are the original writer of this essay and no longer wish to have your work published on UKEssays.com then please: