8 memory management strategies

memory management strategies

1. MemoryManagementStrategies
Background
SwappingSwapping
ContiguousMemoryAllocation
Paging
StructureofthePageTable
Segmentation

2. 1.Background
1.1BasicHardware
•Main memory and registers
are only storage CPU can
accessdirectly
•Register access in one CPU
clock, but, main memory can
takemanycyclestakemanycycles
•Cachesits between main
memoryandCPUregisters
•Protectionofmemoryrequired
toensurecorrectoperation
•A pair ofbaseandlimit
registers define the logical
addressspace
2Loganathan R, CSE, HKBKCE

3. 1.BackgroundContd…
•CPU hardware comparesevery addressgenerated in user mode with the
registers
•A program executing in user mode attempt to access OS memory or other
users' memory results in a trap to the OS, which treats the attempt as a fatal
error
•This prevents a user program from accidentally or deliberately modifying the
codeordatastructuresofeithertheOSorotherusers.
base
base + limit
3Loganathan R, CSE, HKBKCE
CPU
yes
yes
address
≥ <
No
No
Memory
Trap to OS monitor
–addressing error
Hardware Address Protection with base and limit registers

4. 1.2AddressBinding
•A user program will go through several
steps,beforebeingexecutedasshown
•Address binding of instructions and data
to memory addresses can happen at
threedifferentstages
–Compile time: If memory location known
a priori,absolute codecan be generated;
must recompile code if starting location
changesEg.DOS.comPrograms
1.BackgroundContd…
changesEg.DOS.comPrograms
–Load time: Must generaterelocatable
codeif memory location is not known at
compiletime
–Executiontime: Bindingdelayeduntilrun
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)
4Loganathan R, CSE, HKBKCE

5. 1.3Logicalvs.PhysicalAddressSpace
•Logical address– generated by the CPU, also referred asvirtual address
•Physical address – address seen by the memory unit i.e loaded to memory-address
register
•Logical and physical addresses are the same in compile-time and load-time
address-binding schemes; logical (virtual) and physical addresses differ in
execution-timeaddress-bindingscheme
•The run-time mapping from virtual to physical addresses is done by a
hardwaredevicecalledthememory-managementunit(MMU)
1.BackgroundContd…
•InMMU,thevaluein
Dynamic relocation using a relocation
5Loganathan R, CSE, HKBKCE
•InMMU,thevaluein
the relocation register is
added to every address
generated by a user
process at the time it is
senttomemory
•The user program deals
withlogicaladdresses; it
never sees thereal
physicaladdresses
Dynamic relocation using a relocation
register

6. 1.4DynamicLoading
•All routines are kept on disk in a relocatable load format and main program is
loadedintomemoryandisexecuted
•Routineisnotloadeduntilitiscalled
•Therelocatablelinkingloaderiscalledtoloadthedesiredroutine
•Bettermemory-spaceutilizationsinceunusedroutineisneverloaded
•Useful when large amounts of code are needed to handle infrequently
occurringcases
•Nospecialsupportfromtheoperatingsystemisrequiredimplemented
1.BackgroundContd…
Nospecialsupportfromtheoperatingsystemisrequiredimplemented
throughprogramdesign
1.5DynamicLinkingandSharedLibraries
•Linkingpostponeduntilexecutiontime
•Small piece of code,stub, used to locate the appropriate memory-resident
libraryroutine
•Stubreplacesitselfwiththeaddressoftheroutine,andexecutestheroutine
•Operatingsystemneededtocheckifroutineisinprocesses’memoryaddress
•Dynamiclinkingisparticularlyusefulforlibraries
•Systemalsoknownassharedlibraries
6Loganathan R, CSE, HKBKCE

7. 2.Swapping
•A process can be swapped temporarily out of memory to a backing store,
andthenbroughtbackintomemoryforcontinuedexecution
•Similar to round-robin CPU-scheduling algorithm , when a quantum expires,
the memory manager will swap out that process to swap another process
intothememoryspacethathasbeenfreed.
7Loganathan R, CSE, HKBKCE
Swapping of two
processes using a
disk as a backing
store.

