Operating Systems: Three Easy Pieces

What is operating system?

- Middleware between user programs and system hardware

- Manages hardware: CPU, main memory, IO, devices (disk, network card, mouse, keyboard, etc.)

What happens when you run a program?

- Compiler translate high level program into an executable (".c" to "a.out")

- the exe contains instructions that the CPU can understand, and data of the program (all numbered with addresses)

- Instructions run on CPU: hardware implements an instruction set architecture (ISA)

-CPU also consists of few registers, e.g.:

- Pointer to current instructions (program counter or PC)

- Operands of instructions, memory addresses.

So, What happens when you run a program?

To run an exe, CPU:

-Fetches instruction pointed at by PC from memory

-Loads data required by the instructions into registers

-Decodes and executes the instruction

-Stores results to memory

Most recently used instructions and data are in CPU caches for faster access

What does the OS do?

-OS manages program memory

-OS manages CPU

-OS manages external devices

OS manage CPU

- OS provides the process abstraction

- Each process has the illusion of having the complete CPU

-Timeshares CPU between processes

-Enables coordination between processes

OS manages memory

- OS manages the memory of the process: heap, stack, code, data, etc.

- Each process think it has a dedicated memory space for itself (virtual addresses).

- OS abstracts out the details of the actual placement in memory, translates from virtual addresses to actual physical addresses

OS manages devices

- OS has code to manage disk, network card, and other external devices: device drivers

-Device driver talks the language of the hardware devices

Persistent data

Organized as a filesystem on disk

Design goals of an OS

- Convenience, abstractions of hardware resources for user programs

-Efficiency of usage of CPU, memory, etc.

-Isolation between multiple processes

How a computer works?

- Fetch

- Decode

- Execute

OP

- Virtualize the resources (Virtual machine)

- Std library to apps

- Resource manager

procees

A running program

virtualizes CPU

OS timeshares CPU across multiple process

PID

A unique identifier to each process

(Process identification number)

Memory

- Code & dta (static)

- Stack and heap (dynamic)

CPU context

- Program counter

- Current operands

- Stack pointer

file descriptor

- Pointers to open files and devices

-> Stdin (0)

-> Stdout (1)

-> Stderr (2)

How does 0S create a process?

- Allocates memory & creates memory image

- Open basic files

-> STD IN, OUT, ERR

- Initializes CPU registers

->PC points to first instructions

States of a process

- Running: currently executing on CPU

- Ready: waiting to be scheduled

- Blocked: suspended, not ready to run

- New: being created, yet to run

- Dead: terminated

How the OS keep track of all this process?

- OS maintains a data structure (e.g. list) of all active processes

-Information about each process is stored in a process control block (PCB)

A process consists of instructions, and each

instruction can just do one of two things:

- use the CPU

- issue an IO (and wait for it to complete)

fork( )

System call is used in UNIX systems to create a new process.

the creator -> Parent

the newly created process -> child

the child process is a nearly identical copy of the parent

wait( )

System call allows a parent to wait for its child to complete execution

exec( )

family of system calls allows a child to break free from its similarity to its parent and execute an entirely new program

Concurrency

Conceptual term to a host of problems to arise and must be addressed, when working on many things at once

Persistency

Data lost in system memory

-thus we need hardware and software to be able to store data persistently

file system

software in the OS that usually manages the disk

Is the part of the OS in charge of managing persistent data

SJF

Shortest Job First

STCF

Shortest Time to Completion First

RR

Round- Robin

FIFO or FCFS

(First in First out) OR (First come First serve)

workload

set of processes running in the system

Turn around time

is the time interval from the time of arrival of a process to the time of the completion of the process.

response time

time from when the job arrives in a system to the first time it is scheduled

what we are trying to optimize (policies)?

-Maximize utilization -> fraction of time CPU is used

-Minimized avg TAT

-Minimize avg response time

-Fairness -> All process must be threat equally

-Minimize overhead:run process long enough to amortize cost of context switch

Scheduling Policies

