OS MT3

information stored on a context switch, including pc, registers, files, etc., most of what is in /proc/pid

ambiguous, typically a process associated with the proper functioning of the system (must a server be running sshd? must a webserver be running apached or equivalent?)

a value from +19 to -20 that can be applied to the static PR value to create a dynamic PR value; 139 (+19) is the least priority job in the system

where a job gets a temporary boost in PR value by the OS (nice is a user-initiated deviation)

when the process running the program enters a phase with different resource needs from earlier

avoid voo-doo constants

scheduler starts with idea of equal or appropriately unequal divisions of latency into timeslices

markov simulation of proportional share scheduler, approximates based on sampling asymptotics

introduces a virtual economy to determine resource division

deterministic version of lottery scheduler, uses different sized deterministic steps to achieve proportions

completely fair scheduler using vruntimes to determine who runs next (note unrelated to FCFS)

actual cpu time weighted nonlinearly by PR (note vrumtime weight called load, unrelated to system runtime queue length avgs)

CFS target time to service all tasks in RR fashion, though it never uses RR to select next!

CFS min time on cpu before checking for preemption by lower vruntime in ready queue

linux cli for viewing/changing system parameters, esp kernel as root

complex O(nlogn) priority queue for O(logn) or O(1) selection of lowest vruntime

the default text-based system monitor in linux, H for thread-view, f to select fields, V for parent-view, d to change update time

the static priority shown per process in top, 120 shown as 20, negative values have high priority, rt highest, different policy

the nice value shown per process in top output

thread group id in top output

size of executable per process in top output

dirty pages associated per process in top output, needs write-back to disk

(1) copy of data held temporarily in fast access area; (2) place to store data for faster access, temporarily, but possibly uniquely, ie, not a copy because of write-back policy

sometimes can be done across multiple levels of cache

reference found entirely in cache, shown around 98%, depending on temporal and spatial locality

least-recently used replacement policy (for cache, or DRAM)

approximate LRU, often clock or other circular queue with dynamic next pointer

typically from user mode to kernel mode to change state in a nontrivial or privileged way

each reference has k possible cache lines where it could be found/placed

a reference could be in any of the n available cache lines for the set

segregation of cache into parts for more size, usually using higher bits for segregation, adds complexity and power drain

cache miss on an attempted read; must attempt read from slower storage; usually new data inserted into cache

cache miss on an attempted write; write directly to cache (possibly after replacement) then write back, or write through to slower storage and insert into cache

part of the hardware memory model to keep caches sharing lines "simultaneously" updated on writes, using propagation

part of the hardware memory model to enforce certin kinds of correctness, esp wrt read and write interleaving

when one "piece of data" is referenced repeatedly within a small time interval; granularity could mean a byte, a line, a page/frame, or set of pages/frames

when data referenced is located "close to" data "recently" referrenced; granularity could mean next byte, next contiguous page, next disk block, usually prefetchable

often called the latter but meaning the former; preference for staying on a cpu with the same cache so data populating the cache can exploit temporal locality (and spatial if prefetched well)

number of lines, or more vaguely, its tendency to have cache hits across larger times, larger distances if prefetching

the pattern of data references by a process in a phase

spreading load across substitutable (but possibly not identical) resources, esp cpus (including performance and efficient cores in hybrid/asymmetric fashion)

no shared ready queues for cpu, at least across a set of cpus; opposite of shared ready queue

removing data from a cache without on-demand replacement; usually full flush on context switch usually for security, by hw or os

like cache flushing but perhaps just a line or few, not necessarily whole cache flush

sometimes used metaphor for good cache hit behavior for a process

bad cve that involved cache snooping during speculative execution / misprediction in hw

preemptive version of a mlfq using two arrays of linked lists and switching the main pointer when one current array empties (actually only achieves RR for the lowest prio class since preemptive)

one way to induce behaviors when addresses are known, or programs loaded at knowable base locations and contiguous

general term for small memory holes that cannot be coalesced because non-adjacent

virtual address for program relocation or virtualization, not to be confused with virtual memory in re:swapping/paging to disk, basically the numbers in a process memory map

address space id, basically PID, but possbily some ASIDS are PID-less

virtual address space charged per process in top output, often lazy allocation overcharge

physical resident DRAM charged per process in top output, real memory use, modulo shared (SHR) memory

hardware memory management unit, off cpu, originally calculating offsets, now including TLB and other duties

translation lookaside buffer, contains cached translations from ASIDxvAddr to PFN, may have its own levels and banks

physical frame number

quantum of actual DRAM, usually 4kB (4096 bytes)

usually vAddr range, contiguous in eyes of process (but usually not contiguous in physical memory), possibly arbitrary length; in linux, a multiple of page size

