Description
Operating systems
1. Objectives
The objective of this assignment is to allow you to learn how to implement critical
sections and barrier synchronization of concurrent threads using semaphores.
2. Preparation
2.1 Source Code
There are four files to be distributed with the assignment. A soft copy of the code
is available to download from the course website.
2.1.1 File Checklist
Files distributed with the assignment requirements:
common/BaseThread.java
common/Semaphore.java
BlockManager.java
BlockStack.java
2.2 BlockManager and BlockStack
A version of the BlockManager class is supplied. The BlockStack will have to be
modified in accordance with tasks 1 and 2. You will need to ensure that your code
matches the method naming in these files. Specifically, in BlockStack:
• The method to get iTop is called getITop(); //change code
• The method to get iSize is called getISize(); //change code
• The method to get the stack access counter is to called getAccessCounter();
• A new utility method is expected to be there, called isEmpty(), which returns true if the
stack is empty; false otherwise. The definition of the method could be as following:
public boolean isEmpty()
{
return (this.iTop == -1);
}
The exception handling in BlockManager is done in a general way, so it should
theoretically cover all your implementations. However, you must ensure that your
exceptions (created in task 2) work with the BlockManager class.
Operating systems Programming assignment #2 comp346
Computer science and software engineering Page 2
3. Background
We are going to utilize the BaseThread data member – siTurn – to indicate the thread
ID (TID) of the thread that is allowed to proceed to (details below). There are
four other methods in the BaseThread. Two of them are phase1() and phase2(), which
barely do anything useful. However, they indicate the phase # and the state of the
currently executing thread. Another method is turnTestAndSet(). This method tests both
the turn and the TID for equality, and increments/decrements the turn if they are equal.
The method returns true if the turn has changed; false otherwise. This method is intended
to be used primarily in the last task.
Note: This is a very good method to mess things up!
• The Semaphore is a class that implements the semaphore operations Signal()/V() and
Wait()/P() using Java’s synchronization monitor primitives, such as, synchronized, wait(),
and notify(). Objects of this class are going to be used to once again to bring operations
into the right order in this hostile world of synchronization.
• The Synchronization Quest is based on the idea, where you have to synchronize all the
threads according to some criteria. These criteria are:
1. PHASE I of every thread must be done before any of them may begin PHASE
II.
2. PHASE II must be executed in the descending order (…3-2-1) of their TID.
4. Tasks
The following tasks are given. You must make sure that you place clear comments
for every task that involves coding changes that you have made. This will be considered
in the grading process.
Task 1: Writing Some Java Code, Part I
Declare an integer “stack access counter” variable in the BlockStack class. Have it
incremented by 1 every time the stack is accessed (i.e. via push(), pop(), pick(), or getAt()
methods). When the main thread terminates, print out the counter’s value. Submit the
modified code and the output.
Task 2: Writing Some More Java Code, Part II
The BlockStack class has somewhat bogus implementation, no checking for boundaries,
etc… Most of the class is also not quite correctly coded from the good object-oriented
practices point of view like data hiding, encapsulation, etc.
1. Make the iSize, iTop, acStack, and possibly your stack access counter private
and create methods to retrieve their values. Do appropriate changes in the main
code.
2. Modify the push() operation of the BlockStack class to handle the case when
the stack is empty (last element was popped). Calling push() on empty stack
should place an ‘a’ on top.
Operating systems Programming assignment #2 comp346
Computer science and software engineering Page 3
3. Implement boundaries, empty/full stack checks and alike using the Java’s
exception handling mechanism. Declare your own exception, or a set of
exceptions. Make appropriate changes in the main code to catch those exceptions.
NOTE: If do you catch ArrayIndexOutOfBoundsException it’s a good thing, but
it’s not your own exception 🙂
Task 3: Atomicity Bugs Hunt with Mutex
Compile and run the Java app given to you as is, and look at the output. After possibly
getting scared of what you have seen, you will have to correct things. Yet, before you do
so, make execution of the critical sections atomic. Use the mutex semaphore for that
purpose.
Task 4: The Right Order, Take I
In this task you have to ensure that the PHASE I of every thread is completed before
PHASE II of any thread has a chance to commence. You still need to do so using
semaphore operations. Submit the output and a context diff to the original sources.
Task 5: The Right Order, Take II
The second synchronization requirement on top of the one of “Take I” is that all 7 threads
must start their PHASE II in opposite order of their TID, i.e. 7, 6, 5, …, 2, 1 The second
semaphore, s2, and turnTestAndSet() method are provided to you to help with this.
Submit the output and a diff to the original sources.
5 Implementation Notes
• You may NOT use the synchronized keyword. Use the Semaphore objects provided to
you as your primary weapon.
• Refer to the Synchronization Tutorials for barrier synchronization examples.
• It’s up to you to determine the initial values of the semaphores as long as your solution
provides correct mutual exclusion and synchronization without deadlock, starvation, etc.
Although it is discouraged to initialize a semaphore to a negative value in the classical
definition (and you should not do so in any solutions related to the theory component of
the course), you may do so in this assignment provided you can justify your choice
(efficiency, overhead, semantics, etc.).
6 Deliverables
For every task, submit the complete output and a context diff to the original code.
Thus, a file list to submit might look like this:
BlockManager1.java
BlockStack1.java
Operating systems Programming assignment #2 comp346
Computer science and software engineering Page 4
Output1.txt
BlockManager2.java
BlockStack2.java
Output2.txt
BlockManager3.java
BlockStack3.java
Output3.txt
BlockManager4.java
BlockStack4.java
Output4.txt
BlockManager5.java
BlockStack5.java
Output5.txt
Archive these files into a zip file called pa2.zip and submit it electronically using the
EAS system. Keep the confirmation of your submission.
7 Grading Scheme
Grading Scheme:
===============
T# MX MK
————————-
1 /1
2 /1
3 /2
4 /3
5 /3
————————-
Total:
(T# – task number, MX – max (out of), MK – your mark)
8 References
1. API: http://java.sun.com/j2se/1.3/docs/api/
2. Object: http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html
3. wait(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#wait()
4. notify(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#notify()
5. notifyAll(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Object.html#notifyAll()
6. Thread: http://java.sun.com/j2se/1.3/docs/api/java/lang/Thread.html
7. start(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Thread.html#start()
8. run(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Thread.html#run()
9. yield(): http://java.sun.com/j2se/1.3/docs/api/java/lang/Thread.html#yield()
10. join() http://java.sun.com/j2se/1.3/docs/api/java/lang/Thread.html#join()
11. Java API: http://java.sun.com/j2se/1.3/docs/api/
Operating systems Programming assignment #2 comp346
Computer science and software engineering Page 5
12. Tutorial Information
13. http://java.sun.com/docs/books/tutorial/essential/TOC.html#threads
14. CS Help Pages: http://www.cs.concordia.ca/help
