CS 332 s20 — Introduction to Concurrency

Table of Contents

In The Process Model topic, we saw that a process consists of (at least):

In today's topic, we will decompose these and separate the concepts of thread and process.

1 The Big Picture

Threads are about concurrency and parallelism

  • Parallelism: physically simultaneous operations for performance
  • Concurrency: logically (and possibly physically) simultaneous operations for convenience/simplicity
  • One way to get concurrency and parallelism is to use multiple processes
    • The programs (code) of distinct processes are isolated from each other
  • Threads are another way to get concurrency and parallelism
    • Threads share a process — same address space, same OS resources
    • Threads have private stack, CPU state — they are separately schedulable units

1.1 Examples

mapthreads.png

Consider an Earth Visualizer similar to Google Earth. This application lets the user virtually fly anywhere in the world, see aerial images at different resolutions, and view other information associated with each location. A key part of the design is that the user's controls are always up herbal: when the user moves the mouse to a new location, the image is redrawn in the background at successively better resolutions while the program continues to let the user adjust of you, select additional information about the location for display, or enter search terms.

To implement this application the programmer might write code to draw a portion of the screen, display user interface widgets, process user inputs, and fetch higher-resolution images for newly visible areas. In a sequential program, these functions would run in turn. With threads, they can run concurrently so that the user interface is responsive even while new data is being fetched and the screen being redrawn.

Other examples:

  • Imagine a web server, which might like to handle multiple requests concurrently
    • While waiting for the credit card server to approve a purchase for one client, it could be retrieving the data requested by another client from disk, and assembling the response for a third client from cached information
  • Imagine a web client (browser), which might like to initiate multiple requests concurrently
    • The Carleton CS home page has dozens of "src= …" HTML commands, each of which is going to involve a lot of sitting around! Wouldn't it be nice to be able to launch these requests concurrently?
  • Imagine a parallel program running on a multiprocessor, which might like to employ "physical concurrency"
    • For example, multiplying two large matrices — split the output matrix into \(k\) regions and compute the entries in each region concurrently, using \(k\) processors

1.2 What's the goal?

  • If I want more than one thing running at a time, I already have a mechanism to achieve that
    • Processes
  • What's wrong with processes?
    • IPC (inter-process communication) is slow
      • Why?1
  • What's right with processes?
    • Convenient abstraction of CPU, memory, I/O

1.2.1 What's needed?

  • You'd like to have multiple hardware execution states:
    • an execution stack and stack pointer (SP)
      • traces state of procedure calls made
    • the program counter (PC), indicating the next instruction
    • a set of general-purpose processor registers and their values
  • That's a thread
  • You’d like to have very fast communication among the separate execution contexts
    • Use shared memory
      • All threads run in the same virtual address space
    • Globals are shared
    • Locals are "private"
      • Except there is no enforcement of that (threads are free to access any addresses in their shared virtual address space)

1.2.2 How could we achieve this?

  • Key idea:
    • separate the concept of a process (address space, OS resources)
    • … from that of a thread of control (execution state: stack, stack pointer, program counter, registers)
  • This execution state is usually called a thread

thread.png

1.3 Reading: Concurrency: An Introduction

Read Chapter 26 (p. 303–315) of the OSTEP book. It gives a concise overview of the idea of threads and how they're used. The chapter also previews the challenge we will spend the next three weeks exploring: how can we effectively and efficiently coordinate among concurrent threads?

Key terms:

  • thread-local
  • interleaving (when the ordering of operations from multiple threads mix together, they interleave—a given potential ordering is called an interleaving)
  • race condition or data race
  • critical section
  • mutual exclusion
  • atomic operation

1.3.1 Quick Checks

  • Why is the behavior of t0.c (figure 26.2) nondeterministic?2
  • How can a single line of C code like counter++ result in a data race?3
  • How does mutual exclusion prevent data races?4

2 What Are Threads?

  • Most modern OS's therefore support two entities:
    • the process, which defines the address space and general process attributes (such as open files, etc.)
    • the thread, which defines a sequential execution stream within a process
  • A thread is bound to a single process / address space
    • address spaces can have multiple threads executing within them
    • sharing data among threads is cheap: all see the same address space
    • creating threads is cheap too!
  • Threads become the unit of scheduling
    • processes / address spaces are just containers in which threads execute
    • threads provide an execution model in which each thread runs on a dedicated virtual processor with unpredictable and variable speed

threadAbstraction.png

  • Why "unpredictable speed"?
    • The scheduler and available processors can lead to many possible interleavings (see examples below).
    • Thread programmers should therefore not make any assumptions about the relative speed with which different threads execute.

unpredictableSpeed.png

  • Threads are concurrent executions sharing an address space (and some OS resources)
    • Address spaces provide isolation
      • If you can't name it, you can't read or write it
    • Hence, communicating between processes is expensive
      • Must go through the OS to move data from one address space to another
    • Because threads are in the same address space, communication is simple/cheap
      • Just update a shared variable!

perThread.png

process-addr-space-combined.png

2.1 The Process/Thread Separation

threads-vs-processes.png

Different aspects of this diagram:

  • one thread per process: a simple, single-threaded application running in user mode, using system calls to ask the kernel to perform privileged operations
  • many threads per process: a process has multiple concurrent threads, all executing in user mode. At any given time a subset of these threads may be running while the rest are suspended.
  • many single-threaded processes: as recently as 20 years ago, many operating systems supported multiple processes, but only one thread per process (this is the model osv uses, in fact). To the kernel, however, each process looks like a thread: a separate sequence of instructions, executing sometimes in the kernel and sometimes at user level. For example, on a multiprocessor, if multiple processes perform system calls at the same time, the kernel, in effect, has multiple threads executing concurrently in kernel mode.
  • many kernel threads: to manage complexity, shift work to the background, exploit parallelism, and hide I/O latency, the operating system kernel itself can benefit from using multiple threads. In this case, each kernel thread runs with the privileges of the kernel. The operating system kernel itself implements the thread abstraction for its own use.

Supporting multithreading — that is, separating the concept of a process (address space, files, etc.) from that of a minimal thread of control (execution state), is a big win. It means that creating concurrency does not require creating new processes. Since processes have a lot more overhead than threads (e.g., a whole new address space), this makes concurrency faster / better / cheaper. Multithreading is useful even on a single core processor running only one thread at a time—why?5

3 Homework

  1. Remember that the week 2 quiz is due at 9pm tonight (April 22)
  2. Get started on Lab 2. Please post questions in Slack!

Footnotes:

1

Processes are isolated from each other (private addresses spaces), so any sharing of data requires at least one level of indirection

2

Threads are separately schedulable units, meaning the OS scheduler decides which runs when. This creates multiple possible interleavings of the operations of the two threads, and thus multiple possible program behaviors.

3

A single line of C code often compiles to multiple processor instructions (e.g., a read, an add, and a write), creating the possibility that two threads accessing shared data could interfere with each other.

4

It ensures that only one thread can execute a critical section/access a shared piece of data at a time.

5

Threads can end up waiting for I/O, so a multithreaded process can have one thread wait for blocking I/O while another makes progress.