Introduction To The Linux Kernel
Introduction To The Linux Kernel
Introduction To The Linux Kernel
國立中正大學
資訊工程研究所
羅習五 老師
Kernel mode and kernel space
User space
Process context
Kernel space
(including
bottom half)
CTX
Top halve
ISR
A preemptve kernel
• No libc support
– There are multple reasons for this, including some
chicken-and-the-egg situatons, but the primary re
ason is speed and size (upcall?).
– Many of the usual libc functons have been impl
emented inside the kernel.
• For example <linux/string.h>
Inline Functons
The process
becomes runnable
if it receives a
signal.
33
Timeslice
• The tmeslice is the numeric value that represen
ts how long a task can run untl it is pre-empted.
– too short => large overhead of switching process
– too long => poor interactve response
• Linux’s CFS scheduler does not directly assign t
meslices to processes.
– CFS assigns processes a proportion of the processor.
– the amount of processor tme that a process receive
s is a functon of the load of the system
34
2.4 scheduler - SMP
busy
run queue
busy
35
2.4 scheduler
• Non-preemptble kernel
– Set p->need_resched if schedule() should be invok
ed at the ‘next opportunity‘ (kernel => user mode)
.
• Round-robin
– task_struct->counter: number of clock tcks left to
run in this scheduling slice, decremented by a tme
r.
36
2.4 scheduler
38
2.4 scheduler – ‘goodness’
(to improve multthreading performance)
if (p->mm == prev->mm)
return p->counter + p->priority + 1;
else
return p->counter + p->priority;
39
2.4 scheduler - SMP
40
Scheduling policy
41
2.6 scheduler
run queue
task migraton
(put + pull)
run queue
42
2.6 scheduler –
User Preempton
43
2.6 scheduler –
Kernel Preempton
• The Linux kernel is a fully preemptve kernel.
– It is possible to preempt a task at any point, so long as the kernel is in a sta
te in which it is safe to reschedule.
– “safe to reschedule”: kernel does not hold a lock
• The Linux design:
– adding of a preempton counter, preempt_count, to each process's thread
_info
– This count increments once for each lock that is acquired and decrements
once for each lock that is released
• Kernel preempton can also occur explicitly, when a task in the kern
el blocks or explicitly calls schedule().
– no additional logic is required to ensure that the kernel is in a state that is
safe to preempt!
44
Most tasks have dynamic priorities
runqueue
that are based on their “nice” value
(static priority) plus or minus 5
Interactivity of a task ≈
1/sleep_time
dynPrio = staticPrio +
bonus
tsk1
bonus = -5 ~ +5
bonus ≈ 1/sleep_time
tsk3
tsk2 tsk3
I/O
bound
expired
active
45
When all tasks have exhausted
runqueue
their time slices, the two priority
arrays are exchanged!
tsk1
tsk3
tsk2
expired
active
46
2.6 scheduler –
CFS
• Classical schedulers compute tme slices for ea
ch process in the system and allow them to ru
n untl their tme slice/quantum is used up.
– After that, all process need to be recalculated.
• CFS considers only the wait tme of a process
– The task with the most need for CPU tme is sched
uled.
47
2.6 scheduler –
CFS
48
vruntme
• The vruntime variable stores the virtual runtm
e of a process, which is the actual runtme norm
alized by the number of runnable processes.
• The virtual runtme’s units are nanoseconds and
therefore vruntme is decoupled from the tmer
tck.
• The virtual runtme is used to help us approxim
ate the “ideal multtasking processor” that CFS is
modeling.
49
Adding Processes to the Tree
This would occur when a process becomes runn
able (wakes up) or is first created via fork().
se->vruntime += cfs_rq->min_vruntime;
update_curr(cfs_rq);
account_entity_enqueue(cfs_rq, se);
update_stats_enqueue(cfs_rq, se);
__enqueue_entty(cfs_rq, se);
請參考課本
50
homework (繳交報告)
• 比較 2.4 、 O(1) 、 CFS 的差異,至少必須
包含:
– 如何分配 tme slice
– 如何決定“下一個 task”
– 如何藉由一個比較好的 scheduling algorithm 提
高整個系統的 throughput ( hint : i/o-bound &
cpu-bound )
• 你或許可以添加下列內容
– 找出一個例子,完整的說明這三種 scheduling al
gorithm 的優缺點
51