Foreword
Process scheduling is a complex project, and the quality of the scheduling strategy directly affects the system experience.
In the LInux Kernel, the most commonly used algorithm is the Completely Fair Scheduling (CFS) algorithm. Today we hack the kernel and spy on how it schedules processes one by one.
Pick your next task
pick_next_task_fair(), pick the next task to be executed
We add printing to intuitively feel the scheduling switching between processes.
kernel/sched/core.c
/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
__pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{<!-- -->
const struct sched_class *class;
struct task_struct *p;
\t// Add to
static int count = 0;
/*
* Optimization: we know that if all tasks are in the fair class we can
* call that function directly, but only if the @prev task wasn't of a
* higher scheduling class, because otherwise those lose the
* opportunity to pull in more work from other CPUs.
*/
if (likely(prev->sched_class <= & amp;fair_sched_class & amp; & amp;
rq->nr_running == rq->cfs.h_nr_running)) {<!-- -->
p = pick_next_task_fair(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto restart;
/* Assume the next prioritized class is idle_sched_class */
if (!p) {<!-- -->
put_prev_task(rq, prev);
p = pick_next_task_idle(rq);
}
//Add the following four lines
if (count < 10000) {<!-- -->
printk("-pid: =, .16s, %d\\
", p->pid, p->comm, count);
count + + ;
}
return p;
}
restart:
put_prev_task_balance(rq, prev, rf);
for_each_class(class) {<!-- -->
p = class->pick_next_task(rq);
if(p)
return p;
}
/* The idle class should always have a runnable task: */
BUG();
}
smp_twd: clock not found -2 Console: color dummy device 80x30 Calibrating local timer... 93.37MHz. Calibrating delay loop... 1581.05 BogoMIPS (lpj=7905280) pid_max: default: 32768 minimum: 301 Mount-cache hash table entries: 1024 (order: 0, 4096 bytes, linear) Mountpoint-cache hash table entries: 1024 (order: 0, 4096 bytes, linear) CPU: Testing write buffer coherency: ok CPU0: Specter v2: using BPIALL workaround -pid: 2, swapper/0, 0 -pid: 1, swapper/0, 1 CPU0: thread -1, cpu 0, socket 0, mpidr 80000000 -pid: 2, kthreadd, 2 -pid: 3, kthreadd, 3 -pid: 1, swapper/0, 4 -pid: 2, kthreadd, 5 -pid: 3, rcu_gp, 6 -pid: 4, kthreadd, 7 -pid: 1, swapper/0, 8 -pid: 2, kthreadd, 9 -pid: 4, rcu_par_gp, 10 -pid: 5, kthreadd, 11 -pid: 1, swapper/0, 12 -pid: 2, kthreadd, 13 -pid: 5, kworker/0:0, 14 -pid: 6, kthreadd, 15 -pid: 1, swapper/0, 16 -pid: 2, kthreadd, 17 -pid: 6, kworker/0:0H, 18 -pid: 7, kthreadd, 19 -pid: 1, swapper/0, 20 -pid: 2, kthreadd, 21 -pid: 7, kworker/u8:0, 22 -pid: 8, kthreadd, 23 -pid: 1, swapper/0, 24 Setting up static identity map for 0x60100000 - 0x60100060 -pid: 2, kthreadd, 25 -pid: 8, mm_percpu_wq, 26 -pid: 9, kthreadd, 27 -pid: 1, swapper/0, 28 -pid: 9, ksoftirqd/0, 29 -pid: 1, swapper/0, 30 rcu: Hierarchical SRCU implementation. -pid: 2, kthreadd, 31 -pid: 9, ksoftirqd/0, 32 -pid: 10, kthreadd, 33 -pid: 1, swapper/0, 34 -pid: 2, kthreadd, 35 -pid: 10, rcu_sched, 36 -pid: 11, kthreadd, 37 -pid: 1, swapper/0, 38 -pid: 11, migration/0, 39 -pid: 1, swapper/0, 40 -pid: 12, kthreadd, 41 -pid: 1, swapper/0, 42 -pid: 12, cpuhp/0, 43 -pid: 1, swapper/0, 44 smp: Bringing up secondary CPUs ... -pid: 2, kthreadd, 45 -pid: 12, cpuhp/0, 46 -pid: 13, kthreadd, 47 -pid: 1, swapper/0, 48 -pid: 13, cpuhp/1, 49 -pid: 1, swapper/0, 50 -pid: 2, kthreadd, 51 -pid: 14, kthreadd, 52 -pid: 1, swapper/0, 53 -pid: 14, migration/1, 54 -pid: 1, swapper/0, 55 -pid: 2, kthreadd, 56 -pid: 15, kthreadd, 57 -pid: 1, swapper/0, 58 -pid: 15, ksoftirqd/1, 59 -pid: 1, swapper/0, 60 -pid: 2, kthreadd, 61 -pid: 10, rcu_sched, 62 -pid: 16, kthreadd, 63 -pid: 1, swapper/0, 64 -pid: 2, kthreadd, 65 -pid: 16, kworker/1:0, 66 -pid: 17, kthreadd, 67 -pid: 1, swapper/0, 68 -pid: 17, kworker/1:0H, 69 -pid: 0, swapper/0, 70 CPU1: thread -1, cpu 1, socket 0, mpidr 80000001 CPU1: Specter v2: using BPIALL workaround -pid: 1, swapper/0, 71 -pid: 13, cpuhp/1, 72 -pid: 0, swapper/0, 72 -pid: 16, kworker/1:0, 74 -pid: 1, swapper/0, 74 -pid: 15, ksoftirqd/1, 75 -pid: 17, kworker/1:0H, 76 -pid: 0, swapper/1, 77 -pid: 2, kthreadd, 79 -pid: 18, kthreadd, 80 -pid: 1, swapper/0, 81 -pid: 18, cpuhp/2, 82 -pid: 1, swapper/0, 83 -pid: 2, kthreadd, 84 -pid: 19, kthreadd, 85 -pid: 1, swapper/0, 86 -pid: 19, migration/2, 87 -pid: 1, swapper/0, 88 -pid: 2, kthreadd, 89 -pid: 20, kthreadd, 90 -pid: 1, swapper/0, 91 -pid: 20, ksoftirqd/2, 92 -pid: 1, swapper/0, 93 -pid: 2, kthreadd, 94 -pid: 21, kthreadd, 95 -pid: 1, swapper/0, 96 -pid: 2, kthreadd, 97 -pid: 21, kworker/2:0, 98 -pid: 22, kthreadd, 99 -pid: 1, swapper/0, 100 -pid: 10, rcu_sched, 101 -pid: 22, kworker/2:0H, 102 -pid: 0, swapper/0, 103 -pid: 10, rcu_sched, 104 -pid: 0, swapper/0, 105 -pid: 10, rcu_sched, 106 -pid: 0, swapper/0, 107 -pid: 10, rcu_sched, 108 -pid: 0, swapper/0, 109 CPU2: thread -1, cpu 2, socket 0, mpidr 80000002 CPU2: Specter v2: using BPIALL workaround -pid: 1, swapper/0, 110 -pid: 10, rcu_sched, 111 -pid: 18, cpuhp/2, 112 -pid: 0, swapper/0, 113 -pid: 20, ksoftirqd/2, 114 -pid: 1, swapper/0, 114 -pid: 2, kthreadd, 116 -pid: 21, kworker/2:0, 117 -pid: 22, kworker/2:0H, 118 -pid: 23, kthreadd, 119 -pid: 0, swapper/2, 119 -pid: 1, swapper/0, 120 -pid: 23, cpuhp/3, 122 -pid: 1, swapper/0, 123 -pid: 2, kthreadd, 124 -pid: 24, kthreadd, 125 -pid: 1, swapper/0, 126 -pid: 24, migration/3, 127 -pid: 1, swapper/0, 128 -pid: 2, kthreadd, 129 -pid: 25, kthreadd, 130 -pid: 1, swapper/0, 131 -pid: 25, ksoftirqd/3, 132 -pid: 1, swapper/0, 133 -pid: 2, kthreadd, 134 -pid: 26, kthreadd, 135 -pid: 1, swapper/0, 136 -pid: 2, kthreadd, 137 -pid: 26, kworker/3:0, 138 -pid: 27, kthreadd, 139 -pid: 1, swapper/0, 140 -pid: 27, kworker/3:0H, 141 -pid: 0, swapper/0, 142 CPU3: thread -1, cpu 3, socket 0, mpidr 80000003 CPU3: Specter v2: using BPIALL workaround -pid: 1, swapper/0, 143 -pid: 0, swapper/0, 144 -pid: 1, swapper/0, 145 -pid: 0, swapper/0, 146 -pid: 23, cpuhp/3, 147 -pid: 25, ksoftirqd/3, 148 -pid: 26, kworker/3:0, 149 -pid: 27, kworker/3:0H, 150 -pid: 0, swapper/3, 151 -pid: 1, swapper/0, 152 smp: Brought up 1 node, 4 CPUs SMP: Total of 4 processors activated (5903.15 BogoMIPS). CPU: All CPU(s) started in SVC mode. -pid: 10, rcu_sched, 153 -pid: 2, kthreadd, 154 -pid: 28, kthreadd, 155 -pid: 0, swapper/1, 156 -pid: 0, swapper/0, 156 -pid: 1, swapper/0, 158 -pid: 0, swapper/0, 159 -pid: 28, kdevtmpfs, 160 -pid: 0, swapper/1, 161 -pid: 1, swapper/0, 161 devtmpfs: initialized -pid: 10, rcu_sched, 163 -pid: 0, swapper/2, 164 -pid: 2, kthreadd, 165 -pid: 0, swapper/0, 166 -pid: 29, kthreadd, 167 -pid: 0, swapper/3, 168 -pid: 1, swapper/0, 169 -pid: 29, inet_frag_wq, 170 -pid: 0, swapper/3, 171 VFP support v0.3: implementor 41 architecture 3 part 30 variant 9 rev 0 clocksource: jiffies: mask: 0xffffffff max_cycles: 0xffffffff, max_idle_ns: 19112604462750000 ns futex hash table entries: 1024 (order: 4, 65536 bytes, linear) NET: Registered PF_NETLINK/PF_ROUTE protocol family -pid: 16, kworker/1:0, 172 -pid: 5, kworker/0:0, 172 -pid: 26, kworker/3:0, 172 -pid: 2, kthreadd, 175 -pid: 0, swapper/1, 176 -pid: 0, swapper/3, 176 -pid: 30, kthreadd, 178 -pid: 0, swapper/0, 179 -pid: 32, kthreadd, 179 -pid: 31, kthreadd, 181 -pid: 0, swapper/2, 182 -pid: 5, kworker/0:0, 183 -pid: 16, kworker/1:0, 183 -pid: 26, kworker/3:0, 184 -pid: 30, kworker/1:1, 186 -pid: 32, kworker/3:1, 186 -pid: 31, kworker/0:1, 186 -pid: 1, swapper/0, 189 -pid: 0, swapper/1, 190 -pid: 0, swapper/3, 190 -pid: 31, kworker/0:1, 192 -pid: 30, kworker/1:1, 193 -pid: 32, kworker/3:1, 194 -pid: 21, kworker/2:0, 194 -pid: 1, swapper/0, 196 -pid: 0, swapper/3, 196 -pid: 0, swapper/2, 197 -pid: 2, kthreadd, 199 -pid: 1, swapper/0, 200 -pid: 33, kthreadd, 201 -pid: 21, kworker/2:0, 202 -pid: 0, swapper/1, 203 -pid: 33, kworker/2:1, 204 -pid: 0, swapper/0, 205 -pid: 0, swapper/2, 205 -pid: 1, swapper/0, 207 DMA: preallocated 256 KiB pool for atomic coherent allocations -pid: 31, kworker/0:1, 208 -pid: 1, swapper/0, 209 cpuidle: using governor ladder hw-breakpoint: debug architecture 0x4 unsupported. Serial: AMBA PL011 UART driver irq: type mismatch, failed to map hwirq-75 for interrupt-controller@1e001000! -pid: 10, rcu_sched, 210 -pid: 0, swapper/2, 211 -pid: 31, kworker/0:1, 212 -pid: 1, swapper/0, 213 -pid: 2, kthreadd, 214 -pid: 0, swapper/0, 215 -pid: 34, kthreadd, 216 -pid: 0, swapper/2, 217 -pid: 1, swapper/0, 218 -pid: 2, kthreadd, 219 -pid: 34, khungtaskd, 220 -pid: 0, swapper/0, 221 -pid: 0, swapper/2, 222 -pid: 35, kthreadd, 223 -pid: 0, swapper/1, 224 -pid: 1, swapper/0, 225 -pid: 35, oom_reaper, 226 -pid: 2, kthreadd, 227 -pid: 0, swapper/1, 228 -pid: 0, swapper/0, 229 -pid: 36, kthreadd, 230 -pid: 0, swapper/2, 231 -pid: 1, swapper/0, 232 -pid: 36, writeback, 233 -pid: 0, swapper/2, 234 -pid: 2, kthreadd, 235 -pid: 0, swapper/0, 236 -pid: 37, kthreadd, 237 -pid: 0, swapper/3, 238 -pid: 1, swapper/0, 239 -pid: 37, kcompactd0, 240 -pid: 0, swapper/3, 241 -pid: 10, rcu_sched, 242 -pid: 0, swapper/2, 243 -pid: 2, kthreadd, 244 -pid: 0, swapper/0, 245 -pid: 38, kthreadd, 246 -pid: 0, swapper/3, 247 -pid: 1, swapper/0, 248 -pid: 38, kblockd, 249 -pid: 0, swapper/3, 250 SCSI subsystem initialized -pid: 2, kthreadd, 251 -pid: 0, swapper/0, 252 -pid: 39, kthreadd, 253 -pid: 0, swapper/3, 254 -pid: 1, swapper/0, 255 -pid: 39, ata_sff, 256 -pid: 0, swapper/3, 257 usbcore: registered new interface driver usbfs usbcore: registered new interface driver hub usbcore: registered new device driver usb -pid: 10, rcu_sched, 258 -pid: 0, swapper/2, 259 pps_core: LinuxPPS API ver. 1 registered pps_core: Software ver. 5.3.6 - Copyright 2005-2007 Rodolfo Giometti <[email protected]> PTP clock support registered Advanced Linux Sound Architecture Driver Initialized. -pid: 1, swapper/0, 260 clocksource: Switched to clocksource arm,sp804 -pid: 10, rcu_sched, 261 -pid: 0, swapper/2, 262 -pid: 7, kworker/u8:0, 263 -pid: 2, kthreadd, 264 -pid: 28, kdevtmpfs, 265 -pid: 0, swapper/0, 266 -pid: 40, kthreadd, 267 -pid: 0, swapper/3, 268 -pid: 7, kworker/u8:0, 269 -pid: 40, kworker/u8:1, 270 -pid: 0, swapper/3, 271 -pid: 0, swapper/1, 272 -pid: 1, swapper/0, 273 -pid: 0, swapper/3, 274 -pid: 28, kdevtmpfs, 275 -pid: 0, swapper/1, 276 -pid: 1, swapper/0, 277 -pid: 0, swapper/3, 278 -pid: 28, kdevtmpfs, 279 -pid: 0, swapper/1, 280 -pid: 1, swapper/0, 281 -pid: 0, swapper/3, 282 -pid: 28, kdevtmpfs, 283 -pid: 0, swapper/1, 284 -pid: 1, swapper/0, 285 -pid: 0, swapper/3, 286 -pid: 28, kdevtmpfs, 287 -pid: 0, swapper/1, 288 -pid: 1, swapper/0, 289 -pid: 0, swapper/3, 290 -pid: 28, kdevtmpfs, 291 -pid: 0, swapper/1, 292 -pid: 1, swapper/0, 293 -pid: 0, swapper/3, 294 -pid: 28, kdevtmpfs, 295 -pid: 0, swapper/1, 296 -pid: 1, swapper/0, 297 -pid: 0, swapper/3, 298 -pid: 28, kdevtmpfs, 299 -pid: 0, swapper/1, 300 -pid: 1, swapper/0, 301 -pid: 0, swapper/3, 302 -pid: 28, kdevtmpfs, 303 -pid: 0, swapper/1, 304 -pid: 1, swapper/0, 305 -pid: 0, swapper/3, 306 -pid: 28, kdevtmpfs, 307 -pid: 0, swapper/1, 308 -pid: 1, swapper/0, 309 -pid: 0, swapper/3, 310 -pid: 28, kdevtmpfs, 311
# ps
PID USER COMMAND
1 root init
2 root [kthreadd]
3 root [rcu_gp]
4 root [rcu_par_gp]
5 root [kworker/0:0-mm_]
6 root [kworker/0:0H-mm]
7 root [kworker/u8:0-ev]
8 root [mm_percpu_wq]
9 root [ksoftirqd/0]
10 root [rcu_sched]
11 root [migration/0]
12 root [cpuhp/0]
13 root [cpuhp/1]
14 root [migration/1]
15 root [ksoftirqd/1]
16 root [kworker/1:0-rcu]
17 root [kworker/1:0H-kb]
18 root [cpuhp/2]
19 root [migration/2]
20 root [ksoftirqd/2]
21 root [kworker/2:0-mm_]
22 root [kworker/2:0H-kb]
23 root [cpuhp/3]
24 root [migration/3]
25 root [ksoftirqd/3]
26 root [kworker/3:0-rcu]
27 root [kworker/3:0H-ev]
28 root [kdevtmpfs]
29 root [inet_frag_wq]
30 root [kworker/1:1-pm]
31 root [kworker/0:1-mm_]
32 root [kworker/3:1-eve]
33 root [kworker/2:1-mm_]
34 root [khungtaskd]
35 root [oom_reaper]
36 root [writeback]
37 root[kcompactd0]
38 root [kblockd]
39 root [ata_sff]
40 root [kworker/u8:1-ev]
41 root [rpciod]
42 root [kworker/3:1H-kb]
43 root [kworker/u9:0]
44 root [xprtiod]
45 root [kswapd0]
46 root [nfsiod]
47 root [kworker/3:2-eve]
48 root [kworker/u8:2-ev]
49 root [kworker/1:2-mm_]
53 root [irq/33-mmci-pl1]
54 root [kworker/1:3-eve]
55 root[mmc_complete]
56 root [kworker/1:1H-kb]
57 root [kworker/0:1H-mm]
58 root [card0-crtc0]
59 root [ext4-rsv-conver]
61 root [kworker/3:2H]
74 root [kworker/2:1H-kb]
78 root /sbin/syslogd -n
82 root /sbin/klogd -n
134 root udhcpc -t1 -A3 -b -R -O search -O staticroutes -p /var/run/udhcp
136 root-sh
138 rootps
The first few dozen times of scheduling are all switching between processes within 20. At this time, it is in the kernel thread creation stage, and the number of processes is gradually increasing.
After 275 times, it basically switches between process 0 1 28, 0 is idle, 1 swapper/0 (the predecessor of the init process), 28 is inet_frag_wq network related
After the kernel is loaded and the init process is started, process No. 1 changes from swapper/0 to init.
-pid: 58, kworker/0:1H, 1412 -pid: 0, swapper/0, 1413 -pid: 1, swapper/0, 1414 -pid: 57, kworker/1:1H, 1415 -pid: 0, swapper/1, 1416 -pid: 58, kworker/0:1H, 1417 -pid: 0, swapper/0, 1418 -pid: 1, swapper/0, 1419 -pid: 57, kworker/1:1H, 1420 -pid: 0, swapper/1, 1421 -pid: 37, kcompactd0, 1422 -pid: 0, swapper/2, 1423 -pid: 57, kworker/1:1H, 1424 -pid: 15, ksoftirqd/1, 1425 -pid: 1, swapper/0, 1426 -pid: 57, kworker/1:1H, 1427 -pid: 1, swapper/0, 1428 // -pid: 57, kworker/1:1H, 1429 -pid: 15, ksoftirqd/1, 1430 -pid: 1, init, 1431 // Process No. 1 changes from swapper/0 to init -pid: 9, ksoftirqd/0, 1432 -pid: 58, kworker/0:1H, 1433 -pid: 0, swapper/0, 1434 -pid: 57, kworker/1:1H, 1435 -pid: 0, swapper/1, 1436 -pid: 58, kworker/0:1H, 1437 -pid: 0, swapper/0, 1438 -pid: 1, init, 1439 -pid: 57, kworker/1:1H, 1440 -pid: 0, swapper/1, 1441 -pid: 58, kworker/0:1H, 1442 -pid: 0, swapper/0, 1443 -pid: 1, init, 1444
When you see S02sysctl and the like, you know that each startup script under /etcinit.d/ is being executed.
-pid: 87, S02sysctl, 2303 -pid: 0, swapper/1, 2304 -pid: 88, S02sysctl, 2305 -pid: 81, syslogd, 2306 -pid: 88, S02sysctl, 2307 -pid: 89, S02sysctl, 2308 -pid: 81, syslogd, 2309 -pid: 37, kcompactd0, 2310 -pid: 10, rcu_sched, 2311 -pid: 88, S02sysctl, 2311 -pid: 85, klogd, 2312 -pid: 81, syslogd, 2314 -pid: 20, ksoftirqd/2, 2314 -pid: 85, klogd, 2316 -pid: 88, S02sysctl, 2316 -pid: 81, syslogd, 2318 -pid: 87, S02sysctl, 2319 -pid: 88, S02sysctl, 2319 -pid: 81, syslogd, 2321 -pid: 89, S02sysctl, 2322 -pid: 88, S02sysctl, 2322 -pid: 90, S02sysctl, 2323 -pid: 10, rcu_sched, 2323 -pid: 85, klogd, 2324 -pid: 81, syslogd, 2326 -pid: 88, S02sysctl, 2327 -pid: 81, syslogd, 2328 -pid: 91, S02sysctl, 2328 -pid: 10, rcu_sched, 2330 -pid: 85, klogd, 2332 -pid: 20, ksoftirqd/2, 2333 -pid: 88, S02sysctl, 2333 -pid: 85, klogd, 2334 -pid: 30, kworker/0:1, 2334 -pid: 89, xargs, 2337 -pid: 91, S02sysctl, 2338 -pid: 81, syslogd, 2339 -pid: 0, swapper/3, 2340
From now on, process scheduling is basically fixed between the 0 idle process and the syslogd process.
-pid: 81, syslogd, 3145 -pid: 85, klogd, 3147 -pid: 0, swapper/1, 3148 -pid: 81, syslogd, 3149 -pid: 0, swapper/1, 3150 -pid: 81, syslogd, 3151 -pid: 0, swapper/1, 3152 -pid: 81, syslogd, 3153 -pid: 0, swapper/1, 3154 -pid: 81, syslogd, 3155 -pid: 0, swapper/1, 3156 -pid: 81, syslogd, 3157 -pid: 0, swapper/1, 3158 -pid: 81, syslogd, 3159 -pid: 10, rcu_sched, 3160 -pid: 0, swapper/0, 3161 -pid: 0, swapper/1, 3162 -pid: 81, syslogd, 3163 -pid: 20, ksoftirqd/2, 3164 -pid: 85, klogd, 3165 -pid: 0, swapper/1, 3165 -pid: 81, syslogd, 3167 -pid: 0, swapper/1, 3168 -pid: 42, kworker/3:1H, 3168 -pid: 81, syslogd, 3170 -pid: 0, swapper/3, 3171 -pid: 58, kworker/0:1H, 3172 -pid: 0, swapper/0, 3173 -pid: 0, swapper/1, 3174 -pid: 107, ifup, 3174 -pid: 81, syslogd, 3176 -pid: 0, swapper/1, 3177