Find, Count and Close the Gaps — Threads, asyncio, SQLite

Goal

You will confirm with bytecode why counter += 1 is not atomic, and build, count, and fix lost updates across threads, double seat booking, an overdraft between awaits in asyncio, and the update loss of two SQLite connections. You will measure the cost of a call that blocks the event loop as "loop lag," and measure how fast threads and processes finish CPU work under the GIL.

Why it matters

A race condition arises in the gap between the value you read and the value you write. With threads, the gap is between bytecode instructions; with asyncio, it is the await; and with a database, it is between SELECT and UPDATE. A fix that wraps only part of the gap in a lock runs without errors while the numbers are wrong, so it is rarely caught in review. So the grader of this lab does not look only at the numbers you wrote; it runs your functions again on inputs that are not the materials and compares them with the reference implementation. Judgments involving time are looked at only within a wide range, because the Pod shares its CPU.

Materials

They are under /opt/fixtures/svccs/concurrency/. Only read them.

params.json    threads·loops(2·3단계) · sqlite_rounds(7단계) · lag_handlers·lag_block_s·lag_tick_s(6단계)
               cpu_n·io_tasks·io_sleep_s(8단계)
bookings.json  좌석 예약 요청 목록 [{"user": "u001", "seat": "A01"}, …] — 같은 좌석 요청이 몰려 온다
accounts.json  {"balances": {계좌: 잔액}, "withdrawals": [{"account": 계좌, "amount": 금액}, …]}

Steps

1. In /root/svccs/concurrency/bytecode.json, write python (for example, the major and minor version such as "3.12"), ops, and atomic. ops is the list of instruction names obtained by disassembling def bump(): global counter; counter += 1 with dis.get_instructions, excluding those that start with RESUME and RETURN, and atomic is whether this increment is atomic across threads (true/false).
2. In /root/svccs/concurrency/conc.py, create unsafe_increment(threads, loops). Each of threads threads raises a shared value loops times, and for each increment it does read → time.sleep(0) → write the value it read + 1, in that order. It returns {"expected": threads×loops, "actual": 최종값, "lost": expected − actual} (actual is the final value). Run it with the threads·loops from params.json, and in /root/svccs/concurrency/lost.json write the result as threads·loops·expected·actual·lost.
3. In the same file, create locked_increment(threads, loops). Do the same read → time.sleep(0) → write as in step 2, but block it with threading.Lock so that lost becomes 0. Do not remove the yield (time.sleep(0)); the grader counts how many times it is called.
4. In the same file, create book(requests, safe). For each request, one thread does check whether the seat is free → time.sleep(0) → record the booking. If safe is true, block it with a lock. It returns {"requests", "seats"(서로 다른 좌석 수), "confirmed"(예약 성공 응답 수), "double_booked"(confirmed − 성공 응답에 나온 서로 다른 좌석 수)} (seats is the number of distinct seats, confirmed is the number of successful booking responses, and double_booked is confirmed minus the number of distinct seats that appear in successful responses). Run it twice with bookings.json (without a lock, and with a lock), and in /root/svccs/concurrency/seats.json write requests·seats·unsafe·safe (unsafe and safe are objects that each hold confirmed and double_booked).
5. In the same file, create run_withdrawals(balances, withdrawals, mode). Start one coroutine per withdrawal with asyncio.gather, in the order of the request list, and each coroutine does check whether balance ≥ amount → await asyncio.sleep(0) → deduct (reject it if the balance is short). If mode is "locked", block it with a per-account asyncio.Lock. It returns {"approved", "rejected", "overdrawn_accounts"(최종 잔액이 음수인 계좌 수), "final"(계좌별 최종 잔액)} (overdrawn_accounts is the number of accounts with a negative final balance, and final is the final balance per account). Run both modes with accounts.json, and in /root/svccs/concurrency/overdraft.json write {"unsafe": …, "locked": …}.
6. In the same file, create async def handler(offload, block_s=0.2) and measure_lag(offload, handlers=3, tick=0.01). If offload is false, handler calls time.sleep(block_s) as is, and if true, it calls it by moving it with asyncio.to_thread. measure_lag measures according to the "Loop lag rule" below. In /root/svccs/concurrency/lag.json, write the two cases as handlers·blocking·offloaded (blocking and offloaded are the objects returned by measure_lag, as they are).
7. In the same file, create sqlite_lost(path, rounds, mode). Use two connections alternately in a single thread, following the "SQLite rule" below. Run the three modes with sqlite_rounds from params.json, and in /root/svccs/concurrency/sqlite.json write rounds·read_modify_write·atomic·deferred_txn.
8. In the same file, create cpu_bound(n) (the sum of i*i % 7 for i from 0 to n−1), gil_compare(n), and io_compare(tasks, sleep_s), and write /root/svccs/concurrency/gil.json following the "GIL rule" below.

