Roadmap Contiguous memory management and its limitations Paged

Roadmap  Contiguous memory management and its limitations  Paged

Roadmap Contiguous memory management and its limitations Paged memory management Motivation This presentation is intended to be and overview Binding, page table, mode. and the MMU viewed in the slideshow If you are reading this management text, you are not in slide Segmented memory Motivation and overview show Hit the F5 function key to The mode. segment table enter slideshow mode. MSJ-1 Summary of Contiguous Memory Management Contiguous memory management means that the physical address space of a process must be a single contiguous block (sometimes known as a partition) in physical memory External fragmentation is intrinsic to contiguous memory management It is the variable length holes in memory that lead to external fragmentation and since processes are variable length, so too will be the holes Even if we quantize our allocations and hence our holes, there can still be a variable number of quanta per hole and so we still will eventually have external fragmentation Compaction is in fact a solution, but not for real time systems To take the next step were going to have to drop the requirement for the physical address space of a process to be contiguous MSJ-2 Introduction to Paged Memory Management address Paged memory management divides the logical Paged memory management divides the logical Here, for example, we see the OS view of memory Here, for example, we see the OS view of memory 0x0000 12 44 33up 33 address space of the load module into fixed 12 address space of the load module up into fixed for a page/frame size of 2 = (2 ) =16 bytes =1K for are does indeed chop a page/frame size of 2the = loader (2 ) =16 bytes =1K16 Pages Pages are real real enough, enough, the loader does indeed chop 16 0x1000 length chunks (quanta, now called pages) before length chunks (quanta, now called pages) before up the load modules logical address space into pages (thats a hex K there; it would be 4096 , in decimal) up the load modules logical address space into pages (thats a hex K there; it would be 409610 10, in decimal) loading them independently into frames defined 0x2000 loading them independently into frames defined as as itit loads loads the the process process from from disk disk into into memory memory by by evenly evenly spaced spaced main main memory memory addresses addresses that that 0x3000 Frames are a fiction, however, merely a consequence Frames are a fiction, however, merely a consequence appear appear to to divide divide physical physical memory memory into into fixed fixed length length of the way the OS allocates physical memory the So 44 starts at physical 4(frame offrame the way the OS allocates physical memory the== 0x4000 chunks So frame starts

atsame physical address 4(frame size) The physical memory doesnt see any of exactly the size as pages chunks The physical memory doesnt see any of this; this;size) exactly the same sizeaddress as pages memory itself nothing about frames and 41K ==continues 0x4000 and runs up to but not including the memory itself knows knows nothing about frames and there there 0x5000 41K 0x4000 and runs up to but not including the it just its boring life of receiving a 16 it just continues its boring life of receiving a 16 Any page can go to any frame Any can5go to any frame are changes to the hardware itself arepage no changes to theaamemory memory hardware itself start of frame or addresses page0 physical address plus control bit which tells start ofno frame 5 at at 0x5000, 0x5000, or physical physical addresses 0x6000 physical address plus control bit which tells 0x4000 0x4fff, inclusive whether to read or write that address 0x4000 0x4fff, inclusive ititThe whether tojust read or write that address loader makes sure that whenever The loader just makes sure that whenever itit loads loads aa page1 0x7000 page, itit loads itit starting at base address page, loads starting at a a baseinto address that is is some some Its up the to pages the page2 Its up to to the loader loader to load load pages into the that 0x8000 multiple of the page/frame size i.e., the base address multiple of the page/frame sizeits i.e., the base address correct physical addresses up correct physical addresses and and its up to to the the page3 0x9000 of frame #k is k f, where f is the page/frame size, so MMU to aa logical address to of frame #k is k**f,bind where f is the page/frame MMU to properly properly bind logical

address to aa size, so load 0xa000 the frame number is in fact nothing more than the most physical address before its sent to the memory the frame number is in fact nothing more than the most physical address before its sent to the memory module 0xb000 significant bits of (well see significant bitsshortly) of its its base base address address (well see how how shortly) frame # 0 1 2 3 4 5 6 7 8 9 a b main memory MSJ-3 The Long Term Scheduler, Admission, the Free Frame List, and the Page Table The The long long term term scheduler scheduler (in (in charge charge of of admission) admission) asks asks the memory manager there enough free frames For memory management, the free memory manager there are are enough frames on the For paged paged memory management, the free All means in FFL is Remember: Remember: All this thisififnumber number means in the the FFL is on the free frame list for the space list simplified to aaprocess free frame the free frame list for the new new process space list is is simplified tofrom free frame list list that the physical memory address that the physical memory from address (FFL) whose is (FFL) whose management management is much much simpler to address is IfIf 220*(pageSize) so, 220*(pageSize) the to number address of frames 221*(pageSize) are removed is from so, the requisite requisite number of 221*(pageSize) frames aresimpler removed from than the older free space list: thanand the older free space list: currently not used so its free for assignment to any currently not used so its free for assignment to any the FFL inserted into the new processs page table FFL and inserted into the new processs page table the The page table (PT) is a data structure used for the The page table (PT) is a data structure used for the

It doesnt need to be ordered It doesnt need to be ordered page of any process that needs itit page of any process that needs execution time execution time binding binding of of paged paged memory memory management management Since Since theyre theyre fixed fixed length, length, any any frame frame is is as as Each process must have its own page table as other whatsoever Eachgood process must havefor itsany ownuse page table good as any any other for any use whatsoever A A PT PT contains contains the the frame frame numbers numbers assigned assigned to to (containing) (containing) the the process process A A processs processs page page table table is is created created when when itit (a (a new new process) process) is is admitted admitted and and loaded loaded Page Table (PT) FFL 220 3e8 99 a2 2f5 aa5 678 27 27b MSJ-4 Execution Time Binding for Paged Memory Management main memory memory management unit (MMU) LA p fp d d PA PA=fp*(pageFrameSize)+d CPU page table (PT) The The frame frame number number the the MMU MMU f finds is finds there, there, in in PT[p], PT[p], is the the frame f d f p page p p frame in main memory that the frame in main memory that the f Pretend, for Pretend, for illustrative illustrative purposes purposes that that all all pp is is used used as as an offset into an offset into splits The MMU circuitry The MMU circuitry splits table the page table up logical address up the the page logical address OS OS assigned assigned to to hold hold page page pp of of into into aa page page number, number, p, p, the aa book contained exactly the pages pages of ofthe book contained exactly processs logical address thesame processs logical address fp Pages are the size so the Pages and and frames frames are the same size so the and and the the displacement displacement 1000 characters 100010 characters 10 space space of from the beginning

aa page is the displacement from the beginning of page is the from of from the the beginning beginning displacement of Then character #35879 in the book would Then character #35879 in the book would same as the displacement from the base address of same as the displacement from the base address of that th that page, page, dd th be the 879 character from the beginning be the 879 character from the beginning the that holds that page, so the MMU appends the frame frame that holds that page, so the MMU appends The management unit (MMU) The memory memory management unit (MMU) of page 35 in the book of page 35 in the book the displacement (from the logical the displacement (from thelogical logical address) address) to to the the uses page table each uses the the page table to to bind bind each logical frame number from the page table and the result is number the address emitted by CPU to the addressframe emitted by the thefrom CPU topage the table and the result is the physical address to sent physical address to be bememory sent to to main main memory memory correct physical address in correct the physical address in main main memory 0 1 2 MSJ-5 So Where is the Page Table? Page Table in the MMU Each page register Each page register also also nn CPU There There must must be be 22 page page registers, registers, needs an extra bit to indicate needs an extra bit todevoted indicate where n is the number of bits where n is the number of bits devoted memory management unitwhether (MMU)or not itit is valid whether or in not is valid to the page number the MMUs to the page number in the MMUs main memory n bits So, for example, for decoding of a logical address example, for aa process process

decodingSo, of afor logical address LA PA p d fpwhose dp logical address space whose Fewer bits for page number, p, Fewer bits for the thelogical page address number, space p, was only 5 pages, only the was only 5 pages, only the means context switch, since means aa faster faster context switch, since page page table first 55will page registers would first page registers would be be the page table be smaller the page table will be smaller the page table for the running IfIfmarked registers (PT) the page table for the running marked valid valid But since the number in v since process is to be in But the total total number of bits in aa process is going going to of bebits in the the MMU, reference to invalid A v A CPU CPU reference to an an invalid logical address fixed, also means MMU, itit is must be in to what logical address is fixed, also means must beititread read in to what v bits page would the MMU page would cause thed, MMU more for the displacement, are called the MMU more bits for the displacement, d, are called thecause MMU page page v fp which to aapage hardware trap 2n page to generate generate hardware trap means that the size is registers as part of the context which means that the page size is registers as part of the context When a process is not running, its page table is kept in memory When a process is not running, table is kept in memory v its page registers and the OS would terminate and the OS would terminate larger internal fragmentation switch whenever the process larger and and internal fragmentation switch whenever the process is is i There the process how MMU will access the process There are are two two possibilities

