Concurrency in SK | Single Threaded


#1

After learning that SK is using single threaded Concurrency, could the implementation be further explained?

For example, if we have several concurrent tasks, does the thread simply switch between the current concurrent tasks and the main task as they complete, performing operations for some specified CPU number of cycles on a given task? or is there some other model being used?


#2

Each coroutine is managed by a Mind object.

Also see:

With each simulation update frame, SkookumScript iterates through all its active Mind objects that have running tasks. Each Mind object has a list of all the coroutines that are currently running on it. Each coroutine will do as much atomic (instantaneously occurring) work as it can until it runs into something (usually another coroutine call) that it has to wait for. When this happens it does as much atomic work as it can in that coroutine, etc., etc. Then when all that it can do is wait for tasks to complete, the next coroutine managed by the current Mind object will continue until it is blocked and so on. Any new coroutines are added to the mind’s list such that they will be run on the next update.

Once all a mind’s coroutines have done as much as they can within the update then the next Mind object goes through the same process. Any new mind objects are added to the update list so that they will be run on the next update.

Once all the Mind objects have completed updating then the SkookumScript simulation update is complete for a given update frame.

There are other details of consideration though that is basically the process.

It is a form of cooperative multitasking:

Cooperative multitasking can be very efficient with context switching between tasks. In SkookumScript it is just essentially incrementing an index counter. Hard to beat that.

An ancestor language of SkookumScript used pre-emptive multitasking though its performance ended up being far worse and it was more complicated to manage concurrency as well. :thinking:


#3

So essentially, the tasks switch when SK completes as much atomic work as it can do, or a “wait” appears.
From our perspective, does SK have uninterrupted sequential execution within a coroutine during that coroutine until it hits an actual “wait” statement or perhaps a call to UE4 can also result in a task switch?
I guess, my concern is that Determinism may be affected if we are doing something like “destroying an object” meanwhile some other NPC is at the same time picking it up.

So I guess what I am saying and asking is that if we are in a section of code where we want to make sure that nothing else happens to the object we are working on, what is to prevent the concurrency task switch?

Theoretically if we have this it appears safe from task switching?

if objects_of_interest.find?[item = @goal]; !idx [           
   !goal_found : objects_of_interest.pop_at(idx)
   goal_found.destroy_sk_actor
]

Versus: Unsafe methodology

if objects_of_interest.find?[item = @goal]; !idx [           
   _wait
   !goal_found : objects_of_interest.pop_at(idx)
   goal_found.destroy_sk_actor
]

Is that essentially correct? Or are both basically unsafe?
Or are both safe?


#4

To be clear, the _wait is dangerous here because if two tasks make it into the find? block, the task that makes it past the _wait first will pop an object that the other task assumes is still at that index. What makes this a bit scary is that the index is valid up until the _wait call. Its validity is undefined afterwards.

So I assume, anticipating this is a real danger, how do we ensure our indices are coherent? We can check that the goal_found is valid, but that’s a symptom of a deeper problem.


#5

It would be the same as other languages, multi-threaded or not. If you are pushing/popping from multiple places, you only trust the index in the exact moment that you calculate it. After that, it’s garbage. In the example above, you should move the _wait to after you pop the actor so that you know your index is still valid and then always check for validity of the object after the wait.

Instead of using indexes for removal, I’d use remove_same to remove a specific object from the list.


#6

Yes, the index problem is more general. Does remove_same call the removed object’s deconstructor? It doesn’t return the removed object.


#7

Nope, it only removes it from the list, if it was in the list. Check the method header, it returns indexes and bools and stuff if needed.


#8

Thanks for the replies.
The idea that an index (perhaps other objects) are not safe except for the moment you calculate it, is somewhat bothersome. It makes sense for multi-threaded, but for single threaded, it is a little more concerning because I don’t ever really know if it is valid the moment after I calculate it. (In other words what use is it to me…if its not valid after the calc unless there is some guarantee its valid in the same line of code or code block. ).

Wouldn’t it be reasonable to add some sort of mechanism that guaranteed a sequential execution code block. so something like:
_do_atomic [
// Cannot Task Switch
// wait just waits here…
]


#9

It would have been more specific if I had said that once you calculate an index, it’s potentially garbage after you _wait. Everything you do in-between _wait's is atomic. Once you _wait, you yield the floor to other code.

All immediate statements already work like this.

[
  some_code()
  !i : some_index()
  more_code()
  even_more_code(i)
  !loc : actor_location
  actor_location_set(loc + [actor_forward_vector * 1000.0])
  // all of the above was atomic

  _wait
  // while waiting, some other code may have jacked my list 
  //and invalidated my index
  final_code(i) // I shouldn't do this
]

#10

Ah, that’s perfect! Thanks.