Virtual Memory#

Virtual memory is the operating-system layer that gives each process its own address space. It lets the kernel separate process memory from physical memory and decide which pages should be resident, shared, protected, or backed by storage.

What is Virtual Memory?#

Virtual memory gives a process a private view of memory that does not directly match the machine’s physical memory.

This supports several operating-system goals:

Programs can run even when their total virtual memory use is larger than available physical memory.
File I/O can be buffered and cached in memory.
Processes can share pages, such as executable code or shared library text.
The kernel can enforce memory protection between processes.
Virtual addresses can be translated to physical addresses by hardware and kernel-managed tables.

Memory Management Units#

The memory management unit, or MMU, is the hardware that translates virtual addresses into physical addresses.

The MMU also enforces memory protection and works with structures such as page tables and the translation lookaside buffer. In modern systems, the MMU is usually part of the CPU. When a process accesses memory, the CPU and MMU use the current process’s page tables to decide where the access goes and whether it is allowed.

Pages and Page Tables#

A page is a fixed-size block of virtual memory. A page table records how virtual pages map to physical pages.

Every process appears to have access to a large address space, but only some of that address space is actually mapped and resident at any given time. The operating system maintains page tables so the MMU can translate virtual addresses and enforce permissions.

Page Table Size#

Page size affects page-table overhead.

If a 32-bit system used 128-byte pages, it would need more than 33 million page entries to describe a 4 GB address space. Even with very compact entries, that overhead would be too large for each process.

With 4 KB pages, a 4 GB address space has 1,048,576 virtual pages. On 32-bit x86, each page-table entry is 32 bits, so a flat page table would still require about 4 MB per process. That is too much overhead for a small process.

Page Table Entries#

A page-table entry stores the physical page number and attributes for a virtual page.

For a 4 KB page in a 32-bit address space, 20 bits identify the page and 12 bits remain for flags and other information. Common attributes include whether the page is present, writable, executable, and modified.

Multi-Level Page Tables#

Multi-level page tables reduce memory overhead by allocating lower-level tables only for address ranges that are actually used.

In a two-level page table, part of the virtual address selects a first level entry, and another part selects a second level entry. The first level covers large regions. The second level is created only when a process actually uses pages in that region.

Two-Level Page Table#

The two-level page-table diagram shows how a virtual address can be split into indexes and an offset.

MMU Address Translation Algorithm#

Address translation first checks the TLB. If the translation is not cached, the MMU and kernel page-table structures are used to find the physical page.

physical_address translate(virtual_address v_addr) {
   physical_address addr;
   if(tlb.contains(v_addr)) {
      addr = tlb[v_addr];
   } else {
      first10 = (v_addr >> 0x16) & 0xa;
      second10 = (v_addr >> 0xc) & 0xa;
      level_1 = page_table_1[first10];
      entry = level_1[second10];
      physical_page = (v_addr >> 0xc) & 0x14;
      if(physical_page >> RESIDENT_OFFSET & 0x01 == 0) {
         generate page fault;
      }
      addr = (physical_page << 0xc) & (v_addr & 0xc);
      tlb[v_addr] = addr;
   }
   return addr;
}

Key points:

The TLB caches recent virtual-to-physical translations.
A TLB miss requires a page-table lookup.
Page-table entries contain both page addresses and permission or status bits.
A nonresident page causes a page fault.
Once translation succeeds, the result can be cached in the TLB.

Page Faults#

A page fault is an exception raised when a memory reference cannot be completed using the current page-table entry.

Common causes include accessing a page that is not resident in physical memory, writing to a read-only page, or executing from a non-executable page. The operating system decides whether the fault can be repaired or whether the process must be notified or terminated.

Page Faults in UNIX#

UNIX systems usually handle nonresident pages by loading the page and retrying the instruction.

If the page cannot be loaded because memory is exhausted, the process may fail or the system may take stronger action. If the access violates permissions, the kernel normally sends SIGSEGV to the process.

Page Faults in Windows#

Windows also handles nonresident pages by loading the page and retrying the instruction when possible.

If the fault cannot be repaired, Windows raises an exception in the faulting process. Permission faults are also reported through the exception mechanism.

Page Replacement and Swapping#

Page replacement is the policy for choosing which physical page to reuse when memory is needed.

The swapper moves pages between physical memory and slower backing storage. It handles heap and stack pages, and it may also demand-page program text so execution can begin before the full program is loaded.

