CSS 443 - Machine Problem #2

 

More Realistic Garbage Collection

with Threads

 

Assigning Date: April 9, 2003

Program Due Time: 2:30 pm, April 23, 2003

Design Document Due Time: 3:40 pm, April 23, 2003

 

 

 

Objectives:

In this programming assignment we will extend our mp1 into multiple threads where we will simulate the different timing requirement for different list and memory operations.

 

 

Approach:

 

One again, as in mp1, we have a simple link list of integers with a memory manager that implements mark and sweep garbage collection. In this case, our link list will support searching for specific keys.

 

Please refer to the TthreadBase class we went through in lectures. You are to subclass from TthreadBase class and develop three new thread classes:

 

TfindThread(char *filename, TmyList *list, int workTime);

TprintThread(char *fileName, TmyList *list, int workTime);

TgarbageCollectThread(char *fileNameˇ¨, TrecordMemoryPool *pool, TmyList *list, int workTime);

 

As the names suggest, TfindThread will input one key from the user and attempt to locate the key from the list. TprintThread will traverse the list and print out each element. These two threads require public access right to the list. The garbageCollectThread collects garbage. This thread requires exclusive access to the TrecordMemoryPool, but only requires public access to the link list. This means, while garbage collection is in process, we should still be able to print and search the list, but insert, delete, and sort operations will block.

 

In each case, fileName is the output file name for the thread, list is the list that the thread will operate on, and workTime is the simulated amount of time it would take for the thread to finish its work. In our implementation, after our thread obtain the accessing right to the list/pool, we would call TthreadBase::ThreadWorkTime() before proceed with our operations on the list/pool. Immediately after we are done processing, we should once again call TthreadBase::ThreadWorkTime() to simulate thread/processing overhead. This should be done before we release our access right to the list/pool.

 

You need to build a TsynBarrier class that will provide support to both TmyList and TrecordMemoryPool classes such that these two classes can support multithreaded accessing. Please note that our other mp1 operations: insert/delete/print pool/sort will still work off the main thread. You must make sure all the threads are properly synchronized and ensure correct and predictable results.

 

As in mp1, all print outs (e.g. from either find command, and/or print command, etc) must include: NumOps (number of operations) performed. This number is very important; it helps me grade your answers. Finally, you cannot use the CcriticalSection synchronization object in this mp.


What to hand-in:

 

1.        Please refer to Programming Assignments section in our class syllabus for details. You should create a zip file with your FirstLastNameMp2.zip, containing the source code to your implementations and copy it to \\Hermes\Classes\CSS443\mp2 before the deadline time (of 2:30pm). Please submit your entire project source code for this mp. The only requirement is that, please leave the following line of code:

#define   NUM_RECORDS_IN_POOL             <number>

in TrecordMemoryPool.h, and you should assume I will change the NUM_RECORDS_IN_POOL to something very large for testing purposes.

 

2.        Hand-in a design document on the due date before 3:40pm.  In this document please include the followings:

a.        The detailed design of your TsynBarrier class.

b.       Summary of changes you made to your (or mine, if you decide to use my mp1 results) TmyList and TrecordMemoryManger in order to support multi threads.

c.        Pseudo code for your main thread methods in each of the find/print/garbage collect threads.

 

 

Credit Distribution:

 

1.       Correct public access for print and find threads                                                             20%

 

2.       Proper TsynBarrier function supporting exclusive and public access                        30%

 

3.       Correct garbage collection thread                                                                                    15%

 

4.       Proper operation of the rest of the list commands                                                          10%

 

5.       Design Documentation:                                                                                                      20%

 

6.       Proper programming style and proper submission                                                         5%

 

BE WARNED! If your program does not compile, or if your implementations do not generate correct results, you WILL NOT GET ANY CREDIT. If your linked-List does not work, you WILL NOT get any credit for TrecordMemoryPool. If you implement algorithms based on pass studentsˇ¦ design documentations that are available on-line (or otherwise), please clearly indicate that. You will not receive any credit for those implementations. You have one and a half week to work on this assignment, please plan accordingly, and start early. If it is still not clear, this assignment is VERY DIFFICULT!! L  Please start early! J

 

 

Extra Credit:

 

3pt: Implement two extra threads supporting insertion and deletion via separate threads.

3pt: Implement memory printing as a separate thread. Note: in order to print memory manager pool, you need public access to both the list and the memory pool.

 

You will get a maximum of 6 pts for extra credit. Implementation with no corresponding design document submission will not get you any extra credit.

 

This programming assignment contributes 15% towards your final grade for this course.