Transcript File

Memory Management
1
Address Binding
 The normal procedures is to select one of the
processes in the input queue and to load that
process into memory.
 As the process executed, it accesses instructions and
data from memory, when the process terminates,
and its memory space is declared available.
 Most systems allow a user process to reside in any
part of the physical memory.
 Address space of the computer starts at 00000,
addresses may be represented in different ways.
2
3
 Addresses in the source program are
generally symbolic. A compiler will
typically bind these symbolic addresses
to re-locatable addresses.
 The linkage editor or loader will in turn
bind these re-locatable addresses to
absolute addresses.
 Each binding is a mapping from one
address space to another.
4
 The binding instruction and data to memory
address can be done at any step along the way:
 Compile time
 Load time
 Execution time
5
Compile Time
 If you compile time where the process will
reside in memory, the absolute code can be
generated. For example, if you know a priori
that a user process resides starting at location
R, then the generated compile time will start at
that location and extend up from there.
 Absolute code : - A code used when the
addresses in a program are to be written in
machine language exactly as they will appear
when the instructions are executed by the
control circuits.
6
Load time
 If it is not known at compile time
where the process will reside in
memory, then the compiler must
generate re-locatable code.
 In this case, final binding is delayed
until load time. If the starting address
changes, we need only to reload the
user code to incorporate this changed
value.
7
Execution time
 If the process can be moved during its
execution from one memory segment to
another, then binding must be delayed until
run time.
8
Dynamic Loading
 The entire program and data of a process must be




9
in physical memory for the process to execute.
To obtain better memory-space utilization, we can
use dynamic loading.
With dynamic loading, a routing is not loaded until
it is called.
All routines are kept on disk in re-locatable load
format. The main program is loaded into memory
and is executed.
When routine needs to call another routine, the
calling routine first checks to see whether the
other routine has been loaded.
 If not, the re-locatable linking loader is called
10
to load the desired routine into memory and
to update the program’s address tables to
reflect this change.
 The advantage of dynamic loading is that an
unused routines is never load.
 Useful when large amounts of code are
needed to handle infrequently occurring
cases.
 Dynamic loading does not require support
from operating system. The designer job is to
design their program to take advantage of
such method.
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
 The compile time and load-time address binding
generate identical logical and physical address.
 However, the execution-time address binding
scheme results in differing logical and physical
addresses.
 We usually refer to the logical address as a virtual
address
11
Memory Management Unit (MMU)
 The run-time mapping from virtual to physical addresses is done
by a hardware called the memory-management unit(MMU).
12
Swapping
 A process can be swapped temporarily out
of memory to a backing store, and then
brought back into memory for continued
execution.
 For example, a round robin scheduling
algorithm. When quantum expires, the
memory manager will start to swap out the
process that just finished, and to swap in
another process to the memory space that
has been freed.( see figure on next slide).
13
Schematic View of Swapping
14
 Roll out, roll in – swapping variant used for
priority-based scheduling algorithms; lowerpriority process is swapped out so higher-priority
process can be loaded and executed.
 A process that is swapped out will swapped back
into memory at same location that previously
occupied.
 This restriction is dictated by the method of
address binding.
 If binding is done at assembly or load time, then
process can not move at different location but
binding is done at execution time then a process
can be swapped into a different memory space.
15
 Swapping requires a backing store. Fast disk
large enough to accommodate copies of all
memory images for all users; must provide
direct access to these memory images.
16
Contiguous Memory Allocation
 The main memory must accommodate both the
operating system and the various user
processes.
 Main memory usually into two partitions:
 Resident operating system, usually held in low
memory with interrupt vector
 User processes then held in high memory.
17
Concept(Base & Limit Register)
 To separate each program’s memory space, we
18
need the ability to determine the range of legal
addresses that the program may access, and to
protect the memory outside the space.
 We can provide this protection by using two
registers. i.e. Base register and Limit register.
 The base register hold the smallest legal physical
memory address; the limit register contains the size
of range.
 For example, if the base register holds 300040 and
limit register is 120900 then the program can legally
access all addresses from 300040 through 420940
inclusive.
 This protection is accomplished by the CPU
hardware
comparing
every
address
generated in user mode with registers.
 Any attempt by a program executing in user
node to access monitor memory or other
users memory results in trap to the monitor,
which treats the attempts as a fatal error.
 This scheme prevents the user program from
modifying the code or data structure of
either the operating system or other users.
19
Memory Protection
 Protecting the operating system from user
