34 replies to this topic

[e_barroga]

//object A's step event:
global.example = 10;

//object B's step event:
hp=global.examlpe;

//object C's step event:
global.example = 100;

The outcome is dependant on the timing of the step event in relation to the instances of these objects. You can have race conditions in GM.

No it isn't, the output is dependent on the order that the instances are created.

instance_create( objecta );
instance_create( objectb );
instance_create( objectc );

Will generate the same output no matter how many times you try.

[sylvan]

//object A's step event:
global.example = 10;

//object B's step event:
hp=global.examlpe;

//object C's step event:
global.example = 100;

The outcome is dependant on the timing of the step event in relation to the instances of these objects. You can have race conditions in GM.

No it isn't, the output is dependent on the order that the instances are created.

instance_create( objecta );
instance_create( objectb );
instance_create( objectc );

Will generate the same output no matter how many times you try.

It's fair to assume in the example code I listed that there is no defined order of instance creation.

Given a different order of creation (a.k.a different event timing) the result of running this code will be different. That's pretty much the definition of a race condition:
google's definition:

A race condition or race hazard is a flaw in an electronic system or process whereby the output and/or result of the process is unexpectedly and critically dependent on the sequence or timing of other events.

In the code I listed the outcome of running the step event is critically dependent on the sequence or timing of the instance creation. Whereas, had I split object A to run in the begin step, B in the step, and C in the end step, the race condition is resolved, because no other events can possibly alter the outcome of this sequence.

I can easily counter your example by just saying the three objects were randomly spawned enemies. A fair assumption, considering large numbers of games do this.

[Yourself]

It's fair to assume in the example code I listed that there is no defined order of instance creation.

No, it isn't, because there is an order.

I can easily counter your example by just saying the three objects were randomly spawned enemies. A fair assumption, considering large numbers of games do this.

Even if the objects are generated randomly, they still execute in the order that they were created, that's a fact not knowing the order is not the same as there not being one. I'm not sure this really counts as a race condition, either, since it requires a rather liberal reading into the definition of a race condition. For example, you overlook the "unexpected" part of the definition. This behavior is not only expected, but it's completely deterministic. Since the creation order of the instances determines the order of execution it would easily be possible to determine what the execution result would be. If it were an actual race condition, knowing the state of the game would tell you very little about the actual state it would reach. The game state would change in an unexpected way because you couldn't predict where it would end up.

It doesn't really matter since race conditions in GM will always be pathological cases that practically have to be constructed outright. In an actual parallel setting they arise all the time because the order of execution is non-deterministic.

[sabriath]

@sylvan: I think you are confusing yourself between what a race condition is and ignoring programming practice in order to force one to occur.

What I mean is...GM is sequential, it does not run on parallel threads or anything special. The code it runs is in a strictly controlled order, and that order is, in fact (with a little forethought), known to the programmer. Begin step, step, end-step, all run in the order the object was created, draw in order of depth (and if those aren't the orders, it doesn't matter...they _DO_ have an order and it _IS_ repeatable). Ignoring these facts does not make it a race condition, it's just you ignoring them.

A true multi-threaded application, however, does not know when and how long it has the CPU to run its code. The O/S designates the time allotment, which is different depending on how many processes are running at any given time, and whether or not the program has to stall in order to read/write on the bus, etc. etc. There is no humanly way to know ahead of time how much code the application will run in this fashion...this is how a race condition can occur.

Think of it like this:

GM is like a marble track, your code is like a bunch of marbles on that track in a specific order....whether or not the OS/CPU/whatever slows down those marbles, or even stops them, the order does not change because GM is single-threaded (there is only 1 track...the marbles behind the stall are also stalled).

MT programs are like having marbles in a shoe box which has holes at the other end, when you tilt the box over, you cannot say for certain which marbles will exit first.

[IQbrew]

Threading reminds me of running more than one room at the same time, using one room to load resources and the other as a responsive tutorial or menu screen.
Although I may be completely off, I just skimmed this topic.

Edited by IQbrew, 21 November 2010 - 09:29 AM.

[sylvan]

@ Yourself, I'm going to reply to sabriath's point mostly, because the two points raised are nearly the same and I don't really want my posts to grow as long as they were previously.

@sylvan: I think you are confusing yourself between what a race condition is and ignoring programming practice in order to force one to occur.

