---
title: OS Chapter 8
---

# Chapter 8: Memory-Management Strategies
* Equals to chapter 9: main memory in the new textbook
## Background
* Program must be brought into memory to start.
* CPU can only access main memory and
* Memory unit only sees a stream of addresses + read requests, or address + data and write requests Register access in one CPU clock
* Register access in one CPU clock (or less)
* Main memory access can take many cycles, causing a stall
* Cache sits between main memory and CPU registers
* Protection of memory required to ensure correct operation
### Basic Hardware
* A possible implementation for hardware to protect user processes from accessing each others memory.

* Base register and limit register defines the logical address space for process.
* CPU must check every memory access generated in user mode to be sure it is between base and limit for that user
* The figure above is a scheme to prevent user processes to address out of bound area.

### Address binding
* Programs on disk, ready to be brought into memory to execute form an input queue
* Computer address starts at 00000. But with support first address of user process not need to be 00000.
* Addresses an be represented differently during different stages of a programs life.
* Source code addresses usually symbolic
* Compiled code addresses bind to relocatable addresses
* e.g. “14 bytes from beginning of this module”
* Linker or loader will bind relocatable addresses to absolute addresses
* e.g. 74014
* Each binding maps one address space to another
#### Address binding in three stages
* Binding of instructions and data to memory addresses can happen at three different stages
* Compile time: If you know where the process will reside in memory, then absolute address can be generated. If starting location changes, recompile is necessary.
* Load time: generate relocatable code if memory location is not known at compile time
* Execution time: If the process can be moved during its execution from one memory segment to another, then binding must be delayed until runtime.

### Logical Versus Physical address space
* Logical address(a.k.a Virtual address) is generated by CPU.
* Physical memory is the address seen by the memory unit
* Logical address is bound to physical address space.
* Binding address at either compile or load time generates identical logical and physical address ; logical (virtual) and physical addresses differ in execution-time address-binding scheme
* Logical address space is the set of all logical addresses generated by a program
* Physical address space is the set of all physical addresses generated by a program
#### Memory Management Unit (MMU)
* Run-time mapping from virtual to physical address is done by MMU.
* Simple scheme:
* Base register is know called relocation register
* User only access virtual addresses, never access real physical address.
### Dynamic loading
* A routine is not loaded until it is called.
* Better memory-space utilization; unused routine is never loaded
* All routines kept on disk in relocatable load format
* Useful when large amounts of code are needed to handle infrequently occurring cases
* No special support from the operating system is required, implemented through program design
### Dynamic linking and shared libraries
* Dynamic linked libraries(**DLL**) are system libraries that are linked to user programs when the programs run.
* Static linking – system libraries and program code combined by the loader into the binary program image
* Dynamic linking –linking postponed until execution time
* A small piece of code, called **stub**, is used to locate the DLLs.
* Stub replaces itself with the address of the routine, and executes the routine
* OS checks if routine is in process memory. If not, load it.
* Dynamic linking is useful for libraries.
## Swapping
Swapping is after paging in the tenth edition textbook
* A process can be **swapped** out of of memory into a secondary memory, and then brought back for execution.
* Roll in,Roll out: Swapping variant for priority-based scheduling algorithms. Lower priority process is swapped out so higher priority process can be loaded and executed.
* System maintains a ready queue of ready-to-run processes which have memory images on disk
* Major part of swapping time is transfer time. **Transfer time is directly proportional to the amount of memory swapped.**
* Standard swapping
* swapping has to swap back to the same physical address.
* Modified swapping:
* normally disabled
* Start if more than threshold amount of memory allocated
* Disable again once memory demand reduced below threshold
* Other constraints as well on swapping
* Pending I/O – can’t swap out as I/O would occur to wrong process
* Or always transfer I/O to kernel space, then to I/O device (double buffering)
### swapping on mobile system
* Not mentioned in review questions, so is omitted
## Contiguous Memory allocation
* Memory most support both OS and User processes.
* Because memory is limited, allocation has to be efficient. Contiguous memory allocation is an early method to achieve this.
* Main memory is usually spit in to two partitions
* OS usually resides in the lower partition with the interrupt vector.
* User process is held in the higher partition.
* Each process contains in single contiguous section of memory.
### memory protection
* Relocation registers are used to protect user processes from each other, and from changing operating-system code and data
* Base register contains value of smallest physical address
* Limits register contains range of logical addresses – each logical address must be less than the limit register
* MMU maps logical address dynamically
* Can then allow actions such as kernel code being transient and kernel changing size
### memory allocation
* Multiple-partition allocation
* Degree of multi-programming is limited by number of partitions
* Variable-partition sizes (i.e. memory size is allocated according to needs)
* Hole: block of available memory
* When a process arrives, it is allocated memory from a hole large enough to accommodate it
* Process exiting frees its partition, adjacent free partitions is then combined
* Operating system maintains information about holes and allocated partitions

