CS作业代写 CS162 © UCB Spring 2022

Recall: Demand Paging Cost Model
• Since Demand Paging like caching, can compute average access time! (“Effective Access Time”)
– EAT = Hit Rate x HitTime + Miss Rate x MissTime
– EAT = Hit Time + Miss Rate x Miss Penalty • Example:

– Memory access time = 200 nanoseconds
– Average page-fault service time = 8 milliseconds
– Suppose p = Probability of miss, 1-p = Probably of hit – Then, we can compute EAT as follows:
EAT = 200ns + p x 8 ms
= 200ns + p x 8,000,000ns
If one access out of 1,000 causes a page fault, then EAT = 8.2 μs: – This is a slowdown by a factor of 40!
What if want slowdown by less than 10%? – EAT < 200ns x 1.1 ⇒ p < 2.5 x 10-6 – This is about 1 page fault in 400,000! Joseph & Kubiatowicz CS162 © UCB Spring 2022 Recall: Clock Algorithm (Not Recently Used) Set of all pages in Memory Single Clock Hand: Advances only on page fault! Check for pages not used recently Mark pages as not used recently • Clock Algorithm: Arrange physical pages in circle with single clock hand – Approximate LRU (approximation to approximation to MIN) – Replace an old page, not the oldest page • Details: – Hardware “use” bit per physical page (called “accessed” in Intel architecture): » Hardware sets use bit on each reference » If use bit isn’t set, means not referenced in a long time » Some hardware sets use bit in the TLB; must be copied back to page TLB entry gets replaced – On page fault: » Advance clock hand (not real time) » Check use bit: 1→ used recently; clear and leave alone 0→ selected candidate for replacement Joseph & Kubiatowicz CS162 © UCB Spring 2022 Recall: Meaning of PTE bits • Which bits of a PTE entry are useful to us for the Clock Algorithm? Remember Intel PTE: Page Frame Number (Physical Page Number) – The “Present” bit (called “Valid” elsewhere): » P==0: Page is invalid and a reference will cause page fault » P==1: Page frame number is valid and MMU is allowed to proceed with translation – The “Writable” bit (could have opposite sense and be called “Read-only”): » W==0: Page is read-only and cannot be written. » W==1: Page can be written – The “Accessed” bit (called “Use” elsewhere): » A==0: Page has not been accessed (or used) since last time software set A→0 » A==1: Page has been accessed (or used) since last time software set A→0 – The “Dirty” bit (called “Modified” elsewhere): » D==0: Page has not been modified (written) since PTE was loaded » D==1: Page has changed since PTE was loaded 31-12 11-9 876543210 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Recall: Second- Algorithm (VAX/VMS) Directly Mapped Pages Marked: RW List: FIFO Page-in From disk LRU victim Marked: Invalid List: LRU SC Victims • Split memory in two:Active list (RW), SC list (Invalid) • Access pages in Active list at full speed • Otherwise, Page Fault – Always move overflow page from end of Active list to front of Second-chance list (SC) and mark invalid – Desired Page On SC List: move to front of Active list, mark RW – Not on SC list: page in to front of Active list, mark RW; page out LRU victim at end of SC list Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.4 Set of all pages in Memory Single Clock Hand: Advances as needed to keep freelist full (“background”) Free Pages For Processes • Keep set of free pages ready for use in demand paging – Freelist filled in background by Clock algorithm or other technique (“Pageout demon”) – Dirty pages start copying back to disk when enter list • Like VAX second-chance list – If page needed before reused, just return to active set • Advantage: faster for page fault – Can always use page (or pages) immediately on fault 3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.5 Reverse Page Mapping (Sometimes called “Coremap”) • When evicting a page frame, how to know which PTEs to invalidate? – Hard in the presence of shared pages (forked processes, shared memory, ...) • Reverse mapping mechanism must be very fast – Must hunt down all page tables pointing at given page frame when freeing a page – Must hunt down all PTEs when seeing if pages “active” • Implementation options: – For every page descriptor, keep linked list of page table entries that point to it » Management nightmare – expensive – Linux: Object-based reverse mapping » Link together memory region descriptors instead (much coarser granularity) 3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.6 Allocation of Page Frames (Memory Pages) • How do we allocate memory among different processes? – Does every process get the same fraction of memory? Different fractions? – Should we completely swap some processes out of memory? • Each process needs minimum number of pages – Want to make sure that all processes that are loaded into memory can make forward progress – Example: IBM 370 – 6 pages to handle SS MOVE instruction: » instruction is 6 bytes, might span 2 pages » 2 pages to handle from » 2 pages to handle to • Possible Replacement Scopes: – Global replacement – process selects replacement frame from set of all frames; one process can take a frame from another – Local replacement – each process selects from only its own set of allocated frames Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.7 Fixed/Priority Allocation 3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.8 Page-Fault Frequency Allocation • Can we reduce Capacity misses by dynamically changing the number of pages/application? • Establish “acceptable” page-fault rate – If actual rate too low, process loses frame – If actual rate too high, process gains frame • Question:What if we just don’t have enough memory? Joseph & Kubiatowicz CS162 © UCB Spring 2022 • If a process does not have “enough” pages, the page-fault rate is very high. This leads to: – low CPU utilization – operating system spends most of its time swapping to disk • Thrashing ≡ a process is busy swapping pages in and out with little or no actual progress • Questions: – How do we detect Thrashing? – What is best response to Thrashing? 3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.10 Locality In A Memory-Reference Pattern • Program Memory Access Patterns have temporal and spatial locality – Group of Pages accessed along a given time slice called the “Working Set” – Working Set defines minimum number of pages for process to behave well • Not enough memory for Working Set ⇒ Thrashing – Better to swap out process? 3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.11 Working-Set Model Δ ≡ working-set window ≡ fixed number of page references – Example: 10,000 instructions WSi (working set of Process Pi) = total set of pages referenced in the most recent Δ (varies in time) – if Δ too small will not encompass entire locality – if Δ too large will encompass several localities – if Δ = ∞ ⇒ will encompass entire program D = Σ|WSi| ≡ total demand frames if D > m ⇒Thrashing
– Policy: if D > m, then suspend/swap out processes – This can improve overall system behavior by a lot!
Joseph & Kubiatowicz CS162 © UCB Spring 2022

