ECE344 Fall 2026 (Sec 1) Lec 20 - Parallelization Example
Watch on YouTube →
Overview
Jon Eyolfson uses a bank simulation with 10 million transfers and eight pthreads to show why parallelization requires more than dividing work: shared random-number generation can serialize threads, and unsynchronized account balances create data races. The example develops per-account mutexes, explains transaction-level locking and deadlocks, then uses try-lock retries or consistent account-ID lock ordering to coordinate transfers safely; Eyolfson also reviews likely Test 2 topics.
Key takeaways
- Dividing 10 million transfers among eight pthreads is necessary but does not ensure an eightfold speedup: shared rand() state can serialize threads through internal synchronization.
- rand_r() avoids shared RNG state when each thread supplies a private seed, but it does not protect shared account balances from concurrent reads and writes.
- Correct bank transfers require holding both account mutexes across the debit and credit so concurrent operations observe a complete transaction rather than a half-finished transfer.
- Deadlock can be prevented either by releasing the first mutex and retrying with pthread_mutex_trylock(), or by always acquiring the lower account ID before the higher one.
- A transfer whose source and destination are the same account can self-deadlock when it tries to lock the same mutex twice, so the operation should be skipped.
- A race may disappear in tests with many accounts because collisions become less likely; passing a run is not evidence that concurrent balance updates are safe.
Chapters
- The simulation initializes accounts with unique IDs and a $1,000 starting balance, then performs 10 million transfers of 10% of an account's current balance.
- The transfer loop chooses random source and destination accounts; a final balance tally checks that the bank's total funds are conserved.
- The serial baseline takes about 10 seconds, providing a reference point for evaluating an eight-thread implementation.
- Creating eight pthreads is not enough: each thread must handle one eighth of the 10 million transfers, or the program accidentally performs 80 million.
- After partitioning, the run is far slower than the hoped-for eightfold speedup, and the account totals are incorrect.
- Eyolfson identifies thread-safe rand() as a likely bottleneck because its shared pseudorandom state may require internal locking, making random-number generation effectively serial.
- Replacing rand() with rand_r() gives each thread its own unsigned-int seed, initialized from its thread ID, avoiding shared random-number state.
- The program then runs faster but still loses money because concurrent transfers can read and write the same account balance without synchronization.
- A run with many accounts may appear correct because account collisions are less likely, but a successful test does not prove the balance code is free of data races.
- Eyolfson adds a pthread mutex to each account and initializes it alongside the account data.
- A transfer must hold both the source and destination mutexes across the debit and credit, protecting the operation as one transaction rather than locking each balance update separately.
- Locking accounts in source-then-destination order can deadlock when two threads transfer in opposite directions, such as A to B and B to A.
- The retry strategy locks the source account, attempts to acquire the destination with pthread_mutex_trylock(), and releases the first lock before yielding and retrying if the second is unavailable.
- Releasing the held mutex before yielding breaks the hold-and-wait condition that can cause deadlock.
- A transfer from an account to itself must be skipped: otherwise the thread locks the same non-recursive mutex twice and can retry forever.
- A second deadlock solution orders the two mutexes by account ID and always locks the lower-ID account first.
- Both threads transferring between the same pair of accounts therefore acquire locks in the same order, preventing circular wait without using trylock().
- The code unlocks both mutexes after the transfer; Eyolfson notes that reverse-order unlocking is conventional but not required for correctness.
- Test 2 covers material through Lecture 20 and is expected to be shorter than Test 1, with less wordy multiple choice and some fill-in-the-blank questions.
- Eyolfson recommends past 353 and 444 finals for practice, especially questions labeled synchronization, locking, or threads; the test may include an approximately 11-to-14-mark problem in this area.
- Other expected topics include Lab 3, virtual memory with multi-level page tables, scheduling, and processes; Lab 4 is excluded because students have not completed it.
Transcript excerpt
1:59 Mhm. >> Alrighty, welcome back to operating
3:08 systems. Today, lots of slides to get through. So, let's go for it. So, we are running a bank. Joy, this is the setup for it. We're going to do 10 million transfers. So, we have a simulation or I have a simulation that can create a varying number of accounts given by a command line argument. Each account has a unique ID associated with it and a balance. And the balance starts at $8,000. We are going to generate transfers between two random accounts where each one transfers 10% of its current balance to the other. And in order to make the numbers fun when I actually run it, They must call this securely connect to bank function
3:54 before starting their transfer. That's it. That's the whole slides. So, the rest of it is coding example. It's going to be fun. We're going to run a giant bank and you are going to run it, not me, cuz you're going to run you're going to tell me what to write. I am just I'm just the conduit. So, this is the setup. So, we have a few defines here starting balance of $1,000 or 10 transfers. We are going to write this using eight threads. So, ideally, if we want to get our promotion and not get fired, uh we want to go eight times faster. So, here is our struct for an account. It has an ID associated with it and then a balance. Then, I have an array of accounts here and a variable for the number of
4:43 accounts, since it's just an array. And then I have the securely connect to bank function, which I'm not going to show you. Then, there's this transfer function. So, this takes two accounts, an account
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Jon Eyolfson.