Then they're worth a lot. As in "stop your program from crashing" a lot.
Unlike the target of the Normal Whitfield song (War), Semaphores and Mutexes have a purpose that's hardly contentious. Coordinating threads usually doesn't result in bloodshed, though it can result in annoying errors.
tl;dr:
- Mutex will lock access to a variable and needs to be unlocked to allow other threads access.
- Semaphores allow a thread to wait / stop execution until another threads posts.
Thread
Many of Accessible Sudoku's computationally intensive tasks are run in a dedicated worker thread to free the main thread up to handle the UI changes and user interactions.
The Uniqueness indicator, for example, is the colored circle in the corner of game that indicates when a puzzle has one or multiple solutions available. When clicked or pressed the indicator will trigger a fresh check of the active game in the background while the player is free to continue playing.
From the player's perspective there's not much going on that needs to be threaded. Running the Generator, on the other hand, has plenty that benefits from running in the background.
Generator
There are three main tasks Accessible Sudoku uses the Generator level for:
- Find new solutions
- Find new puzzles
- Test puzzle+solution pairs for uniqueness
At the time of this writing the blunt / random approach has been working just fine for finding solutions and puzzles up to level 5 difficulty.
The time it takes to clear the test queue scales linearly with how many tests are in the queue and exponentially with the difficulty of the puzzles.
Puzzle generation has remained the most challenging component.
Puzzles
Many Sudoku games I've played used generic level indicators to roughly approximate some interpretation of difficulty based on their own standards. As many of these games are targeting the advanced players, certain knowledge may be expected for even the "Easy" puzzles.
With Accessible Sudoku puzzle difficulty is a linear(-ish) scale from 1 - 9 and a special mode (WIP) at level 10. Each level up to 7 clears N * 10% of the board's playfield cells (e.g., level 1 == 10%, level 4 == 40%). Level 8 clears 75% of the playfield and level 9 is currently targeting what's estimated to be the minimum number of clues a unique Sudoku puzzle can have (Gary McGuire, Bastian Tuegemann, and Gilles Civario say 17).
Easy, right? To be fair, it's a somewhat naive approach to puzzle generation, as it doesn't actually look for any of the techniques required to solve. Higher level puzzles could be solved with simpler solving techniques (like Naked Pairs or Hidden Triples).
One solution is to keep track of the uniqueness check's recursion depth to assign a rudimentary complexity indicator, but that's a topic for another time.
How puzzles are generated
Random
The first implementation calculated how many cells needed to be blank based on the level, then randomly remove that many cells from the board, before finally testing for uniqueness.
This brute-force approach worked fine up to about level 4 and could hit level 5 given enough time and luck.
Backtracking one at a time
The next approach used a Sudoku solving algorithm known as Backtracking. This is the same technique used by the Uniqueness check to identify how many solutions can fit in a given playfield.
With this approach, Accessible Sudoku now has level 8 puzzles (75% cleared) and is working on level 9.
Where do threads come in?
All the uniqueness checking and computationally intensive part of the above process happens in a thread. The remaining stuff happens in the main thread.
This works fine up to the point where both threads want to access or modify the same bit of data at the same time (or any other number of bad scenarios really).
There are two main tools to facilitate the communication between threads: Mutexes and Semaphores.
Mutex
A Mutex is similar to a library book. One person (thread) can checkout (lock) a book (variable) at a time. If some else (another thread) wants to checkout (lock) the book (variable), they have to wait until the book is returned (unlocked) before they can check it out (lock) to read (or modify).
The official documentation has a good example for using a mutex:
When calling Mutex.lock(), a thread ensures that all other threads will be blocked (put on suspended state) if they try to lock the same mutex. When the mutex is unlocked by calling Mutex.unlock(), the other threads will be allowed to proceed with the lock (but only one at a time).
var counter := 0
var mutex: Mutex
var thread: Thread
# The thread will start here.
func _ready():
mutex = Mutex.new()
thread = Thread.new()
thread.start(_thread_function)
# Increase value, protect it with Mutex.
mutex.lock()
counter += 1
mutex.unlock()
# Increment the value from the thread, too.
func _thread_function():
mutex.lock()
counter += 1
mutex.unlock()
# Thread must be disposed (or "joined"), for portability.
func _exit_tree():
thread.wait_to_finish()
print("Counter is: ", counter) # Should be 2.In this case both ready() and _thread_function() will modify counter, but it's difficult to say which one will come first between different platforms and exports.
This sequence flow diagram shows the sequence if _ready() runs first, but _thread_function() could have locked the mutex first and _ready() would wait / lock until the mutex is available / unlocked.
With a Mutex multiple threads can safely access and modify shared variables.
Semaphore
Where a Mutex is used to coordinate variables between threads, a Semaphore is used to coordinate work between threads.
Threads will execute their task list as fast as they're able. When a thread uses semaphore.wait() the thread essentially goes to sleep until another thread calls semaphore.post(), at which time the sleeping thread will wake and continue execution.
This break in thread execution was vital for Accessible Sudoku's puzzle generation and stopped most of the crashes that had been occurring up to that point.
Wrapping up
While Godot provides a thread-safe API, it's not exhaustive and having good multi-threaded principals will help to add another layer of protection from system crashes.
- Mutex will lock access to a variable and needs to be unlocked to allow other threads access.
- Semaphores allow a thread to wait / stop execution until another threads posts.
Comments