Understanding glibc malloc


I always got fascinated by heap memory. Questions such as

How heap memory is obtained from kernel?
How efficiently memory is managed?
Is it managed by kernel or by library or by application itself?
Can heap memory be exploited?

were in my mind for quite some time. But only recently I got time to understand about it. So here I would like to share my fascination turned knowledge!! Out there in the wild, many memory allocators are available:

  • dlmalloc – General purpose allocator
  • ptmalloc2 – glibc
  • jemalloc – FreeBSD and Firefox
  • tcmalloc – Google
  • libumem – Solaris

Every memory allocator claims they are fast, scalable and memory efficient!! But not all allocators can be suited well for our application. Memory hungry application’s performance largely depends on memory allocator performance. In this post, I will only talk about ‘glibc malloc’ memory allocator. In future, I am hoping to cover up other memory allocators. Throughout…

View original post 3,632 more words

Commons Problems in Parallel Programming

Dining Philosophers Problem

140px-An_illustration_of_the_dining_philosophers_problemThis is a classic problem with data sharing and signaling.

Five (male) philosophers spend their lives thinking and eating. The philosophers share a common circular table surrounded by five chairs, each belonging to one philosopher. In the centre of the table there is a bowl of spaghetti, and the table is laid with five forks, as shown in figure. When a philosopher thinks, he does not interact with other philosophers. From time to time, a philosopher gets hungry. In order to eat he must try to pick up the two forks that are closest (and are shared with his left and right neighbors), but may only pick up one fork at a time. He cannot pick up a fork already held by a neighbor. When a hungry philosopher has both his forks at the same time, he eats without releasing them, and when he has finished eating, he puts down both forks and starts thinking again.

Solutions to this kind of problem are as follows:

  1. Use resource hierarchy: assign numbers to the forks (resources). The philosopher can only request resource with lower number first then the higher number.
  2. Use a central entity for assigning permissions: use a arbitrator (waiter) as a mutex which will allow the philosopher to periodically use the forks(resources).
  3. Distributed message passing between the philosophers without a central authority.
    1. For every pair of philosophers contending for a resource, create a fork and give it to the philosopher with the lower ID (n for agent Pn). Each fork can either be dirtyor clean. Initially, all forks are dirty.
    2. When a philosopher wants to use a set of resources (i.e. eat), said philosopher must obtain the forks from their contending neighbors. For all such forks the philosopher does not have, they send a request message.
    3. When a philosopher with a fork receives a request message, they keep the fork if it is clean, but give it up when it is dirty. If the philosopher sends the fork over, they clean the fork before doing so.
    4. After a philosopher is done eating, all their forks become dirty. If another philosopher had previously requested one of the forks, the philosopher that has just finished eating cleans the fork and sends it.

Sleeping Barber Problem

206px-Sleeping_barberThis is a classic single procedure multiple consumer problem.

The analogy is based upon a hypothetical barber shop with one barber. The barber has one barber chair and a waiting room with a number of chairs in it. When the barber finishes cutting a customer’s hair, they dismiss the customer and go to the waiting room to see if there are other customers waiting. If there are, they bring one of them back to the chair and cut their hair. If there are no other customers waiting, they return to their chair and sleep in it.

Each customer, when they arrive, looks to see what the barber is doing. If the barber is sleeping, the customer wakes them up and sits in the chair. If the barber is cutting hair, the customer goes to the waiting room. If there is a free chair in the waiting room, the customer sits in it and waits their turn. If there is no free chair, the customer leaves.

Process Synchronization and IPC

Why Synchronization

Since Linux 2.0 support Symmetric Multiprocessing with multicore modern microprocessors. But with this new dimension of problems arose like race conditions, dead/live locks etc. In order to mitigate these issues, various synchronization mechanisms were introduced in Linux. The 2.6 version of Linux supported full preemption, that means scheduler can preempt kernel code at virtually any point and reschedule another task.

  • critical path: code that access and manipulate shared data

Reasons for Synchronization:

  • Interrupts. An interrupt can occur asynchronously at almost any time, interrupting the currently executing code.
  • Softirqs and tasklets. The kernel can raise or schedule a softirq or tasklet at almost any time, interrupting the currently executing code.
  • Kernel preemption. Because the kernel is preemptive, one task in the kernel can preempt another.
  • Sleeping and synchronization with user-space. A task in the kernel can sleep and thus invoke the scheduler, resulting in the running of a new process.
  • Symmetrical multiprocessing. Two or more processors can execute kernel code at exactly the same time.

Ways to Synchronization

  • Shared Memory
  • Sockets
  • Atomics and lock-free programming
  • Pipes/FIFOs
  • Mutexes
    • recursive
    • reader/writer
  • Spinlocks
  •  Semaphores
    • Binary and counting
  • Condition variables
  • Messages Queues


Since all threads run in the same address space, they all have access to the same data and variables. If two threads simultaneously attempt to update a global counter variable, it is possible for their operations to interleave in such way that the global state is not correctly modified. Although such a case may only arise only one time out of thousands, a concurrent program needs to coordinate the activities of multiple threads using something more reliable that just depending on the fact that such interference is rare.

A semaphore is somewhat like an integer variable, but is special in that its operations (increment and decrement) are guaranteed to be atomic—you cannot be halfway through incrementing the semaphore and be interrupted and waylaid by another thread trying to do the same thing. That means you can increment and decrement the semaphore from multiple threads without interference. By convention, when a semaphore is zero it is “locked” or “in use”.

Semaphores vs. mutexes (from wikipedia)
A mutex is essentially the same thing as a binary semaphore and sometimes uses the same basic implementation. The differences between them are in how they are used. While a binary semaphore may be used as a mutex, a mutex is a more specific use-case, in that only the thread that locked the mutex is supposed to unlock it. This constraint makes it possible to implement some additional features in mutexes:

  • Since only the thread that locked the mutex is supposed to unlock it, a mutex may store the id of thread that locked it and verify the same thread unlocks it.
  • Mutexes may provide priority inversion safety. If the mutex knows who locked it and is supposed to unlock it, it is possible to promote the priority of that thread whenever a higher-priority task starts waiting on the mutex.
  • Mutexes may also provide deletion safety, where the thread holding the mutex cannot be accidentally deleted.
  • Alternately, if the thread holding the mutex is deleted (perhaps due to an unrecoverable error), the mutex can be automatically released.
  • A mutex may be recursive: a thread is allowed to lock it multiple times without causing a deadlock.

