Cs 345 Project 4 - Dme

Distributed Mutual Exclusion CS 345 - Project Four

Purpose When two or more tasks in a distributed system compete for the use of system resources, there is a requirement for a mechanism to enforce mutual exclusion. New difficulties arise and new solutions are needed when dealing with a distributed operating system that does not share memory or a clock. Consequently, algorithms for mutual exclusion and deadlock must depend upon the exchange of messages without relying upon common memory semaphores. Project 4 is designed to help the student:    

understand mutual exclusion in a distributed system. understand clock and messaging synchronization. understand the client/server relationship with sharable resources. solidify concepts of task communication and synchronization.

Project Requirements The following are important guidelines for programming the DME assignment: 1) Distributed Message Communication: All communication between tasks must be via POSTMESSAGE and GETMESSAGE directives. These functions simulate socket connections between participating task peers in a distributed system. 2) Clock Synchronization: Fundamental to the operation of most distributed algorithms for mutual exclusion and deadlock prevention is the temporal ordering of events. The lack of a common clock or a means of synchronizing local clocks is thus a major constraint. To overcome this problem, a method of time stamping must be implemented which will order events (transmitted messages) without using physical clocks. Each participating peer task in the distributed network maintains a local counter, Cid, which functions as a clock. When a message is received from a peer, the receiving task sets its clock to one more than the maximum of its current clock value and the incoming message timestamp. The event order is determined by comparing the timestamps or, if the timestamps are the same, by comparing the task id‟s. This algorithm avoids any problems of drift among various clocks of the communicating tasks. 3) Distributed Mutual Exclusion: The successful use of concurrency among tasks requires the ability to define critical sections and enforce mutual exclusion. Any facility or capability that is to provide support for full distributed mutual exclusion should meet the following requirements: a. Mutual exclusion must be enforced: only one task at a time is allowed into shared system critical sections. b. A task that halts in its non-critical section must do so without interfering with other tasks. c. It must not be possible for a task requiring access to a critical section to be delayed indefinitely: (ie., no deadlock or starvation.) BYU, CS 345

Project Four – DME

Page 1/11

d. When no task is in a critical section, any task that requests entry must be permitted to enter without delay. e. A task remains inside a critical section for only a small finite amount of time. 4) ATMs and the Bank: Project 4 simulates a distributed banking system consisting of nine remote ATMs (clients) and one centralized Bank (server). Only one ATM is allowed access to the Bank at a time and may exchange many messages for a single transaction. Thus, distributed mutual exclusion must be implemented to protect asynchronous accesses to the Bank (critical section). a) Your shell communicates with the Bank through an ATM as follows: >>atm ,,b >>atm ,,d,<$> >>atm ,,n,<$> >>atm ,<9999>,t >>atm ,,w,<$> >>atm ,,x

request balance deposit <$> into create new with balance <$> list all account balances (9999 is a password) withdraw <$> from delete

which translate to the following task messages: POSTMESSAGE (0,,"b,") POSTMESSAGE (0,,"d,,<$>") POSTMESSAGE (0,,"n, ,<$>") POSTMESSAGE (0,,"t,9999") POSTMESSAGE (0,,"w,,<$>") POSTMESSAGE (0,,"x,")

request balance of deposit <$> into new with balance <$> display summary of accounts withdraw <$> from delete

b) An ATM communicates with the Bank using the following messages: POSTMESSAGE (,10,"s,") POSTMESSAGE (,10,"b") POSTMESSAGE (,10,"d,<$>") POSTMESSAGE (,10,"n") POSTMESSAGE (,10,"t") POSTMESSAGE (,10,"w,<$>") POSTMESSAGE (,10,"x")

select request balance (of selected ) deposit <$> (into selected ) new account (selected ) request summary of all accounts (=9999) withdraw <$> (from selected ) delete account (selected )

The Bank communications back to the ATM as follows: POSTMESSAGE (10,,"+,<$>") POSTMESSAGE (10,,"b, = <$>") POSTMESSAGE (10,,"-,error msg")

request succeeded (return results) request account balance request failed

c) Communication between ATMs is through separate peer DME tasks, which are to implement the DME solution as described below. Before an ATM accesses the Bank, it first requests permission from its associated DME task. After completing the bank transactions, the ATM communicates with its DME task which releases the Bank critical section for other ATMs.

BYU, CS 345

Project Four – DME

Page 2/11

POSTMESSAGE / RECEIVEMESSAGE Directives All communication between tasks must be via POSTMESSAGE and GETMESSAGE directives. These directives simulate the common operating system mechanisms of sockets, ports, and pipes. Sockets are similar to pipes in that they allow tasks to send and receive information, but also often over long distances such as networks or the Internet. Low-level sockets establish a connection between tasks using an IP address and a port number. A connect operation establishes a connection with a remote listening server and the accept operation, on the server side, returns the connected socket. Once two sockets are connected, they exchange information as streams of bytes that are interpreted any way the two sides have agreed upon. For Project 4, socket operations are simulated using the POSTMESSAGE and GETMESSAGE directives. The nine ATM client tasks (tasks 1-9) and the Bank server task (task 10) make up the distributed system. In addition, there are 9 associated DME tasks (tasks 11-19) that participate as peers in the DME process. The shell communicates only with ATMs from port 0 to ports 1-9 and does not participate in the distributed mutual exclusion process (it is not a peer.) The ATMs communicate with the Bank through ports 11-19 to port 10, and the associated socket peer tasks through ports 11-19 to ports 21-29. The DME tasks communicate with each other using ports 21-29. A message (character string) is sent to another task with the POSTMESSAGE directive, using task arguments as source and destination addresses (ports). The GETMESSAGE directive returns a queued received message on a specific connection (from, to). When a message is sent using the POSTMESSAGE directive, the message is placed in the message buffers and the port message ready counting semaphore for the destination socket (msgReady[TID]) is signaled. A task wanting to receive a message uses the GETMESSAGE directive, which waits on its port message counting semaphore (msgReady [TID]) before retrieving the message from the message buffers.

BYU, CS 345

Project Four – DME

Page 3/11

DME Queue Algorithm Distributed mutual exclusion can be implemented using timestamps and a delay queue within each participating peer DME task. This algorithm is based on the following assumptions: 1. A distributed system consists of N nodes, uniquely numbered from 1 to N. Each node contains one task that makes requests for mutually exclusive access to resources on behalf of other task(s). This task also serves as an arbitrator to resolve incoming requests that overlap in time. 2. Every message is correctly delivered to its destination in a finite, ordered amount of time. 3. The network is fully connected; this means that every task can send messages directly to every other task, without requiring an intermediate task to forward the message. For an ATM to acquire the Bank resource: 1. ATM (client) sends a request message (Request, myClock, IDmy) to all other connected ATM„s (peers). ATM saves the time of the request (Tmyreq) and waits for a reply from all peers. 2. When an ATM receives a request message (Request, Tmsg, IDmsg) from a peer, it sets its current time (myClock) to one more than the maximum of its current time and the message timestamp (ie., myClock = 1 + max[myClock, Tmsg]). Then: a) If ATM has not acquired the Bank (not in critical section) nor is it waiting to acquire the Bank (has no outstanding request), then it immediately sends a reply message (Reply, myClock, IDmy) back to peer. b) If ATM has already acquired the Bank (is in critical section), then ATM defers sending a reply message by marking UDmsg in its pending reply array (deferred[IDmsg] = TRUE). c) If ATM has previously requested the Bank (is waiting to acquire the Bank) and the i) incoming peer‟s request is later than ATM‟s request (Tmsg > Tmyreq), then the ATM defers sending a reply message by marking IDmsg in its pending reply array (deferred[IDmsg] = TRUE). ii) incoming peer‟s request is earlier than ATM‟s request (Tmsg < Tmyreq), then the ATM immediately sends a reply message (Reply, myClock, IDmy) back to peer. iii) incoming ATM‟s request is equal to peer‟s request (Tmsg = Tmyreq), then if the ATM‟s ID is less than the peer‟s id (IDmsg > IDmy), the ATM defers sending a reply message by marking IDmsg in its pending reply array (deferred[IDmsg] = TRUE). Otherwise, the ATM immediately sends a reply message (Reply, myClock, IDmy) back to peer. 3. When an ATM, who is requesting the Bank, has received an affirmative reply from all other peer„s, (and adjusted its clock to 1 + max[myClock, Tmsg] for each peer message), then it enters its critical section and can access the Bank resource. 4. When an ATM finishes transacting business with the Bank, it leaves its critical section by sending a reply message (Reply, myClock, IDmy) to each peer marked in its pending reply array (where deferred[ ] = TRUE) and then clearing the array.