possibilities for forbecomes how the the MMU will access the more of an issue dispatched becomes more of an issue the dispatched i page process: page table table for for aa currently currently running running process: i The The bigger bigger the the page page table, table, the the Copy Copy itit into into the the MMU MMU as as part part of of the the context context switch switch longer longer the the context context switch switch time time Use Use the the one one in in main main memory memory There There are are advantages advantages and and disadvantages disadvantages to to each each choice choice MSJ-6 Note Note also also that that now now every every memory memory reference reference by by the the CPU CPU results results in in two two physical physical memory memory references, references, the the first first into into the the page page table table to to obtain obtain ffpp for for binding, binding, and and the the second, second, after after the the binding, binding, to to actually actually satisfy satisfy the the CPUs CPUs request request memory management A unit limit register A page page table table limit(MMU) register (PTLR) (PTLR) in in the the MMU MMU The the takes to satisfy the CPUs memory request To find the physical address in The result result is is to to double double the time time takes toto satisfy the CPUs memory request can used avoid (fairly obvious) problems main To find the physical address inmemory canititbe be used to avoid (fairly obvious) problems n bits memory of the in LA PAbit aa valid/invalid with page memory of the desired entry in with keeping keeping bitentry with each each page p d with fvalid/invalid CPU d desired p the table, table in the page page table, the the page page number number table entry entry in memory memory is added to PTBR is simply simply added to the the PTBR part of a The PTLR and the PTBR are The PTLR and the PTBR are both both part of a the the context context of of aa running running process process Page Page Table Only in Main Memory PTLR Table PTBR p yes p + Note means Note that that using using pp as as an an offset offset in in main main memory memory means p PTLR

? fp max size 2n Ifthat the MMU doesnt registers, itit memory will page table must be entries Ifthat thethe MMU doesnt have page registers,in will need need to to access access the the page page the page table have must be contiguous contiguous in memory no page The frame number there in table in memory and will a special purpose register called The fits frame number there in table in memory and so so will need need a special purpose register called the the If the largest possible page table into a single If the largest possible page table fits into a single trap PT[p] then read into page table base register the base address of PT[p] is is then read into the the page table base register toofcontain contain the base address of the the page page table table for for to OS to frame, thats guaranteed, course, since memory frame, thats guaranteed, of course, since memory MMU the process (each has its MMU and and concatenated the running running process (each process process hasconcatenated its own own page page table, table, remember) remember) within a frame is contiguous within a frame is contiguous with the displacement to with the than displacement to One PTBR is faster to context switch aa whole bunch of One PTBR is faster to context switch than whole bunch of page page registers registers Otherwise, to page the page table! complete the binding Otherwise, itit will will be be necessary necessary to page the page table! complete the binding MSJ-7 Translation Look Aside Buffer (TLAB) memory management unit (MMU) main memory CPU LA p dp fp dp PA page # frame # TLAB hit A A translation translation look look aside aside buffer buffer (TLAB) (TLAB) in in the the MMU MMU PTLR PTBR TLABup TLAB can by eliminating the can speed speed things things up by eliminating the binding binding miss access(es) access(es) to to physical physical memory memory most most of of the

the time time yes p page table f p + The cache of recently referenced page numbers The TLAB TLAB is is an an associative associative cache of recently referenced page numbers In the event the page ? In the event the page and numbers and their their corresponding correspondingnoframe frame numbers number is number is not not found found in in the (TLAB miss), the TLAB TLAB (TLAB miss), When is to TLAB, itit is When aa page page number numbertrap is presented presented to the the TLAB, is searched searched to OS a hit the required frame the(the required framepage associatively presented associatively and and ifif theres theres a hit (the presented page number number is is found), found), its its retrieved from number is retrieved from frame binding without the of frame number number is is available available for fornumber binding is without the necessity necessity of retrieving retrieving itit the the page page table table in in memory memory from from memory memory as as before before p PTLR MSJ-8 A Problem With Paging: 0 0 1 1 0 1 0 0 0 0 1 0 0 1 re wrad ex ite ec ut 1 e re wrad ex ite ec ut cant cant write write to to itit this this might might be be aa frame frame shared shared by by some some other other process process that that owns owns PT the the data, data, wants wants to to share share it, it, but but doesnt doesnt want itit altered this From MMUby design standpoint, its wantan altered by this process process Data stored here Data stored here can can be be both both easy enough: just add protection bits read and written by this process read and written by this process Remember, process its Remember, each process has its own own to each entryeach in the pagehas table page to memory, the page table, table, so so to share share memory, the could help an OS In theory, the