Semaphore is one of the thread synchronization mechanisms. Unlike mutex, semaphore allows more than one thread to access similar shared resources at the same time. There are two types of semaphores

  • binary semaphore
  • counting semaphore.

Pipes and FIFOs

Pipes are used for communicating data between the processes. Output of a process is piped as an input to another process.

cat doctum.txt | wc

Linux: Pipes no Linux
Output of the cat command goes to word count

image credit: https://www.vivaolinux.com.br/dica/Pipes-no-Linux





FIFOs are named pipes. FIFOs can be used as follows:

int mkfifo(const char *path, mode_t mode);
int mkfifoat(int fd, const char *path, mode_t mode);

once the FIFOs are made, they can be opened using open command and the normal file I/O functions (e.g., closereadwriteunlink) all work with FIFOs.

Linux Processes

process is a program in execution. Since linux represent everything in terms of files, currently running processes are also represented using /proc file system. The proc/<pid> contains open files (sockets), pending signals, process state, kernel data structures, threads of execution and data section.

Processes provides two types of virtualization

  • Virtual Processor
  • Virtual Memory

Processes are created on linux using fork() system call. When fork() is called, a process is created which is child of process who is called fork(). The reason it’s called as a child because it gets copy of resources (data, variables, code, pages, sockets etc) from it’s parent process.

The list of processes are stored in a doubly linked list called as task list. The process descriptor is type  struct task_struct defined in <linux/sched.h> .

Processes are identified by PID. PID is a defined by pid_t data structure which is an integer up to 32,768. Generally processes up to number 1024 is kernel processes and rest of them are user processes. When a new process is forked, the number is not sequential but its randomized in order to avoid being guesses. When number is processes reaches max limit, the number is reseted and starts from 1024. The limit of number of processes can be increased by setting value at proc/sys/kernel/pid_max.

Process creation

  • fork()
    • a process can create another process using fork() function.
    • It is implemented using clone()
    • fork(), vfork() and __clone() calls clone() which calls do_fork() which calls copy_process()
    • the process created is called as child process
    • Example of simple fork call:
      pid_t pid = fork();
    • if return value of fork() call is 0, fork is successful and control block is in child process.
       if (pid == 0)
            printf("child process");
    • if return value of fork() call is greater than 0, fork is successful and control block is in parent process process.
      else if (pid > 0)
            printf("parent process");
    • if return value of fork() is negative, the call is failed.
            printf("fork failed");
    • fork() creates a child process that is a copy of the current task. It differs from the parent only in its PID, its PPID (parent’s PID), and certain resources and statistics (e.g. pending signals) which are not inherited
    • Besides the open files, other properties of the parent are inherited by the child:
      • Real user ID, real group ID, effective user ID, and effective group ID
      • Supplementary group IDs
      • Process group ID
      • Session ID
      • Controlling terminal
      • The set-user-ID and set-group-ID flags
      • Current working directory
      • Root directory
      • File mode creation mask
      • Signal mask and dispositions
      • The close-on-exec flag for any open file descriptors
      • Environment
      • Attached shared memory segments
      • Memory mappings
      • Resource limits
  • exec():
    • The exec() family of function calls creates a new address space and loads a new program into the newborn child immediately after a fork.
    • There are following variations of exec calls
      • int execl(const char *path, const char *arg, ...
         /* (char *) NULL */);
      • int execlp(const char *file, const char *arg, ...
         /* (char *) NULL */);
      • int execle(const char *path, const char *arg, ...
         /*, (char *) NULL, char * const envp[] */);
      • int execv(const char *path, char *const argv[]);
      • int execvp(const char *file, char *const argv[]);
      • int execvpe(const char *file, char *const argv[],
         char *const envp[]);
Function pathname filename fd Arg list argv[] environ envp[]
execl * * *
execlp * * *
execle * * *
execv * * *
execvp * * *
execve * * *
fexecve * * *
(letter in name) p f l v e

Process 0 and 1

Process 0 is ancestor of all processes which is also known as swapper process. This process is build from scratch during boot up. Process 0 initializes all the data structures needed by kernel, enables interrupts, and creates init process which is process 1.init process, invoked by the kernel at the end of the bootstrap procedure. It is responsible for bringing up the system after the kernel has been bootstrapped. init usually reads the system-dependent initialization files (/etc/rc* files or /etc/inittab and the files in /etc/init.d) and brings the system to a certain state. Process 1 never dies. It is a normal user process, not a system process within the kernel, but runs with superuser privileges.

State of a Process

Process can be any one of following states:

    • Process is being executed on CPU or waiting
    • Process is sleeping/suspended.
    • Process is in sleeping state but signal to these processes will not change state of the process.
    • Process being stopped.
    • Process is being debugged
    • Child process is being removed because parent process issued wait4() or waitpid()
    • Child process being terminated but parent has not issued wait() or waitpid()

Copy on Write – an optimization on fork()

All the data and resources that belong to the parent are not copied to child. This is done is steps and as needed. This is an optimization in order to delay copying data as needed. The another reason is in calls such as exec(), none of the parent data is actually needed, there should not be a need to copy any pages from parent.

Process Switch

During process switch the registers are saved in kernel memory area for process and loaded back when process resumes on CPU. This is was done using far jmp assembly instruction on x86. On linux 2.6 onwards software is used for context switching instead of hardware context switching. Software context switch is safer and faster.


Processes work on time slicing basis giving user the illusion that only the user has access to the CPU and the memory is unlimited. The scheduling of processes depend upon scheduling policy or algorithm. The scheduling algorithm must schedule in such a way that processes should have fast response, good throughput, limited use of resources and honor the priorities.

Linux processes are preemptive. A process with high priority than low priority runs first by interruption of low priority process is one is running. There are following classes of Linux processes:


Scheduling factors for a process

  • static priority: between 100 (high priority) to 139 (low priority)
  • nice value: -20 (high priority) to 19 (low priority)
  • dynamic priority: between 100 (high priority) to 139 (low priority)
  • real-time priority: 1 (highest priority) to 99 (lowest priority)

Kernel Preemption

In non-preemptive kernels, kernel code runs until completion. That is, the scheduler cannot reschedule a task while it is in the kernel: kernel code is scheduled cooperatively, not preemptively. Kernel code runs until it finishes (returns to user-space) or explicitly blocks.

