Operating Systems 2017F Lecture 10
Notes
Mmap
From Man Mmap: Mapping will be created at nearby page boundary
What is page/paging? Virtual Memory Every process gets its own "memory map" meaning it has: It's own range of addresses For example, Address 2000 is different in each process
Computer hardware is accessed by memory addresses (RAM is accessed by PHYSICAL addresses - every bit of RAM has a unique address) Processes access memory using VIRTUAL addresses
Need a mechanism to translate virtual to physical addresses *on every memory access by a process* (code and data)
Virtual address for PID 4512 -> physical address 512241 (they are different addresses that need to be mapped fast because this limits speed of all completion)
The OS kernel provides information through which the Hardware performs the mapping
When do mappings get updated? When the CPU (core) switches from running one process to the next
What occurs when a virtual address has no corresponding physical address for the process? -> You get segfault/similar error
What is mmap? Mmap is a tool to handle virtual memory map of a process: -> virtual address range corresponds to contents of a file rather than physical RAM -> You can use it to get RAM
Why is it wrong to make all virtual addresses correspond to some physical RAM address? - Revoke access - We are limited by how much RAM we have; eve if use swapping (pretend disk is RAM; even SSD's are slower than RAM!)
Memory Allocation
Memory allocation challenges: Need contiguous address ranges for parts of data structures (arrays) You can't move a data structure once it has been allocated (easily) -> pointers will be invalid
"-" not allocated
'*" allocated
****----*****------*********----
Want to allocate ******** While there is room for number of slots it will not be contiguous (This causes external fragmentation) -> think of fitting furniture in your room by rearranging everything to the point where you cannot enter the room This arises when you have variable sized allocation so to fix this use fixed size allocations (but now you are wasting storage)
Internal fragmentation: space you waste in an allocation (using a 4K file for a 1 byte of data so you waste 1 byte - 4k of data External fragmentation: See above example
It is generally preferable to have internal fragmentation over external fragmentation: All low-level alloctions are in fixed sized units *that can be placed anywhere* How to keep this from limiting the size of arrays "virtualizing" the indexing (addresses)
With both disk and memory, low-level storage is allocated in fixed_sized chunks. In memory it is called a page. On disk, a block.
Sizes are always power of 2 because indexes have to be stored in a fixed number of bits. Because indexes have to be stored in a fixed number of bits This is why we use hexadecimal or octal, not decimal to refer to memory indexes (addresses)
Each hexadecimal digit maps to 4 bits Octal digit maps to 3 bits Decimal digits map to less than 4 bits
Memory indexes are in bits, so use something that is convenient for bits
-*---*** 01234567 <-- "physical"
Create a "mapping": 0->0 1->4 2->1 3->2
****
01234567 <-- "virtual"
Array is range 0-3 So when we do a[1] in virtual space, we get contents of 4
Process virtual addresses are contiguous, physical memory storage isn't at the boundary of allocation
You would need a very big table for mapping every byte in memory to another byte
Typically table maps 4K or more at a time (Power of 2)
32 bit addresses
8bits, 2^8 = 256 2^12 = 4096, which is 4K
Allocate in 4k units (pages) - 12 bits of address No contiguous storage in physical memory for anything larger than 4K.
Fragmentation in upper 20 bits
Upper 20 bits: where to put the page Lower 12 bits: where in the page
I need a data structure that can map 20 bits to 20 bits with this, I map 20 upper bits and copy the lwoer 12 bits from virtual to physical
Lower 12 bits is a page offset Upper 20 bits is the page number
Page -> frame mapping (Frames are RAM, pages are virtual)
I have to store the page to frame mapping inside pages and I cannot have them be contiguous
We use page table (It's similar to a tree)
### ### ### ###
- ****** ****** ******
A page is 4k Every address is 32 bits (4 bytes) You can fit 1024 "pointers" into a page -> that is 10 bits
If I only had 4 megabytes of memory, I just need a page table that can fit in one page
If I want more, I have a page that points to pages 1 page: 1024 pointers each referring to a page Up to (2^10)=1,024 pages: each of those pages has 1024 pointers! Up to (2^20) = 1,048,576 pages: Each of those has 4096 bytes of data
Need 10 bits for offwset in page directory 10 bits for offset in page table 12 bits for offset in data page 32 bits total
DO NOT NEED TO DO ADDRESS CALCULATIONS BUT YOU SHOULD UNDERSTAND THE BASIC CONCEPTS