8 minute read

We want to share memory among programs.

Each byte has its own address.

If we run this code:

    add ecx, 1
    jump start

the start: is at memory address 100. By the time it reaches the jump start the program may have move in memory to memory address 115 which means it wont work. Compile time binding is where a program wont’ get moved in memory.

Load time binding

Ideally would like programs to run anywhere in memory

May be able to generate position independent code (PIC)

Aided by various modes:

pc-relative: jump to current pc value + 5 register-indexed: load

Various addressing mode let’s us do things relative to the content of a register.

We can’t always use position independent code. Some instructions require absolute addresses and not realtive addresses.

If not the program can include a list of instruction addresses that need to be inistalised by loader.

Dynamic Run-Time Binding

Used in modern systems

We assume that every program will run at address 0. You can’t run all programs at address 0.

For programs with address space of size N, all addresses are in range 0 to N-1. Program isn’t going to run at address 0. These are logical addresses. At some point you have to convert these back to real physical addresses.

There are logical (virtual) assistants.

Mapping to physical addresses handled at run-time by CPU’s memory management unit (MMU).

The MMU’s job is to turn all logical addresses to physical addresses. In theory it’ll add +100 to an address to get it at the right physical address.

Logical and Physical Addresses

Addresses are generated by the CPU are known as logical addresses.

The set of all logical addresses generated by a program is known as the logical address space.

The addresses generated by the MMU are known as physical addresses,

The set of all these are called the physical address space.

The addresses generated by ompile-time binding and load time binding result in the logical adn the physical addresses at the saem time.

Store is allocated to programs in contiguous partitions from one end of the store to the other.

Each process has a base or datum (where it starts)

each process also has a limit (how big the program is, how much space or length it occupies)

Loading programmes

we wait for programs to finish before bringing in big programs. We may also need to chose which partition to put a program into. This gives us selection policies, how do we select a partition to load a program.

Fragmentation is what happens when you put a 5kb file into a 6kb space, there is a 1kb fragmentation.

  • first fit - choose first partition of suitable size
  • best fit - choose smallest partition which is big enough
  • worst fit - choose biggest partition
    • we want the worst fitting partition because it may not fragment so much.

It may not be any.

Fragmentation may be severe.

50% rule * for first fit if amount of memory allocated is N, then the amount unusable owing to fragmentation is 0.5N or half unusuable memory

Shortage of memory arrising from fragmentation may not be able to support enough users may have dificuklty loading enough programs to obtain good job mix. we want a mix of input and calculation programs.

Imposes limitations on progra mstructure.

  • not suitable for sharing routiens and data
  • does not reflect high level language structures
  • does not handle memory expansion as well


Would like to start more programs than can fit into physical memory.

To eblae this, keep some program images on disk.

During shceduling, a process image may be swapped in and another swapped out to make room.

  • also helps to prevent starvation

For efficieny may have dedicated swap space on disk.

however swapping whole processes adds considerably to time of context switch.

Dynamic loading

Not always neccesary to load entire image

image can consist of

  • main program
  • error routines

dynamic loading allows us to load the bits we need.

When a routine calls another routine it checks to see if it has been loaded.


you integrate code you write with bits of code written by other people (compiler).

Linking is the intregration of user code with system or 3rd part libraries.

Static Linking

Copies of the library are included in the ifnal binary program image.

Usually done after compilation. Compile program and the linker will bring in

Dynamic linking

Doesnt bring in bits of code it needs. Brings them in when the program runs and needs those routines.

Memory Organisation

To ameliorate some of the software problems arising from the linear store, more complex memory models are used which roganise the store hierarchically.

we have some empty partitions

60k, 240k, 150k, 600k, 108k, 310k

It has a list of empty partitions in memory and were going to have a new program which requires 100k to run.

Let’s say the system wants to put it into partition of 150k.

Different selection policies possible. Which selection policy is being applied?


Paging is the physical division of a programs address spacce itno equal sized units. Instead we take the whole program space and divide it up into equal size units called pages.

Each page resides within a page frame in the real mmeory. We take our physical memory, divide it up into page frames and each page frame can hold 1 page.

Although we take a program space and divide it up pages do not have to be together in real physical memory.

Within the page table we have one entry for each page of the current process. Each entry tells us where that page is in real memory.

How do we turn our virtual address into a real address?

We take our virtual address and we split it into 2 parts.

They do not have to be split equally.

The top part is used to index the page table. The lower part is used to index that page.

CPU wants something from memory, an address.

but that address is between 0 and n for that process. it’s not a physical address in memory. Whenever we compile a program we produce addresses from 0 to n. We have to convert that virtual address into a real physical address.


how many bits are required to index a page of size 1024 bytes?

12 10 8 11 9

1024 = 2^10 so need 10 bits (remember sizes for future)

we’re using the bottom half of the virtual address to index the page.

We need 4 fits to address a space of 16 since 2^4 is 16.

Segmentation and paging

