Assignment 1 of soen423

First Try

1. General analysis

1.1. "startAuction"

a) It is called by auction managers and auction managers can be regarded as special users compared with auction bidders even though from programming perspective they are all clients to our system.

b) You may need to check "repeating itemNo starting". i.e. An itemNo is already started. At first glance you may think there is no synchronization issue here, but the "repeating-checking" is already a "common-data-simultaneous-accessing". So, protect your "active-bidding-table-entry" with synchronization tools like Semaphore, or simply make "checking-function" synchronized.

c) General validity checking such as negative startBid. etc.

1.2. "getBid"

a) It is a "reading" operation which has no synchronization issue here. But general validity checking is still there.

1.3. "placeBid"

a) Similar validity-checking like "startAuction" plus "bidID" (whether four digits?) "proposedBid" (negative?) etc.

b) A "writing-possible" operation and definitely "synchronization" function which must be protected by "critical-section" with Semaphore or make it "synchronized".

c) The biggest performance bottle-neck which may require fine-grained synchronization design. i.e. Bidding items under different auction managers are stored in separated table so that your synchronization mechanism doesn't lock the whole system for a single bidder.

d) Carefully choose your in-memory-storage table class so that "searching itemNo" is efficient. For example, "Vector" is not as good as "HashTable".

2. Synchronization

2.1. Synchronization is one big issue in this course and if you pay attention to this then you will learn almost nothing in distributed system. Here is my old simple notes about synchronization and I am pretty sure you can googled with countless examples. And there are lots of detailed problems discussed in my tutorial page of comp6231_summer (Please don't go there unless you are absolutely free because it is really a mess. Sorry for my laziness. ) However, some issues are similar and you can find those common-mistakes.

3. Testing

3.1. If in your submission there is no testing cases, I would say it is only half-finished because a distributed system is always error prone.

3.2. How to test? As instructed by professor, you must create a bunch of threads to run simultaneously and call all those "getBid" and "placeBid" functions. The parameter for them maybe generated randomly which is very good because it can test your validity-checking.

Second Try

1. General analysis

The center of this assignment is to train you to establish synchronization concept.

a) You don't have to explicitly create "thread" for each function call in "server-side" because RMI will do it for you. So,

beware that your methods are all done in "multi-threaded" environment. It is your job to keep your classes "thread-safe".

b) A small trick about "time-to-close" is that you don't have to use a "Timer" to update the closing "seconds" per second.

The simplest way is just to keep a "expected-closing-time" as a data member of your class "AuctionItem".

c) The following is a just basic implementation in pseudo-code in case you feel hopeless in this assignment.

class AuctionItem
{
	public int expectedClosingTimeInSecond; //time to close in second
	public int itemNo; //six-digit-integer
	public float currentBid;//the current highest bid price
	public int bidderID;//four-digit-integer of id of bidder
}

class DAM
{
	public HashTable activeItemTable;//the table to store active auction item

	//this method should be synchronized 
	public synchronized int startAuction(...)
	{
		//validity-checking
		//first search item no in HashTable
		//if it is null, add the new item
		//return current item no.
	}

	//this method is a read-only method
	public int[] listItem(...)
	{
		//get current time in seconds
		//scan hashtable by using "Enumeration" from method of "element()"
		//check if current time is bigger than the closing moment of auction item
		//if yes, add to return array
	}	

	//this is a read-only method
	public AuctionItem getBid(...)
	{
		//get item from hashtable
	}

	//this is a write method and should be synchronized
	public synchronized boolean placeBid(...)
	{
		//validity-checking
		//get item from hash table
		//check time and bid price to decide whether to accept
		//update if possible
	}
}

2. Performance

2.1. Is "synchronized" key word enough?

Surely it is enough for a beginner. If you are aiming for high efficiency, I would be willing to show you how deep the rabbit hole goes.

a) First Try: 

Items under different auction managers don't have to be mixed together. Why don't we create a concept of "AuctionManager" 

such that it has a list of active items? Instead of "synchronize whole DAM class", we push our synchronization to a fine grain at level of 

auction manager.

class AuctionManager
{
	public HashTable activeItemTable;
	public synchronized int startAuction(...){...}
	public int[] listItem(...)
	public AuctionItem getBid(...)
	public synchronized boolean placeBid(...)
}

class DAM
{
	public HashTable activeManagerTable;
		