Maybe so, but as I mentioned before, object IDs are not generally used by the programmer to control timing. IDs are not assignable, so the only way to control them is to control the exact ordering of instance creation for every object in the game, including those statically defined in the room before execution. If I gave you a game, where the code above was run in the order C,B,A, would you be able to change this timing without deleting and re-adding those objects? (to make the example seem more real-world, pretend I've given you a game with an exceptionally large room, or something along those lines)

Indeed, what happens if I have a game that says "create an instance of A on keypress 'A', B on keypress 'B', C on keypress 'C'"? for the example I listed before, the game would have different results depending on user input, another factor that cannot be controlled by the programmer. This is a very common situation to be in.

A true multi-threaded application, however, does not know when and how long it has the CPU to run its code. The O/S designates the time allotment, which is different depending on how many processes are running at any given time, and whether or not the program has to stall in order to read/write on the bus, etc. etc. There is no humanly way to know ahead of time how much code the application will run in this fashion...this is how a race condition can occur.

Let me draw some parallels here, which should hopefully enlighten the situation here.

"game maker designates the time allotment, which is different depending on how many instances are running at any given time, and whether or not the instance has been deactivated etc."

You can predict the nature of the OS scheduled algorithms by looking at the process table entries. Much like your analogy of find game maker instance ids to control the order of game execution. Yes, the OS is very much more complex than Game Maker, but the point about scheduling here is the same point your using to say why game maker doesn't have race conditions. The instance IDs are knowable, as are the process states (especially in some Linux distributions). By your logic here, there are no race conditions in game maker, because instance time allocation is served based on object creation order, yet there are race conditions in the OS because processes time allocation is served based on process creation order? The two are the same.

Think about how OS scheduling works, there are (basically) three states a process can be in, running, waiting or blocked. This is the same as saying in game maker, an instance is running, waiting or deactivated. Aside from that, the way game maker and the OS schedule these two things is entirely the same. (although the OS is several orders of magnitude more complex, the analogy holds). Instances and processes can be created and destroyed in both game maker and the OS. The OS will ensure each process gets run, just as Game Maker ensures that each instance will be run.

Edited by sylvan, 21 November 2010 - 10:46 PM.

[sabriath]

Maybe so, but as I mentioned before, object IDs are not generally used by the programmer to control timing.

This is exactly what I meant by "ignoring programming practice"....you are ignoring the fact that GM is sequential, doesn't mean the underlying ability of GM being sequential just disappears on that notion.

If you create object A, B, then C...but you put the create code in the step event of C and the use code in A...that would force an error because you ignored the fact that GM sequentially created A, B, and THEN C.

Indeed, what happens if I have a game that says "create an instance of A on keypress 'A', B on keypress 'B', C on keypress 'C'"? for the example I listed before, the game would have different results depending on user input, another factor that cannot be controlled by the programmer. This is a very common situation to be in.

But it still would not be a race condition unless you purposely made it that way. GM is sequential, I'm not sure you understand what race conditions are.

Here:

left = true;
right = true;
void FunctionLeft()
{
  while(!left){}
  left = false;
  while(!right){}
  right = false;
  eat();
  left = true;
  right = true;
}

void FunctionRight()
{
  while(!right){}
  right = false;
  while(!left){}
  left = false;
  eat();
  left = true;
  right = true;
}


f1 = thread(FuncitonLeft);
f2 = thread(FunctionRight);
thread_start_all();

That can cause a race condition because if 'f1' makes it to "left = false" and pauses execution for 'f2' to make it to "right = false", then both function will be blocking each other on the second "while" loop.

GM would run 1 function first, then run the second function next...there is no race condition, the functions complete before execution is returned for the next task. Like I said, YOU are ignoring this in order to cause an infinite loop somehow, this doesn't mean it's a race condition.

"game maker designates the time allotment, which is different depending on how many instances are running at any given time, and whether or not the instance has been deactivated etc."

You read that wrong....after GM runs all events of all objects that are activated for that step, it puts itself to sleep based on how much time has passed versus the room_speed. This does not affect the code itself at all...when the OS has decided the sleep is finished, it returns back to GM to run the next step in all code in the same order it did last cycle.

You can predict the nature of the OS scheduled algorithms by looking at the process table entries

No you can't, the entries in the table have nothing to do with the task given to each process...nor whether they have put themselves to sleep, or waiting for a specific Semaphore event to occur. You can _guess_ what will be run next on the processor, but not only would you be wrong 99% of the time, but you wouldn't know how long the processor will give that operation (whether it be 1 opcode, or 100).

This is the same as saying in game maker, an instance is running, waiting or deactivated.

There is no analogy because GM is 1 thread, not multi-threaded. Each object is run fully and sequentially each step regardless whether it has CPU time or is stalled. GM doesn't just go to ObjectA and put it's code on the processor and say "oh noes, windows forced it off the processor, let me put ObjectB there instead and come back to ObjectA later"....GM doesn't do that.

An instance is either not in the list to be run, or in the list to be run....and if it's in the list, when GM comes to it, it will run it. It will continue to run it until the code is finished, then it will go to the next one in the list.

The OS will ensure each process gets run, just as Game Maker ensures that each instance will be run.

The OS doesn't ensure anything...at all. GM may ensure an instance will get it's time to run the code each game step....an OS could block a program from running altogether because it's busy doing something else entirely. The time it gives each thread is not the same, so some code may run more than others...while GM may take different times processing each instance, it still processes each instance _fully_ before moving to the next, so the code it runs is the same each time.

[sylvan]

That can cause a race condition because if 'f1' makes it to "left = false" and pauses execution for 'f2' to make it to "right = false", then both function will be blocking each other on the second "while" loop.

The shared resource in your example is obviously a problem in concurrent programming only. Game Maker never preempts function calls, so yes, this kind of behaviour is avoided. This does not mean all timing issues when writing game maker code are avoided. Notably the ones I listed above, whereby the result of a shared variable depends entirely on the timing of the game, which is controlled by instance IDs, not explicitly by the programmer. (Unless of course they perhaps delete all objects in a room and re-adding them in the begin step, but I've not known any game maker program/programmer to do this, it's just a waste of resources).

GM would run 1 function first, then run the second function next...there is no race condition, the functions complete before execution is returned for the next task. Like I said, YOU are ignoring this in order to cause an infinite loop somehow, this doesn't mean it's a race condition.

Function preempting is not the only thing that can cause race conditions. Anything where a shared resource is controlled by timing of events can be a race condition. I'm not saying game maker preempts code, I'm not saying game maker has deadlocks. All I'm saying is that the outcome of the step event over multiple instances is controlled by the timing of the step event, which is usually not defined by the programmer.

You read that wrong....after GM runs all events of all objects that are activated for that step, it puts itself to sleep based on how much time has passed versus the room_speed. This does not affect the code itself at all...when the OS has decided the sleep is finished, it returns back to GM to run the next step in all code in the same order it did last cycle.

I'm sorry, but you read that wrong. I wasn't talking about game maker's sleeping and it's process allocation in regards to the OS. I was talking about how game maker schedules it's instances inside the step event is akin to how an OS schedules processes to avoid starvation.

No you can't, the entries in the table have nothing to do with the task given to each process...nor whether they have put themselves to sleep, or waiting for a specific Semaphore event to occur. You can _guess_ what will be run next on the processor, but not only would you be wrong 99% of the time, but you wouldn't know how long the processor will give that operation (whether it be 1 opcode, or 100).

Yes, I was wrong, the process table is not the appropriate thing to look at, what I mean was the queue. Most operating systems manage a queue of processes (usually a priority queue, but that's semantics). The next entry in the queue will be the next entry run. Usually it's a very straightforward algorithm. Once the process on the top of the queue is run, then it is put on the end and the next process is run.

A process waiting on I/O will not be on this queue until an interrupt happens. When an interrupt occurs, the waiting process is simply moved from the waiting heap and put onto the end of the queue. (if there happens to be nothing in the queue it will run straight away)

This is no different to game maker having a "queue" of instance ids, and running their step events in turn.

As for how long the process is run on the processor, it doesn't matter. The OS will schedule a certain number of interrupts based on priority, if the processes ends before it uses up their time, the next process in the queue will be run. If the processes doesn't finish in time, then it will be preempted, and the next one will be run anyway. You still know the exact order in which the processes will be run, as in game maker.

The way the operating system schedules processes in this fashion is analogous to how game maker schedules instances in the step event.

There is no analogy because GM is 1 thread, not multi-threaded. Each object is run fully and sequentially each step regardless whether it has CPU time or is stalled. GM doesn't just go to ObjectA and put it's code on the processor and say "oh noes, windows forced it off the processor, let me put ObjectB there instead and come back to ObjectA later"....GM doesn't do that.

An instance is either not in the list to be run, or in the list to be run....and if it's in the list, when GM comes to it, it will run it. It will continue to run it until the code is finished, then it will go to the next one in the list

This logic is very wrong. According your your train of thought, user level concurrency (of which there are hundreds of different ways to implement, many of which are nearly the same as Game Maker's, including things like coroutines) would be race condition free, simply because they aren't multi-threaded. Multi-threading has nothing to do with race conditions. Race conditions are important in multi-threaded environments, mostly because of deadlock, but this does not mean that programs run along a single thread of execution are free of all race conditions.

The OS doesn't ensure anything...at all. GM may ensure an instance will get it's time to run the code each game step....an OS could block a program from running altogether because it's busy doing something else entirely. The time it gives each thread is not the same, so some code may run more than others...while GM may take different times processing each instance, it still processes each instance _fully_ before moving to the next, so the code it runs is the same each time.

Your very wrong on this point, to quote wikipedia (it's wikipedia, I know, not the best source, but w/e):

... Modern scheduling algorithms normally contain code to guarantee that all processes will receive a minimum amount of each important resource (most often CPU time) in order to prevent any process from being subjected to starvation.

Edited by sylvan, 22 November 2010 - 03:21 AM.

[Gamer3D]

The shared resource in your example is obviously a problem in concurrent programming only. Game Maker never preempts function calls, so yes, this kind of behaviour is avoided. This does not mean all timing issues when writing game maker code are avoided. Notably the ones I listed above, whereby the result of a shared variable depends entirely on the timing of the game, which is controlled by instance IDs, not explicitly by the programmer. (Unless of course they perhaps delete all objects in a room and re-adding them in the begin step, but I've not known any game maker program/programmer to do this, it's just a waste of resources).

But, as you so obstinately refuse to understand, the timing is always the same in the same conditions.

Function preempting is not the only thing that can cause race conditions. Anything where a shared resource is controlled by timing of events can be a race condition. I'm not saying game maker preempts code, I'm not saying game maker has deadlocks. All I'm saying is that the outcome of the step event over multiple instances is controlled by the timing of the step event, which is usually not defined by the programmer.

But the timing is consistent. If you have a user create A, B, and C in a random order, it will have the same outcome for the same order every time. Unless, of course, you include a step event, at which point the timing matters, but is still deterministic.

I'm sorry, but you read that wrong. I wasn't talking about game maker's sleeping and it's process allocation in regards to the OS. I was talking about how game maker schedules it's instances inside the step event is akin to how an OS schedules processes to avoid starvation.

GM will NEVER pause one instance's event to run another. Your analogy is flawed.

Yes, I was wrong, the process table is not the appropriate thing to look at, what I mean was the queue. Most operating systems manage a queue of processes (usually a priority queue, but that's semantics). The next entry in the queue will be the next entry run. Usually it's a very straightforward algorithm. Once the process on the top of the queue is run, then it is put on the end and the next process is run.

A process waiting on I/O will not be on this queue until an interrupt happens. When an interrupt occurs, the waiting process is simply moved from the waiting heap and put onto the end of the queue. (if there happens to be nothing in the queue it will run straight away)

This is no different to game maker having a "queue" of instance ids, and running their step events in turn.

As for how long the process is run on the processor, it doesn't matter. The OS will schedule a certain number of interrupts based on priority, if the processes ends before it uses up their time, the next process in the queue will be run. If the processes doesn't finish in time, then it will be preempted, and the next one will be run anyway. You still know the exact order in which the processes will be run, as in game maker.

The way the operating system schedules processes in this fashion is analogous to how game maker schedules instances in the step event.

Except in multi-CPU machines, where what goes into the queue can be dependent on the order in which operations were run. Again, your analogy is flawed.

This logic is very wrong. According your your train of thought, user level concurrency (of which there are hundreds of different ways to implement, many of which are nearly the same as Game Maker's, including things like coroutines) would be race condition free, simply because they aren't multi-threaded. Multi-threading has nothing to do with race conditions. Race conditions are important in multi-threaded environments, mostly because of deadlock, but this does not mean that programs run along a single thread of execution are free of all race conditions.

Multi-threading has a TON to do with race conditions. A single thread, such as GM, will proceed at its own pace, with operations being executed in a nice, deterministic order. If it tries to access another thread's data, it gets whatever that thread has done, which depends on the CPU and the scheduler. Therefore, without proper controls, this results in a race condition.

A "race condition" in a single thread is nothing more than bad programming. For example, you might have forgotten to terminate a while loop. This is also deterministic, however, and thus not a real race condition.

Your very wrong on this point, to quote wikipedia (it's wikipedia, I know, not the best source, but w/e):

Congratulations. You have pointed out that OS's like to give a minimum amount of time to processes. THIS DOESN'T CHANGE THE FACT THAT WE DON'T KNOW HOW LONG IT WILL GIVE IT. Nor does it change that multi-core CPUs mess with the timing of even a consistent operation allocation.

[mrme]

There's a DLL that will allow you to run GM on multiple threads.

[TheMagicNumber]

There's a DLL that will allow you to run GM on multiple threads.

That is a hack. It requires you to program in a specific way.

[e_barroga]

sylvan, you don't understand the concept I think moderators should close this thread. Please get yourself acquainted with the topic before hand. Please give me an example of a "race condition" issue in a single-threaded environment.

edit:

In the code I listed the outcome of running the step event is critically dependent on the sequence or timing of the instance creation. Whereas, had I split object A to run in the begin step, B in the step, and C in the end step, the race condition is resolved, because no other events can possibly alter the outcome of this sequence.

I can easily counter your example by just saying the three objects were randomly spawned enemies. A fair assumption, considering large numbers of games do this.

So I'm right.... the output is dependent on the order that the instances are created. You countered your own example not mine.

Edited by e_barroga, 05 December 2010 - 06:05 AM.

[_179701]

I think its completely possible to program in a manner to avoid racing conditions. Whether or not its possible to use multiple threads in gamemaker idk. Whether or not its practical idc unless its not practical cpu-wise.

I didn't feel like reading all of the arguing. However, I do feel like sharing how I would implement the threads.

start:

First I would start with 4 threads considering most users have <5 cores.

I would have an object (which runs on the main thread) take every new instance id and stick it into 4 lists. A list for each thread. It determines which list to put it into by reading a average execution time variable (sticks the new instance id into the list with the smallest average execution time).

Main Loop
{

Each thread processes its own list (instance_id->step) and new instances tacked on to the end a list while deleted instances get removed from their lists.

During the process a object may need to interact with another object such as a collision. All objects have their own 'ActiveEvent' list and 'PendingEvent' list. The instance processing the logic tacks the event, and other instance id to its pending list.

repeat until no more new instances or deletions of instances
{

All threads finish up and wait for each other. (save the position it left off at)

Main thread deletes instances that needs it, adjusts saved positions, then adds new instances to the corresponding thread list

Process all 4 thread lists starting from where they left off.

}

repeat until no more pending events
{

Main thread goes through each list of instances and for each instance it checks the event list and copies the event to the other corresponding instance_id's event list.

All threads Process active events

wait for finish

}

Preform drawing, network stuff, sound, ect

}


Then I program my objects with these rules to avoid race conditions and other whatnot:
No other objects can write to each others variable
Object communication must be done through events
Nothing should modify the thread list while multiple threads are running
and what ever else you can think of

I have no experience in programming with threads. I just wrote this for the fun of it. dont know if its useful or not

Edited by _179701, 23 January 2011 - 08:50 PM.

[GearGOD]

Object communication must be done through events

Imagine Object1 has an event that addresses an event of Object2
While Object2 executes its event, it addresses Object1's original event.
Oops, stack overflow.

Most of the rest of your post is too incoherent to understand or critique.

[_179701]

Yes, I addressed that problem by having events 'exchanged' in between objects during a phase which only the main thread is running. However, I do agree that my writing is pretty incoherent and shouldn't be taken seriously. Its a complex solution to a complex problem thus its difficult for someone like me to explain considering I'm still learning.