BYU, CS 345

Project Four – DME

Page 4/11

Distributed Mutual Exclusion Project 4 is implemented with 20 tasks: shell (task 0), 9 ATM‟s (tasks 1-9), BANK (task 10), and 9 DME‟s (tasks 11-19). Before an ATM task can access the BANK, it must make a request for the bank critical section to the corresponding DME task. After completing the operation(s), the ATM task sends a release to the corresponding DME task. The following flowchart may be used to implement the DME task message processing.

Implementation Strategy 1. Read and understand Stallings Chapter 18, Section 3. (Available on-line at http://williamstallings.com/OS/OS6e.html.) 2. Verify that the new shell commands and tasks (OS345atm.h, OS345p4.c, OS345bank.c) are implemented in your operating system and verify the ATM/Bank operations work for individual ATM/Bank requests. (Creating ATM tasks at a higher priority level than the shell will avoid some DME problems, but they must be created at a lower priority for pass-off.) 3. Validate that your counting semaphore implementation from Project 2 works properly. ATM requests from your shell must be queued up in the message buffers awaiting access to the Bank critical section. BYU, CS 345

Project Four – DME

Page 5/11

4. Several other shell commands are included in OS345p4.c which should help in the debug process. The „lm‟ command displays all the messages currently in the message buffers. Verify that this works properly. 5. Lower the priority of your ATM tasks below the shell and implement your distributed mutual exclusion peering solution. Validate with individual requests from the command line that the system still works. 6. Execute the shell commands “test1” and “test2” to validate that the Bank is accessed by only one ATM task at a time. (The validation should be obvious!)

Grading and Pass-off Your DME assignment is to be demonstrated in person to a TA and is outlined as follows: 1) Do the following:  Validate the following (as a minimum) shell commands execute properly: o project4 Create ATM, dmeATM, and BANK tasks o atm ,,{,<$>} Send message to ATM o test1 Stress test the banking system o test2 Stress test the banking system  Implement a Distributed Mutual Exclusion solution in the DME tasks.  Set the ATM tasks at a lower priority than the shell. 2) Demonstrate that your banking system is functioning correctly. Execute the test commands and verify that the bank totals are correct. 3) There are 20 points possible for Project 4. The grading criteria will be as follows:    

Successfully integrate OS345atm.h, OS345p4.c, and OS345bank.c into your OS. (2 pts) Implement a DME solution for critical section access to the bank using the DME peer tasks to arbitrate ATM Requests and Releases. (8 pts) Successfully pass test1 with the ATM tasks at a low priority. (4 pts) Successfully pass test2 with the ATM tasks at a low priority. (6 pts)

In addition to the possible 20 points, the following bonus/penalties apply:    

+2 points bonus for early pass-off (at least one day before due date.) +2 points bonus for implementing a “more stressful” stress test. -8 points for using a common semaphore or shared memory/clock for the DME solution. -2 points penalty for each school day late.

BYU, CS 345

Project Four – DME

Page 6/11

