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

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

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

Multithreading, explaining in simple language, is when several pieces of program code / scripts are executed simultaneously. Today, it is already difficult for us to find programs that run in one 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 a program try to change a resource that exists in a single copy or individually gain control over it for a while.

I will also write scripts in such a way as to minimize their duplication. Those. I will use sprite clones, not individual sprites. It is very important to master this programming style in order to avoid future avalanche changes (1 change leads to 4) and to simplify the search for errors.

In this game, everything is simple, we have 4 lines on which plants are put, in our case, the plant “pea”, which can shoot projectiles along the zombie that comes to it at regular intervals.

→ Link to the game

Copy the code samples and get the result.

IMPORTANT : you can only change the sprite "Gorohostrel"

Take a closer look at the logic of the plants. And you will see that sprites, for example, of plants act in the same way, despite their different position. 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.

Create 4-8 plants is not difficult. Clone, clone and clone again. Now come to the moment that these plants should shoot. Think about 4-8 plants want to access one bullet sprite at the same time .

Imagine that 4 players stand around a soccer ball and hit it at the same time, no good, but what kind of injuries. 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 start the race for the right to own the critical section / resource.

What is the algorithm shot in a nutshell?

1. Give the bullet the coordinates of the clone of the plant.
2. Create a bullet clone at the coordinates, which will fly towards the zombies.

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

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

Now we will try to separate access to this variable in such a way so as to at least avoid the behavior from the previous video. The easiest way is to attempt to divide a resource by time in a fraction of a second. We already have a more tolerable result. But this option again does not exclude the simultaneous possession of a resource and the accidental interception of a bullet object.

In order to organize access to the section , she must have a guard 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 for ordering access to a resource, which guarantees the use of a 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 the semaphore.

1. We are waiting for a random number of fractions of a second to immediately minimize the simultaneous blocking of a resource by several clones of objects.
2. We are requesting access from the guard / semaphore. Therefore, we increase the semaphore value by 1.
3. We check that nobody else took the semaphore. Your value should be equal to exactly 1. And if this is the case, then we execute the critical section.
4. And in any case, we release the semaphore, i.e. decrement the value by 1.

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

Scenario in which no one performs the critical section

Clone 1 captured the first semaphore, i.e. increased its value by 1. And suddenly, the processor interrupted its execution and gave time to work for clone 2, it also captured the semaphore. The semaphore value becomes 2 . The processor has transferred control to clone 1, its next instruction is to verify that it is the only one who captured the resource, i.e. the semaphore value must be equal to 1. However, it detects that it is wrong and skips the critical section. Clone 2 starts again and also makes a check. See that the semaphore is 2 and skips the execution of the critical section. It switches to the instruction for decreasing the semaphore value by 1 and releases the semaphore. And clone 1 also releases a semaphore.

The scenario in which clone 1 will perform critical setskuyu

Clone 1 again got CPU time. 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 comes into play. He captures the semaphore, moves to the next comparison instruction, and he sees that he is not the first to capture this resource. And bypassing the critical section. The processor again gives time to clone 1 and it proceeds to the critical section. Executes it and releases the 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 tend to work with one resource and their scripts run simultaneously. It remains only to make it so that we have 10 shots and shots pass through equal lengths of time, at least approximately;) To do this, add the variable “shot took place” with a visibility zone “only for this sprite”.

Successes to children and adults in multi-threaded programming.

Disclaimer : Not quite accurate definitions and their simplified forms are used here for easier understanding of the material. Also, I deliberately did not raise the topic about the atomic context in order not to traumatize 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 “Only for this sprite” visibility zone.