	public synchronized int startAuction(...)
	{
		//get auctionManager from manager table
		//call acutionManager.startAuction() method
	}
	public int[] listItem(...)
	{
		//get auctionManager from manager table
		//call acutionManager.listItem() method
	}

	public AuctionItem getBid(...)
	{
		//get auctionManager from manager table
		//call acutionManager.getBid() method
	}
//Please note here we don't have to declare it as "synchronized" because it is done at "manager-level"
	public boolean placeBid(...)
	{
		//get auctionManager from manager table
		//call acutionManager.placeBid() method
	}
}

b) Is it good enough? Not necessarily! 

You see, different auction items are actually independent. Why should we "lock-up" whole items when 

we only lock the perticular item? Why don't we push synchronization at level of "item" instead of "manager-level"?

class AuctionItem
{	

	public int expectedClosingTimeInSecond; //time to close in second
	public int itemNo; //six-digit-integer
	public float currentBid;//the current highest bid price
	public int bidderID;//four-digit-integer of id of bidder	
	
	public AuctionItem getBid(...)
	public synchronized boolean placeBid(...)
}

class DAM
{
	public HashTable activeItemTable;//the table to store active auction item

	//this method should be synchronized 
	public int startAuction(...)
	{
		//validity-checking
		//first search item no in HashTable
		//if it is null, add the new item
		//return current item no.
	}

	//this method is a read-only method
	public int[] listItem(...)
	{
		//get current time in seconds
		//scan hashtable by using "Enumeration" from method of "element()"
		//check if current time is bigger than the closing moment of auction item
		//if yes, add to return array
	}	

	//this is a read-only method
	public AuctionItem getBid(...)
	{
		//get item from hashtable and call item's method of getBid
	}

	//Please note here we don't have to declare it as "synchronized" because it is done at "item-level"

	//by doing this, we actually allow multiple thread to access this method to improve concurrency	
	public boolean placeBid(...)
	{
		//get reference of item from "activeItemTable

		//note here we call item's "synchronized" method "place bid" 

		//call currentItem.placeBid()		
	}
}

c) Which one is better? 

In java, many programmer prefer to use the following syntax for synchronization:

	AuctionItem itemRef=(AuctionItem)activeItemTable.get(itemNo);

	synchronized(itemRef)

	{

		itemRef.placeBid(...); //assume AuctionItem's placeBid is not "synchronized"

	}

But is it better than b)? I think not because by using "synchronized(itemRef)" you even block those benign "read-only" method like "getBid"

if you are not properly design your code, if you plan to implement "getBid" also at level of "item". 

d) What else? 

Have I mentioned about "thread-safe-class" issues? Do I mention about how to remove those "closed-items"? Who should do this job? A "Timer"?

3. Testing

a) Which is better? To run multiple client program in different hosts or to run a single client program which has multiple

threads?

In this course, we are dealing with distributed computation environment and multiple accessing is so common that your testing must simulate it.

And my opinion is to write a client program with multiple threads so that they can access your server program simultaneously because it is 

hard for you to press running button across multiple hosts, even with help of your classmates.

b) Is this enough?

However, there is a small flaw by creating multiple threads in your client program because you have to create them one by one and run them by 

calling their "start" method one by one. It is highly possible that they just run through your server one by one because sometimes your server

runs very fast. In other words, you don't really create a situation that multiple threads access your server simultaneously. 

A small trick is to use a "Class CyclicBarrier" to "block" the created threads so that all threads run at the same time. Check the example here

in www.sun.com

4. Report

a) Why is it so important? 

Because in this course, the mark of your assignments and project has as much as 50% of your total grade. And report is half of your programming

assignment. 

b) What do you expect to write?

From purely software engineering perspective, your report should include the basic class diagram, design detail etc. What is more important is

that you are expected to write down your "design choice" after you give some detailed analysis. For example, the correctness and performance 

are the two kernel of all system and how you guarantee to achieve this goal. When , where, why, and how you make proper synchronization in your

program? When , where, why, and how do you provide your system with high performance?

c) What else?

Another big issue in distributed system is that the situations are so complex that no system can guarantee to cope with all challenges. It is 

up to you to write down your "assumptions" and "limitations" of your system. For example, do you expect "startAcution" to be called repeatedly

