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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- pdf the philosophy of physical education and sport from ancient
- pdf linux scheduler columbia university
- pdf presentation notes for philosophy of education
- pdf six ethical philosophies paul martin lester
- pdf philosophies of punishment māris luste
- pdf evolution of operations management past present and future
- pdf philosophies of education linda reed s classroom
- pdf phl 2350 philosophies of columbia southern university
- pdf cte philosophy of education amazon web services
- pdf philosophies of education creighton university
Related searches
- columbia university graduate programs
- columbia university career fairs
- columbia university graduate tuition
- columbia university costs
- columbia university cost per year
- columbia university tuition and fees
- columbia university book cost
- columbia university cost of attendance
- columbia university graduate school tuition
- columbia university tuition 2019
- columbia university tuition 2020 2021
- columbia university neuroscience