UNIT 4/LECTURE 1

Main Memory

Memory Management

• Background
• Swapping
• Contiguous Memory Allocation
• Paging
• Structure of the Page Table
• Segmentation
• Example: The Intel Pentium

Objectives

• To provide a detailed description of various ways of organizing memory hardware
• To discuss various memory-management techniques, including paging and segmentation
• To provide a detailed description of the Intel Pentium, which supports both pure segmentation and segmentation with paging

Background

·         Program must be brought (from disk)  into memory and placed within a process for it to be run

·         Main memory and registers are only storage CPU can access directly

·         Register access in one CPU clock (or less)

·         Main memory can take many cycles

·         Cache sits between main memory and CPU registers

·         Protection of memory required to ensure correct operation

Base and Limit Registers

·         A pair of base and limit registers define the logical address space

Binding of Instructions and Data to Memory

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

1.      Compile time:  If memory location known a priori, absolute code can be generated; must recompile code if starting location changes

2.      Load time:  Must generate relocatable code if memory location is not known at compile time

3.      Execution time:  Binding delayed until run time if the process can be moved during its execution from one memory segment to another.  Need hardware support for address maps (e.g., base and limit registers)

Multistep Processing of a User Program

Logical vs. Physical Address Space

·         The concept of a logical address space that is bound to a separate physical address space is central to proper memory management

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

                              II.            Physical address – address seen by the memory unit

·         Logical and physical addresses are the same in compile-time and load-time address-binding schemes; logical (virtual) and physical addresses differ in execution-time address-binding scheme

Memory-Management Unit (MMU)

·         Hardware device that maps virtual to physical address

·         In MMU scheme, the value in the relocation register is added to every address generated by a user process at the time it is sent to memory

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

Dynamic relocation using a relocation register

Dynamic Loading

·         Routine is not loaded until it is called

·         Better memory-space utilization; unused routine is never loaded

·         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

·         Linking postponed until execution time

·         Small piece of code, stub, used to locate the appropriate memory-resident library routine

·         Stub replaces itself with the address of the routine, and executes the routine

·         Operating system needed to check if routine is in processes’ memory address

·         Dynamic linking is particularly useful for libraries

·         System also known as shared libraries

Swapping

·         A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution

·         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

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

·         Modified versions of swapping are found on many systems (i.e., UNIX, Linux, and Windows)

·         System maintains a ready queue of ready-to-run processes which have memory images on disk

Schematic View of Swapping

Contiguous Allocation

·         Main memory usually into two partitions:

                                I.            Resident operating system, usually held in low memory with interrupt vector

                              II.            User processes then held in high memory

·         Relocation registers used to protect user processes from each other, and from changing operating-system code and data

                                I.            Base register contains value of smallest physical address

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

                            III.            MMU maps logical address dynamically

UNIT 4/LECTURE 2

HW address protection with base and limit registers

Contiguous Allocation

·         Multiple-partition allocation

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

2.      When a process arrives, it is allocated memory from a hole large enough to accommodate it

3.      Operating system maintains information about:
a) allocated partitions    b) free partitions (hole)

Dynamic Storage-Allocation Problem

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

·         First-fit:  Allocate the first hole that is big enough

·         Best-fit:  Allocate the smallest hole that is big enough; must search entire list, unless ordered by size 

1.      Produces the smallest leftover hole

·         Worst-fit:  Allocate the largest hole; must also search entire list 

1.      Produces the largest leftover hole

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

Fragmentation

·         External Fragmentation – total memory space exists to satisfy a request, but it is not contiguous

·         Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is memory internal to a partition, but not being used

·         Reduce external fragmentation by compaction

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

b.            Compaction is possible only if relocation is dynamic, and is done at execution time

c. I/O problem

4  Latch job in memory while it is involved in I/O

4  Do I/O only into OS buffers

Paging

·         Logical address space of a process can be noncontiguous; process is allocated physical memory whenever the latter is available

·         Divide physical memory into fixed-sized blocks called frames (size is power of 2, between 512 bytes and 8,192 bytes)

·         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

Address Translation Scheme

·         Address generated by CPU is divided into:

a.      Page number (p) – used as an index into a page table which contains base address of each page in physical memory

b.      Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit

c.       For given logical address space 2^m and page size 2ⁿ

Paging Hardware

Paging Model of Logical and Physical Memory

Paging Example

                                                          32-byte memory and 4-byte pages

UNIT 4/LECTURE 3

Free Frames

                                 Before allocation                                          After allocation

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 (PRLR) 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

