project 3 Class Discussion Topics prepare 2 slide powerpoint for each question with diagram too Discuss the pros and cons of the memory management s -

project 3
Class Discussion Topics
prepare 2 slide powerpoint for each question with diagram too

Discuss the pros and cons of the memory management schemes presented in this chapter. If given an option, which scheme would you implement and why?
Discuss the difference between associative memory and cache memory and the steps involved in using these types of memory.

Don't use plagiarized sources. Get Your Custom Assignment on

project 3 Class Discussion Topics prepare 2 slide powerpoint for each question with diagram too Discuss the pros and cons of the memory management s

From as Little as $13/Page

Projects
write 2 page paper for each question

Choose an operating system and submit a report on approaches to manage its virtual memory.
Working in teams of four, write pseudocode for the first-in-first-out (FIFO) and least-recently-used (LRU) page replacement policies.

Chapter 3
Memory Management Includes Virtual Memory
Mchoes/Flynn, Understanding Operating Systems, 8th Edition. 2018 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.
1

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
2

Mchoes/Flynn, Understanding Operating Systems, 8th Edition. 2018 Cengage. All Rights Reserved. May not be scanned, copied or duplicated, or posted to a publicly accessible website, in whole or in part.

Introduction
Evolution of virtual memory
Paged, demand paging, segmented, segmented/demand paging
Foundation of current virtual memory methods
Areas of improvement from the need for:
Continuous program storage
Placement of entire program in memory during execution
Enhanced Memory Manager performance: cache memory
3

Paged Memory Allocation (1 of 11)
Incoming job: divided into pages of equal size
Best condition
Pages, sectors, and page frames: same size
Exact sizes: determined by disks sector size
Memory manager tasks: prior to program execution
Determine number of pages in program
Locate enough empty page frames in main memory
Load all program pages into page frames
4

Paged Memory Allocation (2 of 11)
Program: stored in noncontiguous page frames
Advantages: more efficient memory use; compaction scheme eliminated (no external fragmentation)
New problem: keeping track of jobs pages (increased operating system overhead)
5

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

Paged Memory Allocation (4 of 11)
Internal fragmentation: jobs 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)
Stored in main memory: operating system area
Job Table: information for each active job
Job size
Memory location: jobs PMT
7

Paged Memory Allocation (5 of 11)
Page Map Table: information for each page
Page number: beginning with Page 0
Memory address
Memory Map Table: entry for each page frame
Location
Free/busy status
8

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
Job Table

Job Size PMT Location

400 3096

200 3100

500 3150

(a)
Job Table

Job Size PMT Location

400 3096

500 3150

(b)
Job Table

Job Size PMT Location

400 3096

700 3100

500 3150

Paged Memory Allocation (7 of 11)
Line displacement (offset)
Line distance: from beginning of its page
Line location: within its page frame
Relative value
Determining page number and displacement of a line
Divide job space address by the page size
Page number: integer quotient
Displacement: remainder
10

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

Paged Memory Allocation (9 of 11)
Instruction: determining exact location in memory
Step1: Determine page number/displacement of line
Step 2: Refer to the jobs PMT
Determine page frame containing required page
Step 3: Obtain beginning address of page frame
Multiply page frame number by page frame size
Step 4: Add the displacement (calculated in first step) to starting address of the page frame
Address resolution (address translation)
Job space address (logical) physical address (absolute)
12

Paged Memory Allocation (10 of 11)
(figure 3.3)
The sizes of this systems 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

Paged Memory Allocation (11 of 11)
Advantages
Efficient memory use: job allocation in noncontiguous memory
Disadvantages
Increased overhead: address resolution
Internal fragmentation: last page
Page size: crucial
Too small: very long PMTs
Too large: excessive internal fragmentation
14

Demand Paging Memory Allocation (1 of 8)
Loads only a part of the program into memory
Removes restriction: entire program in memory
Requires high-speed page access
Exploits programming techniques
Modules: written sequentially
All pages: not needed simultaneously
Examples
Error-handling modules instructions
Mutually exclusive modules
Certain program options: mutually exclusive or not always accessible
15

Demand Paging Memory Allocation (2 of 8)
Virtual memory
Appearance of vast amounts of physical memory
Less main memory required than paged memory allocation scheme
Requires high-speed direct access storage device (D A S D s): e.g., hard drives or flash memory
Swapping: how and when pages passed between memory and secondary storage
Depends on predefined policies
16