8. •Backing store– fast disk large enough to accommodate copies of all memory
imagesforallusersandprovidedirectaccesstothesememoryimages
•Roll out, roll in– swapping variant used for priority-based scheduling
algorithms; lower-priority process is swapped out so higher-priority process
canbeloadedandexecuted
•The swappedoutprocesswillbe swappedback into thesame memory space
it occupied previously due to the restriction by the method of address
binding(assemblyorloadtime)
•A process can be swapped into a different memory space If execution-time
bindingisusedsincephysicaladdressesarecomputedduringexecutiontime
•Systemmaintainsareadyqueueofready-to-runprocesseswhichhave
memoryimagesondisk
2.SwappingContd…
8Loganathan R, CSE, HKBKCE
•Systemmaintainsareadyqueueofready-to-runprocesseswhichhave
memoryimagesondisk
•The dispatcher swaps out a process in memory if there is no free memory
regionandswapsinthedesiredprocessfromareadyqueue
•Major part of swap time is transfer time; total transfer time is directly
proportionaltotheamountofmemoryswapped
•Example:Userprocessis10MB
Backingstoreisaharddiskwithatransferrateof40MBpersec
Transfertime=10/40MBpersec.=250milliseconds
Swaptime=transfertime+Seektime(latency8millisec)= 258millisec.
Total swap time=swap out + swap in = 516 milliseconds
•Modified versions of swapping are found on many systems (i.e., UNIX, Linux,
andWindows)

9. 3.ContiguousMemoryAllocation
•Main memory usually into two partitions:
–Residentoperating system,usually held in low memory with interrupt vector
–Userprocessesthen held in high memory
3.1Memory Mapping and Protection
•Relocation registers used to protect user processes from each other, and from changing
operating-systemcode and data
–Baseregister contains value of smallestphysicaladdress
–Limit register contains range of logical addresses – each logical address must be less
than the limit register
•MMUmapslogicaladdressdynamicallybyaddingtherelocationregister•MMUmapslogicaladdressdynamicallybyaddingtherelocationregister
9Loganathan R, CSE, HKBKCE
Hardware support for
relocation and limit
registers

10. 3.2MemoryAllocation
•Memory is to divide memory into severalfixed-sized partitions, when a partition is free,
a process is loaded into the free partition and when it terminates, the partition
becomesavailable for another process
•Multiple-partition allocation (generalization of the fixed-partition)
–Hole – block of available memory; holes of various size are scattered throughout memory
–OSmaintains information about the allocated partitions and free partitions (hole)
–When a process arrives, it is allocated memory from a hole large enough to accommodate it
–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 setof holes
–Ifthenewholeisadjacenttootherholes,theadjacentholesaremergedtoformonelargerhole
3.ContiguousMemoryAllocationContd…
–Ifthenewholeisadjacenttootherholes,theadjacentholesaremergedtoformonelargerhole
•Dynamic storage allocation problem, which concerns how to satisfy a request of sizen
froma list of free holes and the solutions are:
•First-fit: Allocate thefirsthole that is big enough , Search from beginning or where the
previous first-fitsearch ended
•Best-fit: Allocate thesmallesthole that is big enough, must search entire list, unless
ordered by size,produces the smallestleftoverhole
•Worst-fit: Allocate thelargesthole; must also search entire list, produces the largest
leftoverhole
First-fitand best-fit better than worst-fit in terms of speed and storageutilization
10Loganathan R, CSE, HKBKCE

11. 3.3Fragmentation
•ExternalFragmentation–totalmemoryspaceexiststosatisfya
request,butitisnotcontiguous,i.e.storageisfragmentedintoalarge
numberofsmallholes
•InternalFragmentation–allocatedmemorymaybeslightlylargerthan
requestedmemory;thissizedifferenceismemoryinternaltoa
partition,butnotbeingused
•Reduceexternalfragmentationby
3.ContiguousMemoryAllocationContd…
•Reduceexternalfragmentationby
1Compaction
–Shufflememorycontentstoplaceallfreememorytogetherinone
largeblock
–Compactionispossibleonlyifrelocationisdynamic,andisdoneat
executiontime
2 Permitthelogicaladdressspaceoftheprocessestobe
noncontiguous,thusallowingaprocesstobeallocated physical
memorywhereveravailable
11Loganathan R, CSE, HKBKCE

12. 4.Paging
•Permitsthe physicaladdressspace of a process to be noncontiguous
4.1BasicMethod
•Divide physicalmemory into fixed-sized blocks calledframes(size is power of 2)
•Divide logical memory into blocks of samesize calledpages
•Thebacking store is divided into fixed-sized blocks of size of frames
•Hardware supportfor paging i.e. a page table to translate logical to physical addresses
12Loganathan R, CSE, HKBKCE

