CS-537 Introduction to Operating Systems - Lecture 1

Link: http://pages.cs.wisc.edu/~remzi/Classes/537/Spring2018/Discussion/videos.html

What is virtualization? Mapping some small number of physical resources into many virtual resources - ex 4 core CPU, multiple virtual CPUs, memory address ranges map 0 to N for every process. Virtualization creates an illusion - each running program thinks it has its own CPU, its own private memory, etc

Key aspects of virtualization? Must be efficient, should not be much slower than physical machine (low overhead). Must be secure, should restrict programs to finite operations and restricted access. For example, not all programs should have access to entire HDD, or network, or entire memory range. Historical footnote, Intel processors exposed arbitrary reading of all memory.

Strategies for CPU virtualization - time-sharing vs space-sharing. Time-sharing - when running multiple processes, let CPU switch from program A to B to A back and forth, giving a little time to each. Space sharing - allocating different blocks of memory. CPUs use time-sharing (sometimes called multiprogramming).

Abstraction: Process. A process is a running program. What are its components?

Memory - private internally, no other process should access the memory directly. This process thinks this is all the memory in the world available - called a “(virtual) address space”. What goes inside memory? Code, stack, heap

Registers - just like normal registers: program counter (PC) (RIP in 64 bit CPU). Changes all the time so CPU knows where instruction is; Stack Pointer (SP) -where in stack are we; General Purpose registers - EAX, EDI, etc - places to put data while we work. Note: Registers are faster than memory/ When we virtualize CPU, registers are primary concern

IO state - open files, for ex

“at the low level there are mechanisms” - how things work. eg you need ways to switch between running programs. On top of mechanisms are policies - rules for determining utilizing resources. Higher level decisions on top of low level mechanisms. eg when do we switch between processes? Focus of class is on mechanisms.

Core mechanism - Limited Direct Execution

What is Direct Execution? Pertains to efficiency. CPUs are very fast (bns of instructions per second). If you run a virtualized CPU, most of what you can do for efficiency is run directly on hardware (hardware is FAST).

If we’re not careful and let programs just Directly Execute on hardware, they can do what they want. That’s where limited comes in. Security, protection. Create environment where OS can prevent process from doing WHATEVER it wants. Sandbox the environment so program can get efficiency without freedom.

Start with a protocol that’s Direct Exec (not limited). Let’s say we have an OS, something simple. First program that runs on machine. OS boots up and runs. Lets say we want to run a user program (eg VSCode). Program A is some lifeless program on a disk. OS starts by loading program off disk into a process. Create an address space in memory for code, heap, stack (stack is initialized with argc and argv). CPU stack pointer points to somewhere in process stack. Program counter in PC points to first instruction in code of process. Now OS is no longer running, it jumps to Program A. Eventually Program A returns to OS when it’s done.

Problems? What if Program A (a user process) wants to do something restricted? eg access disk, allocate more memory, create new process. What if OS wants to stop Program A and start Program B? We need some way to return to OS and toggle to B. We need OS to regain control of CPU What if A does something slow? eg disk IO, network IO. We need a way to switch away from slow process to unblock behavior.

Restricted problem - we need hardware machinery as well as OS behavior. When a program wants file IO, OS needs to make sure user can access that file. We start with a mode - a per-CPU bit. The mode tells us what kind of program is on the CPU. It’s either the OS (running in “kernel mode”) or a user-program (running in “user mode”). In kernel mode, OS can do anything (unrestricted access to hardware). Advantage of open-source OS, can scrutinize code that runs on your hardware. User programs can only do limited number of things - the hardware will prevent the program from doing restricted behavior.

How do we get into one of these modes? How do we transition modes?

First, at boot time - boot into kernel mode. We assume the first thing that runs is OS and we trust the OS. If somehow code is injected into OS, it’ll be running in kernel mode and no hardware restrictions. When we want to run user program, we need a special instruction that transitions into user mode and also jumps to some location in user program.

When the user program wants to do something restricted (eg disk IO) we need to transition back into kernel mode. We also need to jump into kernel. We need some instruction to handle this. But we need to be careful. If we let a user program jump into kernel, we can’t let the user program say where in kernel it wants to jump to. Gives too much freedom to user program (eg, what if user program jumps past user-permission check in kernel). So OS needs to provide mechanism to control where user program can jump to. So this jump for user program -> kernel needs to be a RESTRICTED jump.

Provide two instructions - trap and return from trap.

Trap - hardware-provided instruction to jump into kernel at restricted location, and then elevate privilege level from user-mode to kernel-mode. Also will save enough register state to know how to return back to previous state.

Return from Trap - basically undo, restores state of process, de-escalate privileges, go back to plce in program right before execution of trap.

A (user mode) —> Trap into OS —> OS does stuff (kernel mode) —> Return from Trap —> Back to process A (user mode)

Services provided by OS in kernel mode are often called system calls - asking OS for permission to do things.

How does OS restrict WHERE user program can jump to? That happens at boot time. OS starts up in kernel mode. OS tells hardware where to jump to when a particular trap is issued. Usually you have a trap number (eg file read = trap 80). When trap number is called, OS has a set of trap handlers (created by a special instruction that tells hardware where trap handlers are in OS memory).

We need to save and restore state of a process (in this case, register state). When A traps into OS, there’s behavior in registers and OS will use those registers. So before trap, registered need to be saved into maybe a kernel stack (often hardware will save). Similarly, when we return from trap after, we need to restore register stack (often done with hardware assistance).

How does OS regain control and stop Process A and move to Process B? When OS runs process A, OS isn’t running any more. If A runs forever (while (true) {}) we’re stuck. Coopertive approach - hope that process A just doesn’t do anything bad. Kind of a security problem. Prefer the non-cooperative approach (a preemptive approach) - based on hardware support, use a timer interrupt to stop processes.

Timer interupt - at boot mode, OS runs in kernel mode. Installs trap handlers. It also starts an interrupt timer - a piece of hardware that, after period of time (eg in milliseconds) will interrupt CPU between instructions and runs OS timer interrupt handler to move back to OS from Process.

OS —> Set up —> Switch to process A —> Timer interrupt triggers —> Hardware switches to OS —> OS runs timer interrupt handler —> OS decided what to do next