Lecture Notes for Operating Systems Concepts

7 October 2004 - Concurrent Coordination

Concurrent Computations

• A concurrent computation is

  • a set of executing processes

  • coordinating to solve a problem.

• Both concurrency and coordination are necessary.

• What is this thing called "coordination"?

Coordination

• Process are control + data.

• Concurrency is processes executing at the same time.

• Coordination is processes accessing the same data.

  • Coordination is data sharing among processes (or threads).

  • Coordination also has a control (or execution) sharing part too.

Data Sharing

• Data sharing takes two forms:

  1. Data shared between threads in the same process.

     • Called intra-process or thread-based data sharing.

  2. Data shared between different processes.

     • Called inter-process or process-based data sharing.

• These are not mutually exclusive.

Thread-Based Data Sharing

• Intra-process data sharing is simple and cheap.

  • The threads already share process resources.

  • No protection boundries need to be crossed.

• The lack of protection boundries makes it easier to corrupt data too.

Thread Sharing Mechanisms

• The main intra-process data sharing mechanism is global variables.

  • Each thread acts as a procedure accessing global data.

• Other mechanisms exist, but reduce to some form of global-memory access.

Process-Based Data Sharing

• Inter-process data sharing is unsimple and expensive.

  • It's the process protection boundry that makes it so.

• However, strong protection makes for better reliability.

• Intra-process data sharing takes two forms: true sharing and communication-based sharing.

True Inter-Process Sharing

• True sharing provides global-like access among processes.

  • It relies on memory-map games.

  

• This acts like thread-based sharing.

Communication-Based Sharing

• Communication-based sharing does not share data.

  • It communicates data between processes.

• It's called inter-process communication or IPC.

OS Support for Sharing

• IPC goes through the OS via system calls.

• The OS may provide

  • space within the kernel for sharing, or

  • allow sharing via storage outside the kernel.

• Sharing within the kernel is fast but limited.

  • Fewer and simpler system calls.

  • Kernel storage is (usually) at a premium.

OS-Resident Sharing

• The kernel provides storage and system calls.

  • Storage may be global or per-process.

  • The system calls do manageent: read, write, allocate, free, ...

• Examples include slots (the assignment), message queues (Unix SysV and Windows) and mailboxes.

OS-External Sharing

• General purpose OS facilities that be used for IPC.

• Examples include file systems, pipes (Unix), and general networking protocols (Sockets).

• Sharing via these facilities are

  • expensive due to greater generality, and

  • may have unhelpful semantics, but

  • allow for unlimited data transfer.

Control Sharing

• Control sharing is related to process state.

  • Process A may want to know if process B is done, or just starting.

• Control sharing is like one-bit data sharing.

  • Data sharing can be used for control sharing.

  • Control-sharing specific mechanisms can be optimized.

    • No bits are copied anywhere.

Control-Sharing Mechanisms

• Control sharing mechanisms include

  • Data sharing mechanisms.

    • Send status or ok messages.

  • Signals, also known as software interrupts.

  • Semaphores.

  • Process-state synchronization.

Producer-Consumer

• A producer thread writes data into a buffer, a consumer thread reads data from the buffer.

  pr() while true buff = p() co() while true c(buff)

  data buff main() run_thread(pr) run_thread(co)

Problems

• The producer and consumer aren't coordinated.

  • The consumer could read the same data twice, or read an empty buffer.

  • The producer could overwrite unread data.

  • The producer and consumer could operate on the buffer at the same time.

• These are problems in both data and control sharing.

Solutions

• Use control synchronization to insure that at most one thread accesses the buffer at any time.

• Use data synchronization to insure that each thread accesses the buffer when it's in the proper state.

  • The producer accesses an empty buffer.

  • The consumer accesses a full buffer.

Mutual Exclusion

• We need to insure at most one thread accesses buff at any time.

• This is the mutual exclusion property:

  There is always at most one thread accessing a resource.

• For some resources, mutual exclusion is optional;
  For others, it is required.

Control Synchronization

• A critical section is one or more sections of code in one or more processes.

  • Because only code can access a resource, "code" = "resource".

  • Also, code is a resource.

• A critical section provides execution mutual exclusion for code:

  There is at most one thread executing any code in the critical section.

Critical Sections

• Critical sections are marked with the begin_cs() and end_cs() system calls.

  pr() while true begin_cs() buff = p() end_cs()

  co() while true begin_cs() c(buff) end_cs()

• Now only pr() can be writing buff or co() can be reading it.

Implementing Critical Sections

• Critical sections are most simply and easily implemented by disabling interrupts.

  begin_cs()
    interrupt_disable()
  
  end_cs()
    interrupt_enable()
  

• interrupt_enable() and interrupt_disable() are usually privilidged assembly instructions.

Critical Section Rules

• There are three important rules for critical sections:

  1. Keep it complete.

  2. Keep it running.

  3. Keep it short.

• Getting critical sections wrong makes the computation incorrect, slower than it could be, or completely broken.

Keep It Complete

• Always match a begin_cs() call with an end_cs() call.

  pr()
    begin_cs()
      buff = p()
      if error
        return
    end_cs()
  

• Othewise the critical section is permenently locked.

Keep It Running

• Never block in a critical section.

  pr()
    begin_cs()
      buff = disk_read()
    end_cs()
  

• This forces perhaps unnecessary synchronization, and may deadlock the system.

Keep It Short

• Keep critical-section computations short.

  pr() while true begin_cs() buff = p() end_cs()

  pr() while true b = p() begin_cs() buff = b end_cs()

• This avoids unnecessary delays and increases concurrency.

A Small Problem

• Printers and scanners can't be shared.

  p1() begin_cs() print(f1) end_cs() p2() begin_cs() print(f2) end_cs()

  s1() begin_cs() f1 = scan() end_cs() s2() begin_cs() f2 = scan() end_cs()

