Transcript process i - Georgia State University

Transactions are communications with ACID property:
• Atomicity: all or nothing
• Consistency: interleaving results in serial execution in some order
• Isolation: Partial results are not visible outside
• Durability: After committing, the results are permanent
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Participant:
1.
Prepare to commit the transaction by writing every update in activity
log.
2.
Write a precommit message in the activity log. Wait for request to
vote from coordinator.
3.
Wait for commit message from the coordinator. If received, commit
the transaction. If abort message is received, abort the transaction.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Coordinator:
1.
If the processor crashes, it will check the activity log for the
transaction.
2.
If the precommit message is not in the log, abort the transaction.
3.
If the commit message is not in the log, retake the vote.
4.
If the commit message is there in the log, finish the transaction.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
•
Contention based
Lamport’s algorithm, Ricart & Agrawala’s algorithm, Voting algorithm
•
Token based
Ring structure, tree structure, broadcast structure
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Every process maintains a queue of pending requests for
entering critical section ordered according to the logical timestamp.
Requestor:
1. Send a request to every process.
2. After all replies are collected, enter its own request in
its own queue
3. If own request is at the head of the queue, enter critical
section.
4. Upon exiting the critical section, send a release
message to every process.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Other processes:
1. After receiving a request, send a reply and enter the
request in the queue
2. After receiving release message, remove the
corresponding request from the queue.
3. If own request is at the head of the queue, enter critical
section.
Problems:
• 3(N-1) messages per requests
• Multiple points of failure
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Requestor:
1. Send a request to all other process.
2. Enter critical section upon receipt of reply from all
processes.
Other Processes:
1. Upon receipt of a request check whether it has any
older (by logical clock) pending request of its own or
whether it is executing in critical section.
2. If neither of the above conditions hold, send reply.
Otherwise delay the reply message till both the
conditions are false.
Problems:
1. 2(N-1) message exchange per request.
2. Multiple points of failure.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Requestor:
1. Send a request to all other process.
2. Enter critical section once REPLY from a majority is
received
3. Broadcast RELEASE upon exit from the critical
section.
Other processes:
1. REPLY to a request if no REPLY has been sent.
Otherwise, hold the request in a queue.
2. If a REPLY has been sent, do not send another REPLY
till the RELEASE is received.
Observations:
1. No single point of failure, but possibility of deadlock.
2. O(N) messages per request.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Deadlock prevention method is used by ensuring no hold-and-wait
Requestor:
1. Send a request with time stamp to all other process.
2. Enter critical section once REPLY from a majority is
received
3. Return the REPLY message upon receipt of an
INQUIRY if not currently executing in the critical
section.
4. Broadcast RELEASE upon exit from the critical
section.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Other processes:
1. If no REPLY has been sent, REPLY to any REQUEST.
2. If a REPLY has been sent but the RELEASE has not
been received, compare the time stamp of the new
REQUEST with the time stamp of the replied REQUEST.
If the new REQUEST has an earlier time stamp, try to
retract the old REPLY sending INQUIRY message. If the
older REPLY is returned, send REPLY to the new
REQUEST. Otherwise, wait for the RELEASE.
Observation:
1. High (O(N)) messages per critical section entry.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
To reduce message overhead, the set of (N) processes is divided into N
sets S1 to Sn such that Si I Sk is non-null for all i and k. Si is called the
quorum of process i.
Requestor:
1. Need to secure the REPLY messages from all members
of its quorum only.
Observations:
1. It is possible to reduce number of messages
significantly.
2. Depending on the structure of the quorum and the
exact algorithm, single point of failure may exist.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Control-token circulates in the system in some fixed order. Possession of
the token grants permission to enter critical section.
• Ring structure – simple, deadlock-free, fair. The token circulates even in the absence
of any request (unnecessary traffic). Long path (O(N)) – the wait for token may
be high.
• Tree structure
• Broadcast structure
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
The processes are organized in a logical tree structure, each node pointing
to its parent. Further, each node maintains a FIFO list of token requesting
neighbors. Each node has a variable Tokenholder initialized to false for
everybody except for the first token holder (token generator).
Entry section:
If not Tokenholder
If the request queue empty
request token from parent;
put itself in request queue;
block self until Tokenholder is true;
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Exit section:
If the request queue is not empty
parent = dequeue(request queue);
send token to parent;
set Tokenholder to false;
if the request queue is still
not empty, request token from parent;
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Upon receipt of a request:
If Tokenholder
If in critical section put the requestor in the queue
else
parent = requestor; Tokenholder = false;
send token to parent;
endif
else
if the queue is empty
send a request
to the parent;
put the
requestor in queue;
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Upon receipt of a token:
Parent = Dequeue(request queue);
if self is the parent
Tokenholder = true
else
send token to the parent;
if the queue is not
empty
request token
from parent;
Note that all requests/token receipts must be processed in
FIFO order and the routines must execute atomically.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Data Structure:
The token contains
Token vector T(.) – number of completion of the critical section
for every process.
Request queue Q(.) – queue of requesting processes.
Every process (i) maintains the following
seq_no – how many times i requested critical section.
Si(.) – the highest sequence number from every process i heard of.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Entry Section (process i):
Broadcast a REQUEST message stamped with seq_no.
Enter critical section after receiving token.
Exit Section (process i):
Update the token vector T by setting T(i) to Si(i).
If process k is not in request queue Q and there are pending
requests from k (Si(k)>T(k)), append process k to Q.
If Q is non-empty, remove the first entry from Q and send the
token to the process indicated by the top entry.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Processing a REQUEST (process j):
Set Sj(k) to max(Sj(k), seq_no) after receiving a REQUEST from
process k.
If holds an idle token, send it to k.
Requires broadcast. Therefore message overhead is high.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Used to elect a centralized controller if the older one fails. The
election of a new controller helps to alleviate some of the
problems arising from having a single point of failure.
Two types of election algorithm
• Extrema- finding – based on global priority
• Preference-based – based on local preferences.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Election algorithms and mutual-exclusion algorithms are similar in the sense that
they try to find one process that will be leader or enter the critical section. However,
there are significant differences between two.
1.
Leader election is one time. A process may yield to another process. In
mutual exclusion algorithm, a process competes until it succeeds.
2.
In leader election starvation is not an issue.
3.
Once the leader is elected, all other processes must know who is the
leader.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Election algorithms are designed on the basis of the logical topology of the group of
the processes.
1.
Complete topology
2.
Ring
3.
Tree
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Assumptions:
1.
A process may reach all other processes in one logical hop.
2.
Communication is reliable, only processes may fail.
3.
Time to handle a message is bounded.
4.
Process faults are benign, i.e., a faulty process stops to generate
messages. In other words, a process never generates confusing wrong
messages.
5.
Upon recovery, a process knows that it experienced a failure.
6.
A failed process may rejoin the group upon recovery.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Our algorithm is an extrema-finding algorithm. It is called the bully
algorithm.
Upon detecting that the leader has failed, a process sends an inquiry
message to all higher-priority processes. If no reply is received within
the time-out period, the initiator sends an enter-election message to all
lower priority processes. After the initiator receives a reply from all
lower-priority processes or after the time-out, it declares itself as new
leader and broadcasts that information to all processes.
If a process receives an inquiry message from a lower priority process,
it send inquiry message to all higher priority process and enters election.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
Our algorithm is an extrema-finding algorithm. The processes are organized
in a logical ring.
The initiator sends a message along ring with its own id.
Requesting everybody to elect it the leader.
A process compares its own priority with that of the id. on an
incoming message. If its own priority is higher, and it never
forwarded any other messages, replace the message with its own
id. and forward it. If its own priority is lower, forward the message.
If the message carries its own id. then elect itself the leader and
forward the election message.
Message complexity O(N2) in the worst-case, O(N) in the best-case.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan
There are two types of election algorithms those use the
logical tree topology.
1. The algorithm runs after the spanning tree is
constructed.
2. The algorithm runs before the spanning tree is
constructed and constructs the spanning tree in the
process.
CSC 8420 Advanced Operating Systems
Georgia State University
Yi Pan