OS Chapter 8

Chapter 8 \u00A0Memory Management

Background

Main memory and registers are only storage CPU can access directlyRegister access in one CPU clock (or less)Main memory can take many cyclesCache sits between main memory and CPU registersProtection of memory required to ensure correct operation

Address binding of instructions and data to memory addresses can happen at three different stages

Load time: \u00A0Must generate relocatable code if memory location is not known at compile time

Execution time: \u00A0Binding delayed until run time if the process can be moved during its execution from one memory segment to another

Logical vs. Physical Address Space

Logical address\u00A0

Logical address – generated by the CPU; also referred to as virtual address

Logical address space is the set of all logical addresses generated by a program

Physical address\u00A0

Physical address – address seen by the memory unit

Physical address space is the set of all physical addresses generated by a program

Logical and physical addresses are\u00A0

the same in compile-time and load-time address-binding schemes;\u00A0

differ in execution-time address-binding scheme

Memory-Management Unit (MMU)

Hardware device that at run time maps virtual to physical address

The user program deals with logical addresses; it never sees the real physical addresses

Dynamic Loading

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 requiredImplemented through program designOS can help by providing libraries to implement dynamic loading

Dynamic Linking

Dynamic linking –linking postponed until execution time

Dynamic linking is particularly useful for libraries

System also known as shared libraries

Swapping

concept

Major part of swap time is transfer time; total transfer time is directly proportional to the amount of memory swapped

Does the swapped out process need to swap back in to same physical addresses?

Depends on address binding method

Backing store

fast disk large enough to accommodate copies of all memory images for all users; must provide direct access to these memory images

swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed

Context Switch Time including Swapping

Context switch time can then be very high

100MB process swapping to hard disk with transfer rate of 50MB/sec

Plus disk latency of 8 msSwap out time of 2008 ms (2000ms+ 8ms)Plus swap in of same sized processTotal context switch swapping component time of 4016ms ( 4 seconds)

Can reduce if reduce size of memory swapped – by knowing how much memory really being used

System calls to inform OS of memory use via request memory and release memory

Contiguous Memory Allocation

Main memory usually into two partitions

User processes then held in high memory

Each process contained in single contiguous section of memory

memory mapping and protection

Base register contains value of smallest physical address

Limit register contains range of logical addresses – each logical address must be less than the limit register\u00A0

MMU maps logical address dynamically

Can then allow actions such as kernel code being transient and kernel changing size

Multiple-partition allocation

Hole – block of available memory; holes of various size are scattered throughout memory

Operating system maintains information about:\u000B \u00A0 a) allocated partitions \u00A0 \u00A0b) free partitions (hole)

How to satisfy a request of size n from a list of free holes?

First-fit: \u00A0Allocate the first hole that is big enough

Produces the smallest leftover hole

Worst-fit: \u00A0Allocate the largest hole; must also search entire list\u00A0

Produces the largest leftover hole

First-fit and best-fit better than worst-fit in terms of speed and storage utilization

Fragmentation

External Fragmentation\u00A0

Internal Fragmentation

Reduce external fragmentation by compaction

Shuffle memory contents to place all free memory together in one large block

I/O problem

Latch job in memory while it is involved in I/ODo I/O only into OS buffers

Paging

Its a memory-management scheme that permits the Physical \u00A0address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available

Divide logical memory into blocks of same size called pages

Set up a page table to translate logical to physical addresses

Backing store likewise split into pages

disadvantage :\u00A0Still have Internal fragmentation

Address Translation Scheme

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

Calculating internal fragmentation

Implementation of Page Table

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

Replacement policies must be considered

Some entries can be wired down for permanent fast access

Associative Memory

Associative memory – parallel search\u00A0

Effective Access Time

Associative Lookup = \u00A0\"e\" \u00A0time unitCan be 10% of memory access time

Hit ratio = \"a\"Hit ratio – percentage of times that a page number is found in the associative registers; ratio related to number of associative registers

Consider \"a\

Consider slower memory but better hit ratio - \u00A0\"a\

Memory Protection

Shared Pages

Shared code

Similar to multiple threads sharing the same process space

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 straight-forward methodsConsider a 32-bit logical address space as on modern computersPage size of 4 KB (212)Page table would have 1 million entries (232 / 212)If each entry is 4 bytes - 4 MB of physical address space / memory for page table aloneDon’t want to allocate that contiguously in main memory

Hierarchical Paging

Break up the logical address space into multiple page tablesA simple technique is a two-level page tableWe then page the page table

Two-Level Paging Example

Hashed Page Tables

Common in address spaces 32 bits

The virtual page number is hashed into a page tableThis page table contains a chain of elements hashing to the same location

Each element contains

\u00A0(1) the virtual page number\u00A0

(2) the value of the mapped page frame\u00A0

(3) a pointer to the next element

Inverted Page Tables

One entry for each real page of memory

Segmentation

Memory-management scheme that supports user view of memory\u00A0

Segmentation Architecture\u00A0

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;

segment number s is legal if s STLR

Protection\u00A0With each entry in segment table associate:

validation bit = 0 = illegal segment

read/write/execute privileges