20
processes, and protecting user processes from
one another.
 The relocation register contains the value of
smallest physical address; the limit register
contains the range of logical addresses.
 With relocation and limit register , each logical
address must be less than limit register.
 The MMU maps the logical address
dynamically by adding the value in the
relocation register.
 When the CPU scheduler selects a process for




21
execution, the dispatcher load the relocation and
limit registers with correct values.
Every address generated by the CPU is checked
against these registers.
The relocation register scheme provides an effective
way to allow the OS size to change dynamically.
For example, the OS contains code and buffer space
for device drivers. If a device driver not in used, we
do not need to keep the code and data in memory
so we can able to allocate the space for another
purpose.
Such code is some times called transient OS code.
Relocation
Register
Limit
Register
Yes
CPU
22
Logical
Address
<
No
+
Physical
Address
MEMORY
Memory Allocation
 One of simplest methods for memory allocation is to divide
memory into several fixed-sized partitions.
 Each partitions may contain exactly one process. In multipartition method, when a partition is free, a process is selected
from the input queue and loaded into the free partition. When
process terminates, the partition will be available for another
process.
 The operating system keeps table indicating which parts of
memory are available and which are occupied.
 Initially, all memory is available for user processes, and is
considered as one large block of available memory, a hole.
23
 When process arrives, it search for a hole large
24
enough, if it is found, we allocate only as much
memory as is needed, keeping the rest of another
processes.
 A set of holes, of various sizes, is scattered throughout
memory at any given time.
 When process arrives and needs memory, system
search this set of hole that is large enough for this
process.
 If the hole is too large, it is split into two parts: one
part is allocated to the arriving process; the other is
returned to the set of holes.
 When a process terminates, it release block of
memory, which is then placed back in the set of holes.
 This procedure is a particular instance of the general
dynamic storage allocation problem, which is how
to satisfy a request of size n form a list of free holes.
 There are many solutions to this problem, which are
listed below:
(1) First fit
(2) Best fit
(3)Worst fit
25
 First fit : allocate the first hole that is big enough.
26
Searching can start either at the beginning of the set of
holes or where the previous first-fit search ended. We
can stop searching as we find a free hole that is large
enough.
 Best fit : allocate the smallest hole that is big
enough. We must search the entire list, unless the list
is kept ordered by size. This strategy produces the
smallest leftover hole.
 Worst fit : allocate the largest hole. Again, we must
search the entire list, unless it is sorted by size. This
strategy produces the largest leftover hole, which may
be more useful than the smaller leftover hole from a
best fit approach.
 Simulations have shown that both first fit and best fit are
better than worst fit in terms of decreasing both time and
storage utilization.
 Neither first fit not best fit is clearly better in terms of
storage utilization, but first fit is generally faster.
 These algorithm, however, suffer from external
fragmentation. As processes are loaded and removed from
memory, the free space is broken into little pieces.
 External fragmentation exists when enough total memory
space exists to satisfy a request, but it not contiguous;
storage is fragmented into a large number of small holes.
27
28
Example
 Given memory partitions of 100K, 500K, 200K,
300K, and 600K (in order), how would each of
the First-fit, Best-fit, and Worst-fit algorithms
place processes of 212K, 417K, 112K, and 426K
(in order)?
 Which algorithm makes the most efficient use of
memory?
29
Answer
 First Fit
 212K is put in 500K partition
 417K is put in 600K partition
 112K is put in 288K partition (new partition 288K =
500K - 212K)
 426K must wait
30
 Best fit
 212K is put in 300K partition
 417K is put in 500K partition
 112K is put in 200K partition
 426K is put in 600K partition
 Worst fit
 212K is put in 600K partition
 417K is put in 500K partition
 112K is put in 388K partition
 426K must wait
31
Fragmentation
 Memory allocation can be internal as well as external
 Consider a multiple partition allocation scheme with a hole




32
of 18,464 bytes.
Suppose that the next process requests 18,462 bytes. If we
allocate exactly the requested block, we are left with a hole
of 2 bytes.
The overhead to keep track of this hole will be substantially
larger than the hole itself.
The general approach is to break the physical memory into
fixed-sized blocks, and allocate memory in unit of block.
With this approach memory allocated to a process may be
slightly larger than requested memory.
 Internal fragmentation : - occurs when memory is
divided into fixed-sized partitions(e.g. page frames in
main memory, physical block on disk). If a block of data
is assigned to one or more partitions, then there may be
wasted space in the last partition. This will occur if the
last portion of data is smaller than the last partition.
 External fragmentation : - Occurs when memory is
