Memory

Overview

• There is a part of the operating system called the memory manager, which, obviously, managers all of the computer's memory
• Keep track of all of the memory (in-use and available)
• Allocate and deallocate memory for processes
• Swap data in and out of memory (from memory to disk and disk to memory)
• Programs must be in memory to execute (the disk is strictly to store the program until execution time)
• As with most topics in operating systems, it's all about efficiency.
• We want to keep the CPU busy at all times.
• To keep the CPU busy, we need to run multiple programs.
• To run multiple programs we need lots of memory.
• We'll likely never have enough memory for all processes to have exclusive use, so we'll need to share the memory
• Memory is much more expensive than disk storage
• Disk storage is cheap and very large
• Memory is expensive and very small (in relation to disk storage)
• The faster the device, the more expensive it is and the less of it there is
• The slower the device, the cheaper it is and the more of it there is

Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009

Some Numbers Regarding Memory
Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009

Reading an integer from disk
Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009

• 2-dimensional arrays in C are laid out in row majorrow major ordering (as opposed to column major ordering, e.g. Fortran).
• This has a significant effect on the performance of memory.
• The effect of cache memory can be seen in the example below.
• Here are two matrices (2-dimensional array) and their layouts:

Row major	Column major
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99	0 10 20 30 40 50 60 70 80 90 1 11 21 31 41 51 61 71 81 91 2 12 22 32 42 52 62 72 82 92 3 13 23 33 43 53 63 73 83 93 4 14 24 34 44 54 64 74 84 94 5 15 25 35 45 55 65 75 85 95 6 16 26 36 46 56 66 76 86 96 7 17 27 37 47 57 67 77 87 97 8 18 28 38 48 58 68 78 88 98 9 19 29 39 49 59 69 79 89 99

• However, we know that memory isn't 2D, so it's really laid out more like this:

Row: 0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29 etc...

Col: 0   10  20  30  40  50  60  70  80  90 1   11  21  31  41  51  61  71  81  91  2   12  22  32  42  52  62  72  82  92 etc...

• This program is going to show that all memory accesses are not equal:

Access row-at-a-time	Access column-at-a-time
int row_major(int *array, int stride) { int i, j, index = 0, count = 0; printf("Row major:\n"); for (i = 0; i < stride; i++) { for (j = 0; j < stride; j++) { index = i * stride + j; array[index] = count++; } } return index; }	int col_major(int *array, int stride) { int i, j, index = 0, count = 0; printf("Col major:\n"); for (i = 0; i < stride; i++) { for (j = 0; j < stride; j++) { index = j * stride + i; array[index] = count++; } } return index; }

• Here's the program (mem1.c) in one file. (gcc mem1.c)
• Output:

Access row-at-a-time	Access column-at-a-time
time ./mem1 30000 0 stride = 30000, total = 900000000, fn = 0 Row major: real 0m5.406s user 0m4.080s sys 0m1.290s	time ./mem1 30000 1 stride = 30000, total = 900000000, fn = 1 Column major: real 0m29.360s user 0m27.850s sys 0m1.460s

With optimization (gcc -O2 mem1.c)

Access row-at-a-time	Access column-at-a-time
time ./mem1 30000 0 stride = 30000, total = 900000000, fn = 0 Row major: real 0m1.500s user 0m0.340s sys 0m1.140s	time ./mem1 30000 1 stride = 30000, total = 900000000, fn = 1 Column major: real 0m28.022s user 0m26.560s sys 0m1.420s

• It should be very apparent why Mead is always saying that "Cache is King"^™.

• Cache exploits a process' locality of referencelocality of reference by assuming the process' next memory access will be near the previous one.
• Searching through the caches looking for code/data takes time.
• If the code/data is in the cache, it's called a cache hit. (Many cache hits increase the performance of programs a lot.)
• If the code/data is NOT in the cache, it's called a cache misscache miss. (Many cache misses can decrease the performance of programs a lot.)
• Some (many/most?) CPU architectures separate the instruction cache from the data cache.
  • This can have significant impact.
  • Think: loops (which form the backbone of most programs.)
