DOC PREVIEW
UE CS 470 - LECTURE NOTES

This preview shows page 1-2-16-17-18-33-34 out of 34 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 34 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 34 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 34 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 34 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 34 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 34 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 34 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 34 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Lecture 20OutlineVariable-Size Partitions 1Variable-Size Partitions 2Variable-Size Partitions 3Fragmentation 1Fragmentation 2Fragmentation 3Fragmentation 4Fragmentation 5Fragmentation 6Static, Complete, Contiguous OrganizationStorage Organization IssuesPaging 1Paging 2Address Translation 1Address Translation 2Very Small, Concrete Example 1Very Small, Concrete Example 2Larger ExamplePaging 3Paging 4Page TablesTranslation Look-aside Buffer (TLB) 1Translation Look-aside Buffer (TLB) 2Address Translation with TLB 1Address Translation with TLB 2Effective Memory Access Time 1Effective Memory Access Time 2Effective Memory Access Time 3Paging IssuesVery Large Address Spaces 1Very Large Address Spaces 2Very Large Address Spaces 3Friday, February 25 CS 470 Operating Systems - Lecture 20 1Lecture 20Reminder: Homework 4 due todayHomework 5 posted; due Wednesday after spring break.Questions?Friday, February 25 CS 470 Operating Systems - Lecture 20 2OutlineFragmentationPagingPage tablesTranslation look-aside buffer (TLB)Effective memory access timeVery large address spacesFriday, February 25 CS 470 Operating Systems - Lecture 20 3Variable-Size PartitionsThe processes arrive at time 0 in the order specified.Memory request CPU burst time (ms)P1600K 10P21000K 5P3300K 20P4700K 8P5500K 15Friday, February 25 CS 470 Operating Systems - Lecture 20 4Variable-Size PartitionsIf q = 1, then P2 terminates at t = 14, leaving a 1000K hole. This is enough to load P4, leaving a 300K hole.P1 terminates at t = 28, and OS allocates P5, leaving a 100K hole.OS - 400KP5 - 500KHole - 100KP4 - 700KHole - 300KP3 - 300KHole - 260KFriday, February 25 CS 470 Operating Systems - Lecture 20 5Variable-Size PartitionsIn this scheme, releasing is easy, just add hole to the head of a linked list.Allocation is much harder - if more than one hole is big enough, which hole?First fitBest fitWorst fit ??Friday, February 25 CS 470 Operating Systems - Lecture 20 6FragmentationBoth fixed-sized and variable-sized partition schemes suffer from fragmentation, that is, memory space that is unused due to the memory organization.Variable-size partition organization causes external fragmentation. That is, the unused memory is outside of any allocation. In particular, eventually all the holes will be small, so while there may be enough total free space to run another program, there is not enough contiguous to do so.Friday, February 25 CS 470 Operating Systems - Lecture 20 7FragmentationFixed-size partition organization causes internal fragmentation. That is, a process has been allocated more memory than it needs to run, so the unused memory is inside an allocation. On average, a partition will be only half filled. Thus even when all of the memory is allocated, the system could have run more programs had the partitions been smaller.Friday, February 25 CS 470 Operating Systems - Lecture 20 8FragmentationSince fixed-size partitions are determined by the memory architecture, there is not much that can be done about internal fragmentation.But we can and should do something about external fragmentation when using variable-size partitions. E.g., in the earlier scenario, when P1 terminates, it releases 1000K of which P4 took 700K, leaving a 300K hole. If this free space were added to the other 260K hole, 560K would be large enough to hold P5 as well.Friday, February 25 CS 470 Operating Systems - Lecture 20 9FragmentationA simple technique to handle fragmentation is to coalesce holes that are next to each other forming one larger hole of contiguous memory. This can be done just after a process terminates, but would not help our scenario, since the holes are not contiguous.Friday, February 25 CS 470 Operating Systems - Lecture 20 10FragmentationA better technique is to do compaction. That is, put all the free space together by moving processes. E.g.,Slide all process towards one endMove processes from one end to the otherMove processes in the middle to the endsDeallocation becomes more difficult.Friday, February 25 CS 470 Operating Systems - Lecture 20 11FragmentationCompaction can be done by swapping processes out to disk and then back into a different location. This requires a data structure to keep track of what's on disk and where.Usually want to do this anyway, so that programs can be "pre-loaded" (resolving memory addressing, etc.), so that loading into memory is faster than trying to do it directly from the file system.Friday, February 25 CS 470 Operating Systems - Lecture 20 12Static, Complete, Contiguous OrganizationGenerally, fixed-size partitions are favored over variable-size partitions. They are faster to allocate and deallocate, and are simpler to manage. Just need to make sure the partition size is big enough, but not too big.Friday, February 25 CS 470 Operating Systems - Lecture 20 13Static, Complete, Non-Contiguous OrganizationRecall: The issues in storage organization include providing support for:single vs. multiple processescomplete vs. partial allocationfixed-size vs. variable-size allocationcontiguous vs. fragmented allocationstatic vs. dynamic allocation of partitionsLooked at schemes created by the bolded choices. What happens if we allow non-contiguous allocation?Friday, February 25 CS 470 Operating Systems - Lecture 20 14PagingIn non-contiguous allocation schemes, the logical address space is still contiguous, but it is divided into multiple partitions that are mapped separately into (possibly) non-contiguous physical space.Simplest is paging, which uses fixed-size partitions. Logical memory is divided into fixed-size partitions called pages. Physical memory is divided into partitions of the same size called frames. Backing store also is divided this way.Friday, February 25 CS 470 Operating Systems - Lecture 20 15PagingAn admitted program is allocated memory by finding enough physical frames to map the logical pages.Since all the partitions are the same size (logical page, backing store partition, physical frame), any frame can accept any page.The MMU for this is more complex. Need a page table (basically an array) that is indexed by page numbers with frame number element values.Friday, February 25 CS 470 Operating Systems - Lecture 20 16Address Translationf dp dfCPUpflog. addr.log. addr. phys. addr.dpage table main memoryFriday, February 25 CS 470 Operating


View Full Document

UE CS 470 - LECTURE NOTES

Download LECTURE NOTES
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 LECTURE NOTES 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 LECTURE NOTES 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?