divided into variable-sized partitions corresponding to
the blocks of data assigned to the memory(e.g. segments
in main memory). As segments are moved into and out
of the memory, gaps will occur between the occupied
portions of memory.
33
 There is a hole of 300K and 600K in multiple
partition allocation scheme. Next process request for
700k of memory is free which satisfy the request but
hole is not contiguous.
 So there is an external fragmentation of memory. The
selection of first fit versus best fit can affect the
amount of fragmentation.
 Depending on the total memory of memory storage
and the average process size, external fragmentation
may be either minor or major problem.
34
P50
Hole of 600k
Hole of 300k
OS
35
 One technique for overcoming external fragmentation is
compaction. From time to time, the operating system shifts
the processes so that they are contiguous and all the free memory
is together in one block.
36
 Compaction implies the need for a dynamic
relocation capability. If relocation is static and
done at assembly or load time, compaction can
not be done. Relocation is done at execution
time, the compaction is possible cost is the major
factor for compaction.
 The simplest algorithm of compaction is, the
process moves towards one side of memory. It
produces one large hole of available memory. But
cost of this scheme can be more.
37
Terms
 Page : in virtual storage, a fixed length block that has a
virtual address and that is transferred as a unit between main
memory and secondary memory.
 Paging : - the transfer of pages between main memory and
secondary memory.
 Physical address : - The absolute location of a unit of data
in memory ( e.g. word or byte in main memory, block on
secondary storage).
38
Paging
 Physical memory is divided into fixed-size blocks
called frames and the logical memory is divided
into the fixed-size blocks called pages.
 The size of a page is same as that of frame.
 The key idean of this method is to place the pages
of a process into the available frames of memory,
whenever, this process is to be executed.
 The hardware support for paging is illustrated in
figure( next slide for image).
 The page size is same as frame size.
39
40
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
41
Example
 Using a page size of 4 bytes and a physical memory of 32 bytes(8 pages).
42
 We will see how the user’s view of memory can be mapped into




43
physical memory.
Logical address 0 is page 0, offeset 0. Indiexing into the page
table, we find that page 0 is in frame 5.
Thus , logical address 0 maps to physical address
20(=5 x 4 ) + 0 ).
Logical address 3 (page 0, offset 3) maps to physical address
23(=(5 x 4 + 3).
Logical address 4 is page 1, offset 0; according to page table,
page 1 is mapped to frame 6. thus, logical address 4 maps to
physical address 24(=6 x 4) + 0).
Hardware Support on Paging
 To implement paging, the simplest method is to






44
implement the page table as a set of registers.
These registers should be built with very high-speed
logic to make the paging-address translation efficient.
Every access to memory must go through the paging
map, so efficiency is major factor.
The CPU dispatcher reloads the registers, just as it
reloads the other registers.
Instruction to load or modify the page-table registers
are, of course, so that only OS can change the
memory map.
However, the size of register is limited and the size of
page table is usually large
Therefore, the page table is kept in main memory
Hardware Support on Paging
 If we want to access location I, we must first
index into page table, this requires one
memory access
 With this scheme, TWO memory access are
needed to access a byte
 The standard solution is to use a special,
small, fast cache, called Translation lookaside buffer (TLB) or associative memory
45
TLB
 The TLB is associative, high-speed memory. Each
46
entry in the TLB consists of two parts: a key(or
tag) and a value.
 When the associative memory is presented with
an item, it is compared with all keys
simultaneously.
 If the item is found, the corresponding values
field is returned.
 The search is fast; the hardware; however is
expensive. Typically the number of entries inn a
TLB is small, often numbering between 64 and
1,024
TLB
47
TLB
 If the page number is not in the TLB (TLB
miss) a memory reference to the page
table must be made.
 In addition, we add the page number and
frame number into TLB
 If the TLB already full, the OS have to
must select one for replacement
 Some TLBs allow entries to be wire
down, meaning that they cannot be
removed from the TLB, for example
kernel codes
48
TLB
 The percentage of times that a particular page
49
number is found in the TLN is called hit ratio
 If it takes 20 nanosecond to search the TLB and
100 nanosecond to access memory, then a
mapped
memory
access
takes
120
nanoseconds when the page number is in the
TLB.
 If our hit ratio is 80%, the effective memory
