gcc -o foo foo.c -L/home/linux/ieng6/cs120f/hw -lthread
Implement the semaphore-based readers/writers algorithm given in Lecture 6 in C using the threads package. You should implement three reader threads and three writer threads. You will find it easier to have t_start start a thread that creates the two conditions - one for the semaphore mutex and one for the semaphore r_or_w - and t_forks the three reader and three writer threads. The parameter to the thread should be a unique name for the thread (for example, you could name the reader threads R1, R2 and R3).
Here's my solution:
#INCLUDE "/home/linux/ieng6/cs120f/p1/thread.h"
#include
#include
Condition mutex, w_or_r;
int readcount = 0;
void reader(int me) {
int i;
for (i = 1; i <= 3; i++) {
t_wait(mutex);
if (++readcount == 1) t_wait(w_or_r);
t_sig(mutex, NULL, TRUE);
printf("R%d starts reading.\n", me);
t_yield();
printf("R%d stops reading.\n", me);
t_wait(mutex);
if (--readcount == 0) t_sig(w_or_r, NULL, TRUE);
t_sig(mutex, NULL, TRUE);
}
}
void writer(int me) {
int i;
for (i = 1; i <= 3; i++) {
t_wait(w_or_r);
printf("W%d starts writing.\n", me);
t_yield();
printf("W%d stops writing.\n", me);
t_sig(w_or_r, NULL, TRUE);
}
}
void starter(int counteach) {
int me = 0;
mutex = cond_create();
w_or_r = cond_create();
t_sig(mutex, NULL, TRUE);
t_sig(w_or_r, NULL, TRUE);
for (me = 1; me <= counteach; me++) {
t_fork(writer, (any_ptr) me);
t_fork(reader, (any_ptr) me);
}
}
int main (int argc, char ** argv) {
t_start(starter, (any_ptr) 3);
}
printf("%s starts reading\n", name);
t_yield();
printf("%s stops reading\n", name);
where name is unique name you gave to this reader thread. Similarly, each writer should execute a look so that it tries to enter the Write section three times. The Write section should be:
printf("%s starts writing\n", name);
t_yield();
printf("%s stops writing\n", name);
where name is unique name you gave to this writer thread.
Run your program to verify that it is behaving the way it should. This is the program whose listing we'd like you to turn in along with the output it generates.
Here's our output. Notice our version forks the three writers before the three readers. See if you can figure out why R1 stops reading before R3 starts reading (lines 5 and 6 below). This one stumped your loyal grading staff for several minutes while grading in the wee hours of Thursday morning.
W1 starts writing.
W1 stops writing.
R1 starts reading.
R2 starts reading.
R1 stops reading.
R3 starts reading.
R2 stops reading.
R3 stops reading.
R1 starts reading.
R1 stops reading.
R2 starts reading.
R3 starts reading
R2 stops reading.
R3 stops reading.
R1 starts reading.
R1 stops reading.
R2 starts reading.
R3 starts reading.
R2 stops reading.
R3 stops reading.
W2 starts writing.
W2 stops writing.
W3 starts writing.
W3 stops writing.
W1 starts writing.
W1 stops writing.
W2 starts writing.
W2 stops writing.
W3 starts writing.
W3 stops writing.
W1 starts writing.
W1 stops writing.
W2 starts writing.
W2 stops writing.
W3 starts writing.
W3 stops writing.
Since there's no preemption and no yeild, each thread runs to completion. Hence, there's no real need for all the synchronization - each thread obtains mutual exclusion by default. (Having no synchronization would be a terrible solution, though - what if a thread yielded somewhere in the application, for example?)
W1 starts writing.
W1 stops writing.
W1 starts writing.
W1 stops writing.
W1 starts writing.
W1 stops writing.
R1 starts reading.
R1 stops reading.
R1 starts reading.
R1 stops reading.
R1 starts reading.
R1 stops reading.
W2 starts writing.
W2 stops writing.
W2 starts writing.
W2 stops writing.
W2 starts writing.
W2 stops writing.
R2 starts reading.
R2 stops reading.
R2 starts reading.
R2 stops reading.
R2 starts reading.
R2 stops reading.
W3 starts writing.
W3 stops writing.
W3 starts writing.
W3 stops writing.
W3 starts writing.
W3 stops writing.
R3 starts reading.
R3 stops reading.
R3 starts reading.
R3 stops reading.
R3 starts reading.
R3 stops reading.
The monitor will be the class Table that has two methods: one called StartEating(i) which means that Philosopher i wishes to eat, and one called StopEating(i) which means that Philosopher i stops eating. The file Table.java is the file you'll need to modify to implement this monitor. In StartEating(i), Philosopher i checks to see if either of her neighbors is eating; if so, then i is hungry and waits. StopEating(i) turns the Philosopher's state back to thinking, which may allow a hungry neighbor to start eating. The class also includes a place for you to implement toString: the Philosopher class uses this to print the current states of the philosophers in a convenient manner. This string should contain five character - the first represents the state of Philosopher 0, the second the state of Philosopher 1, and so on. Use the character 'T' to indicate thinking, 'H' for hungry, and 'E' for eating. For example, "THETE" means Philosopher 0 and 3 are thinking, Philosopher 1 is hungry, and Philosophers 2 and 4 are eating. Note that this class has a constructor, in which we've already supplied some code. You'll need to do more.
The file Philosopher.java is the class that implements a philosopher thread, and DiningPhilosophers.java is the class that implements the program: this is the class that has main. You won't have to change either of these files.
To give you a template for a Java monitor, we've also posted BSem.java, which is a java class that implements a binary semaphore (that is, a mutex semaphore). Don't use this class in your implementation of Table; instead, look at it to show you the syntax Java uses for writing monitors.
Turn in a listing of Table.java and the output you generate from running DiningPhilosophers.
Here's my monitor:
public class Table {
private boolean eating[ ], waiting[ ];
private int eaters;
public Table (int numberPhilosophers) {
eaters = numberPhilosophers;
eating = new boolean[eaters];
waiting = new boolean[eaters];
for (int i = 0; i < eaters; i++)
eating[i] = waiting[i] = false;
}
public synchronized void StartEating(int name) {
assert !eating[name]: name;
waiting[name] = true;
while (eating[(name + eaters - 1) % eaters]
|| eating [(name + 1) % eaters])
try { wait(); }
catch (java.lang.InterruptedException e) { };
eating[name] = true;
waiting[name] = false;
}
public synchronized void StopEating(int name) {
assert eating[name] : name;
eating[name] = false;
notifyAll();
}
public synchronized String toString ( ) {
String s = "";
for (int i = 0; i < eaters; i++) {
assert !waiting[i] || !eating[i] : i;
if (waiting[i]) s = s + "H";
else if (eating[i]) s = s + "E";
else s = s + "T";
}
return s + " ";
}
}
Notice that we've used notifyAll instead of notify. This is because when a philosopher stops eating, anywhere between 0 and 2 philosophers can start eating. Here's a run of the system in which the notifyAll is replaced with notify:
TETTT (1 starts)
TETTE (4 starts)
TTHHE (1 stops)
HEHHE (1 starts)
HEHHT (4 stops)
HTHHT (1 stops) ***
HTHET (3 starts) ***
HTHTH (3 stops) ***
ETHTH (0 starts)
ETHEH (3 starts)
THHEH (0 stops)
EHHEH (0 starts)
EHHTH (3 stops)
EHHEH (3 starts)
THHEH (0 stops)
TEHEH (1 starts)
HEHTH (3 stops)
HEHEH (3 starts)
HTHEH (1 stops)
HTHTH (3 stops)
ETHTH (0 starts)
THHTH (0 stops)
THETH (2 starts)
EHETH (0 starts)
EHTTH (2 stops)
THTTH (0 stops)
TETTH (1 starts)
TTHTH (1 stops)
TTHTE (4 starts)
TTHTT (4 stops)
TTETT (2 starts)
TTETE (4 starts)
TTTTE (2 stops)
TTETE (2 starts)
TTETT (4 stops)
TTTTT (2 stops)
TTTTE (4 starts)
TTETE (2 starts)
TTTTE (2 stops)
TTTTT (4 stops)
The lines marked with asterisks show philosopher 0 being able to eat but does not. In particular, you might have become suspicious when 3 stopped eating before 0 starts eating.
The time (hour, minute); the alarm sounding (true/false); the alarm set button (on/off).
The hour is between 0 and 11. If the alarm is sounding then the alarm set button is on.
Time always advances. If the alarm set button is on then the alarm will eventually sound.
Of course, a property can be a combination of a safety and liveness property (just connect a safety property and a liveness property with "and"). And, some properties are confusing. For example, "The alarm won't go off until the alarm time is reached" is either a safety property or a combination of a safety or liveness property, depending on what you mean by "until". If "until" means "unless" then it's a safety property (the bad state is the alarm sounding and the alarm time not having passed); if "until" means "unless it is reached, and it will be reached", then it implies progress, which it has liveness in it.
Context switches is considerably cheaper with threads than with processes. Creating a new thread is cheaper than creating a new process. Processes run in separate address spaces, and so a bug in a process is less likely to corrupt the state of another process.
A net-based server that forks off a new thread for each new connection benefits from threads because it is so much cheaper to create the connection. A shell that forks off a new process for each application benefits from processes because the application can crash and leave the shell intact.
In your implementation, you have three options for the case where signal(s) is done on a semaphore that has already attained its maximum value. You can (i) treat the operation as a no-op; (ii) block the operation until some other thread executes wait(s); (iii) raise an exception (that, if not caught, causes the process to terminate).
For each of these, give a positive attribute and a negative
attribute for using that solution. Which do you think is the best,
and why?
There's no absolutely right answer, since it depends on other issues and costs. In general, though, raising the exception is probably the right thing to do as long as the application developers don't object too much.
One decision to make with an await construct is defining exactly when the boolean expression is evaluated. Of course, when await(B) is initially executed, if B is true then the thread need not wait. The interesting case is when should B be re-evaluated for threads that are waiting for B to become true.
The overhead could be very high. And, there's no guarantee that the monitor invariant holds when a variable used in an await statement is changed. Thus, the waiting process might start to run when the monitor invariant doesn't hold.
Imagine a thread A that awaits for some condition B, and another thread B that enters the monitor, changes a variable that makes B true, and then awaits itself for thread A to change a variable. Thread A will not re-evaluate B even though it holds, and the two threads are deadlocked.
Monitor RW {
int nr = 0, nw = 0;
void StartRead() {
await (nw == 0);
nr++;
}
void EndRead() {
nr--;
}
void StartWrite() {
await (nr == 0 && nw == 0);
nw++;
}
void EndRead() {
nw--;
}
}