ch9 2

Chapter 9: Main Memory
Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018
1.Arrive on time, every time (Max delay is 15 minutes then the door
will be closed)
2.Mobile Phones should be silent

3.Speak up, contribute, learn
4.Preparation: “Come ready, be proactive”
5.Deadlines: “Timely submissions, NO exceptions“
6.Attendance will be recorded
Operating System Concepts – 10th Edition 9.2 Silberschatz, Galvin and Gagne ©2018
Course Plan
Lecture # Content
Orientation
Lecture 1
Chapter 1: Introduction
Lecture 2
Chapter 2: Operating-System Services
Lecture 3
Lecture 4
Chapter 3: Processes
Lecture 5
Lecture 6 Chapter 4: Threads & Concurrency
Lecture 7
Chapter 5: CPU Scheduling
Lecture 8
Lecture 9 Chapter 9: Memory Management

Lecture 10
Chapter 11: Mass-Storage Systems
Lecture 11
Chapter 9: Memory Management
▪ Background
▪ Contiguous Memory Allocation
▪ Paging
▪ Swapping
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
▪ Memory unit only sees a stream of:
• addresses + read requests, or
• address + data and write requests
▪ Register access is done in one CPU clock (or less)
▪ Cache sits between main memory and CPU registers
▪ Protection of memory required to ensure correct operation
Protection
▪ Need to ensure that a process can access only those addresses in
its address space.
▪ We can provide this protection by using a pair of base and limit
registers define the logical address space of a process
Hardware Address Protection
▪ CPU must check every memory access generated in user mode to
be sure it is between base and limit for that user
▪ the instructions to loading the base and limit registers are privileged
Address Binding
▪ Programs on disk, ready to be brought into memory to execute form
an input queue
• Without support, must be loaded into address 0000
▪ Inconvenient to have first user process physical address always at
0000
• How can it not be?
▪ Addresses represented in different ways at different stages of a
program’s life
• Source code addresses usually symbolic
• Compiled code addresses bind to relocatable addresses
 i.e., “14 bytes from beginning of this module”
• Linker or loader will bind relocatable addresses to absolute
addresses
 i.e., 74014
• Each binding maps one address space to another
Binding of Instructions and Data to Memory
▪ Address binding of instructions and data to memory addresses
can happen at three different stages
• Compile time: If memory location known a priori, absolute code

can be generated; must recompile code if starting location
changes
• Load time: Must generate relocatable code if memory location

is not known at compile time
• 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
• Logical address – generated by the CPU; also referred to as

virtual address
• 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
▪ 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)
▪ Hardware device that at run time maps virtual to physical address
▪ Many methods possible, covered in the rest of this chapter
Memory-Management Unit (Cont.)
▪ Consider simple scheme. which is a generalization of the base-

register scheme.
▪ The base register now called relocation register
▪ 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
• Execution-time binding occurs when reference is made to location

in memory
• Logical address bound to physical addresses
Memory-Management Unit (Cont.)
▪ Consider simple scheme. which is a generalization of the base-
register scheme.
▪ The base register now called relocation register
▪ The value in the relocation register is added to every address
generated by a user process at the time it is sent to memory
Contiguous Allocation
▪ Main memory must support both OS and user processes
▪ Limited resource, must allocate efficiently
▪ Contiguous allocation is one early method
▪ Main memory usually into two partitions:
• Resident operating system, usually held in low memory with

interrupt vector
• User processes then held in high memory
 Each process contained in single contiguous section of

memory
Hardware Support for Relocation and Limit Registers
Variable Partition
▪ Multiple-partition allocation
• Degree of multiprogramming limited by number of partitions
• Variable-partition sizes for efficiency (sized to a given process’ needs)
• Hole – block of available memory; holes of various size are scattered
throughout 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 combined
• 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
• Produces the smallest leftover hole
▪ Worst-fit: Allocate the largest hole; must also search entire list
• 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
▪ First fit analysis reveals that given N blocks allocated, 0.5 N blocks
lost to fragmentation
• 1/3 may be unusable -> 50-percent rule
Fragmentation (Cont.)
Internal Fragmentation External Fragmentation
Fragmentation (Cont.)
▪ Reduce external fragmentation by compaction
• Shuffle memory contents to place all free memory together in one