for the same item no even when auction bidding starts? Do you expect same bidder id to "placeBid" at the same time? (Is it impossible in real

life? What if Bill Gates share his ID with Mrs. Gates?) 

Third Try

1. Why bother?

If you are not convinced by what you can see, I think you probably will not spend your time to do what you are asking to do. OK, let me try to convince how things can go wrong with this "buggy" sample program. It is like this:

a) I extend our "HelloWorld" example with two extra method, one increase our price by 100, the other decrease the price by 100. I deliberately to make the "modifying" statement using "more than one instruction" so that it is possible to be broken by a context switch with another concurrent thread.

b) My client program now will run two groups of threads, say 50 of each. One group of threads try to call increase price method and the other group try to call decrease price method. Since the number of threads of two group are equal, we can expect that the starting price will be equal to ending price. i.e. When testing starts, my balance at server is 5000 and 50 threads increase price each by 100, and 50 threads decrease price each by 100. The final result should still be 5000.

c) In order to create a real concurrent situation, I use a "CyclicBarrier" which stops all threads from running until all threads are ready. Otherwise the threads are created one by one and started one by one, you may not be able to observe they run concurrently.

d) Compile and run the program and see what happens. You will probably get a different balance. Try to modify your method of "incPrice" and "decPrice" in HelloImpl and see if you can fix the problem.

e) If you can deliver a similar testing program in your A1, I will be convinced that your program is fully tested.

f) By the way, if you want to declare any method in your "Interface" which inherit from "Remote" interface, make sure it is declared as  "throws java.rmi.RemoteException;". Otherwise you may get some error.

Here come the comments which you may ask yourself...

1.   You say in your webpage about StartAuction function that we must to
check whether an itemNo is already started. However in my application
it is the server which create the item number so how can I detect
whether it is an "repeating item starting"?
　

Just as I said in my blog, this is called by another kind of client, namely auction
managers who are also client in programming perspective. For example, when your server
start running, the auction managers also start your client program in some hosts and call
your "startAuction" function to "post" item for bidding. Surely you don't want your
system can only post some fixed items only, right? Because it is too boring.
So, don't try to initialize your item by server. They must be started by "startAuction"
which can be called even when bidding already starts. Imagine the real world bidding
scene.
　

2.> I think that I badly asked my question : I understand items are
> started by the method 'StartAuction' but my question was "By which
> mechanism can you detect whether the item is already started?"
> Checking whether the attribute item id is already stored? This can't
> work because I generate an unique item number just before to add the
> item in my hashtable, so they will be never two identical item id.
>

ok, I now see your point as I have a slightly different interpretation of "startAuction".
1. If we allow server to generate item no for us, surely we don't have to check conflict item number as long as the item number generating method is correct one. (I will talk it later.)
2. If we allow auction manager to input the item no from client side, surely we have to check if item number is already in use.
3. I think most people and professor intend to use no. 1).
4. However, in either case, you need to make sure your method is properly synchronized. There might be several approaches.
a) Simply using incremental number for next item no. and make sure at least the incrementing part is synchronized.
__EnterCriticalSection;
 increment(currentItemNo);
__ExitCriticalSection;
  return currentItemNo;
b) Using "random" function. But theoretically random number doesn't guarantee no-repeating. In some cases, for example, your server generate multiple instances and each with the random class starting from the same random seed, then your random function will give the exact same random number. In web service, if you don't configure your server properly, every call will create a servlet to handle your request and you probably encounter this in your third assignment. In all, it is a better way to check repeating when you use random function.
c) Some professionals may tend to use pre-generated, uniqueness-guaranteed list of item no and save them in a table at the beginning of server program. This maybe the professional way but a bit out of most students' approach.

5. In all case, you must prevent multiple requests generate same item number.


            Common Mistakes in Assignment 1

            (Some mistakes are not so "common". However, it is worthwhile to notice them before you repeat them.)
　

1.  By using a single variable of AuctionItem and all your "StartAuction" will only insert one item in "ActiveItemTable".

class DAM
{
	private AuctionItem myItem=new AuctionItem(0,0,0);//some default value
	...
	public synchronized int placeBid(...)
	{
		...
		myItem.itemNo=myItemNo;
		myItem.timeToClose=myTimeToClose;
		...		
		activeItemTable.put(myItem.itemNo, myItem);
		...
	}
	...
}

