FINAL STUDY Flashcards
Four issues of complexity?
- Emergent Properties
- Propagation of Effects
- Incommensurate Scaling
- Tradeoffs
Emergent Properties
(issue of complexity)
Properties that show when combining components
Propagation of Effects
(issue of complexity)
Problems in one component affect other components
Incommensurate Scaling
(issue of complexity)
Not all parts of a system scale at the same rate
Tradeoffs
(issue of complexity)
Sacrifice one thing for more of something else
What is a system?
A set of interconnected components that has an expected
behavior observed at the interface with its environment.
Signs of Complexity?
- Large number of components
- Large number of interconnections
- Lots of irregularities (little differences)
- Long description (high information content)
- Large team of designers, implementers, or maintainers
What are the sources of system complexity?
- Interactions of requirements
- Increasing efficiency, utilization, or other measure of “goodness”
Interactions of Requirements in terms of complexity?
(source of system complexity)
A general-purpose tool that can do X and other things is more complex than
a special-purpose tool that can only do X
Increasing efficiency, utilization, or “goodness” in terms of complexity?
(source of system complexity)
Additional gains in efficiency will lead to a more complex system
What increases complexity?
- Principle of escalating complexity
- Principle of excessive generality
- Law of Diminishing Returns
Principle of escalating complexity?
(increases system complexity)
Adding a requirement increases complexity out of proportion
Principle of excessive generality?
(increases system complexity)
If it’s good for everything, it’s good for nothing (flying car)
Law of Diminishing Returns?
(increases system complexity)
The more one measure of goodness is improved, the harder it gets to make
the next improvement
Ways we can manage complexity?
- Modularity
- Abstraction
- Layering
- Hierarchy
Modularity
Break big things into smaller pieces (aka divide and conquer)
Abstraction
Break into components at logical points, Treat an individual component as a black box, Benefit from the Robustness principle
Layering
Build new layer from (already existing) lower layer, Layer may consist of multiple modules (components), Modules in a layer may only interact within the layer or up or down one layer
Hierarchy
Combine small groups of modules into small subsystems, Combine small subsystems into large subsystems, Combine large subsystems into systems, Limit the visibility of each level of abstraction hierarchy to limit
complexity
Robustness Principle
Be TOLERANT on inputs, be STRICT on outputs
Three main things a system does?
Store -> Memory
Compute -> Interpreter
Communicate -> Communication Channels
Volatile Memory/ Non-Volatile Memory
Volatile Memory is memory that only keeps data while it’s powered
Bandwidth (Memory Performance)
Units of memory/Units of time
Latency (Memory Performance)
How long does it take to get a single value from memory
What is more important? Low read latency? Low write latency? Why?
Read Latency, because we can make it asynchronous, writes are synchronous
Programs bound by synchronous writes operate at the speed of write ________.
a. latency
b. bandwidth
c. throughput
Write latency
Programs bound by asynchronous writes operate at the speed of write
_________.
a. latency
b. bandwidth
c. throughput
Write bandwidth
Read/Write Coherency
The result of a read is the same as the most recent write
Read/Write Atomicity
The result of a read is as
if the read occurred completely before or completely after every other write
What two functions does a communication link use?
SEND(link, message_buf)
RECEIVE(link, message_buf)
char *s = “abc”;
s = NULL;
what happens?
s becomes a null pointer
char s[10] = “abc”;
s = NULL;
what happens?
ERROR s is not an address
int main(void) {
char *s;
…
}
What is s initialized to?
It’s not initialized! Local variables aren’t initialized.
char *s;
int main(void) {
…
}
What is s initialized to?
It is initialized to NULL
int main(void) {
static char* s;
…
}
What is s initialized to?
It is initialized to NULL.
It has a GLOBAL storage, but LOCAL scope
open()
- header for function?
- header for flags?
- what arguments?
- success return value(s)?
- error return value(s)?
- Flag to read/write
- Flag to read
- Flag to write
- Flag to create file
- Flag to truncate file
- <unistd.h>
</unistd.h> - <fcntl.h>
</fcntl.h> - open(char* pathname, int flags, mode_t mode)
- Success: non-negative int
- Error: -1
- O_RDWR
- O_RDONLY
- O_WRONLY
- O_CREAT
- O_TRUNC
read()
- header for function?
- what arguments?
- success return value(s)?
- error return value(s)?
- <unistd.h>
</unistd.h> - read(int fd, void* buf, size_t n)
- Success: num bytes read, can be 0
- Error: -1
write()
- header for function?
- what arguments?
- success return value(s)?
- error return value(s)?
- <unistd.h>
</unistd.h> - (int fd, void *buf, size_t n)
- Success: num bytes written, can be zero
- Error: -1
creat()
- arguments
- success return values?
- error return values?
- creat(char* name, mode_t mode)
- Success: non-negative int
- Error: -1
close()
- arguments
- success return values?
- error return values?
- close(int fd)
- Success: 0
- Error: -1
unlink()
- arguments
- success return values?
- error return values?
- unlink(char *name)
- Success: 0
- Error: -1
lseek()
- arguments
- success return values?
- error return values?
- lseek(int fd, off_t offset, int origin)
- Success: non-negative int
- Error: -1
origin:
- SEEK_SET means relative to beginning of file (offset ≥ 0)
- SEEK_CUR means relative to current position
- SEEK_END means relative to end of file (offset ≤ 0)
regcomp()
- arguments
- success return values?
- error return values?
- regcomp(regex_t preg, char regex, int cflags)
- Success: 0
- Error: error code use regerror() to convert
CFlags:
- REG_EXTENDED - use it
- REG_NEWLINE - [”^” -> “$”]
regfree()
- arguments
- success return value?
- error return value?
- regfree(regex_t *preg)
- Success: does not return
- Error: does not return
regexec()
- arguments
- success return value?
- error return value?
- regexec(regex_t preg, char string, size_t nmatch, regmatch_t pmatch[], int eflags)
- Success: 0
- Error: error code convert use regerror()
- declare pmatch array with nmatch items
- pmatch[0] always matches whole expression
regmatch_t struct
- beginning of match
- end of match
- rm_so
- rm_eo
printf(“%.10s”, string);
how many characters will this print
it will print NO MORE than 10 characters
max_width = 5;
printf(“%.*s”, max_width, string);
how many characters will this print?
it will print NO MORE than 5 characters
LAMP Web Server, what does LAMP stand for?
Linux
Apache
MySQL
PHP
Soft Modularity
Dividing code into named modules, functions etc., what we normally do when we code
Hard Modularity
Divide code and let them communicate only through messages. “Connected by a wire”
Marshaling
Essentially serialization, Ensuring that the client and server data have the same meaning
How does the interpreter(CPU) receive the next instruction, aka what does it access?
Instruction Reference
How does the interpreter(CPU) interpret an instruction, aka what does it access?
Instruction Repertoire and Environment Reference
What does the interpreter(CPU) change when it gets an interrupt signal?
Instruction Reference and Environment Reference
what gets printed out here?
printf(“%5s”, 123456789);
12345
what gets printed out here?
printf(“%5s”, 123);
_ _ 123
_ = space
Multiplexing
Create multiple virtual objects from one underlying object
Aggregation
Create one virtual object from multiple underlying objects
Emulation
Create new type of object from underlying objects
Race Condition
Behavior of System depends on the timing or order of uncontrollable events, situation where two interacting events occur at the same time
Atomicity Violation
When an operation should be atomic but it is not
Data Race
When two unordered memory operations (one of which is a write) act on the same variable
What are the conditions of Mutual Exclusion
- No two threads may be in their Critical Regions simultaneously
- Any number of threads
- Thread running outside Critical Region cannot block another thread
- Thread cannot wait forever to enter Critical Region
pthread_mutex_init()
- arguments
- success return value?
- error return value?
1.pthread_mutex_init (pthread_mutex_t *mutex, pthread_mutexattr_t *attr)
2. Success: 0
3. Error: error code
- set attr to NULL to use default attr
pthread_mutex_lock()
- arguments
- success return value?
- error return value?
- pthread_mutex_lock (pthread_mutex_t *mutex)
- Success: 0
- Error: error code
pthread_mutex_unlock()
- arguments
- success return value?
- error return value?
- pthread_mutex_unlock (pthread_mutex_t *mutex)
- Success: 0
- Error: error code
pthread_mutex_destroy()
- arguments
- success return value?
- error return value?
- pthread_mutex_destroy (pthread_mutex_t *mutex)
- Success: 0
- Error: error code
pthread_cond_wait()
- arguments
- success return value?
- error return value?
- pthread_cond_wait (pthread_cond_t *cond, pthread_mutex_t *mutex)
- Success: 0
- Error: error code
pthread_cond_signal()
- arguments
- success return value?
- error return value?
- pthread_cond_signal (pthread_cond_t *cond)
- Success: 0
- Error: error code
pthread_cond_broadcast()
- arguments
- success return value?
- error return value?
- pthread_cond_broadcast (pthread_cond_t *cond)
- Success: 0
- Error: error code
sem_init()
- arguments?
- success return value?
- error return value?
- sem_init (sem_t *sem, int pshared, unsigned value)
- Success: 0
- Error: -1
pthread_cond_init()
- arguments?
- success return value?
- error return value?
- pthread_cond_init (pthread_cond_t *cond, pthread_condattr_t *attr)
- Success: 0
- Error: error code
sem_wait()
- arguments?
- success return value?
- error return value?
- sem_wait(sem_t *sem)
- Success: 0
- Error: -1
sem_post()
- arguments?
- success return value?
- error return value?
- sem_post(sem_t *sem)
- Success: 0
- Error: -1
sem_destroy()
- arguments?
- success return value?
- error return value?
- sem_destroy(sem_t *sem)
- Success: 0
- Error: -1
pthread_create()
- arguments?
- success return value?
- error return value?
- pthread_create (pthread_t thread, pthread_attr_t attr, void func, void arg)
- Success: 0
- Error: error code
- set attr_t to NULL to get default attributes
pthread_join()
- arguments?
- success return value?
- error return value?
- pthread_join(pthread_t thread, void value_ptr**)
- Success: 0
- Error: -1
Preemptable Resource/Nonpreemtable resource
Preemptable resource is a resource that can be taken away from a process with no ill effects.
Infeasible Region
When path inside infeasible region it means two tasks have resource simultaneously
Unsafe Region
If two tasks reach unsafe region there is no way out tasks must end, will get “Cycle of Waiting”. Irreversibility of progress guarantees deadlock
Conditions for an Unsafe Region
- Tasks both claim Mutual Exclusion
- Nonpreemption for both tasks
- Both tasks are in a state of “Hold and Wait”
Conditions for Deadlock
- Tasks both claim Mutual Exclusion
- Nonpreemption for both tasks
- Both tasks are in a state of “Hold and Wait”
- “Cycle of Waiting”
Basically conditions for unsafe region + “Cycle of Waiting”
In a resource and task graph how can we identify a deadlock?
With a cycle
Ostrich Algorithm
Pretend there is no problem, reasonable if deadlock occurs rarely or/and cost of prevention high
How can we eliminate Mutual Exclusion during deadlock
Spooling, Avoid assigning resource when not absolutely necessary, As few processes as possible actually claim the resource
How can we eliminate Hold and Wait during deadlock
Require processes to request resources before starting
Variation: a process must give up all resources before making a new
request
Livelock
processes can still run, but not make progress
P0 gets A, P1 gets B
P0 drops A, P1 drops B
P0 gets B, P1 gets A
…
deci
10^-1
deka
10^1
hecto
10^2
centi
10^-2
milli
10^-3
kilo
10^3
Mega
10^6
micro
10^-6
Giga
10^9
nano
10^-9
In a resource allocation graph:
- what shape is around resources?
- what shape is around tasks?
- what does it mean when an arrow points from resource -> task?
- what does it mean when an arrow points from task -> resource?
- Square
- Circle
- task HOLDS resource
- task WANTS resource
Strict Alternation
TWO threads take turns executing use a shared variable called turn
Dekker’s Algorithm
Basically like Strict Alternation, but thread has to proclaim interest
Lamport’s Bakery
Each task takes a unique number in increasing order, and executes their Critical Section, then give up their number. If two tasks attempt to grab same number break tie with task ID
getopt()
- arguments
- success return value?
- error return value?
- getopt(int argc, char **argv, char *opstring)
- Success: option character or -1
- Error: ? or :
Techniques for improving performance
- Pipelining
- Concurrency
- Fast Path
- Limitations
Latency_a+b ? latency a + latency b
in a pipelined system?
latency_a+b >= latency_a + latency_b
throughput_a+b = ?(throughput_a, throughput_b)
in a pipelined system?
throughput_a+b = min(throughput_a, throughput_b)
Concurrency in terms of Performance
Running independent subtasks in parallel, improves throughput
Formula for Average Latency with a slow path and a fast path
Average Latency = fraction_fast path * latency_fast path + fraction_slow_path * latency_slow path
In a single module what’s the relation between latency and throughput?
Latency = 1/throughput
Total throughput of n CONCURRENT, IDENTICAL modules
n * throughput_individual module
Batching to deal with bottlenecks
Group requests as a group and process them as a single unit
Dallying to deal with bottlenecks
Delay unit hopefully will not be needed or will be batched
Speculation to deal with bottlenecks
Read next data early
Burts and Overload
If sudden burst of requests and pipeline not properly equipped it might be overloaded
How to design system for performance
- Measure the system to see if it is needs to be faster
- Measure again to find the bottleneck
- Predict the impact of removing bottleneck
3.a.Removing the bottleneck doesn’t help performance: reconsider design?
3.b.Removing the bottleneck will help: find ways to remove it - Implement new solution and repeat
Workload
the tasks (requests) processed by a system
Benchmarks
Create a “synthetic” workload based on characteristics observed in real ones, may use some randomness
Caching
remembering expensive computations in case they are
needed again
Working set
the set of items used during interval Δt
Locality Of Reference
clustering of memory references in both time and address space
What if working set < primary storage?
Nothing, that’s a good thing!
What if working set > primary storage?
BAD, thrashing = overwriting of primary storage
Temporal Locality
Recent items are likely to be referenced again soon
Spatial Locality
Items “near” recently items are likely to be referenced
Write-Back
Write to cached data only
Write-Through
Write to both cached data and back-end data
Fully Associative
each item can be stored anywhere
Direct-Mapped Associative
each item can be stored in only one location
N-Way Associative
each item can be stored in n locations
Mechanism
The algorithms and structures used
Policy
The decision of what action to perform
What are the page replacement policies?
- LRU
- FIFO
- Second Chance
- Clock
Not recently used + Dirty bit classes:
0 ___ referenced, ____ dirty
1 ___ referenced, ____ dirty
2 ___ referenced, ____ dirty
3 ___ referenced, ____ dirty
0: not referenced, not dirty
1: not referenced, dirty
2: referenced, not dirty
3: referenced, dirty
Reference String
set of accesses made to system
Belady’s Anomaly (kinda cool)
Adding more memory can increase amount of page faults in FIFO page replacement
Kerchoff’s Doctrine
The security of a system should depend on its key, not on its design remaining obscure
Assumptions in single-node system attacker can:
- Observe the timing of actions
- Observe the inputs/outputs of the system
- Control the inputs to the system
Assumptions in multi-node system attacker can:
- Observe messages sent between nodes
- Drop messages sent between nodes
- Change messages sent between nodes
Types of Security Vulnerabilities
- Corner-case Bugs
- Unsanitized-input Bugs
- Side-channel Bugs
- Dependency Vulnerabilities