What about Compulsory Misses?
• Recall that compulsory misses are misses that occur the first time that a page is seen
– Pages that are touched for the first time
– Pages that are touched after process is swapped out/swapped back in
• Clustering:
– On a page-fault, bring in multiple pages “around” the faulting page
– Since efficiency of disk reads increases with sequential reads, makes sense to read several sequential pages
• Working Set Tracking:
– Use algorithm to try to track working set of application – When swapping process back in, swap in working set
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Linux Memory Details?
Memory management in Linux considerably more complex than the examples we have been discussing
Memory Zones: physical memory categories
– ZONE_DMA: < 16MB memory, DMAable on ISA bus – ZONE_NORMAL: 16MB → 896MB (mapped at 0xC0000000) – ZONE_HIGHMEM: Everything else (> 896MB)
Each zone has 1 freelist, 2 LRU lists (Active/Inactive)
Many different types of allocation
– SLAB allocators, per-page allocators, mapped/unmapped
Many different types of allocated memory:
– Anonymous memory (not backed by a file, heap/stack) – Mapped memory (backed by a file)
Allocation priorities
– Is blocking allowed/etc
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Linux Virtual memory map (Pre-Meltdown)
Kernel Addresses
Empty Space
User Addresses
Kernel Addresses
User Addresses
0xFFFFFFFF
Physical 0xC0000000
0xFFFFFFFFFFFFFFFF
64 TiB Physical
0xFFFF800000000000 “Canonical Hole”
0x00007FFFFFFFFFFF
0x00000000
32-Bit Virtual Address Space
0x0000000000000000
64-Bit Virtual Address Space
Joseph & Kubiatowicz CS162 © UCB Spring 2022
3GBTotal 1GB
128TiB 128TiB

