· 8 years ago · Apr 24, 2018, 03:42 AM
1Linux - elitist attitude - only considers patche of real-world problems. Marketing bullets or one-off requests, such as pageable kernel memory, have received no consideration
2
3Kernel Development
4
5Introduction
6==============
7
8History
9-----------
10
11Unix - Elegant OS
12 (historically)
13 - only a few hundred system calls
14 - almost everything is a file
15 - written in C (portable)
16 - fast process creation time
17 - unique sys call 'fork'
18
19 (today)
20 - preemptive multitasking
21 - multi-threading
22 - virtual memory
23 - demand paging
24 - shared libraries w/ demand loading
25 - TCP/IP networking
26 - Many variants scale to hundreds of processors
27 - Some run on small embedded devices
28
29Linux
30 - Born of frustration at Unix's non-OpenSource
31 - Implements the Unix API as definded by POSIX and the Unix Spec
32 - Not a direct decendent of unix
33
34 - Modular design
35 - Can preempt itself (kernel preemption)
36 - Kernel threads
37 - Dynamic binary loading in Kernel image (kernel modules)
38
39 - Does not differentiate bewoon threads and normal processes
40 - all procs are the same, some just share resources
41 - Hot pluggable events ?
42 - TODO - look into why linux ignores some common Unix features that kernel developers consider poorly designed, such as STREAMS, or standards that are impossible to cleanly implement (p 8)
43
44 System Components Usually Include
45 - Kernel
46 - C lib
47 - toolchain
48 - basic sys utils (eg, login process and shell)
49
50OS Includes (Basic use and administration)
51
52 - Kernel (Manages hardware, distributes system resources)
53 - Interupt handlers
54 - Scheduler - to share processor time btwn procs
55 - Memory Management system
56 - System services (eg. networking / inter-proc comms)
57 - Device drivers
58 - Boot loader
59 - Command shell / UI
60 - Basic file system utilities
61
62Kernel
63 - Above user programs
64 - Privalleged access (kernel space vs user space)
65 - C library provideos higher level functions (although not always that different)
66 - Clibs make system calls
67 - Not all C-libs use system calls (eg strcopy)
68 - applications get work done through system calls
69
70 - in one of three states (always, even corner cases)
71 - User-space, executing process code
72 - Kernel-space, process context, executing system calls
73 - Kernel-space, interrupt context, handlin interrupts
74
75 - Usually a monolithic static binary
76 - Usually require a system with a paged memory-management unit (MMU)
77 - enables memory protection
78 - each proc gets uniq addr space
79 - Monolithic servers (Linux)
80 - Simpler design
81 - Microkernels (Parts of OS X and Windows NT)
82 - Several 'server' processes that communicate via IPC (inter-proc com)
83 - Can swap out server instances
84
85Interupts
86 - stop processor directly
87 - in turn, stops the kernel
88 - interrupts have numbers associated w/ them (hardware)
89 - handlers process and respond
90 - do not run in process context
91
92Getting Started w/ the Kernel
93=============================
94
95[Directories] - see comprehensive lists
96usr - early user-space code (initramfs) ?
97
98Built with flags
99Binary flags
100Tristates - dont build, build as module, build into source
101
102Configure flags with
103 make config (takes long time)
104 make menuconfig (ncurses)
105 make gconfig (gtk+)
106 or just edit `.config`
107
108Build with
109 `make`
110 `make -jn` mulit-proc build where n is # procs)
111
112Installing
113 Architecture and boot-loader dependent - see their docs
114
115 Modules are architecture independent
116 `make modules_install`
117
118Warnings
119 Kernel lacks memory protection afforded to user-space
120 Clibs not available - to heavy / slow
121 see instead `linux/things.h`
122 also - inotify?
123 printk rather than printf
124 inline functions for shit that needs to be fast
125 inline functions usually declared in header files
126
127 `static inline void wolf(unsigned long tail_size)`
128
129 # TODO - what is asm() assembly compiler directive.
130 Usually only used in parts of the kernel that are unique to a specific architecture - cause assembly is arch specific and linux has a goal to support cross platform
131 Small per-process fixed-size stack
132
133 Dereferencing a NULL pointer (illegal memory access)
134 - Major kernel error
135 - No `SIGSEGV` errors
136
137 Kernel memory is not pagable. Erry bite you eat is one less byte of available physical memory
138
139 # TODO - what does it mean to 'catch a trap'
140 Dont do floating point calcs
141
142 Kernel has small stack
143 Symmetrical multiprocessing (SMP)
144
145 Kernel must synchronize between scheduled tasks
146 Spinlocks and Semaphores usually used to avoid race conditions
147
148 Portability - handful of rules
149 Segregate system-specific code to appropriate dirs
150 Remain endian neutral
151 Be 64-bit clean, do not assume word or page sive
152
153
154 Anync interrupts, pre-emption, and SMP mean synchronization and concurrency are major concerns
155
1563. Process Management
157====================
158
159
160Process
161 - executing program code (the 'text section')
162 - Open files
163 - pending signals
164 - internal kernel data
165 - processor state
166 - memory address space (with one or more memory mappings)
167 - one or more threads of execution
168 - a data section contaiing global vars
169
170 Tasks kept in doubly linked list
171
172 Internally to the kernel known as a task
173 `task_struct`
174 - all the data needed by the kernel about a process
175 - allocated by the slab allocator
176 - the kernel stack holds the `thread_info`
177 - `thread_info` has a pointer to the `task_struct`
178 - there are maximum # procs 32k on old machines (cause small ints)
179 - will wrap around
180 - can be as high as 4m set in /proc/sys/kernel/pid_max
181 - `current` macro to get the `task_struct` of the currently running proc
182
183 - open files
184 - proc's addr space
185 - pending signals
186 - proc state
187
188 TODO - revisit 'slab allocator' & thread_info
189
190Threads
191 - objects of activity within a proc
192 includes
193 - unique program counter
194 - process stack
195 - set of procesor registers
196
197 - the kernel schedules threads, not processes
198 - Linux does not differentiate between threads and procs
199 threads are just a special kind of proc
200
201Procs
202 - procs provideo two virtualizations
203 - virtual processor - proc thinks it is alone on the cpu
204 - virtual memory - as if it were alone in its use of memory
205
206 - Threads share virtual memory but not virtual processor
207 - a program is not a process
208 must also include related resources
209
210 Important system calls
211 fork()
212 - creates a new proc
213 - returns 2x, once in the parent, once in the child
214 exec() - function family
215 - creates a new addrs space and loads a new program
216 exit()
217 - terminates the process and frees all resources
218 - puts proc into zombie state
219 wait4()
220 - parent inquires about the status of a terminated child
221 wait()
222 - parent can resolve zombie state
223 waitpid()
224 - parent can resolve zombie state
225
226
227Process State
228-------------
229
230Condition of the Proc (5 flags)
231
232system command `set_task_state(task, state);` # see `linux/sched.h`
233
234TASK_RUNNING
235 - either currently running or on a run queue
236 - only possible state for proc running in user-space
237TASK_INTERRUPTIBLE
238 - sleeping, eg waiting for some condition
239TASK_UNINTERRUPTIBLE
240 - sleeping, does not wake up and become runnable on signal
241__TASK_TRACED
242 - trace, eg. by ptrace
243__TASK_STOPPED
244 - not running, cannot run
245 - eg SIGSTOP, SIGTSTP, SIGTSTP, SIGTTIN received
246
247
248Process Context
249------------------
250
251Program code runs in user-space
252System calls or exception triggering
253 - will enter kernel-space
254 - are the only interface to the kernel
255 - kernel is 'executing on behalf of the process'
256 - kernel is in 'process context'
257
258The Process Family Tree
259--------------------
260
261`init` process is process #1
262 - started in last step of boot
263 - reads initscripts and executes more programs
264
265Process relationships are stored in the `task_struct`
266 - `parent`-> parent's `task_struct`
267 - `children` -> list of children
268
269Can navigate through tasks quite easily - see section for C samples
270
271Process creation
272-----------------
273
274fork()
275 - creates a child proc that is a copy of the current task
276 - almost an exact clone
277 - copy on write, each process gets its own copied page if written to
278 - only overhead is dup of parent's page table & creation of new process descriptor for the child
279
280exec() (a family)
281 - loads a new executable into the address space
282
283Forking
284----------
285
286most work done by `do_fork()` (see kernel/fork.c) which calls `copy_process()`
287
288- PF_SUPERPRIV flag removed from child - no super user privileges
289- Child runs first to avoid copy-on-write overhead if child is just `exec`ing
290
291- vfork is a little strange, parent waits for child to exec or exit
292 - use seems to be for legacy reasons. Or if you dont want to spend time copying the page table
293
294The Linux Implementation of Threads
295-----------------------------
296
297Shared memory space
298Multiple execution capabilities
299Enable 'concurrent programming' and 'parallelism'
300Linux don' care, it scheds like all procs
301Differs from Windows or others whose processes are much heavier
302Rather than 1 proc and 4 threads on Windows, linux has 4 procs w/ shared memory
303clone() sys command
304 - passed flags indicating which resources are shared
305See table here for clone flags and meanings
306
307Kernel Threads
308-----------
309
310Processes run by the kernel in kernel-space
311Schedualable and preemptable, just like normal processes
312Do not have an address space
313
314Things like 'flush' tasks and 'ksoftirqd' are delegated to kernel threads
315See kernel threads with `ps -ef`
316Can only be created by other kernel threads
317Usually forked of the `kthread` kernel process
318
319Procss Termination
320-------------------
321
322By signal or call to `exit()` # see `kernel/exit.c`
323Cleans up file descriptors that reach 0 user procs
324# TODO - what is a file descriptor
325Calls `schedule` to switch to a new process
326
327Removeing the Process Descriptor
328------------------------
329
330After the parent has received info on terminated child, child's `task_struct` is deallocated
331
332wait() and co
333 - use wait4()
334 - std behaviour is to suspend execution until child exits
335
336`do_exit() -> exit_notify() -> forget_original_parent() -> find_new_reaper()` (assigns the orphaned processes a new parent)
337
338`init` routinely calls wait() on its children, cleaning up any zombies assigned to it
339
340Process Scheduling
341==================
342
343Fundamental decision: decide which process will run next given a set of runnable processes
344
345Multitasking
346-------------
347
348Interleaving execution of multiple processes
349Runs processes simultaniously on multi-core machines
350Illusion of concurrency on single processor machines
351
352Enables processes to block or sleep when work is unavailable
353 - can wait until some event (keyboard input, network data, passage of time)
354 - many processes in memory, but only one in a runnable state
355
356Two flavors
357 - cooperative multitasking
358 - preemptive multitasking (most modern OSs)
359 - Scheduler decides when a process is to cease running and a new process is to begin running
360 - 'Preemption' - involuntarily suspending a running process
361 - Usually time a process runs is predetermined - called a 'timeslice'
362 - Linux's unique 'fair' scheduler does not employ timeslices _per se_
363
364 - coop multitasking - proc does not stop running until in voluntarily decides to do so (yielding)
365 - hung process can bring down the whole system
366 - scheduler cannot make global decisions about how long processes run
367 - processes can monopolize the procesor for longer than the user desires
368
369Linux's Process Scheduler
370----------------------
371
372O(1) scheduler
373 Constant time decisions on timeslice calculation and per-processor runqueues
374 Scaled well for large 'iron' systems with tens if not hundreds of processors
375
376 # TODO - define pathological, context: pathological failure
377 Latency-sensetive applications were not serviced well
378 Interactive processes - any application that users interact with
379
380Rotating Staircase Deadline scheduler (most notable of several new algorithms)
381 - introduced `fair scheduling` (borrowed from queuing theory)
382
383Policy
384--------
385
386Behavior of sched that determines what runs when
387Can determine the 'feel' of a system
388
389CFS - Completely fair scheduler
390
391### I/O-bound vs processor-bound Procs
392
393I/O - bound
394
395 Spends most of its time submitting and waiting on i/o requests
396 Usually runnable for only short durations as it eventually blocks waiting on mor io
397 (io here means any type of blockable resource)
398 eg most GUI applications
399
400Processor - bound
401
402 Spend much of their time executing code
403 Tend to run until preemption
404 Dont need to run often (system respone not required)
405 Run less frequently but for longer durations
406
407Some processes change behavior characteristics
408Try to satisfy two conflicting goals
409 fast process response time (low latency)
410 maximal system utilization (high throughput)
411
412Linux favors i/o-bound processes
413
414### Process Priority
415
416Rank processes based on their worth and need for processor time. Procs with higher priority run first and lower, later
417Processes with the same priority run round-robin
418
419Both user and system can set a process's priority to influence scheduling behavior
420
421Two priority ranges
422 'nice' values - in the range (-20 - +19)
423 larger nice values are lower priority (they ar nicer to other procs)
424 lower numbers ar higher priority
425 linux controls proportional timeslice size, others (like OS X) have control over absolute timeslice
426 Can see nice values using `ps -el`
427
428 # Note - after looking, things like kernel workers get maximal priority, pulso audio has high priority for proc in user space (want continuous play)
429
430 Real-time priority
431 By default rage from 0 - 99
432 Higher # - higher priority
433 All real-time processes are at a higher priority than normal procs
434 Disjoint value spaces from nice value
435
436 See with `ps -eo state,uid,pid,ppid,rtprio,time,comm` under RTPRIO
437 Value of '-' means the proc is not real-time
438 # Note - after looking, only RT user-space thing was a wifibus?
439
440Timeslice
441-----------
442
443How long a task resource can run before it is preempted
444
445 Too long => application doesnt feel interactive
446 Too short => lots of time wasted on context switching
447
448IO do not need long time slices
449Processor-bound processes crave long timeslices to keep their caches hot
450
451### On Linux
452
453 Procs get a proportion of processor time (determined by weight)
454 # NOTE - a weight is given. If things are to be added, they must be normalized because the processor use will always attempt to be 100% (1)
455 Nice value affects this performance
456
457 It is preemptive - so of a higher priority task becomes runnable
458 it will preempt the current process if it has not yet reached its
459 share of the cpu (as determined by its proportion)
460
461### Eg
462
463 Text editor and video encoder
464 Want text editor to have large amount of time available to it,
465 not because it needs in, but because we want it to have time available
466 Want text editor to preempt the video encoder when it wakes up
467 Video encoding can take more than its allotted time, esp b/c the text editor is usually blocked on io
468
469 The key is that linux is giving processor time immediately when the text editor requires (because it has used less than its allotted 50%)
470
471The Linux Scheduling Algorithm
472-------------------------------
473
474Has several scheduler classes
475Scheduler is modular
476Allows different algorithms to schedule different types of processes
477Algorithms can coexist
478
479Base scheduler
480 code is in `kernel/sched.c`
481 it iterates over each scheduler class in order of priority
482 the highest priority scheduler class that has a runnable process wins
483
484Completely Fair Scheduler
485 SCHED_NORMAL in Linux
486 code in `kernel/sched_fair.c`
487
488### Process Scheduling in Unix Systems
489
490Unix exports priority to the user-space in the form of nice values
491 `- leads to some problems
492 1. Mapping nice values onto timeslices requires a decision about what absolute timeslice to allot
493 Leads to sub-optimal switching behavior
494
495 When only 2 low priority processes run, each gets a very small timesilice. Many more context switches are required than if time were determined proportionally, rather than absolutely
496 2. Difference of 0 to 1 is much smaller than 18 to 19
497
498 Inverse processor time allotments
499 Background tasks (very nice tasks)
500 - usually need more computation time
501 - in unix, low priority gets smaller, not larger timeslices
502 Normal priority processes tend to be user tasks
503 - need shorter, more frequent time slices
504
505 Solution: make nice values geometric instead of additive
506
507Relative nice values are off too
508 Proportion of nice values does not map well to the proportion of processor time.
509 Eg NV0 = 100ms, NV1 = 95ms # almosts splitting 50/50
510 Eg NV18 = 10ms, NV19 = 5ms # first gets double the time
511
512 Incrementing or decrementing a nice value has wildly different effects depending on what value you start at
513
514 3. Absolute timeslices must be a thing the kernel can measure
515 Im many OSs this means some multiple of the timmer tick which varies widely by machine
516 10ms on one might be 1ms on another
517 # TODO - reread this section after ch 11
518
519 Solution: Mapping nice values to timeslices using a measurement decoupled from the timer tick
520
521 4. Interactive process wake-up
522 Often, you want to give a proc a temporary boost in priority so it can run in spite of an expired time slice
523 Doing this might open up the OS to a program that tries to game the algorithm for unfair processor time
524
525
526 Real underlying problem is that
527 While it is nice to have a contstant switching rate
528 Fairness becomes variable
529
530 Solution: do away with timeslices completely and assign processes a proportion of the processor
531 Results in a constant fairness but a variable switch rate
532
533### Fair Scheduling
534
535CFS is based on the concept: 'Model process scheduling as if the system had an ideal, perfectly multitasking processor'
536 Perfect Fairness and Perfect Multitasking
537 - Timeslices are infentessimally small
538 - For _any_ span of time, each process would have run the exact same ammount as any other process
539 - With 2 processes, this is like running 2 processes at the same time at 50% power
540
541 Unfortunately we cant actually multitask procs
542 And infinitely small timeslices are unreasonable
543 - b/c switching cost
544 - b/c cache penalty
545
546 # TODO - more often, think about the idea / continuous situation
547
548 CFS actually
549 - Calculates how long a process should run as a fn of the total number of runnable processes
550 - Runs procs round robin - selecting the project that has run the least (is this conflicting? or do allotments of time keep round-robin actually in order)
551 - Nice values _weight_ the proportion of processor a process is to receive
552 - Each process runs for a 'timeslice' proportional to its weight / total weight of all runnable threads
553 - Actual timeslice calculation
554 - Set a target for its approximation of 'infinitely small' scheduling duration in perfect multitasking (known as _targeted latency_)
555 - Note, smaller targets yield better interactivity at the expense of higher switching costs (and worse throughput)
556
557 - TODO - need paper
558 - If targeted latency is 20 ms, with n tasks of the same priority, each task will run for 20 / n miliseconds
559 - since high n will result in high switching costs using this model, CFS imposes a floor on the timeslice assigned to a process
560 - floor is called _minimum granularity_ - default of 1ms
561 - so system is not fair when n is high, because all procs will run for the minimum timeslice
562 - TODO - figure out how the targeted latency changes with high n. I think, large n just means that minimum viable targeted latency is larger than setc:w
563
564 - Nice value imposes weight penalty on procs
565 eg 2 procs might split the 20ms targeted latency 15 and 5
566
567 CFS isnt prefecly fair, it just approximateds perfect multitasking
568 It can place a loer bound on latency of n for n runnable procs on the unfairness
569 # TODO - how would you define latency to someone
570
571The Linux Scheduling Implementation
572------------------------------------
573
574Actual implementation lives in `kernel/sched_fair.c`
575
5764 Components
577
578 - Time Accounting
579 - Process Selection
580 - The Scheduler Entry Point
581 - Sleeping and Waking Up
582
583### Time Accounting
584
585Most unix
586
587 Assign a timeslice
588 Decrement timeslice by the tick period each tick
589 On 0, preempt the proc
590
591#### The Scheduler Entity Structure
592
593Used by CFS to keep track of process accounting
594Embedded in the _process descriptor_ `task_struct`
595 member var `se`
596
597#### The Virtual Runtime
598
599`vruntime`
600 - stores the _virtual runtime_ of a proc
601 - time spent running normalized by the number of runnable procs
602 - unit: nanoseconds (decoupled from the timer tick)
603 - on a perfect multitasking system, all tasks of same priority would always have the same virtual runtime
604 - used to determine how long a proc has run and how much longer it ought to run
605
606`update/curr(struct cfs_rq *cfs_rq)` manages the accounting
607
608### Process Selection
609
610Run the process with the lowest vruntime
611CFS uses a red-black tree to manage list of runnable procs
612Note - tree is not actually traversed in finding the left-most node b/c it is cached
613
614### The Scheduler Entry Point
615
616`schedule()`
617 - entry point for rest of the system
618 - system command, in turn cals `deactivate_task()` which removes the task from the runqueue
619 - generic wrt the scheduler classes
620 - find the highest priority scheduler clas with runnable proc, asks it what to run next
621 - invokes pick_next_task()
622
623 - CFS is the scheduler for normal processes
624
625
626### Sleeping and Waking Up
627
628Special state that signals to the scheduler that a task does not wish to be run
629When sleeping, a task is _always_ waiting for an event
630Events include
631 - specified amount of time
632 - more data from a file I/O (common)
633 - some other hardware event
634
635A task may be forced into sleep if it requests tries to obtain a contended semaphore
636
637Two states associated with sleeping
638 `TASK_INTERRUPTIBLE`
639 - respond to signals
640 - _spurious wake up_ -wake-up not caused by the occurrence of the event.. so check and handle signals
641 `TASK_UNINTERRUPTIBLE` - ignores signals
642 both sit on a wait queue waiting for an event
643
644#### Wait Queues
645
646Can be declared statically or dynamically
647Processes put themselves on wait queues and declare themselves not runnable
648When the event associated with the wait queue occurs, the procs on the queue are awakened
649Race conditions can arise when sleeping and waking are incorrectly implemented
650 eg. dont go to sleep aftr the condition becomes true
651
652There is a prescribed approach to putting a process on the wait queue - use it should you ever need to (p 61)
653
654#### Waking Up
655
656`wake_up()`
657 - marks TASK_RUNNING, enqueues it
658 - sets need_resched if the awakened task's priority is higher than the priority of the current task
659 - code that causes the event to occur typically walls wake_up() on everything in its queue waiting for the data
660
661When a task awakens, it is not safe to assume the event has occurred. It may have been a spurrious wakeup - need to check event
662
663
664Preemption and Context Switching
665-------------------------------
666
667`context_switch()`
668 - switches from one runnable task to another
669 - called by schedule()
670
671 2 jobs
672 - switch the virtual memory mapping from that of the old to the new (via `switch_mm`)
673 - switch processor state from the previous proc's to the current's
674 - save and restore stack info / processor registers / arch specifics
675 - via `switch_to()`
676
677Kernel must know when to call schedule
678 cant trust user-space programs to do it
679 `need_resched` flag used to signify needed reschedule
680 - by `scheduler_tick()`
681 - by `try_to_wake_up()` when woke proc is higher prior
682 has some accessor methods
683
684 user preemption - preemption when kernel is about to return to user-space
685 - from system call
686 - from interrupt handler
687
688 kernel preemption - no need to wait for kernel code running in user context to return, can reschedule any time it is safe to do so
689 Not safe
690 - when a lock is held (lock count is non-0)
691 - can do this because the kernel is SMP-safe
692
693 can occur
694 - when an interrupt handler exits, before returning to kernel-space
695 - whent kernel code becomes preemptible again
696 - if a task in the kernel explicitly calls `schedule()`
697 - if a task in the kernel blocks (which results in a call to `schedule)`)
698
699Real-Time Scheduling Policies
700-------------------------
701
702Two real-time scheduling policies
703 `SCHED_FIFO`
704 first in, first out - without timeslices
705 always scheduled over `SCHED_NORMAL`
706 runs until it explicitly blocks or yields
707 no timeslice, can run indefinitely
708 only higher priority real-time proc can preempt
709 two or more at the same priority run round-robin
710 `SCHED_RR`
711 same as above, except with a predetermined timeslice
712 (`SCHED_NORMAL` is non-realtime policy )
713
714 Managed by a specia real-time scheduler in `kernel/sched_rt.c`
715
716 'soft real-time' - kernel tries to make timing deadlines but no promises
717 'hard real-time' - guarantees on the capability to schedule real-time tasks
718
719 # TODO - not sure what it means for nice values and rt values to share a priority space, and how we got a range of 100 to 139
720
721Scheduler-Related System Calls
722-------------------------------
723
724Bunch of C library functions which call system calls, almost directly
725can
726 set a procs nice value
727 only root can set a negative nice value
728 set sched policy
729 get sched policy
730 set rt priority
731 get rt priority
732 get max rt pri
733 get min rt pri
734 get proc timeslice
735 set proc processor affinity
736 attempts soft affinity by default?
737 bit-map enforce hard processor affinity
738 get proc processor affinity
739 yield tho processor
740
741# Note, much of sys call code is checking arguments, setup, and cleanup
742
743There is a load balancer that juggles procs around processors when necessary
744
745`sched_yield()` - expires a proc so it wort run for a while, moreso than just moving it to the end of the run array
746
747Process and Thread Scheduling (Guest ch from diff book)
748===============================
749
750Scheduler
751---------
752
753composed of two separate modules
754
755 Process scheduling - decision-making policies to determine the order in which active processes should compete for the use of processors
756 Process dispatcher - binding of selected process to a processor (remove from run-queue, change status, load state)
757
758implementation
759
760 might be called through syscalls, or
761 might be an anonymous process that polls
762 sometimes in a master/slave configuration
763
764_quantum_ - predifined period of time the process is allowed to run
765_priority_ - used to decide 'who next'
766 P = Priority(p) where P is a number and p is a process
767 P is a number
768 sometimes static, given p
769 p is a process
770 divides procs into _priority levels_
771 _ready list_ (RL), struct to hold levels
772
773framework for scheduling
774
775 2 fundamental questions
776 when to schedule - when should the scheduler be active
777 who to schedule - what proc
778 governed by
779 _priority function_ - seen above
780 _arbitration rule_ - satisfies ties
781
782 decision mode
783 when are priorities evaluated
784 non-preemptive
785 run until block or termination
786 preemptive
787 stop the presses, there is more important shit to print
788 _quantum-oriented_ - performed each quantum
789 when other proc priority > current proc
790 ususally more costly than non-preemptive
791
792 priority furnction
793 uses diff attributes from proc and system
794 common attrs
795 service time so far
796 is real time?
797 deadline
798 periodicity
799 external priority
800 memory requirements
801
802 _job scheduling_
803 long term scheduling
804 choose among batch jobs
805 arrival might be arrival in the system
806 departure might be proc termination
807
808 _process scheduling_
809 select among currently ready processes to run next
810 arrival might be change to ready state
811 departure might be change to running or blocked
812
813 _attained service time_ - amount of time since arrival the proc used the CPU. (Often the most important parameter in scheduling)
814 _real time in system_ - total time in system (attained + waiting time)
815
816 attained and real time of a proc make it easy to compute ratio of runtime
817 total service time
818 attained service time at time of departure
819 some systems know this time in advance
820 usually true of repetitive service tasks
821 sometimes predicted based on proc's most recent behavior
822 procs that block frequently will have smaller total service times
823 deadline
824 point in real time by which a task must be completed
825 time-sensative computation, eg weather forecast, wideo transmission
826 shorter deadline ~= higher priority
827 periodicity
828 repetition of a computation
829 sometimes used to model event driven processes
830 especially when events are polled
831 fixed period automatically imposes an implicit deadline
832 external priorities
833 explicitly assigned priorities
834 memory requirements
835 major scheduling criterion in batch operating systems
836 interactive systems, this is a good measure of swapping overhead
837
838Arbitriation Rule
839----------------
840
841Resolves conflicts btwn procs of equal priority
842Could be random choince, could be round robin
843
844Common Schediling Alogrithms
845-------------------------
846
847FIFO
848 arrival time is only criteria
849
850Shortest-Job-First
851 non-preemptive
852 based on total service time
853 priority is inverse of of total service time
854
855Shortest-Remaining-Time
856 preemptive and dynamic version of SJF
857 P = -(total time - attained service time)
858
859Round-Robin
860 uses fixed quantum
861 quantum might be different at different cpu loads
862 linux sets a floor for minimum quantum time
863 avoids lots of context switching at high load
864
865Multi-Level Priority
866 Fixed set of priorities, 1 to n
867 Each process is assigned a priority e
868 P = e
869 e can be changed by authorized system calls
870 usually preemptive
871 at each level - RR if preemptive, else FIFO
872
873Multi-Level Feedback
874 similar to MLP, but
875 processes migrate to lower levels as attained service time increases
876 each level gets a tP max, if a process exceeds that value, its priority is decreased a level
877 There is a formula (P = n - floor(lg2(a/T + 1)))
878 n - the number of priority levels
879 T - max time at highest level
880
881Rate Monotonic
882 Real time systems
883 procs and threads are often _periodic_
884 computation must be done before the start of the next service time
885 Preemptive policy that dispatches according to period length
886 the shorter the period, the higher the priority
887
888Earliest-Deadline-First
889 preemptive and dynamic
890 highest priority assigned to the process with the smallest remaining time until its deadline
891 assumes all processes are periodic
892 assumes deadline is equal to the end of the current period
893 probably not great for humans? or, maybe is good for some humans
894 P = -(d - r%d)
895 r - time proc entered the system
896 d - period
897 r / d - number of completed periods
898 r % d - time already expired fraction of the current period
899
900 (Table is pretty cool)
901
902Comparison of Methods
903---------------------
904
905FIFO, SJF, SRT - developed primarily for batch processing system
906If total service times are known (or can be predicted)
907 SJF or SRT are usually preferrable to FIFO
908 b/c both SJF nd SRT favor shorter comp time over long
909 users want fast service for short tasks
910 total time required
911 independent of process order
912 avg turnaround time
913 can be changed with diff process orders
914 one of the more important metrics used to compare sched algos
915 # NOTE - it seems like it would be easy to show change in process attributes for different scheduling algorithms
916 # probably in a visually appealing way
917
918_response time_
919 important in time share systems
920 if important
921 implies a preemptive algorithm
922 good algos
923 round robin
924 responsiveness depends on q
925 q -> inf, rr becomes fifo
926 q -> 0, rr is dominated by context switching
927 multi-level feedback
928
929 MLF
930 IO bound procs tend to remain high priority
931 batch jobs tend towards the bottom of the list
932
933Example Schedulers
934----------------
935
936VAX/VMS
937 15 priorities for real-time, 15 for regulars
938 Realtime uses multi-level scheme (without feedback)
939 Regural processes
940 have standard
941 adjusted with other events in the system
942 eg. read completion will ++ a proc priority
943 reaching the end of runtime will -- proc priority
944
945Windows 2000
946 similar to above except threads are scheduled rather than procs
947
948# NOTE - scheduling threads could use the process (tgid struct) to keep track of the attained time - or some aggregate time
949
950Minix
951 Multi-level queues
952 _task_ (kernel stuffs),
953 _server_, (memory, file, network management)
954 and _user_ levels
955 RR
956
957Linux
958 no queues of threads/procs
959
960 sort by _goodness_
961
962 base and current goodness is tied to the quantum
963 each thread has its own variable-length quantum
964 like a countdown time
965
966 each thread
967 gets a base quantum (bq)
968 gets a remaining quantum (rq)
969 current goodness (g)
970 if (rq == 0) g = 0 # alloted quantum has been consumed
971 if (rq > 0) g = bq + rq
972
973 epochs
974 division of scheduler time
975 end when no threads can run
976
977 all threads (or 'exahsted quantums',
978 'blocked')
979
980 reset with formula `rq = bq + (rq / 2)`
981 each thread gets its base quantum plus half of its remaining
982 naturally favors I/O - bound threads
983
984 realtime threads
985 always executed before normal threads
986
987 can be scheduled (or RR,
988 FIFO)
989
990 helps to know if deadline will be met _before_ execution
991
992 _schedule_ - an assignment of proc to process
993 _feasible schedule_ - iff all deadlines are satisfied
994 _optimal scheduling method_ - resulting schedule meets all deadlines whenever a feasible schedule exists
995
996 periodic processes
997 utilize ti/di of the cpu time
998 ti is the total service time for process i for one period
999 di is the period length of process i
1000
1001 overall utilization is
1002 U = sumi=1-n(ti/di)
1003
1004 schedule is feasible if U <= 1
1005
1006 Rate Monotonic
1007 will find optimal for U <~ .7
1008 therefore, it is not optimal
1009
1010 Earliest-Deadline-First
1011 will always fond the optimal solution if there is one
1012
1013Priority Inversion
1014-----------------------
1015
1016Higher priority procs or threads can be delayed or blocked by lower priority ones
1017
1018possible solutions
1019 make critical sections non-preemptable
1020 works well if critical sections are short and few
1021 execute critical sections at the highest priority of any process that _might_ use them
1022 suffers from overkill
1023 leads to other forms of priority inversion
1024 dynamic priority inheritance
1025 when lower priority proc blocks a higher one,
1026 the lower proc is assigned a priority = to the higher until
1027 it exits the critical section.
1028
1029 allows for nested critical sections
1030 blocking times boulded by critical section execution times
1031 can be a cumpulsory requirement in real-time operating systems
1032
1033POSIX focus
1034 user can associate a _ceiling attribute_ with a mutex semaphore
1035 integer specified
1036 when mutex is activated, priority is automatically raised to the value of the ceiling
1037 threads that use this mutex will always run at the same level and will not preempt each other
1038 priority inheritance
1039
1040Windows 2000 focus
1041 every second, scan all ready threads
1042 any that have been idle for more than 3 seconds
1043 bost priority to max
1044 extend quantum by 2x
1045 no thread will be postponed indefinitely due to higher priority threads
1046
1047Multiprocessor and Distributed Scheduling
1048====================
1049
1050Two principal approaches to scheduling procs and threads on multicomputers
1051
1052 Use a single scheduler
1053 all CPUs are in same resource pool
1054 any proc can be run on any processor
1055
1056 Use multiple schedulers
1057 machines are scheduled separately
1058 often a choice for non-uniform multiprocessors
1059 different CPUs have different characteristics and functions
1060 eg. special machines fro I/O, filing, data acquisition, fast Fourier transforms, matrix computations
1061 users and apps tend to have greater control over performance
1062
1063 Case: _the Mach Scheduler_
1064 each machine set has a global ready list of schedulable threads
1065 dispatching
1066 select highest priority thread from the local queue
1067 when empty, select highest priority thread from global list
1068 execute idle thread when both lists are empty
1069
1070 Case: _Windows 2000_
1071 affinity scheduling
1072 goal: keep a thread running on the same processor (if possible)
1073 make use of caching
1074 each thread is associated with two integers
1075 ideal processor
1076 last processor
1077 when thread is ready
1078 prefer running on
1079 1. the ideal processor
1080 2. the last processor
1081 3. the processor currently runnng the scheduler
1082 4. any other processor
1083 idle processor looks for proc to run
1084 1. last thread to run o the processor
1085 2. the thread for which this is the ideal processor
1086 3. then whatever the top priority processor is
1087
1088 Distributed systems
1089 normally have separate schedulers at each site (cluster)
1090 processes usually preallocated to clusters
1091 communication costs time
1092 costs message traffic
1093 applications have threads that utilize a shared address space
1094 distributed shared memory and migrating threads
1095 practical ideas
1096 realization is still slow
1097 often have functional distribution
1098 leads to different schedulers
1099 a node might specialize
1100 focus on email - cause node is an exit node
1101 printing (node has access to printer), etc
1102 RTB requires being really fricken close to exchanges, need to fill request fast
1103
1104 Rate monotonic - preemptive policy that disatches according to period length
1105 shorter the period, the higher the priority
1106
1107 Earliest-Deadine-First (EDF) - preemptive and dynamic scheme
1108 usually designed for real-time applications
1109
1110 Neither of the above two are optimal for multiprocessors
1111 often satisfactory heuristics though
1112 feasible schedules produced, when they exist and when machines are not under heavy load
1113
1114 preallocation of procs is most common because of the complexit of trying to meet real-time constraints
1115
1116
1117
1118
1119
1120Linux Scheduler
1121
1122 - time compelxity depends on number of priorities (queues)
1123 - time compelxity does not depend on the number of processes
1124
1125Calculating Timeslices
1126
1127 Quantum = 140 - (static priority) * 20 if SP < 120
1128 Quantum = 140 - (static priority) * 5 if SP >= 120
1129
1130 static priority - think nice & real-time stuffs
1131
1132 note higher priority process get _longer_ quanta
1133 important process should run longer
1134
1135 dynamic priority
1136 calculate from static priority and avg sleep time
1137 record time sleeping (up to a max value)
1138 when the process is running, decrease value each timer tick
1139 [0, 10] - rough estimate of % time sleeping recently
1140 0 hurts priority by 5
1141 5 is neutral
1142 10 helps priority by 5
1143
1144 DP = max(100, min(SP-bonus + 5, 139))
1145 _interactive_ - if bonus - 5 >= S/4 - 28
1146 low-priority processes have a hard time becoming interactive
1147 default priority process becomes interactive when its sleep time is greater than 700ms
1148
1149Using Quanta
1150 each tick decreases the quantum of _current_
1151 process gets prempted when clock hits 0
1152 if non-interactive -> send to expired list
1153 if interactive -> send to end of current queue (scheduled again)
1154 but running will decrease bonus (along with priority)
1155
1156Avoiding Indefinite Overtaking
1157 remember those 140 queues (_active_ and _expired_)
1158 only run procs from active queues (put on expired when quanta == 0)
1159 swap active and expired queues after running through all of them
1160 pointers to current arrays
1161
1162 two arrays
1163 - avoids the need for traditional aging
1164 - why is aging bad? -> it's O(n) at each clock tick
1165 - ergo, not required for peoples scheduling
1166
1167Many OSs iterate over procs to update priorities
1168Linux is more efficient
1169
1170 - procs are touched on start and on stop only
1171 - recalculate priorities, bonuses, quanta, and interactive status
1172 - never loop over all procs!
1173
1174Locking Runqueues
1175 Sometimes for queue rebalancing, kernel locks queue
1176 in order to move procs
1177
1178Real-time scheduling
1179
1180 soft real-time scheduling
1181 static priority [0, 99] are real-time
1182 FCFS & RR
1183
1184Sleeping and Waking
1185
1186 - proc needs to wait for events
1187 - proc added to wait queue
1188 - wakeups can happen too soon - need to check args and maybe re-sleep
1189
1190 - you dont wake a process
1191 - you DO wake a wait queue
1192
1193System calls
1194
1195 `nice()` - lower a process' static priority
1196 `getpriority()/setpriority()` - change priorities of a process group
1197 `sched_getscheduler()/sched_setscheduler()`
1198 set scheduling policy and params
1199 and others that start with `sched_` (see with man -k)
1200 `scheduler_tick()`
1201 called each timer tick to update quanta
1202 `try_to_wakeup()`
1203 attempt to wake a proc
1204 put on run queue
1205 rebalance loads
1206 `recalc_task_prio()`
1207 update average sleep time and dynamic priority
1208 `schedule()`
1209 pick the next process to run
1210 `rebalance_tick()`
1211 check if load-balancing is needed
1212
1213Fair Share Scheduling
1214 would need to
1215 add new scheduler type
1216
1217Two basic functions
1218 time of day - a service provided to apps
1219 interval timers - something should happen in n ms from now
1220
1221 _Real-Time clock_
1222 tracks time and date
1223
1224 can interrupt at a certain rate
1225 can interrupt at a certain time
1226
1227 only used by Linux for time of day
1228
1229 _programmable interval timer_
1230 generates periodic interrupts
1231 usually based on HZ
1232 some other special , less common timers
1233
1234 Things executed on timer ticks
1235 keep track of time
1236 invoke dynamic timer routines
1237 call `scheduler_tick()`
1238 system uses best timer available
1239 `jiffies`
1240 incremented each tick
1241 roughly the number of HZ since sys boot
1242 32 bit counter - wraps around in ~ 50 days
1243
1244 Time of Day
1245 stored in xtime (`struct timespec`)
1246 incremented once per tick
1247 apparent tick rate can be adjusted slightly see `adjtimex()`
1248
1249 Kernel Timers
1250 Dynamic timers
1251 - call routine after a praticular interval
1252 - specify an interval, subroutine to call, and a param to pass subroutine
1253 - param differentiate different instantiations of the same timer
1254 - timers can be cancelled
1255 Delay loops
1256 - tight spin loops for very short delays (micro seconds or nano seconds)
1257 - nothing else can use CPU during that time (except via interrupt)
1258 - for when dynamic timers are too much overhead
1259
1260 System Calls
1261 `time()` and `gettimeofday()`
1262 `adjtimex()`
1263 tweaks apparent clock rate (even the best crystals drift)
1264 `setitimer()` and `alarm()`
1265 interval timers for applications
1266 user-mode interval timers
1267 similar to kernel dynamic timers
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277System Calls
1278=====================
1279
1280Allow user-space apps to
1281 - access hardware
1282 - create new procs
1283 - communicate with existing ones
1284 - request os resources
1285
1286Layer between user programs and hardware
1287 3 purposes
1288 - abstracts hardware eg. read/write files dont care what media you are on
1289 - security / stability
1290 - virtualized system provided to the process
1291
1292Without controlled access of sys resources
1293 - couldnt multitask
1294 - wouldnt be able to have virtual memory
1295
1296Legal entry points to the kernel
1297 - sys calls
1298 - traps
1299 - exceptions
1300
1301Even device files, or files in /proc, are accessed via system calls
1302
1303APIs, POSIX, and the C Library
1304-------------------------------
1305
1306User space programs usually programmed against an API implemented in use-space, not directly to sys calls
1307Can create defferent APIs from building blocks provided by system calls
1308
1309POSIX - series of standards from the IEEE (eye-triple-E)
1310 Linux strives to be 'POSIX' and 'SUSv3'-compliant
1311 A very common api is based on the POSIX standard
1312
1313A meme related to interfaces in Unix is 'Provide mechanism, not policy'
1314
1315Syscalls
1316---------
1317
1318Typically accessed by function calls in the C library
1319System calls also provide a return value of type `long` that signifies success or error
1320 usually negative value denotes an error
1321 usually 0 is a sign of success
1322 `errno` - holds a special error code of the last error
1323 `perror()` - used to print human-readable error code
1324
1325tgid - is the thread-group id. This is == pid for normal processes, while for threads is the same for all threads of the same group
1326
1327`asmlinkage`
1328 - only look on the stack for the fns arguments
1329 - required for all syscall
1330
1331in kernel, all syscalls are prefixed with `sys_`
1332
1333### System Call Numbers
1334
1335Unique # used to reference a specific system call
1336User-space process identifies calls by #, not name
1337#, once assigned, cannot change - else compiled apps will break
1338
1339### System Call Performance
1340
1341Faster than many other os's
1342Cause
1343 - fast context switching
1344 - streamilened enter/exit
1345 - simple call handler
1346
1347System Call Handler
1348-------------------
1349
1350Kernel fns exist in a protected memory space. User-space programs cannot call them directly
1351
1352Method - use an interrupt: incur an exception and the system will switch to kernel mode, executing the exception handler (in this case, the syscall handler)
1353
1354# TODO - difference between throwing an exception and 'trapping into the kernel'
1355
1356Some processors have a special sysenter feature
1357
1358### Denoting the Correct System Call
1359
1360Architecture dependent, on x86, user-space app sets the eax register before causing the trap into the kernel
1361
1362### Parameter passing
1363
1364Sent to the kernel on registers `ebx, ecx, edx, esi, and edi`
1365Return value is also sent via register
1366 on x86, the `eax` register is used
1367
1368System Call Implementation
1369----------------------------
1370
1371Must first define its purpose - exactly one
1372What are the new system call's arguments, return value, err codes
1373Should have a clean and simple interface
1374Small # args possible
1375Remember, semantics and behaviour are important, they must not change
1376 - Consider how the function use might change over time
1377 - Can your method be changed while maintaining compatability?
1378 - Will bugs be fixable?
1379 - Are you needlessly limiting the fn in some way?
1380 - Purpose remains the same, but uses may change
1381 - Dont make architectual changes
1382
1383### Verifying the Params
1384
1385Thourough checking is in order - security is imperrative
1386Check valid and legal, but also correct
1387Cant trust user-space procs
1388Always check validity of pointers!!!
1389 - must point to user-space memory
1390 - must point to memory in the process's address space
1391 - if reading, memory must be marked readable
1392 - if writing, memory must be marked writable
1393 - if executing, memory must be marked executable
1394 there are helper fns to do this
1395
1396System Call Context
1397-----------------
1398
1399In proc context
1400 - Kernel can sleep
1401 Makes available most kernel functionality
1402 - is fully preemptible
1403 Must make sure call is reentrant
1404 otherwise trouble occurs when another higher priority proc makes same syscall in the middle of a lower prior proc
1405
1406### Final Steps in Binding a System Call
1407
1408Add entry to the end of the syscall table
1409 - must be done for each arch
1410For each architecture, define the call number in `asm/unistd.h`
1411
1412Compile the syscall into the kernel image (as opposed to compiling as a module)
1413
1414# Note - interrupt handlers cannot sleep, and are therefore much more limited in what they can do than syscalls running in proc context
1415
1416Since new sys calls will not be in the C libs, you can wrap access with macros. This will handle setting up register contents and issuing the trap instructions. `_syscalln()` where n is between 0 and 6. (# of params)
1417
1418_see this section for use of your new syscall_
1419
1420### Option of a New Syscall
1421
1422#### Pros
1423
1424 Simple to implement, easy to use
1425 Fast performance on Linux
1426
1427#### Cons
1428
1429 Requires a syscall number, which needs to be officially assigned to you
1430 Written in stone, interface cannot change
1431 Must be explicitly supported by each architecture
1432 Not easily used from scripts
1433 Cannot be accessed directly from filesystem
1434 Hard to maintain outsize of the master kernel tree
1435 Overkill for simple info exchanges
1436
1437#### Alternatives
1438
1439 Implement a device node and `read()` and `write()` to it
1440 use `ioctl()` to manipulate specific settings or retrieve specific info
1441 Certain interfaces, such as semaphores, can be represented as file descriptors and manipulated as such
1442 Add the information as a file to appropriate location in sysfs
1443
1444# TODO - what is sysfs?
1445# Note: you can get a proc's processor afinity in linux with `sched_getaffinity`. In a group context, a warm cache of the processor is relevant. If someone is familiar with offer caching code, you probably want them to continue rather than ramping-up someone else.
1446
1447# Note: for humans: loading something onto disk takes time (learning something for the first time), disk to memory is faster (recall of past), recent tasks is faster still
1448
1449Other
1450------
1451
1452# note - preempt notifiers - let something know that a process has been preempted
1453# TODO what is - group leader
1454# TODO what is - slacktime
1455
1456Kernel Data Structures
1457========================
1458
1459Dont roll your own
1460Not inclusive, just the basics in this book
1461
1462 - linked lists
1463 - queues
1464 - maps
1465 - binary trees
1466
1467
1468Linked Lists
1469-----------------
1470
1471Allows storage of variable number of elements
1472Elements created at differernt times
1473 - must be variable in length
1474 - may occupy discontiguous regions in mem
1475
1476Single linked, double linked, or circular linked
1477Linux Kernel LL is unique, but pretty much a circular, doubly linked list
1478
1479### Moving Through a Linked List
1480
1481Linear movement
1482
1483Bad at
1484 Random access
1485
1486Good at
1487 Dynamic addition / removal O(1) ftw
1488 Iterating
1489
1490### In Linux Kernel
1491
1492Rather than including pointers in the data struct, include a pointer to a LL node instead
1493`linux/list.h`
1494Reference to list_head in the data struct allows several macros to be used to `list_add()` or `container_of()` which take list_head as arguments
1495
1496Since the offeset of a node pointer in a data struct is set at compile time, it is easy to get the containing structure of the list
1497 Presumably `const typeof( ... )` will get the type of the struct in a generic way, so `container_of()` doesnt need to know anything about it
1498
1499Be sure it is embedded in data_struct, otherwise macros arent helpful
1500Need to init the list head on creation
1501
1502Also, there are some safe(er) methodes
1503Also, also, you may need to synchronize for exclusive list access
1504
1505Queues
1506-----------------
1507
1508Producers and consumers
1509see `kernel/kfifo.c` and `linux/kfifo.h`
1510
1511Queues are one page-sized by default
1512
1513Queues leave it up to the user to say
1514 - How many bytes to copy in
1515 - How many bytes to copy out
1516
1517If a queue is nearly full, only a partial add will be done
1518If a queue is nearly empty, only a partial read will be done
1519
1520Maps
1521------------
1522
1523Aka associative array
1524Keys to values
1525
1526Hashtables are a type of map - but not all maps are hashtables
1527Trees can be used as well (self-balancing)
1528
1529Hash
1530 - better average-case complexity
1531
1532Trees
1533 - better worst-case complexity
1534 - can also maintain a sorted order
1535 - can use any type of key, so long as it can define the <= operator
1536
1537### In Linux
1538
1539Map is used to map a UID to a pointer
1540Will also generate a UID for you
1541`idr` maps user-space UIDs to their kernel data structures
1542
1543Need to preallocate a UID before getting a new one, cause memory and locking are hard
1544
1545
1546Binary Trees
1547----------------
1548
1549Math says it is an 'acyclic, connected, directed graph' where each node has 0 or more outgoing edges
1550Binary tree is a tree with no more than 4 outgoing edges per node
1551
1552_binary search tree (BST)_ - specific ordering on nodes
1553
1554 left of root is only nodes < root
1555 right of root is only nodes > root
1556 all subtrees are also binary search trees
1557
1558Pros
1559 fast search
1560 fast ordered traversal
1561
1562### Self-balancing BST
1563
1564Depth of all leaves differs by at most 1
1565In other words, height is managed
1566
1567#### Red-Black Tree
1568
1569 type of self-balancing bst
1570 binary tree of choice in linux
1571
1572 6 properties are enforced
1573 Ensures that the deepest leaf has a depth of no more than double that of the shallowest leaf
1574 Tree is always semi-balanced
1575
1576 B
1577 / \
1578 R B
1579 / \ / \
1580 B nilnil B
1581
1582 It does this by rotating shit thats unbalanced, but dont worry about it unless you are an undergrad compsci student, which im not (anymore)
1583
1584 `rbtree` - `lib/rbtree.c` and `linux/rbtree.h`
1585 inserts are always logarithmic
1586
1587What Data Structure to Use, When
1588--------------------------------
1589
1590What is primary access method?
1591
1592LL
1593 if iterating
1594 when performance is not important
1595 when interfacing with other LL consuming code
1596
1597Queues
1598 if producer / consumer pattern is used
1599 if you know your buffer can hold your data
1600
1601Maps
1602 if UID to obj is needed
1603
1604Rb tree
1605 if storing lots of data is required
1606 fast searching, with efficient in-order traversal
1607 in-memory footprint is not bad
1608
1609Radix tree
1610
1611Algorithmic Complexity
1612----------------------
1613
1614What is the _asymptotic behavior_ of the algorithm
1615
1616Big-oh - upper bound
1617Big-theta - both an upper and lower bound
1618 usually when big-o is dropped, they are really talking abouth the least such big-o (the big theta)
1619
1620Time Complexity - See AoA - Colby CS
1621
1622Interrupts and Interrupt Handlers
1623================================
1624
1625Communicating with hardware is a core responsibility
1626Aint got no time to wait for hardware
1627
1628Rather than polling these devices, the responsibility is on the HW to interrupt the processor when it wants attension
1629
1630Polling - check periodically
1631Interrupt - send a signal to the processor
1632Interrupt handlers - fn to handle interrupt
1633
1634HW device interrupts
1635 async w.r.t. processor clock
1636 aggergated by multiplexes
1637 directly connected to the CPU
1638
1639 have a unique value - for differentiation
1640 aka interrupt request (IRQ) lines
1641
1642 IRQ 0 on a classic PC is the timer interrupt
1643 IRQ 1 on a classic PC is the keyboard
1644
1645 Not always dynamically assigned
1646 PCI bus dynamically generates values
1647
1648
1649Exceptions
1650 - synchronous ~interrupts~
1651 - generated by the processor
1652 - from software
1653
1654Interrupts
1655 - asynchronous interrupts
1656 - generated by hardware
1657
1658Interrupt Handlers
1659------------------
1660
1661aka interrupt service routine (ISR)
1662An associated handler for every device
1663
1664
1665
1666Function
1667 One per device
1668 part of the _driver_
1669 normal C functions
1670 run in _interrupt context_
1671 aka _attomic context_
1672 code cannot block
1673 must run quickly
1674 acknowledge hardware, at a minimum
1675
1676Top Halves vs Bottom Halves
1677---------------------------
1678
1679To balance large amount of work with response speed
1680
1681### Tap Halve
1682
1683 - only the time critical stuff
1684
1685### Bottom Halve
1686
1687 - run at more convenient time
1688
1689
1690Network card example
1691
1692 - card has very little memory
1693 - dont want buffer overruns
1694
1695Registering an Interrupt Handler
1696--------------------------------
1697
1698`request_irq()` in `linux/interrupt.h`
1699One driver for every device
1700One interrupt handler per driver
1701
1702`request_irq()`
1703 params
1704 int irq
1705 the interrupt number
1706 usually dynamically allocated
1707 irq_handler_t handler
1708 pointer to actual handler fn
1709 unsigned long flags
1710 bitmask of one or more of the flags
1711 IRQF_DISABLED
1712 usually poor form to use
1713 handle fn blocks other interrupts from occurring
1714 IRQF_SAMPLE_RANDOM
1715 use as source of entropy
1716 helps with random number generation
1717 obv. dont set for predictable device interrupts
1718 IRQF_TIMER
1719 this handler procsses interrupts for the system timer
1720 IRQF_SHARED
1721 interrupt line can be shared among multiple interrupt handlers
1722 conts char *name
1723 ascii text name of device
1724 used by `/proc/irq` and `/proc/interrupts`
1725 void *dev
1726 used when lines are shared
1727 provide a unique cookie for later identification on removal
1728 the way the kernel tells which handler to remove for shared lines
1729 common to use the driver's device structure
1730
1731 can sleep
1732 so no calling in interrupt context
1733 cause somewhere `kmalloc()` is called
1734
1735 careful to initialize hardware fully before registering handler
1736
1737 `void free_irq(unsigned int irq, void *dev)`
1738 disconnects line iff (not shared || last registered)
1739 must be called from process context
1740
1741Unless your handler is old and crusty
1742 good chance you will need to share
1743
1744Writing an Interrupt Handler
1745-----------------------
1746
1747`static irqreturn_t intr_handler(int irq, void *dev)`
1748 params
1749 int irq
1750 line #
1751 void *dev
1752 same as passed to `request_irq()`
1753 typically the `device` structure
1754 b/c unique to each device
1755 potentially useful to have within the handler
1756
1757 return
1758 IRQ_NONE
1759 handle's device was not the originator
1760 IRQ_HANDLED
1761 handler correctly invoked
1762 IRQ_RETVAL(val)
1763 macro for returning one of the above two based on val
1764
1765 used to determine if device is issuing _spurious interrupts_
1766 spurious interrupts - unrequested
1767
1768Interrupt handlers in Linux need not be reentrant
1769 Processors do not receive inturrupts on the same line while executing a handler for tat line
1770 Avoids dealing with nested interrupts
1771 Code can be preempted, though, by interrupts on other lines
1772
1773### Shared Handlers
1774
1775- IRQF_SHORED flag must be set
1776- dev arg must be unique
1777- Interrupt handler must be able to distinguish what device actually generated an interrupt
1778 hardware capability must exist
1779
1780Invoked sequentially
1781Handler should quickly exit if its device was not the generator of the interrupt
1782
1783Real-time clock (RTC)
1784 `drivers/char/rtc.c`
1785 separate from the system timer
1786 sets the system clock
1787 provides an alarm
1788 supplys a periodic timer
1789
1790 driver's init code registers the handler
1791
1792Interrupt Context
1793-----------------
1794
1795Not associated with a running process
1796 `current` macro is not relevant
1797 cannot sleep
1798 other functions are also not relevant
1799
1800Time-critical
1801 can wait-loop, but dont
1802 push as much as possible into the bottom half
1803
1804Stack location varies
1805Handler should not care what stack setup is in use
1806Always use the absolute minimum amount of stack space
1807
1808Processor jumps to a unique location for each interrupt line
1809 executes code at that location
1810
1811### `/proc/interrupts`
1812
1813stats realated to interrupts
1814 line #
1815 # of times executed
1816 handling controller (eg `XT-PIC`)
1817 name
1818
1819_procfs_
1820 a virtual file system
1821 in kernel memory
1822 mounted at `/proc`
1823
1824 reading / writing files
1825 invokes kernel functions
1826 seems like actually reading/writing files (but are just fns)
1827
1828`XT-PIC`
1829 std PC programmable interrupt controller
1830
1831Interrupt Control
1832-----------------
1833
1834Can enable/disable
1835 a line for the whole machine
1836 aka _masking out_
1837 not used as often now since, increasingly, lines are shared
1838 the interrupt system on a processor
1839 `local_irq_disable()` && `local_irq_enable()`
1840 or safer: `local_irq_save(flags)` && `loal_irq_restore(flags)`
1841
1842Reasons
1843 need synchronization (disable interrupt preemption)
1844 kernel will not be preempted
1845
1846Does not prevent concurrent access from another processor
1847 need a lock for that
1848
1849No `cli()` (global disable interrupts)
1850 means all synchronization must be specific and narrow
1851 results in faster performance
1852
1853### Status of the Interrupt System
1854
1855`in_interrupt()`
1856 - nonzero if kernel is executing a handler
1857 - nonzero if kernel is executing a bottom half
1858 - if 0, kernel is in process context
1859
1860`in_irq()`
1861 - nonzero if kernel is executing a handler
1862
1863
1864Bottom Halves and Deferring Work
1865==========================
1866
1867Top half is not enough
1868
1869Why need for fast
1870
1871 - TH interrupts all the code
1872 - TH disables at least a line, if not all HW comms
1873 - Timing critical, eg. small HW buffers
1874 - Cannot block
1875
1876There is a need to do less critical work later.
1877
1878Bottom Halves
1879----------------
1880
1881Do most work here. All but the critical.
1882You should probably process data copied in the TH, though.
1883
1884Tips for dividing work:
1885
1886 perform in handler
1887 - perform in handler
1888 - HW related
1889 - ensure another interrupt doesnt happen
1890
1891 perform in bottom half
1892 - all other
1893
1894### Several Mechanisms
1895
1896 First approach - a static set of handlers
1897 Second approach - task queues that a driver could append to
1898 Third approach
1899
1900 Softirqs
1901 - statically definded - compile-time
1902 - can run simultaneously on any processor
1903 - two of the same can run concurrently
1904 (require more care)
1905
1906 Tasklets
1907 - dynamically defined
1908 - can run simultaneously on any processor
1909 - two of the same can _NOT_ run concurrently
1910 - build on softirqs
1911
1912 Task Queue replaced with Work Queue
1913 - queue work for later
1914 - runs jobs in process context
1915
1916 (kernel timers)
1917 - after specific time, rather than 'any time but now'
1918
1919Softirqs
1920------------
1921
1922Rarely used directly. Tasklets are much more comon form.
1923`kernel/softirq.c`
1924Usually reserved for the most timing-critical / improtant bottom-half prcessing
1925Currently, only used by networking and block subsystems. But also, tasklets and kernel timers are built on top.
1926Needed for scalability. If you do not need to scale to infinity processors, consider a tasklet
1927Used for high frequency or highly threaded use.
1928
1929Represented by the `saftirq_action` structure (see `linux/interrupt.h`)
1930
1931Each is registered in a 32-entry array
1932 only nine exist now
1933
1934A softirq never preempts another softirq
1935But it can run on a differnt processor
1936Only interrupt handlers can preempt
1937
1938Must mark the softirq before it will run
1939 aka _raising the softirq_
1940 usually done by the interrupt handler
1941
1942 check for pending occurs
1943 in return from HW interrupt code path
1944 in the `ksoftirqd` kernel thread
1945 any code w/ explicit checks
1946 eg. networking subsystem
1947
1948### Use
1949
1950index
1951 must be assigned (`linux/interrupt.h`)
1952 used for priority - lower executes before higher
1953
1954handler must be registered at run-time
1955 `open_softirq()`
1956 eg `open_softirq(NET_TX_SOFTIRQ, net_tx_action)`
1957
1958To avoid need to lock, try and only use per-processor data
1959
1960After installed and init'd
1961 can be raised using `raise_softirq(NET_TX_SOFTIRQ)`
1962
1963
1964Tasklets
1965-----------
1966
1967Called by softirq logic
1968 `HI_SOFTIRQ` - higher priority tasklets
1969 `TASKLET_SOFTIRQ` - regular
1970
1971Represented by the tasklet structure
1972 `struct tasklet_struct`
1973 `unsigned long state`
1974 0, `TASKLET_STATE_SCHED`, or `TASKLET_STATE_RUN`
1975 `count`
1976 tasklet can only run if non-zero
1977 `func`
1978 called the same way `action` is in softirqs
1979
1980### Scheduling tasklets
1981
1982Multiplexed on two softirqs
1983
1984_sheduled tasklets_
1985 - equivallent of raised softirqs
1986 - stored two per processor
1987 linked lists
1988 `tasklet_vec` - regular tasklets
1989 `tasklet_hi_vec` - high priority
1990 - cannot be scheduled if already scheduled
1991
1992System disables interrupts while tasklets are being sched'd
1993Raises the `TASKLET_SOFTIRQ` or `HI_SOFTIRQ` which will call
1994 `tasklet_action()` and `tasklet_hi_action()` respectively
1995
1996 Loop over each pending tasklet in the retrieved list
1997 if already running on another processor
1998 skip it
1999 else
2000 mark it as being run, and run it
2001
2002### Using Tasklets
2003
2004#### Declare your tasklet
2005
2006 statically or dynamically
2007
2008 statically - use macros
2009 use `DECLARE_TASKLET`
2010 or `DECLARE_TASKLET_DISABLED` (count is initially 1, not 0)
2011
2012 both create `tasklet_struct`
2013
2014 dynamically create `tasklet_struct` and call `tasklet_init`
2015
2016#### Write your handler
2017
2018`tasklet_handler` passed an unsigned long data
2019Writing
2020 Cannot sleep
2021 no semaphores
2022 no blocking functions
2023 Interrupts are enabled
2024 careful if you share data with one
2025
2026#### Scheduling Your Tasklet
2027
2028Call `tasklet_schedule` with a pointer to your `tasklet_struct`
2029If already scheduled, it only runs once
2030If already running (eg on another processor), tasklet is rescheduled
2031As an optimization, a tasklet always runs on the processor that scheduled it (hopefully making better use of cache)
2032
2033Need to enable the tasklet if it is created disabled
2034Disabled tasklets are just skipped
2035
2036You can kill a pending tasklet with `tasklet_kill` (sleeps)
2037Helpful when a tasklet frequently reschedules itself
2038
2039#### ksoftirqd
2040
2041Per processor kernel threads
2042Help process softirqs and tasklets
2043
2044Grew out of problem with heavy interrupt load
2045 esp. with softirqs that rescheduled themselves
2046 procs would starve for processor time
2047 but softirqs need to be processed
2048
2049Possible solution 1
2050 Perform rescheduled softirqs before returning to procs
2051 Might starve out processes under high load
2052 User space needs to be run periodicly
2053
2054Possible solution 2
2055 Dont handle reactivated softirqs
2056 must wait for the next time softirqs are processed
2057 doesnt take advantage of an idle system
2058 may starve softirqs
2059
2060Actual Solution
2061 Dont immediately process reactivated softirqs
2062 if softirqs are excessive, wake up some special kernel threads
2063 special kernel threads
2064 run at lowest priority
2065 one per processor
2066 named `ksoftirqd/n`
2067 loop over pending softirqs
2068 sleep to yield to other procs
2069 coop nice toooo
2070
2071#### The Old BH Mechanism
2072
2073Old BH
2074 Max 32
2075 Must be statically defined
2076 inaccesible to modules
2077 Dynamicly defined must piggyback off already defined one
2078 Only one handler can execute at a time
2079 (strictly serialized)
2080 Did not scale well to multiple processes
2081 network layer, in particular, suffered
2082 Much like tasklets in other reguards
2083
2084Work Queues
2085-----------------
2086
2087Defer work into a kernel thread
2088 called _worker threads_
2089 default ones named `events/n`
2090 one per processor
2091 must have a strong reason not to use default
2092 eg. processor-intense
2093 performance-critical
2094 pervent starving out other default werk
2095
2096Always run in process context
2097
2098Can sleep - allows
2099 allocation of lots of memory
2100 semaphores to be used
2101 perform block I/O
2102
2103Decision - if you need to sleep, use a work queue
2104 otherwise, tasklet
2105
2106Alternatively - one could spin up a new kernel thread
2107 but this is frowned upon
2108 or punishable..
2109
2110### Data Structures
2111
2112#### Representing the Threads
2113
2114 `workqueue_struct`
2115 one per _type_ of worker thread
2116 interface / abstraction exposed to the rest of the system
2117 holds a `cpu_workqueue_struct` per processor
2118
2119 `cpu_workqueue_struct`
2120
2121#### Representing the Work