When the Swapper Runs#

The swapper runs when a needed virtual page is not resident or when the system needs more free physical pages.

The operating system may also reclaim memory when a page would be more useful for another process, the filesystem cache, or another kernel purpose. The swapper is therefore part of both memory protection and overall system performance.

Physical Page Contenders#

Many uses compete for physical pages.

Important contenders include the filesystem cache, shared memory regions, memory mapped files, executable and library text, process stacks, process heaps, and device DMA buffers. Some DMA regions must not be swapped because a device is using the physical address directly.

Swapper Algorithms#

A page replacement algorithm tries to minimize expensive page faults.

Useful measures include the total number of page faults, the page faults an optimal algorithm would have produced, and the working set of pages a process is actively using. No real algorithm can predict the future, so replacement policies approximate likely future behavior from recent history.

Page Classification#

Many processors record whether a page has been referenced or modified.

These bits divide pages into four classes:

Not referenced and not modified.
Not referenced and modified.
Referenced and not modified.
Referenced and modified.

The operating system can clear reference bits periodically to estimate which pages have been used recently.

Not Recently Used#

Not Recently Used, or NRU, evicts pages from the lowest available page class.

NRU is simple. It prefers pages that have not been referenced and have not been modified. It is inexpensive, but it is only a rough estimate of future page use.

FIFO Replacement#

First In First Out, or FIFO, evicts the oldest resident page.

FIFO assumes the oldest page is least likely to be used again. That assumption is often wrong, so FIFO is rarely used directly in production systems.

Second-Chance FIFO#

Second-chance FIFO improves FIFO by checking the reference bit before evicting a page.

If the oldest page has not been referenced, it can be evicted. If it has been referenced, the algorithm clears the reference bit and gives the page another chance. This avoids evicting heavily used pages simply because they are old.

Clock Replacement#

The clock algorithm is an efficient implementation of second-chance replacement.

It stores pages in a circular list and keeps a pointer to the next candidate. If the pointed-to page has a clear reference bit, it is evicted. If the bit is set, the algorithm clears it and advances the pointer.

Least Recently Used#

Least Recently Used, or LRU, evicts the page that has not been used for the longest time.

LRU is often close to optimal because programs tend to reuse pages they used recently. A perfect LRU implementation is expensive because the kernel would need to update ordering information on every memory access.

Not Frequently Used#

Not Frequently Used, or NFU, approximates LRU with counters.

At each clock interrupt, the operating system scans pages and increments a counter for each page whose reference bit is set. On a page fault, a page with a low counter is a candidate for eviction.

NFU is not forgetful enough. A page that was used heavily in the past can keep a high counter long after it stops being useful.

Aging#

Aging improves NFU by making old references matter less over time.

At each clock interrupt, the operating system shifts each counter right. If the page was referenced, it sets the most significant bit. The result is a small history of recent use. Aging still has limited precision, but it tracks recency better than plain NFU.

Belady’s Anomaly#

Belady’s anomaly is the surprising result that adding more physical pages can increase page faults for some replacement algorithms and access patterns.

For example, FIFO with the reference string 3 2 1 0 3 2 4 3 2 1 0 4 can produce 9 page faults with 3 physical pages and 10 page faults with 4 physical pages. More memory does not always help FIFO.

Belady’s Anomaly Diagram#

The diagram shows a reference string where FIFO performs worse with more physical pages.

Modeling Page Replacement#

Page replacement algorithms can be modeled with a reference string and a fixed number of physical pages.

The reference string is the ordered list of page accesses. The model tracks which pages are in physical memory and which pages have been referenced but are not resident. On each reference, the algorithm either finds the page in memory or handles a page fault.

Modeling LRU#

LRU has the stack property: with more physical pages, the set of pages in memory is always a superset of the set that would be present with fewer physical pages.

This property means LRU is not subject to Belady’s anomaly. Adding more physical pages cannot make LRU perform worse for the same reference string.

Distance Strings#

A distance string records how far a referenced page is from the top of the algorithm’s conceptual stack.

Pages not yet referenced have infinite distance. The distance string can estimate page faults for different physical memory sizes by counting how often the distance exceeds the number of available frames.

Fm = Sum(k = m+1, n, Ck) + Cinf

Here, Ck is the number of times distance k occurs, Cinf is the number of infinite distances, m is the number of physical pages, and n is the number of virtual pages.

