[UEFN/Verse Language] Mutual Exclusion: Comparison with C Language, Mutexes, and Semaphores

We can help you with your concerns.

You can learn from us.

This article explains mutual exclusion in Verse.

When multiple NPCs try to pass through the same narrow path, they may collide with each other or become stuck.

Mutual exclusion is used to prevent this problem.

In C, mutexes and semaphores are commonly used to implement mutual exclusion.

On the other hand, Verse provides a different execution model that allows us to implement mutual exclusion without using the same mechanisms as C.

In this article, we compare mutual exclusion in C and Verse using source code from our AI Runner implementation in Unreal Editor for Fortnite (UEFN).

You can play with our AI Runners in the following game.

[UEFN] Ninja Random Switch Deathrun 300+ [Island Code: 3505-9013-4036]

What Is Ninja Random Switch Deathrun 300+? Ninja Random Switch Deathrun 300+ is a ninja-themed deathrun experience playable in Fortnite. Its biggest feature is Random Rooms, which change the course layout every time you play. Challenge more than 300 levels, clear the Random Rooms in each DAN, pass the DAN Exam waiting at the end, and work your way through all 10 DAN ranks. The Element system begins with Fire and Water in the Tutorial and DAN 1. As your DAN increases, more Elements are introduced. By DAN 10, you will take on trials using all four Elements: Fire, Water, ...

What Is Mutual Exclusion?

Mutual exclusion is a mechanism that prevents multiple operations from using the same shared resource at the same time.

For example, suppose two NPCs try to enter a narrow path that only one NPC can pass through.

If both NPCs enter the path at the same time, they may collide and become unable to move.

To prevent this problem, one NPC uses the path while the other NPC waits.

This is the basic concept of mutual exclusion.

In this article, we focus on how to implement mutual exclusion in Verse.

Differences Between C and Verse Language

First, C and Verse use different execution models.

In a multithreaded C program, the operating system may switch from one thread to another while a thread is executing.

Therefore, shared data must be protected using synchronization mechanisms such as mutexes.

On the other hand, synchronous operations in Verse execute without being interrupted by other Verse tasks.

This means that we can check and update shared data without allowing another Verse task to run between these operations, as long as no suspension occurs.

However, if a task is suspended using Sleep or another suspending operation, other tasks can execute.

Therefore, we need to consider where suspension may occur when implementing mutual exclusion.

Mutex

A mutex is a synchronization mechanism that allows only one thread to access a protected resource at a time.

Mutex in C Language

In C, we can use pthread_mutex_lock and pthread_mutex_unlock to implement mutual exclusion.

pthread_mutex_lock acquires the mutex, while pthread_mutex_unlock releases it.

While one thread holds the mutex, other threads cannot acquire the same mutex.

Mutual Exclusion in Verse Language

In Verse, we can use synchronous operations without suspension instead of using a C-style mutex.

In our AI Runner implementation, multiple NPCs share information about path reservations.

The following code is part of the TryClaimAIRunnerLaneLease function.

First, HasAIRunnerLaneOccupancyFromState checks whether another NPC has reserved the target Lane.

If the Lane is already reserved by another NPC, the function returns false.

Otherwise, the function updates the NPC's reservation information and returns true.

The important point is that there is no suspending operation such as Sleep between checking and updating the reservation.

Therefore, another Verse task cannot interrupt this sequence of synchronous operations.

This mechanism is similar to pthread_mutex_trylock in C, which attempts to acquire a mutex without waiting.

However, the reservation mechanism in Verse is not an operating-system mutex.

Semaphore

A semaphore is a synchronization mechanism that limits the number of operations that can access a shared resource at the same time.

For example, a semaphore can be used to allow only one NPC to reserve a narrow path.

Semaphore in C Language

In C, we can use sem_wait and sem_post to manage shared resources.

sem_wait acquires a resource, while sem_post releases it.

If no resource is available, sem_wait waits until a resource becomes available.

Semaphore-Like Implementation in Verse Language

In our AI Runner implementation, paths are managed as Lanes.

Only one NPC can reserve a Lane at a time.

This is similar to a semaphore with a capacity of one.

We use functions such as TryClaimBestAIRunnerPendingLaneLease to attempt to reserve a Lane.

The following code is part of the reservation retry process in our AI Runner implementation.

Note: This code is a simplified excerpt from our implementation. The actual implementation also includes NPC state checks and Watchdog management.

First, ArmAIRunnerLaneDemand registers the NPC's request to use a Lane.

