-
Notifications
You must be signed in to change notification settings - Fork 16
/
concurrency.theory.txt
260 lines (214 loc) · 18.2 KB
/
concurrency.theory.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
CONCURRENCY
CONCURRENCY VS PARALLELISM ==> #Concurrent/concurring programming:
# - two tasks whose start-end periods overlap
# - each might not run continously, i.e. they are not necessarily parallel
# - usually implies async
# - goals:
# - user convenience (multitasking)
# - enables (but do not cause alone) parallelism
# - problem: synchronization
#Parallel:
# - two tasks running at same time
# - goal: performance
SUMMARY ==> #Types:
# - multiprocessing, multiprogramming, multitasking, multithreading
# - process, thread, fiber, task
#Task switch: cooperative (yield, exceptions) vs preemptive (IRQ)
#Task dependencies: sync vs async
#Collisions:
# - critical sections, race conditions, thread-safety
# - process synchronization: exception-safety, atomic operations
# - data synchronization:
# - types: mutex (unique, shared, recursive, timed), semaphores, barriers
# - waiting (spinlocks vs interrupts (or condition variable)) or giving up
# - problems with waiting: starvation (deadlocks, livelocks), resource leaks
/=+===============================+=\
/ : : \
)==: GENERAL :==(
\ :_______________________________: /
\=+===============================+=/
MULTIPROCESSING ==> #Several CPUs on one machine
#Unlike next ones: hardware, and related to parallelism, not concurrency
MULTIPROGRAMMING ==> #Several processes on one CPU
MULTITASKING ==> #Several tasks on one CPU
MULTITHREADING ==> #Several threads on one process (i.e. on one CPU):
# - simultaneous: at the same time
# - hyperthreading: marketing term by Intel for it
# - temporal: alternated with a "thread switch"
/=+===============================+=\
/ : : \
)==: TASKS SCHEDULING :==(
\ :_______________________________: /
\=+===============================+=/
SCHEDULING ==> #Handling tasks state:
# - can be running, idle, blocked, to be removed
# - process Control Block (PCB) or switchframe: current tasks and process state, kept by OS
TASK SWITCH ==> #When current task changes.
#Can allow it:
# - async cancelable: anytime
# - sync cancelable: on specific "cancelation points"
# - uncancelable: never
#Can be triggered by:
# - cooperative: current instruction
# - preemptive: external event
#Can be:
# - precise: interrupts at stable cancellable point and goes back to it
# - imprecise
COOPERATIVE ==> #Can be:
# - precise, e.g.: sleep, yield, lock release
# - imprecise (exceptions): e.g. software interrupt, i.e. CPU exception (e.g. runtime error)
#Benefits: might be easier to code by being more geared towards structured programming
PREEMPTIVE ==> #Using hardware interrupt / interrupt request (IRQ):
# - e.g. devices
# - including input, network
# - including IRQ0, i.e. clock timer
# - usally OS allowing IRQ use max "time slice" for a given task before task switch
# - trigger interrupt handler / interrupt service routine (ISR)
# - masking:
# - prevent handlers from being fired
# - non-maskable interrupts (NMI) do not allow it
# - rate limiting often used to prevent handlers from taking whole resources ("interrupt storm")
#Benefits:
# - performance
# - might be easier to code by avoiding too many structures
#Reentrancy:
# - can be paused by interrupts without problems
# - possible problems:
# - (main one) using global variables
# - self-modifying code
OS VS USERSPACE ==> # - OS: less control, but can use multiple CPU cores, i.e. parallel
# - userspace: more control, but single core, i.e. not parallel
TASK DEPENDENCIES ==> #Sync|blocking:
# - runs then yields
# - joining: making a task block on another
#Async|non-blocking:
# - yields then runs
# - communicate end by using interrupts
/=+===============================+=\
/ : : \
)==: PRIMITIVES :==(
\ :_______________________________: /
\=+===============================+=/
TASK ==> #Process, thread or fiber
PROCESS ==> #Own memory (address space), I/O resources (file handles)
#Need IPC (files, sockets) for communication
#Requires most CPU/memory resources
#Most isolated, i.e. secure and fault tolerant
#OS, pre-emptive scheduling
THREAD ==> #Different lines of execution within process.
#Share process memory with other threads. Also has own thread-local storage (TLS)
#Has own code stack (~2MB)
#According to privileges, can be kernel or user thread
# - kernel thread can switch address space
#Easier communication, but requires more synchronization
#OS, pre-emptive scheduling
GREEN THREAD ==> #Thread that is in userspace (e.g. Java VM). Still pre-emptive scheduling.
PROTOTHREAD ==> #Thread that share same code stack
FIBER ==> #Like thread but userspace, co-operative scheduling.
GENERATOR/SEMICOROUTINE ==> #Like fiber but with language syntactic sugar to declare it within functions, e.g. "yield"
#Can communicate to parent, e.g. "yield VAL"
COROUTINE ==> #Like generator but parent can communicate to child, e.g. "VAL = yield"
GOROUTINE ==> #Like coroutine but using OS threads under hood, i.e. co-operative scheduling but benefit from OS scheduling too.
#Use a threads pool:
# - each time goroutine yields, return thread to pool.
# - when continue, inverse.
#Specific to Go
ACTORS ==> #Similar to goroutine but instead of functions, use more generic concept|model "actors": logic + state + messages
#More generic, i.e. can be implemented using threads, processes, different machines, fibers, etc.
#Formalizing|declaring logic|state|messages allows for optimizing orchestration and shared state sync
#Message passing is async with no return value, i.e. no sync needed
# - sometimes a dispatcher is used as an abtract layer for incoming messages
/=+===============================+=\
/ : : \
)==: RESOURCES :==(
\ :_______________________________: /
\=+===============================+=/
RESOURCE ==> #Anything that can be used by competing tasks
#Can be:
# - processing: e.g. CPU. Handled by OS timesharing
# - memory: e.g. file, socket, variable
#Ownership (i.e. usage):
# - exclusive vs shared
# - write vs read
DEPENDENCIES ==> #Can be:
# - "output": both A and B write to same resource
# - "input": both A and B read same resource
# - "true|flow": A writes to resource read by B
# - "anti": inverse, i.e. B read resource written to by A
CRITICAL SECTION ==> #Code section assuming exclusive ownership over a given resource
#Collision:
# - when two tasks critical sections happen at same time
# - i.e. assume exclusive ownership but do not have it
# - race condition: when collision is time-dependent (i.e. non-deterministic)
# - compiler|interpreter can also re-order statements within a specific task, because
# it does not change that task behavior in isolation, but it might impact other tasks
# using shared resource
COLLISION SOLUTIONS ==> #Can use:
# - process synchronization: making context switches (interrupts, exceptions):
# - not harmful (exception-safety), i.e. avoid critical sections
# - impossible (atomic operations), i.e. minimize critical sections
# - data synchronization: preventing resource ownership
# - can reduce parallelism|multithreading, so prefer process synchronization
#Thread-safety: avoiding collisions
IDEMPOTENCY ==> #Idempotency can be used to prevent collisions
/=+===============================+=\
/ : : \
)==: PROCESS SYNCHRONIZATION :==(
\ :_______________________________: /
\=+===============================+=/
EXCEPTION SAFETY ==> #Code section that, when exceptions are thrown, does not induce:
# - collisions
# - memory leak
#RAII:
# - pattern when creating|destroying resource also locks|unlocks it
# - i.e. make it exception-safe providing object is automatically destroyed when exception is thrown
ATOMIC OPERATIONS ==> #Making critical section so short no context switch can happen, e.g. single CPU instruction
#Buffering prevent atomicity, since it delays operation
#"read-modify-write" operation:
# - atomic operation doing several instructions
# - e.g.:
# - compare-and-swap (CAS): if X == Y { X = Z }
# - optimistic concurrency control: X = Y; if X == Y { V = Z }
# - test-and-set: X2 = X; X = Y; return X
# - fetch-and-add: X += Y
/=+===============================+=\
/ : : \
)==: DATA SYNCHRONIZATION :==(
\ :_______________________________: /
\=+===============================+=/
MUTEX ==> #Flag:
# - checked and set when owning resource
# - unset when released, by same tasks having set it
#Types:
# - unique: 1 task owns write+read
# - shared: 1+ tasks own read, prevent write
# - recursive: can set flag several times, i.e. it must unset several times
# - timed: unset flag after timeout
#Monitor: class whose methods require locking a mutex
SEMAPHORE ==> #Like recursive mutex, except flag can be unset by other tasks that ones that set it
BARRIER|RENDEZVOUS ==> #Like semaphore, except action is delayed until resource locked
WAITING ==> #Implies locking, i.e. blocking other tasks, which can wait using:
# - spinlocks (spinning / busy waiting / software-driven), i.e. sync:
# - repeatedly test if resource locked
# - polling|sleeplock: when there is a fixed sleep time
# - interrupts (interrupt-driven), i.e. async:
# - wait for interrupt
# - condition variable:
# - application-level alternative to interrupts
# - task subscribe to a conditional variable, in order to own resource
# - other tasks notify change of condition to conditional variable, in order to potentially release resource
# - benefits of each: see above sync vs async
#Alternative to waiting: giving up
PROBLEMS WITH WAITING ==> #Starvation (endless waiting):
# - deadlock: mutual starvation, i.e. several tasks need the others' resources and cannot release their own until others acquired
# - livelock: deadlock where there is a function trying to solve it, but it always end up in a new deadlock
#Priority inversion:
# - A (high priority) waits for C (low priority) resource, B (middle priority) waits for nothing
# - i.e. B prevents C from running, which prevents A from running, even though A has more priority than B
# - can solve with priority inheritance: making C temporarily high priority because it is required by A
#Resource leaks:
# - incur if resource not unlocked after use
# - e.g. memory leak, handle leak
# - resource tracking: automatic search of resource leaks (e.g. garbage collection)