/ 0
Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems
Summary
- Performance of Demand Paging
- Process Creation
- Memory Mapped Files
Performance of Demand Paging with Page Replacement
When there is no free frame available, page replacement is required, and we must select the pages to be replaced. This can be done via several replacement algorithms, and the major criterion in the selection of a particular algorithm is that we want to minimize the number of page faults. The victim page that is selected depends on the algorithm used, it might be the least recently used page, or the most frequently used etc depending on the algorithm.
Another Example
- Effective memory access is 100 ns
- Page fault overhead is 100 microseconds = 105 ns
- Page swap time is10 milliseconds = 107 ns
- 50% of the time the page to be replaced is “dirty”
- Restart overhead is 20 microseconds = 2 x 104 ns
Effective access time = 100 * (1-p) + (105 + 2 * 104 + 0.5 * 107 + 0.5 * 2 * 107) * p
= 100 * (1-p) + 15,120,000 * p
What is a Good Page Fault Rate?
For the previous example suppose p is 1%, then EAT is
= 100 * (1-p) + 15,120,000 * p
= 151299 ns
Thus a slowdown of 151299 / 100 = 1513 occurs.
For the luxury of virtual memory to cost only 20% overhead, we need
120 > 100 * (1-p) + 15,120,000 * p
120 > 100 -100 p + 15,120,000 p
p < 0.00000132
⇒ Less than one page fault for every 755995 memory accesses!
Process Creation and Virtual Memory
Paging and virtual memory provide other benefits during process creation, such as copy on write and memory mapped files.
Copy on Write fork()
Demand paging is used when reading a file from disk into memory and such files may
include binary executables. However, process creation using fork() may bypass initially
the need for demand paging by using a technique similar to page sharing. This technique
provides for rapid process creation and minimizes the number of new pages that must be
allocated to newly created processes.
Recall the fork() system call 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, considering that many child
processes invoke the exec() system call immediately after creation, the copying of the
parent’s address space may be unnecessary. Alternatively we can use a technique known
as copy on write. This works by allowing the parent and child processes to initially share
the same pages. These shared pages are marked as copy-on-write pages, meaning that if
either process writes to a shared page, a copy of the shared page is created. For example
assume a child process attempts to modify a page containing portions of the stack; the
operating system recognizes this as a copy-on-write page. The operating system will then
create a copy of this page mapping it to the address space of the child process. Therefore
the child page will modify its copied page, and not the page belonging to the parent
process. Using the copy-on-write technique it is obvious that only the pages that are
modified by either process are copied; all non modified pages may be shared by the
parent and the child processes. Note that only pages that may be modified are marked as
copy-on-write. Pages that cannot be modified (i.e. pages containing executable code) may
be shared by the parent and the child. Copy-on-write is a common technique used by
several operating systems such as Linux, Solaris 2 and Windows 2000.
When it is determined a page is gong to be duplicated using copy-on-write it is
important to note where the free page will be allocated from. Many operating systems
provide a pool of free pages for such requests. These free pages are typically allocated
when the stack or heap for a process must expand or for managing copy-on-write pages.
Operating systems typically allocate these pages using a technique known as zero-fill-ondemand.
Zero-fill-on-demand pages have been zeroed out before allocating, thus deleting
the previous contents on the page. With copy-on-write the page being copied will be
copied to a zero-filled page. Pages allocated for the stack or heap are similarly assigned
zero-filled pages.
vfork()
Several versions of UNIX provide a variation of the fork() system call—vfork() (for virtual memory fork). vfork() operates differently than fork() with copy on write. With vfork() the parent process is suspended and the child process uses the address space of the parent. Because vfork() does not use copy-on-write, if the child process changes any pages of the parent’s address space, the altered pages will be visible to the parent once it resumes. Therefore, vfork() must be used with caution, ensuring that the child process does not modify the address space of the parent. vfork() is intended to be used when the child process calls exec() immediately after creation. Because no copying of pages takes place, vfork() is an extremely efficient method of process creation and is sometimes used to implement UNIX command-line shell interfaces.
Linux Implementation
In Linux, shared pages are marked read-only after fork(). If either process tries to modify a shared page, a page fault occurs and the page is copied. The other process (who later faults on write) discovers it is the only owner; so no copying takes place. In other words, Linux implementation of fork() is based on the “copy-on-write” semantics.
Memory Mapped files
Consider a sequential read of a file on disk using the standard system calls open(), read(),
write(). Every time the file is accessed requires a system call and disk access.
Alternatively we can use the virtual memory techniques discussed so far to treat file I/O
as routine memory accesses. This approach is known as memory mapping a file, allowing
a part of the virtual address space to be logically associated with a file. Memory mapping
a file is possible by mapping a disk block to a page (or pages) in memory. Initial access
to the file proceeds using ordinary demand paging resulting in a page fault. However, a
page sized portion of the file is read from the file system into a physical page. Subsequent
reads and writes to the file are handled as routine memory accesses, thereby simplifying
file access and usage by allowing file manipulation through memory rather than the
overhead of using the read() and write() system calls. Note that writes to the file mapped
in memory may not be immediate writes to the file on disk. Some systems may choose to
update the physical file when the operating system periodically checks if the page in
memory mapping the file has been modified. Closing the file results in all the memory
mapped data being written back to disk and removed from the virtual memory of the
process. The concept of memory mapped files is shown pictorially in the following
diagram.
Memory-Mapped Files in Solaris 2
Some operating systems provide memory mapping only through a specific system call
and treat all other file I/O using the standard system calls. However, some systems
choose to memory map a file regardless of whether a file was specified as a memory map
or not. For example: Solaris 2 treats all file I/O as memory mapped, allowing file access
to take place in memory, whether a file has been specified as memory mapped using
mmap() system call or not.
Multiple processes may be allowed to map the same file into the virtual memory of
each to allow sharing of data. Writes by any of the processes modify the data in virtual
memory and can be seen by all others that map the same section of the file. Given our
knowledge of virtual memory it should be clear how the sharing of memory mapped
sections of memory is implemented. The virtual memory map of each sharing process
points to the same page of physical memory – the page that holds a copy of the disk
block. This memory mapping is illustrated as:
The memory mapping system calls can only support copy-on-write functionality
allowing processes to share a file in read-only mode, but to have their own copies of any
data they modify. So that access to the shared data is coordinated, the processes involved
might use one of the mechanisms for achieving mutual exclusion.
mmap() System Call
In a UNIX system, mmap() system call can be used to request the operating system to memory map an opened file. The following code snippets show “normal” way of doing file I/O and file I/O with memory mapped files.
“Normal” File I/O
fildes = open(...);
lseek(...);
read(fildes, buf, len);
/* use data in buf */
File I/O with mmap()
fildes = open(...)
address = mmap((caddr_t) 0, len,(PROT_READ | PROT_WRITE), MAP_PRIVATE, fildes, offset);
/* use data at address */
Google +