Distance String Example#

The distance-string counts can be read from the LRU model.

In this example, C1 = 4, C2 = 2, C3 = 1, C4 = 3, C5 = 2, C6 = 2, C7 = 1, and Cinf = 8. Therefore:

F1 = 2 + 1 + 3 + 2 + 2 + 1 + 8 = 19
F2 = 1 + 3 + 2 + 2 + 1 + 8 = 17
F5 = 2 + 1 + 8 = 11
F6 = 1 + 8 = 9

Design Considerations for Paging Systems#

A naive paging system could start a process with none of its pages in memory, but that would cause many page faults at startup.

Real systems try to avoid unnecessary faults. They use locality, read-ahead, working-set estimates, and page replacement policies to keep the pages a process is likely to use in memory.

Working Sets#

A working set is the set of pages a process is actively using during a period of execution.

Many programs show locality of reference. If a process is using one page now, it is likely to use the same page or nearby pages soon. Stacks, heaps, loops, and data structures often create these patterns.

Taking Advantage of Locality#

Operating systems use locality to reduce page faults.

They may load adjacent pages from executable files or libraries, continue loading pages asynchronously after a fault, and prefer evicting pages far from the current working set. These techniques trade a little extra work now for fewer faults later.

Costs of Paging Page Classes#

Not all page evictions cost the same amount.

Unmodified pages can usually be dropped and reloaded later from their original backing store. Modified pages must be written to swap or another backing store before their physical page can be reused.

Reducing Paging Cost#

The kernel can reduce future paging cost by cleaning modified pages in the background.

When the disk is otherwise idle, the system may write dirty pages that are likely eviction candidates. This makes later eviction cheaper because the page is already clean. Replacement policies also prefer clean pages when the performance tradeoff is reasonable.

Local and Global Paging#

Page replacement can be local or global.

In global replacement, a faulting process may cause the kernel to evict a page from any process. In local replacement, the kernel prefers to evict pages owned by the process that faulted. Local replacement can improve fairness, while global replacement can improve overall memory use.

Page Locking#

Page locking pins a page in physical memory so the swapper cannot evict it.

Pinned pages are needed for operations such as DMA, where a device reads from or writes to a specific physical memory region. During the DMA operation, the kernel must ensure that the physical page remains present and stable.

Copy on Write#

Copy on write, or COW, lets related processes share pages until one of them writes to a shared page.

After fork() or clone(), the kernel can copy page-table entries instead of copying every page. The shared entries are marked read-only. When the parent or child writes to one of those pages, the write causes a page fault. The kernel then copies the physical page, updates the faulting process’s page table, and marks the new page writable.

Backing Store#

Backing store is the persistent or recoverable location that backs a virtual page.

For heap, stack, and data pages, the backing store is usually a swap file or swap partition. Simpler systems often prefer swap partitions because the kernel can address the disk directly. Modern systems can also use swap files efficiently because the filesystem can provide stable block locations.

Hibernation#

Hibernation stores the machine’s memory state so the system can power down and later resume.

To hibernate, the operating system writes used physical pages to a hibernation file or swap area. On the next boot, the kernel detects the hibernated state, restores enough core state to resume, rebuilds page tables, and pages data back in as needed.

Hot Memory#

Hot memory is free memory kept available so the system can satisfy small bursts of memory demand without immediate page replacement.

Modern systems often keep some physical pages free even though using all memory for cache might seem optimal. This reserve reduces jitter when processes allocate memory, files are read, or the filesystem cache grows and shrinks.

Hot Memory Example#

The following diagram shows memory use on a long-running Linux system.

The example includes filesystem cache, software memory, buffers, swapped pages, and a small amount of free or recently freed memory. That free area gives the kernel room to respond quickly to new allocation requests.

Summary: Page Fault Handling#

Page fault handling is the path from a faulting memory instruction back to a runnable process.

The usual sequence is:

The hardware traps into the kernel and saves the process state.
The kernel identifies the faulting address and the reason for the fault.
If the access is invalid, the kernel signals or terminates the process.
If the access is valid, the kernel finds or creates a free physical page.
If a dirty page must be evicted, the kernel schedules it to be written to backing storage.
The kernel loads the needed page from backing storage if needed.
The page-table entry is updated to mark the page resident with the correct permissions.
The saved registers are restored.
The faulting instruction is retried, and the process becomes runnable again.