• When the CPU requests a byte of memory from main memory, it needs to first determine:
1. if the block of memory is currently in the cache (a cache hit or miss)
2. if the block is in the cache, where in the cache it is
3. where the byte is within the block
• These operations must be performed extremely quickly or else the cache mechanism is going to make things worse.
• A special kind of very fast (and very expensive) memory is used to build caches.
• The larger the cache:
• the more code/data can be stored, but that also means that it takes longer to search for the code/data.
• the more expensive it is in both cost and CPU real estate. (CPUs have limited space.)
• CPU/cache diagrams for
  • server (AMD FX-8120 quad-core)
  • veronica (Intel i7-3517UE dual-core)
  • clara (Intel i5-2500K quad-core)
• Why is cache so important (possibly, the most important factor) in today's computers?
  • CPU speeds are getting faster and faster, while (main) memory speeds are not.
  • A CPU can execute hundreds of instructions while waiting for data from the cache.
  • Retrieving data from main memory is glacially slower yet.
  • The bottleneck in modern computers is memory.

Physical vs. Logical Addresses

• Consists of the actual memory (hardware) available and uses physical addressesphysical addresses.
• RAM (random access memoryrandom access memory) chips on motherboardmotherboard
• Device memory
• Video cardVideo card memory
• Audio card (sound cardsound card) memory
• Other devices
• Not to be confused with disk storage.
• Not necessarily organized contiguously
• We (users and programmers) almost never deal with physical memory/addresses.
• We deal with logical memory.

• Relabels, or maps, physical memory into logical addresseslogical addresses (also called virtual addresses).
• Memory addresses generated by the CPU are logical memory addresses.
• Addresses returned by new and malloc are logical memory addresses.
• Logical memory must be translated (mapped) into physical memory to be used.
• This translation is done by the hardware for every memory access.

• Variables and functions (including main) within a program are ultimately represented by addresses in memory.
• The compiler/linker must assign logical addresses to the variables and functions.
• These logical addresses must be mapped (bound) to physical memory.
• Compile time binding
• Absolute code can be generated (the addresses are fixed and known in advance).
• Actual physical memory addresses are used
• (physical address) = (logical address)
• The program must always be loaded at the same address in physical memory.
• DOS .COM programs worked this way (always loaded the program at address 0x100).
• Okay for single-task operating systems.
• Unsuitable for multitasking operating systems.
• Recall this program that demonstrated where data was laid out in memory.
• Or this simple example:

/* address.c */ #include <stdio.h> int global = 5; int main(void) { int local = 10; static int st = 20; printf("address of global is %p, value is %i\n", (void*)&global, global); printf("address of local is %p, value is %i\n", (void*)&local, local); printf("address of static is %p, value is %i\n", (void*)&st, st); getchar(); return 0; }

Output:

3 instances running on Windows XP (32-bit)		3 instances running on Linux (64-bit)
address of global is 0040D000, value is 5 address of local is 0012FF74, value is 10 address of static is 0040D004, value is 20 address of global is 0040D000, value is 5 address of local is 0012FF74, value is 10 address of static is 0040D004, value is 20 address of global is 0040D000, value is 5 address of local is 0012FF74, value is 10 address of static is 0040D004, value is 20		address of global is 0x601028, value is 5 address of local is 0x7fff039dd77c, value is 10 address of static is 0x60102c, value is 20 address of global is 0x601028, value is 5 address of local is 0x7fff8cdabdfc, value is 10 address of static is 0x60102c, value is 20 address of global is 0x601028, value is 5 address of local is 0x7fffb193203c, value is 10 address of static is 0x60102c, value is 20

• How can this be? It appears that all 3 processes are using the same memory.
• Notice the address of the stack in the Linux output.
  • Linux is employing Address Space Layout Randomization or ASLRASLR, which was created by the Linux PaXPax project in 2001.
  • Windows 7 and later employ it as well. (The output above left is from Windows XP.)
  • Mac OS X since version 10.5 has had some version of it. iOS since version 4.3 also has it.
  • Android has had it since version 4.0.

  3 instances running on Windows 7 (64-bit)

  address of global is 000000013FCF5000, value is 5 address of local is 000000000017F9E0, value is 10 address of static is 000000013FCF5004, value is 20 address of global is 000000013F175000, value is 5 address of local is 00000000001AFA80, value is 10 address of static is 000000013F175004, value is 20 address of global is 000000013F685000, value is 5 address of local is 00000000002AF7C0, value is 10 address of static is 000000013F685004, value is 20

