Description
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