Next, TryClaimBestAIRunnerPendingLaneLease attempts to reserve a Lane.

If PendingLane is greater than or equal to zero, the reservation succeeds.

The function then updates the related reservation state and returns true.

On the other hand, if the reservation fails, Sleep(0.10) suspends the current asynchronous task for approximately 0.1 seconds.

After that, the loop attempts to reserve a Lane again.

In this way, our AI Runner implementation combines reservation attempts and Sleep to control access to shared resources.

Unlike sem_wait in C, this implementation does not wait for a direct notification that a resource has been released.

Instead, it periodically checks whether a Lane can be reserved.

Managing Reservations with Leases

Our AI Runner implementation uses a Lease to manage Lane reservations.

A Lease is a reservation with an expiration time.

For example, suppose an NPC reserves a Lane and is then eliminated.

If the reservation remains valid forever, other NPCs may be unable to reserve the Lane.

To prevent this problem, we set an expiration time for each reservation.

This Map stores the expiration time of each NPC's Lane reservation.

The following condition is used to determine whether a reservation is still valid.

If the current time reaches the expiration time, the reservation is treated as invalid.

This prevents outdated reservations from blocking a Lane forever.

We also explicitly release a reservation when it is no longer needed.

By setting the expiration time to zero, the reservation becomes invalid.

This operation has a purpose similar to sem_post in C because it allows other operations to acquire the resource.

However, an expired reservation does not necessarily mean that the NPC has physically left the Lane.

Therefore, we also need to consider the NPC's actual position and movement state.

Read-Write Lock

A Read-Write Lock is a synchronization mechanism that distinguishes between reading and writing shared data.

In C, we can use pthread_rwlock_rdlock and pthread_rwlock_wrlock.

Multiple threads can read shared data at the same time, but writing requires exclusive access.

On the other hand, Verse can manage shared state using synchronous operations without suspension.

Therefore, we can manage shared state differently from how read-write locks work in C.

Our AI Runner implementation separates functions that read Lane reservation information from functions that update reservation information.

However, this is not the same mechanism as a Read-Write Lock in C.

Instead, it uses the execution model of Verse to manage shared state.

Important Notes When Implementing Mutual Exclusion

When implementing mutual exclusion in Verse, pay attention to the following points.

• Suspension: Do not insert Sleep or another suspending operation between checking and updating reservation information.
• Reservation Release: Make sure outdated reservations do not remain valid after NPC elimination or other interruptions.
• Timeout: Prevent NPCs from waiting forever when a Lane cannot be reserved.

Our AI Runner implementation combines Reservation, Lease, Watchdog, and Recovery mechanisms to handle these situations.

These mechanisms help prevent NPCs from becoming stuck due to resource conflicts.

Summary

In this article, we explained mutual exclusion in Verse by comparing it with C.

The main points are:

• In C, mutexes and semaphores are commonly used to implement mutual exclusion.
• In Verse, synchronous operations without suspension can be used to protect shared state from interference by other Verse tasks.
• Our AI Runner implementation uses Reservations to prevent multiple NPCs from reserving the same Lane.
• Reservation attempts and Sleep can be combined to wait until a resource becomes available.
• Leases prevent outdated reservations from remaining valid forever.

C and Verse take different approaches to mutual exclusion.

In particular, checking and updating shared state without suspension is important when implementing mutual exclusion in Verse.

By understanding this mechanism, we can manage shared resources safely when multiple NPCs are running in the same game.

If you would like to play our game developed using Unreal Editor for Fortnite (UEFN), see the following article:

Our Game in Unreal Editor for Fortnite (UEFN) for Fortnite

You can learn from us. We introduce our game in Unreal Editor for Fortnite (UEFN) for Fortnite. Let's come and play our games! If you want to learn UEFN first, please click the following. March 20, 2024: 🌸🥚Spring Easy Deathrun 250+🌸🥚 [Island Code: 7022-3666-7030] 🌸🥚Spring Easy Deathrun 250+🌸🥚 is a spring-themed deathrun (parkour) game. Deathrun is an action game like a 3D version of Super Mario. You can enjoy cherry blossoms and Easter eggs! https://www.youtube.com/watch?v=zPpiu_hDqTo If you'd like to play, copy the following Island Code "7022-3666-7030" and search for it in Fortnite! April 3, 2024: ✒Math Times Table Deathrun 100+✒ ...

References:

• Verse Language Get Started
• Verse: What it is and why we are building it
• Building a game with Verse and Scene Graph