DOC PREVIEW
U of I CS 241 - Memory

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1Copyright ©: Nahrstedt, Angrave, Abdelzaher 1Memory Copyright ©: Nahrstedt, Angrave, Abdelzaher2Memory Allocation Compile for overlays Compile for fixed Partitions Separate queue per partition Single queue Relocation and variable partitions Dynamic contiguous allocation (bit maps versus linked lists) Fragmentation issues Swapping Paging2Copyright ©: Nahrstedt, Angrave, Abdelzaher3OverlaysOverlay ManagerOverlay AreaMain ProgramOverlay 1Overlay 2Overlay 3Secondary StorageOverlay 1Overlay 2Overlay 3Overlay 10K5k7k12kCopyright ©: Nahrstedt, Angrave, Abdelzaher4Multiprogramming with Fixed Partitions Divide memory inton(possible unequal) partitions.  Problem: FragmentationFree Space0k4k16k64k128k3Copyright ©: Nahrstedt, Angrave, Abdelzaher5Fixed PartitionsLegendFree Space0k4k16k64k128kInternalfragmentation(cannot be reallocated)Copyright ©: Nahrstedt, Angrave, Abdelzaher6Fixed Partition Allocation Implementation Issues Separate input queue for each partition Requires sorting the incoming jobs and putting them into separate queues Inefficient utilization of memory when the queue for a large partition is empty but the queue for a small partition is full. Small jobs have to wait to get into memory even though plenty of memory is free.  One single input queue for all partitions.  Allocate a partition where the job fits in.  Best Fit  Worst Fit First Fit4Copyright ©: Nahrstedt, Angrave, Abdelzaher7Relocation Correct starting address when a program starts in memory  Different jobs will run at different addresses When a program is linked, the linker must know at what address the program will begin in memory.  Logical addresses, Virtual addresses Logical address space , range (0 to max)  Physical addresses, Physical address space range (R+0 to R+max) for base value R.  User program never sees the real physical addresses  Memory-management unit (MMU) map virtual to physical addresses.  Relocation register Mapping requires hardware (MMU) with the base registerCopyright ©: Nahrstedt, Angrave, Abdelzaher8Relocation RegisterMemoryBase RegisterCPU InstructionAddress+BAMAMA+BAPhysicalAddressLogicalAddress5Copyright ©: Nahrstedt, Angrave, Abdelzaher9Question 1 - Protection Problem: How to prevent a malicious process to write or jump into other user's or OS partitions Solution: Base bounds registersCopyright ©: Nahrstedt, Angrave, Abdelzaher10Base Bounds RegistersMemoryBounds Register Base RegisterCPUAddress< +MemoryAddress MALogicalAddress LAPhysical AddressPAFaultBase AddressLimit AddressMA+BABaseAddressBA6Copyright ©: Nahrstedt, Angrave, Abdelzaher11Contiguous Allocation and Variable Partitions: Bit Maps versus Linked Lists Part of memory with 5 processes, 3 holes tick marks show allocation units shaded regions are free Corresponding bit mapCopyright ©: Nahrstedt, Angrave, Abdelzaher12More on Memory Management with Linked Lists Four neighbor combinations for the terminating process X7Copyright ©: Nahrstedt, Angrave, Abdelzaher13Contiguous Variable Partition Allocation schemes Bitmap and link list Which one occupies more space? Depending on the individual memory allocation scenario. In most cases, bitmap usually occupies more space. Which one is faster reclaim freed space? On average, bitmap is faster because it just needs to set the corresponding bits Which one is faster to find a free hole? On average, a link list is faster because we can link all free holes togetherCopyright ©: Nahrstedt, Angrave, Abdelzaher14Storage Placement Strategies Best fit Use the hole whose size is equal to the need, or if none is equal, the whole that is larger but closest in size.  Rationale? First fit Use the first available hole whose size is sufficient to meet the need Rationale? Worst fit Use the largest available hole Rationale?8Copyright ©: Nahrstedt, Angrave, Abdelzaher15Storage Placement Strategies Every placement strategy has its own problem Best fit Creates small holes that cant be used  Worst Fit Gets rid of large holes making it difficult to run large programs  First Fit Creates average size holes Copyright ©: Nahrstedt, Angrave, Abdelzaher16How Bad Is Fragmentation? Statistical arguments - Random sizes First-fit Given N allocated blocks 0.5∗N blocks will be lost because of fragmentation Known as 50% RULE9Copyright ©: Nahrstedt, Angrave, Abdelzaher17Solve Fragmentation w. CompactionMonitor Job 3FreeJob 5 Job 6Job 7 Job 85Monitor Job 3FreeJob 5 Job 6Job 7 Job 86Monitor Job 3FreeJob 5 Job 6Job 7 Job 87Monitor Job 3FreeJob 5 Job 6Job 7 Job 88Monitor Job 3FreeJob 5 Job 6Job 7 Job 89Copyright ©: Nahrstedt, Angrave, Abdelzaher18Storage Management Problems Fixed partitions suffer from internal fragmentation Variable partitions suffer from external fragmentation Compaction suffers from  overhead10Copyright ©: Nahrstedt, Angrave, Abdelzaher19Question What if there are more processes than what could fit into the memory?Copyright ©: Nahrstedt, Angrave, Abdelzaher20SwappingMonitorDiskUserPartition11Copyright ©: Nahrstedt, Angrave, Abdelzaher21SwappingMonitorDiskUser 1UserPartitionCopyright ©: Nahrstedt, Angrave, Abdelzaher22SwappingMonitorUser 1DiskUser 1UserPartition12Copyright ©: Nahrstedt, Angrave, Abdelzaher23SwappingMonitorUser 2User 1DiskUser 1UserPartitionCopyright ©: Nahrstedt, Angrave, Abdelzaher24SwappingMonitorDiskUser 2User 2UserPartitionUser 113Copyright ©: Nahrstedt, Angrave, Abdelzaher25SwappingMonitorDiskUser 2User 2UserPartitionUser 1Copyright ©: Nahrstedt, Angrave, Abdelzaher26SwappingMonitorDiskUser 1User 2UserPartitionUser 114Paging Request3 1234DiskMemoryVirtual Memory Stored on Disk1 2 3 4 5 6 7 81 2 3 41234Page TableVM FrameReal MemoryRequest Page 3Paging3 11 234DiskMemoryVirtual Memory Stored on Disk1 2 3 4 5 6 781 2 3 41234Page TableVM FrameReal MemoryRequest Page 115Paging3 116234DiskMemoryVirtual Memory Stored on Disk1 2 3 4 5 6 7 81 2 3 41234Page TableVM FrameReal MemoryRequest Page 6Paging3 116234DiskMemoryVirtual Memory Stored on Disk123456781 2 3 41234Page TableVM FrameReal MemoryRequest Page 2216Page Mapping HardwareContents(P,D)Contents(F,D)P DF DP→F0101101Page TablePhysical MemoryVirtual Address (P,D)Physical Address (F,D)PFDDPVirtual MemoryPage Mapping HardwareContents(4006)Contents(5006)004 006005 0064→50101101Page


View Full Document

U of I CS 241 - Memory

Documents in this Course
Process

Process

28 pages

Files

Files

37 pages

File I/O

File I/O

52 pages

C Basics

C Basics

69 pages

Threads

Threads

14 pages

Lecture

Lecture

55 pages

C Basics

C Basics

24 pages

Signals

Signals

27 pages

Memory

Memory

45 pages

Threads

Threads

47 pages

Threads

Threads

28 pages

LECTURE

LECTURE

45 pages

Threads

Threads

30 pages

Threads

Threads

55 pages

Files

Files

37 pages

SIGNALS

SIGNALS

22 pages

Files

Files

37 pages

Threads

Threads

14 pages

Threads

Threads

13 pages

Load more
Download Memory
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Memory and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Memory 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?