This mistake is probably originated from STL of C++ where containers like list, vector, set are holding "copy" of item instead of "reference". Unfortunately in java every complex type other than "primitive type" like int, float etc are all "references" or "pointers" in C++. So, every time you want to generate a new instance, you need use "new". I think this kind of mistakes only happens for java beginners or C++ zealots.

2. How can you return a integer array without knowing its length in advance? And how can I iterate a HashTable?

The most intuitive idea is to put them in a "self-incremental-container" first and later copy them out one by one.

To iterate a hashTable, we can use "Enumeration" or "Iterator"
Enumeration myEnum=HashTable.elements().

AuctionItem temp;
Vector myVect=new Vector();

While (myEnum.hasMoreElements())
{
	temp=(AuctionItem)myEnum.nextElement();
	//and put the temp into a AuctionItem array or vector
	myVect.addElement((Object) temp);
}

//now we copy the data item one by one
int[]  result=new int[myVect.size()];
for (int i=0; i<myVect.size(); i++)
{
	result[i]=(AuctionItem) myVect.elementAt(i).itemNo;
}
return result;

//But I found some guy has a even better way to do it. There is a method called "toArray()" of Vector. So, simply return it //without copying. This is a purely new discovery for a java beginner like me.

3. Why on earth do I need to care about synchronization at all? Can system do it for me with "magic"?

I think no system will take care about user level synchronization issues because system simply doesn't know your application logic at all. So, don't escape from this subject! If you want to become a serious programmer, do it by yourself.

The following is just a brief repetition about how things are going wrong.

In DAM, it is possible that two requests from two clients call "PlaceBid"
for the same itemNo and different "ProposedBid"
Obviously they will get the same reference of AuctionItem in "PlaceBid" and 
call its "PlaceBid" method in a interleaved manner. i.e. a race condition happens here.

In your AuctionItem class, assume your method "PlaceBid" is not synchronized.
Then at the statement of 

"if bidValue > getCurrentBid())" 

it may return true when the first request call this and immediately a context switch happens such that the second request gets a 
chance to run the same "PlaceBid".   Here the second the request may update the "CurrentBid" to a bigger bid and exit. 
When the first request wake up, it continue its execution to update the bid because he thinks the statement above is still true.

4. How to design a test case? 

Some of you guys have a slightly wrong concepts in testing. Do we really care about whether any method is correctly synchronized or whether 

our program runs correctly? Indeed our goal is to run our program with correct result and synchronization is simply just a tool.

So, we don't aim to test if some "critical part" is correctly "blocked". Instead we design a real world scenario and test if our program is 

giving correct answer. Of course this is all based on your analysis when, how and where the program can go wrong. That is why professor gives

half marks for report! Even though this is just a simple concept, still I think it is worth noticing.

5. How to test "placeBid"?

As I mentioned above, we want to give a real world running environment and test if anything can go wrong. For example, the logic behind this is

after all bidders place their bids, only the highest bid get placed. So, your program should reflect this. Is it simple? This is purely a 

commonsense and has little to do with any skills of programming language, right?

6. Do I need to clear up my activeItemTable by a demon?

This seems to be a good approach. However, do you really need to create a thread to this? The answer is no because what you

need is a Timer instead of a separate thread busy looping. (Of course even Timer can be considered as a separate thread. But it is system level and is implemented with high efficiency.)

The following is a simple demo:

Class MyTimerTask extends TimerTask
{
	Private int myItemNo;
	Private DAM myDam;
	Public MyTimerTask(DAM dam, int itemNo)
	{
		myItemNo = itemNo;
		myDam=dam;
	}

	Public void run()
	{
		myDam.removeExpiredItems(myItemNo);
	}
}


Inside class AuctionItem, modify to add a private data of Timer and also 
modify the constructor
Of AuctionItem to pass a reference of DAM.
Class AuctionItem
{
	public	DAM myDam;
	Public AuctionItem(DAM dam)
	{
		myDam=dam;
	}
	Private Timer myTimer;
	public synchronized Boolean placeBid(int bidderId, float proposedBid)
	{

		...
		myTimer=new Timer(new MyTimerTask(myDam, itemNo));

		...
	}
...

}

7. In rmi, if you need to return a type or passing a parameter other than "primitive type", then you need to implements its

"Serializable" interface. And in most cases, you can simple "declare" it "implements" without really doing something.