where segments are not adjacent, evidence of external fragmentation

fixed size (usually 4kB) of contiguous vAddrs; also huge pages, 2MB, 4MB, or more, rare birds often contiguous in PFNs

general term for wasted memory because minimum size of page or frame (or block, ...)

how the OS keeps track of vAddr to PFN translations when TLB miss, often ridiculously sparse, hence use HPT or IPT, usually per process

a page table entry, typically one entry per segment, not per individual page; note larger or huge pages use fewer PTEs

content-addressable memory, basically a fast associative array/hash table/dictionary used for TLB

basically a full cache flush or selective cache invalidation applied to the TLB

basically the ASID

per malloc request policy for finding space requested: best fit, worst, first, next, near, last freed, random; actually uses hybrid with bins of sizes

idea that if there were a list of contiguous free bytes after malloc/free, one could traverse that list as part of heap allocation strategy; may also used in any contiguous memory allocation mechanism; used even if data structure is not a linked list

in the context of free list, whether freed blocks of contiguous bytes go on front or back of linked list

joining adjacent free ranges to create a larger range from their union

recently freed blocks of contiguous bytes not yet placed in sorted bins, for immediate reallocation of same size

ensuring that parallel accesses by two or more threads maintains correct state (usually consistency or serialization) for next events (reads, writes, etc.)

pools of fixed sized objects used/reused by the kernel to avoid internatl frag on pages/frames, may take more than 1 page

a fixed sized object in a slab; objects per slab determined in advance

compromise between coalescing time and internal frag, no external frag, using contiguous pages in powers of two and coalescing only with buddy;/proc/buddyinfo shows buddy applied to physical memory (even though contiguity is less of an issue with dram)

contiguous memory recently released, not coalesced, assuming another malloc might want same or similar size, like a user-level slab

hierarchical page table where pointers point to subtables (actually higher order bits are used for direct access), which themselves point to subtables; the point being that most of those subtables are empty, hence saving space by omitting them entirely; requires k references to find translation for height k

often used to indicate page is in memory in a page table entry, just as a dirty bit indicates writeback needed

compressed data structure for array of boolean, which usually use a byte for boolean, so 8:1 compression and direct addressing

page table base register, allows quick indexing with offsets added to base

page table length register, at least for each table in a hierarchy, allows correctness checking any offset indexing

reference requires OS to use sw to find page translation in HPT or IPT, which can be done in parallel; associative caches can be searched in parallel and often are; L1, L2, L3 can be searched in parallel but often are NOT (power/complexity of routing issue)

inverted page table, software hash for page table translation

improving spatial locality so prefetching lines is improved (see also chasing pointers on disk)

allowing part of disk to act as virtual memory

one way to implement swap space esp in microsoft OS, see also swap partition (linux)

transferring data from memory to swap space on disk, or vice versa

vague idea of rate of memory consumption, see also high and low watermark

linux kernel parameter for tendency to swap out before 100% of memory used, 0-100

when a PTE does not find a page in memory (maybe in swap space, maybe needs to be created, maybe file on disk mapped in memory)

major page faults, number or delta since last update of top, required access of secondary memory (disk)

minor page fautlt, number or delta, did not require disk i/o, served by disk cache (or swap cache)

memory that is copy of what is on disk but still in memory, i.e., disk-backed non-dirty frames, adds to free mem to show available

memory that is copy of what is on disk specifically in swap space; i.e., it should be in memory but was swapped out to disk but a copy is still in memory

often reported in linux with disk cache, but different purpose, for buffering writes esp streaming i/o

memory locked in memory that cannot be swapped out

kernel daemon responsible for swap out

strategy for deciding victim page/frame when paging in and insufficient free memory

power of 2 for max number of contiguous pages swapped in as pre-fetch when swapping in a page

may also refer to swap out, not just swap in

ambiguous term for using swap area on disk for pages/frames mapped to secondary memory (NOT vAddr idea)

marketing term for swap space

old DEC OS that was proud of its virtual memory subsystem

lower-functionality OS than general-purpose, aimed at controlling a specific kind of system

philosophy of design where new is based heavily on prior to avoid massive unforseen failures

stack area for a thread visible in address space of threads sharing thread group

area adjacent to thread-specific stack where global variables get localized to avoid threads colliding making routines that were not intended for multi-threading MT-safe

pthread_create

the library required at the command line with gcc or cc when using a thread library

when nondeterminism results because of timing of thread execution that accesses shared data, specifically involving writes

one user at a time for a resource, mutual exclusion, usually a mechanism for creating mutual exclusion, if not guaranteeing it

a lock used to achieve mutex, where threads spin wait on cpu to acquire the lock once freed/released

a counter that locks a resource that is shareable once the limit is reached

