aspose file tools*
The moose likes Threads and Synchronization and the fly likes Getting crazy: semaphore rythming a scheduler Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Threads and Synchronization
Bookmark "Getting crazy: semaphore rythming a scheduler" Watch "Getting crazy: semaphore rythming a scheduler" New topic
Author

Getting crazy: semaphore rythming a scheduler

Jean-Michel Vilain
Greenhorn

Joined: Aug 06, 2010
Posts: 27

Hey,
I'm getting irritated to see how this simple code fails... one time over 100.000.
Here's the code:



This code spawns null pointer exceptions in two distinct cases.

First case:
22:10: [ERROR] **********START-OF-ERROR**********
22:10: [ERROR] java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
22:10: [ERROR] java.util.ArrayList.rangeCheck(Unknown Source)
22:10: [ERROR] java.util.ArrayList.remove(Unknown Source)
22:10: [ERROR] faeria.world.action.WorldScheduler.run(WorldScheduler.java:21)
22:10: [ERROR] java.lang.Thread.run(Unknown Source)
22:10: [ERROR] **********END-OF-ERROR**********
Line 21 is number 11 in the posted code sample.

Second case:
00:12: [ERROR] **********START-OF-ERROR**********
00:12: [ERROR] java.lang.NullPointerException
00:12: [ERROR] faeria.world.action.WorldScheduler.run(WorldScheduler.java:22)
00:12: [ERROR] java.lang.Thread.run(Unknown Source)
00:12: [ERROR] **********END-OF-ERROR**********
Line 22 is number 12 in the posted code sample.


Notes:
  • Very few code has been hidden from the actual WorldScheduler, no other method modifies the actions ArrayList.
  • The code catching exceptions is primarily there to recover from a WorldAction crashing.
  • This is part of a big ServerSocket (25.000 code lines), its record is 60 players connected.
  • I have checked and every call to schedule(WorldAction) is passing an object just instanciated with new, unconditionally.


  • Designer and developer on FaĆ«ria: Strategy Card Game (www.faeria.net). The server is 100% Java.
    @Jiem_ on Twitter (http://twitter.com/Jiem_)
    Jelle Klap
    Bartender

    Joined: Mar 10, 2008
    Posts: 1836
        
        7

    You'll need to synchonize access to the ArrayList seperately, and completely to achieve visibility guarentees - not just for the purpose of adding, but also for the purpuse of retrieval. The former you've accomplished by making schedule() synchonized, but you'll need to synchonize on the same lock for calls to actions.remove(0) as well. A synchonized block would do, or alternatively you wrap the actions ArrayList using Collections.synchonizedList().

    The thing is that in this scenario a client thread A could call schedule() and increment the Semaphore's count, and then the WorldSchedule thread could get greenlit, and see that the Semaphore has an available permit. It assumes that this must mean an item is available in the ArrayList, but because the Semaphore doesn't enforce visibility of data beyond the state of it's internal counter, it instead gets treated to an empty ArrayList. That's your IndexOutOfBoundsException right there


    Build a man a fire, and he'll be warm for a day. Set a man on fire, and he'll be warm for the rest of his life.
    Steve Luke
    Bartender

    Joined: Jan 28, 2003
    Posts: 4181
        
      21

    Can we get an idea of why you are using an ArrayList + Semaphore for this? Have you investigated BlockingQueue and its family? From the brief code you have, it looks like the only thing you really need is to make sure the WorldScheduler waits on the semaphore until there is something in the List, and then you take just the first one - and that is what the BlockingQueue does so well.


    Steve
    Jean-Michel Vilain
    Greenhorn

    Joined: Aug 06, 2010
    Posts: 27

    Jelle Klap wrote:..., but because the Semaphore doesn't enforce visibility of data beyond the state of it's internal counter, it instead gets treated to an empty ArrayList. That's your IndexOutOfBoundsException right there

    Aha! I'm not sure to understand.
    The schedule method calls release() AFTER adding the action into the ArrayList.
    Seems 100% safe to me.

    Now about what you say... Does it mean that the ArrayList's state has probably not been updated for the Scheduler's thread? How is this possible?! *scared*
    I really need to understand this. I mean, I have to handle lots of multi-threading in this project and I want to succeed.

    I didn't knew about the BlockingQueue, I will use afterwards but I want to understand first.

    Thanks to both of you.
    Jelle Klap
    Bartender

    Joined: Mar 10, 2008
    Posts: 1836
        
        7

    Jean-Michel Vilain wrote:
    Jelle Klap wrote:..., but because the Semaphore doesn't enforce visibility of data beyond the state of it's internal counter, it instead gets treated to an empty ArrayList. That's your IndexOutOfBoundsException right there

    Aha! I'm not sure to understand.
    The schedule method calls release() AFTER adding the action into the ArrayList.
    Seems 100% safe to me.

    What you're describing is piggybacking on synchonization performed by the Semaphore, where the unsynchonized write to the ArrayList gets flushed to main-memory when the Semphore synchonizes on invocation of the release() method. That is a Really Bad Idea (tm), though, as this is a very brittle and doesn't clearly convey intent. Furthermore it will only work corrrectly if you can ensure that the client thread will write to the ArrayList (check), the WorldScheduler thread will read from the ArrayList (fail!), and there will not be any concurrent writes to the ArrayList by multiple client threads (fail!).
    Jean-Michel Vilain
    Greenhorn

    Joined: Aug 06, 2010
    Posts: 27

    Thank you Jelle.
    It took me a long time to respond, you showed me that my vision on of JVM concurrency is incomplete.
    I didn't knew about visibility and ordering, I knew only about atomicity.
    It's been 2 years I'm on this multi threaded server and almost everything seems to be working fine. That's it takes a little time to realize my knowledge about concurrency is full of gaps. So thanks again.

    According to what I have read, I understand I have to choose between 2 different fixes:
  • declare the actions ArrayList as volatile
  • put the body of the while(true) loop into a synchronized block


  • This is still pretty naive, could you tell me if I'm correct and which of these two possibility you prefer?
    Jean-Michel Vilain
    Greenhorn

    Joined: Aug 06, 2010
    Posts: 27

    Mmmh. My bad, the idea to put the acquire into a synchronized block is total garbage, it would generate a deadlock. Only the remove() should be inside a synchronized block.
     
    I agree. Here's the link: http://aspose.com/file-tools
     
    subject: Getting crazy: semaphore rythming a scheduler