Memory Management

In this lecture, we will discuss the following:

• Background
• Swapping
• Contiguous Memory Allocation
• Paging
• Segmentation
• Segmentation with Paging

• Program must be brought into memory and placed within a process for it to be executed.
• A process may be moved between memory and disk during execution.
• Main memory and registers are only storage CPU can access directly
• Memory unit only sees a stream of addresses + read requests, or address + data and write requests
• Input queue – collection of processes on the disk that are waiting to be brought into memory for execution.
• User programs go through several steps before being executed.

• A process can be swapped temporarily out of memory to a backing store , and then brought back into memory for continued execution. (ex: Round Robin Algorithm)
• Backing store – fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images.
• Roll out, roll in – swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed.
• Does the swapped out process need to swap back in to same physical addresses?
• Depends on address binding method, if binding is done
  • At assembly or load time, p moves to the same location
  • At execution time, process can be swapped into diff memory space because physical add are computed during execution time
• Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped.

• External Fragmentation: Enough total memory space exists to satisfy a request, but it is not contiguous.
  • Solutions
    • Compaction- Shuffle memory contents to place all free memory together in one large block. If relocation is static and is done at assembly or load time, compaction cannot be done. It is possible only if relocation is dynamic and is done at execution time.
    • Allow the logical-address space of a process to be noncontiguous. Ex: Paging and Segmentation
• Internal Fragmentation: when memory allocated is slightly larger than the size needed by the process. the size difference between the process size and the allocated memory is memory that is internal to a partition, but not being used.

• Memory-management scheme that supports user view of memory.
• A logical address space is a collection of segments.
• A program is a collection of segments. A segment is a logical unit such as: main program, procedure, function, local variables, global variables, common block, stack, symbol table, arrays
• Each segment has a name and a length. For simplicity, the segments are given numbers.

contiguous

• Paging relieves fragmentation issue. Single process can be distributed over a number of holes.
• Divide physical memory into fixed-sized blocks called frames 1 (size is power of 2, between 512 bytes and GB per page).
• Divide logical memory into blocks of same size called pages.
• Keep track of all free frames.
• To run a program of size N pages, need to find N free frames and load program.
• Set up a page table to translate logical to physical addresses
• Internal fragmentation

• Consider a logical address space of 256 pages with a 4-KB page size, mapped onto a physical memory of 64 frames. a. How many bits are required in the logical address?

Consider that the physical memory is 256K, logical memory (per process) is 64K

1.

and the page size is 2K. Calculate the following values Number of pages per process

a)

Number of frames in physical memory

b)

Number of bits indicating page number

c)

Number of bits indicating offset

d)

• Associative registers Page # Frame # Address translation (page #, frame #)
  • If page# is in associative register, get frame # out.
  • Otherwise get frame # from page table in memory

memory.

• Hit Ratio = h: The percentage of times that a particular page number is found in the TLB.
• Effective access time can be calculated based on:
  • The time it takes to access main memory
  • The time it takes to access the TLB
  • The hit ratio for the TLB
• Example: Consider h = 80%,  = 20ns for TLB search, 100ns for memory access
  • Time to access main memory = 100ns
  • Time to access TLB = 20 ns
  • Hit ratio = 0.8 (80%) we found the desired page No in the TLB 80% of time
  • If page is found in TLB, total access time = 120?
  • If page is not found in TLB, total access time = 220?need to access memory for page table & frame No(100) & access the desire byte in memory (100)
  • Effective access time = ? 0.8 * 120 + 0.2 *220 = 140 ns where, h = hit ratio of TLB EAT = h*(c+m) + (1-h)*(c+2m) m = Memory access time c = TLB access time

• Memory protection in a paged environment is implemented by associating protection bit with each frame.
• 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.

• Shared code
  • One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems).
  • Shared code must appear in same location in the logical address space of all processes.
• 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.