Memory

Overview

Memory is one of the most important parts of a computer and without it computers would be very limited.

There is a part of the operating system called the memory manager, which, obviously, managers all of the computer's memory. It's one of the main jobs of the operating system (kernel).

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

Previous hierarchy Updated hierarchy

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

Some Numbers Regarding Memory

Operating System Concepts - 10th Edition Silberschatz, Galvin, Gagne ©2018

Some Numbers Regarding Memory

Operating System Concepts - 10th Edition Silberschatz, Galvin, Gagne ©2018

Reading an integer from disk

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

Reading an integer from disk

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

The Importance of Cache

2-dimensional arrays in C are laid out in row majorrow major ordering (as opposed to column major ordering, e.g. Fortran, OpenGL).

This is just for notation and means that, for performance reasons, you should traverse the array in the order the language says it is ordered.

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

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; }

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

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

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

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"^™.

CacheCache performance

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.)
Imagine if the code below was run on a computer with a unified data/instruction cache. The performance would be terrible. Why?

C code		Assembly
#define SIZE (1024 * 1024 * 10) int A[SIZE]; int B[SIZE]; int C[SIZE]; void fn1(int x) { for (int i = 0; i < SIZE; i++) { A[i] = x / 2; B[i] = A[i] * x * x; C[i] = A[i] * B[i] * 3; } }		fn1: .LFB39: endbr32 pushl %ebp pushl %edi pushl %esi pushl %ebx movl 20(%esp), %eax call __x86.get_pc_thunk.bx addl $_GLOBAL_OFFSET_TABLE_, %ebx movl %eax, %edx shrl $31, %edx addl %eax, %edx sarl %edx movl %edx, %ecx imull %eax, %ecx movl A@GOT(%ebx), %edi movl B@GOT(%ebx), %esi movl C@GOT(%ebx), %ebx imull %eax, %ecx movl %edx, %eax imull %ecx, %eax leal (%eax,%eax,2), %ebp xorl %eax, %eax .L2: movl %edx, (%edi,%eax,4) movl %ecx, (%esi,%eax,4) movl %ebp, (%ebx,%eax,4) addl $1, %eax cmpl $262144000, %eax jne .L2 popl %ebx popl %esi popl %edi popl %ebp ret

C code

Assembly

#define SIZE (1024 * 1024 * 10)

int A[SIZE];
int B[SIZE];
int C[SIZE];

void fn1(int x)
{
  for (int i = 0; i < SIZE; i++)
  {
    A[i] = x / 2;
    B[i] = A[i] * x * x;
    C[i] = A[i] * B[i] * 3;
  } 
}

fn1:
.LFB39:
	endbr32
	pushl	%ebp
	pushl	%edi
	pushl	%esi
	pushl	%ebx
	movl	20(%esp), %eax
	call	__x86.get_pc_thunk.bx
	addl	$_GLOBAL_OFFSET_TABLE_, %ebx
	movl	%eax, %edx
	shrl	$31, %edx
	addl	%eax, %edx
	sarl	%edx
	movl	%edx, %ecx
	imull	%eax, %ecx
	movl	A@GOT(%ebx), %edi
	movl	B@GOT(%ebx), %esi
	movl	C@GOT(%ebx), %ebx
	imull	%eax, %ecx
	movl	%edx, %eax
	imull	%ecx, %eax
	leal	(%eax,%eax,2), %ebp
	xorl	%eax, %eax
.L2:
	movl	%edx, (%edi,%eax,4)
	movl	%ecx, (%esi,%eax,4)
	movl	%ebp, (%ebx,%eax,4)
	addl	$1, %eax
	cmpl	$262144000, %eax
	jne	.L2
	popl	%ebx
	popl	%esi
	popl	%edi
	popl	%ebp
	ret

When the CPU requests a byte of memory from main memory, it needs to first determine:

if the block of memory is currently in the cache (a cache hit or miss)
if the block is in the cache, where in the cache it is
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 main memory.
This chart explains why caching is the most important technique in computing:

Memory vs. CPU Performance

Computer Architecture: A Quantitative Approach ©2012 Elsevier, Inc. All Rights Reserved.

Memory vs. CPU Performance

Computer Architecture: A Quantitative Approach ©2012 Elsevier, Inc. All Rights Reserved.

Fun with cache

Data structures performance comparison (access.c)

/* 4 million (2²²) */
#define SIZE 1024 * 1024 * 4

/* All data together */
struct GRAPHICS_DATA
{
  int red;
  int green;
  int blue;
  int alpha;
};

/* Array of structs containing all data */
struct GRAPHICS_DATA data[SIZE];

/* Colors in separate arrays */
int reds[SIZE];
int greens[SIZE];
int blues[SIZE];
int alphas[SIZE];

int main(void)
{
  int i;
#if 1
  for (i = 0; i < SIZE; i++)
    data[i].red = i % 255;
#else
  for (i = 0; i < SIZE; i++)
    reds[i] = i % 255;
#endif

  return 0;
}

Timings (Your numbers may vary with CPU/memory speed, cache architecture. -O2):

