Operating Systems Lecture Notes

2014 September 16 • Inter-Process Communication

---

Outline

• Quicksort
• Inter-process communication.
  • Shared memory.
• Resource pooling.
  • Message passing.

Sorting

• How does quicksort sort?

  

Quicksort

qsort(a[], l, r)
  if r - l > 1
    m = partition(a, l, r)
    qsort(a, l, m)
    qsort(a, m, r)

qsort(a, 0, a.length)

• So what?

Embarrassing Concurrency

• Quicksort is an example of embarrassing concurrency.

  static void * qsorter(void * qsp)
  
    if (qsp->right - qsp->left <= 16)
      selection_sort(qsp->a, qsp->left, qsp->right)
    else
      mid = partition(qsp->a, qsp->left, qsp->right)
      tid1 = make_qsorter(qsp->a, qsp->left, mid)
      tid2 = make_qsorter(qsp->a, mid, qsp->right)
  
      check_error(pthread_join(tid1, NULL))
      check_error(pthread_join(tid2, NULL))
    
    pthread_exit(0)
  

• See the code.

Quicksort Concurrency

Thread Communication

How do quicksort threads communicate? They don’t. Or through thread-create parameters.

t_create(qsort, left, mid)
t_create(qsort, mid, right)

• And through the shared process address space.

Quicksort Communication

• Each thread gets its own piece of the array.
  • It partitions its piece.
  • Then hands off each part to a child thread.
• There is no conflict over a particular piece of the array.
  • No coordination or synchronization needed.
  • Or rather, trivial fork-exit synchronization.
• Shared state is nice in this way.

Process Quicksort.

• Threads did well for quicksort, how about processes?

  int main()
  
    if (pid = fork()) ≡ 0
      qsorter(array, 0, n)
    else
      waitpid(pid, NULL, 0)
      check_sorted_array(array, 0, n)
  

Process Quicksorting

• How does process quicksort work?

  

Process Quicksort..

void qsorter(array[], left, right)

  if (right - left ≤ 16)
    selection_sort(array, left, right)
  else
    mid = partition(array, left, right)

    if (pid-l = fork()) ≡ 0
      qsorter(array, left, mid)
    
    if (pid-r = fork()) ≡ 0
      qsorter(array, mid, right)
    
    waitpid(pid-l, NULL, 0)
    waitpid(pid-r, NULL, 0)

  exit(EXIT_SUCCESS)

• See the code.

Mission Accomplished?

• Wow! Pretty cool, right? But does it work?
• What is process quicksort concurrency?
• What is process quicksort communication?

Process Concurrency

Inter-Process Communication

fork() semantics easily communicates resource down the process tree.

• Communicating resources back up the tree is not so easy.

Inter-Process Protection

• The protection boundary around a process consists of
  • an address-space per process, and
  • no inherent, general mechanism for one process to access another process’s address space.
• Protection boundaries are a design decision.
  • They isn’t necessary, and may not be available on small OSs.

The IPC Problem

• How can processes easily communicate among themselves in arbitrary ways?
• Threads don’t have this problem because they have natural sharing.
  • All threads are within the same protection boundary.
  • But what about threads in different protection boundaries (processes)?
• Is there some way to provide “natural sharing” among processes?

Shared Storage

• Oh, you mean files.
  • Well, yes but,
    • Files are not particularly natural to a processes access patterns.
    • File access is even slower than are processes.
• A mechanism providing thread-like sharing among processes.

Shared Memory

• Shared memory is a named byte-array mapped into a process address space.
• Some POSIX shared memory operations:
  • shm_open() — create or access shared memory.
  • mmap() — map shared memory into a process address space.
  • close() — unmap shared memory.
  • shm_unlink() — delete shared memory.

Shared Memory Example

Observations

• There are other shared-memory systems.
  • SYS-V Unix shared memory, for example.
• Sharing doesn’t have to follow the process tree.
  • A process with the segment name and permission can map the segment.
• There is no access penalties for mapped shared memory.
  • There are costs, but they're obscure.

Quicksort Concurrency Again

• How many threads (or processes) are there?

Runaway Concurrency

• Quicksort uses O(n) concurrent executions to sort an n-element array.
  • Too many even for small arrays (n ≈ 1000).
• Need some way to limit or throttle concurrency to reasonable amounts.
  • “Reasonable” is a context-dependent quality.

Resource Pooling

• Define some reasonable limit n and make sure there's n concurrency units available.
  • N threads or processes.
• The collection is known as a thread (or process) pool.
  • In general, the technique is known as resource pooling.
  • Pooling is related to caching.

Thread Pool Organization

• There's one boss (or master) thread and n worker (or slave) threads.
• The boss thread manages the pool.
  • Manage the pool (add and remove worker threads).
  • Dispatch work to the pool.
  • Keep track of over-all progress.
• Worker self-organization is also possible.
  • At greater complexity.

Thread Pool Example

Quicksort Tasks

• A thread sorts array[left..right).

  

• A quicksort task is a struct.

  struct { int left, right }
  

Quicksort Task Communication

• Quicksort tasks get put into a queue (or a set).
• An idle worker pulls a task from the queue.
  • Or waits for a task if the queue is empty.
• The left and right subtasks get put back in the queue.
• This communication repeats until the array's sorted.
  • When does that happen?

Quicksort Pool Example

Messaged-Based Communication

• Sending messages around is another IPC mechanism.
  • In quicksort, the struct is the message.
• For threads, shared store is a central part of message passing.
• An OS may support other, more formal message-passing mechanisms.
  • Usually called mailboxes.

Process-Based Message Passing

• Via shared storage, processes can use message-passing IPC.
• There are non-sharing message-passing mechanisms too.
  • UNIX or Berkeley sockets, for example.
• Message queues are another popular mechanism.

Summary

• The main IPC mechanisms are shared storage and message passing.
• IPC are useful for both threads and processes.
• Resource pooling is a way to control resource use.
• Understand quicksort.

---

This page last modified on 2014 September 16.