Chapter 3 Memory Management Includes Virtual Memory
Chapter 3 Memory Management Includes Virtual Memory
Chapter 3 Memory Management Includes Virtual Memory
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in 1
part.
Learning Objectives
After completing this chapter, you should be able to describe:
• How complex memory allocation methods function
• How page allocation methods spawned virtual memory
• How several page replacement policies compare in function and best uses
• How paging works and how a memory allocation scheme determines which
pages should be swapped out of memory
• How the concept of the working set is used in memory allocation schemes
• How cache memory issued by the operating system to improve response
time
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
2
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Introduction
• Evolution of virtual memory
o Paged, demand paging, segmented, segmented/demand paging
o Foundation of current virtual memory methods
• Areas of improvement from the need for:
o Continuous program storage
o Placement of entire program in memory during execution
• Enhanced Memory Manager performance: cache memory
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
3
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (1 of 11)
• Incoming job: divided into pages of equal size
• Best condition
o Pages, sectors, and page frames: same size
• Exact sizes: determined by disk’s sector size
• Memory manager tasks: prior to program execution
o Determine number of pages in program
o Locate enough empty page frames in main memory
o Load all program pages into page frames
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
4
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (2 of 11)
• Program: stored in noncontiguous page frames
o Advantages: more efficient memory use; compaction scheme eliminated (no
external fragmentation)
o New problem: keeping track of job’s pages (increased operating system
overhead)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
5
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (3 of 11)
(figure 3.1)
In this example, each page frame can
hold 100 bytes. This job, at 350 bytes
long, is divided among four page frames.
The resulting internal fragmentation
(wasted space) is associated with Page 3,
loaded into Page Frame 11.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
6
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (4 of 11)
• Internal fragmentation: job’s last page frame only
• Entire program: required in memory during its execution
• Three tables for tracking pages: Job Table (JT), Page Map Table (PMT), and
Memory Map Table (MMT)
o Stored in main memory: operating system area
• Job Table: information for each active job
o Job size
o Memory location: job’s PMT
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
7
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (5 of 11)
• Page Map Table: information for each page
o Page number: beginning with Page 0
o Memory address
• Memory Map Table: entry for each page frame
o Location
o Free/busy status
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
8
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (6 of 11)
(table 3.1)
Three snapshots of the Job Table. Initially the Job Table has one entry for each job (a). When the
second job ends (b), its entry in the table is released. Finally, it is replaced by the entry for the
next job (c).
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
9
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (7 of 11)
• Line displacement (offset)
o Line distance: from beginning of its page
o Line location: within its page frame
o Relative value
• Determining page number and displacement of a line
o Divide job space address by the page size
o Page number: integer quotient
o Displacement: remainder
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
10
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (8 of 11)
(figure 3.2)
This job is 350 bytes long and is divided into
four pages of 100 bytes each that are loaded
into four page frames in memory. Notice the
internal fragmentation at the end of Page 3.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
11
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (9 of 11)
• Instruction: determining exact location in memory
o Step1: Determine page number/displacement of line
o Step 2: Refer to the job’s PMT
• Determine page frame containing required page
o Step 3: Obtain beginning address of page frame
• Multiply page frame number by page frame size
o Step 4: Add the displacement (calculated in first step) to starting address of the
page frame
• Address resolution (address translation)
o Job space address (logical) → physical address (absolute)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
12
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (10 of 11)
(figure 3.3)
The sizes of this system’s page frames and pages are 512 bytes each. The PMT shows where the job's
two pages (Page 0 and Page 1) are loaded into the two available page frames (Page Frame 5 and Page
Frame 3, respectively) in main memory.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
13
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Paged Memory Allocation (11 of 11)
• Advantages
o Efficient memory use: job allocation in noncontiguous memory
• Disadvantages
o Increased overhead: address resolution
o Internal fragmentation: last page
• Page size: crucial
o Too small: very long PMTs
o Too large: excessive internal fragmentation
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
14
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (1 of 8)
• Loads only a part of the program into memory
o Removes restriction: entire program in memory
o Requires high-speed page access
• Exploits programming techniques
o Modules: written sequentially
• All pages: not needed simultaneously
o Examples
• Error-handling modules instructions
• Mutually exclusive modules
• Certain program options: mutually exclusive or not always accessible
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
15
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (2 of 8)
• Virtual memory
o Appearance of vast amounts of physical memory
• Less main memory required than paged memory allocation scheme
• Requires high-speed direct access storage device (DASDs): e.g., hard drives
or flash memory
• Swapping: how and when pages passed between memory and secondary
storage
o Depends on predefined policies
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
16
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (3 of 8)
• Algorithm implementation: tables, e.g., Job Table, Page Map Table, and
Memory Map Table
• Page Map Table
o First field: page requested already in memory?
o Second field: page contents modified?
o Third field: page referenced recently?
o Fourth field: frame number
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
17
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (4 of 8)
(figure 3.5)
Demand paging requires that the Page
Map Table for each job keep track of each
page as it is loaded or removed from main
memory. Each PMT tracks the status of
the page, whether it has been modified,
whether it has been recently referenced,
and the page frame number for each
page currently in main memory. (Note: For
this illustration, the Page Map Tables have
been simplified. See Table 3.3 for more
detail on 30th slide.)
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
18
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (5 of 8)
• Swapping process
o Resident memory page: exchanged with secondary storage page
• Resident page: copied to disk (if modified)
• New page: written into available page frame
o Requires close interaction between:
• Hardware components
• Software algorithms
• Policy schemes
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
19
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (6 of 8)
• Hardware components:
o Generate the address: required page
o Find the page number
o Determine page status: already in memory
• Page fault: failure to find page in memory
• Page fault handler: part of operating system
o Determines if empty page frames in memory
• Yes: requested page copied from secondary storage
• No: swapping (dependent on the predefined policy)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
20
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (7 of 8)
• Tables updated when page swap occurs
o PMT for both jobs (page swapped out; page swapped in) and the MMT
• Thrashing
o Excessive page swapping: inefficient operation
o Main memory pages: removed frequently; called back soon thereafter
o Occurs across jobs
• Large number of jobs: limited free pages
o Occurs within a job
• Loops crossing page boundaries
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
21
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Demand Paging Memory Allocation (8 of 8)
(figure 3.6)
An example of demand paging that causes a page swap each time the loop is executed and
results in thrashing. If only a single page frame is available, this program will have one page
fault each time the loop of this C program is executed.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
22
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Page Replacement Policies and Concepts
• Page replacement policy
o Crucial to system efficiency
• Two well-known algorithms
o First-in first-out (FIFO) policy
• Best page to remove: page in memory longest
o Least Recently Used (LRU) policy
• Best page to remove: page least recently accessed
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
23
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
First-In First-Out (1 of 3)
• Removes page: longest in memory
• Failure rate
o Ratio of page interrupts to page requests
• More memory: does not guarantee better performance
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
24
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
First-In First-Out (2 of 3)
(figure 3.7)
First, Pages A and B are loaded into the two available page frames. When Page C is needed, the first page
frame is emptied so C can be placed there. Then Page B is swapped out so Page A can be loaded there.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
25
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
First-In First-Out (3 of 3)
(figure 3.8)
Using a FIFO policy, this page trace analysis shows how each page requested is swapped into the two available page
frames. When the program is ready to be processed, all four pages are in secondary storage. When the program calls
a page that isn’t already in memory, a page interrupt is issued, as shown by the gray boxes and asterisks. This
program resulted in nine page interrupts.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
26
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Least Recently Used (1 of 3)
• Removes page: least recent activity
o Theory of locality
• Efficiency
o Additional main memory: causes either decrease in or same number of interrupts
o Does not experience FIFO Anomaly (Belady Anomaly)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
27
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Least Recently Used (2 of 3)
(figure 3.9)
Memory management using an LRU page removal policy for the program shown in Figure 3.8.
Throughout the program, 11 page requests are issued, but they cause only 8 page interrupts.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
28
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Least Recently Used (3 of 3)
• Clock replacement variation
o Circular queue: pointer steps through active pages’ reference bits; simulates a
clockwise motion
o Pace: computer’s clock cycle
• Bit-shifting variation
o 8-bit reference byte and bit-shifting technique: tracks pages’ usage (currently in
memory)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
29
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Mechanics of Paging (1 of 4)
• Page swapping
o Memory manage requires specific information: Page Map Table
(table 3.3)
Page Map Table for Job 1 shown in Figure 3.5. For the bit indicators, 1 = Yes and 0 = No.
© Cengage Learning 2018
Page No. Status Bit Modified Bit Referenced Bit Page Frame No.
0 1 1 1 5
1 1 0 0 9
2 1 0 0 7
3 1 0 1 12
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
30
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Mechanics of Paging (2 of 4)
• Page Map Table: bit meaning
o Status bit: page currently in memory
o Referenced bit: page referenced recently
• Determines page to swap: LRU algorithm
o Modified bit: page contents altered
• Determines if page must be rewritten to secondary storage when swapped out
• Bits checked when swapping
o FIFO: modified and status bits
o LRU: all bits (status, modified, and reference bits)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
31
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Mechanics of Paging (3 of 4)
(table 3.4)
The meaning of the zero and one bits in the Page Map Table.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
32
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Mechanics of Paging (4 of 4)
(table 3.5)
Four possible combinations of modified and referenced bits and the meaning of each.
Yes = 1, No = 0.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
33
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Importance of the Working Set (1 of 2)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
34
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
The Importance of the Working Set (2 of 2)
(figure 3.13)
Timeline showing the amount of time required to process page faults for a single program.
The program in this example takes 120 milliseconds (ms) to execute but an additional 900
ms to load the necessary pages into memory. Therefore, job turnaround is 1020 ms.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
35
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (1 of 6)
• Each job divided into several segments: different sizes
o One segment for each module: related functions
• Reduces page faults
o Loops: not split over two or more pages
• Main memory: allocated dynamically
• Program’s structural modules: determine segments
o Each segment numbered when program compiled/assembled
o Segment Map Table (SMT) generated
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
36
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (2 of 6)
(figure 3.14)
Segmented memory allocation. Job 1 includes a main program and two subroutines. It is a
single job that is structurally divided into three segments of different sizes.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
37
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (3 of 6)
(figure 3.15)
The Segment Map Table tracks each
segment for this job. Notice that
Subroutine B has not yet been loaded
into memory.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
38
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (4 of 6)
(figure 3.16)
During execution, the main program
calls Subroutine A, which triggers
the SMT to look up its location in
memory.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
39
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (5 of 6)
• Memory Manager: tracks segments in memory
o Job Table: one for the whole system
• Every job in process
o Segment Map Table: one for each job
• Details about each segment
o Memory Map Table: one for the whole system
• Main memory allocation
• Instructions within each segment: ordered sequentially
• Segments: not necessarily stored contiguously
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
40
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented Memory Allocation (6 of 6)
• Two-dimensional addressing scheme
o Segment number and displacement
• Disadvantage
o External fragmentation
• Major difference between paging and segmentation
o Pages: physical units; invisible to the program
o Segments: logical units; visible to the program; variable sizes
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
41
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented/Demand Paged Memory Allocation (1 of 5)
• Subdivides segments: equal-sized pages
o Smaller than most segments
o More easily manipulated than whole segments
o Segmentation’s logical benefits
o Paging’s physical benefits
• Segmentation problems removed
o Compaction, external fragmentation, secondary storage handling
• Three-dimensional addressing scheme
o Segment number, page number (within segment), and displacement (within page)
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
42
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented/Demand Paged Memory Allocation (2 of 5)
• Scheme requires four tables
o Job Table: one for the whole system
• Every job in process
o Segment Map Table: one for each job
• Details about each segment
o Page Map Table: one for each segment
• Details about every page
o Memory Map Table: one for the whole system
• Monitors main memory allocation: page frames
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
43
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented/Demand Paged Memory Allocation (3 of 5)
(figure 3.17)
How the Job Table, Segment
Map Table, Page Map Table,
and main memory interact in
a segment/paging scheme.
© Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
44
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented/Demand Paged Memory Allocation (4 of 5)
• Disadvantages
o Overhead: managing the tables
o Time required: referencing tables
• Associative memory
o Several registers allocated to each job
• Segment and page numbers: associated with main memory
o Page request: initiates two simultaneous searches
• Associative registers
• SMT and PMT
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
45
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Segmented/Demand Paged Memory Allocation (5 of 5)
• Associative memory
o Primary advantage (large associative memory)
• Increased speed
o Disadvantage
• High cost of complex hardware
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
46
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Virtual Memory (1 of 3)
• Made possible by swapping pages in/out of memory
• Program execution: only a portion of the program in memory at any given
moment
• Requires cooperation between:
o Memory Manager: tracks each page or segment
o Processor hardware: issues the interrupt and resolves the virtual address
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
47
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Virtual Memory (2 of 3)
(table 3.6)
Comparison of the advantages and disadvantages of virtual memory with paging and
segmentation.
© Cengage Learning 2018
Virtual Memory with Paging Virtual Memory with Segmentation
Allows internal fragmentation within page frames Doesn’t allow internal fragmentation
Doesn’t allow external fragmentation Allows external fragmentation
Programs are divided into equal-sized pages Programs are divided into unequal-sized segments
that contain logical groupings of code
The absolute address is calculates using the page The absolute address is calculated using the
number and displacement segment number and displacement
Requires Page Map Table (PMT) Requires Segment Map Table (SMT)
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
48
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Virtual Memory (3 of 3)
• Advantages
o Job size: not restricted to size of main memory
o More efficient memory use
o Unlimited amount of multiprogramming possible
o Code and data sharing allowed
o Dynamic linking of program segments facilitated
• Disadvantages
o Higher processor hardware costs
o More overhead: handling paging interrupts
o Increased software complexity: prevent thrashing
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
49
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Cache Memory (1 of 3)
• Small, high-speed intermediate memory unit
• Computer system’s performance increased
o Faster processor access compared to main memory
o Stores frequently used data and instructions
• Cache levels
o L2: connected to CPU; contains copy of bus data
o L1: pair built into CPU; stores instructions and data
• Data/instructions: move between main memory and cache
o Methods similar to paging algorithms
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
50
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Cache Memory (2 of 3)
(figure 3.19)
The traditional path used by early computers was direct: from secondary storage to main
memory to the CPU registers, but speed was slowed by the slow connections (top). With cache
memory directly accessible from the CPU registers (bottom), a much faster response is
possible. © Cengage Learning 2018
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
51
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Cache Memory (3 of 3)
• Four cache memory design factors
o Cache size, block size, block replacement algorithm, and rewrite policy
• Optimal cache and replacement algorithm
o 80 to 90% of all requests in cache possible
• Cache hit ratio
number of requests found in the cache
HitRatio * 100
total number of requests
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
52
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Conclusion (1 of 3)
• Operating system: Memory Manager
o Allocating memory storage: main memory, cache memory, and registers
o Deallocating memory: execution completed
Mchoes/Flynn, Understanding Operating Systems, 8 th Edition. © 2018 Cengage. All Rights Reserved.
53
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Conclusion (2 of 3)
(table 3.7)
The big picture. This is a comparison of the memory allocation schemes discussed in Chapters
2 and 3. © Cengage Learning 2018
Scheme Problem Solved Problem Created Key Software Changes
Single-User Job size limited to physical memory size;
contiguous CPU often idle
Fixed partitions Idle CPU time Internal fragmentation; job size limited to Add Processor Scheduler; add
partition size protection handler
Dynamic partitions Internal External fragmentation Algorithms to manage partitions
fragmentation
Relocatable dynamic External Compaction overhead; Job size limited to Algorithms for compaction
partitions fragmentation physical memory size
Paged Need for Memory needed for tables; Job size Algorithms to manage tables
compaction limited to physical memory size; internal
fragmentation returns
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
54
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
Conclusion (3 of 3)
(table 3.7 continued)
The big picture. This is a comparison of the memory allocation schemes discussed in Chapters
2 and 3. © Cengage Learning 2018
Scheme Problem Solved Problem Created Key Software Changes
Demand paged Job size limited to Large number of tables; possibility of Algorithm to replace pages;
memory size; thrashing; overhead required by page algorithm to search for pages in
inefficient memory use interrupts; paging hardware added secondary storage
Segmented Internal fragmentation Difficulty managing variable-length Dynamic linking package; two-
segments in secondary storage; dimensional addressing scheme
external fragmentation
Segmented/demand Segments not loaded Table handling overhead; memory Three-dimensional addressing
paged on demand needed for page and segment tables scheme
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. © 2018 Cengage. All Rights Reserved.
55
May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.