13. •AddressgeneratedbyCPUisdividedinto:
Page number (p)– used as an index into apage tablewhich contains base
addressofeachpageinphysicalmemory
Page offset (d)– combined with base address to define the physical memory
addressthatissenttothememoryunit
4.PagingContd…
•For given logical address space
2
m
and page size2
n
thenm – n
bits of a logical address
designatethepagenumber,
13Loganathan R, CSE, HKBKCE
Paging Model of Logical
and Physical Memory
page number page offset
p d
m - n n
designatethepagenumber,
and then low-order bits
designatethepageoffsetas:
where p is an index into the
page table and d is the
displacementwithinthepage

14. 4.PagingContd…
Paging example for a 32-byte(2
5
)
memory with logical address of 16 byte
(2
4
) and 4-byte(2
2
) pages i.e. m=4 & n=2
For logical address 0 is page 0, offset 0
Indexing into the page table, find that
page 0 is in frame 5
Logical address 0 maps to physical
address = 5(frame number) x 4(page
32-byte memory and 4-byte pages
14Loganathan R, CSE, HKBKCE
size) + 0(offset) = 20
Logical address 3 (page 0, offset 3)
maps to physical address = 5x4+ 3 = 23
Logical address 13(page 3, offset 1)
indexing to page 3 find frame number 2
which maps to physical address = 2x4
+ 1 = 9

15. 4.PagingContd…
In paging no external fragmentation:Any freeframe can be allocated to a process
that needs it, but, may have some internal fragmentation i.e.last frameallocated
maynotbecompletelyfull
Iftheprocessrequiresnpages, Ifnframesareavailable, theyareallocated
The first page of the
process is loaded into one
of the allocated frames,
and the frame number is
put in the page table for
thisprocess.
Before allocation After allocation
15Loganathan R, CSE, HKBKCE
thisprocess.
The next page is loaded
into another frame, and its
frame number is put into
the page table and so on
OS keeps tracks of which
frames are allocated,
which frames are
available, how many total
frames are there, and so
on in a frame table

16. 4.2HardwareSupport
•Hardware implementation of Page Table is a set of high speed dedicated
Registers
•Pagetableiskeptinmainmemoryand
•Page-tablebaseregister(PTBR)pointstothepagetable
•Page-tablelengthregister(PTLR)indicatessizeofthepagetable
•The CPU dispatcher reloads these registers, instructions to load or modify the
page-tableregistersareprivileged
•Inthisschemeeverydata/instructionaccessrequirestwomemoryaccesses.
4.PagingContd…
•Inthisschemeeverydata/instructionaccessrequirestwomemoryaccesses.
Oneforthepagetableandoneforthedata/instruction.
•The two memory access problem can be solved by the use of a special fast-
lookup hardwarecachecalledassociative memoryortranslation look-aside
buffers(TLBs)
•TLB entry consists a key (or tag) and a value, when it is presented with an item,
theitemiscomparedwithallkeyssimultaneously
16Loganathan R, CSE, HKBKCE
Page # Frame #

17. 4.PagingContd…
•When page number from CPU address is presented to the TLB, if the page
number is found, its frame number is immediately available and is used to
accessmemory.
•If the page number is not in the TLB (known as a TLB miss), a memory
reference to the page table must be made, also the page number and frame
numbertotheTLB.
•If the TLB is full, the
OS select one entry
forreplacement.
•Replacement
17Loganathan R, CSE, HKBKCE
PagingHardware With TLB
•Replacement
policies range from
LRUtorandom
•TLBs allow entries
(for kernel code)to
be wired down, so
that they cannot be
removed from the
TLB.

18. 4.PagingContd…
•Some TLBs store address-space identifiers (ASIDs) in each TLB
entrywhichidentifieseachprocessandisusedtoprovideaddress-
spaceprotectionforthatprocess
•TLBmustbeflushed(orerased)toensurethatthenextexecuting
processdoesnotusethewrongtranslationinformation
•Thepercentageoftimesthataparticularpagenumberisfoundin
theTLBiscalledthehitratio
4.3Protection
•Memoryprotectionimplementedbyassociatingprotectionbit
18Loganathan R, CSE, HKBKCE
•Memoryprotectionimplementedbyassociatingprotectionbit
witheachframe,Valid-invalidbitattachedtoeachentryinthe
pagetable:
–“valid”indicatesthattheassociatedpageisintheprocess’s
logicaladdressspace,andisthusalegalpage
–“invalid”indicatesthatthepageisnotintheprocess’slogical
addressspace

