Reading: OSTEP, up to Ch. 6

Warm-up Question

• Open Task Manager / Activity Monitor – whatever application your system provides to see running programs
• How many processes do you see?
• It is likely you will see hundreds of processes
• How many CPU cores does your computer have?

Introduction

“An OS is a land of magic and illusions”

• So far, we’ve been building our toolbox for understanding OS: Assembly, C, GDB, etc.
  • Knowing about registers and instructions = Useful
  • Knowing about memory, addresses, pointers = Useful
  • C is the language many OS are written in
• Today we will start diving into the OS itself
• The main job of an OS is to make complex HW “easy” to use - both for users and for programmers
• To achieve this, two main tools are employed:
  1. abstraction
     • The OS provides a simplified interface (API) to perform HW tasks
  2. virtualization
     • The OS creates and illusion of a more ideal, more powerful machine
• Our first foray into the OS will be looking at how the OS virtualizes the CPU and abstracts computation related to a program as a process

Processes

• A representation of a program on a disk is an executable file (and associated libraries)
• The representation of a program loaded in memory is a process
• The executable contains instructions - as does a process in memory
• Each CPU core performs an instruction at a time, done as part of the fetch-decode-execute (FDE) cycle:

• So, if your CPU has 4 cores there are 4 FDE cycles going on at the same time
• But… how many programs do you have running at the same time?
• How is it that we see ~100 programs run on just 4 cores?
• How is it that the same can be seen on older hardware with just a single core?

Limited Execution and Time Sharing

• Here’s an idea: we start multiple programs and the we let each run for a bit, then we switch to the next one
• This is called time sharing
• To do this we’ll need some bookkeeping: let’s start with each process being in one of two states: running or ready
• Here’s what the situation might look like with 3 processes on a single CPU (ready state is represented by a dashed line):

• Seems promising, but… are these two states enough?
• What about if a process needs to read something from the disk or perform a network request?
• These operation take (comparatively) long to complete
• If we leave the process running, it will keep hogging the CPU while it waits for disk or network I/O to complete
• If we switch the process to ready, it might not be ready to run when it is its turn again, so we will waste time asking it to run
• Solution: introduce a third state: blocked – this means that the process requested some I/O operation and cannot run until that operation is completed
• (How convenient that the OS is also in charge of getting the result of such operation back to the process – but more on that later)
• Below is a little more terminology

scheduling

The act of letting the process take control of the CPU

descheduling

Removing the process from the CPU to use it for something else

• Here’s the different states of a process and transitions between them

           deschedule
+---------+ -------> +-------+
| Running |          | Ready |
+---------+ <------- +-------+
        \   schedule   ^ 
   I/O   \            /  I/O
requested \          /  completed
           v        /   
          +---------+    
          | Blocked |    
          +---------+

• We’re on the right path, but we have one problem…
• The CPU runs a FED cycle on a stream of instructions, taken from the executable
• The OS is also a stream of instructions, performed on the CPU
• The OS is responsible for interrupting one stream of instructions (descheduling) and replacing it with another stream (scheduling)
• Where’s the flaw here?
• Who gets the CPU to execute the OS’ instruction stream so it can do its job??

Switching Between Processes

• One solution would be for the OS to act as an intermediate and supervise the execution of each instructions, deciding when to start executing its own code
• Problem? Very slow…
• We want each program to take full advantage of the CPU when it has a chance to do so
• Ideally, each process should get to execute its own instructions and something should switch to the OS as necessary or appropriate
• One way is to let the OS take control when a program requests I/O: We block it, and let something else run, while hardware deals with the I/O request
• But what if a program doesn’t need to use I/O for a long time? Then it just keeps running?

Cooperative Multitasking

• Another solution: let the process relinquish control – yield the CPU to the OS

• This is called cooperative multitasking

• Each program will run for a bit, and then say “okay, I can rest for a bit” and pass control over to the OS, which can then schedule another program

• Where’s the downside?

• What if programs don’t cooperate? What if they don’t relinquish control of the CPU? What happens if…

  while (1) {
  }

• This could be non-malicious

• So we need a way of letting the OS take control without relying on the programs to do that for us

Preemption

• A more viable and robust solution is to ensure the OS has regular say over what’s being executed by leveraging interrupts

Mechanism: Exceptional Control Flow

• There are 2 main categories of exceptions

1. Asynchronous: (Hardware) Interrupts
   • Caused by external events (external to the CPU) - meaning not caused by something the software did
   • Examples: timer interrupts, Ctrl+C, data available from disk, data arrives from net, …
2. Synchronous
   1. Traps
      • Intentionally triggered by the software - system calls, breakpoints
      • System calls are the primary mechanism of how user programs can interact with the OS
      • Used to request a service from the OS - The service code needs to execute in privileged mode
   2. Faults
      • Unintentionally triggered
      • Potentially recoverable
      • Page faults, floating point exceptions
   3. Aborts
      • Unintentionally triggered
      • Unrecoverable
      • Illegal instruction, RAM parity errors

To be continued…