Linux Kernel Module Case Study#

This case study shows the smallest structure of a Linux loadable kernel module.

#include <linux/module.h>

/* Defines the license for this LKM */

MODULE_LICENSE("GPL");

/* Init function called on module entry */

int my_module_init( void )

{

    printk(KERN_INFO "my_module_init called.  Module is now loaded.\n");

    return 0;

}

/* Cleanup function called on module exit */

void my_module_cleanup( void )

{

    printk(KERN_INFO "my_module_cleanup called.  Module is now unloaded.\n");

    return;

}

/* Declare entry and exit functions */

module_init( my_module_init );

module_exit( my_module_cleanup );

Key points:

MODULE_LICENSE() declares the module license to the kernel.
module_init() registers the function called when the module loads.
module_exit() registers the function called when the module unloads.
printk() writes messages to the kernel log rather than standard output.

Linux /proc Module Case Study#

This case study shows a Linux kernel module that exposes state through a /proc entry.

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/proc_fs.h>
#include <linux/string.h>
#include <linux/vmalloc.h>
#include <asm/uaccess.h>

/*
 * original code by:
 * http://www.ibm.com/developerworks/linux/library/l-proc/index.html
 *
 * fixes by: Joe Kaylor
 *
 */
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Fortune Cookie Kernel Module");
MODULE_AUTHOR("M. Tim Jones");

#define MAX_COOKIE_LENGTH       PAGE_SIZE

static struct proc_dir_entry *proc_entry;
static char *cookie_pot;  // Space for fortune strings
static int cookie_index;  // Index to write next fortune
static int next_fortune;  // Index to read next fortune

static const struct file_operations fops =
{
    .owner = THIS_MODULE
};

ssize_t fortune_write(struct file *filp, const char __user *buff, unsigned long len, void *data )
{
    int space_available = (MAX_COOKIE_LENGTH-cookie_index)+1;

    if (len > space_available)
    {
        printk(KERN_INFO "fortune: cookie pot is full!\n");
        return -ENOSPC;
    }

    if (copy_from_user( &cookie_pot[cookie_index], buff, len ))
    {
        return -EFAULT;
    }

    cookie_index += len;

    cookie_pot[cookie_index-1] = 0;

    return len;
}

int fortune_read( char *page, char **start, off_t off, int count, int *eof, void *data )
{
    int len;
    if (off > 0)
    {
        *eof = 1;
        return 0;
    }

    /* Wrap-around */

    if (next_fortune >= cookie_index)
    {
        next_fortune = 0;
    }
    len = sprintf(page, "%s\n", &cookie_pot[next_fortune]);
    next_fortune += len;

    return len;
}

int init_fortune_module( void )
{
    int ret = 0;
    cookie_pot = (char *)vmalloc( MAX_COOKIE_LENGTH );

    if (!cookie_pot)
    {
        ret = -ENOMEM;
    }
    else
    {
        memset( cookie_pot, 0, MAX_COOKIE_LENGTH );

        proc_entry = create_proc_entry( "fortune", 0666, NULL );

        if (proc_entry == NULL)
        {
            ret = -ENOMEM;
            vfree(cookie_pot);
            printk(KERN_INFO "fortune: Couldn't create proc entry\n");
        }
        else
        {
            cookie_index = 0;
            next_fortune = 0;
            proc_entry->read_proc = fortune_read;
            proc_entry->write_proc = fortune_write;
            proc_entry->size = MAX_COOKIE_LENGTH;
            printk(KERN_INFO "fortune: Module loaded.\n");
        }
    }
    return ret;
}

void cleanup_fortune_module( void )
{
    remove_proc_entry("fortune", &proc_entry);
    vfree(cookie_pot);
    printk(KERN_INFO "fortune: Module unloaded.\n");
}


module_init( init_fortune_module );
module_exit( cleanup_fortune_module );

Key points:

The module allocates kernel memory for stored fortune strings with vmalloc().
create_proc_entry() creates the /proc/fortune interface.
copy_from_user() copies data safely from a user buffer into kernel memory.
The read handler returns one stored fortune at a time.
Cleanup removes the proc entry and frees the allocated memory.

Linux Character Device Case Study#

This case study shows how a Linux character device exposes kernel code through the file interface.

/*
 *  example from htttp://tldbp.org/LDP/lkmpg/2.6/html/x569.html
 *
 *  Various fixes and updates by Joe Kaylor
 *
 */


