void enQ(int n) {

x = new Item(n);

if (head==NULL) head=x;

else tail->next=x;

tail=x;

}

int deQ() {

x=head;

yield();

if (x==NULL) return -1;

if (x==tail) tail=NULL;

head=x->next;

v=x->value;

delete x;

return v;

}

Two threads are started, with the list containing 3 items, values 1 (in head->value), 2, and 3 (in tail->value). Each thread executes deQ() operations until the list is empty.

[20 pts] Present a scenario (interleaving) which causes some erroneous results to occur. Explain what the erroneous actions or conditions are.

ANSWER: Thread 1 yields; thread 2 deQ’s all elements of the list. Then thread 1 finishes its first deQ, This causes element 1 to be returned from 2 different deQ’s. It also leaves head and tail pointing to deleted elements, and causes the item holding 1 to be deleted twice. The behavior of thread 1 in executing subsequent deQ’s depends on whether the Item fields are cleared by delete, or not.

[20 pts] Complete the definition of the List class, showing all variable declarations, and adding P() and V() operations to the methods which ensure that each deQ() and enQ() operation functions atomically. Place the semaphore operations so that as few instructions as possible are executed in the critical regions. The “new” and “delete” statements are guaranteed to run as atomic operations. However, the scheduler uses pre-emptive scheduling, so that a thread switch can occur between any two instructions. Explain why your solution works, and why even more instructions cannot be removed from the critical regions.

ANSWER:

Class List {

Item* head, tail;

Semaphore mutex ;

void List() {

head = tail = NULL;

mutex=1;

}

void enQ(int n) {

Item* x;

x = new Item(n);

P(mutex);

if (head==NULL) head=x;

else tail->next=x;

tail=x;

V(mutex);

}

int deQ() {

Item* x;

int v;

P(mutex);

x=head;

if (x==NULL) {V(mutex); return -1; }

if (x==tail) tail=NULL;

head=x->next;

V(mutex);

v=x->value;

delete x;

return v;

}

By making x and v local to the methods, references to these variables need not be done within critical sections, since each thread has its own copy of these variables. However, the variables head and tail MUST be global to the methods, and local to each instance of a List object, so references to these variables must be done in mutual exclusion. Once either head or tail is referenced, all computations until the last store into either of them should be done within the critical section, or a thread switch could leave head and tail with inconsistent values. All paths which exit the methods must be certain to execute a V(mutex);

2. [60 pts] The low-level mechanism for communicating between a certain pair of computers uses the send(char* message) and recv(char* message) primitives. These primitives are both blocking, and always send and receive 256 byte messages. The OS uses them to provide a “connection-oriented” messaging service. This service supplies the following primitives to applications:

int connect(): Returns an integer which designates a new “connection ID”.

Write(connectionID, char* message, int nchars):

Sends a message of length nchars bytes, which consists of the bytes message[0]...message[nchars-1] on connection connectionID. nchars cannot be larger than 200.

Int Read(connectionID, char* message)::

Reads a message from connection connectionID into message[0]..message[n-1], where the message consists of n bytes. Returns n.

These primitives block until completion.

Even if many connections are active, the messages using each connection are kept distinct, and arrive at the receiving end of the connection in the same order in which they were sent.

Sketch an implementation of the connection-oriented primitives, and the daemon which monitors the low-level communication mechanism. Allow Write to complete as soon as the OS gets the message to be sent (don’t force it to wait until the message is actually transmitted). Read must block if there are no messages waiting on this connection.

You may use the List class defined in Question 1, and you should assume it has been implemented correctly. You may use additional synchronization operations as needed. You may assume that when both machines execute a “connect()” operation, the same connection ID is returned by both operations. You need not show the implementation of “connect”. [Hint: The OS can embed the application’s message in a longer one for actual transmission.]

ANSWER:

/* low-level transmission format */

class Msg {

int connID;

int n;

char data[200];

char xxx[256-8]; /* Fill out the 256 bytes of a low-level message */

}

Msg rbuff ;

List * Toapp = new List[1000]; // Initially empty

Semaphore Tocnt = new Semaphore [1000]; // Initially zero

List *sending = new List;

Semaphore *sndcnt = new Semaphore(0);

/* read daemon: (Runs as a thread within the kernel.): (Only one such daemon)*/

While(1) {

Recv(&rbuff);

int cID=rbuff.connID;

If (!legal(cID)) continue;

Msg *tm = new Msg(rbuff); /* copy message to new buffer */

Toapp[cID]->enQ((int) tm);

Tocnt[cID]->V();

}

Int Read(connectionID, char* message) {

Tocnt[connectionID]->P();

Msg *m = ( Msg *) Toapp[connectionID]->deQ();

int n = m->n;

For (int i=0; i<n; i++) message[i] = m->data[i];

Delete m;

Return(n);

}

Write(connectionID, char* message, int nchars) {

If ((nchar>200)||nchar<0) error(“bad message length”);

If (!legal(connectionID)) error(“bad connection ID”);

Msg *m = new Msg;

m->n=nchar;

for (int i=0; i<nchar; i++) m->data[i]=message[i];

m->connID = connectionID;

sending->enQ((int) m);

sndcnt->V();

}

/* write daemon (only one exists) */

while (1) {

sndcnt->P();

Msg *m = (Msg *) sending->deQ();

Send(m);

delete m;

}

[Take Home. Optional. Up to 30 pts extra credit. Open textbook, and notes. No use of the internet.]

Use methods Acquire() and Release() of the Lock class, together with Condition variables, to implement the following version of the readers – writers problem:

Any number of readers can read at once, but a writer cannot run together with either a reader, or another writer. Neither readers nor writers get priority – instead, as soon as a writer arrives, later-arriving readers and writers are delayed, until the writer gains access to the object, and finishes. The delayed readers and writers are then run as if they had all just arrived, with their original arrival order preserved. Similarly, a sequence of writers can be executed, one at a time, until a reader arrives. Once a reader arrives, a later-arriving writer waits until all running readers finish. Readers and writers arriving after the delayed writer wait until that writer finishes, and are then executed in arrival order.

Example: r1 r2 r3 w4 r5 w6 r7 r8 w9 arrive, in numerical order. They should be allowed to execute in the order: {r1 r2 r3} w4 r5 w6 {r7 r8} w9. This execution order should be preserved, even if jobs 5..9 all arrive while w4 is running. Job ri is a reader, wi is a writer. Jobs in “{}” run at the same time.

You may assume that cvar.Signal() wakes up that process that has been waiting longest on condition variable cvar, or is ignored, if no process is waiting. Don’t use any synchronization primitives other than those mentioned above.

The thread scheduler uses preemptive scheduling.

ANSWER:

class RW {

Lock rwm;

Condition pend, writing;

Boolean Rwait, Wwait, Wrun;

int rdrs;

void StRead() {

rwm.Acquire();

if (Wrun||Wwait) pend.Wait();

rdrs++;

pend.Signal(); // Release any readers waiting next

rwm.Release();

}

void EndRead() {

rwm.Acquire();

rdrs--;

if (rdrs==0) {

if (Wwait) writing.Signal();

else pend.Signal();

}

rwm.Release();

}

void StWrite() {

rwm.Acquire();

if (Wrun || (rdrs>0)) pend.Wait();

if (rdrs>0) {

Wwait=TRUE;

writing.Wait();

Wwait=FALSE;

}

Wrun=TRUE;

rwm.Release();

}

void EndWr() {

rwm.Acquire();

Wrun=FALSE;

if (Wwait) writing.Signal();

else pend.Signal();

rwm.Release();

}