Transcript os-4

Operating Systems
Part IV: Memory
Management
Main Memory
Large array of words or bytes each having
its own address
 Several processes must be kept in main
memory to improve utilization and system
response: memory sharing
 Memory management algorithms vary
from simple approach to paging and
segmentation strategies

Memory Basics

Types of memory addresses
–
–
–

Symbolic (e.g. program variables)
Relocatable (e.g. offset + 100)
Absolute (e.g. 255)
Address binding: Which data goes where. May be
determined in any of the following phases
–
–
–
Compile time: compiler generates absolute code for
execution in a fixed address
Load time: compiler generates relocatable code, linkloader computes relocation addresses during link time
Execution time: allows executing processes to move, by
simply changing values of segment registers.
Logical & Physical Addresses


Logical or virtual address – address generated by
the CPU.
Physical address – address loaded into the
memory-address register of RAM
–
–
–
Compile-time and load-time binding generate
identical logical and physical addresses
Execution-time binding generate differing logical
and physical addresses
Memory management unit – maps virtual to
physical addresses during runtime.
Improving Memory Utilization

Dynamic loading
–

Dynamic linking
–
–

Subroutines are stored on disk in relocatable format, and
are not loaded until called
Linking to subroutine libraries postponed until run-time;
stub used as pointer to routine in a shared DLL.
Conserves disk space – a single copy of library is shared
by all executing processes. Versioning issue.
Overlays
–
–
Keeps only needed instructions in memory
Other instructions overwrite previously occupied address
when needed. May be implemented by programmer.
Swapping


Used if memory
is no longer
sufficient
The roll out
(swap out to
disk) and roll in
(swap to MM)
drastically
increases time
for context switch
Swapping
Needs a fast backing store (secondary
memory) for efficient implementation
 Waiting processes are good candidates to
be swapped out to disk
 Processes waiting on I/O should not be
swapped out, since the I/O could be into
their address space, or I/O should be done
into OS buffers only.

Swapping


Modified version of swapping used in Unix.
Swapping normally disabled. Enabled when
memory runs out due to many running
processes.In Linux, only R/W data segment
needs to be swapped out, R/O code segment
are just overwritten, since it can be reread from
disk.
Microsoft Windows provides partial swapping - if
not enough memory for a new program, current
program is swapped out to disk. User
determines swap rather than scheduler
Memory Protection




OS must protect itself from user processes, and
must protect user processes from each other.
Each process is assigned a relocation register
and a limit register.
Relocation register contains the value of the
smallest physical address.
Logical address must be less than the limit
register
How memory protection works

Contiguous Allocation
Type of allocation where each process
occupies only a single continuous block in
main memory
 Simple two-partition scheme

–
–
Low memory: usually contains resident O/S
since interrupt vectors are here
Rest of memory: for user processes
Contiguous Allocation

Multiple-Partition Algorithm
–
Simplest is multiple fixed partition
 Each
partition is allocated to a process
 Multiprogramming limited to number of partitions
–
Dynamic partitioning
 Starts
with one large memory block called a “hole”
 Processes arrive and are allocated a block
 Holes become available as processes terminate
Contiguous Allocation

Multiple-Partition Algorithm
–
Dynamic Partitioning (cont’d)
OS
OS
OS
OS
process 5
process 5
process 5
process 5
process 9
process 9
process 8
process 2
process 10
process 2
process 2
process 2
Contiguous Allocation

Dynamic storage allocation problem
–
–
looking for freed memory for waiting processes
set of holes searched to see w/c one to allocate



–
–
first-fit - allocate first hole big enough for process (search
may start from beginning or end)
best-fit - allocate smallest hole that is big enough
worst-fit - allocate largest hole -> produces largest leftover
(sometimes useful than smaller ones)
first/best better in time/storage utilization, respectively
first-fit is generally faster
Contiguous Allocation

Fragmentation
–
External


–
Enough memory exists but not contiguous
50% rule - given N allocated blocks, the next 0.5N blocks will
be lost due to fragmentation (1/3 is unusable) when first-fit is
used.
Internal

Allocate memory in fixed-sized units, say 4k blocks. Memory
actually allocated to a process may be slightly larger than
requested memory. The difference is internal fragmentation.
Contiguous Allocation

Compaction
–
–
–
–
–
–
A solution to external fragmentation – shuffle memory contents to
place all free memory together in one large block.
Not always possible if relocatable addressing at execution time
is not supported
Algorithm 1: move processes to one end (expensive if many
processes are moved)
Algorithm 2: create big hole in the middle
Swapping may be combined w/ compaction
 processes rolled out to backing store then back in
compaction not possible w/ disk due to slow access
Paging





Allows non-contiguous allocation -> solves external
fragmentation
Logical memory
– Fixed sized blocks called pages
Physical memory
– Fixed-sized blocks called frames
Page table converts pages to frames, using address
translation hardware
– page# + offset -> frame# + offset, using page table
Backing store (swap partition in Linux)
– same structure as logical memory
Paging Examples
Internal Fragmentation in Paging
External fragmentation is eliminated but
internal fragmentation is not since
processes rarely take up all the memory
space allocated to them
 Worst case:

–
–
Process needs (n pages + 1 byte)
Wasted space of (page size bytes – 1 byte)
Page Table Structure

Each O/S has own method for storing page tables ->
most allocate a page table per process

Context-switch time increases with paging due to
need to store page tables in PCB of each process

Each page table entry might include access type as
r/o (constant data), r/w (variable data), or x/o (code),
to implement a further level of memory protection

Page table structure: linear, multilevel hierarchical,
hashed, inverted.
Shared Pages

Shared read-only/execute-only code
–


When several instances of a single program are
running, only one copy of the program code is stored
in memory, but each instance has its own program
data. Code must be reentrant.
Possibility of sharing common code is another
advantage of paging
Similar to sharing of address space of a task by
threads.
Shared Pages: An Example
Segmentation
Scheme divides logical memory into
segments
 More intuitive view of memory from user’s
point of view (e.g. program divided into
segments -- subroutines, procedures, data
-- that have different length)

Logical View of Segmentation
1
4
1
2
3
user space
4
2
3
physical memory space
Segmentation Hardware




Logical (2-dimensional) vs. physical (1dimensional) -> mapping effected through a
segment table
Entry consists of segment base (=starting
address in physical memory) and limit (= length
of segment)
Similar to concept of pages except segments do
not have fixed length
Intel 80x86 is based on segmentation
Mapping Segments to Physical
Memory
Segments and Fragmentation
Segmentation may cause external
fragmentation
 Happens when all free blocks are too
small to accommodate a segment
 Compaction may be used to solve the
problem
 Process may wait if segment cannot be
found

Segmentation with Paging
Solves the external fragmentation problem
of pure segmentation
 Each segment is composed of several
equal-sized pages