- No preemptive

- Preemptive

job

process

Machine state

what a program can read or update when it is running at any given time

-MEMORY: components of machine state that compromise a process

-REGISTERS:

->PC (program count) or IP (instruction pointer)

->stack pointer

-> I/O (persistent storage device)

Process API

Calls programs

-create new process fork()

-destroy -> close or exit by themselves exit()

-Wait-> waiting interface wait()

-Miscellaneous control -> i.e. suspend a process and then resume it

-Status -> status inf. about process

Loading

Takes on-disk program and reads it into the address space of process

Process state

- the contents of memory in its address space

-the contents os CPU registers (including SP, PC, etc)

-Information about I/O

Process exists in one of many different states transitions a process from one of these states to other

-READY

-RUNNING

-BLOCKED

Process events

-scheduled

-descheduled

-waiting for I/O to complete

A process list

Contains information about all processes int the system. Each entry is found in what is sometimes called a process control block (PCB), which is really a structure that contains information about a specific process

PCB

Process Control Block

cache

common resource that is being shared by all process

every address generated by a user program is a virtual address.

The OS is just providing an illusion to each process, specifically that it has its own large and private memory; with some hardware help, the OS will turn these pretend virtual addresses into real physical addresses, and thus be able to locate the desired information.

buffer overflow

not allocating enough memory

dangling pointer

Sometimes a program will free memory before it is finished using it

memory leak

when you forget to free memory

double free

Programs also sometimes free memory more than once;

invalid frees

call of free() incorrectly.

address translation

technique for translating the virtual address into physical address

Limited Direct Execution (LDE)

Set of techniques to implement performance and control over implementation of virtualization machinery

User mode

A mode of the user interface to a router or switch in which the user can type only nondisruptive EXEC commands, generally just to look at the current status, but not to change any operational settings.

code that runs in user mode is restricted in what it can do.

applications dont have full access to hardware resources

kernel mode

An access mode for applications while they are running on the CPU that allows full access to all hardware devices and memory in the computer.

The OS runs in.

The OS has access to the full resources of the machine

System call

applications runs into user mode and use system call (An instruction that interrupts the program being executed) to trap into the kernel to request operating system services

privileged operation over kernel mode

special instructions from kernel mode to user mode

trap into the kernel mode and return-from-trap back to the user mode

Programs are also provided, instructions that allow the OS to tell the hardware where the trap table resides in memory

how does the trap know which code to run inside the OS

The kernel does so by setting up a trap table at boot time.

system call number

specify the exact system call

How can the OS regain control of the CPU so that it can switch between processes?

- cooperatively: system call

-forcefully: timer interrupt

scheduler

-> continue running the currently process

-> switch to a different one

kernel stack

user registers of the running process are implicitly saved by the hardware using kernel stack of that process

the CPU should support at least two modes of execution

- A restricted user mode

- A privileged (non-restricted) kernel mode.

trap instruction

-saves registers

-change hardware status to kernel mode

- jump into OS to a pre-specified destination: the trap-table

return-from-trap-instruction

when the OS is done handling system call or interrupt, it calls a special instruction -> return-from-trap and return to the user program

-Before returning to user mode, OS check if it must switch to another process

trap table

set up by the OS at boot time and make sure that they cannot be readily modified by user programs

timer interrupt

Once a program is running, the OS must use hardware mechanisms to ensure the user program does not run forever

context switch

A low-level technique to help the OS, during a timer interrupt or system call, might wish to switch from running the current process to a different once.

Memory hadrware Memory management (MMU)

calculated PA from VA:

Physical address = Virtual address + base

OS is not involved in every translation?

provided base / bound registers to MMU

What constitute a process?

- A unique PID

- Memory image

- Code & data (static)

- Stack and heap (dynamic)

- CPU context: registers

- Program Counter

- Current operands

- Stack pointer

-File descriptors

-Pointer to open files and devices

Information about each process is stored in a PCB

- Process identifier

- Process state

- Pointers to other related process ( parent)