* First Fit: allocate the first hole that is big enough.
* Best fit: allocate the smallest hole.Must search the entire list unless ordered by size. Produce the smallest leftover hole
* Worst-fit: Allocate the largest hole. Must search entire list. Produces the largest leftover hole segmentation
### Fragmentation
* External Fragmentation: Total memory space exists to satisfy a request, but it is not contiguous so is useless.
* Internal Fragmentation: Allocated memory is larger than needed. The excess memory is internal to the process, but is not used.
* Compaction: method to reduce external fragmentation
* SHuffle memory contents to place all free memory together to create a large block
* Compaction is only possible if relocation is dynamic. Compaction is done at execution time.

### Segmentation
Is not in 10th edition.
* Memory-management scheme that supports user view of memory
* A program is a collection of segments
* Logical address consists of a two tuple: <segment-number,offset>
* Segment table: maps two-dimensional physical addresses. each table entry has:
* base – contains the starting physical address where the segments reside in memory
* limit – specifies the length of the segment
* Segment-table base register (STBR): points to the segment table’s location in memory
* Segment-table length register (STLR): indicates number of segments used by a program;
## Paging
* Physical address space of a process can be non-contiguous.
* process is allocated whenever physical memory is available
* Avoids external fragmentation
* Avoids problem of varying sized memory chunks
### Basic Method
* Physical memory is divided into fixed-sized blocks called frames
* logical memory is divided into blocks of same size called pages
* To run a program of size N pages, need to find N free frames and load program
* A page tables is set up to translate logical to physical addresses
#### Page table(Pure paging)
* Address generated by CPU is divided into:
* Page number (p) – used as an index into a page table which contains base address of each page in physical memory
* Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit
* given logical address space 2m and page size 2n
* Paging example

### Hardware support(TLB)
* Page table is kept in main memory.
* Page-table base register (PTBR) points to the page table
* Page-table length register (PTLR) indicates size of the page table
* In this scheme every data/instruction access requires two memory accesses
* One for the page table and one for the data / instruction
* The two memory access problem can be solved by the use of a special fast-lookup hardware cache called associative memory or translation look-aside buffers (TLBs)
* Some TLBs store address-space identifiers (ASIDs) in each TLB entry – uniquely identifies each process to provide address-space protection for that process
* Otherwise need to flush at every context switch

* On a TLB miss(i.e. page number si not in TLB), value is loaded into the TLB for faster access next time
* Replacement policies must be considered
* Some entries can be wired down for permanent fast access
#### Effective access time
* omitted
### Protection
* Memory protection implemented by associating protection bit with each frame to indicate if read-only or read-write access is allowed
* Can also add more bits to indicate page execute-only, and so on
* Valid-invalid bit attached to each entry in the page table:
* “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page
* “invalid” indicates that the page is not in the process’ logical address space
Or use page-table length register (PTLR)
* Any violations result in a trap to the kernel
### shared paging
* Share codes
* One copy of read-only (reentrant) code shared among processes
* Similar to multiple threads sharing the same process space
* Also useful for interprocess communication if sharing of read-write pages is allowed
* Private code and data
* Each process keeps a separate copy of the code and data
* The pages for the private code and data can appear anywhere in the logical address space
## Structure of the Page table
* Memory structures for paging can get huge using straightforward methods(those above)
### Hierarchial paging
* Break up the logical address space into multiple page tables
* A simple technique is a two-level page table
* We then page the page table
* 
#### Example
* A logical address (on 32-bit machine with 1K page size) is divided into:
* a page number consisting of 22 bits
* a page offset consisting of 10 bits
* Since the page table is paged, the page number is further divided into:
* a 12-bit page number
* a 10-bit page offset
* Thus, a logical address is as follows:
p1 is an index into the outer page table, p2 is the displacement within the page of the inner table.

