Solutions to Problem Set 1

1. (3 points) This question explores why a monitor enforces mutual exclusion (i.e., no more than one process or thread can be executing in the monitor at any point in time). Suppose that a monitor did not enforce mutual exclusion and consider the readers-writers monitor in the following scenario: a single reader process has just finished reading from the database and has called the endread procedure while a single writer process has just invoked the startwrite procedure. Describe a sequence of actions that results in the writer being unable to access the database even though the reader has relinquished control of the database. Ignore all other reader and writer processes.

The endread and startwrite procedures are as follows:

If the above statements are executed in the following order, then the writer will wait indefinitely:

S1, E1, S2a, E2, E3, E4, S2b, S3, S4

There are other orders that will also demonstrate an indefinite wait experienced by the monitor, but they should all have one key similarity: the signal sent by the endread procedure is sent before the startwrite procedure waits. This can happen when startwrite reads the value of readercount before endread updates its value.

2. (3 points) In a given state, the readers-writers monitor has 6 reader processes blocked on the OKtoread condition variable because a writer process was writing to the database. Ignoring all other processes, how many processes will at some point be on the urgent queue from the time when the writer completes until the time when all of the reader processes are reading?

6 of the 7 processes will at some point be on the urgent queue. First, the writer signals the readers in the endwrite procedure, which puts the writer on the urgent queue. Then, a reader comes off of the OKtoread condition queue, and it sends another signal to the other readers, which puts this first reader onto the urgent queue as well. This process repeats for the next five readers. The last reader to come off of the condition queue will send a signal, but since the OKtoread condition queue is now emtpy, the signal will have no effect. This means that the last reader continues to execute without going onto the condition queue.

A note about the interpretation of this problem: you shouldn't try to find a single point in time and see how many processes are in the urgent queue. Look at each process instead, and see which ones are on the urgent queue at some point in time.

3. (4 points) The database in the readers-writers problem cannot be encapsulated by the monitor. Thus, it is possible for badly programmed processes to directly access the database without the proper synchronization. Show the design of a system in which encapsulation is used to protect the database and guarantee proper synchronization while allowing concurrent reading of the database.

The best way to solve this problem is to create an object class that encapsulates both a database and the monitor that protects it. Suppose that we have a monitor that is as defined in the text on page 23. Suppose also that we have the following methods exposed by our database object:

class Database {
	public DBTable DBread(String query);
	public boolean DBwrite(String key, DBentry entry);
	// ...
}

We will create a wrapping class that encapsulates both this database and a monitor to coordinate and synchronize access to it. Both the database and the monitor are "off-the-shelf" objects -- we do not need to make any modifications to them to use them in our example. They will be protected by the access mechanisms that are present in our Java-like language. (For Java purists: we're ignoring object instantiation and initialization.)

class ProtectedDatabase {
	public DBTable read(String query)
	{
		DBTable result;

		m.startread();
		result = DB.DBread(query);
		m.endread();

		return result;
	}

	public boolean write(String key, DBentry entry)
	{
		boolean result;

		m.startwrite();
		result = DBwrite(key, entry);
		m.endwrite();

		return result;
	}

	private Database DB;
	private Monitor m;
}

Since the database and monitor are both declared as private members of our encapsulating class, they cannot be accessed from outside this class. This protects them from being manipulated by an improperly written process. The methods exposed allow a user of this class to access it just as if it was the database itself being accessed. Synchronization is enforced as required, since the methods access the monitor and the database in the proper fashion, as shown in the monitor-based readers/writers problem solution.