DOC PREVIEW
SJSU CS 147 - Revision Mid 2 &Virtual Memory

This preview shows page 1-2-3-4-5-32-33-34-35-64-65-66-67-68 out of 68 pages.

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

Unformatted text preview:

Revision Mid 2 &Virtual MemorySlide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Fixed (Static) PartitionsSimplified Fixed Partition Memory Table (Table 2.1)Slide 14Dynamic PartitionsDynamic Partitioning of Main Memory & Fragmentation (Figure 2.2)Dynamic Partition Allocation SchemesFirst-Fit Allocation Example (Table 2.2)Best-Fit Allocation Example (Table 2.3)First-Fit Memory RequestBest-Fit Memory RequestBest-Fit vs. First-FitRelease of Memory Space : DeallocationCase 1: Joining 2 Free BlocksCase 2: Joining 3 Free BlocksCase 3: Deallocating an Isolated BlockRelocatable Dynamic PartitionsCompaction StepsMemory Before & After Compaction (Figure 2.5)Virtual MemoryMotivations for Virtual MemoryVirtual MemoryLevels in Memory HierarchyDRAM vs. SRAM as a “Cache”Locating an Object in a “Cache” (cont.)A System with Physical Memory OnlyA System with Virtual MemoryPage Faults (Similar to “Cache Misses”)TerminologyImportance of Hit RatioCache vs Virtual MemoryCache Replacement AlgorithmsLRU vs RandomVirtual Memory Replacement AlgorithmsOptimalSlide 46FIFOSlide 48Example of FIFO InconsistencyLRUSlide 51Example of LRU ConsistencyServicing a Page FaultHandling Page FaultsPage FaultWhat to Page inVM Page ReplacementMeasuring Demand Paging PerformancePerformance ExamplePage Replacement AlgorithmsThe Best Page to ReplacePage Replacement - FIFOFIFO vs. OptimalSecond ChanceClock ReplacementNot Recently Used Page Replacement AlgorithmLeast Recently Used (LRU)LRU ApproximationsRevision Mid 2 &Virtual Memory Prof. Sin-Min LeeDepartment of Computer ScienceclkTclearNote that when Clear is 1, everything goes to 0.When Clear is 0, this does not affect the others.Q1Fixed (Static) Partitions•Attempt at multiprogramming using fixed partitions –one partition for each job–size of partition designated by reconfiguring the system–partitions can’t be too small or too large.•Critical to protect job’s memory space.•Entire program stored contiguously in memory during entire execution.•Internal fragmentation is a problem.Simplified Fixed Partition Memory Table (Table 2.1)PartitionsizeMemoryaddressAccess Partitionstatus100K 200K Job 1 Busy25K 300K Job 4 Busy25K 325K Free50K 350K Job 2 BusyOriginal State After Job Entry100K Job 1 (30K)Partition 1Partition 1Partition 225K Job 4 (25K)Partition 2Partition 325KPartition 3Partition 450K Job 2 (50K)Partition 4Job List :J1 30KJ2 50KJ3 30KJ4 25KTable 2.1 : Main memory use during fixed partition allocation of Table 2.1. Job 3 must wait.Dynamic Partitions•Available memory kept in contiguous blocks and jobs given only as much memory as they request when loaded.•Improves memory use over fixed partitions.•Performance deteriorates as new jobs enter the system–fragments of free memory are created between blocks of allocated memory (external fragmentation).Dynamic Partitioning of Main Memory & Fragmentation (Figure 2.2)Dynamic Partition Allocation Schemes•First-fit: Allocate the first partition that is big enough.–Keep free/busy lists organized by memory location (low-order to high-order).–Faster in making the allocation.•Best-fit: Allocate the smallest partition that is big enough– Keep free/busy lists ordered by size (smallest to largest). –Produces the smallest leftover partition.–Makes best use of memory.First-Fit Allocation Example (Table 2.2) J1 10K J2 20K J3 30K* J4 10KMemory Memory Job Job Internallocation block size number size Status fragmentation10240 30K J1 10K Busy 20K40960 15K J4 10K Busy 5K56320 50K J2 20K Busy 30K107520 20K FreeTotal Available: 115K Total Used: 40KJob ListBest-Fit Allocation Example(Table 2.3) J1 10K J2 20K J3 30K J4 10KMemory Memory Job Job Internallocation block size number size Status fragmentation40960 15K J1 10K Busy 5K107520 20K J2 20K Busy None10240 30K J3 30K Busy None56230 50K J4 10K Busy 40KTotal Available: 115K Total Used: 70KJob ListFirst-Fit Memory RequestBefore request After requestBeginningaddressMemoryblock sizeBeginningaddressMemoryblock size4075 105 4075 1055225 5 5225 56785 600 *6985 4007560 20 7560 207600 205 7600 20510250 4050 10250 405015125 230 15125 23024500 1000 24500 1000Best-Fit Memory RequestBefore request After requ estBeginningaddressMemoryblock sizeBeginningaddressMemoryblock size4075 105 4075 1055225 5 5225 56785 600 6785 6007560 20 7560 207600 205 *7800 510250 4050 10250 405015125 230 15125 23024500 1000 24500 1000Best-Fit vs. First-FitFirst-Fit•Increases memory use•Memory allocation takes less time•Increases internal fragmentation•Discriminates against large jobsBest-Fit•More complex algorithm•Searches entire table before allocating memory•Results in a smaller “free” space (sliver)Release of Memory Space : Deallocation•Deallocation for fixed partitions is simple–Memory Manager resets status of memory block to “free”.•Deallocation for dynamic partitions tries to combine free areas of memory whenever possible–Is the block adjacent to another free block?–Is the block between 2 free blocks?–Is the block isolated from other free blocks?Case 1: Joining 2 Free BlocksBefore Deallocation After DeallocationBeginningaddressMemoryblock sizeStatus BeginningaddressMemoryblock sizeStatus4075 105 Free 4075 105 Free5225 5 Free 5225 5 Free6785 600 Free 6785 600 Free7560 20 Free 7560 20 Free(7600) (200) (Busy)1*7600 205 Free*7800 5 Free 10250 4050 Free10250 4050 Free 15125 230 Free15125 230 Free 24500 1000 Free24500 1000 FreeCase 2: Joining 3 Free BlocksBefore Dealloca tion After DeallocationBeginningaddressMemoryblock sizeStatus BeginningaddressMemoryblock sizeStatus4075 105 Free 4075 105 Free5225 5 Free 5225 5 Free6785 600 Free 6785 600 Free7560 20 Free 7560 245 Free(7600) (200) (Busy)1* (null)*7800 5 Free 10250 4050 Free10250 4050 Free 15125 230 Free15125 230 Free 24500 1000 Free24500 1000 FreeCase 3: Deallocating an Isolated BlockBusy List Before Busy List AfterBeginningaddressMemoryblock sizeStatus BeginningaddressMemoryblock sizeStatus7805 1000 Busy 7805 1000 Busy*8805 445 Busy * (null entry)9250 1000 Busy 9250 1000 BusyRelocatable Dynamic Partitions•Memory Manager relocates programs to gather all empty blocks and compact them to make 1 memory block.•Memory compaction (garbage collection, defragmentation) performed by OS to reclaim fragmented sections of memory space. •Memory Manager optimizes use of memory & improves


View Full Document

SJSU CS 147 - Revision Mid 2 &Virtual Memory

Documents in this Course
Cache

Cache

24 pages

Memory

Memory

54 pages

Memory

Memory

70 pages

Lecture 1

Lecture 1

53 pages

Cisc

Cisc

18 pages

Quiz 1

Quiz 1

4 pages

LECTURE 2

LECTURE 2

66 pages

RISC

RISC

40 pages

LECTURE 2

LECTURE 2

66 pages

Lecture 2

Lecture 2

67 pages

Lecture1

Lecture1

53 pages

Chapter 5

Chapter 5

14 pages

Memory

Memory

27 pages

Counters

Counters

62 pages

Load more
Download Revision Mid 2 &Virtual 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 Revision Mid 2 &Virtual 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 Revision Mid 2 &Virtual 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?