Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / A Distributed Mutual Exclusion Primitive
A Distributed Mutual Exclusion Primitive.
Description:
You are asked to develop a distributed mutual exclusion primitive for a number of processes running on the computers on a single switched LAN (our Linux lab).
System Architecture:
Process1 Process2 Process3 Process4 ...
| | | |
| | | |
| LAN | | |
|------------------|--------------|---------------|-----
The client and servers are running Network File System (NFS) so that user files are visible at $HOME directory. You may want to set up the following environment:
Your implementation must follow the distributed mutual exclusion algorithm descrbied below.
Requesting the critical section:
(a) When a site S i wants to enter the CS, it broadcasts a timestamped REQUEST message to all other sites.
(b) When site S j receives a REQUEST message from site S i , it sends a REPLY message to site S i if site S j is neither requesting nor executing the CS, or if the site S j is requesting and S i ’s request’s timestamp is smaller than site S j ’s own request’s timestamp. Otherwise, the reply is deferred and S j sets RD j [i]=1
Executing the critical section:
(c) Site S i enters the CS after it has received a REPLY message from every site it sent a REQUEST message to.
Releasing the critical section:
(d) When site S i exits the CS, it sends all the deferred REPLY messages: ∀j if RD i [j]=1, then send a REPLY message to S j and set RD i [j]=0.
Notes:
Test:
To demonstrate your distributed mutual exclusion primitive is working, you must provide a test program that is running at all computers listed in your process.hosts file. In the test, you may want to simulate a bank account balance inquiry, deposit, and withdraw operations from all computers. The application program must invoke the distributed mutual exclusion primitive before and after the actually bank account read/write operations.
Implementation Guidance:
1. Message Structure:
struct msg_packet {
unsigned short cmd; // command, e.g., HELLO | HELLO_ACK | REQUEST | REPLY (HELLO & HELLO_ACK are additional command for debugging purposes)
unsigned short seq;
unsigned int hostid; // this is optional because you can obtain the host (sender) information from the ip header, we add this fied for the convenience.
unsigned short vector_time[10]; // support upto to 10 hosts
};
2. process.hosts:
You may artificially give an ID to each host. For example:
turing11.eecs.csuohio.edu 0
turing12.eecs.csuohio.edu 1
turing13.eecs.csuohio.edu 2
turing14.eecs.csuohio.edu 3
Therefore, the timestamps will be in the same order for each host. The host ID is also useful for managing the deferred array.
3. Blocking:
As I mentioned in the class, when a process sends a request but does not receive all replies, this process will be blocked until it receive all the replies.
When you use the UDP platform, this blocking is automatically done for you when you invoke recvfrom function. Note, you need to maitain a counter that counts how many REPLY messages you receive from all other hosts. If no enough REPLY received, you still need to call recvfrom function (and therefore the process is blocked).
Requirements:
1. You can only use C programming lanuage to complete this project. Your implementation should not rely on any extra library (to compile your code). Your code must compile by using gcc installed on the Linux workstations in FH 133.
2. Your distributed mutual exclusion primitive must be based on message passing. It's up to you to choose either RPC or UDP based network communications as your messaging system.
3. Your distributed mutual exclusion primitive must provide a clean interface (API) such that application programmers only need to invoke the lock and unlock calls before and after the program enters the critical section. While the lock is not available, the calling process must be suspended and be waiting for the availability of the lock. Busy waiting is not allowed.
4. Makefile: you need to provide a Makefile that allows the instructor to compile your code by simply typing "make"
5. Write-up: you are required to write a README document (in txt format) that describes your project design detail and the execution sequence (with the commands). In particular, please explicitly state which part, if there is any, does not work and the possible reasons why that module does not work. For those working modules, please give a brief (in short) sample output.
*********************** Further Hint: Implementation Details. ************************************
DIstributed Mutual Exclusion API:
1. distributed_mutex_init();
// for initialization, should be called by the user who wants to use the distributed_mutex primitive;
// in addition to variable initialization, init() should create a pthread that is listening on port 0x3333 (for incoming message)
2. distributed_mutex_lock();
// before the calling user enters in the critical section, the user must obtain this lock. Or the user should be waiting
3. distributed_mutex_unlock();
// it's the user's responsibility to call unlock before leaving the critical section. this API should send queued (deferred) REPLY messages to the sending hosts according the procotol described above.
The duty of the spawned thread is to process the incoming message. It's duty includes, but not litmited to, in the following:
1. If the host receives a REQUEST message and the host is not requesting, sends a REPLY immediately;
2. If the host receives a REQUEST message and the host is also requesting:
a) the host has a vector time earlier than that of REQUEST, defer the REPLY and put the REQUEST in the queue;
b) the host has a vector time later than that of REQUEST, sends a REPLY immediately.
3. If the host receives an other message, e.g., HELLO, replies an ACK immediately.
The communication between the spawned thread and the main thread (distributed_mutex_lock()) can be done through pthread semaphore:
int distributed_mutex_lock(void) { // parameter setting is up to you
sem_init(&sem, 0, 4); // creatte a semaphore with a value of 5 (assuming there are 5 hosts, so we need to collect 4 REPLYs to proceed)
send REQUESTs to other hosts for entering CS
sem_wait(&sem); // if the value goes below 4, the distributed_mutex_lock will wait until someone else adds
// reached here since all REPLYs are collected
return 0; // allow the user to enter CS
}
In your spawned thread that processes the incoming messages, if it is a REPLY message, then you should do: sem_post(&sem).
***************************************************************************************************************
Grading criteria:
1. If your implementation only support 2 hosts, your highest score will be 60%.
2. If your implementation only support 3 hosts, your highest score will be 80%.
3. You can earn 100% if your implementation supports 4 or more hosts.
4. Test platform establishment (20%): any host is able to communicate with all other hosts.
5. Vector time management (20%): correctly maintain and update vector timestamps for all hosts (including self).
6. Correctly executing the distributed mutual exclusion algorithm (30%).
7. Application test program development (20%): implementation of a comprehensive test application (balance check/deposit/withdrawal) and capture of the test results.
8. README (10%).
9. Bonus (up to 50% extra):
If your improvement (compared to project3), in term of the grade, is over
50%, e.g., from 10%-->60%, you will be awarded extra 50%
40-49%, you will be awarded extra 40%
30-39%, you will be awarded extra 30%
20-29%, you will be awarded extra 20%
10-19%, you will be awarded extra 10%
If your project4 receives 80% or above, you will be awarded extra 50% regardless how much improvement you have made compared to project3.
The above bonus can only be awarded once.
Submission:
