Unix memory management

1. UNIX MEMORY
MANAGEMENT
1

2. AGENDA
Introduction
History of UNIX
Swapping
Demand Paging
Page Replacement Algorithm
Kernel Memory Allocator
Conclusion
2

3. Introduction
UNIXisaportable,multi-taskingandmulti-useroperating
system.
–Portable:runsonmanydifferenthardwarearchitectures(Intel
x86andIA-64,Alpha,MIPS,HPPA-RISC,PowerPC,IBM
S/390,SPARC,Motorola680x0,etc.).
–Preemptivemulti-tasking:severalprogramscanrunatthe
sametime(timeslices,interrupts,andtaskswitching).
–Multi-user:manyuserscansharethecomputersystematthe
sametime.
3

4. Other Features…
•Usesasimple,uniformfilemodelwhichincludesdevicesand
accesstootherservicesinaflexible,hierarchicalfilesystem.
•Writteninahigh-levellanguage(“C”)makingiteasyto
read,understand,changeandport.
•Thecommandpromptisasimpleuserprocess,theUnixshell,
whichisalsoaconvenientjobprogramminglanguage.
•Includessupportforregularexpressionswhichareconvenient
forcomplexsearching.
4

5. History of UNIX
•1964jointprojectbetweenAT&TBellLabs,GE,andMITto
developanewOS.
•Goal:developanOSthatcouldprovidecomputational
power,datastorageandtheabilitytosharedataamong
multipleusers.
•Result:MultiplexedInformation&ComputerService-
MULTICS.
5

6. •1969BellLabswithdrawsfromgroup.
•TwoBellLabscientists,KenThompsonandDennisRitchie,
continueresearch.Theywerestillleftwithouta“Convenient
interactivecomputingservice”*.
•AtthesametimeKenThompsonwroteagame“space
travel”inFortrantorunonGECOSOS.
•Thespaceshipwashardtocontrolanditwasexpensiveto
run.Hewastoldtogetthegameoffhisworkcomputer.
6

7. •ThompsonportedthegametoalittleusedPDP-7computer.
•Unics(laterUnix)wasbornasapunonMultics.
•DennisRitchiedeveloped“B”.Thenwrote“C”acompiled
language.
•In1973entireOSportedto“C”.
•1991Linux0.02isfirstreleasedtothepublic.
•1994Linux1.0isreleased.
7

8. Memory Management
UNIXismachineindependentsoitsmemorymanagement
schemewillvaryfromonesystemtonext.
EarlyversionsofUNIXusedvariablepartitioningwithno
virtualmemoryscheme.
CurrentimplementationsofUNIXmakeuseofpagedvirtual
memory.
Therearetwomemorymanagementschemes:
PagingSystem
KernalMemoryAllocator
8

9. Virtual Memory
9

10. Memory Management policies
•Swapping
–Easy to implement
–Less system overhead
•Demand Paging
–Greater Flexibility
10

11. Swapping
•Theprocessofmovingsomepagesoutofmainmemoryand
movingothersin,iscalledswapping.
•ApagefaultoccurswhentheCPUtriestoaccessapagethat
isnotinmainmemory,thusforcingtheCPUtowaitforthe
pagetobeswappedin.
•Sincemovingdatatoandfromdiskstakesasignificant
amountoftime,thegoalofthememorymanageristo
minimizethenumberofpagefaults.
11

12. •SwapSpace-Diskmemoryusedtoholddatathatisnotin
RealorFileSystemmemory.Swapspaceismostefficient
whenitisonaseparatediskorpartition,butsometimesitis
justalargefileintheFileSystem.
•Allocationofbothmainmemoryandswapspaceisdone
first-fit.
•ApagefaultoccurswhentheCPUtriestoaccessapage
thatisnotinmainmemory,thusforcingtheCPUtowaitfor
thepagetobeswappedin.
12

13. •Sincemovingdatatoandfromdiskstakesasignificant
amountoftime,thegoalofthememorymanageristo
minimizethenumberofpagefaults.
•Whenthesizeofaprocess'memoryimageincreases(dueto
eitherstackexpansionordataexpansion),anewpieceof
memorybigenoughforthewholeimageisallocated.
•Ifnosinglepieceofmainmemoryislargeenough,the
processisswappedoutsuchthatitwillbeswappedbackin
withthenewsize.
13

14. •Decisionsregardingwhichprocessestoswapinorswapout
aremadebytheschedulerprocess(alsoknownasthe
swapper).
•Aprocessismorelikelytobeswappedoutifitisidleorhas
beeninmainmemoryforalongtime,orislarge;ifno
obviouscandidatesarefound,otherprocessesarepickedby
age.
•Aprocessismorelikelytobeswappedinifitshasbeen
swappedoutalongtime,orissmall.
14

15. 15

16. Allocating Swap Space
16
1 10000 101 9900
151 9750251 9850
Allocate 100 unit
Allocate 100 unit
Allocate 50 unit
Map
AddressUnit

17. Freeing Swap Space
17
251 9750
50 unit free at 101
Map
Address Unit
101 50
251 9750
Case 1: Free resources fill a hole,
but not contiguous to any resources in the map

