CS6456: Graduate Operating Systems Brad Campbell [email protected] https://www.cs.virginia.edu/~bjc8c/class/cs6456-f19/

CS6456: Graduate Operating Systems Brad Campbell  bradjc@virginia.edu https://www.cs.virginia.edu/~bjc8c/class/cs6456-f19/

CS6456: Graduate Operating Systems Brad Campbell [email protected] https://www.cs.virginia.edu/~bjc8c/class/cs6456-f19/ Slides modified from CS162 at UCB 1 Recall: What is an OS? Referee Resource sharing, protection, isolation Illusionist: clean, easy to use abstractions Infinite memory, dedicated machine Higher level objects: files, users, messages Masking limitations, virtualization Glue: Common Services

Storage Window system Networking Authorization 2 Recall: Virtual Machines Definition: Software emulation of abstract machine Programs believe they own the machine Simulated "hardware" has the features we want Two types: 1. Process VM: Run a single program in the VM, e.g. an OS 2. System VM: Run entire OS & its apps in the VM, e.g. Virtualbox, VMWare, Xen 3

Recall: Protecting Processes Use two features offered by hardware: 1. Dual Mode Operation Processes run in user or kernel mode Some operations prohibited in user mode 2. Address Translation Each process has a distinct and isolated address space Hardware translates from virtual to physical addresses Policy: No program can read or write memory of another program or of the OS 4 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack

Address space (with translation) Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other 5 OS Bottom Line: Run Programs instructions foo.c Load &

Execute compiler data OS stack heap Memory editor Program Source int main() {; }

0xFFF Executable data a.out instructions Load instruction and data segments of executable file into memory Create stack and heap Transfer control to program Provide services to program 0x000 PC: registers

Processor While protecting OS and program 6 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack Address space (with translation) Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other

7 Threads of Control Definition: A single, unique execution context Program counter, registers, stack A thread is executing on a processor when it is resident in that processor's registers Registers hold the root state of the thread: The rest is "in memory" Including program counter the currently executing instruction Registers point to thread state in memory: Stack pointer to the top of the thread's (own) stack 8 Multiprogramming - Multiple Threads of Control

Thr d. 1 Thr d. 2 OS Thr d. n stack heap Static Data code stack heap Static Data code

stack heap Static Data code 9 Illusion of Multiple Processors vCPU1 vCPU2 vCPU3 vCPU1 vCPU2 Shared Memory vCPU3 vCPU1 vCPU2 Time Multiple threads: Multiplex hardware in time

Contents of virtual core (thread): Program counter, stack pointer Registers Where is it? On the real (physical) core, or Saved in memory called the Thread Control Block (TCB) 10 Very Simple Multiprogramming All vCPU's share non-CPU resources Memory, I/O Devices Each thread can read/write data of others Threads can overwrite OS functions Unusable? No. This approach is used in Embedded applications (but not all!) MacOS 1-9/Windows 3.1 (switch only with voluntary yield)

Windows 95-ME (switch with yield or timer) 11 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack Address space (with translation) Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other 12

Second OS Concept: Address Space Definition: Set of accessible addresses and the state associated with them 232 = ~4 billion on a 32-bit machine What happens when you read or write to an address? Perhaps nothing Perhaps acts like regular memory Perhaps causes I/O operation stack 0xFFF heap Static Data code 0x000

(Memory-mapped I/O) Crash Communicate with another program 13 Address Space: In a Picture 0xFFF stack PC: SP: heap Processor registers Static Data instructio

n Segment Code 0x000 14 Address Space Translation translato r ad dre ss ph y si rtu

a vi Processor 0x000 ca l la dd res s Program operates in an address space that is distinct from the physical memory space of the machine

Memory 0xFFF 15 Virtual Address Translation/Paging Gives every process the whole address range Breaks memory into pages (~4K chunks) Allows unallocated "holes" and other tricks 16 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack

Address space (with translation) Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other 17 The Process Definition: execution environment with restricted rights Address Space with One or More Threads Owns memory (address space) Owns file descriptors, file system context, Encapsulate one or more threads sharing process resources