page table, In theory, the page table, could help an OS But theframe programs logical address same number can appear in the same frame number can appear in the to enforce aa security policy so tomultiple enforceby security so that, that, for for page of processes policy and space as produced the compiler page table table of multiple processes and example, users dont to code code example, users dontintry try to overwrite overwrite code will usually be in different pages the will usually be in different pages in the and linker isin contiguous andthey thein library files that have aa right in library files that they in fact factlooks havelike right This page/frame itit contains different processes, each with its own This page/frame looks like contains different processes, each with its own ? ? ? boundaries between the various code to execute (but not to change) to execute (but not to change) code; protection code; the the CPU CPU can can fetch fetch instructions instructions from from protection bits bits data and data structures usually wont fall here here for for execution, execution, but but other other accesses accesses neatly on page boundaries the are permitted are not notthat permitted e The read from but The CPU CPU can canBits read data data from here, here, but be Applied to Pages Protection Cannot Really 1 1 1 compiler doesnt know anything about What What protection protection should should be be applied applied to to this this page? page? 0 0 0 0 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 pages in the contiguous logical address space MSJ-9 Roadmap Contiguous memory management and its limitations Paged memory management Segmented memory management Motivation and overview The segment table MSJ-10 Segmented Memory Management Segments are logically distinct chunks of the overall logical address space of a process stack stack global global data data heap heap

user user code code shared shared memory memory library library code code process Each segment is logically contiguous and is assigned (bound) to physical memory by the OS and the MMU independently of other segments MSJ-11 The Segment Table The The segment segment number, number, s, s, is is used used as as an an offset offset into into the the segment segment table table To the the To complete complete the binding, binding, the the segment table is stored Depending on where memory management unit Depending on where(MMU) the segment table is stored displacement is added to the displacement is added to the (same choices for page the MMU (same choices as as the for aaprotection page table), table), theare MMU main For a valid segment, bits then segmentation error, For a valid segment, the protection bits are then base address of the segment base address theeither segment can use aa valid/invalid canof use either valid/invalid bit bit for for each each memory core dumped checked to determine if the operation requested checked to determine ifaathe operation requested segment register or segment table limit register n bits segment register or segment table limit register The segment table is the key data structure used by no by the CPU is legal for that segment by the CPU to is determine legal for that (STLR) ifif the segment (STLR) to determine thesegment segment number number from from d LA segmented memory management, analogous to the PA sisdidnt We need to do this We didnt need to dodone this for CPU logical address valid, just as was s logical address is valid, just as was done for dsMMU < limit dIf raises a protection violation trap sIf not, not,aathe the MMU raises a protection violation trap yes check when paging, since ? page number by a paging MMU page table for pagedthe memory managmement check all the page number by awhen pagingpaging, MMU since all pages were the size and pages the same same size and IfIf the is the raises the segment segment number numberwere is invalid, invalid,

the MMU MMU raises all possible values of all possible values of ddpp were were aa segmentation error trap to OS segmentation error trap to OS ItThe segment table is where the protection bits applicable to each The MMU MMU splits splits up up the the logical logical The displacement within legal, segments Thealways displacement within always legal, but but segments are are address receives from segment stored the in fact,the thats onelength indicator ofentry a in address ititare receives from the segment, d variable so aa given the segment, dss,, is is then then variable length soEach given Each entry in ? ? ? CPU into two fields: a segment CPU into two fields: a segment segment: Something that coherent inmay, terms of its segment and in general Note the checked against the this binding mechanism segment may, and insegment general the segment checked against the Note that that thisis binding mechanism ds number aa displacement number and andrequirements displacement will, be less than the maximum table records size limit of the segment means that a segment must be stored will, be less than the maximum protection and independent of other table records size limitmust of the means that a segment besegment stored within within that that segment segment nn possible segment size of 2 the protection from the segment table contiguously in main memory! possible segment size of 2 the protection from the segment table contiguously in main memory! segments protection requirements bytes, nn is the size, bytes, where where isbits, the number number bits, size, and and Thats back to Thats not not progress; progress;ofwere were back to bits of the base of base bits for for the the dds field field ofaddress the base address rcontiguous w e segment memory contiguous memory management management sand and logical address for aa segment segment protection size address logical address for external again! external fragmentation fragmentation again! +

