1Lecture 8Segmentation and PagingOctober 28, 2003Prof. Joe PasqualeDepartment of Computer Science and EngineeringUniversity of California, San Diego© 2003 by Joseph PasqualeCSE 120: Principles of Operating Systems2Before We Begin …Read Chapter 9 (on Paging and Segmentation)Midterm gradingProgramming assignment 2 will be available this weekend• due in 2 weeks, Sunday Nov 16 at midnight3Structure of Process Address SpaceText: program instructions• execute-only, fixed sizeData: variables (global, heap)• read/write, variable size• dynamic allocation by requestStack: activation records• read/write, variable size• automatic growth/shrinkageTextDataStack4Segmented Address SpaceAddress space is a set of segmentsSegment: a linearly address memory• typically contains logically-related information• examples: program code, data, stackEach segment has an identifier s, and a size n• s between 0 and S-1, S = number of segmentsLogical addresses are of form (s, i)• offset i within segment s, i must be less than n5Ex. of Segmented Address SpaceText(--x)Segment 0Stack(rw-)Segment 2SharedData(r--)Segment 3Data(rw-)Segment 10, 00, n0-11, 01, n1-12, M2, M-n23, 03, n3-1ns = size of segment s6Address Translation for SegmentsSegment table contains, for each segment s• base, bound, permissions, (+ valid bit)Logical to physical address translation• check if operation is permitted• check if i < s.bound• physical address = s.base + i7Example of Address Translationsegment s offset i10 bits 22 bits32 bit logicaladdressv perm base bound+seg[s].base + iSegment TableBase RegisterSegment TableBound Register8Advantages of SegmentationEach segment can be• located independently• separately protected• grow independentlySegments can be shared between processes9Problems with SegmentationVariable allocationDifficult to find holes in physical memoryMust use one of non-trivial placement algorithm• first fit, next fit, best fit, worst fitExternal fragmentation10Paged Address SpaceAddress space is linear sequence of pagesPage• physical unit of information• fixed sizePhysical memory is linear sequence of frames• a page fits exactly into a frame11AddressingEach page is identified by a page number 0 to N-1• N = number of pages in address space• N * pagesize = size of address spaceLogical addresses are of form (p, i)• offset i within page p• i is less than page size12Address Translation for PagesPage table contains, for each page p• frame number that corresponds to p• other: perms, valid bit, reference bit, modified bitLogical address (p, i) to physical address translation• check if operation is permitted• physical address = p.frame + i13Example of Address Translationoffset ipage p10 bits22 bits32 bit logicaladdressv perm frame #Page TableRegisteripage[p].frame32 bit physicaladdressr m14Multi-Level Page Tablesoffset ipage dir d10 bits12 bits32 bit logicaladdressidir[d]->page[p].frame32 bit physicaladdresspage p10 bits15Segmentation vs. PagingSegment is good logical unit of information• sharing, protectionPage is good physical unit of information• simple memory managementBest of both• segmentation on top of paging16Combining Segmentation and PagingLogical memory is composed of segments• each segment is composed of pagesSegment table• per process, in memory pointed to by register• entries map seg # to page table base• shared segment: entry points to shared page tablePage tables (like before)17Address TranslationLogical address: segment #, page #, and offsetIndex seg # into seg table: get base of page tableCheck bounds (number of pages using page #)• may get a segmentation violationUse page # to index into page table, get frame #Concatenate frame # and offset to get physicaladdress18Example of Address Translationsegment s10 bits32 bit logicaladdressbaseoffset i10 bitspage p12 bitsiseg[s].base->page[p].frame32 bit physicaladdress19Cost of TranslationEach page table lookup costs a memory reference• for each reference, additional references required• slows machine down by factor of 2 or moreTake advantage of locality of reference• most references are to a small number of pages• keep translations of these in high-speed memoryProblem: we don’t know which pages until referenced20Translation Lookaside Buffer (TLB)Fast associative memory keeps most recent translationsDetermine whether non-offset part of LA is in TLB• yes: get corresponding frame num for phys addr• no: wait for normal memory translation (parallel)logical page page frame21Translation Cost with TLBCost is determined by• speed of memory: ~ 100 nsec• speed of TLB: ~ 20 nsec• hit ratio: fraction of refs satisfied by TLB, ~95%Speed with no address translation: 100 nsecSpeed with address translation• TLB miss: 200 nsec (100% slowdown)• TLB hit: 120 nsec (20% slowdown)• average: 120 x .95 + 200 x .05 = 124 nsec22TLB Design IssuesThe larger the TLB• the higher the hit rate• the slower the response• the greater the expenseTLB has a major effect on performance!• must be flushed on context switches• alternative: tagging entries with PIDsMIPS: has only a TLB, no page tables!• devote more chip space to
View Full Document
Unlocking...