Lab 13 | NPRG038

Part 1: `Monitor.Enter`/`Monitor.Exit` and `lock()`

First, as a reminder, what is the difference between the two snippets? Solution

// Snippet 1
Monitor.Enter(obj);
f();
Monitor.Exit(obj);

// Snippet 2
lock (obj) {
    f();
}

Now, are there any scenarios where Snippet 1 is a better option than Snippet 2? Solution

Part 2: Thread-safety

Consider the following code:

var array = new double[360];
Parallel.For(0, array.Length, i =>
{
    array[i] = Math.Sin(i / 360.0 * Math.PI);
    Console.WriteLine($"Processing {i}.");
});

Is it thread-safe? Are there any data races? Answer

It is important to always assume a type is not thread-safe unless the documentation states otherwise.

Part 3: Counting data-races

Consider the following code (explanation below):

var semaphore = new SemaphoreSlim(0, 2);
var counter = 0;
var iterations = 10_000;
var writer = new StreamWriter("log");

try {
    var t1 = new Thread(() => {
        semaphore.Wait();
        Test();
        semaphore.Release();
    });
    t1.Start();

    var t2 = new Thread(() => {
        semaphore.Wait();
        Test();
        semaphore.Release();
    });
    t2.Start();

    Thread.Sleep(500);

    semaphore.Release(2);

    Thread.Sleep(500);

    semaphore.Wait();
    semaphore.Wait();
} catch (Exception ex) {
    Console.WriteLine($"Exception caught in Main: {ex}");
}

Console.WriteLine($"Expected == {iterations * 2}, Actual == {counter} ...");

void Test() {
    for (int i = 0; i < iterations; ++i)
        counter++;
}

The code inherently starts two threads that run in parallel and increment a shared variable without any means of data race prevention. The semaphore is there to try to ensure that the threads run as much in parallel as possible. Without the synchronization, it is very possible that t1 would finish all iterations before t2 is even instantiated (creating an OS thread is an expensive operation).

Try to think about the following questions (try to run the code yourself):

Will the output be Actual == 20000? Solution
Will the output be at least 10000? Solution
What is the smallest possible value of counter? Solution

Now imagine that we detected a bug in our application (we expect a variable to be 20000, but it’s less than that). The first step in debugging is adding debugging output. Try the same program with the function Test being replaced with the following:

void Test() {
    for (int i = 0; i < iterations; ++i) {
        Console.WriteLine($"Thread {Environment.CurrentManagedThreadId}: counter == {counter}");
        counter++;
    }
}

Try running the program a few times. Why did the behavior change? How did we fix the bug? Answer

Let’s inspect what happens if we replace Console logging with file logging (StreamWriter).

void Test()
{
    for (int i = 0; i < iterations; ++i)
    {
        writer.WriteLine($"Thread {Environment.CurrentManagedThreadId}: counter == {counter}");
        counter++;
    }
}

Again, try running this yourself first. Answer

Part 4: WebAPI

If you recall Part Two of homework assignment 08-WebAPI, we manually implemented routing in a web server:

The user implements ISimplisticRoutesHandler and registers routes via RouteMap.Map(string path, Delegate method).
Using reflection, we instantiate all implementations of ISimplisticRoutesHandler and call their RegisterRoutes method with our RouteMap instance.
When a request arrives, we parse the query and try to find the appropriate Delegate to call, possibly passing arguments to the function.

This is actually something that .NET can do for us. If you recall, we used the ConsoleApp template and manually changed the framework to include ASP.NET, which contains the Kestrel web server (WebApplication).

When creating a project, we can use the ASP.NET Core Web API template. The template can be further configured. We are interested in the following two points:

☒ Enable OpenAPI support — this automatically prepares an OpenAPI specification (json) that we can use to display the documentation.
☐ Use controllers — we want to use MinimalAPI instead of Controllers.

Note that the template changed in .NET 9 (Brief explanation of changes).

Let’s assume we would like to create a Web API application that does the following:

Queries another WebAPI for data
Transforms the data
Returns the data

For the sake of demonstration, let’s query the CoinBase service, retrieve exchange rates from EUR/GBP/USD to CZK, and calculate their average (however useless such a value may be). Here is a starting project. It exposes one route (rates/average) that is served by GetAverageRate. The Swagger documentation is at http://localhost:5290/swagger (for simplicity, the app only listens on HTTP).

Now, this application, as is, is data-race free. Although not everything is truly immutable, we don’t modify any data, and all things we use (i.e. HttpClient, WebApplication) are declared thread-safe. Now let’s add some more endpoints (HTTP Post /rates that adds a new currency, and HTTP Delete /rates/{currency} that removes a specific currency).

Is the application data-race free? (Answer).