Pre-Meltdown Virtual Map (Details)
• Kernel memory not generally visible to user
– Exception: special VDSO (virtual dynamically linked shared objects) facility that maps kernel code into user space to aid in system calls (and to provide certain actual system calls such as gettimeofday())
• Every physical page described by a “page” structure – Collected together in lower physical memory
– Can be accessed in kernel virtual space
– Linked together in various “LRU” lists
• For 32-bit virtual memory architectures:
– When physical memory < 896MB » All physical memory mapped at 0xC0000000 – When physical memory >= 896MB
» Not all physical memory mapped in kernel space all the time » Can be temporarily mapped with addresses > 0xCC000000
• For 64-bit virtual memory architectures:
– All physical memory mapped above 0xFFFF800000000000
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Post Meltdown Memory Map
• Meltdown flaw (2018, Intel x86, IBM Power,ARM)
– Exploit speculative execution to observe contents of kernel memory
1: // Set up side channel (array flushed from cache)
2: uchar array[256 * 4096];
3: flush(array); // Make sure array out of cache
4: try { // … catch and ignore SIGSEGV (illegal access)
5: uchar result = *(uchar *)kernel_address; // Try access!
6: uchar dummy = array[result * 4096]; // leak info!
7: } catch(){;} // Could use signal() and setjmp/longjmp
8: // scan through 256 array slots to determine which loaded
– Some details:
» Reason we skip 4096 for each value: avoid hardware cache prefetch
» Note that value detected by fact that one cache line is loaded
» Catch and ignore page fault: set signal handler for SIGSEGV, can use setjump/longjmp….
• Patch: Need different page tables for user and kernel
– Without PCID tag in TLB, flush TLB twice on syscall (800% overhead!)
– Need at least Linux v 4.14 which utilizes PCID tag in new hardware to avoid flushing when change address space
• Fix: better hardware without timing side-channels – Will be coming, but still in works
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.17

Recall: Five Components of a Computer
Diagram from “Computer Organization and Design” by Patterson and Hennessy
3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.18

Requirements of I/O
• So far in CS 162, we have studied:
– Abstractions: the APIs provided by the OS to applications running in a process – Synchronization/Scheduling: How to manage the CPU
• What about I/O?
– Without I/O, computers are useless (disembodied brains?)
– But… thousands of devices, each slightly different
» How can we standardize the interfaces to these devices?
– Devices unreliable: media failures and transmission errors » How can we make them reliable???
– Devices unpredictable and/or slow
» How can we manage them if we don’t know what they will do or how they will perform?
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.19

Recall: OS Basics: I/O
Process 1 Process 2 Process 3 OS Hardware
Virtualization
Protection Boundary
OS provides common services in form of I/O
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recall: Range of Timescales
Jeff Dean: “Numbers Everyone Should Know”
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Example: Device Transfer Rates in Mb/s (Sun Enterprise 6000)
• Device rates vary over 12 orders of magnitude!!!
• System must be able to handle this wide range
– Better not have high overhead/byte for fast devices
– Better not waste time waiting for slow devices
Joseph & Kubiatowicz CS162 © UCB Spring 2022

In a Picture
Read / Write
Secondary Storage
I/O Controlle
interrupts
Read / Write
L3 Cac he (sh are d)
Main Memory (DRAM)
DMA transfer
Secondary Storage
hL e Core1e 2
• Processors accesses them by reading and writing IO registers as if they were memory
– Write commands and arguments, read status and results
• I/O devices you recognize are supported by I/O Controllers
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Modern I/O Systems
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.24

What’s a bus?
Common set of wires for communication among hardware devices plus protocols for carrying out data transfer transactions
– Operations: e.g., Read,Write
– Control lines,Address lines, Data lines – Typically multiple devices
Protocol: initiator requests access, arbitration to grant, identification of recipient, handshake to convey address, length, data
Very high BW close to processor (wide, fast, and inflexible), low BW with high flexibility out in I/O subsystem
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.25

Why a Bus?
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.26

PCI Bus Evolution
• PCI started life out as a bus
• But a parallel bus has many limitations
– Multiplexing address/data for many requests
– Slowest devices must be able to tell what’s happening (e.g., for arbitration) – Bus speed is set to that of the slowest device
Joseph & Kubiatowicz CS162 © UCB Spring 2022

