Date: Mon, 11 Nov 1996 17:25:15 GMT Server: NCSA/1.5 Content-type: text/html Last-modified: Thu, 29 Feb 1996 16:13:50 GMT Content-length: 6112 CS 537 - Quiz #4
UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department
CS 537
Spring 1996
Bart Miller
Quiz #4
Wednesday, February 28

Messages: Readers/Writers Revisited

You are to write the code to implement the access control for the n readers/1 writer problem. You will use message passing, as defined in the class notes and lecture, as your synchronization mechanism (i.e., you cannot use monitors or semaphores).

Each client process that wants to read or write shared database will use the StartRead()/EndRead() or StartWrite()/EndWrite(), as appropriate. These procedures are described below.


You are to write the four client procedures, plus the code for a server process.
StartRead():
This procedure is called by a client process before it wants to have read access to the shared database. This procedure will not return until it is safe to read the data. Note that the actual reading of the data is not done in this procedure.
EndRead():
This procedure is called after a client process is done reading the shared database.
StartWrite():
This procedure is called by a client process before it wants to have write access to the shared database. This procedure will not return until it is safe to write to the data. Note that the actual writing of the data is not done in this procedure.
EndWrite():
This procedure is called after a client process is done writing the shared database.

It might be useful to refer to Section 7 of the lecture notes. For this problem, do not be concerned with whether the readers or writers get more priority.

Solution: Version 1

Here's a good, general solution. It may be a bit more complex than some of you used, but it has some useful characteristics.

The most interesting characteristic is that each client has its own mailbox for response. Having separate client mailboxes allows the clients to run on different hosts in a network.

Note that I didn't write any queuing routines in my code. By clever use of the message system (in this example, by using two message sends for each start request), I was able to use the implicit queuing provided by the mailboxes.

void StartRead()
{
    char mboxname[MAXNAMESIZE];

    MakeMboxName (mboxname);
    send ("request", STARTREAD);
    send ("start-read", mboxname);
    receive (mboxname, buff);
}
void EndRead()
{
    send ("request", ENDREAD);
}
void StartWrite()
{
    char mboxname[MAXNAMESIZE];

    MakeMboxName (mboxname);
    send ("request", STARTWRITE);
    send ("start-write", mboxname);
    receive (mboxname, buff);
}
void EndWrite()
{
    send ("request", ENDWRITE);
}
void MakeMboxName (char *mboxname)
{
    sprintf (mboxname, "mbox.%d", getpid());
    CreateMailboxName (mboxname);
}
void ReaderWriterServer ()
{
    int value;
    int AR=0, WR=0, AW=0, WW=0;
    char mboxname[MAXNAMESIZE];

    CreateMailboxName ("request");
    CreateMailboxName ("start-read");
    CreateMailboxName ("start-write");

    while (1) {
	Receive ("request", &value)
	if (VALUE == STARTREAD) {
	    if (AW + WW == 0) {
		AR++;
		Receive ("start-read", mboxname);
		Send (mboxname, 0);
	    } else {
		WR++
	    }
	} else if (VALUE == STARTWRITE) {
	    if (AW == 0) {
		AW++;
		Receive ("start-write", mboxname);
		Send (mboxname, 0);
	    } else {
		WW++;
	    }
	} else if (VALUE == ENDREAD) {
	    AR--;
	    if (((AR == 0) and (WW > 0)) {
		AW++;
		WW--;
		Receive ("start-write", mboxname);
		Send (mboxname, 0);
	    }
	} else if (VALUE == ENDWRITE) {
	    AW--;
	    if (WW>0) {
		AW++;
		WW--;
		Receive ("start-write", mboxname);
		Send (mboxname, 0);
	    } else {
		while (WR>0) {
		    AR++;
		    WR--;
		    Receive ("start-read", mboxname);
		    Send (mboxname, 0);
		}
	    }
	}
    }
}

Solution: Version 2

Here's a slightly simpler one. This version has the client processes sharing mailboxes. This type of approach is valid, but not as useful since it work work if the client processes are on different hosts in a network.
void StartRead()
{
    send ("request", STARTREAD);
    receive ("oktoread, 0);
}
void EndRead()
{
    send ("request", ENDREAD);
}
void StartWrite()
{
    MakeMboxName (mboxname);
    send ("request", STARTWRITE);
    receive ("oktowrite, 0);
}
void EndWrite()
{
    send ("request", ENDWRITE);
}
void ReaderWriterServer ()
{
    int value;
    int AR=0, WR=0, AW=0, WW=0;
    char mboxname[MAXNAMESIZE];

    CreateMailboxName ("request");
    CreateMailboxName ("oktoread");
    CreateMailboxName ("oktowrite");

    while (1) {
	Receive ("request", &value)
	if (VALUE == STARTREAD) {
	    if (AW + WW == 0) {
		AR++;
		Send ("oktoread, 0);
	    } else {
		WR++
	    }
	} else if (VALUE == STARTWRITE) {
	    if (AW == 0) {
		AW++;
		Send ("oktowrite, 0);
	    } else {
		WW++;
	    }
	} else if (VALUE == ENDREAD) {
	    AR--;
	    if (((AR == 0) and (WW > 0)) {
		AW++;
		WW--;
		Send ("oktowrite", 0);
	    }
	} else if (VALUE == ENDWRITE) {
	    AW--;
	    if (WW>0) {
		AW++;
		WW--;
		Send ("oktowrite", 0);
	    } else {
		while (WR>0) {
		    AR++;
		    WR--;
		    Send ("oktoread", 0);
		}
	    }
	}
    }
}


Last modified: Thu Feb 29 10:13:49 CST 1996 by bart