Loop lag rule

ticker 작업: 반복해서 due = loop.time() + tick → await asyncio.sleep(tick) → loop.time() − due 를 기록
ticker 를 띄우고 tick×3 만큼 기다린 뒤, handler(offload) 를 handlers 개 gather 한다(걸린 시간 = elapsed_s)
gather 가 끝나면 ticker 를 멈추고 기다린다
돌려줄 것: max_lag_ms(기록 최댓값 × 1000, 소수 첫째 자리) · ticks(기록 개수) · elapsed_s(소수 셋째 자리)

SQLite rule

path 에 새 DB: CREATE TABLE counter (id INTEGER PRIMARY KEY, n INTEGER NOT NULL), 행 (1, 0)
연결 a, b 는 sqlite3.connect(path, timeout=0.05). 라운드마다
  read_modify_write  a 가 n 을 읽고, b 가 n 을 읽고, a 가 (읽은 값+1) 을 쓰고 commit, b 도 같게
  atomic             a 가 UPDATE counter SET n = n + 1 후 commit, b 도 같게
  deferred_txn       a·b 의 isolation_level = None. a: BEGIN·읽기, b: BEGIN·읽기, a: 읽은 값+1 쓰기,
                     b: 읽은 값+1 쓰기 후 COMMIT — OperationalError 면 busy +1 하고 ROLLBACK, 끝으로 a: COMMIT
돌려줄 것: final(최종 n) · expected(2×rounds) · busy · lost(expected − final − busy)

GIL rule

gil_compare(n): cpu_bound(n) 을 한 번 돌려 데운 뒤, cpu_bound(n) 두 번을 순서대로 / 스레드 2개로 /
                ProcessPoolExecutor(max_workers=2) 로 돌린다. 셋 다 벽시계(perf_counter)와 CPU 시간을 함께 잰다
                → cpu_seq_s · cpu_threads_s · cpu_procs_s (벽시계 초)
                → seq_cpu_s · threads_cpu_s (time.process_time 차이 — 이 프로세스 모든 스레드의 CPU 시간)
                → procs_cpu_s (os.times() 의 children_user + children_system 차이 — 끝난 자식 프로세스의 CPU 시간)
                (여섯 값 모두 소수 셋째 자리)
io_compare(tasks, sleep_s): time.sleep(sleep_s) tasks 번을 순서대로 / 스레드 tasks 개로 → io_seq_s · io_threads_s
gil.json: gil_disabled_build(sysconfig.get_config_var("Py_GIL_DISABLED") 를 bool 로), 위 여덟 값,
          thread_speedup = cpu_seq_s ÷ cpu_threads_s, proc_speedup = cpu_seq_s ÷ cpu_procs_s,
          io_thread_speedup = io_seq_s ÷ io_threads_s,
          thread_cores = threads_cpu_s ÷ cpu_threads_s, proc_cores = procs_cpu_s ÷ cpu_procs_s
          (다섯 비율 모두 소수 둘째 자리 — cores 는 '그동안 평균 몇 개의 코어가 일했나' 입니다)
          lost_updates_with_gil = lost.json 의 lost

Notes

• The grader imports conc.py. Put code that produces the result JSON under if __name__ == "__main__": or in a separate script.
• The loss count in thread races differs every time, because the operating system decides the order. The grader checks whether the fixed side is exactly 0 and the unfixed side is greater than 0. The asyncio and SQLite numbers are the same every time.
• Common mistakes: wrapping only the write in a lock, wrapping only the check in a lock and doing the action outside, awaiting while holding a threading.Lock inside a coroutine (the loop stops), and writing that you moved it with to_thread while leaving time.sleep as it is.
• The outputs disappear when the session ends. Keep them elsewhere if you need them.

