1VirtualMemoryCS217MemoryManagement• Problem1:Twoprogramscan’tcontrolallofmemorysimultaneously• Problem2:Oneprogramshouldn’tbeallowedtoaccess/changethememoryofanotherprogram• Problem3:Machinemayhaveonly256MBofmemory,whilevirtualaddressspaceis4GB00xffffffffTextDataBSSStackHeap0x2000OSOperatingsystemmustmanagesharingofphysicalmemorybetweenmanyprocessesOperatingsystemmustmanagesharingofphysicalmemorybetweenmanyprocesses2VirtualMemory• BasicideaProgramsdon’t(andcan’t)namephysicaladdressesInstead,theynamevirtualaddresses(eachprocesshasownaddressspace)Thekerneltranslateseachvirtualaddressintoaphysicaladdressbeforetheoperationiscarriedout• AdvantagesCanrunmanyprogramsatonce,withoutthemworryingthattheywillusethesamephysicalmemoryKernelcontrolsaccesstophysicalmemory,sooneprogramcan’taccessormodifythememoryofanotherCanrunaprogramthatusesmorevirtualmemorythanthecomputerhasavailableinphysicalmemorySegmentation• AllocatememoryforsegmentsProvidemappingfromaddressesinsegmentstophysicalmemory• Usebaseandlimitregisterstotranslatevirtualaddressestophysicaladdresses12PhysicalMemoryBaseregisterLimitregistercpu <limit base+VirtualAddressPhysicalAddress312PhysicalMemorySegmentation• AllocatememoryforsegmentsProvidemappingfromaddressesinsegmentstophysicalmemory• Problems:SegmentsmaygrowFragmentationLargeprocessesSwappingefficiencyBaseregisterLimitregisterDiskStorage3Paging• MotivationMappingentiresegmentsistoocoarsegranularityMappingindividualbytesistoofinegranularity• PagesDivideupmemoryintoblocks,calledpages(~4KB)EachvirtualpagecanbemappedtoanyphysicalpageEachtranslationinvolvestwosteps:– Decidewhichphysicalpage holdsthevirtualaddress– DecideawhatoffsetthevirtualaddressisinsidethepageThephysicaladdressisformedbygluingtogetherthephysicalpagenumberandtheoffsetwithinthepage4Paging• PagetablemapsvirtualaddressestophysicaladdressesSilberschatz&PetersonPaging(cont)Silberschatz&Peterson5PagedSegmentationSilberschatz&PetersonSwapping• Whathappensifcumulativesizesofsegmentsexceedsphysical memory?6SwappingtoDisk• Ifallthevirtualmemorycan’tfitinphysicalmemory,theOScantemporarilystashsomepagesondiskCansupportvirtualmemorybiggerthanphysicalmemorySilberschatz&PetersonPageTable• TheOSstoresforeachpage...Physicalpagenumber(24bits)Cacheablebit(C)Modifiedbit(M)Referencedbit(R)Accesspermissions(Readonly,Read/write)Valid/invalid(V)7PageFaults• Ifprocessaccessesvirtualaddressthatmapstoapagenotinmemory,thentheOSmustfetchthatpagefromdisk• Sincemostreferencesfollowothersonsamepage,thecostofreadingfromdiskisamortizedacrossmanyreferencesSilberschatz&PetersonPageReplacement• Whenreadonepagefromdisk,anotherpagemustbeevicted?• Whichpageshouldbereplaced?Ideal:– OnethatwillbeaccessedfurthestinfuturePracticalheuristics:– Leastrecentlyused– Leastfrequentlyused– Etc.void StringArray_read(StringArray_Ts,FILE*fp){charstring[MAX_STRING_LENGTH];s->nstrings =0;while(fgets(string,MAX_STRING_LENGTH, fp)){StringArray_grow(nstrings+1);s->strings[(s->nstrings)++]= strdup(string);}}8PageReplacement(cont)Silberschatz&PetersonWorkingSets• LocalityofreferenceMostmemoryreferencesarenearbypreviousones• WorkingsetAtanypointinaprogram’sexecution,usuallyasmallregionofmemoryisaccessedfrequentlyTheregionofmemory(workingset)changesduringthecourseofexecutionint main(){Array_T*strings;strings= ReadStrings(stdin);SortStrings(strings);WriteStrings(strings,stdout);return0;}9Thrashing• Whathappenswhencumulativesizeofworkingsetsexceedscapacityofphysicalmemory?StorageHierarchy• Registers~128,1-5nsaccesstime(CPUcycletime)• Cache1KB– 4MB,20-100ns(multiplelevels)• Memory64MB– 2GB,200ns• Disk1GB– 100GB,10ms• Long-termStorage1TB,1-10s10StorageHierarchyLatencyJimGraySummary• MemorymanagementImportantfunctionofoperatingsystemUnderstandinghowitworksiscriticaltoeffectivesystemdevelopment• VirtualmemoryOS&HardwaresupportformappingvirtualaddressestophysicaladdressesMappingisusuallyatpagegranularity,whichfacilitates...– Relocation– Swappingtodisk– Protection– Fragmentation–
View Full Document