18. Freeing Swap Space
18
251 9750
50 unit free at 101
Map
Address Unit
101 50
251 9750
100 unit free at 1
1 150
251 9750
Case 2: Free resources fill a hole,
and immediately precedes an entry in the map

19. 19
Freeing Swap Space
251 9750
50 unit free at 101
Allocate 200 unit
Map
AddressUnit
101 50
251 9750
100 unit free at 1
1 150
251 9750
1 150
451 9550
1 10000
300 unit free at 151
Case 3: Free resources fill a
hole, and completely fills the
gap between entries in the
map

20. Demand Paging
•DemandpagingtounixwithBSD(Berkleysystem)which
transferredmemorypagesinsteadofprocesstoandfroma
secondarydevice.
•Whenaprocessneedsapageandthepageisnotthere,a
pagefaulttothekerneloccursaframeofmainmemoryis
allocated,andtheprocessisloadedintotheframebythe
kernel.
20

21. PageTable
•frame#containsthephysicalframewherethevirtualpage
isstored
•ageisprocessordependant,andismeanttomaintainhow
longithasbeensincethepagewasaccessed.
•CopyonWritestorethecopyonwritebit,whichisusedin
UNIXsystemsto,amongotherthings,renderforkefficient.
PageFrame
Number
AgeCopy on
write
ModifyReferenceValidProtect
21

22. •Dirtyisasinglebitthatindicateswhetherapagehasbeen
modifiedsincelastswappedin(theoppositeofdirtyisclean,
andacleanpageneednotbewrittenouttodiskif
swapped).
•RefcontainstheusageinformationnecessaryforaCLOCK-
stylealgorithm.
•ValidisthestandardUNIXjargonforresident.Avalidpage
isinmainmemory,aninvalidoneisswappedout.
•Protectcontainsthepermissioninformationforthepage
andisalsohardwaredependant.
22

23. Diskblockdescriptor
•Thediskblockdescriptorcontainstheinformationmapping
avirtualpagetoaspotondisk.
•TheOSmaintainsatableofdescriptorsforeachprocess.
23
Swap device NumberDevice Block No. Typeof storage

24. •Device#isbasicallyapointertothediskthatthispagewas
swappedto.
•Block#istheactualblockthatthepageisstoredon.Thisis
whymostUNIXsystemsprefertohaveaseparateswap
partition,sothattheblocksizecanbesettothepagesize.
•Typespecifieswhetherthepageisneworpre-existing.This
letstheOSknowifithastocleartheframefirst.
24

25. Page frame data table
•The page frame data table holds information about each
physical frame of memory (indexed by frame number).
•This table is of primary importance for the replacement
algorithm.
Page State Reference
Count
Logical
device
Block
number
Pf data
pointer
25

26. •Page state indicates whether or not the frame is available or
has an associated page (i.e. whether its been allocated to a
process or not).
•Ref. Count holds the number of processes that refer to this
page (remember, processes can share the same physical
page).
•Logical device contains the device number of the disk that
holds a physical copy of the page.
26

27. •Block # holds the block number on that disk where the
page data is located.
•Pfdata pointeris a pointer field that is used to thread a
singly-linked list of free frames through the frame table. If
the page is free, this points to the next free page (useful for
free list-style allocation).
27

28. Swap use table
•Reference Count: Number of page table entries that point
to a page on the swap device.
•Page/storage unit number : Page identifier on storage unit
28
Reference
count
Page/storage
unit number

29. Page Replacement Algorithm
•The Page frame data table is used for page replacement.
•All of the available frames are linked together in a list of free
frames available for bringing in pages.
•The two-handed clock algorithm uses the reference bit in the
page table entry for each page in memory that is eligible
(not locked) to be swapped out.
•This bit is set to 0 when when the page is first brought in and
set to 1 when the page is refernced for a read or write .
29

30. Two-Handed clock Page Replacement Algorithm
30

31. •Twoparametersdeterminetheoperationofthealgorithm:
–Scanrate:Therateatwhichthetwohandsscanthroughthe
pagelist,inpagespersecond.
–Handspread:Thegapbetweenfronthandandbackhand
•Thesetwoparametershavedefaultvaluessetatboottime
basedontheamountofphysicalmemory.
31

32. •The parameter varies linearly between the values slowscan
and fastscan as the amount of free memory varies between
the values lotsfree and minfree.
•The handspread parameter determines the gap between the
fronthand and the backhand and therefore, together with
scanrate,determines the window of oppurtunity to use a
page before it is swapped out due to lack of use.
32

33. Kernal Memory Allocator
•Kernelmemoryallocator:providesbuffersofmemoryto
variouskernelsubsytems.
EvolutionCriteria:
–mustbespace-efficienti.e.minimizewastage.
–Canbemeasuredbyutilizationfactor
–mustbefast
–musthaveasimpleprogramminginterface
–shouldnotforcetofreetheentireallocatedareaallatonce
–mustguardagainstthewastageofmemory
–mustbeabletointeractwiththepagingsystem
33

34. 34
Advantages
•easy to implement
•not restricted to memory allocation
•no wastage of space
•can release any part of the region
•allows reuse of memory by coalescing

35. References
Books :
*********
1. Os Internals & design
---William Stallings
2.The design of the unix operating system
---Maurice J. Bach prentice hall
35