Why processes? Protected from each other! OS Protected from them Tradeoff: protection vs. efficiency Threads more efficient than processes (more later) Application: one or more processes 18 Single and Multithreaded Processes Threads encapsulate concurrency: Active component Address spaces encapsulate protection: Passive part Keeps buggy program from trashing the system Why have multiple threads per address space?

19 Protection Why? Reliability: buggy programs only hurt themselves Security and privacy: trust programs less Fairness: enforce shares of disk, CPU Mechanisms: Address translation: address space only contains its own data Privileged instructions, registers Syscall processing (e.g., enforce file access rights) 20 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack Address space (with translation)

Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other 21 Dual Mode Operation: HW Support 1 bit of state (user/kernel mode bit) Always? Certain actions only permitted in kernel mode User->Kernel mode sets kernel mode, saves user PC Only transition to OS-designated addresses

OS can save the rest of the user state if necessary Kernel->User mode sets user mode, restores user PC 22 UNIX Structure 23 3 Types of UK Mode Switches System Call (syscall) "Function call" into the kernel Example: exit, read Kernel reads syscall id # and arguments from user registers Interrupt External asynchronous events: Timer, I/O

Trap or Exception Special event in process Protection violation (segfault), divide by zero All 3 are an implicit transfer of control 24 Where do mode transfers go? Cannot let user program specify (why?) Solution: Interrupt Vector interrupt number (i) Address and properties of each interrupt handler intrpHandler_i () {

} 25 Implementing Safe Kernel Mode Transfers Carefully constructed kernel code packs up the user process state and sets it aside Must handle weird/buggy/malicious user state Syscalls with null pointers Return instruction out of bounds User stack pointer out of bounds Should be impossible for buggy or malicious user program to cause the kernel to corrupt itself User program should not know interrupt has occurred (transparency) Can a user program find out? 26 The Kernel Stack Two-stack model

Each OS thread has kernel stack (located in kernel memory) plus user stack (located in user memory) Place to save user registers during interrupt 27 Before Interrupt 28 During Interrupt 29 How do we take interrupts safely? Interrupt vector Limited number of entry points into kernel

Kernel interrupt stack Handler works regardless of state of user code Interrupt masking Handler is non-blocking Atomic transfer of control Single instruction-like to change: Program counter Stack pointer Memory protection Kernel/user mode Transparent restartable execution

User program does not know interrupt occurred 30 Kernel System Call Handler Vector through well-defined syscall entry points! Table mapping system call number to handler Locate arguments In registers or on user (!) stack Copy arguments From user memory into kernel memory carefully checking locations! Protect kernel from malicious code evading checks Validate arguments Protect kernel from errors in user code Copy results back Into user memory carefully checking locations!

31 Four Fundamental OS Concepts Thread: Execution Context Program Counter, Registers, Execution Flags, Stack Address space (with translation) Program's view of memory is distinct from physical machine Process: an instance of a running program Address Space + One or more Threads Dual mode operation / Protection Only the system can access certain resources Combined with translation, isolates programs from each other 32 Putting It Together:

Mode Transfer & Translation Mode transfer should change address translation mapping Examples: Ignore base and bound in kernel mode Page tables with "kernel mode only" bits 33 OS Running Proc 1 code Proc Proc 2 n

0000 Static Data heap OS stack sysmode 1 code 1000 Static Data heap

uPC xxxx stack PC code regs 1100 3000 Static Data heap stack

3080 FFFF 34 About to Switch Proc 1 code Proc Proc 2 n 0000 Static Data heap

OS stack sysmode 1 code 1000 Static Data heap uPC 0001 stack PC

code regs 00FF Privileged Inst: set special registers 1100 3000 Static Data heap stack 3080

FFFF 35 User Code Running Proc 1 code Proc Proc 2 n 0000 Static Data heap

OS stack sysmode 0 code 1000 Static Data heap uPC xxxx stack PC code

regs 1100 3000 Static Data heap stack 3080 FFFF 36 Handling Interrupt Proc 1

code Proc Proc 2 n 0000 Static Data heap OS stack sysmode 1

code 1000 Static Data heap uPC 0000 1234 stack PC IntrpVector[i] code regs Save registers and set up system stack

00FF 1100 3000 Static Data heap stack 3080 FFFF 37 How do we switch between processes? We already have all the necessary machinery!

