Defns Flashcards
library os
library of standard services
multitasking os
can have multiple processes existing at once
preemption
interrupt a running task
memory protection
protect processes from one another
multi user os
provides protection to serve distrustful users/buggy apps
interposition/mediation
os tracks all the resources an app can use and checks legality on each access
process
an instance of a running program
io bound
time of task determined by waiting for io
cpu bound
time of task determined by speed of processor
concurrency
multiple programs running/appearing to run simultaneously
parallelism
run two threads at the same time in multiple cores
preemptive multitasking
rapidly switch between two threads on the same core
process control block
struct os uses to track state of a process
context switch
a transition between contexts
thread
schedulable execution context
limitations of kernel threads
slower thread operations
one-size fits all thread impl
heavy weight memory reqs
limitations of user threads
cannot take advantage of multiple cores
blocking syscall blocks all threads
possible deadlock if one thread blocks all threads
limitations of n:m threads
blocked threads, deadlock
hard to maximize parallelism
kernel doesn’t know relative importance of each thread
caller-save
not preserved across subroutine calls
saved in switchframe
callee-save
preserved across subroutine calls
saved in trapframe
race condition
program result depends on order of execution
cache coherence
all threads see the same value for a shared resource
cache consistency
all threads receive updates in order
seqcon
result of execution is as if the operations of each processor occurred in the order specified by the program
write atomaticity
if any core reads the result of a write, all subsequent reads see the same result
write-back caching
mark cache portion as dirty, write back when flushing
write-through caching
write back immediately
write-combining
store writes in a buffer and occur in a burst
weak consistency
no guarantee that reads/writes have seqcon
critical section
code that accesses a shared variable and must not be executed concurrently by >1 thread
mutual exclusion
only one thread can be in a critsec at a time
progress/liveness
if no thread is in a critsec and one wants to get in, it will eventually
bounded waiting/fairness
once a thread starts waiting to enter a critsec, there is a limit to how long it waits
lockset algorithm
for each shared resource keep a lockset; if the lockset is ever empty there is no mutex protecting it (catch potential races)
amdahl’s law
T(n)= T(1)(B + 1/n(1 - B))
scalable commutativity rule
whenever interface operations commute, they can be implemented in a way that scales
coarse grained locking
one lock for a whole data structure, if it isn’t used that often
fine grained locking
one lock for each element, maximizes concurrency for a structure used often
contention
threads often waiting for a particular resource; often good to use fine grained locking
spinlock
a lock that spins (repeatedly tests the lock’s availability in a loop until it is obtained)
cache line states
modified, shared, invalid
modified state
one cache has a valid (dirty copy), all other copies in other caches are stale (they must be invalidated before entering this state)
shared state
one or more caches have a valid copy
invalid state
doesn’t contain the data
non-uniform memory access (NUMA)
processors can access their local memory faster than the memory of other processors
deadlock
multiple threads waiting on each other, preventing progress
deadlock conditions
- limited access
- no preemption of resources
- hold and wait
- circularity in graph of requests
interrupt
signals generated by devices that need attention
exception
conditions discovered by the processor while executing an instruction
interrupt handler
a function in the kernel that services a device request
non-maskable interrupt (NMI)
interrupts that cannot be disabled, for urgent requests (e.g. overheating)
interrupt descriptor table (IDT)
defines the entry point for a particular interrupt vector
x86 hardware interrupt handling process
RESTITS
application binary interface (ABI)
defines the contract between an app’s functions and system calls (OSes and compilers must obey these rules - calling conventions)
stack frame
contains all the saved registers and local variables that must be saved within a single function call
execution context
the environment where functions execute, including their arguments, local vars, memory
application context
application threads
kernel context
kernel threads, software interrupts
interrupt context
interrupt handler
