logging in or signing up 7134216-Memory-Management KailashDangwal Download Post to : URL : Related Presentations : Let's Connect Share Add to Flag Embed Email Send to Blogs and Networks Add to Channel Copy embed code: Embed: Flash iPad Dynamic Copy Does not support media & animations Automatically changes to Flash or non-Flash embed WordPress Embed Customize Embed URL: Copy Thumbnail: Copy The presentation is successfully added In Your Favorites. Views: 130 Category: Entertainment License: All Rights Reserved Like it (0) Dislike it (0) Added: March 27, 2012 This Presentation is Public Favorites: 1 Presentation Description No description available. Comments Posting comment... Premium member Presentation Transcript Memory Management: Memory Management Operating Sytems Lecture 4Today: Today We’ll try to finish most of memory management today EXAM two weeks from today Material covered only up through today Lab before exam will be a study session for the examEarly memory management schemes: Early memory management schemes Originally used to devote computer to single user: User has all of memory 0 65535Limitations of single-user contiguous scheme: Limitations of single-user contiguous scheme Only one person using the machine--lots of computer time going to waste (why?) Largest job based on size of machine memoryNext: fixed partitions: Next: fixed partitions Created chunks of memory for each job: Job 1 Job 2 Job 3 0 65535Limitations of fixed partitions: Limitations of fixed partitions Operator had to correctly guess size of programs Programs limited to partitions they were given Memory fragmentation resulted The kind illustrated here is called internal memory fragmentationDynamic Partitions: Dynamic Partitions 1 3 4 2 1 6 5 7Internal versus external memory fragmentation:: Internal versus external memory fragmentation: Job 8 Space previously allocated by Job 1 Space currently allocated by Job 8Dynamic Partitions: Dynamic Partitions Contiguous memory is still required for processes How do we decide size of the partitions? Once the machine is going, how do old jobs get replaced by new ones?Dynamic Partitions: First Fit: Dynamic Partitions: First Fit In this scheme, we search forward in the “free list” for a partition large enough to accommodate the next job Fast, but the gaps left can be largeDynamic Partitions: Best Fit: Dynamic Partitions: Best Fit In this scheme, we try to find the smallest partition large enough to hold the next job This tends to minimize the size of the gaps But it also requires that we keep list of free spacesDeallocating memory: Deallocating memory If the block we are deallocating is adjacent to one or two free blocks, then it needs to be merged with them. So either we are returning a pointer to the free block, or we are changing the size of a block, or bothRelocatable Dynamic Partitions: Relocatable Dynamic Partitions We can see that in some cases, a job can “fit” into the combined spaces within or between partitions of the early schemes So how do we take advantage of that space? One way is to move programs while they are in the machine--compacting them down into the lower end of memory above the operating systemSeveral names for this: Several names for this Garbage collection Defragmentation Compaction All share a problem: relative addressing!Special registers: Special registers Early machine architectures went through a phase of “more complexity is better” Few registers, but large sets of commands RISC computers have changed all of that (for architectural reasons we won’t go into in detail)But...: But... In order to manage dynamic relocatable partitions, two registers were assigned to each partition Note: jobs were not broken into parts, but were relocated whole hog Note that the whole job is stored in memory--still no heavy use of external storage devicesSummary of early schemes: Summary of early schemes These were adequate for batch jobs But speed of components continued to advance Storage devices appear And then the biggie: remote terminals Note that processor speeds double about every 1.5 years--much faster than memory!To accommodate changes: To accommodate changes We really need to be able to extend memory by hiding unused parts of programs on storage devices--called virtual memory We can do this if we can break a program into pieces--called pages --that can be independently loaded and removed from memory without affecting the running programPaged Memory: Paged Memory Allows jobs to reside in noncontiguous memory More jobs can be squeezed into memory But—some internal fragmentation, particularly if the number of jobs is largeDisk partitions to page frames: Disk partitions to page frames Disk partitions varied in size before Now we want to fix the size to match the chunk size of the programs coming in (plus a tiny bit of bookkeeping space) We call these chunks of memory page framesIs there any fragmentation?: Is there any fragmentation? We can see that if page frames are chosen right, we shouldn’t have external fragmentation Seldom will the size of code exactly fit the frames, so there will be a little bit of internal fragmentation Tradeoff between internal fragmentation and processor time spent managing framesOther problems: Other problems Earliest schemes didn’t allow virtual memory Tables for managing memory a significant part of the operating system--its growing!Demand Paging: Demand Paging Demand paging broke jobs into pieces and became popular because it allowed only parts of jobs to be active in memory New problems: thrashing and page faultsPage Replacement Algorithms: Page Replacement Algorithms Optimal page replacement simply not possible Keep referenced (R) and Modify (M) bits to allow us to keep track of past usage instead Page is referenced by any read or write in it Page is modified by any change (write) made to itPage Replacement Algorithms, Continued: Page Replacement Algorithms, Continued FIFO = First in, first out LRU = Least recently used LFU = Least frequently used both of the latter rely on a page request call to the operating system a failure to find a page = page interrupt we might measure quality by failure rate = page interrupts / page requestsPage Replacement Algorithms, Continued: Page Replacement Algorithms, Continued Clock page replacement Hand of the clock points to the oldest page If a page fault occurs, check R bits in “clockwise” order A variant called the “two-handed clock” is used in some UNIX systemsFIFO solution is not more memory: FIFO solution is not more memory Called Belady’s anomaly the page request order is an important factor, not just the size of memoryLRU: LRU Doesn’t suffer from Belady’s anomaly Presumes locality of reference But while it works well, it is a little more complex to implement in software Consequently, aging and various clock algorithms are the most common in practice Aging can yield a good approximationSegmented Memory Allocation: Segmented Memory Allocation Instead of equal divisions, try to break code into its natural modules Compiler now asked to help operating system No page frames--different sizes required (meaning we get external fragmentation again)Segmented/Demand Paging: Segmented/Demand Paging Subdivide the natural program segments into equal sized parts to load into page frames eliminates external fragmentation allows for large virtual memory, so it is often used in more modern OS’sTradeoffs: Tradeoffs Note that there is a tradeoff between external fragmentation and page faults in paging systems Note also that we probably want slightly smaller page frames in a Segmented-Demand Paging framework You do not have the permission to view this presentation. In order to view it, please contact the author of the presentation.