Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (487)
Games in Android Showcase (112)
games submitted by our members
Games in WIP (553)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Thread Safety (for my RTS game)  (Read 2713 times)
0 Members and 1 Guest are viewing this topic.
Offline firepowerjohan

Senior Newbie





« Posted 2009-02-01 22:39:59 »

Hi
Been a while since I posted, been busy programning my new RTS game or in fact it is rather a TBS/RTS hybrid.

Anyway, since it uses a peer2peer system (will later convert it to a combination of client server and peer2peer with a web server) I am dealing with thread safety. As of now, I have not had any problems but I only tried it 3 players so far, if game will have 10-20 players problems might show up that I do not yet have realised. So, I am going to check with others here if my method is correct or if I already need to design something better. 

Now, here is how the HOST player works.

It has an orderqueue, basically a class basically like a vector but it decodes the strings you have put into the vector to something useful for the game i.e. an action that is to be performed. A "a 129 133" for example could be decoded as to attack from hex 129 to hex 133 or in code be using like game.resolvebattle(129, 133, blablabla some parameters needed here). So the orderqueue is used by game and the game uses it like a queue so it removes the first element and performs that action (for example might be someone that says "I move my Militia from 30, 30 to 30, 35).

Any requested order in game results to sending into the HOST orderqueue. So there is one queue per game session with say up to 16 players and it is positioned in the host player game. An order means for example move unit or attack or purchase a unit or deploy unit or declare war, ..., etc...

Now, the threads that are used for the socket connections (one socket per client by the way) gets incoming strings and put them into the orderqueue.

I heard that Vector is thread safe but that it is also not 100% thread safe, Meaning, if I do orderqueue.get(0) and say that there is only one object in it and someone else does orderqueue.remove(0) at the same time if I am unlucky the remove is done first and the get results in exception.

BUT, the fine thing is all the incoming traffic result in the add method and only the one thread on the host game will remove anything from queue. This means, there are several thread adding into the queue but only ONE thread running that will ever remove anything from the queue, so is this combination thread safe?

Johan Persson - Firepower Entertainment
Developer of the Commander series (Commander Europe at War, Commander Napoleon at War) and World Empires Live
Offline Jono
« Reply #1 - Posted 2009-02-02 03:02:14 »

Each of Vector's methods are synchronized, so as you describe the situation there should be no problem. Some things to keep in mind though..
When you're adding to the queue, make sure (assuming you are adding an Order called "order" to a Vector called "queue") you use
1  
queue.addElement(order);

and not
1  
queue.add(order,queue.size());


When you're removing from the queue, just something like
1  
2  
3  
4  
if(!queue.isEmpty()){
  order = queue.firstElement();
  queue.removeElementAt(0);
}

will be fine, since you only have one thread doing the removing. Also, make sure you're never iterating over the Vector, because its size could change part way through giving an out of bounds exception.
Offline Jackal von ÖRF

Junior Member





« Reply #2 - Posted 2009-02-02 07:51:03 »

You are using the Vector like a queue, so it would be better to use a thread-safe implementation of java.util.Queue or java.util.concurrent.BlockingQueue. Vector is not meant for being used as a FIFO queue, because adding/removing the first element is an O(N) operation (only adding/removing the last element is an O(1) operation).

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #3 - Posted 2009-02-02 08:47:59 »

If I understand your post, your talking about a "single-producer/single consumer" model (only one thread performs puts and one thread performs gets).  If that is the case you can use a "wait-free" method (no locks or atomic operations).

Here some example code using a circular buffer:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
31  
32  
33  
34  
35  
36  
37  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
58  
59  
60  
61  
62  
public final class CQueue<T>
{
  /** The actual array. */
  private final T[] array;

  /** */
  private final int mask;

  /** Current read position */
  private volatile int rPos;

  /** Current write position */
  private volatile int wPos;

  /**
   *  Creates a queue that can hold up to 2<sup>n</sup> elements.
   */

  @SuppressWarnings("unchecked")
  public CQueue(int n)
  {
    int size = (1<<n);

    mask  = (n-1);
    array = (T[])(new Object[size]);
    rPos  = 0;
    wPos  = 0;
  }

  /** Get an element. Returns <i>null</i> if empty. */
  public T get()
  {
    if (rPos != wPos) {
      T t = array[rPos];

      rPos = (rPos + 1) & mask;

      return t;
    }

    return null;
  }

  /**
   * Adds an element to the queue. Returns <i>true</i> if successful.
   * <p>
   * Inserting <code>null</code> would be a very bad idea as the
   * consumer will think the queue is empty.  This however doesn't
   * break the queue.
   */

  public boolean put(T t)
  {
    int next = (wPos + 1) & mask;
   
    if (next != rPos) {
      array[wPos] = t; // place element before index update
     wPos        = next;

      return true;
    }

    return false;
  }
Offline Mr_Light

Senior Member




shiny.


« Reply #4 - Posted 2009-02-02 09:17:10 »

Yeah like Jackal saids using a Queue makes more sense then reinventing the wheel, moreover BlockingQueue even gives you the bonus of not having to implement a wait mechanism to not waist cpu cycles.(as it blocks.) Make sure the queue is visible to the other threads though.

hmm apparantly Roquen was posted while I was typing:
http://java.sun.com/javase/6/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html
Quote
ConcurrentLinkedQueue:
This implementation employs an efficient "wait-free" algorithm based on one described in  Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms by Maged M. Michael and Michael L. Scott.
If you wanted a wait free one.

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #5 - Posted 2009-02-02 09:26:49 »

The code provided by Roquen is not threadsafe at all!

Not even for 1 thread reading and one thread writing. Both threads can have the fields cached. At least use the volatile keyword, but the CQueue impl has more disadvantages, like overwriting the oldest elements when the queue is full.

Better use the thouroughly tested classes provided in the JRE.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #6 - Posted 2009-02-02 10:27:27 »

General notes:

The reason I suggested a circular-buffer based method is because CAS ops can take 100s to 1000s of cycles on modern processors, so it is nice to not used them unless needed.  Single Producer/Single Consumer can avoid the heavy overhead of atomic operations and locks.  No races, dead-locks or any other headaches of concurrent programming. Also there is nothing faster unless the hardware has specialized support. (Okay, not quite true...but you need to go to cache oblivious or conscious)

@Mr_Light:
This paper look interesting (haven't tried):
http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf

@Riven
I typed off the top of my head and yes I should have stuck volatile on rPos and wPos (bad me). But re-read the code, it does not overwrite any unread element.  The only trick is dealing with a full-queue (via block the producer), but the whole point is to provide a sufficiently large queue for this not to occur.



Offline Riven
« League of Dukes »

JGO Overlord


Medals: 783
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #7 - Posted 2009-02-02 10:42:06 »

Even now, the references in the T[] array can be cached. Adding a volatile to the field obviously doesn't work, as it only ensures the reference to the array is not shared.

So... either use locks or AtomicReferenceArray, otherwise it's bound to corrupt your data, sooner or later, depending on the amount of cores in your CPU, and the amount of CPUs in your system.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #8 - Posted 2009-02-02 12:19:06 »

The problem with not having volatile on the two counters is that the runtime can inline the routines and promote the counters to registers and break sync. This is not possible with the array accesses.

To get the behaviour your describing would require a multi-processor system with an incoherent cache memory system.  These are pretty much only low-cost embedded systems.
Offline Mr_Light

Senior Member




shiny.


« Reply #9 - Posted 2009-02-02 12:30:15 »

General notes:

The reason I suggested a circular-buffer based method is because CAS ops can take 100s to 1000s of cycles on modern processors, so it is nice to not used them unless needed. 
I'm sure the jvm uses the assembly instruction and considering how often that gets called

@Mr_Light:
This paper look interesting (haven't tried):
http://people.csail.mit.edu/edya/publications/OptimisticFIFOQueue-journal.pdf
The abstract looks interesting enough - I'll read the rest tonight.  I like optimistic approaches in general  Wink Usually if you align the rest of the system stuff can run at near optimal, unsafe, speeds.

But to bring it back to core - unless firepowerjohan's profiler said that CAS is a bottleneck of any sorts - we need not worry. Which is why I proposed blockingqueue as it gives you additional stuff for free. In retrospect a simple if(poll()==null){ sleep some } might just as well suffice. I wouldn't mind a hefty discussion about theoretical speeds of queues to satisfy the geek in me though I'm not sure that we want to behave like a bunch of kernel hackers. The culture and temperateness around these forums is far too pleasant to drag it down like that.  

It's harder to read code than to write it. - it's even harder to write readable code.

The gospel of brother Riven: "The guarantee that all bugs are in *your* code is worth gold." Amen brother a-m-e-n.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline firepowerjohan

Senior Newbie





« Reply #10 - Posted 2009-02-02 16:05:36 »

Thanks for all the replies, I did not expect this many replies seems it is interesting topic  Smiley

I am not using single-producer/single consumer since there are many threads that are adding into the vector but only one that is removing from vector. This belongs to the NETWORKING forum in fact so that is why I did not bring up the networking details yet. Why I have many producers is because host has one socket per player so one thread per player in fact. Client only have one socket since all its communication goes to server. Server broadcast to the other clients.

So in a 4 player game the HOST has 3 threads with one socket each picking up messages from that player, using streams (objectoutputstream, objectinputstream). I am not sure, some say I can just use one single socket for all communication and let all players send on it. Would it work like a queue so that no problem occur if 2 players send a message simultaneously I am not sure.

Why I chose vector was, at one time I was thinking the consumer should be able to search through the orderqueue for a specific instruction but so far I have not needed such functionality.


 

Johan Persson - Firepower Entertainment
Developer of the Commander series (Commander Europe at War, Commander Napoleon at War) and World Empires Live
Offline Roquen
« Reply #11 - Posted 2009-02-03 14:53:05 »

In that case I'd suggest using a ConcurrentLinkedQueue.  It scales pretty well from low to pretty high thread contention.

@Mr_Light:
I wasn't trying to start a debate on design & usage of concurrent data-structures. My attempted point was that they should be avoided like the plague when one can.  And if you must and happen to have single producer/consumer, then you can still avoid the headaches.

(entering super geek mode, you most likely want to ignore the rest)

the cycle counts I gave are for the hardware instruction itself, which on Intel-a-likes lock down the memory controller for the duration of the instruction. So all processors are shut-out from reading main memory for the duration, OUCH!
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

TehJavaDev (16 views)
2014-08-28 18:26:30

CopyableCougar4 (25 views)
2014-08-22 19:31:30

atombrot (38 views)
2014-08-19 09:29:53

Tekkerue (35 views)
2014-08-16 06:45:27

Tekkerue (32 views)
2014-08-16 06:22:17

Tekkerue (20 views)
2014-08-16 06:20:21

Tekkerue (31 views)
2014-08-16 06:12:11

Rayexar (66 views)
2014-08-11 02:49:23

BurntPizza (44 views)
2014-08-09 21:09:32

BurntPizza (34 views)
2014-08-08 02:01:56
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!