Just requires two mode transfers 38 Representing Processes: PCB Proc 1 code Proc Proc 2 n 0000 RTU Static Data

heap OS stack sysmode 1000 1100 0000 1234 regs 00FF 0 code Base 1000

0000 Static Data Bound 1100 FFFF heap uPC xxxxxx stack PC 0000 100 code 1000 1100

3000 Static Data heap stack 3080 FFFF 39 Process Control Block Kernel representation of each process Status (running, ready, blocked) Register state (if not running) Thread control block(s) Process ID Execution time

Memory translations Scheduler maintains a data structure of PCBs Scheduling algorithm: Which process should the OS run next? 40 Scheduler if ( readyProcesses(PCBs) ) { nextPCB = selectProcess(PCBs); run( nextPCB ); } else { run_idle_process(); } Scheduling: Mechanism for deciding which processes/threads receive the CPU Lots of different scheduling policies provide Fairness or Realtime guarantees or

Latency optimization or .. 41 Process Operations Processes need to manipulate other processes: Start a new process Exit Wait for another process to terminate Processes need to do various other tasks, e.g., I/O How? System calls 42 What does "syscall" really mean? Application programmers generally dont write syscalls directly Cant in C without inline assembly, etc. Instead, OS libraries do this on our behalf

43 OS Run-Time Library Proc 1 Proc Proc 2 n OS Appln login Window Manager

OS library OS library OS library OS 44 A Narrow Waist Compilers Word Processing Web Browsers Email

Databases Portable OS Library User Hardware Application / Service OS System Call Interface System Software Web Servers

Portable OS Kernel Platform support, Device Drivers x86 PowerPC ARM PCI Ethernet (1Gbs/10Gbs) 802.11 a/g/n/ac SCSIGraphicsThunderbolt 45 POSIX/Unix Portable Operating System Interface [X?] Defines Unix, derived from AT&T Unix Created to bring order to many Unix-derived OSs

Interface for application programmers (mostly) 46 pid.c #include #include #include #include int main(int argc, char *argv[]) { /* get current processs PID */ pid_t pid = getpid(); printf(My pid: %d\n, (int) pid); exit(0);

} 47 Process Management Syscalls: fork copy the current process exec change the program being run by the current process wait wait for a process to finish kill send a signal (interrupt-like notification) to another process sigaction set handlers for signals Lot of legacy here. Further reading: https://www.microsoft.com/en-us/research/uploads/prod/2019/ 04/fork-hotos19.pdf 48 Creating Processes

pid_t fork(); -- copy the current process New process has different pid Return value from fork(): pid (like an integer) When > 0: Running in (original) Parent process return value is pid of new child When = 0: Running in new Child process When < 0: Error! Must handle somehow Running in original process State of original process duplicated in both Parent and Child! Memory, File Descriptors (covered later), etc 49 What happens when we use fork?

Paren t code Child 0000 Static Data heap OS stack 1000 sysmode 1100

0000 1234 1 Base 1000 0000 Static Data Bound 1100 FFFF heap uPC 0000 regs

code stack PC 00FF code 3000 3080 0000 1234 regs 00FF 1000 1100

3000 Static Data heap stack 3080 FFFF 50 Example: fork1.c #include #include #include #include

int main(int argc, char *argv[]) { pid_t cpid, mypid; pid_t pid = getpid(); /* get current processes PID */ printf("Parent pid: %d\n", pid); cpid = fork(); if (cpid > 0) { /* Parent Process */ mypid = getpid(); printf("[%d] parent of [%d]\n", mypid, cpid); } else if (cpid == 0) { /* Child Process */ mypid = getpid(); printf("[%d] child\n", mypid); } else { perror("Fork failed");

} } 51 Process Management fork copy the current process exec change the program being run by the current process wait wait for a process to finish kill send a signal (interrupt-like notification) to another process sigaction set handlers for signals 52 fork2.c int status; pid_t tcpid; cpid = fork();

