Make sure to read Chapter 7 of the Silberschatz book carefully before you begin working on this lab.
class RWLock
{
public:
enum LockType {READER, WRITER};
RWLock();
~RWLock();
void Lock(LockType OptionalType = READER);
void Unlock(LockType OptionalType = READER);
private:
// your private data is declared here... You can use Semaphores
// and any other variables you need
};
Based on the optional LockType (the C++ default
arguments to Lock/Unlock give the value READER if the caller
does not specify an argument), the Lock and Unlock
functions can behave
as read or as write locks. The locks should behave in the same manner as in the readers/writers problem with reader priority. This means that any number of readers can gain access if another reader is holding the lock. When a writer holds the lock, no other reader or writer can gain access. When a writer finishes writing, waiting readers must have priority over waiting writers. This is similar to the standard readers/writers solution given in Chapter 7 of your Silberschatz book, except that readers have priority when a writer finishes writing. Clearly, writers may starve, but this is the specification you should follow.
The above class should be implemented in synch.h and synch.cc.
Implement an atomic map -- shared among all threads -- where a name string is associated with a value (some number). Many times, it is useful to have such global atoms ((key, value) pairs) shared among threads. For instance, an entry in this global table could be used for message passing between threads or for sharing data. In addition to being able to share globally mapped atoms, the map can be used for synchronizing threads that access an entry.
Each atom has an owner that can perform certain operations that other threads cannot perform on that atom. The thread that creates an atom is its owner and is capable of changing its state and not just reading its value. The owner can delete an atom or block it. An atom in a blocked state will cause any readers (except the owner) to be placed on a wait queue until the owner thread performs the unblock operation, which will move all waiting threads to the ready list. If any threads are on a wait queue of some atom, they must be freed up when the thread calls unblock, deletes the atom, or terminates. Upon termination, all atoms that have been created by that thread must be removed from the atom table. All of the operations on the map and on an atom must be multi-thread safe. However, the read operations should not be restrictive when other read operations are occurring (therefore, use RWLock's).
The object of type AtomTable that you declare must be globally accessible -- just like the scheduler object (examine system.h and system.cc). Call the pointer that points to an object of type AtomTable "atomTbl". Make sure to use new to allocate space for the table in system.cc.
Your task is to implement the API functions listed below to allow the use of the atomic table. Since a computer has only a limited number of resources and OS operations need to be as fast as possible, the number of table entries is limited to 20 entries. Your code must handle the situation when an atom is deleted while some other thread is waiting to read it. The function that waited on an atom that got deleted needs to return ATOM_DELETED, even if some new atom with the same name as the deleted one has been reinserted into its old spot.
Define the following enumerated type as a public member of the class AtomTable:
enum ErrCond {ATOM_OK, ATOM_FAIL, ATOM_DELETED};
The public members of the AtomTable class are defined as follows:
class AtomTable
{
public:
enum ErrCond {ATOM_OK, ATOM_FAIL, ATOM_DELETED};
AtomTable();
ErrCond InsertAtom(char *name, int value); // create a new atom
ErrCond DeleteAtom(char *name); // only the owner can call this
ErrCond GetAtom(char *name, int *value); // read the value of an atom
ErrCond TryGetAtom(char *name, int *value); // read the value of an atom if unblocked; return error otherwise
ErrCond BlockAtom(char *name); // only the owner can call this
ErrCond UnblockAtom(char *name); // only the owner can call this
ErrCond DestroyAtoms(); // MUST be called by a thread upon exit
private:
// your private data and functions are declared here
// in addition to the actual atom table (which
// contains for each atom its name, value, and any
// locks and semaphores required), declare any other
// RWLocks and variables you need.
// You can also declare private functions that are
// used from within public functions here.
};
The AtomTable methods should implement the following functionality:
You should create a new pair of files atom.h and atom.cc where you will implement the atom table. Do not forget to change the Makefile so that the new files will be included into the build (Hint: see target "depend" in Makefile.common).
void AtomSynchTest(int arg)
{
int value;
atomTbl->GetAtom("TestAtom", &value);
printf("^1 TestAtom: %x\n", value);
currentThread->Yield();
printf("^Getting the atom again\n");
atomTbl->GetAtom("TestAtom", &value);
printf("^2 TestAtom: %x\n", value);
done.V();
}
void AtomTblTest(int arg)
{
atomTbl->InsertAtom("TestAtom", 0xBEEF);
Thread *t3 = new Thread("C1");
t3->Fork(AtomSynchTest, 0);
// yield and let the SynchThread wakeup
currentThread->Yield();
atomTbl->BlockAtom("TestAtom");
// the atom is blocked but I should be able to read it myself
atomTbl->GetAtom("TestAtom", &sum);
printf("TestAtom Blocked and we are yielding...\n");
currentThread->Yield();
atomTbl->UnblockAtom("TestAtom");
printf("TestAtom UnBlocked and we are waiting...\n");
done.P();
printf("Atom Synch test is done\n");
printf("ATOM TESTS ARE FINISHED\n");
}
void ThreadTest1(int arg)
{
Thread *t2 = new Thread("AT Test");
srand(time(0));
t2->Fork(AtomTblTest, 0);
}
Here is the expected output of this test:
^1 TestAtom: beef TestAtom Blocked and we are yielding... ^Getting the atom again TestAtom UnBlocked and we are waiting... ^2 TestAtom: beef Atom Synch test is done ATOM TESTS ARE FINISHED
Part 2 of the lab (AtomTable) is due on Sunday November 14th, 2004 before 11:59 PM.
Make sure to start early as many of the RWLock and Atom functions are non-trivial.
To submit part 1 of your lab: