CSCI 4061 Quiz 2

pthread_create signature

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void (start_routine)(void *), void *arg)

pthread_join signature

int pthread_join(pthread_t thread, void **value_ptr)

pthread_cond_wait signature

int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)

sem_init signature

int sem_init(sem_t *sem, int pshared, unsigned int value)

pthread_mutex_lock signature

int pthread_mutex_lock(pthread_mutex_t *mutex)

Static mutex initializer

PTHREAD_MUTEX_INITIALIZER

Static condition variable initializer

PTHREAD_COND_INITIALIZER

sem_init second argument (pshared)

0 = shared within process only; nonzero = shared across processes

pthread return convention

Returns 0 on success, nonzero error code on failure. Does NOT set errno. Never returns EINTR.

Thread

An independent stream of instructions within a process; has its own PC, stack, registers, signal mask; shares address space, globals, heap, file descriptors, code with other threads in the process

Race condition

A situation where program outcome depends on the relative execution order of concurrent threads/processes accessing a shared resource

Critical section

A code segment that requires mutual exclusion; all executions are serialized

Atomic operation

An indivisible operation that either executes completely or not at all, and cannot be interrupted

Mutual exclusion

One-at-a-time access to a resource or code segment; only one thread permitted at a time

Mutex

A binary lock (locked/unlocked) where at most one thread owns it at a time; used for short critical sections

Condition variable

A synchronization primitive that atomically unlocks a mutex and blocks a thread until signaled

Semaphore

A synchronization primitive with an integer value; sem_wait decrements (blocks if would go below 0); sem_post increments

Deadlock

A situation where no thread can make progress because each is waiting on a resource held by another

Multiprogramming vs multithreading

Multiprogramming = multiple processes sharing CPU (disjoint address spaces); multithreading = multiple threads in one process (shared address space)

Joinable vs detached thread

Joinable: holds resources until another thread joins; Detached: releases resources immediately on exit, cannot be joined

Three ways to end thread execution

exit() kills entire process; pthread_exit() kills only calling thread; return from start routine = pthread_exit with return value

Shared between threads in a process

Address space, global variables, heap, open file descriptors, code, data, signal handlers

Private to each thread

Program counter, stack, registers, signal mask, errno (in modern implementations)

Three operations hidden inside counter++

Load counter to register; add 1 to register; store register back to counter

Three steps of a bank withdrawal race

Read balance; modify (subtract); write back — another thread can interleave between any two

Check-then-act race

Two threads both pass a condition check before either acts, both then act based on stale assumption (e.g., both withdraw after seeing sufficient balance)

Four parts of a critical section

Entry section (request); critical section (access); exit section (release); remainder section (concurrent resumes)

Three requirements for correct critical section solution

Mutual exclusion; progress (waiting thread can enter if none inside); fairness (no indefinite postponement)

Coffman condition 1

Mutual exclusion — at least one resource held in non-sharable mode

Coffman condition 2

Hold and wait — thread holds one resource while waiting for another

Coffman condition 3

No preemption — only the holder can release a resource; cannot be forcibly taken

Coffman condition 4

Circular wait — a cycle of threads each waiting for a resource held by the next

Deadlock prevention condition

ALL four Coffman conditions must hold simultaneously; eliminating any one prevents deadlock

Single-lock strategy eliminates

Hold-and-wait AND circular wait (only one lock exists)

Backoff (trylock) strategy eliminates

Hold-and-wait (thread releases everything it holds if it cannot acquire next lock)

Total lock ordering eliminates

Circular wait (fixed global acquisition order makes cycles impossible)

Ostrich algorithm

Ignore deadlocks; handle rare occurrences by rebooting or killing processes; used by most real OSes

Which Coffman conditions are hard to eliminate

Mutual exclusion (inherent to protected resources) and no preemption (forcible lock-stealing would leave data inconsistent)

pthread_cond_signal vs pthread_cond_broadcast

Signal wakes ONE waiting thread; broadcast wakes ALL waiting threads

When to use broadcast over signal

When multiple waiters may need to proceed (barriers, wait groups) or when unsure how many waiters exist

Why while loop around pthread_cond_wait

(1) POSIX allows spurious wakeups; (2) predicate may have become false again between signal and reacquisition of mutex

What pthread_cond_wait does atomically

Releases the mutex AND blocks the thread as one indivisible operation

Bug if unlock and block were separate in cond_wait

Another thread could signal between unlock and block, causing signal to be lost forever

Mutex vs semaphore: ownership

Mutex can only be unlocked by the thread that locked it; semaphore has no ownership — any thread can sem_post

Mutex vs semaphore: counting

Mutex is strictly binary; semaphore can be initialized to any non-negative N (counting semaphore)

Semaphore initialized to 1 acts like

A mutex (binary lock)

Semaphore initialized to 0 is used for

Signaling/ordering — a thread blocks on sem_wait until another thread sem_posts

exit() from any thread

Terminates the entire process; all threads die immediately

pthread_exit() from main thread

Only main thread exits; process continues running until last thread terminates

return from start routine

Equivalent to pthread_exit with the returned pointer as value

pthread_equal vs ==

pthread_t may be a struct on some implementations, so always use pthread_equal to compare thread IDs

pthread_self()

Returns the calling thread's own thread ID

pthread_join(pthread_self(), NULL)

Causes deadlock — thread waits for itself to finish

Never return from a thread

A pointer to an automatic (stack-allocated) local variable — stack is deallocated on thread exit, pointer becomes dangling

Safe return values from a thread

malloc'd memory, static variables, string literals, or memory provided by the creator via the argument

errno in multithreaded programs

Modern implementations make errno a per-thread macro, so each thread has its own effective copy

Thread-unsafe functions (examples)

strerror, rand, ctime, gmtime, localtime, readdir, strtok

Thread-safe function naming convention

_r suffix (e.g., strerror_r, rand_r)

Program 12.9 bug

All threads share &i pointer; by the time threads dereference, i has changed (often all see final loop value)

Fix for shared-pointer-to-loop-variable bug

Give each thread its own storage: per-thread array element, malloc'd struct, or cast scalar directly to void*

pthread_cancel behavior

Asynchronous request; returns immediately; target terminates based on its cancellability state (ENABLE/DISABLE) and type (DEFERRED/ASYNCHRONOUS)

Default cancellation type

Deferred — thread only acts on cancellation at designated cancellation points (certain blocking calls)

Mutex self-deadlock

Locking a mutex already held by the calling thread; POSIX says MAY return EDEADLK but detection not required

Producer-consumer with one cond variable problem

Signal may wake wrong kind of waiter (another producer when consumer needed); broadcast works but wastes CPU

Producer-consumer with two cond variables

'items' signaled when item added (wakes consumers); 'slots' signaled when slot freed (wakes producers)

Busy-waiting inside a held lock

Catastrophic deadlock — lock-holder spins forever, no other thread can acquire lock to change the condition

Why mutex alone insufficient for producer-consumer

Waiting for buffer to become non-empty/non-full can be unbounded in duration; need condition variables or semaphores

Wait group purpose (Lab 9)

Lets one thread block until N other threads complete their work (Go-style synchronization primitive)

Why waitgroup_done uses broadcast

Multiple threads may be waiting on the wait group; signal would only wake one and leave others stuck

Lab 7 key insight

When work partitions cleanly (distinct rows of output), no mutex needed — threads write to disjoint memory

Correct mutex-protected check-and-act pattern

lock → check condition → act if condition holds → unlock (entire sequence under one lock)