FINAL STUDY Flashcards
(139 cards)
1
Q
Four issues of complexity?
A
- Emergent Properties
- Propagation of Effects
- Incommensurate Scaling
- Tradeoffs
2
Q
Emergent Properties
(issue of complexity)
A
Properties that show when combining components
3
Q
Propagation of Effects
(issue of complexity)
A
Problems in one component affect other components
4
Q
Incommensurate Scaling
(issue of complexity)
A
Not all parts of a system scale at the same rate
5
Q
Tradeoffs
(issue of complexity)
A
Sacrifice one thing for more of something else
6
Q
What is a system?
A
A set of interconnected components that has an expected
behavior observed at the interface with its environment.
7
Q
Signs of Complexity?
A
- 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
8
Q
What are the sources of system complexity?
A
- Interactions of requirements
- Increasing efficiency, utilization, or other measure of “goodness”
9
Q
Interactions of Requirements in terms of complexity?
(source of system complexity)
A
A general-purpose tool that can do X and other things is more complex than
a special-purpose tool that can only do X
10
Q
Increasing efficiency, utilization, or “goodness” in terms of complexity?
(source of system complexity)
A
Additional gains in efficiency will lead to a more complex system
11
Q
What increases complexity?
A
- Principle of escalating complexity
- Principle of excessive generality
- Law of Diminishing Returns
12
Q
Principle of escalating complexity?
(increases system complexity)
A
Adding a requirement increases complexity out of proportion
13
Q
Principle of excessive generality?
(increases system complexity)
A
If it’s good for everything, it’s good for nothing (flying car)
14
Q
Law of Diminishing Returns?
(increases system complexity)
A
The more one measure of goodness is improved, the harder it gets to make
the next improvement
15
Q
Ways we can manage complexity?
A
- Modularity
- Abstraction
- Layering
- Hierarchy
16
Q
Modularity
A
Break big things into smaller pieces (aka divide and conquer)
17
Q
Abstraction
A
Break into components at logical points, Treat an individual component as a black box, Benefit from the Robustness principle
18
Q
Layering
A
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
19
Q
Hierarchy
A
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
20
Q
Robustness Principle
A
Be TOLERANT on inputs, be STRICT on outputs
21
Q
Three main things a system does?
A
Store -> Memory
Compute -> Interpreter
Communicate -> Communication Channels
22
Q
Volatile Memory/ Non-Volatile Memory
A
Volatile Memory is memory that only keeps data while it’s powered
23
Q
Bandwidth (Memory Performance)
A
Units of memory/Units of time
24
Q
Latency (Memory Performance)
A
How long does it take to get a single value from memory
25
What is more important? Low read latency? Low write latency? Why?
Read Latency, because we can make it asynchronous, writes are synchronous
26
Programs bound by synchronous writes operate at the speed of write ________.
a. latency
b. bandwidth
c. throughput
Write latency
27
Programs bound by asynchronous writes operate at the speed of write
_________.
a. latency
b. bandwidth
c. throughput
Write bandwidth
28
Read/Write Coherency
The result of a read is the same as the most recent write
29
Read/Write Atomicity
The result of a read is as
if the read occurred completely before or completely after every other write
30
What two functions does a communication link use?
SEND(link, message_buf)
RECEIVE(link, message_buf)
31
char *s = "abc";
s = NULL;
what happens?
s becomes a null pointer
32
char s[10] = "abc";
s = NULL;
what happens?
ERROR s is not an address
33
int main(void) {
char *s;
...
}
What is s initialized to?
It's not initialized! Local variables aren't initialized.
34
char *s;
int main(void) {
...
}
What is s initialized to?
It is initialized to NULL
35
int main(void) {
static char* s;
...
}
What is s initialized to?
It is initialized to NULL.
It has a GLOBAL storage, but LOCAL scope
36
open()
1. header for function?
2. header for flags?
3. what arguments?
4. success return value(s)?
5. error return value(s)?
6. Flag to read/write
7. Flag to read
8. Flag to write
9. Flag to create file
10. Flag to truncate file
1.
2.
3. open(char* pathname, int flags, mode_t mode)
4. Success: non-negative int
5. Error: -1
6. O_RDWR
7. O_RDONLY
8. O_WRONLY
9. O_CREAT
10. O_TRUNC
37
read()
1. header for function?
2. what arguments?
3. success return value(s)?
4. error return value(s)?
1.
2. read(int fd, void* buf, size_t n)
3. Success: num bytes read, can be 0
4. Error: -1
38
write()
1. header for function?
2. what arguments?
3. success return value(s)?
4. error return value(s)?
1.
2. (int fd, void *buf, size_t n)
3. Success: num bytes written, can be zero
4. Error: -1
39
creat()
1. arguments
2. success return values?
3. error return values?
1. creat(char* name, mode_t mode)
2. Success: non-negative int
3. Error: -1
40
close()
1. arguments
2. success return values?
3. error return values?
1. close(int fd)
2. Success: 0
3. Error: -1
41
unlink()
1. arguments
2. success return values?
3. error return values?
1. unlink(char *name)
2. Success: 0
3. Error: -1
42
lseek()
1. arguments
2. success return values?
3. error return values?
1. lseek(int fd, off_t offset, int origin)
2. Success: non-negative int
3. 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)
43
regcomp()
1. arguments
2. success return values?
3. error return values?
1. regcomp(regex_t *preg, char* regex, int cflags)
2. Success: 0
3. Error: error code use regerror() to convert
CFlags:
- REG_EXTENDED - use it
- REG_NEWLINE - ["^" -> "$"]
44
regfree()
1. arguments
2. success return value?
3. error return value?
1. regfree(regex_t *preg)
2. Success: does not return
3. Error: does not return
45
regexec()
1. arguments
2. success return value?
3. error return value?
1. regexec(regex_t *preg, char* string, size_t nmatch, regmatch_t pmatch[], int eflags)
2. Success: 0
3. Error: error code convert use regerror()
- declare pmatch array with nmatch items
- pmatch[0] always matches whole expression
46
regmatch_t struct
1. beginning of match
2. end of match
1. rm_so
2. rm_eo
47
printf("%.10s", string);
how many characters will this print
it will print NO MORE than 10 characters
48
max_width = 5;
printf("%.*s", max_width, string);
how many characters will this print?
it will print NO MORE than 5 characters
49
LAMP Web Server, what does LAMP stand for?
Linux
Apache
MySQL
PHP
50
Soft Modularity
Dividing code into named modules, functions etc., what we normally do when we code
51
Hard Modularity
Divide code and let them communicate only through messages. "Connected by a wire"
52
Marshaling
Essentially serialization, Ensuring that the client and server data have the same meaning
53
How does the interpreter(CPU) receive the next instruction, aka what does it access?
Instruction Reference
54
How does the interpreter(CPU) interpret an instruction, aka what does it access?
Instruction Repertoire and Environment Reference
55
What does the interpreter(CPU) change when it gets an interrupt signal?
Instruction Reference and Environment Reference
56
what gets printed out here?
printf("%5s", 123456789);
12345
57
what gets printed out here?
printf("%5s", 123);
_ _ 123
_ = space
58
Multiplexing
Create multiple virtual objects from one underlying object
59
Aggregation
Create one virtual object from multiple underlying objects
60
Emulation
Create new type of object from underlying objects
61
Race Condition
Behavior of System depends on the timing or order of uncontrollable events, situation where two interacting events occur at the same time
62
Atomicity Violation
When an operation should be atomic but it is not
63
Data Race
When two unordered memory operations (one of which is a write) act on the same variable
64
What are the conditions of Mutual Exclusion
1. No two threads may be in their Critical Regions simultaneously
2. Any number of threads
3. Thread running outside Critical Region cannot block another thread
4. Thread cannot wait forever to enter Critical Region
65
pthread_mutex_init()
1. arguments
2. success return value?
3. 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
66
pthread_mutex_lock()
1. arguments
2. success return value?
3. error return value?
1. pthread_mutex_lock (pthread_mutex_t *mutex)
2. Success: 0
3. Error: error code
67
pthread_mutex_unlock()
1. arguments
2. success return value?
3. error return value?
1. pthread_mutex_unlock (pthread_mutex_t *mutex)
2. Success: 0
3. Error: error code
68
pthread_mutex_destroy()
1. arguments
2. success return value?
3. error return value?
1. pthread_mutex_destroy (pthread_mutex_t *mutex)
2. Success: 0
3. Error: error code
69
pthread_cond_wait()
1. arguments
2. success return value?
3. error return value?
1. pthread_cond_wait (pthread_cond_t *cond, pthread_mutex_t *mutex)
2. Success: 0
3. Error: error code
70
pthread_cond_signal()
1. arguments
2. success return value?
3. error return value?
1. pthread_cond_signal (pthread_cond_t *cond)
2. Success: 0
3. Error: error code
71
pthread_cond_broadcast()
1. arguments
2. success return value?
3. error return value?
1. pthread_cond_broadcast (pthread_cond_t *cond)
2. Success: 0
3. Error: error code
72
sem_init()
1. arguments?
2. success return value?
3. error return value?
1. sem_init (sem_t *sem, int pshared, unsigned value)
2. Success: 0
3. Error: -1
73
pthread_cond_init()
1. arguments?
2. success return value?
3. error return value?
1. pthread_cond_init (pthread_cond_t *cond, pthread_condattr_t *attr)
2. Success: 0
3. Error: error code
74
sem_wait()
1. arguments?
2. success return value?
3. error return value?
1. sem_wait(sem_t *sem)
2. Success: 0
3. Error: -1
75
sem_post()
1. arguments?
2. success return value?
3. error return value?
1. sem_post(sem_t *sem)
2. Success: 0
3. Error: -1
76
sem_destroy()
1. arguments?
2. success return value?
3. error return value?
1. sem_destroy(sem_t *sem)
2. Success: 0
3. Error: -1
77
pthread_create()
1. arguments?
2. success return value?
3. error return value?
1. pthread_create (pthread_t *thread, pthread_attr_t *attr, void* func, void* arg)
2. Success: 0
3. Error: error code
- set attr_t to NULL to get default attributes
78
pthread_join()
1. arguments?
2. success return value?
3. error return value?
1. pthread_join(pthread_t thread, void value_ptr**)
2. Success: 0
3. Error: -1
79
Preemptable Resource/Nonpreemtable resource
Preemptable resource is a resource that can be taken away from a process with no ill effects.
80
Infeasible Region
When path inside infeasible region it means two tasks have resource simultaneously
81
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
82
Conditions for an Unsafe Region
1. Tasks both claim Mutual Exclusion
2. Nonpreemption for both tasks
3. Both tasks are in a state of "Hold and Wait"
83
Conditions for Deadlock
1. Tasks both claim Mutual Exclusion
2. Nonpreemption for both tasks
3. Both tasks are in a state of "Hold and Wait"
4. "Cycle of Waiting"
Basically conditions for unsafe region + "Cycle of Waiting"
84
In a resource and task graph how can we identify a deadlock?
With a cycle
85
Ostrich Algorithm
Pretend there is no problem, reasonable if deadlock occurs rarely or/and cost of prevention high
86
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
87
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
88
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
...
89
deci
10^-1
90
deka
10^1
91
hecto
10^2
92
centi
10^-2
93
milli
10^-3
94
kilo
10^3
95
Mega
10^6
96
micro
10^-6
97
Giga
10^9
98
nano
10^-9
99
In a resource allocation graph:
1. what shape is around resources?
2. what shape is around tasks?
3. what does it mean when an arrow points from resource -> task?
4. what does it mean when an arrow points from task -> resource?
1. Square
2. Circle
3. task HOLDS resource
4. task WANTS resource
100
Strict Alternation
TWO threads take turns executing use a shared variable called turn
101
Dekker's Algorithm
Basically like Strict Alternation, but thread has to proclaim interest
102
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
103
getopt()
1. arguments
2. success return value?
3. error return value?
1. getopt(int argc, char **argv, char *opstring)
2. Success: option character or -1
3. Error: ? or :
104
Techniques for improving performance
1. Pipelining
2. Concurrency
3. Fast Path
4. Limitations
105
Latency_a+b ? latency a + latency b
in a pipelined system?
latency_a+b >= latency_a + latency_b
106
throughput_a+b = ?(throughput_a, throughput_b)
in a pipelined system?
throughput_a+b = min(throughput_a, throughput_b)
107
Concurrency in terms of Performance
Running independent subtasks in parallel, improves throughput
108
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
109
In a single module what's the relation between latency and throughput?
Latency = 1/throughput
110
Total throughput of n CONCURRENT, IDENTICAL modules
n * throughput_individual module
111
Batching to deal with bottlenecks
Group requests as a group and process them as a single unit
112
Dallying to deal with bottlenecks
Delay unit hopefully will not be needed or will be batched
113
Speculation to deal with bottlenecks
Read next data early
114
Burts and Overload
If sudden burst of requests and pipeline not properly equipped it might be overloaded
115
How to design system for performance
1. Measure the system to see if it is needs to be faster
2. Measure again to find the bottleneck
3. 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
4. Implement new solution and repeat
116
Workload
the tasks (requests) processed by a system
117
Benchmarks
Create a “synthetic” workload based on characteristics observed in real ones, may use some randomness
118
Caching
remembering expensive computations in case they are
needed again
119
Working set
the set of items used during interval Δt
120
Locality Of Reference
clustering of memory references in both time and address space
121
What if working set < primary storage?
Nothing, that's a good thing!
122
What if working set > primary storage?
BAD, thrashing = overwriting of primary storage
123
Temporal Locality
Recent items are likely to be referenced again soon
124
Spatial Locality
Items “near” recently items are likely to be referenced
125
Write-Back
Write to cached data only
126
Write-Through
Write to both cached data and back-end data
127
Fully Associative
each item can be stored anywhere
128
Direct-Mapped Associative
each item can be stored in only one location
129
N-Way Associative
each item can be stored in n locations
130
Mechanism
The algorithms and structures used
131
Policy
The decision of what action to perform
132
What are the page replacement policies?
1. LRU
2. FIFO
3. Second Chance
3. Clock
133
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
134
Reference String
set of accesses made to system
135
Belady's Anomaly (kinda cool)
Adding more memory can increase amount of page faults in FIFO page replacement
136
Kerchoff's Doctrine
The security of a system should depend on its key, not on its design remaining obscure
137
Assumptions in single-node system attacker can:
1. Observe the timing of actions
2. Observe the inputs/outputs of the system
3. Control the inputs to the system
138
Assumptions in multi-node system attacker can:
1. Observe messages sent between nodes
2. Drop messages sent between nodes
3. Change messages sent between nodes
139
Types of Security Vulnerabilities
1. Corner-case Bugs
2. Unsanitized-input Bugs
3. Side-channel Bugs
4. Dependency Vulnerabilities
