Transcript Memory Management

Memory Management
◦ Operating Systems
◦ CS550
Paging and Segmentation
 Non-contiguous memory allocation
 Fragmentation is a serious problem with contiguous allocation
 Non-contiguous allocation removes this problem
 Modern memory systems use more advanced allocation schemes
- Paging
- Segmentation
Paging
o Process address space divided into pages which have a 1to-1 correspondence with frames
o Frames are fixed size blocks of physical memory
o Page size is a power of two e.g. 1024bytes or 1K
o No external fragmentation
o Internal fragmentation occurs on the last page of a process
o Remember, memory for a process includes program and
data
o Not stored contiguously
Logical addresses
o
o
o
o
o
o
o
o
Logical address of a process consists of a page number and a process
Physical address is determined by the frame number and the offset
Use the page table to keep track of which frame corresponds to which page
Could be an array or linked list
One table entry per page (per frame)
Most sig. bits - page number
Least sig. bits – offset
For real page table w/20 bit addressing, have 1024 pages with 1024bytes each
• first 10 bits - address
• next 10 – offset
o 0000000010 -- page 2
o 0111011110 -- offset 478 bytes
Logical addresses (Contd..)
• Page number provides an index into the page table
• Offset provides value into memory
+-------------+----------+
| page # | offset |
+-------------+----------+
• This figure will also be drawn in class.
• The OS must do the translation
Segmentation
o Segments are variable length modules of a program corresponding to logical
units (addresses)
o Represent modular structure of program
o Examples include:
o Main method
o Other methods
o Data
o All need to be loaded into memory
o Prefer to load segments into contiguous blocks of memory
Differences: Paging and Segments
 Segments not all of the same size
 Segments could be large compared to size of page
 Number of segments in a process is small
 Operating system often keeps a segment table
 It keeps track of all segments for a process including starting address
and length
 Need to use segment table to get to physical address via page table
Virtual Memory
o Memory space of process divided into blocks of pages or segments
o Don't need all blocks to execute a process though
o Virtual address space of a process is the entire set of all addresses in a
program
o Keep absolute form of program on disk
o Physical address space is much smaller
o Virtual memory manager swaps out pages/segments of an executing process
as needed
o Operating system must provide a way to translate between virtual and
physical addresses
o Virtual address space is much larger than physical address space
o Need efficient way to load blocks as program executes
o Swap space or page file
Process locality
o Often only reference subset of memory references while program executes reference
locality
o Process executes in steps and usually only some memory is needed during those steps
o Sets of pages a process operates on are called a locality
Segmentation
o Often only a few segments are needed at once.
o Segments may be of variable size
o Only need to load a few segments into memory
o When need another segment go to page file/swap space and get data (called a page
fault)
o Transfer replaced segment back to memory
o No control from user on how to divide segments
Address Translation
 Check for valid page number
 Check for valid physical address
 OS must trigger an interrupt to access memory/disk if page is not in
memory
 OS must write data (pages) back to disk if there are modifications to
physical memory within the program (must keep page file up to date)
uses a bit to indicate this
 Managing page table can be costly may need to only load part of it
into memory
 Important to consider page size (too big/too small)
Paging with virtual memory
o May allocate few pages to a process of large size
o When process references page not in memory page fault occurs
o Costs time to handle a page fault (OS overhead)
Paging Policies
oWhen to swap a page - fetch policy
o Replacement policy - select page to replace if no empty frames
o Placement policy - where to place page (which frame) in memory
o Number of frames to allocate to a process
Fetch Policy
• Demand paging - page not loaded until referenced in memory by
program
• Prepaging - load page before it is referenced by program
• With demand paging faults occur when
• need instruction
• need operand of an instruction
• With prepaging
• need to be careful about which pages to load esp. if not using them soon
Replacement Policy
• Carry out these steps when page fault occurs
• Process generating fault is suspended
• OS locates referenced page on HDD using page tables
• If no free frame select page to replace and transfer this page back to
HDD
• Load referenced page into selected frame and update page/frame
tables
• Resume interrupted process
• Need replacement policy
• Need to examine modified bit to determine if we need to store a
page in memory
Frame Allocation
• Need to be careful about how many pages to allocate to a
process
• Too few frames = lots of page faults
• Causes thrashing - worse than deadlock because processes don't make
progress
• Use equal or proportional allocation (proportional to size)
• With replacement, use local and global allocation
• local - select only from own set of frames
• global - select from other process frames or empty ones
Page Faults & Performance
• Time to service page fault important (overhead)
•
•
•
•
•
Time interval to service page fault interrupt
Time to swap out (store) replaced page to HDD
Time to swap in (load) referenced page from HDD
Delay in queuing for HDD
Delay in scheduling process with referenced page
• Disk I/O time is most significant page fault rate its
number of
• Page faults per unit of execution time
• Unit of execution time defined as
• time without page faults + number of faults * fault service time
Paging Algorithm
• Implement replacement policy
• Static frame allocation policies
• Dynamic frame allocation policies
• Based on how frames allocated to a process
• Assume process has a reference stream of pages and ref stream
represents process actions
• <3, 6, 1, 3, 3, 2, 7, 8, 9, 10, 11, ...>
• We have 3 static policies
• FIFO
• Optimal replacement
• LRU
Paging Algorithm (Contd..)
• In class we will look at a FIFO example with 3 page segment ...
• This may exhibit poor performance even if number of frames
increased
• Optimal algorithm needs entire page reference stream in
advance
• Replace page in memory that will not be used for the longest
period
• LRU replace page in memory that has not been used for the
longest period
[1, 2]