Transcript Linux Processing Management/Scheduling Jamie Cummings Philip

Linux Processing
Management/Scheduling
Jamie Cummings
Philip Hansen
Content
●
●
●
●
●
Linux process states
Information stored about each process
How the scheduler works
Differences in a Real-time system
Differences in a multiprocessor
environment
Linux State Diagram
Process Table Contents
The process table is a double linked list
with an entry for each task
●
●
●
●
●
State
Process priority
Real-time information
Mm_struct– describes memory
allocated to the task and the location of
its page table in memory
Thread_struct – contains threads
register values
Process Scheduling - Goals
●
●
●
Run all tasks
–
Within a reasonable amount of time
–
With respect task priorities
–
While maintaining high resource utilization and
throughput
–
Reduce overhead of scheduling operations
Provide high-processor affinity
In the 2.4 kernel, all the scheduler functions ran
at O(n). The 2.6 kernel has these functions
running at O(1) :-D
Timing
●
●
●
A process's time slice is determined by the
process's priority
Always between 10 – 200 time intervals (usually
10 – 200 milliseconds)
A process will run until one of three things
happens
1) Its time slice expires
2)A higher priority process becomes available
3)The process blocks
Expired time slice
Library with only one computer represents processor.
Moderator represents the process scheduler.
Users represent processes and have a card with
their time slice
Scenario: The user presents the scheduler with their
time slice and begins using the computer. Once the
time slice is up, the scheduler re-evaluates the the
user and presents him with a new time slice. He then
joins the end of the queue.
A higher priority process becomes
available
Scenario: While using the computer, a
user is removed in favor of a higher
priority user. The moderator removes
the user and saves any important
information.
When a higher process becomes
available the scheduler removes the
current process and saves its
information.
The process blocks
Food and drink aren't allowed in the Library so the user would have to leave the
machine if he wanted food or drink. There are a few other I/O type scenarios
where a user might leave the machine suddenly.
Epoch
●
●
A period of time in which each task in the run
queue will execute at least once.
Time is defined by the starvation limit, which
occurs when a process has gone too long
without running.
–
●
Default is 10n where n is the number of tasks in the
run queue.
Interactive vs Non-interactive (batch)
At the end of an epoch...
The active variable points to an array with all
processes waiting to be run. When the
starvation limit is reached, each process runs
for one more time slice. It is then moved the
the expired array. Once there are no more
processes in the active array, the active
variable switches it's pointer to the expired
variable's array, and vice-versa.
Note, arrays[0] should probably be array0[] and array[1] should probably be array1[]
Playing Nice
●
●
●
●
●
A schedule's priority is determined by its nice value. When
the process is created it is assigned a nice value, which is
called its static priority.
A value between -20 and 19, with smaller number having
higher priority.
If a process is interrupted by a higher priority task or
spends a lot of time sleeping, it may receive a priority
boost up to five integers (which means you subtract up to
five from its nice value).
If a process is processor bound (taking up a lot of
processor time) it may loose some of its priority (or have
up to five integers added to its nice value)
This is called effective priority.
More on Nice
●
●
If a process uses the clone command to
create child processes the child processes
must share the parent's time slice during their
first epoch.
This keeps processes from taking over
resources by constantly spawning new
processes.
Not all processes play Nice
●
●
Real time processes never end up in an
expired state.
Real processes must complete their tasks in
a certain amount of time.
–
●
There are 140 priority levels. Real-time occupies
the upper 100.
Real-time processes may only be created by
the root user.
Multiprocessor Scheduling
●
●
Problem: Because each processor has its
own run queue (new feature in 2.6
kernel), there is the potential for one
processor to be idle while one is busy
Solution: Every timer interrupt, the
scheduler will perform load balancing if
one processor has >25% more tasks in its
run queue than another
Load Balancing
●
●
●
Actual migration of tasks is limited to
every 200 timer interrupts to reduce
overhead
The scheduler will not attempt to make
the run queues of the two processors
equal. It will only migrate enough tasks to
reduce the difference by half
The scheduler will attempt to migrate only
cache-cold tasks.
The Power
Userfirendly by J.D. “Illiad” Frazer
References
Deitel, HM., Deitel, PJ., Choffnes, DR. Operating Systems, 3rd edition. Pearson
Prentice Hall, NJ, 2004.
●
Bovet, Daniel P., Cesati, Marco. Understanding the Linux Kernel, 3rd edition.
O'Reilly, 2005.
●
IBM's documentation on the Linux scheduler. http://www128.ibm.com/developerworks/linux/library/l-scheduler/
●
Linux Journal Article on the 2.4 kernel and improvements that were being worked
on. http://www.linuxjournal.com/article/6530
●
Documentation on the Linux scheduler.
http://josh.trancessoftware.com/linux/linux_cpu_scheduler.pdf
●
Further Reading
●
Documentation on processes and nicing. http://docs.cs.byu.edu/docs/runaway/