A Small Problem Still

• But now p₁ can't access the printer when s₂ is accessing the scanner.

  p1() begin_cs() print(f1) end_cs()

  s2() begin_cs() f2 = scan() end_cs()

• One critical section deals pooly with multiple, independent resources.

A Simple Solution

• Identifiy each critical sections.

  p1() begin_cs(pid) print(f1) end_cs(pid) p2() begin_cs(pid) print(f2) end_cs(pid)

  s1() begin_cs(sid) f1 = scan() end_cs(sid) s2() begin_cs(sid) f2 = scan() end_cs(sid)

Multiple Critical Sections

• An identified critical section provides limited mutual exclusion for code:

  There is at most one thread executing any code associated with the identified critical section.

  • What's happening in other critical sections doesn't matter.

• Identified critical sections are easy to implement, but hard to implement efficiently.

  • Other synchronization facilities provide the same effect more efficiently.

Data Synchronization

• Critical sections provide buffer mutual exclusion.

• Now the producer and consumer need to synchronize over the state of the buffer.

  • The consumer only reads a full buffer.

  • The producer only writes an empty buffer.

A Simple Solution

• Use a boolean to indicate the state of the buffer.

  • The producer and consumer synchronize over the boolean.

  data buff bool empty = true pr() while not empty { } begin_cs() buff = p() end_cs() empty = false

  co() while empty {} begin_cs() c(buff) end_cs() empty = true

Spin Locking

• This technique

  while not empty { }
  begin_cs()
  buff = p()
  end_cs()
  empty = false
  

  is known as spin locking.

• Spin locking is inefficient and does not work if there's more than one producer or consumer.

Inefficient Spin Locks

• A process in a spin lock burns CPU time repeatedly testing a boolean.

  while not empty { }
  

• On a uniprocessor system, it's more efficient to block the process.

  • Spin locks may be o.k. for multiprocessor systems.

• Spin locking also requires a pre-emptive scheduler to work at all.

Unsafe Spin Locks

• The stone in the bowl.

  • There are two bowls marked "full" and "empty".

  • If a stone is in the full bowl, the buffer is full; if a stone is in the empty bowl, the buffer is empty.

  • One thread at a time tries to grab the stone.

    • If several threads are grabbing at the same time, one is selected as the winner and gets to grab.

  • If the stone's in the bowl, the grabbing thread always gets it.

  • If the stone's not in the bowl, the grabbing thread never gets it.

    • The stone is never added to the bowl while a thread is grabbing.

    • There's only one stone.

  • The grabbing threads never interfere with the replacing thread.

• The stone and bowl solution.

  • The stone's initially in the empty bowl.

  • Producers keep grabbing in the empty bowl until one of them gets the stone.

  • The successful producer fills the empty buffer and puts the stone in the full bowl.

  • Consumers keep grabbing in the full bowl untill one of them gets the stone.

  • The successful consumer emptys the full buffer and puts the stone in the empty bowl.

• The stone and the bowl is a metaphore for the semaphore.

  • A semaphore is an abstract data type with the following operations:

    • semaphore(bool)() create a semaphore containing a stone when called with true or not when called with false.

    • bool grab()() returns when the stone is in the bowl and the calling thread has managed to grab it.

    • put()() returns the stone to the bowl.

  • This is a binary semaphore because it is either true or false (it contains either zero or one stones).

• The semaphore solution to producer-consumer buffering.

  semaphore full(false), empty(true)
  data buff
  
  pr()
    while true
      full.grab()
      buff = p()
      empty.put()
  
  co()
    while true
      empty.grab()
      c(buff)
      full.put()
  

  • The explicit critical section markers are gone.

    • There's only one stone, and the thread dealing with the buffer has it.

• Implementing binary semaphores.

  • Each binary semaphore needs a boolean and a queue of threads waiting to grab for the stone.

  • The boolean and queue are shared amoung all threads using the semaphore, and so need to be accessed under mutual exclusion.

  • Put is implemened as

    begin_cs(sema_id)
      stone = true
      deque a waiting thread, if any,  and make it ready.
    end_cs(sema_id)
    

  • Grab is implemented as bool winner = false begin_cs(sema_id) if stone winner = true stone = false end_cs(sema_id) if not winner block on the semaphore waiting queue

  • Given the queue operations, these are best implemented by the OS as system calls.

    • In which case the critical sections can be implemented by disabling interrupts given the shortness of the code.

• There are many variations and extensions for semaphores.

  • Counting semaphores can contain more than one stone.

    • Suppose there are three printers, all identical.

  • Other operations.

    • try() is a non-blocking grab(); it returns true if the calling thread managed to grab the stone; false otherwise.

      • This can be used to implement asynchrony in semaphore management.

    • release() is similar to put(): it puts the stone back in the bowl, but unblocks all waiters rather than just one.

      • The grab() function has to be re-implemented to use a loop if the semaphore provides release().

      • Java calls this notifyAll().

    • waiters() returns the number of threads waiting to grab for the stone.

    • There are many others.

• Binary semaphores can easily implement critical sections.

  • A thread needs the stone to execute code in the critical section.

  • Each critical section gets its own semaphore, allowing for multiple critical sections.

  • Initially each critical-section semaphore is true (the critical section is empty).

  • The start of each code section in the critical section is marked with a get() on the associated semaphore.

  • The end of the section is marked with a put().

  • A binary semaphore used to implement a critical section is called a mutex.

• Semaphores vs. explicit critical sections.

  • Semaphores minimize system implemented mutual exclusion, which is safer.

    • However, abusing semaphores can still introduce unnecessary synchronization.

  • Threads can still "forget" to return the stone to the bowl.

This page last modified on 14 November 2004.