Virtual memory * Basic virtual memory Example h/w system: 12-bit virtual address and 12-bit physical address. Consider the following snippet of assembly mov $0x02e, %rcx mov (%rcx), %rbx The 12-bit address 0x02e is a virtual address (VA) CPU---VA---> MMU ---PA--->Memory (MMU usually reside on the CPU chip) Virtual address space ____ 0xfff |____| |____| | | 0x000 |____| Physical address space (1KB memory) 0x3ff _____ |_____| | | 0x000 |_____| Suppose Page size is 16 bytes How many pages are there in the VA space? 2^12/2^4 = 2^8 = 256 pages What's the address of the first virtual page? 0x000 What's the address of the second virtual page? 0x010 ... 0x020 What's the address of the first physical page? ... Suppose virtual page 0x020 is mapped to physical page 0x010 Then what's VA 0x02e mapped to? 12-bit VA |_____VPN______|___VPO___| 8-bit 4-bit |_____PPN_____ |___PPO___| One-level page table. How many entries are there from VPN to PPN? Every VPN should have its own entry ____________ 00 |___________| 01 |___________| 02 |___________| ... ff |___________| Draw MMU performing VA lookup * Multi-level page table One level page table for x-86 64-bit, how many PTE? 48-bit VA, 4K page size In our example, suppose 256 page table entries are too much Organize into a two-level page table 16 page tables each with 16 PTE entries Draw one page table pointing to 16 second-level page tables Given an address 02e, which of the second-level page tables should MMU lookup? |_____0____|____2____|____e___| 4-bit 4-bit 4-bit Why does multi-level page table save space? * OS, processes VM is managed by OS What is OS? Draw picture Chrome, rklab, gcc, __________________ |____ OS _______| |_____h/w________| OS: a layer of software between app and h/w two purposes: 1) hides (messy) details of h/w 2) manages resources among many running user programs OS' concrete jobs: * scheduling (illusion of excluse use of CPU) * VM management (illusion of excluse use of memory) * file system, networking, other I/O Process: an instance of a running program C file ----gcc---> binary executable ----./a.out----> process ---ctrl-c---> process killed Each process corresponds to some state in OS process_id state (runntable, blocked etc.) user id open files rip other saved registers VM structure called task_struct in Linux Only OS should be allowed to modify OS data structure Privileged vs. unprivileged mode of execution this is a h/w primitive OS runs in privileged mode (can mess with h/w) user processes run in unprivileged mode (cannot mess with OS data structure, h/w) How to get into privileged mode? 1. exception (e.g. divide by zero, access memory not allowed according to PTE) 2. traps (user programs asks for kernel assistance) 3. interrupt (timer, or device events such as packet arrival, keyboard press) How to get out of privileged mode? special h/w instruction (iret) return to where the user program was not necessarily the same program, may context-switch to a different one Traps are used to implement syscalls (syscall is doing function call invoking some kernel functions) Each syscall has a number 0 read 1 write 2 open 3 close ... 57 fork 59 execve 60 exit 62 kill user code kernel code | | | syscall --------------------> | open the requested file <-------------------- next | | Exceptions are also when kernel takes control | | |-----h/w exception-------> check process vm data structure, fetch page from disk | <------------------------ | |