Array of structs: 0.090s
   Array of ints: 0.028s

Array of structures: Only 25% of the pre-fetched data is used, the rest is wasted.

Array of integers: 100% of the pre-fetched data is used.

Suppose we added more data to the structure (not uncommon)

struct GRAPHICS_DATA
{
  int red;
  int green;
  int blue;
  int alpha;
  double x, y, z; /* add more data */
};

Now running it:

Array of structs: 2.408s

Array of bigger structures: Only about 13% of the pre-fetched data is used.

Because of this, structure alignment (from CS120) can interfere with the cache behavior.

Note:

These times are directly related to memory and cache access times. It demonstrates that, if your code requires top performance, you need to understand how your data is structured. You don't just want to blindly lump all data together, unless it's absolutely necessary.

Cache Primer An overview of cache.

Physical vs. Logical Addresses

Physical memory

Consists of the actual memory (hardware) available and uses physical addressesphysical addresses.

RAM (random access memoryrandom access memory) chips/packages on motherboardmotherboard
Device memory

Video cardVideo card memory
Audio card (sound cardsound card) memory
Other devices (network cards, hard drives, etc.)

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.

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.

Address binding

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, at some point.

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.

Load time binding

Addresses are relative (offset) to some base address in physical memory.
(physical address) = (base) + (offset)
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.

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(); /* poor man's pause */ 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.

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

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 to help prevent security exploits.
Windows 7 (2009) and later employ it as well. (The output above left is from Windows XP.)
Mac OS X since version 10.5 (2007) has had some version of it. iOS since version 4.3 (~2011) also has it.
Android has had it since version 4.0 (2011).

3 instances running on Windows 7 (64-bit) 3 instances running on Windows 10 (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

address of global is 00007FF663715000, value is 5 address of local is 000000F5E930F8D0, value is 10 address of static is 00007FF663715004, value is 20 address of global is 00007FF6DD465000, value is 5 address of local is 0000009B2CB4FE80, value is 10 address of static is 00007FF6DD465004, value is 20 address of global is 00007FF6AA0C5000, value is 5 address of local is 00000041A52FFAC0, value is 10 address of static is 00007FF6AA0C5004, value is 20

Windows 7/10 is randomizing global/static as well as the stack.

3 instances running on Windows 7 (64-bit)	3 instances running on Windows 10 (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	address of global is 00007FF663715000, value is 5 address of local is 000000F5E930F8D0, value is 10 address of static is 00007FF663715004, value is 20 address of global is 00007FF6DD465000, value is 5 address of local is 0000009B2CB4FE80, value is 10 address of static is 00007FF6DD465004, value is 20 address of global is 00007FF6AA0C5000, value is 5 address of local is 00000041A52FFAC0, value is 10 address of static is 00007FF6AA0C5004, value is 20

Dynamic Loading

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.

Still used with systems with small amounts of memory (e.g. embedded systems).

Libraries

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 linked library

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 (Microsoft compilers).
usually a .o file extension under Linux/Mac (GNU/Clang 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.

On Windows, static libraries usually have the extension: .lib (for library)
On POSIX, static libraries usually have the extension: .a (for archive)
Two different executables that use the same library function will each have their own copy of the function.

If they are running at the same time, there will be two copies of the function in memory.

Dynamically linked library (DLLDLL) and shared objectsshared objects

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.

If they are running at the same time, there will be only one copy of the function in memory.

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 hello.obj /out:hello.dll
```
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 hello.obj /out:hello.dll
```
Then, create the executable that will use the DLL:
```
cl wmain.c /Fewmain.exe
```
And run it. It should fail.
The module definition file is a simple text file that looks like this:
```
EXPORTS
  printme
  add
```
And this is the link command:
```
link /dll /def:hello.def hello.obj /out:hello.dll
```
Dependency Walker This Windows program allows you to peer inside of DLLs to see all kinds of interesting information. It used to be included with Visual Studio, but I don't think it is any longer. It's pretty old and doesn't work well with Windows 10 (what does?), so you may want to try this: Dependencies, which is a replacement for it. Related information: DLL Hell.

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

Other references:

Program Library How-to shows how to create static/shared/dynamic libraries.
The Dynamic Linker by Michael Kerrisk (author of TLPI)
Beginners Guide to Linkers Talks a lot about Windows

Some details from one of the devs that created the ELF (Executable and Linkable Format or Extensible Linking Format) file format. The articles were written for The Linux Journal in 1995, but they're still very relevant today:
- The ELF Object File Format: Introduction
- The ELF Object File Format by Dissection
- Everything You Ever Wanted to Know about DLLs This is from CppCon 2017. It gives you all of the gory details about DLLs. The talk is very informative and moves pretty quickly (which I like, so I don't get bored) but is far beyond the scope for CS 180. Great information for those that need to know what's really going on with Windows' DLLs.
Note: The C programming language has been around for a long time and is still one of the most popular languages of all time. Though some consider it antiquated, it is unlikely it will cease to exist any time soon. DLLs and shared objects are used everywhere and must have a C interface. Almost every program, regardless of the programming language used, on all major platforms (Windows, Linux, Mac OS, Android, iOS) use these C libraries, even though you (the programmer) may not even be aware of it.

Stack and Heap

A process has two areas of memory to use for program 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). Diagram
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, 8 MB for GNU, but these values can be changed.)
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. (count and i could be in a register)
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.

Implementing a heap using a linked list

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:

Search list for available hole (unallocated block) that is at least size bytes long (see later)
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:

Search for item in the list whose start address is the specified address
Mark item as unallocated
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

Strategies for handling memory requests

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.

Likely to find an available block more quickly.

Quick fit - uses multiple lists

Each list contains blocks of the same size.
No need to search for a fit.

FragmentationFragmentation

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

Page tablesPage tables

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 (typical) 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.
That's where the magical 4GB limit comes from with 32-bit computers. (4,096 * 1,048,576 = 4GB)

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.

Shared pages

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).

E.g. There may be only one copy of the printf function in memory that is used by all running processes.

Protection

Pages can be tagged with special bits:

Read-only (e.g. code or const data)
Read-write (e.g. non-const data)
Execute or no execute (e.g. code)
Invalid (not in physical memory)

Illegal use of memory can be easily detected.

Swapping

If a process is not active, its state 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 allows us to pretend that we have (almost) unlimited amounts of 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.

Freeing physical memory

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.

Demand paging

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.

Copy-on-write (COW)

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: (P₁ is the parent, P₂ is the child)

Before P₂ (child) modifies page 1:

This is why the fork() call is so efficient. Essentially, all it does is:

duplicate the parent's page tables (in the child)
create a unique process id (PID) for the child

In the common case, the child will likely call exec immediately after the call to fork, thus, not wasting any time copying other stuff.

Historical note: The vfork system call was invented as an optimization to fork.

Useful when the child immediately calls one of the exec functions. (No need to duplicate everything.)

The parent process is blocked until the child exits or calls exec.

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.)

From the man page:
Historic description
Under Linux, fork(2) is implemented using copy-on-write pages, so the only penalty incurred by fork(2) is the time and memory required to duplicate the parent's page tables, and to create a unique task structure for the child. However, in the bad old days a fork(2) would require making a complete copy of the caller's data space, often needlessly, since usually immediately afterward an exec(3) is done. Thus, for greater efficiency, BSD introduced the vfork() system call, which did not fully copy the address space of the parent process, but borrowed the parent's memory and thread of control until a call to execve(2) or an exit occurred. The parent process was suspended while the child was using its resources. The use of vfork() was tricky: for example, not modifying data in the parent process depended on knowing which variables were held in a register.

Page replacement

When a page fault occurs, but there are no free physical memory frames:

A victim frame must be chosen — this frame may need to be paged out (written to disk).
The page that caused the fault will be assigned to the victim frame and read in from disk.
It's possible that an unused frame (least recently used) from the requesting process will be used to satisfy the request rather than "stealing" it from another process.

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, hasn't been modified, and can be paged back in later).

Page replacement algorithmsPage replacement algorithms

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)

To see it, try this pattern 3 2 1 0 3 2 4 3 2 1 0 4 with 3 frames (9 faults) and then 4 frames (10 faults).

Second chance algorithm (a.k.a. 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 frame, 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 (oldest) time stamp value.

Stack-like structure 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
The data structure used (stack vs. queue) determines the mechanics.
A queue is a more general-purpose structure.

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 be sorted by 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.

ThrashingThrashing

Paging is expensive

Page fault (interrupt) handling: save PCB, put process in Blocked queue
Search for a free frame - apply the page replacement algorithm if none are free
Copy page 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

Avoiding page faults

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).

Memory Cache (revisited)

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 more likely, a 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 lot of the performance of a CPU comes from the cache implementation (prediction, read-ahead, pre-fetching).
Locality of referenceLocality of reference The concept that objects near to each other in memory improve overall performance.

Spatial locality - Objects physically next to each other
Temporal locality - Objects accessed around the same time
Array access vs. linked-list access:

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. This article is kind of like Mead's Coke Story, except it uses a lumberyard/furniture store metaphor instead. If you only read one article on cache, this is it.

Security Issues

Re-using pages from another process?
Data must be cleared (set to 0) before giving the page to another process.
Generally done by a background thread.

Links:

What Every Programmer Should Know About Memory This is definitely an advanced read, but if you want all of the gory details, here they are.

Abstract: As CPU cores become both faster and more numerous, the limiting factor for most programs is now, and will be for some time, memory access. Hardware designers have come up with ever more sophisticated memory handling and acceleration techniques—such as CPU caches—but these cannot work optimally without some help from the programmer. Unfortunately, neither the structure nor the cost of using the memory subsystem of a computer or the caches on CPUs is well understood by most programmers. This paper explains the structure of memory subsystems in use on modern commodity hardware, illustrating why CPU caches were developed, how they work, and what programs should do to achieve optimal performance by utilizing them.

Remember this chart? This is the reason why we are dealing with any of this.