The Linux kernel (since 2.6), unlike most other Unix variants and many other operating systems, is a fully preemptive kernel. It is possible to preempt a task at any point, so long as the kernel is in a state in which it is safe to reschedule.


Linux threads are light weight processes i.e. Linux does not make any difference between threads and processes. They share resources with parent like heap space, file descriptors, sockets  but each thread gets own stack.

  • each thread contain TCB- a thread control block which contains following
    • Thread Identifier:Unique id (tid) is assigned to every new thread
    • Stack pointer: Points to thread’s stack in the process
    • Program counter: Points to the current program instruction of the thread
    • State of the thread (running, ready, waiting, start, done)
    • Thread’s register values
    • Pointer to the Process control block (PCB) of the process that the thread lives on
  • threads are also created with clone() system call like other processes except for some flags to clone like

Address Space of a Process

The address space of a process consist of linear addresses the process is allowed to use. The linear address spaces are different per process. The linear addresses are managed in form of Memory Regions. Following are examples of system calls to manage memory regions:

Syscall usage
brk()/sbrk() changing the heap size of process
execve Load a new program in the memory in the currently running process
_exit() exit the current process and delete the memory space occupied
fork() create a new (child) process, copying/referencing page tables from parent process
mmap(), mmap2() creates memory mapped file, enlarge the memory address space of the process.
mremap() Expand or shrink memory region
munmap() destroys previously mmaped memory area and shrinks memory space of the process
shmat() Attaches new memory region to the process
shmdt() Detaches new memory region to the process

List all processes

Since linux uses proc file system to represent processes, listing all the processes can be done using ls /proc/

Screen Shot 2018-03-04 at 11.24.18 PM

listing /proc/<PID>/

Screen Shot 2018-03-04 at 11.28.01 PM

The directories and files listed here represent resources like file descriptors /fd/ etc

Memory Descriptor

The address associated with a process is stored in memory descriptor with type mm_struct. All the descriptors are stored in a doubly linked list with type mmlist.

Heap Management

malloc(size): c stdlib method to request size of Dynamic memory. On success returns pointer to  first linear address. On failure returns non zero integer.

calloc(n, size):c stdlib method to request size of Dynamic memory. On success returns pointer to  first linear address, set the memory to 0. On failure returns non zero integer.

realloc(size):c stdlib method that changes the size of memory location of previously allocated memory region.

free(): frees the allocated memory.

brk(address): Modifies the heap directly

sbrk(incr): increases/decreases the memory region

brk() System call:

  • brk() is the only function that is a syscall. All the other functions listed above are implemented using brk() and mmap()
  • it allocated and deallocated whole pages since it acts on memory region.

System calls a.k.a syscalls:

syscalls are implemented in Kernel and can be called from a process running in user space with appropriate privileges. There are around 330 number of system calls in Linux. The Linux API is written in c.

Process Termination

Process termination can be normal (finishing intended code execution) or can be abnormal. The Abnormal execution is because of following reasons:

  • Kernel, the process itself or any other process send certain signal.
  • Sigfault: Process tries to access memory location which it does not have privilege of access.
  • Abnormal conditions is exit with non-zero code.

On process exit Kernel releases the memory and other resources held by the process like file descriptors.

When Parent process dies, the children of that process becomes orphan processes and the process init becomes parent of those processes. Sometimes parents do not wait for child processes after fork(). These child processes becomes zombi processes after termination. A process can wait (block) when its children are in the running state using wait or waitpid.

  • The wait function can block the caller until a child process terminates, whereas waitpid has an option that prevents it from blocking.
  • The waitpid function doesn’t wait for the child that terminates first; it has a number of options that control which process it waits for.

Linux Performance Optimization

3 main levels for tuning

  1. CPU/BIOS tuning:
  2. OS tuning:
  3. Network Tuning:

Configuration using tuned

  • tuned is available from RHEL7
  • Make changes in sysctl as well as /sys directory
  • there are profiles available for specific needs like network-latency, latency-performance, network-performance, throughput-performance, desktop and balanced etc

Screen Shot 2018-03-14 at 7.49.16 PM

Examples of the profiles

Screen Shot 2018-03-14 at 7.50.11 PM

Latency Performance Settings in Linux Tuned

Settings  Meaning
force_latency=1 processor state C1
governor=performance CPU is at higher performance state
energy_perf_bias= performance Higher performance state
min_perf_pct=100 comes from the P-state drivers. The interfaces provided by the cpufreq core for controlling frequency the driver provides sysfs files for controlling P state selection. These files have been added to /sys/devices/system/cpu/intel_pstate.
kernel.sched_min_granularity_ns=10000000 Minimal preemption granularity for CPU-bound tasks
vm.dirty_ratio=10 The generator of dirty data starts writeback at this percentage
vm.dirty_background_ratio=3 Start background writeback (via writeback threads) at this percentage
vm.swappiness=10 The swappiness parameter controls the tendency of the kernel to move processes out of physical memory and onto the swap disk. 0 tells the kernel to avoid swapping processes out of physical memory for as long as possible 100 tells the kernel to aggressively swap processes out of physical memory and move them to swap cache
kernel.sched_migration_cost_ns=5000000 The total time the scheduler will consider a migrated process “cache hot” and thus less likely to be re-migrated
net.core.busy_read=50 This parameter controls the number of microseconds to wait for packets on the device queue for socket reads. It also sets the default value of the SO_BUSY_POLL option.
sysctl.net.core.busy_poll=50 This parameter controls the number of microseconds to wait for packets on the device queue for socket poll and selects
kernel.numa_balancing=0 disable NUMA balancing
net.ipv4.tcp_fastopen=3 Linux supports configuring both overall client and server support via /proc/sys/net/ipv4/tcp_fastopen (net.ipv4.tcp_fastopen via sysctl). The options are a bit mask, where the first bit enables or disables client support (default on), 2nd bit sets server support (default off), 3rd bit sets whether data in SYN packet is permitted without TFO cookie option. Therefore a value of 1 TFO can only be enabled on outgoing connections (client only), value 2 allows TFO only on listening sockets (server only), and value 3 enables TFO for both client and server.

More information about Tunables:

  • Dependent on NUMA:
    • Reclaim Ratios
      • /proc/sys/vm/swappiness
      • /proc/sys/vm/min_free_kbytes
  • Independent of NUMA:
    • Reclaim Ratios
      • /proc/sys/vm/vfs_cache_pressure
      • Writeback Parameters
        • /proc/sys/vm/dirty_background_ratio
        • /proc/sys/vm/dirty_ratio
      • Readahead parameters
        • /sys/block/queue/read_ahead_kb

