- Greetings and felicitations!
- Maekawa's Algorithm
- Request sets satisfy the following conditions:
- for all 1 <=
*i*,*j*<=*n*with*i*!=*j*,*R*INTERSECT_{i}*R*!= NULLSET_{j} - for all 1 <=
*i*<=*n*,*p*IN_{i}*R*_{i} - for all 1 <=
*i*<=*n*, |*R*| =_{i}*K* -
*p*is contained in_{j}*K*number of*R*_{i}

- for all 1 <=
- Idea: every pair of processes has has a mediator (in both request sets) to mediate conflicts
- Only one outstanding REPLY per process, so each process gives permission to enter to only one other process
- Assumes messages delivered in order which they are sent
- To avoid deadlock, can INQUIRE whether someone cannot get it
- A FAILED message just means someone else is going in out of order
- Performance: between 3
*N*and 5*N*messages

- Request sets satisfy the following conditions:
- Sanders' generalized protocol
- Inform set
*I*is set of processes to be informed when_{i}*p*enters or leaves CS_{i} - Status set
*ST*contains pids for which_{i}*p*maintains status information; note:_{i}*p*IN_{i}*I*=>_{j}*p*IN_{j}*ST*_{i} - If
*p*IN_{i}*I*for all_{i}*i*, then necessary and sufficient conditions to guarantee mutual exclusion are: *I*SUBSET_{i}*R*_{i}*I*INTERSECT_{i}*I*!= NULLSET or (_{j}*R*IN_{i}*R*and_{j}*p*IN_{j}*R*)_{i}

- Inform set
- Suzuki-Kasami's broadcast protocol
- token-based
- uses sequence numbers, not clocks
- token has sequence numbers, associated queue
- how to handle stale requests? token's sequence number too high

- Raymond's tree-based protocol
- token-based
- think of token as at root of tree, root moves around

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu | Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print. |