Homework answers / question archive / A Distributed Mutual Exclusion Primitive

A Distributed Mutual Exclusion Primitive

Computer Science

Share With

---

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:

• $HOME/process.hosts: a list of computers (hostnames) which are running processes that need the distributed mutual exclusion.  There is no reason why your implementation cannot support up to 10 servers.

Your implementation must follow the distributed mutual exclusion algorithm descrbied below.

• A process sends a REQUEST message to all other processes to request their permission to enter the critical section. A process sends a REPLY message to a process to give its permission to that process.
• Processes use Lamport-style logical clocks to assign a timestamp to critical section requests and timestamps are used to decide the priority of requests.
• Each process p_i maintains the Request-Deferred array, RD_i , the size of which is the same as the number of processes in the system.
• Initially, ∀i ∀j: RD_i [j]=0. Whenever p_i defer the request sent by p_j , it sets RD_i [j]=1 and after it has sent a REPLY message to pj , it sets RD_i [j]=0.

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:

• When a site receives a message, it updates its clock using the timestamp in the message.
• When a site takes up a request for the CS for processing, it updates its local clock and assigns a timestamp to the request.

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:

1. Create a folder and name it as your group ID, concatenated with "_p4", e.g., group1_p4 (all lower case).
2. Copy all your source code to the above folder (clean your source code folder and remove all binary files).  Please do not submit any binary code! 
3. Provide a Makefile such that the instructor only needs to type "make" to compile all the binaries.
4. Edit a README file (in plain text format only) and provide the following information:
   • The group member contribution percentile: e.g., 50%-50%.
   • Design details
   • Compiling instruction and execution sequence (with commands)
   • A sample test run
   • Please explicitly state which part, if there is any, does not work and the possible reasons why that module does not work.
5. Log in grail, go to the parent director of the folder you created, and run (suppose the your folder is "group1_p4")
   $ turnin -c cis620w -p p4 group1_p4
   If there is no error message, your submission is successful.
6. Your most recent submission will always automatically overwrite the previous one.