bits MSJ-12 Paging Within a Segment Gets the Best of Both Worlds The The MMU MMU checks checks for for protection protection and and segment segment memory size size violations violations as as before before CPU LA s management unit (MMU) Each Each segment segment has has segmentation error, core dumped no p dsdp ds < limityes ? its its own own page page table table main memory paging using p, dp, and the segments page table, PTs PA PTs The IfIf the to The only only change to to the the the segment segment table table were were stored stored in in memory memory as as opposed opposed to change segment table segment segment registers address the memory segment table is is that that legality of the logical Once registers in the MMU the CPUs CPUs requested memory segment tablerequested Once the the legalityin ofthe theMMU logical address the operation would 33 accesses to memory: the base base address address is is and requested operation are operation would take take accesses to physical physical memory: and the the CPUs CPUs requested operation are now for determined, One the now#s for the the segments segments the within determined, One to to retrieve retrieve the segment segment table table entry for for segment segment #s the displacement displacement withinentry table, segment, One the page table entry for segment page table,ssnot not for for the the ddss,, is two fields, segment, One to to retrieve retrieve thesplit pageinto table entry for page page pp of ofpage segment is then then split into two fields, aaThe access to the physical segment itself itself The access towithin the final, final, bound physical address segment page number the segment and page number within thebound segment and address aa displacement within displacement within the the page page A would mandatory A TLAB TLAB would be be essentially essentially mandatory here here Binding via Binding is is then then completed completed via the the protection segment page table segments segments page page table table bits size base address MSJ-13

Recently Viewed Presentations

  • Cluster groups - SBVTS

    Cluster groups - SBVTS

    General practitioners (GPs) are the first point of contact for nearly all NHS patients. They can direct you to other NHS services, and are experts in family medicine, preventative care, health education and treating people with multiple and long-term conditions.
  • Target setting: Is it feasible in the Early years foundation ...

    Target setting: Is it feasible in the Early years foundation ...

    ELG: children count reliably with numbers from 1 - 20, place them in order and say which one is one more or less than the other. I can count sets of different objects to 20. I can identify numbers to...
  • TERTIARY SECTOR - WordPress.com

    TERTIARY SECTOR - WordPress.com

    Tertiary Sector. The tertiary sector provides services to people or to other economic sectors. These services include transport, communications, commerce, tourism, healthcare and education.
  • 1. Pension: 2. Pension Plan Sponsor/Policy New Pension

    1. Pension: 2. Pension Plan Sponsor/Policy New Pension

    (Please use the updated form from our CISVA Benefits website) Total employer and employee contributions to an RPP (including Voluntary RPP contributions) are limited to the lesser of the current year's contribution limit (as set by CRA) and 18% of...
  • Fourth Grade ELA - C-PP ELA

    Fourth Grade ELA - C-PP ELA

    4th Grade ELA Matrix. The 4th Grade Matrix is a tool for teachers and parents outlining the curriculum, standards, and assessments that make up the individual modules.
  • I don&#x27;t do motivation - Mark Le Messurier

    I don't do motivation - Mark Le Messurier

    This book was designed for special education coordinators, class teachers, school support officers, counsellors, psychologists and leaders in schools, as well as for parents at home.
  • Integration - Aquinas Maths

    Integration - Aquinas Maths

    Integration. You can use numerical integration. In C2 you saw how to estimate the area under a curve by using the trapezium rule. This method can take time and is only an approximation, but it allows you to find areas...
  • Canada &amp; World War I

    Canada & World War I

    - Old Empire - Young / aggressive - NAVY - ARMY = TENSIONS. 2. another type of nationalism growing in colonized countries: =intense loyalty toward and desire to preserve one's cultural identity, language, traditions Eg. Slavic nations