EEL 602 - Operating Systems
Spring 2007
Indian Institute of Technology Delhi, New Delhi

---

---

Assignment # 5

Synchronization using Semaphores

{Only submit this assignment if your assignment # 3 marks are less than 10}

 

Problem

A particular river crossing is shared by both Linux Hackers and Microsoft employees. A boat is used to cross the river, but it only seats four people, and must always carry a full load. In order to guarantee the safety of the hackers, you cannot put three employees and one hacker in the same boat (because the employees would gang up and convert the hacker).  Similarly, you cannot put three hackers in the same boat as an employee (because the hackers would gang up and convert the employee). All other combinations are safe.                                                                          

                                                

 

Problem Overview

 

Control Flow

a.       The pool of hackers and employees are waiting for the queue-check function to release the queue-lock so that they can enter the queue.

b.      When the queue-lock is released the hackers/employees take a random backoff  and enter in the queue. The lock of the queue is released for certain amount of time only.

c.       The queue-check function checks for safe-boat load at all times. When safe boat load is achieved, the queue-check function locks the queue and empties people from respective queue’s.

d.      One of person on the boat calls rowBoat function and returns back the control to queue-check function.

e.       If the queue-check function finds safe-boat load condition again, it keeps on locking the queue, and empties the queue unless the safe-boat load condition removed.

f.        If safe-boat-load condition does not exist it unlocks the queue for certain amount of time.

g.       After unlocking of queue’s, control of program passes to step b.

 

Implementation:

 

Two procedures are needed: HackerArrives and EmployeeArrives, called by  a hacker or employee when he/she arrives at the river bank. The procedures arrange the arriving hackers and employees into safe boatloads; once the boat is full, one thread calls Rowboat and only after the call to Rowboat, the four threads representing the people in the boat can return.

 

You can use either semaphores or condition variables to implement the solution. Any order is acceptable and there should be no busy-waiting and no undue waiting ¨C hackers and employees should not wait if there are enough of them for a safe boatload.

 

Your code should be clearly commented, in particular, you should comment each semaphore or condition variable operation to specify how correctness properties are preserved.

You must generate appropriate comments in your code to ascertain the your code is running.

Marking Scheme

 Your Implementation: (10 marks)

1.      Five marks are subtracted if there are no comments, 2 marks if the comments were weak or useless.  

2.      One mark is subtracted for each minor error, up to 2 marks.

a.       Not defining or initializing variables

b.      Gratuitous checks. For example, checking if the boat contained four people, even if the condition is never visible to other threads.

3.      One mark is subtracted for each major error, up to 4 marks:

a.       Signaling/waiting outside a critical region (or using a semaphore inside one)

b.      Busy waiting

c.       Failing to wait for Rowboat to be called before a thread returns

4.      A non-symmetric solution where the HackerArrives and EmployeeArrives procedures were different.

a.       Undue waiting caused by loading one person at a time instead of  two or four:

b.      Loading one at a time is bad because you could have a string of three hackers followed by a long string of employees, all of whom would be forced to wait for another hacker. Loading two or four at a time would avoid such a situation.