/*
 *  chardev.c: Creates a read-only char device that says how many times
 *  you've read from the dev file
 */

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/fs.h>
#include <asm/uaccess.h>	/* for put_user */

/*
 *  Prototypes - this would normally go in a .h file
 */
int init_module(void);
void cleanup_module(void);
static int device_open(struct inode *, struct file *);
static int device_release(struct inode *, struct file *);
static ssize_t device_read(struct file *, char *, size_t, loff_t *);
static ssize_t device_write(struct file *, const char *, size_t, loff_t *);

#define SUCCESS 0
#define DEVICE_NAME "chardev"	/* Dev name as it appears in /proc/devices   */
#define BUF_LEN 80		/* Max length of the message from the device */

/*
 * Global variables are declared as static, so are global within the file.
 */

static int Major;		/* Major number assigned to our device driver */
static int Device_Open = 0;	/* Is device open?
				 * Used to prevent multiple access to device */
static char msg[BUF_LEN];	/* The msg the device will give when asked */
static char *msg_Ptr;

static struct file_operations fops =
{
    .read = device_read,
    .write = device_write,
    .open = device_open,
    .release = device_release
};

/*
 * This function is called when the module is loaded
 */
int init_module(void)
{
    Major = register_chrdev(0, DEVICE_NAME, &fops);

    if (Major < 0)
    {
        printk(KERN_ALERT "Registering char device failed with %d\n", Major);
        return Major;
    }

    printk(KERN_INFO "I was assigned major number %d. To talk to\n", Major);
    printk(KERN_INFO "the driver, create a dev file with\n");
    printk(KERN_INFO "'mknod /dev/%s c %d 0'.\n", DEVICE_NAME, Major);
    printk(KERN_INFO "Try various minor numbers. Try to cat and echo to\n");
    printk(KERN_INFO "the device file.\n");
    printk(KERN_INFO "Remove the device file and module when done.\n");

    return SUCCESS;
}

/*
 * This function is called when the module is unloaded
 */
void cleanup_module(void)
{
    /*
     * Unregister the device
     */
    /*int ret = */unregister_chrdev(Major, DEVICE_NAME);
    /*if (ret < 0)
    	printk(KERN_ALERT "Error in unregister_chrdev: %d\n", ret);*/
}

/*
 * Methods
 */

/*
 * Called when a process tries to open the device file, like
 * "cat /dev/mycharfile"
 */
static int device_open(struct inode *inode, struct file *file)
{
    static int counter = 0;

    if (Device_Open)
        return -EBUSY;

    Device_Open++;
    sprintf(msg, "I already told you %d times Hello world!\n", counter++);
    msg_Ptr = msg;
    try_module_get(THIS_MODULE);

    return SUCCESS;
}

/*
 * Called when a process closes the device file.
 */
static int device_release(struct inode *inode, struct file *file)
{
    Device_Open--;		/* We're now ready for our next caller */

    /*
     * Decrement the usage count, or else once you opened the file, you'll
     * never get get rid of the module.
     */
    module_put(THIS_MODULE);

    return 0;
}

/*
 * Called when a process, which already opened the dev file, attempts to
 * read from it.
 */
static ssize_t device_read(struct file *filp,	/* see include/linux/fs.h   */
                           char *buffer,	/* buffer to fill with data */
                           size_t length,	/* length of the buffer     */
                           loff_t * offset)
{
    /*
     * Number of bytes actually written to the buffer
     */
    int bytes_read = 0;

    /*
     * If we're at the end of the message,
     * return 0 signifying end of file
     */
    if (*msg_Ptr == 0)
        return 0;

    /*
     * Actually put the data into the buffer
     */
    while (length && *msg_Ptr)
    {

        /*
         * The buffer is in the user data segment, not the kernel
         * segment so "*" assignment won't work.  We have to use
         * put_user which copies data from the kernel data segment to
         * the user data segment.
         */
        put_user(*(msg_Ptr++), buffer++);

        length--;
        bytes_read++;
    }

    /*
     * Most read functions return the number of bytes put into the buffer
     */
    return bytes_read;
}

/*
 * Called when a process writes to dev file: echo "hi" > /dev/hello
 */
static ssize_t
device_write(struct file *filp, const char *buff, size_t len, loff_t * off)
{
    printk(KERN_ALERT "Sorry, this operation isn't supported.\n");
    return -EINVAL;
}