top utility

  • available on all the machines
  • default tool for measurement that has lot of information.

Parameters important for Optimization


  • Controls how aggressively the system reclaims anonymous memory versus
    page cache memory:

    • Anonymous memory – swapping and freeing
    • File pages – writing if dirty and freeing
    • System V shared memory – swapping and freeing
  • Default is 60
  • If it is decreased: more aggressive reclaiming of page cache memory
  • If it is Increased: more aggressive swapping of anonymous memory
  • Should be set to 0 as per the low latency optimization guide http://wiki.dreamrunner.org/public_html/Low_Latency_Programming/low-latency-programming.html

Memory reclaim watermarks:

Screen Shot 2018-03-14 at 10.54.08 PM


  • Controls NUMA specific memory allocation policy
  • When set and node memory is exhausted:
    • Reclaim memory from local node rather than allocating
      from next node
    • Slower initial allocation, higher NUMA hit ratio
  • When clear and node memory is exhausted:
    • Allocate from all nodes before reclaiming memory
    • Faster initial allocation, higher NUMA miss ratio
  • To see current setting: cat /proc/sys/vm/zone_reclaim_mode
  • Turn ON: echo 1 > /proc/sys/vm/zone_reclaim_mode
  • Turn OFF: echo 0 > /proc/sys/vm/zone_reclaim_mode
  • It is recommended that the settings should be off for large in memory database server.

CPU Tuning

  • p-states
    • It’s an Advanced Configuration and Power Interface (ACPI) defined processor performance state.
    • P0, P1, P2..p11 etc are values for P-states. For highest performance the p-states should be set to P0
  • c-states
    • It allow the CPU package to shut down cores and parts of the CPU microarchitecture to save energy while balancing response times.

    • C0, C1, C3, C6 etc are the values for c-states. Here is the chart for more information

      Mode Name What it does CPUs
      C0 Operating State CPU fully turned on All CPUs
      C1 Halt Stops CPU main internal clocks via software; bus interface unit and APIC are kept running at full speed. 486DX4 and above
      C1E Enhanced Halt Stops CPU main internal clocks via software and reduces CPU voltage; bus interface unit and APIC are kept running at full speed. All socket LGA775 CPUs
      C1E Stops all CPU internal clocks. Turion 64, 65-nm Athlon X2 and Phenom CPUs
      C2 Stop Grant Stops CPU main internal clocks via hardware; bus interface unit and APIC are kept running at full speed. 486DX4 and above
      C2 Stop Clock Stops CPU internal and external clocks via hardware Only 486DX4, Pentium, Pentium MMX, K5, K6, K6-2, K6-III
      C2E Extended Stop Grant Stops CPU main internal clocks via hardware and reduces CPU voltage; bus interface unit and APIC are kept running at full speed. Core 2 Duo and above (Intel only)
      C3 Sleep Stops all CPU internal clocks Pentium II, Athlon and above, but not on Core 2 Duo E4000 and E6000
      C3 Deep Sleep Stops all CPU internal and external clocks Pentium II and above, but not on Core 2 Duo E4000 and E6000; Turion 64
      C3 AltVID Stops all CPU internal clocks and reduces CPU voltage AMD Turion 64
      C4 Deeper Sleep Reduces CPU voltage Pentium M and above, but not on Core 2 Duo E4000 and E6000 series; AMD Turion 64
      C4E/C5 Enhanced Deeper Sleep Reduces CPU voltage even more and turns off the memory cache Core Solo, Core Duo and 45-nm mobile Core 2 Duo only
      C6 Deep Power Down Reduces the CPU internal voltage to any value, including 0 V 45-nm mobile Core 2 Duo only
    • Latency for C states








      1 μs

      1 μs


      106 μs

      80 μs


      345 μs

      104 μs

How to Optimize

  1. Use real production system for measurement
  2. Note the state of system before change
  3. Apply the optimizations later going to come in the post.
  4. Compare state of system after applying the optimizations
  5. Tune until you get desired results.
  6. Document the changes.

Types of Tools needed

  • Tools that gather system information or Hardware
    • lscpu
    • uname
    • systemctl list -units -t service
  • Tools for measuring Performance
  • Tools for Microbenchmarking

Optimization include Benchmarking, Profiling and Tracing

  • Benchmarking
    • this is comparing performance with industry standard
    • Tools used for benchmarking
      • vmstat used for benchmarking virtual memory
      • iostat used for benchmarking io
      • mpstat multiple processor
  • Profiling gathering information about hot spots
  • Tracing

Based on the Benchmarking, Profiling and Tracking the system is tuned as follows;

  • using echo into /proc
    • The settings are not persistent. Stay until reboot.
    • /proc files system has pid directories for processes, configuration files and sys directory
      • /proc/sys directory has some important directories like /kernel, /net, /vm , /user etc.
      • /proc/sys/vm has settings for with virtual memory.
  • Using sysctl command
    • sysctl it’s a service
    • Persistent settings.
    • It’s started at the boot time’s
    • It reads settings from a configuration file at /etc directory
    • There are some more settings in
      • usr/lib/sysctl.d stores the default
      • /run/sysctl.d stores the runtime
    • /etc/sysctl.d stores runtime settings
  • Using loading/unloading of kernel modules and configure kernel parameters
    • Using modinfo to gather information about available parameters
    • Using modprobe for modifying parameters
    • modprobe modulename key=val
    • for persistent settings, /etc/modprobe.d modulename.conf

Linux Memory Management

Memory Address

For x86 Architecture there are 3 types of addresses:

  • Logical Address:
    • This address is address of an instruction or data in machine language
    • This address consist of a segment and an offset i.e. distance from segment start address.
  • Linear address or Virtual address:
    • This address is a binary number in virtual memory that enables a process to use a location in main memory independently of other processes and to use more space than actually exists in primary storage by temporarily relegating some contents to a hard disk or internal flash drive.
  • Physical Address:
    • Address of the memory cells in RAM of the computer.

Need for Virtual Addressing

  • The main memory (RAM) available for a computer is limited.
  • Many processes use a common code in libraries.
  • Using Virtual addressing, a CPU and Kernel gives an impression to a process that the memory is unlimited.

