Week 10.a. CS 5600 11/09 2021 On the board ------------ 1. Last time 2. page thrashing & mmap 3. I/O architecture ------------------------------------------------------- Admin: - Lab3: --introduce the overall picture --what is a KV-store? put(key, value) get(key) -> value --a monitor doesn't have to have condition variable. [note: c.v. is used for synchronization scheduling] --------- 1. Last time -- virtual memory: VA => PA --paging: VPN => PPN "offset" doesn't change --very useful -- how to achieve this? -- OS + hardware (MMU, inside CPU) -- OS configures (%cr3, page table entries) -- hardware executes (waling page tables) -- x86-64 paging -- many details -- 4-level page tables, as a tree -- PTE: PPN + bits -- TLBs -- page faults -- two types: not present & violating permissions -- page fault handler (another case of OS configures and hardware executes) -- very versatile -- the most classic usage: overcommitting memory 2. page thrashing & mmap A. Thrashing [The points below apply to any caching system, but for the sake of concreteness, let's assume that we're talking about page replacement in particular.] What is thrashing? Processes require more memory than system has Specifically, each time a page is brought in, another page, whose contents will soon be referenced, is thrown out Example: --one program touches 50 pages (each equally likely); only have 40 physical page frames --If we have enough physical pages, 100ns/ref --If we have too few physical pages, assume every 5th reference leads to a page fault --4refs x 100ns and 1 page fault x 1ms for SSD I/O --this gets us 5 refs per (1ms + 400ns) ~ 0.2ms/ref = 2,000x slowdown!!! --What we wanted: virtual memory the size of disk with access time the speed of physical memory --What we have here: memory with access time roughly of disk (0.2 ms/mem_ref compare to 1 ms/disk_access) As stated earlier, this concept is much larger than OSes: need to pay attention to the slow case if it's really slow and common enough to matter. Reasons/cases: (1) process doesn't reuse memory (or has no temporal locality) (2) process reuses memory but the memory that is absorbing most of the accesses doesn't fit. (3) individually, all processes fit, but too much for the system what do we do? --well, in the first two reasons above, there's nothing you can do, other than restructuring your computation or buying memory (e.g., expensive hardware that keeps entire customer database in RAM) --in the third case, can and must shed load. how? two approaches: a. working set b. page fault frequency a. working set --only run a set of processes s.t. the union of their working sets fit in memory --definition of working set (short version): the pages a process has touched over some trailing window of time b. page fault frequency --track the metric (# page faults/instructions executed) --if that thing rises above a threshold, and there is not enough memory on the system, swap out the process B. mmap, continued - idea: mapping an opened file to a region of my virtual memory [draw the figure in handout week9.b] - usages: - reading big files. map the whole thing, rely on the paging mechanism to bring the needed pieces into memory as necessary - shared data structures, when flag is MAP_SHARED - file-based data structures: - load data from file, update it, write it back - this is implemented entirely with loads/stores Question: how does the OS ensure that it's only writing back modified pages? [answer: dirty bit in PTE] --how's mmap implemented?! (answer: through virtual memory, with the VA being addr [or whatever the kernel selects] and the PA being what? answer: the physical address storing the given page in the kernel's managed pages, called buffer cache). 3. I/O architecture general: [draw picture: CPU, Mem, I/O, connected to BUS] --lots of details. --fun to play with. --registers that do different things when read vs. written. [draw some registers in devices, with status and data] CPU/device interaction (can think of this as kernel/device interaction, since user-level processes classically do not interact with devices directly. A. Mechanics of communication (a) Port-mapped I/O (PMIO) explicit I/O instructions outb, inb, outw, inw examples: (i) reading keyboard input. see handout keyboard_readc(); --I/O ports (PS/2): IO Port Access Type Purpose 0x60 Read/Write Data Port 0x64 Read Status Register 0x64 Write Command Register [https://wiki.osdev.org/%228042%22_PS/2_Controller] --keyboard keycode --handout uses "Scan Code Set 1" --differentiate "pressed" and "released" by the most significant bit: 0x1E: A pressed 0x9E: A released (notice: the difference is 0x80, namely binary: b10000000) Question: how many keys can be mapped to the key code? [answer: 128, because a key code is 1B, indicating 256 (2^8) key code; and each key has pressed and released; making it 128 keys.] --more keys? a mode change: --two bytes received, starting with 0xE0 --a lot of multimedia keys, like volume up/down --see "Scan Code Set 1" for more details (link below) [https://wiki.osdev.org/PS/2_Keyboard#Scan_Code_Set_1] (ii) setting blinking cursor. see handout console_show_cursor(); (b) memory-mapped I/O (MMIO) physical address space is mostly ordinary RAM low-memory addresses (<1MB), sometimes called "DOS compatibility memory", actually refer to other things. [see handout panel 2.a] You as a programmer read/write from these addresses using loads and stores. But they aren't "real" loads and stores to memory. They turn into other things: read device registers, send instructions, read/write device memory, etc. --interface is the same as interface to memory (load/store) --but does not behave like memory + Reads and writes can have "side effects" + Read results can change due to external events Example: writing to VGA or CGA memory makes things appear on the screen. See handout (last panel 2.b): console_putc() To avoid confusion: this is not the same thing as virtual memory. this is talking about the *physical* address. --> is this an abstraction that the OS provides to others or an abstraction that the hardware is providing to the OS? [the latter] [Acknowledgments: Mike Walfish, David Mazieres, Mike Dahlin, Brad Karp]