INTRO TO OPERATING SYSTEMS
INTRO TO OPERATING SYSTEMS CS 333
Popular in Course
AFST 104 001
verified elite notetaker
Popular in ComputerScienence
This 68 page Class Notes was uploaded by Orrin Rutherford on Tuesday September 1, 2015. The Class Notes belongs to CS 333 at Portland State University taught by Jonathan Walpole in Fall. Since its upload, it has received 31 views. For similar materials see /class/168271/cs-333-portland-state-university in ComputerScienence at Portland State University.
Reviews for INTRO TO OPERATING SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/01/15
CS 333 Introduction to Operating Systems Class 9 Memory Management Jonathan Walpole Computer Science Portland State University Memory managemenT a Memory a linear array of byTes Holds 05 and programs processes Each cell byTe is named by a unique memory address a Recall processes are defined by an address space consisTing of TexT daTa and sTack regions a Process execuTion CPU feTches insTrucTions from The TexT region according To The value of The program counTer PC Each insTrucTion may requesT addiTional operands from The daTa or sTack region Addressing memory a CannoT know ahead of Time where in memory a program will be loaded a Compiler produces code conTaining embedded addresses 4 These addresses can39T be absoluTe physical addresses a Linker combines pieces of The program Assumes The program will be loaded aT address 0 a We need To bind The compilerlinker generaTed addresses To The acTual memory locaTions Relocafable address generation Library Routines Prog P P 0 P 100 P push push push foo jmp foo jmp 75 jmp 175 End P foo 75 foo 175 foo VVVk Compilation Assembly Linking 1000 Library Routines 1100 1175 P push jmp 1175 foo Loading Address binding a Address binding fixing a physical address To The logical address of a process39 address space a Compile fime binding if program locaTion is fixed and known ahead of Time D Load fime binding if program locaTion in memory is unknown unTil runTime AND locaTion is fixed a Execufion fime binding if processes can be moved in memory during execuTion Requires hardware supporT 0 Library 1000 Library Routines Compile Time R ut1nes Address Binding P L P push push jmp 175 jmp 1175 175 foo 1175 foo Load Time I Address Binding Execution Time 1000 Address Binding L1brary 3 Library Routines Routines 1100 100 P P Base register 39 push 1000 PUSh jmp 1175 jmp 175 1175 175 foo foo Rum ime binding base amp limit registers a Simple rurrl39ime relocation scheme Use 2 regis rers To describe a par ri rion a For every address generated at rurrl39ime Compare To The limiT regisTer amp aborT if larger Add To The base regisTer To give physical memory address Dynamic relocation with a base register a Memory Management Unit MMU dynamically converts logical addresses into physical address a MMU contains base address register for running process Relocation register for process Max Mem Max addr Program generated address r U Physical memory M MU address Protection using base amp limit registers a Memory protection Base register gives starting address for process Limit register limits the offset accessible from the relocation register r ister l gical a dress yes base re Ister Physical address addressing error Multiprogramming with base and limit registers a Multiprogramming a separate partition per process a What happens on a context switch Store process A39s base and limit register values Load new values into base and limit registers for process B limit PartitionD base Partition B Partition A Swapping a When a program is running The en rire program musT be in memory Each program is puT info a single par ri rion a When the program is not running May remain residenT in memory May geT swappea ouT To disk D Over Time Programs come inTo memory when They geT swapped in Programs leave memory when They geT swapped ouT Basics swapping a Benefits of swapping z Allows mul riple programs To be run concurrently z more Than will fi r in memory at once Swap in Swap ou l39 Swapping can lead To fragmentation 896K 576K 896K 320K 128K MwNH MwNH Vaul Momm Momm NN Meow MNMM Mohm MwNH MwNH Vaul Momm Momm NN Meow MNMM Mohm MwNH MwNH Vaul Momm Momm NN Meow MNMM Mohm MwNH Momm NN MNmm MwNH Momm Mohm MwNH Momm MwNH vm Mom gwwm o MwNH Meow MwNH Momm NN MNmm MwNH Momm Mohm MwNH Momm MwNH vm Mom gwwm o MwNH Meow MwNH Momm NN MNmm MwNH Momm Mohm MwNH Momm MwNH vm Mom gwwm o MwNH Meow MwNH Momm Mohm MwNH Momm MwNH vm Mom gwwm o MwNH Meow Dealing with fragmentation a Compaction from time to time shift processes around to collect all free space into one contiguous block Memory to memory copying overhead 39 memory to disk to memory for compaction via swapping How big should partitions be a Programs may want to grow during execution More room for stack heap allocation etc a Problem If the partition is too small programs must be moved 4 Requires copying overhead Why not make the partitions a little larger than necessary to accommodate some cheap growth Allocating extra space within partitions B W A Operating system a l l l l Room for growth Actually in use Room for growth Actually in use BStack BProgram AStack AProgram Operating system b Room for growth Room for growth Managing memory a Each chunk of memory is either Used by some process or unused free a Operations Alloca re a chunk of unused memory big enough To hold a new process Free a chunk of memory by reTurning iT To The free pool afTer a process Termina res or39 is swapped ouT Managing memory with bit maps a Problem how To keep Track of used and unused memory a Technique 1 Bi39l39 Maps A long biT sTring One biT for every chunk of memory 1 in use 0 free Size of allocaTion uniT influences space required Example unit size 32 bits overhead for biT map 133 3 Example unit size 4Kby139es overhead for biT map 132769 Managing memory with bit maps 11111000 11111111 11001111 11111000 Managing memory with linked lists a Technique 2 Linked List a Keep a list of elements a Each element describes one unit of memory Fr39ee inuse BiT Ppr39ocess Hhoe z STar Ting address LengTh PoinTer39 To nexT elemem Managing memory with linked lists OI Al 1 1 Bl l 1C1 1 WM 1 I P I l I El l 16 24 P05HH53gtP8l6gtP144Hgt CIHI182 gtF 206 gtF 26l3lgtH293gtlt T f Hole Starts Length Process at 18 2 Merging holes a Whenever a uniT of memory is freed we wan r To mer39ge adjacen r holes Merging holes Before X terminates After X terminates A X B becomes A W B Merging holes Before X terminates A X B A X W becomes becomes After X terminates A m B A W Merging holes Before X terminates After X terminates A X B becomes A W B A x becomes A W X B becomes W B 3263 303 wmd oqm x 33333 26 x quaimEm gt x w a oooo mm gt w gt x a oooo mm gt gx w a oooo mm w x a oooo mm Managing memory with linked lists a Searching the list for space for a new process First Fit Next Fit Start from current location in the list Not as good as first fit Best Fit Find the smallest hole that will work Tends to create lots of little holes WOF ST Fl l Find the largest hole Remainder will be big QUle Keep separate lists for common sizes Fragmentation a Memory is divided into partitions a Each partition has a different size a Processes are allocated space and later freed a After a while memory will be full of small holes z No free space large enough for a new process even though there is enough free memory in total a If we allow free space within a partition we have internal fragmentation a Fragmentation External fragmentation unused space between partitions Internal fragmentation unused space within partitions Solution to fragmentation a Compaction requires high copying overhead a Why not allocate memory in noncontiguous equal fixed size units no external fragmentation internal fragmentation lt 1 unit per process a How big should the units be The smaller the better for internal fragmentation The larger the better for management overhead u The key challenge for this approach How can we do dynamic address translationquot Using pages for noncontiguous allocation a Memory divided into fixed size page frames Page frame size 2quot byTes Lowes r n bi rs of an address specify by re offse r in a page D But how do we associate page frames with processes And how do we map memory addresses wi rhin a process To The correcT memory byTe in a page frame a Solution 4 Processes use virTual addresses CPU uses physical addresses hardware suppor r for vir rual To physical address Transla rion Vir139ual addresses a Virtual memory addresses what The process uses Page number plus byTe offseT in page Low order n biTs are The byTe offse r Remaining high order biTs are The page number bit 31 bit n 1 by 0 20 bits I 12 bits L J J page number offset Example 32 bi39l39 virtual address Page size 212 4KB Address space size 232 byTes 468 Physical addresses a Physical memory addresses what The CPU uses Page frame number plus byTe offseT in page Low order n biTs are The byTe offse r Remaining high order biTs are The frame number bit 24 bit n 1 bil39r 0 12 bits I 12 bits L J J r r Frame number offse39l39 Example 24 bi39l39 physical address Frame size 212 4KB Max physical memory size 224 byTes 16MB Address Translation a Hardware maps page numbers to frame numbers a Memory management unit MMU has multiple registers for multiple pages Like a base register except its value is substituted for the page number rather than added to it Why don39t we need a limit register for each page Memory Management Unit MMU The CPU sends virtual CPU addresses to the MMU package CPU gt Memory M Disk 1 management emory controller unit Bus The MMU sends physical addresses to the memory Virtual address spaces a Here is The virtual address space as seen by The process Lowesf address Hg39ghesf addres Virfua Addr Space Virtual address spaces u The address space is divided into quotpagesquot In BLITZ The page size is 8K Page 0 Page 1 IO U39lhWNI O N Virfua Addr Space Virtual address spaces a In reality only some of The pages are used 0 39 W Virfua Addr Space Physical memory a Physical memory is divided info page framesquot Page size frame size 39A 7 39 A IO U39lhWNI O 39 39A Virfua Addr Space Physical memory Virtual and physical address spaces a Some frames are used To hold The pages of This process 39A 7 39 A IO U39lhWNI O These frames are used for fhls process 39 39A Virfua Addr Space Physical memory Virtual and physical address spaces a Some frames are used for other processes 39A 7 39 A Used by 1 ofher processes IO U39lhWNI O 39 39A Virfua Addr Space Physical memory Virtual address spaces a Address mappings say which frame has which page f 4 IO U39lhWNI O VA A Virfua Addr Space Physical memory Page Tables a Address mappings are stored in a page fabe in memory a One page Table entry per page Is This page in memory If so which frame is i r in 39 A 39 4 IO U39lhWNI O VA Virfua Addr Space Physical memory Address mappings and Translation a Address mappings are sTored in a page Table in memory 4 Typically one page Table for each process a Address TranslaTion is done by hardware ie The MMU a How does The MMU geT The address mappings z EiTher The MMU holds The enTire page Table Too expensive or iT knows where iT is in physical memory and goes There for every TranslaTion Too slow z Or The MMU holds a porTion of The page Table MMU caches page Table enTries Cache is called a TranslaTion lookaside buffer T LB and knows how To deal wiTh TLB misses Address mappings and Translation a WhaT if The TLB needs a mapping iT doesn39T have a SofTware managed TLB iT generaTes a TLBmiss faulT which is handled by The operaTing sysTem like inTerrupT or Trap handling The operaTing sysTem looks in The page Tables geTs The mapping from The righT enTry and puTs iT in The TLB a Hardware managed TLB iT looks in a prespecified physical memory locaTion for The appropriaTe enTr39y in The page Table The hardware archiTecTur39e defines where page Tables musT be sTored in physical memory OS musT load currenT process page Table There on conTexT swiTch The BLITZ architecture a Page size 8 Kbytes a Virtual addresses logical addressesquot 24 bits gt 16 Mbyte virtual address space 211 Pages gt 11 bits for page number The BLITZ architecture a Page size 8 Kbytes a Virtual addresses logical addressesquot 24 bits gt 16 Mbyte virtual address space 211 Pages gt 11 bits for page number a An address 23 1312 o 11 bits 13 bits I J J W w page number offset The BLITZ architecture a Physical addresses 32 biTs gt 4 GbyTe insTalled memory max 219 Frames gt 19 bi rs for frame number The BLITZ architecture a Physical addresses 32 biTs gt 4 GbyTe insTalled memory max 219 Frames gt 19 bi rs for frame number 31 1312 19 bits 13 bits V w frame number offset The BLITZ architecture a The page table mapping Page gt Frame a Virtual Address 23 1312 11 bits a Physical Address A r 31 1312 19 bits The BLITZ page Table a An array of page fabe enfriesquot KepT in memory a 211 pages in a virtual address space gt 2K enTries in The Table a Each entry is 4 bytes long 19 biTs The Frame Number 1 bi l 1 bi l 1 bi l 1 bi l 9 biTS Valid BiT WriTable Bi r Dir ry Bi r Referenced Bi r Unused and available for OS algoriThms The BLITZ page Table a Two page Table relaTed regisTers in The CPU z Page Table Base RegisTer z Page Table LengTh RegisTer C These define The currenT page Table 4 This is how The CPU knows which page Table To use z MusT be saved and resTored on conTexT swiTch 4 They are essenTially The BliTz MMU a BiTs in The CPU sTaTus regisTerquot SysTem Mode InTerrust Enabled Paging Enabled 1 2 Perform page Table TranslaTion for every memory access 0 Do noT do TranslaTion The BLITZ page Table 31 1312 0 frame number I unused IDIRIWIVI j V referenced bi39l39 writable bi39l39 valid bi39l39 The BLITZ page Table page Table base register 31 1312 0 0 frame number unused D R W V 1 frame number unused D R W V 2 frame number unused D R W V frame number unused D R W V 2K frame number unused D R W V Indexed by Me page number The BLITZ page Table 23 13 12 El I page number I offset virtual address page Table base register 31 1312 0 0 frame number unused D R W V 1 frame number unused D R W V 2 frame number unused D R W V frame number unused D R W V 2K frame number unused D R W V The BLITZ page Table 23 13 12 El I page number I offset virtual address page Table base register 31 1312 0 0 frame number unused D R W V 1 frame number unused D R W V 2 frame number unused D R W V frame number unused D R W V 2K frame number unused D R W V 31 physical address The BLITZ page Table 23 1312 D I page number I offset vir39l39ual adaress page Table base register 31 1312 0 frame number unused D R W 1 frame number unused D R W 2 frame number unused D R W frame number unused D R W 2K frame number unused D R W 31 1312 I I offset physical address The BLITZ page Table 23 1312 0 D I page number I offset k 1 L 1 page Table base re is139 Vir lal address 31 1312 0 0 frame number unused D R W V 1 frame number unused D R W V 2 frame number unused D R W V frame number unused D R W V 2K frame number unused D R W V 31 1312 0 I I offset physical address The BLITZ page Table 23 1312 0 D I page number I offset I page table base virtual address 1312 unused unused unused unused 2K unused 31 1312 0 I frame number I offset I physical address Quiz a What is The difference between a virtual and a physical address a What is address binding a Why are programs not usually written using physical addresses a Why is hardware support required for dynamic address translation a What is a page Table used for a What is a TLB used for a How many address bits are used for The page offset in a system with ZKB page size
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'