Multiprogramming and Multiprocessor Systems

Learning outcomes:

  • Explain what multiprogramming is, and what an operating system needs to support it
  • Describe multi-core and multiprocessor systems, including sockets, cores, and logical processors
  • Compare multiprocessor organizations and memory designs, such as symmetric multiprocessing and NUMA
  • Explain how multiprocessor scheduling, processor affinity, and load balancing keep every core busy

Would you like to download my PowerPoint to follow along?

  • Multiprogramming
    • Multiprogramming keeps several processes in memory at the same time
    • While one process uses the CPU, another can use an I/O device, and the rest wait in line
      • Device work overlaps with CPU work, so less time is wasted
    • The number of processes in memory at once is the degree of multiprogramming
      • With a degree of 1, only one process is in memory, and the CPU sits idle every time it waits for I/O
  • Quick Review from Week 2
    • A process is a program that's running, or waiting for the CPU or I/O
    • The OS keeps a line (queue) for each service, such as the CPU or a drive
    • A context switch saves one process and loads another
    • The scheduler picks which process runs next (Week 5)
  • Requirements for Multiprogramming
    • Keep the CPU and other resources busy as much as possible
    • With one CPU, only one process actually runs at a time. The others wait in the ready queue
    • Processes also need passive resources, such as memory
  • OS Features Needed for Multiprogramming
    • I/O routines supplied by the system, such as device drivers
    • Memory management, to keep processes apart (Week 11)
    • CPU scheduling (Week 5)
    • Handing out devices fairly
  • Model of a System with Multiprogramming
    • A simple model has one CPU, one I/O device, and three queues:
      • Processes waiting for memory
      • The ready queue, for the CPU
      • The I/O queue, for the device
    • The CPU and the device work at the same time, on different processes
  • Multiprocessor Systems
    • A computer with more than one processor, or more than one core
    • Benefits: more processing power, and use as many processors as the work needs
    • Extra jobs for the OS:
      • Keep all processors busy, with work spread evenly
      • Make sure every processor sees the same, up-to-date copy of shared data
      • Keep related processes in step, and stop them from changing shared data at the same time (mutual exclusion)
  • Multi-core Is Everywhere
    • Socket: a physical processor chip. Most laptops and phones have one, and big servers may have two or more
    • Core: a complete processor inside the chip. Phones have 6 to 8, and server chips can have over 100
    • Logical processor: what the OS sees. With hyper-threading, each core shows up as two
    • Check yours: Task Manager, Performance, CPU on Windows, or lscpu and nproc on Linux (Linux manual page: lscpu)
  • Flynn's Categories
    • Flynn's categories sort computers by how many instructions and how much data they handle at once
      • SISD: one instruction on one piece of data. A classic single-core processor
      • SIMD: the same instruction on lots of data at once. Built into every modern CPU, and how GPUs work (Arm: Neon)
      • MISD: several instructions on the same data. Rarely used
      • MIMD: different instructions on different data. Any multi-core processor
    • Historical note: VLIW chips, such as Intel's Itanium, packed several instructions into one. Itanium has been discontinued. Still worth knowing because you may meet the term in older servers and textbooks
  • Processor Interconnection Schemes
    • How processors and memory are connected inside a computer
    • The classic designs, pictured below:
      • Shared bus: everyone shares one connection, like one hallway
      • Crossbar switch: a switch for every processor and memory pair, like a grid of doors
      • Mesh: each node connects to its neighbors, like city blocks
      • Hypercube: nodes at the corners of cubes, connected corner to corner
    • Today, the cores in one chip are linked by a fast on-chip network, and AMD builds processors from several small chips (chiplets) in one package
  • Processor Interconnection Diagrams
    • Diagrams: a shared bus, a crossbar switch matrix, a 2-D mesh, and 3-D and 4-D hypercubes
  • Loosely Coupled vs. Tightly Coupled Systems
    • Tightly coupled: processors share most resources, including memory
      • More efficient, and easier for OS programmers
    • Loosely coupled: each processor has its own memory, and they talk by sending messages
      • More flexible, survive failures better, and can grow bigger
    • A multi-core laptop is tightly coupled. A cluster of servers is loosely coupled (Week 14)
  • Coupling Diagrams
    • Diagrams: a tightly coupled system with two processors sharing resources, and a loosely coupled system with two processors, each with its own memory, connected by a communication link
  • Multiprocessor Operating System Organizations
    • Primary/secondary: one processor runs the OS, and the others only run user programs
      • Simple, but if the primary fails, everything stops
      • You may hear this called master/slave. We use primary/secondary instead, because the old terms come from slavery and can make people feel unwelcome, and the new terms describe the job just as clearly. The Linux kernel and many other projects have made the same change (Linux kernel coding style: inclusive terminology)
    • Separate kernels: each processor runs its own copy of the OS. A failure only affects that processor
    • Symmetric: all processors share the OS and the work. The most fault tolerant, but it needs mutual exclusion
  • Organizations Today
    • Windows, macOS, and Linux all use the symmetric design, called symmetric multiprocessing (SMP)
    • Phones with performance and efficiency cores still run one symmetric OS, but the scheduler treats the cores differently (later this week)
    • Historical note: the textbook examples, nCUBE, Tandem, and BBN Butterfly, are 1980s systems. Still worth knowing because the other designs still show up in embedded devices and research systems
  • Uniform Memory Access (UMA)
    • All processors share all memory, at about the same speed
    • Usually connected by a shared bus or crossbar switch
    • Also called symmetric multiprocessing (SMP). Works well for a small number of processors
  • Nonuniform Memory Access (NUMA)
    • Each node has a few processors and its own local memory
    • Local memory is faster than memory on another node, and NUMA scales to bigger systems than UMA
    • Big servers today are NUMA. On Linux, lscpu or numactl --hardware shows the nodes (Linux kernel documentation: What is NUMA?)
  • Other Memory Designs
    • COMA (cache-only memory architecture): each node's memory acts like a cache, and data moves to the node that uses it most. Mostly a research design
    • NORMA (no remote memory access): processors don't share memory at all, and talk by sending messages. This is really a distributed system (Week 14)
  • Multiprocessor Scheduling
    • Decides which process runs on which processor, and when
    • Two goals that pull against each other:
      • Parallelism: run as much at the same time as possible
      • Processor affinity: keep a process on the same core, because its data is already in that core's cache
    • Simple approaches use one shared line for all processors. Smarter ones keep related processes together
    • Linux gives each core its own run queue (Linux kernel documentation: Scheduler)
    • You can pin a program to certain cores: Set affinity in Task Manager's Details tab, or taskset on Linux (Linux manual page: taskset)
  • Scheduling on Mixed Cores
    • Many chips mix performance cores and efficiency cores (Week 3)
    • The OS sends demanding work to performance cores, and background work to efficiency cores
    • This saves battery while keeping what you're using fast
  • Load Balancing
    • Spread the work evenly, so no processor sits idle while another is overloaded
    • Makes response times more consistent
    • Static: decide where work goes ahead of time. Works when the workload is predictable
    • Dynamic: move work while the system runs. Busy processors can hand work off, or idle ones can ask for more
    • Linux balances automatically. Watch htop while a big job runs, and you'll see the load spread across every core
  • Multiprocessor Mutual Exclusion: A Preview
    • When processors share data, two of them can try to change it at the same time
    • Mutual exclusion makes sure only one changes it at a time
    • Some tricks that work on one processor don't work with many, such as turning off interrupts, which only affects one core
    • This comes back in more detail in Week 6, Synchronization, including the locks that make it work

Suggested Activities and Discussion Topics:

  • Discussion: your computer probably has several processor cores. How does the operating system decide which core runs which program?
  • Activity: find out how many cores and logical processors your computer has. On Windows, open Task Manager, choose Performance, then CPU. On Linux, run lscpu or nproc. Does each core show up as one logical processor, or two?
  • Activity: open Task Manager (right-click the CPU graph and choose to show logical processors) or htop on Linux, then start something demanding, like a big game or video export. Does the work spread across every core?
  • Activity: in a Linux virtual machine, run lscpu and look for the NUMA lines. How many NUMA nodes does it have? Why do you think a laptop usually has just one?
  • Discussion: why might a laptop maker add efficiency cores instead of more performance cores?

Would you like to see some more classes? Click here