Operating Systems – Memory Management and Paging – Test 2

Memory is central to the operation of modern OSs – processes must be in and share memory.

Program must be brought (from disk) into memory and placed within a process for it to be run.

large array of words/bytes each with own address.

Main Memory
Main memory and registers are the only storage CPU can access directly.

Register access in 1 CPU clock cycle; Main memory many CPU clock cycles.

Protection of memory required to ensure correct operation.

Memory Hierarchy
CPU registers, cache, primary memory (RAM), magnetic disk (secondary memory), magnetic tape.
Primary Memory
Random Access Memory (RAM).

SRAM and DRAM technology.

Typical access time for DRAM 70 ns.

An array of addressable cells.

Cell – a group of bits : In modern machines, a cell is a group of 8 bits (byte). Each cell in memory has a unique address.

Memory Address
Addresses are unsigned binary numbers.

n bit address – maximum number of addressable cells = 2n.

Memory Address Register (MAR).

Read Only Memory (ROM)
Operates on the same principle as RAM.

Cannot modify information (easily), different kinds – PROM, EPROM, EEPROM.

Base register – holds smallest legal physical memory address a process can access.

Limit register – specifies the range/size.

Processing a User Program
Compiler – program/set of programs that transforms source code written in a programming language (source language) into another computer language (target language or into binary form object code); often used to create an executable program.

Linker/linkage editor – program that takes one or more objects generated by a compiler and combines them into a single executable program.

Loader – program that loads the executable into actual memory.

Binding of Instructions and Data to Memory
Addresses in source program are symbolic addresses (e.g., count) that need to be bound to absolute memory addresses.

Compiler binds symbolic to relocatable addresses.

Linker/loader binds these relocatable addresses to absolute memory addresses.

When can Binding be done
Compile time – done when you know where a process will reside in memory at compile time itself; if location changes then need to recompile.

Load time – if address of process not known at compile time then compiler must produce relocatable code; final binding delayed until load time.

Execution time – If process can be moved during its execution from one memory segment to another, then binding must be delayed until run time (used by most OSs).

Logical or virtual address address space
Address generated by the CPU.
Physical address or real address space
Physical address in memory accessed; address seen by the memory unit (loaded into MAR).

Logical and physical address space differ (especially in exec-time address binding scheme).

Memory Management Unit (MMU)
Hardware device that maps the logical address to physical address (run time).

Logical addresses (0 to max); Physical (R+0 to R+max).

Dynamic Linking and Loading
Routine is not linked and/or loaded until it is called (run-time).

Better memory-space utilization; unused routine is never loaded.

Useful when large amounts of code are needed to handle infrequently occurring cases.

No special support from the OS is required; implemented through program design (modular, library routines).

A process must be in memory to be executed.

A process can be swapped temporarily out of memory to a backing store, and then brought back into memory for continued execution.

Backing store – fast disk large enough to accommodate copies of all memory images for all users.

Context-switch time in a swapping system is high.

Roll out, roll in
Swapping variant used for priority-based scheduling algorithms; lower-priority process is swapped out so higher-priority process can be loaded and executed.
Swap Time
Transfer time is directly proportional to the amount of memory swapped.

Usually a process that is swapped out will be swapped back into the same (previous) memory space.

Execution-time binding allows the process to be moved to a different memory space as the physical addresses are computed only during execution.

System maintains a ready queue of ready-to-run processes which have memory images on disk or in memory.

Contiguous memory allocation for a process
Main memory divided into 2 partitions – 1 for resident OS (in low memory addresses) and 1 for user processes (higher addresses).

Relocation registers used to protect user processes from each other, and from changing OS code/data.

Each process contained in a single contiguous section of memory.

OS with fixed memory partitions
Divide memory into several fixed-size partitions. Each partition has 1 process, degree of multiprogramming bound by number of partitions.

Internal memory fragmentation problem : Wasted memory because allocated memory is larger than requested.

OS with variable memory partition
OS keeps track of available (hole)/occupied memory.

Initially all memory available, one large block/hole. As memory fills up, holes of various sizes develop.

OS keep track of holes and process memory requirements and decides which processes can be allocated memory. Adjacent holes are merged to form a bigger hole.

Cannot allocate a process (contiguous requirement) even though there is enough combined memory.

Dynamic storage allocation problem
First-fit (FF) – Allocate the first hole that is big enough.

Best-fit (BF) – Allocate the smallest hole that is big enough; must search entire list, unless ordered by size; produces the smallest leftover hole.

Worst-fit (WF) – Allocate the largest hole; must also search entire list; Produces the largest leftover hole. May be more useful than smaller leftover hole from BF.

FF and BF are better than WF in terms of time and storage utilization; FF and BF are similar in terms of storage utilization, but FF is faster.

External Fragmentation – ‘total’ memory space exists to satisfy a request, but not contiguous. Place all free memory together in one large block to reduce it.

50-percent rule – given N allocated blocks, 0.5N blocks will be lost to fragmentation.

Internal Fragmentation – allocated memory may be slightly larger than requested memory; this size difference is unused memory internal to a partition, but not being used. Can only be done if relocation is dynamic; done at exec-time

Non-contiguous (physical) memory allocation – place process wherever memory is available.

Divide physical memory into fixed-sized blocks called frames (size is power of 2, usually between 512 – 8Kbytes).

Divide logical memory into blocks of same size called pages. When a process is executed, load its pages from storage into any available frames.

Page sizes
To run a program of size n pages, need to find n free frames and load program.

Set up a page table to translate logical to physical addresses.

Address translation
Virtual/logical address generated by CPU divided into:

Page number (p) – index into a page table which contains base address of each page in physical memory.

Page offset (d) – combined with base address to get physical memory address sent to the memory unit.

Logical address space = 2m ,page size = 2n.

Fragmentation with paging
No external fragmentation – any free frame can be allocated to any page (process).

Internal fragmentation remains – last frame may not be full.

Worst case a process needs n pages plus 1 byte; On average 0.5 page wasted per process; small page sizes are desirable – can reduce swapping.

Small and Large pages
Small pages implies more pages (larger page table/overhead).

To reduce size of page table – larger pages: Disk I/O is more efficient when larger data is transferred.

Separation of logical (users view) and actual physical memory
User does not and should not know where their data goes.

Translation (page table) is hidden by the OS, no way of addressing memory outside of the page table.

Frame Table
Tracks each physical page frame – free/allocated, if allocated, to which page of which process.


Page Table Registers
Page-table base register (PTBR) points to the page table and Page-table length register (PTLR) indicates its size.

Changing page table requires only changing PTBR. Reduces context switch time.

Every access requires two memory accesses – one for the page table and one for the data/instruction (slow by a factor of 2!)

Translation look-aside buffer (TLB)
A fast cache memory in CPU containing (page #, frame #) pairs for recently accessed page table entries (cannot be too large).

Parallely search Associative cache (fast, but very expensive).

Access times/Effective access time when page is in memory
Associative Lookup = time unit.

Hit ratio – percentage of times that a page number is found in the associative registers; related to num. of associative registers.

Equation: 2M – M(PHETA) + E
M =
PHETA = percent
E = time units

Memory Protection
Implemented by associating protection bit with each frame – define a page to be read/write or read only.

Additionally Valid/invalid bit used in each entry of page table indicating whether the associated page is in the process’ logical address space, and is thus a legal page.