usually guaranteed by hardware, a multi-step operation that cannot be interrupted by another thread or process once started

a software declaration that memory or processes need to be synchronized at some point, usually with waits issued by the compiler

a lock that requires a thread to check whether the lock is held voluntarily (linux)

a lock that is enforced by the OS (microsoft)

the size of the data locked, usually determining the amount of potential parallelism

also wait spin, busy wait, using cpu to poll for availability of a lock or flag, but can be paused to shorten wasted timeslices

one kind of atomic operation often provided by hardware

another kind of atomic operation

turn-yielding provably correct way of achieving mutex in software with three values (two variables, one an array with two values), if there is sequential consistency

memory operation discipline of the hardware (and possibly compiler), especially wrt cache read/write reorderings or cache coherence latency

total store order, better than PSO but not as good as sequential consistency, as memory consistency models go

like Peterson's algorithm but uses a ticket numbering idea

an idea where the programmer hints to the OS, e.g., that it is spin-waiting, so a pause or timeslice early expiry is possible

fast userspace mutex, sometimes does not require the kernel's intervention (when lock is free, fastpath), did not have the bug that pthread_mutex_lock had

two phase, spins first, then sleeps and waits for notification (interrupts sleep)

threads spin on local variable and notify next up

where a lock is held by a lower prio process and a higher prio process needs that locked resource to proceed

when there is priority inversion, the lower prio process gets the priority of the highest prio process that is waiting for the lock to be released

microsoft way of solving priority inversion, randomly boosting priorty of processes when locks are held (and there are processes waiting)

when there is a circular wait of any length and progress cannot be made by any thread/process in the circle

mutex, holding, no preemption, circular wait

vague idea of processes not technically deadlocked but not making progress, threads not blocked but not happy, typically cycling through states

in 1d, require before giving a resource (e.g., a lock to a thread) that the recipient be able to complete and free that resource; in k-d, must simulate possible n-thread allocation orders and find at least one sequence of execution that leads to release of resource

simple illustration of deadlock-prone multi-processing with n threads and n pairwise shared resources

one solution to avoiding deadlock in Dining Philosophers'

one illustration of delayed global accuracy so local counts can be separated for parallelism

penalty for synchronization that prevents linear speedup with parallel processing

locking nodes within a linked list rather than the whole linked list

another illustration of parallelizing data structure, head and tail have separate locks

another illustration of parallelizing data structure, lock each collision chain for a hash bucket

premature optimization is the root of all evil

redundant array of independent disks, storage control that stripes for performance, mirrors for redundancy, or adds parity for error detection AND correction (RAID 0 striping, RAID 1 mirroring)

cyclic redundancy check, just a fancy name for checksum that adds numeric representation of data chunks, then stores remainder mod k

in linux, where we store metadata, possibly even a checksum

triple modular redundancy, a voting method for robust operation against 1-failure

n (odd n?) generalization of TMR to survive floor(n/2)-failure

Zettabyte file system which writes anew then switches pointer to data block rather than making changes in place

what disk scrubbing by checking data checksums tries to avoid

allowing access to a resource based on knowing, having, or being; also behaving, situating, signed on elsewhere, system having

multi-factor authentication

stored passwords not in plain text but using a hash function as cipher

breaking a password by trying using enumeration of all possible

if the hash function is known, pre-computing the hashes to discover common passwords easily from their hashed form (e.g., stealing the password file in hashed form)

added to user passwords to extend the length, unique to each password instance, combats rainbow tables, naive users

added to user passwords to extend the length, stored separately, often same per user, combats theft of password hashes with salts, naive sysadmins

times and places where password must be revealed for authentication, hence available for leak, see progressive revelation

idea that once authenticated, movement within the perimeter requires no further authentication, vs continuous authentication, layered defense, defense in depth

places where a system is vulnerable to attack by malign actor (independent of other failures that are non-adversarial)

hiding access in such a way that once the path or secret is known, there is no further or future protection

idea that users and processes should have no more privileges than necessary to perform their intended task(s)

moving target defense, changing locations, names, or paths to access so those in the know retain access but not those who discover but do not update

software defined network, one way to implement MTD for servers

role-based authentication vs ABAC, attribute-based

history-based authentication

path-based authentication

machine that is not bare-metal, require emulation on bare-metal machine (BMM); scalable, isolated, secure

software that runs a guest OS as virtual machine; type-1: no host OS; type-2: host OS you can use independently; plays on supervisor=monitor=OS

example popular type 1 hypervisor

example popular type 2 hypervisor

allowing guest OS to communicate directly with host OS or BMM drivers, esp for i/o performance using hypercalls, bypassing emulation

considered alternative to hypervisor but is really a packaging of software, not an isolation and emulation; less secure, more like virtual backend web services with minimal dependencies specified in config files