Make a Lost Update and a Deadlock by Hand

Goal

Instead of reading about race conditions and deadlocks, you will create them yourself and remove them yourself. After the eight steps, you will have confirmed by hand not that "you just add a lock", but how far to wrap, why the order must be unified, and when it is better not to share at all.

Why it matters

Concurrency bugs do nothing in most runs. So they pass tests and blow up in production. Step 2 of this lab shows that in numbers: if you run the same program five times, you get five different values.

Python has a global interpreter lock, so threads do not truly run at the same time. Even so, updates are lost. This is because the cause of a race condition is not parallel execution but the fact that the read-modify-write section is divided. It is enough for the interpreter merely to switch threads in between. This actually makes the concept clearer.

Deadlock is the same. The only thing that changes between steps 5 and 6 is the order in which locks are taken. You do not add more locks or lengthen the waiting time.

Steps

Reproduce the lost updates with /root/conc/race.py and save them to /root/conc/01-race.txt.
Run the same program five times and save the result of each run to /root/conc/02-repeat.txt.
Remove the loss with a lock in /root/conc/lock.py and save it to /root/conc/03-lock.txt.
Build a way not to share at all in /root/conc/local.py and save it to /root/conc/04-local.txt.
Create a deadlock with /root/conc/deadlock.py reverse and save it to /root/conc/05-deadlock.txt.
Add a same branch to the same program to remove the deadlock and save it to /root/conc/06-order.txt.
Collect the elapsed times of steps 3 and 4 and save them to /root/conc/07-cost.txt.
Summarize what you learned and save it to /root/conc/08-notes.md.

Notes

Put all outputs under /root/conc/. Run mkdir -p /root/conc first.
Set the number of threads to 4 and the number of increments per thread to 50,000. The grader checks against these values.
If you do not see any loss, add sys.setswitchinterval(0.000001). Threads switch more often, and the gap that was already there shows up.
Common mistake 1: writing it as the single line counter += 1. The gap is narrow, so the loss is hard to see. Split the read and the write into two statements.
Common mistake 2: acquiring the second lock without a time limit. The program stops forever and nothing appears on the screen. Use acquire(timeout=2).
Common mistake 3: merging the locks into one in step 6. That makes the deadlock disappear, but it also makes what you were meant to learn disappear. Keep the two locks and change only the order.

Reproduce the lost updates

Create /root/conc/race.py. Have 4 threads each increment the same global variable 50,000 times, writing each increment as the two statements v = counter and counter = v + 1. The program must print two lines, expected 200000 and actual <실제값> (the actual value goes in place of the placeholder), and you save that output to /root/conc/01-race.txt.

Each increment must be split into two statements, a read and a write, so that another thread can cut in between them. If you write it as the single line counter += 1, the gap is narrow and the loss is hard to see.

If you still do not see any loss, make threads switch often with sys.setswitchinterval(0.000001). This does not create the bug; it creates the condition under which a bug that was already there shows itself.

Run the same program five times

Run the program from step 1 five times and save the following to /root/conc/02-repeat.txt: the first line expected 200000, then five lines in the format <회차> <actual 값> (the run number, then the actual value).

Run it with for i in 1 2 3 4 5; do ...; done and write down only the actual value of each run.

The point of this step is that the value is different every time. A race condition is a matter not of existing or not but of showing itself or not, so passing a test ten times out of ten does not mean there is no bug.

Remove the loss with a lock

Create /root/conc/lock.py. Use the same structure as step 1 and remove the loss by adding a threading.Lock. Print three lines, expected 200000, actual <값>, and elapsed <밀리초> (the value and the elapsed milliseconds go in place of the placeholders), and save that output to /root/conc/03-lock.txt.

You must wrap the read and the write together in a with lock: block. If you wrap only the read or only the write, the space between them stays open and the loss remains.

For elapsed, write in milliseconds the time from just before you start the threads to just after all of them have joined. You will use this value in step 7.

A way not to share at all

Create /root/conc/local.py. Each thread counts its own share in a local variable and the results are merged at the end to produce the same result. Do not use locks or semaphores. The output format is the same as in step 3, and you save that output to /root/conc/04-local.txt.

Each thread increments only its own local variable, and when it finishes, puts the result into its own slot in a list, and the main thread adds them up after all have joined. There is no sharing, so there is nothing to protect.

The grader also checks that this file contains no Lock, Semaphore, or Condition. The point of this step is to get the same accuracy without using a lock.

Create a deadlock by taking locks in opposite orders

Create /root/conc/deadlock.py. When it is called with python3 /root/conc/deadlock.py reverse, two threads must take two locks in opposite orders and cause a deadlock. Acquire the second lock with acquire(timeout=2) so that it never stops forever, and print two lines, mode <갈래> (the branch name) and blocked <못 잡은 스레드 수> (the number of threads that failed to acquire the lock). Save that output to /root/conc/05-deadlock.txt.

After taking the first lock, rest briefly with time.sleep(0.05) so that the other thread can also take its own first lock. Without that gap, one side finishes everything first and no deadlock occurs.

If you acquire without a timeout, the program stops forever, because a deadlock does not resolve itself. Setting a time limit is not a way to fix the deadlock but a way to observe that a deadlock has occurred.

Remove the deadlock by unifying the order

In deadlock.py, add a branch named same. Change only so that the two threads take the locks in the same order, and leave everything else as it is. Save the output of python3 /root/conc/deadlock.py same to /root/conc/06-order.txt. The value of blocked must be 0.

Do not remove the locks, do not remove the rest time, and do not lengthen the time limit. Unify only the order in which they are taken. That breaks circular wait, one of the four deadlock conditions.

This is why, in practice, lock order is fixed in a document. If everyone takes them in whatever order is convenient, two paths will eventually cross.

Measure how much the lock charges

Take the elapsed of the step 3 and step 4 programs and save them to /root/conc/07-cost.txt as two lines, lock <밀리초> and local <밀리초> (the milliseconds go in place of the placeholders).

The two programs count the same number the same number of times. The only difference is whether the shared variable is protected by a lock or not shared at all.

Locks are not free. So the practical direction is not to use locks well but to make them unnecessary. Also remember, though, that splitting up the counting is not always possible.

Summarize what blocked what

Write at least three lines in /root/conc/08-notes.md: one sentence each on why the updates were lost, what the lock prevented, and how you removed the deadlock.

The text must contain 임계 (critical), 교착 (deadlock), and 순서 (order).

Above all, write down exactly what you changed between steps 5 and 6. It was neither adding more locks nor lengthening the time limit.