Key points:

register_chrdev() asks the kernel for a major device number.
The file_operations structure connects file operations to driver functions.
device_open() prepares the message returned by the device.
put_user() copies bytes from kernel memory to the user buffer.
unregister_chrdev() removes the device registration when the module unloads.

Linux System Call Case Study#

This case study shows the pieces needed to add and test a simple Linux system call.

diff -r linux-source-2.6.38-orig//arch/x86/ia32/ia32entry.S linux-source-2.6.38//arch/x86/ia32/ia32entry.S
853a854
> 	.quad sys_addsyscall
diff -r linux-source-2.6.38-orig//arch/x86/include/asm/unistd_32.h linux-source-2.6.38//arch/x86/include/asm/unistd_32.h
348a349
> #define __NR_addsyscall		341
352c353
< #define NR_syscalls 341
---
> #define NR_syscalls 342
diff -r linux-source-2.6.38-orig//arch/x86/include/asm/unistd_64.h linux-source-2.6.38//arch/x86/include/asm/unistd_64.h
671a672,673
> #define __NR_addsyscall				303
> __SYSCALL(__NR_addsyscall, sys_addsyscall)
diff -r linux-source-2.6.38-orig//arch/x86/kernel/syscall_table_32.S linux-source-2.6.38//arch/x86/kernel/syscall_table_32.S
342a343,344
> 	.long sys_addsyscall
> 

Key points:

The patch adds a system call number for the new call.
The syscall table is updated so the kernel can dispatch to the new handler.
The public syscall declaration is added to syscalls.h.
The implementation adds two integer arguments and returns the result.

#include <unistd.h>
#include <stdio.h>

#define __NR_addsyscall (303)

long addsyscall(int x, int y)
{
    return syscall(__NR_addsyscall, x, y);
}

int main(int argc, char* argv[])
{
    int result = (int)addsyscall(2, 3);
    printf("result = %d\n", result);
    if(result == (-1))
    {
        perror("error");
    }
    return 0;
}

Key points:

The test program defines the syscall number used by the patched kernel.
syscall() invokes the kernel entry directly.
The wrapper function gives the test a normal C function shape.
perror() reports failure if the syscall returns -1.

Minix Startup Case Study#

This case study shows a minimal Minix program using the System Event Framework startup path.

#include <stdio.h>
#include <stdlib.h>
#include <minix/syslib.h>

int main(int argc, char **argv)
{
    sef_startup();

    printf("Hello, World!\n");
    return EXIT_SUCCESS;
}

Key points:

sef_startup() initializes the Minix service environment.
The program then runs ordinary user code.
The example is useful as a minimal starting point for Minix service examples.

Minix Time Driver Case Study#

This case study shows a small Minix character driver that exposes the current time from CMOS through a device interface.

#ifndef __TIME_H
#define __TIME_H

#define TIME_MAJOR (17)

#endif /* __TIME_H */

Key points:

TIME_MAJOR defines the major number for the time device.
The header keeps the device number separate from the driver implementation.

#include <minix/drivers.h>
#include <minix/driver.h>
#include <unistd.h>
#include <errno.h>
#include <time.h>
#include <stdio.h>
#include <stdlib.h>
#include <minix/ds.h>
#include <machine/cmos.h>
#include "time.h"

/*
 *
 *  Some code borrowed from /usr/src/drivers/readclock
 *
 */


FORWARD _PROTOTYPE( char * time_name,   (void) );
FORWARD _PROTOTYPE( int time_open,      (struct driver *d, message *m) );
FORWARD _PROTOTYPE( int time_close,     (struct driver *d, message *m) );
FORWARD _PROTOTYPE( struct device * time_prepare, (int device) );
FORWARD _PROTOTYPE( void time_from_cmos, (char* buffer, int size));
FORWARD _PROTOTYPE( int time_transfer,  (int procnr, int opcode,
                    u64_t position, iovec_t *iov,
                    unsigned nr_req) );
FORWARD _PROTOTYPE( void time_geometry, (struct partition *entry) );

/* SEF functions and variables. */
FORWARD _PROTOTYPE( void sef_local_startup, (void) );
FORWARD _PROTOTYPE( int sef_cb_init, (int type, sef_init_info_t *info) );

