Imprint | Privacy Policy

Interrupts and I/O I

(Usage hints for this presentation)

IT Systems, Summer Term 2024
Dr. Jens Lechtenbörger (License Information)

1. Introduction

1.1. Today’s Core Questions

  • Recall keyboard handling in Hack.
    • You used a loop to wait for I/O; this is called polling.
  • How can we improve I/O processing over polling?
    • Why keep CPU busy in loop when nothing happens?
    • With multitasking such time is wasted as other tasks could make better use of the CPU.
  • Add interrupts as I/O notification mechanism.
    • How to organize I/O then?
    • How much overhead arises?
      • (Overhead: Additional indirect computation time; makes system less efficient.)
      • How to deal with “lots” of I/O events?

1.2. Learning Objectives

  • Explain techniques for I/O communication
    • Including sequencing of events under synchronous and asynchronous techniques (polling vs interrupts)
  • Discuss dis/advantages of I/O communication techniques
  • Explain (interrupt) livelock and mitigation via hybrid technique

1.3. A Note on Literature

1.4. Retrieval Practice

  • Before you continue, answer the following; ideally, without outside help.
    • How does the von Neumann architecture look like?
    • How does I/O processing work with Hack?
    • How to talk to an OS kernel?
    • How are programs, processes, and threads related?
    • What is multitasking? What are its advantages?

1.4.1. Von Neumann and Hack Architecture

1.4.2. Computations


2. Hack vs Modern Computers

2.1. Recall: Von Neumann Architecture

von Neumann Architecture

von Neumann Architecture

Figure by Kapooht under CC BY-SA 3.0; converted from Wikimedia Commons

2.2. Tabular Comparison

         Modern Computer          
      (e.g., PC, smartphone)      
 • RAM for data, ROM for instructions 
 • Physical RAM addresses             
 • No secondary memory                
 • RAM for data and instructions  
 • Physical and virtual addresses 
 • Memory hierarchy (disks)       
 • Single core                        
 • Single mode of execution           
 • Neither cache nor MMU              
 • Multi-core                     
 • Multiple protection domains    
 • Caches and MMU                 
 • No interrupts                      
 • Polling for I/O (recall keyboard)  
 • Interrupts, DMA                
 • Different options for I/O      
 • Language library                   
 • Single thread, no multitasking     
 • No virtual memory                  
 • Real OSs with system calls     
 • Multitasking, scheduling       
 • Virtual memory                 

2.3. CPUs in the Real World

  • Known from Hack
    • Registers (addresses, data, control information)
    • Instruction execution cycle (e.g., fetch, decode, execute)
  • Additionally

    • Caching

      • Cache = Small, fast memory between CPU and RAM
        • (Usually, multiple levels of caches; L1, L2, …)
      • Instructions and data must be in cache before CPU can access them
      • Replacement policies when full (similar to those for memory management)
      • Overhead for context switches, cache pollution

    • Special instructions and modes

      • Access to memory and devices in kernel mode: Subsequent slide
      • Enter idle state when nothing to do (save power)
    • Interrupts: Later slides

2.4. Privilege Levels/Rings/Modes

  • Hierarchical protection domains of CPUs
    • Recall: Kernel mode vs. user mode
      • (See also Sec. 7.3.1 of (Hailperin 2019))
      • Governed by bit pattern in special register
  • Instruction set restricted depending on mode/privilege level
    • Special registers protected
    • I/O, memory management protected
  • OS starts in kernel mode
    • Applications run in user mode
    • Interrupts (system calls, traps, …) lead into kernel mode

2.5. Big Picture

  • I/O devices are components that interact with the OS

    • Some receive requests and deliver results
      • E.g., disk, printer, network card
    • Some generate events on their own
      • E.g., timer/clock, keyboard, network card
  • Alternative types of I/O

    1. OS polls (continuously asks) for events/results
    2. Device triggers interrupt when event occurs or result is ready
      • (Historically, special CPU input pins/bits were used to signal interrupts; now, also existing buses are used, e.g., MSI)
      • CPU interrupts current computation and jumps into OS, which handles interrupt

2.5.1. Types of I/O

  • With polling, I/O is called synchronous
    • OS monitors I/O operation for completion
  • With interrupts, I/O is called asynchronous
    • OS initiates I/O
    • I/O proceeds asynchronously, CPU free to perform other tasks
    • Device triggers interrupt when I/O operation completed
      • CPU interrupted, I/O result handled by OS

3. Polling

3.1. I/O with Polling

I/O happens synchronously while OS polls for result

I/O with Polling image/svg+xml I/O with Polling Jens Lechtenbörger Summer 2017, 2018 Application OS I/O Device time Application invokes system call for I/O OS starts I/O operation on behalf of application I/O operation proceeds, monitored by OS I/O operation finishes OS transfers result to application

3.2. Polling Observations

  • Advantages
    • Simple
    • Fast
      • Result processed as soon as it is available
        • No overhead (compared to interrupts as presented subsequently)
  • Disadvantage
    • Busy waiting = waiting on CPU for event to occur
      • CPU time wasted if I/O is slow or infrequent
      • Bad idea if wait period is “long”