* known as forward-mapped page table.

### Hashed page table
* Common in address spaces > 32 bits
* The virtual page number is hashed into a page table.
* page table contains a chain of elements hashing to the same location
* each element contains:
1. Virtual page number
2. Value of the mapped page frame
3. pointer to the next element
* Virtual page numbers are compared in this chain searching for a match
* If a match is found, the corresponding physical frame is extracted

### Inverted Page Table
* Rather than each process having a page table and keeping track of all possible logical pages, track all physical pages
* One entry for each real page of memory
* Entry consists of the virtual address of the page stored in that real memory location, with information about the process that owns that page
* Decreases memory needed to store each page table, but increases time needed to search the table when a page reference occurs
## Example: Intel 32- and 64-bit architecture
### IA-32
* Supports both segmentation and segmentation with paging
* Each segment can be 4 GB
* Up to 16 K segments per process
* Divided into two partitions
* CPU generates logical address
* selector given to segmentation unit which produces linear address
* Linear address given to paging unit
* Which generates physical address in main memory
* Paging units form equivalent of MMU
* Pages sizes can be 4 KB or 4 MB
### IA-64
* Nobody Cars!

# Review Question
## 1. [How does the address binding work in the three stages?](#Address-binding-in-three-stages)[How does MMU work?](#Memory-Management-Unit-MMU)
### ANS
* Compile time: If you know where the process will reside in memory, then absolute address can be generated. If starting location changes, recompile is necessary.
* Load time: generate relocatable code if memory location is not known at compile time
* Execution time: If the process can be moved during its execution from one memory segment to another, then binding must be delayed until runtime.
* MMU: Do run-time mapping from virtual to physical address
## 2. When do we use [dynamic loading](#Dynamic-loading) and [dynamic linking](#Dynamic-linking-and-shared-libraries)?
### ANS
* When we need libraries, dynamic load them when program starts. Dynamic loading loads them when function is called.
## 3. [What are two major problems of process memory swapping?](#Swapping)
### ANS
* transfer time: Moving in and out main memory
* Pending I/O: can’t swap out as I/O would occur to wrong process
## 4. [Explain the difference between the three dynamic storage allocation strategies.](#memory-allocation)
* First Fit: allocate the first hole that is big enough.
* Best fit: allocate the smallest hole
* Worst-fit: Allocate the largest hole.
## 5. [How does segmentation work while translating the logical address?](#Segmentation)
### ANS
* Use s to get base and limit in segment table, d for the size of segment, to access physical memory.
## 6. Compare logical address translation in [pure paging](#Page-tablePure-paging), [TLB](#Hardware-supportTLB), [two-level page table](#Hierarchial-paging), [hashed page table](#Hashed-page-table), and [inverted page table](#Inverted-Page-Table).
### ANS
1. Pure Paging
* Cut memory into pages and frames of same size. Use a page table to transform contiguous logical memory into non-contiguous physical memory.
2. TLB
* TLB stores pages that are frequently used.
* If desired page is found in TLB, we can access to physical memory.
* If not found, search it in page table like pure paging.
3. two-level page table
* Break up the logical address space into multiple page tables.We then page the page table.
4. hashed table
* The virtual page number is hashed into a page table. Page table contains a chain of elements hashing to the same location
5. inverted page table
* Rather than keeping track of all possible logical pages, track all physical pages
* Entry consists of the virtual address of the page stored in that real memory location and wich process it belongs to.
## 7. Why paging can allow continuous logical-address pages without moving data blocks in physical memory?
* By using a page table, We access physical memory by address.Continuous logical-address pages don't need to have continuous physical addresses.
## 8. [How does logical address translation work in Intel IA-32, including segmentation and paging?](#IA-32)
### ANS

###### tags: `Operating System` `CSnote`