Introduction To CPU Scheduling Information Technology Essay

ABSTRACT

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

4. Terminates

* 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 context

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 version

Scheduler

Linux pre 2.5

Multilevel Feedback Queue

Linux 2.5-2.6.23

O(1) scheduler

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

Cache problem

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

Normal 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

UNIX SCHEDULAR

4.1 Process Scheduling in Unix

􀀁 Based on multi-level feedback queues

􀀁 Priorities range from -64 to 63 (lower number means higher

priority)

􀀁 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.

4.4.Example

􀀁 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

scheduled)

􀀁 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

•4.6 Formulas:

– New priority = 50 + estimatedUtilization/4

• Lower priority is better!

– Running process: New estimatedUtilization =

DecayRunnable(estimatedUtilization)

• Accounts for (hopes) process closer to terminating!

– Sleeping process: new estimatedUtilization =

DecaySleep(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

Running

4.5 Summary of Unix Scheduler

􀀁 Commonly used implementation with multiple priority

queues

􀀁 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

between queues

REFERENCES:

oreilly.com/catalog/linuxkernel/chapter/ch10.html

www.ibm.com/developerworks/linux/library/l-scheduler/

people.cis.ksu.edu/~gud/docs/ppt/scheduler.pdf

www.cis.upenn.edu/~lee/07cis505/Lec/os-schedule-v2.pdf

www.thehackademy.net/madchat/ebooks/sched/cpusched.pdf

www.articles.assyriancafe.com/documents/CPU_Scheduling.pdf