Main memory and registers are the only storage the CPU can directly access.
The memory unit only sees a stream of addresses and read requests, or address + data and write requests.
Cycles:
We define logical address space with pairs of base and limit registers.
TODO Diagram
CPU must check that every user mode memory access is within the logical address space for that user.
TODO Diagram of hardware access protection (check address limits)
Checking if Address is Valid:
Physical Memory (RAM): Hardware structure consisting of a linear sequence of words that hold a program during execution.
Physical Address: Integer in range [0, n-1] that identifies a word in a RAM of size n. The address comprises a fixed number of bits.
Logical Address Space: Abstraction of physical memory.
Logical Address: Integer that identifies a word in logical address space.
Why?: This simplifies programming, and lets the operating system break up and rearrange (allocate) memory in efficient ways.
More on Program Transformation:
- Source: TODO
- Object: TODO
- Load: TODO
Relocation: Once a program is loaded in memory, we can move it around.
- Static Relocation: Bind all logical addresses to physical addresses prior to execution.
- Done at compile-time.
- Dynamic Relocation: Postpone binding of logical address to physical address until it is accessed during execution.
- Done at runtime.
Relocation can be done multiple times, before and during execution.
Static v. Dynamic: There is no room for expanding or shrinking in static relocation. In fact, you can’t even move it, as you’d need to change tons of addresses. Dynamic just means you change the
TODO Relocation may need to be given a parent section.
Relocation Register: Contains physical starting address of program/program component.
Recall — Most programs are three parts: Code, static data, and dynamic.
Single Relocation Register: The 3 components are a single one unit which occupies a contiguous area of memory.
TODO The other method is the one where we have one relocation register for each component (code, static data, dynamic).
Related to above.
TODO
TODO
External v. Internal Allocation:
- External: Happens when we allocate and deallocate memory contiguously, leaving holes.
- e.g., you have two 50kb holes that aren’t contiguous, but want to use 75kb.
- Internal: ???
First-fit: Allocate the first hole that is big enough.
Next-fit: Start each search at point of last allocation
Best-fit: Allocate smallest hole possible.
Worst-fit: Allocate biggest hole possible.
More on Best and Worst — Requires us to search the entire list (unless it’s already sorted)
(Bonus) Coalescing: Relocate things to make holes bigger.
50% Rule: If the probability of finding an exact match of a request approaches 0, one third of all memory partitions are holes and two thirsts are occupied.
If there is no big-enough hole, we can:
Swap: Temporarily take module out memory and store it the disk.
Compaction: Systematically shift modules (generally to one side) to create a larger hole.
Page Table: Translates logical to physical addresses.
Pages and Frames:
Remember — Frames and pages must have the exact same size due to 1:1 mapping.
- We can have a different number of each, but their sizes must match!
Why? — As previous seen, contiguous allocation requires us to find large empty spaces in the physical memory, which is very hard. And dealing with internal fragmentation is very expensive.
Address generated by CPU divided into two parts:
For a given logical address space 2^m and page size 2^n:
Q: An address consists of a 5-bit page number and 4-bit offset.
A:
Internal Fragmentation: The loss of usable memory space due to the mismatch between the page size and the size of a program, which creates a hole at the end of the program’s last page. Page Size: 2048 B Process Size: 72766 B 35 Pages + 1086 B Internal fragmentation of 2048 - 1086 = 965 B Worst-Case Fragmentation = 1 frame - 1 byte TODO I don’t get this at all.Example: Calculating internal fragmentation
Internal v. External Fragmentation: Internal fragmentation occurs when you allocate memory with page tables (caused by wasted memory on the last frame), external fragmentation occurs when you allocate memory contiguously.
Q: Consider a logical address space of 2048 pages with a 4KB page size, mapped onto a physical memory of 512 frames.
A:
Q: Assuming a 1KB page size, what are the page numbers and offsets for the following address references (provided as decimal numbers):
A:
All you need to do is divide each process by the page size to get number of pages entirely. Then the rest of the offset. ??? And then it takes up another page.
Background — So far we’ve learned memory allocation via (1) contiguous and (2) page table allocation.
The third approach treats programs are a collection of segments.
Segments: We must know the size and starting address of each.
- Main Program
- Procedure
- Function
- Method
- Object
- Local Variables, Global Variables
- Common Block
- Stack
- Symbol Table
- Arrays
Note — We have to know the size of the segment because the sizes are variable.
Array that keeps track of which segment resides in which area of physical memory.
On Segments — Segments are identified by a single number (segment number)
- With pure segmentation (no paging), a segment would occupy a contiguous area of physical memory and be the smallest unit of data for memory management.
TODO Copy diagram from slides, “Logical Address Space <–> Segment Table <–> Physical Memory” on “Segmentation”
Similar to paging, segmentation breaks each logical address into two components:
Example: Segment Table TODO
| Base | Limit |
|---|---|
Differences from Paging: This is nearly identical to paging, except:
^ TODO Basically in a page table all you do is copy patterns, but here we gotta add.
Now, let’s combine the benefits of both methods.
- Segmentation: Ability to create variable-size address spaces.
- Paging: Ability to place any page into any frame.
Logical addresses are three components: (s, p, w) (segment #, page #, offset)
Note — This is a space-time tradeoff. We need to use memory to store the segment table, page table, and physical memory.
TODO Copy Diagram 6.4.5 from slides
TODO isn’t this like a 2D matrix? like s[p[w]]?
TLB: Fast associative memory buffer that maintains recent translations of logical addesses to frames.
In Other Words — It’s a frame & page table cache.
Suppose we’ve previous mapped logical (s,p,w) \to physical (f,w) and have it cached.
If we then want to get (s,p,w'), all we have to do is calculate (f, w')
\boxed{ \text{EAT} = \text{TLB hit time} * \text{hit ratio} + \text{TLB miss time} * (1 - \text{hit ratio) } TODO Cleanup this formula?
Hit Ratio: Percentage of times a page number is found in the associative registers.
Q: Calculate EAT for hit ratio of 99% with 100ns memory access.
A:
\text{EAT} = 100 \times .99 + 200 \times .01 \\ = 101 \text{ns}
GAP (missed beginning of class) (TODO)
Demand Paging: Principle of loading a page into memory only when it’s needed.
Present Bit: Flag that indicates whether a page is residing in memory.
Page Fault: TODO
As virtural memory is much larger than physical memory… TODO
Page Replacement: TODO
Modified Bit: Flag that indicates TODO indicates if a page has been changed.
Recall how we needed three tables loaded in memory to do this.
TODO BASICALLY: Page the page table, because the page table is so large.
This changes access from s,p,w to s,p1,p2,w TODO cleanup
TODO this is about like limiting # of frames a process can have?
Reference String: Sequence of page numbers referenced by an executing program during a time interval. TODO what. its like used to compaire page replacement algorithms.
Simplest to implement. Selects the page that has been resident in memory the longest.
TODO Example of FIFO page replaceement (copy from slides)
Belady’s Anomaly: Adding more frames doesn’t always reduce page faults!
Why?: Algorithms that are not stack-based (e.g., FIFO, others) suffer from Belady’s Anomaly.
Selects page that won’t be referenced for the longest time in the future.
Usually used as a comparison.
TODO Example of Optimal page replacement (copy from slides)
Selects page that has not been referenced for the longest time.
Three Implementations:
Like optimal, LRU doesn’t suffer from Belady’s anomaly.
True LRU requires queue/stack/clock, which makes algorithm too inefficient.
Aside — Stack Algorithms: Algorithm for which it can be shown that the set of pages in memory for n frames is always a subset of the set of pages that would be in memory with n + 1 frames.
- In other words, when you make a new call, all the old ones are still a part of the deal (???)
- For LRU, the set of pages in memory would be the n most recently referenced pages. If the number of frames is increased, these n pages will still be the most recently referenced and so will still be in memory (ties into Second Chance).
Rather than maintain pages sorted in exact LRU order, pages are grouped (given a referenced bit), and the aging register is shift periodically to the right by 1 bit.
Algorithm is invoked TODO
Something to do with discarding the least-significant bit (this is all very efficient on the hardware). We are working at the level of bit shifts, but the simple pattern/behavior is efficient… TODO
tl;dr we roughly do LRU by not caring about exact order?
Coarse-grain approximation of LRU.
Like second-chance, but iwht an additional m-bit to detect modifications.
| r-bit and m-bit | becomes | means |
|---|---|---|
| 11 | 01 | modified |
| 01 | 00 | modified (cont.) |
| 10 | 00 | unmodified |
aka: Not-recently-used page replacement algorithm.
TODO PA 7.3.6 Diagram
Recall — If page fault becomes too high, efficiency drops (waiting for pages to move from disk to memory).
Optimal Working Set: Set of resident pages that will still be needed in the immediate future, and thus should remain.
Why? — In the first few memory operations, the number of page references increases rapidly, but the rate diminishes with time.
- Thus, d must be chosen to cover the period of rapid growth, but not past the point where adding more pages is wasteful.
TODO example of the window trawling through the reference string, explaining at each time unit, the size of things referenced and working set.
To estimate the optimal working set, we use temporal locality by assuming recently references pages will be similar to pages references in the immediate future
TODO
Page Fault Rate: Number of page faults (f) occuring during an number of memory references (t).
\boxed{ P = f/t \text{ where } 0 \le P \le 1 }
P=1 means every memory reference causes a pae fault, P=0 means no page faults occur.
Effective Access Time:
\boxed{ E = (1-P) * m + P * S } \\~\\ \text{where m s the time to access physical memory and S is the time to process a page fault}
Example: TODO PA : 7.5.2
Load Control: Activity of determining how many processes should be running concurrently to maximize performance.
Thrashing: When most time is spent moving pages between memory and disk while CPU remains mostly idle, causing processes to not make any progress.
TODO So basically, we do a lot of context switching, and more processes means smaller pages, therefore more page faults.
Why? — Page size has a major impact on time and space overhead of virtual memory (and thus the entire system).
Larger: You can put less pages in memory, but can give more memory to each process.
Smaller: You can put more pages in memmory, but you can get more page faults.
Most common page sizes range between 512 and 4096, with the number increasing with improvements in disk technology.