19. 4.PagingContd…
19
Loganathan R, CSE, HKBKCE
Valid(v)orInvalid(i)BitInAPageTable

20. 4.4SharedPages
•An advantage of paging is the
possibility ofsharingcommon
code
•If the code isreentrant code
(orpurecode),itcanbeshared
•One copy of read-only
(reentrant) code shared among
processes (i.e., text editors,
compilers,windowsystems).
4.PagingContd…
compilers,windowsystems).
•Shared code must appear in
same location in the logical
addressspaceofallprocesses
•Each process keeps a separate
copyofthecodeanddata
•The pages for the private code
and data can appear anywhere
inthelogicaladdressspace
20Loganathan R, CSE, HKBKCE
Sharing of code in a paging environment

21. 5.StructureofthePageTable
5.1HierarchicalPaging
•Break up the logical address space into
multiple page tables
•Asimple technique is a two-levelpage table
•A logical address (on 32-bit machine with 1K
page size) is divided into a page number
consisting of 22 bits and a page offset
consistingof10bits
Techniquesforstructuringthepagetable:1.Hierarchical
Paging 2.HashedPageTables3.InvertedPageTables
consistingof10bits
•Since the page table is paged, the page
number is further divided into a 12-bit page
number a 10-bit page offset
wherep
iis an index into the outer page
table, andp
2is the displacement within the
pageof the outer page table
21Loganathan R, CSE, HKBKCE
Two-LevelPage-Table Scheme
page number page offset
p
i
p
2 d
1210 10

22. •Address-TranslationSchemeforatwo-level32-bitpagingarchitecture
5.StructureofthePageTableContd…
•Three-levelPagingScheme
•Example64bitlogicaladdress
22Loganathan R, CSE, HKBKCE
Using two-level paging scheme
Using three-level paging scheme

23. 5.2HashedPageTables
•Commoninaddressspaces>32bits
•Thevirtualpagenumberishashedintoapagetable.Thispagetablecontains
achainofelementshashingtothesamelocation.
•Virtual page numbers are compared in this chain searching for a match. If a
matchisfound,thecorrespondingphysicalframeisextracted.
5.StructureofthePageTableContd…
23
Loganathan R, CSE, HKBKCE
HashedPageTable
p &q - page numbers
s&r - frame numbers

24. 5.3InvertedPageTable
•Oneentryforeachrealpageofmemory
•Entry consists of the virtual address of the page stored in that real memory
location,withinformationabouttheprocessthatownsthatpage
•Decreases memory needed to store each page table, but increases time
neededtosearchthetablewhenapagereferenceoccurs
•Use hash table to limit the search to one — or at most a few — page-table
entries
5.StructureofthePageTableContd…
24
Loganathan R, CSE, HKBKCE
Inverted Page TableArchitecture

25. 6.Segmentation
•Memory-management scheme that supports user view of memory i.e. a
collection of variable-sized segments, with no necessary ordering among
segments
6.1BasicMethod
•Segments are numbered and are referred to
by a segment number i.e. a logical address
consistsofatwotuple:
<segment-number,offset>
•Aprogramisacollectionofsegments,
User's view of a program
25Loganathan R, CSE, HKBKCE
•Aprogramisacollectionofsegments,
compilerconstructsseparatesegmentsfor:
•Thecode
•Globalvariables
•Theheap,fromwhichmemoryis
allocated
•Thestacksused,byeachthread
•ThestandardClibrary

26. 6.2Hardware
•Segmenttable–maps2dimensionalphysicaladdresses,eachtableentryhas:
–base–containsthestartingphysicaladdresswherethesegmentsresidein
memory
–limit–specifiesthelengthofthesegment
6.SegmentationContd…
•Segment-table base
register (STBR)points to
the segment table’s
locationinmemory
•Segment-tablelength
26Loganathan R, CSE, HKBKCE
•Segment-tablelength
register (STLR)indicates
number of segments
usedbyaprogram;
Segment numbersis legal
ifs<STLR
Segmentation
hardware.

27. 6.SegmentationContd…
• Segment 2 is 400
bytes long and begins
at location 4300. Thus,
a reference to byte 53
of segment 2 is
mapped onto location
4300 + 53 = 4353
• Segment 3, byte 852,
is mapped to 3200 (the
baseofsegment3)+
27Loganathan R, CSE, HKBKCE
ExampleofSegmentation
baseofsegment3)+
852 = 4052
• A reference to byte
1222 of segment 0
would result in a trap
to the operating
system, as this
segment is only 1,000
bytes long