INCS102
OPERATING
SYSTEMS
MEMORY
Dr. JOHN ZAKI 1
TABLE OF CONTENTS
01 RECALL
02 MAIN MEMORY
03 MEMORY ALLOCATION & SEGMENTATION
04 MEMORY PAGING
05 VIRTUAL MEMORY
Dr. JOHN ZAKI 2
RECALL
1. The CPU can access the memory and registers
2. When the CPU reads from the registers, usually
that happens in a single clock cycle.
3. When the CPU reads memory it can take more
than one cycle…It causes a stall. (recall?)
4. Cache sits between the main memory and the
CPU, it is faster than the main memory.
5. Protection of memory is required to ensure
correct operation. A process must not access the
memory locations of other processes. (Recall?)
Dr. JOHN ZAKI 4
RECALL: MEMORY MANAGEMENT & PROTECTION
● To execute a program all (or part) of the instruction
and data must be in memory
● To protect the memory, OS doesn’t allow a program
to access another program’s memory location
through assigning base, and limit addresses.
BASE REG
● Memory management determines what is in memory
and when
○ Optimizing CPU utilization and computer
response to users
LIMIT REG
● Memory management activities (MMU)
○ Keeping track of which parts of memory are
currently being used and by whom
○ Deciding which processes (or parts thereof)
and data to move into and out of memory
○ Allocating and deallocating memory space as
needed
Dr. JOHN ZAKI 5
BASE & LIMIT REGISTERS
Need to ensure that a process can
access only those addresses in its
address space.
CPU checks that the process generated
an address in the process address
space.
We can provide this protection by
using a pair of base and limit registers
define the logical address space of a
process
Base + limit = limit register content
300040 + 120900 = 420940
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
ADDRESS
BINDING
How does it work?
Programs on disk, ready to be brought
into memory to execute form an input
queue
Without OS support, must be loaded into address 0000
Inconvenient to have first user process
physical address always at 0000
Why?
EX. Think of a program code you write.
ADDRESS BINDING
Addresses represented in different ways at different stages of a
program’s life
▪ Source code addresses usually symbolic (Variable names e.g. int count)
▪ 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
▪ i.e., exact memory location is: 74014
▪ Each binding maps one address space to another
Symbolic Compiler binds
Relocatable Loader binds
Absolute
address address address
Source program
ADDRESS BINDING
MAIN MEMORY
0
0
Some C code OS
Void main ()
{
… COMPILER 14 bytes
… from the
14 int count = 0 beginning
30000
…
…
P1 30014
} RELOCATABLE
ADDRESS
PROGRAM CODE
FOR PROCESS P1
ABSOLUTE ADDRESS = BASE ADDRESS + RELOCATABLE ADDRESS ABSOLUTE
ADDRESS
BINDING INSTRUCTIONS & 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) Multi-step processing of a
user program
LOGICAL & 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 (RAM)
Dr. JOHN ZAKI 13
MEMORY MANAGEMENT UNIT (MMU)
It is the hardware device that maps virtual to physical address at runtime
Dr. JOHN ZAKI 14
MEMORY MANAGEMENT UNIT (MMU)
If we attempt to join the concepts of
base-register, binding, relocatable
address, logical address, virtual address,
and physical address, a generalization of
the base register is 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 EX.
addresses; it never sees the real Logical addr = 346, Relocation reg. = 14000
physical addresses Physical addr = 14364
Dr. JOHN ZAKI 15
DYNAMIC LOADING
The entire program does need to be in memory to execute
Routine is not loaded until it is called
All routines kept on disk in relocatable load format
Useful when large amounts of code are needed to handle
infrequently occurring
DYNAMIC LINKING
SHARED LIBRARIES
Static linking – system libraries & program code combined by the
loader into the binary program image
Dynamic linking –linking postponed until execution time
Stub –small piece of code used to locate the appropriate library routine
(resident in memory)
The OS checks if the routine is in the memory, if not… it loads the library
CONTIGUOUS
ALLOCATION
CONTIGUOUS ALLOCATION
A D
MEMORY SPLIT TWO PARTITIONS:
MAIN MEMORY MUST SUPPORT
1. OS IN LOW MEMORY
BOTH USER & OS PROCESSES
2. USER PROCESS IN HIGH MEMORY
LIMITED RESOURCES, ALLOCATE
B E
EACH PROCESS IS CONTAINED
EFFICIENTLY. MMU MAPS IN A SINGLE CONTIGUOUS
LOGICAL ADDR. DYNAMICALLY SECTION
RELOCATION REGISTERS USED
C F
AN EARLY METHOD OF
MEMORY ALLOCATION TO PROTECT USER PROCESSES
FROM EACH OTHER
CONTIGUOUS ALLOCATION – PROTECTION
HW SUPPORT FOR RELOCATION AND LIMIT REGISTERS
SWAPPING
A process or part of it
can be swapped out of Swap time depend on the
memory to a backing amount of memory
storage. Then brought swapped. Major part of
back in for continued swap time is transfer time
execution.
Reason is the total The system maintain a
memory requirement of ready-queue for
processes exceed the processes ready to run
physical memory with images on disk
available.
MEMORY ALLOCATION - VARIABLE PARTITION
Hole – block of available memory; holes of various size are scattered throughout memory
Variable-partition sizes for efficiency (sized to a given process’ needs)
When a process arrives, it is allocated memory from a hole large enough to accommodate it
Exiting process frees its partition, adjacent free partitions are combined.
Operating system maintains information about:
a) allocated partitions b) free partitions (hole)
What happens when
there isn’t sufficient
memory to satisfy the
demands of an arriving
process?
What happens if there
are two adjacent holes
next to each other?
DYNAMIC STORAGE ALLOCATION PROBLEM
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
Dr. JOHN ZAKI 26
EXAMPLE
AVAILABLE MEMORY SPACES (10, 30, 20) KB AND WE WANT TO
ALLOCATE SPACE TO (15, 9 KB)
15 KB 9 KB
BEST FIT 20 10
WORST FIT 30 20
FIRST FIT 30 10
Dr. JOHN ZAKI 27
WHAT IS THE PROBLEM
THAT COULD HAPPEN
WITH FIRST-FIT & BEST
FIT?
FRAGMENTATION
Fragmentation
External Fragmentation – total memory
space exists to satisfy a request, but it is
not contiguous. The solution is …..
Compaction: Shuffle memory
contents to place all free memory
together in one large block. Is there
another solution?
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
Dr. JOHN ZAKI 29
SEGMENTATION
PROGRAMMER VIEW OF MEMORY
DEVELOPERS DO NOT USUALLY VIEW
THE MEMORY AS A LINEAR ARRAY OF
BYTES.
INSTEAD, THEY LIKE TO THINK ABOUT IT
AS SEGMENTS (OF VARIABLE SIZE).
Segmentation is a memory-
management scheme that supports
this programmer view of memory.
A logical address space is a
collection of segments. (SEGMENT
NUMBER & OFFSET)
SEGMENTATION
EACH SEGMENT <SEG-#, OFFSET>
1. THE CODE
2. GLOBAL VARIABLES
3. THE HEAP
4. THE STACK
5. THE LIBRARIES
NON-CONTIGUOUS AS IT IS SPLIT
INTO SEGMENTS
SEGMENTATION HW
PAGING
PAGING
Physical address space of a process can be noncontiguous
Avoids external fragmentation,
Avoids problem of varying sized memory chunks
PHYSICAL MEMORY FRAMES = LOGICAL MEMORY PAGES
size power of 2
Keep track of all free frames
EX: 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
Dr. JOHN ZAKI 34
ADDRESS TRANSLATION SCHEME
1. 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
page number page offset
p d
m -n n
c. For given logical address space 2m and page size 2n
PAGING HARDWARE
Dr. JOHN ZAKI 36
PAGING MODEL OF LOGICAL AND PHYSICAL MEMORY
0
4
PAGE
5
EXAMPLE 6
Logical address: n = 2 and m = 4. Using a page 7
size of 4 bytes and a physical memory of 32 bytes
(8 pages)
FRAME
MODEL
PAGING - CALCULATING INTERNAL FRAGMENTATION
EXAMPLE
Page size = 2,048 bytes
Process size = 72,766 bytes
➔35 pages + 1,086 bytes (36 pages)
Internal fragmentation of 2,048 - 1,086 = 962 bytes
Worst case fragmentation = 1 frame for use by only 1 byte
On average fragmentation = 1 / 2 frame size
Dr. JOHN ZAKI 38
ARE SMALL
FRAME SIZES
DESIRABLE?
Free Frames
Before allocation After allocation
IMPLEMENTATION OF PAGE TABLE
HW SUPPORT
1. EACH OS HAS ITS OWN WAY OF IMPLEMENTING PAGE TABLE (used for storing paging info)
▪ Registers: Page table is kept in registers for tables with relatively small entries (ex. 256
entries)
▪ Page-table base register (PTBR) points to the page table which is kept in memory
(reduce context switching).
▪ 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
2. The two-memory access problem can be solved by the use of a special fast-lookup hardware
cache called translation look-aside buffers (TLBs) (also called associative memory).
TRANSLATION LOOK-ASIDE BUFFER
1. The standard solution to the 2-memory access
problem is to use a special fast hardware cache
(TLB). High speed associative memory.
2. Parallel search for items within the table.
3. Some TLBs store address-space identifiers
(ASIDs) in each TLB entry – uniquely identifies each
process to provide address-space protection for
that process
4. TLBs typically small (64 to 1,024 entries)
5. On a TLB miss, value is loaded into the TLB for
faster access next time
a. Replacement policies must be considered
b. Some entries can be wired down for
permanent fast access
EFFECTIVE ACCESS TIME
Hit ratio – percentage of times that a page number is found in the TLB
An 80% hit ratio means that we find the desired page number in the TLB 80% of the time.
EXAMPLE
Suppose that 10 nanoseconds to access memory.
a. If we find the desired page in TLB then a mapped-memory access take 10 ns
b. Otherwise ,we need two memory access, so it is 20 ns
Effective Access Time (EAT)
EAT = 0.80 x 10 + 0.20 x 20 = 12 nanoseconds
implying 20% slowdown in access time
Consider a more realistic hit ratio of 99%,
EAT = 0.99 x 10 + 0.01 x 20 = 10.1ns
implying only 1% slowdown in access time.
MEMORY PROTECTION IN PAGED ENVIROMENT
VALID (V) OR INVALID (I) BIT IN A PAGE TABLE
1. Memory protection implemented by
associating protection bit with each frame to
indicate if read-only or read-write access is
allowed
2. 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)
3. Any violations result in a trap to the kernel
SHARED PAGES
1. Shared code
a. One copy of read-only (reentrant) code
shared among processes (i.e., text editors,
compilers, window systems)
b. Similar to multiple threads sharing the
same process space
c. Also useful for interprocess
communication if sharing of read-write
pages is allowed
2. Private code and data
a. Each process keeps a separate copy of
the code and data
b. 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 methods
EXAMPLE: Consider a 32-bit logical address space as on modern computers
a. Page size of 4 KB (212)
➔Page table would have 1 million entries (232 / 212)
a. If each entry is 4 bytes
➔ each process 4 MB of physical address space for the page table alone
i. Don’t want to allocate that contiguously in main memory
a. One simple solution is to divide the page table into smaller units
i. Hierarchical Paging
ii. Hashed Page Tables
iii. Inverted Page Tables
HIERARCHICAL PAGE TABLES
RECALL……PAGING
page number page offset
p d
m -n n
PAGING OF THE PAGING
HIERARCHICAL PAGE TABLES
EXAMPLE
1. A logical address (on 32-bit machine with 4K page size) is divided into:
a. a page number consisting of 20 bits
b. a page offset consisting of 12 bits
2. Page the page table, thus the page number is further divided into:
a. a 10-bit page number
b. a 10-bit page offset
SUMMARIZE
PAGING WITH
SWAPPING
VIRTUAL
MEMORY
Virtual memory
We discussed many strategies that
allows the
attempt to keep as many processes
as possible in the memory and allow
execution of
multiprogramming.
process that
However, they tend to require that
the entire process be in the memory
ARE NOT
before execution.
COMPLETELY IN
MEMORY
WHAT IS THE
ADVANTAGE OF
SUCH TECHNIQUE
BACKGROUND
Code needs to be in memory to execute, but entire program rarely used
EX: Error code, unusual routines, large data structures
Consider ability to execute partially-loaded program
Program no longer constrained by limits of physical memory
Each program takes less memory while running -> more programs run at the same time
Increased CPU utilization and throughput with no increase in response time or turnaround time
Less I/O needed to load or swap programs into memory -> each user program runs faster
Separation of user logical More programs running
memory from physical memory. concurrently. Thus, less I/O
Only part of the program needs needed to load or swap
to be in memory for execution. processes
Logical address space can Allows address spaces to be
therefore be much larger shared by several processes
than physical address Allows for more efficient
space process creation
logical view of how process is stored in memory
Usually start at address 0, contiguous addresses
until end of space VIRTUAL
Meanwhile, physical memory organized in page
frames ADDRESS
MMU must map logical to physical
Virtual memory can be implemented via:
SPACE
Demand paging
Demand segmentation
VIRTUAL MEMORY > PHYSICAL MEMORY
backing
storage
Dr. JOHN ZAKI 62
VIRTUAL-ADDRESS SPACE
Design logical address space for stack to start at Max logical
address and grow “down” while heap grows “up”.
Unused address space between the two is hole.
No physical memory needed until heap or stack grows to a given
new page.
Enables sparse address spaces with holes left for growth,
dynamically linked libraries, etc.
System libraries shared via mapping into virtual address space
Shared memory by mapping pages read-write into virtual
address space
Dr. JOHN ZAKI 63
SHARED LIBRARY USING VIRTUAL MEMORY
Dr. JOHN ZAKI 64
DEMAND PAGING
We could bring entire process into
memory at load time
Or bring a page into memory only when
it is needed
Less I/O needed, no unnecessary I/O
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
Dr. JOHN ZAKI 65
BASIC CONCEPTS
When swapping a process in, the pager guesses which pages will be used
before swapping out again
Instead, pager brings in only those pages into memory
How to determine that set of pages?
Need new MMU functionality to implement demand paging
If pages needed are already memory resident
No difference from non-demand-paging
If page needed and not memory resident
Need to detect and load the page into memory from storage
Without changing program behavior
Without programmer needing to change code
Dr. JOHN ZAKI 66
VALID-INVALID BIT
With each page table entry, a valid–invalid bit is
associated
v in-memory – memory resident
i not-in-memory
Initially valid–invalid bit is set to i on all entries
Example of a page table snapshot:
During MMU address translation, if valid–invalid
bit in page table entry is i page fault
Dr. JOHN ZAKI 67
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:
Invalid reference abort
Just not in memory
2. Find free frame
3. Swap page into frame via scheduled disk operation
4. Reset tables to indicate page now in memory
5. Set validation bit = v
6. Restart the instruction that caused the page fault
Dr. JOHN ZAKI 69
PAGE FAULT
Dr. JOHN ZAKI 70
ASPECTS OF DEMAND PAGING
Extreme case – start process with no pages in memory
OS sets instruction pointer to first instruction of process, non-memory-resident ->
page fault
And for every other process pages on first access
Pure demand paging
Actually, a given instruction could access multiple pages ➔ multiple page faults
Consider fetch and decode of instruction which adds 2 numbers from memory and
stores result back to memory
Pain decreased because of locality of reference
Hardware support needed for demand paging
Page table with valid / invalid bit
Secondary memory (swap device with swap space)
Instruction restart
Dr. JOHN ZAKI 71
COPY-ON-WRITE
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
Before Process 1 Modifies Page C
Dr. JOHN ZAKI 72
AFTER PROCESS 1 MODIFIES PAGE C
Dr. JOHN ZAKI 73
PAGE REPLACEMENT
What happens if there is no free frame?
Used up by process pages
Also in demand from the kernel, I/O buffers, etc.
Page replacement – find some page in memory, but not really in use, page it
out
Algorithm – terminate? swap out? replace the page?
Performance – want an algorithm which will result in minimum number of page
faults
Same page may be brought into memory several times
Use modify (dirty) bit to reduce overhead of page transfers – only modified
pages are written to disk
Dr. JOHN ZAKI 74
NEED FOR PAGE REPLACEMENT
Dr. JOHN ZAKI 75
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
- Write victim frame to disk if dirty
3. Bring the desired page into the (newly) free frame; update the page
and frame tables
4. Continue the process by restarting the instruction that caused the
trap
Dr. JOHN ZAKI 76
PAGE REPLACEMENT
Dr. JOHN ZAKI 77
PAGE AND FRAME REPLACEMENT ALGORITHMS
1. Frame-allocation algorithm determines
a. How many frames to give each process
b. Which frames to replace
2. Page-replacement algorithm
a. Want lowest page-fault rate on both first access and re-access
3. Evaluate algorithm by running it on a particular string of memory references
(reference string) and computing the number of page faults on that string
a. String is just page numbers, not full addresses
b. Repeated access to the same page does not cause a page fault
c. Results depend on number of frames available
4. In all our examples, the reference string of referenced page numbers is
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1
SUMMARY
01
02
03
04
05
Dr. JOHN ZAKI 90
THANK
YOU
Dr. JOHN ZAKI 91