/* Entry points to the time driver. */
PRIVATE struct driver time_tab =
{
    time_name, time_open, time_close,
    nop_ioctl, time_prepare, time_transfer,
    nop_cleanup, time_geometry, nop_alarm,
    nop_cancel, nop_select, nop_ioctl, do_nop,
};

/** Represents the /dev/time device. */
PRIVATE struct device time_device;

PRIVATE char * time_name(void)
{
    printf("time_name()\n");
    return "time";
}

PRIVATE int time_open(d, m)
struct driver *d;
message *m;
{
    printf("time_open()\n");
    return OK;
}

PRIVATE int time_close(d, m)
struct driver *d;
message *m;
{
    printf("time_close()\n");
    return OK;
}

PRIVATE struct device * time_prepare(dev)
int dev;
{
    time_device.dv_base.lo = 0;
    time_device.dv_base.hi = 0;
    time_device.dv_size.lo = 0;
    time_device.dv_size.hi = 0;
    return &time_device;
}

void write_register(int reg_addr, int value)
{
    if(sys_outb(RTC_INDEX, reg_addr) != OK)
    {
        printf("cmos: outb failed of %x\n", RTC_INDEX);
        exit(1);
    }
    if(sys_outb(RTC_IO, value) != OK)
    {
        printf("cmos: outb failed of %x (index %x)\n", RTC_IO, reg_addr);
        exit(1);
    }
}

int bcd_to_dec(int n)
{
    return ((n >> 4) & 0x0F) * 10 + (n & 0x0F);
}

int dec_to_bcd(int n)
{
    return ((n / 10) << 4) | (n % 10);
}

int read_register(int reg_addr)
{
    u32_t r;

    if(sys_outb(RTC_INDEX, reg_addr) != OK)
    {
        printf("cmos: outb failed of %x\n", RTC_INDEX);
        exit(1);
    }
    if(sys_inb(RTC_IO, &r) != OK)
    {
        printf("cmos: inb failed of %x (index %x) failed\n", RTC_IO, reg_addr);
        exit(1);
    }
    return r;
}

int nflag = 0;
int wflag = 0;
int Wflag = 0;
int y2kflag = 0;

void get_time(struct tm *t)
{
    int osec, n;

    do
    {
        osec = -1;
        n = 0;
        do
        {
            /* Clock update in progress? */
            if (read_register(RTC_REG_A) & RTC_A_UIP) continue;

            t->tm_sec = read_register(RTC_SEC);
            if (t->tm_sec != osec)
            {
                /* Seconds changed.  First from -1, then because the
                 * clock ticked, which is what we're waiting for to
                 * get a precise reading.
                 */
                osec = t->tm_sec;
                n++;
            }
        }
        while (n < 2);

        /* Read the other registers. */
        t->tm_min = read_register(RTC_MIN);
        t->tm_hour = read_register(RTC_HOUR);
        t->tm_mday = read_register(RTC_MDAY);
        t->tm_mon = read_register(RTC_MONTH);
        t->tm_year = read_register(RTC_YEAR);

        /* Time stable? */
    }
    while (read_register(RTC_SEC) != t->tm_sec
            || read_register(RTC_MIN) != t->tm_min
            || read_register(RTC_HOUR) != t->tm_hour
            || read_register(RTC_MDAY) != t->tm_mday
            || read_register(RTC_MONTH) != t->tm_mon
            || read_register(RTC_YEAR) != t->tm_year);

    if ((read_register(RTC_REG_B) & RTC_B_DM_BCD) == 0)
    {
        /* Convert BCD to binary (default RTC mode). */
        t->tm_year = bcd_to_dec(t->tm_year);
        t->tm_mon = bcd_to_dec(t->tm_mon);
        t->tm_mday = bcd_to_dec(t->tm_mday);
        t->tm_hour = bcd_to_dec(t->tm_hour);
        t->tm_min = bcd_to_dec(t->tm_min);
        t->tm_sec = bcd_to_dec(t->tm_sec);
    }
    t->tm_mon--;  /* Counts from 0. */

    /* Correct the year, good until 2080. */
    if (t->tm_year < 80) t->tm_year += 100;

    if (y2kflag)
    {
        /* Clock with Y2K bug, interpret 1980 as 2000, good until 2020. */
        if (t->tm_year < 100) t->tm_year += 20;
    }
}