Address Translation

  • Since 2 out of 3 address are virtual mentioned above, there is a need for address translation from Logical to Linear and Linear to Physical address.
  • For this reason each CPU contains a hardware names as Memory Management Unit (MMU).
  • Segmentation Unit: converts the Logical address to Linear.
  • Paging Unit: converts Linear address to Physical.
  • The address translation from linear address is done using two translation tables
    • Page Directory
    • Page Table


Image Credit: https://manybutfinite.com/post/memory-translation-and-segmentation/

Address Translation in Intel x86


Linear-Address Translation to a 4-KByte Page using IA-32e Paging


Formats of CR3 and Paging-Structure Entries with PAE Paging



Image Credit: By Mdjango, Andrew S. Tanenbaum (Own work) [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], via Wikimedia Commons

Segmentation and Paging in Linux

  • Both segmentation and Paging is redundent and hence Linux use segmentation in limited way.
  • Segmentation can assign a different linear address space to each process
  • Paging can map the same linear address space into different physical address spaces.

Segments and their usage

  • Each segment is described by 8-byte Segment Descriptor.
  • These descriptors are defined in Global Descriptor Table (GDT) or in the Local Descriptor Table(LDT).


Image credit: By John Källén (jkl at commons) (Own work) [Public domain], via Wikimedia Commons

Types of Segment Descriptors

  • Code Segment Descriptor
  • Data Segment Descriptor
  • Task State Segment Descriptor

Segmentation in Linux


image credit https://manybutfinite.com/post/anatomy-of-a-program-in-memory/

Data structures for segmentation

  • GDT Global Descriptor Table
    • There is one GDT per CPU in Linux.
    • There are 18 descriptors in each GDT for various purposes as follows:
      • Descriptors for Kernel code and User code.
      • Task State Segment (TSS)
      • default Local Descriptor Table (LDT)
      • Thread-Local Storage (TLS) segments
      • Advanced Power Management (APM )
      • Plug and Play (PnP ) BIOS services
      • Special segment used for handling exceptions.


