Changes aren't done atomically. = Other threads can see partial changes
space[i][j][k] = 0.5
space[i][j][k+1] = 0.5
Thread can be preemptive. = they see inconstant state.
Case: Number of cores != number of threads
ex) 8 threads and 4 cores
limiting / throtting/ scheduling
[Solution]
Ignoring problems (Good enough sometimes)
Solve it rigorously
Bill Gates's Bank Account
int balance; // Dr. Eggert's balance in pennies.
// Dr. Eggert's maximum: 2^31-1: Roughly 20 million
long long int balance; // Bill Gates' balance in pennies.
// Bill Gates's maximum: 2^63-1
[Case 1]
What if he put more than 2^63-1?
Bank: Sorry, Bill Gates. Your balance is negative since you put too much money.
How to detect integer overflow?
gcc .ftrapv // if there is a signed integer overflow, crash it.
Problem: You will get negative amount of the money
[Solution]
long long b = balance
if(amount > b)
balance = b-amount;
With this fix, balance will never go negative.
Some more-complex actions
You want to transfer money from one account to another.
We want to put a variable that check everything is fine.
Account lock (acct1 and acct2) at the same time.
transfer(amount, acct1, acct2){
}
Needs lock both accts. which one first?
Audit(all accounts);
Take a snapshot of system state and audit it for consistency.
Do consistency check - Expensive, but necessary.
Shut down the bank for 4 hours and check everything is fine.
Prohibit all changes while we audit
Most banks have system maintenance time.
Stock trading: shut down and prohibit any transactions.
You can't audit if somebody's transferring the money.
Threads' actions could collide if something has a dependency.
Example:
Action 11 -> Action 12 -> Action 13 .
Action 21 -> Action 22 -> Action 23 .
NOT Allowed: Action happens at the same time.
Terminology
Atomicity: Action is either done or not done (with no effect.)
Sequence coordination: Action 1 must be done before action 2 starts.
Free within 1 thread.(By using ";" )
Isolation: Actions guaranteed to not interfere with other threads.
Observability
Serializability
low level actions(invisible to use)
Explained as a series of atomic high level actions well behaved in a serial order.
Pipe Implementation with Lock
It needs to be synchronized since one file is reading and one file is writing
// Read and write only one byte
enum { EMPTY = CHAR_MAX+1 };
enum N = 1024;
struct pipe{
char buf[N];
unsigned r, w;
}
R => ----------------------------------------- <= W
read starts from the left and write starts from the right
bool writec(struct pipe *p, char c){
int ret;
lock(&l);
if(p->w - p->r == N) ret = 0;
p->buf[p->w++ %N] = c;
ret = 1;
unlock(&l)
return ret;
}
int readc(struct pipe *p){
int r;
lock(&l).;
if(p->w == p->r) r = empty; // if writing amount is reading amount.
int ret = p->buf[p->r++%N];
unlock(&l);
return ret;
}
[Problem 1] "W" thinks the pipe is empty, but it could be full.
[Solution 1] Use a lock and unlock!
lock(&l);
unlock(&l);
[Precondition 1]
We don't own l - You can't lock something that you already locked.
Grab on exclusive lockon
If already locked, we busy - wait.
[Precondition 2]
You can only unlock, if we have l
[Problem 2]
Ugliness and Inefficiency
Use lock and unlock for a single byte reading/writing.
Code becomes ugly.
lock + unlock for each byte!
[Solution 2]
Bigger primitive for do more
For example, you can read buffer instead of read char.
Let's make a primitive really big.
Suppose your buffer is mega byte or gigabyte.
[Problem 3]
threads have to wait a long time.
Synchronization = mutual exclusion + bounded wait
Program does not make a progress.
We want guarantee: if thread has a lock, it will give up *soon*.
Assume preemption or plenty of CPUs.
[Solution 3]
Don't use only single lock inside the function.
Declare lock instance variable inside of the pipe struct.