Associative Memory

·         Associative memory – parallel search

      Address translation (p, d)

·         If p is in associative register, get frame # out

·         Otherwise get frame # from page table in memory

Paging Hardware With TLB

Effective Access Time

·         Associative Lookup = e time unit

·         Assume memory cycle time is 1 microsecond

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

·         Hit ratio = a

·         Effective Access Time (EAT)

EAT = (1 + e) a + (2 + e)(1 – a)

                                    = 2 + e – a

Memory Protection

·         Memory protection implemented by associating protection bit with each frame

·         Valid-invalid bit attached to each entry in the page table:

1.      “valid” indicates that the associated page is in the process’ logical address space, and is thus a legal page

2.      “invalid” indicates that the page is not in the process’ logical address space

Valid (v) or Invalid (i) Bit In A Page Table

Shared Pages

·         Shared code

1.      One copy of read-only (reentrant) code shared among processes (i.e., text editors, compilers, window systems).

2.      Shared code must appear in same location in the logical address space of all processes

·         Private code and data

1.      Each process keeps a separate copy of the code and data

2.      The pages for the private code and data can appear anywhere in the logical address space

UNIT 4/LECTURE 4

Shared Pages Example

Structure of the Page Table

·         Hierarchical Paging

·         Hashed Page Tables

·         Inverted Page Tables

Hierarchical Page Tables

·         Break up the logical address space into multiple page tables

·         A simple technique is a two-level page table

Two-Level Page-Table Scheme

Two-Level Paging Example

·         A logical address (on 32-bit machine with 1K page size) is divided into:

1.      a page number consisting of 22 bits

2.      a page offset consisting of 10 bits

·         Since the page table is paged, the page number is further divided into:

1.      a 12-bit page number

2.      a 10-bit page offset

     Thus, a logical address is as follows:

where p_i is an index into the outer page table, and p₂ is the displacement within the page of the outer page table

Address-Translation Scheme

Three-level Paging Scheme

Hashed Page Tables

·         Common in address spaces > 32 bits

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

·         Virtual page numbers are compared in this chain searching for a match. If a match is found, the corresponding physical frame is extracted.

UNIT 4/LECTURE 5

Inverted Page Table

·         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

·         Use hash table to limit the search to one — or at most a few — page-table entries

Inverted Page Table Architecture

Segmentation

·         Memory-management scheme that supports user view of memory

·         A program is a collection of segments.  A segment is a logical unit such as:

                        main program,

                        procedure,

                        function,

                        method,

                        object,

                        local variables, global variables,

                        common block,

                        stack,

                        symbol table, arrays

User’s View of a Program

Logical View of Segmentation

Segmentation Architecture

·         Logical address consists of a two tuple:

<segment-number, offset>,

·         Segment table – maps two-dimensional physical addresses; each table entry has:

o   base – contains the starting physical address where the segments reside in memory

o   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

o   With each entry in segment table associate:

4  validation bit = 0 Þ illegal segment

4  read/write/execute privileges

·         Protection bits associated with segments; code sharing occurs at segment level

·         Since segments vary in length, memory allocation is a dynamic storage-allocation problem

·         A segmentation example is shown in the following diagram

Segmentation Hardware

Example of Segmentation

UNIT 4/LECTURE 6

Virtual Memory

• Background
• Demand Paging
• Copy-on-Write
• Page Replacement
• Allocation of Frames
• Thrashing
• Memory-Mapped Files
• Allocating Kernel Memory
• Other Considerations
• Operating-System Examples

Objectives

• To describe the benefits of a virtual memory system
• To explain the concepts of demand paging, page-replacement algorithms, and allocation of page frames
• To discuss the principle of the working-set model

Background

• Virtual memory – separation of user logical memory from physical memory.

1. Only part of the program needs to be in memory for execution
2. Logical address space can therefore be much larger than physical address space
3. Allows address spaces to be shared by several processes
4. Allows for more efficient process creation

• Virtual memory can be implemented via:

                                                        I.            Demand paging

                                                      II.            Demand segmentation

Virtual Memory That is Larger Than Physical Memory

Virtual-address Space

Shared Library Using Virtual Memory

Demand Paging

• Bring a page into memory only when it is needed
• Less I/O needed
• Less memory needed
• Faster response
• More users
• Page is needed Þ reference to it
• invalid reference Þ abort
• not-in-memory Þ bring to memory
• Lazy swapper – never swaps a page into memory unless page will be needed

o   Swapper that deals with pages is a pager

Transfer of a Paged Memory to Contiguous Disk Space

