程序代写代做代考 database algorithm Mutual Exclusion and Quorums

Mutual Exclusion and Quorums

CS 171

MUTUAL EXCLUSION & QUORUMS

CS 171

Distributed Mutual Exclusion

• Given a set of processes and a single
resource, develop a protocol to ensure
exclusive access to the resource by a single
process at a time.

• This is a fundamental operation in operating
systems, and is generalized to locking in
databases.

CS 171

Centralized algorithm

• One process elected as coordinator

Crequest(R)

grant(R)

1. Request resource

2. Wait for response

3. Receive grant

4. access resource

5. Release resource

release(R)

CS 171

Centralized Solution

• But we can have multiple concurrent requests!

• Coordinator maintains queue of pending requests.

• Protocol:
– Process send request to coordinator.

– If no other request, coordinator sends back reply.
• Otherwise, put request in queue

– On receipt of reply, process accesses resource.

– Once done, process sends release to coordinator.

– On receipt of release, coordinator checks queue for any
pending requests.

CS 171

Centralized Solution

C
request(R)

reply(R)

release(R) P1

request(R)

Queue

request(R)

reply(R)

5
thanks paul krzyzanowski rutgers

CS 171

Centralized Approach

• Does it satisfy requests in order the requests
are made?

CS 171

Lamport’s Distributed Solution

• Instead of a central coordinator, all processes
collectively

• Use similar approach, but engage ALL
processes.

• Each request is time stamped with:

– Lamport Logical Time + Identifier (process ID)

– Ie, Timestamps are totally-ordered Lamport pairs.

CS 171

Lamport’s Distributed Solution

– Process sends time stamped request to all processes
and puts request in local queue.

– On receipt of request
– process puts request in queue and sends back reply.

– Process accesses resource
• On receipt of all replies

• Own request at head of queue

– Once done, process sends release to all processes.

– On receipt of release, process removes request

CS 171

Distributed Solution
• Does this work (Lamport original solution)?

• Need to order queues so they are identical:

– Use logical Lamport time + proc id to break ties.

– FIFO channels

• Requests are executed in causal order.

– Why?

CS 171

Example

P0 P1

P2 P3

Assume that process P0 and process P2 need to access the
shared resource at the same time.

Queue

request P0

request
P2

request

Queue

request

Queue

request

CS 171

Example

P0 P1

P2 P3

Using process id to break ties, process P0’s request will
end up on top of the queue, over process P2’s.

Queue

P0 P2

Queue

P0 P2

Queue

P0 P2

Queue

P0 P2

CS 171

Example

P0 P1

P2 P3

Process P0 is done and broadcasts a release message.

release

Queue

P0 P2

Queue

P0 P2

Queue

P0 P2

Queue

CS 171

Example

P0 P1

P2 P3

When process P2 is done with the shared resource, it
also broadcasts the release message.

release

Queue

CS 171

Complexity of Lamport’s Solution
• This algorithm creates 3(N − 1) messages per

request:

• (N − 1) total number of requests

• (N − 1) total number of replies

• (N − 1) total number of releases

• Can we reduce the number of messages while
maintaining the same guarantees?

CS 171

Quorums

• What if there are failures?

• Mostly network failures

• No failure of the resource holder

• Do we need to communicate with ALL
processes?

• A quorum is the minimum number of votes that
a process has to obtain in order to be allowed
access to the shared resource.

CS 171

Quorums

• Any two requests should have a common
process to act as an arbitrator.

• Vi is called a quorum.

• Let process pi (pj) request permission from Vi (Vj), then

Vi ⋂ Vj ≠ Ø

CS 171

Quorums

• Given N processes: |Vi| > N/2, ie,

• In general, majority, ie ⌈(N/2)⌉.
[Gifford 79]

Basic MUTEX Protocol
• Requesting CS

– process requests CS by sending request message to processes in
its quorum

– If a process receives a request it sends back reply unless it
granted permission to other process; in which case the request
is queued—similar to granting a lock

• Entering CS

– process may enter CS when it receives replys from all processes
in its quorum

• Releasing CS

– after exiting CS process sends release to every process in its
quorum—release lock

– when a process gets release it sends reply to another request in
its queue

CS 171

Example

P0 P1

P2 P3

Assume that process P0 and process P2 need to
access the shared resource at the same time.

P4
Quorums:
V0: {P0, P1, P4}
V2: {P2, P3, P4}

Queue

request
P0

Queue

request

Queue

request

CS 171

Example

P0 P1

P2 P3

Process P4 is the arbitrator since it’s common in both
V0 and V2 quorums.

replyQuorums:
V0: {P0, P1, P4}
V2: {P2, P3, P4}

Queue

P0 P2

CS 171

Example

P0 P1

P2 P3

Process P0 sends the release message to its quorum.

release

release
P4

Quorums:
V0: {P0, P1, P4}
V2: {P2, P3, P4}

Queue

P0 P2

CS 171

Example

P0 P1

P2 P3

Process P2 finishes and broadcasts to its quorum
the release message.

release

P4
Quorums:
V0: {P0, P1, P4}
V2: {P2, P3, P4}

Queue

CS 171

Deadlock

• Unfortunately, the quorums approach can
lead to Deadlocks.

• Deadlocks occur even with a single resource.

• Not the standard database or operating
system multi-object deadlock.

CS 171

Deadlock Example

P0 P1

P2 P3

Assume that process P0 and process P2 need to
access the shared resource at the same time.

Quorums:
V0: {P0, P1, P3}
V2: {P2, P1, P3}

Queue

request
P0

Queue

request

Queue

request

CS 171

Deadlock Example

P0 P1

P2 P3

P1 and P3 don’t agree on which process should
get the resource.

Queue

Quorums:
V0: {P0, P1, P3}
V2: {P2, P1, P3}

Queue

CS 171

Site Failure Example

P0 P3

P1 P2

How many sites can we afford to go down?

We can achieve quorum!

CS 171

Site Failure Example

P0 P3

P1 P2

How many sites can we afford to go down?

We can not achieve quorum!

No majority possible.

CS 171

Network failure: Partitioning

P0 P3

P1 P2

If sites are unreachable, quorum might still be
possible.

Here we can achieve quorum!

This partition won’t be able to get the resource.

CS 171

Network failure: Partitioning

P0 P3

P1 P2

If sites are unreachable, quorum might still be
possible.

No partition can now get the resource.

CS 171

Studying the Sizes of Quorums

• Can we have quorums of sizes LESS than
majority?

• Yes:

– Using logical structures

CS 171

Quorum Sizes on Logical Grid Structure

31Quorum size is O(√N)

Published by admin

Leave a Reply Cancel reply