CS-3310 - 02 Processes - Concurrency

thread

like a process with shared memory and resources

How does the OS keep track of threads?

thread control block

Threads have individual (or thread-local) ____

stacks

Transforming a single-threaded program into a program that does work on multiple CPUs

parallelization

Why parallelization?

avoid blocking from I/O

Processes across programs

multiprocessing

Because of the unpredictability of the scheduler, the result of a multithreaded program is

non-deterministic

Non-deterministic output is due to

race conditions

Race condition (or data race)

multiple threads updating the same data

Portion of code that accesses a shared resources

critical section

Preventing other threads from executing the same section of code as the current one

mutual exclusion

Instruction that runs completely, or not at all

atomic instruction

Indeterminate program

involves at least one race condition

Allows critical sections to be run atomically

lock

Lock states

free, held

Thread that has acquired a lock

owner thread

Single lock for all critical sections

coarse-grained

Multiple locks for different data

fine-grained

Requirements for solution to the critical section problem

mutual exclusion, progress, bounded waiting

Spin-wait

do nothing until a condition is met

Simple hardware support for spin lock

test-and-set/atomic exchange

test-and-set

atomically get value from pointer and set memory location to new value

Spin lock requires a ____ scheduler

preemptive

Different simple primitive instruction - more flexible, compares with expected value

compare-and-exchange

compare-and-exchange

test if value is expected; if so, update to new value

yield

moves caller from running to ready

True/false: a while loop is still necessary with yield

true

Linux fast locking mechanism

futex

Two-phase lock phases

spin, sleep if unsuccessful

Condition variable

queue for threads waiting on some condition

How are threads woken from waiting on a condition variable?

another thread signaling

Always use a ____ variable when using a condition variable

state

One or more producer threads and one or more consumer threads with a shared buffer

bounded buffer problem

Always use ____ ____ with condition variables to recheck the condition every time a signal happens

while loops

Integer value with down and up routines

semaphore

Semaphore down routine

sem_wait

Semaphore up routine

sem_post

sem_wait

decrement then block if negative

sem_post

increment then wake a sleeping thread

Binary semaphore

semaphore used as a lock

Language construct supported by the compiler that provides mutual exclusion

monitor

Java monitor keyword

synchronized

Design issues with message passing

message loss, process naming, authentication

Mailbox

data structure that buffers messages

Message passing strategy with no message buffer

rendezvous

Synchronization method for groups of processes where all processes finish phase before any move on

barrier

Common barrier application

matrix operations

IPC

inter-process communication