week 7 memory management

Question 1

describe memory management

Answer 1

Management of a limited resource:
(Memory hunger of applications increases with capacity!)
⇒ Sophisticated algorithms needed, together with support from
HW and from compiler and loader.

Question 2

what is logical address

Answer 2

Key point: program’s view memory is set of memory cells starting
at addresss 0x0 and finishing at some value (logical address)

Question 3

what is physical address

Answer 3

Hardware: have set of memory cells starting at address 0x0 and
finishing at some value (physical address)

Question 4

goal of memory management

Answer 4

Want to be able to store memory of several programs in main memory at the same time

Question 5

how can we manage memory

Answer 5

eed suitable mapping from logical addresses to physical addresses

Question 6

what happens at compile time

Answer 6

absolute references are generated (eg MS-DOS .com-files)

Question 7

what happens at load time

Answer 7

can be done by special program

Question 8

what happens at execution time

Answer 8

needs HW support

Question 9

what can we use to take address mapping one step further

Answer 9

dynamic linking

Question 10

what is dynamic linking

Answer 10

use only one copy of system library

Question 11

how does os help memory management

Answer 11

same code accessible to more than one process

Question 12

why does swapping happen

Answer 12

memory demand is too high,

Question 13

what happens in swapping

Answer 13

If memory demand is too high, memory of some processes is
transferred to disk
Usually combined with scheduling: low priority processes are
swapped out
Problems:
Big transfer time
What to do with pending I/O?
First point reason why swapping is not principal memory
management technique

Question 14

what are problems with swapping

Answer 14

Big transfer time
What to do with pending I/O?

Question 15

what is swapping usallu combined with

Answer 15

scheduling

Question 16

is swapping a primary memory management technique

Answer 16

no -> seen as a last resort

Question 17

wha is fragmentation caused by

Answer 17

swapping

Question 18

what are the two types of fragmentation

Answer 18

internal and external

Question 19

describe internal fragmentation

Answer 19

programs only a little smaller than hole ⇒ leftover too small to qualify as hole

Question 20

describe external fragmentation

Answer 20

over time, many small holes appear in memory

Question 21

what are the 4 strategies to choose holes in fragmentation

Answer 21

first fit
rotating first fit
best fit
buddy system

Question 22

what is first fit

Answer 22

Start from beginning and use first available hole

Question 23

what is rotating first fit

Answer 23

start after last assigned part of memory

Question 24

what is best fit

Answer 24

find smallest usable space

Question 25

what is buddy system

Answer 25

Have holes in sizes of power of 2. Smallest possible hole used. Split hole in two if necessary. Recombine two adjacent holes of same size

Question 26

how can we avoid external fragmentation

Answer 26

paging

Question 27

describe paging

Answer 27

Alternative approach: Assign memory of a fixed size (page) ⇒ avoids external fragmentation Translation of logical address to physical address done via page table

Question 28

describe hardware use in paging

Answer 28

Hardware support mandatory for paging: If page table small, use fast registers. Store large page tables in main memory, but cache most recently used entries

Question 29

what do we use if page table is small

Answer 29

fast registers

Question 30

what do we use if page table is large

Answer 30

Store large page tables in main memory, but cache most recently used entries

Question 31

general principle in paging

Answer 31

Whenever large lookup tables are required, use cache (small but fast storage) to store most recently used entries

Question 32

describe memory proctection in paging

Answer 32

Memory protection easily added to paging: protection information stored in page table

Question 33

describe ides of segmentation

Answer 33

Divide memory according to its usage by programs: Data: mutable, different for each instance Program Code: immutable, same for each instance Symbol Table: immutable, same for each instance, only necessary for debugging

Question 34

describe hardware in segmentation

Answer 34

Requires again HW support same principle as paging but have to do a overflow check

Question 35

describe difference between paging and segmentation

Answer 35

Paging motivated by ease of allocation, segmentation by use of memory ⇒ combination of both works well (eg 80386)

Question 36

describe virtual memory

Answer 36

dea: complete separation of logical and physical memory ⇒ Program can have extremely large amount of virtual memory works because most programs use only small fraction of memory intensively. Efficient implementation tricky Reason: Enormous difference between - memory access speed (ca. 60ns) - disk access speed (ca. 6ms for hard disks, 60μs for SDD

Question 37

what is virtual memory impemented as

Answer 37

demand paging

Question 38

describe demand pages

Answer 38

Two strategic decisions to be made: Which process to “swap out” (move whole memory to disk and block process): swapper which pages to move to disk when additional page is required: pager Minimisation of rate of page faults (page has to be fetched from memory) crucial If we want 10% slowdown due to page fault, require fault rate p < 10−6 for HDD and p < 10−4 for SDD

Question 39

what are the 3 page replacement algorithms

Answer 39

FIFO Optimal algorithm Leat recently used

Question 40

descibe FIFO

Answer 40

easy to implement, but does not take locality into account Further problem: Increase in number of frames can cause increase in number of page faults (Belady’s anomaly)

Question 41

describe optimal algorithm

Answer 41

select page which will be re-used at the latest time (or not at all) ⇒ not implementable, but good for comparisons

Question 42

describe leat recently used algorithm

Answer 42

use past as guide for future and replace page which has been unused for the longest time

Question 43

problems with least recently used algorithm

Answer 43

Requires a lot of HW support

Question 44

how to fix least recently used algorithm

Answer 44

Stack in microcode -Approximation using reference bit: HW sets bit to 1 when page is referenced. Now use FIFO algorithm, but skip pages with reference bit 1, resetting it to 0 ⇒ Second-chance algorithm

Question 45

describe thrashing

Answer 45

if process lacks frames it uses constantly, page-fault rate very high. ⇒ CPU-throughput decreases dramatically. ⇒ Disastrous effect on performance

Question 46

what is the 2 solutions to thrashing

Answer 46

working set model page fault frequency

Question 47

what is the working set model

Answer 47

Working-set model (based on locality): Define working set as set of pages used in the most recent ∆ page references keep only working set in main memory ⇒ Achieves high CPU-utilisation and prevents thrashing Difficulty: Determine the working set! Approximation: use reference bits; copy them each 10,000 references and define working set as pages with reference bit set

Question 48

what is the page fault frequency solution

Answer 48

akes direct approach: - give process additional frames if page frequency rate high - remove frame from process if page fault rate low

Question 49

four segments in linux kernel device

Answer 49

Kernel Code Kernel Data User Code User Data

Question 50

kernel address and user address in 32 bit architecture

Answer 50

Have separate logical addresses for kernel and user memory For 32-bit architectures (4 GB virtual memory): kernel space address are the upper 1 GB of address space (≥ 0xC0000000) user space addresses are 0x0 to 0xBFFFFFFF (lower 3 GB) kernel memory always mapped but protected against access by user processes

Question 51

kernel address and user address in 64 bit architecture

Answer 51

For 64-bit architectures: kernel space address are the upper half of address space (≥ 0x8000 0000 0000 0000) user space addresses are 0x0 to 0x7fff ffff ffff, starting from above. kernel memory always mapped but protected against access by user processes

Question 52

describe page caches in linux

Answer 52

Experience shows: have repeated cycles of allocation and freeing same kind of objects (eg inodes, dentries) can have pool of pages used as cache for these objects (so-called slab cache) cache maintained by application (eg file system) kmalloc uses slab caches for commonly used sizes

Question 53

what are caches made of

Answer 53

pool of pages

Question 54

what are caches maintaine by

Answer 54

application (e.g files system)

Question 55

what is kmalloc used for

Answer 55

uses slab caches for commonly used sizes