7. Memory management in operating system.ppt

Memory management in operating system.

1. Memory Management
Dr. M. Bilal Qureshi

2. Background
•Programmustbebrought(fromdisk)into
memoryandplacedwithinaprocesstorun
•Mainmemoryandregistersareonlystorage
thatCPUcanaccessdirectly
•RegistersareaccessedinoneCPUclock(or
less)
•Mainmemorycantakemanycycles
•CachesitsbetweenmainmemoryandCPU
registers
•Protectionofmemoryrequiredtoensure
correctoperation

3. Basic Concepts
•Memoryconsistsofalargearrayofwordsor
bytes,eachwithitsownaddress.
•Instruction-fetch-executioncycle,e.g.,first
fetchesaninstructionfrommemory,whichis
thencodedandexecuted.
•Operandsmayhavetobefetchedfrom
memory.Afterinstructionhasbeenexecuted,
theresultsarestoredbackinmemory.

4. •PC:containsaddressofthenextinstructiontobefetched.Unless
instructedotherwise,theprocessoralwaysincrementsthePCafter
eachinstructionfetchsothatthenextinstructioninsequence(i.e.,
instructionlocatedatthenexthighermemoryaddress).
•IR:containstheinstructionmostrecentlyfetched.
4

5. Instruction Execution
•Instruction-fetch-execute cycle.
•A program to be executed by a CPU consists of set of
instructions stored in memory.
•The processor reads (fetches) instructions from memory
one at a time and executes each instruction.
•Program execution halts only if the processor is turned off,
some sort of unrecoverable error occurs, or a program
instruction that halts the processor is encountered.
5

6. 6
Memory Management
•Ideally programmers want memory that is
–Large
–Fast
–Non volatile (No loss in case of power failure)
•Memory hierarchy
–Very small, extremely fast, extremely expensive, and volatile –
CPU registers
–Small, very fast, expensive, and volatile –cache
–Some medium-speed, medium price, and volatile –main
memory
–Gigabytes of slow, cheap, and non-volatile –secondary
storage
•Memory managers handle the memory hierarchy

7. 7

8. 8
Basic Memory Management
Three simple ways of organizing memory with OS and one user process.
(a) Used by mainframes and minicomputers (b) Used by some handheld computers
and embedded systems (c) Used by early personal computers

9. 9
Source to Execution
•Translation of a source program in a high-level
or assembly language.
•This process generates machine language
executable code (known as a binary image)
for the source program.
•To execute binary code, it is loaded into the
main memory and the CPU state is set
appropriately.

10. Illustration of the relocation problem. (a) A 16-KB program. (b) Another 16-
KB program. (c) Two programs loaded consecutively into memory
Multiple Programs Without Memory Abstraction
Constant 16384 is added to every program address during the load process
Called static relocation

11. 11
Swapping (1)
Memory allocation changes as
–processes come into memory
–leave memory
Shaded regions are unused memory

12. Swapping(2)
•Swappingcreatesmultipleholesinmemory
•Combiningthemallintoonebigonebymovingall
theprocessesdownwardcalledmemorycompaction.
•ItsusuallynotdonebecauseitrequiresalotofCPU
time
•Howmuchmemoryshouldbeallocatedforaprocess
whenitiscreatedorswappedin:
–FixedAllocation:Ifprocessesarecreatedwithafixedsize
theoperatingsystemallocatesexactlywhatisneeded
–DynamicAllocation:Dynamicallyallocatingmemoryto
growingprocess.Ifaholeisadjacenttotheprocess,itcan
beallocatedandtheprocessallowedtogrowintothehole.
12

13. 13
Swapping (3)
(a) Allocating space for growing data segment
(b) Allocating space for two growing segments of a process
(stack & data segment)

14. Challenge –Memory Allocation
•Fixed partitions
•Variable/Dynamic partitions

