Implementing Locks

Provided:  the public interface to locks in synch.h

You:    define the private data and implement the interface
                only need to modify synch.h and synch.cc
                should not need to modify the public parts of synch.h
 

Why Do We Need Locks...? to avoid race conditions
 

• to make sure that two processes do not get into each other's way when
• accessing a common resource
• to sequence the processes when there are dependencies among them

solution...?   mutual exclusion

simplest hardware solution -- to have each process disable interrupts
software solutions  -- Semaphores, Locks and Monitors

Locks...

•   lock is a synchronization primitive similar to semaphores
•   provides mutual exclusion
•   two atomic operations provided are Acquire() and Release()

lock can either be free or busy
initially, a lock is free

before accessing shared variable process acquires the lock
releases it after it is done accessing that variable

               Lock->Acquire();
                  critical section
               Lock->Release();

Note:  a lock is released by the process that acquires it

this is different from semaphores where it is not necessary that the
process decrementing the semaphore value to say, x, will increment it to x+1 upon
finishing with its critical section

your implementation of Acquire() and Release() should have instructions
for disabling and enabling interrupts

Second...

you need to make sure that the process that calls Release() is the same
one that has invoked Acquire()

you should use the function isHeldByCurrentThread() which is part of the
Lock class definition
 

Finally...              provision of a wait mechanism

implement a queue for each lock in a way similar to the semaphore
implementation
                                                        or

since the semaphore implementation is already given to you, you may
simply want to use it to implement your locks

1.      Implement Lock constructor and destructor

 
Lock variables you may need to add consist of:
                name, semaphore, lock holder thread

2.      Implement isHeldByCurrentThread() routine

3.      Implement Acquire()

disable interupts
do a wait on the lock semaphore
set the lock holder thread to the current thread
enable interupts

4.      Implement Release()

disable interupts
if the current thread is the one calling the lock release
set the lock holder thread to NULL
do a signal on the lock semaphore
enable interupts

Provided:  public interface to condition variables in synch.h

You:    define the private data and implement the interface
                should only need to modify synch.h and synch.cc
                should not need to modify the public parts of synch.h

Note:  semaphores and locks have to be used carefully because a small
error, like a misplaced P() may cause a deadlock or other forms of unpredictable and
irreproducible behavior

Condition Variables...
 

provide a way for the processes to block themselves when they cannot
proceed

as with locks and semaphores, two operations are provided with them
wait            aka             P()
signal          aka             V()

Remember -- condition variables are not counters
they do not accumulate signals the way semaphores do
if a condition variable is signalled with no one waiting on it, the signal
is lost

1.      Implement Condition constructor and destructor

        Condition variables you may need to add consists of:
                                                                name (for debugging)
                                                                queue (a List)

2. Wait()                       // releases the lock, gives up the CPU until signalled
                                        // then re-acquires the lock

make sure that the lock is held by the current thread
disable interrupts
release the condition lock
append the current thread to the condition queue
put the current thread to sleep
acquire the condition lock
reenable interupts

3.      Signal()                        // wakes up a thread if there are any waiting
                                                // on the condition variable

make sure that the lock is held by the current thread
disable interrupts
remove thread from condition queue
place it on the scheduler's ready list calling ReadyToRun()
reenable interupts

4.      Broadcast()             // wakes up all threads waiting on the condition

does the same thing as Signal() but does it for all the threads on
the condition queue, not just one

Producer/Consumer...  Pseudocode...

You:   Implement producer/consumer communication through a bounded buffer, using semaphores and/or locks

You may need:    3 Semaphores

Semaphore emptySem
Semaphore fullSem
Semaphore mutexSem

Producer will need to do the following...
 

// Wait for an empty buffer slot
// Get exclusive access to file, buffer

// if the infile is not empty...
// get a character from the file
// put it into the buffer
// print "producer <id> producing <character read>"

// Release exclusive access to file, buffer
// Indicate that a buffer slot has been used

currentThread->Yield();  // yield to allow interesting mixing
 

// Wait for a filled slot
// Get exclusive access to buffer
 
// print "consumer <id> consuming <character>"
 
// Release exclusive access
// Indicate a buffer is now empty
 
currentThread->Yield();      // Yield to allow interesting mixixing

is left to you to come up with the pseudocode and implement....