if (cpid > 0) { /* Parent Process */ mypid = getpid(); printf("[%d] parent of [%d]\n", mypid, cpid); tcpid = wait(&status); printf("[%d] bye %d(%d)\n", mypid, tcpid, status); } else if (cpid == 0) { /* Child Process */ mypid = getpid(); printf("[%d] child\n", mypid); } 53 Process Management fork copy the current process exec change the program being run by the current process wait wait for a process to finish kill send a signal (interrupt-like

notification) to another process sigaction set handlers for signals 54 fork3.c cpid = fork(); if (cpid > 0) { /* Parent Process */ tcpid = wait(&status); } else if (cpid == 0) { /* Child Process */ char *args[] = {ls, -l, NULL}; execv(/bin/ls, args); /* execv doesnt return when it works. So, if we got here, it failed! */ perror(execv); exit(1); }

55 Shell Job control system Allows user to create/manage applications to do tasks Users wrapper around process management functions Windows, OS X, Linux all have shells 56 Process Management 57 Process Management fork copy the current process exec change the program being run by the current process

wait wait for a process to finish kill send a signal (interrupt-like notification) to another process sigaction set handlers for signals 58 inf_loop.c #include #include #include #include #include void signal_callback_handler(int signum) {

printf(Caught signal!\n); exit(1); } int main() { struct sigaction sa; sa.sa_flags = 0; sigemptyset(&sa.sa_mask); sa.sa_handler = signal_callback_handler; sigaction(SIGINT, &sa, NULL); while (1) {} } 59 Common POSIX Signals SIGINT control-C SIGTERM default for kill shell command SIGSTP control-Z (default action: stop process) SIGKILL, SIGSTOP terminate/stop process Cant be changed with sigaction

Why? 60 Multiplexing Processes Snapshot of each process in its PCB Only one active at a time (per core) Give out CPU to different processes Scheduling Policy Decision Give out non-CPU resources Memory/IO Another policy decision Process Control Block 61

Context Switch Overhead! 62 Lifecycle of a Process As a process executes, it changes state: new: being created ready: waiting to run running: instructions executing on the CPU waiting: waiting for some event to occur (e.g., keypress) 63 terminated: finished execution Scheduling: All About Queues

PCBs move from queue to queue Scheduling: which order to remove from queue 64 Modern Processes: Multiple Threads Thread: execution stream within a process Used to be called "lightweight processes" Shares address space with other threads belonging to the same process Why separate concepts of threads and processes? Threads: Concurrency Processes: Protection 65 So does the OS schedule processes or threads? Usually it's threads (e.g., in Linux) One point to notice: switching threads vs.

switching processes incurs different costs: Switch threads: Save/restore registers Switch processes: Change active address space too! Expensive Disrupts caching 66 Thread vs. Process State Process-wide state: Memory contents (global variables, heap) I/O bookkeeping Thread-"private" state: CPU registers including program counter Execution stack Kept in Thread Control Block 67

Execution Stack Review A: tmp=1 ret=exit A(int tmp) { if (tmp<2) B(); B: ret=A+2 printf(tmp); C: ret=b+1 } A: tmp=2 ret=C+1 B() {

C(); Stack Pointer Stack Growth } C() { A(2); } Stack holds temporary results Used to implement recursion A(1); 68 Shared vs. Per-Thread State

69 Memory Footprint: Two Threads Two sets of CPU registers Two sets of Stacks Stack 1 Issues: How do we position stacks relative to each other? What maximum size should we choose for the stacks? What happens if threads violate this? How might you catch violations? Heap Address Space

Stack 2 Global Data Code 70 Threads Motivation Back to Jeff Dean's "Numbers everyone should know" Handle I/O in separate thread, avoid blocking other progress 71

Example for Threads Imagine the following program: main() { ReadLargeFile(pi.txt); RenderUserInterface(); } What is the behavior here? Still respond to user input While reading file in the background 72 Dispatch Loop Loop { RunThread(); ChooseNextThread(); SaveStateOfCPU(curTCB); LoadStateOfCPU(newTCB); }

Conceptually all the OS executes Infinite Loop When would we ever "exit?" Can we assume some thread is always ready? 73 Dispatch Loop Loop { RunThread(); ChooseNextThread(); SaveStateOfCPU(curTCB); LoadStateOfCPU(newTCB); } How to run a new thread? Load thread's registers into CPU Load its environment (address space, if in different