large block
• Compaction is possible only if relocation is dynamic, and is done

at execution time
Paging
▪ Physical address space of a process can be noncontiguous;
process is allocated physical memory whenever the latter is
available
• Avoids external fragmentation
• Avoids problem of varying sized memory chunks
▪ Divide physical memory into fixed-sized blocks called frames
• Size is power of 2, between 512 bytes and 16 Mbytes
▪ 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
▪ Backing store likewise split into pages
▪ Still have Internal fragmentation
Address Translation Scheme
▪ 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
page number page offset

p d
m -n n
• For given logical address space 2m and page size 2n
Paging Hardware
Paging Model of Logical and Physical Memory
Paging Example
▪ Logical address: n = 2 and m = 4. Using a page size of 4 bytes and
a physical memory of 32 bytes (8 pages)
Swapping
▪ A process can be swapped temporarily out of memory to a backing
store, and then brought back into memory for continued execution
• Total physical memory space of processes can exceed physical

memory
▪ 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
Swapping (Cont.)
▪ Does the swapped out process need to swap back into same physical
addresses?
▪ Depends on address binding method
• Plus consider pending I/O to / from process memory space
▪ Modified versions of swapping are found on many systems (i.e., UNIX,

Linux, and Windows)
• Swapping normally disabled
• Started if more than threshold amount of memory allocated
• Disabled again once memory demand reduced below threshold
Schematic View of Swapping
Swapping with Paging
End of Chapter 9
Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018

ch9 2

Uploaded by

Copyright:

Available Formats

ch9 2

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

ch9 2

Uploaded by

Copyright:

Available Formats

Chapter 9: Main Memory

2.Mobile Phones should be silent

Lecture 6 Chapter 4: Threads & Concurrency

Lecture 9 Chapter 9: Memory Management

▪ Contiguous Memory Allocation

▪ Memory unit only sees a stream of:

• addresses + read requests, or

• address + data and write requests

▪ Register access is done in one CPU clock (or less)

▪ Cache sits between main memory and CPU registers

▪ Protection of memory required to ensure correct operation

• Compile time: If memory location known a priori, absolute code

• Load time: Must generate relocatable code if memory location

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

• Physical address – address seen by the memory unit

▪ Logical and physical addresses are the same in compile-time and

▪ Logical address space is the set of all logical addresses generated

▪ Physical address space is the set of all physical addresses

▪ Many methods possible, covered in the rest of this chapter

▪ Consider simple scheme. which is a generalization of the base-

▪ The base register now called relocation register

▪ The value in the relocation register is added to every address

• Execution-time binding occurs when reference is made to location

• Logical address bound to physical addresses

▪ Limited resource, must allocate efficiently

▪ Contiguous allocation is one early method

▪ Main memory usually into two partitions:

• Resident operating system, usually held in low memory with

• User processes then held in high memory

 Each process contained in single contiguous section of

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

▪ Best-fit: Allocate the smallest hole that is big enough; must

• Produces the smallest leftover hole

• Produces the largest leftover hole

▪ 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

• 1/3 may be unusable -> 50-percent rule

Internal Fragmentation External Fragmentation

▪ Reduce external fragmentation by compaction

• Shuffle memory contents to place all free memory together in one

• Compaction is possible only if relocation is dynamic, and is done

page number page offset

• For given logical address space 2m and page size 2n

• Total physical memory space of processes can exceed physical

▪ Backing store – fast disk large enough to accommodate copies of all

▪ Roll out, roll in – swapping variant used for priority-based scheduling

▪ Depends on address binding method

• Plus consider pending I/O to / from process memory space

▪ Modified versions of swapping are found on many systems (i.e., UNIX,

• Swapping normally disabled

• Started if more than threshold amount of memory allocated

• Disabled again once memory demand reduced below threshold

You might also like