Image Credit: Lars H. Rohwedder (User:RokerHRO – selfmade work


  • paging unit translates linear addresses into physical ones
  • For efficiency the linear addresses are divided in fixed length intervals called as pages. These continuous linear addresses within a page are mapped into continuous physical addresses.
  • Page frames: main memory is divided into fixed lenght page frames. Each page frame contains a page. Page is just block of data in memory or disk.
  • page tables: The data structures that map linear to physical addresses.
  • Page Size: 4 KB
  • Huge Pages: 2 MB and 1 GB.
  • Page address (32 bit) = Directory (10 bits) + Page Table (10 bits) + Offset(12 bit)

Physical Address Extension (PAE)

  • In order to use more than 4 GB memory Intel started using 36 pins for address translation effectively supporting more addresses.

Caching in Hardware

  • There are atleast 3 levels of caches supported in modern microprocessor.
  • The caches work on principle of spatial locality and principle of temporal locality.
  • Cache is devided into cache line generally of 64 bytes.
  • Most of caches are N-way associative.
  • Cache unit resides between the paging unit and the main memory.
  • It includes both a hardware cache memory and a cache controller.
  • Each cache line has a tag and some flags that stores the status of cache line.
  • CPUs first look for address in cache before looking into main memory.
  • Flushing cache is done using write Back mechanism which is more efficient. Only cache entry is updated by CPU and the main memory is updated eventually.

Translation Lookaside Buffers (TLB)

  • This is kind of a cache used for storing recently converted addresses between linear to physical.
  • The Address Translation unit first looks in TLB for physical address for given linear address if not found, the hardware goes through page tables to find the page.


Process page tables

  • Linux stores pages using 4 levels
  • Page Global Directory
  • Page Upper Directory
  • Page Middle Directory
  • Page Table
  • Each process has its own Page Global Directory and its own set of Page Tables.
  • Linear addresses from 0x00000000 to 0xbfffffff can be addressed when the process runs in either User or Kernel Mode.
  • Linear addresses from 0xc0000000 to 0xffffffff can be addressed only when the process runs in Kernel Mode.

Non Uniform Memory Access

NUMA is a shared memory architecture used in today’s multiprocessing systems. Each CPU is assigned its local memory and can access memory from other CPUs in the system. Local memory access provides the best performance; it provides low latency and high bandwidth. Accessing memory that is owned by the other CPU has a performance penalty, higher latency, and lower bandwidth.

  • Access to local memory is fast, more latency for remote memory
  • Practically all multi-socket systems have NUMA
  • Most servers have 1 NUMA node / socket
  • Some AMD systems have 2 NUMA nodes / socket
  • Sometimes optimal performance still requires manual tuning.

Typical 4 node NUMA system.

Screen Shot 2018-03-14 at 7.51.21 PM

Image credit: https://videos.cdn.redhat.com/summit2015/presentations/15284_performance-analysis-tuning-of-red-hat-enterprise-linux.pdf

Processors and Memory layout in NUMA system

Screen Shot 2018-03-14 at 11.53.58 PM

Image credit: http://pages.rubrik.com/rs/794-OHF-673/images/vSphere_6.5_Host_Resources_Deep_Dive.pdf


Screen Shot 2018-03-14 at 11.58.39 PM

Image credit: http://pages.rubrik.com/rs/794-OHF-673/images/vSphere_6.5_Host_Resources_Deep_Dive.pdf

To see the NUMA nodes and which cpus are under numa nodes:

Screen Shot 2018-03-14 at 8.02.02 PM

To see the CPUs under NUMA

Screen Shot 2018-03-14 at 8.05.09 PM

NUMA system represented on my machine.


NUMA related tools

Screen Shot 2018-03-14 at 11.00.34 PM

Numa Settings

  • BalancingTurn off: echo 0 > /proc/sys/kernel/numa_balancing
  • NUMA locality (hit vs miss, local vs foreign)
    • Number of NUMA faults & page migrations
    • /proc/vmstat numa_* fields
  • Location of process memory in NUMA system
    • /proc/<pid>/numa_maps
  • Numa scans, migrations & numa faults by node
    • /proc/<pid>/sched


More info here


Superscalar Processor Design

Superscalar processors are designed to fetch and issue multiple instructions every machine cycle vs Scalar processors which fetch and issue single instruction every machine cycle.


  • Instruction set architecture provides a contract between software and hardware i.e between program and the machine.
  • ISA is an abstraction between the hardware implementation and programs can be written with knowledge of ISA.
  • ISA ensures portability.
  • For hardware developers, ISA is a specification.
  • The set of instructions defined by ISA is an assembly language.
  • Dynamic-static interface: defined as separation between stuff can be done statically (at compile time) and stuff can be done dynamically (at runtime).

Processor Performance is measured as CPI – cycles per instruction. There are following techniques for decreasing instruction count

  • Executing multiple instructions per cycle using pipelining. The deeper pipeline goes, the branch misprediction penalty goes high as processor has to flush the pipeline and fill it up with new instructions. Also a deeper pipeline increases hardware and latency overhead.
  • Decreasing the instruction count and moving the complexity on Hardware may increase cycle time.

Stages of Execution in Scalar Pipelined Processors

Fetch, Instruction decode, execute, memory and writeback stages in scalar pipelines processors.

Image credit: http://www.oberle.org/procsimu-index.html







Screen Shot 2018-03-17 at 11.31.11 PM
CRAY-1 is an example of superpipelined processor
Screen Shot 2018-03-17 at 11.38.49 PM
Superscalar Instruction level parallelism machines
Screen Shot 2018-03-17 at 11.38.39 PM
Very Long Word Instruction Set Machines

Stages in scalar Pipelined processors

  1. Fetch: Since main memory is slow, the fetch stage is divided into two or more sub-stages. This ensures once the data/instructions starts coming into processor for execution, more than stage is executed in parallel. But since all the next stages are depend upon this stage, the pipeline is stalled until data/instructions become available at this stage. This stage is considered as in-order front-end.
    1. A superscalar processor can fetch more than one instruction in parallel.
  2. Decode: The instructions are divided into further micro-instructions(micro-ops) at this level. Various caching and optimization techniques are done in order to complete this stage faster. This stage is considered as in-order front-end.
    1. for CISC processors this stage is complex and itself is divided into multiple substages.
    2. Since the decoding functionality is extremely complex, the predecoding has been implemented.
  3. Dispatch:
  4. Execution: the execution unit of a processor generally has more parallelism and considered as out of order execution stage. Intel x86 processors have 2 ALU, FPUs and vectorized processors in this stage.
  5. Complete
  6. Retite ( Writeback) : the results of processor execution are written back the registers.


Image credit: By Inductiveload – Own work, Public Domain, https://commons.wikimedia.org/w/index.php?curid=5769084

The instruction types are

  1. Arithmetic Operations
  2. Load/store – data movement operations between memory, caches and registers.
  3. Branch Instructions

Superscalar Pipelines

Image credit: http://euler.mat.uson.mx/~havillam/ca/CS323/0708.cs-323009.html

This an example of a super scalar processor design. The pipeline is not only deep but also parallel.

Dynamic Pipelines

image credit: http://www.cs.utah.edu/~wyman/classes/arch/athlon.html
  • Buffers are used to hold the data between multiple stages in the pipelined design.
  • In parallel pipelined processors, multientry buffers are used.
  • Parallel pipelined design that supports out of order execution of instructions is called as dynamic pipeline.
  • The complex multientry buffer designs allow instructions flow in different order.
    • First of the buffers in pipeline is dispatch buffer. This buffer receives instructions from program in order but can dispatch them out of order to the functional units.
    • Similar kind of buffer named completion buffer is present at the back end of pipeline. It can receive results of computation in any order. This buffer retires the instructions in order and proceeds the results to WB stage.

Buffers in superscalar design

Image credit: https://www.realworldtech.com/haswell-cpu/6/

Example of latest Intel x86 Microprocessor

Each core has following number of hardware units:

  • Reorder Buffer
    • ROB is used for register renaming and reordering the out of order execution results
    • 192 entries
  • Reservation Station
    • has 60 entries
  • Register file
    • 168 integer registers
  • Vector registers
    • 168
  • Loopback buffer
    • 56 entries.
  • μop cache
    • 1536 μops, 8 way, 6 μop line size, per core
  • L1I cache
    • 32 KB, 8 way set associative 64 sets
    • 64 bytes cache line
    • 32 bytes read and write per clock cycle
  • L1D cache
    • 32 KB, 8 way set associative 64 sets
    • 64 bytes cache line
  • L2 cache
    • 256KB, 8 way set associative 512 sets
    • 64 bytes cache line
  • L3 cache
    • 45 MB (ring shaped shared)
  • Instruction Fetch Rate
    • 16 bytes per clock cycle.

Trace Cache

After the instructions fetch, they are decoded and divided into μops. Instructions are stored in the trace cache after being decoded into μops. The opcode has length between 1 to 15.

Here is a nice video about breaking ISA instruction set.

Branch Prediction Techniques

Predicting branches correctly is important for superscalar processor performance. The branch prediction is much predictable because of various techniques explained below:

  • Branch Target Speculation
    • A fully associative cache name Branch Target buffer is used for storing target address of last branch taken. For next lookup, the cache is used.
    • image007image009
  • Branch Conditional Speculation
  • Multi-level adaptive branch predictor
  • Image13
    • The Two-Level Branch Predictor, also referred to as Correlation-Based Branch Predictor, uses a two-dimensional table of counters, also called “Pattern History Table”. It was introduced by Yeh and Patt who because of the fact that the outcome of the branch depends not only on the branch address but also on the outcome of other recent branches (inter branch correlation) and a longer history of the same branch itself (intra branch correlation).
      • A Global Branch History is a shift register in which the outcome of any branch is stored. A “one” is stored for a taken branch and a “zero” for a non-taken one. The register is shifted through while storing the newest value. In order to address the table, the n last branch outcomes are considered.
      • The Local History Table is a table of shift registers of the sort of a global branch history. Each shift register, however, refers to the last outcomes of one single branch. Since this local history table is accessed as a one-level branch prediction table, it is not guaranteed that no overlapping of the branches occurs, and in one shift register may be stored the information of different branches.
      • Since the table has only two dimensions, two of the three information sources have to be selected to access rows and columns. Another method is to merge two sources to one, which will be covered later.
      • In general it can be stated that a two-level branch predictor is more accurate than a one-level branch predictor, but this advantage is also associated with the disadvantage of a more costly implementation and the fact that the so called Warm Up Phase, i.e. the time the table entries contain usable values, is much longer.
  • Static Branch Prediction

    • Static Branch prediction algorithms do not speculate the prediction based on the past hence they are simple. Following are some of the techniques
  • Dynamic Branch Prediction

    • Dynamic Branch prediction predicts at the rate of 80% to 95%.
    • The past outcomes are used as input for branch prediction.
      • One level branch predictor
      • Various predictor features
      • Two level branch predictor
      • Hashing techniques
      • Difficulties
      • Hybrid branch predictor
      • Multiple component Hybrid branch predictor
      • Branch classification
      • Industry branch prediction implementations

Register Renaming

Register renaming is controlled by the reorder buffer and the scheduler. Register renaming is a technique that eliminates the false data dependencies arising from the reuse of architectural registers by successive instructions that do not have any real data dependencies between them.

Machine language programs specify reads and writes to a limited set of registers specified by the instruction set architecture (ISA). For instance, the Alpha ISA specifies 32 integer registers, each 64 bits wide, and 32 floating-point registers, each 64 bits wide. These are the architectural registers



Anatomy of an Assembly Program

Here is a very simple c/c++ program and its assembly program compiled using flag -S.
There are no headers included.

int main(){
  return 0;

Following is the output generated.

This output shows an anatomy of an

; represents sections in the program like .bss section, .text section etc.
 .file "simple.cpp"
 .globl main
 .type main, @function
; entry to main function
; push the current value of each should be pushed onto the stack to be restored at the end
 pushq %rbp
; move the contents of stack pointer to rbp register.
 movq %rsp, %rbp
; push the exit code 0 to the eax register.
 movl $0, %eax
; pop the contents of rbp register.
 popq %rbp
; return from the program.


Virtual Memory

What is Virtual Memory?

It allows us to run more applications on the system than we have enough physical memory to support. Virtual memory is simulated memory that is written to a file on the hard drive.

Why Virtual Memory?

Most of the modern CPUs has memory management unit built in to generate virtual memory addresses. Using virtual memory has following advantages.

  • Main Memory is limited: especially in small devices like raspberry pi which runs linux can run multiple processes each with 32 bit addressing (4GB/process)
  • Sharing: It makes easy for library programs to be shared across applications example glibc.
  • Memory protection: Memory corruption in one program does not affect memory for another program.
  • Only a part of program needs to be in memory execution.


Virtual Memory is implemented with

  • Demand Paging
  • Demand Segmentation

Physical memory management

Zones are defined using data structure struct zone, which is defined in <linux/mmzone.h>. On X86 the physical memory is divided in zones as follows

  • ZONE_DMA First 16MB of memory
  • This is used by (legacy) hardware because the hardware can address only upto 16 bytes.
  • ZONE_NORMAL 16MiB – 896MB
  • The DMA and NORMAL zone page frames can be accessed directly by Kernel.
  • ZONE_HIGHMEM 896 MB – End
  • In 32 bit systems – the page frames belongs to HIGHMEM can not be accessed directly by Kernel.
  • In 64-bit system this problem does not exists because the linear space available is vastly large than the RAM available on the system.

Each zone has a zone descriptor with following fields:

  • free_pages: Number of free pages
  • pages_min: Number of reserved pages
  • pages_low: Low watermark for reclaiming page frames
  • pages_high: High watermark for reclaiming page frames
  • free_area: Blocks of free pages
  • lru_lock: spinlock for any operation
  • wait_table: wait queues of processes waiting on one of the pages in the zone.
  • zone_mem_map: pointer to first page descriptor
  • name: “DMA”, “Normal” or “HighMem”

Screen Shot 2018-03-14 at 8.27.48 PM

Zones in NUMA System

Screen Shot 2018-03-14 at 8.22.46 PM

Memory Management in Linux

  • Some part of main memory is assigned permanenetly to Kernel.
  • Remaining memory is called as Dynamic Memory
  • The effeciancy of system depends upon how effectively the memory is managed.

Page Frame sizes

  • Linux uses 4 KB and 4MB page size by default.
  • With PAE (Physical Address Extension) enabled it can support 2 MB pages.
  • 32-bit architectures have 4KB pages
  • 64-bit architectures have 8KB pages.
  • This means: 4KB pages and 1GB of memory, physical memory is divided into 262,144 distinct pages.

The reason to support 4 KB page size

  • Data transfer between disk and main memory is effecient when smaller page size is used.

Page Descriptors

  • The page information structure is defined using struct page structure. This structure is defined in <linux/mm_types.h>
  • Information about the state of the page frame is stored in page descriptor data structure.
  • Page descriptor store following information:
    • Flags
      • Various flags store the information about page.
      • The flag values are defined in <linux/page-flags.h>.
    • Frame’s reference counter
      • This is important field. When its value is -1, the page frame free and can be accessed by any process or kernel. A 0 or positive number implies, that the page is assigned to one or more processes.
    • Number of page entries
    • Index
    • pointer to least recently used doubly linked list

Memory Allocation

  • Zoned Page Frame Allocator is used by Kernel to handle memory allocation requests for a group of continuous page frames. The algorithm used is called as “Buddy System”. Kernel provides various macros as follows for allocating page frames.
    • alloc_pages(gfp_mask, order)
    • alloc_page(gfp_mask)
    • _ _get_free_pages(gfp_mask, order)
    • _ _get_free_page(gfp_mask)
    • get_zeroed_page(gfp_mask)
    • _ _get_dma_pages(gfp_mask, order)

    Deallocation of page frames is done using following:

    • _ _free_pages(page, order)
    • free_pages(addr, order)
    • _ _free_page(page)
    • free_page(addr)

    High-Memory Page frame mappings:

    There are 3 mechanisms to map page frames in high memory:

    • Permanent Kernel mapping
    • Temporary Kernel Mapping
    • Non Contiguous Memory Allocation


    • Frequent allocations and deallocations of page frames of different sizes may result in several small blocks of free page frames scattered in the block of page frames. Then it is impossible to allocate large chunk of page frames.
    • To fix this issue, Kernel keeps track of existing blocks of free contiguous page frames and avoid need to split up large blocks if request comes for smaller chunk.

    Buddy System

    • This is one of the algorithms for allocating memory from fixed-size segment consisting of physically-contiguous pages.
    • Memory is allocated from the segment using a power-of-2 allocator
      • This method satisfies requests in units sized as power of 2
      • The requests rounded up to next highest power of 2
      • When smaller allocation needed than is available, current chunk split into two buddies of next-lower power of 2
      • Continue until appropriate sized chunk available
    • For example, assume 256KB chunk available, kernel requests 21KB
      • Split into AL and Ar of 128KB each
        • One further divided into BL and BR of 64KB
          • One further into CL and CR of 32KB each – one used to satisfy request
    • Advantage – quickly coalesce unused chunks into larger chunk
    • Disadvantage – fragmentation


Slab Allocator

  • There is an alternate strategy for Memory allocation Slab Allocator.
  • A slab allocator is a list that contains a block of available, already allocated, data structures.
  • When needed the data structure is allocated from the slab, when not needed, it’s returned to the slab rather than freeing.
  • The slab allocator works as generic data structure caching layer.
  • Slab is one or more physically contiguous pages
  • Cache consists of one or more slabs
  • Single cache for each unique kernel data structure
    • Each cache filled with objects – instantiations of the kernel data structure
  • Slab-allocation algorithm uses caches to store kernel objects
    • When cache created, filled with objects marked as free
    • When a new object for a kernel data structure is needed, the allocator can assign any free object from the cache to satisfy the request.
    • The object assigned from the cache is marked as used.
    • There are 3 states of a slab,  full slab has no free objects, an empty slab has no allocated objects and partial slab has some free and some allocator objects.
  • If slab is full of used objects, next object allocated from empty slab
    • If no empty slabs, a new slab is allocated from contiguous physical pages and assigned to a cache
  • Benefits include no fragmentation, fast memory request satisfaction

Screen Shot 2018-02-28 at 11.53.26 PM.png

Screen Shot 2018-03-13 at 8.06.41 PMScreen Shot 2018-03-13 at 8.07.37 PM

Demand Paging

Software Programs are generally very large in size and can not fit entirely in main memory. Hence only part of the pages are brought in main memory from disk when absolutely required.

Advantages of demand paging

  • Similar to a paging system with swapping
  • Less I/O needed, no unnecessary I/O
  • Less memory needed. Example: Raspberry pi.
  • Faster response because of shared libraries.
  • More users can be using the operating system at a time

Details of demand paging

  • Extreme case – start a process with no pages in memory
    • OS sets instruction pointer to the first instruction of process, non-memory-resident page fault
    • And for every other process pages on first access faults for the page
    • Pure demand paging never bring a page into memory until it is required.
  • Actually, a given instruction could access multiple pages multiple page faults
    • One page for the instruction and many for data : unacceptable system performance
    • Fortunately, pain decreased because of locality of reference reasonable performance
  • Hardware support needed for demand paging
    • Page table with valid / invalid bit
    • Secondary memory, usually a high-speed disk. (swap device with swap space)
    • Instruction restart capability after a page fault
      • We must be able to restart the process in exactly the same place and state,
      • With the saved state (registers, condition code, instruction counter) of the interrupted process

Stages in Demand Paging

  1. Trap to the operating system
  2. Save the user registers and process state
  3. Determine that the interrupt was a page fault
  4. Check that the page reference was legal and determine the location of the page on the disk
  5. Issue a read from the disk to a free frame:
    1. Wait in a queue for this device until the read request is serviced
    2. Wait for the device seek and/or latency time
    3. Begin the transfer of the page to a free frame
  6. While waiting, allocate the CPU to some other user : context switch
  7. Receive an interrupt from the disk I/O subsystem (I/O completed)
  8. Save the registers and process state for the other user
  9. Determine that the interrupt was from the disk
  10. Correct the page table and other tables to show page is now in memory: set to v
  11. Wait for the CPU to be allocated to this process again : context switch
  12. Restore the user registers, process state, and new page table, and then resume the interrupted instruction: restart

Copy on Write

  • Copy-on-Write (COW) allows both parent and child processes to initially share the same pages in memory: fork() system call
    • If either process modifies a shared page, only then is the page copied
  • COW allows more efficient process creation as only modified pages are copied
  • In general, free pages are allocated from a pool of zero-fill-on-demand pages
    • Why zero-out a page before allocating it?
  • vfork() as a variation on fork() system call has parent process suspended and child process uses address space of parent.
    • Different from fork() with copy-on-write.
    • Do not use copy-on-write; changes made by the child process on any pages of the parent’s address space the altered pages will be visible to the parent once it resumes
    • Must be used with caution to prevent the child from modifying the parent address space
    • vfork() is intended to be used when the child calls exec()immediately after creation
    • No copy of pages, very efficient method of process creation.

Handling Page Fault

  1. Check an internal table (within PCB) to decide:
    1. Invalid reference ⇒ abort, terminate the process
    2. Valid reference ⇒ page it in when it is not in memory
  2. Find a free frame (taking one from the free-frame list)
  3. Schedule a disk operation to read the desired page into the new frame
  4. Reset tables to indicate the page is now in memory
  5. Restart the instruction that was interrupted by the trap caused by the page fault

Screen Shot 2018-02-28 at 11.40.07 PMScreen Shot 2018-02-28 at 11.40.25 PM

Page Replacement Algorithms

  1. Find the location of the desired page on disk
  2. Find a free frame:
    1. If there is a free frame, use it
    2. If there is no free frame, use a page replacement algorithm to select a victim frame
    3. Write the victim frame to the disk if dirty
  3. Bring  the desired page into the (newly) free frame; update the page and frame tables
  4. Continue the process by restarting the instruction that caused the trap

Note now potentially 2 page transfers (one out and one in) for page fault – increasing EAT

LRU Algorithm

  • This is generally good algorithm and used most widely.
  • Use past knowledge rather than future
  • Replace page that has not been used for the longest period of time
  • Associate time of last use with each page

Implementation of the LRU aalgorithm

  • Need hardware assistance to determine an order for the frames defined by the time of last use.
  • Counter implementation
    • Every page entry has a time-of-use field and a logical clock (counter) is added to the CPU;
    • Every time a page is referenced, the clock is incremented and the clock register value is copied into the time-of-use field in its page-table entry.
    • When a page needs to be changed, look at the counters to find smallest value
      • Search through table needed
  • Stack implementation
    • Keep a stack of page numbers in a doubly linked list
    • When a page referenced:
      • Removed from the stack and put on the top
      • Most recently used page is always at the top of the stack.
      • requires 6 pointers to be changed at worst
    • But each update more expensive
    • No search for replacement; the tail points to the bottom of the stack, the least recently used (LRU) page.
  • LRU and OPT are cases of stack algorithms that don’t have Belady’s Anomaly