• Load time binding
• Addresses are relative to some base address in physical memory.
• (physical address) = (base) + (logical address)
• Programs can be loaded anywhere in physical memory. (Relocatable code)
• Once the program is loaded, the addresses are assigned and will remain the same for the rest of the execution.
• Program can only be loaded if there is a contiguous block of free memory available large enough to hold the program and data.
• Execution time binding
• The physical address is computed (from the logical address) in hardware at runtime by the memory management unitmemory management unit (MMU).
• (logical address) → (physical address)
• The mapping is not necessarily linear (details will be given later).
• Program may be relocated during execution (even after it is loaded).
• Program does not require contiguous physical memory.
• It is the most flexible and is used by most modern operating systems today.

• Don't need to load the entire program into memory.
• On-demand loading of routines is more efficient when most routines won't be used.
• Programmer's (tools) responsibility not the OS.
• Programmers still have to layout their programs to take advantage. (Minimize inter-dependencies)
• Sometimes this was the only solution when computers had limited memory.

• A library is a collection of compiled functions, usually in the form of a single binary file.
• Standard C and C++ libraries (glibcglibc, msvcrtmsvcrt, etc.)
• Win32 API libraries
• e.g. user32.lib, gdi32.lib, kernel32.lib, etc.
• User created libraries
• Two basic types of libraries
• Statically linkedStatically linked
• Dynamically linkedDynamically linked

• The compiler generates a machine codemachine code image from the user's code, an object fileobject file.
• usually a .obj file extension under MS windows.
• usually a .o file extension under Linux (GNU compilers).
• The linker obtains the library functions used in the user's code from the library file and links them with the object file to produce an executable file.
• Two different executables that use the same library function will each have their own copy of the function.

• The compiler generates an object file from the user's code.
• The linker replaces each library function call with a stub function (a function which will locate the function code at runtime), and generates an executable.
• A library function is loaded into memory only when the stub function is called.
• Two different executables (processes) will use the same library function code: there is only one copy of the function in memory at runtime.
• Example: Creating a dynamic link library and shared-object library from this code: (hello.c)

  #include <stdio.h>
  
  void printme(const char *str)
  {
    printf("Hello from library: %s\n", str);
  }
  
  int add(int a, int b)
  {
    return a + b;
  }
  

  This can easily be statically linked with main1.c

  
  #include <stdio.h>
  
  void printme(const char *str);
  int add(int a, int b);
  
  int main(void)
  {
    printme("This function is statically linked.");
    printf("The sum of 5 and 10 is %i.\n", add(5, 10));
  
    return 0;
  }
  

  gcc main1.c hello.c -o hello-static
  

  Output:

  Hello from library: This function is statically linked.
  The sum of 5 and 10 is 15.
  

• Dynamically linking to the functions from POSIX code (main.c). Compile and link:

  gcc -fPIC -c hello.c -o hello.o
  gcc -shared hello.o -o libhello.so
  gcc main.c -o main -ldl	
  