access time equal:
0.8*(100+20) + 0.2 *(100+100)=140 nanosec
 If our hit ratio is 98%, the effective memory
access time equal:
0.98*(100+20) + 0.02 *(100+100)=122 nanosec
 Disadvantage of TLB is that: if two pages use the same
entry of the memory, only one of them can be
remembered at once, if process is referencing both pages
at same time.TLB does not work very well.
50
Segmentation
 Since the user’s view of memory is not the same
as the actual physical memory, segmentation
helps user to view memory as a collection of
variable-size segment
 Segmentation is a memory management scheme
that supports user view of memory.
51
Segmentation
A program is a collection of segments. A segment is a logical
unit such as:









52
main program,
procedure,
function,
method,
object,
local variables, global variables,
common block,
stack,
symbol table, arrays
53
 Segmentation is memory-management scheme
that supports this user view of memory.
 A logical address space is a collection of
segments. Each segment has a name and length.
 The addresses specify both the segment name and
the offset within the segment.
 The user therefor specifies each address by two
quantities: a segment name and an offset.
54
55
Segmentation
 The user specifies each address by two quantities:
a segment name and an offset
<segment-number, offset>
 Compare with page scheme, user specifies only a
single address, which is partitioned by hardware
into a page number and an offset, all invisible to
the programmer
56
Segment Hardware
 Although the user can refer to objects in the
program by a two-dimensional address, the
actual physical address is still a one-dimensional
sequence
 Thus, we need to map the segment number
 This mapping is effected by a segment table
 In order to protect the memory space, each
entry in segment table has a segment base and
a segment limit.
57
 The segment base contains the starting physical address
where the segment resides in memory, whereas the segment
limit specifies the length of the segment.
58
59
 A logical address consists of two parts: a
segment number, s, and an offset into that
segment, d.
 The segment number is used as an index into the
segment table. The offset d of the logical
address must be between 0 and the segment
limit.
 If it is not, we trap to the Operating system. If
this offset is legal, it is added to the segment
base to produce the address in physical memory
of the desired byte.
 The segment table is thus essentially an array of
base-limit register pairs.
60
Example of Segmentation
61
 Consider the figure of previous slide.
 We have five segments numbered from 0 to through
4. the segment are stored in physical memory as
shown.
 The segment table has a separate entry for each
segment, giving the beginning address of the segment
in physical memory(or base) and the length of that
segment.
62
Difference between Segmentation and Paging
 Segment is logical unit, visible to user’s program and is of
arbitrary size.
 A page is “physical unit”, invisible to the user’s program and
is of fixed size.
63
Comparison of paging and segmentation
64
Virtual Memory
 Virtual memory is a technique that allows the execution of
processes that may not completely in memory.
 One major advantages of this scheme is that programs can be
larger than physical memory.
 Further, virtual memory abstract main memory into an
extremely large, uniform array of storage, separating logical
memory as viewed by the user from physical memory
 Virtual memory also allows processes to easily share files and
address space, and it provides mechanism for process
creation.
65
 The ability to execute a program that is only partially
in memory would consult many benefits.
1) A program would no longer be constrained by the
amount of physical memory that is available. User
would be able to write programs for an extremely
large virtual-address space, simplifying the
programming task.
2) Because each user program could take less physical
memory, more program could be run at the same
time, with a corresponding increase in CPU
utilization and throughput, but with no increase in
response time or turnaround time.
3) Less I/O would be needed to load or swap each user
program into memory, so each user program would
run faster.
66
Background
 The instruction being executed must be in physical
67
memory. The first approach to meeting this
requirement is to place entire logical address space
in physical memory.
 Virtual memory is the separation of user logical
memory from physical memory. This separation
allows an extremely large virtual memory to be
provided for programmers when only a smaller
physical memory is available.
 Virtual memory makes the task of programming
much easier, because the programmer no longer
needs to worry about the amount of physical
memory available.
Demand Paging
 A demand paging is similar to a paging system with




68
swapping.
Processes reside on secondary memory (i.e. disk).
When we want to execute a process, we swap into
memory.
Rather than swapping the entire process into memory,
we use a lazy swapper.
A lazy swapper never swaps a page into memory
unless that page will be needed.
A swapper manipulate entire processes, whereas a
pager concerned with the individual pages of a
process.
Concept
 When a process is to be swapped in , the
pager guesses which pages will be used
before the process is swapped out again.
 Instead of swapping in a whole process, the
pager bring only those necessary pages into
memory.
 It avoids reading into memory pages that