Valid-Invalid Bit

• With each page table entry a valid–invalid bit is associated
  (v Þ in-memory, i Þ not-in-memory)
• Initially valid–invalid bit is set to i on all entries

                         Example of a page table snapshot:

·         During address translation, if valid–invalid bit in page table entry is I Þ page fault

Page Table When Some Pages Are Not in Main Memory

Page Fault

• If there is a reference to a page, first reference to that page will trap to operating system:

page fault

1. Operating system looks at another table to decide:

1. Invalid reference Þ abort
2. Just not in memory

2. Get empty frame
3. Swap page into frame
4. Reset tables
5. Set validation bit = v
6. Restart the instruction that caused the page fault

• Restart instruction

                    block move

·         auto increment/decrement location

UNIT 4/LECTURE 7

Steps in Handling a Page Fault

Performance of Demand Paging

• Page Fault Rate 0 £ p £ 1.0
• if p = 0 no page faults
• if p = 1, every reference is a fault
• Effective Access Time (EAT)

                        EAT = (1 – p) x memory access

                                    + p        (page fault overhead

                                                      + swap page out

                                                      + swap page in

                                                      + restart overhead

                                                     )

Demand Paging Example

• Memory access time = 200 nanoseconds
• Average page-fault service time = 8 milliseconds
• EAT = (1 – p) x 200 + p (8 milliseconds)