• Calling the functions from Windows code (wmain.c). Compile and link:

  cl /c hello.c /Fohello.obj
  link /dll /def:hello.def hello.obj /out:hello.dll
  cl wmain.c /Fewmain.exe
  

  May need the entire path to the linker (if GCC's linker is in the path first). For example:

  "C:\Program Files\Microsoft Visual Studio 10.0\vc\bin\link" /dll /def:hello.def hello.obj /out:hello.dll
  

  The module definition file is a simple text file that looks like this:

  EXPORTS
    printme
    add
  

• Calling the functions from D code
• Calling the functions from Python code
• Calling the functions from Free Pascal code
• Calling the functions from Perl code

• The ELF Object File Format: Introduction
• The ELF Object File Format by Dissection

Stack and Heap

• A process has two structures to use for program memory needs
• StackStack
• Function calls: passed arguments and return address
• Local and temporary variables
• Call stackCall stack and stack framestack frame.
• HeapHeap
• Dynamically allocated memory
• The stack grows from top down, the heap grows from bottom up (although this is just a conventional way).
• Enough memory must be allocated to the stack and heap to avoid a collision.
• The stack is generally much smaller than the heap and is allocated by the linker. (About 1 MB with Microsoft's linker, 2 MB for GNU.)
• Simple example:

float *foo(int count)		
{
  int i;
  float *array = malloc(count * sizeof(float));

  for (i = 0; i < count; i++)
    array[i] = sqrt((float)i);

  return array;
}

• variables i, array, and count are allocated on the stack.
• memory pointed to by array is allocated on the heap.
• argument to sqrt is passed on the stack (could be in a register instead).
• the return address from sqrt is passed on the stack.
• the return value from foo is passed on the stack (could be in a register instead).
• What about the address of sqrt? Where is the sqrt function? Refer to this.

• The heap is allocated as a single contiguous chunk of memory
• To keep track of allocated and unallocated blocks within the heap, we maintain a list that stores the following information about each block
• Allocation flag: 0 if unallocated, 1 if allocated
• Address: beginning address of the block
• Size: number of bytes in the block
• List items are ordered by start address
• An alternate scheme is to order the blocks by size.
• To allocate a block of memory of size bytes:
1. Search list for available hole (unallocated block) that is at least size bytes long (see later)
2. Remove the item from the list and replace it with two list items:
• First item represents an allocated block of size bytes, with same start address as original block
• Second item represents an unallocated block (hole) for the remaining unused bytes of the original block
• Return:
• NULL pointer, if no block found in list
• Start address of allocated block, if block is found in list
• To deallocate (free) a block:
1. Search for item in the list whose start address is the specified address
2. Mark item as unallocated
3. Consolidate adjacent unallocated memory into a single unallocated block
• Merge with the preceding memory block if it is currently unallocated
• Merge with the succeeding memory block if it is currently unallocated
• Diagrams and details

• It's possible that we have many different sized blocks on our list
• When allocating a block of size bytes, we may have a choice among various unallocated blocks of size at least size bytes
• First fit - choose the first available hole
• Fast.
• May lead to fragmentation.
• Best fit - choose the smallest hole
• Produces smallest remaining hole.
• Entire list must be searched.
• Worst fit - choose the largest hole
• Produces the largest remaining hole.
• Entire list must be searched.
• Next fit - like first fit but starts where last search left off.

• Two types of fragmentation: External and internal
• External fragmentationExternal fragmentation
• The heap is said to have external fragmentation if there are many small holes between allocated blocks.
• A hole may be smaller than the list item that represents it.
• A fragmented heap may be compacted:
• Move allocated blocks to remove holes.
• Not always practical, since it is a time consuming process.
• Languages with raw pointers, like C/C++, can't do this (easily).
• Also known as garbage collectiongarbage collection.
• Pointers vs. Handles for compacting memory.
• Internal fragmentationInternal fragmentation
• Happens when we try to avoid many very small blocks.
• Instead of tracking many very small and almost useless blocks, we allow blocks to have some "wasted" space.
• Fixed-size blocks can lead to internal fragmentation.
• This is generally a trade off: faster memory allocation and deallocation at the cost of a small amount of memory.

Paging

• Allows contiguous logical memory to be mapped to noncontiguous physical memory
• Avoids the problem of finding a block of physical memory large enough to hold a process
• Requires hardware support in order to implement

• Memory is divided up into blocks of equal size (usually a power of 2)
• Page – block of logical memory
• Frame – block of physical memory of the same size
• Pages are generally 4 KB (4096 bytes) in size
• Some systems support larger page sizes (e.g. 1 MB or 4 MB) using page size extension (PSE)page size extension (PSE)
• Like everything else, there are trade-offs such as needing many more smaller pages for an allocation or having internal fragmentation with larger pages.
• A logical memory location has a page number P and a page offset O within that page
• Generally, the first few bits of the address are used as a page number.
• The rest of the bits are the offset.
• The offset may also be referred to as the displacement.
• The page number is used as an index into a page table which contains base address of each page in physical memory.
• The page offest is combined with base address to define the physical memory address that is sent to the memory unit.
• (logical address) → (P,O)
• Example: logical address 1234 has page number 1 and offset 234
• This means that we look in the page table at index 1 to find the start address (frame) and add 234 to that address.
• Example: logical address 7A64 has page number 7 and offset A64
• This means that we look in the page table at index 7 to find the start address (frame) and add A64 to that address.
• Example: logical address 0100 has page number 0 and offset 100
• This means that we look in the page table at index 0 to find the start address (frame) and add 100 to that address.
• For example, a system with 4KB pages will use only 12 bits for the offset. (2¹² is 4096)
• A 32-bit system could have 20 bits for the page number, for a maximum of 2²⁰ (1,048,576) pages.

Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009


The diagram below may represent a 16K array of characters (four 4096-byte pages). From the programmer's view, it's contiguous, but physically it may not be.

Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009


Another view:

Operating System Concepts - 8th Edition Silberschatz, Galvin, Gagne ©2009

• More page table examples:
• Suppose the page size is 4kb = 1000h
• Assume logical memory starts at address 0
• Page 0 contains: 0000h – 0FFFh
• Page 1 contains: 1000h – 1FFFh
• Page 2 contains: 2000h – 2FFFh
• . . .
• Suppose the page table is

0 | 1234h
1 | 0234h
2 | 8234h
3 | 4234h	

• For (logical address) = 1056h
• Page number: P = 1 (index 1 in the page table)
• Page offset: O = 056h
• From the page table at index 1, P → 0234h
• The physical address of 1056h is then
• (physical address) = 0234h + O
• = 0234h + 056h = 028Ah
• For (logical address) = 317Bh
• P = 3, O = 17Bh
• From the page table at index 3, P → 4234h
• Physical address is: 4234h + 17Bh = 43AFh
• There is overhead incurred by paging
• The page table (possibly large) of a process must be stored in the PCB (process control block) of the process.
• Each logical address must be converted to a physical address (helped by hardware support).
• A translation look-aside buffertranslation look-aside buffer (TLB) is used to speed up the mapping. (It's basically a cache for the page table.)
• May have multiple levels (like cache).
• Contains a few dozen to a few thousand entries.
• Could have separate TLBs for data and instructions. (DTLB and ITLB)
• Hit times of about 1 cycle, miss times from 10 to 100 cycles.
• Hit rate is generally greater than 99%.
• Context switching can be expensive (may flush the TLB).
• Could fail:
• The memory location is invalid (outside of the proceses' address space).
• The memory location is valid, but the physical frame is not resident in memory.

• It is possible for processes to share pages.
• Code pages (dynamic link libraries, shared objects)
• This is not the same as shared memory we discussed during IPC (i.e. shmget).
• IPC shared memory is mainly for shared data, not code.
• Multiple instances of a program can share the code (not the data).
• There may be only one copy of the printf function in memory that is used by all running processes.

• Pages can be tagged with special bits:
• Read-only
• Read-write
• Execute or no execute
• Invalid (not in physical memory)
• Illegal use of memory can be easily detected.

• If a process is not active, it may be copied from memory to disk (disk swapping).
• The swap area on the disk is special because it needs high-performance.
• 32-bit and 64-bit Windows (before Windows 8) has one or more files called pagefile.syspagefile.sys where it stores processes. (Backing store)
• Windows 8 and 10 also have a swapfile.sys, as well. Some information here.
• Linux (or a Unix-like system) uses a swap partitionswap partition (or file) to manage the processes.

Virtual Memory

Virtual memory space

• We allow the logical memory size to exceed physical memory size.
• Pages and frames are added to the page table as needed.
• When physical memory has been exceeded, frames are written (temporarily) to the hard disk to free up physical memory.
• Swap space is used for writing frames: a contiguous block of disk space set aside for this purpose.

• Swapping – an entire process (including data, stack, and code segments) is removed from physical memory and written to disk.
• Frees up several frames of physical memory.
• Paging – a frame of physical memory is written to disk.
• Frees up a single frame of physical memory
• Several contiguous frames may be written to disk at one time
• Swapping and paging are expensive (in terms of time), so should be minimized.
• Too much swapping/paging leads to thrashingthrashing.

• Also called lazy swapping.
• A page in virtual memory is given a physical frame only when memory within that page is accessed.
• Each entry in the page table contains a bit (flag) to mark the page.
• Valid – the logical page has been assigned a physical frame.
• Invalid – the logical page has not been assigned a physical frame.
• When a location in logical memory is accessed, the valid/invalid bit of corresponding page is examined.
• If the page is valid, process execution continues as normal.
• If the page is invalid, a page faultpage fault occurs.
• The OS finds a free frame in physical memory.
• The desired page is read into the new frame.
• The page table is updated with the new page information, and valid/invalid bit is set to valid.
• Process execution is resumed.
• Demand paging can boost performance when starting a program.
• Only the first page that contains the first instruction needs to be loaded.
• As the code is executed, more pages will be brought in.
• No need to bring in the entire program to begin execution.
• As long as the page-fault rate is reasonably low, performance is acceptable.
• Because of the likelyhood of locality of reference of programs, the worst-case (every instruction causes a page fault) is very rare.

• Logically, when a process forks another process, each process has its own copy of memory.
• The parent and child processes do not share the pages.
• With COW, parent-child processes originally share pages (after the fork).
• Only when one of the processes modifies a page does an actual copy take place.
• Since many (even most or all) pages are not modified, there is little copying (faster performance).
• Windows and Linux both use COW to increase performance.
• Immediately after a fork system call:



• After P₂ modifies page 1:



• The vfork system call was invented as an optimization to fork.
• However, today's implementations of fork are quite good. Here are some caveats to using vfork today.
• This description of vfork and page sharingvfork and page sharing is also enlightening.
• In the end, the copy-on-write semantics of most operating systems (and fork implementations) make vfork unecessary, yet it's still an interesting approach to the original problem.
• Bottom line: Don't use vfork. (It's usually just an alias to fork anyway.)

Page replacement

• When a page fault occurs, but there are no free physical memory frames:
• A victim frame must be chosen – this frame will be paged out (written to disk).
• The page that caused the fault will be assigned to the victim frame and read in from disk.
• Optimization: a page that has not been modified since it was first read in (such as a code segment) need not be saved to disk (it is already there and hasn't been modified).

• FIFO (First-In First-Out) page replacement
• This page replacement algorithm chooses the page that has been in physical memory for the longest as the victim frame.
• Easy to implement using a (FIFO) queue.
• Often does not yield optimal performance: more than the minimum number of page faults will occur.
• All pages are considered of equal importance, which is generally not true. (Rarely accessed vs. often accessed, high vs. low priority processes.)
• Suppose there are 3 frames of physical memory.
• Suppose we access the following sequence of pages in logical memory:

7, 0, 1, 2, 0, 3, 0, 2, 0, 4, 0, 2

• The queue states are

7    fault [7    ]
0    fault [7 0  ]
1    fault [7 0 1]
2    fault [0 1 2]
0     ok   [0 1 2]
3    fault [1 2 3]
0    fault [2 3 0]
2     ok   [2 3 0]
0     ok   [2 3 0]
4    fault [3 0 4]
0     ok   [3 0 4]
2    fault [0 4 2]

• Total of 8 page faults
• What if the access pattern was 1 2 3 4 1 2 3 4 1 2 3 4? (Work it out on your own.)
• What if there were 4 frames with the original sequence? (Work it out on your own.)
• Adding more frames does not always result in less page faults (Bélády anomalyBélády's anomaly)
• Second chance algorithm (clock)
• A modification of the FIFO algorithm.
• Some implementations will distinguish between second chancesecond chance and clockclock, but they are logically the same, but the implementations are different (queue vs. circular queue).
• Each page in memory has a reference bit associated with it.
• Whenever a page is referenced (a memory location within the page is accessed), the reference bit is set to 1
• If a page is already in memory then no searching is done, as it is at a known location (via the page table) and the reference bit is set.
• If a page is not in memory and there is no available frames, then a search will occur.
• During the search as pages are encountered for possible replacement, the value of the reference bit is examined
• If it is 0, the page is replaced
• If it is 1, the bit set to 0, and the next item in the queue is selected in circular queue fashion.
• The page replacement policy only kicks in if the page is not present and there aren't any more available frames.

Operating System Internals and Desgin Principles - 5th Edition William Stallings ©2005

• 3 frames of physical memory (as before)
• These pages are accessed (as before):

7, 0, 1, 2, 0, 3, 0, 2, 0, 4, 0, 2

• The queue states are (+ = 1, - = 0) and the underscore indicates the position of the "clock hand" after the replacement.

7    fault [7+      ]
0    fault [7+ 0+   ]
1    fault [7+ 0+ 1+]
2    fault [2+ 0- 1-]
0     ok   [2+ 0+ 1-]
3    fault [2+ 0- 3+]
0     ok   [2+ 0+ 3+]
2     ok   [2+ 0+ 3+]
0     ok   [2+ 0+ 3+]
4    fault [4+ 0- 3-]
0     ok   [4+ 0+ 3-]
2    fault [4+ 0- 2+]

• Total of 7 page faults
• What if there were 4 frames? (Work it out on your own.)
• There is a simple optimization that can be added to the algorithm with only one additional bit: a dirty bit.
• A dirty bit just indicates that the page has been modified.
• Pages that have been modified will be required to be written back to the disk. This means another I/O operation.
• Non-dirty pages (i.e. unmodified pages) don't have to be written back to disk so it will be faster to replace those pages.
• Using 2 bits (accessed and modified) can improve overall performance during the page replacement operation.
• LRULRU (Least Recently Used) algorithm
• The page that has not been used for the longest period of time is selected as victim frame.
• Implemented in one of two ways:
• Time stamp is used - whenever a page is referenced, it is marked with the time.
• The victim frame is the page with the smallest time stamp value.
• Stack is used – if a page is referenced, it is removed from the stack and placed on top.
• The victim frame is the page at the bottom of the stack
• Generally expensive to implement as it can be a time-consuming task.
• 3 frames of physical memory (as before)
• These pages are accessed (as before):

7, 0, 1, 2, 0, 3, 0, 2, 0, 4, 0, 2

• Queues states ((#) = time stamp):

                               Time
7    fault [7(0)            ]   0
0    fault [7(0)  0(1)      ]   1
1    fault [7(0)  0(1)  1(2)]   2
2    fault [0(1)  1(2)  2(3)]   3
0     ok   [1(2)  2(3)  0(4)]   4
3    fault [2(3)  0(4)  3(5)]   5
0     ok   [2(3)  3(5)  0(6)]   6
2     ok   [3(5)  0(6)  2(7)]   7
0     ok   [3(5)  2(7)  0(8)]   8
4    fault [2(7)  0(8)  4(9)]   9
0     ok   [2(7)  4(9) 0(10)]  10
2     ok   [4(9) 0(10) 2(11)]  11

• Total of 6 page faults
• The internal order of the queue doesn't really matter (it's up to the implementation)
• Oldest one is replaced (may sort on age).
• What if there were 4 frames? (Work it out on your own.)
• This algorithm intuitively makes sense.
• Optimal Page Replacement
• Replace the page that is the likeliest to not be needed.
• Easier said than done. (Prediction)
• The same "problem" is inherent in the SJF scheduling algorithm.
• Mainly used as a reference to compare replacement algorithms.

• Paging is expensive
• Page fault (interrupt) handling: save PCB, put process in Blocked queue
• Search for free frame - apply page replacement algorithm if none free
• Copy to and from disk
• I/O wait
• Restore PCB and restart process (put process in Ready queue)
• Thrashing occurs when the system spends more time paging than executing processes.
• May happen if there are many processes running (CPU high utilization).
• It's generally a good indication that the system needs more physical memory.
• Your system is thrashing when:
• High disk usage when no process is doing I/O
• CPU activity is low and responsiveness is low
• Interactions cause lots of unexplained disk I/O

• As a programmer, there are some things you can do to decrease the amount of paging that your program will undergo when executing – thereby reducing the execution time.
• Localize variable access when possible – when accessing a set of variables repeatedly, try to keep the variables near each other in memory.
• When doing two-dimensional array computations, process the array elements by rows. (See this example above for details.)
• If you have to use a linked list with a large number of entries, you can allocate nodes from a contiguous block of memory (e.g. a custom memory manager).

• In addition to RAM, most computers also use a CPU cache: special high speed memory used to temporarily store frequently accessed memory.
• When a page of logical memory is accessed, a copy (or partial copy) is placed into the cache.
• As long as the page remains in the cache, memory access is improved.
• A cache miss occurs when logical memory is accessed that is not in the cache (even though it may be in physical memory).
• A program may avoid cache misses by using the same techniques used to avoid page faults.
• A lot of the performance of a CPU comes from the cache implementation (prediction).
• Locality of referenceLocality of reference The concept that objects near to each other in memory improve overall performance.
• Understanding CPU Caching and Performance This is an article from Ars Technica. It's a little old, but the information is still very accurate and relevant.