Now the application is working correctly, but it is not ideal. When one thread holds the lock and another tries to acquire the same lock, the thread will passively wait until the lock is available. In the case of our application, that might take a very long time. Note that the CPU clock timer is on the order of nanoseconds (GHz), but network communication is on the order of tens of milliseconds. From the perspective of the CPU, the lock is being held for ages. While we normally do not mind this (as the thread waits passively), the web server thread is part of a thread pool. We now face a problem referred to as thread-pool starvation. The web server has to spawn more threads to the thread pool in order for requests to be processed. We might end up in a situation where we have hundreds of threads passively waiting in the thread pool.

We can solve this via Tasks, ContinueWith, or via async-await:

async Task<decimal> GetAverageRateAsync(List<string> currencies) {
    decimal sum = 0;
    lock (currencies) {
        foreach (var currency in currencies) {
            var json = await gHttpClient.GetStringAsync($"https://api.coinbase.com/v2/exchange-rates?currency={currency}");
            sum += ParsePrice(json);
        }
    }

    var avg = sum / currencies.Count;
    return avg;
}

This code won’t compile. Why? Hint, Answer.

Semaphores, on the other hand (SemaphoreSlim), work differently, and we can make use of that. Note that this solution purposefully contains a bug that occurs quite often when migrating between different synchronization primitives. Answer.

While our solution is functional again, we haven’t resolved thread starvation, as SemaphoreSlim.Wait is still a blocking operation (the thread will passively wait for the semaphore to become available).

If you are familiar with homework assignment 12-AsyncSemaphore, you know exactly how to resolve this. We will make use of the WaitAsync method from SemaphoreSlim, illustrated here.

This does solve the problem with thread-pool starvation, but processing requests is still slow. The inherent problem is that while we iterate over the shared list, it could be modified as a result of a different request. What if we don’t iterate over the shared list but rather make a copy of it? While making a copy of data sounds like it wastes memory and time, in our case it is quite beneficial. The list contains a few elements that can be copied in no time (recall how long it takes to wait for a third-party Web API to answer our requests). Code.

Note that we went back to using Monitors, as we now know they are held for only short amounts of time, so there is no thread pool starvation.

If we wanted to improve our solution even further, we could take advantage of the fact that the CoinBase API can probably handle multiple requests simultaneously. So instead of sending a query, waiting for a response, sending another one, etc., we can send all of them at once and then wait for the responses.

async Task<decimal> GetAverageRateAsync(List<string> currencies) {
    List<string> copy;
    lock (gCurrencies)
        copy = [..currencies];

    var tasks = new List<Task<decimal>>();
    foreach (var currency in copy) {
        var task = gHttpClient.GetStringAsync($"https://api.coinbase.com/v2/exchange-rates?currency={currency}")
                .ContinueWith(t => ParsePrice(t.Result));
        tasks.Add(task);
    }

    var results = await Task.WhenAll(tasks);
    var avg = results.Sum() / copy.Count;

    return avg;
}

The lock(obj) f() statement is actually syntactic sugar for the following:

Monitor.Enter(obj);
try {
    f();
} finally {
    Monitor.Exit(obj);
}

The reason is that if the execution of f() throws an exception, we want the lock associated with obj to be released, to prevent possible deadlocks.

The following does compile:

async Task<decimal> GetAverageRateAsync(List<string> currencies) {
    decimal sum = 0;
    Monitor.Enter(currencies);
    foreach (var currency in currencies) {
        var json = await gHttpClient.GetStringAsync($"https://api.coinbase.com/v2/exchange-rates?currency={currency}");
        sum += ParsePrice(json);
    }
    Monitor.Exit(currencies);

    var avg = sum / currencies.Count;
    return avg;
}

but will likely throw a SynchronizationLockException.

We forgot to migrate the Monitor to SemaphoreSlim for the /rates/{currency} endpoint:

app.MapDelete("/rates/{currency}", (string currency) =>
{
    gSemaphoreSlim.Wait();
        gCurrencies.Remove(currency);
    gSemaphoreSlim.Release();
}).WithOpenApi();

If no exception happens, there is no difference. If an exception is thrown, then we have the following options:

In Snippet 1, obj is left in a locked state and some other thread will be waiting for obj indefinitely → Deadlock
In Snippet 2, obj is unlocked and some other thread can enter the critical section protected by obj → No deadlock

This seems like Snippet 2 is better, as there is no deadlock. But why did we even put the lock there in the first place? There are scenarios where we just need to make sure that the critical section is executed atomically (at least when observed from other threads). Imagine the following thread-safe implementation of a dictionary where we can index via either key or value:

class BidirectionalDictionary<TKey, TValue> {
    private Dictionary<TKey, TValue> _byKey = new();
    private Dictionary<TValue, TKey> _byValue = new();
    private object _lock = new();

