Virtual memory Flashcards
What do most virtual memory systems use?
paging
what is the basic idea of virtual memory?
combined size of a program likely to exceed memory available for it.
So, chop it up and have parts in use in memory, and the other parts on disk.
What is another term for a programmed address?
virtual address
Virtual addresses form [x]
virtual address space
On computer without virtual memory, [x]
virtual address is put directly onto memory bus and physical word is read or written
When virtual memory memory is used [x]
virtual addresses go to an MMU
The MMU [x]
maps virtual addresses onto physical addresses
The virtual address space is [x] into units called [y]
x = divided y = pagees
The corresponding unit in actual memory from a page is called the
page frame
What is important about size of pages to page frames?
They are exactly the same
When a program tries to access address 0, what happens?
Virtual address - sent to MMU
MMU sees that virtual address falls on a page number
That page number maps to page frame 2 which has a physical address [y]
It outputs physical address [y] onto the bus
What keeps track of which pages are physically present in memory?
Present/absent bit
What happens if a page is not mapped?
MMU notices and causes the CPU to trap.
What is a CPU trap called in the instance of not finding a page mapping?
page fault
What happens after a page fault?
1) Operating system picks a page, writes its contents to disk.
2) It then fetches the references page and writes it to the page frame just wiped.
3) It changes the mapping
4) It restarts
What is the purpose of the page table?
map virtual pages onto page frames.
How many page tables are created?
As many page tables as there are processes.
Why does each process need its own page table?
Because each process has its own virtual address space
What is the most important field in a page table?
Page frame number
What fields are in a page table?
Page frame number Present/absent bit Protection bit Modified bit Referenced bit Caching disabled bit
What does protection bit describe?
The permissions associated with the page
What does the modified bit describe?
If a page has been used and modified.
If a page has been modified, what must happen if it is being replaced?
It must be written back to disk.
What does the referenced bit do?
It helps the operating system understand if the page is being used or not.
Why is the disk address not part of the page table.
Simple. The page table is about mapping virtual to physical.
Where is information about faults kept?
In the operating system.
What is a TLB?
Translation lookaside buffer
What is a TLB
A fast cache-like item usually in the MMU.
Where does the TLB come from?
The understanding that most programs tend to make a large number of references to a small number of pages
What does the TLB allow?
The mapping of virtual addresses to physical address without going through the page table
What is included in a TLB entry?
Information about one page:
1) virtual page number
2) a modified bit
3) protection code
4) the physical page frame in which the page is located
5) referenced bit
What kind of correspondence exists between the TLB and the page table?
One to one.
What happens when virtual address is presented to the MMU
1) IT checks the TLB.
2) If in TLB, it just loads page straight from there without going to page table.
What happens if a virtual page number is not in a TLB?
The MMU sees the TLB miss, does a page table lookup.
It then evicts an item from the TLB and loads that page in.
If TLB and page table miss, it has to load it into page table and also into TLB.
What are the common algorithms for replacing pages?
Not recently used First in first out Second chance Clock page Least recently used Working set page WSClock
Basics for not recently used?
on page fault, operating system checks 4 fields based on reference and modication
not referenced, not modified
not referenced, modified
referenced, not modified
referenced, modified
when a process is started, both r and m bits set to 0. Periodically (clock interrupt), r bit is cleared. M bit changes if it has been referenced.
Basics for first in first out
it’s a queue.
at the head (the oldest) item is removed.
Basics for Second Chance Page Replacement algo
Modifies FIFO
Rather than throwing out a heavily used old page, the referenced bit is checked.
If r = 0, it is old and unused = remove.
If r = 1, r is reset and it is put to the end of the queue and treated like a new page.
Basics for clock page replacement algo?
Like second chance, but keeps things on a circular list with a pointer (like a hand).
When page fault occurs, the page being pointed at is inspected.
If page = 0, page is evicted.
If page = 1, the R bit is cleared and hand moves.
Process continues until a 0 is found to be able to do a replacement.
Basics for least recently used algo
Idea stems from notion that something that’s in use or has been used recently will likely be used again.
What is a problem with least recently used algo?
It’s expensive.
Must keep a linked list of all pages. Most recently used page must be kept at front of list.
List constantly updating.
The set of pages that a process is currently using is called its [x]
working set
Working set is defined as
The set of pages that a process is currently using
Thrashing is defined as
a program causing page faults every few instructions
Define demand paging
When pages are loaded on demand, not in advance.
What is the working set model?
An attempt to keep track of working set to greatly reduce page fault rate
Define prepaging
Loading pages before the process is allowed to run.
Why does it matter that the working set changes slowly?
Because you can make a reasonable guess at which pages need loading in when a program restarts.
what do you need to be able to do to implement a working set model?
You need to be able to keep track of the pages that are being used.
Where does working set page replacement algorithm come in then?
When a page fault occurs, find a page not in the working set of the particular program that’s being worked on and evict it.
Algorithm for working set page replacement basics:
Reference and modified bits are in as standard, as is a clock which clears reference bit every interrupt.
On page fault, everything checked. If R = 1, current virtual time is written into TIME OF LAST USE field = page was in use since last page fault. This means it is part of working set.
If R = 0 and TIME OF LAST USE is greater than the current virtual time, then you can evict
If R = 0 and TIME OF LAST USE is less than current virtual time, it will be temporarily spared.
Define current virtual time
The amount of CPU time a process has actually used since it started
