cse process synchronization review

• Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing
• Uses adaptive mutexes for efficiency when protecting data from short code segments
  • Starts as a standard semaphore spin-lock
  • If lock held, and by a thread running on another CPU, spins
  • If lock held by non-run-state thread, block and sleep waiting for signal of lock being released
• Uses condition variables
• Uses readers-writers locks when longer sections of code need access to data
• Uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or reader-writer lock
  • Turnstiles are per-lock-holding-thread, not per-object
• Priority-inheritance per-turnstile gives the running thread the highest
  of the priorities of the threads in its turnstile

• Uses interrupt masks to protect access to global resources on uniprocessor systems
• Uses spinlocks on multiprocessor systems
  • Spinlocking-thread will never be preempted
• Also provides dispatcher objects user-land which may act mutexes, semaphores, events, and timers
  • Events - An event acts much like a condition variable
  • Timers notify one or more thread when time expired
  • Dispatcher objects either signaled-state (object available) or non-signaled state (thread will block)

• Prior to kernel Version 2.6, disables interrupts to implement short critical sections
• Version 2.6 and later, fully preemptive
• Linux provides:
  • semaphores
  • spinlocks
  • reader-writer versions of both
• On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption

• Pthreads API is OS-independent
• Pthreads provides:
  • mutex locks
  • condition variables
• Non-protable extensions include:
  • read-write locks
  • spinlocks

• System Model
• Log-based Recovery
• Checkpoints
• Concurrent Atomic Transactions

• Assures that operations happen as a single logical unit of work, in its entirety, or not at all
• Related to field of database systems
• Challenge is assuring atomicity despite computer system failures
• Transaction - collection of instructions or operations that performs single logical function
  • Here we are concerned with changes to stable storage – disk
  • Transaction is series of read and write operations
  • Terminated by commit (transaction successful) or abort (transaction failed) operation
  • Aborted transaction must be rolled back to undo any changes it performed
• Types of Storage Media
  • Volatile storage: main memory, cache
  • Nonvolatile storage: disk and tape
  • Stable storage: not actually possible

• Log on stable storage, each log record describes single transaction write operation, including
  • Transaction name
  • Data item name
  • Old value
  • New value
• Ti starts writtTi commits> written when Ti commitsen to log when transaction Ti starts
• Ti commits written when Ti commits
• Algorithm
  • Using the log, system can handle any volatile memory errors
    • Undo(Ti) restores value of all data updated by Ti
    • Redo(Ti) sets values of all data in transaction Ti to new values
  • Undo(Ti) and Redo(Ti) must be idempotent
  • If system fails, restore state of all updated data via log
    • If log contains Ti starts without Ti commits, undo(Ti)
    • If log contains Ti starts and Ti commits, redo(Ti)

• Checkpoint scheme:
  • Output all log records currently in volatile storage to stable storage
  • Output all modified data from volatile to stable storage
  • Output a log record checkpoint to the log on stable storage

• Serialazability
• Could perform all transactions in critical section (Inefficient, too restrictive)
• Concurrency-control algorithms provide serializability

• Locks
  • Shared
  • Exclusive

Each transaction issues lock and unlock requests in two phases

• Growing
• Shrinking

Transaction Ti associated with timestamp TS(Ti) before Ti starts

• TS(Ti) < TS(Tj) if Ti entered system before Tj
• TS can be generated from system clock or as logical counter incremented at each entry of transaction

Timestamps determine serializability order

• If TS(Ti) < TS(Tj), system must ensure produced schedule equivalent to serial schedule where Ti appears before Tj

Data item Q gets two timestamps

• W-timestamp(Q) – largest timestamp of any transaction that executed write(Q) successfully
• R-timestamp(Q) – largest timestamp of successful read(Q)
• Updated whenever read(Q) or write(Q) executed