    public void Add(TKey key, TValue value) {
        lock (_lock)
        {
            _byKey.Add(key, value);
            _byValue.Add(value, key);
        }
    }
}

This implementation contains a bug (Dictionary.Add throws if the key is already present).

Now, is it better for the application to halt (deadlock from Snippet 1) or for the application to continue functioning with inconsistent data?

Maybe, but very unlikely. counter is a variable shared by two threads, and both of them modify it → data race.

As a reminder, counter++ is actually register = counter; register = register + 1; counter = register. Therefore, the following sequence of operations is possible:

T1	T2
`reg = 0 reg = reg + 1 counter = 1`	`\| \| \| reg = 0 \| reg = reg + 1 \| counter = 1 \|`

We will lose some of the writes.

Consider the following sequence of operations:

T1 T2

T1	T2
`reg = 0 // Iteration 1 reg = reg + 1 // Iteration 1 counter = 1 // Iteration 1 ... // Iteration 2 - 9998 reg = 9998 // Iteration 9999 reg = reg + 1 // Iteration 9999 counter = 9999 // Iteration 9999 reg = 1 // Iteration 10000 reg = reg + 1 // Iteration 10000 counter = 2 // Iteration 10000`	`\| reg = 0 // Iteration 1 \| reg = reg + 1 // Iteration 1 \| \| \| \| \| \| \| \| counter = 1 // Iteration 1 \| \| \| reg = 1 // Iteration 2 \| reg = reg + 1 // Iteration 2 \| counter = 2 // Iteration 2 \| ... // Iteration 3 - 9999 \| reg = 9999 // Iteration 10000 \| reg = reg + 1 // Iteration 10000 \| counter = 10000 // Iteration 10000 \|`



reg = 0        // Iteration 1
reg = reg + 1  // Iteration 1
counter = 1    // Iteration 1
...            // Iteration 2 - 9998
reg = 9998     // Iteration 9999
reg = reg + 1  // Iteration 9999
counter = 9999 // Iteration 9999

reg = 1        // Iteration 10000
reg = reg + 1  // Iteration 10000







counter = 2    // Iteration 10000

| reg = 0          // Iteration 1
| reg = reg + 1    // Iteration 1
|
|
|
|
|
|
|
| counter = 1      // Iteration 1
|
|
| reg = 1          // Iteration 2
| reg = reg + 1    // Iteration 2
| counter = 2      // Iteration 2
| ...              // Iteration 3 - 9999
| reg = 9999       // Iteration 10000
| reg = reg + 1    // Iteration 10000
| counter = 10000  // Iteration 10000
|

An important piece of information is that the program still contains the same data-race, but the chances of it occurring were drastically reduced. As we know, Console.WriteLine is (internally) synchronized. This means that the sequence of operations in each iteration changed from

reg = counter
reg = reg + 1
counter = reg

lock
reg1 = counter
reg2 = thread_id
concatenate strings
call OS API
wait for data to be written
unlock
reg = counter
reg = reg + 1
counter = reg

For the bug to manifest, the OS scheduler would have to reschedule the threads right after the unlock statement. The incrementation of the counter variable is a few instructions, while Console.WriteLine is thousands of instructions if we acquire the lock and way more if we don’t.

This can be very frustrating because logging present in debug builds for testing basically prevents a bug from manifesting—a bug that happens every single time in production builds.

First, it is imperative to understand that StreamWriter (or rather the underlying FileStream) is not thread-safe, mostly due to performance reasons. We also know that due to performance reasons, writing data to physical disk is buffered (likely on several layers). Therefore, we are once again in a situation where two threads modify the same memory location → data-race. What we will see is likely some unhandled exception (could be IndexOutOfRangeException, ArgumentOutOfRangeException, or OverflowException).

Let’s also take a look at the file that was created. It may look normal for a while, but there might also be parts like these:

Thread 5: counter == 623
Thread 5: counter == 624
== 584
Thread 5: coun
Thread 5: counter == 626

Thread 5: counter == 628
Thread 5: counter == 629
Thread 5: counter == 630
== 589
Thread 5: coun
Thread 5: counter == 631
r == 591
Thread 5: co
Thread 4: counter == 633

Thread 5: counter == 635
Thread 4: counter == 635

Apparently, two threads were modifying the same file at the same time (before it crashed).

What is also interesting is why the program crashes if it’s enclosed in a try-catch block? Answer

Part 1: Monitor.Enter/Monitor.Exit and lock()

Part 2: Thread-safety

Part 3: Counting data-races

Part 4: WebAPI

Part 1: `Monitor.Enter`/`Monitor.Exit` and `lock()`