PRIVATE void time_from_cmos(buffer,size)
char *buffer;
int size;
{
    struct tm tVal;

    get_time(&tVal);


    snprintf(buffer, size,
             "%04d-%02d-%02d %02d:%02d:%02d\n",
             tVal.tm_year + 1900, tVal.tm_mon + 1,
             tVal.tm_mday, tVal.tm_hour, tVal.tm_min,
             tVal.tm_sec);
}

PRIVATE int time_transfer(proc_nr, opcode, position, iov, nr_req)
int proc_nr;
int opcode;
u64_t position;
iovec_t *iov;
unsigned nr_req;
{
    int bytes, ret;
    char buffer[1024];

    printf("time_transfer()\n");

    time_from_cmos(buffer, sizeof(buffer));

    bytes = strlen(buffer) - position.lo < iov->iov_size
            ? strlen(buffer) - position.lo
            : iov->iov_size;
    if(bytes <= 0)
    {
        return OK;
    }
    switch(opcode)
    {
    case DEV_GATHER_S:
        ret = sys_safecopyto(proc_nr, iov->iov_addr, 0, (vir_bytes)(buffer+position.lo),bytes,D);
        iov->iov_size -= bytes;
        break;
    default:
        return EINVAL;
    }
    return ret;
}

PRIVATE void time_geometry(entry)
struct partition *entry;
{
    printf("time_geometry()\n");
    entry->cylinders = 0;
    entry->heads     = 0;
    entry->sectors   = 0;
}

PRIVATE void sef_local_startup()
{
    /*
     * Register init callbacks. Use the same function for all event types
     */
    sef_setcb_init_fresh(sef_cb_init);
    sef_setcb_init_lu(sef_cb_init);
    sef_setcb_init_restart(sef_cb_init);

    /*
     * Register live update callbacks.
     */
    /* - Agree to update immediately when LU is requested in a valid state. */
    sef_setcb_lu_prepare(sef_cb_lu_prepare_always_ready);
    /* - Support live update starting from any standard state. */
    sef_setcb_lu_state_isvalid(sef_cb_lu_state_isvalid_standard);

    /* Let SEF perform startup. */
    sef_startup();
}

PRIVATE int sef_cb_init(int type, sef_init_info_t *info)
{
    int do_announce_driver = TRUE;
    switch(type)
    {
    case SEF_INIT_FRESH:
        printf("startup\n");
        break;
    case SEF_INIT_LU:
        printf("new version\n");
        do_announce_driver = FALSE;
        break;
    case SEF_INIT_RESTART:
        printf("restart\n");
        break;
    }
    if(do_announce_driver)
    {
        driver_announce();
    }
    return OK;
}

PUBLIC int main(int argc, char **argv)
{
    /*
     * Perform initialization.
     */
    sef_local_startup();

    /*
     * Run the main loop.
     */
    driver_task(&time_tab, DRIVER_STD);
    return OK;
}

Key points:

The driver table connects Minix driver operations to local functions.
read_register() and write_register() access CMOS registers through kernel calls.
get_time() reads a stable RTC value and converts BCD fields.
time_transfer() copies formatted time data to the requesting process.
The SEF callbacks handle fresh startup, live update, and restart.

Virtual Memory

Contents

Virtual Memory#

What is Virtual Memory?#

Memory Management Units#

Pages and Page Tables#

Page Table Size#

Page Table Entries#

Multi-Level Page Tables#

Two-Level Page Table#

MMU Address Translation Algorithm#

Page Faults#

Page Faults in UNIX#

Page Faults in Windows#

Page Replacement and Swapping#

When the Swapper Runs#

Physical Page Contenders#

Swapper Algorithms#

Page Classification#

Not Recently Used#

FIFO Replacement#

Second-Chance FIFO#

Clock Replacement#

Least Recently Used#

Not Frequently Used#

Aging#

Belady’s Anomaly#

Belady’s Anomaly Diagram#

Modeling Page Replacement#

Modeling LRU#

Distance Strings#

Distance String Example#

Design Considerations for Paging Systems#

Working Sets#

Taking Advantage of Locality#

Costs of Paging Page Classes#

Reducing Paging Cost#

Local and Global Paging#

Page Locking#

Copy on Write#

Backing Store#

Hibernation#

Hot Memory#

Hot Memory Example#

Summary: Page Fault Handling#

Linux Kernel Module Case Study#

Linux /proc Module Case Study#

Linux Character Device Case Study#

Linux System Call Case Study#

Minix Startup Case Study#

Minix Time Driver Case Study#