Concurrency on 2D array

[Mlada Jagnjetina]

Hello Everyone!

This is my first post here, so sorry for the bad way of explaining the problem
I am working on a school project, and it is necessary to create a city matrix on which people will move and set up some additional facilities (houses, hospitals ...). The main rule is that people must keep a distance of at least two fields when moving (It's Corona time). I made an application that simulates the movement of people but without the use of threads. I've read a lot about threads and how to sync, but I'm not doing well ....
I want each person to be one thread.
I am interested in how to generate the next step of a person to check if there are other people at a distance of 2 fields in relation to the intended field (with no concurrency is easy, because I take a 9x9 matrix and see if there are other people in those fields, if no people the right step, if there is I am looking for another direction (all directions are possible) because other people then cannot move because i use only one thread and loop).
Do I need to put the whole matrix in a synchronized block (which sounds very bad to me because matrix is 100x100) while I generate the next step and how will I ensure that if I find a 9x9 matrix (in 100x100 matrix) in which there are no other persons, the second thread does not get its time and enters that 9x9 matrix, so that the matrix would no longer be empty and the first person would enter and be at a distance of less than 2(obviously "race condition").
So, if I am in position (5,5), and I choose the RIGHT direction, I go to the field (5,6), but to make that step, it must not be other Persons in the range of 2 fields on either side of the field (5.6 ) be other Persons.

[Norm Radder]

Another idea instead of using threads, is to do the movements at fixed time steps.  Each person would have a flag that determined at what time step they were to make a move.  So at each time step some people would move and some not.
Sort of like how the Game of life runs.

[Mlada Jagnjetina]

Yes, I had that in mind, but the movement of persons must not be predictable in any way (neither the start time nor the order), and the use of threads is required... Such a way of realization would be similar to my first way, because it is still predictable and periodic (which is the same as using a loop). Thanks for the reply anyway!

[Piet Souris]

If A is at (0, 0) and B at (0, 2), is it possible to move A to (0, 1), and next B to (0, 3)? Requiring an empty 9x9 seems pretty rectrictive.

And can you explain this sentence:

but the movement of persons must not be predictable in any way (neither the start time nor the order), and the use of threads is required.

.

Using a Thread for each person is possible, but the synchronizing is pretty expensive, and it makes that the threads are executed sequentially anyway. So you might as well use one Thread (Norms advice seems also very reasonable to me).

But maybe I miss what your intentions are. If this is an exercise, can you show it to us?

[Mlada Jagnjetina]

B can't be at (0,2) if A is on(0,0),because distance is less then 2(only one field(A on 0, B on 2, only 1 is between them));
If B would be on (0,3) and A on (0,0), it's not possible to move A on (0,1) because distance would be less then 2 fields. I can move A only on (1,0) in this case.
Yeah, I understand it's expensive, and if i block every object to move only one, i don't see the purpose of the threads.
One friend told me to use Lock object, but i do not see how honestly...

This is the start of project
In the imaginary city of CoronaCity, it is necessary to simulate the operation of the post-emergence population monitoring system
dangerous virus JavaKov-20. The city is represented by a square matrix whose dimension it can have
the minimum value is 15 and the maximum is 30 and is determined randomly when generating the matrix itself.
The inhabitants of the city are divided into three groups: children, adults and the elderly. Each resident is characterized by a unique
identifier, name, surname, year of birth and gender, as well as the identifier of the house in which they live. Children are old
from 0 to 18 years, adults from 18 to 65 and aged 65+. Residents live in houses. Each house has a unique
identifier and counter that tracks the current household number. Children cannot be alone in the house. Every resident
it also has a body temperature that is generated automatically and changes every 30 seconds

This is the problem...
...When moving, it is necessary to take into account that the distance between the two inhabitants must always
be a minimum of two fields, except in the case of a child: the child may be on a smaller one
distance from an adult or other child. In case the distance is disturbed by the movement, the resident changes
direction of movement. Movement should not be predictable in any way (it is best to use threads for each person). During the movement, for each resident, his name is displayed combined with a unique
identifier, which side it is moving to and in which field it is located......

[Piet Souris]

I see, thanks for the info.

So, people may get out of their house (provided they do not leave a lonely child behind), or get into their house (provided the distance is 0?), et cetera.

How did you model all of this? Do you have e Person class, and a House class? Did you have the Person class implement Runnable? (I was thinking of a Runnable that once started, moves the Person, releases the lock on the board, and goes to sleep some random time).

And lastly: do you give each Person a Timenr that sets that temperature? And what to do with these temperatures? Curious to know!

[Mlada Jagnjetina]

Thank you for your interest,

Yes, I have a Person class (which is abstract and implemented by Runnable) and a House class, but I don't keep a list of people in the House class, I keep a HashMap <homeID, ArrayList <Person>> in the Main class (I don't know if that's a better way to implement , or simply to keep a list of people in that house for each House object, but i do not know what would i do with person ID and house ID then) ...

Yes as you wrote, private static Object lock; in the Person class and before generating the next step I go into synchronized (lock) (I think this is the only way to prevent other Persons from moving or I don't see better way) ...
So I'm wondering if this way of syncing is good, or I should have a private Object lock without "static" (although I don't see if I would do the same with it) ....
Thank’s for curiosity, I have a TemperatureChanger class that extends TimerTask and periodically changes the temp for all people.
This is only part of the project, if someone has a temperature, and is next to the "ControlPunkt" facility that measures the temperature, the person stops, an ambulance picks him up, transports him to the ambulance, all the people who were in the house with him return to house and don't go out anymore etc ..
I would like to post the code, but it is not written in English (except for the key words: D), so I don't believe it would be understandable ....

[Norm Radder]

the movement of persons must not be predictable in any way

That could be controlled by using random numbers.

[Mlada Jagnjetina]

That's true. That is the way how I implemented all the functionality, as I wrote at the beginning, when I worked without threads, but I would like to do it using threads (because the exams that follow involve using threads and syncing)...

[Norm Radder]

I don't know what advantages there would be to using more than one thread for this project.  Threads are a way to do two or more things on a computer at the same time.  The number of things that can be done simultaneously is limited by the number of CPUs your computer has.

[Paul Clapham]

This problem sounds to me a bit like the Dining Philosophers Problem, in which you have a collection of people whose actions might possibly interfere with the actions of others. You might want to have a look on the web and find out about techniques which have been used in solving that problem.

[Piet Souris]

Thanks, Paul, I had never heard of that problem.

I saw a film on Youtube about it, and that film showed a solution by having a waiter that has to give permission to a Philosopher before he/she could grab two spoons. and that solved the problem.

But that made me thinking. There are 5 spoons, so in theory two people could be eating any time. And so I was thinking again about this project. If a Person, at (0, 0), wants to move, that should not prevent a Person at (100, 100) from moving. However, Person one owms the lock on the matrix.

So, could we not also have a 2D array of Locks? For instance, that Person at (0, 0) could try to obtain a lock on field (0, 3), and if succesful, just move to (0, 1). Person (100, 100) can do the same. That means that usually more than one Person can move.

How is the distance between two fields defined?

[Mlada Jagnjetina]

Piet Souris, that was the actual point of my question, I have implemented it like Dining Philosophers, but as Norm Radder sad

Norm Radder wrote:I don't know what advantages there would be to using more than one thread for this project.  Threads are a way to do two or more things on a computer at the same time.  The number of things that can be done simultaneously is limited by the number of CPUs your computer has.

.

And this is true if, I lock all persons on map to move only one, threads are useless...

Piet Souris wrote:
So, could we not also have a 2D array of Locks? For instance, that Person at (0, 0) could try to obtain a lock on field (0, 3), and if succesful, just move to (0, 1). Person (100, 100) can do the same. That means that usually more than one Person can move.

That's why i asked if i can somehow lock only part of the matrix. For example if a person wants to field (2,2), fields in range (0,0) - (0,4) - (4,0) - (4,4) should be locked, but the person on (9,9) should be able to move freely

[Piet Souris]

I think you can relax that 9x9 a little.

If (5, 5) wants to go to (5, 6) and it is posible, then it is not necessary to lock (5, 3). This way, we can have  simultanious moves (5, 2) -> (5, 3) and (5, 5) -> (5, 6). But I asked how distances are defined. What is th distance from (5, 5) to (7, 6)?

[Mlada Jagnjetina]

Distance from (5, 5) to (7, 6) is one field (the shortest possible distance).

[Tim Holloway]

The idea of having 10,000 locks makes me shudder. It's both a lot of overhead and a lot of opportunity for deadlocks.

What I'd probably shoot for myself is some sort of quantum time. That is, instead of ticking a coarse-grained clock like the Game of Life does, I'd make the clock tick faster and randomly select a segment of the population to move on any given tick rather than moving everyone once per tick.

Speaking as one who's made a career out of dealing with multi-threaded and multi-processing system, I prefer to keep the number of synchronization points as small as possible.

[Piet Souris]

Never worked with 10.000 locks myself, but I think that it will work. At least it meets the requirements that moves should be unpredictable in direction and time. And we discudded the overhead. I think it's worth trying. That distance function is still unclear to me, but it determines what Locks must be used. And last, I used Locks here, so that lock.tryLock can be used, and trying some other direction if the lock is not available.

Simpler solutions have been discussed. So, Mlada, keep us informed!