Concurrency Flashcards
(25 cards)
What is an atomic instruction
is an instruction, when executed doesn’t get interleaved with another process
what is a critical section
it’s a piece of code that tries to be executed by several processes
what is mutual exclusion
the execution of the critical section must never be interleaved
what is deadlock
happen when a process waits for another indefinitly
what is starvation
can be defined such that when a process wishing to enter its critical section, doesn’t have to wait indefinitely
livelock
when processes are constantly changing but none of them can proceed
cite the five states of a process
inactive –> ready running –>completed
^ |
|___ _ __ __ |—> blocked
Semaphores
S : { V : integer , L : set of processes }
initialized S –> (K, ∅)
Which unrealistic assumption is required for the correctness of the Ricart-Agrawala algorithm
it’s illogical to assume that all nodes would always answer
what is the idea behind the bakery algorithm?
the idea is to give processes tickets with increasing number, and the waiting process having the smallest ticket number is server first
explain the bakery algorithm for n process
each process would pick the max ticket number that is exactly greater than the max loop forever p1: non-critical section p2: number[i] ← 1 + max(number) p3: for all other processes j p4: await (number[j] = 0) or (number[i] ≪ number[j]) p5: critical section p6: number[i] ← 0
each time the process with the lowest ticket number is chosen in case of conflict, we choose the lowest identifier however, this algorithm is unrealistic because it making the assumption that the max number is an atomic operation the following fixes that loop forever p1: non-critical section p2: choosing[i] ← true p3: number[i] ← 1 + max(number) p4: choosing[i] ← false p5: for all other processes j p6: await choosing[j] = false p7: await (number[j] = 0) or (number[i] ≪ number[j]) p8: critical section p9: number[i] ← 0
what is a blocked process?
it is a process that is not eligible to run
explain semaphores
semaphore is composed of two :
s.v -> unsigned integer
s.L -> list of processes
wait(s) decrement, else the process, else the process is added to the waiting list
signal(s) increment and the process may resume the execution
▶ wait(S)
if S.V > 0
S.V ← S.V - 1
else
S.L ← S.L + p
p.state ← blocked
▶ signal(S)
if S.L = ∅
S.V ← S.V + 1
else
let q be an arbitrary element of S.L
S.L ← S.L \ {q}
q.state ← ready
explain what is the flaw of the semaphore and how to fix it
in the previous definition, semaphore may lead to starvation because each time the processes are chosen arbitrarily, this can be fixed by setting up a FIFO to put the processes in
what is a synchronization problem?
it s the problem that arises when several processes compete for shared resource
explain how to solve the merge sort problem using synchronization
sorting the fist half and the second half is independent however the emerging must wait that they finish : Array a binary semaphore S1 ← (0, ∅) binary semaphore S2 ← (0, ∅) sort1 sort first A.half1 signal(S1) sort2 sort A.half2 signal(S2) merge : wait(S1) wait(S2) merge(A.half1, A.half2)
implement producer, consumer using the semaphores
producer: loop : d -> produce append(d, buffer) signal(not_empty)
consumer :
loop
wait(not_empty)
consume(buffer)
implement producer-consumer with semaphores for a finite buffer
Since buffers are finite, then we must ensure not to write to a full buffer producer: loop : d -> produce wait(not_full) append(d, buffer) signal(not_empty)
consumer : loop wait(not_empty) consume(buffer) signal(not_ful;)
why in the Ricart-Agrawala algorithm, tickets number can not be compared
it is an algorithm for mutual exclusion in a distributes system
because there is no shared memory between them
another point to consider is the fact that the process should only die out of it critical section
explain Ricart-agrawala algorithm
Initially,
1-the highest number process is chosen
2 -a request is sent by this process, to all the node to get permission to enter the critical section
3- in the receiving the priority is compared then decides whether to send the request or add the process to the deferred list
what are the desirable properties of the distributes system
fault tolerance . one failure wont affect the whole system
fail-safety : failing won’t cause damage to the whole system
explain the consensus problem
There are duplicate CPUs and sponsors and values are filtered by a comparator
initially, each node picks a value and sends it to the others, then through the majority vote algorithm, a value is chosen, since the source of the data is the same thus making the same final choise
explain the consensus system failures
crash failure: node ceases to send messages
byzantine failure: node send erroneous messages
how to solve the byzantine problem
By using the two rounds algorithm
in the first round, every node send its plan to all the other nodes
in the second round, every node sends the received data to all the other nodes