Demand Paging Memory Allocation (3 of 8)
Algorithm implementation: tables, e.g., Job Table, Page Map Table, and Memory Map Table
Page Map Table
First field: page requested already in memory?
Second field: page contents modified?
Third field: page referenced recently?
Fourth field: frame number
17

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

Demand Paging Memory Allocation (5 of 8)
Swapping process
Resident memory page: exchanged with secondary storage page
Resident page: copied to disk (if modified)
New page: written into available page frame
Requires close interaction between:
Hardware components
Software algorithms
Policy schemes
19

Demand Paging Memory Allocation (6 of 8)
Hardware components:
Generate the address: required page
Find the page number
Determine page status: already in memory
Page fault: failure to find page in memory
Page fault handler: part of operating system
Determines if empty page frames in memory
Yes: requested page copied from secondary storage
No: swapping (dependent on the predefined policy)
20

Demand Paging Memory Allocation (7 of 8)
Tables updated when page swap occurs
PMT for both jobs (page swapped out; page swapped in) and the MMT
Thrashing
Excessive page swapping: inefficient operation
Main memory pages: removed frequently; called back soon thereafter
Occurs across jobs
Large number of jobs: limited free pages
Occurs within a job
Loops crossing page boundaries
21

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

Page Replacement Policies and Concepts
Page replacement policy
Crucial to system efficiency
Two well-known algorithms
First-in first-out (F I F O) policy
Best page to remove: page in memory longest
Least Recently Used (L R U) policy
Best page to remove: page least recently accessed
23

First-In First-Out (1 of 3)
Removes page: longest in memory
Failure rate
Ratio of page interrupts to page requests
More memory: does not guarantee better performance
24

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

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 isnt 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

Least Recently Used (1 of 3)
Removes page: least recent activity
Theory of locality
Efficiency
Additional main memory: causes either decrease in or same number of interrupts
Does not experience F I F O Anomaly (Belady Anomaly)
27

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

Least Recently Used (3 of 3)
Clock replacement variation
Circular queue: pointer steps through active pages reference bits; simulates a clockwise motion
Pace: computers clock cycle
Bit-shifting variation
8-bit reference byte and bit-shifting technique: tracks pages usage (currently in memory)
29

The Mechanics of Paging (1 of 4)
Page swapping
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

The Mechanics of Paging (2 of 4)
Page Map Table: bit meaning
Status bit: page currently in memory
Referenced bit: page referenced recently
Determines page to swap: LRU algorithm
Modified bit: page contents altered
Determines if page must be rewritten to secondary storage when swapped out
Bits checked when swapping
F I F O: modified and status bits
L R U: all bits (status, modified, and reference bits)
31

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
Status Bit

Value Meaning

0 not in memory

1 resides in memory

Modified Bit

Value Meaning

0 not modified

1 was modified

Referenced Bit

Value Meaning

0 not called

1 was called

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

Modified? Referenced? What it Means

Case 1 0 0 Not modified AND not referenced

Case 2 0 1 Not modified BUT was referenced

Case 3 1 0 Was modified BUT not referenced (Impossible?)

Case 4 1 1 Was modified AND was referenced

The Importance of the Working Set (1 of 2)
Set of pages residing in memory: accessed directly without incurring a page fault
Demand paging schemes: improves performance
Requires locality of reference concept
Structured programs: only small fraction of pages needed during any execution phase
System needs definitive values:
Number of pages comprising working set
Maximum number of pages allowed for a working set
Time-sharing and network systems
Must track every working sets size and identity
34

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

Segmented Memory Allocation (1 of 6)
Each job divided into several segments: different sizes
One segment for each module: related functions
Reduces page faults
Loops: not split over two or more pages
Main memory: allocated dynamically
Programs structural modules: determine segments
Each segment numbered when program compiled/assembled
Segment Map Table (SMT) generated
36

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

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

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

Segmented Memory Allocation (5 of 6)
Memory Manager: tracks segments in memory
Job Table: one for the whole system
Every job in process
Segment Map Table: one for each job
Details about each segment
Memory Map Table: one for the whole system
Main memory allocation
Instructions within each segment: ordered sequentially
Segments: not necessarily stored contiguously
40