PCI Express “Bus”
No longer a parallel bus
Really a collection of fast serial channels or “lanes”
Devices can use as many as they need to achieve a desired bandwidth Slow devices don’t have to share with fast ones
One of the successes of device abstraction in Linux was the ability to migrate from PCI to PCI Express
– The physical interconnect changed completely, but the old API still worked
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Example: PCI Architecture
Memory CPU Bus
Host Bridge
ISA Bridge
PCI Bridge
PCI #0 PCI #1
Legacy Devices
Joseph & Kubiatowicz CS162 © UCB Spring 2022
ISA Controller
USB Controller
SATA Controller

How does the Processor Talk to the Device?
Processor Memory Bus
Bus Bus Adapt Adapt
Other Devices
Bus Interfac
Registers (port 0x20)
Addressabl e
Memory and/or
Queues Memory Mapped
Device Controller
Hardware Controller
write contr
Region: 0x8f008020
Joseph & Kubiatowicz CS162 © UCB Spring 2022
• CPU interacts with a Controller
– Contains a set of registers that can be read and written – May contain memory for request queues, etc.
• Processor accesses registers in two ways:
– Port-Mapped I/O: in/out instructions
» Example from the Intel architecture: out 0x21,AL
– Memory-mapped I/O: load/store instructions
» Registers/memory appear in physical address space » I/O accomplished with load and store instructions
Interrupt Request
Address + Data
Regular Memory
Interrupt Controller

Port-Mapped I/O in Pintos Speaker Driver
Pintos: devices/speaker.c
Pintos: threads/io.h
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Example: Memory-Mapped Display Controller
• Memory-Mapped:
– Hardware maps control registers and display memory into physical address space
» Addresses set by HW jumpers or at boot time
– Simply writing to display memory (also called the “frame buffer”) changes image on screen
» Addr: 0x8000F000 — 0x8000FFFF
– Writing graphics description to cmd queue
» Say enter a set of triangles describing some scene » Addr: 0x80010000 — 0x8001FFFF
– Writing to the command register may cause on-board graphics hardware to do something
» Say render the above scene » Addr:0x0007F004
• Can protect with address translation
0x80020000
0x80010000
0x8000F000
0x0007F004 0x0007F000
Graphics Comman
Display Memory
Physical Address Space
3/29/22 Joseph & Kubiatowicz CS162 © UCB Spring 2022

Chip-scale Features of 2015 x86 (Sky Lake)
• Significant pieces:
– Four OOO cores with deeper buffers
» Intel MPX (Memory Protection Extensions) » Intel SGX (Software Guard Extensions)
» Issue up to 6 μ-ops/cycle
– GPU, System Agent (Mem, Fast I/O)
– Large shared L3 cache with on-chip ring bus » 2 MB/core instead of 1.5 MB/core
» High-BW access to L3 Cache
• Integrated I/O
– Integrated memory controller (IMC) » Two independent channels of DRAM
– High-speed PCI-Express (for Graphics cards)
– Direct Media Interface (DMI) Connection to PCH (Platform Control Hub)
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.34

Sky Lake I/O: PCH
Sky Lake System Configuration
• Platform Controller Hub
– Connected to processor with proprietary bus
» Direct Media Interface • Types of I/O on PCH:
– USB, Ethernet
– Thunderbolt 3
– Audio, BIOS support
– More PCI Express (lower speed than on Processor)
– SATA (for Disks)
Joseph & Kubiatowicz CS162 © UCB Spring 2022 Lec 17.35

Operational Parameters for I/O
• Data granularity: Byte vs. Block
– Some devices provide single byte at a time (e.g., keyboard) – Others provide whole blocks (e.g., disks, networks, etc.)
• Access pattern: Sequential vs. Random
– Some devices must be accessed sequentially (e.g., tape)
– Others can be accessed “randomly” (e.g., disk, cd, etc.) » Fixed overhead to start transfers
– Some devices require continual monitoring
– Others generate interrupts when they need service
• Transfer Mechanism: Programmed IO and DMA
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Transferring Data To/From Controller
• Programmed I/O:
– Each byte transferred via processor in/out or load/store
– Pro: Simple hardware, easy to program
– Con: Consumes processor cycles proportional to data size
• Direct Memory Access:
– Give controller access to memory bus
– Ask it to transfer
data blocks to/from memory directly
• Sample interaction with DMA controller (from OSC book):
Joseph & Kubiatowicz CS162 © UCB Spring 2022

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts