Transcript Virtual Memory

Computer Studies (AL)
Memory Management
Virtual Memory I
Reference

Silberschatz, Galvin, Gagne, “Operating
System Concepts sixth edition”, 2003,
Wiley
Content




Introduction to Virtual Memory
Demand Page
Effective Access Time
Process Creation
Problem

If we have 1MB ram, how can we run a
program with 2MB?
Execute program partially in
memory may benefit:



No longer be constrained by the amount of
physical memory that is available
Each user program could take less physical
memory, more programs could be run at the
same time, with a corresponding increase
in CPU utilization.
Less I/O would be needed.
Virtual memory

Virtual memory is the separation of user
logical memory from physical memory.
Demand Paging




A demand-paged system is similar to a
paging system with swapping.
Process reside on secondary memory.
When we want to execute a process, we
sway it onto memory
We use lazy swapper, which never swaps a
page into memory unless that page will be
needed.
Demand Paging


Since we are now viewing a process as a
sequence of pages, rather than as one large
contiguous address space, use of swap is
technically incorrect.
A swapper manipulates entire
processes,whereas a pager is concerned
with the individual pages of a process.
Basic Concepts



When a process is to be swapped in, the pager
guesses which pages will be used before the
process is swapped out again.
Pager brings only those necessary pages into
memory
Thus, it avoids reading into memory pages that
will not be used anyway, decreasing the swap
time and the amount of physical memory needed.
Valid-invalid bit scheme

When the above scheme is used, we need to
distinguish:



Those pages are in memory?
Those pages are on the disk?
In the page table, we have set a valid-invalid bit:


Valid: the associated page is both legal and in
memory
Invalid: either the page is not valid, or is valid but is
currently on the disk
When the page is not in memory


Access to a page marked invalid causes a
page-fault trap.
The paging hardware, in translating the
address through the page table, will notice
that the invalid bit is set, causing a trap to
the operating system.
Procedure handling page fault 1


We check an internal table (usually kept
with the process control block) for this
process, to determine whether the reference
was a valid or invalid memory access.
If the reference was invalid, we terminate
the process. If it was valid, but we have not
yet brought in that page, we now page it in.
Procedure handling page fault 2


We find a free frame (by taking one from
the free-frame list, for example)
We schedule a disk operation to read the
desired page into the newly allocated frame
Procedure handling page fault 3


When the disk read is complete, we modify
the internal table kept with the process and
the page table to indicate that page is now
in memory
We restart the instruction that we
interrupted by the illegal address trap. The
process can now access the page as though
it have always been in memory.
Remark

It is important to realize that, because we
save the state (registers, condition code,
instructor counter) of the interrupted
process when the page fault occurs, we can
restart the process in exactly the same place
and state, except that the desired page is
now in memory and is accessible.
Hardware and software support


Hardware: Paging hardware
Software: OS


If the page fault occurs on the instruction
fetch, we can restart by fetching the
instruction again.
If a page fault occurs while we are fetching
an operand, we must fetch and decode the
instruction again, and then fetch the operand.
Example of worse case





Fetch and
decode the
instruction
(ADD)
Fetch A
Fetch B
Add A and B
Store the sum
in C

If we try to store in C (C
is on disk):




Bring it in
Correct page table
Restart instruction
The restart would require
fetching the instruction
again, decoding it, and
fetching the two operands
again, and adding again.
Performance of Demand Paging


Demand paging can have a significant
effect on the performance of a computer
system.
Effective access time (EAT)
= (1-p) * ma + p * page fault time.

Where p is the probability of a page fault
(0<=p<=1)
Example



If we take an average page-fault service
time of 25 milliseconds and a memoryaccess time of 100 nanoseconds:
EAT = (1-p) x (100) + p(25 milliseconds)
= (1-p) x 100 + p x 25,000,000
= 100 + 24,999,900 x p
EAT is directly proportional to the pagefault rate.
Example

If one access out of 1000 causes a page
fault, the EAT is 25 microseconds. The
computer would be slowed down by a
factor of 250 because of demand paging.
Example

If we want less than 10-percent degradation,
we need:


110>100+25,000,000 x p
10 > 25,000,000 x p
p < 0.0000004
That is, keep the slowdown due to paging
to a reasonable level, we can allow only
less than one memory access out of
2,500,000 to the fault.
Note on example


It’s important to keep the page-fault rate
low.
Disk I/O to swap space is generally faster
than that to the file system
Process Creation


Paging and virtual memory can also provide for
benefits during process creation.
Consider:



Demand paging is used when reading a file from disk
into memory and such files may include binary
executables.
However, process creation using the fork() system
call may initially bypass the need for demand paging
by using technique similar to page sharing.
This technique provides for rapid process creation
and minimizes the no. of new pages that must be
allocated to the newly created process.
Remark on fork() system call



It creates a child process as a duplicate of its
parent.
Traditionally fork() worked by creating a copy of
the parent’s address space for the child,
duplicating the pages belonging to the parent.
However, if many child processes invoke the
exec() system call immediately after creation, the
copying of the parent’s address space maybe
unnecessary. (waste?)
Better approach: Copy-on-write




Copy-on-write technique allows the parent and
child processes to initially share the same pages.
If either process writes to a shared page, a copy
of the shared page is created.
The OS will create a copy of this page, mapping
it to the address space of the child process. Thus,
the child process will modify its copied page and
not the page belonging to the parent process.
Only pages that may be modified need be marked
as copy-on-write.
Note on using copy-on-write


When it is determined a page is going to be
duplicated using copy-on-write, it’s
important to note where the free page will
be allocated from.
Many OS provide a pool of free pages for
such request. (zero-fill-on-demand)
Summary

What is virtual memory?



It’s a technique that allows the execution of
processes that may not be completely in
memory.
It’s the separation of user logical memory
from physical memory.
What is demand paging?

When the desired page is not in main memory,
page it in the memory.
Summary

Function of valid-invalid bit



Valid? Invalid?
In memory? On the disk?
Procedure of page-fault trap occurs






Reference
Trap
Page is on backing store
Bring in missing page
Reset page table
Restart instruction
Summary


Effective access time
Benefit from paging: process creation

Copy-on-write technique
Next time

We are going to discuss about Page
Replacement