Example Program // OS345p4.c - Distributed Mutual Exclusion // *********************************************************************** // ** DISCLAMER ** DISCLAMER ** DISCLAMER ** DISCLAMER ** DISCLAMER ** // ** ** // ** The code given here is the basis for the CS345 projects. ** // ** It comes "as is" and "unwarranted." As such, when you use part ** // ** or all of the code, it becomes "yours" and you are responsible to ** // ** understand any algorithm or method presented. Likewise, any ** // ** errors or problems become your responsibility to fix. ** // ** ** // ** NOTES: ** // ** -Comments beginning with "// ??" may require some implementation. ** // ** -Tab stops are set at every 3 spaces. ** // ** -The function API's in "OS345.h" should not be altered. ** // ** ** // ** DISCLAMER ** DISCLAMER ** DISCLAMER ** DISCLAMER ** DISCLAMER ** // *********************************************************************** #include <stdio.h> #include <stdlib.h> #include <string.h> #include #include <setjmp.h> #include #include "OS345.h" #include "OS345atm.h" extern extern extern extern

TCB tcb[]; int curTask; Account accounts[]; Message messages[];

// task control block // current task # // process message buffers

// *********************************************************************** // project 4 variables Semaphore* dmeMutex; Semaphore* msgReady[NUM_SEMAPHORES]; // project 4 tasks int atmTask(int, char**); int bankTask(int, char**); int dmeTask(int, char**); // *********************************************************************** // *********************************************************************** // DME task int dmeTask(int argc, char* argv[]) { Message newMsg; char buf[sizeof(Message)]; int myID = INTEGER(argv[1]) + BANK; // 11-19 while(1) { GETMESSAGE(ATMS, myID, newMsg); DMEDebug(("(%d->%d) %s", newMsg.from, newMsg.to, newMsg.msg)); // ?? this is where your distributed mutual exclusion algorithm (Lamports) must // ?? be implemented.

BYU, CS 345

Project Four – DME

Page 7/11

if (newMsg.msg[0] == 'A') { SEM_WAIT(dmeMutex); } if (newMsg.msg[0] == 'R') { SEM_SIGNAL(dmeMutex); } sprintf(buf, "OK"); POSTMESSAGE(myID, newMsg.from, buf); } return 0; } // end dmeTask // ***************************************************************************** // project4 command // // SHELL (0) (1) ATM1 (11) (10) BANK // (2) ATM2 (12) // .... // (9) ATM9 (19) (21) DME1 // (22) DME2 // .... // (29) DME9 // void CL4_project4(int argc, char* argv[]) // project 4 { int i, atm; char buf[sizeof(Message)]; char* newArgv[2]; // kill all but current task (CLI) killTask(-1); // create dme mutex dmeMutex = createSemaphore("dmeMutex", 1, 1); // initialize accounts for (i=0; i
BYU, CS 345

Project Four – DME

Page 8/11

newArgv[0] = buf; createTask("USA Bank", bankTask, HIGH_PRIORITY, 1, newArgv);

// // // // //

task task task task task

name priority argc argv

// startup DME tasks to enforce distributed mutual exclusion // of BANK resource for (i=1; i<=NUM_ATMS; i++) { sprintf(buf, "DME #%d", i+BANK); newArgv[0] = buf; newArgv[1] = buf+5; createTask( buf, // task name dmeTask, // task VERY_HIGH_PRIORITY, // task priority 2, // task argc newArgv); // task argv } // OK to access accounts now atm = 1; // create an initial account printf("\nCreate new account 1000 with $10000"); sprintf(buf, "n,1000,10000"); POSTMESSAGE(CLI, atm, buf); printf("\nCreate new account 2000 with $20000"); sprintf(buf, "n,2000,20000"); POSTMESSAGE(CLI, atm, buf); printf("\nBank Account Summary:"); sprintf(buf, "t,9999"); POSTMESSAGE(CLI, atm, buf); return; } // end project4 // ************************************************************************** // ATM 1,1111,b ; account balance // ATM 1,1111,d,100 ; deposit $100 to 1111 // ATM 1,1111,n,100 ; open new account // ATM 1,9999,t ; bank totals // ATM 1,1111,w,100 ; withdraw $100 from 1111 // ATM 1,1111,x ; delete account void CL4_atm(int argc, char* argv[]) // ATM { char buf[sizeof(Message)]; char code; int atm, account, amount; if (argc < 3) { printf("\n printf("\n printf("\n printf("\n printf("\n printf("\n

