вход по аккаунту

код для вставкиСкачать
The Linux Scheduler
2.4 vs 2.6
Michael McCabe
Scheduling Basics
 Tasks are divided into three groups, real time
processes, IO bound, and CPU bound
 Real Time - Extremely high scheduling
requirements, needs a guarantee on how often they
will run, usually the highest priority process in a
 IO bound - processes that spend most of their time
waiting for data going to or coming from the disk
Scheduling Basics cont.
 CPU bound - Processes that consume large
amounts of cpu
 Time slice - amount of time that a process
can run on the CPU
 Preemption - When the execution of the
currently running process is interrupted in
order to run a different, higher priority
The schedule function
 Schedule() is the function in the linux kernel that
does the actual scheduling
 Has multiple ways of being run
 Runs when a new process needs to be selected for
 Is called when the currently running process is
blocked, waiting for a resource
 Each processor can call schedule on its own
 Many device drivers will call schedule
2.4 Basics
 1400 Lines of code
 Three basic data structures
 Basic data structure is schedule_data. This
data structure contains a pointer to the
currently running process and the timestamp
of the last time the schedule function ran
 There is one run queue, and it’s a linked list
struct schedule_data {
struct task_struct * curr;
cycles_t last_schedule;
} schedule_data;
char __pad [SMP_CACHE_BYTES];
Schedule_data explained
 Remarkably simple data structure
 Defined in sched.c
 Contains a time stamp of the last process
 Also contains a pointer to the process that is
currently running
2.4 SMP
 Reschedule_idle checks to see if the process
that just moved out of the running state
should be moved to a different cpu
 It doesn’t use the counter and nice values
directly, it uses the goodness function to
check priorities
 Goodness takes into account the cost of
moving a process across cpus
2.6 Basics
 5700 Lines of code
 Run queue and priority arrays are the basic
data structures
 One run queue per processor
 Two priority arrays per run queue
Run Queue
spinlock_t lock;
unsigned long nr_running;
unsigned long prio_bias;
unsigned long cpu_load[3];
unsigned long long nr_switches;
unsigned long nr_uninterruptible;
unsigned long expired_timestamp;
unsigned long long timestamp_last_tick;
task_t *curr, *idle;
struct mm_struct *prev_mm;
prio_array_t *active, *expired, arrays[2];
int best_expired_prio;
atomic_t nr_iowait;
struct sched_domain *sd;
int active_balance;
int push_cpu;
task_t *migration_thread;
struct list_head migration_queue;
Run queue explained
Primary scheduling data structure
Defined in sched.c
Needs to be locked before its modified
Locks are obtained on multiple run queues
in ascending order
Priority Array
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
Priority Arrays explained
 Defined in sched.c
 Provides constant running time for the scheduling
 Contains lists of runnable processes at each
priority level
 A bitmap is used to efficiently discover the highest
priority process
 When a task with priority 10 becomes runnable bit
10 in the bitmap gets set to 1
2.6 SMP
 Load_balance is the function that makes
sure each processor has a relatively equal
number of processes on it
 Only is run on multi processor systems
 Runs every millisecond when the system is
idle or every 200 milliseconds
 Only tasks that are not running are moved
Big O running times
 The 2.6 kernel has a
constant running time
 O(1)
 Leads to better scalability
than the 2.4 kernel
 Also has a much more
complex implementation
 Time slices are calculated
when a process’s timeslice
is used, before it moves to
the expired array
 2.4 kernel has a linear
running time in the
worst case
 Loops over the
process list at the end
of each time quantum
 Recalculates each
processes’s time slice
Real time differences
 2.6 provides soft real
time support
 Real time processes
will preempt regular
 Real time priorities are
set statically
 Not all versions of the
2.4 kernel can offer
any real time
 Not all versions of the
2.4 kernel offer
 Priority inversion
occurs frequently in
the 2.4 kernel
 Understanding the Linux Kernel 2nd
 Kernel newbies
 Linux Kernel Cross Reference
 Linux Kernel Development
 Linux Device Drivers 3rd Edition
Пожаловаться на содержимое документа