How many instructions is counter += 1

Disassemble counter += 1 with dis, and write the list of instruction names and the judgment about atomicity to /root/svccs/concurrency/bytecode.json as python, ops, and atomic.

dis.get_instructions(function) returns the instructions one by one, and the opname of each instruction is its name. If the read (LOAD_) and the write (STORE_) are different instructions, think about what that tells you when combined with the fact that the GIL guarantees only one instruction at a time.

Lose updates with threads

Create unsafe_increment(threads, loops) in conc.py, run it with the threads and loops from params.json, and write threads, loops, expected, actual, and lost to /root/svccs/concurrency/lost.json. The grader also calls the function with other thread counts and iteration counts.

Keep the shared value in a global or a dict, and have each thread repeat v = value → time.sleep(0) → value = v + 1. sleep(0) releases the GIL, creating a gap in which another thread can read the same value. expected is threads × loops.

Block the whole gap with a lock

Create locked_increment(threads, loops) in conc.py. Keep read → time.sleep(0) → write as is, and make lost 0 with threading.Lock. The grader calls it with several thread counts and also counts how many times time.sleep is called.

What the lock has to wrap is the whole point of this step. If you wrap only the write line, the value you already read is stale while waiting for the lock, and they overwrite one another in turn. Treat everything from the read to the write as one block.

Double seat booking: check-then-act

Create book(requests, safe) in conc.py, run it with bookings.json without a lock and with a lock, and write requests, seats, unsafe, and safe to /root/svccs/concurrency/seats.json. The grader also calls it with other request lists.

If another thread checks the same seat between "is it free?" and "reserve," both get a success response. If you put only the check inside the lock and leave the recording outside, the gap stays. If you collect the seats in the list of successful responses, you can count double_booked (list.append is an operation that the FAQ says is atomic).

An overdraft between awaits

Create run_withdrawals(balances, withdrawals, mode) in conc.py, run unsafe and locked with accounts.json, and write them to /root/svccs/concurrency/overdraft.json. The grader calls both modes with other account and withdrawal lists and compares them exactly with the reference implementation.

asyncio has one thread, but at an await the turn passes to another coroutine. If there is an await between the check and the deduction, another withdrawal from the same account sees the same balance in the meantime. For the lock, use asyncio.Lock with async with, one per account, and wrap from the check through the deduction. If you await while holding a threading.Lock in a coroutine, the loop stops.

One blocking call stalls everyone

Create handler(offload, block_s=0.2) and measure_lag(offload, handlers=3, tick=0.01) in conc.py, and write the two cases to /root/svccs/concurrency/lag.json as handlers, blocking, and offloaded. The grader measures your handler again with its own measuring tool.

While time.sleep runs, the loop thread cannot wake any other task. If you gather three handlers, the three block one after another within the same loop turn, so the delays add up. Even when you move it with to_thread, the work itself still has to be done, so elapsed_s does not become 0.

Two SQLite connections: a silent loss and a loud failure

Create sqlite_lost(path, rounds, mode) in conc.py following the SQLite rule, run the three modes with sqlite_rounds, and write rounds, read_modify_write, atomic, and deferred_txn to /root/svccs/concurrency/sqlite.json. The grader calls the three modes with other round counts.

Python's sqlite3, under its default settings, opens a transaction only before UPDATE, so a value read with SELECT is not protected. UPDATE ... SET n = n + 1 is one statement for the read and the write. If two connections that did BEGIN themselves both read and then try to write, one of them cannot be upgraded to a write and gets "database is locked."

The GIL: it does not get faster, and it is not safe either

Create cpu_bound, gil_compare, and io_compare in conc.py, and write /root/svccs/concurrency/gil.json following the GIL rule. lost_updates_with_gil is the lost from lost.json in step 2. The grader calls io_compare directly and checks the value of cpu_bound.

A function that uses only the CPU almost never releases the GIL, so two threads run one after the other. A process has its own interpreter, so it has its own GIL. Wall-clock time wobbles when the neighboring Pod is busy, but "CPU time ÷ wall-clock time" is how many cores worked on average in the meantime, so the trace of the GIL is clearer. time.sleep releases the GIL while waiting, so threads overlap.