Segmanatation involves a logical division of the address space varying units of size units are visible to the program, they are related to the program.

Paging physical division of addres space every unit is the same size as every other unit no relation to program structure

Either may be used as a basis for a swapping system

you can have both in place.

More complex mapping function using 2 tables.

Advantages of paging:

  • fixed size units make space allocation simpler

Example intel x86

supports segmentation with paging

cpu generates logical address which is passed to segmentation unit

segmentation unit produces a linear address which is passed to the paging unit

Paging unit generates phsical address in main memory.

virtual memory

the maximum logical address space per process may be smaller than physical memory.

It may also be larger.

Not all pages need to be in memory.


What happens if a process references a page that is not in main memory?

We want to jump in the code or access a data structure and that data is on a different page not in memory.

A page fault occures. it sounds like an error but its not actually an error. All it means is that we’re trying to access a page not accessible in main memory.

Page fault generates an interrupt because address references cannot be satisifed until page swapped in.

operating system response is to get a page

problem 2

what do we do if all our page frames are full?

how do we make room for a fetched page? (page replacement problem)

would like to swap out pages nt immedtially needed. but we have to guesss as we’re trying to work out the future. Which of these pages are not needed in the future?

If we constantly make bad guesses we will get constant swapping (thrasing)

Page replacement

Optimal policy: swap out a page that will not be needed for the longest time in the future.

To estimate this we can use:

principle of locality over any short period of time, a program’s memory references tend to be spatially localised.

What tends to happen is we’ll move to a regeion of address space and we’ll stay in that region for a while.

Principle of locality - if statements are not a part of this since they redirect you to different regions.

Page Replacement

How do we decide what pages to keep and what pages to throw out?

Working set model

The working set of a process is defined to be the set of resources (T, s) defined in the time interval [T, T+s].

Consider the following sequenece of page references in a paged memory management system

Page - | p | q | r | q | q | q | p | r | r | q | time - 0 1 2 3 4 5 6 7 8 9

What is the working set expressed as W(3, 4).

The time interval is between W(3, (3 + 4)) = W(3, 7). It is a set so repitions are not included. So everything from 3 to 7 which is qp or pq (order does not matter as it is a set)

The principle of locality states that when you enter a region of code you tend to stay there because of loops recursion and so on.

By the principal of locality we can predict the next working set usign this formula.

Hence for each process:

Try to ensure its working set is in memory. Estimate next working set by recording set of pages referenced in preceding time intervals.

Predict the next working set using the principle of locality law to predict the next working set for the set W(10, 3).

Since the formula is W(t, s) = W(t - s, s) we do W(10-3, 3) = W(7, 3).

The accuracy of the working set depends on its sixze. If the set is too small, it will not cover the entire locality.

If the set is too large, it will cover several localities.

Over time the working set of a process will change as references to data and code sections move from one locality to another.

Replacement policies which are used:

Least recently used

First in first out

Least frequently used

Consider the following page references:

Page - | p | q | r | q | q | q | p | r | r | q | time - 0 1 2 3 4 5 6 7 8 9

Page s arrives at time 10. Which of the following policies suggests we should throw out page p to make room for s?


All 3 policies suggest we should throw out page p based on this data.

Go through each one.

Least recently used

Page - | p | q | r | q | q | q | p | r | r | q | time - 0 1 2 3 4 5 6 7 8 9

We see q, then r then r again then p. P is the least recently used so throw it out.

Least frequently used

Page - | p | q | r | q | q | q | p | r | r | q | time - 0 1 2 3 4 5 6 7 8 9

q and r are chosen recently so throw out

Frame allocation

The fixed amount of free memory must be allocated among the various processes.

Each process will need a minimum number of pages.

Performance considerations

Segmentation and paging overcome many of our problems. But there is a performance hit. We have to access tables, segmentation tables.

Sometimes we need a special piece of hardware or we can keep our tables in special fast memory such as cache memory.

Page size is also a consideration. A large paze size means a smaller page table.

A small page means lots of them so page table is quite big.

However, large pages mean more wastage.

on average 50% of a page per process lost to internal fragmentation.

Small pages give us a better more finegrained resolution.

Can bring in just the code / data needed for the working set.

Small pages increaes chance of page fault.

Cache Memory

Computer systems have a storage hierachy.

Moving away from the CPU we have registers at the top of the hierarchy. Then main memory, then external storage such as disks.

Access speed decreases as we go down the hierarchy.

What we try to do is keep the data as close to the CPU as possible. We want all data to be in registers but this is impossible as we only have a handful of registers.

Main memory is slower.

We can introduce something called cache memory. Cache memory is a small, fast memory that sits between the CPU and main memory.

It contains copies of items in main memory

When the CPU needs information, it first checks the cache.

If the item is in cache memory then it is called a cache hit.

If it’s not in the cache we have a cache miss.

We bring in a whole block of items. Why do we bring in a whole block of items? Principle of locality. By the principle it is likely that future items will now be in the cache.

You expect your cache-hit ratio to be above 70%.