will not be used anyway, decreasing the
swap time and the amount of physical
memory needed.
69
Transfer of a Paged Memory to Contiguous Disk Space
70
 With this scheme, we need some form of
hardware support to distinguish between those
pages that are in memory and those pages that
are one the disk.
 The valid-invalid bit scheme can be used for this
purpose.
 When the bit is set to “valid”, this value indicates
that the associated page is both legal and in
memory.
 If the bit is set to “invalid”, this value indicates
that the page either is not valid( that is, not in the
logical address space of the process), or is valid
but is currently on the disk.
71
 The page-table entry for a page that is brought
into memory as usual, but the page-table entry for
a page that is not currently in memory is simply
marked invalid, or contains the address of the
page on disk. This situation is shown in next slide.
72
Page Table When Some Pages Are Not in Main Memory
73
 If the process tries to access a page that was not
brought into memory? Access to a page marked
invalid causes a page-fault trap.
 The procedure for handling this page fault is
straightforward. See next slide for figure.
74
Steps in Handling a Page Fault
75
1)
2)
3)
4)
5)
6)
76
We check an internal table for this process, to
determine whether the reference was a valid or
invalid memory access.
If the reference was invalid, we terminate the
process. If it was valid, but we have not yet brought
in that page, we now page it in.
We find a free frame.
We schedule a disk operation to read the desired
page into the newly allocated frame.
When the disk read is complete, we modify the
internal table kept with the process and the page
table to indicate that page is now in memory.
We restart the instruction that was interrupted by
the illegal address trap.
Page Replacement
 Over-allocation demonstrates itself as follows.
While a user process is executing, a page fault
occurs.
 The hardware traps to the operating system, which
checks its internal tables to see that this page fault
is genuine one rather than an illegal memory
access.
 The operating system determines where the
desired page is residing on the disk, but then finds
that there are no free frames on the free frame list.
 All memory is in use( see next slide for figure)
77
Need For Page Replacement
78
 Reference String : - we evaluate an algorithm by running
it on a particular string of memory and computing the
number of page faults. The string of memory reference is
called a reference string.
79
FIFO Page replacement
 A FIFO replacement algorithm associates with
each page the time when that page was brought
into memory.
 When a page must be replaced, the oldest page is
chosen.
 We replace the page at the head of the queue.
When a page is brought into memory, we insert it
at the tail of the queue.
 FIFO page replacement algorithm is easy to
understand and program. However, its
performance is not always good.
80
 Let us consider the following string
0,1,2,3,0,1,2,3,0,1,2,3,4,5,6,7
Belady’s anomaly:
For some page replacement algorithms, the page fault rate may
increase as the number of allocated frames increase. FIFO page
replacement algorithm may space this problem.
81
82
LRU Page Replacement
 LRU replacement associates with each page
the time of that page the time of that page’s
last use.
 When a page must be replaced, LRU choose
that page that has not been used for the
longest period of time.
 This strategy is the optimal pagereplacement algorithm looking backward in
time, rather than forward.
83
84
Optimal Page Replacement
 The optimal policy selects for replacement that page for
which the time to the next reference is the longest.
 An optimal page replacement algorithm has the lowest page
fault rate of all algorithms, and will never suffer from
Belady’s anomaly.
 This algorithm is impossible to implement because it would
require the operating system to have perfect knowledge of
future events.
 The optimal page replacement algorithm says the page with
the highest label should be removed.
85
86
Example
 Page Reference String : -
5,4,3,2,1,4,3,5,4,3,2,1,5
Count FIFO , LRU
87
Second Chance Algorithm(Clock)
 The basic algorithm of second-chance replacement is




88
a FIFO replacement algorithm.
When a page has been replaced, however, we inspect
its reference bit.
If the value is 0, we proceed to replace this page. If the
reference bit is set to 1, however, we give that page a
second chance and move on to select the next FIFO
page.
When a page gets a second chance, its reference bit is
cleared and its arrival time is reset to the current time.
Thus, a page that is given a second chance will not be
replaced until all other pages are replaced,
 One way to implement the second chance algorithm is
as a circular queue.
 A pointer indicates which page is to be replaced next.
When a free is needed, the pointer advances until it
finds a page with 0 reference bit.
 As it advances, it clears the reference bits.
 Once a victim page is found, the page is replaced, and
the new page is inserted in the circular queue in that
position.
89
Thrashing
 If a process does not have “enough” pages, the page-fault rate




90
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