PDF Linux Scheduler - Columbia University

[Pages:40]Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

Linux Scheduler

1 / 40

Descending to Reality. . .

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s The Linux scheduler tries to be very efficient s To do that, it uses some complex data

structures s Some of what it does actually contradicts the

schemes we've been discussing. . .

2 / 40

Philosophies

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s Use large quanta for important processes s Modify quanta based on CPU use s Bind processes to CPUs s Do everything in O(1) time

3 / 40

Processor Scheduling

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s Have a separate run queue for each processor s Each processor only selects processes from its

own queue to run s Yes, it's possible for one processor to be idle

while others have jobs waiting in their run queues s Periodically, the queues are rebalanced: if one processor's run queue is too long, some processes are moved from it to another processor's queue

4 / 40

Processor Affinity

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s Each process has a bitmask saying what CPUs it can run on

s Normally, of course, all CPUs are listed s Processes can change the mask s The mask is inherited by child processes (and

threads), thus tending to keep them on the same CPU s Rebalancing does not override affinity

5 / 40

Basic Scheduling Algorithm

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s Find the highest-priority queue with a runnable process

s Find the first process on that queue s Calculate its quantum size s Let it run s When its time is up, put it on the expired list s Repeat

6 / 40

The Run Queue

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s 140 separate queues, one for each priority level s Actually, that number can be changed at a

given site s Actually, two sets, active and expired s Priorities 0-99 for real-time processes s Priorities 100-139 for normal processes; value

set via nice() system call

7 / 40

The Highest Priority Process

Linux Scheduler Descending to Reality. . .

Philosophies Processor Scheduling

Processor Affinity Basic Scheduling Algorithm

The Run Queue The Highest Priority Process Calculating Timeslices

Typical Quanta

Dynamic Priority

Interactive Processes

Using Quanta Avoiding Indefinite Overtaking

The Priority Arrays

Swapping Arrays

Why Two Arrays? The Traditional Algorithm Linux is More Efficient

Locking Runqueues Real-Time Scheduling

Sleeping and Waking

s There is a bit map indicating which queues have processes that are ready to run

s Find the first bit that's set: x 140 queues 5 integers x Only a few compares to find the first that is non-zero x Hardware instruction to find the first 1-bit x Time depends on the number of priority levels, not the number of processes

8 / 40

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download