process) Jump to thread's PC How does dispatch loop get control again? Thread returns control voluntarily yield, I/O External events: thread is preempted 74 Voluntarily Giving Up Control I/O e.g. keypress Waiting for a signal from another thread Thread makes system call to wait Thread executes thread_yield() Relinquishes CPU but puts calling thread back on ready queue 75

Stack for Yielding Thread yield Trap to OS kernel_yield run_new_thread switch Stack growth ComputePI Cyan = User Stack; Red = Kernel Stack run_new_thread() { newThread = PickNewThread(); switch(curThread, newThread); ThreadHouseKeeping(); /* Do any cleanup */ } 76

The Context Switch Itself Switch(tCur,tNew) { /* Unload old thread */ TCB[tCur].regs.r7 = CPU.r7; TCB[tCur].regs.r0 = CPU.r0; TCB[tCur].regs.sp = CPU.sp; TCB[tCur].regs.retpc = CPU.retpc; /*return addr*/ /* Load and execute new thread */ CPU.r7 = TCB[tNew].regs.r7; CPU.r0 = TCB[tNew].regs.r0; CPU.sp = TCB[tNew].regs.sp; CPU.retpc = TCB[tNew].regs.retpc; return; /* Return to CPU.retpc */ } 77

Summary Variety of process management syscalls fork, exec, wait, kill, sigaction Process consists of two pieces 1. Address Space (Protection) 2. One or more threads (Concurrency) Scheduling: Threads move between queues Threads: multiple stacks per address space Context switch: Save/Restore registers, "return" from new thread's switch routine 78

Recently Viewed Presentations

  • UAlbany Green Scene - University at Albany, SUNY

    UAlbany Green Scene - University at Albany, SUNY

    These include: Fall energy campaign Empire Commons bill program Destination Green (Sustainable Transportation Day) Campus sustainability Day International Day of Climate Action (350.org) National Teach In on Climate change Recyclemania Earth Day Clean up day Give and Go ( formerly...
  • Industrial Biotechnology - Islamic University of Gaza

    Industrial Biotechnology - Islamic University of Gaza

    They function in development, sporulation, light emission, virulence, production of antibiotics, pigments and cyanide, plasmiddriven conjugation and competence for genetic transformation. ... fungi, where more secondary metabolites are produced by it than by any other. Most of the known ...
  • Noise Modeling of Sensors: The Allan Variance Method

    Noise Modeling of Sensors: The Allan Variance Method

    The January 1, 1801 , an Italian monk, Giuseppe Piazzi (1746-1846), discovered a faint, nomadic object through his telescope in Palermo. Piazzi watched the object for 41 days but then fell ill, and shortly thereafter the wandering star star strayed...
  • Speed Limits - Tmcec

    Speed Limits - Tmcec

    AUTHORITY OF MUNICIPALITY TO ALTER SPEED LIMITS. Section 545.356 of the Texas Transportation Code. Highway or part of the highway within the municipality (including a highway of the state highway system)
  • Abiotic vs. Biotic Factors - Lancaster High School

    Abiotic vs. Biotic Factors - Lancaster High School

    Abiotic vs. Biotic Factors . Another relationship in Ecosystems. What are the other relationships? What is an Ecosystem? The living and non-living components of an environment. But… What is living? What is non-living? Biotic Factors .
  • Down and Dirty Field Scale Analysis This is

    Down and Dirty Field Scale Analysis This is

    -Improper equipment sizing -Stimulation by- products -Incompatible waters -Natural, or induced, formation of asphaltenes (CO2flood) Figure 1 - Representative Water Analysis Indicating Scaling Tendencies . Table 4 Common Suspended Solids and their Probable Origins .
  • Untitled Presentation - VACLAV

    Untitled Presentation - VACLAV

    A comprehensive, up-to-date examination of the most important theory, concepts, methodological approaches, and applications in the burgeoning field of judgment and decision making (JDM) Emphasizes the growth of JDM applications with chapters devoted to medical decision making, decision making and...
  • Life Saving Rules - Z Energy

    Life Saving Rules - Z Energy

    The HSWA 2015 places a duty on Z as a PCBU to ensure, so far as is reasonably practicable, that work is completed without risks to the health and safety of any person. ... Section 3 - 6 - Contractor...