3.2.1. Polling Example: Hack Keyboard

  • Program waits for user to press key
    • Loop, repeatedly reading keyboard memory location until key pressed
    • Recall memory-mapped I/O
  • CPU executes instructions all the time
  • Even if Hack had OS with multitasking, nothing else could be executed
    • CPU time in loop is wasted

4. Interrupts

4.1. Fundamental Idea

  • Interrupt: Signal to CPU

    • Generated externally to CPU (signal on bus or separate pin)
      • CPU stops doing whatever it did
      • CPU jumps (resets program counter) to interrupt handler instead (details on following slides)
  • If I/O devices generate interrupts, CPU does not need to wait for I/O completion

    • OS initiates I/O operation at device
      • CPU is free to do something else asynchronously during I/O execution
    • At later point, I/O operation completes and device triggers an interrupt
      • OS interrupt handler acts accordingly

4.2. I/O with Interrupts – Overview

  • Asynchronous processing of I/O
    • External notifications via interrupts

I/O with Interrupts image/svg+xml I/O with Interrupts Jens Lechtenbörger Summer 2017, 2018 time Application OS I/O Device Interrupt Handler Application invokes system call for I/OOS starts I/O operation on behalf of application I/O operation proceeds, asynchronously to CPU Whether same or differentapplication continues, depends on type of I/O I/O operation finishedDevice triggers interrupt,application interruptedInterrupt handled by OSsubsequently

4.2.1. Hypothetical Interrupt Example: Hack Keyboard (1/3)

  • Suppose Hack had multitasking OS with threads and interrupts (which it does not)
    • Multiple programs could run concurrently in separate threads
  • Again, wait for user to press key
    • This time, thread invokes (blocking) system call, asking OS for next pressed key
    • OS remembers to inform that thread about keyboard input, blocks it
      • OS takes that thread aside
      • OS dispatches different thread to execute on CPU

4.2.2. Hypothetical Interrupt Example: Hack Keyboard (2/3)

  • Eventually, key gets pressed
    • Keyboard triggers interrupt
      • CPU interrupts whatever it does, jumps to interrupt handler, which interacts with hardware to obtain value representing key
      • OS records that value as return value of system call
        • OS unblocks blocked thread
    • Scheduling decision by OS determines what (unblocked) thread to continue next
      • At some point in time, maybe right now, OS chooses thread that invoked the keyboard system call
        • Thread continues with return value from system call

4.2.3. Hypothetical Interrupt Example: Hack Keyboard (3/3)

  • Notice: Latency (delay) between system call and processing of its return value

    • Latency between system call and key press
      • Cannot be avoided
      • In contrast to polling, with interrupts something useful can happen on the CPU during this period

    • Between key press (interrupt) and return of key’s value into thread

      • Processing of interrupt with overhead
        • Discussed subsequently
      • Resulting delay does not exist for polling

4.3. Interrupts, Traps, Faults, Exceptions

  • Interruption of ordinary CPU execution
  • Hardware-specific, terminology not unified
  • Classification
    • Asynchronous, triggered externally
    • Synchronous, triggered internally
      • Software interrupt

        • After execution of instruction (e.g., overflow)

4.4. Interrupts and CPUs

  • OS specifies a handler for each type of interrupt and exception
    • Handler = function
    • Type of interrupt determined by number
  • E.g., x86 processors
    • Addresses of handlers stored by OS in in-memory table, the Interrupt Descriptor Table (IDT)
      • Synonym: Interrupt Vector (Table)
      • Each table entry points to one handler/function
    • CPU core contains Interrupt Descriptor Table Register (IDTR)
      • OS initializes IDTR with start address of IDT

4.5. Interrupt Handling

  • Upon interrupt of type n:
    • A context switch takes place, and (in kernel mode) the CPU
      • saves state of current execution,
      • uses IDTR to access IDT,
      • looks up entry n in IDT, and invokes corresponding handler/function.
      • Afterwards, state is restored, previous execution continued.

4.6. Aside: Interrupts for System Calls

  • Recall: System calls = API provided by OS kernel
    • Implementation is OS and hardware specific
  • Hardware specific methods to enter kernel mode
    • int 0x80 (generic), SYSCALL (AMD), SYSENTER (Intel)
  • Beyond class: Linux, Intel IA-32, int 0x80

4.7. Self-Study Quiz

This task is available for self-study in Learnweb.

  • Consider a networked machine that receives incoming messages. Each of those messages requires about 4 µs CPU time for processing. If interrupts are used, each interrupt introduces a delay of about 6 µs (caused by different types of overhead).
    • How many messages can be processed per second with polling, how many with interrupts?
    • How much time is wasted (waiting for messages to arrive) with polling in the worst case? How much spent on overhead processing with interrupts?


Hailperin, Max. 2019. Operating Systems and Middleware – Supporting Controlled Interaction. revised edition 1.3.1.
Stallings, William. 2014. Operating Systems – Internals and Design Principles. 8th ed. Pearson.
Tanenbaum, Andrew S., and Herbert Bos. 2015. Modern Operating Systems. 4th ed. Pearson.

License Information

Source files are available on GitLab (check out embedded submodules) under free licenses. Icons of custom controls are by @fontawesome, released under CC BY 4.0.

Except where otherwise noted, the work “Interrupts and I/O I”, © 2017-2024 Jens Lechtenbörger, is published under the Creative Commons license CC BY-SA 4.0.