CISC324: Operating Systems
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CISC324: Operating Systems
Lab 5
Toolbox
This lab is your first time programming exercise in which you will be writing concurrent programs that use monitors in Java. You will improve your programming skills in how to use monitors in practice. You will also get more familiar with the use of the primitives wait(), notify(), and notifyAll() that were discussed during the lectures.
This lab has been prepared to be conducted on any operating system that runs the Java Virtual Machine. Please make sure to have a well set up environ- ment. You need a computer, an operating system, a Java Virtual Machine, and optionally a Java IDE (e.g., Eclipse).
Background and Outcomes
As described in the course lecture: A monitor is a high-level programming language construct that provides mutually-exclusive access to data declared within the monitor. A monitor collects together all critical section codes related to a particular shared data structure. They are considered as less error-prone to use than semaphores. With semaphores, it is easy to forget the acquire() or the release() primitive around some critical sections. Monitors automatically provide mutual exclusion. In addition, for signaling among threads, monitors provide signal and wait operations on condition variables.
A monitor with N condition variables has N+1 queues associated with it. The additional queue is the entry queue which holds threads that are ready to execute some code within the monitor but have to wait on that queue as at that time another thread is already within the monitor (holds the monitor lock) executing some code. There is one queue for each declared condition variable. A thread waits on queue x when it has executed x.wait() on a condition variable named x.
In Java, there is only one condition variable per monitor. This condition variable does not have a name. Threads simply say wait(), without giving the name of a condition variable.
Only one thread at a time can execute monitor code. In Java, this is implemented using the lock associated with the monitor object. Whatever thread is executing monitor code is "holding the lock". When a thread executes wait(), it releases the lock. This allows another thread to execute monitor code. While that thread is executing monitor code, it can execute a notify() or notifyAll(). The way in which wait() releases the lock is analogous to this style of semaphore code:
Release(mutex); // Release mutex in preparation for Acquire(carSem). Acquire(carSem); // Wait for the "carSem" semaphore. Acquire(mutex); // Grab mutex again, now that we’re past the carSem waiting.
Similarly in a monitor, a thread releases the lock while executing wait(), and then, after notify() is received, the thread must again obtain the lock before continuing execution of monitor code. The compiler takes care of implementing this. In Java, when a thread executes notify(), it does not give up the lock; it keeps holding on to the lock and executing the statements following the notify(). The effect of the notify() is that one thread moves from the condition queue to the entry queue. The effect of notifyAll() is that all threads in the condition queue move to the entry queue. If the condition queue is empty, then notify() and notifyAll() have no effect. Also, in Java the “entry queue” is not necessarily FIFO. When a thread releases the lock (by reaching the end of the monitor method that it executes), then one of the threads in the entry queue will get the lock. Which of the entry-queue threads gets the lock is a matter of luck and timing. Note: some Java implementations might choose to use FIFO.
Java is an object-oriented language, with inheritance. Every object in Java inherits from the “Object” class. The Object class defines a lock and a waiting area for threads. The following Java constructs deal with this lock and waiting area. These constructs apply to any Java object, since they all inherit from Object.
• synchronized This is a keyword that can be attached to a method or a block of code. For example, the rwMonitor.java file (provided for lab
5) declares public synchronized void startRead(). Similar declar- ations are used for endRead, startWrite, endWrite. The synchronized keyword delimits code that holds the lock for an object. When a thread wants to execute synchronized code, it has to wait until no other thread is executing synchronized code associated with the same object. (The compiler takes care of implementing this waiting.)
• void wait() Every Object has a wait() method. The wait() method releases the lock and waits. It re-grabs the lock when a notify() is received.
• void notify() Every Object has a notify() method. The notify() method hangs on to the lock, but allows one waiting thread to switch from wait mode to “try to grab the lock” mode. If there is no thread waiting, then notify() has no effect. This is different from semaphores: if no one is waiting for a semaphore, then the semaphore Release is remembered, allowing the next thread to get past Acquire without waiting. In contrast, monitor semantics are that notify() is ignored if no one is waiting. Therefore, in a monitor, a thread that executes a wait() always has to wait, no matter how many preceding notify() calls were made.
• void notifyAll() Every Object has a notifyAll() method. The notifyAll() method hangs onto the lock and allows all waiting threads to switch from wait mode to "try to grab the lock" mode. If there is no thread waiting, then notifyAll() has no effect.
The wait(), notify() and notifyAll() methods can only be called by a thread that is holding the lock on this Object. To get the lock, put the wait(), notify() or notifyAll() inside a block or method that is synchronized. Java does not necessarily use FIFO order for wait() and notify(). If thread T1 executes wait() and then thread T2 executes wait(), either T1 or T2 might be awakened when thread T3 executes notify(). Normally, Java code is written without explicitly naming the object to which synchronize, wait(), and notify() are being applied. (It’s shorthand for saying “this” is the object being used.) In the sample code for lab 5, the wait() and notifyAll() calls in rwMontor.java are being applied to the object rw. This rw object is created in the constructor for class SharedDataStruct, by the statement “rw = new rwMonitor()”.
The wait() code in Java monitors usually takes this form:while <some test> wait()
This code is used (instead of if <some test> wait() ) for three reasons.
1. A thread that executes notify() or notifyAll() immediately continues execution of the following code. The other threads that are awakened by the notify() still have to wait to grab the lock. So by the time they get the lock, the condition for which they got blocked in the first time may have changed. Thus it is necessary to test that the condition still holds, using the while loop.
2. In Java, only one condition variable is used: all threads wait on the same object. Thus a thread executes notifyAll() and leaves it to each awakened thread to determine whether or not its particular condition is really satisfied. If the condition is not satisfied, the while loop makes this thread wait() once again.
3. Java threads can have spurious wakeups. The semantics of Java wait() are as follows: the thread executing wait() can only be woken up because some other thread executes notify() or notifyAll(). However, for efficiency reasons, Java implementations are allowed to have spurious wakeups, where a thread wakes even though there was no execution of notify() or notifyAll(). Because of this, a Java thread that is awoken must allow for the situation that this wakeup was spurious. Surrounding the wait() with a while loop does just that.
The Wikipedia entry for Spurious wakeup provides more information about this disappointing aspect of Java concurrency. The existence of spurious wakeups was an intentional design decision: “on some multiprocessor systems, making condition wakeup completely predictable might substantially slow all condition variable operations.” This while <some test> wait() code looks similar to busy waiting, but only a small amount of repeated testing is involved. Threads spend most of their time waiting in a queue to grab the lock of the object (and not using CPU during this time). Occasionally they become awakened because another thread executes notify() or notifyAll(). The awakened thread executes its test, and if it fails the thread calls wait() again. In contrast, the really CPU-intensive form of busy waiting uses code such as “while <test> do {nothing}”: this wastes a lot of CPU time because the thread constantly tests and retests the same condition, never getting suspended on a queue.
It is possible to explicitly name the Java objects to which wait() and notify() are applied. Remember to do this in a synchronized block of code: it is necessary in order to get the lock for an object before executing wait() or notify(). For example:
Object wrt;
...
synchronized (wrt)
{
wrt.wait();
// wrt.wait() and wrt.notify() must be
// in a synchronized (wrt) block.
...
}
Writing code with several named conditions can be tricky, because every Java object (acting like a condition variable) has its own lock. In contrast, in a traditional monitor (as defined by Hoare Lampson/Redell), the monitor itself provides a lock, and allows any number of condition variables to be declared inside the monitor. The designers of the Java language only provide a simplified approximation to these traditional monitors. Because every Java object has its own lock, deadlock can easily result from code such as the following.
Object wrt, rd;
// declare two objects that act as condition variables
synchronized (wrt)
{
// some code here; perhaps using wrt.wait() or wrt.notify()
synchronized (rd)
{
rd.wait(); // There is a problem here.
// At this point the thread holds a lock
}
// on object wrt as well as on object rd. The rd.wait() releases
}
// the lock on rd and gets into the queue associated with rd.
// However, the whole time that this thread is waiting in the
// rd queue, it will still hold the lock on wrt. Therefore, no
// other thread can get into a “synchronized (wrt)” block, and
// we might get deadlock.
In your lab 5 programs, it is easier if you stick to using one unnamed condition per monitor. However, you have the freedom to choose the option that make you feel comfortable.
1 Readers/Writers Problem (Starvation Free Solution)
A sample monitor, for the readers and writers problem (readers having priority), is provided for you in directory Lab 5. Study the structure of this code carefully. Understand how monitors are used: look at class rwMonitor, used in SharedDataStructure. Also understand the software engineering reasons behind the organization of the SharedDataStructure class. This class declares the shared data to be private, and provides the access methods dataRead and dataWrite that perform the needed synchronization. This organization allows external users (reader and writer threads) to access the data without having to worry about the synchronization - maybe even without being aware that there is any synchronization going on. This ensures that external users cannot by mistake access the shared data directly: they have to go through the access methods, and are thereby guaranteed to get proper synchronization.
Study the readers/writers monitor given above. Execute the monitor code, and study the output to convince yourself that it is working. We have discussed during the lecture that both solutions “readers having priority” and “writers having priority” (in Lab 3) are not starvation free solutions. In this first exercise, you are asked to modify the given code to transform the solution into a starvation free solution.
2 Consumer/Producer Problem (Bounded Buffer)
In this exercise, you will write synchronization code for the producer and con- sumer problem, a.k.a., bounded buffer problem. You are given the following Java files: MainThread.java containing the main class, Producer.java de- fining the producer class, Consumer.java defining the consumer class, and Buffer.java which defines the buffer class.
1. Compile and execute the program then explain the output.
2. In the main thread, swap the two lines p.start() and c.start(), com- pile and execute then explain the output.
3. The program seems to be not working properly. Complete the program so that the producer thread produces letters that are consumed later on by the consumer thread.
3 What to submit
1. Place all your source codes in a folder named in the following format : 324-1234-Lab5 where 1234 stands for the last 4 digits of your student ID,
e.g.: If a student ID is 20196072, the folder should be named 324-6072-Lab5.
2. Place a ReadMe.txt file in the same folder above.
3. Compress the above folder (324-xxxx-Lab5) using Zip (the extension must be .zip)
4. Log into OnQ, locate the lab’s dropbox, and upload your zip-folder
4 What to check during submission
1. Check that you are not submitting an empty folder.
2. Check that you are not submitting the bytecodes (i.e., compiled).
3. Check that you are not submitting the wrong files.
4. Check that you are not submitting to the wrong dropbox.
5. heck that you are submitting before the deadline.
2021-12-05