Semaphores, races, critical sections and Scratch. Plants vs. Zombies

  • Tutorial

Almost everyone perceives Scratch as entertainment with quick results. Indeed, this is important in the first couple. However, let's step over this face today and look at the other side of programming.


I want to share with you a very interesting case that I gave to children to explain the organization of access to one resource from many sprites and simultaneously running scripts. This brings us closer to the serious topic of multithreading.



Multithreading, in simple terms, is when several pieces of code / scripts are executed at the same time. Today, it is already difficult for us to find programs that run in a single thread or sequentially. And it is very important to know the basics of working in such an environment. After all, the problem opens when several simultaneous pieces of the program try to change the resource that exists in a single copy or to individually gain control over it for a while.


I will also write scripts in such a way as to minimize duplication. Those. I will use clones of sprites, but not separate sprites. To master this programming style is very important in order to avoid future floods (1 change leads to 4) and simplify the search for errors.


In this game, everything is simple, we have 4 lines on which the plants are placed, in our case, the pea shooter plant, which can release shells at the zombies coming to it at regular intervals.


→ Link to the game blank


Copy the code examples and get the result.


IMPORTANT : you can only change the sprite "Gorokhostrel"


Take a closer look at the logic of plant work with children. And you will see that sprites, for example, of plants act in the same way, despite their different positions. So we can make a common code and clone an object, and not create another sprite. The location of the sprites is not very interesting to us now, everything is simple, but if you want me to write and explain this code, then write in the comments.


Creating 4-8 plants is not difficult. Clone, clone and clone again. And now we come to the point that these plants must shoot. Think about it, 4-8 plants want to simultaneously access one bullet sprite.


Imagine that 4 players stand around a soccer ball and hit it at the same time, no use, but what an injury. Therefore, you need to organize access to the resource. One owner per unit of time.


Speaking in terms, a bullet is a critical resource / section. And the struggle for the right to possess this resource is called a race . In other words, 4 objects / clones of the plant begin the race for the right to own a critical section / resource.


What is the shot algorithm in a nutshell?


  1. Pass the clone coordinates of the plant clone
  2. Create a bullet clone at the coordinates that will fly towards the zombies.

If you do not access this algorithm / script, there will be consequences. After all, this script is a critical section. All bullets will fly out of the last clone exposed, without any delay.



To transfer the location of the clone of the bullet plant, we need a place through which we will transmit the coordinates (x, y). I use the "walnut clone coordinate" list, since the two given values ​​must be transmitted together.


Now let's try to separate access to this variable in such a way as to at least avoid the behavior from the previous video. The easiest way is to try to split the resource by time in a split second. We get a more tolerant result. But this option again does not exclude the simultaneous ownership of the resource and the accidental interception of the bullet object.







To organize access to the section , it must have a guard who stands at the entrance so that only one object can access the bullet and create a copy of it. His name is a semaphore. A semaphore is a primitive of ordering access to a resource, which guarantees the use of the resource by only one object, and can take several values ​​(0,1, 2, 3, 4, in our case).


Let's try to write access to the critical section through a semaphore.


  1. We are waiting for a random number of fractions of a second to immediately minimize the simultaneous blocking of the resource by several clones of objects.
  2. We request access from the guard / semaphore. Therefore, we increase the value of the semaphore by 1.
  3. Check that no one else took the semaphore. Your value should be exactly 1. And if so, then perform the critical section.
  4. And in any case, release the semaphore, i.e. decrease the value by 1.

Suppose that for this resource 2 clones compete (clone 1 and clone 2), their scripts are executed in parallel, at the same time. There are several possible scenarios for program execution. And yes, in real life, the processor interrupts the execution of any program or its thread at random times.





A scenario where no one will execute a critical section


Clone 1 captured the semaphore first, i.e. increased its value by 1. And suddenly, the processor interrupted its execution and gave time for clone 2 to work, it also captured the semaphore. The semaphore value became equal to 2 . The processor transferred control to clone 1; its next instruction is to verify that it is the only one who has captured the resource, i.e. the semaphore value should be 1. However, it discovers that this is not the case and skips the critical section. Clone 2 starts again and also does a check. He sees that the semaphore is 2 and skips the execution of the critical section. Goes to the instruction to reduce the value of the semaphore by 1 and releases the semaphore. And clone 1 also releases a semaphore.


Scenario in which clone 1 will perform critical secki


Clone 1 got processor time again. It captures the semaphore and proceeds to the next comparison operation. Checking the value of the semaphore, he sees that only one he got access, he goes to the critical section and suddenly, the processor interrupts its execution and clone 2 enters the game. He grabs the semaphore, moves to the next comparison instruction, and he sees that he is not the first to capture this resource. And bypasses the critical section. The processor again gives time to clone 1 and he begins to execute the critical section. Executes it and releases a semaphore. Clone 2 also releases and the race begins again.


We have now touched on a small piece of work in a multi-threaded environment. Where many objects strive to work with one resource and their scripts work simultaneously. It remains only to make sure that we had 10 shots and shots passed through equal periods of time, at least approximately;) To do this, add the variable “shot took place” with a visibility zone “only for this sprite”.





Good luck to children and adults in multi-threaded programming.


Disclaimer : It uses not very precise definitions and their simplified forms for easier understanding of the material. Also, I deliberately did not raise the topic of the atomic context, so as not to injure the psyche, and believed that the correct change of the semaphore variable from several clones / threads is guaranteed by the programming language.


PS: This article will be useful to you - it will tell you about the work of variables with the visibility zone “Only for this sprite”.


Also popular now: