Lecture Notes for Operating Systems Concepts

11 June 2002 - Process Synchronization

1. process interaction

   1. the basics

      1. serial vs concurrent execution

      2. serial software is inefficient and can get complicated to design

      3. cheap and plentiful multi-processor systems and networked computers

      4. big-piece concurrency can be easier and more efficient than one-piece serial software - no concepts, not well supported, no standards

      5. coordinated and uncoordinated concurrency - sharing vs protection

   2. interaction styles

      1. shared data - the fundamental style; independent reading and writing

         1. the dining philosophers problem

      2. producer-consumer - a common style with one-way data movement

      3. readers-writers - a common special case

      4. pure synchronization - the sleeping barber problem

2. process coordination - in space or time

   1. in time - activities occurring in the proper order

   2. in space - unmediated access to shared resources

   3. fork-join concurrency - for coordination in time

      1. synchronization at the atomic process level

   4. critical sections - for coordination in space

      1. guaranteed exclusive access - mutual exclusion

      2. no sharing, no problem

3. semaphores - a bowl with a stone in it

   1. principles

      1. no advance without the stone

      2. no fighting over the stone - one process gets it cleanly

      3. how waiters wait - cpu intensive or not

      4. how waiters go for the stone

   2. implementation

      1. busy wait - ok for multiprocessors, bad for uniprocessors

      2. block - good for uniprocessors; context switches

      3. implementing atomicity - interrupts, atomic instructions, software solutions

      4. handing off vs context switching

   3. use

      1. mutex semaphores - binary semaphores providing mutual exclusion

      2. counting semaphores - many stones in the bowl; manage reusable resources

      3. semaphores can serve as the basis for other synchronization mechanisms - monitors

   4. comments

      1. semaphores are simple but primitive - difficult to manage many of them

      2. semaphore signals don't disappear

      3. there are as many semaphore semantics as there are semaphores

4. shared-memory multiprocessors

This page last modified on 25 June 2002.