15. Partitioning Strategies –Fixed
•Fixed Partitions –divide memory into equal sized
pieces (except for OS)
–Degree of multiprogramming = number of partitions
–Simple policy to implement
•All processes must fit into partition space
•Find any free partition and load the process
•Problem –what is the “right” partition size?
–Process size is limited
–Internal Fragmentation–unused memory in a
partition that is not available to other processes

16. Partitioning Strategies –Dynamic
•Idea: remove “wasted” memory that is not needed
in each partition
•Memory is dynamically divided into partitions
based on process needs
•Definition:
–Hole:a block of free or available memory
–Holes are scattered throughout physical memory
•New process is allocated memory from hole large
enough to fit it

17. Dynamic Partitions
•Morecomplexmanagementproblem
Musttrackfreeandusedmemory
Needdatastructurestodotracking
Whatholesareusedforaprocess?
Externalfragmentation
Memorythatisinholestoosmalltobeusablebyanyprocess
OS
process 1
process 2
process 3
OS
process 1
process 3
Process 2
Terminates
OS
process 1
process 3
Process 4
Starts
process 4

18. Memory Allocation –Mechanism
•MM system maintains data about free and allocated
memory alternatives
–Bit maps -1 bit per “allocation unit”
–Linked Lists -free list updated and coalesced when not
allocated to a process
•At swap-in or process create
–Find free memory that is large enough to hold the process
–Allocate part (or all) of memory to process and mark
remainder as free
•Compaction
–Moving things around so that holes can be consolidated
–Expensive in OS time

19. Memory Management -Maps
•Part of memory with 5 processes, 3 holes
–tick marks show allocation units
–shaded regions are free
•Corresponding bit map
•Same information as a list

20. Memory Management with Linked Lists
•Keepingtrackofmemoryistomaintainalinkedlist
ofallocatedandfreememorysegments
•Asegmenteithercontainsaprocessorisanempty
holebetweentwoprocesses
•Eachentryinthelistspecifiesahole(H)orprocess
(P),theaddressatwhichitstarts,thelength,anda
pointertothenextentry.
•Inlinklist,thesegmentlistiskeptsortedbyaddress
•Sortingthiswayhastheadvantagethatwhena
processterminatesorisswappedout,updatingthe
listisstraightforward.
20

21. Four neighbor combinations for the terminating process, X.
Memory Management with Linked Lists

22. 3.1
-22
Problems with Dynamic Partitions
•Fragmentationoccurs due to creation and deletion of
memory space at load time
•Fragmentation is eliminated by relocation
•Relocation has to be fast to reduce overhead
•Free (unused) memory has to be managed
•Allocation of free memory is done by a placement
algorithm

23. •Operating system must decide which free block to
allocate to a process
•How to satisfy a request of size n from a list of
free holes
•First Fit
–Scans memory from the beginning and chooses the first
available block that is large enough
–Fastest
–May have many process loaded in the front end of
memory that must be searched over when trying to find
a free block
23
Placement Algorithms(1)

24. Placement Algorithms(1)
•Next-fit
–Scansmemoryfromthelocationofthelast
placement
–Moreoftenallocateablockofmemoryatthe
endofmemorywherethelargestblockis
found
–Thelargestblockofmemoryisbrokenupinto
smallerblocks
–Compactionisrequiredtoobtainalargeblock
attheendofmemory
24

25. Placement Algorithms(1)
•Best Fit
–Chooses the block that is closest in size to the request
–Worst performer overall
–Since smallest block is found for process, the
smallest amount of fragmentation is left
–Memory compaction must be done more often
•Worst Fit
–Always take the largest available hole, so that the
new hole will be big enough to be useful
25

26. •Quick Fit
–Maintains separate lists for some of the more common
sizes requested
–For example, it might have a table with nentries, in
which the first entry is a pointer to the head of a list of 4-
KB holes,
–The second entry is a pointer to a list of 8-KB holes, the
third entry a pointer to 12-KB holes, and so on.
–Holes of, say, 21 KB, could be put on either the 20-KB
list or on a special list of odd-sized holes.
26
Placement Algorithms(1)

27. Example Memory Configuration
27
Before and after allocation of 16Mbyte block