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 § – 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?How does MMU work?

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 and dynamic linking?

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?

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.

• 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?

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, TLB, two-level page table, hashed page table, and 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?

ANS

tags: Operating System CSnote