BYU, CS 345

ATM ,,{,}"); = 1-9"); = b account balance"); d deposit"); n new account"); t bank totals");

Project Four – DME

Page 9/11

printf("\n printf("\n return;

w x

withdrawal"); delete account");

} // set atm account, code, and amount variables atm = INTEGER(argv[1]); account = INTEGER(argv[2]); code = argv[3][0]; amount = (argc < 5) ? 0 : INTEGER(argv[4]); if ((atm < 1) || (atm > NUM_ATMS)) { printf("\n **Illegal ATM"); return; } // send message to atm sprintf(buf, "%c,%d,%d", code, account, amount); printf("\n CLI: Send to ATM%d '%s'", atm, buf); POSTMESSAGE(CLI, atm, buf); return; } // end ATM // ************************************************************************** void CL4_listMessages(int argc, char* argv[]) { int i; for (i=0; i%d:%s", i, messages[i].from, messages[i].to, messages[i].msg); SWAP; } return; } // end messages // ************************************************************************** void CL4_stress1(int argc, char* argv[]) // stress1 { char buf[sizeof(Message)]; printf("\nCreate new account 1111 with $111"); POSTMESSAGE(CLI,1,"n,1111,111"); printf("\nCreate new account 2222 with $222"); POSTMESSAGE(CLI,2,"n,2222,222"); printf("\nDeposit $2000 to account 1111"); POSTMESSAGE(CLI,1,"d,1111,2000"); printf("\nWithdraw $22 from account 2222"); POSTMESSAGE(CLI,2,"w,2222,22"); printf("\nRequest balance of account 1111"); POSTMESSAGE(CLI,1,"b,1111"); printf("\nWithdraw $1111 from account 1111"); POSTMESSAGE(CLI,1,"w,1111,1111"); printf("\nRequest balance of account 1111"); POSTMESSAGE(CLI,1,"b,1111");

BYU, CS 345

Project Four – DME

Page 10/11

printf("\nRequest balance of account 2222"); POSTMESSAGE(CLI,2,"b,2222"); printf("\nDeposit $1800 to account 222"); POSTMESSAGE(CLI,2,"d,2222,1800"); printf("\nRequest balance of account 2222"); POSTMESSAGE(CLI,2,"b,2222"); printf("\n Account Summary:"); POSTMESSAGE(CLI,1,"t,9999"); CL4_listMessages(argc, argv); return; } // end stress1 // ************************************************************************** void CL4_stress2(int argc, char* argv[]) // stress2 { char buf[sizeof(Message)]; int a, atm; #define startAccount 1001 #define endAccount 1009 //define accounts 1001 thru 1009 with $100 in each for (atm=1,a=startAccount; a<=endAccount; atm++,a++) { sprintf(buf, "%c,%d,%d", 'n', a, 100); POSTMESSAGE(CLI,atm,buf); } // deposit $9 to 1st account, $18 to 2nd, ... for (atm=1; atm<10; atm++) { for (a=startAccount; a<=endAccount; a++) { sprintf(buf, "%c,%d,%d", 'd', a, a-startAccount+1); POSTMESSAGE(CLI,atm,buf); } } // withdraw $8 from 1st, $16 from 2nd, ... for (atm=1,a=startAccount; a<=endAccount; atm++,a++) { sprintf(buf, "%c,%d,%d", 'w', a, (a-startAccount+1)*8); POSTMESSAGE(CLI,atm,buf); } // withdrawal $100 from each account for (atm=1,a=startAccount; a<=endAccount; atm++,a++) { sprintf(buf, "%c,%d,%d", 'w', a, 100); POSTMESSAGE(CLI,atm,buf); } // examine results thru atms for (atm=1,a=startAccount; a<=endAccount; atm++,a++) { sprintf(buf, "%c,%d", 'b', a); POSTMESSAGE(CLI,atm,buf); } // get bank summary POSTMESSAGE(CLI,1,"t,9999"); CL4_listMessages(argc, argv); return; } // end stress2

BYU, CS 345

Project Four – DME

Page 11/11