Segmented Memory Allocation (6 of 6)
Two-dimensional addressing scheme
Segment number and displacement
Disadvantage
External fragmentation
Major difference between paging and segmentation
Pages: physical units; invisible to the program
Segments: logical units; visible to the program; variable sizes
41

Segmented/Demand Paged Memory Allocation (1 of 5)
Subdivides segments: equal-sized pages
Smaller than most segments
More easily manipulated than whole segments
Segmentations logical benefits
Pagings physical benefits
Segmentation problems removed
Compaction, external fragmentation, secondary storage handling
Three-dimensional addressing scheme
Segment number, page number (within segment), and displacement (within page)
42

Segmented/Demand Paged Memory Allocation (2 of 5)
Scheme requires four tables
Job Table: one for the whole system
Every job in process
Segment Map Table: one for each job
Details about each segment
Page Map Table: one for each segment
Details about every page
Memory Map Table: one for the whole system
Monitors main memory allocation: page frames
43

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

Segmented/Demand Paged Memory Allocation (4 of 5)
Disadvantages
Overhead: managing the tables
Time required: referencing tables
Associative memory
Several registers allocated to each job
Segment and page numbers: associated with main memory
Page request: initiates two simultaneous searches
Associative registers
SMT and PMT
45

Segmented/Demand Paged Memory Allocation (5 of 5)
Associative memory
Primary advantage (large associative memory)
Increased speed
Disadvantage
High cost of complex hardware
46

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:
Memory Manager: tracks each page or segment
Processor hardware: issues the interrupt and resolves the virtual address
47

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 Doesnt allow internal fragmentation

Doesnt 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 number and displacement The absolute address is calculated using the segment number and displacement

Requires Page Map Table (PMT) Requires Segment Map Table (SMT)

Virtual Memory (3 of 3)
Advantages
Job size: not restricted to size of main memory
More efficient memory use
Unlimited amount of multiprogramming possible
Code and data sharing allowed
Dynamic linking of program segments facilitated
Disadvantages
Higher processor hardware costs
More overhead: handling paging interrupts
Increased software complexity: prevent thrashing
49

Cache Memory (1 of 3)
Small, high-speed intermediate memory unit
Computer systems performance increased
Faster processor access compared to main memory
Stores frequently used data and instructions
Cache levels
L2: connected to C P U; contains copy of bus data
L1: pair built into C P U; stores instructions and data
Data/instructions: move between main memory and cache
Methods similar to paging algorithms
50

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 C P U registers, but speed was slowed by the slow connections (top). With cache memory directly accessible from the C P U registers (bottom), a much faster response is possible. Cengage Learning 2018

Cache Memory (3 of 3)
Four cache memory design factors
Cache size, block size, block replacement algorithm, and rewrite policy
Optimal cache and replacement algorithm
80 to 90% of all requests in cache possible
Cache hit ratio

Average memory access time
Avg_Mem_AccTime
= Avg_Cache_AccessTime + (1 HitRatio) * Avg_MainMem_AccTime
52

Conclusion (1 of 3)
Operating system: Memory Manager
Allocating memory storage: main memory, cache memory, and registers
Deallocating memory: execution completed
53

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 contiguous Job size limited to physical memory size; C P U often idle

Fixed partitions Idle C P U time Internal fragmentation; job size limited to partition size Add Processor Scheduler; add protection handler

Dynamic partitions Internal fragmentation External fragmentation Algorithms to manage partitions

Relocatable dynamic partitions External fragmentation Compaction overhead; Job size limited to physical memory size Algorithms for compaction

Paged Need for compaction Memory needed for tables; Job size limited to physical memory size; internal fragmentation returns Algorithms to manage tables

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 memory size; inefficient memory use Large number of tables; possibility of thrashing; overhead required by page interrupts; paging hardware added Algorithm to replace pages; algorithm to search for pages in secondary storage

Segmented Internal fragmentation Difficulty managing variable-length segments in secondary storage; external fragmentation Dynamic linking package; two-dimensional addressing scheme

Segmented/demand paged Segments not loaded on demand Table handling overhead; memory needed for page and segment tables Three-dimensional addressing scheme

*100numberofrequestsfoundinthecacheHitRatiototalnumberofrequests

Related Questions:

Related questions

Leave a Comment Cancel Reply