= (1 – p  x 200 + p x 8,000,000

            = 200 + p x 7,999,800

• If one access out of 1,000 causes a page fault, then

EAT = 8.2 microseconds.

            This is a slowdown by a factor of 40!!

Process Creation

• Virtual memory allows other benefits during process creation:

            - Copy-on-Write

            - Memory-Mapped Files (later)

Copy-on-Write

• Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memory
  
  If either process modifies a shared page, only then is the page copied
• COW allows more efficient process creation as only modified pages are copied
• Free pages are allocated from a pool of zeroed-out pages

Before Process 1 Modifies Page C

After Process 1 Modifies Page C

What happens if there is no free frame?

• Page replacement – find some page in memory, but not really in use, swap it out
• algorithm
• performance – want an algorithm which will result in minimum number of page faults
• Same page may be brought into memory several times

Page Replacement

• Prevent over-allocation of memory by modifying page-fault service routine to include page replacement
• Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk
• Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory

Need For Page Replacement

Basic Page Replacement

1. Find the location of the desired page on disk
2. Find a free frame:
      -  If there is a free frame, use it
      -  If there is no free frame, use a page replacement            algorithm to select a victim frame
3. Bring  the desired page into the (newly) free frame; update the page and frame tables
4. Restart the process

Page Replacement

UNIT 4/LECTURE 8

Page Replacement Algorithms

• Want lowest page-fault rate
• Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
• In all our examples, the reference string is

               1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Graph of Page Faults Versus The Number of Frames

First-In-First-Out (FIFO) Algorithm

• Reference string: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• 3 frames (3 pages can be in memory at a time per process)

• 4 frames

• Belady’s Anomaly: more frames Þ more page faults

FIFO Page Replacement

FIFO Illustrating Belady’s Anomaly

Optimal Algorithm

• Replace page that will not be used for longest period of time
• 4 frames example

                         1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• How do you know this?
• Used for measuring how well your algorithm performs

Optimal Page Replacement

Least Recently Used (LRU) Algorithm

Reference string:  1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

• Counter implementation

1. Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter
2. When a page needs to be changed, look at the counters to determine which are to change

LRU Page Replacement

UNIT 4/LECTURE 9

LRU Algorithm can be implemented in the following ways:-

• Stack implementation – keep a stack of page numbers in a double link form:

a.      Page referenced:

                                                                                      i.      move it to the top

                                                                                     ii.      requires 6 pointers to be changed

b.      No search for replacement

Use Of A Stack to Record The Most Recent Page References

LRU Approximation Algorithms

• Reference bit
• With each page associate a bit, initially = 0
• When page is referenced bit set to 1
• Replace the one which is 0 (if one exists)
• We do not know the order, however
• Second chance

o   Need reference bit

o   Clock replacement

o   If page to be replaced (in clock order) has reference bit = 1 then:

4  set reference bit 0

4  leave page in memory

4  replace next page (in clock order), subject to same rules

Second-Chance (clock) Page-Replacement Algorithm

Counting Algorithms

• Keep a counter of the number of references that have been made to each page
• LFU Algorithm:  replaces page with smallest count
• MFU Algorithm: based on the argument that the page with the smallest count was probably just brought in and has yet to be used

Allocation of Frames

• Each process needs minimum number of pages
• Example:  IBM 370 – 6 pages to handle SS MOVE instruction:
• instruction is 6 bytes, might span 2 pages
• 2 pages to handle from
• 2 pages to handle to
• Two major allocation schemes

o   fixed allocation

o   priority allocation

Fixed Allocation

• Equal allocation – For example, if there are 100 frames and 5 processes, give each process 20 frames.
• Proportional allocation – Allocate according to the size of process

Priority Allocation

• Use a proportional allocation scheme using priorities rather than size
• If process P_i generates a page fault,

                                I.            select for replacement one of its frames

                              II.            select for replacement a frame from a process with lower priority number

Global vs. Local Allocation

• Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another
• Local replacement – each process selects from only its own set of allocated frames

UNIT 4/LECTURE 10

Thrashing

• If a process does not have “enough” pages, the page-fault rate is very high.  This leads to:
• low CPU utilization
• operating system thinks that it needs to increase the degree of multiprogramming
• another process added to the system
• Thrashing º a process is busy swapping pages in and out

Demand Paging and Thrashing

• Why does demand paging work?
  Locality model
• Process migrates from one locality to another
• Localities may overlap
• Why does thrashing occur?
  S size of locality > total memory size

Locality In A Memory-Reference Pattern

Working-Set Model

• D º working-set window º a fixed number of page references
  Example:  10,000 instruction
• WSS_i (working set of Process P_i) =
  total number of pages referenced in the most recent D (varies in time)
• if D too small will not encompass entire locality
• if D too large will encompass several localities
• if D = ¥ Þ will encompass entire program
• D = S WSS_i º total demand frames
• if D > m Þ Thrashing
• Policy if D > m, then suspend one of the processes

Keeping Track of the Working Set

• Approximate with interval timer + a reference bit
• Example: D = 10,000
• Timer interrupts after every 5000 time units
• Keep in memory 2 bits for each page
• Whenever a timer interrupts copy and sets the values of all reference bits to 0
• If one of the bits in memory = 1 Þ page in working set
• Why is this not completely accurate?
• Improvement = 10 bits and interrupt every 1000 time units

Page-Fault Frequency Scheme

• Establish “acceptable” page-fault rate

o   If actual rate too low, process loses frame

o   If actual rate too high, process gains frame

Buddy System

• Allocates memory from fixed-size segment consisting of physically-contiguous pages
• Memory allocated using power-of-2 allocator

o   Satisfies requests in units sized as power of 2

o   Request rounded up to next highest power of 2

o   When smaller allocation needed than is available, current chunk split into two buddies of next-lower power of 2

4  Continue until appropriate sized chunk available

UNIT 4/LECTURE 11

Other Issues –

• Prepaging

• To reduce the large number of page faults that occurs at process startup
• Prepage all or some of the pages a process will need, before they are referenced
• But if prepaged pages are unused, I/O and memory was wasted
• Assume s pages are prepaged and α of the pages is used

4  Is cost of s * α  save pages faults > or < than the cost of prepaging
s * (1- α) unnecessary pages? 

4  α near zero Þ prepaging loses

• Page size selection must take into consideration:

• fragmentation
• table size
• I/O overhead
• locality

·         TLB Reach

Ø  TLB Reach - The amount of memory accessible from the TLB

Ø  TLB Reach = (TLB Size) X (Page Size)

Ø  Ideally, the working set of each process is stored in the TLB

o   Otherwise there is a high degree of page faults

Ø  Increase the Page Size

o   This may lead to an increase in fragmentation as not all applications require a large page size

Ø  Provide Multiple Page Sizes

o   This allows applications that require larger page sizes the opportunity to use them without an increase in fragmentation

·         Program Structure

Ø  Int[128,128] data;

Ø  Each row is stored in one page

Ø  Program 1      

                                      for (j = 0; j <128; j++)
                                           for (i = 0; i < 128; i++)
                                                    data[i,j] = 0;

                           128 x 128 = 16,384 page faults

Ø  Program 2      

                                      for (i = 0; i < 128; i++)
                                            for (j = 0; j < 128; j++)
                                                    data[i,j] = 0;

              128 page faults

·         I/O interlock

Ø  I/O Interlock – Pages must sometimes be locked into memory

Ø  Consider I/O - Pages that are used for copying a file from a device must be locked from being selected for eviction by a page replacement algorithm

Reason Why Frames Used For I/O Must Be In Memory