- CPU context of the process (saved when the process is suspended)

- Pointers to memory locations

- Pointer to open files

what API does the OS provide to user programs?

API provided by OS is a set of system calls

How does a shell work?

- In a basic OS, the init process is created after initialization of hardware

-The init process spawns a shell like bash

-Shell reads user command, fork a child, execs the command executable, waits for it to finish, and reads next command

-Common commands like ls are all executables that are simply exec'ed by the shell

Trap Instruction execution

- Move CPU to higher privilege level

- Switch to kernel stack

- Save context (old PC, registers) on kernel stack

- Look up address in IDT, and jump to trap handler function in OS

Process Execution

- OS allocates memory and creates memory image

-Code and data

- Stack and heap

- Points CPU program counter to current instruction

- Other registers may store operands, return values etc.

- After setup, OS is out of the way and process executes directly on CPU.

Trap instructions is executed on hardware in following cases:

- System call(program needs OS services)

- Program fault (program does something illegal)

- Interrupt(external device needs attention of OS)

Saving context

Context (PC and other CPU registers) saved on the kernel stack in two different scenarios:

- When going from user mode to kernel mode user context is saved on kernel stack by the trap instruction

- Restore by return-from-trap

-During a context switch, kernel context of process A is saved on the kernel stack of A by the context switching code.

-Restores kernel context of process B

Address space

The number of distinct locations that may be referred to with the machine address. For most binary machines, it is equal to 2n, where n is the number of bits in the machine address.

virtual address space

The virtual storage assigned to a process.

Every process assumes it has access to a large space of memory => Code(and static data), Stack(used during function calls), Heap(dynamic allocations)

How is actual memory reached?

-Address translation from VA to PA

-CPU issues loads/stores to VA but memory hardware accesses PA

-OS allocates memory and tracks location of processes

-Translation done by memory hardware called(MMU) Memory Management Unit

Paging

- OS divides Vistual address space into fixed size pages, physical memory into frames

- To allocate memory, a page is mapped to a free physical frame

-Page table stores mappings from virtual page number to physical frame number for a process

-MMU has access to page tables, and uses it to translate VA to PA

Goals of memory virtualization

- Transparency: user programs should not be aware of the messy details

- Efficiency: minimize overhead and wastage in terms of memory space and access time

- Isolation and protection: user process should not be able to access anything outside its address space

Memory allocation system calls

Algorithms for efficient memory allocation and free space management

What is the address space of the OS?

- OS is not a separate process with its own address space

-Instead, OS code is part of the address space of every process

-A process sees OS as part of its code (e.g. library)

- Page tables map the OS addresses to OS code

How does the OS allocate memory?

- OS needs memory for its data structures

-For large allocations, OS allocates a page

- For smaller allocations, OS uses various memory allocation algorithms

Who performs address translation?

-OS tells hardware => base/bounds

-MMU calculates PA from VA

PA = VA + BASE

- MMU also checks if address is beyond bound

-OS is not involved in every translation

Role of hardware in translation

- CPU provides privileged mode of execution

- Instruction set has privileged instructions to set translation information (e.g. base / bounds)

-Hardware (MMU) uses this information to perform translation on every memory access

-MMU generates faults and traps to OS when access is illegal

Role of OS in translation

- OS maintains free list of memory

-Allocates space to process during creation (and when asked) and cleans up when done

-Maintains inf. of where space is allocated to each process (in PCB)

-Sets address translation inf. (e.g. base & bounds) in hardware

-Updates this inf. upon context switch

-Handles traps due to illegal memory access

External Fragmentation

small holes in memory left between segments

threading

running different tasks concurrently

Temporal locality:

If at one point a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future.

Spatial locality:

If a particular storage location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future.

blocking

if the thread that is currently holds the lock is delayed, then all others threads attempting to access the counter are also delayed.

deadlocks

threads may block each other in a cyclic fashion such that none evers make progress.

What is a thread ? IMPORTANT

A thread is a special process that shared the address space with the parent