Distributed_system
多个server的concurrency解决思路
Centralized Approach 中央集权
- what: 直接指派一个作为中央
- why:easy and gurante
- how: 3 messeages per cs entry : (request, permission, done)
- problem: central dies and threads dies in the cs
lamport timestamp
- what: global pripority queue for cs. send to each node request
- why: every node know what happens.
- how: 3(N-1) messeages per requests (request,reply,release)
- problem: no falut tolerant. message may not arrive in time, especially when sending requst
Ricarti and Agrawala timestamp approach
- what: combine reply and release. change global queue to voting.
- why: reduce message number
- how: send request to others and if other agree(not in CS, or in cs and exit will reply) will reply. Get enough vote can start. 2*(n-1) messages.
- problem: workhorses. too much messages. Even a single failure can disable the entire system. Both timestamp approaches require more messages than a centralized approach -- and have lower fault tolerance. The centralized approach provides one single point of failure (SPF). These timestamp approaches have N SPFs.
Voting
- what: send request to others, if other have voted, put it in queue. When one exit cs, it send release to others and other could handle request in the queue.
- why: only majority agree is ok. change the way of message and queue.
- how: break ties could use lamport time. break deadlock when no one win, use inqure message, and other could vote again.It sends an INQUIRE message to the candidate for who it voted. If this candidate won the election, it can just ignore the INQUIRE and RELEASE normally when done. But, if it hasn't yet entered the critical section, it gives back the vote and signals this by sending back a RELINQUISH. Upon receipt of the RELINQUISH, the voter is free to vote for the preceding request.
- problem: less message. (3+x)(1/2 N+?) request, vote, release
voting districts
- what: send message to districts, just in the same line and cloumn.
- why: reduce message
- how: same voting techniques. 3*(2sqrt(N)-1)
- problem: not falut tolerant, no deadlock. one server die may change.选择多个进入cs
token ring
- what: everyone know successor, and move token one by one. hold it until done cs
- why: fault tolerance. good at high contention
- how: if one dies with token, last one see time out and generate a new one. Under high contention, message low. Every one has limited time with token.
- problem: not good at low contention.
raymond's algorithm
- what: use tree to pass token ring.
- why: more quick in low contention
- how: pass by node.
- problem: worst case, travel long
path compression
- what: allow short cut to pass token ring
- why: current_dir may out-of-date, when request happened, node can get into current_dir end and enqueue in next queue.
- how: use a queue of pending request with current_dir and next. current_dir point to next waiting, next is current(with token) point to waiting.
Children