Examples
Solaris
- 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
Windows XP
- 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)
Linux
- 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
- Pthreads API is OS-independent
- Pthreads provides:
- mutex locks
- condition variables
- Non-protable extensions include:
- read-write locks
- spinlocks
Atomic Transactions
- System Model
- Log-based Recovery
- Checkpoints
- Concurrent Atomic Transactions
System Model
- 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-Based Recovery
- 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)
- Using the log, system can handle any volatile memory errors
Checkpoints
- 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
Concurrent Transaction
- Serialazability
- Could perform all transactions in critical section (Inefficient, too restrictive)
- Concurrency-control algorithms provide serializability
Locking Protocol
- Locks
- Shared
- Exclusive
Two-phase Locking Protocol
Each transaction issues lock and unlock requests in two phases
- Growing
- Shrinking
Timestamp-based Protocols
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
近期评论